基于大數(shù)據(jù)處理的模式匹配算法效率分析

汪 瀅，熊 璐，劉 曉

（南昌師范學(xué)院，江西 南昌330032）

0 引 言

目前大數(shù)據(jù)和網(wǎng)絡(luò)技術(shù)已經(jīng)相對成熟，每天產(chǎn)生的數(shù)據(jù)信息呈指數(shù)級增長，網(wǎng)絡(luò)數(shù)據(jù)流的高效快速處理是當(dāng)前信息安全研究的重要方向[1]。海量數(shù)據(jù)有四個(gè)特點(diǎn)：數(shù)量大、種類多、速度快、價(jià)值高，因此常規(guī)數(shù)據(jù)處理方法難以適用。檢索大量數(shù)據(jù)并進(jìn)行快速匹配是許多系統(tǒng)應(yīng)用所要解決的問題。模式匹配算法是防火墻數(shù)據(jù)過濾、入侵檢測、天氣數(shù)據(jù)分析和預(yù)測等應(yīng)用中不可缺少的一部分[2]。

數(shù)據(jù)檢索和快速匹配技術(shù)的核心是模式匹配算法，該算法主要有單模式匹配和多模式匹配兩種，單一模式匹配算法只能匹配文本串中的一個(gè)模式字符串，而多模式匹配算法則是一組模式，即在文本字符串中快速匹配多個(gè)模式字符串。單一模式匹配算法的研究是多模式匹配算法的基礎(chǔ)，但是在實(shí)際應(yīng)用中，多模式匹配算法得到了越來越廣泛的應(yīng)用。

分析模式匹配算法效率對于提高匹配算法的適用性有重要意義。文獻(xiàn)[3]提出了一種基于Snort系統(tǒng)的模式匹配算法效率分析方法，設(shè)計(jì)了馬爾可夫鏈狀態(tài)轉(zhuǎn)換圖，然而這種轉(zhuǎn)換圖雖然具有直觀的意義，但是由于不能將匹配次數(shù)和文本串聯(lián)系到一起，所以得到的結(jié)論與實(shí)際結(jié)果嚴(yán)重不符。文獻(xiàn)[4]提出了基于一次判斷雙字符比較的模式匹配算法，通過窮舉法計(jì)算算法效率，該算法準(zhǔn)確率高，然而計(jì)算過程復(fù)雜。

綜上所述，本文基于大數(shù)據(jù)處理研究了一種模式匹配算法效率分析方法，建立算法分析模型，并通過窮舉法對算法的效果進(jìn)行分析，最后通過實(shí)驗(yàn)驗(yàn)證了方法的有效性。

1 模式匹配算法效率分析模型

由于基于大數(shù)據(jù)處理的模式匹配算法效率分析方法有單模式匹配算法和多模式匹配算法，因此本文建立的模式匹配算法分析模型也包括兩種，分別是單模式匹配算法分析模型和多模式匹配算法分析模型[5?6]。

1.1 單模式匹配算法效率分析模型

設(shè)定單模式匹配算法文本串為T，計(jì)算表達(dá)式為：

根據(jù)式（1）可知，文本串的長度為n。

設(shè)定單模式匹配算法的模式串為P，表達(dá)式為：

根據(jù)式（2）可知，模式串的長度為m。

在對單模式匹配算法進(jìn)行分析時(shí)，需要判斷在文本串中是否出現(xiàn)過模式串，如果判斷結(jié)果為出現(xiàn)，則證明匹配結(jié)果是成功的；如果判斷結(jié)果為沒有出現(xiàn)，則證明匹配結(jié)果是失敗的[7?9]。具體單模式匹配算法的匹配過程如圖1所示。

圖1 單模式匹配算法數(shù)據(jù)匹配過程

單模式匹配算法的效率平均值計(jì)算需要進(jìn)行字符串和模式串匹配，匹配方向?yàn)閺挠蚁蜃?，如果第一組數(shù)據(jù)匹配成功，則繼而進(jìn)行第二組數(shù)據(jù)匹配，依次進(jìn)行，如果所有的數(shù)據(jù)都能夠順利匹配，則證明匹配成功；反之，則證明匹配失敗[10?11]。

1.2 多模式匹配算法分析模型

設(shè)定多模式匹配算法文本串為T′，計(jì)算表達(dá)式為：

