bnfa_search.c

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

                
				res = Match (patrn, index, data);
			    if ( res > 0 )
                {
                     *current_state = state;
				     return nfound;
                }
                if( res < 0 )
                {
                    last_match=last_match_saved;
                }
    	}
	}
  }
  return nfound;
}
#endif

/*
   binary array search on sparse transition array

   O(logN) search times..same as a binary tree.
   data must be in sorted order in the array.

   return:  = -1 => not found
		   >= 0  => index of element 'val' 

  notes:
	val is tested against the high 8 bits of the 'a' array entry,
	this is particular to the storage format we are using.
*/
static
inline 
int _bnfa_binearch( bnfa_state_t * a, int a_len, int val )
{
   int m, l, r;
   int c;

   l = 0;
   r = a_len - 1;

   while( r >= l )
   {
      m = ( r + l ) >> 1;

	  c = a[m] >> BNFA_SPARSE_VALUE_SHIFT;

      if( val == c )
      {
          return m;
      }

      else if( val <  c )
      {
          r = m - 1;
      }

      else /* val > c */
      {
          l = m + 1; 
      }
   }
   return -1;
}

/*
*   Sparse format for state table using single array storage
*
*   word 1: state
*   word 2: control-word = cb<<24| fs
*           cb	: control-byte
*				: mb | fb | nt
*				mb : bit 8 set if match state, zero otherwise
*				fb : bit 7 set if using full format, zero otherwise
*				nt : number of transitions 0..63 (more than 63 requires full format)
*			fs: failure-transition-state 
*   word 3+: byte-value(0-255) << 24 | transition-state
*/
static
inline 
unsigned 
_bnfa_get_next_state_csparse_nfa(bnfa_state_t * pcx, unsigned sindex, unsigned  input)
{
   int k;
   int nc; 
   int index;
   register bnfa_state_t * pc;

    for(;;)
	{
      pc = pcx + sindex + 1; /* skip state-id == 1st word */

      if( pc[0] & BNFA_SPARSE_FULL_BIT )
	  {   
		if( sindex == 0 )
		{
		  return pc[1+input] & BNFA_SPARSE_MAX_STATE; 
		}
		else
		{
		  if( pc[1+input] & BNFA_SPARSE_MAX_STATE ) 
			  return pc[1+input] & BNFA_SPARSE_MAX_STATE;
		}
	  }
      else
	  {
         nc = (pc[0]>>BNFA_SPARSE_COUNT_SHIFT) & BNFA_SPARSE_MAX_ROW_TRANSITIONS;

	     if( nc > BNFA_SPARSE_LINEAR_SEARCH_LIMIT )
		 {
    	   /* binary search... */
		   index = _bnfa_binearch( pc+1, nc, input );
		   if( index >= 0 )
		   {
		      return pc[index+1] & BNFA_SPARSE_MAX_STATE;
		   }
		 }
	     else
		 {
    	   /* linear search... */
           for( k=0; k<nc; k++ ) 
		   {   
             if( (pc[k+1]>>BNFA_SPARSE_VALUE_SHIFT) == input )
			 {
                return pc[k+1] & BNFA_SPARSE_MAX_STATE;
			 }
		   }
		 }
	  }

	  /* no transition found ... get the failure state and try again  */
	  sindex = pc[0] & BNFA_SPARSE_MAX_STATE;
    } 
}
/*
 *  Per Pattern case search, case is on per pattern basis
 *
 *  note: index is not used by snort, so it's commented
 */
