acsmx2.c

linux下IDS软件,来源于snort社团.

       fwrite(  p, sizeof(acstate_t), n, fp);
    }
    else if( fmt ==ACF_SPARSEBANDS )
    {
       nb    = *p++; 
       fwrite( &nb,    sizeof(acstate_t), 1, fp);
       for(i=0;i<nb;i++)
       {
         n     = *p++;
         fwrite( &n,    sizeof(acstate_t), 1, fp);

         index = *p++;
         fwrite( &index,sizeof(acstate_t), 1, fp);

         fwrite( p,     sizeof(acstate_t), 1, fp);
       }
    }
    else if( fmt == ACF_FULL ) 
    {
      fwrite( p,  sizeof(acstate_t), acsm->acsmAlphabetSize,  fp);
    }

    //Print_DFA_MatchList( acsm, k);

  }

  fclose(fp);
}
*/

/*
*
*   Convert an NFA or DFA row from sparse to full format
*   and store into the 'full'  buffer.
*
*   returns:
*     0 - failed, no state transitions
*    *p - pointer to 'full' buffer
*
*/
/*
static 
acstate_t * acsmConvToFull(ACSM_STRUCT2 * acsm, acstate_t k, acstate_t * full )
{
    int i;
    acstate_t * p, n, fmt, index, nb, bmatch;
    acstate_t ** NextState = acsm->acsmNextState;

    p   = NextState[k];

    if( !p ) return 0;

    fmt = *p++; 

    bmatch = *p++;

    if( fmt ==ACF_SPARSE )
    {
       n = *p++; 
       for( ; n>0; n--, p+=2 )
       { 
         full[ p[0] ] = p[1];
      }
    }
    else if( fmt ==ACF_BANDED )
    {

       n = *p++; 
       index = *p++;

       for( ; n>0; n--, p++ )
       { 
         full[ index++ ] = p[0];
      }
    }
    else if( fmt ==ACF_SPARSEBANDS )
    {
       nb    = *p++; 
       for(i=0;i<nb;i++)
       {
         n     = *p++;
         index = *p++;
         for( ; n>0; n--, p++ )
         { 
           full[ index++ ] = p[0];
         }
       }
    }
    else if( fmt == ACF_FULL )
    {
      memcpy(full,p,acsm->acsmAlphabetSize*sizeof(acstate_t));
    }
    
    return full;   
}
*/

/*
*   Select the desired storage mode
*/
int acsmSelectFormat2( ACSM_STRUCT2 * acsm, int m )
{
 switch( m )
 {
    case ACF_FULL:
    case ACF_SPARSE:
    case ACF_BANDED:
    case ACF_SPARSEBANDS:
      acsm->acsmFormat = m;
      break;
    default:
      return -1;
 }

 return 0;
}
/*
*
*/
void acsmSetMaxSparseBandZeros2( ACSM_STRUCT2 * acsm, int n )
{
    acsm->acsmSparseMaxZcnt = n;  
}
/*
*
*/
void acsmSetMaxSparseElements2( ACSM_STRUCT2 * acsm, int n )
{
    acsm->acsmSparseMaxRowNodes = n;
}
/*
*    
*/
int acsmSelectFSA2( ACSM_STRUCT2 * acsm, int m )
{
 switch( m )
 {
    case FSA_TRIE:
    case FSA_NFA:
    case FSA_DFA:
      acsm->acsmFSA = m;
    default:
      return -1;
 }
}
/*
*    
*/
int acsmSetAlphabetSize2( ACSM_STRUCT2 * acsm, int n )
{
   if( n <= MAX_ALPHABET_SIZE )
   {
     acsm->acsmAlphabetSize = n;
   }
   else
   {
      return -1;
   }
   return 0;
}
/*
*  Create a new AC state machine
*/ 
ACSM_STRUCT2 * acsmNew2 () 
{
  ACSM_STRUCT2 * p;

  init_xlatcase ();

  p = (ACSM_STRUCT2 *) AC_MALLOC(sizeof (ACSM_STRUCT2));
  MEMASSERT (p, "acsmNew");

  if (p)
  {
    memset (p, 0, sizeof (ACSM_STRUCT2));

    /* Some defaults */
    p->acsmFSA               = FSA_DFA;
    p->acsmFormat            = ACF_FULL;//ACF_BANDED;
    p->acsmAlphabetSize      = 256;
    p->acsmSparseMaxRowNodes = 256;
    p->acsmSparseMaxZcnt     = 10;  
  }
  
  return p;
}
/*
*   Add a pattern to the list of patterns for this state machine
*
*/ 
int
acsmAddPattern2 (ACSM_STRUCT2 * p, unsigned char *pat, int n, int nocase,
		int offset, int depth, void * id, int iid) 
{
  ACSM_PATTERN2 * plist;

  plist = (ACSM_PATTERN2 *) AC_MALLOC (sizeof (ACSM_PATTERN2));
  MEMASSERT (plist, "acsmAddPattern");

  plist->patrn = (unsigned char *) AC_MALLOC ( n );
  MEMASSERT (plist->patrn, "acsmAddPattern");

  ConvertCaseEx(plist->patrn, pat, n);
  
  plist->casepatrn = (unsigned char *) AC_MALLOC ( n );
  MEMASSERT (plist->casepatrn, "acsmAddPattern");
  
  memcpy (plist->casepatrn, pat, n);

  plist->n      = n;
  plist->nocase = nocase;
  plist->offset = offset;
  plist->depth  = depth;
  plist->id     = id;
  plist->iid    = iid;

  plist->next     = p->acsmPatterns;
  p->acsmPatterns = plist;

  return 0;
}
/*
*   Add a Key to the list of key+data pairs
*/ 
int acsmAddKey2(ACSM_STRUCT2 * p, unsigned char *key, int klen, int nocase, void * data)
{
  ACSM_PATTERN2 * plist;

  plist = (ACSM_PATTERN2 *) AC_MALLOC (sizeof (ACSM_PATTERN2));
  MEMASSERT (plist, "acsmAddPattern");
 
  plist->patrn = (unsigned char *) AC_MALLOC (klen);
  memcpy (plist->patrn, key, klen);

  plist->casepatrn = (unsigned char *) AC_MALLOC (klen);
  memcpy (plist->casepatrn, key, klen);

  plist->n      = klen;
  plist->nocase = nocase;
  plist->offset = 0;
  plist->depth  = 0;
  plist->id     = 0;
  plist->iid = 0;

  plist->next = p->acsmPatterns;
  p->acsmPatterns = plist;

  return 0;
}

