Abstract

诸如American Fuzzy Lop（AFL）之类的灰盒模糊器是用于查找程序中的错误和潜在漏洞的流行工具。虽然这些模糊器已经能够在许多广泛使用的程序中找到漏洞，但它们效率不高; AFL在典型的模糊测试中执行的数百万输入中，只有极少数发现看不见的行为或触发崩溃。剩下的输入是多余的，表现出已经观察到的行为。在这里，我们提出了一种方法，通过应用机器学习直接模拟程序的行为来提高像AFL这样的模糊器的效率。我们学习了一种前向预测模型，该模型将程序输入映射到执行轨迹，对标准模糊测试期间收集的数千个输入进行训练。该学习模型通过关注模糊输入来指导探索，模糊输入对我们的模型最不确定（通过预测的执行轨迹分布的熵进行测量）。通过专注于执行输入我们学习的模型不确定，并忽略我们的模型所确定的行为的任何输入，我们表明我们可以显着限制浪费的执行。通过测试我们对作为DARPA网络大挑战的一部分发布的一组二进制文件的方法，我们表明我们的方法能够找到一组输入，导致更多的代码覆盖和发现崩溃，而基线模糊测试的执行次数明显减少。

KEYWORDS：program modeling; binary fuzzing; coverage-based fuzzing

relevant information
作者 Siddharth Karamcheti;Gideon Mann;David Rosenberg
单位 Bloomberg CTO Data Science
New York, NY, USA
出处 期刊Acm Sigplan Notices
原文地址 https://arxiv.org/pdf/1811.08973.pdf
源码地址
发表时间 2018年

1. 简介

fuzz-testing或fuzzing的目标是发现一组测试输入，以最大化给定程序中的代码覆盖率，希望这样做可以解决错误，崩溃或其他潜在漏洞。虽然有许多模糊测试工具，但像American Fuzzy Lop （AFL）这样的灰盒突变模糊器是最成功的。这些模糊器的工作原理是维护一系列有趣的程序输入或“父母”，它们覆盖程序的不同部分，并使用一组随机变异函数（例如，flip bits，delete bits，insert random bits 等）迭代地对它们进行变换来生成新的“子”输入。然后将这些子项提供给程序的一个版本，该程序已被轻量级插桩以跟踪给定输入的执行。如果输入执行之前未观察到的程序路径，则会将其添加到队列中。否则，它被丢弃。不幸的是，丢弃输入需要付出代价;每次执行都需要时间，从几纳秒到一秒以上，具体取决于程序。在典型的模糊测试运行中，生成了数十亿输入的数量级，只有少数实际上覆盖了看不见的代码路径，导致数百分钟的不必要的执行时间。在这项工作中，我们提出了一种方法，通过使用机器学习模拟程序行为来减少这些冗余执行。

具体来说，我们认为要成功fuzzing，重要的是能够将程序输入与生成的执行路径相关联。通过使用机器学习来预测来自给定输入的执行路径，我们引入了一种与灰盒模糊测试互补的方法，允许我们在执行之前过滤无用的输入。我们的过滤方法背后的直觉很简单：我们专注于执行生成的输入，我们的学习推理模型表达了低的置信度（如果我们无法推断输入会做什么，那么它很可能会做一些不同于我们之前见过的所做的事情的）。通过专注于建模程序行为，我们表明，我们可以通过较少的程序执行来显着提高程序覆盖率。

我们在AFL之上构建我们的方法，AFL是卓越的灰盒模糊器之一。我们通过对DARPA网络大挑战二进制文件的一系列实验表明，我们的方法显着提高了模糊效率，获得了比许多强基线更高的代码覆盖率，包括最佳性能的AFL版本。

2 相关工作

虽然在程序中有很多种方法可以发现bugs，但我们关注的是两种关键类型：白盒方法[7]，包括符号执行[1,4,6,9,14-16,19]，和灰盒子方法[3,12,13,17,18,22]。这些名称来自所需基础程序的透明度;白盒方法需要很大的透明度（通常可以访问程序源代码，或者将二进制文件提升到中间表示的能力），而灰盒方法需要的很少（通常只需要对程序运行时进行检测，来收集小块信息，例如每当代码进入新的基本块时）。还存在黑盒方法[8,10,11,20]，它们可以非常快速地随机生成输入，并执行程序来发现崩溃。虽然它们可以用于解决浅层漏洞，但它们往往无法深入到程序中。

