應(yīng)用于Web服務(wù)器匹配算法的FPGA實(shí)現(xiàn)

孟旭東，許強(qiáng)凱

(1.南京郵電大學(xué) 寬帶無(wú)線(xiàn)通信與傳感網(wǎng)技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210003；2.南京郵電大學(xué) 江蘇省電信網(wǎng)絡(luò)融合實(shí)驗(yàn)室，江蘇 南京 210003)

應(yīng)用于Web服務(wù)器匹配算法的FPGA實(shí)現(xiàn)

孟旭東1,2，許強(qiáng)凱1,2

(1.南京郵電大學(xué) 寬帶無(wú)線(xiàn)通信與傳感網(wǎng)技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210003；2.南京郵電大學(xué) 江蘇省電信網(wǎng)絡(luò)融合實(shí)驗(yàn)室，江蘇 南京 210003)

Web服務(wù)已經(jīng)成為現(xiàn)代人網(wǎng)絡(luò)生活的一部分，人們需要通過(guò)Web迅速地獲取信息，需要在Web上快速地搜索關(guān)鍵字。在Web服務(wù)器端實(shí)現(xiàn)快速搜索，需要Web服務(wù)器能夠快速地對(duì)流經(jīng)服務(wù)器的數(shù)據(jù)流進(jìn)行字符串匹配。對(duì)字符串匹配算法進(jìn)行了系統(tǒng)介紹，其中重點(diǎn)分析了利用位并行計(jì)算的Shift-Or算法。之所以利用FPGA來(lái)實(shí)現(xiàn)，是因?yàn)镕PGA的實(shí)現(xiàn)方式在速率上高于軟件實(shí)現(xiàn)方式，在靈活性上高于專(zhuān)用集成電路的實(shí)現(xiàn)方式。在FPGA上實(shí)現(xiàn)了Shift-Or字符串匹配算法，并在千兆以太網(wǎng)的環(huán)境下進(jìn)行了實(shí)驗(yàn)測(cè)試。實(shí)驗(yàn)結(jié)果表明，該方法能夠滿(mǎn)足在高速網(wǎng)絡(luò)環(huán)境下對(duì)數(shù)據(jù)包內(nèi)容的深度檢測(cè)。

Web服務(wù)器；字符串匹配；Shift-Or；FPGA

0 引 言

在網(wǎng)絡(luò)這個(gè)數(shù)據(jù)的海洋里，數(shù)據(jù)流量正不斷增長(zhǎng)，人們迫切需要對(duì)數(shù)據(jù)進(jìn)行搜索，需要在Web服務(wù)器[1]上實(shí)現(xiàn)字符串匹配,工作量巨大。這一要求對(duì)數(shù)據(jù)搜索查找技術(shù)提出了巨大挑戰(zhàn)。字符串匹配是其核心技術(shù)。在網(wǎng)絡(luò)服務(wù)器[2]端，數(shù)據(jù)匹配的需求幾乎無(wú)處不在，尤其是在網(wǎng)絡(luò)安全領(lǐng)域。網(wǎng)絡(luò)安全領(lǐng)域中的一系列應(yīng)用，例如防火墻、入侵檢測(cè)防護(hù)、垃圾郵件過(guò)濾、深度內(nèi)容檢測(cè)等，都與字符串匹配緊密相關(guān)[3]。字符串匹配在上述安全領(lǐng)域的應(yīng)用中都處于核心位置，并且占用著大量的計(jì)算資源。舉個(gè)例子，在檢測(cè)入侵的網(wǎng)絡(luò)安全應(yīng)用中，字符串匹配是系統(tǒng)能否成功發(fā)現(xiàn)包含安全威脅信息的關(guān)鍵。入侵檢測(cè)系統(tǒng)先把部分已知具有安全威脅特征的模式串保存下來(lái)，定義成一系列的規(guī)則。當(dāng)有數(shù)據(jù)流入內(nèi)部網(wǎng)絡(luò)時(shí)，系統(tǒng)按照這些預(yù)先定義的規(guī)則和預(yù)先存下來(lái)的模式對(duì)流入數(shù)據(jù)進(jìn)行對(duì)比，檢查出數(shù)據(jù)包內(nèi)容中可能存在安全威脅的信息。據(jù)統(tǒng)計(jì)，在這樣的安全系統(tǒng)里，字符串匹配所消耗的計(jì)算資源占到了系統(tǒng)所有計(jì)算資源的50%以上[4]。字符串匹配本身需要消耗大量的計(jì)算資源，這一點(diǎn)對(duì)在網(wǎng)絡(luò)服務(wù)器端實(shí)現(xiàn)字符串匹配提出了較高要求。

在目前已有的字符串匹配算法中，最直接的方法是BF算法，俗稱(chēng)蠻力算法。也就是不涉及任何技巧，逐個(gè)字符進(jìn)行比較判斷，從而得到兩個(gè)字符串是否相同的結(jié)論。除了BF算法之外，研究人員提出了各種各樣的字符串匹配算法。這些算法中，有非常經(jīng)典的Knuth-Morris-Pratt(KMP)算法[5]、Boyer-Moore(BM)算法[6]；也有一些新式算法采用較新技術(shù)思想(例如位并行)，其中的代表是Shift-And/Shift-Or算法，它通過(guò)同時(shí)完成多個(gè)位的計(jì)算達(dá)到同時(shí)處理多個(gè)字符串位置的目的，從而大幅提高了匹配效率[7]。

