AddressSanitizer の内部実装を読む 1 〜概要・論文編

はじめに

基礎技術研究部の末吉です。

バグを検知するツールにサニタイザー(Sanitizer)というものがあります。英語で Sanitizer は「消毒剤」という意味で、Hand Sanitizer なら手指消毒剤を意味します。ここで紹介するサニタイザーは、菌の代わりにバグを消毒してくれます。

サニタイザーは通常、GCC などのコンパイラに付属していて、コンパイル時にアプリケーションにバグの検知・報告機構を計装(instrument)します。そしてアプリケーションの実行中にバグの発生を検知したらバグの調査に有用な情報を出力してアプリケーションを終了させます。

ここではサニタイザーの中でもおそらく最もよく使われているであろう AddressSanitizer(ASan) について複数回にわたって説明することとし、今回はその仕組みについてその源流である Google の発表した論文を読んでいきます。次回の記事では Clang(LLVM) ではどのように実装されているか、ソースコードを読んでいきます。

使い方

サニタイザーについて色々御託を並べるより使ったほうが理解しやすいので使い方から説明します。

本記事での環境は以下の通りです。Clang, GCC は sudo apt install clang, gcc ですぐインストールできるものを使用しています^*1。

OS: Ubuntu 22.04 LTS
Clang: 14.0.0-1ubuntu1.1
GCC: 11.4.0-1ubuntu1~22.04

試しに以下のプログラム test1.c をコンパイルして動かしてみましょう。第一引数に入った文字列を buf にコピーして表示するだけのプログラムです。

#include <stdio.h>

int main(int argc, char** argv){
    char buf[8];
    int i;

    if(argc <= 1){
        printf("%s <input>\n", argv[0]);
        return 0;
    }

    printf("argv[1]=%s\n", argv[1]);
    for(i = 0; argv[1][i] != '\0'; i++) buf[i] = argv[1][i];
    buf[i] = '\0';
    printf("buf=%s\n", buf);

    return 0;
}

まずは、普通に Clang でコンパイルしてみます。GCC でも構いません。

$ clang test1.c
$ # gcc test1.c # GCC でも可

早速実行してみましょう。

$ ./a.out
./a.out <input>
$ ./a.out aaaa     # a を 4 文字
argv[1]=aaaa
buf=aaaa
$ ./a.out aaaaaaa  # a を 7 文字
argv[1]=aaaaaaa
buf=aaaaaaa
$ ./a.out aaaaaaaa # a を 8 文字
argv[1]=aaaaaaaa
buf=aaaaaaaa

ちゃんと実行できていそうです。特に問題は見当たりません。

次は、サニタイザーの 1 つである AddressSanitizer(ASan) 付きでコンパイルしてみましょう。 ASan はメモリ系のバグを検知するサニタイザーです。 ASan 付きでコンパイルするには -fsanitize=address オプションをつけます。 GCC, Clang どちらもこのオプションが使えます。

$ clang -fsanitize=address test1.c
$ # gcc -fsanitize=address test1.c # GCC でも可

では早速実行してみましょう。

$ ./a.out
./a.out <input>
$ ./a.out aaaa     # a を 4 文字
argv[1]=aaaa
buf=aaaa
$ ./a.out aaaaaaa  # a を 7 文字
argv[1]=aaaaaaa
buf=aaaaaaa

ここまでは先ほどと全く同じで、特に問題なく実行できていそうです。さて、a を 8 文字入力して実行してみると、見るからにただ事ではないメッセージが怒涛の勢いで表示されます。

$ ./a.out aaaaaaaa # a を 8 文字
argv[1]=aaaaaaaa
=================================================================
==33806==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7ffe3f6abe28 at pc 0x5599d10021d1 bp 0x7ffe3f6abdf0 sp 0x7ffe3f6abde8
WRITE of size 1 at 0x7ffe3f6abe28 thread T0
    #0 0x5599d10021d0 in main (/home/user/a.out+0xdc1d0) (BuildId: 23ae16e22d9c7a5c355e1a54678f263f18563e96)
    #1 0x7f3078e29d8f in __libc_start_call_main csu/../sysdeps/nptl/libc_start_call_main.h:58:16
    #2 0x7f3078e29e3f in __libc_start_main csu/../csu/libc-start.c:392:3
    #3 0x5599d0f44304 in _start (/home/user/a.out+0x1e304) (BuildId: 23ae16e22d9c7a5c355e1a54678f263f18563e96)

