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

Gang XIONG; Hui-min HE; Jing YU; Yan-bing LIU; Li GUO

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

您当前的位置：

首页 >

文章列表页 >

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

Academic paper | 更新时间：2024-06-05

- HybridFA:a memory reduction technique for the AC automata based on statistics
- Journal on Communications Vol. 36, Issue 7, Pages: 31-39(2015)
- 作者机构：
  
  1. 中国科学院信息工程研究所，北京 100093
  2. 中国移动（深圳）有限公司，深圳 518031
- 作者简介：
- 基金信息：
- DOI：10.11959/j.issn.1000-436x.2015148
  CLC： TP301.1
- Online First：2015-07，
  
  Published：25 July 2015
- 稿件说明：
移动端阅览
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：

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

Views

2662

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

FilterFA: a multiple string matching algorithm based on specification of character set

HashTrie:a space-efficient multiple string matching algorithm

Related Author

Ping ZHANG

Hui-min HE

Chun-yan ZHANG

Cong CAO

Yan-bing LIU

Jian-long TAN

Ping ZHANG

Jing YU

Related Institution

Institute of Information Engineering, Chinese Academy of Sciences

University of Chinese Academy of Sciences

National Engineering Laboratory for Information Security Technologies

China Mobile (Shenzhen) Co., Ltd.

AI问答

⁰