丁麟軒，黃昆，張大方

(1. 湖南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長沙 410082；2. 中國科學(xué)院 計算技術(shù)研究所，北京 100190)

1 引言

近年來，隨著網(wǎng)絡(luò)應(yīng)用的日益增多，網(wǎng)絡(luò)安全面臨著越來越嚴峻的挑戰(zhàn)。網(wǎng)絡(luò)入侵檢測與防御系統(tǒng)（NIDPS, network intrusion detection/prevention system）是網(wǎng)絡(luò)安全防御的主要手段，它通過實時監(jiān)測網(wǎng)絡(luò)流量，檢查和阻止網(wǎng)絡(luò)攻擊[1]。深度分組檢測[2]（DPI, deep packet inspection）是 NIDPS、防火墻和應(yīng)用層交換機的核心部件，不僅檢查數(shù)據(jù)分組的頭部信息，而且檢查數(shù)據(jù)分組的有效載荷。由于正則表達式具有豐富和靈活的表達能力，目前主流的 NIDPS，例如 Snort[3]、Bro[4]、TippingPoint[5]、Cisco[6]廣泛采用正則表達式匹配算法進行DPI操作。

三態(tài)內(nèi)容可尋址存儲器（TCAM, ternary content addressable memory）是一種快速并行查找的專門硬件。TCAM在一個時鐘周期內(nèi)并行查找所有表項，返回與關(guān)鍵字匹配的第一條表項的地址。TCAM具備三態(tài)表示特性，即TCAM表項可存儲0、1和“*”，其中“*”表示無關(guān)位，可以匹配0或1。在網(wǎng)絡(luò)處理應(yīng)用中，TCAM通常與靜態(tài)隨機存儲器（SRAM,static random access memory）結(jié)合在一起使用，在關(guān)鍵字查找匹配成功后，TCAM將匹配的表項地址發(fā)送到SRAM，輸出SRAM中保存的相應(yīng)信息。與TCAM相比，SRAM的存儲空間大且能耗低。

近年來，研究者提出了多種基于TCAM的正則表達式匹配算法[7～9]，實現(xiàn)線速 DPI。基于 TCAM的正則表達式匹配算法采用 TCAM 表示確定型有限自動機（DFA, deterministic finite automaton），即將狀態(tài)遷移表的每條狀態(tài)遷移邊存儲在一條TCAM表項中，每條表項由TCAM和SRAM兩部分組成：源狀態(tài)和輸入字符存儲在TCAM部分，目的狀態(tài)及其他相關(guān)信息存儲在與TCAM部分對應(yīng)的 SRAM部分?；赥CAM的正則表達式匹配算法的查找過程如下：首先，將當前狀態(tài)和輸入字符組合成一個關(guān)鍵字，在TCAM中查找與該關(guān)鍵字匹配的表項；然后，根據(jù)匹配的表項地址，訪問相應(yīng)的SRAM部分，獲取遷移的目的狀態(tài)；最后，將目的狀態(tài)作為當前狀態(tài)，讀入下一個輸入字符，重復(fù)執(zhí)行相似的TCAM查找，直至輸入字符結(jié)束。

已有基于 TCAM 的正則表達式匹配算法主要關(guān)注減少TCAM存儲開銷，很少關(guān)注減少TCAM能耗。TCAM雖然匹配查找速率快，但是存在能耗高等缺點。在正則表達式匹配中，導(dǎo)致TCAM高能耗的原因是：給定一個查找的關(guān)鍵字（即當前狀態(tài)和輸入字符），TCAM將該關(guān)鍵字與TCAM中存儲的所有遷移邊表項進行并行比較。例如，存儲空間大小為18 MB的TCAM一次查找操作所需能耗高達15 W[10]，這將導(dǎo)致嵌入TCAM芯片的路由器、交換機或者其他硬件設(shè)備能耗過載。同時，隨著網(wǎng)絡(luò)應(yīng)用的發(fā)展，網(wǎng)絡(luò)攻擊和應(yīng)用日益復(fù)雜化，特征規(guī)則集條數(shù)不斷增多且描述越來越復(fù)雜，存儲DFA所需的 TCAM 存儲空間也越來越大，從而導(dǎo)致TCAM能耗開銷進一步提高。

