跳到主要內容

臺灣博碩士論文加值系統

(3.237.38.244) 您好!臺灣時間:2021/07/24 17:21
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:尤若寧
研究生(外文):Jo-NingYu
論文名稱:應用於深度封包檢測之基於字串切割的低記憶體DFA
論文名稱(外文):A Memory Efficient DFA based on Pattern Segmentation for Deep Packet Inspection
指導教授:張燕光
指導教授(外文):Yeim-Kuan Chang
學位類別:碩士
校院名稱:國立成功大學
系所名稱:資訊工程學系碩博士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2012
畢業學年度:100
語文別:英文
論文頁數:59
中文關鍵詞:深度封包檢測Aho-Corasick決定性有限狀態自動機切割字串比對病毒掃描
外文關鍵詞:Deep packet inspectionAho-CorasickDeterministic Finite AutomataSegmentationPattern matchingvirus scanning
相關次數:
  • 被引用被引用:0
  • 點閱點閱:251
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
隨著網路速度的成長越來越快,資訊安全的問題也越加受到重視。在深度封包檢測(Deep Packet Inspection, DPI)機制中,病毒碼的字串比對效能是整體網路速度成長的瓶頸。如何利用低記憶體執行高效能演算法搜尋封包內用戶資料的潛在病毒是近年來熱門討論的議題。
基於有名的Aho-Corasick (AC) automaton,我們分析AC automaton並提出三種方式來改良記憶體的使用量。首先,我們觀察到某些transitions會回到狀態圖中的前幾層,那是因為目前正在比對的pattern子字串正好為另一條pattern的字首子字串(稱為共同子字串)。基於上述的觀察,我們切割擁有這樣特性的字串成為多條短字串,使得共同子字串可以共用AC automaton中的狀態及transitions。另一方面,我們也觀察到大部分的transitions會回到AC automaton中的前k層(例如:在ClamAV 的病毒字串集合中,transitions回到前四層的條數佔所有transitions的比例為99.52%)因此,我們利用平行架構及k個獨立區塊來維護transition的查詢表格。經由這項技術,AC automaton就可以不記錄回到前k層的transition進而使用較少量的記憶體。最後,我們再利用bit map來壓縮每一個狀態記錄的資料結構之記憶體使用量。透過ClamAV病毒資料庫的實驗結果得知,我們提出的架構所花費的記憶體少於大部分演算法,尤其只需要最佳化版本的AC automaton 0.905%的記憶體使用量。

As the network becomes faster, the role of network intrusion detection system (NIDS) that solves network security problem has become more and more important. The performance of pattern match algorithm is the bottleneck of NIDS. We have to develop a high-throughput algorithm that requires a small amount of memory to find out the hidden virus in packet payload.
Based on the famous Aho-Corasick (AC) automaton, we perform an analysis on the AC automata and propose three methods to reduce the memory usage. First, we observe that some transitions will end up reaching a state in the top few levels of the state diagram because the suffix of current sub-pattern is the prefix of another pattern (called common sub-patterns). We segment these patterns into shorter sub-patterns, based the above observation and so that the states and transitions in the common sub-patterns can be shared. We also observe that most of the transitions go back to the top k levels. (e.g. transitions which ended up arriving the states at the top 4 levels are 99.52% out of the entire transitions in pattern set of ClamAV). Therefore, we use parallel architecture and k independent blocks to maintain the transition table. By this technique, the AC automaton can use fewer memories by not recording the transitions to the top k levels. Finally, we also exploit bit map to compress the memory that is used to record the state information. The results of experiments in ClamAV pattern set show that our proposed scheme uses less memory than the most existing algorithms. Specifically, proposed scheme needs only 0.905% of the memory used in optimized AC automaton.

Chapter 1 Introduction 1
1.1 Motivation 1
1.2 Pattern Matching Problem 2
1.3 The Familiar NIDS and Real-Life Pattern Sets 3
1.3.1 ClamAV 3
1.3.2 Snort 4
1.3.3 Bro 6
1.4 Overview of the Thesis 7
Chapter 2 Background and Related Work 8
2.1 Brute Force Algorithm 8
2.2 Software-Based Approaches 10
2.2.1 Knuth-Morris-Pratt Algorithm 10
2.2.2 Aho-Corasick Algorithm 12
2.3 Hardware-Based Approaches 16
2.3.1 FPGA-Based Techniques 16
2.3.2 TCAM-Based Techniques 17
2.4 Hash-Based Approaches 18
2.5 Other Pattern Matching Approaches 19
Chapter 3 Proposed Scheme 21
3.1 Motivation 21
3.2 Proposed Three Schemes 22
3.2.1 Pattern segmentation 22
3.2.2 Parallel Match Top k Levels 26
3.2.3 Bitmap Application 32
3.3 Construct the Improving Pattern Match Machine 34
3.4 Search Flow of Entire Architecture 40
Chapter 4 Performance Evaluation 46
4.1 Simulation Environment 46
4.2 Analysis 47
4.3 Results of Experiments 51
Chapter 5 Conclusion 57
Chapter 6 References 58

