HybridFA：一种基于统计的AC自动机空间优化技术

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

通信学报 ›› 2015, Vol. 36 ›› Issue (7): 31-39.doi: 10.11959/j.issn.1000-436x.2015148

HybridFA：一种基于统计的AC自动机空间优化技术

熊刚¹,何慧敏²,于静¹,刘燕兵¹,郭莉¹

¹ 中国科学院信息工程研究所，北京 100093
² 中国移动（深圳）有限公司，深圳 518031

出版日期:2015-07-25 发布日期:2015-07-25
基金资助:
中国科学院战略性科技先导专项基金资助项目;国家高技术研究发展计划（“863计划）基金资助项目;国家自然科学基金青年基金资助项目

HybridFA:a memory reduction technique for the AC automata based on statistics

Gang XIONG¹,Hui-min HE²,Jing YU¹,Yan-bing LIU¹,Li GUO¹

¹ Institute of Information Engineering,Chinese Academy of Science,Beijing 100093,China
² China Mobile Group,Guangdong Co.Ltd.,Shenzhen Branch,Shenzhen 518031,China

Online:2015-07-25 Published:2015-07-25
Supported by:
The Strategic Priority Research Program of the Chinese Academy of Sciences;The National High Technology Research and Development Program of China (863 Program);The National Natural Science Foundation of China

摘要/Abstract

摘要：

针对高级Aho-Corasick (AC)自动机为提高串匹配速度而造成的空间浪费问题，研究发现数据流对自动机节点的访问规律，据此提出基于数据访问特征的混合自动机构建算法HybridFA。分别研究了基于访问频率、访问层次以及结合上述2种特征对AC自动机的部分节点实现完全化的算法。在Snort、ClamAV、URL等真实数据集上的实验结果表明，HybridFA算法的存储空间低于高级AC自动机的5%。此外，结合访问频率和访问层次的改进算法在保证匹配速度的同时具有更强的数据适应性。

关键词: 多模式串匹配, 空间优化, 高级AC自动机, 统计策略, 节点完全化

Abstract:

Despite the fast speed in multiple string matching tasks,the advanced Aho-Corasick(AC) automata wastes storage memory to a great extent.Study indicated that the automata states have specific statistical access characteristics in practice.Accordingly,a series of algorithms based on statistical characteristics for building hybrid finite automata,named HybridFA,are proposed.This work completes partial states of the AC automata according to different features,including access frequency,state hierarchy,and combined characteristics respectively.Experimental results on the real-world datasets like Snort,ClamAV,and URL show that the storage space of HybridAC is reduced to less than 5% of the space cost by the advanced AC automata.Furthermore,HybridFA based on combined characteristics achieves the superior performance on matching speed and robustness comparing to other proposed algorithms.

Key words: multiple string matching, memory reduction, advanced AC automata, statistical strategy, state completing

熊刚,何慧敏,于静,刘燕兵,郭莉. HybridFA：一种基于统计的AC自动机空间优化技术[J]. 通信学报, 2015, 36(7): 31-39.

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.

图/表 11

表1

表2

图1

图2

图3

图4

图5

图6

图7

图8

表3

参考文献 14

[1]	ME L , HEYE L , KURI J , et al. A pattern matching based filter for audit reduction and fast detection of potential intrusions[A]. The 3rd International Workshop on the Recent Advances in Intrusion Detection[C]. Toulouse,France, 2000. 17-27.
[2]	NAVARRO G , KURI J . Fast Multipattern Search Algorithms for Intrusion Detection[R]. Technical Report TR/DCC-99-11,Dept.of Computer Science,Univ of Chile. 1999.
[3]	VARGHESE G , FIST M . Applying Fast String Matching to Intrusion Detection[R]. Technical Report In preparation,successor to UCSD TR CS2001-0670.University of California,San Diego. 2002.
[4]	AHO A V , CORASICK M J . Efficient string matching:an aid to bibliographic 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]. SIAM Publishing, 2002.
[6]	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.
[7]	AHO A V , SETHI R , ULLMAN J D . Compilers:Principles,Techniques,and Tools[M]. Addison-Wesley Publishing, 2006.
[8]	ZIEGLER S , . Smaller faster table driven parser[EB/OL]. . Unpublished manuscript.Madison Academic Computing Center, 1977.
[9]	AOE J , MORIMOTO0 K , SATO T . An efficient implementation of trie structures[J]. Software—Practice and Experience, 1992,22(9): 695-721.
[10]	刘燕兵, 刘萍, 谭建龙等. 基于存储优化的多模式串匹配算法[J]. 计算机研究与发展, 2009,46(10): 1768-1776. LIU Y B , LIU P , TAN J L , et al. A multiple string matching algorithm based on memory optimization[J]. Journal of Computer Research and Development, 2009,46(10): 1768-1776.
[11]	NAVARRO G , RAFFINOT M . Fast and flexible string matching by combining bit-parallelism and suffix automata[J]. Experimental Algorithmics, 2000,5(4):DOI:10.1145/351827.384246.
[12]	Clam Antivirus,an anti virus detection software[EB/OL]. .
[13]	Free real network data for string matching test released by MIT[EB/OL]. .
[14]	Snort,a free and open source network intrusion detection and prevention system[EB/OL].

节点数目	节点数目所占百分率	累计访问频率
408	0.86%	91%
465	0.98%	92%
531	1.12%	93%
613	1.29%	94%
715	1.51%	95%
850	1.79%	96%
1 057	2.23%	97%
1 404	2.96%	98%

访问层次	访问频率	累计访问频率
2	43.6%	86.3%
3	8.9%	95.2%
4	2.0%	97.2%
5	1.0%	98.2%
6	0.4%	98.6%
7	0.4%	99.0%
8	0.3%	99.3%
9	0.2%	99.5%

算法	频率界限	层次界限	Snort数据集		ClamAV数据集		URL数据集
算法	频率界限	层次界限	存储空间/MB	匹配速度/(Mbit·s^-1)	存储空间/MB	匹配速度/(Mbit·s^-1)	存储空间/MB	匹配速度/(Mbit·s^-1)
高级AC	—	—	56.16	84.39	549.89	37.49	187.74	85.35
HybridFA_1	98%	—	2.22	69.86	10.25	39.77	8.60	68.26
HybridFA_2	—	3	2.22	53.27	13.29	33.74	8.22	47.98
HybridFA_3	98%	3	2.75	72.41	14.55	45.01	8.70	71.53

HybridFA：一种基于统计的AC自动机空间优化技术

HybridFA:a memory reduction technique for the AC automata based on statistics

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 11

参考文献 14

相关文章 2

Metrics

推荐阅读 0

[1]	张萍,何慧敏,张春燕,曹聪,刘燕兵,谭建龙. FilterFA：一种基于字符集规约的模式串匹配算法[J]. 通信学报, 2016, 37(12): 103-114.
[2]	张萍,刘燕兵,于静,谭建龙. HashTrie：一种空间高效的多模式串匹配算法[J]. 通信学报, 2015, 36(10): 172-180.