PaperlayerView exact revision on arXiv

Source-linked AI summary

Sorting and Transforming Program Repair Ingredients via Deep Learning Code Similarities

Martin White, Michele Tufano, Matias Martinez, Martin Monperrus, Denys Poshyvanyk

arXiv:1707.04742v2cs.SE

TL;DR

Redundancy-based repair often reuses code without reasoning about which repair ingredients to select or how to adapt them. DeepRepair uses unsupervised deep-learning code similarities to prioritize ingredients and transform identifiers, evaluating these strategies on real Java bugs. It generally finds compilable ingredients faster than jGenProg and finds some otherwise unavailable patches, but does not significantly improve broader patch-generation effectiveness.

  • Problem

    Redundancy-based repair techniques often select repair ingredients randomly and apply them rigidly, limiting patches that require novel expressions or identifier adaptation.

  • Method

    DeepRepair uses unsupervised deep learning to sort code fragments by similarity and transform out-of-scope identifiers into similar in-scope identifiers.

  • Results

    DeepRepair generally finds compilable ingredients faster than jGenProg and finds patches unavailable to existing redundancy-based techniques, without significantly more patches or fewer test-adequate-patch attempts on average.

  • Takeaways & Limitations

    Code similarities can expand redundancy-based repair to patches that existing techniques cannot find, even without significantly increasing overall patch counts.

  • Takeaways & Limitations

    DeepRepair was not evaluated with optimal training settings for every program revision or project, and its random components can produce different patches across runs.

Abstract

from arXiv · show

In the field of automated program repair, the redundancy assumption claims large programs contain the seeds of their own repair. However, most redundancy-based program repair techniques do not reason about the repair ingredients---the code that is reused to craft a patch. We aim to reason about the repair ingredients by using code similarities to prioritize and transform statements in a codebase for patch generation. Our approach, DeepRepair, relies on deep learning to reason about code similarities. Code fragments at well-defined levels of granularity in a codebase can be sorted according to their similarity to suspicious elements (i.e., code elements that contain suspicious statements) and statements can be transformed by mapping out-of-scope identifiers to similar identifiers in scope. We examined these new search strategies for patch generation with respect to effectiveness from the viewpoint of a software maintainer. Our comparative experiments were executed on six open-source Java projects including 374 buggy program revisions and consisted of 19,949 trials spanning 2,616 days of computation time. DeepRepair's search strategy using code similarities generally found compilable ingredients faster than the baseline, jGenProg, but this improvement neither yielded test-adequate patches in fewer attempts (on average) nor found significantly more patches than the baseline. Although the patch counts were not statistically different, there were notable differences between the nature of DeepRepair patches and baseline patches. The results demonstrate that our learning-based approach finds patches that cannot be found by existing redundancy-based repair techniques.

I. INTRODUCTION

DeepRepair addresses the limited reasoning and rigid use of repair ingredients in redundancy-based repair by sorting and transforming them with deep-learning code similarities. Its evaluation found faster discovery of compilable ingredients, but no significant improvement in test-adequate patch attempts or patch counts over jGenProg.

  • Motivation: Redundancy-based repair reuses source code from the repository or other projects, but commonly harvests repair ingredients randomly without reasoning about optimal selection.This trial-and-error strategy can find patches, yet rigid ingredient application makes patches requiring novel expressions unattainable.
  • Approach: DeepRepair sorts code fragments by similarity to suspicious elements and transforms out-of-scope identifiers into similar identifiers that are in scope.It uses deep learning to represent source-code structure and lexical meaning without predefined features.
  • Evaluation: The evaluation assesses sorting, transforming, and their combination across different granularity and scope settings using metrics tailored to ingredient-selection strategies.The study evaluates these strategies against a baseline and examines which aspects contribute to repair effectiveness.
  • Contributions: DeepRepair provides a learning-based algorithm and publicly available Java implementation for selecting and adapting repair ingredients.The approach is implemented on top of Astor, a Java implementation of GenProg.
  • Results: 374 real Defects4J bugs were evaluated, and DeepRepair found patches unavailable to existing redundancy-based techniques.The experiments covered six open-source Java projects.

II. BACKGROUND AND RELATED WORK

