跳到主要內容

臺灣博碩士論文加值系統

(3.231.230.177) 您好!臺灣時間:2021/08/02 11:48
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:梁文澤
研究生(外文):Wen-TseLiang
論文名稱:Cool DFACAM: 以DFA為基礎的深度封包檢測之TCAM節能架構
論文名稱(外文):Cool DFACAM: a Power-Efficient TCAM Architecture for DFA-based Deep Packet Inspection
指導教授:張燕光
指導教授(外文):Yeim-Kuan Chang
學位類別:碩士
校院名稱:國立成功大學
系所名稱:資訊工程學系碩博士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2012
畢業學年度:100
語文別:英文
論文頁數:55
中文關鍵詞:深度封包檢測有限狀態機正規表示法比對三態內容尋址記憶體
外文關鍵詞:Deep packet inspectionDeterministic Finite AutomataRegular expression matchingTernary Content Addressable Memory
相關次數:
  • 被引用被引用:0
  • 點閱點閱:1118
  • 評分評分:
  • 下載下載:15
  • 收藏至我的研究室書目清單書目收藏:0
一個可靠的深度封包檢測(Deep Packet Inspection, DPI)的機制,保護我們的電腦免受蠕蟲和病毒在網路上攻擊。深度封包檢測檢查封包中的用戶資料(payload)以用來偵測是否有惡意的特徵存在。正規表示法(Regular Expression, RegEx)比對是現代網路設備中一項重要的工作。包括如DPI或是分析協議(protocol analysis)等。確定性有限狀態機(Deterministic Finite Automata, DFA)可以有效地處理正規表示法比對的問題,對於一個輸入字元,DFA只需要存取一次記憶體即可完成。如使用三態內容尋址記憶體(Ternary Content-addressable memory, TCAM)實現DFA,有著平行搜尋功能以及三態(Don’t care)的比對功能,而TCAM已經廣泛應用在現代的網路設備中。但是TCAM卻有著需要消耗更高功率的問題。
因此,在這篇論文當中,我們首先提出兩種方法劃分DFA成多個組別,而各個組別會儲存在一個或多個TCAM分段中(block of TCAM),使得在查詢的過程中只需要啟動相對應的TCAM分段,以節省TCAM的功率消耗。再者,一個最佳化的方法進一步地再合併TCAM的entry,讓啟動的TCAM區塊的平均使用率約為1個區塊。我們使用的病毒規則表是取自於Snort和Bro兩種開放原始碼的軟體以及Linux應用層防火牆(Layer-7 Filter)。實驗結果顯示,我們提出的方法針對使用的病毒規則表可以有效地的減少約32%至98%的記憶體使用量。
A reliable Deep packet inspection (DPI) system protects our computers from being attacked by worms and viruses on the Internet. The DPI system inspects the payload of packets to detect whether malicious signatures exists or not. Regular expression (RegEx) matching has become an important engine of modern network device such as DPI, protocol analysis, and so on. Deterministic Finite Automata (DFA) is efficient at regular expression matching while it takes once memory access to match each input symbol. Ternary Content Addressable Memories (TCAMs) have been widely deployed in modern network devices with the feature of parallel searching and “Don’t Care” matching capability. However, the usage of TCAM results in higher power consumption.
In this thesis, we first propose two schemes to divide the DFA into several groups each of which is stored in one or more TCAM blocks such that each searching operation only needs corresponding TCAM blocks to be activated to reduce power consumption. Second, an optimization scheme is proposed to further merges TCAM entries to have the utilization of activated block is to be 1 at most. Our design is simulated by using real-life rule-sets from the open source software, Snort and Bro, and Linux layer-7filter. The simulation results show that our proposed schemes reduce the memory consumption dramatically in different rule-sets with the compression rate at about 32% to 98.9%
Table of Contents
Chapter 1 Introduction 1
1.1 Motivation 1
1.2 Bro 2
1.3 ClamAV 3
1.4 Linux layer-7 filter 3
1.5 Snort 4
1.6 Pattern Matching Problem 5
1.7 Organization of the Thesis 6
Chapter 2 Related Work 7
2.1 Introduction 7
2.2 Software-based method 7
2.2.1 Boyer-Moore algorithm 7
2.2.2 Aho-Corasick Algorithm 9
2.2.3 DFA and NFA 11
2.3 Hardware-based method 13
2.4 TCAM-based method 14
2.5 Prior Work 17
Chapter 3 Proposed Scheme 24
3.1 Introduction 24
3.2 Analysis of DFA 24
3.3 Problem statements and Preliminaries 26
3.4 Scheme 1 – group by having the same most number of next state 29
3.5 Scheme 2 – group by common similar state 33
3.6 Optimization 37
Chapter 4 Performance Evaluation 40
4.1 Introduction 40
4.2 Results 42
4.3 Analyzing Result 47
Chapter 5 Conclusion 53
Chapter 6 References 54
[1]Application Layer Packet Classifier for Linux: http://l7-filter.sourceforge.net/
[2]B. Agrawal and T. Sherwood. “Modeling TCAM power for next generation network devices, in IEEE Symposium on Peoformace Analysis of Systems and Software, 2006.
[3]A. V. Aho and M. J. Corasick, “Efficient string matching: An aid to bibliography search, Comm. Of the ACM, vol 18, no.6, pp.333-340, 1975.
[4]M. Alicherry, M. Muthuprasanna, and V. Kumar. “High speed pattern matching for network IDS/IPS. In Proc. of IEEE ICNP, 2006.
[5]M. Becchi, P. Crowley, “An improved algorithm to accelerate regular expression evaluation, in Proc. ANCS, 2007.
[6]M. Becchi, P. Crowley, “Efficient reqular expression evaluation: Theory to practice. In Proc. ANCS, 2008.
[7]M. Becchi, M. Franklin and P. Crowley, “A Workload for Evaluating Deep Packet Inspection Architectures, in IISWC 2008.
[8]R.S. Boyer and J. S. Moore, “A fast string searching algorithm, Communcations of the ACM, vol.20 no10, pp. 762-772, Oct. 1977.
[9]A. Bremler-Barr, D. Hay and Y. Koral. “CompactDFA: generic state machine compression for scalabe pattern matching. In Proc. INFOCOM, 2010
[10]Bro: http://bro-ids.org
[11]Clam Anti-Virus signature database: http://www.clamav.net
[12]J.E. Hopcroft and J.D. Ullman “ Introduction to Automata Theory, Language and Computation “, Addison Wesley, 1979.
[13]S. Kumar, S. Dharmapurikar, F. Yu, P. Crowley and J. Turner,Algorithms to accelerate multiple regular expressions matching for deep packet inspection. In Proc. SIGCOMM, 2006.
[14]S. Kumar, J. Turner and J. Williams. “Advanced algorithms for fast and scalable deep packet inspection. In Proc. ANCS, pp. 81-92, 2006.
[15]S. Kumar, B. Chandrasekaran, J. Turner and G. Varghese.Curing regular expression matching algorithms from insomnia, amnesia and acalculid. In Proc. ANCS, 2007.
[16]R. Smith, C. Estan and S. Jha. “XFA: Faster signature matching with extended aotomata. In Proc. Symposium on Security and Privacy, 2008
[17]R. Smith, C. Estan, S. Jha and S. Kong. “Deflating the big bang: fast and scalable deep packet inspection with extended finite aotomata. In Proc. SIGCOMM, pp. 207-218, 2008
[18]Snort: http://www.snort.org
[19]T. Song, W. Zhang, D. Wang and Y. Xue, “A memory efficient muliple pattern matching architrcture for network security, INFOCOM 2008. pages 166-170.
[20]L. Tan and T. Sherwood, “A High Throughput String Matching Architecture for Intrusion Detection and Prevention, in IEEE ISCA, pp. 112-122, 2005.
[21]Q. Wang and V. K. Prasanna, “Multi-Core Architecture on FPGA for Large Dictionary String Matching, in 17th IEEE Symposium on Field Programmable Custom computing Machines, pp. 96-103, 2009.
[22]F. Zane, G. Narlikar and A. Basu. “CoolCAMs: Power-Efficient TCAMs for Forwarding Engines In. IEEE INFOCOM, 2003

連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top