Probabilistic Path Prioritization for Hybrid Fuzzing

Probabilistic Path Prioritization for Hybrid Fuzzing

Abstract

混合模糊测试结合了模糊测试和符号执行，已成为软件漏洞检测的先进技术。基于对模糊和符号执行本质上是互补的观察，最先进的混合模糊测试系统部署了demand launch和optimal switch策略。虽然这些想法听起来很有意思，但由于过于简单的假设，我们指出了它们中的几个基本限制。然后，我们提出了一种新颖的discriminative dispatch策略，以更好地利用符号执行的能力。我们设计了一种新的基于Monte Carlo的概率路径优先级模型，用于量化每条路径的难度，并优先考虑它们的符号执行。该模型将模糊测试视为随机抽样过程。它根据采样信息计算每个路径的概率。最后，我们的模型优先考虑并指定最困难的路径来符号执行。我们实现了原型系统DigFuzz，并使用两个有代表性的数据集评估我们的系统。结果表明，在各个主要方面，DigFuzz中的符号执行性能优于最先进的混合模糊测试系统。特别是，DigFuzz中的符号执行有助于发现更多的漏洞（12对5），并在CQE数据集上产生比在Driller中执行的更多代码覆盖（18.9％对3.8％）。

1. Introduction

软件漏洞被认为是对网络空间最严重的威胁之一。因此，发现一个软件中的漏洞至关重要[12]，[16]，[25]，[27]，[32]。最近，混合模糊测试，模糊测试和符号执行的组合，在漏洞发现中变得越来越流行[5]，[29]，[31]，[39]，[42]，[46]。由于模糊测试和符号执行本质上是互补的，因此将它们结合起来可以潜在地利用它们的独特优势并减轻弱点。更具体地说，模糊测试是精通探索包含一般分支（具有大的满足值空间的分支，比如x>100）的路径，但是不能探索包含特定分支的路径（具有非常窄的满足值空间的分支,比如x=2）[27]。相反，符号执行能够生成具体的输入，确保程序沿着特定的执行路径执行，但它会遇到路径爆炸问题[9]。在混合方案中，模糊测试由于高吞吐量通常承担路径探索的大多数任务，而符号执行辅助模糊测试探索低概率的路径、并且生成满足特定分支的输入。通过这种方式，可以减轻分支符号执行中的路径爆炸问题，因为符号执行仅负责探索可能阻止模糊测试的低概率路径。

关键的研究问题是如何结合模糊测试和符号执行以实现最佳的整体性能。 Driller [39]和hybrid concolic testing[29]采取需求启动策略：模糊测试首先开始，并且只有当模糊测试在一段时间内无法取得任何进展（即stuck）时才会启动符号执行。最近的一项工作[42]提出了一种最佳转换策略：它量化通过模糊测试和符号执行来探索每条路径的成本，并选择更经济的方法来探索这条路径。

我们使用DARPA CQE数据集[13]和LAVA-m数据集[15]评估了需求启动和最佳转换策略，并发现尽管这些策略听起来很有趣，但由于不太现实或过度简化的假设，它们都没有充分发挥作用。

对于需求启动策略，首先，模糊器的卡住状态不是启动符号执行的良好指标。模糊测试正在取得进展并不一定意味着不需要进行符号执行。模糊器仍然可以探索新代码，即使它已经被许多特定分支阻塞，而因为模糊器未处于卡住状态，因此符号执行器被迫空闲。其次，该策略无法识别阻止模糊测试的特定路径。一旦模糊器卡住，需求启动策略就会将模糊器保留的所有种子提供给符号执行，用于探索所有错过路径。然后，这种大量错过的路径会让执符号执行不堪重负，并且可能会在很长一段时间后为特定路径生成有效的输入。到那时，模糊器可能已经生成了一个良好的输入来遍历该特定路径，从而使整个符号执行变得毫无用处。

