簡易檢索 / 詳目顯示

研究生: 謝政宏
Hsieh, Cheng-Hung
論文名稱: 利用圖形處理器與階層式平行技術加速網路入侵偵測系統
A Novel Hierarchical Parallelism for Accelerating NIDS Using GPUs
指導教授: 林政宏
Lin, Cheng-Hung
學位類別: 碩士
Master
系所名稱: 電機工程學系
Department of Electrical Engineering
論文出版年: 2018
畢業學年度: 106
語文別: 中文
論文頁數: 65
中文關鍵詞: 網路入侵偵測系統多重樣式字串比對圖形處理器Aho-Corasick 演算法
英文關鍵詞: Network intrusion detection systems, Graphics processing units, Multiple string matching, Aho-Corasick algorithm
DOI URL: http://doi.org/10.6345/THE.NTNU.DEE.004.2018.E08
論文種類: 學術論文
相關次數: 點閱:145下載:20
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  • 目前網路入侵偵測系統大多採用多重樣式字串比對的方式,是否含有網路攻
    擊與異常的封包,透過比對數以千計的攻擊特徵來偵測封包內容。隨著大數據時代的來臨,網路速度與攻擊活動的增加,多重樣式字串比對面臨效能與吞吐量的不足,導致許多封包沒有處理且遺失。為了改善網路入侵偵測系統的效能與吞吐量,本論文提出階層式平行架構,利用多張圖形處理(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.

    中文摘要 ii 英文摘要 iv 誌謝 vi 目錄 viii 圖目錄 x 表目錄 xiii 第一章 緒論 1 1.1 研究背景與動機 1 1.2 研究目的 2 1.3 研究方法概述 2 1.4 研究貢獻 4 1.5 論文架構 4 第二章 文獻探討 6 2.1 入侵偵測系統 6 2.2 Snort 網路入侵偵測系統 7 2.3 樣式字串比對 10 2.3.1 單一樣式字串比對 10 2.3.2 多重樣式字串比對 15 2.4 Snort 相關研究文獻與討論 17 2.4.1 Supra-linear Packet 18 2.4.2 MultiSnort 20 2.4.3 PixelSnort 21 2.4.4 Gnort 21 第三章 研究方法 25 3.1 多重字串比對演算法的優化 25 3.1.1 Data Parallel Aho-Corasick Algorithm 25 3.2 Snort 處理流程與程式架構 27 3.2.1 Snort 處理流程 27 3.2.2 Snort 程式架構 28 3.3 階層式平行架構 30 3.3.1 緩衝區機制 30 3.3.2 第一層 – 資料平行於多個圖形處理器 32 3.3.3 第二層 – 任務平行於個別圖形處理器 32 3.3.4 第三層 – 資料平行於 Aho-Corasick 33 3.3.5 後處理程序 39 第四章 實驗結果 41 4.1 實驗環境與測試數據 41 4.1.1 實驗環境 41 4.1.2 測試數據 42 4.2 演算法效能分析 45 4.2.1 單執行緒 CPU 與 單圖形處理器 GPU 45 4.3 系統整體效能評估 49 4.3.1 多圖形處理器 Multi-GPU 49 4.3.2 多圖形處理器(Multi-GPU)樣本採計 51 4.4 相關論文之實驗數據分析 57 4.5 實驗結論 57 第五章 結論與未來展望 59 5.1 結論 59 5.2 未來展望 59 參考文獻 61 自傳 64

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

    下載圖示
    QR CODE