【论文分享】LibAFL: A Framework to Build Modular and Reusable Fuzzers

1. 简介

AFL是软件安全测试领域的一个重要里程碑，使得fuzzing成为了一个主要的研究领域，并带动了大量的研究去提高fuzzing流水线上的各个方面。

许多研究是通过fork AFL的代码来进行实现的。虽然一开始看起来挺合适的，但是要把多种fork合并到一个fuzzer，需要大量的工程开销，阻碍了不同技术客观和公正的评估。严重碎片化的fuzzing的生态阻止了研究者组合多种技术来实现新的原型系统。

2.fuzzing的9个模块

input：程序的输入，或者从外部获取的数据，输入到系统中，影响了系统的行为。这样的数据就是输入。

然而，字节数组并不是输入的理想表示形式。就比如，如果目标程序希望接受一系列的系统调用的话，字节数组就不合适了。另外一种方式是把输入存储为抽象语法树（AST）的形式，这样可以保留语法信息。还有其他的工作是把输入处理为一序列的tokens或者语言的IR。

Corpus：输入的存储以及关联的元数据。不同的存储会影响fuzzer的能力，比如，corpus存在内存中，会使得fuzzer运行很快，但是同时也会很快消耗完内存。而存储在disk的corpus虽然也可以检查fuzzer的状态，但是会引入disk操作的开销。

主流的fuzzer都存在disk，但这个选择影响了并行fuzzing的扩展性，并且需要标准库来实现文件IO的操作。

在libafl的模型中，一个fuzzer至少需要两个单独的corpora，一个用来存储有趣的测试样例，作为fuzzer进化算法的组件。另一个用来存储solutions，也就是满足fuzzer目标的测试样例，例如导致程序崩溃的crash。

Scheduler：调度器是和corpus紧密连接的一个模块。这个模块主要是告诉fuzzer下一个要fuzz的测试样例。最原始的调度器的实现有FIFO（先进先出）或者随机选择。更复杂的调度去可能会使用一些概率算法或者应用其他的调度器到corpus的子集里去。

Stage：stage是一个组件，定义了从corpus操作测试样例的一个行为。通常来说，调度器选择了一个测试样例后，fuzzer会在每个阶段执行给定的输入。Stage是一个很广的实体，通常作为唤起变异器的组件（random，havoc stage in AFL）

另外一个很知名的stage是最小化的过程。他主要是把测试样例的大小弄小，同时不改变测试样例的覆盖率。

Observer：观察器从目标程序的执行中提供信息。比较知名的观察器就是覆盖率映射表。这个映射表包含了执行过的每一条边。这个信息不会被多次运行的时候保持不变，他是程序的动态属性。（AFL的bitmap）

Feedback：反馈是用来区分程序的执行的输出是否有趣。理论上，这个信息用来确定对应的输入是否被加到corpus中。大多数情况下，feedback和observer是深度关联的。但是这两个是不同的概念。事实上，feedback通常处理多个观察器传来的信息来确定执行是否是有趣的。而有趣这个概念是很抽象的，通常可以理解为是否发现了新的东西（比如发现了新的边）。

识别有趣输入的过程在fuzzing中也有第二个重要目标，找到能够满足特定的属性的solution，比如目标程序中一个可观测到的crash。

Mutator：将一个输入或者多个输入变成新的输入。变异器可以组合多个其他的变异器，并且通常与一个特定的输入类型有关。在传统的fuzzer里，变异器包含许多位级别的操作，比如位翻转或者基本块交换。一个变异器也可以依据输入格式来变异。比如通过交换AST树上的一个节点来实现变异。

Generator:从scratch中生成一个新的输入。例如NAUTILUS使用基于语法的生成器创建初始的corpus和子树生成器作为它的语法变异器。

3. 框架结构

3.1 设计理念和顶层设计

LibAFL的目的是构建一种基于可重用组件和可靠、快速和可扩展的先进技术的模块化设计的新时代fuzzer。

libafl的框架基于三个关键原则：

1. Extensibility：允许用户交换第三章介绍的实体的不同实现，而不需要改动其他的部分。这样可以允许不同的技术融合到一起。

2. Portability：大多数的fuzzer是操作系统特定的。要不只能对unix程序，要不是windows。为了避免这个缺点，libafl以一种不依赖系统的方式来设计核心库。而且，为了最大化可移植性，实现了LibAFL的子集，包含了所有的核心组件，而不需要任何标准库的依赖。因此，可以让用户对bare-metal目标（比如嵌入式系统、内核）写fuzzer。

3. Scalability：设计的选择不能和fuzzer的多核运行的特性相矛盾。因为这点，libafl设计了一个基于事件的接口，能够在fuzzer之间相互通信。

libfuzzer虽然能够在不同的操作系统上用，但是不能不需要标准库来进行编译。AFL自身是基于disk进行IO通信，同时用了大量的系统调用，比如fork，导致其扩展到多核上的效果不好。其他扩展性更好的方案，比如HONGGFUZZ依然是基于系统调用来控制目标并且在多个并行的线程中保留一个共享的状态。

为了创建一个fuzzing的框架，能够满足上面的三个目标，围绕三个核心库设计了LibAFL。

• LibAFl Core是主要的库，包含fuzzing的组件和他们相应的组件。这个库的大部分都依赖于Rust core+alloc，因此，可以在没有标准库的情况下运行。

• LibAFL Targets包含了在目标程序里的代码。比如用来追踪覆盖率的运行时的库。

• LibAFL CC提供了函数来写编译器的wrapper，方便用户来进行插桩。

