简介：
当前已有的混合模糊测试虽然对覆盖率有很高的提升，但是仍然存在以下两点问题：
1、对AFL提供的种子无挑选进行符号化执行操作
2、很多漏洞会覆盖其所在分支但是没有触发
SAVIOR针对以上两点问题，首先利用了LLVM的UBSan工具对二进制潜在漏洞点进行标记，构建CFG进行分析，在运行中计算未发现边的漏洞数量进而打分实现对AFL种子的选择排序；其次，把标记过UBSan标签的LLVM中间代码给符号化执行组件，在符号化执行过程中约束求解来验证漏洞是否存在。
在24h的实验中，SAVIOR发现漏洞的速率比DRILLER和QSYM分别快43.4%和44.3%，比DRILLER、QSYM分别多发现88和76个漏洞。
一、研究背景
现有的模糊测试工具有AFL的改进（增强反馈信息影响力、对源代码流图分析等）和AFL与concolic testing相结合的混合模糊测试工具（DRLLER，QSYM）。
CollAFL减少覆盖反馈中的哈希冲突从而减少false positive。PTrix支持基于高效硬件跟踪的路径敏感模糊测试。TFUZZ转换已测试的程序，以绕过复杂的条件提高代码覆盖率，然后使用验证器重新生成用于原始程序的输入。ProFuzzer根据输入的结构信息来产生高质量的种子。AFLGO计算路径距离对种子进行排序筛选。
Driller更连贯地结合了模糊测试和符号化执行更加协同执行，可以无缝地测试各种软件系统。Digfuzz利用蒙特卡罗算法预测对路径探索难度，实现对种子排序。QYSM省略了约束求解不必要的运算。
但是混合模糊测试工具存在两点不足：
1、对AFL提供的种子无挑选进行符号化执行操作
2、很多漏洞会覆盖其所在分支但是没有触发
针对这两点不足，SAVIOR提供了漏洞导向的种子挑选机制以及在符号化执行部件执行的漏洞验证机制。
二、实现
1、 漏洞导向的种子排序
SAVIOR会优先选择能导向更多漏洞可能的种子。要实现这个机制要有两个要求，R1是能够知道一个种子在一次符号化执行后有可能执行哪些边（当前unexplored）。R2是统计那些边能够导向的漏洞数量。
为了满足R1，SAVIOR利用LLVM生成了程序的控制流图CFG，记录每个基本块的id、其后继id以及对应的边信息。在动态运行的时候，打印基本块的id来获取执行顺序，从而知道有哪些边是没有被发现但是通过符号化执行是可以被发现的。
为了满足R2，SAVIOR先引入了Clang的标记工具Clang’s Undefined Behavior Sanitizer (UBSan)，可以对一些内存操作进行标记并在LLVM中间代码中加入相应的验证操作。下图是SAVIOR选择的四类内存操作，其余的UBSan标签会被去除。
在CFG中可以得到一个边能指向的UBSan数量，从而实现对边的漏洞可能性排序。
然后打分方法如下：
一个种子有n条没有发现的边{e1, e2, . . . , en}
每条边可以到达的UBSan标签数量{L1, L2, . . . , Ln}
每条边在符号化执行中的求解难度 {S1, S2, . . . , Sn}
[图片上传失败...(image-9fc439-1586141522151)]
这样一来对AFL种子队列中的种子进行打分就可以实现种子排序。
2、 漏洞验证机制
之前提到了LLVM可以在中间代码中插入求解约束，在符号化执行阶段就会进行约束求解，如果产生能触发漏洞的新种子，则说明该标签漏洞可以被触发。
三、框架
SAVIOR分为三个部分，分别是以AFL-2.5b为主体的模糊测试部分、python编写的用于种子排序挑选的中间件以及用于验证漏洞、寻找边界种子的符号化执行部件。
1、 预处理。
分析。对源码进行UBSan标签、修建标签、构建CFG图、记录基本块和边的信息。
插桩。SAVIOR插桩了三份程序，分别是用afl-gcc插桩用于AFL进行模糊测试的二进制，可以打印执行的基本块id的中间件二进制程序以及插入了LLVM标签约束的用于符号化执行的bitcode。
2、 模糊测试
由AFL独立运行。
3、 中间件
中间件既要从AFL种子队列中挑选种子给concolic testing做符号化执行，又要把符号化执行中有用的结果挑选出来加入AFL的种子队列。
挑选种子阶段把AFL种子队列中的新种子在本地运行一边，因为会打印执行过的基本块id得到基本块的执行序列，就得到了没有发现的边集合，就可以对种子进行打分了。
符号化执行完把新的种子跑一遍，只留下带来新的覆盖率或者触发新的标签的种子留下来，并把这些种子加入AFL的队列。同时，对于符号化执行后没有被求解的边，对应的求解难度加一。
4、 符号化执行部件
首先对KLEE进行修改使其能够进行concolic testing。然后再本地建立一个bitmap来解决路径爆炸问题。同时为了减少符号化执行初始化的时间，采用了ForkServer模式加快了符号化执行速度。
四、实验
这里的数据集是LAVA-M和8个现实生活中的程序。
对比的工具既有混合模糊测试工具（DRILLER、QSYM），也有AFL作为基准比较，还有导向fuzz（AFLGO，TFUZZ等）
从发现漏洞的效率（数量、速度）以及发现漏洞的彻底性进行比较。
这里举tcpdump的测试结果作为例子。
可以看到，SAVIOR不是覆盖率最高的，但是触发的漏洞最多，原因在于UBSan的引入减慢了运行过程、同时符号化执行采用KLEE，速度也不高。但是由于漏洞验证机制，他能发现更多的漏洞。
为了突出漏洞验证机制的优越性，SAVIOR把所有fuzzer再24h运行后的种子放入SAVIOR的符号化执行部件，由于UBSan插入的LLVM IR，符号化执行部件能在种子输入中对漏洞标签处约束求解，得到能够触发漏洞的新种子。
五、总结
SAVIOR较之前的模糊测试加入了种子选取以及漏洞验证机制，能够更有效地发现漏洞。其中，UBSan标签带来的漏洞验证机制可以引入到我们的工作中去帮助挖掘漏洞；同时，实验的对比方法也值得借鉴。
