计算机科学 ›› 2021, Vol. 48 ›› Issue (12): 85-93.doi: 10.11896/jsjkx.200800178

• 计算机软件 • 上一篇    下一篇

基于深度优先搜索的模糊测试用例生成方法

李毅豪, 洪征, 林培鸿   

  1. 中国人民解放军陆军工程大学指挥控制工程学院 南京210000
  • 收稿日期:2020-08-27 修回日期:2020-09-25 出版日期:2021-12-15 发布日期:2021-11-26
  • 通讯作者: 洪征(hz5215@163.com)
  • 作者简介:enhancelee@foxmail.com
  • 基金资助:
    国家重点研发计划基金资助项目(2017YFB0802900)

Fuzzing Test Case Generation Method Based on Depth-first Search

LI Yi-hao, HONG Zheng, LIN Pei-hong   

  1. Command and Control Engineering College,Army Engineering University of PLA,Nanjing 210000,China
  • Received:2020-08-27 Revised:2020-09-25 Online:2021-12-15 Published:2021-11-26
  • About author:LI Yi-hao,born in 1996,postgraduate.His main research interests include cyberspace security and protocol reverse engineering.
    HONG Zheng,born in 1979,Ph.D,associate professor.His main research in-terests include cyberspace security and protocol reverse engineering.
  • Supported by:
    National Key R&D Program of China (2017YFB0802900).

摘要: 模糊测试是挖掘网络协议漏洞的重要方法之一。现有的模糊测试方法存在覆盖路径不完全、效率低下等问题。为了解决这些问题,文中提出了基于深度优先搜索的模糊测试用例生成方法,该方法将状态机转换成有向无回路图,以获得状态迁移路径,并通过提高测试用例在发送报文中的占比来提升模糊测试效率。该方法主要包括合并状态迁移、消除循环路径、搜索状态迁移路径、标记重复状态迁移和基于测试用例引导的模糊测试5个阶段。在合并状态迁移阶段,将首尾状态相同的状态迁移进行合并。在消除循环路径阶段,根据深度优先搜索判断图中的循环,并通过删除边将状态机转换成有向无回路图。在搜索状态迁移路径阶段,搜索有向无回路图从初始状态到终止状态的全路径,并对原状态机图使用Floyd算法补充被去除的边构造测试路径,以确保充分测试状态机中的每一个状态迁移。在标记重复状态迁移阶段,对重复状态迁移进行标记,避免对重复的状态迁移进行反复测试,以缩减测试的冗余。在基于测试用例引导的模糊测试阶段,生成针对状态迁移的测试用例,并将测试用例均匀分发到重复的状态迁移上,其中的部分测试用例能够起到引导状态迁移的作用,对被测目标进行模糊测试。实验结果表明,所提方法能够取得更高的有效测试用例比例。

关键词: 模糊测试, 漏洞挖掘, 有状态协议, 协议状态机, 深度优先搜索

Abstract: Fuzzing test is an important method to exploit network protocol vulnerability.Existing fuzzing test methods have some problems such as incomplete path coverage and low efficiency.To solve these problems,this paper proposes a depth-first search based fuzzing test case sgeneration method.The method transforms the state machine into a directed acyclic graph to obtain the state transition paths,and increases the proportion of test cases in the testing messages to improve the fuzzing efficiency.The method includes five stages:merging state transition,eliminating loops,searching state transition paths,marking the same state transitions,and test case guidance based fuzzing test.Firstly,the state transitions which have the same start states and end states are merged.Secondly,according to the depth-first search,the loops in the graph are found,and the state machine is converted into a directed acyclic graph by deleting the edges of the loops.Thirdly,the directed acyclic graph is analyzed for the full path from the initial state to the end state,and the original state machine graph is supplemented with the removed edges using Floyd algorithm to construct the complete test paths,so as to ensure that each state transition in the state machine can be fully tested.Fourthly,repeated state transitions are marked to avoid repeated test of similar state transitions and reduce testing redundancy.Finally,test cases for state transitions are generated,and test cases which may guide the state transition are distributed evenly over the repetitive state transitions to carry out fuzzing test on the target.Experimental results show that the proposed method can achieve higher proportion of valid test cases.

