一种多模式正则表达式匹配方法及装置

1.一种多模式正则表达式匹配方法，其特征在于，该方法包括：
按照预先建立的第一层过滤特征集对待匹配数据进行过滤得到第一层过滤的数据分片和命中的精确字符串；所述第一层过滤特征集包括：从每个正则表达式提取的一个长度超过预设阈值的精确字符串；
根据所述命中的精确字符串查找对应的正则表达式超集，按照所述正则表达式超集对所述第一层过滤的数据分片进行第二层过滤得到第二层过滤的数据分片和命中的正则表达式超集；所述正则表达式超集是根据正则表达式的精确字符串和模糊字符串的逻辑关系组成的表达式；
根据所述命中的正则表达式超集确定对应的正则表达式，利用所述正则表达式对所述第二层过滤的数据分片作匹配。
2.根据权利要求1所述的方法，其特征在于，所述第一层过滤特征集通过以下方式建立：
对每个正则表达式进行分割得到对应的精确字符串和模糊字符串；
从每个正则表达式对应的精确字符串中选择长度超过预设阈值的精确字符串，将选择的精确字符串组合成备选字符串集；
按照精确字符串的优先级顺序从所述备选字符串集中针对每个正则表达式选择一个精确字符串组合成第一层过滤特征集。
3.根据权利要求2所述的方法，其特征在于，在所述对每个正则表达式进行分割得到对应的精确字符串和模糊字符串之后，所述方法还包括：
将所述模糊字符串进行确定化，并与相邻的精确字符串分片合并。
4.根据权利要求2或3所述的方法，其特征在于，所述按照精确字符串的优先级顺序从所述备选字符串集中针对每个正则表达式选择一个精确字符串组合成第一过滤特征集，包括：
按照字符串长度大小关系来设置所述备选字符串集中每个正则表达式对应的精确字符串的优先级顺序，且该优先级顺序在使用过程中根据第一层过滤和第二层过滤的结果进行调整；从每个正则表达式对应的精确字符串中选择优先级最高的精确字符串以组合成第一层过滤特征集。
5.根据权利要求1所述的方法，其特征在于，所述正则表达式超集通过以下方式生成：
对正则表达式进行分割得到精确字符串和模糊字符串，采用逻辑关系符号替代所述模糊字符串，根据所述精确字符串和所述逻辑关系符号生成正则表达式超集；所述逻辑关系符号用于表征所述模糊字符串与其相邻的精确字符串之间的逻辑关系。
6.一种多模式正则表达式匹配装置，其特征在于，该装置包括：
第一层过滤单元，用于按照预先建立的第一层过滤特征集对待匹配数据进行过滤得到第一层过滤的数据分片和命中的精确字符串；所述第一层过滤特征集包括：从每个正则表达式提取的一个长度超过预设阈值的精确字符串；
第二层过滤单元，用于根据所述命中的精确字符串查找对应的正则表达式超集，按照所述正则表达式超集对所述第一层过滤的数据分片进行第二层过滤得到第二层过滤的数据分片和命中的正则表达式超集；所述正则表达式超集是根据正则表达式的精确字符串和模糊字符串的逻辑关系组成的表达式；
匹配单元，用于根据所述命中的正则表达式超集确定对应的正则表达式，利用所述正则表达式对所述第二层过滤的数据分片作匹配。
7.根据权利要求6所述的装置，其特征在于，所述装置还包括：
第一层过滤特征集生成单元，用于生成所述第一层过滤特征集；
所述第一层过滤特征集生成单元，包括：
字符串分割子单元，用于对每个正则表达式进行分割得到对应的精确字符串和模糊字符串；
备选字符串集生成子单元，用于从每个正则表达式对应的精确字符串中选择长度超过预设阈值的精确字符串，将选择的精确字符串组合成备选字符串集；
第一过滤特征集生成子单元，用于按照精确字符串的优先级顺序从所述备选字符串集中针对每个正则表达式选择一个精确字符串组合成第一层过滤特征集。
8.根据权利要求7所述的装置，其特征在于，所述第一过滤特征集生成单元还包括：
确定化子单元，用于将所述模糊字符串进行确定化，并与相邻的精确字符串分片合并。
9.根据权利要求7或8所述的装置，其特征在于，所述第一层过滤特征集生成子单元具体用于：
按照字符串长度大小关系来设置所述备选字符串集中每个正则表达式对应的精确字符串的优先级顺序，且该优先级顺序在使用过程中根据第一层过滤和第二层过滤的结果进行调整；从每个正则表达式对应的精确字符串中选择优先级最高的精确字符串以组合成第一层过滤特征集。
10.根据权利要求6所述的装置，其特征在于，所述装置还包括：
正则表达式超集生成单元，用于对正则表达式进行分割得到精确字符串和模糊字符串，采用逻辑关系符号替代所述模糊字符串，根据所述精确字符串和所述逻辑关系符号生成正则表达式超集；所述逻辑关系符号用于表征所述模糊字符串与其相邻的精确字符串之间的逻辑关系。

