| 本文已被：浏览 5351次 下载 7840次 |
码上扫一扫！ |
|
|
| 正则表达式分组的1/(1-1/k)-近似算法 |
|
柳厅文1,2,3, 孙永1,3, 卜东波1, 郭莉1,3, 方滨兴1,3
|
|
1.中国科学院 计算技术研究所,北京 100190;2.中国科学院 研究生院,北京 100049;3.信息内容安全技术国家工程实验室,北京 100190
|
|
| 摘要: |
| 对正则表达式集合进行分组是解决DFA状态膨胀问题的一种重要方法.已有的分组算法大都是启发式的或蛮力的,分组效果很差.分析了DFA状态膨胀的原因,总结了某些正则表达式间的冲突状况.证明了当冲突非负和冲突独立时,正则表达式集合的最优k分组问题可归结为最大k割问题,从而说明该问题是NP-Hard的.基于局部搜索的思想,提出了一种分组算法GRELS来解决分组问题,并证明对最大k割问题,该算法的近似比是1/(1-1/k).与已有的分组算法相比,当分组数目相同时,GRELS算法分组结果的状态总数最少,并且集合发生变化时所需的更新时间最短. |
| 关键词: 正则表达式 深度包检测 分组算法 局部搜索 1/(1-1/k)近似 |
| DOI：10.3724/SP.J.1001.2012.04098 |
| 分类号: |
| 基金项目:国家自然科学基金(61070026); 国家重点基础研究发展计划(973)(2007CB311100); 国家高技术研究发展计划(863)(2011AA010703); 中国科学院战略性先导科技专项(XDA06030200) |
|
| 1/(1-1/k)-Optimal Algorithm for Regular Expression Grouping |
|
LIU Ting-Wen1,2,3, SUN Yong1,3, BU Dong-Bo1, GUO Li1,3, FANG Bin-Xing1,3
|
|
1.Institute of Computing Technology, The Chinese Academy of Sciences, Beijing 100190, China;2.Graduate University, The Chinese Academy of Sciences, Beijing 100049, China;3.National Engineering Laboratory for Information Security Technologies, Beijing 100190, China
|
| Abstract: |
| Dividing regular expression sets into multiple groups is an important process to solve the problem of DFA state explosion. Previous grouping algorithms are heuristic or are done by brute-force, which have poor grouping results. This paper analyzes the reasons of states explosion and summarizes conflicting relationship among regular expressions of some types. When conflicts are non-negative and independent, the optimum k-grouping problem of regular expression sets can be reduced to the maximum k-cut problem, which is NP-hard. Based on the idea of local searching, a new grouping algorithm named GRELS is introduced to solve the problem efficiently, which is 1/(1-1/k) -approximation for maximum k-cut problem. Comparing with previous grouping algorithms, GRELS has the minimum number of states for the same number of groups, and requires the least time to update grouping results when pattern sets change. |
| Key words: regular expression deep packet inspection grouping algorithm local searching 1/(1-1/k)- approximation |
