PaperlayerView exact revision on arXiv

Source-linked AI summary

Test Case Generation for Program Repair: A Study of Feasibility and Effectiveness

Zhongxing Yu, Matias Martinez, Benjamin Danglot, Thomas Durieux, Martin Monperrus

arXiv:1703.00198v1cs.SE

TL;DR

Test suites are often incomplete, so patches that pass them can still overfit and fail to generalize. The paper proposes two approaches for incorporating generated tests into repair and evaluates them on Defects4J bugs. The tests changed patches but were not effective at turning incorrect patches into correct ones.

  • Problem

    Test suite based repair relies on test suites that are typically inadequate to specify expected behavior completely, allowing patches that pass tests but fail to generalize.

    Source: §1 · p. 1, §2.1 · p. 2

  • Method

    The paper proposes MinImpact for generate-and-validate repair and UnsatGuided for synthesis-based repair, and evaluates them on 224 Defects4J bugs.

    Source: §1 · p. 1, §5 · p. 10

  • Results

    Test generation changed the resulting patch, but was quite ineffective at turning incorrect patches into correct ones.

    Source: §1 · p. 2, §5 · p. 10

  • Takeaways & Limitations

    The results show that generated tests can influence repair, but only one new correct patch was found, which the authors describe as not particularly effective.

    Source: §4.8 · p. 10

    The study covers 224 faults from four Defects4J Java programs and uses jGenProg and Nopol as representatives, so results may not hold for other benchmarks.

    Source: §4.9 · p. 10

Abstract

from arXiv · show

Among the many different kinds of program repair techniques, one widely studied family of techniques is called test suite based repair. Test-suites are in essence input-output specifications and are therefore typically inadequate for completely specifying the expected behavior of the program under repair. Consequently, the patches generated by test suite based program repair techniques pass the test suite, yet may be incorrect. Patches that are overly specific to the used test suite and fail to generalize to other test cases are called overfitting patches. In this paper, we investigate the feasibility and effectiveness of test case generation in alleviating the overfitting issue. We propose two approaches for using test case generation to improve test suite based repair, and perform an extensive evaluation of the effectiveness of the proposed approaches in enabling better test suite based repair on 224 bugs of the Defects4J repository. The results indicate that test case generation can change the resulting patch, but is not effective at turning incorrect patches into correct ones. We identify the problems related with the ineffectiveness, and anticipate that our results and findings will lead to future research to build test-case generation techniques that are tailored to automatic repair systems.

1. INTRODUCTION

Test suite based repair can produce patches that pass available tests but fail to generalize. The paper studies two ways of using generated tests in repair and evaluates them on Defects4J bugs.

1. INTRODUCTION

  • MinImpact targets generate-and-validate repair, while UnsatGuided targets synthesis-based repair.The approaches use generated tests in ways tailored to each technique’s specificity.Source: §1 · pp. 1–2
  • Test suites are incomplete input-output specifications, so patches that pass them may still be incorrect and fail on other test cases.The paper calls patches overly specific to the used test suite and unable to generalize “overfitting patches.”Source: §1 · p. 1
  • The evaluation covers 224 Defects4J bugs, and the paper presents its study as the first systematic, large-scale investigation of test generation for repair.Defects4J is described as a repository of real-life Java bugs.Source: §1 · pp. 1–2
  • Generated tests changed repair outputs but had little impact on patch correctness or on discarding overfitting patches.The authors also report that generated tests cannot be fed naively to repair systems and that the overhead is acceptable.Source: §1 · p. 2
  • The paper analyzes generated tests and characterizes overfitting as part of its contribution.It also identifies two approaches for incorporating generated tests into test suite based repair.Source: §1 · p. 2

2. RELATED WORK

Prior work includes generate-and-validate and synthesis-based repair, while studies report that test-suite patches often overfit. The related work also reviews automatic test generation, including Java tools that generate assertions for current program behavior.

