付文亮,郭 平,周 舟

(1.北京理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,北京 100081;2.中國(guó)科學(xué)院信息工程研究所信息內(nèi)容安全技術(shù)國(guó)家工程實(shí)驗(yàn)室,北京 100093)

?

一種面向100Gbps網(wǎng)絡(luò)的L7-filter硬件加速方法

付文亮1,郭 平1,周 舟2

(1.北京理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,北京 100081;2.中國(guó)科學(xué)院信息工程研究所信息內(nèi)容安全技術(shù)國(guó)家工程實(shí)驗(yàn)室,北京 100093)

L7-filter是當(dāng)前廣泛應(yīng)用的流量分類(lèi)系統(tǒng),其采用基于正則表達(dá)式匹配的深包檢測(cè)方法,通過(guò)檢測(cè)數(shù)據(jù)包有效載荷中存在的字符串特征對(duì)流量進(jìn)行分類(lèi).然而,由于計(jì)算復(fù)雜度高、存儲(chǔ)消耗大等原因,現(xiàn)有L7-filter軟硬件方法的處理性能?chē)?yán)重不足,不能適應(yīng)當(dāng)前40Gbps以及更高性能骨干網(wǎng)絡(luò).在對(duì)L7-filter的應(yīng)用層協(xié)議規(guī)則集進(jìn)行分析,總結(jié)其中廣泛存在的特征的基礎(chǔ)上,本文提出了一個(gè)硬件加速方法,其通過(guò)有針對(duì)性的數(shù)據(jù)模型、算法優(yōu)化、匹配架構(gòu)設(shè)計(jì)以提高流量分類(lèi)系統(tǒng)的處理能力.為了驗(yàn)證方法的可行性,采用了基于Virtex6的FPGA板卡實(shí)現(xiàn)原型系統(tǒng)并對(duì)其進(jìn)行評(píng)估.實(shí)驗(yàn)結(jié)果表明,原型系統(tǒng)的數(shù)據(jù)吞吐率可以達(dá)到約115Gbps.

流量分類(lèi);正則表達(dá)式匹配;100Gbps;FPGA

1 引言

隨著互聯(lián)網(wǎng)應(yīng)用進(jìn)一步發(fā)展,其逐漸滲透到人們生活的各個(gè)方面,為人類(lèi)生活提供了極大便利的同時(shí),也為網(wǎng)絡(luò)安全領(lǐng)域提出新的挑戰(zhàn).一方面,互聯(lián)網(wǎng)安全環(huán)境日趨復(fù)雜,針對(duì)網(wǎng)絡(luò)應(yīng)用漏洞而產(chǎn)生的木馬、蠕蟲(chóng)攻擊等惡意行為逐漸增多,現(xiàn)有網(wǎng)絡(luò)安全系統(tǒng)亟待加強(qiáng)針對(duì)網(wǎng)絡(luò)應(yīng)用的檢測(cè)能力,應(yīng)用層協(xié)議識(shí)別成為網(wǎng)絡(luò)安全、管理系統(tǒng)的核心功能之一[1];另一方面,隨著網(wǎng)絡(luò)接入帶寬遵循丹尼爾定律快速增長(zhǎng)[2](即每年增長(zhǎng)約50%),40Gbps及更高性能骨干網(wǎng)絡(luò)標(biāo)準(zhǔn)逐步普及,現(xiàn)有應(yīng)用層協(xié)議識(shí)別方法性能不足[3],成為制約相關(guān)網(wǎng)絡(luò)安全、管理系統(tǒng)發(fā)展的重要瓶頸.

L7-filter是當(dāng)前主流的應(yīng)用層協(xié)議識(shí)別系統(tǒng),其采用了基于正則表達(dá)式匹配的深包檢測(cè)方法對(duì)數(shù)據(jù)包有效載荷中的字符串特征進(jìn)行識(shí)別[3].由于具有識(shí)別率高、識(shí)別準(zhǔn)確率高等優(yōu)點(diǎn),L7-filter常被用于網(wǎng)絡(luò)安全相關(guān)系統(tǒng).然而,受其核心正則表達(dá)式匹配方法處理能力制約,現(xiàn)有L7-filter軟件檢測(cè)速率僅達(dá)到百兆級(jí)別[4].為了提高性能,正則表達(dá)式匹配加速方法成為研究熱點(diǎn).具體來(lái)看,現(xiàn)有加速方法分為基于通用處理器的軟件方法、基于特定處理器的軟件方法(如網(wǎng)絡(luò)處理器)、基于可編程芯片的方法等.

基于通用處理器的軟件方法主要利用硬件平臺(tái)處理器主頻高、內(nèi)存大等特點(diǎn),在Linux等開(kāi)源操作系統(tǒng)上通過(guò)標(biāo)準(zhǔn)編程語(yǔ)言進(jìn)行實(shí)現(xiàn).為了達(dá)到高性能,基于通用處理器的加速方法主要針對(duì)軟件算法進(jìn)行優(yōu)化,涉及壓縮狀態(tài)機(jī)[5]、合并狀態(tài)[6～8]、分組規(guī)則[9]等.然而,由于硬件平臺(tái)并行能力有限(匹配引擎數(shù)量有限,單引擎融合成百上千規(guī)則,造成狀態(tài)機(jī)爆炸)、代碼執(zhí)行效率不高等原因,該類(lèi)加速方法只能提供千兆級(jí)別吞吐率.

為了解決通用平臺(tái)并行性不足的問(wèn)題,研究者提出使用網(wǎng)絡(luò)處理器(Network Processor,NP)、圖像處理器(Graphic Processing Unit,GPU)、眾核處理器(Many-Core Processor)等專用處理平臺(tái)實(shí)現(xiàn)加速.由于計(jì)算核心數(shù)量較多,該類(lèi)型加速方法能夠運(yùn)行多個(gè)獨(dú)立匹配引擎,降低了每個(gè)引擎的狀態(tài)機(jī)規(guī)模.相關(guān)研究證明,基于眾核平臺(tái)[10]、GPU[11,12]的匹配方法性能可以達(dá)到萬(wàn)兆級(jí)別.然而,由于匹配引擎頻繁讀取存儲(chǔ)器、需要通過(guò)額外硬件接口與軟件驅(qū)動(dòng)獲取網(wǎng)絡(luò)數(shù)據(jù)等原因,該類(lèi)方法無(wú)法適用于40Gbps以及更高性能網(wǎng)絡(luò).

