基于自动机并操作的多目标AC-BM算法

计算机科学 ›› 2013, Vol. 40 ›› Issue (6): 119-123.

基于自动机并操作的多目标AC-BM算法

王正才,许道云,王晓峰

贵州大学计算机科学与信息学院贵阳550025;贵州大学计算机科学与信息学院贵阳550025;贵州大学计算机科学与信息学院贵阳550025

出版日期:2018-11-16 发布日期:2018-11-16
基金资助:
本文受国家自然科学基金项目(60863005,8),贵州大学自然科学青年科研基金项目((2009)021),贵州大学研究生创新基金项目(省研理工2010005)资助

Multi-objective AC-BM Algorithm Based on Automata Union Operation

WANG Zheng-cai,XU Dao-yun and WANG Xiao-feng

Online:2018-11-16 Published:2018-11-16

摘要/Abstract

摘要： AC-BM算法的优点在于能同时进行多个模式串的匹配搜索,且文本串的移位得到优化,但一次只能在一个文本串中进行搜索。为了实现一次可以同时在多个文本串中进行搜索,设计了多目标AC-BM算法。利用自动机并操作技术构造多目标多模式树自动机,借助BM算法的坏字符跳转技术来计算文本串集移位。在Snort系统中分别实现2-目标AC-BM算法和3-目标AC-BM算法。实验结果表明,新算法如果在多个文本串中找到模式串就停止(表示检测到攻击行为),其在时间性能上就明显优于AC-BM算法。

关键词: AC-BM算法,模式串,匹配搜索,自动机,坏字符跳转技术,Snort

Abstract: The AC-BM algorithm has the advantages that multiple pattern strings are searched simultaneously and that number of characters of moving text string is optimized．But,they are searched only in one text string in one time．To search in multiple text strings simultaneously,this paper designed multi-objective AC-BM algorithm．By union operation of two automatons,multi-objective multi-pattern tree automata was structured,and by BM algorithm’s bad character move technique,function of moving a set of text strings was designed．In the Snort,2-goal AC-BM algorithm and 3-goal AC-BM algorithm were implemented．On the condition that if in multiple text strings a pattern string is found,the algorithm stops,the result shows the new algorithm is obviously superior to AC-BM algorithm in time.

Key words: AC-BM algorithm,Pattern string,Pattern matching search,Automata,Bad character move technique,Snort

王正才,许道云,王晓峰. 基于自动机并操作的多目标AC-BM算法[J]. 计算机科学, 2013, 40(6): 119-123. https://doi.org/

WANG Zheng-cai,XU Dao-yun and WANG Xiao-feng. Multi-objective AC-BM Algorithm Based on Automata Union Operation[J]. Computer Science, 2013, 40(6): 119-123. https://doi.org/

参考文献

[1] Navaro G R M．Flexible Pattern Matching in Strings[M]．Cambridge University Press,2002
[2] Roesch M,Green C.Snort users manual．https://www.Snort.org
[3] Boyer R S,Moor J S.A fast string searching algorithm[J]．Communications of the ACM,1977,20(10):762-772
[4] Fan Jang-jong,Su K．An Efficient Algorithm for Matching Multiple Patterns[J]．IEEE Transactions on Knowledge and Data Engineering,1993,5(2):339-351
[5] 周四伟,蔡勇．AC-BM算法的改进及其在入侵检测中的应用[J].微计算机应用,2007,8(1):27-31
[6] 万国根,秦志光．改进的AC-BM字符串匹配算法[J].电子科技大学学报,2006,5(4):531-534
[7] 姚亚锋,蒋毅．模式匹配算法及其优化[J]．南通职业大学学报,2011,5(4):98-100
[8] Hou Zheng-feng,Zhang Xiao-le．Research and improvement ofAC-BM algorithm[J]．Chinese Journal of Scientific Instrument,2011,3(2):216-221
[9] Wu Pei-fei．The research and amelioration of pattern-matchingalgorithm in intrusion detection system[C]∥Proceedings of the 14th IEEE International Conference on High Performance Computing and Communications(HPCC-2012)．2012:1712-1715
[10] 杨超．双向AC算法及其在入侵检测系统中应用[J]．计算机应用,2011,0(3):222-225
[11] 黄海．字符串匹配算法通用并行技术研究[D]．西安:西安建筑科技大学,2010
[12] Miao Chang-sheng,Chang Gui-ran,Wang Xing-wei．FilteringBased Multiple String Matching Algorithm Combining q-Grams and BNDM[C]∥Proceedings of the 2010Fourth International Conference on Genetic and Evolutionary Computing．ACM,2010:582-585
[13] Zhang Wei-zhe,Zhang Yuan-jing,Zhang Hong-li,et al.A Memo-ry-Efficient Multi-pattern Matching Algorithm Based on the Bitmap[C]∥Proceedings of the 2009Fourth International Confe-rence on Internet Computing for Science and Engineering．ACM,2009:1-5
[14] Chen Xin-ming,Ge Kai-lin,Chen Zhen．AC-Suffix-Tree:Buffer Free String Matching on Out-of-Sequence Packets[C]∥Proceedings of the 2011ACM/IEEE Seventh Symposium on Architectures for Networking and Communications Systems,2011:36-44

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed