ファジングの原理（カバレッジ誘導とサニタイザ）

ファジングが「探す」とはどういうことか

ファジング（fuzzing）の基本動作は単純です。プログラムに大量の自動生成入力を与え、クラッシュ・ハング・サニタイザ検出といった「異常」を起こす入力を探します。狙うのは、開発者が想定しなかった経路――不正なバイト列、極端な長さ、境界値の組み合わせ――が引き起こすメモリ破壊や未定義動作です。

しかし純粋なランダム生成（ブラックボックスファジング）は、現実のプログラムでは早々に行き詰まります。たとえば入力先頭 4 バイトが "FUZZ" のときだけ深い処理に進むパーサがあれば、ランダムにその 4 バイトを当てる確率は約 1/2^32 で、事実上到達できません。バグは深い経路に潜むのに、ランダム探索は浅瀬を撹拌し続けるだけになる――これが素朴なファジングの限界です。

カバレッジ誘導：実行の足跡を報酬にする

ブレークスルーは「入力がどれだけ深いコードに到達したかを測り、新しい経路を開いた入力を残して育てる」という発想です。これが**カバレッジ誘導（coverage-guided）**で、AFL と libFuzzer が体現しました。

仕組みの中心は**コンパイル時の計装（instrumentation）**です。コンパイラがプログラム中のすべての分岐（basic block の境界）に小さなコードを挿入し、実行のたびに「どの分岐エッジを通ったか」を共有メモリ上のカウンタ配列に記録します。AFL はこのエッジを 64KB のビットマップへハッシュで畳み込み、libFuzzer は LLVM の SanitizerCoverage（-fsanitize-coverage=...）で得たエッジ情報を使います。

入力 → 計装済みプログラムを実行 → エッジ到達ビットマップを取得
        ↓
  新しいエッジ（未踏の分岐）を踏んだか？
        ↓ Yes                        ↓ No
  入力をコーパスに保存し              破棄
  突然変異の種として再投入

ここがアルゴリズムの肝です。ファジャは「新しいエッジを 1 つでも開いた入力」だけをコーパス（種入力の集合）に加えます。先ほどの "FUZZ" の例なら、偶然 "FUZ?" のように一部が一致してマジック比較の手前まで進む入力が出れば、それは新しいエッジを踏むため保存されます。次の世代はその入力を突然変異させて生成するので、残り 1 バイトを当てるだけの局所探索に問題が縮みます。32 ビットを一発で当てる問題が、1 バイトずつ前進する勾配のある問題に変わる――これがカバレッジ誘導が深部へ届く理由です。

進化的探索のループと突然変異

カバレッジ誘導ファジングは、遺伝的アルゴリズムに近い進化的探索として動きます。コーパスを母集団とみなし、有望な個体（新カバレッジを生んだ入力）を選んで変異させ、適応度（新エッジ）が上がった子を母集団へ戻す、という反復です。

loop:
  seed   = コーパスから 1 つ選ぶ（新カバレッジ寄与の大きいものを優先）
  child  = mutate(seed)            # ビット反転・バイト挿入/削除・既知定数の代入・複数入力の splice 等
  cov    = run(child)              # 計装済み実行でエッジ集合を取得
  if cov に未踏エッジが含まれる:
      コーパスへ child を追加        # この入力が新しい探索の起点になる
  if child がクラッシュ/サニタイザ検出:
      クラッシュ入力として保存（再現用）

突然変異の演算子は多彩です。ビット/バイトの反転、算術加減、0・-1・INT_MAX のような境界定数の代入、辞書（dictionary）に登録したトークンの挿入、そして 2 つのコーパス入力を継ぎ合わせる splice などを組み合わせます。さらに AFL++ や libFuzzer は、if (x == 0xDEADBEEF) のようなマジック値比較を計装で観測し（CmpLog / value-profile）、比較対象の定数を変異候補へ直接フィードバックします。これにより、本来は確率的に当てるしかない多バイトの一致を、ほぼ決定的に突破できます。

サニタイザ：サイレントな不正を例外へ変える

カバレッジ誘導で深部へ到達できても、バグが「クラッシュ」として観測できなければ見逃します。C/C++ の領域外読み取りや解放後アクセスは、運が良ければ（悪ければ）何事もなく続行してしまう――この沈黙こそ最大の障害です。ここで**サニタイザ（sanitizer）**が、検出を担います。

ASan（AddressSanitizer）は、確保したメモリの前後にレッドゾーン（redzone）という毒入り領域を挟み、別途シャドウメモリ（実メモリ 8 バイトを 1 バイトで表す写像）で各アドレスのアクセス可否を記録します。コンパイラが全メモリアクセスの直前にシャドウ照合を計装し、レッドゾーンや解放済み領域に触れた瞬間に検出してアボートします。解放後アクセス（use-after-free）は、解放したチャンクをすぐ再利用せず**隔離（quarantine）**して毒入りのまま保持することで捕まえます。

