在近幾年內，隨著網路流量快速的增加，以深度封包檢測系統 (Deep packet inspection, DPI) 來確保資訊安全的需求變得越來越重要。深度封包檢測系統依靠著字串比對來檢測封包的內容，來尋找封包內可能的威脅。所以字串比對的效能就是深度封包檢測系統的一個關鍵點。我們必須去找出一個能有穩定效能且低記憶體需求的演算法，去改進字串比對的效能。為了使知名的Aho-Corasick (AC) 演算法能運行在管線化架構上，我們將字串切割成許多子字串，避免產生過多線程且能同時在輸入流中同時運行。在這篇論文中，我們提出一個能在字串集合中尋找出所有共同子字串的方法並且利用這些共同子字串去切割原本的字串。在切割字串集合後，我們用這些得到的子字串去建立AC-DFA，且因為是運行在管線化架構上， 此AC-DFA中所有的failure transition可被移除。之後為了將這些子字串再次組合成原本的字串，我們使用了一個樹狀的資料結構將AC-DFA的結果再次結合成原本尚未切割的字串。在最後，我們利用這兩個資料結構的transition表格建立我們的管線化架構。我們的實驗結果顯示，在子字串分組值K為5，處理約58,000字元的時候，我們利用了Xilinx Virtex-7 XC7V2000T上約5.9%的Block RAM、0.2%的Slice Registers以及16%的Slice LUTs。在記憶體消耗量上比Split AC及Bit-Split分別少了29%及75%。

In recent years, due to the rapid growth of network traffic, the demand of deep packet inspection (DPI) system to ensure the network security is becoming more and more important. The DPI systems rely on pattern matching to detect the payload of the packet, in order to find possible threats in the packet. Therefore, the performance of pattern matching is the key point of the DPI systems. We have to figure out a solution that provides stable throughput and has low memory requirement to improve the performance of pattern matching. In order to let the well-known Aho-Corasick (AC) algorithm work on the pipeline architecture, we segment the patterns into pattern segments for decreasing the number of threads that tracks the input stream. In this thesis, we propose a technique to find out all the common subpatterns in the pattern set and use them to divide the patterns. After dividing the patterns, we use the pattern segments to build up the AC-DFA that eliminates all the failure transitions that are not needed in the pipeline architecture. In addition, we have to combine the subpatterns into their original pattern. Here, a tree-like structure is used for AC-DFA without failure transitions to find the original patterns. Finally, we use the transition tables of these two structures to construct the pipeline architecture. Our implementation result shows that on Xilinx Virtex-7 XC7V2000T, when group threshold K = 5, which handles 58k characters, we utilize 5.9% of Block RAM, 0.2% of Slice Registers, and 16% of Slice LUTs. The memory cost of our scheme is lower than Split AC and Bit-split by 29% and 75%.

