基于状态分组的高效i-DFA构造技术

发布时间：2019-03-13 18:41

【摘要】：正则表达式匹配在很多网络安全领域起着非常重要的作用。确定性有限自动机(DFA,deterministic finiteautomaton)具有线速稳定的匹配性能,因而更适合在高速网络环境下执行正则表达式匹配。但DFA可能由于状态膨胀而占用巨大的内存空间。作为状态膨胀问题的一种经典解决方案,i-DFA在大幅降低内存开销的同时,还能保证最差匹配性能。然而,已有方法构造i-DFA时在时间和空间上都是非常低效的。基于状态分组的思想,提出了一种高效的i-DFA构造方法。进一步地,对状态分组进行了形式化描述,并证明了获得最优状态分组是NP困难的,并基于局部搜索的思想提出了一种近优的状态分组算法。实验结果表明,相比经典的i-DFA构造方法,所做的工作在时间和空间上都有极大的改进:i-DFA的状态规模可能只是已有方法的2/3,而构造i-DFA所用时间仅是已有方法的1/16。
[Abstract]:Regular expression matching plays a very important role in many areas of network security. Deterministic finite automata (DFA,deterministic finiteautomaton) is more suitable for regular expression matching in high-speed networks because of its line-rate stable matching performance. But DFA may take up a huge amount of memory due to state inflation. As a classic solution to the state inflation problem, i-DFA can greatly reduce the memory overhead and ensure the worst matching performance at the same time. However, the existing methods for constructing i-DFA are very inefficient both in time and space. Based on the idea of state grouping, an efficient i-DFA construction method is proposed. Furthermore, the formal description of the state grouping is given, and it is proved that it is difficult to obtain the optimal state grouping by NP, and a near-optimal state grouping algorithm is proposed based on the idea of local search. The experimental results show that compared with the classical i-DFA construction method, the work done is greatly improved in both time and space: the scale of the state of the i-DFA may be only 2 ~ 3 of the existing method. The time it takes to construct a i-DFA is only 1. 16. 6% of the existing method.
【作者单位】：中国科学院信息工程研究所;信息内容安全技术国家工程实验室;国家计算机网络应急技术处理协调中心;
【基金】：国家高技术研究发展计划(“863”计划)基金资助项目(2011AA010703,2011AA010705) 国家自然科学基金资助项目(61070026,61003295) 国家242信息安全计划基金资助项目(2011F47)~~
【分类号】：TP393.08

【参考文献】