アメリカンファジーロップ（ソフトウェア）

アメリカンファジーロップ

American Fuzzy Lop の afl-fuzz がテストプログラムで実行中
開発者	ミハウ・ザレフスキ
初回リリース	2013年11月12日; 11年前 ( 2013-11-12 )
安定版リリース	2.57b / 2020年6月30日; 4年前[1] ( 2020-06-30 )
リポジトリ	github.com/google/AFL
書かれた	C、アセンブリ
オペレーティング·システム	クロスプラットフォーム
タイプ	ファザー
ライセンス	Apache ライセンス 2.0
Webサイト	lcamt​​uf.coredump.cx/afl/

American Fuzzy Lop ( AFL ) は、すべて小文字でamerican fuzzy lopと表記され、遺伝的アルゴリズムを使用してテストケースのコードカバレッジを効率的に増やすフリーソフトウェア ファザーです。これまでに、X.Org Server、^[2]、PHP、^[3]、OpenSSL、^{[4] [5]、}pngcrush、bash、^[6]、Firefox、^[7]、BIND、^{[8] [9]、}Qt、^[10]、SQLite ^[11]などの主要なフリーソフトウェアプロジェクトで数十の重大なソフトウェアバグを検出しました。

^{AFL [12]}は、2013 年 11 月に最初にリリースされて以来、セキュリティ研究で最も広く使用されているファザーの 1 つになりました。リリース後何年もの間、AFL は「最先端の」ファザーと見なされてきました。^[13] AFL は「ファジングのデファクト スタンダード」と見なされており、^[14] AFL のリリースは、研究分野としてのファジングの発展に大きく貢献しました。^{[15] AFL は学術界で広く使用されており、学術的なファザーは AFL の}フォークであることが多く、AFL は新しい手法を評価するためのベースラインとしてよく使用されています。^{[16] [17]}

アメリカン・ファジー・ロップのソースコードはGitHubで公開されています。その名前はウサギの一種であるアメリカン・ファジー・ロップに由来しています。

AFL では、テスト対象のアプリケーションを実行するサンプル コマンドと、少なくとも 1 つの小さなサンプル入力をユーザーが提供する必要があります。入力は、標準入力経由で、またはプロセス コマンド ラインで指定された入力ファイルとして、テスト対象のプログラムに渡すことができます。ネットワーク プログラムのファジングは現在直接サポートされていませんが、場合によっては、この問題に対する実行可能な解決策があります。^[18]たとえば、オーディオ プレーヤーの場合、American fuzzy lop に短いサウンド ファイルを開くように指示することができます。次に、ファジング ツールは指定されたコマンドを実際に実行しようとし、成功した場合は、同じ動作をトリガーする最小のファイルに入力ファイルを縮小しようとします。

この初期段階の後、AFL は入力ファイルにさまざまな変更を適用して、実際のファジング プロセスを開始します。テスト対象のプログラムがクラッシュまたはハングする場合、これは通常、新しいバグ、おそらくセキュリティの脆弱性が発見されたことを意味します。この場合、変更された入力ファイルは、ユーザーがさらに検査できるように保存されます。

ファジングのパフォーマンスを最大化するために、American fuzzy lop では、制御フローを追跡するヘルパー関数を使用してコードをインストルメント化するユーティリティ プログラムの支援を受けてテスト対象プログラムをコンパイルすることを想定しています。これにより、ファジングツールは入力に応じてターゲットの動作がいつ変化したかを検出できます。これが不可能な場合は、ブラック ボックス テストもサポートされます。

ファジングツールは、さまざまな入力に対してプログラムを繰り返し実行することで、対象プログラムの予期しない動作（つまり、バグ）を見つけようとします。前述のように、AFLはグレーボックスファジングツールです。つまり、コンパイル時に対象プログラムにコードカバレッジを測定するためのインストルメンテーションを注入し、カバレッジメトリックを使用して新しい入力の生成を指示します。AFLのファジングアルゴリズムは、その後の多くのグレーボックスファジングツールに影響を与えました。^{[20] [21]}

