入侵检测系统中的多模式精确匹配算法WDawgMatch

doi:10.3969/j.issn.1007130X.2010.

J4 ›› 2010, Vol. 32 ›› Issue (8): 17-21.doi: 10.3969/j.issn.1007130X.2010.

入侵检测系统中的多模式精确匹配算法WDawgMatch

宁卓,龚俭

（1.东南大学计算机科学与工程学院，江苏南京 210096;2.江苏省计算机网络技术重点实验室，江苏南京 210096;3.教育部计算机网络与信息集成重点实验室，江苏南京 210096）

收稿日期:2009-05-18 修回日期:2009-09-21 出版日期:2010-07-25 发布日期:2010-07-25
通讯作者: 宁卓
作者简介:宁卓（1975），女，广西玉林人，博士生，研究方向为网络安全检测；龚俭，教授，博士生导师，研究方向为网络安全、网络管理和网络体系结构等。
基金资助:
国家973计划资助项目（2009CB320505）；国家科技支撑计划资助项目（2008BAH37B04）

WDawgMatch:An Accurate MultiPattern MatchingAlgorithm in Intrusion Detection Systems

NING Zhuo,GONG Jian

(1.School of Computer Science and Technology,Southeast University,Nanjing 210096;2.Jiangsu Provincial Key Laboratory of Computer Network Technology,Nanjing 210096;3.Key Laboratory of Computer Network and Information Integration,Nanjing 210096,China)

Received:2009-05-18 Revised:2009-09-21 Online:2010-07-25 Published:2010-07-25
Contact: NING Zhuo

摘要/Abstract

摘要：

经典的多模式匹配算法如AC、BM，并不满足NIDS对报文负载中攻击特征串检测时做在线乱序流匹配的需求。著名的多模式精确匹配算法DawgMatch弥补了上述算法无法在扫描的同时获得分片摘要信息的缺点，因此在网络入侵检测系统（NIDS）的在线检测中得到普遍应用。尽管基于DAWA自动机使得DawgMatch可通过二元索引来提高空间使用效率，但它的匹配性能尚不能达到高速报文入侵检测线速匹配的要求。本文提出了新算法WDawgMatch，它牺牲预处理时间，引入加权边消除了DawgMatch匹配回溯现象，提升了匹配速度。性能分析和实验结果表明，WDawgMatch降低了原算法的最坏时间复杂度，缩小了与AC算法的差距，完全满足NIDS线速匹配的要求。

关键词: DAWA, DawgMatch, 匹配回溯

Abstract:

The traditional multipattern matching algorithms like AC,BM do not meet the requirements of online outoforder stream reassembly when NIDS detects attack signature matches within packet payloads. As a famous accurate multipattern matching algorithm, DawgMatch is generally used in NIDS as it can get the digests of the segment being scanned.Unfortunately,though it promotes the space usage by a 2tuple indexing factor with the help of the DAWA automaton, its matching speed still can not catch up with the need of online linear detection.To promote the performance of DawgMathch,we design a new algorithm WDawgMach based on it. WDawgMach makes use of weighted edges to eliminate the back trace problem of DawgMatch to achieve the linear matching speed.The performance analysis and experience shows that,by sacrificing the preprocessing time,WDawgMach improves the worst time complexity of DawgMatch and makes it comparable to algorithm AC.

Key words: DAWA;online outoforder reassembly;packet scan

宁卓,龚俭. 入侵检测系统中的多模式精确匹配算法WDawgMatch[J]. J4, 2010, 32(8): 17-21.

NING Zhuo,GONG Jian. WDawgMatch:An Accurate MultiPattern MatchingAlgorithm in Intrusion Detection Systems[J]. J4, 2010, 32(8): 17-21.

入侵检测系统中的多模式精确匹配算法WDawgMatch

WDawgMatch:An Accurate MultiPattern MatchingAlgorithm in Intrusion Detection Systems

PDF

可视化

摘要/Abstract

引用本文

使用本文

相关文章 0

编辑推荐

Metrics

本文评价