快速高效的模式匹配算法的剖析与改进

计算机工程与设计ｃｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇ踟ｄ・信息安全技术・ＤｅｓｉｇＴｌ２００９，３０（１１）２６４９快速高效的模式匹配算法的剖析与改进王杰，刘亚宾，石成辉（郑州大学电气工程学院，河南郑州４５０００１）摘要：考虑到处理性能和内存开销两大因素，模式匹配成为网络入侵检测系统（ＮＩＤｓ）中最为关键的一环，而现有内存消耗较少的算法性能一般较差。因此，提出一种专为入侵检测领域设计的Ｍｏｄｉｆｉｅｄ．Ｐｉ啪ｈａ（ＭＰ）算法，它基于排斥思想，并采用位图法、优化高速缓存和状态重排思想对Ｐｍｈａ算法中的哈希表进行了改进，进一步减少了匹配步骤和内存访问次数，极大地提升了模式匹配的效率。实验结果表明，相对目前先进的模式匹配算法，ＭＰ算法能显著提升ｓｎｏｒｔ的性能，能减少ｌＯ．８％～３６．７％的处理时间，节省５．６—络一３８．９％的内存使用．关键词：ＭＰ算法；网络入侵检测系统；模式匹配；特征检测；住图中图法分类号：ＴＰ３９３．０８文献标识码：Ａ文章编号：１０００．７０２４（２００９）１１．２６４９一０３ＡｎａｔｏｍｙａｎｄｉｍｐｒｏＶｅｍｅｎｔｏｆｆａｓｔａｎｄｍｅｍｏｒｙ－ｅｍｃｉｅｎｔｐａｔｔｅｍｍａｔｃｈｉｎｇａｌｇｏｒｉｔｈｍＷＡＮＧ（ＳｃｈｏｏｌＪｉｅ，ＬｒＵＹａ－ｂｉＩｌ，ＺｈｅｎｇｚｈｏｕＳＨＩＣｈｅｎｇ－ｈｕｉＺｈｅｎｇｚｈｏｕ４５０００ｌ，ｔ１１ｅｏｆＥｌｅｃｔｒｉｃａｌＥｎｇｉｎｅｅｒｉＩｌｇ，ｉｌｌｔｏＵｎｉＶｅｒｓｉ饥Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ｔ敬ｉｌｌｇｐｒｏｃｅｓｓｉｎｇ锄ｄｍ锄ｏｒｙｒｅｓｏｕｒｃｅｓＮＩＤｓｅｓ，ｂｕｔｔｈｅｅｘｉｓｔｅｄｐａｔ锄－ｍａｌｃｈｉｎｇａｌｇｏｒｉｔｈｍｓｗｈｉｃｈｃｏｎｓｕｍｅｄＩｅｓｓｍｅｍｏ叫ｇｉｖｅｓｐｏｏｒｐｅｄ．ｏｒｍａｎｃｅｇｅｎｅｍｌｌｙ．Ｍ０ｄｉｆｉｅｄ－Ｐｉ鼬ａｐ砒哪ｍａｔｃｈｉｎｇｔａｉｌｏｒｅｄａｃｃｏ嘣，ｐａｔｔ锄ｍａｔｃｈｉｎｇｈ勰ｂｅｃｏｍｅｍｏｓｔｃｒｎｉｃａｌｐａｒｔｏｆｓｉ印砷ｕ陀．ｂａｓｅｄ（ＭＰ），粕ｉｍｐｒｏｖｅｄａｌｇｏｒｉｔｌｌｍｆｏｒｍｅｒａｒｅｓｔｆ研ｉｎ仃ｕｓｉ∞ｄｅ踟ｉｏ玛ｐａｔｔ锄ｗｉｌｌｉｓｄｅｖｅｌｏｐｅｄ．Ｉｔｉｓｂａｓｅｄｏｎｔｈｅｏｂｓｅｎｒ“ｏｎｔＩｌａｔｉｆａｌ－ｓｕｂｓ仃证ｇｏｆａｐａｔｔｅｍｄ∞ｓｎｏｔ印ｐｅ虬ｔ１１朗ｔｈｅｗｈｏｌｅｄｅｆｉｎｊｔｅｌｙｎｏｔｍａｔｃｈ．Ｔｏｂｃｔｔ既ｔＩｌｅｈ弱ｈｔａｂｌｅｏｆｐ眦ｈａｇ嘶ｔｈ鸭ｔｌ把武！ｔｈｏｄｍ蛐ｇｍ即ｔａｌ５．６％ｔｏｏｆｂｉｎｌｌ印ｓ锄ｄｔｌｌｅｔｈｏｕｇｌｌｔｏｆ０ｐｔｉｍｉｚｅｄｃａｃｈｅ彻ｄｒｅ盯ｍｎｇｉｎｇｓｔａｔｅｓｉｓｕ∞ｄ．Ｂｙｌｌｓｉｎｇｔｌｌｅｐｒｏｐｏｓｅｄｍｅｔｈｏｄ，ｔｈｅｓｔ印柚ｄｔｈｅｍｅｍｏ叫ａｃｃｅｓｓａ舱ｅＶｉｄ舶ｔｌｙｍｄｕｃｅｄ，锄ｄｔｈｅｐａｔｔｅｍｍａｔｃｈｉｎｇｅｍｃｉ∞ｃｙｉｓｐｒｏｍｏｔｅｄ朗。咖。吣ｌｙ．Ｔｈｅｅｘｐｅｒｉ—ＭＰａｌｇｏｒｉｔｈｍｃ锄ｅｎｈ锄ｃｅｔｈｅｒｃｓｕｌｔｓｉｎｄｉｃａｔｅｔｈａｔ３８．９％ｉｎ咖ｓｐｅｒｆｏ姗柚ｃｅｏｆＳｎｏｒｔｂｙｌ０．８％ｔｏ３６．７％ｉｎｔｅｍｓｏｆｐｒｏｃｅｓｓｉｌｌｇｔｉｍｅ锄ｄｂｙｏｆｍｅｍｏｒｙｕｓａｇｅｃ伽１ｐａ心ｄｔｏｅ）【ｉｓｔｉｎｇｓｔａｔｅ—ｏｆ＿ｔｈｅ－ａｎａｌｇｏｒｉｔｈｍｓ．Ｋｅｙｗｏｒｄｓ：ｍｏｄｉｆｉｅｄ＿ｐｉｒａｌｌｌｌａａｌｇｏｒｉ她；ＮＩＤＳ；ｐａｎｅｍｍａｔｃｈｉｎｇ；ｓｉ母ｌａｔｕｒｅ－ｂａ∞ｄ出惦ｃｔｉｏｎ；ｂｉｎｌｌ印法）和基于排斥的Ｅ２）【Ｂｏ川算法与Ｐｉ删１ｈ∥算法等。１．１０引言Ｅ２ｘＢ算法由于模式匹配需要对数据包负荷进行完全检测…，简单的匹配也需检测数据包的包头信息，因此模式匹配对入侵检测系统的性能影响很大。研究表明㈨，花在模式匹配上的处理时间约占总处理时间的３０％。在某些情况下，如在Ｗ曲应用密集的流量中，这一比例会高达８０％。此外，随着规则集的增大，入侵检测系统对内存的需求会更高。同时，鉴于网速逐年递增，快速而高效的模式匹配算法亟待研究蜘。Ｅ２ｘＢ算法专为入侵检测特殊需求而设计，同下述Ｐｉ啪ｌｌａ算法类似，它也是基于排斥思想：若欲检测输入字符串环包含字符串Ｐ的子串，则字符串丁必不包含字符串Ｐ。用集合论公式证明该命题的真理性：因ｐ尸，尸印－＞聊，则ｒ牛ｐ，Ｐ印．＞肼尸（其中，“＞”为“集合包含”符号）。如果所有ｐ均为７’的子串，则视为一次疑似匹配，之后调用标准模式匹配算法如Ｂ删判定Ｐ是否为ｒ的子串。该算法借助触发位图（ｏｃｃｕｒ锄ｃｅｍ印）增强匹配效率，并可以使用任意位长的码元（ｅｌｅｍｅｎｔｓ），但码元大小的选取需要采取一个折衷方案：码元较长能减少误匹配率，但会相应地增加触发位图的长度，导致漏匹配率增加和性能降低。１模式匹配算法‘人侵检测系统中使用的典型匹配算法有Ｂｏｙ盯－Ｍｏｏｒｅ¨ｌ，Ｍｏｄｉｆｉｅｄ、Ⅳｕ－Ｍ卸ｂｅ一“（Ｓｎｏｎ２．０以后版本中默认的模式匹配算收稿日期：２００８一０６．１２：修订日期：２００９．０２．１６。基金项目：河南省杰出人才创新基金项目（０７４２００５１００１３）；河南省教育厅自然科学基金项目（２００７５２００４８）。作者简介：王杰（１９５９一），男，河南周口人，博士，教授，博士生导师，研究方向为智能控制与智能计算、信息与计算机网络安全；（１９８３一），男，河南周口人．硕士研究生，研究方向为信息与计算机网络安全、模式匹配算法ｆ刘亚宾石成辉（１９８２一）。男．河南信阳人，硕士研究生．研究方向为ｉＩ算机网络与信息安全、智能化入侵防御系统。Ｅ—ｍａｉｌ：ＬＨＤＡＳ２００６＠１６３．伽万方数据２６５０２００９，３０（１１）计算机工程与设计ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＤｅｓｉ印１．２Ｐｉｒａｎｈａ算法Ｐｉｎｎｈａ算法思想：若在数据包负荷内发现一个模式中最少使用的四字节子串，则认为模式匹配成功，即每一个模式都可以由它的代表性的四字节子串来代表。该算法本身只处理其长度大于或等于四字节的模式，而小于四字节的模式被单独处理。其具体实现分为预处理和搜索两个阶段。１．２．１预处理阶段Ｐｉ础将每一字节对齐的模式看作３２位的子模式集合，以便使用整数值进行快速运算。如模式“／ａｄｍｉｎ．ｅｘｅ”（Ｒ１）可看作“／ａｄｍ”，“ａｄｎｌｉ”，“ｄｍｉｎ”，“ｍｉｎ．”，“ｉ１１．ｅ”，“ｎ．ｅｘ”和“．ｅｘｅＪ，的集合。模式匹配由ＡＮＤ运算符组成的公式表示，每一种模式表示一个门，而门由多个３２位的子模式组成，每一个输入表示在数据包负荷中是否有３２位的子模式出现。门初始输入值均置０，并随着子模式字符序列在数据包中的出现做出相应变化。当输出门置为ｌ时，认为是一次疑似匹配。为了快速查找哪些输入被置为ｌ，需要维护一张记录所有模式的４．ｂｙｔｅ子模式字符序列的索引表。假定索引表中只有两个模式，一个是“枷ｍｉｌｌ．ｅｘｅ”（Ｒ１），另一个是“／ａｄｍｉｎ．ｓｈ”（Ｒ２），如图ｌ所示。字符序列“棚ｍ”，“ａｄｍｉ”，“ｄｍｉｎ”和“ｍｉｎ．”在Ｒ１和Ｒ２中均出现，而“．ｅｘｅ”，“ｉｎ．ｅ”和“ｎ．ｅｘ，，只属于Ｒｌ，“ｉｎ．ｓ”和“ｎ．ｓｈ”只属于Ｒ２，当有一项出现在索引表中时，相应的输入就会做出相应切换。例如，当数据包的负荷为“ｍｉｎ．既ｅ”时，则首先读取索引表中的“ｍｉｎ．”，它所对应Ｒｌ和Ｉ匕的输入将做出相应切换，之后依次读取“ｉｎ．ｅ”，“ｎ．ｅｘ”和“．瓯ｅ”，它们所对应Ｒｌ的输入也将做出相应切换。—偷＋＼√／ａｄｍ—儡卜锄＼√耐ｍｉＨ瓮卜讲‘俞＼√ｄｍｉｎ诉＼√—ｉ涮刷＼－／Ｉｎ．Ｃ＼—／ｎ．ｅＸ—ｉ沁一＼—／，ａｄｍＵ黜Ｅ．ｅＸｅ叫俞一∑￡一到睁’景１：＿卜二兮Ｉｎ．ＳＨｎ．ｃｘＰｎ．ｓｈ卜一ｎｓｈＰ图ｌ优化前后的模式索引表和门尽管使用门方法具有较低的疑似匹配率，但其性能依然很差，这是由于大部分开销都用于判定一个模式是否被匹配上。为了减少检查的步骤和内存的使用，对索引表进行优化：留Ｒ１的具有代表性的子模式字符“ｎ．ｅｘ”和Ｒ２的具有代表性的子模式字符“ｎ．ｓｈ”，优化后的索引表如图ｌ右下角所示。这即如果一个字符序列在一个索引中出现，那么这就可能是一万方数据１．２．２搜索阶段对于每个数据包负荷中的４．ｂｙｔｃ字符序列，在索引表中查找是否含有特定代表性序列的模式，然后系统对这些模式做进一步检测。仍如前例，如果数据包负荷为“／ｌｏｇｉｌｌ．ｓｈ”，则需检查“／Ｉｏｇ”，“ｌｏｇｉ，，，“ｏｇｉｎ”，“ｇｉｎ．”，“ｉｎ．ｓ”和“ｎ．ｓｈ”等字符序列。在优化后的索引表中，发现“ｎ．ｓｈ”在模式Ｒ２中出现，于是假定ＩＵ被匹配。而其余的字符序列不属于任何一种模式，不必检查。为了减少疑似匹配率，在决定一个模式是否匹配后，用模式的最后两个字符与数据包负荷中相应的最后两则字符做比较，如果相同再触发进一步的检查。采取上述优化步骤后，可以减少５０‰７５％的触发次数。２Ｍｏｄｉ矗ｅｄ．Ｐｉｒａｎｈａ算法２．１预处理阶段通常，一个模式长为８－ｂｙｔｅ的索引表会含有２”个入口，它所消耗的内存是巨大的。为保证内存占用量尽可能小，ＭＰ算法使用一个哈希表来实现索引表的功能。哈希表中表项的位置是由关键字经过哈希运算得到的索引值决定，如果不同表项算出的索引值相等就会发生冲突：小哈希表容易产生较多的冲突，同时，为了查询正确的索引项，需要遍历较长的链表；相反，大哈希表产牛的冲突较少，但是，由于高速缓存的限制，每一次的访问性能较差。此阶段采用位图法和优化高速缓存对Ｐ础算法中的哈希表进行改进。２．１．１位图法哈希表是根据关键码值（Ｋｅｙ）而直接进行访问的数据结构。其中映射函数为散列函数，存放记录的数组为散列表，数组中的每个元素称为桶（Ｂｕｃｋｅｔ），每个桶再用一个链表处理节点冲突９ｌ，并可看作为一个二次链表，算法理想复杂度为ｏ（１）。哈希表的性能主要取决于两个因素：哈希函数和冲突处理。因此，在建造哈希表时不仅要设定一个好的哈希函数，而且要设定一种处理冲突的方法。在ＭＰ中，哈希表选取适用于字符串的ＡＰＨ勰ｈ函数和位运算哈希函数。通过设置大小合适的取余模数与移位数值，并运用除留余数法使各个元素更均匀地分布所确定的数据结构上，再经过位运算哈希函数二次哈希，将得到的相同的地址的关键字值链入对应的链表中。同时另设一个溢出表，不管得到的哈希地址如何，一旦发生冲突，都填入溢出表，单独处理（如与协议分析相结合，定位入侵特征）以解决碰撞冲突与查找性能之间的矛盾。就欲匹配的入侵特征集而言，查找的效率与比较次数密切相关。然而数据包中绝大部分为正常数据流，即在哈希表中查找失败，这意味着在桶链表Ｅ的遍历大都是无用的。可将入侵特征集中频繁匹配的特征信息保存在桶内，并根据相应设定的计数器进行更新排序，每次从计数值较大的桶结点链表开始查找。这样就能进一步减少无用的遍历，降低内存访问次数。本文采用位图在桶内记录入侵特征节点的一些信息（如图２所示）。位图是一个宽为Ｗ位的字ｗ，满足：ｗ的第ｉ位置位，当且仅当存在入侵特征节点ｕ使得位哈希函数Ｈ（ｕ）％Ｗ＝ｉ。其中Ｃｌｌ，Ｃ１２，Ｃｋｌ等为位哈希匹配计数器。改进的位图哈希表查找算法如下：选择一个具有代表性的４．ｂｙｔｅ子模式字符序列来代表一个门，所有其它的输入从门中清除。如对于前例，在索引表中只保样每个门只有一个输入，且其输出等价于输入，同时减少了运行时间内的匹配冲突，因此我们就能够使用索引表进行搜索。次匹配。王杰，刘亚宾，石成辉：快速高效的模式匹配算法的剖析与改进２００９。３０（１１）２６５ｌ图２位图法优化的哈希表步骤１：Ｈｉ＜－．ＡＰＨ髂ｈ（ｘ）％ＭＯＤ；／，为使控制精确，添加求余运算，ＭＯＤ＝１６３８４。步骤２．ｂｉｔ（．．Ｂｉｔ、ｖｉｓｅＨａｓｈ（ｘ），如果发生冲突，填入溢出表；步骤３：ｎｏｄｅ＜～哈希表中第Ｈｉ个桶：／，定位第Ｈｉ个桶节点。步骤４：如粜ｎｏｄｅ的位图中ｂｉｔ位为Ｏ，返回窄值，停止查找；步骤５：否则，在ｎｏｄｅ指向的链表中查找和ｘ相等的节点，若匹配成功，相应位哈希匹配计数器加ｌ，并进行排序调整。该改进与基于排斥的Ｐｍｎｈａ算法相结合，突破哈希表的链表平均长度小于位图宽度和在哈希表中查找成功的概率Ｐ近似为Ｏ的硬性限制，集中体现在步骤１～步骤５中。步骤ｌ中，由Ｓｎｏｎ２．６中的默认规则集分析可知，入侵特征字符串长度在２～３９个字节之间，平均长度为１４个字节。再加上相应的ＴＣＰ／ＩＰ头部长度，根据实验结果，选取求余运算模数ＭＯＤ为１６３８４左右，这样就极人地减少了冲突的发生，使得哈希表的链表平均长度始终处于较好的运行状态。但同时要确保算法中哈希函数中的Ｐ值为素数，否则可能会出现性能恶化的情况。步骤５中，由于网络运行环境相对稳定，在一段时间内，网络攻击行为相对集中，所匹配的入侵特征也会有一定的共性。这样每隔一段时间，将频繁匹配的入侵特征依据所设定的计数器和类别进行排序调整，使待检测的数据流尽早地与默认的入侵特征集匹配，减少匹配次数，并能够更准确伞面地描述网络的基本运行状态。这种方法也适合于密集攻击的行为，但相应地会增加一定的内存开销。优化高速缓存是提高数据结构速度的常见途径之～。该算法应用聚合（Ｃｌｕｓｔ嘶ｎｇ）思想‘”１对入侵特征哈希表优化高速缓存，同时借鉴Ｎｉｓｈｉｍｕ豫等人提出的状态重排法““，将访问频繁的及可能～起被访问的元素按类别放置在一个高速缓存块中，从而增强了高速缓存块的使用效率，提高了数据访问的本地性，同时还提供了隐含的预取性能。下面利用树结构来证明这一概念。树的一种有效聚合方式是将ｆ树存储于一个高速缓存块中，对子树聚合的二叉树进行直觉判断：对一系列的任意树检存块中的子树具有七个结点，则期单的块访问次数为子树的高万方数据是假设在随机访问模式下进行的。对于特殊的访问模式，如深度优先查寻的访问模式，其他的聚合方式也许更好些。此外，对树的更改可能会破坏数据访问的本地性。实验表明，对于那些改变不频繁的树，子树聚合方式以及入侵特征重排将可能一起被访问的、频繁匹配的元素放置在～个高速缓存块中，并进行局部动态地调整，因此远比分配顺序的聚合方式有效。入侵特征哈希表中的哈希表由桶、入侵特征节点和优化后的入侵特征字符串组成，并以单向链表的形式联系在一起（如图２所示）。采用聚合以及入侵特征状态重排思想对哈希表的优化过程在预处理阶段进行：在内存中动态分配一定大小的空间，用以保存索引规则，多个同类入侵索引规则形成一条索引链。每成功匹配一次，则将该条索引规则移动到同类入侵规则链的前端，删除长时间不匹配的以及超出分配空间范围的索引规则，以节省内存开销。图３是哈希表优化后的高速缓存暂态示意图，其中的节点和字符串来自图２，并在之后的运行过程中加以调整。图３优化的哈希表存储暂态２．２搜索阶段在Ｐｉｒａｎｈａ算法的搜索阶段，考虑单模匹配Ｂｏｙｅ卜Ｍ００心算法适用于中小规模规则集，而多模匹配、Ⅳｕ．Ｍ锄ｂｅｒ算法适用于大规模规则集，但在短规则情况下性能有所降低。因此我们对小模式匹配调用Ｂｏｙｅｒ－Ｍ００ｒｅ算法，对正常模式匹配调用ＭｏｄｉｆｉｅｄＷｕ—Ｍ粕ｂｅｒ（ＭｗＭ）算法进行模式匹配，用以代替Ｐｉ珊ｈａ算法中效率较低的ｍａｔｃｈＯ函数。２．３ＭＰ算法实现ＭＰ算法流程如下：预处理阶段：步骤ｌ：对每一个匹配模式，循环读入门列表：步骤２：循环构建并优化索引哈希表；步骤３：如果不再有新门出现，则循环添加索引规则链至规则列表中。搜索阶段：群ｉｆｄｅｆＳＭＡＬＩ，艄ｒｒＥＲＮＳ／／小匹配模式处理（匹配模式长度小于４）对于负载中的每一次偏移：步骤ｌ：若小匹配模式长度为１，转步骤６；步骤２：若小匹配模式长度为２，且负载中大写转换前后的第２个字符与模式的第２个字符相等，转步骤６；步骤３：若小匹配模式长度为３，且负载中大写转换前后的第２、第３个字符与模式的第２、第３个字符均相等，转步骤６；托ｌｓｅ／／正常匹配模式处理（匹配模式长度大于等于４）对于负载中的每一次偏移：拌印ｄｉｆ（下转第２６５５页）２．１．２优化高速缓存（Ｃａｃｈｅ）索时．访问任一子结点的可能性为１／２。若聚合在一个高速缓度ｌ０９２（斛１），且当七＞３时，ｌ０９２（Ｈ１）＞２。而在深度优先的聚合方式下，高速缓存块中的ｋ个结点形成一个惟一的父．子．孙…链，它所期望的块访问次数为逢树增２。当然，这种分析刘伟，胡平：ｗｉｎｄｏｗｓ文件系统过滤驱动在防病毒方面的应用２００９，３０（１１）２６５５（上接第２６５ｌ页）步骤４：若优化索引表的模式索引值与转换为大写后的负载索引值相等转５，否则，转步骤８；步骤５：若负载中相应的最后两则字符与模式的最后两个字符相同，转７，否则，转步骤８；步骤６：调用ＢＭ算法，若匹配成功，返回ｌ，否则，转步骤８：步骤７：调用ＭｗＭ算法，若匹配成功，返回ｌ，否则，转步骤８；步骤８：返回Ｏ。３实验关闭ｓｎｏｎ２．６中所有预处理功能，通过与ＭｗＭ、酽ｘＢ和Ｐｉ啪ｈａ算法的比较，综合评估ＭＰ算法性能。主机配置：ＰＤＥ２１４０ｐｒｏｃｅｓ∞ｒ１．２ＧＨｚ，ｌＧＢＭｅｌＩｌｏｒｙ；操作系统：ＲｅｄｈａｔＬ抽谜９．Ｏ，ｋ嘲ｅｌｖｅｒｓｉｏｎ２ｆ４．２０。数据源：（１）使用抓包工具Ｔｃｐｄ啪ｐ获取的校园网千兆口镜像流量Ｚｚｕ数据；（２）ＭＩＴＬｉｌｌｃｏｌｎｌａｂ实验室给出的入侵检测攻击场景数据集２０００Ｄ川良ＰＡ；（３）２００３年第ｌｌ届ＤｅｆＣ∞ＣＲＦ（Ｃａｐｔｕ心ｔｈｅＲ００ｔＦｕ！）的ＴＳＧ（ＴｈｅＳｈｍ００Ｇｒｏｕｐ）数据集。使用基于２７８４条规则的Ｓｎｏｎ２．６分别读取部分待测文件，并取测试平均值，结果如表ｌ所示，表１中的内存使用是指加载所有规则时的内存开销）。表ｌ不同模式匹配算法性能比较ＺＺＵＤＡＲＰＡＴＳＧ内存使用ＭＷＭ“．８８ｓ∞１４．６９８ｅｃｌＯ－２６８∞４７ＭＢＥ２ｘＢ４３．３２ｓ∞１３．３４ｓ∞８．７３Ⅻ５０Ｍ田Ｐｉｍｎｈａ４２．９ｌｓｅｃ１３．２７ｓ∞８．７４ｓ∞３８Ｍ【ＢＭＰ３７．７５ｓ∞１１．３２ｓ∞７．５０９∞３６ＭＢ表ｌ中，ＺＺＵ列、ＤＡＩ心Ａ列和ＴＳＧ列分别为１０次读取１２０Ｍ的镜像流量数据，读取ＩＤＥＶＡＬ２和ＩＤＥｖＡＬ３，读取８个小组的攻击数据后的平均测试结果。从以上试验数据可以看出，ＭＰ算法相对于Ｍｏｄｉｆｉｅｄｗｕ．Ｍ柚ｂｅｒ算法减少了１０．８％一３６．７％匹配时间，节省３０．６％的内存使用；相对于Ｅ姐算法减少了１４．７‰１７．８％匹配时间，节省３８．９％的内存使用：相对于Ｐｉ删ｎｈａ算法减少了约１３．７％一１７，２％的处理时间，节省５．６％的内存使用。４结束语在导致大量模式匹配的网络环境中，结合排斥思想，ＭＰ万方数据算法采用位图法和优化高速缓存对Ｐｒａｕｎｌｌａ算法中的哈希表改进后，进一步减少了匹配步骤和内存访问次数。从实验结果中可以看出，该算法明显地提升了网络入侵检测系统的性能。但是没有任何一种算法完全适用于不同的网络环境，因此需要依据流量特征、规则集和硬件环境建立一种门限（ｎ睇ｓｈｏｌｄ）判决机制，用以调用各种最适匹配算法，这是我们下一步的研究工作。参考文献：【ｌ】ＲｕｂｉＩｌｓ，ＪＩｌａＳ，Ｍｉ¨ｅｒＢＰ．Ｐｒｏｔｏｍａｔｃｈｉｎｇｎｅｔｗｏｒｌ【ｎ＿ａ伍ｃｆｏｒｈｉｇｈｔｈｒｏｕ曲ｐｕｔｎｅ附ｏｒｌ‘ｉｎｔ九ｌｓｉｏｎｄ曲ｅｃｔｉｏｎ【Ｃ】．Ｐｒｏｃｏｆｔｌｌｅｌ３ｍＡＣＭＣｏｎｆ．∞Ｃｏｍｐｕｔｅｒ锄ｄＣｏｍｍ呻ｉｃａｔｉ∞ｓｓｅｃ面吼２００６：４７—５８．【２】Ａｎ咖ａｔｏｓＳ’Ａ船印ｏｓｔａｋｉｓＫＧ，Ｍａｄ斌ｏｓＥ只烈ａ１．Ｐ酬鼢抛ａｎｃｅ锄ａｌｙｓｉｓｏｆ鲫他ｎｔＩｎｊ批ｈｉｎｇｉＩｌｔｎｌｓｉ∞ｄｃｔｃｃｔｉ∞ｓｙｓｔｃｍｓ［ｃ】．ＰｒｏｃｏｆｔｌｌｅＩｎｔ唧ａｔｉｏｎａｌＳｙｌｌｌｐｏｓｉｕｍｏｎＡｐｐｌｉｃａｔｉ∞ｓ锄ｄｔｈｅ王ｎ－钯ｍｅＬ２００４．［３】张国平，徐汉东．字符串模式匹配算法的改进【Ｊ】．计算机工程与设计，２００７，２８（２０）：４８８Ｉ－４８８４．【４】巫喜红，凌捷．ＢＭ模式匹配算法剖析【Ｊ】．计算机工程与设计，２００７，２８（１）：２９．３１．【５】唐谦，张大方．入侵检测中模式匹配算法的性能分析【Ｊ】．计算机工程与戍用，２００５，４１（１７）：１３６－１３８．【６】陈瑜，陈国龙．ｗｕ－Ｍ卸ｂｅｒ算法性能分析及其改进【Ｊ】．计算机科学，２００６，３３（６）：２０３—２０９．【７】Ａｎａｇｎｏｓｔａ】【ｉｓＫＧ，Ｍ盯ｋａｔｏｓＥ咖ｔｏｎａｔｏｓＳ，ｅｔａＩ．Ｅ２ｘＢ：Ａｄｏ－ｍｉｎｓｐｃｃｉｆｉｃＳｃｆｉｆＩｇｍａｔｃｈｉｎｇａｌｇｏｒｉｔｈｌＩＩｆｏｒｉｎ衄Ｉｓｉｏｎｄｅｔｅｃｔｉｏｎ【Ｃ】．Ｐｒｏｃｏｆｔｌｌｅｌ８ｔｈＩＦＩＰｌｎｎ啪ｌａｔｉｏｎａｌＩｎｆｏ加ａｔｉｏｎｓｅｃ州ｔｙＣ∞ｅ２００３：２１７—２２８．【８】Ａｎｔ０衄ｔｏｓｓ，Ｐｏｌｙｃｈｍｎａｌ【ｉｓＭ’ＡⅫｔｉｄｉｓＰ’ｃｔａ１．Ｐｉ删Ⅱｌｌａ：Ｆａｓｔ加ｄｍ锄ｏｒｙ－ｅ丘ｉｃｉｅｎｔｐａｔｔｃｍｍａｔｃｈｉｎｇｆｏｒ咖ｓｉｏｎｄｅｔｅｃｔｉｏｎ【Ｃ】．Ｃｈｉｂａ＇Ｊａｐ蛐：Ｐｒｏｃｏｆ山ｅ２０ｔｈＩＦＩＰＩＩｌｔｅｎｌ撕。叫ｌＩｎｆｏｌｌｎａｔｉｏｎｓｅ—ｃ嘶ｔｙＣｏｎｅ２００５：３９３．４０８．【９】郑卫斌，张德运．基于哈希表的高性能ＵＲＬ过滤器研究【Ｊ】．小型微型计算机系统，２００５，２６（２）：１７８．１８０．【ｌＯ】ＣｈｉｌｉｍｂｉＴＭ，ＨｉｌｌＭＤ，ＬａｍｓＪＩ乙ＭａＩ【ｉＩｌｇｐｏｉｎｔ盯－ｂａ靶ｄｄａｔａ蚋ｃｔｕｆｅｓｃ孔ｈｅｃｏｎｓｃｉｏｕｓ【Ｊ】．Ｃ鲫№２０００，３３（１２）：６７—７４．ｎｌ】ＮｉｓｈｉｍｕｒａＴ＇Ｆｕｌ噎ｍａｃｈｉＳ，Ｓｈｉｎｏｈ帆Ｔ．Ｓｐｅｅｄ－ｕｐｏｆＡｈｏ－Ｃｏｍ－ｓｉｃｋ群吡啪ｍａｔｃｈｉｎｇ眦ｃｈｉｎｅｓｂｙｍａｍｎｇｉｎｇｓｔａｔｅｓ【Ｃ】．Ｐ陆ｃ∞ｄｉＩ唱ｓｏｆＥｉｇｈｔｈＩｒＩｔｅｍａｔｉｏｎａｌＳｙｒＩｌｐｏｓｉｕｍｏｎＳｔｒｉｎｇＰｒｏｃｅ－ｓ咖ｇ锄ｄＩｎｆ０咖ａｔｉ∞ＲｅｔｒｉｅＶａｌ，２００ｌ：１７５．１８５．