面向内容安全的多模精确匹配算法性能分析.pdfVIP

2004年7月 通 信 学 报 、b1．25NO．7 第25卷 第7期 JOURNALOFCHINAINSTI11，TEOFCOMMUNICATIONS July2004 面向内容安全的多模精确匹配算法性能分析 张冬艳，殷丽华，胡铭曾，云晓春，郑秀荣 (1．哈尔滨E业大学 计算机科学与技术学院，黑龙江 哈尔滨 150001： 2．国家计算机信息内容安全重点实验室，黑龙江 哈尔滨 150001) 摘 要：在对大规模网络流量进行实时处理的情况下，对几种典型的多模式精确匹配算法，结合 信息内容安全的特点，提出了分析性能的测试方案。根据测试方案，通过实验模拟分析了算法的 性能，给出了不同情况下的最优算法。 关键词：模式匹配；最优算法；性能测试；内容安全 中图分类号：TP393．08 文献标识码：B 文章编号：1000-436X(2004)07—0128—09 Theperformanceofmultiple-keywordpatternmatching algorithmsofinformationcontentsecurity ZHANGDong—yan，YINLi—hua，HUMing—zeng，YUNXiao—chun，ZHENGXiu—rong f1．SchoolofComputerScienceandTechnology．HarbinInstituteofTechnology,Harbin150001，China； 2．StateKeyLaboratoryofComputerInformationCon~ntSecurity,Harbin150001，China) Abstract：Theperformancenaalysisprojectisproposednadusedtotestsometypicalmutiple—keyword paHemmatchingalgorithmsinareal—timenadlarge—scalenetwork．Accordingtotheproject，wemade experimentalsimulationsnadtheresultsindicatethatwhichalgorihtm isbestindifferentapplications． Keywords：paaemmatch；optimizationalgorihtms；perfomr nacetest；contentsecurity 1 引言 近年来，随着因特网的迅猛发展，人们又面临着网络安全问题的严峻考验，在大规模网 络流量上进行中英文混合实时处理的情况下，结合信息内容安全的特点，本文对几种典型的 多模式精确匹配算法的性能进行了分析，找到了在不同应用环境下的最优算法。此项研究在 实际的工程应用中有着很大的意义。 2 算法简介 多模式匹配算法主要有 Aho—Corasick自动机算法(1975年)，反向跳跃自动机算法(2000 年)，SBOM算法(1999年)，mgrep算法(1994年)，Commentz—Walter算~(1979年)，DAWG— MATCH算~(1993年)，MULTI—BDM算法(1996年)，SumKim99和BNDM 算~(2001年)等 收稿日期：2004．02．10 基金项目：国家自然科学基金资助项目；国家 “863”基金资助项目(2002AA142020) 第7期 张冬艳等：面向内容安全的多模精确匹配算法性能分析 等。本文主要实现并分析了其中的五种算法。 (1)Aho—Corasick算法 ‘ Aho—Corasick自动机算法 (简称AC自动机)是一个比较经典的多模式匹配算法。在预 处理阶段，AC自动机算法建立了三个函数，转向函数goto，失效函数 和输出函数output， 由此构造了一个树型有限自动机。在有哪些信誉好的足球投注网站查找阶段，则通过这三个函数的交叉使用扫描文本， 定位出关键字在文本中的所有出现位置。此算法