Automated Program Repair and Fault Localisation

GenProg was reported to fix 55 of 105 real defects in C programs. When the patches were re-examined, GenProg had produced a correct patch for only 2 of them. Most of the reported patches did not even pass the validation tests once infrastructure errors were fixed, and the overwhelming majority of incorrect ones were equivalent to deleting functionality. A deliberately naive system that only deleted code, Kali, produced at least as many correct patches (Qi et al., 2015, An Analysis of Patch Plausibility and Correctness for Generate-and-Validate Patch Generation Systems, ISSTA 2015).

That result frames the whole field. Repair is two problems, finding where the bug is and producing a change that is actually right, and a test suite is a weak judge of the second.

Where is the bug

Spectrum-based fault localisation (SBFL) uses nothing but coverage. Run the tests, record which statements each test executes, and score each statement \(s\) with four counts: \(e_f\) and \(e_p\), the failing and passing tests that execute \(s\); \(n_f\) and \(n_p\), those that do not. Let \(F = e_f + n_f\) be the total number of failing tests.

Tarantula scores \(s\) by the fraction of failing tests that cover it relative to passing ones (Jones & Harrold, 2005, ASE). The Ochiai coefficient, a similarity measure borrowed from biology, proved more accurate in Abreu, Zoeteweij and van Gemund's comparison (Abreu et al., 2007, On the Accuracy of Spectrum-based Fault Localization, TAIC PART):

It rewards statements executed by many failing tests and penalises statements that passing tests also execute. Take two failing and 98 passing tests. Statement A is run by both failing tests and by 10 passing ones: \(2/\sqrt{2 \times 12} \approx 0.41\). Statement B is run by one failing test and no passing test: \(1/\sqrt{2 \times 1} \approx 0.71\). The entry point, run by everything: \(2/\sqrt{2 \times 100} \approx 0.14\). B tops the ranking, which is right if the two failures have different causes and wrong if they share one in A.

Whether such rankings help people is contested. Evaluations usually report how much code a developer would examine before reaching the fault, which quietly assumes the developer reads the list in order and recognises the bug on sight. Parnin and Orso's two user studies found that several assumptions of this kind did not hold in practice (Parnin & Orso, 2011, Are Automated Debugging Techniques Actually Helping Programmers?, ISSTA). Repair tools make a more natural customer, because they do consume the list mechanically.

Generate and validate

GenProg searched over edits to the abstract syntax tree with genetic programming, using the test suite as fitness and localisation to decide where to mutate (Le Goues et al., 2012, GenProg, IEEE TSE 38(1)). Its acceptance criterion defines the central distinction. A patch is plausible if it passes the validation tests and correct if it matches the developer's intent.

The gap between them is overfitting. Smith et al. repaired programs with one test suite and evaluated the patches on an independent one, finding that the tools were unlikely to improve the proportion of independent tests passed and that patch quality tracked the coverage of the repair suite. They also found novice developers overfit, and the tools did no worse than them (Smith et al., 2015, Is the Cure Worse Than the Disease?, ESEC/FSE). Deleting the code that makes a failing test fail is the degenerate optimum of "make the tests pass".

The LLM pipeline is the same loop

Agentless replaced autonomous agents with a fixed three-phase pipeline: hierarchical localisation that narrows from files to classes and functions to edit locations; repair that samples several candidate diffs; and validation that runs reproduction and regression tests to select one. It resolved 32.00% of SWE-bench Lite at $0.70 per issue, beating more elaborate agents at the time (Xia et al., 2024, Agentless, arXiv:2407.01489). Structurally it is localisation plus generate-and-validate with a language model at each stage, and the ordering still matters: a repair step cannot fix code the localiser never surfaced. The scoring side is covered in SWE-bench and agentic coding evaluation, and the in-loop use of tests in test-driven agents.

When it breaks

Omission faults have no line to rank. SBFL scores executed statements. A missing null check or an absent branch is not in the spectrum, so the true fix location may never appear in the list.

Coincidental correctness dilutes the signal. Passing tests often execute the faulty statement without triggering the fault, inflating \(e_p\) and pushing the culprit down the ranking.

Multiple faults interfere. Failures from two different bugs blend their spectra, as the worked example shows.

Plausibility is cheap and correctness is undecidable in general. A repair tool can only check the oracle it has. LLM repair adds new routes to the degenerate optimum: editing the test, special-casing the input it checks, or catching and swallowing the exception. Held-out tests and human review remain the only reliable filter.