PaperlayerView exact revision on arXiv

Source-linked AI summary

ARJA: Automated Repair of Java Programs via Multi-Objective Genetic Programming

Yuan Yuan, Wolfgang Banzhaf

arXiv:1712.07804v1cs.SE

TL;DR

GenProg’s performance for Java repair is unsatisfactory, motivating a search-focused redesign. ARJA combines a lower-granularity patch representation with multi-objective GP and search-space reduction, and outperforms jGenProg on Defects4J while repairing several difficult multi-location bugs.

  • Problem

    Recent empirical studies report unsatisfactory GenProg performance for Java, including many nonsensical patches and limited validation of its expressive search.

  • Method

    ARJA uses a decoupled patch representation, NSGA-II multi-objective search, test filtering, search-space rules, and type matching for Java program repair.

  • Results

    ARJA generated test-suite adequate patches for 59 Defects4J bugs versus 27 for jGenProg and correctly fixed at least 18 versus 5.

  • Takeaways & Limitations

    The results suggest that GP’s repair capability was not fully exploited and that ARJA can repair several real multi-location bugs.

  • Takeaways & Limitations

    Test-suite adequate patches can still be incorrect, and the paper identifies test-suite augmentation as a fundamental solution to patch overfitting.

Abstract

from arXiv · show

Recent empirical studies show that the performance of GenProg is not satisfactory, particularly for Java. In this paper, we propose ARJA, a new GP based repair approach for automated repair of Java programs. To be specific, we present a novel lower-granularity patch representation that properly decouples the search subspaces of likely-buggy locations, operation types and potential fix ingredients, enabling GP to explore the search space more effectively. Based on this new representation, we formulate automated program repair as a multi-objective search problem and use NSGA-II to look for simpler repairs. To reduce the computational effort and search space, we introduce a test filtering procedure that can speed up the fitness evaluation of GP and three types of rules that can be applied to avoid unnecessary manipulations of the code. Moreover, we also propose a type matching strategy that can create new potential fix ingredients by exploiting the syntactic patterns of the existing statements. We conduct a large-scale empirical evaluation of ARJA along with its variants on both seeded bugs and real-world bugs in comparison with several state-of-the-art repair approaches. Our results verify the effectiveness and efficiency of the search mechanisms employed in ARJA and also show its superiority over the other approaches. In particular, compared to jGenProg (an implementation of GenProg for Java), an ARJA version fully following the redundancy assumption can generate a test-suite adequate patch for more than twice the number of bugs (from 27 to 59), and a correct patch for nearly four times of the number (from 5 to 18), on 224 real-world bugs considered in Defects4J. Furthermore, ARJA is able to correctly fix several real multi-location bugs that are hard to be repaired by most of the existing repair approaches.

1 INTRODUCTION

ARJA targets limitations in GenProg’s Java repair performance by improving GP search, while preserving scalability and support for diverse, multi-location transformations. It introduces a decoupled patch representation, multi-objective search, filtering, search-space reduction, and broader fix-ingredient generation.

  • Motivation: GenProg’s reported patches are often nonsensical, while its ability to address multi-location bugs remains insufficiently validated.The paper distinguishes patch incorrectness caused by weak tests from nonsensical transformations such as single deletions.
  • Motivation: The paper identifies search-algorithm effectiveness as a bottleneck after prior studies largely validated GenProg’s redundancy-based search space.GenProg’s scalability and expressive GP transformations motivate improving search rather than abandoning the redundancy assumption.
  • Evaluation: On 224 Defects4J bugs, ARJA generated test-suite adequate patches for 59 real bugs versus 27 for jGenProg and correctly fixed at least 18 versus 5.The study also reports correct repairs for several multi-location bugs that most other approaches struggle to address.
  • ARJA approach: ARJA decouples likely-buggy locations, operation types, and replacement or insertion code in a lower-granularity patch representation.This representation is designed to let GP explore repair possibilities more effectively.
  • ARJA approach: ARJA formulates repair as multi-objective optimization and uses NSGA-II to search for repairs while minimizing weighted failure rate and patch size.The approach explicitly seeks simpler repairs rather than optimizing test performance alone.
  • ARJA approach: ARJA filters unaffected tests and applies rules across operation initialization, ingredient screening, and solution decoding to reduce fitness-evaluation effort and search space.It also restricts replacement or insertion statements using both variable scope and method scope.

2 BACKGROUND AND MOTIVATION