在網(wǎng)絡(luò)服務(wù)器這樣的對(duì)信息處理速度要求非常高的地方，傳統(tǒng)的利用通用處理器CPU，通過(guò)軟件實(shí)現(xiàn)字符串匹配存在運(yùn)行速率不足的問(wèn)題。軟件實(shí)現(xiàn)方式不能保證線(xiàn)速處理，從而造成網(wǎng)絡(luò)時(shí)延較大或信息檢索不充分。由于通用處理器性能的提升跟不上網(wǎng)絡(luò)速率的提升，一般在通用處理器上以軟件方式實(shí)現(xiàn)字符串匹配只能用于低于100 Mbps的低速網(wǎng)絡(luò)中。所以利用硬件來(lái)實(shí)現(xiàn)字符串匹配算法。

1 Shift-Or算法的FPGA實(shí)現(xiàn)設(shè)計(jì)概要

Shift-Or算法[8]利用位并行的方法提高了字符串匹配速率，通過(guò)一個(gè)位掩碼D，表示模式串前綴和文本串后綴的匹配情況。它同樣是先根據(jù)模式字符串構(gòu)造一個(gè)表B，用來(lái)記錄字母表中每個(gè)字符的位掩碼bm…b1。如果pj=c，掩碼B[c]的第j位被置0，其余為1。這里的位掩碼D初始為全1。若模式串前綴p1…pj是文本串t1…ti的后綴，就把位掩碼D=dm…d1的第j位置0，并稱(chēng)D的第j位是活動(dòng)的。

當(dāng)模式串P=p1…pm長(zhǎng)為m，dm是活動(dòng)的時(shí)候，就說(shuō)明有一個(gè)成功匹配。每次讀入下一個(gè)文本字符ti+1時(shí)，需要重新計(jì)算位掩碼D。同樣是利用了位并行的方式，使得D的計(jì)算可以在常數(shù)時(shí)間內(nèi)完成。D的更新公式如下：

D=(D?1)|B[ti+1]

可以發(fā)現(xiàn)Shift-Or算法實(shí)際上是Shift-And算法的一種富技巧性的實(shí)現(xiàn)。它通過(guò)對(duì)位取反從而去掉0m-11，從而簡(jiǎn)化了計(jì)算，提高了速度。Shift-Or算法的偽代碼如下[9]：

Shift-Or(p=p1…pm,T=t1…tn)

Preprocessing

Forc∈∑DoB[c]=1m

Forj∈1…mDoB[pj]=B[pj]&1m-j01j-1

Searching

D=1m

Fori∈1…nDoD=(D?1)|B[ti]

ifD|01m-1≠1mThenfindanoccurrenceati-m+1

EndofFor

假設(shè)在進(jìn)行信息查找之前，F(xiàn)PGA內(nèi)沒(méi)有事先存儲(chǔ)需要匹配的模式字符串。根據(jù)Shift-Or算法，F(xiàn)PGA需要在對(duì)文本字符串進(jìn)行信息搜索之前完成對(duì)模式字符串的預(yù)處理，計(jì)算得到算法需要的表格B并存在RAM內(nèi)。先向FPGA發(fā)送包含模式字符串的數(shù)據(jù)包，讓FPGA對(duì)模式串進(jìn)行預(yù)處理。預(yù)處理完成后，F(xiàn)PGA開(kāi)始等待接收包含文本字符串的數(shù)據(jù)包，對(duì)接收到的文本串計(jì)算字符串匹配結(jié)果。

2 利用該字符串匹配模塊工作的系統(tǒng)設(shè)計(jì)

該系統(tǒng)工作在網(wǎng)絡(luò)的數(shù)據(jù)鏈路層[10]，利用千兆以太網(wǎng)口收發(fā)以太網(wǎng)幀[11]。但它對(duì)數(shù)據(jù)的處理不局限于以太網(wǎng)數(shù)據(jù)幀的幀頭部信息。以太網(wǎng)幀中封裝了數(shù)據(jù)包，數(shù)據(jù)包的凈荷里存放著接下來(lái)所做的字符串匹配所需要的模式字符串和文本字符串。系統(tǒng)在接收到一個(gè)數(shù)據(jù)幀后，會(huì)傳給FPGA芯片，可以對(duì)幀內(nèi)所有數(shù)據(jù)進(jìn)行操作處理。

以太網(wǎng)幀中包括6字節(jié)的目標(biāo)MAC地址，6字節(jié)的源MAC地址，2字節(jié)的數(shù)據(jù)類(lèi)型，4字節(jié)的校驗(yàn)和，以及幀中間的數(shù)據(jù)包部分。以太網(wǎng)協(xié)議規(guī)定數(shù)據(jù)包最少46字節(jié)，最長(zhǎng)1 500字節(jié)。而這里除數(shù)據(jù)包以外都可以認(rèn)為是幀的頭部信息，屬于數(shù)據(jù)鏈路層，不影響在應(yīng)用層做字符串匹配。FPGA在接收了這樣一個(gè)數(shù)據(jù)幀后，首先是存到RAM[12]里，再進(jìn)一步對(duì)數(shù)據(jù)進(jìn)行處理。協(xié)議規(guī)定了以太網(wǎng)幀的固定結(jié)構(gòu)，每一個(gè)以太網(wǎng)幀的頭部信息長(zhǎng)度是固定的，可以利用這一點(diǎn)，準(zhǔn)確找到在FPGA中的RAM里存下來(lái)的數(shù)據(jù)幀內(nèi)部的數(shù)據(jù)。

