PaperlayerView exact revision on arXiv

Source-linked AI summary

Precise Condition Synthesis for Program Repair

Yingfei Xiong, Jie Wang, Runfa Yan, Jiachen Zhang, Shi Han, Gang Huang, Lu Zhang

arXiv:1608.07754v5cs.SE

TL;DR

Insufficient tests make plausible patches unreliable, motivating ACS’s precise condition synthesis for program repair. ACS ranks variables and predicates using program dependencies, documentation, and mined contextual frequencies, and also uses precise boundary conditions to return test oracles. On Defects4J, it produced 17 correct patches with 73.9% precision and 7.6% recall.

  • Problem

    Insufficient real-world test suites mean that passing all tests does not necessarily establish program correctness, while correct patches are sparse among plausible patches.

  • Method

    ACS decomposes condition synthesis into variable and predicate selection, ranking variables by dependencies and documentation and predicates by frequencies in similar project contexts.

  • Results

    ACS generated 23 patches for four Defects4J projects, including 17 correct patches, achieving 73.9% precision and 7.6% recall.

  • Takeaways & Limitations

    The results indicate that refined ranking techniques for specific repair techniques are promising, and precise conditions can support boundary-case oracle returning.

Abstract

from arXiv · show

Due to the difficulty of repairing defect, many research efforts have been devoted into automatic defect repair. Given a buggy program that fails some test cases, a typical automatic repair technique tries to modify the program to make all tests pass. However, since the test suites in real world projects are usually insufficient, aiming at passing the test suites often leads to incorrect patches. In this paper we aim to produce precise patches, that is, any patch we produce has a relatively high probability to be correct. More concretely, we focus on condition synthesis, which was shown to be able to repair more than half of the defects in existing approaches. Our key insight is threefold. First, it is important to know what variables in a local context should be used in an "if" condition, and we propose a sorting method based on the dependency relations between variables. Second, we observe that the API document can be used to guide the repair process, and propose document analysis technique to further filter the variables. Third, it is important to know what predicates should be performed on the set of variables, and we propose to mine a set of frequently used predicates in similar contexts from existing projects. We develop a novel program repair system, ACS, that could generate precise conditions at faulty locations. Furthermore, given the generated conditions are very precise, we can perform a repair operation that is previously deemed to be too overfitting: directly returning the test oracle to repair the defect. Using our approach, we successfully repaired 17 defects on four projects of Defects4J, which is the largest number of fully automatically repaired defects reported on the dataset so far. More importantly, the precision of our approach in the evaluation is 73.9%, which is significantly higher than previous approaches, which are usually less than 40%.

I. INTRODUCTION

ACS targets precise program-repair patches by ranking synthesized conditions more finely than test behavior alone. It combines dependency-based variable ordering, document analysis, and predicate mining, achieving 73.9% precision on Defects4J.

  • Motivation: Real-world test suites are often insufficient, so passing all tests can produce plausible but incorrect patches.Precision measures the proportion of defects correctly fixed by the first plausible patch among plausibly fixed defects.
  • Motivation: Correct patches are sparse among plausible patches, making it difficult to identify the correct repair from a large candidate space.Experiments found often hundreds or thousands of plausible patches but only one or two correct ones per defect.
  • Approach: Condition synthesis inserts or modifies an if condition and decomposes ranking into variable selection followed by predicate selection.The approach treats synthesizing if(a>10) as selecting variable a and then selecting predicate >10.
  • Approach: ACS ranks variables by dependency-based locality, filters them using program documentation, and mines predicates frequent in similar contexts.These techniques exploit the buggy program’s structure, documentation, and conditional expressions in existing projects.
  • Contribution: ACS’s precise conditions also support directly returning a failed test’s oracle when the synthesized condition identifies a boundary case.The paper presents this as a repair operation previously considered too overfitting.
  • Results: 73.9% precision and 7.6% recall were achieved on four Defects4J projects from 23 generated patches, including 17 correct patches.The reported precision was higher than previous testing-based approaches, which were usually below 40%.

II. MOTIVATING EXAMPLE

The motivating example shows ACS selecting a precise boundary condition from many test-consistent alternatives. Its ranking combines dependency locality, documentation, and mined predicates, while current document analysis remains lightweight.

  • Motivating Example: The Math99 defect involves Integer.MIN_VALUE, where abs can return a negative value and the failed test expects ArithmeticException.The passing test uses a=1, b=50, while the failing test uses a=Integer.MIN_VALUE, b=1.
  • Motivating Example: Two tests permit many plausible conditions, including b==1 and lcm != 50, so ACS must select the correct condition from a large space.Existing approaches may assign equal priority to conditions with identical testing behavior.
  • Ranking Strategy: ACS decomposes condition ranking into variable ranking and predicate ranking using three ranking techniques.The techniques rank both which variables to use and which predicates to apply.
  • Dependency-Based Ordering: Dependency ordering favors lcm because it depends on a and b and is therefore more likely to appear in the following conditional expression.The locality intuition treats upstream variables as more temporary and derived variables as more likely condition operands.
  • Document Analysis: Document analysis extracts variables from @throws comments and uses fuzzy matching to connect documented words with variable names.For example, elitismRate is split into “elitism” and “rate,” with the last word used for matching.
  • Limitation: Current document analysis only makes lightweight use of javadoc comments; more sophisticated analysis is left for future work.The paper notes that richer techniques might obtain more information or directly generate conditions.
  • Predicate Mining: Predicate mining ranks predicates by their frequency in contexts similar to the target condition using a large repository of existing projects.The context may include variable type, variable name, and surrounding method name.
  • Generated Repair: ACS synthesizes lcm==Integer.MIN_VALUE, treating the single-value check as a likely boundary case suitable for directly returning the oracle.The example uses the precise condition to generate the repair.

