高速网络线速深度分组检测关键技术研究

摘要

普通的分组检测仅仅检测分组的头部，深度分组检测（Deep Packet Inspection）有时也称为完全分组检测，属于应用语义级的检测。随着计算机网络的发展，网络的功能正逐步从简单的“浅层检测”到基于深度分组检测的复杂应用进行演化，甚至被认为是网络发展的最终目标，主要表现在三方面：对于网络服务提供商，DPI设备可以检测OSI参考模型的第二至第七层，从而使一系列新的网络功能成为可能；对于企业界，DPI已成为网络信息安全的核心理论与关键技术；对于政府部门，DPI作为管理信息传播的重要手段，可以实现网络敏感内容的调查、网络舆情分析与传播、网络流量监测与审查，对解决社会稳定安全，国民经济发展，乃至国防建设具有重大意义。
　　 基于深度分组检测的复杂应用程序关键性能影响因素可归结为检测模型与检测算法两方面，检测模型决定系统的稳定、高效、灵活、升级、扩展等性能；检测算法决定系统的检测速度，进而影响系统的准确性和有效性。本课题围绕深度分组检测的模型与算法进行了系统深入的研究，提出了高速网络环境下线速（On-line Speed）深度分组检测的有效模型与体系结构，给出了一系列高效的深度分组检测算法与实现方法，解决了高速网络深度分组检测“速度与性能”之间的矛盾。本研究工作取得了以下的主要创新性成果：
　　 （1）提出了基于可编程状态机（Programmable State Machine）的深度分组检测模型，该模型的核心思想是分离决策密集型处理，并提供灵活、非过程化的编程模型，解决了深度分组处理的稳定，高效，灵活，升级，扩展等问题。通过将决策与执行相分离，PSM能够在大量的信息需要被解析、且解析过程中信息的位置和大小事先不确定的情况下，使解析操作变得快速容易。同时该模型能够结合模式匹配算法或正则表达式（Regular Expression）搜索算法，将解析和搜索结合起来实现面向特征的多模式分类处理。给出了PSM模型的具体优化及实现方法，使得深度分组处理所使用的数据结构组织良好，所需存储空间小并且存储操作方便，达到了线速的深度分组处理。
　　 （2）提出了网络流乱序分组的深度检测的方法及相关算法，建立了乱序分组的数学分析模型，为乱序流的深度检测提供了理论基础。给出了在不丢弃，不缓冲乱序分组的条件下进行跨分组的深度检测DLmax原理。方法根据DLmax原理，以动态B+树索引分组边缘模式碎片，加快了乱序碎片的处理速度，同时以正则表达式作为模式语言，进一步减少了需要存贮的边缘模式碎片的长度，显著地降低了存储空间要求。在不丢弃、不缓冲乱序分组的、避免“协议落地”的同时，实现了按分组的物理到达顺序进行快速的跨分组深度检测。
　　 （3）分析了正则表达式作为模式描述语言的必然性，提出了快速正则表达式搜索算法Set-Wise-RE，该算法是一种基于启发因子的快速RE搜索算法，具有特征集大小感知的功能，且搜索速度快，可以实现正则表达式的快速搜索，解决了深度分组检测中的速度瓶颈问题。
　　 （4）提出了大规模RE集合的快速搜索算法，该算法利用Bloom filter集合查询时间与集合大小无关的特点，使得RE搜索速度不受模式集前缀集合大小的影响，如果采用多个Bloom filter并行，则搜索速度进一步加快，不但能够实现RE的快速搜索，而且对于大规模正则表达式集合，算法性能优势尤其明显，解决了大规模RE集合的快速搜索问题。
　　 （5）提出了线速深度分组检测的动态检测算法，解决了规则集的动态的更新问题。该算法基于加权计数型Bloom filter，可以执行O（1）时间复杂度的动态查询，显著提高了系统的吞吐量。同时，基于程序局部性原理，提出了额定长度前缀的方法，实现了对长规则的可扩展性。给出了动态高效的多模式匹配算法，实现线速的动态深度分组检测，同时极大的减少了硬件资源开销，提高了可扩展性。

目录

文摘

英文文摘

声明

第一章 绪论

1.1 课题研究背景、来源及选题意义

1.2 研究现状与存在的问题

1.2.1 基本概念

1.2.2 国内外研究现状

1.2.3 存在的问题与挑战

1.3 本文的主要研究内容与成果

1.4 本文的组织结构

第二章 基于PSM的深度分组检测模型

2.1 引言

2.2 基于PSM的深度分组检测模型

2.2.1 问题描述

2.2.2 PSM深度分组检测模型

2.2.3 模型的优化

2.3 模型的实现

2.4 性能分析与实验结果

2.5 小结

第三章 高速网络流的深度检测方法

3.1 引言

3.2 面向行为特征的流识别算法

3.3 乱序分组的数学建模与分析

3.4 乱序分组检测方法的原理

3.4.1 DLmax原理。

3.4.2 乱序分组检测的模式碎片处理方法

3.5 性能分析与实验结果

3.6 小结

第四章 线速深度分组检测的RE检测算法

4.1 引言

4.2 正则表达式与模式识别自动机

4.2.1 正则表达式

4.2.2 模式识别自动机

4.2.3 模式识别自动机的构造

4.3 启发式RE搜索算法Set-Wise-RE

4.3.1 启发式Set-Wise-RE基本思想

4.3.2 启发式Set-Wise-RE算法

4.3.3 性能分析与实验结果

4.4 基于Bloom filter的大规模RE集合搜索算法

4.4.1 最短路径Lmin与前缀集合

4.4.2 Bloom filter与RE集合搜索

4.4.3 性能分析与实验结果

4.5 小结

第五章 线速深度分组检测的动态检测算法

5.1 引言

5.2 双通道线速动态模式匹配

5.2.1 快速通道

5.2.2 慢速通道动态模式匹配算法

5.3 性能分析与实验结果

5.3.1 Weighted Counting Bloom filter参数设置

5.3.2 算法测试

5.3.3 系统吞吐量分析

5.4 小结

结论与展望

结论

展望

参考文献

附录A线速深度分组检测关键算法的源代码

攻读博士学位期间发表的与学位论文内容相关的学术论文

致 谢