[發(fā)明專利]正則表達(dá)式匹配系統(tǒng)及匹配方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201110424853.4
• 申請(qǐng)日: 2011-12-16
• 公開(kāi)（公告）號(hào): CN102523219A
• 公開(kāi)（公告）日: 2012-06-27
• 發(fā)明（設(shè)計(jì)）人: 王凱;亓亞烜;李軍
• 申請(qǐng)（專利權(quán)）人: 清華大學(xué)
• 主分類號(hào): H04L29/06
• 分類號(hào): H04L29/06;G06F17/30
• 代理公司: 北京路浩知識(shí)產(chǎn)權(quán)代理有限公司 11002
• 代理人: 王瑩

技術(shù)領(lǐng)域

本發(fā)明涉及網(wǎng)絡(luò)安全技術(shù)領(lǐng)域，尤其涉及一種正則表達(dá)式匹配系統(tǒng)及匹配方法。

背景技術(shù)

基于正則表達(dá)式的模式匹配，簡(jiǎn)稱正則表達(dá)式匹配，是深度檢測(cè)防火墻(Deep?Inspection?Firewall)、網(wǎng)絡(luò)入侵檢測(cè)/防御系統(tǒng)(NIDS/NIPS)、統(tǒng)一威脅管理(UTM)等安全網(wǎng)關(guān)系統(tǒng)的關(guān)鍵組成部分和核心技術(shù)所在。正則表達(dá)式匹配通過(guò)檢查和處理OSI網(wǎng)絡(luò)協(xié)議的L4層之上的網(wǎng)包載荷(Payload)來(lái)對(duì)網(wǎng)包進(jìn)行監(jiān)控或者過(guò)濾。

正則表達(dá)式匹配主要通過(guò)確定型有窮自動(dòng)機(jī)(DFA)和非確定型有窮自動(dòng)機(jī)(NFA)兩種數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)。DFA匹配速度快，但內(nèi)存占用過(guò)高，對(duì)于不少?gòu)?fù)雜的正則表達(dá)式規(guī)則或者大規(guī)模的正則表達(dá)式規(guī)則集合DFA會(huì)發(fā)生狀態(tài)爆炸從而根本無(wú)法構(gòu)造出；NFA內(nèi)存占用小，但匹配速度極慢，在多核或通用處理器平臺(tái)上根本不能滿足實(shí)際的網(wǎng)絡(luò)處理要求。

目前工業(yè)界在正則表達(dá)式匹配上普遍沒(méi)有好的解決方案，其方法和面臨的瓶頸主要是：1)利用學(xué)術(shù)界提出的規(guī)則分組思想，將一個(gè)集合中的正則表達(dá)式規(guī)則分成多組，每一組正則表達(dá)式規(guī)則分別構(gòu)造出對(duì)應(yīng)的滿足一定內(nèi)存占用大小的DFA，用多個(gè)DFA來(lái)進(jìn)行正則表達(dá)式匹配，但這無(wú)法解決不少規(guī)則單條就會(huì)造成DFA狀態(tài)爆炸的問(wèn)題，也無(wú)法解決大規(guī)模情況下分組DFA太多而造成匹配性能過(guò)低的問(wèn)題；2)為了保證一定的正則表達(dá)式匹配性能，改動(dòng)正則表達(dá)式規(guī)則的語(yǔ)義以避免生成狀態(tài)爆炸的DFA，大大犧牲了正則表達(dá)式規(guī)則所描述特征的精確性；3)提取正則表達(dá)式規(guī)則中的近似精確串的部分作為預(yù)過(guò)濾規(guī)則，將一個(gè)集合中所有正則表達(dá)式規(guī)則對(duì)應(yīng)的預(yù)過(guò)濾規(guī)則構(gòu)造成DFA作為預(yù)過(guò)濾器，而將原來(lái)的正則表達(dá)式規(guī)則集合構(gòu)造成NFA作為匹配引擎，通過(guò)預(yù)過(guò)濾器來(lái)過(guò)濾到大部分確定不匹配的內(nèi)容，而只將疑似匹配的內(nèi)容傳給匹配引擎做精確匹配，但這無(wú)法保證匹配性能，好壞完全決定于匹配引擎是否被觸發(fā)。

而在學(xué)術(shù)界，關(guān)于正則表達(dá)式匹配的研究也非常熱門，代表性的方法如：基于FPGA平臺(tái)的NFA方法^{【R.Sidhu?and?V.K.Prasanna，“Fast?Regular?Expression?Matching?using?FPGAs，”Proc?of?IEEE?FCCM，2001】}，正則表達(dá)式規(guī)則分組方法^{【F.Yu，X.Chen，Y.Diao，T.V.Lakshman，and?R.H.Katz，“Fast?and?Memory-efficient?Regular?Expression?Matching?for?Deep?Packet?Inspection，”Proc.of?ACM/IEEE?ANCS，2006】}，DFA壓縮方法^{【Y.Qi，K.Wang，J.Fong，Y.Xue，J.Li，W.Jiang，and?V.Prasanna，“FEACAN：Front-end?Acceleration?for?Content-aware?Network?Processing，”Proc?of?IEEE?INFOCOM，2011】}，混合型有窮自動(dòng)機(jī)方法^{【M.Becchi?and?P.Crowley，“A?Hybri?Finite?Automaton?for?Practical?Deep?Packet?Inspection，”Proc.of?ACM?CoNEXT，2007】}以及擴(kuò)展型有窮自動(dòng)機(jī)方法^{【R.Smith，C.Estan，S.Jha，and?S.Kong，“Deflating?the?Big?Bang：Fast?and?Scalable?Deep?Packet?Inspection?with?Extended?Finite?Automata，”Proc.of?ACM?SIGCOMM，2008】}等，但是目前沒(méi)有一種已公開(kāi)的方法可以實(shí)際全面地解決正則表達(dá)式匹配存在的上述問(wèn)題。

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

(一)要解決的技術(shù)問(wèn)題

本發(fā)明要解決的技術(shù)問(wèn)題是：提供一種正則表達(dá)式匹配系統(tǒng)及匹配方法，其能夠提高正則表達(dá)式匹配的速度，并且具有較強(qiáng)的擴(kuò)展性。

(二)技術(shù)方案