同样，尽管最佳切换策略旨在基于可靠的数学模型（即，具有成本的马尔可夫决策过程，简称MDPC）做出最优决策，但是量化每条路径的模糊测试和符号执行的成本是非常重要的。例如，为了量化特定路径的独立执行成本，MDPC需要收集已经很昂贵的路径约束。结果，MDPC的总吞吐量大大降低。此外，在量化模糊测试的成本时，MDPC假设所有测试用例均匀分布。这种假设过于简单，因为许多最先进的模糊测试技术[4]，[12]，[16]是自适应和进化的。最后，即使可以准确地估计模糊测试和符号执行的成本，但要将它们标准化以进行统一比较是具有挑战性的，因为这两种成本是通过具有不同度量的技术来估计的。

基于这些观察，我们在构建混合模糊测试系统时争论以下设计原则：1）由于符号执行比模糊测试慢几个数量级，我们应该只让它解决最难的问题，并让模糊测试采取路径探索的多数任务; 2）由于高通量对于模糊测试至关重要，因此任何额外的分析都必须是轻量级的，以避免对模糊测试的性能产生不利影响。

在本文中，我们提出了一种判别性调度策略，以更好地结合模糊测试和符号执行。也就是说，我们优先考虑路径，以便符号执行仅用于模糊测试最难以突破的选择性路径。因此，可以更好地利用符号执行的能力。然后，这种歧视性调度策略的关键是量化每条路径的难度级别的轻量级方法。先前的工作通过执行昂贵的符号执行来解决这个问题[18]，因此不适合我们的目的。

特别地，我们提出了一种新的基于蒙特卡罗的概率路径优先级（$MCP^3$）模型，以有效的方式量化每个路径的难度。更具体地说，我们通过随机输入可能遍历此路径的概率来量化路径的难度。为了计算这个概率，我们使用蒙特卡罗方法[35]。核心思想是将模糊测试视为随机抽样过程，将随机执行视为整个程序空间的样本，然后根据抽样信息计算每个路径的概率。

我们已经实现了一个名为DigFuzz的原型系统。它利用流行的模糊器，American Fuzzy Lop(AFL)[47]作为模糊组件，并在开源符号执行引擎Angr之上构建了一个符号执行器[38]。我们使用来自ARPA Cyber Grand Challenge [13]和LAVA数据集[15]的CQE评估来评估DigFuzz的有效性。评估结果表明，与最先进的混合系统相比，DigFuzz中的复杂执行对代码覆盖率的增加和发现的漏洞数量的增加做出了更大的贡献。更具体地说，DigFuzz中的执行执行有助于发现更多的漏洞（12对5），并在CQE数据集上产生更多的代码覆盖率（18.9％对3.8％），而不是在Driller [39]中执行。

贡献。该文件的贡献概述如下：

我们对两种最先进的混合模糊测试策略（需求启动和最佳切换）进行独立评估，并发现以前未报告过的几个重要限制。
我们提出了一种新颖的判别式调度策略，作为构建混合模糊测试系统的更好方法。它遵循两个设计原则：1）让模糊测试进行路径探索的大多数任务，并且只分配最困难的路径进行符号执行; 2）路径困难的量化必须是轻量级的。为了实现这两个原则，我们设计了一个基于蒙特卡罗的概率路径优先模型。
我们实施原型系统DigFuzz，并使用DARPA CQE数据集和LAVA数据集评估其有效性。我们的实验表明DigFuzz在更多发现的漏洞和更高的代码覆盖率方面优于最先进的混合系统Driller和MDPC。

2. Background And Motivation

Fuzzing [30]和concoic execution [9]是软件测试和漏洞检测的两种代表性技术。由于观察到模糊和执行的执行在本质上可以相互补充，已经提出了一系列技术[5]，[29]，[31]，[39]，[42]将它们组合在一起并创建混合模糊系统。通常，这些混合模糊测试系统分为两类：“需求启动”和“最佳切换”。

A. Demand Launch

