現在人的生活愈來愈離不開網路，然而網路上電腦病毒猖獗，網路入侵偵測系統顯得愈來愈重要。網路入侵偵測系統是藉由字串比對，辨識出已知的惡意攻擊字串，來防止惡意程式的入侵。隨著網路速度和病毒數量的快速增加，傳統上單純使用軟體的作法，已經無法滿足高速網路的需求，所以有很多的硬體架構被提出來加速，主要分成邏輯基礎架構和記憶體基礎架構兩大類。
近年來記憶體基礎架構受到大家的矚目，基於容易更新病毒碼、容易擴增和成本較低廉的特性，使用記憶體為基礎的字串比對硬體架構，被廣泛的使用在網路入侵偵測系統上。隨著病毒數目的快速增加記憶體的使用量也隨之愈來愈大，而效率、成本、電源消耗，都和記憶體的大小有關。因此，一個成功的網路入侵偵測系統，必須有一個有效率使用記憶體的字串比對演算法和對應的硬體設計。
這篇論文裡我們提出一個有效率使用記憶體的字串比對演算法，藉由我們的演算法，可以降低在記憶體架構下，記憶體的使用量。針對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.

List of Contents:
Abstract i
Contents ii
List of Figures iii
List of Tables iv
Chapter 1 Introduction 1
Chapter 2 Review of the Aho-Corasick Algorithm 6
Chapter 3 Basic Idea 9
Chapter 4 State Traversal Mechanism on a merg_FSM 12
Chapter 5 Construction of the State Traversal Machine 19
Chapter 6 Experimental Results 25
Chapter 7 Conclusions 28
References 29

List of Figures:
Figure 1 (a): DFA for matching “bcdf” and “pcdg” 3
Figure 1 (b): Next state and output vector are stored in memory 4
Figure 2: State diagram of an Aho-Corasick machine 7
Figure 3: Aho-Corasick state table 8
Figure 4: Merging non-equivalent states 10
Figure 5: The architecture of the state traversal 11
Figure 6: New State diagram of merg_FSM 15
Figure 7: Stare transitions of the input string 17
Figure 8: State traversal pattern matching algorithm 18
Figure 9: Construction of pathVec and ifFinal 22
Figure 10: State diagram of the state traversal 24

List of Tables:
Table 1: Experimental results of the AC algorithm and our algorithm 27
Table 2: Experimental results of the bit-split algorithm and our algorithm 27

References
[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.
[2]. R. Franklin, D. Carver, and B.L. Hutchings. Assisting Network Intrusion Detection with Reconfigurable Hardware. In Proceedings of IEEE FCCM 2002, pp. 111-120, Apr. 2002.M. Anis, S. Areibi, and M. Elmasry, “Dynamic and Leakage Power Reduction in MTCMOS Circuits using an Automated Efficient Gate Clustering Technique,” Proc. of DAC, pp. 480–485, 2002.
[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.
[6]. Young H. Cho and William H. Mangione-Smith, A Pattern Matching Co-processor for Network Security. In 42nd IEEE/ACM Design Automation Conference, Anaheim, CA, June 13-17, 2005.
[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.
[8]. S. Dharmapurikar and J. Lockwood. Fast and Scalable Pattern Matching for Content Filtering. In Proceedings of Symposium on Architectures for Networking and. Communications Systems (ANCS), Oct 2005.C. Long and L. He, “Distributed Sleep Transistor Network for Power Reduction,” IEEE Transactions on VLSI systems, vol. 12, no. 9, Sep. 2004.
[9]. L. Tan and T. Sherwood. A high throughput string matching architecture for intrusion detection and prevention. In ISCA'05: 32nd Annual International Symposium on Computer Architecture, pp. 112-122, 2005.S. Pant, and D. Blaauw, “Static timing analysis considering power supply variations,” Proc. of ICCAD, 2005.
[10]. H. J. Jung, Z. K. Baker, and V. K. Prasanna. Performance of FPGA Implementation of Bit-split Architecture for Intrusion Detection Systems. In IPDPS 2006: 20th International Parallel and Distributed Processing Symposium, 2006.
[11]. M. Roesch. Snort- lightweight Intrusion Detection for networks. In Proceedings of LISA99, the 15th Systems Administration Conference, 1999.