Statistical debugging gives you a sorted list of predicates, not a root cause. You instrument every branch and null check, run a hundred thousand executions, and the algorithm hands you a scoreboard. buffer_idx > max_len at parser.c:144 has an importance of 0.94. So does log_file != NULL at main.c:38. One of them is the bug. The other just happens to be true whenever the program crashes.

A high correlation means a predicate and a crash co-occur. It does not mean the predicate caused the crash. If every crash passes through the same cleanup path, every predicate on that path will look guilty. You need a way to separate the perpetrator from the bystanders.

What the correlation score actually measures

The standard metric is importance, introduced by Liblit et al. in Cooperative Bug Isolation. Importance is the product of two numbers: increase and support.

Increase is the difference between the crash rate when a predicate is true and when it is false. If p != NULL is true in 99% of crashing runs and 98% of non-crashing runs, the increase is 0.01. That predicate is useless even if it fires on every crash.

Support is the fraction of all runs where the predicate is true. It keeps rare but perfect predictors from dominating the ranking. A predicate that only fires once but that run crashes gets high increase and near-zero support.

importance(pred) = (P(crash | pred=True) - P(crash | pred=False)) * P(pred=True)

This filters noise well. It does not localize bugs. A predicate with high importance might be the bug, the safety check that catches it, or a common operation on every path to the crash.

Why guilty-looking predicates are often innocent

Consider an off-by-one error at line 42 where a loop bound uses <= instead of <. The crash happens twenty lines later. The loop condition fires on every iteration. A bounds check at line 45 fires on every iteration. The null check at line 10 fires once at startup. All of them have high support and all appear in crashing runs.

The problem is temporal and causal distance. A predicate that executes moments before the crash is more likely to be related than one from startup. A predicate inside the same function is more likely to be related than one in a utility logger. Statistical debugging ignores this unless you add it back in.

How to filter by reachability and distance

The first refinement is control-flow reachability. A predicate that is always true in crashing runs but also always true in non-crashing runs that reach the same code is not suspicious. It is just a property of that path.

Compute a conditional probability. Instead of asking “how often does this predicate crash?”, ask “how often does it crash given that the program reached this point in the control flow?” If the crash rate does not change when you condition on reaching the function, the predicate is not adding information.

The second refinement is spatial distance. After ranking by importance, re-rank by distance to the crash site. This is a heuristic. Bugs can propagate far. But most memory corruption and null dereference bugs live within a few lines of the predicate that first diverges from correct behavior.

Here is a lightweight implementation that computes importance and filters by distance:

from dataclasses import dataclass
from typing import List, Set

@dataclass(frozen=True)
class Predicate:
    pid: str
    file: str
    line: int
    expr: str

@dataclass
class Run:
    crashed: bool
    crash_file: str = ""
    crash_line: int = 0
    predicates: Set[Predicate] = None


def importance(pred: Predicate, runs: List[Run]) -> float:
    total = len(runs)
    with_pred = [r for r in runs if pred in r.predicates]
    without_pred = [r for r in runs if pred not in r.predicates]

    if not with_pred or not without_pred:
        return 0.0

    crash_with = sum(1 for r in with_pred if r.crashed) / len(with_pred)
    crash_without = sum(1 for r in without_pred if r.crashed) / len(without_pred)
    support = len(with_pred) / total

    return (crash_with - crash_without) * support


def avg_distance(pred: Predicate, runs: List[Run]) -> float:
    crash_runs = [r for r in runs if r.crashed]
    if not crash_runs:
        return float('inf')
    dists = []
    for r in crash_runs:
        if pred.file != r.crash_file:
            return float('inf')
        dists.append(abs(pred.line - r.crash_line))
    return sum(dists) / len(dists)


def rank_predicates(runs: List[Run]) -> List[tuple]:
    all_preds = set()
    for r in runs:
        all_preds.update(r.predicates)

    scored = []
    for p in all_preds:
        imp = importance(p, runs)
        dist = avg_distance(p, runs)
        # Higher importance is better, lower distance is better.
        if dist == float('inf'):
            score = imp * 0.1
        else:
            score = imp / (1 + dist / 10)
        scored.append((score, imp, dist, p))

    scored.sort(key=lambda x: x[0], reverse=True)
    return scored

