Strongly-typed genetic programming and purity analysis: input domain reduction for evolutionary testing problems

ABSTRACT

Search-based test case generation for object-oriented software is hindered by the size of the search space, which encompasses the arguments to the implicit and explicit parameters of the test object's public methods. The performance of this type of search problems can be enhanced by the definition of adequate Input Domain Reduction strategies.

The focus of our on-going work is on employing evolutionary algorithms for generating test data for the structural unit-testing of Java programs. Test cases are represented and evolved using the Strongly-Typed Genetic Programming paradigm; Purity Analysis is particularly useful in this situation because it provides a means to automatically identify and remove Function Set entries that do not contribute to the definition of interesting test scenarios.

REFERENCES

• 1: 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]
• 2: David J. Montana, Strongly typed genetic programming, Evolutionary Computation, v.3 n.2, p.199-230, Summer 1995 [doi>10.1162/evco.1995.3.2.199]
• 3: J. C. B. Ribeiro, M. Zenha-Rela, and F. F. de Vega. ecrash: a framework for performing evolutionary testing on third-party java components. In JAEM'07: Proceedings of the I Jornadas sobre Algoritmos Evolutivos y Metaheuristicas at the II Congreso Español de Informática, pages 137--144, 2007.
• 4: A. Salcianu and M. C. Rinard. Purity and side effect analysis for java programs. In VMCAI'05: Proceedings of the 6th International Conference on Verification, Model Checking, and Abstract Interpretation, volume 3385 of Lecture Notes in Computer Science, pages 199--215. Springer, 2005.
• 5: Raja Vallée-Rai , Phong Co , Etienne Gagnon , Laurie Hendren , Patrick Lam , Vijay Sundaresan, Soot - a Java bytecode optimization framework, Proceedings of the 1999 conference of the Centre for Advanced Studies on Collaborative research, p.13, November 08-11, 1999, Mississauga, Ontario, Canada
• 6: Stefan Wappler , Joachim Wegener, Evolutionary unit testing of object-oriented software using strongly-typed genetic programming, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144317]

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

Keywords:
input domain reduction, search-based test case generation, strongly-typed genetic programming