本文關(guān)鍵詞： 多模式匹配 FFT 散列函數(shù) 歐幾里得距離　出處：《吉林大學(xué)》2017年博士論文　論文類型：學(xué)位論文

【摘要】：人們每天需要處理的信息量正快速增長。若要為所有授權(quán)用戶保存這些信息時實現(xiàn)高機(jī)密性、完整性和可用性,則需要強(qiáng)大的技術(shù)和穩(wěn)健的工具。而信息安全與管理工具直接取決于其算法的有效性和熟練度。多模式匹配算法主要用于大量信息處理和信息安全的應(yīng)用程序,比如,入侵檢測/預(yù)防系統(tǒng)、殺毒系統(tǒng)、數(shù)據(jù)挖掘應(yīng)用和數(shù)據(jù)分析應(yīng)用,這些應(yīng)用都主要以多模式匹配算法為基礎(chǔ),都需要強(qiáng)大和高效的算法,從而可以同時準(zhǔn)確搜索成千上萬的模式,然后報告每個模式出現(xiàn)的位置。直接應(yīng)用在非常長的字符串中逐一搜索成千上萬模式的單模式匹配算法,不能算是高效的操作,特別是當(dāng)我們處理大量信息時。必須開發(fā)高效的多模式匹配算法,不僅運行及時,而且不會對信息轉(zhuǎn)化有任何延誤。否則,安全或處理工具就會變成影響整個應(yīng)用程序性能的瓶頸。多模式匹配被定義為如果一組k個模式P={p0,p1,p2...pk}的總長度為｜P｜,每個模式的長度為m。長度為n的文本t的串鏈都位于相同的有限字母集∑,這里,n、｜P｜0和n ≥m。如果模式p出現(xiàn)在文本t內(nèi),則它們決定其出現(xiàn)位置和出現(xiàn)次數(shù)。有許多技術(shù)用于改進(jìn)模式匹配算法的性能,比如,主要采用一般線性乘積、位并行、壓縮字符串、漢明距離、素數(shù)編碼、正則表達(dá)式、散列函數(shù)和AC自動機(jī)等。帶通配符的模式匹配算法可以視作一般線性乘積的特殊情形,可以按照布爾卷積或多項式卷積處理它。多項式卷積可以通過離散傅里.葉變換(Discrete Fourier transform,DFT)有效計算,主要包括四個步驟,即預(yù)處理、計算有兩個多項式系數(shù)的DFT、對DFT結(jié)果做簡單分量乘法、以及計算乘法乘積的離散傅里葉逆變換(Inverse Discrete Fourier transform,IDFT),如下所示。假設(shè)a和b是兩個向量,長度為n,我們需要使用快速傅里葉變換(Fast Fourier Transform,FFT),即DFT及其IDFT,來計算這兩個向量之間的卷積,因此,必須完成如下步驟:1、為a和b的末端都填補(bǔ)0,定義a'和b'為:a'=[a0,a1,...,an-1,0,0,...,0]Tb' =[b0,b1,...,bn-1,0,0,...0]T2、計算a'和b'的離散傅里葉變換:y = Fa' 和z= Fb'.3、乘以向量y和z,以分量方式定義簡單乘積:y.z = Fa'.Fb'4、計算這個簡單乘積的離散傅里葉逆轉(zhuǎn)換:c=F-1(Fa'.Fb')結(jié)果c是向量α和b之間的卷積結(jié)果,可以在時間復(fù)雜度O(n log n)內(nèi)予以計算。以上四個步驟被稱為卷積定理,可以用于計算相同時間復(fù)雜度O(n log m)內(nèi)的模式和文本之間的卷積,這里,n是較長向量多項式系數(shù)的數(shù)量或文本t的長度,而m是較短向量多項式系數(shù)的數(shù)量或模式m的長度。某些情況下,模式是長的,這時不能使用FFT以單機(jī)運算計算卷積。乘以大整數(shù)是展示如何把長模式變成小部分的良好示例,可以在單機(jī)運算中完成處理。散列函數(shù)是有效的計算函數(shù),它把任意長度的二進(jìn)制串映射成一些固定長度的二進(jìn)制串,稱為散列值,這里,一個散列值用作一個輸入串的緊湊代表。計算上,散列函數(shù)無法找到兩個不同的輸入散列為相同的值。散列函數(shù)根據(jù)其所使用的運算主要有三種方案,前兩種是通過除法散列和通過乘法散列,第三種是全域散列。在模式匹配中,散列值用于降低計算成本,模式和每個文本聯(lián)配都散列成小數(shù)值,僅用于核查匹配。位并行算法以利用單機(jī)指令可以運算有w位的位向量為基礎(chǔ)。如果一個算法的數(shù)據(jù)項可以壓縮成w位,這個算法就可以通過在一個單機(jī)指令內(nèi)處理許多數(shù)據(jù),從而實現(xiàn)在時間和空間上有盈余。如下符號用于描述本文中所使用的主要基本位運算:(?)表示逐位"OR",''表示逐位"AND",'!'表示逐位"NOT",''表示向右移動位向量,''表示向左移動位向量,移動時,兩個方向上都進(jìn)行零填補(bǔ)。壓縮串匹配技術(shù)以計算機(jī)字長w大于字母集字符log2α的事實為基礎(chǔ)。單機(jī)字可以容納至多α = w/log2α個字符。壓縮串匹配保證可以把許多數(shù)據(jù)壓縮成一個單機(jī)字,從而可以用單機(jī)指令進(jìn)行運算。模式匹配算法中用作位運算指令的主要機(jī)器指令包括:邏輯指令、算術(shù)指令和控制指令。字符串匹配有特殊指令。字長匹配指令wsmatch(a,b)和字長計較指令wscmp(a,b)被認(rèn)為是字符串匹配的重要特殊指令。特殊字長壓縮串匹配指令以英特爾單指令多數(shù)據(jù)流擴(kuò)展(streaming SIMD extension,SSE)技術(shù)為基礎(chǔ)。最近,提出用中國剩余定理(Chinese Remainder Theorem,CRT)素數(shù)編碼來改善帶通配符的模式匹配的性能。開發(fā)多模式匹配算法時需要考慮許多問題,主要包括模式組大小、搜索文本大小、字母集大小、單個模式大小、模式字符大小寫敏感性、算法攻擊抵抗能力、搜索運行時間、不中斷模式更新、最差大小寫性能、以及是否存在通配符。比如,在入侵檢測系統(tǒng)中,開發(fā)高效多模式匹配算法時的一個重要問題是更新簽名時不中斷入侵檢測系統(tǒng)。這里所說的問題是由基于諸如AC自動機(jī)等結(jié)構(gòu)化數(shù)據(jù)所引起的。最近,有許多讓人有興趣開發(fā)的模式匹配算法,分標(biāo)準(zhǔn)形式和非標(biāo)準(zhǔn)形式。非標(biāo)準(zhǔn)形式指的是模式、或文本、或兩者都包括通配符,而通配符符號與字符集中的任何字符、包括其本身都匹配。本文中,我們研究了帶通配符的多模式匹配問題。首先,介紹四種以往工作中作為主要算法的、帶通配符的多模式匹配算法。這四種算法具有四種不同技術(shù),依靠快速傅里葉轉(zhuǎn)換(FFT)計算模式和文件間的卷積。前三種算法用于理論上與我們之前的三種算法進(jìn)行比較,第四種算法用于實踐上與我們之前的算法進(jìn)行比較。第一種算法以計算模式和文件間的歐式距離為基礎(chǔ),在時間O(n log｜｜P｜+ooc log k)內(nèi)運行,第二種算法以計算模式和文件間的漢明距離為基礎(chǔ),在時間Olog ｜P｜ log σ + occ log k)內(nèi)運行,第三種算法以素數(shù)編碼為基礎(chǔ),在時間O(n log m + ooclog0)內(nèi)運行,這里m是最長模式的長度。第四種算法是克利福德算法的單模式匹配算法的重復(fù),克利福德算法是帶通配符的單模式匹配中最高效的算法之一,在時間O(k n log m)內(nèi)運行。第二,我們提出了三種帶通配符的多模式匹配算法。第一種算法以歐幾里得距離和散列函數(shù)為基礎(chǔ),包括三個主要步驟:預(yù)處理、檢查每個模式步驟的第一塊、以及當(dāng)?shù)谝粔K匹配時檢查模式的剩余部分。在預(yù)處理步驟中,每個模式被劃分成適合的長度為l的塊,需要假設(shè)最短模式的長度也足以創(chuàng)建一個塊。如果模式的最后一個部分不足以創(chuàng)建一個完整的塊,那么最后一個塊與前面一個塊合并。分別計算模式py的第一個塊和該模式剩余塊之間的平方差之修正和。首先,每個模式和文本中的每個符號都用獨一無二的整數(shù)以及帶0的通配符進(jìn)行編碼。然后,計算第一個塊by,l和by,q塊之間方差值的修正和Rp[by.l,by,q],如下所示:Rp[by.l,by.q]值用作散列值H[by,l,by.q],用于檢查剩余塊的匹配。為了檢查每個模式的第一塊的匹配情況,計算模式的每個第一個塊by,l和每個可能的聯(lián)配文本t之間的方差之修正和,如下所示:如果塊在位置i處匹配文本,那么和在位置I處等于零。如果模式py的塊by,l匹配文本,那么模式py被視作部分匹配,還需要檢查它的剩余塊。為了檢查部分匹配模式py的剩余塊的匹配情況,假設(shè)塊by,q是部分匹配模式py的一個剩余塊,第一個塊by,1在位置i處匹配文本;然后,需要檢查位置i+(q-1)/處的塊by.q的匹配情況。如果H[by1,by,q]=H[by,1,ti+(q-1)t],那么塊by.q在位置i+(q-1)l處匹配文本,不帶通配符,這里H[by,1,by,q]是by,l和by,q之間的散列值,而H[by,1,ti+(q-1)t]是by,1和文本在位置i+(q-1)l處的散列值。如果在模式的剩余匹配塊中或者在文本中有通配符,那么有值會由于零通配符值而導(dǎo)致丟失。丟失的值可以使用分量乘法輕松予以計算,因為通配符的位置可以在編碼步驟中予以保存。如果Rt'(j)[by.1,by.q]和Rp(j)[by.q,ti+(q-1)t]分別是由于文本中的通配符和模式by,q的剩余塊的零值所導(dǎo)致的丟失值之和,那么如果下式成立,塊by,q在位置i+(q-1)l處匹配帶有一個通配符的文本。如果模式py的第一個塊和所有剩余塊都匹配文本,那么模式py有一個匹配。算法的預(yù)處理時間是O(｜P｜-lk),可以在時間O(k n log l+ o +d)內(nèi)高效找到模式匹配,這里n是文本t的長度,l是塊的長度,k是模式的數(shù)量,o是使用散列值匹配的塊的數(shù)量,而d是使用模式和文本中的散列值匹配的塊中通配符的數(shù)量。我們的算法的主要優(yōu)點是:(1)可以有效找到長模式的匹配;(2)如果字母集大小σ較長,該算法也很有效;(3)支持不中斷模式更新。第二種算法以位并行為基礎(chǔ)。除預(yù)處理步驟外,該算法還包括兩個主要過程。第一個過程構(gòu)建文本符號的位向量,稱為"更新文本字符陣列tbv[i + ml]的位向量"。第二個過程計算漢明距離,稱為"更新結(jié)果陣列R[i][y]的位向量"。為了保證移動過程中每次只處理一個字符,一個長度為w的移動窗口沿著文本移動。更新結(jié)果陣列R[i][y]的位向量在移動窗口的左端、文本的位置i處發(fā)生,而更新文本字符的位向量在移動窗口的右端、文本的位置i+ w處發(fā)生。在預(yù)處理步驟,構(gòu)建模式字符Pbv[][]的位向量和模式字符(fp[][])的發(fā)生位置。這里,ind[][]是用于為發(fā)生模式的字符進(jìn)行索引的一個陣列。在更新文本字符的位向量時,字母集的每個字符都有兩個參數(shù),即文本字符位向量tbv[]和字符lp[]的最后一個發(fā)生位置。字符的最后一個發(fā)生位置是一個整數(shù),表明陣列tbv[]中文本字符位向量的最后一個更新位置。文本字符位向量更新在滑動窗口的右端、文本的位置i+ w處發(fā)生。當(dāng)i = 0時,字符t[w]的位向量應(yīng)該在位置w處更新,從而構(gòu)建了第一個W文本字符的位向量。在移動窗口的每個移動過程中,移動窗口移動1,字符x進(jìn)入移動窗口,對字符x tbv[t[i+ ml]]的位向量進(jìn)行更新�？梢园凑杖缦路绞酵瓿勺址逻^程。字符xtbv'[t[i+ml]]的第一個當(dāng)前位向量根據(jù)當(dāng)前位置和字符x(i+ ml-1p[t[i + ml]])的最后一個更新位置之間的差值移動到左側(cè)。通過用無符號整數(shù)1的OR運算移動的當(dāng)前位向量,增加窗口中字符x的位。然后,位向量及其發(fā)生位置分別存儲在tbv[t[i+ ml]]和1p[t[i + ml]]中。在更新結(jié)果陣列位向量時,假設(shè)移動窗口按照1進(jìn)行移動。在移動窗口的左側(cè),在位置i處有一個字符已經(jīng)離開移動窗口。假設(shè)這個已經(jīng)離開移動窗口的字符是字符x,它的文本位向量用于對所有模式更新陣列R[i][y]的位置i處的位向量,這些模式就包括字符x。這個過程如下所示。首先,字符.x的當(dāng)前文本位向量根據(jù)當(dāng)前位置和最后一個更新位置(i-lp[t[i]])之間的差值移動到左端。假設(shè)字符x在模式py中發(fā)生,字符x的第一個發(fā)生位置是文本的.fp[y][x]處。然后,字符.x的文本位向量移動fp[y][x],到達(dá)右端。接著,在文本位向量tbv[t[ii]和模式位向量pbt[y][x]之間完成aND(即"")位運算。把位向量結(jié)果通過在陣列R[i-fp[y]M][y]的位置(i-fp[y][x],j)處的位向量進(jìn)行OR運算而加到結(jié)果陣列中。然后,如果位向量R[i-fp[y][x]][y]和模式py !pb[y][*]的通配符位向量的補(bǔ)碼相同,那么模式py在位置i處匹配文本。該算法可以在O(n + d(n/σ)(m/w))時間內(nèi)有效查找模式匹配,克服了發(fā)生高百分比通配符的問題。第三種算法以壓縮串和位并行為基礎(chǔ)。主要原理是把文本的每一個α=w/og2a符號壓縮成一個單機(jī)字,用作沿著整個文本移動的移動窗口。在每個移動步驟中,移動窗口的壓縮串與所儲存模式的壓縮串進(jìn)行比較。除預(yù)處理步驟之外,該算法包括兩個主要步驟:移動窗口更新過程和比較過程。假設(shè)機(jī)器字w的大小是標(biāo)準(zhǔn)尺寸(即32或64位)。然后,每個機(jī)器字可以包括至多α = W/log2 σ個字符,這里,σ是字母集大小。γ=log2σ是用于編碼字母集的單個字符的位數(shù)。在預(yù)處理步驟中,文本和模式的每個符號都被編碼成獨一無二的整數(shù),而通配符都被編碼成0。所有模式字符都壓縮成一個機(jī)器字。假設(shè)每個模式都可以編碼成單個機(jī)器字(即mα),因此,每個比較過程花費的時間都只有O(1)。壓縮過程通過移動以及OR位運算來執(zhí)行。串結(jié)果存儲成壓縮串模式。我們以同樣的方式壓縮文本字符。首先,帶有字符尺寸α = w/;log2σ的移動窗口沿著文本t移動。壓縮前面α個字符,然后比較移動窗口的壓縮串與模式的壓縮串。比較過程可以按照如下方式完成。首先,計算模式py壓縮串的補(bǔ)位,然后在模式py的壓縮串和移動窗口壓縮串之間的位置i處執(zhí)行AND位運算,這里通配符的字位都是0。如果結(jié)果字位都是0,就意味著在文本位置i處有模式py匹配。當(dāng)然,匹配可能是偽匹配。另一個過程用于復(fù)查,通配符的位都改成1,在模式壓縮串補(bǔ)位和移動窗口壓縮串之間執(zhí)行OR運算。如果結(jié)果字位都是1,那么模式py有匹配。請注意,在AND位處理中,通配符的位都是0,而在OR位處理中,通配符的位都是1。當(dāng)無法把模式壓縮成單個機(jī)器字時(即mα)需要另一個過程來檢查部分匹配模式的剩余部分的匹配。
[Abstract]:......
【學(xué)位授予單位】：吉林大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2017
【分類號】：TP391.1

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 閔聯(lián)營;趙婷婷;;模式匹配算法的研究與改進(jìn)[J];計算機(jī)與現(xiàn)代化;2006年08期

2 劉省賢;;模式匹配算法及其在農(nóng)作物嫁接中的作用[J];安徽農(nóng)業(yè)科學(xué);2009年19期

3 宋華,戴一奇;入侵檢測中一類允許誤差的多模式匹配算法[J];清華大學(xué)學(xué)報(自然科學(xué)版);2003年07期

4 伊靜,劉培玉;入侵檢測中模式匹配算法的研究[J];計算機(jī)應(yīng)用與軟件;2005年01期

5 彭詩力,譚漢松;基于特征值的多模式匹配算法及硬件實現(xiàn)[J];計算機(jī)工程與應(yīng)用;2005年01期

6 張春生;張曉英;王國忠;;字符串隨機(jī)探測模式匹配算法[J];內(nèi)蒙古民族大學(xué)學(xué)報(自然科學(xué)版);2007年06期

7 林南暉;張國軍;;對模式匹配算法的存儲優(yōu)化研究[J];中國海洋大學(xué)學(xué)報(自然科學(xué)版);2008年S1期

8 王杰;劉亞賓;孫珂珂;;一種快速高效的模式匹配算法的應(yīng)用研究[J];計算機(jī)工程與應(yīng)用;2008年32期

9 周延森;汪永好;;網(wǎng)絡(luò)入侵檢測系統(tǒng)模式匹配算法研究[J];計算機(jī)工程與設(shè)計;2008年07期

10 劉磊;;多模式匹配算法的研究與優(yōu)化[J];濰坊學(xué)院學(xué)報;2008年02期

相關(guān)會議論文 前10條

1 張曉利;周榮輝;;多模式匹配算法在協(xié)議識別中的應(yīng)用[A];中國電子學(xué)會第十六屆信息論學(xué)術(shù)年會論文集[C];2009年

2 佟冰;張忠平;宋麗;;一種改進(jìn)的多源模式匹配算法[A];2005年全國理論計算機(jī)科學(xué)學(xué)術(shù)年會論文集[C];2005年

3 王德正;;網(wǎng)絡(luò)入侵檢測系統(tǒng)中模式匹配算法的研究與改進(jìn)[A];計算機(jī)技術(shù)與應(yīng)用進(jìn)展·2007——全國第18屆計算機(jī)技術(shù)與應(yīng)用（CACIS）學(xué)術(shù)會議論文集[C];2007年

4 朱艷;許家s，

本文編號：1490957