ファジング

プログラミングとソフトウェア開発において、ファジングまたはファジング テストは、無効なデータ、予期しないデータ、またはランダムなデータをコンピュータ プログラムへの入力として提供する自動ソフトウェア テスト手法です。その後、プログラムは、クラッシュ、組み込みコードアサーションの失敗、または潜在的なメモリリークなどの例外がないか監視されます。通常、ファジング ツールは、構造化された入力を受け取るプログラムをテストするために使用されます。この構造は、ファイル形式やプロトコルなどで指定され、有効な入力と無効な入力を区別します。効果的なファジング ツールは、パーサーによって直接拒否されないという点で「十分に有効」である半有効な入力を生成しますが、プログラムのより深い部分で予期しない動作を引き起こし、適切に処理されていない コーナー ケースを明らかにするのに「十分に無効」です。

セキュリティの観点からは、信頼境界を越える入力が最も有用であることが多いです。^[1]たとえば、特権ユーザーのみがアクセスできる構成ファイルを解析するコードをファジングするよりも、任意のユーザーがアップロードしたファイルを処理するコードをファジングする方が重要です。

「ファズ」という用語は、ウィスコンシン大学のバートン・ミラー教授が教鞭を執った大学院の上級オペレーティングシステムクラス (CS736) の1988 年の授業プロジェクト^[2]に由来し、その結果はその後 1990 年に発表されました。^{[3] [4]} UNIXユーティリティをファズテストすることは、ユーティリティのランダムな入力とコマンドラインパラメータを自動的に生成することを意味していました。このプロジェクトは、UNIX コマンドラインプログラムの信頼性をテストするために、多数のランダムな入力をクラッシュするまで立て続けに実行するように設計されました。ミラーのチームは、テストしたユーティリティの 25 ～ 33 パーセントをクラッシュさせることができました。次に、各クラッシュをデバッグして原因を特定し、検出された各障害を分類しました。他の研究者が他のソフトウェアで同様の実験を行えるように、ツールのソースコード、テスト手順、および生の結果データが公開されました。^[5]この初期のファズテストは、現在ではブラックボックス、世代別、非構造化 (ダムまたは「クラシック」) ファズテストと呼ばれています。

バートン・ミラー教授によると、「プロジェクトの説明を書く過程で、この種のテストに名前を付ける必要がありました。ランダムで構造化されていないデータという感覚を呼び起こす名前が欲しかったのです。いくつかのアイデアを試した後、ファズという用語に落ち着きました。」^[4]

この初期の取り組みの重要な貢献は、単純な (ほとんど単純化された) オラクルでした。プログラムは、ランダム入力によってクラッシュまたはハングした場合、テストに不合格となり、それ以外の場合は合格とみなされました。テスト オラクルの構築は難しい場合がありますが、この初期のファズ テストのオラクルは、適用が簡単で汎用的でした。

2012年4月、Googleは、 Chromiumウェブブラウザのセキュリティ上重要なコンポーネント向けのクラウドベースのファジングインフラストラクチャであるClusterFuzzを発表しました。^[6]セキュリティ研究者は独自のファジングツールをアップロードし、アップロードされたファジングツールでClusterFuzzがクラッシュを発見した場合にバグ報奨金を受け取ることができます。

2014年9月、広く使用されているUNIX BashシェルのセキュリティバグファミリーとしてShellshock ^{[7]が公開されました。Shellshockの脆弱性のほとんどは、ファザー}AFLを使用して発見されました。^[8]（一部のWebサーバー展開など、インターネットに接続された多くのサービスは、特定のリクエストを処理するためにBashを使用しているため、攻撃者は脆弱なバージョンのBashに任意のコマンドを実行させることができます。これにより、攻撃者はコンピュータシステムに不正にアクセスできるようになります。^[9]）