Address 0x7ffe3f6abe28 is located in stack of thread T0 at offset 40 in frame
    #0 0x5599d1001eaf in main (/home/user/a.out+0xdbeaf) (BuildId: 23ae16e22d9c7a5c355e1a54678f263f18563e96)

  This frame has 1 object(s):
    [32, 40) 'buf' <== Memory access at offset 40 overflows this variable
HINT: this may be a false positive if your program uses some custom stack unwind mechanism, swapcontext or vfork
      (longjmp and C++ exceptions *are* supported)
SUMMARY: AddressSanitizer: stack-buffer-overflow (/home/user/a.out+0xdc1d0) (BuildId: 23ae16e22d9c7a5c355e1a54678f263f18563e96) in main
Shadow bytes around the buggy address:
  0x100047ecd770: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x100047ecd780: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x100047ecd790: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x100047ecd7a0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x100047ecd7b0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x100047ecd7c0: f1 f1 f1 f1 00[f3]f3 f3 00 00 00 00 00 00 00 00
  0x100047ecd7d0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x100047ecd7e0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x100047ecd7f0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x100047ecd800: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x100047ecd810: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
==33806==ABORTING

このメッセージでは、ASan がスタックバッファオーバーフロー(1 バイト書き込み)を検知した、と言っています。 ASan はこのように、バグを検知するとそのタイミングでスタックトレースや周辺のシャドウメモリ(後述)状況などを記したレポートを出力してアプリケーションを終了させます。スタックトレースの a.out に該当する部分はアドレスしか書かれていませんが、コンパイル時に -g オプションをつけてシンボルを含めておくと、レポートにもシンボルが反映されてソースコードのどの行でバグが発生したかわかりやすくなります。

$ clang -g -fsanitize=address test1.c # シンボル付きでコンパイル

$ ./a.out aaaaaaaa
argv[1]=aaaaaaaa
=================================================================
==34111==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7ffeafe74e48 at pc 0x561233c761d1 bp 0x7ffeafe74e10 sp 0x7ffeafe74e08
WRITE of size 1 at 0x7ffeafe74e48 thread T0
    #0 0x561233c761d0 in main /home/user/test1.c:14:12
    #1 0x7f80dbe29d8f in __libc_start_call_main csu/../sysdeps/nptl/libc_start_call_main.h:58:16
    #2 0x7f80dbe29e3f in __libc_start_main csu/../csu/libc-start.c:392:3
    #3 0x561233bb8304 in _start (/home/user/a.out+0x1e304) (BuildId: 59e081ab354a7b54bcfc9e3d4cd5a0efe7dae767)

Address 0x7ffeafe74e48 is located in stack of thread T0 at offset 40 in frame
    #0 0x561233c75eaf in main /home/user/test1.c:3

  This frame has 1 object(s):
    [32, 40) 'buf' (line 4) <== Memory access at offset 40 overflows this variable
HINT: this may be a false positive if your program uses some custom stack unwind mechanism, swapcontext or vfork
      (longjmp and C++ exceptions *are* supported)
SUMMARY: AddressSanitizer: stack-buffer-overflow /home/user/test1.c:14:12 in main
Shadow bytes around the buggy address:
(...省略...)

どうやら test1.c の 14 行目でスタックバッファオーバーフローが発生したようです。バグの原因は 13 行目で buf のサイズを考慮せずに argv[1] のデータをコピーしたせいで、14 行目で buf[8] にヌル文字を代入しようとしてオーバーフローしたことです。

