bnfa_search.c

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

       NextState = (bnfa_state_t **)bnfa->bnfaNextState;
       if( !NextState ) 
		   continue;

       p = NextState[k];

       printf("fs=%-4d nc=256 ",bnfa->bnfaFailState[k]);

       for( i=0; i<bnfa->bnfaAlphabetSize; i++ )
       {
          state = p[i];

          if( state != 0 && state != BNFA_FAIL_STATE )
          {
             if( isprint(i) )
               printf("%3c->%-5d\t",i,state);
             else
               printf("%3d->%-5d\t",i,state);
          }
       }
    }
#endif

   printf("\n");

   if( MatchList[k] )
       printf("---MatchList For State %d\n",k);

    for( mlist = MatchList[k];
         mlist!= NULL;
         mlist = mlist->next )
    {
	     bnfa_pattern_t * pat;
		 pat = (bnfa_pattern_t*)mlist->data;
         printf("---pattern : %.*s\n",pat->n,pat->casepatrn);
    }
  }
}

/*
*  Create a new AC state machine
*/ 
bnfa_struct_t * bnfaNew(void) 
{
  bnfa_struct_t * p;
  static int first=1;
  int bnfa_memory=0;

  if( first )
  {
      bnfaInitSummary();
      first=0;
  }
  
  init_xlatcase ();

  p = (bnfa_struct_t *) BNFA_MALLOC(sizeof(bnfa_struct_t),bnfa_memory);
  if(!p) 
	  return 0;

  if( p )
  {
     p->bnfaCaseMode           = BNFA_PER_PAT_CASE;
     p->bnfaFormat             = BNFA_SPARSE;
     p->bnfaAlphabetSize       = BNFA_MAX_ALPHABET_SIZE;
     p->bnfaForceFullZeroState = 1;
     p->bnfa_memory            = sizeof(bnfa_struct_t);
  }
  
  queue_memory = 0;
  return p;
}

void bnfaSetCase(bnfa_struct_t  * p, int flag)
{
   if( flag == BNFA_PER_PAT_CASE ) p->bnfaCaseMode = flag; 
   if( flag == BNFA_CASE    ) p->bnfaCaseMode = flag; 
   if( flag == BNFA_NOCASE  ) p->bnfaCaseMode = flag; 
}

/*
*   Fee all memory 
*/ 
void bnfaFree (bnfa_struct_t * bnfa) 
{
  int i;
  bnfa_pattern_t * patrn, *ipatrn;
  bnfa_match_node_t   * mlist, *ilist;

  for(i = 0; i < bnfa->bnfaNumStates; i++)
  {
      /* free match list entries */
      mlist = bnfa->bnfaMatchList[i];
      while (mlist)
      {
		ilist = mlist;
		mlist = mlist->next;
		BNFA_FREE(ilist,sizeof(bnfa_match_node_t),bnfa->matchlist_memory);
      }
      bnfa->bnfaMatchList[i] = 0;

#ifdef ALLOW_NFA_FULL
      /* free next state entries */
      if( bnfa->bnfaFormat==BNFA_FULL )/* Full format */
      {
         if( bnfa->bnfaNextState[i] )
		 {
            BNFA_FREE(bnfa->bnfaNextState[i],bnfa->bnfaAlphabetSize*sizeof(bnfa_state_t),bnfa->nextstate_memory);
		 }
      }
#endif
  }

  /* Free patterns */
  patrn = bnfa->bnfaPatterns;
  while(patrn)
  {
     ipatrn=patrn;
     patrn=patrn->next;
     BNFA_FREE(ipatrn->casepatrn,ipatrn->n,bnfa->pat_memory);
     BNFA_FREE(ipatrn,sizeof(bnfa_pattern_t),bnfa->pat_memory);
  }

  /* Free arrays */
  BNFA_FREE(bnfa->bnfaFailState,bnfa->bnfaNumStates*sizeof(bnfa_state_t),bnfa->failstate_memory);
  BNFA_FREE(bnfa->bnfaMatchList,bnfa->bnfaNumStates*sizeof(bnfa_pattern_t*),bnfa->matchlist_memory);
  BNFA_FREE(bnfa->bnfaNextState,bnfa->bnfaNumStates*sizeof(bnfa_state_t*),bnfa->nextstate_memory);
  BNFA_FREE(bnfa->bnfaTransList,(2*bnfa->bnfaNumStates+bnfa->bnfaNumTrans)*sizeof(bnfa_state_t*),bnfa->nextstate_memory);
  free( bnfa ); /* cannot update memory tracker when deleting bnfa so just 'free' it !*/
}

