基于AC-BM改进算法的入侵检测技术研究论文
摘 要：网络的飞速发展带来了诸多安全隐患，入侵检测技术作为一种积极防御手段成为了网络安全领域的研究热点。模式匹配由于原理简单、无需训练、检测效率高、扩展性好广泛用于目前的入侵检测系统。本文首先分析了模式匹配，比较了经典的模式匹配算法，总结了其存在的问题，并在此基础上对AC-BM模式匹配算法进行优化，提出了AC-BM改进算法，有效提高了检测效率，降低了检测过程中的资源消耗。
关键词：入侵检测 模式匹配 AC-BM改进算法 检测效率
随着网络的日新月异，网络入侵行为变得越来越复杂，因此网络安全也日益受到人们广泛关注。入侵检测系统能够在不影响网络正常工作的前提下，对网络数据进行监测、收集和分析，进而从中发现是否存在入侵行为 [1]。根据入侵检测方法的不同，可以分为异常检测技术和误用检测技术。误用检测技术存在一个已知攻击模式特征库，通过网络数据与库中攻击模式进行匹配来判断是否存在入侵行为，其检测的误报率较低。误用检测中使用的检测技术主要有模式匹配、专家系统、状态转移等，而模式匹配由于原理简单、可扩展性好等特点被广泛应用[2]。网络数据包的高速传输使得模式匹配算法应用于入侵检测领域面临了诸多问题，模式匹配的效率将直接影响入侵检测的性能。
1 模式匹配
模式匹配是指：已知一长度为n的文本字符串T=T1T2….Tn和一长度为t (t
目前的模式匹配算法多分为单模式匹配和多模式匹配[3]。若每次文本串只能对一种模式串进行模式匹配，这种方法称为单模式匹配算法。即己知文本串Text=T[l...n]和模式串Pattern=P[l...t]，对于1<=f<=n，存在T[f+1...f+t]=P[1…t]。
网络入侵类型日益复杂，为了提高匹配速度期望可以实现每次可以同时对多个模式进行匹配，这种方法称为多模式匹配方法。也就是说，文本字符串Text=T[l...n]对模式树进行扫描时，至少在模式树种发现其中一个模式串与之相匹配。
2 应用于入侵检测的经典模式匹配算法
2.1 BM算法[4]
BM基本思想是进行匹配时，将文本字符串和模式串左边对齐，然后从右向左进行字符比较。如果字符匹配，则继续进行下一次比较;若模式字符P[k]和文本字符串T[i+k]文本字符串不匹配，此时分别计算Goodsuffix[k]和Badchar[T[i+k]]-(m-k) 两个函数值中更大的那个作为偏移量，文本字符串指针向右移动偏移量的长度，进而重新开始匹配。此外，若找到了模式串在文本字符串中出现过一次，则文本字符串向右移动Goodsuffix[0]的距离。一直进行下去直到找出模式串所有可能出现的位置。
2.2 AC算法[5]
AC算法巧妙地将字符比较转化为了状态转移。AC算法有以下两个特点：一是扫描字符时不需要回溯;二是时间复杂度为O(n)，与模式的数目和长度无关。
该方法的核心思想是在AC算法匹配开始之前，首先建立转向函数goto()，失效函数failure()和输出函数output()，在此基础上构建出树形状态机。在扫描匹配阶段，AC算法采用以上三个函数扫描文本字符串，从而搜索岛模式串在文本字符串中所有出现的位置。
2.3 AC-BM算法[6]
AC-BM 算法的模式树从文本右端向左边移动，每一次匹配时字符从左到右进行比较，AC-BM算法同时使用坏字符移动规则和好前缀移动规则。
坏字符移动：如果模式串与文本字符串不匹配，则移动模式树中其他模式分支和当前比较字符相同的那个字符的位置。如果在当前深度上，模式树中的任何一个模式分支在文本字符串中都没有出现，则模式树的移动偏移量等于模式书中最短的模式分支的长度min l。
好前缀移动：移动模式树，使其与已经匹配成功另一个模式分支的完全前缀的后一位置处，也可以是移动到模式树中的另一个模式分支的后缀可以匹配成功文本的前缀的后一位置。需要注意的是，移动模式树时，其移动偏移量必须小于模式树中最短模式分支的长度min l。
3 改进的AC-BM算法
AC-BM算法结合了AC算法和BM算法的优点，允许将不同模式放在一棵模式树上同时进行搜索匹配。但AC-BM算法仍旧存在一些问题。一是每一次模式串的移动距离必须小于模式树中模式分支的最短长度 min l。二是AC-BM算法沿用了BM算法坏字符移动和好前缀移动，但好前缀规则预处理阶段过程比较复杂，并且难以实现。三是每一次的匹配都对所有字符进行一一比较，即便是有些字符在模式树中没有出现过也要进行比较，并且模式树的跳跃距离是根据匹配过程中单个“坏字符”决定的，但这些坏字符在下一轮匹配中却不一定能匹配成功。四是AC-BM算法的每次匹配都是从左往右，因此可能出现模式串和文本字符串的相当一部分前缀一致，但最后极少数后缀不同时还是需要进行很多次字符比较的浪费。
基于以上缺点，并结合AC-BM算法自身特点，主要考虑从加大算法跳跃距离和减少每轮匹配字符比较次数两方面对其进行改进。
3.1 改进算法描述
为了避免匹配过程中坏字符存在于文本串最后几个字符，使之前的字符比较都是浪费的情况，AC-BM改进算法在每次匹配开始前，首先检验待匹配文本串的最后两个字
本文标签：