本文關鍵詞：FilterFA:一種基于字符集規(guī)約的模式串匹配算法

  更多相關文章： 入侵檢測 多模式串匹配 字符集規(guī)約 字符集映射

【摘要】：多模式串匹配技術是入侵檢測系統(tǒng)的核心技術之一,Aho-Corasick算法廣泛應用于其中。針對AC自動機內(nèi)存開銷巨大影響算法性能的問題,提出一種基于字符集規(guī)約的改進算法——FilterFA。利用字符集映射函數(shù)將原字符集壓縮為多個像字符集,針對像字符集構造新的自動機FilterFA,將空間復雜度降至O(P|Σ′|)。在隨機數(shù)據(jù)集和真實數(shù)據(jù)集ClamAV上的測試結果表明,當像字符集大小為8,且保證誤識別率小于2%時,FilterFA算法消耗的存儲空間僅為AC算法的3%左右。
【作者單位】： 中國科學院信息工程研究所;中國科學院大學;信息內(nèi)容安全技術國家工程實驗室;中國移動(深圳)有限公司;
【基金】：中國科學院戰(zhàn)略性科技先導專項基金資助項目(No.XDA06031000) 新疆自治區(qū)科技專項基金資助項目(No.201230123)~~
【分類號】：TP391.1
【正文快照】： 1引言字符串匹配問題是網(wǎng)絡入侵檢測系統(tǒng)的核心技術之一,在近幾十年的發(fā)展中研究非常廣泛。它廣泛應用于信息安全、文本檢索和計算生物學等領域。著名的入侵檢測系統(tǒng)Snort[1]包含多種規(guī)則匹配算法,如Boyer-Moore(BM)[2]、Wu-Manber(WM)[3]和Aho-Corasick(簡稱AC)[4]算法。其中，

本文編號：1250810