[Paper] No Grammar, No Problem: Towards Fuzzing the Linux Kernel without System-Call Descriptions

🤔

No Grammar, No Problem: Towards Fuzzing the Linux Kernel without System-Call Descriptions

Abstract

整个计算生态系统的完整性取决于操作系统（OS）的安全性。不幸的是，由于操作系统代码的规模和复杂性，每年都会在操作系统中发现数百个安全问题[32]。因此，操作系统一直是应用安全分析工具的主要用例。近年来，模糊测试已成为自动查找软件安全问题的主要技术。因此，模糊测试已被用于发现内核中的成千上万个错误[14]。然而，现代操作系统模糊测试工具（如Syzkaller）依赖于每个内核接口的精确、广泛和手动创建的测试套件和语法。由于对语法的依赖，当前的操作系统模糊测试工具面临着规模扩展的问题。

在本文中，我们提出了FUZZNG，这是我们对在操作系统上进行系统调用模糊测试的通用方法。与Syzkaller不同，FUZZNG不需要复杂的系统调用接口描述即可运行。相反，FUZZNG利用基本的内核设计特性来重塑和简化模糊测试的输入空间。因此，FUZZNG只需要为每个新目标提供一个小配置：实质上是一个文件列表和模糊测试器应该探索的系统调用编号列表。

我们为Linux内核实现了FUZZNG。在Syzkaller的广泛描述下，对超过10个具有详细描述的Linux组件进行FUZZNG测试，结果显示，平均而言，FUZZNG实现了Syzkaller覆盖率的102.5%。FUZZNG发现了9个新的漏洞（其中5个是Syzkaller已经进行了多年的广泛模糊测试的组件）。此外，FUZZNG的轻量级配置文件大小不到Syzkaller手动编写的语法的1.7%。关键是，FUZZNG在没有初始种子输入或专家指导的情况下实现了这一点。

I. Introduction

操作系统在现代计算中仍然是最具安全性关键性的构建模块之一。操作系统在管理资源和执行应用程序之间的隔离方面的角色使其成为攻击者的目标，这些攻击者试图打破操作系统提供的保护。鉴于操作系统安全性的关键性质，模糊测试工具已经识别出并帮助修复了操作系统内核中的数千个错误。最近，操作系统模糊测试工具的成功展示了编写安全的低层代码的困难，甚至推动了一些倡议，如在Linux内核中支持更安全的编程语言，以及利用内存标记等硬件特性来实现对内存损坏问题的低开销防御[23]，[44]。目前大多数操作系统模糊测试工具专注于关键的系统调用接口，这使得用户空间应用程序可以请求内核提供服务。

Syzkaller[14]，最多产生的系统调用模糊测试工具，已经成为Linux内核开发生命周期中不可或缺的组成部分，在内核提交信息中已经被提及超过2,700次。因此，syzkaller本身已经发展成为一个庞大的项目，拥有200多名贡献者。关键是，Syzkaller只能对足够由"syzlang"语法描述的系统调用进行模糊测试。这些语法编码并注释了系统调用输入和输出中提供的资源类型。因此，syzkaller社区的很大一部分工作集中在为系统调用开发和完善"syzlang"描述上，这对于Syzkaller的成功至关重要。

开发这样的语法是一个手动的过程，需要详细了解所涉及的接口（即一组系统调用）。因此，语法容易出现人为错误，并可能导致覆盖范围的缺失或过度拟合（阻止模糊测试工具探索代码可能被覆盖的所有状态和场景）。此外，有时Syzkaller需要编写额外的测试代码来对特别复杂的接口进行模糊测试。例如，为了对Linux内核虚拟机（KVM）接口进行模糊测试，该接口用于支持安全关键的虚拟化软件，Syzkaller开发人员编写了891行详细的系统调用描述，243个与KVM相关的常量，以及额外的879行KVM特定的C语言测试代码（如图1所示）。尽管Syzkaller拥有数以万计的手工编写的"syzlang"规则，但当前的流程无法扩展到每年添加到Linux内核中的数百万行代码的模糊测试[33]。学术研究已经认识到Syzkaller使用手动创建的syzlang语法存在可扩展性问题，并专注于自动生成语法的研究。像Difuze、IMF、SyzGen和KSG这样的作品应用静态和动态分析技术来自动生成系统调用描述[12]，[18]，[9]，[51]。Difuze、IMF和SyzGen的设计和评估针对的是没有基准手动描述的接口，如Android驱动程序和macOS API。KSG的描述似乎提高了Syzkaller的覆盖率，但源代码尚未发布，上游基于Syzkaller的Linux模糊测试工作仍然仅依赖于手动编写的描述。一些描述生成的上游努力仅限于识别传递给ioctl系统调用的结构参数的类型[36]。重要的是，自2018年以来，Syzkaller项目一直在跟踪自动生成Linux系统调用描述的需求，目前这仍然是一个未解决的问题[53]。

其他内核模糊测试工作集中在改进syzkaller的输入生成[52]，[57]，改进针对复杂内核接口的模糊测试支持[59]，对特定设备-内核接口进行模糊测试[40]，[49]，通过快照提高内核模糊测试的性能[50]，开发用于覆盖引导的灰盒模糊测试OS内核的工具[47]，或将模糊测试与符号执行相结合以找到更多错误[27]。Moonshine[38]已经确定了维护准确的系统调用描述的成本。然而，所提出的替代方法需要收集和分析来自实际程序的大量系统调用跟踪。找到并运行与复杂内核接口广泛交互的程序本身就是一个具有可扩展性问题的复杂问题。基于手动编写的描述或实际跟踪的模糊测试工具可以迅速达到内核代码的深层部分。然而，手动收集系统调用跟踪或编写描述的过程容易出现人为错误：从描述和跟踪中立即获得的覆盖率收益可能会导致模糊测试工具不再能够有意义地执行的代码部分被掩盖。作为对此的证明，FUZZNG在Syzkaller标记为已覆盖的代码中发现了漏洞。

在本文中，我们提出了FUZZNG，这是一种无需详细描述每个接口即可对系统调用进行模糊测试的系统。默认情况下，内核通过系统调用接口公开了一个巨大的输入空间，涵盖了一个进程的所有虚拟内存（例如，通过指向缓冲区的指针）和整个文件描述符表。因此，尽管从表面上看，系统调用接受最多六个数字参数，但一个简单的模糊测试策略，只是简单地将随机参数传递给系统调用，将无法取得足够的结果，因为大多数参数将是语义上无效的（例如，指向未映射内存的指针或不存在的文件描述符号码）。目前的系统调用模糊测试工具依赖于详细的系统调用描述和实际跟踪来生成有效的系统调用参数，从而避免了模糊测试与由内核提供给用户空间应用程序的进程内存和文件描述符相关联的整个输入空间。然而，这些基于语法的方法只是将生成有效系统调用的负担转移到了开发人员身上。

FUZZNG的核心观点是，可以通过对系统调用输入空间进行重塑来摆脱对详细的系统调用描述的依赖，以实现以下目标：(1) 不需要特定于系统调用的语法，(2) 使系统调用模糊测试适用于经过实战验证的现成模糊测试工具。为了实现这种重塑，FUZZNG利用了内核代码在正常操作中已经使用的API，具体而言是用于访问用户空间内存和管理文件描述符的API。通过应用输入空间重塑，FUZZNG基本上依赖于前面提到的“简单”模糊测试策略的变体，直接从模糊测试工具（如libFuzzer）传递系统调用参数。通过这种技术，FUZZNG消除了对个别系统调用的详细描述和测试套件的需求。简而言之，FUZZNG在模糊测试之前不依赖于任何对每个系统调用的详细预分析。

我们为Linux内核实现了FUZZNG，并在Syzkaller具有详细描述的10个Linux接口上对其进行了评估。我们发现，尽管输入空间的重塑使得FUZZNG可以避免详细的系统调用描述，但与Syzkaller相比，FUZZNG在覆盖范围和发现漏洞的能力方面表现出色。例如，FUZZNG能够设置基于KVM的虚拟机，配置虚拟内存槽，填充指令，运行虚拟机，使其退出到KVM指令仿真代码，并在没有特定了解KVM接口或其100多个不同的ioctl命令的情况下发现错误。类似地，FUZZNG创建的输入可以自动创建并执行复杂的bpf程序和io_uring序列。所有之前能够针对这些复杂接口的系统都需要人工编写的系统调用描述。此外，FUZZNG在已经被Syzkaller覆盖的代码中发现了新问题（详见第五节的详细内容），这凸显了手动编写的描述往往会导致接口拟合不足或过度拟合的情况。总之，我们提出了以下贡献：

