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

熊刚; 何慧敏; 于静; 刘燕兵; 郭莉

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

您当前的位置：

首页 >

文章列表页 >

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

学术论文 | 更新时间：2024-06-05

- HybridFA：一种基于统计的AC自动机空间优化技术
- HybridFA:a memory reduction technique for the AC automata based on statistics
- 通信学报 2015年36卷第7期页码：31-39
- 作者机构：
  
  1. 中国科学院信息工程研究所，北京 100093
  2. 中国移动（深圳）有限公司，深圳 518031
- 作者简介：
  
  [ "熊刚（1977-），男，湖北汉川人，中国科学院信息工程研究所高级工程师，主要研究方向为网络测量与行为分析、信息对抗、信息安全。" ]
  [ "何慧敏（1987-），女，山东菏泽人，中国移动（深圳）有限公司工程师，主要研究方向为串匹配算法。" ]
  [ "于静（1989-），女，河北承德人，中国科学院信息工程研究所实习研究员，主要研究方向为模式匹配算法、机器学习、图像处理。" ]
  [ "刘燕兵（1981-），男，湖北麻城人，中国科学院信息工程研究所副研究员，主要研究方向为模式匹配算法、图数据计算、信息内容安全。" ]
  [ "郭莉（1969-），女，湖南湘潭人，中国科学院信息工程研究所教授级高级工程师，主要研究方向为信息安全、数据流处理。" ]
- 基金信息：
  
  中国科学院战略性科技先导专项基金资助项目;The Strategic Priority Research Program of the Chinese Academy of Sciences(XDA06030602);国家高技术研究发展计划(“863”计划)基金资助项目;The National High Technology Research and Development Program of China (863 Program)(2011AA010703);国家自然科学基金青年基金资助项目;The National Natural Science Foundation of China(61202477)
- DOI：10.11959/j.issn.1000-436x.2015148
  中图分类号： TP301.1
- 网络出版日期：2015-07，
  
  纸质出版日期：2015-07-25
- 稿件说明：
移动端阅览
熊刚, 何慧敏, 于静, 等. HybridFA：一种基于统计的AC自动机空间优化技术[J]. 通信学报, 2015,36(7):31-39.

Gang XIONG, Hui-min HE, Jing YU, et al. HybridFA:a memory reduction technique for the AC automata based on statistics[J]. Journal on communications, 2015, 36(7): 31-39.
熊刚, 何慧敏, 于静, 等. HybridFA：一种基于统计的AC自动机空间优化技术[J]. 通信学报, 2015,36(7):31-39. DOI： 10.11959/j.issn.1000-436x.2015148.

Gang XIONG, Hui-min HE, Jing YU, et al. HybridFA:a memory reduction technique for the AC automata based on statistics[J]. Journal on communications, 2015, 36(7): 31-39. DOI： 10.11959/j.issn.1000-436x.2015148.

摘要

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

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.

关键词

Keywords

references

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 .

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 .

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 .

AHO A V , CORASICK M J . Efficient string matching:an aid to bibliographic search [J ] . Communications of the ACM , 1975 , 18 ( 6 ): 333 - 340 .

NAVARRO G , RAFFINOT M . Flexible Pattern Matching in Strings:Practical On-line Search Algorithms for Texts and Biological Sequences [M ] . SIAM Publishing , 2002 .

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 .

AHO A V , SETHI R , ULLMAN J D . Compilers:Principles,Techniques,and Tools [M ] . Addison-Wesley Publishing , 2006 .

ZIEGLER S , . Smaller faster table driven parser [EB/OL ] . http://www.researchgate.net/publication/242522203_Smaller_faster_table_driven_parser http://www.researchgate.net/publication/242522203_Smaller_faster_table_driven_parser . Unpublished manuscript.Madison Academic Computing Center , 1977 .

AOE J , MORIMOTO0 K , SATO T . An efficient implementation of trie structures [J ] . Software—Practice and Experience , 1992 , 22 ( 9 ): 695 - 721 .

刘燕兵 , 刘萍 , 谭建龙等 . 基于存储优化的多模式串匹配算法 [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 .

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.

Clam Antivirus,an anti virus detection software [EB/OL ] . http://www.clamav.net/binary.html#pagestar http://www.clamav.net/binary.html#pagestar .

Free real network data for string matching test released by MIT [EB/OL ] . http://www.ll.mit.edu/IST/ideval/ http://www.ll.mit.edu/IST/ideval/ .

Snort,a free and open source network intrusion detection and prevention system [EB/OL ] . http://www.snort.org/snort-rules/?#rules http://www.snort.org/snort-rules/?#rules

浏览量

1396

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

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

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