Search-based test case generation for object-oriented java software using strongly-typed genetic programming

ABSTRACT

In evolutionary testing, meta-heuristic search techniques are used to generate high-quality test data. The focus of our on-going work is on employing evolutionary algorithms for the structural unit-testing of object-oriented Java programs.

Test cases are evolved using the Strongly-Typed Genetic Programming technique. Test data quality evaluation includes instrumenting the test object, executing it with the generated test cases, and tracing the structures traversed in order to derive coverage metrics. The strategy for efficiently guiding the search process towards achieving full structural coverage involves favouring test cases that exercise problematic structures and control-flow paths. Static analysis and instrumentation is performed solely with basis on the information extracted from the test objects' Java Bytecode.

Relevant contributions include the introduction of novel methodologies for automation, search guidance and input domain reduction, and the presentation of the eCrash automated test case generation tool.

REFERENCES

• 1: Boris Beizer, Software Testing Techniques, John Wiley & Sons, Inc., New York, NY, 1990
• 2: Bruce Eckel, Thinking in Java, Prentice Hall Professional Technical Reference, 2002
• 3: Alex Kinneer , Matthew B. Dwyer , Gregg Rothermel, Sofya: Supporting Rapid Development of Dynamic Program Analyses for Java, Companion to the proceedings of the 29th International Conference on Software Engineering, p.51-52, May 20-26, 2007 [doi>10.1109/ICSECOMPANION.2007.68]
• 4: S. Luke. ECJ 16: A Java Evolutionary Computation Library. http://cs.gmu.edu/~eclab/projects/ecj/, 2007.
• 5: 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]
• 6: J. C. B. Ribeiro, F. F. de Vega, and M. Z. Rela. Using Dynamic Analysis of Java Bytecode for Evolutionary Object-Oriented Unit Testing. In SBRC WTF 2007: Proceedings of the 8th Workshop on Testing and Fault Tolerance at the 25th Brazilian Symposium on Computer Networks and Distributed Systems, pages 143--156. Brazilian Computer Society (SBC), 2007.
• 7: 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.
• 8: J. C. B. Ribeiro, M. Zenha-Rela, and F. F. de Vega. An Evolutionary Approach for Performing Structural Unit-Testing on Third-Party Object-Oriented Java Software. In NICSO 2007: Proceedings of the 2nd International Workshop on Nature Inspired Cooperative Strategies for Optimization (to appear), Studies in Computational Intelligence. Springer-Verlag, 11 2007.
• 9: José Carlos Bregieiro Ribeiro , Mário Zenha Rela , Francisco Fernandéz de Vega, A strategy for evaluating feasible and unfeasible test cases for the evolutionary testing of object-oriented software, Proceedings of the 3rd international workshop on Automation of software test, May 11-11, 2008, Leipzig, Germany [doi>10.1145/1370042.1370061]
• 10: José Carlos Bregieiro Ribeiro , Mário Alberto Zenha-Rela , Francisco Fernandéz de Vega, Strongly-typed genetic programming and purity analysis: input domain reduction for evolutionary testing problems, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389439]
• 11: 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.
• 12: 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
• 13: S. Wappler and J. Wegener. Evolutionary Unit Testing Of Object-Oriented Software Using A Hybrid Evolutionary Algorithm. In CEC'06: Proceedings of the 2006 IEEE Congress on Evolutionary Computation, pages 851--858. IEEE, 2006.
• 14: 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:
evolutionary testing, object-orientation, search-based test case generation, strongly-typed genetic programming