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

Abstract

Patching is a common activity in software development, generally performed to address bugs or add new functionalities. Given the recurrence of bugs across projects, similar patches can be leveraged to extract generic fix actions. While various approaches leverage patch similarity to guide program repair, they often fail to yield fix patterns that are tractable and reusable as actionable input to Automated Program Repair (APR) systems. In this paper, we propose FixMiner, a systematic approach to mining relevant and actionable fix patterns based on an iterative clustering strategy applied to atomic changes within patches. FixMiner leverages "Rich Edit Scripts," a specialized tree structure that captures the AST-level context of code changes. By using different tree representations—abstract syntax trees, edit actions trees, and code context trees—FixMiner identifies similar changes across thousands of open-source patches. Evaluation on the Defects4J benchmark shows that FixMiner correctly fixes 26 bugs with a high probability of correctness: 81% of the generated plausible patches are correct.

The Challenge of Automated Program Repair

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, obtaining these patterns remains a major bottleneck. Manual mining is tedious and does not scale, while existing automated tools often produce "intractable" patterns that either lack necessary code context or are too project-specific.

Researchers face a "granularity gap": a fix pattern must be abstract enough to apply to many bugs, yet specific enough to include the surrounding code context (e.g., whether a change occurred inside an IfStatement or a ReturnStatement) so the repair tool knows exactly where and how to apply it.

Methodology: The FixMiner Framework

FixMiner introduces a novel pipeline to bridge this gap, focusing on the extraction of context-aware bug-fix patterns from large-scale repositories.

The overall FixMiner workflow, illustrating the process from collecting bug fix patches to the iterative folding of Rich Edit Scripts into clusters.

Rich Edit Scripts

Standard tools produce simple edit scripts describing what changed (e.g., "Update variable name"). FixMiner enriches these into Rich Edit Scripts, which capture the Abstract Syntax Tree (AST) context. 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.

Iterative Three-Fold Clustering

FixMiner employs an iterative "folding" strategy to group patches across three dimensions:

  1. Shape Clustering: Groups changes by their AST structure (the "ShapeTree") to identify the context of the fix.
  2. Action Clustering: Groups changes by specific edit operations (the "ActionTree") to identify the fix strategy.
  3. Token Clustering: Groups changes by specific code tokens and literals (the "TokenTree").

To handle millions of potential tree pairs, the system utilizes a Search Index to group similar scripts before performing computationally expensive tree-edit distance calculations.

Evaluation and Results

The authors evaluated FixMiner's patterns using a prototype repair tool called PARFixMiner against the Defects4J benchmark, which contains 357 real-world Java bugs.

A comparison of FixMiner against other state-of-the-art APR tools, demonstrating its superior pattern tractability and context awareness.

Key findings include:

  • Repair Power: PARFixMiner correctly fixed 26 bugs in the Defects4J benchmark, including 6 bugs that had not been fixed by any other state-of-the-art APR tool at the time of publication.
  • High Precision: 81% of the "plausible" patches (those passing all test cases) were semantically identical to the developer's original fix. This precision significantly outperforms many competing tools.
  • Consistency: Automated clustering showed high agreement (73% to 92%) with human-labeled fix patterns, suggesting the tool effectively mimics human intuition in identifying fix strategies.

Conclusion

FixMiner demonstrates that context is king in automated program repair. By capturing the AST-level environment of a change through Rich Edit Scripts and applying iterative clustering, the framework generates highly relevant and actionable patterns. While future work remains in capturing deeper program semantics like data flow, FixMiner provides a robust foundation for building more precise and scalable APR systems.

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},
}
Figure