臺灣博碩士論文加值系統

通訊協議逆向工程有助於自動取得通訊協議的標準，並常被網路安全系統以及測試項目產生工具所使用。為了達到更好的準確性，通訊協議逆向工程需要同時擷取訊息交換的順序以及訊息的內容。
然而，現有的技術只著重在將訊息交換的順序轉換成一個有限狀態機而不考慮訊息的內容。擴展有限狀態機使每個狀態具有記憶體，狀態之間的交換也新增了對資料內容的條件，是一個常被用來表示資料內容流的方法。我們提出了一個新的方法 ReFSM ，解析封包記錄檔並轉換成通訊協議的擴展有限狀態機。我們使用了兩種基於文字的通訊協議 (FTP 和 SMTP) 以及兩種二進位的通訊協議(Bittorrent) 來測試我們的方法。根據測試結果顯示 ReFSM 的覆蓋範圍和正確性都高於 90 %，並且推測出來的擴展有限狀態機也很接近通訊協議原本的標準。

Protocol reverse engineering is helpful to automatically obtain the specification of protocols which are useful for network security systems and test case generation tools. To achieve better accuracy, these kinds of applications require good models that should capture not only the order of exchanging message (control flow aspect), but also the data being transmitted (data flow aspect).
However, current techniques only focus on inferring the control flow represented as a Finite State Machines (FSM) and without interpreting the data flow. The Extended Finite State Machine (EFSM), embedding memories in the states and data guards in the FSM transitions, is a method commonly used to represent the data flow. In this work, we propose the ReFSM, a novel method to infer the EFSMs of protocols from only the network traces. Our method is evaluated by using datasets of four network traces including two text-based protocols (FTP and SMTP) and two binary protocols (Bittorrent and PPLive). Based on the evaluation results, the coverage, accuracy scores of correctness and behavior of inferred models are always higher than 90%. The inferred EFSMs are close to the correct model deriving from protocol specification.

摘要 i
Abstract ii
Acknowledgements iii
Table of content iv
List of figures vi
List of tables vii
Chapter 1 Introduction 1
Chapter 2 Background 3
2.1. Extended Finite State Machine 3
2.2. Message type identification. 4
2.3. Inter and intra message dependencies inference 4
2.4. Related works 5
2.4.1. Protocol reverse engineering methodologies 5
2.4.2. Daikon and K-tail algorithm. 6
Chapter 3 Problem Statement 8
3.1. Notations 8
3.2. Problem statement 8
Chapter 4 ReFSM: Reverse Engine for extended Finite State Machine 10
4.1. Overview 10
4.2. Data pre-processing module 10
4.3. Message type identification module 11
4.4. FSM construction module 12
4.5. Semantic deduction module 14
Chapter 5 Evaluation 19
5.1. Experimental setup 19
5.1.1. Implementation 19
5.1.2. Datasets 19
5.1.3. Metrics 20
5.1.4. Choice of compared methods 22
5.2. Experimental result 23
5.2.1. Message type identification accuracy 23
5.2.2. Quality of inferred EFSM. 25
Chapter 6 Conclusions and future works 30

