论文阅读-Directed Greybox Fuzzing 定向灰盒模糊（2017）

摘要：

本文介绍了一种新的Directed Greybox Fuzzing (DGF)方法，可以有效地指导模糊测试，以便更快地到达目标程序位置。作者开发了一种基于模拟退火的能量调度算法，逐渐为更接近目标位置的种子分配更多能量，同时减少远离目标位置的种子的能量。实验表明，DGF比有向符号执行的白盒模糊测试和无向灰盒模糊测试都更有效。作者还展示了DGF在补丁测试和崩溃重现方面的应用，并讨论了将AFLGo集成到Google的持续模糊测试平台OSS-Fuzz中的可能性。

注：什么叫退火算法？

模拟退火算法是一种全局优化算法，它通过引入一个温度参数，在搜索过程中可以接受一定概率的劣解，从而避免陷入局部最优解。在每一次迭代中，算法会随机选择一个邻域解，并计算其能量值。如果邻域解的能量值比当前解的能量值更优，则直接接受邻域解。如果邻域解的能量值比当前解的能量值更劣，则以一定概率接受邻域解，这个概率与当前温度和能量差有关。随着迭代次数的增加，温度逐渐降低，接受劣解的概率也逐渐降低，最终算法会收敛到全局最优解或近似最优解。

1 INTRODUCTION  

什么是灰盒模糊测试？

灰盒模糊测试（GF）被认为是漏洞检测领域的最先进技术。使用轻量级仪器确定输入所执行的路径的唯一标识符，生成新的输入并添加到fuzzer的队列中。新的输入是通过改变提供的种子输入来生成的，并且如果它们执行新的且有趣的路径，则将其添加到模糊器的队列中。

定向灰盒模糊器的motivation:

然而，现有的灰盒模糊器无法有效地进行定向。定向模糊器是安全研究人员的重要工具。与无向模糊器不同，有向模糊器将大部分时间预算用于到达特定目标位置，而不会浪费资源来强调不相关的程序组件。定向模糊器的典型应用可能包括:

• patch testing:（补丁测试）通过设置更改的语句作为目标，可以使用定向模糊测试来检查更改是否引入了漏洞。
• crash reproduction:定向模糊测试可以用于快速复现现场崩溃，通过设置堆栈跟踪中的方法调用作为目标。
• static analysis report verification:静态分析报告验证可以通过设置静态分析工具报告的潜在危险语句作为目标来生成测试输入。
• information flow detection:信息流检测可以通过设置敏感源和敏感接收器作为目标来生成执行，以暴露数据泄漏漏洞。

白盒定向模糊的介绍：

大多数现有的定向模糊测试工具(基于符号执行技术的白盒测试），使用程序分析和约束求解来生成不同程序路径的输入。符号执行的效果较好，但效率较低，因为它需要进行重量级的程序分析和约束求解。

相比之下，灰盒模糊测试工具可以执行更多的输入，因此有机会开发（轻量级和定向）的灰盒模糊测试工具。

定向灰盒测试的概念：Directed Greybox Fuzzing (DGF)

它专注于达到程序中给定的目标位置。DGF将可达性问题视为优化问题，并使用一种特定的元启发式方法来最小化生成种子与目标之间的距离。为了计算种子距离，我们首先计算并测量每个基本块到目标的距离。种子距离是跨过程的，我们的新方法只需要对调用图进行一次分析，对每个过程内的控制流图进行一次分析。在运行时，模糊器将每个执行的基本块的距离值聚合起来，计算种子距离的平均值。DGF使用的元启发式方法是模拟退火，并作为功率调度实现。功率调度控制所有种子的能量，种子的能量指定了模糊种子的模糊时间。与所有灰盒模糊技术一样，通过将分析移到编译时，我们最小化了运行时的开销。DGF将目标位置的可达性视为优化问题，而现有的有向（白盒）模糊方法将可达性视为迭代约束满足问题。

AFLGO的提出：

​​​​​​​定向灰盒模糊在有效性(即DGF暴露更多漏洞)和效率(即DGF在同一时间内达到更多目标)方面优于定向符号执行。然而，两种技术的集成比单独使用一种技术的性能更好。我们在流行且非常成功的灰盒模糊器AFL中实现了DGF[43]，并将我们的定向灰盒模糊器称为AFLGo。AFLGo是一个有用的补丁测试工具，可以有效地暴露最近引入的漏洞和以前报告的漏洞的不完整修复。

contribution

•灰盒模糊与模拟退火的融合(使灰盒定向）;

•程序间距离的正式度量，一次考虑多个目标，可以在仪器时有效地预先计算，并在运行时有效地推导;

•定向灰盒模糊测试作为AFLGo的实施，该AFLGo可在https://github.com/aflgo/aflgo公开获取;

•将AFLGo作为补丁测试工具集成到OSS-Fuzz的全自动工具链中，该工具链可在https://github.com/aflgo/oss-fuzz上公开获取

•对定向灰盒模糊测试作为补丁测试和崩溃再现工具的有效性和效用进行大规模评估。

2 使用心脏出血作为示例案例研究来解释定向灰盒模糊的相关特征

3 讨论距离的形式化度量以及灰盒模糊与模拟退火的集成

4 介绍了实现以及实验设计

5 将AFLGo应用于补丁测试，并将其与最新技术进行比较(Katch[21])

6 讨论将AFLGo集成到OSS-Fuzz中

7 将AFLGo应用于崩溃再现，并将其与基线无向灰盒模糊器(AFL)和最先进的(BugRedux[18])进行比较

8 引出了对有效性的威胁
9 对相关工作的调查

10 conclusion