本文提出一種基于字符索引的正則表達式匹配算法，減少TCAM的能耗。該算法的核心思想是：將TCAM分為索引塊和存儲塊；DFA的字母表存儲在TCAM索引塊中，每個字符的索引范圍存儲在對應(yīng)的 SRAM 中；狀態(tài)遷移邊的源狀態(tài)存儲在TCAM 存儲塊中，目的狀態(tài)存儲在對應(yīng)的 SRAM中。該算法的匹配查找過程如下：首先，在TCAM索引塊中查找當前的輸入字符，在對應(yīng)的SRAM中獲取相應(yīng)的索引范圍；然后，根據(jù)索引范圍啟動對應(yīng)的TCAM存儲塊，匹配當前狀態(tài)，在SRAM中獲取遷移的目的狀態(tài)。

本文的主要貢獻是：1）提出了基于字符索引的DFA（CIDFA, character-indexed DFA），減少匹配時激活的TCAM塊數(shù)，降低TCAM能耗；2）針對Snort和 Bro特征規(guī)則集開展實驗，結(jié)果表明，與DFA相比，CIDFA在 TCAM 能耗上平均減少了92.7%，在 TCAM 存儲空間開銷上平均減少了32.0%，在吞吐量上平均提高了57.9%。

2 相關(guān)工作

DPI技術(shù)的核心是正則表達式匹配算法，基于硬件的正則表達式匹配算法主要從壓縮存儲空間等方面開展研究。基于FPGA的算法[11～14]實現(xiàn)了非確定性有限自動機（NFA, nondeterministic finite automata），基于ASIC的算法[15～18]則實現(xiàn)了DFA。Kumar等人[15,16]提出了基于D2FA的正則表達式匹配算法，壓縮了 DFA的遷移邊，Smith等人[19,20]提出了基于 XFA的正則表達式匹配算法，壓縮了DFA的狀態(tài)。在基于TCAM的算法方面，Meiners等人[8]提出了共享遷移邊、融合狀態(tài)遷移表等優(yōu)化算法壓縮了DFA的存儲空間，將DFA實現(xiàn)在較小的TCAM片上，Peng等人[9]利用NFA和DFA結(jié)構(gòu)上的關(guān)聯(lián)，提出了鏈式DFA壓縮算法，保證匹配速度的同時，壓縮了DFA的狀態(tài)空間。在數(shù)據(jù)分組分類領(lǐng)域，Meiners等人[21～23]提出了多種TCAM表項壓縮算法，降低TCAM的存儲空間開銷。

TCAM具有查找速度快、存儲空間小等特性，且能耗與存儲空間成正比，在部署大規(guī)模設(shè)備的網(wǎng)絡(luò)環(huán)境中，如何降低TCAM能耗成為研究熱點。在IP查找和數(shù)據(jù)分組分類領(lǐng)域，研究者提出了多種低能耗的TCAM方案，Zane等人[24]提出了適用于IP查找的 CoolCAM，將路由表拆分成多個子表，通過將IP地址映射到路由表的一個子表，縮小查找范圍。Spitznagel等人[25]改進了CoolCAM的結(jié)構(gòu)，提出了適用于數(shù)據(jù)分組分類的Extended TCAM，將一個索引過濾器與多個 TCAM 存儲塊相連，限制TCAM查找過程中激活的TCAM塊數(shù)。Ma等人[10]提出了SmartPC，將源IP地址和目的IP地址組成的地址對作為預(yù)分類器，數(shù)據(jù)分類器中的規(guī)則按照地址對的范圍，啟發(fā)式地存儲在不同的 TCAM 塊中，且每條規(guī)則僅存儲在一個TCAM塊中。SmartPC僅需激活預(yù)分類器和部分TCAM塊，即可完成規(guī)則匹配。SmartPC在能耗上平均減少了88%，索引開銷小于TCAM存儲空間的4%，是目前所知最優(yōu)的低能耗分組分類算法。

