改进Boyer匹配算法在Snort入侵检测中的应用

马小雨， 刘双红

(1. 河南工程学院 计算机学院， 河南 郑州 451191；

2. 郑州航空工业管理学院 计算机科学与应用系， 河南 郑州 450046)



改进Boyer匹配算法在Snort入侵检测中的应用

马小雨1， 刘双红2

(1. 河南工程学院 计算机学院， 河南 郑州 451191；

2. 郑州航空工业管理学院 计算机科学与应用系， 河南 郑州 450046)

摘要：以Snort入侵检测系统为研究对象，探讨其规则匹配环节的适用算法，并在Boyer算法的基础上设计一种改进方法.此方法首先设计了一个统计数组，然后以两个相邻字符为组合执行匹配，并分为3种策略判断如何确定最大移动长度.实验结果表明：这种改进措施，使得最大移动长度更加合理，相比于Boyer方法，改进方法的字符比较次数明显降低，窗口移动次数明显降低，执行时间明显减少.

关键词：网络安全； 入侵检测； Snort系统； Boyer算法

为了应对黑客攻击风险、协议漏洞风险、防御缺陷风险等一系列网络间的安全隐患[1-2]，信息安全、密码理论、入侵检测等领域的研究被大量开展[3-5].Snort入侵检测系统是一个非常成功的网络安全检测系统，具有免费开源、精准匹配的诸多优点[6-7]，且在大多数操作系统上都可以运行，这对国内普遍使用的Windows系统具有重要意义.从执行流程上看，Snort入侵检测系统以字符为单位对网络信息进行解读，分为捕获数据、解码数据、预处理数据、规则匹配、判断输出等环节[7-8].规则匹配是用于判断信息是否为安全的核心环节，在这个阶段中，很多字符匹配算法被成功应用，而Boyer匹配算法是一种最常见的方法[9].Boyer匹配算法原理简单，便于实现，但也存在重复比较等问题.为此，很多基于Boyer算法的改进算法被构建出来，如BMH算法、BMHS算法等[10-11].本文在Boyer算法的基础上进行改进，提出更适合Snort入侵检测系统使用的规则匹配算法.

1改进Boyer匹配算法

从实现原理上看，经典的Boyer匹配算法属于典型的后缀匹配方法.在字符串匹配执行的过程中，设置一个标准串，将标准串和待匹配的字符串，按照由右及左的顺序执行比较.匹配过程是否结束的判断依据有2个：第1种是达到预先设定的，确定为匹配失败；第2种是确定为匹配成功.整个匹配过程，都需要根据两个重要的特征字符指引，一个称为“优良后缀”，一个称为“不良字符”.

在实际运用中，为了减少带匹配字符串和标准串的比较次数，Boyer匹配算法增大了移动距离.据此，在经典Boyer匹配算法的基础上进行改进，以期获得更大的移动距离.

首先，根据经典的Boyer匹配算法获得一个移动距离L1.然后，把T[k+1]和T[k+2]组合起来，再计算出一个移动距离L2.最后，比较这两个移动距离的大小，选取最大的那个作为匹配过程执行时的移动距离.其中：T为表示待匹配字符串;k为一个以i为边界,同标准串后缀能够匹配上的最大长度;B为标准字符串.算法有如下4个实际的执行过程.

1) 设置一个统计数组，用于统计各个字符在标准串中出现的次数，即

(1)

式(1)中:Btime(Char)为字符Char在标准串中出现的次数.如果字符Char在标准串B中只出现1次，统计数组纪录为1；如果字符Char在标准串B中出现的次数大于1，统计数据纪录为0.

2) 从待匹配字符串中按照T[k+1]和T[k+2]的顺序提取相邻的字符组合，并纪录为Char(1，2)，并用Char(1，2)和标准串B进行匹配.

3) 若标准串B没有字符组合和Char(1，2)相同，需要进一步比较Char(1，2)和标准串的第1个字符B[1].如果Char(1，2)不含字符B[1]，L2的值就是m+2；如果Char(1，2)中的第1个字符和B[1]相等，那么L2的值是m+2；如果Char(1，2)中的第2个字符和B[1]相等，那么L2的值是m+1.

4) 若标准串B中有字符组合和Char(1，2)相同，且Char(1，2)中不含字符B[1]，Dtime(Char)=1，那么L2的值是m+2；若标准串B中有字符组合和Char(1，2)相同，且Char(1，2)中不含字符B[1]，Dtime(Char)=0，那么L2和L1相同.L1的表达式为

2实验结果与分析

从执行先后顺序的逻辑关系上看，Snort入侵检测系统从主函数Main()开始，然后调用并执行Detect()函数完成入侵检测.实验中，需要将各种字符匹配算法编制成函数，并用Detect()函数调用.为了和改进算法形成对比，选择了经典的Boyer匹配算法，通过程序实现后封装在Boyer()函数中.对于提出的改进算法，通过程序实现后封装在ImBoyer()函数中.在验证实验的过程中，Boyer()函数和ImBoyer()函数都可以供Detect()函数调用.

实验所用的计算机配置：酷睿双核主频为2.0 GHz的CPU，8 GB的内存，500 GB的硬盘；Windows 7.0操作系统；Snort入侵检测系统.实验针对50个随机长度的待匹配字符串，并以不同长度标准串完成匹配.50个待匹配字符串的部分样本及全部不同长度的标准串，如表1所示.

