一种空间高效的多模式串匹配方法和系统的制作方法

一种空间高效的多模式串匹配方法和系统的制作方法
【技术领域】
[0001] 本发明设及信息过滤、信息检索、计算生物学等领域，具体设及一种空间高效的多 模式串匹配方法和系统。
【背景技术】
[0002] 近年来，随着宽带技术的发展和多媒体应用的流行，互联网技术得到极大的普及 和发展。随着网络用户飞速增长的同时，攻击模式亦飞速增长，对入侵检测系统的需求亦随 之增加。面对当前互联网协议设计缺陷、计算机系统漏洞、网络入侵攻击等日趋严峻的网络 安全问题，已有算法的存储空间和运算速度已经难W满足高速网络环境下对特征串实时匹 配的应用需求。因此，设计更加高效的多模式串匹配系统，具有重要的理论和实际意义。
[0003] 文献(EfficientStringMatching:AnAidtoBibliographic Search,CommunicationsoftheACM, 333-340, 197巧提出了基于前缀捜索的多模式串匹 配算法一Aho-Corasick算法（简称AC算法），从模式串集合构建AC自动机，通过对自动机 的访问进行匹配。该算法匹配的时间复杂度正比于待扫描文本长度，不受关键词长度和文 本统计特征的影响，性能比较稳定。但是需要巨大的存储空间来存储自动机，通常不是最快 的匹配算法。
[0004] 文献（AFastAlgorithmforMulti-PatternSearching,Universityof Arizona,Tech.Rep.TR94-17, 1994)提出的基于后缀捜索的方法一Wu-Manber算法（简称 WM算法），是Boyer-Moore算法的扩展和改进。该算法使用散列函数将所有可能的字符块 散列到跳跃距离表甜IFT上，然后利用甜IFT表进行快速地移动W跳过不可能匹配的文本 字符。Wu-Manber算法简单高效，实际效果好。但该算法适合于字符集比较大、模式串长度 比较长的应用场景，不适用于模式串长度比较短的场景。
[0005] 文献（Ahighthroughputstringmatchingarchitectureforintrusion detectionandprevention,ComputerArchitecture,ISCA' 05.Proceedings, 32nd InternationalSymposium,pages: 112-122, 2005)提出了一种按位拆分的自动机存储结构 bit-split。该方法将一个AC有限状态机按位拆分为一组较小的AC有限状态机，W减少总 内存需求。但是按位分割存储结构是一种基于硬件的实现方案，软件实现效率较低。
[0006]文献（Hi曲-PerformancePattern-MatchingforIntrusionDetection,INF0C0M 2006, 25thIEEEInternationalConferenceonComputerCommunications,Proceedings ，pages: 1-13,April2006)提出了一种基于硬件实现的可编程状态机机制。该方法将模式 串集聚类拆分，并将状态存放在一个256行的表中，移除AC有限状态机中那些转移到初始 状态和初始状态的下一个状态的状态。采用散列函数来减小内存开销，用上界4限制状态 转移的最大哈希冲突数目。但是对哈希冲突的处理会增加存储器访问次数，降低算法的性 能。
[0007] 文献(Hash-AV:Fastvirussignaturescanningbycacheresident filters,InternationalJournalofSecurityandNetworks, 2 (1-2) : 50-59, 2007)提出 的化sh-AV，作为WM的一个变体，使用一组散列函数和适合于CPU二级高速缓存的布隆过滤 器阵列。化sh-AV在不访问主存储器情况下，过滤掉多数的"不匹配"情况，在缓存中实现快 速扫描。但不可避免的继承了WM的缺陷，该算法同样不适用于模式串长度比较短的场景。
[0008] 文献（AMemoryEfficientMultiplePatternMatchingArchitecturefor NetworkSecurity,INFOCOM2008,The27化ConferenceonComputerCommunications,IE 邸，pages: 166-170, 2008)设计了基于缓存的确定性有限自动机的匹配算法ACC,提出后继 状态寻址机制来存储和访问内存中DFA的状态转移边。运用此种方法，转移边可W被有效 地存储和直接访问。然而在该机制下，仍然使用传统二维存储结构存储有多条状态转移边 的状态。当此类状态增加时，算法性能降低。
[0009] 文献（Memory-EfficientPatternMatchingArchitecturesUsingPerfect 化shingonGr耶hieProcessingUnits,INFOCOM2012,pages: 1978-1986, 2012)义用完美 哈希函数来压缩状态转移表，W消除哈希冲突。相比传统的二维存储结构，算法在性能和内 存使用效率上均有所提高。但在实际应用中，计算完美哈希函数的代价很大，会极大地影响 算法的性能。对完美哈希函数值的计算亦受到存储空间的制约，加重了算法在GPU上访问 内存的开销。
[0010] 在之前的模式匹配技术中，运用的存储压缩技术主要有W下五种：完全矩阵，存储 所有的元素，用一个固定大小的向量表示一行；行压缩，完全紧凑的存储方式，顺序查找或 二分查找；Band-Row,存储第一个到最后一个非零元素之间所有的元素；Bitmap,用一个比 特位标识某个元素是否为空；Perfect化sh，找到一个一一映射函数，使得存储空间在线性 范围内。上述方法中，没有最坏情况下的空间开销保证，体现了时间和空间的折衷。虽然上 述方法在某一方面（时间或者空间）是相对高效的，但是根据当前不断增加的信息安全需 求，更好的空间-时间高效的多模式串匹配技术仍需要进一步研究。

