acsmx2.c

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

      return 0;
  }

  state = *current_state;


  for( ; T < Tend; T++ )
  {
      state = SparseGetNextStateDFA ( NextState[state], state, xlatcase[*T] );
      
      /* test if this state has any matching patterns */
      if( NextState[state][1] ) 
      {   
        for( mlist = MatchList[state];
             mlist!= NULL;
             mlist = mlist->next )
        {
             index = T - mlist->n - Tc + 1; 
             if( mlist->nocase )
             {
                nfound++;
                if (Match (mlist->id, index, data) > 0)
                {
                    *current_state = state;
                    return nfound;
                }
             }
             else
             {
                if( memcmp (mlist->casepatrn, Tx + index, mlist->n) == 0 )
                {
                    nfound++;
                    if (Match (mlist->id, index, data)> 0)
                    {
                        *current_state = state;
                        return nfound;
                    }
                }
             }
        }
      }
  }

  *current_state = state;

  return nfound;
}
/*
*   Full format DFA search
*   Do not change anything here without testing, caching and prefetching 
*   performance is very sensitive to any changes.
*
*   Perf-Notes: 
*    1) replaced ConvertCaseEx with inline xlatcase - this improves performance 5-10%
*    2) using 'nocase' improves performance again by 10-15%, since memcmp is not needed
*    3) 
*/
static 
inline
int
acsmSearchSparseDFA_Full(ACSM_STRUCT2 * acsm, unsigned char *Tx, int n,
            int (*Match) (void * id, int index, void *data), 
            void *data, int* current_state ) 
{
  ACSM_PATTERN2   * mlist;
  unsigned char   * Tend;
  unsigned char   * T;
  int               index;
  acstate_t         state;
  acstate_t       * ps; 
  acstate_t         sindex;
  acstate_t      ** NextState = acsm->acsmNextState;
  ACSM_PATTERN2  ** MatchList = acsm->acsmMatchList;
  int               nfound    = 0;

  T    = Tx;
  Tend = Tx + n;

  if ( !current_state )
  {
    return 0;
  }

  state = *current_state;

  for( ; T < Tend; T++ )
  {
      ps     = NextState[ state ];

      sindex = xlatcase[ T[0] ];

      /* check the current state for a pattern match */
      if( ps[1] ) 
      {   
        for( mlist = MatchList[state];
             mlist!= NULL;
             mlist = mlist->next )
        {
             index = T - mlist->n - Tx; 

             if( mlist->nocase )
             {
                nfound++;
                if (Match (mlist->id, index, data)>0)
                {
                    *current_state = state;
                    return nfound;
                }
             }
             else
             {
                if( memcmp (mlist->casepatrn, Tx + index, mlist->n ) == 0 )
                {
                    nfound++;
                    if (Match (mlist->id, index, data)>0)
                    {
                        *current_state = state;
                        return nfound;
                    }
                }
            }
        }
      }
      
      state = ps[ 2u + sindex ];
  }

  /* Check the last state for a pattern match */
  for( mlist = MatchList[state];
       mlist!= NULL;
       mlist = mlist->next )
  {
      index = T - mlist->n - Tx;

      if( mlist->nocase )
      {
        nfound++;
        if (Match (mlist->id, index, data)>0)
        {
            *current_state = state;
            return nfound;
        }
      }
      else
      {
        if( memcmp (mlist->casepatrn, Tx + index, mlist->n) == 0 )
        {
            nfound++;
            if (Match (mlist->id, index, data)>0)
            {
                *current_state = state;
                return nfound;
            } 
        }
      }
  }

  *current_state = state;
  return nfound;
}
/*
*   Banded-Row format DFA search
*   Do not change anything here, caching and prefetching 
*   performance is very sensitive to any changes.
*
*   ps[0] = storage fmt 
*   ps[1] = bool match flag
*   ps[2] = # elements in band 
*   ps[3] = index of 1st element
*/
static 
inline
int
acsmSearchSparseDFA_Banded(ACSM_STRUCT2 * acsm, unsigned char *Tx, int n,
            int (*Match) (void * id, int index, void *data), 
            void *data, int* current_state ) 
{
  acstate_t         state;
  unsigned char   * Tend;
  unsigned char   * T;
  int               sindex;
  int               index;
  acstate_t      ** NextState = acsm->acsmNextState;
  ACSM_PATTERN2  ** MatchList = acsm->acsmMatchList;
  ACSM_PATTERN2   * mlist;
  acstate_t       * ps; 
  int               nfound = 0;

  T    = Tx;
  Tend = T + n;

  if ( !current_state )
  {
    return 0;
  }

  state = *current_state;

  for( ; T < Tend; T++ )
  {
      ps     = NextState[state];
      
      sindex = xlatcase[ T[0] ];
            
      /* test if this state has any matching patterns */
      if( ps[1] ) 
      {   
        for( mlist = MatchList[state];
             mlist!= NULL;
             mlist = mlist->next )
        {
             index = T - mlist->n - Tx; 

             if( mlist->nocase )
             {
                nfound++;
                if (Match (mlist->id, index, data)>0)
                {
                    *current_state = state;
                    return nfound;
                }
             }
             else
             {
                if( memcmp (mlist->casepatrn, Tx + index, mlist->n) == 0 )
                {
                    nfound++;
                    if (Match (mlist->id, index, data)>0)
                    {
                        *current_state = state;
                        return nfound;
                    }
                }
             }
        }
      }
      
      if(      sindex <   ps[3]          )  state = 0;
      else if( sindex >= (ps[3] + ps[2]) )  state = 0; 
      else                                  state = ps[ 4u + sindex - ps[3] ];
  }

  /* Check the last state for a pattern match */
  for( mlist = MatchList[state];
       mlist!= NULL;
       mlist = mlist->next )
  {
      index = T - mlist->n - Tx; 

      if( mlist->nocase )
      {
        nfound++;
        if (Match (mlist->id, index, data)>0)
        {
            *current_state = state;
            return nfound;
        }
      }
      else
      {
        if( memcmp (mlist->casepatrn, Tx + index, mlist->n) == 0 )
        {
          nfound++;
          if (Match (mlist->id, index, data)>0)
          {
            *current_state = state;
            return nfound;
          }
        }
      }
  }

  return nfound;
}