表1　待匹配字符串样本和标准串

随着标准串长度的改变，比较经典Boyer算法和提出的ImBoyer算法完成匹配的字符比较次数、窗口移动次数和执行时间，结果如图1所示.图1中：n1为字符比较次数；n2为窗口移动次数；t为执行时间；l为标准串长度；s为数据包大小.由图1(a)可知:提出的ImBoyer算法的字符比较次数明显低于Boyer算法;同时，随着标准串长度的增加，两种算法的字符比较次数都开始下降，但ImBoyer算法下降的速度明显更快.这充分说明，所提出的ImBoyer算法性能更加优秀.由图1(b)知：提出的ImBoyer算法的移动次数明显低于Boyer算法；同时，随着标准串长度的增加，两种算法的移动次数都开始下降，但ImBoyer算法下降的速度明显更快.这充分说明，所提出的ImBoyer算法性能更加优秀.由图1(c)可知：提出的ImBoyer算法的执行时间明显低于Boyer算法；同时，随着数据包大小的增加，两种算法的执行时间都开始增加，但ImBoyer算法增加的速度明显更慢.这充分说明，所提出的ImBoyer算法性能更加优秀.

(a) 字符比较次数　　　　　　　　(b) 窗口移动次数　　　　　　　　　　(c) 执行时间　　　　图1　经典Boyer算法和ImBoyer算法的比较Fig.1　Comparision between Boyer algorithm and ImBoyer algorithm

3结束语

通过在规则匹配环节算法设计，对Boyer字符匹配算法进行了改进.通过对字符比较次数、窗口移动次数、执行时间3个方面进行实验研究，证实了改进工作的有效性.

参考文献：

[1]SRIDHAR M，VAIDYA S，YAWAKJAR P.Intrusion detection using keystroke dynamics and fuzzy logic membership functions[C]∥Proceedings International Conference on Technologies for Sustainable Development.Switzerland：Bridges Press,2015，27(4):444-458.

[2]李杰.基于Snort的入侵检测系统规则解析及改进研究[J].电子技术与软件工程，2014，19(8):240.

[3]PARVAT T J，CHANDRA P.Performance improvement of deep packet inspection for intrusion detection[C]∥Proceedings 2014 IEEE Global Conference on Wireless Computing and Networking.[S.l.]:IEEE Press,2014:224-228.

[4]PASTRANA S，TAPIADOR J E，ORFILA A.Defidnet: A framework for optimal allocation of cyberdefenses in intrusion detection networks[J].Computer Networks，2015，80:66-88.

[5]谭笑，柯泽贤.基于混合高斯和帧间差分的机场安全入侵检测[J].计算机仿真，2014，31(11):38-41.

[6]陈柏生，吴可沾，杨育辉.互联网用户安全登陆平台设计[J].华侨大学学报(自然科学版)，2011，32(6):638-640.

[7]储泽楠，李世扬.基于节点生长马氏距离K均值和HMM的网络入侵检测方法设计[J].计算机测量与控制，2014，22(10):3406-3409.

[8]MACDERMOTT A，SHI Q，KIFAYAT K.Collaborative intrusion detection in a federated cloud environment using the Dempster Shafer theory of evidence[C]∥European Conference on Information Warfare and Security.[S.l.]:Earlybird Press,2015，195-203.

[9]PAN Zhiwen，HARIRI S,AI-NASHIF Y.Anomaly based intrusion detection for building automation and control networks[C]∥Proceedings of IEEE/ACS International Conference on Computer Systems and Applications.Morocco:EasyChair Press,2015:72-77.

[10]袁其帅，刘云朋.基于人工免疫原理的网络入侵检测系统的应用与研究[J].科技通报，2014，30(11):131-135.

[11]钱勤，张减，张坤，等.用于入侵检测及取证的冗余数据删减技术研究[J].计算机科学，2014，41(11):252-258.

(责任编辑： 陈志贤 英文审校： 吴逢铁)

Application of Improved Boyer Matching Algorithm in Snort Intrusion Detection

MA Xiaoyu1， LIU Shuanghong

(1. School of Science， Henan University of Engineering， Zhengzhou 451191， China；2. Department of Computer Science and Application， Zhengzhou University of Aeronautics， Zhengzhou 450046， China)

Abstract：In this paper， the application of Snort intrusion detection system is studied. An improved method based on Boyer algorithm is designed. This method first designs a statistical array， then executes the matching with two adjacent characters， and divides into three strategies to determine the maximum movement length. Experimental results show this improvement makes the maximum movement length more reasonable. Compared with the Boyer method， the proposed method is significantly lower than the number of characters method， the number of windows mobile number is significantly reduced， the execution time is significantly reduced.

Keywords：network security； intrusion detection； Snort system； Boyer algorithm

中图分类号：TP 393.08

文献标志码：A

基金项目：河南省科技厅科研项目(102102310261)

通信作者：马小雨(1978-)，男，讲师，博士研究生，主要从事计算机网络与安全的研究.E-mail:2622810975@qq.com.

收稿日期：2015-12-22

doi:10.11830/ISSN.1000-5013.2016.02.0168

文章编号：1000-5013(2016)02-0168-03