[論文の読み方 USENIX 2023]DAFL: データ依存によってガイドされる指向性グレーボックスファジング

バックグラウンド#

Fuzzing の手法は、大量の入力を生成してテスト対象のプログラムのエラーを見つける方法です。

Fuzzing の重要なポイントの一つは、入力の生成方法であり、もう一つは入力のソート方法、そしてソフトウェア内部の情報の取得と適用です。

もし入力が完全に自分自身で構築されている場合、この方法は generational fuzzing と呼ばれます。

もし入力が元のシードをわずかに変更して生成される場合、この fuzzing は Mutational fuzzing と呼ばれます。

もし Mutator がある程度のプログラム情報によって誘導されることができる場合、これは GrayBox Fuzzing と呼ばれます。たとえば、カバレッジに基づくファジングです。

もし Seed が Power Schedule によってエネルギーの割り当てを受け、その後 Mutator が Seed のエネルギーの大きさに基づいてソートされる場合、この方法は Boosted GrayBox Fuzzing と呼ばれます。

グレーボックスファジングとは何ですか#

ホワイトボックスは、ソースコードを利用して制約解決やプログラム解析などを行います。

ブラックボックスは、ソースコードの情報を一切取得しません。

グレーボックスは、プログラムの一部の情報を取得します。一般的なのは、プログラムの実行カバレッジを取得することで、最も一般的な手法はバイナリインストゥルメンテーション（コンパイル時にカスタムのレコードコードをジャンプブランチの後に挿入する）です。たとえば、AFL はグレーボックスファジャーです。

DGF（directed grey-box fuzzing）とは何ですか#

DGF が存在する理由#

ほとんどのグレーボックスファジングは、カバレッジに基づいてシードを使用してテストケースを進化させるため、限られた時間内にできるだけ多くのパスをカバーします。これを行う主な理由は、コードのカバレッジとバグのカバレッジは正の相関関係にあるため、ファジングツールがより多くのコードをカバーすると、より多くのバグを見つけることができるからです。

しかし、すべてのコードを同等に扱うことはできません。なぜなら、ファジングツールがカバーするほとんどのコードにはバグが含まれていないからです。また、実際のアプリケーションでは、コードの分布を完全にカバーすることは非常に困難であるか、完全に不可能です。

この問題を克服するために、ガイド付きファジングが提案されました。

伝統的なグレーボックスファジングとの違い#

伝統的なグレーボックスファジングと比較して：

1. 目標が異なります：伝統的なグレーボックスファジングはコードカバレッジを向上させるために行われますが、DGF は特定のコードブロックのバグをテストすることに重点を置いています。
2. 技術が異なります：DGF は通常、データフローグラフと制御フローグラフを使用してシードとターゲットコードセグメントの距離を計算するためのものです。

DGF が最終的に解決しようとしている問題#

シードとターゲットの間の距離を利用して、適応度関数としてシードの選択を支援します。

ターゲットにより近い位置にあるシードは、より多くの変異の機会を持ち、グレーボックスファジングをターゲットの位置に誘導します。

全体的なガイド付きグレーボックスファジングは、到達可能性の問題を最適化問題に変換します。

つまり、生成されたシードとターゲット位置の距離をどのように定義して最適化するかが、問題の鍵です。

背景#

DGF は現在、2 つのキーメカニズムに基づいています：

1.DGF は、カバレッジガイドのないグレーボックスファジングからテストケースを進化させることができます。
2.DGF は、CFG（制御フローグラフ）の実行ノードとターゲットノードの距離を使用して、各テストケースの優先順位を測定し、ソートし、ファジャーにターゲットプログラムポイントへの到達を指示します。
現在、2 つの DFG の拡張性の問題があります：

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 の脆弱性に対して fuzz を実行し、指標は TTE（Time-to-Exposure）であり、脆弱性を fuzz するのにかかる時間です。

ただし、なぜか図に 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