VUzzer: Application-aware Evolutionary Fuzzing
(NDSS’17)
Abstract
Fuzzing是一种有效的软件测试技术，用于查找错误。考虑到实际应用程序的大小和复杂性，现代模糊器往往是可扩展的，但在探索执行中更深层次的错误方面无效，或者能够在应用程序中深入渗透但不具有可扩展性。
在本文中，我们提出了一种应用程序感知(application-aware)的进化模糊测试策略，它不需要任何有关应用程序或输入格式的先验知识。为了最大化覆盖范围并探索更深入的路径，我们利用基于静态和动态分析的控制和数据流功能来推断应用程序的基本属性。与应用程序不可知(application-agnostic)的方法相比，这可以更快地生成有趣的输入。我们在VUzzer中实现我们的模糊测试策略并在三个不同的数据集上进行评估：DARPA Grand Challenge二进制文件（CGC），一组实际应用程序（二进制输入解析器）和最近发布的LAVA数据集。在所有这些数据集中，通过快速查找几个现有和新的错误，VUzzer产生的结果明显优于最先进的模糊器。
1 INTRODUCTION
模糊测试是一种在漏洞变成漏洞之前及早发现漏洞的测试技术。然而，现有的模糊器主要用于发现表面缺陷，接近软件表面（低悬挂的错误）[13]，[17]，同时与更复杂的模式进行斗争。现代程序具有复杂的输入格式，并且执行在很大程度上取决于符合格式的输入值。通常，模糊器会盲目地改变值以生成新输入。在此（pes- simistic）场景中，大多数结果输入不符合输入格式，并在执行的早期阶段被拒绝。这使得传统的随机模糊器在查找隐藏在执行中的错误时通常无效。
AFL [52]等最先进的模糊器采用进化算法来运行有效的输入生成。这种算法采用简单的反馈回路来评估输入的好坏程度。详细地说，AFL保留任何发现新路径的输入并进一步改变该输入以检查这样做是否会导致新的基本块。虽然简单，但这种策略无法有效地选择最有希望的输入来从发现的路径中进行变异。此外，改变输入涉及回答两个问题：在哪里进行变异（在输入中哪个偏移）以及用于变异的值是什么？问题是AFL完全与应用程序无关，并采用盲变异策略。它只是依赖于生成大量的变异输入，希望能够发现一个新的基本块。不幸的是，这种方法产生了一种缓慢的模糊测试策略，它只能通过纯粹的运气发现深层执行路径。幸运的是，通过考虑回答上述问题的信息，我们可以提高类似AFL的模糊器的效率。
在这个方向上，象征性和执行性执行的使用已经显示出有希望的结果[33]，[47]。 Driller [47]使用复杂的执行来使AFL能够探索新的路径，当它被卡在表面上时。然而，像AFL这样的模糊器旨在针对任意大型程序，尽管有一些进步，但是对这些程序应用符号/模仿技术仍然是一个挑战[10]。例如，Driller以126个DARPA CGC二进制文件为基准[15]，当AFL卡在41个这样的二进制文件上时，它的concoic引擎只能从13个这样的二进制文件中产生新的有意义的输入。 LAVA论文[17]中报告的结果证明了符号执行方法的类似问题。在最近的另一项研究[50]中，作者报告说，基于符号执行的输入生成（使用KLEE）在探索有意义和更深层的路径方面并不十分有效。实质上，虽然将模糊测试与符号执行相结合是一个有趣的研究领域，但这种方法也显着削弱了模糊测试的原始关键优势之一：可伸缩性。
在本文中，我们介绍了VUzzer，一个应用程序感知的进化模糊器，它既可扩展又可快速发现执行中的漏洞。与优化输入生成过程以最大速率生成输入的方法相比，我们的工作探索了设计领域的一个新点，我们在前端做更多的工作，产生更少但更好的输入。关键的直觉是我们可以通过基于控制和数据流应用功能的“智能”突变反馈回路来提高通用模糊器的效率，而无需采用可扩展性较低的符号执行。我们展示了我们可以通过在模糊运行期间对应用程序进行轻量级静态和动态分析来提取这些功能。我们的控制流功能允许VUzzer优先考虑深度（并因此感兴趣）路径，并在改变输入时优先考虑频繁（因此无趣）路径的优先级。我们的数据流功能允许VUzzer准确地确定改变这些输入的位置和方式。
由于其应用感知突变策略，VUzzer比现有的模糊器更有效。我们在三个不同的数据集上评估了VUzzer的性能：a）DARPA CGC二进制文件[15]，这是一组旨在评估错误发现技术的人工创建的交互式程序; b）一组具有不同复杂程度的Linux程序（djpeg，mpg321，pdf2svg，gif2png，tcpdump，tcptrace）和c）最近发布的来自LAVA团队的二进制文件[17]，许多Linux实用程序都注入了多个错误。在我们对不同数据集的实验中，我们通过生成更少输入的订单来表现优于AFL，同时发现更多崩溃。例如，在mpg3211中，我们通过执行23K输入发现300次独特崩溃，而883K输入则通过AFL找到19次独特崩溃。
贡献：我们做出以下贡献： 1）我们表明现代模糊器可以“更智能”而不需要采用符号执行（难以扩展）。 我们的应用感知突变策略将AFL等最先进的模糊器的输入生成过程提高了几个数量级。 2）我们提出了几个应用程序功能来支持有意义的输入变异。 3）我们在三个不同的数据集上评估VUzzer，一个实现我们的方法的功能齐全的模糊器，并表明它非常有效。 4）为了促进该领域的进一步研究和支持开放科学，我们开放采购我们的VUzzer原型，可在https://www.vusec.net/projects/fuzzing获得。
2 BACKGROUND
在本节中，我们将介绍在后续章节中讨论VUzzer所需的背景知识。
A. A Perspective on Fuzzing
Fuzzing是一种软件测试技术，旨在发现应用程序中的错误[35]，[48]。模糊器的关键是它能够生成错误触发输入。从输入生成的角度来看，模糊器可以是基于突变或基于生成的。基于突变的模糊器从给定应用程序的一组已知输入开始，并改变这些输入以生成新输入。相比之下，基于生成的模糊器首先学习/获取输入格式并基于此格式生成新输入。 VUzzer是一个基于突变的模糊器。 关于输入变异，模糊器可以分为白盒，黑盒和灰盒。 whitebox fuzzer [21]，[22]，[26]假设访问应用程序的源代码 - 允许它执行高级程序分析，以更好地理解输入对执行的影响。 blackbox fuzzer [1]，[39]无法访问应用程序的内部。 greybox模糊器的目标是中间地带，采用基于对应用程序二进制代码的访问的轻量级程序分析（主要是监控）。 VUzzer是一个灰盒子模糊器。 影响输入生成的另一个因素是应用程序探索策略。如果模糊器生成输入以遍历特定的执行路径集[20] - [22]，[26]，[38]，则指示模糊器。另一方面，基于覆盖的模糊器旨在生成输入以遍历应用程序的不同路径，以期触发其中某些路径上的错误[14]，[28]，[44]，[47]，[ 52。 VUzzer是一个基于覆盖的模糊器。 根据定义，基于coverage的模糊器旨在最大化代码覆盖率以触发可能包含错误的路径。为了最大化代码覆盖率，模糊器尝试生成输入，使得每个输入（理想情况下）执行不同的路径。因此，对于模糊器来说，考虑每个生成的输入所获得的增益是至关重要的，这是我们称之为输入增益（IG）的属性。 IG被定义为输入通过执行新的基本块或增加先前执行的基本块的频率（例如，循环执行）来发现新路径的能力。 显然，如果基于覆盖的模糊器经常生成具有非零IG的输入，则它是有效的。不难发现，使用非零IG生成输入的能力需要解决第I部分中的两个问题（在哪里以及要改变什么）。不幸的是，大多数现有的模糊器，尤其是基于变异的模糊器，都没有为实现这一目标付出太多努例如，让我们考虑清单中的代码片段。 1。
...
read(fd, buf, size);
if (buf[5] == 0xD8 && buf[4] == 0xFF) //notice the order of CMPs
... some useful code ...
else
EXIT_ERROR("Invalid File\n");
在此代码中，buf包含来自输入的污染数据。 在这个简单的代码中，AFL运行了几个小时而没有取得任何进展，如果条件。 这种相当悲观行为的原因有两个：（i）AFL必须完全正确地猜测FFD8字节序列; （ii）AFL必须找到正确的抵消（4和5）进行变异。 由于AFL是基于coverage的模糊器，对于未通过if条件并因此导致新路径（else分支）的输入，AFL可能专注于探索此新路径，即使路径导致错误状态。 在这种情况下，AFL卡在else分支中。 基于符号执行的解决方案，如Driller [47]可以通过在右偏移处提供右字节的输入来帮助AFL。 然而，这不是一个明确的解决方案，因为，通过这个新输入，AFL再次开始随机变异。 在此过程中，它可能会尝试再次改变这些偏移，浪费处理能力和时间。
...
read(fd, buf, size);
...
if (...) {
if (...) //nested if
...
} else {
...
}
现在考虑列表中的另一个简单（伪）代码片段。 2.在第5行，输入字节上有另一个多字节if条件，它嵌套在外部if中。由于AFL可能无法满足分支约束，因此它将生成遍历else分支的输入。由于在else分支中存在要探索的代码，AFL将无法确定针对if分支的优先级。即使通过符号执行，也很难将此类知识传授给AFL。因此，嵌套if代码区域内的任何错误都可能保持隐藏状态。在另一种情况下，当AFL卡在第5行的if条件时，基于符号执行的方法（如Driller [47]）将尝试通过顺序否定路径条件来找到新路径。在这个过程中，他们可能会否定第4行的约束以找到新的路径，这可能会导致一些错误处理代码。但是，AFL不了解这种错误处理代码，因此，它将开始探索这个方向。通常，有一些复杂的现实世界代码结构可能会阻碍基于覆盖的模糊器的进展。
为了理解这些代码构造，我们将介绍清单3中提供的更复杂的代码片段。虽然VUzzer不需要源代码，但我们使用高级C代码来更好地说明。代码读取文件，并根据输入中固定偏移量的某些字节执行某些路径。
int main(int argc, char **argv) {
unsigned char buf[1000];
int i, fd, size, val;
if ((fd = open(argv[1], O_RDONLY)) == -1)
exit(0);
fstat(fd, &s);
size = s.st_size;
if (size > 1000)
return -1;
read(fd, buf, size);
if (buf[1] == 0xEF && buf[0] == 0xFD) // notice the order of CMPs
printf("Magic Bytes matched!\n");
else
EXIT_ERROR("Invalid File\n");
if (buf[10] =='%' && buf[11] == '@') {
printf("2nd stop: on the way...\n");
if (strncmp(&buf[15], "maze", 4) == 0) //nested if
...some bug here...
else {
printf("you just missed me...\n");
... some other task ...
closed(fd);
return 0;
}
} else {
ERROR("Invalid bytes");
... some other task ...
closed(fd);
return 0;
}
close(fd);
return 0;
}
有趣的是，当我们使用AFL [52]运行清单3中的代码片段时，我们无法在24小时内到达错误状态。这个代码片段有什么特别之处，AFL等模糊器中缺少什么？我们通过考虑以下代码属性来解决这个问题：
1）魔术字节：首先比较第二个和第一个字节以验证输入（第11行）。如果在某些输入偏移处未正确设置这些字节，则立即丢弃输入。在我们的示例中，首先检查偏移1，然后检查偏移0。我们在实际应用程序中观察到了这种行为，例如djpeg实用程序。这也解释了AFL需要数百万个输入来生成有效的jpeg image2。由于AFL不是应用程序感知的，因此它不知道这样的字节和偏移量。它将继续猜测字节和偏移的有效组合。
2）更深入的执行：为了更深入地执行，必须通过第15行的另一个检查，比较偏移10和11（注意，这些偏移可以从输入读取，因此在输入之间变化，不像魔术字节的情况）。无论该检查的结果如何，都采用新的路径。然而，真正的分支将导致第18行的错误点。再次，在处理此示例时，AFL花费很长时间来猜测字节和偏移的有效组合。通常，在输入生成的几次迭代之后，大部分输入将落入错误处理代码中。 AFL和搜索新基本块的任何其他基于覆盖的模糊器可能会从这些输入中进一步探索，因为这些输入确实找到了新的代码。但是，如果我们考虑探索更有意义和更有趣的路径，重用这些输入不会带来任何好处，并阻碍对应用程序代码的进一步探索。
3）标记：为了到达第18行的错误点，在第17行有一个分支约束要满足。应该注意的是，这些字节可能不存在于固定偏移处，而是作为某些字段的标记。许多输入格式，例如JPEG，PNG或GIF。米勒和彼得森表明，这些标记的存在（和不存在）对执行的代码有直接影响[36]。由于这些标记通常是多字节的，因此AFL努力生成这些字节以执行某些路径。
4）嵌套条件：在基于覆盖的模糊测试的上下文中，每条路径都很重要。但是，达到某些路径可能比其他路径更难。例如，为了到达线18，输入必须满足线17处的检查，其仅在满足线15处的约束时被触发。因此，为了增加到达第18行的机会，我们需要更频繁地模糊到达第15行的任何输入。在AFL的情况下，即使它在第15行通过或失败约束，它在两种情况下都发现新的路径并且它试图以相等的概率模糊对应于两个分支的输入。在这个过程中，它花费很长时间来改变执行更简单路径的输入，从而最小化到达第18行的机会。这是在第17行花费更少的时间来满足约束的结果。显然，这种策略不能优先考虑关注有趣路径的努力。更好的策略是根据应用程序的控制流特性优化工作。
有趣的是，其中一位LAVA作者在最近发表的文章中指出了AFL的类似问题[16]。这支持了我们的观察结果，像AFL这样的黑/灰盒模糊器往往与应用程序无关，这使得它们在发现难以触及的错误方面效率大大降低。
我们注意到，上面讨论的一些问题原则上可以通过基于符号/模仿的方法[9]，[20]，[22]，[33]来处理，例如Driller [47]。 Driller结合AFL和concolic执行来探索更深层次的执行路径。通过符号执行，我们可以快速学习魔术字节并帮助AFL跨越第11行的第一个障碍。但是，AFL将再次卡在以下行中。此外，这种组合再次与嵌套条件无关，因此路径优先化仍然是一个问题。更普遍和实际的问题是基于符号执行的解决方案的可扩展性差。虽然在这个小动作示例中不是问题，但实际应用程序非常复杂，足以将符号执行推向状态爆炸场景。从Driller论文[47]中的结果可以看出这一点：在DARPA CGC的41个二进制文件中，Driller的concoic引擎只能为13个二进制文件生成新的有意义的输入。另一项研究[50]根据经验确定，符号执行不适合寻找探索有趣路径的输入。因此，尽管CGC二进制文件具有很好的结果，但基于符号/模型执行的方法的可扩展性差仍然是实际应用程序的一个强大的限制因素。
B. Evolutionary Input Generation
尽管有一些陷阱，AFL是一个非常有前途的模糊器。 AFL的成功主要归功于其反馈循环，即增量输入生成。在我们的激励示例的情况下，几乎不可能生成将在一个突变中达到错误状态的输入。这促使我们采用渐进式模糊测试策略，即依赖于用于输入生成的进化算法（EA）的模糊测试策略。在下文中，我们将简要介绍典型EA遵循的主要步骤（请参阅算法1）。在后面的部分中，我们将详细介绍VUzzer的主要组件，并参考这些步骤。
每个EA都以一组初始输入（种子）开始，这些输入经历了如下的进化过程。通过一些选择概率，选择一个或两个输入（父项）（SELECT1状态）。然后，这些输入由两个遗传算子处理，即交叉（RECOMBINE状态）和突变（MUTATE状态）。在交叉中，通过选择偏移（切割点）并交换相应的两个部分以形成两个子项来组合两个输入。在变异中，我们在单个父输入上应用几个变异操作符（如添加，删除，替换字节）以形成一个子节点。通过这种策略，我们得到了一组经过评估状态（EVALUATE）的新输入。在此状态下，我们基于一组属性监视每个新输入的执行。这些属性用于适应度函数以评估输入的适合性。我们为下一代输入选择具有最高适应度分数的输入。整个过程一直持续到满足终止条件：达到最大代数或达到目标（在模糊测试的情况下，发现崩溃）。
3. OVERVIEW
为了解决上一节中提到的挑战，我们提出了VUzzer，一种应用感知的进化模糊器。图1概述了其主要组件。由于VUzzer是一个进化模糊器，因此有一个反馈循环可以帮助从旧的输入中获得新的输入。在生成新输入时，VUzzer会根据其在上一代输入上的执行情况来考虑应用程序的功能。通过考虑这些特性，我们使反馈回路“智能”并帮助模糊器找到具有高频率的非零IG的输入。
A. Features
VUzzer的两个主要组件是静态分析器（如左图所示）和主（动态）模糊测试循环（如右图所示）。我们使用这些组件从应用程序中提取各种控制和数据流功能。图1显示VUzzer不断将这些信息反馈到进化突变和交叉算子中，以帮助在下一代产生更好的输入。我们首先介绍这些功能，然后讨论静态分析器和主要模糊环路。
数据流功能：数据流功能提供有关输入数据与应用程序中的计算之间关系的信息。 VUzzer使用众所周知的技术（例如污点分析）提取它们，并使用它们根据输入中某些偏移处的数据类型推断输入结构。例如，它通过检测x86 ISA的cmp系列的每个指令来确定输入字节来确定分支（“分支约束”），以确定它使用哪些输入字节（偏移）以及它与哪些值进行比较。通过这种方式，VUzzer可以确定哪些偏移对于变异感兴趣以及在这些偏移处使用哪些值（在第I部分中提供问题的部分答案）。 VUzzer现在能够通过更频繁地定位此类偏移并通过在这些偏移处使用预期值来满足分支约束来更明智地进行变异。这样做可以解决魔术字节的问题，而无需使用符号执行。
同样，VUzzer监视lea指令以检查索引操作数是否被污染。如果是这样，它可以确定相应偏移处的值是int类型并相应地改变输入。除了这两个简单但功能强大的功能外，还有许多其他功能。
控制流功能：控制流功能允许VUzzer推断某些执行路径的重要性。例如，图2显示了清单3中代码的简化CFG。执行错误块的输入通常不是很有趣。因此，识别这样的错误处理块可以加速有趣输入的生成。我们将在以下部分中展示如何检测错误处理代码。目前，我们假设我们可以启发式地识别包含错误处理程序的基本块。
另一个例子涉及嵌套块的可达性。到达块F的任何输入更有可能比到达块H的输入更深入到代码中，因为后者不是嵌套的。我们使用控制流功能来对路径进行优先级排序和优先级排序。由于枚举应用程序中的所有可能路径是不可行的，我们通过为各个基本块分配权重来实现此度量。具体而言，作为错误处理代码一部分的基本块获得负权重，而难以到达的代码区域中的基本块获得更高权重。
图1显示了单次模糊测试包含几个步骤。 VUzzer期望有效输入的初始池SI，称为种子输入。第一步是执行过程内静态分析以获得一些控制流和数据流特征（第III-B节），然后是主要的进化模糊循环。在本节的其余部分，我们将介绍描述整个过程的所有步骤。
B. The static analyzer
在模糊测试过程开始时，我们使用轻量级过程内静态分析来（i）通过扫描应用程序的二进制代码来获得cmp指令的立即值，以及（ii）计算应用程序二进制的基本块的权重。
应用程序代码中cmp指令中存在的许多立即值通常表示应用程序期望输入在某些偏移处具有许多这些值。例如，清单3中对程序的分析产生了每个基本块的权重列表LBB和包含{0xEF，0xFD，％，@，MAZE}的字节序列的列表Limm。为了确定基本块权重，我们将每个函数的CFG建模为马尔可夫模型，并计算到达函数中每个基本块b的概率pb。然后我们计算每个基本块b的权重wb为1 / pb。因此，到达基本块的概率越低，重量越高。使用该模型，每个基本块的概率和权重显示在图2中的每个节点旁边（参见第IV-A3节）。我们观察到，例如，到达基本块G的概率小于到达基本块F的概率，而基本块F的概率低于基本块H.VUzzer在模糊循环的后续步骤中使用这些列表。
C. The main fuzzing loop
我们通过使用算法1中的步骤来描述主要模糊测试循环。在主循环开始之前，我们使用种子输入SI集执行应用程序以推断出一组初始的控制流和数据流特征。对于SI中的所有输入，我们运行动态污点分析（DTA）以捕获有效输入的共同特征。具体来说，我们这样做是为了前面提到的魔术字节和错误处理代码检测。使用这些功能，我们生成一个初始输入总体，作为算法1中INITIALIZE步骤的一部分。请注意，我们的魔术字节检测确保这些新输入跨越第一次这样的应用程序检查。由于DTA具有很高的开销，我们在主循环开始后尽可能少地使用它。
输入执行：我们使用上一步中的每个输入执行应用程序，并生成相应的已执行基本块的跟踪。如果任何输入执行以前看不见的基本块，我们会污染输入并使用DTA通过监视应用程序的数据流功能来推断其结构属性。 适应度计算：在算法1的评估步骤中，我们计算每个输入的适应度作为执行的基本块的频率的加权和。我们使用权重列表LBB在基本块上分配权重。属于错误处理代码的基本块会产生负权重 - 现在我们仍然假设我们可以识别这些基本块。该适应度计算背后的直觉是为执行具有较高权重的基本块的输入提供高分，从而对相应路径进行优先级排序，同时还执行具有高频率的某些基本块以捕获大循环。例如，让我们考虑两条路径p1和p2，分别由两个输入i1和i2执行，即p1 = A→B→D→E→H→J和p2 = A→B→D→E→F→J.Forsimplicity，let我们假设错误处理基本块J得到权重-1并且每个基本块的执行频率是1.使用图2中的权重，p1和p2的频率的加权和是7（1 + 1 + 2 + 2 + 2-1）和9（1 + 1 + 2 + 2 + 4-1）。因此，输入i2获得更高的适应度分数，并且将比i1更多地参与生成新输入。该步骤最终以其健康分数的降序生成输入的排序列表Lfit。
遗传算子和新输入生成：这是我们模糊测试策略中最后也是最重要的功能，包括算法1中的SELECT，RECOMBINE和MUTATE步骤。这些子步骤一起负责生成有趣的输入。在主循环的每次迭代中，我们通过组合和改变来自S I的输入，所有受污染的输入和Lfit的前n％来生成新一代输入。我们将此集称为ROOT集。
具体来说，我们通过交叉和变异生成新的输入。首先，我们从ROOT中随机选择两个输入（父母）并应用交叉产生两个新输入（儿童）。具有固定概率，这两个输入进一步突变。 Mutation使用多个子操作，例如删除，替换和在给定输入中的某些偏移处插入字节。变异运算符利用数据流功能生成新值。例如，在插入或替换字节时，它使用来自Limm的字符来生成不同长度的字节序列。类似地，选择来自当前输入的父母的各种偏移用于突变。因此，如果存在任何魔术字节，它们将在结果输入中的适当偏移处被替换。
这个循环的输入生成一直持续到我们满足终止条件。目前，我们在发现崩溃或VUzzer达到预先配置的代数时终止。
为便于参考，表I提供了我们在整篇论文中使用的符号列表。在下一节中，我们将详细介绍通过使用控制流和数据流功能来获取有关输入结构的相关信息的算法。
4.DESIGN AND IMPLEMENTATION
在本节中，我们将详细介绍计算上一节中讨论的几种基元的技术。 该部分还介绍了VUzzer的实现细节。
A. Design Details
1）动态污点分析（DTA）：DTA是VUzzer的核心，因为它在发展新输入方面发挥着重要作用。这也是将VUzzer与现有模糊器区分开来的技术。 DTA用于监视应用程序内受污染的输入（例如，网络包，文件等）的流动。在程序执行期间，DTA可以确定哪些存储器位置和寄存器依赖于受污染的输入。根据粒度，DTA可以将受污染的值追溯到输入中的各个偏移量。 VUzzer使用DTA跟踪cmp和lea指令中使用的污染输入偏移。对于每个执行的cmp指令cmp op1，op2（op1和op2可以是寄存器，存储器或立即操作数），DTA确定op1和/或op2是否被一组偏移污染。我们的DTA实现能够在字节级别跟踪污点。对于给定的受污染操作数op，DTA为op的每个字节提供污点信息。象征性地，如果op表示为b3，b2，b1，b0，则DTA分别为每个字节bi提供污点信息。我们表示将给定cmp指令的第i个操作数的第j个字节污染为Tji的偏移集。我们还记录了这些操作数的值。象征性地，我们将受污染的cmp指令表示为cmpi =（f set，value），其中f set和value是受污染输入的偏移集和cmp指令的无污染操作数的值集。对于每个lea指令，DTA仅跟踪索引寄存器。 Llea包含污染此类索引的所有偏移量。
2）Magic-byte Detection：基于我们对具有魔术字节的文件格式的理解，我们假设魔术字节是输入字符串中固定偏移处的固定字节序列。我们已经在几种具有魔术字节的文件格式上验证了这种假设，例如jpeg，gif，pdf，elf和ppm。由于VUzzer假定给定应用程序有一些有效输入，我们在模糊测试开始时在这些输入上使用DTA的结果。由于应用程序期望输入包含魔术字节，因此DTA在cmp指令上的结果将包含对魔术字节的相应检查。
例如，清单3中的代码在输入文件的开头需要一个魔术字节0xFDEF。因此，DTA将捕获两个cmp指令-cmp reg，0xFD with reg taintedbyoffset0andcmp reg，0xEFwithregtaintedby offset 1.如果我们有一组有效的输入用于该程序，我们可以在所有相应的执行中观察这两个cmp指令。相反，如果对于一组有效输入，我们在所有输入的DTA结果中得到cmpi =（oi，vi），则vi是偏移oi处的魔术字节的一部分。
应该注意，我们用于检测魔术字节的算法可能会产生误报。如果所有初始有效输入在相同的偏移处共享相同的值，则可能发生这种情况。尽管如此，这仍然有助于生成超出对魔术字节的初始检查的输入，并且探索不同路径的概率降低。为了避免这种情况，我们倾向于从一组多样但有效的输入开始。
| 在魔术字节检测期间，对于给定的cmpi指令，如果相应的值取决于每个字节的多个偏移量，我们不认为这样的偏移量是魔术字节的伪指令。例如，对于给定的cmp指令，如果DTA检测到 | Tji | > 1，我们从魔术字节占位符的任何进一步考虑中排除这种偏移（∈Tji）。这种情况表明相应操作数的值可以从那些偏移εTji处的污染值导出。对多个字节的依赖打破了魔术字节是固定（常量）字节序列的假设。我们将所有这些偏移的集合表示为Oother。 |
3）基本块重量计算：从基于覆盖的模糊测量角度来看，每条可行路径对于遍历都很重要。一个简单的模糊测试策略是花费同等的努力为所有可行路径生成输入。但是，由于存在控制结构，某些路径的可达性可能与其他路径的可达性不同。如果我们有嵌套的控制结构，这种情况就会频繁出现[41]。因此，与其他输入相比，任何运行这种难以触及的代码的输入都应该得到更多奖励。
我们通过为嵌套控制结构中包含的基本块指定更高权重来合并此奖励。由于枚举过程间级别的所有路径都难以缩放，我们在过程内限制我们的分析，即我们计算包含函数内每个基本块的权重。稍后，我们收集并添加由给定输入执行的路径中所有基本块的权重。通过这种策略，我们通过将几个过程内路径分数拼接在一起来模拟过程间路径的分数。
如果我们认为特定基本块的输入到下一个基本块的转换取决于某个概率，我们可以从控制流图（CFG）中导出一个称为马尔可夫过程的概率模型用于输入行为。马尔可夫过程是一个随机过程，其中给定试验的结果仅取决于过程的当前状态[30]。我们将函数的CFG建模为马尔可夫过程，其中每个基本块具有基于其与其他基本块的连接的概率。
7.CONCLUSIONS
本文认为，模糊测试的关键优势在于实现轻量级，可扩展的错误查找技术，并且应用重量级和不可扩展的技术（如基于符号执行的方法）并不是提高覆盖率性能的最终解决方案 - 基于模糊器。在研究了几种现有的通用（黑/灰盒）模糊器之后，包括最先进的AFL模糊器，我们注意到它们往往与应用程序无关，这使得它们在发现根深蒂固的错误方面效率较低。应用程序不可知策略的关键限制是它们无法更快地生成有趣的输入。我们通过模糊化应用程序感知测试过程来解决这个问题。
我们利用应用程序的控制和数据流功能来推断输入的几个有趣属性。控制流功能允许我们对某些路径进行优先级排序和优先级排序，从而使输入生成成为受控过程。我们通过为基本块分配权重并为输入实现权重感知适应性策略来实现这一点。通过使用动态污点分析，我们还监控应用程序的多个数据流功能，使我们能够推断输入的结构属性。例如，这为我们提供了有关输入中的哪些偏移在几个分支条件下使用，哪些值用作分支约束等的信息。我们在反馈循环中使用这些属性来生成新输入。
我们在一个名为VUzzer的开源原型中实现了我们的模糊测试技术，并在几个应用程序上对其进行了评估。我们还将其性能与AFL的性能进行了比较，结果表明，在几乎所有测试案例中，与AFL相比，VUzzer能够发现数量少于一个数量级的错误。这具体表明，通过分析应用行为来推断输入属性是一种可行且可扩展的策略，可以提高模糊性能，并为该领域的未来研究提供有希望的方向。