**UBSan（UndefinedBehaviorSanitizer）は、符号付き整数オーバーフロー、ヌルポインタ参照、未整列アクセス、シフト量過大、列挙範囲外といった未定義動作（UB）**を実行時に検出します。UB は最適化と結びついて任意の挙動を許してしまうため、機能的には正しく見えるコードに潜む地雷を顕在化させます。

重要なのは、ファジング（探索）とサニタイザ（検出）は役割が直交することです。カバレッジ誘導が「バグのある経路へ到達する」力なら、サニタイザは「到達したバグを取りこぼさず例外化する」力です。どちらが欠けても、深いバグは静かに見過ごされます。この検出可能性の壁は、メモリ破壊攻撃の原理で触れた、攻撃者が突く「実装で本当に溢れているか」という問いと表裏一体です。

コーパス最小化：少ない入力で同じ探索を保つ

長く回したファジングは、数十万件の種入力を抱えがちです。多くは同じカバレッジを重複して持つ冗長な入力で、母集団が膨れると 1 周あたりの実行効率が落ちます。そこで**コーパス最小化（corpus minimization）**を行います。

最小化には 2 つの軸があります。第 1 は集合の最小化で、AFL の afl-cmin や libFuzzer の -merge=1 が担います。これは集合カバー問題に近く、「全体と同じエッジ集合を覆う、できるだけ少ない入力部分集合」を貪欲に選びます。第 2 は個々の入力の縮小で、afl-tmin が担い、各入力からカバレッジを変えずに削れるバイトを削る――同じエッジ集合を保ったまま入力長を縮め、再現とデバッグを容易にします。

afl-cmin: 大量コーパス → 同一エッジ集合を覆う最小の入力部分集合（集合の刈り込み）
afl-tmin: 1つの入力   → 同一カバレッジを保つ最短形へ縮小（バイト単位の刈り込み）

最小化は単なる節約ではありません。コーパスは継続的ファジングで次回以降の探索の起点として再投入される資産であり、これを引き締めることが長期的なバグ発見速度を支えます。

クラッシュトリアージ：大量の発見を実用情報に変える

ファジングは同じ根本原因のクラッシュを何千通りもの異なる入力で再発見します。生のクラッシュ群をそのまま人手で見るのは非現実的なので、**トリアージ（triage）**で整理します。

第 1 段階は重複排除（deduplication）です。各クラッシュのスタックトレースやクラッシュ箇所のハッシュで束ね、同一原因を 1 件にまとめます。AFL は実行パスのハッシュで一意なクラッシュを区別し、libFuzzer は ASan の出力を手掛かりにします。これで「数千クラッシュ」が「十数件の固有バグ」に圧縮されます。

第 2 段階は最小化と再現性確認です。afl-tmin 等で各クラッシュ入力を最短化し、サニタイザ有効ビルドで確実に再現するかを確かめます。間欠的にしか再現しないものは、データ競合（→ TSan）や未初期化値（→ MSan）など別種の問題を示唆します。

第 3 段階は深刻度の評価です。同じ「クラッシュ」でも、読み取りの領域外と書き込みの領域外では悪用可能性が大きく異なります。書き込みプリミティブや制御フローの奪取につながるものを優先する判断は、ペネトレーションテストでの実証評価や、OWASP Top 10が示すリスクの文脈と接続して行います。

実務での位置づけ：継続的に回し続ける

ファジングは「一度回して終わり」ではなく、コードが変わるたびに回し続けることで真価を発揮します。Google の OSS-Fuzz は主要 OSS を継続的にファジングし、回帰の早期検出と修正検証を自動化しています。CI へ組み込めば、新しいコミットが導入したメモリバグを統合前に捕まえられます。

• ハーネスを増やす：API ごとに薄いハーネスを用意し、攻撃面（パーサ、デコーダ、シリアライザ）を網羅的に叩く。シードコーパスに実データの正常入力を与えると、深部への到達が一気に速くなる。
• サニタイザを使い分ける：通常は ASan＋UBSan、未初期化値が疑わしければ MSan、並行コードには TSan を別ビルドで。検出器を変えると見える不具合が変わる。
• 発見を資産化する：固有バグごとに最小化した再現入力を回帰テストへ取り込み、コーパスは最小化して次回探索の起点として育てる。OSS 依存を多用する系では、上流の脆弱性がサプライチェーン攻撃の起点になり得るため、依存ライブラリのファジング成果も注視する。

ファジングが教えるのは、「レビューで正しく見えること」と「あらゆる入力で本当に壊れないこと」は別物だ、という一点です。探索（カバレッジ誘導）と検出（サニタイザ）を噛み合わせ、発見を最小化・トリアージして回し続ける――この循環こそが、人手のテストでは届かない深部のバグを継続的に潰す現実的な道筋です。