mwm.c

一种多模串匹配算法

    kk = ps->msNumPatterns;

    ps->msNumPatterns++;

    if( ps->msPatArray[kk].psLen < (unsigned)ps->msSmallest ) ps->msSmallest= ps->msPatArray[kk].psLen;
    if( ps->msPatArray[kk].psLen > (unsigned)ps->msLargest  ) ps->msLargest = ps->msPatArray[kk].psLen;
 
    ps->msTotal   += ps->msPatArray[kk].psLen;
    ps->msAvg      = ps->msTotal / ps->msNumPatterns;

    return 1;
}
#endif

  
/*
** Exact Pattern Matcher - don't use this...
*/
int mwmAddPattern( void * pv, unsigned char * P, int m, unsigned id )
{

    return mwmAddPatternEx( pv, P, m, 0, id, 0, pv, 0 );
}



/*
** bcompare:: 
**
** Perform a Binary comparsion of 2 byte sequences of possibly 
** differing lengths.
**
** returns -1 a < b
**         +1 a > b
**          0 a = b
*/
static int bcompare( unsigned char *a, int alen, unsigned char * b, int blen ) 
{
  	 int stat;
	 if( alen == blen )
	 {
	   return memcmp(a,b,alen);
	 }
	 else if( alen < blen )
	 {
       if( (stat=memcmp(a,b,alen)) != 0 ) 
	        return stat;
 	   return -1;
	 }
	 else 
	 {
       if( (stat=memcmp(a,b,blen)) != 0 ) 
	     return stat;
	   return +1;
	 }
}

/*
** sortcmp::  qsort callback
*/
static int CDECL sortcmp( const void * e1, const void * e2 )
{
    MWM_PATTERN_STRUCT *r1= (MWM_PATTERN_STRUCT*)e1;
    MWM_PATTERN_STRUCT *r2= (MWM_PATTERN_STRUCT*)e2;
    return bcompare( r1->psPat, r1->psLen, r2->psPat, r2->psLen ); 
}

/*
** HASH ROUTINE - used during pattern setup, but inline during searches
*/
static unsigned HASH16( unsigned char * T )
{
     return (unsigned short) (((*T)<<8) | *(T+1));
}

/*
** Build the hash table, and pattern groups
*/
static void mwmPrepHashedPatternGroups(MWM_STRUCT * ps)
{
  unsigned sindex,hindex,ningroup;
  int i;

  /*
  **  Allocate and Init 2+ byte pattern hash table 
  */
   ps->msNumHashEntries = HASHTABLESIZE;
   ps->msHash = (HASH_TYPE*)malloc( sizeof(HASH_TYPE) * ps->msNumHashEntries );
   if( !ps->msHash ) 
   {
       FatalError("No memory in mwmPrephashedPatternGroups()\n"
                  "Try uncommenting the \"config detection: search-method\""
                  "in snort.conf\n");
   }

   /* Init Hash table to default value */
   for(i=0;i<(int)ps->msNumHashEntries;i++)
   {
      ps->msHash[i] = (HASH_TYPE)-1;
   }
   
   /* Initialize The One Byte Pattern Hash Table */
   for(i=0;i<256;i++)
   {   
      ps->msHash1[i] = (HASH_TYPE)-1;
   }

  /*
  ** Add the patterns to the hash table
  */
  for(i=0;i<ps->msNumPatterns;i++)
  {
    if( ps->msPatArray[i].psLen > 1 )
    {
       hindex = HASH16(ps->msPatArray[i].psPat); 
       sindex = ps->msHash[ hindex ] = i;
       ningroup = 1;  
       while( (++i < ps->msNumPatterns) && (hindex==HASH16(ps->msPatArray[i].psPat)) )
         ningroup++;
       ps->msNumArray[ sindex ] = ningroup;
       i--;
    }
    else if( ps->msPatArray[i].psLen == 1 )
    {
       hindex = ps->msPatArray[i].psPat[0]; 
       sindex = ps->msHash1[ hindex ] = i;
       ningroup = 1;  

       while((++i < ps->msNumPatterns) && (hindex == ps->msPatArray[i].psPat[0]) && (ps->msPatArray[i].psLen == 1))
         ningroup++;

       ps->msNumArray[ sindex ] = ningroup;
       i--;
    }
  }


}