最先进的混合方案，如Driller [39]和混合动力系统测试[29]部署了“需求启动”战略。在Driller [39]中，由于模糊器在一段时间内无法取得任何进展，因此该模板执行器仍处于空闲状态。然后，它依次处理来自模糊器的所有保留输入，以生成可能有助于模糊器的输入，并进一步导致新的代码覆盖。类似地，混合分析测试[29]通过混合测试获得了对程序状态空间的深入和广泛的探索。它通过利用随机测试的能力快速到达程序状态，然后通过执行执行彻底探索邻居状态。

在一个问题上，必须有两个假设才能使“需求启动”战略按预期发挥作用：（1）非卡住状态的模糊器意味着不需要执行。只有当模糊器卡住时，混合系统才应该开始执行。（2）卡住状态表明模糊器在可接受的时间内无法在发现新的代码覆盖范围方面取得任何进展。此外，具有执行力的执行能够找到并解决阻塞模糊器的难以解决的条件检查，以便模糊测试可以继续发现新的覆盖范围。

观察。为了评估需求启动战略的表现，我们仔细研究了Driller如何在DARPA Cyber Grand Challenge（CGC）的12个小时中工作12小时，并找到五个有趣且令人惊讶的事实。（1）Driller仅在118个二进制文件中的49个中调用了concoic执行，这意味着模糊器只会卡在这49个二进制文件上。这一事实与Driller [40]的论文中报道的数字（42）相当。（2）对于事实1中的49个二进制文件，我们统计计算卡住时间段，卡住时间段的分布如图1所示。我们可以观察到超过85％的卡住时间段低于100秒。（3）平均而言，为一个具体的输入完成动态符号执行需要1654秒。（4）在测试的12小时内，由模糊执行器处理的只有7.1％（23915中的1709个）由模糊器保留的输入。图2显示了由于执行的输入数量和模糊测试保留的输入数量之间的巨大差距。（5）Driller中的模糊器确实可以从事实1的49个二进制文件中的13个二进制文件中获得有关执行（从至少一个由concolic执行产生的输入）的帮助，在1709次执行的系统执行后总共输入51个输入。

限制。上述结果表明需求启动战略的两个主要局限。

首先，模糊器的卡住状态不是判断是否需要执行模板的好指标。根据事实1，模糊器仅停留在49个二进制文件上，这意味着其他77个二进制文件永远不会启动模仿执行。对这77个二进制文件的源代码进行手动调查表明，它们都包含可以阻止模糊测试的特定分支。进一步结合事实2，我们可以看到处于卡住状态的模糊器并不一定意味着它实际上需要执行，因为大多数卡住状态非常短（85％的卡住状态不到100秒）。这些事实打破了上述假设1。

其次，“需求启动”策略无法识别阻止模糊测试的特定路径，从而导致非常低效的执行。一方面，平均执行平均需要1654秒来处理一个输入（事实3）。另一方面，模糊器通常比常规执行可以保留更多的输入（事实4）。结果，对应于阻止模糊测试的特定分支的输入（即，可能导致执行到目标位置的输入）仅具有非常小的机会被通过结构执行来拾取和处理。因此，上述假设2在实践中并不真正成立。事实5可以进一步证实这一结论，尽管它是在49个二进制文件上发布的，但是对于仅仅13个二进制文件的执行可以帮助模糊测试。此外，在1709次符号执行之后，模糊执行器仅导入了51个来自符号执行的输入，表明由符号执行而产生的输入质量非常低。

B. Optimal Switch

“最佳切换”策略旨在基于数学模型（即，具有成本的马尔可夫决策过程，简称MDPC）对使用哪种方法来探索给定的执行路径做出最佳决策。为了获得最佳性能，MDPC始终选择成本较低的方法来探索每条路径。为了使这一战略运作良好，必须遵循以下假设：

（1）可以准确地估计通过模糊和经验执行来探索路径的成本。（2）成本估算的开销可以忽略不计。（3）用于做出最优决策的算法是轻量级的。

观察。为了评估最佳切换的性能，我们评估了MDPC如何在CQE数据集中对118个二进制文件工作12小时，并有3个有趣的观察结果。