以太網(wǎng)幀封裝的是網(wǎng)絡(luò)層的數(shù)據(jù)包，也就是通常所說(shuō)的IP包。IP包里包含著用戶(hù)數(shù)據(jù)，但是和上述的幀結(jié)構(gòu)類(lèi)似，IP包存在一個(gè)20字節(jié)的頭部信息。IP報(bào)文里的頭部包括源IP地址、目標(biāo)IP地址、頭校驗(yàn)和等信息，屬于網(wǎng)絡(luò)層信息。IP數(shù)據(jù)包里接下來(lái)是TCP/UDP包，同樣也包含固定長(zhǎng)度的頭部信息。對(duì)UDP包而言，UDP報(bào)頭包括2字節(jié)的源端口號(hào)，2字節(jié)的目的端口號(hào)，2字節(jié)的UDP長(zhǎng)度和2字節(jié)的校驗(yàn)和，一共8字節(jié)的頭部信息。上述所有的頭部信息，因?yàn)槎际枪潭ㄩL(zhǎng)度，所以在RAM中的存儲(chǔ)相對(duì)位置也是固定的。利用信息在RAM中相對(duì)位置固定的特點(diǎn)，可以方便地找到處理所需要的數(shù)據(jù)。

按照上述原理，把應(yīng)用層的模式字符串和文本字符串分別封裝在不同的數(shù)據(jù)包中，從外部通過(guò)以太網(wǎng)幀的形式傳入系統(tǒng)，利用UDP的端口號(hào)來(lái)對(duì)其進(jìn)行區(qū)分，以完成不同的處理。根據(jù)算法工作流程(見(jiàn)第三節(jié))，如果判定為模式串，根據(jù)UDP報(bào)頭里的數(shù)據(jù)包長(zhǎng)度確定模式串的長(zhǎng)度，并在FPGA中對(duì)模式串進(jìn)行Shift-Or算法預(yù)處理；如果判定為文本串，還是可以根據(jù)UDP報(bào)頭里的數(shù)據(jù)包長(zhǎng)度確定文本串的長(zhǎng)度，并在FPGA中對(duì)文本串進(jìn)行Shift-Or算法匹配，這兩個(gè)過(guò)程可以分開(kāi)并行執(zhí)行。如果匹配成功，可以將匹配成功信息通過(guò)數(shù)據(jù)包的形式返回給外部接口。系統(tǒng)的結(jié)構(gòu)如圖1所示，系統(tǒng)核心部分在字符串匹配模塊。

圖1 系統(tǒng)結(jié)構(gòu)

2.1 字符串匹配模塊的具體實(shí)現(xiàn)

Shift-Or算法及其在FPGA上實(shí)現(xiàn)的思路已經(jīng)在前面進(jìn)行了詳細(xì)分析。字符串匹配模塊下還可以更細(xì)致地分為模式串預(yù)處理模塊和文本串匹配模塊。

字符串匹配所需的模式串和文本串分別由具有不同端口號(hào)的TCP/UDP包封裝起來(lái)。FPGA可以根據(jù)所收到的數(shù)據(jù)包中的TCP/UDP端口號(hào)來(lái)判斷已經(jīng)存入RAM的數(shù)據(jù)包中的凈荷是模式串還是文本串。在verilog程序中，模式串預(yù)處理模塊和文本串匹配模塊分別用一段always語(yǔ)句塊實(shí)現(xiàn)。

2.1.1 模式串預(yù)處理實(shí)現(xiàn)

如果FPGA判定正在處理的數(shù)據(jù)包所含凈荷是模式字符串，Shift-Or算法要求對(duì)模式字符字符串進(jìn)行預(yù)處理。在這個(gè)預(yù)處理中，算法會(huì)根據(jù)讀入的模式字符串制作一張模式特征表格。模式特征表B的每一行對(duì)應(yīng)模式串中的一個(gè)字符。定義的表格B有27行，可以處理26個(gè)英文字母，其他的任意字符統(tǒng)一記為‘*’。

在ASCII編碼中，一個(gè)英文字符的長(zhǎng)為1字節(jié)，即8位比特位，并且有大小寫(xiě)之分，即大寫(xiě)的字符‘A’和小寫(xiě)的字符‘a(chǎn)’編碼不同。通過(guò)對(duì)字符編碼的判斷，實(shí)現(xiàn)了忽略英文字符大小寫(xiě)的模式匹配。例如，字符串“CHINA”在該字符串匹配系統(tǒng)中和字符串“china”效果相同。

字符‘A’的ASCII編碼為65，即8'b0100_0001，字符‘a(chǎn)’的ASCII編碼為97，即8'b0110_0001，在計(jì)算模式特征表格B時(shí)，同時(shí)考慮了這兩種情況，字母‘A’或‘a(chǎn)’在模式串中的特征(在模式串中出現(xiàn)的位置)都在表格B的第一個(gè)行向量B[0]中表示出來(lái)。同理，字符‘B’的ASCII編碼為66，即8'b0100_0010，字符‘b’的ASCII編碼為98，即8'b0110_0010，在計(jì)算模式特征表B時(shí)，字母‘B’或‘b’在模式串中的特征都在表格B的第二個(gè)行向量B[1]中表示出來(lái)。對(duì)于非英文字母表的字符，一概認(rèn)為是字符‘*’，相應(yīng)的在表格B中對(duì)應(yīng)的行向量B[26]就為全1。

在計(jì)算表B時(shí)，需要考慮兩個(gè)位置問(wèn)題：

