用于文本或网络内容分析的大规模特征匹配的方法

摘要

本发明提供了一种用于文本或网络内容分析的大规模特征匹配的方法，包括步骤：S1.读入所有特征串，建立双哈希表；S2.在哈希表内建立有限状态机；S3.将哈希表内的有限状态机转化为双数组结构存储；S4.文本或网络内容匹配搜索。本发明的方法能够有效提升文本或网络内容分析的匹配速度，降低内存消耗。

说明书

技术领域

本发明属于计算机数据处理技术领域，特别涉及一种用于文本或 网络内容分析的大规模特征匹配的方法。

背景技术

多模式匹配是计算机科学领域中的基本问题之一。其需要解决的 问题就是快速而准确地判断待测文本或者网络内容中所有出现任意模 式串的位置。多模式匹配技术的应用领域非常广泛，除了已经得到广 泛应用的网络入侵检测/防御系统（IDS/IPS）、病毒扫描系统，垃圾邮 件过滤系统，应用层网络协议分析系统、网络审计系统和最近提出的 统一威胁管理（Unified Threat Management，UTM）系统等网络安全领 域，还扩展到其它学科和领域，例如信息管理、网络搜索引擎和生物 信息学当中的基因序列检测等。因此，研究和发展多关键词匹配技术 具有很强的学术和实际意义，被相关的学术和业界所关注。

多关键词匹配技术已经存在许多经典算法，按照在滑动窗口内的 匹配策略，可以分为前缀算法（Prefix-based Algorithms）、后缀算法 （Suffix-based Algorithms）两类，其中滑动窗口的大小取决于最短特 征串长度。前缀算法是在滑动窗口内由前往后匹配，比如KMP、Aho  Corasick等，后缀算法是在滑动窗口内由后往前匹配，比如 Boyer-Moore、BMH、Commentz-Walter、WuManber等。这些字符串 匹配算法各有所长，应用于不同的场景。

AC算法是贝尔实验室的Aho和Corasick提出的目前应用最广泛 的一种多模式特征匹配算法。该算法采用有限状态自动机（Finite State  Automaton，FSA）的思想来一次性预处理所有的模式串。有限状态机 FSM（Finite State Machine）是包含一组状态集（states）、一个起始状 态（start state）、一组输入符号集（alphabet）、一个映射输入符号和当 前状态到下一状态的转换函数（transition function）的计算模型。算法 将待匹配的文本串T视为一个流，当流进入状态机之后，每输入一个 字符都会使得自动机改变一种状态，并检测是否可能发生了匹配。文 本串长度N决定了AC算法复杂度，其复杂度为O(N)。对于中小规模 特征匹配，AC算法相比于其他算法具有匹配速度恒定的优点，具有高 性能鲁棒性和良好的可扩展性。但是，当面对大规模特征匹配时，它 指数级增长的内存空间消耗，对算法的性能构成了致命的威胁。

双数组算法是建立在AC算法思想的基础上，基于改进的有限状 态机的多模式匹配算法。双数组算法利用一个二维数组构成的矩阵形 式来表示trie树。双数组包含两个整数数组base[]和check[]。base数 组的值相当于trie树的一个节点，check数组的值相当于当前状态的前 一状态，在算法匹配过程中，base起跳转作用，check起校验作用。如 果base和check同时为0，则代表该位置为空状态，如果base为负值， 则表示该状态匹配成功。设前一状态为s，后一状态为t，c为目前输 入的变量，则它们之间必须满足：check[base[s]+c]＝s；base[s]+c=t。双 数组算法是根据base[s]+c的值进行状态间的跳转的，设文本串长度为 N，所以双数组算法复杂度为O(N)。由于采用的是数值运算和数组读 取操作，避免了字符串比较和拷贝，因此双数组算法具有匹配方式简 单，单次遍历速度快的特点。但是，由于双数组算法同样是基于有限 状态机的，当模式集规模增大时，其内存消耗也非常严重。同时，尽 管单次遍历速度很快，但由于无法跳跃，限制了算法整体的匹配速度。

