入侵检测系统中模式匹配算法的研究

闫宏丽 赵丽

摘要：结合模式匹配的概念，提出模式匹配在入侵检测系统中使用的原理及特点在分析了常见的单模式匹配和多模式匹配算法之后，将模式匹配方法应用在误用入侵检测系统中，去完成对已知攻击的检测.基于模式匹配的入侵检测系统具有较低的虚警率，但要想提高入侵检测系统的性能，必须对模式匹配算法做进一步的改进

关键词：入侵检测;模式匹配;误用入侵检测;攻击;虚警率

中图分类号：TP393

文献标识码：A

文章编号：1006-8228（2020）09-81-03

Research on pattern matching algorithm in intrusion detection system

Yan Hongli， Zhao Li

（School of Information Technology and Engineering， Jinzhong University，Jinzhong，Shanxi 010619，China）

Abstract： Combined with the concept of pattern matching， the principle and characteristics of pattern matching used in intrusiondetection system are put forward. After analyzing comrrion single-mode matching and multi-mode matching algorithms， the patternmatching method is applied to the misuse intrusion detection system to complete the detection of known attacks. The intrusiondetection system based on pattern matching has low false positive rate. but in order to improve the performance of intrusiondetection system， the pattern matching algorithm must be further improved.

Key words： intrusion detection; pattern matching; misuse intrusion detection; attack; false positive rate

0引言

根據检测方法不同，入侵检测系统可以分为误用入侵检测系统和异常检测系统。在误用检测系统中，模式匹配算法由于其方法简单、易于实现而受到较多关注。模式匹配检测技术主要优点是检测过程简单，无须训练，检测效率高，一般情况下不存在误检测。因此模式匹配在网络入侵检测中有着非常重要的影响。

1模式匹配

1.1模式匹配的概念

模式匹配是指：已知一长度为n的文本字符串T=T1T2…Tn，和一长度为m（m≤n）的模式字符串P=P1P2…Pm，看T中是否存在长度为m的子串。

模式匹配系统主要是用一定的模式描述来提取攻击的主要特征，其基本任务就是把存放在入侵检测规则集中的已知入侵模式与系统正在检测的网络包或者重构的TCP流中的文本进行匹配，如果匹配成功，则可以断定发生了入侵。这个过程是不断循环前进的。

1.2模式匹配原理

模式匹配是由入侵检测领域的大师Kumar在1995年提出的，首先，Kumar提出了入侵信号的层次性概念。依据底层的审计事件，可以从中提取出高层的事件;由高层的事件构成入侵信号，并依照高层事件之间的结构关系，划分入侵信号的抽象层次并对其分类。其次，Kumar将入侵信号分成四个层次，每一层对应相应的匹配模式。

（1）存在（Existence）

这种入侵信号表示只要存在这样一种审计事件就足以说明发生了入侵行为或入侵企图，它所对应的匹配模式称为存在模式（ Existence Pattern）。存在模式可以理解为在一个固定的时间对系统的某些状态进行检查，并对系统的状态进行判定。

（2）序列（ Sequence）

有些入侵是由一些按照一定顺序发生的行为所组成的，它具体可以表现为一组事件的序列。其对应的模式就是序列模式（Sequence Pattern）。序列模式在检测入侵时需要特别关注间隔和持续时间。

（3）规则表示（Regular Expressions）

规则表示模式（Regular Expressions Patterns）是指用一种扩展的规则表达式方式构造匹配模式，规则表达式是由用AND逻辑表达式连接一些描述事件的原语构成的。适用这种模式的攻击信号通常由一些相关的活动组成，而这些活动间没有什么事件顺序的关系。

（4）其他

其他模式（ Other Pattern）是指一些不能用前面的方法进行表示的攻击。

在具体的实现中，很难做到对所有入侵信号进行模式匹配，一般只是部分实现。

1.3模式匹配系统的特点

把攻击信号看成一种模式进行匹配检测有以下一些特点。

（1）事件来源独立：模式的描述并不包含对事件来源的描述，模式只需要了解事件可以提供什么数据，而不管事件如何提供这些数据。

（2）描述和匹配相分离：描述入侵信号的模式主要是定义什么需要匹配，而不是如何去匹配。

（3）动态的模式生成：描述攻击的模式可以在需要的时候被动态生成。

（4）可移植性：入侵模式可以被轻易地移植，而不需要重新生成。

2常用的模式匹配算法

2.1单模式匹配

单模式匹配算法：对文本T的一次扫描，只能处理一个模式串。

（1） Brute Force算法

此算法的实质是将模式P和文本T从左到右逐个搜索，若在某一位匹配失败，则将模式P向右移动一位，仍从模式P的第一位开始搜索，直到将文本T搜索完为止。在最坏的情况下，要执行（n-m+l）×m次字母的匹配，因此，其时间复杂度为O（m×n）。所以，当n不大时，可以采用这种算法。

（2） KMP算法[1]

Brute Force搜索算法在一次字符比较失败后，只是简单地把模式向右移动一个字符位置。这样做的缺点是完全丢弃了前面已经做过的字符匹配中得到的信息，实际上这些匹配信息是可以利用的。

KMP算法是Knuth，Morris，Pratt提出的。和簡单算法不同，当某次匹配不成功时，模式串不一定只能右移一格，右移后也不一定必须从模式起点处开始匹配。具体算法描述如下。

在某次试匹配成功时，若Tj≠Pj，即模式的前j-l个字符全能匹配，如果事先知道子模式P1P2……Pj-1有一个最长的真首子串和它的尾子串相等，即P1P2……Pk-1=Pj-k+1Pj-k+2……Pj-1，那么，下一次试匹配时，就可把模式串右移next[j]位置，next[j]表示当模式串中第j个字符与主串中相应字符“失配”时，在模式中需重新和主串中该字符进行比较的字符的位置。next[j]可以在预处理时计算。

