一種生成特徵碼確定狀態機的方法和裝置的製作方法
2023-06-03 02:35:06 2
專利名稱：一種生成特徵碼確定狀態機的方法和裝置的製作方法
技術領域：
本發明涉及網絡安全技術領域，特別是涉及一種生成特徵碼確定狀態機的方法和裝置。
背景技術：
為了保證計算機或網絡安全，通常需要檢查文件或報文中是否存在妨害安全的信息，比如病毒、攻擊程序等。由於這些病毒或攻擊程序一般具有某種特徵碼，所以在檢查文件或報文時，特徵碼就常常作為被檢查的對象。如果檢查出文件或報文中存在某種特徵碼，則可以認為該文件或報文有妨害安全的信息。
特徵碼一般用正則表達式(Regular Expression)的形式進行描述。由於正則表達式可以表示字符串輸入狀態的情況，所以通常又將正則表達式編譯為確定狀態機(DFA，Deterministic Finite Automation)的形式。其中，DFA中的一個狀態可以表示字符串輸入過程的一個狀態，DFA的狀態數則可以表示字符串輸入過程中所存在的狀態數。另外，DFA佔用存儲空間的大小與狀態數呈正比關係，即狀態數越多，DFA佔用存儲空間也越多。
正則表達式編譯為DFA之後，就可以將文件或報文中的字符串作為輸入字符串，利用DFA對輸入的字符串的狀態進行匹配，如果匹配成功，則確定輸入字符串中存在特徵碼，從而實現特徵碼的匹配。
實際應用中，不同的病毒或攻擊程序存在不同的特徵碼。如果為每一個特徵碼單獨編譯一個DFA，在檢查某文件或報文時，由於不清楚該文件或報文是否存在妨害安全信息的特徵碼，也不清楚存在哪種特徵碼，就需要利用多個DFA依次對文件或報文進行檢查，其查找速度非常緩慢。
為了提高查找特徵碼的速度，可以將多個特徵碼對應的正則表達式進行分組，並分別將每一個分組的正則表達式進行合併編譯，生成對應的DFA。這樣，在利用某一個DFA檢查文件或報文時，就可以對多個特徵碼同時進行匹配，從而提高查找速度。
在生成DFA的過程中，現有技術一般是將正則表達式隨機進行分組，再對每一個分組分別進行編譯。在這種方式下，如果分組不合理可能會導致生成的DFA的狀態數過多，佔用內存過多的現象。比如，某正則表達式為/ALTER\s.* FILE\s+((AS|MEMBER|TO)\s+) (\x27[^\x27]{512})/smi；另一達式為/ALTER\s.* FILE\s+((AS|MEMBER |TO)\s+) (\x22[^\x22]{512})/smi。如果將這兩個正則表達式合併編譯為同一個DFA，編譯後將產生3.67M個狀態數，生成的DFA將佔用3.67G字節的內存。但如果將兩條正則表達式單獨進行編譯，每一條正則表達式僅生成8.6K個狀態數，佔用8.6M字節的內存。
可見，由於在生成DFA過程中分組不合理，多個正則表達式編譯後產生的狀態數可能比正則表達式單獨編譯後總的狀態數多得多，增加了佔用內存的容量，不利於實現特徵碼的匹配工作。
發明內容
有鑑於此，本發明的第一個發明目的在於提供一種生成特徵碼確定狀態機的方法，可以保證分組的合理性，避免合併編譯生成的確定狀態機產生大量的狀態，佔用過多的存儲空間。
本發明的第二個發明目的是提供一種生成特徵碼確定狀態機的裝置，可以保證分組的合理性，避免合併編譯生成的確定狀態機產生大量的狀態，佔用過多的存儲空間。
為了達到上述第一個發明目的，本發明提出的技術方案為一種生成特徵碼確定狀態機的方法，該方法包括以下步驟a、將第一條特徵碼對應的正則表達式作為當前表達式；
b、判斷是否存在未與當前表達式合併編譯過的未處理分組，如果有，則將未處理分組中的一個作為當前未處理分組，執行步驟c；否則，將當前表達式加入新建的分組中並單獨編譯生成確定狀態機DFA，執行步驟d；c、將當前表達式與當前未處理分組進行合併編譯，如果合併編譯獲得的狀態數不大於當前表達式與當前未處理分組單獨編譯的狀態數之和，則將當前表達式加入當前未處理分組中，將合併編譯的結果作為生成的DFA，再執行步驟d；否則，返回步驟b；d、將下一條特徵碼對應的正則表達式作為當前表達式，返回步驟b，直至處理完所有特徵碼對應的正則表達式。
上述方案中，步驟b所述將當前表達式加入新建的分組中並單獨編譯生成DFA之後，步驟b進一步包括保存單獨編譯後獲得的狀態數；步驟c所述當前未處理分組單獨編譯的狀態數為事先保存的狀態數。
上述方案中，所述步驟c包括c1、將當前表達式進行單獨編譯，獲得當前表達式單獨編譯的狀態數；c2、將當前表達式與當前未處理分組進行合併編譯，並在合併編譯的過程中，實時判斷當前合併編譯所獲得的狀態數是否大於當前表達式單獨編譯的狀態數與保存的當前未處理分組的狀態數之和，如果大於，則將當前未處理分組作為已處理分組，並返回步驟b；c3、將當前表達式加入當前未處理分組中，將合併編譯的結果作為生成的DFA，將合併編譯後獲得的狀態數作為當前未處理分組的狀態數進行保存，再將當前未處理分組作為已處理分組，並執行步驟d。
上述方案中，事先設置用於記錄合併編譯過程所產生狀態數的計數變量，並將初始值設置為0，步驟c2所述將當前表達式與當前未處理分組進行合併編譯的過程中進一步包括每編譯完一個狀態，所述計數變量加1；步驟c2所述判斷當前合併編譯所獲得的狀態數是否大於當前表達式單獨編譯的狀態數與保存的當前未處理分組的狀態數之和的方法為判斷所述計數變量的值是否大於當前表達式單獨編譯的狀態數與保存的當前未處理分組的狀態數之和。
上述方案中，所述步驟d之後，如果分組個數大於事先設置的值，則該方法進一步包括x1、將所有分組中任意兩個分組進行合併編譯，獲得任意兩個分組合併編譯後的狀態數；x2、將最小的狀態數所對應的兩個分組合併為一個分組，並生成DFA；x3、判斷當前分組個數是否大於事先設置的值，如果大於，則返回步驟x1；否則，退出本流程。
本發明的另一發明目的是這樣實現的一種生成特徵碼確定狀態機的裝置，該裝置包括表達式存儲模塊，用於保存特徵碼對應的正則表達式；表達式選取模塊，用於從表達式存儲模塊中選取一條表達式作為當前表達式；分組存儲模塊，用於保存所有分組經過編譯後生成的確定狀態機DFA；分組選取模塊，用於根據判別模塊的通知從分組存儲模塊中選取一個未處理分組作為當前未處理分組；判別模塊，用於判斷分組存儲模塊中是否存在未與表達式選取模塊中的當前表達式合併編譯過的分組，如果有，則通知分組選取模塊選取當前未處理分組，並通知編譯模塊對當前表達式與當前未處理分組進行合併編譯；否則，通知編譯模塊對當前表達式進行單獨編譯；還用於根據編譯模塊返回的編譯成功信息通知表達式選取模塊選取下一條表達式，直至處理完所有特徵碼對應的正則表達式；編譯模塊，用於根據判別模塊的通知，將表達式選取模塊中的當前表達式和分組選取模塊中的當前未處理分組進行合併編譯，如果合併編譯獲得的狀態數不大於當前表達式與當前未處理分組單獨編譯的狀態數之和，則將當前表達式加入當前未處理分組中，將合併編譯的結果作為生成的DFA保存在分組存儲模塊中，並向判別模塊返回編譯成功信息；否則，向判別模塊返回編譯失敗信息；還用於根據判別模塊的通知，對當前表達式進行單獨編譯，將當前表達式加入新建的分組中，將單獨編譯的結果作為生成的DFA保存在分組存儲模塊中，並向判別模塊返回編譯成功信息。
上述方案中，所述編譯模塊包括編譯控制模塊，用於根據判別模塊發送的進行合併編譯的通知，控制編譯執行模塊進行合併編譯，在接收到來自編譯執行模塊的編譯結束信號時向判別模塊返回編譯成功信息，在接收到來自狀態數判別模塊的超值觸發信號時向判別模塊返回編譯失敗信息；還用於根據判別模塊發送的進行單獨編譯的通知，控制編譯執行模塊進行單獨編譯，並在接收到來自編譯執行模塊的編譯結束信號時向判別模塊返回編譯成功信息；編譯執行模塊，用於在編譯控制模塊的控制下，將表達式選取模塊中的當前表達式經過單獨編譯後獲得的狀態數輸出給單獨編譯狀態數存儲模塊保存；將表達式選取模塊中的當前表達式和分組選取模塊中的當前未處理分組進行合併編譯，將合併編譯過程中獲得的狀態數實時輸出給狀態數判別模塊，並在合併編譯結束時向編譯控制模塊返回編譯結束信號，並將編譯結果作為生成的DFA輸出給分組存儲模塊保存；還用於在編譯控制模塊的控制下，將表達式選取模塊中的當前表達式進行單獨編譯，並在單獨編譯結束時向編譯控制模塊返回編譯結束信號，並將編譯結果作為生成的DFA輸出給分組存儲模塊；單獨編譯狀態數存儲模塊，用於保存編譯執行模塊輸出的單獨編譯當前表達式所獲得的狀態數；分組狀態數存儲模塊，用於保存來自分組選取模塊中當前未處理分組的狀態數；狀態數判別模塊，用於實時判斷來自編譯執行模塊的狀態數是否大於單獨編譯狀態數存儲模塊和分組狀態數存儲模塊中所保存的狀態數之和，如果大於，則向編譯控制模塊發送超值觸發信號。
上述方案中，該裝置進一步包括合併判別模塊，用於判斷分組存儲模塊中分組的個數是否大於事先設置的值，如果大於，則通知合併模塊進行合併處理，直至分組存儲模塊中分組的個數小於或等於事先設置的值；合併模塊，用於將分組存儲模塊中任意兩個分組進行合併編譯，將合併編譯後最小的狀態數所對應的兩個分組合併為一個分組，並將合併分組生成的DFA保存在分組存儲模塊中。
綜上所述，本發明提出的一種生成特徵碼確定狀態機的方法和裝置，由於在將特徵碼對應的正則表達式加入分組前，需要判斷正則表達式和分組的合併編譯產生的狀態數是否大於單獨編譯產生的狀態數，並只有在不大於的情況下，才將正則表達式加入分組生成DFA，從而保證分組的合理性，避免了合併編譯後生成的DFA產生大量的狀態數，佔用過多的存儲空間。
圖1是本發明的流程圖；圖2是應用本發明方案的方法實施例的流程圖；圖3是應用本發明方案的裝置實施例一的基本結構示意圖；圖4是裝置實施例一中編譯執行模塊的內部結構示意圖；圖5是應用本發明方案的裝置實施例二的基本結構示意圖。
具體實施例方式
為使本發明的目的、技術方案和優點更加清楚，下面將結合附圖及具體實施例對本發明作進一步地詳細描述。
圖1是本發明生成特徵碼確定狀態機的流程圖。如圖1所示，該方法可以包括步驟101將第一條特徵碼對應的正則表達式作為當前表達式。
步驟102～104判斷是否存在未與當前表達式合併編譯過的未處理分組，如果有，則將未處理分組中的一個作為當前未處理分組，執行步驟105；否則，將當前表達式加入新建的分組中並單獨編譯生成DFA，執行步驟108。
這裡所述的單獨編譯和合併編譯都可以採用現有的軟體工具來實現，比如FLEX軟體等。當然，應用本發明方案的用戶還可以採用其它軟體編譯或自行編譯，此處不再贅述。
另外，當前表達式可能需要與多個分組依次進行合併編譯，才能確定應該加入哪一個分組。這裡，為了區分是否進行了合併編譯，可以將未與當前表達式合併編譯過的分組稱為未處理分組，將已經與當前表達式合併編譯過的分組稱為已處理分組。
步驟105將當前表達式與當前未處理分組進行合併編譯。
步驟106～107判斷合併編譯獲得的狀態數是否不大於當前表達式與當前未處理分組單獨編譯的狀態數之和，如果是，則將當前表達式加入當前未處理分組中，將合併編譯的結果作為生成的DFA，再執行步驟108；否則，返回步驟102。
為了保證正則表達式分組合理，在將當前表達式加入某個分組時，需要判斷加入該分組後是否發生「爆炸」，即當前表達式與要加入的分組合併編譯之後的狀態數是否大於單獨編譯的狀態數之和。如果發生「爆炸」，則說明分組不合理，當前表達式不應該加入該分組中；如果沒有發生「爆炸」，則說明分組是合理的，當前表達式可以加入該分組中。
實際應用中，可以在合併編譯結束之後，再判斷合併編譯所獲得的狀態數是否大於單獨編譯的狀態數之和；也可以在合併編譯的過程中，實時判斷合併編譯所獲得的狀態數是否大於單獨編譯的狀態數之和。
可以實時判斷的原因在於在合併編譯的過程中，每當將特徵碼對應正則表達式表示的一個字符串輸入狀態編譯為DFA可以表示的一個狀態後，其狀態數就可以加1。所以，在編譯的過程中，如果用某個變量對產生狀態的數量進行計數，就可以明確當前的狀態數是否大於當前表達式和當前未處理分組單獨編譯的狀態數之和。
當然，如果在合併編譯的過程中，實時判斷合併編譯所獲得的狀態數是否大於單獨編譯的狀態數之和，還需要在判斷之前明確當前表達式和當前未處理分組進行單獨編譯的狀態數之和。
其中，確定當前表達式進行單獨編譯的狀態數比較容易，只需要在步驟105執行合併編譯之前，將當前表達式進行單獨編譯就可獲得當前表達式的狀態數。而確定當前未處理分組的狀態數則需要在新建一個分組時，將加入該分組中的正則表達式進行單獨編譯，並將獲得的狀態數作為新建分組的狀態數進行保存。此後，就可以直接利用保存的分組的狀態數，無需再次進行編譯。在進行實時判斷的情況下，步驟105～步驟107又可以具體為c1、將當前表達式進行單獨編譯，獲得當前表達式單獨編譯的狀態數。
c2、將當前表達式與當前未處理分組進行合併編譯，並在合併編譯的過程中，實時判斷當前合併編譯所獲得的狀態數是否大於當前表達式單獨編譯的狀態數與保存的當前未處理分組的狀態數之和，如果大於，則將當前未處理分組作為已處理分組，並返回步驟102；c3、將當前表達式加入當前未處理分組中，將合併編譯的結果作為生成的DFA，將合併編譯後獲得的狀態數作為當前未處理分組的狀態數進行保存，再將當前未處理分組作為已處理分組，執行步驟108。
步驟108將下一條特徵碼對應的正則表達式作為當前表達式，返回步驟102，直至處理完所有特徵碼的正則表達式。
這樣，就可以將所有特徵碼的正則表達式合理地進行分組，以保證每一個分組產生的DFA不會又過多的狀態，也就不會佔用過多的存儲空間。
為了更好地說明本發明方案，下面用一個較佳實施例進行詳細描述。
本實施例中，為了區分是否與當前正則表達式進行過合併編譯，可以為每一個分組依次編號，當前未處理分組的組號用current_group表示，分組總個數用group_number表示，group_number的初始值為0。
圖2是本實施例的流程圖。如圖2所示，本實施例可以包括步驟201將第一條特徵碼對應的正則表達式作為當前表達式。
步驟202將current_group的值設置為0。
步驟203將當前表達式進行單獨編譯，獲得單獨編譯的狀態數。
步驟204判斷current_group的值是否小於group_number的值，如果是，則執行步驟205；否則，執行步驟210。
這裡，如果current_group的值小於group_number，則可以確定還存在未與當前表達式進行合併編譯的分組。
步驟205當前表達式與current_group對應的分組進行合併編譯。
步驟206～步驟207判斷合併編譯過程中獲得的狀態數是否大於當前表達式單獨編譯的狀態數與current_group對應分組的狀態數之和，如果大於，則將current_group加1，再執行步驟204；否則，執行步驟208。
這裡，將current_group加1可以表示將current_group對應的分組作為已處理分組，而將下一個分組，即current_group+1對應的分組作為當前未處理分組。
步驟208判斷合併編譯是否結束，如果結束，則執行步驟209；否則，返回步驟205繼續進行合併編譯。
這裡，步驟205～步驟208為一個循環過程，即當前表達式和current_group對應的分組實現合併編譯的過程。但需要注意的是，這裡並不是合併編譯完成之後才判斷合併編譯過程中獲得的狀態數是否大於單獨編譯的狀態數，而是在合併編譯的過程中進行實時判斷。
為了在合併編譯過程中實時判斷，可以事先設置用於記錄合併編譯過程所產生狀態數的計數變量，並將初始值設置為0。在合併編譯的過程中，如果每編譯完一個狀態，就將所述計數變量加1，計數變量的值就可以表示合併編譯過程中所獲得的狀態數。那麼，在步驟206進行實時判斷時，就可以直接判斷計數變量的值是否大於當前表達式單獨編譯的狀態數與保存的當前未處理分組的狀態數之和。
步驟209將當前表達式加入current_group對應的分組中，將合併編譯的結果作為生成的DFA，並將合併編譯後獲得的狀態數作為current_group對應分組的狀態數進行保存，再執行步驟212。
步驟210新建一個分組，將當前表達式加入新建分組中單獨編譯生成DFA，並將單獨編譯後獲得的狀態數作為新建分組的狀態數。
步驟211將group_number的值加1。
步驟212～步驟213判斷是否處理完所有的特徵碼對應的正則表達式，如果是，則退出本流程；否則，將下一條特徵碼對應的正則表達式作為當前表達式，並執行步驟202。
另外，實際應用中，不管採用哪種方法生成特徵碼的DFA，如果分組太多都可能會導致在文件或報文中查找特徵碼的效率降低。在這種情況下，可以事先設置分組個數的最大值，如果實際分組個數大於這個預先設置的值，就可以進一步將分組進行合併。具體實現方式可以為x1、將所有分組中任意兩個分組進行合併編譯，獲得任意兩個分組合併編譯後的狀態數。
x2、將最小的狀態數所對應的兩個分組合併為一個分組，並生成DFA。
這裡所述的將兩個分組合併為一個分組就是指將兩個分組中所有的正則表達式進行合併編譯。
x3、判斷當前分組個數是否大於事先設置的值，如果大於，則返回步驟x1；否則，退出本流程。
也就是說，通過合併分組，可以將分組的個數按照實際情況控制在一定範圍內。這樣，既可以保持分組的合理性，不佔用過多的存儲空間，又可以避免分組過多而導致查找效率降低的問題。
針對上述方法，本發明還提出一種生成特徵碼確定狀態機(DFA)的裝置實施例。圖3是本發明中生成特徵碼DFA裝置實施例一的基本結構示意圖。如圖3所示，該裝置包括表達式存儲模塊301、表達式選取模塊302、分組存儲模塊303、分組選取模塊304、判別模塊305、編譯模塊306。其中，表達式存儲模塊301，用於保存特徵碼對應的正則表達式。
表達式選取模塊302，用於從表達式存儲模塊301中選取一條表達式作為當前表達式。
分組存儲模塊303，用於保存所有分組經過編譯後生成的確定狀態機DFA。
分組選取模塊304，用於根據判別模塊305的通知從分組存儲模塊303中選取一個未處理分組作為當前未處理分組。
判別模塊305，用於判斷分組存儲模塊303中是否存在未與表達式選取模塊302中的當前表達式合併編譯過的分組，如果有，則通知分組選取模塊304選取當前未處理分組，並通知編譯模塊306對當前表達式與當前未處理分組進行合併編譯；否則，通知編譯模塊306對當前表達式進行單獨編譯；還用於根據編譯模塊306返回的編譯成功信息通知表達式選取模塊302選取下一條表達式，直至處理完所有特徵碼對應的正則表達式。
編譯模塊306，用於根據判別模塊305的通知，將表達式選取模塊304中的當前表達式和分組選取模塊302中的當前未處理分組進行合併編譯，如果合併編譯獲得的狀態數不大於當前表達式與當前未處理分組單獨編譯的狀態數之和，則將當前表達式加入當前未處理分組中，將合併編譯的結果作為生成的DFA保存在分組存儲模塊303中，並向判別模塊305返回編譯成功信息；否則，向判別模塊305返回編譯失敗信息；還用於根據判別模塊305的通知，對表達式選取模塊304中的當前表達式進行單獨編譯，將當前表達式加入新建的分組中，將單獨編譯的結果作為生成的DFA保存在分組存儲模塊303中，並向判別模塊305返回編譯成功信息。
實際應用中，所述編譯模塊306的內部結構可以如圖4所示，包括編譯控制模塊3061，用於根據判別模塊305發送的進行合併編譯的通知，控制編譯執行模塊3062進行合併編譯，在接收到來自編譯執行模塊3062的編譯結束信號時向判別模塊305返回編譯成功信息，在接收到來自狀態數判別模塊3065的超值觸發信號時向判別模塊305返回編譯失敗信息；還用於根據判別模塊305發送的進行單獨編譯的通知，控制編譯執行模塊3062進行單獨編譯，並在接收到來自編譯執行模塊3062的編譯結束信號時向判別模塊305返回編譯成功信息。
編譯執行模塊3062，用於在編譯控制模塊3061的控制下，將表達式選取模塊302中的當前表達式經過單獨編譯後獲得的狀態數輸出給單獨編譯狀態數存儲模塊3064保存；將表達式選取模塊302中的當前表達式和分組選取模塊304中的當前未處理分組進行合併編譯，將合併編譯過程中獲得的狀態數實時輸出給狀態數判別模塊3065，並在合併編譯結束時向編譯控制模塊3061返回編譯結束信號，並將編譯結果作為生成的DFA輸出給分組存儲模塊303保存；還用於在編譯控制模塊3061的控制下，將表達式選取模塊302中的當前表達式進行單獨編譯，並在單獨編譯結束時向編譯控制模塊3061返回編譯結束信號，並將編譯結果作為生成的DFA輸出給分組存儲模塊303進行保存。
分組狀態數存儲模塊3063，用於保存來自分組選取模塊304中當前未處理分組的狀態數。
單獨編譯狀態數存儲模塊3064，用於保存編譯執行模塊3062輸出的單獨編譯當前表達式所獲得的狀態數。
狀態數判別模塊3065，用於實時判斷來自編譯執行模塊3062的狀態數是否大於單獨編譯狀態數存儲模塊3064和分組狀態數存儲模塊3063中所保存的狀態數之和，如果大於，則向編譯控制模塊3061發送超值觸發信號。
當然，圖3和圖4僅僅是實現本發明方案的實施例，實際應用中，也可以利用其它的裝置結構實現，此處不再贅述。
另外，實際應用中，如果分組太多都可能會導致在文件或報文中查找特徵碼的效率降低。在這種情況下，可以事先設置分組個數的最大值，如果實際分組個數大於這個預先設置的值，就可以進一步將分組進行合併。
圖5是本發明中生成特徵碼DFA裝置實施例二的基本結構示意圖。如圖5所示，該裝置不僅包括表達式存儲模塊301、表達式選取模塊302、分組存儲模塊303、分組選取模塊304、判別模塊305、編譯模塊306，還包括合併判別模塊307、合併模塊308。其中，
合併判別模塊307，用於判斷分組存儲模塊303中分組的個數是否大於事先設置的值，如果大於，則通知合併模塊308進行合併處理，直至分組存儲模塊303中分組的個數小於或等於事先設置的值。
合併模塊308，用於將分組存儲模塊303中任意兩個分組進行合併編譯，將合併編譯後最小的狀態數所對應的兩個分組合併為一個分組，並將合併分組生成的DFA保存在分組存儲模塊303中。
而圖5中的表達式存儲模塊301、表達式選取模塊302、分組存儲模塊303、分組選取模塊304、判別模塊305、編譯模塊306的功能和結構與圖3相同，此處不再詳細描述。
當然，如果利用DFA實現特徵碼匹配的設備的查詢速度很塊，不需要限制分組個數，也可以省略合併判別模塊307和合併模塊308。
應用本發明方法實施例或/和裝置實施例的方案，可以將所有特徵碼對應的正則表達式進行分組，並在分組的過程中完成對每一個分組的編譯，從而達到生成DFA的目的。由於在分組過程中，通過判斷合併編譯產生的狀態數是否大於單獨編譯的狀態數，可以保證分組的合理性，避免每一個分組對應的DFA產生的狀態數過多，佔用大量的存儲空間。另外，由於可以採用實時判斷合併編譯過程中所獲得的狀態數是否大於單獨編譯的狀態數的方法，如果大於，則不必完成後續合併編譯的過程就可以確定當前表達式不應該加入該分組，從而大大節約了編譯時間，提高了編譯的效率。
綜上所述，以上僅為本發明的較佳實施例而已，並非用於限定本發明的保護範圍。凡在本發明的精神和原則之內，所作的任何修改、等同替換、改進等，均應包含在本發明的保護範圍之內。
權利要求
1.一種生成特徵碼確定狀態機的方法，其特徵在於，該方法包括以下步驟a、將第一條特徵碼對應的正則表達式作為當前表達式；b、判斷是否存在未與當前表達式合併編譯過的未處理分組，如果有，則將未處理分組中的一個作為當前未處理分組，執行步驟c；否則，將當前表達式加入新建的分組中並單獨編譯生成確定狀態機DFA，執行步驟d；c、將當前表達式與當前未處理分組進行合併編譯，如果合併編譯獲得的狀態數不大於當前表達式與當前未處理分組單獨編譯的狀態數之和，則將當前表達式加入當前未處理分組中，將合併編譯的結果作為生成的DFA，再執行步驟d；否則，返回步驟b；d、將下一條特徵碼對應的正則表達式作為當前表達式，返回步驟b，直至處理完所有特徵碼對應的正則表達式。
2.根據權利要求1所述的方法，其特徵在於，步驟b所述將當前表達式加入新建的分組中並單獨編譯生成DFA之後，步驟b進一步包括保存單獨編譯後獲得的狀態數；步驟c所述當前未處理分組單獨編譯的狀態數為事先保存的狀態數。
3.根據權利要求2所述的方法，其特徵在於，所述步驟c包括c1、將當前表達式進行單獨編譯，獲得當前表達式單獨編譯的狀態數；c2、將當前表達式與當前未處理分組進行合併編譯，並在合併編譯的過程中，實時判斷當前合併編譯所獲得的狀態數是否大於當前表達式單獨編譯的狀態數與保存的當前未處理分組的狀態數之和，如果大於，則將當前未處理分組作為已處理分組，並返回步驟b；c3、將當前表達式加入當前未處理分組中，將合併編譯的結果作為生成的DFA，將合併編譯後獲得的狀態數作為當前未處理分組的狀態數進行保存，再將當前未處理分組作為已處理分組，並執行步驟d。
4.根據權利要求3所述的方法，其特徵在於，事先設置用於記錄合併編譯過程所產生狀態數的計數變量，並將初始值設置為0，步驟c2所述將當前表達式與當前未處理分組進行合併編譯的過程中進一步包括每編譯完一個狀態，所述計數變量加1；步驟c2所述判斷當前合併編譯所獲得的狀態數是否大於當前表達式單獨編譯的狀態數與保存的當前未處理分組的狀態數之和的方法為判斷所述計數變量的值是否大於當前表達式單獨編譯的狀態數與保存的當前未處理分組的狀態數之和。
5.根據權利要求1至4任一項所述的方法，其特徵在於，所述步驟d之後，如果分組個數大於事先設置的值，則該方法進一步包括x1、將所有分組中任意兩個分組進行合併編譯，獲得任意兩個分組合併編譯後的狀態數；x2、將最小的狀態數所對應的兩個分組合併為一個分組，並生成DFA；x3、判斷當前分組個數是否大於事先設置的值，如果大於，則返回步驟x1；否則，退出本流程。
6.一種生成特徵碼確定狀態機的裝置，其特徵在於，該裝置包括表達式存儲模塊，用於保存特徵碼對應的正則表達式；表達式選取模塊，用於從表達式存儲模塊中選取一條表達式作為當前表達式；分組存儲模塊，用於保存所有分組經過編譯後生成的確定狀態機DFA；分組選取模塊，用於根據判別模塊的通知從分組存儲模塊中選取一個未處理分組作為當前未處理分組；判別模塊，用於判斷分組存儲模塊中是否存在未與表達式選取模塊中的當前表達式合併編譯過的分組，如果有，則通知分組選取模塊選取當前未處理分組，並通知編譯模塊對當前表達式與當前未處理分組進行合併編譯；否則，通知編譯模塊對當前表達式進行單獨編譯；還用於根據編譯模塊返回的編譯成功信息通知表達式選取模塊選取下一條表達式，直至處理完所有特徵碼對應的正則表達式；編譯模塊，用於根據判別模塊的通知，將表達式選取模塊中的當前表達式和分組選取模塊中的當前未處理分組進行合併編譯，如果合併編譯獲得的狀態數不大於當前表達式與當前未處理分組單獨編譯的狀態數之和，則將當前表達式加入當前未處理分組中，將合併編譯的結果作為生成的DFA保存在分組存儲模塊中，並向判別模塊返回編譯成功信息；否則，向判別模塊返回編譯失敗信息；還用於根據判別模塊的通知，對當前表達式進行單獨編譯，將當前表達式加入新建的分組中，將單獨編譯的結果作為生成的DFA保存在分組存儲模塊中，並向判別模塊返回編譯成功信息。
7.根據權利要求6所述的裝置，其特徵在於，所述編譯模塊包括編譯控制模塊，用於根據判別模塊發送的進行合併編譯的通知，控制編譯執行模塊進行合併編譯，在接收到來自編譯執行模塊的編譯結束信號時向判別模塊返回編譯成功信息，在接收到來自狀態數判別模塊的超值觸發信號時向判別模塊返回編譯失敗信息；還用於根據判別模塊發送的進行單獨編譯的通知，控制編譯執行模塊進行單獨編譯，並在接收到來自編譯執行模塊的編譯結束信號時向判別模塊返回編譯成功信息；編譯執行模塊，用於在編譯控制模塊的控制下，將表達式選取模塊中的當前表達式經過單獨編譯後獲得的狀態數輸出給單獨編譯狀態數存儲模塊保存；將表達式選取模塊中的當前表達式和分組選取模塊中的當前未處理分組進行合併編譯，將合併編譯過程中獲得的狀態數實時輸出給狀態數判別模塊，並在合併編譯結束時向編譯控制模塊返回編譯結束信號，並將編譯結果作為生成的DFA輸出給分組存儲模塊保存；還用於在編譯控制模塊的控制下，將表達式選取模塊中的當前表達式進行單獨編譯，並在單獨編譯結束時向編譯控制模塊返回編譯結束信號，並將編譯結果作為生成的DFA輸出給分組存儲模塊；單獨編譯狀態數存儲模塊，用於保存編譯執行模塊輸出的單獨編譯當前表達式所獲得的狀態數；分組狀態數存儲模塊，用於保存來自分組選取模塊中當前未處理分組的狀態數；狀態數判別模塊，用於實時判斷來自編譯執行模塊的狀態數是否大於單獨編譯狀態數存儲模塊和分組狀態數存儲模塊中所保存的狀態數之和，如果大於，則向編譯控制模塊發送超值觸發信號。
8.根據權利要求6或7所述的裝置，其特徵在於，該裝置進一步包括合併判別模塊，用於判斷分組存儲模塊中分組的個數是否大於事先設置的值，如果大於，則通知合併模塊進行合併處理，直至分組存儲模塊中分組的個數小於或等於事先設置的值；合併模塊，用於將分組存儲模塊中任意兩個分組進行合併編譯，將合併編譯後最小的狀態數所對應的兩個分組合併為一個分組，並將合併分組生成的DFA保存在分組存儲模塊中。
全文摘要
本發明提供一種生成特徵碼確定狀態機的方法和裝置，將特徵碼對應的正則表達式進行分組並進行合併編譯，如果合併編譯獲得的狀態數不大於單獨編譯的狀態數之和，則將特徵碼對應的正則表達式加入分組，將合併編譯的結果作為生成的確定狀態機(DFA)。應用本發明方案，可以保證分組的合理性，避免合併編譯生成的DFA產生大量的狀態，佔用過多的存儲空間。
文檔編號H04L29/06GK101079890SQ20071011829
公開日2007年11月28日 申請日期2007年7月4日 優先權日2007年7月4日
發明者常利民 申請人:杭州華三通信技術有限公司