Source-linked AI summary
On the Efficiency of Test Suite based Program Repair: A Systematic Assessment of 16 Automated Repair Systems for Java Programs
Kui Liu, Shangwen Wang, Anil Koyuncu, Kisub Kim, Tegawendé F. Bissyandé, Dongsun Kim, Peng Wu, Jacques Klein, Xiaoguang Mao, Yves Le Traon
TL;DR
Although APR research has increasingly reported bugs fixed, the efficiency of patch generation remains underexplored and matters for practical use. The paper systematically evaluates 16 Java repair systems using generated patch candidates under identical fault-localization configurations, finding that state-of-the-art tools are the least efficient and that template-based systems generally produce too many candidates. These findings support treating efficiency as a complementary performance target while recognizing the study’s benchmark and methodological boundaries.
Problem
Patch-generation efficiency is underexplored despite concerns about APR evaluations and the practical importance of reducing repair effort.
Method
The study evaluates 16 Java APR systems under identical fault-localization configurations, assessing efficiency through generated patch candidates and examining patch validity and correctness.
Results
State-of-the-art APR tools are the least efficient, while template-based systems generally produce too many patch candidates.
Takeaways & Limitations
Efficiency should be considered alongside repairability as a performance target for facilitating APR adoption in software industry settings.
Takeaways & Limitations
Findings are limited to Java repair tools evaluated on the Defects4J benchmark, and the patch-correctness rules are not exhaustive.
Abstract
from arXiv · showhide
Test-based automated program repair has been a prolific field of research in software engineering in the last decade. Many approaches have indeed been proposed, which leverage test suites as a weak, but affordable, approximation to program specifications. Although the literature regularly sets new records on the number of benchmark bugs that can be fixed, several studies increasingly raise concerns about the limitations and biases of state-of-the-art approaches. For example, the correctness of generated patches has been questioned in a number of studies, while other researchers pointed out that evaluation schemes may be misleading with respect to the processing of fault localization results. Nevertheless, there is little work addressing the efficiency of patch generation, with regard to the practicality of program repair. In this paper, we fill this gap in the literature, by providing an extensive review on the efficiency of test suite based program repair. Our objective is to assess the number of generated patch candidates, since this information is correlated to (1) the strategy to traverse the search space efficiently in order to select sensical repair attempts, (2) the strategy to minimize the test effort for identifying a plausible patch, (3) as well as the strategy to prioritize the generation of a correct patch. To that end, we perform a large-scale empirical study on the efficiency, in terms of quantity of generated patch candidates of the 16 open-source repair tools for Java programs. The experiments are carefully conducted under the same fault localization configurations to limit biases.
1 INTRODUCTION
Automated program repair has expanded rapidly, but research has emphasized repairability more than the efficiency of patch generation. This study addresses that gap by assessing how many patch candidates 16 Java repair systems generate under controlled fault-localization configurations.
- APR research has grown around heuristic, constraint-solving, and machine-learning techniques that generate patches until tests indicate the desired behaviour.The literature includes random mutation, symbolic execution, and code-transformation approaches.
- Execution time is an unstable and weakly generalizable efficiency measure because it depends on variables unrelated to the repair approach.The paper therefore motivates counting generated candidates instead of relying only on time-to-generate-and-validate.
- Efficiency concerns how many repair attempts are made before a valid patch is found, but this aspect has received little systematic attention.The study uses the number of validated patch candidates as an efficiency-oriented measure.
- The study assesses 16 Java APR systems under identical and controlled fault-localization configurations.Its objective is to analyze how repair strategies affect the quantity of generated patch candidates.
- Template-based systems generally generate too many candidates, although clean or bug-specialized templates can substantially improve efficiency.Constraint solving and donor-code search can reduce nonsensical candidates, whereas random search requires large candidate sets to increase the chance of finding a correct patch.
2 BACKGROUND AND MOTIVATION
Test-based APR uses fault localization, patch generation, and test-based validation, but execution time is unstable and machine-dependent. The study therefore motivates number of generated patch candidates as an intrinsic efficiency metric.
- APR pipeline: APR commonly follows three steps: fault localization, patch generation, and patch validation against the test suite.Fault localization ranks suspicious locations; generation applies change operators; validation executes tests on patched programs.
- Patch assessment: A test-passing patch is only plausible because uncovered behaviors or developer preferences may still make it incorrect or unacceptable.Correctness is generally assessed manually against the developer-provided benchmark patch.
- Time-based efficiency: More than 29,000 patches per Closure bug were generated and validated on average, about 10 times the Chart average, yet Closure took 20 times longer.This mismatch makes execution time difficult to interpret as a general efficiency measure.
- Time-based efficiency: Different machine configurations produced drastically divergent compilation and testing times, making time cost unreliable for reproducible repair-efficiency comparisons.Statistical tests found Machine 1 consumed significantly more CPU time than Machine 2 for both compilation and testing.
- Candidate-based efficiency: The study proposes number of generated patch candidates as an approach-intrinsic metric that is agnostic to machine-configuration variability.The metric is intended to avoid biases associated with execution-time measurements.
3 STUDY DESIGN
This section describes the design of the empirical study.
- The section presents the design details of the empirical study.
3.1 Research Questions
The study examines repairability, patch-generation efficiency, and the impact of fault-localization noise. It evaluates these questions across many repair systems using consistent configurations and considers both plausible and correct patches.
- RQ1. Repairability across time: RQ1 asks how many bugs test-suite-based repair approaches can fix, assessing plausibility and correctness across systems under the same configurations.It also examines how effectiveness has evolved over time.
- RQ2. Patch generation efficiency: RQ2 asks how many patch candidates are generated and checked before fixing a bug, including nonsensical and in-plausible patches.The question treats efficiency as important because resource budgets are limited.
- RQ3. Fault Localization noise impact on efficiency: RQ3 investigates how noisy fault-localization inputs affect efficiency and whether repair strategies differ in resilience to wrong code locations.The study uses multiple repair systems rather than the single system examined in the cited recent work.
3.2 Subject Selection
The study selects 16 executable, configurable, standalone, publicly available Java APR tools from a broader set of approaches. It covers diverse repair categories while excluding tools that require unavailable resources or cannot satisfy the study criteria.
- Scope: The study focuses on Java because it is widely targeted and has a well-formed real-world bug dataset with tool support for compilation and execution.Many approaches were excluded because they were not open-source or publicly available.
- Selection criteria: Tools are selected for public availability, executability, configurability, and standalone operation using source code and the available test suite.Tools requiring private services, fixed fault information, or external data are excluded.
- Included approaches: The final study includes 16 tools spanning heuristic-, constraint-, and template-based repair approaches.Learning-based approaches are excluded because they are generally not standalone.
- Study coverage: The study covers a more diverse tool set than the previous large-scale benchmark-overfitting study, including widespread template-based tools, ACS, and SimFix.
3.3 Experiment Settings
The study standardizes benchmark, fault localization, patch validation, and correctness assessment settings to compare 16 Java APR systems. It uses explicit semantic-similarity rules to label correct patches and a 10,000-attempt threshold to control experiments.
- Inputs and benchmark: The study uses Defects4J, a widely used APR benchmark, while acknowledging that APR systems may overfit study benchmarks.
- Inputs and benchmark: All APR tools use identical fault-localization information generated with GZoltar v1.7.2 to reduce configuration-related bias.
- Patch validation: A patch is valid when it makes the revised program pass the entire test suite, although such a patch may still overfit the tests.
- Patch validation: Correctness is assessed through explicit rules for identical and semantically similar patches, reducing subjectivity and supporting reproducibility.The rules compare tool-generated patches with developer-provided patches and include cases where syntactically different patches have the same program effect.
- Patch validation: The correctness rules are not exhaustive, and the benchmark developer patch used as ground truth may itself be erroneous.
- Experimental control: Repair systems are halted after 10,000 attempts rather than by a time budget, because execution time depends on unrelated variables and is unstable.
3.4 Terminology
The paper uses “valid patches” for all plausible patches, including correct ones, and reserves “plausible” for valid patches not manually assessed as correct.
- “Valid patches” are all plausible patches, including patches that are correct.
- Unless manually assessed as correct, valid patches are referred to as plausible patches.
3.5 Efficiency Metric: NPC
NPC measures repair efficiency as the number of patch candidates generated before the first plausible patch is found. The metric sums candidates across nonsensical, in-plausible, and valid categories.
- NPC is the number of patch candidates generated by an APR tool until the first plausible patch is found.The metric was previously proposed as a proxy for assessing fault-localization performance through program repair.
- Nonsensical patches fail to compile, whereas in-plausible patches compile but fail some available test cases.
- The efficiency metric is computed by summing the numbers of patches in each category.
- NPCvalid equals 1 in practice because generation stops when the first valid patch is found.
- The experimental data exclude bugs for which many candidates are generated but none is valid, leaving those cases for future study.
4 STUDY RESULTS
The study finds that repairability and efficiency do not align straightforwardly: tools that fix more bugs often generate more candidates, while strategy and fault localization strongly shape candidate quality and volume.
- Repairability: Template-based tools kPAR, FixMiner, AVATAR, and TBar show better repair performance by fixing more bugs than other tools.SimFix also performs among the top tools.
- Repairability: ACS has the highest ratio of plausible patches found to be correct, consistent with its dependency-based ordering, document analysis, and predicate mining.
- Repairability: Recent tools increasingly correctly fix bugs not fixed by previous tools, although several older tools produce no exclusive correct fixes.SimFix, ACS, AVATAR, and TBar lead in exclusive correct fixes, whereas eight listed tools produce none.
- Repairability: Implementation differences matter: jGenProg and GenProg-A, and jKali and Kali-A, show diverging repair performance on the same benchmark.
- Efficiency: All tools have median NPC below 250 candidates, but SimFix, TBar, and kPAR can exceed 1,000 candidates for some bugs.The distribution spread is significant for 8 of 16 tools and varies across tools.
- Efficiency: Template-based tools can generate many nonsensical patches, while DynaMoth, Nopol, and SimFix generate none according to the assessment.The findings motivate triaging nonsensical patches within the search space.
- Efficiency: More templates do not necessarily improve efficiency: TBar’s 35 templates increase candidate matching opportunities, while kPAR’s 10 templates is nevertheless least efficient.Template matching and donor-code search remain important efficiency factors.
- Efficiency: Allowing more repair attempts does not guarantee correct patches; using fewer attempts appears to improve the correctness ratio.
5 THREATS TO VALIDITY
The study’s validity is constrained by its benchmark and language scope, implementation and manual-assessment choices, and an attempt threshold that may penalize some tools.
- External validity: The external-validity findings cover only the Defects4J benchmark and Java repair tools.The authors state that findings might be valid only for this configuration.
- Internal validity: Fault-localization implementation and manual patch-correctness assessment may threaten the validity of some conclusions.The authors mitigate this through reused components, explicit correctness rules, and cross-reviewed assessments.
- Construct validity: The 10,000-patch validation threshold may penalize some tools by limiting resource exhaustion.The threshold was selected using empirical results from PraPR.
6 RELATED WORK
Related work evaluates repairability through fixed-bug counts, plausibility, correctness, and execution time, while this study emphasizes generated patch candidates as an intrinsic efficiency measure.
- Performance evaluation: Repairability metrics evolved from counting fixed bugs toward distinguishing plausible and correct patches because test suites can be incomplete.
- Performance evaluation: This study uses identical controlled fault-localization configurations, differing from prior repairability studies.
- Repair efficiency: Execution time has been used to assess repair efficiency, but the study argues it can be biased and instead measures generated patch candidates.The candidate count is presented as intrinsic to the repair approaches.
- Empirical studies: Prior empirical studies examined real-bug repair, overfitting, test cases, test-suite metrics, and related repair questions.
7 CONCLUSION
The paper studies repair efficiency through the number of candidates generated before a valid patch, comparing 16 Java repair systems under identical fault-localization configurations.
- Efficiency is defined as the number of patch candidates generated before a repair system hits a valid patch.
- The study comprehensively evaluates 16 repair systems under identical fault-localization configurations.It examines repairability, repair efficiency, and fault localization’s impact on both criteria.