《Improving Function Coverage with Munch: A Hybrid Fuzzing and Directed Symbolic Execution Approach》

《Improving Function Coverage with Munch: A Hybrid Fuzzing and Directed Symbolic Execution Approach》用一个混合模糊测试和定向符号执行方法Munch改善功能覆盖率

• 问题
• • 基础知识
  • 解决了什么问题？(提高函数覆盖率)
  • 使用了什么方法？
  • 达到了什么效果？
• 翻译
• • 摘要
  • 1 介绍
  • 2 动机
  • 3 研究方法
  • • 3.1 操作模式
    • • 3.1.1 FS Hybrid
      • 3.1.2 SF Hybrid
    • 3.2 Munch的组件
    • • 3.2.1 AFL for fuzzing
      • 3.2.2 KLEE for symbolic execution
      • 3.2.3 Orchestrator
  • 4 评价
  • 5 相关工作
  • 6 总结

问题

基础知识

模糊测试：是一种使种子输入值发生变异的黑盒测试方法，测试用例的修改(突变)依赖于启发式，期望这些启发式能够帮助发现新的程序路径。通常模糊测试无法生成行使程序中所有路径的多样化输入。
符号执行：是一种白盒测试方法，是一种确定性方法，它使用工具动态地收集表示程序分支条件的约束，并解决这些约束，以生成执行程序中不同路径的输入。由于路径爆炸问题和对SMT求解器的依赖，符号执行可能会“卡住”在程序的浅层部分，永远无法到达(并解决)更深层次的分支，因此也可能无法实现较高的路径覆盖率。
SMT（Satisfiability modulo theories）求解器：用于形式化验证
函数覆盖率：如果一个函数(除了main函数)在执行一个程序的所有过程中被另一个(父)函数调用了至少一次，那么它就被称为覆盖了;否则，就称为未覆盖

解决了什么问题？(提高函数覆盖率)

模糊测试和符号执行本身往往不能在程序的所有深度实现很高的功能覆盖率。浅覆盖意味着程序中靠近入口点的部分的高覆盖，而在距离入口点较远的部分的低覆盖，或者在调用图中较深的部分的低覆盖。

符号执行工具往往在有限的时间内实现浅覆盖，因为底层约束求解器(例如，SMT求解器)返回的时间太长。
同样，模糊处理工具也不能覆盖深度定位的函数，这些函数的入口点由难以通过的分支条件保护。

如果没有对所有深度进行适当的覆盖，这两种技术都可能无法发现重要的漏洞。所以需要将模糊处理和符号执行结合起来，以增加函数的覆盖率。

使用了什么方法？

我们的框架Munch以两种方式将模糊处理和符号执行结合起来，以增加函数的覆盖率:
(1)FS Hybrid：使用模糊测试(带有手工种子输入)对程序进行初步探索，然后使用有针对性的符号执行来探索模糊处理未覆盖的函数。
在这个混合策略的变种中，我们在有限的时间内模糊程序，计算由模糊器实现的函数覆盖率，然后，使用定向(或定向)符号执行来达到那些没有被模糊器覆盖的函数。
(2)SF Hybrid：使用符号执行来生成一组功能不同的测试用例，然后使用这些测试用例来模糊程序。
这种混合策略针对的是对于输入的种子不容易获得或生成的程序。
在这个变体中，我们象征性地在有限的时间内执行被测试的程序，在需要的时候提供符号命令行参数、符号标准输入(STDIN)和符号文件输入。为了处理符号执行的浅层覆盖，我们使用符号执行生成的输入(标准参数、STDIN或文件)作为fuzzer的种子输入，作为SF混合技术的第二步。
由于符号执行所实现的覆盖的多样性(虽然很浅)，所生成的测试用例在种子输入中提供了足够的多样性，以便fuzzer在程序中触发不同的(并且，希望是更深入的)行为，而手动生成的种子输入很难触发这些行为。

