Please wait a minute...
浙江大学学报(工学版)
JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE)  2018, Vol. 52 Issue (5): 1014-1019    DOI: 10.3785/j.issn.1008-973X.2018.05.023
Computer Technology     
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
Download:   PDF(1036KB) HTML
Export: BibTeX | EndNote (RIS)      

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.

Received: 25 April 2017      Published: 07 November 2018
CLC:  TP399  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Cite this article:

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.

URL:

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


基于遗传算法的二进制程序模糊测试方法

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

[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!