Source-linked AI summary
Nopol: Automatic Repair of Conditional Statement Bugs in Java Programs
Jifeng Xuan, Matias Martinez, Favio Demarco, Maxime Clément, Sebastian Lamelas, Thomas Durieux, Daniel Le Berre, Martin Monperrus
TL;DR
NOPOL addresses automatic repair of buggy IF conditions and missing preconditions, where test suites provide expected behavior and expose bugs. It localizes expected condition values, collects runtime traces, and uses SMT synthesis to generate patches. On 22 real-world bugs, NOPOL fixed 17, while the paper also documents five limitation cases.
Problem
IF conditions are error-prone in Java, motivating automatic repair of conditional statements in real-world programs.
Method
NOPOL uses angelic fix localization, runtime traces, and SMT encoding to synthesize conditional patches from buggy programs and test suites.
Results
17 out of 22 real-world bugs were fixed by NOPOL, including four bugs with manually added test cases.
Takeaways & Limitations
NOPOL provides a publicly available approach for repairing buggy IF conditions and missing preconditions in Java programs.
Takeaways & Limitations
The evaluation covers 22 bugs, and the authors identify five bugs revealing limitations of NOPOL.
Abstract
from arXiv · showhide
We propose NOPOL, an approach to automatic repair of buggy conditional statements (i.e., if-then-else statements). This approach takes a buggy program as well as a test suite as input and generates a patch with a conditional expression as output. The test suite is required to contain passing test cases to model the expected behavior of the program and at least one failing test case that reveals the bug to be repaired. The process of NOPOL consists of three major phases. First, NOPOL employs angelic fix localization to identify expected values of a condition during the test execution. Second, runtime trace collection is used to collect variables and their actual values, including primitive data types and objected-oriented features (e.g., nullness checks), to serve as building blocks for patch generation. Third, NOPOL encodes these collected data into an instance of a Satisfiability Modulo Theory (SMT) problem, then a feasible solution to the SMT instance is translated back into a code patch. We evaluate NOPOL on 22 real-world bugs (16 bugs with buggy IF conditions and 6 bugs with missing preconditions) on two large open-source projects, namely Apache Commons Math and Apache Commons Lang. Empirical analysis on these bugs shows that our approach can effectively fix bugs with buggy IF conditions and missing preconditions. We illustrate the capabilities and limitations of NOPOL using case studies of real bug fixes.
1 INTRODUCTION
NOPOL is an automatic repair system for conditional bugs that uses test suites, runtime information, and SMT-based synthesis to generate patches. Evaluated on 22 real-world bugs, it fixed 17 and included case studies of its benefits and limitations.
- The test suite supplies passing cases that model expected behavior and at least one failing case exposing the bug.
- It collects primitive values and object-oriented features, then encodes runtime traces into an SMT problem whose solution becomes a source patch.The collected object-oriented data include nullness and certain method-call results.
- 17 out of 22 real-world bugs were fixed, including four bugs with manually added test cases.The dataset contained 16 bugs with buggy IF conditions and 6 with missing preconditions.
- The paper analyzes repair results through four case studies and discusses limitations using five bugs.
- NOPOL targets buggy IF conditions and missing preconditions in Java programs.It generates conditional patches from a buggy program and its test suite.
- NOPOL localizes potential repair sites with angelic fix localization and identifies expected conditional values.
2 BACKGROUND
NOPOL applies test-suite-based repair to buggy IF conditions and missing preconditions through fault localization, angelic values, runtime traces, and SMT synthesis. Its design supports nullness and selected object-state queries in Java programs.
- Test-suite-based repair uses passing tests as expected-behavior specifications and failing tests as bug specifications.The approach assumes the test suite adequately models the program functionality.
- NOPOL repairs buggy IF conditions and missing preconditions in Java code.
- Overview: Fault localization ranks statements, and NOPOL treats IF statements or other eligible statements as candidate repair locations.
- Overview: Angelic fix localization changes an IF value to true or false during execution to identify a repair location and expected behavior.The same process supports arbitrary statements as candidates for missing preconditions.
- Overview: Runtime trace collection records primitive variables plus nullness and selected method-call information at candidate locations.
- Overview: NOPOL converts traces into an SMT formula, translates satisfiable solutions into patches, and re-executes the test suite for validation.Unsatisfiable candidates are skipped in favor of the next ranked statement.
9 end
The procedure forces a conditional value to false and checks whether the failing tests then pass.
- NOPOL forces the condition to false while executing the failing-test set.
- If a failing test passes after the forced value, the procedure records that outcome.
15 end
The test-case set is described as passing after the relevant execution step.
- The procedure records that all test cases in Tf pass.
23 end
NOPOL uses angelic fix localization to identify conditional locations and expected boolean values that could make failing tests pass. It records these findings as angelic tuples for subsequent patch synthesis.
- NOPOL examines each IF condition executed during test-suite execution in a failing test case.
- An angel forces an executed IF condition to true or false and checks whether the failing test case passes.
- An angelic tuple records the IF-condition location, forced boolean value, and failing test case.
9 end
The missing-precondition localization algorithm reports success when skipping the candidate statement allows all failing tests to pass.
- The algorithm considers a candidate non-IF statement and a set of failing test cases.
- It checks whether skipping the statement causes the failing test cases to pass.
- The algorithm's successful outcome is that all test cases in the failing set pass.
14 end
NOPOL collects expected outcomes and runtime data, then synthesizes conditional expressions through SMT constraints. Its object-oriented handling includes nullness and selected side-effect-free state queries, while search assumptions and strategy choices limit completeness.
- Search-space assumptions: The search space for buggy IF conditions is reduced from 2^tc to 2 per condition and failing test case by assuming a constant angelic value across repeated executions.
- Limitations: NOPOL does not prioritize updating conditions over adding preconditions, and its single-value assumption makes the approach incomplete.
- Patch synthesis: NOPOL synthesizes an expression whose evaluations match the collected expected outcomes using an SMT-based component-synthesis technique.
- Expected outcome collection: For buggy IF conditions, angelic values supply expected outcomes for failing tests, while actual condition evaluations supply them for passing tests.
- Expected outcome collection: For missing preconditions, expected values are true for passing tests and false for failing tests, causing the statement to be skipped.
- Runtime data collection: NOPOL collects primitive variables, parameters, fields, constants, nullness, and outputs of argument-less side-effect-free state-query methods.
3 Function traverse(lx)
The traversal procedure searches for a building-block expression and its input locations. It treats locations appearing in the input set as building-block inputs.
- The procedure finds an expression φx(Ix, x) together with the input-location tuple Ix.
- The input locations are represented as a tuple containing Ix,1, Ix,2, and subsequent locations.
- A location x in I is handled as the input of a building block.
13 end
NOPOL localizes suspicious statements, gathers execution information, and encodes candidate repairs as SMT constraints before translating feasible solutions into conditional-expression patches.
- SMT-to-patch translation: A feasible SMT solution is translated into a conditional expression that returns a boolean and can replace an IF condition or serve as a precondition.Translation uses backward traversal from the final output location and converts the resulting variables and Boolean combinations into source code.
- SMT-to-patch translation: For the running example, the solution binds the output to f2, producing the Boolean patch f2(i0, i0), while f1 is unused.The output location is lr = 5, and f2 receives the integer input represented by li0.
- Angelic fix localization: Statement suspiciousness ranges from 0 to 1, with 1 indicating the highest likelihood of localizing the bug and 0 indicating no likelihood.The score uses total failing tests together with failing and passing tests covering the statement.
- Angelic fix localization: NOPOL ranks statements with Ochiai suspiciousness and examines positive-ranked statements for IF-condition repair or added preconditions.Ochiai is used because prior empirical studies report stronger localization of root causes in object-oriented programs than alternative techniques.
4 AUTOMATIC REPAIR OF REAL-WORLD IF BUGS
NOPOL fixed 17 of 22 real-world conditional bugs, generating patches that often matched or functionally equaled developer patches. The evaluation also exposes specification, localization, timeout, and synthesis limitations.
- Repair effectiveness: 17 of 22 bugs were fixed: 13 of 16 buggy IF conditions and 4 of 6 missing preconditions.Four of five unfixed bugs related to timeout, under a five-hour execution limit.
- Patch characteristics: Generated patches used primitive values as well as nullness checks and string length() features.Nullness checking appeared in Bugs CL4 and PM2, while length() appeared in Bugs CL1, CL2, CL3, and CL5.
- Patch locations: Six buggy IF-condition bugs were fixed by adding preconditions rather than updating existing conditions.A major reason was that a non-IF statement ranked above the buggy IF statement during fault localization.
- Patch correctness: 13 of 17 synthesized patches were functionally as correct as the manually written patches.Five of these required additional test cases because the original test suite was too weak.
- Test specifications: Additional test cases were required for six bugs because the original specifications were too weak to drive correct synthesis.Without those additions, the synthesized patches degenerated.
- Limitations: NOPOL failed on one bug because it incorrectly identified the output of a precondition.This failure occurred for Bug PL3 despite its buggy statement being ranked first.
- Efficiency: NOPOL’s average repair time was 24.8 seconds for 17 fixed bugs, while four of five non-fixed bugs timed out.Across all 22 bugs, execution time ranged from 6 to 84 seconds in the reported runs.
- Fault localization: The average fault-localization rank for patched statements was 32.8, with four of 17 patched statements ranked over 50.This indicates room for improving fault-localization techniques.
5 DISCUSSIONS
The discussion contrasts NOPOL with related approaches, examines fault localization and parallelization, and reflects on test-suite quality and overfitting.
- Comparison with SemFix: NOPOL extends component-based synthesis to missing preconditions and object-oriented patches containing null checks and method calls.Its evaluation is larger than SemFix's, using real bugs from programs averaging 25K lines of code.
- Fault localization: Jaccard performs best on average wasted effort for buggy IF conditions, while Tarantula performs best for missing preconditions; Ochiai remains acceptable.Median results are tied across several techniques, and the authors conclude that NOPOL is not highly sensitive to the localization choice.
- Potential parallelization: NOPOL's core algorithms are highly parallelizable across test cases, potential locations, and independent SMT synthesis levels.Parallel synthesis can produce multiple patches and may waste cost at higher levels when a simpler patch is already available.
- Test-suite quality: For nine bugs, the existing test suite led to a correct patch; adding tests enabled correct patches for four more bugs.The authors call for methods recommending when additional tests are needed and what they should specify.
- Overfitting: Repair operators may overfit test inputs for some bugs while producing generic correct solutions for others.The paper identifies qualification of repair operators according to overfitting as future work.
6 THREATS TO VALIDITY
The validity discussion identifies threats involving evaluation scope, repair assumptions, test modifications, and possible bias in dataset construction.
- Scope: The evaluation covers 22 real-world bugs, which may be too few to represent NOPOL's actual effectiveness.The authors characterize the limited bug count as a threat despite focusing on two specific bug types.
- Assumptions: NOPOL targets single-location faults and does not currently address multiple faults or patches requiring multiple locations.This is stated as a boundary shared with previous test-suite-based repair work.
- Test cases: Several test cases were added, transformed, or deleted to facilitate repair, so evaluation results depend partly on test-case modification.The paper analyzes the root causes of these modifications and lists them publicly.
- Dataset construction: Dataset construction may be biased because the authors manually separated conditional patch fragments from commits containing additional code.Bug PM2 required retaining only one of two nested preconditions from a complex fixing commit.
7 RELATED WORK
Related work situates NOPOL among test-suite-based, semantic, search-based, and empirical studies of automatic repair, while highlighting concerns about patch correctness and overfitting.
- Test-suite-based repair: GenProg uses genetic programming to generate AST patches for C programs, whereas NOPOL synthesizes conditional repairs for Java using SMT.Test-suite-based repair generates and validates patches against a given test suite.
- Semantic repair: SemFix synthesizes assignments and conditions through semantic analysis and SMT encoding, motivating NOPOL's synthesis design.NOPOL differs by addressing missing preconditions and supporting object-oriented constructs.
- Condition synthesis: SPR also synthesizes conditions and supports other bug types, while NOPOL's simplified trace trades repairability for lower synthesis cost.The simplification can fail when a condition executes more than once in a test case.
- Patch prioritization: Prophet prioritizes candidate patches with a probability model and generated correct patches for 15 of 69 GenProg defects.NOPOL's SMT implementation can also synthesize more than one patch.
- Empirical foundations: Studies examine maintainability, human debugging support, reusable code, repair-action priors, and overfitting in automatically generated patches.These works broaden evaluation beyond whether patches merely pass the test suite.
- Empirical foundations: Kali's empirical reassessment found only two GenProg, three AE, and two RSRepair bugs correctly patched, with other reported patches affected by experimental issues.This work motivates scrutiny of correctness in automatic-repair evaluations.
8 CONCLUSION
NOPOL is an SMT-based test-suite repair approach for buggy IF conditions and missing preconditions, evaluated on real-world programs and supported by public artifacts.
- Conclusion: NOPOL uses angelic fix localization, execution traces, and SMT encoding to synthesize patches for buggy IF conditions and missing preconditions.The SMT solution is translated into a patch for the buggy program.
- Conclusion: The evaluation covers 22 real-world programs and includes four case studies describing NOPOL's benefits and limitations.The implementation is publicly available for replication and further research.
- Future work: Future work targets more real-world bugs, better angelic fix localization, more method calls, and improved SMT encoding.These directions address limitations identified by the authors.