Fil-Cの単純化モデル

 (corsix.org)
2 ポイント 投稿者 GN⁺ 10 일 전 | 1件のコメント | WhatsAppで共有
  • C/C++のポインタに AllocationRecord メタデータ を付随させて追跡し、逆参照時に メモリ境界検査 を行う構造
  • ポインタ代入、算術、関数引数の受け渡し、戻り値、malloc・free 呼び出しまで、元のポインタ値と対応するメタデータを一緒に移動するか、Fil-C 専用呼び出しに変換する方式
  • ヒープメモリ内のポインタメタデータは invisible_bytes に別途保存し、ポインタのロード・ストア時に値とメタデータを一緒に読み書きし、アラインメント検査 も追加で適用
  • filc_free は visible_bytes と invisible_bytes だけを解放し、AllocationRecord 自体は維持し、その後の整理はガベージコレクタが担当し、アドレスがエスケープする可能性のあるローカル変数は ヒープ昇格 で処理
  • スレッド、関数ポインタ、メモリ・性能最適化など実装上の複雑さは残るが、大規模な C/C++ コードの メモリ安全性検証 や pointer provenance の 具体的なシステム例 として活用できる可能性がある

単純化した Fil-C モデル

  • Fil-C は C/C++ コードをメモリ安全に扱うため、ポインタと一緒に AllocationRecord* メタデータを追跡する構造を使う
    • 実際の実装は LLVM IR の書き換え方式だが、単純モデルでは C/C++ ソースコードを自動変換する形
    • 各関数のポインタ型ローカル変数ごとに対応する AllocationRecord* ローカル変数を追加
    • 例として T1* p1 には AllocationRecord* p1ar = NULL を追加する形
  • ポインタのローカル変数に対する単純な代入や計算では、元のポインタ値と一緒に AllocationRecord* も同時に移動する方式
    • p1 = p2 は p1 = p2, p1ar = p2ar に変換
    • p1 = p2 + 10 でも p1ar = p2ar を伴う
    • 整数からポインタへのキャストはメタデータを NULL に設定
    • ポインタを整数に変換するキャストはそのまま維持
  • 関数引数の受け渡しと戻り値でも、ポインタと一緒に AllocationRecord* を追加で渡し、特定の標準ライブラリ呼び出しは Fil-C 専用関数 に置き換える
    • malloc と free の呼び出しはそれぞれ filc_malloc、filc_free の形に変換
    • 例として p1 = malloc(x); free(p1); は {p1, p1ar} = filc_malloc(x); filc_free(p1, p1ar); の形
  • filc_malloc は要求されたメモリを 1 つだけ確保するのではなく、3 つの割り当てを行う
    • AllocationRecord オブジェクトの割り当て
    • 実データ用 visible_bytes の割り当て
    • 見えないメタデータ保存用の invisible_bytes を calloc で割り当て
    • AllocationRecord は visible_bytes、invisible_bytes、length フィールドを持つ

逆参照と境界検査

  • ポインタの逆参照時には付随する AllocationRecord* を使って 境界検査 を行う
    • ポインタメタデータが NULL でないことを確認
    • 現在のポインタ位置と visible_bytes の開始アドレスとの差を計算
    • オフセットが全体の長さより小さいことを確認
    • 残りの長さが逆参照対象のサイズ以上あることを確認
  • 読み込みと書き込みの両方に同じ検査手順を適用
    • x = *p1 の前にも検査を実行
    • *p2 = x の前にも同じ形の検査を実行
  • この構造により、ポインタが指す対象へのアクセスが割り当て範囲を外れるのを防ぐ

ヒープ内のポインタと invisible_bytes

  • ヒープメモリに保存されたポインタは、ローカル変数のようにコンパイラが直接別変数として管理できないため、invisible_bytes を使う
    • visible_bytes + i の位置にポインタがあるなら、対応する AllocationRecord* は invisible_bytes + i の位置に保存
    • つまり invisible_bytes は要素型が AllocationRecord* の配列のように動作する
  • ポインタ値をメモリから読み書きする際は、通常の境界検査に加えて アラインメント検査 を追加
    • オフセット i が sizeof(AllocationRecord*) の倍数であることを確認
    • この条件を満たして初めて invisible_bytes を AllocationRecord** 配列のように安全にアクセスできる
  • ポインタのロード時にはデータポインタと一緒にメタデータも読み込む
    • p2 = *p1 は p2 = *p1 の後に p2ar = *(AllocationRecord**)(p1ar->invisible_bytes + i) を追加
  • ポインタのストア時にはポインタ値だけでなく、対応するメタデータも一緒に保存
    • *p1 = p2 は実データ保存後に *(AllocationRecord**)(p1ar->invisible_bytes + i) = p2ar を実行

