一種基於模式聚類的並行網絡流特徵檢測方法
2023-10-25 08:39:57 3
專利名稱：一種基於模式聚類的並行網絡流特徵檢測方法
技術領域：
本發明涉及網絡流量內容檢測技術領域，尤其涉及一種基於模式聚類的並行網絡
流特徵檢測方法。
背景技術：
隨著網際網路成為當今社會的主要基礎設施之一，網際網路中對數據流進行完整性、私密性、可用性等方面的惡意攻擊也快速增長。防火牆作為最廣泛的網絡安全設備，其主要功能是針對網絡數據包包頭的各個域來判斷該網絡數據包是否是授權訪問，之後決定是否讓網絡數據包通過。然而，網絡攻擊模式的增多和形式多樣化使得僅僅檢測網絡數據包包頭部分已經不能滿足攻擊防範的需求，對於網絡數據包負載部分的特徵檢測已經成為網絡入侵檢測系統(NIDS)和網絡入侵防禦系統(NIPS)的非常重要的環節，同時也是統一威脅管理系統(UTM)的重要環節。 現行的特徵檢測方法從算法層面可以稱為多模式匹配方法，它主要研究從待檢測文本中快速查找多個模式的技術。多模式匹配算法首先需要一個用戶預先定義的模式集，其中每個模式標識一種網絡攻擊或者入侵；然後將待檢測網絡數據作為輸入文本進行特徵檢測，從而判斷該網絡數據流是否存在潛在的攻擊或者入侵，然後決定是否阻斷該網絡數據流。 當前網絡主幹網的帶寬發展突飛猛進，對多模式匹配方法的檢測速度提出了更高的需求；與此同時，新的網絡攻擊和入侵模式日益湧現，使得模式集的規模與日倶增，同樣對多模式匹配方法提出了嚴峻的挑戰，許多主流的模式匹配算法(例如AC、麗等)在面對大型規模的模式集時性能都急劇下降，同時基於狀態機或樹結構的算法(AC、 AC_BM、Setwise—BMH等)對空間的需求急劇增加，也使得算法的適用性面臨巨大考驗。在網絡入侵防禦系統(NIPS)和統一威脅管理系統(UTM)中，由於需要實時檢測攻擊模式並給出處理結果，特徵檢測方法的速度已經成為限制設備處理吞吐量的嚴重瓶頸。 基於專用晶片(ASIC)以及FPGA的系統解決方案，雖然在處理速度上具有一定優勢，但是其成本高、靈活性差的特點限制了在特徵檢測方法的應用。同時，隨著多核處理器成為新一代的硬體處理平臺，研究適用於多核平臺的並行網絡流特徵檢測方法成為具有重大意義的課題。
發明內容
( — )發明目的 本發明的目的是提出一種基於模式聚類的並行網絡流特徵檢測方法，以克服上述
特徵檢測方法中的時間和空間性能的不足之處。
發明內容
—種基於模式聚類的並行網絡流特徵檢測方法，包括以下步驟 Sl :選定模式的匹配算法集合，包括適用於短模式的匹配算法和適用於長模式的
4匹配算法； S2:根據所選定的適用於短模式和適用於長模式的匹配算法，選定模式的長度分
割點，將模式集分割為短模式子集和長模式子集； S3 :決定處理短模式子集和長模式子集的處理單元個數； S4 :複製待檢測文本為多份使其份數為所述短模式子集和長模式子集總份數，並
將每份待測文本分別輸入各個短模式子集或長模式子集對應的處理單元中； S5:結合各個短模式子集和長模式子集的處理結果判斷待檢測文本中是否存在攻
擊模式； S6 :重複步驟S4和S5，對待檢測快速網絡流傳送的數據流進行連續檢測。 其中，所述步驟S3包括 決定所述短模式子集的處理單元個數； 利用模式聚類方法將長模式分割為多個長模式子集； 決定所述長模式子集的處理單元個數。 其中，所述步驟S4中若一個短模式子集或一個長模式子集被多個處理單元處理，
那麼輸入的待檢測文本只需送入所述多個處理單元中的一個處理單元進行處理。 其中，所述步驟S5還包括 若存在攻擊模式，執行報警或阻斷操作。
—種基於模式聚類的並行網絡流特徵檢測系統，其中包括 選擇模式匹配算法模塊，用於選定模式的匹配算法集合，包括適用於短模式的匹配算法和適用於長模式的匹配算法； 分割模式集模塊，用於根據所選定的適用於短模式和適用於長模式的匹配算法，選定模式的長度分割點，將模式集分割為短模式子集和長模式子集； 決定處理單元個數模塊，用於決定處理短模式子集和長模式子集的處理單元個數； 檢測文本模塊，用於複製待檢測文本為多份使其份數為所述短模式子集和長模式子集總份數，並將每份待測文本分別輸入各個短模式子集或長模式子集對應的處理單元中； 判斷攻擊模式模塊，用於結合各個短模式子集和長模式子集的處理結果判斷待檢測文本中是否存在攻擊模式； 重複執行模塊，用於重複步驟S4和S5，對待檢測快速網絡流傳送的數據流進行連續檢測。 其中，所述決定處理單元個數模塊包括 決定短模式處理單元個數模塊，用於決定短模式處理單元個數；
長模式分割模塊，用於利用模式聚類方法將長模式分割為多個長模式子集；
決定長模式處理單元個數模塊，用於決定所述長模式子集的處理單元個數。
其中，所述判斷攻擊模式模塊還包括 執行報警或阻斷模塊，用於若存在攻擊模式時執行報警或阻斷操作。
(三)有益效果 本發明中的基於模式聚類的並行網絡流特徵檢測方法是一個可擴展的網絡流特徵檢測整體解決方案，能夠適用於各種等級性能需求以及各種規模的模式集，對於高性能內容檢測、入侵檢測、病毒防護和統一威脅管理、網絡信息監控等系統都具有極為深遠的作用。
圖1是本發明方法對網絡數據流進行檢測的流程 圖2是在AMD 0pteron 270 CPU (64KB LI Cache)的單核上曲線圖； 圖3是在AMD 0pteron 270 CPU (64KB LI Cache)的單核上能曲線圖； 圖4是MRSI算法的數據結構 圖5是本發明的基於模式聚類的並行特徵檢測模型。
具體實施例方式
本發明提出的基於模式聚類的並行網絡流特徵檢測方法，結合附圖和實施例說明如下。 如圖1所示，本發明提出的基於模式聚類的並行網絡流特徵檢測方法。 步驟Sl，選定想要採用的模式的匹配算法集合，一般包括適用於短模式的匹配算
法(如AC)，以及適用於長模式的匹配算法(如麗、RSI等)。 步驟S2，根據所選定的適用於短模式以及適用於長模式的匹配算法，選定模式的長度分割點，將模式集分割為短模式子集和長模式子集，短模式子集用適用於短模式的匹配算法處理，而長模式子集用適用於長模式的匹配算法處理。 步驟S3，根據短模式的經驗化的性能曲線，以及整個特徵檢測系統的期望性能，決定用多少個處理單元來處理短模式集；並根據長模式的經驗化的性能曲線，以及整個特徵檢測系統的期望性能，將長模式分割為多個長模式子集，分割方法為基於代價函數的模式聚類方法，然後決定每個長模式子集用多少個處理單元來處理。 步驟S4，假設整個模式集被分割為N份，那麼將輸入的待檢測文本複製N份，分別輸入各個短模式子集和長模式子集對應的處理單元中，進行並行處理，如果一個短模式子集或長模式子集被多個處理單元處理，那麼輸入的待檢測文本只需送入其中的一個處理單元進行處理，從而達到分流的目的。 步驟S5，結合N個模式子集的處理結果，判斷待檢測文本中是否存在攻擊模式，並給出相應的操作(報警或阻斷)。 步驟S6，重複S4和S5的過程，對待檢測快速網絡流傳送的數據流進行連續檢測。
實施例1 此實施例中，採用的模式集為2008年3月的Snort規則集，該模式集共包含5831條模式。 步驟Sl，選定想要採用的模式匹配算法集合，選定適用於短模式的匹配算法為AC，選定適用於長模式的匹配算法為MRSI。 步驟S2，根據所選定的適用於短模式算法AC和適用於長模式的匹配算法MRSI，選
測出的AC算法的性能測出的MRSI算法的性
6定模式的長度分割點，將模式集分割為短模式子集和長模式子集，由於MRSI算法要求模式的長度最短為6，因此，此實施例中選定長短模式的分割點為6，在Snort規則集中長度小於6的模式的數量為1421條，其餘長度均大於等於6，即長度小於6的模式劃歸AC算法處理(共1421條模式)，而長度大於等於6的模式劃歸MRSI算法處理(共4410條模式)。
步驟S3，決定處理短模式子集和長模式子集的處理單元個數。如圖2所示，為在AMD Opteron 270 CPU(64KB LI Cache)的單核上測出的AC算法的性能曲線，其中，1421條模式下AC的處理速度大約為400Mbps，如果特徵檢測系統的整體性能要求為400Mbps，那麼用1個處理單元(單核)來處理短模式集即可，如果整體性能要求達到800Mpbs，那麼可用2個處理單元來處理短模式集。如圖3所示，為在AMD Opteron 270 CPU (64KB LI Cache)的單核上測出的MRSI算法的性能曲線，其中，4410條模式下MRSI的處理速度大約為170Mbps,而2000條模式下MRSI的處理速度可以達到300Mpbs，如果特徵檢測系統的整體性能要求為300Mbps，那麼可以將長模式集分割為2個長模式子集，然後用2個處理單元來處理，如果特徵檢測系統的整體性能要求為600Mbps，那麼可以將長模式集分割為2個長模式子集，然後對2個子集分別用2個(一共用4個)處理單元來處理。 —般情況下，可以假設需要將長模式集分割為m個長模式子集，那麼從數學上來看，將長模式集分割為m個子集的問題可以看作是尋找一個最優的映射函數f :P — S，使得m個長模式子集的代價函數之和A j(l《j《m)最小。此處需要用到模式聚類的思想，此方法具體包含四個步驟 (1)隨機選擇m個長模式，每個長模式置於一個長模式子集中，針對每個長模式子集，計算得到它的代價函數A j(l《j《m)。 (2)對於其餘的n-m個長模式Pi ，針對Pi加入每個長模式子集Sk，計算長模式子集代價函數之和E k A j。如果E t A j = mini《k《m E kA」，即Pi加入長模式子集St得到的長模式子集代價函數之和最小，那麼將Pi置於長模式子集Si中。至此，每個長模式都得到初始子集編號，並且每個長模式子集都得到了初始代價函數值《j《m)。
(3)開始模式聚類循環在第1次循環中，對於每個長模式Pi，假設其子集編號為t，將其子集編號分別設置為1到m並且計算新的長模式子集代價函數之和E k°Aj，E』入j表示Pi加入長模式子集Sk的長模式子集代價函數之和。如果2:^,mm'^ZA ，即Pi加入長模式子集Sv的長模式子集代價函數之和最小，那麼將Pi的子集編號由t更改為v。當所有長模式都完成第1次循環後，各個長模式子集得到了新的代價函數值A / (1《j《m)。
(4)繼續模式聚類循環，直到循環前後的長模式子集代價函數之和的差小於預先
設定的正數e為止，即G^-2:r'w/i:A"。此時，循環停止，循環次數為r，並且各個長模式
得到各自最終的子集編號。 此處需要額外指出的是，此模式聚類方法適用於各種基於跳躍的模式匹配方法，
如麗、RSI、MRSI、AC BM等，當然針對不同的算法，其代價函數也會有所不同。此處以MRSI
算法為例，給出代價函數的具體定義，其它算法的代價函數可同理獲得。 如圖4給出了 MRSI算法的數據結構，其中第一階段的字塊跳躍表格BLTftl存儲
了根據匹配窗口的倒數第一、第二字節組成的字塊能夠得到的最大跳躍值，字塊跳躍表格
BLT#2存儲了根據匹配窗口的倒數第三、第四字節組成的字塊能夠得到的最大跳躍值，字塊
跳躍表格BLTft3存儲了根據匹配窗口的倒數第五、第六字節組成的字塊能夠得到的最大跳躍值。第二階段的潛在匹配表格(PMT)存儲了當BLTftl中的跳躍值為O時可能匹配的模式， 如果有多個可能匹配的模式，則用鍊表進行維護。MRSI算法的匹配過程為
(1)利用3個雙字節字塊(匹配窗口的倒數第一第二字節，第三第四字節，第五第 六字節)來分別索引3張BLT表格，得到3個跳躍值； (2)將3個跳躍值中的最大值記為L^，如果Lmax > 0，那麼將文本的匹配窗口移動 L 個字節
^maxI 丁 lJ ， (3)如果L^ = O，那麼利用匹配窗口的倒數第一第二字節構成的雙字節字塊來索 引PMT表格，然後將逐一掃描鍊表中可能匹配的模式，最終確定真正匹配的模式。
根據MRSI算法的匹配過程，可以看到算法的匹配速度取決與三個字塊跳躍表格 (BLT)中的跳躍值的大小以及潛在匹配表格(PMT)中鍊表的長度。顯然地，如果BLT表格 中的跳躍值越大，PMT表格中鍊表的長度越短，MRSI算法的速度更快。因此，在將長模式 集劃分為子集的過程中，策略是讓3張BLT表格中的平均跳躍值最大，並且讓PMT表格中 的鍊表平均長度最短。假設3個BLT表格中跳躍值為L,(0《i《65535， 1《k《3)，那 麼可以用:^^—。來表示3張BLT表格中的平均跳躍值；假設PMT表格中的鍊表長度為 Hi(O《i《65535)，那麼可以用》=柳""(z/,)來表示PMT表格中的鍊表平均長度。如果文本的
匹配窗口可以移動Z個字節，代表每個字節位置需要l/Z次的內存訪問，而鍊表長度為i 則表 示每個字節位置平均需要^2次內存訪問。假設存在潛在匹配的概率為P^。h(即需要訪問
鍊表的概率)，那麼MRSI算法的代價函數可以表示為J = (i-U"U^2 。利用此代價 函數，根據上述的模式聚類方法，可以將長模式集優化分割為多個子集。此模式聚類方法能 夠達到局部最優解。 步驟S4，複製待檢測文本為多份使其份數為所述短模式子集和長模式子集總份 數，並將每份待測文本分別輸入各個短模式子集或長模式子集對應的處理單元中。為方便 舉例，假設一共有6個模式& Pe，其中P" P2為短模式，P3， P4， P5， P6為長模式，而長模式 又被分割為2個長模式子集Pn P4以及P5， P6。那麼模式集一共被分割為3份，這樣就需要 將輸入的待檢測文本複製3份，分別交由3個模式子集的處理單元進行處理。另外，如果短 模式集合Pi，^由2個處理單元來處理，那麼可以將待檢測文本只需送入其中的一個處理單 元進行處理，從而達到分流的目的。此模型具體可參見圖5所示的並行特徵檢測模型。
步驟S5，結合各個短模式子集和長模式子集的處理結果判斷待檢測文本中是否 存在攻擊模式。如圖5所示，網絡數據包Pktl的處理結果需要根據Core#l、 Core#3以及 Coreft4的處理結果共同決定，只要一個處理單元發現待檢測文本中存在攻擊模式，那麼就 應當給出相應的操作(報警或阻斷)。 S6 :重複步驟S4和S5，對待檢測快速網絡流傳送的數據流進行連續檢測。
本發明中的基於模式聚類的並行網絡流特徵檢測方法，在時間性能方面，通過挖 掘各類模式匹配算法的性能特點和優勢，將模式集分割為適合於不同算法的模式子集，利 用多核處理器平臺的多處理器硬體特性，達到並行處理模式子集的效果；同時利用模式聚 類的方法，在長模式規則子集的分割過程中，做到局部最優，從而使得整個特徵檢測系統的 檢測速度達到最大程度的優化。在空間性能方面，由於將模式集分割為多個模式子集，使 得整體的空間佔用比原始的模式集大幅減小，也提高了各個模式子集處理單元的緩存命中 率，進一步提高了系統的整體性能。
以上實施方式僅用於說明本發明，而並非對本發明的限制，有關技術領域的普通 技術人員，在不脫離本發明的精神和範圍的情況下，還可以做出各種變化和變型，因此所有 等同的技術方案也屬於本發明的範疇，本發明的專利保護範圍應由權利要求限定。
權利要求
一種基於模式聚類的並行網絡流特徵檢測方法，其特徵在於，包括以下步驟S1選定模式的匹配算法集合，包括適用於短模式的匹配算法和適用於長模式的匹配算法；S2根據所選定的適用於短模式和適用於長模式的匹配算法，選定模式的長度分割點，將模式集分割為短模式子集和長模式子集；S3決定處理短模式子集和長模式子集的處理單元個數；S4複製待檢測文本為多份使其份數為所述短模式子集和長模式子集總份數，並將每份待測文本分別輸入各個短模式子集或長模式子集對應的處理單元中；S5結合各個短模式子集和長模式子集的處理結果判斷待檢測文本中是否存在攻擊模式；S6重複步驟S4和S5，對待檢測快速網絡流傳送的數據流進行連續檢測。
2. 如權利要求1所述的基於模式聚類的並行網絡流特徵檢測方法，其特徵在於，所述步驟S3包括決定所述短模式子集的處理單元個數；利用模式聚類方法將長模式分割為多個長模式子集；決定所述長模式子集的處理單元個數。
3. 如權利要求1所述的基於模式聚類的並行網絡流特徵檢測方法，其特徵在於，所述步驟S4中若一個短模式子集或一個長模式子集被多個處理單元處理，那麼輸入的待檢測文本只需送入所述多個處理單元中的一個處理單元進行處理。
4. 如權利要求1所述的基於模式聚類的並行網絡流特徵檢測方法，其特徵在於，所述步驟S5還包括若存在攻擊模式，執行報警或阻斷操作。
5. —種基於模式聚類的並行網絡流特徵檢測系統，其特徵在於，包括選擇模式匹配算法模塊，用於選定模式的匹配算法集合，包括適用於短模式的匹配算法和適用於長模式的匹配算法；分割模式集模塊，用於根據所選定的適用於短模式和適用於長模式的匹配算法，選定模式的長度分割點，將模式集分割為短模式子集和長模式子集；決定處理單元個數模塊，用於決定處理短模式子集和長模式子集的處理單元個數；檢測文本模塊，用於複製待檢測文本為多份使其份數為所述短模式子集和長模式子集總份數，並將每份待測文本分別輸入各個短模式子集或長模式子集對應的處理單元中；判斷攻擊模式模塊，用於結合各個短模式子集和長模式子集的處理結果判斷待檢測文本中是否存在攻擊模式；重複執行模塊，用於重複步驟S4和S5，對待檢測快速網絡流傳送的數據流進行連續檢
6. 如權利要求5所述的基於模式聚類的並行網絡流特徵檢測系統，其特徵在於，所述決定處理單元個數模塊包括決定短模式處理單元個數模塊，用於決定短模式處理單元個數；長模式分割模塊，用於利用模式聚類方法將長模式分割為多個長模式子集；決定長模式處理單元個數模塊，用於決定所述長模式子集的處理單元個數。
7.如權利要求5所述的基於模式聚類的並行網絡流特徵檢測系統，其特徵在於，所述判斷攻擊模式模塊還包括執行報警或阻斷模塊，用於若存在攻擊模式時執行報警或阻斷操作。
全文摘要
本發明公開了一種基於模式聚類的並行網絡流特徵檢測方法，包括步驟選定模式的匹配算法集合，選定模式的長度分割點，將模式集分割為短模式子集和長模式子集；決定處理短模式子集和長模式子集的處理單元個數；複製待檢測文本的份數為長短模式子集總份數，並將每份待測文本分別輸入各個模式子集對應的處理單元中；結合各個模式子集的處理結果判斷待檢測文本中是否存在攻擊模式；重複上述步驟，對待檢測快速網絡流傳送的數據流進行連續檢測。該方法是一個可擴展的網絡流特徵檢測整體解決方案，能夠適用於各種等級性能需求以及各種規模的模式集，對於高性能內容檢測、入侵檢測、病毒防護和統一威脅管理、網絡信息監控等系統都具有極為深遠的作用。
文檔編號H04L12/26GK101719849SQ20091023708
公開日2010年6月2日 申請日期2009年11月3日 優先權日2009年11月3日
發明者徐波, 李軍, 薛一波 申請人:清華大學