Munch的组件：
(1)AFL：Munch使用AFL (American Fuzzy Lop)进行模糊测试，一种使用初始测试用例和基因突变来生成新测试用例的工具
(2)KLEE：Munch使用KLEE作为它的符号执行引擎。
(3)Orchestrator：它是协调模糊测试和符号执行引擎工作的中心组件。除了协调任务外，Orchestrator还负责生成在FS和SF操作模式下正确运行所需的统计数据。Orchestrator的功能如下：(1)从程序编译的LLVM位码中提取调用图。(2)按拓扑顺序对函数列表进行排序。(3)启动Munch。(4)将命令行参数转换为STDIN。(5)启动fuzzing (FS模式)或符号执行(SF模式).(6)在FS模式下运行时，读取afl-cov[1]覆盖率信息，计算用于目标符号执行的未覆盖函数列表。(7)如果在SF模式下运行，则读取KLEE测试用例并填充测试用例位置。(8)最后，计算函数覆盖率。

达到了什么效果？

(1)在KLEE中实现了有针对性的搜索功能，可以到达任意函数的入口点。
(2)我们实现了两种混合方法，通过减少符号执行工具发出的查询数量来处理SMT求解器的瓶颈。
(3)首次对一个混合框架在9个开源程序上的有效性进行了实证评估。结果表明，Munch比单独的模糊测试和符号执行获得更高的功能覆盖率，运行时间更短。

原因是我们可以极大地减少对约束求解器的调用数量。通过只关注那些可能导致未覆盖函数的路径，可以减少对SMT求解器的查询数量，以及用于符号执行的时间。

翻译

摘要

模糊测试和符号执行是查找漏洞并生成程序测试用例的流行技术。模糊测试是一种使种子输入值发生变异的黑盒方法，通常无法生成行使程序中所有路径的多样化输入。由于路径爆炸问题和对SMT求解器的依赖，符号执行也可能无法实现较高的路径覆盖率。与单独的模糊处理或符号执行相比，涉及模糊处理和符号执行的混合技术可以实现更好的功能覆盖。在本文中，我们介绍了Munch，这是一个实现基于模糊测试和符号执行的混合技术的开源框架。我们根据经验显示，使用9个大型开源程序，总体而言，与单独执行符号或模糊测试相比，Munch的功能覆盖率更高（深度）。使用基于总分析时间和发给SMT求解器的查询数量的指标，我们还表明Munch在实现更好的功能覆盖方面更有效。

1 介绍

模糊测试和符号执行通常不能达到很高的覆盖率，不仅在源代码、二进制代码或任何中间代码级别，而且在组件级别也是如此。软件的组件是软件的基本构建块，如面向对象编程中的类或函数编程中的函数。因此，组件覆盖率可以定义为在软件测试周期中至少执行一次的程序中组件的数量。对于那些只能通过组件链中许多其他组件才能到达的组件，可以经常观察到低组件覆盖率[6,28]。对于组件可以跨程序重用的情况也是如此，例如，以开放api[12]的形式，或者当它们被不同的团队开发时。组件覆盖率低直观地增加了未覆盖组件中深藏在程序内部的漏洞未被发现的可能性。

发现此类漏洞的自动化方法可以分为两类。黑盒测试方法忽略了被测系统(SUT)的内部工作方式。另一方面，白盒方法考虑程序的底层结构，通过源代码、软件模型或任何其他中间表示，以获得有效的测试策略。实际上，大多数测试方法都可以放在blackbox和whitebox(也称为greybox)之间的光谱上，这取决于SUTs的可用信息。模糊测试[29]是(主要)黑盒测试方法的一个例子。Fuzzing使用和修改用户提供的测试用例，以发现软件中以前未发现的新功能。测试用例的修改(突变)依赖于启发式，期望这些启发式能够帮助发现新的程序路径。由于它的遗忘w.r.t. SUTs实现，模糊可能会错过程序路径，不太可能执行随机变化的输入。这样的程序路径甚至可能涉及到靠近程序入口点的分支，但是无论如何都很难进入。

符号执行(或它的实际方法，例如，协同执行[26]或白盒模糊[15])，白盒方法，是一种确定性方法，它使用工具动态地收集表示程序分支条件的约束，并解决这些约束，以生成执行程序中不同路径的输入。但是，由于对SMT求解器的依赖和路径爆炸[11]的问题，符号执行可能会“卡住”在程序的浅层部分，永远无法到达(并解决)更深层次的分支。

