一种BM算法改进的研究*

朱俚治

(南京航空航天大学信息中心　南京　210016)



一种BM算法改进的研究*

朱俚治

(南京航空航天大学信息中心南京210016)

摘要在当今的互联网中黑客攻击事件频频发生,为了阻止黑客攻击网络事件的发生从而保证网络的安全性,需要能够检测出网络用户行为的某种算法。在入侵检测技术中,模式匹配算法是一种重要的检测算法,该种算法能够检测已知和未知的网络攻击行为。目前模式匹配算法有多种,其中字符串匹配算法也属于一种模式匹配算法,字符串匹配算法在入侵检测中有着广泛的应用。经典的字符串匹配算法有BM算法和KMP算法,论文为了提高和改进BM算法在字符匹配时的速度,将MMTD算法和粗糙集中的决策系统在BM算法中进行应用,这是论文的创新点。论文改进BM算法的思路是首先使用MMTD算法对字符串的属性值进行衡量,然后再使用决策系统对该字符串中字符匹配是否成功做出决策。论文提出的算法在一定程度上能够提高BM算法的匹配速度。

关键词MMTD; 决策系统; BM算法

Study on the Improvement of BM Algorithm

ZHU Lizhi

(Information Center, Nanjing University of Aeronautics and Astronautics, Nanjing210016)

AbstractIn today’s internet hacker attacks occur frequently, in order to prevent hacker attacks, network event occurs so as to ensure the security of the network. Therefore, it is necessary to detect a algorithm of network user behavior. In intrusion detection, pattern matching algorithm is an important detection algorithm, which can detect known and unknown network attacks. At present, there are many kinds of pattern matching algorithms, and the string matching algorithm is a pattern matching algorithm, and the string matching algorithm has a wide application in intrusion detection. Classical string matching algorithm includes KMP algorithm and BM algorithm, in order to improve the speed of BM algorithm in the character matching speed. Therefore, the MMTD algorithm and rough set decision system are used in the BM algorithm, which is the innovation of this paper. In this paper, the MMTD algorithm is used to measure the attribute value of the string, and then the decision system is used to make a decision on whether the string is successful or not. The algorithm proposed in this paper can improve the matching speed of BM algorithm to a certain extent.

Key WordsMMTD, decision system, BM algorithm

Class NumberTP301.6

1引言

当今模式匹配算法有很多,其中最著名的两个是KMP算法和BM算法。这两种算法具有较高匹配效率,在最坏情况下均具有线性的搜索时间[6~8]。在算法的匹配速度方面BM算法比KMP算法具有更快的速度和更高的字符匹配效率[6~8]。字符串匹配算法具有更快的匹配速度是人们重点研究的方向之一。BM改进算法都是以改进算法的匹配速度为目标。

BM算法是由Boyer和Moore提出的,该算法是一种字符串匹配算法,在入侵检测的模式匹配中有着较多的应用。入侵检测中模式匹配技术是一种重要的检测技术,误用检测就是通过模式匹配技术来发现已知的和未知的网络攻击行为。因此如何选择模式匹配算法作为入侵检测技术中的匹配算法是相当重要的,可以减少误用检测的漏警率和误警率。

在BM算法中具有较高的字符匹配速度,本文为了近一步提高BM算法的字符匹配速度和匹配效率,本文将MMTD算法在BM算法中进行首次的应用,这是本文的创新点之一。在本文提出的改进算法之中,首先使用了MMTD算法对字符串的属性值进行衡量。如果字符串的属性值匹配成功,则再进行字符串中的字符匹配。如果字符串的属性值匹配不成功,则不再进行字符的匹配。通过字符串属性的匹配之后,再进行字符的匹配,可以缩小字符串匹配的范围,提高BM算法在字符串匹配时的速度和效率。在本文中将粗糙集中的决策系统在BM算法中进行应用,这也是本文的创新点之一。

2BM算法的介绍

BM算法的具体匹配是从P的右端向左进行,进行中考察比较并考虑文本中可能出现的字符在模式中的位置,该算法的基本思想是[6~10]:

1) 匹配自右向左进行;

2) 若匹配失败发生在Pj≠Ti,且Ti不出现在模式T中,则将模式右移直到P1位于匹配失败位Ti的右边第一位(即Ti+1位),若T1在P中有若干地方出现,则应选择j=max{K|Pk=Ti};

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

3MMTD算法技术简介

3.1中介真值程度度量知识简介

图1中介真值程度度量一维函数图

对数轴y=f(x)表示的含义有以下说明[1~2]:

1) 如果数轴上数值点的位置逐步接近P,则事物A所具有P的属性逐步增强。

3.2中介真值程度度量中的距离比率函数

在中介真值程度度量的方法中,数轴上某数值点通过距离比率函数来计算事物所具有属性的强弱。

定理1给定y=f(x)∈f(X),ξ(h(y))=h(y),则有[1~2]：

1) 当αF+εF

2) 当y>αT+εT时,gT(x)>1;当y<αF-εF时,gF(x)>1;

