入侵检测系统中多模式匹配算法的研究与改进

格式：pdf
大小：235.94 KB
文档页数：4

下载文档原格式

/ 4

多模式匹配算法及其在入侵检测系统中的应用研究

多模式匹配算法及其在入侵检测系统中的应用研究多模式匹配算法是一种用于在文本中查找多个模式的算法。

它在入侵检测系统中的应用非常广泛，可以用于检测网络流量中的恶意代码、攻击行为等。

多模式匹配算法的基本思想是将多个模式串构建成一棵Trie树，然后在文本串中进行匹配。

Trie树是一种特殊的树形结构，它的每个节点代表一个字符，从根节点到叶子节点的路径表示一个模式串。

在匹配时，从文本串的第一个字符开始，依次在Trie树上匹配，如果匹配失败，则回溯到上一个匹配成功的节点继续匹配。

多模式匹配算法的时间复杂度取决于模式串的数量和长度。

如果模式串数量和长度都很大，那么算法的时间复杂度会非常高。

为了提高算法的效率，研究者们提出了许多优化算法，如AC自动机算法、双数组Trie树算法等。

AC自动机算法是一种基于Trie树的改进算法，它在Trie树的基础上增加了一个失败指针，用于在匹配失败时快速回溯到上一个匹配成功的节点。

双数组Trie树算法则是将Trie树转化为两个数组，一个存储节点的子节点，另一个存储节点的失败指针，从而减少了空间的使用。

在入侵检测系统中，多模式匹配算法可以用于检测网络流量中的恶意代码、攻击行为等。

例如，可以将病毒、木马等恶意代码的特征构建成多个模式串，然后使用多模式匹配算法在网络流量中进行匹配，如果匹配成功，则说明网络中存在恶意代码。

另外，多模式匹配算法还可以用于检测网络中的攻击行为。

例如，可以将常见的攻击行为的特征构建成多个模式串，然后使用多模式匹配算法在网络流量中进行匹配，如果匹配成功，则说明网络中存在攻击行为。

总之，多模式匹配算法是一种非常重要的算法，在入侵检测系统中有着广泛的应用。

随着网络安全威胁的不断增加，多模式匹配算法的研究和优化将会越来越重要。

入侵检测系统中的模式匹配算法研究

方向。关键词：侵检测；式匹配；ＭＰ算法；Ｍ算法；Ｃ算法；端分段匹配算法入模ＫＢＡ两
中图分类号：Ｐ０Ｔ３１
文献标识码：Ａ
文章编号：６３１８（０００ — １９０１７ — ９０２１）２０５ — ４
常快，实际比较次数只有目标串长度的２％～００３％。
符不匹配，将模式串右滑距离ｄ，则）执行由Ｐｍ与
＋）ｄ起始的自右至左的匹配检查。Ｍ算法采用两Ｂ条规则计算模式串右移的距离：后缀移动和坏字好符移动。（）后缀移动，１好分两种情况。
收稿日期：０９０ — ０２０ — ９３
发．ｏｅ和Ｍｏｒ提出一种新的快速字符串匹配算Ｂｙｒｏｅ
法一Ｂ算法［ｌＭ。．６
Ｂ算法基本思想是：开始时将目标串与模Ｍ
式串Ｐ左对齐，自右至左逐个字符进行比较（即首先
１单模式匹配算法
（）１模式匹配。在给定长度为凡的目标串中
查找长度为ｍ的模式Ｐ首次或多次出现的过程，
，
ｍｘｋｌｋｊ且Ｐ … ：ａ｛ｌ＜，＜２
ｎｘ￣＝ｅｔ］０
一
∥‘ 。 ‘ ）一
集合非空其他情况ｊｏ时＝
等传统安全保护措施后的新一代安全保障技术。模
式匹配算法是基于特征匹配的入侵检测系统中的核心算法。据统计，现在大约９％的入侵检测都是特５征匹配的人侵检测。由此可见，式匹配算法性能模的优劣直接影响到入侵检测系统的效率。在此介绍几种用于入侵检测的经典模式匹配算法．在此基并础上提出一种入进算法．后给出人侵检测系统中最模式匹配算法的选择策略。

