跳到主要內容

臺灣博碩士論文加值系統

(44.211.31.134) 您好!臺灣時間:2024/07/25 18:27
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:張民杰
研究生(外文):Min-Chieh Chang
論文名稱:運用於提升入侵偵測效能的快速多重字串比對
論文名稱(外文):Applying Multi-Pattern Matching Solution to Enhance the Efficiency of Intrusion Detection
指導教授:賴飛羆賴飛羆引用關係
指導教授(外文):Feipei Lai
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:電機工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2004
畢業學年度:92
語文別:英文
論文頁數:70
中文關鍵詞:雜湊表Snort多重字串比對入侵偵測
外文關鍵詞:Intrusion DetectionMulti-pattern matchingHash tableSnort
相關次數:
  • 被引用被引用:1
  • 點閱點閱:175
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:2
以應用『辨識攻擊特徵技術』為基礎的網路入侵偵測系統,是透過網路封包過濾與比對攻擊行為特徵的方式來判定可能的網路攻擊事件並提供警示。

目前而言,網路入侵偵測系統進行入侵偵測時,對大量的網路封包資料進行即時性的特徵比對作業,將耗費釵h作業時間並且對系統整體效能有相當大的影響;因此,如何能提出一個兼具高效率與實用的特徵字串比對方法就成為非常重要的課題。

在本篇研究論文中,我們使用網路型入侵偵測系統『Snort』為研究標的,著手改善並提升關於多重字串特徵比對的效能,在研究中我們以Kim所提出的多重字串比對演算法為基礎,進行理論應用的分析與探討,透過分析在記憶體資源使用與整體速度變化的相對數值,進而使得我們可以根據實際特徵比對的需求,預測投入的記憶體資源使用率,以尋求最佳的記憶體資源配置效能模式。

我們所改進的演算法將有效的降低記憶體的使用率並且平均的效能與AC_BM演算法及Wu_Manber演算法相較之下,具有較佳的表現,而實作應用在Snort的表現上對於入侵偵測與整體服務效能的表現均有效改善。


A typical function of a Network Intrusion Detection Systems ( nIDS ) is based on a set of signatures, each describes one known intrusion threat. A nIDS examines network traffic and determines whether any signatures indicating intrusion attempts are matched. The overall performance mainly depends on packets filtering. Therefore, it is important to define a practical, accurate and efficient pattern matching methodology.

In this thesis, we use a widely adopted nIDS Snort as the experimental tool. We analyze its existing multi-pattern matching algorithms, including AC_BM and Wu_Manber. We introduce another algorithm proposed by Kim. In our improvement, we theoretically analyze the optimal equalization point between memory and speed by using Kim’s algorithm. Our modified algorithm helps the reduction of memory usage and has better performance in speed than the AC_BM and Wu_Manber’s current version Snort 2.0 in average. Therefore our improvement enhances the overall performance of intrusion detection.


Abstract …………………………………………………………........ i
List of Figures ……………………………………………………….. v
List of Tables ………………………………………………………… vii
Chapter 1 Introduction …………………………………………… 1
1.1 Motivation ………………………………………………………….... 1
1.2 Objective …..…………………………………………………..…...... 1
1.3 Thesis Organization …………………………………………………. 2
Chapter 2 Background and Previous Work .…………….………. 3
2.1 Intrusion Detection Systems …………..…………………………….. 3
2.1.1 Introduction to Snort ……….……………………………...... 5
2.2 Aho-Corasick_Boyer-Moore Hybrid Algorithm …………………….. 11
2.3 Wu_Manber Algorithm ………………………………………............ 15
2.4 Kim''s Algorithm ……………………………………………………... 19
Chapter 3 Modeling Kim’s Algorithm and Performance
Enhancement …………………………………………………………
26
3.1 Matching Cost Analysis …….……………………………………….. 27
3.2 Five Sub-processes of Matching Cost …………………..…………… 27
Exp(n) Analysis …………………………………………………… 30
P(A) Analysis ……………………………………………………... 31
P(F) Analysis ……………………………………………………… 32
iii
P(F) Analysis ……………………………………………………… 32
P(D) Analysis …………………………………………………….... 34
3.3 Estimation of each sub-process cost using SimplePower …………… 36
3.4 Summary of Matching Cost …………………………………………. 37
3.5 Optimal Hash Size …………………………………………………... 38
3.6 Implementation Issue on Long Pattern ……………………................ 40
Chapter 4 Results ............................................................................. 43
4.1 Environment ……………………………………………….………… 43
4.2 Experiment Benchmark ……………………………………………... 43
4.3 Results of Theoretical Method ……………………………………..... 44
4.4 Processing Count for each Sub-Process ……………………...……… 48
4.5 Results of different Hash Sizes ………..…………………...………... 50
4.6 Results of Random Data ……………………….……………………. 51
Speed Comparison …………………………………...……………. 52
Memory Comparison …………………………………………….... 54
4.7 Results of Real Data …………………….…………………………… 56
Speed Comparison ……………………………………………….... 57
Memory Comparison …………………………………………….... 59
4.8 Results Analysis……………………………………………………… 60
iv
Chapter 5 Conclusion …….……………………………………….. 64
5.1 Conclusion …………………………………………………………... 64
5.2 Future Work …………………………………………………………. 64
Appendix …………………………………………….………………. 65
Reference …………………………………………………………………………. 69


[1] A. Aho and M. Corasick, Fast pattern matching: an aid to bibliographic search. Commun. ACM, 18(6):333-340, June 1975.
[2] R. Boyer and J. Moore, A fast string searching algorithm. Commun. ACM, 20(10):762-772, October 1977.
[3] S. Kim and Y. Kim, A fast multiple string pattern matching algorithm. In Proceedings of 17th AoM/IAoM Conference on Computer Science, August 1999.
[4] S. Wu and U. Manber, A fast algorithm for multi-pattern searching. Technical Report TR-94-17, University of Arizona, 1994.
[5] C. J. Coit, S. Staniford, and J. McAlerney, Towards faster pattern matching for intrusion detection, or exceeding the speed of snort. In Proceedings of the 2nd DARPA Information Survivability Conference and Exposition (DISCEX II), June 2002.
[6] 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.
[7] M. Fisk and G, Fast Content-Based Packet Handling for Intrusion Detection. UCSD Technical Report CS2001-0670, 2001.
[8] D. Gusfield, Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. University of California Press, 1997.
[9] M. Roesch, Snort: Lightweight intrusion detection for networks. In Proceedings of the 1999 USENIX LISA Systems Administration Conference, November 1999. (software available from http://www.snort.org/).
[10] Snort, Open-source Network Intrusion Detection System. http://www.snort.org
[11] Sourcefire, Snort 2.0 http://www.sourcefire.com/technology/whitepapers.htm
[12] MIT Lincoln Labs, DARPA Intrusion Detection Evaluation. http://www.ll.mit.edu/IST/ideval,1999.
[13] Y.C. Kuo and Y.H. Kuo, A multiple pattern matching method for resource limited network devices. CS. & IE National Cheng Kung University.
[14] J. Beale, J. C. Foster, J. Posluns, R, Russell, B. , Caswell Snort 2.0 Intrusion
Detection Book.
[15] http://www2.ccim.org/~bible/dcb.html King James Bible Download
[16] http://www.snort.org/snort-db/
[17 ] W. Ye, N. Vijaykrishnan, M. Kandemir, and M. J. Irwin. The design and use of SimplePower: A cycle-accurate energy estimation tool. In Proceedings of the Annual ACM IEEE Design Automation Conference, pages 340-345, June 2000.



QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top