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

doi:10.1007/s11704-013-3024-3

Front Comput Sci

2013, Vol. 7

Issue (6) : 822-837 https://doi.org/10.1007/s11704-013-3024-3

RESEARCH ARTICLE

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

Dunwei GONG¹, Yan ZHANG^1,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

Download: PDF(1044 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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

Corresponding Author(s): ZHANG Yan,Email:zhangyancumt@126.com

Issue Date: 01 December 2013

Cite this article:

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.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-013-3024-3
https://academic.hep.com.cn/fcs/EN/Y2013/V7/I6/822

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 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

[1]	Ilyes KHENNAK, Habiba DRIAS. Strength Pareto fitness assignment for pseudo-relevance feedback: application to MEDLINE[J]. Front. Comput. Sci., 2018, 12(1): 163-176.
[2]	Xiaofang QI,Jun HE,Peng WANG,Huayang ZHOU. Variable strength combinatorial testing of concurrent programs[J]. Front. Comput. Sci., 2016, 10(4): 631-643.
[3]	Priyanka CHAWLA,Inderveer CHANA,Ajay RANA. A novel strategy for automatic test data generation using soft computing technique[J]. Front. Comput. Sci., 2015, 9(3): 346-363.
[4]	Yan ZHANG,Dunwei GONG. Generating test data for both paths coverage and faults detection using genetic algorithms: multi-path case[J]. Front. Comput. Sci., 2014, 8(5): 726-740.
[5]	Chang-ai SUN,Zuoyi WANG,Guan WANG. A property-based testing framework for encryption programs[J]. Front. Comput. Sci., 2014, 8(3): 478-489.
[6]	Bo YUAN, Wenhuang LIU. Measure oriented training: a targeted approach to imbalanced classification problems[J]. Front Comput Sci, 2012, 6(5): 489-497.
[7]	Kenli LI, Zhao TONG, Dan LIU, Teklay TESFAZGHI, Xiangke LIAO. A PTS-PGATS based approach for data-intensive scheduling in data grids[J]. Front Comput Sci Chin, 2011, 5(4): 513-525.
[8]	Yaochu JIN, Robin GRUNA, Bernhard SENDHOFF. Pareto analysis evolutionary and learning systems[J]. Front Comput Sci Chin, 2009, 3(1): 4-17.
[9]	Carlos A. COELLO COELLO. Evolutionary multi-objective optimization:some current research trends and topics that remain to be explored[J]. Front Comput Sci Chin, 2009, 3(1): 18-30.

Viewed

Full text

Abstract

Cited

Shared

Discussed