面向软件漏洞检测的Fuzzing样本优化方法

doi:10.6040/j.issn.1671-9352.0.2019.205

摘要/Abstract

摘要：

软件漏洞检测在信息物理融合系统中通常使用模糊测试(Fuzzing)技术。针对Fuzzing技术中存在大量冗余的测试样本,且样本探测异常的有效性较低的情况,提出一种面向软件漏洞检测的Fuzzing样本优化的方法。首先筛除随机样本中软件不接受的样本,并通过改进的动态规划算法获得初始样本的精简集,以减小初始样本的数量;然后在测试过程中跟踪污点传播路径,利用Simhash和海明距离的改进算法求解样本传播路径相似度,通过删除相似度较高的样本进一步降低样本冗余;最后对触发异常的样本进行遗传变异构建新的测试样本,以增加样本的有效性。通过实验结果可以看出,相较于利用基于贪心算法和基于异常分布导向的方法，这里提出的方法有效减小了测试样本冗余,并且提升了测试样本的有效性。

关键词: 漏洞检测, 模糊测试, 样本优化, 样本精简集, 有效性

Abstract:

Software vulnerability detection Fuzzy testing techniques are commonly used in information physical fusion systems.But there are a large number of redundant test samples in Fuzzing technology, and the sample detection anomaly is less effective. Therefore, this paper proposes a Fuzzing sample optimization method for software vulnerability detection. Firstly, the samples that are not accepted by the software in the random sample are filtered out, and the improved dynamic programming algorithm is used to calculate the sample reduced set, and the number of initial samples is reduced. Then track the stain propagation path during the test, use the improved algorithm of Simhash and Hamming distance to solve the similarity of the sample propagation path, and further reduce the sample redundancy by deleting the samples with higher similarity. Finally, the genetic variation of the sample that triggers the abnormality is constructed. New test samples will increase the validity of the sample. It can be seen from the experimental results that compared with the method based on greedy algorithm and based on abnormal distribution orientation, the proposed method effectively reduces the test sample redundancy and improves the validity of the test sample.

Key words: vulnerability detection, Fuzzing, sample optimization, sample reduced set, effectiveness

中图分类号:

TP311

张晶,陈诚,郑焕科. 面向软件漏洞检测的Fuzzing样本优化方法[J]. 《山东大学学报(理学版)》, 2019, 54(9): 1-8, 35.

