跳到主要內容

臺灣博碩士論文加值系統

(3.236.124.56) 您好!臺灣時間:2021/07/31 08:00
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:李建佑
研究生(外文):Jian-You Li
論文名稱:一個用於網路入侵偵測及避免系統的平行字串比對演算法
論文名稱(外文):A parallel string matching algorithm for network intrusion detection and prevention system
指導教授:王丕中
學位類別:碩士
校院名稱:國立中興大學
系所名稱:資訊科學與工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
畢業學年度:96
語文別:中文
論文頁數:65
中文關鍵詞:網路入侵偵測系統平行運算TCAM位元切割Cross Product
外文關鍵詞:NIDSParallel ComputationTCAMBit-SpiltCross Product
相關次數:
  • 被引用被引用:0
  • 點閱點閱:86
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
網路入侵偵測系統(Network Intrusion Detection System)是為了有效防範來自網路的匿名惡意攻擊所研發的系統,它能有效率的過濾出可疑的封包且回報,它的過濾機制主要是由IP Header的檢查和封包payload的字串比對所組成。網路入侵偵測系統的效能主要是受到字串比對那龐大的運算成本所限制,故改善字串比對引擎的效能也會增進網路入侵偵測系統的整體效能。
我們提出了一個由兩個平行的字串比對引擎所組成的演算法,一者為Fang Yu et al.演算法中以TCAM(Ternary Content-Addressable Memory)處理短字串的字串比對引擎所改進的演算法來處理較短的字串,以求在合理的記憶體需求下,達到改進效能及減輕另一個字串比對引擎的負擔。另一者為延伸自Tan et al.演算法的位元分割的Aho-Corasick演算法的概念,及加上Cross Product的概念來減少其平行運算的成本,且以可接受的記憶體花費換取快速的比對效能。
由實驗的結果可得知,我們的演算法在記憶體需求及比對效能上皆優於所比較的演算法,整體字串比對引擎效能最快可達1.9Gbps,且只需約3.5MBytes的記憶體需求。
Network Intrusion Detection System (NIDS) is a system for preventing the anonymous and malicious attacks from network by filtering suspicious packets and report them. NIDS''s filtering mechanism is composed by checking IP Header and matching pattern in packet payload. Therefore, NIDS''s performance is restricted by the huge cost of computation for string matching processing. Improving the performance of string matching engine is also improving the performance of NIDS.
We propose an algorithm consisted of two parallel string matching engine. The first string matching engine improves the TCAM-based approach to handle the string matching for shorter pattern in Fang Yu et al. algorithm. By using reasonable amount of memory, a better performance is achieved and the loading of another string matching engine is reduced. Our second string matching engine extends the concept of bit-spilt Aho-Corasick algorithm in Tan et al. algorithm. With the concept of cross product, the cost of parallel computation is reduced without losing search performance.
The simulation results show that our approach is superior between compared algorithms at the requirement of memory and the search performance of string matching. The peak performance of our string matching engine is about 1.9Gbps while the requirement of our string matching engine only needs about 3.5MBytes.
第一章、緒論 1
1.1 Snort 網路入侵偵測系統 4
1.2 字串比對問題描述 5
1.3 研究動機 6
1.4 主題概述 7
第二章、相關研究 8
2.1 Aho-Corasick演算法 8
2.1.1 非決定性的有限狀態機 9
2.1.2 決定性的有限狀態機 11
2.2 Wu-Manber 演算法 13
2.3 Tan et al.演算法 15
2.4 Dharmapurikar et al.演算法 16
2.5 Fang Yu et al. 演算法 18
第三章、主要方法 21
3.1 基於需求的Cross Product 23
3.2 減少交集的產生 28
3.3 取出字串 30
3.4 針對短字串的TCAM演算法 34
3.5 位元狀態機的加速方法 42
3.6 整體字串比對引擎架構 44
第四章、實驗與分析 48
4.1 Snort字串集合與DEFCON封包資料 50
4.2 長度門檻值 51
4.3 TCAM寬度的實驗與分析 52
4.4 位元分割大小的實驗與分析 54
4.5 位元狀態機加速實驗 58
4.6 效能與總記憶體需求的實驗與分析 59
第五章、結論與未來展望 63
參考文獻 64
[1] I. M. Research. “Intrusion detection/prevention product revenue up 9% in 1Q04,” Technical report, June 2004.

[2] Snort – the de Facto Standard for Intrusion Detection/Prevention, [Online].
Available: www.snort.org

[3] M. Fisk and G. Varghese. “An analysis of fast string matching applied to content-based forwarding and intrusion detection,” Technical Report CS2001-0670 (updated version), University of California - San Diego, 2002.

[4] A. Aho and M. Corasick, “Efficient string matching: An aid to bibliographic search,” Communications of the ACM, vol. 18, no. 6, pp.333-343, June 1975.

[5] D. 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.

[6] L. Tan and T. Sherwood, “A high throughput string matching architecture for intrusion detection and prevention,” in ISCA, 2005.

[7] S. Wu and U. Manber, “A fast algorithm for multi-pattern searching,” Tech. Report, TR94-17, U of Arizona, May 1994.

[8] R. S. Boyer and J. S. Moore, “A fast string searching algorithm,” Communications of the ACM, vol. 20, no 10, pp.762-772, Oct. 1977.

[9] Y. D. hong, X. Ke,C. Yong. “An Improved Wu-Manber Multiple Patterns Matching Algorithm,” IEEE IPCCC ,April 2006.

[10] L. Tan and T. Sherwood, “A high throughput string matching architecture for intrusion detection and prevention,” in ISCA, 2005.

[11] B. Chazelle, J. Kilian, R. Rubinfeld, A. Tal, “The Bloomier filter: an efficient data structure for static support lookup tables,” Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 30–39.

[12] S. Dharmapurikar, P. Krishnamurthy, T. S. Sproull and J. W. Lockwood, “Deep Packet Inspection using Parallel Bloom Filters,” IEEE Micro, vol. 24,no. 1, pp. 52-61,Jan 2004.

[13] F.Yu, R. H. Katz, T. V. Lakshman, “Gigabit Rate Packet Pattern-Matching Using TCAM”, in Proceeding of 12th IEEE International Conference on Network Protocols(ICNP’ 04), Berlin ,Germany, Oct. 2004, pp. 174-183.

[14] S. Azgomi, “Using content addressable memory for network applications,”
[Online]. Available: http://www.commsdesign.com/main/1999/11/9911feat3.htm ,
1999.

[15] L. Tan, B. Brotherton, T. Sherwood, “Bit-Split String-Matching Engines for Intrusion Detection and Prevention,” ACM Transactions on Architecture and Code Optimization, Vol. 3, NO. 1, March 2006, Pages 3-34.

[16] J. S. Sung, S. M. Kang, Y. Lee, T. G. Kwon, B. T. Kim, “A multi-gigabit rate deep packet inspection algorithm using TCAM,” GLOBECOM ''05. IEEE Volume 1, Dec. 2005 Page(s):5 pp.

[17] DEFCON. http://www.shmoo.com/ , http://cctf.shmoo.com/data/cctf-defcon10/

[18] TCPDUMP, http://www.tcpdump.org/

[19] M. Norton, “Optimizing Pattern Matching for Intrusion Detection,” Jul. 2004. [Online]. Available: http://docs.idsresearch.org/OptimizingPatternMatchingForIDS.pdf
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top