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

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

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

【參考文獻】

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

1 胡s，

本文編號：1166530