StateFuzz: 状态敏感的模糊测试

0 介绍

Fuzzing已经成为最流行和最有效的漏洞发现解决方案，被工业界和学术界广泛研究。 例如，谷歌的 OSS-Fuzz 项目持续测试了35个开源项目，截至2021年1月已发现超过25000 个错误。通常，模糊测试随机生成测试用例并使用这些测试用例作为输入执行目标程序。 为了处理内在的随机性，很多模糊测试方案遵循AFL的步骤，利用代码覆盖率来指导模糊测试的探索过程。 一般来说，他们优先考虑命中新代码的测试用例（即有助于提高代码覆盖率），并将它们用作进一步探索的起点。尽管这种方法取得了巨大成功，但覆盖引导的模糊测试解决方案也有许多局限性。最关键的限制是此类解决方案以代码覆盖为中心，并且在探索测试用例搜索空间时对其他反馈不敏感。在实际的生产环境中，大量的程序（包括设备驱动程序和网络服务等）内部程序状态复杂，没有达到特定状态就不会继续执行代码或产生崩溃。 例如，如果特定状态寄存器未设置为预期值，则外设将无法工作。为了有效地测试此类程序，模糊测试方案应该了解程序状态并巧妙地探索状态空间。

最近的工作开始探索程序状态。例如，IJON利用不同形式的手动标注提供的状态表示（例如，迷宫游戏中的位置）不仅可以执行模糊测试，还可以执行像超级马里奥这样的游戏。 InsvCov使用程序的潜在不变量作为边界来划分程序状态空间。 AFLNet使用服务器的响应代码作为程序状态来驱动网络协议模糊测试。 此外，StateAFL通过对特定进程内存执行局部敏感哈希来识别程序状态。 在这个方向上需要更多的研究工作。

通常，在开发状态敏感模糊测试解决方案时需要回答三个问题。

首先，什么是程序状态？ 本质上，一个程序状态是程序的执行上下文，包括所有程序变量的值（从软件的角度）和所有内存和寄存器的值（从硬件的角度）。然而，这种状态的数量非常多，在实践中很难跟踪所有这些状态。 因此，实用的模糊测试器必须像 IJON 和 AFLNet 那样关注程序状态的子集。此外，哪些状态对于模糊测试至关重要以及如何减少状态空间仍然是悬而未决的问题。

第二，如何识别程序状态并进行跟踪。在模糊测试期间 IJON 依靠手动注释来标记状态，并在适当的位置使用手动程序检测来跟踪状态。 AFLNet 通过从服务器的响应消息中解析响应代码来推断程序状态，然而并不是所有程序都有这样的响应代码。 它们要么不是自动化的，要么不是通用的。 InsvCov 使用重量级插桩来跟踪许多变量的值，以推断不变量并估计程序状态转换。 StateAFL 需要在运行时计算一些特定的长生命周期的变量的哈希值，以将每个内存状态映射为唯一的协议状态。 它们都引入了显著的开销并降低了模糊测试的效率。 因此，状态敏感的模糊测试方案应该自动识别程序状态并以有效的方式跟踪它们。

第三，如何利用程序状态来指导fuzzing？IJON 用手动注释的状态覆盖替换了 AFL 使用的代码覆盖位图。 除了代码覆盖率之外，AFLNet 还跟踪状态（响应代码）转换。 他们使用一个种子语料库来存储发现新代码或新状态的测试用例，并倾向于增加代码覆盖率的测试用例。 值得探索新的反馈机制以更好地利用程序状态。

在本文中，我们提出了一种新的状态敏感的模糊测试方案StateFuzz 来改进传统的代码覆盖引导模糊测试方案。 StateFuzz 利用关键变量来表示程序状态。 这些关键变量具有以下特点：它们具有长的生命周期； 它们可以由用户更新（即进行状态转换）； 它们会影响程序的控制流或内存访问指针。 我们将这些关键变量表示为状态变量。 所有状态变量值的组合形成了一个程序状态，这种表示是粗粒度的，但可以为模糊测试提供引导。 此外，StateFuzz 利用静态分析来识别状态变量。 我们注意到富状态程序（例如，设备驱动程序）总是需要多个或多阶段输入。 输入的不同阶段将触发不同的程序动作。 目标程序必须跨程序动作跟踪程序状态以进行同步和协调。因此，状态变量通常由不同的程序动作共享和访问。 例如，与登录状态相关的状态变量应该由登录请求和注销请求共享。 我们使用静态分析从它们访问的共享变量中识别程序动作和状态变量。 为了有效地跟踪程序状态，我们进一步缩小关注的程序状态组合中使用的状态变量的数量和每个状态变量的值空间。 首先，我们使用相关的状态变量对而不是所有状态变量的组合来建模程序状态。 其次，对于每个状态变量，我们识别它可能采用的一组值（或值域范围），其中不同的值选择代表不同的状态。 然后，我们将每个状态变量的值空间划分为几个范围，并跟踪在模糊测试期间是否命中某个范围。 最后，除了代码覆盖之外，我们应用了两种新的反馈类型，并设计了一个三维反馈机制指导模糊测试过程。 第一种反馈是，如果输入可以发现两个变量的新值域范围组合并且这两个变量都在相关的状态变量对中，则输入是有趣的。 第二种类型的反馈是将发现新的状态变量的上限值或下限值的输入认为是有趣的并保存。 当第一个反馈机制失败时，即当无法确定状态变量的取值域范围时，这个极值反馈可以作为补充。 基于模糊测试工具 Syzkaller，我们已经针对Linux 驱动程序模糊测试实现了StateFuzz 的原型。 我们在 Android Pixel-4 手机使用的 MSM-4.14 内核和 Linux 上游内核 v4.19 的驱动程序上评估StateFuzz。 评估结果表明StateFuzz在发现新漏洞和新代码方面是有效的。 StateFuzz 总共发现了2个已知但未修补的漏洞和18个新漏洞，其中15个已分配 CVE ID 或漏洞赏金奖励。与当前最先进的方案Syzkaller相比，StateFuzz 可以找到更多的漏洞并提升了19%的代码覆盖率。

