精确单字符串匹配BM算法及其在snort中的C语言实现代码解析

目录
[隐藏]

BM算法概念

  BM算法是一种精确字符串匹配算法(区别于模糊匹配)。

  BM算法采用从右向左比较 的方法,同时应用到了两种启发式规 则,即坏字符规则 好后缀规则 ,来决定向右跳跃的距离。

BM算法思想

1、三个shift函数:d1,d2,d3,函数的作用是决定当匹配不成功时窗口的 移动位数。

2、假设一个情况:已经读入了一个既是搜索窗口中的 文本的后缀,同时也是模式串后缀的字符串u,并且读入的下一个文本字符σ与模式串的下一个字符a不相等。

3、窗口安全移动是指窗口移动意味着读入新的字符, 放弃上一个窗口的前面几个字符,要保证放弃的字符确实无法参与匹配。窗口移动方向是从前向后。算法的核 心思想是对于模式串,可能至少有2个相同部分,这些部分肯定有一个在模式串的后缀,其它的部分可能在模式串的中间, 也可能在模式串的前缀,在后缀搜索时,发现了文本串和模式串的部分匹配X,此时,如果模式串除了后缀外,其它部分还含有X,则使文本串和模式中发生不匹配的读入的字符加上原来的匹配的X形成的部分有可能与模式串其它部分的X发生匹配(如果与模式串 所有的X不匹配,则说明这个窗口内不可能发生匹配),安全地向后移动窗口,放弃的部分肯定 不会发生匹配了。

1d1:后缀u在模式串p中的另一个位置是最右出现位置是j(不包括在模式串尾的出现 ),文本串的窗口安全移动方法是将窗口移动m-j字符,使文本中的 u与模式串中最右边的u的出现位置相对齐。对模式中的每个后缀,计算它到 它的下一个出现之间的距离,即shiftd1,如果P的后缀u不在P中重复出现,则d1(u)被置为模式串长度m

2d2:后缀u不出现在p中的任何其他位置。但u的后缀v可能是模式串p的一个前缀,需要对模式串所有的后缀计算第二个函 数d2。对于P的每个后缀u,d2(u)表示既是P的前缀,同时也是u的后缀的最长字符串v的长度.

3d3:在搜索窗口中从后向前搜索时,在文本字符σ处不能成功匹配。保证下一次验证时文本 字符σ一定与模式串中的一个字符σ相对应(即:使上次匹配不成功的那个字符能在模式串的第二个 X部分匹配成功,在模式串中找到这个字符,该字符是X的前面一个字符),对每个字母表中的每个字符σ,d3(σ)表示σ在模式串的最右出现位置到模式串末尾的距离, 如果σ不在P中,d3m

4、读入文本字符串u并在字符σ上不匹配时,进行如下几次比较:

1 第一次:取 d1(u)d3(σ)中较大值。
2)第二次:以上面的比较结果与m-d2(u)中的较小者,因为后者是最大的安全移动距离 。

5、如果抵达了窗口的起始位置,说明发现阶段一个成 功匹配,用d2计算窗口的下一次移动距离,进行继续匹配。

BM算法的基本流程图解 

设文本串T,模式串为P。首先将TP进行左对齐,然后进行从右向左比较  ,如下图所示:

    

   若是某趟比较不匹配时,BM算法就采用两条启发式规则,即坏字符规则 好后缀规则 ,来计算模式串向右移动的距离,直 到整个匹配过程的结束。

    下面,来详细介绍一下坏字符 规则 好后缀规则 

    首先,诠释一下坏字符和好后缀的概念。

    请看下图:

    

     图中,第一个不匹配的字符(红色部分)为坏字符,已匹配部分(绿 色)为好后缀。

    1)坏字符规则 (Bad Character):

 BM算法从右向左扫描的过程中,若发现某个字符 x不匹配,则按如下两种情况讨论:

i.  如果字符x在模式P中没有出现,那么从字符x开始的m个文本显然不可能与P匹配成功,直接全部跳过该区域即可。

ii. 如果x在模式P中出现,则以该字符进行对齐。

 用数学公式表示,设Skip(x)P右移的距离,m为模式串P的长度,max(x)为字符xP中最右位置。

           

          1

         下图红色部分,发生了一次不匹配。

              

        计算移动距离Skip(c) = 5 – 3 = 2,则P向右移动2位。

        移动后如下图:

              

        

    2)好后缀规则 (Good Suffix):

若发现某个字符不匹配的同时,已有部分字符匹配成功,则按如下两种情况讨论:

i.  如果在P中位置t处已匹配部分P'P中的某位置t'也出现,且位置t'的前一个字符与位置t的前一个字符不相同,则将P右移使t'对应t方才的所在的位置。

ii. 如果在P中任何位置已匹配部分P'都没有再出现,则找到与P'的后缀P''相同的P的最长前缀x,向右移动P,使x对应方才P''后缀所在的位置。  

 用数学公式表示,设Shift(j)P右移的距离,m为模式串P的长度,j 为当前所匹配的字符位置,st't的距离(以上情况i)或者xP''的距离(以上情况ii)。

           

以上过程有点抽象,所以我们继续图解。

2

下图中,已匹配部分cab(绿色)在P中再没出现。

    

再看下图,其后缀T'(蓝色)与P中前缀P'(红色)匹配,则将P'移动到T'的位置。

         

