The impact of input domain reduction on search-based test data generation

ABSTRACT

There has recently been a great deal of interest in search-based test data generation, with many local and global search algorithms being proposed. However, to date, there has been no investigation ofthe relationship between the size of the input domain (the search space) and performance of search-based algorithms. Static analysis can be used to remove irrelevant variables for a given test data generation problem, thereby reducing the search space size. This paper studies the effect of this domain reduction, presenting results from the application of local and global search algorithms to real world examples. This provides evidence to support the claimthat domain reduction has implications for practical search-based test data generation.

REFERENCES

• 1: James E. Baker, Reducing bias and inefficiency in the selection algorithm, Proceedings of the Second International Conference on Genetic Algorithms on Genetic algorithms and their application, p.14-21, October 1987, Cambridge, Massachusetts, United States
• 2: Boris Beizer, Software testing techniques (2nd ed.), Van Nostrand Reinhold Co., New York, NY, 1990
• 3: David Binkley , Mark Harman, Analysis and Visualization of Predicate Dependence on Formal Parameters and Global Variables, IEEE Transactions on Software Engineering, v.30 n.11, p.715-735, November 2004 [doi>10.1109/TSE.2004.78]
• 4: Lionel C. Briand , Jie Feng , Yvan Labiche, Using genetic algorithms and coupling measures to devise optimal integration test orders, Proceedings of the 14th international conference on Software engineering and knowledge engineering, July 15-19, 2002, Ischia, Italy [doi>10.1145/568760.568769]
• 5: Lionel C. Briand , Yvan Labiche , Marwa Shousha, Stress testing real-time systems with genetic algorithms, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068183]
• 6: S. Chen and S. Smith. Improving genetic algorithms by search space reductions. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 1999), pages 135--140. Morgan Kaufmann, 1999.
• 7: Patrick Cousot , Radhia Cousot, Systematic design of program transformation frameworks by abstract interpretation, ACM SIGPLAN Notices, v.37 n.1, p.178-190, Jan. 2002
• 8: J. W. Duran and S. C. Ntafos. An evaluation of random testing. IEEE Transactions on Software Engineering, 10(4):438--444, 1980.
• 9: Mark Harman , Chris Fox , Rob Hierons , Lin Hu , Sebastian Danicic , Joachim Wegener, VADA: A Transformation-Based System for Variable Dependence Analysis, Proceedings of the Second IEEE International Workshop on Source Code Analysis and Manipulation (SCAM'02), p.55, October 01-01, 2002
• 10: Mark Harman , Phil McMinn, A theoretical & empirical znalysis of evolutionary testing and hill climbing for structural test data generation, Proceedings of the 2007 international symposium on Software testing and analysis, July 09-12, 2007, London, United Kingdom [doi>10.1145/1273463.1273475]
• 11: James C. King, Symbolic execution and program testing, Communications of the ACM, v.19 n.7, p.385-394, July 1976 [doi>10.1145/360248.360252]
• 12: B. Korel, Automated Software Test Data Generation, IEEE Transactions on Software Engineering, v.16 n.8, p.870-879, August 1990 [doi>10.1109/32.57624 ]
• 13: Nashat Mansour , Miran Salame, Data Generation for Path Testing, Software Quality Control, v.12 n.2, p.121-136, June 2004 [doi>10.1023/B:SQJO.0000024059.72478.4e]
• 14: C. C. Michael , G. McGraw , M. A. Schatz, Generating Software Test Data by Evolution, IEEE Transactions on Software Engineering, v.27 n.12, p.1085-1110, December 2001 [doi>10.1109/32.988709 ]
• 15: 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]
• 16: P. McMinn. IGUANA: Input generation using automated novel algorithms. A plug and play research tool. Technical Report, Department of Computer Science, University of Sheffield, 2007.
• 17: Phil McMinn , Mark Harman , David Binkley , Paolo Tonella, The species per path approach to SearchBased test data generation, Proceedings of the 2006 international symposium on Software testing and analysis, July 17-20, 2006, Portland, Maine, USA [doi>10.1145/1146238.1146241]
• 18: W. Miller , D. L. Spooner, Automatic Generation of Floating-Point Test Data, IEEE Transactions on Software Engineering, v.2 n.3, p.223-226, May 1976 [doi>10.1109/TSE.1976.233818]
• 19: Heinz Mühlenbein , Dirk Schlierkamp-Voosen, Predictive models for the breeder genetic algorithm, I.: continuous parameter optimization, Evolutionary Computation, v.1 n.1, p.25-49, Spring 1993
• 20: R. Pargas, M. Harrold, and R. Peck. Test-data generation using genetic algorithms. Software Testing, Verification and Reliability, 9(4):263--282, 1999.
• 21: F. Schmiedle, R. Drechsler, and B. Becker. Exact routing with search space reduction. IEEE Transactions on Computers, 52(6):815--825, 2003.
• 22: Alan C. Schultz , John J. Grefenstette , Kenneth A. De Jong, Test and Evaluation by Genetic Algorithms, IEEE Expert: Intelligent Systems and Their Applications, v.8 n.5, p.9-14, October 1993 [doi>10.1109/64.236476 ]
• 23: 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 ]
• 24: J. Wegener, A. Baresel, and H. Sthamer. Evolutionary test environment for automatic structural testing. Information and Software Technology, 43(14):841--854, 2001.
• 25: J. Wegener and O. Bühler. Evaluation of different fitness functions for the evolutionary testing of an autonomous parking system. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2004), Lecture Notes in Computer Science vol. 3103, pages 1021--1028, Springer-Verlag, 2004.
• 26: M. Weiser. Program slicing. IEEE Transactions on Software Engineering, 10(4):352--357, 1984.
• 27: Darrell Whitley, The GENITOR algorithm and selection pressure: why rank-based allocation of reproductive trials is best, Proceedings of the third international conference on Genetic algorithms, p.116-121, December 1989, George Mason University, United States
• 28: S. Xanthakis, C. Ellis, C. Skourlas, A. Le Gall, S. Katsikas, and K. Karapoulios. Application of genetic algorithms to software testing (Application des algorithmes génétiques au test des logiciels). In 5th International Conference on Software Engineering and its Applications, pages 625--636, Toulouse, France, 1992.

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)

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Experimentation, Measurement, Performance, Theory

Keywords:
automated test data generation, evolutionary testing, genetic algorithms, hill climbing, input domain reduction, search space reduction