PaperlayerView exact revision on arXiv

Source-linked AI summary

Mining Software Repair Models for Reasoning on the Search Space of Automated Program Fixing

Matias Martinez, Martin Monperrus

arXiv:1311.3414v1cs.SE

TL;DR

Automated repair needs evidence about which source-code changes resemble real bug fixes and how those changes should structure the repair search space. The paper mines repository transactions with fine-grained AST differencing, assigns empirical probabilities to repair actions, and shows that repair-model choices produce materially different search behavior. Its scope is constrained by assumptions involved in selecting transactions representative of bug fixes.

  • Problem

    The paper addresses the limited empirical understanding of what real bug fixes contain and how that knowledge should inform automated program-repair search spaces.

  • Method

    The paper mines AST-level repair actions from bug-fix transactions, learns probability distributions from repositories, and uses them to reason mathematically about automated-repair search spaces.

  • Results

    Not all probabilistic repair models are equivalent: transaction selection, repair-model granularity, and probability distributions can substantially change repair-search behavior.

  • Takeaways & Limitations

    Empirical knowledge from past bug fixes can support generic repair models and reasoning about how efficiently automated repair navigates its search space.

  • Takeaways & Limitations

    Repair-space probabilities depend on how bug-fix transactions are selected, because commit-text filtering assumes reliable repository data while small-transaction filtering may omit larger fixes.

Abstract

from arXiv · show

This paper is about understanding the nature of bug fixing by analyzing thousands of bug fix transactions of software repositories. It then places this learned knowledge in the context of automated program repair. We give extensive empirical results on the nature of human bug fixes at a large scale and a fine granularity with abstract syntax tree differencing. We set up mathematical reasoning on the search space of automated repair and the time to navigate through it. By applying our method on 14 repositories of Java software and 89,993 versioning transactions, we show that not all probabilistic repair models are equivalent.

I. INTRODUCTION

The paper mines developer bug fixes to characterize repair actions and uses probabilistic models to reason about automated-repair search spaces. It argues that repair-model granularity and probability-estimation heuristics substantially affect search navigation.

  • Automated program repair generates source-code patches under varied input assumptions and repair strategies, including genetic algorithms and satisfiability models.
  • Repair models are sets of generic repair actions, whereas concrete repairs instantiate those actions with program-specific data.For example, adding a method call is an action, while adding x.foo() is a concrete repair.
  • The paper mines AST-level repair actions from bug-fixing transactions in software repositories using abstract syntax tree differencing.Examples include adding method calls, changing conditions, and deleting catch blocks.
  • Probability distributions are learned from repositories and are reported to be independent of application domain.
  • Probabilistic repair models support theoretical reasoning about navigation time, with likely-correct repairs concentrated in parts of the repair search space.
  • The analysis covers 89,993 transactions from 14 open-source Java projects and represents changes at a granularity of 173 AST-level repair actions.

A. Dataset

The dataset and representation combine 14 Java repositories with fine-grained AST differencing. Two change models encode transactions at different granularities, enabling frequency-based analysis of repair actions.

  • Dataset: CVS-Vintage contains 14 open-source Java repositories spanning desktop applications, servers, libraries, and compilation software.
  • AST differencing: ChangeDistiller is a fine-grained Java AST differencer with 41 source-change types, including statement insertion and conditional changes.
  • AST differencing: Each AST change is represented as a change type and entity type tuple, while formatting-only edits produce no AST-level change.
  • Change models: CT contains 41 change-type features, whereas CTET refines them into 173 valid change-type/entity-type combinations.
  • Change models: The paper treats CT and CTET as different-granularity descriptions rather than declaring one universally superior.
  • Measures: For each action, α_i counts occurrences and χ_i gives its relative frequency among all changes.χ_i = α_i / Σ α_i.

E. Empirical Results

AST-level changes are highly uneven in frequency, and their rankings are broadly consistent across projects. The results also show that finer granularity spreads probability mass across more actions.

  • Overall frequencies: 1,196,385 AST-level changes were extracted from 62,179 Java transactions; statement insertion, deletion, and update account for 28%, 23%, and 14% in CT.
  • CTET frequencies: In CTET, inserting a method invocation as a statement is the most common change, with a relative frequency of 6.9%.
  • Granularity: Statement insertion is decomposed into method-invocation insertion at 6.9%, if-conditional insertion at 6.6%, and new-variable insertion at 4.6%.
  • Granularity: Finer-grained CTET distributions have lower individual frequencies and less concentrated probability mass than CT.
  • Project independence: 75% of project pairs have CT Spearman correlations above 0.852, and all reported CT correlations exceed 0.75.
  • Project independence: CTET correlations are all above 0.301, the critical value at α = 0.01 for 173-feature vectors, indicating statistically significant project-independent action importance.

