レースコンディションのテスト

レースコンディションのテスト 多くのセキュリティバグはレースコンディションであり、マルチスレッド実行がネガティブな効果が現れるために正しいインターリービングで発生する必要があります。これはいくつかのユースケースに課題をもたらします：手動または静的解析によって発見されたバグ候補の確認。回帰テスト：レースコンディションバグを修正した後、テストスイートの一部としてバグを確実にトリガーする回帰テストを作成する良い方法がないことがよくあります。自動バグ発見、例えばファジング：ファザーが並行操作のすべての興味深いインターリービングを行使したり、操作が競合するときにのみ行使されるコードパスに到達したりすることは困難です。 私は主にコードを読んでバグを発見します。バグを見つけたと思ったら、通常はバグが存在するかどうかを証明または反証するためのテストケースを作成します。レースコンディションバグの場合、どちらの結果も達成するのは難しいことがあります。 Linuxカーネルのバグについては、適切な場所に条件付きのmdelay()呼び出し（指定された時間だけスピンループする）を追加した後、カーネルを再コンパイルすることに頼ることがよくあります。通常、これらは実行中のスレッドの名前に基づいて条件付けしますが、より複雑な条件が必要な場合もあります。DTrace（macOSやWindowsなど）をサポートするプラットフォームでは、同様の効果を得るためにchill()を呼び出すDTraceプローブを使用できますが、DTraceはインライン関数境界または明示的なトレースポイントでのみトレースできるため、その有用性は限られています。プラットフォームに関係なく、このアプローチは時間がかかり、コードがバグがあるかどうかを確実に判断するために試行錯誤が必要になる場合があります。 さらに、Linuxカーネルでは、レースコンディションバグの修正には、問題のあるスレッドのインターリービングをコールグラフと関連メモリアクセスとともに示す手書きのASCIIダイアグラムが伴うことがよくあります（例：最近のrt_spin_unlock UAF修正、または最近のjbd2デッドロック修正を参照）。潜在的に脆弱なコードを分析し、同様の表現で結果を示す開発者ツールがあると便利でしょう。 要約 Linuxカーネル用のマルチスレッドテストケースの可能なインターリービングを探索するためのツールを作成しました。 * テストケースのすべての可能なA-B-Aインターリービングを自動的にテストするツール。 * インターリービングを手動で探索するためのターミナルUI。 * インターリービングを手動で探索するためのGUI。 カーネル部分は、ファジングによるレースコンディションの発見にも使用できることを意図していますが、ユーザー空間ツールはまだ実装する必要があります。 ツールはGitHubでMAccConc（「Memory Access Concurrency」の略）という名前で利用可能です。インストールと使用方法については、そこのREADMEを参照してください。 ツールの動作を見たいだけであれば、デモ：自動テストにスキップしてください。ツールの背後にある理論にのみ興味がある場合は、セクション安定識別子：実行ごとのメモリアクセスを参照してください。 先行研究 このプロジェクトは、Ned Williamsonとの議論に触発されました。彼のsockfuzzerプロジェクトは、同期プリミティブで再スケジュールできるカスタムスケジューラを使用して、インターリービングを探索することにより、並行バグの探索を含んでいました。この並行テストの側面に焦点を当てたカンファレンストークのスライドと録画を参照してください。 私のツールは、基本的にSKIのアイデアに基づいていますが、SKIは異なる実装を使用しています。メモリアクセスを記録し、TCGモードのパッチ適用されたQEMUバージョンを使用してvCPUのスケジューリングを制御し、VMスナップショットを使用して異なる実行インターリービングを探索します。 実行ごとのメモリアクセスに対する安定識別子：カウント拡張スタックトレース メモリアクセスの異なる順序をテストするために、テストケース実行全体で興味深いメモリアクセスを安定して識別する方法が必要です。データアドレスに基づくメモリアクセスの識別は、テストケース実行中に新しく割り当てられたオブジェクト内のデータアドレスの場合には機能しません。命令アドレスのみに基づくメモリアクセスの識別は、memcpy()やspin_lock()のような関数内のメモリアクセスの場合にはうまく機能しません。SKIはVMを使用してこれを解決します。 レースコンディションに寄与する可能性のあるメモリアクセス（通信ポイント）の発見 SKIの論文で説明されているように、与えられたマルチスレッドテストケースの興味深い実行インターリービングは、すべてのスレッドのメモリアクセスをトレースし、互いに相互作用する可能性のある2つのスレッドのアクセスのペアを探すことによって発見できます。これは、少なくとも1つが書き込み操作であり、それらが重複するメモリ範囲にアクセスすることを意味します。SKIの論文では、このようなメモリアクセスを通信ポイントと呼んでいます。 これには、メモリアクセス範囲を収集する何らかのメカニズムが必要です。SKIはQEMUのTCGモードをパッチすることによってこれを行いました。私は代わりに、ASANインストルメンテーションを「アウトライン」モード（コンパイラバックエンドフラグasan-instrumentation-with-call-threshold=0、LinuxカーネルのCONFIG_KASAN_OUTLINEによって選択）に依存しています。これは、メモリアクセス時にヘルパー関数呼び出しを生成します。 カーネルは、カーネルがロック取得/解放イベントなどに関するより高レベルの情報も提供できるように、このデータを収集するのに適切な場所であると私は信じていますが、現時点ではこれを実装していません。カーネルにこれを実装することは、理論的にはVM内ではなく、ベアメタルハードウェアでテストできることも意味します。 Linuxにはすでに基本的なブロックカーネルカバレッジ情報をユーザー空間にフィードするためのKCOVメカニズムがありますが、メモリアクセスに関する情報を記録するために同じメカニズムを使用することにしました。代替案としては、トレースユースケース向けで、fentryフックに基づいた関数グラフトレースモードと、システム全体のデータ収集を含むユースケース向けに管理されたより複雑な出力バッファを備えたftraceを使用することが考えられます。 KCOVを選択した理由は、トレースデータのよりシンプルなインメモリ表現（クラッシュしたVMからトレースデータを回復する際に重要になる可能性がある）、ランタイムで有効化されるインストルメンテーションではなく、無効状態ではほぼゼロのオーバーヘッドを持つ静的な常時オンインストルメンテーションを使用すること、そしてftraceよりも高頻度のトレースイベント向けに設計されているという印象を受けたためです。 実装の詳細：ASANとTSAN ASANは通常、後続のメモリアクセスに対してヘルパー呼び出しをマージします。メモリアクセスごとに1つのコールバックを受け取るために、カーネルはasan-opt-same-tempバックエンドフラグを使用して、このコンパイラ最適化を明示的に無効にします。 ASANは通常UAFを特定するために使用されるため、スタック上のオブジェクトへの直接アクセスでは、アウトオブバウンドアクセスが発生する可能性がある場合を除き、ヘルパー呼び出しを発行しません。これは、待機キューのようなオンスタックオブジェクトを伴う一部のレースコンディションは、これで検出できない可能性があることを意味します。 ASANはデフォルトでグローバルへのアクセスに対してヘルパー呼び出しを発行しませんが、asan-opt-globalsバックエンドフラグを使用してこの最適化を無効にすることができます。 代替案としては、データレースの検出のために設計されており、アクセスアトミシティに関する情報も提供するTSANインストルメンテーションを使用することが考えられます。TSANインストルメンテーションの欠点は、コンパイラがASANとTSANのフックを同時に発行することをサポートしていないことです。そのため、TSANフックを使用しながらメモリ安全違反（UAFなど）の検出を機能させるには、カーネルのASAN実装をTSANフックから実行するか、コンパイラを変更する必要があります。 実装の詳細：KCOVとバックグラウンドワーク 一部のレースコンディションはバックグラウンドワークを伴います。例：ループバックネットワークパケットの受信処理、RCUコールバック。 KCOVはオプションで一部のサブシステムでバックグラウンドワークのリモートカバレッジを収集できます。しかし、アップストリームLinuxでは、私にとって興味深いほとんどの種類のバックグラウンドワークはまだこのメカニズムと統合されていません。リモートカバレッジは現在、主にBluetoothやUSBのようなデバイスからの受信データを処理するサブシステムのファジングに使用されています。カーネルの他の部分でこれを有効にすることは比較的簡単であるはずで、RCUコールバックのためにこれを行うためのパッチドラフトがあります。 実行ごとのメモリアクセスに対する安定識別子：カウント拡張スタックトレース メモリアクセスの異なる順序をテストするために、テストケース実行全体で興味深いメモリアクセスを安定して識別する方法が必要です。データアドレスに基づくメモリアクセスの識別は、テストケース実行中に新しく割り当てられたオブジェクト内のデータアドレスの場合には機能しません。命令アドレスのみに基づくメモリアクセスの識別は、memcpy()やspin_lock()のような関数内のメモリアクセスの場合にはうまく機能しません。SKIはVMを使用してこれを解決します。