首页
社区
课程
招聘
[原创]基于覆盖率的Fuzzer和AFL
发表于: 2023-6-27 09:11 19523

[原创]基于覆盖率的Fuzzer和AFL

2023-6-27 09:11
19523

模糊测试器的分类方法方式有好几种,本文将着重介绍基于覆盖率的模糊测试器,因此只详细介绍根据fuzzing策略的分类。基于fuzzing的策略,可将fuzzer分为基于定向的fuzzing和基于覆盖率的fuzzing。
对于基于覆盖率的模糊测试工具来说,往往需要使用恰当的种子测试目标程序,基于目标程序的反馈引导种子的变异生成更多恰当的测试用例,以引导测试覆盖尽可能多的代码路径。之所以用覆盖率这一个指标做为衡量,是因为在实践中人们发现更高的覆盖率往往能够找到更多的bug。
然而在实际场景中,一个项目中大部分代码都是不包含bug的,而且实际过程中,对于覆盖率模糊测试,仅靠依靠模糊测试器自己盲目测试是几乎不可能达到极高的覆盖率。定向模糊工具正是基于上诉原因应运而生。因此对于定向模糊测试工具而言,其目的旨在快速的测试特定的目标位置是否可能存在bug。(定向模糊测试工具并非本文的着眼点,因此将略过。)

基于覆盖率的模糊测试策略是最先被完整应用的,在长时间的应用中十分可靠,高效且有效。对于基于代码覆盖率的Fuzzer来说,我们先讲一个重要的概念,代码覆盖率(Code Coverage),其次我们再介绍基于覆盖率的Fuzzer的一般工作流程,最后我们简单的介绍以下fuzzing另一个重要的概念种子语料库(Seed Corpus)。

代码覆盖是软件测试中的一种度量,描述程序中源代码被测试的比例和程度,简单的说即测试目标代码的覆盖程度,所得比例称为**代码覆盖率。**代码覆盖率的度量方式主要有基本快覆盖、边覆盖率、条件覆盖率。
基本块(Basic Block)是具有单一入口和单一出口的代码片段,即一组顺序执行的指令。如下图,IDA中CFG图的代码块即是一种基本块。
一个基本块从其中第一条指令执行开始,直到执行到最后一条指令才结束(跳转到其他块)。也即,单一入口是指只能从基本块的第一条指令进入基本块,单一出口是指只能从基本块的最后一条指令跳转离开。
所谓基本块覆盖率即统计代码中基本块执行的情况,那些基本块执行了,那些没有执行。用执行了的基本块除于总的基本块即是基本块覆盖率。

边的概念也是依托于基本块的概念,基本块之间的跳转若用一条线画出来,这条线就叫做边。如下图所示。
所谓边覆盖率则是统计基本块之间的分支跳转的情况,也即统计那些边被执行了,那些边没有。相信诸位眼尖的可能发现了,边覆盖率能够覆盖相比于基本块覆盖率,虽然代码执行语句上似乎并无区别,但覆盖了更多的代码逻辑。

我们用一个例子来说明。如下图所示,有BB1、BB2、BB3和BB4,四个基本块。若执行路径BB1->BB2->BB3->BB4,则以基本块覆盖率来说,我们可以理所当然的说,覆盖率已经达100%了。
但是我们却发现代码中许多隐含的逻辑并未被测试出来。例如,我们走BB1->BB3->BB4和BB1->BB2->BB4,显然用基本块覆盖率来衡量自然是100%,但是却展示了一种全然不同的代码逻辑。
我们发现,若我们以边的执行程度来衡量,当所有的边被访问时,此时基本块覆盖率必然100%,并且还挖掘出许多隐含的代码逻辑,也是说,不但代码测的全还测的更加彻底。

我们以《Fuzzing:a survey》给出的覆盖率Fuzzer的一般工作过程的伪代码做为例子来解读。
首先,我们需要输入一个初始种子S,若没有给定初始种子S,则模糊器自己将构造一个。
随后,从初始种子选择种子进行变异生成测试用例,测试程序,若测试的结果为crash则加入Crash输出集。若并未产生crash则模糊器判断该测试用例是否有价值、足够有趣,若答案是肯定的则加入种子集合,再后续的主循环中利用。直到模糊器收到终止信号,则退出循环,并将运行中收集到的crash集输出。

我们可以从这样一个流程中看到,模糊器无外乎做了两件事情,一是根据种子生成测试用例,二是根据测试用例测试程序并追踪程序的状态,如此循环往复。可以简单的兑换为以下的流程图。

