HashTrie：一种空间高效的多模式串匹配算法

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

摘要/Abstract

摘要：

经典的多模式串匹配算法AC的内存开销巨大，已经无法满足当前高速网络环境下大规模特征串实时匹配的应用需求。针对这一问题，提出一种空间高效的多模式串匹配算法—HashTrie。该算法运用递归散列函数，将模式串集合的信息存储在位向量中，以取代状态转移表来减少空间消耗，并利用Rank操作进行快速匹配校验。理论分析表明，HashTrie算法的空间复杂度为O(|P|)，与模式串集合的规模|P|线性相关，与字符集大小σ无关，优于经典多模式串匹配算法AC的空间复杂度O(|P|σlog|P|)。在随机数据集和真实数据集（Snort、ClamAV和URL）上的测试结果表明，HashTrie算法比AC算法节约高达99.6%的存储空间，匹配速度约为AC算法的一半左右。HashTrie算法适合于模式串集合规模较大、模式串长度较短的多模式串匹配问题，是一种空间高效的多模式串匹配算法。

关键词: 入侵检测, 多模式串匹配, 位向量, 递归散列函数, 空间高效

Abstract:

The famous multiple string matching algorithm AC consumed huge memory when the string signatures were massive,thus unable to process high speed network traffic efficiently.To solve this problem,a space-efficient multiple string matching algorithm-HashTrie was proposed.This algorithm adopted recursive hash function to store the patterns in bit-vectors in place of the state transition table in order to reduce space consumption.Further more it made use of the rank operation for fast verification.Theoretic analysis shows that the space complexity of HashTrie is O(|P|),which is linear with the size of pattern set |P|and is independent of the alphabetsize σ.The space complexity is superior to the complexity O(|P|σlog|P|)of AC.Experiments on synthetic datasets and real-world datasets(such as Snort,ClamAV and URL)show that HashTrie saves up to 99.6% storage cost compared with AC,and in the meanwhile it runs at a matching speed that is about half of AC.HashTrie is a space-efficient multiple string matching algorithm that is appropriate to search large scale pattern strings with short lengths.

Key words: intrusion detection, multiple string matching, bit-vector; recursive hash function, space-efficient

张萍,刘燕兵,于静,谭建龙. HashTrie：一种空间高效的多模式串匹配算法[J]. 通信学报, 2015, 36(10): 172-180.

Ping ZHANG,Yan-bing LIU,Jing YU,Jian-long TAN. HashTrie:a space-efficient multiple string matching algorithm[J]. Journal on Communications, 2015, 36(10): 172-180.

图/表 7

图1

图2

表1

图3

图4

图5

表2

参考文献 24