ARJA targets weaknesses in GenProg-based Java repair by improving the representation, search objectives, test evaluation, code-ingredient generation, and search-space reduction. The motivation is to make GP-based repair more effective while preserving scalability and support for diverse, including multi-location, bugs.

  • GenProg background: GenProg uses GP to combine statement deletions, replacements, and insertions while relying on existing program code as repair ingredients.Its patch-based representation improves scalability over AST-based representations, but encodes edits as high-level units.
  • Representation limitations: High-granularity GenProg genes hide operation types, faulty locations, and ingredients from crossover, hindering propagation of useful partial information.Even when two parents collectively contain a needed patch, crossover may not recombine the required edit components, leaving mutation to generate the exact operation.
  • Representation limitations: Lower-granularity representations can expose edit components, but exchanging ingredients across locations may cause information loss or uncompilable variants because contexts and scopes differ.Oliveira et al.’s representation divides operation types, locations, and replacement or insertion code, yet crossover can mismatch these components across destinations.
  • ARJA’s search design: ARJA proposes a lower-granularity representation that addresses GenProg’s representation limitations while avoiding problems introduced by prior decomposed representations.Its design is paired with a multi-objective search formulation that incorporates repair simplicity into GP search.
  • ARJA’s search design: ARJA treats repair as multi-objective optimization and uses NSGA-II to search for patches while biasing the search toward simpler repairs.Multi-objective evolutionary search maintains non-dominated solutions across competing objectives, including patch simplicity.
  • Search-space and ingredient improvements: ARJA uses variable and method scope when selecting replacement or insertion code, improving the likelihood that modified programs compile.The paper also proposes type matching to create potentially useful new statements from syntactic patterns in existing code and rules to remove definitely unnecessary operations.

3 APPROACH

ARJA repairs Java programs with multi-objective genetic programming, combining a decoupled patch representation with test filtering and search-space reduction strategies. Its workflow localizes suspicious code, constructs compatible ingredients, evolves patches, and outputs test-suite adequate solutions.

  • ARJA is a Java repair tool that finds test-suite adequate patches through multi-objective genetic programming.
  • The workflow uses fault localization and coverage analysis to identify likely-buggy statements and seed statements supplying replacement or insertion ingredients.
  • Positive tests unrelated to selected likely-buggy statements are filtered, while variable and method scopes determine usable ingredients at each location.
  • ARJA supports delete, replace, and insert operations, then evolves patches by minimizing test failure rate and patch size simultaneously.
  • Test filtering safely removes positive tests that cannot be affected by GP edits, reducing fitness-evaluation cost without changing search behavior.
  • Its patch representation decouples likely-buggy locations, operation types, and ingredients, while search-space rules reduce meaningless edits and improve compilation prospects.

4 EXPERIMENTAL DESIGN

The evaluation compares ARJA and related repair systems on seeded and real-world Java bugs using targeted research questions about search, scalability, ingredients, and correctness. The design separates search-ability comparisons from broader Defects4J evaluation and documents implementation and dataset boundaries.

  • The study evaluates ARJA through nine research questions covering test filtering, search strategy, multi-objective optimization, multi-location repair, type matching, comparative effectiveness, correctness, failures, and runtime.
  • For RQs 2–4, comparisons use ARJA without type matching to focus on search ability under the redundancy assumption.
  • The repair systems investigated are ARJA, GenProg, RSRepair, Kali, and Nopol, with Java reimplementations of several originally C-oriented systems.
  • ARJA is implemented in Java using jMetal, Eclipse JDT Core, Gzoltar, and JaCoCo, with source code released for reproducibility.
  • Experiments use both seeded bugs and 224 real-world bugs from four Defects4J Java projects.
  • Search-ability comparisons use seeded bugs because Defects4J can confound search with localization failures, limited redundancy, and trivial deletion repairs.

5 EXPERIMENTAL RESULTS AND ANALYSIS

Test filtering substantially reduces the tests and CPU time required for fitness evaluation. The reduction remains safe in the reported validation, provided suspiciousness thresholds do not exclude actual faulty locations.

  • Increasing γmin rapidly decreases the tests and CPU time considered, but excessively large thresholds can miss actual faulty locations.
  • 59%, 31%, 97%, and 37% CPU-time reductions occur for C1, T1, L1, and M1 respectively when γmin = 0.01.
  • At γmin = 0.1 for M1, filtering reduces tests from 5,246 to 118 and one fitness evaluation from 210 seconds to 3.4 seconds.Across 2,000 evaluations, the reported saving can reach 115 hours for one repair trial.
  • Post-run validation found no exceptions: patches passing the reduced test suite also passed the original suite.