AFLへの入力は、インストルメント化されたターゲットプログラム（テスト対象システム）とコーパス、つまりターゲットへの入力のコレクションです。入力はテストケースとも呼ばれます。アルゴリズムは入力のキューを維持し、入力コーパスに初期化されます。全体的なアルゴリズムは次のように機能します。^[22]

1. キューから次の入力をロードする
2. テストケースを最小限に抑える
3. テスト ケースを変更します。変更によってコード カバレッジが増加する場合は、それをキューに追加します。変更によってクラッシュまたはハングが発生する場合は、後で検査できるようにディスクに保存します。
4. ステップ1に進む

新しい入力を生成するために、AFLは既存の入力にさまざまな突然変異を適用します。^{[23]これらの突然変異は、ターゲットプログラムの入力形式にほとんど依存せず、通常は入力を単純な}バイナリデータの塊として扱います。

まず、AFLは各入力に対して決定論的な突然変異のシーケンスを適用します。これらは入力のさまざまなオフセットに適用されます。これには以下が含まれます。^{[24] [25]}

• 1～32ビットの反転（つまり、否定または反転）
• リトルエンディアンとビッグエンディアンの両方のエンコードで、8 ビット、16 ビット、32 ビットの整数を増分および減分します。
• 入力の一部を「約 2 ダースの「興味深い」値」で上書きします。これには、ゼロ、さまざまな幅の符号付きおよび符号なし整数の最大値と最小値が含まれます (これもリトルエンディアンとビッグエンディアンの両方のエンコードで行われます)。
• 入力の一部を、ユーザー指定または自動検出されたトークン（ マジックバイト、テキストベースの形式のキーワードなど）の「辞書」から抽出したデータに置き換える^{[26] [23] [27]}

利用可能なすべての決定論的突然変異を適用した後、AFLは2〜128の突然変異が連続して適用される段階である大混乱に進みます。これらの突然変異は次のいずれかです。 ^[23]

• 上で述べた決定論的突然変異
• ランダムな値でバイトを上書きする
• マルチバイト「ブロック」に対する操作:
  • ブロックの削除
  • ブロックの複製
  • ブロック内の各バイトを単一の値に設定する

AFL がキュー全体を循環して新しいコード カバレッジを達成する入力を生成しない場合は、スプライシングを開始します。スプライシングでは、キューから 2 つの入力を取得し、任意の位置で切り捨てて連結し、その結果に Havoc ステージを適用します。

AFLは、コードカバレッジを測定するためにビン化されたヒットカウントの使用を開拓しました。^[28]著者は、この技術がパス爆発を軽減すると主張しています。^{[29] [30]}

概念的には、AFL は、ターゲットの特定の実行がターゲットの制御フロー グラフの各エッジを通過する回数をカウントします。ドキュメントでは、これらのエッジをタプルと呼び、カウントをヒットカウントと呼びます。実行の最後に、ヒットカウントは1、2、3、4～7、8～15、16～31、32～127、および 128 以上の 8 つのバケットにビンまたはバケット化されます。AFL は、これまでの実行によって生成された (タプル、ビン化されたカウント) ペアのグローバル セットを維持します。入力が (タプル、ビン化されたカウント) ペアを生成し、それがまだグローバル セットにない場合は、その入力は「興味深い」とみなされ、キューに追加されます。

実際には、ヒットカウントは効率的だが損失のある方式で収集され、処理されます。コンパイル時のインストルメンテーションは、ターゲットプログラムの制御フローグラフの各分岐に、概念的に次のようなコードを挿入します。^[31]

cur_location = < COMPILE_TIME_RANDOM > ; shared_mem [ cur_location ^ prev_location ] ++ ; prev_location = cur_location >> 1 ;  
  
    

ここで、<COMPILE_TIME_RANDOM>はランダムな整数であり、はファザーとターゲット間で 共有されるshared_mem64キロバイトのメモリ領域です。

この表現は、単純なブロックまたはステートメントのカバレッジよりもきめが細かく（より多くの実行を区別します）なっていますが、それでも線形時間の「興味深さ」テストが可能になります。