2.1 Test Suite Based Program Repair

  • Generate-and-validate systems search for candidate patches and then test them, whereas synthesis-based systems derive repair constraints from tests and solve them.Examples include GenProg and jGenProg for generate-and-validate, and SemFix and Nopol for synthesis-based repair.Source: §2.1 · p. 2
  • Studies report substantial overfitting: among 47 bugs fixed by jGenProg, jKali, and Nopol, only 9 were correctly fixed.Other cited studies found functionality deletion or failures to generalize among generated patches.Source: §2.1 · p. 2
  • Because test suites are rarely exhaustive, patches that satisfy them may still break untested desired functionality.Prior studies cited in the paper describe overfitting in test suite based repair.Source: §2.1 · p. 2

2.2 Automatic Test Case Generation Tool

  • Java test generation includes Randoop’s feedback-directed random testing and EvoSuite’s search-based approach, which targets a class and generates assertions for current behavior.EvoSuite derives suites that maximize code coverage.Source: §2.2 · pp. 2–3

3. APPROACH

The approach uses generated tests to guide test-suite-based repair, while accounting for the possibility that generated tests preserve buggy behavior. It proposes MinImpact for generate-and-validate repair and UnsatGuided for synthesis-based repair.

3.1.2 The bug-exposing test problem

  • Generated tests can encode buggy behavior, so forcing every generated test to pass can make a repaired patch incorrect.A correctly patched program may instead fail on bug-exposing tests.Source: §3.1.2 · p. 3

3.1.3 Overfitting

  • A-Overfitting changes only some buggy inputs, while B-Overfitting also breaks some correct inputs; the figure contrasts patches by how closely their impact matches a perfect patch.The input domain is divided into buggy and correct portions, and a perfect patch changes behavior throughout the buggy portion without changing correct behavior.Source: §3.1.3 · p. 3, §3.1.1 · p. 3, Figure 1 · p. 3

3.2 MinImpact: Minimizing the Behavioral Impact for Generate-and-Validate Techniques

  • MinImpact generates tests for files changed by each test-adequate patch, then returns the patch with the fewest failing generated tests.It compares multiple patches; a sole generated patch is returned directly, while no generated patches yields an empty patch.Source: §3.2 · p. 4

3.3 UnsatGuided: Incremental Test Suite Augmentation for Synthesis-based Repair

  • UnsatGuided is intended to strengthen synthesis constraints using generated tests, discarding tests whose constraints contradict those from the manual suite.Such contradictions are treated as evidence that a generated test may expose buggy behavior.Source: §3.3 · p. 5
  • UnsatGuided adds generated tests one at a time and retains a test when synthesis returns a nonempty patch; otherwise it removes that test.Each synthesis attempt receives twice the time used to generate the initial patch.Source: §3.3 · p. 5

3.4 Analysis of Algorithms

  • MinImpact may trade reduced behavioral impact on correct inputs for selecting patches that fix fewer buggy inputs represented by generated tests.The analysis distinguishes generated tests in Icorrect from those in Ibug and notes that the latter can encourage overfitting to specific buggy inputs.Source: §3.4 · pp. 5–6
  • UnsatGuided incrementally keeps generated tests whose constraints permit a synthesized patch, but weak initial constraints may let bug-exposing tests remain.When initial repair constraints are strong, contradictions can identify and discard bug-exposing tests; with weak constraints, those tests may be kept and preserve buggy behavior.Source: §3.4 · p. 6

3.5 Technical Insights

  • Both approaches generate tests for files involved in the initial patch, and the process removes flaky tests because the approaches assume determinism.UnsatGuided’s test order matters; the current ordering uses involved-file size, then generated-file creation order and test order, with potential to prioritize tests by their ability to improve constraints left for future work.Source: §3.3 · p. 5, §3.5 · p. 6

4. EXPERIMENTAL EVALUATION

The evaluation asks whether the approaches change patches, affect correctness, depend on bug-exposing tests, and add time overhead. It uses selected Defects4J Java faults, two repair systems, and EvoSuite.

4. EXPERIMENTAL EVALUATION

  • The study evaluates four questions: whether patches change, whether correctness changes, the importance of bug-exposing tests, and time overhead.The benchmark is Defects4J, a database of real faults in real-world Java programs.Source: §4 · p. 6, §4.1.1 · p. 6

4.1.1 Programs

  • The evaluation uses 224 faults from four Defects4J projects, excluding Mockito and Closure faults for framework stability and test-execution constraints.The study excludes 38 Mockito faults and 133 Closure faults; the latter use scripts rather than standard JUnit tests.Source: §4.1.1 · p. 6