/*
*  Copy a boolean match flag int NextState table, for caching purposes.
*/
static
void acsmUpdateMatchStates( ACSM_STRUCT2 * acsm )
{
  acstate_t        state;
  acstate_t     ** NextState = acsm->acsmNextState;
  ACSM_PATTERN2 ** MatchList = acsm->acsmMatchList;

  for( state=0; state<acsm->acsmNumStates; state++ )
  {
     if( MatchList[state] )
     {
         NextState[state][1] = 1;
     }
     else 
     {
         NextState[state][1] = 0;
     }
  }
}

/*
*   Compile State Machine - NFA or DFA and Full or Banded or Sparse or SparseBands
*/ 
int
acsmCompile2 (ACSM_STRUCT2 * acsm) 
{
    int               k;
    ACSM_PATTERN2    * plist;
  
    /* Count number of states */ 
    for (plist = acsm->acsmPatterns; plist != NULL; plist = plist->next)
    {
     acsm->acsmMaxStates += plist->n;
     /* acsm->acsmMaxStates += plist->n*2; if we handle case in the table */
    }
    acsm->acsmMaxStates++; /* one extra */

    /* Alloc a List based State Transition table */
    acsm->acsmTransTable =(trans_node_t**) AC_MALLOC(sizeof(trans_node_t*) * acsm->acsmMaxStates );
    MEMASSERT (acsm->acsmTransTable, "acsmCompile");

    memset (acsm->acsmTransTable, 0, sizeof(trans_node_t*) * acsm->acsmMaxStates);

    if(s_verbose)printf ("ACSMX-Max Memory-TransTable Setup: %d bytes, %d states, %d active states\n", max_memory,acsm->acsmMaxStates,acsm->acsmNumStates);

    /* Alloc a failure table - this has a failure state, and a match list for each state */
    acsm->acsmFailState =(acstate_t*) AC_MALLOC(sizeof(acstate_t) * acsm->acsmMaxStates );
    MEMASSERT (acsm->acsmFailState, "acsmCompile");

    memset (acsm->acsmFailState, 0, sizeof(acstate_t) * acsm->acsmMaxStates );

    /* Alloc a MatchList table - this has a lis tof pattern matches for each state, if any */
    acsm->acsmMatchList=(ACSM_PATTERN2**) AC_MALLOC(sizeof(ACSM_PATTERN2*) * acsm->acsmMaxStates );
    MEMASSERT (acsm->acsmMatchList, "acsmCompile");

    memset (acsm->acsmMatchList, 0, sizeof(ACSM_PATTERN2*) * acsm->acsmMaxStates );

    if(s_verbose)printf ("ACSMX-Max Memory- MatchList Table Setup: %d bytes, %d states, %d active states\n", max_memory,acsm->acsmMaxStates,acsm->acsmNumStates);
 
    /* Alloc a separate state transition table == in state 's' due to event 'k', transition to 'next' state */
    acsm->acsmNextState=(acstate_t**)AC_MALLOC( acsm->acsmMaxStates * sizeof(acstate_t*) );
    MEMASSERT(acsm->acsmNextState, "acsmCompile-NextState");

    for (k = 0; k < acsm->acsmMaxStates; k++)
    {
      acsm->acsmNextState[k]=(acstate_t*)0;
    }

    if(s_verbose)printf ("ACSMX-Max Memory-Table Setup: %d bytes, %d states, %d active states\n", max_memory,acsm->acsmMaxStates,acsm->acsmNumStates);
     
    /* Initialize state zero as a branch */ 
    acsm->acsmNumStates = 0;
  
    /* Add the 0'th state,  */
    //acsm->acsmNumStates++; 
 
    /* Add each Pattern to the State Table - This forms a keywords state table  */ 
    for (plist = acsm->acsmPatterns; plist != NULL; plist = plist->next)
    {
        AddPatternStates (acsm, plist);
    }

    acsm->acsmNumStates++;

    if(s_verbose)printf ("ACSMX-Max Trie List Memory : %d bytes, %d states, %d active states\n", 
                 max_memory,acsm->acsmMaxStates,acsm->acsmNumStates);

    if(s_verbose)List_PrintTransTable( acsm );
  
    if( acsm->acsmFSA == FSA_DFA || acsm->acsmFSA == FSA_NFA )
    {
      /* Build the NFA */
      if(s_verbose)printf("Build_NFA\n");

      Build_NFA (acsm);

      if(s_verbose)printf("NFA-Trans-Nodes: %d\n",acsm->acsmNumTrans);
      if(s_verbose)printf("ACSMX-Max NFA List Memory  : %d bytes, %d states / %d active states\n", max_memory,acsm->acsmMaxStates,acsm->acsmNumStates);

      if(s_verbose)List_PrintTransTable( acsm );
    }
  
    if( acsm->acsmFSA == FSA_DFA )
    {
       /* Convert the NFA to a DFA */ 
       if(s_verbose)printf("Convert_NFA_To_DFA\n");

       Convert_NFA_To_DFA (acsm);
  
       if(s_verbose)printf("DFA-Trans-Nodes: %d\n",acsm->acsmNumTrans);
       if(s_verbose)printf("ACSMX-Max NFA-DFA List Memory  : %d bytes, %d states / %d active states\n", max_memory,acsm->acsmMaxStates,acsm->acsmNumStates);

       if(s_verbose)List_PrintTransTable( acsm );
    }

    /*
    *
    *  Select Final Transition Table Storage Mode
    *
    */

    if(s_verbose)printf("Converting Transition Lists -> Transition table, fmt=%d\n",acsm->acsmFormat);

    if( acsm->acsmFormat == ACF_SPARSE )
    {
      /* Convert DFA Full matrix to a Sparse matrix */
      if( Conv_Full_DFA_To_Sparse(acsm) )
          return -1;
   
      if(s_verbose)printf ("ACSMX-Max Memory-Sparse: %d bytes, %d states, %d active states\n", max_memory,acsm->acsmMaxStates,acsm->acsmNumStates);
      if(s_verbose)Print_DFA(acsm);
    }

    else if( acsm->acsmFormat == ACF_BANDED )
    {
      /* Convert DFA Full matrix to a Sparse matrix */
      if( Conv_Full_DFA_To_Banded(acsm) )
          return -1;
   
       if(s_verbose)printf ("ACSMX-Max Memory-banded: %d bytes, %d states, %d active states\n", max_memory,acsm->acsmMaxStates,acsm->acsmNumStates);
       if(s_verbose)Print_DFA(acsm);
    }

    else if( acsm->acsmFormat == ACF_SPARSEBANDS )
    {
      /* Convert DFA Full matrix to a Sparse matrix */
      if( Conv_Full_DFA_To_SparseBands(acsm) )
          return -1;
   
       if(s_verbose)printf ("ACSMX-Max Memory-sparse-bands: %d bytes, %d states, %d active states\n", max_memory,acsm->acsmMaxStates,acsm->acsmNumStates);
       if(s_verbose)Print_DFA(acsm);
    }
    else if( acsm->acsmFormat == ACF_FULL )
    {
      if( Conv_List_To_Full( acsm ) )
            return -1;

       if(s_verbose)printf ("ACSMX-Max Memory-Full: %d bytes, %d states, %d active states\n", max_memory,acsm->acsmMaxStates,acsm->acsmNumStates);
       if(s_verbose)Print_DFA(acsm);
    }

    acsmUpdateMatchStates( acsm ); /* load boolean match flags into state table */

    /* Free up the Table Of Transition Lists */
    List_FreeTransTable( acsm ); 

    if(s_verbose)printf ("ACSMX-Max Memory-Final: %d bytes, %d states, %d active states\n", max_memory,acsm->acsmMaxStates,acsm->acsmNumStates);

    /* For now -- show this info */
    /*
    *  acsmPrintInfo( acsm );
    */


    /* Accrue Summary State Stats */
    summary.num_states      += acsm->acsmNumStates;
    summary.num_transitions += acsm->acsmNumTrans;

    memcpy( &summary.acsm, acsm, sizeof(ACSM_STRUCT2));
    
    return 0;
}

