bnfa_search.c

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

       if( !t )
	   {
		   return 0;
	   }

       while(t && (t->key < BNFA_MAX_ALPHABET_SIZE ) )
       {
         full[ t->key ] = t->next_state;
         tcnt++;
         t = t->next;
       }
       return tcnt;
    }
}

/*
*  Add pattern characters to the initial upper case trie
*  unless Exact has been specified, in  which case all patterns
*  are assumed to be case specific.
*/
static 
int _bnfa_add_pattern_states (bnfa_struct_t * bnfa, bnfa_pattern_t * p) 
{
  int             state, next, n;
  unsigned char * pattern;
  bnfa_match_node_t  * pmn;

  n       = p->n;
  pattern = p->casepatrn;
  state   = 0;

  /* 
  *  Match up pattern with existing states
  */ 
  for (; n > 0; pattern++, n--)
  {
      if( bnfa->bnfaCaseMode == BNFA_CASE )
        next = _bnfa_list_get_next_state(bnfa,state,*pattern);
      else
        next = _bnfa_list_get_next_state(bnfa,state,xlatcase[*pattern]);

      if( next == BNFA_FAIL_STATE || next == 0 )
      {
         break;
      }
      state = next;
  }
  
  /*
  *   Add new states for the rest of the pattern bytes, 1 state per byte, uppercase
  */ 
  for (; n > 0; pattern++, n--)
  {
      bnfa->bnfaNumStates++; 

      if( bnfa->bnfaCaseMode == BNFA_CASE )
      {
        if( _bnfa_list_put_next_state(bnfa,state,*pattern,bnfa->bnfaNumStates)  < 0 )
             return -1;
      }
      else
      {
        if( _bnfa_list_put_next_state(bnfa,state,xlatcase[*pattern],bnfa->bnfaNumStates)  < 0 )
             return -1;
      }
      state = bnfa->bnfaNumStates;

      if ( bnfa->bnfaNumStates >= bnfa->bnfaMaxStates )
      {
	       return -1;
      }
  }

  /*  Add a pattern to the list of patterns terminated at this state */
  pmn = (bnfa_match_node_t*)BNFA_MALLOC(sizeof(bnfa_match_node_t),bnfa->matchlist_memory);
  if( !pmn )
  {
	  return -1;
  }

  pmn->data = p;
  pmn->next = bnfa->bnfaMatchList[state];

  bnfa->bnfaMatchList[state] = pmn;

  return 0;
}


/*
*   Build a non-deterministic finite automata using Aho-Corasick construction
*   The keyword trie must already be built via _bnfa_add_pattern_states()
*/ 
static 
int _bnfa_build_nfa (bnfa_struct_t * bnfa) 
{
    int             r, s, i;
    QUEUE           q, *queue = &q;
    bnfa_state_t     * FailState = bnfa->bnfaFailState;
    bnfa_match_node_t ** MatchList = bnfa->bnfaMatchList;
    bnfa_match_node_t  * mlist;
    bnfa_match_node_t  * px;
  
	/* Init a Queue */ 
	queue_init (queue);
  
	/* Add the state 0 transitions 1st, 
	* the states at depth 1, fail to state 0 
	*/ 
	for (i = 0; i < bnfa->bnfaAlphabetSize; i++)
	{
		/* note that state zero deos not fail, 
		*  it just returns 0..nstates-1 
		*/
		s = _bnfa_list_get_next_state(bnfa,0,i); 
		if( s ) /* don't bother adding state zero */
		{
		  if( queue_add (queue, s) ) 
		  {
              return -1;
		  }
		  FailState[s] = 0;
		}
	}
  
	/* Build the fail state successive layer of transitions */
	while (queue_count (queue) > 0)
	{
		r = queue_remove (queue);
      
		/* Find Final States for any Failure */ 
		for(i = 0; i<bnfa->bnfaAlphabetSize; i++)
		{
			int fs, next;

			s = _bnfa_list_get_next_state(bnfa,r,i);

			if( s == BNFA_FAIL_STATE )
				continue;
		   
			if( queue_add (queue, s) ) 
			{
				return -1;
			}
 
			fs = FailState[r];

			/* 
			*  Locate the next valid state for 'i' starting at fs 
			*/ 
			while( (next=_bnfa_list_get_next_state(bnfa,fs,i)) == BNFA_FAIL_STATE )
			{
				fs = FailState[fs];
			}
	      
			/*
			*  Update 's' state failure state to point to the next valid state
			*/ 
			FailState[s] = next;
	      
			/*
			*  Copy 'next'states MatchList into 's' states MatchList, 
			*  we just create a new list nodes, the patterns are not copied.
			*/ 
			for( mlist = MatchList[next];mlist;mlist = mlist->next)
			{
				/* Dup the node, don't copy the data */
				px = (bnfa_match_node_t*)BNFA_MALLOC(sizeof(bnfa_match_node_t),bnfa->matchlist_memory);
				if( !px )
				{
					return 0;
				}

				px->data = mlist->data; 
		  
				px->next = MatchList[s]; /* insert at head */
		 
				MatchList[s] = px;
			}
		}
	}
  
	/* Clean up the queue */
	queue_free (queue);

	return 0;
}

