Utopia：使用单元测试实现模糊测试驱动程序的自动生成|技术进展

原文名称：UTOPIA: Automatic Generation of Fuzz Driver using Unit Tests

原文作者：Bokdeuk Jeong , Joonun Jang , Hayoon Yi等

原文链接：https://ieeexplore.ieee.org/abstract/document/10179394

发表期刊：IEEE Symposium on Security and Privacy（S&P），2023

开源代码：https://github.com/Samsung/UTopia

模糊测试是在软件中检测安全漏洞的最切实可行的方法，但采用模糊测试需要付出相当大的努力。为了发挥它的有效性，高质量的模糊测试驱动器首先需要使用一系列适当的API来详尽地探索程序状态。

为了减轻这个负担，现有的解决方案尝试通过从消费者代码（即API的实际使用）中推断有效的API序列，或者直接从样本执行中提取它们来生成模糊测试驱动器。

不幸的是，所有现有方法都存在一个共同的问题：观察到的API序列，无论是静态推断还是动态监视，都与自定义的应用逻辑交织在一起。然而，我们观察到单元测试是由API的实际设计者精心设计的，用于验证其正确使用的，重要的是，在开发过程中编写单元测试是一种常见的实践（例如，超过70％的流行GitHub项目）。

在本文中，我们提出了一个名为UTOPIA的开源工具和分析算法，可以从现有的单元测试中自动合成有效的模糊测试驱动器，几乎不需要人工参与。

为了证明其有效性，我们将UTOPIA应用于55个开源项目库，包括Tizen和Node.js，并从8000个合格的单元测试中自动生成了5000个模糊测试驱动器。

此外，我们对生成的模糊测试驱动器进行了大约500万个核心小时的执行，并发现了123个漏洞。更重要的是，2400个生成的模糊测试驱动器已经被采用到Tizen项目的持续集成过程中，这表明了合成的模糊测试驱动器的质量。提出的工具和结果是公开可用的，并得到了广泛的研究人员和实践者的应用和维护。

针对库的模糊测试（library fuzzing）需要手动编写驱动程序（或称为harness）来完成测试过程，本文希望提出一种方法来实现harness的自动生成。

harness生成的困难在于:

• inter-API 约束。例如按照设计逻辑API A应该在 B 之前调用，则调用序列 B -> A 产生的crash会被视为spurious crash

• intra-API 约束。指的是API 参数的约束，例如 Array-Length

• 有害输入：例如控制循环次数和分配空间大小的参数。

基于多数开源库都有单元测试（UT）的事实，本文提出Utopia，一种基于UT生成harness的工具。采用UT的优势如下：

• 在harness的生成过程中，最困难的问题是inter-API 约束的推测。UT 提供了一串语义上合法的API调用序列，省去了inter-API约束的推测过程。

• 一个UT 往往代表了库的一个特定功能的完整实现。例如A,B,C为一个库的导出API，但在实际使用中只会同时使用A,B，而C只会被单独使用。

• 相比于consumer code ，UT不包含冗余的自定义逻辑。这使得生成的harness更简短，有助于缩短模糊测试运行时间，提高效率。

Utopia的基本目标是将UT转化为一个可被fuzzer使用的harness。其效果如下所示：

图 1 Utopia harness生成示例

本文将图中标红的语句称为fuzz target, Utopia 所做的就是在UT中找到这样的fuzz target替换为图中标绿的注入点。注入点语句的右值是一个接收fuzzer随机生成值的变量。

基本工作流程如下：

图 2 Utopia 工作流图

1. 对不同UT框架的结构分析

不同库所使用的单元测试框架不同，这给UT的提取和分析来困难。Utopia提出了一种简单的结构分析方法来解决这一问题。

经过分析，主流的UT框架都暴露如下三种接口：

Utopia借助Clang AST Matchers，利用接口名匹配的方式提取UT相关代码。用户只需要在使用时根据特定UT框架设置对应的接口名pattern即可。

2. API参数的属性分析

Utopia根据def-use chain来判断API的参数是否具有以下属性：

• Output: 一个只被写入不被读取的指针。

• Filepath 和 Allocsize:  对 libc 中相关函数的特定参数做标记，通过过程间分析方法找到判断对应参数是否被标记。