G. Recapitulation

The study provides large-scale, fine-grained evidence about source-code changes and examines how transaction selection affects repair-action probability distributions. Its results also identify validity boundaries involving project, language, and transaction-label assumptions.

  • The probability distribution of change actions is highly unbalanced, with a small set of actions dominating observed changes.
  • 62,179 transactions support empirical importance estimates for 173 source-code change actions at previously unpublished scale and granularity.
  • The findings may not generalize beyond the 14-project Java dataset, and implementation defects could also threaten validity.
  • Bug-fix probability estimates require selecting representative transaction bags rather than relying only on commit-message classification.The stated goal is approximating repair-action probabilities, not maximizing classification precision or recall.
  • The BFP bag selects transactions containing “bug,” “fix,” or “patch,” but assumes developers use recognizable repair-related syntax in commit messages.The paper notes that this behavioral assumption is not generally reliable in practice.
  • The 1-SC bag assumes transactions containing one AST change are likely to be bug fixes and unlikely to introduce new features.

C. Do Small Versioning Transactions Fix Bugs?

A manual study tested whether transactions containing one AST change are predominantly bug fixes. Three-rater inspection found substantial agreement and supported using the 1-SC transaction bag to estimate repair-action probabilities.

  • 144 transactions were sampled from 6,953 one-AST-change transactions across 16 open-source projects.
  • Three raters independently judged whether each transaction represented a bug-fix change using diffs, AST changes, and commit messages.
  • 74 of 144 transactions, or 51.8%, received full agreement as bug fixes.
  • At least two of three raters classified 95 of 144 transactions, or 66%, as bug fixes.
  • Adding a method was the most common fully agreed non-bug-fix case, although polymorphism sometimes made the same change a bug fix.
  • The overall agreement was 0.77, indicating substantial agreement close to almost perfect agreement on the reported scale.
  • The chance-adjusted agreement κ was 0.517, and the null hypothesis that observed agreement was due to chance was rejected.

6) Conclusion:

The paper converts mined change models into probabilistic repair models and compares transaction-bag definitions. The resulting distributions are strongly concentrated, yet action rankings and probabilities vary with the chosen bag.

  • A repair model is a subset of a change model whose feature probabilities are interpreted from a bug-fixing perspective.
  • The comparison evaluates ALL, BFP, and 1-SC, 5-SC, 10-SC, and 20-SC transaction bags for repair models CT and CTET.
  • The top 10 repair actions account for more than 92% of cumulative probability, while individual action probabilities range from above 30% to 0.000x%.
  • Statement insertion ranks first for ALL but fourth for 1-SC, with probability changing from 29% to 12%.
  • Even similar action rankings can hide distribution changes: χStmt_Upd is 29% for ALL and 33% for 20-SC.
  • ALL and BFP produce close probability distributions, suggesting BFP may behave like a random subset of ALL transactions.
  • Different definitions of repair transactions therefore yield different probability distributions over a repair model.

C. Discussion

The discussion shows that transaction-selection heuristics produce different repair-action distributions, while transaction size can identify distinctive fix transactions and support guided repair-space navigation.

  • C. Discussion: Transaction-selection heuristics can yield substantially different repair-action distributions, so repair-model topology depends on how fix transactions are selected.The paper notes that commit-text selection favors actual repairs but assumes repository metadata is reliable, whereas small-transaction selection may omit larger fixes and distort probabilities.
  • C. Discussion: 0.68 is the Spearman correlation between ALL and 1-SC, indicating that 1-SC produces a differently ordered repair-action distribution.By contrast, the ALL–BFP correlation is 0.99, showing near-identical frequency ordering for those bags.
  • C. Discussion: 15% to 7%: the probability of updating a method invocation decreases from 1-SC transactions to all transactions.For transactions with one AST change, probabilities are more uneven, while transactions with more than 10 AST changes have top-change probabilities below 0.9%.
  • C. Discussion: Probabilistic repair models offer a first step toward automated repair approaches that imitate how human developers fix programs.The proposed direction uses repository-derived probabilities to explore likely repair actions earlier.
  • C. Discussion: The repair search space combines fault localization, repair shaping, and concrete synthesis, and the paper concentrates on navigating the shaping component.Repair shapes are unordered combinations of repair actions, while synthesis instantiates those actions with concrete statements and values.