基于多模式匹配的入侵检测系统研究与改进的开题报告

基于多模式匹配的入侵检测系统研究与改进的开题报告一、研究背景随着互联网技术的广泛应用，信息安全问题愈发严重。

针对网络黑客、病毒、恶意软件等攻击方式，研究基于多模式匹配的入侵检测系统具有重要意义。

传统的入侵检测系统主要基于特征匹配、统计分析、机器学习等方法，存在一定局限性。

基于多模式匹配的入侵检测系统通过对攻击行为的详细样本库建立多模式匹配规则集，既能检测出已知的攻击模式，也能对未知的攻击模式进行识别，提高了入侵检测系统的准确性和实用性。

二、研究对象本研究主要针对基于多模式匹配的入侵检测系统进行研究。

包括对多模式匹配算法的优化、样本库的更新和管理、入侵检测系统的性能评估等方面。

三、研究内容1. 算法优化：结合基于多模式匹配算法的原理，针对其算法特点进行优化，提高入侵检测系统的性能。

2. 样本库的更新和管理：收集和分析现有的攻击样本数据集，并建立有效的样本库管理机制，保证入侵检测系统的检测能力和精度。

3. 入侵检测系统的性能评估：针对已有的多模式匹配入侵检测系统，设计相应的测试方案，对其性能进行评估和分析，优化其检测能力和实用性。

四、研究方法1. 文献分析法：对基于多模式匹配的入侵检测系统相关文献进行阅读和分析，掌握该领域的研究现状和前沿发展。

2. 算法优化法：根据基于多模式匹配算法的特点，结合实际应用需求，进行算法优化，提高入侵检测系统的性能。

3. 实验研究法：通过搭建实验测试平台，实现入侵检测系统的设计、测试和评估，掌握其性能表现和实际应用情况。

五、研究意义本研究将通过对入侵检测系统的多模式匹配算法优化和样本库管理机制的建立等方面进行研究，提高入侵检测系统的检测能力和实用性，为保障信息安全提供有力技术支撑。

入侵检测模式匹配算法研究

络数据分析、匹配．判断网络中是否有入侵企图。ｆ定所有入侵行为和手
系统一般不单独采川ＫｕｈＰａｔＭｏｒ算法．而是配合其他算法ｎｔ— ｒｔｒｉ — ｓ
共同实现。
段（及其变种）都能够表达为一种模式或特征，那么所有已知的入侵方法都可以用模式匹配的方法发现。一般意义上的模式匹配算法非常多，本文只研究与入侵检测直接相关的算法，主要有Ｂｕｒ算法，ｎｔｒｔＦｃｅｏｅＫｕ — ｈ
ＰａｔＭｏｒ算法，ｏｅ— ｏｅｒｔ — ｒｓｉＢｙｒＭｏｒ算法、ｈ — ｏｉｋ算法、ｅ— ｉｏｅ— ＡｏＣｍｓｃｓＩｗｓＢｙｒｅＭｏｒ— ｒｐｏ算法，ｈ — ｏｉｋＢｙｒＭｏｒ算法。ｏｅＨｏｓｏｌＡｏＣｍｓ — ｏｅ— ｏｅｃ
ＢｙｒＭｏｅ算法先将ＰＴ左端对齐．然后按照从右向左的模式从ｏｅ— ｏｒ，摸式串最右一个字符开始扫描。在不匹配的情况下（或者整个字符串完
全匹配），它用两个预处理函数决定右移的长度。这两个函数分别叫做好
后缀移动函数（叫匹配移动）也和坏字符移动函数（叫出现移动）也。
法、ｏｅ＇ｏｅ算法、ｈ — ｏａｉｋ算法、ｅ－ｉｏｅ— ｏｒ— ｏｐｏ算法和ＡｏＢｙｒＭｏｒＡｏＣｒｓｃＳｔｗｓＢｙｒＭｏｅＨｍｏｌｅｈ—
Ｃｒｓｃｏａｉｋ
—
ＢｙｒＭｏｅ算法。ｏｅ— ｏｒ
文献标识码：Ａ
２３系统应用－
１ＢｕｏｃｒｔＦｒｅ算法ｅ

