今天要为大家推荐的论文是来自USENIX Security 2024的Data Coverage for Guided Fuzzing，由清华大学WingTecher 团队完成并投稿。

1. 代码覆盖和模糊测试 

今天来聊聊模糊测试中的一个经典话题——代码覆盖率。作为软件测试中的重要技术，代码覆盖率具有不可忽视的地位。简单来说，要找到程序中的 bug，首先需要确保测试覆盖到相关的代码段，这就是代码覆盖率的意义所在。特别是在导向式模糊测试（Guided Fuzzing）中，代码覆盖率的作用尤为显著。 

提到代码覆盖率的具体实现，不得不提到 2014 年面世的 American Fuzzy Lop（AFL）。AFL 巧妙地将代码覆盖率转化为控制流特征，并用一个固定大小的计数器数组来存储这些特征。数组的索引代表不同的控制流转移（例如，if-then 和 if-else 就会有两个不同的计数器索引）。数组中计数器的值则代表控制流的转移次数（例如，for 循环执行了 100 次）。这种设计将程序执行的空间和时间特征转换为一个简单的数组，既高效又实用。 

2. 代码覆盖：局限及改进 

然而，代码覆盖率并非万能。特别是对于涉及数据的程序构造，它的效果就显得力不从心。例如，在各种程序中广泛存在的“魔法数字”就给代码覆盖率带来了挑战。举个例子，在 LCMS 色彩管理引擎中，有这样一段代码：

这段代码看起来简单，就是检查一个魔法数字。然而，对于代码覆盖率来说，这就成为了一个难题。它只能告诉我们测试是否通过，却无法反映我们猜测的值离正确答案有多近。结果是测试工具只能像无头苍蝇一样乱撞，猜对的概率仅为 $2^{−32}$，大约需要试验 30 亿次才能有 50% 的成功率。按每秒 1000 次执行速度计算，大约需要一个多月的时间。 

面对这一挑战，研究人员并没有闲着。他们主要采用了两种方法：符号执行和智能分支求解。 