在这篇文章中，我们介绍了一个框架，通过结合模糊和协同执行来增加c程序的所有深度的功能覆盖。我们在C程序中定义函数覆盖率如下:如果一个函数(除了main函数)在执行一个程序的所有过程中被另一个(父)函数调用了至少一次，那么它就被称为覆盖了;否则，就称为未覆盖。我们的技术利用KLEE[9]进行符号执行，AFL[1,2]进行模糊处理。我们用基于最短路径搜索算法(章节3.2.2)的目标搜索策略扩充了KLEE。我们还展示了我们的框架在几个开源程序上的评估结果，以演示我们方法的有效性。

问题。模糊测试和符号执行本身往往不能在程序的所有深度实现高功能覆盖率。浅覆盖意味着程序中靠近入口点的部分的高覆盖，而在距离入口点较远的部分的低覆盖，或者在调用图中较深的部分的低覆盖。符号执行工具往往在有限的时间内实现浅覆盖，因为底层约束求解器(例如，SMT求解器)返回的时间太长。同样，模糊处理工具也不能覆盖深度定位的函数，这些函数的入口点由难以通过的分支条件保护。如果没有对所有深度进行适当的覆盖，这两种技术都可能无法发现重要的漏洞。

解决方案。我们的框架Munch以两种方式将模糊处理和符号执行结合起来，以增加函数的覆盖率:(1)使用模糊处理(带有手工种子输入)对程序进行初步探索，然后使用有针对性的符号执行来探索模糊处理未覆盖的函数。(2)使用符号执行来生成一组功能不同的测试用例，然后使用这些测试用例来模糊程序。我们假设，这两种混合方法都能以较低的成本(时间)实现更高的功能覆盖率，也能实现深度定位的功能。

贡献。(1)针对这方面研究和工具的不足，我们在KLEE中实现了有针对性的搜索功能，以达到(然后，探索)任意函数的入口点。(2)我们实现了两种混合方法，通过减少符号执行工具发出的查询数量来处理SMT求解器的瓶颈。由于使用fuzzer(一种混合方法)的初始探索阶段，符号执行引擎将那些容易到达入口点的函数排除在状态搜索之外，因此可以将更多的时间投入到难以到达的函数上。我们演示了这些方法，并评估了人工生成和真实程序的效率。(3)就我们所知，我们首次对一个混合框架在现实世界(9个开源)程序上的有效性进行了实证评估。我们表明，当运行时间更短时，我们的方法比单独的模糊测试和符号执行获得更高的功能覆盖率，特别是在调用图的深处，这两种简单的方法都导致低覆盖率。原因是我们可以极大地减少对约束求解器的调用数量。(4)最后，据我们所知，我们的框架Munch是唯一一种可用于任何C程序的开箱即用的开源混合测试框架。

2 动机

使用人工生成的C程序，我们首先证明模糊测试和符号执行对于大型程序的函数覆盖是无效的。针对不充分的功能覆盖和对SMT解决程序的依赖，我们证明了需要更有效的方法来达到更深层次的功能。

我们用一个脚本生成了C程序，该脚本将所有生成函数所需的分支因子b和程序调用图的深度d作为输入。这些程序要求用户提供0到bd-1之间的输入。分支因子为2，调用图深度为3的人工程序对应的调用图如图1所示。对于这个项目,一个有效的用户输入0到7(1)23日之间。整个范围的上限和下限之间的整数的有效输入然后逐渐分成两半,每一半范围是一个相应的参数函数,直到一个函数(调用图中的叶节点)达到输入在屏幕上打印。对于我们的计算，我们生成了调用图深度从1到4、分支因子2到4(总共12个程序)的程序。