[1]	NAVARRO G , RAFFINOT M . Flexible Pattern Matching in Strings:Practical On-line Search Algorithms for Texts and Biological Sequences[M]. Cambridge University Press, 2002.
[2]	AHO A V , CORASICK M J . Efficient string matching:an aid to bibliographic search[J]. Communications of the ACM, 1975,18(6): 333-340.
[3]	BAEZA-YATES R , GONNET G H . A new approach to text searching[J]. Communications of the ACM, 1992,35(10): 74-82.
[4]	BOYER R S , MOORE J S . A fast string searching algorithm[J]. Communications of the ACM, 1977,20(10): 762-772.
[5]	COMMENTZ-WALTER B . A String Matching Algorithm Fast on the Average[M]. Springer Berlin Heidelberg, 1979.
[6]	HORSPOOL R N . Practical fast searching in strings[J]. Software:Practice and Experience, 1980,10(6): 501-506.
[7]	WU S,MANBERU . A fast algorithm for multi-pattern searching[R]. Technical Report TR-94-17,University of Arizona, 1994.
[8]	RAFFINOT M . On the multi backward dawg matching algorithm(MultiBDM)[A]. Proc of 4th South American Workshop on String Processing[C]. 1997. 149-165.
[9]	ALLAUZEN C , CROCHEMORE M , RAFFINOT M . Factor oracle:a new structure for pattern matching[A]. SOFSEM’99:Theory and Practice of Informatics[C]. Springer Berlin Heidelberg, 1999. 295-310.
[10]	NAVARRO G , RAFFINOT M . A bit-parallel approach to suffix automata:fast extended string matching[A]. Combinatorial Pattern Matching[C]. Springer Berlin Heidelberg, 1998. 14-33.
[11]	LIN C H , LIU C H , CHANG S C ,et al. Memory-efficient pattern matching architectures using perfect hashing on graphic processing units[A]. INFOCOM,2012 Proceedings IEEE[C]. IEEE, 2012. 1978-1986.
[12]	AOE J I . An efficient implementation of static string pattern matching machines[J]. IEEE Transactions on Software Engineering, 1989,15(8): 1010-1016.
[13]	ERDOGAN O , CAO P . Hash-AV:fast virus signature scanning by cache-resident filters[J]. International Journal of Security and Networks, 2007,2(1): 50-59.
[14]	TAN L , SHERWOOD T . A high throughput string matching architecture for intrusion detection and prevention[J]. ACMSIGARCH Computer Architecture News,IEEE Computer Society, 2005,33(2): 112-122.
[15]	VAN L J . High-performance pattern matching for intrusion detection[A]. INFOCOM,2006 Proceedings IEEE[C]. IEEE, 2006. 1-13.
[16]	SONG T , ZHANG W , WANG D ,et al. A memory efficient multiple pattern matching architecture for network security[A]. INFOCOM 2008,The 27th Conference on Computer Communications[C]. IEEE, 2008.
[17]	Available online[EB/OL]. .
[18]	JACOBSON G . Space-efficient static trees and graphs[A]. Foundations of Computer Science[C]. 1989. 549-554.
[19]	何慧敏, 刘燕兵, 谭建龙 ,等. 一种基于子串识别的多模式串匹配算法[J]. 计算机应用与软件, 2012,28(11): 10-14. HE H M , LIU Y B , TAN J L ,et al. A substring recognition based multiple patterns string matching algorithm[J]. Computer Applications and Software, 2012,28(11): 10-14.
[20]	LIU Y B , LIU Q Y , LIU P ,et al. A factor-searching-based multiple string matching algorithm for intrusion detection[A]. Communications(ICC),2014 IEEE International Conference[C]. IEEE, 2014. 653-658.
[21]	Available online[EB/OL]. .
[22]	Available online[EB/OL]. .
[23]	Available online[EB/OL]. .
[24]	Available online[EB/OL]. .

算法	空间	预处理时间	搜索时间
AC	O(\|P\|σlog\|P\|)	O(\|P\|σ)	O(n)
DAC	O(\|P\|log\|P\|)	O(\|P\|² σ)	O(n)
HashTrie	O(\|P\|)	O(\|P\|)	O(l_max n)

数据集	算法	模式串数量	预处理时间/s	内存用量/MB	匹配速度/(MB·s^?1)	匹配数量
	AC	6 325	0.15	240.686	255.92	98 537
Snort	TAC	6 325	0.12	119.833	181.672	98 537
Snort	DAC	6 325	0.07	2.834	124.181	98 537
	HashTrie	6 325	0.01	0.95	108.202	98 537
	AC	79 560	11.44	14 930.818	32.413	18 523 455
ClamAV	TAC	79 560	8.48	7 427.517	27.976	18 523 455
ClamAV	DAC	79 560	7.16	158.116	54.3	18 523 455
	HashTrie	79 560	0.14	46.573	21.609	18 523 455
	AC	794 615	16.55	22 609.141	109.269	41 591
URL	TAC	794 615	18.33	11 266.525	79.275	41 591
URL	DAC	794 615	10.76	289.771	79.783	41 591
	HashTrie	794 615	0.57	201.329	51.031	41 591
	AC	100 000	1.02	1 288.529	11.858	10 534
随机数据集	TAC	100 000	0.76	642.636	12.448	10 534
随机数据集	DAC	100 000	0.61	19.008	48.387	10 534
	HashTrie	100 000	0.02	9.076	50.847	10 534