• Loop Count: 利用 LLVM LoopAnalysis 得到一个指令是否作为循环退出条件，然后根据def-use chain 判断该参数是否参与循环退出判断。

• Array - Length：数组首地址和长度的关系。

下面我们以Array-Length 属性为例，详细介绍API参数属性的提取过程。

图 3 Array-Length属性分析过程

对于API的每个参数，我们沿着它的DU chain，观察DU chain 上的元素是否被作为gep（即图中的getelementptr）指令的第一个参数，若是，则该参数被视为Array属性参数。

Length 属性分析只有在如下条件下开始进行：

• gep 指令在循环中，且 gep 的 index 参数是循环的归纳变量。

• 循环的终止条件在循环过程中保持不变

例如，while(i < b) { arr[i] = 1; } 中的b即满足如上的Length 分析开始条件。

在满足条件的情况下，如图所示，本文利用LLVM提供的API找到循环终止条件语句，找到判断循环终止的长度变量（即上述的b），沿着该变量的use-def chain（DU chain 的逆向），找到其来自于哪一个API参数。该参数即于先前的Array参数构成Array-Length约束。

3. Fuzz Target的选择

Fuzz Target 的选择指的是决定将UT中的哪些语句作为fuzz target的过程。寻找fuzz target 实际上等价于从API的调用点的每一个参数出发，寻找其根定义（root definition）的过程。

图 4 根定义寻找过程示例

如图所示，根定义指的是，某一调用点处的参数最终“来自”哪里。我们只需要对根变量的值进行变异，即可改变后续API调用的行为。在图示示例中，所有的调用点参数的根定义都是A。

由于我们分析得到的是API参数的属性，但最终针对fuzz target 做变异，所以我们需要制定一套属性继承机制，使得我们提取到的参数属性能最终作用于fuzz target 的变异。Utopia的继承策略是：只继承直接使用fuzz target的API参数的属性。

即：图中的 `int A = 10;` 只继承API_1 和API_2的第一个参数的属性。

4. Harness 生成

这一部分包括以下三个步骤：Fuzz input赋值，fuzzing 循环构建，初始种子提取。

Fuzzing input 赋值指的是替换fuzz target 的过程。UTOPIA将每个测试用例转化为模糊驱动程序，通过将识别到的模糊目标替换为模糊输入赋值语句。在识别到的模糊目标中，如果无法修改其源代码或者找不到适当的方法生成模糊输入，UTOPIA会排除某些根定义。排除的标准如下：

• 头文件中的根定义或项目文件之外的根定义

• 在编译时确定的常量（例如，sizeof(int))

• 对外部函数的返回值或输出参数进行赋值（非输入参数）

• 具有nullptr赋值的根定义，因为我们不知道如何初始化由指针引用的对象

• 函数指针参数

• 依赖于被忽略值的值（例如，被忽略数组的ArrayLen）

• 文件属性（例如，读取、写入）

在排除操作之后，UTOPIA根据数据类型和变异策略，用模糊输入替换赋值语句的r-values。UTOPIA遵循以下变异策略以符合API语义。

• FilePath: 将模糊输入写入到文件内容中，而不是改变文件路径。

• AllocSize: 限制用作内存分配大小参数的模糊输入范围。

• LoopCount: 限制用作循环退出条件参数的模糊输入范围。

• Array: 将模糊输入作为数组（即创建一个数组并为数组的每个元素分配模糊输入）。

• ArrayLength/Index: 将模糊输入限制为创建的数组大小减一。

Fuzzing 循环的构建。UTOPIA在每个模糊测试循环中构造一个入口函数。入口函数从模糊引擎（例如libfuzzer）接收模糊输入，并按顺序调用已识别和转换的测试函数（例如gtest中的SetUp()、TestBody()和TearDown()），以执行带有分配的模糊输入的模糊驱动程序。

初始种子提取。此外，UTOPIA在UT分析期间执行的一种简单而有效的过程是获取嵌入在测试代码中的初始种子语料库，这些种子是根定义语句中被识别为模糊目标的常量值。这些初始种子允许模糊驱动在模糊测试的早期阶段达到深入的程序状态，并帮助模糊器扩展其对深层路径的探索。

本文从如下几个方面对Utopia进行评估：