隨著信息技術(shù)的快速發(fā)展,具有天然并發(fā)性、豐富邏輯資源、高可擴(kuò)展性等優(yōu)勢(shì)的現(xiàn)場(chǎng)可編程邏輯門(mén)陣列(Field-Programmable Gate Array,FPGA)進(jìn)入人們視線.FPGA加速方法可分為兩類(lèi):基于存儲(chǔ)器和基于芯片邏輯資源.

基于存儲(chǔ)器的方法將狀態(tài)機(jī)跳轉(zhuǎn)規(guī)則和命中狀態(tài)存入存儲(chǔ)器,通過(guò)引擎查詢存儲(chǔ)器實(shí)現(xiàn)狀態(tài)機(jī)運(yùn)轉(zhuǎn).匹配時(shí),引擎根據(jù)輸入字符和當(dāng)前活躍狀態(tài)索引跳轉(zhuǎn)表以找到下一時(shí)刻活躍狀態(tài),并根據(jù)當(dāng)前活躍狀態(tài)索引命中狀態(tài)表以判斷是否匹配成功.為了提高系統(tǒng)吞吐率、增加規(guī)則支持的數(shù)量,相關(guān)研究主要從降低狀態(tài)機(jī)存取開(kāi)銷(xiāo)的角度出發(fā),針對(duì)狀態(tài)機(jī)跳轉(zhuǎn)的統(tǒng)計(jì)特性[13]、狀態(tài)跳轉(zhuǎn)輔助變量[4,14,15]、狀態(tài)機(jī)合并[16]等進(jìn)行優(yōu)化.通用存儲(chǔ)器的優(yōu)化也為該方法帶來(lái)一定性能提升[17].然而,由于頻繁讀取存儲(chǔ)器、重復(fù)設(shè)置匹配引擎導(dǎo)致計(jì)算復(fù)雜度增加等問(wèn)題,該類(lèi)加速方法處理能力不能滿足骨干網(wǎng)絡(luò)要求.

基于芯片邏輯資源的匹配方法通過(guò)將狀態(tài)機(jī)映射到FPGA可編程邏輯資源(如查找表和觸發(fā)器)實(shí)現(xiàn)匹配.為了達(dá)到高性能,Yamagaki N.等人對(duì)非確定有限狀態(tài)機(jī)(Nondeterministic Finite Automata,NFA)進(jìn)行擴(kuò)展[18],通過(guò)將1字符輸入非確定有限狀態(tài)機(jī)(如非特指,下文狀態(tài)機(jī)均特指非確定有限狀態(tài)機(jī))轉(zhuǎn)化為等價(jià)的多字符輸入狀態(tài)機(jī)以提高匹配引擎的處理能力.然而,由于多字符輸入狀態(tài)機(jī)在輸入字符寬度較大時(shí)存在狀態(tài)機(jī)規(guī)模膨脹的問(wèn)題,該方法僅僅適合輸入字符數(shù)量不超過(guò)8字符的情況,提供千兆級(jí)別處理能力[18].

由于不需要共享處理器、存儲(chǔ)器等硬件資源,基于FPGA邏輯資源的加速方法具有較高的并行性和優(yōu)化潛力.此外,該類(lèi)方法具有較低的生產(chǎn)與維護(hù)成本,且基于FPGA芯片的子系統(tǒng)更適合嵌入到相關(guān)網(wǎng)絡(luò)系統(tǒng).基于上述發(fā)展現(xiàn)狀,本文首先針對(duì)L7-filter規(guī)則集及多字符輸入狀態(tài)機(jī)規(guī)模膨脹問(wèn)題進(jìn)行研究,并有針對(duì)性的提出一個(gè)新型多字符輸入狀態(tài)機(jī),從數(shù)據(jù)模型角度出發(fā)降低狀態(tài)機(jī)規(guī)模及正則匹配的計(jì)算復(fù)雜度;然后,針對(duì)匹配模型的特點(diǎn),提出一個(gè)基于Bitmap的優(yōu)化方法,從算法角度進(jìn)一步降低匹配的計(jì)算復(fù)雜度;最后,提出一個(gè)適合FPGA芯片的高性能匹配架構(gòu),從具體實(shí)現(xiàn)角度出發(fā)提高加速方法的性能.

2 L7-filter規(guī)則集特征分析

正則表達(dá)式是描述字符串特征的有效工具,其每個(gè)字符或者為具體字符(如a,b等),或者為描述字符模式的元字符.L7-filter協(xié)議規(guī)則主要有兩種元字符:集合元字符和重復(fù)元字符.前者用于描述具體字符的集合(如元字符“.”代表匹配除“ ”外的任意一個(gè)具體字符);后者用于描述字符的重復(fù)模式(如元字符“*”代表前一字符重復(fù)1次或多次).從本質(zhì)看,元字符及多個(gè)元字符互相影響造成了正則匹配計(jì)算復(fù)雜度高、存儲(chǔ)消耗大等問(wèn)題[19].本節(jié)針對(duì)L7-filter規(guī)則集[20]進(jìn)行分析,找到其中廣泛存在的規(guī)則特征,并以此作為硬件加速方法的基礎(chǔ).其中,整個(gè)規(guī)則集包含了125條正則表達(dá)式,涵蓋了常用互聯(lián)網(wǎng)應(yīng)用,如P2P、聊天、游戲、郵件等.需要注意的是,本節(jié)探討的規(guī)則特征不僅適用于L7-filter規(guī)則集中已有的應(yīng)用協(xié)議,還體現(xiàn)了網(wǎng)絡(luò)應(yīng)用在通信中普遍存在和廣泛使用的特征.換句話說(shuō),本節(jié)提煉的規(guī)則特征具有一定的普適性.

