入侵检测中BM模式匹配算法的研究与改进
资源库
论文题目)米堡j型主型撞针匹配翼选自匠所有塑料线作者名挂圭教师睦庙主量参考：重叠主垒在学科的主要七墨垫上打马虎眼所在学院焦皇三星堕落提交日期-行业盟主土旦，且l旦_浙江工业大学硕士学位论文入侵检测中BM模式匹配算法的研究与改进征求摘要
入侵检测是一种动态安全手段，它能主动识别入侵信息，为网络系统提供安全性保护。 模式匹配技术是入侵检测系统识别攻击行为的主要技术，能够快速检测攻击的保存那么，它具有误报率低、准确性高、实用性强等优点。 在高速网络环境下，入侵检测的速度如下由于无法跟上数据包传输速度，有可能导致攻击行为的漏报，入侵检测系统的检测速度越来越快成为取得其实效的瓶颈之一。 降低入侵检测常用模式匹配算法的时间复杂度和空间复杂度噪声是提高检测性能的有效方法。 本论文的研究重点是用于入侵检测的模式匹配法进行研究和改进。本文首先分析了入侵检测的现状，重点研究了网络入侵检测的核心技术——模型公式匹配。 从模式匹配方法的原理出发，提出了面临的问题。 在此基础上，提出了目前最流行的BM算法从原理到性能都进行了详细的分析和讨论。 BM算法匹配效率高，但是，无法记录上次的一致结果。 此外，算法的预处理过程还会增加内存占有量。 本文从时间复杂度和空间复杂度两个方面进行了算法的改进研究，分别提出了两种改进算法。BMLT和BMLS。 BMLT通过设定新的预处理函数计算移动量，可以有效地增加模式列的移动距离。 BMLS可以通过减少处理规则，判断不良文字出现在模式列中的次数，来调整时间在复杂度影响较小的前提下，减少算法的空间复杂度。本文利用著名的开源入侵检测系统Snoa和实际网络环境，从匹配速度和空间占用两者对BMLT和BMLS算法进行了测试分析，并与BM算法进行了比较。 与改善前相比，算法的时间复杂度最多减少了60%，空间复杂度最多减少了26%。 实验结果表明，两种算法能够有效地提高入侵检测的性能。
关键词：网络安全、入侵检测、模式匹配、BM算法、算法改进浙江工业大学硕士学位论文I欢迎SEARCH oN BM
ALGolUTHM FoR INTRUSIoN DETECTIoNABSTRACT
intrusiondetectionisallactivesecurity—defensive mechanism.itcallrecognizeintrusiveinformationandoffersecureprotectiontonetworksystems.thetechniqueofpatternmatchingis主yadoptedbytheintrusiondetectionsystem (ids ) becauseofitshighdetectionaccuracy，lowfalsedetectionrateandstrongpracticability，whichdetectstheattackmorerapidlyandexactly。However，withtheaccelerationofthenetworkspeed，theprocessingspeedofidscannotcatchupwimthepackettransmissionspeed，resultinginthemissingdetectionsofintrusionfrequently。So，the detection speed is becoming aperformancebottleneckofthedetectionsystem.reducing
thetimecomplexityandspacecomplexityofthepatternmatchingalgorithmusedinidsisoneofeffectivesolutionstothisproblem.thisdissertationfocusesontheimprovementofpattemmatchingalgorithmintheintrusiondetection
First，thisdissertationanalysesthecurrentstatusofintrusiondetection，focuses on thepattemmatchingalgorithmwhichisthemostdifficulttechniqueinnetworkintrusiondetection、anddiscussestheprincipleandthedifficulties.thisdissertationdiscussesonthetechnologyprincipleandperformanceofthepopularalgorithmofbm，whichisefficientinpatternmatching。thedisadvantageofbmisthatitcannotrecord the last match result．And its pretreatmentfunctions need lots of memory．This dissertation discusses the improvement of BM in the timecomplexity and space complexity,brings forward two improved algorithms：BMLT and BMLS．The algorithm of BMLT with a new pretreatment function Can increase in the movement ofpattern significantly．The algorithm of BMLS Can reduce the space complexity and maintain thetime complexity by reducing a pretreatment function and recording the number of times that abad char found in the pattern，In this dissertation，the improved algorithms are both implemented with actual networkenvironment and Snort，the famous open—source IDS．Experiments indicate that the timecomplexity is reduced by 60％and the space complexity is reduced by 26％at most．Therefore，the improved algorithms can provide significant improvement in pattern matching performance浙江工业大学硕士学位论文
when using in all IDS．
Key Words： network security，intrusion detection，pattem matching，BM—algorithm，algorithm improvement浙江工业大学
学位论文原创性声明
本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究工作所取得的研究成果。除文中已经加以标注引用的内容外，本论文不包含其他个人或集体已经发表或撰写过的研究成果，也不含为获得浙江工业大学或其它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本人承担本声明的法律责任。…轹午1 醐1盯月订日学位论文版权使用授权书
本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权浙江工业大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本学位论文属于作者签名：导师签名：
1、保密口，在——年解密后适用本授权书。2、不保密彤
(请在以上相应方框内打“√”)黧1差＼r詈 1务 训彳厂叮浙江工业大学硕士学位论文第1章绪 论本章概括介绍了课题的研究背景、研究现状，阐述了本文的研究内容和目标，最后列出了论文的组织结构。1．1研究背景
随着计算机网络应用范围的扩大，对网络的各种攻击与破坏行为与日俱增，采用的攻击方法和手段也层出不穷。由于因特网中许多基础协议在制定时过于注重开放性和交互性，对安全性却有所忽视，使得网络防御变得愈加困难。计算机网络的安全问题，目前已经为计算机网络应用和信息化建设领域中的关键问题。
入侵检测(Intrusion Detection)0-3】是一种新型的安全防御措施，与防火墙、VPN、信息加密等传统安全防护技术不同，它可以主动识别针对网络资源(广泛意义上来说是针对信息系统)的恶意企图甚至恶意行为，并做出及时的响应。作为一种主动防御技术【4】，入侵检测在很大程度上弥补了传统安全技术的种种不足，因此入侵检测系统IDS(IntrusionDetection System)也逐渐成为网络安全市场上的主导产品，开始在各种不同的网络环境中发挥关键作用I引。
对入侵检测系统研究的最核心部分就是对入侵检测技术的研究。20世纪90年代后，随着基于网络的入侵检测系统的问世，对入侵检测技术的研究进入了快速发展阶段。其他工程领域的一些方法也逐渐被人们引入该领域，像神经网络、人工智能、数据挖掘、免疫学方法等。但是，从根本上说，上述这些方法大多还处于试验研究阶段，实用性不高。而基本的模式匹配方法由于技术相对成熟、检测原理简单易懂、实现难度小、准确率高、实时性好等优点而备受青睐，在入侵检测产品中得到了广泛的应用。模式匹配是指把从网络上捕获的每一条数据报文和预先定义好的入侵规则树进行匹配。如果发现存在一条入侵规则与该报文相匹配，就表示检测到一个攻击行为，接着按照规则指定的操作进行处理(如发送警告等)；相反如果搜索完所有规则都没有找到任何一条可与之匹配，则表示该报文是正常报文。模式匹配过程是入侵检测中运行时间和存储空间消耗最大的环节之一，需要高效的模式匹配算法作为保障。因此模式匹配算法直接影响l浙江工业大学硕士学位论文
检测性能，对入侵检测而言有着重大意义。
目前入侵检测领域中存在多种模式匹配算法。作为情报密码学中广为应用的字符匹配算法，近年来BM(Boyer-Moore，BM)算法【6J在入侵检测系统中也起到了很好的应用效果，典型的入侵检测系统Snort就采用了BM算法。但是在实际应用中，BM算法也暴露出了一些缺陷，如检测效率不够高，导致在高速网络环境下入侵检测的速度可能跟不上数据包的传输速率，进而导致丢包和漏检现象；同时算法本身的内存占用量也偏大。针对BM算法的上述缺点，本文基于时间复杂度和空间复杂度两个角度分别提出了BM算法的改进算法：BMLT和BMLS，目的是加快算法的模式匹配速度或者减少算法的内存占用量，进而提高网络入侵检测系统的性能。1．2入侵检测及模式匹配算法的研究现状1．2．1 入侵检测研究现状
对入侵检测的研究最早可追溯到20世纪80年代，但其真正受到重视并快速发展还是在因特网兴起之后。入侵检测技术的研究和发展历史可按时间顺序简述如下：
1 980年，在一份名为((Computer Security Threat Monitoring and Surveillance))的技术报告中，Anderson提出了安全审计系统的改进建议【7l，其目的是检测计算机网络用户的非授权活动。在文中，Anderson还首次构建了检测的基本思路。
1 984--1 986年，Denning和Neumann在SRI公司中设计实现了IDES(Intrusion DetectionExport System，入侵检测专家系统)。作为一种基于主机的入侵检测系统模型18】，IDES系统包括了统计分析和专家系统两大组件，能同时实现基于规则的误用检测技术和基于统计分析的异常检测技术。1987年，Denning在独立发表的一篇论文中正式提出了入侵检测的基本模型19】，并设计出了几种用于入侵检测的统计分析模型，入侵检测领域的研究工作宣告启动。
1990年，第一个基于网络的入侵检测系统模型NSM(Network Security Monitor)【7j出现了；这是入侵检测技术第一次将实际的网络数据包作为输入的信息源。NSM系统可在TCP／IP体系中截获分组数据并分析研究，实现异构网络环境下对异常活动的监控。1996年以后，入侵检测技术走出了实验室研究阶段，逐步出现了大量的商用入侵检测系统。早期的入侵检测系统都是基于主机的(一般称为HIDS)，这类系统主要在系统调用和应用层审计上完成信息收集工作，然后试图从系统日志来判断误用事件和入侵事件的线浙江工业大学硕士学位论文索。当前流行的入侵检测系统大多是基于网络的(～般称为NIDS)18J，主要通过实时监控网络中的关键路径来捕获分组，并把截获的原始网络包作为数据源来分析和检测入侵行为或入侵企图。该类系统通常被部署在网段中的一台独立主机上，采用被动监听的工作模式，因此不会影响服务器或其它主机的正常运行；而且数据包分析通常采用标准化协议进行，因此一般不存在移植性问题。检测系统实现网络监控的技术难点是数据量十分庞大，需要其根据所采用的操作系统特征对网络异常行为进行准确的判断。目前在网络入侵检测系统中最为常见的是由Martin Roesch设计开发的Snort系统。该系统具有实时数据流量分析能力，能够进行网络协议分析，并在此基础上完成对信息内容的搜索和匹配，是一个强大的轻量级入侵检测系统lloJ。更重要的是，Snort系统基于GPL(GNU通用公共许可证，GNU General Public License)，是一个开源软件，因此通常被用于入侵检测系统的性能改进研究。1．2．2 模式匹配算法研究现状
入侵检测系统通常被部署在重要网络内部或者其边界入口处，实时捕获网络内部或进出网络的数据流并进行综合分析，从中发现可能的入侵行为并进行实时响应(报警或阻断)。在系统工作过程中，模式匹配算法作为一种快速搜索攻击特征的方法，是实现基于攻击特征误用检测的核心技术，算法的运行效率直接影响到整个系统的检测性能。
自1995年Sandeep Kumar在他的博士论文【ll】中提出使用模式匹配的方法来检测入侵行为以来，入侵检测系统中的模式匹配方法得到了长足的发展。最初采用的是朴素的模式匹配算法BF(Brute Force，BF算法)，这种算法对数据包的匹配效率相当低，于是人们希望将更有效的模式匹配算法应用于入侵检测。在对BF算法进行严格分析的基础上出现了KMP算法，该算法从本质上讲就是出现失配情况下带有智能指针初始化的BF算法，在一定程度上提高了模式匹配的工作效率【12】。但KMP算法只有在模式串与主串之间存在大量“部分匹配”情况时才能显示出其优越性，使用起来有很大的局限性。随后产生的BM由于使用了启发式搜索，能够在搜索时跳过大部分主串文本，从而拥有较高的运行效率。BM算法在实际应用中往往比KMP算法快上3～5倍，该算法也逐渐成为入侵检测系统中使用的主要算法【13l。1999年著名的轻量级入侵检测系统Snort引入了BM模式匹配算法，这使得检测效率有了巨大的改善，此后入侵检测产品大都采用BM算法或基于它的改进算法。在BM改进
算法中较为成功的如BMH(Boyer．Moore—Horspool，BMH)算法，该算法针对BM算法预浙江工业大学硕士学位论文
处理阶段复杂、匹配效率不高的缺点，对预处理函数进行了简化处理，采用单一规则启发的方法，在一定程度上减少了字符比较次数，但是BMH算法仅在自然语言环境下改善效果显著，适用范围较小【141。另一种常见的BM改进算法是QS(Quick Search，QS)算法，该算法主要增加了BM算法的比较方向，在发生失配时，首先分析模式串当前位置右边的主串字符，根据其是否在模式串中出现来生成跳跃距离，减少比较次数，QS算法的缺点也是适用范围较小，仅在模式串较短或者相对于字符表来说模式串中出现的字符较少的情况下拥有较好的匹配效率115J。目前，国外方面以S Antonatos，Mike Fiskll6】，Coit C jtl7】等为权威代表的个人或机构大量发展了入侵检测环境下的模式匹配算法研究。国内也积极开展了这方面的研究，如清
华大学的宋华，研究改进了BM算法的签名容量【18】；上海交通大学的王永成，对QS算法进行了性能改进【】91。而河北大学、哈尔滨工业大学、西北工业大学、南京师范大学等120-24]一些其它高校主要从多种模式匹配算法的性能比较测试、较长模式串分解、多处理器并行匹配等角度对模式匹配算法进行了改进研究。近年来，随着不同学科间逐步形成的领域融合，模式匹配算法中也逐步加入一些其他学科的研究手段，如投票机制‘251、半聚类1261、人工免疫仁7】等。从以上文献资料可以看到，BM是目前所知平均情况下效率最好的算法，也是当前网络入侵检测系统中最常用的模式匹配算法，目前针对入侵检测中模式匹配算法的研究主要集中于算法的描述测试以及对BM算法的一些改进研究上。而现有的许多BM改进算法基本只是在该算法的时间或空间单一性能上做简单改进，虽然也取得了一定的成果，但算法性能基本都受限于入侵规则数目或者实现算法本身需要的空间消耗过大，因此总体效果都不是很理想，在入侵检测系统中的实用性不强。本文根据高速网络环境的实时检测要求对入侵检测中的模式匹配算法进行了研究，综合分析了现有模式匹配算法的性能。特别针对目前流行的BM算法在时间和空间两方面存在的缺点进行了讨论，在此基础上相应地提出了两种改进算法，并在高速网络环境下的入侵检测系统中对两种算法完成了性能的测试和比较。
1．3本文研究内容和目标
作为入侵检测技术中的核心算法，模式匹配算法的效率直接影响入侵检测系统的性能。如何提高模式匹配算法的效率，一直是入侵检测技术中的广泛研究的课题。目前国内浙江工业大学硕士学位论文外有许多种模式匹配算法，每种算法各有优势，但局限性也很明显。本文正是在分析目前流行的BM算法的基础上，提出了算法的研究和改进。本文的研究工作主要包括以下几个方面：
(1)研究了入侵检测系统和模式匹配技术，包括入侵检测系统的基本概念、发展历程、国内外研究现状、模式匹配的原理、模式匹配算法目前存在的问题。(2)详细介绍了朴素的模式匹配算法和BM算法的基本思路与匹配过程，同时提出了算法在匹配过程中的优点和不足之处。(3)针对BM算法匹配效率有限及内存占用量大的缺点，分别从降低时间复杂度和空间复杂度两个角度提出了改进的算法：BMLT和BMLS，使得改进后的算法具有一定的高效性和实用性，并举例论证。
(4)利用著名的开源入侵检测系统Snort和实际的网络环境，从时间复杂性和空间复杂性两方面对提出的两种改进的模式匹配算法进行了测试分析。相比BM算法，两种改进算法的时间复杂度最多减少了60％，空间复杂度最多减少了26％。实验结果表明两种算法均能有效地提高入侵检测的性能。同时分析了两种算法各自适用的情况。1．4本文的组织结构本文以入侵检测中模式匹配算法的研究和改进为中心，首先介绍了入侵检测技术及模式匹配技术的相关概况；然后深入研究了模式匹配算法，针对BM算法的不足之处分别从两方面进行了改进，提出了两种改进算法；最后对改进后算法的性能完成了测试与分析。文章的结构和章节安排如下：第一章：绪论。说明了入侵检测技术和模式匹配算法的研究意义，介绍了课题的研究现状，对全文的主要内容和章节安排作说明。
第二章：模式匹配及算法分析。详细介绍了模式匹配算法，包括模式匹配的原理、检测方法、常见模式匹配算法的实现思路及存在的问题。
第三章：模式匹配算法的研究改进。针对BM算法的缺点，从降低时间复杂度和空间复杂度两个方向分别提出了改进算法。举例论证了改进后算法的可行性。第四章：改进算法的测试及结果分析。在实际网络环境中使用Snort系统对改进的算法进行了详细全面的测试，并对实验结果进行了比较和分析。第五章：总结与展望。总结了论文中舯主要工作，并提出了进一步的研究方向及意义。浙江工业大学硕士学位论文
第2章模式匹配及算法分析
本章主要对模式匹配技术做了比较深入的研究，对目前入侵检测中常用的模式匹配算法做出较为详细的分析，并举例进行了算法验证。2．1模式匹配
目前大部分入侵检测系统都是基于网络的，称为网络入侵检测系统(Net IntrusionDetection System，NIDS)。NIDS被放置在比较重要的网段内，实时监视网段中的数据包，并对每一个数据包(或其中可疑的数据包)进行模式匹配分析。如果数据包的内容与NIDS内置的某些规则吻合，NIDS就会发出警报，甚至切断网络连接。整个过程中直接影响系统检测性能的关键技术是模式匹配技术，因此模式匹配技术的研究对入侵检测而言有着重大意义。入侵检测系统采用的入侵检测方法一般可分为基于误用的和基于异常的两大类。基于误用的入侵检测方法主要有模式匹配、状态转移、专家系统等；基于异常的入侵检测方法主要包括统计分析、聚类分析、数据挖掘、神经网络等。当今最成熟、最常见的入侵检测
产品如Snort和NFR(Network Flight Recorder)128]基本上都属于基于误用检测的IDS，而模式匹配算法正是误用检测IDS的必备算法129]。2．1．1 模式匹配原理
字符串模式匹配算法是计算机领域中广泛研究的一项重要技术，在语言翻译、语法检查、数据压缩、网络入侵检测、搜索引擎、计算机病毒特征码匹配以及DNA序列匹配等各种应用中，都需要进行字符串模式匹配。
在入侵检测中，模式匹配算法可以描述为：给定入侵规则库中的一个特定的模式字符串P，在网络数据包丁中进行查找，确定P是否在r中出现。1995年，Kumar首次在入侵检测系统中引入模式匹配算法，经过深入地研究和发展，目前模式匹配已经成为入侵检测领域中应用最为广泛的检测手段。Kumar同时提出了入侵信号的层次性概念…j。通过底层的审计事件提取出高层的事件6
浙江工业大学硕士学位论文
或活动；由高层的事件构建入侵信号，并依照高层事件之间的结构关系，划分出入侵信号的抽象层次并进行分类。在此基础上，如果能按照审计对构建信号的事件进行精确定义，就可以根据抽象的层次得到实例化的层次结构，并在每一层中对匹配信号的复杂性边界进行划分。
根据Kumar的理论，入侵信号可以划分为四个层次：存在(Existence)、序yi](Sequence)、规则表示(Regular Expressions)和其它(Other)。每个层次都有对应的匹配模式，在具体的系统实现中，一般很难做到对所有入侵信号进行模式匹配，而只能实现部分匹配。如常见的Snoa系统主要使用存在模式来表示入侵信号，这也是模式匹配方法中针对网络数据包查找的主要模式。基于模式匹配的入侵检测中需要解决两个关键问题：l、入侵行为的描述方式；2、快速检测入侵行为的模式匹配算法。
2．1．2 模式匹配中的规则描述方法
模式匹配的方法必须依靠确定的入侵模式来完成检测功能，这就需要预先设定好一种入侵行为的描述方式。当前，各个产商的入侵检测系统中定义的描述方式不尽相同，且各具优势，这就导致用户只能依赖开发商来被动升级入侵检测模式库。以目前网络入侵检测系统的典型代表Snort为例，它的优势是轻量级且开放源代码。为了检测出各种不同的入侵行为和入侵企图，Snon需要对采集的网络数据包进行一系列规则的模式匹配，这就要求针对入侵行为的描述方法简洁灵活，能够描述绝大多数入侵行为。Snoa系统采用了一种简单的规则语言来描述对数据包需要进行的操作以及可能情况下的响应动作，该入侵规则描述方法具体介绍如下：一条Snort规则在结构上由规则首部(Ruler Head)和规则选项(Ruler Option)两个逻辑部分组成。其中规则首部定义了规则操作、匹配针对的协议、源IP地址、目标IP地址、子网掩码和端口号等信息。而规则选项则包含报警信息以及需要检查的数据包区域位置信息，以确定是否触发规则中相应的操作【301。
以下为一个Snort规则的典型实例：alert tcp any any->192．168．1．0／24 111(content：”10001 86 aSI”：msg：”mountd access”；)。该规则可描述如下：在任何连接网络192．168．1．0／24中的任意主机的11l端口的TCP协议报文段中，如果发现二进制数据“00 01 86 a5”，便发出报警信息：“mountd access”。圆括号前的内容是规则首部，规则首部中包含了判断数据包“从哪里来，到哪里去，浙江工业大学硕士学位论文
做什么”以及当某个数据包符合该规则所有条件时应该怎么办的信息。规则首部的第一项是规则操作，说明当发现满足条件的数据包时应该如何处理；第二部分判断数据包使用的协议；第三部分是数据包收发双方各自的IP地址及端口号。
圆括号中的内容是规则选项，这是规则描述的核心，入侵检测系统正是根据规则选项来检查网络数据包的。规则选项中定义了入侵数据包具备的典型特征，只有当规则中的所有元素都为真时，才能触发相应的规则操作【301，因此规则选项应具有易用性和灵活性的特点。一个规则的规则选项中可以包含多个选项，不同选项之间使用“；”分隔，表示“与"的关系。每条选项均由关键字和对应的参数组成，两者之间使用冒号“："分隔。网络入侵检测以网络中采集的数据包为数据源，使用模式匹配方法对数据包进行检测从而发现网络中可能存在的入侵事件。其中对数据包的检测就是要在网络数据包中检测是否存在可以代表入侵行为或入侵企图的一些字符串，即查找出某些入侵规则中规则选项content中所标识的字符串。由于规则数较多，模式匹配过程是入侵检测中时间消耗最大的环节之一。如果没有高效的模式匹配算法作为保障，检测过程中就会产生超时溢出错误，此时为了保证正常工作状态，系统将主动地丢弃一些数据包，形成漏检。2．2模式匹配算法概述模式匹配算法最初由入侵检测领域的专家Kumar于1995年提出【11】，该算法的工作原理就是将采集到的信息与网络入侵检测系统中现有的模式数据库进行比较，从中发现违背安全策略的入侵行为。该过程可以很简单(如通过字符串匹配来寻找一条简单的代码或指令)；也可能很复杂(如使用严格的数学表达式来体现安全状态的变化)。模式匹配算法的工作过程描述如下【31】：
(1)对从网络上采集的某一个数据包进行分析。(2)从数据包包首开始和入侵规则进行匹配比较。(3)若比较结果匹配，则报告检测到一个可能的攻击。
(4)若比较结果不匹配，则从数据包中的下一个位置开始，重新进行模式匹配。(5)当数据包中的所有字节比较完毕时，一个入侵规则匹配结束。(6)重复步骤(2)，进入下一入侵规则的匹配比较。(7)重复比较直至每一个入侵规则匹配结束，该数据包的匹配完毕。(8)对下一数据包进行采集分析。浙江工业大学硕士学位论文
随着攻击手段的多样化，入侵检测中需要处理的数据量日渐庞大，对检测效率和检测精度的要求也越来越高。若算法的匹配速度不能适应数据包的传输速度，入侵检测系统将主动跳过部分数据包以免产生系统故障，这将形成漏检和丢包，成为入侵检测性能的瓶颈。因此，模式匹配算法在入侵检测中的重要性日渐突出，人们对算法的研究也越来越深入，一些优秀的算法相继出现。为了衡量比较各种模式匹配算法的优劣，需要对算法进行性能分析。性能分析一般从时间复杂度和空间复杂度两方面来考虑。
时间复杂度(Time Complexity)又称为计算复杂度(Computation Complexity)，是对算法运行时间的相对量度f32】。算法的运行时间是指在计算机内存中一个算法从开始运行到结束所花费的时间总和，大致等于计算机执行某种简单操作(如赋值、计算、比较、返回、转向、输入、输出等)所需时间与该算法需要进行的简单操作次数的乘积之和。因为执行一种简单操作需要的时间主要由计算机本身的软硬件水平决定，而与算法的性能无关，在这里只考虑影响运行时间的另一个因素：算法中简单操作的次数。一个算法无论简单或复杂，最终都被分解成若干简单操作由CPU执行实现；简单操作的次数越多，其执行时间相对就越多。因此通常用算法中包含简单操作次数的多少来衡量一个算法的计算时间性能，称为算法的时间复杂度。如果要讨论的问题规模为聍，算法的时间复杂度应该是刀的一个函数／(n1。实际上，算法的时间复杂度一般很难通过计算精确得出，只能大致估计出相应的数量级。而在模式匹配算法中，主要进行的匹配操作是字符比较，因此实际分析中通常以字符的比较次数来分析算法的时间复杂度。
空间复杂度(Space Complexity)则是对算法在运行过程中占用存储空间大小的量度，具体包括算法本身占用的存储空间、算法在运行过程中额外占用的I临时存储空间以及算法的输入输出数据占用的存储空间【321。对于模式匹配算法，在匹配过程中除了定义若干整型变量对算法的字符比较位置进行存储之外，只需要多加几个数组用以临时存放参与计算移动量的数据，因此其空间占用相对来说较为有限。在实际的网络入侵检测系统中，检测的实时性是主要诉求，因而模式匹配的时间始终是考虑的首要因素。从这个角度分析，以存储空间的增大换取时间效率的提高是完全可行的。同时，随着存储技术的发展，计算机的存储容量迅速增大，存储器本身的价格也日益走低，因此存储空间也逐渐成为算法性能分析中的次要因素。以下将通过性能分析比较来简述模式匹配算法的发展概况。浙江工业大学硕士学位论文
最早提出的模式串匹配算法是朴素的模式匹配算法(Brute．Force，简称BF算法)，该算法从主串的第一个字符开始与模式串中的第一个字符相比较，如果相等，则逐个比较后续字符，否则从主串的下一个字符开始与模式串的第一个字符重新比较。很明显，这是一种强行搜索算法。在最坏的情况下，BF算法的时间复杂度为O(mnl，总计要执行(理一m+1)宰m次字符的匹配运算，特别在主串中多个子串与模式串形成部分匹配的情况下，主串上的匹配指针需要反复回溯，算法的效率很低。1970年，Cook s．A．在理论上证明模式匹配问题可以在O(m+n)时间内解决。根据Cook的研究理论，Knuth D．E．和PrattV．R．构造出了一个算法。与此同时，Moms J．H．在研究正文处理问题时也独立地得出了一个与前两人本质上相同的算法，这两个算法被合称为
Knuth—Moms．Pratt算法(简称KMP算法)【331。KMP算法根据匹配成功部分的字符信息，可以一次将模式串向前移动若干个字符，尽量避免了重复比较，同时也实现了主串上匹配指针的无回溯。为了达到跳跃匹配的目的，KMP算法需要额外计算一个shift表，通过预处理的方式来确定发生失配时需要跳跃的距离。这有时候也会造成主串中的一个字符与模式串中的多个相同字符作不必要重复比较的情形，大大降低了算法的效率，因此KMP算法并不能本质上提高BF算法的性能。不考虑额外的函数计算，仅就搜索阶段而言，KMP算法在最坏情况下的时间复杂度为O(mnl，与BF算法相同。1977年，Boyer R．S．和Moore J．S．设计了一种全新的模式匹配算法Boyer-Moore算法(简称BM算法)【61。BM算法的基本思想是匹配前先对模式串进行预处理，分别计算出两个偏移函数：Badchar和GoodSuffixs，然后将主串和模式串左对齐，匹配比较却从右往左进行。当主串字符与模式字符失配时，根据函数Badchar和GoodSuffix计算出的移动值，取两者中的较大值作为主串上匹配指针的右移量。BM算法大大提高了模式匹配算法的效率，算法在查找阶段的时间复杂度为D(聊玎)，最好情况下的时间复杂度为O(nlm)，空间复杂度为o(o)。在BM算法的研究基础上，又派生出了许多算法。例如Boyer-Moore．Horspool算法(简称BMH算法)[14)，该算法仅采用单一的偏移函数Badchar来确定主串上匹配指针的右移量。查找阶段时间复杂度为O(mn)。
1980年，Karp和Rabin合作从完全独立于KMP算法和BM算法的思路研究出了一种基于数值计算的新算法，称为Karp—Rabin算法(简称KR算法)[34】。该算法利用预先定义好的一个Hash函数将模式串和主串中与模式串长度相等的子串均转换成数值，通过比较浙江工业大学硕士学位论文
Hash函数值的方法来完成匹配。该算法预处理阶段的时间复杂度为O(m1，在最好情况下的时间复杂度为o(m-t-n)，最坏情况下的时间复杂度为O(mn)，空间复杂度为o(o-)。1990年，Sunday D．M．通过对BM算法的简化研究，提出了Quick Search算法(简称QS算法)115]，该算法根据主串字符是否在模式串中出现来决定移动量，适合模式串较短和大字母表情况，在实践中也被证明是一种简捷高效的算法。该算法在一般情况下时间复杂度均为O(mn)，空间复杂度为ob)。纵观上述各种算法，思路各异且性能参差不齐。BM算法可以在匹配过程中跳过很多无用的字符，形成跳跃式的匹配【351，达到快速匹配的目的。现有BM的许多改进算法基本只是在BM算法的时间或空间单一性能上做简单改进，改善的效果并不十分明显。实际研究表明，BM依然是目前所知平均情况下效率最好的算法，也是当前网络入侵检测系统中最常用的模式匹配算法【361。以下将对BM算法进行详细地研究。2．3 BM算法
2．3．1 算法基本思想
首先用数学语言对模式匹配的定义描述如下：
假设有长度为挖的文本字符主串丁和长度为m的模式字符串P，两者都是由字符构成的有向序列，其中主串丁定义在一个有限的字母表∑(如各种自然语言、ASCII码等)上，字母表的大小为盯。模式匹配的目的是确定P在丁内出现的位
放置或丁不含尸体。 将丁
和p中的字符从左到右依次从1开始编号，对于一个指定的偏移像堆积一样，如果丁中有长度
(度为m的子串) T=兹兀儿)为m1)，如果兹/一l=局(坏事----- 1，2…m )，则认为p在丁
去向一致。
与BF算法不同，BM算法侧重于在进行模式匹配时从完成的匹配过程中提取
信息参与模式列移动量的计算，达到高速匹配的目的。 考虑模式列的最后一个字符和主列
字符不一致的概率必须大于首字母‘13’。 模式一致时，首先将模式尸体左对齐主签，沿主
字符串将模式p从左向右移动，而字符比较将从右向左移动。 如果字符不一致，请这样做
图案列p移动更远的距离。 该算法采用两种启发规则——坏字符(Badchar )规则和好后
(Goodsuffix )规则在这两个规则下分别计算图案的移动值，取两者中较大的值，
尽量向右移动图案列P[37.38，直到匹配成功。
11
浙江工业大学硕士学位论文
l、不良的文字规则
此时，为了计算移动量，定义函数沈，胁1(x )。 其中，x是失配时t的相应位置的字符。
加上1(x )可以记述如下。
，f m x不会出现在p上，或者辄只会出现在尸体的最后
加1 ) x ) 2j肌一，其他情况下，之后(石蕊) j:P，=x。l
由于／=o，这里f的值等于模式串P的长度脚。下面举例说明BM算法的模式匹配过程。假设 P：EXAMPLET：HERE IS A SIMPLE EXAMPLE
(1)首先将A和丁·左对齐，并从P的末字符开始右至左匹配，如果匹配成功，则依次向左比较直至P全部匹配或有失配情况出现。此时比较^和％失配。第一次匹配：Pl P卅
E X A M P L I E
H E I R I E J J I l S I A I l S J I l M l P I L l E J l E l X J A I M J P L ET1 乃(2)采用坏字符规则。第一次匹配后发现^=”E”与％=”S”失配，且字符”S”并未在模式串中出现，则模式串应右移距离m使A与死+·对齐。第二次匹配：P1 Pm
E X A M P L I E
H E i R f E I f I I S l I A I I S f I l M l P f L f E I E l X f A I M P l L E％+1 乃(3)采用坏字符规则。比较字符^=”E”和Tz。=…P’失配，且字符”P”在模式串中的位置5上出现，于是模式串向右移动2个位置。第三次匹配：P、Pm
E X A M P L E
H E I R E I I I S A I S 1 M P L E E X l A I M P L E矗+3 兀
(4)采用好后缀规则。从右至左逐个比较直到主串字符”I”与模式串中对应字符”A”失配，此时注意到模式串后缀”MPLE”已经匹配，虽然在模式串中没有出现其他与”MPLE”相同的子串，但是模式串的前缀”EfI是”MPLE”的子串，于是模式串向右移动6个位置。浙江工业大学硕士学位论文第四次匹配：R Pm
E X A M P L l E
H E R E I l S I A S l I M P l L E l E X A M P L E而+9 死
(5)采用坏字符规则a比较字符…P’和”Ett导致不匹配，但是字符…P’在模式串中的位置5上出现，于是模式串向右移动2个位置。此时，匹配完全成功。第五次匹配：P、Pm
E}X A l M l P L E
H E R E I S l A S l I M P l L l E l E l X A M l P I L El★一6 =f★上例中使用BM算法进行模式匹配，模式串需进行4次移动共15次比较，比上一节中朴素的模式匹配算法要快2倍。2．3．2 算法性能分析
通过前面的分析可以看出，BM算法在进行匹配之前，首先需要采用两种启发性规则对主串和模式串进行预处理。这样做的好处是在匹配过程时，主串匹配指针无需回溯，大大减少了比较次数，进而使匹配速度得到了较大的提升。
实践表明，BM算法是比较快的模式匹配算法，该算法在预处理阶段的时间复杂度为O(m+盯)，空间复杂度为D∞+仃)，其中万是与P、丁所在的有限字符集的长度。算法在查找阶段的时间复杂度为D(所以)，其中当匹配一个非周期化的模式时即在最坏情况下至多需要进行3押次比较，而在最好情况下的时间复杂度为O(n／rn)。2．4本章小结本章主要对模式匹配技术及其算法进行了讨论。首先介绍了模式匹配的基本原理，然后对模式匹配算法进行了分析讨论。在众多算法中，BM算法应用最为广泛，是目前模式匹配算法改进的热点。本章着重研究了BM算法的设计思想、原理、算法描述以及算法的复杂度。16
浙江工业大学硕士学位论文
第3章BM模式匹配算法的研究改进
通过前一章的分析可知，模式匹配算法是从某个位置开始，将模式串p与主串r对齐后按某种顺序进行字符的逐个比较，当比较失败，则移动模式串到另一个位置上再次进行比较，直至完成所有字符的比较。决定算法效率的关键之处在于它所计算的移动量，即在失配后模式串能向后移动的距离。BM算法具有一定的模式串跳跃能力，匹配速度较高，是目前最流行的模式匹配算法。但该算法在实际应用中仍存在一些问题和有待改进之处，本章将着重对BM算法进行改进。3．1 BM算法基于时间复杂度的改进3．1．1改进思路的提出
在2．4．1节中，本文通过一个自然语言文本的匹配实例来说明BM算法的设计思想。在入侵检测环境下的模式匹配中，无论是文本主串还是规则模式串均是基于多种编码的随机字符串，字符集较大，而且字符串中可能会出现较多的重复字符。这会令BM算法暴露出一定的局限性。以下将举例说明：假设 尸：D％FDFDFD
T：D％FC&D％FDFDFDCFCF％FDCF％D首先进行算法预处理。根据坏字符规则的比加1(x)函数计算公式可得：工 F ％ D Caettal(x) 1 6 2 8
根据好后缀规则的delta2(j)函数计算公式可得：)O 1 2 3 4 5 6 7
char D ％ F D F D F Ddelta2(j) 7 7 7 2 7 4 7 1(1)第一次匹配，J『=7，字符比较1次；移动量如打臼2(7)=ae#ol(r)-8+8=1。17浙江工业大学硕士学位论文P、Pm
D ％ F D F D F D
D ％ F C & D ％ F D F D F D C F C F ％ F D C F ％ DTI(2)第二次匹配，／=5，字符比较3次；P、Pm
L
移动量沈加2(5)=比加1(％)一8+6=4。D ％ F D F D F DD ％ F C & D ％ F D F D F D C F C F ％ F D C F ％ DT2(3)第三次匹配，完全匹配，字符比较8次；移动量如加2(o)=7。P、PmD ％ F D F D F D J
D ％ F C & D ％ F D F D F D C F C F ％ F D C F ％ DIT6
(4)第四次匹配，j『=5，字符比较3次：兀
移动量detta2(5)=deltal(％)-8+6=4。P、P。D ％ F D F D F D I
D ％ F C & D ％ F D F D F D C F C F ％ F D C F ％ D lTla 品(5)第五次匹配，-，=6，字符比较2次；摊delta2(6)=7。P、PmD ％ F D F D F Dl
D ％ F C & D ％ F D F D F D C F C F ％ F D C F ％ D，k一7 2★此时模式串已到达主串尾，匹配结束。
在上例模式匹配中，文本字符数24，模式串字符数8，共需进行5次移动17次比较。观察整个匹配过程，可以注意到在第二次匹配时得到部分匹配的子串”FD”。而紧接着第三次匹配时虽然完成了模式匹配；但在匹配过程中仍然逐字符比较了一个模式的长度共计8次；可以说第二次匹配时得到的部分匹配信息完全被忽视了。如果可以有效利用第二次匹配的部分匹配结果，对子串”FD”进行记录，那么进行第三次匹配时就可以在一定程度上减少字符比较次数或加快模式串移动，从而减小算法的时间复杂度。18浙江工业大学硕士学位论文3．1．2 算法设计思想
根据以上分析，本文提出一种基于时间复杂度的BM改进算法——BM．Less Time(BMLT)算法。改进后的算法针对部分匹配的结果设置了记录因子，当上次匹配计算出的移动量为delta2(f)时，BMLT算法与BM算法有两个区别：(1)在本次匹配过程中，当在主串中发现己记录的上次部分匹配的子串时，有可能实现跳跃式比较，部分甚至全部跳过此子串，从而减少字符的比较次数。(2)计算下次移动量时要考虑一个函数妇驴以确定最小移动量，即移动量要取deltal(x)、delta2(j)和shifi中的最大值，这无疑会进一步加快字符跳跃频率。BMLT算法的前提是上次匹配中采用了好后缀规则下的移动量，即出现了尸与丁部分匹配的情况。假设尸和丁中共同存在的部分匹配子串为厂，根据／在模式串中的存在情况，可以分别考虑如下三种情况：
(1)情况一：若模式P中还存在另一个相同的子串f(若存在多个／则取距离最近者)，则此时应将P向右移动，使得P中左侧另一个子串f与丁中己匹配的子串厂对齐，这样尸和丁将有可能匹配成功。如图3．1所示。尸：[卫Ⅱ工二二二]D……”
图3．1 BMLT算法在好后缀规则下移动情况一
(2)情况二：若模式P中并不存在另一个相同的子串f，但尸中从首字符开始存在一个子串e，而且丁中已经部分匹配的文本中也包含有这样的子串e，此时应将尸向右移动，使得尸中左侧子串e与丁中己匹配的子串e对齐，如图3．2所示。浙江工业大学硕士学位论文图3．2 BMLT算法在好后缀规则下移动情况二
(3)情况三：若模式尸中同时不存在上述的子串P和子串厂，这就意味着当前尸与丁对应部分中不可能再次出现匹配，此时应将模式串P向右移动的距离为P的长度m。对于上述的情况二，上一次匹配中得到的部分匹配信息完全可以被下一次匹配参考，以得到更大的移动量，BMLT算法为此定义了一个函数s办驴。如果在某次模式与主串进行匹配时，上一次匹配中所记录的部分匹配子串长度IPJe大于当前的部分匹配子串长度I厂l，则触发幽驴的计算。在这种情况下，可称e为记录因子，显然子串ezf是尸的一个后缀子串。图3-3 BMLT算法触发妫驴的移动情况在本次匹配中，口和6分别是P和T中导致失配的字符，从图3—1中可以看出矿也是P的～个后缀子串。之前做了假定H>1／I，所以矽同样是P的后缀子串。令字符口和6在主串中的距离为Y，由于P是P可的边界，尸中长度为fP可I的后缀子串就包含了一个长度为】，=IzfI的字符区间，因此H<】，。再考虑到口≠b，贝．EJ e中不可能包含字符6，此时应至少20
浙江工业大学硕士学位论文
把子串P移动至6的右侧方有可能匹配成功，即最小黼shin为lel-I；I，如图3-3所示。考虑一下BMLT算法在坏字符规则下的性能。在这种情况下字符jc和Y是完全不同的两个字符，此时应将y移动至主串末尾，实际移动距离至少为H+1。如图3—4所示。图3-4 BMLT算法在坏字符规则下的移动情况在以上基于时间复杂度的改进后，BMLT算法流程图如图3．5所示。( JI．始 )
I
I瑚：础妯炉彤；人 ◆卉《三岁匹配失败 i墨(遢笔)申 瓠丫上是√胁
丫f害P}◇仃斗絮f'-瓣lB'J：．胡I，，√一1 I 等 大匹配成功
输出i．I 枣◇杏 ● ●．，hifi：deha2(O)；F-=ln-,,JJ所：，f，”一，．c—J “¨，，∥叫)
l e-+O；严◇l 矿I
．','hi／f-muxts；linF一、1—r
l¨、bib l
图3．5基于时间复杂度改进的BMLT算法流程图浙江工业大学硕士学位论文3．1．3 算法语法描述
i=O；e=O；shift--m；for(i=O；i++；i<=n·m){j=m；
while(j>O&&p[jl----t[i+j】){if(e!=0&&j—硼一shift)j=j—e；elsej巧一1；}
if(i<忡0){
printf(”％d．．，i+1)；shift=delta2(O)；
高等职业学校
else{
f=-m-j；shift=-e-f；
shift=max(deltal(t[i+j】一m+j，delta2(j)，shift)；if(shift=deltal(j))e--min(m—shift，f)；else
{
if(shift pfintf(”Match failed!”)；22浙江工业大学硕士学位论文3．1．4 算法性能分析 对于本节一开始提出的BM算法字符匹配的例子，采用BMLT算法重新匹配如下：假设 尸：D％FDFDFDT：D％FC&D％FDFDFDCFCF％FDCF％D (1)第一次匹配，歹=7，字符比较1次：移动量出加2(7)=比加1(…F’)-8+8=1。P1 ^D ％ F D F D F D D ％ F C & D ％ F D F D F D C F C F ％ F D C F ％ D乃 死(2)第二次匹配，7=s，字符比较3次；移动量如砌2(5)=施加1(”％”)-8+6=4。Pl P。I D ％ F D F D F D D ％ F C & D ％ F D F D F D C F C F ％ F D C F ％ DT2 乃(3)第三次匹配，完全匹配，字符比较6次1，移动量妫驴=7。(其中带阴影的字符表示上次已经被匹配了，本次匹配可以选择跳过)P、Pm} D ％ F D F D F D D ％ F C & D ％ F D F D F D C F C F ％ F D C F ％ D丁6 兀(4)第四次匹配，_，=5，字符比较3次；摊delta2(S)=deltal(”％”)-8+6=4。P、PmD ％ F D F D F D D ％ F C & D ％ F D F D F D C F C F ％ F D C F ％ DTJ3(5)第五次匹配，，=6，字符比较2次；移动量如妇2(6)=7。此时模式串己到达主串尾，匹配结束。户l Pm D ％ F D F D F D D ％ F C & D ％ F D F D F D C F C F ％ F D C F ％ Dn一723 浙江工业大学硕士学位论文 在上例匹配中，主串字符数24，模式串字符数8，共需进行5次移动15次比较。在第三次匹配时，由于前一次已经匹配子串”FD”，所以省略了2次字符比较次数。设厂为模式串P在主串T中出现的次数，BMLT算法的时间复杂度是p(疗+脚)，空间复杂度为o(m+仃)。在最坏的情况下，其时间复杂度为D锄，z)；最好的情况下，时间复杂度为O(n／trll。算法除了在进行匹配之前对模式串P进行预处理之外，在匹配过程中还定义了一个变量e来记录上次匹配中的部分匹配子串，得出最小移动量幽班。然后把s乃驴与坏字符规则下移动的距离幽妇1G)和好后缀规则下移动的距离沈，彻20)两个函数进行最大值求取，确定下一次比较位置，这在一定程度上减少了比较次数，使算法的匹配效率得到了较大的提升。接下来对BM算法和BMLT算法进行定量的性能分析，主要同时从执行时间和空间占用量两方面来比较两者的性能。本次测试采用的系统平台是Windows 2000 Server，用于模式匹配的主串是使用Windump软件在因特网环境下随机采集的500MB容量的网络数据流，存入程序目录下的T1．txt文档。因为数据容量较大，以下仅给出部分数据样本：E：＼test>windump．exe-i 3一t>T1．txt windump．exe：listening on＼Device2qPF_{F6CEF77F·DE8E-4EOA-83CB-E5F98742A9F5)00：05：32：5f：ee：88(oui Unknown)>01：00：Oc：cc：cc：cd(oui Unknown)SNAP Unnumbered，ui，Flags[Command]，length 5001：00：Oc：cc：cc：ed(oui Unknown)>00：05：32：5f．ee：88(oui Unknown)SNAP Unnumbered，ui，Flags【Command]，length 50 IP 10．216．80．1．67>255．255．255．255．68：BOOTP／DHCP,Reply,length 300IP 10．216．80．1．67>255．255．255．255．68：BOOTP／DHCP,Reply,length 30000：05：32：5f．ee：88(oui Unknown)>01：00：Oc：cc：cc：cd(oui Unknown)sNAP Unnumbered，ui，Flags[Command]，length 50802．1 d con_fig 8000．00：e0：0f．9e：8b：ee．8017 root 8000．00：e0：0f：9e：8b：ee pathcost 0 age 0max 20 hello 4 fdelay 15 01：00：0c：cc：cc：cd(oui Unknown)>00：05：32：5f．ee：88(oui Unknown)SNAP Unnumbered，ui，Flags【Command]，length 50802．1d config 8000．00：e0：0f：9e：8b：ee．8017 root 8000．00：e0：0f．9e：8b：ee pathcost 0 age 0max 20 hello 4fdelay 15 为了比较算法在不同形式模式串匹配过程中的体现出来的性能改善，在规则数逐步递增的前提下，本文采用普通文本模式串和重复后缀较多的特殊文本模式串分别对两种算法进行了测试。其中普通文本模式串是利用ASCII码中26个英文字母的大小写字符和阿拉24浙江工业大学硕士学位论文 伯数字组成的字符库，随机生成长度固定为6字节(如“pD7flg”模式串)的字符串。字符串生成代码如下： #include { int flag，charLengt；int ij，k=0；char p[Pl+1]={NULL}； srand((unsigned)time(NULL))；for(i=O；i<60；i++)／／这里生成60个模式串{for(j=0j flag=randO％2； if(flag)p[k州_’A’+rand0％26；else p【k++】=…a+randO％26；}p【k】-叼。；k=O； printf(”％s＼1l”，ch)；}getchO；) 对于重复后缀较多的特殊文本模式串，考虑到自然英文文本中各种ASCII字符出现的概率，本文选取前3个字节随机，后3个字节由字符“t"、“e”、“d"随机排序组成(如“aN4etd”模式串)的6字节字符串。字符串生成代码如下：#include #include #define P2 6／／模式串长度固定为6int main(){ int flag，charLengt；int ij．k=0；char p[P2+1]2{NULL}； srand((unsigned)time(NULL))；for(i=0；i<60；i++)／／这里生成60个模式串{for(j=Oj<2j++){ flag--randO％2； if(flag)p【k++】-～A+rand()％26；else p[k抖】一’a’+randO％26；char p口base={lt．，’e。，’dt)；int tmp=rand()％2；ch区卜+]+=base[tmp]；) p【k】=-＼O’；k--O； printf(“％s＼11”，ch)；)getchO；) 为了尽可能减小测试误差，每一项测试均反复进行5次，测试结果取平均值。两种算法的测试结果对比如下：1．时间复杂性比较 首先进行普通文本模式串的测试。选取模式串60个作为匹配规则，然后依次增加类似本文20条直至120条规则分别对主串进行模式匹配，通过计时程序得到如图3-6所示的时间复杂性比较图。从图中可以看出，BMLT算法性能有一定的提高，但是改善的幅度并不是很大，大约在4％～12％左右。26 浙江工业大学硕士学位论文(秒) 60 80 100 120 规则数囹BM算法口BMLT算法图3-6普通文本情况的时间复杂性比较图 接着进行特殊文本模式串的测试。选取模式串60个作为匹配规则。然后依次增加类似模式串直至120条规则分别对主串进行模式匹配，通过计时程序得到如图3．7所示的时间复杂性比较图。’从图中可以看出，BMLT算法性能提高十分明显，大约在50％左右。由此可见，BMLT算法在处理具有重复后缀的模式匹配时运行速度较快，有很大的优势。(秒)60 80 100 120 规则数团BM算法口BMLT算法 图3．7特殊文本情况的时间复杂性比较图问踮∞撕加垢加5O 间们踮∞弱加坫加50浙江工业大学硕士学位论文 BMLT算法时间复杂性测试代码参见附录l、2。2．空间复杂性比较 在进行算法时间性能比较的同时，也记录了两种算法的内存占用情况。根据模式匹配所采用规则数的不同，可得到如图3．8所示的空间复杂性比较图。可以看出，BMLT算法所需的内存空间和BM算法相比变化不大，增减量大约在1％左右。内存68 (KB) 60 80 100 120 规则数囹BM算法口BMLT算法图3-8空间复杂性比较图 以上实验数据表明，相比BM算法而言，虽然BMLT算法在大部分情况下会牺牲一些额外的预处理时间及内存空间，但是在模式重复后缀较多时能够明显地加速匹配过程。总体看来，这些开销是值得的，BMLT算法即使工作在最坏的情况下，也能够带来一定的性能改善。3．2 BM算法基于空问复杂度的改进3．2．1 改进思路的提出 为了确定在失配发生时模式串可移动的最大距离，BM算法使用了两种规则：坏字符规则和好后缀规则。在实际应用中，算法为了获得尽可能大的移动量(显然一次移动距离最大为m)，分别需要在两种规则下进行函数冼，砌1(x)和delta2(j)的预处理计算，用数组储存后再求取较大值，可见BM算法的预处理过程会大大增加算法的内存占用空间，加重2R76543216666666 浙江工业大学硕士学位论文 系统负担。因此，在保证算法效率的前提下，尽可能减少算法的内存使用量，是BM算法基于空间复杂度改进的思路要点。 1980年，Horspool发表了改进与简化BM算法的论文，提出BMH算法【l41。该算法在移动模式时仅仅考虑了坏字符规则，即在算法预处理阶段只使用deltal(x)函数。通过试验研究Horspool证明：在主串r的字符种类较少的情况下，坏字符规则的匹配效率并不高，通过好后缀规则可以加快匹配速度，提高匹配效率。但当主串丁的字符种类较多时(例如r中字符为ASCII码)，坏字符规则的效率明显提高，这时好后缀规则的优越性反而体现得不明显，因此仅采用坏字符规则可以对BM算法产生比较明显的改进【391。BMH算法单纯地采用BM算法的坏字符规则，在运行过程中不考虑主串中具体由哪个字符造成失配，而只使用与模式串末尾对齐的主串字符来计算移动量。这就使得移动量的计算独立于失配情况，算法变得更简洁高效，平均情况下可以提高匹配速率。该算法预处理阶段时间复杂度为O(m+盯)，空间复杂度为Dp)，查找阶段时间复杂度为D(胁，2)。但是由于BMH算法完全舍弃了好后缀规则，这在实际的模式匹配过程中往往会产生一些负面影响。例如在入侵检测环境下，经常出现模式串的一部分后缀与主串匹配，而前缀却不匹配的情况，这时坏字符规则的匹配效率可能会不尽如人意。结合BM和BMH算法各自的特点，可以提出一种改进思路，增加模式串在失配时向后跳跃的幅度，力求在对时间复杂度影响不大的前提下，减小算法的空间复杂度。3．2．2 算法设计思想 根据以上分析，本文提出一种基于空间复杂度的BM改进算法——BM．Less Space(BMLS)算法。BMLS算法简化了预处理过程，只计算比加1(x)函数并存入相应数组。同时为了保证算法的匹配效率，需要记录主串中各个字符的出现频率，当某字符x∈P，且仅出现一次，返回值记为1，否则记为0。以上过程可通过函数A(x1定义如下：m)=器 凳二勰 ㈦·，首先把模式串P和主串丁左对齐，然后从^和死开始自右向左进行比较。若比较结果匹配，就用函数A(x)检查该字符是否在模式串P中只出现过一次，如果是，则用一个变量pos记录下整个匹配过程中第一个彳(兀)=1的指针i的值，然后继续比较下一字符。持续比较直至出现失配，将主串匹配指针修改为m+pos，重新开始行新一轮比较。发生失配时如果pos的值为0，则表明模式串P中该失配字符之后的所有字符全都曾多次出现，那浙江工业大学硕士学位论文么下一轮比较的主串匹配指针应修改为兀+deltal(T，)。假设在某一轮比较在主串丁的乃…乃+，一l子串和模式串P之间进行，此时辟与兀失配，且有兀∈P。当pos≠0时，说明之前～定有字符在模式中只出现过一次，若当前主串指针f-，．+，一1那么必然有pos>，．+_，。根据算法设计思想，此时BMLS算法移动模式串后的主串匹配指针f=m+pos，而用BM算法计算出新的主串匹配指针f7=，．+，一l+m—detta](乃)，显然有f>f’。因此BMLS算法在大多数情况下拥有较高的匹配速度；同时，由于预处理函数的减少，算法占用的内存资源会有所减少。 在以上基于空间复杂度的改进后，BMLS算法流程图如图3-9所示。(，＼ 了F始 ／、)l● pos=O；f-，，t：／=坍：产◇丫足<◇／毒 1|蝴众 丫<≤≥足t i=i+如l凇j U11：i="· (， 退：1I 、) ＼、幻w。0，／ ● J，．‘ ＼ ／ 、／ i=m+pos：譬 pos20；j2ll'l"【 ‘l pos=iI ，斗二_一f 1<～卸t>人是 |乞I1 丫’}J‘陀失败'r划{] ＼ ／ 图3-9 基于空间复杂度的BMLS算法流程图浙江工业大学硕士学位论文3．2．3 算法语法描述class BMLSearch{ static cop_st im MAXCHAR=256；im delta 1[MAXCHAR]；char}part；public： BMLSearch(char木)；int find(char车)；)；BMLSearch：：BMLSearch(char母p){assert(p)；patt=p；int k--O； for(k=0；k return i+l；浙江工业大学硕士学位论文k+=deltal[t【k+1】】；) printfC”Match failed!”)；return O；3．2．4 算法性能分析 为了对改进后的算法进行性能分析，仍然选取2．4．1节中BM算法匹配的例子，采用改进BMLS算法重新匹配如下：假设 尸：EⅪ6山伊LE T：HERE IS A SIMPLE EXAM口LE(1)预处理Z E X A M P L H R I S 口 deltal(x) 6 5 4 3 2 l 7 7 7 7 7 (2)第一次匹配，字符”S”不匹配，字符比较1次，pos=0，deltal(…S．)=7；移动量为deltal(…S．)=7，即模式串右移7位。P、Pm E X A M P l L E H E R E I I I S A l S I M P L E I l E X A l Ml P L En 兄 (3)第二次匹配，字符”P”不匹配，字符比较1次，pos=O，deltal(…P')=2；移动量为deltal(…S’)=2，即模式串右移2位。P、Pm。 E X A M P L E H E R E l S A I S I M P L E E X A M P L ETs 乃 (4)第三次匹配，部分匹配，字符比较5次，其中字符”L”在P中仅出现一次，pos=6；移动量为pos=6，即模式串从不匹配字符”I”开始右移6位。32 浙江工业大学硕士学位论文P、PmE X I A M P I L I E H E R l E l I l S A I S l I M P L E I l E X l A M P L ET10(5)第四次匹配，完全匹配，字符比较7次。E X A M I P L E H E R E I l l S l I A l S I I M P L I E E X A M l P L El★一6 y★此时模式串己到达主串尾，匹配结束。 改进前使用BM算法需进行4次移动15次比较， 另一方面，BMLS算法只需移动3次14 比较起来，匹配和移动次数减少了。 这是因为a(x )函数和pos变量的存在，BMLS 算法在部分一致的情况下，增加了模式列p的后跳幅度。 让我们研究一下BMLS算法的时间和空间复杂性。 )1)在算法中使用后)函数的目的是了解模式列p中是否有a，且是否只出现过一次，实际上 目前，该函数只需要预处理阶段的下沉1G ) )函数中保留中间结果，没有添加额外的计算 该算法的时间复杂度增加o(1)。 )2)算法的重要改进是，pos0被判断为尸体，在模式列中唯一出现时，主列与手指一致 指针直接跳过m个字符。 这将大大减少比较次数。 时间的复杂性最好减少旦o)，最m 不良情况(即pos一直为0时为o ) Mn )。 )3)在预处理阶段，) x )函数不涉及主字符串，因为仅使用预处理函数，例如，通过增加1b 因此，空间复杂度从d (历注视)减少到o )。 其次对BM算法和BMLS算法进行了定量的性能分析，主要同时从运行时间和空间上占用 在使用量两方面比较了两者的性能，测试平台基于Windows 2000 Server系统。 使用Windump 软件在互联网环境下随机重新采集500MB容量的网络数据流，存储在程序目录下的T2.PAt 文档用作模式匹配的主字符串。 由于数据容量较大，以下仅列出部分数据样本。 E:\testwindump.exe—i 3一tT2.PAt windump.exe ' listening on\] deviceh ' qpf { f6ce f77 f-de8e-4 eoa-83cb-e5f 98742 a9 F5 } o:05:32:5f.ee:88(ouiunknown ) 01:00:0c:cc:CD ) ouiunknown ) SNAP Unnumbered， ui:Flags[Command]，length 50 一号煤气 浙江工业大学硕士学位论文 IP 10.216.80.1.67255.255.255.255.68:BOOTP/DHCP、Reply、length 300 802.1 d config 8000.00:E0:0f:9e:8b:ee.8017 root 8000.00:E0:0f:9e:8b:eepathcost 0 age 0 max 20 hello 4 fdelay 15 ppoe [ ses0x 294 e ] ipho sd09-73.dynamic.58.82.r.retail.telecom Italia.it.6344 ww2EFE 2659183 b.445:s 1124037:1124037 (0) win 65535 ARP whohas 10.216.83.118 tell 10.216.80.1 ARP reply 10.216.80.1 is—atoo:OE:84:1f.30:00 (oui unknown ) ) ) ) ) ) ) ) ) ) ) ) )。 其他测试方法采用与3.1.4节相同的方案，为了尽可能减少D、n的尝试误差，各测试 都重复5次，测试结果取平均值。 两种算法的测试结果比较如下。 1 .时间复杂性比较 首先，考虑普通的文本模式列匹配，和3.1.4节一样，使用ASCII码中26个英文字母的大小 由小写字母和阿拉伯数字构成的文字库，随机生成60个长度固定为6字节的字符串 符合规则。 然后，依次增加正文这样的20条到120条规则分别对主列进行模式匹配，并通过 时机程序得到了图3.10所示的时间复杂性比较图。 改进的算法与BM算法性相比 可以明显改善； 并且，规则数增加到一定程度时，BMLS算法的消耗时间的增加会减缓。 在规则增加、失配频繁的情况下，可以看出该算法具有一定的优势。 秒 jZ.62 _ 28.12 25.97… .翳25.26 26.89 24.12 21.3l升 1o、 慢慢来 60 80 100 120规则数 团BM算法nBMLS算法 图3.10普通文本时时间复杂度的比较图 接着重复后缀多的特殊文本模式列进行测试，与3.1.4节同样选择最初的3个字节 随机，最后3个字节将由" t "、" e "、" d "随机排序构成的特殊文本图形串的共计60个作为匹配规则 34 可5 0 5 o 5 0 5 0 听脚尖 情节 加 凹凸不平 加 5 0 浙江工业大学硕士学位论文 不行。 然后，在120个规则分别对主列进行模式匹配之前，依次增加本论文这样的内容，通过定时程序得到 图3.11所示时间复杂度的比较图。 从图中可以看出，BMLT算法的性能有一定的提高，较大 约为78%。 秒 60 80 100 120规则数 囫BM算法口BMLS算法 图3.1特殊文本时时间复杂性的比较图 BMLS算法的时间复杂性测试代码见附录3、4。 2 .空间复杂性比较 然后比较两种算法的内存使用情况。 BMLS算法省略了规则预处理函数的计算， 除了有效地减少中间计算量外，额外定义的函数a(x1及变量pos的计算量有限，占不了太多 存储空间。 总的来看，BMLS算法占用的空间仍然在减少。 从图3.12中可以看出，改进了 算法的平均内存使用情况一般比原算法有明显改善，减少约5%巧%。 通过测试的实验数据表明，BMLS算法在时间上快于BM算法，主要体现在规则数上 的增加对匹配时间的影响很小。 浙江工业大学硕士学位论文内存70 (KB) 60 80 100 120 规则数囹BM算法n BMLS算法图3．12两种算法的空间复杂性比较图3．3本章小结 本章针对BM模式匹配算法在匹配过程中存在的一些不足进行了讨论和改进，从时间复杂度和空间复杂度两个不同角度分别提出了改进思路，给出了改进算法的设计思想，并对其进行了详细地语法描述。使得改进后的算法通过增加失配时的移动量和减少预处理函数，分别降低了算法的时间复杂度和空间复杂度。最后通过实例对每一种改进后的算法进行了定量的性能分析，从时间复杂性和空间复杂性两方面证明了算法的可行性。368642O86 c'O乞‘uCU￡uc．O5 Lru 浙江工业大学硕士学位论文第4章 改进算法测试及结果分析 算法的复杂度是评价算法优劣的重要依据，可分为时间复杂度和空间复杂度。一般说来，好的模式匹配算法应该具有速度快，并且占用内存少的特点。针对常见的BM模式匹配算法，前面本文在理论上分别基于时间复杂度和空间复杂度提出了研究改进。通过定量的性能分析，证明改进后的算法具有一定的实用性。根据本文的研究背景，当把模式匹配算法应用于入侵检测技术中时，究竟哪一种算法的表现更佳呢?本章将在网络入侵检测系统(NIDS)的具体环境中，对此展开实验论证。4．1测试环境为了测试前文中两种改进算法在NIDS中的工作状况，首先需要构建一个测试环境。本次测试的实验环境如表4．1所示，系统硬件环境部署如图4．1所示。表4．1测试实验环境 CPU Pentium(R)4 3．0GHz物理内存 lGBRAM 操作系统 Redhat Linux 9．0 Personal网络负载 1 OOMbit／s数据库 MySQL 5．0N1DS Snort 2．0 在这里，本文选用NIDS的典型代表Snorts 2．0来测试模式匹配算法。作为一个轻量级网络入侵检测系统，Snort具有易于安装、系统尺寸小、便于配置、使用灵活、功能强大、规则库更新快等优点。更为重要的，Snort是开放源代码软件，因此可以非常方便地通过修改其配置文件来满足测试改进算法的要求。浙江工业大学硕士学位论文11)S精涮 Yeb服务器图4-1测试系统部署4．2测试前期准备 Snort提供了三种工作模式：嗅探器、数据包记录器和网络入侵检承4系统。嗅探器模式仅仅是简单地从网络上读取数据包并将其连续显示在终端显示器上；数据包记录嚣模式能够把数据包记录在硬盘上；而网络入侵检测模式是可配置的，能够让Snort分析网络数据内容并匹配事先定义好的一些规则，并根据匹配结果采取一定的操作，相对来说最为复杂。 为了测试多种算法对Snort系统性能的影响，需要在detect c文件的Preprocess(Packet+p)函数中额外增加三个计时变量，以计算系统运行的时间。其中在函数运行前，增加运行前时间变量stan；在函数运行的末尾增加时间变量finish；两者相减即可得出系统运行的时间runtime。为了显示系统运行的时间nmlime，可以在显示运行结果的"061 c文件中输出结果的末尾再添加一条输出语句：prinif(”Rumime：％2 2fseeoads、n"，runtime)。其次，对snon的配置文件snort conf进行网络环境参数配置。在每一次测试之前，都必须用改进后的算法去代替系统原来的Bid算法。具体的方法是测试BMLT算法时，在snort conf配置文件里增加一句：coP,fig detection：searchmethodBMLT；而在测试BMLS算法时，重新设置为：config detection：searchmethodBMLS。如下所示：#Configure the detection engine #Use a different pattern matcher in ca．se you have a machine with very#limited resources：# 毒一暂 已一蓄洲 浙江工业大学硕士学位论文 群con．fig detection：search-method lowmem拌config detection：search—method BMLT撑COl-ffig detection：search·method BMLSBMLT、BMLS算法在Snoa系统中测试代码参见附录5、6。4．3测试过程及结果分析为了便于进行算法性能的比较，首先应使Snon工作于嗅探器模式下，在如图4．1所示的网络环境中进行数据采集，然后对采集的数据分别使用上述两种改进算法进行测试，测试内容包括时间复杂性和空间复杂性两方面。特别地，为了对比算法改进前后的性能优化，测试过程中同时还记录了Snort系统使用默认的BM算法匹配时的性能参数。1．时间复杂性测试为了检测尽可能多的因特网数据，测试中首先对Web服务器进行数据采集，该服务器 域名地址为：www．zjc．zjut．edu．crl，其在内部网络中的IP地址为：172．16．253．16。在Snon规则库中，针对Web内容的检测规则共有274条，分别位于web．attacks．rules、web-cgi．rules、web-client．rules、web-coldfusion．rules、web-frontpage．rules、web-iis．rules、web-misc．rules、web．pap．rules共8个规则文件中f401，以下列出部分规则：(1)alert tcp$EXTERNAL—NET any->$HTTP—SERVERS$mTP—PORTS (msg：HWEB-ATTACKS ps command attempt"；flow：tojerver,established；uricontent：|'／bin／ps”：nocase；sid：132&classtype：web-application—attack rev：4；)(2)alert tcp$EXTERNAL—NET any->$HTTP—SERVERS$矗吼P?ORTS (msg：“WEB-ATTACKS ／bin／ps command attempt"； flow：tojerver,established；uricontent：‘'ps％20”：nocase；Sid：j 329：classtype：web—application-attack rev：4；)《3)alert tcp $EXTERNAL NET any．> $HI-ljP SERVERS $H，rTP PORTS(msg：“WEB-ATTA CKS wget command attempt“； flow：tojerver,established；content：t'wget％20t'；nocase；sid：l 330：classtype：web—application—attack；rev：4；)t4、alert tcp SEXlERNAL奠ET any ->$HTTP—SERVERS $强1TP jORTS(msg：”WEB-ATTACKS uname —a command attempt“： flow：tojerver,established；content：t'uname％20一at'；nocase；sid：】33 1：classtype：web—application—attack；rev：4；)《5)alert tcp$EXTERNAL NET any ．> sHTlP SERVERS$HTTP PORTS(msg：“WEB-AT砑C憋 ／usr／bin／id command attempt“： flow：to_server,established；content：’'／usr／birdid3','nocase；std：i 332：classtype：web—application—attack；rev：4；)《6)alert tcp$EXTERNAL』ET any·> SHnPjERVERS SHTTP?ORTS39 浙江工业大学硕士学位论文 (msg：”WEB-ATTACKS id command attempt”：flow：tojerver,established；content：“＼：idl'；nocase；sid：1333；classtype：web·-application··attack；rev：4；)本次采集的数据包共1000个，其数据类型统计如表4．2所示。表4-2采集的数据包类型统计表 数据包类型 数量 比例TCP 939 93．9％UDP 7 O．7％ICMP 18 1．8％ARP 5 0．5％other 31 3．1％ 在4．2中设置的变量runtime负责提供对程序的时间统计功能。测试过程中首先采用其中的50条Web内容检测规则，分别使用三种算法进行检测，记录每种算法完成规则模式匹配需要的时间。接着将检测规则每次递增50条直至274条，依次记录。为了更客观真实地获取实验数据，按相同的方法对每一个算法重复测试5次，并将测试结果取平均值。最终得到的算法时间复杂性比较如图4．2所示。(秒) 14．67 -一 ／： 12-45·乞多Z ： Q 9R：：毵59…。。 一力缀 √ 一 黾。≮黾．◆◆·哆哆刍9 o，oh．，，‘毯．、＆ 潲／^。弧 ／ um匾哌r／k强 ．2·26 ． ． ．+BM算法+BMLT算法+BNLS算法图4．2三种算法的时问复杂性比较图(数据包固定，规则递增)规则数侗埔M 屹加8642o日 浙江工业大学硕士学位论文 从图4．2可以看出，随着有关内容检测规则的增多，需要检测的内容增加，三种算法的检测时间基本都呈线性增长，因为它们都需要逐个规则匹配。相比BM算法而言，BMLT和BMLS算法在运行速度上均有所改善，算法的时间复杂度最多减少了60％。具体地，在规则数较少的阶段，BMLT算法的时间复杂性相比较来说优势更明显。究其原因，Wreb服务器上的数据流以H1]曙报文为主体(这一点只需观察表4．2中TCP数据包比例达到93．9％便可以证明)；而Snort中的Web内容检测规则中有很大一部分的串尾字符是相同的。而BMLT算法擅长的恰恰是重复后缀比较，而且规则数越少，它的优势就越明显。但是随着规则数的增加，失配的情况逐渐频繁起来，这时BMLS算法受规则数增加的影响较小，规则匹配时间相对增长较慢，算法性能相比来说也有优化的趋势。在前面测试的基础上，为了进一步考查算法的持续性和自适应性，需要测试文本数量的增加对算法性能的影响。在这里测试系统维持规则数274条不变，继续对Web服务器进行数据采集。采集的数据包逐步增加到2000和3000个，分别使用三种算法进行检测，记录每种算法完成规则模式匹配需要的时间。每一个算法重复测试5次，测试结果取平均值，算法的时间复杂性比较如图4．3所示。时间(秒)44．58： ： 36·12／乞f■ ／ 一■■，一—_■-’一6V”J_■’l t≥ ： 22．83乞形 ·一一‘… ：，．。，——!!：／。‘。。：：_／——25．49一…‘ 荔多／m!：幺6 ■．61-彳■ “一。rr8．74 ■ ● ■ ● 1000 1500 2000 2500 3000--m'-BM算法+BMLT算法+BMLS算法图4．3三种算法的时间复杂性比较图(规则固定，数据包递增)数据包观察图4—3，随着所采集数据包数目的增加，需要检测的内容大大增加，三种算法的检测时间依然是线性增长的。对BM算法来说，BMLT和BMLS算法在运行速度上均有进41∞ 钙们 }8∞筋加坫加5O 浙江工业大学硕士学位论文 一步改善，效果更为明显，可见改进算法的持续性符合入侵检测的要求。就两种改进算法而言，BMLS算法有进一步优化的趋势，因为其相比BMLT算法使用了更少的预处理函数计算过程；而数据包越多，出现坏字符的比例会有所增加。随着数据量的增加(尤其是海量数据的情况)，两种算法之间的性能差距会趋于稳定，但相比之下，仍然是BMLT算法性能更佳。2．空间复杂性测试 接下来分析比较改进算法对系统内存的占用情况。重新取出最先采集的1000个数据包，测试系统还是首先采用Snort规则库中前100条Web内容模式规则，分别使用三种算法进行匹配检测；然后逐步递增50条规则直至274条。每种算法重复测试5次，对测试结果取平均值，得到算法的空间复杂性比较如图4-4所示。内存(船) 100 150 200 274 规则数口BM算法口BMLT算法口BMLS算法图44三种算法的空间复杂性比较图(数据包固定，规则递增) 从图4．4中可以看出，因为三种算法都是逐个规则进行匹配的，它们对内存的要求并没有随着规则库的增加而快速增长。BMLT算法相对BM算法的改进是基于时间复杂度完成的，算法增加了预处理函数，这在一定程度上加重了系统负担，因此其空间复杂性与BM算法相比基本没有改善。BMLS算法在预处理过程中定义的函数和变量相对较少，算法的空间复杂度最多减少了26％，因此从空间占用角度考虑，该算法的性能更佳。综合以上对两种算法的测试分析，可以得出以下结论：∞踮加∞的们∞加加0 浙江工业大学硕士学位论文 (1)本次研究的两种改进算法，不管是在匹配速度还是空间占用的角度上，相比改进前的BM算法均有明显的提高。 本章利用Snort软件和实际的网络环境，对上一章提出的两种改进的模式匹配算法进行了测试分析。测试分为时间复杂性和空间复杂性两方面进行。相比改进前，算法的时间复杂度最多减少了60％，空间复杂度最多减少了26％。实验结果表明：两种算法均比BM算法拥有更好的算法性能，其中BMLT算法适合模式规则数较少、数据量较小的情况：而BMLS算法适合模式规则数较多、对系统内存占用较为苛刻的情况。因此针对不同的数据流和模式库，应灵活地选用不同的算法来进行模式匹配。43 浙江工业大学硕士学位论文第5章结论与展望5．1结论 作为一种积极主动的安全防护技术，入侵检测是确保网络安全运行的重要手段。基于模式匹配技术的入侵检测系统是目前较为先进的检测产品，它利用已知的入侵模式和高效的模式匹配算法，能够快速地探测网络上的不安全因素。 本文主要对入侵检测中的模式匹配算法进行了研究。从介绍入侵检测技术入手，较全面地分析了入侵检测技术的历史、现状和发展趋势，系统地说明了模式匹配的原理，了解了模式匹配技术，对常见模式匹配算法的实现思想和性能进行了详细的阐述和分析。重点对BM算法中存在不足之处进行分析，从两个不同的角度提出了改进算法。最后在实际网络环境中利用Snort系统对改进算法进行了测试分析。本论文所完成的研究开发工作主要包括： (1)研究了入侵检测技术和模式匹配技术，尤其是网络入侵检测系统的一般架构，介绍了模式匹配的原理，讨论了目前模式匹配算法面临的主要问题和未来的发展趋势。(2)深入研究了入侵检测系统中常用的模式匹配算法，详细介绍了BM算法的基本思路与匹配过程，同时也提出了算法在匹配过程中的优点和不足之处。(3)在BM算法原有思想基础上，从时间复杂度和空间复杂度两个角度分别提出了两种改进算法：BMLT算法和BMLS算法，力求使改进后的算法具有一定的可行性与高效性，并分别举例论证。(4)利用Snort系统和实际网络环境，从时间复杂性和空间复杂性两方面对提出的两种改进的BM算法进行了测试分析，实验结果表明两种改进算法的时间复杂度最多减少了60％，空间复杂度最多减少了26％，相比改进前的BM算法均有明显的提高。同时分析了两种算法各自适用的情况，说明针对不同的数据流和模式库，应灵活地选用不同的算法来进行模式匹配。5．2展望 设计和实现一个准确、高效的模式匹配算法是网络入侵检测系统中最关键的环节，本44浙江工业大学硕士学位论文 文只是基于最常见的BM算法进行了分析、研究、改进和验证，还有很多技术细节没考虑周全，这需要在今后的工作中逐步实现和完善。后续的研究工作主要包括以下方面：(1)进一步研究模式匹配算法，目前有两个考虑的方向：一是针对规则模式的结构特点，采用文本两端和中央同步匹配的方案；二是基于字符出现在文本中的概率特征的匹配算法研究。争取通过后续研究把两者应用于具体的入侵检测环境。(2)从单模式到多模式的算法变迁是模式匹配技术发展的新技术方向【4l】，通过深入研究更先进的多模式算法，进一步加快特征匹配速度，提高匹配精度。(3)继续分析多样化的入侵手段，在检测模块中结合其他智能化的检测方法，如神经网络、遗传算法、粗糙集理论1421等。 总之，基于模式匹配技术的入侵检测系统是目前较为先进的入侵检测产品。通过对模式匹配算法的研究和改进，能大大改善入侵检测的效率和系统资源占用情况。随着网络数据流的急剧膨胀和入侵特征规则的不断增加，今后模式匹配算法研究的主要方向是设法提高算法的平均效率和减少内存资源耗费。在实际的网络应用中主要可以采用减少匹配次数、在多设备中并行完成模式匹配算法等途径，以减少模式匹配所消耗的时间和空间资源。浙江工业大学硕士学位论文[2][3][4][5][6][7][8][9] [10][i1][12][13][14][153参考文献 Yuebin Bai，HideBune Kobayashi．Intrusion Detection Systems：Technology and Development[A]．Proceedings of the 1 7m International Conference on Advanced Information Networking andApplications[C]．Oakland：IEEE Computer Press，2003．Zhuowei Li，Amitabha Das，Jianying Zhou．Theoretical Basis for Intrusion Detection[A]．Proceedingsof the 2005 IEEE Workshop Oil Information Assurance and Security[C]．WestPoint：United StatesMilitary Academy,2005．卿斯汉，蒋建春，马恒太等．入侵检测技术研究综述【J】．通信学报，2004，25(7)：1 9—27．张然，钱德沛，张文杰等．入侵检测技术研究综述【J】．小型微型计算机系统，2003，24(7)：1113．1118． 柴平宣，程时瑞．入侵检测技术分析叨．计算机工程与应用，2003，28(14)：164—166． Robert S，Boyer J，Strother M．A fast string searching algoritrma[J]．Communications ofthe ACM，1977，20(1 O)：762—772．唐正军，李建华．入侵检测技术[M】．北京：清华大学出版社，2004． 王永全．入侵检测系统(mS)的研究现状和展望们．通信技术，2008，41(1 1)：139—143．郑军．入侵检测与网络安全【J】．通信工程，2007，1：1-4．韩东海，王超，李群．入侵检测系统及实例剖析【l咽．北京：清华大学出版社，2002． KumarGClassification and detection of computer intmsion[D】．Purdue University,1 995．佟治，刘娜，郑楠楠．模式匹配算法的深入研究【J】．上海师范大学学报：自然科学版，2008，37(6)：581．586． 张丽霞，陈莉．一种改进的模式匹配算法[J】．微计算机信息，2008，24(30)：68-70． Horspool N．Practical fast searching in strings[J]．Software-Practice and Experience，1980，10(6)：501—506．Sundey D M．A very fast substring search algorithm[J]．Communications ofthe ACM，1990，33(8)：132．142． Antonatos S，Anagnostakis K，Markatos E，Polychronakis M．Performance Analysis of ContentMatching Intrusion Detection Systems[A]．Proceedings ofthe 4恤IEEE／IPSJ Symposium OilApplications and the Internet[C]．Oakland：IEEE Computer Press，2004．Coit C J，Staniford S，McAlerney J，Towards faster pastern matching for inmasion detection orexceeding the speed of snort[C]．DARPA Information Survivability Conference and Exposition，2001．宋华，戴一奇．入侵检测中一种新的快速字符串匹配算法fJ】．计算机工程与应用，2003，39(32)：48．51． 王永成，沈洲，许一震．改进的多模式匹配算法【J]．计算机研究与发展，2002，39(1)：55．60．田俊峰，黄建才，杜瑞忠，翟建强．高效的模式匹配算法研究【J】．通信学报，2004，25(1)：61-69．李昀．李伟华．面向入侵检测的模式匹配算法研究【J]．计算机工程与应用，2003，39(6)：1—3．46印力踟 朝∞¨nn |= 口眩眩 浙江工业大学硕士学位论文 殷丽华，张东艳，方滨兴．面向入侵检测的单模式匹配算法性能分析【J]．计算机工程与应用，2004，40(24)：1—3． 于泠，陈波．IDS中模式匹配算法及其并行化设计【J】．计算机工程，2004，30(4)：46-48．蒋盛益，李庆华．有指导的入侵检测方法研究【J】．通信学报，2006，27(3)：86-93．王成，刘金刚．一种改进的字符匹配算法【j】．计算机工程，2006，32(2)：62-64．俞研，黄皓．一种半聚类的异常入侵检测算法【J】．计算机应用，2006，26(7)：1640—1643．翟书颖．基于人工免疫算法的入侵检测系统研究【D】．中国优秀硕士学位论文全文数据库．2006(2)：9—1 0．Network Flight Recorder．NFR[CP]．http／／：www．nfr．com，2005．朱雁辉．W'mdows防火墙与网络封包截获技术【M】．北京：电子工业出版社，2002．陈思．入侵特征与入侵检测所需规则【J】．2008，12：39-40． Jain R．Congestion Control and Traffic Management in ATMNet-Work：Recent Advanced and aSurvey[J]．Computer Networks and ISDN Systems，1 996，28(3)：1 723·1 738．徐孝凯，贺桂英．数据结构(c语言描述)【M】．北京：清华大学出版社，2004．Knuth D，Morris J，Pratt VFast pattem matching in stringsp]．SIAM Journal on Computing，1 977，6(2)：323-350． Karp M，Rabin O．Efficient randomized pattern—matching algorithms[J]．mM J．RES．DEVELOP,1987，3 1(2)：249—260．周延森，汪永好．网络入侵检测系统模式匹配算法研究【J】．计算机工程与设计，2008，29(7)：1652-1654． 申晋祥，杨秋翔．模式匹配算法的研究与改进【J】．电脑开发与应用，2007，20∽：9-10． AHO A．Algorithms for finding patterns in snings[A]．Handbook ofTheoretical Computer Science(Volume A)：Algorithms and complexity[C]．Cambridge，MA：MIT Press，1991．扬宏宇．网络入侵检测技术的研究【D】．天津：天津大学，2003．杨小平，苏静．基于协议分析的入侵检测技术研翘J】．计算机应用研究，2004，2(3)：108—110．李晓芳，姚远．入侵检测工具Snort的研究与使用【J】．计算机应用与软件，2006(2)：123-141．刘磊．多模式匹配算法的研究与优化【J】．潍坊学院学报，2008(2)：35．38．杨淑棉，王学军，刘剑．粗糙集理论在模式匹配算法中的应用【J】．信息技术与信息化，2008(4)：71．73．47幻 朝钔明印刀胡钔∞订幻卵铂印 田刀 胡踟啪Ⅲ嘲眨 眩阻眩眩眩眩心口口口口口 l竺I口∞嘧口心阻心 浙江工业大学硕士学位论文附 录 附录1 BMLT算法时问复杂性测试代码(普通文本模式串)#include #include static char p[PI+I]={NULL}；char*NorP0／／模式串生成模块{int flag，charLengt；int ij，k=O； srand((unsigned)time(NULL))； for(i=0；i<60；i++)／／这里生成60个模式串，可增加至120个{for(j=O；j if(flag)“k++]=¨¨A+rand0％26；else p[k抖】．“a+rand0％26；)“k卜’＼0’；48 浙江工业大学硕士学位论文k=0；) return p；) int*MakeDeltal 0／／根据坏字符规则做预处理，建立一张坏字符表{inti； static int木deltal 2(int})malloc(256木sizeof(int))；if(deltal===NULL){ fprintf(stderr,”malloc failed!”)；return 0；) for(i=0；i<256；i抖){宰(deltal+i)--m；} while(m!=0)／／给表中需要赋值的单元赋值{ ·(deltal+(unsigned char)木p斗斗)2 m一；)return deltal；} int木MakeDelta20／／根据好后缀规则做预处理，建立一张好后缀表{ static int宰delta2=(int*)malloc(m木sizeof(int))；／／为好后缀表申请m个整型空间int幸sptr=delta2+m-l：char}pptr=P+m·1；charc； if(delta2一NULL){ fpfintf(stderr,”malloc failed!” % 29 % ef % BC % 9b %0are tum % 20o % ef % BC % 9b % 0a % ef % BC % 89 % 0a 49 % 0a % E6 % b5 % 99 % E6 % B1 % 9f % E5 % B7 % ab7 % AC 6 % E6 % 96 % 87 % 0ae % 3d % E6 % 8e % 8c % ef % BC % 88p % 20111 % C2 % b71 % ef % BC % 891 % ef % BC % 9b % 0a % E6 % 9c % be % 8c % E3 % 81 % 8b % E3 % 82 % 892 % E7 % 95 % aa % E7 % 9b % AE % E3 % 81 % AE % E6 % 96 % 87 % E5 % ad % 97 % E3 % 81 % lt a2 % ef % BC % 89 % 2f % E3 % 81 % 93 % E3 % 81 % AE % E6 % 9c % 80 % E5 % a4 % 96 % E5 % B1 % a4 % E3 % 83 % ab % E3 % 83 % E3 % 83 % AE % E3 % 83 % 83 % E3 % 82 % af % E3 % 82 % B9 % E8 % a1 % A8 % E3 % 81 % AE % E5 % 90 % 84 % E3 % 83 % a6 % E3 % 83 % 8b % E3 % a1 % E3 % 8b % E3 % 83 % a1 % a3 % a3 % E3 a6 % E3 % 82 % 8b % E4 % BD % 9c % E6 % a5 % ad % E3 % 82 % 92 % E5 % AE % 8c % E4 % ba % 86 % E3 % 81 % 99 % E3 % 82 % 8b % 000 P3 % ef % BC % 9b % 0a do % 2f % 2f % E3 % 81 % 93 % E3 % 81 % aedo % E2 % 80 % a6 while % E3 % 83 % ab % E3 % 83 % BC % E3 % 83 % 83 1 % AEP ptr % E3 % 81 % 8c % E6 % 8c % 87 % E3 % 81 % 99 % E6 % 96 % 87 % E5 % ad % 97 % E3 % 82 % 92 % E5 % a2 % 83 % E7 % 95 5 % E3 % 81 % 99 % E3 % 82 % 8b % E8 % B7 % 9d % e9 % 9b % a2 % 0a % 7b % 20 % 0a while % ef % BC % 88 P1 % 3dp % E5 % B9 % b8pl 3 % 3d pl % ef % BC % 9b % 0a wile % ef % BC % 88p3% 3dp % ef % BC % 89p3% ef % BC % 88 % E6 % 8e % 8c % E4 % b8 % 80 % E6 % 96 % 80 % E6 % 99 P3 _ pp2 % 3d pptr % ef % BC % 89 % ef % BC % 9b % 0a % E5 % B9 % b8 sptr % 3d delta2% 20m-sptr % 20p2- P3 % ef % BC % 9b % 8d % E7 % B6 % 9a % E3 % 81 % 8d % E5 % 89 % 8d % E6 % 96 % B9 % E3 % 81 % ab % E7 % a7 % bb % E5 % 8b % 95 % E3 % 81 % 99 % e9 % ab 1 % E3 % 82 % BF % E3 % 83 % BC % E3 % 83 % B3 % E3 % 83 % 9e % E3 % 83 % 81 % E3 % 83 % B3 % E3 % 82 % B0 % E3 % B0 % E3 BC % 8c % E4 % bb % 81---o % ef % BC % 9b % 20 static % 20m % 3d P1 % ef % BC % 9b % 0a static % 20 shift % 3d m % ef % BC % aj-- m % ef % BC % 9b % 0a while % ef % BC % 88 jop1% ef % BC % 88j % ef % BC % 89 % E3 % 82 % 92 % E5 % B7 % 9e % E3 % 81 % 89 % ef % BC % 89 % ef % BC % 89 % ef % BC % 89 % ef % BC % 89 % E3 % 80 % 82 % 0a % 7b % 20 % 0a if % ef % BC % % 9b % 0a else % 0aj % E3 % 80 % 81l % ef % BC % 9b % 0a % ef % BC % 89 % 0a if % ef % BC % 88j % 3d0% ef % BC % 89 % ef % BC % % ad % a6 % E4 % BF % AE % E5 % a3 % ab % E5 % ad % a6 % E4 % BD % 8d % E8 % ab % 96 % E6 % 96 % 87 % 0a % 7b % 20 %0apr intr 7 % E3 % 83 % ab % E3 % 82 % bf2 % ef % BC % 88o % ef % BC % 9b % 0ae % 3a---m-shift % ef % BC % 9b % 0a % ef % BC % 880 % ef % ba % b5 % ef % ba % b5 % ef % ba % b5 % ef % ba % b5 % E3 % 80 % 82 % 0a shift % 3d max % ef % BC % 88 deltal % ef % BC % % 89 % ef % BC % 9b % 0a if % ef % BC % 88 shift % 3d-deltal % ef % BC % 88j % ef % BC % 89 % ef % BC % 89 % 89 % ef % BC % 89 % ef ef % BC % 89 % ef % BC % 89 % ef % BC % 89 % ef % BC % 89 % E3 % 80 % 82 % 0ae-- min % ef % BC % 88m-shift ef % BC % 88 % E2 % 80 %9dmatchfailed % ef % BC % 81 % 20 % E3 % 80 % 8d % ef % BC % 9b % 0a return % 200 % ef % BC % 9b % 0a c % 89 % 2f % 2f-% E6 % 9c % 80 % E5 % a4 % a7 % E5 % 80 % a4 % E3 % 82 % 92 % E6 % B1 % 82 % E3 % 82 % 81 % E3 % 82 % 8b a else % 20q % 3dx % ef % BC % 9b % 0a return % 20q % ef % BC % 9b % 0a % ef % BC % 89 % 0a int % 20 maino % 2f % E3 % 82 % BC % 82 % b8 % E3 % 83 % a5 % E3 % 83 % BC % E3 % 83 % ab % 0a % 7b % 20 % 0a dword % 20 start-% 3d timegettime0% ef % BC % 9b % 2 % BF % E3 % 83 % BC % E3 % 83 % 88 % E3 % 81 % 95 % E3 % 81 % 9b % E3 % 82 % 0a file %7DFP % ef % BC % 9b % 20 % 2f % 20 % E3 % 82 % 8b % 0a if % ef % BC % 88 % ef % BC % 89fp % 3d fopen % ef % BC % 89 % E3 % 80 % 8ct1. % e9 % a3 % b2t . % ef % BC fn % E2 % 85 % B1 % ef % BC % 8cl % ef % BC % 89 % 29 % 0a % 7b % 20 % 0a printf % ef % BC % 88 % E2 % 80 %9dfileopenfailed % 89 % 0a static % 20 char % 20t % 5b % E3 % 80 % 912 fgets % ef % BC % 88fp % ef % BC % 89 % ef % BC % 9b % 0af lose % ef % BC % 8880 o % ef % BC % 9b %0abm lt0% ef % BC % 9b % 0a dword % 20 end % 3d timegettime0% ef % BC % 9b % 20 % 2f % 2f % E8 % A8 % 88 % E6 al % 3d end.start % ef % BC % 9b % 20 % 2f % 2f % E8 % A8 % 88 % E7 % AE % 97 % E6 % 99 % 82 % e9 % 96 % 93 % 0a % E3 % 83 % 83 % % 93 % E3 % 82 % 92 % E8 % A8 % 98 % e9 % 8c % B2 % E3 % 81 % 99 % E3 % 82 % 8b % E3 % 80 % 82 % 0a if % ef % BC % 88 % ef % BC void BMLT ()//模式匹配模块 { int ij，e，f=O； 静态m=p2； 静态shift=m； for(I=0； I； I=13(1m ) { ) ) 浙江工业大学硕士学位论文 J2m； while(jop2(JL----t ) Ij ) ) ) ) )。 { if(e！=Oj==m-shift ) j=j—e； else j-j-1； ） if(j=o ) ) ) { pnntf(%d )、i 1 )； shift=三角洲2(o； 铀-shift； } else { f-=m-j； shift=e shift--max(deltal(t[Ij]-mj，delta2(j ) j，shift )； if(shift=deltal(j ) ) e--min(m—shift，f )； else { if(Shifiy ) q=y； else q=x； 返回q； } int main ()//时间主控模块 { DWORD start=timeGetTimeO； //启动计时器 文件树fp； //读取文本 if () FP=fopen (“t1.txt '，' w ' ) )—-NULL ) ) { printf(”fileopenfailed！ ha”； exit(o； ） 静态字符【】。 FETS(FP )； flose(FP )； staticn=strlen(p； 57 浙江工业大学硕士学位论文 SpecP0； BMLTO； DWORD end--timeGetTimeO； //结束计时 DWORD Total=end.start； l/计算时间 木邱； //记录时间 if () ) FP=fopen (" bmlttimel 092 .戟t "，" w " ) (—_NULL ) ) { primf(”fileopenfailed！ (ia ) )； 退出(0； ） futs(itoa )总的，货币； fputs (。 、邱1； flose(FP )； 返回0； ） 附录3 BMLS算法时间复杂性测试代码(普通文本模式串) )。 #包含 #包含 #包含 #包含 #包含 #包含 #包含 #包含 #包含 #包含 #pragmacomment(1IB，' winmm.1ib ) ) #definePl 6 静态m=P1； 静态char p [ pl1 ]5{ null； 58 浙江工业大学硕士学位论文 类bml search { 静态常数im max char-256； 输入删除【最大字符】； char树patt； 公共： bml搜索(字符率)； intfind(char树)； )； char幸NorP0//模式列生成模块 { int flag，charLengt； int ij，k_0； srand () unsigned (time ) ) null )； for(I_0)； i60； ih//这里可以生成60个模式列，增加到120个 { for(J20； jn ) { int k=m一1； while(k=0t[I]-pat-to ) ) A一； I一； ） if(j----1 ) )。 return i l； k=deltal【t[1【 1】】； ） ） int main ()//时间主控模块 { DWORD start=timeGetTimeO； //启动计时器 文件树fp； //读取文本 if () F1 ):fopen (“T2.txt '，' w ' ) ) .—.NULL ) ) { printf(”fileopenfailed！ kn”； exit(o； ） 静态字符端口=fgets(FP )； flose(FP )； staticn=strlen(p； NorPO； BMLsearchbmls(char树p，char树t，m，n )； DWORD end=timeGetTime (； //结束计时 浙江工业大学硕士学位论文 DWORD Total=end—start； //计算时间 记录文件* FP//时间 if () FP=fopen (“bmlstimel 091.txt '，' w ' )—INULL ) ) { printf(”fileopenfailed！ \n "； 退出(0； ） futs(itoa(total )、邱)； futs(w，邱)； flose(FP )； 返回0； 附录4 BMLS算法时间复杂性测试代码(特殊文本模式串) )。 #包含 #包含 #包含 #包含 #包含 #包含 #include1ist #包含 混合墨水 #包含 #pragmacomment(1IB，' winm_rn.1ib ) ) #define P2 6 静态m=p2； static char p[P2 1]2{NULL}； 类bml search { 状态const int max char=256 : 61 浙江工业大学硕士学位论文 int deltal[MAXCHAR]； char树patt； 公共： BMLsearch(char树)； hatfind(char )； )； char枣SpePO//模式列生成模块 { hat flag，charLengt； imij嫉妒o； srand () unsigned (time ) ) null )； for(I=0； i60； I//这里可以生成60个模式列，增加到120个 { for(j=0jqjh ) )。 { flag=randO%2； if(Flag ) p州=ta’rand0&； else p[1() -’a ' rando &； char p【】base={，’，’e’，’d’； int tmp=randO%2； P[k抖]=base[trap]； ） (() ) )； k=0； ） 返回p； ） BMLsearch:BMLsearch(char幸p ) )。 { assert(p； patt=p； int k=0: for(k=0； kn ) { int k--m一1； wile(1(1(1)=ot【I】. patt[j] ) ) ) ) ) ) ) wile(1)=ot【I】. patt[j] ) ) ) ) ) wile ) ) ) ) ) wile ) ) Wii ) ) wi ) ) Ji ) Ji ) Ji ) Ji ) Ji ) Ji ) Ji ) Ji ) Ji。 {j一； I一； ） if(j(1) ) ) ) )。 返回I 1； k=deltal[t【k 1】； } ） int mainOH时间主控模块 { DWORD start=timeGetTime0； //启动计时器 文件树fp； //读取文本 if () ) FP=fopen (“T2.txt '，' w ' ) )—-NULL ) ) { PFIMF(”fileopenfailed！ ha”； 退出(0； ） 静态char t端口2fgets(FP； flose(FP )； staticn=strlen(p； SpecP0； BMLsearchbmls(char车p、char树t、m？ n； DWORD end=timeGetTime0； //结束计时 63 浙江工业大学硕士学位论文 DWORD Total=end.start； //计算时间 木邱； //记录时间 if () fly-- fopen (“bmlstimel 092.t”) t，“w”)—-NULL ) ) { PRMTF(”fileopenfailed！ kn”； 退出(0； futs(itoa(total )、邱)； futs(t(n )，邱)； flose(FP )； 返回0； 附录5用5 BMLT算法Snort系统测试代码 组ltdef HAVE—CONFIG—H # include’con _ fig.h’’ #endif #包含 #include”mstring.h " #include”debug.h " # include " plug base.h’’ #include”util.h " 以fdef GIDS为标题 extern int detect_depth； #endif/*GIDS树/ extern const u—int8一t树doe_ptr； #ifdefTEST，—MSTRING int main () ) { char test [ ]=”\ o\o\o\o\o\o\o\o\o\o\ockaaaaaaaaaaaaaaaaaa AAAAA\0\0 " 64 浙江工业大学硕士学位论文 char find [ ]=" ckaaaaaaaaaaaa\0\0 " int i； int toks； 静态输入奉shift； 静态宰戴尔； 静态树三角洲2； Debug_Wrap(Debugmessage ) Debug_Pattern_match，' %dkn '， research(test，sizeof(test )一1，find，sizeof (FMD )-1，deltal，delta2)； )； 返回0； ） #endif int幸makedeltal(char宰ptm，int pLen )//根据坏文字的规则进行预处理，制作坏文字表 { int i； int幸deltal=(int幸) malloc ) 256 ) sizeof ) int )1) )为了创建坏的字符表，申请256个整数空间 if(deltal===null ) () ) ) ) ) ) ) ) )。 { fprintf(stderr，“malloc failed！ ”； 返回o； //初始化不良字符表，将256个单元全部初始化为pLen for(I=0； i256； I ) { 宰(deltal i )=pLen； ） //为表中需要赋值的单元赋值 wile (计划！=0) { 宰(deltal(unsignedchar )木ptm )=pLen一； ） 返回删除； } int奉makeDelta2(char宰ptrn，int pLen )//按照好的后缀规则进行预处理，制作好的后缀表 { //为了好的后缀表申请pLen个整数空间 int蝽象delta2=fint树(malloc(plen树sizeof ) int )； int树sptr=delta2 pLen-1 : 65 浙江工业大学硕士学位论文 char幸pptr=ptm pLen一1； 字符； iffdelta2一空) { fprintf(stderr，' malloc failed！ ”； 返回0； } c=木(p仄n pLen-1 )； 牵引sptr=1； ptr----边界移动到倒数第二个字符 sptr -一！=delta2(//该最外层循环完成向好的后缀表的各单元分配值的作业 { char树pl 2ptm pLen-2，幸p2，*p3； (此do…while循环完成，以当前pptr所指字符为边界时移动的距离 d0 { wile(PL2PTM幸pl一！=c； p2=ptrn pLen； p3=pl； while(P3=PTM树P3 (一对一为p2~p2=pptr ) )； ） while(p32ptMP2=PP曲； 幸sptr=delta2 pLen-sptr p2p3； pptr-一边界继续向前移动 ） 返回深度2； ） 根据int宰makeshift(char半bur，char ) ptrn，int pLen，im blen )//函数shift计算移动量 { int i，j，e，仁0； shifl=pLen； for(I=o； I； i=blen—pLen ) { j2pLen； 浙江工业大学硕士学位论文 while(joptrn[j]=buf[Ij] ) )。 { if(e！=Oj—节len shift ) j.j； else j=j-1； if(j=0) )。 { shift----Delta2(0； e=pLen-shift； ） else { f=pLen-j； shift=e -。 shift=max(deltal(buf[Ij]plenj，delta2(j ) j，shift )； if(shift=deltal(j ) ) e=min(plen-shift，f )； else { if(shifty ) q=y； else q5x； returrl q； 附录6用6 BNILS算法Snort系统测试代码 #ifdef HAVE——CONFIG——H #include”config.h " #endif #包含 #include”mstring.h " #include”debug.h " #include”plugbase.h " #include”util.h " 以fdef GIDS为标题 类bml search { 静态常数int max char=256； 输入删除【最大字符】； 蜜枣patt； 公共： BMLsearch(char*，pLen )； intfind(char*， )； extem int detect._depth； #endif/*GIDS树/ extem const u_int8_t幸doe ptr； #ifdefTEST-MSTRING int main0 { chartest [ ]2"\o\o\o\0\o\o\0\0\0 ckaaaaaaaaaaaaaa AAAAA\0\o” char find [ ]=" ckaaaaaaaaaaaa\0\0 " 浙江工业大学硕士学位论文 hat i； int toks； 幸deltal； int shift； debug _ wrap (debug message (debug—pattern _ match，' %dha )， research(test，sizeof(test ) l，find，sizeof ) find )一1，deltal，s11iR )； )； retDa-Tl 0； ） #endif int幸makedeltal(char树ptm，int pLen )//根据坏文字的规则进行预处理，制作坏文字的表 { int i； i11t树deltal=(int树) malloc ) 256论sizeof ) int )； //为了制作不良的文字表，申请256的整数空间 if (删除—空) ) { fprintf(stderr，“malloc failed！ 返回o； ） (初始化坏的字符表，将256个单元全部初始化为pLen for(I=0； i256； I ) { 树(deltal i )=pLen； ） 为表中需要赋值的单元赋值 wile (计划！=0) { 宰(deltal(unsignedchar )木Ptm )=pLen--； ） 返回删除； ） BMLsearch:BMLsearch(char木bur，char宰ptm，int pLen，char宰p ) )。 { assert(p； patt2ptm； int k=O : for(k=0； kblen ) { int k=pLen一1； while (k=obu tii (patt ) j ) ) )。 {j一； I一； } if(j----1 ) )。 return i l； k=deltal[buf例1 ]； ） 返回- 1； ） BMLsearchbmls(char即ptm，char树bur，血blen，int pLen )//模式匹配 { intb_id(【=plen； 计划一0 )。 返回1； while(b_idx----_blen ) /计算字符串是否与主字符串的末尾匹配 { b—idx -k； ） 结果0； ） 71 浙江工业大学硕士学位论文 谢谢 在我毕业之际，首先要感谢我的导师陈庆章教授。 本论文的研究和写作从一开始就开始了 直到最后都是在陈教授的悉心指导下完成的。 陈教授~规规矩矩、严谨求实的治学态度令人诚惶诚恐 敬业、敬业的精神，使我的理论水平和科研能力有了很大的进步。 特此敬陈小姐 教授，非常感谢。 此外，我的论文还得到了包括俞立教授、孟在内的信息工程学院所有其他老师的无私指导 利民教授、古辉教授、南余荣教授、钱能教授、黄德才教授、陈胜勇教授、杨良怀副教授、 贾新副教授、梁荣华副教授、叶蕾博士、龚卫华博士等。 他们对我的开题报告，中期 检查和最终的毕业论文提出了很多宝贵的意见，我不再走很多弯路。 衷心感谢他们！ 感谢浙江工业大学之江学院各位老师在学习上的帮助和支持！ 我能完成学业，离不开家人全力支持和无私的爱，他们是我的精神支柱！ 感谢各位专家在百忙之中审阅和指导本文。 浙江工业大学硕士学位论文 学位期间参加的科研项目和成果 参加的科研项目 【1】浙江工业大学校级科研基金：之江学院学生信息查询系统(项目编号： 20050099 ) )。 招聘和发表的论文 [1]鲍卫兵、杜丰、周云水. GPRS在远程抄表终端上【j】.浙江工业大学学报，2006 三十四(四) 420424。 【2】杜丰，张英杰，陈璐.基于模拟退火算法的通用无纸化考试系统研究【j】.浙工大 学报，2008，36 (4) 382—385国家职业教育
#include