移动后如下图:

          

 自此,两个规则讲解完毕。

 BM算法匹配的过程中,取SKip(x)Shift(j)中的较大者作为跳跃的距离。

      BM算法预处理时间复杂度为Om+s),空间复杂度为O(s)s是与P, T相关的有限字符集长度,搜索阶段时间复杂度为O(m·n)

     最好情况下的时 间复杂度为O(n/m),最坏情况下时间复杂度为O(m·n)

BM模式匹配算法实现C 语言代码

   下面是SNORT中提取出的代码。

#include<iostream>
using namespace std;
//#define u_char unsigned char
/* ****************************************************************
    函数:int* MakeSkip(char *, int)
       目的:根据坏字符规则做预处理,建立一张坏字符表
       参数:
              ptrn => 模式串P
              PLen => 模式串P长度
    返回:
           int* – 坏字符表
 ****************************************************************/
int* makeskip(char *ptrn, int pLen)
{    
       int i;
       //为建立坏字符表,申请256int的空间
       /*PS:要申请256个空间胡原因,是因为一个字符是8位,所以字符可能有28次方即256种不同情况 */
       int *skip = (int*)malloc(256*sizeof(int));
 
       if(skip == NULL)
       {
              fprintf(stderr, "malloc failed!");
              return 0;
       }
 
       //初始化坏字符表,256个单元全部初始化为pLen
       for(i = 0; i < 256; i++)
       {
              *(skip+i) = pLen;
       }
       //给表中需要赋值的单元赋值,不在模式串中出现的字符就不用再赋值了
       while (pLen != 0)
       {
              *(skip+(unsigned char)*ptrn++) = pLen–;
       }
 
       return skip;
}
 
/****************************************************************
       函数:int* MakeShift(char *, int)
       目的:根据好后缀规则做预处理,建立一张好后缀表
       参数:
              ptrn => 模式串P
              PLen => 模式串P长度
    返回:
           int* – 好后缀表
 ****************************************************************/
int* MakeShift(char* ptrn,int pLen)
{
       //为好后缀表申请pLenint的空间
       int *shift = (int*)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;//以最后一个字符为边界时,确定移动1的距离
 
//     pptr–;//边界移动到倒数第二个字符(这句是我自己加上去的,因为我总觉得不加上去会有 BUG,大家试试"abcdd"的情况,即末尾两位重复的情况)
 
       while (sptr– != shift)//该最外层循环完成给好后缀表中每一个单元进行赋值 的工作
       {
              char *p1 = ptrn + pLen – 2, *p2,*p3;
              
              //do…while循环完成以当前pptr所指的字符为边界时,要移动的距离
              do{
                      while(p1 >= ptrn && *p1– != c);//该空循环,寻找与 最后一个字符c匹配的字符所指向的位置
                     
                      p2 = ptrn + pLen – 2;
                      p3 = p1;
                     
                      while(p3 >= ptrn && *p3– == *p2– && p2 >= pptr);//该空循环,判断在边界内字符匹配到了什么位置
 
              }while(p3 >= ptrn && p2 >= pptr);
 
              *sptr = shift + pLen – sptr + p2 – p3;//保存好后缀表中,以 pptr所在字符为边界时,要移动的位置
              /*
                PS:在这里我要声明一句,*sptr = shift + pLen – sptr + p2 – p3;
                   大家看被我用括号括起来的部分,如果只需要计算字符串移动的 距离,那么括号中的那部分是不需要的。
                       因为在字符串自左向右做匹配的时候,指标是一直向左移的,这里 *sptr保存的内容,实际是指标要移动
                       距离,而不是字符串移动的距离。我想SNORT是出于性能上的考虑,才这么做的。                 
              */
 
              pptr–;//边界继续向前移动
       }
 
       return shift;
}
 
/****************************************************************
       函数:int* BMSearch(char *, int , char *, int, int *, int *)
       目的:判断文本串T中是否包含模式串P
       参数:
           buf => 文本串T
              blen => 文本串T长度
              ptrn => 模式串P
              PLen => 模式串P长度
              skip => 坏字符表
              shift => 好后缀表
    返回:
           int – 1表示成功(文本串包含模式串),0表示失败(文本串不包含模式串)。
 ****************************************************************/
int BMSearch(char *buf, int blen, 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 < 0)
                              return 0;
                      if (p_idx == 0)
                      {    
                              return 1;
                      }
              }
              skip_stride = skip[(unsigned char)buf[b_idx]];//根据坏字符规则计算跳 跃的距离
              shift_stride = shift[p_idx];//根据好后缀规则计算跳跃的距离
              b_idx += (skip_stride > shift_stride) ? skip_stride : shift_stride;//取大者
       }
       return 0;
}
 
 
int main(int argc, char* argv[])
{
    //char test[] = "CKAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA ";
    //char find[] = "CKAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
              //printf("%d",sizeof(int));
/*   char test[] = "x90x90x90x90x90x90xe8xc0xffxffxff/bin/sh x90x90x90x90x90x90x90x90x90x90";
     char find[] = "xe8xc0xffxffxff/bin/sh";  */
 
       char test[] = "avbcatelmaddd";
       char find[] = "lmaddd";
 //   int i;
 //   int toks;
    int *shift;
    int *skip;
 
       shift=MakeShift(find,sizeof(find)-1);
    skip=makeskip(find,sizeof(find)-1);
 
   
    int ret = BMSearch(test, sizeof(test)-1, find, sizeof(find)-1, skip,shift);
       printf ("test:%sn",test);
       printf ("find:%sn",find);
       printf ("Result:");
       if(ret ==0)
       {
              printf("not foundn");
       }
       if (ret == 1)
       {
              printf("have foundn");
       }
 
    getchar();
    return 0;
}

 

点赞 (0)

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.