张萍，何慧敏，张春燕，曹聪，刘燕兵，谭建龙

(1.中国科学院信息工程研究所，北京 100093；2.中国科学院大学，北京 100049；3.信息内容安全技术国家工程实验室，北京 100093；4.中国移动（深圳）有限公司，深圳 518031)

FilterFA：一种基于字符集规约的模式串匹配算法

张萍1,2,3，何慧敏4，张春燕1,3，曹聪1,3，刘燕兵1,3，谭建龙1,3

(1.中国科学院信息工程研究所，北京 100093；2.中国科学院大学，北京 100049；3.信息内容安全技术国家工程实验室，北京 100093；4.中国移动（深圳）有限公司，深圳 518031)

多模式串匹配技术是入侵检测系统的核心技术之一，Aho-Corasick算法广泛应用于其中。针对AC自动机内存开销巨大影响算法性能的问题，提出一种基于字符集规约的改进算法——FilterFA。利用字符集映射函数将原字符集压缩为多个像字符集，针对像字符集构造新的自动机FilterFA，将空间复杂度降至。在随机数据集和真实数据集ClamAV上的测试结果表明，当像字符集大小为8，且保证误识别率小于2%时，FilterFA算法消耗的存储空间仅为AC算法的3%左右。

入侵检测；多模式串匹配；字符集规约；字符集映射

1 引言

字符串匹配问题是网络入侵检测系统的核心技术之一，在近几十年的发展中研究非常广泛。它广泛应用于信息安全、文本检索和计算生物学等领域。著名的入侵检测系统 Snort[1]包含多种规则匹配算法，如Boyer-Moore(BM)[2]、Wu-Manber(WM)[3]和Aho-Corasick (简称AC)[4]算法。其中，BM算法适合单模式串匹配问题，AC算法和WM算法适用于多模式串匹配。

自20世纪70年代以来，字符串匹配技术有着显著的发展，国内外多位研究者相继提出了上百种模式串匹配算法。根据其搜索方式的差异性，Gonalo Navarro和Mathieu Raffinot[5]将字符串匹配算法分为3类：基于前缀的模式串匹配算法、基于后缀的模式串匹配算法和基于子串搜索的模式串匹配算法。……