ファジングとカバレッジ誘導テスト

ファジングとは何を狙う手法か

**ファジング（fuzzing）**は、半ばランダムに作った入力をプログラムへ大量に流し込み、クラッシュ・ハング・サニタイザ検出といった異常を観測する自動テスト手法です。テストの基礎で扱う単体テストが「想定した入力に正しい出力が返るか」を確かめるのに対し、ファジングは「想定外の入力で壊れないか」を確かめます。期待出力（オラクル）を人が用意できなくても、「異常終了しないこと」自体を弱いオラクルとして使えるのが強みです。

狙うのは主に堅牢性とメモリ安全性です。C/C++ ならバッファオーバーフロー、use-after-free、整数オーバーフロー由来の破壊。管理言語でも未処理例外、無限ループ、過大なメモリ確保（資源枯渇）が標的になります。パーサ・デコーダ・プロトコル実装・正規表現エンジンなど、外部からの非信頼入力を直接受ける境界が最も費用対効果が高い適用先です。

ブラックボックス・ファジングの限界

最も素朴なブラックボックス・ファジングは、対象を中身の見えない箱として扱い、ランダムなバイト列や既知入力の乱変異を投げ続けます。実装は簡単ですが、深いコードパスに到達できないという根本問題があります。

たとえば先頭4バイトが特定のマジックナンバー（50 4B 03 04 など）でなければ即座にエラー返却するパーサを考えます。ランダムな4バイトがその値に一致する確率はおよそ 1 / 2^32 で、その先のロジックには事実上到達できません。深くネストした分岐や、特定の長さ・チェックサムを要求する経路は、確率的にますます遠ざかります。入力空間が広大なのに、関心のある領域は薄く偏在している。当てずっぽうでは探索が表層で頭打ちになるわけです。

カバレッジ誘導という発想

この壁を破ったのが**カバレッジ誘導ファジング（coverage-guided fuzzing）です。鍵は、実行中にどのコードを通ったかを観測し、それを探索の報酬信号（フィードバック）**として使うことにあります。

ブラックボックス: 入力 → 実行 → クラッシュ?（通った経路は見ない）
カバレッジ誘導:   入力 → 実行 → どのエッジを通ったか観測
                  → 新しいエッジを開いた入力だけ「価値あり」と判定し保存

ここでの被覆単位は行ではなく**エッジ（基本ブロック間の遷移）**です。A→B と A→C を別個に数えることで、分岐の真偽どちらに進んだかを区別できます。実装はコンパイル時の計装（instrumentation）で行います。AFL なら afl-cc、libFuzzer なら Clang の -fsanitize-coverage=trace-pc-guard（SanitizerCoverage）が、各エッジに「ここを通った」と記録する小コードを挿入します。AFL は古典的に 64KiB の共有メモリをビットマップとして使い、エッジIDをハッシュした位置のカウンタを更新します。

遺伝的アルゴリズムとしての探索ループ

カバレッジ誘導ファザーの中核は、遺伝的アルゴリズム（GA）に酷似した進化ループです。GA の用語に対応づけると構造がはっきりします。

ループはこう回ります。コーパスから入力を1つ選び、変異を加えて実行し、それまで未踏のエッジを1つでも開けばその変異後入力をコーパスへ追加する。開かなければ捨てる。これを延々と繰り返します。

seed をコーパスへ投入
loop:
    input  = コーパスから選択（新規発見が多い入力を優先しがち）
    mutant = mutate(input)            # ビット反転・splice 等
    cov    = run_and_observe(mutant)  # 通ったエッジ集合を計装で取得
    if cov に新規エッジがある:
        コーパスへ mutant を追加      # = 適応度が高い個体を残す
    if クラッシュ または サニタイザ検出:
        crash として保存（シード付き）

この「新規エッジを開いた入力だけ生き残る」選択圧が決定的です。マジックナンバーの例なら、変異の過程で4バイトのうち一部が偶然一致してわずかに先へ進んだ入力がコーパスに残り、それを足場にさらに変異が進む。部分的な進捗が保存・蓄積されるため、ブラックボックスでは天文学的だった深部到達が、エッジを階段状に登る現実的な確率に変わります。これは乱択アルゴリズムが乱数を使いつつ構造的なフィードバックで収束を早めるのと同じ発想です。

観測可能性とサニタイザ

ファジングの効果は「潜在的な誤りをどれだけ目に見えるクラッシュへ変換できるか」に強く依存します。配列の境界をわずかに越えるだけのバグは、たまたま隣接メモリを踏むだけで素のままでは何も起きず、ファザーは異常を検知できません。

そこで AddressSanitizer（ASan） などのサニタイザを併用します。ASan は確保領域の周囲にレッドゾーンを置き、解放済み領域を隔離して、不正アクセスの瞬間に確定的にプロセスを停止させます。仮想メモリ上のシャドウメモリで各バイトのアクセス可否を追跡する仕組みです。同様に UBSan（未定義動作）、MSan（未初期化読み出し）、TSan（データ競合）が、それぞれ無症状のバグを観測可能な失敗に変えます。サニタイザなしのファジングは、地雷の上を歩いても爆発しない状態に近いと考えてよいでしょう。

再現性・最小化・運用

クラッシュを見つけたら終わりではなく、再現と原因特定が要ります。ファザーはクラッシュを誘発した入力をファイルとして保存するので、それを単体で再投入すれば再現できます。乱数を使う以上シード管理が重要で、同じシードからは同じ変異列が再生されます。

巨大で雑然としたクラッシュ入力は、そのままではデバッグしづらい。そこで**最小化（minimization）**を行います。afl-tmin や libFuzzer の -minimize_crash は、クラッシュを保ったまま入力からバイトを削り、より小さく単純な再現入力へ縮約します。これはデバッグで触れる delta-debugging と同じ差分最小化の発想です。コーパス側も afl-cmin や -merge で、被覆を落とさず冗長な入力を間引いて軽くします。

まとめ

ファジングは、変異させた入力を大量に投げてクラッシュやサニタイザ検出を探す確率的テストです。素朴なブラックボックスは入力空間の広さに阻まれ表層で頭打ちになりますが、カバレッジ誘導がこれを覆します。コンパイル時の計装でエッジ被覆を観測し、新しいエッジを開いた入力だけをコーパスに残す——個体・適応度・突然変異・交叉という遺伝的アルゴリズムの枠組みそのもので、部分的な進捗を足場に深部へ階段状に到達します。AddressSanitizer などが無症状のバグを確定的クラッシュへ変換し、最小化とシードが再現性を支えます。AFL／AFL++ と libFuzzer はこの原理の代表実装であり、OSS-Fuzz のように継続的に回し続けることで、人手のテストでは届かない経路のバグを地道に掘り当て続けます。