精確單字符串匹配BM算法及其在snort中的C語言實現(xiàn)代碼解析

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

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

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

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

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

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

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

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

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

10、nt*)malloc(pLen*sizeof(int);int *sptr = shift + pLen - 1;/方便給好后綴表進行賦值的指標，初始指向模式串最后一個字符位置的地址char *pptr = ptrn + pLen - 1;/記錄好后綴表邊界位置的指標，開始指向模式串最后一個字符的地址char c; /用于保存模式串中最后一個字符if(shift = NULL) /空間分配失敗則報錯并退出fprintf(stderr,malloc failed!);return 0;c = *(ptrn + pLen - 1);/保存模式串中最后一個字符，因為要反復用到它*sptr = 1;/

11、以最后一個字符為邊界時，確定移動距離為1/pptr-;/邊界移動到倒數(shù)第二個字符（這句是我自己加上去的，因為我總覺得不加上去會有BUG，大家試試abcdd的情況，即末尾兩位重復的情況）while(sptr- != shift)/該最外層循環(huán)完成給好后綴表中每一個單元進行賦值的工作char *p1 = ptrn + pLen - 2, *p2,*p3;/該do.while循環(huán)完成以當前pptr所指的字符為邊界時，要移動的距離dowhile(p1 = ptrn & *p1- != c);/該空循環(huán)，尋找與最后一個字符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所在字符為邊界時，要移動的位置/*在這里聲明一句，*sptr = （shift + pLen - sptr） + p2 - p3; 看被用括號括起來的部分，如果只需要計算字符串移動的距離，那么括號中的那部分是不需要的。 因為在字符串自左向右做匹配的時候，指標是一直向左移的，這里*sptr保存的內(nèi)容，實際是指

13、標要移動距離，而不是字符串移動的距離。我想SNORT是出于性能上的考慮，才這么做的。 */pptr-;/邊界繼續(xù)向前移動return shift;/*函數(shù)：int* BMSearch(char *, int , char *, int, int *, int *)目的：判斷文本串T中是否包含模式串P參數(shù)： buf = 文本串Tblen = 文本串T長度ptrn = 模式串PPLen = 模式串P長度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) /模式串為空則無需查找，返回return 1;while (b_idx = blen)/計算字符串是否匹配到了盡頭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