WM（Wu-Manber）算法是由台湾的Sun Wu和美国的亚利桑那大 学的Udi Manber提出的，采用坏字符块的启发策略取代了BMH算法 中的坏字符策略，充分地降低了坏字符块在字符串中出现的概率，从 而十分有效地增加了跳跃效率。WM算法引入了shift表来避开无谓的 比较操作，达到跳跃的目的，hash表来链接其对应的多条特征串，同 时也引入prefix表来过滤不可能匹配的字符串，从而提升算法的性能。 设B是块字符的长度，N是文本的长度，M是特征串的最短长度，则 WM算法的平均复杂度是O(BN/M)。WM算法基于跳跃匹配的思想， 并采用了哈希函数，算法效率非常高。但是，当面对大规模模式集时， 容易产生哈希冲突问题，此时便只能利用精确的BF算法进行匹配， 导致算法性能的急速下降。另外，WM算法在逐个精确匹配完成返回 时，滑动窗口只能从左向右移动一个字符，算法性能受到很大影响。

随着计算机应用和网络应用的普及，数据处理量日益增大。尤其 是在网络应用环境中，存在大量的实时数据处理的需求，例如：网络 内容过滤、防病毒、反垃圾邮件、短信过滤、网络入侵检测和防御等。 在这些应用中，由于数据处理量和用户需求的不断增大，关键词数量 也会不断的增大，规模常常达到上千万级。著名的开源病毒扫描软件 ClamAV的病毒特征库条目达到了75万条，同时著名的URL黑名单 Url Blacklist已经达到349万条，而且它们都还在不断地增长。目前大 多数经典的模式匹配算法是在小到中等规模的模式集背景下设计、测 试和使用的。这些算法并未考虑到模式集中字符出现概率不均带来的 严重问题，并不能直接有效地运用到拥有大规模模式集的文本或者网 络内容的处理中。因此，迫切需要引入新的思路和方法，来解决模式 匹配算法的性能瓶颈问题，并使之更适用于大规模模式串集背景下的 文本或者网络内容的处理应用。

发明内容

（一）要解决的技术问题

本发明要解决的技术问题是：如何提供一种大规模特征匹配的方 法，能够有效提升文本或网络内容分析的匹配速度，降低内存消耗。

（二）技术方案

为了解决上述问题，本发明提供了一种用于文本或网络内容分析 的大规模特征匹配的方法，包括步骤：S1.读入所有特征串，建立双 哈希表；S2.在哈希表内建立有限状态机；S3.将哈希表内的有限状态 机转化为双数组结构存储；S4.文本或网络内容匹配搜索。

优选地，步骤S1包括：S1.1依次读取所有特征串，将特征串信 息存入PAT结构体；S1.2根据特征串规模、运行平台、缓存大小确定 两级哈希表，即SHIFT表和MAP表的长度N1、N2，以及哈希字符块 的长度B；S1.3初始化SHIFT表和MAP表，统计特征串集合中的最 短特征串长度m，并将SHIFT表及MAP表中所有表项的跳跃值初始 化为m-B+1；S1.4对PAT结构体链表中特征串的所有字符块进行两级 哈希运算，保存跳跃值到SHIFT表并链接相应的特征串到不同MAP 表表项的入口；S1.5计算并保存MAP表的匹配跳跃属性值，即skip 值。

优选地，步骤S1.2包括：S1.2.1确定SHIFT表大小和MAP表大 小，即SHIFT表和MAP表表项数目；S1.2.2确定两级哈希表分别相 对应的HASH函数hash_1、hash_2。

优选地，步骤S1.4包括：S1.4.1对所有特征串中的字符块从后至 前依次通过hash_1函数运算，并根据字符块距离特征串最末端的距离 确定对应的SHIFT表跳跃值；S1.4.2对所有特征串中的后缀字符块通 过hash_2函数运算，并将相应的指向特征串的内存指针保存至对应的 MAP表结构体链表中。

优选地，步骤S1.5包括：S1.5.1对所有特征串中的非后缀字符块 通过hash_1函数运算，并判断运算结果是否为0；S1.5.2对所有通过 hash_1函数运算结果为0的字符块通过hash_2函数运算，并保存当前 字符块距离特征串最末端的距离值至MAP表结构体中，如果有多个距 离值，则保存最小的。

优选地，步骤S2包括：S2.1统计MAP表中每个表项链接特征 串的数目；S2.2对于MAP表表项中链接特征串数目大于1的表项根 据其特征串建立有限状态机。

优选地，步骤S3包括：S3.1预编码阶段，对有限状态机中出现 的所有字符进行编码；S3.2遍历阶段，利用递归算法一次性完成Base 和Check双数组的构建；S3.3释放MAP表表项中建立的有限状态机 所占内存。

优选地，步骤S3.2中：Base和Check数组需要满足的条件是： check[base[s]+c]=s，并且base[s]+c=t，其中s代表当前状态，t代 表下一状态，c代表当前输入字符编码值。

