提高fuzzing边覆盖率的改进方法

doi:10.11959/j.issn.1000-436x.2019223

Abstract

Abstract:

Aiming at the problems of incomplete edge coverage,insufficient uses of edge coverage information and valid bytes information in AFL (American fuzz lop),a novel method was proposed.Firstly,a new seed selection algorithm was introduced,which could completely cover all edges discovered in one cycle.Secondly,the paths were scored according to the frequency of edges,to adjust the number of tests for each seed.Finally,more mutations were crafted on the valid bytes of AFL.Based on the method above,a new fuzzing tool named efuzz was implemented.Experiment results demonstrate that efuzz outperforms AFL and AFLFast in the edge coverage,with the increases of 5% and 9% respectively.In the LAVA-M dataset,efuzz found more vulnerabilities than AFL.Moreever,in real world applications efuzz has found three new security bugs with CVEs assigned.The method can effectively improve the edge coverage and vulnerability detection ability of fuzzer.

Key words: fuzzing, vulnerability, AFL, edge coverage

CLC Number:

TP311.1

Chunfu JIA,Shengbo YAN,Zhi WANG,Chenlu WU,Hang LI. Method to improve edge coverage in fuzzing[J]. Journal on Communications, 2019, 40(11): 76-85.

Figures/Tables 10

References 19

[1]	SUTTON M , GREENE A , AMINI P . Fuzzing:brute force vulnerability discovery[M]. NJ: Pearson EducationPress, 2007.
[2]	CHEN C , CUI B , MA J ,et al. A systematic review of fuzzing techniques[J]. Computers ＆ Security, 2018,75(1): 118-137.
[3]	RAWAT S , JAIN V , KUMAR A ,et al. VUzzer:application-aware evolutionary fuzzing[C]// ISOC Network and Distributed System Security Symposium. ISOC, 2017: 1-14.
[4]	B?HME M , PHAM V T , NGUYEN M D ,et al. Directed greybox fuzzing[C]// ACM Conference on Computer and Communications Security. ACM, 2017: 2329-2344
[5]	CHEN H , XUE Y , LI Y ,et al. Hawkeye:towards a desired directed grey-box fuzzer[C]// ACM Conference on Computer and Communications Security. ACM, 2018: 2095-2108.
[6]	STEPHENS N , GROSEN J , SALLS C ,et al. Driller:augmenting fuzzing through selective symbolic execution[C]// ISOC Network and Distributed System Security Symposium. ISOC, 2016: 1-16.
[7]	SHOSHITAISHVILI Y , WANG R , SALLS C ,et al. Sok:state of the art of war:offensive techniques in binary analysis[C]// IEEE Symposium on Security and Privacy. IEEE, 2016: 138-157.
[8]	OGNAWALA S , KILGER F , PRETSCHNER A . Compositional fuzzing aided by targeted symbolic execution[J]. arXiv Preprint,arXiv:1903.02981, 2019.
[9]	CADAR C , DUNBAR D , ENGLER D R . KLEE:unassisted and automatic generation of high-coverage tests for complex systems programs[C]// USENIX Symposium on Operating Systems Design and Implementation. USENIX, 2008: 209-224.
[10]	孙鸿宇, 何远, 王基策 ,等. 人工智能技术在安全漏洞领域的应用[J]. 通信学报, 2018,39(8): 1-17.
	SUN H Y , HE Y , WANG J C ,et al. Application of artificial intelligence technology in the field of security vulnerability[J]. Journal on Communications, 2018,39(8): 1-17.
[11]	GODEFROID P , PELEG H , SINGH R . Learn ＆ fuzz:machine learning for input fuzzing[C]// IEEE/ACM International Conference on Automated Software Engineering. IEEE/ACM, 2017: 50-59.
[12]	WANG J , CHEN B , WEI L ,et al. Skyfire:Data-driven seed generation for fuzzing[C]// IEEE Symposium on Security and Privacy. IEEE, 2017: 579-594.
[13]	GAN S , ZHANG C , QIN X ,et al. CollAFL:path sensitive fuzzing[C]// IEEE Symposium on Security and Privacy. IEEE, 2018: 679-696.
[14]	KLEES G , RUEF A , COOPER B ,et al. Evaluating fuzz testing[C]// ACM Conference on Computer and Communications Security. ACM, 2018: 2123-2138.
[15]	DOLAN-GAVITT B , HULIN P , KIRDA E ,et al. Lava:large-scale automated vulnerability addition[C]// IEEE Symposium on Security and Privacy. IEEE, 2016: 110-121.
[16]	LI J , ZHAO B , ZHANG C . Fuzzing:a survey[J]. Cybersecurity, 2018,1(1):6.
[17]	>B?HME M , PHAM V T , Roychoudhury A . Coverage-based greybox fuzzing as Markov chain[C]// ACM Conference on Computer and Communications Security. ACM, 2016: 1032-1043.
[18]	WANG M , LIANG J , CHEN Y ,et al. SAFL:increasing and accelerating testing coverage with symbolic execution and guided fuzzing[C]// International Conference on Software Engineering. 2018: 61-64.
[19]	王志, 蔡亚运, 刘露 ,等. 基于覆盖率分析的僵尸网络控制命令发掘方法[J]. 通信学报, 2014,35(1): 156-166.
	WANG Z , CAI Y Y , LIU L ,et al. Using coverage analysis to extract Botnet command-and-control protocol[J]. Journal on Communications, 2014,35(1): 156-166.