4.1.2 Test Suite Based Repair Systems

  • jGenProg and Nopol represent generate-and-validate and synthesis-based Java repair, respectively.The authors select them as open-source systems targeting modern Java; PAR was unavailable and Jaff did not support the required modern Java versions.Source: §4.1.2 · p. 6

4.1.3 Automatic Test Case Generation Tool

  • EvoSuite generates the additional Java unit tests and can target a specific class, as required by the proposed approaches.The paper describes EvoSuite as state of the art to the authors’ knowledge.Source: §4.1.3 · pp. 6–7

4.2 Experimental Setup

The setup repeats randomized test generation across seeds, manually assesses patch correctness against human fixes, and imposes time limits to keep the experiments manageable.

4.2 Experimental Setup

  • Each of 224 faults is evaluated with both approaches; EvoSuite runs 30 seeds and jGenProg uses the same seed, except two faults receive 10 seeds.The two reduced-seed cases are Chart 26 and Math 24 because Nopol with UnsatGuided could take over 13 hours per EvoSuite seed.Source: §4.2 · p. 7
  • Two authors independently compare generated patches with human patches, counting only exact or semantically equivalent patches as correct.Reported correctness is based on their agreement, and analysis time ranges from minutes to hours.Source: §4.2 · p. 7
  • The time budgets are 120 minutes for MinImpact and 40 minutes for UnsatGuided; experiments run on Grid’5000 and a 200-node cluster, respectively.The authors reduce seeds for two costly Nopol-plus-UnsatGuided cases to manage runtime.Source: §4.2 · p. 7
  • Experimental materials include the programs, EvoSuite tests, generated patches, and the authors’ correctness analyses.The paper says these materials and results are available at.Source: §4.2 · p. 7

4.3 Result Presentation

This section explains how Table 3 presents Nopol+UnsatGuided results and clarifies that changed patches can still be correct when semantically equivalent to human patches.

4.3 Result Presentation

  • Table 3 reports Nopol+UnsatGuided results only for bugs with test-suite-adequate patches found by plain Nopol.Its columns include removed-test and contradiction counts, plus patch change and correctness ratios.Source: Table 3 · p. 8, §4.3 · p. 8
  • The table reports results for Nopol and Nopol+UnsatGuided, including generated-test counts, repair time, and patch change and correctness ratios.The ratios are reported over runs with different EvoSuite seeds.Source: §4.3 · pp. 7–8
  • A patch that differs from the initial repair can still be correct if it is semantically equivalent to the human patch.Source: §4.3 · p. 8

4.4 RQ1: Changed Patches

Generated tests often change repair outputs, but the experiments found little improvement in correctness overall: MinImpact made no improvement, while UnsatGuided found one new correct patch.

4.4 RQ1: Changed Patches

  • Across one-seed executions for initially repairable buggy versions, MinImpact changed 615/810 jGenProg patches and UnsatGuided changed 702/1220 Nopol patches, relative to jGenProg and Nopol alone, respectively.Source: §4.4 · p. 8

4.5.1 jGenProg+MinImpact

  • MinImpact changed 21 incorrect jGenProg patches, but the resulting patches were still incorrect.Source: §4.5.1 · p. 9
  • For Math 50, MinImpact retained the correct patch in 17 executions but produced an incorrect overfitting patch in 13; for Math 70, the two test-adequate patches included one correct and one incorrect patch.The Math 70 incorrect patch failed an average of 2.8 generated tests, versus 1.1 for the correct patch.Source: §4.5.1 · p. 9

4.5.2 Nopol+UnsatGuided

  • For Math 85, UnsatGuided produced a correct patch in 21 EvoSuite-seed runs; it changed 30 other initially incorrect patches, which remained incorrect, while preserving Nopol's three correct patches.Source: §4.5.2 · p. 9
  • Overall, generated tests had little positive impact on correctness: MinImpact made no improvement, while UnsatGuided helped Nopol find one new correct patch.Source: §4.5.2 · p. 9

4.6 RQ3: Impact of Bug-exposing Tests

Bug-exposing generated tests complicate repair because a correct patch may fail them; the experiments warn against treating every such failure as evidence of overfitting.

