Statistical Debugging gibt Ihnen eine sortierte Liste von Prädikaten, keine Root Cause. Sie instrumentieren jeden Branch und jeden Null-Check, führen hunderttausend Ausführungen durch, und der Algorithmus übergibt Ihnen eine Anzeigetafel. buffer_idx > max_len in parser.c:144 hat eine Importance von 0,94. Ebenso log_file != NULL in main.c:38. Eines davon ist der Bug. Das andere ist nur zufällig immer wahr, wenn das Programm abstürzt.

Eine hohe Korrelation bedeutet, dass ein Prädikat und ein Absturz gemeinsam auftreten. Es bedeutet nicht, dass das Prädikat den Absturz verursacht hat. Wenn jeder Absturz denselben Cleanup-Pfad durchläuft, wird jedes Prädikat auf diesem Pfad schuldig aussehen. Sie benötigen einen Weg, den Täter von den Zuschauern zu trennen.

Was der Korrelationsscore tatsächlich misst

Die Standardmetrik ist Importance, eingeführt von Liblit et al. in Cooperative Bug Isolation. Importance ist das Produkt aus zwei Zahlen: Increase und Support.

Increase ist die Differenz zwischen der Absturzrate, wenn ein Prädikat wahr ist, und wenn es falsch ist. Wenn p != NULL in 99 % der abstürzenden Durchläufe und in 98 % der nicht abstürzenden Durchläufe wahr ist, ist das Increase 0,01. Dieses Prädikat ist nutzlos, selbst wenn es bei jedem Absturz auslöst.

Support ist der Anteil aller Durchläufe, in denen das Prädikat wahr ist. Es verhindert, dass seltene, aber perfekte Prädiktoren das Ranking dominieren. Ein Prädikat, das nur einmal auslöst, aber dieser Durchlauf abstürzt, erhält ein hohes Increase und nahezu null Support.

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

Das filtert Rauschen gut. Es lokalisiert aber keine Bugs. Ein Prädikat mit hoher Importance könnte der Bug sein, der Safety-Check, der ihn fängt, oder eine gemeinsame Operation auf jedem Pfad zum Absturz.

Warum schuldig aussehende Prädikate oft unschuldig sind

Betrachten Sie einen Off-by-One-Fehler in Zeile 42, wo eine Schleifengrenze <= statt < verwendet. Der Absturz passiert zwanzig Zeilen später. Die Schleifenbedingung löst bei jeder Iteration aus. Ein Bounds-Check in Zeile 45 löst bei jeder Iteration aus. Der Null-Check in Zeile 10 löst einmal beim Start aus. Alle haben hohen Support und erscheinen in abstürzenden Durchläufen.

Das Problem ist die zeitliche und kausale Distanz. Ein Prädikat, das Momente vor dem Absturz ausgeführt wird, ist wahrscheinlicher verwandt als eines vom Start. Ein Prädikat innerhalb derselben Funktion ist wahrscheinlicher verwandt als eines in einem Utility-Logger. Statistical Debugging ignoriert dies, es sei denn, Sie fügen es wieder hinzu.

Wie man nach Erreichbarkeit und Distanz filtert

Die erste Verfeinerung ist die Control-Flow-Erreichbarkeit. Ein Prädikat, das in abstürzenden Durchläufen immer wahr ist, aber auch in nicht abstürzenden Durchläufen, die denselben Code erreichen, immer wahr ist, ist nicht verdächtig. Es ist nur eine Eigenschaft dieses Pfads.

Berechnen Sie eine bedingte Wahrscheinlichkeit. Statt zu fragen “Wie oft lässt dieses Prädikat abstürzen?”, fragen Sie “Wie oft lässt es abstürzen, gegeben dass das Programm diesen Punkt im Control Flow erreicht hat?” Wenn sich die Absturzrate nicht ändert, wenn Sie auf das Erreichen der Funktion konditionieren, fügt das Prädikat keine Information hinzu.

Die zweite Verfeinerung ist die räumliche Distanz. Nach dem Ranking nach Importance ranken Sie neu nach Distanz zur Absturzstelle. Das ist eine Heuristik. Bugs können sich weit ausbreiten. Aber die meisten Memory-Corruption- und Null-Dereference-Bugs liegen innerhalb weniger Zeilen des Prädikats, das sich als Erstes vom korrekten Verhalten unterscheidet.

Hier ist eine leichtgewichtige Implementierung, die Importance berechnet und nach Distanz filtert:

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

