ReZZan:Efficient Greybox Fuzzing to Detect Memory Errors

1. 引言

  • 内存错误是安全漏洞的常见来源

    • 赋予攻击者更改内存内容的能力，可能会构成信息泄露和控制流劫持

  • 内存错误的静默性：

    • 内存错误不一定会导致程序立即崩溃
    • 进行插桩监控内存情况：Sanitizer（e.g. AddressSanitizer）

  • fork模式的模糊测试 + 内容错误sanitizers = 显著的性能开销

    • AFL+AddressSanitizer：吞吐量降低了约58%
    • 性能下降的原因：sanitizer的实现与模糊测试过程之间的不利交互
      • 传统sanitizer使用disjoint metadata来跟踪内存状态
      • 维护disjoint metadata会引入额外的开销

  • 基于LBC和REST等工具首创的随机化嵌入式令牌（RET）的思想来对内存sanitizer进行设计

  • ReZZan = REt + fuZZing + sANitizer

    • 在fork模式的模糊测试下速度明显更快
    • 1.27 × 原生AFL的运行（AddressSanitizer 2.36 x ）
    • 额外提供一种简化配置，无需精确的边界检查，开销为1.14 x

1.1 贡献

  • 提出了一种基于随机嵌入令牌（RET）概念的内存错误sanitizer的设计

  • 调整设计，无需使用disjoint metadata；此外介绍了在基于RET的设计下用于字节精确内存错误检测的精细边界检查的概念

  • 以ReZZan工具的形式实现了该设计，并将ReZZan与流行的灰盒模糊器集成在一起

  • 对ASAN和FuZZan进行比较，显示该方法的优越性

  • 项目开源：https://github.com/bajinsheng/ReZZan

2. 背景

模糊测试：

  • fork server：

内存错误Sanitizers：

  • 专用Sanitizer和通用Sanitizer

    专用Sanitizer：

    • Stack金丝雀专门用于堆栈缓冲区溢出
    • LowFat和轻量级边界检查（LBC）专门用于溢出/下溢
    • FreeSentry专门用于UAF

    通用Sanitizer：

    • AddressSanitizer：字节级精度检测所有类型的内存错误

  • 内存错误检测可能是部分检测或不精确检测：

    • GWP-ASAN仅对随机选择的堆对象应用保护
    • LowFat/REST允许小的溢出（不与其他对象相交，即不影响其他对象变量值）

  • AddressSanitizer：

    • 实施一种内存投毒（memory poisoning）的方法，其基本思想是：当使用一个内存错误能够访问该内存时，该内存则别标记为“中毒”，包括：

      • 对每个有效分配对象之间插入的小的REDZONE区域进行标记，该区域用于检测对象边界溢出/下溢错误
      • 对free()的内存进行标记来检测UAF错误

    • 使用运行时支持库来1⃣ 在已分配对象之间插入redzone并对其标记；2⃣ 对free()的内存进行标记

    • 对所有内存访问操作进行插桩，以检测内存是否中毒：

      1
      2
      3
      if ( poisoned ( p )) // Instrumentation
      	error ();
      * p = v ; /* or */ v = * p ; // Access

  • AddressSanitizer的内存投毒：

    • 将程序的虚拟地址空间分为两个部分来实现内存投毒：应用程序内存(application memory) 和 影子内存(shadow memory)

    • 影子内存用以跟踪应用程序内存中每个字节的中毒情况。因此，应用程序内存每8个字节都将映射到相应的影子字节，i.e. $addr_{shadow}=offset_{shadow}+(addr/8)$，这里的影子内存其实就是disjoint metadata的一种表现

    • disjoint metadata（i.e. 一种额外的metadata）：1⃣ 由Sanitizer维护；2⃣ 与应用程序内存/数据分离

      • 会带来额外的内存开销
      • 影响了内存位置（i.e. 应用程序和影子内存是分离的）

  • 内存投毒的替代实现——RET（随机化嵌入令牌）：

    • poisoned内存由一个特殊的令牌表示，该令牌初始化为某个预定的随机数值，如果内存直接存储该随机值，则认为内存“中毒”了

      1
      poisoned(p)=(*(p-p%sizeof(Token))==NONCE)

    • 如果NONCE值与程序正常执行期间创建的合法值冲突，则可能会发生错误的检测

    • REST使用一个非常大的令牌大小（整个512位缓存线）和一个强大的伪随机源

      • 大型（多字节）令牌会导致内存错误检测粒度降低（粗粒度）

      • e.g. 给定REST 512位（64字节）令牌，对malloc(27)的调用将：

        (1) 将分配大小增加 64 - 27 = 37 字节

        (2) 分配已对齐了一个64字节的对象

        (3) 在64..127字节处存储一个token值来实现redzone

        i.e. 27..63字节的溢出都不会访问令牌，即不会判断为内存错误，因此REST不是字节精确的

    • RET思想最早被LBC所使用，不像REST，LBC使用单字节（8位）令牌大小，允许进行字节精确的内存错误检测，但这也意味着碰撞不可避免；为了避免碰撞，LBC实现了一种混合方法，该方法保留了disjoint metadata，以区分冲突和合法的内存错误

