基于指紋模型的海量模式并行匹配方法研究

郭三川

文章編號： 2095-2163（2018）03-0037-04中圖分類號： 文獻(xiàn)標(biāo)志碼： A

（國家計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)急技術(shù)處理協(xié)調(diào)中心， 北京 100029）

摘要： 關(guān)鍵詞： （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：

基金項(xiàng)目：

作者簡介：

收稿日期： 引言

精確字符串匹配，即給定一個(gè)模式集合P={P1，P2，…，Pn}， 其中，Pn為有限字母表∑上的字符串Pn={Pn1，Pn2，…，Pnl}，從輸入文本T中，找出模式集合中的模式在文本中出現(xiàn)的所有位置。近年來，隨著計(jì)算機(jī)和互聯(lián)網(wǎng)的發(fā)展，越來越多的場合需要應(yīng)用到精確字符串匹配，而隨著數(shù)據(jù)量的增加，海量模式精確匹配的技術(shù)研究備受關(guān)注。基于這樣的背景，本文的研究目標(biāo)是對現(xiàn)有的海量模式精確匹配算法進(jìn)行優(yōu)化，提升匹配速度。

1相關(guān)工作

精確字符串匹配方法目前已進(jìn)入應(yīng)用廣泛，發(fā)展也比較成熟的時(shí)期。最著名的算法是AC和WM算法。AC算法效率高，但是消耗內(nèi)存大，適合短字符串的匹配；WM算法采用不良字符塊的跳轉(zhuǎn)機(jī)制加速匹配，基于哈希函數(shù)選擇匹配階段可能匹配的模式串，WM算法在長字符串匹配上表現(xiàn)出更好的性能，但是在海量模式集下，哈希的沖突率很大，導(dǎo)致匹配效率低下。AC與WM的比較結(jié)果可見表1。

針對WM的深入研究中，文獻(xiàn) 1] 提出了一種基于共享位置的并行WM算法，對于同一內(nèi)存內(nèi)容，在多核處理器上，操作多個(gè)掃描窗口進(jìn)行并行匹配。文獻(xiàn) 2] 利用OpenCL架構(gòu)在GPU上實(shí)現(xiàn)了WM算法的并行化，提高了匹配速度。隨著多核性能的提升，WM算法的匹配效率也相應(yīng)得到提高，但是上述方法并未能有效地解決海量模式的匹配效率低下問題，如入侵檢測系統(tǒng)中，背景流量較大時(shí)，海量模式的低效匹配會導(dǎo)致嚴(yán)重的丟包率，漏包嚴(yán)重。文獻(xiàn) 3]提出了一種基于隨機(jī)指紋模型的WM算法（RFP-WM），通過多項(xiàng)式對每個(gè)模式串計(jì)算出一個(gè)唯一指紋，與傳統(tǒng)的WM算法相比，哈希函數(shù)的沖突率大大降低，而且模式集越大，效果越顯著，性能越好。文獻(xiàn) 4]根據(jù)模式串的長度對海量模式提供子集劃分并通過多核實(shí)現(xiàn)并行化，通過理論證明了相同長度的字符串需要放到一個(gè)子集里，并利用動態(tài)規(guī)劃算法進(jìn)行子集的重新組合，對于多核的優(yōu)化調(diào)度問題采用貪心算法解決。文獻(xiàn) 5-6] 同樣是通過劃分子集的方法實(shí)現(xiàn)并行化。文獻(xiàn) 7] 則是通過提升內(nèi)存使用率來提高算法的性能。文獻(xiàn) 8] 提出一種基于最大二部圖匹配的最優(yōu)窗口選擇方法改善性能。

本文對前述研究進(jìn)行組合優(yōu)化，采用指紋模型替代哈希函數(shù)的WM算法，并對海量模式集以長度為衡量進(jìn)行子集劃分，通過動態(tài)規(guī)劃方法重新組合，實(shí)際計(jì)算出合并后子集中每個(gè)模式?jīng)_突率最小的指紋，調(diào)節(jié)各子集的沖突率，最后，通過貪心算法調(diào)度到多核處理器中。

2基于指紋模型的海量模式并行匹配方法

2.1基于指紋模型的WM算法

本部分采用文獻(xiàn)3]中的隨機(jī)指紋模型，指紋定義如下。

定義1給定一個(gè)模式串P=P1，P2，…，Pl，∝∈θ， P的一個(gè)多項(xiàng)式指紋為φf，αP=∑lipifimod α， 其中， f∈Fα，1≤i≤l，且α為一個(gè)質(zhì)數(shù)，F(xiàn)α是整數(shù)與質(zhì)數(shù)α取模后的域。

基于指紋模型的WM算法將指紋模型應(yīng)用到WM算法中。傳統(tǒng)WM算法對模式集開展預(yù)處理時(shí)需要建立3個(gè)表：Shift表、Hash表和Prefix表。滑動窗口選取最小模式長度，記為lmin。基于指紋模型的WM算法利用指紋替代哈希值，降低沖突率。該算法分為如下3步：

