通信学报 ›› 2013, Vol. 34 ›› Issue (8): 102-109.doi: 10.3969/j.issn.1000-436x.2013.08.014

• 学术论文 • 上一篇    下一篇

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

乔登科1,2,王卿3,柳厅文1,2,孙永1,2,郭莉1,2   

  1. 1 中国科学院 信息工程研究所，北京 100093
    2 信息内容安全技术国家工程实验室，北京100093
    3 国家计算机网络应急技术处理协调中心，北京 100029
  • 出版日期:2013-08-25 发布日期:2017-08-31
  • 基金资助:
    国家高技术研究发展计划(“863”计划)基金资助项目;国家高技术研究发展计划(“863”计划)基金资助项目;国家自然科学基金资助项目;国家自然科学基金资助项目;国家242信息安全计划基金资助项目

Efficient i-DFA construction algorithm based on state grouping

Deng-ke QIAO1,2,Qing WANG3,Ting-wen LIU1,2,Yong SUN1,2,Li GUO1,2   

  1. 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
  • Online:2013-08-25 Published:2017-08-31
  • Supported by:
    The National High Technology Research and Development Program of China (863 Program);The National High Technology Research and Development Program of China (863 Program);The National Natural Science Foundation of China;The National Natural Science Foundation of China;242 National Information Security Pro-gram

在线阅读

1

PDF下载

533

摘要：

正则表达式匹配在很多网络安全领域起着非常重要的作用。确定性有限自动机 (DFA,deterministic finite automaton) 具有线速稳定的匹配性能，因而更适合在高速网络环境下执行正则表达式匹配。但 DFA 可能由于状态膨胀而占用巨大的内存空间。作为状态膨胀问题的一种经典解决方案，i-DFA在大幅降低内存开销的同时，还能保证最差匹配性能。然而，已有方法构造i-DFA时在时间和空间上都是非常低效的。基于状态分组的思想，提出了一种高效的 i-DFA 构造方法。进一步地，对状态分组进行了形式化描述，并证明了获得最优状态分组是 NP困难的，并基于局部搜索的思想提出了一种近优的状态分组算法。实验结果表明，相比经典的i-DFA构造方法，所做的工作在时间和空间上都有极大的改进：i-DFA的状态规模可能只是已有方法的2/3，而构造i-DFA所用时间仅是已有方法的1/16。

关键词: 正则表达式, 状态膨胀, 状态分组, 局部搜索

Abstract:

Regular expression matching plays an important role in many network and security applications.DFA is the preferred representation to perform regular expression matching in high-speed network,because of its high and stable matching efficiency.However,DFA may experience state explosion,and thus consume huge memory space.As a classical solution for the problem of state explosion,i-DFA can reduce the memory consumption significantly and guarantee the worst matching performance at the same time.However,prior methods are inefficient in both time and space during the construction of i-DFA.An efficient i-DFA construction algorithm based on the idea of state grouping was proposed.Furthermore,a formal description for the problem of state grouping was given,and it was proved that it was NP-hard to get the best state grouping result.Thus,based on local search strategy,a near-optimal algorithm was introduced to divide states into different groups.Compared with the classical construction method,the significant improvement in both time and space is achieved; the i-DFA of the proposed method may have 2/3 states as that of prior method and the proposed i-DFA is constructed with only 1/16 time of it.

Key words: regular expression, state explosion, state grouping, local search

No Suggested Reading articles found!