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.
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:
- Shape Clustering: Groups changes by their AST structure (the "ShapeTree") to identify the context of the fix.
- Action Clustering: Groups changes by specific edit operations (the "ActionTree") to identify the fix strategy.
- 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.
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