网络入侵检测系统中的模式匹配算法设计优化

陈卓民

（陕西警官职业学院教务处陕西西安710021）

在现代互联网不断发展的过程中，网络规模在不断的扩大，网络应用也越来越朝着全球化的方向发展。在此背景下，网络入侵攻击事件的发生机率也在不断的增加。传统防火墙技术已经无法有效保证网络安全，网络入侵检测系统属于积极主动安全防护技术，其目前已经成为网络安全领域中的研究热点内容[1]。网络入侵检测系统一般使用被动监听方式实现，通过关键网段实现网络传输数据包的获取，并且通过多种检测分析方式对数据包进行分析，从而寻找入侵的证据。网络入侵检测系统能够基于不对网络性能造成影响然后实现网络检测，从而寻找网络攻击事件[2]。现代网络入侵检测系统检测分析的方法主要包括两种，分别为异常检测和基于特征检测。因为异常检测需要学习时间，并且具有较高的检测误报率，无法满足大流量网络实时检测需求。所以，目前都使用基于模式匹配特征检测。现代网络流量在不断的提高，并且入侵特征库在逐渐更新，对于基于特征匹配网络入侵实时检测性能提出了一定的挑战[3]。基于此，文中对网络入侵检测系统模式匹配算法的设计进行全面的分析。

1 网络入侵检测系统和算法

1.1 网络入侵检测系统

网络入侵检测系统属于标识并且隔离入侵安全的技术，其也是防火墙以外的第二道防线，图1为网络入侵检测系统的结构。

图1 网络入侵检测系统的结构

网络入侵检测系统的主要特点就是经济性、安全性、时效性、可扩展性，其主要包括事件产生器、事件分析器、响应单元和事件发生库。在实际使用过程中，入侵检测系统主要包括存储系统、分析系统传感器及控制台，其中存储系统的主要目的就是实现系统运行数据及入侵攻击过程进行存储，其中控制台的目的就是集中管理[4]。

1.2 网络入侵检测算法

网络入侵检测算法对检测精准性及效率具有直接的影响，现代网络入侵检测算法主要包括模式匹配、专家系统、状态迁移分析、统计、神经网络、数据挖掘及免疫学[5]。

每个基于模式匹配的入侵检测都要求具有已经设置的入侵模式，那么就需要实现入侵行为描述的方法目前入侵检测系统描述方法并不同，不同产商的定义描述方法不同，那么用户只能够根据开发商对自身入侵检测模式库进行升级[6]。图2为基于模式匹配入侵检测系统的结构。

图2 基于模式匹配入侵检测系统的结构

目前模式匹配检测算法在执行任务的过程中都是通过fpEvalPacket实现的，在函数模块实现预处理之后，对Detect函数进行调用，之后实现数据包内容特征的规则匹配。如果捕捉的数据包协议为Tcp，那么就实现fpEvalHeaderTcp函数的调用。

2 传统模式匹配算法

传统模式匹配算法的概念为：

假设n长度文本是T[1…n]，m长度模式P属于P[1…m]，模式的集合属于{Pi}，模式集合的总长度属于M。单模式匹配指的是文本T在对P的寻找；多模式匹配指的是文本T在对多个模式进行寻找。在入侵特征不断增加的过程中，入侵检测模式匹配算法也逐渐从单模式转变成为多模式[7]。

传统模式匹配算法主要包括以下：

其一，AC算法。此算法使用最为广泛，其属于多模式匹配经典算法，目前其主要包括两个基本的研究方向，分别为基于自动机和基于BM跳跃及过滤。其使用有限状态机思想，在实现模式匹配之前要实现所有模式预处理，从而实现有限状态机生成，之后从其中寻找匹配。AC函数预处理的过程主要包括3个函数，分别为状态转移函数goto、失效函数fail、输出函数output，图3为AC算法转移函数的转换过程[8]。

图3 AC算法转移函数的转换过程

基于失效函数结构过程，其示意图详见图4虚线部分。

图4 AC算法失效函数的示意图

图5为AC算法中的输出函数示意图，在预处理以上3个函数之后，AC算法以转移函数及实效函数创建类似确定状态自动机，此类能够对转换矩阵存储状态，矩阵中的每行都相互对应某个状态，每个对的状态要实现相应列对应字符之后的转换状态[9]。

表1为状态转换矩阵，其匹配的过程为从0状态开始，逐一实现T文本字符的输入，以状态转换矩阵寻找之后状态，目前状态输出函数不空的时候就要实现匹配内容的输出，直到文本末尾[10]。AC算法模式匹配时间复杂程度表示O（n）。