/*
*   Add a pattern to the pattern list
*/ 
int
bnfaAddPattern (bnfa_struct_t * p, 
		unsigned char *pat, 
                int n,
                int nocase,
		void * userdata )
{
  bnfa_pattern_t * plist;

  plist = (bnfa_pattern_t *)BNFA_MALLOC(sizeof(bnfa_pattern_t),p->pat_memory);
  if(!plist) return -1;

  plist->casepatrn = (unsigned char *)BNFA_MALLOC(n,p->pat_memory );
  if(!plist->casepatrn) return -1;
  
  memcpy (plist->casepatrn, pat, n);

  plist->n        = n;
  plist->nocase   = nocase;
  plist->userdata = userdata;
  
  plist->next     = p->bnfaPatterns; /* insert at front of list */
  p->bnfaPatterns = plist;

  p->bnfaPatternCnt++;

  return 0;
}

/*
*   Compile the patterns into an nfa state machine 
*/ 
int
bnfaCompile (bnfa_struct_t * bnfa) 
{
    bnfa_pattern_t  * plist;
    bnfa_match_node_t   ** tmpMatchList;
	unsigned          cntMatchStates;
	int               i;
    static int first=1;

    if( first )
    {
        bnfaInitSummary();
        first=0;
    }
	queue_memory =0;

    /* Count number of states */ 
    for(plist = bnfa->bnfaPatterns; plist != NULL; plist = plist->next)
    {
       bnfa->bnfaMaxStates += plist->n;
    }
    bnfa->bnfaMaxStates++; /* one extra */

    /* Alloc a List based State Transition table */
    bnfa->bnfaTransTable =(bnfa_trans_node_t**) BNFA_MALLOC(sizeof(bnfa_trans_node_t*) * bnfa->bnfaMaxStates,bnfa->list_memory );
    if(!bnfa->bnfaTransTable)
	{
		return -1;
	}

    /* Alloc a MatchList table - this has a list of pattern matches for each state */
    bnfa->bnfaMatchList=(bnfa_match_node_t**) BNFA_MALLOC(sizeof(void*)*bnfa->bnfaMaxStates,bnfa->matchlist_memory );
    if(!bnfa->bnfaMatchList)
	{
		return -1;
	}

    /* Add each Pattern to the State Table - This forms a keyword trie using lists */ 
    bnfa->bnfaNumStates = 0;
    for (plist = bnfa->bnfaPatterns; plist != NULL; plist = plist->next)
    {
        _bnfa_add_pattern_states (bnfa, plist);
    }
    bnfa->bnfaNumStates++;

    if( bnfa->bnfaNumStates > BNFA_SPARSE_MAX_STATE )
	{
		return -1;  /* Call bnfaFree to clean up */
	}

    /* ReAlloc a smaller MatchList table -  only need NumStates  */
    tmpMatchList=bnfa->bnfaMatchList;

    bnfa->bnfaMatchList=(bnfa_match_node_t**)BNFA_MALLOC(sizeof(void*) * bnfa->bnfaNumStates,bnfa->matchlist_memory);
    if(!bnfa->bnfaMatchList)
	{
		return -1;
	}
    
	memcpy(bnfa->bnfaMatchList,tmpMatchList,sizeof(void*) * bnfa->bnfaNumStates);
    
	BNFA_FREE(tmpMatchList,sizeof(void*) * bnfa->bnfaMaxStates,bnfa->matchlist_memory);

    /* Alloc a failure state table -  only need NumStates */
    bnfa->bnfaFailState =(bnfa_state_t*)BNFA_MALLOC(sizeof(bnfa_state_t) * bnfa->bnfaNumStates,bnfa->failstate_memory);
    if(!bnfa->bnfaFailState)
	{
		return -1;
	}

#ifdef ALLOW_NFA_FULL
    if( bnfa->bnfaFormat == BNFA_FULL )
	{
	  /* Alloc a state transition table -  only need NumStates  */
      bnfa->bnfaNextState=(bnfa_state_t**)BNFA_MALLOC(sizeof(bnfa_state_t*) * bnfa->bnfaNumStates,bnfa->nextstate_memory);
      if(!bnfa->bnfaNextState) 
	  {
		  return -1;
	  }
	}
#endif
	
    /* Build the nfa w/failure states - time the nfa construction */
    if( _bnfa_build_nfa (bnfa) ) 
	{
        return -1;
	}

    /* Convert nfa storage format from list to full or sparse */
    if( bnfa->bnfaFormat == BNFA_SPARSE )
    {
      if( _bnfa_conv_list_to_csparse_array(bnfa)  )
	  {
		  return -1;
	  }
      BNFA_FREE(bnfa->bnfaFailState,sizeof(bnfa_state_t)*bnfa->bnfaNumStates,bnfa->failstate_memory);
	  bnfa->bnfaFailState=0;
    }
#ifdef ALLOW_NFA_FULL
	else if( bnfa->bnfaFormat == BNFA_FULL )
    {
      if( _bnfa_conv_list_to_full( bnfa ) )
	  {
            return -1;
	  }
    }
#endif
	else
	{
		return -1;
	}

    /* Free up the Table Of Transition Lists */
    _bnfa_list_free_table( bnfa ); 

	/* Count states with Pattern Matches */
	cntMatchStates=0;
	for(i=0;i<bnfa->bnfaNumStates;i++)
	{
		if( bnfa->bnfaMatchList[i] )
			cntMatchStates++;
	}

	bnfa->bnfaMatchStates = cntMatchStates;
	bnfa->queue_memory    = queue_memory;

    bnfaAccumInfo( bnfa  );

    return 0;
}