[1]Alfred V. Aho and Margaret J. Corasick, “Efficient string matching: An aid to bibliography search, Comm. Of the ACM, Volume 18, no.6, pp.333-340, 1975.
[2]Mansoor Alicherry, M. Muthuprasanna, and Vijay Kumar, “High Speed Pattern Matching for Network IDS/IPS, In Proceedings of the 14th IEEE International Conference on Network Protocols (ICNP ‘06), pp. 187-196, October 2006.
[3]Burton H. Bloom, “Space/time trade-offs in hash coding with allowable errors, In Proceedings of the ACM, Volume 13, Issue 7, pp. 422-426, July 1970.
[4]R. S. Boyer and J. S. Moore, “A fast string searching algorithm, Communications of the ACM, Volume 20, no 10, pp.762-772, October 1977.
[5]Bro. [Online]. Available: http://bro-ids.org/index.html
[6]Young H. Cho and William H. Mangione-Smith, “Fast Reconfiguring Deep Packet Filter for 1+ Gigabit Network, In Proceedings of the 13th IEEE Field-Programmable Custom Computing Machines (FCCM ‘05), pp. 215-224, April 2005.
[7]ClamAV. [Online]. Available: http://www.clamav.net.
[8]Sarang Dharmapurikar and John W. Lockwood, “Fast and Scalable Pattern Matching for Network Intrusion Detection Systems, In Proceedings of the IEEE Journal on Selected Areas in Communications, Volume 24, Issue 10, pp. 1781-1792, October 2006.
[9]E. Knuth, J. H. M. Jr., and V. R. Pratt, “Fast pattern matching in strings, SIAM J. Comput., vol. 6, no. 2, pp. 323-350, June 1977.
[10]Jan van Lunteren, “High-Performance Pattern-Matching for Intrusion Detection, In Proceedings of the 25th IEEE International Conference on Computer Communications (INFOCOM ‘06), pp. 1-13, April 2006.
[11]Jan van Lunteren, “Searching very large routing tables in wide embedded memory, In Proceedings of the Global Telecommunications Conference (GLOBECOM ‘01), Volume 3, pp. 1615-1619, November 2001.
[12]V. Paxson, “Bro: A system for detecting network intruders in real-time, Computer Networks: The International Journal of Computer and Telecommunications Networking, Volume 31, pp. 2435-2463, 1999.
[13]PCRE web site: http://www.pcre.org
[14]Piti Piyachon and Yan Luo, “Efficient memory utilization on network processors for deep packet inspection, In Proceedings of the ACM/IEEE Symposium on Architectures for Networking and Communications Systems (ANCS ‘06), pp. 71-80, December 2006.
[15]Snort. [Online]. Available: http://www.snort.org.
[16]Tian Song, Wei Zhang, Dongsheng Wang, and Yibo Xue, A memory efficient multiple pattern matching architecture for network security, In Proceedings of the 27th IEEE International Conference on Computer Communications (INFOCOM ‘08), pp. 166-170, April 2008.
[17]Jung-Sik Sung, Seok-Min Kang, Youngseok Lee, Taeck-Geun Kwon, and Bong-Tae Kim, “A multi-gigabit rate deep packet inspection algorithm using TCAM, In Proceedings of the Global Telecommunications Conference (GLOBECOM ‘05) , Volume 1, December 2005.
[18]Lin Tan, Brett Brotherton, and Timothy Sherwood, “Bit-split string-matching engines for intrusion detection and prevention, In Proceedings of the ACM Transactions on Architecture and Code Optimization (TACO ‘06), Volume 3, Issue 1, pp. 3-34, March 2006.
[19]Yang Xu, Lei Ma, Zhaobo Liu, and H. Jonathan Chao, “A Multi-Dimensional Progressive Perfect Hashing for High-Speed String Matching, In Proceedings of the 7th ACM/IEEE Symposium on Architectures for Networking and Communications Systems (ANCS ‘11), pp. 167-177, Oct. 2011.
[20]Yi-Hua E. Yang and Viktor K. Prasanna, “Memory-Efficient Pipelined Architecture for Large-Scale String Matching, In Proceedings of the 17th IEEE Field-Programmable Custom Computing Machines (FCCM ‘09), pp. 104-111, April 2009.
[21]Fang Yu, Randy H. Katz, and T. V. Lakshman, “Gigabit Rate Packet Pattern-Matching Using TCAM, In Proceedings of the 12th IEEE Conference on Network Protocols (ICNP ‘04), pp. 174-183, October 2004.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top