How to Shadow Every Byte of Memory Used by a Program

valgrind の shadow values の実装に関する論文 How to Shadow Every Byte of Memory Used by a Program を読んだので、まとめておく。

• memcheck
  • shadow values を表現するために以下のデータを持つ。
    • A (Addressability) bit
      • そのアドレスが有効であるかどうかを示す。1 バイトにつき 1 ビットで表現される。
    • V (Validity) bit
      • そのアドレスの各ビットが初期化済かどうかを示す。1 ビットにつき 1 ビットで表現される。
  • 確保されたそれぞれのヒープ領域はハッシュテーブルで管理されている。

• データ構造
  • ページ単位で管理する。1 ページには 64KB 分の A/V bit が保存される。
  • PM (Primary Map) と呼ばれる配列は各ページを表現する SM (Secondary Map) へのリンクを保持する。
  • A bit が 0 (すなわち有効でないアドレス) である場合は V bit は意味を持たないため、そのようなページは PM からのリンクが共有される。
  • A/V の操作はビット演算でおこなわれる。
  • A bit が 0 である場合はエラーにする。

• shadow values
  • 以下の状態のいずれかである。(A/V ビットとは別に一般的な話)

状態	発生させる関数
NOACCESS	free
UNDEFINED	malloc
DEFINED	calloc

• • システムコールに渡す領域もチェックする。
  • バギーなプログラムが shadow values を破壊する危険性がある。
    • NOACCESS な領域とすることで対応している。
    • x86 だとセグメントレジスタが使えたけど、移植性の問題から取り除いた。
    • プログラムよりも遠くのアドレスに置くことで破壊の危険性を減らす。
  • 64 bit 対応
    • テーブルの段数を増やす。
  • マルチスレッド対応
    • 実際のデータと shadow values の更新は atomic にする。

• 改善案
  • 4 バイトアラインされている場合はベクトル化。
    • 4 バイトアラインされていない場合は従来と変わらないため、遅くなることはない。
  • SP (Stack Pointer) の高速な更新
    • 固定バイト数であることが多いためにアンロール済の memset 的な関数を使う。
  • VA bits を従来の A/V bits の代わりに使用する。1 バイトにつき 2 ビットで以下の状態を表現する。

状態	意味
NOACCESS	不正なアドレス
DEFINED	すべてのビットが初期化済
UNDEFINED	すべてのビットが未初期化
PARTDEFINED	一部のビットのみが初期化済

• • PARTDEFINED の場合のみ V bit を持つするようにすることでメモリ使用量を削減する。
  • V bit のテーブルは AVL 木で管理する。
    • 更新によって、すべての V bit が DEFINED or UNDEFINED になると、V bit テーブルの存在が冗長となるため、GC するべきである。
    • しかし、V bit のテーブルは近い将来に再度更新される可能性もあるので、すぐに GC すべきではないとも考えられることから、3 回 GC される間に更新がなかったら、GC するものとする。
  • PARTDEFINED の時の処理は従来よりも遅くなるが、全体では高速化できる。
  • ROM への書き込みは検出しない。
    • 状態が増えると VA bits ã‚’ 3 ビットにしないといけなくなる。
    • どうせ ROM への書き込みは SIGSEGV 発生となるため、わざわざ検出できても、それほどうれしくない。

• 他のツールの手法
  • shadow values を決められたオフセットだけずれたアドレスに置くことで shadow values の計算を簡略化する。
  • V bit ã‚’ 1 バイトにつき 1 ビットだけにする。