• 自动化程度。UTOPIA可以自动转换多少个基于UT（单元测试）的项目，与UT相比，合成的模糊驱动程序有多有效？

• Fuzzing效果。就代码覆盖率和漏洞发现来说，UTOPIA生成的模糊驱动程序与手动编写的驱动程序相比效果如何？

• 比较：UTOPIA与现有的自动模糊测试驱动生成方法相比如何？

• 设计目标。减少了多少虚假崩溃，如何处理断言的最佳策略，以及 UTOPIA 分析 API 属性的效果如何？

1. 实验环境

UTOPIA利用25个基于gtest和boost实现UT的OSS库以及30个基于Tizen TCT实现UT的Tizen项目进行评估。我们为每个实验目的进行了不同的设置，详细的设置在每个小节中描述。相同的是，每个harness在安装了Ubuntu 18.04基础镜像的Docker容器中作为单个libFuzzer工作进程运行。容器在Intel Xeon Gold 6258R处理器（2.70GHz，112个核心）和251GB RAM上运行。

2.Harness的自动化生成

UTOPIA能够在不需要人工干预的情况下，成功从试验案例（TCs）中合成25个尝试生成的开源软件（在表格II中列出的项目）的模糊驱动程序。

实验设置。我们从Github选择了6个热门项目，其中有11个被ossfuzz基准套件包含，还有7个是Android依赖的外部库，以及Tizen使用的一个外部项目。这些项目代表了各种规模（从几千到几百万行代码），构建系统（例如，cmake，bazel和ninja）和单元测试框架（例如，gtest和boost）。对于所有25个项目，每个由UTOPIA生成的模糊驱动程序运行了1个核心小时。

harness生成。在项目中的5,523个TC中，我们排除了包含在我们的原型实现中无法处理的宏函数的1,039个TC，即那些不是TEST和TEST_F（对于gtest）或BOOST_AUTO_TEST_CASE_FIXTURE（对于boost）的TC（表II中的其他TC）。在剩下的4,484个TC中，UTOPIA根据我们的排除标准，在确定根定义的过程中删除了1,769个TC（占受检查的4,484个TC的39％）。总之，UTOPIA从这些项目中的可行候选TC中自动产生了所有2,715个（100％）模糊驱动程序。对于感兴趣的读者，我们在附录的表VIII中分享了已删除TC中特征的比率。

生成的模糊驱动程序包括2,292个库导出的函数，并直接为56％所使用的库函数提供了模糊输入，这意味着另一半的库函数被用于构建适当的初步状态进行测试。

与单元测试比较。UTOPIA生成的模糊驱动程序在每个生成的驱动程序的模糊执行的每个核心小时内，将这些项目的唯一测试覆盖率提高了1.4-58.2％（相对于相应的测试用例）。每个模糊器的覆盖率显著增加了多达60倍（表II中的MG列）。这些发现突显了UTOPIA的两个有趣方面：1）自动扩展单元测试的测试能力；2）测试用例被设计用于检查开发人员认为是正确的方面，而模糊器则专注于开发人员没有预料到的方面。UTOPIA很好地结合了这两种方法。

生成时间。对于分析4,484个测试用例和库以及从中生成2,715个模糊驱动程序，总共需要15.7个每核心小时，这表明我们可以每15个每核心秒生成一段模糊驱动程序的源代码。具体而言，分析需要15.6个每核心小时，合成相应的模糊驱动程序需要6个每核心分钟，但与构建时间相比（我们的112个核心机器上的2小时），这几乎可以忽略不计。

崩溃。我们手动审查了在此设置的模糊测试中发生的共1,167个唯一崩溃。在这些唯一崩溃中，即通过崩溃报告中包含的堆栈跟踪的独特性区分的崩溃组，有109个是错误，572个是由于超时、oom和中止而引起的正常崩溃，486个是由API错误使用引起的虚假崩溃。即使正确使用API，正常崩溃也会发生，并降低了模糊测试的执行性能。75%的正常崩溃是由于超时引起的，主要是因为此类API的测试涉及到较长的处理时间（例如，图像数据处理）。43%的虚假崩溃是由UTOPIA未覆盖的属性引起的，33%是由分析失败引起的。然而，没有发生由于不正确的序列而导致的虚假崩溃。虚假崩溃的详细统计数据在附录的表X中说明。

