PaperlayerView exact revision on arXiv

Source-linked AI summary

Elixir: Effective object-oriented program repair

Ripon K. Saha, Yingjun Lyu, Hiroaki Yoshida, Mukul R. Prasad

arXiv:2112.10915v1cs.SE

TL;DR

Object-oriented repair needs broader treatment of method invocations, which are pervasive in Java code and bug fixes. ELIXIR generates expressive invocation-based repairs and uses machine learning to rank candidates before validation. It correctly repaired more bugs than its baselines and other evaluated repair techniques on Defects4J and Bugs.jar.

  • Problem

    Method invocations are fundamental in object-oriented programs and prevalent in Java bug fixes, while existing repair techniques support them only through restricted schemas.

  • Method

    ELIXIR generates expressive repair expressions using method calls alongside variables, fields, and constants, then ranks candidate patches with a four-feature machine-learned model.

  • Results

    ELIXIR correctly repaired 26 Defects4J bugs versus 14 previously, and 22 Bugs.jar bugs versus 14, while outperforming the evaluated state-of-the-art techniques.

  • Takeaways & Limitations

    The evaluation supports ELIXIR as an effective object-oriented repair technique for the two studied Java bug datasets.

  • Takeaways & Limitations

    The conclusions may not generalize beyond Defects4J and Bugs.jar or beyond Java application bugs to other object-oriented languages.

Abstract

from arXiv · show

This work is motivated by the pervasive use of method invocations in object-oriented (OO) programs, and indeed their prevalence in patches of OO-program bugs. We propose a generate-and-validate repair technique, called ELIXIR designed to be able to generate such patches. ELIXIR aggressively uses method calls, on par with local variables, fields, or constants, to construct more expressive repair-expressions, that go into synthesizing patches. The ensuing enlargement of the repair space, on account of the wider use of method calls, is effectively tackled by using a machine-learnt model to rank concrete repairs. The machine-learnt model relies on four features derived from the program context, i.e., the code surrounding the potential repair location, and the bug report. We implement ELIXIR and evaluate it on two datasets, the popular Defects4J dataset and a new dataset Bugs.jar created by us, and against 2 baseline versions of our technique, and 5 other techniques representing the state of the art in program repair. Our evaluation shows that ELIXIR is able to increase the number of correctly repaired bugs in Defects4J by 85% (from 14 to 26) and by 57% in Bugs.jar (from 14 to 22), while also significantly out-performing other state-of-the-art repair techniques including ACS, HD-Repair, NOPOL, PAR, and jGenProg.

I. INTRODUCTION

ELIXIR targets object-oriented repair by treating method invocations as first-class repair components and ranking the resulting candidate patches with machine learning. It introduces the Bugs.jar dataset and reports gains over baselines and state-of-the-art tools.

  • Motivation: 57% of statements in three Java projects contained method invocations, while 77% of one-line bug fixes involved method-invocation changes.The study covered Eclipse JDT, Platform, and BIRT.
  • Approach: ELIXIR aggressively uses method invocations alongside variables, fields, and constants to construct expressive repair expressions for object-oriented programs.The technique is implemented as a generate-and-validate repair approach.
  • Approach: ELIXIR ranks candidate repairs using four features derived from surrounding code and, when available, the bug report.The features measure frequency, distance, contextual name similarity, and bug-report similarity.
  • Evaluation: 85% more bugs were correctly repaired in Defects4J, increasing from 14 to 26, while Bugs.jar increased by 57%, from 14 to 22.The evaluation compared ELIXIR with two baselines and five external techniques, including ACS, HD-Repair, NOPOL, PAR, and jGenProg.
  • Resources: Bugs.jar contributes a new dataset containing 1,158 bugs and patches to complement existing repair benchmarks.The dataset is made available to the research community.

II. MOTIVATION