static
inline
unsigned
_bnfa_search_csparse_nfa(   bnfa_struct_t * bnfa, unsigned char *Tx, int n,
		    			int (*Match)(bnfa_pattern_t * id, int index, void *data), 
						void *data, unsigned sindex, int *current_state ) 
{
  bnfa_match_node_t  * mlist;
  unsigned char      * Tend;
  unsigned char      * T;
  unsigned char        Tchar;
  unsigned             index;
  bnfa_match_node_t ** MatchList = bnfa->bnfaMatchList;
  bnfa_pattern_t     * patrn;
  bnfa_state_t       * transList = bnfa->bnfaTransList;
  unsigned             nfound = 0;
  unsigned             last_match=LAST_STATE_INIT;
  unsigned             last_match_saved=LAST_STATE_INIT;
  int                  res;

  T    = Tx;
  Tend = T + n;
  
  for(; T<Tend; T++)
  {
   	Tchar = xlatcase[ *T ];

   	/* Transition to next state index */
   	sindex = _bnfa_get_next_state_csparse_nfa(transList,sindex,Tchar);

   	/* Log matches in this state - if any */
	if( sindex && (transList[sindex+1] & BNFA_SPARSE_MATCH_BIT) )
	{
        if( sindex == last_match )
            continue;
        
        last_match_saved = last_match;
        last_match = sindex;
        
       	for(mlist = MatchList[ transList[sindex] ];
			mlist!= NULL;
			mlist = mlist->next )
		{
		   	patrn = (bnfa_pattern_t*)mlist->data;

           	index = T - Tx - patrn->n + 1;
           	if( patrn->nocase )
           	{
                nfound++;
	        	res = Match (patrn->userdata, index, data);
	        	if ( res > 0 )
                {
                  *current_state = sindex;
				  return nfound;
                }
                else if( res < 0 )
                {
                    last_match = last_match_saved;
                }
           	}
           	else
           	{  	/* If case sensitive pattern, do an exact match test */
			  	if( memcmp (patrn->casepatrn, T - patrn->n + 1, patrn->n) == 0 )
			  	{
                  nfound++;
	        	  res = Match (patrn->userdata, index, data);
	        	  if ( res > 0 )
                  {
                    *current_state = sindex;
				    return nfound;
                  }
                  else if( res < 0 )
                  {
                    /* Revert, must retest this rule */
                    last_match = last_match_saved;
                  }
			  	}
                else
                {
                    /* Revert last_match since we did not test a rule in this set 
                     * and must revisit this rule list next time we hit this state.
                     */
                    last_match = last_match_saved;
                }
           	}
		}
	  }
  }
  return nfound;
}
/*
 * Case specific search, global to all patterns
 *
 *  note: index is not used by snort, so it's commented
 */
static
inline
unsigned
_bnfa_search_csparse_nfa_case(   bnfa_struct_t * bnfa, unsigned char *Tx, int n,
		    			int (*Match)(bnfa_pattern_t * id, int index, void *data), 
						void *data, unsigned sindex, int *current_state ) 
{
  bnfa_match_node_t  * mlist;
  unsigned char      * Tend;
  unsigned char      * T;
  unsigned             index;
  bnfa_match_node_t ** MatchList = bnfa->bnfaMatchList;
  bnfa_pattern_t     * patrn;
  bnfa_state_t       * transList = bnfa->bnfaTransList;
  unsigned             nfound = 0;
  unsigned             last_match=LAST_STATE_INIT;
  unsigned             last_match_saved=LAST_STATE_INIT;
  int                  res;

  T    = Tx;
  Tend = T + n;
  
  for(; T<Tend; T++)
  {
   	/* Transition to next state index */
   	sindex = _bnfa_get_next_state_csparse_nfa(transList,sindex,*T);

   	/* Log matches in this state - if any */
	if( sindex && (transList[sindex+1] & BNFA_SPARSE_MATCH_BIT) )
	{
        if( sindex == last_match )
            continue;
   
        last_match_saved = last_match;
        last_match = sindex;
       	
        for(mlist = MatchList[ transList[sindex] ];
			mlist!= NULL;
			mlist = mlist->next )
		{
		   	patrn = (bnfa_pattern_t*)mlist->data;
           	index = T - Tx - patrn->n + 1;
            nfound++;
	       
            res = Match (patrn->userdata, index, data);
	        if ( res > 0 )
            {
               *current_state = sindex;
		       return nfound;
            }
            else if( res < 0 )
            {
               /* Revert, must retest this rule */
               last_match = last_match_saved;
            }
		}
	}
  }
  return nfound;
}
/*
 *  NoCase search - global to all patterns
 *
 *  note: index is not used by snort, so it's commented
 */
