高效的模式匹配算法研究

２００４年ｌ川第２５卷第ｌ划通信学报ＪＯＵＲＮＡＬＯＦＣＨＩＮＡＩＮＳＴＩＴＵＴＥＯＦＣＯＭＭＵＮＩＣＡＴＩＯＮＳＪａｎ…２００３、Ⅶ２５ＮｏＪ高效的模式匹配算法研究田俊峰，黄建才，杜瑞忠，翟建强河北大学阿络技术研究所，河北保定０７１００２）摘要：对入侵检测中模式匹配的方法进行了研究，分析了当前常用的模式匹配方法的弱点与不足，提出了一种基于三叉树结构的自动机方法，较好的避免了传统树型结构中由于节点数目变化而导致的不便。此外，利用匹配失败的信息，实现了跳跃匹配，提高了模式匹配的速度。关键词：网络安全：入侵检测：模式匹配；协议分析；自动机中图分类号：ＴＰ３９３０８文献标识码：Ａ文章编号：ｌ０００－４３６ｘ（２００４）０１一００６１—０９Ｒｅｓｅａｒｃｈｏｆｐａｔｔｅｒｎａｈｉｇｈｐｅｒｆｂ珊ａｎｃｅｍａｔｃｈｉｎｇａｌｇＯｒｉｔｈｍＴＩＡＮＪｕｎ—ｆｅｎｇ，ＨＵＡＮＧＪｉａｎ·ｃａｉ，ＤＵＲｕｉ—ｚｈｏｎｇ，ＺＨＡＩＪｉａｎ—ｑｉａｎｇ　（１ｎｓｔｌｔｕｋｏｆｃｏｍｐｕｋｒＮｅｔｗｏｒｂｌｋｈｎ０１０９ＨＨｅｂｅｉｕｎｉｖｅｍｉｔｙ，Ｂａｏｄｉｎｇ０７１００２，ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ｔｈｉｓｐａｐｅｒｓｔｕｄｉｅｓｔｌｌｅｍｅｍｏｄｏｆｐａｔｔｅｍｍａｔｃｈｉｎｇｉｎｉｎｔｒｕｓｉｏｎｄｅｔｅｃｔｉｏｎ，ａｎａｌｙｚｅｓｔｈｅｆａｕｌｔａｎｄｌａｃｋｏｆｔｈｅａｖｏｉｄｓｓｏｍｅｃｕｍｎｔｕｓｕａｌｍｅｔｈｏｄｓ蛐ｄｐｒｅｓｅｎｔｓｌａｃｋｓｒｅｓｕｍ“ｇｆｒｏｍｍｅｃｈａｎ百“ｇｏｆｔｈｉｓｍｅｍｏｄａ缸ｎａｒｙ一衄ｅ—ｂａｓｅｄａｕｔｏｍａｔｉｏｎｍｅｔｈｏｄ，ｗｈｉｃｈｔｈｅｎｏｄｅ砌ｏｕｎｔｍ打ａｄｍｏｎａｌ仃ｅｅｓｔｍｃｔｕｒｅＩｎｌｅｎｅｒｓａｄｄｉｔｉｏｎ，ｄｕ＾“ｇｍａｃｃｈｉ“ｇｊｕｍｐｓｓｏｍｅｗ岫ｕｎｓｕｃｃｅｓｓｆＩｌｌｉｎｆｏｎｎ柚ｏｎ，ｗｈｉｃｈｉｍｐｒｏｖｅｓｔｈｅｓＰｅｅｄＫｅｙｗｏｒｄｓ：ｎｅｔｗｏｒｋｓｅｃｕ＾ｔｙ；ｉｎｔｒＩｌｓｉｏｎｄｅｔｅｃ吐０ｎ；ｐａｎｅｍｍａｔｃｌｌｉ“ｇ；ｐｍｔｏｃｏｌａｎａｌｙｓｉｓ；ａｕｔｏｍａｔｉｏｎ１引言随着互联网技术的发展，网络自身的安全也显得越发重要。网络安全…的。一个主要的威胁就是通过网络对信息系统的入侵。网络入侵是指试图破坏信息系统的完整性、机密性或可信性的任何网络活动的集合。入侵检测系统（ＩＤｓ）”“１是防火墙的合理补充，成为维护网络安全的重要手段。它从计算机网络系统中的若干关键节点收集信息，并分析这些信息，检测网络中是否有违反安全策略的行为和遭到袭击的迹象，从而判断是否有网络入侵发生。信息收集之后的信号分析算法是影响入侵检测系统效率的重要因素。现在国内外对ＩＤｓ的研究很收稿日期：２００３．０５．２８：修订日期：２００３．０９．０９基金项目：“８６３”计划基金资助项目（２００ｌＡＡｌ４２０３０）万方数据　通情学报多，提出Ｊ，很多力法，比如譬家系统、统¨分析、人Ｉ．智能、模式匹配等。其中模式肛配方法斟其实用性越来越受到重视”’…。日前常见的模式Ｉ巧配算法存在效率低、误报漏报率高等缺点，不能适应高速网络的入侵检测。如ｓｎｏｒｔ…叫”算法，它为ＴｃＰ、ｕＤＰ、ＩｃＭＰ和ＩＰ等协议建立规则树，规则树由·维链表封ｌ成：规』ｌｌＩＪ头、规则项、函数指针。规则头主要包括ＩＰ地址和端口号，规则项主要包括匹配的内窬，甬数指针指向发现入侵发生后执行的动作。多个规则头组成‘个链，每个规１Ｊ！｜Ｊ头引导一个对应的规则项组成的链，每个规则项中由指针指向对应的执行幽数。ｓＪ】ｏｎ州Ｂｏｙｅ｝Ｍｏｏｒｅ匹配算法Ｉｌ“实现数据包的匹配。这种匹配策略只应用了在个规则内部已经匹配的信息，实现了跳转，并没有在多个规则之间实现跳跃，效率比较低。有限状态自动机算法是解决多模式匹配”””１的常用方法。它主要是在匹配前，对规则中要匹配的模式串集合进行预处理，转换成有限状态自动机，然后，对文本串扫描一次，就可以找出所匹配的串。入侵柃测中的模式匹配，是获取原始数据后，在规则库中搜索是否有匹配的规则，这也是‘种多模式匹配。本文提出了一种基于有限状态自动机的模式匹配算法。该自动机是一种树状结构“…，是对传统多模式匹配所依赖的树状结构改进后而构造的一种新型树结构，与之相适应的新算法改善了传统算法中构造速度慢、内存空间耗费大的缺点，提高了匹配速度。传统树型有限状态自动机算法采取的结构是：如果一个节点有ｎ个子树，那么该节点就应有ｎ个指针分别指向这ｎ个子树。在树的构造过程中，由于不能预先知道每个节点有几个分支，因此只能采取两种处理方法：（１）每次增加子节点时，重新分配父节点占用的内存空间。这种方法造成频繁的内存释放和分配操作，使树的构造速度大大降低。（２）每个节点部分配固定个数的指针空间，这个固定值足所有节点子树个数的最大值。这种方法会造成空间的极大浪费。此外，在树型结构的基础上本文还对快速多模式匹配算法”“进行了改进，将较长的模式串进行分解，只有当子模式匹配成功时，才对整个模式进行匹配，从而提高了匹配速度。　２三叉树表示的有限状态自动机的构造本文提出的ｊ叉树表示的是确定型有限状态自动机，用五元组表示就是自动机Ｍ＝（芷，￡，＾Ｓ，Ｚ）其巾，Ⅳ是一个有穷集，它是自动机中状态的集合，如图１中的数字就表示状态；三是一个有穷字母集，它的每个元素称为一个输入字符，包括所有可以识别的字符的总体；ｒ是转换函数，是在Ｋ×￡上的映像，即如果，（＆。，Ⅱ）＝女，（岛ＥＫ，女，Ｅ￡）就意味着，当前状态为岛，输入字符为Ⅱ时，将转换到下一个状态岛，我们把岛称作ｋ。的一个后继状态；ｓ是惟的一个初态，并且ｓ∈髟，在图１中状态“０”就是初态；ｚ是～个终态集，是足的一个真子集，在这里，构造的自动机出现ｚ中的一个元素时，就表示某个模式结束。自动机可以用图形的方式表示出来，但是本文所用的图形表示方法与传统的图形表示方法不同。首先，在传统方法中用状态图表示自动机，而在此用三叉树来描述：其次，这早的自动机构造的＿‘叉树除了终态节点之外，其它节点可能具有相同的状态。规则１为了与传统状态图进行区别，对三叉树中节点的状态规定如下：一ｉ叉树的根节点的状态为“ｓ”；万方数据　第】期…俊峰等：高效的模式匹配算法研究如果某节点’ｒ的状态为≈。，那么’ｚ’的左分支的根节点或中问分支的根节点的状态是通过，转换得到的，’ｚ’的√ｉ分支的根节点的状态也为ｋ，。依此类推可以确定所有节点的状态。规则２在构造二叉树过程中涉及到如何把某一个节点的次状态划分在左分支还是中间分支的问题，现规定如Ｆ：对于导致状态岛发生一次变化的所有字符按照不大于中间字符和大于中间字符分别分为两个集合＾和丑，』４中的元素导致的状态在岛左分支，Ｂ中的元素导致的状态在岛的中间分支。规则３为了便于添加节点或删除节点，将三叉树的节点，即自动机的状态作如下进一·步规定：在三叉树中的某一‘个节点‰的左分支中，导致与该分支的根节点具有相同状态的字符按照降序排列，并依此安置字符对应的状态：而岛的中间分支中，导致与此分支的根节点具有相同状态的字符按照升序排列，并依此安置字符对应的状态。添加节点或删除一个节点时，只需左分支向中间分支移动一一个节点，或中间节点向左分支移动一个节点。规则４三叉树的访问规则为：访问从初始状态开始进行，根据待检测字符还是中间分支；若某节点ｎ与输入待检测字符后的状态相同规则２确定ｎ的状态在左分支还是右分支；否则依此类推可以确定是否有模式相匹配。以入侵模式串集合｛ｃＧＩ．ＢＩＮ，ｃＧＩ－ＬＯｃ，ＭＯＤ—ＰＥＲＬ，ｓＣＲＩＰｓ，ｃＯＭＰｓ｝为例构造一颗ｊ叉树，如图１所示，给定一个待检测字符串序列，从三叉树的根结点开始，按照预定的访问方式进行匹配，就可以判断出该字符串序列中是否有包含在特征模式串集合中的模式串。要榆查一个字符序列是否可产生攻击行为时，首先要检查其是否与特征库中现有的特征串相匹配，其过程如下：从该字符串的某一个字符开始，并从三叉树的根结点即初始状态“ｏ”开始，查找字符，如果字符小于或等于字符“Ｍ”则转向左分支，大于“Ｍ”则转向中间分支，字符为空则转向右分支；以左分支为例说明各个分支的处理过程，在左分支中，若字符等于“Ｍ”，则第二个状态为此分支的根节点，即状态“ｌ”，否则，转向状态“ｌ”的右分支：若字符为“ｃ”，则第二个状态为“８”；假设字符为“ｃ”，下一个字符若小于或等于“Ｇ”则转向状态“８”的左分支，否则，转向它的中间分支；……依此类推就可以判断模式串是否匹配成功。冈１二二叉树结构的有限状杏机依据规则２确定下一个状态出现在左分支则检测下一个字符，检测的方法是：依据检测节点ｎ的右分支。　万方数据　通信学撤３模式匹配算法的描述在模式匹配算法中对模式串采取从后向前比较的方法。快速多模式匹配算法ｆＩ“匹配前对模式串集合进行预处理，把模式串集合转换成有限自动机，得到Ｇ０１’ｏ（ｓ，ｃ）””函数和ＯｕＴＰｕＴ（ｓ）”“函数，并计算ｓⅪＰ１（ｃ）和ｓＫｌＰ２（ｓ，ｃ）。其中，ｓ是某个状态；ｃ为某一个字符；ＧＯＴｏ（ｓ，ｃ）表示输入ｃ后ｓ转向的状态；ＯＵＴＰｕＴ（研表示输出状态ｓ；从后向前匹配时，如果与终态比较时失败，则跳转ｓＫＩＰ，（ｃ），如果不是在终态，而是其他状态，则跳转ＭＡｘ（ｓＫＩＰｌ（ｃ），ｓⅪＰ２（ｓ，ｃ））。在匹配过程中，匹配从ｓ：ｏ，扛ｍｆｎ砌（ｍ加肠Ｈ是模式串集合中最短模式串的长度），５［ｆ】开始０是待检测的字符串），根据Ｇ０１Ｄ函数进行。若匹配成功，涪ｆ＿ｌ；否则，如果ｓ＝０时，模式串集右移ｓｌ（ＩＰｌ（５［件ｌ】），即江ｉ＋ｓＫＩＰＩ（Ｊ［“１］）（ｉ为匹配失败的字符位置），若ｓ≠Ｏ，模式串集右移ＭＡｘ（ｓⅪＰ１（ｓ【沣ｌ】），ｓⅪＰ２（ｓ，ｓⅡ】））（此时，｛为模式串的最后一个字符对应的位置，７为匹配失败的字符的位置）。ｓⅪＰｌ（ｃ）和ｓⅪＰ２（ｓ，ｃ）的定义如下：ｃ，％一ｍｎ拓Ｈ匈＜％，１≤‘≤ｇ】ｓＫ皿（ｃ）』Ｍ矾｛帆一，＋１Ｉ剐力２ｌＩ血ｎｋｎ＋】ｓＫＩＰ２（ｓ，ｃ）＝ＭＩＮ｛ｄ≤Ⅲ，），１≤七≤曰｝ｃ出现在｛尸｝中ｃ不出现在｛尸）中Ｉ（１≤ｄ≤ｍｍｆ肼）且（ｄ习或Ｐｔ［Ｊ一棚＝ｃ），（（ｄ≥ｆ或Ｒ［ｆ＿ｄ］＝尸ｆ［ｆ］Ｊ，ｆｏｒ』＜ｆ其中，４是模式串集合中模式串的个数，Ｒ是第女个模式串，ｍ女是第女个模式串的长度。当字符串较长时，上面提到的算法将消耗比较多的时间，因为需要大量的工作计算ｓＫＩＰ．和ｓＩ（ＩＰ２的值；用较多的存储空间来跟踪它们值的变化。本文提出将较长模式进行分解的方法。该方法的理论依据是推论““：如果一个长为ｍ　的允许插入女个字符的模式存在匹配，则将模式分成Ｊ段时，必可以和其中一段匹配，并Ｈ．允许插入【￡们个字符。当模式串较长时，可以将该模式分解为若干个子模式，当其中的某‘个子模式匹配成功后，再进行全模式的匹配。试验证明：当子模式串约为１００个字符长度时，匹配的速度比较理想；匹配失败时，失败字符一般也在几十个字符之内。所以将一个模式进行分解时，分解后子模式的个数依据以下公式ｎ＿『甜的对象，如果此子模式匹配成功，再对整个模式进行匹配。㈣其中Ｈ是分解时子模式的个数，ｆ是模式的长度。子模式分好后，取第一个子模式作为匹配４模式匹配算法的实现模式匹配算法用ｃ语言实现如下：ｖｏｉｄＰａｔｔｅｍＭａｔｃｈ（ｃｈａｒ＋ｓ，ｉｎｔｎ，ｉｎｔｍｉｎｌｅｎ，ＴｒｉｎａｒｙＴｒｅｅ柚ｅａｄｅｒ）ｆ／／ｓ是待检测的字符串，ｎ是字符串的长度，／／ｍｉｎｌｅｎ是模式串集合中最短模式的长度，，ｍｅａｄｅｒ是三叉树的头指针，即其初始状态，相当于图１状态“Ｏ”ｉｎｔｉ，ｉ：，，记载匹配过程中，待检测字符串的位置，／记载模式串的状态ＴｒｉｎａｒｖＴｒｅｅ＋ｓ：ＴｒｉｎａｒｙＴｒｅｅ４ｎｓ；万方数据　第ｌ期田俊峰等：高效的模式匹配算法研究　万　方数据ｉ＝ｍｉｎＩｅｎ：Ｓ＝ｈｅａｄｅｒ：ｊ＝缸ｗｈｉｌｅ“＜＝ｎ－１１｛ｎｓ＝ＭａｔｃｈＧｏＴｏ（ｓ，ｓＤ】）；／，字符匹配并且确定状态ｉｆ（ｎｓ＆＆ｎｓｋｈｅａｄｅｎｆＳ＝ｎｓ：ｉｆ（０ｕｔｐｕｔ（Ｓ）！＝ＮＵＬＬ），／输出状态，如果没有输出，返回ＮｕＬＬ埘ｎｔｆ（”％ｄ”Ｊ）；ｊｆ（ｓ．ｓｔａｔ‘Ｊｓ—ＳＵｃｃＥｓｓ），，Ｓ．ｓｃａｃｕｓ等于ｓｕｃｃＥＳｓ表明该状态为自动机，，的结束状态，等于ｓｕＢＳＴＲＩＮＧｓｕｃｃＥｓｓ时／／表明是子模式匹配成功，需要进一步进行总，，模式的匹配。（ｐｍ饿”Ｍａｔｃｈｉｎｇｉｓｓｕｃｃｅｓｓｆｕｌ”）；ｂｒｅａｋ：）ｅｌｓｅ｛ｉｆ（Ｓ．Ｓｔａｍｓ＝＝ＳＵＢＳＴＲＩＮＧＳＵＣＣＥＳＳ）Ｍａｌｃｈｗｈｏｌｅｓ蛹ｎｇ（）；／／匹配整个模式串】ｊ－＿；）ｅｌｓｅ｛ｉ“Ｓ：＝ｈｅａｄｅｒ）｛ｉ．ｉ＋ｓｋｉｐｌ（ｓ［“１］）；｝ｅｌｓｅｆｌ＝ｉ＋ｍ“（∞ｐ１（ｓ【ｌ＋１】），啦ｐ２（ｓ，ｓＤ】））；Ｓ＝ｈｅａｄｅｒ：｝ｊ＝ｉ；）｝ｓｋｉｐｌ（ｃ）和ｓｋｉｐ２（ｓ，ｃ）的具体实现可以参见文献【１３】。通靠ｉ学报２０㈣ｑ５性能分析５．１漏报、误报分析入侵检测中的传统模式匹配技术¨７１往往是当读取一个数据包之后，首先从数据包的第个字节开始提取Ｌｊ规则库ｃ｛，的第·个攻击特征串等长的一绸字节与第个攻击特征串比对，如果两组字节相同，则视为检测到一次攻击；如果两组字节不同，则从数据包的第．个宁节丌始提取与攻击特征串等长的‘组『宁：节与攻击特征串比对。比对过程重复进行，每次后移个字节卣到数据包的每个宁节都比对完毕。最后，将数据包与特征库中下一个攻击特征串进行匹配。由此我们可以看出，模式匹配技术的效率由比对次数决定，其每秒比对次数为足＝ｎ。×ｎｆ×Ｋｆ×以，（２）其中，ｎ。表示攻击特征字节数，ｍ表示数据包字节数，仇表示网络中每秒数据包数量，ｎ，表示特征库中攻击特征数量。若平均一个攻击特征有２０ｂｙｔｅ，一个数据包有３００ｂｙｔｅ，网络流量每秒３０，０００数据包，特征库有１０００个攻击特征，那么据上面公式可知比对次数≈为１８００亿次／ｓ。当运算能力不能满足时，入侵检测系统就会忽略‘些数据包，造成漏报。此外，传统的入侵检测系统也容易造成误报。由于原始数据包括了多个字段的内容，可能会造成一种数据包中的一段字节串与某。攻击特征吻合但实际上这段字节串根本不是攻击的情况，即发生误报。５．２匹配效率分析本文提出的针对入侵榆测的模式匹配是在协议分析”１的基础上进行的。协议分析技术利用删络协议的高度规则性快速探测攻击的存在，包括协议解码、命令解析和防议校验等技术。　协议解码技术主要确定数据所属的协议；命令解析器使用的命令解析技术可以对各种上层防议进行解析，识别同一命令可能的不同变种；协议校验技术可以将分散的ＩＰ碎片重新组合，然后进行分析，还可以检查不同层的协议域来寻找非法或可疑内容，如未被使用的域、１Ｆ法值、不适当选项、不规则序列号和ｃＲｃ修改等等。可以通过计算‘个数据包的比对次数来说明采取协议分析的优点。假设在采取传统字符匹配算法的前提下，即逐个字符进行比列，个数据包的比列次数为七’＝ｎⅢדｚ×Ｈｒ（３）ｎ。、ｍ唧的含义与ｒ面提到的一样。采取协议分析的方法之后，由于不再是对整个数据包进行匹配，所以ｎｆ将减小，比如，若可疑数据在ＴｃＰ头部分，就不必比较ＴｃＰ的数据区的数据和ＩＰ头部的数据；由于协议分析将匹配的范围缩小在具体的协议范围，甚至缩小到某条命令的范围，因而Ｈ，也将减小。采取协议分析之后，一个数据包的比对次数为ｔ·：ｎ。×（上。仰）×（上×ｎ，）ｎ垅（４）由于数据包的各个部分不同，当匹配数据区时，ｎ的取值比较小；当匹配ＩＰ头部时，ｎ的取值就比较大。一一个ＴｃＰ数据包的最火长度为６５５３５ｂｙｔｅ，ＩＰ头为２０ｂｙｔｅ，所以有ｎＥ（１，３２７７）：肋、议分析将规则库分成ｒ小同部分，ｍ的取值与协议的个数以及协议当中的命令的个数有关，比如ｓｎｏｒｔ曾列出约１７３６条规则，其中，关于Ｎｅｔｂｉｏｓ的攻击规则为１４条，如果利用１ｊｊ、议分析方法，确定攻击所属协议为Ｎｅｔｂｉｏｓ后，ｍ取值约为１２４。万方数据　第ｌ期…俊峰等：高敏的模式旺配算法研究根据Ｌ面分析，采用相同匹配算法的前提Ｆ，进行协议分析之后，对一个数据包的比对可以由原来的ｒ亿次减少到几Ⅱ次甚至儿ｆ‘次。速度的加快，将减小漏报的町能性。此外由于协议分析缩小了匹配的范田，避免了原来数据包巾将其他字段１１１不是入侵的数据误认为入侵的情况，即减小了误报的可能，从而有效地提高了算法的匹配效率。协泌分析的过程实际是通过对数据包的关键宁段进行分析确定的，这些字段的位胃、ｋ度范围是受约束的。本文采用散列函数的方法对数据包进行处理。散列函数的构造过程如下：１）对分析字段中出现的各个字符设置数字对照表，比如：ａｂ２ｃｄ５ｅｆ７…………１４６２）根据被分析字段出现的字符，分别赋予对应的数字，最终将形成一个数字序列。比如，设被分析的字段对应的字符序列为“ｂｅａｄ”，则通过查找数字对照表，得到数字序列２６１５。３）按照折叠法，处理数字序列。比如，将出现的数字序列从右至左，取３位为一组分成若手组，然后将各个部分相加，得到和值，采用上述过程对２６１５进行处理，其结果为６】７。４）对上述计算出的结果对ｐ求余，其中，ｐ是大于协议或命令个数的质数。５）如果计算出的结果出现了冲突，则按照链地址法进行处理。首先，对出现的各种待检测字段按照上述散列函数过程计算初值，构造散列表。当收到～个数据包之后，对被分析字段按照散列函数的过程进行处理，然后查找散列表，确定数据包所属的协议、包的序列号、使用的命令等内容。５．３空间复杂度、时间复杂度分析本文在引言部分曾提到，传统树型有限状态自动机算法采取的结构，在构造树的过程中存在不能确定分支的问题，并提出了两种解决方法。但采取第一种方法，会造成效率下降：采取第二二种方法，会造成空间浪费。三叉树结构不存在重新分配节点空间的问题，从而避免丁第一种方法的缺点。第二种方法中，每个节点分配固定数目的分支，指向各个次状态，会造成大量分支的空闲。假设分支的数目为ｃ，一个状态“ｘ”的次状态数目为ｄ，那么，此状态对应的节点的空闲分支数目ｒ为ｒ＝ｃ＿ｏｆ５、　三叉树结构中，每个节点的三个分支是以两个次状态和一个相同状态出现的，如果状态“ｚ”对应的节点的右分支为空，则此节点的空闲分支数目为止任ｄ≥２ｄ＝ｌｄ＝０（６）如果状态“ｚ”对应的节点的右分支不为空，则此节点的空闲分支还要减少‘个。但相应地，若分别把ｄ≥２、ｄ＝１或ｄ－Ｏ代入式（５），所得的节点的空闲分支的数目可能大得多。比如，攻击者常常以协议命令来实现入侵，此时，特征串大都是以英文字母组成的序列出现的，这种情况下取２６个字母作为分支数目，即ｃ＝２６，则空闲分支数目分别为ｒ≤２４、ｒ＝２５或ｒ＝２６。了玎见，与第二种方法相比，三叉树结构明显提高了分支的利用率，即降低了空问复杂度。三叉树方式使节点不必预先设置指针，提高了空间利用率。采取本文提出的算法可以提高匹配效率。设待检测数据Ａ长度为ｎ，模式集－ｆ，模式的个万方数据　通信学报２００４≈‘数为ｍ，模式串的长度为ｆ。（ｆ＿ｌ，２，…ｍ），模式集中的最小模式的长度为ｍｆｎ船ｎ，最大长度卅∑ｆｆ为ｍ—ｋｎ。以ｓｎｏｒｔ算法为例，令ｆ＿』三Ｌ。最坏的情况是模式集中的每一个模式及其每一ｍ个字符都进行匹配，这时候的时间复杂度是ｏｒｎｚｍＪ。最好的情况是只匹配第一个模式，并且匹配失败后跳转的长度为整个模式长度，此时的时间复杂度是Ｄｆ，以ｌＪ，如果ｆｌ＝ｍ胁据ｎ，则此时的时间复杂度就是０ｆ，砌ｚｆｎｆｅｎＪ。平均情况下，时间复杂度与字符出现的概率有关。文献【１８】中提出，平均情况下算法的性能通过发现不匹配字符所花的代价和发现该不匹配后能够移动１的距离之比的概率平均值来考察。设每个模式匹配成功的概率都是一样的，即为二，则ｓｎｏｒｔ，ｎ算法的性能平均为，：上萝争∑ｃ（Ｊ）‰（，）‘‘ｍ智智∑Ｐ（州∑女·‰（Ｊ，女）式中，ｃ（．７）为某个模式ｘ中查找，个字符（从后向前）所花的代价；Ｒ。（．７）为在ｘ查找（从后向前）到第，个字符时才发现不匹配的概率；尸。Ｈ。（Ｊ，妨为在ｘ查找（从后向前）到第Ｊ个字符时发现不匹配后，能够跳过≈个字符的概率；Ｐ（７）为ｘ中出现第Ｊ个字符的概率。采用快速多模式匹配算法”…，最优情况下的时间复杂度为０（＂“ｍ抽ｆｍ＋１））；在最坏情况　下的时间复杂度为Ｄｍ·ｍ“ｆＭ）；平均情况下，时间复杂度与字符出现的概率有关，根据文献【１７］可以得出其性能为ｐ’＝而ｉ—曼焉蒜丁——一∑尸协Ｉ∑¨只坤’（Ｊ，≈）ｌ『＿０ｔ＝０∑ｃ’（，）·只。’（Ｊ）（８）式中，ｃ’（，）为查找一１个字符（从后向前）所花的代价；Ｐ’。。（，）为在查找（从后向前）到第一１个字符时发现才不匹配的概率；Ｐ’。Ｈ，（工妨为在查找（从后向前）到第一１个字符时发现不匹配后，能够跳过ｔ个字符的概率；Ｐ，（Ｊ）为第Ｊ个字符出现的概率。当一个模式串比较长时，将它分解为多个子模式，对其中一个子模式进行匹配，如果匹配成功，再对整个模式进行匹配。取字模式串的长度为１００个字符，所以此时的性能为ｐ”－ｐ’＋（１’一１００）×ｒ（９）其中，ｒ为较长的字符串的长度，ｒ是子模式匹配成功的个数。通过上面的分析可以看出，本文提出的方法可以有效的提高匹配速度，减小漏报、误报的可能性。６结束语本文对入侵检测中的模式匹配进行了研究，在协议分析的基础上，提出了一种基于三叉万方数据　第ｌ划田俊峰等：高教的模式匹配算法研究树的自动机方法，并且模式串采用从后向前的匹配策略。如果模式串比较长＝，则将模式串分成若干个子模式。在匹配过程中，如果匹配失败，则利用匹配信息，跳过若干字节继续进行操作，提高了ｒ匹配效率。参考文献…曾志峰，杨义先网络安全的笈腱与研究【Ｊ１讨算机工程～应用，２０００，１０：ｌ一３【２】ｆ３】【４】【５】ｆ６】ｆｌｌＩ全眺，姚围祥网络安争需求分析及安全策略研究【Ｊ】计算机工程，２０００，２６（６）５６—５８蒋建存．弓ｆ¨Ａ，任党恩，卿斯坡网络安全入侵捡测：研究综述［Ｊ】软件学报，２０吣】】（】Ｉ）：】４６０．ｊ４６６张亮，蒋东兴，徐时新主机网络安全及其关键技术研究【Ｊ】计算机］程与应用，２００１．１０：４２一“乇晓程，刘恩德，谢小权网络入侵检测系统的研究【Ｊ】计算机工程与科学，２０００，２２（４）：３０一”ＲｏｗＥＮｃ，ｓｃＨｌＡｖｏｓＡｎｍ嘲１嘻ｅｎｌｔｕｔｏｒｆｏｒｌｎ廿ｕｓｌｏｎｄｅｔｅｃｔｌｏｎｃｏｍｐｕｋｒｓｙｓｔ锄ｓｆＥＢ／０Ｕｈ叩，『Ｗｗｗｎｐｓｎａｖｙｍｌｌ，ｐｅｏｐｌｅ，ｆａｃｕｌｑ，ｒｏｗ酣ｌｄｔｕ幻Ｌｈｔｍｌ【７】ｆ８］ｃ０ＭＥＲＤ，ＳＥＴＨＩＲＴｈｅｃｏｍｐｌｅｘｉｔｙＴｏｆｔｒｉｅｌｎｄｅｘｃｏｎｓｔｍｃｂｏｎ［Ｊ】ＡｃＭ，１９７７，２４（３）：４２８—“０ＤＥＭＡｌＮＥＰＡＤ，ＲｏＴｗＩＴＴｓｔｏｒａｇｅｏｐｔｉｍｌｚａｔｉｏｎ０ｆ”ｅｅｓｔｎｌｃｔｕ删６ｌｅｓ托ｐ坼ｓｅｍｉ岵ｄｅｓ晡ｐＩｏｒｓｅｔｓ【Ａ】．Ｐｒｏｃ２０７—２１７ＡｃＭｓＩＧＦＩＤＥＴｗｏｒｋｓｈｏｐｏｎＤａｔａＤｅｓｃｄｐｔｉｏｎ，Ａｃｃｅｓｓ，ａｎｄＣｏｎⅡｏｌ【ｃ】１９７１［９１ＤｅｓａｉＮＩｎｃ啪ｓｉｎｇｐｅｆｆｏｎｎａｎｃｅｈｉｇｈｓｐｅｅｄＮＩＤｓ［ＥＢ，０Ｌ】ｈ婶：Ⅳｗｗｗｌｍｕｘｓｅｃｕ＾ｔｙｃｏｍ厅ｅｓｏｕｒｃｅ＿ｎＩｅｓ＾ｎ咖ｓｉｏｎ—ｄｅｔｅｃｔｌｏ“Ｉｎｃ托ａｓｌｎｇ～Ｐｃ怕丌ｎａｌｌｃｅ＿ｌｎ—Ｈｌ曲～ｓｐｃｅｄ—ＮＩＤｓｐｄｆ０ｃｏＩＴｃＪ，ｓＩＡＮＩＦｏＲＤｓ，ＭｃＡＬＥＲＮＥＹＪＴ０ｗ删ｓ‰ｔｅｒｓｔｒｉｎｇｍａ曲ｉｎｇｆｏｆｉｎ叽ｓｉｏｎｄｅｆｅｃＩｌｏｎｏｒｅｘｃｅｅｄｊ“ｇｍｅｓｐｅｅｄｏｆｓｎｏｎ【ＥＢ，ｏＬ】ｈｎｐ，，ｗｗ砒ｓｉＩｉｃｏｎｄｅ岛ｎｓｅｃｏｍＡｏＲｗａｒｅ位ｂⅡ以ｐｅｃｄ—ｏｆ－ｓｎｏｒＬＤ３－１６一珈１呲ＦＩｓＫＭＡｐｐ｝扣丑ｇｆａｓｆｓ撕雌埘ａ蛐ｊｎｇｃｏ抽昀ｓｉ。丑ｄｅ∽ｄｏｎｆＥＢ，ｏＬｌｈ拄ｐ：恤Ｍｉｃ．１衄ｌｇｏｖ，ｍ疗ｓｋ，ｐａｐ邮船打ｎａｋｈ瑚ｄ李信满，赵夫哲，赵宏．刘积仁基于应用的高速网络入侵检测系统研究［Ｊ】通信学报，２００２，２３（９）：ｌ一７ｐｄｆ嘏佩华，乇永成，刘功申基于有序二叉树的多模式匹配算法ｍ计算机科学，２００２，２９（１ｊ）：６５－６８　许震，王永成．沈洲一种快速的多模式字符串匹配算法ＩＪｌＥ海交通大学学报，２００２，３６（４）５１６—５２０；８沈洲，乇永成，许一震一种面向中文的快速字串多模式匹配算法Ⅱ】上海交通大学学报，２００１，３５（９）：１２８５一１２８９袁华稍．蔡军，葛家翔用多模式匹配的方法设｜十基于网络的工亡吲刀计算机工程，２００２，２８（２）ｌｊ２．１５４刘志刚ＢＯＹＥＲＲ“保安”质变——降低ＩＤｓ误报、漏报率的新技术【ＥＢ，０Ｕｓ，Ｍ００ＲＥＪｓｈｔ中：Ⅳｗｗｗｐｃｗｏｄｄｃｏｍｃ埘ｓｓｕ眈００２ｍ２驯２４０８ｂａｓｐＡ缸ｔｓｍｎｇｓｅａｒｃｈｌ“ｇａｌｇｏ珊Ｉｌｎ【Ｊ】ｃｏｍｍｕｎＡｃＭ，１９７７．２０（１０）：７６２—７７２作者简介田俊峰（１９６５．），男，河北保定人，河北大学教授，主要研究方向为信息安全、网络技术。黄建才（１９７７一），男，河北保定人，河北大学研究生，主要研究方向为信息安全。杜瑞忠（１９７６．），男，河北沧州人，河北大学助教，主要研究方向为网络技术。翟建强（１９７３一），男，河北邢台人，河北大学研究生，主要研究方向为网络技术。万方数据　高效的模式匹配算法研究

