- 原文链接：Kernel Fuzzing with syzkaller
- 作者：MARK JOHNSTON
如果你曾经不幸地遇到过 FreeBSD 内核崩溃，你完全有理由问一下那些不太谨慎的内核程序员是怎么测试他们的代码的。内核是整个系统的支柱，对它的任何修改当然应该在用户能够启动最新版本之前经过精心测试。然而，为了辩护，内核程序员们在一个恶劣且不友好的环境中工作。FreeBSD 内核是用 C 语言编写的，这是一种以其微妙的陷阱和缺乏便利性而臭名昭著的编程语言。内核还需要应对多个敌人：首先，它执行并为各种软件提供服务，其中一些可能具有恶意目的；其次，它与计算机的硬件以及所有相关的缺陷、复杂的设计和明显的 bug 进行交互。许多内核开发者曾在无数个不眠之夜调试内存损坏，最终发现问题源于存在 bug 的设备固件，它在某些方式触发时会覆盖系统内存。最后，像任何现代操作系统内核一样，FreeBSD 内核会利用计算机上所有的 CPU，而内核开发者必须应对为多核系统编写高效、可扩展且正确的软件的内在复杂性。简而言之，这是个棘手的问题。
FreeBSD 的开发者在发布稳定、经过充分测试的版本上投入了大量的精力。值得花些时间思考一下，如何测试：例如，现有系统调用的更改或新的系统调用。系统调用在某种意义上是内核的前端：它们提供了所有程序使用的底层抽象，单个系统调用的调用可能会导致内核代表调用者执行成千上万行代码。添加新系统调用的开发者肯定会编写一些测试程序，以验证其是否按照规范运行，但通常无法对单个系统调用的所有可能输入进行详尽的测试。此外，测试程序无法证明 bug 的不存在；即使系统调用产生了正确的结果，可能仍然会存在一个 bug，它以一种在事后很长一段时间内无法检测到的方式破坏了内核内存。系统调用之间还可能相互作用：多线程程序通常会同时执行多个系统调用，每个系统调用都会更新某些内核状态，因此，我们假设的内核开发者必须仔细考虑这些调用的同步问题，以及现有数百个系统调用如何与目标系统调用相互作用。
这类问题并非特定于内核编程，我们拥有许多概念性和技术性的工具，能够帮助我们应对编写无 bug 内核代码的巨大复杂性，并自信地交付稳定的 FreeBSD 版本。在过去几年里，一种名为 syzkaller 的新工具，在发现所有主要操作系统（包括 FreeBSD）中的严重 bug 方面取得了极大的成功。
一种重要的软件测试方法是模糊测试（fuzzing）。粗略来说，模糊测试是一种程序化地为待测软件生成输入，将这些输入提供给软件，并监控是否有意外结果和副作用的技术。这是发现处理输入验证代码中的 bug 的有效技术，已成为一种不可或缺的软件测试工具。例如，你的 PDF 阅读器（你大概用它来打开在互联网上找到的文件）就应该经过了模糊测试，PDF 规范相当复杂，解析该规范的代码也会相应复杂，因此使得 PDF 成为恶意软件作者的一个有吸引力的攻击向量。事实上，模糊测试通常被安全研究人员和恶意软件作者用来发现安全漏洞。
模糊测试是用于测试软件的众多技术之一。它的一个显著局限性是通常无法验证软件是否按预期行为运行，只能验证软件是否未按某些标准发生错误。例如，一个语言解析器的模糊测试工具会尝试寻找会导致解析器崩溃的输入，但对于某个给定输入未发生崩溃，并不意味着该输入根据解析器的规范正确处理。模糊测试工具擅长发现其他软件测试方法忽略的边界情况和很少执行的代码路径，而这些路径很可能包含 bug。为了最大化效果，待测软件应使用断言和其他形式的运行时检查，以尽早发现无效状态。
模糊测试工具的复杂程度各不相同。一个简单的模糊测试工具可能会生成纯粹随机的数据，并将其直接输入到待测软件中。虽然这种方法可能会发现一些 bug，但它不太可能找到除基本输入验证 bug 以外的其他问题，而且会消耗大量计算资源。例如，考虑一个简单的编译器模糊测试工具，它仅生成随机的 ASCII 字符串：大多数这样的字符串不是有效的程序，因此会被编译器的解析器迅速拒绝，结果编译器的许多组件，如优化和代码生成逻辑，都不会得到执行。智能模糊测试工具了解输入格式，因此能够生成通过基本验证逻辑的看似有效的输入。例如，一个旨在测试 IPv6 数据包处理器的模糊测试工具会确保输入至少以有效 IPv6 数据包头部的 4 位版本号开始。它可以通过使用有效的 IPv6 数据包语料库作为起点，或者具有内置的 IPv6 数据包头部布局知识，或者可能是两者的组合来实现这一点。
第二个有效的优化涉及向模糊测试工具提供反馈。一个简单的模糊测试工具会在循环中生成输入，将其提供给待测软件，然后等待程序崩溃或正常终止。它没有通用的方式来判断给定输入是否有助于提高软件的测试覆盖率，因此无法专注于"有趣的"输入。考虑一个在两个阶段执行输入验证的模糊测试目标：
阶段 1 可能仅仅验证输入的各个部分是否具有正确的长度，而阶段 2 则验证各个部分是否包含有效的值。如果大多数输入在阶段 1 验证时失败，那么阶段 2 的验证将很大程度上未被测试。然而，如果模糊测试工具能够动态地学习哪些输入通过了阶段 1 的验证，它可以通过优先考虑已知通过阶段 1 验证的输入来提高阶段 2 验证的覆盖率。
模糊测试工具有多种方式来获取反馈。例如，它可以衡量处理给定输入所花费的时间，并使用一个启发式方法来丢弃那些处理速度非常快的输入，假设这些输入正在失败基本的有效性测试。另一种技术是由先进的模糊测试框架（如 libFuzzer、AFL 和 syzkaller）使用的，它通过测量代码覆盖率来提供反馈。通过利用软件插桩工具，覆盖引导的模糊测试工具可以“追踪”处理给定输入时执行的代码路径，并利用这些信息尝试生成能揭示先前未执行的代码的输入。模糊测试工具使用此技术非常高效地实现高水平的测试覆盖率，实际上，上述模糊测试工具已经被用来在各种软件项目中发现成千上万的严重漏洞，甚至是在那些被认为是成熟和经过充分测试的软件中。
操作系统内核处理来自各种不受信任源的输入：无特权进程会调用系统调用，并可能试图控制计算机；连接到互联网的系统处理来自不受信任源的网络数据包；内核可能会被请求挂载一个包含无效内容的文件系统；计算机可能支持可插拔的外部设备，这些设备可以直接与内核通信。简而言之，有用的内核提供了巨大的攻击面，多年来的高调内核安全漏洞表明，流行操作系统之间还有很大的改进空间。syzkaller 旨在改善这种状况。
syzkaller 是 Dmitry Vyukov 开发的一个开源覆盖引导内核模糊测试工具。它最初针对 Linux，但后来扩展支持了近十个其他操作系统。syzkaller 有时被称为系统调用模糊测试工具，但它足够灵活，可以针对其他操作系统接口进行测试；例如，它曾用于对 Linux 的 USB 堆栈进行模糊测试，并且仅在 USB 子系统中就发现了数十个漏洞。细节很复杂，但其基本思想很简单：生成一个程序，调用一个或多个系统调用（或向网络注入数据包等），运行它，并检查系统是否诊断出了错误（例如，通过崩溃）。如果没有，收集内核代码覆盖率信息，并决定是继续迭代之前的测试程序，还是重新开始。如果有错误发生，则收集崩溃信息，并尝试发现一个最小的测试用例来触发崩溃。
syzkaller 主要是用 Go 编写的，由十几个松耦合的程序组成，这些程序的前缀都是 syz-，它们共同提供一个自包含的系统，完成以下所有任务：
- 启动并运行一组操作系统实例，通常在虚拟机中。
- 监控这些虚拟机的崩溃或其他诊断报告，通常通过监控控制台输出。
- 生成在目标操作系统下运行的程序，使用覆盖信息来驱动下一步尝试的决策，并运行它们。
- 维护一个观察到的崩溃和诊断报告的数据库，以尝试分类发现的不同漏洞。
- 提供一个网页仪表盘，显示统计数据、代码覆盖率信息，以及观察到的崩溃及其重现方法（如果有的话）。
- 定期更新自身和被测操作系统，而无需人工干预。
- 尝试将新的崩溃问题细分到引入该漏洞的提交。
该系统的高层组件在 FreeBSD 上运行的示意图如下所示：
得益于 Google，syzkaller 开发者提供了多个公共的 syzkaller 实例，这些实例以持续集成模式运行，在这种模式下，syzkaller 定期更新自身和目标操作系统。这些"syzbot"实例会在目标的最新构建中找到漏洞，因此回归问题会迅速且完全自动地报告出来。FreeBSD 实例发现了大量的漏洞和重现方法，帮助开发者快速诊断和修复漏洞，并提供更高质量的发布版本。
syzkaller 并不是第一款内核模糊测试工具，但无疑是最突出的。1990 年代初期的新闻组帖子描述了那些通过随机系统调用轰炸 UNIX 内核的程序，取得了显著效果。Peter Holm 为 FreeBSD 编写的 stress2 测试套件对某些系统调用进行了有针对性的模糊测试（其中包括许多其他功能）。然而，syzkaller 引入了一个关键创新，即利用代码覆盖率来驱动测试用例生成。这一创新利用了 kcov(4) 内核子系统，该子系统最初由 Dmitry Vyukov 为 Linux 编写，后来被各自的开发者移植到其他操作系统。虽然 syzkaller 严格来说不需要代码覆盖信息，但有了来自内核的额外反馈，它的效果会更好。
在 FreeBSD 中，kcov(4) 是 LLVM 的 SanitizerCoverage 的一个包装器。Sanitizers 是编译器特性，通过注入一些代码，使编译结果能够进行某些类型的自省。例如，LLVM 的 AddressSanitizer 会在生成的机器代码中的每一次内存访问前插入特殊的函数调用；这些调用可用于判断内存访问是否无效，例如是否存在"使用后释放"情况。这为类似 Valgrind 的强大错误检测设施提供了支持，但使用的是不同的机制：Valgrind 通过在软件虚拟机中运行未修改的目标程序来拦截内存访问并进行验证，而 Sanitizers 是由编译器本身实现的，需要特定的编译标志。Sanitizers 和 Valgrind 都会引入显著的性能开销，通常只在测试场景中使用。Sanitizers 具有额外的好处，即它们有时可以用于验证内核，而 Valgrind 则无法做到这一点。
SanitizerCoverage 会根据生成代码的控制流插入函数调用。大多数 CPU 指令不会修改控制流：一旦指令完成，CPU 会从 RAM 中获取并执行后续指令。控制流指令会导致 CPU 跳转到另一个地址并开始在那里执行。这就是编程语言中的基本结构，如 if 语句、循环和 goto 背后的实现方式。一个编译后的程序可以被分解为一组"基本块"，其中基本块是一系列不包含控制流指令的指令。每个基本块的结束后都会跟随一个控制流指令。因此，如果目标是弄清楚针对给定输入执行了哪些代码，追踪执行的基本块就足够了。
SanitizerCoverage 大致来说，会在每个基本块之间插入函数调用，就像在 FreeBSD 内核函数 vm_page_remove() 的这段机器代码中所示：
<+0>: push %rbp
<+1>: mov %rsp,%rbp
<+4>: push %r15
<+6>: push %r14
<+8>: push %rbx
<+9>: push %rax
<+10>: mov %rdi,%rbx
<+13>: callq 0xffffffff81167dc0 <__sanitizer_cov_trace_pc>
<+18>: mov %rbx,%rdi
<+21>: callq 0xffffffff815b7c50 <vm_page_remove_xbusy>
<+26>: mov %eax,%r14d
<+29>: mov $0x1,%ecx
<+34>: xor %esi,%esi
<+36>: mov $0x2,%eax
<+41>: lock cmpxchg %ecx,0x54(%rbx)
<+46>: setne %r15b
<+50>: sete %sil
<+54>: xor %edi,%edi
<+56>: callq 0xffffffff81167ea0 <__sanitizer_cov_trace_const_cmp1>
<+61>: test %r15b,%r15b
<+64>: jne 0xffffffff815b78f9 <vm_page_remove+73>
<+66>: callq 0xffffffff81167dc0 <__sanitizer_cov_trace_pc>
<+71>: jmp 0xffffffff815b790d <vm_page_remove+93>
<+73>: callq 0xffffffff81167dc0 <__sanitizer_cov_trace_pc>
<+78>: movl $0x1,0x54(%rbx)
<+85>: mov %rbx,%rdi
<+88>: callq 0xffffffff81107950 <wakeup>
<+93>: mov %r14d,%eax
<+96>: add $0x8,%rsp
<+100>: pop %rbx
<+101>: pop %r14
<+103>: pop %r15
<+105>: pop %rbp
<+106>: retq这里的 __sanitizer_cov_trace_* 函数调用是由 SanitizerCoverage 插入的，可以由内核实现。kcov(4) 通过实现这些函数来工作。
在典型使用中，用户程序分配一个缓冲区来存储覆盖信息，打开 /dev/kcov 并使用 ioctl(2) 将缓冲区映射到内核中并启用当前线程的追踪。当线程随后进入内核，可能是执行系统调用时，覆盖追踪钩子会将每个基本块的地址记录到缓冲区中。当线程禁用追踪时，再次使用 ioctl(2) 调用，它可以利用缓冲区中提供的信息。例如，记录的地址可以通过管道传输到 addr2line(1) 程序，以查找追踪的 C 代码所在的文件和行号。kcov(4) 手册页包含了该 ioctl(2) 接口的详细信息以及一些示例代码。
之前我们提到，fuzzers 在拥有一些关于软件输入格式的知识时，效果会更好，而不是将其视为黑盒。尽管理论上，syzkaller 可以在没有任何关于系统调用的知识的情况下调用系统调用，仅通过使用覆盖信息来尝试"学习"哪些参数值导致更多的代码执行，但这既低效又可能适得其反。考虑一下如果一个 fuzzer 调用 kill(-1, SIGKILL) 会发生什么：内核会按照请求立即终止 fuzzer 进程。
不幸的是，系统调用接口无法通过编程方式发现。换句话说，通常没有办法请求内核描述它实现的系统调用集。即使是 C 函数原型，也忽略了许多重要的细节。以 read(2) 为例：
read(int fd, void *buf, size_t nbytes);首先，fd 在这里是一个整数，但实际上它必须是一个有效的文件描述符。fd 有 4,294,967,295 个可能的值，而其中绝大多数都是无效的。其次，不清楚内核应该如何处理 buf：是应该从那个地址读取数据，还是写入数据，或者两者都做，还是都不做？第三，nbytes 应该表示 buf 缓冲区的大小，但原型中并没有表明这两个参数是相关的；C 语言本身没有足够的表达能力来做到这一点。如果你熟悉 ioctl(2)，想一想它是如何让一个糟糕的情况变得更加糟糕的。
为了解决这些问题，syzkaller 引入了 syzlang：一种用于建模内核编程接口的语言。它足够灵活，可以定义与 C 类型二进制兼容的数据布局，并且表达能力足以描述互相关联的 C 参数，等等。在 syzlang 中，read(2) 的原型变为：
read(fd fd, buf buffer[out], count len[buf])与 C 不同（但像 Go 一样），参数名在前，后面是类型。我们立刻可以看到，这个定义比 C 原型提供了更多的信息：有一个 fd 类型，用来区分文件描述符和普通整数；buf 是指向调用者地址空间中的缓冲区的指针，[out] 注解表示它是一个"输出参数"，即内核应该将数据写入该缓冲区；count 是 buf 缓冲区的字节长度。
使用专门的类型来表示文件描述符和其他内核资源，对于生成做"有趣"事情的程序是非常重要的，因为许多系统调用以先前系统调用的结果作为输入。例如，要从文件中读取数据，一个程序可能会执行以下系统调用序列：
const size_t len = 4096;
void *buf = mmap(NULL, len, PROT_READ | PROT_WRITE, MAP_ANON, -1, 0);
int fd = open("/tmp/foo", O_RDWR);
read(fd, buf, len);
close(fd);
munmap(buf, len);注意，mmap(2) 和 open(2) 调用的结果作为输入传递给后续的调用。在没有先前的 mmap(2) 和 open(2) 调用的情况下，对 munmap(2) 和 close(2) 进行 fuzzing 并没有太大意义，因此 syzlang 模型定义了相应的资源，syzkaller 使用这些关系创建系统调用链，以引导其选择。
mmap(2) 的使用还说明了需要为"标志"参数（如第三和第四个参数）定义有效值的集合。syzlang 为此提供了内置的 flags 类型：
mmap(addr vma, len len[addr], prot flags[mma_prot],
flags flags[mmap_flags], fd fd, offset fileoff)
mmap_prot = PROT_EXEC, PROT_READ, PROT_WRITE
mmap_flags = MAP_SHARED, MAP_PRIVATE, MAP_ANON, ...在创建标志参数的参数时，fuzzer 将选择零个或多个标志值。
syzlang 还可以使用子类型化来更准确地建模系统调用接口。网络连接和打开的文件在系统调用接口中都通过文件描述符表示，但许多系统调用只接受某些类型的文件描述符。例如，sendfile(2) 的一个参数是对应网络连接的文件描述符，用于发送文件的数据。这类描述符是通过 socket(2) 或 socketpair(2) 创建的。将常规文件的描述符传递给它会失败，因此为了节省 fuzzer 的时间，我们可以定义一个新的套接字类型。首先，我们有文件描述符 (fd) 的定义：
resource fd[int32]: 0xffffffffffffffff, AT_FDCWD这将 fd 从内置的整数类型 int32 派生，并定义了几个特殊值：-1，表示参数类型为 fd 的系统调用参数是可选的（如 mmap(2)），以及 AT_FDCWD，由 openat(2) 和类似的系统调用使用。接下来，我们可以为套接字定义一个派生的资源类型：
resource sock[fd]
socket(...) sock
sendfile(fd fd, s sock, ...)对于那些参数布局依赖于另一个参数值的系统调用，采用类似的技巧。ioctl(2) 是这个例子的典型，但 fcntl(2)、setsockopt(2) 和 bind(2) 的行为也类似。例如，pf(4) 定义了大量的 ioctl 命令，但每个命令都有自己的参数类型。我们可以在 syzlang 中精确描述它们：
resource fd_pf[fd]
openat$pf(fd const[AT_FDCWD], file ptr[in, string["/dev/pf"]], ...) fd_pf
ioctl$DIOCRADDTABLES(fd fd_pf, cmd const[DIOCRADDTABLES], arg ptr[in, pfioc_table])在这里，我们定义了一个新的 fd 类型，它对应于 /dev/pf 的文件描述符。然后，特殊的 openat(2) 和 ioctl(2) 描述了 fuzzer 如何打开 pf(4) 设备并发出 DIOCRADDTABLES ioctl，这是 pfctl(8) 用于定义地址表的命令。
syzlang 定义在构建时编译成 syzkaller 的 fuzzer 使用的表格。syzkaller 维护着它自己的系统调用及其参数的内部表示，并且它对程序的表示仅仅是一个调用和参数的列表。所有的 fuzzing 都是通过这些表示来执行的；当找到一个内核 bug 的重现程序时，它最终会被翻译成一个独立的 C 程序。这可以通过手动使用 syz-prog2c 来完成，但通常会自动处理。
由于大多数情况下 syzkaller 还在赶超，因此新系统调用的定义经常被添加：现有的内核接口非常庞大，且用 syzlang 定义这些接口需要时间和精力。特别是，许多 FreeBSD 的组件尚未被 syzlang 描述，因此 syzbot 不会对其进行测试。为 FreeBSD 添加 syzlang 定义是开始为 syzkaller 项目做贡献的一个好方法，并帮助确保 FreeBSD 获得尽可能多的测试覆盖。
到目前为止，我们已经了解了 syzkaller 如何解决所有 fuzzer 面临的通用技术问题：从目标软件获取反馈（通过 kcov(4)）以及描述内核接口（使用 syzlang）。现在我们可以更深入地了解一些需要的机制，以便对操作系统内核进行 fuzzing。
fuzzer 的目标是"运行"被测试的代码，因此它需要一个环境来执行代码并提供输入。对内核进行 fuzzing 还带来了一些额外的挑战：fuzzer 需要在与被测试内核相同的系统上运行，因此如果它达到了目标并触发了内核 panic，所有 fuzzer 的状态都会丢失。syzkaller 的解决方案是将目标内核运行在一组虚拟机中，这些虚拟机可以在不丢失任何重要数据的情况下被安全地清除。这些虚拟机可以在与 syzkaller 相同的主机上运行，或者在 Google Compute Engine 等云环境中运行。
syz-manager 是 syzkaller 的主要前端程序。它以配置文件作为输入，并根据配置启动多个虚拟机实例。它会自动安装并启动每个虚拟机实例中的 fuzzer 程序，并通过 SSH 的 RPC 接口与它们通信。syz-manager 还监控虚拟机的控制台，以检测崩溃。当发生崩溃时，虚拟机会自动重新创建。即使没有崩溃，虚拟机也会定期重新启动；其中一个原因是启用"语料库轮换"。
syz-manager 还维护着实例的崩溃数据库。当发现崩溃时，syz-manager 会向崩溃数据库添加一条记录。崩溃通过内核打印的 panic 消息来识别，当发现新的崩溃时，syz-manager 会将一部分虚拟机专门用来尝试重现崩溃。执行导致崩溃的程序会被重新播放，如果崩溃可以重现，syzkaller 还会尝试找到崩溃的最小重现程序，并将其添加到崩溃数据库中。最后，syzkaller 尝试将崩溃的程序转换为独立的 C 程序，使开发人员能够在不需要 syzkaller 安装的情况下调试崩溃。
设置 syzkaller 大部分工作涉及创建一个包含目标操作系统的虚拟机镜像。虚拟机的内核应该启用 kcov(4)，并且必须安装 root 用户的 SSH 密钥。虚拟机镜像作为模板使用；当 syz-manager 启动时，它会在启动虚拟机之前创建该镜像的快照，并且每个虚拟机都使用该模板的本地副本。当虚拟机重新启动时，它将获得一个新的模板镜像副本，因此 fuzzer 所做的任何损坏都会被丢弃。
syz-manager 支持多种不同的虚拟机监控器和云 API。在 FreeBSD 上，可以使用 bhyve 作为后端虚拟机监控器。为了创建虚拟机镜像模板，syz-manager 使用 ZFS 克隆，因为 bhyve 不支持创建磁盘镜像快照。在启动 syz-manager 时，它还会启动一个 Web 服务器，提供包含统计信息和代码覆盖信息、去重后的崩溃报告以及崩溃重现程序的仪表盘。一个示例的 syz-manager 配置如下所示：
{
"target": "freebsd/amd64",
"http": "0.0.0.0:8080",
"workdir": "/data/syzkaller",
"image": "/data/syzkaller/vm.raw",
"syzkaller": "/home/markj/go/src/github.com/google/syzkaller",
"procs": 4,
"type": "bhyve",
"ssh_user": "root",
"sshkey": "/data/syzkaller/id_rsa",
"kernel_obj": "/usr/obj/usr/home/markj/src/freebsd/amd64.amd64/sys/SYZKALLER",
"kernel_src": "/",
"vm": {
"bridge": "bridge0",
"count": 32,
"cpu": 2,
"hostip": "169.254.0.1",
"dataset": "data/syzkaller"
}
}这个配置指定了 32 个虚拟机实例；通常情况下，更多的虚拟机更好，因为每个虚拟机都会与其他虚拟机并行运行测试程序。cpu 参数定义了每个虚拟机分配的虚拟 CPU 数量，而 procs 参数定义了每个虚拟机中将运行的 fuzzer 进程数量。拥有多个虚拟 CPU 和 fuzzer 进程可以提高发现某些类型 bug 的几率，但过度分配主机资源可能会降低 fuzzing 的效果，因为这会使得重现 bug 变得困难。为每个主机 CPU 配置一个或两个虚拟 CPU 是合理的，但如果配置超过这个数量，可能就太多了。
有关如何构建和配置您自己的 syzkaller 设置的详细信息，请参见 FreeBSD/syzkaller 文档。配置文件编写完成后，可以通过以下命令启动 syzkaller：
# syz-manager -config /path/to/config在使用 bhyve 时，syzkaller 需要以 root 用户身份运行才能创建虚拟机。通过一些努力，syzkaller 也可以在 jail 中运行；目前有一些正在进行的工作，旨在简化这一过程。
如果您希望运行您自己的私有 syzkaller 实例，请做好耐心等待的准备——现在很多低阶问题已经解决，syzkaller 可能需要几天时间才能找到一个新的内核 bug。
现在我们已经了解了 syzkaller 用于 fuzzing 操作系统内核的主要机制，接下来我们可以开始了解 syzkaller 的核心部分。
除了崩溃数据库，syzkaller 的主要持久状态部分是 corpus：一组代表性的程序，其执行会覆盖内核代码。corpus 最初为空，实际上是 fuzzer 的种子：通过从 corpus 中选择一个程序，稍微改变它并检查是否有以前未覆盖的内核代码被新的程序覆盖，就可以生成一个新的测试程序。如果是这样，该程序可能会被添加到 corpus 中，随后作为其他程序的起始点。算法上，fuzzer 只做一件事，那就是尝试增大 corpus 的大小。为了使这一过程对 syzkaller 的真正目的——发现 bug——更有效，应用了许多启发式方法，但核心思想非常简单。
多种程序变异类型是可能的。fuzzer 可能会：
- 将多个程序拼接在一起
- 插入一个新的系统调用
- 删除一个现有的系统调用
- 修改程序中某个调用的参数
如果 corpus 为空，fuzzer 会通过生成一个随机的系统调用列表，并为其随机选择参数来创建一个新的程序。即使 corpus 非空，这一过程也会定期进行。
在 syzkaller 管理的每个虚拟机内，运行着一对程序，syz-fuzzer 和 syz-executor，它们通过共享内存接口进行通信。顾名思义，syz-fuzzer 生成测试程序，syz-executor 则实际执行它们。syz-fuzzer 和 syz-manager 使用简单的 RPC 协议进行协调；由于 syz-fuzzer 生成的程序可能会导致虚拟机崩溃，它依赖 syz-manager 来存储 corpus。
syz-fuzzer 由 syz-manager 通过 SSH 启动。当它开始时，它会与 syz-manager 建立 RPC 连接，并创建多个工作队列，每个队列由一个线程（实际上是 goroutine）管理。每个工作线程会启动一个 syz-executor 实例，并立即开始 fuzzing，形成如下图所示的结构：
工作线程执行大部分将程序添加到 corpus 中的工作：它们生成新的程序并变异现有的程序。它们还处理特殊类型的工作：
- 分类处理：当一个程序似乎生成了新的覆盖时，它会被放入分类队列进行进一步细化。分类步骤尝试确定程序的行为是否一致（即重新运行时生成相同的覆盖信息），如果是，它会尽量在保持覆盖的同时最小化程序的大小。
- 压缩处理：当一个程序经过分类处理，并且看起来值得被添加到 corpus 中时，工作线程会花额外时间对其进行变异，以寻找新的覆盖。
- 候选程序处理：在某些情况下，syz-manager 可能会向 fuzzer 发送候选程序。工作线程执行这些程序，可能会创建分类或压缩处理工作。
在稳定运行时，syz-fuzzer 使用两个 RPC 来与管理程序通信：Poll 和 NewInput。
Poll 会定期调用，用于更新 fuzzer 的 corpus 快照和全局覆盖信息，并收集待 fuzz 的候选程序。它还用于在 syzkaller 启动时重新处理现有的 corpus；典型的 syzkaller 安装会定期更新自身和目标内核，并随后需要重新启动。保存的 corpus 会立即分发给 fuzzer 进行执行和分类处理，因为更新后的内核可能会与之前评估时处理现有 corpus 项目的方式不同。
NewInput 用于将分类过的程序发送回 syz-manager，作为全球 corpus 的潜在候选程序。在某些情况下，syz-manager 会拒绝新的输入，例如为了避免过度膨胀 corpus 的大小，或者如果另一个 fuzzer 已经发现了类似的程序。如果被接受，新的 corpus 程序最终会通过 Poll 被其他 fuzzer 实例看到。
不幸的是，代码覆盖率并不是一个理想的度量标准：程序的 100% 代码覆盖并不排除可检测 bug 的存在，尤其是在现代操作系统内核等多线程代码中。优化一个不完美的度量标准往往会导致次优的结果——我们（希望！）并不会根据程序员编写的代码行数来评估他们。在 syzkaller 的情况下，如果某个测试程序没有增加 corpus 的代码覆盖，它可能会被丢弃。为了尝试缓解这个问题，syzkaller 执行了 corpus “轮换”：一些系统调用和 corpus 程序会对单个 fuzzer 隐藏，以迫使它们找到具有等效覆盖但具有新特征的程序。这可能导致重复工作，但有助于确保系统不会因为找到局部最大值而“卡住”。
为了全面了解 syzkaller，我们需要看看 syz-executor。syzkaller 使用内部表示的系统调用程序进行模糊测试，但当然需要实际运行这些程序。syz-executor 是 syzkaller 中执行此任务的组件；与 syzkaller 的其他部分不同，它是用 C++ 编写的。
执行器由 syz-fuzzer 工作线程启动，并使用简单的共享内存接口与工作线程进行通信。它首先创建一个线程池来实际执行系统调用，然后打开 /dev/kcov 并使用 ioctl(2) 启用代码覆盖信息的收集，并将其返回给工作线程。此时，可能会发生相当多的额外初始化，具体取决于 syzkaller 的配置。例如，执行器可能会进入一个软件沙箱，试图限制测试程序的影响：一个向无辜进程发送信号的程序可能会导致虚拟机卡死并触发高昂的超时和重启。它还可能会初始化设备或网络设施，作为目标模糊测试的一部分。
当需要执行系统调用时，syz-executor 会遍历调用列表，并为每个调用分配一个空闲线程，必要时等待线程变为可用。最初，主线程在每个调用被分发后会等待短暂的时间。一旦输入程序执行完成，它会以“冲突模式”再次执行：不再在每个调用分发后等待短暂的时间，而是允许系统调用的成对执行并发，从而帮助触发内核中本应被忽视的竞态条件。
实际的系统调用执行是通过便利的 syscall(2) 系统调用来实现的，这是一个通用的系统调用，接受系统调用编号和可变参数列表作为参数。在内部，内核使用系统调用编号将调用路由到请求的处理程序。系统调用的结果也会被记录下来，用于优先级排序和分类程序：成功的系统调用比失败的系统调用更受青睐。
如果你已经读到这里，请不要停下来！syzkaller 是许多讲座、文章甚至研究论文的主题——请查看 syzkaller 的文档，其中包含一些精心挑选的链接。本文仅触及了 syzkaller 内部工作的皮毛，源代码通常是了解 syzkaller 实际工作原理的权威参考。
模糊测试是一个令人着迷的主题，观看模糊测试器运行时，尤其是在它找到你最喜爱的操作系统中的漏洞时，会让人感到一种特别的兴奋。我们鼓励你尝试一下。
MARK JOHNSTON 是一位承包商和 FreeBSD 源代码提交者，居住在加拿大多伦多。他特别关注内核调试，并寻找新的方法来帮助提高 FreeBSD 的稳定性。在业余时间，他喜欢烹饪、演奏巴赫的《大提琴组曲》，以及通过实验自定义键盘布局来妨碍自己的工作效率。