基于动态时间切片和高效变异的定向模糊测试

doi:10.3969/j.issn.1671-1122.2023.08.009

摘要/Abstract

摘要：

定向灰盒模糊测试（Directed Grey Box Fuzzing，DGF）是一种漏洞挖掘领域的新技术，它的最大优势是高效性。DGF已被广泛应用于补丁测试、信息流检测和崩溃复现等领域。然而，现有的DGF技术存在两个问题，第一，传统的DGF没有考虑到长路径种子也能触发漏洞，并且没有考虑种子的优先级；第二，强随机性的变异会浪费大量资源，从而降低定向模糊测试的效率。文章提出了一种基于动态时间切片和高效变异的定向灰盒模糊测试方法。文章提出了动态时间切片策略，将时间分为3个阶段，包括无差别探索阶段、短路径优先阶段和长路径优先阶段，同时应用了基于种子路径执行频率的模拟退火算法用于能量分配。同时，还使用了ε-贪婪算法来引导变异过程的havoc阶段，以提升变异效率。文章基于这3种策略实现了一个名为DyFuzz的系统并且在8个真实的数据集上与AFLGo进行比较。实验表明，该方法能够有效提高触发漏洞的概率和速度，覆盖更多的边缘和触发更多的崩溃。

关键词: 漏洞挖掘, 定向模糊测试, 动态时间切片, havoc变异

Abstract:

Directed grey box fuzzing (DGF) is a novel technology in the field of vulnerability mining whose biggest advantage is high efficiency. DGF has been widely used in many fields such as patch testing, information flow detection, and crash reproduction. However, there are two problems with existing DGF technologies. First, traditional DGF does not consider that long-path seeds can also trigger vulnerabilities, and does not consider the priority of seeds. Second, strong random mutation wastes a lot of resources, thereby reducing the efficiency of directed fuzzing. This paper proposed a directed grey-box fuzzing method based on dynamic time slicing and efficient mutation. Firstly, this paper proposed a dynamic time slicing strategy, which divided time into three stages, including indiscriminate exploration stage, short-path priority stage and long-path priority stage, and also applied a simulated annealing algorithm based on the execution frequency of seed paths for energy distribution. Secondly, the ε-greedy algorithm was also used to guide the havoc stage of the mutation process to improve the mutation efficiency. Based on these three strategies, this paper implements a system called DyFuzz and compares it with AFLGo on 8 real datasets, which can effectively improve the probability and speed of triggering vulnerabilities, cover more edges and trigger more crashes.

Key words: vulnerability mining, directed fuzzing, dynamic time slicing, havoc mutation

中图分类号:

TP309

钟远鑫, 刘嘉勇, 贾鹏. 基于动态时间切片和高效变异的定向模糊测试[J]. 信息网络安全, 2023, 23(8): 99-108.

ZHONG Yuanxin, LIU Jiayong, JIA Peng. Directed Fuzzing Based on Dynamic Time Slicing and Efficient Mutation[J]. Netinfo Security, 2023, 23(8): 99-108.

图/表 13

图1

图2

图3

图4

表1

图5

表2

表3

表4

表5

表6

表7

表8

参考文献 28