/*
*  Standard Bad Character Multi-Pattern Skip Table
*/
static void mwmPrepBadCharTable(MWM_STRUCT * ps)
{
    unsigned  short i, k,  m, cindex, shift;
    unsigned  small_value=32000, large_value=0;
    
    /* Determine largest and smallest pattern sizes */
    for(i=0;i<ps->msNumPatterns;i++)
    {
      if( ps->msPatArray[i].psLen < small_value ) small_value = ps->msPatArray[i].psLen;
      if( ps->msPatArray[i].psLen > large_value ) large_value = ps->msPatArray[i].psLen;
    }

    m = (unsigned short) small_value; 

    if( m > 255 ) m = 255;

    ps->msShiftLen = m;

    /* Initialze the default shift table. Max shift of 256 characters */
    for(i=0;i<256;i++)
    {
       ps->msShift[i] = m;  
    }

    /*  Multi-Pattern BAD CHARACTER SHIFT */
    for(i=0;i<ps->msNumPatterns;i++)
    {
       for(k=0;k<m;k++)
       {
          shift = (unsigned short)(m - 1 - k);

          if( shift > 255 ) shift = 255;

          cindex = ps->msPatArray[ i ].psPat[ k ];

          if( shift < ps->msShift[ cindex ] )
              ps->msShift[ cindex ] = shift;
       }
    }
}

/*
** Prep and Build a Bad Word Shift table
*/
static void mbmPrepBadWordTable(MWM_STRUCT * ps)
{
    int i;
    unsigned  short  k,  m, cindex;
    unsigned  small_value=32000, large_value=0;
    unsigned  shift;

    ps->msShift2 = (unsigned char *)malloc(BWSHIFTABLESIZE*sizeof(char));
    if( !ps->msShift2 )
         return;

    /* Determine largest and smallest pattern sizes */
    for(i=0;i<ps->msNumPatterns;i++)
    {
        if( ps->msPatArray[i].psLen < small_value ) small_value = ps->msPatArray[i].psLen;
        if( ps->msPatArray[i].psLen > large_value ) large_value = ps->msPatArray[i].psLen;
    }

    m = (unsigned short) small_value;  /* Maximum Boyer-Moore Shift */

    /* Limit the maximum size of the smallest pattern to 255 bytes */
    if( m > 255 ) m = 255; 

    ps->msShiftLen = m;

    /* Initialze the default shift table. */
    for(i=0;i<BWSHIFTABLESIZE;i++)
    {
      ps->msShift2[i] = (unsigned)(m-1);  
    }


    /* Multi-Pattern Bad Word Shift Table Values */
    for(i=0;i<ps->msNumPatterns;i++)
    {
        for(k=0;k<m-1;k++)
        {
         shift = (unsigned short)(m - 2 - k);

         if( shift > 255 ) shift = 255;

         cindex = ( ps->msPatArray[i].psPat[ k ] | (ps->msPatArray[i].psPat[k+1]<<8) );

         if( shift < ps->msShift2[ cindex ] ) 
             ps->msShift2[ cindex ] = shift;
       }
    }
}




/*
**  Print some Pattern Stats
*/
void mwmShowStats( void * pv )
{
   MWM_STRUCT * ps = (MWM_STRUCT*)pv;

   int i;
   printf("Pattern Stats\n");
   printf("-------------\n");
   printf("Patterns   : %d\n"      , ps->msNumPatterns);
   printf("Average    : %d chars\n", ps->msAvg);
   printf("Smallest   : %d chars\n", ps->msSmallest);
   printf("Largest    : %d chars\n", ps->msLargest);
   printf("Total chars: %d\n"    , ps->msTotal);

   for(i=0;i<ps->msLargest+1;i++)
   {
     if( ps->msLengths[i] ) 
       printf("Len[%d] : %d patterns\n", i, ps->msLengths[i] );
   }

   printf("\n");

}