3. Fuzzing有效性

模糊测试器的有效性可以通过发现的漏洞数量直接加以解释。UTOPIA总共发现了123个漏洞：在为25个开源软件项目生成的2,715个模糊驱动程序进行短期试运行几天中，发现了109个漏洞，同时，在为30个Tizen原生库生成的2,411个模糊驱动程序进行了大约两周的测试，发现了14个漏洞。

关于在Utopia 分别在OSS 库和 Tizen库中具体的漏洞发现情况详见原文。

4. 与OSS-Fuzz driver的比较

我们将UTOPIA生成的模糊驱动程序集与六个OSS-Fuzz项目的手动编写的模糊器进行了比较，并在表2和图5中分享了结果。

图 5 Utopia与Oss-Fuzz driver 100小时覆盖率

表 2 Utopia与 Oss-Fuzz driver 100小时结果对比

实验设置。在这个评估中，我们对OSS-Fuzz和UTOPIA进行了超过100小时的代码覆盖率测试，展示了UTOPIA自动化方法与手动调优、表现最好的模糊测试工具相比的有效性。请注意，UTOPIA对于这些库的驱动程序设置与表格II中列出的相同，并且我们将每种方法消耗的资源总量设置为每核心100小时（例如，对于Node.js，OSS-Fuzz的两个驱动程序在单个CPU上每个运行了50小时，而UTOPIA的41个驱动程序在单个CPU上每个运行了约2.4小时）。

代码覆盖率。在代码覆盖率方面，UTOPIA的模糊驱动器在6个项目中有4个的表现超过了平均20.5％，而在另外2个项目中则表现不佳（平均9.7％）。UTOPIA的覆盖增益主要可以归因于其对更多API进行模糊测试。即便如此，在图5中，我们可以观察到UTOPIA的覆盖范围随时间的推移而不断增加，这表明UTOPIA的大量测试API不仅对覆盖率有初步影响，还提供了进一步探索每个库的有效机会。

有趣的是，正如在表2中观察到的那样，即使在总体覆盖率方面UTOPIA表现不佳，它仍然可以探索到开源模糊驱动程序未能到达的库中的独特区域。

5. 设计目标评估

实验设置。根据每次评估的标准，生成的UTOPIA驱动程序会执行10次每个模糊驱动程序24个核心小时（表3）或12个核心小时（图6）的试验。

减少预期外的崩溃。我们进行了实验来研究通过库分析获取的ArrayLength、AllocSize和LoopCount这些属性对减少崩溃和由有害模糊输入引起的崩溃的影响。为了评估，我们从三个项目中选择了测试具有这三个属性的API参数的模糊驱动程序，并删除其中一个属性以进行比较。如表3所列，在没有ArrayLength或AllocSize属性的设置下，崩溃数量猛增了一两个数量级，而覆盖率仅略有增加。另一方面，如果没有LoopCount属性，崩溃没有任何区别，但每秒执行次数性能下降了多达40%。对于assimp项目，与包含该属性相比，当删除AllocSize属性时，覆盖率和每秒执行次数分别降低到37%和2%。在libhtp项目中，如果没有ArrayLength属性，崩溃数量增加了645倍，覆盖率和每秒执行次数性能也很差。此外，如果在leveldb中省略LoopCount属性，每秒执行次数性能会降低到41%。

断言处理。为了改善fuzzing的性能，UTOPIA利用UT的语义习惯生成fuzzing驱动程序。具体而言，我们评估了处理UT断言的七种策略：i)通过在检查失败的条件下提前终止来拒绝进一步执行，ii)忽略所有断言的nop，iii-v)是nop的派生版本nopNs，vi)只维护检查nullptr的断言的nullptr check only，以及vii)只维护检查后续API依赖对象的断言的dependent object check only。如图6所示，三个库的fuzzing结果在这些策略之间显示出最大的差异。具体而言，libhtp和assimp的fuzz驱动程序具有许多关于nullptr检查的断言，而uriparser的fuzz驱动程序具有许多关于将函数返回值与特定值进行比较的断言。总体而言，忽略断言逻辑对fuzzing性能有害，因为覆盖率和每个时间的执行都会显著下降。尽管只保留nullptr检查在某些情况下可能更有益，但其他策略在覆盖率方面显示出了可以比拟的性能，或者在执行方面表现更好。