/*
*   Get the NextState from the NFA, all NFA storage formats use this
*/
inline 
acstate_t SparseGetNextStateNFA(acstate_t * ps, acstate_t state, unsigned  input)
{
   acstate_t fmt;
   acstate_t n;
   int       index;
   int       nb;

   fmt = *ps++;

   ps++;  /* skip bMatchState */
   
   switch( fmt )
   {
    case  ACF_BANDED:
    {
     n     = ps[0];
     index = ps[1];

     if( input <  index     )  
     {
         if(state==0)
         {
           return 0; 
         }
         else
         { 
           return (acstate_t)ACSM_FAIL_STATE2;
         }
     }
     if( input >= index + n )
     {  
          if(state==0)
          {
              return 0; 
          }
          else 
          {
              return (acstate_t)ACSM_FAIL_STATE2;
          }
     }
     if( ps[input-index] == 0  ) 
     {
         if( state != 0 ) 
         {
           return ACSM_FAIL_STATE2;  
         }
     }

     return (acstate_t) ps[input-index];
    } 

    case ACF_SPARSE:
    {
     n = *ps++; /* number of sparse index-value entries */

     for( ; n>0 ; n-- )
     {
       if( ps[0] > input ) /* cannot match the input, already a higher value than the input  */
       {
           return (acstate_t)ACSM_FAIL_STATE2; /* default state */
       }
       else if( ps[0] == input )
       {
           return ps[1]; /* next state */
       }
       ps+=2;
     }
     if( state == 0 )
     {
	 return 0;
     }
     return ACSM_FAIL_STATE2;
    } 

    case ACF_SPARSEBANDS:
    {
     nb  = *ps++;   /* number of bands */

     while( nb > 0 )  /* for each band */
     { 
       n     = *ps++;  /* number of elements */
       index = *ps++;  /* 1st element value */

       if( input <  index )
       {
           if( state != 0 ) 
	   {
               return (acstate_t)ACSM_FAIL_STATE2;
	   }
           return (acstate_t)0;
       }
       if( (input >=  index) && (input < (index + n)) )  
       {
           if( ps[input-index] == 0 )
           {
               if( state != 0 ) 
	       {
                   return ACSM_FAIL_STATE2;
	       }
           }
           return (acstate_t) ps[input-index];
       }
       nb--;
       ps += n;
     }
     if( state != 0 )
     {
       return (acstate_t)ACSM_FAIL_STATE2;
     }
     return (acstate_t)0;
    } 

    case ACF_FULL:
    {
      if( ps[input] == 0 )
      {
        if( state != 0 ) 
	{
            return ACSM_FAIL_STATE2; 
	}
      }
      return ps[input]; 
    }
  }

  return 0;
}



