Abstract
Automated program repair (APR) has great potential to reduce the effort and time-consumption in software maintenance and becomes a hot topic in software engineering recently with many approaches being proposed. Multi-location program repair has always been a challenge in this field since its complexity in logic and structure. While some approaches do not claim to have the features for solving multi-location bugs, they generate correct patches for these defects in practice. In this paper, we first make an observation on multi-location bugs in Defects4J and divide them into two categories (i.e., similar and relevant multi-location bugs) based on the repair actions in their patches. We then summarize the situation of multi-location bugs in Defects4J fixed by current tools. We analyze the twenty-two patches generated by current tools and propose two feasible strategies for fixing multi-location bugs, illustrating them through two detailed case studies. At last, the experimental results prove the feasibility of our methods with the repair of two bugs that have never been fixed before. By learning from successful experience in the past, this paper points out possible ways ahead for multi-location program repair.
Introduction
Automated Program Repair (APR) aims to automate the generation of patches for software defects. While most state-of-the-art tools excel at "single-shot" fixes, real-world maintenance often requires modifying multiple code locations simultaneously. Empirical studies indicate that over 60% of bugs in benchmarks like Defects4J require multi-point changes. Fixing these bugs presents a "search space explosion" problem: finding multiple correct edits exponentially increases computational complexity, often making traditional methods infeasible.
Categorizing Multi-Location Bugs
To address this complexity, the authors categorize multi-location bugs into two primary types based on the required repair actions:
- Similar Multi-Location Bugs: These involve edits at different points that share similar syntax. For example, adding the same null check to multiple methods.
- Relevant Multi-Location Bugs: These involve edits that are logically or structurally linked within the Abstract Syntax Tree (AST), such as modifying a variable's definition and its subsequent usage.
Proposed Repair Strategies
By analyzing 22 "accidental" successes where single-location tools fixed multi-location defects, the authors propose two formal strategies:
Strategy 1: Incremental Fixing for Similar Bugs
This strategy uses a "partial fixing" approach guided by a fitness function. If a repair action reduces the number of failing test cases, the tool retains that change and continues searching for the next edit. To prevent "overfitting," the authors advocate for test suite augmentation (e.g., using EvoSuite) to provide a more robust safety net during the incremental search.
Strategy 2: Error Propagation Chain (EPC) for Relevant Bugs
Instead of fixing every individual buggy point, this strategy identifies an Error Propagation Chain (EPC) intersection. By finding a single statement through which multiple errors pass, a tool can generate a single "guard" condition (using an SMT solver) that neutralizes the bug's effect across all locations. This effectively turns a multi-location problem into a strategic single-location fix.
Experimental Results
The study utilized the Defects4J benchmark, analyzing 244 multi-location patches. The authors successfully validated their strategies by fixing two bugs—Math#49 and Closure#8—that had never been repaired by any previous APR tool.
The results demonstrate a significant difference in efficiency. While search-based tools like SimFix (Strategy 1) can take hundreds of minutes, semantics-based tools like Nopol (Strategy 2) can find fixes in under two minutes by targeting logical intersections.
Conclusion
This research highlights that multi-location repair is achievable by leveraging incremental fitness progress and logical bottlenecks. While challenges remain—such as automatically classifying bug types before repair—these strategies provide a clear roadmap for the next generation of APR tools to handle complex, real-world software defects.
Summary updated