探讨入侵检测系统中模式匹配算法的研究与实现

摘要：随着我国科学技术的不断发展，计算机与网络的应用越来越广泛，但是随之而来的网络安全问题已不容忽视。随着攻击手段与方法的日益复杂，传统的静态防御技术已经明显落后。本文结合当前计算机发展实际，对入侵检测系统（Intrusion Detection System）以及相关模式匹配算法进行分析与阐述。

关键词：入侵检测系统；模式匹配；实现

中图分类号：TP393.08 文献标识码：A 文章编号：1007-9599 (2011) 21-0000-02

Pattern Matching Algorithm Study&Achievement in Intrusion Ddetection System

Wan Shuyi

(HeFei University of Technology,Information and Network Center,Hefei 230001,China)

Abstract:With the continuous development of China's science and technology,computers and networks more widely,but the ensuing network security issues can not be ignored.With the means and methods of attack increasingly complex,the traditional static defense technology has lagged behind.In this paper,the actual development of the current computer,the intrusion detection system(Intrusion Detection System)and related analysis and pattern matching algorithms described.

Keywords:Intrusion detection system;Pattern matching;Achievement

随着我国互联网技术的飞速发展，网络安全问题受到前所未有的关注。网络安全问题的主要来源之一就是网络给信息系统造成的入侵破坏。据相关数据统计分析，目前我国大多数网络存在安全隐患，其中20%属于较为严重的网络安全问题。另外，每年利用计算机网络产生的违法行为日益增加，尤其黑客攻击越来越猖獗。入侵检测作为一种全新防护方法，是一项动态、实时技术，对人为误操作、外部入侵、内部攻击等行为进行监控，实时保护计算机系统，实现网络系统的危害拦截。自上世纪90年代开始，入侵检测系统纷繁出现，逐渐朝向分布式、智能化方向发展。但是以目前入侵检测技术的应用状况来看，存在较多问题，这些问题直接影响了入侵检测系统的安全防御手段。虽然目前使用的大多数科研成果都应用了神经网络、数据挖掘、人工智能等高科技算法，但是算法相对复杂，对设备提出了较高要求，再加上报警系统不完善，没有实现全面推广。

一种基于模式匹配算法的入侵检测系统，实现了网络数据包和入侵规则库的特征匹配，通过协议分析技术，提高入侵分析的效率与质量，通过协议分析，将冗余数据过滤，并在规则树种交叉体现，提高深度。一旦检测到数据库中已知的匹配攻击事件或网络异常行为，就可以自动对比攻击行为资料库，同时进行跟踪、记录、攻击封包、拦截等作用；当侦测到具体的攻击事件，系统就会通过简单网络管理协议（SNMP）、电子邮件等方式通知管理者，并显示具体的攻击方式、连接IP以及相关封包等内容，由系统发出报警，做出及时反应。以下将对匹配算法在入侵检测系统中的应用相关问题进行具体分析：

一、模式匹配算法的现状

以我国当前入侵检测系统的发展状况来看，模式匹配算法是较常用的算法之一。由于当前入侵检测及时，主要通过检测访问行为、应用检测系统数据库的相关规则来比较、判断是否存在入侵行为，因此，涉及到大量的字符串模式匹配问题。最初，入侵检测系统应用的BF算法较为简单，且数据包匹配效率较低，已经无法符合当前入侵行为的复杂性，失去了对网络系统的监控意义。因此，对更高效、更快捷的匹配算法提出了需求。1999年，一种开源入侵系统（Snort）中，开始应用BM算法，极大提高了检测效率与检测精准性，此后使用的各种入侵检测产品，大多应用BM算法或者建立在BM基础上的优化改进算法，如QS、BMH等。

目前，有关模式匹配算法的研究主要集中于对比各种算法、优化测试及改进等方面，一般认为最具代表性的就是改进BM串的匹配算法，即NEWBM算法。在该算法中，继承了BM算法的各种优势，通过优化与改进，在模式匹配过程中，采取逐位匹配顺序，提高匹配效率与质量。有关BM的改进算法，还可以在某一次匹配失败之后，通过启发特殊位置字符，获得字符串前后移动位置的可能距离，一般情况下，根据定义的统一函数发出，取其中最大值，作为字符串向后方移动的真实距离，进而确保匹配速度。

根据数理统计抽样思路与原则，改善字符串匹配算法。这种算法根据模式字符串的实际长度，在文本中街区固定字符，作为抽样点，然后判断该抽样点是否在模式中出现，从中将抽样点分离出来，完成抽样点周围的精确匹配，也可在一定程度上确保匹配质量。

二、模式匹配算法的实现形式

对于入侵检测系统来说，模式匹配算法是必不可少的因素之一。模式匹配算法的应用效果，直接影响系统的快捷性、精准性，假设P为模式、长度为m；T为进行匹配的文本，长度为n。以下将对四种常用模式匹配算法在入侵检测系统中的应用进行分析；

（一）BM算法

BM算法是一种最基本、最简单、最常用的单模式字符串匹配算法，随后发展的大多数入侵检测模式匹配算法都是建立在BM算法基础上。应用BM算法，主要具备以下四方面特点：①模式和文本的匹配按照从右向左的顺序进行。实现P和T的左端对齐，即P1和T1对齐。首先从P的右端字符开始匹配，判断Pm和Tm是否匹配。如果匹配成功，则可向右移动，继续判断Pm-1和Tm-1是否匹配，持续循环，直到模式中所有字符匹配成功；②坏字符的移动。在BM算法中，可对模式进行预处理，获得启发信息，并利用相关信息计算向右移动P的距离，这一移动函数主要针对某个字符。

