賴飛羆臺灣大學：電機工程學研究所張民杰Chang, Min-ChiehMin-ChiehChang2007-11-262018-07-062007-11-262018-07-062004http://ntur.lib.ntu.edu.tw//handle/246246/53282以應用『辨識攻擊特徵技術』為基礎的網路入侵偵測系統，是透過網路封包過濾與比對攻擊行為特徵的方式來判定可能的網路攻擊事件並提供警示。 目前而言，網路入侵偵測系統進行入侵偵測時，對大量的網路封包資料進行即時性的特徵比對作業，將耗費釵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 …………………………………………………………………………. 69808429 bytesapplication/pdfen-US雜湊表Snort多重字串比對入侵偵測Intrusion DetectionMulti-pattern matchingHash tablethesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53282/1/ntu-93-P90921010-1.pdf