[發明專利]一種多模式下匹配字符串的方法及系統

有效

• 申請號: 201210064914.5
• 申請日: 2012-03-13
• 公開（公告）號: CN103309882B
• 公開（公告）日: 2016-11-30
• 發明（設計）人: 許金鵬;薛萍;李健安;熊金芬;李旻翊
• 申請（專利權）人: 北京啟明星辰信息技術股份有限公司;北京啟明星辰信息安全技術有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京安信方達知識產權代理有限公司 11262
• 代理人: 栗若木;曲鵬

技術領域

本發明涉及互聯網技術領域，一種多模式下匹配字符串的方法及系統。

背景技術

字符串匹配算法在入侵檢測，短消息過濾，信息查詢等領域尤其是入侵檢測方面均有重要的應用。隨著網絡技術的發展和Internet的普及，網絡信息安全越來越受到人們的重視，現在社會是信息社會，保障信息的安全已成為刻不容緩的重要課題。

入侵檢測技術就是為保證信息系統的安全而設計的一種能夠及時發現并報告系統中未授權或者異常信息的技術，具有主動安全防范的特性，表現出良好的發展前景。而入侵檢測系統檢測引擎的核心即基于字符串匹配的特征匹配算法，這種檢測方法可以在主機或網絡數據中，通過準確的字符串模式匹配查找攻擊簽名，從而判斷是否出現入侵。隨著網絡攻擊技術的發展和攻擊的多樣化，如何改進字符串匹配算法，提高檢測效率，已成為入侵檢測系統研究的核心內容。

字符串匹配算法有很多，目前較常用的單模式字符串匹配算法是BM算法和KMP算法。應用廣泛的入侵檢測系統snort就采用了BM算法，但它是一種單模式的字符串匹配算法，在單一模式的字符串匹配算法中，BM算法一般被認為是性能最佳的。但在多模式字符串匹配過程中，BM算法需要對每一種模式分別進行匹配，因此BM算法的性能就大大降低了。目前的多模式匹配算法，比較高效的有CW算法，AC-BM算法，SBMP算法等。其中，CW算法的思路是首先用模式集構建一棵搜索樹，然后在文本中用搜索樹對模式進行跳躍搜索，在構建搜索樹時，將模式從右邊對齊，從右往左進行構建，樹上相同的分支節點進行合并。在進行搜索時，以搜索樹中模式的最短長度為匹配窗長度，文本從左往右匹配，在匹配窗內搜索樹從右往左進行匹配。如果在匹配過程中一旦出現不匹配，則整個匹配樹往右移動。匹配樹往右移動的位移表可以預先通過線性算法構建。AC-BM算法非常類似于CW算法，采用了“壞字符”和“好后綴”兩種啟發式規則來進行跳躍。SBMP算法也非常類似于CW算法，但只采用了“壞字符”啟發式規則來進行跳躍。

發明內容

本發明所要解決的技術問題是，提供一種多模式下匹配字符串的方法及系統，以解決提高字符串匹配效率的問題。

為了解決上述技術問題，本發明公開了一種多模式下匹配字符串的方法，包括：

存儲模式集信息，所述模式集信息至少包括各關鍵字的長度和其首字母序號；

當接收到字符串時，從所接收的字符串中提取出待匹配字，然后從所存儲的模式集信息中查找長度和首字母序號與所述待匹配字的長度和首字母序號均相同的關鍵字，將所查找到的關鍵字與待匹配字比較，若比較結果一致，則此待匹配字匹配成功，否則匹配失敗。

較佳地，上述方法中，通過一個數組存儲所述模式集信息，該用于存儲模式集信息的數組至少包括關鍵字長度、關鍵字首字母序號以及關鍵字在模式集中可容忍沖突數，其中，關鍵字在模式集中可容忍沖突數為模式集中關鍵字長度以及關鍵字首字母序號均相同的關鍵字總數，所述數組的值為關鍵字在模式集中的位置序號。

較佳地，上述方法中，從所存儲的模式集信息中查找關鍵字長度和關鍵字首字母序號與所述待匹配字的長度和首字母序號均相同的關鍵字為多個時，將所查找到的多個關鍵字依次與待匹配字進行比較。

較佳地，上述方法中，從所存儲的模式集信息中查找長度和首字母序號與所述待匹配字的長度和首字母序號均相同的關鍵字，將所查找到的關鍵字與待匹配字比較的過程如下：

獲取所述待匹配字的長度L及其首字母序號M，從用于存儲模式集信息的數組中查找長度為L，首字母序號M、可容忍沖突數的值為0的數組元素，比較將所查找到的數組元素對應的關鍵字與所述待匹配字是否一致，若比較結果一致，則匹配成功，若比較結果不一致，則更新數組元素的可容忍沖突數再從用于存儲模式集信息的數組中查找長度為L，首字母序號M、可容忍沖突數為更新值的數組元素，比較所查找到的數組元素對應的關鍵字與所述待匹配字是否一致，其中，所述數組元素的可容忍沖突數的更新值為上一個所要查找的數組元素的可容忍沖突數的值加1。

較佳地，上述方法中，更新所要查找的數組元素時，若更新操作次數達到設定次數時，所提取出的關鍵字與所述待匹配字仍不一致時，結束本方法的操作。

本發明還公開了一種多模式下匹配字符串的系統，包括：

存儲單元，存儲模式集信息，所述模式集信息至少包括各關鍵字的長度和其首字母序號；