【摘要】 正则表达式匹配在网络安全应用中发挥着重要的作用.确定有限自动机(deterministic finite automaton,DFA)具有高速稳健的性能,因而更适合于在骨干网络环境下执行正则表达式匹配.然而,DFA存在状态膨胀的问题.很多研究工作基于状态关系来解决DFA的状态膨胀问题.然而目前对如何获得状态间的关系仍然缺少一种时空高效的解决办法.提出了一个通过有限自动机(finite automaton,FA)的活跃状态集来准确计算状态关系的算法,并给出了一个高效的获取所有活跃状态集的方法.实验结果证明,该方法不仅能准确地得到状态关系,而且其空间占用和时间消耗仅是已有方法的1?256和15%左右.更多还原

【Abstract】 Regular expression matching plays an important role in many network security applications. DFA is preferred to perform regular expression matching in backbone networks because of its high and robust matching efficiency. However, it may experience the problem of state explosion. Some recent work try to address the problem based on the relation between states. However, there is still lack of a time-efficient and memory-efficient method to obtain exact relations between states. We give a new algorithm to achieve the goal by analyzing all active state sets of finite automata, and introduce a method to obtain the active state sets. Experimental results show that our work can obtain exact state relations with only 1/256 memory consumption and 15% time cost comparing with prior methods.更多还原