入侵检测中BM模式匹配算法和改进.

入侵检测中BM模式匹配算法和改进入侵检测是一种动态的安全防护手段,它能主动识别入侵信息,为网络系统提供安全保护。

模式匹配技术是入侵检测系统识别攻击行为的主要技术,它能够快速探测攻击的存在,具有误报率低、准确性高、实用性强等优点。

在高速网络环境下,入侵检测的速度有可能跟不上数据包传输速率,导致攻击行为的漏报,因而入侵检测系统的检测速度越来越成为其获得实效的瓶颈之一。

降低入侵检测中常用的模式匹配算法的时间复杂度和空间复杂度是提高检测性能的一种有效途径。

本文的研究重点是对入侵检测中使用的模式匹配算法进行研究和改进。

本文首先对入侵检测的现状进行了分析,重点研究了网络入侵检测的核心技术——模式匹配。

研究从模式匹配方法的原理出发,提出了其面临的问题。

在此基础上,对当前最流行的BM算法从原理到性能进行了详细地分析和讨论。

BM算法拥有较好的匹配效率,但是它不能记录上一次匹配结果,而且算法的预处理过程也会带来较大的内存占有量。

本文从时间复杂度和空间复杂度两个方面进行了算法的改进研究,分别提出两种改进算法:BMLT和BMLS。

BMLT通过设定一个新的预处理函数来计算移动量,能有效增加模式串的移动距离。

BMLS通过减少处理规则和判断坏字符在模式串中出现的次数,能在对时间复杂度影响不大的前提下,减少算法的空间复杂度。

本文利用著名的开源入侵检测系统Snort和实际的网络环境,从匹配速度和空间占用两方面对BMLT和BMLS算法进行了测试分析,并与BM算法进行了比较。

相比改进前,算法的时间复杂度最多减少了60%,空间复杂度最多减少了26%。

实验结果表明两种算法均能有效地提高入侵检测的性能。

【相似文献】[1]. 李洋,王康,谢萍.BM模式匹配改进算法[J].计算机应用研究, 2004,(04)[2]. 徐成,孙伟,戴争辉,喻飞.一种面向入侵检测的BM模式匹配改进算法[J].计算机应用研究, 2006,(11)[3]. 梁志荣.具有入侵检测技术的个人防火墙实现[J].网络安全技术与应用, 2006,(04)[4]. 罗峰.入侵检测系统与技术研究[J].电脑知识与技术(学术交流),2006,(17)[5]. 闾浩,何安元.基于IPV6网络入侵检测技术的研究[J].福建电脑,2007,(03)[6]. 邓晓辉,胡丹.网络入侵检测技术[J].南昌高专学报, 2006,(04)[7]. 程拥军.浅谈入侵检测技术[J].湖南冶金职业技术学院学报, 2006,(03)[8]. 庄绪春,孟相如,韩仲祥.高速网络环境中入侵检测技术探讨[J].信息与电子工程, 2006,(04)[9]. 赵准剑.入侵检测技术与计算机网络安全问题思考[J].湖南行政学院学报, 2006,(06)[10]. 兰义华,张颕江,钱涛.入侵检测技术的分析与发展趋势研究[J].网络安全技术与应用, 2005,(08)【关键词相关文档搜索】：计算机技术; 网络安全; 入侵检测; 模式匹配; BM算法; 算法改进【作者相关信息搜索】：浙江工业大学;计算机技术;陈庆章;杜丰;。

