Palus: A Hybrid Automated Test Generation Tool for Java

Sai Zhang
University of Washington, USA

In object-oriented programs, a unit test often consists of a sequence of method calls that create and mutate objects. It is challenging to automatically generate sequences that are legal and behaviorally-diverse, that is, reaching as many different program states as possible. This paper proposes a combined static and dynamic 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 dynamicallyinferred 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 approach. We compared it with a pure random approach, a dynamic-random approach (without a static phase), and a static-random approach (without a dynamic phase) on six popular open-source Java programs. Tests generated by Palus achieved 35% higher structural coverage on average. Palus is also internally used in Google, and has found 22 new bugs in four well-tested products.