面向二进制程序的导向性模糊测试方法

张瀚方 周安民 贾鹏 刘露平 刘亮

摘 要：为了解决当前模糊测试技术中变异存在一定的盲目性以及变异生成的样本大多经过相同的高频路径的问题，提出并实现了一种基于轻量级程序分析技术的二进制程序模糊测试方法。首先对目标二进制程序进行静态分析来筛选在模糊测试过程中阻碍样本文件深入程序内部的比较指令;随后对目标文件进行插桩来获取比较指令中操作数的具体值，并根据该具体值为比较指令建立实时的比较进度信息，通过比较进度衡量样本的重要程度;然后基于模糊测试过程中实时的路径覆盖信息为经过稀有路径的样本增加其被挑选进行变异的概率;最后根据比较进度信息并结合启发式策略有针对性地对样本文件进行变异，通过变异引导提高模糊测试中生成能够绕过程序规约检查的有效样本的效率。实验结果表明， 所提方法发现crash及发现新路径的能力均优于模糊测试工具AFLDyninst。

关键词：导向性模糊测试;反馈式模糊测试;二进制模糊测试;程序插桩;漏洞挖掘

中图分类号：TP311

文献标志码：A

Abstract： In order to address the problem that the mutation in the current fuzzing has certain blindness and the samples generated by the mutation mostly pass through the same highfrequency paths， a binary fuzzing method based on lightweight program analysis technology was proposed and implemented. Firstly， the target binary program was statically analyzed to filter out the comparison instructions which hinder the sample files from penetrating deeply into the program during the fuzzing process. Secondly， the target binary program was instrumented to obtain the specific values of the operands in the comparison instructions， according to which the realtime comparison progress information for each comparison instruction was established， and the importance of each sample was measured according to the comparison progress information. Thirdly， the realtime path coverage information in the fuzzing process was used to increase the probability that the samples passing through rare paths were selected to be mutated. Finally， the input files were directed and mutated by the comparison progress information combining with a heuristic strategy to improve the efficiency of generating valid inputs that could bypass the comparison checks in the program. The experimental results show that the proposed method is better than the current binary fuzzing tool AFLDyninst both in finding crashes and discovering new paths.

英文关键词Key words： directed fuzzing; feedback fuzzing; binary fuzzing; program instrumentation; vulnerability mining

0 引言

随着计算机的广泛使用和网络技术的飞快发展，计算机软件早已融入到人们的日常生活中，在金融、交通、医疗卫生和国防科技等领域中发挥着重要作用。软件数量日益增加，与之俱来的软件安全问题也越发突出。软件中存在的漏洞为攻击者提供了可乘之机，近年來攻击者利用软件漏洞实施攻击的事件屡见不鲜，2017年wannacry勒索病毒利用永恒之蓝漏洞进行传播，造成巨大经济损失[1];2018年黑客利用思科高危漏洞攻击关键基础设施，导致全球20万台交换机受到影响[2]。

由于软件功能的增加，软件的代码量越来越大，代码结构越来越复杂，复杂的工作逻辑与数据处理过程导致软件在运行过程中极易产生bug，严重的则会引发安全漏洞。高效、自动化的安全测试理论和方法对软件测试和安全检测具有重要意义，也是计算机学科和网络安全学科的一个重要研究方向。模糊测试是一种有效的软件安全性检测方法，其基本思想是通过不断构造不规则数据作为应用程序的输入，执行并监视应用程序在处理输入数据时是否发生崩溃等异常来发现应用程序潜在的安全问题[3]。当前，模糊测试技术已被谷歌[4]、微软[5]等软件公司用于软件安全的测试。针对计算机软件的模糊测试可以根据能否获得应用程序的源码而分为针对开源软件的源码级别模糊测试和针对闭源软件的二进制级别模糊测试。由于大部分的软件厂商出于知识产权保护和商业利益的考虑并不会开放其软件源代码，在针对二进制程序的测试中可能存在输入数据格式未知等情况，因此相比于源码级别的模糊测试，二进制级别的模糊测试难度更大，面向二进制程序的软件漏洞挖掘技术也是当今研究的一个热点[6]。

当前在模糊测试领域，AFL（American Fuzzy Loop）[7]是最具有代表性的工具之一，它使用遗传算法，并将代码覆盖信息作为反馈用于筛选子代。相对于传统的模糊测试方法，AFL提高了模糊测试的效率;但是该工具仍存在一定的局限性，如变异生成的输入文件大多会运行到相同的高频路径[8-9]，在面向二进制程序的模糊测试中难以产生能够通过程序规约检查的有效用例，变异存在一定的盲目性，导致难以发现存在于程序深处的bug等。

