在NetFPGA上使用多階管線化布隆過濾器高效比對字串

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：18

、訪客IP：18.191.189.85

姓名

朱君平(Jun-ping Zhu) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

在NetFPGA上使用多階管線化布隆過濾器高效比對字串
(Analysis of Effective Pattern Matching Using Pipelined Bloom Filter Based on NetFPGA)

相關論文

★ 整合多樣配置組態下的藍芽射頻驗證系統	★ 具檔案敘述相關語查詢之智慧型檔案搜尋系統
★ 具遲到者支援功能之網際網路簡報系統	★ 以快速廣播法建構熱門視訊隨選服務伺服器
★ 具事件同步再現特性之遠程電傳展示伺服器	★ 無線網路環境下之廣播資訊快速下載
★ 中文網站繁簡互訪協助系統	★ 支援時光平移播放之調適性現場直播演算法
★ 用於互動式廣播之段落對齊法	★ 熱門影片廣播法之影片區段復原機制
★ 配合熱門影片廣播的本地伺服器高效快取法	★ 一個增進SIP在防火牆環境中應用的協同模組
★ 考量網頁熱門度之一致性雜湊法解決網頁代理伺服器之負載平衡	★ 以網域名稱伺服器為基礎之色情網站過濾系統
★ 使用熱門廣播法及支援點對點傳輸之影音內容傳遞網路	★ 變動頻寬平滑化之熱門廣播演算法

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

隨著網際網路的蓬勃發展，網路安全也日漸受到重視。網路入侵偵測系統就是針對網路上惡意封包作特徵比對以達到網路上重要的安全防護。然而，目前許多網路入侵偵測系統應用多數為軟體上的實作，因為網路速度的快速提升而成為目前在網路骨幹上偵測的瓶頸。因此許多在硬體的上的實作方法也已紛紛被提出。
本篇研究以史丹佛大學與Xilinx合作開發的NetFPGA平台設計網路惡意封包偵測系統以達到快速比對效果，雖然在FPGA上設計之IC具有快速、平行比對之特性，但該平台所能使用的資源有限，而導致特徵資料庫的數量受到限制。在目前網路入侵偵測系統的硬體實作上不僅耗費大量硬體電路成本也因為針對字串作完全比對降低網路吞吐量，因此本研究提出改良式的布隆過濾器在針對酬載的比對上建置不同特徵字串長度的群組來進行快速封包酬載之比對。由於透過布隆過濾器進行比對會造成誤報率的發生，因此本篇研究也針對一般的布隆過濾器與本篇改良的布隆過濾器作誤報率上的分析以達到最小誤報率發生。

摘要(英)

With the rapid development of Internet, the network security is increasing attention. Network intrusion detection system is to achieve the important security protection for the malicious packets on the network . However, many current
network intrusion detection system that is implemented on the software
applications which become the bottleneck when the network speed has improved rapidly and need to detect on the network. So many of the hardware implementation on the way also have been proposed.
This study by Stanford University that developed in collaboration with Xilinx platform NetFPGA malicious network packet detection system to achieve the effect on the network, although the IC design on the FPGA are faster, parallel comparison
of the features, but the platform can use of limited resources, which led to the number of database features are limited. In the current network intrusion detection system hardware implementation, not only cost intensive but also because of the hardware circuit for the exact match for the string reduces network throughput, this study proposed a modified Bloom filter build on the set of different
characteristics than the string length groups for fast comparison on packet payload. Because Bloom filters through to compare the incidence of false positives will result, so this study also for the general filter and our proposed
Bloom filter for improving false positive rate on the analysis to minimize false positives occur.

關鍵字(中)

★ NetFPGA
★ 布隆過濾器

關鍵字(英)

★ NetFPGA
★ Bloom Filter

論文目次

第一章緒論………………………. ………………………………………………………1
1.1 研究背景 1
1.2 研究動機與目的 3
1.3 章節架構 4
第二章相關研究 ………………………………………………………………………………….5
2.1 以暴力演算法作為酬載比對 5
2.2 以布隆過濾器作為酬載比對 8
2.2.1 布隆過濾器簡介 8
2.2.2 於FPGA上使用布隆過濾器之研究 9
2.2.3 誤報率之分析 11
2.3 NetFPGA介紹 12
2.4 相關研究比較 13
第三章系統架構與設計 …………………………………………………………………….14
3.1 目標 14
3.2 NetFPGA系統架構 14
3.3 本研究系統架構 17
3.4 PMM模組設計 18
3.5 4-Level Bloom Filter Unit設計 20
3.6 Hash Function Unit設計 22
3.7 系統流程 24
第四章布隆過濾器誤報率之分析 ……………………………………………………..27
4.1 誤報率之分析 27
4.2 基本的布隆過濾器 29
4.3 使用連續位元陣列的階層式布隆過濾器 30
4.4 使用分離式陣列的階層式布隆過濾器 32
4.5 模擬數據 33
4.6 實驗環境及工具 36
第五章結論及未來研究 …………………………………………………………………….42
5.1 研究結論與貢獻 42
5.2 未來研究 43
英文參考文獻 ............................................................................................................ 44
中文參考文獻 ............................................................................................................ 46
相關網站 .................................................................................................................... 46
附錄：研究論文計畫口詴建議改進事項………………………………………………….47