作者：作者单位：刊名：英文刊名：年，卷(期)：被引用次数：

田俊峰， 黄建才， 杜瑞忠， 翟建强

河北大学网络技术研究所,河北,保定,071002通信学报

JOURNAL OF CHINA INSTITUTE OF COMMUNICATIONS2004,25(1)12次

1.蒋建春;马恒太;任党恩;卿斯汉 网络安全入侵检测:研究综述[期刊论文]-软件学报 2000(11)2.何全胜;姚国祥 网络安全需求分析及安全策略研究[期刊论文]-计算机工程 2000(06)3.曾志峰;杨义先 网络安全的发展与研究[期刊论文]-计算机工程与应用 2000(10)4.Desai N Increasing performance in high speed NIDS

5.DEMAINE PAD;ROTWITr T Storage optimization of tree structured files representing destriptor sets1971

6.Comer D;SETHI R The complexity of trie index construction 1977(03)

7.Rowe N C;SCHIAVO S An intelligent tutor for intrusion detection on computer systems8.Boyer R S;MOORE J S A fast string searching algorithm[外文期刊] 1977(10)9.刘志刚 \"保安\"质变-降低IDS误报、漏报率的新技术

10.袁华鹏;蔡军;葛家翔 用多模式匹配的方法设计基于网络的IDS[期刊论文]-计算机工程 2002(02)11.沈洲;王永成;许一震 一种面向中文的快速字串多模式匹配算法[期刊论文]-上海交通大学学报 2001(09)12.许一震;王永成;沈洲 一种快速的多模式字符串匹配算法[期刊论文]-上海交通大学学报 2002(04)13.胡佩华;王永成;刘功申 基于有序二叉树的多模式匹配算法[期刊论文]-计算机科学 2002(11)14.李信满;赵大哲;赵宏;刘积仁 基于应用的高速网络入侵检测系统研究[期刊论文]-通信学报 2002(09)15.Fisk M Applying fast suing matching to intrusion detection

