確定自動機狀態轉換表的空間壓縮方法

2023-11-30 22:04:21 3

專利名稱：確定自動機狀態轉換表的空間壓縮方法
技術領域：
本發明涉及信息檢索領域，特別涉及確定自動機狀態轉換表的空間壓縮方法。
背景技術：
近年來，正則表達式匹配已經成為網絡安全領域的一個研究焦點。網絡通信過程 中對實時性和高效性的需求，增強了確定自動機(DFA)在識別正則表達式過程中的重要 性。然而，隨著正則表達式在實際應用中的不斷複雜化，由正則表達式所生成的DFA的狀態 規模也不斷增大，DFA狀態規模的不斷增大使得計算機存儲空間的消耗急劇增長，這種急劇 增長已經成為限制正則表達式應用的一個瓶頸。基於上述原因，需要對DFA空間進行壓縮， DFA空間的壓縮方法已經成為學者關注的焦點。現有技術中存在DFA空間的壓縮方法，如在參考文獻1 「Fast and memory-efficient regular expression matching for deep packet inspection. Proceedings of the 2006 ACM/IEEE symposium on Architecture for networking and communications systems 2006, San Jose, California, USA December 03-05,2006」 中 利用規則重寫和規則分類的方法來簡化正則表達式，文中提出把一組正則表達式集合分成 若干組，每組都可用中等規模的DFA來識別。然而這一重寫規則的方法僅適用於非重疊匹 配的情況。在參考文獻 2 「Algorithm to Accelerate Multiple Regular Expressions Matching for Deep Packet Inspection Conference -SIGCOMM' 06 September 11-15， 2006」中提出了用D2FA方法來壓縮DFA的存儲空間。D2FA方法利用默認轉換來消除重複 的轉換，但是識別一個字符的狀態變換時間將成比例的增長。在參考文獻3 「An improved algorithm to accelerate regular expression evaluation, Proceedings of the 3rd ACM/IEEE Symposium on Architecture for networking and communications systems, 145-154，2007」提出了一種DFA的壓縮方法，它在處理長度為N的字符串時最多做2N次狀 態變迀，這種方法可達到與D2FA相當的壓縮效果，但同樣具有識別時間長的缺陷。在參考文 獻 4 "Animproved DFA for fast regular expression matching,ACM SIGCOMM Computer Communication Review, Volume 38，Issue 5 (October 2008)，Pages 29—40」中，提出了用 δ FA方法來消除DFA狀態轉換表中的冗餘。在DFA的遍歷過程中，對相同的輸入字符臨近 狀態分享大部分的下一跳狀態，因此當前狀態的轉換可以從其父節點的狀態轉換表中動態 的檢索出來。但是每次狀態轉換都需要更新當前狀態的狀態轉換表，非常費時。在參考文獻 5 "XFA :Faster Signature Matching with Extended Automata, Security and Privacy, 2008. SP 2008. IEEESymposium, pp. 187-201，18-22May 2008」提出了用 XFA 的方法來解決 兩類特殊的正則表達式的指數爆炸問題。該方法對DFA進行擴展，在DFA的每個狀態上附 加計數器來記錄匹配過程中正則表達式中字符重複的次數。該方法只能解決某些正則表達 式的指數爆炸問題，不具有通用性。綜上所述，現有技術中的方法存在兩個共同的特點(1)增加時間開銷來換取空 間的減少；(2)沒有最壞情況下的空間開銷保證。雖然上述方法在某些特殊的情況下是有效的，但是仍需要做進一步的改進。