基于WM算法改进的多模式匹配算法

Ｊｌ０１ｕｙ２１
文章编号：６１５９（０１０－３３０１７－８６２１）４０８－５
基于ＷＭ算法改进的多模式匹配算法
董迎亮，玄雪花，王德民
（吉林大学ａ．计算机科学与技术学院；．网络中心，ｂ长春１０１）３０２
段。
在高速网络环境中，如果模式匹配算法不能满足处理大量实时网络数据包的要求，入侵检测系统必
然会丢弃部分网络数据包，而这些被丢弃的数据包中就可能包含入侵信息。由于模式匹配算法的性能直
接影响入侵检测系统的检测效率，笔者将以基于误用检ｉ技术的模式匹配算法为研究目标，提出一种改贝０进后的ＷＭ多模式匹配算法。该算法与原ＷＭ（ — ａｂｒｗｕＭｎｅ）算法相比具有运算效率高的优点。
若在Ｔ中能找到Ｐ的出现，则称匹配成功；否则称匹配失败。一次在文本中只能对一个模式串进行匹配的算法，称为单模式匹配算法，可同时对多个模式串进行匹配的算法称多模式匹配算法。
收稿日期：０１４１２１－ —３０作者简介：董迎亮（９２１８一）男，，长春人，吉林大学硕士研究生，主要从事计算机网络安全研究，Ｔ１８ — ６０９０７Ｅｍｉｌｎｄｌ（ｅ）６１２７１５（－ａ）ａｇｙ３ｌｉ＠ｆｍｉｃｒ；民（９８ｏａ．ｏ王德ｘｌｎ１５一）男，，长春人，吉林大学教授，硕士生导师，主要从事智能网络与数据库、网络安全研究（ｅ）６１８４０１１Ｅｍｉｗｍ＠ｊ．ｄ．ＩＴ１８－３９８８１（ — ａｌｄ）ｌｅｕＣ。ｕ１

入侵检测系统中模式匹配算法的改进

Ａｂｔａｔｓｒｃ
Ｉｔｓｎｄｔｔｎｓｓｍ（Ｄ）ａｔｎｌｕｐｅｅｔｏｔｒｗｌ，ａｅｎｄｖｌｅｅｏｅｏｅｋｙｃｍｏｅｔｎｒｉｅｃｏｔｕｏｅｉｙｅＩＳ，ｓｒｉａｓｐｌｎｅｆｅａｌｈｓｅｅｅｏｄｔｂｎｆｈｅｏｐｎｎａａｏｍｔｈｉｂｐｏｔｓ
ａｇｒｔｍｓａｌｒｔｄａｄｉｌｍｅｔｄｉｈｓｐｐｒｂｓｄｏｈｈｕｈｆｉｃｅｓｎｌｅｄｓｎｅｗｉｈａｔｒｏｓｎｔｍａｃ．ｌｏｈｉｍｅｉａｅｍｐｅｎｅｎｔｉａｅａｅｎｔｅｔｏｇｔｏｎｒａｉｇｇｉｉｔｃｈｌｔｅｐｔｎｄｅｏｔｈｉｏｎｄａｅｅ
０引言
随着网络技术的飞速发展，网络和计算机系统面临的安全威胁也日趋严重，侵检测系统作为一种主动的、入实时的人侵检测工具逐渐发展起来并成为网络安全研究的热点。它可以在不影响网络性能的情况下对网络进行监视，而提供对内部从
ｏｅｎｔｏｋｓｃｒｙｓｓｅＩＳｉｆｃｎｅｈｌｎｅｕｏｆｓｄｖｌｐｎｆｅｗｒｅｈｏｏｙａｄｔｅｅｏｅｎｅｓｔｅｉｒｖｄｆｔｅｗｒｅｕｔｙｔｍ．Ｄｓａｉｇｎｗｃａｌｇｓｄｅｔａｔｅｅｏｍｅｔｏｔｏｋｔｃｎｌｇｎｈｒｆｒｅｄｏｂｈｉｅｎｍｐｏｅｏｓｓｓｍｅｏｍａｃｓｔｒｕｈａｌｋｎｓｏｐｒａｈｓａｄｔｅｏｅａｉｎｅｆｉｎｙｏｕｅｍａｃｉｇｍｏｕｅ，ｈａｄｃｒｆＩｆｉｙｔｐｒｒｎｅｈｏｇｌｉｄｆａｐｏｃｅ，ｎｈｐｒｔｆｃｅｃｆｒｌｔｈｎｄｌｔｅｈｒｏｅｏＤＳ，ｓｔｅｆｏｉｉｓｒｉｈｆｅｅｙｔｅｐｒｒａｃｆｐｔｒｔｈｎｌｏｉｍ．Ｔｒｕｈｔｏｏｇｎｌｓｎｐｉｒｏｅ — ｏｅａｇｒｈ，ｈＭｔｇｔｅｔｄｂｈｅｏａｅｆｍｎｅｏａｔｎｍａｃｉｇａｇｒｔｅｈｈｏｇｈｒｕｈａａｙｉｏｒｓｍａｙＢｙｒＭｏｒｌｏｔｍｔｅＢｉ

