| 基于状态分组的高效i-DFA构造技术 |
| |
| 引用本文： | 乔登科,王卿,柳厅文,孙永,郭莉. 基于状态分组的高效i-DFA构造技术[J]. 通信学报, 2013, 34(8): 14-109. DOI: 10.3969/j.issn.1000-436x.2013.08.014 |
| |
| 作者姓名： | 乔登科 王卿 柳厅文 孙永 郭莉 |
| |
| 作者单位： | 1. 中国科学院 信息工程研究所，北京 100093; 信息内容安全技术国家工程实验室，北京100093
2. 国家计算机网络应急技术处理协调中心,北京,100029 |
| |
| 基金项目： | 国家高技术研究发展计划(“863”计划)基金资助项目(2011AA010703, 2011AA010705)；国家自然科学基金资助项目(61070026, 61003295)；国家242信息安全计划基金资助项目(2011F47) |
| |
| 摘 要： | 正则表达式匹配在很多网络安全领域起着非常重要的作用。确定性有限自动机(DFA,deterministic finiteautomaton)具有线速稳定的匹配性能,因而更适合在高速网络环境下执行正则表达式匹配。但DFA可能由于状态膨胀而占用巨大的内存空间。作为状态膨胀问题的一种经典解决方案,i-DFA在大幅降低内存开销的同时,还能保证最差匹配性能。然而,已有方法构造i-DFA时在时间和空间上都是非常低效的。基于状态分组的思想,提出了一种高效的i-DFA构造方法。进一步地,对状态分组进行了形式化描述,并证明了获得最优状态分组是NP困难的,并基于局部搜索的思想提出了一种近优的状态分组算法。实验结果表明,相比经典的i-DFA构造方法,所做的工作在时间和空间上都有极大的改进:i-DFA的状态规模可能只是已有方法的2/3,而构造i-DFA所用时间仅是已有方法的1/16。
|
| 关 键 词： | 正则表达式 状态膨胀 状态分组 局部搜索 |
| 收稿时间： | 2013-05-02 |
Efficient i-DFA construction algorithm based on state grouping |
| |
| QIAO Deng-ke , WANG Qing , LIU Ting-wen , SUN Yong , GUO Li. Efficient i-DFA construction algorithm based on state grouping[J]. Journal on Communications, 2013, 34(8): 14-109. DOI: 10.3969/j.issn.1000-436x.2013.08.014 |
| |
| Authors: | QIAO Deng-ke WANG Qing LIU Ting-wen SUN Yong GUO Li |
| |
| Affiliation: | 1. Institute of Information Engineering,Chinese Academy of Sciences,Beijing 100093,China;2. National Engineering Laboratory for Information Security Technologies,Beijing 100093,China;3. National Computer Network Emergency Response Technical Team/Coordination Center of China,Beijing 100029,China |
| |
| Abstract: | |
| |
| Keywords: | regular expression state explosion state grouping local search |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《通信学报》浏览原始摘要信息 |
|
点击此处可从《通信学报》下载全文 |
|
