基于TCAM的低能耗正则表达式匹配算法

丁麟轩; 黄昆; 张大方

doi:10.3969/j.issn.1000-436x.2014.08.020

您当前的位置：

首页 >

文章列表页 >

基于TCAM的低能耗正则表达式匹配算法

学术论文 | 更新时间：2024-10-11

- 基于TCAM的低能耗正则表达式匹配算法
- Low-power TCAM for regular expression matching
- 通信学报 2014年35卷第8期页码：162-168
- 作者机构：
  
  1. 湖南大学信息科学与工程学院，湖南长沙 410082
  2. 中国科学院计算技术研究所，北京 100190
- 作者简介：
  
  [ "丁麟轩（1988-），男，山东烟台人，湖南大学硕士生，主要研究方向为网络安全。" ]
  [ "黄昆（1978-），男，江西永丰人，博士，中国科学院助理研究员，主要研究方向为未来互联网、网络安全。" ]
  [ "张大方[通信作者]（1959-），男，上海人，博士，湖南大学教授、博士生导师，主要研究方向为可信系统与网络、网络安全、软件工程。E-mail:dfzhang@hnu.edu.cn。" ]
- 基金信息：
  
  国家重点基础研究发展规划（“973计划）基金资助项目;The National Basic Research Program of China (973 Program)(2012CB315805);国家自然科学基金资助项目;The National Natural Science Foundation of China(61173167);国家自然科学基金资助项目;The National Natural Science Foundation of China(61100171)
- DOI：10.3969/j.issn.1000-436x.2014.08.020
  中图分类号： TP393
- 网络出版日期：2014-08，
  
  纸质出版日期：2014-08-25
- 稿件说明：
移动端阅览
丁麟轩, 黄昆, 张大方. 基于TCAM的低能耗正则表达式匹配算法[J]. 通信学报, 2014,35(8):162-168.

Lin-xuan DING, Kun HUANG, Da-fang ZHANG. Low-power TCAM for regular expression matching[J]. Journal on communications, 2014, 35(8): 162-168.
丁麟轩, 黄昆, 张大方. 基于TCAM的低能耗正则表达式匹配算法[J]. 通信学报, 2014,35(8):162-168. DOI： 10.3969/j.issn.1000-436x.2014.08.020.

Lin-xuan DING, Kun HUANG, Da-fang ZHANG. Low-power TCAM for regular expression matching[J]. Journal on communications, 2014, 35(8): 162-168. DOI： 10.3969/j.issn.1000-436x.2014.08.020.

摘要

提出一种基于字符索引的正则表达式匹配算法，对确定型有限自动机（DFA

deterministic finite automaton）的字母表和状态进行分离存储，构建字符索引，减少匹配时激活的TCAM块数，显著降低TCAM能耗。实验结果表明：与DFA相比，基于字符索引的DFA（CIDFA

character-indexed DFA）在能耗上平均减少了92.7%，在存储空间开销上平均减少了32.0%，在吞吐量上平均提高了57.9%。

Abstract

A character-indexed regular expression matching algorithm was presented to address the limitations of TCAM power consumption. This algorithm used the idea of separating the alphabet table from the states in deterministic finite automaton (DFA) for building a character index

in order to reduce the number of activated TCAM blocks

which in turn translated low TCAM power. Experimental results showed that proposed algorithm reduces the TCAM power by 92.7% on average as well as the TCAM space usage by 32.0% on average

and improves the matching throughput by 57.9% on average compared to previous solutions based on DFA.

关键词

Keywords

references

PAXSON V , ASANOVIC K , DHARMAPURIKAR S , et al . Rethink-ing hardware support for network analysis and intrusion prevention [A ] . Proceeding of USENIX Workshop on Hot Topics in Security [C ] Van-couver, Canada , 2006 .

SOMMER R , PAXSON V . Enhancing byteleve network intrusion detection signatures with context [A ] . Proceeding of ACM Conference on Computer and Communications security [C ] Washington, DC, USA , 2003 . 262 - 271 .

Snort::rules [EB/OL ] . http://www.snort.org/start/rules http://www.snort.org/start/rules , 2013 - 12 - 01 .

The bro network security monitor [EB/OL ] . http:// bro-ids.org http:// bro-ids.org , 2013 .

HP TippingPoint S1200N IPS A7500 module [EB/OL ] . http://h17007. www1.hp.com/us/en/products/network-security/HP_TippingPoint_S1200N_IPS_A7500_Module/index.aspx?jumpid=reg_r1002_usen http://h17007. www1.hp.com/us/en/products/network-security/HP_TippingPoint_S1200N_IPS_A7500_Module/index.aspx?jumpid=reg_r1002_usen , 2013 - 12 - 01 .

Intrusion prevention system(IPS)-Cisco systems [EB/OL ] . http://www. cisco.com/en/US/products/ps5729/Products_Sub_Category_Home.html http://www. cisco.com/en/US/products/ps5729/Products_Sub_Category_Home.html , 2013 - 12 - 05 .

