本文共 5806 字，大约阅读时间需要 19 分钟。

上面是关于bm算法的原理介绍

接下来我基于snort-2.9.5分析源码实现，源码文件主要涉及到mstring.h|c、sp_pattern_match.h|c。

先看一下数据结构设计

typedef struct _PatternMatchData{...    /* 大小写是否敏感*/    int nocase;             /* Toggle case insensitity */    /* 模式串长度*/    u_int pattern_size;     /* size of app layer pattern */    /* 模式串内容*/    char *pattern_buf;      /* app layer pattern to match on */    /* 搜索函数  例如uniSearchReal*/    int (*search)(const char *, int, struct _PatternMatchData *);  /* search function */    /* 坏字表*/    int *skip_stride; /* B-M skip array */    /* 好后缀表*/    int *shift_stride; /* B-M shift array */...    /* 每条规则里面的规则选项理论可以无限长，所有解析时，使用双向链表进行管理*/    struct _PatternMatchData *prev; /* ptr to previous match struct */    struct _PatternMatchData *next; /* ptr to next match struct */}PatternMatchData；

坏字表实现函数：

/* * ptrn : 模式串 * plen : 串长度 * 返回坏字表 */int *make_skip(char *ptrn, int plen){    int  i;    /* 创建256 的ascii表数组， 每个字符的值为下表，存储的值为跳跃的长度 */    int *skip = (int *) SnortAlloc(256* sizeof(int));    /* 默认初始化为 长度加一， 表明该字符未在串中出现过*/    for ( i = 0; i < 256; i++ )        skip[i] = plen + 1;    /* 循环遍历模式串， 如果如果出现过，更新长度， 例如"abcda", skip['b'] = 4*/    while(plen != 0)        skip[(unsigned char) *ptrn++] = plen--;    return skip;}

好后缀函数实现 ：

int *make_shift(char *ptrn, int plen){    int *shift = (int *) SnortAlloc(plen * sizeof(int));    int *sptr = shift + plen - 1;    char *pptr = ptrn + plen - 1;    char c;     c = ptrn[plen - 1];    *sptr = 1;    while(sptr-- != shift)    {        char *p1 = ptrn + plen - 2, *p2, *p3;        do        {            while(p1 >= ptrn && *p1-- != 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--;    }    return shift;}

实际搜索函数

/* * buf : 目标串 * blen : 目标串长度 * ptrn : 模式串 * plen : 模式串长度 * skip : 模式串的坏字表 * shift : 模式串的好后缀 */int mSearch(const char *buf, int blen, const char *ptrn, int plen, int *skip, int *shift){    int b_idx = plen;...    if(plen == 0)        return 1;    /* 循环搜索模式串是否出现过 只要出现就直接返回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;}

以上是bm的实现：预处理（构造两个哈希表），搜索实现

简单举例分析这些函数与PatternMatchData如何关联snort启动的时候会注册一些回调函数进行规则解析，其中有一类是模式串的解析，例如规则中包含content:"snort"; uricontent:"suricata";。这类规则在解析的时候需要创建PatternMatchData对象，进行保存预处理信息，比如现在要分析的bm算法的坏字表和好后缀表skip_stride、shift_stride两个“哈希表”。

首先通过大致流程进行注册：

SnortInit => RegisterRuleOptions => SetupPatternMatch => RegisterRuleOption => PayloadSearchInit => NewNode

通过注册规则选项解析函数，在程序启动后解析规则时，当匹配到关键字时，会调用对应的规则选项的解析函数进行解析。

规则选项使用rule_opt_config_funcs链表进行管理（去重）。

...ParseConfigFile=> snort_conf_keywords(配置选项数组) => ParseAlert=> ParseRule=> ParseRuleOptions => rule_opt_config_funcs => PayloadSearchInit ...

#define func fptr.fptr#define vfunc fptr.void_fptrtypedef struct _RuleOptOverrideInitFuncNode{    /* 规则关键字 ：content, uricontent*/    char *keyword;     RuleOptType type;    union {        /* 实际的解析函数 例如content : PayloadSearchInit*/        RuleOptOverrideInitFunc fptr;        void *void_fptr;    } fptr;    RuleOptOtnHandler otn_handler;    struct _RuleOptOverrideInitFuncNode *next;} RuleOptOverrideInitFuncNode;

/* * sc : snort的最主要的一个结构，用于管理整个程序相关的信息：运行模式、日志配置、模式匹配引擎、数据统计 * data : 规则选项中对应的内容，content:"snort", data = "snort" * otn : 规则选项 * protocol : 暂且翻译 协议 ，未分析其用途 */static void PayloadSearchInit(struct _SnortConfig *sc, char *data, OptTreeNode * otn, int protocol){...    PatternMatchData *pmd;...    /* 创建PatternMatchData 对象，并将其挂在otn的ds_list[PLUGIN_PATTERN_MATCH]链表中（尾部）*/    pmd = NewNode(otn, PLUGIN_PATTERN_MATCH);...    /* 这个函数会对这个pmd进行预处理，设置坏字表和好后缀表 和 搜索函数*/    ParsePattern(opt_data, otn, PLUGIN_PATTERN_MATCH);...}

PatternMatchData * NewNode(OptTreeNode *otn, int type){    PatternMatchData *pmd = NULL;    if (otn->ds_list[type] == NULL)    {        otn->ds_list[type] = (PatternMatchData *)SnortAlloc(sizeof(PatternMatchData));        pmd = otn->ds_list[type];    }    else    {        /* 添加到 ds_list[type]的尾部，GetLastPmd 遍历到尾部*/        pmd = GetLastPmd(otn, type);        if (pmd != NULL)        {            pmd->next = (PatternMatchData *)SnortAlloc(sizeof(PatternMatchData));            pmd->next->prev = pmd;            pmd = pmd->next;        }        else        {            return NULL;        }    }    /* Set any non-zero default values here. */    pmd->offset_var = BYTE_EXTRACT_NO_VAR;    pmd->depth_var = BYTE_EXTRACT_NO_VAR;    pmd->distance_var = BYTE_EXTRACT_NO_VAR;    pmd->within_var = BYTE_EXTRACT_NO_VAR;    return pmd;}

void ParsePattern(char *rule, OptTreeNode * otn, int type){...    ds_idx = (PatternMatchData *) otn->ds_list[type];    /* 获取最后一个节点元素pmd*/    while(ds_idx->next != NULL)        ds_idx = ds_idx->next;    /* 设置模式串内容、长度、 搜索函数*/    ds_idx->pattern_buf = (char *)SnortAlloc(dummy_size+1);    memcpy(ds_idx->pattern_buf, tmp_buf, dummy_size);    ds_idx->pattern_size = dummy_size;    ds_idx->search = uniSearch;    /* 设置模式串的坏字表、好后缀表*/    make_precomp(ds_idx);...}

void make_precomp(PatternMatchData * idx){    if(idx->skip_stride)       free(idx->skip_stride);    if(idx->shift_stride)       free(idx->shift_stride);    /* 设置坏字表*/    idx->skip_stride = make_skip(idx->pattern_buf, idx->pattern_size);    /* 设置好后缀表*/    idx->shift_stride = make_shift(idx->pattern_buf, idx->pattern_size);}

snort的规则选项解析content:大致涉及到的点基本是这些了

转载地址：http://avtmd.baihongyu.com/