Finding the needles in the haystack: Generating legal test inputs for object-oriented programs

Download: PDF, slides (PDF), slides (PowerPoint).

“Finding the needles in the haystack: Generating legal test inputs for object-oriented programs” by Shay Artzi, Michael D. Ernst, Adam Kieżun, Carlos Pacheco, and Jeff H. Perkins. In M-TOOS: 1st Workshop on Model-Based Testing and Object-Oriented Systems, (Portland, OR, USA), Oct. 2006, pp. 27-34.
A previous version appeared as MIT Computer Science and Artificial Intelligence Laboratory technical report MIT-CSAIL-TR-2006-056, (Cambridge, MA), September 5, 2006.

Abstract

A test input for an object-oriented program typically consists of a sequence of method calls that use the API defined by the program under test. Generating legal test inputs can be challenging because, for some programs, the set of legal method sequences is much smaller than the set of all possible sequences; without a formal specification of legal sequences, an input generator is bound to produce mostly illegal sequences.

We propose a scalable technique that combines dynamic analysis with random testing to help an input generator create legal test inputs without a formal specification, even for programs in which most sequences are illegal. The technique uses an example execution of the program to infer a model of legal call sequences, and uses the model to guide a random input generator towards legal but behaviorally-diverse sequences.

We have implemented our technique for Java, in a tool called Palulu, and evaluated its effectiveness in creating legal inputs for real programs. Our experimental results indicate that the technique is effective and scalable. Our preliminary evaluation indicates that the technique can quickly generate legal sequences for complex inputs: in a case study, Palulu created legal test inputs in seconds for a set of complex classes, for which it took an expert thirty minutes to generate a single legal input.

Download: PDF, slides (PDF), slides (PowerPoint).

BibTeX entry:

@inproceedings{ArtziEKPP2006,
   author = {Shay Artzi and Michael D. Ernst and Adam Kie{\.z}un and
	Carlos Pacheco and Jeff H. Perkins},
   title = {Finding the needles in the haystack: Generating legal test
	inputs for object-oriented programs},
   booktitle = {M-TOOS: 1st Workshop on Model-Based Testing and
	Object-Oriented Systems},
   pages = {27--34},
   address = {Portland, OR, USA},
   month = oct,
   year = {2006}
}

(This webpage was created with bibtex2web.)

Back to Michael Ernst's publications.