C や C++ を書いて -fsanitize=address でコンパイルしたことがあれば、AddressSanitizer (ASan) を使ったことになります。コンパイルして実行すると、バッファオーバーフロー、use-after-free、use-after-scope、double-free などのバグを捕まえ、どのバイトがどこからアクセスされたかを正確に診断します。ランタイムオーバーヘッドはだいたい 2 倍で、得られるものを考えれば驚くほど小さいです。

魔法は 2 つの半分で起きます: 全ロード、ストア、alloca を計装する コンパイラパス と、シャドウメモリを管理してレポートを印字する ランタイムライブラリ（compiler-rt の一部）。この記事はコンパイラパスについて — どんな IR を書き換え、なぜかです。

行番号は全て llvm/lib/Transforms/Instrumentation/AddressSanitizer.cpp のもの。テストケースは llvm/test/Instrumentation/AddressSanitizer/ 下に住んでいます。

大きなアイデア: シャドウメモリ

ASan の中心的なトリックは シャドウメモリ です。プログラムのアドレス可能メモリ 8 バイトごとに、ASan はどこか別の場所に 1 バイトのシャドウ状態を保ち、「これら 8 バイトのうち何バイトが現在アクセス可能か」を記録します。

マッピングは計算が自明です:

shadow_address = (app_address >> 3) + ShadowOffset

アドレスを 3 ビット右シフト（8 で割る）し、プラットフォーム固有のオフセットを足せば、シャドウバイトに到達します。オフセットは、シャドウ領域が未使用の仮想アドレス空間に収まるように選ばれます。Linux x86_64 では 0x7fff8000、AArch64 では 1 << 36 などです（定数は AddressSanitizer.cpp:99-127）。

シャドウバイトの値は、対応する 8 バイトのアプリメモリがアクセス可能かをエンコードします:

計装された全てのロードとストアはメモリにアクセスする前にシャドウバイトをチェックします。非ゼロなら、ASan はランタイムを呼んでバグを報告します。

ロードとストアの計装

ロード/ストア計装のエントリポイントは instrumentMop（AddressSanitizer.cpp:1778-1852）で、instrumentAddress（AddressSanitizer.cpp:1947-2027）に委譲します。擬似コードで、出力される IR は次のようになります:

; オリジナル:
%tmp1 = load i32, ptr %a, align 4

; 計装後:
%0 = ptrtoint ptr %a to i64
%1 = lshr i64 %0, 3           ; 8 で割る
%2 = add i64 %1, 2147450880   ; シャドウオフセット加算
%3 = inttoptr i64 %2 to ptr
%4 = load i8, ptr %3, align 1 ; シャドウバイトロード
%5 = icmp ne i8 %4, 0         ; 高速パスチェック
br i1 %5, label %crash_block, label %ok, !prof !0

crash_block:
  ; 低速パス洗練: 特定のアクセス範囲が実際にポイズンされているか?
  %7 = and i64 %0, 7           ; 8 バイトチャンク内のバイトオフセット
  %8 = add i64 %7, 3           ; 最後のアクセスバイト (size - 1 = 3 for i32)
  %9 = trunc i64 %8 to i8
  %10 = icmp sge i8 %9, %4
  br i1 %10, label %report, label %ok

report:
  call void @__asan_report_load4(i64 %0)
  unreachable

ok:
  %tmp1 = load i32, ptr %a, align 4

起きていること:

  1. シャドウアドレス計算（memToShadow、AddressSanitizer.cpp:1405-1419）。アプリアドレスを整数に変換、Mapping.Scale（デフォルト 3）だけ右シフト、Mapping.Offset を加算。一部プラットフォームでは、オフセットがシフトと整列する 2 のべき乗なら ADD の代わりに OR が使われます。

  2. 高速パス。シャドウバイトをロードしてゼロと比較。シャドウが完全にゼロなら、全 8 バイトがアドレス可能で、実際のロードに直進します。これが共通ケース — ほとんどのメモリは有効 — で高速です: 余分なロード 1 つ、比較 1 つ、分岐 1 つ。

  3. 低速パス洗練。シャドウが非ゼロなら、特定の アクセスがポイズンされたバイトに重なるかをチェックする必要があります。シャドウバイトが「最初の 5 バイトのみアドレス可能」（値 5）と言い、アクセスが最初の 4 バイトなら問題ありません。洗練ロジック（createSlowPathCmp、AddressSanitizer.cpp:1883-1899）は 8 バイトチャンク内のアクセスのオフセットを計算し、シャドウ値と比較します。

  4. レポート。洗練が本当の違反を確認したら、適切なランタイム関数を呼ぶ。アクセスサイズごとに専用レポータ（__asan_report_load1, __asan_report_load2, __asan_report_load4, __asan_report_load8）と、奇数サイズ用の汎用版（__asan_report_load_n）があります。