バッファオーバーフローなどのメモリ破壊系バグは命令ポインタを不正なものに変化させたりしなければバグ発生の兆候(クラッシュ等)が現れず、気付けません。しかしながら上記のようなたった 1 バイトのオーバーフローでも深刻な脆弱性に繋がる危険もあり、見逃すと大事になりかねません。また、この手のバグはクラッシュが起きたとしても、バグの発生タイミングとクラッシュの発生タイミングが別であるために根本原因の解析が困難なことも多々あります。

ASan が無いと a を 8 文字入力した場合は特に何も起こらず、オーバーフローの発生に気付けません。ですが ASan を使用すると、発生時に検知してレポートしてくれます。 ASan はこのような見つけづらいバグの発見、修正を補助してくれます。

サニタイザーは ASan 以外にも色々な種類があり、それぞれ適用対象や検知できるバグが異なります。よく知られているものとして、未初期化変数の使用を検知する MemorySanitizer(MSan), 未定義動作を検知する UndefinedBehaviorSanitizer(UBSan), スレッド間の競合を検知する ThreadSanitizer(TSan) などがあります。これらの派生サニタイザーも多く存在し、例えば QEMU 上で動的に ASan を計装できるようにした QASan などがあります。

ただし欠点もあります。サニタイザーは数倍パフォーマンスを低下させ、余分なメモリを使用します。そのため、stack canary などのように本番環境で動かす脆弱性防御機構としては使えません。その代わり、テスト段階でバグを探す時に有用です。

まとめると、サニタイザーにはパフォーマンス低下、メモリ使用量の増加などの欠点はありますが、バグ探しと修正においてそれを大幅に上回る利点が存在します。また、主要なコンパイラに付属していて簡単に利用できる点、大規模なコードベースでも適用可能な点、誤検知の少なさもあって様々なプロジェクトで使用されています。

AddressSanitizer: A Fast Address Sanity Checker

2012 年に Google が AddressSanitizer: A Fast Address Sanity Checker という論文を発表しました。これがサニタイザーシリーズの源流です。

サニタイザーのコードは sanitizers リポジトリで公開後、LLVM 本体に組み込まれました。それ以降 LLVM のリポジトリでコードを管理し、このリポジトリはサニタイザーに関する情報を管理しています。 sanitizers の Wiki(以降、Wiki と言った場合これを指します)ではサニタイザーの実装やアルゴリズムなどが書かれています。なお、ASan の最初のコードはこのリポジトリの過去のコミットを遡れば見られます。今の LLVM の ASan コードと比べれば機能が少ないので非常にシンプルです。

ここでは論文から、ASan のバグ検知機構の基礎であるシャドウメモリ、レッドゾーン、ランタイムライブラリについて解説します。今の ASan は論文当時よりも大きく進化していますが、この基礎は変わっていません。

シャドウメモリ

注) 以下ではアドレス不可領域(unaddressable region)とアクセス不可領域(inaccessible region)という用語が登場します。この 2 つは意味が異なるため注意してください。アドレス不可領域は、そのアドレスのメモリへのアクセス(値の読取/書込/実行のいずれか)自体は可能ですが、バグが無ければ本来アクセスされないはずの領域です。アクセス不可領域は、そのアドレスのメモリへのアクセスが禁止されていて、アクセスが発生すると Access Violation が発生する領域です。なお、アドレス可能領域とアクセス可能領域は同義として扱っています。

ASan は仮想アドレス空間内の各アドレスのアドレス可否制御をシャドウメモリ(shadow memory)と呼ばれる領域に格納します。シャドウメモリは仮想アドレス空間内の一部の領域に確保されます。

ヒープを確保する malloc 関数は、少なくとも 8 バイトアライメントされた領域のアドレスを返します。この領域は、最初の k バイト(0 <= k <= 8) はアドレス可能ですが、残りの 8 - k バイトはアドレス不可という仕様になります。

すなわち、×××○○○○○ はありえますが、×××○×○○○ のような飛び地や、○○○○○××× のような、最初の k バイトはアドレス不可で残りの 8 - k バイトはアドレス可能とはなりません。よって、malloc で確保した領域のアドレス可否パターンは、全て可から全て不可までの 9 通りだけです。

