[發(fā)明專利]用于數(shù)據(jù)流的模式匹配方法和裝置

有效

• 申請?zhí)枺?/td>: 200910132546.1
• 申請日: 2009-03-31
• 公開（公告）號: CN101854341A
• 公開（公告）日: 2010-10-06
• 發(fā)明（設(shè)計）人: 鄭凱
• 申請（專利權(quán)）人: 國際商業(yè)機器公司
• 主分類號: H04L29/06
• 分類號: H04L29/06;H04L9/36;G06F21/00
• 代理公司: 中國國際貿(mào)易促進委員會專利商標事務(wù)所 11038
• 代理人: 趙冰

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

本發(fā)明涉及一種用于數(shù)據(jù)流的模式匹配(FPM)方法和裝置。

背景技術(shù)

作為一項新型的防火墻技術(shù)，深度包檢測(DPI)技術(shù)已被廣泛應(yīng)用于入侵檢測/防御系統(tǒng)(IDS/IPS)、阻止垃圾郵件/防病毒、防止數(shù)據(jù)泄漏、內(nèi)容過濾等領(lǐng)域。深度包檢測技術(shù)深入地檢查通過防火墻的每個數(shù)據(jù)包及其有效載荷，其中的DPI引擎基于指紋匹配、啟發(fā)式技術(shù)、異常檢測、以及統(tǒng)計學分析等技術(shù)的規(guī)則集來決定如何處理數(shù)據(jù)包。為了檢測數(shù)據(jù)流中的每個數(shù)據(jù)包例如是否具有攻擊特征，在DPI引擎中普遍采用了模式匹配/特征搜索技術(shù)，對數(shù)據(jù)流中的每個可疑字節(jié)進行比較。然而現(xiàn)有的模式匹配算法所需的計算量和通信量均非常巨大。通常，DPI應(yīng)用針對包含大量模式的模式集需要有大量網(wǎng)絡(luò)傳輸量與其相適配，而且所需的計算能力與被監(jiān)控的網(wǎng)絡(luò)接口的線速成正比(因為DPI不僅檢測包頭，而且還檢測有效載荷)，這使得DPI難以應(yīng)付數(shù)千兆甚至萬兆比特的線速和龐大模式集。

由于模式匹配算法對CPU處理速度有較高的要求，而微電子技術(shù)的發(fā)展已接近它的極限，可能很快會出現(xiàn)“存儲墻(memory?wall)”問題，即存儲速度制約了處理速度，因此采用并行(parallelism)算法可能是開發(fā)針對高性能網(wǎng)絡(luò)入侵檢測系統(tǒng)(NIDS)的可擴展的模式匹配引擎(PM引擎)的唯一出路。目前已經(jīng)提出了一些并行執(zhí)行的模式匹配算法。目前，TCAM(三態(tài)內(nèi)容尋址存儲器)芯片尤其適合用作并行處理的模式匹配引擎，從而實現(xiàn)對流模式匹配的硬件加速。TCAM技術(shù)的優(yōu)點的是查找速度快、功耗低，并且已經(jīng)得到了Cisco、3Com等設(shè)備供應(yīng)商的廣泛支持。因此，有必要提供執(zhí)行效率高、即可以實現(xiàn)高效率并行流水線作業(yè)的解決方案。

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

本發(fā)明旨在提供一種效率更高的流模式匹配方法和裝置，其中通過利用互斥的模式子集來完成流水線式的并行模式匹配。

為此，本發(fā)明一方面提供了一種用于數(shù)據(jù)流的模式匹配方法，該方法包括以下步驟：將輸入的數(shù)據(jù)流分割成多個片段，并將這些片段分別分配給多個模式匹配引擎中的一個，其中每個模式匹配引擎存儲多個在給定檢測窗口長度下互斥的模式子集中的一個；以及所述多個模式匹配引擎中的任意一個模式匹配引擎根據(jù)其中存儲的模式子集對所分配的片段進行模式匹配對比，并在該片段與該任意一個模式匹配引擎存儲的模式子集匹配命中的情況下將該片段輸出。

為了實現(xiàn)流水線式處理，可選地，當某個模式匹配引擎發(fā)現(xiàn)分配給它的片段不能與相應(yīng)的模式子集相匹配時，將該片段送至另一個模式匹配引擎繼續(xù)進行對比；并且當某個片段已經(jīng)被所有的模式匹配引擎檢查過之后均沒有發(fā)現(xiàn)匹配時，報告該片段沒有發(fā)生匹配命中，結(jié)束對該片段的檢查。

為了無誤地對各數(shù)據(jù)片段進行匹配檢測，輸入的數(shù)據(jù)流被分割成長度不小于檢測窗口長度的片段，最好是片段的長度等于檢測窗口長度。可選的是，在將數(shù)據(jù)流分成多個片段時，使得需要對比的模式不跨越至少兩個片段的分割點。為此，可以按照需要對比的目標模式的“反模式(negative?pattern)”來確定數(shù)據(jù)流上的分割點，在該分割點處分割片段，其中所述反模式無論加上任何后綴和/或前綴都不會構(gòu)成所述目標模式。

根據(jù)本發(fā)明，所述多個互斥的模式子集可以是通過對包含多個模式的模式集進行劃分而得到的。可選的是，在將一個模式集劃分成互斥的模式子集時，首先將該模式集劃分成盡可能多的互斥模式子集，然后再將較小的模式子集進行合并，以實現(xiàn)模式子集大小的均衡。

本發(fā)明另一方面還提供了一種用于深度包檢測的流模式匹配裝置，包括：多個模式匹配引擎，其中每個模式匹配引擎存儲多個在給定檢測窗口長度下互斥的模式子集中的一個；流分割及分配單元，用于將輸入的數(shù)據(jù)流分割成多個片段，并將這些片段分別分配給所述模式匹配引擎，其中所述多個模式匹配引擎中的任意一個模式匹配引擎根據(jù)其中存儲的模式子集對所分配的片段進行模式匹配對比，并在該片段與該任意一個模式匹配引擎存儲的模式子集匹配命中的情況下將該片段輸出。該流模式匹配裝置相應(yīng)地執(zhí)行根據(jù)本發(fā)明的上述方法的各步驟。

由于當將一個大的模式集劃分成若干個互斥的子集時，針對一個數(shù)據(jù)包片段可能不需要檢查所有的子集，因而本發(fā)明利用了模式子集的互斥性減少了PM引擎的查找次數(shù)，使流水線處理成為可能，從而大大提高了并行PM引擎的工作效率。通過這種基于“互斥”模式子集的并行模式匹配，無需采用冗余存儲器來擴展存儲空間。

附圖說明

圖1示出了根據(jù)本發(fā)明執(zhí)行并行流模式匹配的裝置的示例性示意圖；

圖2示出了根據(jù)互斥原理對模式集進行劃分的一種示例性算法；以及