（1）表I显示了模糊测试，符号执行和MDPC中的最佳决策之间的吞吐量差距。我们可以观察到最优决策非常昂贵，比模糊测试大几千倍。（2）由于MDPC在探索每条路径之前做出最佳决策，因此整体分析吞吐量显着降低，从纯模糊测试中每秒执行417次到MDPC中每秒执行2.6次。（3）由于吞吐量降低的影响，MDPC仅在29个二进制文件中发现漏洞，而纯模糊测试可以发现67个二进制文件中的漏洞。

由于MDPC在探索每条路径之前做出了最佳决策，昂贵的最优决策都会带走模糊测量的高吞吐量。作为优化，我们可以将最佳决策移出，使其与模糊测试并行工作，并构建并发MDPC。也就是说，并发MDPC中的最优决策不会干扰模糊测试的工作进度，它只是从模糊测试中收集覆盖率统计数据来计算成本。从这个并发的MDPC的评估，我们有另一个观察。

（4）几乎所有错过的路径都决定在模糊测试开始后的几秒钟内通过模糊执行进行探索。通过检查覆盖率统计，我们观察到模糊器能够在几秒钟内生成数百个测试用例，这导致基于MDPC中的算法通过模糊测试来探索错过路径的高成本。相反，即使我们将最高的求解成本（定义为[42]的50）分配给每个路径约束，也可以降低执行成本。

限制：上述观察结果表明，最佳转换策略的关键限制是估计通过模糊测试和符号执行来探索路径的成本是重量级且不准确的，这掩盖了制定最优解决方案的好处。

首先，估计分配执行的成本依赖于收集路径约束并确定这些约束的解决成本。由于收集路径约束需要将程序语句转换为符号表达式，因此这种解释也是重量级的，特别是对于具有长路径的程序。此外，MDPC设计了一种贪婪算法以实现最佳决策。该算法依赖于路径敏感的程序分析。对于具有大状态的程序，路径敏感分析也是重量级的。

其次，准确估计通过模糊测试和符号执行探索给定路径的成本是非常重要的。 MDPC根据平等的复杂性估算解决成本，并根据覆盖统计估计随机测试的成本。这些估计涉及模糊测试的运行时吞吐量，约束求解器的性能以及符号执行引擎，并且它们中的每一个本质上是不同的程序分析技术。因此，定义统一度量以评估不同技术的成本具有挑战性。

3. PROBABILISTIC PATH PRIORITIZATION GUIDED BY MONTE-CARLO

为了解决当前混合模糊测试系统的上述局限性，我们提出了一种新颖的判别调度策略，以更好地结合模糊和执行。

A. Key Challenge

如上所述，我们策略的关键挑战是以轻量级方式量化遍历模糊器路径的难度。有一些解决方案可以使用昂贵的程序分析来量化路径的难度，例如值分析[45]和概率符号执行[5]。然而，这些技术并没有解决我们的问题：如果我们已经执行了重量级分析来量化路径的难度，我们也可以只解决路径约束并生成遍历路径的输入。最近的一项研究[42]提出了一种理论框架，用于优化的结构测试。它定义了基于程序路径概率和约束求解成本的最优策略，然后将问题简化为带有成本的马尔可夫决策过程（简称MDPC）。本研究与我们的工作有着相似的问题范围。然而，马尔可夫决策过程本身对于具有大状态空间的程序来说是重量级的。此外，模糊测试和符号执行的成本对于评估和标准化以进行比较是具有挑战性的。

B. Monte Carlo Based Probabilistic Path Prioritization Model

在这项研究中，我们提出了一种新的基于蒙特卡罗的概率路径优先级模型（简称$MCP^3$）来应对这些挑战。为了轻量化，我们的模型应用蒙特卡罗方法来计算通过模糊测试探索路径的概率。要使蒙特卡罗方法有效运作，需要满足两个要求：1）。对搜索空间的抽样必须是随机的; 2）。需要大量随机抽样才能使估计具有统计意义。由于模糊器随机生成测试程序的输入，我们的见解是将这些输入的执行视为整个程序状态空间的随机样本，因此满足第一个要求。此外，由于模糊测试具有非常高的吞吐量，因此也可以满足第二个要求。因此，通过将模糊测试作为抽样过程，我们可以通过覆盖统计以轻量级方式统计估计概率。

