##论文《LearnAFL: Greybox Fuzzing With Knowledge Enhancement》选自IEEEAccess
####本文框架优势
###预备知识
####AMERICAN FUZZY LOP (AFL)
• Fuzzing是一种自动化检测软件中漏洞的方法。
• 迄今为止，fuzzing技术已经发现了大量程序中的漏洞。
• 关键思想：产生大量测试用例并喂到被测项目中，以触发一些软件错误。
• 白盒fuzzing：基于分析被测项目内部结构。
• 黑盒fuzzing：不需要了解被测项目内部结构。
• 灰盒fuzzing：只知道有限的项目结构，大多数不需要被测项目源码，且可以更好地了解被测项目的信息和更高效地测试。
• 使用轻量级（二进制）打桩确定一条路径。
• 变异种子产生测试用例。
#####运行机制
描述：
AFL将测试用例进行分类。Favorite seed：在控制流的任何边缘执行时，速度最快、输入最小。
如果是不是favorite seed，会被忽略，进行下一个。
如果是，则进入变异阶段，对该种子进行变异后对目标系统进行测试。如果新变异出来的测试用例t探索到新的path，就会被加入到队列。当t触发了漏洞，就会被放入crash集中。
然后开始下一个seed执行同样的操作。
#####变异机制
变异策略：确定性变异和随机变异 。、
确定性变异：
bitflip： 按位翻转，每次都是比特位级别的操作，从 1bit 到 32bit ，从文件头到文件尾，会产生一些有意思的额外重要数据信息；
arithmetic： 与位翻转不同的是，从 8bit 级别开始，而且每次进行的是加减操作，而不是翻转；
interest： 把一些有意思的东西“interesting values”对文件内容进行替换；
dictionary： 用户提供的字典里有token，用来替换要进行变异的文件内容，如果用户没提供就使用 bitflip 自动生成的 token；
随机变异策略：havoc 和splice
havoc： 进行很大程度的杂乱破坏，规则很多，基本上换完就是面目全非的新文件了；
splice： 通过将两个文件按一定规则进行拼接，得到一个效果不同的新文件；
首先使用确定性变异找到魔法字节，然后使用随机变异策略进行变异。
缺点：
对魔法字节进行随机变异时，可能会破坏种子格式，使得具有一致的格式的种子数量减少，使得不易发现深层次漏洞。
花太多时间在确定性变异上会降低AFL的效率。
####Mapping Theroy
j∈P,Si∈T 有F(Si) =j（满射）
###本论文创新点
1.基于同类的格式生成理论
将执行同样路径的测试用例分为一类，当测试用例数量足够大时，可以推测出程序的结构。
映射理论：
将软件看做映射，每个测试用例对应一个确切的路径。
满射→双射
将T根据每个测试用例在测试时所执行的路径，分为几个子集，
T_i={S_(i_j ) |F(S_(i_j ) )=i}。
双射
F^':T^'→P,T^'={T_1,T_2,T_3,…}，F^' (T_i )=i
执行同一条path的测试用例越多，我们推测出的结果就能够越接近正确的格式。
有代码程序段如下：
分析path如下：
T_2={' bed.' ,' beef'}→format:'be**' 只有很少的测试用例时，这样的推测是错误的。
2. 基于格式的路径转换模型
• 马尔科夫链
路径转换本质：在变异过程中，种子格式改变，成为满足另一条路径约束条件的测试用例。
• 可以通过收集和观察大量执行path i的测试用例，得到path i的格式，就可以得到执行path i的约束条件。
• 修改这些约束条件和输入格式，就可以探索新的path。
例如：代码段如下
分析路径如下：
Paths|Input format
--|--
1|****
2|b***
3|ba**
4|bad*
5|bad!
6|bad!x(0≤x≤8)
7|bad!xy(0≤x≤8,y=x+1)
s=' bast^' →^' best^' , T_3→T_2. 这是一个向下转换的例子
又：
假如现在已经确定了前四个字符的格式‘bad!’，即已经确定了path1-4，接下来判断E，
如果输入为‘bad!t’，显然不会通过E的判定。
此时按照AFL的变异方法，会进行随机变异，这样会有很大可能向上转换，对于探索深层次的path没有帮助。
• 总结
• 已知一些种子和这些种子执行的路径格式。
• Decrease-transition：我们可以通过破坏种子的格式来执行比较高频的路径。
• Increase-transition：保持已知格式不变，变异其他部分，有助于产生能够探索深层paths的测试用例。
描述：一个seed输入后，执行的路径为i，经过变异后执行路径为j。也就是将本来是同一类的测试用例经过变异后产生的输入得到的路径脱离了这个类。根据这个理论，通过观察大量能够执行path A的测试用例的格式，并对之进行修改，或许就可以探索到新的路径。
路径转换：同类转换，一一对应的意思。
获得深层path比较难，可以通过保持已有的有效格式不变，进行下一步变异。
3. 增强型魔法字节表达式
• 实际项目中，代码语句复杂，状态繁多，路径
也很复杂，所以使用增强型魔法字节表达式辅助变异。
• 一个二维数组（建立在所有执行同一路径的测试
用例的常规表达式之上）
• 一维存放执行同一路径的所有测试用例的
共有子串。
• 一维存放对应子串在测试用例中所在的位置。
0，-1，-2
• 生成和调整增强型魔法字节表达式
• 将该表达式中的字符串进行变异，变异后，若
产生新的paths，则认为是魔法字节，确定输入格
式。
• 之后变异非表达式部分，探索深层路径。
魔法字节的增强表达式产生算法描述
基于最长公共子串搜索算法。
选择硬编码 作为最高级子串，它在一个集合中的所有测试用例中的位置固定不变。根据硬编码将集合分成几个子集。将每个集合中的字符串扩展最多的，最左边的子串作为第二优先级的子串。使用这些新串产生新的表达式来调节格式。
###架构设计与实现 • 基于AFL-2.52b（havoc变异策略，资源调度，执行引擎）。 • Python script：学习路径的格式。 • 辅助机制：借助这些格式来变异种子。 辅助变异算法 使用格式信息变异种子。 过程：初始阶段，执行变异。学习格式，提高对path的表达。 第二阶段：仅变异种子的提高性表达式部分，产生新的测试用例来测试。如果这个测试用例探测到了新的路径，说明这个部分是格式的一部分。 直到魔法字节提高性表达式中的所有子串被改变，才能确定哪个子串是格式的重要部分，并且能够得到一个精确的格式模型。 第三阶段:变异那些在执行确定性变异过程中，不在魔法字节提高性表达式中部分的字符，并且利用这个格式调节通过非确定性变异产生的测试用例。 结果：在格式模块的辅助下产生的所有测试用例都满足路径中的提高性表达。这就有可能探索更深层次的路径。
执行流程
###实验设计
• 对比实验
• 被测项目：gif2pn-2.5.9
• 对比工具：LearnAFL&AFL
• 实验环境：kali-linux
• 实验时常：约一小时
• 使用的种子：AFL源码中的testcase文件夹下的gif
###实验过程
1、安装learnAFL
输入命令：make&sudo make install
2、gif2png-2.5.9
(1)打桩设置
./configure CC="afl-gcc" CXX="afl-g++"
这里可能会出现一个问题：缺少png库
解决办法：
安装png库
sudo apt-get install libpng-dev
sudo apt-get install zlib1g-dev
(2)编译
Make出现问题
然后sudo apt-get install xmlto
这时候，网络不可达啦！重启虚拟机，再下载：
之后make
使用testcases中的gif
3、运行
对那些可以直接从stdin读取输入的目标程序来说，语法如下：
$ ./afl-fuzz -i testcase_dir -o findings_dir /path/to/program […params…]
对从文件读取输入的目标程序来说，要用“@@”，语法如下：
$ ./afl-fuzz -i testcase_dir -o findings_dir /path/to/program @@
此处：
alf-fuzz -i ../afl_in -o /afl_out ../gif2png-2.5.9/gif2png
运行时的截图：
说明：
这里展示了当前fuzzer的运行时间、最近一次发现新执行路径的时间、最近一次崩溃的时间、最近一次超时的时间。
值得注意的是第2项，最近一次发现新路径的时间。如果由于目标二进制文件或者命令行参数出错，那么其执行路径应该是一直不变的，所以如果从fuzzing开始一直没有发现新的执行路径，那么就要考虑是否有二进制或者命令行参数错误的问题了。对于此状况，AFL也会智能地进行提醒
overall results
这里包括运行的总周期数、总路径数、崩溃次数、超时次数。
其中，总周期数可以用来作为何时停止fuzzing的参考。随着不断地fuzzing，周期数会不断增大，其颜色也会由洋红色，逐步变为黄色、蓝色、绿色。一般来说，当其变为绿色时，代表可执行的内容已经很少了，继续fuzzing下去也不会有什么新的发现了。此时，我们便可以通过Ctrl-C，中止当前的fuzzing
stage progress
这里包括正在测试的fuzzing策略、进度、目标的执行总次数、目标的执行速度
执行速度可以直观地反映当前跑的快不快，如果速度过慢，比如低于500次每秒，那么测试时间就会变得非常漫长。如果发生了这种情况，那么我们需要进一步调整优化我们的fuzzing
1h4min后手动停止fuzz，开始分析
其中，crashes文件中，包含了所有导致被测项目崩溃的测试用例，hangs文件夹中包含了所有导致被测项目挂起的测试用例，knowledge文件夹包含learning engnine中学到的格式信息。
###分析crash
思路：
先是查看了一下导致crash的文件的十六进制（xxd命令），然后没有头绪。
所以打算用gdb，将导致crash的文件作为输入，但是下载gdb时，其中有一个询问是否更新libc6-dev的库还是什么，然后不小心点了"no",中断了下载，然后悲伤的事情就发生了！apt-get install再也不能用了，报错！报错！还是报错！！！
错误如下：
kali@kali:~/Downloads/afl_out_afl_org$ sudo apt-get install gdb
[sudo] password for kali:
Reading package lists... Done
Building dependency tree
Reading state information... Done
You might want to run 'apt --fix-broken install' to correct these.
The following packages have unmet dependencies:
build-essential : Depends: libc6-dev but it is not going to be installed or
libc-dev
clang-8 : Depends: libc6-dev but it is not going to be installed
Recommends: llvm-8-dev but it is not going to be installed
gdb : Depends: libbabeltrace1 (>= 1.5.4) but it is not going to be installed
Depends: libipt2 (>= 2.0) but it is not going to be installed
Depends: libpython3.8 (>= 3.8.2) but it is not going to be installed
Depends: libsource-highlight4v5 (>= 3.1.9) but it is not going to be installed
Recommends: libc-dbg
libc-bin : Depends: libc6 (< 2.30) but 2.30-8 is to be installed
libexpat1-dev : Depends: libc6-dev but it is not going to be installed or
libc-dev
libstdc++-8-dev : Depends: libc6-dev (>= 2.13-5) but it is not going to be installed
libstdc++-9-dev : Depends: libc6-dev (>= 2.13-5) but it is not going to be installed
locales : Depends: libc-bin (> 2.30) but 2.29-9 is to be installed
E: Unmet dependencies. Try 'apt --fix-broken install' with no packages (or specify a solution).
使用apt --fix-broken install并不能解决，apt-get install libc6-dev也不行，尝试了各种方法都未果，放弃。
只能将crash中的文件作为gif2png的输入查看报错信息，类似这样：
这个猜测是颜色处理不了。
段错误可能原因：（1）写入只读存储器（2）空指针取消引用（3）缓冲区溢出（4）堆栈溢出。
在最后结果数据分析部分，本来想用orignal pro的，但是plot_data中的数据在vim中才能打开，但是这个kali的vim还不支持复制到寄存器再复制到该以外的地方，所以，这个也没有实现。
###实验结果对比
下载依赖gnuplot
sudo apt-get install gnuplot
使用afl-plot绘制图像
(afl-plot afl_state_dir graph_output_dir)
kali@kali:~/Downloads$ afl-plot afl_out/ graph/
progress plotting utility for afl-fuzz by lcamtuf@google.com
[] Generating plots...
[] Generating index.html...
[+] All done - enjoy your charts!
kali@kali:/Downloads$ cd grap
bash: cd: grap: No such file or directory
kali@kali:/Downloads$ cd graph/
kali@kali:~/Downloads/graph$ ls
exec_speed.png high_freq.png index.html low_freq.png
-|learnAFL|AFL
--|--|--
执行状态|
|
发现crash的数量|
|
执行速度|
|
###实验小结
LearnAFL相对AFL来说，执行速度会相对来说慢一些，这是由于加了一个learning engine，用掉了一部分时间，但是发现crash的效率要比AFL高很多，从图中可以看到，在一个小时内（甚至LearnAFL比AFL少运行了几分钟），learnAFL发现了73个crashes，而AFL仅仅发现了34个crashes，并且发现了更多的路径。