臺灣博碩士論文加值系統

隨著高速網路時代的來臨，網路安全的議題日趨重要，網路入侵偵測系統 (Network Intrusion Detection System，簡稱 NIDS) 為了執行深度封包偵測 (deep packet inspection) 需要針對每個封包進行比對，防止有害封包進入，研究文獻指出 Snort 花費大約 31% 的執行時間在執行字串比對，若能改善字串比對速度，便能大幅度加速 NIDS 的效能。傳統的比對演算法大多都只有實作在中央處
理器 (Central Processing Unit，簡稱 CPU) 或者圖形處理器 (Graphic Processing Unit，簡稱 GPU) 上，因此本論文提出利用 CPU 與 GPU協同合作的字串比對演算法，透過 CPU 端的前置過濾，將可能含有有害內容的封包送到 GPU 進行精確比對，達到封包偵測的分工執行。本論文在 Linux 的系統環境下，裝設兩張雙埠 10 GbE 網路卡進行實驗，實驗結果顯示當有害封包比例小於 30% 時，本論文所提出的演算法效能可以達到 AC-CPU 的 5.1 倍、AC-GPU 的 1.6倍。

With the increasing popularity of the Internet, network security is-suesarebecomingmoreandmoreimportant. Networkintrusiondetection
systems (NIDSs) have been developed for greater security by performing
deeppacketinspection. Previousstudieshaveindicatedthatstringmatch-
ing can consume up to 31% of the total execution time of Snort, which
is a well-known open source NIDS. Thus, a fast string matching algo-
rithm is crucial for implementing a high performance NIDS. A number of
string matching algorithms can be found in the literature. Most of them
only involve central processing units (CPUs) or graphic processing units
(GPUs). In this thesis, we propose a CPU/GPU string matching algo-
rithm that distributes the packet-inspecting workload between a CPU and
GPU. We implemented our proposed algorithm in a Linux-based system
with two dual-port 10Gbps Ethernet network interface cards. Test results
indicate that when intrusive packet percentages were less than 30%, the
matching speeds of our proposed algorithm were 5.1 times and 1.6 times
faster than that of the AC-CPU and AC-GPU algorithms, respectively.

目錄
指導教授推薦書 · · · · · · · · · · · · · · · · · · · · · · · ·
口試委員會審定書· · · · · · · · · · · · · · · · · · · · · · ·
中文摘要 · · · · · · · · · · · · · · · · · · · · · · · · · · · iii
英文摘要 · · · · · · · · · · · · · · · · · · · · · · · · · · · iv
目錄 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · v
表目錄· · · · · · · · · · · · · · · · · · · · · · · · · · · · · vii
圖目錄· · · · · · · · · · · · · · · · · · · · · · · · · · · · · viii
1 序論· · · · · · · · · · · · · · · · · · · · · · · · · · · · · 1
1.1 相關背景 . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 研究動機 . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 研究目的 . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 論文架構 . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 相關研究 · · · · · · · · · · · · · · · · · · · · · · · · · · 5
2.1 Aho-Corasick 演算法 . . . . . . . . . . . . . . . . . . . 5
2.2 階層式多字串比對演算法 . . . . . . . . . . . . . . . . 9
2.3 在多核心加速晶片下進行快取集中的平行字串比對
演算法 . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4 CPU 與 GPU 互相合作的字串比對演算法 (CGC) . . . 12
3 協同比對演算法實作 · · · · · · · · · · · · · · · · · · · · 14
3.1 負載平衡 . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.2 封包擷取 . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.3 前置過濾 . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.4 封包複製到 GPU . . . . . . . . . . . . . . . . . . . . 17
3.5 管線化 CPU 與 GPU . . . . . . . . . . . . . . . . . . . 18
4 模擬實驗與結果分析 · · · · · · · · · · · · · · · · · · · · 20
4.1 模擬環境設置 . . . . . . . . . . . . . . . . . . . . . . 20
4.2 前置作業 . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.3 實驗結果與分析 . . . . . . . . . . . . . . . . . . . . . 22
4.3.1 Host 端與 device 端之間資料傳輸速度 . . . . . 22
4.3.2 Double buffering 機制在 GPU 上對效能的影響 22
4.3.3 緩衝區大小對 GPU 的效能影響 . . . . . . . . 23
4.3.4 不同核心數影響 . . . . . . . . . . . . . . . . . 26
4.3.5 不同有害比例影響 . . . . . . . . . . . . . . . 28
5 結論· · · · · · · · · · · · · · · · · · · · · · · · · · · · · 31
參考文獻 · · · · · · · · · · · · · · · · · · · · · · · · · · · 32

表目錄
2.1 字串集合 {he, she, his, hers} 之失誤轉移函式 . . . . . 7
2.2 字串集合 {he, she, his, hers} 的輸出函式 . . . . . . . . 8
4.1 硬體規格表 . . . . . . . . . . . . . . . . . . . . . . . . 20
4.2 字串集合長度分布 . . . . . . . . . . . . . . . . . . . . 21
4.3 Host 與 device 之間資料傳輸速度 (MB/s) . . . . . . . 22
4.4 進入 GPU 比對字元數量 . . . . . . . . . . . . . . . . 29

