近年來，越來越多的攻擊和病毒已在網路上傳播。因此，我們需要一個可靠的深度封包檢測（Deep Packet Inspection, DPI）的機制，以保護我們的電腦免受蠕蟲和病毒在網路上攻擊。然而，擁有一個有效率的樣式比對演算法在深度封包檢測上扮演著重要的角色。非確定性有限狀態自動機（Non-deterministic Finite Automata, NFA）是一個著名的理論，它就是被廣泛應用在現有的樣式比對演算法中。雖然多字元NFA是能夠匹配多個字元在每一次的字元輸入上，並達到更高的速度。但它的缺點是需要複製單一字元NFA架構的電路才能達到多字元架構。
在這篇論文中，我們提出一種基於前處理且低成本的NFA的架構，此架構同樣能夠支援多字元架構。而我們所提出的前處理基礎架構可以減少複製原來單字元NFA的架構。我們將所提出的設計實作在Virtex5 XC5VLX110T FPGA晶片上。而所使用的病毒規則表是取自於Snort和ClamAV這兩種開放式源碼的軟體。根據我們模擬實作的結果， 我們所提出的架構能表現出比傳統暴力法以及相關的方法有更高的速度以及更小的資源使用量。在我們所模擬的兩字元、四字元以及八字元架構中，其空間使用密度分別能達到每slice支援2.86，2.10和0.24字元。而在速度上分別能達到4.6，7.2和12 Gbps。平均而言，我們的架構與沒有前處理架構相比，能有效的降低41％的晶片面積成本(chip area cost)。

In recent years, more and more attacks and viruses have spread on the Internet. Thus, we need a reliable Deep packet inspection (DPI) system to protect our computers from being attacked by worms and viruses on the Internet. An efficient pattern matching algorithm plays an important role in DPI. Non-deterministic Finite state Automata (NFA) is a well-known theory that is widely used in the existing pattern matching algorithms. Although the multi-character NFA is capable of matching multiple characters per cycle and achieves higher throughput, it needs to duplicate the circuits of 1-character architecture.
In this thesis, a low cost NFA architecture based on pre-processing is proposed to process multiple characters per clock cycle. The proposed pre-processing based architecture can reduce the duplication of 1-character NFA needed in the original multi-character NFA architecture. Our design is implemented on the chip of Vertex-5 XC5VLX110T from FPGA family and simulated by using real-life pattern sets from the open source softwares, Snort and ClamAV. The simulation results show that the proposed architecture performs better than all the existing Brute-Force based approaches in terms of throughput and slice utilization. Specifically, the proposed architectures of 2-character, 4-character, and 8-character designs can achieve the throughputs of 4.6, 7.2, and 12 Gbps and the slice utilization of 2.86, 2.10, and 0.24 in terms of char/slice, respectively. In average, the chip area cost can be reduced by 41% compared with the multi-character NFA architechture without pre-processing.