其二，BM算法。此算法属于单模式匹配算法中的经典算法，目前单模式匹配算法大部分都是基于BM算法进行改进。其在匹配的过程中要对其文本左端和模式，从模式右端起逐一进行字符对比，在出现不匹配的时候就要使模式向右进行移动，移动距离通过预处理的规则计算值进行决定。BM算法以坏字符及好后缀的规则对移动距离进行计算，从而创建坏字符移动表及好后缀的移动表，在实现匹配的过程中对此表进行查找，使用此表移动距离最大的实现模式移动[11]。BM算法创建坏字符异动表时间复杂程度为O（m+Σ），创建之后的好后缀异动表时间复杂度属于O（m）。虽然BM算法最坏的时间复杂度表示O（m*n），但是因为算法使用跳跃式的匹配，所以其实际的次数只是文本长度20%～30%。

BM算法术单模式匹配，其在一般使用过程中的性能比较优秀，但是其在每次匹配的时候都要计算模式，那么就会提高预处理的花费，并且其在多模式匹配过程中的使用效果并不理想，要对BM算法重复使用，从而降低了使用效率[12]。

其三，MWM算法。此算法属于改进算法，其主要是利用目前匹配模式集合特征实现NoBC算法及ExBC算法、EXBW算法的调用。模式集合中的数量较多，因为最小模式长度会对算法匹配时候的文本字符最大的跳跃距离造成影响，假如最小模式为1，那么就使用hash表及NoBC表。其预处理的过程为：

图5 AC算法中的输出函数示意图

表1 状态转换矩阵

首先，字典排序，得到msPatArray表的内容，详见表2。

之后，创建hash表，其主要是以每个模式前两个字符散列值为基础进行创建。表3为hash表中的内容。

通过以上可以看出来，0的前缀字符块为aa。因为其表是以字符串为基础创建的，所以有256项。本文以BM算法为基础实现模单式匹配算法的优化[13]。

表2 msPatArray表的内容

表3 hash表中的内容

3 网络入侵检测系统模式匹配算法的优化

网络入侵检测系统能够实现执行数据包的深入检测，其还能够对负载没有或者已经实现定义的规则集相互匹配模式串进行扫描，从而对其是否具有入侵检测事件进行检测。

3.1 分析BM算法中的好后缀函数

从理论方面进行分析，BM算法较为严谨，但是其在实际使用过程中的性能并不理想。所以，本文就修改了好后缀规则中的不足。此实验需要测试的指标主要为：

其一，BM和BMH算法运行的时间；

其二，BM和BMH算法的字符比较数量；

其三，BM算法中字符比较数量及使用好后缀规则数量。

因为入侵检测中的模式串长度都是在20～30字符自检，本文进行随机选择进行实验[14]。表4为BM和BMH算法运行过程中总时间的对比。

通过表4可以看出来，BM算法和BMH算法的总字符数量相同，但是在时间复杂度方面，后者性能更加良好。

通过表5可以看出来，BM算法匹配过程使用好后缀数量较少，并且没有规律，所以就提高了BM算法总体运行时间。对于此种问题，本文就对全新模式匹配算法进行改进，将好后缀规则进行去掉，改进坏字符规则，从而有效提高模式匹配速度。

表4 BM和BMH算法运行过程中总时间的对比

表5 BM算法总字符对比数量和使用好后缀规则数量

3.2 改进算法

3.2.1 主要思想

其一，大部分规则匹配内容后缀及前缀都相同，所以改进算法要能够满足入侵检测系统模式匹配；

其二，单模式匹配算法及模式对其文本字符进行偏移量计算，另外就是通过下一个字符对偏移量进行计算，本文所改进的算法就是将两者相互结合，从而形成全新的算法[15]。图6为改进算法的工作流程。

3.2.2 算法实现

改进算法的实现步骤主要为两个阶段，第一阶段：预处理。对两个字符集进行计算，得到计算结果；第二阶段为初始位置及匹配方向。在开始匹配的时候，要求模式串左端和待测文本左端相互对齐，字符对比通过模式串末端对齐文本T开始，从右到左开始。如果匹配失败，模式串就要移动到右端。

3.2.3 算法实例

使用改进算法，其只移动了两次，一共匹配3次就能够寻找模式块，说明本文所设计的改进算法能够提高预处理时间，并且计算方式较为简单[16]。

图6 改进算法的工作流程

表6 Badchar1与Badchar2的函数

4 结束语

在网络使用不断发展的过程中，网络宽带在不断的增加，所以就要提高网络入侵检测系统处理性能，从而使其能够满足大流量网络环境需求。本文就对模式匹配算法进行了研究，并且实现了单模式匹配算法的改进。通过实例表示，改进的匹配模式算法能够有效满足网络使用需求，提高系统检测效率。