/*
*   Get the NextState from the DFA Next State Transition table
*   Full and banded are supported separately, this is for 
*   sparse and sparse-bands
*/
inline 
acstate_t SparseGetNextStateDFA(acstate_t * ps, acstate_t state, unsigned  input)
{
   acstate_t  n, nb;
   int        index;

   switch( ps[0] )  
   {
    /*   BANDED   */
    case  ACF_BANDED:
    {
       /* n=ps[2] : number of entries in the band */
       /* index=ps[3] : index of the 1st entry, sequential thereafter */

       if( input  <  ps[3]        )  return 0; 
       if( input >= (ps[3]+ps[2]) )  return 0; 

       return  ps[4+input-ps[3]];
    } 

    /*   FULL   */
    case ACF_FULL:
    {
       return ps[2+input]; 
    }

    /*   SPARSE   */
    case ACF_SPARSE:
    {
       n = ps[2]; /* number of entries/ key+next pairs */
        
       ps += 3;
  
       for( ; n>0 ; n-- )  
       {
          if( input < ps[0]  ) /* cannot match the input, already a higher value than the input  */
          {
            return (acstate_t)0; /* default state */
          }
          else if( ps[0] == input )
          {
            return ps[1]; /* next state */
          }
          ps += 2;
       }
       return (acstate_t)0;
    } 


    /*   SPARSEBANDS   */