一种基于BM 的入侵检测优化匹配算法

李俊涛

（中共青海省委党校，青海西宁810001）

随着计算机网络的迅速发展，新一代互联网技术正全方位融入到人们的生活中，各类网络购物、移动支付、在线政务等应用和服务发展迅猛。互联网不断改变着人类生活的方式，也不断制造着各类木马和病毒，网络攻击事件频发，无不表明网络威胁的存在。如何保证互联网的安全，减少其负面影响，已成为一个重要话题。当前网络安全的防御策略主要是构建包括防火墙、安全网关、访问控制、入侵检测等的多层次防御体系，从而提高网络的安全性[1]。其中防火墙采用阻隔数据流量来规避威胁，入侵检测则是主动防御，主动检测目标网络中的流量，对数据包进行深度分析检测，如发现危险行为立刻报警，最大程度地提高了系统的安全性。

1 入侵检测系统

入侵检测的关键技术是对网络流量、系统状态和系统资源进行监控，如发现异常则进行示警，从而避免入侵行为对系统造成损害[2]。其核心思想来源于安全审计理论，首先对用户和系统行为的可信度进行评定，以结果作为依据，来识别非法入侵行为，从而帮助管理人员来制定相应的安全策略和防范措施，确保系统的完整性、保密性和可用性[3]。

1980 年James P.Anderson 在一份报告中首次提出入侵检测这一概念，他将未经授权故意试图访问信息导致系统不安全的行为阐述为入侵[4]。1987 年Dorothy E.Denning 在统计实现的基础上，给出了一种抽象的入侵检测模型IDES，主要由系统主体、检测对象、特征代码、异常活动、检测规则、审计记录6 部分组成[3]。后续又有学者在IDES 模型的基础上作了进一步的改进，将检测的重心偏向网络数据流量方面，得到了另一种检测系统NSM，它侧重于对网络数据流量的主动查找，探寻可疑行为，规避危险行为。

入侵检测技术按照不同的检查原理通常划为基于异常的入侵检测和基于特征的误用检测两类[5]。第一类是异常检测，它利用数据挖掘的原理，通过观察正常的网络流量，统计和归纳出一种特征规律并不断更新。当系统资源的使用状况或者用户行为和这种特征规律相偏离时，判断可能出现了入侵行为。它的优点在于可以抽象正常的行为，从而辨别出异常行为，其检测方式不受经验的限制，可以检测出未知的攻击，常见的算法有KNN 和Neural network 等。但是在实际的使用过程中，异常检测效率并不高，而且耗时过长，容易出现漏报和误报，使用上存在一定的局限性。第二类是误用检测，它的基本思想是用一种模式来表示入侵行为。通过分析各种不同的攻击手段和违规操作等，创建所有可能的攻击模式的合集和入侵特征库。当捕捉并预处理后的网络数据和该特征库相匹配时，则认定发生了入侵行为。其中匹配所用时间的复杂度是影响其性能的关键因素。误用检测核心在于有效正确地建立入侵检测模式，及时有效地更新特征库，这样才能保证系统的可用性。

2 Snort 入侵检测系统

Snort 入侵检测系统被用于各类平台，检测方法属于误用检测，使用快捷方便，规则语言通俗易懂。该系统不仅为开发者提供了可编写的规则原型，同时用户也可以自行编制入侵特征库和检测标准。Snort 系统框架如图1 所示。

图1 snort 系统架构图

捕获器：检测的前提基础任务就是获取数据包，首先将网卡更改为混杂模式，并设定中断模式的时间伐值，降低丢包率，从而精确捕获经过的网络数据包；其次根据不同系统环境选择Libpcap 或者Winpcap函数来收集数据包并分析网络协议。

解码器：捕捉好的数据包由解码器进行拆解分析，目前系统授权的网络接口有Ethernet、SLIP 等。捕获的数据包有：以太网、令牌环、UDP、TCP/IP 等。各类数据形式各不相同，因此必须对这些具体的元素进行解码，形成统一的可验证格式。Snort 解码器在不同的数据传输层，分别使用不同的解析函数进行解码，按照从低到高的方式，逐层递进直至全部完成。

预处理模块：为了便于检测模块对数据进行响应，新捕捉到的数据包不能直接进行检测匹配，而是先要进行预处理，形成统一的标准可识别的数据。预处理器可由外置插件组成，具有很强的灵活性和可扩展性，主要功能包括：对网络数据包重组、对异常数据检测、对网络协议分类解码等。

检测引擎：系统的核心任务就是检测，它的任务是检测数据包中是否存在安全威胁。按照用户设置好的规则，将标准化的数据包和特征库进行匹配，如果发现异常，则向报警系统发出危险信号，否则丢弃数据包。系统检测速度的快慢，取决于配置主机的性能和加载好的检测规则数量。

日志和报警：根据检测引擎对数据包的检测结果，该模块负责生成报警和记录日志。系统的输出方式和呈现形式灵活多样，可以自行设置日志和警报的内容形式、保存目录和输出类型等。

Snort 系统在入侵检测时，首先要进行初始化，如解析代码命令、载入特征规则、生成三维检测链表等。其次设置网卡模式，调用API 函数捕捉数据包并进行拆解分析，将分析后的数据预处理生成标准统一可用的数据。最后和特征规则库进行比对，匹配说明有入侵行为，触发报警输出模块，生成日志文件。若不匹配，则返回处理下一个数据包，如此反复循环检测，直至所有采集到的数据包检测完成。

随着高速网络时代的来临，入侵检测系统特征库不断增大，如何加快模式匹配速度、减少漏检与误检的产生，是入侵检测领域研究的一个新方向。

3 BM 算法及其改进算法

Snort 系统在各类网络安全研究中都备受关注，其搜索检测引擎模块经常会被移植到各类系统平台中。而检测引擎的核心是模式匹配，常用的模式匹配算法有单模式和多模式。本文着重探讨单模式匹配算法BM的思路与特点，并提出一种新的改进算法。

3.1 BM 算法

1977 年，Boyer 和Mooer 受KMP 算法的启发，阐释了一种字符串快速匹配的算法，即BM算法[3]。将两个字符串左对齐，从模式串最右的字符与文本串对应字符进行比较，若相同则继续向左比较；若不同，则将两个跨跃数值进行比较，取数值大的作为模式串的右移跨跃距离，再进行下一轮比较直至完毕。算法中有坏字符规则和好后缀规则两个函数，首先定义：P 为模式串，长度为n，P=P0P1P2...Pn-1，Pj∈∑（0≤j≤n- 1）；T 为文本串，长度为m，T=T0T1T2...Tm-1，Ti∈∑（0≤i≤m- 1）。

坏字符，在P 和T 对比的过程中，出现字符Ti和字符Pj不相同，此时可以分成两种情况，一是Ti在模式串P 中没有相同的字符，这时直接将模式串P 右移n 个位置继续比较。另一种是有一样的字符，只用考虑和Ti相同的最右边的Pj，将模式串P 右移n- j 个位置后继续比较。

好后缀，在对比过程中，P 与T 部分字符相同，此时可以利用已匹配的字符创建一个跨越函数，函数值表示右移距离j，移动后继续进行下一轮的比较。当出现不匹配时分成两种情况，一种是模式字符串Pi与模式字符Tj不匹配时,查看Tj左侧靠近j 的位置有没有模式串的一部分（Pj-s+1,...,Pn-s）与已匹配串的一部分（Pj+1,...,Pn）相同,如果相同则跨越S 个距离；再一种是没有相同的部分,但是P 中有一个最长的前缀与已匹配串部分相同（P1,...,Pn-s）=（Ps+1,...,Pn）,则模式串向右移动S 个距离。

BM匹配算法过程中，影响其性能的关键因素耗时，最坏情况为全部遍历一次,最好情况为一次匹配成功[6]。BM算法的优越性得到了许多专家和学者的认可，但仍不能满足大吞吐量数据的匹配需求，因此BM算法有待进一步提高。

3.2 BM 的改进算法

从上述的BM算法中可以看出，模式匹配算法要提高效率，关键是要解决字符对比失败以后，模式串向右跨越出的更远距离，从而减少对比的次数，减少匹配总体耗时。本文在BM算法和其他匹配算法研究的基础上，结合坏字符串的右移规则，只考虑模式串中存在的字符来增大右移距离，提出了一个新的算法。主要从两方面思考，匹配窗口右侧首选字符是否在模式串字符存在，如果有，是否和模式串首字符相同，以此为依据进行辨别，循环比对完成对整个文本串的检索。算法的基本思路如下：

第一步，将P 和T 两个字符串左边对齐，然后从右开始顺序比较，看首字符Pn-1和Tn-1是否相同，如果一致，则继续比较次字符Pn-2和Tn-2看是否相等，直至全部匹配或者出现不匹配的字符为止。

第二步，当出现不匹配时，观察模式串P 中是否有当前对比文本串Tn的后一位字符Ti+n，如果有则进入下一步，如果没有则继续查看Ti+n的后续字符，直至第s 个字符在模式字符串P 中存在，并检查该字符Ti+n+s是否和模式串首字符P0相同。

第三步，根据上述情况判断是否进入下一轮比对。

通过以上匹配算法分析可知，此算法可以快速全面查找文本串，相比BM 算法，增大了模式串向右跨越距离，减少了对比次数，降低了检测的耗时，整体算法优于BM。

3.3 实例仿真验证

为了验证改进算法的性能，实验使用了Snort、AppServ、adodb、ACID 等软件，进行了两类实验。

实验一：使用三台计算机互联，其中一台发送随机攻击数据包1000 条，另一台发送普通流量数据包，使用WinPcap 等软件制作成合成数据包共三组，通过数据包播放器分别发送给搭载BM 算法和改进算法的检测系统，分别记录了两个系统的检测时间如表1所示。

表1 系统检测时间对比表

对相同的攻击数来说，检测的时间越短，说明系统的检测速度越快。从获取的数据来看，BM改进后的算法比BM算法的耗时减少了约3%左右，说明改进的算法是比较成功的。

实验二：为了进一步确定改进算法的效率，通过输入相同的模式串和不同长度的文本串进行比较。实验随机选取了6 MB 和12 MB 大小的纯英文文本，以“world”为模式串进行测试。通过实验数据验证如图2所示。

图2 不同算法消耗时间对比图

改进算法无论是在匹配次数还是在耗时上都有所减少，说明改进算法在模式匹配过程中移动距离明显提升，匹配速度有一定的提高，改进的算法是比较成功的。

4 结语

本文介绍了入侵检测系统，对Snort 入侵检测系统的各功能模块进行了详细分析说明，得出系统的重要核心是检测模块，该模块的性能则取决于匹配算法的优劣。

通过对BM单模式匹配算法的学习和分析，提出了一种新的算法，该算法通过只考虑模式串中存在的字符来增大右移距离，检测效率明显提升。最后为了验证新算法，部署了Snort 入侵检测系统，通过不同实验条件，对改进的算法进行了评测和分析，表明新的改进算法比BM算法更优，对今后高速网络大吞吐量的入侵检测有一定的借鉴意义。