• Hi:欢迎来到一心论文网!
  • 您当前的位置:首页 > 工学 > 计算机 > 正文

    论入侵检测系统的研究与改进

    来源:网络  时间:2017-07-01 00:32:00

      

    1 BM算法研究
      
      1977年Boyer和Moore提出了一种全新的算法,即BM算法。它的特点在于匹配过程中,模式从左向右移动,但字符比较却从右向左进行。其基本算法思想是:(1)匹配从右至左进行。(2)若匹配失败发生在Pi≠Ti且Ti不出现在模式P中,则将模式右移直到Pi位于匹配失败位置T的右边第一位(即Ti 1位),若Ti在P中有若干地方出现,则选择j=max{k|Pk=Ti}即通过Skip函数计算文本字符Ti失配时模式向右移动的距离,也称坏字符启发。(3)若模式后面k位与文本T中一致的部分有一部分在P中其他地方出现,则可以将P向右移动,直接使这部分对齐,且要求这一部分尽可能大,Shift函数通过对已经匹配部分的考查决定模式向右移动的距离,也称好后缀启发。
      实例分析:
      第1次匹配:
      Example
      here is a simple example
      第2次匹配(坏字符启发):
      Example
      here is a simple example
      第3次匹配(坏字符启发):
      Example
      here is a simple example
      第4次匹配(好后缀启发):
      Example
      here is a simple example
      第5次匹配(坏字符启发):
      Example
      here is a simple example
      BM算法预处理时间复杂度为O(m s),空间复杂度为O(s),s是与P, T相关的有限字符集长度,搜索阶段时间复杂度为O(mn)。最坏情况下要进行3n次比较,最好情况下的时间复杂度为O(n/m)。
      
      2 改进BM匹配算法研究
      
      2.1 改进的意义
      综合分析会发现虽然BM算法考虑较全面,但它使用了两个数组,预处理时间开销较大,于是在BM算法基础上我们对其进行了简化,使得算法更简单、高效,提出了一种改进的BM算法。通过实验表明改进的模式匹配算法能减少比较次数,有效地提高了匹配效率。
      2.2 改进的原理
      在BM算法匹配过程中,常出现模式的一部分后缀与文本匹配,而模式的前缀却不匹配,在这种情况下,就进行了一些不必要的比较。因此在BMGJ算法中,我们在对模式串与文本字符串进行匹配时采用从模式两端向中间位置交替的匹配顺序,模式匹配先从模式最右端Pm开始进行。若Pm匹配不成功,则通过Skip函数计算出模式向右移动的距离,这与BM算法中坏字符启发思想相同;若Pm匹配成功,则比较模式P1与文本中相应的字符。若P1匹配不成功,则考查文本中与模式中Pm下一个字符对齐的字符,若该字符不出现在模式中,则模式可以向右移动m 1个位置,若该字符出现在模式中,则计算其Skip函数,然后将模式向右移动相应的长度;若P1匹配成功,则按上述方法依次对Pm-1,P2,Pm-2,P3,…进行匹配,依此类推,直到匹配过程完成。实例分析:

      第1次匹配:
      Example
      here is a simple example
      第2次匹配:
      Example
      here is a simple example
      第3次匹配(传统BM算法匹配中,此遍比较需要从右端比较5次才可以找到一个坏字符,但对于改进后的算法,只比较两次就可以找到一个坏字符):
      Example
      here is a simple example
      第4次匹配:
      Example
      here is a simple example
      第5次匹配:
      Example
      here is a simple example
      在上例中,我们可以看出用传统的BM算法匹配共进行了4次移动15次比较,用改进的BM算法匹配共进行了4次移动12次比较,匹配次数减少。
      改进后的BM算法的预处理时间复杂度为O(m s),空间复杂度为O(s),搜索阶段时间复杂度为O(mn)。该算法在比较右端字符失配时采用BM坏字符启发的思想,在比较了左端字符失配时采用对文本中与模式最右端对齐的下一个字符进行考查的方法,使得大多数情况下具有比BM算法更大的右移长度,从而有更好的平均性能。
    2.3 改进的实验分析
      我们所做的实验软件环境主要是:采用的操作系统是MicroSoft Windows XP Professional(Service Pack2),使用JBuilder2006编译工具,所用JDK为jdk1.6。
      为了对各算法的性能进行比较次数和比较用时的测试,我们随机地选取了一段纯英文自然语T文本和模式串P,在同一台计算机上用不同算法进行3万、5万、10万次循环匹配,分别统计各算法循环匹配所进行的字符比较次数和总消耗的时间。
      文本串:T=One day one pig went to a bar and the bar tender asked what can I get for you today and the pig said five beers. He drank up all the beer and then he asked were the bathroom was the bar tender said straight down the hall to the left. Then three more pigs came in and the bar tender asked what can I get you today.
      模式串:P= I get you today.
      测试结果下表1所示:

      经过多次匹配实验,结果显示改进后的BM算法进行模式匹配时字符比较次数、匹配时间均少于原BM算法,匹配效率有所提高。
      
      3 结语
      
      随着网络规模的不断扩大和入侵手段的不断更新,对入侵检测也提出了更高的要求。目前,BM算法还是入侵检测系统中主要使用的模式匹配方法,而它本身存在的一些问题使其还是有改进的余地,本文对其进行了改进,并且通过实验结果分析得出改进以后在匹配效率的提高。以后我们还可以在检测引擎中结合其他智能化的检测方法,如协议分析、神经网络、遗传算法等,这将是我们下一步研究的重点。
      
      

    参考文献


      [1]?谷晓钢,江荣安,赵铭伟.Snort的高效规则匹配算法[J].计算机工程,2006,(18).
      [2]?唐正军.入侵检测技术导论(第一版)[M].北京:机械工业出版社,2004.
      [3]?边肇祺,阎平凡,杨存荣.模式识别(第一版)[M].北京:清华大学出版社,1988.
      [4]?郭军,笹尾勤.入侵检测中模式匹配算法的FPGA实现[J].科技创新导报,2007,(14).

    相关论文

    最新论文

    热点论文

    [中等教育职专政治教育中的德育渗透
      帮助学生树立正确的价值观和人生观,提升学生的个人品德与思想素质,是职专政治教育的主要目标与根本目的。但受限于传统政治教育的教学 [全文]
    [中国哲学传递“中国梦”正能量是记者的神圣使命
      摘要:中国梦是中华民族伟大复兴的梦,是当今中华民族前进的动力,是当前中国最具影响力、最具感染力、最具普遍性的正能量。记者作为以 [全文]
    [财务控制论企业集团财务控制的对策
    摘 要:市场经济飞速发展促使企业集团组织形式发生非常大的变化,那么企业集团需要有效利用自身发展优势,促进现代化经济发展。 改革逐渐 [全文]
    [财务控制中小企业的财务控制问题分析
    摘 要:随着市场经济体制不断完善,我国中小企业进入快速发展阶段,其在国民经济发展中的作用被不断凸显出来。本文中笔者以中小企业财务管 [全文]
    [职业教育分析音乐课堂中的情感互动及学生体验
      【摘要】针对音乐课堂中的情感互动及学生体验进行分析,基于学生的实际音乐学习需求、音乐学习目标等予以教学设计,以期能够不断提升音 [全文]
    [市场营销新时期下市场营销的演变趋势分析
    摘要:随着全球经济互相影响,新市场格局的形成让新时期环境里市场营销不断发生变革。而本文主要是对当今市场新形势进行一个分析,找出对市 [全文]
    [国际贸易国际贸易融资创新及风险控制
    [摘 要] 国际贸易企业融资风险的主要表现有两种:一是国际贸易企业无法以自身的流动资金偿还债务,要通过集资的方式偿还债务本金和利息; [全文]
    [国际贸易“互联网 +”时代下国际贸易发展策略研究
    摘 要:随着网络技术和经济全球化的进一步发展,互联网关系到国际贸易领域的方方面面,并以全新的国际贸易形态,将分散在世界各地的市场, [全文]

    售前客服

    咨询QQ:619978682

    在线客服