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

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

通信学报 ›› 2019, Vol. 40 ›› Issue (11): 76-85.doi: 10.11959/j.issn.1000-436x.2019223

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

贾春福¹,严盛博¹,王志¹(),武辰璐¹,黎航²

¹ 南开大学网络空间安全学院，天津 300350
² 南开大学人工智能学院，天津 300350

修回日期:2019-09-13 出版日期:2019-11-25 发布日期:2019-12-06
作者简介:贾春福（1967- ），男，河北文安人，博士，南开大学教授、博士生导师，主要研究方向为计算机网络与信息安全、可信计算、恶意代码分析。|严盛博（1987- ），男，湖北荆州人，南开大学硕士生，主要研究方向为逆向工程与漏洞挖掘。|王志（1981- ），男，山西长治人，博士，南开大学讲师，主要研究方向为计算机病毒的分析与防治。|武辰璐（1997- ），女，河南焦作人，南开大学硕士生，主要研究方向为二进制漏洞挖掘。|黎航（1995- ），男，湖北荆门人，南开大学硕士生，主要研究方向为自然语言处理。
基金资助:
国家自然科学基金资助项目(61972215);国家自然科学基金资助项目(61702399);国家自然科学基金资助项目(61972073);国家自然科学基金资助项目(61872202);天津市自然科学基金资助项目(17JCZDJC30500);赛尔网络下一代互联网技术创新基金资助项目(NGII20180401)

Method to improve edge coverage in fuzzing

Chunfu JIA¹,Shengbo YAN¹,Zhi WANG¹(),Chenlu WU¹,Hang LI²

¹ College of Cyber Science,Nankai University,Tianjin 300350,China
² College of Artificial Intelligence,Nankai University,Tianjin 300350,China

Revised:2019-09-13 Online:2019-11-25 Published:2019-12-06
Supported by:
The National Natural Science Foundation of China(61972215);The National Natural Science Foundation of China(61702399);The National Natural Science Foundation of China(61972073);The National Natural Science Foundation of China(61872202);The Natural Science Foundation of Tianjin(17JCZDJC30500);CERNET Innovation Project(NGII20180401)

摘要/Abstract

摘要：

针对 AFL 边覆盖不全、未充分利用边覆盖信息和有效字节信息的问题，提出了改进方法。首先，设计了新的种子选择算法，在一轮循环中可完全覆盖所有已发现的边；其次，按边覆盖热度对路径评分，以此调整种子的测试次数；最后，对有效字节进行更多的变异。基于上述方法实现了新的 fuzzing 工具—efuzz。实验表明， efuzz的平均边覆盖数比AFL和AFLFast分别增加了5%和9%；在LAVA-M测试集中，efuzz发现的漏洞数超过了AFL；在常用软件中，efuzz发现了3个新的CVE漏洞。所提方法可以有效提高fuzzing的边覆盖率、提升漏洞发现能力，具有实用性。

关键词: fuzzing技术, 漏洞, AFL, 边覆盖

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

中图分类号:

TP311.1

贾春福,严盛博,王志,武辰璐,黎航. 提高fuzzing边覆盖率的改进方法[J]. 通信学报, 2019, 40(11): 76-85.

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.

图/表 10

图1

图2

表1

表2

表3

表4

表5

表6

表7

表8

参考文献 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.

路径	经过的边	说明
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%

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

Method to improve edge coverage in fuzzing

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 19

相关文章 15

Metrics

推荐阅读 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]	唐明, 胡一凡. Load-to-store: store buffer暂态窗口时间泄露的利用[J]. 通信学报, 2023, 44(4): 64-77.
[2]	康海燕, 龙墨澜. 基于吸收马尔可夫链攻击图的网络攻击分析方法研究[J]. 通信学报, 2023, 44(2): 122-135.
[3]	张云涛, 方滨兴, 杜春来, 王忠儒, 崔志坚, 宋首友. 基于异构观测链的容器逃逸检测方法[J]. 通信学报, 2023, 44(1): 49-63.
[4]	杨宏宇, 杨海云, 张良, 成翔. 基于特征依赖图的源代码漏洞检测方法[J]. 通信学报, 2023, 44(1): 103-117.
[5]	黄桦烽, 苏璞睿, 杨轶, 贾相堃. 可控内存写漏洞自动利用生成方法[J]. 通信学报, 2022, 43(1): 83-95.
[6]	马博林, 张铮, 任权, 张高斐, 邬江兴. 软件异构冗余执行系统的安全能力分析[J]. 通信学报, 2021, 42(9): 1-11.
[7]	秦佳伟, 张华, 严寒冰, 何能强, 涂腾飞. 上下文感知的安卓应用程序漏洞检测研究[J]. 通信学报, 2021, 42(11): 13-27.
[8]	张炳, 文峥, 赵宇轩, 王苧, 任家东. 双粒度轻量级漏洞代码切片方法评估模型[J]. 通信学报, 2021, 42(11): 233-241.
[9]	孙鸿宇,何远,王基策,董颖,朱立鹏,王鹤,张玉清. 人工智能技术在安全漏洞领域的应用[J]. 通信学报, 2018, 39(8): 1-17.
[10]	乐德广,龚声蓉,吴少刚,徐锋,刘文生. RTF数组溢出漏洞挖掘技术研究[J]. 通信学报, 2017, 38(5): 96-107.
[11]	叶子维,郭渊博,王宸东,琚安康. 攻击图技术应用研究综述[J]. 通信学报, 2017, 38(11): 121-132.
[12]	李舟,唐聪,胡建斌,陈钟. 面向SaaS云平台的安全漏洞评分方法研究[J]. 通信学报, 2016, 37(8): 157-166.
[13]	温涛,张玉清,刘奇旭,杨刚. UVDA：自动化融合异构安全漏洞库框架的设计与实现[J]. 通信学报, 2015, 36(10): 235-244.
[14]	王志强,刘奇旭,张玉清. Android平台NFC应用漏洞挖掘技术研究[J]. 通信学报, 2014, 35(Z2): 117-123.
[15]	陈曦,田有亮,马卓,马建峰. 商业银行移动支付安全研究[J]. 通信学报, 2014, 35(Z2): 131-139.