1 背景

POSIX 驱动模糊测试

近年来，已经提出了许多用于发现漏洞的模糊测试解决方案，例如用于 Mac OS 内核的IMF，用于 Windows 内核的 iofuzz，ioctlfuzzer，ioctlbf和 ioattack . Syzkaller使用基于语法的模板生成测试用例，通过系统调用接口与内核交互，并利用 KCOV和 KASAN分别跟踪代码覆盖率和检测内存错误。 在 Linux 内核中一切都是文件，硬件设备也是如此。 POSIX 标准为用户空间应用程序提供了硬件的统一抽象。 /dev 目录中的每个文件都代表 Linux 中的一个硬件设备，它可以像普通文件一样被用户空间程序使用。 例如，用户空间应用程序需要获取设备的文件描述符，然后通过读写系统调用与其交互。 此外，还为用户空间应用程序提供了原型为 int ioctl(int fd, unsigned long request, …) 的特殊系统调用，以根据请求支持自定义硬件行为。 通常，Linux 驱动程序有两个攻击面，一个在于硬件设备，另一个在于系统调用。 因此，对 Linux 驱动程序进行模糊测试有两个方面。 第一个维度是模糊驱动程序，通过配置或 I/O 通道（如端口 I/O、MMIO 和 DMA）从硬件设备端注入输入。 例如，为了模糊测试 USB 驱动程序的probe过程，USBFuzz 利用通用 USB 设备与驱动程序匹配，并向它们发送恶意 USB 描述符。 PeriScope通过挂钩page fault handler将模糊测试数据注入驱动程序的 MMIO。 第二个维度来自系统调用，由于系统调用的参数是多种多样的，因此需要生成有效的测试用例。 例如，一个有效的 ioctl() 系统调用通常采用一个复杂的结构和一个命令（通常是一个大整数）作为参数。 Syzkaller 依靠人工来提取系统调用接口，以触发驱动程序的操作。 DIFUZE应用静态分析从设备驱动程序的自定义接口中提取支持的请求类型和相关参数，这有助于模糊测试器生成有效的测试用例。

代码覆盖率引导的模糊测试的局限性

代码覆盖率引导的模糊测试在测试具备复杂状态的程序（比如网络协议程序、内核驱动）时存在局限，即fuzzer缺乏指导来遍历程序状态。原因在于代码覆盖率引导的模糊测试只关心代码覆盖率，因此会丢弃没有触发新代码的测试用例，即使这些测试用例触发了新的状态。以IJON[2]论文提出的迷宫程序为例，在图1的代码中，代码覆盖率引导的模糊测试可以轻松地覆盖所有代码行，在此之后，即使x和y有不同取值，也会被模糊测试器丢弃，因为没有触发新的代码行。这样一来，因为缺乏指导，模糊测试很难通过随机生成x和y，来遍历所有的x、y取值组合来触发Bug()函数。 因此，对这些程序，需要使用状态敏感的模糊测试（state-aware fuzzing）。

程序状态

从本质上讲，程序状态是程序的执行上下文，包括程序当前操作的所有内容，即所有程序变量的值（从软件的角度来看）和所有虚拟内存和寄存器的值（从软件的角度来看）。 硬件）。 探索所有潜在的程序状态将揭示所有潜在的漏洞。 然而，由于计算资源的限制，在模糊测试期间跟踪此类程序状态是不可行的。程序状态是由程序维护的特定执行上下文，以记住先前的事件或用户交互。我们对状态丰富的程序进行了研究，以了解它们如何表示程序状态。具体来说，我们从开源项目中收集了包含关键字“state machine”的50 个代码提交，这表明程序正在处理某些状态。 这50次提交包括 (1) 具有关键字的 patchwork 中的所有 14 个 Linux 内核提交，(2) MSM 内核中从 2019 年 3 月到 2020 年 9 月的 21 次提交，以及 (3) Github中来自流行网络协议项目的 15 次提交，这些项目包括了nfs-ganesha、curl、httpd、OpenSMTPD、OpenSSL 和 OpenSMTPD。然后，我们手动分析了这些代码提交是如何标记程序状态的。结果表明，在 50 个提交中的 48 个中，状态由布尔/整数或枚举类型的变量表示（图2展示了几个变量示例）。对于另外两个提交，一个使用函数指针来表示状态，另一个使用数据包中的状态代码来表示状态。 因此，程序将有价值的程序状态存储到变量中是很常见的，我们可以利用保存关键信息的变量来表示程序状态。

2 StateFuzz方案设计

