asan论文阅读

太久没更新博客了，把之前学习的一些笔记上传一波

ASAN

Introduction

针对内存破坏检测，市场上有各类工具，这些工具在速度，内存消耗，检测bug的范围上，报错率，支持的平台和其他特性上各不相同。有些工具支持检测很广的漏洞类型范围但是开销很大。asan在两者上平衡的很好，asan由两部分组成，检测模块和运行时模块，检测模块修改代码用于在内存使用时检测状态，并在栈和全局变量周围创建poisoned red zones用于检测越界。目前这些实现都是基于LLVM编译器的。运行时库的功能是负责替换用于分配释放内存相关的函数的(malloc free).用于在分配的内存周围分配 poisoned red zones。延迟被释放的内存的二次使用。并负责报错。

使用shadow memory用于存储应用相关信息，应用程序的内存被映射到shadow memory用于存储对应内存的信息。有通过多级表查询的方法映射到shadow memory，也有直接映射的。直接映射的最典型代表是TaintTrace和LIFT。TT内存消耗是1：1这也导致了许多程序在原本其内存的1/2内存限制下无法正常运行，LIFT的内存消耗是1/8.

另一些工具使用的多级地址转换的方法，如Valgrind和Dr.Memory把他们的shadow memory分成了多级并用一个表来查询这些shadow address，这需要额外的内存。

还有一些通过管理分配内存方式来检测内存漏洞，各自都存在缺陷。

AddressSanitizer Algorithm

类似Valgrind，基于shadow memory但是更加高效。

shadow memory

由于内存分配都按照8字节对齐，所以每个对齐的8字节内存都有9种状态即前0-8字节可访问。这些可以由一个字节来表示。

基于此asan需要源程序1/8内存空间来存放shadow memory。shadow bytes地址的计算方式如下

(Addr>>3)+Offset

关于offset的选取取决于应用程序所占用的内存大小且是动态的。内存从Offset到Offset+Max/8必须在程序启动时没有被占用。一般情况下linux中32位程序选用offset 0x20000000，64位程序中选用offset 0x0000100000000000。在某些开启地址随机化的情况选用0地址。这样也能精简指令集。

对于shadow byte。0表示全部可访问，1-7表示前x字节可访问，负数表示无法访问。asan使用不同的负数来表示不同种类的不可访问内存，如(heap redzones, stack redzones, global redzones, freed memory)

Instrumentation

检测逻辑，当触及8字节的内存时，asan会计算其对应的shadow bytes判断是否为0，不为0则直接报错

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

当触及1-7字节内存时算法类似

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

此处Addr & 7主要是因为内存对齐，如果直接AccessSize > k会忽略一种情况，从内存偏移x处开始读取size字节的情况。

asan的检测逻辑代码会被部署在llvm的最后阶段，因为优化会删除部分代码，放在最后阶段可以使得只有最终的代码才会被进行检测，提示性能。优化过程会减少代码的冗余操作，如果没放在最后阶段部分代码被优化而asan代码保留这样可能会引起误报，llvm自身也会有一些检测，asan不会对这类代码进行检测，默认其安全。

报错函数ReportAndCrash最多运行一次，但是他在代码各处都部署，所以还有很多的优化空间，目前是通过简单的函数调用来实现，另一个选择是使用硬件中断。

Run-time Library

运行时库的主要功能是管理shadow memory，在应用程序启动时整个shadow区域都会被映射，在linux上shadow区域在程序启动时总是不被占用的所以每次都会成功。在MacOS上需要把地址随机化关闭。目前shadow memory机制在windows上也适用。

malloc和free函数会被替换，malloc会在返回地址周围分配额外的内存即redzone，这些区域会被标记为不可访问即poisoned。redzone区域的大小决定了能检测溢出范围的大小。

内存区域的布局类似与一系列的freelist，每一个区域左右都有个redzone，n个区域会有n+1个redzone。

左侧redzone用于存储分配相关的信息如大小和线程id，redzone的最小大小是32字节。当free触发时会把整个内存区域放入隔离区quarantine以防止短时间内的重用，用于检测uaf。目前quarantine的策略是FIFO会拖延固定数量的内存一段时间。

默认情况下malloc和free的调用栈会记录用于提供详细的错误报告，malloc的调用栈会被记录在左侧redzone(redzone越大能记录的调用栈越大)，free的会被记录在右侧即开头区域，因为左redzone也是另一个regime的右redzone。