5.2 Genetic Search vs. Random Search (RQ2)

Within the ARJA framework, genetic search generally outperforms pure random search in both repair effectiveness and efficiency. The advantage is especially pronounced for bugs requiring multi-line patches.

  • Except for F2 and F5, ARJA achieves higher success rates and requires fewer evaluations than ARJAr across the considered seeded bugs.
  • For F10–F13, ARJAr finds no test-suite adequate patch in 30 trials, whereas ARJA succeeds in the majority of trials.
  • ARJA always fixes F5, while ARJAr succeeds in only 3 of 30 trials despite finding repairs more quickly when successful.
  • Overall, ARJA significantly outperforms ARJAr in repair effectiveness and efficiency, particularly on multi-location bugs.
  • The result contrasts with earlier GenProg-versus-random-search findings, which used a different framework and C bugs dominated by trivial functionality deletions.

5.3 Multi-Objective vs. Single-Objective (RQ3)

ARJA’s multi-objective formulation outperforms its single-objective variant, producing simpler and more numerous repairs while improving the search for test-suite adequate patches.

  • ARJA generates smaller patches than ARJAs on nearly all evaluated bugs, with F5 as the only exception.Its average patch size is usually close to each bug’s k value, indicating effective minimization of f1.
  • ARJA finds notably more distinct test-suite adequate patches than ARJAs for every bug in a successful trial.
  • ARJA clearly outperforms ARJAs on the “Success” metric, despite both variants evaluating weighted failure rate.The results suggest that jointly minimizing f1 and f2 promotes minimization of f2.
  • The helper objective f1 can guide search toward better building blocks and help escape local minima.
  • The multi-objective formulation finds simpler repairs, more of them, and more effective test-suite adequate patches than the single-objective formulation.

5.4 Strength in Fixing Multi-Location Bugs (RQ4)

On multi-location bugs, ARJA outperforms GenProg and RSRepair in success rate and generally finds simpler repairs with comparable overall CPU time.

  • The comparison covers F3–F13 because these are multi-location bugs, whereas F1 and F2 are single-location bugs.All three approaches use the redundancy assumption, and the relevant fix ingredients exist in their search spaces.
  • ARJA outperforms GenProg and RSRepair on all considered multi-location bugs in terms of success rate.On most bugs, ARJA achieves a much higher success rate than both counterparts.
  • ARJA generally requires fewer evaluations than GenProg and RSRepair to find a repair.GenProg achieves better “#Evaluations” on F9, but that metric uses only one successful trial.
  • ARJA’s overall CPU time is comparable to GenProg’s, despite ARJA performing more work in each fitness evaluation.RSRepair fixes only two bugs here with very low success rate, so its efficiency cannot be rated.
  • ARJA usually finds much simpler repairs than GenProg on the evaluated multi-location bugs.The paper attributes this difference to their distinct search mechanisms and patch-growth behavior.

5.5 Effect of Type Matching (RQ5)

Type matching expands ARJA’s ingredient space by synthesizing statements from existing syntactic patterns, helping repair bugs whose ingredients are absent from the program but challenging genetic search.

  • Type matching creates new ingredient statements by matching variables, methods, or both, rather than directly screening existing ingredients.
  • ARJA finds no test-suite adequate patch for H1–H3 and H5, whereas ARJAv or ARJAb can often fix these bugs.This indicates that type matching can help when fix ingredients do not exist in the buggy program.
  • Method-only type matching performs poorly on H1–H3 and H5, suggesting difficulty generating their required fix ingredients.
  • The enlarged ingredient space challenges GP’s search ability, so additional CPU time may help ARJAv and ARJAb overcome this difficulty.
  • Type matching can generate useful ingredients for bugs that violate the redundancy assumption.

5.6 Evaluation on Real-World Bugs (RQ6)

