sfportobject.c

著名的入侵检测系统snort的最新版本的源码

/****************************************************************************
 *
 * Copyright (C) 2005-2007 Sourcefire, Inc.
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License Version 2 as
 * published by the Free Software Foundation.  You may not use, modify or
 * distribute this program under any other version of the GNU General
 * Public License.
 *
 * 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.
 *
 ****************************************************************************/

/*
   sfportobject.c
   
   author:	marc norton
   date:	11/05/2005

   description: 
   
   Port objects provides support for generic ports lists comprised of 
   individual ports, port ranges, and negation of ports and port ranges.
   
   Port lists require a somewhat more complex scheme to determine the proper
   grouping of rules for each port while minimizing the number of rule groups 
   created. We can use a single group of rules in the multi-pattern detection phase,
   however that can have a huge impact on performance.  Instead we try to create 
   a smaller grouping of rules that might be applicable to each port.
   
   As rules are defined using port ranges, and port lists there will be port
   overlapps between rules. This requires us to determine whether we should
   create one larger rule group to apply to all relevant ports, or to 
   create multiple rule groups and apply the smallest applicable one to 
   each port. In practice snort has some rules which span almost all 64K ports
   which might cause all rules in all port-rule groups to be merged into one set
   unless we apply a more complex logic than simply merging rule-port groups
   with common ports.  This is the problem addressed by the sfportobject
   module.
  
   port list examples of acceptable usage:

   - var has been overloaded, if it includes _port we add as a port-object also.
   var http_ports 80
   var http_range_ports 80:81 
   var http_list_ports  [ 80 8080 8138 ]
   
   - portvar has been added to indicate portvariables, this form does not require _port
   portvar http 80
   portvar http_range 80:81
   portvar http_list  [ 80 8080 8138 ]
   
   80
   $http
   !90
   80:81
   $http_range
   !90:91
   [ 80 8080 8138 ]
   $http_list
   [ $http  $http_list ]
   [ 2001 2008 20022 8100:8150 !8121 !8123 ]
   [ !any ] - uhhh, why do people ask about this ?
  
   Rules are defined using a port, a port-range or a list of these, we call these port objects. 
   As rules are loaded we generate some large rule counts on some ports, and
   small rule counts on most ports.  If for each port you build a list of 
   rules on that port, we may end up with some ports with a large rule set that
   differs by the addition of a few rules on each port (relative to the group sizes) 
   we don't want to generate compeletely different rule groups for these as that 
   would than generate multiple large state machines for the multi-pattern matching 
   phase of the detection engine which in turn could use a lot of memory.

   It turns out that one scheme, the one used herein, provides some blending
   of rule groups to minimize memory, and tries to minimize large group sizes
   to keep performance more optimal - although this is at the expense of memory.
  
   --- Port varaibles
   Var - has been overloaded. If it's name includes _port as part of the var name it is 
   added to the PortVarTable.  
   PortVar - has been added. These are always added to the PortVarTable.
  
   --- Loading Port lists and rules
   PortTables - we support src and dst tables for tcp/udp/icmp/ip/arp rules. 
   PortVar References - we dup the PortVar entries as needed into each table if referenced,
   so HTTP_PORTS for tcp and udp contain different rules.  If a rule references a PortVar
   we look it up in the table, if its not present we dup it from the PortVarTable, otherwise
   we just add the rule index to the PortVar HTTP_PORTS in the proper table. If a PortVar 
   is not used to specify a Port entry in a rule we create a temp port-object, and check if 
   it's port-list is already in the table. If it's not we make the temp port-object the 
   permanent entry in the  table. If it is, we just add the rule index to the existing entry, 
   and delete the temp port-object. When the rules are done loading we should have a set of 
   port-objects with port-lists that differ by at least one port.  The next step handles the 
   cases where we have multiple port-objects with at least one common port.
   
   --- Merging Ports and Rules
   We maintain for each port a list of port objects and their rules that apply 
   to it. This allows us to view combining the rules associated with each port
   object using a few heuristics. A list of port objects applicable to each port 
   presents rules in one of four catagories:

   1) a single port object, and all rules associated with it.
   2) multile port objects each with a small set of rules assoicated with it.
   3) one port object with a large rule set, and one or more port objects  
      with a small set of rules assoicated with each.
   4) multiple port objects with large rule sets, and zero or more port objects 
      each with a small set of rules assoicated with it.

    We process these four categories as follows:

    1) -a single port object (large or small)
		do nothing, each port referncing this port object is complete.
    2) -multiple small port objects
		merge the rules for all port objects into one virtual object,  
	   for each port in this category lookup it's combined port object
	   to see if it's already defined, if not create one.  This way
	   all ports that have the same port groups point to the same virtual 
	   port object.   
	3) -one large port object, and one or more small port objects
		add the small rule groups into the large rule set, using the existing 
	   port object.
	4) -multiple large port objects and zero or more small port objects
		merge the large port objects into a virtual port object and 
	   add all rules from both large and small sets into it's rule set.
	   we use the combined large group ports to form a key, so any ports 
	   referencing just these large rule groups, and some small ones
	   will be recognized as the same.  This handles cases where we have
	   2,3,4.etc large rule groups combined.  Any time we see a 'n' grouping 
	   of the same large rule sets we'll look it up and point to it for that 
	   port.

    To determine when a port object has a large rule set or a small one we use 
	a simple threshold value. In theory the larger this value is the more 
	merging of rules in category 2 and 3 will occur. When this value is 
	small category 4 should become a more prevalent situation.  However,
	the behavior of groupings for a given threshold can change as more rules
	are added to port groups.  Therefore generous statistics are printed after
	the rules and port objects are compiled into their final groupings.
    

  Procedure for using PortLists

  1) Process Var's as PortVar's and standard Var's (for now). This allows
  existing snort features to work, with the Var's.  Add in the PortVar support
  to parse the Var input into PortObjects, and add these to the PortVartable.

  2) Read Rules
	a) Read port numbers and lists
		1) Dereference PortVar/Var Names if any are referenced.
	b) Create a Port Object
	c) Test if this Port object exists already, 
		1) If so, add the sid to it.
		2) If not add it ....
	 


  Notes:

	All any-any port rules are managed separately, and added in to the final 
	rules lists of each port group after this analysis. Rules defined with
	ranges are no longer considered any-any rules for the purpose of organizing
	port-rule groupings.  This should help prevent some cross fertilization of
	rule groups with rules that are unneccessary, this causes rule group 
	sizes to bloat and performance to slow.

  Hierarchy:

	PortTable -> PortObject's 

	PortVar -> PortObject ( These are pure, and are dup'ed for use in the PortTables )

	PortObject -> PortObjectItems (port or port range)
	
*/


