FixMiner: Mining relevant fix patterns for automated program repair

Anil Koyuncu, Kui Liu, Tegawendé F. Bissyandé, Dongsun Kim, Jacques Klein, Martin Monperrus, Yves Le Traon

TL;DR

FixMiner is a novel framework that automatically extracts actionable and context-aware bug-fix patterns from thousands of open-source patches. By using a specialized "Rich Edit Script" representation and an iterative clustering strategy, it generates high-quality repair templates that allowed a prototype system to correctly fix 26 real-world bugs with an impressive 81% precision.

What Problem Does This Paper Address?

Automated Program Repair (APR) aims to reduce manual debugging effort by automatically generating patches for software bugs. Many successful APR systems rely on fix patterns (or templates)—predefined ways to transform buggy code into fixed code.

However, there is a major bottleneck: how do we get these patterns?

  1. Manual Mining: Researchers often manually inspect thousands of patches to find commonalities. This is tedious, error-prone, and doesn't scale.
  2. Existing Automated Tools: Previous attempts at automation often produced "intractable" patterns. They either lacked the necessary code context to be useful or were too specific to a single project.

The authors identify a "granularity gap": a fix pattern needs to be abstract enough to apply to many bugs, but specific enough to include the surrounding code context (like whether a change happened inside an IfStatement or a ReturnStatement) so the repair tool knows where and how to apply it.

Methods

The core of the paper is FixMiner, which introduces two key innovations:

1. Rich Edit Scripts

Standard tools like GumTree produce "edit scripts" that describe what changed (e.g., "Update variable name"). FixMiner enriches these into Rich Edit Scripts. These capture the AST (Abstract Syntax Tree) context of the change.

The AST representation of a simple Java class, showing the hierarchical structure FixMiner leverages.

By traversing the AST from the point of change up to a predefined "root" (like a Statement or Method Declaration), FixMiner preserves the structural "shape" of the code surrounding the fix.

2. Iterative Three-Fold Clustering

FixMiner doesn't just group patches in one go. It uses an iterative "folding" strategy:

  • Step 1: Shape Clustering: Groups changes by their AST structure (the "ShapeTree"). This identifies the context of the fix.
  • Step 2: Action Clustering: Within those shapes, it groups by the specific edit operations (the "ActionTree"). This identifies the fix strategy.
  • Step 3: Token Clustering: Finally, it looks at the specific code tokens and literals involved (the "TokenTree").
The overall FixMiner workflow, from collecting patches to iterative clustering.

To make this computationally feasible across millions of potential tree pairs, the authors implemented a Search Index to group similar scripts before performing expensive tree-edit distance calculations.

Datasets

  • Mining Dataset: 11,416 patches collected from 43 large open-source Java projects (including Apache, JBoss, Spring, and Wildfly).
  • Evaluation Benchmark: Defects4J, the industry standard for Java APR research, containing 357 real-world bugs.
  • Human Oracle: A manually dissected dataset of 395 Defects4J patches used to verify if FixMiner's automated clusters match human intuition.

Key Insights and Ideas

  • Context is King: A change like "replacing an operator" is much more useful to a repair tool if it knows that change typically happens inside an InfixExpression within an IfStatement.
  • Handling "Tangled" Patches: Real-world commits are often messy, containing refactors or multiple unrelated fixes. FixMiner addresses this by breaking patches down into "atomic units" (hunks) before mining.
  • Tractability: Unlike many research prototypes, FixMiner is designed to produce a standalone library of patterns that can be reused by other APR systems.

Key Results

The authors evaluated FixMiner's patterns using a prototype repair tool called PARFixMiner.

  • Consistency: Automated clustering was highly consistent with human labels (73% to 92% agreement across different cluster types).
  • Repair Power: PARFixMiner correctly fixed 26 bugs in the Defects4J benchmark.
  • High Precision: 81% of the "plausible" patches (those that passed all test cases) generated by the tool were actually correct (semantically identical to the developer's original fix). This is significantly higher than many competing tools.
  • Novelty: FixMiner successfully fixed 6 bugs that had not been fixed by any other state-of-the-art APR tool at the time of publication.
A comparison showing FixMiner's high precision and competitive performance against other APR tools.

Limitations and Future Work

  • Token-Level Integration: While FixMiner successfully mines very specific "Token patterns," these are currently used more for analyzing "collateral evolutions" (repetitive changes across a codebase) rather than being fully integrated into the general repair pipeline.
  • Search Space: Even with indexing, comparing millions of tree structures is computationally heavy.
  • Semantic Gap: While AST context is a huge step forward, it doesn't capture deeper program semantics like data flow or complex logic, which might be needed for more difficult bugs.
  • Future Direction: The authors suggest automating the conversion of Token patterns into generic "semantic patches" using specialized languages like SmPL.

Summary updated

Abstract

Patching is a common activity in software development. It is generally performed on a source code base to address bugs or add new functionalities. In this context, given the recurrence of bugs across projects, the associated similar patches can be leveraged to extract generic fix actions. While the literature includes various approaches leveraging similarity among patches to guide program repair, these approaches often do not yield fix patterns that are tractable and reusable as actionable input to APR systems. In this paper, we propose a systematic and automated approach to mining relevant and actionable fix patterns based on an iterative clustering strategy applied to atomic changes within patches. The goal of FixMiner is thus to infer separate and reusable fix patterns that can be leveraged in other patch generation systems. Our technique, FixMiner, leverages Rich Edit Script which is a specialized tree structure of the edit scripts that captures the AST-level context of the code changes. FixMiner uses different tree representations of Rich Edit Scripts for each round of clustering to identify similar changes. These are abstract syntax trees, edit actions trees, and code context trees. We have evaluated FixMiner on thousands of software patches collected from open source projects. Preliminary results show that we are able to mine accurate patterns, efficiently exploiting change information in Rich Edit Scripts. We further integrated the mined patterns to an automated program repair prototype, PARFixMiner, with which we are able to correctly fix 26 bugs of the Defects4J benchmark. Beyond this quantitative performance, we show that the mined fix patterns are sufficiently relevant to produce patches with a high probability of correctness: 81% of PARFixMiner’s generated plausible patches are correct.
BibTeX
@inproceedings{koyuncu2020fixminer,
  author = {Anil Koyuncu and Kui Liu and Tegawendé F. Bissyandé and Dongsun Kim and Jacques Klein and Martin Monperrus and Yves Le Traon},
  title = {{FixMiner: Mining relevant fix patterns for automated program repair}},
  booktitle = {Empir. Softw. Eng},
  year = {2020},
  url = {https://openreview.net/forum?id=HK-UmzT3mgq},
}

Loading related content...

Figure