Die Scoring-Funktion ist bewusst einfach. In Layered Architectures verwenden Sie eine schwächere Distanzstrafe. In engen Parsern funktioniert eine starke Strafe besser.

Vom Prädikat zur exakten Zeile: Triangulation

Ein Prädikat ist immer noch keine Bug-Location. Es ist ein boolescher Ausdruck wie i <= buf->len. Um zu einer Zeilennummer zu gelangen, betrachten Sie das Prädikat im Kontext.

Die Schlüsselfrage: Was ist die Negation dieses Prädikats, und würde die Negation den Absturz verhindern? Wenn das Prädikat p == NULL ist und der Absturz eine Null-Dereference ist, würde die Negation ihn verhindern. Das macht das Prädikat zu einer direkten Ursache. Wenn das Prädikat log_level > 2 ist und der Absturz ein Buffer Overflow ist, ändert die Negation nichts. Das Prädikat ist ein Zuschauer.

Sie können dies teilweise automatisieren. Für jedes Top-Ranked-Prädikat zwingen Sie es in einem Reproduktionsfall zu falsch. Wenn der Absturz verschwindet, haben Sie die kontrollierende Bedingung gefunden. Der Bug ist normalerweise die Zuweisung oder der Vergleich, der das Prädikat überhaupt erst wahr gemacht hat.

Das statistische Ranking verengt die Suche von Tausenden von Prädikaten auf eine Handvoll. Ein gezielter Test oder eine kurze Debugger-Session schließt den Kreis.

Der Trade-off: Coverage versus Präzision

Je mehr Prädikate Sie instrumentieren, desto mehr statistische Power haben Sie, aber desto mehr Falschpositive erzeugen Sie. Die Instrumentierung jedes Memory Access produziert Millionen von Prädikaten. Die meisten werden schwach zufällig mit dem Absturz korrelieren.

Die Lösung ist selektive Instrumentierung. Beginnen Sie mit Null-Checks, Bounds-Checks, Error-Return-Values und Branch-Conditions in Funktionen aus dem Stack Trace. Diese sind am wahrscheinlichsten dazu geeignet, abstürzendes von nicht abstürzendem Verhalten zu trennen.

Sie benötigen auch genug Durchläufe. Der Importance-Score ist eine Stichprobenstatistik. Bei hundert Durchläufen dominiert Rauschen. Bei zehntausend schärft sich das Signal. Die Daumenregel aus den CBI-Papieren ist mindestens tausend Durchläufe pro Bug. Seltene Abstürze brauchen Volumen.

Was das nicht finden kann

Statistical Debugging findet Bugs, die sich als beobachtbare Prädikat-Abweichungen manifestieren. Es wird keine Performance-Regressionen finden, Logikfehler, die innerhalb der Grenzen bleiben, oder Race Conditions, die die Instrumentierung stören.

Es ist auch im Grunde post-hoc. Die Abstürze sind bereits passiert. Sie führen Forensik an einem Datensatz durch. Der Wert liegt darin, den Suchraum von “der gesamte Codebase” auf “vielleicht fünfzig Zeilen” zu verkleinern.

Ein minimales End-to-End-Beispiel

Hier ist, wie die Teile mit simulierten Daten zusammenpassen:

# 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}")

Die Ausführung gibt p2 in parser.c:42 den höchsten Score, weil es sowohl hohe Importance als auch eine kurze Distanz zum Absturz hat. p1 hat eine ähnliche Importance, sitzt aber weiter weg. p4 wird dafür bestraft, in einer anderen Datei zu sein.

Beginnen Sie mit dem Absturz, den Sie bereits untersuchen

Sie benötigen kein Framework auf Forschungsniveau. Wählen Sie einen Absturz, der häufig reproduziert wird. Fügen Sie Instrumentierung zu den fünf interessantesten Prädikaten im Call Stack hinzu. Führen Sie Ihre Test-Suite oder Produktionstraffic aus. Berechnen Sie Importance und Distanz. Wenn ein Prädikat abstürzende von nicht abstürzenden Durchläufen trennt und nah an der Absturzstelle sitzt, haben Sie die Suche eingegrenzt.

Statistical Debugging ist kein Ersatz für Stack Traces oder Debugger. Es ist ein Ersatz dafür, jede Zeile Code zwischen main und dem Segfault zu lesen. Die Korrelation bringt Sie in die Nachbarschaft. Erreichbarkeit, Distanz und ein schneller Check der Negation bringen Sie zur Tür.