2015 年 4 月、Hanno Böck 氏は、ファジング ツール AFL が 2014 年の Heartbleed 脆弱性をどのように発見できたかを示しました。^{[10] [11]} ( Heartbleed脆弱性は 2014 年 4 月に公開されました。これは、暗号化された通信を攻撃者が解読できる深刻な脆弱性です。この脆弱性は、TLSを実装し、インターネット上のほとんどのサーバーで使用されているOpenSSLに誤って導入されました。Shodanは、2016 年 4 月に 238,000 台のマシンが依然として脆弱であると報告しました。^[12] 2017 年 1 月には 200,000 台でした。 ^[13] )

2016年8月、国防高等研究計画局（DARPA）は、 11時間続いた完全自動化されたキャプチャー・ザ・フラッグ競技である第1回サイバー・グランド・チャレンジの決勝戦を開催した。 ^[14]目的は、ソフトウェアの欠陥をリアルタイムで発見、悪用、修正できる自動防御システムを開発することだった。ファジングは、対戦相手のソフトウェアの欠陥を発見するための効果的な攻撃戦略として使用された。これは、脆弱性検出の自動化において大きな可能性を示した。優勝したのは、 David Brumley率いるチームForAllSecureが開発した「Mayhem」 ^[15]と呼ばれるシステムだった。

2016年9月、マイクロソフトはソフトウェアのセキュリティ上重大なバグを見つけるためのクラウドベースのファズテストサービスであるProject Springfieldを発表しました。^[16]

2016年12月、Googleは、セキュリティ上重要なオープンソースプロジェクトを継続的にファジングできるOSS-Fuzzを発表しました。^[17]

Black Hat 2018で、Christopher Domas氏はファジングを使用してプロセッサ内の隠されたRISCコアの存在を明らかにすることを実演しました。 ^[18]このコアは既存のセキュリティチェックをバイパスして、リング3から リング0のコマンド を実行することができました。

2020年9月、マイクロソフトはソフトウェアバグの検出を自動化するセルフホスト型のファジング・アズ・ア・サービス・プラットフォームであるOneFuzzをリリースした。^[19] WindowsとLinuxをサポートしている。 ^[20] 3年後の2023年11月1日にアーカイブされた。^[21]

ランダム入力によるプログラムのテストは、データがまだパンチカードに保存されていた1950年代にまで遡ります。^[22]プログラマーはゴミ箱から取り出したパンチカードや乱数の入ったカードデッキをコンピュータプログラムへの入力として使用していました。実行時に望ましくない動作が明らかになった場合、バグが検出されたことになります。

ランダム入力の実行は、ランダム テストまたはモンキー テストとも呼ばれます。

1981年、デュランとンタフォスは、ランダム入力によるプログラムテストの有効性を正式に調査しました。^{[23] [24]}ランダムテストはプログラムをテストする最悪の手段であると広く認識されていましたが、著者らは、ランダムテストがより体系的なテスト手法よりも費用対効果の高い代替手段であることを示すことができました。

1983年、アップル社のスティーブ・キャップスは「ザ・モンキー」^{[25]を開発した。これは、} MacPaintなどの古典的なMac OSアプリケーション用のランダムな入力を生成するツールである。^[26]比喩的な「モンキー」は、猿がタイプライターのキーボードでキーをランダムに無限の時間押し続けると、最終的にシェイクスピアの全作品を打ち出すという無限猿定理を指す。テストの場合、猿はクラッシュを引き起こす特定の入力シーケンスを書き込む。

1991年にcrashmeツールがリリースされました。これは、ランダムに選択されたパラメータでシステムコールをランダムに実行することで、UnixおよびUnix系 オペレーティングシステムの堅牢性をテストすることを目的としていました。^[27]

ファジングツールはいくつかの方法で分類できる: ^{[28] [1]}

1. ファザーは、入力が最初から生成されるか、既存の入力を変更することによって生成されるかに応じて、生成ベースまたは変異ベースになります。
2. ファザーは、入力構造を認識しているかどうかに応じて、ダム (非構造化) またはスマート (構造化) になります。
3. ファザーは、プログラム構造を認識しているかどうかに応じて、ホワイト ボックス、グレー ボックス、またはブラック ボックスになります。

変異ベースのファジングツールは、ファジング中に既存のシード入力コーパスを活用します。提供されたシードを変更（または変異）することで入力を生成します。 ^[29]たとえば、画像ライブラリlibpng をファジングする場合、ユーザーは有効なPNG画像ファイルのセットをシードとして提供しますが、変異ベースのファジングツールはこれらのシードを変更して各シードの半有効なバリアントを生成します。シードファイルのコーパスには、潜在的に類似した入力が何千も含まれている可能性があります。自動化されたシード選択（またはテストスイートの削減）により、ユーザーはファジングキャンペーン中に発見されるバグの総数を最大化するために最適なシードを選択できます。^[30]

生成ベースのファザーは、入力をゼロから生成します。たとえば、スマートな生成ベースのファザー^[31]は、ユーザーが提供した入力モデルを使用して新しい入力を生成します。突然変異ベースのファザーとは異なり、生成ベースのファザーはシード入力のコーパスの存在や品質に依存しません。

一部のファジングツールは、ゼロから入力を生成する機能と、既存のシードの変異によって入力を生成する機能の両方を備えています。^[32]

通常、ファジング ツールは、ファイル、キーボードやマウスの一連のイベント、メッセージの一連のイベントなど、構造化された入力を受け取るプログラムの入力を生成するために使用されます。この構造により、プログラムによって受け入れられて処理される有効な入力と、プログラムによってすぐに拒否される無効な入力が区別されます。有効な入力を構成する要素は、入力モデルで明示的に指定できます。入力モデルの例としては、形式文法、ファイル形式、GUIモデル、ネットワーク プロトコルなどがあります。通常は入力と見なされない項目でも、データベースの内容、共有メモリ、環境変数、スレッドの正確なインターリーブなど、ファジングできます。効果的なファジング ツールは、パーサーから直接拒否されない程度に「十分に有効」で、コーナー ケースにストレスを与えて興味深いプログラム動作を引き起こす可能性がある程度に「十分に無効」な、半有効な入力を生成します。

スマートな（モデルベース、^[32]、文法ベース、^{[31] [33]、}またはプロトコルベース^[34]）ファジングツールは、入力モデルを活用して、有効な入力の割合を高めます。たとえば、入力を抽象構文木としてモデル化できる場合、スマートな突然変異ベースのファジングツール^{[33]は、ランダムな}変換を使用して、完全なサブツリーを1つのノードから別のノードに移動します。入力を形式文法でモデル化できる場合、スマートな生成ベースのファジングツール^[31]は、生成ルールをインスタンス化して、文法に関して有効な入力を生成します。ただし、通常、入力モデルは明示的に提供する必要がありますが、モデルが独自のもの、不明なもの、または非常に複雑な場合は、これを実行するのは困難です。有効な入力と無効な入力の大規模なコーパスが利用できる場合は、AngluinのL*アルゴリズムなどの文法誘導技術を使用して入力モデルを生成できます。^{[35] [36]}

ダム ファザー^{[37] [38]}は入力モデルを必要としないため、より幅広いプログラムをファジングするために使用できます。たとえば、AFL は、ランダム ビットを反転したり、ランダム バイトを「興味深い」値に置き換えたり、データ ブロックを移動または削除したりしてシード ファイルを変更する、ダム変異ベースのファザーです。ただし、ダム ファザーは有効な入力の割合が低くなり、プログラムの主要コンポーネントではなくパーサーコードに負荷をかける可能性があります。ダム ファザーの欠点は、巡回冗長検査(CRC)の有効なチェックサムの構築によって説明できます。CRC は、入力ファイルに含まれるデータの整合性が送信中に保持されることを保証するエラー検出コードです。チェックサムは入力データに対して計算され、ファイルに記録されます。プログラムが受信ファイルを処理し、記録されたチェックサムが再計算されたチェックサムと一致しない場合、ファイルは無効として拒否されます。 CRCを認識しないファジングツールが正しいチェックサムを生成する可能性は低い。しかし、保護されたデータを愚かな変異ベースのファジングツールが変更すると、変異した入力の潜在的なチェックサムを識別して再計算する試みがある。^[39]

