论文部分内容阅读
随着互联网逐步发展成为综合性业务运营平台，新型应用不断涌现，信息容量稳步增长，网络接口速率快速提升。作为网络安全和精细化运营、管理的重要支撑，报文检测技术在匹配速率、资源占用等方面面临严峻挑战。为解决以上问题，正则表达式匹配技术成为现代网络关注和研究的热点。本文以提升正则表达式匹配速率为目标，按照理论分析、算法设计、平台验证的思路，对正则表达式匹配算法进行了研究。主要内容包括三个方面：提升正则表达式匹配速率、降低内存占用以及支持并发数据流的匹配。为提升正则表达式匹配速率，从自动机基础理论出发，分析了单周期多字符匹配结构的特性，并针对其存在的问题，提出一种单周期处理多字符的正则表达式匹配算法MC-DFA。通过合并标准DFA结构中的单字符状态转移，MC-DFA算法可以在单周期内处理多个字符，达到提升匹配速率的目标；为降低多字符处理引入的存储冗余，MC-DFA针对性的设计了状态转移表深度压缩算法，使得内存占用增长较小。MC-DFA算法在FPGA平台上达到了6.7Gbps的吞吐率。为降低DFA结构的内存占用，通过分析NFA转化为DFA时的状态指数增长现象，设计了基于状态约束的混合自动机结构SC-HFA。SC-HFA将NFA的状态集合按照约束关系分组，将可能引发指数增长现象的状态置于不同的组中，形成NFA和DFA共存的混合结构，有效的抑制了状态数的增长，减少了内存使用。与标准DFA相比，SC-HFA能够减少约75%的状态数。针对实际网络中数据流并发出现的情况，提出一种基于时分复用的并发数据流匹配方案VLSM-HFA。VLSM-HFA通过存储功能保存和恢复匹配状态，实现了对多数据流的支持；通过综合MC-DFA高速处理和SC-HFA内存占用小的特点，实现了高性能的正则表达式匹配。同时，为保证数据流切换的性能并兼顾数据流的公平性和差异性，MC-DFA设计了快速变长切换机制。平台验证部分，3386条规则下，VLSM-HFA方案在FPGA平台中，最多可支持131条并发数据流，吞吐率可达到9.6Gbps。综上所述，本文在理论分析的基础上，从算法实现和平台验证两个方面对正则表达式匹配技术进行了归纳和创新。理论分析为算法的设计提供了研究基础和方向，基于FPGA的部署检验了理论和算法的正确性，并为相关系统的设计提供了一定的参考依据。