1、精確單字符串匹配BM算法及其在snort中的C語(yǔ)言實(shí)現(xiàn)代碼解析一、BM算法概念首先，先簡(jiǎn)單說(shuō)明一下有關(guān)BM算法的一些基本概念。 BM算法是一種精確字符串匹配算法（區(qū)別于模糊匹配）。 BM算法采用從右向左比較的方法，同時(shí)應(yīng)用到了兩種啟發(fā)式規(guī)則，即壞字符規(guī)則和好后綴規(guī)則，來(lái)決定向右跳躍的距離。二、BM算法思想1、三個(gè)shift函數(shù)：d1,d2,d3，函數(shù)的作用是決定當(dāng)匹配不成功時(shí)窗口的移動(dòng)位數(shù)。2、假設(shè)一個(gè)情況：已經(jīng)讀入了一個(gè)既是搜索窗口中的文本的后綴，同時(shí)也是模式串后綴的字符串u,并且讀入的下一個(gè)文本字符與模式串的下一個(gè)字符a不相等。3、窗口安全移動(dòng)是指窗口移動(dòng)意味著讀入新的字符，放棄上一個(gè)窗口

2、的前面幾個(gè)字符，要保證放棄的字符確實(shí)無(wú)法參與匹配。窗口移動(dòng)方向是從前向后。算法的核心思想是對(duì)于模式串，可能至少有2個(gè)相同部分，這些部分肯定有一個(gè)在模式串的后綴，其它的部分可能在模式串的中間，也可能在模式串的前綴，在后綴搜索時(shí)，發(fā)現(xiàn)了文本串和模式串的部分匹配X，此時(shí)，如果模式串除了后綴外，其它部分還含有X，則使文本串和模式中發(fā)生不匹配的讀入的字符加上原來(lái)的匹配的X形成的部分有可能與模式串其它部分的X發(fā)生匹配（如果與模式串所有的X不匹配，則說(shuō)明這個(gè)窗口內(nèi)不可能發(fā)生匹配），安全地向后移動(dòng)窗口，放棄的部分肯定不會(huì)發(fā)生匹配了。1）d1:后綴u在模式串p中的另一個(gè)位置是最右出現(xiàn)位置是j（不包括在模式串尾的

3、出現(xiàn)）,文本串的窗口安全移動(dòng)方法是將窗口移動(dòng)m-j字符，使文本中的u與模式串中最右邊的u的出現(xiàn)位置相對(duì)齊。對(duì)模式中的每個(gè)后綴，計(jì)算它到它的下一個(gè)出現(xiàn)之間的距離，即shift的d1，如果P的后綴u不在P中重復(fù)出現(xiàn)，則d1(u)被置為模式串長(zhǎng)度m2）d2:后綴u不出現(xiàn)在p中的任何其他位置。但u的后綴v可能是模式串p的一個(gè)前綴，需要對(duì)模式串所有的后綴計(jì)算第二個(gè)函數(shù)d2。對(duì)于P的每個(gè)后綴u,d2(u)表示既是P的前綴，同時(shí)也是u的后綴的最長(zhǎng)字符串v的長(zhǎng)度.3）d3:在搜索窗口中從后向前搜索時(shí)，在文本字符處不能成功匹配。保證下一次驗(yàn)證時(shí)文本字符一定與模式串中的一個(gè)字符相對(duì)應(yīng)（即：使上次匹配不成功的那個(gè)字

4、符能在模式串的第二個(gè)X部分匹配成功，在模式串中找到這個(gè)字符，該字符是X的前面一個(gè)字符），對(duì)每個(gè)字母表中的每個(gè)字符，d3()表示在模式串的最右出現(xiàn)位置到模式串末尾的距離，如果不在P中，d3為m4、讀入文本字符串u并在字符上不匹配時(shí)，進(jìn)行如下幾次比較：1） 第一次：取d1(u)和d3()中較大值。2）第二次:以上面的比較結(jié)果與m-d2(u)中的較小者，因?yàn)楹笳呤亲畲蟮陌踩苿?dòng)距離。5、如果抵達(dá)了窗口的起始位置，說(shuō)明發(fā)現(xiàn)階段一個(gè)成功匹配，用d2計(jì)算窗口的下一次移動(dòng)距離，進(jìn)行繼續(xù)匹配。三、BM算法的基本流程圖解設(shè)文本串T，模式串為P。首先將T與P進(jìn)行左對(duì)齊，然后進(jìn)行從右向左比較，如下圖所示:若是某趟比

