隨著網路的快速發展，越來越多的病毒及惡意攻擊散布在網路上，我們最常使用入侵偵測系統來偵測這些惡意攻擊以及病毒來幫助我們保護我們的系統，字串比對對於入侵偵測系統是很重要的一環，我們需要利用字串比對的演算法來有效率的找到潛伏在封包裡的惡意資訊，為了應付現在的網路速度，軟體的字串比對演算法可能無法在短時間有效且確實的處理完大量的封包，硬體架構的字串比對架構漸漸被需要，在我們的論文裡，我們提供了一個有效率的字串比對架構，而且在硬體的耗費上可以比多字元的可規畫陣列這個架構還節省，而且效能也可以達到5Gbps，我們的架構的主要想法是當字串比對要先命中字串的開頭，我們才去載入字串的尾端來比較，我們用同一塊硬體來處理整個尾端字元，反觀多字元可規畫陣列這個架構，它需要使用數個處理單元才能完成整個尾端字元，因此當字串長度越長，我們的架構相對於多字元可規畫陣列來說硬體資源的消耗就更少，而且我們的架構的處理速度亦是可接受的。

With the growth of internet, more and more attacks and viruses spread in the net, we usually use NIDS system to detect those attacks or viruses and help us to protect our system. Pattern match algorithm play an important role for NIDS system, we need to use pattern match algorithm to found those attacks and virus hidden in the payload of packets efficiently, in order to suit the internet speed, software-based algorithm may not process so many packets in short time, hardware-based architecture is needed, in our thesis, we proposed an efficiency pattern match architecture which can use less area cost then multi-character processor array architecture, and also have 5Gbps throughput, the main idea is when prefix of pattern matched, we load suffix characters to continue following comparisons, we use the same hardware to process suffix. But suffix in multi-character processor array may need several PE according to suffix length, as pattern length increase, our architecture can use hardware resource than multi-character processor array, and keep acceptable processing speed.

[1] A. Aho and M. Corasick, “Efficient string matching: An aid to bibliographic search,” Communications of the ACM, vol. 18, no. 6, pp.333-343, June 1975.
[2] M. Aldwairi, T. Conte, and P. Franzon. “Configurable string matching hardware for speeding up intrusion detection,” NIGARCH Comput. Archit. News, 33(1):99.107, 2005.
[3] R. N. Boyer and J. N. Moore, “A fast string searching algorithm,” Communications of the ACM, vol. 20, no 10, pp.762-772, Oct. 1977.
[4] Young H. Cho, W.H. Mangione-Nmith, “Deep packet filter with dedicated logic and read only memories,” in Proceedings of the 12th IEEE Nymposium of Field-Programmable Custom Computing Machines, 2004.
[5] N. Dharmapurikar, P. Krishnamurthy, T. N. Nproull and J. W. Lockwood, “Deep Packet Inspection using Parallel Bloom Filters”, IEEE Micro, vol. 24, no. 1, pp. 52-61, Jan. 2004.
[6] R. Nidhu and V. K. Prasanna, “Fast Regular Expression Matching Using FPGAs,“ In Proceedings of the 9th Annual IEEE Nymposium on Field-Programmable Custom Computing Machines (FCCM’01), pages 227–238, Rohnert Park, CA, UNA, May 2001.
[7] Nnort-the de Facto Ntandard for Intrusion Detection/Prevention, [Online]. Available: www.snort.org
[8] I. Nourdis and D. Pnevmatikatos. “Pre-decoded CAMs for efficient and high-speed NIDS pattern matching.” In IEEE Nymposium on Field-Programmable Custom Computing Machines, (FCCM), Napa, CA, Apr. 2004.
[9] L. Tan and T. Nherwood, “A high throughput string matching architecture for intrusion detection and prevention,” in INCA, 2005.
[10] F. Yu, R. H. Katz, T. V. Lakshman, “Gigabit Rate Packet Pattern-Matching Using TCAM,” in Proceeding of 12th IEEE International Conference on Network Protocols (ICNP’04), Berlin, Germany, Oct. 2004, pp. 174-183.