バックグラウンド#
Fuzzing の手法は、大量の入力を生成してテスト対象のプログラムのエラーを見つける方法です。
Fuzzing の重要なポイントの一つは、入力の生成方法であり、もう一つは入力のソート方法、そしてソフトウェア内部の情報の取得と適用です。
もし入力が完全に自己構築されたものであれば、この方法は generational fuzzing と呼ばれます。
もし入力が元のシードを微妙に変更して生成されたものであれば、この方法は Mutational fuzzing と呼ばれます。
もし Mutator が一定のプログラム情報によって誘導されることができる場合、これは GrayBox Fuzzing と呼ばれます。例えば、カバレッジに基づくファジングです。
もし Seed がパワースケジュールによってエネルギーの割り当てを受け、その後 Mutator が Seed のエネルギーの大きさに基づいてソートされる場合、この方法は Boosted GrayBox Fuzzing と呼ばれます。
グレーボックスファジングとは#
ホワイトボックスは、ソースコードを利用して制約解決やプログラム解析などを行います。
ブラックボックスは、ソースコードの情報を一切取得しません。
グレーボックスは、プログラムの一部の情報を取得します。一般的なのは、プログラムの実行カバレッジを取得することで、最も一般的な手法はバイナリインストゥルメンテーション（コンパイル時に各ジャンプブランチの後にカスタムのレコードコードを挿入すること）です。例えば、AFL はグレーボックスファジングです。
DGF（directed grey-box fuzzing）とは#
なぜ DGF が必要なのか#
ほとんどのグレーボックスファジングは、カバレッジに基づいてシードを使用してテストケースを進化させます。限られた時間内にできるだけ多くのパスをカバーするためです。これを行う主な理由は、コードのカバレッジとバグのカバレッジが正の相関関係にあるため、ファジングツールがより多くのコードをカバーすると、より多くのバグを見つけることができるからです。
しかし、すべてのコードを同等に扱うことはできません。なぜなら、ファジングツールがカバーするほとんどのコードにはバグが含まれていないからです。また、実際のアプリケーションでは、コードの分布を完全にカバーすることは非常に困難であるか、完全に不可能です。
この問題を克服するために、ターゲット指向のファジングが提案されました。
伝統的なグレーボックスファジングとの違い#
伝統的なグレーボックスファジングと比較して：
1. 目標が異なる：伝統的なグレーボックスファジングはコードカバレッジを向上させるために行われますが、DGF は特定のコードブロックのバグをテストすることに重点を置いています。
2. 技術が異なる：DGF は一般的にデータフローグラフと制御フローグラフを使用してシードとターゲットコードの距離を計算します。
DGF が最終的に解決しようとしている問題#
シードとターゲットの間の距離を利用して、適応度関数としてシードの選択を支援します。
ターゲットにより近い位置にあるシードは、より多くの変異の機会を持ち、グレーボックスファジングをターゲットの位置に導くために使用されます。
全体的なターゲット到達性の問題を最適化問題に変換することで、ターゲットとシードの位置の距離を定義する方法が問題の鍵です。
背景#
DGF は現在、2 つのキーメカニズムに基づいています：
1.DGF は、カバレッジに基づいた無向グレーボックスファジングからテストケースの進化をサポートできます。
2.DGF は、CFG（制御フローグラフ）の実行ノードとターゲットノードの距離を使用して、各テストケースの優先順位を測定し、ソートして、ファジャーにプログラムの特定のポイントに到達するためのガイダンスを提供します。
現在、DFG には 2 つの拡張性の問題があります：
1. 伝統的なカバレッジフィードバックは、目標のプログラムポイント（クラッシュが存在するセグメントと言えます）を見つけるための有意義なガイダンスを常に提供するわけではありません。
2. プログラムが複雑な制御構造を持つ場合、既存のシード距離アルゴリズムのパフォーマンスが低下します。
カバレッジに基づいたガイダンスは、プログラムが非常に大きいため、ガイダンスの方向が目標のプログラムポイントから逸れることがあります。Beacon はこの問題を解決しようと最初に試みましたが、目標のプログラムポイントに到達するかどうかを判断するために最も弱い事前条件を使用しましたが、この方法はループ構造が複雑な場合には機能しません。
プログラムが大きい場合、実行ノードチェーンの長さが非常に長くなり、目標のプログラムポイントとは関係のないセマンティックに関連するノードが多く含まれることがあります。WindRanger は、バイアス基本ブロック（DBB）を使用してバイアス問題を解決する最初の手法ですが、ループ構造ではうまく機能しません。
動機#
単純に言えば、C 言語の配列の範囲外アクセスエラーです。ユーザーはインデックスとして任意の大きさの整数を入力することができますが、脆弱な関数は入力されたインデックスを検証しません。
この脆弱な関数に到達するパスは 1 つだけですが、main からこのパスを通る間には多くの分岐パスがあり、テストケースのエネルギー配分が大幅に分散し、誤った方向に誘導されます。
また、AFLGo のシード距離計算と WindRanger のシード距離計算を比較した結果、同じ結果が得られました。つまり、複雑なループ構造が関与する場合、DBB に基づく距離測定も誤った方向に誘導される可能性があるということです。
解決策#
選択的カバレッジインストゥルメンテーション#
プログラム P の指定されたコードポイント t に到達するために、t で Def-Use グラフを逆方向に構築し、すべての依存ステートメントを収集し、Thin Slicing を使用します。
Thin Slicing について：ポインタのデリファレンス（余分な変数を削除）を行うことで、スライス（データ依存の逆方向のデータフローグラフと理解できます）のサイズを小さくし、ターゲット指向のファジングにより効率的なガイダンスを提供します。
なぜ DUG を使用するのかというと、DUG は多くの関係のないノードを自動的に無視することができるためです。つまり、データ依存関係のあるノードのみが残ります。また、対応する CFG にループがない限り、DUG にはループもありません（ループデータ依存性がない限り）。
セマンティック関連スコアリング#
目標ノードから DUG 上で最も遠い距離を 1 とし、その後のすべてのノードから目標ノードまでの最短距離ごとに 1 を加算することで、実行ノードパスのスコアの合計を計算します。
効果を達成するために、シードがより多くのノードを実行したり、より目標プログラムポイントに近いノードを実行した場合、総合スコアが高くなります（図 3c 参照）。
実験#
AFL、AFLGo、Beacon、WindRanger、DAFL の 5 つのファジャーを使用して、Beacon の論文中の 41 の脆弱性をファジングし、指標は TTE（Time-to-Exposure）であり、脆弱性をファジングして最初のクラッシュを得るまでの時間を示しています。
しかし、なぜか図に Beacon がありません
結果は、DAFL が他のファジャーよりも平均 1.93 倍速くなることがわかりました。
その後、以下の実験も行いました：
Thin slicing により、平均 2.01 倍速くなります。
選択的カバレッジインストゥルメンテーションにより、平均 1.73 倍速くなります（AFL と比較）。
セマンティック関連スコアリングにより、平均 1.39 倍速くなります（AFL と比較）。
これら 2 つのテクニックを組み合わせると、平均 1.93 倍速くなります（AFL と比較）。
議論#
DAFL の多目標サポートについて議論しました。つまり、実行ノードチェーン上に複数の目標プログラムポイントがある場合、それらの平均距離を関連スコアとして取得します。
また、C/C++、Go などの他の言語のサポートについても議論しました。
まとめ#
既存の DGF 距離計算には誤った方向に誘導される問題があるため、CFG の代わりに DUG を使用し、制御フロー情報の代わりにデータフロー情報を使用することで、関係のないノードが存在しなくなり、ファジャーのターゲット指向を誘導することができます。
Thin slicing により、DUG はよりシンプルになり、ファジャーの効率が向上します。
参考リンク#
Fuzzing 技術総括（Fuzz Testing の簡単な調査）
https://zhuanlan.zhihu.com/p/43432370
Directed Greybox Fuzzing に関する関連情報の整理
https://zhuanlan.zhihu.com/p/415316061
Hawkeye：Directed Greybox Fuzzing の技術
https://zhuanlan.zhihu.com/p/130767857
ファジングに目を向けよう - Directed Greybox Fuzzing（Directed Greybox Fuzzing）の概要
https://www.cnblogs.com/welkinchan/p/17685797.html
【学習ノート】Fuzzing 学習ノート 3 - グレーボックス Fuzzing
https://superlova.github.io/2020/08/20/%E3%80%90%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0%E3%80%91Fuzzing%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B03%E2%80%94%E2%80%94%E7%81%B0%E7%9B%92Fuzzing