16.Coit C J;STANIFORD S;MCALERNEY J Towards faster string matching for intrusion detection orexceeding the speed of Snort

17.王晓程;刘恩德;谢小权 网络入侵检测系统的研究[期刊论文]-计算机工程与科学 2000(04)18.张亮;蒋东兴;徐时新 主机网络安全及其关键技术研究[期刊论文]-计算机工程与应用 2001(10)

1.陈牮华 网络入侵检测系统中的模式匹配算法优化研究[期刊论文]-计算机仿真 2011(2)2.史志才.夏永祥 高速网络环境下的入侵检测技术研究综述[期刊论文]-计算机应用研究 2010(5)

3.韩江洪.潘晓明.魏振春.刘小平.孙安 基于树型有限自动机的DES规则匹配算法研究[期刊论文]-系统仿真学报2010(8)

4.王文奇.郑秋生.吴婷.李伟华 高速入侵检测研究[期刊论文]-计算机工程与设计 2008(14)

5.许占文.王鹤翔.张锦 一种神经网络和模式匹配相结合的入侵检测系统[期刊论文]-沈阳工业大学学报 2007(3)6.王文奇 入侵检测与安全防御协同控制研究[学位论文]博士 2006

7.王永杰.鲜明.王国玉.肖顺平 基于指纹分析的Web服务探测技术[期刊论文]-计算机工程 2005(17)8.肖潇 基于主机用户行为的入侵检测技术研究[学位论文]硕士 2005

9.王秀芳 基于协议分析技术的入侵检测研究与应用[学位论文]硕士 200510.黄金莲 网络入侵检测系统中模式匹配算法的研究[学位论文]硕士 200511.周勇 神经网络与SNORT融合的入侵检测系统研究与应用[学位论文]硕士 200512.乔瑞 基于移动代理技术和协议分析技术的入侵检测系统[学位论文]硕士 2005

本文链接：http://d.g.wanfangdata.com.cn/Periodical_txxb200401008.aspx