REDQUEEN译文

Abstract

近年来，基于模糊的自动化软件测试经历了复兴。尤其是反馈驱动的模糊化已经因其在有限的输入语料库中有效地执行随机测试的能力而广为人知。尽管取得了很多进展，但两个常见的问题是幻数和（嵌套的）校验和。通常使用诸如污点跟踪和符号执行等昂贵的计算方法来克服这些障碍。不幸的是，此类方法通常需要访问源代码、对环境的相当精确的描述（例如，库调用或底层操作系统的行为）或平台指令集的确切语义。

在本文中，我们引入了一种轻量级但非常有效的替代方案来代替污点跟踪和符号执行，以促进和优化最先进的反馈模糊化，该模糊化可以轻松扩展到大型二进制应用程序和未知环境。我们观察到，在给定程序的执行过程中，部分输入通常直接（即几乎未修改）进入程序状态。可以利用这种输入到状态的对应关系来创建一种鲁棒的方法，以高效的方式克服常见的模糊障碍。我们的原型实现称为REDQUEEN，能够为给定的二进制可执行文件自动解决magic bytes和（嵌套的）校验和测试。此外，我们还表明，我们的技术在不同权限级别（内核空间和用户区域）的各种目标上优于各种最先进的工具，无需特定于平台的代码。REDQUEEN是第一种在所有目标中发现超过100%的LAVA-M中种植的bug的方法。此外，我们还发现了65个新的bug，并在多个程序和OS内核驱动程序中获得了16个CVE。最后，我们的评估表明，REDQUEEN是快速的、广泛适用的，并且比并发方法的性能高出三个数量级。

采用I2S的方式代替污点分析和符号执行解决magic bytes、（nested） checksum

1 Introduction

模糊化已成为测试软件系统质量的关键组件。在过去的几年中，更智能的模糊化工具在学术研究和工业中都获得了巨大的吸引力。最值得注意的是，美国模糊触发器（AFL[44]）对安全形势产生了重大影响。由于其易用性，现在可以方便地更彻底地测试软件，许多研究人员和开发人员都这样做了。在学术方面，DARPA的网络大挑战（CGC）令人信服地证明了模糊化仍然与最先进的bug发现高度相关：所有团队都使用这种技术来发现新的漏洞。继CGC之后，提出了许多新的模糊化方法，这些方法引入了新的思想，以有效和可扩展的方式发现漏洞（例如，[10]，[16]，[19]，[31]，[34]–[38]）。

为了确保在实践中采用模糊化方法，模糊化应该以最少的先验知识来工作。不幸的是，这与通常为提高效率所做的两个假设相冲突：（i）需要从一个良好的种子输入语料库开始，或者（ii）需要一个输入格式生成器。在缺少这两个元素的情况下，模糊器需要学习有趣的输入是什么样子的能力。反馈驱动的模糊化，一个由AFL推广的概念，能够做到这一点：触发新行为的有趣输入被保存以产生更多的测试用例，其他所有东西都被丢弃。

AFL好用就在于最少的先验知识：所以种子语料库或者输入生成器被摒弃

A Common Fuzzing Roadblocks

为了激励我们的方法，我们首先重新审视有效发现新代码的问题，重点是克服常见的模糊障碍。在实践中，模糊化中的两个常见问题是magic numbers和校验和测试。清单1中显示了此类代码的示例。只有当输入的前8个字节是特定的magic头时，才能找到第一个错误。为了达到第二个错误，输入必须包含字符串“RQ”和两个正确的校验和。随机创建满足这些条件的输入的概率可以忽略不计。因此，反馈驱动的模糊器不会产生新的覆盖范围，并且模糊化过程停滞。 ![[Pasted image 20230118093350.png]]

过去，人们非常关注解决这些障碍。提出了不同的方法，这些方法通常使用高级程序分析技术，如污点跟踪和符号执行[12]、[13]、[16]、[22]、[23]、[26]、[36]、[35]、[38]、[40]。值得注意的是，ANGORA[16]和T-FUZZ[34]都属于这一类别。这些方法通常需要对环境（例如，库调用或底层操作系统的行为）和平台指令集的确切语义进行相当精确的描述。因此，很难在使用复杂指令集扩展（即浮点指令）或不常见库和操作系统的目标上使用此方法。因此，这种方法与AFL开创的方法截然相反：在很大程度上，AFL的成功是基于它对项目的行为几乎不做假设的事实。基于这一洞察，我们研究了一种新颖的模糊化方法，该方法擅长增加任意目标上的代码覆盖率，从开源用户程序到开源OS内核。我们证明了这种方法可以优于现有的模糊策略。

举了路障的例子

B. Our Approach: Input-to-State Correspondence

在本文中，我们提出了一种新颖且轻量级的方法，在许多情况下，该方法能够取代两个复杂的分析原语：污点跟踪和符号执行。与上述两种技术相比，我们的方法易于实现，并可扩展到大型、复杂的目标和不同的环境。我们的方法基于一个简单而直观的观察：在许多情况下，输入的部分直接对应于运行时的内存或寄存器。因此，在输入和当前程序状态之间存在强的输入到状态对应关系。这可用于实现有效的模糊化方法。实际上，在使用输入数据之前，大多数程序只对输入应用少量的解码步骤。我们发现，真实世界程序使用的一组编码方案通常很小：通常，这些值直接用于硬条件的上下文中，例如检查特定的header value（magic bytes）。例如，通常将输入字节解释为小端整数，然后直接与校验和或特定magic bytes进行比较。

依据：输入的某些部分和程序状态存在对应关系
程序一般对输入数据做很少处理（大小端，hash或一些编码操作）后就直接使用（如与magic bytes或校验和比较）

我们通过跟踪程序来观察比较指令中使用的值来利用这种观察。通过用随机字节“着色”输入，我们创建了一个非常轻量级的污点跟踪近似值。然后，我们推测我们能够通过改变相应的输入字节来控制这些值。最后，我们使用快速模糊过程来验证我们是否触发了新的和潜在的有趣行为。类似地，我们会迅速丢弃由这种over-approximation引起的误报false positives。该方法允许我们跳过复杂的代码部分，例如API调用或未知指令，否则很难处理污点跟踪或符号执行。因此，即使是通过未知库函数、大型数据相关循环和浮点指令的输入也不会显著降低结果的质量。我们继续使用相同的原理来实现基于修补的解决方案，以处理校验和测试。与类似的方法相比，我们的方法完全避免了符号执行，同时始终保持输入队列具有有效校验和且没有误报false positives。

这段没看懂！！！

反馈驱动的模糊器通常在所有执行中使用相同的工具来测量代码覆盖率和其他反馈信息。例如，VUZZER对生成的每个输入使用其完整的污点跟踪功能。由于大多数模糊化执行（数百万到数十亿）发生在相同的几个输入（数千到数十万）之上，我们建议将分析以不同的方式纳入反馈驱动模糊化：我们将更昂贵的分析过程与模糊化过程分开。在我们的例子中，对于找到的每个新输入，我们只执行一次昂贵的路径特定输入到状态对应的搜索。然后执行所有实际的模糊，而不需要额外的开销。我们发现，这种方法大大降低了与更昂贵的分析相关的成本，并允许剩余的模糊化过程利用在分析阶段获得的知识。