3) 当y<αF-εF时,gT(x)<0;当y>αT+εT时,gF(x)<0;

4)gT(x)+gF(x)=1。

(1)相对于P的距离比率函数[1~2]

4MMTD在字符串匹配上的应用

4.1度量公式

函数:

说明:函数y=f(x)的含义是需要匹配的字符串偏离被匹配字符串的程度。

1) 如果函数

2) 如果函数

讨论: 1) 如果函数y=f(x)的值越小,则需要匹配的字符串属性值偏离被匹配的字符串的程度越小,那么字符串的相似程度就越高。这时字符串匹配程度部分好部分差,那么需要匹配的字符串可以向某个方向进行搜索匹配。

2) 如果函数y=f(x)的值越大,则需要匹配的字符串属性值偏离被匹配的字符串的程度就越大。如果偏离值越大,那么字符串的相似程度就越差。

根据本节中的分析讨论,在本文中可以使用中介的思想对字符串的匹配进行描述和分析:

结论: 1) 如果偏离函数y=f(x)值为0,则表示字符串的属性值匹配成功,匹配程度好。

2) 如果偏离函数y=f(x)值不为0,偏离值越小,则表示字符串属性值的匹配程度部分好部分差。

3) 如果偏离函数y=f(x)值不为0,偏离值越大,则表示字符串属性值的匹配程度就越差。

4.2中介对用户行为的描述

根据4.1节中的分析讨论,以下可以使用中介的思想对字符串的匹配过程进行描述和分析。

1) 中介逻辑对字符串的匹配

2) 距离比率函数

图2中介真值程度度量一维函数的应用

相对于P的距离比率函数

通过距离比率函数hT(x)对y值的计算,如果有：

(1)若函数hT(x)=1,y值落在区域(αl-εl,αl+εl),则代表匹配程度好。

(2)若函数hT(x)=0,y值落在区域(αr-εr,αr+εr),则代表匹配程度差。

4.3字符串匹配的讨论和分析

在字符串的匹配过程中如果匹配成功,那么这两个字符串的属性值之和必然相等。

1) 两个属性值相同的字符串,长度可能不相同,此时字符串的匹配不成功。

分析:现在存在两个需要匹配的字符串A与B,字符串A中含有字符a与b,其属性值分别为8和3。

字符串B中含有字符c、d、e,其属性值分别为4、5、2。

从上面可以知道字符串的属性值之和是相等的,但这时字符串的匹配是不成功的。

2) 长度相同的字符串,字符串的属性值未必相同。

3) 如果两个字符串的属性值不相同,但长度相同,那么在某个字符串中必定有某个字符的属性值不同。

结论:当两个字符串相互匹配时，只有当两个字符串的属性值相同并且字符的长度也相同,此时字符串的匹配是成功的。

1) 字符串的匹配如果是成功的,那么这两个字符串的属性值之和是相等的。

2) 字符串的匹配如果不成功,那么这两个字符串的属性值之和一定不相等。

3) 如果两个匹配的字符串属性值相等,这两个字符串匹配不一定成功。

4.4根据MMTD算法对字符串的匹配分析和描述的结论

1) 如果字符串的属性值匹配成功,则使用粗糙集中的决策系统进行该字符串中的字符进行匹配。

2) 如果字符串的属性值匹配不成功,则无需进行该字符串中的字符匹配。

5粗糙集的决策系统

在实际应用中存在一大类任务:给定一组有特征描述的样本和样本的类别,需要通过一个学习算法从该组样本中学习一个分类函数,实现从特征到分类的映射。粗糙集理论中称该数据集为信息系统[3~4]。

6决策系统在度量实例匹配上的应用

由于决策条件属性的属性值的不同,因此能够产生不同的决策属性的属性值,事实上正是由于不同的决策属性的属性值,才产生了不同的决策结果,这些不同的决策结果能够将不同属性的样例进行有效的分类。条件属性的属性值决策规则的内涵是决策系统做出决策结果的重要决定因数。

6.1决策系统的参数设定:

1) 域:

U={x1,x2,x3,…,xn},其中x1,x2,x3,…,xn分别表示等待匹配的每个字符。

2) 属性集:

A={a1,a2,a3},其中a1表示字符串中某个字符的属性值,a2表示字符的匹配值,a3表示字符的匹配是否成功。

3) 值域:

V={Y,N}

6.2决策函数

1) 如果f(x)=1,那么由决策系统做出决策的这次字符匹配是成功的,决策属性值为Y。

2) 如果f(x)≠1,那么由决策系统做出决策的这次字符匹配是不成功的,决策属性值为N,则将模式右移直到P1位于匹配失败位Ti的右边第一位(即Ti+1位)。

6.3字符对象属性的匹配决策表

在一个决策系统中如果把每一条样例的条件属性值部分作为规则的前件,把决策属性值部分作为规则的后件,那么每一条样例都可以看成一条规则[3~4]。在决策系统中每一条样例都对应着一条具体的决策规则。在以下的决策表中可将决策属性分为条件属性和决策属性[3~4]。信息系统中的属性集合可以分成两部分,一部分为条件属性集合,另一部分为决策属性,这种信息系统通常称为决策系统或决策表[3~4]。

