Multi-Location Program Repair Strategies Learned from Past Successful Experience

Shangwen Wang, Xiaoguang Mao, Nan Niu, Xin Yi, Anbang Guo

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) has made significant strides in fixing "one-liner" bugs. However, real-world software maintenance is rarely that simple; empirical studies show that over 60% of real-world bugs require modifications in multiple locations. Fixing these multi-location bugs presents a "search space explosion" problem. If a tool must navigate thousands of possible fixes for a single location, finding a coordinated fix for multiple locations simultaneously becomes computationally prohibitive. This research investigates why some existing APR tools—even those not designed for multi-location repair—occasionally succeed and how to formalize these successes into deliberate strategies.

Taxonomy and Strategies

By analyzing 244 multi-location patches in the Defects4J database, the authors introduced a two-part taxonomy for these defects:

  1. Similar Multi-Location Bugs: Modifications at different points share similar syntax (e.g., adding the same null check in multiple functions).
  2. Relevant Multi-Location Bugs: Modifications are logically or structurally linked within the program's Abstract Syntax Tree (AST) (e.g., adding a method definition and calling it elsewhere).
Table 1: Analysis of multi-location bugs in Defects4J and their repair status across various APR tools.

Based on this classification, two distinct repair strategies were developed:

  • Strategy 1 (Similar Bugs): This strategy utilizes a fitness function that rewards partial fixes. If a tool fixes one location and the number of failing tests decreases, the tool retains that change and continues searching. To support this, Test Suite Augmentation (using tools like EvoSuite) is recommended to ensure the bug is caught at every location.
  • Strategy 2 (Relevant Bugs): Instead of fixing every point, this strategy identifies a "bottleneck." By analyzing Error Propagation Chains (EPCs), researchers can find a single intersection point where a strategic "guard condition" (like an if statement) can prevent error propagation, effectively neutralizing multiple buggy points with one edit.

Evaluation and Results

The proposed strategies were evaluated by attempting to fix eight multi-location bugs that had never been solved by previous APR tools. The results demonstrated the feasibility of learning from past successful patches to guide future repairs.

Table 2: Experimental results comparing SimFix+Strategy1 and Nopol+Strategy2 on previously unfixable bugs.

Key findings include:

  • Success Stories: The researchers successfully generated correct patches for two previously "unfixable" bugs: Math#49 (a similar bug) and Closure#8 (a relevant bug).
  • Efficiency: For relevant bugs, the search time was remarkably low—often under two minutes—once the intersection point in the Error Propagation Chain was identified.
  • The Power of Preconditions: For logically complex bugs, automated tools can often achieve the same result as a human multi-chunk patch by finding a "choke point" and adding a single, well-placed precondition.

Conclusion

While tools like ACS and SimFix show potential for multi-location repair, a significant gap remains in handling "relevant" bugs. A primary hurdle is a posteriori classification; currently, the bug type is only known after seeing the human fix. Future work must focus on predicting bug types by analyzing the context of suspicious code points before the repair process begins. Integrating these strategies into a unified, automated tool could significantly advance the field of multi-location program repair.

Summary updated

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.
BibTeX
@misc{wang2018multi,
  author = {Shangwen Wang and Xiaoguang Mao and Nan Niu and Xin Yi and Anbang Guo},
  title = {{Multi-Location Program Repair Strategies Learned from Past Successful Experience}},
  year = {2018},
  eprint = {1810.12556},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1810.12556},
}
Figure