Reproducible Containers (ASPLOS'20)

ゼミ資料 浅田睦葉 20251110

Transcript

1. システムセキュリティ研究室 ゼミ 2025/11/10 Reproducible Containers 担当: 浅田睦葉 情報科学類4年 1 Omar S. Navarro Leija et al.
2. 2 目次 1.概要 2.背景 3.提案手法 4.DetTraceの設計 5.実験方法 6.評価 7.まとめ
3. 3 1. 概要
4. 4 書誌情報 ・タイトル 　・Reproducible Containers ・著者 　・Omar S. Navarro Leija, Kelly Shiptoski, Ryan G. Scott, Baojun Wang, 　　Nicholas Renner, Ryan R. Newton, Joseph Devietti ・会議 　・ASPLOS’20 　・The International Conference on Architectural Support for Programming 　　Languages and Operating Systems 2020 ・URL: https://dl.acm.org/doi/10.1145/3373376.3378519
5. 5 概要 ・再現性はビルドだけでなく、科学技術計算や分散システム、プログラムの 　デバッグなどに対して良い影響を与える ・再現可能（reproducible）なコンテナをLinuxユーザ空間で実現する手法を提案 　・初期ファイルシステム状態にのみ依存した純粋関数として計算を実行 ・この研究では、再現可能なコンテナであるDetTraceを実装 　・完全にユーザ空間で動作する 　・実行したいバイナリを書き換えない 　・root権限が不要 ・Linuxが提供するコンテナ機能とptraceを組み合わせて実現している
6. 6 2. 背景
7. 7 モチベーション ・現代の計算環境では、同一のプログラムに同一の入力を与えて実行しても結果が 　変わることがある 　・非決定的要因が原因 　　・システムクロックの時刻 　　・プロセスIDやスレッドの実行順序 　　・乱数、ハードウェア依存命令 ・結果が変わると何が困るのか？ 　・ソフトウェアビルドの信頼性が低下する（安定的にソフトウェアを出荷できない） 　・科学技術、機械学習分野の実験再現性を損なう ・ 💪 アプリケーションを変更せず、OSやカーネルに手を入れずに解決したい！
8. 8 決定性と再現性の違い ・ 🤔 既存の決定論的なOSで解決できないのか...？ 　・たとえばDeterminatorは毎回同じreadが同一の値を返す決定実行を提供する 　・この仕組みの元でビルドや計算をすればいいのでは ・決定性は、同一マシンにおける実行の性質 　・起動時刻やPIDなどの開始状態に差が出るためファイルシステムは決定的でない 　・さらに、複数マシンで同一の結果が得られることは保証しない ・再現性は、複数のマシンにおいて同一の結果が得られる性質 　・大規模なソフトウェアや実験では分散ビルド、分散計算を行う 　・Dockerなどの通常のコンテナではホストにより挙動に差が生まれるため不十分
9. 9 なぜ再現性が重要なのか ・再現性は、複数のマシンで同じ入力に対して常に同じ結果を得られる性質 ・恩恵を受ける分野はたくさんある 　・デバッグ、分散システム、ビルド、科学技術計算、機械学習、... ・デバッグ 　・問題が同じ形で再現できるので、より短時間で開発者が問題解決に至れる ・分散システム 　・レプリカ間における一貫した動作を保証できる → 合意形成が早まる ・ビルド 　・ビルドの信頼性が向上、キャッシュヒット率も向上してビルド時間も短縮 ・科学技術計算、機械学習 　・モデルや性能改善の評価で再現性が必要だが、乱数や並列計算の順序に依存する 　　ため通常は非決定的
10. 10 3. 提案手法
11. 11 再現可能コンテナ ・本研究の目標 　・再現可能なコンテナ（reproducible container）を提供すること ・初期のファイルシステム状態とそこから実行されるプログラムにより定義される ・コンテナ内で実行されるプログラムは以下を実行できる 　・任意のx86命令 　・Linuxシステムコール 　・ただし、すべての呼び出しを必ず成功させることは保証しない ・コンテナ内で実行されるコードは以下の範囲で相互作用できる 　・自身のファイルシステム 　・コンテナ内で並行して動作する他のプログラム ・将来的には再現性が保証される範囲で外部とのやり取りを許可する方向性 　・ハッシュ値が既知のファイルのダウンロード（Nixにおけるfetchurl）
12. 12 再現性の構成要素 ・再現性を保証することは、すなわち以下の2つの性質を保証することである 　・決定性（determinism）= データフロー決定性（dataflow determinism） 　・移植性（portability）
13. 13 再現性の構成要素: 決定性 ・同一のマシン上では、すべてのread操作が毎回同じ値を返すという性質を 　データフロー決定性と呼ぶ 　・この性質により、時刻や明示的な乱数などの非再現要因が隠蔽される 　・つまり、gettimeofday() や getrandom() は呼べるが、 　　DetTraceが固定した値を返すようにする ・決定性が成り立つと、以下のような性質が得られる 　・全てのプロセスが終了した後のファイルシステムの状態が常に同一 　・標準出力、標準エラー出力に出力されるメッセージも常に同一 ・厳密には決定化ができない外部要因が存在するため準決定性（quasi-determinism） 　・たとえば、ディスク容量の枯渇 ・同一の実行を2回行った時、データフロー決定的である or クラッシュ
14. 14 再現性の構成要素: 移植性 ・データフロー決定性が異なるマシン間でも成立することを移植性と呼ぶ 　・CPUのマイクロアーキテクチャやOSのバージョンが異なっても同一の結果 ・実際のアーキテクチャやハードウェア、OSの差異を隠蔽するために、 　DetTraceのコンテナは常に以下の環境を仮想的に提示する 　・x86-64 単一コア 　・Linux kernel 4.0 ・実用性の観点から、Arm上でx86-64 CPUをエミュレートすることはしない 　・制約として、Intel Ivy Bridge以降のプロセッサとLinux 4.12〜を前提とする
15. 15 コンテナ技術との比較 ・既存のコンテナ技術（Dockerなど）は以下の情報が内部から直接見える 　・ホストOSの詳細 　　・ファイルシステムのmtime, ctime 　　・カーネル構成（/proc/version, /sys/devices/ など） 　・プロセッサのマイクロアーキテクチャの詳細 　　・CPU命令レベル（cpuid, rdtsc など） → したがって、決定性も移植性も持たない
16. 16 仮想マシンとの比較 ・VMはDockerよりも強いハードウェア抽象化を提供する ・以下の3つの理由により、決定性を持たない 　・VM上のスレッドスケジューラやI/O割り込みがホストOSのタイミング依存 　　・同一入力を与えても割り込み順序やスレッド実行順序が変化する 　・VMのRTC(Real Time Clock)やTSC(Time Stamp Counter)はホストの時計や 　　NTPなどに依存 　・VMごとにエミュレートされるハードウェア構成が異なる ・DetTraceは時刻や乱数、スケジューラを固定するため、例外を除き再現性を持つ
17. 17 Linux / x86-64における再現性の要件 ・コンテナ内で実行されるコードは2つのインタフェースにアクセスできる 　・x86-64命令セット 　・LinuxシステムコールAPI → どの命令、ないしはシステムコールが非再現性の原因となるのか？ ・特に、クリティカルなインタフェース要素を特定する必要がある 　・非再現性を引き起こす可能性があるが、実行時に確実に検出できない命令/syscall 　・もしそのような命令が存在するなら、サイレントに非再現性が導入されてしまう
18. 18 システムコールの監視と対処 ・Linuxの全てのシステムコールは ptrace で観察できる 　・したがって、クリティカルな = 検出不可能なシステムコールは存在しない ・非再現性の原因となるシステムコールの例 　・時刻系（gettimeofday） 、乱数系、シグナル、タイマ、ファイルメタデータなど ・対処 　・システムコールをラップしたり代替手段に置き換えたりして決定的にする 　　・time() の戻り値を固定値にする 　・システムコールをnopに変換する 　・非サポート扱いとして、再現可能な一貫したエラーを発生させる
19. 19 x86-64命令における非再現性 ・x86-64命令セットには多数の非再現的命令が存在する ・特権命令 　・非再現的だが、ユーザ空間コンテナで実行されると例外が投げられるので 　　DetTraceの観点では問題ではない（ので省略） ・rdrand / rdseed 　・ハードウェアエントロピー源からランダムビットを返す命令 　・ハイパーバイザからは捕捉できるがring 0レベルでは捕捉できない 　→ cpuidで存在しないと報告してプログラムに使わせない ・rdpmc 　・パフォーマンスカウンタを読み取る命令 　→ ユーザ空間からも実行できる場合があるが、カーネル設定によりトラップできる
20. 20 TSX命令の非再現性 ・調査の中で、x86-64命令で明確にクリティカルな命令群を特定した ・TSX: Transactional Synchronization Extensions 命令群 　・複数スレッドが同じメモリを扱う際には、ロックで排他制御を行う 　・しかし、ロックは待ち時間が発生するため性能が低下する 　→ロックを取らずに全部成功 or 全部失敗のどちらかになるようにメモリ操作を行う 　　・もし衝突したらやり直す 　　・高速に並行実行できる ・トランザクションのabortは観測不能な要因で起こる 　・CPU内部のタイミング、割り込み、キャッシュ状態、... 　・さらに、xbeginでアボートハンドラ（abortすると実行される）を登録できる 　　→ 本質的に決定的に制御できない
21. 21 TSX命令の非再現性の対処 ・cpuidを使えばrdrandでもTSXでも利用できない命令であると報告できる 　・善良なプログラムはcpuidの報告に従うので再現性を保証できる 　・cpuidの結果に従わない悪意あるプログラムは呼び出せてしまい、再現性が壊れる ・rdrandは純粋に乱数を返す命令なので実行経路や他の命令に対する副作用を 　持たない上、VT-xなどを利用してハイパーバイザで捕捉できる ・TSXはcpuidで存在を隠蔽できるが、ハードウェアで検出することができない 　→ x86-64命令セットの中でクリティカルな命令群であると考えられる ・著者らは将来的にハードウェアレベルで命令トラップが可能になる仕組みが 　必要であると主張している
22. 22 4. DetTraceの設計
23. 23 設計 ・DetTraceは標準的なLinuxのコンテナ技術を利用する 　・namespace: UIDやPIDなどを隔離する 　・bind mount: 必要なファイルやディレクトリをコンテナに安全に見せる 　・chroot: コンテナ内のファイルシステムを限定する ・さらに、ptraceで他のプロセスを監視して、全てのシステムコールを監視する → 環境を隔離し、再現性を壊す動作を再現可能な 　形に書き換えるか、禁止する ・ここからは具体的な要因に対する処理を説明
24. 24 ① プロセス、ユーザID、グループID ・LinuxのPID namespaceを利用する 　・プロセスIDの見え方を独立させるLinuxが持つ機能（clone, CLONE_NEWPID） ・コンテナ内のプロセスはホストとは独立した固有のPIDを受け取る 　・コンテナ内のプロセスはコンテナ外のプロセスを名前で参照できない ・コンテナ内のプロセスは決定的に生成・終了する 　→ Linuxは各ネームスペース内でPIDをシーケンスに割り当てるので決定的となる ・ユーザID、グループIDについてもuser namespace, group namespaceを利用 ・したがって、これらはホストから分離される
25. 25 ② OSが生成する乱数 ・Linuxのユーザプロセスは以下の手段で乱数を取得できる 　・① getrandomシステムコール 　・② /dev/random、/dev/urandomのread ・① getrandom() のインターセプト 　・PTRACE_SYSCALLをフックして、システムコール番号が__NR_getrandomなら 　　DetTraceがカーネルに渡さず、自前の擬似乱数生成器で乱数を生成 　・トレースしたプロセスのメモリに乱数を書き込み、成功扱いで実行を再開 ・② /dev/random, /dev/urandom 　・起動時に独自の /dev/random, /dev/urandomを名前付きパイプとして準備 　・DetTraceは別スレッドで擬似乱数を定期的に書き込む
26. 26 ③ 時刻とクロック ・Linuxのユーザプロセスは以下の手段で現在時刻を取得できる (実行の度に変化) 　・gettimeofday(), clock_gettime(), time() ・DetTraceでは時間をユーザプロセスが時刻取得関数を呼び出した回数と定義する 　・この定義は時刻の単調増加性、再現性、相対的順序を保つ ・Linuxでは性能向上のため、gettimeofday() などをシステムコールを呼ばずに 　ユーザ空間で直接実行される（vDSOメカニズム） 　・しかし、これはカーネルを通過しないためptraceで呼び出しを捕捉できない 　・LD_PRELOADで上書きすれば良いように思えるが、静的リンクされたバイナリに 　　効果が無く、プロセスがgetauxval()を使ってvDSOを呼ぶことがある 　　・実際に、libcの mkstemp() はvDSOを直接呼び出す ・そこで、プロセスが新しいプログラムを起動した直後に、そのプロセス空間にある 　vDSOライブラリを上書きして独自実装を挿入し、syscallを呼び出すようにする
27. 27 ④ シグナルとタイマ ・通常のLinuxはシグナル送信のタイミングが非決定的 　・プログラムがシグナルに依存していると再実行のたびに挙動が変更される ・DetTraceではシグナルを常に明示的に制御して同じ順番で処理するようにする 　・制約として、プロセス間シグナルを無効化している 　・自分自身へのシグナルは扱う 　・特に、SIGSEGV, SIGILL, SIGABRTは実行中に必ず同じタイミングで 　　発生するので再現的に扱える → precise exceptions（厳密な例外） 　・タイマによるシグナルは順番が維持される形で即時的に 　　実行されるように変換する
28. 28 ④ シグナルとタイマ ・通常のLinuxはシグナル送信のタイミングが非決定的 　・プログラムがシグナルに依存していると再実行のたびに挙動が変更される ・DetTraceではシグナルを常に明示的に制御して同じ順番で処理するようにする 　・制約として、プロセス間シグナルを無効化している 　・自分自身へのシグナルは扱う 　・特に、SIGSEGV, SIGILL, SIGABRTは実行中に必ず同じタイミングで 　　発生するので再現的に扱える → precise exceptions（厳密な例外） 　・タイマによるシグナルは順番が維持される形で即時的に 　　実行されるように変換する
29. 29 ⑤ ファイルとディレクトリ ・chrootでコンテナ内のプログラムからホストのファイルが見えないようにする ・UID/GID, パーミッションなどのメタデータを入力の一部とみなす 　・コンテナ内で現在のユーザをroot（UID 0）にマップし、それ以外を 　　nobody/nogroupにマップする ・ディレクトリ内容の取得（getdents()）は並び順がファイルシステム依存 　・DetTraceは名前順にソートしてから返す ・read/writeは要求したバイト数全てを処理しないことがある 　・足りなかった場合は再試行して、プログラムからは1度で全て読めたように見せる 　・read syscallを捕捉 → 部分読み取りであればプログラムカウンタを1つ戻して 　　再実行し、引数を調整して続きを読む ・ファイル/ディレクトリの一意のIDであるinodeがOSによって再利用される 　・DetTraceがファイルごとに独自の仮想inodeテーブルを管理して再利用しない ・ファイルタイムスタンプは、atime/ctimeを0に固定、mtimeは仮想時刻を割り当て
30. 30 ⑥ 決定的なスケジューラ ・通常はOSがいつ、どのプロセスを実行するかを自由に決める 　→ マルチプロセス/マルチスレッド環境では実行順序が変動する ・DetTraceの決定的なスケジューラの実装 　・ユーザ空間内のコード実行、すなわち通常の計算は並行で計算 　・システムコールは1つずつ順番に実行する 　・ブロッキングを起こすシステムコール（readなど）はデッドロックを起こす 　　→ Non-blocking I/O mode に書き換える（O_NONBLOCK） 　　・戻されたら Blocked queue に入れておく ・Parallel queue: 並行実行中のプロセス ・Runnable queue: 次に実行すべきsyscallを持つプロセス ・Blocked queue: システムコール中で待機するプロセス
31. 31 ⑦ スレッド ・Linuxではスレッドも実装上は軽量プロセスとして扱われる 　→ ptraceでプロセスと同様の方法で制御できる ・DetTraceでは同じプロセス内の異なるスレッドを順番に実行するように変更する 　→ 共有メモリへのアクセス順が常に同じになる 　→ 競合（race condition）が発生しない 　→ 何回実行しても、同じ順序で同じ値が読み書きされる ・スレッド間の排他制御にはfutex（fast userspace mutex）が利用される 　・waitが呼ばれるとBlocked queueに入れて停止させる 　・wakeが呼ばれると他のスレッドが再開可能になる 　→ これによりfutexベースのロックも決定的に動作させることができる
32. ・CPUを実行し続けて待機するbusy-wait方式のプログラムは再現的に制御できない 　・DetTraceのスケジューラはシステムコールを元に切り替えを行うから 　　・ptraceはシステムコールの前後でのみトレースを行う 　・スレッドが動かずに全体が停止してしまう 32 ⑦ スレッド: 制約
33. 33 5. 実験方法
34. ・DetTraceが提供する再現可能コンテナを、以下の3点で評価する 　・① 再現性 　　・同一の入力で同一の結果を得られるか 　・② 正確性 　　・DetTrace下でも動作結果が壊れないか 　・③ パフォーマンス 　　・DetTrace下ではどの程度のオーバーヘッドが発生するか ・実験環境 　・Linux distribution: Debian 7 　・Intel Skylake, Linux Kernel 4.15 34 評価指標と実験環境
35. ・再現性 　・reprotest v0.7.8を実験用に改良して利用した 　・ビルドを2回行い、以下のような条件差を付けて再現性を破壊することを試みる 　　・ビルド順序、タイムスタンプを変更する 　　・ファイルシステム内のメタデータを差し替える ・正確性 　・DetTraceでビルドしたバイナリをVM上で起動させ、通常ビルド版と 　　一致することを確認して評価する ・移植性 　・Skylake上で動作するUbuntu 18.04とBroadwell上で動作するUbuntu 18.10 　・ランダムに選んだ1000パッケージを再ビルドして比較 35 評価手法
36. 36 6. 評価
37. ・12,130個のDebianパッケージを対象に評価 ・DetTraceがサポートする全パッケージを100%再現した 　・対象外としたパッケージは除外（708個） 　・通常のビルドでは11,958件中、8,688件（72.65%）が非再現であった 　・元々再現したパッケージも再現した 37 再現性の評価
38. ・LLVM 3.0をビルドしてテストスイートを比較した 　・DetTrace下でも通常環境でもテストスイートの結果は変わらなかった ・両者でビルドしたBlenderのGUI操作や出力結果も変化しなかった ・ランダムに抽出した1000個のパッケージのうち、全てのバイナリのハッシュが 　完全に一致した 　・stat()が返すディレクトリサイズに差異があり、再現値を返す処理を追加した 38 正確性 / 移植性の評価
39. ・計算中心のタスクではオーバーヘッドは2%未満であった ・I/O負荷の高いビルドでは平均オーバーヘッドは3.49倍であった ・主要因はシステムコールの量であり、毎秒のsyscallの呼び出し回数が多いほど 　遅くなることが明らかになった 39 パフォーマンスの評価
40. 40 7. まとめ
41. ・DetTraceはLinuxユーザ空間で動作する再現可能コンテナ ・12,130個のDetTraceが対応するDebianパッケージについて、 　バイナリ側の改変なしに再現可能なビルドを実現した ・Linuxコンテナ機能とptraceを用いて、環境の隔離とシステムコールの捕捉を行う 　ことで、再現性に影響を与えるファイル、時刻、乱数、スケジューリングなどの 　要因を仮想化して統一的に制御する ・計算中心のタスクではオーバーヘッドが2%未満で、I/O中心のビルドでも 　平均3.49倍と実用的な範囲内であった ・TSXやソケット通信など、ハードウェア依存の非決定要因については未対応 41 まとめ