文章发表于 ASPLOS’24，

本文的工作

基于 ASan 的原理，对其进行了改进，提出了 GiantSan，其主要的改进点在于，将连续的内存块进行合并，从而减少了运行时内存检测的开销，并对内存检测结果进行了缓存，使其能够在后续的访存中，直接从缓存中读取结果，从而减少了运行时的开销。通过和 ASan 以及 ASan-- 的对比，证明了 GiantSan 在性能上的优势。

ASan 的原理

在开始介绍 GiantSan 之前，我们先来了解下 ASan 的原理，正如前文所说，ASan 是一种内存检测工具，其工作涉及到编译时以及运行时两个阶段。

编译时主要的工作是在栈对象以及全局对象前后插入一些特殊的内存区域，称之为 poisoned redzone 用于检测访存越界，同时对访存有关的指令进行了替换，在访存前后检测对应内存区域的状态码，如果发现异常，则会记录并在程序退出时输出。

运行时工作则主要针对的是堆对象，其实现了一个特殊的堆分配器，将 malloc/free 替换为了自己的实现，具体替换的这里并不展开，与 Linux 的动态链接库加载有关，有兴趣的可以自行查阅。这里类似的，也是在分配的内存前后插入了 poisoned redzone，用于检测溢出，同时也有类似的状态码机制；额外要提及的还有对于 free 后的内存进行延迟释放，用于检测 UAF(Use After Free) 的情况。

上文所将的内存状态码存储的区域被称为 shadow memory，其对应关系为 8 Byte 的内存(segment)对应 1 Byte(8 bit) 的 shadow memory，用于存储对应内存的状态码。选取 8 Byte 的原因是因为大部分现代计算机的内存访问都是以 8 Byte 对齐的。这样我们可以得知，内存地址 Addr 对应的 shadow memory addr 为 Offset + (Addr >> 3)，其中 Offset 为 shadow memory 的起始地址。

接着，对于 shadow memory 的状态码(shadow encoding)，其主要有以下几种：

0x00: 整个 8 Byte 的内存块都是可以访问的
0x01-0x07: 对应的 8 Byte 内存块的前 1-7 Byte 是可访问的
任意负数，例如 0xFA，这些状态码表示对应的 8 Byte 内存块是不可访问的，并使用不同的状态码来表示不同的情况，如 global redzone, heap redzone 等

之后在每次访问内存时，都会检查对应的 shadow memory 的状态码。

GiantSan 的工作

通过上文对 ASan 的原理介绍不难发现发现，ASan 的 shadow memory 机制存在一个问题，考虑一个极大的内存块，例如 1GB，那么对应的 shadow memory 就需要 128MB，假设程序对其进行了遍历操作，那么就需要对 128MB 的 shadow memory 进行访问，这样会导致大量的内存访问，从而导致程序性能的下降；可能单次访问开销并不显著，但是，这样的开销在每一次访存时都会发生，例如我们申请内存后，进行 memset 操作，那么就会对 shadow memory 进行大量的访问，从而导致性能的下降。

那么这一问题的根源在于，ASan 的保护粒度过于细了，每 8 bit 只能保护 8 Byte。具体来说，考虑一个内存片段 $[L, R)$ ，这里假设访问是 8B 对齐的，即 $L \equiv 0(mod \ 8)，$ ASan 会对其进行 8 Byte 的划分，此时访问这片内存所需要的 shadow memory 的访问次数为 $\lceil \frac{R - L}{8} \rceil$ ，这样就会导致大量的访问。

为了解决这个问题，GiantSan 提出了 Segment Folding 的方法，其主要思想是将 shadow memory 的保护粒度进行合并，即将多个 8 Byte 的内存块合并为一个 segment，从而减少了对 shadow memory 的访问次数。具体来说，对于一个内存片段 $[L, R)$ ，GiantSan 会将其划分为多个 segment，每个 segment 对应 $n \times 8$ Byte 的内存块，这样就可以减少对 shadow memory 的访问次数，下面我们详细介绍下 GiantSan 是如何实现的。

Folded-Segment

GiantSan 将多个连续的可访问的 segment 合并为 folded-segment，并根据合并的 segment 的数量，对应的 shadow memory 的状态码进行编码，这样就可以减少对 shadow memory 的访问次数。文中将这些合并后的 folded-segment 称之为 (x)-folded-segment，其中 x 为合并的 segment 的度，其表示这个 folded-segment 由 $2^x$ 个 segment 合并而成。

Shadow Memory Encode

编码上，首先对所有的可能情况进行下分类，类似 ASan，可能有 partial，即一个 8 Byte 中只有从头开始的 x 可用；folded-segment，即多个 segment 合并为一个 folded-segment；以及 unreachable，即不可访问的内存块，这部分还有 ASan 中的一些情况，这里不再赘述。

先考虑 folded 的情况，上文提到，GiantSan 的 folded-segment 是以二进制指数形式进行表示的，而目前绝大多数 64 位操作系统对于内存申请上都有一个申请上限，即 $2^{64}$ Byte，这样，folded 的状态码只需要 64 个即可，而对于 partial 的情况，其状态码则需要 7 个，这样就可以减少对 shadow memory 的访问次数，因而这里使用了 uint8_t 来存储 shadow memory 的状态码。

GiantSan 对于 shadow memory 的状态码的编码如下：

folded-segment 的状态码为 $64-i$ ，其中 $i$ 为 folded-segment 的度
partial 的状态码为 $72-i$ ，其中 $i$ 为 partial 的度
unreachable 的状态码大于 $72$ ，具体的状态码不再赘述

如此，每个内存块的状态码都是唯一的，且内存块可访问大小越大，对应的状态码越小。