4.6 RQ3: Impact of Bug-exposing Tests

  • All 30 jGenProg+MinImpact runs correctly fixed Math 53, despite an average of 1.1 failing EvoSuite tests.Ignoring bug-exposing tests would likely discard this correct patch.Source: §4.6 · p. 9
  • Without special handling for bug-exposing tests, generated tests can cause repair techniques to discard correct patches.Source: §4.6 · p. 9
  • Lang 44 and Lang 58 were always correctly repaired by Nopol+UnsatGuided despite nonzero average contradiction-test counts.Supplying all generated tests directly to Nopol could leave these bugs without patches.Source: §4.6 · p. 9

4.7 RQ4: Time Overhead

MinImpact's overhead depends on its allocated time budget, while UnsatGuided adds repair time that is under an hour for most evaluated faults but can be much larger.

4.7 RQ4: Time Overhead

  • MinImpact's time overhead depends on the allocated time budget, which was 120 minutes in this experiment.Source: §4.7 · p. 9
  • For 28 of 42 initially Nopol-repairable bugs, Nopol+UnsatGuided took at most one hour on average; for three bugs, it took more than 10 hours.Math 24 averaged 24.1 hours.Source: §4.7 · p. 10
  • UnsatGuided's average repair time was much longer than Nopol's original repair time, though it remained under an hour for most evaluated faults.Source: §4.7 · p. 10

4.8 Discussion

Generated tests influenced repairs but yielded only one new correct patch in Defects4J. The discussion attributes limited effectiveness partly to bug-exposing tests and outlines behavioral profiling and patch-impact reasoning as possible directions.

4.8 Discussion

  • Only one new correct patch was found on Defects4J, despite demonstrating that generated tests can influence repair.The authors describe this outcome as not particularly effective.Source: §4.8 · p. 10
  • Generated tests may fall in Ibug, where no automated oracle distinguishes bug-exposing inputs from inputs in Icorrect.Neither MinImpact nor UnsatGuided handles bug-exposing tests well enough to avoid overfitting to specific Ibug points.Source: §4.8 · p. 10
  • Behavioral profiling could estimate whether generated tests are bug-exposing by measuring their behavioral distance from manually written failing tests.Tests behaviorally close to failing tests may lie in Ibug, while more distant tests may lie in Icorrect.Source: §4.8 · p. 10
  • Patch-impact reasoning offers another direction: very small Ipatch may indicate A-overfitting, while unusually large Ipatch may indicate B-overfitting.The authors connect direct reasoning about Ipatch to research on making generated patches resemble human patches.Source: §4.8 · p. 10

4.9 Threats to Validity

The evaluation has boundaries in its benchmarks, repair systems, test generator, and manual correctness assessment. The authors note that these choices may limit generalization and that manual assessment may introduce errors.

4.9 Threats to Validity

  • The study covers 224 faults in four Defects4J Java programs, so results may not hold for other benchmarks.The authors also identify jGenProg and Nopol as representatives of two repair categories and caution that findings may not generalize to other systems.Source: §4.9 · p. 10
  • Only EvoSuite was used for automatic regression-test generation, limiting the evaluation to one test-generation tool.The authors characterize EvoSuite as a state-of-the-art Java unit-test generator.Source: §4.9 · p. 10
  • Manual patch assessment may introduce errors, although two authors checked and confirmed the reported results.The human patch served as the correctness baseline and helped identify the bug's root cause.Source: §4.9 · p. 10

5. CONCLUSION

The paper evaluates two approaches that use generated tests to improve test suite based repair, finding that they can change patches but are ineffective at turning incorrect patches into correct ones. The authors anticipate future work on test generation tailored to repair systems.

5. CONCLUSION

  • Test case generation can change the resulting patch, but is quite ineffective at turning incorrect patches into correct ones.The paper proposes two approaches and evaluates them in a large-scale experiment.Source: §5 · p. 10
  • The study investigates whether generated test cases can alleviate overfitting in test suite based repair.The approaches use test case generation to improve test suite based repair techniques.Source: §5 · p. 10
  • The authors anticipate future research on test-case generation techniques tailored to automatic repair systems.Source: §5 · p. 10
Loading 1703.00198v1…