static
inline
unsigned
_bnfa_search_csparse_nfa_nocase(   bnfa_struct_t * bnfa, unsigned char *Tx, int n,
		    			int (*Match)(bnfa_pattern_t * id, int index, void *data), 
						void *data, unsigned sindex, int *current_state ) 
{
  bnfa_match_node_t  * mlist;
  unsigned char      * Tend;
  unsigned char      * T;
  unsigned char        Tchar;
  unsigned             index;
  bnfa_match_node_t ** MatchList = bnfa->bnfaMatchList;
  bnfa_pattern_t     * patrn;
  bnfa_state_t       * transList = bnfa->bnfaTransList;
  unsigned             nfound = 0;
  unsigned             last_match=LAST_STATE_INIT;
  unsigned             last_match_saved=LAST_STATE_INIT;
  int                  res;
  
  T    = Tx;
  Tend = T + n;
  
  for(; T<Tend; T++)
  {
   	Tchar = xlatcase[ *T ];

   	/* Transition to next state index */
   	sindex = _bnfa_get_next_state_csparse_nfa(transList,sindex,Tchar);

   	/* Log matches in this state - if any */
	if( sindex && (transList[sindex+1] & BNFA_SPARSE_MATCH_BIT) )
	{
        if( sindex == last_match )
            continue;
        
        last_match_saved = last_match;
        last_match = sindex;
        
       	for(mlist = MatchList[ transList[sindex] ];
			mlist!= NULL;
			mlist = mlist->next )
		{
		   	patrn = (bnfa_pattern_t*)mlist->data;
           	index = T - Tx - patrn->n + 1;
            nfound++;
	  
            res = Match (patrn->userdata, index, data);
	        if ( res > 0 )
            {
               *current_state = sindex;
		       return nfound;
            }
            else if( res < 0 )
            {
               /* Revert, must retest this rule */
               last_match = last_match_saved;
            }
		}
	  }
  }
  return nfound;
}

/*
*  BNFA Search Function
*
*  bnfa   - state machine
*  Tx     - text buffer to search
*  n      - number of bytes in Tx      
*  Match  - function to call when a match is found
*  data   - user supplied data that is passed to the Match function
*  sindex - state tracker, set value to zero to reset the state machine,
*			zero should be the value passed in on the 1st buffer or each buffer
*           that is to be analyzed on its own, the state machine updates this 
*			during searches. This allows for sequential buffer searchs without 
*			reseting the state machine. Save this value as returned from the 
*			previous search for the next search.
*
*  returns 
*	The state or sindex of the state machine. This can than be passed back
*   in on the next search, if desired.  
*/
unsigned 
bnfaSearch(	bnfa_struct_t * bnfa, unsigned char *Tx, int n,
			int (*Match) ( void * id, int index, void *data), 
            void *data, unsigned sindex, int* current_state )
{
    int ret = 0; 

    /***** This should be tested before we use it *******/
    /*
    if (current_state)
    {
        sindex = (unsigned)*current_state;
    }
    */

#ifdef ALLOW_NFA_FULL
    if( bnfa->bnfaFormat == BNFA_SPARSE )
    {
        if( bnfa->bnfaCaseMode == BNFA_PER_PAT_CASE )
        {
          ret = _bnfa_search_csparse_nfa( bnfa, Tx, n, 
		      (int (*)(bnfa_pattern_t*,int i,void *data))Match, data, sindex, current_state );
        }
        else  if( bnfa->bnfaCaseMode == BNFA_CASE )
        {
          ret = _bnfa_search_csparse_nfa_case( bnfa, Tx, n, 
		        (int (*)(bnfa_pattern_t *,int index,void *data) )Match, data, sindex, current_state );
        }
        else /* NOCASE */
        {
          ret = _bnfa_search_csparse_nfa_nocase( bnfa, Tx, n, 
		        (int (*)(bnfa_pattern_t *,int index,void *data) )Match, data, sindex, current_state );
        }
    }
    else if( bnfa->bnfaFormat == BNFA_FULL )
    {
        if( bnfa->bnfaCaseMode == BNFA_PER_PAT_CASE  )
        {
            ret = _bnfa_search_full_nfa( bnfa, Tx, n, 
		     (int (*)(bnfa_pattern_t *,int index, void *data) )Match,data, (bnfa_state_t) sindex, current_state );
        }
        else if( bnfa->bnfaCaseMode == BNFA_CASE  )
        {
            ret = _bnfa_search_full_nfa_case( bnfa, Tx, n, 
		      (int (*)(bnfa_pattern_t *,int index, void *data) )Match,data, (bnfa_state_t) sindex, current_state );
        }
        else
        {
            ret = _bnfa_search_full_nfa_nocase( bnfa, Tx, n, 
		      (int (*)(bnfa_pattern_t *,int index, void *data) )Match,data, (bnfa_state_t) sindex, current_state );
        }
    }
#else
    if( bnfa->bnfaCaseMode == BNFA_PER_PAT_CASE )
    {
   	    ret = _bnfa_search_csparse_nfa( bnfa, Tx, n, 
		    (int (*)(bnfa_pattern_t *,int index,void *data) )Match, data, sindex, current_state );
    }
    else if( bnfa->bnfaCaseMode == BNFA_CASE )
    {
   	    ret = _bnfa_search_csparse_nfa_case( bnfa, Tx, n, 
		    (int (*)(bnfa_pattern_t *,int index,void *data) )Match, data, sindex, current_state );
    }
    else/* NOCASE */
    {
   	    ret = _bnfa_search_csparse_nfa_nocase( bnfa, Tx, n, 
		    (int (*)(bnfa_pattern_t *,int index,void *data) )Match, data, sindex, current_state );
    }
#endif
    return ret;
}

