Sanitizer的paper reading和一些关键知识点。

ASAN

Shadow Memory

ASAN包含两个大模块:

  1. Instrumentation module
  2. Run-time library.

ASAN核心的工作原理就是：使用shadow memory表示可执行文件能够安全访问的内存范围。在编译期增加相应的检查shadow memory的指令到可执行文件，然后在运行期，通过这些指令检测内存访问是否合法。

Shadow Memory的计算方式

对于malloc分配的内存，一般是8字节对齐的，那么对于任意的8字节，都有9种状态，表示有k个字节(0 <= k <= 8)应用程序可用，而8 - k个字节不可用。

Address Sanitizer将应用程序的虚拟地址空间按照一定的比例映射到一块单独的内存区域，这块区域就叫做shadow memory。实际上就是将应用程序的8个字节，映射到shadow memory中的1个字节。

计算方法如下:

ShadowByte = (Addr>>3)+Offset

由于是8个字节映射到一个字节，所以需要[Offset, Offset + max / 8)这样一块区域用来保存原始内存的访问状态。

这个转换函数我们称为MemToShadow。任何shadow memory中被标记为不能访问的地址，其虚拟地址是不能够被访问的。 如果对一个本身已经在shadow memory的地址做转换，得到的地址也不能被访问的(因为shadow memory本身是没有被应用程序使用的)。

figure

Offset的值根据是32/64系统有所区别:

  • 64-bit

Shadow = (Mem >> 3) + 0x7fff8000;

wiki和原始paper中不一致，paper中为0x0000100000000000

virtual memory address region
[0x10007fff8000, 0x7fffffffffff] HighMem
[0x02008fff7000, 0x10007fff7fff] HighShadow
[0x00008fff7000, 0x02008fff6fff] ShadowGap
[0x00007fff8000, 0x00008fff6fff] LowShadow
[0x000000000000, 0x00007fff7fff] LowMem
  • 32-bit

Shadow = (Mem >> 3) + 0x20000000;

virtual memory address region
[0x40000000, 0xffffffff] HighMem
[0x28000000, 0x3fffffff] HighShadow
[0x24000000, 0x27ffffff] ShadowGap
[0x20000000, 0x23ffffff] LowShadow
[0x00000000, 0x1fffffff] LowMem

Shadow Memory的编码方式

除了Addressable映射的内存地址和Partially addressable可访问部分映射的内存地址，对其他内存地址的读写都是非法的。

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
  Shadow gap:            cc

Heap right redzone实际也是fa

Instrumentation module

有了shadow memory和对应的检测算法，Instrumentation module就是负责生成对应的检测代码，并增加到可执行文件中。具体工作如下：

  1. 在编译期增加指令，所有的内存访问都去检查该内存所对应的shadow memory的状态。
  2. 对栈上的对象和全局对象都在对象的内存前后各增加一块保护区(Poisoned redzone)，用来检测overflows和underflow。

目前这一步是在LLVM编译期完成的静态插桩，所有ASAN指令都是在LLVM完成所有优化之后加上的。

We placed the AddressSanitizer instrumentation pass at the very end of the LLVM optimization pipeline. This way we instrument only those memory accesses that survived all scalar and loop optimizations performed by the LLVM optimizer.

根据上面shadow memory的计算方式，编译器增加的代码如下：

  • 如果是8字节的memory access，直接计算shadow memory地址，然后检查是不是0x00即可。
  • 如果是1/2/4字节的memory access，先计算shadow memory地址，然后检查要访问的内存大小是否小于等于shadow memory后三位的值。
byte *shadow_address = MemToShadow(address);
byte shadow_value = *shadow_address;
if (shadow_value) {
  if (SlowPathCheck(shadow_value, address, kAccessSize)) {
    ReportError(address, kAccessSize, kIsWrite);
  }
}

// Check the cases where we access first k bytes of the qword
// and these k bytes are unpoisoned.
bool SlowPathCheck(shadow_value, address, kAccessSize) {
  last_accessed_byte = (address & 7) + kAccessSize - 1;
  return (last_accessed_byte >= shadow_value);
}

