Regular Expression Grouping Algorithm Based on Expansion Coefficient

doi:10.3969/j.issn.1006-2475.2014.07.029

Abstract

Abstract: Matching speed of deterministic finite automata (DFA) is far faster than that of the non-deterministic finite state automata (NFA). However, when a large number of regular expressions transform into a DFA, the DFA may consume huge storage space because of state explosion. Firstly, to describe characteristics of the regular expressions, expansion coefficient was defined. Based on the concept of expansion coefficient, a more efficient grouping algorithm which named IGA algorithm was proposed. IGA algorithm isolated those regular expressions which easily lead to state explosion, thus saved storage space. Experimental results show that, compared with the original algorithm, when the number of groups is same to the original one, IGA algorithm could reduce 25 percents of the number of states averagely.

Key words: expansion coefficient, regular expression, grouping algorithm, DFA

CLC Number:

TP393.08

WANG Mei-yang1, TANG Xue-wen2, YANG Zheng-yi3. Regular Expression Grouping Algorithm Based on Expansion Coefficient[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2014.07.029.

References 16

[1]	姚远,刘鹏,单征,等. 面向存储的正则表达式匹配算法综述[J]. 计算机应用, 2009,29(12):3171-3173.
[2]	邓凯元,姜磊. 正则表达式匹配引擎性能分析[J]. 计算机与现代化, 2011(7):105-107.
[3]	Kumar S, Dharmapurikar S, Yu Fang, et al. Algorithms to accelerate multiple regular expressions matching for deep packet inspection[C]// Proceedings of the 2006 ACM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications. 2006:339-350.
[4]	Kumar S, Turner J, Williams J. Advanced algorithms for fast and scalable deep packet inspection[C]// Proceedings of the 2006 ACM/IEEE Symposium on Architecture for Networking and Communications Systems. 2006:81-92.
[5]	Ficara D, Giordano S, Procissi G, et al. An improved DFA for fast regular expression matching[J]. Computer Communication Review, 2008,38(5):29-40.
[6]	Smith R, Estan C, Jha S. XFA: Faster signature matching with extended automata[C]// Proceedings of the 2008 IEEE Symposium on Security and Privacy. 2008:187-201.
[7]	Yu Fang, Chen Zhifeng, Diao Yanlei, et al. Fast and memory-efficient regular expression matching for deep packet inspection[C]// Proceedings of the 2006 ACM/IEEE Symposium on Architecture for Networking and Communications Systems. 2006:93-102.
[8]	Becchi M, Crowley P. A hybrid finite automaton for practical deep packet inspection[C]// Proceedings of the 2007 ACM Conference on Emerging Network Experiment and Technology. 2007.
[9]	李鲲鹏,兰巨龙,李印海. 基于Bloom filter的高效正则表达式匹配算法[J]. 计算机应用研究, 2012,29(3):950-954.
[10]	徐乾,鄂跃鹏,葛敬国,等. 深度包检测中一种高效的正则表达式压缩算法[J]. 软件学报, 2009,20(8):2214-2226.
[11]	王磊,陈曙晖,苏金树,等. 深度报文检测中基于GPU的正则表达式匹配引擎[J]. 计算机应用研究, 2010,27(11):4324-4327.
[12]	吴鸿伟,郭东辉,庄进发,等. 基于多GPU的正则表达式匹配技术[J]. 华中科技大学学报(自然科学版), 2013,41(1):51-55.
[13]	Mitra A, Najjar W, Bhuyan L. Compiling PCRE to FPGA for accelerating SNORT IDS[C]// Proceedings of the 2007 ACM/IEEE Symposium on Architecture for Networking and Communications Systems. 2007:127-136.
[14]	Lee J, Hwang S H, Park N. A high performance NIDS using FPGA-based regular expression matching[C]// Proceedings of the 2007 ACM Symposium on Applied Computing. 2007:1187-1191.
[15]	Dan Lo C, Tai Yi-Gang, Psarris K. Hardware implementation for network intrusion detection rules with regular expression support[C]// Proceedings of the 2008 ACM Symposium on Applied Computing. 2008:1535-1539.
[16]	唐球,姜磊,谭建龙,等. FPGA实现的正则表达式匹配性能分析[J]. 小型微型计算机系统, 2012,33(11):2405-2409.