statistical debuggingは、根本原因ではなくソートされたpredicatesのリストを与える。すべての分岐とnull checkを計測し、10万回の実行を行い、アルゴリズムがスコアボードを渡す。parser.c:144のbuffer_idx > max_lenのimportanceは0.94だ。main.c:38のlog_file != NULLも同様だ。一方はバグであり、もう一方はプログラムがクラッシュするたびに真になるだけだ。

高い相関はpredicateとクラッシュが同時に発生することを意味する。predicateがクラッシュを引き起こしたことを意味するわけではない。すべてのクラッシュが同じクリーンアップパスを通る場合、そのパス上のすべてのpredicateは有罪に見える。犯人と傍観者を分ける方法が必要だ。

相関スコアが実際に測定するもの

標準的なメトリックはimportanceであり、LiblitらがCooperative Bug Isolationで導入したものだ。importanceは2つの数値、increaseとsupportの積である。

increaseはpredicateが真のときのクラッシュ率と偽のときのクラッシュ率の差だ。p != NULLがクラッシュした実行の99%で真であり、クラッシュしなかった実行の98%で真なら、increaseは0.01だ。そのpredicateはすべてのクラッシュで発火しても役に立たない。

supportはpredicateが真であるすべての実行の割合だ。稀だが完璧な予測子がランキングを支配するのを防ぐ。1回だけ発火してその実行がクラッシュするpredicateは、高いincreaseとほぼゼロのsupportを得る。

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

これはノイズをうまくフィルタリングする。バグを局在化はしない。高いimportanceを持つpredicateは、バグかもしれないし、それを捉える安全チェックかもしれないし、クラッシュへのすべてのパスでの共通操作かもしれない。

有罪に見えるpredicatesがしばしば無罪である理由

行42でループの境界が<の代わりに<=を使っているオフバイワンエラーを考えてみよう。クラッシュは20行後に発生する。ループ条件はすべての反復で発火する。行45の境界チェックはすべての反復で発火する。行10のnull checkは起動時に1回発火する。すべてが高いsupportを持ち、すべてがクラッシュした実行に現れる。

問題は時間的および因果的な距離だ。クラッシュの直前に実行されるpredicateは、起動時のものより関連している可能性が高い。同じ関数内のpredicateは、ユーティリティロガー内のものより関連している可能性が高い。statistical debuggingは、これを追加し直さない限りこれを無視する。

到達可能性と距離でフィルタリングする方法

最初の洗練は制御フローの到達可能性だ。クラッシュした実行で常に真であり、同じコードに到達したクラッシュしなかった実行でも常に真であるpredicateは怪しくない。それはそのパスの特性に過ぎない。

条件付き確率を計算する。「このpredicateはどれくらいの頻度でクラッシュするか？」と問うのではなく、「プログラムが制御フローのこの地点に到達した場合、どれくらいの頻度でクラッシュするか？」と問う。関数に到達したことでクラッシュ率が変化しないなら、そのpredicateは情報を追加していない。

2番目の洗練は空間的距離だ。importanceでランク付けした後、クラッシュサイトへの距離で再ランク付けする。これは発見的手法だ。バグは遠くまで伝播することがある。しかし、ほとんどのメモリ破損とnull dereferenceバグは、正しい動作から最初に逸脱した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

スコアリング関数は意図的に単純だ。レイヤードアーキテクチャでは、より弱い距離ペナルティを使う。タイトなパーサーでは、強いペナルティがより効果的だ。

predicateから正確な行へ：トライアングレーション

predicateはまだバグの場所ではない。i <= buf->lenのようなBoolean expressionだ。行番号を得るには、文脈の中でpredicateを見る。

重要な質問：このpredicateの否定は何か、そしてその否定がクラッシュを防ぐか？predicateがp == NULLでクラッシュがnull dereferenceなら、否定はそれを防ぐだろう。これにより、そのpredicateは直接の原因となる。predicateがlog_level > 2でクラッシュがbuffer overflowなら、否定は何も変えない。そのpredicateは傍観者だ。

これを部分的に自動化できる。各トップランクのpredicateについて、再現ケースでそれを偽に強制する。クラッシュが消えれば、制御条件を見つけたことになる。バグは通常、最初にpredicateを真にした代入または比較である。

統計的なランキングは、検索範囲を数千のpredicateから少数に絞り込む。ターゲットを絞ったテストまたは短いデバッガセッションでループを閉じる。

トレードオフ：カバレッジ対精度

計測するpredicateが多ければ多いほど、統計的な力は強まるが、偽陽性も増える。すべてのメモリアクセスを計測すると、数百万のpredicateが生成される。ほとんどは偶然によってクラッシュと弱く相関するだろう。

解決策は選択的計測だ。stack traceの関数内のnull checks、bounds checks、エラー戻り値、分岐条件から始める。これらがクラッシュする動作とクラッシュしない動作を分離する可能性が最も高い。

十分な実行回数も必要だ。importance scoreはサンプル統計量だ。100回の実行ではノイズが支配する。1万回なら信号が鮮明になる。CBI論文からの経験則は、バグあたり少なくとも1000回の実行だ。稀なクラッシュにはボリュームが必要だ。

これが捉えられないもの

statistical debuggingは、観測可能なpredicateの逸脱として現れるバグを見つける。パフォーマンス回帰、境界内に留まる論理エラー、計測が攪乱する競合状態は見つけられない。

これは本質的に事後的でもある。クラッシュはすでに発生している。データセットに対してフォレンジックを行っているのだ。価値は、検索空間を「codebase全体」から「おそらく50行」に縮小することにある。

最小限のエンドツーエンド例

シミュレートされたデータで各部分がどう組み合わさるかを以下に示す。

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

これを実行すると、parser.c:42のp2が最高スコアを得る。なぜなら、高いimportanceとクラッシュへの短い距離の両方を持つからだ。p1は同様のimportanceを持つが、より遠くにある。p4は異なるファイルにあるためペナルティを受ける。

すでに調査しているクラッシュから始めよう

研究グレードのフレームワークは不要だ。頻繁に再現するクラッシュを選ぶ。コールスタック内で最も興味深い5つのpredicateに計測を追加する。テストスイートまたは本番トラフィックを実行する。importanceと距離を計算する。1つのpredicateがクラッシュする実行とクラッシュしない実行を分離し、クラッシュサイトに近ければ、検索を絞り込んだことになる。

statistical debuggingはstack tracesやデバッガの代替ではない。mainとsegfaultの間のすべてのコード行を読むことの代替だ。相関はあなたを近隣に導く。到達可能性、距離、否定の迅速なチェックがあなたをドアまで導く。