filc_free とガベージコレクタ

  • filc_free はポインタが NULL でないとき、AllocationRecord との整合性を検査したうえで 2 つのメモリだけを解放する
    • par != NULL を確認
    • p == par->visible_bytes を確認
    • visible_bytes と invisible_bytes を解放
    • その後 visible_bytes、invisible_bytes を NULL に、length を 0 に変更
  • filc_malloc は 3 つを割り当てるが、filc_free は AllocationRecord オブジェクト自体は解放しない
    • この差分はガベージコレクタが処理する
  • 単純モデルでは stop-the-world GC で十分で、実際の Fil-C は並列・並行・インクリメンタル収集器を使う
    • GC は AllocationRecord オブジェクトをたどって追跡
    • 到達不能な AllocationRecord を解放対象として扱う
  • GC は追加で 2 つの作業を行う
    • 到達不能な AllocationRecord を解放するときに filc_free を呼び出す
    • length が 0 の AllocationRecord を指すすべてのポインタを、長さ 0 の単一の正規 AllocationRecord に変更する
  • この動作により、free を呼ばなくてもメモリリークにはつながらない
    • GC が自動で解放を実行
    • ただし free 呼び出しは GC より早い時点でのメモリ解放を可能にする
  • free 後、その AllocationRecord は最終的に到達不能になり、後で整理できる

ローカル変数アドレスのエスケープとヒープ昇格

  • GC が存在すると、ローカル変数のアドレスを安全に扱える範囲が広がる
    • ローカル変数のアドレスが取得され、そのアドレスが変数寿命の外へ エスケープしないことの証明 をコンパイラができない場合は、ヒープ割り当てに昇格する
  • こうしたローカル変数はスタックではなく malloc で割り当てる
    • 対応する free を別途挿入する必要はない
    • GC が回収を担当する

Fil-C 版 memmove

  • C 標準ライブラリの memmove は任意のメモリを扱うため、その中にポインタがあるかどうかをコンパイラが把握できないという問題がある
  • これに対して ヒューリスティック を適用
    • 任意メモリ内のポインタは、そのメモリ範囲内に 完全に含まれている 必要がある
    • ポインタは正しくアラインされていなければならない
  • この規則により、同じ 8 バイトの移動でも動作に差が出る
    • アラインされた 8 バイトを 1 回で memmove すると、対応する範囲の invisible_bytes も一緒に移動する
    • 1 バイトずつ 8 回に分けて memmove すると、invisible_bytes は移動しない

実装で追加される複雑さ

  • スレッド

    • 並行性は GC の複雑さ を高める要因
    • filc_free はメモリを即座には解放できない
      • 解放中のスレッドと、他のスレッドによる同一メモリへのアクセスが競合状態になる可能性があるため
    • ポインタに対するアトミック操作も追加の処理が必要
      • 基本的な書き換えではポインタのロード/ストアを 2 回のロード/ストアに変えるため、アトミック性が壊れる

  • 関数ポインタ

    • AllocationRecord の追加メタデータとして、visible_bytes が通常データではなく 実行コードポインタ であることを示す
    • 関数ポインタ p1 を通じた呼び出しでは、p1 == p1ar->visible_bytes の確認とともに、p1ar が関数ポインタを表すかどうかを検査
    • 関数ポインタに対する型混同攻撃を防ぐため、呼び出し ABI でも 型シグネチャ検証 が必要
    • 1 つの方法は、すべての関数が同一の型シグネチャを持つようにする方式
      • すべての引数を構造体に詰めてメモリ経由で渡すように扱う
      • ABI 境界では各関数が、その構造体に対応する単一の AllocationRecord 1 つだけを受け取る形

  • メモリ使用量の最適化

    • filc_malloc が invisible_bytes を即時に割り当てず、必要時に遅延割り当てする方式を検討できる
    • AllocationRecord と visible_bytes を 1 回の割り当てで一緒に配置する方式も検討できる
    • 基盤の malloc が各割り当ての先頭部分にメタデータを付けるなら、そのメタデータを AllocationRecord に取り込む方式も候補になる

  • 性能最適化

    • Fil-C のメモリ安全性には 性能コスト が伴う
    • 失われた性能を一部取り戻すためのさまざまな手法を適用できる余地がある

Fil-C の利用場面

  • 大規模な C/C++ コードが一見動作していても メモリ安全性の検証 がなく、メモリ安全性のために GC 導入と大きな性能低下を受け入れられる場合に利用できる
    • Java、Go、Rust への書き換えまでの暫定措置としての可能性に言及
  • ASan のようにメモリバグ検出を目的として Fil-C を実行することもできる
    • C/C++ コードを Fil-C の下で実行してメモリバグを確認できる
  • コンパイル時言語とランタイム言語が同じで、コンパイル時安全性が強い言語では、安全なコンパイル時計算 の用途もありうる
    • 例として Zig に言及
    • ランタイム評価が安全でなくても、コンパイル時評価には Fil-C 構成を使える
  • pointer provenance を扱う具体的なシステム事例としての意味もある
    • p1 と p2 の型が同じとき、if (p1 == p2) { f(p1); } を if (p1 == p2) { f(p2); } に変える最適化が可能か、という問いを提示
    • Fil-C では f に渡される AllocationRecord* が異なるため、答えは明確に不可能だと述べる
    • この点で Fil-C は pointer provenance を持つ具体的システムの一例となる