为了解决代码覆盖引导模糊测试器的局限性，我们提出了一种状态敏感的模糊测试解决方案 StateFuzz，用于基于系统调用的 Linux 驱动程序模糊测试。 在本节中，我们将介绍此解决方案的设计细节。

状态建模

状态变量：我们总结了用于表示程序状态的变量的特征如下：首先，这些变量具有较长的生命周期，可以跨越不同的程序状态来记录状态信息。 其次，它们可以由用户更新（即状态转换）。 第三，由于程序状态总是控制程序的行为，这些变量应该能够（直接或间接）影响程序的控制流或内存访问指针。 我们将这些变量标记为状态变量。

程序状态：由于每个状态变量都可以保存关键的程序状态信息，因此理想情况下，程序状态应该包含所有状态变量值的组合。 然而，这种组合的数量太多，跟踪这种状态是不切实际的。 因此，我们尝试通过两个优化来减少组合的数量。 首先，我们只考虑程序状态中的相关状态变量对，这参考了代码覆盖率引导的模糊测试通常只跟踪代码边覆盖（即两个相关基本块的组合）而不是路径覆盖（即 所有基本块的组合）。 如果存在同时受两个状态变量影响（直接或间接）的控制流或内存访问指针，我们将这两个状态变量标记为相关的状态变量对。 例如，如果两个变量分别被两个条件语句检查，并且这两个条件语句是嵌套的，则这两个状态变量是相关的。 其次，每个状态变量的取值空间都很大（例如，32 位整型变量有 232个取值），但这个变量可能仅被程序离散地使用到某几个值域范围。 因此，我们提出将状态变量的值空间划分为几个值域范围，并跟踪在模糊测试期间是否命中新的值域范围。 在模糊测试过程中，我们跟踪每个相关状态变量对的两个变量的值域范围组合，而不是跟踪它们的单个具体值。 我们将这种值域范围组合表示为值域边。 此外，我们还跟踪状态变量的极值作为值域边覆盖率的补充。 如果我们发现新的值域边或状态变量的新极值，我们认为我们发现了新的程序状态。

StateFuzz概述

图3说明了 StateFuzz 的大概工作流程。它包括三个主要阶段：程序状态识别、程序插桩和模糊测试循环。我们首先分析Linux驱动程序的源代码，通过提取状态变量、状态变量的值选择以及状态变量之间的相关性来识别程序状态。具体来说，我们利用静态分析来识别由不同阶段的输入触发的程序动作，并识别由多个程序动作访问的共享变量。为了更实际的跟踪状态变量，我们进一步分析了它们的值（或值域范围）选择。然后我们利用静态符号执行来收集每个状态变量的值约束，并推断其离散的值域范围。之后，我们插桩目标程序（即 Linux 驱动程序）以跟踪程序状态覆盖率以及代码覆盖率（例如，由 KCOV 提供）。具体来说，给定已识别的状态变量，我们首先使用 SVF进行别名分析，以识别状态变量的别名。然后在编译期间，StateFuzz 检查每条store指令的目标指针。如果目标指针指向状态变量或状态变量的别名，则指令被插桩以跟踪被store的值。更准确地说，它将跟踪值域边和极值以产生程序状态覆盖反馈。接下来，我们通过将程序状态反馈应用于种子输入保存和种子选择的过程来扩展代码覆盖引导的模糊测试。具体来说，我们将保留发现新值域边或状态变量新极值的输入，以及发现新代码的输入。最后，我们应用一种精细的选择策略从这些不同类型的保存种子中选择并变异输入。

程序状态识别

作为 StateFuzz 的核心，除了代码覆盖反馈之外，它还考虑程序状态。在本节中，我们将详细介绍如何识别程序状态。

首先第一步识别程序动作，对于富状态程序，例如驱动程序，通常需要多级或多级输入。每个输入阶段都会触发特定的程序动作。对于 Linux 设备驱动程序，程序动作是可以通过系统调用触发的对应系统调用处理函数。图 4 说明了几个示例程序动作，它们取自 hpet 驱动程序的代码。首先，许多程序动作在全局操作结构中初始化。例如，在全局operation结构 hpet_fops 中初始化的 hpet_open 和 hpet_read 处理程序表示open和read操作，这些操作可以由某些输入触发。其次，驱动程序可以通过 ioctl 接口的子命令执行程序动作。例如，第 8 行到第 13 行的语句代表一个特定的程序动作，它可以由用户输入命令 HPET_IE_ON 来触发。基于 Linux 驱动程序代码的这些约定，我们利用静态分析来识别程序动作。 对于包括read、write、open、poll和 mmap 在内的系统调用，我们分析它们的源代码以定位将函数处理程序分配给全局操作结构的初始化程序。 这些分配的函数处理程序是程序动作的入口点。 对于 ioctl 系统调用，我们扩展了工具 DIFUZE以执行跨过程和路径敏感分析并识别所有支持的子命令。 与每个子命令关联的代码片段是一个程序动作。

