原文标题：AFGEN: Whole-Function Fuzzing for Applications and Libraries
原文作者：Yuwei Liu, Yanhao Wang∗, Xiangkun Jia, Zheng Zhang, Purui Su∗
原文链接：https://www.computer.org/csdl/proceedings-article/sp/2024/313000a011/1RjE9PjiDss
发表会议：2024 IEEE Symposium on Security and Privacy (SP)
主题类型：漏洞挖掘与分析
笔记作者：Kn0w
主编：黄诚@安全学术圈
模糊测试技术被广泛应用于漏洞发现，例如自动为API函数生成模糊测试代码（fuzzing harnesses）以直接测试目标函数，但对程序和库来说，由于内部函数复杂的依赖关系、上下文和约束，无法覆盖到其中的所有功能。文章针对这一问题提出了全函数模糊测试的概念，并设计了原型工具AFGEN，它可以对任意函数直接进行模糊测试，有效识别漏洞并生成测试代码。文章还提出了反馈式“片段测试代码”（类似FuzzDriver）修正和验证方法，AFGEN重点解决了测试代码生成中的数据依赖、数值初始化来源和漏洞触发路径约束问题，降低了模糊测试带来的误报问题，提升了深层次代码的漏洞挖掘能力。通过实验评估，AFGEN 成功为所有易受攻击的函数创建了测试代码，识别了11个开源项目共102 个已知漏洞中的 66 个漏洞，结果明显优于通用模糊测试工具AFL、AFL++和定向模糊测试工具AFLGo、Parmesan、Beacon，Fuzz Driver。AFGEN 触发崩溃的精度达到 77.1%，是FUDGE 精度的 10 倍。此外 AFGEN 还发现了 24 个0day，并得到了 CVE ID 确认。
模糊测试作为一种动态测试技术，已广泛应用于测试应用程序和库。覆盖率是评估模糊测试有效性的关键指标，覆盖率越高，发现漏洞的机会越大。尽管研究人员在不断努力提高代码覆盖率，但未得到令人满意的结果。本文提出“全函数模糊测试”的概念，即：若能为所有函数生成模糊测试代码，就可直接测试每个函数，轻松增加覆盖率。
以往的工作重点是自动为API生成模糊测试代码。对API函数排列组合其API调用来构建模糊测试代码。但由于API和程序内部函数之间的差异，该方法不能直接应用于任意函数。因此存在如下挑战：
C1：构建适当的程序上下文：获取准确且全面的上下文对内部函数来说更加复杂，能够使用的文档或用例相比API而言很少；
C2：为变量赋有效值：内部函数的参数通常比较复杂（如嵌套结构），它们的初始化语句更难提取，所以需要根据变量类型（整数、结构体或指针）用不同的方法分配有效值；
C3：满足程序约束条件：对于内部函数来说，提取依赖关系和参数的初始化相比API会更困难，并且需要使赋值和提取的控制流满足程序约束。否则，模糊测试代码会意外崩溃，导致大量误报。
Listing 1的示例显示了 ngiflib 的 GetByte 函数（此处存在 CVE-2021-36531），该函数采用 g 表示的结构指针作为输入。它检查 g->mode的值；如果是NGIFLIB_NO_FILE，函数从内存缓冲区获取一个字节（第15行）；否则，它从文件中获取字节（第 17 行）。在15行， GetByte 包含一个堆溢出漏洞，它在从内存缓冲区读取字节时不检查边界。
以往从应用程序入口点或库 API 生成模糊测试代码的方法不太可能检测到此漏洞，因为 GetByte 中的易受攻击的代码与 g->mode 相关，并且很难被覆盖到。文章中自动生成了一个覆盖此函数并生成触发漏洞的模糊测试代码的案例。
Listing 2显示了由AFGEN生成的该示例的测试代码，AFGEN使用了和FUDGE类似的切片技术。Listing 2 中 AFG_func（第 3∼7 行）中的代码是 GetByte 的切片用例代码。对于C2，AFGEN根据变量类型赋值。LLVMFuzzerTestOneInput开头的代码（第 19∼31 行）为 struct ngiflib_img 及其成员赋值。接着计算具有特定大小的变量所需的最小数据大小minimum_size（第13∼15行），并将其余数据分配给没有特定大小的内存缓冲区（第18、28行）。这样就可以合成模糊测试代码并从中获取崩溃报告。但还需要确保模糊测试代码满足程序的约束，否则将会出现大量的误报结果。根据之前的崩溃报告，可得到两个关键变量，g->mode 和 g->input.bytes。根据对原程序中关键变量的跟踪约束，发现有与 g->mode 相关的新约束语句（例如Listing 1 中的第 7 行），并且没有发现新的约束代码与 g->input.bytes 相关，它直接从输入文件初始化。AFGEN 在模糊测试代码的第 34∼40 行添加了新的约束语句，以恢复目标函数 GetByte 的完整的运行上下文。AFGEN 在第 37 行用随机条件替换了原始分支条件，以避免在测试代码中引入更多变量。再次运行测试代码并获得相同的崩溃报告后，可以保证它确实是一个漏洞而不是误报。
本文提出了“全函数模糊测试”的概念和反馈式“片段测试代码”修正和验证方法，并设计了一个原型——AFGEN。
Figure 2为 AFGEN 概览。给定模糊测试目标的源代码，AFGEN首先对代码进行预处理，提取结构信息、函数依赖关系和其他必要信息，以便进行后续分析。通过函数依赖，AFGEN定位调用目标函数的函数，并切出调用目标函数的代码片段。如果切片代码中的某些变量未初始化，AFGEN会根据变量类型和结构信息为其赋值，从而合成有效的模糊测试代码。AFGEN 运行测试代码并生成崩溃报告，接着分析该报告以提取与崩溃相关的变量，搜索定义或初始化这些变量的代码，最后整合回模糊测试代码中。
文章提供了 AFGEN 三个主要组件的设计细节：双向切片器、变量值分配器和约束跟踪器。
Algorithm 1为切片算法，切片过程包括提取控制流和数据流，添加必要的代码以使模糊测试代码可编译，以及删除一些无害的代码以提高性能。例如对一个包含目标函数的任意函数，切片器会将其标记为调用者函数funcs，并对每个调用者应用切片，切片器会将与关键变量有数据流依赖关系（即 IsDataRelated）和与输出语句有控制流依赖关系（即 IsControlRelated）的语句添加到输出语句集中，并将这些语句中使用的变量添加到关键变量中。对于数据流依赖性，切片器会检查该语句是否最解决关键变量的赋值语句，若切片语句是调用语句，则会前向切片以获取其中的关键变量，AFGEN会重复上述过程直到Set_code不再发生变化。文章默认对直接调用目标函数的函数进行切片，以防代码大小爆炸。对于通过依赖分析得到的可能存在一些语法和逻辑错误的切片，AFGEN会在这些控制语句的主体种添加诸如null的语句以保证编译和程序逻辑正确。
为了提高模糊测试性能，本研究也通过无害化处理以提高效率，例如对输出语句来说，如果满足以下条件之一就能被认为可优化：1）输出函数不属于printf家族；2) 传递给输出函数的格式参数是一个不带修饰符的常量字符串（例如%s或%n）；3) 传递给输出函数的格式参数是一个常量字符串，并且模糊器生成的输入不会作为参数传递给修饰符（例如%s或%n）。
在对切片器中的切片代码进行定义或初始化之后才能进行编译。变量值分配器组件根据变量的类型为代码片段中未初始化的变量分配值。常规赋值方法为直接赋值、分配后赋值和打开文件后赋值。AFGEN只为切片结果识别到的关键成员赋值，但对于复杂的结构变量，例如嵌套结构，AFGEN设置了阈值，只为该结构变量中的前几个嵌套赋值。但诸如函数指针变量、强制转换指针变量和枚举类型变量这些类型的变量也无法通过上述方法处理。对于这些类型，文章提出以下解决方法：
函数指针类型：AFGEN扫描源码，提取该变量的赋值语句，通过预处理器组件将相同的函数赋值给该变量，若无法在源码中找到该变量的赋值语句时，AFGEN会搜索参数类型与函数指针变量相同的函数，然后将该函数分配给该变量；
强制转换指针类型：有些指针变量，在被使用之前无法获取它们的实际类型。若在声明时根据变量的类型为其赋值，fuzzer可能会意外崩溃。AFGEN会在切片过程中识别类型转换语句，当强制类型比原始类型更复杂时会用强制类型替换原始类型；
枚举类型变量：AFGEN提取枚举变量的所有候选值，并根据模糊输入赋予其中之一的值。
为减少误报，AFGEN对任意函数构建模糊测试代码时会考虑约束。Algorithm 2显示，约束跟踪器根据先前的模糊框架触发的崩溃报告跟踪约束。为了使跟踪器更加高效，AFGEN 只跟踪与崩溃点直接相关的变量的约束，并构建一棵分赋值树，赋值树的每个节点代表一个变量，每条边代表赋值语句，根节点代表与崩溃直接相关的变量。这样得到追踪到的约束后，出于有效性的考虑，会从数据流和控制流方面对约束进行修改。对于约束追踪到的变量，将其分为两类分别处置：
程序输入：AFGEN 会为其分配随机数据。例如一些程序输入是通过main函数的argv参数来分配的。如果对追踪记录语句中的这些变量应用其他修改，AFGEN 会将这些修改添加到模糊测试代码中。
新控制变量：考虑到性能，实验将嵌套跟踪的阈值设置为 1，这样AFGEN直接用模糊输入中的值替换新变量，或者对于动机示例，AFGEN获取由新变量控制的约束，并将原始表达式替换掉。
数据集：11 个开源项目共102 个CVE已确定的漏洞（Table 11）。
实验搭建：实验在配备 40 核 Intel(R) Xeon(R) CPU E5-2630 v4 @ 2.20GHz、64 GB RAM 和 64 位 Ubuntu 16.04.3 LTS 的服务器上运行。随机生成初始种子，并在整个实验中为每个测试库使用相同的种子。实验选择 AFL (2.52b) 和 AFL++ (4.01a) 作为代表性的通用模糊器，并选择定向灰盒模糊器AFLGo 、Parmesan 和 Beacon 作为基线进行比较。重复运行各fuzzer 10 次，在 CVE 报告中使用相同的模糊测试命令，并将定向灰盒模糊器的目标配置为 CVE 报告中的崩溃点。
模糊驱动程序崩溃分类：在实验中，如果无法通过 API 或程序入口点触发相应的崩溃，会将测试代码视为误报 。鉴于自动崩溃分类的问题尚未解决，实验采用手动分析每个崩溃以确定误报。每个误报需要初级安全研究人员不到 20 分钟的时间来验证。
本研究基于 Clang/LLVM 框架实现了 AFGEN，包含 5.7K 行 C++ 代码和 1.2k 行 Python 代码，包括预处理器（1,107 行 C++，250 行 Python）、双向切片器（ 1,417 行 C++、243 行 Python）、变量值分配器（573 行 Python）和约束跟踪器（3,194 行 C++、194 行 Python）。选择 libFuzzer作为 AFGEN 生成的模糊工具的模糊引擎，且所有模糊工具都使用 Address Sanitizer进行编译。
预处理器收集的信息：文章实现了一个单独的预处理器用于收集信息（收集的信息和收集方法见Table 2），预处理器只需为项目运行一次。分析收集代码相关信息是基于Clang AST的，并且在构建项目时利用开源工具Bear收集编译命令。
切片器中的依赖分析：切片器是基于Clang AST开发的。AFGEN现在处理41个语句，其中10个为C++语句。为分析控制流依赖性，AFGEN 检查控制语句的主体，即 IfStmt、WhileStmt、ForStmt、SwitchStmt、SwitchCase、DoStmt 和 CXXTryStmt。若这些语句的主体包含切片代码，AFGEN 将这些语句标记为具有控制流依赖性的语句。对于数据流依赖性，AFGEN检查DeclStmt和DeclRefExpr中的变量是否在关键变量集中。若是，AFGEN 将其父语句标记为具有数据流依赖性的语句。
不使用切片代码赋值：对于切片器无法为fuzzer提供上下文的情况。AFGEN 将生成一个简单的模糊测试代码，其中变量值分配器根据这些目标函数的参数的类型直接为其分配值。
查找和过滤约束语句：约束跟踪器以 LLVM IR文件和崩溃报告作为输入进行流分析，以找到过滤误报所需的约束。LLVM 将源代码转换为 IR 代码后，约束追踪器利用崩溃报告中的行号和变量来定位 IR 代码中相应的行和中间变量。然后遍历中间变量的use-def链（直到找到源代码中表示创建局部变量的AllocaInst操作符），找到源代码中为中间变量赋值的局部变量，跟踪局部变量的 def-use 链以获得易受攻击变量的约束语句。文章利用 IR 中的 GetElementPtrInst 运算符来区分结构中的不同字段。
结构变量追踪：如果模糊测试代码因结构变量中的特定成员而崩溃，约束跟踪器在跟踪时将获取所有成员的约束。为消除冗余约束，AFGEN为该结构创建一个映射并记录与崩溃相关的成员的索引。通过比较获取结构体成员时的索引，可以判断当前约束是否多余。类似地，文章通过在结构和相关成员索引集之间构建映射链来跟踪嵌套结构中的约束。
Table 11展示了AFGEN和其它fuzzer再现现实场景漏洞（来自11个开源项目共102个CVE）的结果比较。
文章通过对三个研究问题的回答进行实验评估：
RQ1：全函数模糊测试在应用程序漏洞发现中的效果如何？
RQ2：全函数模糊测试在库漏洞发现中的效果如何？
RQ3：全函数模糊测试发现现实场景中未知漏洞的效果如何？
对于RQ1，AFGEN的表现优于AFL++和其它模糊器，不管是在通用模糊器还是定向模糊器中，它发现的漏洞数量都是最多的（Table 3）。在漏洞再现方面， 通过MannWhitney U 测试 p 值发现，AFGEN 的性能明显优于所有其他模糊器，再现的漏洞比 AFLGo、Parmesan 和 Beacon 多 1.7 倍、2 倍和 5.5 倍。研究还发现定向模糊器的表现并不如预期。在漏洞复杂性方面，AFGEN可以有效地探索和再现隐藏在更深路径和复杂分支中的漏洞，其他模糊器表现不佳是因为它们无法到达深层易受攻击的代码。从时间性能角度来说， AFGEN 对单个漏洞的平均发现时间远远少于任何其他模糊器，其他模糊器的漏洞发现时间从几秒到几小时不等，而 AFGEN 在 300 秒内发现了每个漏洞，并且组件的耗时平均在37.94s（Table 5）。在对AFGEN组件的有效性分析中发现，通过禁用这三个组件之一，崩溃的精度会从 ∼7% (94.55% - 87.64%) 下降到 ∼47% (94.55% - 46.97%)。这表明，所有三种设计选择对于提高 AFGEN 发现崩溃的精度都发挥着重要作用。
对于RQ2，实验对所有11个开源库应用了AFGEN和FUDGE工具，并比较了这两个工具的结果。由于现有的库模糊测试工作针对的是库 API，因此在两种场景下比较 AFGEN 和 FUDGE：全函数场景，定制 FUDGE 将每个函数都视为库 API，以及纯 API 场景，定制 AFGEN 只专注于API。测试库总共产生 5,292 个函数和 1,234 个库 API。对于每个生成的模糊工具，使用库编译执行，并验证崩溃的正确性。
对全函数场景，Table 7 显示了从 11 个库中识别出的独特崩溃 AFGEN 和 FUDGE 的数量。AFGEN 成功为所有 5,292 个函数生成模糊测试代码。AFGEN 有 505 个真阳性和 150 个假阳性，准确率达到 77.1%，比 FUDGE 的准确率（7.6%）高 10 倍。研究对误报进行了调查，发现其中 87.3% (131/150) 是由不准确的静态分析引起的（Table 10）。尤其包含大量函数指针和复杂约束的库阻碍了 AFGEN 准确跟踪约束的能力，导致在发现的崩溃中出现大量误报。与同一函数指针关联的函数也具有不同类型的变量，这些变量是隐式转换的。因此，AFGEN无法准确地将所有指针与其对应的函数匹配，导致了80.6%（31中的25个）的崩溃误报。另一个重要因素是缺乏语义。
对于仅 API 库模糊测试，Table 8 为 API 的数量以及 AFGEN 和 FUDGE 的崩溃统计数据。AFGEN 生成了 124 个真阳性和 10 个假阳性，实现了 92.5% 的精度。FUDGE 生成了 78 个真阳性和 484 个假阳性，精度为 13.9%。并且由于 FUDGE 对 API 参数有特定要求，因此 FUDGE 只能分析 1,234 个 API 函数中的 48 个。AFGEN 在适用性、真实崩溃次数和崩溃精度方面优于 FUDGE。
关于RQ3，AFGEN 发现了Table 9 所示的 24 个未知漏洞。这些漏洞包括堆缓冲区溢出、堆栈缓冲区溢出、空指针取消引用以及违反安全相关断言。AFGEN 发现的大多数新漏洞很难被其他模糊器发现。AFL 和 AFL++ 均发现了 4 个新漏洞，而 AFLGo 仅发现了其中 2 个。根据触发方式，研究将这24个漏洞分为四类：General、API、CPL 和Option。General包括理论上可以仅通过改变输入文件来触发的漏洞，并且不需要额外的选项。API代表通过API而不是应用程序的入口点触发的漏洞。CPL包括需要触发额外编译选项的漏洞。例如，ngiflib中的CVE-2021-36530和CVE2021-36531在其他fuzzer的模糊测试过程中，如果没有特定的编译命令，则无法触发。Option表示由特定命令行选项触发的漏洞。比如CVE-2022-28550是一个堆栈溢出漏洞，可以通过命令行选项触发。
此外，在发现的漏洞中，研究发现了三例之前已发现漏洞，但由于补丁不完整或不正确而仍然易受攻击的情况。例如在漏洞应用补丁后，程序无法触发PoC的漏洞，但补丁并未添加对应的检查，因此漏洞依然存在。全函数模糊测试可以帮助开发人员快速验证补丁和新提交的代码。
本文的实验设计采用包含通用和定向的多个模糊测试器作为参考基线，在相同运行条件（测试时间、轮数等）下对统一的测试程序进行了重复实验，降低了模糊测试的不确定性。另外，目前AFGEN的性能表现已经力压群雄，不过如果引入并行化机制，或许在测试速度、深度、覆盖率和资源利用效率等方面还会有显著提升？
Yuwei Liu，中国科学院软件研究所
Yanhao Wang，中国科学院软件研究所
Purui Su，中国科学院软件研究所研究员，中国科学院大学
专题笔记征稿 | Security Tasks of LLMs-Driven 2023
安全学术圈招募队友-ing
有兴趣加入学术圈的请联系 secdr#qq.com
