PaperlayerView exact revision on arXiv

Source-linked AI summary

A Comprehensive Study of Automatic Program Repair on the QuixBugs Benchmark

He Ye, Matias Martinez, Thomas Durieux, Martin Monperrus

arXiv:1805.03454v4cs.SE

TL;DR

Program repair research repeatedly uses the same benchmarks, threatening the external validity of its findings. This study evaluates 10 repair tools and patch-assessment techniques on QuixBugs, finding that 53.3% of generated patches were overfitting.

  • Problem

    Program repair research repeatedly uses the same benchmarks, threatening the external validity of findings.

    Source: §1 · p. 1

  • Method

    The study prepares QuixBugs for Java repair and evaluates 10 repair tools, using manual assessment and three automated techniques to assess patches.

    Source: §1 · p. 1, §3.2.3 · p. 4

  • Results

    53.3% of generated patches were overfitting, and the tools correctly repaired seven buggy programs.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Repair tools can repair programs with only failing test cases, and RGT_Evosuite had the highest accuracy of the three automated assessment techniques.

    Source: §8 · p. 15

    Manual correctness assessment may misclassify patches because of limited expertise or mistakes.

    Source: §5 · p. 13

Abstract

from arXiv · show

Automatic program repair papers tend to repeatedly use the same benchmarks. This poses a threat to the external validity of the findings of the program repair research community. In this paper, we perform an empirical study of automatic repair on a benchmark of bugs called QuixBugs, which has been little studied. In this paper, 1) We report on the characteristics of QuixBugs; 2) We study the effectiveness of 10 program repair tools on it; 3) We apply three patch correctness assessment techniques to comprehensively study the presence of overfitting patches in QuixBugs. Our key results are: 1) 16/40 buggy programs in QuixBugs can be repaired with at least a test suite adequate patch; 2) A total of 338 plausible patches are generated on the QuixBugs by the considered tools, and 53.3% of them are overfitting patches according to our manual assessment; 3) The three automated patch correctness assessment techniques, RGT_Evosuite, RGT_InputSampling and GT_Invariants, achieve an accuracy of 98.2%, 80.8% and 58.3% in overfitting detection, respectively. To our knowledge, this is the largest empirical study of automatic repair on QuixBugs, combining both quantitative and qualitative insights. All our empirical results are publicly available on GitHub in order to facilitate future research on automatic program repair.

1. Introduction

Repeated use of a small set of program-repair benchmarks threatens the external validity of community findings. This study evaluates QuixBugs with ten repair tools and three patch-assessment techniques, reporting repair outcomes and overfitting rates.

1. Introduction

  • The study evaluates ten repair tools on QuixBugs, generating 338 plausible patches across 16 of its 40 buggy programs.It manually assessed the patches and applied three automated correctness-assessment techniques.Source: §1 · pp. 1–2
  • RGT_Evosuite, RGT_InputSampling, and GT_Invariants achieved overfitting-detection accuracies of 98.2%, 80.8%, and 58.3%, respectively.Source: §1 · p. 2
  • The authors provide a Java-usable QuixBugs version and benchmark-characteristics data, with experimental patches and correctness labels publicly available.They present the study as a baseline for future QuixBugs repair research.Source: §1 · p. 2
  • Manual assessment found that 53.3% of generated patches were overfitting, confirming tools produce many overfitting patches; the study also showed the considered automatic repair tools correctly repaired seven buggy programs [22].Source: §1 · p. 2
  • The study reports that some tools can repair programs with only failing tests, while invariant-based assessment produces many false positives.Source: §1 · p. 2
  • The journal extension expands the prior study from five to ten tools and from 64 to 338 discussed patches, and adds invariant-based assessment.It also compares the accuracy of three assessment techniques and discusses invariant assessment false positives.Source: §1 · p. 2

2. Benchmark preparation

The original QuixBugs materials lacked elements needed for Java test-suite-based repair and patch evaluation. The authors corrected test and compilation problems, created JUnit oracles and Java ground truths, and contributed the prepared benchmark to the public repository.

