Aho-Corasick 演算法已經被廣泛使用於網路入侵檢測系統（Network Intrusion Detection System，簡稱 NIDS），用來檢查網路封包裡數以千計數的惡意代碼片段。為了提高網路入侵檢測系統的性能，許多基於 Aho-Corasick 衍生出來的演算法使用圖形處理器（GPU）或特殊硬體來加速多字串比對，其中一種方法便是增加每週期處理的字元數來提升多字串比對的速度。然而，增加每週期處理的字元數將會遇到兩個主要問題，第一個問題是輸入對齊問題，第二個問題則是儲存狀態轉換表所需的記憶體空間大幅增加。這兩個問題導致多字元比對的方法變得不太可行。在本文中，我們提出了一種適合在圖形處理器上執行的雙字元平行字串比對演算法。而前述的兩個主要問題，本文提出了一個新形態的狀態機來解決輸入對齊問題，並用完美雜湊壓縮狀態轉換表以解決記憶體空間爆炸問題。實驗結果證明所提出的演算法無論在性能或記憶體空間需求方面均優於目前最先進的方法。

Aho-Corasick algorithm has been widely used in network intrusion detection system to inspect network packets against thousands of attack patterns. To improve the performance of network intrusion detection systems, many variations of Aho-Corasick algorithm are proposed to accelerate multiple string matching on GPUs or dedicated hardware. One of the proposed variations is to increase the number of characters that are processed per cycle. However, increasing the number of characters processed per cycle will encounter two major problems. The first problem is the input alignment problem while the second problem is the large increase of memory required for storing the state transition table. The two problems cause the multi-character approach become less feasible. In this thesis, we propose a novel parallel dual-character string matching algorithm on graphical processing units. In order to solve the two major problems, the proposed algorithm presents a new state machine to solve the input alignment problem, and compresses the state transition table using perfect hashing to solve the memory explosion problem. The experimental results show that the proposed algorithm is superior to the state-of-the-art approaches in terms of performance and memory requirements.

[1] T. AbuHmed, A. Mohaisen, and D. Nyang, “A survey on deep packet inspection for intrusion detection systems,” CoRR, vol. abs/0803.0037, 2008.
[2] A. V. Aho and M. J. Corasick, “Efficient string matching: An aid to bibliographic search,” Commun. ACM, vol. 18, no. 6, pp. 333–340, Jun. 1975.
[3] M. Alicherry, M. Muthuprasanna, and V. Kumar, “High speed pattern matching for network ids/ips,” in Proceedings of the 2006 IEEE International Conference on Network Protocols, Nov 2006, pp. 187–196.
[4] A. Bremler-Barr, D. Hay, and Y. Koral, “CompactDFA: Generic state machine compression for scalable pattern matching,” in 2010 Proceedings IEEE INFOCOM, March 2010, pp. 1–9.
[5] Y. K. Chang, C. R. Chang, and C. C. Su, “The cost effective pre-processing based nfa pattern matching architecture for nids,” in 2010 24th IEEE International Conference on Advanced Information Networking and Applications, April 2010, pp. 385–391.
[6] C.-C. Chen and S.-D. Wang, “An efficient multicharacter transition string-matching engine based on the aho-corasick algorithm,” ACM Trans. Archit. Code Optim., vol. 10, no. 4, pp. 25:1–25:22, Dec. 2013.
[7] “Clang: a C language family frontend for LLVM,” https://clang.llvm.org/, April 2017.
[8] S. Dharmapurikar and J. W. Lockwood, “Fast and scalable pattern matching for network intrusion detection systems,” IEEE Journal on Selected Areas in Communications, vol. 24, no. 10, pp. 1781–1792, Oct 2006.
[9] S. Dharmapurikar and J. Lockwood, “Fast and scalable pattern matching for content filtering,” in Proceedings of the 2005 ACM Symposium on Architecture for Networking and Communications Systems, ser. ANCS ’05. New York, NY, USA: ACM, 2005, pp. 183–192.
[10] N. Hua, H. Song, and T. V. Lakshman, “Variable-stride multi-pattern matching for scalable deep packet inspection,” in IEEE INFOCOM 2009, April 2009, pp. 415–423.
[11] N. F. Huang, H. W. Hung, S. H. Lai, Y. M. Chu, and W. Y. Tsai, “A gpu-based multiple-pattern matching algorithm for network intrusion detection systems,” in 22nd International Conference on Advanced Information Networking and Applications - Workshops (aina workshops 2008), March 2008, pp. 62–67.
[12] W. Jiang, Y. H. E. Yang, and V. K. Prasanna, “Scalable multi-pipeline architecture for high performance multi-pattern string matching,” in 2010 IEEE International Symposium on Parallel Distributed Processing (IPDPS), April 2010, pp. 1–12.
[13] J. Kim and S. i. Choi, “High speed pattern matching for deep packet inspection,” in 2009 9th International Symposium on Communications and Information Technology, Sept 2009, pp. 1310–1315.
[14] C. H. Lin, J. C. Li, C. H. Liu, and S. C. Chang, “Perfect hashing based parallel algorithms for multiple string matching on graphic processing units,” IEEE Transactions on Parallel and Distributed Systems, vol. PP, no. 99, pp. 1–1, 2017.
[15] C. H. Lin, C. H. Liu, L. S. Chien, and S. C. Chang, “Accelerating pattern matching using a novel parallel algorithm on gpus,” IEEE Transactions on Computers, vol. 62, no. 10, pp. 1906–1916, Oct 2013.
[16] NVIDIA, “CUDA Zone,” https://developer.nvidia.com/cuda-zone, Sept 2016.
[17] “OpenCL - The open standard for parallel programming of heterogeneous systems,” https://www.khronos.org/opencl/, 2017.
[18] “The OpenMP API specification for parallel programming,” http://www.openmp.org/, 2016.
[19] T. Song, W. Zhang, D. Wang, and Y. Xue, “A memory efficient multiple pattern matching architecture for network security,” in IEEE INFOCOM 2008 - The 27th Conference on Computer Communications, April 2008.
[20] J. van Lunteren, “High-performance pattern-matching for intrusion detection,” in Proceedings IEEE INFOCOM 2006. 25TH IEEE International Conference on Computer Communications, April 2006, pp. 1–13.
[21] Wikipedia, “Data structure alignment,” https://en.wikipedia.org/wiki/Data_structure_alignment, 2017.
[22] Wikipedia, “PCI Express,” https://en.wikipedia.org/wiki/PCI_Express, 2017.
[23] N. Yamagaki, R. Sidhu, and S. Kamiya, “High-speed regular expression matching engine using multi-character nfa,” in 2008 International Conference on Field Programmable Logic and Applications, Sept 2008, pp. 131–136.