(1)目前正在計(jì)算模式串的第幾個(gè)字符位置;

(2)計(jì)算的位向量應(yīng)該是表格B中的第幾行。

變量decoder就是為了描述第一個(gè)位置問(wèn)題而設(shè)置的。當(dāng)目前正在處理的字符在模式串的第一位時(shí)，對(duì)模式特征表B的計(jì)算結(jié)果只針對(duì)表的某一行向量的最低位(即最右邊的一位)，具體是哪一行，那是第二個(gè)位置問(wèn)題。在順序讀入模式字符串時(shí)，應(yīng)該一直明確當(dāng)前讀入的字符在模式字符串中的位置。為了明確這一位置，就另行設(shè)定了這個(gè)decoder向量。當(dāng)正在讀入的字符是模式串的第一個(gè)字符時(shí)，相應(yīng)的decoder的最低一位(最右邊一位)就設(shè)置為0，其他位設(shè)置為1。同理，當(dāng)正在讀入的字符是模式串的第二個(gè)字符時(shí)，相應(yīng)的decoder從右往左的第二位就設(shè)置為0，其他位設(shè)置為1。其他情形以此類(lèi)推。

如果模式串長(zhǎng)為16，就可以把算法中的字符c對(duì)應(yīng)的模式特征表B中行向量B[c]的長(zhǎng)度設(shè)定為16，即為一個(gè)reg[15:0]的變量。在計(jì)算表B時(shí)，另外設(shè)定了一個(gè)長(zhǎng)為16位的寄存器變量decoder，變量類(lèi)型為reg[15:0]，用來(lái)記錄字符c在模式串從低到高(0到15位)16個(gè)可能的位置中出現(xiàn)的確切位置，從而方便計(jì)算B[c]。計(jì)算decoder的部分verilog代碼如下：

case(str_len)

5'd0:decoder[15:0]<=16'hfffe;

5'd1:decoder[15:0]<=16'hfffd;

5'd2:decoder[15:0]<=16'hfffb;

5'd3:decoder[15:0]<=16'hfff7;

//這里省略5'd4到5'd15的情形

endcase

如果讀入的字符是模式字符串的第一個(gè)字符，decoder的二進(jìn)制表示就是16'b1111_1111_1111_1110，即為16'hfffe。同理，當(dāng)處理到模式串的第二個(gè)字符時(shí)，變量decoder的二進(jìn)制表示就是16'b1111_1111_1111_1101，即為16'hfffd。這樣，就通過(guò)設(shè)置一個(gè)類(lèi)似位掩碼向量的decoder寄存器變量，解決了上述的第一個(gè)位置問(wèn)題。

第二個(gè)位置問(wèn)題需要由正在處理的模式串字符確定。事先規(guī)定模式特征表B的行數(shù)為27，前26行表示26個(gè)英文字母，而且不區(qū)分大小寫(xiě)，最后一行表示其他任意字符。

還是在模式串長(zhǎng)度不超過(guò)16個(gè)字符的假設(shè)下，進(jìn)行模式串特征制表。按照Shift-Or算法，每讀入一個(gè)模式串字符c，都可能需要更新模式特征向量B[c]。在這里需要用到上述第一個(gè)位置問(wèn)題里的寄存器變量reg[15:0]decoder，先把當(dāng)前的decoder向量和與當(dāng)前讀入的模式串字符c相應(yīng)的特征向量B[c]作按位與運(yùn)算，這樣就可以針對(duì)B[c]的某一位進(jìn)行操作，繼而完成對(duì)B[c]的賦值。部分verilog代碼如下：

case(c)

8'b0100_0001:B[0]<=(B[0] &decoder[15:0]);//字符‘A’

8'b0110_0001:B[0]<=(B[0] &decoder[15:0]);//字符‘a(chǎn)’

8'b0100_0010:B[1]<=(B[1] &decoder[15:0]);//字符‘B’

8'b0110_0010:B[1]<=(B[1] &decoder[15:0]);//字符‘b’

//這里省略另外24個(gè)英文字母

default:B[26]<=(B[26] &decoder[15:0]);//其他字符

endcase

可以發(fā)現(xiàn)Shift-Or算法實(shí)際上利用了空間換時(shí)間[13]的算法思想，在開(kāi)始對(duì)文本串進(jìn)行字符串匹配前，需要對(duì)模式串進(jìn)行分析計(jì)算，得出一張模式字符串特征表，也就是算法的預(yù)處理過(guò)程。構(gòu)成這張二維數(shù)據(jù)表的元素為0和1，表格包括了字符串匹配系統(tǒng)所有可以識(shí)別的字符。這里將系統(tǒng)可以識(shí)別的字符集定義為所有英文字母，所以系統(tǒng)的模式特征表格有27行，前26行分別對(duì)應(yīng)26個(gè)英文字母，最后一行代表可能在文本串出現(xiàn)的任意其他字符，比如空格或標(biāo)點(diǎn)符號(hào)。每一行作為描述對(duì)應(yīng)字符在模式串中的特征，反映了該字符在模式串中的出現(xiàn)位置信息。在接下來(lái)對(duì)文本串進(jìn)行匹配時(shí)，就通過(guò)這樣一張模式字符串特征表來(lái)對(duì)每個(gè)讀入的文本串字符操作，用表格B里的行向量和字符串匹配狀態(tài)編碼，即位掩碼D進(jìn)行位并行操作，節(jié)省了大量時(shí)間。在制表時(shí)考慮到字母大小寫(xiě)的問(wèn)題，從而實(shí)現(xiàn)了允許大小寫(xiě)通用的字符串匹配，增加了系統(tǒng)的靈活性。

