【一种针对大规模URL关键字的多模匹配算法】多模匹配算法 arm平台
时间：2020-03-11 07:17:29 来源：雅意学习网 本文已影响 人 
摘要： 针对网络信息安全中大规模ＵＲＬ关键字匹配过程中自动机内存占用过大问题，提出一种基于分类思想的多模匹配算法，将ＵＲＬ关键字按照模式长度和匹配要求进行分类，分别使用Ｗｕ－Ｍａｍｂｅｒ算法和自动机类多模匹配增效算法ＧＦＡＭ进行匹配。实验结果表明，经过分类后，大规模配置（＞１０ｗ）情况下，算法能够将占用内存降低为只使用ＧＦＡＭ算法的内存的５％以内。
关键词：
中图分类号： ＴＰ３０１．６ 文献标识码：Ａ 文章编号：２０９５－２１６３（２０１１）０１－００２０－０４
０引言
字符串匹配问题是计算机科学中的一个经典研究领域。信息安全领域中，ＵＲＬ关键字匹配是入侵检测系统、防火墙系统、反钓鱼防御系统等的最基础也是最核心的部分。然而随着ＵＲＬ域名数量的不断增长，网络安全威胁不断升级，尤其是数据规模惊人增长的情况下，大规模ＵＲＬ关键字多模匹配算法的性能已经成为系统的瓶颈，同时针对ＵＲＬ关键字的匹配不再是简单的精确匹配，还包含了如“与”表达式匹配、模糊匹配等多种匹配需求。传统的字符串匹配算法已经不能适用于大规模ＵＲＬ关键字的匹配，可以说提高大规模ＵＲＬ关键字匹配的效率，降低ＵＲＬ关键字匹配部分的系统开销，提高算法的适应性和健壮性将对消除系统瓶颈起到至关重要的作用。
１研究现状
从多模匹配算法的特点来说，可以将多模匹配算法分为基于前缀搜索的匹配算法、基于后缀搜索的匹配算法、基于子串搜索的匹配算法、基于位并行的匹配算法以及基于硬件的匹配算法。目前在字符串匹配领域的研究工作主要集中在对经典算法的改进上，由于基于位并行的匹配算法和基于硬件的匹配算法不适用于大规模ＵＲＬ关键字匹配，以下主要介绍其他三类中最具代表性的算法。
（１）基于前缀搜索的ＡＣ[１]算法。ＡＣ算法是经典的多模匹配算法，至今大部分的多模匹配算法都是针对ＡＣ算法进行改进。ＡＣ算法对所有关键字建立有限自动机，利用该自动机对输入文本进行扫描。自动机建立过程建立三个函数：状态跳转函数ｇｏｔｏ，输出函数ｏｕｔｐｕｔ，失效函数ｆａｉｌｕｒｅ。
匹配过程是从零状态出发，每次扫描文本中的一个字符，在当前状态情况下，查看扫描到的字符，利用ｇｏｔｏ函数、ｆａｉｌｕｒｅ函数跳转到下一个状态。如果跳转到的状态的ｏｕｔｐｕｔ函数不为空，表示命中了某个关键字，输出该关键字。
（２）基于后缀搜索的Ｗｕ－Ｍａｍｂｅｒ算法[２]。Ｗｕ－Ｍａｍｂｅｒ算法基于单模匹配中ＢＭ[３]算法的坏字符跳转思想，维护一个固定长度的扫描窗口，能够实现对文本的跳跃式扫描。算法初始化阶段首先确定所有规则的最短长度ｍ，并建立三个表，分别是跳转表Ｓｈｉｆｔ、后缀哈希表Ｈａｓｈ、前缀表Ｐｒｅｆｉｘ。通过Ｓｈｉｆｔ表确定扫描窗口内后缀的跳转距离；Ｈａｓｈ表存储的是指针，指针指向具有相同后缀哈希值的所有模式串组成的链表，同时指向具有相同后缀哈希值的模式串的前缀链表；Ｐｒｅｆｉｘ表存储了模式串的前缀哈希值，以提高匹配速度。
（３）基于子串搜索的ＳＢＯＭ算法[４]。ＳＢＯＭ算法采用一种称为Ｆａｃｔｏｒ Ｏｒａｃｌｅ[５]自动机的数据结构，可以识别模式串集合的超集，利用自动机，在长度为ｌｍｉｎ的文本窗口内，从后向前逐个识别字符。
ＡＣ算法具有与关键字特征无关，匹配速度稳定的优势，但内存消耗高，初始化时间长。ＳＢＯＭ算法的匹配速度快，但效率不够稳定，并且对最短串长度敏感，内存和预处理时间与ＡＣ基本相同。Ｗｕ－Ｍａｍｂｅｒ算法的预处理时间短，内存消耗少，且模式串规模越大，预处理时间和内存优势越明显，但匹配速度不稳定，对最短串长度敏感。
ＡＣ算法以其匹配效率稳定，适应性强的优势成为目前大多数信息安全系统的首选算法，如ＳＮＯＲＴ系统使用的基于ＡＣ的改进算法ＡＣ＿ＢＭ。但随着ＵＲＬ关键字规模的持续高速增长，ＡＣ算法内存消耗过高，自动机启动时间过长的问题逐渐突显，已经成为系统瓶颈，必须进行优化。
２基于分类思想的多模匹配算法ＰＭＵＣ
２．１大规模ＵＲＬ关键字的特征
针对目前一般的信息安全系统普遍使用的特征库中ＵＲＬ配置（不少于１０万条）的统计，ＵＲＬ关键字长度分布在４～２５６之间，平均长度为４０个字节左右。长度在４～１０的关键字较少，而长度在１１～５０之间的关键字占到接近所有关键字的８５％左右。另外由于ＵＲＬ配置由数据库进行维护，数据库对ＵＲＬ关键字长度有一定的限制，因此存在“与”表达式匹配的需求，即将较长的ＵＲＬ关键字分割成多个小关键字，对每个小关键字添加一个“＆”属性，借此表示该关键字具有“与”表达式匹配需求，而只有当所有“与”表达式关键字均命中，才能报告整体关键字的命中。从对配置文件的统计结果来看，“与”表达式最多被“＆”分割成４段，具有“与”表达式匹配要求的关键字较少，只占到总规则条数的１．２５％左右。
２．２ＰＭＵＣ算法的理论基础
２．２．１Ｗｕ－Ｍａｍｂｅｒ算法的思想
假设模式串集合Ｐ中最短的模式长度为ｍ，Ｗｕ－Ｍａｍｂｅｒ算法在后面仅考虑所有模式的前ｍ个字符组成的模式串。预处理阶段将建立三个表格：
（１）移动表（Ｓｈｉｆｔ表）：该表用来决定扫描文本的过程中，可以跳过多少个字符。存在两种情况。其中，ｘ为ＵＲＬ关键字字符串，ｉ为每Ｂ个字符映射成的哈希值。
① Ｘ和任何模式中的子串都不匹配，这种情况下，可以移动文本的ｍ－Ｂ＋１个字符。记录移动表ＳＨＩＦＴ[ｉ]的值为ｍ－Ｂ＋１。
② Ｘ出现在一些模式中，找出Ｘ在所有模式中的最右出现。假设Ｘ在模式Ｐｊ的位置ｑ处结束，并且Ｘ并不结束在任何其他模式中比ｑ大的位置，记录ＳＨＩＦＴ[ｉ]的值为ｍ－ｑ。
（２）哈希表（Ｈａｓｈ表）：指向后缀ｈａｓｈ值相同的模式链表和前缀表。表项与ｓｈｉｆｔ表有相同的哈希值。
（３）前缀表（Ｐｒｅｆｉｘ表）：存放字符串的前缀哈希值，提高匹配效率。
例如，假设模式集合为?邀ｆｒｏｍ， ｆｒｏｎｔ， ｂｏｏｍｅｄ?妖，最短串的长度是４，设字符块大小Ｂ为２。为该模式集合建立的Ｓｈｉｆｔ表如表１所示。
Ｗｕ－Ｍａｍｂｅｒ算法的匹配过程：
（１）计算所有模式中最短串的长度；
（２）扫描模式集合，建立三个表；
（３）如果Ｓｈｉｆｔ表对应表项的值不为０，按照ｓｈｉｆｔ值向后移动窗口，继续执行步骤（３），为零时转步骤（４）；
（４）查找Ｈａｓｈ表，找出ｓｈｉｆｔ值为零的Ｂ个字符在模式集合中出现的位置以及每个位置上的模式，执行步骤（５）；全部扫描结束，转步骤（３）继续扫描剩余文本；
（５）查找该模式的前缀表项，与当前窗口中的文本前缀值比较，相等则逐个比较，如果全部匹配，报告一个成功匹配，否则转下一个位置，继续执行步骤（５）。
２．２．２ＧＦＡＭ算法的思想
ＣＦＡＭ 算法[６]是对ＡＣ算法的改进，采用字频映射技术分类压缩列，采用位图检索技术[７]提高检索效率。在匹配过程中，根据映射规则转换输入字符，高频字符在保留列中查找跳转状态；低频字符利用位图信息获得跳转状态。根据输入字符ｃ 计算转移状态的伪码如下：
ｉｆ Ｆ（ｃ） ＝＝ ０
ｒｅｔｕｒｎ ０；
ｅｌｓｅ ｉｆ Ｆ（ｃ） ＞ ０
ｒｅｔｕｒｎ ｔｈｅ ｄａｔａ ｉｎ ｕｎｃｏｍｐｒｅｓｓｅｄ ａｒｒａｙ （Ｆ（ｃ）， ｃ）；
ｅｌｓｅ
ｉｆ ＣＨＥＣＫ＿ＢＩＴ（ｃ， ｐｂｉｔｍａｐ） ＝＝ ０
ｒｅｔｕｒｎ ０；
ｅｌｓｅ
ｒｅｔｕｒｎ ｔｈｅ ｄａｔａ ｉｎ ｃｏｍｐｒｅｓｓｅｄ ａｒｒａｙ ｗｉｔｈ ｉｎｄｅｘ ｃｏｍｐｕｔｅｄ ｂｙ ｂｉｔｍａｐ；
２．３ＰＭＵＣ算法
２．３．１基本思想
从对大规模（不低于１０万条配置）ＵＲＬ关键字的统计结果来看，长度较长的关键字占多数，较为适合Ｗｕ－Ｍａｍｂｅｒ算法，而通过长度过滤后，其余短关键字适合自动机类算法。算法专门针对大规模ＵＲＬ关键字匹配进行性能优化，命名为ＰＭＵＣ算法（Ｍｕｌｔｉ－ｐａｔｔｅｒｎ Ｍａｔｃｈｉｎｇ Ａｌｇｏｒｉｔｈｍ ｆｏｒ ＵＲＬ ｂａｓｅｄ ｏｎ Ｃｌａｓｓｉｆｉｃａｔｉｏｎ）。
ＰＭＵＣ算法利用Ｗｕ－Ｍａｍｂｅｒ算法来匹配长度较长的ＵＲＬ关键字，长度范围在１０以上的关键字占总关键字条数的９０％以上，并且命中率较低，实际匹配过程中命中率在１０％以下，这部分关键字非常适用于Ｗｕ－Ｍａｍｂｅｒ类算法，产生较大跳跃距离的同时，大大节省了内存空间。
ＰＭＵＣ算法同时采用了基于字频特征和位图压缩ＧＦＡＭ，该算法对ＡＣ算法进行了改进。长度较短的关键字以及具有“与”表达式匹配需求的关键字使用ＧＦＡＭ算法进行匹配，经过Ｗｕ－Ｍａｍｂｅｒ算法对长关键字以及具有“与”表达式需求的关键字进行过滤后，利用ＧＦＡＭ算法进行匹配的关键字只占很小一部分，且相比于ＡＣ算法来说，ＧＦＡＭ算法能够进一步压缩自动机占用的内存。
ＰＭＵＣ算法结合这两个改进算法，将ＵＲＬ关键字按照关键字特征进行分类匹配，在保证匹配效率的基础上，达到了明显的内存优化效果。实验表明，ＰＭＵＣ算法占用的内存可压缩为原只使用ＡＣ算法的５％以下，并且关键字规模越大，优化效果越明显。同时初始化时间有了明显降低，这对于经常进行配置更新的信息安全系统来说，将明显提高系统的启动速度。图３所示的伪代码表明了ＰＭＵＣ算法的初始化与匹配过程。其中Ｓ表示分类条件。
２．３．２算法匹配条件
目前，ＵＲＬ关键字匹配规模在１０ｗ条以上，且未来规模将越来越大。每条关键字的长度一般在４～１ ０２４之间变化，其中长度大于１０的关键字占总关键字比例的９０％以上。另外在入侵检测中，存在一种称为“与”表达式匹配的匹配规则，只有当规则中的所有模式都匹配到的情况才宣告匹配成功。
根据以上ＵＲＬ关键字匹配特点，将关键字按照如下条件分类。其中，关键字的长度用Ｌ表示，临界长度用ｍ表示，为关键字添加属性ｂｄｓ，关键字的ｂｄｓ＝１时，说明该关键字是一条“与”表达式规则的关键字。
Ｗｕ－Ｍａｍｂｅｒ算法的匹配条件：
ｐａｔｔｅｒｎ．Ｌ＞＝ｍ＆＆ｐａｔｔｅｒｎ．ｂｄｓ＝０；
ＧＦＡＭ算法的匹配条件：
ｐａｔｔｅｒｎ．Ｌ＜ｍ｜｜ｐａｔｔｅｒｎ．ｂｄｓ＝１。
２．３．３参数对算法性能的影响
ｍ：Ｗｕ－Ｍａｍｂｅｒ算法对所有模式的最短串长度敏感，因此使用Ｗｕ－Ｍａｍｂｅｒ算法进行匹配的模式的最短长度不能太短，ｍ表示所有模式的最短串长度。文献[２]给出了Ｗｕ－Ｍａｍｂｅｒ算法的时间复杂度为Ｏ（ＢＮ/ｍ），在模式较为随机的情况下，ｍ越大，跳跃距离越大，匹配速度越快。但对于ＰＭＵＣ算法来说，ｍ增大也就意味着模式中使用ＧＦＡＭ算法进行匹配的模式增多，因此将导致内存的增大。
Ｄ：ＧＦＡＭ算法在自动机的前Ｄ层仍然用二维数组来记录跳转状态，且层数越低，出度越大，保证了高频字符的查找速度。而层数大于Ｄ后，跳转状态使用链表来实现，由于此时Ｄ层后的字符出现频率较低，出度较小，因此在尽可能保证查找速度的条件下，压缩了内存空间。由于所有关键字中长度大于ｍ的关键字已经使用Ｗｕ－Ｍａｍｂｅｒ进行匹配，因此，Ｄ的设置应当小于ｍ。一般来说，Ｄ越小，越节省内存，但匹配速度有所下降。
３实验结果与分析
３．１测试环境与数据
实验的测试环境为８核ＣＰＵ，主频为２．６Ｈｚ，操作系统采用ＧｒｅａｔＴｕｒｂｏ ＥｎｔｅｒｐｒｉｓｅＳｅｒｖｅｒ１０，内存总量为１６ＧＢ。文本集采用离线网络数据包，分别包含１００万条ｈｔｔｐ包、２００万条、３００万条、４００万条。关键字采用真实ＵＲＬ中提取的部分连续字符串作为测试集合。
３．２实验结果与分析
首先测试调整参与“与”匹配时间的关系，分别选取含有１００ｗ、２００ｗ、３００ｗ，４００ｗ包的ｃａｐ包，使用ＧＦＡＭ算法和ＰＭＵＣ进行匹配，记录精确到ｕｓ的匹配时间。测试匹配时间时，选用１４万条的配置规模，实验结果如图４所示。
图４中，横坐标表示ｍ和Ｄ的不同值组合。其中，ｍ初始值设置为１１，Ｄ设置为８，ｍ初始测试值根据对规则长度的统计结果进行设置。可以看出，整体的匹配时间是呈现下降趋势的，小范围内有波动。最左侧的时间也比较短， 而在 右侧的曲线内，ｍ＝８，Ｄ＝６的点以及ｍ＝７，Ｄ＝４的点匹配时间较短。如果考虑内存因素，那么必然是选择ｍ＝７，Ｄ＝４比较好。
图５说明了调整参数ｍ和Ｄ对内存的影响。从内存占用情况来看，Ｄ值相同的情况下，ｍ＞＝９时，ｍ每减小１，内存减小１Ｍｂ左右；而当ｍ＜９时，ｍ值的减小对内存占用基本没有影响。但是在固定ｍ的情况下，Ｄ每减小１，内存相应减小约１０Ｍｂ，因此，在选定ｍ的情况下，如果匹配时间没有明显的变短，那么Ｄ可以尽可能减小，以节省内存。
图６给出了两者内存对比情况，结果表明与ＧＦＡＭ相比，ＰＭＵＣ的内存占用明显较低，此时选取的参数是Ｄ＝４，ｍ＝７，则ＰＭＵＣ将获得更好的内存性能。
图７表明，模式规模越大，ＰＭＵＣ的内存优化的效果越明显。
４结束语
本文针对信息安全领域中ＵＲＬ配置量不断加大，内存消耗巨大，造成系统产生瓶颈的问题，提出使用分类思想的多模匹配算法ＰＭＵＣ，通过调整分类参数使得ＰＭＵＣ算法达到速度与内存的最佳结合点，从而在匹配速度可接受的情况下，大幅降低自动机匹配部分的消耗。实验表明，ＰＭＵＣ算法占用的内存，可降低为原只使用ＧＦＡＭ算法时的５％以下，这为今后系统的高效稳定运行提供了有力的保证，并为未来应用于不断增长的数据留下了更大的空间，使得系统的可扩展性提升。同时，针对特定匹配，选择合适的算法进行分类匹配的思想，也为研究高效的串匹配算法提供了开阔思路。
参考文献：
[１] ＡＨＯ Ａ Ｖ，ＣＯＲＡＳＩＣＫ Ｍ Ｊ． Ｅｆｆｉｃｉｅｎｔ ｓｔｒｉｎｇ ｍａｔｃｈｉｎｇ：ａｎ ａｉｄｔｏ ｂｉｏｌｏｇｉｇｒａｐｈｉｃ ｓｅａｒｃｈ． Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｏｆ ｔｈｅ ＡＣＭ，１９７５，１８ （６）：３３３－３４０．
[２] ＷＵ Ｓ，ＭＡＮＢＥＲ Ｕ． Ａ ｆａｓｔ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｍｕｌｔｉ－ｐａｔｔｅｒｎ ｓｅａｒｃｈ－ ｉｎｇ． Ｒｅｐｏｒｔ ＴＲ－９４－１７，Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，Ｕｎｉｖ－ ｅｒｓｉｔｙ ｏｆ Ａｒｉｚｏｎａ，Ｔｕｃｓｏｎ，ＡＺ，１９９４．
[３] ＢＯＹＥＲ Ｒ Ｓ，ＭＯＯＲＥ Ｊ Ｓ． Ａ Ｆａｓｔ Ｓｔｒｉｎｇ Ｓｅａｒｃｈｉｎｇ Ａｌｇｏｒｉｔｈｍ [Ｊ]． Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｏｆ ｔｈｅ ＡＣＭ，１９７７，１０（１０）：７６２－７７２．
[４] ＣＲＯＣＨＥＭＯＲＥ Ｃ Ａ Ｍ，ＲＡＦＦＩＮＯＴ Ｍ． Ｆａｃｔｏｒ Ｏｒａｃｌｅ： Ａ Ｎｅｗ Ｓｔｒｕｃｔｕｒｅ ｆｏｒ Ｐａｔｔｅｒｎ Ｍａｔｃｈｉｎｇ[Ｒ]． Ｉｎｓｔｉｔｕｔｅ Ｇａｓｐａｒｄ－Ｍｏｎｇｅ， Ｕ－ ｎｉｖｅｒｓｉｔｅ ｄｅ Ｍａｒｎｅ－ｌａ－Ｖａｌｌｅｅ，１９９９．
[５] ＡＬＬＡＵＺＥＮ Ｃ，ＲＡＦＦＩＮＯＴ Ｍ． Ｆａｃｔｏｒ Ｏｒａｃｌｅ ｏｆ ａ Ｓｅｔ ｏｆ Ｗｏｒ－ ｄｓ[Ｒ]． Ｔｅｃｈｎｉｃａｌ Ｒｅｐｏｒｔ ９９－１１，Ｉｎｓｔｉｔｕｔｅ Ｇａｓｐａｒｄ－Ｍｏｎｇｅ，Ｕｎｉｖ－ ｅｒｓｉｔｅ ｄｅ Ｍａｒｎｅ－ｌａ－Ｖａｌｌｅｅ，１９９９．
[６] 李超，张宏莉，楚国锋． 基于字频特征的自动机多模匹配增效 算法[Ｊ]． 微计算机信息，２００９，２９（３）：２０６－２０８．
[７] 张元竞，张伟哲． 一种基于位图的多模匹配算法[Ｊ]． 哈尔滨工 业大学学报，２００８，３６（６）：１１０－１１４．
推荐访问:匹配 算法 多模 一种针对大规模URL关键字的多模匹配算法 多模匹配算法 多模匹配算法ppt下载