In Defects4J, ARJA fixes more real-world bugs than the compared repair approaches and complements Nopol, while type-matching variants add some non-redundancy fixes but do not improve ARJA’s total count.

  • 59 bugs, or 26.3% of 224, are fixed by ARJA—the highest count among the ten evaluated approaches.The paper states that no existing repair approach had synthesized adequate patches for as many bugs on the same dataset.
  • Type-matching ARJA variants do not repair more bugs overall than ARJA, but they fix some bugs unavailable to redundancy-based approaches.Their larger search spaces may exceed GP’s search ability.
  • ARJAb can invent a new statement by mapping out-of-scope variable and method usages through type matching, enabling the patched program to pass the given test suite.
  • ARJA fixes 15 bugs that GenProg, RSRepair, and Kali cannot fix, while all four approaches fix 23 bugs.
  • ARJA and Nopol show complementarity: ARJA handles 41 bugs that Nopol cannot, while Nopol handles 17 that ARJA cannot.
  • The ten approaches collectively synthesize test-suite adequate patches for 88 of 224 Defects4J bugs.

5.7 Patch Correctness (RQ7)

ARJA synthesized at least 18 correct patches in Defects4J, outperforming jGenProg and repairing several multi-location bugs. Manual case studies show that ARJA patches can be semantically equivalent to human-written fixes despite syntactic differences.

  • At least 18 correct patches were synthesized by ARJA, compared with 5 correctly fixed by jGenProg.The comparison concerns Defects4J bugs and uses manual assessment of patch correctness.
  • 13 correctly fixed bugs were single-location cases repaired by ARJA with one edit.M58 and M86 are presented as examples.
  • Single-location bugs: For M58, ARJA’s syntactically different inserted statement was semantically equivalent to the human-written replacement.The relevant method invocations were confirmed not to change anything outside the statement’s computation.
  • Multi-location bugs: For L35, ARJA’s patch differed only in the exception message, without affecting the specified functionality.
  • Multi-location bugs: For T15, ARJA reproduced the human fix’s behavior through different edits that avoided an incorrect overflow result.The patch replaces one statement with break and adds overflow detection elsewhere.
  • Some test-suite adequate patches may be incorrect but can still assist developers because they resemble corresponding human-written patches.The paper identifies C1, C19, L7, and L16 as examples.
  • ARJA generated correct patches for several multi-location bugs that most other repair approaches cannot repair.
  • Comparisons with non-redundancy-based approaches are limited because correct-fix counts depend on bug classes and dataset distributions.The authors note that Defects4J may not reflect the natural distribution of real-world bugs.

5.8 Reasons for Failure (RQ8)

ARJA failures arise when needed ingredients are absent, genetic search cannot find existing patches, or fault localization excludes relevant lines. Adjusting search parameters or tests can alleviate some localization and search failures.

  • Some bugs are unrepairable when their required fix ingredients are absent from ARJA’s search space.This explains ARJA’s failures on H1–H3 and H5.
  • ARJA may miss an existing patch when GP cannot find it within the allowed generations.The paper attributes failures on F9 and L53 to insufficient search ability and possible local optima.
  • Fault-localization failures can omit relevant faulty lines, preventing ARJA from considering necessary edits.
  • Increasing nmax to 80 enabled ARJA to find a correct patch for L10.The resulting patch deleted the if statement at line 5.
  • Modifying the JUnit test enabled ARJA to fix M46 with a patch identical to the human-written patch.M46 is a multi-location bug.

5.9 Repair Efficiency (RQ9)

ARJA and its variants generally repair Defects4J bugs within minutes, with lower reported time costs than several comparison approaches. The authors characterize this efficiency as broadly acceptable for industrial use, despite occasional long maximum runtimes.

  • Around 5 minutes median and 10 minutes average were required for successful repairs by ARJA and its three variants.
  • ARJA and its variants were more efficient than GenProg, RSRepair, and Nopol in the reported comparisons.Kali was fastest on average but considered only trivial patches.
  • Maximum CPU time for a repair could exceed one hour.
  • The authors regard ARJA’s efficiency as generally acceptable for industrial use in light of human bug-fixing time.

6 THREATS TO VALIDITY