优选地，步骤S4包括：S4.1在文本开始处设置滑动窗口，滑动 窗口大小为最短特征串长度；S4.2对滑动窗口内的后缀字符块通过 HASH函数hash_1运算得到字符块对应的SHIFT表表项，查看表项中 skip值是否为0；S4.3如果SHIFT表表项中skip值不为0，则将文本 滑动窗口向右移动skip值的距离并返回S4.2继续执行，如果SHIFT 表表项中skip值为0，则进入S4.4；S4.4对滑动窗口内的后缀字符 块通过HASH函数hash_2运算得到字符块对应的MAP表表项，查看 是否存在链接的特征串；S4.5如果MAP表表项中不存在链接特征 串，则进入S4.8，如果MAP表表项中链接特征串数目为1，则进入 S4.6，如果MAP表表项中链接特征串数目大于1，则进入S4.7；S4.6采 用Brute Force算法快速对比当前滑动窗口起始端的字符串与MAP表 表项中链接的特征串，如果对比结果相等，则匹配成功并返回，如果 对比不相等，则进入S4.8；S4.7采用MAP表表项中链接的双数组一 次性快速匹配查询当前滑动窗口起始端开始的字符串，如果匹配成功 则返回，如果匹配失败，则进入S4.8；S4.8查询MAP表表项中存放 的匹配跳跃属性值，即skip值大小，并根据此值向右移动文本滑动窗 口skip值距离，并返回S4.2；S4.9如果滑动窗口已滑至文本的最末 端仍未匹配成功，则匹配结束并返回匹配失败。

优选地，步骤S4.7包括：S4.7.1根据滑动窗口起始端的首字符的 编码确定双数组的起始状态值，并得到其Base数组取值；S4.7.2将 上一步得到的base值与滑动窗口字符串输入的下一个字符的编码值相 加，得出的结果作为跳转的下一状态号并跳转；S4.7.3校验当前状态 的check值是否等于上一状态号，如果不等，则匹配失败并返回，如 果相等，则继续判断base值是否为负，为负则匹配成功并返回，否则， 进入S4.7.2。

（三）有益效果

本发明的方法可以应用于大规模的文本或网络内容分析，该方法 可以处理的特征串集规模可达到千万级，在保证内存消耗的情况下达 到了数百倍的匹配速度（大于100Mbps）；同时，解决了精确匹配中存 在的哈希冲突问题，对于任意的特征串集合均可保证稳定的查找速率 和匹配时间；并且本发明的方法更适合于特征串集合的更新删除操作， 使更新删除系列操作效率高，易于管理及实际应用。

附图说明

下面参照附图并结合实例来进一步描述本发明。其中：

图1为根据本发明实施例的大规模特征匹配的方法流程图。

图2为根据本发明实施例的SHIFT表和MAP表初始化结构示意 图。

图3为根据本发明实施例的SHIFT表和MAP表预处理完成结构 示意图。

图4为根据本发明实施例的MAP表项中链接构建的有限状态机结 构示意图。

图5为据本发明实施例的所有可能出现的字符编码结构示意图。

图6为据本发明实施例的双数组构建结构示意图。

具体实施方式

下面结合附图和实施例，对本发明的具体实施方式作进一步详细 描述。以下实施例用于说明本发明，但不用来限制本发明的范围。

如图1所示，依照本发明一种实施方式的大规模特征匹配的方法 包括步骤：

S1.读入所有特征串，建立双哈希表。

S2.在哈希表内建立有限状态机。

S3.将哈希表内的有限状态机转化为双数组结构存储。

S4.文本匹配搜索。

其中，步骤S2和步骤S3循环交替执行。

其中，步骤S1进一步包括：

S1.1依次读取所有特征串{lightweight,facebook,globalcom, microsoft,sunshine,moonlight,starlight}，将特征串信息存入PAT结构 体。

S1.2根据特征串规模、运行平台、缓存大小确定两级哈希表 （SHIFT表、MAP表）的长度N1、N2，以及哈希字符块的长度B。

S1.3如图2所示，初始化SHIFT表和MAP表，统计特征串集合 中的最短特征串长度m，并将SHIFT表及MAP表中所有表项的跳跃 值初始化为m-B+1。

S1.4如图3所示，对PAT结构体链表中特征串的所有字符块进行 两级哈希运算，保存跳跃值到SHIFT表并链接相应的特征串到不同 MAP表表项的入口。

S1.5计算并保存MAP表的匹配跳跃属性值(skip值)。

其中，步骤S1.2进一步包括：

