ASAN和HWASAN原理解析
由于虚拟机的存在，Android应用开发者们通常不用考虑内存访问相关的错误。而一旦我们深入到Native世界中，原本面容和善的内存便开始凶恶起来。这时，由于程序员写法不规范、逻辑疏漏而导...
由于虚拟机的存在，Android应用开发者们通常不用考虑内存访问相关的错误。而一旦我们深入到Native世界中，原本面容和善的内存便开始凶恶起来。这时，由于程序员写法不规范、逻辑疏漏而导致的内存错误会统统跳到我们面前，对我们嘲讽一番。
这些错误既影响了程序的稳定性，也影响了程序的安全性，因为好多恶意代码就通过内存错误来完成入侵。不过麻烦的是，Native世界中的内存错误很难排查，因为很多时候导致问题的地方和发生问题的地方相隔甚远。为了更好地解决这些问题，各路大神纷纷祭出自己手中的神器，相互PK，相互补充。
ASAN(Address Sanitizer)和HWASAN(Hardware-assisted Address Sanitizer)就是这些工具中的佼佼者。
在ASAN出来之前，市面上的内存调试工具要么慢，要么只能检测部分内存错误，要么这两个缺点都有。总之，不够优秀。
HWASAN则是ASAN的升级版，它利用了64位机器上忽略高位地址的特性，将这些被忽略的高位地址重新利用起来，从而大大降低了工具对于CPU和内存带来的额外负载。
1. ASAN
ASAN工具包含两大块：
插桩模块(Instrumentation module)
一个运行时库(Runtime library)
插桩模块主要会做两件事：
对所有的memory access都去检查该内存所对应的shadow memory的状态。这是静态插桩，因此需要重新编译。
为所有栈上对象和全局对象创建前后的保护区(Poisoned redzone)，为检测溢出做准备。
运行时库也同样会做两件事：
替换默认路径的malloc/free等函数。为所有堆对象创建前后的保护区，将free掉的堆区域隔离(quarantine)一段时间，避免它立即被分配给其他人使用。
对错误情况进行输出，包括堆栈信息。
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的错误，需要有两点保证：
已经free掉的内存区域需要被标记成特殊的状态。在ASAN的实现里，free掉的normal memory对应的shadow memory值为0xfd（猜测有freed的意思）。
已经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。虽然它的表现很突出，但仍然有些地方不尽如人意，重点表现在以下几点：
ASAN的运行是需要消耗memory和CPU资源的，此外它也会增加代码大小。它的性能相比于之前的工具确实有了质的提升，但仍然无法适用于某些压力测试场景，尤其是需要全局打开的时候。这一点在Android上尤为明显，每当我们想要全局打开ASAN调试某些奇葩问题时，系统总会因为负载过重而跑不起来。
ASAN对于UseAfterFree的检测依赖于隔离区，而隔离时间是非永久的。也就意味着已经free的区域过一段时间后又会重新被分配给其他人。当它被重新分配给其他人后，原先的持有者再次访问此块区域将不会报错。因为这一块区域的shadow memory不再是0xfd。所以这算是ASAN漏检的一种情况。
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具有如下缺点：
可移植性较差，只适用于64位机器。
需要对Linux Kernel做一些改动以支持工具。
对于所有错误的检测将有一定概率false negative（漏掉一些真实的错误），概率为1/256。原因是tag的生成只能从256（2^8）个数中选一个，因此不同地址的tag将有可能相同。
不过相对于这些缺点，HWASAN所拥有的优点更加引人注目：
不再需要安全区来检测buffer overflow，既极大地降低了工具对于内存的消耗，也不会出现ASAN中某些overflow检测不到的情况。
不再需要隔离区来检测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…
参考文章：
www.usenix.org/system/file…
arxiv.org/ftp/arxiv/p…
clang.llvm.org/docs/Hardwa…
github.com/google/sani…
作者：芦半山
链接：
https://juejin.im/post/5e8362096fb9a03c3b2bb652
来源：掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
(END)
更多精彩，尽在"Linux阅码场"，扫描下方二维码关注
别忘了点个在看哦
华为开发者空间，是为全球开发者打造的专属开发空间，汇聚了华为优质开发资源及工具，致力于让每一位开发者拥有一台云主机，基于华为根生态开发、创新。
更多推荐
10
0- 0
已为社区贡献7条内容
所有评论(0)