🤔

Titan : Efficient Multi-target Directed Greybox Fuzzing

作者

传统方案

传统定向模糊测试只能针对单一目标，且现有方法没有意识到目标之间的相关性，因此随着目标数量的增加，可能会退化为无定向模糊处理。最终，模糊器无法有效地为多个目标选择种子和生成输入，我们称之为协同无知问题。

现有的定向模糊测试方案通过寻找最接近目标的潜在种子来提高直接性，以及通过拒绝无法达到目标的输入来避免能量浪费。

传统的距离算法

• AFLGo：将测试输入到目标基本区块的距离定义为区块 B 与目标之间的平均距离，其中 B 的范围是输入执行路径所到达的区块。
• Hawkeye：通过考虑调用轨迹的相似性来优化距离度量，其直觉是漏洞是由一连串调用指令而非单一程序点触发的。
• CAFL：通过观察到在触发崩溃之前应到达多个前置点来进一步提高度量的精确度。因此，它设置了漏洞崩溃转储中的所有调用点，并要求模糊器按顺序到达这些调用点。
• MC2：将定向模糊转化为蒙特卡洛计数模型，并利用每个分支的执行频率来近似估计达到目标的难度，并优先选择达到目标难度最低的种子。

种子剪枝方案

• FuzzGuard：训练了一个分类器作为预测器，以过滤测试输入，从而使达到目标概率较高的输入以较高的优先级执行。
• Beacon：由于重现错误应满足路径条件，因此它以可证明的方式进一步完善了剔除功能。它使用静态分析来推断达到目标的先决条件，并在执行过程中违反先决条件时删除输入。

阻碍现有定向模糊器高效覆盖多个目标的主要问题是，它们无法区分不同目标之间的相关性，主要表现为路径条件重叠、冲突和独立。

作者方案

为了解决协同无知问题，我们的主要见解是模糊器可以利用多个目标可行条件之间的相关性，即独立性和矛盾性，来协同生成针对这些目标的输入。更具体地说，如果我们获得了与给定目标相关的变量的解空间，模糊器就可以区分目标之间的相关性，从而精确地指导种子调度和突变，从而高效地达到多个目标。

如果此时存在两个个种子$A(a,b,c,d):(6,3,1,1)$，$B(a,b,c,d):(5,0,3,1)$

• 首先，矛盾相关性表明触发这些目标的条件是否存在冲突。因此，我们可以为满足不同目标条件的种子分配不同的优先级。例如，$target\ 1$和$target\ 2$对变量$b$的条件有冲突（即$b>1$和 $b\le1$）。因此，模糊器可以对$target\ 2$使用种子$A$，对$target\ 1$使用种子 $B$​，以提高种子调度的有效性。
• 独立性相关性表明，多个输入字节可以独立影响不同的目标。因此，模糊器可以尝试同时改变这些输入字节，以接近多个目标，从而减少达到目标所需的执行时间。例如，在例子中，由于 a 和 d 是独立的，模糊器可以针对$target\ 1$和$target\ 3$同时改变它们的值。

我们首先根据不同目标的路径条件近似值发现它们之间的相关性。然后，我们通过检查目标的近似值是否冲突来确定目标之间的相关性。因此，模糊器可以通过识别和使用相关性，而不是仅仅依赖控制流距离，获得对多个目标的精确反馈。

条件的关系显示了检测多个目标的潜力。如果我们能对这些关系进行精确推理，定向模糊就能有效地达到多个目标。首先，模糊器可以利用冲突相关性来区分到达不同目标（如目标 1 和 2）的难度，从而更准确地为多个目标选择种子。其次，模糊器可以通过使用独立相关性为多个目标更有效地生成输入，例如，同时改变目标 1 和目标 3 的独立字节 b 和 d。

利用新的细粒度反馈，我们引入了两种优化的输入生成技术：

1. 协同感知调度策略，通过对种子进行细粒度排序，找到可能到达最多目标的种子。
2. 以多目标为导向的突变，可生成接近多个目标的输入，并减少所需的执行次数。

静态条件推断器

给定一组目标程序点，我们设计了两阶段静态分析：推断达到每个目标的先决条件，以及计算区分多个目标的相关性。

先决条件推断: 首先，我们将前提条件推断为达到目标代码的程序变量的必要条件。为了便于计算条件，我们利用区间域来过度近似达到目标的路径条件的可行搜索空间。从形式上看，静态分析可以推断出以下信息

