Overview of State Machine Inference Technology for Unknown Protocols

Abstract

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

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.

References

［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.

[1]	WANG Yang1,2, LIU Shi-pei1, WANG Zheng2. A Chinese Address Resolution Model Based on Trie Tree and Finite Automata [J]. Computer and Modernization, 2016, 251(07): 60-67.
[2]	LI Qing-song;ZHANG Ye. Study on Approach for Test Case Generation Based on UML Collaboration Diagram and DFA [J]. Computer and Modernization, 2011, 1(8): 32-38.