spp_defrag.c

该源码是用C语言编写的,实现网络入侵检测系统的功能

/*
** Copyright (C) 1998,1999,2000,2001 Martin Roesch <[e-mail]>
** Copyright (C) 2000,2001 Dragos Ruiu <[e-mail]/[e-mail]>
**
** This program is free software; you can redistribute it and/or modify
** it under the terms of the GNU General Public License as published by
** the Free Software Foundation; either version 2 of the License, or
** (at your option) any later version.
**
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
** GNU General Public License for more details.
**
** You should have received a copy of the GNU General Public License
** along with this program; if not, write to the Free Software
** Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
*/
/*
 * spp_defrag v1.0b24 - 9 Nov 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)       *((u_int16_t *)((u_int8_t *)x->iph+4))
#define PROTO(x)    *((u_int8_t *)x->iph+9)
#define SADDR(x)    *((u_int32_t *)((u_int8_t *)x->iph+12))
#define DADDR(x)    *((u_int32_t *)((u_int8_t *)x->iph+16))
#define DATA(x)     ((u_int8_t *)x->iph+20)

/* Uh-oh hope this wierdness is right :-) */
#define FOFF(x)     (u_int32_t)((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;

u_int32_t mem_locked;
u_int32_t mem_freed;


/*  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;
time_struct last_frag_time;



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

#define TIME_LT(x,y) (x tv_sec<(unsigned long)y tv_sec||(x tv_sec==(unsigned long)y tv_sec&&x tv_usec<(unsigned long)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_tree_node;
    if(t)
    {
        t = fragsplay(i,t);
        if(fragcompare(i, t->key)==0)
        {
            return t;  /* it's already there */
        }
    }

    new_tree_node = (Tree *) malloc (sizeof (Tree));
    fragmemuse += sizeof(Tree);
#ifdef DEBUG
    fprintf(stderr, "+++++++++++++++++++++++++\n");
    fprintf(stderr, "%p + Tree Alloc\n", new_tree_node);
    fprintf(stderr, "+++++++++++++++++++++++++\n");
    fflush(stderr);
    mem_locked += sizeof(Tree);
#endif

    if(!new_tree_node)
    {
        ErrorMessage("Ran out of space\n");
        return(t);
    }
    if(!t)
    {
        new_tree_node->left = new_tree_node->right = NULL;
    }
    else
        if(fragcompare(i, t->key) < 0)
    {