问题描述：

  • 现象：模糊测试和Sanitizer应该协同工作，但在实践中，模糊测试和Sanitizer的组合性能较差

  • 根本原因：fork()系统调用的写时复制（copy-on-write COW）语义与Sanitizer对于任何disjoint metadata的初始化/使用之间的交互

    • 子进程因发生页面错误而拷贝页
    • fuzzing + sanitizer会导致页面错误的激增：一个用于已分配的对象，另一个用于disjoint metadata

  • AddressSanitizer还引入了与fork()相关的其他开销，e.g.复制内核数据结构（包括虚拟内存VMA、页表和相关拆卸开销）

解决办法：

  • 一个想法是选择一个具有低内存开销和高局部性的内存错误Sanitizer
  • 另一个想法是优化disjoint metadata的表示

2.1 我们的设计

  • 提出一种基于随机化嵌入令牌（RET）的变体，该变体不使用影子内存或其他disjoint metadata表示

  • 关键思想是通过使用内存本身跟踪中毒状态

    • 避免任何的其他页错误（由disjoint metadata的初始化或访问导致的）
    • 插桩检查和相应的内存操作不会带来额外的页错误

  • 设计的主要元素总结如下：

    1⃣ 令牌大小

    • 某些现有的工具基于RET设计，如RESR（令牌大小512位）和LBC（令牌大小8位）
    • 见解：对于模糊测试应用，可以容忍一些小级别的错误检测
      • medium 令牌大小：64位
      • 使用不同的随机化NONCE值重新执行测试用例可以在一定程序上减轻错误检测的开销

    2⃣ 内存错误检测粒度

    • 在基本的RET设计下，tokens需要存储在token大小对齐的边界上，也就是说64位tokens需要进行8字节对齐
    • 对RET进行改进：对象边界信息直接编码到令牌表示本身中

    3⃣ 硬件

    • REST：无标准硬件扩展；LBC：32位x86系统
    • 本文提出的基于RET的设计：针对标准硬件（x86_64）和标准模糊器设计

3. 基本内存错误检测

  • 使用以下结构类型来定义RET：
1
struct Token { uint64_t random; };

1⃣ 插桩模式：

  • 基本方法：转换程序（e.g.使用一个LLVM编译器基础设施pass）来在每个内存访问之前插入插桩代码
  • 插桩内容：检查是否违反给定的安全属性（在设计的sanitizer中，该安全属性是相应访问的内容是否被poisoned）

🌰:

第4行内存间接引用不会产生任何其他页错误，而第5-6行的错误检查访问内存以检索存储在全局变量中的NONCE值，而NONCE存储在单个位置，因此这里最多会额外产生一个页错误

2⃣ 运行时支持：

  • 加强内存安全，修改了运行时环境以毒化redzone和free内存

  • 每一个对象类处理方式不同：

    堆分配对象：e.g. malloc, realloc, new等都被替换成为每一个分配目标后添加了redzone的版本，redzones的实现与其他内存错误sanitizer相似，但也有不同：

    1. Poisoning是通过将NONCE-初始化令牌直接写入redzone内存来实现的
    2. redzone的大小是1个或者2个tokens（取决于对齐）
    3. redzone放置在目标的最后，通过前一个对象的redzone来检测Underflows

    实现了一个简单的自定义内存分配器：连续分配目标

    堆内存释放：释放的目标相应内存填充为一个NONCE-初始化的token；维护了一个隔离区（本质上是一个队列），隔离区存放了释放的内存目标，目的是延迟重新分配，从而更可能检测到reuse-after-free。从隔离区删除对象以便重新分配，相应的内存在使用前清零以“unpoison”该内存。

    栈分配对象：使用LLVM pass实现转换

    1. 修改分配大小：包含原始分配的大小和一个redzone内存
    2. redzone内存将写入一个NONCE-初始化token，剩余内存全部置0

    全局变量： 使用LLVM pass实现转换

    具体操作和栈分配对象相似，不再赘述