與上述低能耗TCAM方案不同，本文第一次提出基于TCAM的低能耗正則表達式匹配算法。本文的方法將TCAM分為索引塊和存儲塊，DFA的字母表存儲在TCAM索引塊中，源狀態(tài)存儲在TCAM存儲塊中。匹配查找過程時，首先在TCAM索引塊中查找當前讀入的字符，根據(jù)SRAM中返回的索引范圍，啟動對應(yīng)的TCAM存儲塊，完成查找。本文的方法不僅降低TCAM能耗，而且減少DFA所需的存儲空間，同時提高匹配吞吐量。

3 基于字符索引的正則表達式匹配算法

3.1 基于TCAM的正則表達式匹配

對于給定的特征規(guī)則集，在TCAM上實現(xiàn)正則表達式匹配的步驟如下：首先，構(gòu)造特征規(guī)則集的DFA；然后，構(gòu)建DFA的TCAM表，即將DFA的每條狀態(tài)遷移邊存儲在一條TCAM表項中。每條表項由TCAM和SRAM兩部分組成：源狀態(tài)和輸入字符存儲在TCAM部分，目的狀態(tài)存儲在與TCAM部分對應(yīng)的SRAM部分。該算法的匹配查找過程如下：首先，將當前狀態(tài)和輸入字符組合成一個關(guān)鍵字，啟動TCAM的全部表項查找該關(guān)鍵字，返回與該關(guān)鍵字匹配的第一條表項的地址；然后，根據(jù)匹配表項的地址，獲取SRAM中存儲的目的狀態(tài)；最后，將目的狀態(tài)作為當前狀態(tài)，讀入下一個輸入字符，重復(fù)執(zhí)行相似的 TCAM 查找，直至輸入字符結(jié)束。

圖 1給出了特征規(guī)則集{.*ab.*c}的 DFA和TCAM表，圖1(a)中，初始狀態(tài)為0，匹配狀態(tài)為3，“[^]”表示非字符子集，[^ab]表示除了a和b以外的其他輸入字符。圖1(b)中，TCAM表的表項總數(shù)與DFA的遷移邊條數(shù)相同，源狀態(tài)和目的狀態(tài)對應(yīng)狀態(tài)遷移表中狀態(tài)的二進制編碼，輸入字符為三態(tài)編碼，特征規(guī)則集中出現(xiàn)的輸入字符為該字符的二進制 ASCII碼，其他字符用“********”表示，“********”可匹配除特征規(guī)則集中字符之外的任意輸入字符。

3.2 TCAM分塊存儲和字符索引

TCAM是分塊存儲的，每個TCAM塊中包含了固定數(shù)目的TCAM表項。TCAM提供部分激活的機制，即查找過程中可以僅啟動TCAM中的部分TCAM 塊，而不必啟動整個 TCAM。利用 TCAM部分激活機制的前提是：必須保證在激活的少數(shù)TCAM塊中進行準確無誤的查找。本文通過字符索引達到這一目的。

圖1 特征規(guī)則集{.*ab.*c}的DFA和TCAM表

算法1給出了TCAM分塊存儲和構(gòu)建字符索引的偽代碼。其中，TransitionTable表示特征規(guī)則集的狀態(tài)遷移表，TCAMTable表示特征規(guī)則集對應(yīng)的TCAM表，StorBlock表示存儲塊，IndexBlock表示索引塊，blockSize表示每個 TCAM 塊的大小。第1)～3)行代碼是由狀態(tài)遷移表構(gòu)建TCAM表的步驟，即將狀態(tài)遷移表的每條狀態(tài)遷移邊保存在 TCAM表中，每條遷移邊由三元組成：源狀態(tài)srcID、輸入字符input和目的狀態(tài)destID。第4)～10)行代碼為構(gòu)建存儲塊的步驟，首先，將TCAM表中的表項按照輸入字符升序排列，計算輸入字符相同的TCAM表項數(shù)，賦值給變量minStorEntryNum，根據(jù)TCAM塊的大小，計算每個輸入字符所需的存儲塊數(shù)，賦值給變量storBlockNum；然后，將srcID和destID組合為存儲塊表項，按照TCAM塊的大小構(gòu)建存儲塊。由于storBlockNum存儲塊中包含的表項總數(shù)大于或等于minStorEntryNum，故在最后一個存儲塊中可能存在未使用的TCAM表項，本文采用無關(guān)位（“*”）填滿這些表項，保證TCAM中沒有空白的表項。第11)～15)行代碼表示構(gòu)建索引塊的步驟，首先，將storBlockNum個存儲塊的編號storBlockID存儲在每個輸入字符input的索引范圍indexRange中；然后，按照TCAM塊的大小構(gòu)建索引塊。

