收稿日期: 2008唱07唱10; 修回日期: 2008唱08唱29 基金项目: 浙江省自然科学基金资助项目( Y106176)
作者简介:范轩苗(1983唱) ,男,浙江绍兴人,硕士研究生,主要研究方向为网络安全( fanxuanmiaoweb2 @163.com) ;郑宁 (1961唱) ,男,浙江杭州
人,研究员,博导,主要研究方向为信息系统与信息处理、信息安全等;范渊(1975唱),男,浙江金华人,硕士研究生,主要研究方向为网络安全.
Web 入 侵 检 测 系 统 高 效 多 模 式 匹 配 算 法
倡
范轩苗
1
, 郑 宁
1
,范 渊
2
(1.杭州电子科技大学 计算机学院, 杭州 310018; 2.亚龙( 安恒)信息科技( 杭州) 有限公司, 杭州 310035)
摘 要: 针对 Web 入侵检测系 统中 存在的 攻击模式误 匹配与效率 问题,提 出了一 种高 效 的多模 式 匹 配算 法
MPMA。 MPMA 通过构建比较树,并在比较树的每个节点中记录下次比较的字符位置以提高比较效率,并利用
(模式,偏移) 信息对来搜索可能符合的匹配模式。 详细的实验以及与现有算法的比较表明,提出的 MPMA 不仅
适合于 Web 入侵检测系统,同时在时间、空间和匹配率性能上具有更高的效率。
关键词: 入侵检测系统; 多模式匹配; Web
中图分类号: TP393畅08 文献标志码: A 文章编号: 1001唱3695(2009)04唱1528唱04
Efficient multi唱pattern matching algorithm for Web intrusion detection systems
FAN Xuan唱miao
1
, ZHENG Ning
1
, FAN Yuan
2
(1.School of Computer Science, Hangzhou Dianzi University, Hangzhou 310018, China; 2.Hangzhou DB Appsecurity Information Technology
Co., Ltd, Hangzhou 310035, China)
Abstract: To overcome the defects of false pattern matching and time唱and唱space efficiency in Web intrusion detection systems
(IDSs),this paper proposed an efficient multi唱pattern matching algorithm called MPMA.With building comparison tree, every
tree node had a position value which could tell you where an octet comparison should be made next, and MPMA used(pattern,
offset)pair to find possible matching patterns.Detailed experimental results and comparison with existed algorithms prove that
the proposed MPMA not only fits Web IDS, but also outperforms current state唱of唱the唱art schemes in terms of time efficiency,
space efficiency and matching ratio.
Key words: intrusion detection systems(IDS); multi唱pattern matching; Web
0 引言
由于管理者疏忽、系统漏洞、新的攻击手法层出不穷等各
种因素,使得 Web 服务器遭受网络攻击的事件频繁发生
[1]
。
其中以 Web 应用类型的攻击最多,而大部分 Web 应用并没有
采取专门有效的防护措施来应对。 导致 Web 应用进一步面临
威胁的另一个因素是,Web 服务器与应用底层架构的变化以
及使用非安全开放源代码组件现象的增加
[2]
。 Web 服务器与
Web 应用已经从最初提供简单的静态内容演变到提供丰富的
动态内容;除了可以创建动态页面与启动应用程序外,还可以
与数据库进行通信以生成对用户有用的内容。 大多数 Web 服
务器平台都将应用程序与服务器捆绑在一起,即使最简单的网
站也会与 Web 应用进行交互,这就为攻击提供了更多的机会。
由于 Web 服务通常会自动打开,访问控制机制的应用在
有些情况下是不切实际的。 此外 Web 服务器在结构方面很复
杂,在一个位置安装所有保护机制也不可能达到理想效果,在
那些防御机制有效的地方,需要的配置变化依赖于引起攻击的
根源和特殊的 Web 服务结构。 有一些策略可以使入侵者绕过
IDS 或使 IDS 不起作用。 例如,入侵者可以试图使网络溢出或
在虚拟包中插入一些新的恶意包来实现上述策略
[3]
。 针对
Web 攻击,目前主要的措施是采用入侵检测系统( IDS) 尽快、
尽可能可靠地检测出各种入侵行为
[4]
。 IDS 同时能对数据帧
的帧头与负载进行检测,并与已知的所有攻击方式进行比较,
找出可能的攻击方式。 也就是说,如果将数据包流当做一个很
长的字符串,IDS 的工作就是检测该字符串中的子字符串是否
与已知的攻击模式相符,并根据预定的方案采取相应的防范措
施,以阻挡使用者或以报警的方式进行处理。 针对字符串扫描
检测,文献[5,6] 分别采用哈希与基于签名的方式,虽然这些
方法能快速地找出可能的攻击模式,但是无法避免错误匹配问
题。 而 Snort
[7]
方法在字符串检测上花费高达 70%的执行时间
和 80%的指令执行时间,效率并不理想。
本文针对 Web 入侵检测系统中存在的攻击模式误匹配与
效率问题,提出了一种高效的多模式匹配算法 MPMA。 该算法
基于比较树,利用( 模式,偏移) 信息对来搜索可能的匹配模
式,比较树通过每个节点存储相应的位置信息,记录下次比较
的字符位置以提高搜索效率。
1 多模式匹配算法 MPMA
1畅1 问题描述
对于检测的数据包形成的字符串,定义为 T,T 内每个字
符表示为 t
1
,t
2
,…,t
|T |
。 其中|T |表示 T 的长度。 查找的 n 个
不同的模式定义为 P
i
(i∈[1,n]),P
y
=p
(y)
1
p
(y)
2
…p
( y)
|p
y
|
(y∈[1,
n])。 多模式匹配算法 MPMA 的目的就是要找出上一个位置
x 和 P
y
,满足以下条件:
t
x +i
=p
y
i
,i∈[1, |p
y
|] (1)
第 26 卷第 4 期
2009 年 4 月
计 算 机 应 用 研 究
Application Research of Computers
Vol.26 No.4
Apr.2009