發明內容
本發明的目的是克服現有技術中的確定自動機狀態表的空間壓縮方法所具有的 時間開銷大的缺陷，從而提供一種時間開銷與空間開銷都有明顯提高的空間壓縮方法。為了實現上述目的，本發明提供了一種確定自動機狀態轉換表的空間壓縮方法， 包括步驟1)、將確定自動機狀態轉換表表示為一個mXn的矩陣A，其中m代表確定自 動機中的狀態的個數，η代表字符集的大小；步驟2)、定義一個大小為m的列向量X和一個大小為η的行向量Y ；步驟3)、對所述的列向量X和所述的列向量Y做迭代計算，直到對於任意的 1 ^ i ^m, X[i]是多重集Di.中頻率最高的元素，並且對於任意的1 < j < n，Y[j]是多 重集Dj中頻率最高的元素；其中，所述的Di. = {A[i，j]_Y[j] |1彡j ( η}，所述的Dj = {A[i，j]-X[i] |1 ^ i ^m}；步驟4)、由所述的矩陣A、列向量X和行向量Y計算稀疏矩陣R，並壓縮所得到的稀 疏矩陣 R;其中，R[i，j] = A[i，j]-X[i]_Y[j]。上述技術方案中，所述的步驟3)包括步驟3-1-1)、以隨機的方式為所述的列向量X和所述的行向量Y賦初值；步驟3-1-2)、計算列向量X的值，包括首先令Di. = {A[i，j]_Y[j]|l彡j彡n}，然後用a表示所述Di.中出現頻率最高的 元素，如果a在Di.中的出現次數大於X[i]在Di.中的出現次數，則令X[i] =^否則乂[土] 的值保持不變；步驟3-1-3)、計算行向量Y的值，包括首先令Dj = {A[i，j]_X[i] |1彡i彡m}，然後用a等於Dj中出現頻率最高的元 素，如果3在0」中的出現次數大於Y[j]在0」中的出現次數，則令Y[j] =a，否則Y[j]的 值保持不變；步驟3-1-4)、判斷所述列向量X與行向量Y的值是否發生變化，如果兩者都沒有發 生變化，結束步驟3)的操作，否則重新執行步驟3-1-2)。上述技術方案中，所述的步驟3)包括步驟3-2-1)、以隨機的方式為所述的列向量X和所述的行向量Y賦初值；步驟3-2-2)、計算行向量Y的值，包括首先令Dj = {A[i，j]_X[i] |1≤i≤m}，然後用a等於Dj中出現頻率最高的元 素，如果3在0」中的出現次數大於Y[j]在0」中的出現次數，則令Y[j] =a，否則Y[j]的 值保持不變；步驟3-2-3)、計算列向量X的值，包括首先令Di. = {A[i，j]_Y[j]|l≤j彡n}，然後用a表示所述Di.中出現頻率最高的 元素，如果a在Di.中的出現次數大於X[i]在Di.中的出現次數，則令X[i] =^否則乂[土] 的值保持不變；步驟3-2-4)、判斷所述列向量X與行向量Y的值是否發生變化，如果兩者都沒有發生變化，結束步驟3)的操作，否則重新執行步驟3-2-2)。上述技術方案中，在所述的步驟4)中，採用矩陣壓縮方法對所述的稀疏矩陣R進 行壓縮。上述技術方案中，所述的矩陣壓縮方法為包括二分查找法、三數組法和 Tetris-哈希法在內的經典矩陣壓縮方法。本發明還提供了一種用所述的確定自動機狀態轉換表的空間壓縮方法所得到的 結果實現狀態查詢的方法，包括步驟1)、讀取當前狀態S，當前輸入字符c ；步驟2)、令 t = X [s]+Y [C]；步驟3)、查看稀疏矩陣R中的元素R[s，c]是否為零，如果不是，用t+R[s，c]替換 t，如果是，則無需替換；所得到的結果t為所要轉換的下一個狀態。上述技術方案中，在所述的步驟3)中，採用BloomFilter方法查看稀疏矩陣R中 的元素R[s, c]。本發明的優點在於本發明的確定自動機狀態轉換表的空間壓縮方法在減少內存中所佔用空間的同 時，大大減少了空間開銷。