一种多模式正则表达式匹配方法及装置\n技术领域\n[0001] 本申请涉及网络安全技术领域，特别涉及多模式正则表达式匹配方法及装置。\n背景技术\n[0002] 正则表达式是一种描述字符串的表达形式，具备自由且准确的表述能力，在网络安全领域有着广泛的应用，常被用来描述具有攻击意图的网络数据。在入侵检测系统中，通常会包含描述大量攻击特征的正则表达式集合。在检测过程中，采用多模式正则表达式匹配的方式将正则表达式集合与网络数据流进行匹配，以从中发现攻击行为。而随着互联网发展，网络服务增多，网络环境日益复杂，数据流量带宽也在不断增加，多模式正则表达式匹配在容纳更多更复杂的正则表达式的同时也要求用更少的存储空间进行更快的匹配。\n[0003] 传统的多模式正则表达式匹配方法有三类：第一类方法是非确定有限自动机NFA匹配，具有存储空间少的优点，但存在不确定数量的激活状态，匹配速度通常较慢的问题；\n第二类方法是确定有限自动机DFA匹配，具有匹配速度快的优点，但对于大规模或是特殊写法的复杂正则表达式，可能会产生状态爆炸，从而使自动机构造时间过长，甚至内存耗尽无法构造的问题；第三类方法是先使用精确串多模式匹配或者扩展自动机匹配进行预过滤匹配，当预过滤匹配命中时，就预示附近区域有可能存在成功匹配，这时再用NFA或者DFA进行确认，相比前两类方法，第三类方法更易于实现其可扩展性较好。因此，目前常采用第三类方法，也称为预过滤匹配方法，该方法具体包括：\n[0004] 对待匹配的数据流进行字符串过滤，当数据流中的关键字与预设的特征字具有至少一个相同特征时，表明数据流通过字符串过滤；将通过字符串过滤的数据流进行正则表达式匹配。由于该方法中的字符串是直接从正则表达式中提取的，字符串的长度和数量均无法保证过滤的质量，例如当所有正则表达式中一条或多条正则表达式所提取的均是短字符串或不具区分度的字符串时，则该方法的过滤效果不佳，导致进入正则表达式匹配的数据量巨大，严重影响整个匹配性能。\n发明内容\n[0005] 本发明所要解决的技术问题是提供多模式正则表达式匹配方法，通过两层过滤方式提高过滤速率和过滤效果，进而以保证匹配性能的稳定性。\n[0006] 本发明还提供了多模式正则表达式匹配装置，用以保证上述方法在实际中的实现及应用。\n[0007] 一方面，本发明提供了多模式正则表达式匹配方法，该方法包括：\n[0008] 按照预先建立的第一层过滤特征集对待匹配数据进行过滤得到第一层过滤的数据分片和命中的精确字符串；所述第一层过滤特征集包括：从每个正则表达式提取的一个长度超过预设阈值的精确字符串；\n[0009] 根据所述命中的精确字符串查找对应的正则表达式超集，按照所述正则表达式超集对所述第一层过滤的数据分片进行第二层过滤得到第二层过滤的数据分片和命中的正则表达式超集；所述正则表达式超集是根据正则表达式的精确字符串和模糊字符串的逻辑关系组成的表达式；\n[0010] 根据所述命中的正则表达式超集确定对应的正则表达式，利用所述正则表达式对所述第二层过滤的数据分片作匹配。\n[0011] 优选的，所述第一层过滤特征集通过以下方式建立：\n[0012] 对每个正则表达式进行分割得到对应的精确字符串和模糊字符串；\n[0013] 从每个正则表达式对应的精确字符串中选择长度超过预设阈值的精确字符串，将选择的精确字符串组合成备选字符串集；\n[0014] 按照精确字符串的优先级顺序从所述备选字符串集中针对每个正则表达式选择一个精确字符串组合成第一层过滤特征集。\n[0015] 优选的，在所述对每个正则表达式进行分割得到对应的精确字符串和模糊字符串之后，所述方法还包括：\n[0016] 将所述模糊字符串进行确定化，并与相邻的精确字符串分片合并。\n[0017] 优选的，所述按照精确字符串的优先级顺序从所述备选字符串集中针对每个正则表达式选择一个精确字符串组合成第一过滤特征集，包括：\n[0018] 按照字符串长度大小关系来设置所述备选字符串集中每个正则表达式对应的精确字符串的优先级顺序，且该优先级顺序在使用过程中根据第一层过滤和第二层过滤的结果进行调整；从每个正则表达式对应的精确字符串中选择优先级最高的精确字符串以组合成第一层过滤特征集。\n[0019] 优选的，所述正则表达式超集通过以下方式生成：\n[0020] 用于对正则表达式进行分割得到精确字符串和模糊字符串，采用逻辑关系符号替代所述模糊字符串，根据所述精确字符串和所述逻辑关系符号生成正则表达式超集；所述逻辑关系符号用于表征所述模糊字符串与其相邻的精确字符串之间的逻辑关系。\n[0021] 又一方面，本发明提供了一种多模式正则表达式匹配装置，该装置包括：\n[0022] 第一层过滤单元，用于按照预先建立的第一层过滤特征集对待匹配数据进行过滤得到第一层过滤的数据分片和命中的精确字符串；所述第一层过滤特征集包括：从每个正则表达式提取的一个长度超过预设阈值的精确字符串；\n[0023] 第二层过滤单元，用于根据所述命中的精确字符串查找对应的正则表达式超集，按照所述正则表达式超集对所述第一层过滤的数据分片进行第二层过滤得到第二层过滤的数据分片和命中的正则表达式超集；所述正则表达式超集是根据正则表达式的精确字符串和模糊字符串的逻辑关系组成的表达式；\n[0024] 匹配单元，用于根据所述命中的正则表达式超集确定对应的正则表达式，利用所述正则表达式对所述第二层过滤的数据分片作匹配。\n[0025] 优选的，所述装置还包括：\n[0026] 第一层过滤特征集生成单元，用于生成所述第一层过滤特征集；\n[0027] 所述第一层过滤特征集生成单元，包括：\n[0028] 字符串分割子单元，用于对每个正则表达式进行分割得到对应的精确字符串和模糊字符串；\n[0029] 备选字符串集生成子单元，用于从每个正则表达式对应的精确字符串中选择长度超过预设阈值的精确字符串，将选择的精确字符串组合成备选字符串集；\n[0030] 第一过滤特征集生成子单元，用于按照精确字符串的优先级顺序从所述备选字符串集中针对每个正则表达式选择一个精确字符串组合成第一层过滤特征集。\n[0031] 优选的，所述第一过滤特征集生成单元还包括：\n[0032] 确定化子单元，用于将所述模糊字符串进行确定化，并与相邻的精确字符串分片合并。\n[0033] 优选的，所述第一层过滤特征集生成子单元具体用于：\n[0034] 按照字符串长度大小关系来设置所述备选字符串集中每个正则表达式对应的精确字符串的优先级顺序，且该优先级顺序在使用过程中根据第一层过滤和第二层过滤的结果进行调整；从每个正则表达式对应的精确字符串中选择优先级最高的精确字符串以组合成第一层过滤特征集。\n[0035] 优选的，所述装置还包括：\n[0036] 正则表达式超集生成单元，用于对正则表达式进行分割得到精确字符串和模糊字符串，采用逻辑关系符号替代所述模糊字符串，根据所述精确字符串和所述逻辑关系符号生成正则表达式超集；所述逻辑关系符号用于表征所述模糊字符串与其相邻的精确字符串之间的逻辑关系。\n[0037] 与现有技术相比，本发明具有如下有益效果：\n[0038] 本发明提出了通过两层过滤的方式来提高过滤效果，具体的是按照预先建立的第一层过滤特征集对待匹配数据进行过滤得到第一层过滤的数据分片和命中的精确字符串；\n所述第一层过滤特征集包括：从每个正则表达式提取的一个长度超过预设阈值的精确字符串；这里的第一层过滤是根据字符串数量越少越好，字符串长度越长越好的特点选定的第一过滤特征集，只从每个正则表达式中选择一个字符串；有别于现有技术中的精确串，从而使得第一层过滤能起到降低纯净数据通过率的作用，主要起到“过滤速度最大化”的作用。\n[0039] 在第一层过滤完成时，接着进行第二层过滤，具体是根据所述命中的精确字符串查找对应的正则表达式超集，按照所述正则表达式超集对所述第一层过滤的数据分片进行第二层过滤得到第二层过滤的数据分片和命中的正则表达式超集；所述正则表达式超集是根据正则表达式的精确字符串和模糊字符串的逻辑关系组成的表达式；由于第二层过滤采用的是正则表达式超集，其描述能力已经十分接近原始的正则表达式，能够做到尽可能排除不匹配的数据，以过滤出最接近原始正则表达式的数据分片，避免大量的浑浊数据进入到最后的正则表达式匹配阶段，第二层过滤主要起到过滤效果最大化的作用，并以间接提高匹配效率，同时将多模式匹配分解到不同场景(不同数据分片)上的单模匹配，进而避免了DFA空间膨胀或NFA匹配速度过慢的问题。最后，对第二层过滤得到的数据分片，利用其对应的正则表达式作单条匹配。因此，本发明的技术方案通过两层过滤方式提高过滤速率和过滤效果，进而以保证匹配性能的稳定性，在保证攻击性数据被过滤的情况下，尽可能避免纯净数据的通过。\n附图说明\n[0040] 为了更清楚地说明本发明实施例中的技术方案，下面将对实施例描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本申请的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可以根据这些附图获得其他的附图。\n[0041] 图1是本发明的多模式正则表达式匹配方法实施例的流程图；\n[0042] 图2是本发明提供的第一层过滤特征集的生成方法的流程图；\n[0043] 图3是本发明的多模式正则表达式匹配装置实施例的结构图。\n具体实施方式\n[0044] 下面将结合本申请实施例中的附图，对本申请实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本申请一部分实施例，而不是全部的实施例。基于本申请中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本申请保护的范围。\n[0045] 本申请可用于众多通用或专用的计算装置环境或配置中。例如：个人计算机、服务器计算机、手持设备或便携式设备、平板型设备、多处理器装置、包括以上任何装置或设备的分布式计算环境等等。\n[0046] 本申请可以在由计算机执行的计算机可执行指令的一般上下文中描述，例如程序模块。一般地，程序模块包括执行特定任务或实现特定抽象数据类型的例程、程序、对象、组件、数据结构等等。也可以在分布式计算环境中实践本申请，在这些分布式计算环境中，由通过通信网络而被连接的远程处理设备来执行任务。在分布式计算环境中，程序模块可以位于包括存储设备在内的本地和远程计算机存储介质中。\n[0047] 参考图1，图1是本发明的多模式正则表达式匹配方法实施例的流程图，该方法可以包括：\n[0048] S101，按照预先建立的第一层过滤特征集对待匹配数据进行过滤得到第一层过滤的数据分片和命中的精确字符串；所述第一层过滤特征集包括：从每个正则表达式提取的一个长度超过预设阈值的精确字符串。\n[0049] 这里的第一层过滤特征集在实现匹配方法之前应预先生成，该第一层过滤特征集针对每个正则表达式仅包含一个精确字符串，且该精确字符串必须满足长度超过预设阈值的条件。\n[0050] 针对如何生成第一层过滤特征集，本发明还提出了具体的实现方法，参见图2，图2是本发明提供的第一层过滤特征集的生成方法的流程图，该方法包括：\n[0051] S201，对每个正则表达式进行分割得到对应的精确字符串和模糊字符串。\n[0052] 这里需要说明的是，正则表达式根据语法不同其表达形式可能不同，一般情况下包含：字母、数字、引用符号或特殊语法符号等元素；按照一定的分割条件，均可将一个正则表达式分割成两种类型的字符串，这两种类型字符串分别称为：精确字符串和模糊字符串，分割得到的这两种类型字符串的个数不定。\n[0053] 发明人考虑到在实现过程中精确字符串长度越长，第一层过滤的效率越高的特点，进一步提出了一种实现方式，以在不缩小语义覆盖范围的情况下，尽可能地将精确字符串长度最大化，具体实现方式是在上述S201之后，增加如下步骤：\n[0054] 将所述模糊字符串进行确定化，并与相邻的精确字符串分片合并。然后再进行后续步骤，且后续步骤均是对合并后的精确字符串进行相应的处理。\n[0055] 在完成S201之后，接着进行S202和S203。\n[0056] S202，从每个正则表达式对应的精确字符串中选择长度超过预设阈值的精确字符串，将选择的精确字符串组合成备选字符串集。\n[0057] S203，按照精确字符串的优先级顺序从所述备选字符串集中针对每个正则表达式选择一个精确字符串组合成第一层过滤特征集。\n[0058] 在具体实现时，S203可以是按照精确字符串长度由大到小的顺序来设置优先级由高到低的顺序，然后针对每个正则表达式选择对应的优先级最高的精确字符串(长度最长的精确字符串)，以组合生成第一层过滤特征集。\n[0059] 为了进一步保障第一层过滤效果，发明人还提出了结合实际过滤结果来适应性调整第一层过滤特征集，具体实现方式为：\n[0060] 按照字符串长度大小关系来设置所述备选字符串集中每个正则表达式对应的精确字符串的优先级顺序，且该优先级顺序在使用过程中根据第一层过滤和第二层过滤的结果进行调整；从每个正则表达式对应的精确字符串中选择优先级最高的精确字符串以组合成第一层过滤特征集。\n[0061] 上述实现方式可以理解为，在初始阶段，第一层过滤特征集是直接选择每个正则表达式对应的优先级最高的精确字符串(长度最长的精确字符串)；在后期阶段，根据第一层过滤和第二层过滤的结果来对优先级顺序进行适应性调整，如果精确字符串在第一层过滤时发送命中，但在第二层过滤时未发生命中，此时，将该精确字符串的优先级降至最低，并将备选字符串集中与其顺序相邻的精确字符串的优先级更新为最高级。在整个匹配过程中，采用上述轮询方式，尽可能地让具有较高区分程度的精确字符串长时间地作为第一层过滤特征集的元素，以保证第一层过滤的实际效果最佳。\n[0062] 在具体实现时，可以按照上述优先级顺序的设置方式动态调整备选字符串集合中的精确字符串的优先级高低顺序，从而动态调整第一层过滤特征集，以使其根据实际过滤情况进行动态变化，以满足第一层过滤需求。\n[0063] 为了更好的理解上述步骤S101，下面以具体场景为例对其作进一步解释说明。\n[0064] 在攻击检测应用领域里，一般情况下采用的正则表达式具有明显区分度的特征；\n本发明正是充分利用正则表达式所描述的数据与普通正常数据的差异，来实现较好的过滤功能，以大幅度提高检测效率。\n[0065] 上述第一层过滤的本质是为了匹配每个正则表达式中最具有明显区分度的精确字符串，以保证“纯净”数据无须进入后续的深入检测过程，也为后续的步骤提供较为精确、数据量较小的“浑浊”数据。一般情况下，大量的网络数据均是“纯净”数据，那么经过第一层过滤后，这些“纯净”数据不会再进入后续的第二层过滤及匹配处理，极大地简化了后续处理。这里的“纯净”数据是指非可疑的网络数据，而“浑浊”数据是指可疑的网络数据。\n[0066] 经过第一层过滤可能过滤得到一个数据分片以及被命中的一个精确字符串，也可能得到多个数据分片以及多个被命中的精确字符串，还有可能是没有过滤到数据分片，没有精确字符串被命中；在没有过滤到数据分片的情况下，说明待匹配的数据不符合匹配规则，认为待匹配的数据均是纯净数据，则无需进行后续各个步骤，直接结束此次匹配过程。\n[0067] 当第一层过滤出数据分片时，进入后续的S102和S103。\n[0068] 接着描述本实施例的实现步骤S102和S103。\n[0069] S102，根据所述命中的精确字符串查找对应的正则表达式超集，按照所述正则表达式超集对所述第一层过滤的数据分片进行第二层过滤得到第二层过滤的数据分片和命中的正则表达式超集；所述正则表达式超集是根据正则表达式的精确字符串和模糊字符串的逻辑关系组成的表达式。\n[0070] 这里的正则表达式超集是在实现第二层匹配之前应预先生成的，每个正则表达式对应有一个正则表达式超集，针对如何生成正则表达式超集，本发明还提出了具体的实现方法，该方法包括：\n[0071] 对正则表达式进行分割得到精确字符串和模糊字符串，采用逻辑关系符号替代所述模糊字符串，根据所述精确字符串和所述逻辑关系符号生成正则表达式超集；所述逻辑关系符号用于表征所述模糊字符串与其相邻的精确字符串之间的逻辑关系。\n[0072] 这里需要说明的是，超集是从数据集合的概念上理解的，一个数据集合的超集必然包含这个数据集合的所有元素，以及各个元素的逻辑关系。正则表达式超集所涵盖的元素范围远大于该正则表达式所涵盖的元素范围。从该生成方法可以看出，利用逻辑关系符号替代了模糊字符串，由于逻辑关系符号所涵盖的元素范围远大于模糊字符串所涵盖的范围，因此使得建立的超集的范围远大于正则表达式的范围。由于正则表达式字符串间具有一定的顺序关系，具有一定的数据长度，为了建立一个范围较合适的超集，这里的逻辑关系符号可以是顺序与、与、或、长度判定符号等形式。\n[0073] 第二层过滤的本质是词匹配过程和语义匹配过程。所谓词匹配过程是指与正则表达式超集里的精确字符串进行匹配；所述语义匹配过程是指根据词匹配结果决定用哪个超集语法树进行匹配，遍历语法树，当语法树被命中时，表明该数据分片通过第二层过滤，视为正则表达式超集命中。这里的语法树实质是正则表达式超集的另一种展示形式，语法树是以超集中的精确字符串作为终端节点，以超集中的逻辑关系符号作为非终端节点。\n[0074] 为了更好的理解上述步骤S102，下面以具体场景为例对其作进一步解释说明。\n[0075] 在攻击检测应用领域里，在上述第一层过滤之后再进行第二层过滤主要是为了避免出现大量复杂网络环境中的“浑浊”数据，阻塞到最后的正则表达式匹配环节，因此，第二层过滤主要筛选不能发生命中的数据，直接将这些数据分流以减少正则表达式匹配的数据量，以避免出现DFA的空间膨胀问题或者NFA匹配速度慢的问题。\n[0076] 在完成第二层过滤，且过滤到一些数据分片时，就进入S103以对数据分片进行最终匹配确认。\n[0077] S103，根据所述命中的正则表达式超集确定对应的正则表达式，利用所述正则表达式对所述第二层过滤的数据分片作匹配。\n[0078] 由于待匹配数据中的大部分数据是“纯净”数据，因此在第一层过滤和第二层过滤处理时，已经将大部分数据分流掉，进入到最后环节的数据非常少，又因为在第二层过滤时已经可以确定数据分片与哪个正则表达式最可能匹配，因此，将多模式匹配分解到不同的场景的单模匹配(数据分片对应的单模匹配)，基于此，S103具体实现时，可以采用非确定有限自动机(NFA)方法实现匹配，也可以采用确定有限自动机(DFA)的方式实现匹配。\n[0079] 另外，发明人在上述两层过滤的基础上，还提出了步骤S103可以仅对正则表达式模糊字符串部分进行构建就可以完成最终的匹配。主要是因为在第一层过滤和第二层过滤时已经确定了数据分片精确字符串相匹配，因此，在最后一个环节也可以仅对模糊字符串部分进行匹配。\n[0080] 基于上述描述，上述S103在具体实现时，可以有以下两种实现方式：\n[0081] 第(1)种方式：通过构造非确定有限自动机或确定有限自动机表述所述命中的正则表达式超集对应的正则表达式中的模糊字符串，利用构造的非确定有限自动机或确定有限自动机对第二层过滤的数据分片进行匹配。\n[0082] 第(2)种方式：通过构造非确定有限自动机或确定有限自动机表述所述命中的正则表达式超集对应的正则表达式，利用构造的非确定有限自动机或确定有限自动机对第二层过滤的数据分片进行匹配。\n[0083] 上文描述的以图2示例的第一过滤特征集的生成方法，下面通过具体示例对其S201的实现过程作进一步解释说明，主要是以PCRE正则表达式语法为例来进行举例说明。\n[0084] 对正则表达式进行分割，主要是以模糊因子作为分隔符，将正则表达式分割成精确字符串和模糊字符串。正则表达式的模糊因子是指不能确定地表示一个ASCII字符的符号及其组合。\n[0085] 根据PCRE语法(正则表达式语法)的语法特征，可以定义如下模糊因子：\n[0086] (1)元字符：“.”，“＾”，“$”。\n[0087] (2)分支符：“|”。\n[0088] (3)分组符：(..)。\n[0089] (4)后缀符或词组：“+”，“？”，“＊”，{m，n}，{m，}，{，n}，{m}。\n[0090] (5)字符词组，例如[a－z]，[＾0－9]，[[：alpha：]]等。\n[0091] (6)引用符号，例如正则表达式来描述为(\\[D dSsW w B beZ A ab tnvfr0－9])|(\\[Pp]((\{[a－zA－Z＿]＊\})|([a－zA－Z]))？)，则\d，\f，\n，\pF，\p{N am e}为引用符号。\n[0092] (7)惰性匹配和修改匹配模式的高级语法符号，例如：“＊？”，“+？”，“？？”，“{m，n}？”，“\Q…\E”，“(？i)”，“(？－i)”，“(？s)”，“(？－s)”，“(？m)”，“(？－m)”等。\n[0093] 在具体实现时，模糊因子也可以是以上各种形式的组合形式。\n[0094] 其次，定义模糊判定条件：\n[0095] (a)对于后缀符或词组，与其语法前缀合并成一个模糊字符串，例如正则表达式abc+d可分割得到模糊字符串c+；\n[0096] (b)对于分支符号，若与分组符结合使用，则将分组内所有分支作为一个模糊字符串，否则不分割；\n[0097] (c)其余模糊因子作为分隔符，自身作为一个模糊字符串。\n[0098] (d)所有被模糊子串分开的字符串，作为精确串字符串。\n[0099] 最后，通过定义的模糊判定条件，扫描正则表达式，将其分割成顺序的精确字符串和模糊字符串，并保留字符串之间的位置关系。\n[0100] 下面举例说明：\n[0101] 例1：正则表达式\n[0102] “(20[01][\\x09－\\x0d－～]＊(A U T H IN FO U SE R|new s)finger”可分割成“20，[01][\\x09－\\x0d－～]＊(A U T H IN FO U SE R|new s)，finger”的3个字符串。第一个“20”和最后一个“finger”均为精确字符串，中间的”[01][\\x09－\\x0d－～]＊(A U T H IN FO U SE R|new s)”为模糊字符串。\n[0103] 在分割之后，也可以再进一步对模糊字符串进行确定化处理，接下来通过举例方式对模糊字符串的确定化过程进行解释说明。\n[0104] 确定化方法是针对一些特定构成的模糊字符串作进一步确定化，实施原则是：操作简单，不缩小语义覆盖范围，相邻精确字符串合并，分割的字符串数量可控。例如，可以分步实施：\n[0105] (1)对于包含后缀符或词组的模糊字符串，将其确定化为携带精确字符的字符串，例如将“a{m，n}，a{m}，a{m，}”确定化为“a…a{0，n－m}，a…a{0}，a…a＊”其中“…”表示a展开m次，；将确定化之后的精确字符与相邻的分割得到的精确字符串合并。\n[0106] 例2：正则表达式“abc{3，10}de”分割成“ab，c{3，10}，de”，经过模糊字符串确定化将c{3，10}确定化为cccc{0，7}，则将其与左边相邻的精确字符串“ab”合并得到“abccc，c{0，7}，de”。\n[0107] 再例如，将“a+”确定化为“aa＊”，将确定化之后的精确字符与相邻的分割得到的精确字符串合并。\n[0108] 例3：正则表达式“abc+de”分割成“ab，c+，de”，将其中的模糊字符串“c+”确定化为“cc＊”，再按照分割后的字符串位置关系，将其与相邻的精确字符串“ab”进行合并，得到“abc，c＊，de”；\n[0109] 例4：正则表达式“ab(cd)+de”分割成“ab，(cd)+，de”，将其中的模糊字符串“(cd)+”确定化为(cd)(cd)＊，最后进行合并得到“ab，(cd)，(cd)＊，de”。\n[0110] (2)对于包含分组符的模糊字符串，若内部不包含分支符“|”和后缀符或词组，可以直接删除分组符，并尽量与相邻精确字符串进行合并，这种情况下，上述例4可以进一步确定化为“abcd，(cd)＊，de”。\n[0111] (3)对于包含分支符的模糊字符串，则尝试提取公共前缀和后缀字符串，并尽量与相邻精确字符串进行合并。\n[0112] 例5：正则表达式“x(abcde|abcfe)y”分割成“x，(abcde|abcfe)，y”后确定化为“xabc，(d|f)，ey”。\n[0113] 若无公共前缀和后缀字符串，但分支数量较少，且每个分支都具有较长的精确字符串，可以对模糊字符串进行分支展开。\n[0114] 例如：对上述例1进行分支展开后确定化为“20，[01][\\x09－\\x0d－～]＊，A U T H IN FO U SE R，finger”或“20，[01][\\x09－\\x0d－～]＊，news，finger”。\n[0115] 通过上述几种确定化的具体实现方式，可以对一些模糊字符串作进一步确定化，以达到扩展精确字符串长度的目的。\n[0116] 另外，关于上文描述的正则表达式超集的生成方法，下面以PCRE语法正则表达式为例，来描述如何生成正则表达式超集。\n[0117] 如上文描述的正则表达式超集的生成方法包括：对正则表达式进行分割得到精确字符串和模糊字符串，采用逻辑关系符号替代所述模糊字符串，根据所述精确字符串和所述逻辑关系符号生成正则表达式超集；所述逻辑关系符号用于表征所述模糊字符串与其相邻的精确字符串之间的逻辑关系。\n[0118] 该方法涉及到的分割部分可以参见上文对S201的相应描述部分，在得到精确字符串和模糊字符串之后，也可以进一步地对模糊字符串作确定化处理，删除未能确定化的模糊字符串，并记录该模糊字符串的数据长度范围。然后将，根据字符串间的原始位置关系和逻辑关系重新组合成新的表达式，这个新的表达式描述的数据集合就是原正则表达式的超集，在本发明中称之为正则表达式超集，一个正则表达式对应一个超集。\n[0119] 正则表达式超集允许匹配成功的数据更广泛，并且排除了原正则表达式中空间复杂度和时间复杂度都相对更高的模糊因子多模式匹配部分，具有更高的匹配效率，因而可以提高第二层过滤的性能。\n[0120] 在实际应用中可以针对不同语法的正则表达式，结合正则表达式的特点来生成对应的超集，可以针对常见的模糊字符串形式定义相应的逻辑符号或判定符号，一般来说，至少要包含：顺序与、与、或，长度判定符号等逻辑关系符号。\n[0121] 下面给出一种示例：\n[0122] (1)字符串间的“顺序与”关系用“..”表示，例6：正则表达式abc.＊def的表达式超集为“abc”..“def”，表达先匹配字符串“abc”再匹配“def”。\n[0123] (2)字符串间的“或”关系用“|”表示。\n[0124] 例如：之前例1的表达式超集为“20”..“A U T H IN FO U SE R”..“finger”或“20”..“news”.“. finger”，引入或符号后进一步表示为：(“20”.“. A U T H IN FO U SE R”..“finger”)|(“20”..“news”..“finger”)。\n[0125] (3)字符串间的“与”关系用“&”表示。\n[0126] 优选的，(“A”..“B”)|(“B”.“. A”)可以优化为“A”&“B”，例7：正则表达式“abc.＊def”|“def”.＊“abc”的表达式超集为“abc”&“def”。\n[0127] (4)和一般的表达式一样，字符串通过()来提升优先级别。或者在无需提升优先级的情况下，用来明确字符串分组。比如结合长度判定符号使用。长度判定符号包括：＞，＞＝，＜，＜＝，＝＝。\n[0128] 例8：正则表达式“abc{3}def”的表达式超集为(“abc”.“.def”)＝＝8，表达先匹配“abc”再匹配“def”且匹配区域大小是8。\n[0129] 总结以上例子如下表所示：\n[0130]\n[0131]\n[0132] 上文描述了本发明提供的多模式正则表达式匹配方法，下面对本发明提供的多模式正则表达式匹配装置进行解释说明。\n[0133] 参考图3，图3是本发明的多模式正则表达式匹配装置实施例的结构图，该装置可以包括：\n[0134] 第一层过滤单元301，用于按照预先建立的第一层过滤特征集对待匹配数据进行过滤得到第一层过滤的数据分片和命中的精确字符串；所述第一层过滤特征集包括：从每个正则表达式提取的一个长度超过预设阈值的精确字符串；\n[0135] 第二层过滤单元302，用于根据所述命中的精确字符串查找对应的正则表达式超集，按照所述正则表达式超集对所述第一层过滤的数据分片进行第二层过滤得到第二层过滤的数据分片和命中的正则表达式超集；所述正则表达式超集是根据正则表达式的精确字符串和模糊字符串的逻辑关系组成的表达式；\n[0136] 匹配单元303，用于根据所述命中的正则表达式超集确定对应的正则表达式，利用所述正则表达式对所述第二层过滤的数据分片作匹配。\n[0137] 优选的，所述装置还包括：\n[0138] 第一层过滤特征集生成单元，用于生成所述第一层过滤特征集；\n[0139] 所述第一层过滤特征集生成单元，包括：\n[0140] 字符串分割子单元，用于对每个正则表达式进行分割得到对应的精确字符串和模糊字符串；\n[0141] 备选字符串集生成子单元，用于从每个正则表达式对应的精确字符串中选择长度超过预设阈值的精确字符串，将选择的精确字符串组合成备选字符串集；\n[0142] 第一过滤特征集生成子单元，用于按照精确字符串的优先级顺序从所述备选字符串集中针对每个正则表达式选择一个精确字符串组合成第一层过滤特征集。\n[0143] 优选的，所述第一过滤特征集生成单元还包括：\n[0144] 确定化子单元，用于将所述模糊字符串进行确定化，并与相邻的精确字符串分片合并。\n[0145] 优选的，所述第一层过滤特征集生成子单元具体用于：\n[0146] 按照字符串长度大小关系来设置所述备选字符串集中每个正则表达式对应的精确字符串的优先级顺序，且该优先级顺序在使用过程中根据第一层过滤和第二层过滤的结果进行调整；从每个正则表达式对应的精确字符串中选择优先级最高的精确字符串以组合成第一层过滤特征集。\n[0147] 优选的，所述装置还包括：\n[0148] 正则表达式超集生成单元，用于对正则表达式进行分割得到精确字符串和模糊字符串，采用逻辑关系符号替代所述模糊字符串，根据所述精确字符串和所述逻辑关系符号生成正则表达式超集；所述逻辑关系符号用于表征所述模糊字符串与其相邻的精确字符串之间的逻辑关系。\n[0149] 本发明提出了通过两层过滤的方式来提高过滤效果，具体的是按照预先建立的第一层过滤特征集对待匹配数据进行过滤得到第一层过滤的数据分片和命中的精确字符串；\n所述第一层过滤特征集包括：从每个正则表达式提取的一个长度超过预设阈值的精确字符串；这里的第一层过滤特征集保护的精确字符串是按照长度大小提取的，有别于现有技术中的精确串，从而使得第一层过滤能起到降低纯净数据通过率的作用，由于第一层过滤特征集里的精确字符串具有每个正则表达式只选一个精确字符串来参与的特点，能够保证过滤速率。\n[0150] 在第一层过滤完成时，接着进行第二层过滤，具体是根据所述命中的精确字符串查找对应的正则表达式超集，按照所述正则表达式超集对所述第一层过滤的数据分片进行第二层过滤得到第二层过滤的数据分片和命中的正则表达式超集；所述正则表达式超集是根据正则表达式的精确字符串和模糊字符串的逻辑关系组成的表达式；由于第二层过滤采用的是正则表达式超集，其描述能力已经十分接近原始的正则表达式，能够做到尽可能排除不匹配的数据，以过滤出最接近原始正则表达式的数据分片，避免大量的“浑浊”数据进入到最后的正则表达式匹配阶段，以间接提高匹配效率，同时将多模式匹配分解到不同场景(不同数据分片)上的单模匹配，进而避免了DFA空间膨胀或NFA匹配速度过慢的问题。最后，对第二层过滤得到的数据分片，利用其对应的正则表达式作单条匹配。因此，本发明的技术方案通过两层过滤方式提高过滤速率和过滤效果，进而以保证匹配性能的稳定性，在保证攻击性数据被过滤的情况下，尽可能避免纯净数据的通过。\n[0151] 需要说明的是，本说明书中的各个实施例均采用递进的方式描述，每个实施例重点说明的都是与其他实施例的不同之处，各个实施例之间相同相似的部分互相参见即可。\n对于装置类实施例而言，由于其与方法实施例基本相似，所以描述的比较简单，相关之处参见方法实施例的部分说明即可。\n[0152] 最后，还需要说明的是，在本文中，诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者设备所固有的要素。在没有更多限制的情况下，由语句“包括一个……”限定的要素，并不排除在包括所述要素的过程、方法、物品或者设备中还存在另外的相同要素。\n[0153] 以上对本申请所提供的多模式正则表达式匹配方法及装置进行了详细介绍，本文中应用了具体个例对本申请的原理及实施方式进行了阐述，以上实施例的说明只是用于帮助理解本申请的方法及其核心思想；同时，对于本领域的一般技术人员，依据本申请的思想，在具体实施方式及应用范围上均会有改变之处，综上所述，本说明书内容不应理解为对本申请的限制。