当P中不含有c字符

当Pj=c，j为最大整数（且1≤j≤m）

③好后缀移动。在该移动函数中，主要针对某个子串，而模式的预处理中，算法如果发现了P中包含的某个字符字串，就会在T中寻找该字符可能出现的下一个位置，并将P移动到此位置，确保字符字串和T相关的字符字串对齐。④如果模式和文本不匹配，结合坏字符移动函数及好后缀移动函数来计算，取二者最大值。

（二）AC算法

AC算法可以同时搜索多个模式，应用有限自动机结构，接收字符串。由于自动机结构的特殊性，每一个前缀都可采取唯一标识进行标志，也可实现多个模式串的共同前缀。通过应用AC算法，主要从以下几方面做出改进，优化了系统的运行：①可同时支持各种确定型及不确定型的有限状态自动机；②采取线性链表方式，将状态转移表初始化；③在系统执行过程中，各种确定型与不确定型的有限状态自动机，将状态转换机转变为权矩阵形式，减少内存的不必要消耗；④在任意状态转移链表中，增设布尔型变量，以此表示状态中是否存在匹配模式。

（三）MWM算法

MWM算法可以实现多个模式、多模式匹配的同时搜索，支持较大数量下的模式集合。该算法集成了BM算法中有关坏字符的移动思路，可分为预处理阶段、搜索扫描两种算法。在预处理阶段，先对模式集合执行预处理，将处理结果存入内存或者文件，同时创设移动表、前缀表、哈希表。移动表和BM算法中的移动表相似但是也有所区别，当对文本搜索扫描时，利用移动表决定模式的移动距离，如果移动表值是0，就可以借助哈希表与前缀表来最终确定匹配模式。在搜索阶段，为了避免模式和文本的结合过程中每一个模式都实现匹配，算法可利用哈希技术选择文本匹配，减少不必要的匹配运算。如果哈希表发生冲突，那么该算法就可以凭借前缀表的继续匹配过程。

（四）EXB算法

EXB是一种基于排除法的字符串匹配算法，可以较快速地排除数据包中没有的匹配模式串数据包。这种算法的思想较为简单，假设检测的字符I中含有一个小子串S，如果S中具有至少一个字符不属于I范围内，那么S就不属于I的子串。为了降低匹配的错误率，可以将此算法扩展到字符对中。在匹配过程中，既要检测S中的任意字符是否在I中出现，还要检测任意字符对重字符出现的正确顺序。为了提高判断特定字符c是否属于字符串I中的效率，这种算法又应用了“出现图”方法。在对字符串I进行预处理时，对于其中产生的字符c，在出现图的位置采取二进制值，0代表c不属于I，1代表c不属于I。对于所有全新数据包来说，出现图的清零工作量比较大，为了减少时间的浪费，可根据数据包序列号代替二进制值，明确标记出现图的位置，有效提高计算效率。

三、入侵检测系统的发展趋势

随着匹配算法的不断完善，进一步提高了入侵检测系统的功能。从当前网络应用状况来看，入侵检测系统呈以下几种发展趋势：

（一）标准化

目前，我国有关入侵检测系统的设置还缺乏一定标准。对于不同的入侵检测系统来说，无法支持数据交换与信息通信等功能。虽然目前IETF和DARPA的入侵检测工作组已经开始筹划有关入侵检测系统的标准工作，并开始建立IDMEF标准和CIDF标准，从通信机制、体系结构、消息格式等方面加强入侵检测系统的规范发展，但是进程较为缓慢，目前尚未广泛接受并全面推广。因此，具备标准化结构的入侵检测系统，将成为未来发展趋势。

（二）安全化

要求系统提高安全意识，积极采取各种安全防护技术与手段，加强对入侵检测系统自身攻击的防范。

（三）综合化

与传统的静态入侵检测方式相结合，包括加强和电子交易安全技术、防火墙、身份验证等网络安全和电子商务技术相结合，为网络运行的安全提供保障。

（四）集成化

鉴于主机系统的入侵检测技术和鉴于网络系统的入侵检测技术各具利弊。在今后的入侵检测技术发展中，应将主机与网络相结合。由于主机入侵检测系统可以很好地适应交换环境，实现用户的自定义配置，并对加密信息包进行处理；而网络入侵检测系统可以对数据包的字段位、负载等进行分析，检测到各种形式的TCP/IP协议攻击方式，在今后的入侵检测系统发展中，可以实现二者的有机结合，并提供有关攻击检测、签名、报告等关联功能。

参考文献：

[1]黎幸子.用于SIP滥用检测的入侵检测系统的设计与实现[J].北京邮电大学:信号与信息处理,2009

[2]李莎.神经网络与模式匹配相结合的入侵检测系统的研究[D].太原理工大学,2010

[3]卢汪节,鞠时光.入侵检测系统中一种改进的AC算法[J].计算机工程与应用,2006,15

[4]吴绍根,李洛.入侵检测系统中模式匹配自动机的构造研究[J].微型电脑应用,2006,5

[5]薛传庆,韩明畅,金伟信.入侵检测系统中BM算法的改进[J].计算机技术与发展,2011,6

[6]盛志伟,朱清新.最优搜索理论在入侵检测系统中的应用研究[J].计算机应用与软件,2008,5

[7]朱俊,侯整风,曹亚群.模式匹配算法在IDS中的应用[J].合肥学院学报(自然科学版),2010,3

[8]郭浩,汪学明.入侵检测系统误报率和漏报率的改善方法研究[J].科技经济市场,2009,6