基于迁移边减少的DFA压缩算法

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于迁移边减少的DFA压缩算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

【摘要】现代网络入侵检测系统要在深度数据包检测中检测出危险的模式串，需要以线速度来匹配正则表达式。确定性有限状态机（deterministic finite automation， DFAs）能在线性时间内完成操作，但其需要非常庞大的存储空间，以至于难以实现。该文介绍了一种能减少状态之间迁移边存储空间的压缩算法，实验结果表明，该方法能使状态机的实际实现成为可能。

【关键词】网络入侵检测;确定性有限状态机;迁移边

引言

如何从海量数据中甄别出有害信息，对维护网络中数据的传输安全与稳定，对阻止和遏制潜在的危险行为，对促进互联网产业健康发展，均具有现实的重要意义。在这一需求背景下，以入侵检测＼保护系统为代表的网络安全保障设备应运而生。入侵检测系统负责对网络中的数据流进行实时监测，它的首要任务是在不中断网络的前提下对网络中的数据包的内容进行深度检测，尝试发现其中的不良信息与危险行为，因而需要一种正确而高效的数据内容检查策略――模式匹配算法。由于状态机的存储容量问题，使得一些模式匹配算法的实际性得不到保证。本文主要目的是为了介绍一种能减少状态之间迁移边存储空间的算法。

1.介绍

在文献一中提出了一种带延迟输入有限状态机（Delayed input DFA， D2FA）[2]，它在压缩DFA的存储量和状态之间的遍历数量进行折衷。在字符匹配操作中，对压缩DFA的遍历与传统Aho-Corasick算法[1]相同。

图1 正则表达式状态机

（字母表为{a，b，c，d，e}，所有到0的转移都被省略，红色表示状态深度）

首先，我们知道DFA的存储空间是关于状态数和状态之间迁移边的函数。而且，对于任意给定的正则表达式，一个有最少状态的DFA肯定能找到[3][6]，其时间复杂度为O（nlogn）。然后Kummar观察发现，DFA中的很多状态都有相同的迁移边。即不同状态在相同输入下转移到相同的目的状态。可以通过设置默认转移以消除这些冗余的迁移边，达到减少DFA的存储空间的目的。该算法可形式化为无向图中的最大生成树问题。可用Kruskal算法解决，其算法的复杂度为O（|E|log|V|）。（E为无向图中边的总数，V为顶点总数）

但在D2FA压缩算法中，它忽略了DFA遍历的方式，并只对不同状态的相同迁移边进行操作。我们可以利用一个简单的事实：DFA遍历总是从初始状态s0开始。然后引入一个概念“深度”，即对于DFA中的每个状态s，其深度是从初始状态s0转移到s状态之前，所需遍历的最少状态数。换句话说，初始状态s0的深度为0，由初始状态s0可直接到达的状态集S1的深度为1，而由状态集S1的状态直接到达的状态集S2（但s0不能直接到达）的深度为2。如此可推。DFA的深度信息如图1所示。该DFA是基于正则表达式：ab+c+，cd+和bd+e。

2.算法介绍

2.1 定理介绍

我们的算法是基于以下定理。

定理：如果在D2FA中，没有一个默认转移，是从深度为di的状态到深度为dj的状态（di≤dj），那么对于任意长度为N的字符串，其匹配最多需要2N次状态转移。

证明：对于每个输入的字符，都将会引起一次已标记的转移和零到多次的默认转移。假设，对于给定字符，从状态s转移必须经历k次默认转移。因为默认转移都是只指向深度更小的状态，所以状态s的深度必须大于k。要从初始状态到达状态s，必须至少有k次已标记的转移。因此，默认转移的数量至多比标记转移的数量小1。因为一个长度为N的字符串需要N个标记转移，所以总的状态遍历数量不可能高于2N-1。

2.2 问题形式化

