麦涛涛，潘晓中，王亚奇

(武警工程大学 电子技术系网络与信息安全武警部队重点实验室，陕西 西安710086)

基于FPGA的XFA约束重复检测匹配*

麦涛涛，潘晓中，王亚奇

(武警工程大学 电子技术系网络与信息安全武警部队重点实验室，陕西 西安710086)

针对目前正则表达式匹配中约束重复问题所带来的空间消耗爆炸以及失配等问题，基于FPGA设计了一种硬件约束重复检测匹配模块，该模块与基于并联ROM的XFA匹配模块相结合，可以快速实现约束重复的检测和匹配。通过定义约束重复参数存储器，计数模块仅消耗少量的硬件资源即可实现约束重复的检测匹配。实验中计数模块可实现Gbps的吞吐量，同时使正则表示式规则存储空间压缩50%以上。

约束重复；FPGA；并联ROM

0　引言

正则表达式使用标准的语法规则来描述模式，与精确字符串相比，正则表达式可以描述复杂的字符序列，并降低空间复杂度。强大的表达能力使正则表达式在网络安全领域广泛应用，成为描述规则的主要工具[1]，目前主流的入侵检测/防御系统(NIDS/NIPS)，例如 Snort[2]、ClamAV[3]等已经将基于正则表达式的规则集成到其过滤系统中，且所占比重逐渐增大。

有限状态机（FA）和正则表达式所描述的语言都是正则语言，因此有限状态机是实现正则表达式匹配的主要方法。有限状态机通常分为两种：确定性有限状态机(DFA)和非确定性有限状态机(NFA)，通过对两种状态机深入而细致的研究和分析，Washington University的Kumar和Becchi等人提出了D2FA[4]、混合自动机(Hy brid-FA)[5]以及XFA[6]等方法来实现大规模正则表达式的实用化[7]。……