2. Benchmark preparation

  • The original benchmark contains 40 algorithmic bugs in Java and Python, with JSON test data for 31 programs and ad-hoc Java tests for the other nine.Source: §2 · p. 2
  • The initial Java benchmark lacked regression oracles, had compilation errors and incorrect test values, omitted assertions in nine programs, and lacked Java ground truths.The authors frame clear construction methodology, regression oracles, and real bugs as criteria for a usable repair benchmark.Source: §2 · p. 2
  • The prepared benchmark contains JUnit test oracles and ground truths, was peer-reviewed by QuixBugs' authors, and was contributed to the public repository.Source: §2 · pp. 2–3
  • The authors fixed uncompilable programs and incorrect expected outputs, then converted JSON cases and assertion-less ad-hoc tests into JUnit tests.The JSON conversion generated 224 tests for 31 programs; rewriting the other nine programs' ad-hoc tests produced 35 more.Source: §2 · pp. 2–3
  • They created Java ground-truth programs from the original Python versions so generated patches could be compared with human-written fixes.Source: §2 · p. 3

3. Empirical Study

The empirical study examines QuixBugs characteristics, repairability, patch correctness, and automated overfitting assessment. Its protocols combine benchmark analysis, ten Java repair tools, manual patch review, and three automated assessment approaches.

3. Empirical Study

  • The study covers benchmark analysis, repair effectiveness, and patch correctness assessment, then describes research questions and methods for each dimension.Source: §3 · p. 3

3.1. Research Questions

  • Four research questions ask about QuixBugs characteristics, test-suite-adequate repair, generated-patch correctness, and automated classification of overfitting patches.The study defines a plausible patch as one that makes all tests pass and compares automated assessments with manual assessment.Source: §3.1 · p. 3

3.2. Protocols

  • The protocol gathers bug-type, code-size, test, coverage, input-domain, and failure-symptom information, and selects publicly available, maintained Java test-suite repair tools.Tool selection required Java support, a test-suite-based approach, and public availability with continued maintenance.Source: §3.2 · p. 3, §3.2.1 · pp. 3–4, §3.2.2 · p. 4

3.2.1. RQ1: QuixBugs Benchmark Analysis

  • For RQ1, the researchers characterize bug types and numerical properties, extract input preconditions and domains, and record observed failure symptoms.Reported numerical properties include LOC, passing and failing JUnit tests, execution time, and branch coverage; failure symptoms include wrong output, execution error, exception, and timeout.Source: §3.2.1 · pp. 3–4

3.2.2. RQ2: Repairability of QuixBugs

  • For RQ2, ten selected Java test-suite repair tools run on every QuixBugs program, and the study retains all generated patches rather than stopping at the first.The tools receive source code and a test suite with at least one failing test; the researchers record repaired bugs, bug types, test effects, and failure symptoms.Source: §3.2.2 · p. 4

3.2.3. RQ3: Manual Patch Correctness Assessment

  • For RQ3, patches are manually compared with human-written fixes; identical or behaviorally equivalent patches are correct, and other patches are overfitting if they fail to fix the bug or introduce one.At least two authors discuss assessment results to mitigate bias, and the evaluation is publicly available.Source: §3.2.3 · p. 4

3.2.4. RQ4: Automated Patch Correctness Assessments

  • For RQ4, three automated methods use ground-truth programs: Evosuite-generated tests, program-specific random input sampling, and inferred invariants.RGTEvosuite treats any failing generated test as overfitting; RGTInputSampling generates 300 valid tests per program; GTInvariants flags patches that violate inferred invariants. Automated results are compared with manual assessments using accuracy and confusion categories.Source: §3.2.4 · pp. 4–5

4. Empirical Results

The section characterizes QuixBugs, measures how often ten repair tools produce test-suite-adequate patches, and assesses patch correctness and overfitting using three automated techniques. It reports variation in repair outcomes and assessment performance, with all three techniques missing some overfitting patches.

4.2. Results for RQ2: Repairability of QuixBugs

  • The ten tools generated 338 unique patches after 1,132 duplicates were removed, repairing 16/40 programs with test-suite-adequate patches.The patches covered 10/17 bug types.Source: Figure 1 · p. 7, §4.2 · pp. 8–9