对于队列中input，我们只分析一次

虽然我们的方法可以看作是污点跟踪和符号执行的近似方法，但我们的评估结果与使用更昂贵的“真实”污点跟踪和标记执行的工具相比具有相当的竞争力。为了执行我们的评估，我们实现了一个称为REDQUEEN的方法原型，它可以处理纯二进制目标。我们对GNU binutils套件的经验评估表明，在所有情况下，我们的方法能够覆盖比现有工具多得多的代码。与VUZZER[35]和KLEE[12]相比，测量等覆盖时间可产生5倍至5000倍的加速，与AFLFAST[10]和LAF-INTEL[2]相比，可产生2倍至200倍的加速。此外，我们是第一个发现比LAVA-M数据集（2265）中列出的bug多得多的bug（2600）。总共，我们发现了另外335个未列出的错误，占所有列出错误的114%。我们只遗漏了LAVA-M数据集中列出的2265个漏洞中的两个（>99.9%的错误覆盖率）。

执行效率特别快

此外，我们的技术避免了通常与污点跟踪和符号执行相关的大量实现和性能开销。因此，我们的方法适用于比上述技术更多样化的一组目标，这些技术需要详细的环境模型。事实上，REDQUEEN能够在不需要源代码或平台知识的情况下模糊程序，正如我们通过将REDQUEEN应用于内核和用户空间目标所证明的那样。在我们的评估中，REDQUEEN在2个不同的Linux文件系统驱动程序中发现了10个错误，在16个用户空间程序和软件库中发现了55个错误。此外，针对我们发现的一些更关键的问题，已分配了16个CVE。

能用的目标程序更多

C. Contributions

总之，我们做出了以下贡献：

我们引入了输入到状态对应的概念，作为一种新的原理，以显著加速反馈驱动的模糊化。
我们表明，可以使用输入到状态的对应来代替污点跟踪和符号执行，以解决难以模糊的问题，例如处理magic numbers、动态多字节比较和（嵌套）校验和，而不引入任何误报。由此产生的突变算子比AFL使用的所有其他突变算子更有效（衡量在使用的时间内发现的新路径上）。
我们在一个名为REDQUEEN的工具中构建了方法的原型实现。我们的综合评估结果表明，REDQUEEN在几个指标上优于所有最先进的模糊化工具。

III. INPUT-TO-STATE CORRESPONDENCE

在本节中，我们介绍了一种新的模糊化方法，该方法基于程序具有强大的状态对应输入这一观点。我们观察到，对于非常多的程序，输入值在执行过程中直接用于各种状态。通过观察这些值，我们可以对要替换的偏移量（类似于非常轻量级的污点跟踪）和要使用的值（类似于基于符号执行的方法）进行有根据的猜测。我们可以利用这种关系来处理具有挑战性的模糊化问题，例如魔术字节和（甚至是嵌套的）校验和。我们解释了我们方法的不同构建块，并讨论了它们如何解决我们之前介绍的具有挑战性的模糊问题。

A. Magic Bytes

我们解决的第一个障碍是magic bytes。清单2显示了这类模糊问题的典型示例；它是清单1中介绍的运行示例的摘录。应该注意的是，虽然我们在示例中使用ASCII值以提高可读性，但输入到状态的对应关系也非常适用于二进制格式。

这些构造对于反馈驱动的模糊器来说很难解决，因为它们不太可能猜测到令人满意的输入；在这种情况下是64位输入MAGICHDR。现有方法[16]、[23]、[34]、[35]、[38]、[40]通常使用污点跟踪和符号执行，这两种方法都会产生一定的性能开销。正交方法是用户定义的字典，代表测试程序的专家知识。最后，有一些方法将多字节比较拆分为多个单字节比较。然后，模糊器能够解决单个字节。主要的例子是LAF-INTEL[2]，它在解决多字节比较时非常有效，但需要源级访问来修改程序。另一个工具是STEELIX[31]，它不依赖于对源代码的访问。相反，它使用动态二进制插桩将大型比较拆分为较小的比较。不幸的是，这种方法有很大的性能开销。STEELIX的作者报告称，LAF-INTEL每秒执行的执行次数是它的7倍多。

我们提出了以下基于输入到状态对应关系的轻量级方法，以完全自动化的方式处理magic bytes：我们利用了程序状态的值通常直接对应于部分输入的事实。每次遇到新路径时，我们都会挂起所有比较指令并执行一次跟踪运行。如果我们遇到带有不同参数的比较，我们会提取两个参数并创建一个自定义的突变<pattern → repl>，如下所述。不同步骤如表I所示。

i) Tracing.

当我们开始模糊一个新的输入时（在进入KAFL的确定阶段之前），我们执行一次运行，在该运行中，我们hook所有比较指令并提取参数。这包括编译器发出的一些指令，用于替换普通比较指令或switch-case结构（通过计算跳转表中的偏移量）。此外，我们还hook所有调用指令，因为函数可能实现字符串比较和类似功能。更多详情见第四节。

**Example 1.** 

考虑将“TestSeedInput”作为清单2中代码的输入。比较指令检查输入的前8个字节（解释为无符号64位值）是否等于字符串“MAGICHDR”的64位无符号解释。由于整数通常以小端格式编码，因此比较中使用的最终值的ASCII表示形式为“deeStesT”和“RDHCIGAM”。

ii) Variations.

在运行时，我们不知道在比较之后检查了哪些标志；我们无法区分不同的比较操作，例如“低于”和“等于”。因此，我们对比较值应用一些变化，例如加1和减1。作为这种启发式的一个副作用，我们根据经验发现，这种方法增加了触发一个错误的概率。

**Example 2.**
在这种情况下，我们在“RDHCIGAM”上加上和减去1，得到“RDHCIGAL”和“RDHCIGAN”。

iii) Encodings.

在达到实际比较之前，输入很可能已经以不同的方式进行了处理。为了处理input en-/decoding 的最常见情况并创建更多的突变候选，我们对突变应用各种不同的编码。这些编码的示例是反转零扩展或端序转换。

**Example 3.** 
我们对当前的突变“RDHCIGAM”、“RDHCIGAL”应用小端编码，并获得“MAGICHDR”、“LAGICHDR”和“NAGICHDR。

我们观察到，通常只需要几个原始编码方案。到目前为止，最常见的情况是输入值和状态值之间的一对一映射。具体来说，我们在实验中使用的编码是：

- 零/符号扩展（n）：该值被解释为具有零或符号扩展的小端整数，前导字节被剥离以产生n字节版本的模式（如果适用）。当没有发生大小变化时，这种编码也称为普通编码。
- Reverse：所有的小端编码方案也有一个大端编码方案。
- C-String：该值是一个C字符串，第一个0字节之后的所有内容都被删除。
- Memory（n）：该值被视为类似于memcmp的函数的参数。仅考虑前n∈{4，5，…，32}个字节。
- ASCII: 整数值编码为ASCII数字

