深度包检测中DFA的存储压缩算法

发布时间：2019-08-26 20:15

【摘要】：网络入侵检测在信息安全中占据着重要的地位，而深度包检测(DPI, DeepPacket Inspection)是基于规则匹配的网络入侵检测系统实现的重要方法。目前正则表达式被广泛用于描述DPI中的各种攻击特征规则，用确定的有限状态机（DFA）来实现正则表达式代表的特征规则的匹配。但这样做的问题是DFA的存储空间大，难以适应规模日益增长的特征规则集。本文试图从状态数与状态转移数两个角度压缩DFA的存储空间。首先，，针对DFA中状态数庞大的问题，通过对带长度限制的正则表达式对应的DFA添加计数器，使得正则表达式的构造复杂度与长度限制无关。其中对三类带长度限制的正则表达式，分别给出了对应的带计数器DFA的构造及匹配方法。其次，在状态数目不变的前提下，对DFA中状态转移数进行压缩。一方面从压缩字母表的角度对字符映射表进行改进，对状态转移表中列相同的字符在字符映射表中直接映射到目的状态，进一步压缩了字母表规模。另一方面根据添加默认状态转移的思想提出了BiD2FA算法，其在WD2FA算法基础上添加一种比WD2FA取代更多状态转移的默认状态转移，并直接转向匹配到的下一状态。通过对BiD2FA算法以及字母表压缩与WD2FA结合的压缩方法进行实验，结果表明状态转移数目都减少为原来的1%以下。
【图文】：

正则表达式,长度限制,大小分布

startB3D2Cendnot CC,counter2--not C and D,counter2=counter2-2failurecounter2<0 counter2<01counter1=j图 3.12 ^B+[^\n]{3}CD 对应的带两个计数器的 DFA3.3 实验分析本节实验采用了在密苏里大学副教授 Michela Becchi 提供的正则表达式转有动机的开源源代码（网址 http://regex.wustl.edu/index.php/Main_Page），其代用 C++语言编写，我们在 visual studio 2010 开发环境通过对其改写进行 DFA算法实现和实验。

无向图,状态转移,算法,转移长度

可能多转移信息的默认状态转移。此外还需满足以下两个限制条件：1）默认状态转移构成的状态转移图中不能含有回路，否则会产生死循环。并不是每个状态都存在一条到其它状态的默认状态转移，在状态转移图中，状态转移边构成一棵树或者森林，每棵树中的根结点不存在到其它状态的默态转移。由于构造树要比构造森林的压缩效果要好一些，求取具有最大压缩默认状态转移就转化为了求取一个无向图中最大带权生成树的问题。2）要限制默认状态转移构成的树的最大深度(称为默认转移长度)。假设状态为 n，则最坏条件下最大带权生成树的默认转移长度为 O(n)，即存在某个状某些字符的激励下，对应的需要跳转 n 次才能跳转到目的状态。而 DFA 处理字符的时间复杂度为 O(1)，用最大带权生成树算法得到的状态转移虽然能得大的压缩率，但匹配效率却得不到保证。所以需要对默认转移长度进行限制。因此根据以上三条限制，D2FA 及 WD2FA 算法通过构建一棵默认转移长度不限制的最大带权生成树[19]，为状态构建默认状态转移。图 4.3 为通过 WD2FA构造的^B+.{3}D 对应的默认状态转移树的示例，其中实线代表默认状态转虚线代表非默认的状态转移，实线边上的数字是默认状态转移的权值。
【学位授予单位】：西安电子科技大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP393.08

【参考文献】