Synthesizing method sequences for high-coverage testing

Suresh Thummalapenta, Tao Xie, Nikolai Tillmann, Jonathan De Halleux, Zhendong Su

Research output: Contribution to journalArticlepeer-review


High-coverage testing is challenging. Modern object-oriented programs present additional challenges for testing. One key difficulty is the generation of proper method sequences to construct desired objects as method parameters. In this paper, we cast the problem as an instance of program synthesis that automatically generates candidate programs to satisfy a user-specified intent. In our setting, candidate programs are method sequences, and desired object states specify an intent. Automatic generation of desired method sequences is difficult due to its large search space-sequences often involve methods from multiple classes and require specific primitive values. This paper introduces a novel approach, called Seeker, to intelligently navigate the large search space. Seeker synergistically combines static and dynamic analyses: (1) dynamic analysis generates method sequences to cover branches; (2) static analysis uses dynamic analysis information for not-covered branches to generate candidate sequences; and (3) dynamic analysis explores and eliminates statically generated sequences. For evaluation, we have implemented Seeker and demonstrate its effectiveness on four subject applications totalling 28K LOC. We show that Seeker achieves higher branch coverage and def-use coverage than existing state-of-the-art approaches. We also show that Seeker detects 34 new defects missed by existing tools..

Original languageEnglish (US)
Pages (from-to)189-206
Number of pages18
JournalACM SIGPLAN Notices
Issue number10
StatePublished - Oct 2011
Externally publishedYes


  • Object-oriented testing
  • Symbolic execution

ASJC Scopus subject areas

  • General Computer Science


Dive into the research topics of 'Synthesizing method sequences for high-coverage testing'. Together they form a unique fingerprint.

Cite this