入侵检测中高效模式匹配算法的研究

1、入侵检测中高效模式匹配算法的研究目录3课题研究内容2国内外研究动态1选题背景及其意义5预期成果和可能的创新点4研究方案及难点 NCEPU 1/选题背景及其意义选题背景选题背景由于近年来网络以令人难以置信的速度向前发展，网络技术日新月异，与此同时网络也常常会受到非法入侵者的攻击，网络中的敏感数据可能泄露或被修改，网络传送的信息可能被其他人窃听和篡改等。因此，入侵检测系统技术应运而生，而大型网络以及千兆以太网的出现，使目前的网络入侵检测系统很难跟上网络快速发展的步伐，传统的入侵检测方法面临严重挑战。由于大量的网络数据来不及处理而使入侵漏报，网络入侵检测系统只能形同虚设。目前实用的网络入侵检测系统中

2、的关键是模式匹配运算，模式匹配的效率决定了入侵检测系统的性能，因此提高模式匹配算法的效率是提高系统检测能力关键所在。改进现有的模式匹配算法迫在眉睫。NCEPU 1/选题背景及其意义选题意义选题意义模式匹配是计算机领域的一个重要的研究方向，不仅在入侵检测系统领域，而且在WWW搜索引擎、内容过滤防火墙等领域都有广泛的应用，其面临的挑战性问题多，创新空间大，因此，针对上述因传统入侵检测方法难以跟上网络发展的步伐，而需要改进入侵检测中现有的模式匹配算法的应用需求，通过对经典模式匹配算法的研究和分析，拟对于传统模式匹配算法进行改进，以便提出一种高效的模式匹配算法应用于入侵检测系统中；同时也考虑在入侵检测

3、系统本身出发寻找突破点，研究网络数据包以及网络入侵特征，以完善入侵检测机制。这样一个课题的研究工作，具有重要的理论和应用价值。NCEPU 2/国内外研究现状入侵检测系统的研究现状入侵检测系统的研究现状从首次提出入侵检测系统的概念，划分简单的入侵检测行为，到提出了第一个入侵检测系统的抽象模型，再到基于状态转换分析的入侵检测技术的提出和完善，直到后期国内外都出现了一些入侵检测产品，但也都存在潜在的提升完善空间。 ID 对于入侵检测系统，国内的研究外经历了以上的变化。 NCEPU 2/国内外研究现状入侵检测系统的研究现状入侵检测系统的研究现状入侵检测技术的研究与开发在国外开展的较早。1980年，Ja

4、mesAnderson在一篇名为Computer Security Threat Monitoring and Surveillance的技术报告中首次引入入侵检测系统的概念，对入侵检测行为进行了简单的划分，提出了使用审计信息来跟踪用户的可疑行为。1987，Dorothy Denning提出了第一个入侵检测系统的抽象模型，以及实时的、基于统计量分析和用户行为轮廓的入侵检测技术，首次将入侵检测的概念作为一种计算机系统安全防御问题的措施提出。NCEPU 2/国内外研究现状入侵检测系统的研究现状入侵检测系统的研究现状90年代以后，随着Porras和Kemmerer基于状态转换分析的入侵检测技术的提出

5、和完善，从1995年以后，逐渐出现了一些入侵检测产品，其中比较有代表性的有NAI公司的Cybercop和Cisco公司的NetRanger。国内对于入侵检测系统的开发和研究从九十年代末才开始，起步比较晚，但是已经认识到入侵检测的重要性，呈现出蓬勃发展的局面，也涌现出了很多有成就的IDS厂商，如启明星辰、绿盟科技、金诺、瑞星等。然而，国内对IDS 的开发研究在技术上和产品上与国外还是有很大的差距。NCEPU 2/国内外研究现状模式匹配算法的研究现状模式匹配算法的研究现状从最早的蛮力算法（BF算法）的提出，接着出现了最为快速的BM模式匹配算法，之后到简化和改进BM算法而演变来的BMLS算法，再到基

6、于BMLS算法基础上改进BM算法得来的BMLT模式匹配算法，一直到其他基于BM 的改进算法，依然暂时没有一个特别行之有效的模式匹配算法既能够有着较高的运算效率又能适应各种模式匹配情况。PM 对于模式匹配算法，国内的研究外经历了以上的变化。 NCEPU 2/国内外研究现状模式匹配算法的研究现状模式匹配算法的研究现状蛮力算法(BF算法)BM算法是1977年由Robert S Boyer和J Strother Moore共同提出的的单模式匹配算法，它是在实际应用中最为快速的模式匹配算法之一，被大多数的入侵检测系统所采用。其基本思想是：字符从右往左进行匹配，当出现不匹配时，通过坏字符移动表和好后缀移动