入力が小さいほど実行時間が短くなるという仮定に基づいて、AFLはキュー内のテストケースを最小化またはトリミングしようとします。 ^{[23] [32]}トリミングは入力からブロックを削除することによって機能します。トリミングされた入力でも同じカバレッジが得られる場合（「カバレッジの測定」を参照）、元の入力は破棄され、トリミングされた入力がキューに保存されます。

AFLはキューから優先入力のサブセットを選択し、非優先入力はある確率でスキップされる。^{[33] [28]}

American fuzzy lopが解決しなければならなかった課題の1つは、1秒間に数百のプロセスを効率的に生成するforkことでした。すべてのプロセスを最初から生成する元のエンジンとは別に、American fuzzy lopはシステムコールに大きく依存するデフォルトのエンジンを提供しています。^{[34] [28]これは、} LLVMの遅延フォークサーバーモードまたは同様の永続モードを活用することでさらに高速化できますが、テスト対象のプログラムを変更する必要があるというコストがかかります。^[35]また、American fuzzy lopは、ネットワーク経由で同じプログラムをファジングすることもサポートしています。

American fuzzy lop は、ファジング プロセスに関する統計情報をリアルタイムで表示するカラフルなコマンド ライン インターフェイスを備えています。さまざまな設定は、コマンド ライン オプションまたは環境変数によってトリガーできます。また、プログラムは、マシンが読み取り可能な形式でファイルから実行時統計情報を読み取ることもできます。

afl-fuzzバイナリ計測に使用できる およびツールに加えて、American fuzzy lop には、ファジング プロセスの監視を目的としたユーティリティ プログラムが備わっています。それとは別に、テスト ケースとテスト コーパスの最小化に使用できるafl-cminおよびがあります。これは、 によって生成されたテスト ケースが他のファザーによって使用される場合 afl-tminに役立ちます。afl-fuzz

AFL は、新しいファジング手法を検証したり、さまざまな種類のプログラムにファジングを適用したりするために、何度もフォークされてきました。注目すべきフォークには次のようなものがあります。

• AFL++
• MOPT-AFL ^[36]
• AFLファスト^[37]
• AFLSmart ^[38]
• AFLGo ^[39]
• シムCC-AFL ^[40]
• WinAFL、「WindowsバイナリをファジングするためのAFLのフォーク」^[41]

AFL++（AFLplusplus）^{[43]は、2017年9月以来}Googleの上流AFL開発が比較的不活発であったために作成された、コミュニティによって維持されているAFLのフォークです。新しい機能と高速化が含まれています。^[44]

オープンソースソフトウェアに無料のファジングサービスを提供するGoogleのOSS-Fuzzイニシアチブは、2021年1月にAFLオプションをAFL++に置き換えました。^{[45] [46]}

• Fioraldi, Andrea; Mantovani, Alessandro; Maier , Dominik; Balzarotti, Davide (2023 年 1 月 20 日)。「American Fuzzy Lop の分析 - FuzzBench の評価」。ACM Transactions on Software Engineering and Methodology。32 (2): 1–26。doi : 10.1145 /3580596。ISSN 1049-331X。S2CID  247088398  。
• Metzman, Jonathan; Szekeres, László; Simon, Laurent; Sprabery, Read; Arya, Abhishek (2021 年 8 月 18 日)。「FuzzBench: オープンなファザー ベンチマーク プラットフォームおよびサービス」。第 29 回 ACM 欧州ソフトウェア エンジニアリング会議合同会議およびソフトウェア エンジニアリングの基礎に関するシンポジウムの議事録。ESEC / FSE 2021。米国ニューヨーク州ニューヨーク: Association for Computing Machinery。pp. 1393–1403。doi : 10.1145 /3468264.3473932。ISBN 978-1-4503-8562-6. S2CID  237205274。

• AFL公式ドキュメント
• AFL の作者である Michał Zalewski のブログ。このブログには、AFL の技術的な詳細を詳しく説明した投稿がいくつか掲載されています。