2.1.2 文本串匹配模塊的實(shí)現(xiàn)

字符串匹配模塊對(duì)從RAM取出的數(shù)據(jù)進(jìn)行判別后分流，對(duì)模式字符串和文本字符串分別進(jìn)行不同的處理。文本字符串實(shí)際上應(yīng)該是在FPGA對(duì)模式字符串已經(jīng)預(yù)處理過(guò)后才送入FPGA進(jìn)行字符串匹配，所以在實(shí)現(xiàn)文本串匹配模塊時(shí)，假設(shè)模式字符串已經(jīng)在之前的數(shù)據(jù)包中給入FPGA，并且算法對(duì)模式串的預(yù)處理部分已經(jīng)完成，即模式串特征表已經(jīng)計(jì)算得出。

Shift-Or算法在對(duì)文本串進(jìn)行匹配時(shí)，借助一個(gè)由0、1組成的位掩碼D，判斷匹配是否成功。這個(gè)位掩碼D在之前介紹過(guò)，長(zhǎng)度不少于模式字符串長(zhǎng)，和預(yù)處理模塊計(jì)算得到的模式特征向量B[c]的長(zhǎng)度相同。同時(shí)，D也可以理解為匹配狀態(tài)編碼。位掩碼D的初始值為全1，當(dāng)模式字符串的第一個(gè)字符和最后讀入的文本串字符相匹配時(shí)，D的最低位由1改為0，其余位為1；當(dāng)模式串的前兩個(gè)字符和最后讀入的文本串的兩個(gè)字符同時(shí)匹配時(shí)，D的第二位由1改為0，其余位為1，以此類(lèi)推。這樣的狀態(tài)編碼清晰記錄和表現(xiàn)了字符串匹配過(guò)程。可以非常直觀地推斷，如果模式串長(zhǎng)為m，那么每當(dāng)位掩碼D的第m位(從右往左第m位)為0時(shí)，表明找到了一個(gè)成功匹配。

與之前一樣，這里還是先假設(shè)模式串的長(zhǎng)度為16。那么，模式特征表B中字符c對(duì)應(yīng)的B[c]特征向量長(zhǎng)度就為16，字符串匹配過(guò)程中的狀態(tài)編碼D也為長(zhǎng)度16的向量。在設(shè)計(jì)中，模式特征向量B[c]和字符串匹配狀態(tài)編碼D都定義為reg[15:0]的寄存器變量。負(fù)責(zé)更新匹配狀態(tài)編碼D的部分verilog代碼如下：

case(ch)

8'b0100_0001:D[15:0]<=(D[15:0]<<1|B[0]);//‘A’

8'b0110_0001:D[15:0]<=(D[15:0]<<1|B[0]);//‘a(chǎn)’

8'b0100_0010:D[15:0]<=(D[15:0]<<1|B[1]);//‘B’

8'b0110_0010:D[15:0]<=(D[15:0]<<1|B[1]);//‘b’

//這里省略讀入字符從‘C’/‘c’到‘Z’/‘z’的情況

default:D[15:0]<=(D[15:0]<<1|B[26]);//'*'

endcase

包含有文本串的數(shù)據(jù)包流進(jìn)FPGA被順序讀取，F(xiàn)PGA每讀取一個(gè)文本字符，對(duì)字符進(jìn)行判斷查表處理。如果該文本字符屬于英文字母字符集，則系統(tǒng)可以在模式特征表格B里找到相對(duì)應(yīng)的模式特征向量，更新當(dāng)前的字符串匹配狀態(tài)編碼；如果不屬于英文字母字符集，則可以肯定與模式串不匹配，所用的B[*]為全1，更新得到的匹配狀態(tài)編碼會(huì)直接回到初始全1狀態(tài)。字符串匹配是否成功可以從這個(gè)匹配狀態(tài)編碼得出結(jié)論。

2.2 匹配信息返回模塊實(shí)現(xiàn)

在Shift-Or算法中，字符串匹配是否成功是根據(jù)匹配狀態(tài)編碼，即文本串匹配模塊中的位掩碼D的最高位來(lái)判斷。如果D的最高位為1，則匹配不成功或還沒(méi)有完全匹配；如果D的最高位為0，則模式串在文本串中匹配成功。確定匹配成功后，系統(tǒng)需要以某種方式返回這個(gè)匹配成功信息，其中還應(yīng)該包括在文本串中的成功匹配位置。

每讀入一個(gè)文本串字符c，Shift-Or算法會(huì)更新一次匹配狀態(tài)編碼D。延續(xù)之前的例子，在FPGA實(shí)現(xiàn)中，verilog代碼為：

D[15:0]<=(D[15:0]<<1|B[c])；

注意這里的賦值采用的是非阻塞賦值符，在一個(gè)語(yǔ)句塊內(nèi)，首先計(jì)算該塊內(nèi)所有非阻塞賦值符右邊的值，然后這些值再賦給左邊的寄存器，賦值過(guò)程分成了兩個(gè)小步驟。在這里對(duì)狀態(tài)編碼D的更新中，新的D要在下一時(shí)鐘周期內(nèi)才穩(wěn)定。在完成對(duì)新的匹配狀態(tài)編碼計(jì)算后的下一個(gè)時(shí)鐘周期內(nèi)檢查這個(gè)新的狀態(tài)編碼D的最高位，為0則匹配成功。

