目前網路入侵偵測系統大多採用多重樣式字串比對的方式，是否含有網路攻
擊與異常的封包，透過比對數以千計的攻擊特徵來偵測封包內容。隨著大數據時代的來臨，網路速度與攻擊活動的增加，多重樣式字串比對面臨效能與吞吐量的不足，導致許多封包沒有處理且遺失。為了改善網路入侵偵測系統的效能與吞吐量，本論文提出階層式平行架構，利用多張圖形處理(Multi-GPU)與三種不同層面的平行技術加速網路入侵偵測系統。

階層式平行架構由三層不同的平行技術所組成，從上至下來看，第一層實現資料平行(Data Parallelism)於多張圖形處理器；第二層將管線化排程(Pipeline Schedule)實現於個別圖形處理器中，屬於任務平行(Task Parallelism)；第三層則是採用資料平行的技術，優化 Aho-Corasick 演算法。本論文實驗結果顯示，採用四張圖形處理器 Nvidia Titan X 實現於階層式平行架構，總系統吞吐量可高達 70 Gbps，與傳統使用於 Snort 中的 Aho-Corasick 演算法相比，可高達四十倍的改善倍率。當圖形處理器的數量增加，總系統的吞吐量也會隨之增加。除此之外，本論文採用完美雜湊(Perfect Hashing)的方法，壓縮傳統 Aho-Corasick 的狀態機，減少在 Snort 中 99.2%多重樣式字串比對的記憶體使用量，最後本論文將提出的階層式平行架構實現於開源網路入侵偵測系統 Snort。

Multi-string matching has been widely used in NIDS to detect network attacks and malicious network packets by matching packet contents with thousands of attack patterns. Due to the rapid increase of growing network attacks and network speeds, multi-string matching faces the challenges for limited performance and insufficient throughput. In order to improve the performance and throughput of multi-string matching, this thesis presents a novel hierarchical parallelism that can accelerate multi-string matching on multiple GPUs. The hierarchical parallelism consists of three layers of parallelism. From top to bottom, the first layer is the data parallelism on multiple GPUs; The second layer is the task parallelism on a single GPU; The last layer is the data parallelism of the Aho-Corasick algorithm. Experimental results show that the hierarchical parallelism on a machine featured with four Nvidia Titan X GPUs can achieve 70 Gbps of throughput which is 40 times faster than the Aho-Corasick algorithm used in Snort. As the number of GPUs increase, the throughput of the hierarchical parallelism will also increase. In addition, the proposed approach adopts the perfect hashing to construct state machines that can achieve memory reduction on Snort up to 99.2%. Finally, the proposed hierarchical parallelism is implemented in the open source network intrusion detection system using Snort.

[1] M.Roesch. “Snort-lightweight intrusion detection for networks,” In the 13th USENIX Conference on System Administration, 1999.

[2] Alfred V. Aho, Margaret J. Corasick, “Efficient string matching: an aid to bibliographic search,” Communications of the ACM, vol. 18, no.6, pp. 333-340, June 1975.

[3] OSEC:http://osec.neohapsis.com

[4] Abhishek Mitra, Walid Najjar, Laxmi Bhuyan, “Compiling PCRE to FPGA for accelerating SNORT IDS,” Proceedings of the 3rd ACM/IEEE Symposium on Architecture for networking and communications systems, December 03-04, 2007, Orlando, Florida, USA

[5] Z. K. Baker and V. K. Prasanna, “A methodology for synthesis of efficient intrusion detection systems on FPGAs,” Proc. FCCM, 2004.

[6] X. Chen, Y. Wu, L. Xu, Y. Xue, and J. Li., “Para-Snort: A Multithread Snort on Multi-core IA Platform,” In Proceedings of Parallel and Distributed Computing and Systems (PDCS), 2009.

