中文摘要：

深度包检测（DPI）是网络入侵检测/防御系统、防病毒系统等安全应用的核心功能模块。字符串/正则表达式匹配算法是其关键技术。由于攻击的日益复杂以及网络速度的不断提高，现有方法暴露出性能不足，空间爆炸等问题。因此有必要对高性能、可扩展性好的匹配算法展开更深入的研究。本项目首先建立图形处理单元上的基于比特并行的非确定性自动机模型，由此实现在空间和时间两方面都高效的多正则表达式匹配。其次，引入快速傅里叶变换及比特并行等非标准模式匹配技术，提出不同于有限状态自动机的新型正则表达式匹配方法，提高匹配算法的内存带宽、避免空间爆炸。另外，首次从检测和响应的角度研究针对DPI的算法复杂攻击。最后，基于上述结果实现一个能抵抗算法攻击的高性能入侵检测(预防)系统原型并对其进行评价。

结论摘要：

深入到网络包应用层载荷的检查和处理被称为深度包检测(DPI)。DPI是网络入侵检测系统、防病毒系统等安全应用的核心模块。DPI需要较大的处理开销和空间占用，提高性能一直是DPI研究的关键问题。随着网络速度的提高，研究高性能DPI算法具有重要的意义。本项目以DPI系统中的高性能模式匹配算法与数据结构为中心开展了如下几方面的研究。项目针对正则表达式匹配空间占用大的问题，提出了基于最小完美哈希函数和比特并行Glushkov自动机的混合状态转移方法。实现了低空间高性能的正则表达式匹配。将现有方法的O(m2^m)比特空间复杂降低到O(m2^k)比特，状态转移时间复杂为O(m/w)(m为正则表达式长度，k为其中的字符串数量，w为机器字长)。其次，为了降低多模式匹配的空间占用，引入了紧凑数据结构技术构造Aho-Corasick自动机。降低了空间占用，将状态转移的时间复杂从O(logσ)降低到O(loglogσ)和O(1)(σ为字母表长度)，还实现了时间和空间的调节。另外，提出了确定性有限状态自动机（DFA）的通用优化方法。仅增加很少的空间，实现了时间复杂为 O(loglogσ) 的状态转移函数。提出了实现DFA的重叠状态转移表方法，在保持O(1)时间状态转移的同时降低了空间占用。项目首次研究了针对紧凑输入的卷积算法。利用输入的紧凑存储特征，基于机器指令的比特并行性来加速卷积运算。提出了两种快速卷积算法，均具有优于现有方法的时间复杂度。基于新型卷积算法实现了带通配符的模式匹配算法，新算法的时间复杂优于现有算法。实际测试表明算法具有较高的性能。由于离散卷积的通用性，此工作为高效算法设计与实现提供了有力工具。项目提出一种对算法复杂攻击免疫的压缩数据内容检测算法，无需解压即可在压缩数据中进行模式搜索。新算法的贡献在于处理开销与输入内容无关，实现了对算法复杂攻击的免疫。本项目研究了收集DPI负载信息的图搜索算法，可用于算法复杂攻击的检测。提出了基于标记的一般图搜索算法，支持标记数量的调节。移动代理无需掌握系统信息就可在标记引导下以极小开销实现图搜索。项目在GPU和CPU平台上实现了项目提出的新算法，并开发了一个用于DPI的软件库和测试系统。针对GPU平台的特征，改进并实现了部分项目提出的技术。