（计算机软件与理论专业论文）网络入侵检测系统中模式匹配算法的研究.pdf

摘要 模式匹配算法是入侵检测系统中广泛应用的一种核心算法，因此模式匹配算 法的效率对实时性入侵检测系统的性能有直接的影响。本文介绍了入侵检测系统 的基本原理以及模式匹配算法在入侵检测系统中的应用。对入侵检测系统中的模 式匹配算法进行了研究，对一些已有的模式匹配算法进行了性能的分析。其中比 较重要的有单模式匹配算法b m 算法、k m p 算法、r k 算法和多模式匹配算法a c 算法和a c b m 算法。 本文根据入侵检测系统的基本结构构建了一个网络入侵检测系统。实现了数 据采集，数据解析以及用模式匹配算法进行数据的匹配检测的功能来验证了各种 模式匹配算法性能的优劣。本文针对单模匹配式算法b m 算法和多模式匹配算法 a c b m 算法存在的缺点提出了改进的算法。针对b m 算法的改进主要考虑了增加 对模式串串末字符或坏字符的邻接字符在模式串中的首次出现位置以及是否存在 和唯一的判断，根据判断结果重新计算模式的偏移量，增加模式串移动距离，减 少字符重复比较的次数，以提高匹配效率。针对a c b m 算法的改进主要体现在在 b m 算法的基础上，在跳转过程中增加尽可能多的移位，以获得最大前进步长。在 匹配过程中，移动的是一棵多模式构成的模式树，同时使用坏字符移动和好字符 移动策略。实验结果表明，因为在数据的匹配过程中对偏移量重新进行了调整， 省去了很多不必要的匹配的过程，算法的性能有了较大提升。 关键词：网络安全入侵检测模式匹配 a b s t r a c t p a t t e nm a t c h i n gi sac o r ea l g o r i t h mw h i c hi sw i d e l yu s e di nn e t w o r ki n t r u s i o n d e t e c t i o ns y s t e m ，s oi th a sad i r e c t l yi n f l u e n c eo nt h ep e r f o r m a n c eo ft h er e a l - t i m e i n t r u s i o nd e t e c t i o ns y s t e m ( i d s ) t h i sp a p e rm a i n l yi n t r o d u c e dt h eb a s i cp r i n c i p l eo f t h ei d sa n dt h ea p p l i c a t i o no fp a t t e nm a t c h i n gi nt h es y s t e m t h er e s e a r c ho np a t t e n m a t c h i n ga l g o r i t h mh a sb e e nm a d ea n de x i s t i n ga l g o r i t h mh a sb e e na n a l y s i e d s o m eo f t h em o s ti m p o r t a n ta l g o r i t h ms u c ha s s i n g l ep a t t e r n i n gm a t c h i n ga l g o r i t h m ：b m a l g o r i t h m 、k m pa l g o r i t h ma n d i l ka l g o r i t h m ，m u l t i p l ep a t t e r n i n gm a t c h i n ga l g o r i t h m ： a c a l g o r i t h ma n da c - b ma l g o r i t h m a ni n t r u s i o nd e t e c t i o ns y s t e mi sb u i l tb a s e do nt h eb a s i cs t r u c t u r eo fn e t w o r k i n t r u s i o nd e t e c t i o ns y s t e m t h ef u n c t i o n so fd a t ac o l l e c t i o n ，d a t aa n a l y s i sa n dd a t a m a t c h i n gu s e dp a t t e mm a t c h i n ga l g o r i t h m sa r er e a l i z e dt ov e r i f yt h ep e r f o r m a n c eo ft h e v a r i o u sp a t t e m sm a t c h i n ga l g o r i t h m t h ei m p r o v e dm e t h o d sa r ep r o p o s e db a s e do nb p a l g o r i t h ma n da c b ma l g o r i t h m t h ei m p r o v e db pa l g o r i t h md e t e r m i n e dt h ef i r s tp l a c e w h i c ht h el a s tp a t t e nc h a r a c t e ra n dt h ec h a r a c t e rn e x tt ot h eb a dc h a r a c t e ra p p e a r di nt h e p a t t e ns t r i n g o ri fe x i s t e da n du n i q u e r e c a l c u l a t e dt h eo f f s e ta c c o r d i n gt ot h e d e t e r m i n a t i o n , i n c r e a s e dt h em o v i n gd i s t a n c eo ft h ep a t t e ns t r i n ga n dd e c r e a s e dt h e n u m b e r so fc o m p a r i s o n s ，f i n a l l yi m p r o v e dt h ee f f i c i e n c y t h ei m p r o v e da c - b m a l g o r i t h mm a i n l yb a s e do nb ma l g o r i t h m ，i n c r e a s e dt h em o v i n gd i s t a n c ea sm u c ha s p o s s i b l e d u r i n gt h ep r o c e s s ，t h ep a t t e nt r e ef o r m e do fm u l t i p l ep a t t e r n i n gs t r i n g si s m o v e d s i m u l t a n e o u s l yt a c t i c so fb a dc h a r a c t e ra n dg o o dc h a r a c t e rm o v e sh a sb e e n u s e d t h ee x p e r i m e n t a lr e s u l t ss h o w st h a tt h ep e r f o r m a n c eo ft h ea l g o r i t h mg r e a t l y i m p r o v e db e c a u s eo fo m i t t i n gs o m eu n n e c e s s a r ym o v e s k e y w o r d s ：n e t w o r ks e c u r i t yi n t r u s i o nd e t e c t i o np a t t e nm a t c h i n g 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版。 本人允许论文被查阅和借阅。本人授权西北大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。同时授权中国科学技术信息研 究所等机构将本学位论文收录到中国学位论文全文数据库或其它 相关数据库。 保密论文待解密后适用本声明。 学位论文作者签名： 番地：j 幽 指导教师签名：t 主丝星 2，一：7刀 必f 。年占月移日 劢碑彦其7 日 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，本论文不包含其他人已经发表或撰写过的研究成果，也不包含 为获得西北大学或其它教育机构的学位或证书而使用过的材料。与我 - - m i 作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 学位论文作者签名：喜- - p 9 网 伽i 。年6 月6 日 西北大学硕士学位论文 第一章引言 1 1 计算机网络安全技术概述 随着计算机网络的快速发展和广泛应用，各种信息以及资源的共享使人们的 生活得到了极大的便利，然而由于计算机网络系统本身的局限性以及信息系统的 脆弱性等因素，使网络容易遭到恶意的侵犯，引起系统的异常或崩溃。网络安全 面临着越来越大的威胁。在这样的形势下，网络安全技术变得尤为重要，也促使 人们对计算机网络的安全性问题进行深入的思考和探讨。 因为单一的组件无法确保信息的安全性，因此计算机网络安全主要由防病毒 技术、防火墙技术、数据加密技术、网络监控技术、网络入侵检测技术等多个组 件组成。而目前较为成熟的计算机网络安全技术包括防火墙技术、数据加密技术、 防病毒技术、入侵检测技术等等。 1 1 1 防火墙技术 防火墙技术在网络安全方面发挥着很重要的作用。它通过过滤不安全的信息 或者服务降低网络遭受袭击的风险。网络存取访问如果都经过防火墙时，它就能 记录并保存。当有可疑动作发生时，它可以进行适当报警并提供网络受攻击的具 体情况。除此之外，因为防火墙对内部网络还可以进行划分，从而使得内部网重 点网段实现了隔离，如此就降低了局部的网络安全问题对全局网络安全的影响。 防火墙技术通过一些预定义的安全策略，对内部和外部网络之间强制实施访 问控制的网络安全技术，是在信任网络与非信任网络之间。防火墙技术的核心是 以一定的方法和策略检查两个或两个以上的网络之间传输的数据包，从而决定是 否允许网络之间进行通信。 从原理上分类防火墙技术分为以下几种： ( 1 ) 在网络上传输的数据在传输过程中最小都是以数据包为单位进行的。首 先数据被分割成若干个大小的数据包，其中每一个数据包中都包含一定的信息。 防火墙的作用就是通过这些包中的信息来判断这些数据包是否来自于安全站点， 从而将一些来自非安全站点的数据拒之门外。 ( 2 ) 状态检测技术不仅能对各层的数据进行实时地监测和分析，在分析数据 的同时也能有效地判断各层中的非法侵入，这种防火墙检测技术不仅能检测内部 网络的攻击和恶意侵害，更重要的是可以很好地防范控制来自外部网络的的攻击。 第一章引言 ( 3 ) 代理服务技术位于客户端与服务器之间，如果采用c s 模式的系统架构， 当有数据或服务请求从客户端发出，数据首先会发送给代理服务器，由代理服务 器发送到服务器，而服务器的数据同样先发送到代理服务器然后转发给客户端， 这样一来就阻断了客户端与服务器的直接交流，所以外部的恶意侵害就得到了有 效的控制。 虽然防火墙技术在计算机安全方面发挥很重要的作用，但是防火墙技术本身 也存在着很多的缺陷和漏洞。首先无法防范不经过防火墙的其他一些方式的攻击， 其次由于防火墙技术本身难于管理和配置，而且不具有查杀病毒的能力，很容易 造成安全隐患。 1 1 2 数据加密技术 数据加密技术是指将信息经过加密钥匙或是加密函数的转换，变成无意义的 密文，从而隐藏信息内容，使非法用户无法获取信息的真实内容，而接收方则可 以将密文通过解密钥匙和解密函数得到原始信息的技术。 数据加密的过程如图1 1 所示 加密过程解密过程 图1 1 数据加密模型 数据加密的过程为：首先在加密端用加密算法和密钥对输入的数据进行加密 操作得到密文，当密文传送到接收端时利用解密算法和解密密钥进行解密操作， 解密之后就得到了原始信息。 数据加密对信息处理系统的安全起到极其重要的作用，因此广泛地应用于数 字签名，信息鉴别等技术中。但是数据加密并不是万无一失，本身依然存在很多 缺陷，主要有以下几个方面：公开密钥加密技术的加、解密速度慢；密钥是保密 通信安全的关键，对称密钥加密技术的突出问题是如何才能把密钥安全地送到收 2 西北大学硕士学位论文 信方。这种方法不仅花费代价很高，而且密钥分发过程十分复杂；当多人通信时 密钥组合的数量，会出现爆炸性的膨胀，使密钥分发更加复杂化。 1 1 3 防病毒技术 计算机病毒的预防技术主要原理是用特定的方法来防止系统遭到计算机病毒 的破坏。防病毒技术对病毒的预防的工作流程是：首先采用对病毒的规则进行分 类判定，当在程序运行的过程中发现有类似的规则，就判定其为计算机病毒。由 此可见，病毒的预防是一种动态的判定技术。它主要是通过阻止计算机病毒对系 统内存或对磁盘的操作。 计算机防病毒技术大致可以分为计算机病毒预防技术、计算机病毒检测技术 及计算机病毒清除技术。 ( 1 ) 预防病毒技术 预防病毒就是在病毒还未对计算机进行侵害之前对病毒进行处理以此来保证 计算机系统的安全。对计算机病毒的预防应用主要包括两个部分，对已知病毒和 对未知病毒的预防。对已知病毒的预防可以采用特征判定，也就是根据文件的特 征判定其是否为病毒程序，这是一种静态判定技术；而对于未知病毒的预防则根 据未知程序的行为和动作来判定是否为病毒，这种是动态判定技术。 病毒的预防技术常见的主要包括以下几种：一是对磁盘引导区保护。二是对 可执行程序进行加密。三是读写控制技术。四是对系统进行实时监控。 比如我们常见的防病毒卡的主要功能就是监视在计算机和驱动器之间产生的 信号，判断磁盘当前所处的状态，对磁盘提供写保护，对可能造成危害的命令进 行预防。根据哪一个磁盘要进行写操作，是否在进行写操作，磁盘是否处于写保 护等等一系列的状态，来确定病毒是否将要发作。 ( 2 ) 检测病毒技术 通过一定的手段判定出特定计算机病毒的一种方法即为计算机病毒的检测技 术。 常用的计算机病毒检测技术有以下两种： 第一种是在特征分类的基础上，根据病毒程序段的内容、病毒程序的关键 字、病毒程序的主要的特征以及病毒的传染和传播方式和文件长度以及文件的变 化方式等等一些情况，建立的病毒检测技术。 第二种是不针对具体病毒程序的一种校验技术，只对某个文件或数据段进 第一章引言 行检验和计算并保存其结果。以后对该文件或数据段定期或者不定期地进行检查， 如果发现结果有差异，则表示该文件或数据段的完整性已遭到破坏，这样就可以 检测到病毒的存在。 ( 3 ) 清除病毒技术 计算机病毒的清除技术是计算机病毒检测技术之后的一道防病毒技术。因为 计算机程序要求的精确性很高，一般的杀毒软件也有其很大的局限性，对有些变 种病毒的清除无能为力。通常情况下大部分的病毒清除技术是在某种病毒出现之 后，通过对该种病毒进行分析研究，发现其一些特征，从而针对这种特征研制出 来的具有专杀功能的计算机软件，因此这类病毒清除软件技术的发展往往是滞后 的而且具有被动性，没有很好的效果。而如今，随着计算机网络技术的迅猛发展， 使得计算机防范病毒的技术问题显得尤为突出。这主要有几个方面的原因：首先 因为计算机网络所连接的系统成千上万。这样就是使得网络上传播的病毒具有更 大的破坏力。其次要进行恢复对于已经遭到计算机病毒破坏的系统会非常的繁琐 而且棘手，因为它所涉及到的系统是非常广泛的。甚至在有些情况下，网络系统 的恢复几乎不可能。因此鉴于以上原因，实现高效的网络防病毒技术是一件及其 重要的工作。网络上的系统大都采用c s ( 客户端服务器) 的工作模式，因此一 般来说需要从客户端和服务器端两个方面结合才能对病毒进行有效的防范。 在网络系统上处理计算机病毒有以下四种方法： ( 1 ) 客户端防病毒芯片技术主要是通过将一个集成了防病毒功能的芯片安装在客 户端上，这样就能够经常性地保护客户端及其通往服务器的路径不被病毒破坏， 从而可以有效地防范病毒的入侵。客户端是网络系统的门户，将客户端存取控制 与病毒保护能力两者合一之后，做好第一道门的把关工作，用户就可以免去许多 繁琐的管理方面的工作。 ( 2 ) 网络目录和文件安全性管理技术。这种技术主要根据用户对目录和文件的可 操作的级别，分配不同的访问权限和属性。如此系统的程序就无法受到病毒的感 染和寄生，网络中的其它用户也不会受到病毒的感染。 目录和文件的属性和访问权限是网络系统中提供的两种主要的安全措施。系 统中目录和文件的属性主要有：需归档属性、拷贝禁止和删除禁止属性、仅执行 属性、隐含属性、索引属性、读写审记属性、只读属性、读写属性、改名禁止属 性、可共享属性、系统和交易属性等等。目录和文件的访问权限主要有：控制权 4 西北大学硕士学位论文 限、建立权限、文件扫描权限、文件修改权限、文件读写权限、删除权限和管理 权限。 对于公共目录中的系统文件和软件，应该只设置只读属性，对于系统程序所 在的目录不要授予修改权和管理权。 ( 3 ) 服务器防毒技术。服务器是基于c s 模式的网络系统的核心部分，它是决定 着网络系统能否正常运行的关键，因此对于服务器的防病毒能力要求很高。服务 器一旦遭受到病毒感染或破坏，无法正常启动和运行，就会造成整个网络系统的 瘫痪，这种后果也是灾难性的。 目前服务器端的防病毒技术大都采用了n l m 技术。现在市场上以这种技术 研发出的的产品包括c e n t r a lp o i n t 公司的a n t i v i r u sf o rn e t w o r k s ，南京威尔德电脑 公司的l a n c l e a rf o rn e t w a r e 等等。这些产品都是服务器端的防病毒软件，目的是 使服务器不受到病毒破坏能够正常运行，如此就可以从根本上杜绝病毒在系统中 传播和蔓延。 ( 4 ) 网络系统防毒技术。s t a t i o nl o c k 是t r e n dm i c r od e v i c e s 公司的新一代网络防 病毒产品。s t a t i o nl o c k 防毒概念是建立在”病毒必须执行有限数量的程序之后，才 会产生感染效力“的基础之上，s t a t i o nl o c k 也能处理一些基本的网络安全性问题， 例如预放未授权拷贝、存取控制以及在一个点对点网络环境下限制工作站资源相 互存取等。混合型病毒和多形体病毒在实施感染之前也必须获取系统控制权，才 能运行病毒体程序而实施感染。s t a t i o nl o c k 通过这些特点，用间接方法观察，精 确地预测病毒的攻击行为。其作用对象包括多型体病毒和未来型病毒。病毒是一 个不具自我辨别能力的小程序，在病毒传染过程中至少必须拦截一个d o s 中断请 求，而且必须试图改变程序指针，以便让系统优先执行病毒程序从而获得系统控 制权。引导型病毒必须使用系统的b i o s 功能调用，文件型病毒必须将自己所有的 程序代码拷贝到另一个系统执行文件时才能复制感染。由于s t a t i o nl o c k 是在启动 系统开始之前，就接管了工作站上的硬件和软件，所以病毒攻击s t a t i o nl o c k 是非 常困难的。s t a t i o nl o c k 可以根据病毒活动辨别可能的病毒攻击意图，并在它造成 任何破坏之前予以拦截，所以它是目前网络环境下防治病毒比较有效的方法。 1 1 4 入侵检测技术 入侵检测技术可以被定义为对计算机和网络资源的恶意使用行为进行识 别和相应处理的系统。入侵检测是一种能够及时发现计算机系统中存在的异常， 第一章引言 并且报告系统异常现象的技术，可以用来检测计算机系统中是否存在一些异常的 行为或者违反安全策略的行为的一种手段。入侵检测的主要作用是保证计算机系 统的安全运行，免于遭受外部的干扰和攻击，是用于检测任何可以损害或企图损 害网络系统的保密性、完整性和有效性的行为的一种非常有效的安全技术手段。 由于网络的入侵行为和合法行为是可区分的，也就是可以通过提取行为的模 式特征来判断该行为的性质。这也构成了入侵检测技术的重要前提。 入侵检测技术中最关键的问题在于采用何种手段对传输的数据进行分析辨 别，从而检测数据中是否存在入侵行为或其他异常行为。 入侵检测技术的功能主要体现在以下方面： 评估重要的系统和数据文件的完整性，有效性以及保密性，识别反应已知 的异常行为进攻的活动并报警； 查找用户的越权操作，对用户活动和系统活动进行监视，检查系统的配置 是否正确以及系统存在的安全隐患与安全漏洞，提示管理员修补漏洞； 实时对检测到行为进行行为模式的判定，对发现的异常行为进行行为模式 的统计分析并快速反应； 运用统计学原理和知识，检测出新的入侵或从未发生过的入侵，发现新的 攻击模式。 入侵检测的基本原理如图1 2 所示。 图i 2入侵检测原理图 6 西北大学硕士学位论文 1 2 网络入侵检测在计算机安全领域的重要性 随着入侵检测技术的不断发展，在整个计算机安全领域，入侵检测技术在计 算机安全领域的重要作用正得到认可并接受，因此入侵检测技术也得到了广泛的 应用和长足的发展。入侵检测技术建立了一整套的安全防护的结构体系，目的是 为了确保网络的完整性、机密性和安全性避免受到攻击与破坏，从而对计算机网 络进行多层次、多手段高效的监测防护。入侵检测监视计算机网络中发生的事件， 逐一对这些事件和行为进行分析判定，寻找对于系统的安全、机密、完整、可靠 存在威胁的行为。 由于计算机网络系统的复杂性，仅仅依靠某种单一的安全技术来保证安全是 不现实的，因此必须依靠现有的各种安全技术的优势，针对不同的网络规模、网 络应用环境和安全需求实施不同的安全策略。除此之外，还应该保证网络的物理 环境的可靠性，同时在政策法规、网络管理、人员管理等各个方面加强防护，才 有可能满足网络安全的需求。然而无论何种网络安全需求，发现当前网络中出现 的入侵行为都是必不可少的，这是实施安全策略的前提，因此想要有针对性的阻 止攻击者对受保护网络的危害行为，高效的入侵检测技术是必不可少的，同时如 果对告警进行深层的关联分析，还可以对攻击者的入侵意图进行推理，就能够发 现潜在的攻击，制订出有效的防御措施提供可靠的依据，赢得宝贵的时间。因此， 入侵检测技术是非常必要而且必需的，问题的关键在于如何有针对性地解决当前 入侵检测技术的不足。 入侵检测系统在整个安全防御系统中占据重要地位。入侵检测系统在网络中 的主要用于入侵行为检测和追踪定位、网络病毒监控( 特别是蠕虫病毒) 、拒绝服 务攻击发现和追踪、网络行为审计和主机行为审计、网络状态分析等等。 ( 1 ) 入侵行为检测和追踪定位：通常在移动不同风险等级网络的网络边界部署， 例如短信服务接入边界、入侵检测系统出入口边界以及系统核心服务器区域的接 入边界、等等。入侵追踪定位过程利用入侵检测的事件分析和定位功能，可以用 来对入侵者进行进一步的追踪定位，并且发现入侵者来源。 ( 2 )网络病毒监控：主要用来监控网络蠕虫等一些病毒。主要方法是通过对网 络流量健康状况和蠕虫病毒的代码特征检测、对入侵检测事件的分析可以及时定 位出感染病毒的系统或区域。网络入侵检测可以对蠕虫病毒进行预警和及时发现。 7 第一章弓l 言 入侵检测通过对拒绝服务特征的比较和网络包分布状态的分析，可以及时发现拒 绝的服务攻击，从而进一步追踪入侵来源。 ( 3 ) 网络行为审计和主机行为审计：入侵检测系统可以对正常的网络进行行为审 计，比如对系统敏感业务区域关键服务器的网络访问的审计、弱口令的审计等等； 入侵检测系统可以对关键服务器部署主机入侵检测系统监控审计主机操作、文件 系统、注册表配置文件变动等等。这种情况适用于重要服务器，比如b o s s 系统的 数据库服务器、短信网关服务器等等。 ( 4 ) 网络的状态分析：可以通过在重要网络区域部署网络入侵检测系统，用以监 控网络健康状况以及整体网络的安全状况，包括入侵时间分布、入侵事件分布、 被入侵节点分析、蠕虫事件分布等一系列参数。比如在c m n e t 一些主干网络上 部署大规模入侵检测系统，就可以掌握整体网络安全状况。 入侵检测系统在计算机网络和系统受到危害之前进行报警、拦截和响应，提 供了对内部攻击、外部攻击和误操作的实时防护，是一种积极主动的安全防护工 具，入侵检测系统具有以下主要作用：可以检测系统中其他一些计算机安全技术 ( 比如防火墙技术) 无法阻止的异常行为或攻击行为；向管理员报告计算机系统 或网络中存在的潜在的安全漏洞和威胁并提醒其进行修补；检测到系统在受到攻 击前的一系列探测行为，并预先给管理员发出警报；在大型复杂的计算机网络系 统中安装入侵检测系统，不仅能防止网络遭受恶意侵害，还可以显著提高网络安 全管理的质量。 随着人们对入侵检测认识的逐渐加深，入侵检测在整个计算机安全体系架构 中的地位在不断提高，在整个计算机网络系统中发挥的作用越来越大，入侵检测 系统也逐渐正成为一种计算机网络安全领域非常重要的系统。在实际使用中，入 侵检测系统能够对网络中的异常行为行为进行分析判定，发现入侵之后，能够做 出及时快速的反应，尤其对普通的的网络入侵行为有很好的监测能力，对网络安 全起着很重要的保护作用。 入侵检测一般对用户来说并不是必需的，但有了它的确能够有效地减少了网 络的攻击和侵害，保护计算机系统。入侵检测技术的主要优势就是监听网络流量， 但不会影响网络的性能。有了入侵检测，像给网络中安装了监视器一样，可对整 个环境进行监视，但并不影响常规活动。 8 西北大学硕士学位论文 1 3 网络入侵检测的研究现状及发展方向 1 3 1 网络入侵检测的研究现状 1 9 9 5 年s a n d e e pk u m a r 提出用模式匹配的方法进行入侵检测，从此之后入侵检 测系统中的模式匹配方法得到了很快的发展。最初模式匹配算法采用的是采用的 是朴素的算法b f ( b r u t ef o r c e ) 算法，但是这种算法由于本身存在的问题使得对数 据包的匹配效率相当的低，于是人们希望有更有效的模式匹配算法应用于入侵检 测系统。1 9 9 9 年著名的入侵检测系统s n o r t 系统采用了b m ( b o y e r - m o o r e ) 算法， 使检测效率有了极大的提高，此后入侵检测产品大都采用b m 算法或基于它的改 进算法等等，由于当时网络环境较为简单，这些单模式匹配算法也基本能适应了 要求。随着现代网络带宽和网络容量的不断升级，网络技术的快速发展也使得入 侵检测规则库的日益庞大，简单的单模式匹配算法也成为了入侵检测技术继续向 前发展的瓶颈。此时，多模式匹配算法成为模式匹配中研究的热点。目前，国外 方面有以sa n t o n a t o s ，m i k ef i s k 等为主要代表的个人、研究组织积极展开对模式 匹配算法的研究，取得了一系列成果。国内的研究机构也对模式匹配算法的研究 有了更高的重视，如上海交通大学，清华大学，以及其它一些高校西北工业大学、 哈尔滨工业大学等等。然而由于算法速度受限于入侵规则数目或者需要的空间消 耗太大，这些算法应用于入侵检测系统实用性不强。从相关的资料、文献都可以 看到，目前对入侵检测中的模式匹配算法的研究大部分都停留在单模式匹配算法 方面，或是对多模式匹配算法主要进行算法的测试以及对已有算法的一些相应改 进上。虽然这些改进的算法在一定程度上取得一定的成果，有部分的实际意义， 但是总体来说效果都不是很理想，同时也可以看到，提出一个全新的模式匹配算 法难度较大，所以自采用多模式匹配算法进行检测以来，入侵检测产品引入的多 模式匹配算法仍然继续沿用，比如著名的源代码开放的s n o r t 入侵检测系统采用了 a c 或w m 算法；我国著名的的天阗入侵检测产品和联想网御的检测系列产品采 用a c b m 算法等，都采用经典的算法，没有发生太大的变化。 多模式匹配算法因为有着较好的时间效率，有很高的发展前景和应用价值， 是入侵检测模式匹配算法的主要研究方向。多模式匹配算法扫描一次数据包就可 以完成对多个规则模式的匹配，尤其在规则数量非常庞大时，这种方法更能体现 他的优点：效率高，现在主要采用的多模式匹配算法有以下几种： 9 第一章引言 ( 1 ) a c 算法采用一种有限自动机把所有的模式串构成一个集合，可以在只对 文本进行一次扫描的情况下查找多个模式，是最经典的也是应用在为广泛的多模 式匹配算法。 ( 2 ) w m 算法采用三个哈希表来控制模式的跳转，也可以很好地进行多模式匹 配。它内存资源消耗相对较小，但匹配速度比a c 算法略差。 ( 3 ) a c b m 算法是在经典的a c 算法的匹配自动机基础上结合了b m 算法， 使得入侵检测系统的检测速度得到了较大的提高。 本文对入侵检测中的模式匹配算法进行了进一步的研究。首先介绍了已有的 模式匹配算法。b m 算法、k m p 算法和r k 算法都是简单高效的单模式匹配算法；a c 算法是经典的多模式匹配算法，a c b m 算法是在a c 算法的基础上针对具体情况进 行了改进。本文重点讨论了单模式的b m 算法、多模式的a c 算法和a c b m 算法， 分析了这些算法的优缺点，并在此基础上提出了改进的b m 算法和a c b m 算法。 1 3 2 网络入侵检测的发展方向 随着计算机网络技术迅猛发展，网络攻击技术手段也层出不穷，而且这些攻 击方法都采用了各种不同的数据处理技术，使得其破坏性和隐蔽性也越来越强。这 样入侵检测的难度也变得越来越大，目前已有的i d s 远远无法满足入侵检测的需 要。因此入侵检测系统也在向分布式结构发展，将基于主机的i d s 和基于网络的 i d s 结合使用，构筑面向大型网络的i d s ，所以对处理速度及各相关性能的要求 更高。 网络外入侵检测技术的发展趋势为： ( 1 ) 智能化方向。在智能化的发展方面，利用一些具有自学习能力的专家系 统的方法构建入侵检测系统是常用的方法之一。如此不仅使入侵检测系统对网络 的保护防范能力有较大的提高，同时也实现了知识库的不断更新与扩展，此外运 用现在主流的一些技术，例如模糊技术、神经网络技术、遗传算法等一些常用的 方法用于入侵行为特征的分析与辨别，将入侵检测系统与具有智能检测功能的检 测软件或模块两者相结合，也是一种高效的解决方案。应用前景更加广阔。第三 种就是将异常检测和误用检测方法相互结合，使这两种方法能够紧密结合，发挥 各自的作用。 ( 2 ) 基于网络和基于主机的入侵检测系统相结合 基于网络的入侵检测系统和基于主机的入侵检测系统都能检测到对方无法 1 0 西北大学硕士学位论文 检测到的一些网络入侵行为，这样就可以实现系统功能的互补。因为系统使用系 统日志作为入侵检测的根据，基于主机的入侵监测系统在发现外部的攻击是否成 功时相比基于网络的检测系统更加准确，所以结合基于主机的入侵检测系统和基 于网络的入侵检测系统是一个很好的方法，首先可以使用基于网络的入侵检测系 统进行早期检测，如有异常则报警，然后使用基于主机的入侵检测系统来确认入 侵行为是否已取得成功。把现在已有的基于网络和基于主机这两种检测技术很好 地结合在一起，提供集成化的强大的入侵检测功能，包括检测、报警和事件关联 功能等等，入侵检测系统的网络安全保护能力将会有很大的提高。 基于主机的入侵检测系统和基于网络的入侵检测系统两种方法都有各自的 优势，两者可以相互补充使得检测系统更为安全有效。 1 4 本文主要内容 第一章介绍了计算机安全领域的相关知识，包括计算机安全中几种典型的技 术：防火墙技术、数据加密技术、防病毒技术以及网络入侵检测技术。另外介绍 了网络入侵检测技术的发展历史以及发展趋势。 第二章主要介绍网络入侵检测的一些基本概念，网络入侵检测系统的结构以 及分类，最后简要介绍了最著名的网络入侵检测系统s n o r t 系统。 第三章详细介绍了网络入侵检测中很重要的一种方式：模式匹配。介绍了模 式匹配的概念以及几种常用的模式匹配算法。单模式匹配算法有最朴素的模式匹 配算法b f 算法、b m 算法、k m p 算法和r k 算法。多模式匹配算法则包括a c 算 法以及由a c 算法和b m 算法的基础上形成的a c b m 算法。本文详细介绍了这些 算法的匹配过程以及性能。 第四章详细介绍了两种改进的模式匹配算法。在第三章b m 算法和a c b m 算 法的基础上针对它们存在的问题，提出了解决的方法并做了改进。最后对改进的 算法和原来的算法性能做了分析和对比，证明了改进算法的优越性。 第五章对本文的内容做出了总结，并提出了新的工作方向。 第二章网络入侵检测系统概述 第二章网络入侵检测系统概述 2 1 网络入侵检测的相关概念 入侵是指危害资源的可信度、可获取性以及完整性的行为。从入侵策略的角 度分类，入侵一般分为伪装攻击、尝试性闯入、安全控制系统渗透、泄漏、拒绝 服务攻击、恶意使用六种类型。 入侵检测即是对网络中存在的对系统进行入侵行为的检测。它主要通过分析 网络行为、数据，以及从网络中获得的信息和系统中的的信息，检查系统中是否 存在异常的违反安全规则的行为。 由第一章了解到，入侵检测主要通过完成以下任务实现：评估重要的系统和 数据文件的完整性，有效性以及保密性，识别反应已知的异常行为进攻的活动并 报警；查找用户的越权操作，对用户活动和系统活动进行监视，检查系统的配置 是否正确以及系统存在的安全隐患与安全漏洞，提示管理员修补漏洞；实时对检 测到行为进行行为模式的判定，对发现的异常行为进行行为模式的统计分析并快 速反应；运用统计学原理和知识，检测出新的入侵或从未发生过的入侵，发现新 的攻击模式。 入侵检测技术不但可以对网络遭受的内部和外部的入侵和攻击进行实时保 护，而且在网络受到攻击和危害之前也能够进行拦截并且阻止相应入侵。入侵检 测系统( i d s ) 是实现入侵检测技术的软件与硬件的组合。它是一种对网络传输进 行即时监控，在发现可以传输时发出警报或采取主动反应措施的网络安全设备。 与其它网络安全设备的不同之处在于，入侵检测系统是一种积极主动的安全防护 技术。 2 2 网络入侵检测系统的结构 入侵检测即是检测计算机网络和系统以发现违反安全策略事件的过程。传统 的入侵检测系统的结构如图2 1 所示 - 分析 图2 1 入侵检测系统结构图 1 2 西北大学硕士学位论文 入侵检测系统的工作流程可以分为以下几步： ( 1 ) 首先进行信息收集，收集的信息包括网络流量数据、用户与系统的连接 的状态和行为。 ( 2 ) 采用模式匹配方法、统计分析方法和完整性分析方法对收集到的信息进 行分析。模式匹配和统计分析两种方法用于实时的入侵检测，而完整性分析则用 于事后分析。， 互联网工程任务组将一个入侵检测系统分为四个组件：事件产生器、事件分 析器、响应单元、事件数据库。 入侵检测需要分析的数据统称为事件，它可以是基于网络的入侵检测系统从 网络中提取的数据包，也可以是基于主机的入侵检测系统从系统日志和其它途径 得到的数据信息。纵观入侵检测技术的发展历史，其体系结构主要有以下几种形 式： ( 1 ) 集中式结构入侵检测系统 集中式结构入侵检测系统是最早的一种入侵检测网络体系结构，它的优点是 数据采集和分析判断都是在一台主机一个程序来完成。这种体系结构的优点显而 易见，因为数据是集中处理的，因此对网络数据有整体的认识，可以很准确地分 析出入侵行为，然而它的缺点也很明显，当主机遭受攻击或有故障发生时，整个 系统的安全都受到威胁；如果添加了新的设置或改变现有的功能，通常要重新启 动入侵检测系统；统一的大量的数据采集和分析常会引起网络数据过载，运行速 度慢；在一台主机上进行处理，对整个网络系统的监控受到限制。 ( 2 ) 分层式结构入侵检测系统 分层式结构的入侵检测系统是在传统的集中式系统的基础上发展而来的，它 克服了单个主机资源的限制和单个主机数据采集和处理的缺点，在针对协同攻击 上，采用多个检测单元协同处理，每个检测单元通常是智能代理。每一层都有独 立的任务进行，例如在树形分层体系中，底层的代理负责收集需要的数据信息， 并对收集的信息进行简单的处理之后完成简单的判断。中间层代理一方面可以接 受到来自下层的数据并处理，进行较高层次的数据分析、判断和并输出相应的结 果，一方面可以向高层的节点进行数据传输，中间层代理告起承上启下的作用。 最高层节点主要负责在整体上对各级节点进行管理和协调，此外，它还可根据环 境的要求动态调整节点层次关系图，实现系统的动态配置。加入了中间层和底层 第二章网络入侵检测系统概述 的分层式入侵检测系统不仅减轻了高层中央控制的负担，而且增强了检测系统的 伸缩性和扩展性。 ( 3 ) 分布式结构入侵检测系统 随着入侵检测产品在规模庞大的企业中得到广泛应用，分布式技术也成为入侵 检测产品中的主流技术。计算机网络中攻击与防护的对抗是一个很复杂的过程。 一个好的体系结构从长远考虑，必须提高安全系统可以随着外界变化而变化的的 自适应能力和进化能力。然而目前因为缺乏通用标准，入侵检测系统内部各各部 分之间缺乏有效的信息共享并且难以互相之间交换信息和协调一致工作，因此很 大程度上限制了攻击的检测能力，也降低了入侵检测的效率。 分布式系统结构的优点就是能够较好地实现数据的监听，可以检测内部和外 部的的入侵行为。分布式结构入侵检测系统采用的方法是在网络各个部分用多个 代理分别进行入侵行为的检测，当检测到可能的入侵行为时，可以进行协同处理。 这样就提高了检测和处理的效率。而完全的分布式的入侵检测要求代理分布在同 一个层次，这种要求在现实环境中过于严苛，若代理所处的层次太低，则无法检 测针对网络上层的入侵，若代理所处的层次太高，则无法检测针对网络下层的入 侵。所以这种方法并不能完全解决集中式入侵检测的缺点。而且由于分布式检测 时各个代理只是处理一部分网络数据，都没有对网络数据的整体认识，因此无法 准确判断有些跨时间的网络攻击。 2 3 网络入侵检测系统类型 ( 1 ) 基于数据源的分类 按照数据源对入侵检测系统分类通常分为五种类型：网络、主机、内核、应 用程序、目标。 网络：检测系统工作在混杂模式时，网络适配器可以接收所有在网络中传输的 数据包，提交给操作系统或应用程序进行分析。这种方法为进行网络数据流的监 视和入侵检测提供了必要的数据来源。 主机：基于主机的入侵检测系统检测系统通常部署在权限被授予和跟踪的主机 上，根据一定的算法对主机日志文件中的审计数据进行分析，比如可查事件和可 查信息，如多次登录失败的记录等，这样就能得出非法用户的登录企图、冒充合 法用户等一些简单的入侵行为。 1 4 西北大学硕士学位论文 内核：监视器从操作系统内核收集数据，作为入侵检测的依据。另外还包括数 据分析及相应的响应机制，这种方案作为整体的检测系统进行运作，具备良好的 检测效率和数据源的可信度。目前最为著名的是l i d s ，主要针对开发源码的l i n u x 系统。 应用程序：监视器从运行的应用程序中收集数据。数据源包括了应用事件日志 和其它存储于应用程序内部的数据信息。 目标：监视器通常使用消息摘要算法来检测系统对象的更改，比如审计记录、 日志文件，将这种更改与系统的安全策略进行对照，从而判断是否出现入侵或异 常情况。 ( 2 ) 基于检测方法的分类 从检测方法上分类，可以将入侵检测系统分为异常检测和误用检测两种类型。 异常检测 根据使用者的行为或资源使用状况的正常程度来判断是否入侵。异常检测通 用性较强，与系统相对无关，甚至异常检测能检测出未知的攻击方法。然而。它 也存在很多缺陷，主要缺陷在于误检率较高：另外，入侵者的恶意训练是目前异 常检测所面临的一大困难。 异常入侵检测系统存在的优点是：可以试探系统最新和未知的行为，在某种 程度上，它较少的依赖于特定的操作系统；它能够发现任何企图发掘，对于合法 用户超越其权限的违法行为的检测能力大大增强。 但是异常入侵检测系统也存在很多很明显的的缺点：首先较高的虚警概率是 此种方法的主要缺陷，因为信息系统所有的正常活动不一定在学习建模阶段就全 部了解。建立用户正常行为轮廓的时间周期较长，系统的数据统计难于计算和更 新，而且并非所有的入侵都表现为异常。其次由于系统的活动不断变化的，所以 需要不断地在线学习。而这一过程通常带来两个可能的后果，第一是在学习过程 中，信息系统正遭受着非法的入侵攻击，这样带来的后果就是，入侵检测系统的 学习结果中包含了相关入侵行为的信息，这样，系统将无法检测到该种入侵行为。 另外还有一种可能性是在此学习阶段，入侵检测系统无法正常工作，否则生成额 外的虚假警告信号。 误用检测 误用检测根据已定义好的入侵模式，通过判断在实际的安全审计数据中是否 第二章网络入侵检测系统概述 出现这些入侵模式来完成检测功能。因此有时误用检测也被称为特征分析或基于 知识的检测。误用检测检测结果有明确的参照，准确度较高，为响应也提供了方 便。它的主要缺陷在于无法检测未知的攻击类型。 误用入侵检测系统从入侵行为中提取入侵特征来创建规则库，因此可根据该 特点，配置误用入侵检测的相应规则，这样当收到这样的数据包时，则产生报警。 故而，建立在此技术基础上的入侵检测系统能够检测已发现的攻击行为，虚警率 非常地低，同时可以清楚地描述入侵检测的匹配条件，也有利于管理人员采取清 晰明确的预防保护措施。 误用检测和异常检测各有优劣。在实际系统中，考虑到两者的互补性，往往 结合使用，将误用检测用于网络数据包的监测，将异常检测用于系统日志的分析。 2 4 传统的网络入侵检测方法 ( 1 ) 软计算 软计算的方法包含了神经网络技术、遗传算法与模糊信息处理技术。神经网 络的结构是决定神经网络的非线性映射的关键，如果应用具有自动结构调整的神 经网络进行入侵检测，将会大大提高入侵检测的效率及准确性。 ( 2 ) 移动代理 一般情况下，移动代理需要运行在特定的虚拟机环境中。移动代理特别适合作 大规模信息收集和动态处