[發(fā)明專利]一種多關(guān)鍵詞匹配方法和裝置

無效

• 申請?zhí)枺?/td>: 200810212218.8
• 申請日: 2008-09-05
• 公開（公告）號: CN101364237A
• 公開（公告）日: 2009-02-11
• 發(fā)明（設(shè)計）人: 薛一波;李雪;卞建光
• 申請（專利權(quán)）人: 成都市華為賽門鐵克科技有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30;H04L9/36;H04L29/06
• 代理公司: 北京挺立專利事務(wù)所
• 代理人: 葉樹明

技術(shù)領(lǐng)域

本發(fā)明涉及網(wǎng)絡(luò)通信技術(shù)領(lǐng)域，尤其涉及一種多關(guān)鍵詞匹配方法和裝置。

背景技術(shù)

隨著網(wǎng)絡(luò)應(yīng)用的快速發(fā)展，網(wǎng)絡(luò)環(huán)境日益復雜，越來越多的來自于應(yīng)用層的安全威脅(如病毒、垃圾郵件、流氓軟件等)對網(wǎng)絡(luò)安全造成了巨大的威脅。這些威脅手段封裝在TCP/IP(Transmission?ControlProtocol/Internet?Protocol，傳輸控制協(xié)議/網(wǎng)間協(xié)議)協(xié)議的凈荷部分。傳統(tǒng)防火墻由于僅檢查TCP/IP協(xié)議包頭部分，而不對數(shù)據(jù)包內(nèi)容進行檢查，因而無法攔截此類安全威脅。

在這種形勢下，如圖1所示，基于報文內(nèi)容特征檢測，關(guān)注報文第四層以上(特別是應(yīng)用層)的安全網(wǎng)關(guān)設(shè)備如內(nèi)容安全防火墻、入侵檢測系統(tǒng)、病毒網(wǎng)關(guān)、垃圾郵件網(wǎng)關(guān)、UTM(United?Threat?Management，統(tǒng)一威脅管理)等日益凸顯其重要性。而模式匹配算法作為特征檢測的重要手段，安全網(wǎng)關(guān)中主要性能瓶頸之一，對其功能和性能的要求越來越高。

多模式匹配又稱為多關(guān)鍵詞匹配，是計算機科學領(lǐng)域中的基本問題之一。跟普通單模式匹配算法相對的，掃描的時候針對的是所有預(yù)置的特征進行掃描，通過對待掃描內(nèi)容的一次掃描，獲得所有預(yù)置的特征是否在待掃描內(nèi)容中出現(xiàn)的信息。而對普通的單模式匹配算法，若有多條預(yù)置特征，則需對待掃描內(nèi)容進行多次掃描。

多模式匹配算法解決的問題就是快速而準確地判斷待測文本或者網(wǎng)絡(luò)內(nèi)容中所有出現(xiàn)任意模式的位置。多模式匹配技術(shù)的應(yīng)用領(lǐng)域非常廣泛，除了已經(jīng)得到廣泛應(yīng)用的防火墻、入侵檢測與防御、病毒檢測和網(wǎng)絡(luò)內(nèi)容過濾等網(wǎng)絡(luò)安全領(lǐng)域，還擴展到其它學科和領(lǐng)域，例如信息管理、網(wǎng)絡(luò)搜索引擎和生物信息學當中的基因序列檢測等。因此，研究和發(fā)展多關(guān)鍵詞匹配技術(shù)具有很強的學術(shù)和實際意義，被相關(guān)的學術(shù)和業(yè)界所關(guān)注。

此外，隨著網(wǎng)絡(luò)規(guī)模的擴大，病毒、攻擊、等手段不斷涌現(xiàn)，包含不合法內(nèi)容的站點日益增加，造成的結(jié)果是進行病毒、攻擊、URL(UniformResource?Locator，統(tǒng)一資源定位器)過濾等安全應(yīng)用時，其特征庫的規(guī)模爆炸性增加，現(xiàn)有算法的匹配性能隨著規(guī)則庫的增長逐漸下降，造成相應(yīng)網(wǎng)關(guān)設(shè)備吞吐量的下降，這跟日益增長的網(wǎng)絡(luò)應(yīng)用以及用戶對網(wǎng)絡(luò)吞吐量的需求形成了巨大的反差。在通過更換硬件，采用更高頻率更高性能的硬件產(chǎn)品解決上述反差的同時，對現(xiàn)有模式匹配算法進行優(yōu)化，找到一種更好的適用于超大規(guī)模特征集下的模式匹配算法是當務(wù)之急。

現(xiàn)有技術(shù)中解決多關(guān)鍵詞匹配的基本思路是采用B個字節(jié)的數(shù)據(jù)塊(B一般是采用2～4個字節(jié))通過哈希函數(shù)產(chǎn)生跳躍表，與待測文本作匹配時根據(jù)這個已經(jīng)產(chǎn)生的跳躍表值移動文本，當不能移動時對可能存在匹配的關(guān)鍵詞作進一步的驗證。現(xiàn)有技術(shù)是通過啟發(fā)式的規(guī)則來確定數(shù)據(jù)塊的跳躍值，避開了一些不必要的驗證過程，因而加快了匹配速度。現(xiàn)有技術(shù)的優(yōu)點在于具有平均性能好、匹配速度快、占用的內(nèi)存空間小的特點。

在實現(xiàn)本發(fā)明的過程中，發(fā)明人發(fā)現(xiàn)現(xiàn)有技術(shù)至少存在以下問題：

現(xiàn)有技術(shù)中，關(guān)鍵詞數(shù)量增加后，跳躍表中跳躍值為零的項數(shù)會增多，平均跳躍值會隨之減小，從而無法有效地避免匹配過程中大量不必要的字符比較；導致文本或網(wǎng)絡(luò)內(nèi)容的匹配速度下降；隨著關(guān)鍵詞數(shù)量的增加，前綴相同的關(guān)鍵詞也會大量增加，精確匹配過程中不斷重復匹配相同的前綴也會導致文本或網(wǎng)絡(luò)內(nèi)容的匹配速度下降。

發(fā)明內(nèi)容

本發(fā)明實施例提供一種多關(guān)鍵詞匹配方法和裝置，用于實現(xiàn)提升匹配算法的效率。

本發(fā)明實施例提供一種多關(guān)鍵詞匹配方法，包括：

對關(guān)鍵詞集合進行預(yù)處理并建立相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，所述數(shù)據(jù)結(jié)構(gòu)中包括跳躍表、前綴表、子跳躍表和相同前綴長度表；

根據(jù)待匹配內(nèi)容檢索所述跳躍表；

當所述跳躍表的跳躍值為零時，根據(jù)前綴表表項，調(diào)用子跳躍表和/或相同前綴長度表對所述待匹配內(nèi)容進行匹配。

本發(fā)明還提供一種多關(guān)鍵詞匹配裝置，包括：

預(yù)處理單元，用于對關(guān)鍵詞集合進行預(yù)處理并建立相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，所述數(shù)據(jù)結(jié)構(gòu)中包括跳躍表、前綴表、子跳躍表和相同前綴長度表；

跳躍表檢索單元，用于根據(jù)待匹配內(nèi)容檢索所述跳躍表；

第一內(nèi)容匹配單元，用于當所述跳躍表檢索單元檢索所述跳躍表的跳躍值為零時，根據(jù)所述前綴表表項，調(diào)用子跳躍表和/或相同前綴長度表對所述待匹配內(nèi)容進行匹配。

與現(xiàn)有技術(shù)相比，本發(fā)明實施例具有以下優(yōu)點：