Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

Front. Comput. Sci.    2014, Vol. 8 Issue (5) : 726-740    https://doi.org/10.1007/s11704-014-3372-7
RESEARCH ARTICLE
Generating test data for both paths coverage and faults detection using genetic algorithms: multi-path case
Yan ZHANG1,2,Dunwei GONG2,*()
1. School of Technology,Mudanjiang Normal University,Mudanjiang 157012, China
2. School of Information and Electrical Engineering, China University of Mining and Technology, Xuzhou 221116, China
 Download: PDF(814 KB)  
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
Abstract

Generating test data that can expose the faults of the program is an important issue in software testing. Although previous methods of covering path can generate test data to traverse target path, the test data generated by these methods are difficult in detecting some low-probabilistic faults that lie on the covered paths. We present a method of generating test data for covering multiple paths to detect faults in this study. First, we transform the problem of covering multiple paths and detecting faults into a multi-objective optimization problem with constraint, and construct a mathematical model for it. Then, we give a strategy of solving the model based on a weighted genetic algorithm. Finally, we apply our method to several real-world programs, and compare it with several methods. The experimental results confirm that the proposed method can more efficiently generate test data that not only traverse the target paths but also detect faults lying in them than other methods.

Keywords software testing      multiple paths coverage      faults detection      multi-objective optimization     
Corresponding Author(s): Dunwei GONG   
Issue Date: 11 October 2014
 Cite this article:   
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.
 URL:  