/*
*   Search Text or Binary Data for Pattern matches
*
*   Sparse Storage Version
*/
static
inline
int
acsmSearchSparseNFA(ACSM_STRUCT2 * acsm, unsigned char *Tx, int n,
            int (*Match) (void * id, int index, void *data), 
            void *data, int* current_state ) 
{
  acstate_t         state;
  ACSM_PATTERN2   * mlist;
  unsigned char   * Tend;
  int               nfound = 0;
  unsigned char   * T;
  int               index;
  acstate_t      ** NextState= acsm->acsmNextState;
  acstate_t       * FailState= acsm->acsmFailState;
  ACSM_PATTERN2  ** MatchList = acsm->acsmMatchList;
  unsigned char     Tchar;

  T    = Tx;
  Tend = T + n;

  if ( !current_state )
  {
    return 0;
  }

  state = *current_state;

  for( ; T < Tend; T++ )
  {
      acstate_t nstate;

      Tchar = xlatcase[ *T ];

      while( (nstate=SparseGetNextStateNFA(NextState[state],state,Tchar))==ACSM_FAIL_STATE2 )
              state = FailState[state];

      state = nstate;

      for( mlist = MatchList[state];
           mlist!= NULL;
           mlist = mlist->next )
      {
           index = T - mlist->n - Tx; 
           if( mlist->nocase )
           {
              nfound++;
              if (Match (mlist->id, index, data)>0)
              {
                  *current_state = state;
                  return nfound;
              }
           }
           else
           {
              if( memcmp (mlist->casepatrn, Tx + index, mlist->n) == 0 )
              {
                nfound++;
                if (Match (mlist->id, index, data)>0)
                {
                    *current_state = state;
                    return nfound;
                }
              }
           }
      }
  }

  return nfound;
}