Jing ZHANG,Cheng CHEN,Huan-ke ZHENG. Fuzzing sample optimization method for software vulnerability detection[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2019, 54(9): 1-8, 35.

图/表 8

表1

图1

表2

图2

图3

图4

表3

表4

参考文献 19

1	LI Jun, ZHAO Bodong, ZHANG Chao. Fuzzing: a survey[EB/OL]. (2018-06-05)[2019-03-15]. https://doi.org/10.1186/s42400-018-0002-y.
2	KARGEN U, SHAHMEHRI N. Turning programs against each other: high coverage fuzz-testing using binary-code mutation and dynamic slicing[C]// Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering. New York: ACM, 2015: 782-792.
3	马金鑫, 张涛, 李舟军, 等. Fuzzing过程中的若干优化方法[J]. 清华大学学报(自然科学版), 2016, 56 (5): 478- 483.
	MA Jinxin , ZHANG Tao , LI Zhoujun , et al. Improved fuzzy analysis methods[J]. Journal of Tsinghua University(Science and Technology), 2016, 56 (5): 478- 483.
4	MUNEA T L , KIM I L , SHON T . Design and implementation of Fuzzing framework based on IoT applications[J]. Wireless Personal Communications, 2017, 93 (2): 365- 382. doi: 10.1007/s11277-016-3322-9
5	李舟军, 张俊贤, 廖湘科, 等. 软件安全漏洞检测技术[J]. 计算机学报, 2015, 38 (4): 717- 732.
	LI Zhoujun , ZHANG Junxian , LIAO Xiangke , et al. Survey of software vulnerability detection techniques[J]. Chinese Journal of Computers, 2015, 38 (4): 717- 732.
6	CHEN Jiongyi, DIAO Wenrui, ZHAO Qingchuan, et al. IoTFuzzer: discovering memory corruptions in IoT through App-based Fuzzing[C]// Network and Distributed System Security Symposium. California: NDSS, 2018.
7	SANJAY R, VIVEK J, ASHISH K, et al. VUzzer: application-aware evolutionary Fuzzing[C]// Computer Applications and Software. San Diego: NDSS, 2017: 303-306.
8	欧阳永基, 魏强, 王清贤, 等. 基于异常分布导向的智能Fuzzing方法[J]. 电子与信息学报, 2015, 37 (1): 143- 149.
	OUYANG Yongji , WEI Qiang , WANG Qingxian , et al. Intelligent Fuzzing based on exception distribution steering[J]. Journal of Electronics & Information Technology, 2015, 37 (1): 143- 149.
9	王蕾, 李丰, 李炼, 等. 污点分析技术的原理和实践应用[J]. 软件学报, 2017, 28 (4): 860- 882.
	WANG Lei , LI Feng , LI Lian , et al. Principle and practice of taint analysis[J]. Journal of Software, 2017, 28 (4): 860- 882.
10	马金鑫, 李舟军, 张涛, 等. 基于执行踪迹离线索引的污点分析方法研究[J]. 软件学报, 2017, 28 (9): 2388- 2401.
	MA Jinxin , LI Zhoujun , ZHANG Tao , et al. Taint analysis method based on offline indices of instruction trace[J]. Journal of Software, 2017, 28 (9): 2388- 2401.
11	戴忠华, 赵波, 王婷, 等. 基于污点分析的嵌入式设备固件模糊测试方法[J]. 四川大学学报(工程科学版), 2016, 48 (2): 125- 131.
	DAI Zhonghua , ZHAO Bo , WANG Ting , et al. A Fuzzing test method for embedded device firmware based on taint analysis[J]. Journal of Sichuan University(Engineering Science Edition), 2016, 48 (2): 125- 131.
12	赵斌, 李伟明, 王永剑. 利用动态污点跟踪优化模糊测试的方法[J]. 华中科技大学学报(自然科学版), 2016, 44 (增刊1): 75- 79.
	ZHAO Bin , LI Weiming , WANG Yongjian . Optimization Fuzzing method based on dynamic taint tracking[J]. Journal of Huazhong University of Science and Technology (Nature Science Edition), 2016, 44 (Suppl. 1): 75- 79.
13	刘渊, 杨永辉, 张春瑞, 等. 一种基于遗传算法的Fuzzing用例生成新方法[J]. 电子学报, 2017, 45 (3): 552- 556. doi: 10.3969/j.issn.0372-2112.2017.03.007
	LIU Yuan , YANG Yonghui , ZHANG Chunrui , et al. A novel method for Fuzzing test cases generating based on genetic algorithm[J]. Acta Electronica Sinica, 2017, 45 (3): 552- 556. doi: 10.3969/j.issn.0372-2112.2017.03.007
14	焦龙龙, 罗森林, 刘望桐, 等. 基于遗传算法的二进制程序模糊测试方法[J]. 浙江大学学报(工学版), 2018, 52 (5): 1014- 1019.
	JIAO Longlong , LUO Senlin , LIU Wangtong , et al. Fuzz testing for binary program based on genetic algorithm[J]. Journal of Zhejiang University(Engineering Science), 2018, 52 (5): 1014- 1019.
15	何远, 张玉清, 张光华. 基于黑盒遗传算法的Android驱动漏洞挖掘[J]. 计算机学报, 2017, 40 (5): 1031- 1043.
	HE Yuan , ZHANG Yuqing , ZHANG Guanghua . Android driver vulnerability discovery based on black-box genetic algorithm[J]. Chinese Journal of Computers, 2017, 40 (5): 1031- 1043.
16	王颖, 杨义先, 钮心忻, 等. 基于控制流序位比对的智能Fuzzing方法[J]. 通信学报, 2013, 34 (4): 114- 121. doi: 10.3969/j.issn.1001-2400.2013.04.019
	WANG Ying , YANG Yixian , NIU Xinxi , et al. Smart Fuzzing method based on comparison algorithm of control flow sequences[J]. Journal on Communications, 2013, 34 (4): 114- 121. doi: 10.3969/j.issn.1001-2400.2013.04.019
17	MICHAEL S , ADAM G , PEDRAM A . Fuzzing: brute force vulnerability discovery[M]. Hoboken, USA: Addison-Wesley Professional, 2007: 31- 48.
18	ENCK W, GILBERT P, HAN S, et al. TaintDroid: an information-flow tracking system for realtime privacy monitoring on smartphones[C]// Proceedings of the 9th USENIX Conference on Operating Systems Design and Implementation. New York: ACM, 2010: 99-106.
19	CHEN Bing, ZENG Qingkai, WANG Weiguang. Crashmaker: an improved binary concolic testing tool for vulnerability detection[M]// Proceedings of the 29th Annual ACM Symposium on Applied Computing. New York: ACM, 2014: 1257-1263.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

样本类型	输入规则
中文	是否支持中文输入
英文	是否区分大、小写英文字母
唯一项	是否允许重复
字符长度	长度是否合法
多行文本框	是否支持输入
特殊字符	是否支持特殊字符
特殊代码	是否支持特殊代码
数值	是否支持正负数、小数
边界值	是否合法
日期	日期格式是否合法性
时间	时间格式是否合法性

指令类型	传播源变量	传播规则	被标记变量
常数	右值	直接传递	左值
赋值	右值	直接传递	左值
一元算数	右值	直接传递	左值
多元算数	右值	合并后传递	左值
返回	变量	直接传递	与返回相关的变量
异常处理	变量	直接传递	与异常处理相关的变量
数组	变量	对数组变量直接传播,对索引变量合并后传播	与数组变量相关的变量、数组索引变量
域操作	域变量、域所属变量	合并后传递	与域操作相关的变量

软件名称	样本数量				代码覆盖率/%
软件名称	随机产生(初始样本)	文献[3]方法	文献[12]方法	本文优化集处理	随机产生(初始样本)	文献[3]方法	文献[12]方法	本文优化集处理
Foobar2000_v6.1.4.2	1 000	591	438	390	29	29	29	29
ACDSee_v5.0.1	1 000	410	353	302	22	22	22	22
NitroPDF_v11.0.3	1 000	355	320	284	27	27	27	27

软件名称	异常数量
软件名称	miniFuzz	Sulley	本文SGOM (迭代次数50次)	本文SGOM (迭代次数200次)
Foobar2000_v6.1.4.2	3	5	5	11
ACDSee_v5.0.1	1	5	7	9
NitroPDF_v11.0.3	6	7	10	15

[1]	唐乾,杨飞,黄琪,林果园. 基于TCB子集的访问控制信息安全传递模型[J]. 山东大学学报（理学版）, 2016, 51(7): 98-106.
[2]	谢建民,姚兵,赵廷刚. 广义太阳图S_m,n奇优雅标号算法及实现[J]. 山东大学学报（理学版）, 2016, 51(4): 79-85.
[3]	杜晓军,林柏钢,林志远,李应. 安全软件模糊测试中多种群遗传算法的研究[J]. J4, 2013, 48(7): 79-84.
[4]	王华田,王延平*. 关于连作人工林衰退机理几个热点问题的探讨[J]. J4, 2013, 48(7): 1-8.
[5]	余丽. 集值映射的ε-强次微分及应用[J]. J4, 2013, 48(3): 99-105.
[6]	崔玉泉1,马立杰2,赵晶3,白金燕4. DEA方法在投资组合中的应用[J]. J4, 2011, 46(2): 82-88.