一种节约空间的AC算法与国产化平台实现

AC算法作为多模式匹配算法的一种,在入侵检测、内容过滤防火墙、病毒检测等场景中得到了广泛的应用。AC算法的性能不仅受限于算法本身,还与算法运行的平台相关。使用普通的CPU进行模式匹配,只能达到300 Mbps左右的吞吐率,而使用FPGA进行匹配,吞吐率可以达到1 Gbps以上。但是FPGA的存储容量有限,可以匹配的模式个数受限。本文提出了一种节约空间的AC算法,设计了适用于FPGA存储的状态转移表,降低了AC算法需要的存储空间大小,同时在匹配过程中不带来额外的运算开销,尤其适用于内容过滤防火墙等对实时性要求较高的应用。

Implementation of A Space-saving AC Algorithm and Domestication

As one of multi-pattern matching algorithms,AC algorithm has been widely used in the fields of intrusion detection,content filtering firewall,and virus detection.The performance of the AC algorithm is limited by both the algorithm itself and operation platform.We can only achieve throughput rate of 300 Mbps by using normal CPU,but achieve more than 1 Gbps throughput rate by using FPGA.However,the storage space of FPGA limits the number of patterns which can be matched.In this paper,a space saving AC algorithm is proposed,and a state transition table suitable for FPGA storage is designed,which reduces the storage space required by AC algorithm,and does not bring additional operation cost in the matching process.The space-saving AC algorithm is especially suitable for scenarios with high real-time requirements.