III. APPROACH

ACS takes a program, one failed test, and passed tests, then generates patches through oracle-returning or condition-modification templates. It synthesizes conditions by ranking variables and predicates and returns the first plausible patch found within the time limit.

  • Inputs and Outputs: ACS receives a program, a failed test, and passed tests, and outputs a patch on the program.These inputs define the repair setting for the approach.
  • Oracle Returning: Oracle-returning templates insert a guarded value return or exception throw before the last statement executed by the failed test.Value-returning handles expected return values, while oracle-throwing handles expected exceptions.
  • Oracle Returning: ACS discards synthesized oracle-returning patches when heuristic rules do not classify the guard as a boundary check.This boundary-check filter constrains use of the oracle-returning template.
  • Condition Modification: Condition-modification templates locate a potentially faulty condition and either narrow or widen it using the synthesized condition.Narrowing changes if(c′) to if(c′ && !c); predicate switching determines which modification is applied.
  • Condition Synthesis: Condition synthesis first ranks variables, then ranks predicates for each variable, validating each resulting condition against the failed execution.A candidate condition must evaluate to true on the target failed execution.
  • Search Procedure: ACS applies oracle-returning templates before condition-modification templates and returns the first plausible patch found within the time limit.If no plausible patch is found, the system reports failure.

B. Returning the Oracle

ACS extracts test oracles for guarded repairs, including constants, exceptions, and functional expressions. It uses slicing to isolate reusable oracle code and applies boundary-check rules to constrain oracle-returning patches.

  • Oracle Extraction: ACS extracts constants directly, constructs expected exceptions, or copies functional oracles into generated conditional statements.The oracle form determines how the guarded repair body is generated.
  • Functional Oracle Example: The example inserts if(len==1) { return a[0]*b[0]; } into linearCombination, with len==1 supplied by condition synthesis.The copied expression is the test oracle a[0]*b[0].
  • Oracle Extraction: For functional oracles, ACS subtracts input slices from the oracle slice to retain code needed for the expected result but not test-input initialization.It then renames test-input variables to the target method’s formal parameters.
  • Boundary Checks: ACS classifies if(c) s as a boundary check when c compares a variable with a constant or when an out-of-range comparison guards an exception.The rules encode special logic for boundary inputs and exception cases.

C. Variable Ranking

Variable ranking first prepares and filters candidates, then orders them using dependencies and source proximity; predicate mining separately ranks frequently used predicates from similar contexts.

  • Candidate preparation: The system considers local variables, method parameters, this, and expressions used in other conditions as variable candidates.Expressions are represented as temporary variables to unify candidate handling.
  • Candidate preparation: Variables that cannot distinguish the expected outcomes of test executions are filtered out before synthesis.The remaining variables form the candidate set.
  • Dependency-based ordering: Dependency ranking builds a graph whose nodes are variables and whose edges represent intra-procedural data and control dependencies.Assignment statements create data dependencies, while variables assigned within branches depend on variables in the controlling condition.
  • Dependency-based ordering: Topological sorting prioritizes more dependent variables first, then breaks ties using distance from the faulty condition to each variable’s initialization.Cycles are collapsed before sorting, and the final ordering distinguishes priority levels from ranks.
  • Predicate ranking: Predicate mining retrieves conditions from similar contexts using variable type, names, and method names, then ranks extracted predicates by frequency.The implementation searches GitHub source files using condition, type, and name-related keywords.
  • Predicate ranking: The predicate space includes comparisons, equality, instanceof, and predefined edge-case tests, with normalization rules reducing equivalent forms.The pred function recursively extracts predicate multisets, and only the top 20 predicates are considered for synthesis.

A. Research Questions

