# Digfuzz工具论文调研


论文调研：《Send Hardest Problems My Way: Probabilistic Path Prioritization for Hybrid Fuzzing》

<!--more-->

## 背景知识
> [!NOTE]
> - 参考文章
> [阅读笔记：《The Art, Science, and Engineering of Fuzzing: A Survey》](https://blog.csdn.net/qq_41513009/article/details/121039888)
> [Hybrid Fuzzing Paper Summary](https://www.anquanke.com/post/id/263725)


### fuzzing 的分类
- 根据 fuzzer 观察到的语义粒度，fuzzer 被分为黑盒 fuzzer、灰盒 fuzzer 和白盒 fuzzer。
- 根据 PUT 输入可分为 file, network, UI, web, kernel I/O, or threads fuzzer
#### 黑盒（black-box）fuzzer
- 仅考虑输入、输出信息作为 fuzzer 的 knowledgement
- IO-driven or data-driven
- modern fuzzers：the structural informa about inputs
#### 白盒（white-box）fuzzer
- 分析 PUT 内部结构以及 PUT 执行所产生的信息，系统探索 PUT 状态空间
- DSE 动态符号执行（dynamic symbolic execution，concolic testing，symbolic execution+concrete execution），简化符号执行的约束条件
- 污点分析（taint analysis）
- 开销较大（higher overhead）：动态执行+SMT solving
#### 灰盒（grey-box）fuzzer
- 部分 PUT 内部结构信息以及 PUT 执行所产生的信息
- 不考虑完整的语义信息
- lightweight static analysis or dynamic information about execution（e.g. code coverage）
- approximated, imperfect information 加快速度和产生更多的测试用例
#### Dynamic Symbolic Execution
经典的符号执行是指使用符号化的值作为输入运行一个程序，这些符号化的变量代表所有可能的值。当符号执行器执行 PUT 时，它会建立一个符号表达式而不是计算实际的变量。当它遇到一个条件分支指令的时候，它会分为两个 symbolic interpreter，一个代表正确分支一个代表错误分支。对每一条路径，symbolic interpreter 会为执行过程中遇到的每一条分支指令建立一个路径公式（路径断言）。如果存在一个实际的输入，能够执行目标路径，那么就说该路径公式是可满足的。可以通过求解 SMT solver 来生成一个适用于路径公式的实际输入。动态符号执行是传统的符号执行的变体，在动态符号执行过程中，符号执行和实际的执行会同时进行。因此，**动态符号执行通常被称为 concolic（concrete+symbolic）测试**。结合动态执行的优点是实际的执行可以减小符号约束的复杂度。

相比较于灰盒或者黑盒方法而言，动态符号执行是很慢的，这是由于它需要分析 PUT 的每一条指令并插桩。为了解决开销过大的问题，一种缩小动态符号执行范畴的通用策略被提出：让用户确定代码中不感兴趣的部分或者感兴趣的片段、交替使用 conclic testing 和灰盒 fuzzing。

> [!NOTE]
> **DigFuzz**: 用灰盒测试确定每个分支执行概率，再使用白盒 fuzzer 对对于灰盒 fuzzing 比较 challenging 的路径进行 fuzzing
> **DigFuzz** 提出基于蒙特卡洛的路径概率排序模型 (Monte Carlo Based Probabilistic Path Prioritization Model, $MCP^3$)，在 fuzzing 的过程中，用 seed 的 trace 构建执行路径树，用覆盖率计算每个分支的概率，路径的概率为路径上分支的概率相乘，最后基于路径的概率对路径进行排序，概率越小代表路径越难探索，将最难探索的路径优先给 concolic execution 进行探索。

[Probabilistic Path Prioritization for Hybrid Fuzzing](https://ieeexplore.ieee.org/abstract/document/9280412)
主要翻译参考自 [DigFuzz](https://fgroove.github.io/2019/03/27/digfuzz/)。
## Abstract
混合模糊测试结合了模糊测试和符号执行，是一种先进的软件漏洞检测技术。基于对模糊和符号执行本质上是互补的观察，最先进的混合模糊测试系统部署了`需求启动 demand launch`和`最佳切换 optimal switch`策略。虽然这些想法听起来很有意思，但由于过于简单的假设，我们指出了它们中的几个基本限制。

然后，我们提出了一种新颖的`判别式调度 discriminative dispatch`策略，以更好地利用符号执行的能力。我们设计了一种新的基于`Monte Carlo`的概率路径优先级模型，用于量化每条路径的难度，并优先考虑它们的符号执行。此模型将模糊测试视为随机抽样过程，根据采样信息计算每个路径的概率。最后，我们的模型**优先考虑并指定最困难的路径来符号执行**。

我们实现了原型系统`DigFuzz`，并使用两个有代表性的数据集评估我们的系统。结果表明，在各个主要方面，`DigFuzz`中的符号执行性能优于最先进的混合模糊测试系统。特别是，`DigFuzz`中的符号执行有助于发现更多的漏洞（12对5），并在`CQE`数据集上产生比在`Driller`中执行的更多代码覆盖（18.9％对3.8％）。

## Introduction

软件漏洞被认为是对网络空间最严重的威胁之一。因此，发现一个软件中的漏洞至关重要[12]，[16]，[25]，[27]，[32]。最近，模糊测试和符号执行的组合——混合模糊测试，在漏洞发现中变得越来越流行[5]，[29]，[31]，[39]，[42]，[46]。

由于模糊测试和符号执行本质上是互补的，因此将它们结合起来可以潜在地利用它们的独特优势并减轻弱点。更具体地说，模糊测试（Fuzzing）擅长探索包含一般分支（具有大的满足值空间的分支，比如 x>100）的路径，但是不能探索包含特定分支的路径（具有非常窄的满足值空间的分支,比如 x=2）[27]。相反，符号执行能够生成具体的输入，确保程序沿着特定的执行路径执行，但它会遇到路径爆炸问题[9]。

在混合方案中，模糊测试由于高吞吐量通常承担路径探索的大多数任务，而符号执行辅助模糊测试探索低概率的路径、并且生成满足特定分支的输入。通过这种方式，可以减轻分支符号执行中的路径爆炸问题，因为符号执行仅负责探索可能阻止模糊测试的低概率路径。

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

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

1. 对于`需求启动 demand launch`策略：
- 模糊器(`Fuzzer`)的卡住状态不是良好的启动符号执行指标
	模糊测试正在取得进展，并不一定意味着不需要进行符号执行。模糊器仍然可以探索新代码，即使它已经被许多特定分支阻塞，而因为模糊器未处于卡住状态，因此符号执行器被迫空闲。
- 该策略无法识别阻止模糊测试的特定路径
	一旦模糊器卡住，`需求启动 demand launch`策略就会将模糊器保留的所有种子提供给符号执行，用于探索所有错过路径。然后，这种大量错过的路径会让执符号执行不堪重负，并且可能会在很长一段时间后为特定路径生成有效的输入。到那时，模糊器可能已经生成了一个良好的输入来遍历该特定路径，从而使整个符号执行变得毫无用处。
2. 同样，尽管`最佳切换 optimal switch`策略旨在基于可靠的数学模型（即，具有成本的马尔可夫决策过程，简称`MDPC`）做出最优决策，但是量化每条路径的模糊测试和符号执行的成本是非常重要的。例如，为了量化特定路径的独立执行成本，`MDPC`需要收集已经很昂贵的路径约束。结果，`MDPC`的总吞吐量大大降低。此外，在量化模糊测试的成本时，`MDPC`假设所有测试用例均匀分布。这种假设过于简单，因为许多最先进的模糊测试技术[4]，[12]，[16]是自适应和进化的。最后，即使可以准确地估计模糊测试和符号执行的成本，但要将它们标准化以进行统一比较是具有挑战性的，因为这两种成本是通过具有不同度量的技术来估计的。

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

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

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

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

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

## Background And Motivation
Fuzzing [30]和concoic execution [9]是软件测试和漏洞检测的两种代表性技术。 由于观察到模糊和执行的执行在本质上可以相互补充，已经提出了一系列技术[5]，[29]，[31]，[39]，[42]将它们组合在一起并创建混合模糊系统。通常，这些混合模糊测试系统分为两类：“需求启动”和“最佳切换”。
### Demand Launch
最先进的混合方案，如Driller [39]和混合动力系统测试[29]部署了“需求启动”战略。在Driller [39]中，由于模糊器在一段时间内无法取得任何进展，因此该模板执行器仍处于空闲状态。然后，它依次处理来自模糊器的所有保留输入，以生成可能有助于模糊器的输入，并进一步导致新的代码覆盖。类似地，混合分析测试[29]通过混合测试获得了对程序状态空间的深入和广泛的探索。它通过利用随机测试的能力快速到达程序状态，然后通过执行执行彻底探索邻居状态。

在一个问题上，必须有两个假设才能使“需求启动”战略按预期发挥作用：
1) 非卡住状态的模糊器意味着不需要执行。只有当模糊器卡住时，混合系统才应该开始执行。
2) 卡住状态表明模糊器在可接受的时间内无法在发现新的代码覆盖范围方面取得任何进展。此外，具有执行力的执行能够找到并解决阻塞模糊器的难以解决的条件检查，以便模糊测试可以继续发现新的覆盖范围。
#### 观察
为了评估`需求启动`战略的表现，我们仔细研究了 Driller 如何在 DARPA Cyber Grand Challenge（CGC）的12个小时中工作12小时，并找到五个有趣且令人惊讶的事实。
1) _调用 concolic 执行的百分比较低_。Driller 仅在118个二进制文件中的49个中调用了 concoic 执行，这意味着模糊器只会卡在这49个二进制文件上。这一事实与 Driller [40]的论文中报道的数字（42）相当。
2) _卡住的时间段较少_。对于`事实1`中的49个二进制文件，我们统计计算卡住时间段，卡住时间段的分布如图1所示。我们可以观察到超过85％的卡住时间段低于100秒。 
![图1. 停滞状态持续时间的累积分布](https://cdn.haoyep.com/gh/leegical/Blog_img/md_img202312101455060.png)
3) _巨大的吞吐量差距_。表1 中的执行时间表明，模糊测试的吞吐量比 concolic 执行的吞吐量高出几个数量级。因此，一个实际的设计应该只选择很少的输入来执行，而不是“需求启动”策略，后者将模糊测试保留的所有输入都提供给 concolic 执行器。平均而言，为一个具体的输入完成动态符号执行需要1654秒。
![表1 执行时间比较](https://cdn.haoyep.com/gh/leegical/Blog_img/md_img202312101456025.png)
4) _实用性低_。由于存在如此巨大的吞吐量差距，在实践中，对于“需求启动”策略，符号执行对模糊测试的帮助很有限。图2显示了对 CQE 二进制文件进行符号执行（angr）处理的输入数量和模糊测试器保留的输入数量（23915个中的1709个）。对于12个实际程序，表2显示 QSYM 处理了795个输入，而模糊测试器保留的输入总数为15269个。平均而言，在12小时的测试中，只有模糊测试器保留的输入中的6.3%被符号执行器处理。
![图2. 模糊器保留的输入数和 concolic 执行处理的输入数。](https://cdn.haoyep.com/gh/leegical/Blog_img/md_img202312101454643.png)

![表2 输入由 Fuzzer 保留并由 QSYM 处理](https://cdn.haoyep.com/gh/leegical/Blog_img/md_img202312101503685.png)

5) _对代码覆盖率的贡献很小_。在 12 小时的测试结束时，“需求启动”策略在 49 个 CQE 二进制文件上调用了 concolic 执行，并完成了 1709 次运行。更详细的调查显示，总共只有 51 个由 concolic 执行生成的输入是通过模糊测试导入的，并且 concolic 执行只能通过生成至少一个导致新代码覆盖率的输入来帮助对 13 个二进制文件进行模糊测试。
#### 局限性
上述结果表明`需求启动`策略的两个主要局限。

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

其次，**“需求启动”策略无法识别阻止模糊测试的特定路径，从而导致非常低效的执行**。一方面，平均执行平均需要1654秒来处理一个输入（事实3）。另一方面，模糊器通常比常规执行可以保留更多的输入（事实4）。结果，对应于阻止模糊测试的特定分支的输入（即，可能导致执行到目标位置的输入）仅具有非常小的机会被通过结构执行来拾取和处理。因此，上述假设2在实践中并不真正成立。事实5可以进一步证实这一结论，尽管它是在49个二进制文件上发布的，但是对于仅仅13个二进制文件的执行可以帮助模糊测试。此外，在1709次符号执行之后，模糊执行器仅导入了51个来自符号执行的输入，表明由符号执行而产生的输入质量非常低。
### Optimal Switch
“最佳切换”策略旨在基于数学模型（即，具有成本的马尔可夫决策过程，简称`MDPC`）对使用哪种方法来探索给定的执行路径做出最佳决策。为了获得最佳性能，MDPC 始终选择成本较低的方法来探索每条路径。为了使这一战略运作良好，必须遵循以下假设：

1) 可以准确地估计通过模糊和经验执行来探索路径的成本
2) 成本估算的开销可以忽略不计
3) 用于做出最优决策的算法是轻量级的
#### 观察
为了评估`最佳切换`的性能，我们评估了 MDPC 如何在 CQE 数据集中对118个二进制文件工作12小时，并有3个有趣的观察结果。