分岐重みメタデータ（例の !0、AddressSanitizer.cpp:2009 で発行）は CPU 分岐予測器に高速パスが圧倒的に可能性が高いと伝えます — レポートパスはおおよそ 2²⁰ 回に 1 回。これがないと予測器が悪く投機し、性能が崩壊します。

なぜ 8:1 で 1:1 でないのか

素朴な実装はアプリバイトごとに 1 シャドウ ビット を使うでしょう。なぜアプリメモリ 8 バイトに対してシャドウ 1 バイトなのか？

バイトはほとんどのアーキテクチャが 1 命令でロードできる最小単位です。アプリ 8 バイトごとに単一シャドウバイトは、計装がバイトロードであってビット抽出でないことを意味します。チェックが高速です。トレードオフは、シャドウが「8 バイト粒度でアドレス可能かどうか」しか言えないこと — 粗すぎて小さな範囲外アクセスを見逃すはずです。だからシャドウは 同時に 「N バイトアドレス可能」もエンコードし、境界ケースで 8 バイト以下の粒度を保持します。

このエレガントなエンコーディング — シャドウ 1 バイト、整数値 0..7 は「最初の N が OK」、大きな値はポイズン — が、高速パスを自明に保ちつつバイトレベルのエラーも捕まえる秘訣です。

スタックの計装

スタック計装は FunctionStackPoisoner（AddressSanitizer.cpp:1063-1290）が行います。その仕事: 関数の全 alloca を 1 つの連続フレームにパックし、レッドゾーン を間に挿入し、それらのレッドゾーンをポイズンして変数間のオーバーフローを捕まえる。

入力はこうかもしれません:

%a = alloca [10 x i8]
%b = alloca [20 x i8]
%c = alloca [30 x i8]

計装後:

; 全てを 1 つにパックしたフレーム、32 バイト（レッドゾーンサイズ）にアライン
%MyAlloca = alloca i8, i64 192, align 32

; MyAlloca 内のレイアウト:
;   [ 32 bytes header (metadata)       ]
;   [ 10 bytes data for %a             ]
;   [ 22 bytes RED ZONE (poisoned)     ]
;   [ 20 bytes data for %b             ]
;   [ 12 bytes RED ZONE                ]
;   [ 30 bytes data for %c             ]
;   [ 30 bytes RED ZONE                ]
; = 32 + 10 + 22 + 20 + 12 + 30 + 30 = 156 (切り上げ)

; 関数エントリ時: レッドゾーンのシャドウをポイズン
store i64 <poison pattern>, ptr %shadow_ptr

; 各元 alloca を MyAlloca への GEP で置換
%a = getelementptr inbounds i8, ptr %MyAlloca, i32 32
%b = getelementptr inbounds i8, ptr %MyAlloca, i32 64
%c = getelementptr inbounds i8, ptr %MyAlloca, i32 96

; 関数エグジット時: アンポイズン
store i64 0, ptr %shadow_ptr
ret void

レッドゾーンサイズ定数は kAllocaRzSize = 32（AddressSanitizer.cpp:187）。各元 alloca はその倍数までパディングされ、変数の末尾を超えて歩くと即座にポイズンされたレッドゾーンに着地し、ランタイムが捕まえます。

1 つの alloca へのパッキングは ComputeASanStackFrameLayout（AddressSanitizer.cpp:3579 で呼ばれる）で行われます。ポイズン/アンポイズンパターンを書く関数は poisonAlloca（AddressSanitizer.cpp:3812-3820）:

void FunctionStackPoisoner::poisonAlloca(Value *V, uint64_t Size,
                                         IRBuilder<> &IRB, bool DoPoison) {
  Value *AddrArg = IRB.CreatePointerCast(V, IntptrTy);
  Value *SizeArg = ConstantInt::get(IntptrTy, Size);
  RTCI.createRuntimeCall(
      IRB, DoPoison ? AsanPoisonStackMemoryFunc : AsanUnpoisonStackMemoryFunc,
      {AddrArg, SizeArg});
}

ポイズニングはシャドウメモリにマーカーパターンを書き込み、アンポイズニングはゼロを書き込みます。両方ともランタイム経由なので、ランタイムは自身の簿記を同期できます。

ライフタイムマーカーと use-after-scope

ASan は llvm.lifetime.start と llvm.lifetime.end intrinsic にも耳を傾けます。これらは変数がレキシカルスコープに入るまたは出るときに Clang が出します:

{
  int a;           // llvm.lifetime.start(%a)
  use(a);
  // llvm.lifetime.end(%a)
}
use(a);            // スコープ外使用!

lifetime.start で ASan は変数のバイトをアンポイズン。lifetime.end で再びポイズン。スコープ外でのその変数へのロードやストアはポイズンシャドウにヒットして報告されます。これが ASan が use-after-scope バグを捕まえる仕組みです。

グローバル