[1] V. Paxson, “Bro: a system for detecting network intruders in real-time,” Comput. Netw., vol. 31, no. 23–24, pp. 2435–2463, Dec. 1999.
[2] G. Bossert, F. Guihéry, and G. Hiet, “Towards Automated Protocol Reverse Engineering Using Semantic Information,” in Proceedings of the 9th ACM Symposium on Information, Computer and Communications Security, New York, NY, USA, 2014, pp. 51–62.
[3] A. T. Dahbura, K. K. Sabnani, and M. U. Uyar, “Formal methods for generating protocol conformance test sequences,” Proc. IEEE, vol. 78, no. 8, pp. 1317–1326, Aug. 1990.
[4] M. Tappler, B. K. Aichernig, and R. Bloem, “Model-Based Testing IoT Communication via Active Automata Learning,” in 2017 IEEE International Conference on Software Testing, Verification and Validation (ICST), 2017, pp. 276–287.
[5] W. Cui, J. Kannan, and H. J. Wang, “Discoverer: Automatic Protocol Reverse Engineering from Network Traces,” in Proceedings of 16th USENIX Security Symposium on USENIX Security Symposium, Berkeley, CA, USA, 2007, pp. 14:1–14:14.
[6] Y. Wang, Z. Zhang, D. D. Yao, B. Qu, and L. Guo, “Inferring Protocol State Machine from Network Traces: A Probabilistic Approach,” in Proceedings of the 9th International Conference on Applied Cryptography and Network Security, Berlin, Heidelberg, 2011, pp. 1–18.
[7] M. A. Beddoe, “Network Protocol Analysis using Bioinformatics Algorithms,” p. 5.
[8] J. Duchêne, C. L. Guernic, E. Alata, V. Nicomette, and M. Kaâniche, “State of the art of network protocol reverse engineering tools,” J. Comput. Virol. Hacking Tech., vol. 14, no. 1, pp. 53–68, Feb. 2018.
[9] R. Agrawal and R. Srikant, “Fast Algorithms for Mining Association Rules in Large Databases,” in Proceedings of the 20th International Conference on Very Large Data Bases, San Francisco, CA, USA, 1994, pp. 487–499.
[10] A. Trifilò, S. Burschka, and E. Biersack, “Traffic to protocol reverse engineering,” in 2009 IEEE Symposium on Computational Intelligence for Security and Defense Applications, 2009, pp. 1–8.
[11] Jaccard, THE DISTRIBUTION OF THE FLORA IN THE ALPINE ZONE. The New Phytologist, 1912.
[12] S. B. Needleman and C. D. Wunsch, “A general method applicable to the search for similarities in the amino acid sequence of two proteins,” J. Mol. Biol., vol. 48, no. 3, pp. 443–453, Mar. 1970.
[13] T. Krueger, H. Gascon, N. Krämer, and K. Rieck, “Learning stateful models for network honeypots,” 2012, p. 37.
[14] C. Leita, K. Mermoud, and M. Dacier, “ScriptGen: an automated script generation tool for Honeyd,” in 21st Annual Computer Security Applications Conference (ACSAC’05), 2005, pp. 12 pp. – 214.
[15] J. Antunes, N. Neves, and P. Verissimo, “Reverse Engineering of Protocols from Network Traces,” in 2011 18th Working Conference on Reverse Engineering, 2011, pp. 169–178.
[16] J.-Z. Luo and S.-Z. Yu, “Position-based automatic reverse engineering of network protocols,” J. Netw. Comput. Appl., vol. 36, no. 3, pp. 1070–1077, May 2013.
[18] D. Lorenzoli, L. Mariani, and M. Pezzè, “Inferring State-based Behavior Models,” in Proceedings of the 2006 International Workshop on Dynamic Systems Analysis, New York, NY, USA, 2006, pp. 25–32.
[19] L. Mariani, M. Pezzè, and M. Santoro, “GK-Tail+ An Efficient Approach to Learn Software Models,” IEEE Trans. Softw. Eng., vol. 43, no. 8, pp. 715–738, Aug. 2017.
[20] M. D. Ernst, J. Cockrell, W. G. Griswold, and D. Notkin, “Dynamically discovering likely program invariants to support program evolution,” IEEE Trans. Softw. Eng., vol. 27, no. 2, pp. 99–123, Feb. 2001.
[21] R. Durbin, S. R. Eddy, A. Krogh, and G. Mitchison, Biological sequence analysis: Probabilistic models of proteins and nucleic acids. Cambridge: Cambridge University Press, 1998.
[22] B. D. Sija, Y. H. Goo, Kyu-Seok-Shim, S. Kim, M. J. Choi, and M. S. Kim, “Survey on network protocol reverse engineering approaches, methods and tools,” in 2017 19th Asia-Pacific Network Operations and Management Symposium (APNOMS), 2017, pp. 271–274.
[23] R. Pang and V. Paxson, “A High-level Programming Environment for Packet Trace Anonymization and Transformation,” in Proceedings of the 2003 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, New York, NY, USA, 2003, pp. 339–351.
[24] V. Hatzivassiloglou and K. R. McKeown, “Towards the Automatic Identification of Adjectival Scales: Clustering Adjectives According to Meaning,” in Proceedings of the 31st Annual Meeting on Association for Computational Linguistics, Stroudsburg, PA, USA, 1993, pp. 172–182.
[25] J. Postel and J. Reynolds, “File Transfer Protocol.” [Online]. Available: https://tools.ietf.org/html/rfc959. [Accessed: 07-May-2018].
[26] [Online]. Available: http://www.bittorrent.org/beps/bep_0003.html. [Accessed: 30-Apr-2018].
[27] V. Dallmeier, N. Knopp, C. Mallon, G. Fraser, S. Hack, and A. Zeller, “Automatically Generating Test Cases for Specification Mining,” IEEE Trans. Softw. Eng., vol. 38, no. 2, pp. 243–257, Mar. 2012.
[28] R. Kohavi, “A Study of Cross-validation and Bootstrap for Accuracy Estimation and Model Selection,” in Proceedings of the 14th International Joint Conference on Artificial Intelligence - Volume 2, San Francisco, CA, USA, 1995, pp. 1137–1143.