计算机网络入侵检测系统匹配算法

曾宏志

（江西工程学院智能制造与能源工程学院 江西省新余市 338000）

在现代互联网不断发展的过程中，网络规模不断扩大，网络应用也朝着全球化方向发展。在这样的背景下，网络入侵攻击事件发生的几率也在提高。传统的防火墙技术已经无法保证网络的安全，为了解决计算机网络中网络入侵以及网络攻击等不安全因素，我们应用了大量的网络安全技术，计算机网络入侵检测系统就是其中之一。计算机网络入侵检测系统的应用，能够进一步提高计算机网络的安全性，让人们在使用计算机网络时能够更加安心。本文对网络入侵检测系统模式匹配算法的设计进行全面分析。

1 网络入侵检测基本模型介绍

1.1 网络入侵检测基本过程

网络入侵检测的基本过程，可以分为匹配，分析以及过滤三个部分。匹配是指在网络数据包中进行侦查匹配，来查找当前网络中是否有网络攻击以及非法的网络入侵。其次，分析是指分析数据以及规则板块是否吻合。过滤是指在查找到网络攻击以及网络入侵时，或者是说在网络入侵检测查找到不安全的信息，以及不安全的因素，或者是安全隐患时，不能够及时将这些不安全的信息过滤掉，提升网络使用的安全性。入侵检测系统是网络的保护机制，它能够实时监测我们的网络行为，保护我们日常使用的网络，提高网络使用的安全性。同时，网络入侵检测机制的使用，能够帮助抵抗网络内部的不定时攻击以及网络外部的攻击与网络外部的入侵。

1.2 网络入侵检测基本模型结构

网络入侵检测基本模型主要有两种形态，第一种形态是网络入侵检测基本模型分为审计记录、网络数据包，事件发生器，行为特征模块以及规则模块四个部分，网络数据包主要就是储存各种各样的网络数据，以供之后匹配算法的使用。事件发生器主要作用是抽取一些网络上的有安全隐患的行为；行为特征模块主要是记录异常行为，除了记录异常行为之外，行为特征模块还具备自我更新以及学习的能力，该模块可以定期自我革新，并且可以通过学习增加其他的性能。规则模块儿是判断数据能否入侵的基础，规则模块会将变量域值传输给行为特征模块。

除了以上的结构构成之外，网络入侵检测系统也可以分为数据采集、数据分析以及结果处理三个部分。数据采集板块正如它的名称一样，主要负责网络上各种数据的收集工作。数据分析这一板块，是入侵检测系统中的重要板块，他可以说是入侵检测系统的核心部分。如今现代网络入侵检测装置在进行数据分析时，往往会选择模式匹配这一方法，因为模式匹配的原理较为简单，简模式匹配的工作效率较高，能够较好的分析处理网络入侵。在数据分析完成之后，数据分析板块将会将这一事件发送给结果处理板块，由结果处理板块决定某行为是否构成网络入侵，并采取相应的解决措施。

1.3 网络入侵检测系统评价

在网络入侵检测系统创建成功之后，我们需要根据网络入侵检测系统的性能，对其成功与否进行评价。首先，我们需要判断该入侵检测系统是否能够让管理人员及时的掌握网络中系统的变化，判断该入侵检测系统是否能够及时的查找到网络中所存在的异常信息。在对该入侵检测系统进行评价时，我们也需要考虑该系统是否够在事故发生时，对计算机网络采取全方位的保护，能够保护网络系统免受攻击，或者是免受网络入侵。

2 计算机网络入侵检测系统匹配算法

2.1 模式匹配算法分析

针对字符串模式匹配算法的研究是当今计算机领域的重要研究内容，针对字符串匹配模式的研究被广泛应用到语言应用、拼写检测等多个领域。在网络入侵检测当中，模式匹配算法是指，在给定入侵规则库中模式字符串后，在网络数据包中查找这一字符串，进而确定该模式字符串是否在网络数据包中出现，确定该字符串出现在网络数据包中的哪个位置。网络入侵检测主要包括三个部分，首先是指获取数据包，其次是数据以及字符串的预处理，第三是检测攻击。在网络入侵检测过程当中，数据源就是我们所获得的网络数据包，我们可以采取检测网络数据包的方式，来发现当前计算机网络中的入侵以及攻击。为了提高模式匹配算法在入侵检测中的利用率以及利用效果，我们应当对当前的模式匹配算法进行一定的提升。

（1）当进一步提升当前提取模式的质量，在网络入侵检测装置检测到入侵时或者是检测到攻击时，应当展现出鲜明的特征，能够提醒使用者已经检测到入侵。同时要注意，在提取模式设置以及提升的过程当中，要注意模式与模式之间的配合，避免冲突或者是漏洞的出现。

