Generating test data for both path coverage and fault detection using genetic algorithms

Abstract

The aim of software testing is to find faults in a program under test, so generating test data that can expose the faults of a program is very important. To date, current studies on generating test data for path coverage do not perform well in detecting low probability faults on the covered path. The automatic generation of test data for both path coverage and fault detection using genetic algorithms is the focus of this study. To this end, the problem is first formulated as a bi-objective optimization problem with one constraint whose objectives are the number of faults detected in the traversed path and the risk level of these faults, and whose constraint is that the traversed path must be the target path. An evolutionary algorithm is employed to solve the formulated model, and several types of fault detection methods are given. Finally, the proposed method is applied to several real-world programs, and compared with a random method and evolutionary optimization method in the following three aspects: the number of generations and the time consumption needed to generate desired test data, and the success rate of detecting faults. The experimental results confirm that the proposed method can effectively generate test data that not only traverse the target path but also detect faults lying in it.

Keywords

software testing / path coverage / fault detection / test data / multi-objective optimization / genetic algorithms

References

[1] Myers G. The art of software testing. New York: Wiley, 1979

[2] Beizer B. Software testing techniques. New York: Van Nostrand Rheinhold, 1990

[3] Tassey G. The economic impacts of inadequate infrastructure for software testing. Gaithersburg: National Institute of Standards and Technology, 2002

[4] Gross H, Kruse P M, Wegener J. Evolutionary white-box software test with the evotest framework, a progress report. In: Proceedings of IEEE International Conference on Software Testing Verification and Validation Workshops, ICST ’09. 2009, 111-120

[5] Korel B. Automated software test data generation. IEEE Transactions on Software Engineering, 1990, 16(8): 870-879

[6] Sofokleous A A, Andreou A S. Automatic, evolutionary test data generation for dynamic software testing. The Journal of Systems and Software, 2008, 81(11): 1883-1898

[7] Gong D W, Zhang Y. Novel evolutionary generation approach of test data for multiple paths. Acta Electronica Sinica, 2010, 38(6): 1299-1304

[8] Gong D W, Zhang W Q, Yao X J. Evolutionary generation of test data for many paths coverage based on grouping. The Journal of Systems and Software, 2011, 84(12): 2222-2233

[9] Gong D W, Tian T, Yao X J. Grouping target paths for evolutionary generation of test data in parallel. The Journal of Systems and Software, 2012, 85(11): 2531-2540

[10] Zhang Y, Gong D W. Evolutionary genetation of test data for path coverage based on automatic reduction of searchspace. Acta Electronica Sinica, 2012, 40(5): 1011-1016

[11] Caserta M, Uribe A M. Tabu search-based metaheuristic algorithm for software system reliability problems. Computers & Operations Research, 2009, 36(3): 811-822

[12] Windisch A, Wappler S, Wegener J. Applying particle swarm optimization to software testing. In: Proceedings of Genetic and Evolutionary Computation Conference, GECCO ’07. 2007, 1121-1128

[13] Sagarna R, Yao X. Handling constraints for search based software test data generation. In: Proceedings of IEEE International Conference on Software Testing Verification and Validation Workshop, ICST ’08. 2008, 232-240

[14] Ghiduk A S, Harrold M J. Using genetic algorithms to aid test data generation for data flow coverage. In: Proceedings of the 14th Asia-Pacific Software Engineering Conference, APSEC ’07. 2007, 41-48

[15] Harman M, Lakhotia K, McMinn P. A multi-objective approach to search-based test data generation. In: Proceedings of Genetic and Evolutionary Computation Conference, GECCO ’07. 2007, 1098-1105

[16] Gong D W, Zhang Y. Generating test data for both paths coverage and faults detection using genetic algorithms. In: Proceedings of International Conference on Intelligent Computing, ICIC ’11. 2011, 664-671

[17] Shan J H, Wang J, Qi Z C. Survey on path-wise automatic generation of test data. Acta Electronica Sinica, 2004, 32(1): 109-113

[18] Chen T Y, Kuo F C, Merkel R G. Adaptive random testing: the art of test case diversity. The Journal of Systems and Software, 2010, 83(1): 60-66

[19] Ding Z, Zhang K, Hua J. A rigorous approach towards test case generation. Information Sciences, 2008, 178(21): 4057-4079

[20] Holland J H. Adaptation in natural and artificial systems. Michigan: The University of Michigan, 1975

[21] Xanthakis S, Ellis C, Skourlas C. Application of genetic algorithms to software testing. In: Proceedings of the 5th International Conference on Software Engineering, ICSE ’92. 1992, 625-636

[22] McMinn P. Search-based software test data generation: a survey. Software Testing, Verification and Reliability, 2004, 14(2): 105-156

[23] Pachauri A, Srivastava G. Automated test data generation for branch testing using genetic algorithm: an improved approach using branch ordering, memory and elitism. The Journal of Systems and Software, 2013, 86(5): 1191-1208

[24] Xiao M, Mohamed E A, Reformat M. Empirical evaluation of optimization algorithms when used in goal-oriented automated test data generation techniques. Empirical Software Engineering, 2007, 12(2): 183-239

[25] Arcuri A, Yao X. Search based software testing of object-oriented containers. Information Sciences, 2008, 178(15): 3075-3095

[26] Buhler O, Wegener J. Evolutionary functional testing. Computers & Operations Research, 2008, 35(10): 3144-3160

[27] Yoo S, Harman M. Areto efflcient multi-objective test case selection. In: Proceedings of International Symposium on Software Testing and Analysis, ISSTA ’07. 2007, 140-150

[28] Yang Z H, Gong Y Z, Xiao Q, Wang Y W. A defect model based testing system. Journal of Beijing University of Posts and Telecommunications, 2008, 31(5): 1-4

[29] Ahmed M A, Hermadi I. GA-based multiple paths test data generator. Computer & Operations Research, 2008, 35(10): 3107-3124

[30] Gong Y Z, Zhao R L, Zhang W, Zhao H Q. Software testing. Beijing: China Machine Press, 2008

[31] Deb K. Multi-objective optimization using evolutionary algorithms. American: John Wiley & Sons Inc., 2009

[32] Xuan G N, Cheng R W. Genetic algorithms and engineering optimization. Beijing: Tsinghua University Press, 2004

[33] Jia Y, Harman M. An analysis and survey of the development of mutation testing. IEEE Transactions on Software Engineering, 2011, 37(5): 649-678

[34] Hyunsook D, Sebastian E, Gregg R. Supporting controlled experimentation with testing techniques: an infrastructure and its potential impact. Empirical Software Engineering: An International Journal, 2005, 10(4): 405-435

[35] Zhong H, Zhang L, Mei H. An experimental study of four typical test suite reduction techniques. Information and Software Technology, 2008, 50(6): 534-546

[36] Hutchins M, Foster H, Goradia T. Experiments of the effectiveness of data flow and control flow-based test adequacy criteria. In: Proceedings of 16th International Conference on Software Engineering, ICSE ’94. 1994, 191-200

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg