match_str.c

Firestorm NIDS是一个性能非常高的网络入侵检测系统 (NIDS)。目前

/*
 * This file is part of firestorm NIDS
 * Copyright (c) 2002 Gianni Tedesco
 * Copyright (C) 1998-2002 Martin Roesch <[e-mail]>
 *
 * This code was originally taken from snort, but nearly all of that
 * has gone apart from the boyer moore inner loop. I have removed the
 * delta2 heuristic to keep O(1) memory complexity without really
 * sacrificing performance. Original snort copyright notice is
 * reproduced above anyway.
 *
 * Code could be improved by reversing compare order and combining with
 * Knuth-Morris-Pratt heuristic.
 *
 * Knuth also postulated that this code could be improved by using a
 * larger alphabet with characters >255 representing sequences of
 * characters.
 */

#include <stdlib.h>
#include <stdio.h>
#include <errno.h>
#include <string.h>
#include <ctype.h>
#include <netinet/in.h>

#include <firestorm.h>
#include <packet.h>
#include <alert.h>
#include <signature.h>
#include <decode.h>
#include <matcher.h>
#include <plugin.h>

PLUGIN_STD_DEFS();

struct proto *http_proto=NULL;
proc_decode_proto decode_proto;

struct content_priv {
	char 		*string;
	unsigned int	len;

	unsigned int	depth;
	unsigned int	offset;

	u_int8_t 	flag_depth;
	u_int8_t	flag_uri;

	/* Boyer moore skip/shift tables */
	int		skip[256];
#if 0
	int		*shift;
#endif
};

int str_compare(void *p1, void *p2)
{
	struct content_priv *s1=(struct content_priv *)p1;
	struct content_priv *s2=(struct content_priv *)p2;

	if ( s1->flag_depth==0 && s2->flag_depth==0 &&
		s1->depth!=s2->depth ) return 1;
	if ( s1->len==s2->len &&
		s1->flag_depth==s2->flag_depth &&
		s1->offset==s2->offset &&
		s1->depth==s2->depth &&
		s1->flag_uri==s2->flag_uri &&
		( memcmp(s1->string, s2->string, s1->len)==0 ) ) return 0;
	return 1;
}

/* Build delta1 (skip table) - alphabet sized lookup table for boyer-moore */
void bm_skip(char *x, int plen, int *skip)
{
	int *sptr = &skip[256];

	while( sptr-- != skip )
		*sptr=plen+1;

	while(plen != 0)
		skip[(unsigned char)*x++] = plen--;
}

/* Build a knuth-morris-pratt state transition table */
void kmp_next(char *pat, int M, int *next)
{
	int k=0;
	int j=-1;

	next[0]=-1;
	while (k+1 < M) {
		while( (j >= 0) && (pat[j] != pat[k]) )
			j = next[j];
		k++;
		j++;
		next[k] = (pat[k]==pat[j]) ? next[j] : j;
	}
}

int str_match_regex(struct packet *p, void *priv, unsigned int l, int n)
{
	struct content_priv *sp=priv;
	int skip_stride,shift_stride, p_idx;
	unsigned int hlen;
	unsigned int dsize;
	int literal=0;
	int regexcomp=0;
	char *hs;
	int b_idx;

	l++; /* ignore IP */
	if ( p->layer[l+1].proto ) l++; /* ignore transport layer header */
	if ( l>=p->llen ) return n^0;

	if ( http_proto && sp->flag_uri ) {
		struct http_session *h;

		if ( p->layer[l].proto!=http_proto )
			return n^0;

		if ( !(h=p->layer[l].session) ) return n^0;
		if ( !(dsize=h->uri_len) ) return n^0;
		if ( !(hs=h->uri) ) return n^0;
		if ( sp->len+sp->offset > dsize ) return n^0;

		hs+=sp->offset;
		if ( sp->flag_depth && (sp->depth < (dsize-sp->offset)) ) {
			hlen=sp->depth;
		}else{
			hlen=(dsize-sp->offset);
		}
	}else{
		/* Find size of searchable area */
		if ( !(dsize=p->end-p->layer[l].h.raw) ) return n^0;
		if ( sp->flag_depth && sp->depth<dsize ) dsize=sp->depth;

		/* Make sure packet is big enough */
		if ( sp->len+sp->offset > dsize ) return n^0;

		/* Find start of haystack */
		hs=p->layer[l].h.raw+sp->offset;

		/* Find size of haystack */
		hlen=dsize-sp->offset;
	}

	/* Do the search */
	b_idx=sp->len;
	while(b_idx <= hlen ) {
		p_idx=sp->len;

		while(hs[--b_idx]==sp->string[--p_idx]
			|| (sp->string[p_idx]=='?' && !literal)
			|| (sp->string[p_idx]=='*' && !literal)
			|| (sp->string[p_idx]=='\\' && !literal) ) {

			if ( literal )
				literal=0;

			if ( !literal && sp->string[p_idx]=='\\' )
				literal=1;

			if ( sp->string[p_idx]=='*' ) {
				while(p_idx!=0 && sp->string[--p_idx]=='*');

				while(hs[--b_idx]!=sp->string[p_idx]) {
					regexcomp++;
					if ( b_idx==0 ) return n^0;
				}
			}

			if (p_idx==0) return n^1;
			if (b_idx==0) break;
		}

		skip_stride=sp->skip[(unsigned char)hs[b_idx]];
		shift_stride=(sp->len-p_idx)+1;

		/* micro-optimised max() function */
		b_idx += ( (skip_stride-shift_stride)>0 )
			? skip_stride : shift_stride;
		b_idx += regexcomp;
		regexcomp=0;
	}

	return n^0;
}

int str_match(struct packet *p, void *priv, unsigned int l, int n)
{
	struct content_priv *sp=priv;
	int skip_stride,shift_stride, p_idx;
	unsigned int hlen;
	unsigned int dsize;
	char *hs;
	int b_idx;

	l+=2; /* ignore IP and TCP/UDP/ICMP/whatever */
	if ( l>=p->llen ) return n^0;

	if ( http_proto && sp->flag_uri ) {
		struct http_session *h;

		if ( p->layer[l].proto!=http_proto )
			return n^0;

		if ( !(h=p->layer[l].session) ) return n^0;
		if ( !(dsize=h->uri_len) ) return n^0;
		if ( !(hs=h->uri) ) return n^0;
		if ( sp->len+sp->offset > dsize ) return n^0;

		hs+=sp->offset;
		if ( sp->flag_depth && (sp->depth < (dsize-sp->offset)) ) {
			hlen=sp->depth;
		}else{
			hlen=(dsize-sp->offset);
		}
	}else{
		/* Find size of searchable area */
		if ( !(dsize=p->end-p->layer[l].h.raw) ) return n^0;
		if ( sp->flag_depth && sp->depth<dsize ) dsize=sp->depth;

		/* Make sure packet is big enough */
		if ( sp->len+sp->offset > dsize ) return n^0;

		/* Find start of haystack */
		hs=p->layer[l].h.raw+sp->offset;

		/* Find size of haystack */
		hlen=dsize-sp->offset;
	}

	/* Do the search */
	b_idx=sp->len;
	while(b_idx <= hlen) {
		p_idx=sp->len;

		while((unsigned char)hs[--b_idx]==
			(unsigned char)sp->string[--p_idx]) {
			if (b_idx<0) return n^0;
			if (p_idx==0) return n^1;
		}

		skip_stride=sp->skip[(unsigned char)hs[b_idx]];
		shift_stride=(sp->len-p_idx)+1;

		/* micro-optimised max() function */
		b_idx += ( (skip_stride-shift_stride)>0 )
			? skip_stride : shift_stride;
	}

	return n^0;
}

int str_match_nocase(struct packet *p, void *priv, unsigned int l, int n)
{
	struct content_priv *sp=priv;
	int skip_stride,shift_stride, p_idx;
	unsigned int hlen;
	unsigned int dsize;
	char *hs;
	int b_idx;

	l++; /* ignore IP */
	if ( p->layer[l+1].proto ) l++; /* ignore transport layer header */
	if ( l>=p->llen ) return n^0;

	if ( http_proto && sp->flag_uri ) {
		struct http_session *h;

		if ( p->layer[l].proto!=http_proto )
			return n^0;

		if ( !(h=p->layer[l].session) ) return n^0;
		if ( !(dsize=h->uri_len) ) return n^0;
		if ( !(hs=h->uri) ) return n^0;
		if ( sp->len+sp->offset > dsize ) return n^0;

		hs+=sp->offset;
		if ( sp->flag_depth && (sp->depth < (dsize-sp->offset)) ) {
			hlen=sp->depth;
		}else{
			hlen=(dsize-sp->offset);
		}
	}else{
		/* Find size of searchable area */
		if ( !(dsize=p->end-p->layer[l].h.raw) ) return n^0;
		if ( sp->flag_depth && sp->depth<dsize ) dsize=sp->depth;

		/* Make sure packet is big enough */
		if ( sp->len+sp->offset > dsize ) return n^0;

		/* Find start of haystack */
		hs=p->layer[l].h.raw+sp->offset;

		/* Find size of haystack */
		hlen=dsize-sp->offset;
	}

	/* Do the search */
	b_idx=sp->len;
	while(b_idx <= hlen ) {
		p_idx=sp->len;

		while(toupper((unsigned char)hs[--b_idx])==
			(unsigned char)sp->string[--p_idx]) {
			if (b_idx<0) return n^0;
			if (p_idx==0) return n^1;
		}

		skip_stride=sp->skip[toupper((unsigned char)hs[b_idx])];
		shift_stride=(sp->len-p_idx)+1;

		/* micro-optimised max() function */
		b_idx += ( (skip_stride-shift_stride)>0 )
			? skip_stride : shift_stride;
	}

	return n^0;
}

int hextouint(char *s, unsigned int *v)
{
	unsigned int d;
	int p=0;

	for(*v=0; ; p++) {
		if ( (d=(unsigned int)(*s - '0'))>=10 &&
			(d=((unsigned int)(tolower(*s) - 'a')+10))>=16) break;
		*v=*v*16+d;
		s++;
	}

	if ( p==0 ) return -1;
	if ( *s==0 ) return 0;
	return p;
}

proc_match_match str_validate(char *args, void **priv,
	struct criteria *m, u_int32_t *c, int mode)
{
	char *t;
	int state=0;
	char bin[3]={0,0,0};
	unsigned int i=0, j=0;
	struct content_priv *p;
	struct criteria *mod;
	proc_match_match mfunc=str_match;
	int escaped=0;

	if ( !args )
		return NULL;

	/* zero length string is pointless */
	if ( !(j=strlen(args)) )
		return NULL;

	/* We can survive without this */
	if ( !http_proto )
		http_proto=decode_proto("http");

	if ( !(p=calloc(1, sizeof(*p))) )
		return NULL;

	for(mod=m; mod; mod=mod->next) {
		if ( !strcmp("depth", mod->crit) ) {
			if ( strtouint(mod->args, &p->depth) ) {
				free(p);
				return NULL;
			}
			p->flag_depth=1;
		}else if ( !strcmp("offset", mod->crit) ) {
			if ( strtouint(mod->args, &p->offset) ) {
				free(p);
				return NULL;
			}
		}else if ( !strcmp("regex", mod->crit) ) {
			if ( mfunc==str_match_nocase ) {
				mesg(M_ERR,"match_str: nocase and "
					"regex mutually exclusive.");
				free(p);
				return NULL;
			}
			mfunc=str_match_regex;
		}else if ( !strcmp("nocase", mod->crit) ) {
			if ( mfunc==str_match_regex ) {
				mesg(M_ERR,"match_str: nocase and "
					"regex mutually exclusive.");
				free(p);
				return NULL;
			}
			mfunc=str_match_nocase;
		}
	}

	p->flag_uri=mode;

	/* Finished strings can be no bigger than this */
	if ( !(p->string=malloc(j)) ) {
		free(p);
		return NULL;
	}

	for(p->len=j,t=args,j=0; *t; t++) {
		if ( state==0 ) { /* Normal string */
			if ( !escaped && *t=='\\' ) {
				escaped=1;
			}else if ( !escaped && *t=='|' ) {
				state=1;
			}else{
				escaped=0;
				if ( mfunc==str_match_nocase ) {
					p->string[j++]=toupper(
						(unsigned char)*t);
				}else{
					p->string[j++]=*t;
				}
			}
		}else if ( state==1 ) { /* Binary data */
			if ( *t=='|' ) {
				state=0;
				continue;
			}

			if ( *t==' ' || *t=='\t' ) {
				continue;
			}

			bin[i++]=*t;

			if ( i==2 ) {
				unsigned int num;
				char thisbyte;
				i=0;

				if ( hextouint(bin, &num) ) {
					mesg(M_ERR,"match_str: bogus hex char");
					free(p->string);
					free(p);
					return NULL;
				}

				/* Impossible to be too big cos
				 * 16^2 = 0xff */
				thisbyte=(char)num&0xff;

				if ( mfunc==str_match_nocase ) {
					p->string[j++]=toupper(
						(unsigned char)thisbyte);
				}else{
					p->string[j++]=thisbyte;
				}
			}
		}
	}

	if ( i ) {
		mesg(M_ERR,"match_str: string is n and a half bytes!");
		free(p->string);
		free(p);
		return NULL;
	}

	/* Shrink the string if there was any
	 * binary data inside of it */
	if ( j!=p->len ) {
		realloc(p->string, j); /* can only be smaller */
		p->len=j;
	}

	/* Length can't be bigger than depth */
	if ( p->flag_depth && p->len > p->depth ) {
		mesg(M_ERR, "match_str: len(%u) > depth(%u)", p->len, p->depth);
		free(p->string);
		free(p);
		return NULL;
	}

	/* Perform boyer-moore preprocessing */
	bm_skip(p->string, p->len, p->skip);
#if 0
	if ( !(p->shift=(int *)calloc(sizeof(int), p->len)) ) {
		free(p->string);
		free(p);
		return NULL;
	}
	bm_shift(p->string, p->len, p->shift);
#endif

	/* heuristic to prefer larger strings */
	if ( p->len<1000 && mfunc!=str_match_regex )
		*c-=2*p->len;

	*priv=p;
	return mfunc;
}

proc_match_match content_validate(char *args, void **priv,
	struct criteria *m, u_int32_t *c)
{
	return str_validate(args, priv, m, c, 0);
}
proc_match_match uricontent_validate(char *args, void **priv,
	struct criteria *m, u_int32_t *c)
{
	return str_validate(args, priv, m, c, 1);
}

void str_cleanup(void *priv) {
	struct content_priv *p=priv;

	if ( p ) {
		if ( p->string ) free(p->string);
		free(p);
	}
}

struct matcher str_matchers[]={
	matcher_init("content", MCOST_DATA+1000, content_validate, str_compare, str_cleanup),
	matcher_init("uricontent", MCOST_DATA+1000, uricontent_validate, str_compare, str_cleanup),
	matcher_null()
};

int PLUGIN_MATCHER (struct matcher_api *m)
{
	object_check(m);

	if ( !m->matcher_add(str_matchers) )
		return PLUGIN_ERR_FAIL;

	return PLUGIN_ERR_OK;
}

int PLUGIN_INIT (struct plugin_in *in, struct plugin_out *out)
{
	plugin_check(in, out);

	PLUGIN_ID("match.str", "String matching routines");
	PLUGIN_VERSION(2, 0);
	PLUGIN_AUTHOR("Gianni Tedesco", "[e-mail]");
	PLUGIN_LICENSE("GPL");

	if ( !(decode_proto=in->import("decode.proto")) ) {
		return PLUGIN_ERR_OBJECT;
	}

	return PLUGIN_ERR_OK;
}

int PLUGIN_UNLOAD (int code) {
	return PLUGIN_ERR_OK;
}