根据蒙特卡罗方法，我们可以通过统计计算遍历此路径的执行与所有执行的比率来简单地估计路径的概率。然而，这种直观的方法并不实用，因为保持路径覆盖是一项具有挑战性和重要性的任务。考虑到这一点，大多数当前的模糊测试技术采用了轻量级覆盖度量，例如块覆盖和分支覆盖。对于这一挑战，我们将执行路径视为连续分支的马尔可夫链，受到先前技术的启发[4]。然后，可以基于路径内所有分支的概率来计算路径的概率。

Probability for each branch:

Probability for each path: 路径上所以分支概率乘积。

C. $MCP^3$ based Execution Tree

在我们的判别式调度策略中，关键思想是从模糊测试执行的运行时信息推断并优先考虑符号执行的路径。为此，我们构建并维护一个基于MCP3的执行树，其定义如下： 定义1.基于$M C P^3$的执行树是有向树T = (V，E，α)，其中：

顶点集合V中的每个元素v对应于执行期间程序跟踪中的唯一基本块;
边集合E⊆V×V中的每个元素e对应于两个顶点v和w之间的控制流依赖性，其中v，w∈V。如果一个顶点包含条件检查，则它可以具有两个输出边缘;
标记函数α: E→Σ将边与概率标签相关联，其中每个标签指示模糊器通过分支的概率。

4. Design and Implementation

A. System Overview

图3显示了DigFuzz的概述。它由三个主要部分组成：1）模糊器; 2）$M C P^3$模型; 3）符号执行器。

我们的系统利用流行的现成模糊器，American Fuzzy Lop（AFL）[47]作为模糊测试组件，并在angr [38]之上构建了一个符号执行器，这是一个开源符号执行引擎，与Driller相同[39]。

DigFuzz中最重要的组件是$MCP^3$模型。该组件执行执行采样，构造基于$ MCP^3$的执行树，基于概率计算对路径进行优先级排序，并最终将优先路径馈送到共同执行器。

DigFuzz通过对初始种子输入进行模糊测试来开始测试。只要输入由模糊器生成，$M C P^3$模型就会执行执行采样以收集覆盖率统计信息，这些统计信息指示采样期间每个分支覆盖的次数。同时，它还通过跟踪分析构建基于$M C P^ 3$的执行树，并使用从覆盖统计计算的概率标记树的所有分支。一旦构造了树并且路径用概率标记，则$M C P^ 3$模型优先考虑树中的所有遗漏路径，并识别具有最低概率执行的路径。

由于为了简化路径约束，符号执行同时执行具体值和符号值的程序，一旦遗漏路径被优先化，$M C P^ 3$模型还将识别可以指导符号执行到达错过路径的相应输入。也就是说，通过将输入作为具体值，符号执行器可以沿着遗漏路径的前缀执行程序，生成并收集符号路径约束。当到达遗漏分支时，它可以通过将路径前缀的约束与该错过分支的条件相结合来生成错过路径的约束。最后，concolic executor通过解决路径约束生成错过路径的输入，并将生成的输入反馈给模糊器。同时，它还使用在符号执行期间探索的路径更新执行树。通过利用来自符号执行的新输入，模糊器将能够更深入地移动，扩展代码覆盖范围并更新执行树。

总之，DigFuzz迭代工作。在每次迭代中，$MCP^3$模型通过对模糊器保留的所有输入的跟踪分析来更新执行树。然后，该模型用其概率标记每个分支，该概率是通过执行样本的覆盖率统计来计算的。之后，$M C P^ 3$模型优先考虑所有遗漏路径，并选择具有最低概率执行概率的路径。符号执行器将为跟踪中的错过分支生成输入，将生成的输入返回到模糊器，并使用在执行过程中探索的路径更新执行树。完成这些步骤后，DigFuzz将进入另一个迭代。

B. Execution Sampling

