论文笔记《Directed Greybox Fuzzing》
论文笔记《Directed Greybox Fuzzing》
-
摘要
-
Introduction
-
Technology
-
- 种子输入和多个目标之间的距离测量
-
模拟退火算法遵循（SA）进行能量分配
-
模拟退火(SA)
-
模拟退火算法遵循（SA）进行能量调度
-
实际应用中进行能量系统的整合与优化
-
系统整体架构
-
参考
-
本文第一次提出定向模糊测试。
摘要
传统的Greybox模糊器（GF）在定位有问题的更改或补丁方面存在局限性，在关键系统调用、危险位置以及与我们希望重现的报告漏洞相关的堆栈跟踪行为上表现不佳。本文提出了一种新型定向灰盒模糊测试方法（DGF），该方法旨在通过生成特定输入来精准定位到一组预设的目标程序位置，并通过设计一种渐进式的能量分配策略实现了这一目标：即逐步将更多能量分配给与目标位置更为接近的种子样本，并减少远离目标位置种子的能量权重。经过实验验证，在我们的实现版本AFLGo中,DGF方法显著优于基于符号执行的有向白盒模糊测试框架以及传统非定向灰盒模糊测试方案；此外,我们还展示了DGF在补丁分析以及漏洞再现方面的实际应用效果,并成功将其与开源平台OSS-Fuzz进行了整合.值得注意的是,AFLGo方法由于其高度专注于特定目标特性,能够在多个实际项目中发现大量问题,其中就包括LibXML2等几个较为棘手的安全关键型项目,累计发现了39个问题实例.这些成果对应于17个已知的安全漏洞CVE标识.
Introduction
在本文中阐述了定向灰盒模糊控制(DGF)，其核心在于将可达性转化为程序中的目标位置定位。 在高层次上,我们将可达性转化为最优化问题,并采用了一种独特的启发式方法来最小化生成的种子与目标之间的距离. 为了确定种子间的距离,我们首先计算并确定了每个基本块与目标之间的距离. 尽管这些子块之间的关系跨越了进程边界,但我们的新方法只需对调用图以及每个进程中CFG各执行一次分析即可. 在运行时阶段,模糊器通过集成每个运行的基本块的距离值来计算最终的平均值作为整体的种子间距. DGF采用了模拟退火算法作为其元启发式框架的基础,并通过能量调度机制来管理所有参与fuzzing的种子的能量状态. 所有参与fuzzing的子体能量特性直接决定了其执行fuzzing所需的时间
DGF 将目标位置的可达性转化为最优化问题；而现有的方向（白色模型）的模糊方法则将其转化为迭代约束补偿问题
本文提出的定向灰盒模糊技术是由CG（Call graph）与CFG（Control flow graph）共同构建而成，并通过应用距离测量技术及退火能量调度方法实现了一种高效的解决方案，在补丁测试与程序崩溃复现等领域的应用中表现出显著效果。
本文的主要工作：
-
灰盒模拟与模拟退火的融合
-
提出了一种严格定义的距离测量方法，在多维度评估指标下可全面评估多方面的性能，在预处理阶段计算后能在运行过程中实现最优结果
-
基于定向灰盒模糊的技术框架设计了AFLGo功能模块，并已由官方渠道公开提供，
-
基于AFLGo构建补丁测试功能的方法已被正式开源发布
-
从系统性角度对定向灰盒燃烧技术进行全方位考察, 以期准确评估其在补丁测试与碰撞复制任务中的表现及其实际应用效果
Technology
种子输入和多个目标之间的距离测量
本研究将不同函数间的距离作为评估指标，在基于函数级的调用图和控制流图中赋予每个节点一个特定的数值。
为了衡量跨函数的距离，在函数级别的调用图（CG）以及基于CFG的基本块级过程中为每个节点赋予一个数值。可以通过从给定的源代码参考中快速提取出目标函数Tf以及目标基本块Tb。
在调用图中任意目标函数处所具有的可及性程度上限是由其到该目标的距离所限定的；而各节点间的可及性程度则由它们之间的距离所决定。本文将节点间距离df(n, n')定义为位于调用图中连接两节点n与n'之间最短路径上的边的数量；同时将节点n与目标节点Tf间的层次间距df(n, Tf)定义为其至任一可达的目标节点间距离之倒数平均值。
在 CG 中可从节点 n 出发的所有目标函数集合中定义了 R(n,Tf) 在 CG 中可从节点 n 出发的所有目标函数集合中定义了 R(n,Tf) 在 CG 中可从节点 n 出发的所有目标函数集合中定义了 R(n,Tf) 其加权平均指标能够有效地区分那些分别接近一个目标同时远离另一个目标以及与两目标等距的节点 相比之下 算术平均方法将这两个节点到各自对应的目标的距离视为相等 图4展示了一个具体的例子
基本块级目标距离决定了基本块到调用函数的所有其他基本块的距离，以及函数级目标距离的倍数。本文将基本块的目标距离定义为调用链中到达目标位置的其他基本块的平均距离。BB距离为控制流图中两个基本块的距离。BB距离db(m1, m2)为控制流图中两个基本块之间最短路径上的边缘数。N(m)为基本块m调用的一些函数。最后本文定义基本块级的目标距离：
基于其功能关系的距离度量体系中包含了两个关键要素：首先是由一个基础模块至其所有被调用功能相关的其他基础模块间的平均间距；其次是由这些被调用功能相关联的功能级目标间距的比例系数值；基于这种间距模型所建立的基础模块间的目标间距计算方式能够有效反映各基础模块间的相对功能关联程度；同时该间距计算方式也能够合理地对不同层次的功能关联关系进行定量表征；这种间距计算方法具有良好的功能性表现特性；此外该方法还具有良好的扩展性特征；即可以通过引入新的中间层概念而不断扩展其适用范围；基于此我们提出了一个更具普适性的基础模块间的目标间距计算模型；该模型不仅能够处理单层结构化编译器中的相关问题而且也能够适应多层嵌套式的复杂编译器系统中的应用需求；此外该模型还支持在线动态更新机制的设计与实现；使得编译器优化系统能够在运行过程中实时更新相关参数值从而保证系统的整体优化效果得到持续提升；
其中c=10是一个常数，用于放大函数级距离。注意，db(m, Tb）是为所有m∈Gi定义的。
在此基础上
模糊器系统性地负责管理一组种子S以实现模糊效果。我们将其归一化种子距离d(s, Tb)定义为s到Tb的度量与该组中所有先前种子s′∈S的最小度量之间的差异值，并将其计算结果与该组中所有度量的最大值和最小值之差进行归一化。
基于模拟退火（SA）算法的能量分配
模拟退火(SA)
模拟退火(SA) 属于马尔科夫蒙特卡洛方法(MCMC)，其主要应用于在预设的时间限制范围内，在规模庞大的离散搜索空间中寻求接近全局最优解的目标。
模拟退火算法SA的核心特性在于其运行过程中的双重策略：它优先采纳优越方案，在特定条件下偶尔也会采纳较劣方案。
温度参数调节对较劣方案的接纳概率，并按照预先设定好的降温策略不断递减；初始阶段（T=1），该算法倾向于采纳所有改进方案；而当温度降至趋近于零时，则演变为传统的梯度下降法。
冷却计划：
其中α是一个常数，通常为0.8~0.99.
基于模拟退火的能量调度
由于自动化漏洞挖掘的时间往往有限，在本文中设定一个特定的时间tx作为退火过程的关键转折点。其中，在经历了足够的探索时间后（即经过充分的探索阶段），退火过程进入开发阶段。具体而言，在tx之后（即经过该关键时间点），模拟退火过程的行为将会类似于经典的梯度下降算法（也称为贪婪搜索）。为了实现这一目标，在温度Tk降到小于0.05时，则进入开发阶段。对于高于该阈值的初始温度或其他参数配置以及不同的冷却调度策略进行调整相对较为简单。因此，在时间t处计算相应的温度Texp的过程中无需额外复杂处理。
接下来, 本文将采用指数式冷却策略来明确地设定一种通过模拟退火算法实现的能量分配机制(APS). 给定起始点s和目标位置Tb, 其能量值如下所述:
图5分别展示了当前时间t和归一化种子距离d所对应的三个值来表征接入点的行为。值得注意的是能量p\in[0,1]。此外，在开始搜索时即t=0时段内 APS 均匀地将相同的能量分配给那些具有高种子距离以及低种子距离的所有节点。随着经过时间 d 增加趋向于零时段内 APS 将会逐步向那些仅满足目标条件即' d=0 '的所有节点集中分配越来越多的能量。
实际集成
自AFL实施以来已建立能量调度机制。那么 APS 如何实现整合？现有调度机制则主要依据 s 的执行时间、输入规模以及找到 s 所需的时间等因素来分配能源。我们旨在将 AFL 已有的能源分配策略与基于模拟退火的方法相结合，并将最终整合方案建立在模拟退火基础之上。其中 pafl(s) 表示 AFL 为种子 s 分配的能量值；目标基准块 Tb 上的种子 s 综合能源配置量则由上述整合方案确定。
该系统采用模拟退火技术来调节功率因数f=2^10*(p(s, Tb)−0.5)^以实现AFL功率计划的能量增益或损耗。
图6展示了归一化种子距离d(s, Tb)在两种极端情形下模拟退火因素的行为表现。
第一种情况对应于种子距离最远的情形，在经过仅仅15分钟后（即过后），能量降低至原来的15%。当种子与目标之间的距离较为遥远时（即较远的距离），分配的能量会逐渐减少。（通过公式（12）和（13）可知：）
换句话说，在距离目标位置很远的种子s上，逐渐减少到仅分配了原始能量pafl的约三十分之一秒。
另一种情况为归一化的种子距离最小的情况，
同样可以得出结论：
一个极为接近目标位置的种子不断被赋予越来越多的能量直至其能量达到原始水平的30倍左右
系统整体架构
AFLGo由四个组件实现，即图形提取器、距离计算器、插桩和模糊器。通过与OSS Fuzz的集成，我们证明了这些组件可以在原始构建环境（例如make或ninja）中无缝集成。整体架构如图7所示。下面，我们将解释如何实现这些组件。
（1） AFLGo图提取器（GE）生成调用图（CG）和相关控制流图（CFG）。CG节点由函数签名标识，而CFG节点由相应基本块的源文件和第一条语句的行标识。GE实现为AFL LLVM过程的扩展，该过程由编译器AFL clang fast激活。编译器环境变量CC设置为afl clang fast，并构建项目。
（2） 根据第3.2节，AFLGo距离计算器（DC）采用调用图和每个过程内控制流来计算每个基本块（BB）的过程间距离。DC被实现为一个Python脚本，该脚本使用networkx包来解析图，并根据Djikstra的算法进行最短距离计算。DC生成BB距离文件，其中包含每个BB的基本块级目标距离。
（3） AFLGo Instrumentor获取BB距离文件，并在目标二进制文件中插入每个BB。具体来说，对于每个BB，它确定各自的BB水平目标距离并注入扩展trampoline。trampoline是在每个跳转指令之后执行的一段汇编代码，用于跟踪覆盖的控制流边缘。边缘由64kb共享内存中的一个字节标识。在64位体系结构上，我们的扩展使用了额外的16个字节的共享内存：8个字节用于累积距离值，8个字节用于记录已练习BBs的数量。对于每个BB，AFLGo仪器添加装配代码i）加载当前累积距离并添加当前BB的目标距离，ii）加载并增加练习BB的数量，以及iii）将这两个值存储到共享内存中。该检测作为AFL LLVM通道的扩展而实现。编译器被设置为afl clang fast，编译器标志引用BB距离文件，项目是用ASAN构建的。
（4） AFLGo Fuzzer在AFL版本2.40b中实现（该版本已经集成了AFLFast的探索计划[6]）。它根据我们的基于annealingbase的功率计划（见第3.3节）模糊了插入指令的二进制文件。共享内存中额外的16个字节通知模糊器当前种子距离。当前种子距离是通过将累积的BB距离除以训练的BB数来计算的。
参考
Academic Study of Directed Greybox Fuzzing - PDF
Academic Learning: Directed Greybox Fuzzing ( CCS‘17 )
In-Depth Analysis of Directed Greybox Fuzzing
A Summary of Related Content on Directed Greybox Fuzzing