2.1 特征起始位置

L7-filter協(xié)議特征主要由網(wǎng)絡(luò)通信中自定義的內(nèi)容類(lèi)型標(biāo)識(shí)、命令等關(guān)鍵字構(gòu)成.這些關(guān)鍵字往往被安排在數(shù)據(jù)包的固定位置以方便通信端進(jìn)行解析,例如FTP數(shù)據(jù)包的用戶有效載荷前三個(gè)字符通常是“220”.本文首先針對(duì)協(xié)議特征的起始位置是否固定進(jìn)行統(tǒng)計(jì),結(jié)果如表1所示.規(guī)則集中約76%協(xié)議特征從用戶有效載荷的第一個(gè)字符開(kāi)始.經(jīng)典的狀態(tài)機(jī)及其衍生算法并未針對(duì)這一規(guī)則特性進(jìn)行優(yōu)化.

為了提升性能,如果基于分而治之的思想對(duì)正則表達(dá)式進(jìn)行合理拆分,通過(guò)順序識(shí)別多個(gè)子特征達(dá)到檢測(cè)目的,則起始位置固定的協(xié)議特征往往具有較低的識(shí)別復(fù)雜度.

表1 L7-filter規(guī)則集起位置統(tǒng)計(jì)

2.2 重復(fù)元字符

重復(fù)元字符(如“*”,“+”等)是協(xié)議特征正則表達(dá)式的重要組成.由統(tǒng)計(jì)可知,L7-filter規(guī)則中約80%至少含有1個(gè)重復(fù)元字符;約10%含有5個(gè)以上重復(fù)元字符(個(gè)別協(xié)議規(guī)則甚至有16個(gè)).

為了考量L7-filter規(guī)則集對(duì)多字符輸入狀態(tài)機(jī)規(guī)模的影響,作者根據(jù)L7-filter的協(xié)議特征集生成輸入字寬不同的多字符輸入狀態(tài)機(jī),并對(duì)其狀態(tài)機(jī)規(guī)模(主要指跳轉(zhuǎn)數(shù)量)進(jìn)行統(tǒng)計(jì),結(jié)果如圖1所示.從趨勢(shì)來(lái)看,多字符輸入狀態(tài)機(jī)的跳轉(zhuǎn)數(shù)量隨著每周期處理字符數(shù)的增加指數(shù)增長(zhǎng);從具體數(shù)字來(lái)看,同單字符輸入狀態(tài)機(jī)相比,在每周期處理32字符情況下,多字符狀態(tài)機(jī)跳轉(zhuǎn)數(shù)量平均增長(zhǎng)500多倍;每周期處理128字符情況下,狀態(tài)機(jī)跳轉(zhuǎn)數(shù)量平均增長(zhǎng)超過(guò)百萬(wàn)倍.由于FPGA芯片硬件資源有限,多字符輸入狀態(tài)機(jī)數(shù)據(jù)模型僅能夠適用于每周期處理字符較少的情況.

為了進(jìn)一步明確重復(fù)元字符數(shù)量與狀態(tài)機(jī)膨脹的關(guān)系,我們將L7-filter規(guī)則集轉(zhuǎn)換為32字符輸入狀態(tài)機(jī),并根據(jù)其狀態(tài)機(jī)規(guī)模膨脹程度進(jìn)行分類(lèi)(同單字符輸入狀態(tài)機(jī)相比),如表2所示.狀態(tài)機(jī)跳轉(zhuǎn)數(shù)量膨脹率小于10的規(guī)則平均僅含有0.64個(gè)重復(fù)元字符;狀態(tài)機(jī)跳轉(zhuǎn)數(shù)量膨脹率超過(guò)10000倍的協(xié)議規(guī)則平均含有5.3個(gè)重復(fù)元字符.上述結(jié)果進(jìn)一步說(shuō)明重復(fù)元字符的數(shù)量是影響多字符輸入狀態(tài)機(jī)規(guī)模的重要因素.在L7-filter協(xié)議規(guī)則集條件下,如何提高單周期處理字符數(shù)量的同時(shí)控制狀態(tài)機(jī)規(guī)模是本文要解決的一個(gè)重要科研問(wèn)題.

表2 32字符輸入狀態(tài)機(jī)重復(fù)元字符數(shù)與跳轉(zhuǎn)數(shù)增長(zhǎng)關(guān)系

2.3 集合元字符

如表3所示,L7-filter的規(guī)則集中,帶有集合元字符的正則表達(dá)式比例為69%,且平均每條規(guī)則含有5個(gè)集合元字符.

表3 L7-filter規(guī)則集集合元字符統(tǒng)計(jì)

