基于两级存储的正则表达式匹配技术

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

Abstract

Abstract:

To solve the contradiction between the memory requirement and the inspection performance, a matching en-gine with two-stage memory was proposed for the first time. To deploy the state table to two-stage memory, theories of Markov chain was applied to the FSA. By computing the steady vector, the random access probabilities of each state could be obtained. Further, the states with higher probabilities were deployed in the embedded memory of FPGA, and the states with lower probabilities were deployed in SRAM. Rules in L7-filter were tested in simulation experiments, and the results show that our method can reach a throughput of 33 Gbit/s in large scale FSA, which is 50 times than that of ar-ranging the whole state table in SRAM.

Key words: regular expression, Markov chain, two-stage memory, hybrid FA

Shu-hui CHEN,Cheng-cheng XU. Regular expression matching technology with two-stage memory[J]. Journal on Communications, 2014, 35(6): 47-55.

Figures/Tables 10

References 20

[1]	张树壮，罗浩，方滨兴 . 面向网络安全的正则表达式匹配技术[J]. 软件学报， 2011,22(8): 1838-1854. ZHANG S Z , LUO H , FANG B X . egular expressions matching for network security[J]. Journal of Software, 2011,22(8): 1838-1854.
[2]	Application layer packet classifier for linux[EB/OL]. .
[3]	Snort user manual, the snort project[EB/OL]. .
[4]	Introduction to bro[EB/OL]. .
[5]	YU F , CHEN Z , DIAO Y , et al. Fast and memory-efficient regular expression matching for deep packet inspection[A]. Architecture for Networking and Communications Systems, ANCS2006 ACM/IEEE Symposium on[C]. 2006.93-102.
[6]	BECCHIMCADAMBI S . Memory-efficient regular expression search using state merging[A]. INFOCOM 2007, 26th IEEE International Conference on Computer Communications IEEE[C]. 2007.1064-1072.
[7]	陈曙晖，苏金树，范慧萍等. 一种基于深度报文检测的 FSM 状态表压缩技术[J]. 计算机研究与发展， 2008,45(8): 1299-1306. CHEN S H , SU J S , FANH P , et al. An FSM state table compressing method based on deep packet inspection[J]. Journal of Computer Re-search and Development, 2008,45(8): 1299-1306.
[8]	KUMAR S , DHARMAPURIKAR S , YU F , et al. Algorithms to accel-erate multiple regular expressions matching for deep packet inspec-tion[J]. 2006 ACM SIGCOMM Computer Communication Review, 2006,36 (4): 339-350.
[9]	杨毅夫，刘燕兵，刘萍 . 正则表达式的DFA压缩算法[J]. 通信学报， 2009,30(10): 36-42. YANG Y F , LIU Y B , LIU P . Effective algorithm of compressing regular expressions DFA[J]. Journal on Communications, 2009,30(10): 36-42.
[10]	SOMMER R , PAXSON V . Enhancing byte-level network instruction detection signatures with context[A]. ACM Conf on Computer and Communication Security[C]. 2003. 262-271.
[11]	KUMARS , CHANDRASEKARAN B , TRUNER J , et al. Curing regular expressions matching algorithms from insomnia, amnesia, and acalculia[J]. Proceedings of ACM/IEEE ANCS[C]. 2007. 155-164.
[12]	BECCHI M , CRWOLEY P . A hybrid finite automaton for practical deep packet inspection[A]. ACM Computer Communication Net-works ,CoNEXT 2007[C]. New York, NY, USA, 2007.
[13]	LIN C H , LIU J C . M-DFA(multithreaded DFA): an algorithm for reduction of state transitions and acceleration of REGEXP match-ing[A]. Proceedings of the 8th ACM/IEEE Symposium on Architec-tures for Networking and Communications Systems[C]. 2012.79-80.
[14]	王磊，陈曙晖，苏金树等. 深度报文检测中基于 GPU 的正则表达式匹配引擎[J]. 计算机应用研究， 2010,27(11): 4324-4327. WANG L , CHEN S H , SU J S . , et al. GPU-based regular expression match engine for deep packet inspection[J]. Journal of Application Research of Computers, 2010,27(11): 4324-4327.
[15]	王梓坤 . 北京：科学出版社， 1965. WANG Z K . Beijing: Science Press, 1965.
[16]	GEBALI F . Analysis of Computer and Communication Networks[M]. Victoria:Springer Science, 2008.123.
[17]	侯振挺，郭青峰 . 齐次可列马尔可夫过程[M]. 北京：科学出版社， 1978. HOU Z T , GUO Q F , Countable and Homogeneous Markov Chain[M]. Beijing: Science Press, 1978.
[18]	XIE A G , BEEREL P A . Efficient state classification of finite state markov chains[A]. DAC98[C]. San Francisco, 1998.
[19]	关治，陈景良 . 数值计算方法[M]. 北京：清华大学出版社， 2002. GUAN Z , CHEN J L , Numerical Computing Analysis[M]. Beijing: Tsinghua Press, 2002.
[20]	DAVID K , WARD C . Numerical Analysis[M]. Beijing: China Machine Press, 2005.