在順序讀入文本串的過(guò)程中，設(shè)置一個(gè)計(jì)數(shù)器用來(lái)計(jì)算當(dāng)前正在處理的字符在文本串的序數(shù)。當(dāng)計(jì)數(shù)器值為i的時(shí)候，匹配狀態(tài)編碼D的最高位變成0，表明在搜索到文本串的第i個(gè)字符的時(shí)候，模式串和已經(jīng)讀入的文本串后綴完全匹配。如果模式串長(zhǎng)度為m,可推算出字符串匹配成功發(fā)生在文本串第i-m+1個(gè)字符的位置。這個(gè)匹配成功的位置信息作為數(shù)據(jù)凈荷封裝在一個(gè)數(shù)據(jù)幀里，通過(guò)以太網(wǎng)模塊返回。

3 硬件與系統(tǒng)測(cè)試

3.1 硬件開(kāi)發(fā)平臺(tái)

實(shí)驗(yàn)所使用的硬件開(kāi)發(fā)平臺(tái)包括兩個(gè)主要模塊：千兆以太網(wǎng)模塊和FPGA開(kāi)發(fā)板模塊。以太網(wǎng)模塊提供了一個(gè)千兆以太網(wǎng)口，用來(lái)收發(fā)數(shù)據(jù)幀。與以太網(wǎng)模塊相連的FPGA開(kāi)發(fā)平臺(tái)是系統(tǒng)設(shè)計(jì)的重點(diǎn)，所要完成的字符串匹配算法在這里實(shí)現(xiàn)。

千兆以太網(wǎng)模塊使用了Marvell公司的88E1111芯片。88E1111是一個(gè)用于吉比特以太網(wǎng)的物理層收發(fā)器，它支持1000BASE-T、100BASE-T和10BASE-T類(lèi)型的以太網(wǎng)。88E1111芯片使用標(biāo)準(zhǔn)數(shù)字CMOS工藝制造，包含所有必需的有源電路來(lái)實(shí)現(xiàn)物理層功能。

所選用的FPGA開(kāi)發(fā)板型號(hào)是EP4CE40F23C8N，包括Altera公司的Cyclone IV可編程FPGA芯片。開(kāi)發(fā)板可以提供高達(dá)3.125 Gbps的數(shù)據(jù)傳輸速率，支持千兆以太網(wǎng)協(xié)議，并且功耗低，非常適合于高速網(wǎng)絡(luò)數(shù)據(jù)處理的應(yīng)用。

3.2 實(shí)驗(yàn)環(huán)境搭建

如圖2所示，實(shí)驗(yàn)包括兩臺(tái)電腦和千兆以太網(wǎng)FPGA平臺(tái)。

圖2 實(shí)驗(yàn)設(shè)備

圖中左邊計(jì)算機(jī)和以太網(wǎng)模塊由網(wǎng)線(xiàn)連接，右邊計(jì)算機(jī)與FPGA模塊由USB blaster連接。通過(guò)左邊計(jì)算機(jī)上的科來(lái)數(shù)據(jù)包產(chǎn)生軟件產(chǎn)生以太網(wǎng)數(shù)據(jù)幀，與以太網(wǎng)模塊通信。在右邊計(jì)算機(jī)上的Quartus II軟件上使用verilog語(yǔ)言編程，然后通過(guò)USB blaster將程序下載進(jìn)FPGA。FPGA開(kāi)發(fā)板型號(hào)為EP4CE4DF 23CBN，包括Altera公司的Cyclone IV FPGA芯片。千兆以太網(wǎng)模塊使用Marvell公司的88E1111芯片。FPGA使用鎖相環(huán)PLL[14]產(chǎn)生頻率為125 MHz的時(shí)鐘，每時(shí)鐘處理一個(gè)字節(jié)，而每字節(jié)8 bit，與千兆以太網(wǎng)口速率匹配。

3.3 測(cè)試結(jié)果及分析

測(cè)試中使用科來(lái)數(shù)據(jù)包產(chǎn)生軟件產(chǎn)生包含模式串的數(shù)據(jù)，經(jīng)過(guò)以太網(wǎng)模塊發(fā)送給FPGA模塊。通過(guò)網(wǎng)絡(luò)抓包軟件獲取UDP數(shù)據(jù)包。這個(gè)UDP數(shù)據(jù)包的目標(biāo)端口號(hào)是0x1000，系統(tǒng)中表示凈荷中的數(shù)據(jù)為模式字符串。測(cè)試使用的模式字符串為“ABCABCABCABCABCA”，長(zhǎng)度為16。

FPGA在接收到包含模式字符串的數(shù)據(jù)之后，將凈荷數(shù)據(jù)取出按照Shift-Or算法對(duì)模式串進(jìn)行預(yù)處理，主要任務(wù)就是計(jì)算模式特征表B。通過(guò)軟件Quartus II中的SignalTap可以觀察到算法運(yùn)行情況。如圖3所示，可以看到定義的寄存器變量decoder和讀取的模式串字符q1的時(shí)序圖。變量clk為時(shí)鐘。str_len用來(lái)對(duì)模式串字符計(jì)數(shù)。字符串“A,B,C”的16進(jìn)制表示就是“41h,42h,43h”，從圖中可以找到對(duì)應(yīng)的位置。模式串預(yù)處理模塊中decoder計(jì)算完成后開(kāi)始計(jì)算模式特征表B，在模式串預(yù)處理時(shí)序圖中最下一行的b變量可以觀察到。