我们的问题可以形式化为一个有向图中的最大生成树问题。为找出该问题的最优解，两个相似的算法已被Kruskal[4]提出。解决最大生成树问题基本上可分成两步;选择边和检测是否有循环。首先，每个顶点选择其最大权重的迁移边，并将其添加到容器E’中。如果E’中并不包含循环，则边集E’就是其最大生成树。否则，每个循环可视为一个伪节点，而且修改从改伪节点输出边的权重。然后从中选择出最大权重的边，并在E’中删除先前从其相同源节点输出的边。基本思想就是通过减小最小可能的权重来消除循环。注意到上述算法的复杂主要在于循环检测。幸运的是，在我们的问题中并不需要该部分。实际上，因为在匹配DFA中，所有默认转移总是指向深度减小的状态[5]，所以不会存在任何循环。因此，默认转移的任意子集也不包含循环。

2.3 算法实现

算法：整个问题可看成每个状态选择一个和自己具有最大数量的相同迁移边，前提是选择的状态深度需小于本状态。而且在平等情况下，深度越小的状态，优先级越高。这样可以限制默认转移路径的长度和增强遍历时状态的局部性。如果DFA遍历是广度优先遍历，那么默认状态转移和深度计算都可以在一次遍历中得出。伪代码中，queue是为了实现DFA的广度优先遍历。因为当状态s从队列中弹出时，所有深度比状态s小的状态都已处理完毕，所以每个状态将得到正确的深度值。这个问题还可以推广到使默认转移的尺度至少为k深度大小（k为正整数）。深度小于k的状态将没有默认状态转移。可以得出对长度为N的字符串，将至多需要执行N（k+1）/k的状态转移。算法的时间上界为O（n2），而原始的D2FA算法的时间上界为O（n2logn）。

3.实验结果分析

如图2所示，通过该算法得到状态机的状态转移数量显著减少，使得状态机的存储消耗也相应减少。

图2 压缩之后的状态机

（展示了所有的状态转移;默认转移被表示为虚线）

为了进一步测试该算法的性能。在PC机器上，CPU频率2.0GHz，内存2G，系统为red hat linux 6。在正则表达式处理软件的基础上，我们实现了该算法，并使用了实际中的规则集（比如Snort、Bro入侵检测系统和Cisco安全装置中的规则集）。

图3显示了使用我们的算法所获得的边数与D2FA压缩算法（默认边界参数为2）所获得的边数的比较。由图可以看出，我们的压缩算法在大多数情况下产生的状态转移数比D2FA压缩算法产生的边数少的多。

图3 我们的算法与D2FA之间转移数的比较

（snort后的数字为规则集的条数）

该算法阻止了同深度的默认状态转移以及消除了大量冗余的失效转移。而且由于该算法在默认转移的时候更倾向于选择深度更小的状态，使得状态机的遍历操作具有更好的局部性。

4.结束语

在论文中，我们在传统状态机压缩算法的基础上提出了一种新的压缩技术，使得dfa在实际中具有速度优势的同时，让其内存占用达到可以接受的水平。通过对比实验数据，得出该算法的压缩性能更好。而且在内存中存储该状态机时，为了充分利用其特性，还要将状态机进行编码存储[6]（比如：线性编码、位图编码等等）。

参考文献

[1]Aho A V，Corasick M J.Efficient string matching：an aid to bibliographic search[J].Communications of the ACM，1975：330-340.

[2]Kumar S，Dharmapurikar S，Yu Fang，et al.Algorithms to Accelerate Multiple Regular Expressions Matching for Deep Packet Inspection[C].in ACM SIGCOMM，Sept 2006.

[3]Hopcroft J E，Motwani R， Ullman J D，孙家X译.自动机理论、语言和计算导论（第三版）[M].北京：机械工业出版社，2008：37-48.

[4]J.B.Kruskal，On the shortest spanning subtree of a graph and the traveling salesman problem.Proc.of the American Mathematical Society，Vol.7，No.1.1956：48-50.

[5]Hopcroft J.Theory of Machines and Computation[M].New York：Academic，1971：189-196.

[6]Michela Becchi.A-DFA：A Time- and Space-Efficient DFA Compression Algorithm for Fast Regular Expression Evaluation.ACM Transactions on Architecture and Code Optimization，Vol.10，No.1.April 2013.

作者简介：钱勇（1991―），男，浙江温州人，硕士，研究方向：网络安全算法。