一种快速高效的模式匹配算法的应用研究

提出一种高性能的模式匹配算法——MAC算法,它通过使用从确定性有限状态机(DFA)中得到的特征等同态,在保证高速匹配的前提下,极大地减少了内存需求。同时,该算法具有高度的灵活性,即通过调整就可以适应不同的特定性能和资源限制的要求。在软件使用环境中的实验结果表明,MAC算法的内存使用性能相对目前先进的模式匹配算法提高了1.51～2.40倍。

基于模板有限自动机的正则表达式匹配算法

采用规则分组的办法解决DFA状态爆炸问题,随着规则数目的增加,空间压缩效率大大降低。针对此问题提出了模板有限自动机分组算法。该算法基于规则模板对规则集进行分组,各分组分别构建匹配引擎;同时,根据实际规则数目和系统结构改变规则子集的数目,达到更好的匹配效率。理论分析和实验表明,与传统分组算法相比,在存储空间压缩相当情况下,分组数目大大减少;与其他典型的DFA改进算法相比,预处理时间和存储空间有数量级别的缩减,且匹配速率没有明显降低。

确定型格值有限自动机的最小化

给出了确定型格值有限自动机的定义,并同时给出了有效终止状态和可达到状态的定义。指出了求取DLFAM=(Q,Σ,δ,q0,σ)的实质是求取Q/Rk。由此以可到达状态为基础引入了等价关系Rk、Sk与商集Q/Sk,证明了Rk=Rk-1∩Sk,由此得到Q/Rk的等价类为Q/Rk-1中等价类与Q/Sk中等价类的非空交集全体。引入了Hk,并证明了可由Hk求取Q/Sk,从而得到仅利用集合运算便可求取Q/Rk的算法,最终给出了DLFA最小化算法的一个容易实现的构造型描述和相应示例。

基于子集构造法的优化的NFA确定化算法

使用子集构造法对非确定有限自动机进行确定化的过程中存在大量重复计算的问题。为解决此问题,基于非确定有限自动机的特点并针对子集构造法的不足,提出了一种优化的非确定有限自动机确定化算法。首先定义了识别符的有效引出状态集概念并证明了ε-closure的并定理以保证算法的正确性,其次给出了用于避免重复计算的识别符的有效引出状态集的构造子算法和单状态集的ε-closure的求算子算法,基于这两个子算法给出了优化的非确定有限自动机确定化算法,最后将算法应用于实例,实验结果表明计算量远小于子集构造法的计算量。相比子集构造法,算法能更有效地对非确定有限自动机进行确定化。

DFA化简算法的一种改进方法

在深入研究DFA化简基本原理的基础上,首先给出现有分析算法(分割法)的形式化算法描述,然后证明了该算法存在着漏洞,并给出相应的解决方法。最后,借鉴时序逻辑门电路中原始状态表化简的方法,对现有分割算法进行修改,提出一种新的适用于任何DFA的化简算法——K次划分法。

基于簇聚类和游程编码的正则表达式压缩算法

基于簇聚类的确定型有穷自动机(DFA)压缩算法,即ClusterFA算法,解决了正则表达式匹配中的空间爆炸问题,但该算法的分组个数取理想值较为困难,且其类中心向量表的每一行中连续重复转移状态出现频率较高。针对该问题,提出一种改善ClusterFA算法的方案En_ClusterFA。提取类中心向量表行与行之间相同的首尾部分,并对其进行游程编码以建立索引表,对类中心向量表余下部分的转移状态进行游程编码。利用该方案对Bro,Snort和L7-filter规则集进行测试,实验结果表明,除了L7_2和L7_6规则集的压缩率分别提高到96.1%和98.1%之外,其他规则集的压缩率都提高到99%以上。与ClusterFA算法的压缩率相比,En_ClusterFA平均提高了4%,证明En_ClusterFA能够有效地提高DFA的压缩效率。

细粒度网络流量分类架构及其优化

针对现有网络流量指纹自动生成难度大、粒度粗及匹配阶段内存消耗大等问题,提出了细粒度网络流量分类架构及其优化。在线下,根据特定字符片段在对应流量中保持不变,且代表流量功能的有效字符片段比随机噪声片段出现的频率高这一特性,寻找流量中字符片段出现频率和长度达到一定阈值的有效片段,并将其作为备选指纹规则,通过交并、合并、指纹提纯操作获取该流量对应的指纹。在线上字符串匹配时,根据k均值分类思想重新定义距离,并利用异构位分割状态机的启发式算法对指纹中的字符串进行重新组织,对内存使用进行优化。实验结果表明:所提算法能够在未知网络流量协议格式的情况下自动生成细粒度的流量指纹,平均识别准确率为93.65%,对噪声不敏感;在匹配时若将原所有指纹字符片段重新优化组织,当指纹规则数量在4000以上时,可节约近50%的内存需求。

确定型有限自动机生成最短正则表达式的启发式算法研究

从确定型有限自动机生成简短的正则表达式是计算机理论研究的基础问题之一,经典生成方法对状态排序方式比较敏感,不能保证表达式的生成质量。为了找到最优状态序列,基于状态消减法,提出了一种向前预测的改进权重法。该算法利用权重函数分析消减状态前和消减状态后自动机字符总量的变化,并结合并行消减状态策略,以及连续消减多个状态的向前预测策略,从而确定状态序列。通过实验将改进权重法与现有的启发式搜索算法进行对比,结果显示该算法所生成最优正则表达式的正确率高于其他算法。