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

作者：张萍; 何慧敏; 张春燕; 曹聪; 刘燕兵; 谭建龙

来源：通信学报, 2016, 37(12): 103-114.

DOI：10.11959/j.issn.1000-436x.2016277

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

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

• 单位
  中国科学院大学; 中国科学院信息工程研究所