根據(jù)式（3）可知，文本串的長度為z。

設(shè)定多模式匹配算法的模式串為P′，表達(dá)式為：

根據(jù)式（4）可知，模式串的長度為k。

多模式匹配算法的分析方法與單模式匹配算法分析方法相同，需要判斷在文本串中是否出現(xiàn)過模式串，如果結(jié)果為出現(xiàn)，則匹配成功；否則為失敗[12]。多模式匹配算法數(shù)據(jù)匹配過程如圖2所示。

圖2 多模式匹配算法數(shù)據(jù)匹配過程

單模式匹配算法的效率平均值計(jì)算需要進(jìn)行字符串和模式串匹配，匹配方向?yàn)閺挠蚁蜃?，如果第一組數(shù)據(jù)匹配成功，則繼而進(jìn)行第二組數(shù)據(jù)匹配，依次進(jìn)行，如果所有的數(shù)據(jù)都能夠順利匹配，則證明匹配成功；反之，則證明匹配失敗[13]。

2 基于大數(shù)據(jù)處理的模式匹配算法效率分析

在構(gòu)建模式匹配算法效率分析模型后，應(yīng)用大數(shù)據(jù)處理技術(shù)分析模式匹配算法效率[9]。掃描被匹配的文本串中的字符，根據(jù)掃描結(jié)果判斷運(yùn)行狀態(tài)，分析過程中引入Goto表、Fail表、Output表。

匹配過程如圖3所示。

圖3 不同表格匹配過程

不同表格負(fù)責(zé)不同的工作，分析過程如下：

1）Goto表負(fù)責(zé)記錄模式串中的內(nèi)容，將匹配的字符以模式串的形式轉(zhuǎn)給不同的分支，將得到的分支轉(zhuǎn)到模式樹結(jié)構(gòu)中，挑選出模式樹中重復(fù)的部分，并重新創(chuàng)建，將最后的字符進(jìn)行標(biāo)記，得到終止?fàn)顟B(tài)。

2）Fail表記錄不同自動(dòng)機(jī)的狀態(tài)，將其輸入到不同模式中，記錄文本串中的各個(gè)字符，通過轉(zhuǎn)換狀態(tài)，判斷字符是否失敗，F(xiàn)ail表記錄的是跳轉(zhuǎn)過程中深度最大的狀態(tài)。

3）Output表負(fù)責(zé)記錄終止?fàn)顟B(tài)，當(dāng)記錄的狀態(tài)為終止?fàn)顟B(tài)時(shí)，將所有的模式串集合到一起，如果前面兩個(gè)表的狀態(tài)發(fā)生改變，則需要再次記錄終止?fàn)顟B(tài)，直到所有的終止?fàn)顟B(tài)都寫入到Output表為止。具體的分析流程如圖4所示。

圖4 匹配算法分析流程

記錄不同算法的匹配差，設(shè)定算法在進(jìn)行移動(dòng)的過程中，文本串和模式串的字符個(gè)數(shù)共有μ個(gè)，其中，屬于模式串的字符個(gè)數(shù)為α，不屬于模式串的字符個(gè)數(shù)為β，利用大數(shù)據(jù)算法對文本匹配結(jié)果進(jìn)行計(jì)算，結(jié)果如式（5）所示：

式中S1代表匹配后的結(jié)果。由于匹配的所有文本字符都是隨機(jī)字符，彼此互相獨(dú)立，分布特征與二項(xiàng)式分布特征相同[14]，對分布概率進(jìn)行計(jì)算，得到的概率計(jì)算公式為：

根據(jù)式（6）可知，如果文本中的字符與模式串的字符不符合，則證明匹配結(jié)果不成立。根據(jù)上述過程實(shí)現(xiàn)匹配算法效率分析。

3 實(shí)驗(yàn)與研究

經(jīng)過對上述模式匹配算法的效率分析研究，為驗(yàn)證本文分析方法的性能，將本文方法的研究結(jié)果與傳統(tǒng)方法的研究結(jié)果進(jìn)行實(shí)驗(yàn)比較，并構(gòu)建對比實(shí)驗(yàn)。