DigFuzz需要随机抽样来使用蒙特卡罗方法计算概率[35]。基于观察到模糊性质随机产生输入，我们将模糊过程视为整个程序空间的随机抽样过程。由于模糊测试的高吞吐量，生成的样本数量将很快变得足够大，具有统计意义，这由三个规则定义[43]，其中0到3 / n的间隔是95％置信区间。样本数大于30。

在此观察之后，我们提出算法1来执行采样。该算法接受三个输入并在HashMap中生成coverage统计信息。三个输入是：1）目标二进制P; 2）fuzzer Fuzzer; 3）存储在$Set_{inputs}$中的初始种子。给定三个输入，算法在模糊测试期间迭代地执行采样。 Fuzzer将P和$Set_{inputs}$作为$Set_{NewInputs}$（Ln.7）生成新输入。然后，对于NewInputs中的每个输入，我们收集由P和输入（Ln.9）确定的路径内的每个分支的覆盖统计信息，并进一步更新存储在$HashMap_{CovStat}$（Ln.11和12）中的现有覆盖统计。最后，算法将$Set_{NewInputs}$合并到$Set_{inputs}$（Ln.15）并开始新的迭代。

C. Execution Tree Construction

如图3所示，DigFuzz使用来自模糊器的运行时信息生成基于MCP3的执行树。

算法2演示了树构建过程。该算法采用三个输入，目标二进制C F G的控制流图，由模糊器$Set_{inputs}$保留的输入和覆盖统计$HashMap_{CovStat}$，它也是算法1的输出。输出是基于$MCP^3$的执行树ExecTree。算法主要有两个步骤。第一步是对Setinputs中的每个输入执行跟踪分析，以提取相应的跟踪，然后将跟踪合并到ExecTree（Ln.6到11）。第二步是计算执行树中每个分支的概率（Ln.12到16）。为了实现这一点，对于ExecTree中的每个分支，我们通过检查C F G（Ln.13）来提取其邻居分支brj（bri和brj共享包含条件检查的相同的前任块）。然后，该算法利用等式1来计算bri的概率（Ln.14）。之后，算法用执行树的ExecTree标记计算出的概率（Ln.15）并输出新标记的ExecTree。

为了避免执行树中潜在的路径爆炸问题，我们只对由模糊测试保留的种子输入执行跟踪分析。模糊器通常将那些具有新代码覆盖的突变输入视为进一步突变的种子。对这些保留种子的追踪是模拟由模糊测试探索的计划状态的有希望的方法。对于沿执行轨迹的每个分支，每当相对分支未被模糊覆盖时，则识别出错过的路径，其指的是与未覆盖的分支合并的轨迹的前缀。换句话说，执行树不包括未覆盖的分支，其中相反的分支尚未被覆盖。

为了简化表示，我们提供了一个运行示例，它简化了CQE数据集[13]中的程序，代码片如图4所示。漏洞由特定字符串保护，很难进行模糊检测。图5示出了用于图4中的运行示例的基于M C P 3的执行树。每个节点表示基本块。每条边指的是用概率标记的分支。我们可以观察到标记为红色的树中有两条迹线（t1 =⟨b1，b2，b6，b12，b13，b7，b9，b11⟩和t2 =⟨b1，b3，b4，b12，b14⟩）蓝色。

D. Probabilistic Path Prioritization

然后，我们根据概率确定路径的优先级。如等式2所示，路径被视为马尔可夫链，并且其概率是基于路径内所有分支的概率计算的。路径可以表示为覆盖分支的序列，并且每个分支用其概率标记，该概率指示随机输入可以满足条件的可能性。因此，我们利用马尔可夫链模型将路径的概率视为转换概率序列。

详细算法在算法3中给出。它将来自算法2的基于MCP3的执行树ExecTree作为输入并输出SetProb，一组遗漏路径及其概率。 DigFuzz将根据SetProb进一步优先考虑这些错过的路径，并将具有最低概率的路径馈送到具有执行力的状态。该算法从执行树遍历开始。对于ExecTree中每条迹线上的每个分支，它首先提取邻居brj（Ln.5），然后收集沿给定迹线遗漏的遗漏路径（Ln.6）。然后，该算法通过调用实现等式2的CalP athP rob（）来计算错过的概率，并将该信息存储在SetProb中。最终，该算法产生SetProb，这是一组具有每条迹线概率的遗漏路径。