#ifdef ALLOW_NFA_FULL
/*
*  Conver state machine to full format
*/
static 
int _bnfa_conv_list_to_full(bnfa_struct_t * bnfa) 
{
  int          k;
  bnfa_state_t  * p;
  bnfa_state_t ** NextState = bnfa->bnfaNextState;

  for(k=0;k<bnfa->bnfaNumStates;k++)
  {
    p = BNFA_MALLOC(sizeof(bnfa_state_t)*bnfa->bnfaAlphabetSize,bnfa->nextstate_memory);
    if(!p)
    {
      return -1;
    }
    _bnfa_list_conv_row_to_full( bnfa, (bnfa_state_t)k, p );

    NextState[k] = p; /* now we have a full format row vector */
  }

  return 0;
}
#endif

/*
*  Convert state machine to csparse format
*
*  Merges state/transition/failure arrays into one.
*
*  For each state we use a state-word followed by the transition list for the state
*  sw(state 0 )...tl(state 0) sw(state 1)...tl(state1) sw(state2)...tl(state2) ....
*  
*  The transition and failure states are replaced with the start index of transition state,
*  this eliminates the NextState[] lookup....
*
*  The compaction of multiple arays into a single array reduces the total number of
*  states that can be handled since the max index is 2^24-1, whereas without compaction
*  we had 2^24-1 states.  
*/
static 
int _bnfa_conv_list_to_csparse_array(bnfa_struct_t * bnfa) 
{
  int            m, k, i, nc;
  bnfa_state_t      state;
  bnfa_state_t    * FailState = (bnfa_state_t  *)bnfa->bnfaFailState;
  bnfa_state_t    * ps; /* transition list */
  bnfa_state_t    * pi; /* state indexes into ps */
  bnfa_state_t      ps_index=0;
  unsigned       nps;
  bnfa_state_t      full[BNFA_MAX_ALPHABET_SIZE];

  
  /* count total state transitions, account for state and control words  */
  nps = 0;
  for(k=0;k<bnfa->bnfaNumStates;k++)
  {
	nps++; /* state word */
	nps++; /* control word */

	/* count transitions */
	nc = 0;
	_bnfa_list_conv_row_to_full(bnfa, (bnfa_state_t)k, full );
	for( i=0; i<bnfa->bnfaAlphabetSize; i++ )
	{
		state = full[i] & BNFA_SPARSE_MAX_STATE;
		if( state != 0 )
		{
			nc++;
		}	
	}

	/* add in transition count */
   	if( (k == 0 && bnfa->bnfaForceFullZeroState) || nc > BNFA_SPARSE_MAX_ROW_TRANSITIONS )
	{
		nps += BNFA_MAX_ALPHABET_SIZE;
	}
	else
	{
   	    for( i=0; i<bnfa->bnfaAlphabetSize; i++ )
		{
		   state = full[i] & BNFA_SPARSE_MAX_STATE;
		   if( state != 0 )
		   {
		       nps++;
		   }	
		}
	}
  }

  /* check if we have too many states + transitions */
  if( nps > BNFA_SPARSE_MAX_STATE )
  {
	  /* Fatal */
	  return -1;
  }

  /*
    Alloc The Transition List - we need an array of bnfa_state_t items of size 'nps'
  */
  ps = BNFA_MALLOC( nps*sizeof(bnfa_state_t),bnfa->nextstate_memory);
  if( !ps ) 
  {
	  /* Fatal */
	  return -1;
  }
  bnfa->bnfaTransList = ps;
  
  /* 
     State Index list for pi - we need an array of bnfa_state_t items of size 'NumStates' 
  */
  pi = BNFA_MALLOC( bnfa->bnfaNumStates*sizeof(bnfa_state_t),bnfa->nextstate_memory);
  if( !pi ) 
  {
	  /* Fatal */
	  return -1;
  }

  /* 
      Build the Transition List Array
  */
  for(k=0;k<bnfa->bnfaNumStates;k++)
  {
	pi[k] = ps_index; /* save index of start of state 'k' */

	ps[ ps_index ] = k; /* save the state were in as the 1st word */
	
	ps_index++;  /* skip past state word */

	/* conver state 'k' to full format */
	_bnfa_list_conv_row_to_full(bnfa, (bnfa_state_t)k, full );

	/* count transitions */
	nc = 0;
	for( i=0; i<bnfa->bnfaAlphabetSize; i++ )
	{
		state = full[i] & BNFA_SPARSE_MAX_STATE;
		if( state != 0 )
		{
			nc++;
		}	
	}

	/* add a full state or a sparse state  */
	if( (k == 0 && bnfa->bnfaForceFullZeroState) || 
		nc > BNFA_SPARSE_MAX_ROW_TRANSITIONS )
	{
		/* set the control word */
		ps[ps_index]  = BNFA_SPARSE_FULL_BIT;
		ps[ps_index] |= FailState[k] & BNFA_SPARSE_MAX_STATE;
		if( bnfa->bnfaMatchList[k] )
		{
            ps[ps_index] |= BNFA_SPARSE_MATCH_BIT;
		}
		ps_index++;  

		/* copy the transitions */
		_bnfa_list_conv_row_to_full(bnfa, (bnfa_state_t)k, &ps[ps_index] );

 		ps_index += BNFA_MAX_ALPHABET_SIZE;  /* add in 256 transitions */

	}
   	else
	{
		/* set the control word */
   		ps[ps_index]  = nc<<BNFA_SPARSE_COUNT_SHIFT ;
   		ps[ps_index] |= FailState[k]&BNFA_SPARSE_MAX_STATE;
   		if( bnfa->bnfaMatchList[k] )
	  	{
       		ps[ps_index] |= BNFA_SPARSE_MATCH_BIT;
	  	}
		ps_index++;

		/* add in the transitions */
   		for( m=0, i=0; i<bnfa->bnfaAlphabetSize && m<nc; i++ )
	  	{
       		state = full[i] & BNFA_SPARSE_MAX_STATE;
       		if( state != 0 )
		 	{
           		ps[ps_index++] = (i<<BNFA_SPARSE_VALUE_SHIFT) | state;
				m++;
		 	}
	  	}
	}
  }

  /* sanity check we have not overflowed our buffer */
  if( ps_index > nps ) 
  {
	  /* Fatal */
	  return -1;
  }

  /* 
  Replace Transition states with Transition Indices. 
  This allows us to skip using NextState[] to locate the next state
  This limits us to <16M transitions due to 24 bit state sizes, and the fact
  we have now converted next-state fields to next-index fields in this array,
  and we have merged the next-state and state arrays.
  */
  ps_index=0;
  for(k=0; k< bnfa->bnfaNumStates; k++ )
  {
	 if( pi[k] >= nps )
	 {
		 /* Fatal */
		 return -1;
	 }

	 //ps_index = pi[k];  /* get index of next state */
	 ps_index++;        /* skip state id */

	 /* Full Format */
     if( ps[ps_index] & BNFA_SPARSE_FULL_BIT )
	 {
	   /* Do the fail-state */
       ps[ps_index] = ( ps[ps_index] & 0xff000000 ) | 
		              ( pi[ ps[ps_index] & BNFA_SPARSE_MAX_STATE ] ) ; 
	   ps_index++;

	   /* Do the transition-states */
	   for(i=0;i<BNFA_MAX_ALPHABET_SIZE;i++)
	   {
		 ps[ps_index] = ( ps[ps_index] & 0xff000000 ) | 
		                ( pi[ ps[ps_index] & BNFA_SPARSE_MAX_STATE ] ) ; 
		 ps_index++;
	   }
	 }

	 /* Sparse Format */
	 else
	 {
       	nc = (ps[ps_index] & BNFA_SPARSE_COUNT_BITS)>>BNFA_SPARSE_COUNT_SHIFT;
	   
	   	/* Do the cw = [cb | fail-state] */
   		ps[ps_index] =  ( ps[ps_index] & 0xff000000 ) |
						( pi[ ps[ps_index] & BNFA_SPARSE_MAX_STATE ] ); 
	   	ps_index++;

	   	/* Do the transition-states */
	   	for(i=0;i<nc;i++)
	   	{
       		ps[ps_index] = ( ps[ps_index] & 0xff000000 ) |
			               ( pi[ ps[ps_index] & BNFA_SPARSE_MAX_STATE ] );
		 	ps_index++;
	   	}
	 }

	 /* check for buffer overflow again */
 	 if( ps_index > nps )
	 {
		 /* Fatal */
		 return -1;
	 }

  }

  BNFA_FREE(pi,bnfa->bnfaNumStates*sizeof(bnfa_state_t),bnfa->nextstate_memory);

  return 0;
}

