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

Filter FA: a multiple string matching algorithm based on specification of character set

作　　者：张萍[1,2,3] 何慧敏 张春燕[1,3] 曹聪[1,3] 刘燕兵[1,3] 谭建龙[1,3] ZHANG Ping, HE Hui-min ZHANG Chun-yan CAO Cong LIU Yan-bing TAN Jian-long(Institute of Information Engineering, Chinese Academy of Sciences, B eijing 100093, China University of Chinese Academy of Sciences, Beijing 100049, China National Engineering Laboratory for Information Security Technologies, Beijing 100093, China China Mobile （Shenzhen） Co., Ltd., Shenzhen 518031, China)

机构地区：[1]中国科学院信息工程研究所,北京100093 [2]中国科学院大学,北京100049 [3]信息内容安全技术国家工程实验室,北京100093 [4]中国移动(深圳)有限公司,深圳518031

出　　处：《通信学报》2016年第12期103-114,共12页Journal on Communications

基　　金：中国科学院战略性科技先导专项基金资助项目(No.XDA06031000);新疆自治区科技专项基金资助项目(No.201230123)~~

摘　　要：多模式串匹配技术是入侵检测系统的核心技术之一,Aho-Corasick算法广泛应用于其中。针对AC自动机内存开销巨大影响算法性能的问题,提出一种基于字符集规约的改进算法——FilterFA。利用字符集映射函数将原字符集压缩为多个像字符集,针对像字符集构造新的自动机FilterFA,将空间复杂度降至O(P|Σ′|)。在随机数据集和真实数据集ClamAV上的测试结果表明,当像字符集大小为8,且保证误识别率小于2%时,FilterFA算法消耗的存储空间仅为AC算法的3%左右。Multiple string matching is one of the core techniques of intrusion detection system, where Aho-Corasick algorithm is widely used. To solve the problem that huge storage overhead of AC would influence performance deeply, an improved algorithm ——Filter FA, based on specification of character set was proposed. This algorithm compressed large character by the character set mapping function, and constructed a new automata based on the mapped character set,then space complexity decreased to O（ P｜Σ′｜）. Experiments on synthetic datasets and real-world datasets（such as Clam AV） show that the storage overhead of Filter FA is only about 3% of that of AC, while the size of the character set is 8, and the false recognition rate is less than 2%.

关 键 词：入侵检测 多模式串匹配 字符集规约 字符集映射 

分 类 号：TN925[电子电信—通信与信息系统]