阅读 1059

ASAN和HWASAN原理解析

由于虚拟机的存在,Android应用开发者们通常不用考虑内存访问相关的错误。而一旦我们深入到Native世界中,原本面容和善的内存便开始凶恶起来。这时,由于程序员写法不规范、逻辑疏漏而导致的内存错误会统统跳到我们面前,对我们嘲讽一番。

这些错误既影响了程序的稳定性,也影响了程序的安全性,因为好多恶意代码就通过内存错误来完成入侵。不过麻烦的是,Native世界中的内存错误很难排查,因为很多时候导致问题的地方和发生问题的地方相隔甚远。为了更好地解决这些问题,各路大神纷纷祭出自己手中的神器,相互PK,相互补充。

ASAN(Address Sanitizer)和HWASAN(Hardware-assisted Address Sanitizer)就是这些工具中的佼佼者。

在ASAN出来之前,市面上的内存调试工具要么慢,要么只能检测部分内存错误,要么这两个缺点都有。总之,不够优秀。

HWASAN则是ASAN的升级版,它利用了64位机器上忽略高位地址的特性,将这些被忽略的高位地址重新利用起来,从而大大降低了工具对于CPU和内存带来的额外负载。

1. ASAN

ASAN工具包含两大块:

  • 插桩模块(Instrumentation module)
  • 一个运行时库(Runtime library)

插桩模块主要会做两件事:

  1. 对所有的memory access都去检查该内存所对应的shadow memory的状态。这是静态插桩,因此需要重新编译。
  2. 为所有栈上对象和全局对象创建前后的保护区(Poisoned redzone),为检测溢出做准备。

运行时库也同样会做两件事:

  1. 替换默认路径的malloc/free等函数。为所有堆对象创建前后的保护区,将free掉的堆区域隔离(quarantine)一段时间,避免它立即被分配给其他人使用。
  2. 对错误情况进行输出,包括堆栈信息。

1.1 Shadow Memory

如果想要了解ASAN的实现原理,那么shadow memory将是第一个需要了解的概念。

Shadow memory有一些元数据的思维在里面。它虽然也是内存中的一块区域,但是其中的数据仅仅反应其他正常内存的状态信息。所以可以理解为正常内存的元数据,而正常内存中存储的才是程序真正需要的数据。

Malloc函数返回的地址通常是8字节对齐的,因此任意一个由(对齐的)8字节所组成的内存区域必然落在以下9种状态之中:最前面的k(0≤k≤8)字节是可寻址的,而剩下的8-k字节是不可寻址的。这9种状态便可以用shadow memory中的一个字节来进行编码。

实际上,一个byte可以编码的状态总共有256(2^8)种,因此用在这里绰绰有余。

Shadow memory和normal memory的映射关系如上图所示。一个byte的shadow memory反映8个byte normal memory的状态。那如何根据normal memory的地址找到它对应的shadow memory呢?

对于64位机器上的Android而言,二者的转换公式如下:

Shadow memory address = (Normal memory address >> 3) + 0x100000000

右移三位的目的是为了完成 8➡1的映射,而加一个offset是为了和Normal memory区分开来。最终内存空间种会存在如下的映射关系:

Bad代表的是shadow memory的shadow memory,因此其中数据没有意义,该内存区域不可使用。

上文中提到,8字节组成的memory region共有9中状态:

  • 1~7个字节可寻址(共七种),shadow memory的值为1~7。
  • 8个字节都可寻址,shadow memory的值为0。
  • 0个字节可寻址,shadow memory的值为负数。

为什么0个字节可寻址的情况shadow memory不为0,而是负数呢?是因为0个字节可寻址其实可以继续分为多种情况,譬如:

  • 这块区域是heap redzones
  • 这块区域是stack redzones
  • 这块区域是global redzones
  • 这块区域是freed memory