関連記事

1件のコメント

 
GN⁺ 10 일 전
Hacker News のコメント
  • invisicaps を chibicc や slimcc のようなものに付けてみるのは、かなり面白い実験になりそう 参照カウントや invisible capability system の派生形を試す余地もあるし、少しの間接参照コストと引き換えにメモリを節約できるかもしれない
  • 私は filc-bazel-template を作って、Bazel target としてまとめておいた これらを一緒に使って hermetic builds を作りたい人の役に立てばと思う
  • この文の意味がよくわからない Upon freeing an unreachable AllocationRecord, call filc_free on it. 私の理解では、言いたいのは到達不能な AR を解放する前に、visible_bytes と invisible_bytes フィールドが指しているメモリを先に解放しろ、ということだと思う
  • 私にとって Fil-C は、これまで見てきたプロジェクトの中でも特に過小評価されている部類に入る 安全性のために「rewrite it in Rust」と言うより、既存の C プログラムを完全にメモリ安全にコンパイルできるという点のほうがずっと興味深い
    • いくつかは合わせて見る必要があると思う 第一に、Fil-C は より遅く、より大きい。それで構わないのなら、この10年は Rust より先に Java や C# に移行していてもよかった、という話にもなる 第二に、それでもなお C を使っている。既存コードの保守にはよいが、新しいコードをたくさん書くなら私は Rust のほうがはるかに快適 だと感じる 第三に、Fil-C はランタイム安全性であり、Rust はその一部をコンパイル時に表現できる。さらに WUFFS のような言語は、ランタイムチェックなしでコンパイル段階に安全性を証明しようとするので、コードに論理的な誤りはあり得ても、クラッシュや任意コード実行は防ぐという点で方向性が違う
    • 私はここで過小評価されているとは思わない。すでにかなり多くの議論があった Fil-Qt: A Qt Base build with Fil-C experience, Linux Sandboxes and Fil-C, Ported freetype, fontconfig, harfbuzz, and graphite to Fil-C, A Note on Fil-C, Notes by djb on using Fil-C, Fil-C: A memory-safe C implementation, Fil's Unbelievable Garbage Collector といったスレッドがあった
    • 私が見る Fil-C の最大の限界は、runtime memory safety だという点だ 依然としてメモリ安全でないコードを書くことはできるし、その結果が脆弱性ではなく確実なクラッシュになる、という意味合いに近い 信頼できない入力を受け取る Web API のようなものを作るなら、こうした問題は結局 denial-of-service につながり得るので、改善ではあっても十分に良いとは言いにくい Fil-C の取り組み自体を貶したいわけではなく、ランタイムのアプローチには明確な限界があると思う
    • 関心を持ってくれてありがとう ただ、公平に言うと Fil-C は Rust よりかなり遅く、メモリ使用量も多い 一方で Fil-C は safe dynamic linking をサポートしていて、ある面では Rust より厳密に安全だと言うこともできる 結局はトレードオフなので、それぞれの状況に応じて選べばよいと思う
    • 私の感覚では、C/C++ プログラマに自分のプログラムへ garbage collector を付けられると言っても、目を輝かせる人はあまりいない だからこのアイデアは技術的には興味深くても、感情的には受け入れられにくいのだと思う
  • 私の見るところ、Fil-C は data race の状況ではメモリ安全ではない capability と pointer の値が代入中に引き裂かれる可能性があり、スレッドのインターリーブが悪いと誤ったポインタでオブジェクトにアクセスして 任意の誤動作 が起こり得る こうした限界自体は受け入れられるが、この問題を指摘する人たちに対して支持者までもが強く攻撃的になる雰囲気は残念に感じる
    • 私の知る限り、その部分は atomic ops を使って処理している 残念ながら、それがオーバーヘッドの大きな原因の一つでもある
  • 私には、これは結局 fat pointers 系の手法の別バリエーションに見える この種の方式は、セキュリティ保証が不十分だったり、non-fat ABI boundaries をまたぐのが難しかったり、オーバーヘッドが大きかったりする理由で、何度も実装されては退けられてきた
    • とはいえ最近は fat pointers をハードウェアが直接サポート する流れが再び出てきているので、早計に切り捨てるべきではないのかもしれない しかも filc は単なる fat pointer だけでは説明できないと思う
    • すでに複数のプラットフォームで hardware memory tagging が提供されている点も考慮すべきだと思う