我们描述了Linux系统调用接口所暴露的输入空间的主要特征。接着，我们涵盖了当前模糊测试工具中常见的系统调用语法。最后，我们描述了这些手动编写的语法可能出现的微妙陷阱。
我们介绍了我们的系统调用模糊测试工具FUZZNG，它消除了对专家精心设计的语法的需求。与以前的方法不同，FUZZNG重新塑造了内核的输入空间，而不是试图自动生成系统调用描述。我们证明了与Syzkaller相比，FUZZNG在竞争中表现出色，在Syzkaller已经有详细描述的组件上，平均达到Syzkaller覆盖率的102.5%。我们的结果展示了基于语法的方法的陷阱，通过在Syzkaller已经覆盖的代码中发现漏洞。
我们描述了FUZZNG基于快照的模糊测试方法，以及我们为无需语法的内核模糊测试问题量身定制的变异和执行策略。我们介绍了FUZZNG对于“细化”输入的新颖方法，利用在执行过程中学到的信息来提高输入语料库的质量。
我们报告了FUZZNG发现的9个新漏洞，其中有5个漏洞位于Syzkaller已覆盖的组件中。为了促进对无需语法的内核模糊测试的进一步研究，我们将开源FUZZNG的所有组件。

秉承开放科学的精神，我们将在 https://github.com/BUseclab/FuzzNG 上发布 FuzzNG 的源代码。

II. Background

在本节中，作为我们工作的背景，我们描述了操作系统、系统调用和操作系统模糊测试相关的方面。在Linux上，系统调用由一个整数 "id" 来标识。系统调用支持最多六个字大小的参数（在大多数体系结构上通过寄存器进行通信）。系统调用可以返回一个值，这个值也是通过寄存器提供的。由于传递给系统调用的数值参数大小受限，一些系统调用参数在语义上代表更大的数据结构。具体而言，Linux 内核文档强调了两种类型的系统调用参数，用于间接传递任意大小的数据给内核：指针和文件描述符 [1]，[2]。系统调用使用文件描述符参数允许“用户空间引用内核对象”[1]。对于涉及大量参数的系统调用，这些参数被放置在“通过指针传递给内核的结构中”[2]。例如，alarm 调度信号传递给进程。唯一的参数是距离报警过期的秒数，直接作为整数传递给内核。然而，write 系统调用需要三个参数：文件描述符、将写入文件的缓冲区以及缓冲区的长度。虽然文件描述符和缓冲区的长度表示为可以适应寄存器的整数，但缓冲区的长度可以是任意的。因此，内核希望缓冲区参数的寄存器包含实际缓冲区的地址。 Linux 有数百个系统调用，作为用户空间应用程序从内核请求服务的主要机制。然而，在内部，内核可以对同一系统调用具有许多实现。例如，ioctl 系统调用用于控制设备，作为内核中许多驱动程序的主要配置机制。应用程序通过打开与设备关联的所谓特殊文件（通常位于 /dev 目录中的文件）来获取对驱动程序的引用（即文件描述符）。然后，应用程序可以通过将 ioctl 作为第一个参数来配置驱动程序。在内部，内核将每个文件描述符与 file_operations 结构关联起来，该结构指向将用于透明调用的函数，如读、写和关闭文件。使用 file_operations，内核将 ioctl 请求路由到特定于设备的系统调用的实现，这取决于特殊文件的类型（例如，字符设备与图形加速器）。因此，由于文件描述符和指针参数，Linux 数百个系统调用仅仅是通往数百万行内核代码的狭窄窗口。

A. System-call fuzzers and grammars

像Syzkaller和Trinity这样的系统调用模糊测试工具依赖于语法或规则，这些语法或规则有助于生成有效的系统调用以及相关的文件描述符和指针参数。无需语法的模糊测试工具可以简单地将由模糊测试工具提供的整数作为参数传递给系统调用。然而，由于指针和文件描述符参数引发的实际上是无限制的系统调用输入空间，这种模糊测试工具很快就会变得无用，如第一节中所讨论的。因此，当前的系统调用模糊测试工具依赖于内核接口的详细语法。例如，Syzkaller需要注释结构类型、标志字段、枚举和常量，这些都作为系统调用参数传递。此外，Syzkaller还依赖于对每个系统调用创建的资源（如文件描述符）的手动注释，以确定有效的系统调用序列。这些注释将阻止Syzkaller尝试在没有先调用open来打开相应的文件（例如/dev/中的文件）的情况下使用ioctl系统调用与驱动程序进行交互。

尽管Linux具有数百个系统调用，但系统调用的行为可能在参数上发生巨大变化。例如，write系统调用在所写的文件类型（例如，磁盘上的文件与套接字或管道）不同的情况下会使用大不相同的代码路径。每种不同类型的系统调用调用都需要其自己的Syzkaller描述。因此，Syzkaller包含了数以万计的描述代码行，由数十名开发人员贡献。这些描述是用一种称为“syzlang”的领域特定语言编写的，旨在描述系统调用接口。尽管这是一个巨大的社区努力，但是对于内核接口的系统调用缺乏完整的描述仍然是当前系统调用模糊测试工具的一个已知限制因素[53]。

在本节的剩余部分，我们将描述系统调用模糊测试工具面临的主要困难，以及现有模糊测试工具使用的语法如何试图减轻这些困难。

Pointers: 如上所述，系统调用通常期望一个或多个参数包含指向位于用户空间进程内存中的数据结构的指针。高效的模糊测试工具，如Syzkaller，具有对这些数据结构的描述，使它们能够识别指针参数，并创建和变异相应的数据结构。然而，指针对于仅仅传递变异值作为参数的简单模糊测试工具来说是一个挑战；即使该值指向有效的虚拟地址，简单模糊测试工具也无法知道它应该在内存中的相何处放置变异的数据，即简单的模糊测试工具无法得知相应的数据结构。

通过语法，Syzkaller可以意识到系统调用是否需要一个指针参数。这些语法编码了指针应该引用的数据的长度和类型（例如，平面缓冲区或带有各个字段的结构体）。例如，图2显示了与vhost VIRTIO卸载子系统相关的VHOST_SET_VRING_ADDR ioctl调用的Syzkaller描述。系统调用的最后一个参数被表示为对vhost_vring_addr类型结构体的“指针”。基于描述的模糊测试工具，如Syzkaller，需要对指针参数进行详细的注释，以及内核在用户空间进程中访问的每个结构体。

File-Descriptors: 在Linux上，文件是受内核管理的特权资源。因此，文件操作是通过系统调用发起的。首先，用户空间进程使用诸如open、socket或pipe等系统调用打开文件。在内部，内核为每个进程保留了一个已打开文件的表格。由于一个进程通常打开多个文件，open系统调用返回一个整数文件描述符（或fd），进程可以将其视为已打开文件的句柄。对于每个新打开的文件，内核都会分配最低可用的整数文件描述符，从0开始递增。对于后续的文件相关系统调用，如read、write、mmap和ioctl，进程将整数文件描述符作为参数传递给内核。在内部，内核使用fdget() API在进程的文件描述符表中查找相应的文件对象，该表包含了处理系统调用所需的所有信息。

整数文件描述符对于模糊测试工具构成了一个挑战。典型的进程只打开了一小部分文件。因此，模糊测试工具的随机变异极不可能生成与有效（即已打开）文件相关联的整数系统调用参数。正如前面讨论过的，问题加剧的原因在于文件相关系统调用的行为高度依赖于文件类型。即使模糊测试工具猜测到一个有效的文件描述符整数，它还需要同时选择一个对于该类型文件有效的系统调用（和参数）。为了解决这些问题，系统调用模糊测试工具使用的语法依赖于文件描述符的特殊注释。例如，在图2（第1行）中，syzkaller的描述指示VHOST_SET_VRING_ADDR ioctl调用的第一个参数必须是一个文件描述符。描述还指定了描述符必须是fd_vhost类型。在其他地方，Syzkaller包含了针对open("/dev/vhost..")系统调用的描述，其返回值带有fd_vhost类型的注释。通过这样丰富的描述，Syzkaller确保将有效的文件描述符编号传递给VHOST_SET_VRING_ADDR ioctl调用，并且这些文件描述符与先前打开的vhost文件相关联。

因此，文件描述符和指针参数与大的抽象输入空间（用户空间内存和内核对象）相关联。虽然系统调用依赖于其他看似复杂的参数类型，比如“Magic Number”（只有少数特定值有效）和标志字段（其中一个整数可以表示多个状态/设置），但模糊测试工具已经获得了强大的机制（例如 redqueen/cmplog[5] 和 value-profile[48]）来有效识别通过整数传递的魔法值和标志，因为这些挑战并不是操作系统内核独有的问题。然而，模糊测试指针和文件描述符需要从根本上考虑相应的更大输入空间。

B. Managing File-Descriptors

Linux实现了一组用于管理文件描述符（fd）的系统调用。如上所述，诸如open和socket之类的系统调用会创建新的fd。close系统调用用于销毁fd。此外，dup系列的系统调用可以用于复制文件描述符。例如，dup2系统调用允许进程将对现有文件的现有引用复制到某个特定的整数文件描述符上：

int dup2(int oldfd, int newfd);

