Harnessing Evolution for Multi-Hunk Program Repair

1 INTRODUCTION

• Most APR techniques target single-hunk bugs, although 64% of Defects4J bugs and 76% of Bugs.jar bugs require multi-hunk patches.A simple expansion to search general multi-hunk patches would greatly expand the repair search space.Source: §1 · p. 1
• Evolutionary siblings are similar-looking code in similar contexts expected to undergo similar changes; this approach is distinct from clone detection and orthogonal to donor–donee repair.Unlike repairs relying only on test spectra, it can include locations outside their scope.Source: §1 · pp. 1–2
• Identifying evolutionary siblings is difficult because they are not simply clones, test spectra can miss instances, and imprecise sets risk partial repairs or infeasible searches.The method must balance missing true siblings against including too many candidates.Source: §1 · p. 2
• Hercules uses test spectra to seed sibling identification, syntactic and semantic-context similarity to find candidates, and revision history to filter false positives.The identified siblings are then repaired simultaneously with substantially similar patches, modulo namespace variations.Source: §1 · p. 2
• Hercules correctly fixed 49 Defects4J bugs, the highest count for any individual APR technique to date, including 15 multi-hunk bugs and 13 bugs no other technique had fixed.The evaluation is on Defects4J.Source: §1 · p. 2

2.1 Terminology & Definition

• A single-hunk bug needs edits at one location or contiguous locations; a multi-hunk bug needs edits at multiple non-contiguous locations.A repair location is a statement targeted for modification, deletion, or insertion, and need not be the actual buggy location.Source: §2.1 · p. 2
• A repair schema is an abstract transformation template, while a candidate patch is a concrete modification produced by instantiating that schema.The repair space is the pool of generated candidate patches, counted by its number of patches.Source: §2.1 · p. 2
• A plausible patch passes the test suite but may still be incorrect; correctness is judged by manual comparison with the developer-provided patch for semantic equivalence.The paper classifies a patch as correct when it is semantically equivalent to the developer patch.Source: §2.1 · pp. 2–3

2.2 Generate and Validate Repair Approach

• Generate-and-validate repair ranks repair locations, applies repair schemas to generate candidate patches, then tests candidates and outputs those passing the suite as plausible patches.Validation may be narrowed first to failing tests before running the complete suite.Source: §2.2 · p. 3

3 MOTIVATING EXAMPLE

• For Math-24, the developer changed two return sites from returning current to calling best(current,previous,isMin), producing similar edits at both locations.The bug report said Brent Optimizer did not always report the best point.Source: §3 · p. 3
• The two repair sites are not traditional clones: their surrounding syntax differs, and statement-level matching would produce many false positives.The example yields 10 matches for “return current,” with more matches when identifiers are abstracted.Source: §3 · p. 3
• Hercules compares statements and their reaching-definition context, which can be physically distant and interleaved yet make the repair sites similar in use.For the example, one reaching definition is 4 lines from its repair site and the other is 125 lines away.Source: §3 · p. 3
• The failing test covers only the second site; revision history shows the uncovered first site was never modified independently, supporting similar repairs at both.Hercules uses revision history to assess whether candidate locations evolved independently.Source: §3 · p. 3
• More than 14,000 valid repair expressions per location and 18 valid invocations yield 324 combinations for two sites, motivating simultaneous sibling repair and candidate ranking.The example illustrates why naive multi-location search would be large.Source: §3 · pp. 3–4

4.1 An Overview

• Hercules adds evolutionary-sibling repair localization to conventional repair, then abstracts mapped variables to apply a repair schema simultaneously across locations.It also continues with a single location when no sibling is found.Source: §4.1 · p. 4

4.2.1 Preliminaries.

• Hercules models programs as ASTs and defines spectra, repair locations, relevant context, and edit history for its sibling analysis.A program spectrum contains statement nodes exercised by failing tests.Source: §4.2.1 · pp. 4–5

4.2 Identification of Evolutionary Siblings

• Evolutionary siblings are repair locations with similar contexts and edit histories, at least one of which is exercised by a failing test.Hercules identifies them through location similarity, relevant-context similarity, and version-history analysis.Source: §4.2 · p. 4, §4.2.1 · p. 5

4.2.2 Step-1: Identification of Similar Repair Locations.

• Hercules compares AST repair locations, extracts reaching-definition context, checks context similarity, and uses version history to revise sibling candidates.The history analysis adds similar locations with matching context and removes candidates lacking similar edit histories.Source: §4.2.2 · p. 5, §4.2.3 · p. 6, §4.2.4 · p. 6

4.3 Generation of Candidate Patches

• For multiple repair locations, Hercules abstracts mapped variables, instantiates the same repair schema at each location, then restores original variables.Simultaneous instantiation keeps the repair space comparable to tools generating only single-hunk patches.Source: §4.3 · p. 7

4.4 Ranking of Candidate Patches and Validation

• Hercules ranks candidate patches, tests failing cases first, then runs regression tests and reports a patch when both pass.It validates selected top-ranked candidates one at a time.Source: §4.4 · p. 7

