Staged program repair with condition synthesis

Fan Long, Martin C. RinardESEC/SIGSOFT FSE 2015 · DOI

TL;DR

This paper introduces SPR, a novel program repair system that combines "staged program repair" and "condition synthesis" to efficiently search for and generate software patches. SPR significantly outperforms previous systems, fixing over five times more defects on a common benchmark by intelligently exploring a richer space of potential repairs.

What Problem Does This Paper Address?

Software development is plagued by defects, and manually fixing them is time-consuming and expensive. While automatic program repair (APR) systems aim to automate this process, existing approaches struggle with the vast search space of possible repairs. They often rely on limited transformation schemas or inefficient search strategies, leading to a low success rate for more general classes of defects. This paper tackles the challenge of creating an APR system that can effectively and efficiently search a rich space of repairs to fix a wider range of software bugs.

Methods

SPR employs a three-pronged approach:

  • Parameterized Transformation Schemas: Instead of fixed repair templates, SPR uses general schemas that represent a strategy for fixing a class of defects. These schemas are parameterized, allowing them to generate a large number of potential repairs.
  • Target Value Search: For each parameterized schema, SPR quickly checks if any parameter value can lead to a successful repair. This allows it to prune entire branches of the search space early on if no promising parameters are found.
  • Condition Synthesis: Many of SPR's transformations require synthesizing a logical condition. SPR first uses target value search to gather constraints on this condition and then synthesizes logical expressions that satisfy these constraints, enabling the transformation to generate a correct repair.

This "staged" approach allows SPR to bypass the vast majority of candidate repairs and focus its search on the most promising regions, leading to a significant reduction in the search space explored.

Datasets

The paper evaluates SPR on a benchmark set consisting of 69 real-world defects and 36 functionality changes from eight open-source applications: libtiff, lighttpd, PHP interpreter, gmp, gzip, python, wireshark, and fbc. This benchmark set was previously used to evaluate other automatic patch generation systems.

Key Insights and Ideas

  • Staging is Crucial for Scalability: The core insight is that by staging the repair process (transformation selection, target value search, condition synthesis), SPR can efficiently navigate extremely large repair search spaces that would otherwise be intractable.
  • Parameterized Schemas Unlock Richness: Using parameterized schemas, rather than fixed transformations, allows SPR to represent a much broader range of potential repairs, increasing the likelihood of finding a correct one.
  • Condition Synthesis is Key to Practicality: The ability to synthesize logical conditions is essential for instantiating these parameterized schemas effectively, especially when dealing with complex control flow.
  • Developer Patches as a Semantic Benchmark: The authors note that developer patches often align semantically with SPR's correct repairs, providing a strong validation of SPR's effectiveness.

Key Results

  • Significant Improvement in Defect Fixing: SPR generates correct repairs for 11 out of 69 defects and plausible repairs for 38. This is over five times more defects fixed compared to previous systems (GenProg and AE) on the same benchmark.
  • Reduced Search Space: The staged approach leads to a reduction of up to two orders of magnitude in the size of the search space SPR explores.
  • Efficiency: SPR generates repairs in under two hours on average, even for complex applications.
  • Broader Repair Scope: A significant portion of SPR's correct repairs (17 out of 20) fall outside the search space of previous systems like GenProg and AE, indicating SPR's ability to find novel types of fixes.

Limitations and Future Work

  • Generalizability of Benchmark: While the benchmark is realistic, the authors acknowledge that results might not generalize to all types of defects and test suites.
  • Single Transformation Application: SPR currently applies only one transformation at a time. Combining multiple transformations efficiently is an open challenge, as previous attempts have often resulted in simple, functionality-eliminating patches.
  • Search Space Extensions: The paper discusses potential extensions to SPR's search space (e.g., including more complex conditions, multiple transformations) that could fix additional defects but also increase search complexity. Future work could explore how to manage this increased complexity.
  • Formal Specifications: SPR operates without formal specifications, which is a strength for real-world applications but differs from some other APR approaches.

Summary updated

BibTeX
@inproceedings{long2015staged,
  author = {Fan Long and Martin C. Rinard},
  title = {{Staged program repair with condition synthesis}},
  booktitle = {ESEC/SIGSOFT FSE},
  year = {2015},
  doi = {10.1145/2786805.2786811},
}
Figure