白盒方法的核心是能够充分利用被测程序的透明度，以明确推断控制流程的性质。像KLEE [4]和SAGE [9]这样的符号执行工具将程序提升到中间表示，其中暴露了整个控制流图。然后，这些方法将输入视为变量，将分支条件视为对这些变量的约束。要输出将传递某个分支的输入（例如，输入if / else语句的if条件），使用SAT或约束求解器。通过明确地求解满足约束的输入，理论上可以找到将到达程序中的任何语句的输入。话虽这么说，这种方法的缺点在于它们的速度和对资源的需求。平均程序可能具有数百到数千个非平凡的分支条件，因此，可能需要延长的时间段来求解相应的方程。这是由几个因素决定的，包括输入的大小，代码中对外部库的依赖，以及人们可以轻松地检测给定程序。

在另一方面，灰盒子方法假设程序的透明度最小。对于许多灰盒方法而言，不是推理整个控制流图，而是在运行时指示程序，仅用于跟踪输入何时触及新的（以前看不见的）基本块，或者基本块之间的新边缘。像American Fuzzy Lop [22]这样的方法，它的许多变体[2,3,12,18]跟踪这些信息来指导一个简单的遗传算法，该遗传算法生成一系列输入并通过程序执行它们。

关键在于速度;产生新的输入以进行测试几乎是瞬时的，唯一真正的限制因素是通过程序执行的速度。在许多情况下，这种执行速度是不可忽视的 - 而且，由于许多生成的输入要么是冗余的，要么是非常不正确的，AFL和相关的方法都是浪的，在输入上花费数千个周期而不会增加新的有意义的信息。我们的工作目标是引入一种新的方法，获得与AFL类似的速度和效率，同时使用机器学习技术获得一些像白盒方法的精确和推理能力。通过这种方法，我们可以限制浪费的周期，同时保留有效和大规模发现错误的能力。

3 方法

建模程序行为是提高模糊效率的关键。虽然有很多方法可以解决这个建模问题，但在这项工作中，我们专注于学习前向预测模型：给定输入，预测通过程序的相应执行路径。如果我们有一个完美的执行模型，我们可以简单地跳过导致我们已经看到的执行路径的输入，从而节省了大量的时间。如下所示，我们的方法基于模型在它为给定输入预测的执行路径中自信度越低，输入越有可能导致我们以前从未见过的执行路径的启发式方法。

这种方法还有一个额外的好处。当我们执行每个输入时，我们预测模型获得的额外训练数据。基于不确定性选择新输入是众所周知的主动学习技术，因此该输入选择方法还用于加速预测模型的改进，从而加强系统找到好的候选者的能力。

在高层次上，我们的方法是重复执行以下步骤：

1）使用AFL生成一些可能的子输入，2）通过我们的模型输入这些输入以预测执行路径上的分布，3）对这些生成的输入进行置信度排序预测，4）执行那些排名中置信度最小的生成输入，以及5）使用执行的输入来重新训练我们的路径预测模型。此过程在图1中以图形方式描述，并在算法1中进行逻辑描述。在本节的其余部分中，我们提供有关上述内循环中每个步骤的其他详细信息：生成候选输入，学习路径预测模型和使用这个模型来排名和执行候选人。

3.1 生成候选输入

要选择一组有希望通过该程序执行的输入，我们首先需要候选者。我们通过应用AFL的变异逻辑来获得这组候选者。具体来说，给定我们的输入队列，我们首先对父输入进行采样，然后我们应用一组变异运算符来获得我们的新候选者。我们重复这个过程K次以获得一整批有希望的候选人。请注意，此过程非常快，因为我们不会通过程序执行任何生成的输入。

3.2 通过路径预测建模程序

我们方法的一个关键组成部分是通过程序输入的预测执行路径来理解程序行为。当模糊测试开始时，我们没有用于训练模型的示例，因此我们预测每个示例在单个（空）路径上的均匀分布，这有效地导致在基于置信度排名时对批次进行随机排名（如同将在第3.3节中讨论。但是，在执行第一批输入之后，从算法1的第一次迭代开始，我们有一组初始的标记示例{x，p}，其中x对应于输入的特征化表示（例如，一个袋词表示一个输入字符串），p表示相应的执行路径。请注意，出于我们的目的，执行路径p表示为唯一标签（即每个观察到的执行路径获得其自己的标签），而不是基本块序列或底层控制流图中的边缘。这是因为程序可以有数百个基本块，而我们注意到在实践中，只观察到少数独特的执行路径（遍历的基本块集）。

