JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2019, Vol. 54 ›› Issue (9): 1-8, 35.doi: 10.6040/j.issn.1671-9352.0.2019.205

•   •     Next Articles

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)

RichHTML

22

PDF (PC)

502

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

CLC Number: 

  • TP311

Table 1

Common sample types and their input rules"

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

Fig.1

Program control flow diagram"

Table 2

Stain propagation logic"

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

Fig.2

Stain analysis process"

Fig.3

Signature value calculation process"

Fig.4

Algorithm flow chart"

Table 3

Test sample size and coverage for multiple tools"

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

Table 4

Multiple tool tests to discover the number of anomalies in the software"

软件名称 异常数量
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] XIE Jian-min, YAO Bing, ZHAO Ting-gang. An algorithm and its implementation for odd-elegant labeling of general sun graph Sm,n [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(4): 79-85.
[2] CHEN Lei . On para-communication and pan-communication (Ⅱ) [J]. J4, 2008, 43(5): 32-38 .
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] HE Hai-lun， CHEN Xiu-lan* . Circular dichroism detection of the effects of denaturants and buffers on the conformation of cold-adapted protease MCP-01 and  mesophilic protease BP01[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2013, 48(1): 23 -29 .
[2] WANG Bi-yu, CAO Xiao-hong*. The perturbation for the Browder’s theorem of operator matrix#br#[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(03): 90 -95 .
[3] DING Chao1, 2, YUAN Chang-an1, 3, QIN Xiao1, 3. A prediction algorithm for multi-data streams  based on GEP[J]. J4, 2010, 45(7): 50 -54 .
[4] TANG Xiao-hong1, HU Wen-xiao2*, WEI Yan-feng2, JIANG Xi-long2, ZHANG Jing-ying2, SHAO Xue-dong3. Screening and biological characteristics studies of wide wine-making yeasts[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(03): 12 -17 .
[5] ZENG Weng-fu1, HUANG Tian-qiang1,2, LI Kai1, YU YANG-qiang1, GUO Gong-de1,2. A local linear emedding agorithm based on harmonicmean geodesic kernel[J]. J4, 2010, 45(7): 55 -59 .
[6] GUO Wen-juan, YANG Gong-ping*, DONG Jin-li. A review of fingerprint image segmentation methods[J]. J4, 2010, 45(7): 94 -101 .
[7] GUO Qiao-jin, DING Yi, LI Ning. A context based method for ROI detection in digitized mammograms[J]. J4, 2010, 45(7): 70 -75 .
[8] ZOU Guo-ping1, MA Ru-ning1, DING Jun-di2, ZHONG Bao-jiang3. Image retrieval based on saliency weighted color and texture[J]. J4, 2010, 45(7): 81 -85 .
[9] HU Xuan-zi1, XIE Cun-xi2. A robot local path plan based on artificial immune network[J]. J4, 2010, 45(7): 122 -126 .
[10] MENG Xiang-bo1, ZHANG Li-dong1, DU Zi-ping2. Investment and reinsurance strategy for insurers under #br# mean-variance criterion with jumps#br#[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(05): 36 -40 .
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd