您的位置:山东大学 -> 科技期刊社 -> 《山东大学学报(理学版)》

《山东大学学报(理学版)》 ›› 2019, Vol. 54 ›› Issue (9): 1-8, 35.doi: 10.6040/j.issn.1671-9352.0.2019.205

•   •    下一篇

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

张晶1,2(),陈诚1,*(),郑焕科1   

  1. 1. 昆明理工大学信息工程与自动化学院, 云南 昆明 650500
    2. 云南枭润科技服务有限公司, 云南 昆明 650500
  • 收稿日期:2019-04-17 出版日期:2019-09-20 发布日期:2019-07-30
  • 通讯作者: 陈诚 E-mail:zhangji0548_cn@sina.com;917692783@qq.com
  • 作者简介:张晶(1974—),男,博士,教授,博士生导师,研究方向为嵌入式软件工程、实时嵌入式软件和工业互联网. E-mail:zhangji0548_cn@sina.com
  • 基金资助:
    国家自然科学基金资助项目(61562051)

Fuzzing sample optimization method for software vulnerability detection

Jing ZHANG1,2(),Cheng CHEN1,*(),Huan-ke ZHENG1   

  1. 1. Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, Yunnan, China
    2. Yunnan Xiaorun Technology Service Limited, Kunming 650500, Yunnan, China
  • Received:2019-04-17 Online:2019-09-20 Published:2019-07-30
  • Contact: Cheng CHEN E-mail:zhangji0548_cn@sina.com;917692783@qq.com
  • Supported by:
    国家自然科学基金资助项目(61562051)

摘要:

软件漏洞检测在信息物理融合系统中通常使用模糊测试(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

表1

常见样本类型及其输入规则"

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

图1

程序控制流图"

表2

污点传播逻辑"

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

图2

污点分析过程"

图3

签名值计算过程"

图4

算法流程图"

表3

多个工具的测试样本数量和覆盖率"

软件名称 样本数量 代码覆盖率/%
随机产生(初始样本) 文献[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

表4

多个工具测试发现软件中的异常数量"

软件名称 异常数量
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 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.
[1] 唐乾,杨飞,黄琪,林果园. 基于TCB子集的访问控制信息安全传递模型[J]. 山东大学学报(理学版), 2016, 51(7): 98-106.
[2] 谢建民,姚兵,赵廷刚. 广义太阳图Sm,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.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 何海伦, 陈秀兰*. 变性剂和缓冲系统对适冷蛋白酶MCP-01和中温蛋白酶BP-01构象影响的圆二色光谱分析何海伦, 陈秀兰*[J]. 山东大学学报(理学版), 2013, 48(1): 23 -29 .
[2] 王碧玉,曹小红*. 算子矩阵的Browder定理的摄动[J]. 山东大学学报(理学版), 2014, 49(03): 90 -95 .
[3] 丁超1,2, 元昌安1,3*, 覃晓1,3. 基于GEP的多数据流预测算法[J]. J4, 2010, 45(7): 50 -54 .
[4] 汤晓宏1,胡文效2*,魏彦锋2,蒋锡龙2,张晶莹2,. 葡萄酒野生酿酒酵母的筛选及其生物特性的研究[J]. 山东大学学报(理学版), 2014, 49(03): 12 -17 .
[5] 曾文赋1,黄添强1,2,李凯1,余养强1,郭躬德1,2. 基于调和平均测地线核的局部线性嵌入算法[J]. J4, 2010, 45(7): 55 -59 .
[6] 郭文鹃,杨公平*,董晋利. 指纹图像分割方法综述[J]. J4, 2010, 45(7): 94 -101 .
[7] 郭乔进,丁轶,李宁. 一种基于上下文信息的乳腺肿块ROI检测方法[J]. J4, 2010, 45(7): 70 -75 .
[8] 邹国平1,马儒宁1,丁军娣2,钟宝江3. 基于显著性加权颜色和纹理的图像检索[J]. J4, 2010, 45(7): 81 -85 .
[9] 胡选子1, 谢存禧2. 基于人工免疫网络的机器人局部路径规划[J]. J4, 2010, 45(7): 122 -126 .
[10] 孟祥波1,张立东1,杜子平2. 均值-方差标准下带跳的保险公司投资与再保险策略[J]. 山东大学学报(理学版), 2014, 49(05): 36 -40 .