通常情況下,集合元字符與重復(fù)元字符配合可能導(dǎo)致匹配計(jì)算復(fù)雜度增加.例如,為了識(shí)別IMAP協(xié)議(其正則表達(dá)式為“^(〔 ok|a[0-9]+noop)”,匹配引擎識(shí)必須能夠識(shí)別字符集合[0-9]至少1次,至多上千次(受包長(zhǎng)限制),其狀態(tài)機(jī)規(guī)模與復(fù)雜度遠(yuǎn)大于非集合元字符的情況.

此外,如果采用拆分正則表達(dá)式、通過(guò)多個(gè)子狀態(tài)機(jī)配合識(shí)別協(xié)議特征,集合元字符與重復(fù)元字符配合還可能造成出現(xiàn)多個(gè)中間匹配結(jié)果的情況,具體問(wèn)題將在下節(jié)詳細(xì)分析.

3 基于Link-NFA的硬件加速方法

本節(jié)首先提出一個(gè)擴(kuò)展的多字符輸入狀態(tài)機(jī)模型,稱為L(zhǎng)ink-NFA;然后,針對(duì)Link-NFA的特點(diǎn)提出一個(gè)基于Bitmap的優(yōu)化方法;最后,提出一個(gè)適合FPGA的高性能匹配架構(gòu),從實(shí)現(xiàn)角度出發(fā)提高匹配性能.

3.1 Link-NFA

Link-NFA對(duì)已有狀態(tài)機(jī)模型進(jìn)行擴(kuò)展,使用多個(gè)相關(guān)聯(lián)的多字符輸入狀態(tài)機(jī)(簡(jiǎn)稱Sub-NFA)對(duì)正則表達(dá)式進(jìn)行識(shí)別.Sub-NFA每周期可以處理k個(gè)字符,最多有1個(gè)指向其起始狀態(tài)的重復(fù)跳轉(zhuǎn)(處理k個(gè)相同的字符,該字符稱為BRPT).多個(gè)Sub-NFA之間通過(guò)Link跳轉(zhuǎn)承接邏輯關(guān)系,且后續(xù)Sub-NFA的首個(gè)狀態(tài)均有1個(gè)重復(fù)跳轉(zhuǎn).

Link-NFA可以由9元組{S,∑,s0,F,k,σbasic,σlink,L,θ}表示,其中:S為狀態(tài)集合;∑為輸入字符集合;s0為起始狀態(tài)集合;F為結(jié)束狀態(tài)集合;k為每周期處理字符數(shù)量;σbasic為Sub-NFA內(nèi)部跳轉(zhuǎn)函數(shù):S×∑k→Sσlink為跨越Sub-NFA跳轉(zhuǎn)函數(shù)S→S;L標(biāo)識(shí)當(dāng)前輸入的k字符中,哪些已經(jīng)被處理;θ為輸入替換函數(shù):S×∑k×L×BRPT→∑k.

圖2為表達(dá)式“mnp*q+s”對(duì)應(yīng)2字符輸入Link-NFA范例.Link-NFA根據(jù)兩個(gè)跳轉(zhuǎn)函數(shù)決定下一活躍狀態(tài):σbasic和σlink.如果當(dāng)前狀態(tài)不是某Sub-NFA的最終狀態(tài),則使用σbasic函數(shù)確定下一活躍狀態(tài)且其在本Sub-NFA中;否則使用σlink函數(shù)確定下一活躍狀態(tài)且其在后續(xù)Sub-NFA中(跨Sub-NFA).

如果當(dāng)前Sub-NFA僅處理了當(dāng)前k字符輸入的前L個(gè)字符,則后續(xù)Sub-NFA應(yīng)當(dāng)跳過(guò)已經(jīng)被處理的字符繼續(xù)匹配.Link-NFA使用替換函數(shù)θ完成上述工作.具體來(lái)說(shuō),函數(shù)θ使用L個(gè)后續(xù)Sub-NFA的BRPT來(lái)替換當(dāng)前輸入中已經(jīng)被處理的前L個(gè)字符,并將L與更新過(guò)的輸入傳遞給后續(xù)Sub-NFA.

基于Link-NFA的正則表達(dá)式匹配方法見(jiàn)算法1.每匹配周期開(kāi)始時(shí),REGEX-MATCH-TOP函數(shù)從Input-Buffer讀取k個(gè)字符,并從Link-NFA起始狀態(tài)或本周期活躍狀態(tài)開(kāi)始調(diào)用PROC-INPUT函數(shù)進(jìn)行匹配.PROC-INPUT函數(shù)根據(jù)當(dāng)前活躍狀態(tài)、輸入k字符、已處理字符個(gè)數(shù)和跳轉(zhuǎn)函數(shù)σbasic找到下一時(shí)刻活躍狀態(tài).需要注意的是,如果下一活躍狀態(tài)是某Sub-NFA的結(jié)束狀態(tài)(非Link-NFA結(jié)束狀態(tài)),則需要調(diào)用σlink以找到后繼Sub-NFA,并標(biāo)記當(dāng)前輸入k字符中已經(jīng)被處理過(guò)的字符.匹配過(guò)程中,系統(tǒng)不斷遞歸調(diào)用PROC-INPUT函數(shù)直到某處理周期輸入的k字符全部被處理完成或者匹配成功.

圖3描述了如何用Link-NFA處理字符串“mmnpqqqs”.其中,對(duì)應(yīng)2字符輸入Link-NFA狀態(tài)機(jī)的信息如圖2所示.每個(gè)處理周期開(kāi)始時(shí),系統(tǒng)從緩沖區(qū)讀取2個(gè)字符.匹配從狀態(tài)S0開(kāi)始,并根據(jù)σbasic激活狀態(tài)S0和S1(處理周期1結(jié)束).由于輸入字符已處理完畢,系統(tǒng)從緩存區(qū)再讀取2個(gè)字符,并根據(jù)其中第1個(gè)字符和σbasic激活S2.由于S2是Sub-NFA1的最終狀態(tài),所以根據(jù)S2與σlink激活S3(Sub-NFA2的第1個(gè)狀態(tài)).同時(shí),由于僅處理了當(dāng)前輸入的1個(gè)字符,所以L置為1.根據(jù)更新函數(shù),系統(tǒng)將輸入“np”替換為“pp”,并依照當(dāng)前狀態(tài)S3和σbasic激活狀態(tài)S3(處理周期2結(jié)束).系統(tǒng)按照上述邏輯繼續(xù)匹配,直到最終狀態(tài)S6被激活,并報(bào)告匹配成功.

3.2 Link-NFA構(gòu)造方法

圖4為構(gòu)造Link-NFA的流程圖,其中包含如下4個(gè)步驟:

(1)根據(jù)經(jīng)典算法將正則表達(dá)式轉(zhuǎn)換為NFA[19];

(2)將NFA拆分為Split-NFA,每個(gè)Split-NFA僅包含1個(gè)重復(fù)跳轉(zhuǎn),且彼此通過(guò)Link跳轉(zhuǎn)相連.需要注意的是,為了保證邏輯完整,接連的Split-NFA有1個(gè)狀態(tài)重疊.圖5為Split-NFA的范例,子圖a,b分別為拆分前、后對(duì)應(yīng)的狀態(tài)機(jī),虛線為連接子狀態(tài)機(jī)的Link跳轉(zhuǎn);

(3)將Split-NFA轉(zhuǎn)換為k字符輸入狀態(tài)機(jī)[18],且轉(zhuǎn)換時(shí)不考慮Link跳轉(zhuǎn);

(4)標(biāo)記每個(gè)跳轉(zhuǎn)可以處理的字符數(shù)量,從而完成Link-NFA構(gòu)造.

3.3 優(yōu)化Link-NFA

在Link-NFA模型中,Sub-NFA相對(duì)規(guī)整,其典型模式如圖6所示.從硬件成本來(lái)看,實(shí)現(xiàn)圖6所示Sub-NFA共需實(shí)現(xiàn)130個(gè)跳轉(zhuǎn),每個(gè)跳轉(zhuǎn)匹配數(shù)量不同的字符,其消耗硬件邏輯資源量也不同.為了便于量化,我們用所需匹配字符的數(shù)量作為衡量硬件資源消耗的指標(biāo).圖6所示Sub-NFA共需要匹配8512個(gè)字符的硬件資源,其中每周期輸入的128個(gè)字符分別與不同數(shù)量的BRPT比較占了其中很大一部分.

考慮某時(shí)刻輸入,如圖7所示,其由三個(gè)部分組成:已處理,軟匹配和硬匹配.已處理部分長(zhǎng)度由L標(biāo)識(shí)(已知);軟處理由不同數(shù)量的BRPT組成;硬處理輸入部分實(shí)質(zhì)決定下一活躍狀態(tài).為了降低成本,作者使用基于Bitmap的方法快速跳過(guò)軟處理部分,直接從硬處理部分進(jìn)行匹配,從而降低實(shí)現(xiàn)狀態(tài)機(jī)的硬件成本.

具體來(lái)說(shuō),優(yōu)化算法先針對(duì)當(dāng)前k字符輸入和BRPT生成k-bit Bitmap:如果輸入的第i個(gè)字符是BRPT,則Bitmap的第i個(gè)位為1,否則為0.然后,通過(guò)查找Bitmap中第L位以后的第1個(gè)0bit即找到硬匹配的起始位置.優(yōu)化后算法的匹配成本主要由三部分組成:生成Bitmap、找到其中第1個(gè)0bit以及比對(duì)硬匹配部分的字符.進(jìn)行優(yōu)化后,實(shí)現(xiàn)圖6所示狀態(tài)機(jī)共需要匹配1162字符(三部分各匹配128,1032及2字符).同未優(yōu)化相比,降低硬件資源消耗約86.3%.

需要注意的是,優(yōu)化方法僅適用于軟處理與硬處理部分劃分清晰的情況,即BRPT不包含硬處理部分的首字符(圖7中B1).否則該優(yōu)化方法不適用.例如,BRPT為‘a(chǎn)ny’(即匹配任意字符)且當(dāng)前輸入中有多個(gè)滿足Sub-NFA邏輯的子串,則可能在該Sub-NFA產(chǎn)生多個(gè)中間匹配結(jié)果,每一個(gè)結(jié)果對(duì)應(yīng)一個(gè)不同的L.這一問(wèn)題將在后續(xù)章節(jié)分析解決.

3.4 Link-NFA匹配架構(gòu)

在Link-NFA中,每個(gè)Sub-NFA僅負(fù)責(zé)識(shí)別正則表達(dá)式的一部分.為了達(dá)到匹配的高性能,本文提出一個(gè)基于流水線的匹配架構(gòu),如圖8所示.其中各條流水線用于處理起始位置在不同階段的匹配進(jìn)程.如果某周期處理完輸入字符后激活了Stage-2中的狀態(tài),則被激活狀態(tài)應(yīng)當(dāng)“下移”至流水線Line 2等待下一處理周期繼續(xù)匹配.

此外,考慮到BRPT為‘a(chǎn)ny’(即匹配任意字符)且當(dāng)前輸入中有多個(gè)滿足Sub-NFA邏輯的子串的情況,其可能產(chǎn)生多個(gè)匹配結(jié)果.由于流水線各階段單周期只能處理一個(gè)輸入,Link-NFA匹配架構(gòu)應(yīng)當(dāng)在該Sub-NFA與后續(xù)Sub-NFA之間連接隊(duì)列以存儲(chǔ)中間結(jié)果.針對(duì)同批次k字符輸入,中間結(jié)果具有不同的L.Sub-NFA是否可能產(chǎn)生多個(gè)匹配結(jié)果由其對(duì)應(yīng)的正則表達(dá)式邏輯決定.使用隊(duì)列帶來(lái)的額外資源消耗將在下一節(jié)詳細(xì)進(jìn)行評(píng)估.

4 評(píng)估

評(píng)估從理論分析和實(shí)際測(cè)量?jī)蓚€(gè)角度進(jìn)行.首先,將L7-filter的協(xié)議規(guī)則集轉(zhuǎn)換為每周期處理字符數(shù)量不同的Link-NFA,對(duì)狀態(tài)機(jī)跳轉(zhuǎn)數(shù)量及其增長(zhǎng)趨勢(shì)進(jìn)行統(tǒng)計(jì),并與多字符狀態(tài)機(jī)進(jìn)行對(duì)比,從理論上對(duì)Link-NFA狀態(tài)機(jī)的規(guī)模與計(jì)算復(fù)雜度進(jìn)行分析.然后,實(shí)現(xiàn)了基于Link-NFA的硬件原型系統(tǒng),并針對(duì)原型的實(shí)現(xiàn)成本、檢測(cè)效率進(jìn)行測(cè)量與分析.其中主要考察原型系統(tǒng)的硬件資源成本、可擴(kuò)展性、處理能力、延遲等關(guān)鍵參數(shù).