1) _Heavyweight Estimation_。表1 显示了模糊测试、MDPC、符号执行（angr、QSYM）中的最佳决策之间的吞吐量差距。可以观察到使用 MDPC 计算概率的成本很高，是模糊测试的大几千倍。
![表1 执行时间比较](https://cdn.haoyep.com/gh/leegical/Blog_img/md_img202312101456025.png)
2) _吞吐量降低_。由于 MDPC 在探索每条路径之前做出最佳决策，因此整体分析吞吐量显着降低，从纯模糊测试中每秒执行417次到 MDPC 中每秒执行2.6次。由于吞吐量减少的负面影响，下图显示了由 AFL 维护的位图大小，这是代码覆盖的近似。可以观察到，`optimal concolic testing`发现的代码覆盖较少，而不如纯模糊测试。
3) _估计不准确_。由于吞吐量降低的影响，MDPC 仅在29个二进制文件中发现漏洞，而纯模糊测试可以发现67个二进制文件中的漏洞。
![Fuzing和MDPC的代码覆盖率比较](https://cdn.haoyep.com/gh/leegical/Blog_img/md_img202312101511673.png)
由于 MDPC 在探索每条路径之前做出了最佳决策，昂贵的最优决策都会带走模糊测量的高吞吐量。作为优化，使模糊测试和最优决策工作并行进行，而不是像在原始系统中那样按顺序运行，并构建并发 MDPC。使用相同的数据集对其进行评估，并得出以下观察结果，我们有另一个观察。

4) 在模糊测试开始后的几秒钟内，几乎所有遗漏的路径都决定通过 concolic 执行进行探索。通过检查覆盖率统计，我们观察到模糊器能够在几秒钟内生成数百个测试用例，这导致基于 MDPC 算法的 Fuzzing 搜索遗漏路径的代价很高。相反，即使我们为每个路径约束分配最高的求解成本(如定义[42]所示的50)，也可以降低执行成本。
#### 限制
上述观察结果表明，`最佳切换`策略的关键限制是估计通过模糊测试和符号执行来探索路径的成本是重量级且不准确的，这掩盖了制定最优解决方案的好处。

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

其次，准确估计通过模糊测试和符号执行探索给定路径的成本是非常重要的。MDPC 根据路径约束的复杂性估计求解代价，并根据覆盖统计估计随机测试的成本。这些估计涉及模糊测试的运行时吞吐量、约束求解器以及符号执行引擎的性能，它们本质上是不同的程序分析技术。因此，定义一个统一的衡量标准来评估不同技术的成本是具有挑战性的。
## PROBABILISTIC PATH PRIORITIZATION GUIDED BY MONTE-CARLO
为了解决当前混合模糊测试系统的上述局限性，我们提出了一种新颖的`判别调度`策略，以更好地结合模糊和执行。
### Key Challenge
如上所述，我们策略的关键挑战是**以轻量级方式量化模糊器遍历路径的难度**。

>有一些解决方案可以使用昂贵的程序分析来量化路径的难度，例如值分析[45]和概率符号执行[5]。然而，这些技术并没有解决我们的问题：如果我们已经执行了重量级分析来量化一条路径的难度，我们还不如只解决路径约束并生成一个输入来遍历这条路径。
>
>最近的一项研究[42]提出了一种理论框架，用于优化的结构测试。它定义了基于程序路径概率和约束求解成本的最优策略，然后将问题简化为带有成本的马尔可夫决策过程（简称 MDPC）。本研究与我们的工作有着相似的问题范围。然而，马尔可夫决策过程本身对于具有大状态空间的程序来说是重量级的。此外，模糊测试和符号执行的成本对于评估和标准化以进行比较是具有挑战性的。
### Monte Carlo Based Probabilistic Path Prioritization Model
在这项研究中，我们提出了一种新的基于`Monte Carlo`的概率路径优先级模型（简称 $MCP^3$）来应对这些挑战。为了轻量化，我们的模型应用`Monte Carlo`方法来计算通过模糊测试探索路径的概率。要使蒙特卡罗方法有效运作，需要满足两个要求：