Automated repair includes generate-and-validate techniques that reuse and mutate existing code and semantics-based techniques that synthesize code from program properties. DeepRepair builds on this landscape by using learned similarities at arbitrary granularities and by transforming identifiers, while addressing limitations of prior similarity-based and learning-based approaches.

  • Automated Program Repair: Generate-and-validate repair reuses and rearranges existing code, whereas semantics-based repair synthesizes code with specified properties.Generate-and-validate methods operate at coarse granularity, while semantics-based methods work on expressions and variables.
  • Related Work: SearchRepair combines symbolic search with semantic patch generation, but has been demonstrated only on small programs and depends on input-output examples.DeepRepair instead targets real software systems and automatically learns features for distinguishing code fragments.
  • Similarity-Based Repair: Prior code-similarity repair used fixed four-, six-, or eight-line regions and token-sequence similarity, whereas DeepRepair uses arbitrary granularities and learning-based clone detection.The comparison also differs in evaluation scale: the prior study used 24 bug-fix commits, while DeepRepair uses 374 revisions.
  • Learning-Based Repair: Representation learning automatically encodes code fragments for similarity detection, while Prophet uses explicitly designed features to rank candidate repairs.DeepRepair also maps out-of-scope variables to variables in scope at the modification point.
  • Redundancy Assumption: Temporal redundancy studies found most redundancy localized in the same file, and commit reconstruction studies found grafts were mostly single-line micro-clones.DeepRepair uses micro-clones to compute representations for larger code fragments and prioritize statements.

III. TECHNICAL APPROACH

DeepRepair builds a three-phase pipeline that recognizes code at multiple granularities, learns representations and similarities, and uses them to guide repair decisions. Its learning process combines language-model embeddings, recursive autoencoding, and identifier clustering.

  • III. TECHNICAL APPROACH: The pipeline comprises recognition, learning, and repair phases that produce code representations, encoders, and repair decisions.Recognition consumes source code and produces training data; learning produces encoders; repair uses them to query and transform code fragments.
  • A. Language Recognition Phase: The recognition phase parses source files into an AST or equivalent model, enabling queries over files, classes, and methods.For the Math library, the model contains 459 files, 661 classes, and 4,983 methods.
  • A. Language Recognition Phase: DeepRepair builds file-, class-, and method-level corpora by printing syntax-tree terminal symbols and storing identifiers for each code element.These corpora support similarity mining at multiple granularities, including classes, methods, and lexical elements.
  • A. Language Recognition Phase: Corpus normalization replaces literal tokens with generic symbols representing their types before learning begins.For example, floating-point literals in the Math corpus are mapped to a generic floating-point symbol.
  • B. Machine Learning Phase: A neural language model learns embeddings from term order, placing terms used in similar ways near one another in feature space.These embeddings initialize the next learning stage.
  • B. Machine Learning Phase: A recursive autoencoder encodes streams of embeddings by repeatedly selecting the adjacent pair with the lowest reconstruction error.The procedure recursively replaces the selected pair with its encoding and then optimizes the error through backpropagation through structure.
  • B. Machine Learning Phase: The learned representations support similarity comparisons among classes, methods, and identifiers without manually specified features.Identifier embeddings are clustered so that identifiers used in similar program contexts can be grouped together.
  • C. Program Repair Phase: During repair, clustered identifiers constrain transformations: an out-of-scope variable may be replaced only by an in-scope identifier from the same cluster.This cluster-based criterion operationalizes decisions about whether ingredients should be transformed.

C. Program Repair Phase

The program repair phase follows a generate-and-validate loop while prioritizing ingredients from similar code and transforming identifiers to make otherwise uncompilable ingredients fit the modification point.

  • C. Program Repair Phase: DeepRepair begins with fault localization, applies repair operators at suspicious statements, recompiles changed classes, and validates candidate patches.The process follows a generate-and-validate repair loop similar to GenProg.
  • C. Program Repair Phase: DeepRepair uses statement addition and replacement, omitting statement removal because it generates too many incorrect patches.Ingredients are drawn from local, package, and global pools according to their location relative to the modification point.
  • C. Program Repair Phase: Ingredient sorting prioritizes statements from methods or classes similar to the code containing the modification point.Statements are extracted from similar methods in order and placed into a first-in-first-out ingredient queue.
  • C. Program Repair Phase: An ingredient is compilable when all its variable accesses are in scope at the modification point.DeepRepair therefore distinguishes raw ingredients from ingredients that fit the target context.
  • C. Program Repair Phase: DeepRepair transforms out-of-scope identifiers using in-scope identifiers from the same learned cluster, expanding the generated patch space beyond raw jGenProg ingredients.The Math-63 example replaces out-of-scope eps with in-scope SAFE_MIN, yielding a correct patch.