在dup2调用之后，与旧的文件描述符（oldfd）相关联的文件也与新的文件描述符（newfd）相关联。在这种情况下，内核将把文件与用户提供的文件描述符编号相关联，而不是遵循上述提到的默认的“最低可用”策略。

C. Pointer APIs in Linux

在现代Linux系统中，内核和用户空间内存位于虚拟内存的不同“半区”。如上所述，内核经常将系统调用参数解释为指针。然而，内核必须谨慎处理这些指针，因为它们可能来自恶意进程。恶意指针可能指向内核地址，而不是用户地址，或者可能指向另一个线程正在写入的位置（可能创建数据竞争）。由于访问用户空间内存中的数据是一种常见模式，Linux内核实现了特殊的API，如copy_{from,to}_user和get_user，必须用于访问用户空间内存中的数据。对用户空间的访问被如此仔细地处理，以至于CPU架构已经实现了专门的机制，以确保无意中的用户空间指针解引用是不可能的：在支持监管模式访问防止（SMAP）功能的现代Intel架构上运行的Linux上，必须清除CR4寄存器中的特殊位才能实现对用户空间内存的访问。这进一步确保对用户空间内存的访问不能是偶然的，而应该通过集中的API进行。

D. Automatic Grammar Generation

多个研究尝试自动或半自动地收集系统调用的语法。语法可以通过静态或动态分析技术自动收集。通常，这些方法依赖于内核交互的种子跟踪，由于缺乏实现对内核组件进行完全覆盖的用户空间应用程序，这些种子跟踪难以收集。白盒静态和动态分析侧重于相对浅层的启发式方法，例如用于定义系统调用和特定ioctl参数类型的源代码模式。自动推断的语法受到这样一个事实的影响，即分析中的小失误可能对生成的语法产生严重影响。例如，如果一个ioctl依赖于多个嵌套的结构体（即，一个结构体指向另一个结构体，依此类推），但是分析未能将第二级结构体与第一级结构体中的指针字段关联起来，那么语法将无法描述第二级及其以后的任何层次。我们将在接下来的章节中演示FUZZNG不具有相同的限制，因为FUZZNG不试图注释各个参数和结构体字段，而是重新塑造和模糊化内核向用户空间暴露的基本输入空间。

III. Approach

在本节中，我们介绍了FUZZNG的特点，这些特点使得在没有详细注释的情况下能够有效地进行系统调用模糊测试。FUZZNG通过hook与指针和文件相关的内核API，以及根据需要将从现成的模糊测试工具获得的半随机参数变形为每个系统调用的有效值，来重新塑造输入空间。在第四节中，我们将解释我们的解决方案如何融入FUZZNG的整体设计。

A. Reshaping the input-space

FUZZNG方法的核心是“重新塑造”系统调用的输入空间。对于提供随机参数给系统调用的模糊测试工具，其性能较差，因为它在输入空间上的模型是不完整的（它没有机制来有意义地模糊fd和基于指针的参数）。然而，简单地扩展模糊测试工具可访问的输入空间，例如允许模糊测试工具将模糊数据写入进程内存的任意位置，不能改善性能，因为模糊测试工具不太可能猜到系统调用实现将从哪些用户空间地址读取。没有反馈的情况下，只是将随机整数参数传递给系统调用的模糊测试工具无法知道在哪里放置指针读取的数据，或者应该打开哪些文件描述符并传递给后续的系统调用。重新塑造指的是一种机制，FUZZNG通过该机制为模糊测试工具提供了所涉及输入空间的动态“视图”。也就是说，在任何时刻，FUZZNG都知道内核正在主动访问的内存和文件描述符。使用API hook，FUZZNG在内核引用指针或文件描述符时暂停模糊测试工具输入的执行，并在继续执行输入之前采取措施填充相应的用户空间区域或文件描述符编号。因此，模糊测试工具无需对fd或指针参数进行详细描述，因为FUZZNG会根据需要拦截相关的内核访问。实现输入空间重塑的一种机制可以直接替换内存访问和文件描述符API的返回值为模糊数据。然而，FUZZNG将模糊数据放置在内存访问和文件描述符API引用的位置。这种技术的优势在于避免了在没有hook的现成内核中不可能出现的行为。例如，这种方法防止FUZZNG在错误的指针地址（例如，空指针或内核指针）提供模糊数据。这种设计的一个重要优点是，当FUZZNG发现一个漏洞时，可以轻松生成一个“重现器”，可以与漏洞报告一起提供，以在未经修改的内核中触发漏洞（与FUZZNG无关）。为此，在模糊测试后，FUZZNG将崩溃的输入转换为简单的系统调用序列（类似于Syzkaller），省略了hook。

通过内核API挂钩重新塑造输入空间，FUZZNG使得系统调用接口在没有详细的系统调用描述或种子输入的情况下变得适合于模糊测试。由于通过API挂钩提供的动态反馈，FUZZNG可以自动详细了解其他模糊测试工具在离线状态下编码为系统调用描述的指针和文件描述符参数。由于FUZZNG重新塑造了内核的基本文件描述符和内存输入空间，所以其方法甚至适用于复杂的接口，如KVM和io uring，在这些接口中，自动化技术（如ioctl参数类型的静态分析）生成的语法细节不足。图3展示了FUZZNG如何重新塑造输入空间，以便内核不会因为无效的指针和文件描述符而拒绝大部分输入。在本节的其余部分，我们将描述FUZZNG的方法，涵盖了系统调用输入空间的这两个特性。

B. Pointers

正如前面提到的，系统调用通常依赖于用户空间应用程序提供的指针。内核在提交系统调用后启动指针访问，访问的大小取决于系统调用的类型和参数。普通用户空间应用程序的开发人员对系统调用如何处理指针参数具有专业知识（例如，来自文档和手册），因此在调用系统调用之前，他们会编写代码来填充指针，以相应的数据。然而，FUZZNG没有关于内核如何处理各个系统调用参数的知识。相反，FUZZNG利用了这样一个事实，即总体上，从内核代码到用户空间内存的访问必须通过集中式API进行，由于安全措施（例如SMAP）。例如，内核提供了一个copy_from_user函数，其语义类似于memcpy，但专门用于允许将数据从用户空间内存复制到内核内存。FUZZNG对copy from user和get user API应用轻量级挂钩，以即时了解对用户空间内存的访问。当内核组件使用其中一个API进行访问时，FUZZNG会暂停访问，并填充相应的用户空间内存范围，以提供模糊器提供的数据。因此，一旦FUZZNG恢复访问，内核组件自然地访问模糊器控制的数据。通过即时填充用户内存访问，FUZZNG避免了识别进程内存中应包含模糊器生成数据的位置的猜测工作。

Userspace access safety net: 绝大多数内核对用户空间内存的访问都是通过集中式内核API进行的。然而，在极少数情况下，内核组件可能会实现自己的API版本，或者禁用保护。例如，内核虚拟机（KVM）子系统希望虚拟机内存映射到用户空间。当启动KVM虚拟CPU（使用KVM_RUN ioctl）时，内核直接指示CPU从用户空间的虚拟机内存中执行指令。在这种情况下，VM指令在非特权模式下执行，并且为VM分配的用户空间内存是在没有SMAP保护的情况下访问的。这种行为将绕过FUZZNG的重新塑造，因此必须适当处理。为了捕获绕过集中式API的用户空间访问，FUZZNG使用附加机制来挂钩用户空间内存访问。为此，FUZZNG通过映射尽可能多的页面来“膨胀”模糊处理的地址空间（请注意，这些页面不会占用物理内存，因为操作系统只有在首次访问页面时才分配物理页面）。通过映射尽可能多的虚拟页面，我们确保对用户空间内存的访问很可能与有效的虚拟页面映射相对应。然而，这些用户空间页面标记为“不存在”，在任何访问时触发页面故障。然后，使用userfaultfd（一种可以在用户空间处理页面故障的设施），FUZZNG在继续内核组件执行之前，填充每个访问的页面。与基于API挂钩的方法不同，基于userfaultfd的挂钩不依赖于任何内核代码模式，例如使用copy from user。因此，它捕获了所有在不通过集中式API的情况下内核尝试访问用户空间内存的情况。默认情况下，此挂钩仅在每页触发一次，对于后续的访问，该页面将被标记为存在，并且不会再触发页面故障。然而，由于FUZZNG填充了整个页面，从同一页面进行的进一步读取将继续返回模糊数据。

C. File-Descriptors

如第 II 节所讨论的，内核通常期望系统调用参数包含文件描述符号。然而，通用的模糊器会为相应的参数提供随机数，这些随机数极不可能是有效的内核文件对象。为了克服这种模糊的障碍，FUZZNG 将模糊器提供的文件描述符号与由进程打开的现有文件对象关联起来。FUZZNG 钩住文件描述符 API，以确保模糊器生成的 fd 号重新映射为有效的文件对象。在内部，FUZZNG 利用了这样一个事实，即内核将文件描述符与底层的 struct file 对象相关联，该对象包含有关文件权限、偏移、支持的操作等信息。内核开发人员必须使用 fdget() API 将文件描述符号解析为底层的 struct file 对象。因此，FUZZNG 可以钩住每个尝试解析文件描述符（有效或无效的）。然后，使用 dup2 系统调用，FUZZNG 可以将（可能无效的）模糊整数与有效的文件关联起来。这确保内核解释为 fd 的任何模糊器提供的值都映射到一个有效的打开文件。

