メモリアクセス追跡とスタックベースの遅延注入による競合状態のテスト

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