模式串預(yù)處理完成后，向FPGA發(fā)送文本字符串，與之前發(fā)送模式字符串的方法相同。文本串?dāng)?shù)據(jù)包與模式串?dāng)?shù)據(jù)包不同的是UDP的目標(biāo)端口號(hào)，包含文本串?dāng)?shù)據(jù)的UDP使用0x8000的目標(biāo)端口號(hào)。用抓包軟件捕捉到UDP包。

FPGA接收到上述包含文本串的數(shù)據(jù)包后，對(duì)其展開(kāi)深度內(nèi)容檢測(cè)，即對(duì)UDP數(shù)據(jù)凈荷進(jìn)行模式串匹配。在SignalTap中可以觀察到在時(shí)鐘信號(hào)clk的驅(qū)動(dòng)下，文本串順序讀入字符q2和匹配狀態(tài)編碼D的時(shí)序圖。這里的字符串匹配用到了模式特征向量B[0],B[1],B[2]，它們分別為6DB6h，DB6Dh，B6DBh。

為了更細(xì)致地觀察匹配狀態(tài)編碼D，將字符串匹配成功的部分放大，如圖4所示。在編號(hào)35的時(shí)鐘周期內(nèi)，16位狀態(tài)編碼D的最高位變位0，表示匹配成功。

注意到當(dāng)D的最高位為0時(shí)，D=“01101101 10110110”，以“011”的形式重復(fù)，這正好符合測(cè)試使用的模式串“ABCABCABCABCABCA”以“ABC”的形式重復(fù)。通過(guò)手工計(jì)算，也可以驗(yàn)證該算法在FPGA上正確運(yùn)行。實(shí)際上在圖4中編號(hào)33的時(shí)鐘信號(hào)上升沿的地方，模式字符串就已經(jīng)完整地在文本字符串中出現(xiàn)了，而此時(shí)的D還沒(méi)有更新，要到下一個(gè)時(shí)鐘周期內(nèi)D才會(huì)更新，最高位改寫(xiě)為0。

圖3 模式串預(yù)處理時(shí)序

圖4 字符串匹配結(jié)果時(shí)序

算法理論上，模式串“ABCABCABCABCABCA”對(duì)應(yīng)的模式特征表項(xiàng)B[0]代表字符‘A’,B[0]應(yīng)該為“0110110110110110”。實(shí)際測(cè)試中，計(jì)算得到B[0]是“6DB6”(十六進(jìn)制表示)，換算成二進(jìn)制為0110_1101_1011_0110，與理論值相同。同樣的方式可以驗(yàn)證字符‘B’的模式特征向量B[1]和字符‘C’的模式特征向量B[2]，實(shí)際的模式特征表與理論相符。

當(dāng)順序讀入文本串時(shí)，匹配狀態(tài)編碼D會(huì)相應(yīng)更新，可以跟蹤D的更新過(guò)程來(lái)驗(yàn)證系統(tǒng)的工作。初始時(shí)，16位的D為全1，實(shí)驗(yàn)中，讀入不屬于英文字符集的字符時(shí)，D一直保持全1。當(dāng)讀入字符‘A’，D在下一時(shí)鐘周期里更新為“1111_1111_1111_1110”，繼續(xù)讀入字符‘B’時(shí)，D更新為“1111_1111_1111_1101”；讀入文本串的后綴為“ABCA”時(shí)，D將在下一時(shí)鐘周期內(nèi)更新為“1111_1111_1111_0110”。可以發(fā)現(xiàn)實(shí)驗(yàn)中匹配狀態(tài)編碼D的更新與Shift-Or算法理論完全相符。

系統(tǒng)的字符串匹配處理速率與系統(tǒng)時(shí)鐘頻率有關(guān)。該系統(tǒng)FPGA通過(guò)鎖相環(huán)PLL產(chǎn)生頻率為125MHz的時(shí)鐘信號(hào)。系統(tǒng)每個(gè)時(shí)鐘周期處理一個(gè)字符，而一個(gè)字符長(zhǎng)8bit，可以算出該系統(tǒng)可以支持千兆以太網(wǎng)上的字符串匹配應(yīng)用。

4 結(jié)束語(yǔ)

網(wǎng)絡(luò)服務(wù)器承載了大量的用戶(hù)數(shù)據(jù)流量，在當(dāng)今網(wǎng)絡(luò)數(shù)據(jù)的傳輸速率飛速發(fā)展，并且用戶(hù)越來(lái)越多的背景下，數(shù)據(jù)流量很容易達(dá)到千兆甚至萬(wàn)兆比特每秒。數(shù)據(jù)傳輸速度的提高已經(jīng)成為了用戶(hù)最基本、最重要的需求。然而隨著計(jì)算機(jī)通信技術(shù)的進(jìn)步，如果只是簡(jiǎn)單地傳輸數(shù)據(jù)，那么并不能實(shí)現(xiàn)更有意義的功能，需要對(duì)服務(wù)器中所承載的數(shù)據(jù)進(jìn)行處理。文中在千兆以太網(wǎng)的測(cè)試環(huán)境中，實(shí)現(xiàn)了線(xiàn)速對(duì)數(shù)據(jù)包凈荷內(nèi)容的字符串匹配。選擇FPGA作為字符串匹配算法實(shí)現(xiàn)平臺(tái)，針對(duì)FPGA在并行計(jì)算上的強(qiáng)大性能以及FPGA可編程的靈活性，選用以位并行計(jì)算為特點(diǎn)的Shift-Or算法。實(shí)驗(yàn)在千兆以太網(wǎng)FPGA開(kāi)發(fā)平臺(tái)上進(jìn)行，在Altera生產(chǎn)的CycloneIVFPGA芯片里實(shí)現(xiàn)了Shift-Or字符串匹配算法。實(shí)驗(yàn)中，通過(guò)一臺(tái)計(jì)算機(jī)產(chǎn)生數(shù)據(jù)幀，數(shù)據(jù)幀通過(guò)千兆以太網(wǎng)模塊傳給FPGA，在FPGA中完成字符串匹配。通過(guò)實(shí)驗(yàn)驗(yàn)證，結(jié)果與理論相符，達(dá)到了在千兆以太網(wǎng)下線(xiàn)速實(shí)現(xiàn)字符串匹配的目標(biāo)。