在以下的系统决策表中,条件属性是: 1)a1表示某个字符的属性值。 2)a2表示字符的匹配值。决策属性:a3表示字符的匹配是否成功。

图3　决策表应用示意图

说明: 1) 当字符串中的某个字符时,其属性值为Y。

2) 当字符的匹配值为1时,其属性值为Y,否则其属性值为N。

3) 当字符匹配成功时,其属性值为Y,否则其属性值为N。

6.4决策规则

决策规则:

1) (某个字符,Y)∧(字符的匹配值,Y)⟹(字符的匹配,Y)。

2) (某个字符,Y)∧(字符的匹配值,N)⟹(字符的匹配,N)。

7改进BM算法

改进BM算法的具体匹配是从P的右端向左进行,进行中考察比较并考虑文本中可能出现的字符在模式中的位置,该算法的基本思想是:

1) 使用MMTD算法对字符串属性值的匹配程度好与坏做出衡量;

2) 匹配自右向左进行;

3) 若匹配失败发生在Pj≠Ti,且Ti不出现在模式T中,则将模式右移直到P1位于匹配失败位Ti的右边第一位(即Ti+1位),若T1在P中有若干地方出现在,则应选择j=max{K|Pk=Ti};

4) 使用粗糙集中的决策系统对匹配是否成功做出决策;

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

8结语

BM算法和KMP算法是两种经典的字符串匹配算法,BM算法有多种改进型算法[6~10],改进算法具有更快的字符匹配速度,因此BM算法是一种有效和实用性强的算法,同时也是一种高效的智能性算法。本文的作者在查阅了BM算法和一些字符串匹配算法之后,提出将MMTD算法和粗糙集中决策系统与BM相互结合在一起,形成一种改进型BM算法。本文提出的改进型BM算法具有一定的智能性,在某种程度上可以提高BM算法在字符匹配时的速度和效率,将MMTD算法和决策系统在BM算法中进行应用是本文的创新点。

参 考 文 献

[1] 洪龙,肖奚安,朱梧槚.中介真值程度的度量及其应用(Ⅰ)[J].计算机学报,2006(12):2186-2193.

HONG Long, XIAO Xi’an, ZHU Wujia. Intermediary true value measurement and its application level (Ⅰ)[J]. Chinese Journal of Computers,2006(12):2186-2193.

[2] 朱梧槚,肖奚安.数学基础与模糊数学基础[J].自然杂志,1980,7:723-726.

ZHU Wujia, XIAO Xi’an. With fuzzy mathematics[J]. Journal Nature Mathematical Foundation,1980,7:723-726.

[3] 胡清华,于达仁.应用粗糙集计算[M].北京:科学出版书,2012,6.

HU Qinghua, YU Daren. Application of rough set calculation of[M]. Beijing: Scientific Publishing Books,2012,6.

[4] 陈德刚.模糊粗糙集理论与方法[M].北京:科学出版社,2013,11.

CHEN Degang. The theory and method of fuzzy rough set[M]. Beijing: Science Press,2013,11.

[5] Tom M.Mitchell.机器学习[M].北京:机械工业出版社,2013.

Tom M.Mitchell. Machine learning[M]. Beijing: Machinery Industry Press,2013.

[6] 孙文静,钱华.改进BM算法及其在网络入侵检测中的应用[J].计算机科学,2013,40(12):174-176.

SUN Wenjing, QIAN Hua. The improved BM algorithm and its application in computer science [J]. Computer Science,2013,40(12):174-176.

[7] 李洋,王康,谢萍,等.BM模式匹配改进算法[J].计算机应用研究,2004,21(4):58-59.

LI Yang, WANG Kang, XIE Ping. The Improving Algorithm of BM[J]. Application Research of Computers,2004,21(4):58-59.

[8] 杨薇薇,廖翔.一种改进的BM模式匹配算法[J].计算机应用,2006,26(2):318-319.

YANG Weiwei, LIAO Xiang. Improved pattern matching algorithm of BM[J]. Journal of Computer Applications,2006,26(2):318-319.

[9] 闵联营,赵婷婷.BM算法的研究与改进[J].武汉理工大学学报,2006,30(3):528-530.

MIN Lianying, ZHAO Tingting. Research and improvement of BM[J]. Journal of Wuhan University of Technology,2006,30:528-530.

[10] 巫喜红,凌捷.BM模式匹配算法剖析[J].计算机工程与设计,2007,28(1):29-31.

MIN Xihong, LING Jie. Anatomy of BM pattern matching algorithm[J]. Computer Engineering and Design,2006,30:528-530.

中图分类号TP301.6

DOI:10.3969/j.issn.1672-9722.2016.02.005

作者简介:朱俚治,男,工程师,研究方向:计算机科学与技术。

基金项目:北京航空航天大学软件开发环境国家重点实验室开放基金项目(编号:SKLSDE-2013KF-02)资助。

*收稿日期:2015年8月10日,修回日期:2015年9月24日