本文實(shí)驗(yàn)在單機(jī)的環(huán)境下執(zhí)行任務(wù)操作指令。硬件系統(tǒng)規(guī)格為內(nèi)置CPU，內(nèi)存2 GB，操作主系統(tǒng)選用Fedoral13。將基于Snort系統(tǒng)的模式匹配算法效率分析（見文獻(xiàn)[3]）、規(guī)則軟件系統(tǒng)模式匹配算法效率分析（見文獻(xiàn)[4]）與本文基于一次判斷雙字符比較的模式匹配算法效率分析在上述實(shí)驗(yàn)環(huán)境中進(jìn)行對比。實(shí)驗(yàn)過程中的操作數(shù)據(jù)來自于互聯(lián)網(wǎng)中的流數(shù)據(jù)，模式集數(shù)據(jù)由頻繁出現(xiàn)于網(wǎng)絡(luò)中的系統(tǒng)數(shù)據(jù)組成，流數(shù)據(jù)結(jié)構(gòu)圖如圖5所示。

圖5 流數(shù)據(jù)結(jié)構(gòu)圖

將以上數(shù)據(jù)與實(shí)驗(yàn)數(shù)據(jù)集合相組合，并匹配相應(yīng)的系統(tǒng)操作手段，調(diào)整此時(shí)的實(shí)驗(yàn)環(huán)境操作狀態(tài)，按照實(shí)驗(yàn)內(nèi)部監(jiān)管原則對操作的數(shù)據(jù)進(jìn)行監(jiān)管，保證算法運(yùn)行的安全可靠性。將模式集數(shù)據(jù)劃分為規(guī)模結(jié)構(gòu)不同的5組數(shù)據(jù)，實(shí)驗(yàn)操作文本數(shù)據(jù)均來自于內(nèi)部網(wǎng)絡(luò)空間，由此確保操作的有效性。將需進(jìn)行實(shí)驗(yàn)操作的算法分別錄入模式集數(shù)據(jù)中，并進(jìn)行實(shí)驗(yàn)操作匹配。構(gòu)建的數(shù)據(jù)及參數(shù)如表1所示。

表1 數(shù)據(jù)集參數(shù)表

本文利用上述數(shù)據(jù)集管理不同的模式匹配算法效率狀況，并對實(shí)驗(yàn)得出的不同算法匹配次數(shù)進(jìn)行比較，檢驗(yàn)其與標(biāo)準(zhǔn)次數(shù)間的差異，設(shè)置標(biāo)準(zhǔn)次數(shù)為32次，所獲取的實(shí)驗(yàn)結(jié)果與標(biāo)準(zhǔn)次數(shù)的差異越小，則表示該方法的效率分析效果越好。構(gòu)建實(shí)驗(yàn)對比結(jié)果如圖6所示。

圖6 匹配次數(shù)差異對比圖

根據(jù)圖6可以分析出，本文基于大數(shù)據(jù)處理的模式匹配算法效率分析的匹配次數(shù)相較于其他兩種分析方法更加接近標(biāo)準(zhǔn)次數(shù)，算法效率分析效果較好。文獻(xiàn)[3]方法的匹配次數(shù)與標(biāo)準(zhǔn)次數(shù)的差異較小，文獻(xiàn)[4]方法的匹配次數(shù)與標(biāo)準(zhǔn)次數(shù)的差異較大。

由于本文分析方法在實(shí)驗(yàn)研究的過程中不斷錄入相應(yīng)的數(shù)據(jù)信息保護(hù)規(guī)則，將數(shù)據(jù)控制在系統(tǒng)可控的范圍內(nèi)。同時(shí)，及時(shí)保存消耗的數(shù)據(jù)信息，時(shí)刻記錄已完成實(shí)驗(yàn)操作的數(shù)據(jù)，并專門設(shè)置數(shù)據(jù)存儲(chǔ)中心存儲(chǔ)已接受檢驗(yàn)的匹配算法數(shù)據(jù)，減少了不必要的操作麻煩，縮減操作步驟，節(jié)約算法信息匹配時(shí)間，縮減匹配次數(shù)差異率。文獻(xiàn)[3]方法利用Snort系統(tǒng)快速檢測操作引擎及原理，調(diào)整操作狀態(tài)，彌補(bǔ)算法匹配過程中的不足。加強(qiáng)對數(shù)據(jù)集移動(dòng)距離的計(jì)算力度，獲取較為精準(zhǔn)的算法信息數(shù)據(jù)，提升其算法運(yùn)算效率，降低匹配次數(shù)差異率。而文獻(xiàn)[4]方法雖完善了內(nèi)部效率管理空間性能，但對于匹配操作的了解程度較低，未達(dá)到效率分析的標(biāo)準(zhǔn)，匹配次數(shù)差異較高。