为了不遗漏可能完全匹配的情况，上述的真首子串必须是最长的。故对于任—个子模式P1P2……Pj（1≤j≤n），“自匹配”的真首子串是唯一的，它只和模式自身的结构有关。

KMP算法采取的方法是一次把模式向右移动多个位置，这就使得在匹配过程中完全不需要回溯。在最好的情况下，KMP算法的时间复杂度为O（n+m）。计算next[j]的时间复杂度为O（m）。

（3） Boyer_Moore（BM）算法[2]

①匹配自右向左进行;

②若匹配失败发生在Pi≠Ti，且Ti不出现在模式P中，则将模式右移直到Pi位于匹配失败位Ti的右边第一位（即Ti+1位），若Ti在P中有若干地方出现，则应选择j=max{k|Pk=Ti};

③模式P后面K位和文本T中一致的部分，有一部分在T中其他地方出现，则可以将T向右移动，直接使这部分对齐，且要求这部分尽可能的大。

BM算法采用“跳跃式”查找策略，在多数情况下不需要对文本进行一次完整的扫描，其时间复杂度为O（n/m）。

2.2多模式匹配

多模式匹配算法：对文本T的一次扫描，能够同时处理多个模式串的集合。

（1） Aho_Corasick（AC）算法[3]

AC算法是同时搜索多个模式的经典算法。AC算法使用了有限状态自动机的结构来接收集合中所有的字符串。自动机是结构化的，这样每个前缀都可用惟一的状态来标识，甚至是那些多个模式的前缀。当文本中下一个字符不是模式中预期的，则会有一条失败链指向那个状态，代表最长的模式前缀，同时也是当前状态的相应后缀。AC算法的复杂性是O（n），预处理阶段的复杂性是O（m）。

在用AC算法构造的有限状态自动机中，可以发现这样一个现象：离自动机根较近的地方，结点比较密集，即这时自动机的各个分枝中的结点都比较密集;相反，离根越远，结点越稀疏，这是由于模式串的长度不同而引起的。在AC算法中，要为每一个模式串的每一个字符建立一个结点，这样无疑算法空间使用很多，为了压缩AC算法的空间使用率，可以将稀疏的结点合并成一个结点，即AC-Path算法。但是AC-Path算法在节省了空间的同时，却也增加了模式匹配时的难度，其运行所需要的时间也随之增加。

（2） Wu-Manber（WM）算法[4]

Wu-Manber算法是BM算法处理多模式匹配问题的派生形式，是一种快速实用的多模式匹配算法。它采用了BM算法的基本框架，但不同于BM，它不是使用一个字符来计算坏字符移动的距离表，而是使用块字符来计算坏字符移动的距离表（shift[]）。此外，在进行模式匹配时它使用哈希表选择模式串集合中的一个子集与当前的文本进行匹配，以减少无谓的匹配运算。Wu-Manber算法不会随着模式串集合的增加而成比例的增长，而且远少于使用每一个模式和BM算法对文本进行匹配的时间总和。Wu-Manber算法的时间复杂度在最好的情况下能达到O（B×n/m）（B是块字符的长度，是算法在每一个入口点计算块字符的时间）。

3模式匹配系统的具体实现

（1）模式的提取：必须使提取的模式具有很高的质量，能够充分表示入侵信号的特征，同时模式之间不能有冲突。

（2）匹配模式的动态增加和删除：为了适应不断变化的攻击手段，匹配模式必须具有动态变更的能力。

（3）增量匹配和优先级匹配：在事件流对系统处理能力产生很大压力的时候，要求系统采取增量匹配的方法来提高系统效率，或者可以对高优先级的事件先行处理，暂缓对低优先级事件的处理。

（4）完全匹配：匹配机制必须能够提供对所有模式进行匹配的能力。

4结束语

之前的调查结果表明[5]，基于模式匹配的入侵检测系统中，30%的处理时间都在进行模式匹配，除了运行时间，网络入侵检测系统同时需要较小的内存空间，所以需要找到一种好的模式匹配算法[6]，才能更好地提高入侵检测系统的性能。

参考文献（References）：

[1]D.E. Knuth.J. H.Morris，V.R.Pratt. Fast pattern matching instrings[J]. SIAM J.Comput，1977.6（2）：323-350

[2] R.S. Boyer. A Fast String SerachingAlgorithm[J].Communication of the ACM，1977.20（10）：762-772

[3]Aho A，Corasick M.Efficientstring matching： an aid tobibliographic search[J]. Communications of the ACM，1975.18（6）：33-40

[4]S. Wu and U.Manber.A fast algorithm for muti-patternsearching. Department of Computer Science， universityof Arizona， Tucscn， Az. Rep. Tr-94-17，1994.

[5]M. Roesch， Snort： Lightweight intrusion detection fornetworks. In Proceedings ofthe 1999 USENIX LISASystems Administration Conference[C].

[6]赵丽.面向入侵检测的高效模式匹配算法研究[J].计算机与数字工程，2017.45（8）：1592-1596

收稿日期：2020-04-23

基金项目：晋中学院“1331工程”创客团队（jzxycktd2019029）; 2018晋中学院优秀教学团队（2018）

作者简介：闫宏丽（1971-），女，山西晋中人，实验师，主要研究方向：计算机网络。

通讯作者：赵丽（1973-），女，山西晋中人，硕士，副教授，主要研究方向：计算机网络，网络安全。