バイナリ網羅率の誤ったアプローチ
Binary Coverage the Wrong Way (redvice.org)
要約
この記事は、ソフトウェアテストにおける網羅率(カバレッジ)の計測方法について、特にバイナリコードに対するアプローチを論じています。従来の「ダムファジング」からAFLのようなカバレッジ誘導型ファジングへの進化を説明し、ハードウェア(Intel PT)や仮想化(KVM)を用いた高度な手法を紹介する一方で、筆者自身の「間違ったアプローチ」として、INT3命令を用いた低速で複雑なカバレッジ計測方法を試みた経緯を述べています。
全文翻訳
Binary Coverage the Wrong Way
正しいアプローチ
昔々、恐竜の時代、プログラムが正しいかどうかをテストしたい場合、主に2つの選択肢がありました。手動で不正な入力を構築して試すか、ランダムに入力を生成して自動的に試すプログラムを接続するかでした[1]。これらのプログラムはファザー(fuzzer)またはジェネレーター(generator)と呼ばれ、これが「ファズテスト(fuzz testing)」でした。しかし、これは長い間あまり良いものではありませんでした。ジェネレーターは、プログラムがクラッシュしたかどうかというフィードバックしか得られなかったのです。このフィードバックは有用ですが、ファザーが前回のランダムな入力と比較して進歩しているのか、あるいは良い仕事をしているのかを判断することはできませんでした。そのため、ファザーは同じような浅いコードを繰り返し実行するだけでした。1週間実行しても、プログラムの興味深い部分に到達する入力を生成しておらず、それらはすべてすぐに破棄されるか、if(packet_header == 0xdeadbeef) のチェックを通過することすらできませんでした。
American Fuzzy Lop は、カバレッジ誘導型ファジングを導入することで、この分野に革命をもたらしました。ファザーへのフィードバックがクラッシュしたかどうかだけではなく、プログラム実行中にコードカバレッジがどのようにヒットしたかを記録するようになりました。もし入力が以前に到達したことのないプログラムの部分を実行した場合、それは新しいコードをヒットしたことになり、おそらくプログラムの新しい興味深い表面領域をテストできる可能性があり、そこにバグが存在するかもしれません。これは、昔の「ダムファジング(dumb fuzzing)」よりもはるかに効果的でした。
AFLは、テスト対象のプログラムをカスタムclangコンパイラパスでコンパイルすることによりカバレッジを収集します。このパスは、CFGエッジにカバレッジフィードバックを追加します。コード内の新しい基本ブロックに到達すると、新しいカバレッジビットマップエントリが設定されます[2]。入力でプログラムを実行した結果、以前よりも新しいビットが設定されたビットマップが得られた場合、それは新しいコードをヒットしたことになります。その入力は、将来の実行のためにミューテーションのシード入力として保存できます。
ソースコードがないブラックボックスバイナリに対しても、フィードバックベースのファジングを行うことができます。AFL++ には、例えば qemu_mode バックエンドがあります。これは、qemu-user を使用してテスト対象のプログラムを実行します。qemu-user は、x86アセンブリをQEMUのTCG IRにリフトし、JITコンパイラでTCG IRをx86にダウンリフトしますが、これはタイプ2ハイパーバイザー環境下で安全に実行できます。AFL++にはQEMUのフォークがあり、カスタムTCGフックを追加して、ミドルエンドのブロックにカバレッジインストルメンテーションを追加します。各ブロックのIRは、AFLがclang IRにLLVM操作を追加するのと同じ方法で、カバレッジビットマップエントリを書き込むTCG操作で拡張されます。多くの作業のように聞こえますが、この qemu_mode はネイティブでプログラムを実行するよりも約3〜5倍遅いだけです。
ブラックボックスバイナリのカバレッジにおけるゴールドスタンダードは、ハードウェアにそれを任せることです。テスト対象のプログラムに、ファズテストケースを実行するときに追加で実行する必要のある追加操作を挿入する必要はありません。代わりに、Intel PT を使用できます。特定のパフォーマンスカウンタ設定レジスタを有効にすると、プロセッサトレーシングが開始されます。CPUは実行パイプラインの一部としてメタデータを自動的に記録し、ファザーはその結果のメタデータを調べて、実行された基本ブロックのトレースを抽出できます。これは不合理なほど効果的で、Intel PTベースのトレーシングは通常のネイティブ実行よりも約10%遅いだけです。
もちろん、問題は、私のような人がAMDプロセッサを持っていてIntelプロセッサを持っていないことです。AMDには、実行されているコードを記録するブランチトレースバッファを含む独自の魔法のパフォーマンスカウント機能がありますが、それは1) ドキュメントがはるかに悪く、2) Intel PTよりも遅く、3) 正確な方法で使用することは不可能です。つまり、カウンタはサンプリングベースであるため、イベントの1/nしか提供しないか、メタデータバッファがいっぱいになる前にイベントをドロップする可能性があります。どちらの場合も、ファジングには残念ながら適していません(技術的には、単なる確率的カバレッジの上にファザーを構築することは可能で、それほど悪くないかもしれません。しかし実際には誰もそうしておらず、おそらくそれだけの価値はないでしょう)。
そこで私の悪いアイデアが登場します。サイドプロジェクトのために独自のファザーを書きたいと思っており、正確なブラックボックスバイナリのカバレッジを収集したいと思っていました。しかし、独自の動的再コンパイルエンジン(再び)を書いたり、新しいラップトップを購入したりしたくはありませんでした。ソフトウェアエンジニアは何をすべきでしょうか?
代わりに、すべてのブランチを INT3 命令に置き換えることで、ゲストコードをインストルメント化できます。待ってください、説明します。
正確なカバレッジを収集するには、プログラムがブランチにヒットするたびに何かを実行する必要があります。各ブロックに新しい動作を挿入することはできません。なぜなら、ブロックはすでに通常の命令のためにブロック内のすべてのバイトを使用しているからです。ブロックのサイズを変更しようとすると、コードポインタの修正が必要になり、結局QEMU-だが悪いものに戻ってしまいます。ブランチ命令の最小長は2バイトです。Jcc には、単一のオペコードバイトとブランチ用の変位のみを持つ形式があります。INT3 は1命令長で、制御フローを乗っ取りますが、GPRを破壊しないため、命令実行後に続行できます。また、上書きしたブランチの位置をコンテキストとして提供するため、記録したいカバレッジビットマップエントリを計算できます。完璧です!
残念ながら、Linuxで ptrace を使用してこれを試みると、死にたくなるでしょう。Linuxは INT3 を SIGTRAP に変換します。これは、プロセスを監視している ptrace ベースのデバッガでキャッチできます。そのシグナルには、トレーシーのPCとレジスタ状態が含まれており、カバレッジフックを実装するために使用できます。その後、プロセスを続行するために PTRACE_CONT を使用します。しかし、このダンス全体は複数のコンテキストスイッチになります。ゲストプログラム(リング3)-> x86割り込みハンドラ(リング0)への INT3 トラップ -> リング3のデバッガで ptrace イベントを配信するLinuxカーネル -> システムコール経由でデバッガが PTRACE_CONT をリング0へ -> リング3でゲストを再開するLinuxカーネルシステムコール実装。これらのコンテキストスイッチのそれぞれは非常に高価です。特に、特権レベル間のコンテキストスイッチは、同じリング内コンテキストスイッチよりもプロセッサにさらに多くの作業を要求するためです。ああ、別の方法があれば!
答えは、もちろん仮想化拡張機能です。コンピューターは、Intel VT-x(Linuxでは kvm と呼ばれます)の魔法の力によって、その中に小さなコンピューターを実行できます。小さなコンピューター内のコードは、完全にベアメタルで実行されていると考えています。ゲストカーネルは、通常のカーネルのように割り込みハンドラ、MSR、ページングを好きなように設定でき、ゲストカーネルの下でユーザースペースコードを実行することさえできます[3]。すべて、実際には、ゲストカーネルは通常のLinuxカーネルによってホストされた仮想マシンで実行されています。ゲストカーネルが実際のワールドへのI/Oを行おうとすると、それらはホストカーネルにトラップされ、ユーザー空間イベントに変換され、「仮想マシンマネージャー」がそれを実装してから、結果とともに仮想マシンを再開するように設定できます。重要なのは、仮想マシンが実行されている間、それはベアメタルで実行されているということです。プロセッサは実際にゲストVMのすべての命令を実行しており、それらはすべて汎用レジスタやハードウェアページテーブルのような通常のプロセッサ状態を使用しますが、物理メモリのハイパーバイザー翻訳も行う追加のビットが付いています。これにより、VMはVMの境界外に到達できないようになります。重要なのは、VMは、ゲストカーネルがトラップする何かを行おうとしてホストカーネルにVMExitする必要がある場合を除き、基本的に100%ネイティブ速度で実行されるということです。実際、これは非常にうまく機能するため、インターネットのほぼすべてが、Firecrackerのようなクラウドベースのハイパーバイザーの形で kvm の上で実行されています。
TinyKVM は、Varnishの作者による素晴らしいプロジェクトです[4]。これはC++ライブラリとしてVMMを実装しており、任意のLinuxバイナリを実行するために使用できます。最小限のゲストVMと、ユーザモードコードを実行するために必要なx86プロセッサ状態を設定します。割り込みのほとんどがVMMにトラップするだけの小さなゲストカーネルを備えています。これは、ゲストバイナリをVMで実行し、write のようなシステムコールを行うと、VMExitにバブルアップし、ホストVMMが rax=1 と引数の他のGPRを見て、ホストで実際のFDと引数で独自の write システムコールを行うことができることを意味します。
これにより、INT3 フックのコンテキストスイッチが多すぎるという問題が自動的に解決されるわけではありません。しかし、ゲストカーネルは完全なカーネルであるため、INT3 がコンテキストスイッチする割り込みハンドラを好きなように設定できます。私は tinykvm をフォークして、TinyCOV と呼ぶものを作成しました。これはゲストカーネルを少しハックします。x86には、割り込みゲートを記述するIDTデータ構造の一部として、割り込みの特権レベルが実際に設定されています!これは、ゲストユーザースペースコードからゲストカーネル割り込みハンドラに INT3 がトラップする可能性がありますが、リング3に留まることができ、カバレッジフック実装をゲスト「カーネル」コードに直接配置して、割り込みから復帰して実行を続行する前に実行できるようにすることを意味します。これにより、各 INT3 カバレッジフックは、ゲスト割り込みルーチンへの出入りという2つのコンテキストスイッチに削減され、特権レベルの変更はゼロになります。また、ゲストカーネルが割り込みを完全に自分で処理できるため、VMMが特権操作をエミュレートする必要がないため、VMExitする必要すらありません。
ブランチ自体を INT3 で上書きするため、割り込みからトラップした場所に戻るだけでは実際には機能せず、実際のブランチ操作をスキップしてしまいます。INT3 は1バイトですが、ブランチの最小長は2バイトであるため、2バイト目を使用してブランチフックのメタデータを記録できます。そこにインデックスを格納し、そのインデックスとページ内の INT3 のオフセットを使用して場所を一意に識別し、上書きしたのと同じブランチ命令をJITコンパイルできます(ただし、ブランチの前後には元の後続命令へのジャンプ命令があります)。JNZ rax のような動的ジャンプの処理は少しトリッキーですが、それでも可能です。
カーネルからVMMへのVMExitの能力はまだあるため、コード発見を実装するためにもそれを活用できます。tinycov はブロックごとにブランチ命令をフックし、バイナリエントリポイントから開始します。最初にブランチをフックする際にメタバイトとしてセンチネル値を書き込み、ゲストカーネルがカバレッジフックにまだセンチネル値があることを検出して(つまり、初めて実行された場合)、ハイパーバイザーにトラップします。VMMは、基本ブロックの後続命令を逆アセンブルし、それらのブランチをフックして、コード発見のフロンティアを前進させ、センチネル値を正しいトランポリンインデックス値に置き換えることができます。これにより、将来そのブランチがヒットした場合でも、完全にゲストカーネル内に留まることができます。
結果
これがどれほど奇妙に聞こえるとしても、実際に機能します。ランダムなバイナリを tinycov で実行し、ヒットしたコードのカバレッジビットマップを収集できます。また、完全なプログラムトレースを生成するモードもあります。制御フローを完全に乗っ取ることで、INT3 カーネルハンドラに任意のコードを配置できます。cmp 命令で終わるブランチかどうかを記録し、レジスタオペランドの値を記録することで、CmpCOV スタイルの辞書構築を実装できました。カーネル割り込みハンドラ(およびVMM VMExitハンドラ)は、テスト対象プログラムのGPRセット全体に同期してアクセスできるため、Intel PTスタイルの非同期カバレッジトレースでは完全に実現できません。
とはいえ、tinycov はQEMUと比較してどのくらい速いのでしょうか?答えは、ええと、非常に遅いです。いくつかのベンチマークを実行したところ、約700%遅く、bzip4 のようなブランチが多いコードではさらに悪化します。これは、実行される命令ごとにさらに多くの INT3 ハンドラを呼び出すためです。CPUのアウトオブオーダーパイプラインは、たとえコンテキストスイッチが同じ特権レベルに留まるとしても、数命令ごとに割り込みが発生することを本当に嫌います。ユーザー空間割り込みハンドラを kvm の下で使用するというアイデアが機能することは嬉しいです。いくつかのベンチマークを行ったところ、適切なリング3 -> リング0割り込みを使用するよりも約50%高速でした!しかし、遅い方法よりも50%速いだけでも、QEMUがはるかに速い場合、これは実際には使用可能ではありません。
技術的には、QEMUやIntel PTベースのカバレッジではできない、いくつかのクールなことを可能にします。まず、ネイティブコードで実装された単一のカバレッジフックにトラップするため、カスタムカバレッジフックを追加するのは非常に簡単です。一部のファジングターゲットでは、ファザーが同じ制御フローを新しいプログラム状態として扱い、探索を続けるようにするために、カバレッジビットマップ計算に余分な状態を導入したい場合があります。たとえば、仮想PCやその他のデータ駆動ループを持つ言語ランタイムをファジングする場合です。QEMUでこれを行いたい場合は、独自のTCGフック(難しい)を書くか、JITコードからソフトウェアVMExitになるコードコールバックを設定する必要があります(遅い)。
コードをインプレースでフックするため、コードをアンフックする能力もあります。これはクールなことができると思います。QEMUでは、コード生成は高速化のためにJITブロック間に直接ブランチを発行しますが、インストルメンテーションはTCGで発行され、変換されたブロック命令の一部であるため、後でブロック内のフックを削除することはできません。着信エッジがまだ存在するためです。tinycov では、価値がないと判断したブランチ、または両方のtrueとfalseの出口を見て、新しいコードにつながる可能性がないとわかったブランチのカバレッジフックを削除できます。これにより、それらのブランチは元のバイトに戻され、文字通りネイティブ速度で実行されるようになります。
実際には、これはほとんどおもちゃであり、かわいいアイデアだと思いますが、それが機能すること自体は嬉しいです。おそらく、LibAFL のカバレッジ収集実装として使用するために接続してみるつもりですが、完全なファザーの一部としてQEMUよりもどれだけ悪くなるかを見るためにです。しかし、残念ながら、誰もこれを本番環境で使用しようとすべきではありません。動作させるのはかなり楽しかったですし、tinykvm をハックして必要な機能に対応させるのが非常に簡単だったことに、私はかなり驚いています。サイドプロジェクトで非常に呪われたx86カーネル開発を行うための言い訳があり、実際に完成できるほど小さく留まることは、私の本では勝利です。
脚注:
- 一部の人は、3番目の選択肢として「プログラムを形式的に証明する」と言うでしょう。彼らはあなたを騙しています。↩
- 実際にはもう少し複雑です。ほとんどのファザーは現在N-gramカバレッジを使用しており、最後のN個のブランチを組み合わせてビットマップエントリを計算し、より多くのパス依存情報を示すように設定します。奇妙なカバレッジメトリックを持つことは、最初の近似としては、「どのコードがヒットしたか」を記録することにまだ近いので、区別はそれほど重要ではありません。ブランチ履歴を記録する方法があれば、N-gramカバレッジも計算できるでしょう。↩
- 実際、Windows 11を使用している場合、実行していると思っている「ベアメタル」Windowsカーネルは、実際にはこの間ずっと仮想化ゲストとして実行されていましたhttps://learn.microsoft.com/en-us/windows-hardware/design/device-experiences/oem-hvci-enablement。それはちょっとクールではありませんか?↩
- はい、あのVarnishです。HTTPキャッシュです。↩