[1] 于 靜.面向Web應(yīng)用的安全服務(wù)器網(wǎng)卡的研究與設(shè)計(jì)[D].濟(jì)南：濟(jì)南大學(xué)，2010.

[2] 鄭慶良，張 翔,楊 瑩.網(wǎng)絡(luò)服務(wù)器模型分析與實(shí)現(xiàn)[J].杭州電子工業(yè)學(xué)院學(xué)報(bào),2004,24(4):95-98.

[3] 黃 建.入侵檢測(cè)系統(tǒng)中字符串匹配算法與實(shí)現(xiàn)[D].武漢：華中科技大學(xué),2008.

[4]FiskM,VargheseG.Ananalysisoffaststringmatchingappliedtocontent-basedforwardingandintrusiondetection[R].SanDiego:UniversityofCalifornia,2002.

[5]KnuthDE,MoorisJH,PrattJVR.Fastpatternmatchinginstrings[J].SIAMJournalonComupting,1977,6(2):323-350.

[6]BoyerRS,MooreJS.Afaststringsearchingalgorithm[J].CommunicationsoftheACM,1977,20(10):762-772.

[7] 邱慶哲.入侵檢測(cè)系統(tǒng)中檢測(cè)引擎的研究與實(shí)現(xiàn)[D].武漢：華中科技大學(xué)，2007.

[8] 王 誠(chéng)，吳繼華.AlteraFPGA/CPLD設(shè)計(jì)[M].北京:人民郵電出版社,2005.

[9]NavarrG.柔性字符串匹配[M].中科院計(jì)算所網(wǎng)絡(luò)信息安全研究組,譯.北京:電子工業(yè)出版社,2007:15-20.

[10] 孫 鵬，董玉華，韓正之.基于數(shù)據(jù)鏈路層的局域網(wǎng)流量統(tǒng)計(jì)的實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用,2002,38(5):150-152.

[11] 王長(zhǎng)清，張素娟,蔣景紅.基于以太網(wǎng)幀的嵌入式數(shù)據(jù)傳輸方案及實(shí)現(xiàn)[J].計(jì)算機(jī)工程與設(shè)計(jì),2011,32(6):1952-1956.

[12]SalamonS,MaxmellWM.Storageoframsemen[J].AnimalReproductionScience,2000,62(1-3):77-111.

[13]KiltsS.高級(jí)FPGA設(shè)計(jì):結(jié)構(gòu)、實(shí)現(xiàn)和優(yōu)化[M].孟憲元,譯.北京:機(jī)械工業(yè)出版社,2009.

[14] 李桂華，孫仲林，吉利久.CMOS鎖相環(huán)PLL的設(shè)計(jì)研究[J].半導(dǎo)體雜志,2000,25(3):30-37.

Implementation of FPGA Applied to Web Server Matching Algorithm

MENG Xu-dong1,2,XU Qiang-kai1,2

(1.Key Laboratory of Broadband Wireless Communication and Sensor Networkof Ministry of Education,Nanjing University of Posts and Telecommunications,Nanjing 210003,China；2.Telecommunications Network Integration Lab of Jiangsu,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

Web services have become part of the modern life,and people need to get information through the Web quickly and require fast keyword search on the Web.To realize fast pattern matching on the Web server side,the Web server is needed to process the data stream through the server for string matching quickly.String matching algorithm is introduced systematically,in which the analysis is mainly focused on the use of a Shift-Or algorithm with parallel computing.Using FPGA to implement,because FPGA-based implementation can have a higher process rate than software implementations,and be more flexible than the ASIC implementation.The Shift-Or string matching algorithm is implemented in FPGA,and then tested in gigabit Ethernet.The results show that the design can meet the high speed packets rate under network environment of gigabit Ethernet.

Web server;string matching;Shift-Or;FPGA

2016-02-15

2016-06-09

時(shí)間：2016-11-21

國(guó)家“973”重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃項(xiàng)目(2013CB329005)

孟旭東(1959-)，男，副研究員，研究方向?yàn)殡娦啪W(wǎng)絡(luò)和IP網(wǎng)絡(luò)的交換、異構(gòu)網(wǎng)絡(luò)集成及業(yè)務(wù)融合、未來(lái)互聯(lián)網(wǎng)體系結(jié)構(gòu)、網(wǎng)絡(luò)計(jì)算與分布式處理；許強(qiáng)凱(1991-)，男，碩士研究生，研究方向?yàn)橄乱淮ㄐ啪W(wǎng)絡(luò)。

http://www.cnki.net/kcms/detail/61.1450.TP.20161121.1641.036.html

TP301.6

A

1673-629X(2016)12-0142-06

10.3969/j.issn.1673-629X.2016.12.031