Metrics

Recommended 0

No Suggested Reading articles found!

路径	经过的边	说明
q₁	e₁ e₉ e₁₅ e₁₇
q₂	e₁ e₂ e₆ e₇ e₂ e₃ e₄ e₅ e₁₆	e₆的优先种子
q₃	e₁ e₂ e₃ e₄ e₅ e₁₅ e₁₇	e₁₇的优先种子
q₄	e₁ e₂ e₆ e₇ e₉ e₁₆	q₅出现前，e₉的优先种子
q₅	e₁ e₉ e₁₆	e₉的优先种子
q₆	e₁ e₂ e₃ e₈ e₁₂ e₄ e₅ e₁₅ e₁₇	e₈的优先种子

序号	变异方法
1	随机选择位进行翻转
2	随机选择1 B设置为特殊值，值从预定义的集合随机选取
3	随机选择2 B设置为特殊值，值从预定义的集合随机选取
4	随机选择4 B设置为特殊值，值从预定义的集合随机选取
5	随机选择1 B减去一个较小的随机数
6	随机选择1 B增加一个较小的随机数
7	随机选择2 B减去一个较小的随机数
8	随机选择2 B增加一个较小的随机数
9	随机选择4 B减去一个较小的随机数
10	随机选择4 B增加一个较小的随机数
11	随机选择1 B设置为随机数
12	随机删除一段数据
13	插入常量字节块或克隆文件中一段数据到随机位置
14	覆盖写入常量字节块或文件中原有一段数据到随机位置
15	覆盖写入字典中的数据到随机位置
16	插入字典中的数据到随机位置

测试程序	第一个种子	第二个种子	第三个种子	第四个种子	第五个种子
binutils-objdump	empty	rand100	regdbdump	CVE-2018-1000876	CVE-2018-20673
binutils-nm	empty	rand100	regdbdump	CVE-2018-1000876	CVE-2018-20673
binutils-readelf	pr21135	regdump	CVE-2017-6965	CVE-2017-6966	CVE-2017-6969
tcpdump	heapoverflow-tcp_print	stp-heapoverflow	CVE-2017-11108	bgp_vpn_attrset	EIGRP_subnet_down
libtiff	miniswhite-1c-1b	rgb-3c-8b	palette-1c-1b	CVE-2019-7663	CVE-2019-6128

测试程序	覆盖不全总次数	调用算法总次数	覆盖不全的比例	未覆盖的最大边数
binutils-objdump	425	583	72.90%	14
binutils-nm	638	743	85.87%	4
binutils-readelf	1 199	1327	90.35%	7
libtiff	362	458	79.04%	5
tcpdump	1 498	1599	93.68%	10

	tcpdump1	libtiff2	libtiff3	readelf4	readelf5
AFL	11 342.2	3691.4	5154.1	10 222.7	9487.0
AFLFast	10 627.9	3640.9	5279.7	9 753.7	8977.6
Enery	11 756.1	3872	5300.2	10 306.5	9951.7
Bytes	11 601.1	3816.6	5364.1	10 591.8	10068.8
Enery \| AFL	3.65%	4.89%	2.83%	0.82%	4.90%
Enery \| Fast	10.62%	6.35%	0.39%	5.67%	10.85%
Bytes \| AFL	2.28%	3.39%	4.07%	3.61%	6.13%

Method to improve edge coverage in fuzzing

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 19

Related Articles 15

Metrics

Recommended 0

