[發明專利]可變步長流分割和多模式匹配

在審

• 申請號: 201080016841.1
• 申請日: 2010-04-13
• 公開（公告）號: CN102395985A
• 公開（公告）日: 2012-03-28
• 發明（設計）人: N·華;T·V·拉克斯曼;H·宋
• 申請（專利權）人: 阿爾卡特朗訊公司
• 主分類號: G06K9/62
• 分類號: G06K9/62;H04L29/06
• 代理公司: 北京市中咨律師事務所 11247
• 代理人: 楊曉光;于靜

技術領域

本發明涉及通信和計算機網絡，更具體地涉及在用于內容檢查系統應用的多模式匹配中使用可變步長(variable-stride)塊進行處理。

背景技術

該部分介紹可能有助于更好地理解本發明的方面。因此，閱讀到的該部分語句就此而論不應被理解為承認什么是現有技術或者什么不是現有技術。

多模式匹配是由諸如基于簽名的網絡入侵檢測和預防系統(NIDS/NIPS或NIDPS)的內容檢查系統使用的關鍵功能。這樣的系統基于可靠的實時檢測網絡業務中的具體簽名或模式以確定是否業務可能夠潛在地對包括主機的網絡或網絡元件有害。

典型地，內容檢查系統可以同時搜索多個這樣的簽名。當線路速率增加超過10Gbps時，用于有效處理多模式匹配的方法日益變得重要。

歷史上，通過使用確定的有限自動機(DFA)來實現模式匹配。DFA是有限狀態機，其中對于每個狀態和輸入符號，存在一個狀態并僅有一個狀態轉換到下一個狀態。關于DFA的信息可以在Gill.A的有限狀態機理論介紹(Introduction?to?the?Theory?of?Finite-State?Machines)、McGraw-Hill、1962中發現，其公開內容以引用方式并入本文。

在基于DFA的模式匹配的基本類型中，每次對網絡業務流處理一個字節或字符。這樣的DFA要求n個狀態以處理n個單字節模式并要求每個狀態有t個轉換，其中t是在模式字母表中符號的數量。然而，以當前網絡的線路速率處理在每個時鐘處理一個字節太慢。

提高基本DFA吞吐量的一個方法是通過在每個匹配步驟中掃描輸入數據流的多個字節(也就是，塊)。雖然該面向塊的DFA方法相對于面向字節的DFA與塊中的字節數量成比例地加速，但是它帶來其它問題。特別是，由于模式可能在塊中的任意偏移量處開始或結束，面向塊的DFA可能需要(1)重復s次，其中s是DFA的塊大小或“步長”，或(2)為每個狀態提供多個轉換。

例如，在對于模式匹配的第一個面向塊的DFA方法中，將模式分為s-字節的塊，并且將塊用于構建DFA。這導致相比于用于相同模式的相應面向字節的DFA，DFA的狀態和轉換更少。然而，DFA的s個實例需要并行運行，每個實例接收具有一個字節偏移量的相同輸入數據流(以確保不會遺漏模式)。如果輸入流是...babbaba...，序列...|ba|bb|ab|a...和其一個字節的移位版本...b|ab|ba|ba|...都需要進行處理以確保不會遺漏匹配。利用該方法，以較高的存儲器帶寬用量為代價可實現較高的吞吐量(匹配引擎并行運行s個實例的結果)，其中對存儲器帶寬的需求與塊的大小s成比例增長。

或者，可以構建單一的DFA，其中轉換說明在流中能夠發生的所有可能的s-字節模式。通過使用較大的DFA，匹配引擎的單一實例可用于掃描輸入數據流而沒有遺漏匹配的可能。在這種情況下吞吐量增加以較高的存儲器用量為代價，而不是以較高的存儲器帶寬為代價。還需要說明的是，來自任意狀態的轉換數量可達t^s，其中t是字母表的大小。實際上，對于使用英文字母表的NIDS簽名集，t＝26，即使對于塊大小s為2個字節時，存儲器用量也是驚人地高。

因此，現有模式匹配方法的基本問題是存在過度的存儲器或存儲器帶寬要求，特別是對于以當前和預期的網絡接口的線路速率運行的系統。

發明內容

在一個實施方式中，本發明是一種用于將輸入符號流與符號模式進行匹配的機器執行的方法。將輸入符號流分割為符號的可變大小的塊以產生至少兩個不同長度的輸入流片段。至少兩個輸入流片段中的每一個與符號模式的模式片段進行比較，其中模式片段相比于符號模式具有較少的符號。

在另一實施方式中，本發明是一種用于將輸入符號流進行分割的機器執行的方法。在輸入符號流中形成符號的k-gram，其中(k＞0)。為每個k-gram計算值。在長度為w的滑動窗中從k-gram值中識別一個或多個特殊值，其中(k＜w)。根據輸入符號流中一個或多個特殊值的位置將輸入符號流劃分為段，其中至少兩個片段具有不同的長度。

附圖說明

通過下面的詳細說明、所附權利要求、和附圖，本發明的其它方面、特點和優勢會變得更明顯，其中在附圖中相同的附圖標記表示相似或相同的元素。

圖1是根據本發明各種實施方式的橫跨至少兩個自治系統并包括網絡入侵檢測和預防系統的通信網絡的框圖；

圖2是圖1的網絡入侵檢測和預防系統140的框圖；