Synthesizing method sequences for high-coverage testing

Suresh Thummalapenta, Tao Xie, Nikolai Tillmann, Jonathan de Halleux, Zhendong SuOOPSLA 2011 · DOI

TL;DR

This paper introduces Seeker, a novel approach to automatically generate method sequences for object-oriented testing. Seeker intelligently navigates the complex search space of method calls by synergistically combining static and dynamic analysis, achieving higher branch and def-use coverage than existing state-of-the-art tools and detecting new defects.

What Problem Does This Paper Address?

Achieving high code coverage in modern object-oriented (OO) software is a significant challenge for testers. A key difficulty lies in generating the correct sequences of method calls to construct objects with specific states, which are crucial for exercising different code paths, especially conditional branches. Existing approaches often struggle with the vast search space of possible method sequences, the need for precise primitive values, and the complexities introduced by OO features like encapsulation. This paper aims to address this gap by proposing a systematic method for synthesizing these crucial method sequences to achieve high test coverage.

Methods

Seeker employs a novel, iterative approach that combines static and dynamic analysis to synthesize method sequences. The core idea is a feedback loop:

  • Dynamic Analysis (DSE-based): Seeker initially uses a Dynamic Symbolic Execution (DSE) engine (like Pex) to attempt to generate a method sequence that covers a target branch. DSE explores code paths and collects constraints.
  • Static Analysis: If DSE fails to generate a suitable sequence, Seeker resorts to static analysis. It identifies potential "pre-target branches" or methods that might lead to covering the desired branch. This involves techniques like analyzing method-call graphs to understand how methods interact and how fields are modified, even private ones.
  • Feedback Loop: Seeker then uses DSE again, but this time with the candidate sequences or "skeletons" generated by static analysis. DSE helps to "concretize" these skeletons by generating primitive values and also helps filter out irrelevant static candidates. This iterative process allows Seeker to intelligently explore the search space and overcome the limitations of each analysis technique alone.

Key novelties include the synergistic combination of static and dynamic analysis in a feedback loop, the use of method-call graphs to handle encapsulation, and the systematic generation of method sequences to satisfy user-specified intents (desired object states).

Datasets

The evaluation was performed on four subject applications: QuickGraph, Dsa, xUnit, and NUnit. These applications represent a total of 28,000 lines of code (LOC) and are popular open-source libraries. No new benchmarks were introduced; the focus was on evaluating Seeker on existing, real-world software.

Key Insights and Ideas

  • Synergy is Key: Pure static or dynamic analysis alone is insufficient for complex OO testing. Seeker's strength lies in their intelligent combination, where each compensates for the other's weaknesses.
  • Method-Call Graphs for Encapsulation: The use of method-call graphs is a clever way to reason about how to manipulate object states, even when direct field access is not possible due to encapsulation.
  • Intent-Driven Synthesis: Framing the problem as synthesizing sequences to achieve a "desired object state" (user intent) provides a clear goal for the synthesis process.
  • Feedback Loop for Efficiency: The iterative feedback loop between static and dynamic analysis helps prune the search space and focus on promising sequences, making the approach scalable.

Key Results

  • Higher Coverage: Seeker achieved significantly higher branch coverage (up to 12% more than Pex and 26% more than Randoop) and def-use coverage (up to 15.7% more than Pex and 15.3% more than Randoop) across the evaluated applications.
  • Defect Detection: Seeker detected 34 new defects, including an infinite loop in QuickGraph, demonstrating its effectiveness in finding bugs missed by other tools.
  • Comparison with State-of-the-Art: Seeker outperformed Randoop (random approach) and Pex (DSE-based approach) in terms of coverage and defect detection.
  • Effectiveness on Complex Sequences: Seeker was particularly effective in generating complex method sequences required for high coverage, a task that challenged other tools.

Limitations and Future Work

  • Path Explosion: While Seeker suggests shorter skeletons, the underlying DSE engine can still face path explosion issues when exploring these sequences, especially with loops. Future work aims to develop search strategies to guide DSE more effectively.
  • Environment Dependency: Seeker, like DSE, can be affected by environment dependencies in the code under test. Future work may involve combining Seeker with mocking techniques to isolate these dependencies.
  • Loop-Based Sequences: Seeker currently struggles with generating sequences that require methods to be invoked multiple times to achieve a desired state. Future work plans to address this with a fitness-based approach.
  • Abstract Classes/Interfaces: Handling abstract classes and interfaces where implementations are not provided by the library itself is a challenge. Future work will explore techniques similar to mocking environments.
  • Natural Language Intent: The authors plan to extend Seeker to accept user intents expressed in natural language, transforming them into desired object states.

Summary updated

BibTeX
@inproceedings{thummalapenta2011synthesizing,
  author = {Suresh Thummalapenta and Tao Xie and Nikolai Tillmann and Jonathan de Halleux and Zhendong Su},
  title = {{Synthesizing method sequences for high-coverage testing}},
  booktitle = {OOPSLA},
  year = {2011},
  doi = {10.1145/2048066.2048083},
}
Figure