Accelerating the bit-split string matching algorithm using Bloom filters

doi:10.1016/j.comcom.2010.04.043

	Accelerating the bit-split string matching algorithm using Bloom filters
	Huang, Kun 2; Zhang, Dafang 1,3; Qin, Zheng 3
	2010-09-15
发表期刊	COMPUTER COMMUNICATIONS
ISSN	0140-3664
卷号	33 期号:15 页码:1785-1794
摘要	Deep Packet Inspection (DPI) is essential for network security to scan both packet header and payload to search for predefined signatures. As link rates and traffic volumes of Internet are constantly growing, string matching using Deterministic Finite Automaton (DFA) will be the performance bottleneck of DPI. The recently proposed bit-split string matching algorithm suffers from the unnecessary state transitions problem. The root cause lies in the fact that the bit-split algorithm makes pattern matching in a "not seeing the forest for trees" approach, where each tiny DFA only processes a b-bit substring of each input character, but cannot check whether the entire character belongs to the alphabet of original DFA. This paper presents a byte- filtered string matching algorithm, where Bloom filters are used to preprocess each character of every incoming packet to check whether the character belongs to the original alphabet, before performing bit- split string matching. If not, each tiny DFA either makes a transition to its initial state or stops any state transition. Experimental results demonstrate that compared with the bit- split algorithm, our byte-filtered algorithm enormously reduces the string matching time as well as the number of state transitions of tiny DFAs on both synthetic and real signature rule sets. (C) 2010 Elsevier B.V. All rights reserved.
关键词	Intrusion detection String matching Bloom filter Bit-split Byte filter
DOI	10.1016/j.comcom.2010.04.043
收录类别	SCI
语种	英语
资助项目	National Science Foundation of China[90718008] ; National Basic Research Program of China (973)[2007CB310702]
WOS研究方向	Computer Science ; Engineering ; Telecommunications
WOS类目	Computer Science, Information Systems ; Engineering, Electrical & Electronic ; Telecommunications
WOS记录号	WOS:000281892800003
出版者	ELSEVIER SCIENCE BV
引用统计	被引频次：11[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/12222
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Zhang, Dafang
作者单位	1.Hunan Univ, Sch Comp & Commun, Changsha 410082, Hunan, Peoples R China 2.Chinese Acad Sci, Inst Comp Technol, Beijing 100190, Peoples R China 3.Hunan Univ, Sch Software, Changsha 410082, Hunan, Peoples R China
推荐引用方式 GB/T 7714	Huang, Kun,Zhang, Dafang,Qin, Zheng. Accelerating the bit-split string matching algorithm using Bloom filters[J]. COMPUTER COMMUNICATIONS,2010,33(15):1785-1794.
APA	Huang, Kun,Zhang, Dafang,&Qin, Zheng.(2010).Accelerating the bit-split string matching algorithm using Bloom filters.COMPUTER COMMUNICATIONS,33(15),1785-1794.
MLA	Huang, Kun,et al."Accelerating the bit-split string matching algorithm using Bloom filters".COMPUTER COMMUNICATIONS 33.15(2010):1785-1794.