The motivation study finds method invocations pervasive in Java code and bug fixes, exposing limitations in existing repair spaces. ELIXIR addresses these cases by generating rich expressions, ranking candidates, and validating only the highest-ranked patches.

  • Empirical motivation: 77% of studied one-line Java bug fixes involved method-invocation changes, either independently or within another construct.At least 80% of variable initializations, assignments, and return expressions also involved method invocations.
  • Limits of prior repair: Existing Java repair tools manipulate method invocations through restricted schemas, limiting synthesis of substantially new calls and complex call transformations.The restrictions help avoid combinatorial growth in the repair search space.
  • Motivating examples: LANG-538 requires inserting a new method invocation, a repair outside current tools’ spaces; ELIXIR synthesizes 836 valid method invocations for the location.The example illustrates why brute-force validation becomes impractical.
  • Motivating examples: LANG-304 replaces an invocation’s object with another invocation returning a compatible List rather than the original Set, a transformation excluded by current tools.The patch also cannot be copied verbatim from elsewhere in the program.
  • ELIXIR workflow: ELIXIR extracts in-scope objects, variables, and literals, builds valid method-invocation and field-access expressions, and plugs them into transformation schemas.These expressions serve as building blocks for candidate patches.
  • ELIXIR workflow: ELIXIR ranks the large candidate set with a machine-learned model and validates only the top few; for LANG-538, the correct patch ranked 7th of 836.Ranking makes test-suite validation feasible for the motivating example.

III. ELIXIR

ELIXIR localizes likely buggy statements, generates candidate patches from transformation schemas and repair-expressions, ranks candidates with a learned model, and validates them against the test suite until a plausible patch is found.

  • ELIXIR takes a buggy program, a test suite, and optionally a bug report, then processes suspicious statements until finding a plausible patch.A plausible patch passes all test cases, although it may remain incorrect when the test suite is incomplete.
  • Candidate patches are generated by plugging repair-expressions into program transformation schemas for each potential repair location.
  • ELIXIR ranks candidate patches with a machine-learned model and validates the top N candidates in descending rank order.
  • Ochiai instruments the program at statement level, computes suspiciousness from test spectra, and ranks statements by descending suspiciousness.

1) Program Transformation Schemas:

ELIXIR defines transformation schemas covering type changes, expression and guard modifications, Boolean changes, and method-invocation replacement or insertion.

  • Program Transformation Schemas: ELIXIR applies transformation schemas in a fixed order, beginning with widening a variable declaration’s type.
  • Program Transformation Schemas: Null-pointer and range-checking schemas add guards to prevent null accesses, out-of-range array accesses, or invalid collection accesses.
  • Program Transformation Schemas: Boolean-expression schemas mutate infix operators or add and remove predicates from Boolean conditions and return statements.
  • Program Transformation Schemas: The method-invocation schema replaces objects, method names, arguments, or complete invocations with compatible expressions or synthesized invocations.
  • Program Transformation Schemas: The new insertion schema synthesizes method invocations and inserts them within expressions or as complete statements.

2) Synthesis of Repair-Expressions:

ELIXIR constructs a rich pool of repair-expressions, uses them to instantiate transformation schemas, and ranks the resulting concrete patches to manage the enlarged search space.

  • Synthesis of Repair-Expressions: ELIXIR uses a rich repair-expression set that emphasizes method invocations and object accesses for fixing real OO-program bugs.
  • Synthesis of Repair-Expressions: For each repair location, ELIXIR extracts in-scope locals, literals, relevant fields, and callable method signatures to form repair-expressions.
  • Synthesis of Repair-Expressions: Extracted variables, literals, fields, and concrete method invocations form the repair-expression pool used to instantiate candidate patches.
  • Synthesis of Repair-Expressions: ELIXIR ranks candidates because valid patches can be numerous, using program context and bug-report clues in a logistic-regression relevance model.

1) Selection of Feature Set and Calculation of Feature Scores:

ELIXIR scores repair-expressions using distance, contextual similarity, contextual frequency, and bug-report similarity, computing element-level features before aggregating them at patch level.

  • Selection of Feature Set and Calculation of Feature Scores: ELIXIR selects four features: distance, contextual similarity, frequency in the context, and bug-report similarity.
  • Selection of Feature Set and Calculation of Feature Scores: Feature scores are computed for new repair-expressions at element level and then aggregated to represent patch-level features.
  • Selection of Feature Set and Calculation of Feature Scores: Distance favors repair-expressions composed of elements located closer to the repair site, averaging element scores for multi-element expressions.
  • Selection of Feature Set and Calculation of Feature Scores: Contextual similarity compares tokenized repair-expression identifiers with tokenized identifiers from the surrounding code using Jaccard similarity.
  • Selection of Feature Set and Calculation of Feature Scores: Contextual frequency treats repeated use as potentially relevant but depends on element type, with training-data analysis distinguishing variables or objects from method names.
  • Selection of Feature Set and Calculation of Feature Scores: Bug-report similarity uses overlap between bug-report information and repair-related program information to prioritize expressions.

2) Logistic Regression Model for Ranking:

ELIXIR ranks candidate patches by combining four contextual feature scores with learned logistic-regression weights and converting the aggregate into a relevance probability.

  • ELIXIR aggregates distance, context similarity, bug-report similarity, and frequency scores using a learned weighted sum.The weights are α, β, γ, and ζ, learned from a training dataset.
  • The model estimates each candidate patch’s probability of relevance to the program context using logistic regression.The candidate patch is represented by the feature vector [Sdist, Scon, Sbr, Sfreq].
  • For binomial classification, a relevant candidate patch is labeled y=1 and an irrelevant patch y=0.The likelihood follows a Bernoulli distribution.

A. Implementation

ELIXIR is implemented within the FLAiR repair framework and evaluated using Defects4J and the newly created Bugs.jar dataset.

  • A. Implementation: ELIXIR runs on FLAiR, which provides bug localization, transformation schemas, in-memory compilation, test execution, and runtime monitoring.FLAiR is implemented in Java and uses existing libraries where possible.
  • A. Implementation: The ELIXIR-Baseline retains ELIXIR’s transformation schemas but uses repair expressions modeled on existing tools.This baseline isolates the contribution of ELIXIR’s richer repair-expression set.
  • A. Implementation: ELIXIR-NoML retains ELIXIR’s schemas and expressions but randomly selects N patches instead of using machine learning.This baseline tests the contribution of the ranking model.
  • A. Implementation: ELIXIR is evaluated on Defects4J and Bugs.jar, a new dataset created by the authors.Bugs.jar was created both to provide training data and to support evaluation on a dataset distinct from Defects4J.
  • A. Implementation: Each Bugs.jar bug includes buggy source code, a test suite with failing and passing tests, a developer patch, and an associated bug report.The dataset targets real-world relevance, diversity, reproducibility, and automatability across Apache projects.

C. Research Questions

The evaluation examines ELIXIR’s effectiveness, the contributions of its repair expressions and ranking model, the usefulness of its features, and cross-dataset performance.

  • C. Research Questions: The study asks how ELIXIR compares with state-of-the-art repair techniques on Defects4J.
  • C. Research Questions: It separately investigates the contributions of ELIXIR’s repair expressions, ranking and selection model, and individual features.
  • C. Research Questions: It tests whether ELIXIR’s Defects4J performance is also reflected on Bugs.jar.
  • C. Research Questions: Training uses one-line Bugs.jar fixes, extracting positive and negative repair expressions with their feature vectors.
  • C. Research Questions: The balanced training data contains 1,580 points after replicating positives and sampling similar negatives.
  • C. Research Questions: Training and testing subjects are mutually exclusive, with standard 10-fold cross-validation used to train ELIXIR.
  • C. Research Questions: Patches are classified as correct when manual examination finds them semantically equivalent to the developer patch.Two authors independently assessed patches and resolved disagreements through discussion.
  • C. Research Questions: The experiment uses two CPU cores, 4GB memory per instance, Ubuntu 14.04 LTS, and Java 7.

V. EXPERIMENTAL RESULTS

