臺灣博碩士論文加值系統

在本篇論文中，我們使用NetFPGA發展平台，以硬體描述語言Verilog
HDL，實現了以速寫演算法為基礎的流量變異偵測之硬體系統。並且詳述硬體系統之FPGA設計與開發流程，我們更討論本系統之關鍵模組，如速寫演算法模組，所需的雜湊函數與記憶體空間之硬體資源與效能間之取捨，來達成高速(4Gbps)即時流量變異偵測之目標。

In this thesis, we implement a sketch-based network traffic
change detection system on NetFPGA.The architecture and FPGA flow
on several key modules are presented in detail. We further
explore the hardware resources with trade-offs to achieve
on-line, wire-speed (4Gbps) network traffic change detection.

1 導論...1
1.1 研究動機...1
1.2 研究目的...3
1.3 論文架構...3
2 現況與相關研究...4
2.1 統計網路資料的方法...4
2.1.1 取樣法 (Sampling)...4
2.1.2 速寫演算法 (Sketch-based)...4
2.1.3 計數器法 (Counter-based)...5
2.2 分析網路流量的方法...5
2.2.1 移動視窗...5
2.2.2 熵(Entropy)...5
2.2.3 主成分分析(PCA)...6
2.3 相關研究...6
3 NetFPGA開發平台...9
3.1 NetFPGA開發原始碼環境架構...8
3.2 如何新增一個模組階層...11
4 硬體系統實現...18
4.1 速寫演算法模組:...19
4.1.1 2-Universal 雜湊函數實現...20
4.1.1.1 以查表法實現...20
4.1.1.2 以內建乘法器方法實現...21
4.1.1.3 2-Universal 雜湊函數探討...21
4.1.2 4-Universal雜湊函數實現...22
4.1.2.1 4-Universal 雜湊函數以查表法實現...22
4.1.2.2 4-Universal雜湊函數以內建乘法器法實現...23
4.1.2.3 4-Universal 雜湊函數探討...24
4.1.3 Sketch記憶體探討...25
4.1.4 速寫演算法模組實現...27
4.1.4.1 以BRAM實現速寫演算法計數器陣列...27
4.1.4.2 以SRAM實現速寫演算法計數器陣列...28
4.2 預測模組...29
4.3 變異偵測模組...30
4.4 硬體細部運作之探討...32
4.4.1 速寫演算法階層結構...33
4.4.2 SRAM資料儲存位置...34
4.4.3 FIFO設計...36
4.4.4 系統驗證與模擬...37
5 測試結果...40
6 結論...42
7 未來展望...43
A 附錄...47







圖像列表

圖 1:. 藉由定義封包流(flow)可以將高維度的網路封包簡化成較低的維度...1
圖 2:. 圖中紅色圓圈為端口掃描攻擊發生的時間點，圖上半部的封包流鍵值以目的端IP位置作定義，可發現攻擊發生時熵值下降。圖下半部是以目的埠定義封包流鍵值，可以發現攻擊發生時熵值下降，擷取自[16]...6
圖 3:. 主成分分析方法，異常的行為通常會在剩餘的成分中顯露出來。擷取自[17]...8
圖 4:. NF2資料夾樹狀結構...9
圖 5:. projcts資料夾樹狀結構...10
圖 6:. 使用者資料路徑(UDP)模組連接圖...11
圖 7:. NetFPGA UDP階層之間資料傳輸是以推進(Push)的傳輸方式...12
圖 8:. 新增暫存器相關程式碼設定...13
圖 9:. 定義暫存器的位置程式碼...14
圖 10:. 設定完暫存器後，詳細位置會再sketch/lib/C/reg_defines_sketch.h自動顯示...15
圖 11:. 模擬集合成之前必須先source shell scripts ...15
圖 12:. 執行ModelSim模擬時的指令...16
圖 13:. ModelSim wave視窗，當軟體暫存器匯流排SKETCH_SW_0寫入'h123時，硬體中的計數器開始執行封包累加，並將計數器接到硬體暫存器SKETCH_HW_0...16
圖 14:. ModelSim Transcript 視窗顯示詳細執行過程...17
圖 15:. 系統架構圖，在NetFPGA中新增一個Sketch階層，來擷取封包流資訊...18
圖 16:. K-ary Sketche更新(update)...19
圖 17:. H3使用一個布林矩陣Q來當作輸出值的索引...20
圖 18:. 以乘法器實現2-Universal hash function...21
圖 19:. 4-Universal以查表法實現雜湊函數演算法計算過程...23
圖 20:. 以乘法器實現4-Universal hash function...24
圖 21:. 乘法器法實現4-Universal Hash function模擬波形圖...25
圖 22:. ，記憶體陣列大小為4K所需BRAM資源...26
圖 23:. 在硬體實現3個Hash function，記憶體陣列為4K，實現Sktch陣列個數消耗BRAM資源圖...27
圖 24:. 以BRAM實現觀測速寫演算法計數器陣列架構圖...28
圖 25:. H=3，不同大小計數器陣列BRAM資源消耗表...28
圖 26:. 以SRAM實現觀測速寫演算法計數器陣列架構圖...29
圖 27:. 預測模組使用移動視窗並計算出誤差速寫演算法計數器陣列...30
圖 28:. 變異偵測模組架構圖...32
圖 29:. 五階層管線架構，將所有SRAM資源分成八等份，實現Output Queue階層...32
圖 30:. 速寫演算法階層內部結構...34
圖 31:. SRAM儲存資料配置圖...35
圖 32:. 暫存器匯流排所對應到SRAM的位置...36
圖 33:. 資料傳輸流程圖...37
圖 34:. 映射空間初始值為:雜湊函數映射位置加上初始值...38
圖 35:. 速寫演算法模擬波形圖...38
圖 36:. 速寫演算法更新(Update)波形圖...39