4. 改进的边界检查

  • 基本思想：除了随机化的NONCE之外，还将对象边界信息编码存进嵌入令牌中，该边界信息可以在运行时检索

  • 包含两个组件：

    • random：NONCE值
    • boundary：目标边界的编码形式：
    1
    size mod sizeof(Token)  // size是目标的大小

  • 改进的令牌是由具有两个位字段的结构表示：

    1
    2
    3
    4
    struct Token {
    	uint64_t random :61; // NONCE
    	uint64_t boundary :3; // Boundary encoding
    };

    boundary字段至少需要3位来表示所有可能的边界值，那么random字段就只能缩减为61位（64-3）

  • 使用额外的边界检查对内存访问进行插桩，基本思想如下图所示：

🌰 假设目标大小不是一个令牌大小（8字节）的整数倍，e.g. (size mod sizeof(Token)) = 5，也就是要使用一个额外的sizeof(Token)-5=3字节的填充，在该填充中的溢出无法被基本的RET检测到，为了检测到这种溢出，我们对内存访问进行插桩以实施一个额外的边界检测：

  1. 检查内存中当前word的下一个word[8字节]

  2. 如果下一个word不是一个token(i.e.随机比特与NONCE不相同)，那么内存访问是允许的

  3. 否则，检索边界字段并将其余内存访问范围 $lb…ub$ 进行比较，当下面条件不成立时，即发生了越界操作：

由于检查的是下一个word，因此基本上绕过了填充空间不足的问题，在图3的示例中，任何与填充重叠的内存访问都不会满足，因此可以检测到溢出

插桩模式：

  • 图2的第9-13行为边界检查的插桩，这里假设该内存访问已经通过RET检查，保证了ub不包含token

下一个word可能位于不同的页面，因此可能无法访问。这可以通过禁用对页边界的精确检查来进行处理，随之带来的就是精确度的降低；或者所有映射都可以通过一个NONCE-初始化页进行扩展，可以通过使用信号处理器来检测边界检查引起的故障，然后“按需”扩展相应的映射来实现

5. 实验设置

  • x86_64上实现了REt+fuZZing+sANitzer（ReZZan）：

    • ReZZan：细粒度内存错误检测，包括RET（第三节）和字节准确的边界检测（第四节）
    • ReZZanlite：减弱粒度的内存错误检测，仅包括RET。此版本速度更快，但无法检测到对象填充中的某些溢出

  • ReZZan的实现包括两个部分：

    • LLVM Pass：
      • 转换所有内存操作（e.g. load/store）以插入RET和边界检查插桩。对于ReZZanlite来说，边界检查将被忽略
      • 将所有栈分配操作（e.g. alloca）和全局变量转换为使用redzone保护的新版本
    • 运行时库：
      • 实现了替换堆分配函数（例如malloc、free等），替换的函数可以插入redzone以及poison释放的内存

研究问题

  • 主要假说：基于RET的消毒剂设计可以

    1. 在模糊测试环境下表现出较低的性能开销
    2. 实现与更传统的Sanitizer设计（如ASAN）类似的内存错误检测能力

  • 六个研究问题：

序号 描述
RQ1 - 检测能力 ReZZan是否检测到与ASan相同类型的内存错误？
RQ2 - 执行速度 在模糊测试环境下，ReZZan比ASan快多少？
RQ3 - 分支覆盖 ReZZan的分支覆盖范围与ASan相比如何？
RQ4 - 漏洞发现有效性 与ASan相比，ReZZan可以更快地暴露bug吗？
RQ5 - 灵活性 ReZZan可以用来模糊大型程序吗？ReZZan与其他模糊器兼容吗？
RQ6 - 误报 ReZZan在实际执行环境中的错误检测率是多少？

基础设施