圖目錄
1.1 NIDS 運作方式 . . . . . . . . . . . . . . . . . . . . . . 2
2.1 字串集合 {he, she, his, hers} 的有限狀態機建構轉移
函式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 字串集合 {he, she, his, hers} 加入失誤轉移函式的有
限狀態機 . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 傳統 GPU 進行 AC 運算 . . . . . . . . . . . . . . . . . 11
2.4 GPU 進行多核心加速晶片下平行計算字串比對快取
集中演算法示意圖 . . . . . . . . . . . . . . . . . . . . 12
3.1 系統架構圖 . . . . . . . . . . . . . . . . . . . . . . . . 15
3.2 在 PF_RING 下使用 DNA [21] . . . . . . . . . . . . . 16
3.3 管線化 CPU 與 GPU . . . . . . . . . . . . . . . . . . . 19
4.1 模擬架構 . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.2 單一 grid 內不同 block 數影響 . . . . . . . . . . . . . 24
4.3 單一 bolck 內不同 thread 數影響 . . . . . . . . . . . . 26
4.4 不同核心數影響 . . . . . . . . . . . . . . . . . . . . . 28
4.5 不同有害比例影響 . . . . . . . . . . . . . . . . . . . . 30

[1] M. Fisk and G. Varghese, “Applying Fast String Matching to In-
trusion Detection,”Tech. R. TR CS2001-0670, University of Cali-
fornia, San Diego, 2002.
[2] J. B. Cabrera, J. Gosar, W. Lee, and R. K. Mehra,“On the Statistical
DistributionofProcessingTimesinNetworkIntrusionDetection,”in
Proc. IEEE Conference on Decision and Control, vol. 1, pp. 75-80,
2004.
[3] M.Roesch,“Snort–LightweightIntrusionDetectionforNetworks,”
in Proc. the 13 th Systems Administration Conference, pp. 229-238,
1999.
[4] T. Sato and M. Fukase,“Reconfigurable Hardware Implementation
of Host-base IDS,”in Proc. the 13 th Systems Administration Con-
ference, pp. 849-853, 2003.
[5] A.V.AhoandM.J.Corasick,“EfficientStringMatching: AnAidto
Bibliographic Search,”Commun. ACM, vol. 18, no6, pp. 333-340,
1975.
[6] V. Chandola, A. Banerjee, and V. Kumar, “Anomaly Detection: A
Survey,”ACM Computing Surveys, 2009.
[7] D. L. Schff, Y.R. Choe, and V. S. Pai ,“Conservative vs. Optimistic
Parallelization of Stateful Network Intrusion Detection in Commod-
ity Hardware,”in Proc. the 12 th ACM SIGPLAN Symposium on
Principles and Practice of Parallel Programming, 2007.
[8] M.Vallentin, R.Sommer,JLee, C.Leres, V.Paxson, andB.Tierney,
“The NIDS C: Scalable, Stateful Network Intrusion Detection on
Commodity Hardware,”in Proc. the 10 th International Symposium
on Recent Advance in Intrusion Detection, 2007.
[9] G. Vasiliadis, M. Polychronakis, and S. Ioannidis, “MIDeA: A
Multi-Parallel Intrusion Detection Architecture,”in Proc. the 18 th
ACM Conference on Computer and Communication Security(CCS),
pp.297-308, 2011.
[10] N.P.Tran,M.Lee,andD.H.Choi, “CacheLocality-CentricParallel
String Matching on Many-Core Accelerator Chips,”Sci. Program.
2015, pp.1-20, 2015.
[11] N. Cascarano, P.Rolandio, F. Risso, and R. Sisto, “iNF Ant: NFA
Pattern Matching on GPGPU Device,”in Proc. the ACM SIG-
COMM, pp. 21-26, 2010.
[12] G.Vasiliadis, S.Antonatos, M.Polychronakis, E.P.Markatos, andS.
Iasnnidis,“Gnort: High Performance Network Intrusion Detection
UsingGraphicsProcessors,”in Proc.11thInternationalSymposium
on Recent Advances in Intrusion Detection (RAID), 2008.
[13] C. Wu, J. Yin, Z.Cai, E. Zhu, and J. Chen,“A Hybrid Parallel Sig-
nature Matching Model for Network Security Applications Using
SIMD GPU,”in Proc. the 8th APPT, pp.192-204, 2009.
[14] Z. K. Baker and V. K. Prasanna, “Time and Area Efficient Pattern
Matching on FPGAs,”in Proc. 12th ACM/SIGDA International
Symposium on Field Programmable Gate Arrays, 2004.
[15] J. H. Knuth, J. H. Morris, V. R. Pratt, “Fast Pattern Matching in
Strings,”SIAM J. Comput., vol. 6, no. 2, pp.127–146, 1977.
[16] R. S. Boyer, J. S. Moore, “A Fast String Searching Algorithm,”
Commun. ACM, vol. 20, no. 10, pp.762–772, 1977.
[17] S. Wu, U. Manber,“A Fast Algorithm for Multi-pattern Searching,”
Tech. R. TR-94-17, Department of Computer Science, University of
Arizona, 1994.
[18] T. F. Sheua , N. F. Huang and H.P. Lee,“Hierarchical Multi-pattern
Matching Algorithm for Network Content Inspection,”Information
Sciences, pp. 2880-2898, 2008.
[19] Microsoft Corporation,“Scalable Networking: Eliminating the Re-
ceive Processing Bottleneck - Introducing RSS,”2005.
[20] Receive side scaling on Intel Network Adapters. [Online]. Avail-
able:http://www.intel.com/support/network/adapter/pro100/sb/cs-
027574.htm
[21] L. Deri., “Improving Passive Packet Capture: Beyond Device
Polling,”in Proc. 4 th International System Administration and Net-
work Engineering Conference (SANE), 2004.
[22] S. Han, K. Jang, K. Park and S. Moon, “PacketShader: a GPU-
Accelerated Software Router,”in Proc. ACM SIGCOMM, 2010.
[23] Snort2923. [Online]. Available:https://www.snort.org/downloads/
archive/snort/snort-2.9.2.3.tar.gz