$Definition1(Multi-target\ Reachability\ Summary)$: 给定一段程序目标点$T\subseteq N$，多目标可达性总结表达为$\bigcup_{t\in T}S_t$，其中$S_t(n)\sube Var\times Interval$并且$(v,itv)\in S_t(n)$。表明要达到目标程序点$t$，在执行程序点$n\in N$之前变量$v$必须位于区间$itv$​中。

通过$Definition1$在之前的例子中可以推断出如下数据

$S_{t1}(l_5)=flag:[1,1],a:(5,+\infin),b:[0,1]$

$S_{t2}(l_5)=flag:[0,0],a:(5,+\infin),b:(1,+\infin),c:(2,+\infin)$

$S_{t3}(l_5)=d:(3,+\infin)$

其中$l_i$表示在$i$行之前的程序位置，$S_{t1}-S_{t3}$表示$target1-target3$

相关推断: 不同目标的推断变量范围可能存在许多相关性。例如，考虑上例中的多目标可达性总结。到达$target1$和$target2$都需要相同范围的变量$a$，但它们对变量$b$的范围有排他性要求：

$Definition2(Correlation\ among\ Multiple\ Targets)$: 假设静态分析结果为$\bigcup_{t\in T}S_t$，给定变量$v$和程序点$l$，我们定义条件是否重叠、独立、冲突如下

$independent(v,l,t_1,t_2)=(v\in S_{t1}(l)\wedge v\notin S_{t2}(l)) \vee (v\in S_{t2}(l)\wedge v \notin S_{t1}(l))$

$conflict(v,l,t_1,t_2) = S_{t1}(l)(v)\cap S_{t2}(l)(v) = \oslash$

$overlap(v,l,t_1,t_2)=S_{t1}(l)(v)\cap S_{t2}(l)(v)\neq \oslash$

通过$Definition2$在之前的例子中可以推断出

$overlap(a,l_5,t_1,t_2)$

$conflict(b, l_5,t_1,t_2)$

$independent(c,l_5,t_1,t_2)$

$independent(d,l_5,t_1,t_3)$

$independent(d,l_5,t_2,t_3)$

协同定向模糊测试

协同感知种子调度

首先，我们根据图 2 所示的直觉来确定种子应考虑的目标。具体来说，如果到达的变量属于重叠相关或独立相关（如图 2 中的 a) 和 c) 所示），我们就认为种子可以到达这些目标，因为相交的搜索空间表明它们可以同时被覆盖。我们使用冲突相关性为当前种子筛选目标：如果当前种子无法满足目标的先决条件，我们可以暂时不考虑该目标。

$Example$：假设目前存在两个种子$A(a,b,c,d):(6,3,1,1)$，$B(a,b,c,d):(6,0,1,1)$。将它们分别用于$target1$和$target2$。根据种子执行中观察到的 b 值，我们认为 A 更有可能触发目标 2，而 B 则更有可能触发目标 1。

其次，我们需要对种子的重点目标进行优先排序，因为达到每个目标的难度都可能不同。具体来说，我们把达到一个目标视为满足相关联的多个变量的条件。应该优先考虑其值满足大多数变量条件的种子输入。因此，我们通过分析执行反馈来检查执行过程中满足的前提条件的数量。例如，在前面的例子中，由于 B 满足了目标 2 的 a 和 b 这两个变量的前提条件，而 A 只满足了目标 1 的 a 这一个变量的前提条件，因此我们将 B 优先于 A。因此，通过细粒度的反馈测量，我们可以选择最有希望的种子来覆盖多个目标。

面向多个目标的突变

我们在每次运行时对接近多个目标的种子进行突变，以减少多余的执行次数。我们利用独立相关性来改变与独立变量相关的多个字节。具体来说，我们首先使用基于推理的污点分析，动态推断出可影响自相关变量值的输入字节。然后，我们分别对影响自变量的字节进行突变，从而使模糊器能够以较少的突变接近多个目标。

Q1: 污点分析的性能开销?

静态协同推理

对于每个程序点$v'$，算法通过迭代应用每个程序语句stmt的语义转移函数$transfer$，计算出到达$t$的前提条件(第 5-7 行)。根据计算出的multi-target reachability summary，可以根据$Definition4$​得到一个种子的多个目标之间的相关性。

$Definition4(Correlations\ of\ a\ seed)$: 给定一个种子$S$，假设$S$可以到达程序位置$(v_1,l_1), ...,(v_n,l_n)$，其中变量$v_i$在$l_i$定义，则种子$S$的相关集为

$C(S)=\{r(v_i,l_i,t_j,t_k)\}|i\in(1,n),r\in\{independent,conflict,overlap\}$ 其中$(t_j,t_k)$为目标对

​