基于Snort的BM模式匹配算法的改进

姚鑫洋 古春生

摘要：近些年来，很多国家工控系统都遭受到了网络安全攻击，造成了巨大的经济损失。网络入侵检测系统（ NIDS）是网络安全的重要组成部分之一，开源入侵检测软件通过活跃的社区和研究者们不断更新来应对这快速发展的网络环境。文章介绍了BoVer-Moore字符串匹配算法，并提出一种改进的BM算法，并基于Snon入侵检测系统实现并验证改进算法，实验表明改进的算法提高了模式匹配效率。

关键词：入侵检测：BM算法：Snort

中图分类号：TP393. 08

文献标志码：A

0 引言

随着互联网技术在工业控制系统（ICS）中的广泛应用．工控系统被网络攻击的次数也越来越多，攻击手段如病毒、木马等通常会导致系统出现故障，国家一旦重要的工控系统出现损伤，影响将是巨大的。全球近些年来发生了多起工控安全事件，其中有几起非常严重，如2015年乌克兰电网遭“Black Energy”病毒攻击，2017年“WannaCry”勒索病毒攻击全球公共设施．2021年美国最大油管被黑客组织“Darkside”网络攻击并遭到勒索，这几起安全事件都对其国家造成了巨大的经济损失，也警示大家需要重视-厂-控网络安全问题。在网络安全防护体系中，入侵检测系统是继防火墙后的另一道防线，入侵检测的主要功能是对网络和系统中的异常行为与攻击进行监测与报警。

1 入侵检测系统

入侵检测指的是检测计算机网络中未授权的访问。入侵一般是由其他计算机发起的，来攻击网络中的其他设备。入侵检测系统（IDS）通过监测网络流量来检测入侵行为，对未授权行为进行报警，将报警信息记录至系统日志，便于后期的分析及对攻击行为的防范[1]。

1.1入侵检测技术

入侵检测技术分为两种：一是误用入侵检测技术，通过将入侵行为与数据库中存储的已知行为进行比较，当入侵行为与已知行为相匹配时，即被认定为入侵。但随着互联网技术的发展，网络攻击方式越来越多样、数据库不能够及时更新等问题，导致其漏报率很高。二是异常入侵检测技术，通过建立正常行为作为模型，寻找与之偏离的异常行为。相较于误用入侵检测技术，异常入侵检测漏报率低，可以检测出之前没有过的入侵行为，但互联网技术的快速发展，正常行为的模型跟不上发展的速度，因此误报率较高。虽然容易误报，但是几乎所有入侵行为都能被检测到，异常入侵检测技术的安全性大大提高。其中异常入侵检测方法有以下3种：基于统计的方法、基于知识的方法、基于机器学习的方法。

1.2

Snort

Snorc是一种开源入侵检测系统，主要由嗅探器、预处理器、检测引擎和输出模块4个部分组成。它有3种工作方式，嗅探器模式，包记录器模式和网络入侵系统模式，其中入侵检测系统模式最为常用。Snort通过基于规则来对系统进行检测，将事先设定好的规则与监测的流量或数据包比较，来确定是否为攻击行为[2]。Snort规则由规则头部和规则选项组成，规则头部包括动作、协议、地址和端口、方向、目的地。动作：在规则触发时，Snorc应该进行的操作；协议：告诉Snort应用的协议，如IP协议、ICMP协议等；地址和端口：指定发送的地址和端口；方向：分为单向和双向：目的地：与地址和端口相似，但表示的为接收端。规则选项：含有一个报警信息和包的哪个部分被用来产生这个信息。Snort将处理过的数据包和定义好的规则进行匹配，原理是在数据包查找是否存在攻击行为的特征，这一过程被称作模式匹配，模式匹配算法是Snort的核心算法，匹配算法的性能决定入侵检测的效率，入侵检测效率越高，系统的安全性就越高。

2 匹配算法

入侵检测中匹配算法分为单模式匹配算法和多模式匹配算法。单模式匹配算法是一个模式串和一个主串进行匹配，常见的单模式匹配算法有BF、KMP、BM等算法。多模式匹配算法是多个模式串和主串进行匹配，常见的多模式匹配算法有AC算法和Trie树算法等[3]。本文对Snort入侵检测系统中规则匹配所用的BM算法进行了分析并改进，改进后的算法能够提高Snort匹配效率。

2.1

BM算法

BM算法采用从有到左的匹配方式，通过坏字符规则和好后缀规则确定移动距离[4]。首先，将T（文本串）与P（模式串）左侧对齐，然后从右向左依次匹配进行比较，当出现不匹配的情况，通过坏字符和好后缀规则计算模式字符串向右移动的距离，直到匹配过程结束[5-6]。

2.1.1 坏字符规则

模式串P和文本串T从右至左匹配过程中，如果发现P的第一个字符和T的第一个字符x不匹配，将根据字符x是否出现在模式串P中进行讨论，如图1所示。如果出现，将模式串P中最靠近坏字符的第一个字符x与文本串x对齐。如果没有出现，则直接向右移动，移动距离等于模式串长度。