7、表来进行模式串右移，直至找到匹配字符串或文本串匹配结束为止。文献1对BM算法进行了简化与改进，即BMLS算法,其认为好后缀移动函数难以理解且不便于实现，于是在进行模式串右移的判断时，只采用坏字符移动函数，且将字符失配处理与计算模式串右移量独立。NCEPU 2/国内外研究现状模式匹配算法的研究现状模式匹配算法的研究现状同时文献1提出在BMLS算法的基础上对BM算法进行了进一步改进得到BMLT算法，利用与模式串末位对应的后一位文本串字符Ti+m，若Ti+m不在模式串中，则可直接将模式串右移m+1位，若在模式串中，则利用坏字符启发函数进行右移。与BMLS算法相比，能获得更高的匹配效率。其他基于BM

8、的改进算法：文献2提出了一种改进将模式串的最大右移量提高至m+2，文献3、5致力于，使得算法效率有所提高。NCEPU 2/国内外研究现状文献文献文献1：Improved BM Pattern Matching Algorithm for Intrusion DetectionImproved BM Pattern Matching Algorithm for Intrusion Detection, Computational Science and Optimization (CSO), 2010 Third International Joint Conference on , vol.1

9、, no., pp.440,444, 28-31 May 2010文章中提到了BMLS和BMLT算法，但两者都有各自优点和自身弊端，由此我受到启发认为可以扬长避短结合两者的优势设计改进的新算法文献2：An improved pattern matching algorithmIntelligent Information Technology and Security Informatics (IITSI), 2010 Third International Symposium on , vol., no., pp.599,603, 2-4 April 2010该文中提出一种改进将模式串的最大

10、右移量提高至m+2，我认为其中的最大右移思想有借鉴意义，所以提高最大意义距离是提高匹配速度的一个重要因素NCEPU 2/国内外研究现状文献文献文献3：IMPROVEMENT OF ALGORITHM FOR PATTERN MATCHING IN INTRUSION DETECTIONBroadband Network & Multimedia Technology (IC-BNMT), 2013 5th IEEE International Conference on , vol., no., pp.281,284, 17-19 Nov. 2013文献5：An Effective P

11、attern Matching Algorithm for Intrusion Detection Computer Science and Electronics Engineering (ICCSEE), 2012 International Conference on , vol.3, no., pp.34,38, 23-25 March 2012两篇文章都致力于提高了最大移动量m+1出现的概率，以使得算法效率有所提高中，我认为单纯的增大每次匹配的右移距离是一个重要因素，但是只有少量次右移还是不足以有效提高匹配效率，所以设计的算法需要着重考虑如何既能有着较大的右移距离又能有着高的最大右移

12、概率。NCEPU 3/课题研究内容分析现有的模式匹配算法的利弊分析现有的模式匹配算法的利弊BF算法简单，但是效率较低。平均比较次数是：m*(n-m+1)/2。最坏情况下要进行m*(n-m+1)次比较，时间复杂度为O(m*n)。BM算法采用了“跳跃式”查找策略，因此该算法在比较字符的次数上比传统的模式匹配算法少，在模式匹配中存在两个基本定理：任何字符串匹配算法在最坏情况下必须检查至少n-m+1个文本中的字符；任何字符串匹配算法至少检查n/m个字符。因此，没有一个算法比BM算法有更好的计算复杂度，虽然BM算法考虑比较全面，包括了右移时的各种情况，但是它使用了两个数组，预处理时间花费较大，而且我们可

13、以通过改进来减少比较次数，提高匹配的平均性能。对于基于BM算法改进过后的BMLS和BMLT算法，BMLT算法在普遍的情况下比BMLS算法有更高的效率，但若下一字符在模式串中而末字符不在模式串中时，BMLS算法却能获得比BMLT算法更大的右移距离。 NCEPU 3/课题研究内容在现有方法的基础上提出一个更优化方法在现有方法的基础上提出一个更优化方法通过研究BM算法和BMLT算法的具体实现过程可以发现，BM算法既使用了好后缀跳跃规则，又使用了坏字符跳跃规则，最大右移距离为m(模式串长度)，但是其坏字符跳跃规则会造成回溯。BMLT算法对BM算法进行了简化，只使用坏字符跳跃规则，根据当前窗口后一位字符