The scoring function is deliberately simple. In layered architectures, use a weaker distance penalty. In tight parsers, a strong penalty works better.

From predicate to exact line: triangulation

A predicate is still not a bug location. It is a Boolean expression like i <= buf->len. To get to a line number, look at the predicate in context.

The key question: what is the negation of this predicate, and would the negation prevent the crash? If the predicate is p == NULL and the crash is a null dereference, the negation would prevent it. That makes the predicate a direct cause. If the predicate is log_level > 2 and the crash is a buffer overflow, the negation changes nothing. The predicate is a bystander.

You can automate this partially. For each top-ranked predicate, force it false in a reproduction case. If the crash disappears, you have found the controlling condition. The bug is usually the assignment or comparison that made the predicate true in the first place.

The statistical ranking narrows the search from thousands of predicates to a handful. A targeted test or a short debugger session closes the loop.

The trade-off: coverage versus precision

The more predicates you instrument, the more statistical power you have, but the more false positives you generate. Instrumenting every memory access produces millions of predicates. Most will correlate weakly with the crash by random chance.

The fix is selective instrumentation. Start with null checks, bounds checks, error return values, and branch conditions in functions from the stack trace. These are most likely to separate crashing from non-crashing behavior.

You also need enough runs. The importance score is a sample statistic. With a hundred runs, noise dominates. With ten thousand, the signal sharpens. The rule of thumb from the CBI papers is at least a thousand runs per bug. Rare crashes need volume.

What this cannot catch

Statistical debugging finds bugs that manifest as observable predicate deviations. It will not find performance regressions, logic errors that stay within bounds, or race conditions that instrumentation perturbs.

It is also fundamentally post-hoc. The crashes have already happened. You are doing forensics on a dataset. The value is shrinking the search space from “the entire codebase” to “maybe fifty lines.”

A minimal end-to-end example

Here is how the pieces fit together with simulated data:

# Simulate runs for a bug at parser.c:42 (off-by-one loop bound)
runs = []

# 900 non-crashing runs
for _ in range(900):
    runs.append(Run(
        crashed=False,
        predicates={
            Predicate("p1", "parser.c", 10, "buf != NULL"),
            Predicate("p2", "parser.c", 42, "i <= buf->len"),  # the bug
            Predicate("p3", "parser.c", 45, "i < buf->len"),
        }
    ))

# 100 crashing runs: all hit the bug predicate
for _ in range(100):
    runs.append(Run(
        crashed=True,
        crash_file="parser.c",
        crash_line=62,
        predicates={
            Predicate("p1", "parser.c", 10, "buf != NULL"),
            Predicate("p2", "parser.c", 42, "i <= buf->len"),
            Predicate("p3", "parser.c", 45, "i < buf->len"),
            Predicate("p4", "main.c", 5, "argc > 1"),  # startup, irrelevant
        }
    ))

results = rank_predicates(runs)
for score, imp, dist, pred in results[:3]:
    print(f"{pred.file}:{pred.line}  {pred.expr:20s}  "
          f"score={score:.3f}  importance={imp:.3f}  avg_dist={dist:.1f}")

Running this gives p2 at parser.c:42 the highest score because it has both high importance and a short distance to the crash. p1 has similar importance but sits further away. p4 is penalized for being in a different file.

Start with the crash you are already investigating

You do not need a research-grade framework. Pick a crash that reproduces frequently. Add instrumentation to the five most interesting predicates in the call stack. Run your test suite or production traffic. Compute importance and distance. If one predicate separates crashing from non-crashing runs and sits close to the crash site, you have narrowed the search.

Statistical debugging is not a replacement for stack traces or debuggers. It is a replacement for reading every line of code between main and the segfault. The correlation gets you in the neighborhood. Reachability, distance, and a quick check of the negation get you to the door.