模糊测试(Fuzz testing, Fuzzing)最早由威斯康星大学麦迪逊分校的Miller教授在1988年提出[1], 是一种非常有效的自动化漏洞挖掘方法.模糊测试的基本原理是通过生成大量不规则的测试数据并将它们提供给被测程序进行测试, 监控被测程序在处理这些测试数据的过程中是否发生异常从而发现可能的漏洞.
在对程序进行模糊测试时, 模糊测试系统生成的测试数据的代码覆盖率越高, 发现漏洞的可能性越大, 因此模糊测试的一个关键点就是生成具有高代码覆盖率的测试数据.目前, 测试数据的生成方法主要分为基于规范的生成方法和基于变异的生成方法.在已知数据格式规范的情况下使用基于规范的测试数据生成方法能够生成满足格式约束的测试数据[2], 达到非常高的代码覆盖率.但是在很多情况下, 模糊测试中的被测程序是没有源码的二进制程序, 并且输入数据的格式是未知的, 基于变异的测试数据生成方法是这种情况下的主要方法也是研究的热点[3].基于变异的方法通过直接修改现有的测试数据来生成新的测试数据[4].然而如果使用随机变异的方式, 生成的测试数据将在很大程度上测试重复的程序执行路径, 并不能够达到很高的覆盖率, 实际的漏洞挖掘效果并不是特别好.为解决这一问题, 本文提出一种基于遗传算法的二进制程序模糊测试方法, 该方法通过遗传算法指导测试数据的生成过程, 提高测试数据的覆盖率.
1 相关工作对输入数据格式未知的二进制程序进行模糊测试时, 主要使用基于变异的测试数据生成方法.使用随机变异并不能取得很好的测试效果, 近些年来, 研究人员开始使用符号执行、污点分析、进化算法等方法来辅助生成测试数据的过程以此来克服随机变异的缺陷.
基于符号执行的方法将测试数据作为符号值处理.它们在程序处理这些符号值的过程中搜集路径上的约束信息, 然后通过约束求解生成新的测试数据用于测试不同的执行路径.理论上, 使用符号执行能够达到100%的代码覆盖率[5], 然而随着程序复杂程度的增加, 路径爆炸、复杂约束求解等问题严重限制符号执行的应用范围[6].符号执行并不适用于复杂程序.
基于污点分析的方法利用动态污点分析技术将软件的输入数据标记为污染源, 记录污点的传播过程并提取关键污点信息, 用于指导新的测试用例生成[7].整个测试数据生成过程主要关注污点所在的一些关键执行路径, 对其他路径的测试较少.
基于进化算法的方法将测试数据转换为进化算法能够处理的格式, 通过进化算法的引导生成新的测试数据, 其中应用最广泛的是遗传算法.目前研究人员在使用遗传算法指导测试数据的生成过程中需要预定义一条[8]或多条[9]执行路径, 最终生成符合预设的执行路径的测试数据, 并不能够对其他路径进行测试.
综上所述, 目前针对输入数据格式未知的二进制程序模糊测试方法存在不适用于复杂程序、测试的执行路径少等问题.针对这些问题, 本文提出一种基于遗传算法的二进制程序模糊测试方法, 该方法使用遗传算法中的进化思想, 通过监控被测程序的执行过程获取程序执行路径信息用于遗传算法中适应度的计算, 从而生成能够覆盖更多程序执行路径的测试数据.
2 方法原理 2.1 原理框架基于遗传算法的二进制程序模糊测试方法将测试数据转化为遗传算法中种群的个体, 使用个体在进化过程中的改变产生新的测试数据, 其原理如图 1所示.首先使用初始测试数据或随机值初始化遗传算法中的种群, 种群中的每个个体对应一个测试数据.然后跟踪被测程序处理这些测试数据的过程并记录执行路径信息, 同时监控程序的执行状态, 提取造成程序崩溃(Crash)的测试数据.接下来使用执行路径信息计算每个个体的适应度.最后通过对个体进行选择、交叉和变异生成新的测试数据并开始新一轮的测试.
|
图 1 方法原理图 Fig. 1 Principle diagram of proposed method |
在遗传算法中, 种群由若干数量的个体组成, 每个个体可以抽象表示为染色体, 设染色体的长度为D, 那么种群中的第i个个体可以表示为Xi=(xi, 1, xi, 1, xi, 1, …, xi, D).种群初始化的过程就是为Xi中每一个基因xi, d赋值.本文中, 每个xi, d代表一个字节, 长度D即为测试数据的字节数.存在初始测试数据时, 使用初始测试数据的每一个字节分别为每一个xi, d赋值.在其他情况下, 使用随机赋值的方式初始化整个种群.初始化完成之后, 每个个体的染色体数据即为一条测试数据的内容, 可直接将其转换为下一步所需的测试数据.
2.3 跟踪执行被测程序跟踪执行被测程序需要进行两方面的工作：1)监控当前的测试数据是否会造成被测程序崩溃；2)记录程序执行路径.程序在崩溃时会发送一个错误信号(如SIGILL、SIGSEGV、SIGABRT)[10], 因此通过接收程序发送的信号可以监控程序是否崩溃.一个程序可以被划分为许多基本块, 程序执行的过程就是不断重复执行一个基本块、跳转到另外一个基本块的过程.通过跟踪记录当前正在被执行的基本块可以得到程序执行路径.
每个基本块只有一个入口和一个出口, 且仅会从入口处开始执行并从出口离开, 因此可以使用每个基本块的入口地址表示一个基本块.一个简单程序中的几个基本块如图 2所示.使用Quick Emulator (QEMU)进行插桩能够获取程序执行过程中的基本块信息.用户模式下QEMU模拟执行程序的过程中将程序划分为基本块进行翻译和执行, 通过在QEMU执行一个基本块之前插入一段输出当前正在执行的基本块的信息的代码, 能够在QEMU模拟执行程序时得到程序执行过程对应的基本块序列.
|
图 2 一个简单程序中的几个基本块 Fig. 2 Some basic blocks of simple program |
将程序中每一个基本块b视为一个点, 使用基本块的入口地址代表b, 通过跟踪程序执行过程可获得一个基本块的序列(b1, b2, b3, …, bn).定义程序执行过程中2个连续基本块之间的跳转为e=(bk, bk+1), 那么e就是以基本块为节点的程序控制流图中的边(如图 2所示).经过基本块到边的转换, 程序的执行路径可以表示成边的序列Ee=(e1, e2, e3, …, en-1).在序列Ee中, 某些边不可避免的将出现多次, 即有可能存在x、y使序列中的ex与ey代表相同的边.合并这些相同的边将得到包含出现次数信息的边的集合E′e={e′1, e′2, e′3, …}.每条边出现的次数在不同的程序执行过程有可能是不同, 根据出现次数的不同, 将其分成8种不同的类型：1、2、3、4~7、8~15、16~31、32~127、≥128.这8种类型能够在实际应用时使用一个字节的不同位进行表示, 便于编程实现.经过分类后, 将得到一个新的边的集合E″e={e″1, e″2, e″3, …}.使用上述过程处理种群中的每一个个体Xi对应的程序基本块序列, 最终将得到程序的执行路径信息, 即边的集合Ei={ei, 1, ei, 2, ei, 3, …}.
2.4 适应度计算测试数据生成过程中发现新的执行路径的测试数据有更重要的意义, 而发现新的执行路径也就意味着发现新的边.定义整个模糊测试过程中所有曾经发现的边的集合为Et={et, 1, et, 2, et, 3, …}.对于集合Et中任意一条边et, i, 假设最后一次发现这条边的测试数据为Xt, i, 那么可以得到一个边与测试数据相对应的集合Wt={(et, 1, Xt, 1), (et, 2, Xt, 2), (et, 3, Xt, 3), …}.
个体Xi的适应度f分为2个方面：发现的新的边的数量f1和集合Wt中与其相关的边的数量f2.使用函数f1(Xi)=card (Ei-Et)计算发现的新的边的数量；使用函数
当适应度计算时, 首先计算每个个体的f1, 然后更新集合Et和Wt, 最后计算每个个体的f2.由于每轮测试完成后, 均会更新用于计算适应度的2个集合, 故对于上一轮中的个体, 其适应度也将随之改变, 且f1将始终为0, 而当本轮的个体的执行路径完全覆盖上一轮的某个个体的执行路径时, 其f2也将为0.当2个个体进行适应度对比时, 首先比较f1的值, 在无法区分的情况下比较f2的值.
2.5 个体选择、交叉和变异使用精英选择的方式用于产生新的个体.精英选择是遗传算法中一种产生新个体的策略, 将一定数量的适应度高的个体不经任何改变直接代入下一代.本文的选择过程中, 同时考虑前两代个体, 用于产生新的子代.
交叉过程使用2-opt交换.一个个体的染色体的长度为D, 首先生成2个0到D之间的随机数作为交叉点, 然后交换染色体中2个交叉点之间的片段.
变异操作采取随机赋值的方式进行.首先生成一个0到D之间的随机数作为变异点, 然后将变异点处的基因使用随机生成的值进行替换.
完成所有操作之后, 将染色体数据转换为测试数据提供给下一轮测试使用.
3 实验分析基于本文的方法构建基于遗传算法的模糊测试系统(Genetic-Algorithm-based Fuzzing, GAF), 使用代码覆盖率实验和漏洞挖掘实验测试GAF用于模糊测试的效果, 并与同类型的模糊测试工具American Fuzzy Lop (AFL)[11]进行对比.实验在一个Ubuntu 14.04的VMware虚拟机中进行, 为其分配双核2.50 GHz的CPU和2 GB内存.
3.1 代码覆盖率实验 3.1.1 实验目的使用本实验测试固定时间内GAF生成的测试数据的代码覆盖率.
3.1.2 实验数据使用3个广泛使用的程序作为实验中的被测程序：媒体处理程序FFmpeg[12]；XML文件解析库Expat[13]；PDF文件转换工具pdf2svg[14].
3.1.3 评价方法代码覆盖率能够使用测试数据发现的代码分支的数量表示.本文中描述的边和二进制情况下的代码分支具有相同的意义, 因此可以使用相同时间内系统生成的测试数据发现的边的数量Ne作为评价标准.
3.1.4 实验过程使用AFL和GAF对3个被测程序进行测试, 其中FFmpeg的测试分为输出为视频文件和音频文件的2个测试.测试分为2组进行, 测试时为每个程序提供一个1 024字节的文件作为初始测试数据.在第1组测试中, 初始测试数据是一个每个字节均是’\x00’的文件.在第2组测试中, 初始测试数据是一个随机生成的文件.每个程序的测试进行6 h, 在测试完成后, 记录发现的边的数量.
3.1.5 实验结果如图 3所示, 经过6 h的测试, 在第1组测试中, AFL在4个不同的测试中分别发现21 820、15 630、521和3 556条边, GAF分别发现22 415、19 867、1 561和4 470条边；在第2组测试中, AFL分别发现8 162、8 146、1 406和4 086条边, GAF分别发现12 700、12 291、1 660和4 450条边.实验结果表明, GAF在2组测试中均比AFL发现更多的边, 即有更高的代码覆盖率.
|
图 3 AFL和GAF发现的边的数量 Fig. 3 Number of edges found by AFL and GAF |
使用本实验测试GAF发现程序中崩溃漏洞的能力.
3.2.2 实验数据使用7个程序作为被测程序, 每个程序中包含一个已知的崩溃漏洞.其中3个程序(1285 realpath-2.4.2、1289 ns-lookup和1303 mime2)来自于NIST的SARD项目提供测试套件SARD.testsuit-88.2014-12-21-10-39-47[15].另外4个被测程序如表 1所示.
|
表 1 被测程序的内容 Table 1 Content of programs under test |
AFL和GAF在生成测试数据的过程中均存在一定的随机性, 因此针对每个测试程序进行多次实验, 使用发现程序中崩溃漏洞所需的测试数据数量的平均值Nt作为评价标准.
3.2.4 实验过程使用AFL和GAF分别对7个测试程序进行测试, 测试分为2组进行, 测试时为每个程序提供一个文件作为初始测试数据, 文件的大小如表 2所示.在第1组测试中, 初始测试数据是一个每个字节均是’\x00’的文件.在第2组测试中, 初始测试数据是一个随机生成的文件.当在测试中发现被测程序崩溃时, 记录使用过的测试数据的数量, 并重新开始测试.在2组测试中, 每个程序的测试均重复执行100次.
|
|
表 2 初始测试数据的大小 Table 2 Size of initial test data |
在实验中, 由于AFL在对Test1进行测试时, 发现漏洞所需的测试数据过多, 最终的实验结果为20次测试的平均值.如图 4所示, 第1组测试中AFL平均分别需要7 833 029.39、491.91、1 995.72、85 594.21、37 258.43、3 285 761.1和6 413.27个测试数据用于发现7个测试程序中的崩溃漏洞, 而GAF平均分别需要330 650.63、286.78、116.71、18 910.3、4 040.77、62 460.7和5 820.28个测试数据；在第2组测试中, AFL平均分别需要5 298 425.05、349.0、2 329.9、18 724.42、433.0、2 247 479.36和1个测试数据, GAF平均分别需要387 647.41、298.77、346.68、15 921.0、271.32、50 602.01和1个测试数据.在第2组测试中, 随机生成的数据直接导致被测程序1 303产生崩溃, 故AFL和GAF均仅需一个测试数据便能发现程序中的漏洞.实验结果表明, GAF在对所有7个测试程序的测试中, 发现程序中的崩溃漏洞所需的测试数据数量均比AFL少.
|
图 4 漏洞挖掘实验结果 Fig. 4 Results of vulnerability detection |
在代码覆盖率实验的4组测试中, GAF发现的边的数量平均比AFL多25.4%, 这表明在相同时间内, GAF生成的测试数据能够获得更高的代码覆盖率, 证明了遗传算法对于模糊测试中测试数据的生成具有显著的指导意义.
在漏洞挖掘实验中, GAF能够发现所有7个程序中的崩溃漏洞并且发现崩溃漏洞的效率至少比AFL提高了10%.发现程序中的崩溃漏洞也意味着生成的测试数据能够覆盖特定程序执行路径, 漏洞挖掘实验结果同样证明GAF探索程序的执行路径的效率比AFL更高, 与代码覆盖率实验的结果相符.对于测试程序Test1, 虽然其输入数据仅有4字节, 但AFL和GAF均需要大量的测试数据才能发现其中包含的崩溃漏洞, 这主要是因为触发Test1崩溃的输入相当于一种特殊的格式, 而AFL和GAF在生成测试数据的过程中均没有考虑格式信息, 需要花费大量的时间才能够探索到可能的格式, 如果使用格式信息辅助测试数据的生成过程将大大减少这一过程的消耗.
5 结语本文提出了一种基于遗传算法的二进制程序模糊测试方法, 该方法使用遗传算法指导模糊测试中测试数据的生成过程并且不需要任何预定义的程序执行路径.测试数据生成过程中使用程序执行路径信息计算遗传算法中每个个体的适应度并用于指导遗传算法的进化过程, 使生成的测试数据能够覆盖更多的程序执行路径.实验结果表明, 同等时间内该方法生成的测试数据拥有更高的代码覆盖率, 并且能够提高发现程序中的崩溃漏洞的效率.本文的方法同样存在一些局限.测试数据生成的过程中并没有考虑数据的格式, 对于一些需要满足特定格式才能测试的程序执行路径, 需要花费大量的时间来探索格式信息.为了解决这些问题, 下一步将研究格式逆向分析技术用于辅助测试数据的生成过程.
| [1] |
MILLER B P, FREDRIKSEN L, SO B. An empirical study of the reliability of UNIX utilities[J]. Communications of the ACM, 1990, 33(12): 32-44. DOI:10.1145/96267.96279 |
| [2] |
YANG H, ZHANG Y, HU Y, et al. IKE vulnerability discovery based on fuzzing[J]. Security and Communication Networks, 2013, 6(7): 889-901. DOI:10.1002/sec.v6.7 |
| [3] |
CHA S K, WOO M, BRUMLEY D. Program-adaptive mutational fuzzing[C]//2015 IEEE Symposium on Security and Privacy. San Jose: IEEE, 2015: 725-741. http://ieeexplore.ieee.org/document/7163057/
|
| [4] |
HOCEVAR S. zzuf-multi-purpose fuzzer[EB/OL]. (2015-06-09)[2017-04-13]. http://caca.zoy.org/wiki/zzuf.
|
| [5] |
CADAR C, SEN K. Symbolic execution for software testing:three decades later[J]. Communications of the ACM, 2013, 56(2): 82-90. DOI:10.1145/2408776 |
| [6] |
ZHANG D, LIU D, LEI Y, et al. SimFuzz:Test case similarity directed deep fuzzing[J]. Journal of Systems and Software, 2012, 85(1): 102-111. DOI:10.1016/j.jss.2011.07.028 |
| [7] |
CHOI Y H, PARK M W, EOM J H, et al. Dynamic binary analyzer for scanning vulnerabilities with taint analysis[J]. Multimedia Tools and Applications, 2015, 74(7): 2301-2320. DOI:10.1007/s11042-014-1922-5 |
| [8] |
MEI J, WANG S Y. An improved genetic algorithm for test cases generation oriented paths[J]. Chinese Journal of Electronics, 2014, 23(3): 494-498. |
| [9] |
YAO X, GONG D, WANG W. Test data generation for multiple paths based on local evolution[J]. Chinese Journal of Electronics, 2015, 24(1): 46-51. DOI:10.1049/cje.2015.01.008 |
| [10] |
GNU. The GNU C Library: Program error signals[EB/OL]. (2016-02-19). https://www.gnu.org/software/libc/manual/html_node/Program-Error-Signals.html.
|
| [11] |
MICHAL Z. American fuzzy lop[EB/OL]. (2016-06-05). http://lcamtuf.coredump.cx/afl/.
|
| [12] |
FFmpeg. FFmpeg[EB/OL]. (2016-10-01)[2017-04-13]. https://www.ffmpeg.org/.
|
| [13] |
CLARK J. The Expat XML Parser[EB/OL]. (2016-06-21)[2017-04-13]. http://www.libexpat.org/.
|
| [14] |
BARTON D. pdf2svg[EB/OL]. (2015-06-16)[2017-04-13]. http://www.cityinthesky.co.uk/opensource/pdf2svg/.
|
| [15] |
ROSENBERG E. Testing exploitable buffer overflows from open source code[EB/OL]. (2014-06-09)[2017-04-13]. https://samate.nist.gov/SARD/testsuite.php.
|
| [16] |
CVE. CVE-2016-3861[EB/OL]. (2014-06-09)[2017-04-13]. https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2016-3861.
|