入侵检测中一种新的快速字符串匹配算法.pdfVIP

掌·学术探讨 ·睾 带 带 带 带 入侵检测中一种新的快速字符串匹配算法 宋 华 戴一奇 (清华大学计算机系，北京 100084) E—mail：songh00@mails．tsinghua．edu．en 摘 要 基于字符 串匹配的检测方法是入侵检测系统 中一类很重要 的分析方法。文章首先分析 了现有 的几种准确字符 串匹配算法 ，然后提 出了一种新 的多模式字符 串匹配算法 ，并且分析 了这些算法的复杂性。最后 ，文章用具体 的实验数据 来验证这些算法的性能。通过实验可以看 出，新算法使得检测速度大大提高，签名容量大大增加 。 关键词 入侵检测 签名匹-配算法 多模式字符 串匹配算法 文章编号 l0o2—8331一(20o3)32-oo48—04 文献标识码 A 中图分类号 I’P393 A New FastString MatchingAlgorithm for Intrusion Detection SongHua DaiYiqi (TheComputerDepartmentofTsinghuaUniversity，Beijing100084) Abstract： String matching algorithms are very importantanalyzing methods in intrusion detection．This paperna alyzes someexisting stringmatchingalgorihtmsna drelatedresealches，and then presentsanew multi patterns stringmatching algorihtm．Itshowsnaalyticallyna d experimentallyhtatthenew algorithm isfasterin esarching large sets ofpatterns． Keywords：Intrusion detection，Signature matchingalgorithms，Multipatternsstring matchingalgorihtms l 引言 否有模式字符串，在匹配时将文本和模式字符串对齐，首先 在现代信息社会，对黑客入侵进行检测与防范、保障信息 比较匹配窗 口内模式字符 串的最后一个字符 ，从右到左进行 基础设施 的安全 已经成为刻不容缓的重要课题。入侵检测技术 比较 。 是为保证信息系统的安全而设计的一种能够及时发现并报告 AlfredV．Aho和MargaretJ．Corasiek设计了一种简单有效 系统 中未授权或异常现象的技术 ，是一种用于检测计算机网络 的多模式字符串匹配算法悯，用以在文本中发现有限数量的多 中违反安全策略行为的技术 。 个模式字符串的所有出现。算法首先利用多个模式字符串构建 基于字符 串匹配的检测方法是入侵检测系统 中一类很重 一 个有限状态模式匹配 自动机 ，然后利用这个模式匹配 自动机 要 的分析方法 。这种检测方法在主机或网络数据 中，通过准确 一 次性有哪些信誉好的足球投注网站文本 ，找到所有 出现的模式 。构建模式匹配 自动机 的字符 串模式匹配查找攻击签名 ，从而判断是否出现入侵 。在 的时间正 比于所有模式字符 串长度 的总和。在文本 中有哪些信誉好的足球投注网站模式 很多的商业入侵检测产品和研究项 目中，例如 NetworkSecu- 字符串时模式匹配 自动机状态转换的数量和模式字符串的数 ritj，Monitort”，Durgon~，BmDl，Sn0rt嘲，都采用 了字符 串匹配算 量无关，而正 比于文本 的长度 。Aho-Corasiek算法是 Knutll— 法 。因此 ，对字符 串匹配算法进行深入 的研究