B. Mathematical Analysis Over Repair Models

The mathematical analysis models repair-shape discovery by sampling repair actions from a probability distribution, yielding an estimated median number of attempts under an independence assumption.

  • B. Mathematical Analysis Over Repair Models: A repair shape of size n is modeled by drawing n repair actions according to their probability distribution, prioritizing frequent actions.The model assumes repair actions are independent when deriving the exact median attempt count.
  • B. Mathematical Analysis Over Repair Models: The repair shape may contain repeated instances of the same repair action, so its action counts affect the navigation analysis.For example, a bug fix can contain several statement insertions.
  • B. Mathematical Analysis Over Repair Models: 12 attempts: Equation 1 estimates the average attempts needed in repair model CT to find the correct shape for an Eclipse bug involving two inserted statements.The example concerns revision 1.2 of Eclipse’s CheckedTreeSelectionDialog.
  • B. Mathematical Analysis Over Repair Models: A repair shape is not a complete fix, but its navigation time enables comparisons between probability distributions over repair models.The analysis therefore evaluates shaping rather than full patch correctness.

C. Comparing Probability Distributions Over Repair Actions From Versioning History

The paper compares repository-learned probability distributions by training on selected transactions and measuring how quickly they recover observed repair shapes, using cross-validation across 14 repositories.

  • C. Comparing Probability Distributions Over Repair Actions From Versioning History: A probability distribution P guides search by exploring likely repair shapes first, making its quality central to search-space traversal time.The comparison asks how distributions should be learned and how their shaping performance should be evaluated.
  • C. Comparing Probability Distributions Over Repair Actions From Versioning History: The evaluation selects bug-fix transactions, extracts repair shapes, and computes each shape’s average discovery time under a trained repair model.The output is the median number of attempts required to find good repair shapes.
  • C. Comparing Probability Distributions Over Repair Actions From Versioning History: For small transactions, the CT model finds the correct repair shape in fewer than 100 attempts.Table V reports median attempts and the numbers of tested fix transactions for each project and transaction size.
  • C. Comparing Probability Distributions Over Repair Actions From Versioning History: Cross-validation separates transactions used to estimate probability distributions from those used to measure repair-shape discovery time, reducing overfitting risk.The evaluation also instantiates the comparison for different repair-shape sizes measured by AST changes.
  • C. Comparing Probability Distributions Over Repair Actions From Versioning History: 14 repositories are evaluated by holding one project out for testing while calibrating the model on the other 13, repeating the process for every project.This cross-project design predicts repair shapes in one repository from data learned on different software projects.

E. Empirical Results

Empirical results show that repair-model granularity and probability-estimation heuristics strongly affect how quickly likely repair shapes can be found. Coarser CT supports larger findable shapes and generally faster navigation than finer CTET, but with a larger synthesis space.

  • Experimental setup: CT contains 41 repair actions, whereas CTET contains 173, and both models were evaluated with multiple transaction-selection heuristics.The heuristics included ALL, 1-SC, 5-SC, 10-SC, and 20-SC, alongside a commit-text heuristic and a uniform baseline.
  • Experimental setup: 23,048 bug-fix transactions with fewer than 8 AST changes were used to evaluate the number of attempts needed to identify correct repair shapes.The dataset includes transactions of varying AST-change sizes across the 14 projects.
  • Generalization: Cross-validation showed similar performance across the 14 project-held-out runs, indicating that distributions learned from other projects predicted repair shapes for each held-out project.The authors state that this supports applying the approach to new projects using distributions mined from the dataset.
  • Heuristics for CT: For CT, 5-SC performed best below 5 repair actions, while 20-SC performed best for larger transactions; EQP and 1-SC could produce exploding repair times.For small shapes, 1-SC was also best at size 1, but it was inefficient beyond two AST-level changes.
  • CT versus CTET: CTET found correct repair shapes only through 4 AST changes, whereas CT could find shapes through 7 changes in a finite number of attempts.The finer-grained CTET model also had substantially larger average repair times.
  • CT versus CTET: CT found likely repair shapes in fewer than 5,000 attempts for large repairs, while CTET reduced synthesis-space size but made likely-shape concentration harder.The results describe a trade-off between abstract repair actions that enlarge synthesis and concrete actions that hamper probabilistic shaping.

