DOI: 10.1145/3861066 ISSN: 1049-331X

Look Back Before You Bisect: A Risk-Aware Approach for Efficient Bisection

Ali Sayedsalehi, Peter C. Rigby
Show PDF Cite

Culprit localization often relies on bisection over version history to identify the first revision that exhibits a failure. A familiar instance is

git bisect
, which applies a standard midpoint search once a known-good and known-bad boundary are available. In practice, however, bisection-based culprit localization faces two key limitations: midpoint selection assumes a uniform culprit probability over the commits in the search interval, and the workflow requires a trustworthy clean boundary even though the most recent clean revision is often unknown or costly to validate. We therefore introduce an initial phase that looks back through the sequence of commits to localize a clean commit and construct a small, effective search interval for bisection. We call this phase lookback . To estimate culprit likelihood over commit history, we use just-in-time defect prediction to assign commit-level risk scores, and then use these scores to guide both lookback and bisection. We thus model culprit localization as two coupled phases, lookback followed by bisection, and study how risk-aware lookback and risk-aware bisection together reduce the total number of localization steps needed for finding the culprit.

We provide new localization algorithms and adapt and evaluate some algorithms from previous studies, including risk-aware variants, and augment these algorithms with commit-level risk scores derived from learned risk prediction models. To train these models, we create MozillaJIT, a large just-in-time defect prediction dataset mined from Mozilla Firefox repository history, and fine-tune both LLaMA- and ModernBERT-based risk models on it, comparing their performance.

To evaluate these algorithms, we implement a simulation framework that captures the end-to-end workflow and the interaction between lookback and bisection. Using Mozilla historical regressions in this simulation, we show that accurate lookback substantially reduces end-to-end cost by shrinking the search interval, and that augmenting both phases with risk scores yields additional savings.

Across the evaluated strategies, our best end-to-end combinations achieve roughly 35% fewer localization steps than a NoLookback + StandardMidpointBisection baseline. We release our dataset and a replication package containing model training code and experimental artifacts.

More from our Archive