最近幾年，隨著網路流量大幅成長，每天都有大量的病毒和惡意入侵封包散佈於網路。網路入侵偵測系統能藉由比對事先定義好的規則驗證惡意攻擊。以軟體為基礎的網路入侵系統在極短時間內無法處理大量傳輸的封包。因此，用硬體方式實作預防惡意攻擊的網路入侵系統逐漸變成一個重要議題。
在本篇論文中，我們以AC演算法為基礎提出一個有效率的架構。主要的概念是設計一個可在同一時脈處中理多個封包的架構。在提出的架構中，改善原始AC演算法所建立的單一搜尋引擎架構以提高處理產能。相較於原始AC演算法，本論文提出的雙引擎系統其記憶體成本比原始系統增加的17%至44%，處理能力可增加78%到98%。相同比較，提出的八引擎系統需要約兩到四倍的原始AC搜尋引擎的記憶體成本，比原始系統可提升393%至717%的處理能力。模擬結果顯示八引擎的系統中複製四次中間層有最佳的效能。

With the rapid growth of Internet traffic in recent years, a large number of viruses and malicious intrusion packets are spreading in the network every day. Network Intrusion Detection System (NIDS) is able to identify attacks by searching a set of patterns. The main drawback of the software-based NIDSs is that they can not process a large number of arriving packets in a short period of time. Therefore, the issue of the hardware implemented NIDS to prevent the malicious attacks from intruders has become more significant.
In this thesis, we propose an efficient architecture based on AC algorithm. Our main idea is to design an architecture that processes multiple packets per clock cycle. The proposed architecture improves the original AC architecture for single search engine and enhances the processing throughput. Compared to the original AC search engine, our proposed approach only requires more 17% to 44% of the total memory while achieving 78% to 98% higher throughput in two-engine system. Although the proposed 8-engine system needs about double to quadruple memory of the original AC search engine, its throughput can reach 393% to 717% of the throughput achieved by the original AC search engine. The simulation shows that the 8-engine system with four duplicated middle layers has the best performance.

[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]R. S. Boyer and J. S. Moore, “A fast string searching algorithm,” Communications of the ACM, vol. 20, no 10, pp.762-772, Oct. 1977.
[3]”Bro”, http://www.bro-ids.org/
[4]“Clam AntiVirus”, http://www.clamav.net
[5]C. R. Clark and D. E. Schimmel. “Scalable Pattern Matching for High Speed Networks,” In IEEE Symposium on Field-Programmable Custom Computing Machines, (FCCM), Napa, CA, Apr. 2004.
[6]Yeim-Kuan Chang, Ming-Li Tsai and Cheng-Chien Su, “Improved TCAM-based Pre-Filtering for Network Intrusion Detection Systems” In 22th IEEE Advanced Information Networking and Applications, 2008. (AINA ‘08), pp. 985-990.
[7]“DansGuardian”, http://dansguardian.org
[8]S. Dharmapurikar, P. Krishnamurthy, T. S. Sproull and J. W. Lockwood, “Deep Packet Inspection using Parallel Bloom Filters”, IEEE Micro, vol. 24, no. 1, pp. 52-61, Jan. 2004.
[9]D. E. Knuth, J. H. M. Jr., and V. R. Pratt, “Fast pattern matching in strings,” SIAM J. Comput., vol. 6, no. 2, pp. 323–350, June 1977.
[10]R. Nigel Horspool, “Practical fast searching in strings.” Software–Practice & Experience 10–6 (1980) pp.501–506.
[11]Andrew Hume & Daniel Sunday, “Fast string searching.” Software–Practice &Experience 21–11 (1991) pp.1221–1248.
[12]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), pp.227–238, Rohnert Park, CA, UNA, May 2001.
[13]Snort-the de Facto Standard for Intrusion Detection/Prevention, [Online]. Available: www.snort.org
[14]I. Sourdis and D. Pnevmatikatos. “Pre-decoded CAMs for efficient and high-speed NIDS pattern matching.” In IEEE Symposium on Field-Programmable Custom Computing Machines, (FCCM), Napa, CA, Apr. 2004.
[15]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.
[16]L. Tan and T. Sherwood, “A High Throughput String Matching Architecture for Intrusion Detection And Prevention,” in Proc. IEEE ISCA, pp. 112-122, 2005.
[17]Qingbo Wang, Viktor K. Prasanna, “Multi-Core Architecture on FPGA for Large Dictionary String Matching” in 17th IEEE Symposium on Field Programmable Custom Computing Machines , 2009, pp.96-103.
[18]Tian Song, Wei Zhang,Dongsheng Wang, Yibo Xue, “A Memory Efficient Multiple Pattern Matching Architecture for Network Security”. In 27th IEEE Conference on Computer Communications (INFOCOM ‘08), pp. 166-170.