Fast and Memory-Efficient Regular Expression Matching Using Transition Sharing

doi:10.1587/transinf.E92.D.1953

	Fast and Memory-Efficient Regular Expression Matching Using Transition Sharing
	Zhang, Shuzhuang 1; Luo, Hao 2; Fang, Binxing 1; Yun, Xiaochun 2
	2009-10-01
发表期刊	IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS
ISSN	0916-8532
卷号	E92D 期号:10 页码:1953-1960
摘要	Scanning packet payload at a high speed has become a crucial task in modern network management due to its wide variety applications on network security and application-specific services. Traditionally, Deterministic finite automatons (DFAs) are used to perform this operation in linear time. However, the memory requirements of DFAs are prohibitively high for patterns used in practical packet scanning, especially when many patterns are compiled into a single DFA. Existing solutions for memory blow-up are making a trade-off between memory requirement and memory access of processing per input character. In this paper we proposed a novel method to drastically reduce the memory requirements of DFAs while still maintain the high matching speed and provide worst-case guarantees. We removed the duplicate transitions between states by dividing all the DFA states into a number of groups and making each group of states share a merged transition table. We also proposed an efficient algorithm For transition sharing between states. The high efficiency in time and space made our approach adapted to frequently updated DFAs. We performed several experiments on real world rule sets. Overall, for all rule sets and approach evaluated, Our approach offers the best memory versus run-time trade-offs.
关键词	regular expression memory reduction deep packet inspection transition sharing
DOI	10.1587/transinf.E92.D.1953
收录类别	SCI
语种	英语
资助项目	National High-Tech Development 863 Program of China[2007AA01Z467] ; Major State Basic Research Development Program[2007CB311100]
WOS研究方向	Computer Science
WOS类目	Computer Science, Information Systems ; Computer Science, Software Engineering
WOS记录号	WOS:000272394700016
出版者	IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG
引用统计	被引频次：1[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/11800
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Zhang, Shuzhuang
作者单位	1.Harbin Inst Technol, Res Ctr Comp Network & Informat Secur Technol, Harbin 150001, Peoples R China 2.Chinese Acad Sci, Inst Comp Technol, Beijing 100190, Peoples R China
推荐引用方式 GB/T 7714	Zhang, Shuzhuang,Luo, Hao,Fang, Binxing,et al. Fast and Memory-Efficient Regular Expression Matching Using Transition Sharing[J]. IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS,2009,E92D(10):1953-1960.
APA	Zhang, Shuzhuang,Luo, Hao,Fang, Binxing,&Yun, Xiaochun.(2009).Fast and Memory-Efficient Regular Expression Matching Using Transition Sharing.IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS,E92D(10),1953-1960.
MLA	Zhang, Shuzhuang,et al."Fast and Memory-Efficient Regular Expression Matching Using Transition Sharing".IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS E92D.10(2009):1953-1960.