Key words: Fuzzing test, Vulnerability discovery, Stateful protocol, Protocol state machine, Depth first search

中图分类号: 

  • TP398.08
[1]ZHANG X,LI Z J.Survey of Fuzz Testing Technology[J].Computer Science,2016,43(5):1-8,26.
[2]ZHANG H Z,HONG Z,ZHOU S L,et al.A fuzzing optimization method based on protocol state migration traversal[J].Computer Engineering and Applications,2019,56(4):82-91.
[3]Oulu University Secure Programming Group.The PROTOS Project[EB/OL].[2020-08-09].https://www.ee.oulu.fi/research/ouspg/Protos.
[4]EDDINGTON M.PeachFuzzer[EB/OL].[2020-08-09].https://sourceforge.net/projects/peachfuzz.
[5]GitHub.Sulley[EB/OL].(2013-06-11)[2020-08-09].https://github.com/OpenRCE/sulley.
[6]Spike fuzzing platform [EB/OL].[2017-08-11].http://www.immunitysec.com/resourcesfreesoftware.shtml.
[7]SONG C,YU B,ZHOU X,et al.SPFuzz:A Hierarchical Sche- duling Framework for Stateful Network Protocol Fuzzing[J].IEEE Access,2019,7:18490-18499.
[8]LI J L,CHEN Y L,LI Z,et al.Mining RSTP Protocol Vulnerabilities Based on Traversal of Protocol State Graph[J].Compu-ter Science,2018,45(9):171-176.
[9]MA R,WANG D,HU C,et al.Test data generation for stateful network protocol fuzzing using a rule-based state machine[J].Tsinghua Science and Technology,2016,21(3):352-360.
[10]RONG F,CHANG Y.Machine Learning for Black-Box Fuzzing of Network Protocols[C]//Proceedings of the International Conference on Information and Communications Security.2017:621-632.
[11]ZHANG S D,ZHANG L Y.Vulnerability Mining for Network Protocols Based on Fuzzing[C]//Proceedings of the 2014 2nd International Conference on Systems and Informatics.2014:644-648.
[12]HUANG Y,ZOU Q W,FAN K F.Fuzzing test-based vulnerability mining for industrial control network protocol[J].Journal on Communications,2018,39(S2):181-188.
[13]WANG G B,ZHAO J L,CUI B J.Fuzzing method based on field filter and packet repair for GTPv2 protocol[J].Internet of Things,2019,8(100104):1-7.
[14]ZHANG W Y,ZHANG L,MAO J L,et al.An Automated Method of Unknown Protocol Fuzzing Test[J].Computer Science,2020,43(4):653-667.
[15]NEMINATH H,JONATHAN S.Detecting TCP ACK storm attack:a state transition modelling approach[J].IET Networks,2018,7(6):429-434.
[16]BOSSERT G,HIET G,HENIN T.Modelling to simulate botnet command and control protocols for the valuation of network intrusion detection systems[C]//2011 Conference on Network and Information System Security (SAR-SSI).La Rochelle:IEEE,2011:1-8.
[17]ZUO X F,SHEN W J.An Improved Algorithm for Multiple Shortest Path Problem Based on Floyd Algorithm[J].Compu-ter Science,2017,44(5):232-234,267.
[18]MA R,REN S,MA K,et al.Semi-valid Fuzz Testing Case Ge- neration for Stateful Network Protocol[J].Tsinghua Science and Technology,2017,22(5):458-468.
[1] 李明磊, 黄晖, 陆余良, 朱凯龙. SymFuzz:一种复杂路径条件下的漏洞检测技术[J]. 计算机科学, 2021, 48(5): 25-31.
[2] 郑建云, 庞建民, 周鑫, 王军. 基于约束推导式的增强型二进制漏洞挖掘[J]. 计算机科学, 2021, 48(3): 320-326.
[3] 赵赛, 刘昊, 王雨峰, 苏航, 燕季薇. Android组件间通信的模糊测试方法[J]. 计算机科学, 2020, 47(11A): 303-309.
[4] 李佳莉, 陈永乐, 李志, 孙利民. 基于协议状态图遍历的RTSP协议漏洞挖掘[J]. 计算机科学, 2018, 45(9): 171-176.
[5] 锁延锋,王少杰,秦宇,李秋香,丰大军,李京春. 工业控制系统的安全技术与应用研究综述[J]. 计算机科学, 2018, 45(4): 25-33.
[6] 张亚丰,洪征,吴礼发,周振吉,孙贺. 基于状态的工控协议Fuzzing测试技术[J]. 计算机科学, 2017, 44(5): 132-140.
[7] 程诚,周彦晖. 基于模糊测试和遗传算法的XSS漏洞挖掘[J]. 计算机科学, 2016, 43(Z6): 328-331.
[8] 张雄,李舟军. 模糊测试技术研究综述[J]. 计算机科学, 2016, 43(5): 1-8.
[9] 李 洋,文中华,伍小辉,劳佳琪. 求最小期望权值强循环规划解[J]. 计算机科学, 2015, 42(4): 217-220.
[10] 王辰,吴礼发,洪征,郑成辉,庄洪林. 一种基于域知识的协议状态机主动推断算法[J]. 计算机科学, 2015, 42(12): 233-239.
[11] 余莹,李肯立,郑光勇. 一种基于GPU集群的深度优先并行算法设计与实现[J]. 计算机科学, 2015, 42(1): 82-85.
[12] 张亚军,李舟军,廖湘科,蒋瑞成,李海峰. 自动化白盒模糊测试技术研究[J]. 计算机科学, 2014, 41(2): 7-10.
[13] 侯莹,洪征,潘增,吴礼发. 基于模型的Fuzzing测试脚本自动化生成[J]. 计算机科学, 2013, 40(3): 206-209.
[14] 史飞悦,傅德胜. 缓冲区溢出漏洞挖掘分析及利用的研究[J]. 计算机科学, 2013, 40(11): 143-146.
[15] 陈韬,孙乐昌,潘祖烈,刘京菊. 基于文件格式的漏洞挖掘技术研究[J]. 计算机科学, 2011, 38(Z10): 78-82.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 张宏伟,党瑞荣. 基于Internet对潜油电泵温度压力的远程监控[J]. 计算机科学, 2016, 43(Z6): 551 -554 .
[2] 潘孝勤, 芦天亮, 杜彦辉, 仝鑫. 基于深度学习的语音合成与转换技术综述[J]. 计算机科学, 2021, 48(8): 200 -208 .
[3] 王俊, 王修来, 庞威, 赵鸿飞. 面向科技前瞻预测的大数据治理研究[J]. 计算机科学, 2021, 48(9): 36 -42 .
[4] 余力, 杜启翰, 岳博妍, 向君瑶, 徐冠宇, 冷友方. 基于强化学习的推荐研究综述[J]. 计算机科学, 2021, 48(10): 1 -18 .
[5] 王梓强, 胡晓光, 李晓筱, 杜卓群. 移动机器人全局路径规划算法综述[J]. 计算机科学, 2021, 48(10): 19 -29 .
[6] 高洪皓, 郑子彬, 殷昱煜, 丁勇. 区块链技术专题序言[J]. 计算机科学, 2021, 48(11): 1 -3 .
[7] 毛瀚宇, 聂铁铮, 申德荣, 于戈, 徐石成, 何光宇. 区块链即服务平台关键技术及发展综述[J]. 计算机科学, 2021, 48(11): 4 -11 .
[8] 余杰, 纪斌, 刘磊, 李莎莎, 马俊, 刘慧君. 面向中文医疗事件的联合抽取方法[J]. 计算机科学, 2021, 48(11): 287 -293 .
[9] 张倩, 肖丽. 基于流线的流场可视化绘制方法综述[J]. 计算机科学, 2021, 48(12): 1 -7 .
[10] 王焘, 张树东, 李安, 邵亚茹, 张文博. 一种面向异常传播的微服务故障诊断方法[J]. 计算机科学, 2021, 48(12): 8 -16 .