通常、ファジングツールは、コードカバレッジのレベルが高いほど効果的であると見なされます。その理由は、ファジングツールがプログラム内の特定の構造要素を実行しないと、これらの要素に隠れているバグも検出できないためです。一部のプログラム要素は、他の要素よりも重要だと見なされます。たとえば、除算演算子はゼロ除算エラーを引き起こす可能性があり、システムコールはプログラムをクラッシュさせる可能性があります。

ブラックボックスファザー^{[37] [33]}はプログラムをブラックボックスとして扱い、内部プログラム構造を認識しません。たとえば、ランダムに入力を生成するランダム テストツールはブラックボックス ファザーと見なされます。したがって、ブラックボックス ファザーは 1 秒あたり数百の入力を実行でき、簡単に並列化でき、任意のサイズのプログラムに拡張できます。ただし、ブラックボックス ファザーは表面をなぞって「浅い」バグを露呈させるだけです。そのため、入力を与えられたプログラムの出力を観察することで、ファジング中にプログラムの内部構造 (および動作) について段階的に学習できるブラックボックス ファザーの開発が試みられています。たとえば、LearnLib はアクティブ ラーニングを使用して、 Web アプリケーションの動作を表す オートマトンを生成します。

ホワイトボックスファザー^{[38] [32]は、}プログラム分析を利用してコード カバレッジを体系的に増やしたり、特定の重要なプログラム位置に到達したりします。たとえば、SAGE ^{[40] は}シンボリック実行を利用してプログラム内のさまざまなパスを体系的に探索します (コンコリック実行と呼ばれる手法)。プログラムの仕様が利用可能な場合、ホワイトボックス ファザーはモデルベース テストの手法を利用して入力を生成し、プログラム出力をプログラム仕様と照合します。ホワイトボックス ファザーは、プログラムの奥深くに隠れているバグを非常に効果的に検出できます。ただし、(プログラムまたはその仕様の) 分析にかかる時間が長すぎる場合があります。ホワイトボックス ファザーが入力を生成するのに比較的時間がかかりすぎる場合は、ブラックボックス ファザーの方が効率的です。^[41]そのため、ブラックボックス ファザーの効率とホワイトボックス ファザーの有効性を組み合わせる試みがあります。^[42]

グレーボックスファザーは、プログラム分析ではなくインストルメンテーションを利用してプログラムに関する情報を収集します。たとえば、AFLとlibFuzzerは軽量のインストルメンテーションを利用して、入力によって実行される基本ブロックの遷移をトレースします。これにより、パフォーマンスのオーバーヘッドは適度に発生しますが、ファジング中にコードカバレッジの増加がファザーに通知されるため、グレーボックスファザーは非常に効率的な脆弱性検出ツールになります。^[43]

ファジングは主に、悪意を持って悪用される可能性のあるセキュリティ上重要なプログラムの脆弱性を明らかにするための自動化された手法として使用されます。 ^{[6] [16] [17]}より一般的には、ファジングはバグが存在しないことを示すためではなく、バグが存在することを示すために使用されます。バグが見つからないまま数週間ファジングキャンペーンを実行しても、プログラムが正しいことが証明されるわけではありません。 ^[44]結局のところ、プログラムはまだ実行されていない入力に対して失敗する可能性があります。すべての入力に対してプログラムを実行するのは法外なコストがかかります。すべての入力に対してプログラムが正しいことを証明することが目的である場合、正式な仕様が存在し、形式手法の手法を使用する必要があります。