[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 URL
[2]	CNCERT. 2020 China Internet Network Security Report[EB/OL]. (2021-07-21)[2022-10-06]. https://www.cert.org.cn/publish/man/upload/File/2020%20Annual%20Report.pdf.
	国家互联网应急中心. 2020年中国互联网网络安全报告[EB/OL]. (2021-07-21)[2022-10-06]. https://www.cert.org.cn/publish/man/upload/File/2020%20Annual%20Report.pdf.
[3]	ZALEWSKI M. American Fuzzy Lop[EB/OL]. (2020-11-11)[2022-10-11]. https://lcamtuf.coredump.cx/afl/.
[4]	GODEFROID P. Random Testing for Security:Blackbox vs Whitebox Fuzzing[C]//IEEE. Proceedings of the 2nd International Workshop on Random Testing: Co-Located with the 22nd IEEE/ACM International Conference on Automated Software Engineering (ASE 2007). New York: IEEE, 2007: 1-12.
[5]	RAWAT S, JAIN V, KUMAR A, et al. VUzzer:Application-Aware Evolutionary Fuzzing[C]//ISOC. Network and Distributed System Security Symposium 2017. San Diego: ISOC, 2017: 1-14.
[6]	CHEN Peng, CHEN Hao. Angora:Efficient Fuzzing by Principled Search[C]//IEEE. 2018 IEEE Symposium on Security and Privacy. New York: IEEE, 2018: 711-725.
[7]	ASCHERMANN C, SCHUMILO S, BLAZYTKO T, et al. REDQUEEN:Fuzzing with Input-to-State Correspondence[C]//ISOC. Network and Distributed System Security Symposium 2019. San Diego: ISOC, 2019: 1-15.
[8]	GAN Shuitao, ZHANG Chao, CHEN Peng, et al. GREYONE:Data Flow Sensitive Fuzzing[C]//ACM. 29th USENIX Security Symposium. New York: ACM, 2020: 2577-2594.
[9]	LYU Chenyang, JI Shouling, ZHANG Chao, et al. MOPT:Optimized Mutation Scheduling for Fuzzers[C]//ACM. 28th USENIX Security Symposium. New York: ACM, 2019: 1949-1966.
[10]	HU Zhicheng, SHI Jianqi, HUANG Yanhong, et al. GANFuzz:A GAN-Based Industrial Network Protocol Fuzzing Framework[C]//ACM. CF '18:Computing Frontiers Conference. NewYork: ACM, 2018: 138-145.
[11]	CUMMINS C, PETOUMENOS P, MURRAY A, et al. Compiler Fuzzing Through Deep Learning[C]//ACM. ISSTA'18:International Symposium on Software Testing and Analysis. NewYork: ACM, 2018: 95-105.
[12]	SHE Dongdong, PEI Kexin, EPSTEIN D, et al. Neuzz:Efficient Fuzzing with Neural Program Smoothing[C]//IEEE. 2019 IEEE Symposium on Security and Privacy. New York: IEEE, 2019: 803-817.
[13]	GODEFROID P, PELEG H, SINGH R. Learn&Fuzz:Machine Learning for Input Fuzzing[C]//IEEE. 2017 32nd IEEE/ACM International Conference on Automated Software Engineering (ASE). New York: IEEE, 2017: 50-59.
[14]	BÖHME M, PHAM V T, NGUYEN M D, et al. Directed Greybox Fuzzing[C]//ACM. CCS'17: 2017 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2017: 2329-2344.
[15]	CHEN Hongxu, XUE Yinxing, LI Yuekang, et al. Hawkeye:Towards a Desired Directed Grey-Box Fuzzer[C]//ACM. CCS '18: 2018 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2018: 2095-2108.
[16]	LIANG Hongliang, ZHANG Yini, YU Yue, et al. Sequence Coverage Directed Greybox Fuzzing[C]//IEEE. ICSE '19: 41st International Conference on Software Engineering. New York: IEEE, 2019: 249-259.
[17]	LEE G, SHIM W, LEE B. Constraint-Guided Directed Greybox Fuzzing[C]//ACM. 30th USENIX Security Symposium. New York: ACM, 2021: 3559-3576.
[18]	HUANG Heqing, GUO Yiyuan, SHI Qingkai, et al. BEACON:Directed Grey-Box Fuzzing with Provable Path Pruning[C]//IEEE. 2022 IEEE Symposium on Security and Privacy (SP). New York: IEEE, 2022: 36-50.
[19]	ÖSTERLUND S, RAZAVI K, BOS H, et al. Parmesan:Sanitizer-Guided Greybox Fuzzing[C]//ACM. SEC'20: 29th USENIX Conference on Security Symposium. New York: ACM, 2020: 2289-2306.
[20]	ZHANG Chenhui, ZHOU Anmin, JIA Peng. A Time Slicing-Based Directed Fuzzing[J]. Modern Computer, 2022, 28(8):63-67.
	张晨辉, 周安民, 贾鹏. 一种基于时间分片的定向模糊测试[J]. 现代计算机, 2022, 28(8):63-67.
[21]	JASON S. GNU Binutils[EB/OL]. (2001-06-19)[2022-11-04]. https://www.gnu.org/software/binutils/.
[22]	DMITRY F. MJS: Restricted JavaScript Engine[EB/OL]. (2018-02-09)[2022-11-04]. https://github.com/cesanta/mjs.
[23]	KAREEM E. DARPA Challenge Binaries on Linux, OS X, and Windows[EB-OL]. (2021-04-14)[2022-11-04]. https://github.com/trailofbits/cb-multios.
[24]	SANDRO S. Libming[EB/OL]. (2021-05-11)[2022-11-04]. http://www.libming.org/.
[25]	ALAN Y. Jasper[EB/OL]. (2021-09-28)[2022-11-04]. https://ece.engr.uvic.ca/frodo/jasper/doc.
[26]	NICK W. Libxml2[EB/OL]. (2022-08-25)[2022-11-04]. https://github.com/GNOME/libxml2.
[27]	VADIM Z. Libtiff[EB/OL]. (2017-11-29)[2022-11-04]. https://github.com/vadz/libtiff.
[28]	PETER J. Yasm[EB/OL]. (2022-09-15)[2022-11-04]. https://github.com/yasm/yasm.

编号	数据集	目标文件
1	GNU binutils^[21]	cxxfilt.c:62
2	cb-multios^[22]	service.c:65
3	MJS^[23]	mjs.c:13732
4	yasm^[24]	intnum.c:415
5	libming^[25]	decompile.c:349
6	libtiff^[26]	tiff2ps.c:2479
7	Jasper^[27]	mif_cod.c:497
8	libxml2^[28]	valid.c:1181

CVE	Tool	R/次	TTE/s	Factor
2016-4487	DyFuzz	8	192	—
2016-4487	AFLGo	8	341	1.78
2016-4488	DyFuzz	8	102	—
2016-4488	AFLGo	8	132	1.29
2016-4490	DyFuzz	8	91	—
2016-4490	AFLGo	8	143	1.57
2016-4491	DyFuzz	1	16413	—
2016-4491	AFLGo	0	—	—
2016-4492	DyFuzz	8	863	—
2016-4492	AFLGo	8	1432	1.66
2016-4493	DyFuzz	3	23112	—
2016-4493	AFLGo	2	20123	0.87

Program	Tool	R/次	TTE/s	Factor
cb-multios	DyFuzz	8	27	—
cb-multios	AFLGo	8	31	1.15
MJS	DyFuzz	6	13564	—
MJS	AFLGo	5	15021	1.11
yasm	DyFuzz	6	14576	—
yasm	AFLGo	6	22053	1.51
libming	DyFuzz	7	6841	—
libming	AFLGo	6	7935	1.16
libtiff	DyFuzz	8	1475	—
libtiff	AFLGo	8	3458	2.34
jasper	DyFuzz	8	87	—
jasper	AFLGo	8	115	1.32
libxml2	DyFuzz	6	14520	—
libxml2	AFLGo	4	24579	1.69

CVE	Tool	R/次	TTE/s	Factor
2016-4487	DyFuzz	8	371	—
2016-4487	AFLGo	8	341	0.92
2016-4488	DyFuzz	8	150	—
2016-4488	AFLGo	8	180	1.01
2016-4490	DyFuzz	8	182	—
2016-4490	AFLGo	8	143	0.79
2016-4491	DyFuzz	1	19866	—
2016-4491	AFLGo	0	—	—
2016-4492	DyFuzz	8	1343	—
2016-4492	AFLGo	8	1432	1.07
2016-4493	DyFuzz	3	18431	—
2016-4493	AFLGo	2	20123	1.09

CVE	Tool	R/次	TTE/s	Factor
2016-4487	DyFuzz	8	309	—
2016-4487	AFLGo	8	341	1.10
2016-4488	DyFuzz	8	167	—
2016-4488	AFLGo	8	132	0.79
2016-4490	DyFuzz	8	257	—
2016-4490	AFLGo	8	143	0.96
2016-4491	DyFuzz	2	18766	—
2016-4491	AFLGo	0	—	—
2016-4492	DyFuzz	8	1365	—
2016-4492	AFLGo	8	1432	1.06
2016-4493	DyFuzz	3	19564	—
2016-4493	AFLGo	2	20123	1.03