spp_defrag.c

该软件是一个有名的基于网络的入侵检测系统

/*
 * spp_defrag v1.0b20 - 19 Sep 2000
 * 
 * Purpose: IP defragmentation preprocessor
 * Author:  Dragos Ruiu ([e-mail]/[e-mail])
 * Acknowledgements:    Code skeleton from [e-mail]
 *			There's a good paper about splay trees
 *			by the developer and they rock.
 *			Marty Roesch([e-mail])
 *			and Ron Gula([e-mail])
 *			helped and did something few in the security
 *			community do, shared knowledge.  Thanks.
 *
 * notes:
 *		This defragger implementation differs from the usual
 *		hash table and linked list technique in that it uses
 *		self caching splay trees. My hypothesis is that this
 *		provides substantial performance improvements.  I
 *		hope this module will be able to demonstrate or debunk
 *		this hypothesis. 
 * 
 * Splay Tree:
 * `A self-organizing data structure which uses rotations to move an
 *  accessed key to the root. This leaves recently accessed nodes near
 *  the top of the tree, making them very quickly searchable (Skiena 1997, p. 177). 
 * 
 * All splay tree operations run in O(log n) time _on_average_, where n is the
 * number of items in the tree, assuming you start with an empty tree.  Any single
 * operation can take Theta(n) time in the worst-case, but operations slower than
 * O(log n) time happen rarely enough that they don't affect the average.
 * 
 * Although 2-3-4 trees make a stronger guarantee (_every_ operation on a 2-3-4
 * tree takes O(log n) time), splay trees have several advantages.  Splay trees
 * are simpler and easier to program, and they can take advantage of circumstances
 * in which lots of find operations occur on a small number of items.  Because of
 * their simplicity, splay tree insertions and deletions are typically faster in
 * practice (sometimes by a constant factor, sometimes asymptotically).  Find
 * operations can be faster or slower, depending on circumstances.  Splay trees
 * really excel in applications where a fraction of the items are the targets of
 * most of the find operations, because they're designed to give especially fast
 * access to items that have been accessed recently.
 *
 * a good reference on splay trees is:
 * http://www.cs.umbc.edu/courses/undergraduate/341/fall98/frey/ClassNotes/Class17/splay.html
 * 
 * References 
 * Skiena, S. S. The Algorithm Design Manual. New York: Springer-Verlag, pp. 177 and 179, 1997. 
 * Sleator, D. and Tarjan, R. "Self-Adjusting Binary Search Trees." J. ACM 32, 652-686, 1985. 
 * Tarjan, R. Data Structures and Network Algorithms. Philadelphia, PA: SIAM Press, 1983. 
 * Wood, D. Data Structures, Algorithms, and Performance. Reading, MA: Addison-Wesley, 1993. 
 * 
 */


#include <pcap.h>
#include "decode.h"

/* Warning these are only valid for IPv4
   also note that these are still 
   in raw network order (see htons)  
   and these may fail on 64 bit machines 
*/
#define ID(x)		((unsigned short*)((char*)x->iph+4))
#define PROTO(x)	*((char*)x->iph+9)
#define SADDR(x)        *((unsigned int*)((char*)x->iph+12))
#define DADDR(x)        *((unsigned int*)((char*)x->iph+16))
#define	DATA(x)		((char*)x->iph+20)

/* Uh-oh hope this wierdness is right :-) */
#define FOFF(x)		(int)((x->frag_offset)<<3)
#define DF(x)		(x->df)
#define MF(x)		(x->mf)


/* fragment ID structure  */
typedef Packet *frag;

typedef struct tree_node Tree;
struct tree_node {
    Tree * left, * right;
    frag key;
    int size;   /* maintained to be the number of nodes rooted here */
};

Tree *froot;


/*  These next declarations are for the fragment timeout and 
    and cleanup/sweeping process... time math routines are from
    an obscure piece of old code for a defunct video camera product
*/

#define FRAGTIMEOUTSEC	10	/* 10 seconds let's play safe for now */
#define FRAGTIMEOUTUSEC	0	/* 0 micro seconds		      */
#define FASTSWEEPLIM	16000000	/* memory use threhold for fast sweep */

long int fragmemuse;
int fragsweep;  /* the packet timeout / garbage collection stuff  */

typedef struct _timestruct
{
        u_int32_t tv_sec;
        u_int32_t tv_usec;
} time_struct;

time_struct fragtimeout;
 


/******Timestamp Routines******/

#define TIME_LT(x,y) (x tv_sec<y tv_sec||(x tv_sec==y tv_sec&&x tv_usec<y tv_usec))

void addtime(time_struct *op1, time_struct *op2, time_struct *result)
{
    result->tv_usec = op1->tv_usec+op2->tv_usec;
    if (result->tv_usec > 999999)
    {
        result->tv_usec -= 1000000;
        op1->tv_sec++;
     }
     result->tv_sec = op1->tv_sec+op2->tv_sec;
}



/******Splay Tree Stuff******/

/* Function: fragcompare(i,j)				    */
/* This is the splay tree comparison.                       */
/* Returns 1 if i>j; 0 if i=j; -1 if i<j;                   */

