中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 计算技术研究所
  3. 中国科学院计算技术研究所
  4. 中国科学院计算技术研究所期刊论文
  5. 英文
Accelerating the bit-split string matching algorithm using Bloom filters

文献类型：期刊论文

作者Huang, Kun2; Zhang, Dafang1,3; Qin, Zheng3
刊名COMPUTER COMMUNICATIONS
出版日期2010-09-15
卷号33期号:15页码:1785-1794
关键词Intrusion detection String matching Bloom filter Bit-split Byte filter
ISSN号0140-3664
DOI10.1016/j.comcom.2010.04.043
英文摘要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.
资助项目National Science Foundation of China[90718008] ; National Basic Research Program of China (973)[2007CB310702]
WOS研究方向Computer Science ; Engineering ; Telecommunications
语种英语
WOS记录号WOS:000281892800003
出版者ELSEVIER SCIENCE BV
源URL[http://119.78.100.204/handle/2XEOYT63/12221]  
专题中国科学院计算技术研究所期刊论文_英文
通讯作者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.

入库方式： OAI收割

来源：计算技术研究所

浏览0
下载0
收藏0
其他版本

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。