（2）为了提高模式匹配算法，我们需要在原有的基础上增添或者是删除一些模式匹配，因为攻击手段以及攻击方法始终处于不断的变化当中，为了适应这些不断的变化，我们需要对模式匹配进行一定的变更。

（3）我们需要解决增量匹配与完全匹配这一问题，增量匹配的应用，能够减轻处理系统的压力，提高入侵检测系统的工作效率。我们对网络入侵检测系统进行一定的升级，能够使得匹配机制更加全面，能够解决更多的匹配问题，检测到更多的网络攻击以及网络入侵。

2.2 传统网络入侵检测算法（BM算法）

BM 算法是单模型精确匹配算法，该匹配算法是由Boyer 和Moore 共同设计的，这也就是为何这种匹配算法被命名为BM 算法。BM 算法运算效率较高，在计算机网络入侵检测系统中有着十分重要的应用，BM 算法再进行运算时，在对字符串进行匹配时，会舍弃，或者说跳过那些没有用处的字符，这样的匹配方式能够进一步提高BM 算法的运算速度，减少运算时间的浪费，BM 算法有着很高的运算效率。

BM 算法的主要运作过程:比如说在当前的文章中，要求从a位置起，让这字符串与运算模式进行从左向右的匹配比较，我们可以发现，如若再匹配比较过程当中，Wa 将不会在这一运算模式中出现，或者是在运算完成之后，出现在运算模式的末端。如若算法运行过程当中，没有发现匹配内容，那么正文当中的许多字符就不会出现在模式串中。在之后的运算以及匹配时，应当从正文的a+dist[Wa]处再次进行匹配。

在算法的字符串与模式匹配过程当中，可以选择跳过一定数量的字符，这些字符无需进行比较，直接略过这些字符来进行字符串与模式的匹配。因为BM 算法在运算过程中，常常会跳过一些字符，并不是所有位置都会进行匹配，因而BM 算法在运算以及匹配时速度更快，因此有着更高的实用性。BM 算法在匹配以及查找过程当中，使用的是“跳跃式”查找策略，如果在匹配过程当中，相同的字符在模式串中反复出现，那在大多数情况下，我们就不需要对完整的这一文本进行全方面的扫描，这在一定程度上减少了工作量，减轻了工作负担。

2.3 改进的BM算法

在BM 算法运算时，如若执行文字串或者是正文中从a 位置开始的“返前”匹配模式，并在这一匹配模式下进行从左到右的匹配检查，如若在匹配过程中发现不匹配，那么文本串的指针就会出现回溯这一现象，在某些情况下，会导致死循环的出现，这会影响匹配工作的进行。因此，为纠正BM 算法中出现的问题，以及BM算法的局限性，需要在bm 算法的基础上进行一定的改进，为此Horspool 在1980年提出了bmH 算法。BMH 算法在BM 算法的基础上进行了优化，简化了原有的bm 算法，匹配效率相比于bm 算法有了更大的提高。改进过后的bm 算法，相比于圆心的bm 算法，不匹配过程中的模式与正文移动距离相较于之前有所增加。除此之外，与bm 算法不同，不再只是关注没有匹配的字符，而是将关注的焦点放在了匹配文本的每一次匹配失败的最后一个字符。在算法的匹配过程中，会根据这最后一个字符在文本中是否出现，根据这最后一个字符在文本中出现的位置来决定匹配时所跳跃的步数，进而决定跳跃模板的长度。如若在匹配过程中，最后一个字符在模式中并未出现，那模式的长度就会被作为跳跃的步数，也就是决定了跳跃模板的长度。

如今所改进的算法在运算过程中的主要思想是：首先，我们在探究主要思想前，先假设模式的第一次匹配字符与最后一次匹配字符为变量x，在进行算法匹配时，如若出现不匹配，那就能够实现T[k+1]的判断。如若出现T[k+1]的判断结果，我们就可以将这一模式的移动距离设为c，与此同时，我们规定c=max{dist[t[k+1]],di st[T[a]]}+1, 在这一公式中，a 的含义与前文中所规定的相同，我们所规定的这一表达式主要是用于比对T[k+1]与dist[T[a]]的大小。在二者进行对比之后，就可以找到正文与模式的最大移动距离，进而来进行接下来的匹配。

在这一匹配过程当中，我们按照从右到左这样一种匹配模式来进行正文与模式之间的匹配，模式右边的字符匹配将会大于左边的字符匹配。如若在匹配过程中存在常模式这一特殊情况，在匹配过程当中，将其与左边不匹配的时候进行对比，会消耗更多的时间。为了节约时间，提高算法的匹配效率，我们可以运用上文所说的方法来进行匹配对比，删除或者是避免一些不必要的匹配过程，这样子的方式可以提高匹配的速度，减少匹配所要使用的时间，提高匹配的效率。