/*
 *  Summary Info Data
 */
static bnfa_struct_t summary;
static int summary_cnt=0;

/*
*  Info: Print info a particular state machine.
*/
void bnfaPrintInfoEx( bnfa_struct_t * p, char * text )
{
    unsigned max_memory;

    if( !p->bnfaNumStates )
    {
	    return;
    }
    max_memory = p->bnfa_memory + p->pat_memory + p->list_memory + 
		         p->matchlist_memory + p->failstate_memory + p->nextstate_memory;

    if( text && summary_cnt )
    {
    printf("+-[AC-BNFA Search Info%s]------------------------------\n",text);
    printf("| Instances        : %d\n",summary_cnt);
    }
    else
    {
    printf("+-[AC-BNFA Search Info]------------------------------\n");
    }
    printf("| Patterns         : %d\n",p->bnfaPatternCnt);
    printf("| Pattern Chars    : %d\n",p->bnfaMaxStates);
    printf("| Num States       : %d\n",p->bnfaNumStates);
    printf("| Num Match States : %d\n",p->bnfaMatchStates);
    if( max_memory < 1024*1024 )
    {
        printf("| Memory           :   %.2fKbytes\n", (double)max_memory/1024 );
		printf("|   Patterns       :   %.2fK\n",(double)p->pat_memory/1024 );
		printf("|   Match Lists    :   %.2fK\n",(double)p->matchlist_memory/1024 );
		printf("|   Transitions    :   %.2fK\n",(double)p->nextstate_memory/1024 );
    }
    else
    {
    	printf("| Memory           :   %.2fMbytes\n", (double)max_memory/(1024*1024) );
	    printf("|   Patterns       :   %.2fM\n",(double)p->pat_memory/(1024*1024) );
    	printf("|   Match Lists    :   %.2fM\n",(double)p->matchlist_memory/(1024*1024) );
	    printf("|   Transitions    :   %.2fM\n",(double)p->nextstate_memory/(1024*1024) );
    }
    printf("+-------------------------------------------------\n");
}
void bnfaPrintInfo( bnfa_struct_t * p )
{
     bnfaPrintInfoEx( p, 0 );
}

void bnfaPrintSummary( void )
{
     bnfaPrintInfoEx( &summary, " Summary" );
}
void bnfaInitSummary( void )
{
    summary_cnt=0;
    memset(&summary,0,sizeof(bnfa_struct_t));
}
void bnfaAccumInfo( bnfa_struct_t * p )
{
    bnfa_struct_t * px = &summary;

    summary_cnt++;

    px->bnfaAlphabetSize  = p->bnfaAlphabetSize;
    px->bnfaPatternCnt   += p->bnfaPatternCnt;
    px->bnfaMaxStates    += p->bnfaMaxStates;
    px->bnfaNumStates    += p->bnfaNumStates;
    px->bnfaNumTrans     += p->bnfaNumTrans;
    px->bnfaMatchStates  += p->bnfaMatchStates;
	px->bnfa_memory      += p->bnfa_memory;
	px->pat_memory       += p->pat_memory;
	px->list_memory      += p->list_memory;
	px->matchlist_memory += p->matchlist_memory;
	px->nextstate_memory += p->nextstate_memory;
	px->failstate_memory += p->failstate_memory;
}