バイナリ網羅率の誤ったアプローチ

正しい方法 恐竜時代、プログラムを書いてその正しさをテストしたい場合、主に2つの選択肢がありました。不正な入力を手動で構築して試すか、ランダムな入力を生成して自動的に試すプログラムを接続するかです。これらのプログラムはファザー、あるいはジェネレーターと呼ばれ、これは「ファズテスト」でした。 また、かなりの間、それはあまり良くありませんでした。ジェネレーターは、プログラムがクラッシュしたかどうかというフィードバックしか得られませんでした。このフィードバックは有用ですが、ファザーは前のランダムな入力と比較して進歩しているのか、あるいは良い仕事をしているのかを判断できません。そのため、ファザーは同じ浅いコードを繰り返しヒットするだけでした。1週間実行しておいてから戻ってくると、プログラムの興味深い部分に到達する入力を生成しておらず、すべてすぐに破棄されるか、if(packet_header == 0xdeadbeef) チェックを通過できないことが判明するでしょう。 American Fuzzy Lopは、カバレッジ誘導型ファジングを導入することで、この分野に革命をもたらしました。ファザーへの唯一のフィードバックが入力がクラッシュしたかどうかである代わりに、プログラム実行中にヒットしたコードカバレッジを記録しました。入力が以前に到達したことのないプログラムの部分を実行した場合、それは新しいコードにヒットし、おそらくプログラムのバグが含まれている可能性のある新しい興味深い表面領域をテストできるようになったということです。これは、過去の「ダムファジング」よりもはるかに効果的でした。 AFLは、テスト対象プログラムをカスタムclangコンパイラパスでコンパイルすることでカバレッジを収集します。これはCFGエッジにカバレッジフィードバックを追加します。新しい基本ブロックにヒットした場合、新しいカバレッジビットマップエントリが得られます。入力でプログラムを実行した結果、以前よりも新しいビットが設定されたビットマップが得られた場合、それは新しいコードにヒットしたことを意味します。その入力は、将来の実行のためにシード入力として保存できます。 ソースコードがないブラックボックスバイナリに対しても、フィードバックベースのファジングを行うことができます。例えば、AFL++にはqemu_modeバックエンドがあります。これは、テスト対象プログラムをqemu-userで実行します。qemu-userはx86アセンブリをQEMUのTCG IRにリフトし、JITコンパイラでx86にダウンリフトしますが、これはタイプ2ハイパーバイザー環境で安全に実行できます。AFL++にはQEMUのフォークがあり、カスタムTCGフックを追加して、ミドルエンドのブロックにカバレッジインストルメンテーションを追加します。各ブロックのIRは、AFLがLLVMの追加操作でclang IRを強化するのと同じ方法で、カバレッジビットマップエントリを書き込むTCG操作で拡張されます。 これらは多くの作業のように聞こえますが、このqemu_modeはネイティブでプログラムを実行するよりも約3〜5倍遅いだけです。 ブラックボックスバイナリのカバレッジのゴールドスタンダードは、ハードウェアにそれを任せることです。 テスト対象プログラムに追加の操作を挿入する必要がなく、ファズテストケースを実行するときにそれらを実行する必要がある代わりに、Intel PTを使用できます。 特定のパフォーマンスカウンター構成レジスタを有効にすると、プロセッサトレースが開始されます。CPUは実行パイプラインの一部としてメタデータを自動的に記録し、ファザーはその結果のメタデータを調べて、実行した基本ブロックのトレースを抽出できます。 これは不当に効果的であり、Intel PTベースのトレースは通常のネイティブ実行よりも約10％遅いだけです。 もちろん、問題は、私のような人がラップトップにIntelではなくAMDプロセッサを搭載していることです。AMDには、実行されているコードを記録するブランチトレースバッファなど、独自の魔法のパフォーマンスカウント機能がありますが、1）ドキュメントがはるかに少なく、2）Intel PTよりも遅く、3）正確な方法で使用することは不可能です。つまり、カウンターはサンプリングベースであり、イベントの1/nしか提供しないか、メタデータバッファがいっぱいになる前にドレインできない場合にイベントをドロップする可能性があります。 どちらの場合も、ファジングには残念ながら適していません（厳密には、確率的なカバレッジのみに基づいてファザーを構築することは可能であり、それほど悪くないかもしれません。しかし実際には誰もそうしておらず、おそらくそれだけの価値はありません）。 これが私の悪いアイデアにつながります。 サイドプロジェクトのために独自のファザーを書きたいと思っており、正確なブラックボックスバイナリカバレッジを収集したいと思っていました。しかし、独自の動的再コンパイルエンジン（再び）を書き直したり、新しいラップトップを購入したりしたくありませんでした。ソフトウェアエンジニアはどうすればよいでしょうか？ 間違った方法 代わりに、すべての分岐をINT3命令に置き換えることで、ゲストコードをインストルメント化できます。待ってください、説明させてください。 正確なカバレッジを収集するには、プログラムが分岐にヒットするたびに何かを実行する必要があります。 各ブロックに新しい動作を挿入することはできません。なぜなら、ブロックはその通常の命令のためにすでにブロックのすべてのバイトを使用しているからです。ブロックのサイズを変更しようとすると、コードポインタの修正が必要になり、結局QEMU-but-badに戻ってしまいます。 分岐命令の最小長は2バイトです。Jccには、単一のオペコードバイトと分岐用の変位という形式があります。 INT3は1命令長で、GPRを上書きせずに制御フローをハイジャックするため、命令後の実行を継続できます。そして、上書きした分岐の位置をコンテキストとして提供するため、記録したいカバレッジビットマップエントリを計算できます。 それは完璧です！ 残念ながら、Linuxでptraceを使用しようとすると、死にたくなるでしょう。 LinuxはINT3をSIGTRAPに変換します。 これは、プロセスを監視しているptraceベースのデバッガによってキャッチできます。そのシグナルには、トレーシーのPCとレジスタ状態が含まれており、カバレッジフックを実装するために使用できます。その後、PTRACE_CONTを使用してプロセスを続行できます。 ただし、このダンス全体は複数のコンテキストスイッチになります。ゲストプログラム（リング3）-> x86割り込みハンドラ（リング0）へのINT3トラップ-> Linuxカーネルがデバッガ（リング3）にptraceイベントを配信->デバッガがsyscall経由で（リング0）にPTRACE_CONT -> Linuxカーネルのsyscall実装がゲスト（リング3）を再開します。 これらの各コンテキストスイッチは非常にコストがかかります。特に、特権レベル間のコンテキストスイッチは、同じリング内コンテキストスイッチよりもプロセッサにとってさらに多くの作業を必要とするためです。 ああ、別の方法があればいいのに！ 答えは、もちろん、仮想化拡張機能です。 あなたのコンピュータは、Intel VT-x（Linuxではkvmと呼びます）の魔法の力によって、その中に小さなコンピュータを実行できます。 小さなコンピュータ内のコードは、完全にベアメタルで実行されているかのように動作します。ゲストコードは、通常のカーネルのように割り込みハンドラ、MSR、ページングを自由に構成でき、ゲストカーネルの下でユーザー空間コードを実行することさえできます。 実際には、ゲストカーネルは通常のLinuxカーネルによってホストされている仮想マシンで実行されており、ゲストカーネルが実際のワールドにI/Oを行おうとしたときに、ホストカーネルにトラップされ、ユーザー空間イベントに変換され、「仮想マシンマネージャー」がそれを実装し、結果で仮想マシンを再開できるように構成できます。 重要なのは、仮想マシンが実行されている間、それはベアメタルで実行されているということです。プロセッサは実際にゲストVMのすべての命令を実行しており、それらはすべて汎用レジスタやハードウェアページテーブルなどの通常のプロセッサ状態を使用しますが、物理メモリに対してハイパーバイザー翻訳を実行して、VMの境界外に到達できないようにする追加のビットがいくつかあります。 重要なのは、VMがほぼ100％ネイティブ速度で実行されるということです。ただし、ゲストカーネルがハイパーバイザーにトラップされる何かを実行しようとしてVMExitしてホストカーネルに戻る必要がある場合を除きます。 実際、これは非常にうまく機能するため、インターネットのほぼ全体が、Firecrackerのようなクラウドベースのハイパーバイザーの形でkvmの上に実行されています。 TinyKVMは、Varnish4の作者による優れたプロジェクトです。 これはC++ライブラリとしてVMMを実装しており、これを使用してアービトラを実行できます。