除了这三个核心库，也包含插桩后端提供API来让libafl可以应用到不同的执行引擎，比如QEMU和Frida。

3.2 核心库

libafl的核心架构如下图所示：

4.1 Bypassing Roadblocks

bypassing roadblocks指的是通过绕过很难求解的约束来增加代码覆盖率。比如，多字节比较对于通过随机的遗传变异是很难绕过的。因为解空间很大，盲目地猜测是不切实际的。Libafl提供了几种现有的技术来绕过这些roadblocks。

• value-profile（libfuzzer）：通过最大化两个指令的操作数的匹配的位来求解比较指令

• cmplog（AFL++）：通过找到并替换input-to-state values。对比较指令和将两个指针作为参数的函数进行插桩。并且在运行时记录相关的值到映射表。然后变异器匹配输入的模式，并用比较指令另一个操作数的值替代输入。

• autotokens（AFL++）：从比较指令中提取tokens，从函数中提取立即数，编码到二进制的段里。然后把这些token放在状态的元数据字典里，然后在变异器使用这些tokens。由于这种方法不引入开销，所以将这种方法作为baseline。

最后的实验结果是cmplog（95.94）>value_profile_complog（95.03） > plain（94.65） > value_profile（90.13）。

4.2 Structure-aware Fuzzing

基于遗传算法的变异器对于一些结构化的输入表现不好。针对这个问题，一种解决方法是让fuzzer意识到输入的格式。Libafl也提供了几种现有的技术，来处理结构化的输入。

• NAUTILUS：一种基于语法的覆盖率导向的fuzzer。他的核心思想是在语法树上进行变异。

• GRAMATRON：利用一种grammar-to-automata的转换方法来实现高效的变异器。

• GRIMOIRE：使用那些会增加覆盖率的部分输入作为tokens来构建树形的输入，并且做grammar-like的变异。他原本是对JavaScript语言进行fuzz的，但是libafl的实现是通用的，并且可以用到任何语言。

评估这些方法的指标为未覆盖的bug的数目。因为这类fuzzer的有效性并不依赖于代码覆盖率。

实验结果如下，grimoire的表现效果最好。

4.3 Corpus Scheduling

从语料库中选择哪一个测试样例来用是许多研究的重点。最简单的是随机选择或者FIFO队列。libafl提供了这两种方法，也包括其他的调度器。

• MinimizerScheduler（AFL）：基于执行速度和输入的长度，同时保持最大的覆盖率来选择种子。

• weighted（AFL++）：基于概率进行抽样，概率的分数使用各种指标，包括执行的时间，覆盖率映射表的大小。

• accounting（TORTOISEFUZZ）：使用三种安全影响指标来选择输入，基本块和函数粒度级别的内存操作，loop back edges（回到循环的边）的数目。

实验结果：weighted>minimizer>accounting>rand

并且这几个差别不是很大。尽管有相当多的研究在做这个问题。

4.4 Energy Assignment

能量分配主要是回答一个输入需要变异多少次生成一个测试样例的问题。最原始的方法是使用一个常数值。最常见的简单的方法是根据时间间隔来分配一个随机值。libafl提供了这种方法，名为plain。AFLFast工作里提出了六种不同的算法：exploit，explore，coe，fast，lin和quad。

实验结果：explore>fast>plain>coe

同样，他们的区别很小。

4.5 通用的bit-level Fuzzer

这部分就把前面的四个问题里最好的技术整合到一起，和其他成熟的fuzzer（AFL++，Honggfuzz，libfuzzer）进行评估。

总体上效果要优于现有的fuzzer。

具体的实验结果在该 址可以看到：https://www.fuzzbench.com/reports/experimental/2022-04-11-libafl/index.html

4.6 Differential Fuzzing

NeoDiff，原本是基于python写的，会去比较基于同样的输入比较两个以太坊虚拟机的执行结果。具体来说，它使用了状态哈希的方法。就是将寄存器的值，内存和栈上每个指令的概率抽样进行哈希。它使用的反馈是类型哈希（type hash），操作码的哈希以及每个指令在栈上前两个东西的类型。任何输入产生了新的类型哈希，就会被加入到语料库中。

4.7第三方应用

libafl已经被很多新用户使用了。这些用户之前没有使用这些框架的经验。

1. TLSPUFFIN：结合fuzzing和模型测试，实现了对TLS协议的fuzzer。

2. TARTIFLETTE：基于KVM的快照fuzzer。提供了一种新的执行器，通过系统调用模拟和覆盖率追踪的插桩来将Linux ELF当作是VM进行运行。

3. NANAFZZ：检查竞态条件的漏洞的fuzzer。

5 局限性

没有包含Link Time Optimization pass来构建程序的控制流图，导致不支持大部分的定向模糊测试。

libafl提供了强大的concolic tracing的API，可以用来扩展SymCC和SymQEMU来过滤约束和符 路径通信。目前，libafl使用Z3来生成新的测试样例。然而传统的concolic fuzzer的缺陷，这个框架也不能解决。主要原因是：

1. 求解器时间开销和资源开销都很大。

2. fuzzer和concolic结合的并不好。即使当一个求解器生成了复杂约束的测试样例，也很难让fuzzer去变异生成的测试样例，而不去破坏求解出来表达式的合法性。

最后是关于这篇论文的一些链接：

• libafl的github仓库：https://github.com/AFLplusplus/LibAFL

• 论文地址：https://www.eurecom.fr/publication/6973/download/sec-publi-6973.pdf