バグを発見するためには、ファジングツールは期待される（通常の）プログラム動作と予期しない（バグのある）プログラム動作を区別できなければなりません。しかし、機械は必ずしもバグと機能を区別できるわけではありません。自動ソフトウェアテストでは、これはテストオラクル問題とも呼ばれます。^{[45] [46]}

通常、ファジングツールは、仕様がない場合にクラッシュする入力とクラッシュしない入力を区別し、単純で客観的な基準を使用します。クラッシュは簡単に識別でき、潜在的な脆弱性（サービス拒否や任意のコード実行など）を示している可能性があります。ただし、クラッシュがないことは脆弱性がないことを示すものではありません。たとえば、Cで書かれたプログラムは、入力によってバッファ オーバーフローが発生したときにクラッシュする場合とクラッシュしない場合があります。むしろ、プログラムの動作は未定義です。

ファジングツールをクラッシュ以外の障害に対してより敏感にするために、障害が検出されたときにプログラムをクラッシュさせるアサーションを挿入するサニタイザーを使用することができます。^{[47] [48]}バグの種類に応じて異なるサニタイザーがあります。

• バッファオーバーフローや解放後使用などのメモリ関連のエラーを検出する（AddressSanitizerなどのメモリデバッガを使用）
• 競合状態とデッドロックを検出する（ThreadSanitizer）
• 未定義の動作を検出する(UndefinedBehaviorSanitizer)
• メモリリークを検出する（LeakSanitizer）、または
• 制御フローの整合性をチェックします(CFISanitizer)。

ファジングは、リファレンス実装が利用可能な場合、「差分」バグの検出にも使用できます。自動回帰テストでは、^[49]生成された入力が同じプログラムの 2 つのバージョンで実行されます。自動差分テストでは、^[50]生成された入力が同じプログラムの 2 つの実装で実行されます (たとえば、lighttpdとhttpd はどちらも Web サーバーの実装です)。2 つのバリアントが同じ入力に対して異なる出力を生成する場合、一方にバグがある可能性があり、より詳しく調べる必要があります。

静的プログラム分析は、実際にプログラムを実行せずに分析します。これにより、ツールが実際には存在しないプログラムの問題を報告するという誤検知が発生する可能性があります。ファジングと動的プログラム分析を組み合わせることで、報告された問題を実際に証明する入力を生成することができます。^[51]

現代のウェブブラウザは広範囲に渡ってファジングされています。Google ChromeのChromiumコードは、Chromeセキュリティチームによって15,000コアで継続的にファジングされています。^[52] Microsoft EdgeとInternet Explorerについては、Microsoftは製品開発中に670マシン年でファジングテストを実施し、10億のHTMLファイルから4000億を超えるDOM操作を生成しました。^{[53] [52]}

ファザーは比較的短時間で大量の入力を生成します。例えば、2016年にGoogle OSS-fuzzプロジェクトは1週間あたり約4兆個の入力を生成しました。 ^[17]そのため、多くのファザーは、障害を誘発する入力の自動生成に続く、通常は手動で面倒なタスクを自動化するツールチェーンを提供しています。

自動バグトリアージは、多数の障害誘発入力を根本原因別にグループ化し、各バグを重大度別に優先順位を付けるために使用されます。ファジングツールは多数の入力を生成し、障害誘発入力の多くは実質的に同じソフトウェアバグを露呈する可能性があります。これらのバグのうち、セキュリティ上重要なものは一部だけであり、優先度を高くしてパッチを適用する必要があります。たとえば、CERTコーディネーションセンターは、生成されたスタックトレースによってクラッシュ入力をグループ化し、各グループを悪用される可能性に応じてリストするLinuxトリアージツールを提供しています。^[54] Microsoftセキュリティリサーチセンター（MSEC）は、「！exploitable」ツールを開発しました。これは、最初にクラッシュ入力のハッシュを作成してその一意性を決定し、次に悪用可能性の評価を割り当てます。^[55]

