当前,越来越多的网络应用需要依赖深度报文检测技术对报文进行识别,如协议识别、入侵检测、基于应用的带宽管理等。深度报文检测用预定义的特征集对报文的负载进行匹配,以判断负载部分是否符合规则集中的某条特征。正则表达式以其强大而灵活的表达能力而广泛应用于深度报文检测中的特征描述。正则表达式的匹配通常需要借助自动机来实现,而当前网络应用中特征集的规模不断增加,这给自动机的编译、配置及性能带来极大的挑战。另一方面,骨干链路网络速率的提升也对报文检测的性能提出了更高的要求。针对这些挑战,本文从正则表达式匹配的硬件体系结构、分组算法、自动机设计三个方面展开研究。论文首先对正则表达式匹配技术进行总结,从应用背景、技术原理、软件解决方案和硬件解决方案四个方面展开。结合一款实用的混合自动机,设计了一个新型的以存储为中心的FPGA+Multi-core的混合体系结构。对正则表达式分组算法进行建模分析,设计了一种高效的分组算法及相应的优化算法。从自动机状态爆炸的根源入手,设计了一个新型自动机Offset-FA,以解决状态爆炸问题,并且在存储开销和匹配效率上取得较好的平衡。本文的主要创新点包括:1)本文对深度报文检测中的正则表达式匹配技术进行了系统的综述。首先介绍了深度报文检测的应用背景及常见的深度报文检测方法。随后,介绍了正则表达式匹配的技术背景,指出状态爆炸是正则表达式匹配面临的主要挑战。从规则特征和状态的语义关系两个方面讨论了状态爆炸的成因。将当前的正则表达式匹配的解决方案粗略分为自动机优化的软件方法和并行加速的硬件方法,同时分别对两类方法进行深入的细分。自动机的优化主要分为自动机的压缩和可扩展自动机两类,可扩展自动机按解决状态爆炸的方法又可以分为规则分组、半确定自动机、附加标记及指令的自动机。并行加速主要基于以下平台:FPGA、GPU、通用多核CPU、TCAM。文章分别给出各类软件解决方案和各类硬件解决方案的详细对比。最后,基于以上对比分析,对构建高效的深度报文检测系统给出具体的指导建议。2)Hybrid-FA[1]是一款实用性较强的自动机,在工业界的产品中也有所体现。但是混合自动机面临着头部自动机过大、尾部自动机处理效率低的问题。头部自动机过大导致其无法配置在小容量的高速片上存储器中,尾部自动机处理效率低会严重影响整体的匹配性能。本文提出了一种以存储为中心的FPGA+Multi-core的混合体系结构。该结构的匹配引擎由两部分构成,即FPGA上的硬件匹配引擎和多核处理器上的软件匹配引擎。硬件引擎和软件引擎以流水的方式协同工作,报文负载先交给硬件引擎处理,当尾部自动机状态被激活时再将剩余的负载交给软件引擎处理。流水的方式可以独立出尾部自动机的处理,避免其对整体性能的影响。另一方面硬件引擎采用FPGA片上RAM加片外DDR3 SDRAM的两级存储形式,将高频访问的头部自动机状态配置在片上RAM上,以实现硬件引擎部分的高速匹配。仿真实验表明,hybrid-FA可以在FPGA+Multi-core的混合匹配架构上实现高速匹配。3)规则分组是有效避免状态爆炸的一种方法,当前通用的分组算法无法同时兼顾分组时间开销和分组结果。经过分析,规则分组问题可以归纳为图的最大k割问题。本文探索了模拟退火算法、遗传算法在规则分组问题中的适用性。同时,提出一种简洁高效的贪婪算法OSG算法以及相应的优化算法HI算法。实验结果表明,OSG算法在取得与当前最优分组结果可比的分组效果的前提下,大幅降低分组时间开销。4)为从根源上解决状态爆炸问题,本文从规则的特点入手,指出带闭包或重复限定的大字符集是导致状态爆炸的主要原因,提出一种新型的自动机Offset-FA来解决状态爆炸问题。根据这类特征出现的位置将原始的规则切割成多个片段,然后将这些片段编译成一个确定性有限状态自动机,另外用一个片段关系表和一个复位表来记录片段之间的关系,以维持与原规则集的语义等价性。去除这类特征后,自动机的状态爆炸得到了有效的解决。另外我们对Offset-FA的编译算法及匹配算法进行了一系列优化,以尽量减少这些片段被匹配上的频率及片段匹配上时需要的校验工作。实验结果表明,Offset-FA在自动机空间开销和匹配效率上取得了较好的平衡,在有效地解决状态爆炸问题的同时能够取得优于当前研究的匹配效率。