VI. ACTIONABLE GUIDELINES FOR AUTOMATED SOFTWARE REPAIR

The paper turns its empirical and theoretical findings into guidelines for probabilistic automated repair. It recommends learning or tuning non-uniform action probabilities while accounting for the trade-off between shaping and synthesis.

  • Guidelines: Automated repair systems should assign probability distributions to repair actions because action importance varies and uniform distributions are extremely suboptimal.The distribution can be learned from historical repairs or tuned incrementally.
  • Guidelines: More precise repair shapes substantially increase shaping time: size-3 fixes require approximately 150 attempts in CT versus around 4,000 in CTET.The latter represents more than a ten-fold increase for the same shape size.
  • Theoretical limits: Repair shapes larger than 10 actions in CT and larger than 5 actions in CTET are not found in finite time under the analyzed models.Because a repair shape abstracts a concrete fix, failure to find the abstraction prevents finding the corresponding concrete fix.
  • Theoretical limits: The methodology and equation are repair-action agnostic and can analyze the size of fixes that are findable by a repair process.The paper applies these guidelines in a simplified GenProg case study.

D. Case Study: Reasoning on GenProg within our Probabilistic Framework

The GenProg case study applies the probabilistic framework to concrete insertion, deletion, and swap repairs in an infinite-loop bug. Favoring empirically more likely insertion actions reduces the predicted logical repair time.

  • Repair model: The studied GenProg model uses three repair actions: inserting, deleting, and swapping statements.The target bug is fixed by inserting a return statement into the Euclidean GCD program.
  • Shaping and synthesis: The GCD program has 13 insertion places and 8 AST statements, yielding synthesis spaces based on insertion, deletion, and swap combinations.The case study approximates insertion possibilities as nplace ∗ nast, deletion possibilities as nast, and swap possibilities as (nast)^2.
  • Probabilistic repair: Under uniform action probabilities, the concrete fix requires 219 predicted attempts, while favoring insertion reduces logical time to 185, 160, 144, or 120 attempts across tested distributions.The strongest listed reduction uses pinsert = .60, pdelete = .20, and pswap = .20.
  • Probabilistic repair: Favoring insertion over deletion decreases the logical time needed to find the repair.This matches the empirical observation that insertion is more likely than deletion in real bug fixes.
  • Fault localization: Fault localization that reduces candidate locations from 13 to 7 lowers the predicted logical time from 219 to 118 runs under a uniform distribution.The case study also reports that larger programs and more candidate locations sharply increase repair time.
  • Caveats: Static typing and runtime semantics restrict where nodes can be inserted, so the calculated runs overestimate the concrete search but preserve the relevant order-of-magnitude comparison.The simulation also omits fitness functions and therefore represents guided random search rather than full evolutionary repair.

VII. RELATED WORK

The paper differs from prior empirical mining and automated-repair work by automatically extracting fine-grained AST repair actions and analyzing their probabilistic search behavior. It complements manual templates, project-specific mining, and repair tools rather than directly fixing concrete bugs.

  • Mining repair knowledge: Prior studies examined small commits, modification requests, or manually identified bug-fix patterns, whereas this work automatically extracts repair actions through AST differencing.The paper emphasizes systematic extraction at a finer granularity than several related approaches.
  • Mining repair knowledge: Related work mined project-specific patterns, return-value checks, cochanged method calls, and broader change categories, while this paper focuses on detailed generic repair actions.The authors distinguish their analysis from coarser or project-specific forms of mined knowledge.
  • Automated repair systems: Compared with AutoFix-E, this work uses 173 basic repair actions and predicts combinations of 4 actions, rather than relying on two elementary contract-based actions.AutoFix-E uses state-changing statements and preconditions as its elementary repair actions.
  • Automated repair systems: Mutation-based repair and PAR use fault localization or manually designed templates, whereas this paper systematically mines repair actions but remains more theoretical and does not fix concrete bugs.The authors suggest that PAR templates could potentially be augmented with probability distributions.
  • Contribution and future work: The paper analyzes 62,179 versioning transactions from 14 open-source projects to learn generic repair actions intended to be independent of bug type and software domain.Future work proposes applying the learned probabilistic models to real bugs in PAR and GenProg datasets.
Loading 1311.3414v1…