In an object-oriented program, a unit test often consists of a sequence of method calls that create and mutate objects, then use them as arguments to a method under test. It is challenging to automatically generate sequences that are legal and behaviorally diverse, that is, reaching as many different program states as possible.
This project investigates how to use static and dynamic program analyses to improve the effectiveness of automated test generation. As an initial step, we proposed a combined static and dynamic automated test generation approach to address these problems for code without a formal specification.
Our approach first uses dynamic analysis to infer a call sequence model from a sample execution, then uses static analysis to identify method dependence relations based on the fields they may read or write. Finally, both the dynamically inferred model (which tends to be accurate but incomplete) and the statically identified dependence information (which tends to be conservative) guide a random test generator to create legal and behaviorally diverse tests.
Our Palus tool implements this testing approach. We compared its effectiveness with a pure random approach, a dynamic-random approach (without a static phase), and a static-random approach (without a dynamic phase) on several popular open-source Java programs. Tests generated by Palus achieved higher structural coverage and found more bugs.
Palus is also used internally in Google. It has found a number previously unknown bugs in four well-tested Google products.