snort是一款著名的开源IPS，其主页地址:snort 官网。更详细的介绍网上很多，可自行搜索了解。本博客主要介绍snort-2.9.5版本的模式匹配引擎的加载和匹配。
模式匹配引擎主要使用多模式匹配算法和单模式匹配算法。先由多模式匹配算法大概确定有哪些规则可能匹配成功，然后再通过单模式匹配算法和其他规则选项去精确匹配。其配置格式如下：
config detection: search-method ac-split search-optimize max-pattern-len 20
snort的初始化函数主要做的工作是读取配置文件，第一次只是把所有配置项解析出来，第二次则是解析所有规则，将所有规则加载到对应的配置对象中。
SnortInit为入口，主要步骤如下（预处理模块、输出模块、动态库加载等暂不介绍）：
1：命令行解析，本博客暂不介绍，
2：注册一些解析配置的函数，作为准备工作， 主要由以下三个注册函数完成：
- RegisterOutputPlugins：注册输出日志解析配置等函数。在程序运行中会将防护日志记录到对应的配置中。
- RegisterPreprocessors：注册预处理模块解析配置等函数。由ARP、连接管理、http解析、端口扫描等模块，他们基本都是为后面的模式匹配引擎做准备工作的。
- RegisterRuleOptions：注册解析规则内容、匹配等函数。其中与模式匹配引擎息息相关的是content、uricontent字段的内容，模式匹配引擎根据其来生成的。
3：解析配置文件
- ParseSnortConf ：解析配置文件，模式匹配引擎的配置也在这个函数中完成
4：解析规则
- ParseRules：解析配置文件，将所有规则加载到内存中，然后做相关处理
5：生成引擎
- fpCreateFastPacketDetection：根据第3步解析到的模式匹配引擎配置，将第4步解析到的规则重新组织生成模式匹配引擎，在匹配规则中用。
void SnortInit(int argc, char **argv)
{
...
/* chew up the command line */
/* 命令行解析*/
ParseCmdLine(argc, argv);
...
if (!ScVersionMode())
{
/* Every run mode except version will potentially need output * If output plugins should become dynamic, this needs to move */
/* 注册输出模块 */
RegisterOutputPlugins();
}
...
/* if we're using the rules system, it gets initialized here */
if (snort_conf_file != NULL)
{
SnortConfig *sc;
/* initialize all the plugin modules */
/* 注册预处理模块*/
RegisterPreprocessors();
/* 注册规则解析相关模块*/
RegisterRuleOptions();
/* 解析配置函数，通过解析命令行获取配置文件snort.conf,再通过这个文件解析出所有配置*/
sc = ParseSnortConf();
/* Merge the command line and config file confs to take care of * command line overriding config file. * Set the global snort_conf that will be used during run time */
/* 合并命令行与配置文件中相关的配置，命令行的配置会覆盖配置文件中的配置 */
snort_conf = MergeSnortConfs(snort_cmd_line_conf, sc);
/* Handles Fatal Errors itself. */
/* 事件队列，这个队列中的节点会被输出日志模块使用*/
SnortEventqNew(snort_conf->event_queue_config, snort_conf->event_queue);
}
else if (ScPacketLogMode() || ScPacketDumpMode())
{
/* Make sure there is a log directory */
/* This will return the cmd line conf and resolve the output * configuration */
SnortConfig* sc = ParseSnortConf();
snort_conf = MergeSnortConfs(snort_cmd_line_conf, sc);
SnortEventqNew(snort_conf->event_queue_config, snort_conf->event_queue);
}
...
/* 解析规则，由于规则中会使用一些变量，所以解析规则在解析配置后面，保证规则的正确性*/
ParseRules(snort_conf);
...
fpCreateFastPacketDetection(snort_conf);
...
}
SnortConfig * ParseSnortConf(void)
{
/* 创建snort的配置对象， 所有的配置都保存在这个结构里面，所以非常庞大 */
SnortConfig *sc = SnortConfNew();\
...
/* 这里是模式匹配引擎的配置对象的创建，在FastPatternConfigNew函数中会调用fpSetDefaults设置默认值，默认使用 MPSE_AC_BNFA 算法*/
sc->fast_pattern_config = FastPatternConfigNew();
...
/* 通过变量parse_rules来判断，0：解析配置；1：解析规则 */
parse_rules = 0;
/* 这里是真正解析配置和规则文件的地方 */
if ( strcmp(file_name, NULL_CONF) ) ParseConfigFile(sc, sc->targeted_policies[policy_id], file_name);
}
ParseConfigFile函数的源码比较长，暂不贴出来。大概讲一下其逻辑。
1：打开文件，完整的读取一行。
2：调用mSplit对该行切分成两个元素
3：将切分好的第一个元素循环与snort_conf_keywords比较看是否有相关配置的解析函数，如果有，再判断parse_rules来决定是解析配置还是规则，最终会调用snort_conf_keywords[i].parse_func(sc, p, args)来解析相关配置。如果有特殊配置需要处理， 以此类推，进行处理
例如今天要介绍的模式匹配引擎的配置；假设其配置如下：
config detection: search-method ac-split search-optimize max-pattern-len 20
ParseConfigFile的执行流程如下：
- ParseConfigFile=》snort_conf_keywords[i].parse_func(sc, p, args)=》ParseConfig=》config_opts[i].parse_func(sc, opts)=》ConfigDetection 通过这一系列的调用模式匹配引擎的配置就算是解析完成了
ParseRules函数最终也是调用ParseConfigFile完成规则解析，部分源码如下：
void ParseRules(SnortConfig *sc) {
...
/* 设置标志：表明是解析规则*/
parse_rules = 1;
...
/* 真正去解析规则 */
ParseConfigFile(sc, sc->targeted_policies[policy_id], snort_conf_file);
...
/* Compile/Finish and Print the PortList Tables */ /* 为生成模式匹配引擎做准备，将规则进行去重等*/
PortTablesFinish(sc->port_tables, sc->fast_pattern_config);
...
}
fpCreateFastPacketDetection函数
根据前面的准备工作来创建模式匹配引擎；
主要工作：
1：将规则重新分类，从每条规则中选出一个最特殊的模式串出来，加入到模式匹配引擎中，然后生成模式匹配引擎，
2： 再将每条规则重新组织。在解析的时候，规则的匹配函数是以链表的形式组织，经过这个函数后变成了一棵树，这样做的优点是去重，节约内存。至此，模式匹配引擎的初始化完成。
3：然后通过SetPktProcessor函数设置各类数据包解码函数，
4：最终调用PacketLoop进行处理数据包
PacketLoop的处理流程
1：通过DAQ_Acquire从内核中获取数据包，
2：调用PacketCallback函数处理数据包，
3：调用ProcessPacket，在该函数中调用grinder进行解码，
4：然后调用Preprocess来调用预处理插件和模式匹配引擎匹配接口函数Detect，
5：然后依次调用fpEvalPacket=>fpEvalHeaderTcp=>fpEvalHeaderSW=>mpseSearch=>rule_tree_match=>detection_option_tree_evaluate=>detection_option_node_evaluate
这里只列出了tcp数据包的匹配过程，UDP与TCP一样。其中mpseSearch就是模式匹配引擎的匹配函数，而rule_tree_match则是匹配规则的入口函数
int SnortMain(int argc, char *argv[]) { ...
/* snort的初始化 包括预处理模块、模式匹配引擎、日志模块*/
SnortInit(argc, argv);
...
/* 设置数据包解码函数*/
SetPktProcessor();
...
/* 循环处理数据包：先从内核获取数据包、解码、预处理、利用模式匹配引擎检测攻击、产生日志、做出动过:alert 、drop、pass */
PacketLoop();
return 0;
}
static int SetPktProcessor(void)
{
const char* slink = NULL;
const char* extra = NULL;
int dlt = DAQ_GetBaseProtocol();
switch ( dlt )
{
case DLT_EN10MB:
slink = "Ethernet";
grinder = DecodeEthPkt;/* 此处为设置以太网的解码函数*/
break;
...
default:
/* oops, don't know how to handle this one */
FatalError("Cannot decode data link type %d\n", dlt);
break;
}
...
return 0;
}
void PacketLoop (void)
{
...
while ( !exit_logged )
{
/* 通过DAQ向内核获取数据包然后调用PacketCallback回调函数 */
error = DAQ_Acquire(pkts_to_read, PacketCallback, NULL);
...
}
...
}
static DAQ_Verdict PacketCallback(
void* user, const DAQ_PktHdr_t* pkthdr, const uint8_t* pkt)
{
...
/* 处理数据包*/
verdict = ProcessPacket(&p, pkthdr, pkt, NULL);
...
}
DAQ_Verdict ProcessPacket(
Packet* p, const DAQ_PktHdr_t* pkthdr, const uint8_t* pkt, void* ft)
{
...
/* 数据包解码*/
(*grinder) (p, pkthdr, pkt);
...
if ( !(p->packet_flags & PKT_IGNORE) )
{
/* 调用预处理模块和检测引擎（模式匹配引擎）*/
Preprocess(p);
/* 记录日志*/
log_func(p);
}
...
}
int Preprocess(Packet * p)
{
...
// If the packet has errors, we won't analyze it.
if ( p->error_flags )
{
...
}
else
{
...
if ( p->dsize )
{
while ((idx != NULL) && !(p->packet_flags & PKT_PASS_RULE))
{
if ( ((p->proto_bits & idx->proto_mask) || (idx->proto_mask == PROTO_BIT__ALL) ) && IsPreprocBitSet(p, idx->preproc_bit))
{
/* 调用预处理模块 */
idx->func(p, idx->context);
...
}
else
idx = idx->next;
}
}
...
if ((do_detect) && (p->bytes_to_inspect != -1))
{
/* Check if we are only inspecting a portion of this packet... */
if (p->bytes_to_inspect > 0)
{
DEBUG_WRAP(DebugMessage(DEBUG_DETECT, "Ignoring part of server " "traffic -- only looking at %d of %d bytes!!!\n", p->bytes_to_inspect, p->dsize););
p->dsize = (uint16_t)p->bytes_to_inspect;
}
/* 调用检测引擎*/
Detect(p);
}
else if (p->bytes_to_inspect == -1)
{
DEBUG_WRAP(DebugMessage(DEBUG_DETECT, "Ignoring server traffic!!!\n"););
}
}
...
}
int Detect(Packet * p)
{
...
detected = fpEvalPacket(p);
...
}
int fpEvalPacket(Packet *p)
{
...
switch(ip_proto)
{
case IPPROTO_TCP:
DEBUG_WRAP(DebugMessage(DEBUG_DETECT,
"Detecting on TcpList\n"););
if(p->tcph == NULL)
{
ip_proto = -1;
break;
}
return fpEvalHeaderTcp(p, omd);
default:
break;
}
/*
** No Match on TCP/UDP, Do IP
*/
return fpEvalHeaderIp(p, ip_proto, omd);
}
static inline int fpEvalHeaderTcp(Packet *p, OTNX_MATCH_DATA *omd)
{
...
if (dst != NULL)
{
if (fpEvalHeaderSW(dst, p, 1, 0, omd))
return 1;
}
...
}
static inline int fpEvalHeaderSW(PORT_GROUP *port_group, Packet *p,
int check_ports, char ip_rule, OTNX_MATCH_DATA *omd)
{
...
if (do_detect_content)
{
...
if (p->uri_count > 0)
{
...
if ((so != NULL) && (mpseGetPatternCount(so) > 0))
{
start_state = 0;
mpseSearch(so, UriBufs[i].uri, UriBufs[i].length,
rule_tree_match, omd, &start_state);
...
}
}
}
}
}
return 0;
}
- mpseSearch函数源码：此函数如果执行成功会调用rule_tree_match函数继续匹配规则，进行检测
int mpseSearch( void *pvoid, const unsigned char * T, int n, int ( *action )(void* id, void * tree, int index, void *data, void *neg_list), void * data, int* current_state )
{
...
switch( p->method )
{
/* 这里就是调用多模式匹配算法AC*/
case MPSE_AC_BNFA:
case MPSE_AC_BNFA_Q:
/* return is actually the state */
ret = bnfaSearch((bnfa_struct_t*) p->obj, (unsigned char *)T, n, action, data, 0 /* start-state */, current_state );
...
default: PREPROC_PROFILE_END(mpsePerfStats);
return 1;
}
}
static int rule_tree_match( void * id, void *tree, int index, void * data, void * neg_list)
{
...
rval = detection_option_tree_evaluate(root, &eval_data);
...
return 0;
}
- detection_option_tree_evaluate函数源码：
static int detection_option_tree_evaluate(detection_option_tree_root_t *root, detection_option_eval_data_t *eval_data)
{
...
/* 这里就是匹配规则树*/
for ( i = 0; i< root->num_children; i++)
{
/* New tree, reset doe_ptr for safety */
UpdateDoePtr(NULL, 0);
/* Increment number of events generated from that child */
/* 匹配规则树的节点*/
rval += detection_option_node_evaluate(root->children[i], eval_data);
}
...
}
- detection_option_node_evaluate函数源码：
int detection_option_node_evaluate(detection_option_tree_node_t *node, detection_option_eval_data_t *eval_data)
{
...
/* No, haven't evaluated this one before... Check it. */
do
{
switch (node->option_type)
{
...
case RULE_OPTION_TYPE_CONTENT:
if (node->evaluate)
{
/* This will be set in the fast pattern matcher if we found * a content and the rule option specifies not that * content. Essentially we've already evaluated this rule * option via the content option processing since only not * contents that are not relative in any way will have this * flag set */
if (dup_content_option_data.exception_flag)
{
if ((dup_content_option_data.last_check.ts.tv_sec == eval_data->p->pkth->ts.tv_sec) && (dup_content_option_data.last_check.ts.tv_usec == eval_data->p->pkth->ts.tv_usec) && (dup_content_option_data.last_check.packet_number == cur_eval_pkt_count) && (dup_content_option_data.last_check.rebuild_flag == (eval_data->p->packet_flags & PKT_REBUILT_STREAM)))
{
rval = DETECTION_OPTION_NO_MATCH; break;
}
}
/* 调用BM算法匹配规则的模式串 */
rval = node->evaluate(&dup_content_option_data, eval_data->p);
}
break;
case RULE_OPTION_TYPE_CONTENT_URI:
if (node->evaluate)
{
/* 调用BM算法匹配规则的模式串 */
rval = node->evaluate(&dup_content_option_data, eval_data->p);
}
break;
...
}
}
return result;
}
本博客是涉及到模式匹配引擎的初始化和匹配过程，并未讨论其中的算法实现。
可以参考 https://github.com/testwill/Multi-pattern-matching-engine ， 有snort的ac实现。