第二步是识别状态变量。不同的程序动作有时必须通过状态变量来协调程序状态。因此，状态变量通常由多个程序动作共享。例如，与登录状态相关的状态变量应该由登录请求和注销请求共享。为了识别状态变量，我们基于函数调用图分析每个程序动作的代码并识别访问的变量。如果变量可以回溯到全局变量或结构字段，那么我们会将它们标记为候选状态变量，因为状态变量应该有很长的生命周期。在分析所有程序动作之后，我们将过滤所有候选状态变量：我们只保留将由一个程序动作更新并由另一个程序动作加载的候选状态变量（即，如果没有被任何动作读取或未被任何动作写入，变量将被丢弃）。例如，图 4 中的变量 devp->hd_ireqfreq 和 devp->hd_hdwirq 都被识别为状态变量。

第三步是推测状态变量的值域范围。为了推断每个状态变量的值域范围，我们在源代码的抽象语法树 (AST) 上执行过程间和路径敏感的静态符号执行。为了避免路径爆炸，值得注意的是，我们的符号执行一次只分析一个源代码文件（即模块内分析），这大大减少了路径的数量。我们可以通过它们的类型和名称来定位 AST 中的状态变量。然后我们探索每个程序路径并在探索过程中识别与状态变量相关的路径约束。然后，如果有一条路径的约束同时涉及两个状态变量，我们将这两个变量识别为相关的状态变量对。通过约束求解器，我们可以推断出状态变量的边界值。然后我们使用这些边界值来分割状态变量的值空间。例如，在图 4 所示的驱动程序代码中，state-variables devp->hd_ireqfreq 和 devp->hd_hdwirq 在第 9 行和第 11 行中分别与 0 进行检查。第 9 行的条件语句引出了两个分支，这两个分支提取的约束分别为 devp->hd_ireqfreq!=0（即 devp->hd_ireqfreq<=-1 或 devp->hd_ireqfreq>=1）和 devp- >hd_ireqfreq==0。因此，我们可以得到三个边界值：-1、0、1。于是我们将devp->hd_ireqfreq的值空间用这3个数字划分为4个值域，即[INT_MIN,-1],(-1, 0],(0,1],(1,INT_MAX]。第 11 行的情况类似。

模糊测试阶段

在插桩驱动程序以跟踪状态变化后，模糊测试进入主模糊测试循环。 StateFuzz 采用遗传算法来引导模糊测试器探索更多的程序状态，就像 AFL 增加代码覆盖率一样。 具体来说，StateFuzz 保留并优先考虑发现新代码或新状态的种子。 在本节中，我们将介绍 StateFuzz 如何通过新颖的三维度反馈机制、种子保存策略和选择策略来微调进化。

首先是三维度反馈机制。StateFuzz 采用一种新颖的三维反馈机制来指导状态探索，由以下三个维度组成。

代码覆盖维度：StateFuzz 重用现有 fuzzer（例如 Syzkaller）的代码覆盖率反馈，只要测试用例遇到新代码，就会发出反馈信号。 这种反馈维度使模糊测试器能够保留发现新代码的种子。

值域边维度： StateFuzz 应用了一种新颖的值域范围维度反馈。 如果输入触发一个新的值域边，这意味着触发一个新状态，它会发出一个反馈信号。 它使模糊测试器能够保留发现新程序状态的种子，并在与遗传算法一起工作时实现智能状态空间探索。 例如，在图 4 所示的驱动程序代码中，状态变量 devp->hd_ireqfreq 和 devp->hd_hdwirq 都有 4 个取值域范围，即 [INT_MIN,-1],(-1,0],(0, 1],(1,INT_MAX]。当 devp->hd_ireqfreq 从 0 变为 1 时，取值域范围从 (-1, 0] 变为 (0, 1]。这样就会产生devp ->hd_ireqfreq 和 devp->hd_hdwirq新的取值域范围 。

极值维度： 有时由于缺少约束或者约束无法求解，我们无法解析某些状态变量的值域范围。 此外，发现一个新的极值也意味着程序进入了一个新的状态。 因此，我们提供了另一种新的反馈维度，可以交替跟踪状态变量的极值。 具体来说，模糊测试器记录测试历史中每个状态变量的上限和下限，并在新的测试用例设置状态变量超出其边界极值时发出反馈信号。 这种反馈维度使模糊测试器能够保留触发极值的测试用例。

接下来是StateFuzz的种子保存和选择策略。我们设计了一个三层种子语料库来根据每个种子触发的反馈信号的类型来保存种子。 有了这样的种子语料库，StateFuzz 然后周期性地从不同的层中选择种子来探索新的代码和新的状态。

首先是种子保存：鉴于三种不同的反馈机制，我们因此提供了一个三层种子语料库来存储分别发现新代码、新值域边和新极值的种子。如果种子同时触发多个反馈，它可以存储在多个层中。有时，发现新的值域边但执行了类似代码的种子过多，可能会填满队列，从而阻止模糊测试器探索其他代码。为了减少这种局部性，我们使用种子的控制流路径对种子进行聚类，并且我们不仅会在种子选择阶段调度种子，还会调度这些聚类（即bucket）。图5 演示了 StateFuzz 如何详细保存种子。在执行完一个测试用例后，StateFuzz 会检查是否产生了反馈信号，并根据反馈信号将测试用例放入不同的层。首先，如果测试用例发现新代码，则将其添加到种子语料库的第 1 层。其次，如果测试用例发现了新的值域边，StateFuzz 会将测试用例添加到第 2 层中的特定存储桶中，该存储桶由执行的基本块地址的哈希作为索引。如果这个测试用例的路径对于 StateFuzz 来说是新的，StateFuzz 会在 Tier-2 中创建一个新的 bucket 并存储这个测试用例，否则，它将这个测试用例存储在一个现有的 bucket 中。第三，如果测试用例发现新的极值，将被添加到种子语料库的 Tier-3 中。然后 StateFuzz 更新极值记录，并移除之前发现过时极值的种子，以最小化语料库。由于我们的最小化机制，Tier-3 中的种子数量不是很大，我们不需要使用桶来聚类种子。