所有12个人工生成的程序通过模糊(AFL)和符号执行(KLEE)实现的函数覆盖如表1所示。AFL没有达到理想的功能覆盖范围，甚至对于那些不包含任何复杂分支条件、大型输入缓冲区或输入依赖循环的程序也是如此。使用KLEE，功能覆盖率总是100%。然而，为了检查新状态的有效性，或者为有效路径[9]生成测试用例，我们还需要考虑KLEE发出的SMT求解器查询的数量。从表1的第8列可以看出，KLEE发出的求解器查询的数量远远高于相应程序中不同分支的数量。FS代表Fuzzing+符号执行，这是一种简单的混合技术，首先在有限的时间内对程序进行模糊处理，然后使用符号执行来处理那些在模糊处理期间没有涉及到的函数。我们将在第3节和第4节解释这一技术以及通过人工生成程序所取得的相应改进。KLEE在这里发出的查询数量非常多，这表明存在瓶颈，可能会增加分析时间方面的成本。事实上，我们将在4.2节中更详细地看到，在复杂的分支条件、循环和外部调用自然比人工程序更常见的情况下，这种趋势对实际程序的影响更严重。

看看模糊测试和符号执行的性能，我们声明这两种技术本身在有效地实现高功能覆盖率(即总体分析时间)方面是不够的。模糊不能产生足够的输入多样性来覆盖程序中的所有函数，符号执行在SMT求解器中花费太多时间。为了处理模糊测试和符号执行的这些限制，我们现在提出一种混合方法，以有效和高效的方式在程序的所有深度实现高功能覆盖。

3 研究方法

Munch是一个自适应框架，可以在两种混合模式下运行。在本节中，我们首先对这两种模式进行高级描述，然后给出Munch实现这些高级步骤的主要组件的一些低级细节。

3.1 操作模式

3.1.1 FS Hybrid

FS代表Fuzzing+符号执行，按照这个顺序。在这个混合策略的变种中，我们在有限的时间内模糊程序，计算由模糊器实现的函数覆盖率，然后，使用定向(或定向)符号执行来达到那些没有被模糊器覆盖的函数。当一个程序在有限的时间内被模糊化时，这些函数将被覆盖，在理想情况下，对于种子输入的大多数突变来说，这些函数很容易到达(在程序的调用图中)。如3.2.2节所述，使用符号执行引擎中的自定义路径搜索策略——声纳搜索，FS策略消除了模糊处理中已经覆盖的那些函数的路径，从而减轻了约束求解器的一些负担。

读者可能已经注意到，FS hybrid要求用户为fuzzing的第一步提供种子输入。因此，FS hybrid在程序的示例输入可用或可以快速(手动)生成的情况下特别有用，特别是对于基于文件的输入。

3.1.2 SF Hybrid

对于种子输入不容易获得或生成的程序，Munch提供了混合灰盒模糊的第二种变体，称为SF混合策略。SF代表符号执行+Fuzzing，按照这个顺序。在这个变体中，我们象征性地在有限的时间内执行被测试的程序，在需要的时候提供符号命令行参数、符号标准输入(STDIN)和符号文件输入。在第一轮符号执行中，我们将讨论由不同输入调用的那些函数。但是，由于约束求解器的瓶颈，符号执行只能实现较浅的覆盖。为了处理符号执行的浅层覆盖，我们使用符号执行生成的输入(标准参数、STDIN或文件)作为fuzzer的种子输入，作为SF混合技术的第二步。由于符号执行所实现的覆盖的多样性(虽然很浅)，所生成的测试用例在种子输入中提供了足够的多样性，以便fuzzer在程序中触发不同的(并且，希望是更深入的)行为，而手动生成的种子输入很难触发这些行为。

3.2 Munch的组件

如3.1节所述，为了自适应地实现这两种操作模式，使用了模糊测试和符号执行的共同核心，并由我们的Orchestrator组件管理整个操作。我们现在在下面描述这三个组件

3.2.1 AFL for fuzzing

为了模糊程序，Munch使用AFL (American Fuzzy Lop)[2]，一种使用初始测试用例和基因突变来生成新测试用例的工具。AFL与目标二进制文件一起工作，这些二进制文件可以直接接受来自STDIN或文件的输入。AFL直接从编配器接收种子输入(第3.2.3节)，编配器还负责调整程序，以便在某些特殊情况下将命令行参数转换为STDIN。然后，我们的框架在特定时间内模糊了程序二进制代码，我们稍后将在第4节中详细说明。

3.2.2 KLEE for symbolic execution

