入侵检测系统中一种模式匹配算法的研究与改进
- 格式：pdf
- 大小：180.47 KB
- 文档页数：3
下载文档原格式
合集下载
Snort中BM模式匹配算法的研究与改进
－ － － ３ － ５ ４ ３ － － １ ３ ０ ８ ９ １
当 Ｐ中字符 。与 Ｔ中 对应字 符 ｂ失配 时 ， 同时共有 ３ 条 启发性规 则指导 Ｐ滑动 （ Ｔ为参 照 ） 以 到下一个适 当 的位置 ， 哪种规则 下滑动的距离最大 ， 便采 用哪一种 。
ａ Ｏ． ｔｒ） － ｄｌ２ｊ： ｅｔ （ ａ ）
０ ￥
－ － ６
１
２ ３
４
５ ６
７
的第一 步是 将 目标 串 Ｔ与模 式 串 Ｐ两 者的左 端对齐 ，
然后从 Ｐ的末字符 开始往 左对 比 Ｔ中相 对应 的字符 。
Ｈ Ｄ Ｂ Ｈ Ｂ Ｈ Ｂ Ｈ
１ １ １ １ ６ ５ ４ ３ ２ １ ６ ０
表 ２
规则一 ， 如果 ｂ没有被包含在 模
式 串 Ｐ中 ， 么 Ｔ中从 ｂ开始 ， 那 长度 等 于 ｓｔｎ Ｐ ＝ ｍ 的子 串是 不可 ｔ （） ｒ ｅ 能和 Ｐ匹配成功的。
规 则二 ， 如果 ｂ被包 含在 Ｐ中 ，
关键 词 ： 式 匹 配 Ｂ 算 法 入 侵 检 测 Ｓ ｏ 模 Байду номын сангаас ｎｄ
１ 引言
模 式匹配是 指在一个 目标文本 Ｔ中查找某个特定 的子串 ， 使得 这个子 串 与已知的模 式 串 Ｐ相等 。如 果 在 Ｔ中找到等于 Ｐ 的子 串， 则称匹配成功 ，
统（Ｄ ） Ｉ 的工 作 效 率。著 名 的轻 量 级 入 侵 检 测 系统 Ｓ ｓｎ ｏ ｄ采用的是 Ｂ 模 式 匹配算 法 ， Ｍ 该算 法被 称为 亚线 性 算法 ， 平均 匹配速度 比 同类型 的 Ｋ 其 ＭＰ算法还要 快 ３ —５倍 。本 文对 Ｂ 算 法进行 了改进 ， Ｍ 使之 更适合 与
当 Ｐ中字符 。与 Ｔ中 对应字 符 ｂ失配 时 ， 同时共有 ３ 条 启发性规 则指导 Ｐ滑动 （ Ｔ为参 照 ） 以 到下一个适 当 的位置 ， 哪种规则 下滑动的距离最大 ， 便采 用哪一种 。
ａ Ｏ． ｔｒ） － ｄｌ２ｊ： ｅｔ （ ａ ）
０ ￥
－ － ６
１
２ ３
４
５ ６
７
的第一 步是 将 目标 串 Ｔ与模 式 串 Ｐ两 者的左 端对齐 ，
然后从 Ｐ的末字符 开始往 左对 比 Ｔ中相 对应 的字符 。
Ｈ Ｄ Ｂ Ｈ Ｂ Ｈ Ｂ Ｈ
１ １ １ １ ６ ５ ４ ３ ２ １ ６ ０
表 ２
规则一 ， 如果 ｂ没有被包含在 模
式 串 Ｐ中 ， 么 Ｔ中从 ｂ开始 ， 那 长度 等 于 ｓｔｎ Ｐ ＝ ｍ 的子 串是 不可 ｔ （） ｒ ｅ 能和 Ｐ匹配成功的。
规 则二 ， 如果 ｂ被包 含在 Ｐ中 ，
关键 词 ： 式 匹 配 Ｂ 算 法 入 侵 检 测 Ｓ ｏ 模 Байду номын сангаас ｎｄ
１ 引言
模 式匹配是 指在一个 目标文本 Ｔ中查找某个特定 的子串 ， 使得 这个子 串 与已知的模 式 串 Ｐ相等 。如 果 在 Ｔ中找到等于 Ｐ 的子 串， 则称匹配成功 ，
统（Ｄ ） Ｉ 的工 作 效 率。著 名 的轻 量 级 入 侵 检 测 系统 Ｓ ｓｎ ｏ ｄ采用的是 Ｂ 模 式 匹配算 法 ， Ｍ 该算 法被 称为 亚线 性 算法 ， 平均 匹配速度 比 同类型 的 Ｋ 其 ＭＰ算法还要 快 ３ —５倍 。本 文对 Ｂ 算 法进行 了改进 ， Ｍ 使之 更适合 与
入侵检测系统中模式匹配算法研究
法 。该 算 与 文本 串 失 败 的当
文本
ｑ
ｄ ｅ ｂ
ｄ
ｂ
ｄ
ｄ
第
趟
ｂ ｄ
ｄ
ｂ ｄ ｂ ｄ ｄ ｄ
ｂ ｄ ｄ
按 Ｂ 的 Ｍ
不 出现 ，
筇 ． 趟 ｊ 趟
趟
一 璧 ｜ 童 Ⅲ
字 符 是 否 与 模 式 串 Ｐ［］ 等 ，若 相 等 ，则 将 Ｐ［ １相 １ ］
定义一 个 从字母 到 正 整数 的映 射 ：
ｄｔ ｉ． ｓ ｎ ， ＂ ， ： ｝
ＢＭ 算 法 采 用 “ 跃 式 ” 查 找 策 略 ，多数 情 况 跳
下不 需 要 对文 本 进 行一 次 完 整 的扫描 。假设 在 执行
正文 中 自位 置 ｉ “ 前 ” 的一 段 与模 式 的 自右至 起 返
入侵检测 系统 中模式 ｐ ］ ｃｉ ｍ 算法研 究
李 君 秋 ，王 法 能
（ 大连 装备制 造职 业技 术学 院 ， 宁 大连 １ ６ ） 辽 １０ １ １
霜
摘 要 ：分析 了Ｂ ，Ｋ Ｐ Ｍ模 式匹配算法 ，在此算法的基础上提 出 了一种改进的模 式 匹配算法 （Ｂ ） Ｆ Ｍ ，Ｂ Ｆ Ｍ ，该算 法的思想是对 Ｂ Ｍ
根 据 滑 动 距 离 函 数 ｄ ｓ 则 模 式 串 向右 滑 动 ５个 字 ｉｔ 符 ：第 二 趟 从 文 本 串 的第 ９个 字 符 自右 向左 比较 ， ３ ，Ｔ［１ ＝ ［１ ７ ｇ Ｐ ３，根 据滑 动 距离 … ｉｔ ｓ
该算 法 的关键 是求 ｎ ｘ ｅ ｔ函数 的修正 值 ：
ｋ Ｉ ＝Ｐ ＼Ｐ
ｌ “也
１
２３Ｂ ． Ｍ算法
入侵检测系统中的模式匹配算法研究
方 向。 关 键 词 ： 侵 检 测 ； 式 匹 配 ； ＭＰ算 法 ； Ｍ 算 法 ； Ｃ算 法 ； 端 分段 匹 配算 法 入 模 Ｋ Ｂ Ａ 两
中图 分 类 号 ：Ｐ ０ Ｔ３１
文 献 标 识 码 ： Ａ
文 章 编 号 ：６ ３ １８ （０ ０ ０ — １９ ０ １７ — ９ ０ ２ １ ）２ ０ ５ — ４
常快 ， 实际 比较次数只有 目标 串长度 的 ２ ％～ ０ ０ ３％。
符 不 匹 配 ， 将模 式 串右 滑 距 离 ｄ ， 则 ）执行 由 Ｐ ｍ与
＋ ） ｄ 起始 的 自右 至左 的匹配检 查 。 Ｍ 算法采 用两 Ｂ 条规则 计算 模 式 串右移 的距离 ： 后 缀 移动 和 坏字 好 符 移动 。 （ ） 后缀 移动 ， １好 分两种 情况 。
收 稿 日期 ： ０ ９ ０ — ０ ２ ０ — ９ ３
发 ． ｏｅ 和 Ｍｏｒ 提 出一种 新 的快速 字符 串匹 配算 Ｂ ｙｒ ｏｅ
法一 Ｂ 算 法 ［ ｌ Ｍ 。 ． ６
Ｂ 算法 基 本思 想是 ：开始 时 将 目标 串 与模 Ｍ
式 串 Ｐ左对 齐 ， 自右 至左 逐个 字符 进行 比较（ 即首先
１ 单 模 式 匹 配 算 法
（） １ 模式 匹 配 。在 给定 长度 为 凡的 目标 串 中
查找 长度 为 ｍ 的模 式 Ｐ首 次 或多 次 出现 的过程 ，
，
ｍ ｘｋｌｋｊ且 Ｐ … ： ａ｛ｌ ＜ ， ＜ ２
ｎ ｘ￣＝ ｅｔ］ ０
一
∥‘ 。 ‘ ） 一
集 合非 空 其 他情况 ｊ ｏ时 ＝
等传统 安 全保护 措施后 的新 一代 安 全保 障技术 。模
式 匹配算法 是基 于特 征匹 配 的入 侵检 测 系统 中的核 心算 法 。据 统计 ， 现在 大约 ９ ％的入 侵 检 测都 是 特 ５ 征 匹配 的人 侵检 测 。 由此 可见 ， 式 匹 配算 法 性 能 模 的优劣 直接 影响 到入侵 检测 系统 的效 率 。在此介 绍 几 种用 于入侵 检 测 的经 典模 式 匹 配算 法 ． 在 此基 并 础 上提 出一种 入 进算 法 ． 后 给 出人 侵 检测 系 统 中 最 模 式匹 配算法 的选 择策 略 。
中图 分 类 号 ：Ｐ ０ Ｔ３１
文 献 标 识 码 ： Ａ
文 章 编 号 ：６ ３ １８ （０ ０ ０ — １９ ０ １７ — ９ ０ ２ １ ）２ ０ ５ — ４
常快 ， 实际 比较次数只有 目标 串长度 的 ２ ％～ ０ ０ ３％。
符 不 匹 配 ， 将模 式 串右 滑 距 离 ｄ ， 则 ）执行 由 Ｐ ｍ与
＋ ） ｄ 起始 的 自右 至左 的匹配检 查 。 Ｍ 算法采 用两 Ｂ 条规则 计算 模 式 串右移 的距离 ： 后 缀 移动 和 坏字 好 符 移动 。 （ ） 后缀 移动 ， １好 分两种 情况 。
收 稿 日期 ： ０ ９ ０ — ０ ２ ０ — ９ ３
发 ． ｏｅ 和 Ｍｏｒ 提 出一种 新 的快速 字符 串匹 配算 Ｂ ｙｒ ｏｅ
法一 Ｂ 算 法 ［ ｌ Ｍ 。 ． ６
Ｂ 算法 基 本思 想是 ：开始 时 将 目标 串 与模 Ｍ
式 串 Ｐ左对 齐 ， 自右 至左 逐个 字符 进行 比较（ 即首先
１ 单 模 式 匹 配 算 法
（） １ 模式 匹 配 。在 给定 长度 为 凡的 目标 串 中
查找 长度 为 ｍ 的模 式 Ｐ首 次 或多 次 出现 的过程 ，
，
ｍ ｘｋｌｋｊ且 Ｐ … ： ａ｛ｌ ＜ ， ＜ ２
ｎ ｘ￣＝ ｅｔ］ ０
一
∥‘ 。 ‘ ） 一
集 合非 空 其 他情况 ｊ ｏ时 ＝
等传统 安 全保护 措施后 的新 一代 安 全保 障技术 。模
式 匹配算法 是基 于特 征匹 配 的入 侵检 测 系统 中的核 心算 法 。据 统计 ， 现在 大约 ９ ％的入 侵 检 测都 是 特 ５ 征 匹配 的人 侵检 测 。 由此 可见 ， 式 匹 配算 法 性 能 模 的优劣 直接 影响 到入侵 检测 系统 的效 率 。在此介 绍 几 种用 于入侵 检 测 的经 典模 式 匹 配算 法 ． 在 此基 并 础 上提 出一种 入 进算 法 ． 后 给 出人 侵 检测 系 统 中 最 模 式匹 配算法 的选 择策 略 。
入侵检测模式匹配算法研究
络数据分析 、 匹配 ． 判断网络中是否有 入侵企图。ｆ 定所有入侵行为和手
系统 一般不单独采川 Ｋ ｕｈ ＰａｔＭｏｒ 算法 ．而是配 合其他算法 ｎ ｔ— ｒｔ ｒｉ — ｓ
共同实现。
段（ 及其变种 ） 都能够表达 为一种模式或特 征 ， 那么所有 已知的入侵方 法 都可 以用模式匹配 的方法 发现 。一般 意义上的模式 匹配算法非 常多 ， 本 文只研究 与入侵检测直接 相关 的算法 ，主要有 Ｂｕ ｒ 算法 ， ｎ ｔ ｒｔ Ｆ ｃ ｅｏｅ Ｋｕ — ｈ
ＰａｔＭｏｒ 算法 ，ｏｅ— ｏｅ ｒｔ — ｒｓ ｉ Ｂ ｙｒ Ｍｏｒ 算法 、ｈ — ｏ ｉｋ算法 、ｅ— ｉ ｏｅ— Ａ ｏ Ｃ ｍｓ ｃ ｓ Ｉｗ ｓ Ｂ ｙｒ ｅ Ｍｏｒ— ｒｐｏ 算法 ，ｈ — ｏ ｉｋ Ｂ ｙｒ Ｍｏｒ 算法 。 ｏｅ Ｈｏｓｏｌ Ａ ｏ Ｃ ｍｓ — ｏｅ— ｏ ｅ ｃ
Ｂ ｙｒＭｏｅ 算法先将 Ｐ Ｔ左端对齐 ．然后按 照从右 向左的模式从 ｏｅ— ｏｒ ， 摸式 串最右一个字符开始扫描 。在不匹配的情况下 （ 或者整个字符串完
全匹配 ） ， 它用两个预处理 函数决定右移的长度 。 这两个 函数分别 叫做好
后缀移 动函数 （ 叫匹配移动 ） 也 和坏字符移动 函数 （ 叫出现移动 ） 也 。
法、 ｏｅ＇ ｏｅ 算法 、 ｈ — ｏａｉｋ算法 、ｅ－ ｉ ｏｅ— ｏｒ— ｏ ｐｏ 算法和 Ａ ｏ Ｂ ｙｒＭｏ ｒ Ａ ｏ Ｃ ｒｓ ｃ Ｓ ｔｗｓ Ｂ ｙｒ Ｍ ｏｅ Ｈ ｍ ｏｌ ｅ ｈ—
Ｃ ｒｓ ｃ ｏ ａｉｋ
—
Ｂ ｙｒＭ ｏｅ算法。 ｏｅ— ｏ ｒ
文献标识码 ： Ａ
２３ 系 统应 用 －
１ Ｂ ｕ ｏｃ ｒｔ Ｆ ｒｅ算法 ｅ
系统 一般不单独采川 Ｋ ｕｈ ＰａｔＭｏｒ 算法 ．而是配 合其他算法 ｎ ｔ— ｒｔ ｒｉ — ｓ
共同实现。
段（ 及其变种 ） 都能够表达 为一种模式或特 征 ， 那么所有 已知的入侵方 法 都可 以用模式匹配 的方法 发现 。一般 意义上的模式 匹配算法非 常多 ， 本 文只研究 与入侵检测直接 相关 的算法 ，主要有 Ｂｕ ｒ 算法 ， ｎ ｔ ｒｔ Ｆ ｃ ｅｏｅ Ｋｕ — ｈ
ＰａｔＭｏｒ 算法 ，ｏｅ— ｏｅ ｒｔ — ｒｓ ｉ Ｂ ｙｒ Ｍｏｒ 算法 、ｈ — ｏ ｉｋ算法 、ｅ— ｉ ｏｅ— Ａ ｏ Ｃ ｍｓ ｃ ｓ Ｉｗ ｓ Ｂ ｙｒ ｅ Ｍｏｒ— ｒｐｏ 算法 ，ｈ — ｏ ｉｋ Ｂ ｙｒ Ｍｏｒ 算法 。 ｏｅ Ｈｏｓｏｌ Ａ ｏ Ｃ ｍｓ — ｏｅ— ｏ ｅ ｃ
Ｂ ｙｒＭｏｅ 算法先将 Ｐ Ｔ左端对齐 ．然后按 照从右 向左的模式从 ｏｅ— ｏｒ ， 摸式 串最右一个字符开始扫描 。在不匹配的情况下 （ 或者整个字符串完
全匹配 ） ， 它用两个预处理 函数决定右移的长度 。 这两个 函数分别 叫做好
后缀移 动函数 （ 叫匹配移动 ） 也 和坏字符移动 函数 （ 叫出现移动 ） 也 。
法、 ｏｅ＇ ｏｅ 算法 、 ｈ — ｏａｉｋ算法 、ｅ－ ｉ ｏｅ— ｏｒ— ｏ ｐｏ 算法和 Ａ ｏ Ｂ ｙｒＭｏ ｒ Ａ ｏ Ｃ ｒｓ ｃ Ｓ ｔｗｓ Ｂ ｙｒ Ｍ ｏｅ Ｈ ｍ ｏｌ ｅ ｈ—
Ｃ ｒｓ ｃ ｏ ａｉｋ
—
Ｂ ｙｒＭ ｏｅ算法。 ｏｅ— ｏ ｒ
文献标识码 ： Ａ
２３ 系 统应 用 －
１ Ｂ ｕ ｏｃ ｒｔ Ｆ ｒｅ算法 ｅ
入侵检测系统模式匹配算法研究【文献综述】
毕业设计文献综述计算机科学与技术入侵检测系统模式匹配算法研究一、前言部分计算机网络的发展使人们的工作、学习和生活更加高效和便利，但借助于网络的入侵行为的数量和破坏性也不断增加。
近年来，网络安全事件呈爆炸性增长，安全问题日益突出。
根据CERT／CC的统计，1994年安全事件为2 340件，而2003年这一数字己达到137529件(此项统计截至于2003年) [1] .网络安全是指利用网络管理和控制技术，保证网络系统的硬件，软件及其系统中的数据不被偶然的或者恶意的原因破坏，更改，泄漏，保持系统连续可靠正常地运行，网络服务不中断。
网络安全从其本质上来讲就是网络上的信息安全。
它涉及到网络上信息的保密性，完整性，可用性，真实性和可控性的相关技术和理论。
网络安全应该具有保密性、完整性、可用性、可控性和正确性五个方面的特征[2]。
面对日益加剧的网络安全威胁，传统的静态安全技术如认证机制、加密和防火墙等已经难以胜任。
为此，我们需要尽可能找到更好的措施以保护系统免受入侵者的攻击。
要求事先设置规则。
对于实时攻击或异常行为不能实时反应。
无法自动调整策略设置以阻断正在进行的攻击。
因而出现了入侵检测系统[3]。
入侵检测系统(Intrusion Detection System ，IDS)可以弥补防火墙技术的不足，对网络或操作系统上的可疑行为作出策略反应，及时切断资料入侵源，记录并通过各种途径通知网络管理员，以求最大幅度地保障系统安全。
它是防火墙的合理补充，可以帮助系统对付网络攻击，扩展系统管理员的安全管理能力(包括安全审计、监视、进攻识别和响应)，从而提高信息安全基础结构的完整性，被认为是防火墙之后的第2道安全闸门。
它能在不影响网络性能的情况下监测网络，从而提供对内部攻击、外部攻击和误操作的实时保护[4]。
入侵检测作为一种重要的动态安全技术，能够提供对计算机系统和网络的外部攻击、内部攻击及误操作的全面检测，其主要功能是监视并分析用户和系统的行为、审计系统构造和弱点、评估重要系统图、安全事件报告数据和数据文件的完整性、识别己知攻击的行为模式、异常行为模式的统计分析、操作系统的审计跟踪管理和识别用户违反安全策略的行为。
ID3算法在入侵检测系统中的研究与改进
ｔｅ ｅｔ ｎ ． Ｔ ｔ ｉ ｆｕｔ， ａ ｊ ｒｖ ｄ ｄｃｓ ｎ ｒｅ ｌｏｉｈ ｗａ ｐｏｏｅ ｈ ｂ ｓ ｏ ｅ ｏ ｈｓ ａ ｌ ｎ ｍｐｏ ｅ ｅｉｉ ｔｅ ａｇ ｒｔｍ ｏ ｓ ｒｐｓｄ． Ｔ ｏｇ ｉ ｒｖ ｄ ｎ ｏｍａ ｉｎ ａｎ， ｓｌ ｔ ｇ ｈ ｂ ｓ ｄｖｓｏ ｈ ｕ ｈ ｍｐｏ ｅ ｉｆｒ ｔ ｇ ｉ ｏ ｅ ｃ ｉ ｔｅ ｅｔ ｉｉ ｎ ｅ ｎ ｉ ａ ｔｉｕｅ ， ｔ ｅ ａａ ｏｌｃｅ ｗａ ｃａｓｆ ｄ ｔｅ ｔｅ ｅｉｏ ｔｅ ｗｉｈ ｅｓ ｒ ｎｈ ｓ ｎ ｌｗｅ ｈｉｈ ｗａ ｃｅ ｔ ｄ Ｔｈ ａｇ ｒ ｈ ｔ ｒ ｔ ｓ ｈ ｄ ｔ ｃ ｌ ｔｄ ｂ ｅ ｓ ｌｓｉｉ ， ｈｎ ｈ ｄｃｓ ｎ ｒｅ ｔ ｌｓ ｂａ ｃｅ ａｄ ｏ ｒ ｅｇ ｔ ｅ ｉ ｓ ｒａ ｅ ． ｅ ｌｏｉ ｍ， ｃｍｂ ｉｇ ｔ ｏ ｉｎ ｎ
本 总数 。其 中对于给 定子 集的期 望信 息为 ：
或程 序足够 的 “ 正常 的”和 “ 常的” 审计数 据 ， 异 然后应
用一个 分类 算法 训练分 类器 ， 使之 可 以标识 或预测 属于正
常类 型或异 常类 型的新 的未 见过 的特征 。决策 树算 法是 比 较常用 的有效 分 类方法 ，而 Ｉ ３ Ｄ 算法是 决策树 的核 心算法 。
ｗｉ ｐ ｔｅｎ ｔ ａ ｔｒ ｍａ ｃ ｈ ｔｈ， ｗａ ｕｅ ｔ ｄ ｔｃ ｉｔｕｆｎ ． Ｅ ｐ ｒ ｎ ａ ｒｓｌ ｓｏ ｄ ｈ ｅ ｆｃ ｉｅｅｓ ｆ ｈ ａｇ ｒ ｈ ｓ ｓｄ ｏ ｅ ｅｔ ｎｒｓ ｓ ｏ ｘ ｅｉ ｔ ｆ ｅｕｔ ｈｗｅ ｔｅ ｆ ｅｔｖ ｎｓ ｏ ｔ ｅ ｌｏｉ ｍ， ｆ ｌ ａａ ｍ ａ ｅ ｎ ｏ ｓｉｎ ｍｅ ｓ ｔ ａｓ ｅ ｌｒ ｒ ｔ ａ ｄ ｍｉ ｏ ｓ
本 总数 。其 中对于给 定子 集的期 望信 息为 ：
或程 序足够 的 “ 正常 的”和 “ 常的” 审计数 据 ， 异 然后应
用一个 分类 算法 训练分 类器 ， 使之 可 以标识 或预测 属于正
常类 型或异 常类 型的新 的未 见过 的特征 。决策 树算 法是 比 较常用 的有效 分 类方法 ，而 Ｉ ３ Ｄ 算法是 决策树 的核 心算法 。
ｗｉ ｐ ｔｅｎ ｔ ａ ｔｒ ｍａ ｃ ｈ ｔｈ， ｗａ ｕｅ ｔ ｄ ｔｃ ｉｔｕｆｎ ． Ｅ ｐ ｒ ｎ ａ ｒｓｌ ｓｏ ｄ ｈ ｅ ｆｃ ｉｅｅｓ ｆ ｈ ａｇ ｒ ｈ ｓ ｓｄ ｏ ｅ ｅｔ ｎｒｓ ｓ ｏ ｘ ｅｉ ｔ ｆ ｅｕｔ ｈｗｅ ｔｅ ｆ ｅｔｖ ｎｓ ｏ ｔ ｅ ｌｏｉ ｍ， ｆ ｌ ａａ ｍ ａ ｅ ｎ ｏ ｓｉｎ ｍｅ ｓ ｔ ａｓ ｅ ｌｒ ｒ ｔ ａ ｄ ｍｉ ｏ ｓ
一种改进的入侵检测模式匹配算法
ｄ ｔｃ ｉ ｎ ｔ ｃ ｎ ｌ ｇ ａ ｅ ｏ ｎ ｉ ｏ ｔ ｎ ｏ ｏ ｅ ｔ ｏ ｅｗｏ ｋ ｓ ｃ ｒｔ ｅｅ ｔ ｅ ｈ ｏ ｏ ｙ ｈ ｓ ｂ ｃ ｍｅ ａ ｍｐ ｒａ ｔ ｃ ｍｐ ｎ ｎ ｆ ｎ ｔ ｒ ｅ ｕ ｉ ｏ ｙ．Ｔ ｉ ｐ ｐ ｒ ｉ ｔ ｄ ｃ ｓ ｔ ｅ ｂ ｓｃ ｆ ｉ ｔ ｓｏ ｈ ｓ ａ ｅ ｎ ｒ ｕ ｅ ｈ ａ ｉ ｓ ｏ ｎ ｒ ｉｎ ｏ ｕ ｄ ｔｃ ｉ ｎ ａ ｄ ｉ ｔ ｉ ｎ ｄ ｔｃ ｉ ｎ ｏ ｈ ｅｅ ｔ ｎ ｎ ｒ ｏ ｅｅ ｔ ｎ ｔ ｅ ＢＭ ｌ ｏ ｉ ｍ ｏ ａ ｔｒ ｔｈ ｎ ｎ ｌ ｓｓ ｎ ｎ ｔ ｉ ｂ ｓｓ ｈ ｍｐ ｏ ｅ ｏ ｕｓ ｏ ａｇ ｒ ｈ ｆ ｒ ｐ ｔ ｎ ｍａｃ ｉ ｇ ａ ａｙ ｉ，ａ ｄ ｏ ｈ ｓ ａ ｉ，ｔ ｅ ｉ ｒ ｖ ｄ ＧＢＭ ｔ ｅ ｐ ｏ ｏ ｅ ｌｏ ｉ ｍ ｆｅ ｔ ｅｙ ｉ ｒ ｖ ｓ ｈ ｆ ｃｅ ｃ ｆ ａｔ ｒ ｔｈ ｎ ． ｒ ｐ ｓ ｄａ ｇ ｒ ｈ ｅ ｃ ｉ ｌ ｔ ｖ ｍｐ ｏ ｅ ｅ ｅ ｉｎ ｙ ｏ ｔ ｎ ｍａｃ ｉ ｇ ｔ ｉ ｐ ｅ
Ｋｅ ｙ ｗｏｒ ：ｎｔｕ ｉ ｎ ｅｔｃ ｉｎ； ｔｅ ａｃ ｎｇ ｄｓ ｉ ｒ ｓｏ ｄ ｅ ｔｏ ｐａｔ ｒ ｍ ｔｈｉ ；ＢＭ ｌ ｒｔ ；Ｓ ｒ ｎ ａｇｏ ｉｈｍ ｎｏ ｔ
引 言
随着 网络 的越来 越普 及，网络 攻击 、非 法访 问等 事件 的数 量飞 速增 长，网络 安全 形势 日益 严峻 ，网络 安 全逐 渐成 为Ｉｔ ｎｔ ｎｅ ｅ及各项 网络 服务 和应 用进一 步发 展 的关键 问题 …． 《 ＮＣ Ｒ ／Ｃ２０ 年 网络安 全 ｒ 据 Ｃ Ｅ ＴＣ ０ ９ Ｔ作报 告 》记载 ： ０ ９ ５ １ ２ ０ 年 月 ９日晚 间 ，中 国 部 分 省 区 市 发 生 了 大 面 积 网 络 异 常 ，导 致 很 多互 联 网用 户 的 网络 中 断 或 业 务 受 到 影 响 Ｉ．据美 国 《 融 时报 》报 道 ， ２ ］ 金 现在 平 均每２ 秒就 发生一 次计 算机 网络 人 ０
模式匹配算法的研究与改进
地提 高 了系统 的检测 性 能。
【 键词】 模 式 匹配算法 ，Ｂ 算法 ，Ｂ 关 Ｍ ＭＨ 算 法
中图 分 类 号 ：Ｔ ３ １ Ｐ ９ 文 献 标 识 码 ：Ａ
ＡＢ Ｔ Ｓ ＲＡＣＴ Ｗ ｉｈ ｔ ｅｒ ｐ ｄ ｄ ｖ ｌ ｐ ｅ ｔｏ ｈ ｅ ｗｏ ｋ，ｈ ｎ ｉ ｅ ｓ ｃ ｒｔ ｕ ｓ ｉｎ ｉ ｏ ｔ ｔ ｎ ｉ ｇ ｄ ｙ ｂ ａ ｉ ｔ ｕ ｉ ｎ ｄ ｔ ｃ ｉｎ ｔ ｈ ａ ｉ ｅ ｅｏ ｍ ｎ ｆ ｅ ｎ ｔ ｒ ｔ ｅｏ ｌ ｅ ｕ ｉ ｑ ｅ ｔｏ ｕ ｓａ ｄ ｎ ａ ｙ ｄ ｙ， ｒ ｓｏ ｅ ｅ ｔｏ ｔ ｎ ｙ ｓ ｎ ｔ ｃ ｎ ｑ ｅ ｎ ｗａ ａ ｓ ｂ ｃ ｍｅ ｈ ｏ ｕ ｉｈ ｔ ｅ ｓ ｃｅ ｙ ｐ ｙ ｌ ｓ ｔｅ ｔｏ ｏ ｅ ｈ ｉ ｕ ｏ ｄ ｙ ｅ ｏ ｓ ｔ ｅ ｆ ｃ ｓ ｗｈ ｃ ｈ ｏ ｉｔ ａ ｓｃ ｏ ｅ ａ ｔ ｎ ｉ ｎ ｔ ．Ｐ ｔ ｅ ｎ ｍａ ｃ ｉ ｇ ａ ｇ ｒ ｍ ｓａ ｅ ｖ ｒ ｐ ｒａ ｔ ａ ｔ ｒ ｔｈ ｎ ｌ ｏ ｉｈ ｒ ｅ ｙ ｉ ｏ ｔ ｎ ｍ
目前基 于 规则 人侵 检测 系统 常用 的算 法 。Ｂ 算 法 和 Ｍ ＫＭＰ算 法 的不 同是 对模 式 串 的扫 描方 式 由 自左 至 右
变 成 自右至左 ， 一个 是 考 虑 正文 中可 能 出现 的字 符 另 在模式 中的位 置 。这样 做 的好 处是 当正 文 中出现模 式
ｆ ｒ ｔ ｅｒ ｌ — ａ ｅ ｔ ｕ ｉ ｎ ｄ ｔ ｃ ｉｎ ｓ ｓ ｅ Ｉ ｉｅ ｔ ｌ ｅ ｃ ｓｔ ｅ ａ ｃ ｒ ｃ ｎ ｅ ｌｔ ｅｐ ｒｏ ｍａ ｃ ｆ ｈ ｙ ｔ ｍ ． ｅｐ ｐ ｒ ｏ ｈ ｕ ｅ ｂ ｓ ｄ ｉ ｒ ｓｏ ｅ ｅ ｔｏ ｙ ｔ ｍ． ｔ ｒ ｃ ｌ ｉ ｕ ｎ ｅ ｈ ｃ ｕ ａ ｙａ ｄ ｒ ａ －ｉ ｅ ｆ ｒ ｎ ｅｏ ｅ ｓ ｓ ｅ ｎ ｄ ｙ ｎｆ ｍ ｔ Ｔｈ ａ ｅ
【 键词】 模 式 匹配算法 ，Ｂ 算法 ，Ｂ 关 Ｍ ＭＨ 算 法
中图 分 类 号 ：Ｔ ３ １ Ｐ ９ 文 献 标 识 码 ：Ａ
ＡＢ Ｔ Ｓ ＲＡＣＴ Ｗ ｉｈ ｔ ｅｒ ｐ ｄ ｄ ｖ ｌ ｐ ｅ ｔｏ ｈ ｅ ｗｏ ｋ，ｈ ｎ ｉ ｅ ｓ ｃ ｒｔ ｕ ｓ ｉｎ ｉ ｏ ｔ ｔ ｎ ｉ ｇ ｄ ｙ ｂ ａ ｉ ｔ ｕ ｉ ｎ ｄ ｔ ｃ ｉｎ ｔ ｈ ａ ｉ ｅ ｅｏ ｍ ｎ ｆ ｅ ｎ ｔ ｒ ｔ ｅｏ ｌ ｅ ｕ ｉ ｑ ｅ ｔｏ ｕ ｓａ ｄ ｎ ａ ｙ ｄ ｙ， ｒ ｓｏ ｅ ｅ ｔｏ ｔ ｎ ｙ ｓ ｎ ｔ ｃ ｎ ｑ ｅ ｎ ｗａ ａ ｓ ｂ ｃ ｍｅ ｈ ｏ ｕ ｉｈ ｔ ｅ ｓ ｃｅ ｙ ｐ ｙ ｌ ｓ ｔｅ ｔｏ ｏ ｅ ｈ ｉ ｕ ｏ ｄ ｙ ｅ ｏ ｓ ｔ ｅ ｆ ｃ ｓ ｗｈ ｃ ｈ ｏ ｉｔ ａ ｓｃ ｏ ｅ ａ ｔ ｎ ｉ ｎ ｔ ．Ｐ ｔ ｅ ｎ ｍａ ｃ ｉ ｇ ａ ｇ ｒ ｍ ｓａ ｅ ｖ ｒ ｐ ｒａ ｔ ａ ｔ ｒ ｔｈ ｎ ｌ ｏ ｉｈ ｒ ｅ ｙ ｉ ｏ ｔ ｎ ｍ
目前基 于 规则 人侵 检测 系统 常用 的算 法 。Ｂ 算 法 和 Ｍ ＫＭＰ算 法 的不 同是 对模 式 串 的扫 描方 式 由 自左 至 右
变 成 自右至左 ， 一个 是 考 虑 正文 中可 能 出现 的字 符 另 在模式 中的位 置 。这样 做 的好 处是 当正 文 中出现模 式
ｆ ｒ ｔ ｅｒ ｌ — ａ ｅ ｔ ｕ ｉ ｎ ｄ ｔ ｃ ｉｎ ｓ ｓ ｅ Ｉ ｉｅ ｔ ｌ ｅ ｃ ｓｔ ｅ ａ ｃ ｒ ｃ ｎ ｅ ｌｔ ｅｐ ｒｏ ｍａ ｃ ｆ ｈ ｙ ｔ ｍ ． ｅｐ ｐ ｒ ｏ ｈ ｕ ｅ ｂ ｓ ｄ ｉ ｒ ｓｏ ｅ ｅ ｔｏ ｙ ｔ ｍ． ｔ ｒ ｃ ｌ ｉ ｕ ｎ ｅ ｈ ｃ ｕ ａ ｙａ ｄ ｒ ａ －ｉ ｅ ｆ ｒ ｎ ｅｏ ｅ ｓ ｓ ｅ ｎ ｄ ｙ ｎｆ ｍ ｔ Ｔｈ ａ ｅ
一种面向入侵检测的BM模式匹配改进算法
块 。数据分析模块涉及 到两个 问题 ， 即如何描述入侵行为与使 用什 么样 的算 法来快速 准确 地检测 出人侵行 为。本文针 对第
二个 问题对 入侵检测 中常用 的模 式匹配算 法进行了深入分析 ， 并提 出一个新 的 Ｂ Ｍ模式 匹配改进算 法。
中其他地方出现 ， 可 以将 Ｐ 向右 移 动 ， 则 直接使 这部 分对 齐 ，
本字符 串 Ｔ 。 … 和长度 为 ｍ（ ＝Ｔ ｍ≤ｎ 的模式字符 串 Ｐ＝ ）
Ｐ Ｐ …Ｐ ，Ｍ算法 的基本思想是 ： ２ Ｂ
护， 有效地弥补 了防火墙 的不足 ， 而且还 能结合 其他 网络安全
产品， 对网络安全进行全方位 的保 护 ， 有主 动性 和实 时性 的 具
（） １ 匹配从右至左进行。
且要求这一部分 尽可能 大 ，ｈｆ 函数通 过对 已经 匹配 部分 的 Ｓｉ ｔ 考查决定模式 向右移动 的距离 ， 也称好 后缀启发。 由于篇幅有限 ， 里不给出 Ｓｉ 数组和 Ｓ ｉ 这 ｈｆ ｔ ｋ ｐ数组 的算法 ， 只给 出 Ｂ Ｍ算法的 Ｃ语言描述 ：
远的距离 ， 两个数组 为 Ｓｉ 和 Ｓｉ。假设有 长度 为 ｎ的文 这 ｈｆ ｔ ｋｐ
Ｉｔ ｅ及各 项网络服务和应用进一步发展所 需解决 的关 键问 ｎｅ ｔ ｎ ｒ 题 。人侵检测技术是一种主 动的网络安全 防御措施 ， 它不仅可
以通过监测 网络实现对 内部攻击 、 外部攻击和误操作的实时保
中图法分 类号 ：Ｔ ３ ２ Ｐ １ 文 献标识 码 ：Ａ 文章 编号 ：１０ —６ ５ ２０ ） １０ ８ —３ ０ １３ ９ （ ０ ６ １ －０ ９ ０
Ｉ ｒ ｖ ｄ Ａｌｏ ｉｈ ｏ ｍｐ ｏ ｅ ｇ ｒｔ ｍ ｆＢＭ ｏ ｎ ｒ ｓｏ ｔ ｃ ｉ ｎ ｆ ｒ Ｉ ｔｕ ｉ ｎ Ｄｅ ｅ ｔｏ
入侵检测中单模式匹配算法的研究与分析
重 的安 全威 胁 防火 墙技 术作 为一 种被 动 的安 全 防御机
制 来 保 证 网络 系 统 的 安 全 。 作 为防火 墙 的一种 补充 ， 入侵 检 测 系统 （ Ｉ Ｄ Ｓ ： Ｉ ｎ ｔ ｒ ｕ ｓ ｉ ｏ ｎ Ｄ ｅ ｔ ｅ ｃ ｔ ｉ ｏ ｎ Ｓ ｙ ｓ ｔ ｅ ｍ） 以 主动 的方 式 。 通 过监 视 、 分 析用 户及 系统 活动 ， 发 现 入 侵 企 图 或 异 常 现
为影 响 网络入侵 检测 系统性 能 的主要 因素嘲 本 文 主 要 研
究和 比较 了几种 典型 的单模 式匹 配算 法
二、 模 式 匹 配 问 题 概 述
够 跳过 一些 文本 字符 ．因而使 得采 用基 于后 缀 搜索 的 模 式 匹配 算法 具有 亚 线性 的平均 时 间复 杂度 基 于 子 串搜 索 的匹配法 的搜 索 方 向与基 于后 缀 的相 同 ．也 是从 后 向
式 匹 配算 法 的研 究 主 要有 寻 找更 为 简 单 的 匹配 算 法 、 寻
找 常量 空 间 的匹配算 法 、寻 找最优 平均 时 间复 杂度 的算
可 以扩展后 用 于多模 式匹 配 三、 相关 算法分 析
【 收稿 日期 】 ２ ０ １ ３ — ０ ５ — １ ０ 【 作者 简 介 】 万 民（ １ ９ ７ ７ 一 ） ， 男， 江西 南 昌人 ， 南昌 广播 电视 大 学信 息 中心 主任 ， 研 究方 向 ： 计 算 机 网络 ；
一
、
引 言
法 以及 寻 找能 够 匹配 扩 展模 式 串 的算 法 等 几 个方 向 ． 由 此也就 衍生 出 了众多不 同的匹配算 法
在 模 式 匹 配 的 实 现 过 程 中 ．则 主 要 有 基 于 前 缀 的 搜
模式匹配及其改进算法在入侵检测系统中的应用
配 的算法 。
移 动后 重新 开 始 比较 的 位 置仅 与模 式 串 Ｐ 有关 ， 而 与 目标 串 ７ 无 关 ， １ 因此 可 以通过 下 面 的 ｎ ｘ ｅ ｔ函数
事先 确定 。 ｆ ｘ ｋ ＜ｋ ｍａ ｛ Ｉ ｌ ＜歹且 Ｐ Ｐ …Ｐ 一 １２
．
入侵 检 测系统 的模式 匹 配算法 的实 质就是 将 收集 到 的信息 与 已知 的网络入 侵 和系统误 用模 式数 据库 进
是 否 匹配 。若 Ｔ ＜＞Ｐ ， 分 成 两种 情况 ： 则 若 ＝１ 则 ， 模 式 串右 移 一位 ， 查 丁 和 Ｐ 是 否 匹配 ； １ ＜ 检 若 ＜
＝ｍ， 模 式 串 右 移 是＝Ｊ ｎ ｘ （ ） ， 查 Ｔ 和 则 — ｅｔＪ 位 检 Ｐ ｅ ｔ 是 否 匹 配 。重 复此 过程 直 到 一优 或 ｉ ｎ结 ｎ ｘ（） －
束。
ｍ） ２ 字 符集 ）若 Ｐ 在 中 出现 １次或 多 次 ， ∈ ５（ ， 则
称 匹配 成功 ， 否则 称 匹配失 败 。 人 侵检 测 系统 的模 式 匹配算 法又 分为单 模式 匹配 算法 和 多模 式 匹配算法 。单 模式 匹配算 法是 指在 目标 串 中 １ 只 能对 １个模 式 串进行 匹配 的算法 。多模 式 次 匹 配算法 是 指在 目标 串 中可同时对 多个 模式 串进行 匹
模 式 匹 配是指 在 给定 长度 为 的 目标 串 Ｔ＝Ｔ Ｔ。
…
和 Ｐ 的 匹配 检查 。若 Ｔｆ 则继 续检 查 ＋和Ｐ ＋ —Ｐ ， ，１
中查 找长 度 为 的模式 串 Ｐ—Ｐ Ｐ …Ｐ 的首 次
—弋
出现或 多次 出现 的过 程 。 里 （ ≤ ， ， １ ≤ 这 １ ≤ ｚ Ｐ （ ≤歹 ）
移 动后 重新 开 始 比较 的 位 置仅 与模 式 串 Ｐ 有关 ， 而 与 目标 串 ７ 无 关 ， １ 因此 可 以通过 下 面 的 ｎ ｘ ｅ ｔ函数
事先 确定 。 ｆ ｘ ｋ ＜ｋ ｍａ ｛ Ｉ ｌ ＜歹且 Ｐ Ｐ …Ｐ 一 １２
．
入侵 检 测系统 的模式 匹 配算法 的实 质就是 将 收集 到 的信息 与 已知 的网络入 侵 和系统误 用模 式数 据库 进
是 否 匹配 。若 Ｔ ＜＞Ｐ ， 分 成 两种 情况 ： 则 若 ＝１ 则 ， 模 式 串右 移 一位 ， 查 丁 和 Ｐ 是 否 匹配 ； １ ＜ 检 若 ＜
＝ｍ， 模 式 串 右 移 是＝Ｊ ｎ ｘ （ ） ， 查 Ｔ 和 则 — ｅｔＪ 位 检 Ｐ ｅ ｔ 是 否 匹 配 。重 复此 过程 直 到 一优 或 ｉ ｎ结 ｎ ｘ（） －
束。
ｍ） ２ 字 符集 ）若 Ｐ 在 中 出现 １次或 多 次 ， ∈ ５（ ， 则
称 匹配 成功 ， 否则 称 匹配失 败 。 人 侵检 测 系统 的模 式 匹配算 法又 分为单 模式 匹配 算法 和 多模 式 匹配算法 。单 模式 匹配算 法是 指在 目标 串 中 １ 只 能对 １个模 式 串进行 匹配 的算法 。多模 式 次 匹 配算法 是 指在 目标 串 中可同时对 多个 模式 串进行 匹
模 式 匹 配是指 在 给定 长度 为 的 目标 串 Ｔ＝Ｔ Ｔ。
…
和 Ｐ 的 匹配 检查 。若 Ｔｆ 则继 续检 查 ＋和Ｐ ＋ —Ｐ ， ，１
中查 找长 度 为 的模式 串 Ｐ—Ｐ Ｐ …Ｐ 的首 次
—弋
出现或 多次 出现 的过 程 。 里 （ ≤ ， ， １ ≤ 这 １ ≤ ｚ Ｐ （ ≤歹 ）
入侵检测系统中模式匹配算法的改进
Ａｂｔａｔ ｓｒｃ
Ｉｔ ｓ ｎｄｔ ｔ ｎｓｓ ｍ （Ｄ ） ａ ｔ ｎｌ ｕｐｅ ｅ ｔｏｔ ｒｗ ｌ，ａ ｅｎｄｖｌ ｅ ｅｏｅｏ ｅｋｙｃｍ ｏ ｅｔ ｎｒ ｉ ｅ ｃ ｏ ｔ ｕｏ ｅ ｉ ｙ ｅ Ｉ Ｓ ，ｓ ｒ ｉ ａ ｓｐ ｌ ｎ ｅｆｅ ａｌｈｓ ｅ ｅｅｏ ｄｔ ｂ ｎ ｆｈ ｅ ｏ ｐ ｎｎ ａ ａｏ ｍ ｔ ｈ ｉ ｂ ｐ ｏ ｔ ｓ
ａｇ ｒｔ ｍ ｓａ ｌ ｒ ｔｄ ａ ｄ ｉ ｌ ｍｅ ｔｄ ｉ ｈ ｓ ｐ ｐ ｒ ｂ ｓ ｄ ｏ ｈ ｈ ｕ ｈ ｆｉ ｃ ｅ ｓｎ ｌ ｅ ｄ ｓ ｎ ｅ ｗ ｉ ｈ ａｔｒ ｏ ｓ ｎ ｔｍａ ｃ ． ｌ ｏ ｈ ｉ ｍｅ ｉ ａｅ ｍｐ ｅ ｎ ｅ ｎ ｔ ｉ ａ ｅ ａ ｅ ｎ ｔ ｅ ｔ ｏ ｇ ｔｏ ｎ ｒ ａ ｉ ｇ ｇ ｉ ｉｔ ｃ ｈ ｌ ｔ ｅ ｐ ｔ ｎ ｄ ｅ ｏ ｔｈ ｉ ｏ ｎ ｄ ａ ｅ ｅ
０ 引 言
随着 网络技术 的飞速发 展 ， 网络和计 算机 系统面临 的安全 威胁 也 日趋严 重 ， 侵 检测 系统 作为 一种 主动 的 、 入 实时 的人 侵检测 工具逐渐发展起来并成为 网络安全研究 的热点 。它可 以 在 不影响 网络性能 的情况下 对 网络 进行监 视 ， 而提供 对 内部 从
ｏ ｅｎ ｔ ｏ ｋ ｓ ｃ ｒ ｙ ｓ ｓｅ Ｉ Ｓ ｉ ｆ ｃｎ ｅ ｈ ｌ ｎ ｅ ｕ ｏｆ ｓ ｄ ｖ ｌ ｐ ｎ ｆ ｅ ｗ ｒ ｅ ｈ ｏ ｏ ｙ ａ ｄ ｔ ｅ ｅｏ ｅ ｎ ｅ ｓｔ ｅ ｉ ｒ ｖ ｄ ｆｔ ｅｗ ｒ ｅ ｕ ｔ ｙ ｔｍ． Ｄ ｓ ａ ｉ ｇ ｎ ｗ ｃ ａｌ ｇ ｓｄ ｅ ｔ ａ ｔ ｅ ｅ ｏ ｍｅ ｔｏ ｔ ｏ ｋ ｔ ｃ ｎ ｌｇ ｎ ｈ ｒ ｆｒ ｅ ｄ ｏ ｂ ｈ ｉ ｅ ｎ ｍｐ ｏ ｅ ｏ ｓｓ ｓ ｍ ｅ ｏｍａ ｃ ｓ ｔ ｒ ｕ ｈ ａｌ ｋ ｎ ｓ ｏ ｐ ｒ ａ ｈ ｓ ａ ｄ ｔ ｅ ｏ ｅ ａｉｎ ｅｆ ｉｎ ｙ ｏ ｕ ｅ ｍａ ｃ ｉ ｇ ｍｏ ｕ ｅ，ｈ ａｄ ｃ ｒ ｆ Ｉ ｆｉ ｙ ｔ ｐ ｒ ｒ ｎ ｅ ｈ ｏ ｇ ｌ ｉｄ ｆａ ｐ ｏ ｃ ｅ ， ｎ ｈ ｐ ｒ ｔ ｆ ｃｅ ｃ ｆｒ ｌ ｔ ｈｎ ｄ ｌ ｔ ｅ ｈ ｒ ｏ ｅ ｏ ＤＳ，ｓ ｔ ｅ ｆ ｏ ｉ ｉ ｓｒ ｉｈ ｆ ｅｅ ｙ ｔ ｅ ｐ ｒ ｒ ａ ｃ ｆ ｐ ｔ ｒ ｔｈ ｎ ｌｏ ｉ ｍ．Ｔ ｒ ｕ ｈ ｔｏ ｏ ｇ ｎ ｌ ｓ ｎ ｐ ｉ ｒ ｏ ｅ — ｏｅ ａｇ ｒ ｈ ，ｈ Ｍ ｔ ｇ ｔ ｅ ｔｄ ｂ ｈ ｅ ｏ ａ ｅ ｆ ｍ ｎ ｅ ｏ ａｔ ｎ ｍａｃ ｉ ｇ ａ ｇ ｒｔ ｅ ｈ ｈ ｏ ｇ ｈ ｒｕ ｈ ａ ａｙｉ ｏ ｒ ｓ ｍａｙ Ｂ ｙ ｒＭｏ ｒ ｌｏ ｔ ｍ ｔ ｅ Ｂ ｉ
入侵检测模式匹配算法的研究与改进
通过反复测试发现，在 比较的四个算法中， 新 算法 ｌ 每次查找所口配的次数最少 ， 效率方面与 Ｂ ＭＨ算法接近。 新算法 ２ 每次匹配的次数少于 Ｂ Ｍ 算法， 效率方面与 Ｂ Ｍ算法接近。通常在查找的模 ｛｝ｌ ｌ ｋｍ） ｋ１ ＜ ； 【叫 对应的字符的下一字符来按坏字符启发模式向右 式串出现在文本中重复率高时 ， 新算法的效率明显 若模式串 Ｐ 后面 ｋ 位和文本串 Ｔ中一致 的部 滑动相应的位数 ｓ 一 ， 重新进行比较。依次循环 ， 直到 高于 Ｂ Ｍ算法和 Ｂ ＭＨ算法。 分， 有一部分存模式串 Ｐ中其他部分 观 ， 则可将 完全匹配成功或都不匹配为止。 举例描述如表 ３所 ５Ｊ ／ 结 、 Ｐ向右移动， 直接使这部分对齐， 且要求这一致部分 示 ： 本文通过分析 Ｂ Ｍ和 Ｂ Ｈ等模式匹配算法 ， Ｍ 尽 可能 地大 。 本例中按改进后的算法匹配了四趟 ， 比较了 提出了…种以 Ｂ 共 Ｍ算法思想为基础，结合 Ｂ ＭＨ算 Ｂ Ｍ算法德语处理时间复杂度为 ０ｍ ｓ空问 ７ ６ 。 （＋】 ， ＋次 法的简化思想的进一步改进 Ｂ Ｍ算法的方法。 该算 复杂度为 （ｓ， ）ｊ ｆ 搜索阶段时间复杂度为 Ｏｍｎ。最坏 （） 改进 后的算法预处理时间复杂度为 ０ ， 空 法采用了 Ｂ Ｍ算法中的跳跃比较思想和 Ｂ Ｈ简化 Ｍ 情况下要进行 ３ ｎ次比较 ，最好 情况下的时间复杂 间复杂度为 ０ｓ搜索阶段时间复杂度为 Ｏｍ ） ｆ， 】 （ｎ。 方法以及向下一位匹配的思想 ， 进而简化了初始化 度为 （￣ｎ。 ＸＣＯ其中 ｍ为模式串 Ｐ的长度， ｎ为文本串 在模式串 Ｐ中重复的字符较多时或 Ｔ中字符 过程， 加大了匹配失败后向后跳跃的幅度 ， 减少了 Ｔ的长度，是与 ＰＴ相关的有限宁符集长度。 ｓ 、 大多在模式 串 Ｐ 现时 ， 中 该算法可进一步改进 比较次数 ， 提高了模式匹配效率。通过算法测试比 ２ ＭＨ算 ２ ．Ｂ 为， 若文本串Ｔ中与 模式串 Ｐ 最后字符对应的字符 较 ， 达到了预期效果 。 Ｂ Ｍ算法为了确定在不匹配的情况下最大的 以及其下—个字符都出现在模式串 Ｐ中， 比较两 则 参 考文献 可行移位距离而使用了两种启发， 即坏字符和好后 者最终按坏字符启发需要滑动的距离大小， 然后按 川 伊 刘培玉＿ 入侵检测中 模式匹配算法的 究ｌ 研 Ｊ Ｉ ． 缀启发。两种启发均能导致最大为 ｍ 若于模式串 滑动距离大的字符滑动， （ 重新进行比较。 计算机应用与软件２ Ｏ２２ ） ２ １４ Ｏ ５ ｎ：１＿ １． １ 进 一 步 的改 进 后 的 『牟永钦 李美贵， 入侵检测系统中模式匹配算 ２ １ 梁琦． 表 ３ 改进 算 法 １匹配过 程 算法增加了预处理时间 ， 法的研究叽电子学￣ ２ ０ ４１）４ ８ ０ ６ （２２８ — ３ ： 又章 串 Ｔ ｓ ａ ｓ ｒ ｃ ｈ １ ｎ ｇ ｓ ｅ ａ ｓ ｒ ｓ ｈ ｉ ｓ ｅ ａ ｒ ｈ … ４ ０ 和 比较选择滑 动距 离的 ２ ９ ． 第一次 ｓ ｅ ａ ｒ ｃ ｌ ’ 时间。由于只是在必要时 ｆ贺龙涛， ３ ］ 方滨兴， 余翔湛． 一种时间复杂度最优 的精 第 二孜 ｓ ｅ ａ ｒ ｃ ｈ 进行简单的大小 比较 ， 进 确 串匹配算法ｌ． Ｊ软件学报２ ０ ， （：７ ￣８． １ ０ ５ ５ ６ ６ ３ １ １ ６ 三次 ｓ ｅ ｜ ｌ ｃ ｈ １ 第 四次 ｓ ｅ ａ ｒ ｃ ｈ 行 比较所花 费的时间不 ＩＪ 孙克雷． ４ Ｉ ＤＳ中一种快速模式匹配算法ｌＩ Ｊ 安徽理 ． 说明 带 下划线 字母 衷示 发 生不匹 配，相 体 字母 代表 产生启 发 的字母 。 会太多。 该算法能够确保 工 大学 学４ ２ ０ ２ ０ ￣ ０ ６ ６
网络入侵检测系统模式匹配算法研究
周延 森 汪永好 ，
（．国 际关 系学 院 信 息科技 系，北京 １０９ ；２ １ ００ １ ．北京 电子 科技 学院 计 算机 科 学 与技 术 系， 北 京 １０７） ０００
摘 要 ： 式 匹配 算法是 网络入侵 检 测 中的关键 所在 ， 模 它直接 影响 到 网络入 侵检 测 系 的实时检 测性 能。引入 ４种模 式 匹配 算法， 分析 其 工作 原理 ， 通过 实验对 上述 ４ 算法 进行 了性 能测试 。 种 根据 实验 结果 ， 出了不 同算法 的应 用 范围 ， 得 为今 后入侵
检 测 系统 开发者 选择模 式 匹配算 法提供 了有价 值 的参考 。
关键词： 入侵检测；模式 匹配；羊模 匹配；多模 匹配；有限 自动机 中图法分类号：Ｐ０ 文献标识码： 文章编号：００ ０４ ￣ｏ） ７１５—３ Ｔ ３９ Ａ １０— ２ （ ８０— ２ ７ ｏ ６ ０
Ｒｅ ｅ ｒ ｈ ｏ ａｔｒ ａｃ ｉ ｇａｇ ｒｔｍｉ ｆ ｅｗｏ ｋ ｉ ｔ ｓｏ ｅｅ ｔ ｎ ｓ ｓｅ ｓ ａ ｃ ｎ ｐ ｔ ｎ ｍ ｔｈ ｎ ｌ ｏ ｉ ｅ ｈ ｃｏ ｔ ｒ ｒ ｉｎ ｄ ｔ ｃｉ ｙ ｔｍ ｎ ｎ ｕ ｏ
Ａｂ ｔ ａ ｔ Ｐ ｔ ｒ ｔｈ ｎ ｌ ｏ ｔ ｍ ｓｉ ｏ ｔｎ ｅｗｏ ｋ ｉ ｔ ｓｏ ｅ ｅ ｔｏ ｙ ｔ ｍ， ｗｈ ｃ ｆ ｅ ｃ ｓｒ ａ ｍ ｅ ｄ ｔ ｃｉ ｎ ｐ ｒｏ － ｓｒ ｃ ： ａｔ ｎ ｍａｃ ｉ ｇ ａｇ ｒ ｈ ｉ ｅ ｉ ｍｐ ｒ ｔ ｎ ｎ ｔ ｒ ｒ ｉｎ ｄ ｔ ｃｉ ｎ ｓ ｓｅ ａ ｉ ｎｕ ｉ ｈ ｉ ｌ ｎ ｅ ｅ ｌ ｉ ｅ ｅ ｔｏ ｅｆ ｒ ｎ ｕ ｔ ｍａ ｃ ｆ ｅ ｏ ｋ ｉ ｔ ｓｏ ｅｅ ｔ ｎ ｓ ｓｅ 。Ｆ ｕ ａ ｅ ｍａ ｃ ｉ ｇ ａｇ ｒｔｍ ｓａ ｅｉ ｔｏ ｕ ｅ ， ｔ ｅ ｅｒ ｒ ｉ ｇ ｐ ｎ ｉ ｌ ｎ ｓｅ ｎ ｅｏ ｎ ｔ ｒ ｒ ｉｎ ｄ ｔ ｃ ｉ ｙ ｔｍ ｗ ｎ ｕ ｏ ｏ ｒ ￣ ｍ ｔｈ ｎ ｌ ｏ ｉ ｐ ｈ ｒ ｒ ｄ ｃ ｄ ｈ ｎ ｔ ｉ ｗｏ ｋ ｎ ｒ ｃｐ ｅａ ｄｔ ｔ ｄ ｎ ｈ ｉ ｅ ｐ ｒｏ ｍ ａ ｃ ｆ ｏ ａｔ ｒ ｔｈ ｎ ｌ ｏ ｔ ｍ ｒ ｕ ｈ ｅ ｐ ｒｍｅ ｔ ｒ ａｙ ｅ ．Ａｃ ｏ ｄ ｎ ｘ ｅ ｉ ｎ ｓ ｌ ｔ ｎ ｕ ｅ ｐ ｌ ｉ ｇｒｎ ｅ ｅ ｒ ｎ ｅｏ ｆ ｕ ｐ ｔ ｎ ｍａ ｃ ｉ ｇａ ｇ ｒ ｈ ｔ ｏ ｇ ｅ ｆ ｒ ｅ ｉ ｈ ｘ ｉ ｎ ｅａ ｌ ｚ ｄ ａ ｎ ｃ ｒ ｉ ｇｅ ｐ ｒｍｅ ｔ ｅ ｕ ｔ ｓ ｓ ｐ ｙ ｎ ｇ ｒ ，ｉ ｅ ｒ ａ ａ ｏ ｆｅ ｅ ｔ ｌ ｏ ｉ ｍ ， ｐ ｏ ｉ ｅ ￣ ｆ ｌ ｅ ｅ ｅ ｃ ｆ ｅ ｅ ｔ ｇ ｐ ￣ ｍ ｔ ｈ ｎ ｌ ｏ ｉ ｍ ｒ ｅ ｅ ｏ ｉ ｇＮＩ 。 ｆ ｉ ｒ ｎ ｇ ｒｔ ｄ ａ ｈ ｒ ｖ ｄ ￣ｕ ｅ ａ ｒ ｆ ｒ ｎ ｅｏ ￣ ｌｃｉ ａ ｅ ｍａ ｃ ｉ ｇ ａ ｇ ｒ ｈ ｆ ｖ ｌ ｐ ｎ Ｄ８ ｉ ｎ ｔ ｏ ｄ Ｋｅ ｒ ｓ ｉ ｔｕ ｉ ｎ ｄ ｔ ｃｉ ｎ ｐ ｔｅｎ ｍａ ｃ ｉ ｇ ｓｎ ｌ ｄ ｔｈ ｎ ； ｍｕ ｔ ｄ ｔｈ ｎ ； ｆ ｉ ｕ ｏ ｔｎ ｙ ｗｏ ｄ ； ｎ ｒ ｓ ｅｅ ｔｏ ； ａｔｒ ｔｈ ｎ ； ｉ ｇ ｅｍｏ ｅｍａ ｃ ｉ ｇ ｏ ｌ ｍｏ ｅｍａ ｃ ｉ ｇ ｉ ｔ ａ ｔ ｍａｏ ｉ ｎ ｅ
（．国 际关 系学 院 信 息科技 系，北京 １０９ ；２ １ ００ １ ．北京 电子 科技 学院 计 算机 科 学 与技 术 系， 北 京 １０７） ０００
摘 要 ： 式 匹配 算法是 网络入侵 检 测 中的关键 所在 ， 模 它直接 影响 到 网络入 侵检 测 系 的实时检 测性 能。引入 ４种模 式 匹配 算法， 分析 其 工作 原理 ， 通过 实验对 上述 ４ 算法 进行 了性 能测试 。 种 根据 实验 结果 ， 出了不 同算法 的应 用 范围 ， 得 为今 后入侵
检 测 系统 开发者 选择模 式 匹配算 法提供 了有价 值 的参考 。
关键词： 入侵检测；模式 匹配；羊模 匹配；多模 匹配；有限 自动机 中图法分类号：Ｐ０ 文献标识码： 文章编号：００ ０４ ￣ｏ） ７１５—３ Ｔ ３９ Ａ １０— ２ （ ８０— ２ ７ ｏ ６ ０
Ｒｅ ｅ ｒ ｈ ｏ ａｔｒ ａｃ ｉ ｇａｇ ｒｔｍｉ ｆ ｅｗｏ ｋ ｉ ｔ ｓｏ ｅｅ ｔ ｎ ｓ ｓｅ ｓ ａ ｃ ｎ ｐ ｔ ｎ ｍ ｔｈ ｎ ｌ ｏ ｉ ｅ ｈ ｃｏ ｔ ｒ ｒ ｉｎ ｄ ｔ ｃｉ ｙ ｔｍ ｎ ｎ ｕ ｏ
Ａｂ ｔ ａ ｔ Ｐ ｔ ｒ ｔｈ ｎ ｌ ｏ ｔ ｍ ｓｉ ｏ ｔｎ ｅｗｏ ｋ ｉ ｔ ｓｏ ｅ ｅ ｔｏ ｙ ｔ ｍ， ｗｈ ｃ ｆ ｅ ｃ ｓｒ ａ ｍ ｅ ｄ ｔ ｃｉ ｎ ｐ ｒｏ － ｓｒ ｃ ： ａｔ ｎ ｍａｃ ｉ ｇ ａｇ ｒ ｈ ｉ ｅ ｉ ｍｐ ｒ ｔ ｎ ｎ ｔ ｒ ｒ ｉｎ ｄ ｔ ｃｉ ｎ ｓ ｓｅ ａ ｉ ｎｕ ｉ ｈ ｉ ｌ ｎ ｅ ｅ ｌ ｉ ｅ ｅ ｔｏ ｅｆ ｒ ｎ ｕ ｔ ｍａ ｃ ｆ ｅ ｏ ｋ ｉ ｔ ｓｏ ｅｅ ｔ ｎ ｓ ｓｅ 。Ｆ ｕ ａ ｅ ｍａ ｃ ｉ ｇ ａｇ ｒｔｍ ｓａ ｅｉ ｔｏ ｕ ｅ ， ｔ ｅ ｅｒ ｒ ｉ ｇ ｐ ｎ ｉ ｌ ｎ ｓｅ ｎ ｅｏ ｎ ｔ ｒ ｒ ｉｎ ｄ ｔ ｃ ｉ ｙ ｔｍ ｗ ｎ ｕ ｏ ｏ ｒ ￣ ｍ ｔｈ ｎ ｌ ｏ ｉ ｐ ｈ ｒ ｒ ｄ ｃ ｄ ｈ ｎ ｔ ｉ ｗｏ ｋ ｎ ｒ ｃｐ ｅａ ｄｔ ｔ ｄ ｎ ｈ ｉ ｅ ｐ ｒｏ ｍ ａ ｃ ｆ ｏ ａｔ ｒ ｔｈ ｎ ｌ ｏ ｔ ｍ ｒ ｕ ｈ ｅ ｐ ｒｍｅ ｔ ｒ ａｙ ｅ ．Ａｃ ｏ ｄ ｎ ｘ ｅ ｉ ｎ ｓ ｌ ｔ ｎ ｕ ｅ ｐ ｌ ｉ ｇｒｎ ｅ ｅ ｒ ｎ ｅｏ ｆ ｕ ｐ ｔ ｎ ｍａ ｃ ｉ ｇａ ｇ ｒ ｈ ｔ ｏ ｇ ｅ ｆ ｒ ｅ ｉ ｈ ｘ ｉ ｎ ｅａ ｌ ｚ ｄ ａ ｎ ｃ ｒ ｉ ｇｅ ｐ ｒｍｅ ｔ ｅ ｕ ｔ ｓ ｓ ｐ ｙ ｎ ｇ ｒ ，ｉ ｅ ｒ ａ ａ ｏ ｆｅ ｅ ｔ ｌ ｏ ｉ ｍ ， ｐ ｏ ｉ ｅ ￣ ｆ ｌ ｅ ｅ ｅ ｃ ｆ ｅ ｅ ｔ ｇ ｐ ￣ ｍ ｔ ｈ ｎ ｌ ｏ ｉ ｍ ｒ ｅ ｅ ｏ ｉ ｇＮＩ 。 ｆ ｉ ｒ ｎ ｇ ｒｔ ｄ ａ ｈ ｒ ｖ ｄ ￣ｕ ｅ ａ ｒ ｆ ｒ ｎ ｅｏ ￣ ｌｃｉ ａ ｅ ｍａ ｃ ｉ ｇ ａ ｇ ｒ ｈ ｆ ｖ ｌ ｐ ｎ Ｄ８ ｉ ｎ ｔ ｏ ｄ Ｋｅ ｒ ｓ ｉ ｔｕ ｉ ｎ ｄ ｔ ｃｉ ｎ ｐ ｔｅｎ ｍａ ｃ ｉ ｇ ｓｎ ｌ ｄ ｔｈ ｎ ； ｍｕ ｔ ｄ ｔｈ ｎ ； ｆ ｉ ｕ ｏ ｔｎ ｙ ｗｏ ｄ ； ｎ ｒ ｓ ｅｅ ｔｏ ； ａｔｒ ｔｈ ｎ ； ｉ ｇ ｅｍｏ ｅｍａ ｃ ｉ ｇ ｏ ｌ ｍｏ ｅｍａ ｃ ｉ ｇ ｉ ｔ ａ ｔ ｍａｏ ｉ ｎ ｅ
基于Snort入侵检测系统模式匹配改进算法研究
改进 ，使其在实际应 用 中提 高信息安 全防 范能 力。
关 键 词 ： 网络 入 侵检 测 ；Ｓ ｒ；Ｂ ｎ ｔ Ｍ算 法 ；Ｗ — ａｂｒ 法 ｏ ｕ Ｍ ｎｅ算
Ｂａ ｅ ｎ Ｓｎ ｒ ｎ ａ ｉ ｎ ｓ ｄ ｏ ｏ ｔ Ｉ ｖ ｓ ｏ Ｅｘ ｍｉ ａ ｉ ｎ ａ ｎ ｔｏ Ｓｙ ｔ ｍ Ｍｏ ｅ Ｍａ ｃ Ｉ ｒ ｖ ｍｅ ｔ ｓｅ ｄ ｌ ｔ ｈ ｍｐ ｏ ｅ ｎ
Ａｌ ｏ ｉｈ Ｒｅ ｅ ｒ ｈ ｇ ｒｔ ｍ ｓ ａ ｃ
Ｙ Ｎ Ｊ ｎ ， Ｅ Ｇ ａ 一 Ａ Ｇ ｕ Ｄ Ｎ Ｆ 唱
（ｕｎｚｏ ａ／ ｔ ｎ ｏ ｇ ｖ ｅａｙ ｓ ｏ ｆｍ ｄｎａ０ｔｅｃ ｍ ｎａｌ ｎ／ｅｎ ／ ｔ￣． Ｇａ ｈｕｎｖｄｅ ｔ Ｃｌ ｅｌ ｅ ｓ ｃ／ ｈｏ ｚ ｏ ａｏ ｎ 打 ｏ ｕｉ ｔｎｅ ｎ ｒｄ ｍ＃ｕ ｄ ｇ ｓ ｅ ｌ ｅ ｌｐ ／￣ ｃ ｌ￣ ｒ ｅ ｍ ｃ ￣ ｄｅｉ
能 ：数 据 包嗅探 、数 据包 记 录 、入侵 检 测等 。其 工
类 ，分 别 是基 于异 常 的入 侵 检 测和 基 于规 则 的 入侵
检 测 。其 检 测 算 法种 类 繁 多 ，诸 如 专 家 系统 、模 式 匹 配 、数 据 挖 掘 、统计 方 法 以及 免 疫 学 等 ，其 中模
ｏｅ ａ ｉ ａ ｃ ａ ｎｌ ｂ ｔ ｎ ｈ ｖ ｓ ］ ｅｎｔ ｅｗｏｋ， ｔ ｅ ｙ ｔ ｍ ａｙ Ｏ ｅ ｅ ｅ ｈ ｏ ｔｉｅ ｈ ａ ｔｃ ａ ｄ ｈ ｄ ｓｒｃｉｎ， ｔｅ ｎ ｏｍａ ｉｎ ｐ ｒｔｏ ｌ ｈ ｎ ｅ， ｕ ｉ ｎ ｔｅ ａ ｔ ｎ ｒｅ ｎ ｔ ｒ ｔ ｈ ｓ ｓｅ ｅ ｓ ｔ ｒｃ ｉ ｔ ｅ ｕ ｓ ｔｅ ｔ ａ ｋ ｎ ｔ ｅ ｅ ｔｕｔｏ ｖ ｄ ｈ ｉ ｒ ｔ ｆ ｏ
关 键 词 ： 网络 入 侵检 测 ；Ｓ ｒ；Ｂ ｎ ｔ Ｍ算 法 ；Ｗ — ａｂｒ 法 ｏ ｕ Ｍ ｎｅ算
Ｂａ ｅ ｎ Ｓｎ ｒ ｎ ａ ｉ ｎ ｓ ｄ ｏ ｏ ｔ Ｉ ｖ ｓ ｏ Ｅｘ ｍｉ ａ ｉ ｎ ａ ｎ ｔｏ Ｓｙ ｔ ｍ Ｍｏ ｅ Ｍａ ｃ Ｉ ｒ ｖ ｍｅ ｔ ｓｅ ｄ ｌ ｔ ｈ ｍｐ ｏ ｅ ｎ
Ａｌ ｏ ｉｈ Ｒｅ ｅ ｒ ｈ ｇ ｒｔ ｍ ｓ ａ ｃ
Ｙ Ｎ Ｊ ｎ ， Ｅ Ｇ ａ 一 Ａ Ｇ ｕ Ｄ Ｎ Ｆ 唱
（ｕｎｚｏ ａ／ ｔ ｎ ｏ ｇ ｖ ｅａｙ ｓ ｏ ｆｍ ｄｎａ０ｔｅｃ ｍ ｎａｌ ｎ／ｅｎ ／ ｔ￣． Ｇａ ｈｕｎｖｄｅ ｔ Ｃｌ ｅｌ ｅ ｓ ｃ／ ｈｏ ｚ ｏ ａｏ ｎ 打 ｏ ｕｉ ｔｎｅ ｎ ｒｄ ｍ＃ｕ ｄ ｇ ｓ ｅ ｌ ｅ ｌｐ ／￣ ｃ ｌ￣ ｒ ｅ ｍ ｃ ￣ ｄｅｉ
能 ：数 据 包嗅探 、数 据包 记 录 、入侵 检 测等 。其 工
类 ，分 别 是基 于异 常 的入 侵 检 测和 基 于规 则 的 入侵
检 测 。其 检 测 算 法种 类 繁 多 ，诸 如 专 家 系统 、模 式 匹 配 、数 据 挖 掘 、统计 方 法 以及 免 疫 学 等 ，其 中模
ｏｅ ａ ｉ ａ ｃ ａ ｎｌ ｂ ｔ ｎ ｈ ｖ ｓ ］ ｅｎｔ ｅｗｏｋ， ｔ ｅ ｙ ｔ ｍ ａｙ Ｏ ｅ ｅ ｅ ｈ ｏ ｔｉｅ ｈ ａ ｔｃ ａ ｄ ｈ ｄ ｓｒｃｉｎ， ｔｅ ｎ ｏｍａ ｉｎ ｐ ｒｔｏ ｌ ｈ ｎ ｅ， ｕ ｉ ｎ ｔｅ ａ ｔ ｎ ｒｅ ｎ ｔ ｒ ｔ ｈ ｓ ｓｅ ｅ ｓ ｔ ｒｃ ｉ ｔ ｅ ｕ ｓ ｔｅ ｔ ａ ｋ ｎ ｔ ｅ ｅ ｔｕｔｏ ｖ ｄ ｈ ｉ ｒ ｔ ｆ ｏ
模式匹配算法的研究与改进
闵联营 ， 赵婷婷
（ 武汉理工大学计 算机科 学与技术学院， 湖北 武汉 ４０６ ） ３０３
摘要 ：Байду номын сангаас随着网络 的迅速发展 ， 网络安全 问题 日益突 出， 入侵检 测技 术也成为 当今 社会关 注的焦点。对 于基 于规 则的入侵
检测来说 ， 匹配算法非常重要 ， 模式 它直接影响到 系统的准确性和 实时性能 。本 文介 绍 了 Ｋ Ｐ Ｂ Ｍ 和 Ｍ算法 ， Ｂ 对 Ｍ算法
ｂ ｓｄ ｉｔ ｓｏ ｅ ｃｉｎｓｓ ｍ．Ｉ ｄｒ ｔ ｆ ｅ ｃｓｔｅａｃ ｒｃ ｎ ａ－ｍｅｐｆ ｎ ａ ｃ ｆｔｅｓｓｅ ．Ｔ ｅｐｐ ｒｎｈ ｔｃ ＭＰ ａｅ ｒ ｉｎ ｄｔ ｔ ｙｔ ｎｕ ｅ ｏ ｅ ｔ ｉ ｌ ｉｌ ｎｅ ｃｕａ ｙａ ｄｒ ｌｉ ｅ ｏ ｎ ｎｅｏ ｈ ｔ ｅ ｙ ｎｕ ｃ ｈ ｅ ｔ ｙ ｍ ｈ ｅ ｔｘｕ ｅ Ｋ ａ ｉ ｓ
样， 检测准确率和效率都很高。
生。传统的防火墙技术 已经难以单独保障网络的安
全 ， 络入 侵 检 测 系 统． ｅ ｏ ｎｕｉ ｅ ｃｏ 网 （ ｔ ｒ Ｉ ｒ ｏ Ｄｔ ｔｎ Ｎ ｗ ｋ ｔ ｓｎ ｅ ｉ Ｓｓ ｍ Ｎ ）） ｙｅ ， ⅡＳ作为一种积极主动的安全防护技术 ， ｔ 已
ＭＩ Ｌ ａ ・ ｈ ， ＨＡＯ ｎ —ｉｇ Ｎ ｉｎ ｙ ｇ Ｚ Ｔｉｇ ｔ ｎ
（ ｏｅｅｏ Ｃ ｍ ｕ ｒ ｃ ｎｅａｄＴｃｎｌ ｙ Ｗｕａ ｎ ｅｓｙｏ Ｔ ｈｏ ｇ，Ｗｕａ ３０ ３ ｈ ａ Ｃｌ ｇ ｆ ｐｔ ｉ ｃ ｎ ｅｈｏ ｇ ， ｈｎＵ ｉ ｒｔ ｆ ｅ ｎｌ ｙ ｌ ｏ ｅ Ｓｅ ｏ ｖ ｉ ｃ ｏ ｈｎ４０ ６ ，Ｃ ｉ ） ｎ
的改进进行 了研究 ， 并提 出一种改进的 Ｂ Ｍ算法。改进后的算法运 用到入侵检测 系统模型 中极 大地提 高了检测性能。
（ 武汉理工大学计 算机科 学与技术学院， 湖北 武汉 ４０６ ） ３０３
摘要 ：Байду номын сангаас随着网络 的迅速发展 ， 网络安全 问题 日益突 出， 入侵检 测技 术也成为 当今 社会关 注的焦点。对 于基 于规 则的入侵
检测来说 ， 匹配算法非常重要 ， 模式 它直接影响到 系统的准确性和 实时性能 。本 文介 绍 了 Ｋ Ｐ Ｂ Ｍ 和 Ｍ算法 ， Ｂ 对 Ｍ算法
ｂ ｓｄ ｉｔ ｓｏ ｅ ｃｉｎｓｓ ｍ．Ｉ ｄｒ ｔ ｆ ｅ ｃｓｔｅａｃ ｒｃ ｎ ａ－ｍｅｐｆ ｎ ａ ｃ ｆｔｅｓｓｅ ．Ｔ ｅｐｐ ｒｎｈ ｔｃ ＭＰ ａｅ ｒ ｉｎ ｄｔ ｔ ｙｔ ｎｕ ｅ ｏ ｅ ｔ ｉ ｌ ｉｌ ｎｅ ｃｕａ ｙａ ｄｒ ｌｉ ｅ ｏ ｎ ｎｅｏ ｈ ｔ ｅ ｙ ｎｕ ｃ ｈ ｅ ｔ ｙ ｍ ｈ ｅ ｔｘｕ ｅ Ｋ ａ ｉ ｓ
样， 检测准确率和效率都很高。
生。传统的防火墙技术 已经难以单独保障网络的安
全 ， 络入 侵 检 测 系 统． ｅ ｏ ｎｕｉ ｅ ｃｏ 网 （ ｔ ｒ Ｉ ｒ ｏ Ｄｔ ｔｎ Ｎ ｗ ｋ ｔ ｓｎ ｅ ｉ Ｓｓ ｍ Ｎ ）） ｙｅ ， ⅡＳ作为一种积极主动的安全防护技术 ， ｔ 已
ＭＩ Ｌ ａ ・ ｈ ， ＨＡＯ ｎ —ｉｇ Ｎ ｉｎ ｙ ｇ Ｚ Ｔｉｇ ｔ ｎ
（ ｏｅｅｏ Ｃ ｍ ｕ ｒ ｃ ｎｅａｄＴｃｎｌ ｙ Ｗｕａ ｎ ｅｓｙｏ Ｔ ｈｏ ｇ，Ｗｕａ ３０ ３ ｈ ａ Ｃｌ ｇ ｆ ｐｔ ｉ ｃ ｎ ｅｈｏ ｇ ， ｈｎＵ ｉ ｒｔ ｆ ｅ ｎｌ ｙ ｌ ｏ ｅ Ｓｅ ｏ ｖ ｉ ｃ ｏ ｈｎ４０ ６ ，Ｃ ｉ ） ｎ
的改进进行 了研究 ， 并提 出一种改进的 Ｂ Ｍ算法。改进后的算法运 用到入侵检测 系统模型 中极 大地提 高了检测性能。
入侵检测中一种新的多模式匹配算法
关 键词 ：入侵 检测 ；多模式 匹配 ；Ａ Ｃ算法 ；ＷｕＭ ｎｅ 算法 ；Ａ — 算法 — ａｂｒ ＣＷＭ
中图分类 号 ：Ｔ ３ ３ ０ Ｐ９．８ 文献标 志码 ：Ａ 文章编号 ：１０ —６ ５ ２ ０ ） ８ ２ ７ ・３ ０ １ ３９ （０ ８ ０ — ４４ ０
Ｎｅ ｍｕｔｐｅ ｐ ｔ ｒ ｓｍａｃ ｉｇ ａｇ ｒｔ ｍ ｎ ｉｔｕ ｉｎ ｄ ｔｃｉｎ ｗ ｌ ｌ ａｔ ｎ ｔｈ ｎ ｌｏ ｉ ｉ ｅ ｈ ｉ ｎｒ ｓｏ ｅｅ ｔｏ
ｐ ｅｐ ｔ ｒ ｓｍａｃ ｉｇ ａｇ ｒ ｈ ，ｓ ｃ ｓＡＣ ａｇ ｒ ｈ ｎ — ｎ ｅ ｇ ｒ ｈ ｉ ａｔ ｎ ｔｈ ｎ ｌ ｏ ｉ ｍｓ ｕ ｈ ａ ｏｉ ｍ ａ ｄ Ｗｕ Ｍａ ｂ ｒａ ｏｉ ｍ，ａ ｄ ｔ ｅ ｒ ｓ ｎ ｅ ｅ ｌ ｐ ｅ ｐ ｔ ｒ ｓ ｅ ｔ ｌ ｔ ｌ ｔ ｎ ｎ ｐ ｅ ｅ ｔｄ ａ ｎ ｗ ｍｕ ｔ ｌ ａｔｎ ｈ ｉ ｅ
随着 网络技术的发展 ， 网络 环境 变得越来 越复杂 ， 对于 网 络安全来说 ， 单纯 的防火墙技术 暴露 出明显 的不足和弱 点 ， 如 无法解决安全后 门问题 ； 不能阻止 网络 内部攻 击 ； 能提供实 不 时入侵检测能力 ； 对于病毒束 手无策等 。入侵检测 系统是继防 火墙和信息加密等安全保 障技 术之后 出现的新一代 网络 安全 防护系统 ， 能够有效地弥补上述安全系统的不足。它通过对计 算机网络或计算机系统 中的若 干关键点 收集信息并对其 进行
李 庚 ， 韩 进 ， 谢 立
（ 南京 大学 ａ 计算机 科学与技 术 系 ；ｂ 软件 新技 术 国家重点 实验 室，南京 ２ ０ ９ ） ． ． １０ ３ 摘 要 ：基 于模 式 匹配的检 测方法是 目前入侵检 测 系统的一种 重要 方法 ， 因此作 为模 式 匹配方法核 心 的字符 串
改进的模式匹配算法在入侵检测中的应用
ｎｏ ｄ ｙｓｂ ｃ ｍ ｅ ｈ ｏ ｕｓｗ ｈｉｈ ｔ ｅ ｌ ｙｓｃｏ ｅ ａｔｎｔｏ ｏ． ｗａ ａ ｅ ｏ ｓｔ ｅ ｆ ｃ ｃ ｈｅ ｐ ｏｐｅ ｐａ ｌ ｓ ｔｅ ｉ ｎ ｔ Ａｎ ｆｃ ｔ ｎ ｒ ｃｓ ｔｅ ａｃ ｉ ｌｏｒｔ ｍ ｓｉ ｐｏ ｔｎ ｏ ｅ ｅ ｖｅ ａ ｄ ｐ ｅ ｉｅ ｐａｔｒ ｍ ｔ ｈｎｇ ａｇ ｉｈ ｉ ｍ ｉ ｎ ｒａ ｔｔ ｉ ｍ ｓｏｎ ｄ ｃ ｔｏｎ ｓ ｓｅ ．Ｉ ｔ ｉ ｐｅ ，ｂ ｓ ｄ ｏｎ ｔ ｎａｙｓ ￣ ｓ ｎｇ ｐａｔｒ ｍ ａｃ ｉ ｇ ａｇ ｉｔ ｓｐ ｏｐ ｅ ｎ ｉ ｈｔ ｉ ｅ ｅｉ ｙ ｔｍ ｎ ｈｓｐａ ｒ ａ ｅ ｈｅ ａ ｌ ｉ ｏｆｅ ｔ ｔｅ ｎ ｔ ｈ ｎ ｌｏｒ ｈｍ ，ｒ ｏｓｄ ａ ｍｐｒ ｖｅ ｌｏｒ ｔ ｍ ｏ ｓ ｉ ｏ ｄ ａｇ ｕ ｈ ｆ ｒ
Ｖｏ． ， ． Ｆｅ ｒ ａｙ ２ １ ， Ｐ ８ — ２ １ Ｎｏ４， ｂ ｕ ｒ ０ ０ Ｐ ． ２１ ８ ３ ６
改进 的模 式 匹配算 法 在入 侵 检测 中的应 用
汪 勇 大
（ 尔 滨 理工 大 学 计 算 机科 学 与 技 术 学 院 ， 龙 江 哈 尔 滨 １０ ８ ） 哈 黑 ５ ０ ０
＿
多的 字符 ． 实现 更快 的 匹配 过 程 。 实验 证 明 ， 改进 后 的 算 法 大 大提 高 了检 测 的 性 能 。 关 键词 ： 入侵 检 测 ： 式 配 ； Ｍ 算 法 ； Ｃ 算 法 ； Ｃ Ｂ 算 法 模 Ｂ Ａ Ａ ＿ Ｍ
中 图分 类 号 ： ３ ９ ＴＰ ０ 文 献 标 识码 ： Ａ 文章 编号 ：０ ９ ３ ４ （０ ００ — ８ １ ０ １ ０ — ０ ４ ２ １ ）４ ０ ２ — ３
外 界 的 攻击 与破 坏 ， 息 的 安 全保 密性 受 到严 重 影 响 。 网 络安 全 问 题 已 成 为 世 界 各 国政 府 、 业 及 广 大 网 络 用 户 最 关 心 的 问题 之 信 企
Ｖｏ． ， ． Ｆｅ ｒ ａｙ ２ １ ， Ｐ ８ — ２ １ Ｎｏ４， ｂ ｕ ｒ ０ ０ Ｐ ． ２１ ８ ３ ６
改进 的模 式 匹配算 法 在入 侵 检测 中的应 用
汪 勇 大
（ 尔 滨 理工 大 学 计 算 机科 学 与 技 术 学 院 ， 龙 江 哈 尔 滨 １０ ８ ） 哈 黑 ５ ０ ０
＿
多的 字符 ． 实现 更快 的 匹配 过 程 。 实验 证 明 ， 改进 后 的 算 法 大 大提 高 了检 测 的 性 能 。 关 键词 ： 入侵 检 测 ： 式 配 ； Ｍ 算 法 ； Ｃ 算 法 ； Ｃ Ｂ 算 法 模 Ｂ Ａ Ａ ＿ Ｍ
中 图分 类 号 ： ３ ９ ＴＰ ０ 文 献 标 识码 ： Ａ 文章 编号 ：０ ９ ３ ４ （０ ００ — ８ １ ０ １ ０ — ０ ４ ２ １ ）４ ０ ２ — ３
外 界 的 攻击 与破 坏 ， 息 的 安 全保 密性 受 到严 重 影 响 。 网 络安 全 问 题 已 成 为 世 界 各 国政 府 、 业 及 广 大 网 络 用 户 最 关 心 的 问题 之 信 企
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
由于 计 算 机 网 络 自身 存 在 的 局 限 性 和信 息 系统 的脆 弱 性 ， 得 计 算 机 网 络 系 统 上 的 硬 件 资 源 ， 信 资源 ， 件 及ห้องสมุดไป่ตู้信 息 资 源 等 因 使 通 软 为各 种 原 因而 遭 到 破坏 、 改 、 露 或功 能失 效 ， 得 信 息 系 统处 于异 常状 态 ， 至 引起 系 统 的崩 溃 瘫 痪 ， 成 巨 大 的 经 济 损 失 。 在 更 泄 使 甚 造 这样 的形 式 下 ， 以保 护 网 络 中 的信 息免 受 各 种攻 击 为 目的 的 网 络安 全 变 得 越 来 越 重 要 ， 安 全 方 面 的 考 虑 提 高 到 了越 来 越 重 要 的 对 地位 上 。
朱 余 俊。强
（ 合肥 工 业 大 学 计 算 机 与 信 息 学 院 ， 徽 合 肥 ２ ０ ０ ） 安 ３ ６ １
摘 要 ： 基 于入 侵 检 测 系统 来说 ． 式 匹配 算 法是 基 于特 征 匹 配 的入 侵 检 测 系统 中的核 心 算 法 ， 是 当前 入 侵 检 测 设 备 中普 遍 应 用 对 模 也
Ｒｅ ｓ ｈ ｎ ｎ ｍ ｐ ｏ ｉ ｇ ｏ ｔｅ ｎ Ｍ ａ ｃ ｉ ｇ Ａｌ ｏ ｉ ｍ ｎ ｒ ｓｏ ｔ ｃ ｉ ｎ Ｓ ｓｅ ａ ｃ ｉｇａ ｄ Ｉ ｒ ｖｎ ｆ Ｐａ ｔ ｒ ｔｈ ｎ ｇ ｒｔ ｈ ｉ Ｉ ｔ ｕ ｉｎ Ｄｅｅ ｔｏ ｙ ｔｍ ｎ
Ｚ ＨＵ ｎ ａ ｇ Ｊ ． Ｑｉ ｕ ＹＵ ｎ （ｃ ｏ ｌ ｆ ｏ ｐ ｔ ＆ Ｉｆｒ ｔ ｎ Ｈｅ ｉ ｉｅ ｉ ｆ ｅｈ ｏ ｇ ， ｆ ３ ６ １ Ｃ ｉ ａ Ｓ ｈ ｏ ｍ ｕｅ ｏＣ ｒ ｎｏｍａ ｏ ， ｆ ｖ ｒ ｔ ｏ ｃ ｎ ｌ ｙ Ｈｅ ｉ ０ ０ ， ｈｎ ） ｉ ｅ Ｕｎ ｓ ｙ Ｔ ｏ ｅ２ Ａ ｓ ａ ｔ Ｆ ｒ ｈ ｔ ｓ ｎＤｅ ｃ ｏ ｙｔ （ ） ｐ ｔ ｍ ａｃ ｉｇａ ｏｉ ｍ ａ ｄｏ ａ ｒ ｍ ｔｈ ｇｉｔ ｓ ｎ ｄ ｔｃ ｏ ｓ ｍ ｂ ｔ ｃ ： ｏ ｅＩ ｒ ｉ ｔ ｔ ｎ Ｓ ｓ ｍ Ｉ ， ａ ｅ ｍ ｔ ｎ ｇ ｒ ｈ ｉ ｂ ｓ ｎ ｆ ｔ ｅ ａｃ ｎ ｒ ｉ ｅｅｔ ｎ ｓ ｔ ｉ ｒ ｔ ｎ ｕｏ ｅｉ ｅ ＤＳ ｔ ｈ ｌ ｔ ｓ ｅ ｅｕ ｉ ｎｕｏ ｉ ｙｅ ｎ
的 算 法 。 它的 效 率 直接 影 响 到 入 侵 检 测 系统 的 准确 性 和 实 时性 ， 章 通 过 对 模 式 匹配 算 法 的 改 进 ， 出 了一 种 改进 的 算 法 ， 匹配 文 提 在
文 本 中 重复 字 符 串较 多 时 ， 算 法 可 以加 快 入 侵检 测 系统 的检 测 速 度 ， 高现 有 入 侵 检 测 系统 的检 测 能力 。 该 提 关 键 词 ： Ｍ 算 法 ； 侵 检 测 系统 （ＤＳ ； 式 匹配 Ｂ 入 Ｉ ）模 中 图分 类 号 ： Ｐ ９ Ｔ ３３ 文 献 标 识码 ： Ａ 文 章编 号 ： ０ ９ ３ ４ （０ ０ ０ — １ １ ０ １ ０ — ０ ４ ２ １ ）５ １ ０ — ３
ｉｔｕ ｉｎ ｄ ｔ ｃ ｏ ｓ ｍ ｅｅ ｔ ｎ ｃ ｐ ｂｌ ． ｎｒｓ ｅｅｔ ｎ ｓ ｔ ｏ ｉ ｙ ｅ ｄ ｔｃ ｏ ａ ａ ｉ ｔ ｉ ｉ ｙ
Ｋ ｙ ｗ ｒ ｓ Ｂ ａ ｏ ｔｍ；ｎｒ ｓ ｎ ｄ ｔｃ ｏ ｓ ｍ（ ） ｐ ｔ ｒ ｔ ｎ ｅ ｏ ｄ ： Ｍ ｇ ｒｈ ｉｔ ｉ ｅｅｔ ｎ ｓ ｔ Ｉ ； ａ ｅ ｍａ ｈ ｇ ｌ ｉ ｕｏ ｉ ｙ ｅ ＤＳ ｔｎ ｃ ｉ
Ｖｏ ．， ． ， ｅ ｒ ｒ ０ ０ Ｐ ． １ —１ ０ １ Ｎｏ ５ Ｆ ｂ ｕａ ｙ ２ １ ， Ｐ １ ０１ １ ３ ６
Ｔ ｌ ８— ５ － ６ ０ ６ ５ ９ ９ ４ ｅ： ６ ５ ５ ９ ９ ３ ＋ １ ６ ０６
入侵 检 测 系统 中一 种模 式 匹配算 法 的研 究 与 改进
Ｉ ＳＳＮ １ ０ － ０ ４ ０ ９ ３ ４
Ｅ ｍａｌ ｉｆ ＠ｃ ｃ ． ｅ．ａ — ｉ ｎ ｏ ｃ ｃｎ ｔ ： ｃ
ｈ ｔ ／ｗｗｗ． ｚ ．ｅ ．ａ ｔｐ： ／ ｄｎ ｓｎ ｔｃ
Ｃ ｍｐ ｔ Ｋ ｏ ｌ ｇ ｎ ｅ ｈ ｏ ｇ ｏ ｕ ｒ ｎ ｗｅ ｅａ ｄ Ｔ ｃ ｎ ｌ ｙ电脑 知 识 与技术 ｅ ｄ ｏ
ｔ ｏ ｅ ａｇｏ ｔ ｍ ，ｂ ｓ ｈ ｕｒｅ ｔｉ ｒ ｉ ｎ ｄ ｔ ｃ ｏｎ ｅ ｉ ｅ ｔｗ ｉ ｌ ｓ ｄ ａｇｏ ｉ ｈｅ ｃ ｒ ｌ ｒ ｈ ｉ ｕｔａ ｏ ｔ ｅ ｃ ｒ ｎ ｎｔｕｓｏ ｅ ｅ ｔ ｑｕｐｍ ｎ ｄｅｙ ｕ ｅ ｌ ｉ ｌ ｒｔ ｓ ｔ ｆｉｉｎｃ ｄ ｒ ｃｌ ｆｅ ｔ ｈｅ ａ ｃ ｒ ｃ ｆ ｈｍ ．Ｉｓｅ ｃｅ ｙ ｉｅ ｔｙ ａ ｃｓｔ ｃ ｕ ａ ｙ ｏ ｉｔｕ ｉ ｔｃ ｏｎ ｓ ｓｅ ｓａ ｅ —ｔ ｅ ｈ ｅ ａ ｔ ｌ ｈ ｏｕ ｈ ｍ ｐｒ ｅ ａｔｒ ｍ ｔｈ ｎ ｇ ｉｈ ｓｐ ｏ ｏｓｄ ｎ ｍ ｐｒ ｖｅ ａｇｏ ｔ ｍ ，ｒ － ｎ ｒ ｓｏｎ ｄｅｅ ｔ ｙ ｔｍ ｎｄ ｒ ａ ｉ ，ｔ ｒ ｃｅ ｔ ｒ ｇ ｉ ｉ ｌ ｍ ｉ ｏｖ ｄ ｐ ｔｅｎ ａ ｃ ｇ ａ ｏｒｔ ｍ ｉ ｒ ｐ ｅ ａ ｉ ｉ ｌ ｏ ｄ ｌ ｒ ｈ ｉ ｅ ｐｅ ｔ ｄ ｉ ｈｅ ｍ ａｃ ｉ ｅ ｔｉ ｓｍ ｏ ｅ，ｔ ｇ ｉｔ ａ ｓ ｅ ｈｅｉ ｒ ｓｏｎ ｄｅｅ ｔｏ ｙ ｔ ｍ ｅ ｄ ｔｃ ｏ ｒ ｔ，ｕ ｒ ｄ ｅ ｅ ｉｔｎ ａｅ ｎ ｔ ｔｈ ｎｇ ｔｘｔｓｒｎｇ ｒ ｈｅａ ｏｒ ｈｍ ｃ ｎ ｐｅ ｄ ｕｐ ｔ ｎｔｕ ｉ ｔｃｉ ｎ ｓｓｅ ｔ ｅ ｅ ｔ ｎ ａｅ ｐｇ ａ ｅ ｔ ｘｓ ｇ ｌ ｈ ｉ ｈ ｉ