对于种子选择算法，鉴于保留的三层种子语料库，StateFuzz 进一步应用特殊的种子选择策略来提高模糊效率。图6显示了 StateFuzz 如何从语料库中选择种子的细节。首先，StateFuzz 根据预定义的概率超参数 Pr 和 Pc 选择种子语料库的层。这里我们只是让语料库的三层有相同的被选中概率（即 Pr=3 和 Pc=3）。在层选择之后，StateFuzz 从所选层中选择一个种子。如果选择第 1 层或第 3 层，StateFuzz 从层中随机选择一个种子进行进一步变异。如果选择了第 2 层，StateFuzz 首先从该层中随机选择一个桶，然后从该桶中选择一个随机种子进行进一步的变异。这样，不同的桶就可以有平等的机会被选中。它避免了局部最优情况，即来自一个较大桶的种子比其他种子更频繁地被选择。由于每个桶代表一个控制流路径，这种种子选择策略将确保彻底探索不同的路径。此外，在每个桶内，可能有多个种子触发不同的状态。这个种子选择策略会在选择这个桶时尝试探索不同的状态

3 代码实现细节

StateFuzz 包含三个主要组件，包括程序状态识别、程序插桩和模糊测试循环，以及一些用于衔接各组件的脚本。在第一个组件中，StateFuzz 使用 DIFUZE 的修改版本来识别驱动程序的程序动作。此外，它通过 LLVM Pass识别由不同程序动作共享和访问的状态变量，其中利用来自 CRIX 的基于两层类型的间接调用分析来构建函数调用图。它使用Clang Static Analyzer (CSA) 通过模块内静态符号执行收集状态变量约束并推断每个状态变量的值域范围。在第二个组件中，为了更精确地跟踪状态变量，StateFuzz 利用points-to分析工具 SVF 来分析状态变量的别名，并跟踪对这些别名的访问。我们用变量名（对于非结构类型的全局变量）或它们的类型（对于结构的field）而不是特定的指针来标记状态变量，这是一种保守的解决方案，不需要复杂的指针分析。并且我们利用 SVF 来查找无法通过名称或类型识别的状态变量的别名，作为状态变量的补充。所有覆盖和程序状态跟踪指令都使用 LLVM SanCov 进行 插桩。为了跟踪状态，StateFuzz 插桩目标程序来跟踪状态变量的值。给定生成的状态变量列表，在编译期间，如果目标指针指向状态变量或其别名，StateFuzz 在每条Store指令之后插桩用于跟踪的代码。对于通过调用copy_from_user和memcpy等内存复制函数写入状态变量的操作，我们解析这些函数的目标内存类型，以根据类型检查目标内存中是否涉及状态变量。第三个组件基于现有的内核模糊测试引擎 Syzkaller。与 Syzkaller 类似，StateFuzz 使用三个字典来存储三个维度的覆盖率。对于 value-range 维度，我们将 state-variable ID 和 hit range ID 拼接为 state-variable 的 value-range 单元。然后对于相关状态变量对中的两个变量，我们计算它们的值域范围单元的哈希来表示值域边。字典键是值域范围的边，值是边的命中次数。对于极值维度，字典键是状态变量 ID，字典值是它们的极值。

4 实验评估

为了证明 StateFuzz 的有效性，我们首先评估基于变量的状态模型。 然后，我们评估 StateFuzz 的代码覆盖率和状态覆盖率。 之后，我们评估了StateFuzz 发现新漏洞的能力。 我们将 StateFuzz 与两个最先进的基于系统调用的 Linux 内核模糊测试器进行比较：Syzkaller 和 HFL。 HFL 是一个hybrid fuzzing方案，它通过符号执行来推断系统调用之间的依赖关系，并且在对 Linux 驱动子系统进行模糊测试时表现非常好。

实验环境准备

