基于有状态Bloom filter引擎的高速分组检测
作者:
基金项目:

Supported by the National Natural Science Foundation of China under Grant Nos.60473082, 60403035 (国家自然科学基金); the National Grand Fundamental Research 973 Program of China under Grant No.2003CB314801 (国家重点基础研究发展规划(973))

  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [15]
  • |
  • 相似文献 [20]
  • |
  • 引证文献
  • | |
  • 文章评论
    摘要:

    越来越多的网络安全技术通过分析网络分组中的内容来检测报文中是否含有恶意攻击代码.为了能够在线检测攻击,部署在路由器中的分组检测模块对于分组检测的速度也提出了越来越高的要求.虽然在这个领域已有很多研究工作,然而在性能、可扩展性和适用性方面还有很多可研究的空间.提出了一种基于有状态Bloom filter引擎的高速分组检测方法State-Based Bloom filter engine(SABFE).通过并行查找Bloom filter和前缀寄存器堆,以及利用多个并行的Bloom filter引擎进行流并行检测,达到了较高的吞吐性能.同时,利用快速查找表和前缀寄存器堆保存当前子串的匹配状态来检测长的规则.分析和模拟实验表明:该方法在规则长度增加时依然保持了较高的吞吐性能,可以实现线速的分组检测,同时,极大地减少了硬件资源开销,提高了可扩展性.

    Abstract:

    More and more network security applications depend on inspecting the content of the packets to detect the malicious attacks. To detect these attacks online, packet inspection demands exceptionally high performance. A lot of research works have been done in this field, and yet there is still significant room for improvement in throughput and scalability. This paper proposes a fast packet inspection algorithm based on state-based Bloom filter engines (SABFE). To achieve high throughput, parallel design is adopted when searching in one Bloom filter engine and between multiple Bloom filter engines. In addition, specific lookup table and prefix register heap are constructed in SABFE to keep the state of the matched prefix for the sake of detecting long patterns. The analysis and the evaluation show that the high throughput of the algorithm can satisfy the wire speed detection requirement when the low resource consumption in hardware resource further improves the scalability of SABFE.

    参考文献
    [1]Moore D,Paxson V,Savage S,Shannon C,Staniford S,Weaver N.Inside the slammer worm.IEEE Security and Privacy,2003,1(4):33-39.
    [2]Moore D,Shannon C.Code-Red:A case study on the spread and victims of an Internet worm.In:Proc.of the 2002 ACM SICGOMM Internet Measurement Workshop.Marseille,2002.273-284.http://portal.acm.org/citation.cfm?id=637244&dl= ACM&coll=&CFID=15151515&CFTOKEN=6184618
    [3]Kim HA,Karp B.Autograph:Toward automatic distributed worm signature detection.In:Proc.of the USENIX Security Symp.Diego,2004.271-286.http://www.usenix.org/events/sec04/tech/full_papers/kim/kim.pdf
    [4]Singh S,EstanC,Varghese G,Savage S.Automated worm fingerprinting.In:Proc.of the 6th ACM/USENIX Symp.on Operating System Design and Implementation (OSDI).San Francisco,2004.45-60.http://www.usenix.org/events/osdi04/tech/full_papers/ singh/singh.pdf
    [5]Axelsson.Intrusion detection systems:A survey and taxonomy.Technical Report,99-15,Chalmers University,2000.
    [6]Bloom B.Space/Time trade-offs in Hash coding with allowable errors.Communications of the ACM,1970,13(7):422-426.
    [7]Dharmapurikar S,Krishnamurthy P,Sproull T,Lockwood J.Deep packet inspection using parallel Bloom filters.In:Proc.of the Symp.on High Performance Interconnects (HotI).Stanford,2003.44-51.http://www.hoti.org/archive/Hoti11_program/papers/ hoti11_07_dharmapurikar_s.pdf
    [8]Dharmapurikar S,Attig M,Lockwood J.Design and implementation of a string matching system for network intrusion detection using FPGA-based Bloom filters.Technical Report,WUCSE-2004-12,St.Louis:Washington University,2004.
    [9]Song HY,Dharmapurikar S,Turner J,Lockwood J.Fast hash table lookup using extended Bloom filter:An aid to network processing.In:Proc.of the ACM SIGCOMM 2005.Philadelphia,2005.20-26.http://portal.acm.org/citation.cfm?id=1080114&dl= ACM&coll=&CFID=15151515&CFTOKEN=6184618
    [10]Yu F,Katz RH,Lakshman TV.Gigabit rate packet pattern-matching using TCAM.In:Proc.of the 12th IEEE Int'l Conf.on Network Protocols (ICNP 2004).Berlin,2004.174-183.http://portal.acm.org/citation.cfm?id=1025890&dl=GUIDE&coll=GUIDE
    [11]Lakshminarayanan K,Rangarajan A,Venkatachary S.Algorithms for advanced packet classification with ternary CAMs.In:Proc.of the ACM SIGCOMM 2005.Philadelphia,2005.193-204.http://portal.acm.org/citation.cfm?id=1080115&dl=ACM&coll= &CFID=15151515&CFTOKEN=6184618#
    [12]Taylor DE.Survey and taxonomy of packet classification techniques.Technical Report,WUCSE-2004-24,St.Louis:Washington University,2004.
    [13]Baeza-Yates R.Algorithms for string searching:A survey.SIGIR Forum,1989,23(3-4):34-58.
    [14]Bakerand ZK,Prasanna VK.Time and area effificient pattern matching on FPGAs.In:Proc.of the 2004 ACM/SIGDA 12th Int'l Symp.on Field Programmable Gate Arrays (FPGA 2004).Monterey,2004.223-232.http://portal.acm.org/citation.cfm?coll= GUIDE&dl=GUIDE&id=968312#
    [15]Tuck N,Sherwood T,Calder B,Varghese G.Deterministic memory-efficient string matching algorithms for intrusion detection.In:Proc.of the IEEE Infocom Conf.Hong Kong,2004.333-340.http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1354682
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

叶明江,崔勇,徐恪,吴建平.基于有状态Bloom filter引擎的高速分组检测.软件学报,2007,18(1):117-126

复制
分享
文章指标
  • 点击次数:5511
  • 下载次数: 6319
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:2005-11-08
  • 最后修改日期:2006-04-03
文章二维码
您是第19754484位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号