本文共 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/