[發明專利]確定有限自動機的混合表示

有效

• 申請號: 200910126086.1
• 申請日: 2009-03-09
• 公開（公告）號: CN101834716A
• 公開（公告）日: 2010-09-15
• 發明（設計）人: 馬青明;布賴恩·伯恩斯;李升;劉娜;吳雪君;于珊;鄭麗
• 申請（專利權）人: 叢林網絡公司
• 主分類號: H04L9/00
• 分類號: H04L9/00;H04L29/06
• 代理公司: 北京康信知識產權代理有限責任公司 11240
• 代理人: 余剛;吳孟秋

背景技術

諸如入侵檢測和防御(IDP)設備的安全設備已在服務提供和企業網絡中變為一個關鍵部件。由IDP設備利用來識別攻擊、威脅和/或惡毒流量的傳統技術是基于簽名的。這些簽名典型地為正則表達(如串)或子串的形式，這些正則表達或子串轉換為不確定有限自動機(NFA)或確定有限自動機(DFA)，并被用作通過匹配引擎來比較網絡流量中的一串字節或包序列的圖案。雖然存在多種方式來表示DFA，但是由于正則表達中通配符數量的增加、DFA狀態數量的增加(這些增加有時以指數形式)，DFA易于狀態爆炸(state?explosion)。因此，對于任意DFA表示，通常在存儲器消耗和匹配速度之間存在一個權衡。

發明內容

根據一個實現，由設備執行的方法可以包括：通過該設備接收數據單元；通過該設備確定當前狀態是否為位圖狀態，當前狀態與確定有限自動機(DFA)相關聯，確定有限自動機包括位圖形式的一部分狀態和DFA表形式的其余部分的狀態；當確定當前狀態不是位圖狀態時，通過該設備確定對應于數據單元的值是否大于閾值；當確定對應于數據單元的值大于閾值時，通過該設備確定當前狀態是否不敏感，其中不敏感表示對當前狀態每一個下一個狀態都是相同的狀態；以及當確定當前狀態不敏感時，通過該設備選擇一個缺省狀態作為對當前狀態的下一個狀態。

根據另一個實現，網絡設備包括處理器、存儲器以及通信接口，來接收數據單元；確定當前狀態是否為位圖狀態，該當前狀態與確定有限自動機(DFA)相關聯，確定有限自動機包括位圖形式的一部分狀態和DFA表形式的其余部分的狀態；當確定當前狀態不是位圖狀態時，確定對應于數據單元的數據值是否大于閾值美國信息交換標準編碼(ASCII)值；當確定對應于數據單元的數據值大于閾值ASCII值時，確定當前狀態是否不敏感，其中不敏感表示對當前狀態每一個下一個狀態都是相同的狀態；當確定當前狀態不敏感時，選擇缺省值作為對當前狀態的下一個狀態；并且確定下一個狀態是否對應于表示威脅、攻擊或惡意流量的最終狀態。

根據又一個實現，其上存儲有由至少一個處理器執行的指令的計算機可讀介質可以包括：用于接收數據單元的一個或多個指令；用于確定當前狀態是否為位圖狀態的一個或多個指令，其中當前狀態與確定有限自動機(DFA)相關聯，確定有限自動機包括位圖形式的一部分狀態和DFA表形式的其余部分的狀態；用于當確定當前狀態不是位圖狀態時確定對應于數據單元的美國信息交換標準編碼(ASCII)值是否大于閾值ASCII值的一個或多個指令；用于當確定對應于數據單元的ASCII值大于閾值ASCII值時確定當前狀態是否不敏感的一個或多個指令，其中不敏感表示對當前狀態每一個下一個狀態都是相同的狀態；以及當確定當前狀態不敏感時，用于選擇缺省狀態作為對該當前狀態的下一個狀態的一個或多個指令。

根據另一個實現，網絡設備可以包括：用于存儲確定有限自動機(DFA)的裝置，確定有限自動機包括位圖形式的一部分狀態和DFA表形式的其余部分的狀態；用于接收數據單元的裝置；用于確定與DFA相關聯的當前狀態是否為位圖狀態的裝置；用于確定對應于數據單元的值是否大于閾值的裝置；用于確定當前狀態是否不敏感的裝置，其中不敏感表示對當前狀態每一個下一個狀態都是相同的狀態；以及當確定該值大于閾值并且當前狀態不敏感時，選擇缺省狀態作為對當前狀態的下一個狀態的裝置。

附圖說明

結合于此并構成說明書一部分的附圖示出了本文描述的一個或多個實施例，并結合說明書一起對這些實施例加以闡述。在附圖中：

圖1是示出了可以實現這里描述的方法、設備和系統的示例性環境的示圖；

圖2是示出了圖1中描述的網絡設備的示例性部件的示圖；

圖3是圖1中描述的網絡設備的示例性功能部件的示圖；

圖4A和圖4B是圖3中描述的DFA表的示例性實現的示圖；

圖5是圖3中描述的位圖的示例性實現的示圖；

圖6A和6B是示出了對于圖案匹配的示例性過程的流程圖；

圖7是DFA狀態的示例性表示的示圖；以及

圖8是確定下一個狀態的示例性實現的示圖。

具體實施方式

以下詳細描述參照了附圖。不同附圖中的相同參考標號可以標識相同或類似的元件。此外，以下描述不對本發明構成限制。而是，本發明的范圍由所附權利要求及其等價物限定。