在實(shí)現(xiàn)以上實(shí)驗(yàn)操作后，進(jìn)一步驗(yàn)證本文分析方法的效率分析性能，對其分析過程中產(chǎn)生的內(nèi)存占用率進(jìn)行比較。將屬于相同系統(tǒng)操作的內(nèi)部存儲(chǔ)空間進(jìn)行清理，確保實(shí)驗(yàn)研究的精準(zhǔn)性，避免無關(guān)數(shù)據(jù)的干擾，并轉(zhuǎn)化數(shù)據(jù)鏈狀態(tài)，調(diào)控內(nèi)存信息，構(gòu)建數(shù)據(jù)鏈轉(zhuǎn)化圖如圖7所示。

調(diào)配存儲(chǔ)性裝置，將匹配算法空間內(nèi)部的無關(guān)內(nèi)存清空，保留原始匹配數(shù)據(jù)，在進(jìn)行實(shí)驗(yàn)的同時(shí)注重對匹配原則的管理，防止匹配原則的外泄。時(shí)刻追蹤匹配內(nèi)存占用信息，掌控內(nèi)部數(shù)據(jù)流通狀況，檢驗(yàn)不同匹配算法產(chǎn)生的內(nèi)存占用量。根據(jù)獲取的數(shù)據(jù)進(jìn)行實(shí)驗(yàn)對比，構(gòu)建實(shí)驗(yàn)對比圖如圖8所示。

由圖8可得，文獻(xiàn)[3]方法的分析內(nèi)存占用率較大，文獻(xiàn)[4]方法的分析內(nèi)存占用率較小，本文基于大數(shù)據(jù)處理的模式匹配算法效率分析的分析內(nèi)存占用率均低于其他兩種傳統(tǒng)分析方法。

圖7 數(shù)據(jù)鏈轉(zhuǎn)化圖

圖8 分析內(nèi)存占用率對比圖

造成此種差異的原因在于：本文分析方法不斷匹配相應(yīng)的內(nèi)部計(jì)算程序，精準(zhǔn)掌握匹配算法的運(yùn)算流程，及時(shí)清除干擾度較高的數(shù)據(jù)因素，控制匹配算法在分析過程中的完整性匹配，集中優(yōu)化模式匹配算法的操作流程，追蹤內(nèi)部算法操作信息，并時(shí)刻管理不同的效率分析結(jié)構(gòu)，在分析的同時(shí)獲取高質(zhì)量的數(shù)據(jù)流信息，減少分析內(nèi)存的占用數(shù)量，分析內(nèi)存占用率較低。

文獻(xiàn)[4]方法利用規(guī)則軟件系統(tǒng)規(guī)范算法數(shù)據(jù)的流通狀況，減少不必要的數(shù)據(jù)內(nèi)存占用數(shù)量，并在數(shù)據(jù)管理的過程中匹配相關(guān)的信息操控裝置，監(jiān)管分析空間內(nèi)部的內(nèi)存信息，在產(chǎn)生異常占用時(shí)，立刻清除內(nèi)存數(shù)據(jù)，降低分析內(nèi)存占用率。文獻(xiàn)[3]方法雖緩解了分析過程中的數(shù)據(jù)壓力，但未對分析空間進(jìn)行系統(tǒng)分析，空間內(nèi)部結(jié)構(gòu)較為混亂，對于內(nèi)存占用的了解程度較低，導(dǎo)致其分析過程中產(chǎn)生了大量的無關(guān)數(shù)據(jù)，分析內(nèi)存占用率較高。

4 結(jié) 語

綜上可知，本文基于大數(shù)據(jù)處理的模式匹配算法的效率分析效果良好，能夠減少效率分析過程中的數(shù)據(jù)沖突，合理管理匹配算法的匹配程序，能夠?yàn)楹罄m(xù)研究操作提供較為精準(zhǔn)的數(shù)據(jù)基礎(chǔ)。