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

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

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 朱艷;許家s，

本文編號(hào)：1490957