Search-based multi-paths test data generation for structure-oriented testing

ABSTRACT

This paper presents a new fitness function to generate test data for a specific single path, which is different from the predicate distance applied by most test data generators based on genetic algorithms (GAs). We define a similarity between the target path and execution path to evaluate the quality of the populations. The problem of the most existing generators is to search only one target data a time, wasting plenty of available interim data. We construct another fitness function combined with the single path function, which can drive GA to complete covering multi-paths to avoid the reduplicate searching and utilize the interim populations for different paths.

Several experiments are taken to examine the effectiveness of both the single path and multi-path fitness functions, which evaluate the functions' performance with the convergence ability and consumed time. Results show that the two functions perform well compared with other two typical path-oriented functions and the multi-paths approach retrenches the searching actually.

REFERENCES

• 1: Gibbs.W. Software's chronic crisis. Sci. Am, 271, 3 (Sept. 1994), 72--81.
• 2: David L. Parnas , A. John van Schouwen , Shu Po Kwan, Evaluation of safety-critical software, Communications of the ACM, v.33 n.6, p.636-648, June 1990 [doi>10.1145/78973.78974]
• 3: Boris Beizer, Software testing techniques (2nd ed.), Van Nostrand Reinhold Co., New York, NY, 1990
• 4: James A. Whittaker, What Is Software Testing? And Why Is It So Hard?, IEEE Software, v.17 n.1, p.70-79, January 2000 [doi>10.1109/52.819971]
• 5: Edvardsson. J. A survey on automatic test data generation. In proceedings of the second conference on computer science and engineering in linkoping, ECSEL, (October 1999), 21--28.
• 6: Phil McMinn, Search-based software test data generation: a survey: Research Articles, Software Testing, Verification & Reliability, v.14 n.2, p.105-156, June 2004 [doi>10.1002/stvr.v14:2]
• 7: Manter. T, Alander. JT. Evolutionary software engineering, a review. Applied Software Computing 5 (2005), 315--331.
• 8: Xanthakis. S, Ellis. C, Skourlas. C, Gall. AL, Katsikas. S, Karapoulios. K. Application of genetic algorithms to software testing. Proceedings of the 5th International Conference on Software Engineering, (Toulouse, France, 1992), 158--164.
• 9: Sthamer. H. The automatic generation of software test data using genetic algorithms. Ph.D. thesis, Department of Electronics and Information Technology, University of Glamorgan, 1996.
• 10: B. Korel, Automated Software Test Data Generation, IEEE Transactions on Software Engineering, v.16 n.8, p.870-879, August 1990 [doi>10.1109/32.57624]
• 11: N. Tracey , J. Clark , K. Mander , J. McDermid, An Automated Framework for Structural Test-Data Generation, Proceedings of the 13th IEEE international conference on Automated software engineering, p.285, October 13-16, 1998
• 12: Bueno. PMS, Jino. M. Automatic test data generation for program path using genetic algorithms. International Journal of Software Engineering and Knowledge Engineering. Vol.12, NO. 6 (2002), 691--09.
• 13: Moataz A. Ahmed , Irman Hermadi, GA-based multiple paths test data generator, Computers and Operations Research, v.35 n.10, p.3107-3124, October, 2008 [doi>10.1016/j.cor.2007.01.012]
• 14: C. C. Michael , G. McGraw , M. A. Schatz, Generating Software Test Data by Evolution, IEEE Transactions on Software Engineering, v.27 n.12, p.1085-1110, December 2001 [doi>10.1109/32.988709]
• 15: Wegener. J, Baresel. A, Sthamer. H. Evolutionary test environment for automatic structural testing. Information and Software Technology 43(2001), 841--54.
• 16: Jin-Cherng Lin , Pu-Lin Yeh, Automatic test data generation for path testing using GAs, Information Sciences: an International Journal, v.131 n.1-4, p.47-64, Jan. 2001 [doi>10.1016/S0020-0255(00)00093-1]
• 17: Pargas. RP, Harrold. MJ, Peck. R. Test-data generation using genetic algorithms. Software Testing, Verification and Reliability 9, (1999), 263--282.
• 18: Wegener. J, Sthamer. H, Pohlheim. H. Testing the temporal behaviour of realtime task using extended evolutionary algorithms. In Proceedings of the 7th European Conference on Software Testing, Analysis and Review (EuroSTAR 1999), (Barcelona, Spain, 1999).
• 19: Alison Watkins , Ellen M. Hufnagel, Evolutionary test data generation: a comparison of fitness functions: Research Articles, Software—Practice & Experience, v.36 n.1, p.95-116, January 2006 [doi>10.1002/spe.v36:1]
• 20: Miller. J, Reformat. M, Zhang. H. Automatic test data generation using genetic algorithm and program dependence graphs. Information and Software Technology 48 (2006), 586--605.
• 21: Nashat Mansour , Miran Salame, Data Generation for Path Testing, Software Quality Control, v.12 n.2, p.121-136, June 2004 [doi>10.1023/B:SQJO.0000024059.72478.4e]
• 22: C. Del Grosso , G. Antoniol , E. Merlo , P. Galinier, Detecting buffer overflow via automatic test input data generation, Computers and Operations Research, v.35 n.10, p.3125-3143, October, 2008 [doi>10.1016/j.cor.2007.01.013]
• 23: N. Tracey , J. Clark , K. Mander , J. McDermid, Automated test-data generation for exception conditions, Software—Practice & Experience, v.30 n.1, p.61-79, Jan. 2000 [doi>10.1002/(SICI)1097-024X(200001)30:1<61::AID-SPE292>3.0.CO;2-9]
• 24: Oliver Bühler , Joachim Wegener, Evolutionary functional testing, Computers and Operations Research, v.35 n.10, p.3144-3160, October, 2008 [doi>10.1016/j.cor.2007.01.015]
• 25: Parker. A. Algorithms and data structures in C++. CRC Press LLC, 1993
• 26: Sthamer. H, Wegener. J, Baresel. A. Using evolutionary testing to improve efficiency and quality in software testing. In Procedings of the 2nd Asia-Pacific Conference on Software Testing Analysis and Review (AsiaSTAR), (July 2002, 22--24th).
• 27: Eugenia Díaz , Javier Tuya , Raquel Blanco , José Javier Dolado, A tabu search algorithm for structural software testing, Computers and Operations Research, v.35 n.10, p.3052-3072, October, 2008 [doi>10.1016/j.cor.2007.01.009]
• 28: Kiran Lakhotia , Mark Harman , Phil McMinn, A multi-objective approach to search-based test data generation, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277175]
• 29: Abdelhamid Bouchachia, An Immune Genetic Algorithm for Software Test Data Generation, Proceedings of the 7th International Conference on Hybrid Intelligent Systems, p.84-89, September 17-19, 2007
• 30: Enrique Alba , Francisco Chicano, Observations in using parallel and sequential evolutionary algorithms for automatic software testing, Computers and Operations Research, v.35 n.10, p.3161-3183, October, 2008 [doi>10.1016/j.cor.2007.01.016]
• 31: André Baresel , Harmen Sthamer , Michael Schmidt, Fitness Function Design To Improve Evolutionary Structural Testing, Proceedings of the Genetic and Evolutionary Computation Conference, p.1329-1336, July 09-13, 2002

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Testing tools (e.g., data generators, coverage testing)

General Terms:
Algorithms, Experimentation, Measurement, Performance

Keywords:
automation test, genetic algorithms, path testing, software testing, structure-oriented