算法1 BlockOrganized(TransitionTable)

1) for eachtransitioninTransitionTabledo

2)TCAMTablePushBack (srcID,input,destID);

3) end for

4) for eachentryinTCAMTabledo

5) Sort(entryinascending order ofinput);

6)minStorEntryNum= Count(entrywith sameinput);

7)storBlockNum=Ceil(minStorEntryNum/block-Size);

8)StorEntryPushBack(srcID,destID);

9) end for

10)StorBlock= Partition(StorEntrysrcID,block-Size);

11) for eachinputinalphabetTabledo

12)indexRangeInsert(storBlockIDaccording tostorBlockNum);

13)IndexEntryPushBack(input,indexRange);

14) end for

15)IndexBlock= Partition (IndexEntryinput,blockSize)

圖2給出了圖1應(yīng)用本文算法后的結(jié)構(gòu)示意，其中， TCAM塊的大小為4，TCAM索引塊保存TCAM 存儲塊編號的二進制編碼，用于指示每個字符對應(yīng)的存儲塊范圍；TCAM 存儲塊保存源狀態(tài)的二進制編碼，對應(yīng)的SRAM部分保存目的狀態(tài)的二進制編碼。

圖2 特征規(guī)則集{.*ab.*c}的分塊存儲和字符索引

基于字符索引的正則表達式匹配算法的查找過程如下：首先，在TCAM索引塊中查找當前的輸入字符，返回SRAM中的存儲塊編號；然后，根據(jù)存儲塊編號啟動對應(yīng)的TCAM存儲塊，匹配當前狀態(tài)，在SRAM中獲取遷移的目的狀態(tài)；最后，將目的狀態(tài)作為當前狀態(tài)，讀入下一個輸入字符，重復(fù)執(zhí)行相似的TCAM查找，直至輸入字符結(jié)束。

比較圖 2和圖 1可知，本文的算法將基于TCAM的正則表達式匹配分為2個階段：第1個階段查找TCAM索引塊，第2個階段查找TCAM存儲塊。本文的算法在能耗、存儲空間、吞吐量等重要指標上的變化將在下一節(jié)匯總詳細討論。

4 實驗評估

在正則表達式處理軟件[26]的基礎(chǔ)上，本文采用C/C++設(shè)計實現(xiàn)了DFA和CIDFA，并運行在CPU為Intel Xeon X5506、內(nèi)存為16 GB的計算機上。在軟件模擬實驗中，本文采用 TCAM 仿真工具[27]模擬DFA和CIDFA的TCAM能耗、存儲空間開銷和吞吐量等性能指標。

4.1 實驗方法

本文處理的特征規(guī)則集來自于Snort和Bro特征庫，其中，R1～R9取自Snort特征庫， R10取自Bro特征庫。特征規(guī)則集的參數(shù)如表1所示，其中，通配符表達式的主要形式為{.*{子表達式}.*{子表達式}}，“.*”表示匹配任意數(shù)目的輸入字符。計數(shù)器表達式的主要形式為{[c1…cn]{n}}，“[c1…cn]”表示匹配輸入字符為“c1”至“cn”中的任意一個，“{n}”表示重復(fù)出現(xiàn)n次。由特征規(guī)則集生成DFA時，通配符表達式容易引起DFA狀態(tài)空間急劇增大[20]，導(dǎo)致存儲自動機所需的TCAM空間開銷增加，能耗也隨之增大。