[1] Snort: Open source network IDS/IPS, “http://www.snort.org”
[2] Alfred V. Aho and Margaret J. Corasick, “Efficient string Matching: An aid to bibliographic search,” Commun. ACM, vol. 18, no 6, pp. 333-340, 1975.
[3] Wei Lin and Bin Liu, “Pipelined Parallel AC-based Approach for Multi-String Matching,” Parallel and Distributed Systems, 2008. ICPADS '08. 14th IEEE International Conference on, vol., no., pp.665-672, 8-10 Dec. 2008.
[4] Weirong Jiang, Yi-Hua E. Yang, and Viktor K. Prasanna, “Scalable Multi-Pipeline Architecture for High Performance Multipattern String Matching,” Parallel & Distributed Processing (IPDPS), 2010 IEEE International Symposium on, vol., no., pp.1-12, 19-23 April 2010.
[5] S. Antonatos, K. G. Anagnostakis, and E. P. Markatos, “Generating realistic workloads for network intrusion detection systems,” SIGSOFT Softw. Eng. Notes, vol. 29, no. 1, pp. 207-215, 2004.
[6] J. van Lunteren, “High-performance pattern-matching for intrusion detection,” INFOCOM 2006. 25th IEEE International Conference on Computer Communications. Proceedings, pp.1-13, April 2006.
[7] P.-C. Lin, Y.-D. Lin, T.-H. Lee, and Y.-C. Lai, “Using string matching for deep packet inspection,” Computer, vol. 41, no. 4, pp.23-28, April 2008.
[8] Scarpazza, D.P., Villa, O., and Petrini, F., "High-speed string searching against large dictionaries on the Cell/B.E. Processor," Parallel and Distributed Processing, 2008. IPDPS 2008. IEEE International Symposium on, pp.1-12, April 2008.
[9] Villa, O., Chavarria-Miranda, D., and Maschhoff, K., "Input-independent, scalable and fast string matching on the Cray XMT," Parallel & Distributed Processing, 2009. IPDPS 2009. IEEE International Symposium on, pp.1,12, 23-29 May 2009
[10] Cheng-Hung Lin, Sheng-Yu Tsai, Chen-Hsiung Liu, Shih-Chieh Chang, and Shyu, J.-M., "Accelerating String Matching Using Multi-Threaded Algorithm on GPU," Global Telecommunications Conference (GLOBECOM 2010), 2010 IEEE, pp.1-5, ec. 2010.
[11] Jung-Sik Sung, Seok-Min Kang, Youngseok Lee, Taeck-Geun Kwon, and Bong-Tae Kim, "A multi-gigabit rate deep packet inspection algorithm using TCAM," Global Telecommunications Conference, 2005. GLOBECOM '05. IEEE, vol.1, pp.5, Dec. 2005.
[12] Fang Yu, Katz, R.H., and Lakshman, T. V., "Gigabit rate packet pattern-matching using TCAM," Network Protocols, 2004. ICNP 2004. Proceedings of the 12th IEEE International Conference on, vol., no., pp.174-183, Oct. 2004.
[13] Weinsberg, Y., Tzur-David, S., Dolev, D., and Anker, T., "High performance string matching algorithm for a network intrusion prevention system (NIPS),"High Performance Switching and Routing, 2006 Workshop on, pp.7.
[14] Tian Song, Wei Zhang, Dongsheng Wang, and Yibo Xue, "A Memory Efficient Multiple Pattern Matching Architecture for Network Security," INFOCOM 2008. The 27th Conference on Computer Communications. IEEE, April 2008.
[15] Van Lunteren, J., "High-Performance Pattern-Matching for Intrusion Detection," INFOCOM 2006. 25th IEEE International Conference on Computer Communications. Proceedings, pp.1-13, April 2006.
[16] Attig, M.; Sarang Dharmapurikar; Lockwood, J., "Implementation results of bloom filters for string matching," Field-Programmable Custom Computing Machines, 2004. FCCM 2004. 12th Annual IEEE Symposium on, pp.322-323, April 2004.
[17] Lin Tan, Sherwood, T., "A high throughput string matching architecture for intrusion detection and prevention," Computer Architecture, 2005. ISCA '05. Proceedings. 32nd International Symposium on, pp.112-122, June 2005.
[18] Piyachon, P., Yan Luo, "Efficient memory utilization on network processors for deep packet inspection," Architecture for Networking and Communications systems, 2006. ANCS 2006. ACM/IEEE Symposium on, pp.71-80, Dec. 2006.
[19] Van Lunteren, J., "Searching very large routing tables in wide embedded memory," Global Telecommunications Conference, 2001. GLOBECOM '01. IEEE, vol.3, pp.1615-1619, 2001.
[20] Dimopoulos, V., Papaefstathiou, I., and Pnevmatikatos, D., "A Memory-Efficient Reconfigurable Aho-Corasick FSM Implementation for Intrusion Detection Systems," Embedded Computer Systems: Architectures, Modeling and Simulation, 2007. IC-SAMOS 2007. International Conference on, pp.186-193, July 2007.
[21] Clam AntiVirus, “http://www.clamav.net”
[22] Yang, Y.-H.E. and Prasanna, V.K., "Robust and Scalable String Pattern Matching for Deep Packet Inspection on Multicore Processors," Parallel and Distributed Systems, IEEE Transactions on, vol.24, no.11, pp.2283-2292, Nov. 2013.
[23] Bremler-Barr, A, Hay, D., and Koral, Y., "CompactDFA: Scalable Pattern Matching Using Longest Prefix Match Solutions," Networking, IEEE/ACM Transactions on, vol.22, no.2, pp.415-428, April 2014.
[24] Hoang Le and Prasanna, V.K., "A Memory-Efficient and Modular Approach for Large-Scale String Pattern Matching," Computers, IEEE Transactions on, vol.62, no.5, pp.844-857, May 2013.