Fault Localization by Warping Failing Executions onto Passing Ones

When a test fails, the run that failed and the runs that passed usually execute much of the same code. The difference is that a loop runs a few more times, a branch is taken a little earlier, or a call happens twice. Standard spectrum-based fault localization is the default way to find the buggy line. It counts which lines the passing and failing tests cover, so it discards order and timing, which are exactly where this difference shows up. We propose to treat each execution as a signal over time and align the failing run to the passing runs using only smooth, order-preserving, invertible time warps. These are the one-dimensional version of the topology-preserving deformations used in medical image registration. A warp of this kind can stretch or compress time, which absorbs harmless differences such as a different number of loop iterations. It cannot reorder events, fold two moments onto one, or invent behavior. Whatever the warp cannot explain is a residual, and we attribute that residual to the statements where it occurs. Those statements are the suspects.

This matters because repair tools succeed or fail on localization. Liu et al. showed that roughly 33% (132 of 395) of Defects4J v1.2.0 bugs are invisible to line-level Ochiai ranking. They also showed that the repair tool kPAR fixes 18 bugs under standard localization and 36 when handed the true buggy lines (You Cannot Fix What You Cannot Find!). A separate assessment of 16 repair systems found that imprecise localization inflates the number of patch candidates by an order of magnitude (On the efficiency of test suite based program repair). The gap between 18 and 36 is the prize. Our bet is that part of it is recoverable from information that test executions already contain and that coverage counting throws away.

Core Claim

The claim is narrow and falsifiable. A large share of the difference between a failing run and nearby passing runs is a reparameterization of time: the same code path, executed with different durations. A warp that is constrained to be smooth and invertible separates that reparameterization from genuine divergence more cleanly than either of two simpler options. The first is no alignment at all, as in coverage spectra. The second is unconstrained alignment, such as dynamic time warping, which may collapse any stretch of one run onto a single point of the other and can therefore "explain away" the real fault. The local stretch of the warp is also informative in its own right, in the form of its log-derivative. A statement whose events are consistently stretched in failing runs but not in passing-to-passing alignments is a strong candidate for loop-bound and condition-boundary bugs. These are the control-heavy, token-light statements on which learned statement detectors are reported to degrade (LineVD).

Where the Idea Comes From

The method is borrowed from the deformation literature, and the borrowing has a specific role in each case. Diffeomorphic Temporal Alignment Nets aligns one-dimensional signals with continuous piecewise-affine velocity fields. Integrating such a field yields a warp that is monotone and invertible by construction, and the paper reports beating dynamic-time-warping methods on most of the UCR archive. We reuse this warp family directly. DTAN has only ever been applied to continuous sensor-style signals, and executions are discrete event streams, so the representation step below is new.

Two further papers shape the design. VoxelMorph-diff shows why the constraint matters. Unconstrained displacement predictors produce thousands of folded voxels, while integrating a velocity field leaves about 0.2 on average. That is the imaging analogue of our worry that free alignment will fold away real divergence. DisMorph learns which deformation is nuisance (scanner distortion) and which is signal (atrophy). We take its central move, defining "benign" change from data where only nuisance is present. In our case the nuisance-only data are passing-versus-passing alignments, which calibrate what normal temporal variability looks like for each statement.

Neural Mesh Flow constrains the design. It warns that soft penalties against folding over-smooth the result, which is why we impose invertibility through the warp family itself rather than through a loss term. Its genus limitation also has a direct analogue here. A warp cannot create events that were never executed, so bugs of omission will appear only as a residual at the place where the missing behavior should have occurred. We expect weaker results on that class and will report them separately.

On the software side, the closest relatives either prune discretely or ignore execution order. FLFC slices backward from the failure and scores statements by Jaccard inside the slice. SBIR fuses statement-level bug-report retrieval with spectrum rankings through unsupervised rank aggregation. MVD, LineVD, and WAVES learn statement detectors from static graphs or tokens with commit-derived labels. None of these methods aligns dynamic executions in time. Ours requires no labels and is complementary to SBIR's bug-report signal, so we can feed our ranking into its aggregator.

Research Program

The first component is representation. We restrict tracing to the top methods ranked by method-level spectrum scores, which keeps traces tractable and mirrors how practical tools already narrow their search. Within those methods we record each executed statement event. Each event is encoded as a vector that combines a learned or hashed statement-identity embedding with a few cheap dynamic features: a branch outcome bit, a loop-iteration index, and coarse summaries of the values written. Smoothing the event sequence onto a normalized time axis produces a multichannel signal per run. For each failing test we pick reference passing tests, namely the passing tests whose method-level coverage is most similar.

The second component is alignment and scoring. For a failing signal $f$ and a reference $p$, we fit a warp $\phi$ from the continuous piecewise-affine family. Because $\phi$ is the integral of a velocity field, it is guaranteed to be monotone and invertible. We fit it by minimizing $\lVert f - p\circ\phi \rVert^2$ plus a small velocity-norm prior, either per pair or with a DTAN-style network amortized across a project. The suspiciousness of statement $j$ is then

