Constraint-guided Directed Greybox Fuzzing

难点

有导向的黑盒测试没有考虑有序的目标点和数据条件。本文提出的有约束条件导向的测试方法，将约束定义为目标点和数据条件的组合。并且驱动种子按照顺序满足有顺序的约束。

解决方法

提出新的约束距离来判断seed的优劣，约束距离需要考虑到两个方面，一是有顺序的目标点，二是数据约束，同时提出自动化产生约束的方法。

背景

DGF技术在重现崩溃时非常有用，但是耗时较长，主要是两个方面：1、DGF假设目标点是相互独立无序的，2、DGF没有考虑崩溃所需的数据条件。

介绍

CDGF要求种子满足一连串的约束条件，为了衡量种子对约束的满足程度，CDGF将种子距离定义为约束条件的距离，而不是传统的DGF中到目标点的距离。同时提出了从crash dumps和补丁日志自动生成约束的算法。

在DGF中，每个代码块被赋值为到所有目标点最短路径的调和平均数，种子的距离被定义为代码块的平均值。通常来讲，种子能覆盖更多的目标点，种子距离越小。

这里说是调和平均数，但是通过计算公式，调和平均数应该是倒数相加除以数量再取倒数，但是找了原文：Directed Greybox Fuzzing中，以及文章中给出的计算公式，是倒数相加取倒数，没有除以数量这一过程。也就是在DGF中的函数间调和平均数的概念不一样。但是在这里只用于区分代码块距离目标点的远近，所以少一个倍数对结果没有影响，由于调和平均数能够反映出更小的值对平均结果的影响，所以在这里用来区分代码块远近是很不错的选择。

因此CGDF定义种子距离更短的条件定义为：能满足更多的约束条件和能满足更靠前的约束条件。对于一个独立的约束而言、距离为到达目标点和数据条件的距离和；对约束序列而言，将各个约束的距离结合起来考虑。

根据详细例子，在目标点触发上，就是能达到未触发的site的最短距离加上max/或者认为是inf，这样如果seed没有按照顺序完成约束、也能在现有的seed中做出排序。而在数据约束上，则根据给出的条件计算分值，例子中是访问点与溢出点的距离，自然越近的seed距离越小。

距离描述

一个约束的距离可以分为target距离和data距离

target距离定义如下

target距离定义为现在的基本块到target site之间的距离

data距离以下面的condition为基础

在满足condition时，距离为0，反之就是d(n)，如果未到达target site，data距离定义为INF*条件数，如果有多个条件，则定义为未满足的条件数*INF+ min(INF, min(d(n))，这里min(d(n))是现有的满足的条件中最短的距离。如果是assert条件，则只有0和INF两种情况。

那么，约束距离定义为目标距离和数据距离的和。

分为三种情况，即未到达target、未满足data condition、满足，各自详细情况已经讲过了。

最后来计算总距离：

一个CDGF总是由一个及以上约束组成，所以

其中 $c_{con}$ 是设定的一个约束的最大距离，其思想与多data condition中的计算一致， $\tau^n$ 是约束序列中第一个未被满足的约束的下标。

最后，一个种子的距离设定为执行过程中最小的距离。

约束生成

通过设计可以从crash dump和补丁日志中生成约束。

crash dump

设计了三种模板，nT模板（多个traget site）支持uaf、double free、use of uninitialized value崩溃，2T+D模板（2 target site +data condition）支持buffer overflow崩溃，1T+D （1 target site +data condition）支持assertion failure和除0崩溃

nT模板

对于uaf double free，只设置%cause和%crash约束，对于use of uninitialized value，使用三种约束，其中%trans约束用来表示传递变量的过程。

2T+D模板

在2T+D中，处理的都是buffer overflow模板，所以设置了buffer的分配点和访问约束，其中assert条件保证访问合理，而cond则使访问点不断向缓冲区边界靠近。

1T+D模板

在这种模板里，只是制定了一个target和data condition。

补丁日志

从补丁日志中生成的是根据1T+D模板生成约束，

根据几条规则来生成约束：

新的异常检测被引入：target site设置为原位置、data cond设置为新的异常条件。异常条件可能由throw等关键字带出
分支条件被改变，将target site设置为被改变的条件位置，data_cond设置为新老条件的互斥。
如果变量被替换，则target site为被替换的变量，data cond为新老变量值不相等。
如果前面的规则不适用，则变为nT模板，并将target site设置为所有被修改的地方。

当然了，从规则可以发现，规则并不一定适用于所有补丁日志，补丁日志中可能不是只修改了一个地方。所以如果改变的位置不止一个，就将所有改变的位置与一个哨兵函数联系起来。将target site设置为哨兵函数，即将这些点插入一个哨兵函数的调用，所以到了这些地点就会触发哨兵函数。

CAFL设计

编译器

源码和约束会在编译器中一起编译，进行固定点位的插桩，并且在fuzz中对seed进行有顺序的排列，优先处理距离短的种子。

为了计算target距离，编译器会首先构建程序的调用图。在target测量上，编译器从每个target site开始，计算基本块的目标点距离并插入检查点调用，然后递归调用图和控制流图，直到到达主函数（也许这里是基本块）。

运行时

这里提出了CAFL运行时的概念，在fuzz时，运行时通过检查点使用target距离反馈来保持对种子距离的跟踪。二进制文件会转发出一个包含约束下标和距离的元组。

在跟踪距离的同时，运行时通过共享内存向fuzzer报告当前种子的距离，和当前的约束条件。

fuzzer

fuzzer要做的有种子打分和种子的排序。

打分公式同时考虑了种子距离和种子深度，也就是种子距离与fuzz时间、种子卡住深度的乘积，其中cfuzz和cstuck均小于1，那么距离越短、fuzz时间越短、卡住深度越小，都能使得得分更多。

当有一个种子比当前最大分数大时，会创建一个新的种子。

在种子选取上，CAFL并不以得分高的优先选取，而是按照概率选择，首先将得分递增排列，选取的几率为1/EXP(R(s))，R(s)为种子的排序

总结

在结果上，使用nT相比AFLGO有一定提升，使用nT+D有显著提升。但是仍然有不能正确识别错误数据的bug。

约束可以从git这样的版本控制软件日志中生成。

讨论

CAFL还有更好的使用方法，可以生成遵循特定执行路径的约束，或者找到崩溃的根本原因。

CAFL无法覆盖栈溢出调用漏洞。

如果崩溃的原因与接近崩溃的条件完全无关，则fuzz效率极为低下。

在缓冲区溢出bug中，data cond还不够有效地区分输入。

在关于指针的data cond的距离计算上，效果不太好，因为只要差一点点，指向的就是不同的对象。

不懂的地方

2T+D中的assert和data cond互斥

排序上，得分越高的种子选取概率越低。

最终的fuzz结果取决于constraint生成的结果，所以在生成约束部分比较重要。