未知协议状态机推断技术研究综述

计算机与现代化 ›› 2023, Vol. 0 ›› Issue (05): 58-67.

未知协议状态机推断技术研究综述

（1.南京邮电大学计算机学院,江苏南京210023 南京邮电大学； 2. 南京邮电大学网络安全与可信计算研究所，江苏南京 210023）

出版日期:2023-06-06 发布日期:2023-06-06
作者简介:盛嘉杰（1996—），男，江苏南通人，硕士研究生，研究方向：物联网安全与信息安全， E-mail: sjj754451890@126.com；牛胜杰（1997—），男，山东菏泽人，硕士研究生，研究方向：物联网安全，E-mail: 1220045122@njupt.edu.cn；陈阳（1997—），男，江苏徐州人，硕士，研究方向：物联网安全，E-mail: yyangc@outlook.cn；方伟青（1996—），男，浙江龙泉人，硕士，研究方向：网络安全， E-mail: aili8@foxmail.com；张玉杰（1989—），男，讲师，博士，研究方向：计算机通信网络，无线传感器网络，信息安全， E-mail: zhangyujie@njupt.edu.cn；通信作者：李鹏（1979—），男，福建长汀人，教授，博士生导师，研究方向：网络安全，云计算技术，E-mail: lipeng@njupt.edu.cn；胡素君（1973—），女，河南开封人，副教授，研究方向：计算机网络，E-mail: husj@njupt.edu.cn。
基金资助:
国家自然科学基金资助项目（61872196，61872194，61902196，62102194，62102196）；江苏省六大人才高峰高层次人才项目（RJFW-111）；江苏省研究生科研创新计划（KYCX21_0787）

Overview of State Machine Inference Technology for Unknown Protocols

（1.School of Computer Science， Nanjing University of Posts and Telecommunications， Nanjing 210023， China；
2.Institute of Network Security and Trusted Computing， Nanjing University of Posts and Telecommunications， Nanjing 210023， China）

Online:2023-06-06 Published:2023-06-06

摘要/Abstract

摘要： 协议逆向工程（PRE）描述了协议的行为逻辑，一般分为协议格式提取和状态机构造2个步骤。这2个步骤既相互关联又相互独立，在网络安全领域具有重要意义。本文全面梳理PRE协议状态机推理的相关文献，总结分析协议状态机推理的研究现状和发展趋势。首先，本文介绍PRE的形式化定义和基本原则，并讨论主要领域的具体要求。其次，分析状态机推理方法，并将其分为3种模式：聚类方法、状态相关方法和轮询状态实体方法，然后从不同的角度比较算法的逆向能力和时间效率。最后展望协议状态机推理的发展趋势。

关键词: 协议状态机推断, 协议逆向工程, 协议格式提取, 有限自动机

Abstract: Protocol reverse engineering (PRE) describes the behavioral logic of the protocol， which is generally divided into 2 steps: protocol format extraction and state machine construction. These two steps are both interrelated and independent. PRE has important significance in the field of network security. In this paper， we have comprehensively sort out the relevant reference of protocol state machine inference. The research status and development trend of protocol state machine reasoning are summarized and analyzed. Firstly， we introduce the formal definition and basic principles of PRE and discuss the specific requirements of the main fields. Secondly， we analyze the state machine inference methods and divide them into three patterns: clustering method， state-related method， and polling state entity. Then we compare the inverse ability and time efficiency of the algorithms from different perspectives. Finally， the development trend of protocol state machine reasoning is prospected.

Key words: protocol state machine inference, protocol reverse engineering, protocol format extraction, finite automata

盛嘉杰, 牛胜杰, 陈阳, 方伟青, 张玉杰, 李鹏, 胡素君. 未知协议状态机推断技术研究综述[J]. 计算机与现代化, 2023, 0(05): 58-67.

SHENG Jia-jie, NIU Sheng-jie, CHENG Yang, FANG Wei-qing, ZHANG Yu-jie, LI Peng, HU Su-jun. Overview of State Machine Inference Technology for Unknown Protocols[J]. Computer and Modernization, 2023, 0(05): 58-67.

参考文献［34］