2.1.2好后缀规则

当模式串P和文本串T从右向左依次进行匹配，匹配失败时，有部分字符匹配成功．这些匹配成功的字符被称作好后缀。这时对模式串P进行检索，如果P中存在和好后缀相同的字符，则将这些字符和好后缀对齐。如果P中没有和好后缀相同的字符，则找到和好后缀相同的最长前缀，使最长前缀与好后缀对齐，如果没有出现任何相同的字符，则移动距离为模式串P本身的长度。

2.2 改进BM算法

BM算法的匹配过程：将模式串P与目标串T左边对齐，从右边开始匹配，匹配成功则继续向左移动，若匹配失败则调用好后缀规则和坏字符规则，选择最长的移动距离来当作模式串的移动距离[7-8]。移动距离越长，匹配次数越少，检测效率越高。在此基础上，提出了一种改进的BM算法，改进前后算法移动如表1-2所示，移动距离分两种情况。

（1）當调用好后缀规则时，为文本串T中的下一个字符添加判断，判断下一个字符串是否存在于目标串P中，如果从左到有的n个连续字符不匹配，则移动距离为n+1。

（2）當调用坏字符规则时，如果文本串T的下一个字符不存在目标串P中，则移动距离为n+1．如果下一个字符存在目标串中，则使用原本的坏字符规则来决定移动距离。

3 实验及分析

3.1 实验环境

实验操作系统为Ubuntu 18. 04．Inter（ R） Core（TM）双核CPU2. 30 CJHz．内存4 GB，硬盘容量100 CB.Snort版本2.9.20．数据集DARPA1999。

实验过程为：通过Snort的入侵检测模式对数据集进行读取，得到读取时间，改变规则数目再进行读取，记录下时间。在mslring．c文件中将优化后的算法替换原有的BM算法，对Snort重新进行编译，规则数目和数据集与原保持一致，再进行读取并记录下时间。

3.2 实验结果

如图1所示，实验中数据集个数分别为546、1526和2 100，原算法检测时间为12. 251 s、43. 319 s和52. 298 s，改进算法检测时间分别为9.499 s、40. 481 s和49. 955 s。实验结果表明，改进后的算法和原算法匹配耗费时间比较有所减少，基于DARPA1999数据集，得出优化后算法的效率提升约为6%。通过增大每次字符串比较失败后的移动距离，能够有效提高匹配速度，从而提升Snort入侵检测系统的性能。

4 结语

随着互联网技术的快速发展，智能家居、智能汽车不断地普及，人们生活已离不开网络，一旦网络遭到攻击，人们的生活乃至生命都会受到威胁，因此网络安全需要得到大家的重视。Snorc作为开源网络入侵检测系统，为提高网络安全做出了巨大的贡献。匹配算法多种多样且应用广泛，提高匹配速度意味着提高软件或系统的效率，让它们来应对这快速发展的网络。本文对Snort中BM算法进行了研究与改进，通过提高移动距离，来减少匹配次数。在Snort入侵检测系统下测试，证明可以提高其规则匹配速度，提升入侵检测效率。

参考文献

[1]冷峰，张翠玲，陈闻宇，等．从Snorc规则的协议信息分析攻击[J]．计算机应用，2022（ S1）：173-177.

[2]刘金龙，刘鹏，裴帅，等．基于关联规则的网络异常检测系统设计与实现[J]．信息技术与网络安全，2020（ 11）：14-22．

[3]薛芳，林丽．计算机网络入侵检测系统的多模式匹配算 法 [ J ] . 计算机系统应用 . 2021 （ 4） ： 210-215 .

[4] OJUGO A A， OYEMADE D A. Boyer Moore string-match framework for a hybrid short message service spamfiltering technique [ J ] . Intemational Journal of ArtificialIntelligence， 2021（ 3） ： 519.

[5] OJUCJO A， EBOKA A O. Signature-based malwaredetection using approximate Boyer Moore string matching{algorithm [ J ] . Internalional Journal of MathematicalSciences and Computing， 2019（ 3） ： 49-62.

[6] MELICHAR B. On modification of Boyer - Moore -horspool ' s algorithm for tree pattern matching inlinearisecl trees [ J ] . Theoretical Computer Scieru-.e ， 2020（ 830） ： 60-90.

[7]MAHAJAN A， CUPTA A， SHARMA L S.Performance evaluation of different pattern matchingalgorithms of snort [ J ] . Intemational Journal of AdvancedNenvorking and Applications， 2018（2） ： 3776-3781.

[8]jUAN L I， LINA Y. HAODAN R， et al. Researchand Improvemenr of BM Pattern Matching Algorithm[ C] 2020 International Con～erence on Artific-.ialIntelligence and Compurer Engineering

（ ICAICE ） .IEEE ， 2020 ： 204-210.