Stack And Globals

对于全局变量，在编译期间redzone就会被创建在全局变量周围并在程序启动时将地址发送给运行时库。运行时库会记录此类信息用于后续的报错处理。

对于栈上对象，redzones会目前是按照32字节对齐，案例如下。

1
2
3
void foo() {
char a[10];
<function body> }

如上函数会被转换成如下状态

1
2
3
4
5
6
7
8
9
10
11
12
13
void foo() {
char rz1[32]
char arr[10];
char rz2[32-10+32];
unsigned *shadow =
(unsigned*)(((long)rz1>>8)+Offset);
// poison the redzones around arr.
shadow[0] = 0xffffffff; // rz1
shadow[1] = 0xffff0200; // arr and rz2
shadow[2] = 0xffffffff; // rz2
<function body>
// un-poison all.
shadow[0] = shadow[1] = shadow[2] = 0; }

很好理解shadow[1] = 0xffff0200; 是主要的用于标记的shadow byte，最低字节0表示前8字节都可访问，第二个是02表示前2字节可访问，对应了arr的大小10。

False Negatives

上述的检测方法还是会漏掉一些罕见的bug，案例如下

1
2
3
int *a = new int[2]; // 8-aligned
int *u = (int*)((char*)a + 6);
*u = 1; // Access to range [6-9]

此处的问题是u所访问到的内存越界了，由于a是8字节对齐的采用第一种检测方式

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

按照此种 非对其内存的部分越界访问 asan选择直接忽略，因为目前所能想出的检测逻辑对性能都有不小的影响。

1.使用运行时检测地址是对齐

2.使用单字节映射方式

3.使用更复杂的内存映射来减少忽略该类漏洞的几率

如下的一些问题也会被asan忽略，诸如 Valgrind or Dr. Memory的工具同样也存在问题即过远距离的内存越界访问

1
2
3
char *a = new char[100];
char *b = new char[1000];
a[500] = 0; // may end up somewhere in b

另外一些uaf也不一定会被检测到

1
2
3
4
5
6
char *a = new char[1 << 20]; // 1MB
delete [] a; // <<< "free"
char *b = new char[1 << 28]; // 256MB
delete [] b; // drains the quarantine queue.
char *c = new char[1 << 20]; // 1MB
a[0] = 0; // "use". May land in ’c’.

这种成因主要还是因为asan检测uaf漏洞的实现，是通过隔离区quarantine queue。释放后的内存不会立刻放入free list而是放入quarantine queue。这个队列如果被占满导致内存出去然后c的分配可能使用的是a内存，此时再次进行use就无法检测了。

False Positives

整体来说没有存在误报的情况，但是在开发和部署的过程中有遇到，作者在此处讲解了几个案例

Conflict With Load Widening

即编译器的扩展优化

1
2
3
4
struct X { char a, b, c; };
void foo() {
X x; ...
... = x.a + x.c; }

x结构体三字节但是在内存中还是按照4字节对其的，再取a和c的时候编译器可能会进行优化直接取一个dword。这样asan会以为是越界。为了避免该问题asan启用时llvm会禁用扩展优化。

Conflict With Clone

这类问题存在于父子进程中，父进程创建子进程时带上CLONE VM|CLONE FILES标记会共享内存，假如子进程在栈上创建对象并且返回时选择了调用一些永不返回的函数入exit就会导致栈上的redzone没有被恢复，此时会影响到父进程，父进程在触及这些区域时就会触发误报，解决方案是针对一些exit exec类的函数进行检测，触发则取消先前的redzone标记。类似的针对长跳转和异常处理也要采取unpoisoned操作。

Intentional Wild Dereferences

这里涉及到部分代码中有意实现越界读写，该类情况很少遇到，可以在代码中添加宏no_address_safety_analysis来使得asan忽略该类情况，整个chromium代码中只有用到一次。

Threads

asan整体是线程安全的。shadow memory只有在内存不可被访问时才会被修改(在malloc free调用期间或在栈帧的创建和销毁期间模块初始化期间)。其他情况下的针对shadow memory操作都是读写。malloc和free使用thread-local caches来避免经常性使用锁。如果源程序在数据free和数据访问期间存在条件竞争那么asan可能会识别成uaf。线程的id在每次malloc和free期间都被记录且在错误报告中会体现。

