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

• 作者: 何慧敏 刘燕兵 张春燕 张萍 曹聪 谭建龙
• 来源期刊: 通信学报
• 学科: 工学
• 关键词: 入侵检测 多模式串匹配 字符集规约 字符集映射
• 年，卷（期）: 2016,（12）
• 所属期刊栏目: 学术论文
• 页码范围: 103-114
• 页数: 12页
• 分类号: TN925
• 字数: 10254字
• 语种: 中文
• DOI: 10.11959/j.issn.1000-436x.2016277

摘要

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