- 學位論文
適合高速網路入侵偵測系統之平行字串比對演算法設計
A Parallel String Matching Algorithm for High Speed Network Intrusion Detection System
若您是本文的作者，可授權文章由華藝線上圖書館中協助推廣。
摘要
現今電腦的發展越來越普遍，而網際網路的應用也無所不在。在這樣子的環境下，電腦的資訊安全議題也就變得日趨重要；網路入侵偵測系統 (NIDS) 的重要性也因此越來越被重視。然而在網路入侵偵測系統中，大部份的系統處理被字串比對所佔據，因此字串比對演算法的設計將嚴重影響系統成為效能的瓶頸。本論文著眼於網路入侵偵測系統的核心技術 – 字串比對演算法，設計出新的演算法來加速字串比對的效能。 我們藉由觀察有限狀態機(DFA)，發現在有限狀態機中的每個字元的下一個狀態通常都會對應到一個特定的狀態而與目前狀態無關，稱此狀態為字元所對應的特殊狀態(Magic-State)。因此，我們基於Aho-Corasick演算法和Magic-State特性，設計出一個能一次處理多個字元數的MACMS(Multiple-character AC with Magic-State)演算法。透過利用Magic-state的特性，MACMS演算法能夠迅速預測AC在處理多個字元後的結果，而使得MACMS演算法能夠一次處理多個字元來達到提高字串比對的效能。 實驗數據顯示, 利用MACMS演算法建構Snort Rule，只須要117 KB的TCAM以及98 KB的SRAM即可處理Snort Rule。當TCAM與SRAM的頻率在600MHz時，本論文所提出的系統架構透過一次處理10個字元方式可將字串比對的速度提升到48Gbps。
關鍵字
字串比對參考文獻
[3] “Current Trends in IDS and IPS,”[On-line].
[5] S. Antonatos, K. G. Anagostakis, and E. P. Markatos, “Generating realistic work loads for network intrusion detection systems.” ACM Workshop on Software and Performance, Redwood Shores, CA., USA, 2004.
[6] A. V. Aho and M. J. Corasick, “Efficient string matching: and aid to bibliographic search,” Communications of ACM, 18(6):333-340, 1975.
[9] R. T. Liu, N. F. Huang, C. H. Chen, and C. N. Kao, “A fast string-match algorithm for network processor-based net work intrusion detection system,” ACM Transactions on. Embedded Computer Systems, Vol.3, pp.614-633, 2004.
[11] I. Sourdis and D. Pnevmatikatos. “Pre-decoded CAMs for efficient and high-speed NIDS pattern matching,” IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM2005), 2005.