具体解释

这里对这个 folded-segment 进行进一步的解释，如下图

一个 68 Bytes 的内存示意

这里 shadow memory 的数值表示的是对应的 segment 的度，例如第一个 8B 对应的 shadow value 是 3，表示这个 8B 对应的 segment 的度为 3，即这个 8B 对应的 folded-segment 由 $2^3 = 8$ 个 8B 合并而成，这里我们需要注意的事是，一个 (x)-folded-segment，其表示从当前的地址开始，往后有至少 $8 \times 2^x$ 个 Byte，至多不超过 $8 \times 2^{x+1}$ 个 Byte 是可访问的，这里的至多是因为，可能存在 partial/多余的 segment 不足以令当前的度增加。

同时一个值得注意的点是，对于一个 (x)-folded-segment，其总是有 $2^i$ 个 (i)-folded-segment，其中的 $0 \leq i < x$ ，这点是因为其采用的二进制指数的表示方式决定的。

确定地址有效

内存访问的安全性问题可以转换为这样的一个问题，给定任意的地址区间 $[L, R)$ ，我们需要确定这个区间内的所有地址是否都是可以访问的，这里便是 GiantSan 所作的核心，这里直接把其算法展示如下：

GiantSan 算法

在讲解这个算法前，先确定下如何根据 shadow memory 的值来判断是否有效，大致分为两种情况：

partial：即 $R-L < 8$ ，这种情况下，只需要判断 $L$ 对应的 shadow memory 的值是否大于等于 $72-(R-L)$ 即可
folded：这种情况下， $R-L \geq 8$ ，这种情况下，一个最好的情况是该内存块是一个 (x)-folded-segment，其中 $x > \lceil log_2(\frac{R-L}{8}) \rceil$ ，简单转换下，即 $8 \times 2^x \geq R-L$ ，这样就可以保证这个区间内的所有地址都是可访问的；而另一种情况，为了方便后续讨论，这里记 $t = \lfloor log_2 \lfloor \frac{R-L}{8} \rfloor \rfloor$ ，那么上一种情况实际即为 (t+1)-folded。而对于 (t)-folded-segment，根据 $t = \lfloor log_2 \lfloor \frac{R-L}{8} \rfloor \rfloor$ ，我们可以知道 $L + 8 \times 2^t \le R \le L + 8 \times 2^{t+1}$ ，且根据对应的 folded-segment 的性质，我们已经知道了 $[L, L+8 \times 2^t)$ 是可访问的，那么剩下的问题便是 $[L+8 \times 2^t, R)$ 是否是可访问的。而 $0 \le R-(L+8 \times 2^t) \le 8 \times 2^t$ ，这意味着，这剩下的片段刚好是一个 (t)-folded-segment 所能容纳的，即如果存在一个以 $R$ 为结尾的 (t)-folded-segment，那么 $[L+8 \times 2^t, R)$ 也必然是可访问的。

从而我们总结下，对于一个区间 $[L, R)$ ，其是否是可访问的，我们只需要判断 $L$ 和 $R$ 对应的 shadow memory 的值是否满足上述条件即可，而无需对区间内的每个地址进行判断。

下面对照上面的算法进行解释：

1~3 行：判断是否是 (t+1)-folded，如果是，则直接返回可访问，不进行后续的判断。
4~10 行：分别进行判断是否有以 L 开头的 (t)-folded-segment，以及以 R 结尾的 (t)-folded-segment，如果有任意一个不满足，报错，否则返回可访问。
12~13 行：判断是否是 partial，如果是，检查可用是否满足，否则报错。

缓存

有了高效的检索内存区间是否有效的方法后，我们还希望能够进一步减少检索的次数，例如在一个 for-loop 中，考虑一个 int64_t 的数据，每次访问都需要检查其是否有效，这样会导致大量的检索，为了降低这种循环中检索，GiantSan 提出了一种缓存机制，通过缓存上一次的检索结果，来减少检索的次数。

具体来说，考虑这样的一个代码

int *y = new int[SIZE];

for (int i = 0; i < N; ++i) {
    y[i] = do_something();
}

不考虑缓存的时候，会将其转换为如下的代码

int *y = new int[SIZE];

for (int i = 0; i < N; ++i) {
    CHECK(y+i*sizeof(int), y+(i+1)*sizeof(int)); // 检查 y[i] 的4个字节是否有效
    y[i] = do_something();
}

而考虑缓存后，会将其转换为如下的代码

int *y = new int[SIZE];

for (int i = 0; i < N; ++i) {
    uint64_t ub = 0;
    if (sizeof(int) * i >= ub) {
        CHECK()
        ub = ...;
    }
}

这样就可以减少对 shadow memory 的访问次数，从而提高程序的性能。

基于基地址的检索

这部分主要是针对 redzone 的优化，具体来说，ASan默认的 redzone 设置为 32 Byte，redzone 的设置主要是为了检测内存越界，例如对于一个 int 数组，假设其大小为 SIZE，那么 ASan 会在 int[SIZE] 的前后面插入 32 Byte 的 redzone，这样就可以检测到内存越界的情况。

但是，如果说 redzone 的大小过小，那么就会导致无法检测到一些内存越界的情况，例如对于一个 int 数组，如果访问了 int[SIZE+64]，并且刚好这个位置是可访问的，那么 ASan 就无法检测到这种情况。

而 GiantSan 是基于基地址的检索，即对于一个内存块 $[L, R)$ ，其检索的基地址为 $L$ ，这样就可以检测到这种情况，从而提高了检测的准确性。

论文阅读笔记-GiantSan: Efficient Memory Sanitization with Segment Folding

相关背景