中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 计算技术研究所
  3. 中国科学院计算技术研究所
  4. 中国科学院计算技术研究所期刊论文
  5. 英文
Fast and Memory-Efficient Regular Expression Matching Using Transition Sharing

文献类型：期刊论文

作者Zhang, Shuzhuang1; Luo, Hao2; Fang, Binxing1; Yun, Xiaochun2
刊名IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS
出版日期2009-10-01
卷号E92D期号:10页码:1953-1960
关键词regular expression memory reduction deep packet inspection transition sharing
ISSN号0916-8532
DOI10.1587/transinf.E92.D.1953
英文摘要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.
资助项目National High-Tech Development 863 Program of China[2007AA01Z467] ; Major State Basic Research Development Program[2007CB311100]
WOS研究方向Computer Science
语种英语
WOS记录号WOS:000272394700016
出版者IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG
源URL[http://119.78.100.204/handle/2XEOYT63/11799]  
专题中国科学院计算技术研究所期刊论文_英文
通讯作者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.

入库方式： OAI收割

来源：计算技术研究所

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

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