Statistical debugging даёт вам отсортированный список predicates, а не root cause. Вы инструментируете каждую ветку и null check, запускаете сто тысяч выполнений, и алгоритм выдаёт вам табло score. У buffer_idx > max_len в parser.c:144 importance 0,94. И у log_file != NULL в main.c:38 тоже. Один из них — баг. Другой просто случайно истинен всякий раз, когда программа падает.

Высокая корреляция означает, что predicate и краш совпадают. Это не означает, что predicate вызвал краш. Если каждый краш проходит через один и тот же путь cleanup, каждый predicate на этом пути будет выглядеть виноватым. Вам нужен способ отделить преступника от свидетелей.

Что на самом деле измеряет корреляционный score

Стандартная метрика — importance, введённая Либлитом и др. в Cooperative Bug Isolation. Importance — это произведение двух чисел: increase и support.

Increase — это разница между rate краша, когда predicate истинен, и когда он ложен. Если p != NULL истинен в 99% падающих прогонов и в 98% непадающих, increase равен 0,01. Этот predicate бесполезен, даже если он срабатывает на каждом краше.

Support — это доля всех прогонов, в которых predicate истинен. Он не даёт редким, но идеальным предикторам доминировать в ранжировании. Predicate, который срабатывает только один раз, но в этом прогоне происходит краш, получает высокий increase и near-zero support.

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

Это хорошо фильтрует шум. Оно не локализует баги. Predicate с высоким importance может быть багом, защитной проверкой, которая его ловит, или обычной операцией на каждом пути к крашу.

Почему predicates, выглядящие виноватыми, часто невиновны

Возьмём ошибку off-by-one в строке 42, где граница цикла использует <= вместо <. Краш происходит на двадцать строк позже. Условие цикла срабатывает на каждой итерации. Проверка границ в строке 45 срабатывает на каждой итерации. Null check в строке 10 срабатывает один раз при старте. У всех них высокий support, и все появляются в падающих прогонах.

Проблема во временном и причинном расстоянии. Predicate, который выполняется за мгновения до краша, с большей вероятностью связан, чем тот, что со старта. Predicate внутри той же функции с большей вероятностью связан, чем тот, что в utility-логгере. Statistical debugging игнорирует это, если вы не добавите это обратно.

Как фильтровать по reachability и distance

Первое уточнение — control-flow reachability. Predicate, который всегда истинен в падающих прогонах, но также всегда истинен в непадающих прогонах, достигающих того же кода, не подозрителен. Это просто свойство этого пути.

Вычислите условную вероятность. Вместо вопроса «как часто этот predicate крашит?» спросите «как часто он крашит, учитывая, что программа достигла этой точки в control flow?» Если rate краша не меняется, когда вы условились на достижении функции, predicate не добавляет информации.

Второе уточнение — пространственное расстояние. После ранжирования по importance переранжируйте по расстоянию до места краша. Это эвристика. Баги могут распространяться далеко. Но большинство багов повреждения памяти и разыменования null живут в пределах нескольких строк от predicate, который первым отклоняется от корректного поведения.

Вот лёгкая реализация, которая вычисляет importance и фильтрует по расстоянию:

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

Функция scoring намеренно простая. В многоуровневых архитектурах используйте более слабый штраф за расстояние. В плотных парсерах сильный штраф работает лучше.

От predicate к точной строке: триангуляция

Predicate всё ещё не место бага. Это булево выражение вроде i <= buf->len. Чтобы дойти до номера строки, смотрите на predicate в контексте.

Ключевой вопрос: какова негация этого predicate, и предотвратила бы негация краш? Если predicate — p == NULL, а краш — разыменование null, негация предотвратила бы его. Это делает predicate прямой причиной. Если predicate — log_level > 2, а краш — переполнение буфера, негация ничего не меняет. Predicate — свидетель.

Вы можете частично автоматизировать это. Для каждого top-ranked predicate форсируйте его в false в reproduction case. Если краш исчезает, вы нашли контролирующее условие. Багом обычно является присваивание или сравнение, которое изначально сделало predicate истинным.

Статистическое ранжирование сужает поиск от тысяч predicates до горстки. Целенаправленный тест или короткая сессия с дебаггером замыкают цикл.

Компромисс: покрытие против точности

Чем больше predicates вы инструментируете, тем больше статистическая мощь, но тем больше ложных срабатываний вы генерируете. Инструментирование каждого обращения к памяти производит миллионы predicates. Большинство будет слабо коррелировать с крашем случайно.

Решение — селективное инструментирование. Начинайте с null checks, bounds checks, error return values и условий ветвления в функциях из stack trace. Они с наибольшей вероятностью разделяют падающее и непадающее поведение.

Вам также нужно достаточно прогонов. Score importance — это выборочная статистика. Со ста прогонами доминирует шум. С десятью тысячами сигнал чётче. Правило большого пальца из статей CBI — как минимум тысяча прогонов на баг. Редкие краши требуют объёма.

Что это не ловит

Statistical debugging находит баги, проявляющиеся как наблюдаемые отклонения predicates. Он не найдёт регрессии производительности, логические ошибки, которые остаются в границах, или race conditions, которые инструментирование возмущает.

Он также фундаментально постфактум. Краши уже произошли. Вы делаете криминалистику на датасете. Ценность в сужении пространства поиска от «весь codebase» до «может быть, пятьдесят строк».

Минимальный сквозной пример

Вот как куски складываются вместе с симулированными данными:

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

Запуск этого даёт p2 в parser.c:42 наивысший score, потому что у него и высокий importance, и малое расстояние до краша. У p1 похожий importance, но он дальше. p4 штрафуется за то, что находится в другом файле.

Начните с краша, который вы уже расследуете

Вам не нужен исследовательский фреймворк. Выберите краш, который часто воспроизводится. Добавьте инструментирование к пяти наиболее интересным predicates в call stack. Запустите ваш набор тестов или продакшен-трафик. Вычислите importance и расстояние. Если один predicate разделяет падающие и непадающие прогоны и находится близко к месту краша, вы сузили поиск.

Statistical debugging — не замена stack traces или дебаггерам. Это замена чтению каждой строки кода между main и segfault. Корреляция загоняет вас в район. Reachability, distance и быстрая проверка негации подводят к двери.