Please wait a minute...
浙江大学学报(工学版)
浙江大学学报(工学版)  2018, Vol. 52 Issue (5): 1014-1019    DOI: 10.3785/j.issn.1008-973X.2018.05.023
计算机技术     
基于遗传算法的二进制程序模糊测试方法
焦龙龙, 罗森林, 刘望桐, 潘丽敏, 张笈
北京理工大学 信息与电子学院, 北京 100081
Fuzz testing for binary program based on genetic algorithm
JIAO Long-long, LUO Sen-lin, LIU Wang-tong, PAN Li-min, ZHANG Ji
School of Information and Electronics, Beijing Institute of Technology, Beijing 100081, China
 全文: PDF(1036 KB)   HTML
摘要：

针对当前二进制程序模糊测试中基于变异生成的测试数据的执行路径重复率高导致代码覆盖率低的问题，提出基于遗传算法的二进制程序模糊测试方法.该方法将测试数据转换为遗传算法中的个体，利用Quick Emulator对二进制程序进行插桩以获取程序执行路径，使用基于程序执行路径的适应度函数指导遗传算法中的进化过程，使生成的测试数据能够覆盖更多的程序执行路径.实验结果表明，该方法在相同时间内达到的代码覆盖率平均比模糊测试工具American Fuzzy Lop （AFL）高25.4%.同时，该方法在漏洞挖掘实验中发现了测试程序中的所有崩溃漏洞并且其效率至少比AFL提高10%.该方法能够用于提高模糊测试的漏洞挖掘效率.
Abstract:

A genetic algorithm-based fuzz testing method for binary program was proposed aiming at the low code coverage problem caused by high execution path repetition rate of the test data generated from mutation in binary program fuzz testing. The method transformed test data to individuals in genetic algorithm. Quick Emulator was used to instrument a binary program for extracting program execution path. The evolution process in genetic algorithm was guided by an execution-path-based fitness function, so that the generated test data could cover more program execution paths. Experimental results show that the average code coverage of the method is 25.4% higher than fuzzing tool American Fuzzy Lop (AFL) within the same time. The method can detect all crashes in vulnerability detection experiment and the efficiency is at least 10% higher than AFL. The method is helpful for improving the efficiency of fuzz testing.
收稿日期: 2017-04-25 出版日期: 2018-11-07
CLC:  TP399  
通讯作者: 张笈,男,副教授.orcid.org/0000-0002-3607-1869.     E-mail: zhangjibit@gmail.com
作者简介: 焦龙龙(1990-),男,博士生,从事信息安全等研究.orcid.org/0000-0001-9549-3431.E-mail:xiguazzz@foxmail.com
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章　　

引用本文:

焦龙龙, 罗森林, 刘望桐, 潘丽敏, 张笈. 基于遗传算法的二进制程序模糊测试方法[J]. 浙江大学学报(工学版), 2018, 52(5): 1014-1019.

JIAO Long-long, LUO Sen-lin, LIU Wang-tong, PAN Li-min, ZHANG Ji. Fuzz testing for binary program based on genetic algorithm. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(5): 1014-1019.

链接本文:

http://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2018.05.023    或    http://www.zjujournals.com/eng/CN/Y2018/V52/I5/1014

[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
No related articles found!