[7] Vasiliadis G, Antonatos S, Polychronakis M, Markatos EP, Ioannidis S, “Gnort: high performance network intrusion detection using graphics processors,” In: 11th international symposium on recent advances in intrusion detection, Boston, MA, USA, 2008, pp. 116-134.

[8] C.-H. Lin, J.C. Li, C.H. Liu, S.C. Chang, “Perfect hashing based parallel algorithms for multiple string matching on graphic processing units,” IEEE Tran. on Parallel Distrib. Syst, Vol. 28, no. 9, Sept. 1, pp. 2639-2650, 2017.

[9] C.-H. Lin, C.-H. Liu, L.S. Chien, S.C. Chang, “Accelerating pattern matching using a novel parallel algorithm on gpus,” IEEE Trans. Comput., vol. 62, no. 10, pp. 1906-1916, 2013.

[10] C.-H. Lin, C.-H. Liu, S.-C. Chang, and W.-K. Hon, “Memory- efficient pattern matching architectures using perfect hashing on graphic processing units,” in Proc. 31st Annu. IEEE Int. Conf. Comput. Commun., 2013, pp.1978-1986.

[11] Knuth, D.E., Morris, J.H., Jr., and Pratt, V.R., “Fast pattern matching in strings,” TR CS74-440, Stanford University, Stanford, California, 1974.

[12] Robert S. Boyer , J. Strother Moore, “A fast string searching algorithm,” Communications of the ACM, vol.20, no. 10, pp. 762-772, Oct. 1977.

[13] S. Wu and U. Manber., “A fast algorithm for multi pattern searching,” Technical Report TR-94-17, 1994.

[14] B. Commentz-Walter., “A string matching algorithm fast on the average,” In Proceedings of the 6th International Colloquium on Automata, Languages and Programming, pp. 118-131.

[15] SCHUFF, D. L., CHOE, Y. R., AND PAI, V. S., “Conservative vs. optimistic parallelization of stateful network intrusion detection,” In Proc. of ACM Symposium on Principles and Practice of Parallel Programming, 2007.

[16] “Supra-linear packet processing performance with intel multi-core processors white paper,” Intel Corporation, 2006.

[17] D. L. Cook, J. Ioannidis, A. D. Keromytis, and J. Luck., “Cryptographics: Secret key cryptography using graphics cards,” In Proceedings of RSA Conference, Cryptographer’s Track (CT-RSA), pp. 334–350, 2005.

[18] N. Jacob and C. Brodley., “Offloading IDS computation to the GPU,” In Proceedings of the 22nd Annual Computer Security Applications Conference on Annual Computer Security Applications Conference, IEEE Computer Society, pp. 371-380, Washington, DC, USA, 2006.

[19] G. G. R. I. Lodovico Marziale and V. Roussev., “Massive threading: Using GPUs to increase the performance of digital forensics tools,” Digital Investigation 1, pp. 73–81, September 2007.

[20] NVIDIA. NVIDIA CUDA Compute Unified Device Architecture Programming Guide, version 1.1. http://developer.download.nvidia.com/compute/cuda/11/NVIDIA CUDA Programming Guide 1.1.pdf.

[21] C. Coit, S. Staniford, and J. McAlerney., “Towards faster string matching for intrusion detection or exceeding the speed of Snort,” In Proceedings of DARPA Information Survivability Conference & Exposition II (DISCEX ’01), June 2001.

[22] V. Paxson., “A system for detecting network intruders in real-time,” In Proceedings of the 7th conference on USENIX Security Symposium (SSYM ’98), USENIX Association., pp. 3-3, Berkeley, CA, USA, 1998.

[23] C. IOS. IPS deployment guide: http://www.cisco.com.

[24] Natttawat Khamphakdee, Nunnapus Benjamas and Saiyan Saiyod, “Improving intrusion detection system based on snort rules for network probe attack detection”, International conference on information and communication technology, IEEE, 2014.

[25] The OpenMP API specification for parallel programming (2016): http://www.openmp.org/