实验环境：

  • Intel Xeon CPU E5-2660v3：28个物理内核、56个逻辑内核，2.4GHz
  • 64GB RAM
  • Ubuntu 16.04（64位）LTS（最大利用率为26个内核）

基线：

  • ASan（LLVM-12）、FuZZan（具有动态元数据结构切换模式）
  • ASan和FuZZan都：
    1. 仍在维护
    2. 支持x86_64
    3. 可以与现有的模糊器集成

模糊测试引擎：

  • AFL（v2.57b）
    • 是大多数现代模糊器的基础
    • 评估所使用的所有sanitizer都支持

基准套件：

  • RQ1：Juliet基准套件
  • RQ2/RQ3：cxxfilt、nm、objdump、size（均来自binutils-2.31）、file（来自coreutils版本5.35）、jerryscript（版本2.4.0）、mupdf（版本1.19.0）、，libpng（版本1.6.38）、openssl（版本1.0.1f）、sqlite3（版本3.36.0）和tcpdump（版本4.10.0）
  • RQ4：谷歌的fuzzer-test-suite2

选择相同的初始种子语料库，如果没有提供输入则使用空文件

实验设置：

  • 每个实验进行24小时，重复20次

6. 评估结果

RQ1⃣ 检测能力

  • ReZZan和ReZZanlite对于underflow detection的检测性能略低于ASan，这是因为ASan默认为堆栈对象使用double-wide（32字节）红区。当ReZZan配置类似时，也能100%检测下溢错误

对于Juliet测试套件中的内存错误错误（CWE 121、122、124、126、127、416），ReZZan和ReZZanlite分别通过99.04%和87.89%的坏测试用例

RQ2⃣ 执行速度

  • 页错误

当与模糊测试相结合时，ReZZan（1.27×）和ReZZanlite（1.14×）的开销低于传统的Sanitizer ASan（2.36×）和FuZZan（2.00×）。ReZZan和ReZZanlite的性能与没有任何内存错误sanitization的模糊测试相当，页面错误的数量也是如此.

RQ3⃣ 分支覆盖

平均而言，ReZZan和ReZZanlite实现了与Native类似的分支覆盖。ReZZan的模糊化活动在24小时内探索了比ASan多5.54%的代码分支。

RQ4⃣ 漏洞寻找有效性

ReZZan比ASan快3.68倍。在实践中，ReZZan还可以检测到比ReZZanlite更多的错误。

RQ5⃣ 灵活性

  • 模糊器的支持：

    • 与AFL++集成：

  • 持久模式模糊测试：

    • FuzzBench提供的harness作为测试对象
    • ReZZan和ReZZanlite的性能略有下降
    • 结果表明：1. ReZZan可以应用于fork模式和持久模式；2. ReZZen在较长运行时间内的其性能最终将接近ASan

  • 可扩展性：

    • 考虑到Firefox的规模，与其他基准相比，总体模糊吞吐量要慢得多。尽管如此，ReZZan和ReZZanlite仍以112.60%和114.86%的改善率优于ASan

    • 证明ReZZan是可扩展的

RQ6⃣ 误报

  • ReZZan设计允许少量误报
  • 实验包括超过19200小时（≈2.2年）CPU时间，在此期间没有观察到误报
  • 预期是数十年的CPU时间才可能观察到第一次误报

我的看法

⭐ 亮点：

  • 论文分析了现有Sanitizer与基于fork模式的模糊器结合时对模糊测试性能的影响，主要体现在：1. COW机制导致频繁的页错误；2.disjoint metadata，因此与fork()兼容性不好
  • 论文提出了基于RET和改进的细粒度边界检测的Sanitizer——ReZZan，并通过详细的实验论证ReZZan的性能
  • 实验部分很详细
  • 项目开源：https://github.com/bajinsheng/ReZZan

不足：

  • 仅支持llvm-12，而且wrapper的一些细节处理不是很好
  • 目测应该不会有ASan那么详细的错误报告，也就是说ReZZan仅会异常结束程序，还需要使用ASan查看具体是何种漏洞类型（待验证）
#论文阅读
ReZZan:Efficient Greybox Fuzzing to Detect Memory Errors
http://bladchan.github.io/2023/01/10/ReZZan/
作者
bladchan
发布于
2023年1月10日
许可协议