int fragcompare(i,j)
frag i,j;
{
	if(!j)
	{
		if(!i)
			return(0);
		else
			return(1);
	} else {
		 if(!i)
			return(-1);
	}
             if( SADDR(i) > SADDR(j) )
                 { return (1); }
        else if( SADDR(i) < SADDR(j) )
                 { return (-1); }
        else if( DADDR(i) > DADDR(j) )
                 { return (1); }
        else if( DADDR(i) < DADDR(j) )
                 { return (-1); }
        else if( PROTO(i) > PROTO(j) )
                 { return (1); }
        else if( PROTO(i) < PROTO(j) )
                 { return (-1); }
        else if( ID(i) > ID(j) )
                 { return (1); }
        else if( ID(i) < ID(j) )
                 { return (-1); }
	else if( FOFF(i) > FOFF(j) )
		 { return (1); }
	else if( FOFF(i) < FOFF(j) )
		 { return (-1); }
	else if( i->dsize > j->dsize )
		 { return (1); }
	else if( i->dsize < j->dsize )
		 { return (-1); }
	return (0);
}
 
/* This macro returns the size of a node.  Unlike "x->size",     */
/* it works even if x=NULL.  The test could be avoided by using  */
/* a special version of NULL which was a real node with size 0.  */

#define node_size(x) ((!x) ? 0 : ((x)->size))
 
/* Function: fragsplay(i, t)					*/
/* Splay using the key i (which may or may not be in the tree.) */
/* The starting root is t, size fields are maintained		*/

Tree *fragsplay(frag i, Tree *t) 
{
    Tree N, *l, *r, *y;
    int comp, root_size, l_size, r_size;
    if(!t) return t;
    N.left = N.right = NULL;
    l = r = &N;
    root_size = node_size(t);
    l_size = r_size = 0;
 
    for (;;) {
        comp = fragcompare(i, t->key);
        if(comp < 0) {
            if(!t->left) break;
            if(fragcompare(i, t->left->key) < 0) {
                y = t->left;                           /* rotate right */
                t->left = y->right;
                y->right = t;
                t->size = node_size(t->left) + node_size(t->right) + 1;
                t = y;
                if(!t->left) break;
            }
            r->left = t;                               /* link right */
            r = t;
            t = t->left;
            r_size += 1+node_size(r->right);
        } else if (comp > 0) {
            if(!t->right) break;
            if(fragcompare(i, t->right->key) > 0) {
                y = t->right;                          /* rotate left */
                t->right = y->left;
                y->left = t;
		t->size = node_size(t->left) + node_size(t->right) + 1;
                t = y;
                if(!t->right) break;
            }
            l->right = t;                              /* link left */
            l = t;
            t = t->right;
            l_size += 1+node_size(l->left);
        } else {
            break;
        }
    }
    l_size += node_size(t->left);  /* Now l_size and r_size are the sizes of */
    r_size += node_size(t->right); /* the left and right trees we just built.*/
    t->size = l_size + r_size + 1;

    l->right = r->left = NULL;

    /* The following two loops correct the size fields of the right path  */
    /* from the left child of the root and the right path from the left   */
    /* child of the root.                                                 */
    for(y = N.right; y; y = y->right) {
        y->size = l_size;
        l_size -= 1+node_size(y->left);
    }
    for(y = N.left; y; y = y->left) {
        y->size = r_size;
        r_size -= 1+node_size(y->right);
    }
 
    l->right = t->left;                                /* assemble */
    r->left = t->right;
    t->left = N.right;
    t->right = N.left;

    return t;
}

/* Function: Tree * fraginsert(frag i, Tree * t) 		*/
/* Insert frag i into the tree t, if it is not already there. 	*/
/* Return a pointer to the resulting tree.                   	*/

Tree *fraginsert(frag i, Tree * t) {
    Tree * new;
    if(t) {
	t = fragsplay(i,t);
	if (fragcompare(i, t->key)==0) {
	    return t;  /* it's already there */
	}
    }
    new = (Tree *) malloc (sizeof (Tree));
    if(!new) { ErrorMessage("Ran out of space\n"); return(t);}
    if(!t) {
	new->left = new->right = NULL;
    } else if(fragcompare(i, t->key) < 0) {
	new->left = t->left;
	new->right = t;
	t->left = NULL;
	t->size = 1+node_size(t->right);
    } else {
	new->right = t->right;
	new->left = t;
	t->right = NULL;
	t->size = 1+node_size(t->left);
    }
    new->key = i;
    new->size = 1 + node_size(new->left) + node_size(new->right);
    return new;
}

/* Function: Tree * fragdelete(frag i, Tree *t) 	*/
/* Deletes i from the tree if it's there.               */
/* Return a pointer to the resulting tree.              */

Tree *fragdelete(frag i, Tree *t) {
    Tree * x;
    int tsize;

    if (!t) return NULL;
    tsize = t->size;
    t = fragsplay(i,t);
    if(fragcompare(i, t->key) == 0) {               /* found it */
	if(!t->left) {
	    x = t->right;
	} else {
	    x = fragsplay(i, t->left);
	    x->right = t->right;
	}
	
	free(t);
	if(x) {
	    x->size = tsize-1;
	}
	return x;
    } else {
	return t;                         /* It wasn't there */
    }
}

/* Function: Tree *fragfind_rank(int r, Tree *t)		   */ 
/* Returns a pointer to the node in the tree with the given rank.  */
/* Returns NULL if there is no such node.                          */
/* Does not change the tree.  To guarantee logarithmic behavior,   */
/* the node found here should be splayed to the root.              */

Tree *fragfind_rank(int r, Tree *t) {