基於ac自動機和後綴樹的字符串匹配方法
2023-10-21 05:34:12 1
專利名稱：基於ac自動機和後綴樹的字符串匹配方法
技術領域：
本發明涉及網絡過濾和監控技術領域，特別涉及一種基於AC自動機和後綴樹的字符串匹配方法。
背景技術：
隨著網絡安全要求的不斷提高，入侵檢測、防病毒、內容過濾等功能正越來越多地應用於網絡安全設備中。而字符串匹配算法則是支撐這些功能的核心算法，也決定了網絡安全設備的性能。目前最廣泛應用於網絡安全設備的字符串匹配算法是Aho-Corasick(AC)自動機算法，AC算法是一種基於自動機原理的字符串匹配算法，如圖1所示，其基本工作原理為首先將特徵字符串(如病毒特徵庫、過濾關鍵字等)編譯成自動機，從狀態O開始，逐 字讀入待匹配內容，每次讀入一個字符(例如a)時，檢查當前狀態是否有對應字符的跳轉箭頭，若有，則跳到此跳轉對應的下一狀態，若沒有，則跳回到狀態O。有一些狀態被標記為匹配狀態，如果進入這個狀態代表匹配成功。針對特徵字符串可能分散於多個數據包的情況，目前業界普遍採用的是緩存數據包和重組數據包之後再進行字符串匹配，從而提升了網絡安全設備的內存使用量。然而緩存數據包和重組數據包存在以下缺點首先，緩存數據包會使網絡延遲變大；其次，在千兆級以上的高速網絡中重組數據包需要大量的內存，容易使網絡安全設備出現內存耗盡的情況；再次，在具備高速緩衝存儲器的網絡安全設備中，在內存中大量讀寫數據包數據還會使高速緩衝存儲器的局部性降低，從而降低網絡安全設備的性能。
發明內容
(一)解決的技術問題本發明解決的技術問題是提出一種無需重組數據包就可以檢測出跨包內容的字符串匹配方法。(二)技術方案本發明提出了一種基於AC自動機和後綴樹的字符串匹配方法，所述方法包括S1、將特徵字符串編譯成AC自動機；S2、將特徵子符串的後綴集合編譯成後綴樹；S3、每當有一個數據包進入網絡安全設備時，根據所述AC自動機對所述數據包進行匹配，並利用所述後綴樹保存匹配狀態；S4、若匹配成功，則丟棄所述數據包。優選地，當所述數據包按序進入時，則步驟S3具體包括S31、當接收到當前按序數據包時，搜索所述當前按序數據包的前一個數據包的記錄是否存在；S32、根據所述當前按序數據包的前一個數據包的記錄是否存在判定所述當前按序數據包的狀態編號；
S33、根據所述AC自動機，從所述當前按序數據包的狀態編號開始對所述當前按序數據包進行匹配。
優選地，步驟S32具體包括
若所述當前按序數據包的前一個數據包的記錄存在，則將所述當前按序數據包的前一個數據包的狀態編號作為所述當前按序數據包的狀態編號；
若所述當前按序數據包的前一個數據包的記錄不存在，則所述當前按序數據包的狀態編號為O。
優選地，當所述數據包亂序進入時，則步驟S3具體包括
S31』、在接收當前亂序數據包之前，搜索所述當前亂序數據包的後一個數據包的後綴樹記錄是否存在，並檢測所述當前亂序數據包的後一個數據包的頭部是否為所述後綴樹中的Iv後綴；
S32』、若所述當前亂序數據包的後一個數據包的後綴樹記錄存在，且檢測到所述當前亂序數據包的後一個數據包的頭部是所述後綴樹中的一個後綴時，則保存所述後綴樹在所述後綴上的後綴樹編號；
S33』、當接收到所述當前亂序數據包時，對所述後綴樹在所述後綴上的後綴樹編號上進行回溯；
S34』、將回溯得到的後綴添加到所述當前亂序數據包的尾部，根據所述AC自動機對重組後的所述當前亂序數據包進行匹配。
優選地，所述步驟S31』還包括搜索所述當前亂序數據包的前一個數據包的後綴樹記錄是否存在
若所述當前亂序數據包的前一個數據包的後綴樹記錄存在，且所述當前亂序數據包的前一個數據包為所述後綴的一部分，則所述當前亂序數據包的後綴樹編號為所述當前亂序數據包的前一個數據包的後綴樹編號；
若所述當前亂序數據包的前一個數據包的後綴樹記錄存在，且所述當前亂序數據包的前一個數據包不是所述後綴的一部分，則所述當前亂序數據包的後綴樹編號為所述當前亂序數據包的前一個數據包的後綴樹編號。
優選地，所述步驟S32』中所述若所述當前亂序數據包的後一個數據包的後綴樹記錄存在，且檢測所述當前亂序數據包的後一個數據包不是後綴的一部分，則將所述當前亂序數據包的後一個數據包重組到所述當前亂序數據包進行匹配，且重組後的當前亂序數據包的狀態編號為所述當前亂序數據包的後一個數據包的狀態編號。
(三)有益效果
本發明在對數據包字符串進行匹配時保存狀態機的狀態編號，使得數據包在順序到達時能夠繼續上一次的狀態進行匹配，擺脫了緩存造成的延遲加大內存消耗加大、內存消耗加大和高速緩衝存儲器局部性降低的缺點，可以降低網絡安全設備所需資源，提升其性能。
圖1是AC自動機示意圖2是本發明提出的方法流程圖3是本發明中特徵字符串abcde的後綴樹不意圖。
具體實施例方式下面將結合本發明實施例中的附圖，對本發明實施例中的技術方案進行清楚、完整地描述。本發明提出了一種基於AC自動機和後綴樹的字符串匹配方法，是對AC算法的改進，通過記錄自動機的狀態編號來代替緩存整個數據包的內容，該方法同時能夠用於AC算法的衍生算法AC-Optimized、Cl-AC等算法中，該方法的流程圖如圖2所示，所述方法包括S1、將特徵字符串編譯成AC自動機；S2、將特徵子符串的後綴集合編譯成後綴樹； S3、每當有一個數據包進入網絡安全設備時，根據所述AC自動機對所述數據包進行匹配，並利用所述後綴樹保存匹配狀態；S4、若匹配成功，則丟棄所述數據包。當所述數據包按序進入時，則步驟S3具體包括S31、當接收到當前按序數據包時，搜索所述當前按序數據包的前一個數據包的記錄是否存在；S32、根據所述當前按序數據包的前一個數據包的記錄是否存在判定所述當前按序數據包的狀態編號；S33、根據所述AC自動機，從所述當前按序數據包的狀態編號開始對所述當前按序數據包進行匹配。步驟S32具體包括若所述當前按序數據包的前一個數據包的記錄存在，則將所述當前按序數據包的前一個數據包的狀態編號作為所述當前按序數據包的狀態編號；若所述當前按序數據包的前一個數據包的記錄不存在，則所述當前按序數據包的狀態編號為O。當所述數據包亂序進入時，則步驟S3具體包括S31』、在接收當前亂序數據包之前，搜索所述當前亂序數據包的後一個數據包的後綴樹記錄是否存在，並檢測所述當前亂序數據包的後一個數據包的頭部是否為所述後綴樹中的Iv後綴；S32』、若所述當前亂序數據包的後一個數據包的後綴樹記錄存在，且檢測到所述當前亂序數據包的後一個數據包的頭部是所述後綴樹中的一個後綴時，則保存所述後綴樹在所述後綴上的後綴樹編號；S33』、當接收到所述當前亂序數據包時，對所述後綴樹在所述後綴上的後綴樹編號上進行回溯；S34』、將回溯得到的後綴添加到所述當前亂序數據包的尾部，根據所述AC自動機對重組後的所述當前亂序數據包進行匹配。所述步驟S31』還包括搜索所述當前亂序數據包的前一個數據包的後綴樹記錄是否存在
若所述當前亂序數據包的前一個數據包的後綴樹記錄存在，且所述當前亂序數據包的前一個數據包為所述後綴的一部分，則所述當前亂序數據包的後綴樹編號為所述當前亂序數據包的前一個數據包的後綴樹編號；
若所述當前亂序數據包的前一個數據包的後綴樹記錄存在，且所述當前亂序數據包的前一個數據包不是所述後綴的一部分，則所述當前亂序數據包的後綴樹編號為所述當前亂序數據包的前一個數據包的後綴樹編號。
所述步驟S32』中所述若所述當前亂序數據包的後一個數據包的後綴樹記錄存在， 且檢測所述當前亂序數據包的後一個數據包不是後綴的一部分，則將所述當前亂序數據包的後一個數據包重組到所述當前亂序數據包進行匹配，且重組後的當前亂序數據包的狀態編號為所述當前亂序數據包的後一個數據包的狀態編號。
本實施例假設特徵字符串為abcde，則特徵字符串abcde的後綴集合為 {bcde, cde, de, e},特徵字符串abcde的後綴樹示意圖如圖3所示。
對於本發明提出的基於AC自動機和後綴樹的字符串匹配方法中的數據結構為
其中，AC自動機狀態的數據結構為
typedef struct {uint_32 NextStatef ALPHABET—SIZE ];."下一步狀態 uint—32 F ailState; //無匹配情況下的下一個狀態 AC PATTERN *MatchList; //匹配成功的特徵字符串指針}AC NODE;
後綴樹狀態的數據結構為
typedef struct { uint—32 Next:State[ALPHABET—SIZE ]; //下一步狀態 uint 32 PreState;Il此節點的父節點uchar PreChar;Il從父節點到此節點的對應字符} PSTN0DE;
用於保存亂序信息的記錄表Buffer中的條目數據結構為
typedef struct _bufStmct{ uint_32 fid //根據五元組生成的流的唯一 ID uint_32 seq; //此數據包在流中的序列號 uint—32 Ien //數據包長度 uint—32 Si; //AC自動機狀態編號 uint—32 s2 //後綴樹狀態編號
uint—32 fact; //表不整個包是一個後綴的一部分 bufStruct* Next; //用於解決Hash碰撞的指針
)
} BUFFER—STRUCT; 本發明提出的基於AC自動機和後綴樹的字符串匹配方法的偽代碼如下表1:
權利要求
1.一種基於AC自動機和後綴樹的字符串匹配方法，其特徵在於，所述方法包括 51、將特徵字符串編譯成AC自動機； 52、將特徵子符串的後綴集合編譯成後綴樹； 53、每當有一個數據包進入網絡安全設備時，根據所述AC自動機對所述數據包進行匹配，並利用所述後綴樹保存匹配狀態； 54、若匹配成功，則丟棄所述數據包。
2.根據權利要求1所述的方法，其特徵在於，當所述數據包按序進入時，則步驟S3具體包括 531、當接收到當前按序數據包時，搜索所述當前按序數據包的前一個數據包的記錄是否存在； 532、根據所述當前按序數據包的前一個數據包的記錄是否存在判定所述當前按序數據包的狀態編號； 533、根據所述AC自動機，從所述當前按序數據包的狀態編號開始對所述當前按序數據包進行匹配。
3.根據權利要求2所述的方法，其特徵在於，步驟S32具體包括 若所述當前按序數據包的前一個數據包的記錄存在，則將所述當前按序數據包的前一個數據包的狀態編號作為所述當前按序數據包的狀態編號； 若所述當前按序數據包的前一個數據包的記錄不存在，則所述當前按序數據包的狀態編號為O。
4.根據權利要求1所述的方法，其特徵在於，當所述數據包亂序進入時，則步驟S3具體包括 S31』、在接收當前亂序數據包之前,搜索所述當前亂序數據包的後一個數據包的後綴樹記錄是否存在，並檢測所述當前亂序數據包的後一個數據包的頭部是否為所述後綴樹中的一個後綴； S32』、若所述當前亂序數據包的後一個數據包的後綴樹記錄存在，且檢測到所述當前亂序數據包的後一個數據包的頭部是所述後綴樹中的一個後綴時，則保存所述後綴樹在所述後綴上的後綴樹編號； S33』、當接收到所述當前亂序數據包時，對所述後綴樹在所述後綴上的後綴樹編號上進行回溯； S34』、將回溯得到的後綴添加到所述當前亂序數據包的尾部，根據所述AC自動機對重組後的所述當前亂序數據包進行匹配。
5.根據權利要求4所述的方法，其特徵在於，所述步驟S31』還包括搜索所述當前亂序數據包的前一個數據包的後綴樹記錄是否存在 若所述當前亂序數據包的前一個數據包的後綴樹記錄存在，且所述當前亂序數據包的前一個數據包為所述後綴的一部分，則所述當前亂序數據包的後綴樹編號為所述當前亂序數據包的前一個數據包的後綴樹編號； 若所述當前亂序數據包的前一個數據包的後綴樹記錄存在，且所述當前亂序數據包的前一個數據包不是所述後綴的一部分，則所述當前亂序數據包的後綴樹編號為所述當前亂序數據包的前一個數據包的後綴樹編號。
6.根據權利要求4所述的方法，其特徵在於，所述步驟S32』中所述若所述當前亂序數據包的後一個數據包的後綴樹記錄存在，且檢測所述當前亂序數據包的後一個數據包不是後綴的一部分，則將所述當前亂序數據包的後一個數據包重組到所述當前亂序數據包進行匹配，且重組後的當前亂序數據包的狀態編號為所述當前亂序數據包的後一個數據包的狀態編號。
全文摘要
本發明提供一種基於AC自動機和後綴樹的字符串匹配方法，所述方法包括S1.將特徵字符串編譯成AC自動機；S2.將特徵字符串的後綴集合編譯成後綴樹；S3.每當有一個數據包進入網絡安全設備時，根據所述AC自動機對所述數據包進行匹配，並利用所述後綴樹保存匹配狀態；S4.若匹配成功，則丟棄所述數據包。本發明在對數據包字符串進行匹配時保存AC狀態機和後綴樹的狀態編號，使得數據包即使在亂序到達時也能夠繼續上一次的狀態進行匹配，而不用緩存之前的數據包。擺脫了緩存造成的延遲加大內存消耗加大、內存消耗加大和高速緩衝存儲器局部性降低的缺點，可以降低網絡安全設備所需資源，提升其性能。
文檔編號H04L29/06GK103023883SQ20121048842
公開日2013年4月3日 申請日期2012年11月26日 優先權日2012年11月26日
發明者陳新明, 李軍 申請人:清華大學