[發(fā)明專利]并行正則表達(dá)式匹配器

在審

• 申請(qǐng)?zhí)枺?/td>: 202110632853.7
• 申請(qǐng)日: 2021-06-07
• 公開（公告）號(hào): CN113360726A
• 公開（公告）日: 2021-09-07
• 發(fā)明（設(shè)計(jì)）人: 茍鵬飛;陸泳;劉揚(yáng)帆;徐越;楊浩;施葹
• 申請(qǐng)（專利權(quán)）人: 青芯半導(dǎo)體科技（上海）有限公司
• 主分類號(hào): G06F16/903
• 分類號(hào): G06F16/903;G06F16/901
• 代理公司: 上海智晟知識(shí)產(chǎn)權(quán)代理事務(wù)所(特殊普通合伙) 31313
• 代理人: 張東梅

本發(fā)明提供了一種并行正則表達(dá)式匹配器，包括：軟件預(yù)編譯單元，被配置為將正則表達(dá)式規(guī)則集中的多個(gè)正則表達(dá)式規(guī)則進(jìn)行預(yù)編譯，轉(zhuǎn)換為符合硬件處理行為的格式的正則表達(dá)式規(guī)則，以供硬件匹配電路進(jìn)行匹配；硬件匹配電路，被配置為將待匹配報(bào)文和符合硬件處理行為的格式的正則表達(dá)式規(guī)則進(jìn)行匹配，得出匹配結(jié)果。

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

本發(fā)明涉及正則表達(dá)式技術(shù)領(lǐng)域，特別涉及一種并行正則表達(dá)式匹配器。

背景技術(shù)

正則表達(dá)式是由普通字符(字母/數(shù)字/符號(hào))以及特殊字符(又稱為“元字符”)組成的文字模式，用來描述在搜索文本時(shí)要匹配的一個(gè)或多個(gè)字符串。它被廣泛應(yīng)用于數(shù)據(jù)處理的各種領(lǐng)域。在高速度、大帶寬的網(wǎng)絡(luò)和數(shù)據(jù)庫(kù)應(yīng)用中，對(duì)正則表達(dá)式的處理速度提出了極高的要求。該要求主要包含兩方面：(1)待匹配數(shù)據(jù)的處理帶寬；(2)并行匹配的正則表達(dá)式數(shù)量。

目前的產(chǎn)品主要用軟件實(shí)現(xiàn)。知名的正則表達(dá)式匹配軟件(庫(kù))包含：POSIX REAPI，PCRE，Google RE2，Oniguruma，Hyperscan等。實(shí)現(xiàn)方法的核心是有限狀態(tài)自動(dòng)機(jī)，可分為確定性有限自動(dòng)機(jī)(DFA)，非確定性有限自動(dòng)機(jī)(NFA)以及它們的組合。例如圖1所示為一個(gè)對(duì)正則表達(dá)式a(b|c)*構(gòu)造出來的有限自動(dòng)機(jī)。每個(gè)圓圈代表一個(gè)狀態(tài)，雙線圓圈代表結(jié)束(匹配)狀態(tài)。當(dāng)文本的字符逐一輸入該自動(dòng)機(jī)時(shí)，如果當(dāng)前字符和箭頭上的字符相同，就可以按箭頭前進(jìn)到下一個(gè)狀態(tài)。如果能夠達(dá)到結(jié)束狀態(tài)，則表明發(fā)生一次匹配(Matched)。如果文本的所有字符掃描完時(shí)都沒能到達(dá)結(jié)束狀態(tài)，則說明沒有匹配。

軟件的正則表達(dá)式匹配特點(diǎn)是使用靈活，缺點(diǎn)是速度慢，并行處理能力有限。上述軟件(庫(kù))使用了一些方法例如對(duì)多個(gè)正則表達(dá)式進(jìn)行狀態(tài)圖歸并、多線程、分階段匹配、利用單指令多數(shù)據(jù)(SIMD)指令等來改善上述缺點(diǎn)，但是仍然無法滿足日益增長(zhǎng)的數(shù)據(jù)處理速度需求。舉例來說，目前速度最快的、被主流數(shù)據(jù)中心廠商廣泛采用的Hyperscan，可以達(dá)到7Gbit/秒的Snort正則表達(dá)式集的單線程匹配速度。但是，多線程并不能線性提速、待掃描文本的不同有時(shí)會(huì)顯著地影響速度。其它常用的正則表達(dá)式匹配軟件(庫(kù))往往只有幾十或幾百M(fèi)bit/秒的匹配速度。此外，如果想把正則表達(dá)式的處理嵌入于網(wǎng)絡(luò)處理設(shè)備或數(shù)字信號(hào)處理設(shè)備中，軟件算法也難以做到(上述設(shè)備往往沒有CPU或只有性能較低的微控制器)。

現(xiàn)有的正則表達(dá)式的數(shù)字電路實(shí)現(xiàn)，一般是單純的DFA(確定性有限狀態(tài)自動(dòng)機(jī))或NFA(非確定性有限狀態(tài)自動(dòng)機(jī))電路，對(duì)于單條正則表達(dá)式能夠達(dá)到較好的處理速度(例如幾Gbit/秒到幾十Gbit/s)，但當(dāng)正則表達(dá)式的數(shù)量增加時(shí)，速度以反比例快速下降。當(dāng)正則表達(dá)式數(shù)量為100這個(gè)數(shù)量級(jí)時(shí)，速度不如軟件，缺少實(shí)際應(yīng)用價(jià)值。

目前的產(chǎn)品/方法存在的問題是：軟件正則表達(dá)式實(shí)現(xiàn)使用靈活，但是速度較慢，跟不上現(xiàn)在高速網(wǎng)絡(luò)(25Gbps，100Gbps)或高速接口(PCIe Gen3x16)的數(shù)據(jù)輸入速度。現(xiàn)有的數(shù)字電路實(shí)現(xiàn)無法高效地同時(shí)處理多條正則表達(dá)式。

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

本發(fā)明的目的在于提供一種并行正則表達(dá)式匹配器，以解決現(xiàn)有的正則表達(dá)式速度較慢或無法并行處理的問題。

為解決上述技術(shù)問題，本發(fā)明提供一種并行正則表達(dá)式匹配器，包括：

軟件預(yù)編譯單元，被配置為將正則表達(dá)式規(guī)則集中的多個(gè)正則表達(dá)式規(guī)則進(jìn)行預(yù)編譯，轉(zhuǎn)換為符合硬件處理行為的格式的正則表達(dá)式規(guī)則，以供硬件匹配電路進(jìn)行匹配；

硬件匹配電路，被配置為將待匹配報(bào)文和符合硬件處理行為的格式的正則表達(dá)式規(guī)則進(jìn)行匹配，得出匹配結(jié)果。

可選的，在所述的并行正則表達(dá)式匹配器中，所述軟件預(yù)編譯單元包括拆分模塊、狀態(tài)歸并模塊和配置表模塊，其中：

所述拆分模塊用于將多個(gè)正則表達(dá)式規(guī)則拆分為純字符串和正則單元；