5.1 Implementation

• Hercules is implemented in Java with fault localization, source-code and version-history analysis, simultaneous schema application, and machine-learning patch ranking.Its schemas include null checks, method invocations, and if conditions.Source: §5.1 · p. 7

5.2 Dataset

• The evaluation uses the five Defects4J subjects Math, Lang, Chart, Time, and Closure.Source: §5.2 · p. 7

5.3 Training Hercules

• Hercules trains its patch-ranking model on Bugs.jar, which contains 1,158 bugs from eight Apache projects, excluding Apache Commons Math to keep training and testing mutually exclusive.Source: §5.3 · p. 7

5.4 Research Questions

• The research questions assess sibling localization against clone detection, single- and multi-hunk repair, comparison with state-of-the-art tools, and component contributions.Source: §5.4 · p. 7

5.5 Experimental Configurations

• Experiments used a 0.8 tree-similarity threshold, the top 200 repair locations, 50 candidate patches per schema, and a five-hour timeout.The virtual machines had a dual-core 3.6 GHz processor and 4 GB memory, running Ubuntu 16.04 LTS and Java 7.Source: §5.5 · p. 7

6.1 RQ1: Effectiveness of Repair Localization

• 84% (129/154) of bugs had correctly localized repair locations with Hercules, versus 26% (40/154) with Deckard; on multi-hunk bugs, the counts were 15/24 and 2.Source: Table 1 · p. 8, §6.1 · p. 8

6.2 RQ2: Generalizing Single-hunk Repair

• 49 correct patches included 34 single-hunk and 15 multi-hunk fixes; Hercules-SH produced 34 correct patches, and simultaneous repair added only two incorrect patches.Hercules lost no single-hunk bug due to simultaneous repair.Source: Table 2 · p. 8, §6.2 · p. 8
• Hercules fixed multi-hunk bugs ranging from 2 to 7 hunks.Source: Figure 3 · p. 8, §6.2 · p. 8

6.3 RQ3: Hercules vs. State of the art

• 9 unique multi-hunk bugs were fixed by Hercules but not SimFix or ACS; across all bugs, Hercules fixed 13 that no existing approach fixed.Source: §6.3 · p. 8
• 49 correct patches made Hercules the top tool, 15 more than the next best tool, SimFix.Table 3 compares correct and incorrect patches generated by the evaluated tools.Source: §6.3 · p. 8, Table 3 · p. 9

6.4 RQ4: Contribution of Various Components of Hercules

• On the 49 bugs Hercules correctly fixed, fixed-size context lost 11, ignoring version history lost six, and incremental repair lost nine.The authors conclude that all three features contributed to fixing multi-hunk bugs.Source: §6.4 · p. 9

• Only multi-hunk bugs requiring substantially similar patches are in scope; most multi-hunk bugs remain beyond Hercules and other APR tools.The authors call for future work on other classes of multi-hunk repair.Source: §7 · pp. 9–10
• Major repository restructurings can disrupt revision-history analysis, and its heuristics and sampled manual checks do not guarantee soundness.The authors manually inspected a few sampled bug histories to check the heuristics.Source: §7 · p. 10
• Evaluation on Defects4J’s five subject systems cannot capture the variety of Java applications and bugs; validation on other subjects remains necessary.Source: §7 · p. 10
• Repair results depend on the baseline APR tool, so a different or improved baseline could change them; Hercules’s C/C++ efficacy remains uninvestigated.Source: §7 · p. 10

Automatic program repair

• APR approaches mine repair fragments, learn abstract repair spaces, or generate multi-hunk patches; Hercules instead uses similar code to find locations for concurrent repair.Fragment-mining methods search for compatible code to contribute to a repair, whereas Hercules seeks evolutionary siblings.Source: §8 · p. 10

APR - Learning abstract repair spaces

• Hercules’s sibling identification determines where repair should occur, complementing prior work that informs how to repair at a location.Source: §8 · p. 11

APR - Multi-hunk repair

• Angelix synthesizes patches independently at fault-localized locations, while Hercules derives sibling relationships to localize more accurately and repair locations simultaneously.The authors say Hercules can also repair locations not directly implicated by the test spectrum.Source: §8 · p. 11

Code Clone Detection

• Hercules’s evolutionary siblings may or may not be traditional code clones, despite the work’s inspiration from clone detection and clone genealogies.Source: §8 · p. 11

Systematic Edits

• Systematic-edit tools learn a common abstract edit script from examples, whereas Hercules does not rely on examples to identify sibling locations.Source: §8 · p. 11

• The technique targets multi-hunk bugs needing substantially similar patches and identifies evolutionary siblings using test-spectrum, syntactic and semantic code-similarity, and revision-history information.Source: §9 · p. 11
• 49 Defects4J bugs were fixed by Hercules, the highest total for any individual APR technique to date; this includes 15 multi-hunk bugs and 13 bugs no other technique had fixed.Source: §9 · p. 11
• The authors characterize the results as a small but important step toward practical deployment of APR tools.Source: §9 · p. 11