fuzz

发布日期: 2024-05-05

DAFL论文学习

概述

本文是一篇关于定向灰盒模糊测试的介绍，首先对一些简称进行概述：

DAFL:本文的模糊测试模型
DGF:定向灰盒模糊测试
CFG:控制流程图
Beacon:针对第一个挑战提出计算达到目标的最弱先决条件
AFLGo、HawkeyeWind、Ranger:之前的提出模糊测试器，主要针对第二个挑战
DUG:数据依赖图

现在的DGF有两个关键机制：

1.DGF通过支持传统(无向)灰盒模糊测试中覆盖新执行路径的测试用例来发展测试用例。

2.DGF通过权衡每个测试用例的优先级，根据控制流图(CFG)中执行节点和目标节点之间的距离，为到达目标程序点的模糊测试员提供指导。

同时存在这两个方面仍然存在挑战：

1.代码覆盖率会给DGF带来负面反馈，因为fuzzers可以获得更多的覆盖范围，他们就可以被引导到与目标执行无关的路径上。当目标程序很大时，这个问题会变得更糟，因为它可能包含更多不相关的代码部分。Beacon针对第一个挑战提出计算达到目标的最弱先决条件，但是从现实世界的程序中精确地获得最弱的前提条件是不可行的。

2.AFLGo、Hawkeye和Beacon——通过考虑CFG中所有已执行的节点来计算一个测试用例的种子距离，即优先级分数。然而，它们的距离机制可能对不相关的节点给出错误的引导，特别是当程序很大时，因为长执行路径可能包含许多与目标在语义上不相关的节点。WindRanger提出的DBB也有时无法达到预期。

本文提出的建议：

1.首先，选择性覆盖检测通过仅从与目标执行相关的代码部分收集代码覆盖信息来减少负面反馈。

2.提出了语义相关性评分，计算到DUG的种子距离。

GitHub代码：https://github.com/prosyslab/DAFL-artifact

案例分析

本文通过CVE-2017-7578对这两个挑战进行分析。

程序首先打开一个文件(第9行)，并通过迭代for循环从文件中读取输入数据流，程序将整数46分配给变量类型(第14行)，该变量用于间接调用解析器函数parseSWF_DEFINEMORPHSHAPE(第30行)，数组的大小是8(第35行)，而索引变量i可以有一个任意大的数字，这取决于用户输入(第36行)，因此会在第42行崩溃：

1 struct SWFblock {
2 int type;
3 SWFParseFunc parser;
4 };
5
6 struct SWFblock blks[80] ={ { 46, parseSWF_DEFINEMORPHSHAPE }, ... };
7
8 int main(int argc, char *argv[]) {
9 FILE *f = fopen (argv[1], "r");
10 SWF_Parserstruct *block;
11 for (;;) {
12 if(/* not enough data in the file */)
13 break;
14 int type = fgetc(f);		// 获得文件类型整数46
15 int length = fgetc(f);	// 获得文件长度
16 if (length == 63) {
17 if(/* not enough data in the file */)
18 break;
19 ...
20 } else {
21 block = blockParse(f, type);
22 }
23 ...
24 }
25 }
26
27 SWF_Parserstruct *blockParse(FILE *f, int type) {	// 间接调用解析器
28 for (int i = 0; i < 80; i++) {
29 if (blks[i].type == type)
30 return blks[i].parser(f);
31 }
32 }
33
34 SWF_Parserstruct *parseSWF_DEFINEMORPHSHAPE(FILE *f) {	// 存颜色信息
35 SWF_MORPHGRADREC GradientRecords[8];
36 int i = fgetc(f);
37 parseSWF_RGBA(f, &GradientRecords[i]);
38 ...
39 }
40
41 void parseSWF_RGBA(FILE *f, struct SWF_MORPHGRADREC *gradient) {
42 gradient->StartColor = ...; // crash location
43 ...
44 }

挑战1：负面反馈

DGF

传统的DGF选取相关联的子函数进行制图，虽然可以根据用户输入调用80多个不同的函数，但只有一个函数，即parseSWF_DEFINEMORPHSHAPE，与目标bug相关。

