Title page for 985202020


[Back to Results | New Search]

Student Number 985202020
Author Jun-ping Zhu(朱君平)
Author's Email Address No Public.
Statistics This thesis had been viewed 564 times. Download 353 times.
Department Computer Science and Information Engineering
Year 2010
Semester 2
Degree Master
Type of Document Master's Thesis
Language zh-TW.Big5 Chinese
Title Analysis of Effective Pattern Matching Using Pipelined Bloom Filter Based on NetFPGA
Date of Defense 2011-07-20
Page Count 57
Keyword
  • Bloom Filter
  • NetFPGA
  • Abstract 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.
    Table of Content 第一章緒論……………………….………………………………………………………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.3NetFPGA介紹12
    2.4相關研究比較13
    第三章系統架構與設計…………………………………………………………………….14
    3.1目標14
    3.2NetFPGA系統架構14
    3.3本研究系統架構17
    3.4PMM模組設計18
    3.54-Level Bloom Filter Unit設計20
    3.6Hash 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
    Reference 英文參考文獻
    [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
    Advisor
  • Li-Ming Tseng(曾黎明)
  • Files
  • 985202020.pdf
  • approve immediately
    Date of Submission 2011-08-30

    [Back to Results | New Search]


    Browse | Search All Available ETDs

    If you have dissertation-related questions, please contact with the NCU library extension service section.
    Our service phone is (03)422-7151 Ext. 57407,E-mail is also welcomed.