acsmx2.c

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

    case ACF_SPARSEBANDS:
    {
       nb  =  ps[2]; /* number of bands */
      
       ps += 3;

       while( nb > 0 )  /* for each band */
       { 
          n     = ps[0];  /* number of elements in this band */
          index = ps[1];  /* start index/char of this band */
          if( input <  index )
          {
            return (acstate_t)0;
          }
          if( (input < (index + n)) )  
          {
            return (acstate_t) ps[2+input-index];
          }
          nb--;
          ps += n;
       }
       return (acstate_t)0;
    } 
  }

  return 0;
}
/*
*   Search Text or Binary Data for Pattern matches
*
*   Sparse & Sparse-Banded Matrix search
*/
static
inline
int
acsmSearchSparseDFA(ACSM_STRUCT2 * acsm, unsigned char *Tx, int n,
	    int (*Match) (void * id, int index, void *data), 
            void *data) 
{
  acstate_t state;
  ACSM_PATTERN2   * mlist;
  unsigned char   * Tend;
  int               nfound = 0;
  unsigned char   * T, * Tc;
  int               index;
  acstate_t      ** NextState = acsm->acsmNextState; 
  ACSM_PATTERN2  ** MatchList = acsm->acsmMatchList;

  Tc   = Tx;
  T    = Tx;
  Tend = T + n;
 
  for( state = 0; 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; 
	         if( mlist->nocase )
		 {
		    nfound++;
		    if (Match (mlist->id, index, data))
		        return nfound;
		 }
	         else
		 {
		    if( memcmp (mlist->casepatrn, Tx + index, mlist->n) == 0 )
		    {
		      nfound++;
		      if (Match (mlist->id, index, data))
	  		  return nfound;
		    }
		 }
	    }
      }
  }
  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) 
{
  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;
 
  for( state = 0; 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))
		        return nfound;
		 }
	         else
		 {
		    if( memcmp (mlist->casepatrn, Tx + index, mlist->n ) == 0 )
		    {
		      nfound++;
		      if (Match (mlist->id, index, data))
	  		  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))
	        return nfound;
       }
       else
       {
	    if( memcmp (mlist->casepatrn, Tx + index, mlist->n) == 0 )
	    {
	      nfound++;
  	      if (Match (mlist->id, index, data))
  		  return nfound;
	    }
       }
  }

  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) 
{
  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;
 
  for( state = 0; 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))
		        return nfound;
		 }
	         else
		 {
		    if( memcmp (mlist->casepatrn, Tx + index, mlist->n) == 0 )
		    {
		      nfound++;
		      if (Match (mlist->id, index, data))
	  		  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))
	        return nfound;
       }
       else
       {
	    if( memcmp (mlist->casepatrn, Tx + index, mlist->n) == 0 )
	    {
	      nfound++;
  	      if (Match (mlist->id, index, data))
  		  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) 
{
  acstate_t         state;
  ACSM_PATTERN2   * mlist;
  unsigned char   * Tend;
  int               nfound = 0;
  unsigned char   * T, *Tc;
  int               index;
  acstate_t      ** NextState= acsm->acsmNextState;
  acstate_t       * FailState= acsm->acsmFailState;
  ACSM_PATTERN2  ** MatchList = acsm->acsmMatchList;
  unsigned char     Tchar;

  Tc   = Tx;
  T    = Tx;
  Tend = T + n;
 
  for( state = 0; 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))
	          return nfound;
           }
           else
           {
	      if( memcmp (mlist->casepatrn, Tx + index, mlist->n) == 0 )
	      {
	        nfound++;
  	        if (Match (mlist->id, index, data))
  		  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) 
{

   switch( acsm->acsmFSA )
   {
       case FSA_DFA:

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

       case FSA_NFA:

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

       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",
    };

    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);
  }

  strcpy (text, argv[1]);

  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 /*  */