[發(fā)明專利]一種多條正則表達式的增量分組方法

有效

• 申請?zhí)枺?/td>: 201010611580.X
• 申請日: 2010-12-17
• 公開（公告）號: CN102073530A
• 公開（公告）日: 2011-05-25
• 發(fā)明（設計）人: 李鋒偉;云曉春;杜躍進;汪立東;陳訓遜;包秀國;杜翠蘭;王勇;薛晨
• 申請（專利權）人: 國家計算機網(wǎng)絡與信息安全管理中心;曙光信息產(chǎn)業(yè)（北京）有限公司
• 主分類號: G06F9/45
• 分類號: G06F9/45
• 代理公司: 北京安博達知識產(chǎn)權代理有限公司 11271
• 代理人: 徐國文

技術領域

本發(fā)明涉及網(wǎng)絡安全領域，具體涉及一種增量分組編譯正則表達式的方法。

背景技術

隨著網(wǎng)絡技術的不斷發(fā)展，網(wǎng)絡安全問題日益凸顯，內(nèi)容安全也越來越受到重視。網(wǎng)絡安全系統(tǒng)功不可沒，它防止了有害信息的網(wǎng)絡傳播，它防止了國家或企業(yè)機密信息的網(wǎng)絡泄漏。主要的網(wǎng)絡安全系統(tǒng)有入侵檢測系統(tǒng)(Intrusion?Detection?System，IDS)和入侵防御系統(tǒng)(Intrusion?PreventionSystem，IPS)，等等。通過對入侵行為的檢測，來加強信息安全防御能力。現(xiàn)有的IDS或者IPS中，例如Snort、BRO等，多數(shù)采用了設定規(guī)則的方式對網(wǎng)絡數(shù)據(jù)包進行包頭或者/和內(nèi)容的檢查，符合指定規(guī)則的數(shù)據(jù)包，根據(jù)規(guī)則對應的處理辦法進行處理，或是轉發(fā)，或是日志。另外，網(wǎng)絡安全還有一個重要的技術是病毒檢測，通過對數(shù)據(jù)包進行病毒特征的檢測，檢測到數(shù)據(jù)包不上傳主機，從而避免主機受到病毒的入侵。由于病毒種類繁多，這類病毒特征庫非常龐大。可見，通過規(guī)則和特征進行匹配的方法，將成為影響這類系統(tǒng)性能的重要因素。在很多系統(tǒng)中，也采用了正則表達式的方式來表達規(guī)則和特征，通過較少的正則表達式濃縮更多的規(guī)則和特征。

但是利用正則表達式規(guī)則，進行對比匹配，會消耗大量的系統(tǒng)資源，從而降低系統(tǒng)的性能。當正則式條數(shù)很大時，系統(tǒng)的性能將受到嚴重影響，因此許多研究開始通過定制的ASIC(Application-specific?Integrated?Circuit)或者定制的FPGA(Field-programmable?Gate?Array)來協(xié)同主機進行正則表達式的匹配工作，以減輕主機系統(tǒng)的負擔，帶來提升整個系統(tǒng)的性能的結果。

利用正則表達式進行對比匹配，通常會將其轉換為確定有限自動機(Deterministic?Finite?Automata，DFA)或者非確定有限狀態(tài)機(Nondeterministic?Finite?Automation，NFA)，利用狀態(tài)的跳轉來進行匹配。通常NFA的方法需要需要回溯，匹配速度慢；而DFA的方法不需要回溯，匹配速度非常快，但是其空間的消耗很大，對于規(guī)則數(shù)量較多時，會引起空間的爆炸。因此，利用定制的ASIC和FPGA都面臨硬件面積有限，而規(guī)則數(shù)量多，將面臨硬件無法存儲這么多規(guī)則生成的DFA的問題。

利用DFA進行正則式的匹配，實時性非常好，但正則式規(guī)則數(shù)量多時，將帶來存儲空間的爆炸。假設有n條正則式，其計算的時間復雜度是0(1)，但其空間復雜度是0(2ⁿ)。利用FPGA去做協(xié)同處理的話，如果規(guī)則生成的DFA空間超過了硬件支持的空間，這將有一些規(guī)則無法進行片上處理。

發(fā)明內(nèi)容

本發(fā)明為解決上述問題利用了FPGA的并行處理特性，采用多路引擎對正則式進行識別。

一種多條正則表達式的增量分組方法，步驟如下：

A、讀取N條正則式；

B、生成兩兩間狀態(tài)數(shù)之和，為增量編譯的依據(jù)；

C、根據(jù)兩兩間狀態(tài)數(shù)之和，采用冒泡法進行排序；

D、增量編譯前，初始化變量ruler_no＝0，old_ruler_no＝0和i＝0；

E、設置第i組的狀態(tài)閾值，根據(jù)硬件板卡上各塊空間的大小，設置該組支持狀態(tài)數(shù)的閾值；

F、按照步長STEP，以該變量遞增方式更新ruler_no；如果(ruler_no+STEP)大于等于n，則ruler_no等于n，如果小于n，則ruler_no設置為(ruler_no+STEP)；

G、編譯[old_ruler_no，ruler_no)之間規(guī)則，得到DFA的狀態(tài)數(shù)；

H、此時狀態(tài)數(shù)和該組的狀態(tài)閾值進行比較，如果小于則判斷ruler_no是否等于n，等于則到步驟12保存該組DFA[i]，不等于則返回步驟F；如果等于則到步驟L保存該組DFA[i]；如果大于則進行步驟J；

I、ruler_no減1；

J、編譯[old_ruler_no，ruler_no)之間規(guī)則，得到DFA的狀態(tài)數(shù)；

K、此時狀態(tài)數(shù)和該組的狀態(tài)閾值進行比較。如果小于等于則到步驟L保存該組DFA[i]；如果大于則會對步驟J；

L、保存該組DFA[i]，保存編譯好的合適硬件空間的DFA；

M、判斷是否結束，當i大于等于硬件空間的最大分組數(shù)MAX_GROUP_NUM時，或者所有規(guī)則已經(jīng)編譯完成ruler_no等于n時，退出；否則i加1后，繼續(xù)回到步驟E。