基于预定义类的紧凑型正则表达式匹配算法

针对目前硬件正则表达式匹配算法在存储空间以及吞吐量等方面面临的挑战，结合扩展有限自动机（XFA）正则表达式匹配算法，提出了一种预定义类的压缩自动机匹配算法（Pre-Class CFA）。通过预定义类，算法既可以实现正则表达式中类字符匹配，又能够通过优先级的设定匹配特殊字符集，并在XFA消除确定性有限状态机（DFA）状态爆炸问题的基础上进一步压缩了迁移边数目；同时算法根据现场可编程门阵列（FPGA）和迁移边的特征，设计了一种基于并联只读存储器（ROM）结构的迁移边存取方法，可以实现同一状态多条迁移边的并行读取和匹配。在中低性能FPGA平台ALTERA DE2-70上对算法进行测试，实验中系统吞吐量为1.3 Gb/s，可实现千兆网络下的入侵检测和垃圾过滤。

Predefined-class based algorithm for compact regular expression matching

For hardware regular expression matching algorithms are faced with the challenges in memory space and throughput, a Predefined-class Compact Finite Automaton (Pre-class CFA) matching algorithm based on Extended Finite Automaton (XFA) regular expression matching algorithm was proposed. By using the predefined classes, the algorithm not only can achieve class character matching in regular expression, but also can match the special character set by priority setting; besides, the migrating edges were reduced when eliminating the Deterministic Finite Automaton (DFA) state space exploration problem. At the same time, based on the characteristics of Field-Programmable Gate Array (FPGA) and migration edge, a migration edge access method based on parallel Read-Only Memory (ROM) was designed to realize the parallel reading and matching of the same state with mutiple migration edges. The algorithm was tested on ALTERA DE2-70 FPGA platform, which is a low-performance platform. The throughput of the experimental system is 1.30 Gb/s, which can realize intrusion detection and garbage filtering under gigabit network.