（机械设计及理论专业论文）入侵检测技术中一种改进的字符串匹配算法的研究.pdf

入侵检测技术中一种改进的字符串匹配算法的研究 摘要 字符串匹配是一个在很多信息处理技术中都必须面对的问题，在入侵检 测技术中由为突出，而其相关的研究也己经开展了多年，一些经典的算法 已经在很多入侵检测系统中得以广泛应用。但现有的一些算法都或多或少 地存在某些局限或不足。为此，相关的研究仍在继续。在总结前人经验成 果的基础上，本文提出了自己的新的想法，并将新的想法通过算法加以实 现，最后通过实验验证了算法的正确性和提高之处。 由于目前没有任何一种字符串匹配算法能够适应各种情况，达到最好、 最坏及平均时间复杂度都达到最优，只是理论上存在上述的可能。因此本 文提出的算法只是对前人算法的一种改进，让新的算法更适合于多字符串 并行查找，以及适应动态地增加模式字符串的情况。具体说来，本文得到 如下的成果： 其一：提出一个分割定理，证明了通过非“准匹配”字符可以将大文本 分割为若干个用于匹配的小文本。 其二：提出一个采样定理，证明了针对某一模式串，当采样距离小于模 式串长度时，我们可以通过抽样检测的方式，发现文本中模式串出现的位 置。 其三：实现了一个依据采样定理思想来设计的算法，并通过算法进一步 证明了采样定理的正确性。 其四：将这一算法，应用到入侵检测的入侵识别引擎当中，用于规则匹 配。并提高了检测引擎的效率。 关键词： b m 算法w m 算法字符串模式匹配多模式匹配 a ni m p r o v e ds t r i n gm a t c h i n ga l g o r i t h mu s e di n i n t r u s i o nd e t e c t i o n a b s t r a c t i t i sak e yi s s u et h a tm a n yt e c h n o l o g i e so fi n f o r m a t i o nh a v et od e a lw i t h ， e s p e c i a l l yu s e di ni n t r u s i o nd e t e c t i o n i th a sb e e nd e v e l o p e df o ral o to fy e a r s n o w ，s o m ec l a s s i c a la l g o r i t h m sh a v eb e e nu s e dw i d e l yi nm a n yi n t r u s i o n d e t e c t i o n s y s t e m s b u tt h e r eh a v eb e e ns o m eb l e m i s h e si nt h e s ea l g o r i t h m s f o rt h i sr e a s o n r e s e a r c h i n gi nt h i sf i e l di ss t i1 1v a l u a b l e t h i sa r t i c l eg e t saf e wn e w c o n c l u s i o n sb a s e do nt h er e s u l t so ff o r m e rr e s e a r c h e r s ，a n dw eh a v em a d ea n a l g o r i t h ma c c o r d i n gt ot h e s en e wc o n c l u s i o n so ft h i sa r t i c l ec o m et r u e a n d w ep r o v et h ec o n e l u s i o n st ob ec o r r e c t i nt h ee n d w eu s eag r e a td e a lo fd a t a s t ot e s tt h en e wa l g o r it h m u n t i ln o wa n yo fs t r i n g sm a t c h i n ga l g o r i t h m si sn o tp e r f e c t ，b u tp e o p l eh a v e g o ts o m el i m i t so ft h i sk i n do fa l g o r i t h mi nt h e r o y s ot h en e wa l g o r i t h mi sn o t p e r f e c tb u ti m p r o v e do nt h eb a s eo ff o r m e rp e o p l e w em a k et h en e wa l g o r i t h m m o r ef i tt om u l t ip a t t e r np a r a l l e lm a t c h i n g w h e nt h en e wp a t t e r ns t r i n g sh a s t oa d df o rm a t c h i n gi nt h es a m et e x t ，t h i sa l g r o i t h mw i l lg i v eag o o ds h o wo f i t se f f e c t i nf a c t t h i sa r t i e l ed of o u rw o r ka sb l o w ： 1 ) w eb r i n gat h e o r e mn a m e ds p l i t t e dt h e o r e mf o r w a r d t h i st h e o r e ms h o wt h a t at e x tc a nb es p l i t t e di n t os u b t e x tw h i c hi ss m a l l e rt h a nt h et e x t ，b y n e v e r a p p e a r e d i np a t t e r n sc h a r a c t e r s 2 ) w eb r i n gat h e o r e mn a m e ds a m p li n gt h e o r e mf o r w a r d t h ist h e o r e ms h o wt h a t at e x tc a nb em a t c h e db ys a m p l e sw h i c hc o u l db es a m p l e df r o mt h et e x t t ou s e t h i st h e o r e mw em u s tp r o v et h e1 e n g t hb e t w e e na n yt w os a m p l e si sn o tl o n g e rt h a n t h a to ft h ep a t t e r nw h ic hw il lb em a t c h e d 3 ) w em a k et h es a m p lin gt h e o r e min t ot r u t h a c c o r d in gt ot h et h e o r e m ，w e m a k ea na l g o r i t h mn a m e ds a m p l e a l g o r i t h mt h a tc a nb eu s e dt os t r i n g sm a t c h i n g 4 ) w eu s et h es a m p l e a l g o r i t h mi n t ot h ee n g i l i eo fi n t r u s i o nd e t e c t i o n ，a n d i m p r o v et h ed e t e c t i o ne f f i c i e n c y n a m e ：c h e ny i n g d i r e c t e db y ：l i ( m a c h i n ed e s i g n ) j i e k e yw o r d s ： b o y e r m o o r ea l g o r it h m ，w u m a n b e ra l g o r i t h m ，s t r i r i g s ，p a t t e r nm a t c h i n g ， m u l t i p l ep a t t e r nm a t c h i n g 插图清单 图2 1 入侵检测系统模型1 0 图3 1s u n d a y 算法不匹配的情况，1 6 图3 2s u n d a y 算法移动的第1 种情况1 6 图3 3s u n d a y 算法移动的第2 种情况1 7 图3 4 删算法的匹配扫描1 9 图5 1 算法处理伪流程图3 9 图5 2 模式串h a s h 表4 0 图5 3 文本h a s h 表4 1 图6 1 删与c y 算法匹配时间对比图4 5 表格清单 表3 1 示例一2 1 表4 1 示例2 7 表4 2 表5 1 表5 2 表5 3 表5 4 表6 1 表6 2 表6 3 表6 4 示例2 9 文本字符位置示意表3 3 文本字符位置示意表一3 4 采样示例表一3 6 h a s h 表示例3 6 删与c y 算法匹配时间对比表4 5 删与c y 主循环查找h a s h 表的次数4 6 删与c y 定位匹配次数表4 6 删与c y 预处理时间4 6 4 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得担撼型堂婴宜总瞳或 其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名： 礁塥 签字日期：瑚7 年6 7 月日 学位论文版权使用授权书 本学位论文作者完全了解扭缝型堂婴塞望瞳有关保留、使用学位论 文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论 文被查阅和借阅。本人授权扭撼抖堂硒宜望瞳可以将学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇 编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：i 昝，彳融 导师签名： 葱l 签字r 期：刎7 年0 7 月巧自 签字同期：年月日 机械科学研究院硕士研究生毕业论文 第一章引言 1 1 研究背景 伴随着网络的发展，网络安全成为了人们越来越为关注的问题。为了创 造安全的网络环境，人们不断的研究各种漏洞防范技术，入侵检测技术就 是其中的一种。入侵检测的作用是在网络的接口处检测网络流量中的数据 是否携带了攻击性信息，将攻击拒之1 3 夕b 。其基本的做法是将网络数据包 看作一个字符串，若能从该字符串中检测到攻击性字符串，就将该数据包 拒之门外。因此，字符串匹配的效率就成了制约检测效率的瓶颈。也因此， 如何快速准确地从一个字符串中找到某个或某些特定的字符串就成了入侵 检测技术中不断探索的问题。当今的网络设备的更新换代可以用飞速来形 容，g b 级的数据流量在普通的局域网中就会经常出现，而检测的g b 级的数 据的现有算法效率始终不能令人满意，所以效率也成为阻止入侵检测对入 侵做出快速反应关键因素之一。 此外，在网络信息以指数级速度增长的今天，信息的良莠不齐也是一个 严重困扰人们的问题。大量黄色信息、反动言论和国家机密在网络上蔓延 和传播，给社会稳定和国家安全造成了严重威胁，如何对这些不良信息进 行网络监管是网络内容过滤系统的重要任务。在这些系统中，使用串匹配 算法对有害信息进行匹配是基本的手段之一。这些系统通常运行在骨干网 结点上，单位时间内需要处理的数据量非常之大，实时性要求非常之高。 作为检测引擎的核心字符串匹配算法性能的好坏更是影响系统性能的 决定因素之一。 同时，随着生命科学的发展，人们对生命物质的微观结构有了越来越清 晰的认识。目前，人类基因组序列的绘制工作己经完成，p r o s i t e ，g e n b a n k 等大型序列库也已经建立。计算生物学的一个基本问题是：寻找一个或一组 第l 页 机械科学研究院硕士研究生毕业论文 基因片断在一个基因序列中的出现位置，以此来比较基因的相似性和遗传 关系；或者根据己知的蛋白质样本去匹配未知的蛋白质序列，来确定这种 未知的蛋白质序列所属的蛋白质种类和功能。由于蛋白质和基因都可以用 建立在一定字符集上的符号序列来表示，所以传统的模式串匹配技术又有 了新的用武之地。 1 2 经典算法 字符串匹配是每个入侵检测引擎必不可少的功能。如何从成千上万的网 络数据包中，高效、准确地检索到可疑的字符串，是设计检测引擎时必须 面对的问题。早期的检测引擎多使用b o y e r m o o r 算法来检测网络数据。虽 然b m 算法的效率虽然比经典的k m p 算法有所提高，但在某些方面却差强人 意。其一，b m 算法中对g o o d s u f f i x 处理过于繁琐，降低了效率。对此， s u n d a y 算法统一了g o o d s u f f i x 的处理方式，使算法更为简练高效、易于 理解；其二，b m 算法每次只能处理一个字符串。对此，w u m a n b e r 算法对 b m 算法做出了改进，允许算法在一次文本遍历的过程中同时对多个字符串 进行匹配，批量地提高匹配的效率。此外，l m 算法引入了用字符块( 而不 是单个字符) 来进行比较的思想，以此来提高b a d c h a r a c t e r ( b m 算法中 提出的概念) 的出现概率。 但是，s u n d a y 与1 i i m 算法又各自保留了b m 算法的缺点，s u n d a y 算法仍 是用单字符进行匹配，w m 算法的g o o d _ s u f f i x 处理虽有提高，仍比不上 s u n d a y 算法简练高效。所以本文希望提出一种算法，综合b m 、w m 和s u n d a y 算法的优点，让新算法更为简单高效。 此外，w m 多模式串匹配算法利用关键词集合相对稳足的特点，先对关 键词集合进行预处理，建立可快速访问的索引结构，然后对文本进行扫描 但是在一些实时的网络监测系统中，待扫描的关键词的规模常常高达几千 至几万，并且更新非常频繁，系统要求关键词匹配算法具备快速地更新关 键词集合的能力。但是，经典的多关键词匹配算法不具备动态地、实时地 增删关键词的能力，每增加或删除一个关键词，都需要对关键词集合重新 笔2 面 机械科学研究院硕士研究生毕业论文 进行预处理，建立新的数据结构。对于关键词集合规模很大并且更新非常 频繁的实时系统来说，这种完全重构的方法代价巨大，根本无法满足实时 性的要求。 1 3 本文结构 本文本着解决经典算法面临的瓶颈问题这一思想，以经典算法为依据， 研究和分析经典算法，从中找到各个算法能够提高查找效率的原理。之后， 将分析得出的各个原理予以综合归纳，最终提出了自己的定理。此外，本 文还依据提出的定理设计了改进的算法，并给出了算法的实验数据。 第一章，引言：引言给出了论文的研究背景，引出了本文所研究问题的 意义，以及目前与该问题相关的前人研究成果。此外，这一章还介绍了本 文的各章组成各章的内容简介，起到了总领全文的作用。 第二章，应用：本章主要介绍了模式匹配与入侵检测的相关知识，用于 说明字符串匹配算法在实际中的应用。用于证明字符串匹配算法的研究意 义。 第三章，介绍：本章主要介绍前人的研究成果。其中以b m 、s u n d a y 和 w m 三个算法为重点介绍对象。正是在对这三种算法的分析归纳过程中，才 发现了本文提出的重要定理采样定理。 第四章，原理：本章主要用来介绍采样定理。为此，这一章先介绍了一 些用于定理证明的相关概念。然后，介绍了一个辅助定理分割定理， 用于协助采样定理证明。最后，用较长的篇幅给出了采样定理的证明。 第五章，实现：本章介绍了一个依据采样定理而提出的改进型字符串匹 配算法，该算法具有1 】i m 算法的多字符串并行查找的优点，同时具备s u n d a y 算法经g o o d s u f f i x 与b a d c h a r a c t e r 相统一的好处，同时该算法能够适 应：在文本不变的时候，关键字动态增加的情况。此外，这一章还给出了 算法的时间复杂性证明。 第六章，实验：本章选择了多组数据对新算法进行了测试，通过比对得 出新算法的优点和不足，并依据实验数据刘新算法优缺点的成凶进行了分 第3 页 机械科学研究院硕士研究生毕业论文 析。并希望通过数据分析得出字符串匹配算法的效率提高方向。 第七章，结论：本章全面总结了本文的成果。从结论中可以看出本文结 论的研究历程。本文的成果是对前人研究成果一步步分析、思考、实践最 终成型的。 机械科学研究院硕士研究生毕业论文 第二章发展动向 由于本文所得的研究成果都是在研究入侵检测技术的过程中发现的，因 此有必要介绍一下字符串匹配算法在入侵检测中的应用。在入侵检测中， 一个关键的技术就是入侵检测引擎的研究。检测引擎的检测效率高低与否 是决定整个系统效率的瓶颈。在检测引擎中，最常用的也是最关键的部件 就是模式匹配部件。模式匹配部件的基本原理也就是字符串匹配，即通过 字符串查找的方式从待检测数据中寻找可疑或确定的有害字符串形式的数 据。为了符合于入侵检测领域的称谓习惯，我们在本章中，多使用“模式 匹配”来代替“字符串匹配”。 此外，引入本章的目的是为了从入侵检测的研究历史中看到字符串匹配 算法的重要意义。 2 1 模式匹配 2 1 1 原理 模式匹配是由入侵检测领域的大师k u m a r 在1 9 9 5 年提出的，首先， k u m a r 提出了入侵信号的层次性概念。依据底层的审计事件，可以从中提取 出高层的事件；由高层的事件构成入侵信号，并依照高层事件之间的结构 关系，划分入侵信号的抽象层次并对其进行分类。其次，k u m a r 将入侵信号 分成四个层次，每一层对应相应的匹配模式。 1 ) 存在( e x i s t e n c e ) 这种入侵信号表示只要存在这样一种审计事件就足以说明发生了入侵 行为或入侵企图，它所对应的匹配模式称为存在模式( e x i s t e n c ep a t t e r n ) 。 存在模式可以理解为在一个固定的时间对系统的某些状态进行检查，并对 第5 页 机械科学研究院硕士研究生毕业论文 系统的状态进行判定。 2 ) 序列( s e q u e n c e ) 有些入侵是由一些按照一定顺序发生的行为所组成的，它具体可以表现 为一组事件的序列。其对应的模式就是序列模式( s e q u e n c ep a t t e r n ) 。序 列模式在检测入侵时需要特别关注间隔和持续时间。 3 ) 规则表示( r e g u l a re x p r e s s i o n s ) 规则表示模式( r e g u l a re x p r e s s i o n sp a t t e r n s ) 是指用一种扩展的规则 表达式方式构造匹配模式，规则表达式是由用a n d 逻辑表达式连接一些描 述事件的原语构成的。适用这种模式的攻击信号通常由一些相关的活动所 组成，而这些活动间没有什么事件顺序的关系。 4 ) 其他 其他模式( o t h e rp a t t e r n ) 是指一些不能用前面的方法进行表示的攻 击。在具体的实现中，很难做到对所有入侵信号进行模式匹配，一般只是 部分实现。 2 1 2 特点 把攻击信号看成一种模式进行匹配检测有以下一些特点： 1 ) 事件来源独立： 模式的描述并不包含对事件来源的描述，模式只需要了解事件可以提供 什么数据，而不管事件如何提供这些数据。 2 ) 描述和匹配相分离： 描述入侵信号的模式主要是定义什么需要匹配，而不是如何去匹配。 3 ) 动态的模式生成： 描述攻击的模式可以在需要的时候被动态生成。 4 ) 可移植性： 入侵模式可以被轻易地移植，而不需要重新生成。 机械科学研究院硕士研究生毕业论文 2 1 3 实现 1 ) 模式的提取： 要使提取的模式具有很高的质量，能够充分表示入侵信号的特征，同时 模式之间不能有冲突。 2 ) 匹配模式的动态增加和删除： 为了适应不断变化的攻击手段，匹配模式必须具有动态变更的能力。 3 ) 增量匹配和优先级匹配： 在事件流对系统处理能力产生很大压力的时候，要求系统采取增量匹配 的方法来提高系统效率，或者可以先对高优先级的事件先行处理，暂缓对 低优先级事件的处理。 4 ) 完全匹配： 匹配机制必须能够提供对所有模式进行匹配的能力。 2 1 4 概念 模式匹配系统主要是用一定的模式描述来提取攻击的主要特征，其基本 任务就是把存放在入侵检测规则集中的己知入侵模式与系统正在检测的网 络包或者重构的i 0 数据流中的文本进行匹配，如果匹配成功，则可以断 定发生了入侵。这个过程是不断循环前进的。 2 1 5 意义 模式匹配检测技术主要优点是检测过程简单，无须训练，检测效率高， 般情况下不存在误检测。模式匹配在网络入侵检测中有着非常重要的影 响，以前的调查结果表明3 0 的处理时间都在进行模式匹配，除了运行时间， 网络入侵检测系统同时需要较小的内存空间，所以需要找到一种好的模式 匹配算法，以提高入侵检测系统的性能。 第7 页 机械科学研究院硕士研究生毕业论文 2 2 入侵检测 2 2 1 定义 1 入侵( i n t r u s i o n ) ： 任何试图危害资源的完整性、可信度和可获取性的动作。 s a l v a t o r e 从访问方式上把入侵分为四种： 1 ) d o s ( d e n i a lo fs e r v i c e ) 拒绝服务攻击，如p i n go fd e a t h ， t e a r d r o p 等； 2 )r 2 l ( u n a u t h o r i z e da c c e s sf r o mar e m o t em a c h i n e ) 远程未授权 访问，如密码破译等； 3 )u 2 r ( u n a u t h o r i z e da c c e s st ol o c a ls u p e r u s e rp r i v i l e g e sb y l o c a lu n p r i v i l e g e du s e r ) 本地非授权用户成为超级用户未授权访 问，如各种缓冲区溢出攻击等； 4 ) p r o b 探测，如p o r t s c a n 等。 2 入侵检测( i n t r u s i o nd e t e c t i o n ) ： 指从网络系统中的若干关键点收集信息并进行分析，从而发现网络系 统中是否有违反安全策略的行为和被攻击的对象，并做出适当的响应。它 既能检测非经授权而使用计算机系统的用户( h a c k e r s ) ，也能检测那些虽有 合法的权限，却滥用系统的用户( i n s i d e rt h r e a t ) 。 3 入侵检测系统( i n t r u s i o nd e t e c t i o ns y s t e n r - - i d s ) ： 标识和隔离入侵的安全技术。 入侵检测被认为是防火墙之后的第二道防线，是动态安全技术的核心 技术之一。一个完善的入侵检测系统必须具有下列特征： 1 )经济性。为了保证系统安全策略的实施而引入的入侵检测系统必 须保证不能妨碍系统的正常运行。 2 )时效性。指必须及时地发现各种入侵行为，能在攻击行为发生的 过程中检测到。 第8 页 机械科学研究院硕士研究生毕业论文 3 )安全性。入侵检测系统自身必须安全，如果系统自身的安全得不 到保障，首先意味着信息的无效，更严重的是入侵者控制了入侵检 测系统而获得了对系统的控制权。 4 )可扩展性。首先是机制与数据的分离，即在现有机制不变的前提下 能够对新的攻击进行检测：其次是体系结构的可扩充性，即在必要 的时候可以在不对系统的整体结构进行修改的前提下对检测手段 进行加强，以能够检测到新的攻击。 在图2 1 中给出了一个通用的入侵检测系统结构框图数据采集构件用 于收集数据，包括任何可能包含入侵行为线索的系统数据。检测分析构件 负责从一个或多个采集构件处接收信息，然后用各种不同的检测方法对数 据进行分析。其中数据分析是入侵检测系统的核心，而模式匹配正式数据 分析中的关键。 机械科学研究院硕士研究生毕业论文 图2 1 入侵检测系统模型 第1 0 砸 机械科学研究院硕士研究生毕业论文 2 2 2 分类 1 数据来源 入侵检测系统按照数据的来源，分为两类： 1 )基于主机的入侵检测系统( ( h o s t b a s e di d s r i d s ) ： 通常安装在受保护的主机上，用来监视、检测某一给定计算机系统或 用户，它有两种类型的信息源，操作系统审计踪迹和系统日志。其主要优 点是，信息源完备。系统产生的日志是归类有序的，它准确地记录了每个 用户的行为序列，这样便可以精确监控每个用户的行为，同时也使得i d s 对信息源的处理简单、一致。其次，对某些特定的攻击十分有效。比如， 审计日志能显示出由缓冲区溢出攻击引起的优先级转移的情况，从而能够 有效地检测出缓冲区溢出攻击。其主要缺点是，首先信息源与操作系统密 切相关。所以i d s 系统不能通用于各种平台。其次，信息源单一，缺乏相 关性。随着黑客入侵技术的不断发展，系统入侵通常发生在整个网络范围 内，涉及一系列主机。所以仅靠单一主机的信息源无法做出准确的判断。 第三，对网络底层攻击检测困难。尽管日志记录了大量的网络事件信息， 但是通过审计日志不能发现网络数据包内容或底层攻击，比如s y nf l o o d 攻击。基于主机的i d s 由于在这些日志中没有找到相应信息而忽略某些攻 击。 2 )基于网络的入侵检测系统( n e t w o r k _ b a s e di d s - - n i d s ) ： 它通常安装在网络的关键段，监控出入网络的通信数据流，按照一定 规则对数据流的内容进行分析，从而发现攻击的企图，做出入侵攻击的判 断。其主要优点是，首先，平台无关性。它以网络数据作为信息源，与主 机平台无关。其次，全局性。由于它通常位于网络的关键网段，所有的通 信都会通过这里。所以，它的信息源涵盖了整个内部网络，有利于根据信 息的相关性作了全局推断。其主要缺点是，首先，对经过加密的数据流进 行分析存在困难。数据流经过加密后，其中的数据特征己经变形，i d s 无法 第1 1 缸 机械科学研究院硕士研究生毕业论文 对其进行分析、识别。其次，难以精确监控用户的行为。它只能从用户交 换的报文中粗略地判断用户的行为，却不能判断出用户行为对目标系统造 成的影响，从而忽略某些入侵行为。比如，用户执行了一个缓冲区溢出程 序，网络i d s 只能够决定用户在执行一个程序，却无法判断用户执行的程 序是否有害。 2 检测方法 根据检测方法的不同，可以将入侵检测系统分为两类： 1 )异常检测( a n o m a l yd e t e c t i o n ) ： 它来源于这样的思想，即任何一种入侵行为都能由于其偏离正常或者 所期望的系统和用户的活动规律而被检测出来。描述正常或者合法活动的 模型是从对过去通过各种渠道收集到的大量历史活动资料的分析中得出来 的。入侵检测系统将它与当前的活动情况进行对比，如果发现了当前状态 偏离了正常的模型状态，则系统发出警告信号。就是说，任何不符合以往 活动规律的行为都将被视为入侵行为。其优点是，首先，能够发现任何企 图发掘、试探系统最新和未知漏洞的行为，同时在某种程度上它较少依 赖于特定的操作系统环境。其次，对于合法用户超越其权限的违法行为的 检测能力大大增强。其缺点主要是很高的误警率。 常用的异常检测方法有：统计模型，神经网络，人工免疫，数据挖掘 等。 2 ) 误用检测( m i s u s ed e t e c t i o n ) ： 是建立在对过去各种己知网络入侵方法和系统缺陷知识的积累之上， 它需要首先建立一个包含上述已知信息的数据库，然后在收集到的网络数 据流中查找与之匹配的项目，从而发现是否有攻击的行为。其优点是，具 备较高的检测准确率和较低的误警率，同时检测的条件可以进行清楚地描 述，从而有利于安全管理人员采取清晰明确的预防保护措施。其缺点是， 收集所有已知或己发现攻击行为和系统脆弱性信息的困难性以及及时更新 庞大数据库需要耗费大量精力和时间。另一个问题在于弱的可移植性。因 为关于网络攻击的信息绝大多数是与主机的操作系统、软件平台和应用类 机械科学研究院硕士研究生毕业论文 型密切相关的。此外，检测内部用户的滥用权限活动将变得相当困难，因 为通常这种行为并未利用任何系统缺陷。 常用的误用检测方法有：模式匹配，状态转换等。 3 时效性 按照数据分析发生的时间不同，可以分为： 1 )脱机分析： 就是指先收集数据，然后再对数据进行分析。而不是在数据收集的同 时进行分析。如对日志的审核、对系统文件的完整性检查等都属于这种。 但是，脱机分析也不会间隔很长，它只是和联机相对而言的。 2 ) 联机分析： 就是指在数据产生的同时对其进行检查，以发现攻击行为。这种方式 一般用于对网络数据的实时分析，对系统的资源要求比较高。一种基于高 效模式匹配算法的入侵检测系统 4 分布性 按照系统各个模块运行的分布方式不同，可以分为： 1 ) 集中式： 系统的各个模块包括数据的收集、分析和响应都集中在一台主机上运 行。这种技术的优点是：数据的集中处理可以更加准确地分析可能的入侵行 为。缺点是：数据的集中处理使检测主机成了网络安全的瓶颈，若它出现故 障或受到攻击，则整个网络的安全将无从保障这种方式适用于网络环境比 ，较简单的情况，因为数据采集对于大型的复杂的网络很难实现。 2 )分布式： 系统的各个模块分布在网络中不同的计算机上，这种分布式结构采用 多个代理在网络各部分分别进行入侵检测，并且协同处理可能的入侵行为， 其优点是：能够较好地实现数据的监听，可以检测内部和外部的入侵行为。 这种方式适用于网络环境比较复杂的情况，并且是现在入侵检测的发展方 向之，一。 机械科学研究院硕士研究生毕业论文 第三章前人成果 字符串检索是指在文本t ( t e x t ) = t h t l ( t ) 中检索子串 p ( p a t t e r n ) = p 1 p l ( p ) ( 称为模式) 的所有出现，求解该问题的两 个最著名的算法是b o y e r - - m o o r e ( b m 算法) 及e n u t h - - m o r r is p r a t t ( k m p 算法) 。此后，d a n i e lm s u n d a y 于1 9 9 0 年提出的一种比b m 算法搜索速度 更快的算法。再后来，b a e z a - - y a t e sr 与g o n n e tg h 又提出了一种基 于整数字位运算，最好、最坏和平均检索时间均为0 ( n ) 的检索算法( 称b y g 算法) 。最近基于b y g 的确切匹配算法，s u nw u 和u d im a n b e r 提出了一种 快速相似匹配算法( 称1 i l m 算法) 。 3 1 阴算法 b o y e r 和m o o r e 两人在l m p 算法的启发下，提出了一种新的字符串快 速匹配算法b o y e r m o o r e 串匹配算法( 简称b m 算法) 。 它的特点是考虑到在匹配比较过程中，不少的情形是前面的许多字符 都匹配而最后的若干字符不匹配，这是采用从左到右的方式扫描的话会浪 费很多时间。因此，改用从右到左的方式扫描模式和正文，这是一旦发现 正文中出现模式中没有的字符时就可以将模式、正文大幅度的“滑过”一 段距离。该算法有下列显著特点： 1 ) 模式与文本的匹配从右向左进行考虑到在匹配比较过程中，不少的 情形是前面的许多字符都匹配而最后的若干字符不匹配，最终导致 匹配失败，这时采用从左向右的方式扫描模式串和文本会浪费很多 时间。因此，b m 算法将p 与t 左对齐，即p 1 与t 1 对齐。匹配 从p 的最右端字符开始，判断p l ( p ) 与t l ( p ) 是否匹配，如果 第1 4 顶 机械科学研究院硕士研究生毕业论文 匹配成功，则向左移动，继续判断p l ( p ) - 1 与t l ( p ) 一1 是否匹 配，循环继续下去，直到p 中的字符全部匹配成功或者是有不匹配 的字符出现。 2 ) 坏字符移动b m 算法对模式进行预处理，得到一些启发式信息，并 使用这些信息来计算模式p 向右移动的距离，该移动函数是针对模 式串的某个位置的。坏字符启发式规则是当发生失配时，移动模式 串使得失配的文本字符与该字符在模式串中的最右出现对齐。移动 函数如下： b a d 函n r ( c ) ：( p ) 当字符c 没有在模式p 中出现 一 【三( p ) 一j 当字符c 出现在模式p 中 3 ) 好后缀移动该移动函数是针对模式中某个子串的。当匹配失败时， 如果已匹配子串长度不为o ，就可以采用好后缀启发式规则，即移 动模式串使得己匹配部分与该部分在模式串中的最右端出现对齐。 4 ) 取较大者作为模式移动的距离当模式与文本不匹配时，根据具体情 况采用坏字符或者好后缀移动函数来计算偏移值。有时同时满足两 种启发式规则，在这种情况下就选取两者中的较大者作为模式串右 移的距离。 b m 算法先对模式p 进行预处理，计算两个偏移函数：b a d _ c h a r ( 针对某 个字符) 和g o o d s u f f i x ( 针对某个子串) ，然后将文本和模式对齐，从右往 左进行匹配，当文本字符与模式字符不匹配时，根据函数b a d _ c h a r 和 g o o d s u f f i x 计算出的偏移值，取两者中的大者，将文本指针往右移，匹配 成功则予以输出。 其主要特征如下：最差情况下找到模式的所有出现的时间复杂度为 0 ( l ( t ) 木l ( p ) ) ，找到第一次出现的时间复杂度为o ( 3 l ( t ) ) ；最优情况下的 时间复杂度为0 ( l ( t ) l ( p ) ) 。 3 2s u n d a y 算法 s u n d a y 算法是d a n i e lm s u n d a y 于1 9 9 0 年提出的一种比b m 算法搜索 第15 页 机械科学研究院硕士研究生毕业论文 速度更快的算法。其核心思想是：在匹配过程中，模式串并不被要求一定 要按从左向右进行比较还是从右向左进行比较，它在发现不匹配时，算法 能跳过尽可能多的字符以进行下一步的匹配，从而提高了匹配效率。 假设在发生不匹配时t i p j ，1 i l ( t ) ，1 j l ( p ) 。此时已 经匹配的部分为u ，并假设字符串u 的长度为l 。如图3 1 。明显的，t i + l + i 肯定要参加下一轮的匹配，并且p m 至少要移动到这个位置( 即模式串p 至 少向右移动一个字符的位置) 。 e r 太t 模式p 图3 1s u n d a y 算法不匹配的情况 分如下两种情况： 1 ) t i + l + i 在模式串t 中没有出现。 这个时候模式串p 0 移动到t i + l + i 之后的字符的位置。如图3 2 。 寸本t 模式p 图3 2s u n d a y 算法移动的第】种情况 2 ) t i + l + 1 在模式串中出现。 这里t i + l + i 从模式串p 的右侧，即按p l ( p ) 一1 、p l ( p ) - 2 、t 0 第1 6 页 机械科学研究院硕士研究生毕业论文 的次序查找。如果发现t i + l + i 和p 中的某个字符相同，则记下这个位置， 记为k ，1 k l ( p ) ，且p k = t i + l + 1 。此时，应该把模式串p 向右移 动l ( p ) 一k 个字符的位置，即移动到p k 和t i + l + i 对齐的位置。如图3 3 。 它本t 模式p口工 图3 3s u n d a y 算法移动的第2 种情况 依次类推，如果完全匹配了，则匹配成功；否则，再进行下一轮的移 动，直到文本t 的最右端结束。该算法最坏情况下的时间复杂度为 o ( l ( t ) 木l ( p ) ) 。对于短模式串的匹配问题，该算法执行速度较快。 3 3 删算法 w u m a n b e r 算法提出了一种基于b m 算法的快速多模式串匹配算法。 w u m a n b e r 算法采用了b m 算法中的不良字符转移机制，但是在计算跳跃 距离时利用了块字符，强化了不良字符转移在多模式串匹配下的作用，提 高了匹配效率。w u - m a n b e r 算法采用了跳跃不可能匹配的字符策略和h a s h 散列的方法，加速匹配的进行。该方法需要对所有模式进行预处理，构建 s h i f t 、h a s h 和p r e f i x 这3 个表，便于后续处理。s h i f t 表用于在扫描文 本串的时候，根据读入字符串决定可以跳过的字符数，如果相应的跳跃值 为o ，则说明可能产生匹配，就要用到h a s h 表和p r e f i x 表进一步判，以决 定有哪些匹配候选模式，并验证究竟是哪个或者哪些候选模式完全匹配。 下面首先介绍预处理过程。 假设模式集合p 中最短的模式长度为l ( p ) 。那么后续讨论仅仅考虑所有 模式的前l ( p ) 个字符组成的模式串，即要求所有匹配的模式长度相等。为 了加快比较速度，对长为l ( p ) 的串进行分组，以b 个长度的字符串为基本 笔1 7 顶 机械科学研究院硕士研究生毕业论文 单位，每次比较长度为b 的子串。对于b 的选取，原文给出了指导公式计 算出一个合适的b 值：b = l o g n u m ( 2 m ) 。这里m - - k ( l ( p ) ，k 是模式的数 目；而n u m 表示字符集的大d , g pn u m = i ，i ；，= c i c 在某个模式中 出现) 。 设x = x 1 x b 为t 中的待比较的长度为b 的子串，通过h a s h 函数映 射得到一个索引值i n d e x ，以该索引值作为偏移得到s h i f t 表中的值，该值 决定读到当前子串x 后可以跳过的位数。假设x 映射到s h i f t 表的入口为 i n d e x 的表项，即i n d e x = h a s h ( x ) ： s h i f t i n d e x ：l ( p ) 一口4 - 1 如果x 没在任何模式中出现 l m i n l ( p ) 一j i x 【女】= 尸l i 一b + 】，v k ，1 女b 其他 这样，就需要将每个模式中长度为b 的子串a j b + 1 至a j 映射到 s h i f t 表中去，这里的映射函数是和上面相同的h a s h 函数。 设当前比较的文本子串x 的h a s h 值为h ，如果s h i f t h = 0 ，说明可能产 生了匹配，那么需要进一步进行判断。于是，用该h 值作为索引，查h a s h 表找到h a s h h ，它存储的是指针，指向两个单独的表：一个是模式链表， 另一个是p r e f i x 表。模式链表中存放的是后b 个字符的h a s h 值同为h 的 所有模式。p r e f i x 表存储的是模式链表中每个模式的前缀h a s h 值，它有利 于进一步减少实际比较次数，因为往往有不少模式具有相同后缀，也就有 相同的h a s h 值。这样，它们都指向h a s h 表的同一表项，从而需要逐一比 较每个可能的模式，增加了比较负担，通过引入前缀h a s h 值的比较能够加 速处理。对于待比较长度为l ( p ) 的串，如果其长度为b7 的前缀与模式的 前缀的h a s h 值也相同，则再将相应的文本串与符合的模式逐一进行比较， 最终判定是否完全匹配。 预处理过程结束，完成3 个表的构建。下面讨论扫描文本进行比较匹配 的过程。匹配从文本的第l ( p ) 个字符开始，文本的扫描从左向右；对模式 的匹配是从模式的后面向前进行的，即从右向左。每次扫描b 个字符t l ( p )