实验名	AFL	AFLFast	efuzz	比AFL提高	比AFLFast提高
objdump1	7 288.3	7 223.8	7 852.5	7.74%	8.70%
objdump2	8 314.3	8 098.9	8 569.3	3.07%	5.81%
objdump3	8 371.4	8 403.8	8 623.4	3.01%	2.61%
objdump4	6 969.8	6 701.5	7 458.2	7.01%	11.29%
objdump5	7 599.8	7 031.2	7 829.1	3.02%	11.35%
nm1	5 794.7	5 566.4	6 172.6	6.52%	10.89%
nm2	3 985.2	3 996.5	4 796.1	20.35%	20.01%
nm3	7 306.2	6 450.1	7 618.3	4.27%	18.11%
nm4	6 036.0	5 029.9	6 228.3	3.19%	23.83%
nm5	5 551.9	5 316.3	5 823.7	4.90%	9.55%
readelf1	10 421.2	9 823.0	10 807.8	3.71%	10.03%
readelf2	10 637.9	10 029.5	10 971.2	3.13%	9.39%
readelf3	10 238.0	9 578.3	10 738.4	4.89%	12.11%
readelf4	10 222.7	9 753.7	10 633.0	4.01%	9.02%
readelf5	9 487.0	8 977.6	10 186.9	7.38%	13.47%
libtiff1	5 218.1	5 284.7	5 326.7	2.08%	0.80%
libtiff2	3 691.4	3 640.9	3 875.2	4.98%	6.43%
libtiff3	5 154.1	5 279.7	5 419.0	5.14%	2.64%
libtiff4	5 513.8	5 504.2	5 785.1	4.92%	5.10%
libtiff5	5 299.7	5 376.0	5 489.5	3.58%	2.11%
tcpdump1	11 342.2	10 627.9	11 916.2	5.06%	12.12%
tcpdump2	11 654.2	11 123.8	11 646.5	-0.07%	4.70%
tcpdump3	11 869.0	11 105.9	12 009.9	1.19%	8.14%
tcpdump4	11 844.4	11 183.7	11 894.4	0.42%	6.35%
tcpdump5	11 821.6	11 120.9	11 826.0	0.04%	6.34%
平均	—	—	—	4.54%	9.24%

测试程序	设计bug数	AFL触发数	efuzz触发数
base64	48	6	4
md5sum	61	0	0
uniq	29	4	2
who	2 517	1	56
总计	2 655	11	62

CVE编号	漏洞程序	漏洞说明
CVE-2018-20671	binutils	整型溢出/堆溢出
CVE-2018-20467	ImageMagick	拒绝服务
CVE-2019-6988	openjpeg	拒绝服务

[1]	Ming TANG, Yifan HU. Load-to-store: exploit the time leakage of store buffer transient window [J]. Journal on Communications, 2023, 44(4): 64-77.
[2]	Haiyan KANG, Molan LONG. Research on network attack analysis method based on attack graph of absorbing Markov chain [J]. Journal on Communications, 2023, 44(2): 122-135.
[3]	Yuntao ZHANG, Binxing FANG, Chunlai DU, Zhongru WANG, Zhijian CUI, Shouyou SONG. Container escape detection method based on heterogeneous observation chain [J]. Journal on Communications, 2023, 44(1): 49-63.
[4]	Huafeng HUANG, Purui SU, Yi YANG, Xiangkun JIA. Automatic exploitation generation method of write-what-where vulnerability [J]. Journal on Communications, 2022, 43(1): 83-95.
[5]	Jiawei QIN, Hua ZHANG, Hanbing YAN, Nengqiang HE, Tengfei TU. Research on context-aware Android application vulnerability detection [J]. Journal on Communications, 2021, 42(11): 13-27.
[6]	Changqing AN, Yujia LIU, Hui WANG, Zhiyan ZHENG, Tao YU, Jilong WANG. Research on the invulnerability of regional network based on topology analysis [J]. Journal on Communications, 2021, 42(11): 145-158.
[7]	Bing ZHANG, Zheng WEN, Yuxuan ZHAO, Ning WANG, Jiadong REN. Dual-granularity lightweight model for vulnerability code slicing method assessment [J]. Journal on Communications, 2021, 42(11): 233-241.
[8]	Hongyu SUN,Yuan HE,Jice WANG,Ying DONG,Lipeng ZHU,He WANG,Yuqing ZHANG. Application of artificial intelligence technology in the field of security vulnerability [J]. Journal on Communications, 2018, 39(8): 1-17.
[9]	Cheng-yu SUN,Mao-xing SHEN,Hao SHENG,Jin-ke XIAO. Optimization design of structure invulnerability for air defense multiple sensor network [J]. Journal on Communications, 2017, 38(6): 118-126.
[10]	De-guang LE,Sheng-rong GONG,Shao-gang WU,Feng XU,Wen-sheng LIU. Research on RTF array overflow vulnerability detection [J]. Journal on Communications, 2017, 38(5): 96-107.
[11]	Zi-wei YE,Yuan-bo GUO,Chen-dong WANG,An-kang JU. Survey on application of attack graph technology [J]. Journal on Communications, 2017, 38(11): 121-132.
[12]	Xin JIN,Liang YANG,Cheng-ming JIN,Guo-hua SU,Lei SUN. Method to create and optimize original electric power communication network based on K-means [J]. Journal on Communications, 2016, 37(Z1): 10-14.
[13]	Zhou LI,Cong TANG,Jian-bin HU,Zhong CHEN. Vulnerabilities scoring approach for cloud SaaS [J]. Journal on Communications, 2016, 37(8): 157-166.
[14]	Qi TANG,Shang-feng WU,Jun-wu SHI,Ji-bo WEI. Graph partition based mapping algorithm on multiprocessors for streaming applications [J]. Journal on Communications, 2016, 37(6): 137-143.
[15]	Tao WEN,Yu-qing ZHANG,Qi-xu LIU,Gang YANG. UVDA:design and implementation of automation fusion framework of heterogeneous security vulnerability database [J]. Journal on Communications, 2015, 36(10): 235-244.