グローバル変数は ModuleAddressSanitizer::instrumentGlobals（AddressSanitizer.cpp:990）が扱い、モジュールごとに 1 回走ります。各グローバルはレッドゾーンでパディングされ、コンパイラが起動時にランタイムにメタデータを登録し、ランタイムはレッドゾーンをポイズンとマークします。

登録はモジュールコンストラクタ経由で起きます:

define internal void @asan.module_ctor() {
  call void @__asan_init()
  call void @__asan_register_elf_globals(i64 ptrtoint (...), ...)
}

define internal void @asan.module_dtor() {
  call void @__asan_unregister_elf_globals(...)
}

ELF、Mach-O、COFF にはそれぞれ若干異なる機構があり、プラットフォーム固有のセクションとメタデータ形式を持ちます。原理は同じ: コンパイラがテーブルを出し、コンストラクタがそれをランタイムに伝え、ランタイムがレッドゾーンをポイズンする。

ランタイムインタフェース

ASan のランタイム関数は全て __asan_ で始まります。コンパイラパスはそれらへの呼び出しを出し、リンカは compiler-rt の ASan 実装に対して解決します。最も一般的なもの:

ロード/ストアチェック（高速パスコールバック、-fsanitize-address-use-after-scope-callback=1 時）:

エラー報告（低速パス）:

スタックライフタイム:

グローバル:

その他:

プレフィックスは -asan-memory-access-callback-prefix で設定可能ですが、実際の ASan ビルドが全て使うデフォルトは __asan_ です。

完全な実例

開始 IR:

define i32 @test_load(ptr %a) sanitize_address {
entry:
  %tmp1 = load i32, ptr %a, align 4
  ret i32 %tmp1
}

opt -passes=asan 実行後:

define i32 @test_load(ptr %a) #0 {
entry:
  %0 = ptrtoint ptr %a to i64
  %1 = lshr i64 %0, 3
  %2 = add i64 %1, 2147450880
  %3 = inttoptr i64 %2 to ptr
  %4 = load i8, ptr %3, align 1
  %5 = icmp ne i8 %4, 0
  br i1 %5, label %6, label %12, !prof !0

6:
  %7 = and i64 %0, 7
  %8 = add i64 %7, 3
  %9 = trunc i64 %8 to i8
  %10 = icmp sge i8 %9, %4
  br i1 %10, label %11, label %12

11:
  call void @__asan_report_load4(i64 %0) #4
  unreachable

12:
  %tmp1 = load i32, ptr %a, align 4
  ret i32 %tmp1
}

attributes #0 = { sanitize_address }
!0 = !{!"branch_weights", i32 1, i32 1048575}

単一の 4 バイトロードがおよそ 10 個の新命令プラス基本ブロック分割になりました。ロードごとのオーバーヘッドは小さくないですが:

経験的に ASan 有効コードはネイティブ速度の 40〜60% で走り、挿入されるチェック数を考えれば驚くべきことです。

なぜ選択的にオフにできないか

たまに見る質問: 「失敗し得るロードだけ計装できないか？」。答えは no、少なくとも最適化パス内からは。計装が走ると、ロード/ストアパターンは後続パスには不透明で、特定のアクセスを un-calibrate できません。ASan には 最適化 として、証明可能に安全なアクセスの計装をスキップするもの（isSafeAccess、instrumentMop 参照）があります — 通常は既知サイズのローカルへの範囲内定数インデックスでのアクセス。これはコンパイラが証明できるものに基づいたコンパイル時スキップです。しかし他の全アクセスは計装されます、サニタイザの要点はコンパイラが予見できなかったバグを捕まえることだからです。

ASan が捕まえないもの

完全性のため: ASan のシャドウモデルは空間エラー（バッファオーバーフロー、use-after-free、use-after-scope）と double-free には優れていますが、次は捕まえません:

各サニタイザは自身の計装パスを持ち、インフラの一部（Instrumentation ディレクトリ）を共有しますが、それ以外は独立です。

結び

AddressSanitizer は、私にとって、モダンツールチェーンの最も美しいエンジニアリング作品の 1 つです。シャドウメモリのアイデアは抽象的には素直ですが、各詳細 — 8:1 マッピング、部分有効性のバイトエンコーディング、高速パス/低速パス分岐、スタックフレームパッキング、ライフタイムマーカー統合 — は性能、正しさ、デバッガビリティについて非常に慎重に考えた結果です。それが全て 1 ファイル、プラスランタイムライブラリ、プラス 20 年分のバグ修正に収まっています。

ソースを読みたくなったら: instrumentMop（AddressSanitizer.cpp:1778）から始めて、instrumentAddress と memToShadow を通る呼び出しチェーンを辿ってください。次にスタック側を見るため FunctionStackPoisoner::runOnFunction（AddressSanitizer.cpp:1111）をざっと見る。テストディレクトリ llvm/test/Instrumentation/AddressSanitizer/basic.ll が、理解を照合する「期待出力」を与えてくれます。

次に読むもの