[發明專利]一種亂序數據包流免重組多模式匹配方法

有效

• 申請號: 201210045060.6
• 申請日: 2012-02-24
• 公開（公告）號: CN102685098A
• 公開（公告）日: 2012-09-19
• 發明（設計）人: 齊德昱;林偉偉;李劍
• 申請（專利權）人: 華南理工大學
• 主分類號: H04L29/06
• 分類號: H04L29/06;H04L12/56
• 代理公司: 廣州市華學知識產權代理有限公司 44245
• 代理人: 楊曉松

1.一種亂序數據包流免重組多模式匹配方法，其特征在于，包括以下步驟：

S1：采用KMP算法對模式進行了預處理；

S2：在對模式進行了預處理后，對亂序數據包首尾的邊緣字節進行掃描；

S3：利用區間樹保存特征碼片斷并進行模式匹配。

2.根據權利要求1所述的亂序數據包流免重組多模式匹配方法，其特征在于，步驟S1中，所述預處理為檢測數據包首位兩端是否存在特征碼片段，并針對數據包前端部分和后端部分分別進行預處理，其具體步驟如下：

S11：掃描數據包前端部分時需要從右往左；

S12：掃描末端部分時則相反，即從左往右。

3.根據權利要求1所述的亂序數據包流免重組多模式匹配方法，其特征在于，所述步驟S2掃描邊緣字節包括下述具體步驟：

S21：針對數據包前端部分進行掃描時，掃描的長度為模式長度-1，從右往左掃描，當掃描到數據包第一個字母且此時模式的已匹配數不為0，那么就代表發現了特征碼的片斷，并馬上利用區間樹把特征碼的類型和長度記錄下來；

S22：針對數據包的末端部分進行掃描時，要掃描的部分就是MWM算法沒有處理的末端部分；當掃描到數據包的最后一個字母且此時模式的已匹配數不為0，那么就利用區間樹把特征碼的類型和長度記錄下來。

4.根據權利要求1所述的亂序數據包流免重組多模式匹配方法，其特征在于，步驟S3中，所述區間樹是一種二叉搜索樹，它將一個區間劃分成一些單元區間，每個單元區間對應線段樹中的一個葉結點；區間樹的每一個節點都是代表一段區間，并且針對具體的情況為每一區間加上參數；所述區間樹用于保存數據包可能含有的病毒特征碼片斷的信息，在插入操作時，根據數據包對應的區間的范圍和它所屬的TCP流插入到對應的區間樹里面。

5.根據權利要求1所述的亂序數據包流免重組多模式匹配方法，其特征在于，所述步驟S3包括下述具體步驟：

S31：在實際的掃描中為每一個TCP連接建立一個區間樹，用數據包包頭的段號作為一個區間樹的區間邊界，并為每一個結點的左右區間邊界加入一個參數S，這個參數S用來記錄掃描出來的特征碼片斷的長度；

S32：在掃描完一個數據包，就根據數據包對應的段號的范圍和它所屬的TCP流插入到對應的區間樹里面，并記錄參數S；

S33：比較數據包特征碼片段的長度相加的結果與病毒特征碼的長度，如果相等，則表示該TCP流有病毒，發出警報，如果數據包特征碼片段的長度相加的結果與病毒特征碼的長度不相等，則不做任何提示；

S34：為了減少內存的消耗，設定一個時間限制，每隔一定時間，就釋放區間樹一部分結點；如果該TCP中沒有發現病毒特征碼，就釋放該TCP流的所有空間。

6.根據權利要求5所述的亂序數據包流免重組多模式匹配方法，其特征在于，步驟S32中，進一步包括把相鄰區間的邊界參數S也標志上。