https://academic.hep.com.cn/fcs/EN/10.1007/s11704-014-3372-7
https://academic.hep.com.cn/fcs/EN/Y2014/V8/I5/726
1 Ahmed M A, Hermadi I. GA-based multiple paths test data generator. Computer & Operations Research, 2008, 35(10): 3107-3124
https://doi.org/10.1016/j.cor.2007.01.012
2 Alander J T, Mantere T, Turunen P. Genetic algorithm based software testing. In: Proceedings of the 3rd International Conference on Artificial Neural Networks and Genetic Algorithms. 1997, 325-328
3 Srivastava1 P R, Kim T. Application of genetic algorithm in software testing. International Journal of Software Engineering and Its Applications, 2009, 3(4): 87-95
4 Lin J C, Yeh P L. Automatic test data generation for path testing using GAs. Information Sciences, 2001, 131(1-4): 47-64
https://doi.org/10.1016/S0020-0255(00)00093-1
5 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
https://doi.org/10.1016/j.jss.2012.05.071
6 Miller J, Reformat M, Zhang H. Automatic test data generation using genetic algorithm and program dependence graphs. Information and Software Technology, 2006, 48(7): 586-605
https://doi.org/10.1016/j.infsof.2005.06.006
7 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
https://doi.org/10.1016/j.jss.2011.06.028
8 McMinn P, Harman M, Binkley D, Tonella P. The species per path approach to searchbased test data generation. In: Proceedings of International Symposium on Software Testing and Analysis. 2006, 13-24
9 Zhou Z Q, Huang D H, Tse T H, Yang Z Y, Huang H, Chen T Y. Metamorphic testing and its applications. In: Proceedings of the 8th International Symposium on Future Software Technology. 2004
10 Whittaker J A. What is software testing? and why is it so hard? IEEE Software, 2000, 17(1): 70-79
https://doi.org/10.1109/52.819971
11 Gong D W, Zhang Y. Generating test data for both path coverage and faults detection using genetic algorithms. Frontiers of Computer Science, 2013, 7(6): 822-837
https://doi.org/10.1007/s11704-013-3024-3
12 Mills H D, Dyer M D, Linger R C. Cleanroom software engineering. IEEE Software, 1987, 4(5): 19-25
https://doi.org/10.1109/MS.1987.231413
13 Voas J M, Morell L, Miller KW. Predicting where faults can hide from testing. IEEE Software, 1991, 8(2): 41-48
https://doi.org/10.1109/52.73748
14 Thévenod-Fosse P, Waeselynck H. Statemate: applied to statistical software testing. In: Proceedings of the 1993 ACM SIGSOFT International Symposium on Software Testing and Analysis. 1993, 99-109
15 King J C. Symbolic execution and program testing. Communications of the ACM, 1976, 19(7): 385-394
https://doi.org/10.1145/360248.360252
16 Botella B, Gotlieb A, Michel C. Symbolic execution of floating-point computations. Software Testing, Verification & Reliability, 2006, 16(2): 97-121
https://doi.org/10.1002/stvr.333
17 Zhang J. Symbolic execution of program paths involving pointer structure variables. In: Proceedings of the 4th Intemational Conference on Quality Software. 2004, 87-92
18 Khurshid S, P?s?reanu C S, Visser W. Generalized symbolic execution for model checking and testing. Lecture Notes in Computer Science, 2003, 2619: 553-568
https://doi.org/10.1007/3-540-36577-X_40
19 Korel B. Automated software test data generation. IEEE Transactions on Software Engineering, 1990, 16(8): 870-879
https://doi.org/10.1109/32.57624
20 Harman M, Mansouri A, Zhang Y. Search-based Software Engineering: A Comprehensive Analysis and Review of Trends Techniques and Applications. Technical Report TR-09-03: Department of Computer Science, King’s College London. 2009
21 Holland J H. Adaptation in Natural and Artificial Systems. Michigan: The University of Michigan, 1975
22 Xanthakis S, Ellis C, Skourlas C, Le Gall A, Katsikas S, Karapoulios K. Application of genetic algorithms to software testing. In: Proceedings of the 5th International Conference on Software Engineering. 1992, 625-636
23 McMinn P. Search-based software test data generation: a survey. Software Testing, Verification and Reliability, 2004, 14(2): 105-156
https://doi.org/10.1002/stvr.294
24 Michael C C, McGraw G E, Schatz M A. Opportunism and diversity in automated software test data generation. In: Proceedings of Automated Software Engineer. 1998, 136-146
25 Pargas R P, Harrold M J, Peck R. Test-data generation using genetic algorithms. Software Testing, Verification and Reliability, 1999, 9(1): 263-282
https://doi.org/10.1002/(SICI)1099-1689(199912)9:4<263::AID-STVR190>3.0.CO;2-Y
26 Wegener J, Baresel A, Sthamer H. Evolutionary test environment for automatic structural testing. Journal of Information and Software Technology, 2001, 43(14): 841-854
https://doi.org/10.1016/S0950-5849(01)00190-2
27 Michael C C, McGraw G, Schatz M A. Generating software test data by evolution. IEEE Transactions on Software Engineering, 2001, 27(12): 1085-1110
https://doi.org/10.1109/32.988709
28 Xiao M, Mohamed E A, Reformat M, Miller J. Empirical evaluation of optimization algorithms when used in goal-oriented automated test data generation techniques. Empirical Software Engineering, 2007, 12(2): 183-239
https://doi.org/10.1007/s10664-006-9026-0
29 Arcuri A, Yao X. Search based software testing of object-oriented containers. Information Sciences, 2008, 178(15): 3075-3095
https://doi.org/10.1016/j.ins.2007.11.024
30 Buhler O, Wegener J. Evolutionary functional testing. Computers & Operations Research, 2008, 35(10): 3144-3160
https://doi.org/10.1016/j.cor.2007.01.015
31 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. 2008, 232-240
32 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. 2007, 41-48
https://doi.org/10.1109/ASPEC.2007.73
33 Harman M, Lakhotia K, McMinn P. A multi-objective approach to search-based test data generation. In: Proceedings of Genetic and Evolutionary Computation Conference. 2007, 1098-1105
34 Yoo S, Harman M. Pareto efficient multi-objective test case selection. In: Proceedings of International Symposium on Software Testing and Analysis. 2007, 140-150
35 Morell L J. A theory of fault-based testing. IEEE Transactions on Software Engineering, 1990, 16(8): 844-857
https://doi.org/10.1109/32.57623
36 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
37 Romano D, Penta M D, Antoniol G. An approach for search based testing of null pointer exceptions. In: Proceedings of the International Conference on Software Testing, Verification and Validation. 2011, 160-169
38 Nanda M G, Sinha S. Accurate interprocedural nulldereference analysis for java. In: Proceedings of the 31st International Conference on Software Engineering. 2009, 133-143
39 Bhattacharya N, Sakti A, Antoniol G, Guéhéneuc Y G, Pesant G. Divide-by-zero exception raising via branch coverage. In: Proceedings of the 3rd International Conference on Search based Software Engineering, ICSSE’11. 2011, 204-218
40 Godefroid P, Levin M Y, Molnar D. Active property checking. In: Proceedings of the 8th ACM International Conference on Embedded software. 2008, 207-216
https://doi.org/10.1145/1450058.1450087
41 Cui Z Q, Z. W L, Li X D. Target-directed concolic testing. Chinese Journal of Computers, 2011, 34(6): 953-964
https://doi.org/10.3724/SP.J.1016.2011.00953
42 Fraser G, Zeller A. Mutation-driven generation of unit tests and oracles. In: Proceedings of the 19th international symposium on Software testing and analysis. 2010, 1689-1696
43 Jia Y, Harman M. An analysis and survey of the development of mutation testing. IEEE Transactions on Software Engineering, 2011, 37(5): 649-678
https://doi.org/10.1109/TSE.2010.62
44 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
https://doi.org/10.1016/j.infsof.2007.06.003
45 Hutchins M, Foster H, Goradia T, Ostrand T. Experiments of the effectiveness of data flow and control flow-based test adequacy criteria. In: Proceedings of the 16th International Conference on Software Engineering. 1994, 191-200
https://doi.org/10.1109/ICSE.1994.296778
46 Zhang Z Y, Jiang B, Chan W K, Tse T H, Wang X M. Fault localization through evaluation sequences. Journal of Systems and Software, 2010, 83(2): 174-187
https://doi.org/10.1016/j.jss.2009.09.041
47 Gotlieb A, Petit M. Path-oriented random testing. In: Proceedings of the 1st International Workshop on Random Testing. 2006, 28-35
https://doi.org/10.1145/1145735.1145740
48 Hyunsook D, Sebastian E, Gregg R. Supporting controlled experimentation with testing techniques: an infrastructure and its potential impact. Empirical Software Engineering, 2005, 10(4): 405-435
https://doi.org/10.1007/s10664-005-3861-2
[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] Chang-ai SUN,Zuoyi WANG,Guan WANG. A property-based testing framework for encryption programs[J]. Front. Comput. Sci., 2014, 8(3): 478-489.
[5] 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.
[6] Yaochu JIN, Robin GRUNA, Bernhard SENDHOFF. Pareto analysis evolutionary and learning systems[J]. Front Comput Sci Chin, 2009, 3(1): 4-17.
[7] 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