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

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

摘要/Abstract

摘要：

提出一种基于字符索引的正则表达式匹配算法，对确定型有限自动机（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.

Key words: regular expression matching, character index, block-based storage, low power

丁麟轩,黄昆,张大方. 基于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.

图/表 7

图1

图2

表1

图3

图4

表2

表3

参考文献 27

[1]	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.
[2]	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.
[3]	Snort::rules[EB/OL]. , 2013- 12-01.
[4]	The bro network security monitor[EB/OL]. , 2013.
[5]	HP TippingPoint S1200N IPS A7500 module[EB/OL]. , 2013-12-01.
[6]	Intrusion prevention system(IPS)-Cisco systems[EB/OL]. , 2013-12-05.
[7]	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.
[8]	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.
[9]	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.
[10]	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.
[11]	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.
[12]	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.
[13]	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.
[14]	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.
[15]	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.
[16]	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.
[17]	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.
[18]	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.
[19]	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.
[20]	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.
[21]	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.
[22]	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.
[23]	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.
[24]	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.
[25]	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.
[26]	Regular expression processor[EB/OL]. , 2013-12-01.
[27]	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.

特征规则集	规则条数	字母表大小	通配符表达式条数
R1	31	88	7
R2	23	81	2
R3	33	78	1
R4	33	78	14
R5	33	78	33
R6	31	88	15
R7	23	81	11
R8	23	81	23
R9	31	88	31
R10	217	110	18

特征规则集	DFA/MB	CIDFA/MB
R1	10.32	7.02
R2	16.30	11.09
R3	18.38	12.50
R4	31.34	21.32
R5	50.05	34.03
R6	83.83	57.00
R7	85.77	58.33
R8	96.05	65.32
R9	191.84	130.45
R10	17.29	11.76

特征规则集	DFA/(Gbit·s^?1)	CIDFA/(Gbit·s^?1)
特征规则集	DFA/(Gbit·s^?1)	最小	最大
R1	1.98	3.11	3.63
R2	1.82	2.72	3.11
R3	1.82	2.72	3.11
R4	1.68	2.42	2.72
R5	1.56	2.42	2.72
R6	1.56	2.18	2.42
R7	1.56	2.18	2.42
R8	1.56	2.18	2.42
R9	1.45	1.98	2.18
R10	1.82	3.11	3.63