访问N字节的内存地址，都要求地址空间是N个字节对齐。

In both cases the instrumentation inserts only one memory read for each memory access in the original code. We assume that an N-byte access is aligned to N.

Run-time library

Run-time library主要作用有两个：

  1. 管理shadow memory

在应用程序启动的时候将shadow region通过mmap(不确定)的方式占用。同时，Bad region被设置为无法访问。

  1. 使用自定义的malloc/free函数

对于堆上的内存，在其前后都会分配一块额外的区域称为redzone。这块区域被标记为不可访问unaddressable，也被称为poisoned。redzone越大就越容易检查到overflow和underflow。

对于n个堆上分配的内存，总共会有n+1个redzones，每个分配内存块的右侧redzone，就是下个内存区域的左侧redzone，如下所示： rz1 | mem-1 | rz2 | mem-2 | rz3 | ... | rzn | mem-n | rzn+1

其中left redzone用来保存相关信息(比如申请空间大小、thread id、call stack等)，所以最小值为32bytes，left redzone越大，能保存的信息就越多。(代码上看最小值已经是16bytes了)

当调用free时，ASAN会把整块区域都标记为posisoned (这样可以查到double-free)，并放到一个FIFO队列中。这么做的原因是，标记为无法使用，同时尽可能地延长这块区域的占用时间，这样可以捕捉到更多的heap-use-after-free之类的错误。当这个队列大小Quarantine size的内存都被占用之后，才会真正去释放这些内存。

The run-time library replaces malloc/free and provides error reporting functions like __asan_report_load8.

  1. 管理栈上对象和全局对象

全局对象的redzone会在编译器就创建好，然后在程序启动时，由Run-time library标记为poisoned。

栈上的对象的reezone会在运行时创建和标记。每个栈上的对象使用32个字节(可能有31个字节作为padding，保证32字节对齐)作为redzone。

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

对于上面的代码，在运行时执行的代码如下：(和paper中不是很一致，以wiki为准)

void foo() {
  char redzone1[32];  // 32-byte aligned
  char a[10];         // 32-byte aligned
  char redzone2[22];
  char redzone3[32];  // 32-byte aligned
  int  *shadow_base = MemToShadow(redzone1);
  shadow_base[0] = 0xffffffff;  // poison redzone1
  shadow_base[1] = 0xffff0200;  // poison redzone2, unpoison 'a'
  shadow_base[2] = 0xffffffff;  // poison redzone3
  ...
  shadow_base[0] = shadow_base[1] = shadow_base[2] = 0; // unpoison all
  return;
}

example

demo参考之前老甘留的遗产

缺点

  1. ASAN的运行是需要消耗memory和CPU资源的，此外它也会增加代码大小。它的性能相比于之前的工具确实有了质的提升，但仍然无法适用于某些压力测试场景，尤其是需要全局打开的时候。这一点在Android上尤为明显，每当我们想要全局打开ASAN调试某些奇葩问题时，系统总会因为负载过重而跑不起来。
  2. ASAN对于UseAfterFree的检测依赖于隔离区，而隔离时间是非永久的。也就意味着已经free的区域过一段时间后又会重新被分配给其他人。当它被重新分配给其他人后，原先的持有者再次访问此块区域将不会报错。因为这一块区域的shadow memory不再是0xfd。所以这算是ASAN漏检的一种情况。
  3. ASAN对于overflow的检测依赖于安全区，而安全区总归是有大小的。它可能是64bytes，128bytes或者其他什么值，但不管怎么样终归是有限的。如果某次踩踏跨过了安全区，踩踏到另一片可寻址的内存区域，ASAN同样不会报错。这是ASAN的另一种漏检。

useful flags

  • quarantine_size_mb
  • redzone
  • halt_on_error
  • sleep_before_dying

Tags:

Categories:

Updated:

You May Also Enjoy

Coroutine internals

上次研究了Fiber，这次结合C++ Coroutines TS(N4680)和folly::coro::Baton，看看Coroutine~

Jemalloc 5.3.0 internals, part 3

上一篇介绍了hpa (huge page allocator)，这一篇继续介绍物理层的另一种page allocator: pac (page allocator classic)。