$$s(j) = \frac{1}{|E_j|}\sum_{t \in E_j} \Big( r(t) + \lambda\,\big|\log \phi'(t) - \mu_j\big| \Big),$$

In this score, $E_j$ is the set of time points at which statement $j$ executes in the failing run, $r(t)$ is the residual $\lVert f(t) - p(\phi(t))\rVert$, and $\phi'(t)$ is the local stretch. The term $\mu_j$ is the mean log-stretch that statement $j$ receives when passing runs are aligned to each other, which is the DisMorph-style calibration of benign variability. The weight $\lambda$ is tuned once per project family on held-out bugs. Scores are averaged over failing tests and reference passing tests.

The third component is integration with repair. We feed the ranking to kPAR, and to Arja through SBIR's RAFL aggregator, measuring correct fixes and patch-candidate counts.

Baselines

The naive reference point is line-level Ochiai computed with GZoltar, the configuration under which 132 of 395 Defects4J v1.2.0 bugs are invisible and kPAR fixes 18. We will reproduce it on the same bug set and tests rather than quote it.

The strongest existing method on this question is SBIR (Better Automatic Program Repair by Using Bug Reports and Tests Together). It is statement-level, unsupervised, and evaluated end-to-end with repair tools on Defects4J v2.0. Its reported result is that Arja correctly fixes 28 defects with SBIR versus 21 with standard SBFL, and that 7 defects were repaired that none of 14 prior tools had fixed. We found no reported result on Lacuna for SBIR's Top-N statement accuracy, so we will measure it ourselves on the single-file and single-line subsets that paper uses. The comparison will be fair in three ways: the same bugs, the same Arja configuration and time budget, and an equal hyperparameter tuning budget for both rankings. Beating SBIR means one of two outcomes. Our test-only ranking could exceed it on Top-1 or Top-5 statement accuracy despite using no bug report. Alternatively, adding our ranking as a third input to RAFL could raise Arja's correct fixes above SBIR's under the same budget.

We also include FLFC-style backward slicing with Jaccard as the strongest discrete-pruning competitor. Its reported numbers, 39.74% less repair time and 38.37% fewer candidate patches, come from a 10-bug C suite, so we reimplement it on Java. We also include a count-aware spectrum baseline that weights coverage by execution frequency. It captures "ran more times" without any alignment and is the cheapest way to get part of our signal.

Two ablations isolate the key ingredient. The first replaces the invertible warp with dynamic time warping on identical signals, with and without a band constraint. The second uses an unconstrained per-point displacement warp. A third ablation removes the passing-versus-passing calibration, setting $\mu_j=0$, to test the DisMorph-derived component.

Why not just…?

Why not just use spectrum counts with execution frequency? This option recovers the "loop ran more times" signal at almost no cost, and if it matches our method then the warp is unnecessary. Frequency, however, cannot tell where in a run a divergence begins, and it cannot separate a statement that runs extra times because an upstream branch went wrong from the branch itself. The count-aware baseline is in the main comparison. If it ties us on Top-5 accuracy and on the invisible-bug subset, we will report that the alignment adds nothing.

Why not just align traces with dynamic time warping or a sequence diff? This is the most serious threat. Unconstrained alignment can match a long anomalous stretch to a single reference event, absorbing the divergence into the alignment itself. The folding results in VoxelMorph-diff are the spatial analogue of this failure. The trade-off could still favor dynamic time warping on discrete traces, where DTAN's advantage on continuous signals may not transfer. The banded and unbanded variants of dynamic time warping are run on identical inputs. If a well-banded version matches us, our honest conclusion is that a bounded slope, not invertibility, is what matters.

Why not just train a statement-level detector like LineVD or MVD? These detectors need commit-derived labels, which MVD itself notes are noisy. They use no test executions and are reported on C/C++ vulnerability data rather than Java test-failure bugs. LineVD reports an F1 of 0.360 and an N5 of 0.900 on Big-Vul, but Big-Vul has no runnable tests, so it cannot host our method. We therefore do not claim to compete there. Our approach targets the test-driven repair setting that SBIR and kPAR occupy.

Why not just slice backward from the failure? Slicing helps when the fault lies on the failure's dependence chain. It discards context discretely, and it says nothing about which statement in a long slice is wrong. The FLFC reimplementation measures this directly. We expect our ranking to be most useful inside a slice, so we also test slicing followed by warping.

Decisive Checks

All experiments run on Defects4J v1.2.0, where the invisible-bug analysis and the kPAR numbers come from, and on Defects4J v2.0, where SBIR was evaluated. The metrics are Top-1, Top-3, and Top-5 statement accuracy and the rank of the first buggy line. Downstream, they are kPAR and Arja correct fixes and the number of patch candidates tried before the first correct fix, following On the efficiency of test suite based program repair.

Four results would decide the question. The first is how many of the 132 invisible bugs enter our Top-5. The second is whether the invertible warp beats both dynamic time warping variants and the count-aware spectrum, with a paired test across bugs. The third is a breakdown by fix type: we predict the largest gains on loop-bound and condition fixes and the smallest on pure omissions. The fourth is how far kPAR's correct fixes move from 18 toward 36.

The idea is falsified if the ablation to banded dynamic time warping or to frequency counts closes the gap. In that case the topology-preserving constraint is not doing the work, and the proposal reduces to "use execution order."