Memory Safety

Posted on Edited on

1. ASAN

https://juejin.cn/post/6844904111570157575

https://www.ndss-symposium.org/wp-content/uploads/2018/02/ndss2018_05A-5_Han_paper.pdf

Given the following C++ program test.cpp

1
2
3
4
5
6
7
8
9
#include <stdio.h>

int main(int argc, char** argv) {
    int* a = new int[10];
    a[5] = 0;
    if (a[argc])
        printf("xx\n");
    return 0;
}
image-20210110202244680

1. ASan工作原理

https://github.com/google/sanitizers/wiki/AddressSanitizerAlgorithm

ASAN工具包含两大块：

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

插桩模块主要会做两件事：（静态插桩，需重新编译）

  1. 为每个程序中用到的内存地址都开辟shadow memory来存储内存的相应状态
  2. 对所有的memory access都去检查该内存所对应的shadow memory的状态
  3. 开辟shadow memory的shadow memory为bad region
  4. 为所有栈上对象和全局对象创建前后的保护区(Poisoned redzone)，为检测溢出做准备。

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

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

2. Shadow Memory

Shadow memory是内存中的一块区域，其中的数据仅仅反应其他正常内存的状态信息，可以理解为正常内存的元数据，而正常内存中存储的才是程序真正需要的数据。

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

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

image-20210110165523758

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

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

Shadow memory address = (Normal memory address >> 3) + 0x7fff8000 (for 64 bit)

Shadow memory address = (Normal memory address >> 3) + 0x20000000 (for 32 bit)

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

img

Bad代表的是shadow memory的shadow memory，因此其中数据没有意义，该内存区域不可使用。shadown内存的值有以下几种：

  • 8个字节都可寻址，shadow memory的值为0
  • 负数:所有byte都无效，全无效一般都是插入的内存，并且每种插入的内存对应的负数值不同
  • k：表示前k个byte是有效，后8-k个无效，前提：malloc返回的地址内存对齐

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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  # use-after-free
  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

3. ASan 检验算法

1
2
3
4
ShadowAddr = (Addr >> 3) + Offset; // map from normal memory region to shadow memory
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// before instrumentation
void foo() {
  char a[8];
  ...
  return;
}

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

检验算法的汇编举例如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# int  load4(int *a)  { return *a; }
0000000000000000 <load4>:
   0:	48 89 f8             	mov    %rdi,%rax
   3:	48 89 fa             	mov    %rdi,%rdx
   6:	48 c1 e8 03          	shr    $0x3,%rax
   a:	83 e2 07             	and    $0x7,%edx
   d:	0f b6 80 00 80 ff 7f 	movzbl 0x7fff8000(%rax),%eax
  14:	83 c2 03             	add    $0x3,%edx
  17:	38 c2                	cmp    %al,%dl
  19:	7d 03                	jge    1e <load4+0x1e>
  1b:	8b 07                	mov    (%rdi),%eax    <<<<<< original load
  1d:	c3                   	retq   
  1e:	84 c0                	test   %al,%al
  20:	74 f9                	je     1b <load4+0x1b>
  22:	50                   	push   %rax
  23:	e8 00 00 00 00       	callq  __asan_report_load4

4. ASAN代码解释

对于下列C++代码

1
2
3
4
5
6
7
8
9
#include <stdio.h>

int main(int argc, char** argv) {
    int* a = new int[10];
    a[5] = 0;
    if (a[argc])
        printf("xx\n");
    return 0;
}

其LLVM的代码本来为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
define dso_local i32 @main(i32 %argc, i8** %argv) #0 !dbg !9 {
entry:
  %retval = alloca i32, align 4
  %argc.addr = alloca i32, align 4
  %argv.addr = alloca i8**, align 8
  %a = alloca i32*, align 8
  store i32 0, i32* %retval, align 4
  store i32 %argc, i32* %argc.addr, align 4
  store i8** %argv, i8*** %argv.addr, align 8
  %call = call i8* @_Znam(i64 40) #3, !dbg !11
  %0 = bitcast i8* %call to i32*, !dbg !11
  store i32* %0, i32** %a, align 8, !dbg !12
  %1 = load i32*, i32** %a, align 8, !dbg !13
  %arrayidx = getelementptr inbounds i32, i32* %1, i64 5, !dbg !13
  store i32 0, i32* %arrayidx, align 4, !dbg !14
  %2 = load i32*, i32** %a, align 8, !dbg !15
  %3 = load i32, i32* %argc.addr, align 4, !dbg !16
  %idxprom = sext i32 %3 to i64, !dbg !15
  %arrayidx1 = getelementptr inbounds i32, i32* %2, i64 %idxprom, !dbg !15
  %4 = load i32, i32* %arrayidx1, align 4, !dbg !15
  %tobool = icmp ne i32 %4, 0, !dbg !15
  br i1 %tobool, label %if.then, label %if.end, !dbg !15

if.then:                                          ; preds = %entry
  %call2 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i64 0, i64 0)), !dbg !17
  br label %if.end, !dbg !17