表1 特征規(guī)則集的參數(shù)統(tǒng)計

本文采用的特征規(guī)則集中，通配符表達式條數(shù)占規(guī)則總數(shù)的1.3%～42.3%，DFA狀態(tài)的規(guī)模為5 000～100 000個，存儲狀態(tài)遷移表的TCAM包含400 000～8 000 000條表項，能夠模擬不同規(guī)模的DFA在本文算法下性能的改變。

TCAM存儲空間的大小為TCAM寬度與表項數(shù)的乘積，其中，表項數(shù)由 TCAM 塊的大小與TCAM塊數(shù)的乘積決定。DFA占用的TCAM寬度為源狀態(tài)和輸入字符占用的比特數(shù)之和。本文采用的特征規(guī)則集的字母表為ASCII碼，輸入字符占用的比特數(shù)為8 bit，對于狀態(tài)數(shù)為S的DFA，源狀態(tài)占用的比特數(shù)為，故 DFA占用的 TCAM 寬度為(W+8)bit，其 TCAM 存儲空間開銷為W=[lbS]。對于CIDFA，索引塊的TCAM寬度為輸入字符的比特數(shù)，即8 bit，存儲塊的TCAM寬度為源狀態(tài)占用的比特數(shù)，即Wbit，CIDFA的TCAM存儲空間開銷S2=8RY1+WRY2。

本文以吞吐量衡量算法的匹配速率。吞吐量為每次讀入字符的比特數(shù)與TCAM查找時延之商，對于單步長正則表達式匹配算法，每次讀入一個ASCII字符，為 8 bit。假定上述X、Y1和Y2個 TCAM塊的查找時延分別為Dx、Dy1和Dy2，DFA的吞吐量為8/Dx，CIDFA的吞吐量為8/(Dy1+Dy2)。

4.2 能耗

圖3給出了10個特征規(guī)則集在TCAM能耗上減少的比例。不同 TCAM 塊大小下，CIDFA在TCAM能耗上減少的比例為78.8%～98.5%，平均減少比例為92.7%。當TCAM塊大小為32時，CIDFA在TCAM能耗上減少的比例最小，為8.8%～84.8%，平均減少比例為80.3%。隨著TCAM塊大小的增加，CIDFA在TCAM能耗上減少的比例不斷提高，當TCAM塊大小為1 024時，CIDFA在TCAM能耗上減少的比例達到最大，為98.0%～98.5%，平均減少比例為98.2%。

圖3 能耗減少比例

圖4給出了當TCAM塊大小為64、256和1 024時，DFA與 CIDFA的 TCAM能耗比較。不同TCAM 塊大小下，同一特征規(guī)則集對應(yīng)的 DFA的TCAM能耗基本一致；隨著TCAM塊大小的增加，同一特征規(guī)則集對應(yīng)的CIDFA的TCAM能耗不斷減少。

4.3 存儲空間開銷和吞吐量

本文采用 4.1節(jié)中介紹的方法計算 DFA和CIDFA的TCAM存儲空間開銷和吞吐量。

在存儲空間方面，DFA的TCAM片上保存狀態(tài)遷移邊的源狀態(tài)和輸入字符。CIDFA額外開銷了一部分TCAM空間作為索引塊，但是，TCAM片上僅保存狀態(tài)遷移邊的源狀態(tài)。

表2給出了DFA和CIDFA的TCAM存儲空間開銷比較。與DFA相比，CIDFA在TCAM存儲空間開銷上平均減少了 32.0%。對于不同大小的TCAM塊，同一特征規(guī)則集對應(yīng)的DFA和CIDFA的TCAM存儲空間開銷分別相同。

圖4 不同TCAM塊大小下，DFA與CIDFA的TCAM能耗比較

吞吐量決定了算法的匹配速率，由于 DFA和CIDFA每次匹配操作處理的比特數(shù)相同，故算法的吞吐量由匹配時的查找時延決定。DFA的查找時延為啟動全部TCAM塊完成查找操作的時間，CIDFA的查找時延為啟動TCAM索引塊和TCAM存儲塊完成查找的時間之和。