（1）參數(shù)f和α的選取。方法是通過已有模式集進(jìn)行迭代訓(xùn)練得到最優(yōu)值。

（2）計(jì)算每一個(gè)字符串的所有l(wèi)min窗口的指紋，找到每個(gè)字符串的唯一指紋，保證整個(gè)模式集的指紋集合沖突率最低，然后以指紋集合對應(yīng)的窗口建立Shift表和Hash表。

（3）替換Prefix表為Fingerprint表。Fingerprint表存儲沖突率最小的指紋集合，并且記錄了對應(yīng)窗口的起始位置，作為字符串的指紋索引。

2.2子集劃分與組合

首先，將海量模式集以長度為衡量劃分為若干子集，即P={P1，P2，…，Pn}。 其次，將這些子集進(jìn)行組合優(yōu)化，組合優(yōu)化問題可描述為問題1。

問題1給定模式集合P和處理器核數(shù)c， 找到一個(gè)模式集分解P1，P2，…，Pl， 以及將所有子集調(diào)度到不同核中，找到一個(gè)最佳分解及調(diào)度，使得所有核中最大的運(yùn)行時(shí)間最短，公式表述可見如下：minmaxci=1∑nij=1Tij（1）

s.t. Pi∩Pj= ∪li=1Pi=P1≤i≠j≤l其中，Pi為相同長度的模式集， ni表示核i中的模式集數(shù)量， 每個(gè)核的運(yùn)行時(shí)間為∑nij=1Tij。

問題1是一個(gè)多目標(biāo)組合優(yōu)化的NP難問題，研究采用文獻(xiàn)4] 的動態(tài)規(guī)劃方法近似解決該問題。算法設(shè)計(jì)代碼具體如下：

輸入模式長度的集合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次劃分結(jié)果；Ta，b]表示模式集數(shù)量為a、最小長度為b的運(yùn)行時(shí)間；position數(shù)組記錄每次最優(yōu)劃分，divide數(shù)組記錄最終的劃分結(jié)果。

2.3子集到多核的調(diào)度

通過動態(tài)規(guī)劃算法得到了較優(yōu)的子集劃分結(jié)果，為了進(jìn)一步提高效率，降低沖突率，研究將適當(dāng)調(diào)整各個(gè)子集的沖突率，使得整體沖突率均衡，保證運(yùn)行時(shí)間的均勻。調(diào)整的方法為將沖突率高的字符串分配到?jīng)_突率相對低的子集中，并重新計(jì)算沖突率。調(diào)整時(shí)，考慮到lmin窗口問題，只能調(diào)整長度相鄰的子集，并且是將長度偏長的子集調(diào)整到長度偏短的子集中。調(diào)整過程可如圖1所示。

進(jìn)一步優(yōu)化后的子集需要調(diào)度到多核處理器中，本文采用貪心算法進(jìn)行調(diào)度，數(shù)據(jù)結(jié)構(gòu)采用最大堆。貪心算法的研發(fā)代碼可詳見如下。

輸入每個(gè)子集的執(zhí)行時(shí)間，TP1，…，TPl

輸出每個(gè)核分配的子集，C1…k]，假設(shè)有k個(gè)核

if l≤k then

Ci]=i

Return

Endif

TP1，…，TPl降序排序

For每個(gè)key do

初始化堆

Endfor

For每個(gè)TPi do

堆中刪除值最小的賦值給key

key+=TPi

Enqueue（Ckey]， i）

key插入堆

Endfor

3實(shí)驗(yàn)與分析

3.1實(shí)驗(yàn)環(huán)境

研究中，實(shí)驗(yàn)硬件為 Intel Core（TM） i7-6700HQ CPU 2.60 GHz， 4核， 每個(gè)核可以開啟2個(gè)線程， 32 KB L1 每核獨(dú)立數(shù)據(jù)緩存， 256 KB L2 每核獨(dú)立緩存和 8 MB L3 核間共享緩存， 16 G 內(nèi)存，運(yùn)行系統(tǒng)為 Linux CentOS 7。

實(shí)驗(yàn)數(shù)據(jù)模式集共有106條模式串，來源包括3部分。一部分為從網(wǎng)上隨機(jī)爬取的字符串（60 000條），一部分為從Snort規(guī)則集中提取的字符串（1 000條），最后一部分是隨機(jī)生成的字符串（39 000條）。選擇的所有模式串經(jīng)過了如下預(yù)處理：

（1）統(tǒng)一采用UTF-8方式，保持編碼一致性。

（2）去掉了重復(fù)的字符串。

模式集特征包括：112個(gè)不同字符，115個(gè)不同長度，最小長度為12，最大長度為149。相同長度的模式數(shù)量如圖2所示。