5、較不匹配時(shí)，BM算法就采用兩條啟發(fā)式規(guī)則，即壞字符規(guī)則和好后綴規(guī)則，來(lái)計(jì)算模式串向右移動(dòng)的距離，直到整個(gè)匹配過(guò)程的結(jié)束。 下面，來(lái)詳細(xì)介紹一下壞字符規(guī)則和好后綴規(guī)則。首先，詮釋一下壞字符和好后綴的概念。 請(qǐng)看下圖： 圖中，第一個(gè)不匹配的字符（紅色部分）為壞字符，已匹配部分（綠色）為好后綴。 1）壞字符規(guī)則（Bad Character）：在BM算法從右向左掃描的過(guò)程中，若發(fā)現(xiàn)某個(gè)字符x不匹配，則按如下兩種情況討論：i. 如果字符x在模式P中沒(méi)有出現(xiàn)，那么從字符x開始的m個(gè)文本顯然不可能與P匹配成功，直接全部跳過(guò)該區(qū)域即可。ii. 如果x在模式P中出現(xiàn)，則以該字符進(jìn)行對(duì)齊。用數(shù)學(xué)公式表示，設(shè)Ski

6、p(x)為P右移的距離，m為模式串P的長(zhǎng)度，max(x)為字符x在P中最右位置。例1： 下圖紅色部分，發(fā)生了一次不匹配。 計(jì)算移動(dòng)距離Skip(c) = 5 - 3 = 2，則P向右移動(dòng)2位。 移動(dòng)后如下圖： 2）好后綴規(guī)則（Good Suffix）：若發(fā)現(xiàn)某個(gè)字符不匹配的同時(shí)，已有部分字符匹配成功，則按如下兩種情況討論：i. 如果在P中位置t處已匹配部分P在P中的某位置t也出現(xiàn)，且位置t的前一個(gè)字符與位置t的前一個(gè)字符不相同，則將P右移使t對(duì)應(yīng)t方才的所在的位置。ii. 如果在P中任何位置已匹配部分P都沒(méi)有再出現(xiàn)，則找到與P的后綴P相同的P的最長(zhǎng)前綴x，向右移動(dòng)P，使x對(duì)應(yīng)方才P后綴所在的位

7、置。用數(shù)學(xué)公式表示，設(shè)Shift(j)為P右移的距離，m為模式串P的長(zhǎng)度，j 為當(dāng)前所匹配的字符位置，s為t與t的距離（以上情況i）或者x與P的距離（以上情況ii）。以上過(guò)程有點(diǎn)抽象，所以我們繼續(xù)圖解。例2：下圖中，已匹配部分cab（綠色）在P中再?zèng)]出現(xiàn)。再看下圖，其后綴T（藍(lán)色）與P中前綴P（紅色）匹配，則將P移動(dòng)到T的位置。移動(dòng)后如下圖：自此，兩個(gè)規(guī)則講解完畢。在BM算法匹配的過(guò)程中，取SKip(x)與Shift(j)中的較大者作為跳躍的距離。 BM算法預(yù)處理時(shí)間復(fù)雜度為O（m+s），空間復(fù)雜度為O(s)，s是與P, T相關(guān)的有限字符集長(zhǎng)度，搜索階段時(shí)間復(fù)雜度為O(mn)。最好情況下的時(shí)間

8、復(fù)雜度為O(n/m)，最壞情況下時(shí)間復(fù)雜度為O(mn)。四、BM模式匹配算法-實(shí)現(xiàn)C 語(yǔ)言代碼下面是根據(jù)SNORT中提取出的代碼實(shí)現(xiàn)的。#includeusing namespace std;/#define u_char unsigned char /* * 函數(shù)：int* MakeSkip(char *, int)目的：根據(jù)壞字符規(guī)則做預(yù)處理，建立一張壞字符表參數(shù)：ptrn = 模式串PPLen = 模式串P長(zhǎng)度 返回： int* - 壞字符表 */int* MakeSkip(char *ptrn, int pLen)int i;/為建立壞字符表，申請(qǐng)256個(gè)int的空間/*要申請(qǐng)256個(gè)