為了達(dá)到上述目的,作者首先基于Linux系統(tǒng)和Python語(yǔ)言搭建了Link-NFA編譯系統(tǒng),其可以將正則表達(dá)式轉(zhuǎn)換為基于硬件描述語(yǔ)言的Link-NFA狀態(tài)機(jī);然后使用Xilinx Design Suite 13軟件和Virtex6 xc6vlx550t可編程芯片平臺(tái)實(shí)現(xiàn)了基于Link-NFA的硬件原型.為了獲取原型系統(tǒng)的關(guān)鍵性能(如處理延遲等),作者采用基于NetFPGA的數(shù)據(jù)流產(chǎn)生器[21]發(fā)送、標(biāo)記數(shù)據(jù)包,并通過(guò)對(duì)比標(biāo)記獲得相關(guān)參數(shù).

4.1 跳轉(zhuǎn)數(shù)量

狀態(tài)機(jī)跳轉(zhuǎn)數(shù)量直接決定其匹配算法的計(jì)算復(fù)雜度.圖9描述了Link-NFA與多字符輸入狀態(tài)機(jī)跳轉(zhuǎn)數(shù)量膨脹度與每周期處理字符數(shù)量的關(guān)系.

從具體數(shù)字來(lái)看,每周期處理32字符時(shí),Link-NFA狀態(tài)機(jī)跳轉(zhuǎn)數(shù)量增長(zhǎng)近32倍,其膨脹率比多字符輸入狀態(tài)機(jī)低了1個(gè)數(shù)量級(jí);每周期處理128字符時(shí),狀態(tài)機(jī)跳轉(zhuǎn)數(shù)量增長(zhǎng)100多倍,其膨脹率比多字符狀態(tài)機(jī)低了3-4個(gè)數(shù)量級(jí).