4.1. Results for RQ1: QuixBugs Benchmark Analysis

  • QuixBugs includes 17 bug types and six failure symptoms; programs range from 9 to 67 LOC, sometimes have non-trivial time or space complexity, and 15 programs have no passing tests.Source: §4.1 · pp. 5–7

4.2. Results for RQ2: Repairability of QuixBugs

  • Five of the 16 repaired programs had only failing tests; generate-and-validate tools repaired some such programs, while synthesis-based approaches require passing tests.Seven bug types were not repaired; the reported barriers included missing repair operators or fixing ingredients and limitations handling multi-location fixes.Source: §4.2 · pp. 8–9
  • Repairability was 47.34% (187/395) on Defects4J versus 40% (16/40) on QuixBugs, while repair failure rates were 21.08% versus 4.31%, respectively.Duplicated patches were 51% (19,019/37,224) on Defects4J and 77% (1,132/1,470) on QuixBugs.Source: §4.2 · p. 9

4.3. Results for RQ3: Manual Patch Correctness Assessment

  • 53.3% (180/338) of test-suite-adequate patches were overfitting, while 158 were correct and 7/40 buggy programs were correctly repaired by manual assessment.The resulting QuixBugs repair rate was 17.5%.Source: Figure 2 · p. 10, §4.3 · p. 10
  • Cardumen correctly repaired three programs, more than any other tool, and all ten tools correctly repaired at least one program.Across tools, seven unique programs were correctly repaired; the tools were complementary, and outcomes were mixed across approaches.Source: Figure 3 · p. 10, §4.3 · p. 10

4.4.1. RQ4a: Patches classified as overfitting by automated patch assessments

  • RGTEvosuite classified 174/338 patches as overfitting, RGTInputSampling 115/338, and GTInvariants 289/338.GTInvariants’ high count included 118 LIS patches classified as overfitting, while the other two techniques classified none from LIS that way.Source: Table 4 · p. 11, §4.4.1 · p. 11
  • RGTEvosuite correctly classified 174/180 manually assessed overfitting patches, while all three automated techniques agreed with the manual assessment on 105 overfitting patches.GTInvariants classified 125 correct patches as overfitting, and every overfitting patch identified by RGTInputSampling was also identified by RGTEvosuite.Source: §4.4.1 · p. 11
  • The techniques reached consensus on 9/16 buggy programs, including overfitting diagnoses for three, but manual review found an overfitting NEXT PERMUTATION patch among five programs judged free of overfitting.The five-program consensus on absence of overfitting therefore did not match the manual assessment in every case.Source: §4.4.1 · pp. 11–12

4.4.2. RQ4b: Accuracy of automated patch assessments

  • 98.2%, 80.8%, and 58.3% were the accuracy rates of RGTEvosuite, RGTInputS ampling, and GTInvariants, respectively, making RGTEvosuite the most accurate technique.Table 5 reports the accuracy comparison; the prose identifies RGTEvosuite as the best-performing technique.Source: Table 5 · p. 12, §4.4.2 · pp. 12–13
  • RGTInputS ampling produced 65 false negatives, and no technique found every overfitting patch; generated tests can miss inputs that expose incorrect behavior.For NEXT PERMUTATION, tests from RGTEvosuite and RGTInputS ampling missed repeated list values that distinguish JMutRepair’s “>=” patch from the ground-truth “>” patch.Source: §4.4.2 · p. 12
  • GTInvariants had 125 false positives and 56.7% precision (164/289), while RGTEvosuite and RGTInputS ampling were 100% precise; overly specific invariants and new exit points caused false positives.An invariant can capture a test-specific value rather than a full range, or fail at a newly added program exit point.Source: §4.4.2 · p. 12
  • In QUICKSORT, GTInvariants classified semantically equivalent patches both as correct and overfitting because redundant return statements added exit points where captured invariants did not hold.The paper notes this is a caveat for assessing patches from genetic-programming tools that often add statements with exit points.Source: §4.4.2 · p. 13

5. Threats to Validity

The study’s manual correctness assessment may misclassify patches, while bugs in repair tools may leave some QuixBugs programs unrepaired. The authors note that QuixBugs’ familiar algorithms and short programs make manual assessment less error-prone than for Defects4J and more complex benchmarks.

