关于算法:Sanitizers-系列之-address-sanitizer-原理篇

asan 的原理

概述

如何断定过程是否拜访一片内存区域？一个直观的想法是: 给每个字节做个记号（poison state），将过程不可能拜访的字节标记为 poisoned，而后在每次拜访内存之前先查看它的 poison state，如果是 poisoned，那么就能够判断产生了非法拜访。asan 的外围算法就是基于这个想法，asan 会应用一片专门的内存来保留 application memory 每个字节的 poison state，这片内存的业余名称是 shallow memory，在拜访地址 addr 之前，首先在 shadow memory 中查看 addr 的 poison state，如果 poison state 是 poisoned，那么就能够断定产生了非法拜访，asan 会及时报告谬误，否则程序失常运行。

实际上，asan 的实现远比下面形容的要简单，概括地说，asan 由两局部组成：

通过上述内容能够看出：asan 的实现既依赖于 compiler 在编译时对源代码做非凡的转换（由 instrumentation module 实现），还依赖一个运行时库，下文将对上述内容进行更加具体的介绍。

Shadow Memory

asan 会将过程的 memory space 分为两大类：

• Application Memory（简称为 Mem）

这部分内存属于利用过程，由利用过程进行应用。

• Shadow Memory（简称为 Shadow）

这部分内存用于寄存 shadow value，shadow value 其实就是 Mem 各个 byte 的 poison state。”Shadow“的字面意思是“影子”，在 asan 的具体实现上，Mem 和 Shadow 之间存在着一一对应的关系，这就相当于现实生活中的 ” 影子 ”。依照 Mem 和 Shadow 之间的一一对应的关系，将 Mem 中的一个 byte 标记为“poisoned”是通过将这个 byte 对应的 Shadow 中的 byte 设置为非凡值来实现的。

Shadow memory 是内存谬误查看工具中广泛采纳的一种技术，在应用这种技术时，会波及如下两个问题:

1. Application Memory to Shadow Memory mapping（MemToShadow），即如何将 Application Memory 中的每个字节映射到 Shadow Memory 中。
   在 asan 的具体实现中，这两类内存的组织形式、映射形式应使计算 Application Memory 对应的 Shadow Memory 的速度快。
2. Shadow encoding，即 Shadow Memory 如何紧凑地保留  Application Memory 的 poison state。

下文进行具体介绍：

• MemToShadow
  asan 的实现基于一个事实前提：由 malloc 返回的内存地址总是至多 8 字节对齐，这个个性保障能应用一个对立的地址映射公式来将 Application Memory 中的一个字节映射到 Shadow Memory 中，无需对非凡状况进行非凡的实现。除此之外，这个个性也蕴含了应用程序的 heap memory 的任何 8 字节对齐的 8 字节序列处于 9 种不同状态之一：前 k（0 ≤ k ≤ 8）字节是能够拜访的（可寻址），其余 8-k 字节不可拜访。显然这 9 种状态能够被编码到 Shadow Memory 的单个字节中（一个字节蕴含 8bit，是可能编码 9 种状态的）。基于此，asan 将应用程序的 heap memory 的 8 个字节映射到 Shadow Memory 的 1 个字节中，因而实践上 Shadow Memor 将消耗八分之一的虚拟地址空间。
  asan 的 MemToShadow 计划为：给定位于 Application Memory 的地址  Addr，其对应的 Shadow Memory 的地址为：

(Addr>>Scale)+Offset

Scale 示意缩放比例，当应用后面形容的计划时，Scale 取值为 3，这是因为 Application Memory 的间断 8（8 等于 2 的 3 次方）个字节被映射到 Shadow Memory 的单个字节中。

Offset 示意偏移，asan 为不同的平台选取了不同的 Offset 值：

1. 在 32 位 Linux 或 MacOS 零碎上，asan 选取的 Offset = 0x20000000
2. 在具备 47 个无效地址位的 64 位零碎上，asan 选取的 Offset =0x0000100000000000

下图显示开启了 asan 后过程的 memory space 的空间布局。Application Memory（图中的 Memory 区域）分为两局部（低和高），映射到相应的 Shadow Memory（图中的 Shadow 区域）。如果对 Shadow Memory 中的地址执行上述映射公式，映射公式保障它输入的地址将位于图中的 Bad 区域，在实现中，通过 page protection 机制将 Bad 区域标记为不可拜访从而保障可能及时发现谬误。

• Shadow encoding
  通过后面的介绍可知：asan 将应用程序 heap memory 的 8 个字节映射到 Shadow Memory 的 1 个字节，asan 依照如下规定来编码 Shadow Memory 的每个字节的值：

1. 0 示意对应的应用程序内存区域中的所有 8 个字节都是可寻址的
2. k（1 ≤ k ≤ 7）示意前 k 个字节是可寻址的
3. 任何负值示意整个 8 字节字不可寻址，asan 应用不同的负值来辨别不同类型的不可寻址内存（heap redzones、stack redzones、global redzones、freed memory）

