Reading Papers - Memory Error Detection Overview
# Redzone-Based Approaches
# ATC'05 - Memcheck
Memcheck 以较高的代价(约 20-30 倍的 slowdown、额外 9/8 的内存)提供 bit-level 的内存错误检测。
ATC'05 - Using Valgrind to Detect Undefined Value Errors with Bit-Precision
Taxonomy : redzone-based memory error detection
Tag : shadow memory / C&C++
Memcheck 插桩一切涉及内存访问、分配、回收的函数和系统调用,维护 shadow memory 并检查内存访问的合法性。
Memcheck 所用的 shadow memory 机制如下:
为内存中的每个 bit 维护一个对应的 validity bit ,表示该 bit 是否已被良好地初始化。
为内存中的每个字节维护一个对应的 access bit ,表示该字节是否可被寻址。
Memcheck 仅对存在潜在危险的 validity bit violation 报告错误,以规避一些正常情况,例如复制结构体的 padding 数据。
Memcheck 定义了一系列一元和二元的操作来控制 validity bit 的变化,并对一些特殊情况(例如 x86 的 eflags
寄存器)进行特殊处理,具体请参阅论文原文。
# ATC'12 - AddressSanitizer
AddressSanitizer 利用压缩编码设计了更高效的 shadow memory 机制。
Taxonomy : redzone-based memory error detection
Tag : shadow memory / C&C++
AddressSanitizer 的检测方法与 Memcheck 类似,但是使用了更高效的 shadow memory 机制。
考虑 64 位机器,其地址长度为 字节,可以表示为如下 种状态之一:
表示前 个字节可访问、后 个字节不可访问。
表示整个地址不可访问,用不同的负值来区分不同类型的内存,例如 redzone 和 freed memory 等。
因此可以用 字节来表示 字节的状态,将虚拟地址空间的 用作 shadow memory 即可表示所有地址的状态。设 addr
为被测程序的某个虚拟地址,offset
为 shadow memory 的偏移量,则 shadow memory 的映射如下。对于 shadow memory 所在区域的 shadow memory ,直接将内存 munmap 掉,通过 page protection 来检测。
shadow(addr) = offset + (addr >> 3)
可以将上述基本情况视为 ,将该机制泛化为 ,此时需要虚拟地址空间的 作为 shadow memory ,形成一个 trade-off :更大的 消耗更小的内存用作 shadow memory ,但是也需要更大的 redzone 和 malloc 粒度来满足内存对齐的需求,并且由于与 64 位地址不等长,插桩的检测代码会变得复杂。
对于 字节对齐的内存访问,插桩检测代码如下:
shadow = (addr >> 3) + offset;
if (*shadow != 0)
ReportAndCrash(addr);
对于 字节对齐的内存访问,设其访问对齐为 accsize
,则插桩检测代码如下:
shadow = (addr >> 3) + offset;
if (*shadow != 0 && (addr & 7) + accsize > *shadow)
ReportAndCrash(addr);
AddressSanitizer 利用 redzone 记录 call stack ,以便于在发现错误时提供 bug report 。
TODO: malloc
函数在原本应分配的内存区域周围分配额外的内存 redzone ,此区域被标记为无法寻址或 poisoned 。redzone 越大,可检测到的上溢或下溢范围就越大。
allocator 内的内存区域被组织为与一系列对象大小相对应的空闲列表数组。当与请求的对象大小所对应的空闲列表为空时,操作系统会分配一大组带有 redzone 的内存区域(例如在 Linux 中调用
mmap
)。对于 个区域分配 个 redzone ,形如rz1 mem1 rz2 mem2 rz3 mem3 rz4
。每个内存区域左侧的 redzone 用于存放 allocator 的内部数据(如分配大小、线程 ID 等),因此 heap redzone 的最小大小为 字节。该内部数据不会被其对应内存区域的下溢访问所破坏,因为下溢动作会在实际发生之前被检测到。
除了 redzone-based detection 的固有缺陷外,AddressSanitizer 还会漏报 unaligned access 。此类错误非常罕见,但很难在不引入额外性能负载的情况下解决。
int * a = new int[2]; // 8-aligned
int * u = (int *)((char *)a + 6);
*u = 1; // Access to range [6-9]
# NDSS'18 - MEDS
MEDS 旨在改善 state-of-the-art redzone-based detection 对大型 C/C++ 程序的检测能力。
NDSS'18 - Enhancing Memory Error Detection for Large-Scale Applications and Fuzz Testing
Taxonomy : redzone-based memory error detection
Tag : shadow memory / page aliasing / C&C++
KEY Idea :结合 page aliasing 的方法,充分利用 64 位虚拟地址空间以逼近 infinite gap 的理想情况,同时使物理内存消耗尽可能小。
page aliasing 是指将一组不同的虚拟页映射到同一物理页以减少物理内存消耗的技术,有广泛的应用,例如操作系统中的 copy-on-write (CoW) 和 samepage merge 。直接将 page aliasing 用于 redzone-based detection 是不可行的,因为 malloc 的粒度通常远小于 page ,而不同对象不能被迫具有相同的虚拟页访问权限,同时导致检测时区分同一页内的合法对象和 redzone 变得复杂。
MEDS 将 malloc 的粒度提升至 page-level ,并结合 page aliasing 设计了一种 hierarchical 的 redzone 机制:
在下面的描述中,我们姑且假设对象的大小都相同,并在后续解释如何分别处理不同大小的对象。
MEDS 还采取了一系列性能优化策略:
- 将物理页根据对象大小划分为多个 free-list ,
MEDS 同样是插桩一切涉及内存访问、分配、回收的函数和系统调用,维护 shadow memory 并检查内存访问的合法性。
# General Pointer-Based Approaches
# PLDI'09 - SoftBound
SoftBound 在运行时维护每个指针的状态,并对所有涉及指针的内存读写操作进行检查,以较低的额外性能开销提供较好的 spatial memory safety 。
PLDI'09 - SoftBound - Highly Compatible and Complete Spatial Memory Safety for C
Taxonomy : pointer-based memory error detection / spatial error only
Tag : C&C++
SoftBound 为每个指针额外维护一个三元组 base
, bound
, size
,表示解引用该指针的合法地址范围 [base, bound)
和该指针类型的地址长度 size
。
SoftBound 将指针的 metadata 存储在一个独立的查找表中,不影响原始程序的内存布局。只有发生指针变量的读写时才会读写查找表,以此降低运行时开销。
- 事实上,由于 SoftBound 对函数传参的处理,栈内存的布局是会受到影响的;然而原文并没有提到这一点。
作者对 SoftBound 的内存安全性进行了形式化证明,详见论文原文。
# SoftBound 代码示例
文中所有示例代码为类 C 伪代码,但实际实现为 IR-level 的插桩。
指针解引用时的安全检查示例如下:
check(ptr, ptr_base, ptr_bound, sizeof(*ptr));
value = *ptr;
void check(ptr, base, bound, size) {
if (ptr < size || ptr + size > bound) {
abort();
}
}
指针变量创建时的状态初始化示例如下:
指针算术操作的状态维护示例如下:
int ** ptr;
int * newptr;
...
newptr = *ptr;
newptr_base = table_lookup(ptr)->base;
newptr_bound = table_lookup(ptr)->bound;
# SoftBound 处理结构体成员
对于指向 C struct field 的指针,SoftBound 将其相关操作转换为等价的指针算术运算和解引用操作。
为了检测到 sub-object overflow 错误,对于指向 C struct field 的指针,SoftBound 会收缩指针的边界,例如:
这可能会导致误报,例如:
考虑
struct point { int x, y, z; };
类型,程序可能通过x
的地址进行算术运算来操作y
和z
。Linux 内核中的各类数据结构所用的
container_of
实现。
为避免产生大量误报,SoftBound 不会为强制类型转换和数组下标收缩指针的边界。
int *
->void *
->int *
许多 C 程序会用数组成员地址表示数组的区间,例如
memset(&arr[4], 0, size)
和sort(&arr[4], &arr[10])
等。
# SoftBound 处理函数传参
由于有些 ISA 会通过寄存器进行函数传参,简单地复用 table lookup 接口不能简洁高效地解决问题。
对于返回值为指针类型的函数,改为返回额外包括 base, bound 的三元组;
对于含有指针参数的函数,SoftBound 将每个指针的 base, bound 加入函数的参数列表中,并更改所有声明和 callsite 。这种方法具有通用、ISA-independent 且支持 separate compilation 的优点。
int func(char * s);
int sb_func(char * s, void * s_base, void * s_bound);
# SoftBound 实现细节
SoftBound 将查找表实现为双字取模的哈希表,每个表项包括 tag 和 based, bound 。无哈希冲突时,单次查表需要 9 条 x86 机器指令。为提高性能,SoftBound 利用类似 shadow memory 的方式,占用一段足够大的虚拟内存(原型实现使虚拟地址空间缩小了两个 bit 的长度)作为哈希表,进行 lazy 的物理内存分配,以此保证哈希冲突永不发生。由于无需检查键值,单次查表仅需 5 条 x86 机器指令。
对于可以在编译时刻确定边界的地址(例如静态分配的全局数组),SoftBound 消除对应的 table lookup 行为并直接进行检查。
SoftBound 天然地支持对类库的安全检查,但 memcpy()
需要额外的处理以提高性能:
在复制开始前检查指针边界;
对于 callsite 参数非指针的情况,避免 metadata copy 。
对于函数指针使其 base == bound ;更完备的方案是使用额外的 signature 来区分函数指针和一般数据指针。
对于将非指针值赋值给指针的情况,默认将其 base, bound 设为 NULL(即不可访问);这在一些特殊的 C 程序中可能引起误报。目前的实现提供了额外的 setbound()
接口,用于显式设置指针边界以应对此类情况。
SoftBound 没有为可变参数列表提供安全检查支持。
# ISMM'10 - CETS
CETS 设计了 lock-and-key identifier 的方法,并在 SoftBound 工具原型的基础上实现了 temporal error detection 。
Taxonomy : pointer-based memory error detection / temporal error only
Tag : C&C++
Preceding Work : PLDI'09 - SoftBound
和 PLDI'09 - SoftBound 相同:
文中所有示例代码为类 C 伪代码,但实际实现为 IR-level 的插桩。
作者对 CETS 的内存安全性进行了形式化证明,详见论文原文。
# Lock-And-Key Identifier Approach
注意,考虑 temporal error 的性质,CETS 维护的 metadata 对于内存地址和指针变量而言是不同的,要严格区分。
CETS 为每个指针额外维护 allocation key
和 lock address
,并在全局额外维护一组 lock location
。
allocation key
是每个(动态分配的)内存区域的唯一标识符,在内存分配时通过全局的 64-bitnext_key
计数器赋值。零值保留作为INVALID_KEY
。lock address
是指向某个lock location
的指针。INVALID_LOCK_ADDR
是预设的某一特定非零值,用于暴露 temporal error 。lock location
……
在分配新内存时,CETS :
为新的内存区域赋予唯一的
allocation key
;分配一个新的
lock location
,并将其赋值为该内存区域的allocation key
的值;为对应新赋值的指针变量初始化 metadata 。
# CETS Pointer Metadata
指针变量的状态初始化示例如下:
# CETS Metadata 查找表
和 PLDI'09 - SoftBound 相同,CETS 将指针的 metadata 存储在一个独立的查找表中。但对于 temporal error 而言,查找表的设计和实现更复杂,且对性能的要求更高(可能是因为检查更密集?)。
概念上,CETS 的查找表是从 指针变量的地址 到指针变量的 metadata (allocation key, lock address)
的映射。
CETS 的查找表实现是一个类似于 two-level page table 的数据结构:
CETS 的工具原型假设运行环境有 48 位虚拟地址空间,且地址是 word-aligned 的;所以有 45 bit 可用于查找表索引。
高 22 位用于索引一级表,每个一级表项指向一个二级表。
低 23 位用于索引二级表,每个二级表项指向一个 metadata 二元组(每个占用 128 bit 内存)。
每次查表操作需要 11 条 x86 机器指令。
通过读写内存传递指针值时需要索引 metadata 查找表,例如从内存中读取指针值的代码示例如下:
# CETS 多线程
CETS 工具原型不支持多线程,但其方法允许支持多线程:
- 将
allocation key
的取值范围划分给每个线程(考虑到线程的创建和销毁,这应该没有原文描述的这么简单?),使用 thread-local 的next_key
计数器,以及 thread-local 的lock location
内存池。
然而这蕴含了 race-free 的假设;实际上,CETS 可能面临以下两类 data race :
在 temporal check 和实际内存操作之间,另一线程释放了该内存对象;
通常的指针读写冲突。
为所有 metadata 操作上锁会引入很大的线程同步 overhead 。因此,作者建议仅为那些声明为 atomic 或 volatile 的指针变量上锁,以保证不会导致程序违背其本来遵守的 C memory model ;对于其它情况,CETS 不负责检查并发错误,隐式地认为这应该交给其它工具来解决。
# CETS 消除冗余检查
CETS 的去冗余优化可以分为两类:
removal of unnecessary checks
对于函数调用期间从 stack pointer 直接派生出的任何指针值,因为 stack frame 的生存期是函数执行的周期,所以 temporal check 是不必要的。
对于确定指向静态分配的全局对象的指针,因为其生存期是进程本身,所以 temporal check 是不必要的。CETS 使用简单的数据流分析识别并消除对这些指针的 temporal check 。
removal of redundant checks
若满足以下两个条件,则 temporal check 是冗余的:
存在一个更早的、对该指针或其它指针的检查,被检查的指针与当前指针具有相同的
allocation key
和lock address
;这一更早的检查没有被
free()
所清除。
CETS 通过构建 dominator tree 并进行标准的数据流分析来识别这些冗余检查:如果当前检查被另一更早的检查所支配,则将其消除。
- CETS 工具原型仅进行过程内分析,保守地认为路径上的任意函数调用都会清除所有更早的检查。可以改用更精确的分析方法,例如识别所有可能调用
free()
的函数。
discussion
temporal check 的冗余消除相比 spatial check 有显著不同:
对于 temporal check ,即便两次内存读取操作访问了不同的地址,也可能存在冗余检查;而这种情况下的 spatial check 通常不会冗余。
两次 temporal check 之间的代码可能会阻断其冗余性质,而两次 spatial check 之间的代码与其是否冗余无关。
# NDSS'15 - DangNull
DangNull
Taxonomy : pointer-based memory error detection / temporal error only / use-after-free
Tag : C&C++
# Low Fat Pointers
# NDSS'17 - LowFat
LowFat
Taxonomy : pointer-based memory error detection / low fat pointers / --
Tag : C&C++
# EuroSys'18 - Delta Pointers
Delta Pointers 针对 buffer overflow 这一类错误,利用二进制算术运算来隐式地实现越界检查,消除传统 pointer-based approach 的分支检查,从而达到足以在生产环境部署的性能优势。
Taxonomy : pointer-based memory error detection / low fat pointers / spatial error only / buffer overflow
Tag : C&C++
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01