表格列表

表 1:. 以查表法實現3個2-Universal hash function資源消耗...20
表 2:. 以乘法器實現3個2-Universal hash function資源消耗表...21
表 3:. 2-Universal雜湊函數最大輸出表...22
表 4:. 乘法器及查表法實現2-Universal hash function比較表...22
表 5:. 以查表法實現3個4-Universal 雜湊函數消耗資源表...23
表 6:. 以乘法器實現3個4-Universal hash function消耗資源表...24
表 7:. 乘法器及查表法實現4-Universal hash function比較表...25
表 8:. Reference nic資源消耗表...26
表 9:. 實現H=3 K=4K消耗的資源表...28
表 10:. 暫存器位置與SRAM位置對映表...36
表 11:. 以SRAM實現H=3 K=32K消耗晶片資源表...39

[1] C. Estan, G. Varghese, and M. Fisk. Bitmap algorithms for
counting active flows on high speed links. In Proceedings of the
ACM Internet Measurement Conference, Oct. 2003.

[2] G. Cormode and S. Muthukrishnan, What's new: finding
significant differences in network data streams. In: Proceedings
of IEEE INFOCOM (2004).

[3] Lukasz Golab , M. Tamer Özsu, Issues in data stream
management, ACM SIGMOD Record, v.32 n.2, p.5-14, June 2003.

[4] B. Krishnamurthy, S. Sen, Y. Zhang, and Y. Chen,
“Sketch-Based Change Detection: Methods, Evaluation, and
Applications,” Proc. ACM Internet Measurement Conf., Oct. 2002.

[5] 鄭智記，基於Sketch 演算法之網路流量變異偵測系統之分析與研究，中原大學電機工程研究所，民國96年。

[6] M. Thorup and Y. Zhang. Tabulation based 4-universal hashing
with applications to second moment estimation. In Proc. ACM-SIAM
SODA, Jan. 2004.

[7] Yan Gao , Zhichun Li , Yan Chen, A DoS Resilient Flow-level
Intrusion Detection Approach for High-speed Networks, Proceedings
of the 26th IEEE International Conference on Distributed
Computing Systems, p.39, July 04-07, 2006 .

[8] C. Estan and G. Varghese, "Data streaming in computer
networking," in Proc. Workshop on Management and Processing of
Data Streams (MPDS), San Diego, CA, 2003.

[9] 林俊廷，於NetFPGA實現基於Sketch演算法之網路流量變異偵測系統，中原大學電機工程研究所，民國97年。

[12] http://www.netfpga.org/

[13] Y. Gao, Z. Li, Y. Chen, A dos resilient flow-level intrusion
detection approach for high-speed networks, in: The International
Conference on Distributed Computing Systems, 2006.

[14] G. Cormode and M. Hadjieleftheriou. Finding the frequent
items in streams of data. Communications of the ACM, 52, 2009.

[15] Chandola, V., Banerjee, A., Kumar, V.: Anomaly detection: a
survey. ACM Computing Surveys (2009)

[16] LAKHINA, A., CROVELLA, M., AND DIOT, C. Mining Anomalies
Using Traffic Feature Distributions. ACM SIGCOMM (Philadelphia,
August 2005).

[17] A. Lakhina, M. Crovella, and C. Diot. Diagnosing
Network-Wide Traffic Anomalies. In ACM SIGCOMM, Portland, August
2004.

[18] X. Li, F. Bian, M. Crovella, C. Diot, R. Govindan, G.
Iannaccone, and A. Lakhina. Detection and identification of
network anomalies using sketch subspaces. In IMC, pp. 147–152,
Oct. 2006.

[19] G. Varghese. Network Algorithmics: An Interdisciplinary
Approach to Designing Fast Networked Devices. Morgan Kaufmann
Publishers, Inc., 2004.

[20] Y Hu, DM Chiu and JCS Lui, "Entropy based adaptive flow
aggregation", IEEE/ACM Transactions on Networking, Vol 17 Issue
3, June 2009.

[21] Y. Gu, A. McCallum, and D. Towsley, Detecting anomalies in
network traffic using maximum entropy estimation., in Proc.
Internet Measurement Conference, 2005.

[22]
http://netfpga.org/forums/showthread.php?6-Using-SRAM&highlight=bram