定序窗口布尔表达式匹配技术研究.doc

第12期曹京等：定序窗口布尔表达式匹配技术研究131定序窗口布尔表达式匹配技术研究曹京1,2，刘燕兵1，刘萍1，谭建龙1，郭莉1（1. 中国科学院 计算技术研究所，北京 100080；2. 中国科学院 研究生院，北京 100039）摘 要：提出了布尔表达式匹配技术，给出了算法框架，在此框架上实现了2种常用的实现方式；为了进一步增加布尔表达式的描述功能，增加了定序和窗口2个限制条件，提出了BitCount_OWBE算法，通过理论分析和实验数据证明该算法在多数情况下仍然可以达到原先的性能，从而很好地解决了上万规模的复杂规则匹配问题。关键词：布尔表达式匹配；定序窗口布尔表达式匹配；BitCount_OWBE算法中图分类号：TP301.6 文献标识码：B 文章编号：1000-436X(2007)12-0125-06Research on ordered Boolean expression matching with windowCAO Jing1,2, LIU Yan-bing1, LIU Ping1, TAN Jian-long1, GUO Li1(1. Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100080, China;2. Graduate School of Chinese Academy of Sciences, Beijing 100039, China)Abstract:In view of the difficulty of the complex rule matching problem, Boolean expression matching and a algorithm framework were proposed to solve it. Two popular methods above this framework were given. In addition, two parameters-ORDER and WINDOW- were added into Boolean expression matching in order to enhance the power of the expression rule. Then BitCount_OWBE algorithm was proposed under these two parameters. Test results indicated that BitCount-OWBE could resolve the complex rules matching problem on the scale of 10 000 with no performance decline in most cases.Key words: Boolean expression matching; ordered Boolean expression matching with window; BitCount_OWBE algorithm1 引言经典的串匹配问题主要研究精确串匹配和正则表达式串匹配，但是随着新应用的产生，如病毒检测、入侵检测、垃圾邮件过滤、垃圾短信过滤等，单纯的串匹配算法已经不能很好的处理新应用中复杂匹配规则。这些应用需要将多个关键词组合起来作为一个匹配规则。收稿日期：2007-09-24；修回日期：2007-12-03基金项目：国家重点基础研究发展计划（“973”计划）基金资助项目（2007CB311100）Foundation Item: The National Basic Research Program of China (973 Program) (2007CB311100)Snort1,2是一个强大的轻量级网络入侵检测系统。规则举例如下：Alert tcp $HOME_NET any - $EXTERNAL_NET 1863 (msg:CHAT MSN login attempt; flow:to_server, established; content:USR ; depth:4; nocase; content: TWN ; distance:1; nocase;)。该规则表示要同时匹配USR和TWN2个关键词。Clam Anti Virus3是UNIX/Linux下的一个防病毒工具包。其病毒特征定义举例如下：3c696d67206e616d653d22-1222207372633d22687474703a2f2f38342e3234342e312e3231332f。该病毒特征需要同时匹配-12前后2个字符串序列。上述这些问题无法用精确串匹配来描述；而正则表达式匹配在上万规模时性能太慢（目前使用k表示的空间复杂度是O(m22m/k)，时间复杂度为O(kn)4），无法满足实际应用需要。发现可以用布尔表达式来描述该问题。本文首先给出其定义以及对应算法框架，然后根据应用需求增加定序和窗口2个限制条件，提出了BitCount_OWBE算法，通过实验数据证明，该算法能达到未加限制条件前的性能。本文具体结构如下：第2节给出了布尔表达式匹配的定义、通用算法框架以及对应算法；第3节在布尔表达式匹配的基础上增加定序和窗口2个限制条件，提出了定序窗口布尔表达式匹配，给出通用算法框架的实现算法（BitCount_OWBE算法），通过实验证明其性能跟未加限制条件前一致；第4节是全文的结束语。2 布尔表达式匹配使用布尔逻辑关系：与、或、非来连接多个关键词，从而构成布尔表达式。由于所有逻辑公式都可以表示成析取范式，因此可以将布尔表达式表示成多个只由与、非关系组成的布尔表达式。在给定的文本数据中找到布尔表达式匹配位置即布尔表达式匹配问题。具体定义如下。定义1 给定布尔表达式集合BE=BE1, BE2,BEs，其中，BEi=KeyItem1KeyItem2KeyItemk, KeyItemi=Flagi pi，Flagi=+,，一个文本数据T=t1t2tn，其中T和pi都是字符集上的有限字符序列，则+pi表示正关键词（在数据文本中出现pi），pi表示负关键词（不在数据文本中出现pi），找出满足BEi=True的匹配位置，即布尔表达式匹配问题。定义2 对于只含正关键词的布尔表达式来说，以在文本数据中满足布尔表达式的最后一个关键词出现尾位置作为匹配位置；对于包含负关键词的布尔表达式来说，以文本尾位置作为匹配位置。符号定义如下：布尔表达式的个数为s，关键词的个数为r，每个布尔表达式平均包含关键词个数为k，最短关键词长度为m，测试文本数据长度为n，文本中匹配的关键词个数为q,字符集的大小为|。2.1 算法框架采用两层算法框架来实现布尔表达式匹配算法：多串匹配层和逻辑计算层。多串匹配层位于算法框架的底层，它利用多串匹配算法（如AC1、WM5、SBOM6等）得到文本数据中的匹配关键词序列。本文实验主要使用SBOM算法7；逻辑计算层位于多串匹配层之上，它根据底层得到的匹配关键词序列，通过逻辑计算得到布尔表达式匹配结果。本文主要介绍这一层的处理优化算法。逻辑计算层基本的算法有2种方式，前向计算（如图1所示）和后向计算（如图2所示）。前向计算方式直接向前计算是否满足布尔表达式，是暴力的方式，但不需要额外空间；后向计算方式通过保存中间结果来减少重复计算，性能一般比前向计算方式要好。根据这2种计算，分别实现了双映射表算法和BitCount算法。图1 前向计算方式图2 后向计算方式2.2 算法描述双映射表算法通过构建两张映射表来简化逻辑计算。表达式映射表中索引为布尔表达式序号，内容为该布尔表达式包含所有关键词序号；关键词映射表中索引为关键词序号，内容包含该关键词的所有布尔表达式的序号。逻辑计算部分中，匹配关键词序列个数为q，每个关键词平均在sk/r个表达式中出现，而前向验证最多需要验证个关键词，因此时间复杂度为O(q2sk/r)。BitCount算法采用计数的思想，并利用位掩码和位操作来增快算法速度。使用位掩码BEMask来表示一个布尔表达式，第i位表示布尔表达式中第i个关键词出现情况：1表示该关键词出现，0表示该关键词不出现。使用位掩码CurMask来保存当前布尔表达式的计算结果。这样计算匹配关键词序列中的关键词pi，只需下述公式来更新中间计算结果CurMask：CurMaskCurMask|(110M）。最后将这些表达式包含的关键词随机插入上述生成的随机数据中，这样就生成了测试文本数据。具体结果如图3所示，可以得到如下结论。结论1 随着撒入比例的增加，双映射表性能呈平方级下降；BitCount算法呈线性下降。图3 双映射表算法和BitCount算法性能对比图3 定序窗口布尔表达式匹配在现实应用中需要更加精确的匹配需求，如Snort规则中需要在某一个区间内匹配，而且规则内容需要定序出现。因此对布尔表达式匹配增加限制条件：定序和窗口。形成了定序窗口布尔表达式匹配。所谓定序窗口布尔表达式匹配问题，就是布尔表达式中所有正关键词必须按照次序全部出现在指定的一个窗口大小中，所有负关键词均不出现。具体定义如下。定义3 给定布尔表达式BEi=KeyItem1 KeyItem2KeyItemk, KeyItemi=Flagi pi，Flagi= +,，一个数据文本T=t1t2tn，一个限定窗口大小w，当T中存在一个位置pos，使得在文本区间tpostpos+w内，所有pi不出现，所有+pi在posi出现，如果满足当ij时均有posiposj，则表示布尔表达式在窗口w内定序出现。定义4 给定布尔表达式集合BE=BE1,BE2, BEs，数据文本T=t1t2tn，限定窗口大小w，在文本T中找到所有位置pos，使得区间tpostpos+w内有BEi定序出现，即为定序窗口布尔表达式问题。3.1 算法描述仍然可以采用前向计算方式，但是其性能不如后向计算方式。但不能简单扩展BitCount算法：何时更新成为一个难题。对于布尔表达式BE=p1p2p3来说，如果随时更新匹配位置信息，那么当匹配关键词序列为p1,p2,p1,p3时，会漏报。如果不随时更新，当匹配关键词序列为p1,p2,p1,p2,p3且仅后3个关键词的距离满足窗口大小，那么仍然会漏报。因此需要用二维变量来保存计算结果，使用一个队列来保存关键词在文本中的匹配位置，从而将逻辑计算过程转化成元素进出队列以及队列调整操作。具体操作参加下面4个引理，具体证明略。引理1 对于待加入的关键词pi（1ik）来说，如果此时qi.sizeqi1.size，则可以直接将pi代替队列qi最顶层（qi.size层）的关键词；否则将pi插入队列qi。引理2 对于待加入的关键词p1来说，如果此时q1.sizeq2.size，直接将p1插入队列q1；否则将p1代替q1最顶层（q1.size层）的关键词。引理3 将待加入的关键词pi（1i0，将pk插入队列qk，计算队列中第qk.size层的窗口大小是否满足限定值，删除所有队列的第qk.size层；否则直接忽略该关键词。上面的定理只给出了布尔表达式只包含“与关系”的情况，如果布尔表达式包含“非关系”则需要在窗口内验证“非关系”是否出现。3.2 算法改进BitCount_OWBE算法根据3.1节的描述，得到了一个解决定序窗口布尔表达式匹配的算法。但是跟BitCount算法比较起来有2个缺陷：需要更多的内存空间；需要更多的处理时间。根据引理1引理4可以得到，队列数组形成了一个严格意义上的金字塔形：第i层的元素个数永远比第i+1层少1；而且金字塔形中每一层只有最左边和最右边2个元素有意义：一个表示起始位置，另外一个标记当前定序匹配了多少个关键词。因此可以使用一个数组来表示，其中数组元素值表示起始位置，数组位置表示定序匹配多少个关键词，这样就可以用数组来代替队列数组。下面给出BitCount_OWBE算法的描述。对于每个布尔表达式，先对布尔表达式进行调整：使得+pi全部在前面，pi都在后面。使用ExprPrefixPos这个数组来记录该布尔表达式的前缀定序匹配信息。一开始数组中的元素全部初始化，用来表示没有一个前缀定序匹配。具体算法步骤如下：1) 匹配关键词序列是否全部处理完： 是，算法结束； 否，按次序取出未处理的关键词pi，转2)。2) 判断pi是否是对应布尔表达式中第一个关键词： 是，将ExprPrefixPos0的值置为pi的出现位置，转3)。 否，判断ExprPrefixPosi1是否是：a) 是，表明前面一个关键词还没有匹配成功，转1)；b) 否，将ExprPrefixPosi1值“移动”到ExprPrefixPosi，转3)。3) 判断Pi是否是布尔表达式中最后一个“+”关键词： 是，进行窗口验证过程：比较pi的匹配位置减去ExprPrefixPosi值跟限定窗口的关系：a) 大于限定窗口，匹配不成功，转1)；b) 小于等于限定窗口，需要验证，转4)； 否，没有定序匹配全部关键词，转1)。4) 验证窗口内是否出现“非关系”关键词： 是，匹配不成功，转1)； 否，匹配成功，报告匹配位置，转1)。在此过程中，步骤2)中的是引理1操作；步骤2)中的则是引理2和引理3操作；步骤3)是引理4操作。步骤4)是验证窗口内非关系是否满足的过程。由于布尔表达式包含k个关键词，最多有k个定序匹配前缀，而ExprPrefixPos记录了所有当前匹配前缀，所以算法是正确的。这样，通过“比较”和“移位”操作，就实现了定序窗口布尔表达式匹配算法：BitCount_OWBE算法。接下来分析一下算法的复杂度。步骤4)中的验证过程最坏情况下需要验证所有关键词（包含负关键词并且该关键词没有在文本中出现），而最好情况下不需要验证（全部是正关键词），因此最坏情况下复杂度为O(qsk/r),最好情况下只需要O(1)。由于总共要处理q个关键词，而每个关键词对应sk/r个表达式，所以如果布尔表达式只含正关键词，算法复杂度为O(qsk/r)；如果布尔表达式包含负关键词，则算法复杂度跟窗口有关，最坏情况下为O(qsk/r)2)。3.3 实验结果根据上述理论分析，可以看出布尔关系对算法性能会有一定影响。因此作了一些实验，通过实验来分析算法的性能并给出一些结论。3.3.1 正关键词下限定窗口大小的性能影响首先来看当布尔表达式只含正关键词时，限定窗口大小对BitCount_OWBE算法的影响。作了如下实验：布尔表达式、关键词和测试文本数据生成方式同第2节，区别在于关键词撒入方式不一样：对每个布尔表达式先随机选择插入位置，然后将关键词定序的插入这些位置。布尔表达式个数仍然是10 000个，撒入比例从0100%，步长10%。对于每个撒入比例，测试当限定窗口大小从1MB变化到10MB（步长为1MB）BitCount_OWBE算法的性能变化情况。具体实验结果如图4所示。图4中每条曲线表示一个撒入比例，所有曲线都趋向于直线，因此可以得到如下结论。结论2 对于只包含正关键词的布尔表达式来说，BitCount_OWBE算法的性能跟限定窗口大小无关。 图4 BitCount_OWBE算法窗口性能影响图（不含非关系）又由于撒入比例高的曲线位于图下方，撒入比例低的曲线位于图上方，因此可以得到下面结论：结论3 BitCount_OWBE算法的性能随着表达式命中次数的增加而下降。3.3.2 负关键词下限定窗口大小的性能影响接下来看对于包含负关键词的布尔表达式，限定窗口大小对BitCount_OWBE算法的影响情况。作了如下实验：采用了上一节中的数据，区别是：每个布尔表达式包含的最后一个正关键词被改成负关键词；在测试文本数据中定序撒关键词时不撒负关键词，而撒其他正关键词。具体实验结果如图5所示。同样可以得到下面2个结论。图5 BitCount_OWBE算法窗口性能影响图 结论4 对于包含负关键词的布尔表达式来说，BitCount_OWBE算法的性能随着限定窗口大小变大而下降，呈反比关系。结论5 对于包含负关键词的布尔表达式来说，布尔表达式撒入比例越大，BitCount_OWBE算法的性能受限定窗口大小的影响越大。当然对于一些实际应用来说，限定窗口不会很大8，因此继续测试了一组实验，实验数据同上，只是限定窗口改成100kB1MB（步长为100kB）。具体实验结果如图6所示。如图6所示，看到现在每条曲线趋向于水平直线，即其速度基本受限定窗口大小的影响，因此可以得到下面的结论。结论6 对于包含负关键词的布尔表达式来说，在限定窗口大小比较小的情况下，BitCount_ OWBE的性能不受限定窗口的影响。图6 BitCount_OWBE算法小窗口性能影响图 3.3.3 算法性能对比为了测试布尔表达式在增加定序和窗口这2个限制后的性能变化，将BitCount_OWBE算法跟BitCount算法进行比较。由于布尔表达式包含负关键词时，BitCount_OWBE算法的性能随着限定窗口增加而下降，但是在限定窗口比较小的情况下，其性能基本保持不变。因此只比较只包含正关键词下算法性能。测试数据采用上一节的实验数据。窗口大小为1MB，具体实验结果如图7所示。此可以得到下面的结论：图7 BitCount_OWBE算法和BitCount算法性能比较图结论7 对于只包含正关键词的布尔表达式匹配来说，增加窗口以及定序这2个限定条件后，仍然可以保持性能不变。再结合图6和结论6，可以进一步得到下面的结论：结论8 对于包含负关键词的布尔表达式匹配来说，在限定窗口比较小的情况下，增加窗口以及定序这2个限定条件后，仍然可以保持性能不变。4 结束语本文通过使用布尔逻辑关系与、或、非来组合多个关键词，从而形成布尔表达式匹配。给出了一个通用算法框架，在此框架上实现了2个算法。为了更精确的匹配过滤需求，在布尔表达式匹配的基础上增加了定序和窗口2个限制条件，形成了定序窗口布尔表达式匹配，并给出了BitCount_OWBE算法，通过实验数据证明，在大部分情况下，BitCount_OWBE算法都能很好的解决定序窗口布尔表达式匹配这个问题，使其性能能够达到不加任何限制条件前的性能指标，从而很好地解决上万规模的复杂规则匹配问题。根据BitCount_OWBE算法的特性，发现其算法思想可以推广到wildcard通配符串匹配以及允许gap的扩展串匹配问题。而如何推广则是下一步需要做的工作。参考文献：1AHO A, CORASICK M. Efficient string matching: an aid to bibliographic searchA. Communications of the ACMC. 1975.333-340. 2Snort 2.4.xEB/OL. , 2006.3Clam antiVirusEB/OL. , 2006. 4NAVARRO G, RAFFINOT M. N