入侵检测模式匹配算法的研究与改进

通过反复测试发现，在比较的四个算法中，新算法ｌ每次查找所口配的次数最少，效率方面与ＢＭＨ算法接近。新算法２每次匹配的次数少于ＢＭ算法，效率方面与ＢＭ算法接近。通常在查找的模｛｝ｌｌｋｍ）ｋ１＜；【叫对应的字符的下一字符来按坏字符启发模式向右式串出现在文本中重复率高时，新算法的效率明显若模式串Ｐ后面ｋ位和文本串Ｔ中一致的部滑动相应的位数ｓ一，重新进行比较。依次循环，直到高于ＢＭ算法和ＢＭＨ算法。分，有一部分存模式串Ｐ中其他部分观，则可将完全匹配成功或都不匹配为止。举例描述如表３所５Ｊ／结、Ｐ向右移动，直接使这部分对齐，且要求这一致部分示：本文通过分析ＢＭ和ＢＨ等模式匹配算法，Ｍ尽可能地大。本例中按改进后的算法匹配了四趟，比较了提出了…种以Ｂ共Ｍ算法思想为基础，结合ＢＭＨ算ＢＭ算法德语处理时间复杂度为０ｍｓ空问７６。（＋】，＋次法的简化思想的进一步改进ＢＭ算法的方法。该算复杂度为（ｓ，）ｊｆ搜索阶段时间复杂度为Ｏｍｎ。最坏（）改进后的算法预处理时间复杂度为０，空法采用了ＢＭ算法中的跳跃比较思想和ＢＨ简化Ｍ情况下要进行３ｎ次比较，最好情况下的时间复杂间复杂度为０ｓ搜索阶段时间复杂度为Ｏｍ）ｆ，】（ｎ。方法以及向下一位匹配的思想，进而简化了初始化度为（￣ｎ。ＸＣＯ其中ｍ为模式串Ｐ的长度，ｎ为文本串在模式串Ｐ中重复的字符较多时或Ｔ中字符过程，加大了匹配失败后向后跳跃的幅度，减少了Ｔ的长度，是与ＰＴ相关的有限宁符集长度。ｓ、大多在模式串Ｐ现时，中该算法可进一步改进比较次数，提高了模式匹配效率。通过算法测试比２ＭＨ算２．Ｂ为，若文本串Ｔ中与模式串Ｐ最后字符对应的字符较，达到了预期效果。ＢＭ算法为了确定在不匹配的情况下最大的以及其下—个字符都出现在模式串Ｐ中，比较两则参考文献可行移位距离而使用了两种启发，即坏字符和好后者最终按坏字符启发需要滑动的距离大小，然后按川伊刘培玉＿入侵检测中模式匹配算法的究ｌ研ＪＩ．缀启发。两种启发均能导致最大为ｍ若于模式串滑动距离大的字符滑动，（重新进行比较。计算机应用与软件２Ｏ２２）２１４Ｏ５ｎ：１＿１．１进一步的改进后的『牟永钦李美贵，入侵检测系统中模式匹配算２１梁琦．表３改进算法１匹配过程算法增加了预处理时间，法的研究叽电子学￣２０４１）４８０６（２２８ — ３：又章串Ｔｓａｓｒｃｈ１ｎｇｓｅａｓｒｓｈｉｓｅａｒｈ … ４０和比较选择滑动距离的２９．第一次ｓｅａｒｃｌ ’ 时间。由于只是在必要时ｆ贺龙涛，３］方滨兴，余翔湛．一种时间复杂度最优的精第二孜ｓｅａｒｃｈ进行简单的大小比较，进确串匹配算法ｌ．Ｊ软件学报２０，（：７￣８．１０５５６６３１１６三次ｓｅ｜ｌｃｈ１第四次ｓｅａｒｃｈ行比较所花费的时间不ＩＪ孙克雷．４ＩＤＳ中一种快速模式匹配算法ｌＩＪ安徽理．说明带下划线字母衷示发生不匹配，相体字母代表产生启发的字母。会太多。该算法能够确保工大学学４２０２０￣０６６