/*
*   Search Function
*/
int 
acsmSearch2(ACSM_STRUCT2 * acsm, unsigned char *Tx, int n,
           int (*Match) (void * id, int index, void *data), 
           void *data, int* current_state ) 
{

   switch( acsm->acsmFSA )
   {
       case FSA_DFA:

       if( acsm->acsmFormat == ACF_FULL )
       {
         return acsmSearchSparseDFA_Full( acsm, Tx, n, Match, data, 
                current_state );
       }
       else if( acsm->acsmFormat == ACF_BANDED )
       {
         return acsmSearchSparseDFA_Banded( acsm, Tx, n, Match, data,
                current_state );
       }
       else
       {
         return acsmSearchSparseDFA( acsm, Tx, n, Match, data, 
                current_state );
       }

       case FSA_NFA:

         return acsmSearchSparseNFA( acsm, Tx, n, Match, data, 
                current_state );

       case FSA_TRIE:

         return 0;
   }
  return 0;
}


/*
*   Free all memory
*/ 
  void
acsmFree2 (ACSM_STRUCT2 * acsm) 
{
  int i;
  ACSM_PATTERN2 * mlist, *ilist;
  for (i = 0; i < acsm->acsmMaxStates; i++)
  {
      mlist = acsm->acsmMatchList[i];

      while (mlist)
      {
          ilist = mlist;
          mlist = mlist->next;
          AC_FREE (ilist);
      }
          AC_FREE(acsm->acsmNextState[i]);
  }
  AC_FREE(acsm->acsmFailState);
  AC_FREE(acsm->acsmMatchList);
}

/*
*
*/
void acsmPrintInfo2( ACSM_STRUCT2 * p)
{
    char * sf[]={
      "Full Matrix",
      "Sparse Matrix",
      "Banded Matrix",
      "Sparse Banded Matrix",
    };
    char * fsa[]={
      "TRIE",
      "NFA",
      "DFA",
    };


    printf("+--[Pattern Matcher:Aho-Corasick]-----------------------------\n");
    printf("| Alphabet Size    : %d Chars\n",p->acsmAlphabetSize);
    printf("| Sizeof State     : %d bytes\n",(int)(sizeof(acstate_t)));
    printf("| Storage Format   : %s \n",sf[ p->acsmFormat ]);
    printf("| Sparse Row Nodes : %d Max\n",p->acsmSparseMaxRowNodes);
    printf("| Sparse Band Zeros: %d Max\n",p->acsmSparseMaxZcnt);
    printf("| Num States       : %d\n",p->acsmNumStates);
    printf("| Num Transitions  : %d\n",p->acsmNumTrans);
    printf("| State Density    : %.1f%%\n",100.0*(double)p->acsmNumTrans/(p->acsmNumStates*p->acsmAlphabetSize));
    printf("| Finite Automatum : %s\n", fsa[p->acsmFSA]);
    if( max_memory < 1024*1024 )
    printf("| Memory           : %.2fKbytes\n", (float)max_memory/1024 );
    else
    printf("| Memory           : %.2fMbytes\n", (float)max_memory/(1024*1024) );
    printf("+-------------------------------------------------------------\n");

    /* Print_DFA(acsm); */

}

/*
 *
 */
int acsmPrintDetailInfo2( ACSM_STRUCT2 * p )
{

    return 0;
}

/*
 *   Global sumary of all info and all state machines built during this run
 *   This feeds off of the last pattern groupd built within snort,
 *   all groups use the same format, state size, etc..
 *   Combined with accrued stats, we get an average picture of things.
 */