/*
*  Print the state machine - rather verbose
*/
void bnfaPrint(bnfa_struct_t * bnfa) 
{
  int			   k;
  bnfa_match_node_t  ** MatchList = bnfa->bnfaMatchList;
  bnfa_match_node_t   * mlist;
  int              ps_index=0;
  bnfa_state_t      * ps=0;

  if( !bnfa ) 
      return;
  
  if( !bnfa->bnfaNumStates ) 
	  return;

  if( bnfa->bnfaFormat ==BNFA_SPARSE )
  {
    printf("Print NFA-SPARSE state machine : %d active states\n", bnfa->bnfaNumStates);
    ps = bnfa->bnfaTransList;
    if( !ps )
        return;
  }

#ifdef ALLOW_NFA_FULL
  else if( bnfa->bnfaFormat ==BNFA_FULL )
  {
    printf("Print NFA-FULL state machine : %d active states\n", bnfa->bnfaNumStates);
  }
#endif
  
  
  for(k=0;k<bnfa->bnfaNumStates;k++)
  {
    printf(" state %-4d fmt=%d ",k,bnfa->bnfaFormat);

    if( bnfa->bnfaFormat == BNFA_SPARSE )
    {
	   unsigned i,cw,fs,nt,fb,mb;
       
	   ps_index++; /* skip state number */

       cw = ps[ps_index]; /* control word  */
	   fb = (cw &  BNFA_SPARSE_FULL_BIT)>>BNFA_SPARSE_VALUE_SHIFT;  /* full storage bit */ 
	   mb = (cw &  BNFA_SPARSE_MATCH_BIT)>>BNFA_SPARSE_VALUE_SHIFT; /* matching state bit */
	   nt = (cw &  BNFA_SPARSE_COUNT_BITS)>>BNFA_SPARSE_VALUE_SHIFT;/* number of transitions 0-63 */
	   fs = (cw &  BNFA_SPARSE_MAX_STATE)>>BNFA_SPARSE_VALUE_SHIFT; /* fail state */

	   ps_index++;  /* skip control word */

	   printf("mb=%3u fb=%3u fs=%-4u ",mb,fb,fs);

	   if( fb )
       {
         printf(" nt=%-3d : ",bnfa->bnfaAlphabetSize);

         for( i=0; i<(unsigned)bnfa->bnfaAlphabetSize; i++, ps_index++  )
         { 
    	    if( ps[ps_index] == 0  ) continue;

            if( isprint(i) )
               printf("%3c->%-6d\t",i,ps[ps_index]);
            else
               printf("%3d->%-6d\t",i,ps[ps_index]);
         }
       }  
       else
       {
          printf(" nt=%-3d : ",nt);

          for( i=0; i<nt; i++, ps_index++ )
          { 
             if( isprint(ps[ps_index]>>BNFA_SPARSE_VALUE_SHIFT) )
               printf("%3c->%-6d\t",ps[ps_index]>>BNFA_SPARSE_VALUE_SHIFT,ps[ps_index] & BNFA_SPARSE_MAX_STATE);
             else
			   printf("%3d->%-6d\t",ps[ps_index]>>BNFA_SPARSE_VALUE_SHIFT,ps[ps_index] & BNFA_SPARSE_MAX_STATE);
          }
       }
    }
#ifdef ALLOW_NFA_FULL
    else if( bnfa->bnfaFormat == BNFA_FULL ) 
    {
       int          i;
       bnfa_state_t    state;
       bnfa_state_t  * p;   
       bnfa_state_t ** NextState;