网络入侵检测系统模式匹配算法研究

周延森汪永好，
（．国际关系学院信息科技系，北京１０９；２１００１．北京电子科技学院计算机科学与技术系，北京１０７）０００
摘要：式匹配算法是网络入侵检测中的关键所在，模它直接影响到网络入侵检测系的实时检测性能。引入４种模式匹配算法，分析其工作原理，通过实验对上述４算法进行了性能测试。种根据实验结果，出了不同算法的应用范围，得为今后入侵
检测系统开发者选择模式匹配算法提供了有价值的参考。
关键词：入侵检测；模式匹配；羊模匹配；多模匹配；有限自动机中图法分类号：Ｐ０文献标识码：文章编号：０００４￣ｏ）７１５—３Ｔ３９Ａ１０— ２（８０— ２７ｏ６０
Ｒｅｅｒｈｏａｔｒａｃｉｇａｇｒｔｍｉｆｅｗｏｋｉｔｓｏｅｅｔｎｓｓｅｓａｃｎｐｔｎｍｔｈｎｌｏｉｅｈｃｏｔｒｒｉｎｄｔｃｉｙｔｍｎｎｕｏ
ＡｂｔａｔＰｔｒｔｈｎｌｏｔｍｓｉｏｔｎｅｗｏｋｉｔｓｏｅｅｔｏｙｔｍ，ｗｈｃｆｅｃｓｒａｍｅｄｔｃｉｎｐｒｏ－ｓｒｃ：ａｔｎｍａｃｉｇａｇｒｈｉｅｉｍｐｒｔｎｎｔｒｒｉｎｄｔｃｉｎｓｓｅａｉｎｕｉｈｉｌｎｅｅｌｉｅｅｔｏｅｆｒｎｕｔｍａｃｆｅｏｋｉｔｓｏｅｅｔｎｓｓｅ。Ｆｕａｅｍａｃｉｇａｇｒｔｍｓａｅｉｔｏｕｅ，ｔｅｅｒｒｉｇｐｎｉｌｎｓｅｎｅｏｎｔｒｒｉｎｄｔｃｉｙｔｍｗｎｕｏｏｒ￣ｍｔｈｎｌｏｉｐｈｒｒｄｃｄｈｎｔｉｗｏｋｎｒｃｐｅａｄｔｔｄｎｈｉｅｐｒｏｍａｃｆｏａｔｒｔｈｎｌｏｔｍｒｕｈｅｐｒｍｅｔｒａｙｅ．Ａｃｏｄｎｘｅｉｎｓｌｔｎｕｅｐｌｉｇｒｎｅｅｒｎｅｏｆｕｐｔｎｍａｃｉｇａｇｒｈｔｏｇｅｆｒｅｉｈｘｉｎｅａｌｚｄａｎｃｒｉｇｅｐｒｍｅｔｅｕｔｓｓｐｙｎｇｒ，ｉｅｒａａｏｆｅｅｔｌｏｉｍ，ｐｏｉｅ￣ｆｌｅｅｅｃｆｅｅｔｇｐ￣ｍｔｈｎｌｏｉｍｒｅｅｏｉｇＮＩ。ｆｉｒｎｇｒｔｄａｈｒｖｄ￣ｕｅａｒｆｒｎｅｏ￣ｌｃｉａｅｍａｃｉｇａｇｒｈｆｖｌｐｎＤ８ｉｎｔｏｄＫｅｒｓｉｔｕｉｎｄｔｃｉｎｐｔｅｎｍａｃｉｇｓｎｌｄｔｈｎ；ｍｕｔｄｔｈｎ；ｆｉｕｏｔｎｙｗｏｄ；ｎｒｓｅｅｔｏ；ａｔｒｔｈｎ；ｉｇｅｍｏｅｍａｃｉｇｏｌｍｏｅｍａｃｉｇｉｔａｔｍａｏｉｎｅ

