ファジング

ファジング（）とは、コンピュータプログラムヘの入力として、無効なデータ、予期しないデータ、ランダムなデータを用いた自動化ないし半自動化されたソフトウェアテストの手法である。コンピュータプログラムにファズ（「予測不可能な入力データ」の意、）を与えることで、意図的に例外的な状況を発生させ、その例外的な状況での挙動を確認するという方法を用いる。ファズテスト（fuzz testing）とも呼ばれる。また、ファジングの対象プログラムに対してファズテストを実行するツールは、ファザー（fuzzer）と呼ばれる。
概要.
ファジングは、コンピュータプログラムの検証プロセスの一環として、構造化された入力を受け取るプログラムをテストするために使用される。この構造化された入力とは、たとえばファイル形式やプロトコルで指定された有効な入力、あるいは無効な入力を指す。ファザーは、（パーサーによって拒否されないという意味で）プログラムに対して有効な入力データを生成する。ファザーが生成する入力データ等を使用することで、通常のプログラムの操作や他のテスト方法では達成できない例外的な状況を発生させる可能性がある。
ファジングによって作り出された例外的な状況により、意図せぬクラッシュ(コンピュータ)、適切に処理されていないコーナーケースの発見、組み込みコードアサーションの失敗、潜在的なメモリリーク、実行時エラーの発見・分析などが可能となる。
ファジングの重要な要素として「自動化」が挙げられる。ソフトウェアテストは、従来、テスト実施者の経験と勘に頼って手作業で行われてきた。これに対して、ファジングは、テストケースの自動生成・実行と、自動化に伴う再現性の高さとコードカバレッジの広さで優れており、テスト実施者の経験と勘に依存しないソフトウェアテストとして発展してきた。ただし、ファジングにおいても依然としてテスト実施者の経験と勘に依存する要素はある。入力データの決定方法では半自動化を選択する場合もあるほか、ファイル形式のファジングなどの分野では手動ファジングが効果的な場合もある。
ファジングが有効な例としては、信頼境界線を越えた入力が挙げられる。一例として、ファジングを用いたコードの検証を行う際は、管理者権限ユーザーのみがアクセスできる構成ファイルを解析するコードよりも、任意のユーザーによるファイルのアップロードを処理するコードのほうが、有効な結果を得られる可能性が高い。
ファジングはソフトウェアまたはコンピュータシステムの不具合、特に脆弱性を発見するために一般的に使用され、ソフトウェアの未知の脆弱性と堅牢性の課題を明らかにするうえで最も重要な手法の一つである。
品質保証の分野でもファジングと同様の手法が使用されており、堅牢性テスト、構文テスト、または否定テストと呼ばれている。
ファジングの歴史.
ファジングの前史.
「ファジング」という用語が登場し、手順が確立される以前から、ランダムな入力の実行を用いたテスト手法が存在していた。たとえば、ジェラルド・ワインバーグは、コンピュータプログラムヘの入力として、ゴミ箱から引き出されたパンチカードや乱数のカードを使用し、それらの実行によって望ましくない動作を引き出し、バグの検出に用いていた。
1981年、DuranとNtafosは、ランダムな入力を使用してプログラムをテストすることの有効性を正式に調査した研究論文を発表している。それまでランダムな入力によるテストは、プログラムをテストするための「最悪の手段」であると広く認識されていたが、DuranとNtafosは、ランダムな入力によるテストが費用効果の高い代替手段であることを示した。
1983年、AppleのSteve Cappsは、Mac Paintなどの従来のMacOSアプリケーション用にランダムな入力を生成するツールTheMonkeyを開発した。名称の由来にあるMonkey（日本語：「猿」）は、「無限の猿定理」で提示された「猿がタイプライターのキーボードでランダムにキーを無限に押せば最終的にシェイクスピア全集をタイプアウトする」という思考実験に由来する。
1991年、ランダムなプロセッサ命令のセットを実行することにより、UnixおよびUnixライクなオペレーティングシステムでプログラムの信頼性・堅牢性をテストするように設計されたアプリケーションcrashmeが公開された。
これらのテスト手法は、ランダムテストまたはモンキーテストとも呼ばれてきた。
用語「ファジング」の登場.
原始的なファジングツールは、ウィスコンシン大学マディソン校のオペレーションシステムに関する講義において、教授バートン・ミラー（英語：Barton Miller）と、ミラーが指導する大学院生Lars FredriksenおよびBryan Soによって1988年に開発され、1990年に研究論文として公開された。
これは、UNIXアプリケーションの脆弱性テストに作成したコマンドラインプログラムである。ランダムな入力およびコマンドラインパラメータを自動的に生成することを目的として、エラーで停止するまで他のプログラムにパラメータとして渡されるランダムデータを生成した。ランダムな非構造化データを使用した初めてのテストであるだけでなく、さまざまなオペレーティングシステムのさまざまなプログラムをテストし、テスト中に発生するエラーの種類を体系的に分析するための最初の専用アプリケーションでもあった。
このプロジェクトは、「オペレーティングシステムユーティリティ信頼性プログラム――ファジングジェネレータ」と名付けられた。このファジングという語は、英語の単語fuzzy（ファジー、ぼやけの意味）に由来する。
ミラーらのプロジェクトは、テストしたUNIXユーティリティの25～33％をクラッシュさせることに成功した。また、各クラッシュをデバッグして原因を特定し、検出された各障害を分類した。加えて、他の研究者が他のソフトウェアでも同様の検証実験を行えるようにするために、ツールのソースコード、テスト手順、及び生の結果データが公開された。なお、1990年の研究論文では、ファジングの信頼性とセキュリティの関係性についても言及されている。
この時点ではまだ用いられているテスト内容は、たんに「クラッシュするか否か」「ハングするか否か」といったレベルのものであり、ファジングという用語も概念も登場する前のことであったが、これらのことを行なったバートン・ミラーは「ファジングの父」と呼ばれている。
ファザーを用いたテストは、1995年に再度実験が行われた。アプリケーションは、MacOSおよびWindows用のGUIアプリケーション、ネットワークプロトコル、およびシステムライブラリAPIテストを含むように拡張された。このときには様々なUNIXアプリケーションに対して脆弱性が発見されている。
ファジンツールの多様化.
体系的なファジングツールは、オウル大学でのPROTOSプロジェクトによって開発された。PROTOSの開発は1999年に始まり、2002年には同プロジェクトのメンバーによって商用ファズツールの設計開発会社Codenom1iconが設立され、2005年には商用ファズツールがリリースされている。なお、PROTOSはオープンソースであるが2004年以降開発されていない。2005年にはファジング専門のメーリングリストが作成されるなど、セキュリティ研究家の中でも取り上げられる存在となった。
2002年、によって作成されたオープンソースのファズツールフレームワークSPIKEおよびそれを使ったファズツールsharefuzzなどが登場した。これ以降、Webブラウザを対象としたファジング（mangleme, CSSDIEなど）、ファイル形式を対象としたフジァング（FileFuzz、SPIIKIEfileなど）、ハードウェアファジング機器（Mu Security）、ActiveXを対象としたファジング（AxMan）など，特定分野における様々なファズツールが作られることとなった。
2012年4月、Goog1leは、Chromium Webブラウザのセキュリティが重要なコンポーネント用のクラウドベースのファジングインフラストラクチャであるClusterFuzzを発表した。セキュリティ研究者は、ClusterFuzzがアップロードされたファザーでクラッシュを検出した場合、独自のファザーをアップロードしてバグバウンティを収集できる。
2014年9月には、2014年シェルショック脆弱性の類似する脆弱性として開示されたセキュリティバグ広く使用でUNIXのbashシェル。Shellshockのほとんどの脆弱性は、後述するファジングツールAFLを使用して発見された。発見された脆弱性によりは、一部のWebサーバー展開など、多くのインターネット向けサービスはBashを使用して特定の要求を処理し、攻撃者が脆弱なバージョンのBashに任意のコマンドを実行させることを可能することで、攻撃者はコンピューター・システムヘの不正アクセスを取得することができた。
2015年4月、Hanno Bockは、AFLが2014年のHeartbleedの脆弱性の発見手法を報告している。Heartbleedの脆弱性は2014年4月に公開された。これは、攻撃者が暗号化された通信を解読できる深刻な脆弱性であった。この脆弱性は、TLSを実装するOpenSSLに誤って導入され、インターネット上のサーバーの大部分で使用されていた。Shodanは2016年4月に238,000台、2017年1月に200,000台のマシンがまだ脆弱であると報告されている。
2016年8月、米国国防高等研究計画局（DARPA）は、キャプチャー・ザ・フラッグコンテストとしてサイバーグランドチャレンジを開催した。これは、ソフトウェアの欠陥をリアルタイムで発見悪用、修正できる自動防御システムを開発することを目的としたイベントであった。ファジングは、対戦相手のソフトウェアの欠陥を発見するための効果的な攻撃戦略として使用され、脆性弱検出の自動化に大きな可能性が示された。なお、優勝はデイビット・ブラムリーが率いるチームFor All Secureによって開発されたシステム「メイヘム」であった。
2016年9月、マイクロソフトは、ソフトウェアのセキュリティ上の重大なバグを検出するためのクラウドベースのファジングテストサービスであるProject Springfieldを発表した。2016年12月、GoogleはOSS-Fuzzを発表した。これにより、セキュリティが重要ないくつかのオープンソースプロジェクトを継続的にファジングできる。セキュリテイカンファレンスBlackHat2018で、Christopher Domasは、ファジングを使用してプロセッサ内の隠れたRISCコアの発見手法を提案した。このコアは、既存のセキュリティチェックをバイパスして、リング3からリング0コマンドを実行することができた。
2020年9月、MicrosoftによってOne Fuzzがリリースされた。これは、ソフトウェアのバグの検出を自動化し、自己ホスト型のサービスとしてのファジングプラットフォームであり、WindowsとLinuxをサポートしている。
ファジングの用途と限界.
ファジングは主に、悪意を持って悪用される可能性のあるセキュリティクリテイカルなプログラムの脆弱性を明らかにするための自動化された手法として使用される。より一般的には、ファジングは、バグが存在しないことではなく、存在することを示すために使用される。バグを見つけずにファジングキャンペーンを数週間実行しても、プログラムが正しいことは証明とはならなく、プログラムはまだ実行されていない入力に対して失敗する可能性がある。すべての入力に対してプログラムを実行することは非常にコストがかかるが、プログラムがすべての入力に対して正しいことを証明することが目的である場合は、形式仕様が存在し、形式手法の手法を使用する必要がある。
以下、ファジングが特に効果を発揮している用途を挙げて解説する。
バグの発見.
バグの発見のために、ファザーは予期された（通常の）プログラムの動作と予期しない（バグのある）プログラムの動作を区別できなければならない。ただし、マシンは常にバグと機能を区別できるとは限らない。自動ソフトウェアテストでは、これはテストオラクル問題とも呼ばる。
通常、ファザーは、仕様がない場合にクラッシュする入力とクラッシュしない入力を区別し、単純で客観的な手段を使用する。クラッシュは簡単に特定でき、潜在的な脆弱性（サービス拒否や任意のコード実行など）を示している可能性がある。ただし、クラッシュがないからといって、脆弱性がないことを示すものではない。たとえばCで記述されたプログラムは、入力によってバッファオーバーフローが発生した場合にクラッシュする場合とクラッシュしない場合がある。むしろ、プログラムの動作は未定義であることが多い。クラッシュ以外の障害に対してファザーをより敏感にするために、サニタイザーを使用して、障害が検出されたときにプログラムをクラッシュさせるアサーションを挿入できる。さまざまな種類のバグに対して、さまざまな解消方法がある。バッファオーバーフローやメモリ解放後の再使用(Address Sanitizerなどのメモリデバッガを使用）などのメモリ関連のエラーを検出するには、競合状態とデッドロックを検出するため(Thread Sanitizer)、未定義の動作を検出するには(Undefined Behavior Sanitizer)、メモリリークを検出する(Leak Sanitizer)、またはコントロールフローの整合性をチェックするCFISanitizer)。リファレンス実装が利用可能な場合、ファジングを使用して「差分」バグを検出することも可能である。自動回帰テストの場合、生成された入力は、同じプログラムの2つのバージョンで実行される。自動差分テストの場合、生成された入力は、同じプログラムの2つの実装で実行される。たとえばlighttpdとhttpdは両方ともWebサーバー上に実装される。2つのバリアントが同じ入力に対して異なる出力を生成する場合、1つはバグがある可能性があるため、より詳細に調べる必要がある。
静的解析.
静的解析は、プログラムを実際に実行せずに分析する。これにより、ツールが実際には存在しないプログラムの問題を報告する誤検知が発生する可能性がある。動的プログラム分析と組み合わせたファジングを使用して、報告された問題を実際に確認できる入力を生成しようとすることができる。
テストケースの削減.
テストケースの削減は、より多くのテストケースのセットから多数のテストケースを選択するプロセスである。テストケースの削減は手動またはソフトウェアツールを使用して行うことができ、プログラムの適用範囲に不可欠なテストケースのみが残るまで、テストの一部を1つずつ削除する分割統治法が行われる。ファジングソフトウェアは、ソフトウェアに適用する前に、生成したデータ入力を記録することが多い。実行中にコンピューターにエラーが発生した場合、テストは保持される。生成されたデータストリームが疑似ランダムである場合、ファジングの試みを再現するためにシード値を保存できる。バグが検出された場合、デバッグに使用できるテストケースの作成に役立つ。
一例として、プログラムシリアライザーが同じプログラムパーサーが拒否するものを発行するたびにメッセージを生成することにより、誤ったシリアル化フォームに関連するバグを検出できる。この手法では、プログラムの2つのバージョン間、または同じ仕様の2つの実装間で意図しない違いを見つけることも可能となる。
メモリリークの検出.
ファジングは、メモリデバッガと組み合わせた場合バグやメモリリークを検出するためにも使用することができる。大規模なアプリケーションでは、メモリ使用量の安全性に影響を与えるバグがプログラムの実行中にエラーを生成する可能性があるため、ファジングが有効な場面の一つである。
Webブラウザのセキュリティ診断.
最新のWebブラウザは、広範囲にわたってファジングが実行されている。Google ChromeのChromiumコードは、15,000コアのChromeセキュリティチームによって継続的にファジングされている。Microsoftが行った検証では、Microsoft EdgeおよびInternet Explorerに10億個のHTMLファイルから複数4000億DOM操作を生成してテストが実施された。
限界.
ファジングはセキュリティにおける万能薬ではない。以下のようなものはファジングでは問題を見つけることができない。
また、テスト終了条件、つまりどれだけの入力データを投入すれば充分にテストされたといえるかといった点や、コード網羅率を現状よりも高めるにはどのような入力値を与えればよいのかといった点が判断しづらいという問題もある。
ファジングの種類.
ファジングは、自動化あるいは半自動化されたブラックボックステストないしはグレーボックステストに分類される。ブラックボックステストとして使うこともあるが、リバースエンジニアリングによってどのような機能を持っているか（ネットワークアプリケーションであれば、どのライブラリのどのAPIを呼び出しているか、など）を特定することで入力機能に関する情報が得られるため、このようにして得られた情報を付随してグレーボックステストとして行なわれることもある。
ファジングは、ブラックボックスファジング、グレーボックスファジング、ホワイトボックスファジングの３種に類別することが可能である。Fuzzing-survey.orgでは、既存のブラックボックス、グレーボックス、ホワイトボックスのファザーをそれぞれの系統樹形式で閲覧することができる。
ファジングにおけるツールチェーンの特徴.
ファジングは、比較的短時間で多数の入力を生成して解析に使用する。たとえば、2016年に発表されたGoogleのOSS-fuzzプロジェクトでは、1週間に約4兆件の入力データが生成された。このように多くのファザーは、障害を誘発する入力の自動生成に続く手動で面倒なタスクを自動化するツールチェーンとともに使用される。
自動バグトリアージ.
自動バグトリアージは、多数の障害を誘発する入力を根本原因ごとにグループ化し、個々のバグに重大度ごとに優先順位を付けるために使用される。ファザーは多数の入力を生成し、障害を引き起こすものの多くは同じソフトウェアのバグを効果的に公開する可能性がある。これらのバグの一部のみがセキュリティ上重要であり、より高い優先度でパッチを適用する必要がある。たとえば、CERT Coordination Centerは、生成されたスタックトレースによってクラッシュする入力をグループ化し、悪用される可能性に応じて各グループを一覧表示するLinuxトリアージツールを提供している。Microsoft Security Research Center(MSEC)は、クラッシュする入力のハッシュを最初に作成してその一意性を判断し、次のように悪用可能性の評価を割り当てるツールを開発した。
以前は報告されていなかったトリーアジされたバグが、バグ追跡システムに自動的に報告される場合がある。たとえば、OSS-Fuzzは、セキュリティが必要ないくつかのソフトウェアプロェジクトに対して、大規模で長期にわたるファジングキャンペーンを実行している。このキャンペーンでは、これまで報告されていなかった個別のバグがバグトラッカーに直接報告された。OSS-Fuzzバグトラッカーは、脆弱なソフトウェアをメンテナに自動的に通知し、アップロードされた最小化された障害誘発入力を使用して、バグが最新のリビジョンで修正されたかどうかを定期的にチェックする機能を有する。
自動入力最小化.
自動入力最小化（テストケース削減）は、実際に障害を引き起こしている障害を引き起こす入力の部分を分離するための自動デバッグ手法である。失敗を誘発する入力が大きく、ほとんどが不正な形式である場合、開発者がバグの原因を正確に理解するのは難しい。障害を引き起こす入力を考えると、自動化された最小化ツールは、元のバグを再現しながら、可能な限り多くの入力バイトを削除することができる。たとえば、Delta Debuggingは、拡張されたバイナリ検索アルゴリズムを使用してそのような最小入力を見つける自動入力最小化手法である。
ファズデータの生成方法.
ファズツールは、ファズデータの生成方法によって以下の様に大きく分類される。
ファジングの実施フェーズ.
ファジングにおいては、一般的に以下のフェーズを適用する。
ファジングを用いる対象の例.
ファジングの最も一般的な対象は、ファイル形式とネットワークプロトコルであるが、任意のプログラム入力をテスト対象として使用できる。入力には、環境変数、キーボードとマウスのイベント、およびAPI呼び出しシーケンスが挙げられる。手法によっては、データベースの内容、共有メモリ、スレッド間のコンテキストスワップなど、通常は「入力」とは見なされないアイテムもファジングの対象とすることが可能である。
以下、ファジングを用いる代表的な対象を挙げる。
現在使用されている主なファジングツール.
ファジングの実施に際しては、ファジングの対象にあわせて設計されたツールが必要になることが多いが、いわゆるオープンソースフレームワークが用いられるほか、商用ソフトウェアを用いてテストされることもある。
標準化されたインターフェイスを持つもの、またはプロトコルでアドレス指定できるものは基本的にファジングツールでテストすることができる。一例としてWebアプリケーションは多くの場合、バックグラウンドのプロセスは、常に同じであるため、HTTP/HTMLなどの共通のインターフェイスをもつため、ファジングツールでテストすることができる。
また、用途に応じたファジングツールとして、ブラウザやソフトウェアをファジングするための優れたツールが登場している。ファジングツールを使用することで、Webブラウザとして以前に生成された無効なデータ文字列、ファイルおよび異常なプログラム動作（クラッシュ、サービス拒否、サービスの低下）を制御するために、必要に応じてログを記録して後で評価を行う、といった検査が可能となる。
商用ソフトウェア.
商用ファジングツールには次のものがある。
CodenomiconのDefensicsは、事前定義されたいわゆる「テストケース」で機能する。一方、BeyondSecurityのファザーhoSTORMは、テストケースではなく、n×n個の異常でログ内のすべてのフィールドにサービスを提供する。
「インテリジェント・ファズ」または「ステートフル・ファズ」を標榜したファザーが商用環境で開発されており、事前にテストするシステムの相互運用性をチェックしてから、ファジングテストセット（異常化されたデータパケット）をターゲットシステムに送信する機能が標準的に備わっている。
オープンソースフレームワーク.
よく知られているオープンソースフレームワークとしては、Peach FuzzerやSullyが挙げられる。これらのフレームワークは非常に複雑であり、利用にあたってはファジングとプロトコルに関する広範な知識が必要である。また、既存のテストツールまたは既存のテストプロセスを統合するため、Fuzzinoなどのテスト環境プラットフォームも公開されている。
アメリカンファジーロップ(American Fuzzy Lop, AFL).
オープンソースソフトウェアの分野では、Michat Zalewskiによるファジングツール「アメリカンファジーロップ」（American Fuzzy Lop、名前はウサギの品種に由来する。略してAFL）が2014年から普及している。
AFLは、ファザーafl-fuzzに加えて、他の補助プログラムが利用可能であり、テストケースの最小化とテストコーパスの最小化に有効である。テスト対象のプログラム（テスト項目）のソースコードをインストルメント化することにより、afl-fuzzは、ソフトウェアのどのブロックが特定のテスト刺激で実行されたかを後で確認できる。そのため、AFLはグレーボックステストに使用することができる。遺伝的手法による検査データの生成に関連して、ファザーはテストデータをより適切に生成できるため、このメソッドを使用しない他のファザーよりも、処理中に以前は使用されていなかったコードブロックが実行される。その結果、コードカバレッジは比較的短い時間で比較的高い結果が得られる。この方法は、生成されたデータ内の構造を独立して（つまり、事前の情報なしで）生成することができる。このプロパティは、テストカバレッジの高いテストコーパス（テストケースのコレクション）を生成するためにも使用される。
afl-fuzzの利点は、自動操作（最小限のシンプルな構成）、複数のコアまたは複数のコンピューターとの並列化が可能であり、高性能であると言える。データのフィードにはファイルインターフェイスがサポートされているが、ネットワークインターフェイスはサポートされていない。DUTは、ランタイム拡張機能Address Sanitizerを使用してコンパイルされた場合、特に敏感に反応する。この拡張機能は、コンパイラdangまたはclang++およびgccまたはg++で使用可能であり、メモリアクセスの監視に用いることができる。ソーステキストが利用できない場合、afl-fuzzはQEMUの助けを借りてテスト項目をインストルメント化できる。なお、インストルメント化は動的に実行する必要があるため、テスト項目の処理速度は静的にコンパイルされたインストルメント化よりも遅くなる。
Cluster Fuzz.
Cluster Fuzzは、Googleによって公開されたスケーラブルなファジング・インフラストラクチャである。2019年2月に公開した。Cluster Fuzzは、Google Chromeブラウザのバグを見つけ、パッチが成功したことを確認するために開発された。2012年から2019年2月に開発が開始されて以来、Google Chromeでは16,000のバグが発見され、OSS Fuzzに統合された160を超えるプロジェクトでは11,000のエラーが発見された。
fuzzuf.
ファジングによる脆弱性検出に関心のある研究者・開発者に向けの日本国産ファジングフレームワーク。多種多様なファジングアルゴリズムを統合されたインターフェイスから扱うことのできるフレームワークで、既存のファジングアルゴリズムをブロックのように組み替えて新たなアルゴリズムを作り出すことを可能にするドメイン固有言語「HierarFlow」を備えている。ファジングアルゴリズムの実装コストを低下させ、再利用性を向上させる機能を含む。