2.4 多模式匹配算法

计算机网络中的多模式匹配算法，也就是RAC 算法。该算法相比于其他算法的显著特征是指算法在预处理阶段总共包括三个函数，分别是无效函数、输出函数、和跳转函数。在该多模式匹配算法中，使用以上所说的三种函数对计算机网络进行匹配以及遍历。计算机网络中的这一多模式匹配算法是根据密钥控制模式是否置换来进行计算机网络的检测。多模式匹配算法的检测目标，主要依靠以下所说的方式来实现：在算法匹配开始之前，首先应当通过基数生成器来随机获得256 位随机数，这些随机数可能是1 也可能是0，我们通过采取这样的方式，来实现模式的有效控制。

若我们获得的随机数为1，并且我们所使用的模式的对应阶数是零，在这时，我们就会使零阶概率模式中的0、1 这两种符号他们所对应的概率值进行互换。如果当时使用的是1 阶模式，那么我们需要将与之对应的概率值进行交换。但是如若我们在选取随机数时，所获得的随机数为0，那么多模式就要按照正常多模式匹配模式来进行。在多模式匹配算法运用过程当中，我们可以发现，多模式匹配算法的匹配，信号符号之间的关联性较强，在匹配时能够采取大量记忆匹配，该匹配模式较以往的匹配算法来说，具有记忆性，这能够进一步提高匹配的效率。

2.5 改进的多模式匹配算法

针对多模式匹配算法中存在的问题，我们将多模式匹配算法进行了进一步的改进，提出了多模式匹配算法，也被称为NBM 算法。NBM 算法的核心思想是指如若模式串中的dm 个字符与文本串中三用的字符再进行匹配时，出现匹配失败这一情况，那么我们将按照bm 的算法向右滑过dist[c]=m-j 段距离；如若在匹配过程当中，并未出现匹配失败这一情况，那么需要考虑在模式串中是否出现了导致匹配失败的字符，考虑导致匹配失败的当前字符的下一个字符是否与模式串a 相等。如若相等的话，则需要将它们对齐，婴进而考虑下一个字符。如若不相等的话，则需要按照从右到左的顺序依次比较每个字符。

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

网络入侵检测系统能够实现执行数据包的深入检测，还能够对负载没有或者已经实现定义的规则集相互匹配模式串进行扫描，从而对其是否具有入侵检测事件进行检测。从理论方面进行分析，BM 算法比较严谨，但在实际应用过程中性能并不理想。因此要对好后缀规则中的不足进行修改。此实验需要测试的指标为：

（1）BM 和BMH 算法运行的时间。

（2）BM 和BMH 算法的字符比较数量。

（3）BM 算法中字符比较数量及使用好后缀规则数量。

因为入侵检测的模式串长度在20~30 字符。因此可以发现BM算法和BMH 算法的总字符数量相同，但是在时间复杂度方面，BMH 算法的性能更好。

改进算法的主要思想是大部分规则匹配内容后缀和前缀都相同，所以改进算法只要能够满足入侵检测系统模式匹配。单模式匹配算法及模式对其文本字符进行偏移量计算，另外就是通过下一个字符对偏移量进行计算。本文所改进的算法将两者相互结合，从而形成全新的算法。对算法的改进实现步骤主要分为两个阶段，第一阶段，预处理对两个字符集进行计算，得到计算结果，第二个阶段为初始位置及匹配方向，在开始匹配的时候要求模式串左端和待测文本左端相互对齐，字符对比通过模式串末端对齐，文本开始从右到左开始，如果匹配失败，模式串就要移动到右端。使用改进方法只移动了两次，一共匹配了三次，就能够寻找到模式串，说明本文所设计的改进方法能够提高预处理时间，并且计算方法比较简单，提高网络入侵检测系统处理性能，能满足大流量网络环境的需求，改进的匹配模式算法能够有效满足网络使用需求，提高系统检测的效率。

4 小结

如今我们正处于一个信息化时代，网络化以及信息化的快速发展，指的我们当前的生活以及工作已经离不开计算机网络，计算机已经成为我们生活和工作必不可少的一部分。计算机网络的应用进一步提高了我们的工作效率，但是与此同时，计算机网络的应用也有这一定的安全隐患，计算机网络的安全性不能够得到充分保障，常会受到一些网络攻击或是网络入侵。网络入侵检测系统的应用，能够帮助提高计算机网络的安全性，而匹配算法又是计算机检测系统的重要组成部分，匹配算法的优化以及提升能够使得计算机网络入侵检测系统的性能更加完善。