The evaluation asks how the ranking techniques perform, how ACS handles real-world defects, how it compares with existing approaches, and how its components contribute. It uses top-starred GitHub Java projects and four Defects4J projects, excluding Closure because GZoltar does not support its customized testing format.

  • Research questions: The evaluation addresses ranking performance, real-world defect repair, comparison with existing approaches, and component contributions.These correspond to research questions RQ1 through RQ4.
  • Datasets: Two datasets are used: the five most-starred Java projects on GitHub as of July 15, 2016, and four projects from Defects4J.The GitHub and Defects4J datasets answer different subsets of the research questions.
  • Datasets: Closure is omitted from Defects4J because GZoltar does not support its customized testing format.The paper notes that this matches an existing study’s treatment of the project.
  • Evaluation controls: Predicate mining excludes files from the subject and known forked projects, and correctly repaired cases receive manual clone-result review.These procedures address potential bias from retrieving already-fixed subject-project code.

D. RQ1: Performance of the Three Techniques

ACS evaluates dependency-based variable ordering, document analysis, and predicate mining as ranking and filtering techniques for condition synthesis. The results indicate that correct variables and predicates are usually prioritized, while documentation filtering has more positive than negative effects.

  • Dependency-based ordering: 89.9% of variables ranked in the first dependency priority level, and 97.3% ranked within the first two levels.Average ranks were significantly below 50%, with Wilcoxon signed-rank tests significant for all projects.
  • Document analysis: Document analysis produced more positive than negative effects when filtering variables mentioned in JavaDoc comments.False positives can arise when a comment word, such as “value,” refers to a different variable than the same-named local variable.
  • Predicate mining: 66.7% of predicates were included in the returned list, and 92.5% of included predicates were ranked first.The results support the assumption that predicates are unevenly distributed across similar contexts.
  • Predicate mining: 88.2% of cases had no wasted effort, while 94.9% had wasted effort no greater than 4.Wasted effort counts incorrect predicates ranked above the correct predicate, or the returned-list length when the correct predicate is absent.

E. RQ2: Performance of ACS

ACS was evaluated on Defects4J by comparing generated patches with user patches under a conservative semantic-equivalence criterion. It generated 23 patches, including 17 correct patches, with high precision and substantially higher recall within its target defect class.

  • Repair results: 17 of 23 generated patches were correct, yielding 73.9% precision and 7.6% recall across 224 Defects4J defects.The reported recall includes defects outside the class repairable by changing a condition or returning an oracle.
  • Repair results: 94.4% recall was achieved within the defect space that ACS can generate.Only one additional in-space defect, Time19, was identified; its correct variable was ranked third-level and filtered out.
  • Efficiency: Patch generation took at most 28.0 minutes, with a median of 5.5 minutes and a minimum of 0.9 minutes.Web-query time was excluded because it depends strongly on network speed.
  • Qualitative findings: ACS generated simple-form patches that fixed challenging defects, including a defect caused by Java BigDecimal accepting strings with two minus signs.The generated guard prevents parsing such strings into an incorrect value.

F. RQ3: Comparison with Existing Approaches

ACS achieved the highest precision and recall among the compared approaches, while its components reduced incorrect patch generation and complemented existing repair systems.

  • ACS achieved the highest precision among the five compared approaches and was more than four times as precise as the second-ranked approach.
  • ACS fixed 15 defects for the first time, while only 2 fixed defects overlapped with other approaches.The authors interpret this as evidence that ACS can complement existing repair approaches.
  • Component analysis: Dependency-based ordering usually ranked the correct variable first or second despite up to 12 candidate variables.This reduced the risk of incorrect patches and repair time.
  • Component analysis: Predicate mining prevented many incorrect patches from being generated, and no correct patch was blocked by predicate mining.
  • Component analysis: 11 of 17 successful patches used predicates mined from GitHub, while 6 used predefined predicates.
  • Component analysis: The evaluated repair templates fixed 9 defects through exception-throwing, 6 through value-returning, and 2 through narrowing.The authors suggest effectiveness for defects involving missing boundary checks.

V. DISCUSSION

The discussion positions ACS as a refined condition-ranking approach, contrasts it with alternative repair and ranking methods, and identifies scope boundaries and future directions.

  • More Patches for a Defect: ACS focuses on improving the precision of the first generated patch rather than producing multiple patches for each defect.Ranking multiple patches as debugging aids remains future work.
  • Alternative Method in Condition Synthesis: ACS mines ==0 and negates the condition instead of relying on mining !=0, because this provides more control over the predicate space.
  • Related approaches: ACS uses refined ranking techniques specifically designed for condition synthesis, incorporating variable locality, program documentation, and existing source code.
  • Related approaches: Unlike approaches that rank syntactic distance, mutation operators, or invariants, ACS can distinguish integer predicates by their frequencies in existing projects.
  • Related approaches: DeepFix has been evaluated only on syntactic errors from students’ homework, leaving its performance on more complex defects unknown.
  • Related approaches: QACrashFix achieves 80% precision but is limited to crash fixes whose answers already exist on StackOverflow.

VII. CONCLUSION

The paper studies refined ranking for condition synthesis and reports that ACS achieves relatively high precision with reasonable recall on Defects4J.

  • ACS achieved 73.9% precision and 7.6% recall on Defects4J.
Loading 1608.07754v5…