S1.2.1确定SHIFT表大小和MAP表大小，即SHIFT表和MAP 表表项数目N1=26，N2=23。

S1.2.2确定两级哈希表分别相对应的HASH函数hash_1、hash_2。

hash1

h₁(block)＝(*(block))&0x03FFFFFF

hash2

h₂(block)＝((*(block)《15)+(*(block《10)+(*(block+2)《5)+* (block+3))&0x007FFFFF

其中，步骤S1.4进一步包括：

S1.4.1对所有特征串中的字符块从后至前依次通过hash_1函数运 算，并根据字符块距离特征串最末端的距离确定对应的SHIFT表跳跃 值。

S1.4.2对所有特征串中的后缀字符块通过hash_2函数运算，并将 相应的指向特征串的内存指针保存至对应的MAP表结构体链表中。

其中，步骤S1.5进一步包括：

S1.5.1对所有特征串中的非后缀字符块通过hash_1函数运算，并 判断运算结果是否为0。

S1.5.2对所有通过hash_1函数运算结果为0的字符块通过hash_2 函数运算，并保存当前字符块距离特征串最末端的距离值至MAP表结 构体中（skip值），如果有多个距离值，则保存最小的。

其中，步骤S2进一步包括：

S2.1统计MAP表中每个表项链接特征串的数目。

S2.2对于MAP表表项中链接特征串数目大于1的表项根据其特 征串建立有限状态机，例如若对图3中的MAP表项h2(hine/ligh)构建 有限状态机，结果如图4所示：。

其中，步骤S3进一步包括：

S3.1预编码阶段，对有限状态机中出现的所有字符进行编码，编 码结果如图5所示。

S3.2遍历阶段，利用递归算法一次性完成Base和Check双数组 的构建，构建的双数组如图6所示。

S3.3释放MAP表表项中建立的有限状态机所占内存。

其中，在步骤S3.2中：

Base和Check数组需要满足的条件是：check[base[s]+c]=s并且 base[s]+c=t。其中s代表当前状态，t代表下一状态，c代表当前输 入字符编码值。

其中，步骤S4进一步包括：

S4.1在文本开始处设置滑动窗口，滑动窗口大小为最短特征串长 度。

S4.2对滑动窗口内的后缀字符块通过HASH函数hash_1运算得 到字符块对应的SHIFT表表项，查看表项中skip值是否为0。

S4.3如果SHIFT表表项中skip值不为0，则将文本滑动窗口向右

移动skip值的距离并返回S4.2继续执行；如果SHIFT表表项中 skip值为0，则进入S4.4。

S4.4对滑动窗口内的后缀字符块通过HASH函数hash_2运算得 到字符块对应的MAP表表项，查看是否存在链接的特征串。

S4.5如果MAP表表项中不存在链接特征串，则进入S4.8；如果 MAP表表项中链接特征串数目为1，则进入S4.6；如果MAP表表项 中链接特征串数目大于1，则进入S4.7。

S4.6采用Brute Force算法快速对比当前滑动窗口起始端的字符 串与MAP表表项中链接的特征串，如果对比结果相等，则匹配成功并 返回；如果对比不相等，则进入S4.8。

S4.7采用MAP表表项中链接的双数组一次性快速匹配查询当前 滑动窗口起始端开始的字符串，如果匹配成功则返回；如果匹配失败， 则进入S4.8。

S4.8查询MAP表表项中存放的匹配跳跃属性值（skip值）大小， 并根据此值向右移动文本滑动窗口skip值距离，并返回S4.2。

S4.9如果滑动窗口已滑至文本的最末端仍未匹配成功，则匹配结 束并返回匹配失败。

其中，步骤S4.7进一步包括：

S4.7.1根据滑动窗口起始端的首字符的编码确定双数组的起始状 态值，并得到其Base数组取值。

S4.7.2将上一步得到的base值与滑动窗口字符串输入的下一个字 符的编码值相加，得出的结果作为跳转的下一状态号并跳转。

S4.7.3校验当前状态的check值是否等于上一状态号，如果不等， 则匹配失败并返回。如果相等，则继续判断base值是否为负，为负则 匹配成功并返回；否则，进入S4.7.2。

本发明的描述是为了示例和描述起见而给出的，而并不是无遗漏 的或者将本发明限于所公开的形式。很多修改和变化对于本领域的普 通技术人员而言是显然的。选择和描述实施例是为了更好说明本发明 的原理和实际应用，并且使本领域的普通技术人员能够理解本发明从 而设计适于特定用途的带有各种修改的各种实施例。