從增長(zhǎng)趨勢(shì)來(lái)看,多字符輸入狀態(tài)機(jī)跳轉(zhuǎn)數(shù)量與其每周期處理字符數(shù)量近似指數(shù)關(guān)系;Link-NFA中跳轉(zhuǎn)數(shù)量與其每周期處理字符近似線性關(guān)系.這一結(jié)果符合Link-NFA的設(shè)計(jì)預(yù)期,即通過(guò)多個(gè)子狀態(tài)機(jī)對(duì)重復(fù)元字符進(jìn)行隔離,避免多個(gè)重復(fù)元字符在多字符輸入狀態(tài)機(jī)轉(zhuǎn)換時(shí)互相影響,從而降低狀態(tài)機(jī)規(guī)模膨脹.由上述結(jié)果和分析可知,同多字符輸入狀態(tài)機(jī)相比,Link-NFA可以有效降低狀態(tài)機(jī)膨脹規(guī)模,更適應(yīng)輸入字符數(shù)量較多的情況.

4.2 FPGA資源使用率

為了驗(yàn)證Link-NFA的可用性,作者實(shí)現(xiàn)了輸入字符寬度不同的Link-NFA匹配引擎,并對(duì)其資源消耗情況進(jìn)行統(tǒng)計(jì),結(jié)果如圖10所示.總的來(lái)看,硬件原型系統(tǒng)消耗的查找表資源與輸入字符數(shù)量近似線性關(guān)系.每周期處理128個(gè)字符時(shí),FPGA芯片的查找表資源使用率約為15%.實(shí)驗(yàn)結(jié)果與跳轉(zhuǎn)數(shù)量增長(zhǎng)趨勢(shì)一致:跳轉(zhuǎn)數(shù)量越多,計(jì)算復(fù)雜度就越高,查找表使用率隨之增加.實(shí)驗(yàn)過(guò)程中芯片觸發(fā)器資源使用率始終在10%左右,其與狀態(tài)機(jī)的狀態(tài)數(shù)目相關(guān)且不隨Link-NFA輸入字符數(shù)量增加而顯著變化.

針對(duì)Sub-NFA可能產(chǎn)生多個(gè)匹配結(jié)果的情況,作者使用基于片上存儲(chǔ)器的隊(duì)列對(duì)中間數(shù)據(jù)進(jìn)行緩存.在原型系統(tǒng)中共使用了約45個(gè)18Kbits片上存儲(chǔ)器模塊,占總數(shù)的7.1%,遠(yuǎn)小于實(shí)現(xiàn)復(fù)雜計(jì)算的查找表使用率.此外,片上存儲(chǔ)器的使用率與協(xié)議規(guī)則本身有關(guān),不受輸入字符數(shù)量的影響.

從協(xié)議實(shí)現(xiàn)數(shù)量來(lái)看,本文使用的Xilinx Virtex6 xc6vlx550t芯片最多可以支持約850條應(yīng)用層協(xié)議的識(shí)別.如果使用硬件資源更多的Virtex7系列FPGA,則協(xié)議支持?jǐn)?shù)量最高能達(dá)到約4000.考慮到常用協(xié)議數(shù)量,Link-NFA完全可以支持對(duì)當(dāng)前主流網(wǎng)絡(luò)應(yīng)用的識(shí)別.

由上述分析可知,現(xiàn)有芯片技術(shù)完全可以支撐每周期輸入128字符的Link-NFA匹配引擎.大跨度(每周期處理字符較多)Link-NFA具有可實(shí)現(xiàn)性.

4.3 吞吐率

系統(tǒng)吞吐率是正則表達(dá)式匹配引擎的重要參數(shù),其直接關(guān)系到網(wǎng)絡(luò)檢測(cè)設(shè)備的在線處理能力.具體來(lái)說(shuō),基于FPGA的協(xié)議識(shí)別系統(tǒng)吞吐率T由以下公式?jīng)Q定:

T=Freq×N×8

其中Freq為匹配引擎的實(shí)際工作頻率,N為每周期處理的字符數(shù)量,8為字符轉(zhuǎn)換為比特的常量.因此,基于Link-NFA的匹配方法是否能夠達(dá)到高吞吐率還取決于系統(tǒng)工作頻率.