int acsmPrintSummaryInfo2()
{
    char * sf[]={
      "Full",
      "Sparse",
      "Banded",
      "Sparse-Bands",
    };

    char * fsa[]={
      "TRIE",
      "NFA",
      "DFA",
    };

    ACSM_STRUCT2 * p = &summary.acsm;

    if( !summary.num_states )
        return 0;
    
    printf("+--[Pattern Matcher:Aho-Corasick Summary]----------------------\n");
    printf("| Alphabet Size    : %d Chars\n",p->acsmAlphabetSize);
    printf("| Sizeof State     : %d bytes\n",(int)(sizeof(acstate_t)));
    printf("| Storage Format   : %s \n",sf[ p->acsmFormat ]);
    printf("| Num States       : %d\n",summary.num_states);
    printf("| Num Transitions  : %d\n",summary.num_transitions);
    printf("| State Density    : %.1f%%\n",100.0*(double)summary.num_transitions/(summary.num_states*p->acsmAlphabetSize));
    printf("| Finite Automatum : %s\n", fsa[p->acsmFSA]);
    if( max_memory < 1024*1024 )
    printf("| Memory           : %.2fKbytes\n", (float)max_memory/1024 );
    else
    printf("| Memory           : %.2fMbytes\n", (float)max_memory/(1024*1024) );
    printf("+-------------------------------------------------------------\n");


    return 0;
}




#ifdef ACSMX2S_MAIN
  
/*
*  Text Data Buffer
*/ 
unsigned char text[512];

/* 
*    A Match is found
*/ 
 int
MatchFound (void* id, int index, void *data) 
{
  fprintf (stdout, "%s\n", (char *) id);
  return 0;
}

/*
*
*/ 
int
main (int argc, char **argv) 
{
  int i, nc, nocase = 0;
  ACSM_STRUCT2 * acsm;
  char * p;

  if (argc < 3)
    
    {
      fprintf (stderr,"Usage: %s search-text pattern +pattern... [flags]\n",argv[0]);
      fprintf (stderr,"  flags: -nfa -nocase -full -sparse -bands -sparsebands -z zcnt (sparsebands) -sparsetree -v\n");
      exit (0);
    }

  acsm = acsmNew2 ();
  if( !acsm )
  {
     printf("acsm-no memory\n");
     exit(0);
  }

  strncpy (text, argv[1], sizeof(text) - 1);
  text[sizeof(text) - 1] = '\0';

  acsm->acsmFormat = ACF_FULL;

  for (i = 1; i < argc; i++)
  {
    if (strcmp (argv[i], "-nocase") == 0){
      nocase = 1;
    }
    if (strcmp (argv[i], "-v") == 0){
      s_verbose=1;
    }

    if (strcmp (argv[i], "-full") == 0){
       acsm->acsmFormat            = ACF_FULL;
    }
    if (strcmp (argv[i], "-sparse") == 0){
       acsm->acsmFormat            = ACF_SPARSE;
       acsm->acsmSparseMaxRowNodes = 10;
    }
    if (strcmp (argv[i], "-bands") == 0){
       acsm->acsmFormat            = ACF_BANDED;
    }

    if (strcmp (argv[i], "-sparsebands") == 0){
       acsm->acsmFormat            = ACF_SPARSEBANDS;
       acsm->acsmSparseMaxZcnt     = 10;  
    }
    if (strcmp (argv[i], "-z") == 0){
       acsm->acsmSparseMaxZcnt     = atoi(argv[++i]);  
    }

    if (strcmp (argv[i], "-nfa") == 0){
       acsm->acsmFSA     = FSA_NFA;
    }
    if (strcmp (argv[i], "-dfa") == 0){
       acsm->acsmFSA     = FSA_DFA;
    }
    if (strcmp (argv[i], "-trie") == 0){
       acsm->acsmFSA     = FSA_TRIE;
    }
  }

  for (i = 2; i < argc; i++)
  {
      if (argv[i][0] == '-')
          continue;

      p = argv[i];

      if ( *p == '+')
      {
          nc=1;
          p++;
      }
      else
      {
          nc = nocase;
      }

      acsmAddPattern2 (acsm, p, strlen(p), nc, 0, 0,(void*)p, i - 2);
  }
  
  if(s_verbose)printf("Patterns added\n");

  Print_DFA (acsm);

  acsmCompile2 (acsm);

  Write_DFA(acsm, "acsmx2-snort.dfa") ;

  if(s_verbose) printf("Patterns compiled--written to file.\n");

  acsmPrintInfo2 ( acsm );

  acsmSearch2 (acsm, text, strlen (text), MatchFound, (void *)0 );

  acsmFree2 (acsm);

  printf ("normal pgm end\n");

  return (0);
}
#endif /*  */