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

发布时间：2017-12-04 11:16

  本文关键词：FilterFA:一种基于字符集规约的模式串匹配算法

  更多相关文章： 入侵检测 多模式串匹配 字符集规约 字符集映射

【摘要】：多模式串匹配技术是入侵检测系统的核心技术之一,Aho-Corasick算法广泛应用于其中。针对AC自动机内存开销巨大影响算法性能的问题,提出一种基于字符集规约的改进算法——FilterFA。利用字符集映射函数将原字符集压缩为多个像字符集,针对像字符集构造新的自动机FilterFA,将空间复杂度降至O(P|Σ′|)。在随机数据集和真实数据集ClamAV上的测试结果表明,当像字符集大小为8,且保证误识别率小于2%时,FilterFA算法消耗的存储空间仅为AC算法的3%左右。
【作者单位】： 中国科学院信息工程研究所;中国科学院大学;信息内容安全技术国家工程实验室;中国移动(深圳)有限公司;
【基金】：中国科学院战略性科技先导专项基金资助项目(No.XDA06031000) 新疆自治区科技专项基金资助项目(No.201230123)~~
【分类号】：TP391.1
【正文快照】： 1引言字符串匹配问题是网络入侵检测系统的核心技术之一,在近几十年的发展中研究非常广泛。它广泛应用于信息安全、文本检索和计算生物学等领域。著名的入侵检测系统Snort[1]包含多种规则匹配算法,如Boyer-Moore(BM)[2]、Wu-Manber(WM)[3]和Aho-Corasick(简称AC)[4]算法。其中，

本文编号：1250810