对所有0个字节可寻址的normal memory region的访问都是非法的,ASAN将会报错。而根据其shadow memory的值便可以具体判断是哪一种错。

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 (实际上Heap right 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
复制代码

1.2 检测算法

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

在每次内存访问时,都会执行如上的伪代码,以判断此次内存访问是否合规。

首先根据normal memory的地址找到对应shadow memory的地址,然后取出其中存取的byte值:k。

  • k!=0,说明Normal memory region中的8个字节并不是都可以被寻址的。
  • Addr & 7,将得知此次内存访问是从memory region的第几个byte开始的。
  • AccessSize是此次内存访问需要访问的字节长度。
  • (Addr&7)+AccessSize > k,则说明此次内存访问将会访问到不可寻址的字节。(具体可分为k大于0和小于0两种情况来分析)

当此次内存访问可能会访问到不可寻址的字节时,ASAN会报错并结合shadow memory中具体的值明确错误类型。

1.3 典型错误

1.3.1 Use-After-Free

想要检测UseAfterFree的错误,需要有两点保证:

  1. 已经free掉的内存区域需要被标记成特殊的状态。在ASAN的实现里,free掉的normal memory对应的shadow memory值为0xfd(猜测有freed的意思)。
  2. 已经free掉的内存区域需要放入隔离区一段时间,防止发生错误时该区域已经通过malloc重新分配给其他人使用。一旦分配给其他人使用,则可能漏掉UseAfterFree的错误。

测试代码:

// RUN: clang -O -g -fsanitize=address %t && ./a.out
int main(int argc, char **argv) {
  int *array = new int[100];
  delete [] array;
  return array[argc];  // BOOM
}
复制代码

ASAN输出的错误信息:

=================================================================
==6254== ERROR: AddressSanitizer: heap-use-after-free on address 0x603e0001fc64 at pc 0x417f6a bp 0x7fff626b3250 sp 0x7fff626b3248
READ of size 4 at 0x603e0001fc64 thread T0
    #0 0x417f69 in main example_UseAfterFree.cc:5
    #1 0x7fae62b5076c (/lib/x86_64-linux-gnu/libc.so.6+0x2176c)
    #2 0x417e54 (a.out+0x417e54)
0x603e0001fc64 is located 4 bytes inside of 400-byte region [0x603e0001fc60,0x603e0001fdf0)
freed by thread T0 here:
    #0 0x40d4d2 in operator delete[](void*) /home/kcc/llvm/projects/compiler-rt/lib/asan/asan_new_delete.cc:61
    #1 0x417f2e in main example_UseAfterFree.cc:4
previously allocated by thread T0 here:
    #0 0x40d312 in operator new[](unsigned long) /home/kcc/llvm/projects/compiler-rt/lib/asan/asan_new_delete.cc:46
    #1 0x417f1e in main example_UseAfterFree.cc:3
Shadow bytes around the buggy address:
  0x1c07c0003f30: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x1c07c0003f40: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x1c07c0003f50: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x1c07c0003f60: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x1c07c0003f70: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
=>0x1c07c0003f80: fa fa fa fa fa fa fa fa fa fa fa fa[fd]fd fd fd
  0x1c07c0003f90: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
  0x1c07c0003fa0: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
  0x1c07c0003fb0: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fa fa
  0x1c07c0003fc0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x1c07c0003fd0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
复制代码

可以看到,=>指向的那行有一个byte数值用中括号给圈出来了:[fd]。它表示的是此次出错的内存地址对应的shadow memory的值。而其之前的fa表示Heap left redzone,它是之前该区域有效时的遗留产物。连续的fd总共有50个,每一个shadow memory的byte和8个normal memory byte对应,所以可以知道此次free的内存总共是50×8=400bytes。这一点在上面的log中也得到了验证,截取出来展示如下:

0x603e0001fc64 is located 4 bytes inside of 400-byte region [0x603e0001fc60,0x603e0001fdf0)
复制代码

此外,ASAN的log中不仅有出错时的堆栈信息,还有该内存区域之前free时的堆栈信息。因此我们可以清楚地知道该区域是如何被释放的,从而快速定位问题,解决问题。

1.3.2 Heap-Buffer-Overflow

想要检测HeapBufferOverflow的问题,只需要保证一点:

  • 正常的Heap前后需要插入一定长度的安全区,而且此安全区对应的shadow memory需要被标记为特殊的状态。在ASAN的实现里,安全区被标记为0xfa。

测试代码:

ASAN输出的错误信息:

=================================================================
==1405==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x0060bef84165 at pc 0x0058714bfb24 bp 0x007fdff09590 sp 0x007fdff09588
WRITE of size 1 at 0x0060bef84165 thread T0
    #0 0x58714bfb20  (/system/bin/bootanimation+0x8b20)
    #1 0x7b434cd994  (/apex/com.android.runtime/lib64/bionic/libc.so+0x7e994)

0x0060bef84165 is located 1 bytes to the right of 100-byte region [0x0060bef84100,0x0060bef84164)
allocated by thread T0 here:
    #0 0x7b4250a1a4  (/system/lib64/libclang_rt.asan-aarch64-android.so+0xc31a4)
    #1 0x58714bfac8  (/system/bin/bootanimation+0x8ac8)
    #2 0x7b434cd994  (/apex/com.android.runtime/lib64/bionic/libc.so+0x7e994)
    #3 0x58714bb04c  (/system/bin/bootanimation+0x404c)
    #4 0x7b45361b04  (/system/bin/bootanimation+0x54b04)

SUMMARY: AddressSanitizer: heap-buffer-overflow (/system/bin/bootanimation+0x8b20) 
Shadow bytes around the buggy address:
  0x001c17df07d0: fa fa fa fa fa fa fa fa fd fd fd fd fd fd fd fd
  0x001c17df07e0: fd fd fd fd fd fa fa fa fa fa fa fa fa fa fa fa
  0x001c17df07f0: fd fd fd fd fd fd fd fd fd fd fd fd fd fa fa fa
  0x001c17df0800: fa fa fa fa fa fa fa fa fd fd fd fd fd fd fd fd
  0x001c17df0810: fd fd fd fd fd fa fa fa fa fa fa fa fa fa fa fa
=>0x001c17df0820: 00 00 00 00 00 00 00 00 00 00 00 00[04]fa fa fa
  0x001c17df0830: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x001c17df0840: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x001c17df0850: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x001c17df0860: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x001c17df0870: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
复制代码

可以看到最终出错的shadow memory值为0x4,表示该shadow memroy对应的normal memory中只有前4个bytes是可寻址的。0x4的shadow memory前还有12个0x0,表示其前面的12个memory region(每个region有8个byte)都是完全可寻址的。因此所有可寻址的大小=12×8+4=100,正是代码中malloc的size。之所以此次访问会出错,是因为地址0x60bef84165意图访问最后一个region的第五个byte,而该region只有前四个byte可寻址。由于0x4后面是0xfa,因此此次错误属于HeapBufferOverflow。

1.4 缺陷

自从2011年诞生以来,ASAN已经成功地参与了众多大型项目,譬如Chrome和Android。虽然它的表现很突出,但仍然有些地方不尽如人意,重点表现在以下几点:

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

2.HWASAN

HWASAN是ASAN工具的“升级版”,它基本上解决了上面所说的ASAN的3个问题。但是它需要64位硬件的支持,也就是说在32位的机器上该工具无法运行。

AArch64是64位的架构,指的是寄存器的宽度是64位,但并不表示内存的寻址范围是2^64。真实的寻址范围和处理器内部的总线宽度有关,实际上ARMv8寻址只用到了低48位。也就是说,一个64bit的指针值,其中真正用于寻址的只有低48位。那么剩下的高16位干什么用呢?答案是随意发挥。AArch64拥有地址标记(Address tagging, or top-byte-ignore)的特性,它表示允许软件使用64bit指针值的高8位开发特定功能。

HWASAN用这8bit来存储一块内存区域的标签(tag)。接下来我们以堆内存示例,展示这8bit到底如何起作用。

堆内存通过malloc分配出来,HWASAN在它返回地址时会更改该有效地址的高8位。更改的值是一个随机生成的单字节值,譬如0xaf。此外,该分配出来的内存对应的shadow memory值也设为0xaf。需要注意的是,HWASAN中normal memory和shadow memory的映射关系是16➡1,而ASAN中二者的映射关系是8➡1。

以下分别讨论UseAfterFree和HeapOverFlow的情况。

2.1 Use-After-Free

当一个堆内存被分配出来时,返回给用户空间的地址便已经带上了标签(存储于地址的高8位)。之后通过该地址进行内存访问,将先检测地址中的标签值和访问地址对应的shadow memory的值是否相等。如果相等则验证通过,可以进行正常的内存访问。

当该内存被free时,HWASAN会为该块区域分配一个新的随机值,存储于其对应的shadow memory中。如果此后再有新的访问,则地址中的标签值必然不等于shadow memory中存储的新的随机值,因此会有错误产生。通过如下图示可以很好地明白这一点(图中只用了4bit记录标记值,但不影响理解,8bit标记值的检测和它一致)。

2.2 Heap-Over-Flow

想要检测HeapOverFlow,有一个前提需要满足:相邻的memory区域需要有不同的shadow memory值,否则将无法分辨两个不同的memory区域。为每个memory区域随机分配将有概率让两个相邻区域具有同样的shadow memory值,虽然概率比较小,但总归是个缺陷。因此工具中会有其他逻辑保证这个前提。

下图展示了HeapOverFlow的检测过程。指针p的标签和访问的地址p[32]所对应的shadow memory值不一致,因此报错(图中只用了4bit记录标记值,但不影响理解,8bit标记值的检测和它一致)。

2.3 错误信息示例

Abort message: '==12528==ERROR: HWAddressSanitizer: tag-mismatch on address 0x003d557e2c20 at pc 0x00748b4a6918
READ of size 4 at 0x003d557e2c20 tags: d1/9b (ptr/mem) in thread T0
    #0 0x748b4a6914  (/system/lib64/libutils.so+0x11914)
    #1 0x748a521bdc  (/apex/com.android.runtime/lib64/bionic/libc.so+0x121bdc)
    #2 0x748a51ad7c  (/apex/com.android.runtime/lib64/bionic/libc.so+0x11ad7c)
    #3 0x748a47f830  (/apex/com.android.runtime/lib64/bionic/libc.so+0x7f830)

[0x003d557e2c20,0x003d557e2c80) is a small unallocated heap chunk; size: 96 offset: 0
Thread: T0 0x006b00002000 stack: [0x007fcd371000,0x007fcdb71000) sz: 8388608 tls: [0x000000000000,0x000000000000)
HWAddressSanitizer can not describe address in more detail.
Memory tags around the buggy address (one tag corresponds to 16 bytes):
   e1  e1  e1  e1  83  83  83  83  83  00  a3  a3  a3  a3  a3  a3   
   b7  b7  b7  b7  b7  00  01  01  01  01  01  00  95  95  95  95   
   95  00  ec  ec  ec  ec  ec  00  c8  c8  c8  c8  c8  00  21  21   
   21  21  21  00  cb  cb  cb  cb  cb  00  b8  b8  b8  b8  b8  00   
   14  14  14  14  14  14  b9  b9  b9  b9  b9  b9  89  89  89  89   
   89  89  95  95  95  95  95  95  47  47  47  47  47  00  fe  fe   
   fe  fe  fe  00  c5  c5  c5  c5  c5  00  8e  8e  8e  8e  8e  8e   
   5c  5c  5c  5c  5c  5c  af  af  af  af  af  af  b0  b0  b0  b0   
=> b0  b0 [9b] 9b  9b  9b  9b  9b  1f  1f  1f  1f  1f  1f  69  69 <=
   69  69  69  a0  7a  7a  7a  7a  7a  ff  eb  eb  eb  eb  eb  eb   
   16  16  16  16  16  16  81  81  81  81  81  81  7f  7f  7f  7f   
   7f  7f  57  57  57  57  57  57  e0  e0  e0  e0  e0  e0  94  94   
   94  94  94  00  35  35  35  35  35  35  98  98  98  98  98  00   
   7d  7d  7d  7d  7d  7d  6e  6e  6e  6e  6e  6e  59  59  59  59   
   59  59  8e  8e  8e  8e  8e  8e  6d  6d  6d  6d  6d  6d  69  69   
   69  69  69  69  d5  d5  d5  d5  d5  d5  63  63  63  63  63  63   

复制代码

0x9b总共有6个,因此该memory区域的总长为6×16=96,与上述提示一致。

[0x003d557e2c20,0x003d557e2c80) is a small unallocated heap chunk; size: 96
复制代码

2.4 优缺点

和ASAN相比,HWASAN具有如下缺点:

  1. 可移植性较差,只适用于64位机器。
  2. 需要对Linux Kernel做一些改动以支持工具。
  3. 对于所有错误的检测将有一定概率false negative(漏掉一些真实的错误),概率为1/256。原因是tag的生成只能从256(2^8)个数中选一个,因此不同地址的tag将有可能相同。

不过相对于这些缺点,HWASAN所拥有的优点更加引人注目:

  1. 不再需要安全区来检测buffer overflow,既极大地降低了工具对于内存的消耗,也不会出现ASAN中某些overflow检测不到的情况。
  2. 不再需要隔离区来检测UseAfterFree,因此不会出现ASAN中某些UseAfterFree检测不到的情况。

2.5 一个难题

上述的讨论其实回避了一个问题:如果一个16字节的memory region中只有前几个字节可寻址(假设是5),那么其对应的shadow memory值也是5。这时,如果用地址去访问该region的第2个字节,那么如何判断访问是否合规呢?

此时直接对比地址的tag和shadow memory的值肯定是不行的,因为此时的shadow memory值含义发生了变化,它不再是一个类似于tag的随机值,而是memory region中可访问字节的数目。

为了解决这个难题,HWASAN在这种情况下将memory region的随机值保存在最后一个字节中。所以即便地址的tag和shadow memory的值不等,但只要和memory region中最后一个字节相等,也表明该访问合法。

具体可参考链接:clang.llvm.org/docs/Hardwa…

参考文章:

  1. www.usenix.org/system/file…
  2. arxiv.org/ftp/arxiv/p…
  3. clang.llvm.org/docs/Hardwa…
  4. github.com/google/sani…