ASan はこの性質を利用して、8 バイトのアドレス可否制御を 1 バイトのシャドウメモリに割り当てます。 1 バイトのうちのアドレス可否制御に使わない残りのビットには検知時の追加情報を格納します。この場合、仮想アドレス空間全体をアドレス可否制御するシャドウメモリは、全体の 8 分の 1 を割り当てることになります。

そうして仮想アドレス空間の 8 分の 1 がシャドウメモリに割り当てられ、そのベースアドレスはプラットフォームによって異なるアドレスに確保されます。シャドウメモリのアドレス自体に対応するシャドウメモリを取得する挙動が起きた場合はバグの発生を意味します。そのため、シャドウメモリのシャドウメモリ領域は禁止領域(bad region)としてページ保護(page protection)機能を用いてアクセス不可領域とします。この禁止領域は必ずシャドウメモリの中にできます。そのため、シャドウメモリは禁止領域を挟んで 2 つ作成されます。

アプリケーションの仮想アドレス Addr に対応するシャドウメモリアドレスは、 (Addr >> Scale) + Offset で取得できます。 Offset はシャドウメモリのベースアドレスです。この値はアプリケーション実行時に占領されないアドレスの必要があるため、プラットフォーム毎に異なります。 Scale は、1 バイトのシャドウメモリが何バイトの仮想アドレスを制御するかの粒度です。この例では 8 バイトを 1 バイトで制御しているので、Scale を 3 にすることで Addr を 8 で割り、シャドウメモリの 1 ビットが仮想メモリの 1 バイトを制御します。

なお、論文では禁止領域によって分割されたシャドウメモリを区別していませんが、Wiki では低位側をローシャドウ(low shadow)、高位側をハイシャドウ(high shadow)、禁止領域をシャドウギャップ(shadow gap)と呼んでいます。 Clang や GCC もこれにならって呼んでいます。本記事では論文にしたがって低位と高位をまとめてシャドウメモリと呼び(どちらにせよこの論文中で区別する必要はありません)、禁止領域はそのまま禁止領域と呼ぶこととします。次回以降の記事では、必要に応じてローシャドウ、ハイシャドウという用語を使用し、禁止領域はシャドウギャップと呼びます。

レッドゾーン

以下の関数を考えます。(Wiki より引用)

void foo() {
  char a[8];
  ...
  return;
}

ASan を計装すると、変数 a の領域の前後にレッドゾーン(redzone)と呼ばれる領域が確保されます。このレッドゾーンはアドレス不可領域であり、このレッドゾーンへのアクセスが発生した場合、バグが発生したとみなします。

C のコードで表現すると、以下のような感じになります。(Wiki より引用)

なお、「ポイズン(poison)する」とは、その領域をアドレス不可領域として指定するという意味です。

void foo() {
  char redzone1[32];  // レッドゾーン(32 バイトアライメント)
  char a[8];          // 元の変数
  char redzone2[24];  // a の 8 バイトと合わせて 32 バイトアライメントにしている
  char redzone3[32];  // レッドゾーン
  int  *shadow_base = MemToShadow(redzone1);  // redzone1 に対応するシャドウメモリのアドレスを取得
  shadow_base[0] = 0xffffffff;  // redzone1 をポイズンする
  shadow_base[1] = 0xffffff00;  // redzone2 をポイズンし、a はポイズンしない
  shadow_base[2] = 0xffffffff;  // redzone3 をポイズンする
  ...
  shadow_base[0] = shadow_base[1] = shadow_base[2] = 0; // 関数から出るときにスタック領域のポイズンを解除する
  return;
}

redzone がレッドゾーン、shadow_base がシャドウメモリへのポインタを示します。特定のアドレスをレッドゾーンに指定するには、そのアドレスに対応するシャドウメモリを書き換えます。上記の 8 行目では、関数に入ったときに a に対応するシャドウメモリを 0x00 にして a の領域はアドレス可能とし、周囲の redzone は 0xff にしてアドレス不可にします。

そうすることで、a がオーバーフローして redzone へのアクセスが発生した場合、これを検知します。

