[發明專利]用于正則表達式的編譯器

有效

• 申請號: 201710258370.9
• 申請日: 2012-06-20
• 公開（公告）號: CN107122221B
• 公開（公告）日: 2021-03-12
• 發明（設計）人: R·戈亞爾;S·L·比拉;K·A·布里斯
• 申請（專利權）人: 馬維爾亞洲私人有限公司
• 主分類號: G06F8/41
• 分類號: G06F8/41;G06F9/448;H04L29/06
• 代理公司: 北京市金杜律師事務所 11256
• 代理人: 王茂華

本申請是2012年6月20日遞交的第201280038799.2號發明專利申請的分案申請。

相關申請

本申請是2011年6月24日提交的美國申請No.13/168,450的繼續并且要求其優先權。上述申請的全部教導通過引用合并于此。

技術領域

本公開的非限制性示例一般地涉及通信網絡的技術領域，并且更具體地涉及用于內容搜索的方法和裝置。

背景技術

開放系統互連(OSI)參考模型定義了用于通過傳輸介質進行通信的7個網絡協議層(L1-L7)。上層(L4-L7)表示端對端通信并且下層(L1-L3)表示本地通信。

聯網應用感知系統需要處理、濾波和切換L3到L7網絡協議層的范圍，例如，L7網絡協議層諸如超文本傳輸協議(HTTP)和簡單郵件傳輸協議(SMTP)，以及L4網絡協議層諸如傳輸控制協議(TCP)。除了處理網絡協議層，聯網應用感知系統需要通過L4-L7網絡協議層來同時確保這些協議對基于訪問和內容的安全性，包括防火墻、虛擬專用網(VPN)、安全套接字層(SSL)、入侵檢測系統(TDS)、因特網協議安全(IPSec)、線速度的防病毒(AV)和防垃圾郵件功能。

網絡處理器可用于高吞吐量L2和L3網絡協議處理，即執行分組處理以線速度轉發分組。通常，通用處理器用于處理需要更多智能處理的L4-L7網絡協議。雖然通用處理器可以執行計算密集型任務，但是沒有足夠用于處理數據使得其能夠被以線速轉發的性能。

內容感知聯網需要以“線速度”的對分組內容的檢查。可以對內容進行分析，以確定是否存在安全漏洞或入侵。應用大量正則表示式形式的圖樣和規則以確保所有的安全漏洞或入侵被檢測到。正則表示式是用于描述字符串的圖樣的緊湊型方法。由正則表示式所匹配的最簡單圖樣是單個字符或字符串，例如，/c/或/cat/。正則表示式還包括具有特殊含義的運算符和元字符。

通過使用元字符，正則表示式可以用于更復雜的搜索，諸如“abc.*xyz”。也就是說，在不限制“abc”和“xyz”之間的字符數目的情況下，找到字符串“abc”，之后是字符串“xyz”。另一示例是正則表示式“abc..abc.*xyz；”，也就是找到字符串“abc”，后面兩個字符，然后是“abc”并且在不限制個數的字符后由串“xyz”跟隨。

入侵檢測系統(IDS)應用檢查所有流過網絡的獨立分組的內容，并且識別可能指示嘗試闖入或威脅系統的可疑圖樣。可疑圖樣的一個示例可以是分組中的特定文本串，該特定文本串在100個字符以后跟隨另一特定文本串。

通常使用搜索算法來執行內容搜索以處理正則表示式，搜索算法諸如確定性有限自動機(DFA)或者非確定性有限自動機(NFA)。

發明內容

一種方法和相應的裝置，涉及將用于給定的圖樣集合的非確定性有限自動機(NFA)圖形轉換成具有多個狀態的確定性有限自動機(DFA)圖形。DFA狀態中的每一個被映射成NFA圖形的一個或多個狀態。計算映射成每個DFA狀態的NFA圖形的一個或多個狀態的哈希值。對于給定圖樣，DFA狀態表將多個DFA狀態中的每一個與NFA圖形的一個或多個狀態的哈希值相關。

可以確定與由NFA圖形和DFA圖形所識別的字母相關聯的給定圖樣的有效字符。基于該確定，該方法壓縮NFA圖形和DFA圖形以識別圖樣，該圖樣僅由與NFA圖形和DFA圖形所識別的字母相關聯的給定圖樣的有效字符組成。

附圖說明

從如在附圖中所示的本發明的示例性實施例的以下更具體的描述中，前述內容將顯而易見，在附圖中相同的附圖標記指代所有不同視圖中的相同部件。附圖不一定按比例，而是著重于圖示本發明的實施例。

圖1是圖示系統的框圖，在該系統中操作安全設備以保護專用網絡。

圖2是可以由本發明使用的安全設備的框圖。

圖3是示例NFA的NFA圖形。

圖4是示例DFA的DFA圖形。

圖5A-G是圖示圖形爆炸的原理的NFA和DFA圖形和表。

圖6A-B是將NFA圖形轉換成DFA圖形的方法的流程圖。

圖7是用于確定NFA圖形中的狀態的埃普西隆終止的方法的流程圖。

圖8A-C是用于將NFA圖形轉換成DFA圖形的方法的流程圖。

圖9是用于確定NFA圖形中的狀態的埃普西隆終止的方法的流程圖。

圖9A-9B是用于將NFA圖形轉換成DFA圖形的方法的流程圖。