IV. FUZZNG

在其核心部分，FUZZNG 钩住了与系统调用相关的基本内核 API。在本节中，我们将描述这些钩子如何适用于构成 FUZZNG 系统的各个组件。首先，我们将描述 FUZZNG 的模糊引擎，①QEMU-Fuzz: QEMU-Fuzz主要负责生成输入数据，解析覆盖率数据以识别“有趣”的输入数据，并通过虚拟机快照技术在输入执行之间重置状态。接下来，我们详细介绍 ②mod-NG: mod-NG 是对 Linux 内核进行的修改，以协助进行模糊测试。mod-NG 对内核进行了修改，使其能够钩住文件描述符（fd）和用户内存访问的 API，以及用于检测内核崩溃的错误报告函数。最终我们将介绍 ③NG-Agent: NG-Agent 是用于调用被模糊测试的系统调用的用户空间代理。NG-Agent 负责将输入数据提供给正在测试的内核，配置 kcov 来收集内核的覆盖率数据，并输出每个执行的输入的“规范”版本（在第 IV-C3c 节中解释）。图 4 提供了 FUZZNG 的概述。

A. QEMU-Fuzz

FUZZNG 使用 QEMU-Fuzz，其是我们基于修改版本的 QEMU-KVM 虚拟化器和 libFuzzer 输入变异器构建的基于虚拟机快照的模糊测试工具（图 4 中的 1）。系统调用通常会在用户空间中修改寄存器/内存。它们还可以在内核中建立状态，该状态在系统调用之间保持不变（例如，被 read/write/seek 等系统调用修改的文件描述符偏移）。这对于模糊测试器来说是一个挑战，因为模糊测试器在输入从相同的起始状态下执行时表现最佳。此外，模糊测试输入可能会超时，或者导致 NG-Agent 进程崩溃和损坏。为了解决这个问题，FUZZNG 在运行在虚拟机中的内核下执行系统调用，并在每个模糊测试输入之后从快照中恢复整个虚拟机状态。与 Syzkaller 类似，每个 FUZZNG 模糊测试输入表示一个系统调用序列。FUZZNG 的快照模糊器确保在每个输入之后，代理进程和内核状态都被完全重置到一致的快照状态。这种方法与像 Syzkaller 这样使用“fork-server”来执行输入的模糊测试器不同。也就是说，每个输入在单独的进程中执行。与 Syzkaller 不同，FUZZNG 没有可用于确保输入是良好行为并且不会在虚拟机中创建性能问题的系统调用描述。

QEMU-Fuzz 实现了一个针对模糊测试的虚拟设备，虚拟机可以使用该设备初始化快照并请求重置。此外，虚拟设备提供的接口用于建立 NG-Agent（见第 IV-C 节）在虚拟机中预期接收新的模糊测试输入的内存区域，以及虚拟机存储内核覆盖率数据的页面。QEMU-Fuzz 将每个新输入放入客户机的物理内存中约定的位置。当代理执行完输入后，它使用虚拟设备接口向 QEMU-Fuzz 请求重置。QEMU-Fuzz 将覆盖率数据提供给 libFuzzer 用于输入变异。为了实现这一点，我们修改了 libFuzzer 以支持两种 kcov 覆盖率数据格式（程序计数器跟踪和比较跟踪）。然后，QEMU-Fuzz 重置客户机的内存、寄存器和设备状态到先前初始化的快照。QEMU 的内置虚拟机快照/重载功能主要针对长期快照存储或实时迁移，而不是模糊测试。为了适应模糊测试特定的快照工作负载，QEMU-Fuzz 实现了自定义的虚拟机重置，它将所有快照存储在内存中，并使用 KVM 的脏页跟踪功能仅重置自上次快照以来写入的页面，以降低开销。最后，QEMU-Fuzz 使用计时器来强制虚拟机在输入执行超过配置的超时时限时进行重置。

B. mod-NG

在第 III 节中，我们解释了 FUZZNG 如何钩住与用户内存访问和文件描述符相关的内核代码。为了实现这一点，我们添加了一个名为 mod-NG 的内核模块（图 4 中的 2），其中包含我们用于拦截通过 copy_from_user 类型 API 和文件描述符操作的代码。

copy from user APIs：当 mod-NG 拦截到一个用户内存读取 API 调用时，它会唤醒一个名为“copy-from-user”（CFU）的用户空间处理线程（如图 4 中的 CFU），并向该线程提供有关读取位置和大小的详细信息。CFU 线程的任务是将模糊数据填充到用户空间内存的相应位置。一旦 CFU 线程通知内核已处理完请求，mod-NG 就会继续执行 copy_from_user 调用。值得注意的是，我们使用 CFU 线程和 mod-NG 的组合，而不仅仅是修改 copy_from_user，直接将模糊测试输入字节复制到内核内存中，有多个原因。

a. 通过在用户空间填充读取的数据，我们确保进程实际上可以写入该区域。因此，我们避免了在不可能的位置提供数据（例如，如果读取的目标是未映射的内存）。

b. mod-NG不需要了解模糊器输入。在虚拟机中，与模糊器输入直接交互的唯一组件是NG-Agent。

**c. **用户内存访问的userfaultfd安全机制（UFFD在图4中）也是基于一个用户空间线程的。以类似的用户空间线程处理CFU和userfaultfd挂钩，确保设计的一致性：只有用户空间组件直接从模糊输入中读取。与未修改的系统类似，系统调用输入（包括内存缓冲区）在用户空间进程的上下文中填充。

File-descriptors APIS: mod-NG重塑了数值文件描述符引入的输入空间。也就是说，mod-NG确保任意由模糊器提供的文件描述符号码与内核中的实际底层文件对象相关联。否则，内核会拒绝大多数系统调用，因为它们将包含对未分配文件描述符号码的引用。

为了重塑文件描述符空间，mod-NG挂钩了alloc_fd API，内核使用这个API来分配新的文件描述符，以处理诸如open的系统调用。通过挂钩alloc_fd，mod-NG跟踪由代理进程分配的所有文件描述符号码，存储在“FD堆栈”中。

当内核使用fdget API获取与文件描述符号码关联的底层文件对象时，mod-NG会检查堆栈，以确定文件描述符号码是否已经分配。如果文件描述符已分配，mod-NG简单地恢复API的执行，返回与文件描述符关联的现有文件对象。然而，如果文件描述符未分配，mod-NG会调用dup2来复制现有的文件描述符（从fd堆栈中获取）到传递给fdget的文件描述符号码参数。默认情况下，mod-NG会复制最近分配的文件描述符（位于堆栈的顶部）。然而，mod-NG还向NG-Agent公开了一个特殊的系统调用fuzz-set-fd-offset，用于选择传递给后续dup2操作的堆栈顶部索引。我们将在下一节中详细描述此系统调用的调用方式。

Crash Hooking: mod-NG挂钩了内核的dump_stack API，当发生内核错误时会调用此API。在这种情况下，mod-NG使用Port-IO通知QEMU-Fuzz，将输入保存为潜在的崩溃用于分析。mod-NG还跟踪NG-Agent进程的崩溃（SEGFAULT），并使用Port-IO请求QEMU-Fuzz立即从快照中恢复。代理进程可能会崩溃，因为没有防御措施阻止模糊系统调用覆盖用户空间进程中的敏感代码、堆等区域。代理进程的崩溃并不表示内核存在问题，但它们会减慢模糊测试过程，因为代理无法通知QEMU-Fuzz输入已经执行完成（导致超时）。为了避免在NG-Agent崩溃的情况下出现超时，SEGFAULT跟踪允许FUZZNG改善模糊测试性能。

C. NG-Ageng

由于FUZZNG是一个系统调用模糊测试工具，而系统调用是由用户空间应用程序发起的，因此我们依赖一个代理进程（图4中的2）来调用模糊系统调用序列。NG-Agent是负责将从QEMU-Fuzz接收的二进制模糊输入转换为通过系统调用传递的数据的组件，包括系统调用ID、系统调用参数和内核访问的用户空间内存内容。在启动时，代理进程读取一个配置文件，识别应该进行模糊测试的组件，并与QEMU-Fuzz建立通信。由于QEMU-Fuzz生成原始的二进制输入，NG-Agent具有一个解释器，将原始字节转换为一系列系统调用。代理进程还启动负责处理用户空间内存访问挂钩的CFU和UFFD线程。当代理进程从输入中读取字节时，它会将这些字节组装成一个“规范”的输入版本（在第IV-C3c节中解释）。在执行完输入后，代理进程会请求虚拟机重置并获取一个新的输入，以继续进行模糊测试。