Threats to Validity

  • Manual correctness assessment may misclassify patches through lack of expertise or mistakes; making patches and analyses public lets other researchers assess them.The authors describe public availability as the best mitigation for this threat.Source: §5 · p. 13
  • Manual assessment is less error-prone for QuixBugs than for Defects4J and more complex benchmarks because its algorithms are familiar and its programs are short.These features make generated patches easier to read, debug, and understand.Source: §5 · pp. 13–14
  • Tool bugs may make the reported repairability of QuixBugs an under-estimate.The authors identify this as a construct-validity threat because faulty tools may fail to discover possible patches.Source: §5 · p. 14

6. Discussion

QuixBugs offers findings beyond previously used benchmarks, including repair behavior and patch assessment results. The discussion also identifies substantial repair gaps and limitations in current patch-generation approaches.

6. Discussion

  • 7 of 40 (17.5%) QuixBugs programs are correctly repaired, and the authors attribute the higher rate than Defects4J and IntroClassJava to smaller programs and search spaces.The reported rates are 8.1% and 9.1% higher than for Defects4J and IntroClassJava, respectively.Source: §6 · p. 14
  • Generate-and-validate approaches can repair programs with only failing tests, whereas synthesis-based approaches cannot, a case absent from other benchmarks.Source: §6 · p. 14
  • RGTEvosuite is the most effective automated patch-assessment technique in the study, identifying 98.2% of overfitting patches.Source: §6 · p. 14
  • The study confirms both the prevalence of overfitting patches and that generate-and-validate and synthesis-based approaches work on different bugs.Source: §6 · p. 14
  • 33 of 40 buggy programs remain unrepaired with correct patches, including GCD, which has a simple one-line fix.Source: §6 · p. 14
  • Genetic-programming generate-and-validate approaches commonly produce complex repair code with redundant code repeated in multiple locations, hindering patch understanding.Source: §6 · p. 14
  • High-granularity repair operations are ineffective for finer-grained bugs such as variable swaps or incorrect reference-variable replacements.Source: §6 · p. 14
  • Repair tools could benefit from more diverse fixing ingredients, including new operators, repair patterns beyond buggy-program ingredients, and synthesis mechanisms for method invocations.The study found no patches using invisible method invocations.Source: §6 · p. 14

7. Related Work

Related work situates QuixBugs among established bug benchmarks and compares prior patch-assessment approaches. The paper distinguishes its assessment of QuixBugs patches and its larger-scale evaluation of invariant-based assessment.

7.1. Datasets of Bugs

  • Prior studies use a range of bug benchmarks, and a large-scale study that included QuixBugs did not assess its generated patches.This study reports being the first to assess 338 QuixBugs patches.Source: §7.1 · pp. 14–15

7.2. Patch Correctness Assessment

  • DiffTGen uses Evosuite-generated tests to detect behavioral differences between generated patches and human-written patches.Source: §7.2 · p. 15
  • PATCH-SIM and TEST-SIM heuristically assess correctness by comparing execution similarity before and after patches, while Opad and Fix2Fit target crashes or memory-safety problems and cannot apply to QuixBugs.Source: §7.2 · p. 15
  • Unlike static template-based assessment, this study dynamically captures runtime invariants; its invariant-based assessment covers 338 patches versus 96 and measures accuracy and false positives.Source: §7.2 · p. 15

8. Conclusion

The study evaluates ten repair tools on QuixBugs and compares three automated patch-assessment techniques over 338 generated patches. It finds that programs with only failing tests can be repaired and RGTEvosuite has the highest accuracy at discarding overfitting patches.

8. Conclusion

  • The study compares three automated patch-assessment techniques over 338 generated patches and examines their accuracy and false positives.Source: §8 · p. 15
  • Programs with only failing test cases can be repaired.Source: §8 · p. 15
  • RGTEvosuite has the highest accuracy among the three considered techniques in discarding overfitting patches.Source: §8 · p. 15
  • The 338 patches and their correctness labels provide an asset for future studies of overfitting in automatic program repair.Source: §8 · p. 15
Loading 1805.03454v4…