関数から出る時はスタックが解放されるため、関数内で設定した shadow_base をゼロクリアしてレッドゾーンをアドレス可能領域に戻しておきます。そうしないとこの領域を再び使用するときに誤検知されてしまいます。

ランタイムライブラリ

ASan を適用したアプリケーションは、実行時に計装された ASan のランタイム処理を実行します。

アプリケーション起動時にシャドウメモリを予約して他の処理が使用しないようにし、禁止領域をアクセス不可に設定します。

また、malloc と free 関数を ASan の関数に置き換えてヒープを監視します。

ASan 仕様の malloc は、確保したヒープチャンクの前後にレッドゾーンを配置します。ヒープのメタデータが入っているチャンクヘッダーはレッドゾーンの領域を一部借りて作られます。チャンクヘッダーがレッドゾーンを間借りする都合上、ヘッダーを包み込める 32 バイトがレッドゾーンの最小サイズ(アラインメント)になっています。

ASan 仕様の free 関数は、解放するメモリ領域全体をポイズンおよび隔離し、malloc によってすぐに再割り当てされないようにします。この隔離は FIFO キューで保持しており、一定量のメモリを隔離しています。

また、malloc と free は呼び出されたときのコールスタックを記録して、レポートに情報を載せられるようにしています。

計装

メモリアクセスの直前に対応するシャドウメモリを取得してアドレス可否を確認し、アドレス不可ならば検知するコードを計装します。

8 バイトアクセスの場合を C のコードで書くと、以下のようになります。(論文より引用)

シャドウバイトは 8 バイトを 1 バイトで表現しているため、対応する 1 バイトがゼロか確認するだけで済みます。

ShadowAddr = (Addr >> 3) + Offset;
if (*ShadowAddr != 0) ReportAndCrash(Addr);

一般化して AccessSize バイトアクセスの場合は以下のようになります。(論文より引用)

シャドウバイトからアクセスするバイト数ぶん切り出してアドレス可能か調べる必要があるため、8 バイトアクセスより面倒になります。

ShadowAddr = (Addr >> 3) + Offset;
k = *ShadowAddr;
if (k != 0 && ((Addr & 7) + AccessSize > k)) ReportAndCrash(Addr);

ASan の使い方(発展)

さて、ここまでで論文をざっと説明しましたが、上記論文は 2012 年のものであり、今ではだいぶ古い内容です。現在の ASan は色々進化しているので、その一部を使い方とともに説明します。

以下では、Clang を例に説明します。他のコンパイラでは別のオプション名だったり、オプションが無かったりします。

コンパイラフラグ

コンパイル時にオプションを渡すと、サニタイザーの計装を変更できるコンパイラフラグがあります。

コンパイラフラグは AddressSanitizerFlags で定義されており、このページに書かれているものであれば Clang や GCC で共通して使用できます。

これ以外にも、Clang や GCC にはそれぞれ固有のコンパイラフラグが多数用意されています。

Clang のコンパイラフラグ一覧は AddressSanitizer.cpp, GCC のコンパイラフラグ一覧は opts.cc にあります。

例えば、asan-detect-invalid-pointer-pair は不正なポインタペアを検知する計装を入れるオプションです。このオプションはデフォルトで false になっているため、計装は行われません。

static cl::opt<bool> ClInvalidPointerPairs(
    "asan-detect-invalid-pointer-pair",
    cl::desc("Instrument <, <=, >, >=, - with pointer operands"), cl::Hidden,
    cl::init(false));

ランタイムフラグ

ASAN_OPTIONS 環境変数を設定して ASan をつけたアプリケーションを実行すると、ランタイムフラグ(run-time flag)を設定できます。これによって ASan の動作を変更できます。この環境変数が影響を及ぼすのは、コンパイル時ではなく実行時(ランタイム)であることに注意してください。

ランタイムフラグは SanitizerCommonFlags や AddressSanitizerFlags で定義されていて、Clang, GCC は両方ともこれに準拠しています。

