Generating test data for both path coverage and fault detection using genetic algorithms
Dunwei GONG1, Yan ZHANG1,2()
1. School of Information and Electrical Engineering, China University of Mining and Technology, Xuzhou, 221116, China; 2. School of Technology,Mudanjiang Normal University, Mudanjiang, 157012, China
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.
Dunwei GONG,Yan ZHANG. Generating test data for both path coverage and fault detection using genetic algorithms[J]. Front Comput Sci,
2013, 7(6): 822-837.
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 doi: 10.1109/32.57624
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 doi: 10.1016/j.jss.2007.12.809
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 doi: 10.1016/j.jss.2011.06.028
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 doi: 10.1016/j.jss.2012.05.071
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 doi: 10.1016/j.cor.2007.10.028
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 doi: 10.1016/j.jss.2009.02.022
19
Ding Z, Zhang K, Hua J. A rigorous approach towards test case generation. Information Sciences , 2008, 178(21): 4057-4079 doi: 10.1016/j.ins.2008.06.020
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 doi: 10.1002/stvr.294
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 doi: 10.1016/j.jss.2012.11.045
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 doi: 10.1007/s10664-006-9026-0
25
Arcuri A, Yao X. Search based software testing of object-oriented containers. Information Sciences , 2008, 178(15): 3075-3095 doi: 10.1016/j.ins.2007.11.024
26
Buhler O, Wegener J. Evolutionary functional testing. Computers & Operations Research , 2008, 35(10): 3144-3160 doi: 10.1016/j.cor.2007.01.015
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 doi: 10.1016/j.cor.2007.01.012
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 doi: 10.1109/TSE.2010.62
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 doi: 10.1007/s10664-005-3861-2
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 doi: 10.1016/j.infsof.2007.06.003
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