1) 对搜索空间的抽样必须是随机的;
2) 需要大量随机抽样才能使估计具有统计意义。

由于 fuzzer 随机生成用于测试程序的输入，我们的见解是将这些输入的执行视为整个程序状态空间的随机样本，因此满足第一个要求。此外，由于模糊测试具有非常高的吞吐量，因此也可以满足第二个要求。因此，通过将模糊测试作为抽样过程，我们可以通过覆盖统计以轻量级方式统计估计概率。

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

#### Probability for each branch
量化了模糊测试器通过条件检查并探索分支的难度。方程式1展示了$MCP^3$如何计算分支的概率。
\begin{equation*} P\left(br_i\right) = \left\lbrace \begin{array}{lr}\frac{cov \left(br_i \right)}{cov \left(br_i \right) + cov \left(br_j \right)}, & cov \left(br_i \right)\ne 0 \\\\
\frac{3} {{cov \left(br_j \right)}} , & cov \left(br_i \right) = 0 \end{array} \right. \tag{1} \end{equation*}

在`方程1`中，$b_{ri}$ 和 $b_{rj}$ 是共享相同前继块的两个分支，$cov(b_{ri})$ 和 $cov(b_{rj})$ 分别指的是 $b_{ri}$ 和 $b_{rj}$ 的覆盖统计，表示模糊测试器的样本覆盖了 $b_{ri}$ 和 $b_{rj}$ 的次数。
- 当 $b_{ri}$ 已经被模糊测试器探索过（$cov(b_{ri})$ 非零时），$b_{ri}$ 的概率可以通过将 $b_{ri}$ 的覆盖统计除以 $b_{ri}$ 和 $b_{rj}$ 的总覆盖统计来计算。
- 当 $b_{ri}$ 之前未被模糊测试器探索过（$cov(b_{ri})$ 为零），我们采用统计学中的三比规则[43]来计算 $b_{ri}$ 的概率。三比规则表明，如果某一事件在包含 n 个主体的样本中未发生，则从 0 到 3/n 的区间是该事件在总体中发生率的95%置信区间。当 n 大于$30$时，这是对来自更敏感测试的结果的一个很好的近似。遵循这个规则，如果 $cov(b_{rj})$ 大于$30$，则 $b_{ri}$ 的概率变为 $3/cov(b_{rj})$。如果 $cov(b_{rj})$ 小于$30$，则该概率在统计上没有意义。换句话说，在覆盖统计大于$30$之前，我们将不计算概率。
#### Probability for each path
为了计算路径的概率，我们应用马尔可夫链模型[19]，将路径视为相继分支之间的连续转换[4]。模糊测试器探索路径的概率计算如`方程2`所示。
\begin{equation*} P \left(path_j \right) = \prod \lbrace P\left(br_i \right) | br_i \in path_j \rbrace . \tag{2} \end{equation*}

在方程2中，$path_j$ 代表一个路径，$b_{ri}$ 表示路径覆盖的分支，$P(b_{ri})$ 表示 $b_{ri}$ 的概率。路径 $path_j$ 的概率，即 $P(path_j)$，通过将沿路径的所有分支的概率相乘来计算。
### $MCP^3$ based Execution Tree
在我们的`判别式调度`策略中，关键思想是从模糊测试执行的运行时信息推断并优先考虑符号执行的路径。为此，我们构建并维护一个基于$MCP^3$的执行树。
#### **定义1**
基于$MCP^3$的执行树是是一个有向树 $T = (V, E, \alpha)$，其中：
- 顶点集合 $V$ 中的每个元素 $v$ 对应于程序执行期间的程序轨迹中的一个唯一基本块；
- 边集合 $E⊆V \times V$ 中的每个元素$e$对应于两个顶点 $v$ 和 $w$ 之间的控制流依赖性，其中$v,w \in V$。如果一个顶点包含条件检查，则可以有两个输出边；
- 标记函数$\alpha: E \to \Sigma$将边与概率标签相关联，其中每个标签表示模糊测试器通过该分支的概率。
## Design and Implementation
在本节中，我们将介绍 **DigFuzz** 的系统设计和实现细节。
### System Overview
图3显示了`DigFuzz`的概述。它由三个主要部分组成：1）模糊器; 2）$MCP^3$模型; 3）符号执行器。
![Fig. 3: Overview of DigFuzz](https://cdn.haoyep.com/gh/leegical/Blog_img/md_img202312101450165.png)

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

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

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

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

总之，`DigFuzz` 迭代工作。在每次迭代中，$MCP^3$模型通过对模糊器保留的所有输入的跟踪分析来更新执行树。然后，该模型使用执行样本的覆盖统计为每个分支标记其概率。之后，$MCP^3$模型对所有遗漏路径进行优先排序，并选择具有最低执行概率的路径进行符号执行。符号执行器将为跟踪中的遗漏分支生成输入，将通过符号执行期间已探索的路径更新执行树。完成这些步骤后，`DigFuzz` 将进入另一轮迭代。
### Execution Sampling
DigFuzz 需要进行随机抽样来使用蒙特卡罗方法计算概率[35]。基于模糊器的性质就是生成随机输入，我们将模糊过程视对整个程序状态空间的随机抽样过程。由于模糊测试的高吞吐量，生成的样本数量将很快变得足够大，具有统计意义，这由三个规则定义[43]，其中当样本数大于30时，从0到$3/n$的区间是95%的置信区间。

基于这一观察，我们提出了执行抽样的算法（Algorithm 1）。该算法接受3个输入并在 $HashMap$ 中生成 coverage 统计信息。

> [!TIP]
> - 算法1的3个输入
> 1）目标二进制$P$；  2）模糊测试器$Fuzzer$；  3）存储在$Set_{inputs}$中的初始种子

给定这3个输入，算法在模糊测试过程中进行迭代抽样。
1. $Fuzzer$使用$P$和$Set_{inputs}$以生成新输入 $Set_{NewInputs}$（Ln.7）。
2. 然后，对于 $NewInputs$ 中的每个输入，我们收集由$P$和$input$（Ln.9）确定的路径内的每个分支的覆盖统计信息，并进一步更新存储在$HashMap_{CovStat}$中的现有覆盖统计（Ln.11和12）。
3. 最后，算法将$Set_{NewInputs}$合并到$Set_{inputs}$（Ln.15）并开始新的迭代。
![Algorithm 1 Execution Sampling](https://cdn.haoyep.com/gh/leegical/Blog_img/md_img202312101445625.png)
### Execution Tree Construction
如图3所示，DigFuzz 使用来自模糊器的运行时信息生成基于$MCP^3$的执行树。
![Fig. 3: Overview of DigFuzz](https://cdn.haoyep.com/gh/leegical/Blog_img/md_img202312101450165.png)

> [!TIP]
> - Algorithm 2的输入、输出
> 输入，也是`Algorithm 1`的输出：
> 1）目标二进制文件的控制流图$CFG$；
> 2）fuzzer 保留的输入$Set_{inputs}$；
> 3）覆盖统计$HashMap_{CovStat}$
> 
> 输出：基于$MCP^3$的执行树 $ExecTree$

`Algorithm 2`展示了树构建过程。算法主要分为两个步骤。
- **Step1**：对 $Set_{inputs}$中的每个输入执行跟踪分析，提取相应的跟踪，然后将跟踪合并到 $ExecTree$ 中（Ln. 6到11）
- **Step2**：计算执行树中每个分支的概率（Ln. 12到16）。
	- 为实现这一点，对于 $ExecTree$ 中的每个分支$b_{ri}$，我们通过检查 $CFG$（Ln. 13）提取其相邻分支$b_{rj}$（$b_{ri}$和$b_{rj}$共享包含条件检查的相同前继块）。
	- 然后，算法利用方程1计算$b_{ri}$的概率（Ln. 14）。
	- 之后，算法使用计算得到的概率标记执行树 $ExecTree$（Ln. 15）并输出新标记的 $ExecTree$。
![Algorithm 2 Execution Tree Construction](https://cdn.haoyep.com/gh/leegical/Blog_img/md_img202312101447190.png)

为了避免执行树中潜在的**路径爆炸**问题，我们只对由模糊测试保留的种子输入执行跟踪分析。模糊器通常将那些具有新代码覆盖的突变输入视为进一步突变的种子。对这些保留的种子进行跟踪是一种有前景的方法，可以对探索的程序状态进行建模。对于沿着执行跟踪的每个分支，只要模糊测试器尚未覆盖相反分支，就标识为一个遗漏路径，该路径指的是与未覆盖的分支连接的跟踪前缀。换句话说，执行树不会包括一个相反分支尚未被覆盖的遗漏分支。

为了简化表示，我们提供了一个运行示例，它简化了CQE数据集[13]中的程序，代码如图4所示。漏洞由特定字符串保护，很难进行模糊检测。
![图4.运行示例](https://cdn.haoyep.com/gh/leegical/Blog_img/md_img202312101535292.png)

图5示出了用于图4中的运行示例的基于$MCP^3$的执行树。每个节点表示一个基本块。每条边都是一个用概率标记的分支。可以观察到树中有2个`trace`（红色：$t1 =⟨b1，b2，b6，b12，b13，b7，b9，b11⟩$和蓝色：$t2 =⟨b1，b3，b4，b12，b14⟩$）。请注意，概率是通过多个执行样本计算的。在此示例中，我们为了简化呈现仅提供了两个跟踪。
![图5：具有概率的执行树](https://cdn.haoyep.com/gh/leegical/Blog_img/md_img202312101538774.png)
### Probabilistic Path Prioritization
我们基于概率对路径进行优先排序。如方程2所示，路径被视为一个马尔可夫链，其概率是基于路径内所有分支的概率计算得出的。路径可以表示为一系列已覆盖的分支，每个分支都标记有其概率，该概率表示随机输入能够满足条件的可能性有多大。因此，我们利用马尔可夫链模型，将路径的概率看作是转换的概率序列。
![算法3. DigFuzz中的路径优先排序](https://cdn.haoyep.com/gh/leegical/Blog_img/md_img202312101709167.png)

> [!TIP]
> Algorithm 3的输入、输出
> 输入，也是`Algorithm 2`的输出：基于$MCP^3$的执行树$ExecTree$
> 
> 输出：$Set_{Prob}$，一组未探索（遗漏）的路径及其概率

`Algorithm 3`详细地呈现了这个算法。`DigFuzz` 将根据$Set_{Prob}$对这些 **未探索（遗漏）** 的路径进行进一步的优先排序，并将概率最低的路径提供给符号执行。该算法：
1) 从执行树遍历开始。对于 $ExecTree$ 中每个跟踪上的每个分支$b_{ri}$，它首先提取相邻的分支$b_{rj}$（Ln. 5），然后收集沿给定跟踪未探索的路径（Ln. 6）。
2) 然后，算法通过调用实现方程2的 $CalPathProb()$ 计算了未探索路径的概率，并将信息存储在 $Set_{Prob}$中。
3) 最终，该算法生成$Set_{Prob}$，即每个跟踪的未探索路径及其概率。

得到$Set_{Prob}$后，我们将
1) 按概率降序对未探索路径进行优先排序，并确定**概率最低的路径**供符号执行使用。
2) 确定输入，引导 concolic 执行器优先探索概率最低的路径。

以图4中的程序为例。在图5中，未探索（遗漏）的分支显示为虚线。在构建了执行树并正确标记之后，使用 `Algorithm 3`来获取未探索的路径并计算这些路径的概率。我们可以观察到总共有4条未探索的路径，分别记为$P_1$、$P_2$、$P_3$和$P_4$。通过调用 $CalPathProb()$ 函数，这些未探索路径的概率如图中所示计算，其中概率最低的路径是$P_1$。为了引导 concolic 执行器探索$P_1$，`DigFuzz`将选择导致跟踪$〈b1, b2, b6, b12, b13, b7, b9, b11〉$的输入，并将此输入分配为 concolic 执行的具体值，因为此跟踪与未探索路径$P_1$共享相同的路径前缀$〈b1, b2, b6, b12, b13, b7, b9〉$。
## Discussion
### Threats to Validity
我们的实验结果基于论文中提供的有限数据集。已经努力在实际程序上评估 `DigFuzz`，但是当 Angr [38]遇到不支持的系统调用时，它无法对程序进行符号执行。因此，结果可能无法完全代表实际程序。对这些程序进行评估是必要的，以便就拟议技术在实践中的有效性得出结论。我们将把对真实世界程序的评估留作未来的工作。
### Limitations
首先，虽然`DigFuzz`中的“区别性调度”被设计为轻量级方法，但它仍然会产生一些运行时和内存消耗开销，包括收集模糊测试的运行时信息和构造执行树。但根据评估，可以看到对于模糊测试的吞吐量减少是可以忽略不计的。此外，由于树中的每个节点仅携带非常有限的信息，因此执行树的总内存消耗是非常易于管理的。
其次，由于`DigFuzz`仅估计模糊探测器的路径难度，但没有考虑约束求解的复杂性，所以挑选的路径收集到的约束可能是不可解的，这可能导致浪费整个符号执行循环。此外，可能导致漏洞的最有希望的路径也可能不是`DigFuzz`选择的最难的路径。这两个限制是由于我们找到正确的探索路径的模型。我们考虑将它们解决为未来的工作。
## Related Work
`模糊测试 Fuzzing`和`符号执行 symbolic execution`是程序测试的两种主流技术。许多先前的努力已经致力于改进它们[3]，[27]，[33]，[36]。

BuzzFuzz [17]利用动态污点标记来识别由可疑指令处理的输入字节。Dowser [20]采用反向工程技术来识别与可疑功能相关的输入字段。Vuzzer [34]利用控制流和数据流特征来准确确定何时以及如何变异这些输入。Skyfire [40]利用现有样本中的知识生成用于模糊测试程序的分布良好的种子输入。Angora [12]旨在通过解决路径约束而不使用符号执行来增加分支覆盖。T-Fuzz [32]首先允许模糊测试器在去除了无法绕过的健全性检查的转换程序上工作。作为辅助的后处理步骤，T-Fuzz 利用基于符号执行的方法来过滤掉假阳性。CollAFL [16]是一种基于覆盖率敏感的模糊测试解决方案，通过提供更准确的覆盖信息来减轻路径冲突。它还利用覆盖信息应用了三种新的模糊测试策略。Veritesting [1]通过采用静态符号执行来放大动态符号执行的效果，以解决路径爆炸问题。Mayhem [10]提出将在线和离线符号执行结合起来处理内存耗尽的问题。

`DigFuzz` 的主要贡献在于提出了一种更有效的策略，将模糊测试与符号执行结合起来。因此，模糊测试和符号执行的进展超出了我们的范围。
### Hybrid fuzzing system
大多数混合模糊测试系统遵循通过选择性符号执行增强模糊测试的观察[9]，[27]，[38]，[40]。TaintScope [40]部署动态污点分析来识别校验点，然后应用符号执行生成满足校验和的输入。T-Fuzz [31]首先允许模糊测试器在经过去除健全性检查的转换程序上工作，然后利用基于符号执行的方法来过滤出假阳性。SAVIOR [13]提出了一种基于漏洞的混合模糊测试系统。它优先考虑具有更高潜力导致发现更多漏洞的种子进行合符号执行。此外，它在合符号执行期间启用了安全检查。HFL [25]将模糊测试与符号执行相结合，以解决内核特定的模糊测试挑战。PANGOLIN [23]设计了基于多面体路径抽象的增量混合模糊测试，该抽象在合符号执行阶段保留了探索状态，并允许对现有技术进行更有效的变异和约束求解。与这些技术相比，`DigFuzz` 通过基于覆盖统计量量化模糊测试探索路径的难度来优先考虑路径。

另一种混合模糊测试系统是将符号执行视为输入生成或路径选择的引导者。Pak [30]提出了一种混合模糊测试系统，将符号执行应用于收集路径约束，然后系统生成符合路径谓词并过渡到模糊测试器的输入。DeepFuzz [5]采用概率符号执行为程序路径分配概率，然后利用这些概率来引导模糊测试中的路径探索。

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

QSYM [46]使用动态二进制转换将符号仿真与本机执行集成在一起。 它还减轻了传统的严格健全性要求，减轻了传统的严格健全性要求，使其可扩展到现实世界的程序。 主要重点是使其可以扩展到真实世界的程序。 主要重点是使其可以扩展到真实世界的程序。 有选择地只派遣最难的工作的主要焦点。
### Path prioritization in symbolic execution
路径优先化有望减轻动态符号执行中的路径爆炸问题。代表性研究包括启发式技术和声音程序分析技术[9]。这些启发式方法包括使用控制流图来指导探索，基于频率和基于随机的技术[6] - [8]。最近，采用路径优先级与进化搜索相结合，其中定义适应度函数来指导符号执行[2]。与这些路径探索技术相比，`DigFuzz`中的路径优先级是将具有概率的路径优先化为模糊测试的难度。据我们所知，我们是第一个研究混合模糊测试系统中的路径优先级问题的人。

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

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

## Conclusion
1. 指出了一些最先进的混合模糊测试系统中采用的“需求启动”和“最优切换”策略中的一些根本限制。
2. 进一步提出了一种`discriminative dispatch`策略：通过设计一个基于`Monte Carlo`的概率路径优先模型来更好地利用`concolic execution`的能力，以量化每条路径的难度。
3. 实现了原型系统`DigFuzz`。评估结果显示，与最先进的混合模糊测试系统相比，`DigFuzz` 对于增加代码覆盖和发现漏洞的数量贡献更大。


---

> 作者: [Leehow](https://www.haoyep.com/)  
> URL: https://www.haoyep.com/posts/digfuzz/