Loading article…
プログラミングやソフトウェア開発において、ファジングまたはファズテストとは、コンピュータプログラムに無効なデータ、予期しないデータ、またはランダムなデータを入力として与える自動化されたソフトウェアテスト手法です。プログラムは、クラッシュ、組み込みコードのアサーションの失敗、潜在的なメモリリークなどの例外がないか監視されます。通常、ファザーは構造化された入力を受け取るプログラムのテストに使用されます。この構造は、ファイル形式やプロトコルなどで指定され、有効な入力と無効な入力を区別します。効果的なファザーは、パーサーによって直接拒否されないという意味で「十分に有効」でありながら、プログラムのより深い部分で予期しない動作を引き起こし、適切に処理されていないコーナーケースを明らかにするほど「十分に無効」な、準有効な入力を生成します。
セキュリティの観点からは、信頼境界を越える入力が最も有用な場合が多い。[ 1 ]例えば、特権ユーザーのみがアクセスできる設定ファイルを解析するコードをファジングするよりも、任意のユーザーがアップロードしたファイルを処理するコードをファジングする方が重要である。
「ファズ」という用語は、ウィスコンシン大学のバートン・ミラー教授が担当した大学院の高度オペレーティングシステムクラス（CS736）の1988年の授業プロジェクト[ 2 ]に由来し、その結果は1990年に発表されました[ 3 ] [ 4 ]。このプロジェクトは、UNIXユーティリティのランダムな入力とコマンドラインパラメータを自動的に生成することを目的とした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月時点で23万8000台のマシンが依然として脆弱であると報告し、[ 12 ] 2017年1月時点では20万台であった。 [ 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 ]プログラマーは、ゴミ箱から取り出したパンチカードや乱数のカードデッキをコンピュータプログラムへの入力として使用していました。実行によって望ましくない動作が明らかになった場合、バグが検出されたことになります。
ランダム入力の実行は、ランダムテスト、モンキーテスト、モンテカルロデバッグ[ 23 ] （モンテカルロ法に類似）とも呼ばれます。
1981年、デュランとンタフォスは、ランダムな入力でプログラムをテストすることの有効性を正式に調査した。[ 24 ] [ 25 ]ランダムテストは、プログラムをテストする最悪の方法だと広く認識されていたが、著者らは、それがより体系的なテスト手法に代わる費用対効果の高い方法であることを示した。
1983年、AppleのSteve Cappsは、 MacPaintなどの従来のMac OSアプリケーションにランダムな入力を生成するツール「The Monkey」 [ 26 ]を開発しました。[ 27 ]比喩的な「猿」は、猿がタイプライターのキーボードをランダムに無限の時間叩き続けると、最終的にシェイクスピアの全作品を打ち出すという無限猿定理を指しています。テストの場合、猿はクラッシュを引き起こす特定の入力シーケンスを書き込むことになります。
1991年に、ランダムに選択されたパラメータでシステムコールをランダムに実行することにより、 UnixおよびUnixライクなオペレーティングシステムの堅牢性をテストすることを目的としたcrashmeツールがリリースされました。 [ 28 ]
ファザーはいくつかの方法で分類できます: [ 29 ] [ 1 ]
変異ベースのファザーは、ファジング中に既存のシード入力のコーパスを活用します。提供されたシードを変更（または変異）することで入力を生成します。 [ 30 ]例えば、画像ライブラリlibpngをファジングする場合、ユーザーは有効なPNG画像ファイルのセットをシードとして提供し、変異ベースのファザーはこれらのシードを変更して、各シードの半有効なバリアントを生成します。シードファイルのコーパスには、数千の類似した入力が含まれる可能性があります。自動シード選択（またはテストスイート削減）により、ユーザーはファジングキャンペーン中に発見されるバグの総数を最大化するために最適なシードを選択できます。[ 31 ]
生成ベースのファザーは、入力をゼロから生成します。たとえば、スマートな生成ベースのファザー[ 32 ]は、ユーザーから提供された入力モデルを使用して新しい入力を生成します。突然変異ベースのファザーとは異なり、生成ベースのファザーは、シード入力のコーパスの存在や品質に依存しません。
ファザーの中には、入力をゼロから生成する機能と、既存のシードの変異によって入力を生成する機能の両方を備えているものがある。[ 33 ]
一般的に、ファザーは、ファイル、キーボードやマウスのイベントのシーケンス、メッセージのシーケンスなど、構造化された入力を受け取るプログラムへの入力を生成するために使用されます。この構造により、プログラムが受け入れて処理する有効な入力と、プログラムがすぐに拒否する無効な入力が区別されます。有効な入力を構成するものは、入力モデルで明示的に指定できます。入力モデルの例としては、形式文法、ファイル形式、GUIモデル、ネットワークプロトコルなどがあります。データベースの内容、共有メモリ、環境変数、スレッドの正確なインターリーブなど、通常は入力とはみなされない項目でもファジングできます。効果的なファザーは、パーサーから直接拒否されない程度に「十分に有効」であり、かつ、特殊なケースをストレスで処理し、興味深いプログラムの動作を引き出す程度に「十分に無効」な、半有効な入力を生成します。
スマートな（モデルベース、[ 33 ]文法ベース、[ 32 ] [ 34 ]またはプロトコルベース[ 35 ]の）ファザーは、入力モデルを活用して、より多くの有効な入力を生成します。たとえば、入力が抽象構文木としてモデル化できる場合、スマートな突然変異ベースのファザー[ 34 ]は、ランダムな変換を使用して、完全なサブツリーをあるノードから別のノードに移動します。入力が形式文法でモデル化できる場合、スマートな生成ベースのファザー[ 32 ]は、生成規則をインスタンス化して、文法に関して有効な入力を生成します。ただし、一般的に、入力モデルは明示的に提供する必要がありますが、モデルが独自仕様、不明、または非常に複雑な場合は、これは困難です。有効な入力と無効な入力の大規模なコーパスが利用可能な場合は、Angluinの L* アルゴリズムなどの文法誘導技術を使用して入力モデルを生成できます。[ 36 ] [ 37 ]
ダムファザー[ 38 ] [ 39 ]は入力モデルを必要としないため、より幅広い種類のプログラムをファジングするために使用できます。たとえば、AFLは、ランダムなビットを反転したり、ランダムなバイトを「興味深い」値に置き換えたり、データブロックを移動または削除したりしてシードファイルを変更する、ダム変異ベースのファザーです。ただし、ダムファザーは有効な入力の割合が低く、プログラムの主要コンポーネントではなくパーサーコードに負荷をかける可能性があります。ダムファザーの欠点は、巡回冗長検査（CRC）の有効なチェックサムの構築によって説明できます。CRCは、入力ファイルに含まれるデータの整合性が送信中に維持されることを保証するエラー検出コードです。チェックサムは入力データに対して計算され、ファイルに記録されます。プログラムが受信したファイルを処理し、記録されたチェックサムが再計算されたチェックサムと一致しない場合、ファイルは無効として拒否されます。 CRC を認識していないファザーでは、正しいチェックサムを生成することはまず不可能です。しかし、単純な変異ベースのファザーが保護されたデータを変更した後、変異した入力から潜在的なチェックサムを特定して再計算しようとする試みがあります。[ 40 ]
一般的に、ファザーはコードカバレッジが高いほど効果的であると考えられています。その理由は、ファザーがプログラム内の特定の構造要素をテストしない場合、それらの要素に潜むバグも検出できないからです。プログラム要素の中には、他の要素よりも重要度が高いものがあります。例えば、除算演算子がゼロ除算エラーを引き起こしたり、システムコールがプログラムをクラッシュさせたりする可能性があります。
ブラックボックスファザー[ 38 ] [ 34 ]は、プログラムをブラックボックスとして扱い、プログラムの内部構造を認識しません。たとえば、ランダムに入力を生成するランダムテストツールは、ブラックボックスファザーとみなされます。したがって、ブラックボックスファザーは毎秒数百の入力を実行でき、簡単に並列化でき、任意のサイズのプログラムに拡張できます。ただし、ブラックボックスファザーは表面をなぞるだけで、「浅い」バグしか検出できない可能性があります。そのため、入力を与えてプログラムの出力を観察することで、ファジング中にプログラムの内部構造（および動作）について段階的に学習できるブラックボックスファザーを開発する試みがあります。たとえば、LearnLibは、Webアプリケーションの動作を表すオートマトンを生成するためにアクティブラーニングを採用しています。
ホワイトボックスファザー[ 39 ] [ 33 ]は、プログラム解析を利用してコードカバレッジを体系的に増加させたり、特定の重要なプログラム箇所に到達したりします。たとえば、SAGE [ 41 ]は、シンボリック実行を利用してプログラム内のさまざまなパスを体系的に探索します（コンコリック実行と呼ばれる手法）。プログラムの仕様が利用可能な場合、ホワイトボックスファザーはモデルベーステストの手法を利用して入力を生成し、プログラムの出力をプログラム仕様と照合する可能性があります。ホワイトボックスファザーは、プログラムの奥深くに隠れているバグを明らかにするのに非常に効果的です。ただし、解析（プログラムまたはその仕様）に要する時間が膨大になる可能性があります。ホワイトボックスファザーが入力を生成するのに比較的時間がかかりすぎる場合は、ブラックボックスファザーの方が効率的です。[ 42 ]したがって、ブラックボックスファザーの効率性とホワイトボックスファザーの有効性を組み合わせる試みがあります。[ 43 ]
グレーボックスファザーは、プログラム解析ではなく計測を利用してプログラムに関する情報を取得します。たとえば、AFLとlibFuzzerは、入力によって実行される基本的なブロック遷移をトレースするために軽量の計測を利用します。これにより、妥当なパフォーマンスオーバーヘッドが発生しますが、ファジング中にコードカバレッジが増加したことをファザーに知らせることができるため、グレーボックスファザーは非常に効率的な脆弱性検出ツールとなります。[ 44 ]
ファジングは、悪意を持って悪用される可能性のあるセキュリティ上重要なプログラムの脆弱性を明らかにするための自動化された手法として主に使用されます。[ 6 ] [ 16 ] [ 17 ]より一般的には、ファジングはバグの不在ではなく、バグの存在を示すために使用されます。数週間ファジングキャンペーンを実行してもバグが見つからない場合、プログラムが正しいことを証明することはできません。[ 45 ]結局のところ、プログラムはまだ実行されていない入力に対して失敗する可能性があり、すべての入力に対してプログラムを実行することは非常にコストがかかります。すべての入力に対してプログラムが正しいことを証明することが目的であれば、形式仕様が存在し、形式手法の技術を使用する必要があります。
バグを検出するには、ファザーは期待される（正常な）プログラム動作と予期しない（バグのある）プログラム動作を区別できなければなりません。しかし、機械は常にバグと機能を区別できるとは限りません。自動ソフトウェアテストでは、これはテストオラクル問題とも呼ばれます。[ 46 ] [ 47 ]
一般的に、ファザーは仕様がない場合でも、シンプルかつ客観的な尺度を用いて、クラッシュする入力とクラッシュしない入力を区別します。クラッシュは容易に特定でき、潜在的な脆弱性（サービス拒否攻撃や任意のコード実行など）を示す可能性があります。しかし、クラッシュしないからといって脆弱性がないとは限りません。例えば、 C言語で書かれたプログラムは、入力によってバッファオーバーフローが発生した場合、クラッシュする場合もあれば、しない場合もあります。むしろ、プログラムの動作は未定義です。
クラッシュ以外の障害に対してファザーの感度を高めるために、サニタイザーを使用して、障害が検出されたときにプログラムをクラッシュさせるアサーションを挿入することができます。[ 48 ] [ 49 ]バグの種類によって、サニタイザーは異なります。
参照実装が利用可能な場合、ファジングは「差分」バグの検出にも使用できます。自動回帰テストの場合、[ 50 ]生成された入力は同じプログラムの2 つのバージョンで実行されます。自動差分テストの場合、[ 51 ]生成された入力は同じプログラムの 2 つの実装で実行されます (たとえば、lighttpdとhttpd はどちらも Web サーバーの実装です)。2 つのバリアントが同じ入力に対して異なる出力を生成する場合、どちらか一方にバグがある可能性があり、より詳細に調査する必要があります。
静的プログラム解析は、プログラムを実際に実行せずに解析します。そのため、実際には存在しないプログラムの問題がツールによって報告されるという誤検出が発生する可能性があります。動的プログラム解析と組み合わせたファジングは、報告された問題を実際に再現する入力を生成するために使用できます。[ 52 ]
現代のウェブブラウザは、広範囲にわたるファジングを受けています。Google ChromeのChromiumコードは、Chrome セキュリティ チームによって 15,000 コアで継続的にファジングされています。[ 53 ] Microsoft Edge [Legacy]とInternet Explorerについては、Microsoft は製品開発中に 670 マシン年でファジング テストを実施し、10 億の HTML ファイルから 4,000億を超えるDOM操作を生成しました。[ 54 ] [ 53 ]
ファザーは、比較的短時間で大量の入力を生成します。たとえば、2016年にGoogle OSS-fuzzプロジェクトは週に約4兆個の入力を生成しました。 [ 17 ]そのため、多くのファザーは、障害を引き起こす入力の自動生成に続く、そうでなければ手作業で面倒なタスクを自動化するツールチェーンを提供します。
自動化されたバグトリアージは、多数の障害を引き起こす入力を根本原因ごとにグループ化し、個々のバグを深刻度に応じて優先順位付けするために使用されます。ファザーは多数の入力を生成し、障害を引き起こす入力の多くは、実質的に同じソフトウェアバグを露呈する可能性があります。これらのバグのうち、セキュリティ上重要なものはごく一部であり、より高い優先順位でパッチを適用する必要があります。たとえば、CERT コーディネーションセンターは、生成されたスタックトレースによってクラッシュする入力をグループ化し、各グループを悪用される可能性に応じてリストするLinux トリアージ ツールを提供しています。[ 55 ] Microsoft セキュリティ リサーチ センター (MSEC) は、クラッシュする入力のハッシュを作成して一意性を判断し、次に悪用可能性の評価を割り当てる「!exploitable」ツールを開発しました。 [ 56 ]
これまで報告されていなかった、トリアージされたバグは、バグ追跡システムに自動的に報告される可能性があります。たとえば、OSS-Fuzz は、セキュリティ上重要な複数のソフトウェア プロジェクトに対して大規模で長期間のファジング キャンペーンを実行し、これまで報告されていなかった個別のバグはそれぞれ直接バグ トラッカーに報告されます。[ 17 ] OSS-Fuzz バグ トラッカーは、脆弱なソフトウェアの保守担当者に自動的に通知し、アップロードされた最小限の障害誘発入力を使用して、最新のリビジョンでバグが修正されているかどうかを定期的にチェックします。
自動入力最小化（またはテストケース削減）は、障害を引き起こす入力のうち、実際に障害を引き起こしている部分を分離するための自動デバッグ手法です。 [ 57 ] [ 58 ]障害を引き起こす入力が大きく、ほとんどが不正な形式である場合、開発者がバグの原因を正確に理解することは難しい場合があります。障害を引き起こす入力が与えられた場合、自動最小化ツールは、元のバグを再現しながら、可能な限り多くの入力バイトを削除します。たとえば、デルタデバッグは、拡張バイナリサーチアルゴリズムを使用してそのような最小入力を見つける自動入力最小化手法です。 [ 59 ]
以下は、学術文献で「人気がある」、「広く使われている」などと説明されているファザーのリストです。[ 60 ] [ 61 ]