Instrumentation 

在 asan 论文中，将它的 Instrumentation 纳入了 compile-time instrumentation（CTI）的领域，这是因为 asan 要求编译器在编译时对源程序进行转换，因而任何反对 asan 的编译器都须要依照 asan 的算法进行非凡的实现。

在开启了 asan 后，编译器会将程序中的内存拜访依照以下形式进行转换:

转换前: 

*address = ...;  //  write、store
variable = *address; // read、load

转换后：

byte *shadow_address = MemToShadow(address);
byte shadow_value = *shadow_address;
if (shadow_value)
{if (SlowPathCheck(shadow_value, address, kAccessSize))
  {ReportError(address, kAccessSize, kIsWrite);
  }
}

*address = ...;  //  write、store
variable = *address; // read、load

// 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);
}

上述伪代码形容了 asan 的查看逻辑，其中 kAccessSize 示意的内存拜访的大小，asan 假如 N 字节拜访的地址与 N 对齐，所以 address 是和 kAccessSize 对齐的，上面对上述伪代码进行详细分析：

一、当 kAccessSize 的值为 8，示意 8-byte memory access，那么必须 8-byte 全副可寻址能力拜访，否则就报错，显然此时只须要查看 Shadow_value 的值是否为 0 即可，这个过程能够简化为如下形式：

byte *shadow_address = MemToShadow(address);
byte shadow_value = *shadow_address;
if (shadow_value != 0)
    ReportAndCrash(address);

二、当 kAccessSize 的值为 1、2、4 时，别离示意 1-byte memory access、2-byte memory access、4-byte memory access，如果 8-byte 全副可寻址是最好的，即便不是全副可寻址也不能够间接报错，还须要将地址的最初 3 位与 Shadow_value 进行比拟。

在这两种状况下，asan 只为原始代码中的每个内存拜访插入一个内存读取（读取 shallow memory）。asan 假如 N 字节拜访的地址与 N 对齐，如果理论状况并非如此，asan 可能会错过由未对齐拜访引起的谬误，在前面的 False Negatives 章节会进行介绍。

Poisoned redone

在后面的章节中曾经提及了 poisoned redone，本节将对它进行专门的介绍。

poisoned redone 实质上是一片内存区域，其中所有字节都被标记为 poisoned。这就是象征中，一旦拜访 poisoned redzone 就相当于“踩红线”了，就会触发 asan 报错。在 asan 中，它被用于检测 out of bound（越界拜访）内存谬误，asan 会在 object 的四周创立 poisoned redone，一旦产生了 out of bound，如果进入到 poisoned redone 就会触发 asan 报错。实践上 poisoned redzone 越大，那么通过它检测到 out of bound 内存谬误的概率就越大，但在理论中，因为内存大小无限，asan 会抉择一个适合大小的 poisoned redone。

须要留神的是: 这种形式在一些极限的状况下会生效，这在前面的 False Negatives 章节会进行介绍。

Stack And Globals

为了检测对 global object 和 stack object 的越界拜访，asan 必须在这些对象四周创立“poisoned redzone”。

对于 global object，redzone 是在编译时创立，redzone 的地址在应用程序启动时传递给 run-time library。run-time library 的函数会将该 redzone 标记为 poisoned 并记录地址以供进一步错误报告。

对于 stack，redzone 是在运行时创立并标记为 poisoned 的。目前，应用 32 字节的 redzone（加上最多 31 字节用于对齐）。下表形容了 asan 的转换：

在上述例子中，asan 应用 poisoned redone 实现对 stack object a 的爱护。

Run-time library

在后面曾经概述了 asan 的 run-time library 的次要性能。在开启 asan 后，生成的产物会动静链接 asan 的 run-time library。

asan 的 run-time library 的目标之一是用它的非凡实现的 memory allocator 替换规范库的 memory allocator，以发现 heap object 的谬误。

asan 的 run-time library 的 malloc 和 free 函数的原理如下:

malloc 函数会在返回的 heap 区域四周调配 poisoned redzone 以发现越界拜访。

free 函数会将开释的内存区域全副标记为 poisoned 并将其置于 quarantine（隔离区），这样该区域就不会很快被 memory allocator 重新分配，因而在一段时间内如果再次拜访这片曾经开释的内存区域，就会触发 asan 报错，这样做的目标是发现 use-after-free 类谬误。目前，quarantine 是用 FIFO 队列实现的，它在任何时候都领有固定数量的内存。须要留神的是：这种形式在一些极限的状况下会生效，在后文的 False Negatives 章节会进行介绍。

