利用圖形處理器與階層式平行技術加速網路入侵偵測系統

A Novel Hierarchical Parallelism for Accelerating NIDS Using GPUs

謝政宏(Hsieh Cheng-Hung)

指導教授 ： 林政宏

國立臺灣師範大學/科技與工程學院/電機工程學系/碩士(2018年)

https://doi.org/10.6345/THE.NTNU.DEE.004.2018.E08

摘要

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

關鍵字

網路入侵偵測系統 ； 多重樣式字串比對 ； 圖形處理器 ； Aho-Corasick 演算法

並列摘要

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.

並列關鍵字

Network intrusion detection systems ； Graphics processing units ； Multiple string matching ； Aho-Corasick algorithm

參考文獻

[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.