The empirical evaluation faces threats from implementation, parameter, stochastic-run, seeded-bug, dataset, manual-correctness, and comparison-design limitations. These constraints may affect validity, generalizability, and the interpretation of correctness comparisons.

  • Implementation threats: Reimplemented comparison systems may perform differently from their originals, and undiscovered implementation bugs remain possible.The authors released the implementations to mitigate this threat.
  • Parameter settings: Uniform parameters ensure fair comparisons but may be poor for some bugs and can hide improvements obtainable through bug-specific tuning.Resetting nmax enabled ARJA to find a correct patch for bug L10.
  • Stochasticity: One run per approach on each of 224 Defects4J bugs may overestimate or underestimate stochastic repair effectiveness.The study nevertheless involved 1,568 repair trials across seven methods.
  • Bug selection: Randomly seeded bugs may have fitness landscapes favoring particular search mechanisms, limiting conclusions about differences among search strategies.This concern affects comparisons of multi-objective GP, single-objective GP, and random search.
  • Dataset representativeness: The 224 bugs from four Defects4J projects may not represent real-world defect distributions and difficulties, limiting generalization to other datasets.The authors characterize Defects4J as the most comprehensive dataset of real Java bugs.
  • Correctness assessment: Manual patch assessment can misclassify incorrect patches as correct because analysts may lack sufficient understanding of the buggy program.The paper notes that such manual analysis is not scientifically sound, although it is accepted practice.
  • Comparison design: ARJA’s continued search for multiple adequate patches versus jGenProg’s termination at the first creates a possible bias in correct-fix counts.The authors believe this bias is minimal because jGenProg failed to produce certain patches, but its alternative outcomes remain unobserved.

7 RELATED WORK

Related work spans search-based and semantics-based repair, with systems differing in search strategy, patch representation, templates, learned ranking, and supported bug classes. ARJA builds on this landscape of genetic, stochastic, constraint-solving, and pattern-based approaches.

  • Search-based repair: Search-based repair navigates a potentially repair-containing space using computational methods such as genetic algorithms or random search.The category includes approaches that seek test-suite adequate patches.
  • Genetic programming approaches: JAFF co-evolves programs and unit tests with evolutionary algorithms but handles only a subset of Java and was evaluated on toy programs.Its evaluation scope is narrower than large real-world Java repair studies.
  • Genetic programming approaches: GenProg uses scalable patch representation and was reported to repair 55 of 105 bugs from eight open-source programs.The representation replaced an earlier AST-based representation to support large-scale programs.
  • Genetic programming approaches: GenProg-related studies investigate fitness enhancement, representation and operator choices, and applications to assembly and Java bytecode.These studies extend or examine different components of the GenProg framework.
  • Search-based repair: Mutation-based repair processes suspicious locations individually and mutates the statement at each location to generate candidate fixes.It combines standard mutation operators with fault localization.
  • Pattern- and template-based repair: PAR uses manually learned human fix patterns and templates, producing patches reported as more meaningful than GenProg’s.Its evolutionary process differs from GenProg’s crossover and mutation operators.
  • Search-based repair: AE uses program equivalence and adaptive search to reduce the search space by an order of magnitude relative to GenProg.Its deterministic strategy controls the order of candidate repairs and test cases.
  • Search-based repair: RSRepair replaces GenProg’s evolutionary search with random search, which performed more effectively and efficiently on 24 benchmark bugs.The comparison directly questions whether GP is necessary for that benchmark.

8 CONCLUSION AND FUTURE WORK

ARJA combines a lower-granularity patch representation, multi-objective GP, test filtering, search-space rules, and type matching for Java repair. Across seeded and real-world evaluations, it repaired more bugs than comparison systems and correctly handled several multi-location bugs, while future work targets stronger templates and non-functional optimization.

  • Conclusion: ARJA decouples buggy locations, operation types, and ingredient statements, then uses NSGA-II to minimize weighted failure rate and patch size.The representation is intended to let GP traverse the search space more effectively while seeking simpler repairs.
  • Conclusion: Test filtering, scope- and method-based type matching, and three search-space rules reduce fitness-evaluation effort and unnecessary code manipulations.Type matching also creates potential ingredients from syntactic patterns of existing statements.
  • Empirical findings: Seeded-bug experiments demonstrate the necessity and effectiveness of multi-objective GP and the strength of type matching.The evaluation compares ARJA variants using these mechanisms.
  • Empirical findings: 59 real bugs received test-suite adequate patches with ARJA, compared with 27 for jGenProg and 35 for Nopol.This was the highest number among the compared approaches.
  • Empirical findings: Manual analysis found at least 18 correct Defects4J fixes for ARJA versus 5 for jGenProg, including 7 repaired correctly and automatically for the first time.ARJA also correctly repaired several multi-location bugs considered difficult for most existing approaches.
  • Reproducibility: ARJA is publicly available on GitHub to support reproducible research on automated Java program repair.The paper provides the project repository URL.
  • Future work: Future work will add repair templates and combine ARJA with many-objective GAs to improve non-functional properties of Java software.The planned extensions address real-world repair performance and software robustness-related objectives.
Loading 1712.07804v1…