在手动评估了我们的模糊器产生的覆盖率之后，我们认为上述一组编码方案覆盖了现实世界应用程序中常见情况的大部分。在一些罕见情况下，这些编码是不够的。编码集也可以被视为用户输入，类似于其他模糊系统中的字典。在这种情况下，用户可以容易地提供自己的、更具体的编码方案。这一步骤可以看作是用于猜测当前位置的符号状态的合成算法的轻量级变体。事实上，与其他推断输入如何影响状态（如符号执行或程序合成）的方法相比，这种方法有一个主要优点；很容易表示复杂的操作，例如将十进制ASCII数转换为整数。这是因为我们只需要对具体值执行编码，而不是用符号值查询SMT解算器。

iv) Application.

最后，也是最重要的一点，我们使用the pattern of a mutation<pattern→ repl>，以识别要用突变 repl 替换的输入部分。与其他方法（如ANGORA或STEELIX）相比，我们一次应用整个pattern。这有两个优点：它适用于原子比较，无需对目标进行进一步修改/hooking，并且大大减少了尝试替换的候选位置的数量。

**Example 4.** 
只有输入“TestSeedInput”的子字符串“TestSeed”与“MAGICHDR”进行比较。因此，我们仅用生成的突变替换这一部分。这产生了新的测试用例“MAGICHDR输入”，以及为解决不等式而引入的变体：“LAGICHDRInput”和“NAGICHDRInput”（以及其他编码方案的可能更多输入）。

v) Colorization.

我们发现，申请替换的候选位置数量有时相当多。例如，最小的有效ext4文件系统映像为64KB，大部分由零字节的长字符串组成。将单个零值与某个常数进行比较将产生超过60000个可能的位置。在我们的评估中，我们发现这些比较经常发生。因此，我们设计了一个有效的过程来增加输入中随机字节的数量。输入中的更多熵减少了可能位置的空间。使用这种input的“colored” copy可以大大减少候选位置的数量，通常是多个数量级。在生成彩色版本之后，我们只在两个输入中发现pattern部分处于相同偏移的情况下应用突变。结果，应用的剩余突变数量大幅减少。在我们的评估中，我们发现这种方法引入的突变数量通常比AFL在同一输入上执行的确定性突变数量少两个数量级。

**Example 5.**

假设我们正在测试运行示例中的输入“ZZZZZZZZ...(24个)”。在突变中，我们会发现<ZZZZZZZZ→ MAGICHDR>。这种突变可以应用于许多（24）不同的位置。因此，我们尝试在不更改执行路径的情况下替换尽可能多的字符。在这种情况下，彩色版本可能是任何随机字节字符串（例如“QYISLKFYDBYYSYWSIBSXAXOKHNRUCYU”）。相应地，在重新运行时，相同的指令将产生突变：<QYISLKFY → MAGICHDR>，仅适用于第一个位置。因此，我们只在位置0产生一个候选。

vi) Strings and Memory.

除了前面提到的整数比较之外，程序经常使用函数来比较两个字符串或字节数组的内容。类似地，这些测试通常对模糊器构成重大挑战。为了克服这种构造，我们还钩住所有函数调用。如果函数至少包含两个指针参数，我们将提取指向的前128个字节，并对待它们类似于整数。然而，我们对内存内容使用了与整数不同的一组编码，最值得注意的是，我们要么假设只比较前n∈{4，5，…，32}个字节（函数类似于memcmp），要么假设所有字节直到第一个null字节（strcmp家族的函数）。

vii) Input Specific Dictionary.

最后，我们将包含许多连续 non-zero或non-0xff字节的值添加到特定字典中。这样找到的字符串将仅被当前input的破坏阶段使用。这允许我们使用传递给函数的值（函数内部工作类似于比较功能，使用哈希表查找等非平凡算法）。在某种程度上，这是一个更强大的版本，它是提取字符串工具的输出并将其用作模糊运行的字典的众所周知的技巧，因为我们包括动态计算的字符串，但不包括与此路径无关的字符串。

B. Checksums

模糊器的另一个常见挑战是有效地模糊越过校验和的内容。清单3描述了这个挑战的一个典型示例，它再次代表了清单1中介绍的运行示例的摘录。

![[Pasted image 20230118163714.png]]

现有的方法，如FLAYER[18]、TAINTSCOPE[40]或T-FUZZ[34]，都依赖于相同的想法：删除硬检查，稍后修复。TAINTSCOPE和T-FUZZ都自动检测关键检查，一旦发现有趣的行为，就使用符号执行来修复检查。

我们建议使用以下基于输入到状态对应关系的过程来替换TAINTSCOPE和T-FUZZ中使用的污点跟踪和符号执行：首先，我们识别看起来类似于校验和检查的比较（例如，一侧是一个input-to-state对应值，另一侧定期更改）。然后，我们用始终求值为true的比较替换检查。一旦这个补丁程序上的模糊过程产生了一条看似有趣的路径，我们就进入了验证模式。在这种模式下，我们使用上一节中描述的技术来纠正所有修补的比较。如果成功了，我们将一如既往；否则，我们得知一个不在我们的控制之下的比较，我们删除了该指令的补丁，以避免将来执行不必要的验证步骤。

基于输入到状态对应的思想，我们能够自动推断要修补的指令。此外，我们可以自动修复输入，而无需人工干预或污点跟踪和符号执行的复杂原语。在反馈模糊化过程中，我们修复了任何新发现的输入（与TAINTSCOPE和T-FUZZ相反）。这可确保队列中不存储误报。作为一个额外的好处，这允许与其他工具共享队列。在下文中，我们将讨论选择、修补和验证可疑校验和的过程的细节，重点是哈希和类哈希计算。

1) Identification

第一步发生在magic bytes的处理过程中，如第III-A节所述。这个结果在一个比较列表中，这个值被对比在，在输入的所有不同着色版本中。我们使用以下启发式方法过滤与校验和相关的有趣补丁候选的比较指令：

1）我们能够在使用相同编码的所有输入中找到突变模式的左侧。 2）这两个参数都不是直接值。 3）在着色阶段pattern发生变化（这类似于TAINTSCOPE使用的约束：值取决于许多输入字节）。

这些检查背后的直觉如下：我们观察到一条指令产生了突变<pattern→ repl>。假设pattern是来自输入的字段，repl是在输入的一部分上计算的哈希值。在校验和比较中，左侧应该始终是输入的一部分，并且在着色过程中用随机值替换输入的大部分应该会更改哈希值（因此是repl）。类似地，如果pattern是来自输入的值，而repl是在输入的某部分上计算的哈希值，则两个参数都不能是立即值。显然，这是一个过度近似，我们有时会发现不属于实际校验和的检查。因此，这种方法有一个明显的缺点：删除的指令可能是相关的边界检查，删除它们可能会导致误报（即错误的新覆盖），甚至导致程序稍后崩溃。因此，我们引入了一个验证阶段，以排除潜在的误报，并识别不可修补的比较指令。在模糊器找到新的输入之后，在我们将其存储在队列中之前，我们尝试修复所有patched的比较指令。如果我们识别出模糊器无法自动修复的patch，我们会立即删除该patch。此外，我们在输入到达队列之前丢弃它。这确保了，我们不会浪费时间来修补我们无法轻松修复的patch，也不会产生误报：使用未修改的可执行文件验证每个输入。

