最佳化字串比對演算法設計針對記憶體架構病毒偵測系統

Optimization of Pattern Matching Algorithm for Memory Based Architecture

戴鈺唐(Yu-Tang Tai)

指導教授 ： 張世杰

國立清華大學/電機資訊學院/資訊工程學系/碩士(2007年)

https://doi.org/10.6843/NTHU.2007.00105

摘要

現在人的生活愈來愈離不開網路，然而網路上電腦病毒猖獗，網路入侵偵測系統顯得愈來愈重要。網路入侵偵測系統是藉由字串比對，辨識出已知的惡意攻擊字串，來防止惡意程式的入侵。隨著網路速度和病毒數量的快速增加，傳統上單純使用軟體的作法，已經無法滿足高速網路的需求，所以有很多的硬體架構被提出來加速，主要分成邏輯基礎架構和記憶體基礎架構兩大類。
近年來記憶體基礎架構受到大家的矚目，基於容易更新病毒碼、容易擴增和成本較低廉的特性，使用記憶體為基礎的字串比對硬體架構，被廣泛的使用在網路入侵偵測系統上。隨著病毒數目的快速增加記憶體的使用量也隨之愈來愈大，而效率、成本、電源消耗，都和記憶體的大小有關。因此，一個成功的網路入侵偵測系統，必須有一個有效率使用記憶體的字串比對演算法和對應的硬體設計。
這篇論文裡我們提出一個有效率使用記憶體的字串比對演算法，藉由我們的演算法，可以降低在記憶體架構下，記憶體的使用量。針對Snort rule set，新的演算法和傳統Aho-Corasick演算法[5]相比，可以降低29% 的記憶體使用量。因為我們採用和其他方法完全不同的觀點，所以我們的方法可以用在其他方法上。例如將我們的方法用在目前效果最好的演算法，bit-split演算法[9]上，仍然可以減少22% 的記憶體使用量。

關鍵字

字串比對 ； 網路入侵偵測系統

並列摘要

Due to the advantages of easy re-configurability and scalability, the memory-based string matching architecture is widely adopted by network intrusion detection systems (NIDS). In order to accommodate the increasing number of attack patterns and meet the throughput requirement of networks, a successful NIDS system must have a memory-efficient pattern-matching algorithm and hardware design. In this paper, we propose a memory-efficient pattern-matching algorithm which can significantly reduce the memory requirement. For total Snort string patterns, the new algorithm achieves 29% of memory reduction compared with the traditional Aho-Corasick algorithm [5]. Moreover, since our approach adopts views totally different from other memory reduction approaches, we can obtain substantial gain even after applying the existing state-of-the-art algorithms. For example, after applying the bit-split algorithm [9], we can still gain an additional 22% of memory reduction.

並列關鍵字

pattern matching ； network intrusion detection system

參考文獻

[1]. R. Sidhu and V. K. Prasanna. Fast regular expression matching using FPGAs. In Proc. of the 9th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM '01), pp. 227-238, 2001.

[3]. J. Moscola, J. Lockwood, R. P. Loui and M. Pachos. Implementation of a Content-Scanning Module for an Internet Firewall. In Proc. of the 11th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM’03), Apr. 2003.

[4]. C. R. Clark and D. E. Schimmel. “Scalable Parallel Pattern Matching on High Speed Networks,” in Proceedings of the Twelfth Annual IEEE Symposium on Field Programmable Custom Computing Machines 2004 (FCCM '04), 2004.

[5]. A. V. Aho and M. J. Corasick. Efficient String Matching: An Aid to Bibliographic Search. In Communications of the ACM, 18(6):333–340, 1975.

[7]. M. Aldwairi*, T. Conte, and P. Franzon. Configurable String Matching Hardware for Speeding up Intrusion Detection. In ACM SIGARCH Computer Architecture News, 33(1):99–107, 2005.