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

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

Abstract

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

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.

Figures/Tables 7

References 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]. .

Metrics

Recommended 0

No Suggested Reading articles found!

算法	空间	预处理时间	搜索时间
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

HashTrie:a space-efficient multiple string matching algorithm

RichHTML

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

Figures/Tables 7

References 24

Related Articles 15

Metrics

Recommended 0

[1]	Xin SUN, Guifu ZHANG, Hongyan XING, Wang Zenghui. Research on intrusion detection for maritime meteorological sensor network based on balancing generative adversarial network [J]. Journal on Communications, 2023, 44(4): 124-136.
[2]	Yifeng WANG, Yuanbo GUO, Qingli CHEN, Chen FANG, Renhao LIN. Method based on contrastive learning for fine-grained unknown malicious traffic classification [J]. Journal on Communications, 2022, 43(10): 12-25.
[3]	Qixu LIU, Junnan WANG, Jie YIN, Yanhui CHEN, Jiaxi LIU. Application of adversarial machine learning in network intrusion detection [J]. Journal on Communications, 2021, 42(11): 1-12.
[4]	Youliang TIAN,Yulong WU,Qiuxian LI. Optimum response scheme of intrusion detection based on information theory [J]. Journal on Communications, 2020, 41(7): 121-130.
[5]	Xinglan ZHANG,Shenglin YIN. Intrusion detection model of random attention capsule network based on variable fusion [J]. Journal on Communications, 2020, 41(11): 160-168.
[6]	Wei SUN,Peng ZHANG,Yongquan HE,Lichao XING. Attack detection method based on spatiotemporal event correlation in intranet environment [J]. Journal on Communications, 2020, 41(1): 33-41.
[7]	Zhen ZHANG,Peng WEI,Yufeng LI,Julong LAN,Ping XU,Bo CHEN. Feature selection algorithm based on improved particle swarm joint taboo search [J]. Journal on Communications, 2018, 39(12): 60-68.
[8]	Ying-xu LAI,Zeng-hui LIU,Xiao-tian CAI,Kai-xiang YANG. Research on intrusion detection of industrial control system [J]. Journal on Communications, 2017, 38(2): 143-156.
[9]	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.
[10]	Ye DU,dan ZHANGYa,hong LIMei,wei ZHANGDa. Improved FastICA algorithm for data optimization processing in intrusion detection [J]. Journal on Communications, 2016, 37(1): 42-48.
[11]	Jie SU,Wei-wei DONG,Xuan XU,Shuai LIU,Li-peng XIE. GHSOM intrusion detection based on Dempster-Shafer theory [J]. Journal on Communications, 2015, 36(Z1): 60-64.
[12]	Yang XIAO,Lei BAI,Xian WANG. Friends mechanism-based routing intrusion detection model for mobile ad hoc network [J]. Journal on Communications, 2015, 36(Z1): 203-214.
[13]	Gang XIONG,Hui-min HE,Jing YU,Yan-bing LIU,Li GUO. HybridFA:a memory reduction technique for the AC automata based on statistics [J]. Journal on Communications, 2015, 36(7): 31-39.
[14]	Xiao-nian WU,Xiao-jin PENG,Yu-yang YANG,Kun FANG. Two-level feature selection method based on SVM for intrusion detection [J]. Journal on Communications, 2015, 36(4): 19-26.
[15]	. Research on distributed genetic k-means for anomaly detection in MANET [J]. Journal on Communications, 2015, 36(11): 167-173.