Agent Initialization: 在启动时，NG-Agent进行覆盖率收集的初始化，扩充进程内存，并设置用户内存和快照接口。

a. Configuring kcov: NG-Agent配置kcov以在内核上收集覆盖率数据[26]。kcov是一种适用于诸如Syzkaller等模糊测试工具的Linux内核代码覆盖率机制。通过启用kcov，NG-Agent进程可以访问一个包含内核覆盖率数据的kcov内存区域。kcov有两种模式：一种是报告已覆盖的内核程序计数器（PCs），另一种是报告已覆盖的比较指令以及相应的操作数（CMP跟踪）。这两种模式是互斥的（每个模糊测试进程可以选择跟踪PCs或比较指令）。CMP跟踪模式的信息有助于帮助模糊测试工具自动解决代码中的约束（例如ioctl请求号检查）。因此，现有的模糊测试工具如Syzkaller在模糊测试期间使用这两种模式。NG-Agent支持这两种覆盖率模式。此外，FUZZNG还扩展了kcov的CMP模式，以报告内核中使用strncmp和memcmp等API执行的比较。这个改变受到了现代用户空间模糊测试工具的启发，这些工具可以通过钩子函数自动识别目标期望在输入中的字符串，例如与字符串和内存比较相关的函数。在第V-B节中，我们将展示这个功能对于填充模糊测试输入中的字符串，以满足内核通过系统调用参数接收的期望，是非常有用的。在进行模糊测试之前，每个NG-Agent实例（在自己的虚拟机中运行）会查询QEMU-Fuzz，以确定是使用PC模式还是CMP模式。

b. Inflating Process Memory: 通过钩子拦截用户空间内存访问，FUZZNG可以在不了解编码在语法中的指针参数和结构布局的情况下进行复杂接口的模糊测试（见第II-A节）。然而，在Linux中，普通进程只映射了可用虚拟内存空间的一小部分（在x86-64上为128 TB）。因此，通常情况下，随机生成的由模糊测试工具提供的用户内存地址不太可能由任何物理内存映射支持，而且FUZZNG将无法使用模糊测试生成的数据填充这些虚拟地址。

为了解决这个问题，NG-Agent通过使用mmap系统调用尽可能多地映射内存来“扩充”其地址空间。NG-Agent保留了一小部分（16MB）的内存未分配，以便模糊测试生成的mmap系统调用能够成功。请注意，尽管底层硬件无法支持约128 TB的映射虚拟地址，但只有在首次访问虚拟页面时才分配物理内存。在单个模糊测试运行的整个生命周期中，只有极小部分的“扩充”内存会被访问并由物理页面支持。在这个扩充步骤之后，几乎所有有效的用户地址（< 0x800000000000）都与一个映射关联。因此，随机生成的地址很有可能命中由NG-Agent映射的有效用户空间内存，而且FUZZNG的钩子可以在内核发出系统调用后填充内存。

c. User-Memory Hook Service Threads: 如第III-B节所述，FUZZNG会钩住内核对用户空间的内存访问。为此，FUZZNG依赖于两种机制 - 钩住类似copy_from_user的API和使用userfaultfd。对于这两种机制，NG-Agent会初始化线程（在图中表示为CFU和UFFD），负责将钩住的用户内存读取所引用的内存填充为来自模糊测试输入的字节。我们在第IV-C2节中更详细地描述了这些线程的功能。

d. Communicating with QEMU-Fuzz: NG-Agent通过使用Linux的iopl提升其特权级别，并执行Port-IO指令直接与QEMU-Fuzz通信。每个Port-IO指令都会导致进入QEMU-Fuzz，后者会处理该请求。当NG-Agent执行了与覆盖率和内存相关的初始化后，它就准备好执行模糊测试输入。为了启动模糊测试过程，NG-Agent使用Port-IO向QEMU-Fuzz提供模糊测试输入分配的内存地址和kcov覆盖率内存地址。由于QEMU-Fuzz使用物理寻址与虚拟内存进行交互，代理进程使用/proc/self/pagemap接口将虚拟地址转换为物理地址。然后，NG-Agent请求QEMU-Fuzz创建一个VM快照并提供新的模糊测试输入。一旦NG-Agent解释了输入，它就请求进行VM重置，然后模糊测试过程重复进行。

Agent Config: NG-Agent将由QEMU-Fuzz生成并提供的输入解释为系统调用序列。FUZZNG依赖于代理配置来针对内核的特定组件。我们将内核特性的逻辑分组称为"组件"。示例包括设备驱动程序（console/ptmx、rdma、vhost）、接口（KVM、io uring）和通用API（bpf）。该配置由两个部分组成：

a. Files: 在这里，我们指定代理在进行模糊测试之前打开的特定组件文件（位于/dev/中）。

b. System-Call: 列出了模糊测试程序可以生成的系统调用。对于每个系统调用，我们指定参数的数量，并为每个参数提供一个可选的“掩码”。

举个例子，在图1中的KVM配置中，第一行指定应该打开/dev/kvm文件，因为它是与KVM子系统[55]的所有交互的入口点。其余的六行只是列出了可以与KVM交互的系统调用。每一行表示一个系统调用，模糊测试程序可以调用该系统调用，以及该系统调用所期望的参数数量。可以选择为某些参数提供掩码。掩码不是严格必要的，但有助于限制慢速系统调用。例如，在图1中，我们为读/写系统调用指定了掩码，以限制操作的最大大小。此外，我们还对mmap系统调用应用了掩码，以避免可能会破坏代理的覆盖范围/代码区域的映射。收集与内核组件进行接口的系统调用ID列表可以通过阅读内核文档或检查接口支持的文件API（例如，检查file_operations结构中的字段）来轻松获取。与Syzkaller相比，系统调用参数几乎没有约束（除了用于减少明显无效/浪费参数的掩码）。相反，我们依靠输入空间重塑钩子和覆盖率反馈来识别具有有效/有趣参数的输入。每个参数（包括文件描述符编号和指针地址）只是直接从二进制模糊测试输入中提取的。

c. The NG-Agent Interpreter: QEMU-Fuzz提供给NG-Agent的输入只是一个字节缓冲区。为了将这些字节转换为一系列系统调用，FUZZNG实现了一个解释器。解释器使用一个4字节的值（ASCII“FUZZ”）将输入分割为各个操作。现代模糊测试程序（如libFuzzer）可以自动识别这些“魔术”值并将它们插入输入。有两种类型的操作：System-Calls 调用和 User-Memory 模式。

System-Calls: 对于每个操作，NG-Agent检查第一个字节，并使用它从可用系统调用的表中选择一个系统调用，根据在NG-Agent配置中定义的索引。一旦NG-Agent选择了系统调用，它读取该系统调用所需的参数数量（如代理配置中指定的），并在指定的情况下对每个参数应用一个参数掩码。最后，NG-Agent使用syscall()libc API来调用系统调用。

在内部，NG-Agent还将fuzz-set-fd-offset系统调用添加到表中，以便模糊测试程序可以指定哪个fd应该用于响应未分配的fd编号的fdget调用。模糊测试程序通常会生成与多个文件描述符交互的输入。例如，为了运行KVM虚拟机的输入，必须对/dev/kvm文件执行KVM_CREATE_VM ioctl，该ioctl会为VM创建一个fd。然后，输入必须对新创建的VM fd执行KVM_CREATE_VCPU ioctl，该ioctl会创建一个VCPU fd。最后，输入必须对VCPU fd执行KVM_RUN ioctl。由于mod-NG将新创建的fd存储在栈上，与文件描述符交互的系统调用（如ioctl）将针对最后创建的文件描述符。然而，如果在KVM_RUN调用之后，输入试图执行KVM_SET_MEMORY_REGION ioctl（这是特定于VM fd的），系统调用将失败，因为VCPU fd在mod-NG的栈顶。因此，我们为输入提供了调用fuzz-set-fd-offset系统调用的能力，以选择要使用的堆栈上的哪个文件描述符。由于VM fd位于堆栈的第二个位置（索引1），模糊测试程序在调用KVM_SET_MEMORY_REGION ioctl之前调用fuzz-set-fd-offset(1)。由于模糊测试程序可能需要一些时间来“猜测”fd的偏移量，因此在我们的评估中，有一半的模糊测试虚拟机（参见第V-A节）中，我们将模糊测试程序配置为在系统调用失败时（返回-1）自动调用fuzz-set-fd-offset，循环遍历所有打开的fd。在此模式下，模糊测试程序不需要在堆栈上猜测fd的偏移量，因为代理解释器会自动尝试所有可能的选项。这最大化了系统调用以正确类型的文件描述符执行的机会。