例えば ASan を計装したアプリケーションに ASAN_OPTIONS=help=1 を渡すと ASan のヘルプを表示でき、verbosity=1 とすると、ASan のデバッグログを表示できます。また、halt_on_error=0 を渡すと検知後も止まらずに実行し続けます。コロン区切りで複数設定できるので、verbosity=1:detect_use_after_return=1 とすれば、verbosity=1 と detect_use_after_return=1 が設定されます。

オプションで検知できるようになるバグ

Use-After-Return(UAR) や不正なポインタペアは、オプション無しの ASan は検知しないようになっています。デフォルトで検知しない理由は、大幅なパフォーマンス低下や誤検知などがあります。

以下ではそれを検知できるようにするオプションを説明します。

Use-After-Return

AddressSanitizerExampleUseAfterReturn

関数から返った後で、その関数内のローカル変数を使用しようとするバグです。以下のプログラム test-uar.c は func 関数でローカル変数 x のポインタを返します。main 関数ではそれを使用しようとしています。

#include <stdio.h>

__attribute__((noinline))
int* func(int v){
    int x = 0;
    x = v;
    return &x;
}

int main(){
    int* a = func(5);
    printf("a=%d\n", *a);
}

ASAN_OPTIONS に detect_stack_use_after_return=1 を設定して実行すると検知されます。

$ clang -g -Wno-return-stack-address -fsanitize=address -o test-uar-asan test-uar.c

$ ASAN_OPTIONS=detect_stack_use_after_return=1 ./test-uar-asan 
=================================================================
==38824==ERROR: AddressSanitizer: stack-use-after-return on address 0x7f334ce00020 at pc 0x559087d1a053 bp 0x7ffeac982ef0 sp 0x7ffeac982ee8
READ of size 4 at 0x7f334ce00020 thread T0
    #0 0x559087d1a052 in main /home/user/test-uar.c:12:22
    #1 0x7f334ee29d8f in __libc_start_call_main csu/../sysdeps/nptl/libc_start_call_main.h:58:16
    #2 0x7f334ee29e3f in __libc_start_main csu/../csu/libc-start.c:392:3
    #3 0x559087c5c304 in _start (/home/user/test-uar-asan+0x1e304) (BuildId: a5f8cfc61e1a4c3e6dca75fd7741c5d4ca2babc9)

Address 0x7f334ce00020 is located in stack of thread T0 at offset 32 in frame
    #0 0x559087d19eaf in func /home/user/test-uar.c:4

  This frame has 1 object(s):
    [32, 36) 'x' (line 5) <== Memory access at offset 32 is inside this variable
HINT: this may be a false positive if your program uses some custom stack unwind mechanism, swapcontext or vfork
      (longjmp and C++ exceptions *are* supported)
SUMMARY: AddressSanitizer: stack-use-after-return /home/user/test-uar.c:12:22 in main
Shadow bytes around the buggy address:
  0x0fe6e99b7fb0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0fe6e99b7fc0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0fe6e99b7fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0fe6e99b7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0fe6e99b7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x0fe6e99b8000: f5 f5 f5 f5[f5]f5 f5 f5 00 00 00 00 00 00 00 00
  0x0fe6e99b8010: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0fe6e99b8020: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0fe6e99b8030: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0fe6e99b8040: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0fe6e99b8050: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
==38824==ABORTING

不正なポインタペア

異なるオブジェクトのポインタを比較したり、減算しようとするバグです。これを検知できるようにするにはコンパイラフラグとランタイムフラグを両方設定する必要があります。

以下のプログラム test-pair.c を用意します。

#include <stdio.h>

int main(int argc, char** argv){
    int a[] = {0x11, 0x22, 0x33, 0x44, 0x55};
    int b[] = {0x66, 0x77, 0x88, 0x99, 0xaa}; 

    printf("CHECK!!!!!\n");
    if (a > b){
        printf("a > b\n");
    }else{
        printf("a <= b\n");
    }
    return 0;
}

8 行目で異なるオブジェクト a と b のポインタを比較しています。まずは普通に ASan 付きでコンパイルして、Ghidra などで main 関数を解析してみましょう。

$ clang -g -Wno-tautological-compare -fsanitize=address test-pair.c -o test-pair-asan

