跳到主要內容

臺灣博碩士論文加值系統

(54.91.62.236) 您好!臺灣時間:2022/01/18 01:22
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:郭育志
研究生(外文):Yu-Chin Kuo
論文名稱:適用於具系統資源限制之網路設備的多重字串比對方法
論文名稱(外文):A multiple pattern matching method for resource-limited network devices
指導教授:郭耀煌郭耀煌引用關係
指導教授(外文):Yau-Hwang Kuo
學位類別:碩士
校院名稱:國立成功大學
系所名稱:資訊工程學系碩博士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:英文
論文頁數:62
中文關鍵詞:字串比對網路設備
外文關鍵詞:pattern matchingnetwork devices
相關次數:
  • 被引用被引用:0
  • 點閱點閱:299
  • 評分評分:
  • 下載下載:35
  • 收藏至我的研究室書目清單書目收藏:0
在過去幾年,隨著寬頻與無線網路的盛行,越來越多的人們使用低價的網路設備,來將他們的內部網路連接到網際網路上。相對於商業上所使用的高價網路設備而言,這些低價的網路設備使用較低階的處理器與較少的記憶體,也因此有更多的系統資源限制,比如較低處理器的計算能力,較少的記憶體空間與儲存媒體等。所以,當這些低價的網路設備在處理網路上工作負荷大的封包內容過濾與入侵偵測等問題時,如何善用有限的系統資源,顯得更加的重要。
在本篇論文裡,我們首先探討了舊有的字串比對方法應用在系統資源有限的網路設備上的問題。接著我們提出了一個新的多重字串比對方法,稱之為Set-Exclusive Boyer-Moore Horspool(SEBMH)方法。比起傳統的Aho-Corasick方法與最近所提出的Set-Wise Boyer-Moore Horspool方法而言,我們所提出的方法有著較佳的效能並且使用了較少的系統資源。我們所提出的SEBMH方法融合了雜湊表(Hash table)與二層的連結串連(Link-List)架構以節省記憶體資源的使用,同時並加入了Set Exclusive方法以提升效能。我們所提出的新方法將能更有效的幫助那些資源有限的網路設備來解決處理封包內容過濾的問題。
In the past years, due to the popularization of broadband/wireless communication technologies, many SOHO users now construct their Intranet with low-cost embedded network devices to connect to the Internet. These low-cost network devices have low-level CPU and more limitations on system resource (such as the computation power of CPU, memory, static storage, and so on) than traditional expansive network devices. How to save resource is important for these network devices when they are applied to solve the problems of content-based packet filtering and intrusion detection.
In this paper, we show the problems of existing pattern matching methods when they are implemented in a resource-limited network device. We then propose a novel multiple pattern matching method that has better performance than traditional Aho-Corasick(AC) and Boyer-Moore Horspool (BMH) algorithms and uses less resource than Set-Wise Boyer-Moore Horspool algorithm. It adopts hash table to construct an extended Boyer-Moore Hospool approach for multiple pattern matching with Set-Exclusive Shift Table. The HASH-Link-List structure of the proposed approach will have less requirement of memory resource than other Multiple Pattern Matching algorithms. The Set-Exclusive Table also helps to reduce the times of matching. The proposed pattern-matching method has been applied to content-based packet filtering.
Chapter 1 Introduction 1
1.1 Pattern Matching on Firewall and Network Instruction Detection System 1
1.2 Limitation of Embedded Network Device 2
1.3 Motivation 2
1.4 Thesis Organization 3
Chapter 2 Background and Surveys 4
2.1 Hash algorithm 4
2.1.1 PKP Hash 4
2.1.2 Select-Byte Hash 5
2.2 Pattern Matching Algorithms 6
2.2.1 Single Pattern Matching Algorithms 6
2.2.1.1 Boyer-Moore Algorithm (BM) 6
2.2.1.2 Example of Boyer-Moore Algorithm 9
2.2.1.3 Boyer-Moore Horspool Algorithm (BMH) 10
2.2.1.4 Example of Boyer-Moore Horspool Algorithm 11
2.2.2 Multiple Pattern Matching Algorithms 13
2.2.2.1 Set-Wise Boyer Moore Horspool Algorithm (SBMH) 13
2.2.2.2 Aho-Corasick Algorithm (AC) 14
2.2.2.3 Example of Aho-Corasick Algorithm 15
Chapter 3 Design of Set-Exclusive Boyer-Moore Horspool algorithm (SEBMH) 17
3.1 Design Considerations 17
3.2 Algorithm Architecture 18
3.2.1 Overall Structure of SEBMH Algorithm 18
3.2.2 The Input Mask 20
3.2.3 The Hash function 20
3.2.4 Two-Dimensional Link-List Structure 21
3.2.5 Global Shift Table 22
3.2.6 Set-Exclusive Table 24
3.3 Overall procedure of the proposed Set-Exclusive Boyer-Moore Horspool Algorithm 25
3.3.1 Finding the shift value of hash function 26
3.3.2 Construction of the data structure of SEBMH algorithm 26
3.3.3 Searching with SEBMH algorithm 27
Chapter 4 Theoretical Performance Analysis 29
4.1 Best Case Analysis 29
4.2 Worse Case Analysis 30
4.3 Average Case Analysis 30
4.4 Memory Usage Analysis 31
Chapter 5 Experimental Results 34
5.1 Experiments with Different Hash Functions 34
5.2 Experiments with Random Patterns and Data 36
5.2.1 Results of different pattern matching algorithms 36
5.2.2 Experimental results of different hash functions 39
5.3 Experiments with Real Patterns and Random Data 42
5.4 Experiments with Real Patterns and Real Data 47
5.4.1 Introduction to Snort 48
5.4.2 Experimental results 50
Chapter 6 Conclusion and Discussion 54
6.1 Conclusion 54
6.2 Future works 54
References 56
Appendix A 58
Pattern Table of PKP Hash Algorithm 58
Appendix B 59
Test Patterns from Snort 59
[1]Sun Wu and Udi Manber, “A fast algorithm for multi-pattern searching,” Tech. Rep. TR94-17, Department of Computer Science, University of Arizona, May 1994.
[2]D. Gusfield, Algorithms on Strings, Trees, and Sequences, Cambridge University Press, 1997.
[3]Sun Kim and Yanggon Kim, “A fast multiple string-pattern matching algorithm,” Proceedings of the 17th AoM/IAoM Inernational Conference on Computer Science, May 1999.
[4]C. Charras and T. Lecroq, “Handbook of Exact String-Matching Algorithms”
[5]Pearson, Peter K. Fast Hashing of Variable Length Text Strings. Commun. ACM 33, 6 (Jun 1990), p677.
[6] “RFC 3074 : DHC Load Balancing Algorithm, IETF”, http://www.ietf.org/
[7]Boyer, R.S. and J.S. Moore. “A fast string searching algorithm”, Comm. ACM, 20(10) (1977) 62--72.
[8]Horspool R.N., 1980, Practical fast searching in strings, Software - Practice & Experience, 10(6):501-506.
[9]Mike Fisk, George Varghese. “An Analysis of Fast String Matching Applied to Content-Based Forwarding and Intrusion Detection”, IEEE INFOCOM, 2002.
[10]Aho, A.V. and M.J. Corasick. ``Efficient string matching: an aid to bibliographic search,' Comm. ACM, 18(6) (1975) 333--340.
[11]Knuth D.E., Morris (Jr) J.H., Pratt V.R., 1977, Fast pattern matching in strings, SIAM Journal on Computing 6(1):323-350.
[12]“Unicode.org”, http://www.unicode.org/
[13]“Snort.org”, http://www.snort.org/
[14]“Snort Daily Snapshot”, http://www.snort.org/dl/snapshots/
[15]“DARPA : Defense Advanced Research Projects Agency”, http://www.darpa.mil/
[16]“The Information Systems Technology Group (IST) of MIT Lincoln Laboratory”, http://www.ll.mit.edu/IST/ideval/index.html
[17]Martin Roesch, “Snort - lightweight intrusion detection for networks,” in Proceedings of the 13th Systems Administration Conference. 1999, USENIX.
[18]Vern Paxson, “Bro: A system for detecting network intruders in real-time,” Computer Networks, vol. 31, no. 23-24, pp. 2435–2463, Dec. 1999.
[19]Max Vision, “Advanced reference archive of current heuristics for network intrusion detection systems (arachNIDS),” http://www.whitehats.com/ids/.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文