ii) Patching

在我们确定了一组可疑的哈希检查后，我们用patch替换指令，patch具有成功比较的相同副作用。显然，这可能会导致一种不期望的行为：我们可能会意外地删除绑定检查，或者使得路径变得可达--如果没有patch就不能够触发。尽管如此，我们继续使用这个新patch的二进制文件进行模糊处理，因为我们稍后将修复这些问题。

iii) Verification

在我们对一个输入执行了整个模糊阶段之后，我们有了一个初步结果队列。由于我们的patch，这些输入可能不会在unpatched target上显示预期的行为。在验证阶段，我们尝试修复这些无效的输入,通过应用基于突变的从patch指令获得的input-to-state。然后，我们对unpatched target执行fixed input。如果它们仍然触发新的覆盖范围，则将修复的输入写入实际队列。否则，我们将丢弃patch。在以这种方式处理所有初步输入后，下一轮的初步队列将被清除。

IV. IMPLEMENTATION DETAILS

在下文中，我们简要概述了REDQUEEN，这是我们方法的概念验证实现。我们基于模糊器KAFL[37]实现REDQUEEN。

A. kAFL Fuzzer

KAFL是一个不受操作系统限制的、受AFL启发的反馈驱动内核模糊器，它使用硬件加速跟踪功能“英特尔处理器跟踪”（Intel PT）来获取覆盖信息，而无需插桩目标。它构建在KVM和QEMU（即KVM-PT和QEMU-PT）的修改版本之上，以隔离地执行任意x86操作系统。这样，模糊器可以受益于虚拟化能力，例如硬件加速的代码执行，快照和客户代码的Intel PT跟踪。KVM-PT启用guest的Intel PT跟踪，QEMU-PT将生成的跟踪解码为AFL兼容位图。为此，QEMU-PT维护目标的运行时反汇编。这种反汇编是完美的，因为我们反汇编了根据Intel PT跟踪执行的每条指令。我们使用此反汇编来识别hook或patch的指令。这避免了由于基于静态反汇编修补代码而产生的问题，这可能会对某些字节进行错误分类。QEMU-PT和KVM-PT还提供自定义超级调用和对客户机内存的直接内存访问，以便于与目标进行必要的通信和数据传输。模糊器逻辑基于AFL模糊循环（添加了radamsa[29]阶段），并在Python中重新实现。因此，模糊逻辑独立于目标操作系统。我们还修复了Intel PT数据包解码过程中的一些错误，这些错误消除了由中断跟踪导致的大量非确定性。我们总共添加和更改了大约10万行代码。这些变化很大一部分不是由于本文提出的技术。执行这些更改中的大多数是为了增加对环3模糊化的支持，在KAFL中提供VMI功能并修复错误。此外，这些数字还包含大量用于评估和调试目的的代码。

我们的技术需要一些基本要素：获取程序跟踪、在各种断点检查程序状态以及修补内存中的指令的能力。REDQUEEN仍然使用KAFL的架构，并以完全相同的方式获得覆盖信息。此外，它使用KVM-PT和QEMU-PT提供的VMI来插入断点，并在执行期间检查内存和寄存器内容。在下文中，我们将讨论如何在KAFL之上实现我们的技术。

B. Comparison Hooking

我们依靠硬件辅助的虚拟机断点来提取输入到状态的对应关系。每当运行时反汇编程序遇到一个有趣的类似比较的指令时，它的地址就会被存储起来，以便在下一个REDQUEEN分析阶段放置一个钩子。在REDQUEEN阶段，断点被放置在所有有趣的指令上。当命中断点时，参数被提取并保存到缓冲区，以供模糊逻辑稍后使用。断点在多次命中后会被删除，以限制性能影响。注意，我们不仅hook cmp指令，还有call指令和减法。前者用于识别字符串和内存比较，而减法通常由编译器发出，以代替cmp指令来实现切换表。为了实现减法，编译器有时会发出具有负偏移量的特殊lea或add指令。如果调用指令的前两个参数是有效指针（根据各种调用约定），我们假设该函数是一个潜在的比较函数，并为每个参数转储前128字节的内存。

C. Colorization

在着色步骤中，我们尝试用随机值替换尽可能多的字节，而不改变执行路径（更准确地说，AFL bitmap的hash）。这增加了输入中的熵，因此减少了可以应用观察到的pattern的位置的数量。这可以使用算法1中所示的二分查找方法来完成，该方法通常在少量执行（通常在几百次的数量级）内收敛。最坏的情况相当于AFL对每个输入执行的位翻转次数的八分之一。此外，在我们的实现中，我们将查找限制为最多1000步。即使对于最小输入大小为64KB的文件系统驱动程序目标，这也很有效。

![[Pasted image 20230118200900.png]]

D. Instruction Patching

一旦模糊逻辑计算出从输入到状态对应数据的候选的哈希比较指令列表，我们就用始终为真的伪比较指令替换它们。在我们的实现中，我们使用指令cmp al，al，因为它是x86指令集架构上可用的最小比较指令。原始指令的剩余字节用NOP填充。我们使用KVM和QEMU调试工具在VM内部的内存中应用这些patch。然后，使用patched VM继续正常的模糊过程。但是，如果patched 程序处于活动状态，则不会立即将新找到的路径添加到队列中。有时，即使是良性的C代码和通用编译器也会发出在指令中间跳转的程序集。在我们的例子中，这可以通过“英特尔处理器跟踪”（PT）运行时反汇编检测到。在其他情况下，可以使用指令双关[15]或甚至普通断点等技术来避免引入意外的崩溃。然而，应该注意的是，即使在相对较大的目标程序中，我们也没有观察到任何此类行为，因为patched 指令的数量很低（即，在我们的经验评估中，通常少于5条）。

E. Input Validation and Fixing

我们使用算法2来验证和修正初步结果。该算法迭代地通过重复应用单个突变并观察结果输入到状态的对应关系，反复尝试修复所有比较。请注意，有些情况下存在比较顺序，我们需要在修复输入时保留比较顺序。通常，如果文件格式的头包含文件完整内容的校验和，并且文件中的某些块也受校验和保护，则会遇到这种情况。例如，PNG文件IDAT块的内容受CRC-32 sum保护。如果内容是zlib压缩的，则会受到另一个ADLER-32校验和的保护。在这些情况下，我们必须首先修复内部校验和，以便正确计算外部校验和。检查这些校验和的顺序并不明显。然而，更常见的是首先检查外部校验和。因此，我们尝试先修复最后一个比较，以避免不必要的工作。在我们的实验中，这种简单的方法就足够了。然而，总的来说，我们不能假设情况就是这样。当执行一系列的试运行以按照出现的相反顺序修复所有校验和时，我们观察哪个突变会影响哪个比较指令。因此，我们创建了不同patched 指令的依赖关系图。如果第一次迭代的输入无效，我们使用此依赖图对patches执行拓扑排序并获得有效顺序。这允许我们按照所需的顺序对输入应用另一轮修复。如果最终输入在未修改的可执行文件上没有表现出预期的行为，我们将删除有问题的patch，并从初步队列中丢弃输入。