在我们得到SetProb之后，我们将按照概率的降序排列错过路径的优先级，并确定具有最低概率执行概率的路径。由于concolic执行器将具体输入作为执行基于跟踪的符号执行的具体值，我们将识别一个输入，在该输入上执行能够将concoic executor引导到优先级错过的路径。

以图4中的程序为例。在图5中，错过的分支显示为虚线。在构造并正确标记执行树之后，使用算法3来获得遗漏路径并计算这些路径的概率。我们可以观察到总共有4条错过的路径分别表示为P1，P2，P3和P4。通过调用CalPathProb（）函数，计算这些错过路径的概率，如图所示，最低的路径为P1。为了将concoic执行器引导到P1，DigFuzz将选择通向轨迹⟨b1，b2，b6，b12，b13，b7，b9，b11⟩的输入并将此输入分配为concolic执行的具体值，因为此跟踪与错过的路径P1共享相同的路径前缀，⟨b1，b2，b6，b12，b13，b7，b9⟩。

6. Discussion

A. Threats to Validity

我们的实验结果基于论文中提供的有限数据集。已经努力在实际程序上评估DigFuzz，但Angr [38]无法在遇到不受支持的系统调用时象征性地执行程序。因此，结果可能无法完全代表现实世界的节目。必须对这些方案进行评估，以便就拟议技术在实践中的有效性得出结论。我们将把现实世界的计划评估作为我们未来的工作。

B. Limitations

首先，虽然DigFuzz中的“区别性调度”被设计为轻量级方法，但它仍然会产生一些运行时和内存消耗开销，包括收集模糊测试的运行时信息和构造执行树。但是，根据我们的评估，我们可以看到模糊器的吞吐量降低可以忽略不计。此外，由于树中的每个节点仅携带非常有限的信息，因此执行树的总存储器消耗是非常易于管理的。

其次，由于DigFuzz仅估计模糊探测器的路径难度，但没有考虑约束求解的复杂性，因此从拾取路径收集的约束可能无法解决，这可能导致浪费整个执行循环。此外，可能导致漏洞的最有希望的路径也可能不是DigFuzz选择的最难的路径。这两个限制是由于我们找到正确的探索路径的模型。我们考虑将它们解决为未来的工作。

模糊测试和符号执行是程序测试的两种主流技术。许多先前的努力已经做出改进[3]，[27]，[33]，[36]。 BuzzFuzz [17]利用动态污染来识别由可疑指令处理的输入字节。 Dowser [20]采用逆向工程技术来识别与可疑功能有关的输入字段。 Vuzzer [34]利用控制和数据流功能来准确地确定改变这些输入的位置和方式。 Skyfire [40]利用大量现有样本中的知识，为模糊测试程序生成分布均匀的种子输入。 Angora [12]旨在通过解决路径约束来增加分支覆盖，而无需执行符号。 T-Fuzz [32]首先允许模糊器通过删除模糊检查器无法绕过的健全性检查来处理转换后的程序。作为辅助后4p0处理步骤，T-Fuzz利用基于符号执行的方法来过滤误报。 CollAFL [16]是一种覆盖敏感的模糊测试解决方案，它通过提供更准确的覆盖信息来减轻路径冲突。通过提供更准确的覆盖信息进行碰撞。 fuzz2in0g策略。 Veritesting [1]解决了路径爆炸fuzz2in0g策略。 Veritesting [1]解决了动态sy0mbolic执行的路径爆炸效应。 Mayhem [10]提出结合在线和离线符号执行来处理耗尽内存的问题。 DigFuzz的主要贡献是提出一种更有效的策略，将模糊测试与经典执行结合起来。因此，模糊测试和执行模式的进步超出了我们的范围。