[1] V. Aho and M. J. Corasick, “Efficient string matching: An aid to bibliography search,” Comm. Of the ACM, vol 18, no.6, pp.333-340, 1975.
[2] V. Aho and R.Sethi, and J.D.Uilman, Compilers – Principles Techniques and Tools. Reading , MA, USA:Addison-Wesley, 1986.
[3] M. Aldwairi, T. Conte, and P. Franzon. “Configurable string matching hardware for speeding up intrusion detection,” SIGARCH Comput. Archit. News, 33(1):99.107, 2005.
[4] C. Brodie, D. E. Taylor, and R. K. Cytron, “A Scalable Architecture For High-Throughput Regular-Expression Pattern Matching,” In Proceedings of the 33nd Annual International Symposium on Computer Architecture (ISCA’06), pp. 191–202, 2006.
[5] 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.
[6] Anat Bremler-Barr, David Hay, and Yaron Koral, “CompactDFA: Generic State Machine Compression for Scalable Pattern Matching,” In Proceedings of the 29th IEEE International Conference on Computer Communications (INFOCOM ‘10), pp. 1-9, 2010.
[7] Clam Anti-Virus signature database, www.clamav.net.
[8] C.R. Clark and D.E. Schimmel, “Scalable pattern matching for high speed networks," In Proceedings of the 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines(FCCM '04), pp. 249-257, 2004.
[9] Yeim-Kuan Chang, Ming-Li Tsai, and Yu-Ru Chung , “Multi-Character Processor Array for Pattern Matching in Network Intrusion Detection System,” In Proceedings of the 22th IEEE International Conference on Advanced Information Networking and Applications (AINA’08), pp. 991-996, 2008.
[10] Young H. Cho and W.H. Mangione-Smith, “Deep packet filter with dedicated logic and read only memories,” In Proceedings of the 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM '04), pp. 125-134, 2004.
[11] 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.
[12] B. L. Hutchings, R. Franklin, and D. Carver, “Assisting network intrusion detection with reconfigurable hardware,” In Proceedings of the 10th Annual IEEE Symposium on Field-Programmable Custom Computer (FCCM’02), pp. 111–120, 2002.
[13] Wen-Jyi Hwang, Huang-Chun Roan, and Ying-Nan Shih, Chia-Tien Dan Lo and Chien-Min Ou “FPGA-based ROM-free network intrusion detection using shift-OR circuit,” In Proceedings of Journal of Embedded Computing, vol. 3, pp. 99-107, 2009.
[14] Baker, Z. K. and Prasanna, V. K. “A methodology for synthesis of efficient intrusion detection systems on FPGAs”. In IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM '04), pp. 135-144, 2004.
[15] Cheng-Hung Lin, Chih-Tsun Huang, Chang-Ping Jiang, and Shih-Chieh Chang, “Optimization of Pattern Matching Circuits for Regular Expression on FPGA," IEEE Transactions On Very Large Scale Integration Systems (VLSI’07), vol. 15, no. 12, pp. 1303-1310, 2007.
[16] R. Sidhu and V. K. Prasanna, “Fast Regular Expression Matching Using FPGAs,“ In Proceedings of the 9th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM’01), pp. 227-238, 2001.
[17] Snort: The Open Source Network Intrusion Detection System, www.snort.org.
[18] I. Sourdis and D. Pnevsmatikatos, "Fast, Large-Scale String Match for a 10 Gbps FPGA-based Network Intrusion Detection System, "In Proceedings of the 13th International Conference on Field Programmable Logic and Applications (FPL’03), pp. 880-889, 2003.
[19] Lin Tan and Timothy Sherwood, “Architecture For Bit-Split String Scanning in Intrusion Detection,” IEEE MIRCO, pp. 110-117, 2006.
[20] Lin Tan and Timothy Sherwood, “A High Throughput String Matching Architecture for Intrusion detection and Prevention,” In Proceedings of the 32nd Annual International Symposium on Computer Architecture (ISCA’05), pp. 112-122, 2005.
[21] Yi-Hua E. Yang, Weirong Jiang, and Viktor K. Prasanna, “Compact Architecture for High-Throughput Regular Expression Matching on FPGA,” in proceedings of the 4th ACM/IEEE symposium On Architecture For Networking And Communications Systems (ANCS’08), pp.30-39, 2008.
[22] Norio Yamagaki, Reetinder Sidhu, and Satoshi Kamiya, “High-Speed Regular Expression Matching Engine Using Multi-Character NFA,” In Proceedings of the International Conference on Field Programmable Logic and Applications (FPL ‘08), pp. 697-701, 2008.
[23] F. Yu, R. H. Katz, and T. V. Lakshman, “Gigabit Rate Packet Pattern-Matching Using TCAM,” in Proceeding of 12th IEEE International Conference on Network Protocols (ICNP’04), pp. 174-183, 2004.
[24] Xilinx Virtex-5 Plarform FPGAs: Detailed description. http://www.xilinx.com/support/documentation/virtex-5.htm.