Abstracts - 2006
Feedback-directed Random Test Generation
Carlos Pacheco1, Shuvendu K. Lahiri*, Sanjukta Pal1, Thomas Ball* & Michael D. Ernst1
Random testing  is an attractive technique for detecting software errors. It can very cheaply generate vast numbers of tests, and those tests may expose corner cases that would have been overlooked by a human or by ordinary usage. Some studies suggest that random testing is as effective as systematic techniques [4,6].
A problem with random testing is that it can waste time exploring uninteresting parts of the search space. Not every input to a program is meaningful, and in fact most inputs are probably illegal. Consider a binary search routine that requires a sorted array as input. Since most arrays violate that precondition, random generation would spend most of its time creating such illegal inputs.
We present a new approach to random search by using feedback to prune undesirable states and method sequences from the search. We also contribute a set of auxiliary techniques: heuristics for guiding the search, a contract checking framework that acts as an oracle, and test case minimization for reducing a very long method sequence to a small test sequence that exhibits the same behavior. We have implemented the technique in two tools: Randoop is targeted to Microsoft's .Net Framework, and Joe is targeted to the Java Virtual Machine. Our tools scale to large programs, and they have found serious errors in widely-deployed commercial and open source software.
Consider Figure 1 below, which shows two of the test cases generated
by Joe when run on Sun's JDK (version 1.5). The first test case shows
a violation of the
The second test case creates a legal instance
Feedback-directed test generation
Test case generation for object-oriented programs can be viewed as a search problem over data values and method sequences, where the public methods provide the ways that state can be mutated. Existing approaches to method sequence generation (for example, [1,2,3,7]) typically operate offline: the method sequences are derived statically, compiled, and finally executed. In contrast, we take a feedback-directed, execution-driven approach: our technique inspects the actual execution of the sequence as it is being constructed, in order to guide the search toward sequences that yield new object states. Our technique is fully automatic, requires no input from the user, and scales to realistic applications composed of thousands of classes. Our technique builds inputs incrementally by randomly selecting a method call to apply and selecting arguments from among previously-constructed inputs. As soon as it is built, the input is executed and checked against a set of contracts; the technique then uses the result of the execution to determine if the input is redundant, illegal or error-revealing:
Finally, any test input that exhibits violating behavior is minimized and output as small, failing test case like those in Figure 1.
Why it works
To understand why feedback-directed outperforms undirected, consider
the two test cases from Figure 1. When creating
Offline exploration, on the other hand, may obliviously extend method sequences that throw exceptions, or might create and extend distinct sequences that yield equal objects. In our experiments, offline exploration did not discover the above violation of the equals contract.
We have implemented the technique in two tools, RANDOOP (for Microsoft's .Net Framework) and JOE (for Java). To evaluate the technique's effectiveness, we have applied the tools to a set of 14 widely-used libraries comprising 780KLOC, and found many serious errors, including:
In a second experiment, we evaluated feedback-directed generation against traditional unguided generation. Compared with traditional unguided random test generation (as implemented both by us and by an independent tool ), feedback-directed test generation finds more bugs, finds more interesting and severe bugs, and produces fewer redundant tests.
 H. Y. Chen, T. H. Tse, and T. Y. Chen. Taccle: a methodology for object-oriented software testing at the class and cluster levels. ACM Trans. Softw. Eng. Methodol., 10(1):56-109, 2001.
 C. Csallner and Y. Smaragdakis. JCrasher: an automatic robustness ftester for Java. Software: Practice and Experience, 34:1025-1050, 2004.
 Csallner and Y. Smaragdakis. Check'n' Crash: Combining static checking and testing. In ICSE'05, Proceedings of the 26th International Conference on Software Engineering, St. Louis, MO, USA, May 18-20, 2005.
 J. W. Duran and S. C. Ntafos. An evaluation of random testing. IEEE Transactions on Software Engineering, 10(4):438-444, July 1984.
 D. Hamlet. Random testing. In Encyclopedia of Software Engineering. John Wiley and Sons, 1994.
 D. Hamlet and R. Taylor. Partition testing does not inspire confidence. IEEE Transactions on Software Engineering, 16(12):1402-1411, Dec. 1990.
 T. Xie, D. Marinov, W. Schulte, and D. Notkin. Symstra: A framework for generating object-oriented unit tests using symbolic execution. In Proceedings of the 11th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 05), pages 365-381, April 2005.