/*
**  Calc some pattern length stats
*/
static void mwmAnalyzePattens( MWM_STRUCT * ps )
{
   int i;

   ps->msLengths= (int*) malloc( sizeof(int) * (ps->msLargest+1) );
   
   if( ps->msLengths )
   {
     memset( ps->msLengths, 0, sizeof(int) * (ps->msLargest+1) );

     for(i=0;i<ps->msNumPatterns;i++)
     {
        ps->msLengths[ ps->msPatArray[i].psLen ]++;
     }
   }
}



/*
**  Selects the bad Word Algorithm over the bad Character algorithm
**  This should be called before mwmPrepPatterns
*/
void mwmLargeShifts( void *  pv, int flag)
{
   MWM_STRUCT * ps = (MWM_STRUCT*)pv;
   ps->msLargeShifts = flag;
}

/*
** mwmGetNpatterns::
*/
int mwmGetNumPatterns( void  * pv )
{
    MWM_STRUCT *p = (MWM_STRUCT*)pv;
    return p->msNumPatterns;
}


#ifdef BITOP_TEST    
/*
*  Assign the rule mask vi an API
*/
void mwmSetRuleMask( void  * pv, BITOP * rm )
{
   MWM_STRUCT * ps = (MWM_STRUCT*) pv;
   ps->RuleMask = rm;
}
#endif

/*
*
*  Finds matches within a groups of patterns, these patterns all have at least 2 characters
*  This version walks thru all of the patterns in the group and applies a reverse string comparison
*  to minimize the impact of sequences of patterns that keep repeating intital character strings
*  with minimal differences at the end of the strings.
*
*/
static 
INLINE
int mwmGroupMatch2( MWM_STRUCT * ps, 
                   int index,
                   unsigned char * Tx, 
                   unsigned char * T, 
                   unsigned char * Tc, 
                   int Tleft,
                   void * data,
                   int (*match)(void*,int,void*) )
{
     int k, nfound=0;
     MWM_PATTERN_STRUCT * patrn; 
     MWM_PATTERN_STRUCT * patrnEnd; 

     /* Process the Hash Group Patterns against the current Text Suffix */
     patrn    = &ps->msPatArray[index];       
     patrnEnd = patrn + ps->msNumArray[index];

     /*  Match Loop - Test each pattern in the group against the Text */
     for( ;patrn < patrnEnd; patrn++ )  
     {
       unsigned char *p, *q;

       /* Test if this Pattern is to big for Text, not a possible match */
       if( (unsigned)Tleft < patrn->psLen )
           continue;

#ifdef BITOP_TEST    
       /* Test if this rule has been hit already - ignore it if it has */
       if( ps->RuleMask )
       {
	  if( boIsBitSet( ps->RuleMask, patrn->psIID ) )
    	      continue;
       }
#endif

       /* Setup the reverse string compare */
       k = patrn->psLen - HASHBYTES16 - 1; 
       q = patrn->psPat + HASHBYTES16;     
       p = T            + HASHBYTES16;     

       /* Compare strings backward, unrolling does not help in perf tests. */
       while( k >= 0 && (q[k] == p[k]) ) k--;

       /* We have a content match - call the match routine for further processing */
       if( k < 0 ) 
       {
         if( Tc && !patrn->psNoCase )
         {  
           /* Validate a case sensitive match - than call match */
           if( !memcmp(patrn->psPatCase,&Tc[T-Tx],patrn->psLen) )
           {
             nfound++; 
             if( match( patrn->psID, (int)(T-Tx), data ) )
               return -(nfound+1);
           }

         }else{
           nfound++; 
           if( match( patrn->psID, (int)(T-Tx), data ) )
               return -(nfound+1);
         }
       }
     }

     return nfound;
}


/*
**  
**  No Bad Character Shifts
**  Handles pattern groups with one byte or larger patterns 
**  Uses 1 byte and 2 byte hash tables to group patterns
**
*/
static 

