深度包检测技术中多模式匹配算法研究
开篇：润墨网以专业的文秘视角，为您筛选了一篇深度包检测技术中多模式匹配算法研究范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：网络数据流量的急速增长给深度包检测技术带来了新的挑战，作为深度包检测技术的重要基础，字符串匹配算法针对大模式集合的优化结果直接决定了深度包检测技术的性能优劣。对广泛应用的多模式串匹配AC算法进行了改进，通过引入平衡二叉树结构消除AC自动机中的无用状态节点，在保证算法速度的前提下解决其在大规模模式集合匹配过程中内存占用过大的问题，经过实验验证，在模式集规模达100 000时，改进的AVLAC算法内存占用为传统AC算法的5%左右。
关键词：深度包检测； 字符串匹配； AC算法； AVLAC算法
0引言
随着互联网的迅速发展以及计算机硬件水平的不断提高，网络数据流量呈现出爆炸式的增长，数据特点从曾经的静态、少量和小范围转变为实时、高速和大规模[1]。作为网络安全的重要分支，信息内容安全一直是学术界的热点和重点，而对于深度包检测技术，因其作为一种已获广泛应用的内容安全监管和过滤的技术手段，深入研究其在大数据流量环境下的优化方法具有重要意义。
深度包检测技术，即DPI技术是一种基于应用层的流量检测和控制技术，当IP数据包、TCP或UDP数据流通过基于DPI技术的管理系统时，该系统通过深入读取IP包载荷的内容而对OSI七层协议中的应用层信息进行重组，由此得到整个应用程序的内容，再按照系统定义的管理策略对流量进行操作[2]。深度包检测的技术从功能上可以划分为协议还原、模式匹配和数据包操作3个层次，其中，模式匹配阶段根据预先定义的特征模式集合对协议还原层提交上来的数据进行匹配并将匹配结果递交上层进行相应操作，一个性能良好的串匹配算法会大大提高系统效率。本文主要研究多模式串匹配算法在大规模模式集合情形下的优化。
1研究现状
根据匹配方式的不同，Navarro[3]等人将多模式匹配算法大致分为3类：基于前缀搜索的匹配算法，基于后缀搜索的匹配算法以及基于子串搜索的匹配算法，下面对各类典型的算法进行介绍。
（1）基于前缀搜索的AC自动机算法[4]
AC算法是经典的自动机算法，于1975年产生于贝尔实验室，其特点是基于前缀搜索，并且是目前应用最为广泛的多模式匹配算法之一。该算法应用有限自动机巧妙地将字符比较转化为状态转移。其基本思想分为两步。在预处理阶段，AC自动机算法建立了三个函数，[JP2]也就是状态跳转goto函数、失效fail函数和输出output函数，并由此构造了一个树型有限自动机。在搜索查找阶段，则通过上述三个函数的交叉使用扫描文本，定位得到关键字在文本中的所有出现位置。[JP]
AC算法的关键是构造树型有限自动机，树型有限自动机包含一组状态，每个状态用一个数字代表。算法进行匹配的时候，状态机读入文本串中的字符，然后通过产生状态转移或者偶尔发送输出的方式来处理文本。其行为则可通过预处理阶段建立的三个函数进行标明和指示。
（2）基于后缀搜索的Wu-Manber跳跃扫描算法[5]
Wu-Manber算法是基于后缀的跳跃扫描算法，又简称为WM算法，算法通过坏字符跳转机制，采用字符块技术，增大了待匹配文本和模式不匹配的可能性，从而增加了直接跳跃的机会。使用散列表选择模式集合中的一个子集与当前文本进行完全匹配，并使用前缀表进一步过滤不匹配的模式，使算法获得了较高的运行效率。
WM算法和AC算法一样，在匹配之前也需要对给定的模式集合进行预处理，首先需要知道模式集合中最短的字符串长度，然后根据这一信息建立后缀哈希hash表、跳转shift表以及前缀prefix表，这三个表将在匹配过程中提供算法所需要的各种信息：hash表确定扫描窗口内后缀的跳转距离，通过shift表指向所有具有相同后缀哈希值的模式链表以及具有相同后缀哈希值的模式前缀链表，prefix表则存储了模式的前缀哈希值。
WM算法进行模式匹配时，通过hash表、shift表与prefix表，并连同已知的字符串最短长度m建立滑动窗口，在滑动窗口内，从后往前寻找最长好后缀，并在遇到坏字符时根据相应规则进行跳跃。试用一例说明，如果在hash表中没有找到后缀字符块B相应的hash值，那么算法将会直接跳转m-B+1个字符。WM算法通过巧妙的跳跃规则能够缩短大部分情况下的模式匹配时间，但在特殊情况下，诸如m较小时算法效率不高。
（3）基于子串搜索的SBOM算法[6]
SBOM算法使用了Factor Oracle的数据结构进行扫描，根据这种数据结构建立的自动机可以识别模式集合P的超集，利用Factor Oracle自动机，从后向前地扫描长度为lmin的文本窗口。如此就会出现两种情况：[JP2]如果无法识别文本字符x，则可以将窗口直接移动到字符x的后面。如果无法识别当前窗口内的所有字符，就回到窗口起始位置，再将整个字符串和P的一个子集进行比较验证，判别是否发生了匹配。