The LLVM framework applies some optimizations to construct its internal Dependence Graph [5], such as considering strongly connected components as a single node (the so-called P-Node).

Code：

https://github.com/elManto/DDFuzz

Paper(Marked)：

在AFL基础上引入 data dependency graphs（DDGs）

1. 背景/出发点

作者认为DDGs中的信息可以为fuzzer提供一个CFG无法捕捉到的额外的feedback

作者基于AFL++和LLVM，在Fuzzer通过CFG奖励的同时，在探索新的DDG edge的时候也会得到奖励——DDFuzz

1.1 数据依赖图 Data Dependency Graphs

介绍link→传送门

2. 实现 Methodology and Implementation

借助LLVM pass实现，版本LLVM13

选择LLVM的原因：首先，中间表示IR是 静态单赋值（Single Static Assignment，SSA）形式，这意味着每个变量只分配一次，所有变量必须在第一次使用之前定义， 这简化了与允许使用多个定义的其他代码表示相关的LLVM IR变量之间的依赖关系的恢复；其次，LLVM工具链已经很好地集成到流行的Fuzz项目中，因此新解决方案可以很容易地在现有的Fuzz技术中实现。

DDFuzz实现过程将分为三个主要部分： DDG构建、依赖过滤和目标检测。

2.1 DDG构建

实现静态分析部分时，首先要选择合适的LLVM IR变量来构建数据依赖图。最直观的方法是通过依赖 def-use edge 来表示依赖关系，来恢复LLVM IR中出现的每个变量的依赖关系。然而，作者注意到，这种技术并不适合该技术的应用环境。这是因为IR的SSA形式会产生太多的依赖关系，反过来将导致fuzzer的反馈不佳，执行目标二进制文件时将产生巨大的开销。

LLVM 框架本身可以构造 internal Dependence Graph, 例如将强链接的组件作为单个节点 （strongly connected components as a single node (P-Node)）。本文将这个称为$DDG_{raw}$。