TL;DR
This paper introduces S3, a novel program repair system that leverages programming-by-examples (PBE) to synthesize high-quality, generalizable bug fixes. By combining domain-specific language (DSL) for syntactic constraint, efficient enumeration-based search, and a novel set of syntax- and semantic-guided ranking features, S3 significantly outperforms state-of-the-art techniques in fixing bugs in both small and large real-world programs.
What Problem Does This Paper Address?
Automated program repair (APR) aims to fix bugs in software automatically, reducing the burden on developers. A prominent approach is semantics-based repair, which uses symbolic execution to infer specifications and then synthesizes code to meet them. However, these inferred specifications are often incomplete, leading to a vast search space of potential repairs. This sparsity makes it challenging to synthesize generalizable patches, which not only pass existing tests but also avoid overfitting to them. Overfitting is a critical issue, as it can lead to patches that appear correct but fail in slightly different scenarios. Existing methods struggle to balance expressiveness with the ability to guide synthesis towards high-quality, generalizable solutions.
Methods
S3 tackles the challenge of synthesizing generalizable repairs through a three-pronged approach:
- Domain-Specific Language (DSL) for Syntactic Constraints: S3 uses an extended version of the SYNTH-LIB DSL to systematically constrain the syntactic search space for repairs. This allows for specifying starting "sketches" (often the original buggy expression) and defining grammar rules that guide the synthesis process. This customization helps to focus the search on more plausible repair candidates.
- Efficient Enumeration-Based Search: S3 employs an enumeration-based search strategy over the constrained search space. It systematically explores candidate expressions within a defined size range around the original buggy expression. This approach is designed to be tractable by partitioning the search space into layers, allowing for progressive exploration if initial attempts fail.
- Syntax- and Semantic-Guided Ranking Features: This is a core novelty of S3. It uses a set of ranking features to prioritize candidate repairs based on their syntactic and semantic proximity to the original buggy code.
- Syntactic Features: These include AST differencing (measuring transformations needed to change one AST to another), cosine similarity of AST node occurrence vectors, and locality of variables/constants.
- Semantic Features: These measure semantic distance and quality, including model counting (disagreement between expressions), output coverage (how well a candidate covers example outputs), and anti-patterns (to filter out trivial or obviously incorrect solutions).
Datasets
S3 was evaluated on two datasets:
- Small Programs with High Coverage Test Suites: 52 Java bugs from the IntroClass benchmark, translated to Java. These programs are small but feature potentially complex fixes. Crucially, they come with two independent, high-quality test suites, allowing for a robust assessment of repair quality and generalizability. Additional tests were generated using Symbolic PathFinder (SPF).
- Large Real-World Programs: 100 Java bugs from 62 real-world programs, with patches submitted by developers serving as ground truth. This dataset was curated to include bugs with patches changing fewer than five lines of code to simplify correctness assessment.
Key Insights and Ideas
- Proximity as a Proxy for Quality: The core intuition is that correct repairs are often syntactically and semantically close to the original buggy code. S3 leverages this by using a combination of syntactic and semantic distance metrics to rank candidate solutions.
- Constraining the Search Space is Crucial: By using a DSL to define custom grammars and sketches, S3 effectively prunes the vast search space of possible repairs, making the synthesis process more efficient and leading to higher-quality results.
- Combining Syntax and Semantics for Ranking: Neither syntactic nor semantic features alone are sufficient. S3's strength lies in their synergistic combination, allowing it to identify repairs that are both structurally similar and behaviorally consistent with the original code.
- PBE as a Foundation for Synthesis: The paper demonstrates how programming-by-examples principles can be effectively applied to program repair, moving beyond simple template-based or purely constraint-solving approaches.
Key Results
- IntroClass Dataset (52 bugs): S3 correctly patched 22 bugs, significantly outperforming Angelix (7), Enumerative (1), and CVC4 (1). S3's patches generalized to held-out tests in all 22 cases, with baselines showing very high overfitting rates (61-92%).
- Real-World Dataset (100 bugs): S3 correctly patched 20 bugs (syntactically matching developer fixes), compared to Angelix (6), Enumerative (6), and CVC4 (5). When considering semantically equivalent patches (via manual inspection), S3's performance was even stronger, with no overfitted patches.
- S3's contribution: S3 was able to fix bugs that other tools could not, often producing patches that were semantically equivalent but not syntactically identical to developer fixes.
Limitations and Future Work
- Scope of Repair: S3, like many semantics-based techniques, primarily modifies expressions in conditions or on the right-hand side of assignments. It is limited to boolean and integer types and cannot handle larger structural changes (e.g., transforming
if-then-else iftoif-then-else). - Generalizability of Datasets: While S3 was evaluated on a substantial set of real-world bugs, its performance might not generalize to all types of programs or bug classes.
- Future Work: The authors suggest strengthening specifications with mined invariants, integrating inductive and deductive synthesis, extending the DSL for more complex tasks, and exploring machine learning for bug classification. They also plan to extend the SYNTH-LIB grammar for more complex program repair domains.
Summary updated