圖11為每周期處理不同字符數(shù)量的情況下,原型系統(tǒng)能夠達(dá)到的最低工作頻率與吞吐率.從趨勢(shì)上看,系統(tǒng)工作頻率隨著每周期處理字符數(shù)量增加而降低.這主要是因?yàn)長(zhǎng)ink-NFA跳轉(zhuǎn)數(shù)量增加導(dǎo)致計(jì)算復(fù)雜度增長(zhǎng),進(jìn)而導(dǎo)致芯片布局布線復(fù)雜度增大.然而,由吞吐率來(lái)看,頻率降低的負(fù)面影響遠(yuǎn)小于增加每周期字符處理數(shù)量帶來(lái)的性能提升,原型系統(tǒng)吞吐率單調(diào)遞增并在每周期處理128字符時(shí)達(dá)到性能最大值.此時(shí)系統(tǒng)工作頻率約為113MHz,吞吐率約為115Gbps,達(dá)到設(shè)計(jì)初衷.

表4對(duì)L7-filter軟件方法、本文提出的硬件加速方法以及其他平臺(tái)有代表性算法的性能進(jìn)行對(duì)比.由數(shù)據(jù)可知,本文提出的方法處理能力是L7-filter軟件方法的100多倍;同已有基于FPGA平臺(tái)的Lookahead方法相比,性能提高了約3.38倍.因此,本文提出的方法具有先進(jìn)性,且其可以滿足當(dāng)前產(chǎn)業(yè)界對(duì)應(yīng)用層協(xié)議識(shí)別方法的性能需求.

表4 性能比較

4.4 處理延遲

處理延遲指系統(tǒng)處理1個(gè)數(shù)據(jù)包所需的平均時(shí)間.處理延遲的大小直接關(guān)系到該類(lèi)型應(yīng)用層識(shí)別系統(tǒng)是否適合在線部署.我們對(duì)原型系統(tǒng)的處理延遲進(jìn)行測(cè)量,并與L7-filter的軟件方法進(jìn)行比較,結(jié)果如表5所示.在整個(gè)測(cè)量過(guò)程中,Link-NFA 始終保持較低延遲,其平均值為0.41us,相對(duì)L7-filter軟件方法的加速比約為587.4.上述結(jié)果主要由以下兩個(gè)原因.首先,FPGA芯片可以直接讀取網(wǎng)口數(shù)據(jù),避免了由數(shù)據(jù)總線、網(wǎng)卡接口、驅(qū)動(dòng)等帶來(lái)的延遲.其次,Link-NFA最高可以工作在113MHz,其最多15周期處理1個(gè)數(shù)據(jù)包(受重復(fù)元字符數(shù)量影響),相對(duì)軟件方法處理效率更高.

表5 處理延遲對(duì)比

5 結(jié)論與展望

本文提出了一個(gè)高效的硬件加速方法,其通過(guò)合理的數(shù)據(jù)結(jié)構(gòu)、基于Bitmap優(yōu)化方法和專用匹配架構(gòu)以提高流量分類(lèi)系統(tǒng)的處理能力.使用基于Virtex6 FPGA板卡對(duì)匹配方法進(jìn)行驗(yàn)證的結(jié)果表明,本文所提出的方法可以提供約115Gbps吞吐率.在現(xiàn)有技術(shù)條件下同已有FPGA算法相比,本文提出的方法要快約3.38倍.

由網(wǎng)絡(luò)安全領(lǐng)域發(fā)展趨勢(shì)可知,傳統(tǒng)角色單一的防火墻、入侵檢測(cè)系統(tǒng)已經(jīng)不適合當(dāng)前日趨復(fù)雜的網(wǎng)絡(luò)環(huán)境.具備應(yīng)用層協(xié)議識(shí)別、防火墻、入侵檢測(cè)、網(wǎng)絡(luò)管理等多重角色的新型網(wǎng)絡(luò)安全設(shè)備成為未來(lái)發(fā)展的重要趨勢(shì).例如,我國(guó)新一代網(wǎng)絡(luò)防火墻標(biāo)準(zhǔn)就將應(yīng)用層協(xié)議識(shí)別作為其核心功能之一.本文提出的加速方法立足于產(chǎn)業(yè)界未來(lái)5～10年需求,從研制子系統(tǒng)的角度出發(fā),提出高性能應(yīng)用層協(xié)議識(shí)別方法,適合嵌入復(fù)合型網(wǎng)絡(luò)安全設(shè)備,順應(yīng)了未來(lái)復(fù)合型網(wǎng)絡(luò)安全系統(tǒng)發(fā)展趨勢(shì),具有較高的產(chǎn)業(yè)價(jià)值與科研價(jià)值.

同基于軟件、專用處理器等方法比,本文提出的方法具有吞吐率高、能耗低、空間小等特點(diǎn),不僅適合骨干網(wǎng)、數(shù)據(jù)中心等應(yīng)用場(chǎng)景,還適合物聯(lián)網(wǎng)、車(chē)聯(lián)網(wǎng)等應(yīng)用場(chǎng)景.后續(xù)研究可以從理論與具體應(yīng)用兩方面深入進(jìn)行.在理論方面,可針對(duì)Link-NFA本身的問(wèn)題進(jìn)行深入優(yōu)化,探索Sub-NFA可能產(chǎn)生多個(gè)匹配結(jié)果、如何進(jìn)一步降低匹配引擎硬件資源消耗、將字符輸入數(shù)目進(jìn)一步擴(kuò)展到整個(gè)數(shù)據(jù)包等問(wèn)題,進(jìn)一步提高Link-NFA與硬件加速器的效率.在實(shí)際應(yīng)用方面,考慮研制專用協(xié)議識(shí)別芯片,將所提出的L7-filter加速方法嵌入到實(shí)際設(shè)備中,并根據(jù)測(cè)量與應(yīng)用結(jié)果對(duì)其進(jìn)行改進(jìn).

[1]GA/T1177-2014,信息安全技術(shù) 第二代防火墻安全技術(shù)要求[S].

[2]J.Nielsen.Nielsen’s law of internet bandwidth[EB/OL].http://www.nngroup.com/articles/law-of-bandwidth/,2015-3-12.

[3]Application layer packet classifier for Linux[EB/OL].http://l7-filter.sourceforge.net/,2005-02-18.