表2 DFA和CIDFA的TCAM存儲空間開銷比較

表3給出了DFA和CIDFA的吞吐量比較。與DFA相比，CIDFA在吞吐量上平均提高了57.9%。對于不同大小的TCAM塊，同一特征規(guī)則集對應(yīng)的DFA吞吐量相同；隨著 TCAM 塊大小的增加，同一特征規(guī)則集對應(yīng)的CIDFA吞吐量不斷下降。當TCAM塊大小為32，CIDFA的吞吐量達到最大，比DFA提高50.3%～99.5%；當TCAM塊大小為1 024時，CIDFA的吞吐量最低，比DFA提高36.6%～ 70.9%。

表3 DFA和CIDFA的吞吐量比較

5 結(jié)束語

本文提出了一種基于字符索引的正則表達式匹配算法，該算法將TCAM分為索引塊和存儲塊，其中，索引塊中保存DFA的字母表，存儲塊中保存DFA的源狀態(tài)。匹配時，首先在索引塊中查找當前讀入的字符，然后，僅啟動與讀入字符對應(yīng)的部分存儲塊，即可完成查找操作。該算法能夠避免啟動全部的存儲塊，從而達到降低能耗的目的。

針對實際特征規(guī)則集的實驗表明：與 DFA相比，CIDFA在能耗上平均減少了92.7%，在存儲空間平均開銷上平均減少了32.0%，在吞吐量上平均提高了57.9%。因此，CIDFA是一種低能耗的高效TCAM 方案，不僅確保查找速率，而且顯著降低TCAM能耗和存儲空間。

本文的算法可應(yīng)用于數(shù)據(jù)中心網(wǎng)絡(luò)中大規(guī)模流量識別技術(shù)，有助于減少數(shù)據(jù)中心網(wǎng)絡(luò)中成千上萬臺交換機的能耗，下一步的研究方向是實現(xiàn)基于TCAM的多步長正則表達式匹配算法。

[1] PAXSON V, ASANOVIC K, DHARMAPURIKAR S,et al.Rethinking hardware support for network analysis and intrusion prevention[A].Proceeding of USENIX Workshop on Hot Topics in Security[C]. Vancouver, Canada, 2006.

[2] SOMMER R, PAXSON V. Enhancing byteleve network intrusion detection signatures with context[A]. Proceeding of ACM Conference on Computer and Communications security[C]. Washington, DC, USA,2003, 262- 271.

[3] Snort::rules[EB/OL]. http://www.snort.org/start/rules, 2013-12-01.

[4] The bro network security monitor[EB/OL]. http:// bro-ids.org, 2013.

[5] HP TippingPoint S1200N IPS A7500 module[EB/OL]. http://h17007.www1.hp.com/us/en/products/network-security/HP_TippingPoint_S1200N_IPS_A7500_Module/index.aspx?jumpid=reg_r1002_usen,2013-12-01.

[6] Intrusion prevention system(IPS)-Cisco systems[EB/OL]. http://www.cisco.com/en/US/products/ps5729/Products_Sub_Category_Home.html,2013-12-05.

[7] YU F, KATZ R, LAKSHMAN T V. Gigabit rate packet patternmatching using TCAM[A]. Proceeding of IEEE International Conference on Network Protocols[C]. Berlin, Germany, 2004.

[8] MEINERS C R, PATEL J, NORIGE E,et al. Fast regular expression matching using small TCAMs for network intrusion detection and prevention systems[A]. Proceeding of the 19th USENIX Security Symposium[C]. Washington, DC, USA, 2010, 8.

[9] PENG K, TANG S, CHEN M,et al. Chain-based DFA deflation for fast and scalable regular expression matching using TCAM[A]. Proceeding of ACM/IEEE Symposium on Architectures for Networking and Communications Systems[C]. Brooklyn, NY, USA, 2011.

[10] MA Y, BANERJEE S. A smart pre-classifier to reduce power consumption of TCAMS for multi-dimensional packet classification[A].Proceeding of ACM Conference of the Special Interest Group on Data Communication[C]. Helsinki, Finland, 2012.

