Automatic mutation test input data generation via ant colony

ABSTRACT

Fault-based testing is often advocated to overcome limitations ofother testing approaches; however it is also recognized as beingexpensive. On the other hand, evolutionary algorithms have beenproved suitable for reducing the cost of data generation in the contextof coverage based testing. In this paper, we propose a newevolutionary approach based on ant colony optimization for automatictest input data generation in the context of mutation testingto reduce the cost of such a test strategy. In our approach the antcolony optimization algorithm is enhanced by a probability densityestimation technique. We compare our proposal with otherevolutionary algorithms, e.g., Genetic Algorithm. Our preliminaryresults on JAVA testbeds show that our approach performed significantlybetter than other alternatives.

REFERENCES

• 1: K. Adamopoulos, M. Harman, and R. M. Hierons. How to overcome the equivalent mutant problem and achieve tailored selective mutation using co--evolution. In Genetic and Evolutionary Computation Conference, pages 1338--1349, 2004.
• 2: Christian Blum , Krzysztof Socha, Training feed-forward neural networks with ant colony optimization: An application to pattern classification, Proceedings of the Fifth International Conference on Hybrid Intelligent Systems, p.233-238, December 06-09, 2005 [doi>10.1109/ICHIS.2005.104]
• 3: L. Bottaci. A genetic algorithm fitness function for mutation testing. In proceedings of SEMINAL: Software Engineering using Metaheuristic INovative Algortithms, Workshop 8, ICSE 2001, 23rd International Conference on Software Engineering, pages 3--7, 2001.
• 4: G. Box and M. Muller. A note on the generation of random normal deviates. Annals. Math. Stat., 29:610--611, 1958.
• 5: Timothy Alan Budd, Mutation analysis of program test data, Yale University, New Haven, CT, 1980
• 6: R. A. DeMillo, R. J. Lipton, and F. G. Sayward. Hints on test data selection: help for the practicing programmer. IEEE Computer, 11(4):34--41, 1978.
• 7: Phyllis G. Frankl , Stewart N. Weiss , Cang Hu, All-uses vs mutation testing: an experimental comparison of effectiveness, Journal of Systems and Software, v.38 n.3, p.235-253, Sept. 1997 [doi>10.1016/S0164-1212(96)00154-9]
• 8: W. E. Howden. Weak mutation testing and completeness of test sets. IEEE Transactions on Software Engineering, 8(4):371--379, July 1982.
• 9: B. Jones, H. Sthamer, and D. Eyres. Automatic structural testing using genetic algorithms. Software Engineering Journal, 11(5):299--306, 1996.
• 10: B. Jones, H. Sthamer, X. Yang, and D. E. T. The automatic generation of software test data sets using adaptive search techniques. In Proceedings of the 3rd International Conference on So Quality Management, Seville, Spain, pages 435--444, 1995.
• 11: B. Korel. Dynamic method of software test data generation. Softw. Test, Verif. Reliab, 2(4):203--213, 1992.
• 12: Huaizhong LI , C. Peng LAM, An Ant Colony Optimization Approach to Test Sequence Generation for Statebased Software Testin, Proceedings of the Fifth International Conference on Quality Software, p.255-264, September 19-20, 2005 [doi>10.1109/QSIC.2005.12]
• 13: P. May, K. Mander, and J. Timmis. Software vaccination: An artificial immune system approach to mutation testing. In Artificial Immune Systems, Second International Conference, ICARIS 2003, Edinburgh, UK, September 1--3, 2003, Proceedings, volume 2787, pages 81--92, 2003.
• 14: 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]
• 15: P. McMinn and M. Holcombe. The state problem for evolutionary testing. In Genetic and Evolutionary Computation -- GECCO--2003, pages 2488--2498, Berlin, 2003. Springer--Verlag.
• 16: W. Miller and D. L. Spooner. Automatic generation of floating--point test data. IEEE Transactions on Software Engineering, 2(3):223--226, Sept. 1976.
• 17: E. S. Mresa and L. Bottaci. Efficiency of mutation operators and selective mutation strategies: An empirical study. Softw. Test, Verif. Reliab, 9(4):205--232, 1999.
• 18: Andrew Jefferson Offutt, VI , R. A. Demillo, Automatic test data generation, Georgia Institute of Technology, Atlanta, GA, 1988
• 19: A. Jefferson Offutt , Zhenyi Jin , Jie Pan, The dynamic domain reduction procedure for test data generation, Software—Practice & Experience, v.29 n.2, p.167-193, Feb. 1999 [doi>10.1002/(SICI)1097-024X(199902)29:2<167::AID-SPE225>3.3.CO;2-M]
• 20: Jeff Offutt , Yu-Seung Ma , Yong-Rae Kwon, An experimental mutation system for Java, ACM SIGSOFT Software Engineering Notes, v.29 n.5, September 2004 [doi>10.1145/1022494.1022537]
• 21: A. Jefferson Offutt , Jie Pan , Kanupriya Tewary , Tong Zhang, An experimental evaluation of data flow and mutation testing, Software—Practice & Experience, v.26 n.2, p.165-176, Feb. 1996 [doi>10.1002/(SICI)1097-024X(199602)26:2<165::AID-SPE5>3.0.CO;2-K]
• 22: J. Offutt and R. H. Untch. Mutation 2000: Uniting the orthogonal. In Mutation 2000: Mutation Testing in the Twentieth and the Twenty First Centuries, San Jose, CA, pages 45--55, 2000.
• 23: Roger S. Pressman, Software engineering (3rd ed.): a practitioner's approach, McGraw-Hill, Inc., New York, NY, 1992
• 24: D. Thierens and P. A. N. Bosman. Multi-Objective Mixture-based Iterated Density Estimation Evolutionary Algorithms. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 663--670, 2001.
• 25: Paolo Tonella, Evolutionary testing of classes, Proceedings of the 2004 ACM SIGSOFT international symposium on Software testing and analysis, July 11-14, 2004, Boston, Massachusetts, USA
• 26: Nigel Tracey , John Clark , Keith Mander, Automated program flaw finding using simulated annealing, Proceedings of the 1998 ACM SIGSOFT international symposium on Software testing and analysis, p.73-81, March 02-04, 1998, Clearwater Beach, Florida, United States
• 27: 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]
• 28: Z. Tu and Y. Lu. Global optimization of continuous problems using stochastic genetic algorithm. In Proceedings of the 2003 Congress on Evolutionary Computation CEC2003, pages 1230--1236, 2003.
• 29: Roland H. Untch , A. Jefferson Offutt , Mary Jean Harrold, Mutation analysis using mutant schemata, Proceedings of the 1993 ACM SIGSOFT international symposium on Software testing and analysis, p.139-148, June 28-30, 1993, Cambridge, Massachusetts, United States
• 30: P. J. Walsh. A measure of test completeness. PhD thesis, State University of New York at Binghamton, 1985.
• 31: A. Watkins. The automatic generation of test data using genetic algorithms. In Proceedings of the Fourth Software Quality Conference, pages 300--309. ACM, 1995.
• 32: J. Wegener, A. Baresel, and H. Sthamer. Evolutionary test environment for automatic structural testing. Information & Software Technology, 43(14):841--854, 2001.
• 33: S. Xanthakis, C. Ellis, C. Skourlas, A. L. Gall, S. Katsikas, and K. Karapoulios. Application des algorithmes genetiques au test des logiciels. In 5th Int. Conference on Software Engineering and its Applications, pages 625--636, 1992.
• 34: Yuan Zhan , John A. Clark, Search-based mutation testing for Simulink models, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068188]

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

Keywords:
ant colony optimization, mutation testing, search based testing, test input data generation