#ifdef ALLOW_NFA_FULL

/*
*   Full Matrix Format Search
*/
static
inline
unsigned 
_bnfa_search_full_nfa(	bnfa_struct_t * bnfa, unsigned char *Tx, int n,
					int (*Match)(bnfa_pattern_t * id, int index, void *data), 
                    void *data, bnfa_state_t state, int *current_state ) 
{
  unsigned char      * Tend;
  unsigned char      * T;
  unsigned char        Tchar;
  unsigned            index;
  bnfa_state_t      ** NextState= bnfa->bnfaNextState;
  bnfa_state_t       * FailState= bnfa->bnfaFailState;
  bnfa_match_node_t ** MatchList= bnfa->bnfaMatchList;
  bnfa_state_t       * pc;
  bnfa_match_node_t  * mlist;
  bnfa_pattern_t     * patrn;
  unsigned             nfound = 0;
  int                  res;
  unsigned             last_match=LAST_STATE_INIT;
  unsigned             last_match_saved=LAST_STATE_INIT;
  
  T    = Tx;
  Tend = T + n;
 
  for( ; T < Tend; T++ )
  {
	Tchar = xlatcase[ *T ];

	for(;;)
	{
		pc = NextState[state];
		if( pc[Tchar] == 0 && state > 0 )
		{
			state = FailState[state];
		}
		else
		{
			state = pc[Tchar];
			break;
		}
	}

	if( state )
	{
        if( state == last_match )
            continue;
       
        last_match_saved=last_match;
        last_match = state;
        
    	for(	mlist = MatchList[state];
				mlist!= NULL;
				mlist = mlist->next )
    	{
		   		patrn = (bnfa_pattern_t*)mlist->data;
	
           		index = T - Tx - patrn->n + 1; 
       			if( patrn->nocase )
           		{
                    nfound++;
					res = Match (patrn, index, data);
					if ( res > 0 )
                    {
                        *current_state = state;
						return nfound;
                    }
                    if( res < 0 )
                    {
                        last_match=last_match_saved;
                    }
           		}
           		else
           		{
					if( memcmp (patrn->casepatrn, T - patrn->n + 1, patrn->n) == 0 )
					{
                        nfound++;
					    res = Match (patrn, index, data);
  						if ( res > 0 )
                        {
                            *current_state = state;
  							return nfound;
                        }
                        if( res < 0 )
                        {
                          last_match=last_match_saved;
                        }
					}
                    else
                    {
                          last_match=last_match_saved;
                    }
           		}
    	}
	}
  }
  return nfound;
}
/*
*   Full Matrix Format Search - Exact matching patterns only
*/
static
inline
unsigned 
_bnfa_search_full_nfa_case(	bnfa_struct_t * bnfa, unsigned char *Tx, int n,
					int (*Match)(bnfa_pattern_t * id, int index, void *data), 
                    void *data, bnfa_state_t state, int *current_state ) 
{
  unsigned char      * Tend;
  unsigned char      * T;
  unsigned char        Tchar;
  unsigned        index;
  bnfa_state_t      ** NextState= bnfa->bnfaNextState;
  bnfa_state_t       * FailState= bnfa->bnfaFailState;
  bnfa_match_node_t ** MatchList= bnfa->bnfaMatchList;
  bnfa_state_t       * pc;
  bnfa_match_node_t  * mlist;
  bnfa_pattern_t     * patrn;
  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 = *T ;

	for(;;)
	{
		pc = NextState[state];
		if( pc[Tchar] == 0 && state > 0 )
		{
			state = FailState[state];
		}
		else
		{
			state = pc[Tchar];
			break;
		}
	}

	if( state )
	{
        if( state == last_match )
            continue;
       
        last_match_saved=last_match;
        last_match = state;
    	
        for(	mlist = MatchList[state];
				mlist!= NULL;
				mlist = mlist->next )
    	{
		   		patrn = (bnfa_pattern_t*)mlist->data;
	
           		index = T - Tx - patrn->n + 1; 
                nfound++;
				res = Match (patrn, index, data);
			    if ( res > 0 )
                {
                     *current_state = state;
				     return nfound;
                }
                if( res < 0 )
                {
                    last_match=last_match_saved;
                }
    	}
	}
  }
  return nfound;
}
/*
*   Full Matrix Format Search - no case
*/
static
inline
unsigned 
_bnfa_search_full_nfa_nocase(	bnfa_struct_t * bnfa, unsigned char *Tx, int n,
					int (*Match)(bnfa_pattern_t * id, int index, void *data), 
                    void *data, bnfa_state_t state, int *current_state ) 
{
  unsigned char      * Tend;
  unsigned char      * T;
  unsigned char        Tchar;
  unsigned        index;
  bnfa_state_t      ** NextState= bnfa->bnfaNextState;
  bnfa_state_t       * FailState= bnfa->bnfaFailState;
  bnfa_match_node_t ** MatchList= bnfa->bnfaMatchList;
  bnfa_state_t       * pc;
  bnfa_match_node_t  * mlist;
  bnfa_pattern_t     * patrn;
  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 ];

	for(;;)
	{
		pc = NextState[state];
		if( pc[Tchar] == 0 && state > 0 )
		{
			state = FailState[state];
		}
		else
		{
			state = pc[Tchar];
			break;
		}
	}

	if( state )
	{
        if( state == last_match )
            continue;
       
        last_match_saved=last_match;
        last_match = state;
    
        for(	mlist = MatchList[state];
				mlist!= NULL;
				mlist = mlist->next )
    	{
		   		patrn = (bnfa_pattern_t*)mlist->data;
           		index = T - Tx - patrn->n + 1; 
                nfound++;