我们在两种环境中对 Linux 驱动程序进行了 fuzzing 实验：qemu-system-x86_64 上的 Linux 上游内核 v4.19，以及 Google 的 Android 手机 Pixel-4 上的 Qualcomm MSM-4.14 内核。在第一个实验中（即内核 v4.19），我们在具有 2 个 Intel Xeon CPU E5-2695 v4 (2.10GHz) 和 384GB RAM，运行 Ubuntu 16.04 LTS 的服务器上测试运行在 QEMU 中的内核。对于 Syzkaller 和 StateFuzz，我们为它们每个分配了 8 个虚拟机，每个虚拟机有两个 vCPU（即分配了 16 个 vCPU）。对于 HFL，为了公平比较，它分配有 4 个 VMS，每个 VM 有两个 vCPU（即分配了 8 个 vCPU）和 8 个额外的 vCPU 用于符号执行。在第二个实验（即 MSM-4.14 内核）中，我们在 Pixel-4 手机而不是 QEMU 中测试 MSM-4.14 内核。 MSM-4.14 中的许多设备驱动程序依赖于 QEMU 无法模拟的真实手机外设，从而阻止了 MSM 内核在 QEMU 上启动。因此，HFL 不能应用于 MSM 内核，因为它的符号引擎 S2E依赖于 QEMU 来执行动态二进制转换。我们按如下方式进行手机模糊测试：（1）按照 Android 调试文档的指示为手机构建和刷机，（2）生成和执行测试用例（即运行 syz-fuzzer 和 syz-executor）在手机上，以及 (3) 按照 Syzkaller 文档的说明，通过 USB 调试连接到手机的 PC 机器上监控 fuzzer（即运行 syz-manager）。 这台PC 机器运行 Ubuntu 18.04 LTS，配备 Intel Core i7-8700 CPU (3.20GHz) 和 32GB RAM。在这两种环境中，我们利用 LLVM 编译内核，启用 KCOV 和 KCOV_ENABLE_COMPARISONS 以收集代码覆盖率等。我们还启用 KASAN 来更好的检测crash。实验中涉及的所有模糊测试器都只使用由 DIFUZE 生成的系统调用模板进行模糊测试。为了区别 Syzkaller 和 HFL 的原始版本，我们分别使用 Syzkaller-D 和 HFL-D 来指代应用 DIFUZE 系统调用模板的原始 Syzkaller 和应用 DIFUZE 系统调用模板的原始 HFL。实验中涉及的所有模糊测试器都使用空的初始种子运行。为了更好地展示模糊测试器的性能并获得收敛结果，我们扩大了模糊测试的时间预算。我们对 Linux 上游内核测试 48 小时，对 MSM 内核测试 72 小时（由于 pixel-4 设备的计算能力较低，我们给它更大的时间预算）。所有 fuzzing 时间预算都不包括在状态模型构建上花费的时间。为了减少偏差，我们将所有实验重复三次。

状态模型评估

我们在上述 PC 机器中进行了预分析以构建状态模型。 StateFuzz 的预分析阶段平均需要 15 个小时。 具体来说，状态变量识别需要 6 小时，使用 SVF 进行指针分析需要 2 小时，通过静态符号执行收集约束需要 7 小时。 我们对每个源代码文件执行模块内符号执行（通过 Clang Static Analyzer）最多 1 小时，超过1小时则算作超时。 在我们的实验中，MSM 内核驱动子系统中的 1401 个文件中有 43 个触发超时，Linux-4.19 内核驱动子系统中的 2776 个文件中有 117 个触发超时。 StateFuzz 提取了 840 个程序动作，如图7 所示。丢弃指针类型变量后，StateFuzz 识别出 6,055 个状态变量和 18,921 个值域范围。每个状态变量平均分为 3 个值域范围。变量 sk_buff.len 具有最大范围数（即 157），它存储套接字数据缓冲区的长度，广泛用于网络通信。按照第 3.3 节中的方法，StateFuzz 识别了 25,778 个相关的状态变量对。因此，平均而言，一个状态变量可能有大约 4 个相关的状态变量。对于 MSM-4.14 内核，DIFUZE 标识了 1330 个程序动作。 StateFuzz 找到 5,037 个状态变量、18,743 个值域范围和 18,743 个有序的相关状态变量对。变量 diag_md_session_t.peripheral_mask 的范围最多，为 193。结果表明，一个状态变量的相关状态变量平均不超过 4 个。尽管 StateFuzz 跟踪每个相关状态变量对的两个变量的值域范围组合，但组合的数量是可以接受的，即分别为 25,778 和 18,743。此外，平均而言，每个状态变量的取值域范围少于 4 个（即分别为 3.12 或 2.65）。因此，程序状态位图中每个元素的选择平均少于 16 个。因此，它不会导致状态爆炸问题。