【发明内容】

[0011] 随着攻击模式飞速增长，降低内存需求已经成为存储架构的关键。如何有效解决 多模式串匹配算法的软件实现方式中所面临的存储空间瓶颈和性能瓶颈，有着重要意义。 本发明提出了一种新的存储模式串的数据结构一化shTrie，利用位向量表将原模式串矩阵 存储为一维表的形式，避开传统方法存储自动机的状态转移矩阵问题；利用递归的哈希函 数方法求出该个特殊的位向量表，W达到节约存储空间的目的；在哈希函数计算过程中，利 用位运算技巧，将其转化为简单高效的位与运算操作；另外本发明在化shTrie构造和关 键词查找过程中均使用Rank技术，提高了捜索的空间效率和时间效率。此外，本发明提供 了一种空间高效的多模式串匹配技术，并提供了基于该多模式串匹配技术的关键词匹配系 统。
[0012] 根据本发明的一个方面，提供了一种新的存储模式串的数据结构一化shTrie。 化shTrie构造包含如下步骤；
[0013] 1)读入关键词文件；
[0014] 2)对关键词文件进行规范化处理；
[0015] 3)将规范化处理之后的关键词文件进行预处理：
[0016] 3. 1)给位向量表的长度H赋值，|p|=EpepIpI是所有模式 串的长度之和，p表不一个模式串；
[0017] 3. 2)初始化位向量表B，将B的H个位置均置为0 ;
[0018] 3.3)初始化位向量表F，将F的H个位置均置为0;
[0019] 3. 4)采用递归哈希函数计算过滤散列表B和预匹配散列表F两个位向量表，利用 Rank技术计算校验散列表M，最终得到构造化shTrie的B、F、M;
[0020] 3.4.1)构造位向量B和F，对于给定模式串集合P= {p?，pW，…，的 具体构造过程如下：
[0021] 3.4.1. 1)对每一个模式串分"=成)班>山诚)GP的每一个前缀 ? =记'货伯i…知"ep，其中（0《k<r，1《j《化)，利用递归哈希函数计算该前缀的哈希 值h=化sh(U)，同时将位向量B中第h位置为1 ;
[0022] 3.4. 1.2)对于每一个完整的模式串，除了在位向量B中标记其哈希值外，同时将 其标记在另一个位向量F中。即将F中对应的第h位亦置为1，得到位向量F，W此记录完 整模式串的信息。
[0023] 3.4.2)构造校验散列表M，校验散列表M是一个数组，每个数组元素M[t]为一个 链表：
[0024] 3.4.2 .1)对于模式串集合P={p?，pW，…，ph)}中的每一个模式串pW，计算该 模式串的哈希值h:
[0025] & = (a ? A +皆))& (好-4 ;
[0026] 其中a= 22695477 (a是BorlandC/C++编译器中伪随机数生成器的参数，该样可 W保证所选取的哈希函数具有较好的随机性）；
[0027] 3. 4. 2. 2)利用Rank技术，计算位向量F中第h比特位在F中的次序t。然后将该 模式串存入链表M[t]中，t=Rank(F，h)，M(t) =k。
[002引Rank技术是一种快速、高效的位向量查找算法，具体来说，Rank(h)计算位 向量中前h个比特位中1的个数。该方法利用位向量简洁地表示一个集合，并能快 速地查找出原集合中的元素。在文献（AnEfficientImplementationofStatic StringPatternMatchingMachines,IEEETransactionsonSoftwareEngineer! ng，15巧）：1010-1016, 1989)中，对Rank技术进行了详细的描述。概括地说，对于大小为H 的位向量B，可W在0(1)时间复杂度内实现对位向量B的Rank操作，同时仅需要0化）的额 外存储空间。无论从理论分析还是实验验证，Rank技术在时间和空间上均是高效的。
[0029] 根据本发明的另一个方面，提供了一种空间高效的多模式串匹配方法：
[0030] 4)读入文本数据，从输入文本T的每个位置i开始捜索，对于文本位置i(i= 0,…，n-1)，文本T的当前捜索窗口为titw'.'tw。计算当前窗口的哈希值h=化 tw)，查看位向量B中对应的第h个位置的值；
[0031]W查找位向量B和F中相应的位置是否为1，W确定文本字符串titw…tw是否 可能与某个模式串匹配。若为可能匹配，则进一步进行校验：
[00对 5. 1)如果B比]=0,表示titw…tw不可能与某个模式串的前缀匹配，针对当前 文本位置i的扫描结束；
[0033] 5. 2)否则，文本字符串可能与某个模式串的前缀匹配，需要进一步确 认该前缀是否为一个完整匹配。查看位向量F中对应位置的值F比]，若F比]=1，表示当 前文本字符串是一个可能的完整匹配结果。鉴于哈希冲突的存在，需要对其进 行进一步校验。利用Rank操作计算哈希值h在位向量F上的次序t，链表M[t]中的元素即 为可能命中的模式串，将文本字符串与可能命中的模式串--比较，W发现真 正的匹配结果，校验过程结束。
[0034] 5.如设U为模式串集合中最长模式串的长度，1。。,= 1113义。。|口|，若^'<1。。,，则继 续读入下一个字符，执行上述步骤5. 1)和5. 2);若j>Im。,，则当前文本字符串titw…tw 不可能与模式串匹配，针对当前文本位置i的扫描结束。
[003引 6)校验成功，报告匹配结果，否则，回到步骤4)，进行下一次读入、对比、校验。
[0036] 根据本发明的再一个方面，提供了一种基于该种多模式串匹配技术的关键词匹配 系统，包含：
[0037] 关键词集合规范化装置，用于关键词文件（即待匹配模式串集合）的读入，将读入 的文件规范化为统一的形式；
[003引关键词集合预处理装置，针对关键词规范化装置规范之后的关键词集合，构建对 应的过滤散列表、预匹配散列表和校验散列表；
[0039] 文本捜索装置，其根据文本数据计算所述过滤散列表和预匹配散列表的哈希值， 依该值判断是否为可能匹配，并依此计算校验散列表的哈希值，进而对所述文本数据进行 校验。校验之后，报告匹配结果。
[0040] 与现有技术相比，本发明的有益效果如下：
[0041] 本发明运用递归哈希函数，避开之前传统的二维存储架构，直接将模式串集合存 储在一一维位哈希表中，构建一种新的存储模式串信息的数据结构一化shTrie，其中不存 在状态转移表的存储消耗，从而达到节约存储空间的目的，另一方面也减少了对模式串集 合的预处理时间；在哈希函数计算过程中，利用位运算技巧，将其转化为简单高效的位与运 算操作，W提高效率；在预处理阶段和捜索阶段，均利用高效的Rank技术，提高了捜索的空 间效率和时间效率。在实时入侵检测系统中，具有较短预处理时间的串匹配算法更能满足 检测规则生效的时效性要求。经实际测试表明，本发明的空间高效的多模式串匹配技术， 极大地降低了内存开销和预处理时间，更能满足实时入侵检测系统对规则生效的时效性要 求，更适合于模式串集合规模较大、模式串长度较短的多模式串实时匹配问题。
【附图说明】
[0042] 图1是关键词匹配系统结构示意图。
[004引图2是化shTrie数据结构构造示意图。
【具体实施方式】
[0044] 为使本发明的上述目的、特征和优点能够更加明显易懂，下面通过具体实施例和 附图，对本发明做进一步说明。
[0045] 本发明提出的多模式串匹配技术主要包含两个阶段：预处理阶段和捜索阶段。图 1示意了该多模式串匹配技术的基本流程W及关键词匹配系统的结构。基本流程是：读入 关键词文件，算法进入预处理阶段，利用递归哈希函数和Rank操作构建化shTrie。读入文 本数据，进入捜索阶段。利用递归哈希函数计算当前字符串的哈希值，并结合之前构建的 化shTrie，对文本进行逐个字符捜索、校验。最后，报告最终捜索匹配的结果。
[0046] 在预处理阶段，主要任务是构造化shTrie所需的数据结构。化shTrie包含S个数 据结构；位向量B、位向量F和校验散列表M。构建化shTrie的方法如前文所述，其具体算 法见下面算法1。
[0047]算法 1HashTrie的构造（P= {pW，P。)，…，p(r-"})
[0048]
[0049] 在捜索阶段，主要查找可能匹配的模式串并对其进行校验。从输入文本T的每个 位置i开始捜索，使用递归哈希函数计算文本字符串的哈希值，查找位向量B和 F中相应的位置是否为1，W确定文本字符串titw…tw是否可能与某个模式串匹配。若 为可能匹配，则进一步进行校验。具体的捜索和校验过程如下；在捜索过程中，对于文本位 置i(i=〇，…，n-1)，文本T的当前捜索窗口为titw…tw。计算当前窗口的哈希值h= 化sh(titw…tw)，查看位向量B中对应的第h个位置的值；
[0050] (1)如果B比]=0,表示不可能与某个模式串的前缀匹配，针对当前文 本位置i的扫描结束。
[0051] 似否则，文本字符串可能与某个模式串的前缀匹配，需要进一步确认 该前缀是否为一个完整匹配。查看位向量F中对应位置的值F比]，若F比]=1，表示当前 文本字符串是一个可能的完整匹配结果。鉴于哈希冲突的存在，需要对其进行 进一步校验。利用Rank操作计算哈希值h在位向量F上的次序t，链表M[t]中的元素即为 可能命中的模式串，将文本字符串与可能命中的模式串一一比较，W发现真正 的匹配结果，校验过程结束。若j<lmay，则继续读入下一个字符，执行上述步骤（1)和（2); 若j>U，则当前文本字符串titw…tw不可能与模式串匹配，针对当前文本位置i的扫 描结束。
[0化2] 本发明提出的多模式匹配技术的具体算法见下面算法2。
[0化引 算法 2HashTrie算法（T=t0ti…tn_i)
[0054]
[0055] 本发明利用递归哈希函数计算模式串前缀的哈希值，存储到对应的位向量B和F。 再利用Rank技术构建对应的校验散列表M，得到化shTrie。进而在此数据结构基础上，再 次利用Rank技术实施多模式串匹配技术。下面W模式串集合{she,his,this,sheer}为 例，构造对应的化shTrie数据结构，描述具体的实施过程（构造流程图见图2):
[0化6] 1)从磁盘的模式串文件中读出所有的模式串{this, she, his, sheer}，将其存放 在内存中；
[0057]。依据模式串的大小15计算，I戶i=15，/^ = 2パ。&wlPh=256，则设定的散列表B和F的 长度大小为256 ;
[005引扣初始化过滤散列表B=[0, 0,…，0]，（有256个0);
[0059] 4)初始化预匹配散列表F= [0, 0,…，0]，（有256个0);
[0060] 5)计算B、F的值；
[0061] 5. 1)首先计算P? = {this}S个 前缀t、th、thi及模式串自身this对应的哈希 值，并将其对应的B表中第hO个位置置1，过程如下；计算h(t) = 116,置B中第116个 位置为1。
[0062] 5. 2)同理计算可得h(th) = 108，h(thi) = 197，h(this) = 60,将B表中对应的 第108、197、60位置1。在上述迭代过程中，B表中的值不断更新。
[006引 5.如在上述计算中，注意到h(this) = 60，this是其中的一个模式串，该位置对 应的为一个终结状态，将其信息记录在F表中，即F表中第60个位置置1，其余位置为0。
[0064] 5.4)同理，依次计算p("= {she}，p?=化is}，p?= {sheer}的哈希值，将B中 对应的位置置1，同时在F中标记对应终结状态的位置。
[0065] 6)计算M的值；利用Rank技术，根据上述步骤W得到的F和h,计算出M;最终， 得到模式串{this,she,his,sheer}对应的化shTrie数据结构，如图2中所示，其中，B、F 中均有256个位置，未标记位置均为0。
[0066] 本发明运用递归哈希函数，避开之前传统的二维存储架构，直接将模式串集合存 储在--维位哈希表中，构建一种新的存储模式串信息的数据结构一化shTrie，其中不存 在状态转移表的存储消耗，从而达到节约存储空间的目的，另一方面也减少了对模式串集 合的预处理时间；在哈希函数计算过程中，利用位运算技巧，将其转化为简单高效的位与 运算操作，W提高效率；在预处理阶段和捜索阶段，均利用高效的Rank技术。将AC自动 机的指针实现方式（AC)、表实现方式（TAC)、双数组实现方式值AC)和本发明提出的多模 式串匹配技术-HashTrie算法进行对比。在真实数据集和随机数据集上的测试结果表明， 化shTrie算法比AC节约高达99. 6%的内存空间，匹配速度约为AC算法的一半至4倍。此 夕F，化shTrie算法在所有数据集上的预处理时间均是最短的，比AC、TAC和DAC等算法节省 了约90%的预处理时间在存储空间方面，从表1中的实验结果可W看出。
[0067] 表1.化shTrie算法与AC、TAC、DAC实验结果对比
[0068]
[0069]
[0070] 在化shTrie数据结构构造过程中，在保证减小哈希冲突的前提下，可w选择其它 的递归哈希函数；在保证随机性的基础下，a可W选择由BorlandC/C++编译器中伪随机数 生成器生成其它的随机参数值；在保证合适计算量的前提下，位向量表的长度H可W适当 调整。
[0071] W上实施例仅用W说明本发明的技术方案而非对其进行限制，本领域的普通技术 人员可W对本发明的技术方案进行修改或者等同替换，而不脱离本发明的精神和范围，本 发明的保护范围应W权利要求书所述为准。
【主权项】
1. 一种模式串的数据存储结构，其特征在于，包括过滤散列表B、预匹配散列表F和校 验散列表M，该数据存储结构通过如下步骤构建： 1) 读入关键词文件； 2) 对关键词文件进行规范化处理； 3) 对于规范化处理之后的关键词文件，给位向量表的长度H赋值，并初始化位向量表B 和位向量表F ; 4) 采用递归哈希函数计算过滤散列表B和预匹配散列表F两个位向量表，利用Rank技 术计算校验散列表M，最终得到B、F、M。2. 如权利要求1所述的模式串的数据存储结构，其特征在于，步骤3)所述位向量表的 长度H为：丑，其中|Ρ| =Σ peP|p|是所有模式串的长度之和。3. 如权利要求1或2所述的模式串的数据存储结构，其特征在于，步骤4)中，对于给定 模式串集合P = {p?，p⑴，…，p(d丨，b、F的构造过程如下： 4-1)对每一个模式串Z1 = eP的每一个前缀M = MW/)... W1 eP，其 中O彡k〈r, 1彡j彡mk，利用递归哈希函数计算该前缀的哈希值h = Hash(u)，同时将位向 量B中第h位置为1 ; 4-2)对于每一个完整的模式串，除了在位向量B中标记其哈希值外，同时将其标记在 另一个位向量F中，即将F中对应的第h位亦置为1，得到位向量F，以此记录完整模式串的 信息。4. 如权利要求3所述的模式串的数据存储结构，其特征在于，步骤4)中校验散列表M 是一个数组，每个数组元素 M[t]为一个链表，具体构造过程如下： 4-3)对于模式串集合P= {p'p%···，？6^}中的每一个模式串p(k)，计算该模式串的 哈希值h : /? = ^/! + /，^)&(//-丨）：其中&是此1'1&11(1〇/^++编译器中伪随机数生成器的参数； 4-4)利用Rank技术，计算位向量F中第h比特位在F中的次序t，然后将该模式串存 入链表厘[1:]中，七=1^1111^(?，11)，]\1(1:)=1^。5. -种空间高效的多模式串匹配方法，其特征在于，包括如下步骤： 1) 读入关键词文件，对其进行预处理，即利用递归哈希函数和Rank操作构建过滤散列 表B、预匹配散列表F和校验散列表M，形成权利要求1~4中任一项所述的模式串的数据 存储结构； 2) 读入文本数据，利用递归哈希函数计算当前字符串的哈希值，并结合构建的模式串 的数据存储结构，对文本进行逐个字符搜索和校验，并报告最终搜索匹配的结果。6. 如权利要求5所述的方法，其特征在于，步骤2)具体包括如下步骤： 2-1)读入文本数据，从输入文本T的每个位置i开始搜索，对于文本位置i，i = 0,…， n-1，文本T的当前搜索窗口为1:山+1···!^+』，计算当前窗口的哈希值h = HashUitw…ti+j)， 查看位向量B中对应的第h个位置的值； 2-2)查找位向量B和F中相应的位置是否为1，以确定文本字符串titi+1··· ti+j是否可 能与某个模式串匹配；若为可能匹配，则进一步进行校验： 2-2-1)如果B[h] =0,表示不可能与某个模式串的前缀匹配，针对当前文 本位置i的扫描结束； 2-2-2)否则，文本字符串可能与某个模式串的前缀匹配，需要进一步确认 该前缀是否为一个完整匹配；查看位向量F中对应位置的值F[h]，若F[h] = 1，表示当前文 本字符串&&+1···?μ是一个可能的完整匹配结果，鉴于哈希冲突的存在，需要对其进行进 一步校验；利用Rank操作计算哈希值h在位向量F上的次序t，链表M[t]中的元素即为可 能命中的模式串，将文本字符串&& +1···、+」与可能命中的模式串一一比较，以发现真正的 匹配结果，校验过程结束； 2-2-3)设Imax为模式串集合中最长模式串的长度，若j〈lmax，则继续读入下一个字符， 执行上述步骤2-2-1)和2-2-2);若j彡Imax，则当前文本字符串?Α+1···?Μ不可能与模式 串匹配，针对当前文本位置i的扫描结束； 2-3)如果校验成功，则报告匹配结果；否则回到步骤1)，进行下一次读入、对比、校验。7. -种采用权利要求5所述方法的关键词匹配系统，其特征在于，包括： 关键词集合规范化装置，用于关键词文件即待匹配模式串集合的读入，将读入的文件 规范化为统一的形式； 关键词集合预处理装置，用于针对关键词规范化装置规范之后的关键词集合，构建对 应的过滤散列表B、预匹配散列表F和校验散列表M ; 文本搜索装置，用于根据文本数据计算所述过滤散列表B和预匹配散列表F的哈希值， 依该值判断是否为可能匹配，并依此计算校验散列表M的哈希值，进而对所述文本数据进 行校验；校验之后，报告匹配结果。
【专利摘要】本发明涉及一种空间高效的多模式串匹配方法和系统。首先提出了一种新的存储模式串的数据结构HashTrie，利用位向量表将原模式串矩阵存储为一维表的形式，避开传统方法存储自动机的状态转移矩阵问题；利用递归的哈希函数方法求出这个特殊的位向量表，以达到节约存储空间的目的；在哈希函数计算过程中，利用位运算技巧，将其转化为简单高效的位与运算操作；另外在HashTrie构造和关键词查找过程中均使用Rank技术，提高了搜索的空间效率和时间效率。本发明极大地降低了内存开销和预处理时间，更能满足实时入侵检测系统对规则生效的时效性要求，更适合于模式串集合规模较大、模式串长度较短的多模式串实时匹配问题。
【IPC分类】G06F17/30
【公开号】CN104881439
【申请号】CN201510236364
【发明人】张萍, 刘燕兵, 谭建龙, 郭莉
【申请人】中国科学院信息工程研究所
【公开日】2015年9月2日
【申请日】2015年5月11日