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

摘要

本发明实施例提供了一种正则表达式匹配的方法及装置，该方法包括：输入待匹配报文及DFA状态表，DFA状态表包括状态迁移表，其包括正则表达式匹配过程中的所有状态地址和各个状态之间的迁移关系；判断当前状态对应的数据类型，包括单个字符Char型和多个字符Str型，Str型对应的数据为连续的多个字符；若是Str型，则将待匹配报文中当前状态的多个字符值与匹配条件进行匹配处理，当匹配时，迁移至符合匹配条件的下一状态；若是Char型，则将待匹配报文中当前状态的单个字符值与匹配条件进行匹配处理，当匹配时，迁移至符合匹配条件的下一状态；当下一状态为接受态时，结束匹配过程并输出匹配成功结果。该方法匹配速度快、效率高，DFA表项占用的存储空间小。

主权项

一种正则表达式匹配的方法，其特征在于，所述方法由正则表达式引擎执行，所述正则表达式引擎与通用处理器或者网络处理器配合，实现以下功能：报文过滤、攻击防护、病毒检测、垃圾邮件过滤、协议检测或者基于协议的流量监控；所述方法包括：输入待匹配报文及确定性有限自动机DFA状态表，所述DFA状态表包括状态迁移表，所述状态迁移表中包括正则表达式匹配过程中的所有状态地址和各个状态之间的迁移关系，所述迁移关系包括匹配条件及符合匹配条件的下一状态；所述DFA状态表还包括字符映射表，所述字符映射表中包括字符值与映射值之间的映射关系；判断当前状态对应的数据类型，所述数据类型包括单个字符Char型、多个字符Str型和重复字符Rep型，所述Str型对应的数据为连续的多个字符，所述Rep型对应的数据为连续出现多次的属于一定范围内的多个字符；如果当前状态对应的数据类型是Char型，所述匹配条件包括：预先配置的Char型数据的映射值，所述符合匹配条件的下一状态包括：对应于预先配置的Char型数据的映射值和当前状态的状态号的下一状态的地址；对Char型数据的匹配处理过程包括：将待匹配报文中当前状态的单个字符值对应的映射值与预先配置的Char型数据的映射值进行比较，如果一致，则根据当前状态的状态号和当前状态的映射值，查询所述状态迁移表以获得下一状态的地址，并迁移到下一状态；如果当前状态对应的数据类型是Str型，所述匹配条件包括：存储于StrLen字段中的预设字符个数n1，其中，n1为正整数；以及存储于String字段中的预设的n1个字符各自的字符值；所述符合匹配条件的下一状态包括：存储于StrExitSt字段中的Str型数据匹配成功后迁移至下一状态的地址；对Str型数据的匹配处理过程包括：将待匹配报文中当前状态的n1个字符值，与String字段存储的n1个字符值依次进行比较，当全部相等时，根据StrExitSt字段指示的下一状态的地址迁移到下一状态；如果当前状态对应的数据类型是Rep型，所述匹配条件包括：存储于Count字段中的相同类型字符的重复次数n2，其中，n2为正整数，以及存储于Mask字段中的Rep型数据的字符集合映射值的掩码，所述掩码用来表示当前字符的映射值是否在预定范围之内，若是，则进行计数，直到达到预定计数值；所述符合匹配条件的下一状态：存储于RepExitSt字段中的指示Rep型数据匹配成功后迁移至下一状态的地址；对Rep型数据的匹配处理过程包括：将待匹配报文中n2个字符分别对应的映射值与Mask字段中的掩码进行比较，当 n2个字符各自对应的映射值全部在掩码范围内时，根据所述RepExitSt字段指示的下一状态的地址迁移到下一状态；当所述下一状态为接受态时，结束匹配过程并输出匹配成功结果。