YU F , KATZ R , LAKSHMAN T V . Gigabit rate packet pattern-matching using TCAM [A ] . Proceeding of IEEE International Confer-ence on Network Protocols [C ] . Berlin, Germany , 2004 .

MEINERS C R , PATEL J , NORIGE E , et al . Fast regular expression matching using small TCAMs for network intrusion detection and prevention systems [A ] . Proceeding of the 19th USENIX Security Symposium [C ] . Washington, DC, USA , 2010 , 8 .

PENG K , TANG S , CHEN M , et al . Chain-based DFA deflation for fast and scalable regular expression matching using TCAM [A ] . Pro-ceeding of ACM/IEEE Symposium on Architectures for Networking and Communications Systems [C ] . Brooklyn, NY, USA , 2011 .

MA Y , BANERJEE S . A smart pre-classifier to reduce power con-sumption of TCAMS for multi-dimensional packet classification [A ] . Proceeding of ACM Conference of the Special Interest Group on Data Communication [C ] Helsinki, Finland , 2012 .

SIDHU R , PRASANNA V K . Fast regular expression matching using FPGA [A ] . Proceeding of IEEE International Symposium on Field-Programmable Custom Computing Machines [C ] Rohnert Park, CA,USA , 2001 .

CLARK C R , SCHIMMEL D E . Scalable pattern matching onhigh-speed networks [A ] . Proceeding of IEEE International Sympo-sium on Field-Programmable Custom Computing Machines [C ] . BNapa Valley, CA, USA , 2004 .

SOURDIS I , PNEVMATIKATOS D . Pre-decoded CAMs for efficient and high-speed NIDS pattern matching [A ] . Proceeding of IEEE Inter-national Symposium on Field-Programmable Custom Computing Ma-chines [C ] Napa Valley, CA, USA , 2004 .

MOSCOLA J , LOCKWOOD J , LOUI R P , et al . Implementation of a content-scanning module for an internet firewall [A ] . Proceeding of IEEE International Symposium on Field-Programmable Custom Computing Machines [C ] Napa Valley, CA, USA , 2003 .

KUMAR S , DHARMAPURIKAR S , YU F , et al . Algorithms to accel-erate multiple regular expressions matching for deep packet inspec-tion [A ] . Proceeding of ACM Conference of the Special Interest Group on Data Communication [C ] Pisa, Italy , 2006 .

KUMAR S , TURNER J , WILLIAMS J . Advanced algorithms for fast and scalable deep packet inspection [A ] . Proceeding of ACM/IEEE Symposium on Architectures for Networking and Communications Systems [C ] San Jose, CA, USA , 2006 .

BECCHI M , CADAMI S . Memory-efficient regular expression search using stae merging [A ] . Proceeding of IEEE International Conference on Computer Communications [C ] Anchorage, Alaska, USA , 2007 .

BECCHI M , CROWLEY P . An improved algorithm to accelerate regular expression evaluation [A ] . Proceeding of ACM/IEEE Sympo-sium on Architectures for Networking and Communications Sys-tems [C ] . San Jose, CA, USA , 2008 .

SMITH R , ESTAN C , JHA S . XFA: faster signature matching with extended automata [A ] . Proceeding of IEEE Symposium on Security and Privacy [C ] . Oakland, CA, USA , 2008 .

SMITH R , ESTAN C , JHA S , et al . Deflating the big bang: fast and scalable deep packet inspection with extended finite automata [A ] . Proceeding of ACM Conference of the Special Interest Group on Data Communication [C ] Seattle, WA, USA , 2008 .

MEINERS C R , LIU A X , TORNG E . TCAM Razor: a systematic approach towards minimizing packet classifiers in TCAMs [A ] . Pro-ceeding of IEEE International Conference on Network Protocols [C ] . Beijing, China , 2007 .

LIU A X , MEINERS C R , ZHOU Y . All-match based complete redun-dancy removal for packet classifiers in TCAMs [A ] . Proceeding of IEEE International Conference on Computer Communications [C ] Phoenix, AZ, USA , 2008 .

MEINERS C R , LIU A X , TORNG E . Bit weaving: a non-prefix ap-proach to compressing packet classifiers in TCAMs [A ] . Proceeding of IEEE International Conference on Network Protocols [C ] Princeton, NJ, USA , 2009 .

ZANE F , NARLIKAR G , BASU A . CoolCAMs: power-efficient TCAMs for forwarding engines [A ] . Proceeding of IEEE Interna-tional Conference on Computer Communications [C ] . San Francisco, USA , 2003 .

SPITZNAGEL E , TAYLOR D , TURNER J . Packet classification using extended TCAMs [A ] . Proceeding of IEEE International Conference on Network Protocols [C ] Atlanta, Georgia, USA , 2003 .

Regular expression processor [EB/OL ] . http://regex.wustl.edu/in-dex.php/Main_Page http://regex.wustl.edu/in-dex.php/Main_Page , 2013 - 12 - 01 .

AGRAWAL B , SHERWOOD T . Modeling TCAM power for next generation network devices [A ] . Proceeding of IEEE International Symposium on Performance Analysis of Systems and Software [C ] Austin, TX, USA , 2006 .

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

暂无数据