Ghidra のデコンパイル結果を見て確認してみると、printf の直後にポインタ比較があります。

では、asan-detect-invalid-pointer-pair を有効にしてコンパイルしてみましょう。オプションを有効化するには、-mllvm と -asan-detect-invalid-pointer-pair=1 を指定します。

$ clang -g -Wno-tautological-compare -fsanitize=address -mllvm -asan-detect-invalid-pointer-pair=1 test-pair.c -o test-pair-asan-pair

再び確認してみると、ポインタ比較の直前に __asan::__sanitizer_ptr_cmp 関数が呼ばれることがわかります。この関数が不正なポインタペアを検知する関数です。

この関数はランタイムフラグに応じて挙動が変化し、何も指定しない場合は何もせずにリターンします。この関数を動作させるには ASAN_OPTIONS に detect_invalid_pointer_pairs=2 を指定します。なお、1 と 2 で動作が変化します。1 の場合は片方がヌルポインタの場合は検知しません。今回の場合は 1 でも 2 でも問題ありません。

$ ASAN_OPTIONS=detect_invalid_pointer_pairs=2 ./test-pair-asan-pair
CHECK!!!!!
=================================================================
==30597==ERROR: AddressSanitizer: invalid-pointer-pair: 0x7ffddd78b6a0 0x7ffddd78b6e0
    #0 0x5590d9638ff3 in main /home/user/test-pair.c:8:11
    #1 0x7fbbbce29d8f in __libc_start_call_main csu/../sysdeps/nptl/libc_start_call_main.h:58:16
    #2 0x7fbbbce29e3f in __libc_start_main csu/../csu/libc-start.c:392:3
    #3 0x5590d957b304 in _start (/home/user/test-pair-asan-pair+0x1e304) (BuildId: fdb5eaf243d86218876436b9bcd72313099f05d8)

Address 0x7ffddd78b6a0 is located in stack of thread T0 at offset 32 in frame
    #0 0x5590d9638eaf in main /home/user/test-pair.c:3

  This frame has 2 object(s):
    [32, 52) 'a' (line 4) <== Memory access at offset 32 is inside this variable
    [96, 116) 'b' (line 5)
HINT: this may be a false positive if your program uses some custom stack unwind mechanism, swapcontext or vfork
      (longjmp and C++ exceptions *are* supported)
Address 0x7ffddd78b6e0 is located in stack of thread T0 at offset 96 in frame
    #0 0x5590d9638eaf in main /home/user/test-pair.c:3

  This frame has 2 object(s):
    [32, 52) 'a' (line 4)
    [96, 116) 'b' (line 5) <== Memory access at offset 96 is inside this variable
HINT: this may be a false positive if your program uses some custom stack unwind mechanism, swapcontext or vfork
      (longjmp and C++ exceptions *are* supported)
SUMMARY: AddressSanitizer: invalid-pointer-pair /home/user/test-pair.c:8:11 in main
==30597==ABORTING

おわりに

今回は ASan の概要と使い方、論文について説明しました。 ASan の基礎であるシャドウメモリとレッドゾーン自体は ASan が初出ではなく従来のツールでも行われていた手法ですが、ASan はその仕組みを改良してパフォーマンスと検知能力を大幅に高めました。今はさらなる進化を遂げて色々な機能を持っています。

次回以降では、今の Clang(LLVM) がどのように ASan を実装しているか読んでいきます。そこでは論文に書いてあったシャドウメモリとレッドゾーン、ランタイムライブラリの他に、今回紹介した Use-After-Return と不正なポインタペア検知の実装も見ていきます。

エンジニア募集

ＦＦＲＩセキュリティではサイバーセキュリティに関する興味関心を持つエンジニアを募集しています。採用に関しては採用ページをご覧ください。

*1: 使い方の説明なので簡単にインストールできるものを使用していますが、次回以降の記事では執筆当時最新版の LLVM のコードを読んでいく予定です。 ↩

FFRIエンジニアブログ

株式会社ＦＦＲＩセキュリティのエンジニアが執筆する技術者向けブログです