Evaluation

讲解asan的性能方面的表现，这章直接pass

Future Work

此章节讲解后续能改进asan的一些办法

Compile-time Optimizations

主要是通过减少不必要的内存访问来提升性能

针对两次的内存访问情形进行优化

1.只需要检测第一次

1
2
3
*a = ...
if (...)
	*a = ...

2.针对第二次访问检测

1
2
3
if (...)
	*a = ...
*a = ...

这种优化可能放弃了在实际加载或存储发生之前报告错误的特性。

3.针对数组只检测第一个和最后一个元素

1
2
for (int i = 0; i < n; i++)
	a[i] = ...;

这种检测方案已经在memcpy memset类的函数中使用，当n过大时可能会忽略一些错误情况。

4.针对相邻内存，合并两次检测

1
2
3
struct { int a, b; } x; ...
x.a = ...;
x.b = ...;

5.针对确定安全的访问不必要进行检测,如固定范围的数组迭代

1
2
3
int x[100];
for (int i = 0; i < 100; i++)
	x[i] = ...;

6.不检测全局变量的标量

1
2
3
int glob;
int get_glob() {
return glob; }

Handling Libraries

目前的asan因为基于插桩，所以需要开源的才能支持，系统库由于预编译不能直接处理但是可以处理一些库函数如memset

针对开源库采用asan进行编译

针对闭源库，结合DynamoRIO类的插桩工具，在部分地方可能会有实现的困难，如栈上的redzone。

Hardware Support

asan的开销可以在大部分情况下使用，但是针对某些情况还是存在受限。此时有硬件支持会改善很多，如新增硬件指令“check4 Addr该指令应该等效于如下操作

1
2
3
4
ShadowAddr = (Addr >> Scale) + Offset;
k = *ShadowAddr;
if (k != 0 && ((Addr & 7) + N > k)
	GenerateException();

Offset 和 Scale 的值可以存储在特殊的寄存器中，并在应用程序启动时设置。

通过引入新指令可以显著减小二进制大小，且通过减少指令缓存（icache）压力、组合简单的算术操作以及实现更好的分支预测，这样的指令可以提高性能。

引入的指令还有一定的灵活性，默认情况下，checkN 指令可以是无操作（no-op），只有在设置了特殊的 CPU 标志时才启用。这样可以选择性地测试某些执行，甚至是在长时间运行的进程的一部分执行时间内进行测试。

EXAMPLE

1
2
3
void foo(T *a) {
*a = 0x1234;
}

clang -O2 -faddress-sanitizer a.c -c -DT=long进行编译

1
2
3
4
5
6
7
8
9
10
11
push %rax
mov %rdi,%rax
shr $0x3,%rax
mov $0x100000000000,%rcx
or %rax,%rcx
cmpb $0x0,(%rcx) # Compare Shadow with 0
jne 23 <foo+0x23> # To Error
movq $0x1234,(%rdi) # Original store
pop %rax
retq
callq __asan_report_store8 # Error

汇编如上，首先计算shadow byte地址

ShadowAddr = (Addr >> 3) + Offset;

接着比较是否为0即cmpb $0x0,(%rcx)

不相等则跳转报错，否则进行mov操作movq $0x1234,(%rdi) # Original store

上述是8字节的案例，下面是四字节的

clang -O2 -faddress-sanitizer a.c -c -DT=int

编译后汇编如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
push %rax
mov %rdi,%rax
shr $0x3,%rax
mov $0x100000000000,%rcx
or %rax,%rcx
mov (%rcx),%al # Get Shadow
test %al,%al
je 27 <foo+0x27> # To original store
mov %edi,%ecx # Slow path
and $0x7,%ecx # Slow path
add $0x3,%ecx # Slow path
cmp %al,%cl
jge 2f <foo+0x2f> # To Error
movl $0x1234,(%rdi) # Original store
pop %rax
retq
callq __asan_report_store4 # Error

同上，只不过多了个((Addr & 7) + AccessSize > k)判断操作。

asan论文阅读
http://www.psbazx.com/2023/05/22/asan论文阅读/
Beitragsautor
皮三宝
Veröffentlicht am
May 22, 2023
Urheberrechtshinweis