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 由两部分组成：

Sanitizers 系列之 address sanitizer 原理篇

经过上述内容能够看出：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 区域标记为不行拜访然后确保能够及时发现过错。

Sanitizers 系列之 address sanitizer 原理篇

  • 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、storevariable = *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、storevariable = *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 的转化：

Sanitizers 系列之 address sanitizer 原理篇

在上述比如中，asan 运用 poisoned redone 完成对 stack objecta的保护。

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=newint[2];//8-alignedint*u=(int*)((char*)a+6);*u=1;//Accesstorange[6-9]，

u = 1便是典型的“unaligned access that is partiallyout-of-bounds”。检查完好代码：

github.com/dengking/sa…

现在 asan 忽略了这种类型的过错，因为一切提出的解决方案都会减慢通用程序履行途径。

  1. 越界拜访时拜访了很远的地方，超过前后的 redzone 的范围，拜访到其他部分的运用数据，而检测不出越界拜访过错。能够经过扩展 redzone 的方法来解决，可是开支也更大。

样例代码如下：

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

检查完好代码:

github.com/dengking/sa…

假如内存不是一个严重的限制，主张运用高达 128 字节的 redzone。

  1. 频繁分配、开释大量到堆内存，导致内存块过快地离开了 quarantine，因此检测不出 use-after-free 的过错。

样例代码如下：

char *a = new char[1 << 20]; // 1MBdelete[] a;                  // <<< "free"char *b = new char[1 << 28]; // 256MBdelete[] b;                  // drains the quarantine queue.char *c = new char[1 << 20]; // 1MBa[0]=0;//"use".Maylandin’c’.

检查完好代码:

github.com/dengking/sa…

STL Code annotation

官方文档:

github.com/google/sani…

为了协助定位与 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

官方文档:

github.com/google/sani…

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，拜见：

clang.llvm.org/docs/Hardwa…

现在 clang 和 gcc 都在一定程度上支撑它。

Benchmark

github.com/google/sani…

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