測試輸入數(shù)據(jù)文本包括3×106條字符串，由2部分組成。其中，106條為從模式集中隨機(jī)抽取；2×106條為為隨機(jī)生成。

3.2實(shí)驗(yàn)結(jié)果與分析

3.2.1算法比較實(shí)驗(yàn)

傳統(tǒng)WM算法和基于指紋模型的WM算法的比較如圖3所示。基于指紋模型的WM算法運(yùn)行效率要明顯高于傳統(tǒng)WM算法，并且隨著模式集合的增大，效果越顯著。

3.2.2模式集劃分及優(yōu)化組合實(shí)驗(yàn)

模式集以長度為衡量劃分后的子集運(yùn)行時(shí)間如圖4所示，運(yùn)行時(shí)間與模式集大小和沖突率有關(guān)。模式集數(shù)量越大，運(yùn)行時(shí)間越長；沖突率越大，運(yùn)行時(shí)間越長。

經(jīng)過動態(tài)規(guī)劃算法優(yōu)化后，再進(jìn)行沖突率調(diào)整，需要調(diào)整的子集數(shù)為8個(gè)。本文用8個(gè)線程并行運(yùn)行，選用了初始按長度劃分+貪心調(diào)度、動態(tài)規(guī)劃組合+貪心調(diào)度、動態(tài)規(guī)劃組合+調(diào)整沖突率+貪心調(diào)度這3個(gè)方法展開對比。實(shí)驗(yàn)結(jié)果如圖5所示。經(jīng)過對圖5的分析后可以表明，隨著模式集數(shù)量增加，所有運(yùn)行時(shí)間均呈現(xiàn)增長態(tài)勢，優(yōu)化后的算法運(yùn)行時(shí)間相對更短，且模式集越大，效果越明顯，增加沖突率調(diào)整的算法比原始動態(tài)規(guī)劃方法略好。

4結(jié)束語

本文針對海量模式的精確字符串匹配效率低的問題，提出了一種基于指紋模型的海量模式并行匹配方法。研究中使用多項(xiàng)式計(jì)算出的指紋集合替代傳統(tǒng)WM的Prefix表，降低了沖突率，而且又采用了多核并行的方案，并行化通過模式集的劃分與優(yōu)化組合獲得了協(xié)同處理實(shí)現(xiàn)。首先，按照模式長度將原始模式集劃分多個(gè)子集；其次，利用動態(tài)規(guī)劃算法重新組合，得到效率表現(xiàn)更佳的子集集合，然后，通過調(diào)整沖突率，均衡每個(gè)子集的沖突率；至此，則用貪心算法將最終的子集調(diào)度到多核中運(yùn)行。實(shí)驗(yàn)結(jié)果表明，本文的方法運(yùn)行效率明顯優(yōu)于原始指紋模型隨機(jī)調(diào)度并行方法，與未加沖突調(diào)整的動態(tài)規(guī)劃方法相比，效率略有提升。

參考文獻(xiàn)

[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]. 電子學(xué)報(bào)， 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] 劉燕兵，邵妍，王勇，等. 一種面向大規(guī)模URL過濾的多模式串匹配算法J]. 計(jì)算機(jī)學(xué)報(bào)， 2014， 37（5）： 1159-1169.（上接第36頁）

[2] 楊軍， 李震宇， 孫光才， 等. 一種新的大斜視TOPS SAR全孔徑成像方法J]. 西安電子科技大學(xué)學(xué)報(bào)， 2015， 42（1）： 42-48，55.

[3]崔亞奇，熊偉，何友. 基于目標(biāo)指示的兩坐標(biāo)警戒雷達(dá)目標(biāo)高度補(bǔ)償狀態(tài)估計(jì)J]. 電子學(xué)報(bào)，2015，43（3）： 475-482.

[4] 于超鵬，郝亮飛，謝金華. 線性調(diào)頻和巴克碼組合調(diào)制雷達(dá)信號J]. 探測與控制學(xué)報(bào)，2009，31（5）：20-24.

[5] 李巍， 齊巍， 丁赤飚，等. 基于分布式雷達(dá)的寬帶脈沖三維測距機(jī)制及方法研究J]. 電子與信息學(xué)報(bào)， 2015，37（3）： 643-650.

[6] 王玉璽，黃國策，李偉，等. 基于非單調(diào)遞增頻率偏移的混合相控陣MIMO雷達(dá)目標(biāo)跟蹤方法J]. 電子與信息學(xué)報(bào)， 2017， 39（1）： 110-116.

[7] 黃中瑞， 鄭志東， 張劍云. 目標(biāo)角度估計(jì)的多輸入多輸出雷達(dá)發(fā)射方向圖綜合J]. 電波科學(xué)學(xué)報(bào)， 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ìn)頻率信號認(rèn)知雷達(dá)波形優(yōu)化設(shè)計(jì)方法J]. 航空學(xué)報(bào)， 2016， 37（7）： 2276-2285.