Automatic Test Data Generation For Program Paths Using Genetic Algorithms

A new technique and tool are presented for test data generation for path testing. They are based on the dynamic technique and on a Genetic Algorithm, which evolves a population of input data towards reaching and solving the predicates along the program paths. We improve the performance of test data generation by using past input data to compose the initial population for the search. An experiment was done to assess the performance of the techniques compared to that of random data generation.126691709Aamodt, A., Plaza, E., Case-based reasoning: Foundational issues, methodological variations, and system approaches (1994) AICom - Artificial Intelligence Communications, 7 (1), pp. 39-59Bertolino, A., Marré, M., Automatic generation of path covers based on the control flow analysis of computer programs (1994) IEEE Trans. on Software Engineering, 20 (12), pp. 885-889Bird, D.L., Munoz, C.U., Automatic generation of random self-checking test cases (1983) IBM System Journal, 22 (3), pp. 229-245Boyer, R.S., Elspas, B., Karl, N.L., Select: A formal system for testing and debugging programs by symbolic execution (1975) ACM SigPlan Notices, 10 (6), pp. 234-245Bueno, P.M.S., Jino, M., Identification of potentially infeasible program paths by monitoring the search for test data Proc. IEEE Int. Conf. on Automated Software Engineering (ASE2000), IEEE, Grenoble, France, September 2000, pp. 209-218Clarke, L., A system to generate test data and symbolically execute programs (1976) IEEE Trans. on Software Engineering, 2 (3), pp. 215-222De Millo, R.A., Offutt, A.J., Constraint-based automatic test data generation (1991) IEEE Trans. on Software Engineering, 17 (9), pp. 900-910Ferguson, R., Korel, B., The chaining approach for software test data generation (1996) ACM Trans. on Software Engineering and Methodology, 5 (1), pp. 63-86Forgács, I., Bertolino, A., Feasible test path selection by principal slicing (1997) Software Engineering Notes, 22 (6), pp. 378-394Frankl, F.G., Weyuker, E.J., An applicable family of data flow testing criteria (1988) IEEE Trans. on Software Engineering, 14 (10), pp. 1483-1498Gallagher, M.J., Narasimhan, V.L., Adtest: A test data generation suite for Ada software systems (1997) IEEE Trans. on Software Engineering, 23 (8), pp. 473-484Goldberg, D.E., (1989) Genetic Algorithms in Search, Optimization, and Machine Learning, , Addison-WesleyGupta, N., Mathur, A.P., Soffa, M.L., Automated test data generation using an iterative relaxation method (1998) Foundations of Software Engineering, 11, pp. 231-244Gupta, N., Mathur, A.P., Soffa, M.L., UNA based iterative test data generation and its evaluation Proc. IEEE Automated Software Engineering Conference, October 1999Howden, W.E., Symbolic testing and dissect symbolic evaluation system (1997) IEEE Trans. on Software Engineering, 3 (4), pp. 266-278Ince, D.C., The automatic generation of test data (1987) The Computer Journal, 30 (3), pp. 63-69Jones, B.F., Sthamer, H.H., Eyres, D.E., Automatic structural testing using genetic algorithms (1996) Software Engineering Journal, pp. 299-306. , SeptemberKorel, B., Automated software test data generation (1990) IEEE Trans. on Software Engineering, 16 (8), pp. 870-879Laski, J.W., Korel, B., A data flow oriented program testing strategy (1983) IEEE Trans. on Software Engineering, 9 (3), pp. 347-354Maldonado, J.C., Chaim, M.L., Jino, M., Bridging the gap in the presence of infeasible paths: Potential uses testing criteria Proc. XII Int. Conf. of the Chilean Computer Science Society, Santiago, Chile, October 1992Michael, C.C., McGraw, G., Automated software test data generation of complex programs Proc. Int. Conf. on Automated Software Engineering, IEEE, Honolulu, Hawai, October 1998Michael, C.C., McGraw, G.E., Schatz, M.A., Walton, C.C., Genetic algorithms for dynamic test data generation Proc. Int. Conf. on Automated Software Engineering (ASE '97), IEEE, November 1997Miller, W., Spooner, D.L., Automatic generation of floating-point test data (1976) IEEE Trans. on Software Engineering, 2 (3), pp. 223-226Ntafos, S.C., On required element testing (1984) IEEE Trans. on Software Engineering, 10 (6), pp. 795-803Ntafos, S.C., Hakimi, S.L., On path cover problems in digraphs and applications to program testing (1979) IEEE Trans. on Software Engineering, 5 (5), pp. 520-529Offut, A.J., Jin, Z., Pan, J., The dynamic domain reduction procedure for test data generation (1999) Software Practice and Experience, 29 (2), pp. 167-193Ould, M.A., Testing - A challenge to method and tool developers (1991) Software Engineering Journal, pp. 59-64. , MarchPargas, R.P., Harrold, M.J., Peck, R.R., Test-data generation using genetic algorithms (1999) Journal of Software Testing, Verification and Reliability, 9, pp. 263-282Peres, L.M., Vergilio, S.R., Jino, M., Maldonado, J.C., Path selection strategies in the context of software testing criteria 1st Latin American Test Workshop, IEEE, Rio de Janeiro, Brazil, January 2000, pp. 222-227Ramamoorthy, C.V., Siu-Bun, F.H., Chen, W.T., On automated generation of program test data (1976) IEEE Transactions on Software Engineering, 2 (4), pp. 293-300Rapps, S., Weyuker, E.J., Selecting software test data using data flow information (1985) IEEE Transactions on Software Engineering, 11 (4), pp. 367-375Roper, M., Maclean, I., Brooks, A., Miller, J., Wood, M., Genetic algorithms and the automatic generation of test data (1995), Technical Report RR/95/195 Dep. Computer Science, University of Strathclyde, 1995Srinivas, M., Patnaik, L.M., Genetic algorithms: A survey (1994) IEEE Computer, 27 (6), pp. 17-26Tracey, N., Clark, J., Mander, K., Automated program flaw finding using simulated annealing Proc. Int. Symp. on Software Testing and Analysis, ACM, Florida, USA, March 1998, pp. 73-81Tracey, N., Clark, J., Mander, K., McDermid, J., An automated framework for structural test-data generation (1998) IEEE Automated Software Engineering, , IEEE, HonoluluTracey, N., Clark, J., McDermid Mander, K., Automated test-data generation for exception conditions (2000) Software-Practice and Experience, 30, pp. 61-79Ural, H., Yang, B., A structural test selection criterion (1988) Information Processing Letters, 28 (3), pp. 157-163Herman, W.E., Flow analysis approach to program testing (1976) The Australian Computer Journal, 8 (3), pp. 259-266Zbigniew, M., (1996) Genetic Algorithms + Data Structures = Evolution Programs, , Springer Verlag, 3rd ed