if.end:                                           ; preds = %if.then, %entry
  ret i32 0, !dbg !18
}

其中有a[5]和a[argc]两个内存访问，针对这两个内存访问，Memory Sanitizer分别加入如下语句进行检查

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
; a[5] 
  %arrayidx = getelementptr inbounds i32, i32* %2, i64 5, !dbg !16
  %3 = ptrtoint i32* %arrayidx to i64, !dbg !17
  %4 = lshr i64 %3, 3, !dbg !17
  %5 = add i64 %4, 2147450880, !dbg !17
  %6 = inttoptr i64 %5 to i8*, !dbg !17
  %7 = load i8, i8* %6, !dbg !17
  %8 = icmp ne i8 %7, 0, !dbg !17
  br i1 %8, label %9, label %15, !dbg !17, !prof !18

9:                                                ; preds = %entry
  %10 = and i64 %3, 7, !dbg !17
  %11 = add i64 %10, 3, !dbg !17
  %12 = trunc i64 %11 to i8, !dbg !17
  %13 = icmp sge i8 %12, %7, !dbg !17
  br i1 %13, label %14, label %15, !dbg !17

14:                                               ; preds = %9
  call void @__asan_report_store4(i64 %3), !dbg !17
  call void asm sideeffect "", ""()
  unreachable
  
15:                                               ; preds = %9, %entry
  store i32 0, i32* %arrayidx, align 4, !dbg !17

%arrayidx指的是指向a[5]的指针，memory sanitizer会检查这个指针指向的内存区域是不是合法的。首先将其扩展成64位后左移3个bit后加上offset 2147450880(0x7FFF8000)，也就是%5，该值为对应的shadow memory的内存地址，从shadow memory中加载内存信息为%7：

  • 首先判断该信息是否为0，如果等于0，表示8个内存区域都可以访问，跳转到block 15，说明可以利用%arrayidx访问相应数据
  • 如果不等于0，判断可访问的字节数是否合法，即是否大于k，若大于则跳转到block 14，报错。
1
2
3
4
ShadowAddr = (Addr >> 3) + Offset; // map from normal memory region to shadow memory
k = *ShadowAddr;
if (k != 0 && ((Addr & 7) + AccessSize > k))
	ReportAndCrash(Addr);

同样的%arrayidx1指的是指向a[argc]的指针，memory sanitizer会检查这个指针指向的内存区域是不是合法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
  %arrayidx1 = getelementptr inbounds i32, i32* %16, i64 %idxprom, !dbg !19
  %18 = ptrtoint i32* %arrayidx1 to i64, !dbg !19
  %19 = lshr i64 %18, 3, !dbg !19
  %20 = add i64 %19, 2147450880, !dbg !19
  %21 = inttoptr i64 %20 to i8*, !dbg !19
  %22 = load i8, i8* %21, !dbg !19
  %23 = icmp ne i8 %22, 0, !dbg !19
  br i1 %23, label %24, label %30, !dbg !19, !prof !18

24:                                               ; preds = %15
  %25 = and i64 %18, 7, !dbg !19
  %26 = add i64 %25, 3, !dbg !19
  %27 = trunc i64 %26 to i8, !dbg !19
  %28 = icmp sge i8 %27, %22, !dbg !19
  br i1 %28, label %29, label %30, !dbg !19

29:                                               ; preds = %24
  call void @__asan_report_load4(i64 %18), !dbg !19
  call void asm sideeffect "", ""()
  unreachable

30:                                               ; preds = %24, %15
  %31 = load i32, i32* %arrayidx1, align 4, !dbg !19

5. 缺陷

  1. CPU和Memory资源的消耗
  2. UseAfterFree的检测依赖隔离区，而隔离时间是非永久的，跨越过隔离时间后再次访问是有限的，会导致漏检。
  3. Overflow的检测依赖安全区，而安全区是有大小的，大小是有限的，跨越安全区访问就有可能也不报错，这是另一个漏检的原因。

HWASAN

1. 什么是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

2. 检测UseAfterFree

2.1 Use-After-Free

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

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

img

2.2 Heap-Over-Flow

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

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

img

2.3 优缺点

和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检测不到的情况。

3. MTE

Memory Tagging是Arm v8.5引入的新的硬件特性，从硬件层面完全实现上述HWASAN的逻辑，并添加相应的汇编指令支持tag的操作和分配等。

https://github.com/google/sanitizers/wiki/Stack-instrumentation-with-ARM-Memory-Tagging-Extension-(MTE)

Reference

  1. https://www.usenix.org/system/files/conference/atc12/atc12-final39.pdf
  2. https://arxiv.org/ftp/arxiv/papers/1802/1802.09517.pdf
  3. https://clang.llvm.org/docs/HardwareAssistedAddressSanitizerDesign.html
  4. https://github.com/google/sanitizers/blob/master/hwaddress-sanitizer/Hardware%20Memory%20Tagging%20to%20make%20C_C%2B%2B%20memory%20safe(r)%20-%20iSecCon%202018.pdf