#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <ctype.h>

#include "debug.h"
#include "sfportobject.h"
#include "sfrim.h"
#include "util.h"

#define PO_EXTRA_RULE_CNT 25
#define PTBL_LRC_DEFAULT 10
#define PO_INIT_ID 1000000
#define PO_HASH_TBL_ROWS 10000

/*
   PORT OBJECT FUNCTIONS
*/

/*
    Create a new PortObject
*/
PortObject * PortObjectNew(void)
{
    PortObject *po = (PortObject *)SnortAlloc(sizeof(PortObject));

    po->item_list =(SF_LIST*) sflist_new();

    if( !po->item_list )
    {
        free( po );
        return 0;
    }
    
    po->rule_list =(SF_LIST*) sflist_new();

    if( !po->rule_list )
    {
        sflist_free( po->item_list );
        free( po );
        return 0;
    }
    
    return po;    
}
/*
    Create a new PortObject2
*/
PortObject2 * PortObjectNew2(int nrules)
{
    PortObject2 *po = (PortObject2 *)SnortAlloc(sizeof(PortObject2));

    po->item_list =(SF_LIST*) sflist_new();

    if( !po->item_list )
    {
        free( po );
        return 0;
    }
    
    po->rule_hash =(SFGHASH*) sfghash_new(nrules,sizeof(int),0,free /* frees data - should be rule id ptrs == (int*) */); 
    if( !po->rule_hash )
    {
        sflist_free( po->item_list );
        free( po );
        return 0;
    }

    //sfhashfcn_static( po->rule_hash->sfhashfcn ); /* TODO: Leave this in, else we get different events */ 
    
    return po;    
}
/*
 *  Set the name of the Port Object
 */
int PortObjectSetName(PortObject * po, char * name)
{
    if( !po )
        return -1;
    
    if( !name )
        return -1;
    
    /* free the old name */
    if(po->name)
        free(po->name);

    /* alloc a new name */    
    po->name = SnortStrdup(name);
    if( !po->name )
        return -1;

    return 0;
}
/*
 *  Free the PortObject
 */
void PortObjectFree( void * pvoid ) 
{
    PortObject * po = (PortObject *)pvoid; 
    DEBUG_WRAP(static int pof_cnt = 0; pof_cnt++;);
   
    DEBUG_WRAP(DebugMessage(DEBUG_PORTLISTS,"PortObjectFree-Cnt: %d ptr=%p\n",pof_cnt,pvoid););
    
    if( !po ) return ;

	if( po->name ) free (po->name );
	if( po->item_list) sflist_free_all( po->item_list, free );
    if( po->rule_list) sflist_free_all( po->rule_list, free );
	free( po );
}
/*
 *  Free the PortObject2
 */
void PortObjectFree2( void * pvoid ) 
{
    PortObject2 * po = (PortObject2 *)pvoid; 
    DEBUG_WRAP(static int pof2_cnt = 0; pof2_cnt++;);
   
    DEBUG_WRAP(DebugMessage(DEBUG_PORTLISTS,"PortObjectFree2-Cnt: %d ptr=%p\n",pof2_cnt,pvoid););
    
    if( !po ) return;

	if( po->name ) free (po->name );
    if( po->item_list) sflist_free_all( po->item_list, free );
    if( po->rule_hash) sfghash_delete( po->rule_hash );
	free( po );
}