我们通过研究它们名称的语义来对提取的状态变量进行分类。根据经验，这些变量分为 6 类，分别是“explicit state”、“mode”、“flag”、“size”、“index”和“boolean”。首先，“explicit state”包含名称中带有显式单词“state”的变量。其次，“mode”和“flag”类别中的变量通常用于控制程序的行为。第三，“size”和“index”类别中的变量通常用于保存共享队列或缓冲区的状态。至于“boolean”，这些变量通常使用动词的过去时或进行时来命名，以表示程序状态。每个类别的变量在其名称中都包含特定的关键字。我们修改 Clang 静态分析器以从 AST 中的声明语句中提取状态变量名称。然后我们检查这些变量名称是否包含任何关键字并将它们分成上述类别。具体使用的关键字如图8 所示。我们使用列表中的关键字从上到下检查变量名称。图8显示了分类结果。结果表明，StateFuzz 发现的状态变量中约有一半包含这些关键字。 为了评估我们静态分析的准确性，我们分别从 Linux-4.19 和 MSM-4.14 中随机选择 4 个驱动程序进行验证。程序动作识别的准确性。我们手动识别这些驱动程序的所有程序动作以构建ground truth，然后验证 StateFuzz 识别的程序动作。如图9 所示，在 8 个驱动程序的所有 234 个动作中，StateFuzz 成功识别了 99% 的动作，只有 1 个误报和 2 个误报。误报是由 DIFUZE 将条件语句视为 ioctl 命令检查引起的。另一方面，DIFUZE在识别ioctl命令时漏掉了两个子命令，导致2个假阴性。状态变量识别的准确性。我们评估 StateFuzz 识别的状态变量。然而，手动验证所有变量并识别这些驱动程序中的状态变量是不可行的，因为在一个驱动程序中可能声明了数千个变量（例如，根据我们的 AST 分析，OSS 排序器驱动程序中有 2673 个变量）。相反，我们只收集名称中包含上述关键字的变量和 StateFuzz 识别的候选状态变量，并手动验证这些收集的变量以构造一个近似的基本事实。最终，我们收集到了 659 个变量，其中 StateFuzz 收集了 303 个，关键字匹配方法收集了 163 个，两者都收集了 193 个。根据我们对状态变量的定义，我们手动验证了所有这 659 个变量并识别出 221 个最终状态变量。 StateFuzz 成功识别了 197 个状态变量，占总数的 90%，比关键词匹配方法高出 49%。引入误报的原因有三个：首先，驱动程序通常通过读取和写入在驱动程序外部声明的 inode.i_size 等变量来与内核的其他部分（例如文件系统、网络）进行通信。 StateFuzz 可能会错误地将这些变量标记为状态变量，尽管它们并不代表驱动程序的状态。其次，由于 StateFuzz 遍历指令并根据函数调用图收集状态变量，调用图中不正确的被调用者可能会导致误报。第三，一些候选状态变量仅用于调试、输出或发送回用户空间。这些状态变量不会影响驱动程序的控制流和数据流。在 StateFuzz 产生的 299 个误报中，第一个原因引入了 141 个，第二个原因引入了 13 个，第三个原因引入了 145 个。我们试图减轻第一个原因引入的误报。具体来说，我们首先尝试识别不同驱动程序和内核共享的通用实用程序函数，然后从程序动作的执行轨迹中删除它们的指令。因此，仅在常用实用程序函数中访问的变量不会被标记为状态变量。我们启发式地将被超过 MAX_NUM 个函数调用的函数标记为实用函数。为了防止漏报等副作用，我们保守地将启发式阈值 MAX_NUM 设置为 300，因为核心驱动程序函数不太可能被超过 300 个函数调用。我们还进一步调查了这些误报状态变量对 StateFuzz 针对 Linux-4.19 和 MSM-4.14 的模糊测试活动的影响。我们发现在整个模糊测试活动中从未访问过 54 个（18%）假阳性状态变量，因此在 StateFuzz 的语料库中没有为这些变量保留模糊输入。其他 155 个（52%）变量没有推断值域范围，因此这些变量不能将模糊输入引入语料库以发现新的值域边。结果，299 个误报中的 209 个（即 70%）对 fuzzing 活动的影响可以忽略不计。总体而言，状态变量识别中误报的影响在模糊测试活动中是可以接受的。漏报的主要原因总结如下：首先，在构建LLVM bitcode文件时，如果相关函数位于不同的模块中，则没有链接，导致对函数内部的加载和存储指令缺乏分析。其次，调用图中缺少间接调用的目标调用者也会导致漏报。第三，StateFuzz 忽略了通过包装器读取或写入的状态变量。例如， atomic_inc 函数通常用于更新引用计数。请注意，我们没有发现上述效用函数过滤策略引入的假阴性，表明 MAX_NUM 的保守阈值是合理的。总之，StateFuzz 可以识别 99% 的程序动作并识别大约 90% 的状态变量，证明了我们静态分析的有效性。

覆盖率评估

为了展示 StateFuzz 在探索程序状态方面的能力，我们首先将其与 Syzkaller-D 的修改版本进行比较，其中我们仅应用额外的状态变量跟踪插桩来收集状态变量的值。我们将其记为 Syzkaller-D-col。我们没有在 Syzkaller-D-col 中引入任何新的反馈机制，并且该插桩仅用于日志记录。我们在 4.19.113 版本的 Linux 上游内核上进行了这个实验。命中值域范围计数。然后，我们收集 StateFuzz 和 Syzkaller-D-col 的每个单独值域范围的命中时间。为了更好地演示，我们计算每个值域范围 R 的两个 fuzzer 访问时间的比率。假设 StateFuzz 访问 R 访问了X 次，Syzkaller-D-col 访问 Y 次。如果 X/(X+Y) > 0.5，则意味着 StateFuzz 比 Syzkaller-D-col 更频繁地访问范围 R。因此，我们对所有状态变量范围的 X/(X+Y) 值进行排序。结果可以用图 10 中的累积分布函数 (CDF) 曲线来表示。它表明，超过 80% 的范围比超过 0.5，这意味着 StateFuzz 访问次数比 Syzkaller-D-col 的访问次数多 80%范围。此外，大约 20% 的范围比率大于 0.9，这表明 StateFuzz 访问这些范围的次数是 Syzkaller-D-col 的 9 倍。结果表明，StateFuzz 可以探索很少访问的状态。此外，在 Linux 上游 4.19 内核中，Syzkaller-D-col 发现了 20,701 个值域边，而 StateFuzz 发现了 27,117 个值域边，比 Syzkaller-D-col 多 32%。 如上所示，StateFuzz 不仅可以探索很少访问的值域范围，还可以探索更多的值域边，这意味着 StateFuzz 可以在我们的状态模型的指导下探索更多的状态。 为了验证 StateFuzz 是否能够在相同的时间预算内探索更多代码，我们将其与 HFL 和 Syzkaller 进行了比较。 本实验在 Linux 内核 v4.19 和 MSM-4.14 内核中进行。 由于 HFL 不支持 fuzzing 真正的 Android 设备，我们只使用 HFL-D 来用 QEMU 对 Linux 上游内核进行 fuzz。 如图 11 所示，我们的 StateFuzz 方法显示了代码边缘覆盖的优势。 在 Linux-4.19 中，StateFuzz 发现的代码边缘比 Syzkaller-D 多 19%，比 HFL-D 多 15%，而在 MSM-4.14 中，StateFuzz 发现的代码边缘比 Syzkaller-D 多 7%。结果表明，在相同的时间预算下，StateFuzz 可以实现比最先进的内核模糊测试器更高的代码覆盖率。

