深度数据包检测（DeepPacketInspection，DPI）是现代网络入侵检测/防御系统（NetworkIntrusionDetectionandPreventionSystems，NIDS/NIPS）的核心。随着网络技术的发展和网络流量的迅猛增长，深度数据包检测技术面临着高性能的挑战，即如何满足线速的深度数据包检测和存储需求。深度数据包检测系统采用特征匹配算法进行高速的数据包负载过滤，特征匹配是计算机科学中经典问题，一般来说，确定性有限状态自动机（DeterministicFiniteAutomata，DFA）和非确定性有限状态自动机（Non-deterministicFiniteAutomata，NFA）是特征匹配算法最常用的结构，用于描述特征规则并与数据包负载进行匹配。DFA的匹配速度很快，但存在存储空间开销大的缺陷；NFA存储高效，但是匹配效率很低。因此，高性能特征匹配算法的主要研究内容在于如何设计时空高效的自动机算法。
　　按照特征规则的表达语言划分，特征匹配算法可分为字符串匹配算法和正则表达式匹配算法。最早出现的特征匹配算法都是字符串匹配算法，随着网络应用类型日益复杂，正则表达式具有更强表达能力和灵活性的特点，使其逐渐替代字符串来定义特征规则。但正则表达式复杂的语义也导致基于正则表达式的特征匹配算法面临新的挑战，例如DFA的存储空间爆炸问题和多字符的自动机结构实现问题等等。
　　本文将主要以时空开销为角度，讨论现代DPI系统面临的高性能挑战问题：
　　首先，针对确定性有限状态自动机（DFA）和非确定性有限状态自动机（NFA）分别在时间和空间方面的优势和劣势，以及现有基于字符串规则的特征匹配算法时空互换的折衷性矛盾，本文提出了一种基于多步长索引表的NFA（MSI-NFA）算法。通过我们的分析与观察，确定对真实网络流量的特征匹配具有低频匹配成功率和高频状态迁移率的特点，MSI-NFA算法的设计针对这些真实网络流量特点，使用多步长索引表高速过滤网络流量中大部分无效内容匹配，尽量使相对低速的NFA只匹配正确的网络流量数据块。实验结果表明：在低匹配成功率的网络流量环境中，MSI-NFA算法在NFA存储优势的基础上，拥有接近DFA的匹配效率，同时，与现有主要字符串特征匹配算法相比，MSI-NFA都具有明显的时间与空间优势。
　　其次，针对正则表达式的固定步长分割难题，我们提出了一种扩展的正则表达式分割方法，该方法扩展了正则表达式语义并且实现了正则表达式的多字符分割，这是建立正则表达式的多步长索引表和基于正则表达式的多步长特征匹配算法的基础。在实现了扩展正则表达式的多步长分割基础上，我们设计实现了正则表达式的多步长索引表和扩展的NFA算法（XNFA）。考虑到原MSI-NFA算法在大规模规则集下可伸缩性差的问题，我们改进了多步长索引表和MSI-XNFA的联合匹配机制，在不付出额外存储代价来提高索引步长的情况下，提高MSI-XNFA算法的可伸缩性。实验结果表明：改进的两步长索引的MSI-XNFA算法的过滤性能要优于三步长的MSI-NFA算法，且支持正则表达式规则库。
　　最后，针对传统特征匹配算法单字符匹配模式的性能瓶颈问题，并考虑到现有多字符特征匹配算法都是基于精确字符串规则，本文提出了一种基于正则表达式的多步长DFA算法，包括多步长正则表达式DFA的构建和迁移表的压缩。我们设计了迁移边融合算法（TransitionMergingAlgorithm，TMA）来将单步长的DFA转化为任意多步长的DFA。此外，本文针对多步长DFA指数级的存储开销增长问题，提出了一种分别融合冗余状态和输入标识的迁移表压缩算法，减少多步长DFA的存储空间开销。实验结果表明：相比原始DFA，4步长DFA能够具有69.9%的吞吐量加速比，且减少了65.1%的匹配时间开销；迁移表压缩算法能够减少两步长DFA迁移表中2.1%-37.9%的状态和51.3%-87.2%的迁移边，整体存储空间减少了52.3%-92.1%。