面向入侵检测的模式匹配算法研究

!& 。
!$!
5;?96@.;;69 算法
相比 56789 :;6<9 算法， 5;?96@.;;69 算法有三个增强的特
性使它具有更高的效率，甚至在最坏的情况下也有很好的时间复杂性。这三个特性如下：（( ）从右向左匹配。将 & 和 ’ 从左端对齐，使得 &( 与 ’( 对齐，如图 ! 。匹配先从 & 的最右端字符开始，判断 !%A(#%，如果直到 & 匹配成功，则向左移动，判断 !%@(A)#%@(。这样继续下去，全部匹配成功或是有不匹配的情况出现。（! ）坏字符移动。第一次匹配从 !%( “* ” 和 !%) “2 ” 开始，如图 ! 。5;?96@.;;69 对模式进行了预处理，得到了一些启发式信息。它使用这些信息计算 & 向右的移动量。算法决定 & 的最右端的字符能够匹配 ’ 的位置，即 “* ” ，如图 3 。
&
概述
在入侵检测系统的实现中，关键的部分是检测引擎的实
个字符 A$!A&… A!，匹配相应的字符 B$%#!B&… B"，则 A 位于 B 中偏移量为 # 的位置，记作：
现。而在检测引擎的实现中，关键的是数据分析模块。数据分析模块涉及到两个问题：如何描述入侵行为；使用什么样的算法来快速准确地检测出入侵行为。论文主要探讨第二个问题。对于基于规则的入侵检测来说，模式匹配算法非常重要，它直接影响到系统的准确性和实时性能。作者主要研究了 ’()*+ ,-(.+ 算法， ’-/+( 01--(+ 算法， 23- 04-(567.8 算法， 9+* 0:76+ ’-/+(01--(+0;-(6<--= 算法， 23-04-(567.8>’-/+(01--(+ 算法。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

函数。下面对ｂｆｒｎＬｓ的数组的存储结构进行说ｎａａｓｉＴｔ
收稿日期：００１１２１ —１ —０修稿日期：００１０２１ —１ —２
作者简介：汉元，，士研究生，究方向为计算机网络榻男硕研
配性能
１１．Ａｃ— ＮＦ在内存中的存储ＢＡ
以模式串集合Ｐ｛ｂｃａｄｂ为例，统Ａ＝ａ，｝传Ｃ算法会把模式串转换成为一个自动机自动机主要由转移函数、效函数和输出函数组成转移函数描述自动失
现计机２１１ ① 代算０ｏ１．
＼
研究与开发
＼、
— — — — — — — ＿ — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — 一 — —
＼＼
明。假设其中有一个状态Ｗ，并存在ｂｆｒｎＬｓ内开ｎａａｓｉＴｔ始于ｘ的位置上，么在内存中存储的数据如图２示。那所
随着现代信息科学技术越受到企业和个人的关注以Ｓｏｎｄ为代表的入侵检测系统的现，提高网络系统安全、御网络攻为防击提供了优秀的解决方案之前的研究表明，侵检测入系统化费在模式配处理＿的时间．通常可以占到总Ｊ处理时间的２％～０．在处理Ｗｅ５３％…．当ｂ密集流量时．
善模式匹配处理速度
关键词：入侵检测系统；多模式匹配算法；ｃ— ＮＦＡＢＡ
０引
言
１ＡＢＡ算法Ｃ— ＮＦ
ＡＣ— ＮＦ全称为Ａｈ — ｏａｉｋＢｓｄＮｎｅｅ— ＢＡｏＣｒｓａｅｏｄｔｒｃ
研究ｓ开发
一 —— —————— ——～———— —————— ———— ————— ——————— ——————— ——————— ———— ——————— —————— ————— —————— ～——————— —————— —————— — —————— ———————— —————— ——————
用的算法各算法的内存占用和配性能如表１所示本文主要对Ａ — ＮＡ算法进行研究和改进ＣＢＦ
表１ｎｒ中各匹配算法特点Ｓｏｃ
同１ＡＣ自动机转移函数图
而当使用ＡＣ～ＮＦ算法时．自动机会被合并成ＢＡ为一个名为ｂｆＴａｓｉ的数组．数组中存储着自动ｎａｒｎＬｓｔ机所有能进入的状态号．以及对应的转移函数和失效
间复杂度只与目标串的长度有关．对恶意攻击数据包有较好的抵御性能．所以获得了许多人侵检测系统的采用。
在２１００年３月发布的Ｓｏｔ．．．ｎｒ２８５３巾．可以选用的多模式匹配算法有ＡＣ～ＵＬ．以及以ＡＣ— ＮＦ为ＦＬＢＡ代表的多种优化型ＡＣ算法其中ＡＣＢＦ为默认使 — ＮＡ
这一比例甚至可以达到８％以］２所以提高模式匹配０２Ｉ１．算法效率对入侵检测系统具有重要意义
目前已经提ｍ的多模式配算法有ＡＣ算法、ＭＷＭ算法．以及ＡＣＢ算法等多种算法其中的ＡＣ —Ｍ算法是一种经典的顺序配算法由于ＡＣ算法的时
ｍｉｓｃＦｎｔＡｔｔ．即基于不确定有穷自动机的ｎｔｉｅｕｏａｉｉｉｎａ
ＡｏＣｒｓｋｈ— ｏａｉ算法与传统的ＡｏＣｒｓｋｃｈ — ｏａｉ算法［比，ｃ４１相
Ａ～ＮＡ可以大幅降低内存占用．保持有较好的匹ＣＢＦ并
机在输入匹配字符时进行如何状态转移．例如从图１叮以看Ｉ在状态０下．叶Ｊ当读人字符为ａ时．以转入状可态】则ｇ０，）ｌ失效函数用于指明当输入字符不，（ａ＝。匹配时应转入的状态输出函数负责判断进入某状态后是否已经与模式串形成匹配
／
／／
入侵检测系统中多模式匹配算法的研究与改进
调汉元。陈元琰
（广西师范大学计算机科学与信息程学院，林桂５１０）４０４
摘要：对网络入侵检测系统中的多模式匹配算法进行研究，重点介绍ＡＢＡ算法的匹配过Ｃ— ＮＦ程，根据ＡＢＡ的匹配特点对其进行优化。实验结果表明，化后的匹配算法能改并Ｃ— ＮＦ优