Source-linked AI summary
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
Existing fix-pattern mining approaches often do not produce tractable, reusable artifacts for automated program repair. FixMiner mines actionable patterns from atomic changes using Rich Edit Scripts and iterative clustering, then integrates them into PARFixMiner, which correctly fixes 26 Defects4J bugs and yields 81% correct plausible patches.
Problem
Existing fix-pattern mining approaches may not produce patterns that are tractable and reusable as actionable inputs to automated program repair.
Method
FixMiner mines fix patterns from atomic patch changes using Rich Edit Scripts and iterative clustering across AST, edit-action, and code-context representations.
Results
26 Defects4J bugs were correctly fixed, and correct patches represented 81% of PARFixMiner's plausible patches.
Takeaways & Limitations
The mined patterns function as a separate, reusable component for automated patch generation and produce mostly correct plausible patches in the reported evaluation.
Takeaways & Limitations
The bug-fix dataset selection threatens external validity, and strict bug definitions may classify some included cases as false positives.
Abstract
from arXiv · showhide
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.
1 Introduction
FixMiner addresses the difficulty of automatically mining fix patterns that are relevant, tractable, and reusable in automated program repair. It combines Rich Edit Scripts with iterative clustering and demonstrates usefulness through PARFixMiner.
- Research gap: Existing approaches mine or use fix patterns, but many produce patterns that are intractable, non-reusable, or merely supplementary guidance for patch generation.Manual mining is also described as tedious, error-prone, and unable to scale.
- Approach: Rich Edit Script is a specialized edit-script tree that captures AST-level context and supports comparison through AST, edit-action, and code-context representations.These representations are used to identify similar changes during clustering.
- Approach: FixMiner iteratively clusters atomic changes using tree representations encoding code context, change operations, and code tokens.The approach is designed to discover similar changes across successive clustering rounds.
- Evaluation: FixMiner mined patterns from 11 416 patches addressing user-reported bugs in 43 open source projects.The study also relates the discovered patterns to an existing program-repair dataset and patterns from the literature.
2 Motivation
The paper motivates fine-grained, actionable fix-pattern mining because real-world patches can contain tangled changes and text diffs lack structural detail. FixMiner addresses this by analyzing atomic hunks with context-aware edit representations.
- Motivation: Generic bug-fix catalogs describe common change types, but relevant repair patterns must be recurrent, fine-grained, and actionable for patch generation.The paper distinguishes actionable patterns from generic descriptions of changes that often fix bugs.
- Motivation: FixMiner therefore breaks patches into atomic units, defined as contiguous changed code lines forming a hunk, to reason about recurring changes.Its stated intuition is that global mining is affected by noisy details from tangled changes.
- Approach: The method represents changes through context, change operation, and code-token information, distinguishing syntactically related but semantically different edits.Examples include AST node context, operation order, and specific API tokens.
- Background: ASTs provide hierarchical program representations whose nodes encode language constructs and raw token values for structural analysis.The paper uses this representation as the basis for organizing and comparing code changes.
- Code differencing: Text-based GNU diff represents additions and removals of lines but lacks the fine-grained structural detail needed for systematic change analysis.Tree-based algorithms such as GumTree instead produce edit scripts over AST nodes.
- Motivation: Real-world patches may combine bug fixes with unrelated enhancements, refactorings, documentation, or typo corrections, creating tangled patches.The GWT example combines a browser-related warning with an unrelated typo correction.
3 Approach
FixMiner mines reusable fix patterns from atomic patch changes by enriching GumTree edit scripts with AST-level context and iteratively clustering specialized tree representations. Its pipeline collects and filters patches, constructs Rich Edit Scripts, narrows comparisons with search indices, and infers recurrent action patterns.
- Overview: FixMiner separates atomic changes within bug-fixing patches before mining patterns, addressing tangled commits that may mix fixes with unrelated changes.The approach focuses pattern inference on individual code hunks rather than entire mixed-purpose commits.
- Iterative Mining: FixMiner represents each Rich Edit Script using specialized trees for AST node types, repair actions, and affected program tokens across successive mining iterations.Later iterations operate on clusters produced by earlier rounds.
- Rich Edit Scripts: Rich Edit Scripts retain AST-level context around GumTree edit actions, compensating for contextual information lost in ordinary edit scripts.They reorganize edit actions under minimal AST subtrees and store ordered sequences of extracted subtrees.
- Tree Comparison: Each iteration builds search-index comparison subspaces, computes tree distances, detects identical representations, and regroups them into clusters.The search index reduces the comparison space, while zero edit distance identifies identical trees.
- Pattern Inference: The second iteration extracts recurring repair actions from ActionTrees, and these Action patterns are the reusable fix patterns sought by FixMiner.They are intended as separate components that can be integrated into patch-generation systems.
4 Experimental Evaluation
The evaluation examines FixMiner’s mining process, scalability, cluster characteristics, and research questions using patches from diverse open-source Java projects.
- Dataset: FixMiner’s experiments use code changes from 44 large open-source Java projects selected across multiple software categories.Projects required public bug reports and at least 20 source files in one version.
- Mining process: 11 416 patches are associated with 41 823 hunks, making direct pairwise comparison computationally impractical.The workflow therefore compares hunks through search indices rather than exhaustive pairwise computation.
- Mining process: 98% of the Shape comparison space is eliminated, while Action and Token indices reduce their comparison spaces by 88% and 72%, respectively.The Shape index yields 670 relevant comparison sub-spaces and over 12 million comparison pairs.
- Cluster characteristics: Shape patterns are most diverse, Action patterns are fewer and suitable as repair inputs, and Token patterns may be codebase-specific.Clusters are formed only from tree pairs that are identical among themselves.
- Pattern scope: FixMiner analyzes both partial and full changes and can cope with tangled changes during pattern mining.Most patterns are neither always full nor always partial across patches.
- Research questions: The study evaluates whether FixMiner’s clustering agrees with human dissection, matches known fix patterns, and supports automated program repair.These objectives are expressed as RQ-1, RQ-2, and RQ-3.
5 Results
Results indicate that FixMiner produces patterns largely consistent with human labels, compatible with existing repair patterns, and useful for generating correct APR patches.
- RQ1: Consistency: ∼78% of Shape, ∼73% of Action, and ∼92% of Token clusters are consistent with the corresponding human dissection labels.The authors conclude that FixMiner’s patterns are largely consistent with manual dissection.
- RQ1: Granularity: FixMiner’s patterns are finer-grained than manually dissected patterns, with some human patterns refined into multiple Shape or Action patterns.For example, condBlockRetAdd maps to 14 Shape patterns, while expLogicMod maps to 2 Action patterns.
- RQ2: Compatibility: 16 of the 35 fix patterns used by 11 APR systems are also yielded as FixMiner Action patterns.The matching patterns include categories such as null-pointer checks, range checks, statement insertion, and operator mutation.
- Token patterns: Among the top 50 Token patterns, recurrent changes include modifier updates, logging changes, infix-operator fixes, exception handling, and parameter corrections.The authors report that many recurrent token-associated changes are relevant and include collateral evolutions.
- RQ3: Repair effectiveness: 26 Defects4J bugs are correctly repaired by PARFixMiner, and 81% of its plausible patches are correct.The precision is compared with 63% for ELIXIR, 60% for SimFix, and 84% for CapGen.
- RQ3: Repair effectiveness: PARFixMiner fixes six bugs not fixed by any state-of-the-art APR tools, while 267 Defects4J bugs remain unfixed by tools in the literature.The six-bug result is attributed to its automatically mined patterns.
6 Discussions and Threats to Validity
FixMiner’s experiments were computationally feasible, but validity concerns remain for dataset selection and compatibility comparisons with more abstract literature patterns.
- Runtime performance: Constructing Rich Edit Scripts took about 17 minutes, while comparing 1 108 060 tree pairs took about 18 minutes.The experiments used 24 Intel Xeon E5-2680 v3 cores and 3TB RAM.
- Threats to external validity: Dataset selection may limit external validity despite using known projects and heuristics from previous studies.Commit-to-bug-report links were based on developer tags, and strict bug definitions may classify some cases as false positives.
- Threats to construct validity: Compatibility checks do not use exact element-to-element mappings because literature patterns can be more abstract than FixMiner patterns.The comparison therefore uses contextual information, such as a Return-Statement context, to assess compatibility.
- Threats to construct validity: The compatibility mapping is conservative: a FixMiner pattern matches a literature pattern when it can fit that literature pattern.This allows context-rich FixMiner patterns to be related to broader literature patterns.
7 Related Work
Related work spans automated repair, code differencing, change-pattern mining, and code-change redundancy. FixMiner differs by producing contextual, separate, and reusable patterns independently of patch generation.
- Automated Program Repair: Automated program repair aims to reduce the time and cost of manual patch generation and maintenance.GenProg pioneered repair using mutation operators that insert, replace, or delete code elements.
- Code differencing: Text-line differencing is poorly suited to automated change analysis because it lacks fine-grained semantic representations.AST differencing instead supports more structured representations of program changes.
- Change patterns: Prior mining strategies include hierarchical clustering, association-rule mining, AST differencing, and unsupervised learning for discovering change or repair templates.These studies target different languages, applications, and abstraction levels.
- Studies on code change redundancies: Repeated code changes arise from recurring bugs, API evolution, library migration, refactoring, and routine code cleaning.Prior work found if-condition changes frequently applied to bug fixes, but did not establish how many bugs involve if-conditions.
- Mining-based approaches: Unlike SimFix and CapGen, FixMiner separates pattern mining from patch generation and produces patterns reusable as input to other APR systems.SimFix and CapGen use change-action frequency or contextual redundancy to guide patch generation rather than outputting actionable pattern artifacts.
- Generic and semantic patch inference: Generic and semantic patch inference seeks patches reusable across buggy code, but prior representations may be overfit, too abstract, poorly scalable, or constrained by transformation engines.FixMiner is positioned toward generic, actionable patterns without requiring ready-to-use semantic patches.
8 Conclusion
FixMiner mines relevant and actionable fix patterns through iterative clustering of recurrent tree representations. Its patterns supported correct repairs for 26 Defects4J bugs, representing 81% of plausible generated patches.
- Conclusion: FixMiner uses an iterative three-fold clustering strategy to form clusters of identical trees representing recurrent patterns.The approach systematically mines fix patterns from repeated change structures.
- Conclusion: 26 Defects4J bugs received correct patches from the automated repair pipeline using FixMiner’s mined patterns.The result demonstrates the patterns’ relevance for generating correct patches.
- Conclusion: 81% of all plausible patches generated by the tool were correct.This percentage qualifies the correctness of the generated plausible-patch set.
automatic program repair, program hardening and chaos engineering.
Yves Le Traon is a University of Luxembourg professor whose work spans software engineering, testing, security, and model-driven engineering.
- Author information: Yves Le Traon is a professor at the University of Luxembourg.The passage places his work in software engineering, testing, security, and model-driven engineering.
- Author information: He received an engineering degree and a PhD in Computer Science from the Institut National Polytechnique in Grenoble in 1997.
- Author information: Before joining the University of Luxembourg, he held academic and industry roles in Rennes and France Telecom R&D.The passage dates these positions to 1998–2006.