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

doi:10.11959/j.issn.1000-436x.2016277

摘要/Abstract

摘要：

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

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

Abstract:

Multiple string matching is one of the core techniques of intrusion detection system, where Aho-Corasick al-gorithm is widely used. To solve the problem that huge storage overhead of AC would influence performance deeply, an improved algorithm ——FilterFA, 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 ClamAV) show that the storage overhead of FilterFA 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%.

Key words: intrusion detection, multiple string matching, specification of character set, character set mapping

张萍,何慧敏,张春燕,曹聪,刘燕兵,谭建龙. FilterFA：一种基于字符集规约的模式串匹配算法[J]. 通信学报, 2016, 37(12): 103-114.

Ping ZHANG,Hui-min HE,Chun-yan ZHANG,Cong CAO,Yan-bing LIU,Jian-long TAN. FilterFA: a multiple string matching algorithm based on specification of character set[J]. Journal on Communications, 2016, 37(12): 103-114.

图/表 14

图1

图2

图3

表1

图4

图5

表2

图6

表3

图7

表4

表5

表6

表7

参考文献 21

[1]	Snort.Org[EB/OL]. .
[2]	BOYER R S , MOORE J S . A fast string searching algorithm[J]. Communications of the ACM, 1977,20(10):762-772.
[3]	KHARBUTLI M , ALDWAIRI M , MUGHRABI A . Function and data parallelization of Wu-Manber pattern matching for intrusion detection systems[J]. Network Protocols and Algorithms, 2012,4(3):46-61.
[4]	AHO A V , CORASICK M J . Efficient string matching: an aid to biblio-graphic search[J]. Communications of the ACM, 1975,18(6):333-340.
[5]	NAVARRO G , RAFFINOT M . Flexible pattern matching in strings:practical on-line search algorithms for texts and biological sequences[M]. Oxford City: Cambridge University Press, 2002.
[6]	BAEZA-YATES R A , GONNET G H . A new approach to text searching[C]// 12th International Conference on Research and Devel-opment in Information Retrieval. 1989:168-175.
[7]	DENCKER P , DORRE K , HEUFT J . Optimization of parser tables for portable compilers[J]. ACM Transactions on Programming Languages and Systems, 1984,6(4):546-572.
[8]	NORTON M . Optimizing pattern matching for intrusion detec-tion[EB/OL]. , 2004.
[9]	TUCK N , SHERWOOD T , CALDER B , et al. Deterministic mem-ory-efficient string matching algorithms for intrusion detection[C]// IEEE INFOCOM. 2004.
[10]	AHO V , SETHI R , ULLMAN J D . Compilers: principles, techniques, and tools[M]. New Jersey: Addison-Wesley. 1985.
[11]	AOE J , MORIMOTO K , SATO T . An efficient implementation of trie structures[J]. Software-Practice ＆ Experience, 1992,22(9):695-721.
[12]	ZIEGLER S . Smaller faster table driven parser, unpublished manu-script[Z]. Madison Academic Computing Center, 1977.
[13]	TARJAN R E , YAO A C . Storing a sparse table[J]. Communications of the ACM, 1979,22:606-611.
[14]	FREDMAN M , KOML′OS J , SZEMER′EDI E . Storing a sparse table with O(1) worst case access time[J]. Journal of the ACM, 1984,31(3):538-544.
[15]	杨毅夫，刘燕兵，刘萍，等．串匹配算法中的自动机紧缩存储技术[J]．计算机工程， 2009,35(21):39-41. YANG Y F , LIU Y B , LIU P , et al. Automation compact representa-tion technology in string matching algorithm[J]. Computer Engineer-ing, 2009,35(21):39-41.
[16]	NIEVES R , LADRA B S . K2-trees for compact web graph representa-tion[C]// String Processing and Information Retrieval Lecture Notes in Computer Science. 2009,5721:18-30.
[17]	NIEVES R , LADRA B S . Compact representation of web graphs with extended functionality[J]. Information Systems, 2014,39(1):152-174.
[18]	张萍，刘燕兵，于静，等． HashTrie：一种空间高效的多模式串匹配算法[J]．通信学报， 2015,36(10):172-180. ZHANG P , LIU Y B , YU J , et al. HashTrie: a space-efficient multiple string matching algorithm[J]. Journal on Communication, 2015,36(10):172-180.
[19]	Available online[EB/OL]. .
[20]	Available online[EB/OL]. .
[21]	Available online[EB/OL]. .

	映射方法1	映射方法2
\|Σ′\|
\|Σ′\|	false Pr匹配速度/(Mbit·s^-1)	false Pr匹配速度/(Mbit·s^-1)
2	0.983 37246.174	0.999 5026.727
3	0.927 03180.346	0.966 81081.919
4	0.839 67195.510	0.751 290111.655
5	0.795 34593.517	0.759 349105.640
6	0.743 00998.047	0.463 018118.173
7	0.548 801105.818	0.462 320125.500
8	0.707 900105.818	0.725 228114.717
9	0.707 851105.640	0.366 034121.609
10	0.451 385114.927	0.276 589121.845

算法	空间	预处理时间	搜索时间
AC	O(\|P\|σlog\|P\|)	O(\|P\|σ)	O(n)
HashTrie	O(\|P\|)	O(\|P\|)	O(l _max n)
FilterFA	O(\|P\|\|Σ′\|)	O(\|P\|)	O(n)

最短模式串长度	模式串个数		存储空间/MB
最短模式串长度	模式串个数	AC	HashTrie	FilterFA
8	18 754	558.2	2.02	20.8
12	18 461	556.4	2.04	20.7
16	17 225	542.7	2.045	20.3
18	16 448	532.6	2.035	19.9
20	16 082	527.1	2.045	19.8
22	14 955	507.76	2.009	19.1

			匹配速度/(MB·s^-1)
最短模式串长度	模式串个数
最短模式串长度	模式串个数	AC	HashTrieFilterFA
8	18 754	59.5	48.2354.8
12	18 461	59.6	48.23556.3
16	17 225	61.3	48.23556.3
18	16 448	61.3	45.7156.3
20	16 082	63.3	45.7157.9
22	14 955	65.4	53.7559.6

像字符集大小	误识别率
2	98.985%
4	8.422%
6	0.148%
8	0.006%
10	0.001%
11	0.000%