属性分析有效性统计。我们评估了UTOPIA对API属性分析在识别API参数之间的相互依赖性以及单个参数对API内部行为的影响方面的充分性。因此，我们选择了具有用于崩溃缓解评估的此类属性的顶级项目（assimp、libhtp、leveldb）；在表4中概述的其他项目则是随机选择的。属性分析的准确性在表4中详细说明。所有分析的属性都被正确识别（准确率接近100%），但UTOPIA未能识别出一半的ArrayLeng/Index属性（召回率为45%）。据估计，这些假阴性占了上述虚假崩溃的33%（在表3中）。

表 3 API参数属性对fuzz的影响

表 4 API参数属性分析准确性

图 6 Utopia对 UT的断言处理策略的影响

非常规关系。在第III-B和第III-C节中，我们的分析可以识别出五种常见的关系和几种参数类型，但无法理解非传统或高度定制的用法以生成模糊驱动。例如，char* 类型可以在类似 printf() 的函数中用作格式说明符，但 UTOPIA 很可能会选择参数作为模糊输入，同时与先前使用的字符串一起作为种子语料库。任何包含额外格式说明符（如 %n）的变异输入都会导致错误崩溃。

错误处理不足。由于 UT 代码仅用于测试，开发人员倾向于为非必要的参数硬编码，并提供较少的错误处理检查，与生产代码不同。例如，开发人员通常跳过对对象的正确构造或适当分配的检查，在使用静态参数的 UT 上是合理的。然而，如果这样的 UT 成为模糊驱动的基础，任何错误情况都会导致错误崩溃。尽管 UTOPIA 努力识别这类情况（例如，支持 nullptr 检查），但如果有经验的开发人员在 UT 中提供适当的错误处理检查，就可以避免几种观察到的情况。

文件路径的根定义。在某些测试用例中，文件路径字符串是通过多个字符串操作创建的。在这种情况下，如果 UTOPIA 创建一个用于模糊测试的文件，并在字符串的根定义（在所有操作之前）上分配其路径，那么 API 访问的实际路径将是不正确的。为了避免这种情况，UTOPIA 通过启发式方式将生成的模糊文件路径分配给最接近 API 之前的字符串赋值/操作。然而，由于这种启发式方法，UTOPIA 可能无法在生成的模糊驱动程序中反映原始的 UT 逻辑，因为文件路径分配位置不是根定义。

UT 逻辑中的常量值别名。当测试用例直接使用常量值而不是变量时，UTOPIA 可能难以生成合适的驱动程序。例如，让我们假设一个简单的测试用例：int i = 5; ASSERT_EQ(decode(encode(i)), 5); API(i);。UTOPIA 会通过将赋值修改为 int i = fi 来生成驱动程序，但由于断言，它无法使用 fi=5 以外的值测试 API()。在这种情况下，我们希望忽略断言，但正如我们在第V-D节中评估的那样，我们不能简单地选择自动忽略断言，因为它可能会降低模糊测试的性能。另一种方法可能是将相同值的变量和常量视为别名，并将测试代码更改如下：int i = fi; ASSERT_EQ(decode(encode(i)), fi); API(i);。但这需要额外仔细的分析，因为将共享相同值的值视为别名可能会导致新的一类错误崩溃（例如，在上述情况中，如果通过 arr[5] 访问了一个不相关的数组，将所有常量5与 i 别名化并模糊测试它们可能会导致越界访问）。我们将分析和处理这类情况留作未来工作。

在本文中，我们提出了UTOPIA，它可以从现有的单元测试中自动生成模糊测试驱动程序，几乎不需要人工干预。它不仅理解单元测试框架的语义结构，还分析正在测试的每个库的API实现。结果，UTOPIA能够以可扩展的方式生成许多具有有效API调用序列的模糊测试驱动程序。我们展示了UTOPIA的广泛适用性，并证明UTOPIA成功地为55个流行的开源项目生成了模糊测试驱动程序。我们的评估结果显示，与手工编写的模糊测试程序相比，UTOPIA在6个项目中的4个项目中的代码覆盖率更高（平均为20.4%），同时还包含对开发人员有意义的API。更重要的是，UTOPIA在55个开源项目中发现了123个新的错误。

—END—