我们在0x02章中,工作流程这个小节中发掘,种子库对于fuzzer来说是一个至关重要的环节,而在实践过程中也的确证实,好的种子库对于fuzzer结果的影响和执行效率都十分巨大。
对于基于覆盖率的fuzzer来说,种子语料库的质量显著的影响fuzzing的质量。良好的初始种子可以显著提高fuzzing的效率和效果。
具体来说,提供目标测试程序输入要求良好格式的种子,可以避免因大量无用的CPU消耗。良好的种子输入格式,可以避免模糊器在该阶段盲目的变异猜测。良好输入的格式的种子可以抵达更深和盲目变异难以抵达的路径。
此外,种子语料库的制作是也是一门重要的技能。

AFL是由Google工程师开发的一款基于引导覆盖的模糊测试器,可以用于白盒测试与黑盒测试。在Github上,Google官方的AFL项目对AFL的描述如下:

American Fuzzy Lop is a brute-force fuzzer coupled with an exceedingly simple but rock-solid instrumentation-guided genetic algorithm. It uses a modified form of edge coverage to effortlessly pick up subtle, local-scale changes to program control flow.

AFL的工作流程可以体现为下图。根据Google对AFL主要算法工作原理的总结,可以归纳为下面几点:

在AFL执行流程的每一步中,都有许多迫切的问题。例如,如何挑选种子、如何变异、如何测试、如何测量覆盖率等等,许多的问题都有行之有效的解决方法,但有效的人工干预仍然是一个好的选择。
再下面一节,我们将讨论再AFL中,对于上诉问题采取什么策略,是如何应对的。

AFL的覆盖率度量是一种混合度量,它将边覆盖率与在一次执行中相应边的次数相结合,并设置一个上限(一个2的幂次方),防止路径爆炸。
如果一个testcase访问到了一条新的边(edge),那么AFL则认为它是有趣的(GOOD),将加入到种子队列中。
那么AFL又是如何记录已经访问的边呢?AFL是这样计算的。如下图所示,有两个基本块BB1和BB2,当发生从BB1到BB2的跳转时,即可认为BB1和BB2之间的边被访问。AFL在会在编译插桩阶段对基本块BB1和BB2分别插入一个标识R1和R2,根据这个R1和R2计算出一个哈希值,更新至位图中相应索引的字节。
上诉逻辑可以兑现为如下伪代码。

AFL的变异分为deterministichavoc两种类型。其中deterministic对testcase的内容进行确定性的突变,如位翻转、加法、一些特定值的替换(-1、INT_MAX)等。
havoc模式中,突变将具有更大的不可确定性,如可能会调整testcase的内容(添加或删除部分内容)。

最初AFL对于每次fuzz都会建立一个虚拟进程空间,显而易见,频繁的进程创建对CPU来说是一个巨大的开销,对于fuzzing的效率不可忍受。
为了避免execve()的开销,AFL设计了一套Forkserver机制。每当AFL需要fuzz新的testcase时,AFL会重新写入testcase,然后告诉target fork自己。在这种情况下,AFL不需要每次都支付新进程初始化的开销,而是fork一次后不断在在第一次fork的进程中复用进程空间的资源,直到发生write时。

优先推荐使用AFL的增强版本,AFL++。在比较新的Linux发行版上,大都可以通过一条命令安装AFL++,以Ubuntu为例子,执行以下命令即可。

然而,更加简单快捷的使用完整的新版本AFL++,可以选择容器构建。具体的只需要执行如下命令即可。


[培训]内核驱动高级班,冲击BAT一流互联网大厂工作,每周日13:00-18:00直播授课

最后于 2023-6-27 18:02 被Cx1ng编辑 ,原因:
收藏
免费 6
支持
分享
最新回复 (7)
雪    币: 14517
活跃值: (17538)
能力值: ( LV12,RANK:290 )
在线值:
发帖
回帖
粉丝
2
感谢分享
2023-6-27 09:45
0
雪    币: 191
能力值: ( LV1,RANK:0 )
在线值:
发帖
回帖
粉丝
3
forkserver标题少打了一个k吧
2023-6-27 17:43
0
雪    币: 1804
活跃值: (1225)
能力值: ( LV5,RANK:70 )
在线值:
发帖
回帖
粉丝
4
Humb1e forkserver标题少打了一个k吧
是的,感谢指正,已经修改
2023-6-27 18:03
0
雪    币: 1319
活跃值: (1955)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
5
直接ai做个用编码器压缩语料库呀=-=。探索直接用熵探索。
2023-6-28 15:55
0
雪    币: 4574
活跃值: (2515)
能力值: ( LV4,RANK:55 )
在线值:
发帖
回帖
粉丝
6
学习了
2023-6-30 08:33
0
雪    币: 3059
活跃值: (30876)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
7
感谢分享
2023-6-30 09:13
1
雪    币: 861
活跃值: (683)
能力值: ( LV6,RANK:80 )
在线值:
发帖
回帖
粉丝
8
感谢分享
2023-6-30 17:14
0
游客
登录 | 注册 方可回帖
返回
//