14、来决定右移量。如果当前窗口的下一个字符不在模式串中，则可实现最大右移距离m+l。如果当前窗口的下一个字符在模式串中出现的频率较高，则会减少右移距离。综合上述BM相关算法思想，考虑到模式匹配算法能否顺利完成匹配，关键一点就是模式串需要不断右移，在串匹配算法中，模式每次至少都要向右移动一个位置，从这一点出发，我认为，可以结合BM和BMLT算法的优点，对BM相关算法进行优化改进，使得新算法继承BM和BMLT算法中严谨的右移方式，在确保不会遗漏任何匹配的情况下，既可以实现最大安全跳跃距离m+1，又可以提高最大跳跃距离出现的频率，从而整体上提高模式匹配算法的匹配效率。NCEPU 3/课题研究内容建立一个

15、有针对性的应用模型建立一个有针对性的应用模型正如如上所述，常用的模式匹配算法所采用的思想主要有基于字符比较、基于hash查找、基于位逻辑运算等机构进行搜索匹配，以上的单模式匹配算法应用广泛。而鉴于目前的网络实际状况，多模式的匹配算法更加适合于基于模式匹配的入侵检测系统。所以我认为可以从下面3个方面着手：一是继续研究和改进精确的模式匹配，可以将快速的单模式匹配算法和多模式匹配算法相结合，充分借鉴同类算法的先进思想，如：引入Hash函数，对字符块分块等方式来不断提高模式匹配算法的性能；二是尝试采用模糊匹配的策略，可能借鉴人工智能的知识方法，国外对此已经开始进行相应的研究；三是对于网络数据包和入侵特

16、征进行研究，总结出这两类字符串的特点，有针对性地对这两类字符串的匹配问题进行研究。因此，基于以上几个方面，可以在改进模式匹配算法与研究网络入侵特征的基础上建立一个有针对性的具有高效模式匹配算法的入侵检测应用模型。NCEPU 4/研究方案及难点研究方案研究方案通过研究现有算法的基础上，发现现有算法在各方面所具有的缺陷及优点，在参考了许多国内外的研究方法后，希望改进在入侵检测系统应用中的关键点即模式匹配算法以提高入侵检测的生命力；首先我们希望建立这样的一个研究模型：该模型一方面可以对于现有的模式匹配算法进行类似于上述所述单模式匹配算法的改进，并可以考虑将其与快速的多模式匹配算法相结合。另一方面，我

17、们可以站在问题的其他角度寻找突破口，如为了完善入侵检测系统的功能，提高网络的安全性，可以对其要检测的网络数据包以及网络入侵特征进行研究，总结它们的特点从而针对性的改进模式匹配算法，完善入侵检测机制。接着，在所研究模型的基础上，提出下图所示的研究方案：NCEPU 4/研究方案及难点研究方案研究方案NCEPU入侵检测中高效模式匹配算法的研究入侵检测中高效模式匹配算法的研究结合两种模式匹配算法研究结合两种模式匹配算法研究新型高效的匹配算法，继承新型高效的匹配算法，继承两者的优秀特性两者的优秀特性研究并改进研究并改进单模式匹配单模式匹配算法算法研究并改进研究并改进多模式匹配多模式匹配算法算法尝试采用模

18、糊尝试采用模糊匹配的策略，匹配的策略，可能借鉴人工可能借鉴人工智能领域的知智能领域的知识方法和研究识方法和研究对于网络数据对于网络数据包和入侵特征包和入侵特征进行研究，有进行研究，有针对性的改进针对性的改进入侵检测机制入侵检测机制 4/研究方案及难点难点难点对于经典模式匹配算法改进的难点有：1.对于以上单模式匹配算法需要设计出基于BM相关算法优化改进算法的预处理函数，包括构造和生成坏字符跳跃表以及构造和生成好后缀跳跃表； 2.设计基于BM相关算法优化改进算法的匹配程序； 3.如果预测出两种模式匹配算法的结合能够达到模式匹配的更优效果,如何扬长避短将两算法结合是工作的难点； 由于目前对于模糊匹配策略的研究方法以及对于网络数据包和入侵特征的研究所做的工作还不算很多，对于其具体的实现过程还存在一定的问题。 NCEPU 5/预期成果和可能的创新点预