• 悪用可能
• おそらく悪用可能
• おそらく悪用不可能、または
• 未知。

これまで報告されておらず、トリアージされたバグは、バグ追跡システムに自動的に報告されることがあります。たとえば、OSS-Fuzzは、セキュリティ上重要なソフトウェアプロジェクトに対して大規模で長期にわたるファジングキャンペーンを実施しており、これまで報告されていなかった個別のバグがそれぞれバグトラッカーに直接報告されています。^[17] OSS-Fuzzバグトラッカーは、脆弱なソフトウェアのメンテナーに自動的に通知し、アップロードされた最小化された障害誘発入力を使用して、最新のリビジョンでバグが修正されているかどうかを定期的にチェックします。

自動入力最小化（またはテストケース削減）は、障害を誘発する入力のうち、実際に障害を誘発している部分を切り離すための自動デバッグ手法です。 ^{[56] [57]}障害を誘発する入力が大きく、ほとんどが不正な形式である場合、開発者がバグの原因を正確に理解することは困難です。障害を誘発する入力が与えられれば、自動最小化ツールは元のバグを再現しながら、可能な限り多くの入力バイトを削除します。たとえば、デルタデバッグは、拡張バイナリ検索アルゴリズムを使用してそのような最小入力を見つける自動入力最小化手法です。 ^[58]

以下は、学術文献で「人気がある」、「広く使用されている」などと説明されているファザーのリストです。^{[59] [60]}

• アメリカンファジーロップ（ファザー）
• 結腸テスト
• グリッチ
• グリッチ
• サルのテスト
• ランダムテスト
• 協調的な脆弱性開示
• 実行時エラー検出
• セキュリティテスト
• スモークテスト（ソフトウェア）
• シンボリック実行
• システムテスト
• テスト自動化

• Nappa, A.; Blázquez, E. (2023). マシンに対するファジング: Qemu でエミュレートされた IoT デバイスを使用して脆弱性調査を自動化する。Packt Publishing, Limited. ISBN 9781804614976。エミュレートされた IoT デバイスを使用した自動化された脆弱性調査に関する包括的なガイド。
• ツェラー、アンドレアス。ゴピナート、ラーフル。ベーメ、マルセル。フレイザー、ゴードン。クリスチャン・ホラー (2019)。ファジングブック。ザールブリュッケン: CISPA + ザールランド大学。ファジングに関する無料のオンライン入門教科書。
• Ari Takanen、Jared D. DeMott、Charles Miller、『ソフトウェア セキュリティ テストと品質保証のためのファジング』、2008 年、ISBN 978-1-59693-214-2 
• Michael Sutton、Adam Greene、Pedram Amini。Fuzzing : Brute Force Vulnerability Discovery、2007 年、ISBN 0-321-44611-9。 
• H. Pohl、「脅威モデリングとファジングの支援によるゼロデイ脆弱性のコスト効率の高い特定」、2011 年
• Fabien Duchene、モデル推論支援による進化的ファジングによる Web 脆弱性の検出、2014 年、博士論文
• Bratus, S.、Darley, T.、Locasto, M.、Patterson, ML、Shapiro, RB、Shubina, A.、「Trusting Trust」における植え付けられたバグを超えて: 入力処理の最前線、IEEE Security & Privacy Vol 12、Issue 1、(2014 年 1 月 - 2 月)、pp. 83 ～ 87 — 基本的に、ファジングが非常にうまく機能する理由を強調しています。入力は、インタープリターの制御プログラムであるためです。

• Fuzzing Project には、チュートリアル、セキュリティ上重要なオープンソースプロジェクトのリスト、その他のリソースが含まれています。
• ウィスコンシン大学のファズ テスト (オリジナルのファズ プロジェクト) 論文とファズ ソフトウェアのソース。
• ソフトウェアを失敗させる入力の設計、ファジーテストを含む会議ビデオ
• 「プロトコルを考慮した」ファジング フレームワークの構築