Beacon的弱前提

Beacon通过修剪无法到达目标的不可行的路径来缓解这个问题，比如可以发现type的值(在第14行和第29行)应该是46，让执行流不去别的地方，但是由于main和blockParse函数的控制结构复杂，Beacon无法从它们推断出任何前提条件。

挑战2：误导距离参数

AFLGo

通过计算AFLGo通过取执行节点与目标节点之间距离的平均值来计算sA的种子距离，比如下图一个卡在12行一个卡在17行，算出来SA比SB离结点更近，但是明显SB更加优秀。

WindRanger

WindRanger计算执行节点子集与目标节点之间距离的平均值。它通过考虑cfg中使执行偏离目标位置的节点来选择称为偏离基本块(DBB)的子集。但当涉及环路等复杂控制结构时，基于dbb的距离度量也会对制导产生误导。

DAFL概观

DAFL主要分为两个模块：静态分析阶段和模糊测试阶段。

静态分析阶段

DAFL将带有带注释的目标位置的程序作为输入，并运行过程间静态分析，以识别目标位置依赖于数据的所有语句，分析返回一个Def-Use Graph (DUG)和一组关于目标点的相关函数。同时会分析仅检测目标程序中的相关功能，以便在下一个模糊测试阶段中选择性地仅从程序的相关部分接收覆盖反馈。

模糊测试阶段

在模糊测试阶段，DAFL像传统的灰盒模糊测试一样迭代地运行仪器化的程序，但由于选择性的覆盖率检测，它只能从相关函数中获得代码覆盖率。并且用一种新的方法称为语义相关性评分。

选择性覆盖检测

为了识别这些相关部分，我们从DUG上的目标位置开始向后遍历程序，并收集所有依赖语句。虽然这组节点包含与目标位置在语义上相关的部分，但数据依赖关系可能会错过决定目标位置可达性的关键条件语句(即控制依赖关系)，比如会丢失上面的29行代码。

为了解决这个问题，直接选择相关联的整个函数，并测量了功能中的所有节点以接收覆盖反馈。这反过来又包括与数据依赖关系密切相关的控制相关节点，同时防止过度过度逼近（找不到其它有关的行）。

语义相关性评分

我们将种子输入的分数定义为DUG中执行节点的语义相关性分数的总和，其中每个节点的分数是根据与目标点的接近程度来定义的。具体来说，我们将分数1分配给最远的节点，并将最大分数(即最远节点到目标的距离)分配给距离目标最近的节点。

设计

DAFL实际上可以理解为一个程序，它接受一个程序P和一个目标程序点t作为输入，并返回一组发现的崩溃测试用例。

DAFL流程图