针对于上述问题，本文提出了一种面向二进制程序的导向性模糊测试方法，该方法在AFL原有遗传算法的基础上提高经过稀有路径的种子文件被选中的概率，考虑到程序规约检查中的magic值校验检查，该方法通过二进制插桩技术并结合比较进度信息来指导样本变异以高效地生成能够通过规约检查从而触发程序新路径的变异样本，提高模糊测试的效率。

1 研究现状

在软件安全检测领域中，常用的漏洞挖掘方法有静态分析、污点分析、符号执行和模糊测试等方法。其中，静态分析误报率较高，随着应用程序功能的增多，代码复杂度也日益增加，静态分析方法越发难以发现应用程序中存在的漏洞; 污点分析方法的主要问题是效率较低，需要消耗大量的计算资源; 符号执行方法面临路径爆炸和约束求解困难等问题[10]; 相对于这些技术，模糊测试自动化程度高、原理简单并且误报率极低，因此受到了越来越多的关注[11-12]。

近几年来，针对于模糊测试的研究大多数是结合诸如符号执行[13-14]、污点分析[15]等方法以帮助模糊测试生成有效测试用例，通过结合其他方法的优势提高模糊测试的检测效果。

2 问题分析

在如下的应用程序中包含了magic值字段检查以及嵌套的if条件检查，输入文件只有在逐个绕过这些检查的情况下才能触发程序中所存在的bug，对于这样的应用程序AFL难以生成能够成功触发bug的样本文件。在对该代码进行长达 24h 的测试中，AFL并没有产生任何能够导致程序发生崩溃的测试用例。而在实际应用中，程序往往会通过大量的magic值校验以对输入文件进行格式检查。

在挑选样本进行变异时，通过Check 2检查的样本文件相对于只绕过Check 1检查的样本文件更容易触发程序中所存在的bug，样本文件只有在绕过Check 1的基础上才可能通过Check 2，因此通向Check 2的路径相比通向Check 1的路径更稀有。AFL会为每条路径挑选文件体积小且执行时间快的文件并将其标记为favored，在挑选文件进行变异时，被标记为favored的文件被选中的概率远远大于其他非favored的文件[21]。AFL的种子队列只增不减，在所给程序中，每条路径都可能存在其对应的文件体积最小并且执行时间最少的favored样本，因此在样本执行过的路径中可能会有多个favored文件，AFL没有考虑稀有路径使得这些样本在变异时均会被选择变异，但是，由于通过了Check 2的样本更容易触发程序中所存在的bug，增加通过Check 2校验的样本被选中的概率显然会增加样本触发bug的概率。

AFL使用代码覆盖信息作为反馈以筛选保留子代，在变异过程中生成的变异文件如果能够覆盖新的代码将会被保留。对于magic值校验的情况，如Check 2需要将变异样本的前5个字节设置为“MAGIC”字符串才能通过检查，即使AFL在变异过程中已经将变异样本的前5个字节设置为“MAGIX”，由于最后一个字节不匹配将导致校验失败，并没有触发新的代码，AFL在这样的情况下会舍弃该变异样本。AFL舍弃掉部分字节匹配的样本意味着之前达到部分字节匹配的变异工作对生成通过校验的样本毫无帮助，然而在匹配到部分字节的样本基础上进行变异，相对于在没有匹配到任何一个字节的样本基础上进行变异更容易通过校验。

本文考虑从两个角度解决上述在模糊测试中所面临的难题。首先在调度策略方面，将在原有AFL的基础上进一步增大经过稀有路径的样本文件被挑选进行变异以产生子代样本文件的概率。另外，在变异时将结合一定的启发式策略进行引导并保留具有高比较进度信息的样本以供进一步的变异。

3 导向性模糊测试方法

为了提高面向二进制程序的模糊测试的效率，本文提出了一种面向二进制程序的导向性模糊测试方法。其整体思路如图1所示。与传统AFL框架相比，该方法增加的策略有以下几个方面：

1）对目标二进制文件进行分析，提取其中含有的关键比较指令信息，并根据得到的指令信息有针对性地对目标二进制文件进行插桩以在模糊测试过程中获取比较进度信息和比较指令中操作数的具体值;

2）在模糊测试过程中，在选择种子文件进行变异时优先考虑经过稀有路径的样本文件;

3）在模糊测试过程中，在代码覆盖情况没有发生改变的条件下优先保留比较进度较高的样本文件，一旦变异文件触发或提高了比較进度信息将保留该变异文件以供进一步的变异，并且将使用比较进度得到提高的比较指令中操作数的值对当前样本变异位置前后特定数量的字节进行变异。

