本文關(guān)鍵詞：一種適合于超大規(guī)模特征集的匹配方法

  更多相關(guān)文章： 網(wǎng)絡(luò)安全 超大規(guī)模特征匹配 串匹配 混合自動(dòng)機(jī) 算法 信息安全

【摘要】：串匹配技術(shù)是入侵檢測(cè)系統(tǒng)中的關(guān)鍵技術(shù),隨著特征數(shù)量的增加,現(xiàn)有的自動(dòng)機(jī)類匹配算法都會(huì)面對(duì)內(nèi)存占用過大的問題.當(dāng)特征超過一定數(shù)目后,自動(dòng)機(jī)可能根本無(wú)法構(gòu)造.文中提出了一種針對(duì)超大規(guī)模特征匹配(SLSPM)環(huán)境的匹配算法SLSPM.SLSPM算法借助一個(gè)塊式匹配自動(dòng)機(jī)和若干個(gè)普通自動(dòng)機(jī)完成匹配工作,而且能夠支持至少上萬(wàn)規(guī)模的特征集.與普通匹配自動(dòng)機(jī)先讀入狀態(tài)再判斷讀入符號(hào)的方式不同,SLSPM首先使用散列函數(shù)判斷當(dāng)前文本塊是否可以被過濾掉.如果文本塊無(wú)法被過濾且為合法文本塊時(shí),再檢查當(dāng)前狀態(tài)是否是一個(gè)能夠識(shí)別當(dāng)前文本塊的狀態(tài).僅在當(dāng)前狀態(tài)吻合的情況下再讀入下一個(gè)文本塊進(jìn)行后續(xù)匹配.理論證明顯示SLSPM算法具有近似O(n)的復(fù)雜度.由于SLSPM算法未能保存全部的跳轉(zhuǎn)信息,其匹配速度相對(duì)于高級(jí)AhoCorasick算法未有大幅提升.算法的優(yōu)勢(shì)在于,該算法在軟件環(huán)境下能夠維持與AC算法相同的匹配性能,而且能夠?qū)⑻卣骷虞d規(guī)模至少提升至上萬(wàn)以適應(yīng)超大規(guī)模特征集匹配環(huán)境.
【作者單位】： 哈爾濱工業(yè)大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心;
【基金】：國(guó)家“九七三”重點(diǎn)基礎(chǔ)研究發(fā)展規(guī)劃項(xiàng)目基金(2011CB302605) 國(guó)家“十一五”科技支撐計(jì)劃(2012BAH37B01) 國(guó)家“八六三”高技術(shù)研究發(fā)展計(jì)劃項(xiàng)目基金(2012AA012502,2011AA010705,2012AA012506)資助
【分類號(hào)】：TP393.08;TP391.1
【正文快照】： 1引言字符串匹配可以被理解為從給定符號(hào)序列中找出一個(gè)具有某種屬性的模式,最簡(jiǎn)單的例子是從給定字符序列中找出一個(gè)給定的字符串.字符串匹配是計(jì)算機(jī)科學(xué)中最古老、研究最廣泛的問題之一,并且,字符串匹配的應(yīng)用隨處可見[1],比如生物領(lǐng)域和計(jì)算機(jī)科學(xué)中.本文專注的是計(jì)算機(jī)科

【參考文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前3條

1 胡s，

本文編號(hào)：1166530