圖1為由正則表達式所生成的自動狀態機的示意圖；圖2為一個正則表達式的確定自動狀態機狀態轉換表的矩陣分解過程示意圖；圖3為本發明的確定自動機狀態轉換表的空間壓縮方法的流程圖。
具體實施例方式下面結合附圖和具體實施方式
對本發明加以說明。在一個實施例中，有如下正則表達式a+|b+C|C*d+。利用該正則表達式可以構建 確定自動機(DFA)。由正則表達式構建確定自動機的過程為本領域技術人員所公知的現有 技術，它包括首先將正則表達式解析成一棵表達樹，然後將該表達樹轉換成非確定自動機 (NFA)，最後把非確定自動機轉換為確定自動機。上述過程中正則表達式的表達樹轉換為 NFA的方法有很多種，在本實施例中可採用Thompson構造法。圖1是前述正則表達式所生 成的DFA的示意圖。在得到DFA後，可將DFA中的狀態轉換關係用矩陣表示，這一矩陣被稱 為狀態轉換表。在下面的表1中給出了圖1所示DFA所生成的狀態轉換表。
表 1以上根據正則表達式生成DFA，進而得到DFA的狀態轉換表的實現方法都為現有 技術，本發明主要涉及在得到DFA的狀態轉換表後，如何壓縮這一狀態轉換表，以減少存儲 空間。DFA的狀態轉換表可以表示為一個mXn的矩陣A，其中m代表狀態的個數，η代表 字符集的大小，而A[i，j]即為在當前狀態i讀入字符j所達到的下一個狀態。出於說明的 方便，本實施例中所列舉的正則表達式的形式十分簡單，使得與其對應的表1中的狀態轉 換表的形式也十分簡單，不會佔據多大的內存空間。但本領域技術人員很容易想到，一旦正 則表達式複雜化，則所對應的DFA的狀態轉換表就會消耗大量的內存。因此，需要對DFA的 狀態轉換表進行壓縮。本發明在實現對狀態轉換表的壓縮時，利用一個特殊的矩陣D來逼 近A，以使得R = A-D儘可能稀疏，從而達到用D和R來代替A，減小存儲空間的目的。也就是說，本發明所要解決的問題形式化定義為設X是一個大小為m的列向 量，Y是一個大小為η的行向量，D是一個由X和Y確定的mXn的矩陣，並滿足D[i，j]= X[i]+Y[j] (1彡i彡m，1彡j彡η)。對於給定的矩陣Amxn，求解X和Y以使得矩陣R = A-D =[A[i，j]-X[i]_Y[j]中非零元素的個數最少。下面仍然以表1中的矩陣A為例，結合圖2和圖3就如何確定列向量X、行向量Y 以及稀疏矩陣R加以說明。首先以隨機的方式為列向量X和行向量Y賦初值。假設初始時X= {1,2,4,0,4} T，Y= {4，3，3，2}，則根據R = A-D= [A[i，j]_X[i]_Y[j]]的公式，此時所得到的矩陣R的 值如下面的表2所示。 表2此時，需要對X、Y的值做迭代計算。在第一次迭代計算的過程中，首先計算X的 值，令Di. = {A[i，j]-Y[j] 11彡j彡η}，因此用表1中的第一行減去Y的初始值，得到D1.= {-3，-1，-3，1}。然後從D1.中讀取出現頻率最高的元素，用a表示這一出現頻率最高的元素， 顯然在D1.中，a = -3。接著判斷3在01.中的出現次數是否大於X[l]在D1.中的出現次數， 如果大於，令X[l] =a。當a = _3時，其在隊.中的出現次數為2，而X[l] = 1，其在D1.出 現的次數為1，a在D1.出現的次數大於X[l]在01.出現的次數，所以更新X[l] =a = -3。 參照上述方法，可以得到D2.，然後從D2.中找出出現頻率最高的元素a，通過比較a與X[2] 在~中的出現次數，可以知道是否要將X[2]的值替換為出現頻率最高的元素。結合前述 實例可以知道，X[2]的值發生了變化，新的X[2] =-3。類似的，可以知道，X[3] = 1，X[4] =-3，X[5] = -3。也就是說，在經過第一次迭代計算後，X由原來的[1，2，4，0，4]τ轉變為 [-3，-3,1, _3，-3]τ。接著對Y的值做迭代計算。在計算Y的值時，令Dj = {A[i，j]_X[i] |1彡i彡m}， 因此用表1中的第一列減去X的值。需要說明的是，此處所述的X的值不是X的初始值，而 是X在經過第一次迭代後的新的值。因此，計算得到的D.i= {4，4，0，4，4}τ。在得到D1後， 同樣可以用a表示出現頻率最高的元素，然後將出現頻率最高的元素在D1中的出現次數與 Y[l]進行比較，由於Y[l] =4 = a，所以無需改變Y[l]的值。同理可計算得到Υ[2] =5、 Υ[3] = 3、Y[4] = 6。也就是說，在經過第一次迭代計算後，Y由原來的{4，3，3，2}改變為 {4，5，3，6}。在經過第一次迭代計算後，X、Y的值都發生了變化，因此，矩陣R的值也會發生相 應變化，在下面的表3中給出了矩陣R的新的值。 表3在完成第一次迭代計算後，需要判斷是否繼續進行迭代計算。如果X和Y的值在此 次迭代計算過程中都沒有發生改變，則無需繼續迭代計算，否則，需要繼續進行迭代計算。 在第一次迭代計算過程中，X和Y的值都發生了變化，因此需要繼續進行迭代計算。在第二次的迭代計算過程中，同樣先計算X的值。X值的計算過程與第一次迭代計 算過程相類似，只是此時Y的值為經過第一次迭代計算後的Y值。經過第二此迭代計算後 的X的值由{-3，-3，1，-3，-3}τ改變為{-3，-3，-3，-3，-3}τ。然後繼續計算Y的值，Y的值 沒有發生變化，同樣為{4，5，3，6}。在得到新的X、Y值後，繼續計算矩陣R的值，在下面的表4中給出了矩陣R的新的值。
表 4由於X的值發生了變化，因此在第二此迭代計算完成後，需要繼續進行迭代計算 過程。第三次迭代計算過程與前兩次相似，迭代計算的結果為X = {-3，-3，-3，-3，-3} T，Y= {4,5,3,6} 0與第二次迭代計算相比，此次迭代計算所得到的Χ、Υ的值並沒有發生變 化，因此矩陣R的值與表4相比同樣沒有發生變化，且無需繼續進行迭代計算過程。由上述計算過程可以知道，表1中所涉及的用矩陣表示的DFA的狀態轉換表經過 多次迭代計算轉換成了列向量Χ{_3，-3，-3，-3，-3}τ、行向量Υ{4，5，3，6}以及表4所示的 稀疏矩陣R。對於稀疏矩陣R可以採用現有技術中的相關方法(如現有技術中最常用的二 分查找法、三數組法和Tetris-哈希法)進行壓縮操作，從而達到壓縮DFA狀態轉換表的目 的。雖然在本實施例中，在各次迭代計算的過程中，都是先算X的值，再算Y的值，但在 其它實施例中，也可以先算Y的值，再算X的值。另外，雖然在上面的表2、表3、表4中分別 給出了當Χ、Υ的值發生變化時對應的矩陣R的值，但在實際操作中，並不需要多次計算矩陣 R的值，而且出於減少計算量的考慮，通常是在Χ、Υ的值確定後，才一次性計算矩陣R的值。通過理論推導很容易知道，利用本發明方法壓縮DFA狀態轉換表的空間壓縮率 為 其中，m表示狀態數，η表示字符數，R表示最後得到的稀疏矩陣，nonzero (R)表示 矩陣R中非零元素的個數。在表 5 中，以 L7-filter signatures、Snort signatures 等 18 組正貝U表達式集 所生成的DFA狀態轉換表為例，將本發明方法(在表中用MAT_ADD表示)與前述參考文獻 4中所提到的δ FA算法加以比較。從比較的結果可以看出，本發明方法的空間壓縮率在14 組(約佔77. 8% )中優於現有的δ FA算法。
表 5
通過本發明的上述方法將DFA的狀態轉換矩陣A替換為列向量X，行向量Y和一個 稀疏矩陣R，並對稀疏矩陣R進行壓縮以後，同樣可以利用所述的X、Y以及壓縮後的R快速 地實現DFA狀態轉換。這一狀態轉換過程包括已知當前狀態為S，當前輸入字符為C，令t = X[s]+Y[C]，然後查看稀疏矩陣R的 當前位置R[S，C]是否為零，如果不是，令t+R[s，c]替換t，如果是，則無需替換。所得到的 結果t就代表所要轉換的下一個狀態。在上述過程中，查看稀疏矩陣R的當前位置R[s，c]是否為零時，可採用現有技術 中的BloomFilter方法。BloomFilter方法是一種效率較高的內存索引算法，它利用位數組 很簡潔地表示一個集合，並能判斷一個元素是否屬於這個集合。該方法被廣泛應用到各種 計算機系統之中表達龐大數據集及提高查找效率。本發明把BloomFilter方法用於稀疏矩 陣元素的查找，能夠有效地提高查找效率。在下面的表6中給出了本發明方法(在表中用MAT_ADD表示)與參考文獻4中的 S FA算法相比，在不同稀疏矩陣壓縮方法下查找矩陣所花費時間(單位為秒)，從中可以看 出，本發明方法所花費時間遠遠少於現有技術中的S FA算法，與未壓縮前相比，時間開銷 的差別不大。 表6最後所應說明的是，以上實施例僅用以說明本發明的技術方案而非限制。儘管參 照實施例對本發明進行了詳細說明，本領域的普通技術人員應當理解，對本發明的技術方 案進行修改或者等同替換，都不脫離本發明技術方案的精神和範圍，其均應涵蓋在本發明 的權利要求範圍當中。
1權利要求
一種確定自動機狀態轉換表的空間壓縮方法，包括步驟1)、將確定自動機狀態轉換表表示為一個m×n的矩陣A，其中m代表確定自動機中的狀態的個數，n代表字符集的大小；步驟2)、定義一個大小為m的列向量X和一個大小為n的行向量Y；步驟3)、對所述的列向量X和所述的列向量Y做迭代計算，直到對於任意的1≤i≤m，X[i]是多重集Di.中頻率最高的元素，並且對於任意的1≤j≤n，Y[j]是多重集D.j中頻率最高的元素；其中，所述的Di.＝{A[i，j] Y[j]|1≤j≤n}，所述的D.j＝{A[i，j] X[i]|1≤i≤m}；步驟4)、由所述的矩陣A、列向量X和行向量Y計算稀疏矩陣R，並壓縮所得到的稀疏矩陣R；其中，R[i，j]＝A[i，j] X[i] Y[j]。
2.根據權利要求1所述的確定自動機狀態轉換表的空間壓縮方法，其特徵在於，所述 的步驟3)包括步驟3-1-1)、以隨機的方式為所述的列向量X和所述的行向量Y賦初值；步驟3-1-2)、計算列向量X的值，包括首先令Di. = {A[i，j]_Y[j]|l彡j彡n}，然後用a表示所述Di.中出現頻率最高的元 素，如果a在Di.中的出現次數大於X[i]在Di.中的出現次數，則令X[i] =a，否則X[i]的 值保持不變；步驟3-1-3)、計算行向量Y的值，包括首先令Dj = {A[i，j]-X[i] |1彡i彡m}，然後用a等於Dj中出現頻率最高的元素，如 果3在0」中的出現次數大於Y[j]在0」中的出現次數，則令Y[j] =^否則￥[」]的值保 持不變；步驟3-1-4)、判斷所述列向量X與行向量Y的值是否發生變化，如果兩者都沒有發生變 化，結束步驟3)的操作，否則重新執行步驟3-1-2)。
3.根據權利要求1所述的確定自動機狀態轉換表的空間壓縮方法，其特徵在於，所述 的步驟3)包括步驟3-2-1)、以隨機的方式為所述的列向量X和所述的行向量Y賦初值；步驟3-2-2)、計算行向量Y的值，包括首先令Dj = {A[i，j]-X[i] |1彡i彡m}，然後用a等於Dj中出現頻率最高的元素，如 果3在0」中的出現次數大於Y[j]在0」中的出現次數，則令Y[j] =^否則￥[」]的值保 持不變；步驟3-2-3)、計算列向量X的值，包括首先令Di. = {A[i，j]_Y[j]|l彡j彡n}，然後用a表示所述Di.中出現頻率最高的元 素，如果a在Di.中的出現次數大於X[i]在Di.中的出現次數，則令X[i] =a，否則X[i]的 值保持不變；步驟3-2-4)、判斷所述列向量X與行向量Y的值是否發生變化，如果兩者都沒有發生變 化，結束步驟3)的操作，否則重新執行步驟3-2-2)。
4.根據權利要求1所述的確定自動機狀態轉換表的空間壓縮方法，其特徵在於，在所 述的步驟4)中，採用矩陣壓縮方法對所述的稀疏矩陣R進行壓縮。
5.根據權利要求4所述的確定自動機狀態轉換表的空間壓縮方法，其特徵在於，所述的矩陣壓縮方法為包括二分查找法、三數組法和Tetris-哈希法在內的經典矩陣壓縮方 法。
6.一種用權利要求1-5之一的確定自動機狀態轉換表的空間壓縮方法所得到的結果 實現狀態查詢的方法，包括步驟1)、讀取當前狀態s,當前輸入字符c ； 步驟 2)、令 t = X [s]+Y [c]；步驟3)、查看稀疏矩陣R中的元素R[s，c]是否為零，如果不是，用t+R[s，c]替換t，如 果是，則無需替換；所得到的結果t為所要轉換的下一個狀態。
7.根據權利要求6所述的狀態查詢方法，其特徵在於，在所述的步驟3)中，採用 BloomFilter方法查看稀疏矩陣R中的元素R[s，c]。
全文摘要
本發明提供一種確定自動機狀態轉換表的空間壓縮方法，包括將確定自動機狀態轉換表表示為一個m×n的矩陣A，其中m代表確定自動機中的狀態的個數，n代表字符集的大小；定義一個大小為m的列向量X和一個大小為n的行向量Y；對所述的列向量X和所述的列向量Y做迭代計算，直到對於任意的1≤i≤m，X[i]是多重集Di.中頻率最高的元素，並且對於任意的1≤j≤n，Y[j]是多重集D.j中頻率最高的元素；其中，所述的Di.＝{A[i，j]-Y[j]|1≤j≤n}，所述的D.j＝{A[i，j]-X[i]|1≤i≤m}；由所述的矩陣A、列向量X和行向量Y計算稀疏矩陣R，並壓縮所得到的稀疏矩陣R；其中，R[i，j]＝A[i，j]-X[i]-Y[j]。本發明的確定自動機狀態轉換表的空間壓縮方法在減少內存中所佔用空間的同時，大大減少了空間開銷。
文檔編號G06F17/30GK101916259SQ201010226250
公開日2010年12月15日 申請日期2010年7月6日 優先權日2010年7月6日
發明者何慧敏, 劉燕兵, 劉萍, 譚建龍, 郭莉 申請人:中國科學院計算技術研究所