3.1 关键指令与比较进度

大部分的应用程序在执行初期的规约检查中往往会通过比较指令对输入文件进行格式检查，可能包括大量magic值的检查等校验，其中比较指令主要是指如cmp、strncmp等对操作数进行比较的指令。该类指令的执行结果将会影响程序运行的路径，从而影响后续的代码覆盖情况，因此本方法主要关注比较指令。应用程序中通常包含大量的比较指令，需要对其进行合理的筛选，由于本文目标是解决magic值校验的问题，所以在对比较指令进行过滤筛选时将重点关注操作数包含有立即值的比较指令。

在对比较指令筛选后，需要根据其地址信息有针对性地对目标二进制文件进行插桩，从而获取比较指令中操作数的具体值并根据该具体值建立对应的比较指令的比较进度信息。每条比较指令的进度信息为该比较指令中两个操作数中所匹配的字节的数目。如图2所示的示例中，magic值为“ELF+”，如果两个操作数的值完全相同则将该比较指令的比较进度设为0xFF，当操作数的值为“EXFO”时，此时两个操作数中仅第1个字节和第3个字节相同，此时比较进度将被设为0x2。

该比较进度信息将会作为后续挑选样本的一个重要参考信息。

3.2 种子文件选择

为了在模糊测试过程中能够优先选择经过稀有路径的样本进行变异，本文方法增加了经过稀有路径的样本文件被选中的概率。由于稀有路径需要根据程序在模糊测试过程中实时的测试情况才能确定，因此本文基于模糊测试过程中各样本的路径覆盖信息实时计算挑选稀有路径，通过实时的路径信息为每个种子文件计算能量，能量越高的种子文件被选中的概率越大。该方法以路径被样本队列中的样本所执行的累计次数判断路径是否稀有，考虑到在模糊测试过程中样本执行代码片段越多则越可能触发新路径，因此在计算样本的能量时将会计算各个分支的执行情况从整体上来为种子文件分配能量。

首先记录各分支路径被种子队列中的样本文件所执行的次数，每个分支被执行的次数等于各样本文件所执行该分支的次数的总和：

hitstimebranch=∑input∈queuehits（input，branch）（1）

其中queue属于当前的样本队列。根据分支执行次数的总和可以判断出哪些路径为稀有路径，为了让模糊测试合理使用资源探索新路径，通过为经过稀有路径的种子文件分配更多能量使得其被选中进行变异的概率增大，能量计算公式如下：

E（input）=∑branch∈Bhits（input，branch）hitstimebranch（2）

其中：hitstimebranch是当前branch路径被样本队列所执行的累计次数总和，而branch是当前样本文件所执行到的任一分支，hits（input，branch）为当前该样本在执行过程中执行branch分支的次数，B为当前执行到的所有程序路径分支。如果路径被执行次数较多，则该路径为高频路径，其获得的能量比重减小。 一个样本的能量比重为该样本所执行到的所有分支能量的总和。

3.3 变异引导

为了引导样本文件进行有效变异以产生能够通过比较检查指令的有效子代样本文件，本文在AFL的基础上进行了3个方面的改进：首先是保留比较进度有所增长的样本，其次是根据启发式规则对样本的特定位置进行变异，最后是以比较指令中出现的立即数为取值范围对样本进行变异。

在所给程序中，生成了绕过Check 1的样本后，在对样本文件进行进一步变异以生成通过Check 2校验的样本时，AFL会根据其变异规则对样本文件进行比特翻转、算术操作等，由于AFL将覆盖新代码作为保留子代的条件，即使变异样本已经部分匹配到“MAGIC”值，代码覆盖情况并没有改变，变异文件仍然会被舍弃，因此要求变异样本文件的前5个字节必须完全匹配“MAGIC”才能被保留，在这样的条件下，AFL要生成能够通过Check 2的样本最多需要28×5次变异。这样严苛的条件导致AFL很难生成能够成功通过Check 2的样本。为了降低难度，本文通过引入比较进度信息，在样本变异过程中匹配到magic值校验中的任一字节，即触发了比较进度后，将保留该变异文件进行进一步的变异，在进一步的变异中，将保留具有高比较进度信息的变异样本，在这样的条件下，要通过Check 2校验最多需要28×5次变异。通过引入比较进度信息本方法将极大降低生成通过Check 2样本的难度。