9、空間的原因，是因?yàn)橐粋€(gè)字符是8位，所以字符可能有2的8次方即256種不同情況*/int *skip = (int*)malloc(256*sizeof(int);if(skip = NULL) /如空間分配失敗則報(bào)錯(cuò)并退出fprintf(stderr, malloc failed!);return 0;/初始化壞字符表，256個(gè)單元全部初始化為模式串長(zhǎng)度pLenfor(i = 0; i 模式串PPLen = 模式串P長(zhǎng)度 返回： int* - 好后綴表 */int* MakeShift(char* ptrn,int pLen)/為好后綴表申請(qǐng)pLen個(gè)int的空間int *shift = (i

10、nt*)malloc(pLen*sizeof(int);int *sptr = shift + pLen - 1;/方便給好后綴表進(jìn)行賦值的指標(biāo)，初始指向模式串最后一個(gè)字符位置的地址char *pptr = ptrn + pLen - 1;/記錄好后綴表邊界位置的指標(biāo)，開始指向模式串最后一個(gè)字符的地址char c; /用于保存模式串中最后一個(gè)字符if(shift = NULL) /空間分配失敗則報(bào)錯(cuò)并退出fprintf(stderr,malloc failed!);return 0;c = *(ptrn + pLen - 1);/保存模式串中最后一個(gè)字符，因?yàn)橐磸?fù)用到它*sptr = 1;/

11、以最后一個(gè)字符為邊界時(shí)，確定移動(dòng)距離為1/pptr-;/邊界移動(dòng)到倒數(shù)第二個(gè)字符（這句是我自己加上去的，因?yàn)槲铱傆X(jué)得不加上去會(huì)有BUG，大家試試abcdd的情況，即末尾兩位重復(fù)的情況）while(sptr- != shift)/該最外層循環(huán)完成給好后綴表中每一個(gè)單元進(jìn)行賦值的工作char *p1 = ptrn + pLen - 2, *p2,*p3;/該do.while循環(huán)完成以當(dāng)前pptr所指的字符為邊界時(shí)，要移動(dòng)的距離dowhile(p1 = ptrn & *p1- != c);/該空循環(huán)，尋找與最后一個(gè)字符c匹配的字符所指向的位置p2 = ptrn + pLen - 2;p3 = p1;

12、while(p3 = ptrn & *p3- = *p2- & p2 = pptr);/該空循環(huán)，判斷在邊界內(nèi)字符匹配到了什么位置while(p3 = ptrn & p2 = pptr);*sptr = shift + pLen - sptr + p2 - p3;/保存好后綴表中，以pptr所在字符為邊界時(shí)，要移動(dòng)的位置/*在這里聲明一句，*sptr = （shift + pLen - sptr） + p2 - p3; 看被用括號(hào)括起來(lái)的部分，如果只需要計(jì)算字符串移動(dòng)的距離，那么括號(hào)中的那部分是不需要的。 因?yàn)樵谧址宰笙蛴易銎ヅ涞臅r(shí)候，指標(biāo)是一直向左移的，這里*sptr保存的內(nèi)容，實(shí)際是指

13、標(biāo)要移動(dòng)距離，而不是字符串移動(dòng)的距離。我想SNORT是出于性能上的考慮，才這么做的。 */pptr-;/邊界繼續(xù)向前移動(dòng)return shift;/*函數(shù)：int* BMSearch(char *, int , char *, int, int *, int *)目的：判斷文本串T中是否包含模式串P參數(shù)： buf = 文本串Tblen = 文本串T長(zhǎng)度ptrn = 模式串PPLen = 模式串P長(zhǎng)度skip = 壞字符表shift = 好后綴表 返回： int - 1表示成功（文本串包含模式串），0表示失?。ㄎ谋敬话Ｊ酱?*/int BMSearch(char *buf, int b

14、len, char *ptrn, int plen, int *skip, int *shift)int b_idx = plen; if (plen = 0) /模式串為空則無(wú)需查找，返回return 1;while (b_idx = blen)/計(jì)算字符串是否匹配到了盡頭int p_idx = plen, skip_stride, shift_stride;while (buf-b_idx = ptrn-p_idx)/開始匹配 if (b_idx shift_stride) ? skip_stride : shift_stride;/取大者return 0;int main(int arg

15、c, char* argv) /char test = 000000000CKAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA00; /char find = CKAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA00;/printf(%d,sizeof(int);/* char test = x90 x90 x90 x90 x90 x90 xe8xc0 xffxffxff/bin/shx90 x90 x90 x90 x90 x90 x90 x90 x90 x90; char find = xe8xc0 xffxffxff/bin/sh; */char test = avbcatelmaddd;char find = lmaddd; int *shift; int *skip;shift=MakeShift(find,sizeof(find)-1); skip=MakeSk