[11] SIDHU R, PRASANNA V K. Fast regular expression matching using FPGA[A]. Proceeding of IEEE International Symposium on Field-Programmable Custom Computing Machines[C]. Rohnert Park,CA, USA, 2001.

[12] CLARK C R, SCHIMMEL D E. Scalable pattern matching on high-speed networks[A]. Proceeding of IEEE International Symposium on Field-Programmable Custom Computing Machines[C]. Napa Valley, CA, USA, 2004.

[13] SOURDIS I, PNEVMATIKATOS D. Pre-decoded CAMs for efficient and high-speed NIDS pattern matching[A]. Proceeding of IEEE International Symposium on Field-Programmable Custom Computing Machines[C]. Napa Valley, CA, USA, 2004.

[14] MOSCOLA J, LOCKWOOD J, LOUI R P,et al. Implementation of a content-scanning module for an internet firewall[A]. Proceeding of IEEE International Symposium on Field-Programmable Custom Computing Machines[C]. Napa Valley, CA, USA, 2003.

[15] KUMAR S, DHARMAPURIKAR S, YU F,et al. Algorithms to accelerate multiple regular expressions matching for deep packet inspection[A]. Proceeding of ACM Conference of the Special Interest Group on Data Communication[C]. Pisa, Italy, 2006.

[16] KUMAR S, TURNER J, WILLIAMS J. Advanced algorithms for fast and scalable deep packet inspection[A]. Proceeding of ACM/IEEE Symposium on Architectures for Networking and Communications Systems[C]. San Jose, CA, USA, 2006.

[17] BECCHI M, CADAMI S. Memory-efficient regular expression search using stae merging[A]. Proceeding of IEEE International Conference on Computer Communications[C]. Anchorage, Alaska, USA, 2007.

[18] BECCHI M, CROWLEY P. An improved algorithm to accelerate regular expression evaluation[A]. Proceeding of ACM/IEEE Symposium on Architectures for Networking and Communications Systems[C]. San Jose, CA, USA, 2008.

[19] SMITH R, ESTAN C, JHA S. XFA: faster signature matching with extended automata[A]. Proceeding of IEEE Symposium on Security and Privacy[C]. Oakland, CA, USA, 2008.

[20] SMITH R, ESTAN C, JHA S,et al. Deflating the big bang: fast and scalable deep packet inspection with extended finite automata[A].Proceeding of ACM Conference of the Special Interest Group on Data Communication[C]. Seattle, WA, USA, 2008.

[21] MEINERS C R, LIU A X, TORNG E. TCAM Razor: a systematic approach towards minimizing packet classifiers in TCAMs[A]. Proceeding of IEEE International Conference on Network Protocols[C].Beijing, China, 2007.

[22] LIU A X, MEINERS C R, ZHOU Y. All-match based complete redundancy removal for packet classifiers in TCAMs[A]. Proceeding of IEEE International Conference on Computer Communications[C].Phoenix, AZ, USA, 2008.

[23] MEINERS C R, LIU A X, TORNG E. Bit weaving: a non-prefix approach to compressing packet classifiers in TCAMs[A]. Proceeding of IEEE International Conference on Network Protocols[C]. Princeton,NJ, USA, 2009.

[24] ZANE F, NARLIKAR G, BASU A. CoolCAMs: power-efficient TCAMs for forwarding engines[A]. Proceeding of IEEE International Conference on Computer Communications[C]. San Francisco,USA, 2003.

[25] SPITZNAGEL E, TAYLOR D, TURNER J. Packet classification using extended TCAMs[A]. Proceeding of IEEE International Conference on Network Protocols[C]. Atlanta, Georgia, USA, 2003.

[26] Regular expression processor[EB/OL].http://regex.wustl.edu/index.php/Main_Page, 2013-12-01.

[27] AGRAWAL B, SHERWOOD T. Modeling TCAM power for next generation network devices[A]. Proceeding of IEEE International Symposium on Performance Analysis of Systems and Software[C].Austin, TX, USA, 2006.