參考文獻

英文參考文獻
[1] Sarang Dharmapurikar, Michael Attig and John Lockwood, “Design and Implementation of a String Matching System for Network Intrusion Detection using FPGA-based Bloom filters”, Proc. of 12 th Annual IEEE Symposium on FieldProgrammable Custom Computing Machines, 2004.
[2] Sarang D., Praveen K., John, “Deep Packet Inspection using parallel bloom filters ”, Micro, IEEE Volume 24, Issue 1, Jan.-Feb. Page(s):52-61,2004.
[3] Jared Harwayne G.,Deian Stefan and Ishaan Dalal, “FPGA-based SoC for Real-Time Intrusion Detection using Counting Bloom Filters ”, Southeastcon, 2009. SOUTHEASTCON '09. IEEE , 5-8 March 2009.
[4] Yeim-Kuan Chang, Ming-Li Tsai and Yu-Ru Chung , “Multi-Character Processor Array for Pattern Matching in Network Intrusion Detection System,” In Proceedings of the 22th IEEE International Conference on Advanced Information Networking and Applications (AINA’08), pp. 991-996, 2008.
[5] Young H. Cho and William H. Mangione-Smith “Deep Packet Filter with Dedicated Logic and Read Only Memories”,IEEE Symposium on Field-Programable Custom Computing Machines, 20-23 April 2004.
[6] Seongyong Ahn, Hyejong Hong, Hyunjin Kim,Jin-Ho Ahn,Dongmyong Baek and Sungho Kang, “A Hardware-efficient Multi-Character String Matching Architecture using Brute-force Algorithm”, in SoC Design Conference (ISOCC), 2009 International , 22-24 Nov. 2009.
[7] Haoyu Song,Todd Sproull, Mike Attig,John Lockwood, “Snort offloader:A reconfigurable hardware NIDS Filter”,in Field Programmable Logic and Applications, 24-26 Aug. 2005.
[8] Katashita, T., Yamaguchi Y., Madeda, A, and Toda, K., “FPGA-Based Intrusion Detection System for 10 Gigabit Ethernet,” The Institute of Electronics, Information and Communication Engineers Vol. E90-D, No.12 , 2007.
[9] Aho, A. V. and Corasick, M. J., ‘‘Efficient string matching: an aid to bibliographic search,’’ Communications of the ACM 18, June. 1975 Page(s): 333-340.
[10] R. S. Boyer and J. S. Moore, “A Fast string searching algorithm”, Communications of the ACM,vil.20,no 10,1977.
[11] Knuth, D.E., Morris, J. H. Jr. and Pratt, V. R. , “Fast pattern matching in strings,” SIAM Journal on Computing, 6(2), Page(s):323-350,1977.
[12] Manber,U. and Sun,W., “GLIMPSE: A Tool to Search Through Entire File Systems,” Usenix Winter Technical Conference, Jan. , Page(s): 23-32,1944.
[13] C.R. Chang, C.C. Su, “The Cost Effective Pre-Processing based NFA Pattern Matching Architecture for NIDS”, on Advanced Information Networking and Applications (AINA), 2010 24th IEEE International Conference, 20-23 April 2010.
[14] Bloom, B. H., “Space/time trade-offs in hash coding with allowable errors,” Communications of the ACM, Volume 13, Issue 7, Page(s):422-426, 1970.
[15] Dharmapurikar, S., Michael Attig and Lockwood, J. W., “Design and Implementation of a String Matching System for Network Intrusion Detection using FPGA-based Bloom Filters,” Micro, IEEE Volume 24, Issue 1, Jan.-Feb. Page(s):52-61,2004.
[16] Covington, G. A., Gibb, G., Naous, J., Lookwood, J. W. and McKeown, N., “Encouraging Reusable Network Hardware Design,” http://netfpga.org/ , 2009.
[17] J L. Carter and M. Wegman, “Universal classes of hash functions”, J. Computer and System Science,vol. 1, no 4,pp 143-154, Apr. 1979.
中文參考文獻
[18] 朱彥豪，「以NetFPGA實作結合布隆過濾器與改良式Karp Rabin演算法之網路惡意封包偵測器」，國立中央大學資訊管理研究所碩士論文，2009

指導教授

曾黎明(Li-Ming Tseng)

審核日期

2011-8-30

推文