面向网络预警并行模式匹配方法与研究.pdf
郭三川
文章编号： 2095-2163（2018）03-0037-04中图分类号： 文献标志码： A
（国家计算机网络应急技术处理协调中心， 北京 100029）
摘要： 关键词： （CNCERT/CC， Beijing 100029， China）
Abstract： Precise string matching has been studied for many years. In recent years， the performance of mass pattern matching has drawn the attention of scholars. In this paper， a massive parallel pattern matching method based on fingerprint model is proposed. First， the pattern set is divided into subsets according to the length. Secondly， these subsets are merged using dynamic programming algorithm. Finally， the conflict rates of subsets are adjusted， and subsets are scheduled to many-core processors by greedy algorithm. Experiments show that compared with the existing mass pattern matching method and pattern set dividing method， the performance of the proposed method is better.
Key words：
基金项目：
作者简介：
收稿日期： 引言
精确字符串匹配，即给定一个模式集合P={P1，P2，…，Pn}， 其中，Pn为有限字母表∑上的字符串Pn={Pn1，Pn2，…，Pnl}，从输入文本T中，找出模式集合中的模式在文本中出现的所有位置。近年来，随着计算机和互联网的发展，越来越多的场合需要应用到精确字符串匹配，而随着数据量的增加，海量模式精确匹配的技术研究备受关注。基于这样的背景，本文的研究目标是对现有的海量模式精确匹配算法进行优化，提升匹配速度。
1相关工作
精确字符串匹配方法目前已进入应用广泛，发展也比较成熟的时期。最著名的算法是AC和WM算法。AC算法效率高，但是消耗内存大，适合短字符串的匹配；WM算法采用不良字符块的跳转机制加速匹配，基于哈希函数选择匹配阶段可能匹配的模式串，WM算法在长字符串匹配上表现出更好的性能，但是在海量模式集下，哈希的冲突率很大，导致匹配效率低下。AC与WM的比较结果可见表1。
针对WM的深入研究中，文献 1] 提出了一种基于共享位置的并行WM算法，对于同一内存内容，在多核处理器上，操作多个扫描窗口进行并行匹配。文献 2] 利用OpenCL架构在GPU上实现了WM算法的并行化，提高了匹配速度。随着多核性能的提升，WM算法的匹配效率也相应得到提高，但是上述方法并未能有效地解决海量模式的匹配效率低下问题，如入侵檢测系统中，背景流量较大时，海量模式的低效匹配会导致严重的丢包率，漏包严重。文献 3]提出了一种基于随机指纹模型的WM算法（RFP-WM），通过多项式对每个模式串计算出一个唯一指纹，与传统的WM算法相比，哈希函数的冲突率大大降低，而且模式集越大，效果越显著，性能越好。文献 4]根据模式串的长度对海量模式提供子集划分并通过多核实现并行化，通过理论证明了相同长度的字符串需要放到一个子集里，并利用动态规划算法进行子集的重新组合，对于多核的优化调度问题采用贪心算法解决。文献 5-6] 同样是通过划分子集的方法实现并行化。文献 7] 则是通过提升内存使用率来提高算法的性能。文献 8] 提出一种基于最大二部图匹配的最优窗口选择方法改善性能。
本文对前述研究进行组合优化，采用指纹模型替代哈希函数的WM算法，并对海量模式集以长度为衡量进行子集划分，通过动态规划方法重新组合，实际计算出合并后子集中每个模式冲突率最小的指纹，调节各子集的冲突率，最后，通过贪心算法调度到多核处理器中。
2基于指纹模型的海量模式并行匹配方法
2.1基于指纹模型的WM算法
本部分采用文献3]中的随机指纹模型，指纹定义如下。
定义1给定一个模式串P=P1，P2，…，Pl，∝∈θ， P的一个多项式指纹为φf，αP=∑lipifimod α， 其中， f∈Fα，1≤i≤l，且α为一个质数，Fα是整数与质数α取模后的域。
基于指纹模型的WM算法将指纹模型应用到WM算法中。传统WM算法对模式集开展预处理时需要建立3个表：Shift表、Hash表和Prefix表。滑动窗口选取最小模式长度，记为lmin。基于指纹模型的WM算法利用指纹替代哈希值，降低冲突率。该算法分为如下3步：
（1）参数f和α的选取。方法是通过已有模式集进行迭代训练得到最优值。
（2）计算每一个字符串的所有lmin窗口的指纹，找到每个字符串的唯一指纹，保证整个模式集的指纹集合冲突率最低，然后以指纹集合对应的窗口建立Shift表和Hash表。
（3）替换Prefix表为Fingerprint表。Fingerprint表存储冲突率最小的指纹集合，并且记录了对应窗口的起始位置，作为字符串的指纹索引。
2.2子集划分与组合
首先，将海量模式集以长度为衡量划分为若干子集，即P={P1，P2，…，Pn}。 其次，将这些子集进行组合优化，组合优化问题可描述为问题1。
问题1给定模式集合P和处理器核数c， 找到一个模式集分解P1，P2，…，Pl， 以及将所有子集调度到不同核中，找到一个最佳分解及调度，使得所有核中最大的运行时间最短，公式表述可见如下：minmaxci=1∑nij=1Tij（1）
s.t. Pi∩Pj= ∪li=1Pi=P1≤i≠j≤l其中，Pi为相同长度的模式集， ni表示核i中的模式集数量， 每个核的运行时间为∑nij=1Tij。
问题1是一个多目标组合优化的NP难问题，研究采用文献4] 的动态规划方法近似解决该问题。算法设计代码具体如下：
输入模式长度的集合L={l1，l2，…，lr}；
输出划分的位置
For i=r， r-1， …， 1 do
For j=1， …， r-i do
G[i]=min{G[i+j]+T（j，li）， T（r-i+1）， li}
positioni]=minj
Endfor
Endfor
For i=1，…，r do
dividei]=positionj]+1
j=position[j]
Endfor
算法中，Gi]表示第i次划分结果；Ta，b]表示模式集数量为a、最小长度为b的运行时间；position数组记录每次最优划分，divide数组记录最终的划分结果。
2.3子集到多核的调度
通过动态规划算法得到了较优的子集划分结果，为了进一步提高效率，降低冲突率，研究将适当调整各个子集的冲突率，使得整体冲突率均衡，保证运行时间的均匀。调整的方法为将冲突率高的字符串分配到冲突率相对低的子集中，并重新计算冲突率。调整时，考虑到lmin窗口问题，只能调整长度相邻的子集，并且是将长度偏长的子集调整到长度偏短的子集中。调整过程可如图1所示。
进一步优化后的子集需要调度到多核处理器中，本文采用贪心算法进行调度，数据结构采用最大堆。贪心算法的研发代码可详见如下。
输入每个子集的执行时间，TP1，…，TPl
输出每个核分配的子集，C1…k]，假设有k个核
if l≤k then
Ci]=i
Return
Endif
TP1，…，TPl降序排序
For每个key do
初始化堆
Endfor
For每个TPi do
堆中删除值最小的赋值给key
key+=TPi
Enqueue（Ckey]， i）
key插入堆
Endfor
3实验与分析
3.1实验环境
研究中，实验硬件为 Intel Core（TM） i7-6700HQ CPU 2.60 GHz， 4核， 每个核可以开启2个线程， 32 KB L1 每核独立数据缓存， 256 KB L2 每核独立缓存和 8 MB L3 核间共享缓存， 16 G 内存，运行系统为 Linux CentOS 7。
实验数据模式集共有106条模式串，来源包括3部分。一部分为从网上随机爬取的字符串（60 000条），一部分为从Snort规则集中提取的字符串（1 000条），最后一部分是随机生成的字符串（39 000条）。选择的所有模式串经过了如下预处理：
（1）统一采用UTF-8方式，保持编码一致性。
（2）去掉了重复的字符串。
模式集特征包括：112个不同字符，115个不同长度，最小长度为12，最大长度为149。相同长度的模式数量如图2所示。
测试输入数据文本包括3×106条字符串，由2部分组成。其中，106条为从模式集中随机抽取；2×106条为为随机生成。
3.2实验结果与分析
3.2.1算法比较实验
传统WM算法和基于指纹模型的WM算法的比较如图3所示。基于指纹模型的WM算法运行效率要明显高于传统WM算法，并且随着模式集合的增大，效果越显著。
3.2.2模式集划分及优化组合实验
模式集以长度为衡量划分后的子集运行时间如图4所示，运行时间与模式集大小和冲突率有关。模式集数量越大，运行时间越长；冲突率越大，运行时间越长。
经过动态规划算法优化后，再进行冲突率调整，需要调整的子集数为8个。本文用8个线程并行运行，选用了初始按长度划分+贪心调度、动态规划组合+贪心调度、动态规划组合+调整冲突率+贪心调度这3个方法展开对比。实验结果如图5所示。经过对图5的分析后可以表明，随着模式集数量增加，所有运行时间均呈现增长态势，优化后的算法运行时间相对更短，且模式集越大，效果越明显，增加冲突率调整的算法比原始动态规划方法略好。
4结束语
本文针对海量模式的精确字符串匹配效率低的问题，提出了一种基于指纹模型的海量模式并行匹配方法。研究中使用多项式计算出的指纹集合替代传统WM的Prefix表，降低了冲突率，而且又采用了多核并行的方案，并行化通过模式集的划分与优化组合获得了协同处理实现。首先，按照模式长度将原始模式集划分多个子集；其次，利用动态规划算法重新组合，得到效率表現更佳的子集集合，然后，通过调整冲突率，均衡每个子集的冲突率；至此，则用贪心算法将最终的子集调度到多核中运行。实验结果表明，本文的方法运行效率明显优于原始指纹模型随机调度并行方法，与未加冲突调整的动态规划方法相比，效率略有提升。
参考文献
[1] KHARBUTLI M， ALDWAIRI M， MUGHRABI A. Function and data parallelization of Wu-Manber pattern matching for intrusion detection system J]. Network Protocols and Algorithms， 2012， 4（3）： 46-61.
[2] PYRGIOTIS T K， KOUZINOPOULOS C S， MARGARITIS K G. Parallel implementation of the Wu-Manber algorithm using the openCL framework C]//Artificial Intelligence Applications and Innovations. AIAI 2012. IFIP Advances in Information and Communication Technology.Berlin/Heidelberg： Springer， 2012，382： 576-583.
[3] 张宏莉，徐东亮，梁敏，等. 海量模式高效匹配方法研究 J]. 电子学报， 2014， 42（6）：1220-1224.
[4] TAN Guangming， LIU Ping， BU Dongbo， et al. Revisiting multiple pattern matching algorithms for multi-core architecture J]. Journal of Computer Science and Techonology，2011， 26（5）： 866-874.
[5] LIU Jiahui， LI Fangzhou. SUN Guanglu. A parallel algorithm of multiple string matching based on set-partition in multi-core architecture J]. International Journal of Security and Its Applications， 2016，10（4）：267-278.
[6] JIANG Haiyang， XIE Gaogang. SALAMATIAN K. Load balancing by ruleset partition for parallel IDS on multi-core processorsC]//Proceedings of the 22th International Conference on Computer Communications and Networks. Nassau， Bahamas：IEEE，2013：1-7.
[7] VAKILI S， LANGLOIS J M P， BOUGHZALA B， et al. Memory-efficient string matching for instrusion detection systems using a highprecision pattern grouping algorithmC]//2016 ACM/IEEE Symposium on Architectures for Networking and Communications Systems （ANCS）. Santa Clara， CA：IEEE，2016： 37-42.
[8] 刘燕兵，邵妍，王勇，等. 一种面向大规模URL过滤的多模式串匹配算法J]. 计算机学报， 2014， 37（5）： 1159-1169.（上接第36页）
[2] 杨军， 李震宇， 孙光才， 等. 一种新的大斜视TOPS SAR全孔径成像方法J]. 西安电子科技大学学报， 2015， 42（1）： 42-48，55.
[3]崔亚奇，熊伟，何友. 基于目标指示的两坐标警戒雷达目标高度补偿状态估计J]. 电子学报，2015，43（3）： 475-482.
[4] 于超鹏，郝亮飞，谢金华. 线性调频和巴克码组合调制雷达信号J]. 探测与控制学报，2009，31（5）：20-24.
[5] 李巍， 齐巍， 丁赤飚，等. 基于分布式雷达的宽带脉冲三维测距机制及方法研究J]. 电子与信息学报， 2015，37（3）： 643-650.
[6] 王玉玺，黄国策，李伟，等. 基于非单调递增频率偏移的混合相控阵MIMO雷达目标跟踪方法J]. 电子与信息学报， 2017， 39（1）： 110-116.
[7] 黄中瑞， 郑志东， 张剑云. 目标角度估计的多输入多输出雷达发射方向图综合J]. 电波科学学报， 2015， 30（4）： 789-796.
[8] KHABBAZIBASMENJ A， HASSANIEN A， VOROBYOV S A， et al. Efficient transmit beamspace design for search-free based DOA estimation in MIMO radarJ]. IEEE Transactions on Signal Processing， 2014， 62（6）： 1490-1500.
[9] SAMMARTINO P F， BAKER C J， GRIFFITHS H D. Frequency diverse MIMO techniques for radarJ]. IEEE Transactions on Aerospace and Electronic Systems， 2013， 49（1）： 201-222.
[10]WANG Wenqin， SHAO Huaizong. Range-angle localization of targets by a double-pulse frequency diverse array radarJ]. IEEE Journal of Selected Topics in Signal Processing， 2014， 8（1）： 106-114.
[11]WANG Wenqin， SO H C. Transmit subaperturing for range and angle estimation in frequency diverse array radarJ]. IEEE Transactions on Signal Processing， 2014， 62（8）： 2000-2011.
[12]陳春晖， 张群， 罗迎， 等. 一种步进频率信号认知雷达波形优化设计方法J]. 航空学报， 2016， 37（7）： 2276-2285.
