网络技术的发展带来便利的同时也带来了巨大的安全隐患, 尤其是Internet和企业Intranet的飞速发展对网络安全提出了前所未有的挑战。入侵检测技术是对系统的运行状态进行检测, 从而发现各种攻击企图, 攻击行为或者攻击结果, 以保证系统资源的机密性、完整性与可用性。模式匹配 (BM) 算法是基于特征匹配的入侵检测系统中的核心算法, 模式匹配是基于攻击特征的网络数据包分析技术。
1 模式匹配 (BM) 算法
1.1 BM算法
BM算法在两个数额中选取较大的一个作为滑动距离。按照从右向左的顺序进行匹配的, 不失一般性, 可设模式串第一个字符P1与Ts+1对齐, s为模式串在主串中的位置。匹配先从模式P的最右端字符开始, 判断Pm是否与Ts+m相等, 如果匹配成功, 则向左继续进行匹配, 判断Pm-1是否与Ts+m-1相等。直到P全部匹配成功或者是有不匹配的情况出现。当不匹配时, 用两种启发性方法分别计算右移量, 并取较大值作为滑动距离。
1.2 BM算法的缺陷
对模式串P=“abeabd”和文本串T=“abfabddadcbdabeabd”, 用BM模式匹配算法进行匹配的过程 (下划线为失配的地方) (如表1) 。
首先比较的字符是模式串中最右边的字符, 当比较至P[3]与T[3]时出现不匹配, 此时模式串P应向右滑动一段距离。根据坏字符启发性方法, 因T[3]=“f”没在模式中出现, 应该将P滑动至和“f”的下一位对齐。
但是通过对已知信息的分析发现, 在T[3]失配前已比较的子串为“abd”, 而根据坏字符启发性方法, 失配后这三个字符应与模式P的前三个字符相对齐。又已知模式串的前三字符为“abe”, 与此子串不相++++匹配。因此可以考虑根据已知信息将模式串尽可能的向后移动一段距离。针对BM算法的这一缺点, 对坏字符启发性方法加以改进, 来进一步提高BM算法的效率。
2 BM算法改进
定义1:如果有串Q和串R, 使得Q与R左对齐时每一对对齐字符均是匹配的, 并且Q是长度小于R, 则Q与R左匹配, 并且称Q是R的左子串。即Q在模式R的最左端出现。
定义2:如果有串Q和串R, 使得Q与R右对齐时每一个对对齐字符均是匹配的;并且Q的长度小于R, 则Q与R右匹配, 并且称Q是R的右子串。
对坏字符启发性方法的改进是:首先为模式串中每个可能的失配位置, 计算其在模式串中的最长左子串长度存放在一维数组π[m]中, 如对模式串P=“abababa”, 计算其最长左子串数组为“5533110”。
改进后的坏字符方法执行如下:首先计算出模式串的最长左子串数组π[m]。假设当失配出现在位置j, 即P[j]≠T[s+j], (1≤j≤m) 。并且失配时主串中的字符在模式串中未出现 (原坏字符方法的第一种情况) , 则可以根据π[j]的值来决定右移量, 右移分为以下二种情况。
π[j]=0:若v是模式P的左子串 (length (v) ) ∈[1-m-j]) , u是已成功匹配的字符串则v与u右匹配的长度为0。即当v的长度在[1, m-j]范围内时, v都不能u右匹配。这种情况下可以安全地把s增加m。
π[j]>0:若v是模式P的左子串 (length (v) ∈[1, m-j]) , u是已成功匹配的字符串, 则v与u右匹配的最大长度为π[j]。这种情况下可以安全地把s增加m-π[j]。移动后v与u右对齐。
对上例采用改进的BM算法, 其模式串P=“abeabd”, 计算其最长左子串数组π[m]=“000000”, 因为模式串不存在最长左子串, 所以每次失配时跳跃的长度都为m (如表2) 。
3 改进BM算法的测试及比较
为了避免理论与实际情况的差异, 选用衡量算法的主要指标——运行时间。改进的BM算法明显优于BM算法, 特别当模式串长度较短时, 改进的BM算法相对于BM算法在模式匹配的效率有明显的提高。实验结果表明该算法优于BM算法, 特别是在模式串长度较短的情况下能够有效地提高匹配的效率。
预处理阶段时间和空间复杂度为O (m+σ) ;搜索阶段时间复杂度为O (mn) 。
摘要：入侵检测 (IDS) 是网络安全方面的一个重要技术, 模式匹配的效率决定了入侵检测的效率, 在入侵检测中起到了重要的作用。为提高匹配速度, 提出了一个改进的BM串匹配算法, 通过测试证明可大大提高算法效率。
关键词：入侵检测,模式匹配,匹配算法
参考文献
[1] 杨武, 方滨兴, 云晓春, 等.入侵检测系统中高效模式匹配算法的研究[J].计算机工程, 2004, 3 (13) :96～98.
[2] 宋明秋, 张国权, 邓贵仕.IDS中新的快速多模式匹配算法及其设计[J].计算机工程与应用, 2005 (21) :159～162.
[3] Norton M.Roelker D Hi-perform ance Multi—rule Inspection Engine[Z]http://www.snort.org, 004—04.