int mwmSearchExNoBC( MWM_STRUCT *ps, 
                unsigned char * Tx, int n, unsigned char * Tc,
                int(*match)( void * id, int index,void* data ),
                void * data )
{
    int                 Tleft, index, nfound, ng;
    unsigned char      *T, *Tend, *B;
    MWM_PATTERN_STRUCT *patrn, *patrnEnd;

    nfound = 0;

    Tleft = n;
    Tend  = Tx + n;

    /* Test if text is shorter than the shortest pattern */
    if( (unsigned)n < ps->msShiftLen )
        return 0;

    /*  Process each suffix of the Text, left to right, incrementing T so T = S[j] */
    for(T = Tx, B = Tx + ps->msShiftLen - 1; B < Tend; T++, B++, Tleft--)
    {
        /* Test for single char pattern matches */
        if( (index = ps->msHash1[*T]) != (HASH_TYPE)-1 )
        {
            patrn    = &ps->msPatArray[index];
            patrnEnd = patrn + ps->msNumArray[index];

            for( ;patrn < patrnEnd; patrn++ )  
            {
                if( Tc && !patrn->psNoCase )
                {    
                    if( patrn->psPatCase[0] == Tc[T-Tx] )
	                {  
                        nfound++;
                        if(match(patrn->psID,  (int)(T-Tx), data))  
                            return nfound;
                    }
                }
                else
                {
                    nfound++;
                    if(match(patrn->psID, (int)(T-Tx), data))  
                        return nfound;
                }
            }
        }     

        /* 
        ** Test for last char in Text, one byte pattern test 
        ** was done above, were done. 
        */
        if( Tleft == 1 )
            return nfound; 

        /* 
        ** Test if the 2 char prefix of this suffix shows up 
        ** in the hash table
        */
        if( (index = ps->msHash [ ( (*T)<<8 ) | *(T+1) ] ) == (HASH_TYPE)-1 )
            continue; 

        /* Match this group against the current suffix */
        ng = mwmGroupMatch2( ps, index,Tx, T, Tc, Tleft, data, match );
        if( ng < 0 )
        {
            ng = -ng;
            ng--;
            nfound += ng;

            return nfound;
        }
        else
        {
            nfound += ng;
        }
    }

    return nfound;
}


/*
**
**  Uses Bad Character Shifts
**  Handles pattern groups with 2 or more bytes per pattern
**  Uses 2 byte hash table to group patterns
**
*/
static 

int mwmSearchExBC( MWM_STRUCT *ps, 
                   unsigned char * Tx, int n, unsigned char * Tc,
                   int(*match)( void * id, int index, void * data ), 
                   void * data )
{
  int                 Tleft, index, nfound, tshift,ng;
  unsigned char      *T, *Tend, *B;
  /*MWM_PATTERN_STRUCT *patrn, *patrnEnd;*/

  nfound = 0;

  Tleft = n;
  Tend  = Tx + n;

  /* Test if text is shorter than the shortest pattern */
  if( (unsigned)n < ps->msShiftLen )
      return 0;


  /*  Process each suffix of the Text, left to right, incrementing T so T = S[j] */
  for( T = Tx, B = Tx + ps->msShiftLen - 1; B < Tend; T++, B++, Tleft-- )
  {
       /* Multi-Pattern Bad Character Shift */
       while( (tshift=ps->msShift[*B]) > 0 ) 
       {
          B += tshift; T += tshift; Tleft -= tshift;
          if( B >= Tend ) return nfound;

          tshift=ps->msShift[*B];
          B += tshift; T += tshift; Tleft -= tshift;
          if( B >= Tend ) return nfound;
       }


     /* Test for last char in Text, one byte pattern test was done above, were done. */
     if( Tleft == 1 )
         return nfound; 

     /* Test if the 2 char prefix of this suffix shows up in the hash table */
     if( (index = ps->msHash [ ( (*T)<<8 ) | *(T+1) ] ) == (HASH_TYPE)-1 )
         continue; 

     /* Match this group against the current suffix */
     ng = mwmGroupMatch2( ps, index,Tx, T, Tc, Tleft, data, match );
     if( ng < 0 )
     {
         ng = -ng;
         ng--;
         nfound += ng;
         return nfound;
     }
     else
     {
        nfound += ng;
     }



  }

  return nfound;
}


/*
**
**  Uses Bad Word Shifts
**  Handles pattern groups with 2 or more bytes per pattern
**  Uses 2 byte hash table to group patterns
**
*/
static 
int mwmSearchExBW( MWM_STRUCT *ps, 
                unsigned char * Tx, int n, unsigned char * Tc,