利用这些示例{x，p}和唯一观察到的执行路径P的总数，我们然后可以训练概率分类器以预测给定输入x的P路径上的分布。在我们的实验中，我们使用多项Logistic回归建立概率分类器（通过一对二减少到P分离二元逻辑回归模型，以获得效率）。我们使用双字节计数对每个输入字符串的字节进行优化输入 - 也就是说，我们计算每个唯一的双字节序列在输入中出现的次数的直方图，并使用该直方图作为我们的表示。我们选择不使用L1或L2惩罚，并训练所有模型进行收敛。

3.3通过熵估计不确定性

我们的方法的最后一部分是使用我们的模型来决定哪些候选者通过该程序实际执行。为此，我们应用我们的假设，即具有不确定预测的输入更有可能表现出未被观察到的执行路径，而具有相同预测的输入更可能是多余的。

作为不确定性的度量，我们使用预测分布在执行路径上的熵，高熵指的是高不确定性，低熵指的是低不确定性。给定输入x，令Pr（pi | x）为x展示执行路径pi的概率。鉴于此分布，我们将熵计算为：
$$
H (x) =\sum_{i=1}^P
Pr(p_i | x) log(Pr(p_i | x))
$$
使用此公式，我们然后对给定的迭代对批处理中的每个生成的输入进行评分。然后我们按它们的熵（最高 - 最低）对它们进行排名。最后，我们选择要执行的是最高熵分数α的输入。可以在算法1中找到该过程的完整细分。

4 数据集

我们对DARPA Cyber Grand Challenge Binaries的一部分进行了初步实验。此数据集包含200个单独的程序，作为2016年挑战的一部分发布，用于创建用于修补，验证和修补错误的工具。构建AFL和基于符号执行的方法的许多新工具都来自于这次竞赛[5,18]，从那时起，这个数据集就被用来对类似工具进行基准测试。每个程序都提供独特的功能，由人类编写（与各种DARPA程序相关）。更重要的是，每个程序都写有一个或多个人为编写的错误，旨在模仿开发人员在编写实际程序时可能犯的错误。此外，该数据集中的程序范围很复杂。

在我们的工作中，我们利用来自该数据集的24个随机选择的程序的子集（由于时间限制，我们无法在完整的200上运行）。我们使用了为x86 Linux编译的DARPA CGC二进制版本（与最初的DARPA-specificc VM相对），通过以下链接发布：https：//github.com/trailofbits/cb-multios

5 实验设置

我们使用逻辑回归作为我们的预测模型来实现我们的程序建模方法，并通过收集一包双字节（一个每个唯一字节对出现在输入中的次数的直方图）来强化我们的输入字符串。我们将程序建模方法与三个强大的基线进行比较。第一个基线是AFL本身的基线，因为它开箱即用。然而，我们不是使用标准的AFL参数，而是使用“-d”flag或“FidgetyAFL”[12,21]运行AFL，因为它在短的模糊时间周期内比标准AFL表现更好。

我们使用的第二个基线是AFL的批量版本，我们将其称为Batched FidgetyAFL。 Batched FidgetyAFL和FidgetyAFL之间的差异如下：FidgetyAFL在生成并执行每个输入后立即更新其状态（其队列，因此对哪些父输入进行采样以生成下一个子节点）。批量版本将删除此一致状态更新，并将其替换为批量更新，其中多个输入首先一起生成而不进行任何状态更新，然后一次性执行（使用状态更新）。我们选择此基线，因为它可以更好地与我们的程序建模方法进行比较。回想一下，在我们的方法中，我们首先生成一批示例（不执行），然后对批处理中的输入进行排序以选择要执行的分数α。与Batched FidgetyAFL一样，在我们执行所有排名输入之前，我们不会更新AFL队列的状态。

除了FidgetyAFL和Batched FidgetyAFL之外，我们还有第三个基线，Random Batched FidgetyAFL，它探索了生成的输入相对于模糊性能的排名效果。与我们的程序建模方法不同，后者生成大量输入，然后在通过熵对预测进行排名后执行顶部α分数，随机批处理FidgetyAFL随机选取要执行的批处理的分数α。通过这种方式，该基线可以让我们检查我们的熵排序方法是否真正有效。请注意，随机批处理的FidgetyAFL与Batched FidgetyAFL基线明显不同 - 这是因为AFL没有统一对其队列中的输入进行采样 - 相反，它使用启发式调度来对队列输入进行采样，从队列中获取最新的第一个采样元素，然后（在生成许多新输入之后）开始从队列中采样其他元素。通过这种方式，Random Batched FidgetyAFL表现出比Batched FidgetyAFL稍微更随机的行为，因为它反映了各种不同的抽样父母。