Hybrid fuzzing system。大多数混合模糊测试系统遵循观察来增加模糊选择性符号执行[29]，[39]，[41]。 Driller和混合动力系统测试均采用“需求启动”策略。相反，DigFuzz设计了一种新颖的“辨别调度”策略，以更好地利用具有执行力的执行能力。 TaintScope [41]部署动态污点分析以识别校验和检查点，然后应用符号执行来生成满足校验和的输入。 TaintScope专门用于处理校验和，DigFuzz具有更广泛的范围。更重要的是，DigFuzz采用蒙特卡罗模型来估计概率并优先考虑路径，这比动态污点分析更轻量级。

MDPC [42]提出了一种理论框架，用于最佳的符号测试。它基于程序路径的概率和约束求解的成本来定义最优策略，这与我们识别路径概率的想法类似。与使用重量级技术来计算模糊测试和符号执行成本的MDPC [42]相比，我们的模型使用覆盖率统计来计算概率，这更加轻巧和实用。

QSYM [46]使用动态二进制转换将符号仿真与本机执行集成在一起。它还减轻了传统的严格健全性要求，减轻了传统的严格健全性要求，使其可扩展到现实世界的程序。主要重点是使其可以扩展到真实世界的程序。主要重点是使其可以扩展到真实世界的程序。有选择地只派遣最难的工作的主要焦点。

另一种类型的混合模糊测试系统将符号执行视为输入生成或路径选择的指南。 Pak [31]提出了一种混合模糊测试系统，用于应用符号执行来收集路径约束，然后是系统符号执行来收集路径约束，然后是系统执行以将概率分配给程序路径，然后采用这些概率来指导路径探索。起毛。

符号执行中的路径优先级。路径优先化有望减轻动态符号执行中的路径爆炸问题。代表性研究包括启发式技术和声音程序分析技术[9]。这些启发式方法包括使用控制流图来指导探索，基于频率和基于随机的技术[6] - [8]。最近，采用路径优先级与进化搜索相结合，其中定义适应度函数来指导符号执行[2]。与这些路径探索技术相比，DigFuzz中的路径优先级是将具有概率的路径优先化为模糊测试的难度。据我们所知，我们是第一个研究混合模糊测试系统中的路径优先级问题的人。

定向符号执行还使用路径优先级来达到目标。这些技术旨在为目标语句或分支搜索可行路径[37]，[45]。与有向符号执行技术相比，DigFuzz中的路径优先级是识别用于执行的目标路径，而不是为给定目标搜索可行路径。

模糊测试中的种子调度。种子选择在模糊测试中起着重要作用，并且已经提出了一些研究来通过优先考虑种子投入来改进种子调度[4]，[11]，[44]。 Woo等人。 [44]模型黑盒模糊作为一个多臂强盗问题，其中种子的能量是根据它是否在任何先前的模糊迭代中暴露出崩溃来计算的。 AFLfast [4]通过为AFL较少采用的输入分配更多能量来改进AFL的种子选择策略。这些种子调度技术背后的基本见解是搜索变异执行更有可能发现新程序状态的种子。在我们未来的工作中，我们计划设计调度技术，以便使用难以探索的路径卸载模糊器。

测试用例优先级尝试以提高检测到错误率的方式重新排序测试用例[21]，[22]，[24]，[26]，[28]。本研究中的路径优先级是为了获得最有可能阻塞模糊器的错过路径。搜索算法也与基于搜索的测试优先级和其他基于搜索的软件工程密切相关[23]。

8. Conclusion

在本文中，我们对一些最先进的混合模糊测试系统进行了彻底的调查，并指出了在这些系统中部署的“需求启动”和“最佳切换”策略的几个基本限制。我们进一步提出了一种“判别调度”策略，通过设计基于蒙特卡罗的概率路径优先级模型来量化每条路径的难度，从而更好地利用符号执行的能力。我们基于设计实现了原型系统DigFuzz，并使用两个流行的数据集进行综合评估。评估结果表明，与最先进的混合模糊测试系统Driller和MDPC相比，DigFuzz中的复杂执行对增加的代码覆盖率和增加的已发现漏洞数量的贡献更大。

简单的活着

目录