Metrics

Recommended 0

No Suggested Reading articles found!

状态	b	a	b	e	f
DFA	(0,5)	(0,1)	(0,5)	(0,6)	(0,7)
NFA		1	1、2	1	1

存储器	频率/MHz	访存周期	访存时间/ns	吞吐量/(Gbit·s^?1)
FPGA	400	1/2	1.25	6.4
SRAM	250	3	12	0.67

测试数据集	DFA访问次数	NFA访问次数	FPGA命中次数	SRAM访问次数	FPGA命中率	匹配速度/(ns·byte^?1)	吞吐量/(Gbit·s^?1)
DARPA99	228 370 907	9 020 615	202 893 878	34 497 644	85.46%	2.81	25.60
CAPTURE	2 057 804 459	84 666 639	1 960 267 851	182 203 247	91.49%	2.16	33.26

Regular expression matching technology with two-stage memory

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 20

Related Articles 15

Metrics

Recommended 0

[1]	Haiyan KANG, Molan LONG. Research on network attack analysis method based on attack graph of absorbing Markov chain [J]. Journal on Communications, 2023, 44(2): 122-135.
[2]	Wei SHE, Xinpeng RONG, Wei LIU, Zhao TIAN. Generative blockchain-based covert communication model based on Markov chain [J]. Journal on Communications, 2022, 43(10): 121-132.
[3]	Xin JIAN,Yixiao WEI,Yuqin LIU,Jian SONG,Xiaoping ZENG,Xiaoheng TAN. Power consumption modeling and optimization for NB-IoT eDRX [J]. Journal on Communications, 2019, 40(4): 107-116.
[4]	Xin JIAN,Yuqin LIU,Yixiao WEI,Jian SONG,Fang WANG,Shu FU,Xiaoheng TAN. Performance analysis and optimization for coverage classes updating mechanism of narrow-band internet of things [J]. Journal on Communications, 2018, 39(11): 70-79.
[5]	Xian-zhong TIAN,Min GUO,Jia-cun HE,Gao LIU,Yi-nan ZHU. Multi relay node selection strategy for energy capture collaborative relay network [J]. Journal on Communications, 2017, 38(Z2): 1-7.
[6]	Feng LI,Ya-li SI,Zhen CHEN,Li-min SHEN. Lightweight opportunistic routing forwarding strategy based on Markov chain [J]. Journal on Communications, 2017, 38(5): 108-120.
[7]	Quan-hua ZHAO,Xue SHI,Yu WANG,Yu LI. Remote sensing image segmentation based on spatially constrained Gaussian mixture model with unknown class number [J]. Journal on Communications, 2017, 38(2): 34-43.
[8]	Zhi-yuan LI,Ru-long CHEN,Ru-chuan WANG. Exploiting interests and behavior prediction for dynamic resource discovery in mobile social networking [J]. Journal on Communications, 2016, 37(4): 34-43.
[9]	HOUHan-xun Z,UOWei G,IUJian L,IADa-yu J. Internet worm propagation model based on Markov chain [J]. Journal on Communications, 2015, 36(5): 66-71.
[10]	IUYan L,UBin H,ULi-ping X. Efficient algorithm for computing Walsh spectrum and differential probability [J]. Journal on Communications, 2015, 36(5): 167-173.
[11]	ONGYang-yang G,IUQin-rang L,ANGZhen-xi Y,HAOXiang-yu S,INGChi-qiang X,IAOHui-juan J,ENGZhi-bin P. Improved DFA algorithm based on multi-dimensional finite automata [J]. Journal on Communications, 2015, 36(5): 174-186.
[12]	Shun-fu JIN,Chen-fei WANG,Ling-ling CHEN,Zhan-qiang HUO. Modeling and analysis of Cloud-P2P storage architecture [J]. Journal on Communications, 2015, 36(3): 216-223.
[13]	Lin-xuan DING,Kun HUANG,Da-fang ZHANG. Low-power TCAM for regular expression matching [J]. Journal on Communications, 2014, 35(8): 162-168.
[14]	. Low-power TCAM for regular expression matching [J]. Journal on Communications, 2014, 35(8): 20-168.
[15]	. Regular expression matching technology with two-stage memory [J]. Journal on Communications, 2014, 35(6): 7-55.