[4]付文亮,嵩天,周舟.RocketTC 一個(gè)基于FPGA的高性能網(wǎng)絡(luò)流量分類(lèi)架[J].計(jì)算機(jī)學(xué)報(bào),2014,37(2):414-422.FU Wen-liang,SONG Tian,ZHOU Zhou.RocketTC:A high throughput traffic classification architecture on FPGA[J].Chinese Journal of Computers,2014,37(2):414-422.(in Chinese)

[5]Antonello Rafael,et al.Design and optimizations for efficient regular expression matching in DPI systems[J].Proceedings of Computer Communications,2015,61:103-120.

[6]Wang Kai,Zhe Fu,Xiaohe Hu,and Jun Li.Practical regular expression matching free of scalability and performance barriers [J].Proceedings of Computer Communications 2014:97-119.

[7]Wang Jianhua,et al.A regular expression matching algorithm based on high-efficient finite automaton[J].Proceedings of Journal of Computing Science and Engineering,2014:78-86.

[8]WANG X,et al.StriFA:Stride finite automata for high-speed regular expression matching in network intrusion detection systems[J].IEEE Systems Journal,2013,7(3):374-384.

[9]Liu Tingwen,et al.Towards fast and optimal grouping of regular expressions via DFA size estimation[J].IEEE Journal on Selected Areas in Communications,2014,32(10):1797-1809.

[10]Shukla Surendra Kumar,et al.A survey of approaches used in parallel architectures and multi-core processors[J].For Performance Improvement.Proceedings of Progress in Systems Engineering,2015:537-545.

[11]Vasiliadis Giorgos,et al.GASPP:a GPU-accelerated stateful packet processing framework[A].Proceedings of 2014 USENIX Conference on Annual Technical Conference[C].Philadelphia:USENIX,2014.321-332.

[12]FEITOZA SANTOS A,et al.Multigigabit traffic identification on GPU [A].Proceedings of the First Edition Workshop on High Performance and Programmable Networking[C].New York:ACM,2013.39-44.

[13]Van Lunteren J,et al.Hardware-accelerated regular expression matching at multiple tens of gb/s[A].Proceedings of 31th IEEE INFOCOM[C].New York:ACM,2013.1737-1745.

[14]Smith R,et al.XFA:faster signature matching with extended automata[A].Proceedings of IEEE Symposium on Security and Privacy (S & P)[C].New York:IEEE,2008.187-201.

[15]Becchi M and Cadami S.Memory-efficient regular expression search using state merging[A].Proceedings of IEEE INFOCOM[C].New York:ACM,2007.1064-1072.

[16]Bando M,et al.Scalable lookahead regular expression detection system for deep packet inspection[J].IEEE/ACM Trans on Networking,2012,20(3):699-714.

[17]余慧,王健.一種專用可重配置的FPGA嵌入式存儲(chǔ)器模塊的設(shè)計(jì)和實(shí)現(xiàn)[J].電子學(xué)報(bào),2012,40 (2):215-222.

YU Hui,WANG Jian.The design and implement of a special reconfigureable FPGA embedded BRAM[J].Acta Electronica Sinica,2012,40(2):215-222.(in Chinese)

[18]Yamagaki N,Sidhu R,Kamiya S.High-speed regular expression matching engine using multi-character NFA[A].Proceedings of IEEE Field Programmable Logic and Applications[C].New York:ACM,2008.131-136.

[19]HOPCROFT J E.Introduction to Automata Theory,Languages,and Computation[M].3rd ed,Addison-Wesley Longman Publishing Co,Inc,2006.

[20]Regular expression patterns for L7-filter[EB/OL].http://l7-filter.sourceforge.net/protocols,2015-03-12.

[21]NetFPGA [OL].http://netfpga.org.2015-07-20.

[22]Wang L,et al.Gregex:GPU based high speed regular expression matching engine[A].Proceedings of IEEE Innovative Mobile and Internet Services in Ubiquitous Computing [C].New York:IEEE,2011.366-370.

付文亮 男,1984年出生于河北邯鄲市.現(xiàn)為北京理工大學(xué)計(jì)算機(jī)學(xué)院在讀博士生.主要從事高性能網(wǎng)絡(luò)、網(wǎng)絡(luò)安全、節(jié)能等領(lǐng)域關(guān)鍵技術(shù)研究.

郭 平(通信作者) 男，1957年出生,現(xiàn)為北京理工大學(xué)計(jì)算機(jī)學(xué)院教授,博士生導(dǎo)師.主要從事智能計(jì)算及其應(yīng)用研究.

E-mail:pguo@bit.edu.cn

周 舟 男，1983年出生,現(xiàn)為中國(guó)科學(xué)院信息工程研究所高級(jí)工程師.主要從事高性能網(wǎng)絡(luò)及網(wǎng)絡(luò)安全相關(guān)領(lǐng)域研究.

A Hardware-Accelerated L7-filter Method for 100Gbps Networks

FU Wen-liang1,GUO Ping1,ZHOU Zhou2

(1.SchoolofComputerScienceandTechnology,BeijingInstituteofTechnology,Beijing100081,China; 2.NationalEngineeringLaboratoryforInformationSecurityTechnologies,InstituteofInformationEngineering,ChineseAcademyofSciences,Beijing100093,China)

L7-filter is a widely used traffic classification system which relies on regular expression matching based deep packet inspect method and can identify network traffic by inspecting string patterns hidden in the packet payload.However,due to considerable computation and storage expenditures,existing L7-filter software and hardware solutions could not offer sufficient performance in the context of 40 Gbps and higher speed networks.Based on analysis of common features of the L7-filter protocol patterns,this paper proposes a hardware-accelerated method which is for achieving high performance and includes customized data structure,optimization and matching architecture.To validate the proposed method,a hardware prototype on Virtex 6 FPGA card is implemented and tested.Experimental results show that the prototype can scan network traffic at a typical rate of about 115Gbps.

traffic classification;regular expression matching;100Gbps;FPGA

2015-04-07;

2015-08-17；責(zé)任編輯：藍(lán)紅杰

國(guó)家自然科學(xué)基金(No.61402474)

TP393

A

0372-2112 (2016)11-2561-08

??學(xué)報(bào)URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.11.001