IV. EMPIRICAL VALIDATION

The empirical validation defines a comparative study of DeepRepair and a baseline by specifying research questions, treatments, experimental units, responses, and data-collection procedures.

  • IV. EMPIRICAL VALIDATION: The study defines research questions, its empirical goal, an experimental baseline configuration, and hypotheses.These elements are specified in the empirical-study plan.
  • IV. EMPIRICAL VALIDATION: The comparative experiments are characterized by treatments, experimental units, and measured responses.Experimental units are the objects to which the treatments are applied.
  • IV. EMPIRICAL VALIDATION: The plan concludes by specifying data-collection procedures and the analysis procedure.These procedures follow the study design description.

A. Experiment Scope and Plan

The study compares DeepRepair ingredient-search strategies with jGenProg across multiple research questions, using patch counts, ingredient attempts, and patch quality as outcomes. The experiments evaluate sorting, transformation, and combined strategies across scopes and granularities.

  • Research questions: The experiments addressed whether deep-learning code similarities improve fix-space navigation, ingredient transformation, and overall repair effectiveness.The research questions compare these strategies with uniform random search and default ingredient application.
  • Evaluation setting: The experiments were conducted from a software-maintainer perspective using six open-source Java projects, reproducible bugs, and JUnit tests.The study also assessed patch correctness through human evaluation.
  • Baseline: The baseline used uniform random statement selection with caching and default variable-access matching.The baseline prevented repeated modification instances and matched ingredient accesses by names and types.
  • Measures: The study measured test-adequate patch counts and the number of ingredients attempted.An attempt was defined as a request sent to the fix space for an ingredient.
  • Experimental factors: The design varied ingredient search strategy, scope, clone granularity, and variable-resolution algorithm while fixing Java, fault-localization threshold, and candidate limits.The fixed threshold was 0.1 and the maximum number of suspicious candidates was 1,000.

B. Data Collection Procedure

DeepRepair collected data by modeling buggy Java revisions, learning code representations, computing similarities, and running repair trials across multiple scopes and granularities. The dataset comprised 374 buggy revisions, with one documented modeling failure for Mockito bugs 1–21.

  • Program modeling: Spoon built a source-code model for each buggy program revision before recognition and similarity learning.The model supported later queries over program elements.
  • Program modeling: Program processors queried files, types, and executables at three levels of granularity.Types included classes and interfaces, while executables included methods and constructors; only top-level elements were queried.
  • Representation learning: word2vec initialized embeddings for revision-specific recursive autoencoders trained on normalized file-level corpora.The language models used skip-gram embeddings selected for fast training and initialization.
  • Similarity computation: The trained encoders represented types and executables, whose pairwise Euclidean distances supplied code similarities.Term embeddings were additionally clustered with k-means, with k selected using simulated annealing.
  • Repair trials: The repair evaluation covered six open-source Java projects and 374 Defects4J buggy program revisions.Each trial evolved one program variant for three hours using insertion and replacement operators, excluding removal.
  • Repair trials: Astor with GZoltar computed Ochiai suspiciousness values, and trials varied local, package, and global ingredient scopes.Local scope used classes containing suspicious statements, while broader scopes expanded the ingredient pool.
  • Data boundary: Spoon models could not be built for Mockito bugs 1–21, likely because of missing or incompatible dependencies.

C. Analysis Procedure

