本文针对盲目变异的模糊测试策略带来的效率低下的问题, 综合程序控制流图、输入种子样本特征、异常样本发现、模糊测试器路径反馈等信息, 提出一种更为有效的种子输入变异策略. 本文通过不断监控种子文件在目标程序中的执行路径, 并引入污点分析的方法, 以建立起新增执行路径的起始语句与种子文件中关键字节的一对多映射关系. 最终本文将根据这种映射关系对种子文件中的能够增加路径覆盖的字节进行变异, 以期得到更有效率的模糊测试结果. 我们的实验表明, 增加定向变异之后的模糊测试器在代码覆盖率, 以及模糊测试的效率上都有较为显著的提升.
To solve the problem of low efficiency caused by random mutation, a more effective mutation strategy is proposed in this study. The proposed approach synthesizes different kinds of information to help the Fuzzer mutate seed file, i.e., the CFG of program, the characteristics of input seed file, the information of abnormal input detection, and the branch courage of the Fuzzer. Based on this strategy, we design a new Fuzzer which continuously monitors the execution path of each seed file used as input of target program. Meanwhile, as most path constraints depend on only a few bytes in the input, periodical byte-level taint tracking will be necessary in the whole fuzzing process. After all this, we can infer a one-to-many mapping relation between the new execution path and key bytes in seed files, which can highlight the target start-end tuples of the seed file with more possibility to explore new branches in the target program to mutate. The result shows our design can improve the branch coverage of target program and the efficient of Fuzzing.
软件漏洞挖掘一直是网络空间安全领域极为重要的分支之一, 发掘出来的软件漏洞经常被用来攻击用户电脑、服务器等, 从而获取用户隐私, 甚至危害国防安全. 目前常用的漏洞挖掘技术有静态分析(如IDAPro[
模糊测试通常可以分为白盒模糊测试、黑盒模糊测试以及灰盒模糊测试三种, 其中灰盒模糊测试能够通过对程序轻量级分析获取程序执行信息, 并以此对执行结果进行评估, 从而制定测试策略. 这种方法相对于白盒模糊测试可以保证模糊测试的速度, 是目前运用最广泛的模糊测试方法. 例如American Fuzzy Loop(AFL)[
进行灰盒模糊测试的分析人员往往需要根据围绕输入种子特征, 对输入样本进行变异、筛选, 并在此过程中及时监控程序的执行情况, 以发现并处理那些可以产生新的路径覆盖甚至是造成程序崩溃的异常样本, 从而尽可能保证模糊测试器不会错过任何一个可能触发漏洞的执行样本. 然而在这个过程中, 会不可避免的出现一些问题.
首先, 对于不同的目标软件来说, 用于测试的种子文件特征肯定是不相同的, 如果根据输入种子格式对模糊测试器进行定制, 那么就会带来难以拓展的问题; 而如果设计一种较为通用的模糊测试器, 就有可能忽略掉种子文件的格式对模糊测试过程所带来的信息增益[
针对上述问题, 我们设计了一种可以解析种子文件格式信息, 并且不通过符号执行策略来产生高质量变异的模糊测试器. 我们的设计有以下几个特点.
(1) 解析程序的控制流信息. 在每次模糊测试之前, 根据程序的执行信息获得程序中控制流图中的所有节点所对应的位置. 本文着重于对基于灰盒测试[
(2) 高效的利用文件格式所带来的信息增益. 我们通过污点分析的方法判断出输入的种子文件中能够影响控制流图节点信息的具体字节. 然而污点分析是一个十分必要但是执行速度又过于缓慢的进程, 因从我们利用格式解析器将污点分析得到的绝对位置转化成了相对于文件格式关键字的相对偏移量, 这样对于新输入, 只需要定位到关键字, 从上述信息中可以计算出污点的绝对位置, 从而减少了污点分析的执行次数.
(3) 定向变异与随机变异相结合的变异策略. 我们通过对污点分析得到了一些有可能对程序执行路径发生较大影响的重点字节, 我们将这些字节分组并对其按组进行编码, 最终在不同的执行过程中有选择地对一些字节采用定向变异的方式, 其余字节采用随机变异的策略.
我们在主流模糊测试工具AFL的设计思路上进行改进, 最终实现了模糊测试器TaintFuzzy, 并得到了更为高效的模糊测试结果, 实验表明我们的模糊测试器与AFL有着相近的执行速度, 但是在单位时间内探索路径的数量增加了12.26%, 并且产生了更深层次的路径覆盖.
本节首先详细介绍了模糊测试器的设计流程, 然后介绍了模糊测试工具American Fuzzy Loop[
模糊测试器的设计方法有很多, 但是无论采用何种模糊测试策略, 其测试流程一般都包括识别测试目标及输入, 生成模糊测试数据, 执行模糊测试数据, 监视异常这几个阶段[
作为一款基于覆盖率的模糊测试器, AFL能在在执行测试用例的同时通过遗传算法自动生成那些有可能在目标程序中产生更多路径覆盖的测试用例.
AFL识别测试目标程序, 并对执行测试用例的过程进行异常监视的方法是对其进行插桩处理. 设计者使用afl-gcc作为编译工具实现了对目标程序的插桩, 并使用afl-as作为汇编器, 插入桩代码并执行会变操作. 桩代码中主要是一段汇编代码, 其中主要的操作包括保存edi等寄存器信息、生成一个[0, Map_size]范围内的随机数、保存生成的随机数、调用方法afl_maybe_log、恢复寄存器信息. 其中值得一提的是, 在处理到某个分支, 需要对其插入桩代码时, AFL会生成一个随机数, 用于标识这个代码块, 也就是说, 目标程序的每一个可执行分支都会在编译过程中赋予一个特殊的值作为这条分支的标识
为了高效执行测试用例, AFL实现了一套fork server机制, 在模糊测试器启动的同时, 运行了一个server进程作为fork子进程的服务端, 模糊测试器本身并不fork子进程, 而是通过server实现与目标程序的通信. 通过这种设计, 将目标程序的子进程与模糊测试器的执行分离开来, 从而保证模糊测试器生成测试用例与目标程序执行测试用例能够同时进行, 且通过server完成载入目标文件、解析符号地址等重复性工作.
模糊测试基本流程
AFL的Fork Server机制
在每次运行的时候, AFL都会维护一个全局分支覆盖表, 这个表的索引即为编译过程中AFL对目标程序的分支所赋予的随机数标识
AFL维护着一个队列, 每次从这个队列中取出一个文件, 对其使用一种基于遗传算法的变异策略进行变异[
(1) FLIPBIT: 按位或是按字节翻转. 按照1个比特或是一个字节为步长从头开始对原始文件进行翻转操作, 整个翻转的过程不会增加或是减少输入文件的bit位, 因此不会改变原文件的格式信息
(2) ARITH: 对字节进行整数加减运算, 加减变异的上限默认为35, 并且AFL会按照大端序以及小端序两种整数表示方式进行变异.
(3) INTEREST: 替换一些特殊内容到原文件中. 每次对8、16或是32个比特位及逆行替换, 替换之后不会影响输入文件长度.
(4) HAVOC: 完全随机的比特位翻转或对文件中某一块内容进行删除或是随即写操作.
(5) SPLICY: 在任意位置拼接两个完全不同的文件.
本节介绍了我们的模糊测试器在设计过程中的三个关键部分, 第一部分是结合插桩代码直观的抽取程序的控制流信息, 第二部分是使用污点分析的方法获取测试文件中的关键字节, 最后一部分介绍了我们的变异策略.
程序的控制流图可以描绘程序的控制流信息, 一个流图是一个有向图, 它由有限多个节点的结合NG={
令目标程序中所有被AFL插桩过的节点集合为N, 那么, 对于任意
从插桩代码中获取控制流中节点信息的流程如算法1所示.
算法1. 获得条件语句节点信息
输入: 插桩后的二进制代码(目标程序)
输出: 包含节点信息的数据结构
1 AF = Disassemble(F);
2 While not Eof (AF) do
3 {
4 Line = GetLine (AF);
5 if Line
6
7 (
8
9
10 }
11 else Line = Next (Line);
12 }
13 return
为了有效处理文件格式信息, 模糊测试器需要知道程序的执行路径受到输入文件中哪些字节的影响, 由此需要使用污点分析技术. 通常, 格式文件由两部分组成: 第一部分是关键字(标识符), 用于标记文件格式或其后特定长度字节的语义, 如PNG图片文件由一系列数据包(package)组成, 每一个数据包以特定的关键字开头; 第二部分则为由其前驱关键字声明的数据类型的具体数据. 在进行污点分析之前, 我们利用010Editor的文件格式模版和pfp解析库对输入文件进行解析, 后者依赖前者得到输入文件中每个字节相对于其前驱关键字的偏移量. 关键字信息则可以由模版文件中直接获得. 我们选择以字节作为污点标记的最小单元, 并将输入文件中所有字节都标记为不同的污点源. 我们需要记录跟踪应用程序所在内存空间以及8个通用寄存器中每个字节的污点标签. 然而根据我们的需求, 这里只需要定位3.1节中得到的条件语句位置, 并通过内存污点跟踪系统提取每个条件语句位置上流通过的污点数据. 若两个污点同源, 则记录其源污点数据. 若两个污点数据属于同一关键字节组, 则记录当前字节的前驱关键字节信息, 以及当前字节相对于其前驱关键字节的字节偏移量. 由于每个条件语句可能与多个污点字节有关, 我们最终建立的将是条件语句与字节位置信息之间的一对多映射关系. 污点分析的结果用十字链表结构(如
存储污点分析结果的十字链表
这里我们所做的工作主要是找到包含文件格式信息的字节, 后续的工作将会检查这些字节的变异是否会导致路径覆盖的增加, 如果增加了路径覆盖, 那么模糊测试器将会继续增加这些关键字节变异的概率. 相对于变异文件中的数据字节, 变异这些带有格式信息的字节往往能帮助我们拓展更多的程序执行路径.
然而污点分析是一个极其占用运行时间的方法, 尤其是我们需要以字节为单位进行污点分析的时候. 自动化模糊测试测试工具最大的优势在于极快的运行速度, 因此大部分的模糊测试器没有引入污点分析的方法对输入文件进行分析. 不过我们的研究发现, 对于基于遗传算法变异的模糊测试器来说, 并不需要对每一个输入文件进行污点分析. 以AFL维护的队列为例, 对于起始输入
如2.2小节中所提到的, AFL的变异策略有很大的随机性, 因此往往会出现无法达到深层次路径覆盖的情况. 而我们的设计可以通过污点分析得到输入文件中的字节偏移对条件语句判决的影响, 并参考这个信息对输入文件进行更有针对性的变异, 这样做不仅可以减少很多无效的变异, 提高变异效率, 而且由于加入了文件格式信息对变异的影响, 因此对于深层次路径的探索也大有裨益. 另外, 我们已经得到条件语句在插桩代码中的标识
如果能够顺利得到输入文件的这种映射关系, 则对其采用特殊的定向变异策略, 否则采用随机变异的方法. 如果变异结果可以产生新增的路径覆盖, 那么监督程序将判断其为有价值的变异, 并将其保存到输入队列. 我们设计的模糊测试器对输入文件一次完整的处理过程如
然而, 由于污点分析结果产出缓慢, 所以并不是所有输入文件在执行的过程中都能建立起这样的映射, 并且在实验过程中我们观察到, 原始的几个输入文件在输入进去的时候一定无法建立起这样的映射关系, 但是实际上, 原始的几个输入文件往往可以通过随机变异的方法就能产生大量新的路径覆盖. 因此我们设计了这样的变异策略: 对于原始的输入文件
算法2: 对输入文件的变异策略
1 void Fuzz
2 while Not End of Pool
3 F = GetFileFromPool // 从文件池中取出一个待测试文件
4 if HasTaintTrackingResult(F) ==True // 判断是否已经得到当前文件F污点分析的结果, 如果其父文件存在, 那么返回其父文件污点分析结果.
5 F_mutate = RandomMutate(F); // 对F进行随机变异
6 if FindNewBranchCoverage(){
7
8 Save(F_mutate);
9 (start, end) = SearchtResult(
10 F_mutate = Mutate(star, end); //对关键字节进行变异
11 go to 7;}
12 else
13 Abondon(F_mutate); //如果没有产生路径覆盖则舍弃变异结果
14 else
15 F_mutate = RandomMutate(F);
16 go to 7;
输入文件的处理过程
我们在AFL的基础上实现了本文中所描述的设计TaintFuzzy, 并将此工具与原版的AFL_2.52以及对每一个输入文件进行污点分析的早期版本TaintFuzzy_pre分别进行了24小时的对比试验. 实验目标为libpng库中的readpng程序, 起始的标准输入为AFL自带的png格式图片, 模糊测试的指令都为readpng-name.
模糊测试结果比较(24小时)
总路径数 | 路径深度 | 分支覆盖率(%) | 平均执行速度 | |
AFL | 1093 | 6 | 3.28 | 303.46 |
TaintFuzzy_pre | 775 | 6 | 2.84 | 193.17 |
TaintFuzzy | 1227 | 8 | 3.54 | 290.43 |
我们的方法在执行过程中引入了动态污点分析技术, 而频繁的污点分析必然会给平均执行速度带来一定幅度的下降. 结合
程序路径探索随时间变化的情况
模糊测试是一种能够高效地对软件脆弱性进行全面分析的方法. 本文设计了一种能够综合利用测试文件上下文信息以及程序执行路径信息的模糊测试器, 并且通过将污点分析得到的绝对位置转化成相对于文件格式关键字的相对位置, 减少了污点分析总工作量. 模糊测试在未来的一段时间内仍将是一种软件漏洞挖掘的利器, 模糊测试工具的改进也对实际软件开发有着重要意义.
Miller BP, Fredriksen L, So B. 1990. An empirical study of the reliability of UNIX utilities. Communications of the ACM, 1990, 33(12): 32–44.
Sadowski C, Aftandilian E, Eagle A, et al. Lessons from building static analysis tools at Google. Communications of the ACM, 2018, 61(4): 58–66.
Cohen MB, Snyder J, Rothermel G. Testing across configurations. ACM SIGSOFT Software Engineering Notes, 2006, 31(6): 1–9.