面向存储优化的高速特征匹配算法研究

作     者：杜文超 

作者单位：解放军信息工程大学 

学位级别：硕士

导师姓名：陈庶樵

授予年度：2012年

学科分类：0839[工学-网络空间安全] 08[工学] 

主      题：深度包检测 模式匹配 正则表达式匹配 有限自动机 集合切分 

摘      要：随着互联网传输带宽的不断提高与其所承载的业务日趋多元化，网络管控设备面临着大容量规则存储的需求，如何在保障系统性能的基础上实现存储优化是本课题研究面临的一个问题。传统特征匹配算法以较高的存储空间消耗为代价换取高匹配速率，导致其支持的规则数有限，难以满足高速网络中大规模特征集匹配的需求。论文结合国家863计划课题“面向三网融合的统一安全管控网络，在对典型的特征匹配算法进行分析与总结的基础上，并从高速网络中如何实现大容量特征匹配的角度出发，先后研究了两种规则描述形式——普通模式串特征和正则表达式特征的相关匹配算法及其工程实现。本文主要工作如下： 详细分析了典型的特征匹配算法的基本原理，从算法的时间、空间复杂度、工程实现难易程度等指标对其进行了全面的分析和比较，指出了各种特征匹配算法的优势和存在的问题，为算法进行存储优化和实现指明了方向。 针对传统的基于TCAM的模式匹配算法无法支持大容量了特征匹配的问题，提出了一种基于双重状态编码的高效模式匹配算法DSC-PM (Efficient Pattern MatchingAlgorithm Based on Dual State Coding)。该算法充分利用NFA空间复杂度低与TCAM高速查表能力的优势，采用关键字预过滤加速处理效率，并通过构造失败转移树后对状态进行编码，消除了大量的失败转移，提升了算法支持的规则容量。理论分析和实验仿真表明：该算法不仅大大降低了存储空间消耗，还保持了较高的匹配速率，且算法具有良好的可扩展性。 针对高速网络中基于DFA的正则表达式匹配存在的状态空间膨胀问题，提出了一种基于m-HFA的高效正则表达式匹配算法M-REM(Regular Expression MatchingAlgorithm Based on m-HFA)。算法深入分析了两种有限自动机的关系，采用启发式方法将NFA的激活状态组合切分为可用m个状态表示的子集，构建特殊状态机m-HFA完成匹配。理论分析和仿真结果表明，该算法有效解决了正则表达式匹配存在的状态空间膨胀问题，能够实现大规模的正则表达式匹配，并且保证了最坏情况下的性能。 结合项目需求，提出了一种适合高速网络条件下的特征匹配引擎实现方案。该引擎采用软硬件协同，控制平面与数据平面分离的系统架构，增强了系统的灵活性和可扩展性，可同时支持普通模式串特征与正则表达式特征线速检测，并详细描述了TCAM与SRAM表项结构、状态存储结构及硬件匹配结构，最后通过性能分析和测试验证了该方案的可行性和有效性。