符号执行（Concolic Execution）的思路是将约束条件表示成符号表达式，然后交给 SMT 求解器进行求解。以刚才的例子为例，我们可以将输入的 4 个字节表示为 4 个 8 位向量，然后根据程序执行过程逐步更新这些值的符号表示。通过对 (assert (and (= input3 #x70) (= input2 #x73) (= input1 #x63) (= input0 #x61))) 进行求解，就能得到一个具体的输入值，从而满足所有约束条件。 

智能分支求解（Intelligent Branch Solving）则采取了另一种方法。自 2016 年 Kostya Serebryany 在 libFuzzer 中首创了 “trace_cmp” 分支求解模式以来，这种方法已成为解决魔法数字问题的主流方法，并影响了 Redqueen、AFL++ 等一系列工具。相比难以部署且执行缓慢的符号执行方法，智能分支求解采用启发式方法“猜测”哪些输入字节会影响约束条件，然后有针对性地修改这些字节。例如，在刚才的例子中，我们可以发现前 4 个字节影响了分支判断，期望值是 0x61637370。那么，我们可以直接将这 4 个字节替换成期望值，从而有效解决问题。 

3. 数据：代码覆盖难以捕捉的程序信息 

图灵奖得主 Niklaus Wirth 曾说过，“算法 + 数据结构 = 程序。” 换句话说，程序是基于特定数据的表示和结构的抽象算法的具体形式。从编程语言实现的角度来看也是如此：当编译器将源代码转换成机器码时，算法被转化为机器指令 ，而数据结构则被编码为常量数据 。 

除代码外，常量数据在程序构造中也扮演着重要角色。常量数据有两种物理形式：立即数和静态值。 

• 立即数：这些数据非常简单，通常直接嵌入在代码中。例如，在 C 语言中，代码 ptr = 0x1234abcd 会被编译成 x86 机器码 c7 00 cd ab 34 12=，其中立即数 =0x1234abcd 被嵌入为机器码的最后四个字节。 

• 静态值：这些数据更复杂，具有更高的表达力。在 C 语言中，字符串、静态变量和全局变量都是静态值的例子。这些值可以编码复杂的结构并传达复杂的语义，包括数组、链表、查找表，甚至图结构。 

如果我们只关注代表算法的代码覆盖，就无法捕捉程序中蕴含的数据结构。还记得我们之前讨论的那个简单的魔法数字检查吗？约束求解确实能处理这种简单情况，但当面对数据密集型的程序结构时，约束求解就显得力不从心了。 

举个例子，看看 LCMS 项目中的一个看似简单的字符串比较： 

这段代码实现了不区分大小写的字符串比较。虽然看起来简单，但对约束求解器来说却是个不小的挑战！符号执行会被海量的执行路径淹没：假设字符串长度是 $m$，每次迭代有 8 种可能的路径（两个 toupper 各两种情况，再加上相等比较的两种情况），这意味着总共有 $8^m$ 条路径！即使使用现代化的优化手段，符号执行和求解器调用的开销依然很大。 

智能分支求解也面临问题。由于单个字符的比较很容易成功， while 分支很快就会被标记为“已求解成功”，后续的字符约束就被忽略了。虽然主流测试工具试图通过针对特定程序的优化来解决这个问题，但这种方法显然不具有普适性。 

更糟糕的是，有些静态值的语义根本不是约束。比如，复杂的数据结构如查找表、二叉树、有向图等都可以表示为静态数据，但它们的语义远非简单的约束关系。来看个例子，libpcap支持用户自定义的包过滤表达式，它用 flex 和 bison 自动生成了词法分析器和语法分析器，其中词法分析器的核心是一个有限状态机。虽然左图自动机代码的逻辑很简单，但复杂的自动机规则隐藏在上图中用常量数组编码的转移表中： 

对于只使用代码覆盖的模糊测试工具来说，这就是个噩梦。它需要在自动机中触发新的状态转移，达到新的接受状态，从而触发处理该状态的程序逻辑。然而，由于自动机的驱动代码非常简单，代码覆盖率很快就达到瓶颈，无法提供导向信息来触发新状态并执行相应的处理。简而言之，在这种情况下，代码覆盖率仅反映了“如何运行 任何 自动机”的表层逻辑，而数据覆盖率则揭示了“ 当下的 libpcap 自动机触发了哪些状态转移”的真实逻辑。 

简而言之，虽然引入了符号执行和智能分支求解等技术可以从代码的视角增强模糊测试，但它们并不能根本解决缺失的数据覆盖问题。数据覆盖率对于模糊测试非常重要，它不仅涵盖了简单的“魔法数字”等立即数场景，更允许模糊测试工具充分测试数据密集型的程序构造，并探索更多的程序状态。 

4. 数据 vs 代码的哲思 

在软件开发中，大家往往从代码为中心的角度来看待数据，导致数据被视为“二等公民”。然而，实际上，在软件的世界里，代码和数据就像是一枚硬币的两面，缺一不可。 

让我们探讨一下数据如何“变身”成代码。设想一个非常简单的计算模型，叫做“无限算盘”。这个模型仅包含两个操作： 

•  \(R^+(a)\)：给寄存器 R 加 1，然后跳到 a。 

•  \(R^-(a, b)\)：如果 R 是 0 就跳到 a，否则 R 减 1 再跳到 b。 

虽然这个模型看起来很简单，但 Lambek 在 1961 年证明了它是图灵完备的。这意味着，这两个简单的操作可以表示任何计算机程序的计算！ 

现实世界中的程序也是如此。例如，我们每天使用的字体，TrueType 格式中不仅包含字形轮廓，还可能嵌入了小程序，用于调整栅格化后的字形轮廓。最近，有人甚至在 TTF 字体中实现了大模型推理（关键字 “llama.ttf”）！这些看似普通的数据背后，实际上隐藏了复杂的计算和逻辑。 

反过来，代码也可以看作是一种特殊的数据。作者编写的程序最终被存储在内存中，以数据的形式存在，并等待执行。例如，有些编程语言（如 Scheme 的一个方言 OWL Lisp）会将程序转换为 C 语言的数据数组。在这种情况下，真正反映程序逻辑的，就是这些数据的覆盖率了。 

5. 数据覆盖：从理论概念到实际系统 

数据覆盖可以具有不同的粒度，这取决于如何将程序中的常量数据定义为符号，例如变量、数组、字段或位覆盖。这与代码覆盖中的函数覆盖、行覆盖和分支覆盖类似。然而，在实际测试中，测量精度越高，带来的开销也越大，实际测试效果可能未必理想。 

直观地看，在代码覆盖的场景中，学术界尝试引入基于上下文、N-gram 等更细粒度的覆盖方法。然而，由于实际效果有限，这些细粒度方法尚未在实际测试中广泛应用。类似地，为了实现完美的数据覆盖，需要将程序的地址空间以位为单位进行符号化，在程序执行中收集每个值对常量符号的使用情况，最后在程序结束后，计算实际使用的常量符号。虽然这种方法提供了非常精确的测量结果，但也会显著减慢程序执行速度，并降低总体测试吞吐量。 

简而言之，我们需要在精确度和性能之间找到平衡点。那么，作者是怎么做到的呢？ 

• 静态分析和插桩：在测试开始前，作者执行静态分析，对潜在的关键数据访问进行插桩。为了去除不必要的插桩，作者将数据访问分为 6 个类别，并实施不同的插桩策略。 

• 运行时数据捕获：在测试过程中，当拦截到数据访问时，运行时将不同类型的数据访问转换为（地址，长度）元组，并将新发现的数据访问存储在一个新的集合中，以便进一步检查。 

• 动态调整测试方向：测试用例执行后，模糊测试器检查新发现的数据覆盖集合。如果发现了有趣的代码或数据覆盖，作者就调整测试的方向。

 以下是一个例子，详细说明测试过程中发生的情况：

1. 测试引擎生成测试用例，并用它执行目标程序。 

2. 在测试用例执行期间，插桩后的程序会更新数据覆盖情况。例如，插桩代码拦截了位于 `0x404a1c` 的 `switch` 语句，并将条件和 `case` 值传递给运行时库。 

3. 运行时根据 `switch` 的语义进行抽象，将其视为两个整数访问。第一个访问（图中省略）从 `0x404a19` 读取 4 位，而下一个访问（图中所示）从 `0x404a20` 读取 15 位。 

4. 使用访问元组，作者将其与已知覆盖数据库进行比较，实时检测新覆盖。在这个例子中，对 `0x404a20` 的访问将已知的数据覆盖长度提高到 15 位。作者将其地址添加到新覆盖集合中，并恢复程序执行。 

5. 测试用例执行完成后，作者收集完整的代码覆盖率和新发现的数据特征集合。 

6. 样本保存器分析代码和数据特征。在这个例子中，只检测到新的数据覆盖，因此保存器用当前测试用例替换了原有种子。 

在这个过程中，作者发现了许多有趣的技巧，帮助整个系统降低额外开销，从而提升性能。 

6. 设计 1：分门别类地采集数据访问 

作者观察到，不同的数据访问有不同的语义，因此可以根据数据访问场景制定不同的采集精度。基于这一观察，作者将数据访问分为六类场景： 

1. 比较: 这些场景可能会影响程序的行为，因此作者使用位粒度来跟踪访问行为。具体来说，将整数的比较过程拆解为整数所包含的各个位的多次比较，只统计实际使用的位。其他场景则使用字节粒度进行估计。 

2. 静态量访问: 对于涉及静态量的内存读指令，作者对全部的内存读指令进行插桩。在插桩函数内，通过动态链接器获取程序的内存布局，将覆盖率采集的目标地址限定在程序的静态值相关区段（segment），以避免堆和栈带来的噪音。 

3. 立即数比较: 基于函数调用的指令特征，在插桩函数内获取函数调用的返回地址，从而用桩函数调用指令的地址估算立即数的机器码地址。 

4. 标准库内存访问: 对于标准库 libc 的内存访问，作者将 `memxxx` 和 `strxxx` 相关函数建模为原语，以更高效地模拟标准库的行为。 

5. 平凡的立即数使用: 对这些情况直接忽略插桩，因为代码覆盖可以在一定程度上代替。包含该立即数的指令会随指令所在的基本块一并执行，因此统计基本块的执行情况就能反馈该立即数所在指令的执行情况。

    

7. 设计 2：优化的覆盖率表示方法 

作者采用了一种新的方式来表示已知的覆盖率。具体来说，作者使用一个 8 位整数数组来存储已知的覆盖信息： 

• 数组设计: 每次访问时，将地址的最低 24 位作为数组的索引，将访问的长度直接存储为数组元素的值。这种设计虽然带来了一定的不精确性，但大大减少了插桩和统计的开销。 

• 减少额外内存访问: 大多数内存访问操作（如 `load` 指令和 `memcpy`）通常会触及多个相邻的字节。通过将所有访问合并到一个字节中，减少了因插桩产生的额外内存访问。 

• 减少桩函数开销: 如果一段定长数据已经被完全覆盖，可以将数组元素设置为哨兵值。下次桩函数运行时，若发现数组已被置为哨兵值，则可跳过数据使用长度的计算，从而降低桩函数的执行成本。 

除了设计新的方法存储已知覆盖率外，作者还设计了新的方式用于表示新的覆盖率。为了最小化对程序执行的影响，作者实现了一个动态大小的数组来存储新发现的数据覆盖的基地址。在每次执行过程中，当插桩逻辑识别到一个新的访问元组时，地址会被立即追加到数组尾部。执行完成后，作者将数组转换为集合，通过排序和去重来确保准确性。这一设计解决了传统覆盖率扫描的开销问题。传统代码覆盖率通常在每次执行后扫描覆盖数组以检测新的覆盖。这样的方式在处理数据覆盖时需要较多的时间和计算资源，因为需要访问 64 MiB \(2^{24}\) 的内存。 

8. 设计 3：规避队列爆炸的种子精化保存 

数据覆盖率的空间远大于代码覆盖率。例如，一个中小型项目的代码覆盖存储在 ~100KB，但数据覆盖却固定有 64 MiB。当获得非常精细的数据覆盖反馈时，模糊测试工具可能会倾向于保留大量过于相似的测试用例，带来经典的“队列爆炸”问题。为了解决这一问题，作者采用了种子精化策略。 

具体地，在测试用例完成执行后，作者根据代码和数据特征来决定模糊测试的探索方向。最常见的情况是测试用例没有发现新的数据或代码特征，此时作者会直接忽略这个测试用例，继续下一个测试。如果发现了新的数据特征但没有新的代码特征，作者会对现有种子进行精化，以减少保存的种子数量。例如，对于相同基地址的数据访问，如果新种子的数据访问读取了 8 位，而旧的种子读取了 7 位，作者会直接用新的种子替换旧的种子。如果优化无法进行，作者会将当前测试用例保存为新的种子，并更新数据-种子的映射。 

9. 实验评估 

作者在 libFuzzer 的基础上实现了数据覆盖，并通过 Google FuzzBench 评估了作者的新工作。下面是几个关键的研究问题和回答。 

Q1: 数据覆盖率能否提高模糊测试性能？ 

数据覆盖显著提高了模糊测试的整体性能。它将 libFuzzer 的代码覆盖率提高了 14%，使其在覆盖率得分方面排名第一，在平均排名方面排名第二。它还能持续提供良好的结果，并具有最低的标准偏差。 

Q2: 数据覆盖率是否与先前的技术是否相同？ 

数据覆盖率不同于分支求解相关的一系列技术。例如，如果分析各工具超越基线 libFuzzer 的超额覆盖率，作者工作获得的 34% 的超额覆盖无法被 AFL++ 所复现。此外，它还发现了 28 个之前未被发现的、经 OSS Fuzz 充分测试的 bug。 

Q3: 单个组件的贡献如何？ 

无论有没有代码覆盖，数据覆盖都有效过。使用代码覆盖和数据覆盖可额外增加 14% 的覆盖率。有趣的是，仅使用静态数据覆盖，就可实现 72% 的最大覆盖率。此外，如果收集完整的数据覆盖率（考虑和代码耦合的部分），这一数字还能进一步提高到 94%。 

Q4: 数据覆盖的运行时开销是多少？ 

数据覆盖的开销不会影响端到端模糊测试的性能，即使是短时间的测试也是如此。事实上，在最短的 15 分钟评估中，数据覆盖的覆盖率得分最高。不过，它确实导致吞吐量降低了 34%。这一下降主要是由于收集静态值增加了开销。 

10. 结语 

在模糊测试中，“卷”出更高的代码覆盖率一直是一个常见的话题。为此，本文探索了“数据覆盖”的概念。尽管其理论基础简单，系统实现并不复杂，但要在实际系统中获得良好的效果却需要不断试验和调整。本研究中的插桩策略、数据结构和调度算法虽然经过反复优化，但仍可能不是最优的。 

https://www.usenix.org/system/files/usenixsecurity24-wang-mingzhe.pdf

投稿团队介绍