［1］	李美剑. 基于动态二进制分析的协议模型逆向提取及其应用研究［D］. 长沙:国防科学技术大学， 2014.
［2］	DUCHÊNE J， LE GUERNIC C， ALATA E， et al. State of the art of network protocol reverse engineering tools［J］. Journal of Computer Virology and Hacking Techniques， 2017，14(1):53-68.
［3］	KLEBER S， MAILE L， KARGL F. Survey of protocol reverse engineering algorithms: Decomposition of tools for static traffic analysis［J］. IEEE Communications Surveys & Tutorials， 2019，21(1):526-561.
［4］	潘璠，洪征，周振吉，等. 语义层次的协议格式提取方法［J］. 通信学报， 2013，34(10):162-173.
［5］	王晓晨，沈晶，刘海波，等. 自动协议逆向工程研究综述［J］. 计算机应用研究， 2020，37(09):2561-2570.
［6］	吴礼发，王辰，洪征，等. 协议状态机推断技术研究进展［J］. 计算机应用研究， 2015，32(7):1931-1936.
［7］	COMPARETTI P M， WONDRACEK G， KRUEGEL C， et al. Prospex: Protocol specification extraction［C］// The 30th IEEE Symposium on Security and Privacy Berkeley. 2009:110-125.
［8］	TRIFILO A， BURSCHKA S， BIERSACK E. Traffic to protocol reverse engineering［C］// IEEE Symposium on Computational Intelligence for Security and Defense Applications，.2009:1-8.
［9］	李伟明，张爱芳，刘建财，等. 网络协议的自动化模糊测试漏洞挖掘方法［J］. 计算机学报， 2011，34(2):242-255.
［10］	张洪泽，洪征，周胜利，等. 基于协议状态机遍历的模糊测试优化方法［J］. 计算机工程与应用， 2020，56(4):82-91.
［11］	张蔚瑶，张磊，毛建瓴，等. 未知协议的逆向分析与自动化测试［J］. 计算机学报， 2020，43(4):653-667.
［12］	MA R， WANG D G， HU C Z， 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.
［13］	LEITA C， MERMOUND K， DACIER M， et al. ScriptGen: An automated script generation tool for Honeyd［C］// The 21th Annual Computer Security Applications Conference. 2005:203-214.
［14］	CABALLERO J， POOSANKAM P， KREIBICH C， et al. Dispatcher: Enabling active botnet infiltration using automatic protocol reverse-engineering［C］// The 16th ACM Conference on Computer and Communications Security. 2009:621-634.
［15］	唐成华，刘鹏程，汤申生，等. 基于特征选择的模糊聚类异常入侵行为检测［J］. 计算机研究与发展， 2015，52(3):718-728.
［16］	ANTUNES J， NEVES N， VERISSIMO P. Reverse engineering of protocols from network traces［C］// The 18th Working Conference on Reverse Engineering. 2011:169-178.
［17］	王辰，吴礼发，洪征，等. 一种基于状态融合的协议状态机推断方法［J］. 解放军理工大学学报(自然科学版)， 2015，16(4):322-329.
［18］	LANG K， PEARLMUTTER B， PRICE R. Results of the Abbadingo one DFA learning competition and a new evidence-driven state merging algorithm［C］// The 4th International Colloquium on Grammatical Inference. 1998:1-12.
［19］	WANG Y P， ZHANG Z B， YAO D F， et al. Inferring protocol state machine from network traces: A probabilistic approach［C］// The 9th International Conference on Applied Cryptography and Network Security. 2011:1-18.
［20］	王军. 基于EDSM的二进制协议状态机逆向［D］. 哈尔滨：哈尔滨工业大学， 2016.
［21］	孟凡治，刘渊，张春瑞，等. 基于状态相关字段识别的未知二进制协议状态机逆向方法［J］. 电讯技术， 2015，55(4):372-378.
［22］	闫小勇，李青，莫有权. 基于状态相关字段的二进制协议状态机推断［J］. 计算机工程， 2019，45(7):126-133.
［23］	方敏之. 基于流量行为二进制协议逆向分析方法研究与实现［D］. 南京:东南大学， 2021.
［24］	黄笑言，陈性元，祝宁，等. 基于状态标注的协议状态机逆向方法［J］. 计算机应用， 2013，33(12):3486-3489.
［25］	LIN Y R， LAI Y K， BUI Q T， et al. ReFSM: Reverse engineering from protocol packet traces to test generation by extended finite state machines［J］. Journal of Network and Computer Applications， 2020，171:102819.
［26］	SUN F H， WANG S， ZHANG H L. A progressive learning method on unknown protocol behaviors［J］. Journal of Network and Computer Applications， 2022，197(2):103249.
［27］	ANGLUIN D. Learning regular sets from queries and counterexamples［J］. Information and Computation， 1987，75(2):87-106.
［28］	VALIANT L G. A theory of the learnable［J］. Communications of the ACM， 1984，27(11):1134-1142.
［29］	DUPONT P， LAMBEAU B， DAMAS C， et al. The QSM algorithm and its application to software behavior model induction［J］. Applied Artificial Intelligence， 2008，22(1):77-115.
［30］	ONCINA J， GARCIA P. Inferring regular languages in polynomial update time［J］. Pattern Recognition and Image Analysis， 1992，1(1):49-61.
［31］	王辰，吴礼发，洪征，等. 一种基于域知识的协议状态机主动推断算法［J］. 计算机科学， 2015，42(12):233-239.
［32］	SZÉKELY G， LÁDI G， HOLCZER T， et al. Protocol state machine reverse engineering with a teaching-learning approach［J］. Acta Cybernetica， 2021，25(2):517-535.
［33］	KRAMER M， BADER S， OELMANN B. Reverse Engineering Enhanced State Models of Black Box Software Components to Support Integration Testing［D］. Laboratoire Informatique de Grenoble， 2008.
［34］	潘雁，林伟，祝跃飞. 渐进式的协议状态机主动推断方法［J/OL］. 网络与信息安全学报， 2022（2022-05-09）［2022-05-30］. https://kns.cnki.net/kcms2/article/abstract?
	v=3uoqIhG8C45S0n9fL2suRadTyEVl2pW9UrhTDCdPD66
	Sr0yZ-At6r3ZZ0-X5GzOOL6Lq-Z3hGgLSWHH-XlVloJx
	0BboRkqHq&uniplatform=NZKPT.