User-Memory-Accesses: 与系统调用操作不同，用户内存访问是由内核而不是NG-Agent发起的。但是，在输入中它们仍然被表示为操作。当发生用户内存访问时，它要么由CFU线程处理，要么由UFFD线程处理（取决于是否使用了copy from user-APIs）。为了用模糊数据填充内存中的相应位置，这些线程将fuzzer输入中的下一个操作解释为User-Memory模式。根据访问的大小，从而需要填充访问所需的模糊数据量，NG-Agent使用不同的策略。对于较小的访问（少于256字节），NG-Agent只是从fuzzer输入中读取所需的确切字节数，并将它们用于填充内核访问的区域。这个数据量对于大多数传递到内核的结构体来说是足够的。对于较大的访问，NG-Agent读取操作的第一个字节，并将其解释为重复模式的长度（从后续字节中提取），用于填充内核读取。一旦CFU / UFFD线程使用输入中的字节填充内存区域，它们会更新全局输入指针，以便在主线程中运行的系统调用解释器知道要超越用户内存访问操作。
Enforcing Input Structure: 与Syzkaller等方法不同，后者的输入包含关于系统调用类型和必须填充的结构字段的详细信息，FUZZNG没有关于模糊输入的语义信息，允许它预测与输入对应的系统调用序列和用户内存访问。FUZZNG输入只是由“FUZZ”分隔的字节。然而，当FUZZNG执行一个输入时，它会动态地获取关于所表示的系统调用的有价值的信息。例如，当FUZZNG解释输入时，它可以获取到
- 输入中被忽略/未使用的部分。例如，多余的系统调用参数或参数的屏蔽部分。
- 输入中被规范化为不同值的部分。例如，系统调用操作的第一个字节相对于系统调用表的大小被规范化。
- 填充用户内存访问操作所需的字节数。

为了利用这些有价值的信息，我们对libFuzzer进行了修改，以支持在模糊测试期间修改输入，以便在执行期间可以使输入规范化。我们所描述的所有解释器操作都具有特定的长度要求。然而，这些要求通常无法由libFuzzer提供的输入满足：操作可能包含太多或太少的字节。为了解决这个问题，NG-Agent在解释模糊测试输入时动态地“调整”操作，以确保每个操作包含所需的精确字节数。因此，NG-Agent强制实施输入结构，并确保由libFuzzer保存的输入不包含多余的字节（参见图5的示例）。由于存储的输入中的所有字节都用于操作，输入变异更有可能实现新的代码覆盖。

对于系统调用，如果操作没有足够的字节来填充所有系统调用参数，NG-Agent将从模糊测试输入中删除操作。相反，如果操作后有多余的字节，FUZZNG将从输入中删除多余的字节。同样，FUZZNG确保用户内存访问操作中的字节数恰好与填充访问所需的字节数匹配。如果没有足够的字节，FUZZNG将使用一个伪随机数生成器（从rdtsc中获取的种子）将随机数据插入到输入中，直到操作的大小与访问相匹配。因此，结果输入将包含一个完美大小的用户内存访问操作（如果需要，填充了随机数据），该操作可以用于将来的执行。

此外，NG-Agent将系统调用参数屏蔽直接应用于输入。例如，如果代理配置指定参数具有屏蔽位0xF000，而模糊测试输入为0xDEADBEEF，NG-Agent会在输入中将0xDEADBEEF替换为0x0000B000。NG-Agent还将用于选择系统调用类型的字节标准化（限制为一定范围内的值），其数量由fuzzer可访问的系统调用数决定。

在NG-Agent执行完输入后，它将规范化的版本返回给QEMU-Fuzz。默认情况下，libFuzzer不支持修改模糊测试提供的数据的长度或内容，因此我们进行了轻微的修改以允许这样做。结果是，存储在语料库中的输入不包含任何多余的字节，操作大小保证与所需的字节数相匹配。请注意，由于FUZZNG存储了“规范化”的输入，使用伪随机数生成器来调整操作的大小不会引发非确定性问题：任何随机生成的字节都存储在语料库中的输入中。

总之，我们实现的FUZZNG结合了一个用于生成输入和重置状态的快照模糊测试引擎（QEMU-Fuzz），一个用于调用系统调用并将相关内存填充为模糊数据的用户空间代理（NG-Agent），以及用于钩住与系统调用相关的内核API并向代理提供有关API调用的动态反馈的内核模块（mod-NG）。

V. Evaluation

我们对FUZZNG的模糊测试能力进行评估，以回答以下研究问题。

RQ1：与基于语法的最新系统调用模糊器相比，FUZZNG是否能够实现竞争性的覆盖率？（见§ V-B）

RQ2：与Syzkaller的syzlang描述相比，FUZZNG配置的平均大小是多少？（见表I）

RQ3：FUZZNG是否能够在Linux内核中发现新的漏洞？（见§ V-D）

RQ4：与Syzkaller的fork-server相比，FUZZNG的快照模糊测试性能如何？（见§ V-E）

A. Experimental Setup

我们在配备双插槽 Intel Xeon E5-2600 v3 系列 CPU 的服务器上进行了所有实验，内存范围在192到256 GB之间。我们的所有模糊测试实验都针对Linux内核5.12进行。FUZZNG使用多个QEMU-Fuzz虚拟机在多核系统上进行内核目标的模糊测试。 FUZZNG为每个虚拟机配置了不同的模糊测试选项：

Coverage Mode：如第IV-C1a节中所述，KCOV支持两种覆盖率模式：程序计数器（PC）覆盖率和比较（CMP）覆盖率。PC覆盖率使FUZZNG能够始终确定何时达到了新代码。CMP覆盖率允许FUZZNG解决输入约束，例如“Magic Number”ioctl请求号。因此，FUZZNG将一半的模糊器虚拟机配置为PC覆盖率，另一半配置为CMP覆盖率。这在存储仅仅达到了新分支（PC覆盖率）的输入和用于克服复杂值比较（CMP覆盖率）的输入之间取得了平衡。
Errorless Input: FUZZNG将所有虚拟机中的八分之一配置为丢弃导致系统调用失败的输入（即返回-1的调用）。这鼓励模糊器找到“高质量”的系统调用序列，以达到深层内核状态，而无需任何失败/浪费的系统调用。由于错误代码路径肯定是需要被测试的，因此此功能仅对每八分之一的虚拟机启用。
File-Descriptor “Cascading”: 如IV-C3a节所述，在此模式下，当涉及到文件描述符（fd）的系统调用失败时（返回-1），FUZZNG使用fuzz-set-fd-offset功能来遍历所有可用的fd，为每个fd重复执行系统调用，直到系统调用成功或所有打开的fd都已尝试。这减少了模糊器需要正确猜测每个系统调用应该使用哪个fd的需要。然而，由于许多系统调用会返回错误，这会减慢输入执行的速度，因此我们仅为一半的虚拟机配置了此模式。

注意，这些选项不是相互排斥的（例如，一个虚拟机可以同时使用CMP覆盖率和级联模式）。所有并行的模糊器将新的有趣输入存储在相同的语料库目录中。因此，即使一个输入仅在单个模式下找到了新的覆盖率，它也会被所有模糊器实例变异。

B. Coverage

FUZZNG的主要贡献是能够在与当前系统调用模糊测试器相比，对复杂的内核接口进行模糊测试，并且在测试每个新接口时的设置成本最小。因此，我们将FUZZNG的覆盖率性能与事实上的Linux内核模糊测试器Syzkaller以及应用关系学习技术于Syzkaller的文法以提高变异效率的Healer进行了比较。我们将所有三个模糊测试器配置为对相同的内核构建进行模糊测试。对于每个模糊测试的内核组件，我们提供了一个单独的覆盖率白名单，该白名单仅将KCOV覆盖率仪表化应用于实现该组件的源文件（例如，KVM、bpf等）。因此，FUZZNG、Syzkaller和Healer只对与正在测试的相关组件进行交互的系统调用报告覆盖率（并存储输入）。我们根据以下标准选择要进行模糊测试的组件：

Syzkaller（以及由此推出的Healer）必须支持该组件（即Syzkaller仓库包含相关手工编写的描述）。
该组件必须在x86-64 Linux上可用。
该组件必须是一个系统调用接口。
该组件的描述符必须是全面的。为了确保比较的公平性和普适性，我们根据syzlang描述文件的大小对组件进行了排序，并基于最大的描述符文件来选择模糊测试清晰定义的接口。

我们在20个核心上对每个组件进行了168小时（7天）的模糊测试。我们的边缘覆盖率结果（平均值在3次运行中进行了平均）列在表I中。对于七个组件，FUZZNG实现了比Syzkaller更高的覆盖率。对于其余三个组件，FUZZNG的边缘覆盖率与Syzkaller的差距在7％以内。平均而言，FUZZNG达到了Syzkaller覆盖率的102.5％。 Healer在RDMA代码上没有实现任何覆盖率，因为它依赖于一个不包含RDMA描述的较旧版本的Syzkaller。我们发现，开源版本的Healer（2efbb44c7d）在我们评估的组件上实现的覆盖率低于Syzkaller。Healer旨在有效地识别系统调用之间的关系。在我们的内核配置中，只有目标组件受到覆盖率仪表化。因此，仅将能够增加目标组件覆盖率的系统调用添加到语料库中。因此，Healer对Syzkaller的改进受到限制，因为模糊器自然地针对特定组件。此外，仓库维护人员提到，与Healer论文中使用的私有版本相比，开源版本的Healer在许多方面都存在限制，这很可能解释了覆盖率差异[52]，[3]。

我们将仅由Syzkaller和Healer达到的覆盖率/边缘与FUZZNG进行了比较。每个组件的结果如图6所示。我们手动检查了覆盖率，并发现了Syzkaller/Healer覆盖而FUZZNG未覆盖的边缘的几个常见原因。Syzkaller和Healer支持故障注入，允许模糊器在内核API调用中强制出错（例如，SLAB分配、futex）。我们没有为FUZZNG实现这个功能。因此，一些内核中的错误处理代码未被FUZZNG覆盖，但被Syzkaller覆盖。此外，Syzkaller（以及使用Syzkaller执行器的Healer）可以使用多个线程执行测试用例。目前，FUZZNG从单个线程运行所有系统调用。因此，负责任务引用计数的组件部分只有Syzkaller覆盖。Syzkaller覆盖的KVM代码的很大一部分与在不同的x86操作模式（实模式、保护模式和长模式）中对VM的指令仿真有关。KVM按照CPU模式不同对指令进行不同的仿真。然而，由于实模式VM的设置与长模式VM相比差异较大，因此没有反馈来引导输入生成朝向不同的仿真上下文。Syzkaller使用虚拟系统调用，显式编码操作模式，不需要复杂的变异来达到代码。然而，FUZZNG能够完全覆盖一些指令仿真例程（在所有x86模式下），因此在给予足够时间的情况下，FUZZNG可能会覆盖更多的代码。在BPF中，我们发现FUZZNG的基于libfuzzer的变异器生成有效BPF程序的速度较慢。FUZZNG迅速找到了生成最小可能的有效16字节BPF程序的方法，然而，生成较长的程序需要同时插入字节到BPF程序中，并增加描述程序大小的长度字段，因此FUZZNG无法生成大型BPF程序，从而限制了覆盖范围。在将来，可以通过使变异器意识到长度字段来解决这个问题，FUZZNG可以通过将字节值与用户空间访问长度进行相关来识别长度字段。

然而，正如图6所示，FUZZNG也覆盖了Syzkaller+Healer对所有组件（除了binder）未覆盖的代码部分。此外，合奏模糊测试已经被证明优于单个模糊器[11]。因此，使用FUZZNG和基于Syzkaller的技术的合奏模糊测试将会是有益的。由于FUZZNG和Syzkaller都具有自己的输入表示形式，因此协同模糊测试需要一个可以在输入格式之间进行转换的适配器。另外，我们监控了在模糊测试KVM时随着时间的推移，Syzkaller和FUZZNG实现的覆盖率。结果如图7所示。如预期，由于其全面的语法套件，Syzkaller最初明显优于FUZZNG，但覆盖率很快达到平稳状态。值得注意的是，FUZZNG的无语法方法最终在模糊测试的第60个小时超越了Syzkaller。使用FUZZNG的潜在好处显而易见，因为覆盖率增益不受手动编写的语法的限制。FUZZNG在覆盖率方面的初始“滞后”是可以预期的。但是，由于FUZZNG存储了语料库输入，随后的模糊测试运行将从高覆盖率开始，使得初始运行后的滞后变得无关紧要。相反，FUZZNG不依赖于语法，可以在没有人工干预的情况下继续发现新的代码。

C. Config-Size

我们在表格I中比较了FUZZNG的配置文件大小和Syzkaller的syzlang描述。这个比较代表了将对新组件的支持添加到每个模糊测试器中的实现成本。需要注意的是，对于Syzkaller，我们只包括了syzlang描述，省略了任何特定于组件的测试用例，因为这些代码与不相关的Syzkaller代码交错在一起。因此，我们低估了将新组件添加到Syzkaller中所需的代码行数。平均而言，FUZZNG的配置文件比Syzkaller的描述要小98.3%。

D. Bug-Finding

FUZZNG的覆盖率评估主要关注那些具有广泛的Syzkaller描述并且在数年内一直受到Syzkaller模糊测试的组件。因此，我们不指望在这些代码中发现太多的漏洞。尽管如此，FUZZNG还是在Syzkaller模糊测试过的代码中发现了以前未知的漏洞。此外，我们选择了3个Syzkaller不模糊测试的驱动程序（mmcblk、megaraid、nvme），并为它们创建了FUZZNG配置（总共17行配置）。总共，FUZZNG在Linux内核中发现了9个以前未知的漏洞（见附录）。其中，有5个漏洞位于具有syzlang描述的组件中，并且被Syzkaller很好地覆盖。FUZZNG还在没有Syzkaller描述的三个组件中发现了漏洞。所有的漏洞都是在120小时的测量活动中发现的，并正在进行负责任的披露。接下来，我们将讨论三个案例研究。

KVM仿真代码中的空指针解引用：FUZZNG在KVM的emulate_int代码中发现了一个空指针解引用漏洞，该代码负责模拟中断。为了找到这个漏洞，FUZZNG需要使用独立的ioctl调用来创建一个虚拟机（VM）、创建一个虚拟中央处理单元（VCPU）、为VM创建一个内存槽，并启动VM。当CPU访问VM的内存以运行CPU指令时，FUZZNG使用模糊器数据填充相应的区域。模糊生成的指令会陷入并引发VMEXIT到KVM的模拟代码中，其中由于虚拟化上下文格式不正确导致发生了空指针解引用。尽管Syzkaller在emulate_int代码上具有全面的覆盖，但Syzkaller并没有发现这个漏洞，因为VM的设置完全由硬编码的测试用例处理，该测试用例设置寄存器和页表，并且在VM内部执行的指令由指令生成器生成，该生成器设计用于创建格式良好的指令序列。FUZZNG不依赖于任何特定于KVM的测试用例。因此，尽管FUZZNG需要更长的时间才能达到与Syzkaller相同的覆盖率，但是FUZZNG的变异器对调用的系统调用具有完全的控制权，而不受描述和测试用例的基本限制。这使得FUZZNG能够在其他模糊测试器无法充分执行的代码中发现漏洞，因为这些模糊测试器受到刚性语法的限制。
o uring任务退出代码中的空指针解引用：FUZZNG在io uring线程管理代码中发现了一个空指针解引用漏洞。如果在io uring线程管理代码执行时，调用io uring的进程引发了终止信号，那么就会暴露潜在的竞争条件，因为线程管理代码会更新任务的IO相关位图（触发空指针解引用）。NG-Agent在用户内存异常线程中中止进程，触发了该漏洞。尽管Syzkaller对io uring进行了模糊测试，但它没有捕获到这个漏洞。
MegaRAID代码中的使用后释放：UZZNG在MegaRAID SAS RAID控制器的驱动代码中发现了一个使用后释放漏洞。MegaRAID驱动使用实例结构来跟踪各个MegaRAID设备的状态。FUZZNG创建了一个输入，生成一个ioctl调用，导致一个实例被释放，然后调用一个管理命令，试图将与DMA相关的物理地址写入被释放的结构中，从而触发错误。值得注意的是，Syzkaller没有为此设备提供任何描述，因此也没有发现这个漏洞。

E. Execution Per Second

FUZZNG实现了虚拟机快照模糊测试，以便在测试用例之间进行清理。与FUZZNG不同，Syzkaller采用了轻量级的fork-server方法。我们在4个核心上对复杂但大多数是硬件无关的接口bpf进行了为期24小时的FUZZNG和Syzkaller模糊测试。结果发现，平均每个核心的FUZZNG每秒执行154个测试用例，而Syzkaller每秒执行177个测试用例。检查所有模糊测试组件的总执行次数，我们发现与这个结果没有明显偏差。因此，与Syzkaller相比，FUZZNG的全面虚拟机快照方法实现了可比的性能。此外，这表明FUZZNG的覆盖率与Syzkaller相比，源于其对输入空间的重塑，而不是执行速率方面的巨大差异。

VI. Discussion

尽管FUZZNG取得了积极的结果，但我们简要讨论其局限性和进一步改进的方向

A. Other Kernel Fuzzer

内核一直是模糊测试的主要目标。大多数内核模糊测试工具依赖于细粒度的手工编写或推断出的系统调用语法。FUZZNG提出了一种运行时钩子技术，以避免需要详细的语法。然而，其他模糊测试工具已经研究了内核模糊测试问题空间的不同部分。在这里，我们讨论FUZZNG是否与现有的模糊测试方法兼容。

Moonshine收集和提炼系统调用跟踪（来自strace），并将其转换为可以与Syzkaller一起使用的种子。未来的工作可以将Moonshine应用于为FUZZNG生成种子（Moonshine论文中指出，为非Syzkaller模糊测试工具添加支持是简单的）[38]。