漏洞发现能力评估

在两个月的时间里，我们间歇性地使用 StateFuzz 对 Linux-4.19 内核和 MSM-4.14 内核进行了模糊测试。 StateFuzz 共发现 20 个漏洞，其中在 Linux-4.19 上发现 7 个，在MSM-4.14 上发现 13 个。 在 MSM-4.14 中发现的所有易受攻击的驱动程序都依赖于 Qualcomm SoC 或 Google Pixel 手机的特定外围设备，并且它们的代码不包含在 Linux 上游内核中。 我们向开发人员报告了所有这 20 个漏洞，其中 19 个得到了确认。 图12 显示了 StateFuzz 发现的漏洞。 出于安全考虑，我们隐藏了尚未修复的漏洞的函数名和文件名。 在已确认的 19 个漏洞中，有 14 个被分配了 CVE ID，3 个处于待处理状态，另外 2 个已被开发人员内部发现。 具体来说，谷歌或高通已经为 9 个已确认的漏洞分配了漏洞赏金奖励。为了进一步证明 StateFuzz 的漏洞发现效率，我们使用 Syzkaller-D、HFL-D 和 StateFuzz 对我们的目标进行模糊测试，并比较三个模糊测试器发现的漏洞数量。由于 HFL 不支持对真正的 Android 设备进行模糊测试，因此我们仅将 HFL-D 用于 Linux-4.19。我们将每个 fuzzing 活动重复 3 次，并将漏洞数量累积在一起。我们使用与第 5.1 节中提到的相同的时间预算。结果如图 13所示。在本实验中，StateFuzz 发现了 20 个报告的漏洞中的 19 个，比 Syzkaller-D 多 46%。具体来说，StateFuzz 发现了 Linux-4.19 中的所有 7 个漏洞，其中 HFL-D 发现了 6 个，StateFuzz 发现了- 涵盖 MSM 内核中的 12 个漏洞。 Syzkaller-D 在本实验中也没有发现唯一缺失的漏洞（MSM 诊断驱动程序中的越界写入）。此外，StateFuzz 在本实验中发现了 Syzkaller-D 和 HFL-D 发现的所有 13 个漏洞，表明 StateFuzz 在漏洞发现方面是有效的。我们进一步调查了仅由 StateFuzz 在 MSM-4.14 中发现的 5 个漏洞。在这 5 个漏洞中，StateFuzz 和 Syzkaller-D 都发现了 4 个易受攻击的代码片段。它表明 StateFuzz 在发现易受攻击的代码后可以更好地发现程序状态以触发漏洞。由于HFL 依赖模拟器，HFL无法在手机上测试 MSM-4.14。

消融实验

为了了解 StateFuzz 的工作原理并评估每个反馈维度的贡献，我们通过禁用单个功能来编译 StateFuzz 的三个变体。然后我们在带有变体的 Linux-4.19 内核中执行模糊测试。我们只启用代码覆盖率反馈来实现名为“C”的基线变体。变体 C-R 启用了值域范围跟踪和代码覆盖率的反馈维度。另一个变体 C-E 启用了极值跟踪的反馈维度以及代码覆盖率，而我们的完整方法 C-R-E 启用了所有三个反馈维度。图 14 展示了极值跟踪和值域范围跟踪都有助于代码覆盖率。 C-E 的代码边覆盖率比基线 C 高 9%，C-R 高 10%。 C-R-E 实现了 17% 的最高增长，这意味着三个反馈维度可以在发现更多代码方面相互促进。图 14 还表明，C-R 发现的值域边比基线 C 多 47%，而 C-E 仅多发现 16%。与 C-R 相比，即使启用了额外的极值跟踪，C-R-E 的值域边覆盖率也几乎没有增加。该实验表明，值域范围跟踪对增加值域边覆盖率的贡献最大。

4 总结

在本文中，我们评估了代码覆盖率引导的模糊测试方案的局限性，并提出了一种状态敏感的模糊测试解决方案 StateFuzz。 它利用静态分析来识别由多个程序动作访问的共享变量，并将它们用作状态变量来表征程序状态。 通过跟踪状态变量的值并使用两个状态变量的组合作为反馈，StateFuzz 可以在模糊测试期间有效地探索状态，同时增加代码覆盖率。 我们为 Linux 和 Android 驱动程序测试实现了 StateFuzz 原型。 它在 Linux 上游驱动程序和 Android 驱动程序中发现了 20 个漏洞。此外，StateFuzz 可以实现比现有驱动程序模糊测试方法更高的代码覆盖率和状态覆盖率。