论文部分内容阅读
摘要:该文在介绍了入侵检测技术以及相关的模式匹配算法后,提出了一种改进的BM匹配入侵检测算法XBM,提高了匹配的效率,增强了入侵检测系统的性能。
关键词:XBM;入侵检测;模式匹配
中图分类号:TP301文献标识码:A文章编号:1009-3044(2010)22-6198-03
当前的入侵检测还有一些不足之处,而模式匹配技术在入侵检测中占有重要的地位,所以提高模式匹配的效率是改善入侵检测算法的关键。在介绍了入侵检测技术的不足之后,本文将会详细介绍以BM算法为主的模式匹配算法,然后对其改进,提出一种改进的NBM算法,在时间复杂度和空间复杂度上提高了模式匹配的效率。
1 当前入侵检测的不足
入侵检测系统的不足之处主要表现在以下几个方面[1]:
1) 误报漏报比较多。入侵检测系统中对入侵数据的研究尚不足,因此在实际应用中会有比较高的误报和漏报率。2) 模式特征的问题。很多入侵检测系统都使用模式匹配的方法进行分析,但是特征的匹配存在效率和效果的矛盾。3) 加密网络的问题。目前的入侵检测系统还难以处理经过加密的会话,虽然已经存在不少入侵检测方法,但是将它们有效地用在处理加密会话的入侵检测中还比较困难。
针对以上不足之处,有必要对模式匹配算法进行分析和改进。
2 BM模式匹配算法
从本质上讲,模式匹配技术是一种攻击判别技术,它分析入侵行为,并从中抽取某些特征或表达,建立一种攻击行为模型,然后依据这种行为模型所代表的攻击意图的行为特征来判断它是否属于攻击行为。
传统的模式匹配算法采用的是单字符移动方式,即模式串每和文本串匹配一次,都仅仅移动一个字符,这样大大降低了查找的速度;另外,模式串与文本串每次对齐后都要进行全部字符的匹配,经常出现前面多数字符匹配而后面少量字符不匹配的情况,大大降低了匹配的效率。
BM(Boyer-Moore)算法是一种经典的字符串模式匹配方法,有效解决了上述问题。在进行模式匹配的时候,先对模式串进行预处理,找到不匹配时文本串指针的偏移值,然后“将模式串和文本串的左侧对齐,接着从右向左将模式串的字符与文本串的字符进行比较,如果完全匹配,就成功退出;如果比较中出现不匹配的情况,则计算模式串右移的距离,把模式串向右移动该距离,然后开始新一轮的比较[2]”。
针对单个字符移动的问题,BM模式匹配算法提供了两个解决问题的规则:好后缀规则和坏字符启发规则。
坏字符启发规则使用模式串中的失配字符作为判断标准,如果失配字符存在于模式串当中,那么就用这个失配字符和文本串中的坏字对齐;如果失配字符不在模式串当中,那么只有在文本串坏字之后的字串中才能找到能够和模式串相匹配的字符,因此直接将模式串移动到文本串坏字后面即可,不必仅仅移动单个字符,例子如下:
文本串T:e c d a b d c a d b
模式串P:e c b a b (1)
e c b a b (2)
假设位移函数是skip(b),而且当模式串中第j个字符等于b时,skip=m-j;可以发现上面的例子中失配字符是b(下划线),在模式串中第3个位置(j=3),而模式串长度m=5,所以移动距离m-j=2。将模式串向右移动两个字符后如式2所示,此时刚好将模式串中的失配字符b匹配了文本串中的字符b。
另外,当模式串中不含有b,则此时的位移函数skip=m;
文本串T:e c d a b d c a d b
模式串P:e c a c c (1)
e c a c c (2)
由于模式串中并不含有失配字符b,所以将模式串向右移动5(模式串长度)个字符,就把模式串移动到了坏字之后。
与坏字符启发规则不同的是,好后缀启发规则使用模式中已匹配的字段与文本串进行对齐,而且模式匹配中已经匹配字段的判断是从右向左进行的。
由BM算法的原理我们可以知道,BM模式匹配算法用到了上次匹配的结果,因此在一定程度上提高了模式匹配的效率;但也应该注意的是,在BM模式匹配过程中,很少用到好后缀规则,并且好后缀规则的使用没有规律性,反而增加了算法的时间开销:预处理阶段中,计算好后缀数组的过程其实也是在进行模式匹配;查找阶段进行的比较坏字符数组和好后缀数组的过程也增加了计算复杂性,因此有必要对BM匹配算法进行改进,并结合入侵检测算法的不足,将BM匹配算法用于入侵检测中。
3 改进的BM匹配算法
3.1 改进的BM匹配算法
分析一下BM匹配算法中的好后缀规则,我们可以发现它的一些不足之处[3]:
1) BM匹配算法中的好后缀规则本质上也是一种模式匹配算法,因此如果模式串的长度比较大,那么随后的匹配运算量会越来越大,也会耗费更多的时间。
2) 即使是比较短的模式串,也会因为字符较少而移动超过模式长度的距离,从而无法体现好后缀规则的优势。
3) 与坏字符规则不同的是,好后缀规则要求至少有一个以上的字符匹配,事实上好后缀形成的几率很小,所以匹配过程中好后缀使用的机会也比较少。
基于好后缀规则的这三个不利之处,本文对其进行改进后提出一种改进的BM匹配入侵检测算法,将存在不足之处的好后缀规则去掉的同时也改进了坏字符启发规则,从而使得模式匹配算法更加高效。
由于收集到的入侵检测特征库中的很多规则都会有部分前缀或者后缀相同,在匹配过程中必然会有不必要的比较,因此可以在匹配顺序上有所改进;另外,有的模式匹配算法会从模式串与文本串对其的字符处开始计算位移量,而有的算法会从下一个字符开始计算,因此也可以将这两种偏移量计算方法结合起来,形成一种改进的XBM模式匹配方法。
改进的模式匹配方法主要分预处理和初始匹配两个步骤。预处理阶段主要是通过两个函数计算模式匹配中的坏字符,这两个函数CHAR1[c]和CHAR2[c]的表示如下:
CHAR1[c]= min{i| m-1>=i>=1} c在模式串中
m c不在模式串中
CHAR2[c]= min{i| m>=i>=0} c在模式串中
m 1 c不在模式串中
初始匹配要找到匹配的位置和方向:首先在左侧对其模式串和文本串,然后自模式串尾部从右向左进行比较,如果模式串的尾部和头部都与文本串相匹配,那么就继续比较中间字符,否则的话将模式串按照文本串的方向从左到右移动。
3.2 算法实例
1) 预处理过程:求解坏字符。
c a cd e
CHAR1[c] 3 21 7
CHAR2[c] 1 32 8
2) 匹配阶段:判断匹配字符的位置和方向。
文本串T:a c d e c d a c d a c d a
模式串P:a c d a c d a
在第一轮匹配过程中,先比较模式串P的头部P[0]和文本串中对应的T[0],尾部P[6]和T[6],然后再比较P[3]和T[3],因为预处理阶段得到的CHAR1[a]等于3,并且CHAR2[c]也等于3,因此要将模式串向右移动3个字符。得到移动后的文本串T和模式串P的示意如下:
文本串T:a c d e c d a c d a c d a
模式串P: a c d a c d a
在第二轮匹配的过程中,匹配的只是模式串P的头部和尾部2次:P[6]和T[9],P[0]和T[3],而且由于同样的原因,模式串P也要向右移动3个字符,得到如下的字符序列:
文本串T:a c d e c d a c d a c d a
模式串P: a c d a c d a
在第三轮匹配过程中,由于模式串P和文本串的头部和尾部都匹配,因此还要进行中间字符的匹配,经过比较发现所有字符都匹配,所以一共进行了7次比较,最终匹配成功。
使用本文提出的改进BM匹配算法之后,上面的例子总共进行了3 2 7=12次字符之间的比较,而且仅仅移动了两次,三轮匹配就能够成功地找到模式串P在文本串T中出现的位置。与BM算法相比较,本文提出的算法明显减少了字符比较的次数,但是这个例子因为文本串T字符过少而使得计算过于简单,无法体现预处理的作用。接下来的例子可以更好地说明本文提出的改进BM匹配算法的优势所在:
1) 预处理过程:求解坏字符。
c ACG T
CHAR1[c] 1 62 8
CHAR2[c] 2 71 9
2) 改进的BM模式匹配算法及其应用
文本串T:G C A T C G C A G A G A G T A T A C A G T A C G
模式串P:G C A G A G A G
在第一轮匹配的时候,先比较模式串P的尾部P[7]和文本串T的相应位置T[7],由于这两者不相等,因此无需再比较头部,又因为CHAR1[c]等于1,而且CHAR2[c]也等于1,所以将模式串P向右移动1个字符,得到如下字符序列:
文本串T:G C A T C G C A G A G A G T A T A C A G T A C G
模式串P: G C A G A G A G
在第二轮匹配的过程中,先比较模式串P的尾部P[7]和文本串T中的相应位置T[8],然后比较模式串P的头部P[0]和文本串T的相应位置T[1],由于此时CHAR1[c]等于2,并且CHAR2[c]也等于2,因此要将模式串向右移动两个字符,再次得到下面的序列:
文本串T:G C A T C G C A G A G A G T A T A C A G T A C G
模式串P: G C A G A G A G
第三轮匹配进行模式串P尾部和头部两次比较,即P[7]和T[10],P[0]和T[3],因为此时CHAR1[c]=CHAR2[c]=2,所以将模式串P再次移动两个字符如下:
文本串T:G C A T C G C A G A G A G T A T A C A G T A C G
模式串P:G C A G A G A G
第四轮匹配在比较了模式串P尾部和头部之后,接着比较中间的字符,一共进行了8次比较,又因为CHAR1[c]=CHAR2[c]=9,所以将模式串P向右移动9个字符:
文本串T:G C A T C G C A G A G A G T A T A C A G T A C G
模式串P: G C A G A G A G
第五轮匹配在比较模式串P的尾部P[7]和文本串T中的对应位置T[21]后,发现二者不匹配,且此时CHAR1[c]=CHAR2[c]=6,将模式串P向右移动6个字符:
文本串T:GCATCGCAG AGAGTATACAGTACG
模式串P: GCAG AGAG
第六轮匹配过程中,因为文本串T里面没有字符与模式串P进行比较,因此比较次数为0。
在这个例子中,使用本文提出的XBM模式匹配算法比较14次,模式串P移动了5次,共进行了5轮匹配过程,速度上比原有的BM匹配算法有了很大的提高。
4 总结
模式匹配算法在入侵检测技术中占有重要的地位,但是由于入侵检测本身的不足之处,模式匹配算法不能很好地应用于入侵检测。BM算法是一种很常见的模式匹配算法,虽然它有坏字符启发规则和好后缀规则,但是好后缀规则的应用还存在缺陷。
本文对BM匹配算法进行了改进,提出了一种可以很好地应用于入侵检测的改进BM匹配算法XBM,算法实例证明本文提出的XBM算法在性能和速度上比原有的BM算法有了很大的改进。
参考文献:
[1] 蹼青.入侵检测系统面临问题与发展趋势研究[J].计算机工程与设计,2004,4(25):55-57.
[2] 王飞.基于改进的BM算法的分布式入侵检测系统的研究[D].江苏大学,2008.
[3] 吴红梅.入侵检测系统中模式匹配算法的研究[D].重庆大学,2009.
关键词:XBM;入侵检测;模式匹配
中图分类号:TP301文献标识码:A文章编号:1009-3044(2010)22-6198-03
当前的入侵检测还有一些不足之处,而模式匹配技术在入侵检测中占有重要的地位,所以提高模式匹配的效率是改善入侵检测算法的关键。在介绍了入侵检测技术的不足之后,本文将会详细介绍以BM算法为主的模式匹配算法,然后对其改进,提出一种改进的NBM算法,在时间复杂度和空间复杂度上提高了模式匹配的效率。
1 当前入侵检测的不足
入侵检测系统的不足之处主要表现在以下几个方面[1]:
1) 误报漏报比较多。入侵检测系统中对入侵数据的研究尚不足,因此在实际应用中会有比较高的误报和漏报率。2) 模式特征的问题。很多入侵检测系统都使用模式匹配的方法进行分析,但是特征的匹配存在效率和效果的矛盾。3) 加密网络的问题。目前的入侵检测系统还难以处理经过加密的会话,虽然已经存在不少入侵检测方法,但是将它们有效地用在处理加密会话的入侵检测中还比较困难。
针对以上不足之处,有必要对模式匹配算法进行分析和改进。
2 BM模式匹配算法
从本质上讲,模式匹配技术是一种攻击判别技术,它分析入侵行为,并从中抽取某些特征或表达,建立一种攻击行为模型,然后依据这种行为模型所代表的攻击意图的行为特征来判断它是否属于攻击行为。
传统的模式匹配算法采用的是单字符移动方式,即模式串每和文本串匹配一次,都仅仅移动一个字符,这样大大降低了查找的速度;另外,模式串与文本串每次对齐后都要进行全部字符的匹配,经常出现前面多数字符匹配而后面少量字符不匹配的情况,大大降低了匹配的效率。
BM(Boyer-Moore)算法是一种经典的字符串模式匹配方法,有效解决了上述问题。在进行模式匹配的时候,先对模式串进行预处理,找到不匹配时文本串指针的偏移值,然后“将模式串和文本串的左侧对齐,接着从右向左将模式串的字符与文本串的字符进行比较,如果完全匹配,就成功退出;如果比较中出现不匹配的情况,则计算模式串右移的距离,把模式串向右移动该距离,然后开始新一轮的比较[2]”。
针对单个字符移动的问题,BM模式匹配算法提供了两个解决问题的规则:好后缀规则和坏字符启发规则。
坏字符启发规则使用模式串中的失配字符作为判断标准,如果失配字符存在于模式串当中,那么就用这个失配字符和文本串中的坏字对齐;如果失配字符不在模式串当中,那么只有在文本串坏字之后的字串中才能找到能够和模式串相匹配的字符,因此直接将模式串移动到文本串坏字后面即可,不必仅仅移动单个字符,例子如下:
文本串T:e c d a b d c a d b
模式串P:e c b a b (1)
e c b a b (2)
假设位移函数是skip(b),而且当模式串中第j个字符等于b时,skip=m-j;可以发现上面的例子中失配字符是b(下划线),在模式串中第3个位置(j=3),而模式串长度m=5,所以移动距离m-j=2。将模式串向右移动两个字符后如式2所示,此时刚好将模式串中的失配字符b匹配了文本串中的字符b。
另外,当模式串中不含有b,则此时的位移函数skip=m;
文本串T:e c d a b d c a d b
模式串P:e c a c c (1)
e c a c c (2)
由于模式串中并不含有失配字符b,所以将模式串向右移动5(模式串长度)个字符,就把模式串移动到了坏字之后。
与坏字符启发规则不同的是,好后缀启发规则使用模式中已匹配的字段与文本串进行对齐,而且模式匹配中已经匹配字段的判断是从右向左进行的。
由BM算法的原理我们可以知道,BM模式匹配算法用到了上次匹配的结果,因此在一定程度上提高了模式匹配的效率;但也应该注意的是,在BM模式匹配过程中,很少用到好后缀规则,并且好后缀规则的使用没有规律性,反而增加了算法的时间开销:预处理阶段中,计算好后缀数组的过程其实也是在进行模式匹配;查找阶段进行的比较坏字符数组和好后缀数组的过程也增加了计算复杂性,因此有必要对BM匹配算法进行改进,并结合入侵检测算法的不足,将BM匹配算法用于入侵检测中。
3 改进的BM匹配算法
3.1 改进的BM匹配算法
分析一下BM匹配算法中的好后缀规则,我们可以发现它的一些不足之处[3]:
1) BM匹配算法中的好后缀规则本质上也是一种模式匹配算法,因此如果模式串的长度比较大,那么随后的匹配运算量会越来越大,也会耗费更多的时间。
2) 即使是比较短的模式串,也会因为字符较少而移动超过模式长度的距离,从而无法体现好后缀规则的优势。
3) 与坏字符规则不同的是,好后缀规则要求至少有一个以上的字符匹配,事实上好后缀形成的几率很小,所以匹配过程中好后缀使用的机会也比较少。
基于好后缀规则的这三个不利之处,本文对其进行改进后提出一种改进的BM匹配入侵检测算法,将存在不足之处的好后缀规则去掉的同时也改进了坏字符启发规则,从而使得模式匹配算法更加高效。
由于收集到的入侵检测特征库中的很多规则都会有部分前缀或者后缀相同,在匹配过程中必然会有不必要的比较,因此可以在匹配顺序上有所改进;另外,有的模式匹配算法会从模式串与文本串对其的字符处开始计算位移量,而有的算法会从下一个字符开始计算,因此也可以将这两种偏移量计算方法结合起来,形成一种改进的XBM模式匹配方法。
改进的模式匹配方法主要分预处理和初始匹配两个步骤。预处理阶段主要是通过两个函数计算模式匹配中的坏字符,这两个函数CHAR1[c]和CHAR2[c]的表示如下:
CHAR1[c]= min{i| m-1>=i>=1} c在模式串中
m c不在模式串中
CHAR2[c]= min{i| m>=i>=0} c在模式串中
m 1 c不在模式串中
初始匹配要找到匹配的位置和方向:首先在左侧对其模式串和文本串,然后自模式串尾部从右向左进行比较,如果模式串的尾部和头部都与文本串相匹配,那么就继续比较中间字符,否则的话将模式串按照文本串的方向从左到右移动。
3.2 算法实例
1) 预处理过程:求解坏字符。
c a cd e
CHAR1[c] 3 21 7
CHAR2[c] 1 32 8
2) 匹配阶段:判断匹配字符的位置和方向。
文本串T:a c d e c d a c d a c d a
模式串P:a c d a c d a
在第一轮匹配过程中,先比较模式串P的头部P[0]和文本串中对应的T[0],尾部P[6]和T[6],然后再比较P[3]和T[3],因为预处理阶段得到的CHAR1[a]等于3,并且CHAR2[c]也等于3,因此要将模式串向右移动3个字符。得到移动后的文本串T和模式串P的示意如下:
文本串T:a c d e c d a c d a c d a
模式串P: a c d a c d a
在第二轮匹配的过程中,匹配的只是模式串P的头部和尾部2次:P[6]和T[9],P[0]和T[3],而且由于同样的原因,模式串P也要向右移动3个字符,得到如下的字符序列:
文本串T:a c d e c d a c d a c d a
模式串P: a c d a c d a
在第三轮匹配过程中,由于模式串P和文本串的头部和尾部都匹配,因此还要进行中间字符的匹配,经过比较发现所有字符都匹配,所以一共进行了7次比较,最终匹配成功。
使用本文提出的改进BM匹配算法之后,上面的例子总共进行了3 2 7=12次字符之间的比较,而且仅仅移动了两次,三轮匹配就能够成功地找到模式串P在文本串T中出现的位置。与BM算法相比较,本文提出的算法明显减少了字符比较的次数,但是这个例子因为文本串T字符过少而使得计算过于简单,无法体现预处理的作用。接下来的例子可以更好地说明本文提出的改进BM匹配算法的优势所在:
1) 预处理过程:求解坏字符。
c ACG T
CHAR1[c] 1 62 8
CHAR2[c] 2 71 9
2) 改进的BM模式匹配算法及其应用
文本串T:G C A T C G C A G A G A G T A T A C A G T A C G
模式串P:G C A G A G A G
在第一轮匹配的时候,先比较模式串P的尾部P[7]和文本串T的相应位置T[7],由于这两者不相等,因此无需再比较头部,又因为CHAR1[c]等于1,而且CHAR2[c]也等于1,所以将模式串P向右移动1个字符,得到如下字符序列:
文本串T:G C A T C G C A G A G A G T A T A C A G T A C G
模式串P: G C A G A G A G
在第二轮匹配的过程中,先比较模式串P的尾部P[7]和文本串T中的相应位置T[8],然后比较模式串P的头部P[0]和文本串T的相应位置T[1],由于此时CHAR1[c]等于2,并且CHAR2[c]也等于2,因此要将模式串向右移动两个字符,再次得到下面的序列:
文本串T:G C A T C G C A G A G A G T A T A C A G T A C G
模式串P: G C A G A G A G
第三轮匹配进行模式串P尾部和头部两次比较,即P[7]和T[10],P[0]和T[3],因为此时CHAR1[c]=CHAR2[c]=2,所以将模式串P再次移动两个字符如下:
文本串T:G C A T C G C A G A G A G T A T A C A G T A C G
模式串P:G C A G A G A G
第四轮匹配在比较了模式串P尾部和头部之后,接着比较中间的字符,一共进行了8次比较,又因为CHAR1[c]=CHAR2[c]=9,所以将模式串P向右移动9个字符:
文本串T:G C A T C G C A G A G A G T A T A C A G T A C G
模式串P: G C A G A G A G
第五轮匹配在比较模式串P的尾部P[7]和文本串T中的对应位置T[21]后,发现二者不匹配,且此时CHAR1[c]=CHAR2[c]=6,将模式串P向右移动6个字符:
文本串T:GCATCGCAG AGAGTATACAGTACG
模式串P: GCAG AGAG
第六轮匹配过程中,因为文本串T里面没有字符与模式串P进行比较,因此比较次数为0。
在这个例子中,使用本文提出的XBM模式匹配算法比较14次,模式串P移动了5次,共进行了5轮匹配过程,速度上比原有的BM匹配算法有了很大的提高。
4 总结
模式匹配算法在入侵检测技术中占有重要的地位,但是由于入侵检测本身的不足之处,模式匹配算法不能很好地应用于入侵检测。BM算法是一种很常见的模式匹配算法,虽然它有坏字符启发规则和好后缀规则,但是好后缀规则的应用还存在缺陷。
本文对BM匹配算法进行了改进,提出了一种可以很好地应用于入侵检测的改进BM匹配算法XBM,算法实例证明本文提出的XBM算法在性能和速度上比原有的BM算法有了很大的改进。
参考文献:
[1] 蹼青.入侵检测系统面临问题与发展趋势研究[J].计算机工程与设计,2004,4(25):55-57.
[2] 王飞.基于改进的BM算法的分布式入侵检测系统的研究[D].江苏大学,2008.
[3] 吴红梅.入侵检测系统中模式匹配算法的研究[D].重庆大学,2009.