ELIXIR repairs more Defects4J bugs than the compared techniques, with method-invocation changes especially productive; its rich expressions and learned selection both contribute to performance.

  • A. RQ1: Comparison with state-of-the-art approaches: 26 correct patches make ELIXIR the strongest Defects4J result among the compared techniques, evaluated on 82 single-hunk bugs.ACS produced 18 correct patches, while other tools produced 10 or fewer; HD-Repair’s fair first-ranked comparison is 10.
  • A. RQ1: Comparison with state-of-the-art approaches: Only 4 patches overlap between ELIXIR and ACS, consistent with ELIXIR targeting method-invocation bugs and ACS targeting condition synthesis.The authors identify combining the tools as an interesting but out-of-scope direction.
  • A. RQ1: Comparison with state-of-the-art approaches: Changing method invocations comprehensively generated 12 correct and 6 incorrect patches, the most effective schema category.Boolean-expression changes generated 6 correct and 8 incorrect patches, while method-invocation insertion generated 3 correct and no incorrect patches.
  • B. RQ2: Contribution of ELIXIR’s Repair-Expressions and Ranking and Selection: ELIXIR-Baseline fixed 14 bugs using ELIXIR’s transformation schemas with existing tools’ repair expressions.It produced no correct patches for the motivating examples, supporting the contribution of richer repair expressions.
  • B. RQ2: Contribution of ELIXIR’s Repair-Expressions and Ranking and Selection: ELIXIR-NoML fixed 13 bugs versus ELIXIR-Baseline’s 14 when expanded expressions were randomly selected.The expanded repair-expression space had a median size 30 times larger than the basic space.
  • B. RQ2: Contribution of ELIXIR’s Repair-Expressions and Ranking and Selection: Machine-learned selection preserved all ELIXIR-Baseline fixes and added 12 more correct bugs.

C. RQ3: Effect of Each Feature in Ranking and Selection

ELIXIR’s four ranking features each contribute to selecting correct patches, while Bugs.jar results show improved effectiveness over its baseline despite dataset and validation constraints.

  • Each of ELIXIR’s four features contributed to ranking correct patches; removing any feature reduced the number of correct patches.Distance was least influential, while bug report and frequency were the dominant features.
  • 234 repair-expressions could replace each of a, b, and Float.NAN in the MATH-482 location, making frequency important for selecting the correct patch.The frequent variable a received a high score and led ELIXIR to generate the correct patch.
  • 944 valid method invocations were synthesized for the LANG-477 repair location, with bug-report terms next and pos ranking the correct insertion third.The inserted method invocation contained no element from the local context.
  • 22 Bugs.jar bugs received correct patches from ELIXIR, compared with 14 from ELIXIR-Baseline, including four method-invocation insertions and two method-invocation changes.The experiment randomly sampled 127 bugs from seven subjects and excluded Log4J2 because of engineering issues.
  • ELIXIR’s Bugs.jar conclusions may not generalize beyond the evaluated datasets or Java application bugs, and correct-patch classification relied on manual analysis.The authors mitigated these threats through dataset construction procedures, patch inspection, and author reconciliation.

VII. RELATED WORK

Related repair techniques provide important contrasts: Java systems generally restrict method invocations, whereas ELIXIR expands their use and combines that expansion with machine-learned ranking.

  • GenProg, RSRepair, AE, and Relifix search repair mutations or specialized schemas, primarily for C programs.GenProg copies code snippets, RSRepair uses random search, AE prunes equivalent patches, and Relifix targets regression errors.
  • PAR, HD-Repair, and ACS target Java repair with templates, patch-frequency prioritization, or condition synthesis, but restrict method invocations to avoid search-space explosion.ELIXIR’s expanded and generalized use of method invocations is presented as its main contrast with these techniques.
  • SemFix, MintHint, DirectFix, and SearchRepair use oracle-based, statistical, minimal-repair, or semantic-search strategies, while NOPOL targets Java branch conditions with synthesized oracles.The cited oracle-based techniques primarily target C programs; NOPOL is the Java exception described.
  • Prophet uses a machine-learned model with over 3000 features and improves repair outcomes from 12 to 15 patches, whereas ELIXIR uses four features and improves from 14 to 26.ELIXIR also pairs machine learning with an expanded repair space incorporating method invocations in repair expressions.
  • ELIXIR’s evaluation on Defects4J and Bugs.jar reports significantly more correctly repaired bugs and out-performance of ACS, HD-Repair, NOPOL, PAR, and jGenProg.The conclusion characterizes this as effective searching of an enlarged repair space.
Loading 2112.10915v1…