G.O.S.S.I.P 阅读推荐 2022-08-26 DDFuzz

除了代码覆盖率，你还能找到其他引导 Fuzzing 的程序指标吗？这个问题，或许可以从数据流分析技术中寻找答案。继前天的论文推荐（爆款LibAFL）后，我们今天继续来阅读一篇由 LibAFL 作者及其所在团队 EURECOM S3 在 Euro S&P '22 上发表的工作–Fuzzing with Data Dependency Information

相信很多人在使用 LLVM，angr 等程序分析框架时就已经接触过数据依赖图 Data Dependency Graph（DDG）的概念，它表示了变量之间的 def-use 关系，我们可以借助这样的依赖关系更清晰地找到导致漏洞的结构体。作者也是基于这一点观察，思考能否将 Fuzzing 的过程中 DDG 边的变化也加入到反馈机制当中，从而触发那些在传统的 CFG 边覆盖率引导的 Fuzzing 中检测不到的漏洞。

为了实现这样的 Fuzzer，作者选取了 LLVM Pass 作为分析工具，一方面因为其 SSA 形式的 IR 更容易恢复出数据依赖关系，另一方面则是其更容易集成到已有的 Fuzzing 工作中，例如本文就选取了由作者开发的 AFL++。事实上，LLVM Pass 已经内置了生成 DDG 的 Pass (https://llvm.org/docs/DependenceGraphs/index.html)，但其实现方式开销很大，影响了 Fuzzer 的性能。所以作者用自定义的 Pass 实现了 DDFuzz（滴滴Fuzz？），其工作流程包含三个阶段：

1. DDG 构建：维护一个数据流映射关系，遍历基本块的所有指令，根据指令类型添加映射关系，并不断更新DDG；

2. 依赖关系过滤：Pass 同时收集了 CFG 和 DDG 中的反馈，虽然两种反馈对于 Fuzzing 的影响不同，但仍有交集，所以需要避免重复和无意义的插桩。作者采用了两条过滤规则来过滤那些已经在 CFG 中包含了的依赖关系：

   a) 过滤掉前驱/后继节点中的依赖关系

   b) 过滤掉支配树上的依赖关系

   
   经过过滤后，我们得到的 DDG 有如下性质：对于 DDG 中的一个 use 点，至少对应2个及以上的 def 点。即如上图所示的情况，即使能够达到 100% 地覆盖 use 点，也不能只靠 CFG 恢复出依赖关系。

3. 生成插桩对象：DDFuzz 仍保留了 CFG 中通过异或运算+位图来统计边覆盖率的插桩方法，来指导探索更多的执行路径。而 DDG 中相邻的基本块，在 CFG 中可能夹杂了其他的基本块节点，不能直接采用 CFG 中的插桩方法。作者因此提出了一种流敏感的扩展方法：对于 DDG 中包含 def 点的基本块都插入一个标记变量，并在该基本块中对标记变量进行赋值，随后在包含 use 点的基本块将所有标记变量进行异或，并作为位图的索引。如下图所示，DDFuzz 对 X 和 Y 两个基本块进行了插桩，并在 Z 基本块进行了统计。

为了验证 DDG 辅助传统 Fuzzing 工作的有效性，作者在3类数据集上，从漏洞检测，性能开销，代码覆盖率和种子队列爆炸四个方面对 DDFuzz 进行了全面的评估。

首先，作者针对性地选取了 10 个项目作为数据集一，通过编程经验将它们分为强数据依赖型（上）和弱数据依赖型（下）两类，如下图所示；此外，作者还选取了 FuzzBench 中的 22 个项目作为数据集二，以体现在大规模代码库中的效果（至于为什么不选择 LAVA-M 和 MAGMA，请自己看文章哦）；最后，作者还考虑了在 USENIX Security ‘19 上的一篇同样研究 Fuzzing 中数据依赖关系的论文 GRIMOIRE， 将其中包含的 6 个项目作为数据集三。

作者使用了 AFL++ 的基础设施进行了实验。首先，作者计算了被插桩的基本块占所有基本块的比例（即DD ratio）这一参数，用数据证明了他们区分两类项目的合理性。从下图中可以看出，在强数据依赖型项目的漏洞检测上，DDFuzz 比传统的覆盖率导向的 Fuzzer 表现更好。进一步，对两种 Fuzzer 检测出的漏洞进行去重和对比，作者发现 DDFuzz 还能检测出很多之前发现不了的漏洞。但在弱数据依赖型项目上，DDFuzz 则表现欠佳。之后，作者通过 P-value 的统计分析证明了，DDFuzz 的表现受项目本身数据依赖关系的影响很大，当分析项目为弱依赖型时，DDFuzz 和 AFL++ 差别不大。

对于性能开销的分析，作者主要关注其依赖关系过滤策略的有效性，将 DDFuzz 使用的 DDG 与由 LLVM 生成的 DDG 和过滤之前的 DDG 进行对比。作者发现其他两类 DDG 由于其开销过大，很容易触发 AFL++ 的超时机制，而经过剪枝后的 DDG 降低了插桩数量，从而提高了程序的执行速度。

此外，作者还将 DDFuzz 使用的插桩方式和其他插桩方式（Ngram2，Ngram4 和 Ctx）在漏洞检测和代码覆盖率上的表现进行了对比。作者发现，尽管不存在某个检测漏洞最多的插桩方式，但 DDFuzz 的优势在于发现不同的漏洞。而在代码覆盖率上，DDFuzz 则表现一般，只取得了比 AFL++ 更好的结果，这和作者设计 DDFuzz 的预期也是符合的。

作者随后将 DDFuzz 和 AFL++ 都放到了 FuzzBench 上进行测试，发现 DDFuzz 只有在发现漏洞数目的几何平均（Geomean）数上表现得更好，从整体发现的漏洞数目来看则逊于 AFL++ 。但具体到某个项目上，作者仍然证明了 DDFuzz 具有发现不同漏洞的优势。同时，作者还手动统计了这些项目的 DD ratio，验证了其作为区分强/弱数据依赖型项目标准的合理性。

最后，作者对 DDFuzz 挖掘出的漏洞类型进行了分析。如下图所示，相比于只使用 AFL++，DDFuzz 更容易发现缓冲区溢出类漏洞（之后会不会因此把 DDFuzz 的功能集成到 AFL++ 中呢？

作者还统计了关于数据集三的结果，并抽取了 tcc 中的一个漏洞作为样例分析～

---

论文地址：https://s3.eurecom.fr/docs/eurosp22_mantovani.pdf

论文Artifact：https://github.com/elManto/DDFuzz

原文始发于微信公众号（安全研究GoSSIP）：G.O.S.S.I.P 阅读推荐 2022-08-26 DDFuzz