A strategy for evaluating feasible and unfeasible test cases for the evolutionary testing of object-oriented software

ABSTRACT

Evolutionary Testing is an emerging methodology for automatically producing high quality test data. The focus of our on-going work is precisely on generating test data for the structural unit-testing of object-oriented Java programs. The primary objective is that of efficiently guiding the search process towards the definition of a test set that achieves full structural coverage of the test object.

However, the state problem of object-oriented programs requires specifying carefully fine-tuned methodologies that promote the traversal of problematic structures and difficult control-flow paths - which often involves the generation of complex and intricate test cases, that define elaborate state scenarios.

This paper proposes a methodology for evaluating the quality of both feasible and unfeasible test cases - i.e., those that are effectively completed and terminate with a call to the method under test, and those that abort prematurely because a runtime exception is thrown during test case execution. With our approach, unfeasible test cases are considered at certain stages of the evolutionary search, promoting diversity and enhancing the possibility of achieving full coverage.

REFERENCES

• 1: A. Arcuri and X. Yao. A memetic algorithm for test data generation of object-oriented software. In D. Srinivasan and L. Wang, editors, 2007 IEEE Congress on Evolutionary Computation, pages -, Singapore, 25-28 Sept. 2007. IEEE Computational Intelligence Society, IEEE Press.
• 2: A. Arcuri and X. Yao. Search based testing of containers for object-oriented software. Technical Report CSR-07-3, University of Birmingham, School of Computer Science, Apr. 2007.
• 3: S. Barbey and A. Strohmeier. The problematics of testing object-oriented software. In M. Ross, C. A. Brebbia, G. Staples, and J. Stapleton, editors, SQM'94 Second Conference on Software Quality Management, Edinburgh, Scotland, UK, July 26-28 1994, volume 2, pages 411--426, 1994.
• 4: Y. Cheon, M. Kim, and A. Perumandla. A complete automation of unit testing for java programs. In H. R. Arabnia and H. Reza, editors, Software Engineering Research and Practice, pages 290--295. CSREA Press, 2005.
• 5: Mark Harman, The Current State and Future of Search Based Software Engineering, 2007 Future of Software Engineering, p.342-357, May 23-25, 2007 [doi>10.1109/FOSE.2007.29]
• 6: A. Kinneer, M. Dwyer, and G. Rothermel. Sofya: A exible framework for development of dynamic program analysis for java software. Technical Report TR-UNL-CSE-2006-0006, University of Nebraska, Lincoln, 4 2006.
• 7: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 8: X. Liu, B. Wang, and H. Liu. Evolutionary search in the context of object-oriented programs. In MIC'05: Proceedings of the Sixth Metaheuristics International Conference, 2005.
• 9: S. Luke. ECJ 16: A Java evolutionary computation library. http://cs.gmu.edu/~eclab/projects/ecj/, 2007.
• 10: T. Mantere and J. T. Alander. Evolutionary software engineering, a review. Appl. Soft Comput., 5(3):315--331, 2005.
• 11: 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]
• 12: P. McMinn and M. Holcombe. The state problem for evolutionary testing. In GECCO, pages 2488--2498, 2003.
• 13: D. J. Montana. Strongly typed genetic programming. Technical Report #7866, 10 Moulton Street, Cambridge, MA 02138, USA, 7 1993.
• 14: R. A. Müller, C. Lembeck, and H. Kuchen. A symbolic java virtual machine for test case generation. In M. H. Hamza, editor, IASTED Conf. on Software Engineering, pages 365--371. IASTED/ACTA Press, 2004.
• 15: 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 of the 25th Brazilian Symposium on Computer Networks and Distributed Systems, pages 143--156. Brazilian Computer Society (SBC), 2007.
• 16: 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 CEDI 2007: Proceedings of the 1st Jornadas sobre Algoritmos Evolutivos y Metaheuristicas of the 2nd Congreso Español de Informática, pages 137--144, 2007.
• 17: 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: International Workshop on Nature Inspired Cooperative Strategies for Optimization (to appear), Studies in Computational Intelligence. Springer-Verlag, 11 2007.
• 18: R. Sagarna, A. Arcuri, and X. Yao. Estimation of distribution algorithms for testing object oriented software. In D. Srinivasan and L. Wang, editors, 2007 IEEE Congress on Evolutionary Computation, pages -, Singapore, 25-28 Sept. 2007. IEEE Computational Intelligence Society, IEEE Press.
• 19: A. Seesing and H.-G. GroSS. A genetic programming approach to automated test generation for object-oriented software. ITSSA, 1(2):127--134, 2006.
• 20: 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
• 21: Stefan Wappler , Frank Lammermann, Using evolutionary algorithms for the unit testing of object-oriented software, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068187]
• 22: 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.
• 23: 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