/*
 * Create a new ortObjectItem
 */
PortObjectItem * PortObjectItemNew(void)
{
    PortObjectItem *poi = (PortObjectItem *)SnortAlloc(sizeof(PortObjectItem));

    return poi;
}

/*
 * Add a PortObjectItem to a PortObject
 */
int PortObjectAddItem( PortObject * po, PortObjectItem * poi)
{
   return  sflist_add_tail( po->item_list, poi );
}
/*
	Dup a PortObjectItem
*/
PortObjectItem * PortObjectItemDup( PortObjectItem * poi)
{
   PortObjectItem * poinew;
   
   if( !poi )
	   return 0;

   poinew = PortObjectItemNew();
   if( !poinew )
	   return 0;

   memcpy(poinew,poi,sizeof(PortObjectItem));

   return poinew;
}

#if 0
/*
 *  Create a rule array from the port object,
 *  the caller must free the array.
 */
int * PortObjecExtractRuleArray( PortObject * po, int * nrules )
{
	SF_LNODE       * lpos = NULL;
    int            * prid = NULL;
    int            * array = NULL; 
    int              mrules, n=0;
        
    /* Dup the input rule list */
    if( !po->rule_list )
        return array;
    
    mrules = *nrules = po->rule_list->count;

    array = (int*)SnortAlloc(mrules * sizeof(int));
          
	for(prid  = (int*)sflist_firstpos(po->rule_list,&lpos);
	    prid != 0;
	    prid  = (int*)sflist_nextpos(po->rule_list,&lpos) )
	{
       if( n < mrules )
       {
          array[ n++ ] = *prid;
       }
       else
       {
          DEBUG_WRAP(DebugMessage(DEBUG_PORTLISTS,
                     "ERROR: po->rule_list->count < nrules\n"););
       }
	}

    return array;
}
/*
 *  Create a rule array from the port object,
 *  the caller must free the array.
 */
int * PortObjecExtractRuleArray2( PortObject2 * po, int * nrules )
{
    int            * array = NULL; 
    int            * prid;
    int              mrules, n=0;
    SFGHASH_NODE   * node;
        
    /* Dup the input rule list */
    if( !po->rule_hash )
        return array;
    
    mrules = *nrules = po->rule_hash->count;

    array = (int*)SnortAlloc(mrules * sizeof(int));

    for( node = sfghash_findfirst(po->rule_hash);
         node;
         node = sfghash_findnext(po->rule_hash) )
    {
       prid = node->data;
       
       if( !prid )
          continue;

       if( n < mrules )
       {
          array[ n++ ] = *prid;
       }
       else
       {
           DEBUG_WRAP(DebugMessage(DEBUG_PORTLISTS,"ERROR: po->rule_hash->count <  nrules\n"););
           //exit(0);
       }
	}

    *nrules = n;

    return array;
}
#endif

/*
 * Dup the PortObjects Item List, RuleList, and Name
 */
PortObject * PortObjectDup( PortObject * po )
{
	PortObject     * ponew=0;
    PortObjectItem * poi=0;
    PortObjectItem * poinew=0;
	SF_LNODE       * lpos=0;
    int            * prid=0;
    int            * prule=0;

	ponew = PortObjectNew();
	if( !ponew )
		return 0;

    /* Dup the Name */
    if( po->name )
        ponew->name = strdup(po->name);
    else
        ponew->name = strdup("dup");

    if( !ponew->name )
    {
        free( ponew );
        return NULL;    
    }
   
    /* Dup the Item List */
    if( po->item_list )
    {
	  for(poi =(PortObjectItem*)sflist_firstpos(po->item_list,&lpos);
	      poi!=0;
	      poi =(PortObjectItem*)sflist_nextpos(po->item_list,&lpos) )
	  {
        poinew = PortObjectItemDup( poi );
	    if(!poinew)
        {
            free( ponew->name );
            free( ponew );
	  	    return 0;
        }
	    PortObjectAddItem( ponew, poinew );
	  }
    }

    /* Dup the input rule list */
    if( po->rule_list )
    {
	  for(prid  = (int*)sflist_firstpos(po->rule_list,&lpos);
	      prid != 0;
	      prid  = (int*)sflist_nextpos(po->rule_list,&lpos) )
	  {
          prule = calloc(1,sizeof(int));
          if(!prule)
          {
             free( poinew );
             free( ponew->name );
             free( ponew );
             return NULL;
          }
          *prule = *prid;
          sflist_add_tail(ponew->rule_list,prule);
	  }
    }

	return ponew;
}
/*
 * Dup the PortObjects Item List, and Name
 */
PortObject * PortObjectDupPorts( PortObject * po )
{
	PortObject     * ponew=0;
    PortObjectItem * poi=0;
    PortObjectItem * poinew=0;
	SF_LNODE       * lpos=0;

	ponew = PortObjectNew();
	if( !ponew )