虽然为了通过规约检查引入比较进度后的变异难度已经大幅度减小，但是在对样本变异时需要进行变异的字节位于样本哪个偏移仍然是未知的，因此在实际情况中，变异出能够通过Check 2检查的样本所需要的最多变异次数远远大于28×5，仍然存在很大难度。即使能够准确定位到需要变异的位置，但是面临28×5次变异仍然是一个较大的开销。为了进一步提高变异的准确率和有效性，本文采用一种简单的启发式方法以减小变异范围和搜寻空间。在变异过程中，一旦对样本文件的某个偏移位置进行变异后触发或提高了比较指令的比较进度信息，那么将认为这个字节即为magic值校验检查中的一个字节，由于大部分的magic值是以連续字节的方式存放在输入文件中供应用程序进行校验检查的，因此位于该偏移位置前后的字节很有可能同样是magic字节，因此本方法将会在该变异位置前后的（sizeoperand-1）个字节优先使用该比较进度所对应的比较指令中立即数的具体值逐字节对样本文件进行变异。如在所给程序中，在对样本文件第1个字节进行变异时将第1个字节变异为M后，比较进度信息将被触发，本文方法将会使用“MAGIC”这5个字符逐字节对样本文件的第2～第5个字节进行变异，这将大幅度提高变异的准确性，能够快速生成通过Check 2的变异样本文件从而触发到Check 3的新路径。

4 实验与分析

为了验证所提方法的有效性，本文实现了一个模糊测试系统RMFuzzer并对其进行了实验评估。RMFuzzer使用二进制插桩平台Dyninst[22]以及模糊测试工具AFL进行开发，同时还使用IDA Pro（Interactive Disassembler Professional）及IDAPython辅助对二进制程序进行分析和相关指令信息的提取。在相同实验环境下与二进制模糊测试工具AFLDyninst（该工具采用Dyninst插桩框架对二进制文件进行插桩，其模糊测试器为AFL）进行对比。测试环境为Ubuntu 16.04 LTS32位系统，Intel Xeon CPU E31231 v3处理器和8GB的内存。实验采用了两个数据集进行实验评估，其中包括LAVAM测试集以及现实生活中的实际应用程序。

4.1 LAVAM测试集

LAVAM是一个人工构造的含有大量bug的数据集，其采用了污点分析等技术向应用程序中注入了大量难以被触发的bug[23]。

在对RMFuzzer和AFLDyninst进行对比实验时，使用相同的文件作为初始种子，运行时间为5h，由于模糊测试过程中变异存在一定的随机性，因此前后共进行了3轮测试，实验结果取3次实验的平均数据。在3次实验过程中，AFLDyninst均没有产生任何能够触发crash的样本文件，而RMFuzzer在4个应用程序中均产生了触发其中所存在的部分crash的样本文件。实验结果如表1所示。从实验结果可以看出，在LAVAM测试集中，RMFuzzer能够发现其中注入的bug，其测试效果明显好于AFLDyninst。

5 結语

针对现有模糊测试技术存在的路径覆盖能力不足、变异存在一定盲目性等问题，本文提出了一种面向二进制程序的导向性模糊测试方法，并基于该方法实现了模糊测试工具RMFuzzer。该方法主要从种子文件的调度策略以及变异策略上对模糊测试过程进行了引导，相对于其他将污点分析或符号执行与模糊测试相结合的方法，本文方法采用轻量级的静态分析方法与插桩技术，因此通用性更高，同时节约计算资源。通过实验证明RMFuzzer无论是在发现crash的能力方面还是在路径发现与代码覆盖方面均优于当前流行的模糊测试工具，但是该方法仍然存在一定的问题：

1）在进行变异引导时，本方法采用了一个启发式的策略，一旦该变异位置提高了比较指令中的比较进度就在该位置附近字节进行变异，但是如果输入文件中magic字段并不是连续存放的，那么这种启发式策略将不再奏效。故进一步的工作需要考虑如何解决这样的问题。

2）其次，存在变异导致控制流改变而进一步触发比较进度的情况，在这样的情况下，本文提出的变异引导方法将不再适用，在之后的研究工作中，需要考虑如何能更准确地对需要变异的文件位置进行定位，提高变异引导的效率和准确性。

3）本方法着重于解决应用程序规约检查中输入文件的magic字段的检查问题，在接下来的工作中应进一步研究如何生成能够快速绕过其他类型的程序检查的样本以提高模糊测试的效率。

参考文献 （References）

[1] Wikipedia. WannaCry ransomware attack[EB/OL].[2018-03-10]. https：//en.wikipedia.org/wiki/WannaCry_ransomware_attack.

[2] KHANDELWAL S. Critical flaw leaves thousands of Cisco switches vulnerable to remote hacking[EB/OL].[2018-03-10]. https：//thehackernews.com/2018/04/ciscoswitcheshacking.html.