我们在24个DARPA CGC二进制文件上运行我们的实验，每个二进制文件总共执行50,000次。为了快速启动学习，并消除模糊运行中的大部分差异，我们通过让FidgetyAFL运行3分钟来启动所有运行。我们在此窗口期间执行的输入上预先训练我们的逻辑回归模型。然后，我们使用生成的AFL状态和创建的输入队列来作为我们的初始序列，并在顶部启动4种不同的策略（FidgetyAFL，Batched FidgetyAFL，Random和Logistic Regression）。对于所有实验，我们使用AFL版本2.52b。

为了衡量所有策略的相对表现，我们使用我们称之为相对覆盖率的指标。让s对应给定的策略，给t定的执行迭代，T执行迭代的最大数量，以及策略s通过执行迭代t发现的唯一代码路径的数量code_paths~t~(s)。然后将单个程序的相对覆盖率rel-cov定义为：
$$
rel_cov_t (s) =\frac
{code_paths_t(s)}
{max_{s^′}[code_paths_T(s′)]}
$$
或者已经找到的代码路径数量之间的比率，以及最终执行迭代T所有策略的最大代码路径数量。我们报告了所有24个程序的平均值和标准误差。此外，为了更好地了解不同策略在一段时间内的表现如何，我们会在每10,000次执行时报告相对覆盖率统计数据。

6 结果与讨论

表1报告了每次执行10,000次时四种策略中每种策略的相对覆盖率统计。此外，图2提供了一个图表，报告了发现的代码路径数量 vs 程序Flash文件系统的执行（来自CGC二进制文件的示例程序）。最后，图3包含一个汇总图，汇总了我们测试集中所有24个二进制文件的相对覆盖率，跨二进制文件的间隔为95％。

从这些结果中，有两个关键结论可供选择。首先要意识到，在所有时间步骤中，程序建模方法是明显的赢家，获得比任何基线策略更高的覆盖率。这似乎表明Logistic回归排名的收益明显高于批量更新程序所带来的损失。因此，未来工作的可能途径是通过阈值操作来增强基于熵排序的Logistic回归，以允许模型以在线方式做出是否执行输入的选择。这样做可以消除对批处理的任何需求，并允许该方法产生与传统AFL相同的好处，并持续进行状态更新。

第二个关键观察是，程序建模方法与其他基线方法之间的性能差距随着执行次数的增加而增加。图2和图3中的曲线图最好地展示了这一点。我们看到，在模糊测试开始时，性能差距很小，几乎可以忽略不计，而随着执行的继续，差距越来越大。从中可以得出两个可能的结论：第一个是相当简单的结论，当程序建模方法识别更多代码路径时，AFL的队列被更新，我们开始对更多最近发现的输入进行采样 - 为什么AFL的原因本身就是成功的。但是，另一种可能的解释是程序模型在更多数据可用时的行为方式。随着更多的执行，给了逻辑回归更多标记的例子。因此，它可以更好地识别输入中的模式，并且在推理时分配的协调分数变得更有意义。未来工作的另一个途径是检查学习模型的性质，以及它们如何随着执行的继续而变化。将更强大的学习算法和更多程序特定的特征放入混合中也是值得的，看看是否有办法加强报告的协调分数。

7 结论

在这项工作中，我们提出了一个系统，用于提高AFL的效率和精度，AFL是首屈一指的灰盒模糊器，利用机器学习技术直接模拟程序行为。具体而言，我们注意到AFL和类似方法的一个主要缺点是浪费在冗余或非信息输入上的程序执行次数。为了解决这个问题，我们提出了一种两阶段方法：1）学习将输入映射到执行路径的前向预测模型，以及2）使用该模型来识别可能有趣的输入。我们使用的直觉是，如果我们能够自信地模拟给定输入在执行时的行为方式，那么就不值得执行。相反，我们应该关注我们的模型表现出低置信度的输入 - 这些输入在执行时可能会触发尚未被观察到的新代码区域。我们的结果表明，我们使用简单的逻辑回归分类法构建的基于排名的方法获得了极强的性能，击败了3个强大的基线，包括AFL本身的标准，开箱即用的实现。此外，我们的结果表明，随着我们继续模糊化，我们的方法变得越来越好，我们的方法和基线之间的性能差距随着时间的推移而不断扩大。这些结果表明，在应用从机器学习和模式识别到模糊测试的技术方面有很大的好处，这是一个非常富有成效的研究途径。