Munch适应和使用KLEE[9]作为它的符号执行引擎。对于从符号执行开始的SF操作模式，编配器使用KLEE的路径搜索策略调用KLEE，该策略为先[9]探索新的未见路径而优化。但是对于Munch的FS操作模式，我们需要一个针对任意函数入口点的有针对性的搜索策略。由于KLEE的原始实现没有提供这样的策略，我们将其扩展为一个搜索策略，该搜索策略优先考虑到目标函数的最短路径。

过去已经有人提出了针对符号执行的原型，尽管没有完整的实现或针对不同语言的原型。我们的实现受到了这些工作的启发，但我们修改了它们，使其以程序的控制流图和调用图作为输入，而不只是原始源代码，以计算最短距离。另外，我们的实现使用KLEE的原生搜索启发式作为一个嵌套搜索器，方法如下:当一个状态达到目标函数后，所有连续的状态都使用KLEE的原生搜索启发式进行搜索。在到达目标函数的过程中，所有不能到达目标的状态都会立即终止，从而减少了KLEE要探索的路径数量。完整的搜索策略，带有嵌套的KLEE启发式搜索器，在我们的KLEE fork2中被命名为声纳搜索(因为，像声纳波一样，我们以自下而上的方式不断计算调用图中的距离，并更新搜索器)。

3.2.3 Orchestrator

协调fuzzer和符号执行引擎工作的中心组件是协调器。除了此协调任务外，Orchestrator还负责生成在两种操作模式下正确运行所需的有用统计数据。具体来说，Orchestrator的功能如下
(1)从程序编译的LLVM位码中提取调用图。
(2)按拓扑顺序对函数列表进行排序。对所有函数列表进行拓扑排序的原因是，如果声纳搜索到达一个边界节点，那么调用图中这个边界节点级别以下的其他函数很可能会在相同的FS混合模式运行中被覆盖。边界节点是指在其入口点之前具有相对复杂的保护条件，并且在其下方附有密集的子(调用)图的函数节点。边界节点的例子是一个函数，它解析传入的HTTP数据包并检查数据包报头是否与协议一致，内容长度字段是否传达了关于有效负载的真实信息等等。只有当传入的数据包报头满足一个复杂的约束系统(保护条件)定义的有效性标准时，解析函数才会将有效负载发送到其他处理函数(例如从后端获取查询结果)。
(3)通过读取一个JSON格式的本地(被测程序)配置文件来启动Munch。操作模式取决于测试用例位置是否包含任何文本文件(FS)。
(4)如果程序接受命令行参数，则在编译之前对源代码进行补丁，以将命令行参数转换为STDIN。这是通过对主函数进行简单的包装来完成的。
(5)启动fuzzing (FS模式)或符号执行(SF模式)
(6)在FS模式下运行时，读取afl-cov[1]覆盖率信息，计算用于目标符号执行的未覆盖函数列表。
(7)如果在SF模式下运行，则读取KLEE测试用例并填充测试用例位置。
(8)通过用户定义的每个函数(FS模式)或模糊(SF模式)的时间限制来启动符号执行(每个未覆盖的函数一次)。
(9)最后，计算函数覆盖率。

4 评价

5 相关工作

6 总结

在本文中，我们开发和评估Munch，一个功能覆盖的混合框架，基于模糊测试和符号执行。该自适应框架工作在两种模式的模糊，然后是目标符号执行和符号执行产生不同的种子输入的模糊。在符号执行中使用我们的目标搜索实现，通过只关注那些可能导致未覆盖函数的路径，可以减少对SMT求解器的查询数量，以及用于符号执行的时间。

我们演示了Munch在12个人工生成程序上的效率。我们还对9个广泛使用的开源程序的有效性和效率进行了评估，并将其与纯模糊测试和符号执行进行了比较。我们发现，如4.2节所示，我们的混合方法成功地在程序调用图的所有深度上实现了比模糊处理或符号执行更大的函数覆盖，而花费的时间和SMT查询不到一半。从这些结果来看，我们可以假设，在高度组合的程序中具有更高的函数覆盖率，我们的混合技术更有可能发现模糊或符号执行单独使用时可能遗漏的漏洞。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！