Feedback-directed random test generation

Download: PDF, Randoop implementation.

“Feedback-directed random test generation” by Carlos Pacheco, Shuvendu K. Lahiri, Michael D. Ernst, and Thomas Ball. In ICSE'07, Proceedings of the 29th International Conference on Software Engineering, (Minneapolis, MN, USA), May 23-25, 2007, pp. 75-84.
A tool description appeared as “Randoop: Feedback-directed random testing for Java” by Carlos Pacheco and Michael D. Ernst. In Companion to Object-Oriented Programming Systems, Languages, and Applications (OOPSLA 2007), (Montréal, Canada), October 23-25, 2007, pp. 815-816.
A previous version appeared as Microsoft Research technical report MSR-TR-2006-125, (Redmond, WA), Sep. 2006.

Abstract

We present a technique that improves random test generation by incorporating feedback obtained from executing test inputs as they are created. Our technique builds inputs incrementally by randomly selecting a method call to apply and finding arguments from among previously-constructed inputs. As soon as an input is built, it is executed and checked against a set of contracts and filters. The result of the execution determines whether the input is redundant, illegal, contract-violating, or useful for generating more inputs. The technique outputs a test suite consisting of unit tests for the classes under test. Passing tests can be used to ensure that code contracts are preserved across program changes; failing tests (that violate one or more contract) point to potential errors that should be corrected.

Our experimental results indicate that feedback-directed random test generation can outperform systematic and undirected random test generation, in terms of coverage and error detection. On four small but nontrivial data structures (used previously in the literature), our technique achieves higher or equal block and predicate coverage than model checking (with and without abstraction) and undirected random generation. On 14 large, widely-used libraries (comprising 780KLOC), feedback-directed random test generation finds many previously-unknown errors, not found by either model checking or undirected random generation.

Download: PDF, Randoop implementation.

BibTeX entry:

@inproceedings{PachecoLEB2007,
   author = {Carlos Pacheco and Shuvendu K. Lahiri and Michael D. Ernst
	and Thomas Ball},
   title = {Feedback-directed random test generation},
   booktitle = {ICSE'07, Proceedings of the 29th International Conference
	on Software Engineering},
   pages = {75--84},
   address = {Minneapolis, MN, USA},
   month = {May~23--25,},
   year = {2007}
}

(This webpage was created with bibtex2web.)

Back to Program Analysis Group publications.