G,F	<- Slice(P,t)	// P为程序，t为目标位置；G为DUG，F为G覆盖的一组函数
P' <- SelectiveCovlnstr(P,F)
Pool <- InitializeSeedPool()	// 初始化种子池
Crashes <- {空集}		// 初始化崩溃集
while not timeout do	// 规定一个fuzz时间
	s,scr <- Choose(Pool)	// 选择一个种子
	e <- AssignEnergy(scr)	// 根据语义相关性为s分配能量，该能量用于决定产生多少突变种子
	for e times do
		s' <- Mutates(s)	// 将测试数进行突变
		cov <- MeasureCov(P',s',F)	// 覆盖结点
		scr <- ComputerScore(P',s',G)	// 计算得分
		if cov has any gain then	// 如果有得分
			Pool <- Add(Pool,s',scr)
		if s' crashes P' then	// 如果使程序崩溃
			crashes <- crashes U (S')

Slice程序切片

x = f ();
y = g ();
p = &y;
z = x + *p;

如以上的程序，由于第4行中的变量z受到变量x、y和p的影响，因此简单的切片算法将返回第1-3 行。而实际的值复制是通过第1行和第2行执行的。也就是说，我们可以从示例程序中获得一个紧凑的切片，它只包含第1行和第2行。薄切片通过忽略指针解引用的数据依赖性来解决这个问题。然而，正如之前讨论的那样，由于过度逼近，收集所有数据和控制相关的节点是不切实际的。

因此在实际中，P的DUG具有与CFG相同的节点集，但它包含数据依赖边而不是控制流边。所以使用薄切片，仍然需要知道每个指针变量指向哪些变量。最后根据得到DUG，对它进行修剪得到G结点和目标T之间的关系。

种子调度

语义相关性评分

1.使用种子的程序执行在G中练习了更多的节点

2.使用种子的程序执行更接近目标点的节点，我们会给种子更高的分数。

实际为结点赋分的规则是：$$Score_{G,t}(C)=L-|c-t|+1$$（其中L为t和G之间的最大距离），得分为经过路径的求和。

种子库管理

我们基本上将种子池保持为一个循环队列，并按顺序选择种子。对已经使用的种子按照评分高低进行排序。

能量分配

同时根据语义相关性的评分来衍生种子的突变体。为了从有希望的种子中获得更多的突变体，我们将更多的能量分配给具有更高相关性分数的种子输入。与传统的AFL相比，DAFL的能量再乘上$$scr_s/scr_{avg}$$

评测

评估方面

1.DAFL在复制目标bug方面有多快？

2.切片策略的选择如何影响DAFL的性能？

3.我们的技术(选择性覆盖检测和语义相关性评分)如何影响模糊测试结果的性能？

评估标准

1.崩溃类型和崩溃线与PoC的崩溃类型和崩溃线是否相同

2.检查崩溃行的直接调用者是否匹配

3.检查PoC堆栈跟踪中出现的所有函数是否包含在我们崩溃输入的堆栈

检测结果

图一：DAFL与基线工具的性能比较。每个柱状图表示每个主题在每个工具上花费的总时间(包括静态分析和模糊分析)的总和。请注意Y轴(表示TTEs)是对数刻度。

图二：该图为各个CVE的fuzz时间，其中Tf为模糊过程时间中纯粹花费时间，Tf+sa为静态和模糊测试时间，每个数字为40次重复实验的中位数，NA为超过一半无法还原CVE。括号表示fuzzer能够复制错误的次数。

DFAL不足

比如以下的例子：要触发29行的目标bug，必须从decompileAction中依次调用push和decompileGETPROPERTY函数。因此，在检测目标中包括decompileAction对于发现探索这些函数的输入非常重要。然而，反编译action通过过程间控制依赖关系而不是数据依赖关系与目标位置相关。当decompileAction调用带有两个参数的decompileGETPROPERTY时，decompileGETPROPERTY在调用getInt时不使用这两个参数。相反，它从全局数组中弹出idx，并将其用作getInt的参数。因此，在decompileAction和 decompileGETPROPERTY之间没有数据依赖关系。

因此，DAFL可能无法识别对触发目标错误至关重要的程序行为。所以可以在改进切片方法上做工作。

1 int stack[100];
2 int stack_pointer = 0;
3
4 void push(int* idx){
5 stack[stack_pointer++] = *idx;
6 }
7
8 int* pop(){
9 int idx = stack[--stack_pointer];
10 return idx;
11 }
12
13 int decompileAction(int n, SWF_ACTION *actions){
14 switch(actions[n].ActionCode){
15 ...
16 case SWFACTION_GETPROPERTY:
17 decompileGETPROPERTY(n, actions);
18 break;
19 case SWFACTION_PUSH:
20 int* data = actions[n].data;
21 push(data);
22 break;
23 ...
24 }
25 }
26
27 int decompileGETPROPERTY(int n, SWF_ACTION *actions){
28 int idx = pop();
29 getInt(idx); // Crashing function
30 }

薄切片的影响

在大多数情况下，DAFL和DAFL naive都优于AFL。这是因为这两种切片策略都可以有效地过滤掉不相关的函数。即使是朴素切片也可以平均减少57%的仪器函数的数量，而薄切片提供了更有效的过滤，平均减少了76%的函数。总体结果表明，薄切片为定向模糊提供了更有效的指导（与原始方法相比，薄切片方法的模糊性能平均提高了2.01倍）。

图三：薄切片的影响，Tsa为包含切片时间的静态分析时间，Tf为模糊化时间。