[3] 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.

[4] OSSFuzzContinuous fuzzing for open source software[EB/OL]. [2018-03-10]. https：//github.com/google/ossfuzz.

[5] Microsoft security development lifecycle[EB/OL].[2018-03-10]. https：//www.microsoft.com/enus/sdl/process/verification.aspx.

[6] SHOSHITAISHVILI Y， WANG R， SALLS C， et al. SOK： （State of） the art of war： offensive techniques in binary analysis[C]// Proceedings of the 2016 IEEE Symposium on Security and Privacyn Security and Privacy. Piscataway， NJ： IEEE， 2016： 138-157.

[7] ZALEWSKI M. American fuzzy lop （2.52b）[EB/OL]. [2018-03-10]. http：//lcamtuf.coredump.cx/afl/.

[8] BHME M， PHAM V T， ROYCHOUDHURY A. Coveragebased greybox fuzzing as Markov chain[C]// Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. New York： ACM， 2016： 1032-1043.

[9] LEMIEUX C， SEN K. FairFuzz： a targeted mutation strategy for increasing greybox fuzz testing coverage[C]// Proceedings of the 2018 ACM/IEEE International Conference on Automated Software Engineering. Piscataway， NJ： IEEE， 2018： 475-485.

[10] CADAR C， SEN K. Symbolic execution for software testing： three decades later[J].Communications of the ACM， 2013， 56（2）： 82-90.

[11] LIANG H L， PEI X X， JIA X D， et al. Fuzzing： state of the art[J]. IEEE Transactions on Reliability， 2018， 67（3）： 1199-1218.

[12] GAN S T， ZHANG C， QIN X J， et al. CollAFL： path sensitive fuzzing[C]// Proceedings of the 2018 IEEE Symposium on Security and Privacy. Piscataway， NJ： IEEE， 2018： 679-696.

[13] PENG H， SHOSHITAISHVILI Y， PAYER M. TFuzz： fuzzing by program transformation[C]// Proceedings of the 2018 IEEE Symposium on Security and Privacy. Piscataway， NJ： IEEE， 2018： 697-710.

[14] PHAM V T， ROYCHOUDHURY A. Modelbased whitebox fuzzing for program binaries[C]// Proceedings of the 2016 IEEE/ACM International Conference on Automated Software Engineering. Piscataway， NJ： IEEE， 2016： 543-553.

[15] RAWAT S， JAIN V， KUMAR A， et al. VUzzer： applicationaware evolutionary fuzzing [EB/OL].[2018-03-20].https：//mirror.explodie.org/3714.pdf.

[16] 張斌， 李孟君， 吴波， 等. 基于动态污点分析的二进制程序导向性模糊测试方法[J]. 现代电子技术， 2014， 37（19）： 89-94. （ZHANG B， LI M J， WU B， et al. Method of binary oriented fuzzy testing based on dynamic taint analysis [J]. Modern Electronics Technique， 2014， 37（19）： 89-94.）

[17] 王铁磊. 面向二进制程序的漏洞挖掘关键技术研究[D]. 北京：北京大学， 2011： 41-69. （WANG T L. Research on binaryexecutableoriented software vulnerability detection[D]. Beijing： Peking University， 2011： 41-69.）

[18] STEPHENS N， GROSEN J， SALLS C， et al. Driller： augmenting fuzzing through selective symbolic execution[EB/OL].[2018-03-20].http：//www.cs.ucsb.edu/～chris/research/doc/ndss16_driller.pdf.

[19] LI Y K， CHEN B H， CHANDRAMOHAN M， et al. Steelix： programstate based binary fuzzing[C]// Proceedings of the 2017 Joint Meeting on Foundations of Software Engineering. New York： ACM， 2017： 627-637.

[20] CHEN P， CHEN H. Angora： efficient fuzzing by principled search[C]// Proceedings of the 2018 IEEE Symposium on Security and Privacy. Piscataway， NJ： IEEE， 2018： 697-710.

[21] ZALEWSKI M. Technical “whitepaper” for AFLfuzz[EB/OL]. [2018-03-20]. http：//lcamtuf.coredump.cx/afl/technical_details.txt.

[22] Paradyn/DyninstWelcome[EB/OL]. [2018-03-20]. https：//dyninst.org/.

[23] DOLANGAVITT B， HULIN P， KIRDA E， et al. LAVA： largescale automated vulnerability addition[C]// Proceedings of the 2016 IEEE Symposium on Security and Privacy. Piscataway， NJ： IEEE， 2016： 110-121.