| 深度包检测中一种高效的正则表达式压缩算法 |
| |
| 引用本文： | 徐乾,鄂跃鹏,葛敬国,钱华林. 深度包检测中一种高效的正则表达式压缩算法[J]. 软件学报, 2009, 20(8): 2214-2226 |
| |
| 作者姓名： | 徐乾 鄂跃鹏 葛敬国 钱华林 |
| |
| 作者单位： | 1. 中国科学院,计算机网络信息中心,北京,100190;中国科学院,研究生院,北京,100049
2. 中国科学院,计算机网络信息中心,北京,100190 |
| |
| 基金项目： | Supported by the National High-Tech Research and Development Plan of China under Grant No.2007AA01Z214 (国家高技术研究发展计划(863)); the Youth Foundation of the Computer Network Information Center (CNIC), the Chinese Academy of Sciences under Grant No.0714071101 (CNIC青年基金) |
| |
| 摘 要： | 提出一种基于确定的有穷状态自动机(deterministic finite automaton,简称DFA)的正则表达式压缩算法.首先,定义了膨胀率DR(distending rate)来描述正则表达式的膨胀特性.然后基于DR提出一种分片的算法RECCADR (regular expressions cut and combine algorithm based on DR),有效地选择出导致DFA状态膨胀的片段并隔离,降低了单个正则表达式存储需求.同时,基于正则表达式的组合关系提出一种选择性分群算法REGADR(regular expressions group algorithm based on DR),在可以接受的存储需求总量下,通过选择性分群大幅度减少了状态机的个数,有效地降低了匹配算法的复杂性.
|
| 关 键 词： | 正则表达式 确定的有穷状态自动机(deterministic finite automaton,简称DFA) 深度包检测(deep packet inspection,简称DPI) 多模式匹配算法 入侵检测 |
| 收稿时间： | 2007-10-17 |
| 修稿时间： | 2008-03-14 |
Efficient Regular Expression Compression Algorithm for Deep Packet Inspection |
| |
| XU Qian,E Yue-Peng,GE Jing-Guo and QIAN Hua-Lin. Efficient Regular Expression Compression Algorithm for Deep Packet Inspection[J]. Journal of Software, 2009, 20(8): 2214-2226 |
| |
| Authors: | XU Qian E Yue-Peng GE Jing-Guo QIAN Hua-Lin |
| |
| Affiliation: | Computer Network Information Center;The Chinese Academy of Sciences;Beijing 100190;China;Graduate University;Beijing 100049;China |
| |
| Abstract: | |
| |
| Keywords: | regular expression DFA (deterministic finite automaton) deep packet inspection multi-pattern matching algorithm intrusion detection |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《软件学报》浏览原始摘要信息 |
|
点击此处可从《软件学报》下载全文 |
|