![[Pasted image 20230118202010.png]]

算法2中使用的get_breaked_cmps例程返回当前未满足的所有patched 比较指令的列表，以及正在比较的值.try_fix_value_for_patch尝试应用由第III-A节所述的补丁指令产生的所有突变。然后，该函数检查是否有任何突变修复了比较。如果找到这样的输入，则返回该输入。否则，我们会发现使用我们的技术无法满足比较指令。该补丁将从进一步模糊运行期间使用的补丁列表中删除。get_cmps_influenced例程查找其参数受应用于输入的最后一个fix影响的所有比较指令。这允许我们构建比较指令的顺序，如果需要，稍后将使用这些指令。

**Example 6.**
考虑清单1所示的运行示例中的Bug2。删除两个校验和检查后，模糊器找到初步输入`“01234567abcdefghRQ”`。跟踪产生以下结果：
`p1:=<01234567 → \xc7\x03\0\0\0\0\0\0 >` 
`p2:=<abcdefgh → \xa3\0\0\0\0\0\0\0>。
如果我们同时应用这两种突变，第二个突变将使第一个突变的总和无效。因此，我们首先尝试修复第二个补丁（p2），并注意p1受到影响。fixing p2后，我们获得输入：`“01234567\xa3\0\0\0\0\0\0\0RQ”` 
更改输入的内部校验和也会更改p1的预期值。
p1的新突变现在`<01234567 → \x46\x01\0\0\0\0\0\0\0>。`
然后我们应用第一个补丁p1。这一次，我们不干扰任何其他补丁。
最终输入为：`“\x46\x01\0\0\0\0\xa3\0\0\0\0 \0\0\0\0RQ”`。
由于此输入满足了所有修补的约束，因此我们在没有修补的情况下执行最后一次运行，以确保输入的行为符合预期。这个输入确实会触发Bug2，并从初步队列移动到实际队列。在本例中，我们不需要拓扑排序操作来排序检查，因为我们猜测了修复补丁的正确顺序。

F . Linux User Space Application Loader for KAFL

我们通过Linux ring 3加载器扩展了KAFL，以针对其他用户空间模糊器进行评估，并证明我们的方法是通用的和健壮的。此加载器重新实现AFL fork服务器。由于我们的目标是二进制文件，所以我们使用LD_PRELOAD将forkserver功能注入到目标的启动例程中。通过注入的启动例程触发的自定义KAFL超级调用来执行与模糊逻辑的通信。此外，为了支持KVM-PT中的ring 3跟踪，我们在型号特定寄存器IA32 RTIT CTL MSR中设置了User位。由于最初的KAFL被设计为内核模糊器，它只设置IA32 RTIT CTL MSR.OS以启用环0跟踪。此外，最初的模糊器仅用于模糊64位操作系统。然而，由于某些CGC二进制文件只能为32位目标编译，因此我们扩展了fuzzer以支持32位目标。因此，我们向QEMU-PT添加了32位模式反汇编，以支持32位模式Intel PT跟踪数据的解码。

V. EVALUATION

我们如上所述评估了REDQUEEN的原型实现，以回答以下研究问题：

rq1。对基于I2S的技术是否足够通用，在不同的目标和环境中工作？
rq2。与其他更复杂的技术（如基于污点跟踪或符号执行的方法）相比，我们I2S技术的结果如何
rq3。我们I2S技术的在现实世界的模糊场景中提供了哪些改进？

为了回答这些问题，我们的评估分为三个部分：首先，我们对两个合成测试集（LAVA-M和CGC）和一个真实世界测试集（GNUbinutils）进行比较评估。实验表明，我们的方法组合在很大程度上优于所有其他现有方法。第二，我们证明了我们的工具能够在各种经过良好测试的漏洞中找到新的漏洞。总共，我们在2个不同的Linux文件系统驱动程序中发现了10个错误，在16个用户空间程序和软件库中发现了55个错误。到目前为止，我们获得了16个CVE，4个仍在等待中。最后，我们测量了与KAFL进行的其他突变相比，我们的技术的效率和有效性。我们还通过一个基于小型静态链接PNG库的案例研究，测试了本文中引入的各个技术的影响，因为这种文件格式使用了嵌套校验和。我们证明，我们的方法使我们能够克服以前需要字典和手动删除哈希检查的模糊障碍。

A. Evaluation Methods

所有实验都是在运行Ubuntu Server 16.04.2 LTS的系统上进行的，该系统具有Intel i7-6700处理器（4核）和24 GB RAM。我们将所有工具配置为使用一个模糊化过程，以确保与VUZZER等非多线程工具的可比性。没有实验包含专门针对特定目标所做的更改。除非另有说明，否则我们使用了由可打印ASCII集合中的不同字符组成的未通知的通用种子：“ABC…XYZabc…xyz012。789!¨$. . . ~+”。由于存在各种基本块的定义，并且LAF-INTEL等工具显著改变了二进制中基本块的数量，因此我们总是测量每个模糊器在同一未检测二进制上产生的覆盖范围。因此，未发现的基本块的数量可能与其他论文中报告的数量不匹配，但保证在我们的实验中是一致的。所有实验都进行了多次。在每种情况下，我们报告了在任何时候发现的基本块的中值数量，以及60%的置信区间。最近，人们非常关注发现“深层”错误[34]。虽然“深度”的确切定义仍然有些难以捉摸，但我们使用以下定义作***为一个正在进行的工作：如果从给定的种子输入很难到达，则错误被视为“深度”。因此，我们认为发现新代码覆盖率的能力是发现“深层”错误的能力的一个很好的代理，这是一个很难确定的特性。最后，由于相关研究的术语不同，我们使用“崩溃”来描述导致目标应用程序崩溃的任何输入。我们从不谈论发现的“uniqe”崩溃的数量，因为这一指标非常不可靠，因为不同的工具报告的崩溃数量大相径庭，而且往往是夸大的。相反，我们说“我们能够崩溃”，表示在没有进一步分类的情况下，至少发现了一次崩溃。我们使用术语bug来描述应用程序中具有不相交的根本原因的手动验证和分类的bug。bug不一定是可利用的。最后，在某些情况下，我们获得了CVE编号，我们对其进行了计数和单独列出。

B. LAVA-M

LAVA-M[17]是一组插入到hardt中的合成错误，以达到GNU coreutils套件中真实二进制文件中的位置。它通常用于评估现代模糊器的效率。我们首先描述了其他出版物对LAVAM进行的实验，然后将其与我们的结果进行比较，总结见表II。在LAVA-M的原始论文中，作者进行了两个实验：一个使用未指定的FUZZER和未指定的符号执行工具SES（两者都是未公开的“最先进、备受瞩目的工具”[17]）。这两种工具都在未指定的机器上对照语料库运行了5小时。STEELIX作者进行的所有实验都在一台机器上运行，该机器具有8个Intel（R）Xeon（R）CPU E5-1650 v3内核和8 GB RAM，使用一个线程运行32位Ubuntu 16.04。类似地，Sanjay等人使用VUZZER[35]进行了他们的实验，在一台未指定的机器上运行了5小时，单核内存为4 GB。我们进行了一个类似的实验，每个目标执行5小时。我们使用了原始作者提供的种子的前几个字节，以及我们通常不知情的种子。图1显示了结果（5次运行，每次运行5小时，发现的错误数量的中位数和60%置信区间，以LAVA-M作者预期的错误数量百分比表示）。在所有情况下，我们都发现了比LAVA-M原始作者预期的更多的错误。此外，在所有情况下，我们需要比完整的5个小时更少的时间来查找所有错误。在中等情况下，用了不到5分钟就发现了更多关于who和base64的bug。15分钟后，uniq完全解决。最后，md5sum是最慢的目标，需要25分钟。md5sum比其他目标慢的原因是，我们使用的是busybox环境，其中\/bin/中的所有文件都链接到同一个单片二进制文件，这大大降低了md5的计算速度。

我们发现插入并列出了所有bug，除了who中的两个bug。更重要的是，我们发现了大量的bug（337），这些bug被原作者认为是无法访问的。唯一一个能够找到这些未列出的bug的模糊器是ANGORA。然而，我们发现的bug比ANGORA多50%，未列出的bug数量是ANGORA的三倍多。由于大量未列出的错误，我们联系了LAVA-M的作者之一，他从我们提供的输入中证实了我们的发现。

根据知情种子输入和未知情种子输入之间的差异很小的事实，以及我们以8x到26x的因子优于其他当前最先进的工具的事实，我们得出结论，LAVA-M数据集支持这样的假设，即我们的方法优于最先进的方法，并且能够发现远离所提供的种子输入的深度错误。事实上，即使我们的工具没有种子，我们的表现也优于所有现有方法。但是，应该注意，插入LAVA-M数据集的错误是人为的，并不代表真实世界的漏洞。

C. Cyber Grand Challenge

DARPA的CGC中使用的目标是另一个广泛用于评估模糊度的测试集。类似于LAVA-M语料库，我们现在将描述各种其他模糊器在这些目标上使用的实验设置。然后，我们将他们的结果与我们的结果进行比较。

STEELIX只测试了八个CGC二进制文件的一个子集，并将其结果与AFL-DYNIST进行了比较，后者是一种使用动态二进制检测的AFL版本，比原始AFL慢得多。两种工具都被允许模糊三个小时。STEELIX找到了一架AFL找不到的飞机。相比之下，我们用STEELIX使用的种子在不到30秒的时间内找到了坠机地点。

VUZZER测试了63个二进制文件的子集，过滤使用浮点指令（VUZZER的污点跟踪无法处理）、IPC或容易放入无限循环的二进制文件的二进制文件。作者们友好地向我们提供了他们使用的精确目标集，以及他们能够发现坠机事件的目标集。不幸的是，他们无法向我们提供所用的确切种子。我们用同样的方法重新创建了一组类似的种子。一些输入由CGC中使用的轮询器脚本生成，一些输入来自DARPA原始存储库。然而，我们无法为其中九项挑战创造种子。因此，我们将他们排除在评估之外。VUZZER能够在其中两个排除的二进制文件中找到崩溃。VUZZER的实验是在一台主机上进行的，该主机具有两个未指定的32位Intel CPU和原始DECREE VM中的4GB内存。VUZZER和AFL-PIN均给予6小时的起毛时间。他们能够在27个二进制文件中找到29个崩溃。在这一设置中，AFL-PIN能够发现23起坠机事件。大量的目标二进制文件在忙循环中运行，等待特定的“退出”命令。这会导致大量超时，从而大大降低模糊性能。虽然这种循环在有限的设置（如CGC）中很容易检测到，但这种优化将超出更一般的模糊器的范围。为了减轻这个问题，VUZZER作者手动确保VUZZER始终附加正确的“退出”命令。

我们进行了一组类似的实验，但有一些不同之处：与VUZZER的作者相比，我们使用了Trail of Bits发布的多OS版本[3]。因此，有些比较可能会因细微差异而产生偏差。在这些条件下，我们第一次尝试REDQUEEN时能够触发31个二进制文件中的崩溃，而VUZZER能够触发25个崩溃。

由于这些结果是在完全没有使REDQUEEN适应CGC的情况下产生的，因此该实验作为一个验证集，以确保我们不会将模糊化过程过度拟合到任何特定目标。由于AFL模糊模型主要针对二进制输入格式，CGC包含大量交互式的行基格式，我们进行了另一个实验：我们添加了一些与基于文本的协议相关的突变（主要是拼接行以及添加随机行）。为了加快实验速度，我们还使用了4个核，每个核持续2小时，而不是通常的配置。在这个实验中，我们发现了9个额外的碰撞输入。总共，我们击毁了54个目标中的40个。VUZZER能够在5个二进制文件中找到我们无法崩溃的崩溃。在至少一种情况下，这是由于严重超时，VUZZER通过调整其模糊器以适应前面描述的特定目标（我们没有这样做）来避免这种情况。另一方面，我们崩溃了VUZZER无法崩溃的19个二进制文件。这表明，在这一数据集上，我们能够比VUZZER和AFL-PIN都高出60%和73%。

不幸的是，T-FUZZ的作者没有公开其CGC实验的全部结果。然而，他们表示，在VUZZER使用的二进制文件子集上，他们在分配的6小时内发现了29次崩溃，大大少于我们的方法设法找到的40次崩溃。

对整套CGC二进制文件进行了评估。实验使用了一组未指定的AMD64 CPU，每个目标有四个内核。一致执行处理外包给另一组64个一致执行节点。每次协同执行被限制在4GB内存内，每个目标被模糊化24小时。AFL引信能够发现68个目标的坠毁。DRILLER能够将这个数字增加到77。值得注意的是，作为CGC竞赛的参与者，DRILLER对CGC数据集进行了高度优化。Y et，AFL对基线模糊的改善仅为14%左右。与AFL-PIN（73%）相比，我们对VUZZER数据集的结果表明，如果我们要实现各种DECREE特定机制（如自定义IPC），我们可能会看到类似于DRILLER的改进。

D. Real-World Applications

我们还在几个真实世界的应用程序上评估了REDQUEEN。一般来说，我们发现了模糊器通常会发现的所有类型的错误：对内存的超边界读/写访问、资源耗尽（包括时间和内存）、内存泄漏、堆栈溢出、除以零、断言、释放后使用、未初始化值的使用等等。为了进行此评估，我们忽略了以下错误类：，因为它们太多，无法进行手动分类，对安全性研究也不重要：内存泄漏、资源耗尽、使用未初始化的值（除非它们导致更严重的后果）和堆栈溢出。

binutils。为了估计在难以触及的代码中发现深度错误的能力，我们测量了各种工具对binutils集合中的真实二进制文件产生的覆盖率，以将我们的评估从合成测试用例扩展到更真实的测试。我们使用代码覆盖率作为发现深度错误能力的代理度量，因为发现的错误数量很难确定。为了正确比较工具中发现的bug数量，需要调查成千上万的崩溃。在许多情况下，大多数工具都无法发现一次碰撞，导致了非描述性实验。我们认为代码覆盖率是一个非常好的代理，因为任何模糊器都无法在未覆盖的代码中发现错误。作为测试套件，我们从binutils集合中选择了所有八个程序，这些程序正在处理一个文件而不进行修改。不幸的是，我们无法对DRILLER进行评估，因为它只适用于DECREE二进制文件。此外，由于ANGORA和T-FUZZ还不可用，我们无法运行自己的实验来与它们进行比较。因此，我们选择VUZZER作为为数不多的学术最先进的模糊器，以及具有LAF-INTEL和AFLFAST扩展的AFL。值得注意的是，LAF-INTEL和VUZZER都明确地旨在克服魔法字节和其他模糊障碍，与我们的工具类似。在所有情况下，我们都从一个统一的种子开始衡量解决路障的能力。KLEE不生成测试文件，因为它揭示了新的状态。相反，它只在完全探索状态或达到超时之后生成测试用例。因此，KLEE在运行时只编写少量测试用例并不罕见。到达超时后，它开始解决所有剩余的状态，以产生更多的覆盖率，在某些情况下，它可以花费许多小时的额外计算时间来产生实际的测试用例。因此，我们给KLEE一个7小时的窗口来评估符号状态，加上3小时的测试用例制作。我们在总共10小时后强行终止了KLEE。相同的架构使得很难确定发现新输入的确切时间。出于绘图目的，我们假设输入是以恒定的速率找到的。这一假设显然是错误的，因为我们预计在早期会发现更多的输入。然而，由于我们主要比较所覆盖的基本块的最终数量，因此图中曲线的确切形状并不太相关。VUZZER无法模糊期望在stdin上输入的目标，因此，我们没有cxxfilt目标的VUZZER结果。为了代表其他基于Intel PT的模糊器，我们包括了在Intel PT模式下运行的HONGFUZZ[6]，以及带有Ring 3扩展的原始KAFL。

5次10小时运行的结果如图2所示。值得注意的是，在所有情况下，REDQUEEN都能够触发最多的覆盖。为了确保这些发现不是随机变化的结果，我们对发现的基本块的数量进行了Mann-Whitney U检验，如Arcuri等人[7]所建议的，用于评估随机算法。结果显示在表III中。可以看出，在几乎所有情况下，观察到的差异在p<0.05时都是显著的。有趣的是，VUZZER发现很少新的基本块。我们调查了这种行为，以确保我们没有滥用VUZZER。我们联系了作者，他们复制了我们的实验，并发现了非常相似的结果。在结果对话中，很明显，VUZZER强烈依赖于只有一种有效输入格式的假设。由于大多数binutils程序读取大量不同的格式，VUZZER从搜索中排除了大量路径。此外，VUZZER需要有效的输入来检测错误路径。然而，我们不知情的输入似乎没有严重限制VUZZER，因为它仍然能够立即找到有效的ELF文件（例如，它没有将有趣的路径作为“无趣的错误案例”丢弃）。使用REDQUEEN，我们发现并报告了以下binutils中的错误：ld new、as new、gprof、nm new、cxxfilt和objdump。事实证明，cxxfilt、nm-new和objdump中发现的bug都是共享库中同一个bug的实例，这些bug会破坏C++符号。

我们发现，REDQUEEN、LAF-INTEL和AFLFAST都报告了更高数量的坠机事件。然而，这些“崩溃”中的大多数是超出模糊器设置的内存限制的输入。我们手动验证了objdump中发现的崩溃，并验证了AFLFAST和LAF-INTEL都没有发现任何真正的bug，而REDQUEEN识别的一些崩溃确实是新的bug。这表明，报告发现的崩溃数量的常见做法可能是一种误导性的指示，需要进行适当的错误分类。

案例研究：objdump。令人惊讶的是，我们能够解决objdump中的一个复杂约束，该约束使用哈希表查找函数bfd-get逐段名称（bfdobj，charname）来测试输入对象文件obj中是否存在具有给定名称的节：由于给了该函数两个指针参数，REDQUEEN自动提取名称并将其添加到动态字典中。大破坏阶段后来能够将其插入正确的位置。同样，所有其他模糊器在ar上表现出较低性能的原因是ar使用对strncmp的调用来检查前几个字节是否为“！<thin>”或“！<bout>”。通常，LAF-INTEL能够拆分这样的字符串比较。然而，LAF-INTEL只考虑函数strcmp和memcmp，而不考虑大小受限的版本。这是一个很好的例子，其中更精确的方法需要非常详细的环境模型。这两个结果都证明了我们使用的简单过近似在实际应用中是如何有用的。

其他目标。为了确保我们的工具能够发现新的bug，我们在一组不同的现实世界目标上评估了bug发现能力。结果见表IV。在所有情况下，我们都手动分类并报告了发现的错误。我们从其他论文中常用的目标开始，即libtiff（tiff2ps）[31]、[34]、[40]、imagemagick[34]、[30]和jhead[16]、[28]，每一个都在Ubuntu的最新版本（16.04 LTS）中，这些之前报告的错误应该被修复。尽管这些工具之前已经过详尽的测试，但我们还是发现了新的bug，并进行了分类和报告。我们还评估了一组基于媒体文件格式的工具：sam2p、wine和fdk aac（ffmpg的一部分）。根据最初KAFL论文的精神，我们使用REDQUEEN针对最新的Ubuntu版本（16.04 LTS）中的两个文件系统驱动程序（特别是hfs.ko和ntfs.ko）。在这两种情况下，我们都发现并报告了多个内存损坏。最后，除了到目前为止我们评估的（主要是）基于二进制的目标之外，我们还测试了多个众所周知的基于文本的目标：mruby、perl、bash和libxml2。在几乎所有的目标中，我们都使用了未变形的种子来发现虫子。该实验表明，我们的方法不仅适用于用户空间代码，也适用于内核级代码。

案例研究：mruby。我们发现的一个非常有趣的漏洞是基于mruby中的整数溢出。当调整字符串大小时，选择二次幂作为新的分配大小。计算可能溢出，导致大小为负。这是在计算后通过额外的符号检查防止的。编译器意识到二的幂总是正的，并且由于有符号整数溢出在C中是未定义的行为，因此取消了检查。因此，我们能够生成长度为负的字符串。由于新长度小于旧长度，因此不进行分配，但字符串长度更新为负值。然后，生成的字符串跨越整个内存范围。这种行为仅出现在使用gcc和优化级别2编译的未安装指令的可执行文件中。这个bug很好地说明了为什么在纯二进制目标上有效工作的技术很重要。我们强烈怀疑溢出的整数（一个具有19位数字的64位值）是通过ASCII整数编码找到的。

E. Baseline Evaluation: PNG File F ormat

我们进行了以下实验，以证明在我们的实验中获得的改进确实是由于所提出的技术。我们使用lodpng库，这是一个很容易静态链接的小型库，有助于加载PNG文件。PNG格式是常见模糊障碍的一个有趣的案例研究，因为它基于块列表。每个块以一个标头（由一个4字节的魔术值标识）开始，并包含内容上的CRC32校验和。IDA T的内容chunk是zlib压缩的像素数据，以及另一个Adler-32校验和。在每个实验中，我们进行了15次，每次一小时，并测量了一段时间内发现的基本块的数量。实验结果如图3所示。该图包含在每个时间点发现的基本块的中值数量以及置信区间。

首先，我们验证了REDQUEEN而不是KAFL成功地解决了魔法字节。为此，我们禁用了二进制中的两个校验和检查，并将KAFL、KAFL与包含所有相关魔法字节的字典以及REDQUEEN的结果进行比较。该实验的结果显示在图3的“已删除校验和”配置中。可以看出，与基线相比，词典大幅增加了KAFL产生的覆盖范围。然而，即使没有提供字典，REDQUEEN也能够实现完全相同的覆盖率，尽管这样做需要更多的时间。对于下一个实验，我们使用未修改的目标来证明REDQUEEN能够克服校验和。同样，不带REDQUEEN的KAFL在有字典和没有字典的情况下都会被评估。由于KAFL无法克服校验和，因此它只能找到非常少的路径，而不考虑字典。另一方面，REDQUEEN能够识别和解决相关的校验和，因此实现了与前一个实验相同的覆盖率。事实上，它甚至找到了一些更基本的块（现在激活的校验和计算）。这个案例研究表明，我们能够克服校验和；此外，它还展示了REDQUEEN如何以自动化的方式处理这些障碍。对于普通KAFL，我们需要禁用校验和（在封闭源代码目标上不容易实现的任务），并提供一个自定义字典以获得有趣的覆盖范围。这个实验表明，我们的技术与手动查找一个好字典和删除校验和一样有效。

F . Performance

在这个实验中，我们衡量了我们方法的效率和有效性。为了衡量效率，我们比较了REDQUEEN、KAFL、LAF-INTEL和AFLFAST实现的每秒执行总数。我们通过考虑REDQUEEN中使用的不同变异引擎所发现的输入百分比来获得有效性度量。最后，我们评估了所提出的编码方案的普遍性。在所有情况下，我们使用第V-D节中关于binutils套件的实验数据。

![[Pasted image 20230119164752.png]]

总体模糊性能见图4。条形图表示每秒执行的平均执行次数。与LAF-INTEL和AFLFAST相比，KAFL和REDQUEEN的通常性能影响通常在25-50%之间。这是因为KAFL不使用基于快速编译器的检测，而是在二进制代码上工作。尽管如此，据我们所知，REDQUEEN是迄今为止速度最快的纯二进制模糊器。

在某些情况下，REDQUEEN的表现略好于KAFL。虽然这个结果是反直觉的（毕竟，我们执行了额外的工作），但对这种行为有一个很好的解释：在现实世界的目标上，每秒执行的次数严重依赖于队列中的输入。如果队列中充满了缓慢的输入，则性能会下降。当KAFL无法克服障碍时，唯一的新输入是执行更多循环迭代的输入。如图4所示，REDQUEEN扩展对每秒执行次数的影响很小，有时甚至会增加执行的次数。即使基于断点的跟踪很慢（通常是50倍或更高），它也几乎不会影响模糊性能，因为队列中的每个输入只触发一次REDQUEEN阶段。表V显示了有效性的测量结果。REDQUEEN在每个输入上使用了所有技术，并记录了每个技术发现的新输入的数量。可以看出，基于输入到状态对应的突变通常比其他阶段发现更多或更多的新输入，同时使用的时间明显更短。这表明，我们的技术远远超出了原型障碍：它们有助于比其他突变策略更快地找到大量路径。最后，我们通过计算使用每个编码方案找到的路径的百分比来评估不同编码方案的流行程度。结果如表VI所示。可以看出，我们所做的几乎所有改进都是由于我们认为的一一对应。由于最后两个实验，我们认为基于状态的突变输入是一种高度通用、有效和高效的方案，可用于显著提高模糊器的性能。

G. High-Level Summary

在展示了我们能够显著提高三个大型测试语料库的覆盖率，并在内核和用户空间软件中发现新的bug之后，我们得出结论：RQ 1。I2S技术对于模糊目的是有用的。在对相同测试集上的最先进工具的结果进行比较后，我们有信心回答RQ 2：在衡量发现新行为和错误的能力时，我们能够胜过当前基于符号执行和污点跟踪的方法，以VUZZER、ANGORA、T-FUZZ和KLEE为代表。最后，我们证明，即使在仅二进制的场景中，我们对基于状态对应的技术的输入也足够强大，足以与其他方法竞争，即使消除了对竞争工具的哈希检查，并为它们提供了适当的字典。这符合RQ 3。总之，我们确信我们的I2S方法显著改进了基于覆盖的反馈模糊化。

VI. LIMITATIONS

我们的方法在不访问源代码和不了解环境的情况下适用。是的，即使他们可以访问源代码，它也优于最先进的模糊器。然而，这并不意味着更复杂的方法是无用的。相反，我们坚信这些方法在某些我们的方法不能提供任何优势的地方时有用的。我们在手动检查本文讨论的不同目标时遇到了一些此类情况的示例：PNG文件格式，包含解码器在执行过程中解压缩的压缩数据。在binutils测试集的一些程序中，输入中的一个字符串用于索引哈希图，并返回一个随后使用的整数。最后，来自LAVA-M数据集的base64实用程序应用base64解码。我们当前的实现没有为base64提供编码方案。在所有这些情况下，输入与转换发生后的状态不对应。因此，我们的方法无法有效地解决随后出现的约束。我们认为，前两种情况（压缩和哈希图）对于基于一致执行的方法来说也很困难。大多数concolic引擎无法有效地处理必须使用不同路径来更改值的情况。在base64的情况下，我们可以很容易地添加另一个编码器。然而，正如我们的评估所显示的，这些案例很少。因此，能够解决这些问题的工具会遇到更常见的问题，例如路径爆炸或在复杂的现实世界目标上的性能不佳。我们认为，在可能的情况下，将我们的轻量级方法作为第一步，而不是使用复杂的方法来解决剩余的挑战将是有益的。

VII. CONCLUSION

在本文中，我们提出并评估了I2S的方法，以改进模糊。我们已经表明，通过解决magic-bytes 比较和校验和检查，可以显著提高仅二进制目标的覆盖率。虽然我们的方法不像其他基于符号执行或污点跟踪的方法那样基于形式主义，但我们认为它非常符合AFL的精神：它快速、轻量级，最重要的是健壮。即使项目的某些部分很难分析，我们的方法仍然适用于目标的其他部分并有效。我们相信，我们的工作表明，我们可以显著提高模糊器的性能，而不会回到脆弱和复杂的方法。

标签：AFL,模糊,模糊化,译文,使用,REDQUEEN,我们,输入
From： https://blog.51cto.com/u_16072836/6192298