asan 的 run-time library 的另外一个目标是治理 Shadow Memory。在应用程序启动时，整个 Shadow Memory 都被映射（mapped，仅仅占用地址空间，并未分配内存），因而程序的其余局部不能应用它。

asan 的准确性

实践上，asan 不会产生 false positive（误报），然而会存在 false negative（脱漏），上面联合具体例子进行阐明。

False Negatives 
false negative 指的是理论存在谬误但 asan 没有检测出，本节次要形容 asan false negative 这种状况。

1. an unaligned access that is partially out-of-bounds

样例代码如下：

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

u = 1 就是典型的“unaligned access that is partiallyout-of-bounds”。查看残缺代码：

https://github.com/dengking/s…

目前 asan 疏忽了这种类型的谬误，因为所有提出的解决方案都会减慢通用程序执行门路。

2. 越界拜访时拜访了很远的中央，超过前后的 redzone 的范畴，拜访到其余局部的利用数据，而检测不出越界拜访谬误。能够通过扩充 redzone 的办法来解决，然而开销也更大。

样例代码如下：

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

查看残缺代码: 

https://github.com/dengking/s…

如果内存不是一个重大的限度，倡议应用高达 128 字节的 redzone。

3. 频繁调配、开释大量到堆内存，导致内存块过快地来到了 quarantine，因此检测不出 use-after-free 的谬误。

样例代码如下：

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’.

查看残缺代码: 

https://github.com/dengking/s…

STL Code annotation

官网文档:

https://github.com/google/san…

为了帮忙定位与 STL 相干的一些谬误，LLVM libc++ 采纳了 code annotation 技术，AddressSanitizerContainerOverflow 就是通过对 std::vector 增加 annotation 实现的。

对 STL 容器增加 annotation 的另外益处是进步 LeakSanitizer 的灵敏度。上面的示例存在一个透露，因为应用 pop_back 从全局向量中删除了一个指针，如果没有对 std::vector 增加 annotation 进行非凡实现，那么 LeakSanitizer 会将刚刚从 vector 中 pop 进去的指针视为“live pointer”，因为它依然保留在 std::vector 的存储中。

#include <vector>
std::vector<int *> *v;
int main(int argc, char **argv) {
  v = new std::vector<int *>;
  v->push_back(new int [10]);
  v->push_back(new int [20]);
  v->push_back(new int [30]);
  v->push_back(new int [40]);
  v->pop_back();  // The last element leaks now.}

调节 asan 的 resource usage 的 flag

官网文档:

https://github.com/google/san…

asan 提供了三个调节它 Resource Usage 的 run-time flag，本节将对此进行介绍。

malloc_context_size

堆栈开展的深度（默认值：30）。在每次调用 malloc 和 free 时，asan 都须要开展调用堆栈，以便当发现错误的时候，asan 输入的谬误音讯可能蕴含更多有价值的信息。此选项会影响 asan 的速度，尤其是在应用程序调用 malloc 频率较高的状况下。它不会影响内存占用和谬误发现能力。它须要被设置为一个正当值，如果设置太小，那么在检测到问题后，可能因为 stack trace 太短而无奈剖析出谬误的起因。

quarantine_size_mb

隔离区大小（默认值：256MB）。此值管制查找 use-after- free 谬误的能力，它不影响性能。

redzone、max_redzone 
heap poisoned redzone 的大小（默认值：128 字节）。此选项会影响查找 heap-buffer-overflow 谬误的能力。较大的值可能会显著减慢运行速度、减少内存使用量，尤其是在测试程序动态分配许多较小 heap memory 的状况下。因为 redzone 用于存储 malloc 调用堆栈，因而减小 redzone 会主动减小函数调用堆栈的最大开展深度。

Hardware Support

asan 的性能劣势容许在各种状况下应用。然而，对于性能要求较高的应用程序以及在二进制产物大小十分敏感的状况下，asan 的开销可能无奈承受。为了冲破 asan 自身的限度，能够思考在硬件层面实现 asan 的算法，本节对这个主题进行探讨。

硬件指令 checkN

这种形式是 asan 论文中提出的。asan 执行的检测能够被一个新的硬件指令 checkN 替换（例如，“check4 Addr”用于 4 字节拜访）。带参数 Addr 的 checkN 指令应该等价于如下程序：

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

Offset 和 Scale 的值能够存储在非凡寄存器中，并在应用程序启动时设置，这样的指令通过升高 icache 压力、联合简略的算术运算和更好的分支预测来进步 asan 的性能。它还将显着减小二进制产物的大小。

默认状况下，checkN 指令能够是空操作，并且只能由非凡的 CPU 标记启用。

Hardware-assisted asan

对于 hardware-assisted asan，参见：

https://clang.llvm.org/docs/H…

目前 clang 和 gcc 都在肯定水平上反对它。

Benchmark

https://github.com/google/san…

中进行了十分具体地比照，本文不再赘述。