Healer使用关系学习来提高Syzkaller变异的效率。我们在第五节的实验中显示，当模糊测试单个组件时，Healer的效益有限。然而，如果未来的工作将FUZZNG扩展到模糊测试整个内核，那么Healer的技术可以用于学习FUZZNG生成和执行的系统调用之间的关系，从而提高模糊测试效率。

其他内核模糊测试工具，如Difuze和SyzGen，旨在自动恢复接口的Syzlang描述。这些方法依赖于单独的阶段来生成接口语法并使用语法进行模糊测试。与此不同，FUZZNG在一个阶段中操作，通过重新塑造输入空间进行模糊测试 - 避免了详细语法的需要。

Difuze对内核代码执行静态分析，以自动推断ioctl-based设备接口的描述。特别是，Difuze特别强调了恢复ioctl命令值和参数类型（通过为操作数执行跨过程的类型传播，用于copy_from_user参数）。FUZZNG通过对copy_from_user操作进行运行时钩子，并通过收集KCOV CMP覆盖来自动推断ioctl命令值。但是未来的工作可以借鉴Difuze的思想，在FUZZNG中添加一个受Difuze启发的静态阶段，自动生成FUZZNG配置的变体（例如，通过识别与子系统交互的所有系统调用）。

SyzGen针对闭源内核（如MacOS）并应用符号执行来自动恢复接口的语法。SyzGen恢复的参数类型包括字符串、字节数组、指针和长度字段。SyzGen输出恢复接口的Syzkaller描述。由于FUZZNG重新塑造了系统调用的输入空间，它可以透明地通过运行时钩子对指针和数组进行模糊测试。SyzGen的符号执行技术还可以自动推断整数参数的范围和表示标志字段的整数参数，但是我们发现即使没有这些字段的注释，开箱即用的模糊测试引擎（如libfuzzer）也能表现良好。尽管如此，SyzGen的技术可以用于向FUZZNG自动提供有关参数类型的反馈（无需创建显式的语法），这可能会提高模糊测试效率。

B. Full-Kernel Fuzzing

Syzkaller的默认部署会对所有具有syzlang描述的系统调用进行模糊测试。这种方法能够达到需要与多个内核组件同时交互的代码行（并找到其中的错误）。目前，FUZZNG不能任意地打开命名文件，我们依赖于配置和覆盖率过滤器来将模糊器集中在单个组件上。然而，最近的研究表明，通过观察覆盖率，可以应用"关系学习"来自动推断与每个文件关联的受支持系统调用以及常见的系统调用序列[52]。通过将相同的技术应用于FUZZNG，并调整变异器以检测和生成有意义的输入序列，可能可以在不限制模糊器到单个组件或依赖配置的情况下对内核进行模糊测试。

模糊测试在学术界引起了广泛的关注。在本节中，我们对与内核模糊测试相关的研究进行了简要概述。一个重要的推动因素是American Fuzzy Lop (AFL) [62]模糊器的发布，它推广了覆盖引导的模糊测试方法，适用于各种软件。研究人员致力于提高模糊测试的性能，通过改进输入调度 [25]、[58]、[43]、突变算法 [35]、[8]、[42] 和输入反馈 [4]、[63]、[17] 等方面取得了进展。其他系统专注于应用符号执行 [61]、[29]、[28] 来克服障碍，例如与“魔法常数”和校验和的比较 [41]。像AFL与laf-intel [30]和libFuzzer [48]这样的模糊器应用了源代码插桩，以识别与魔法字节的比较并生成可以通过这些比较的输入。其他工作对复杂的目标进行了模糊测试，例如代码解释器 [60]、[56]、[22]、[19]、编译器 [31]、[10]、[34]、网络协议 [6]、[16]、[13]，以及虚拟设备 [20]、[37]、[46]、[45]、[7]。V-Shuttle [39]表明，通过钩子技术可以在没有语法的情况下对复杂的虚拟化软件进行模糊测试，该技术主要用于模糊测试直接内存访问（DMA）相关的API。近年来，基于快照的模糊测试受到了广泛关注，特别是用于大型、有状态的模糊测试目标。Agamotto引入了基于QEMU的高性能模糊测试快照 [50]，支持在目标的执行过程中不同点创建多个快照，以加速模糊测试。Nyx在QEMU/KVM的基础上实现了用于模糊测试的快速寄存器、内存和虚拟设备快照 [45]。类似地，FUZZNG实现了一个基于QEMU的快照模糊测试工具QEMU-Fuzz，专门用于模糊测试Linux内核，并接受KCOV格式的覆盖率信息。操作系统内核在学术界得到了广泛的关注，已经有针对内核竞态条件 [24]、文件系统 [59] 和外设接口 [49] 的模糊测试系统。类似地，VIA [21]对操作系统驱动程序进行模糊测试，以识别可能损害机密计算环境中安全保证的错误，该环境中不信任虚拟设备代码。kAFL引入了基于硬件的覆盖率收集机制，以实现无需源代码插装的操作系统内核覆盖引导模糊测试 [47]。与这些工作不同，FUZZNG的重点是减少通用系统调用模糊测试所需的描述和测试框架。

操作系统中的系统调用接口在操作系统模糊测试社区中受到了最多的关注。从90年代开始，就有多个模糊器仅通过生成随机参数进行操作，例如tsys、iknowthis、sysfuzz、xnufuzz和kg crashme [54]。像Trinity这样的系统调用模糊器通过整合系统调用描述改进了简单的系统调用生成算法[54]。随着覆盖引导的模糊器在用户空间应用中逐渐流行，Syzkaller被创建出来，将基于描述的模糊器的优势与覆盖引导结合起来，用于对Linux进行模糊测试。如今，Syzkaller是最受欢迎的系统调用模糊器，已经被纳入了Linux内核开发周期，并且已经移植到了XNU、FreeBSD和Windows等操作系统中 [14]。Syzkaller向Linux内核开发人员报告了数千个错误，已经成为内核开发生命周期中的关键部分。与过去的方法不同，FUZZNG利用内核钩子来实现与Syzkaller相当的覆盖率，而无需详细的系统调用描述。

一些研究旨在自动生成系统调用描述。Difuze通过对内核代码进行静态分析，以便自动推断出用于模糊测试的设备接口的描述 [12]。IMF依赖于通过应用程序钩子收集的内核API交互日志，以推断出macOS系统调用的语法规则[18]。SyzGen依赖于数据挖掘和手动收集的日志跟踪的符号执行，以自动生成macOS系统调用的语法规则 [9]。值得注意的是，所有这些系统都专注于自动生成系统调用描述，然而这些工作都没有对具有明确定义的手动规范的接口与Syzkaller进行比较。KSG使用符号执行自动生成syzlang描述，实现了与Syzkaller相当的覆盖率，但未公开源代码 [51]。与语法生成技术不同，FUZZNG通过重塑内核的输入空间，使其适于模糊测试，而不需要种子跟踪，并且不依赖于广泛的静态/动态分析阶段。

其他的学术研究侧重于改进Syzkaller的性能，而不是直接生成语法。Moonshine依赖于来自实际程序的系统调用种子跟踪，以改进Syzkaller的描述 [38]。Healer应用关系学习来改进Syzkaller的系统调用序列突变算法。SyzVegas利用机器学习技术来提高Syzkaller的覆盖率 [57]。Agamotto利用动态虚拟机快照来跳过在Syzkaller输入中常见的系统调用执行，从而提高模糊测试的吞吐量。HFL通过符号执行扩展了Syzkaller [27]。与这些方法不同，FUZZNG不依赖于手动或“学习”得到的系统调用行为描述。相反，FUZZNG将来自旧的随机参数模糊器的技术与新的覆盖引导技术相结合，并重塑系统调用的输入空间，从而创建了一个与基于描述的方法相比具有竞争性覆盖率的模糊测试系统。

VIII. Conclusion

FUZZNG是第一个能够在没有手动编写的系统调用描述或先前对源代码/种子程序进行分析的情况下产生复杂系统调用交互的模糊器。FUZZNG依靠操作系统内核的基本属性，以便“重塑”系统调用接口，消除了指针和文件描述符参数引起的模糊测试障碍。在其核心中，FUZZNG简单地将来自通用模糊测试引擎（如libFuzzer）的二进制输入解释为系统调用序列。在mod-NG中实现的钩子允许FUZZNG透明地在内核访问它们之前实时填充文件描述符和复杂的数据结构。我们的FUZZNG原型的评估显示，它实现了Syzkaller覆盖率的102.5%，而每个组件配置代码只有Syzkaller的1.7%。此外，由于FUZZNG不依赖于任何特定于组件的测试架构，这些架构可能导致无法访问的错误，因此FUZZNG发现了在Syzkaller覆盖的函数中的错误。此外，尽管我们的评估重点放在了Linux内核的经过高覆盖率模糊测试多年的组件上，但我们发现了9个以前未知的漏洞，并将负责进行适当的披露。我们将开源所有FUZZNG代码，并与上游工作合作，将FUZZNG集成到上游，以继续为Linux内核社区带来益处。

目录