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

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

作　　者：王正才[1] 许道云[1] 王晓峰[1] 

机构地区：[1]贵州大学计算机科学与信息学院贵阳550025

出　　处：《计算机科学》2013年第6期119-123,共5页Computer Science

基　　金：国家自然科学基金项目(60863005,61011130038);贵州大学自然科学青年科研基金项目((2009)021);贵州大学研究生创新基金项目(省研理工2010005)资助

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

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

分 类 号：TP393.08[自动化与计算机技术—计算机应用技术]