Empirical evaluation of a nesting testability transformation for evolutionary testing

ABSTRACT

Evolutionary testing is an approach to automating test data generation that uses an evolutionary algorithm to search a test object's input domain for test data. Nested predicates can cause problems for evolutionary testing, because information needed for guiding the search only becomes available as each nested conditional is satisfied. This means that the search process can overfit to early information, making it harder, and sometimes near impossible, to satisfy constraints that only become apparent later in the search. The article presents a testability transformation that allows the evaluation of all nested conditionals at once. Two empirical studies are presented. The first study shows that the form of nesting handled is prevalent in practice. The second study shows how the approach improves evolutionary test data generation.

REFERENCES

• 1: Baresel, A. 2000. Automatisierung von strukturtests mit evolutionren algorithmen. Diploma Thesis, Humboldt University, Berlin, Germany.
• 2: André Baresel , David Binkley , Mark Harman , Bogdan Korel, Evolutionary testing in the presence of loop-assigned flags: a testability transformation approach, Proceedings of the 2004 ACM SIGSOFT international symposium on Software testing and analysis, July 11-14, 2004, Boston, Massachusetts, USA
• 3: Baresel, A. and Sthamer, H. 2003. Evolutionary testing of flag conditions. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'03). Lecture Notes in Computer Science vol. 2724. Springer-Verlag, 2442--2454.
• 4: André Baresel , Harmen Sthamer , Michael Schmidt, Fitness Function Design To Improve Evolutionary Structural Testing, Proceedings of the Genetic and Evolutionary Computation Conference, p.1329-1336, July 09-13, 2002
• 5: Robert S. Boyer , Bernard Elspas , Karl N. Levitt, SELECT—a formal system for testing and debugging programs by symbolic execution, Proceedings of the international conference on Reliable software, p.234-245, April 21-23, 1975, Los Angeles, California
• 6: L. A. Clarke, A System to Generate Test Data and Symbolically Execute Programs, IEEE Transactions on Software Engineering, v.2 n.3, p.215-222, May 1976 [doi>10.1109/TSE.1976.233817]
• 7: Richard A. DeMillo , A. Jefferson Offutt, Constraint-Based Automatic Test Data Generation, IEEE Transactions on Software Engineering, v.17 n.9, p.900-910, September 1991 [doi>10.1109/32.92910]
• 8: Hyunsook Do , Sebastian Elbaum , Gregg Rothermel, Supporting Controlled Experimentation with Testing Techniques: An Infrastructure and its Potential Impact, Empirical Software Engineering, v.10 n.4, p.405-435, October 2005 [doi>10.1007/s10664-005-3861-2]
• 9: Roger Ferguson , Bogdan Korel, The chaining approach for software test data generation, ACM Transactions on Software Engineering and Methodology (TOSEM), v.5 n.1, p.63-86, Jan. 1996 [doi>10.1145/226155.226158]
• 10: Mark Harman , Youssef Hassoun , Kiran Lakhotia , Phil McMinn , Joachim Wegener, The impact of input domain reduction on search-based test data generation, Proceedings of the the 6th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering, September 03-07, 2007, Dubrovnik, Croatia [doi>10.1145/1287624.1287647]
• 11: Mark Harman , Lin Hu , Robert M. Hierons , André Baresel , Harmen Sthamer, Improving Evolutionary Testing By Flag Removal, Proceedings of the Genetic and Evolutionary Computation Conference, p.1359-1366, July 09-13, 2002
• 12: Mark Harman , Lin Hu , Rob Hierons , Joachim Wegener , Harmen Sthamer , André Baresel , Marc Roper, Testability Transformation, IEEE Transactions on Software Engineering, v.30 n.1, p.3-16, January 2004 [doi>10.1109/TSE.2004.1265732]
• 13: Harman, M. and McMinn, P. 2009. A theoretical and empirical study of search-based testing: Local, global, and hybrid search. IEEE Trans. Softw. Engin. To appear.
• 14: R. M. Hierons , M. Harman , C. J. Fox, Branch-Coverage Testability Transformation for Unstructured Programs, The Computer Journal, v.48 n.4, p.421-436, July 2005 [doi>10.1093/comjnl/bxh093]
• 15: Jones, B., Sthamer, H., and Eyres, D. 1996. Automatic structural testing using genetic algorithms. Softw. Engin. J. 11, 5, 299--306.
• 16: Jones, B., Sthamer, H., Yang, X., and Eyres, D. 1995. The automatic generation of software test data sets using adaptive search techniques. In Proceedings of the 3rd International Conference on Software Quality Management, 435--444.
• 17: 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]
• 18: 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]
• 19: Korel, B. 1992. Dynamic method for software test data generation. Softw. Test. Verif. Reliabil. 2, 4, 203--213.
• 20: Bogdan Korel , Ali M. Al-Yami, Assertion-oriented automated test data generation, Proceedings of the 18th international conference on Software engineering, p.71-80, March 25-29, 1996, Berlin, Germany
• 21: Bogdan Korel , Mark Harman , S. Chung , P. Apirukvorapinit , R. Gupta , Q. Zhang, Data Dependence Based Testability Transformation in Automated Test Generation, Proceedings of the 16th IEEE International Symposium on Software Reliability Engineering, p.245-254, November 08-11, 2005 [doi>10.1109/ISSRE.2005.16]
• 22: 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]
• 23: McMinn, P., Binkley, D., and Harman, M. 2005. Testability transformation for efficient automated test data search in the presence of nesting. In Proceedings of the UK Software Testing Workshop (UKTest'05). University of Sheffield Computer Science tech. rep. CS-05-07, 165--182.
• 24: P. McMinn , M. Holcombe, Evolutionary Testing Using an Extended Chaining Approach, Evolutionary Computation, v.14 n.1, p.41-64, March 2006 [doi>10.1162/106365606776022742]
• 25: 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]
• 26: 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 [doi>10.1162/evco.1993.1.1.25]
• 27: Pargas, R., Harrold, M., and Peck, R. 1999. Test-Data generation using genetic algorithms. Softw. Test. Verif. Reliabil. 9, 4, 263--282.
• 28: P. Puschner , R. Nossal, Testing the Results of Static Worst-Case Execution-Time Analysis, Proceedings of the IEEE Real-Time Systems Symposium, p.134, December 02-04, 1998
• 29: Tracey, N. 2000. A search-based automated test-data generation framework for safety critical software. Ph.D. thesis, University of York.
• 30: Nigel Tracey , John Clark , Keith Mander, Automated program flaw finding using simulated annealing, ACM SIGSOFT Software Engineering Notes, v.23 n.2, p.73-81, March 1998
• 31: Tracey, N., Clark, J., and Mander, K. 1998b. The way forward for unifying dynamic test-case generation: The optimisation-based approach. In Proceedings of the International Workshop on Dependable Computing and Its Applications. 169--180.
• 32: N. Tracey , J. Clark , K. Mander , J. McDermid, An Automated Framework for Structural Test-Data Generation, Proceedings of the 13th IEEE international conference on Automated software engineering, p.285, October 13-16, 1998
• 33: 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]
• 34: Wegener, J., Baresel, A., and Sthamer, H. 2001. Evolutionary test environment for automatic structural testing. Inform. Softw. Technol. 43, 14, 841--854.
• 35: Wegener, J., Grimm, K., Grochtmann, M., Sthamer, H., and Jones, B. 1996. Systematic testing of real-time systems. In Proceedings of the 4th European Conference on Software Testing, Analysis and Review (EuroSTAR'96).
• 36: Joachim Wegener , Matthias Grochtmann, Verifying Timing Constraints of Real-Time Systems by Meansof Evolutionary Testing, Real-Time Systems, v.15 n.3, p.275-298, Nov. 1998 [doi>10.1023/A:1008096431840]
• 37: Whitley, D. 2001. An overview of evolutionary algorithms: Practical issues and common pitfalls. Inform. Softw. Technol. 43, 14, 817--831.
• 38: Xanthakis, S., Ellis, C., Skourlas, C., Le Gall, A., Katsikas, S., and Karapoulios, K. 1992. Application of genetic algorithms to software testing (Application des algorithmes génétiques au test des logiciels). In Proceedings of the 5th International Conference on Software Engineering and its Applications, 625--636.

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

Keywords:
Evolutionary testing, search-based software engineering, test data generation, testability transformation