The analysis compared repair strategies statistically across patch productivity, search attempts, ingredient transformation, and patch correctness. Non-parametric tests with Bonferroni correction were used for the principal comparisons.

  • RQ1: Wilcoxon tests with Bonferroni correction compared test-adequate patch counts between jGenProg and code-similarity strategies.The comparisons covered executable- and type-level strategies across scopes.
  • RQ1: The analysis also measured the percentage of DeepRepair patches absent from the jGenProg patch set.This set-difference measure was |D \ J| / |D|, where D and J denote DeepRepair and jGenProg patches.
  • RQ1: Mann-Whitney tests with Bonferroni correction compared attempts needed to generate test-adequate patches.The attempt analysis complemented the patch-count comparison.
  • RQ2–RQ3: RQ2 compared jGenProg with embedding-based ingredient transformation, while RQ3 compared jGenProg with code similarity plus transformation.These comparisons assessed patch counts, patch-set differences, and attempts.
  • RQ4: Three judges evaluated a random sample of 30 patches for correctness using correct, incorrect, or unknown ratings.The sample contained 15 jGenProg and 15 DeepRepair patches, with judges also reporting confidence.

V. EMPIRICAL RESULTS

Across 19,949 completed trials, DeepRepair generally found compilable ingredients faster than jGenProg but did not significantly improve patch counts or attempts. Nevertheless, DeepRepair produced alternative patches and unlocked bugs unavailable to the baseline.

  • Overall results: 19,949 completed trials produced 19,832 distinct test-adequate patch instances after 247 trials were killed.The completed trials consumed 2,616 days of computation time and attempted 406,443,249 ingredients.
  • RQ1: Code-similarity sorting generally reduced attempts to find compilable ingredients but did not reduce attempts to find test-adequate patches on average.The study reported no significant increase in patch counts relative to the baseline.
  • Overall results: The results show notable differences between DeepRepair and jGenProg patches despite no significant patch-count advantage.This conclusion is stated as the principal comparison between the learning-based search strategy and the baseline.

B. RQ2 (Analysis of RE Strategy)

DeepRepair’s similarity-based strategies found compilable ingredients faster than jGenProg, but did not produce test-adequate patches in fewer attempts or significantly more patches. Despite similar patch counts, DeepRepair generated complementary patches, including transformed ingredients and novel expressions.

  • 49 bugs received test-adequate patches under treatment RE.
  • 53%, 3%, and 53% of DeepRepair’s Chart, Lang, and Math patches were not found by jGenProg.
  • DeepRepair patches differed from jGenProg patches, with complementary patch sets despite statistically indistinguishable patch counts.
  • 42 and 38 bugs received test-adequate patches under treatments EE and TE, respectively.
  • 99%, 28%, and 51% of DeepRepair’s Chart, Lang, and Math patches under EE or TE were not found by jGenProg.
  • DeepRepair generally found compilable ingredients faster than jGenProg, but not test-adequate patches in fewer attempts or significantly more patches.
  • Five DeepRepair patches and five jGenProg patches were judged correct, with no significant readability difference reported.
  • DeepRepair transformed out-of-scope identifiers and generated novel conditional expressions, producing both semantically equivalent and test-passing patches.

VI. THREATS TO VALIDITY

The evaluation has internal, external, construct, and conclusion-validity threats. These include non-optimal learning configurations, limited benchmark representativeness, exclusion of multiple-fault revisions, possible flaky tests, and randomness across runs.

  • DeepRepair’s learning configurations were not necessarily optimal for each revision or project, and configuration choices may confound results.
  • The 374 buggy revisions from six Defects4J systems may not represent the actual differences between DeepRepair and jGenProg.
  • The evaluation excludes program revisions with multiple faults, limiting its scope to single-fault settings.
  • Potentially undetected flaky tests could affect both DeepRepair and jGenProg.
  • Because both approaches contain random components, different runs could produce different patches.
  • The study used 19,949 trials spanning 2,616 days of computation, but manually evaluated only a random subset of generated patches.

VII. CONCLUSION

DeepRepair selects and transforms repair ingredients using deep learning within a generate-and-validate repair loop. It did not significantly improve effectiveness by number of attempts, but generated patches unavailable to existing redundancy-based techniques.

  • DeepRepair uses unsupervised deep learning to select ingredients from similar methods or classes and transform identifiers for compilability.The approach expands the fix space by mapping identifiers according to similarity.
  • DeepRepair did not significantly improve effectiveness when measured by number of attempts.
  • DeepRepair generated many patches that existing redundancy-based repair techniques cannot generate.
Loading 1707.04742v2…