acsmx.c

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

}


/*
*   Build Deterministic Finite Automata from NFA
*/ 
static void
Convert_NFA_To_DFA (ACSM_STRUCT * acsm) 
{
  int r, s;
  int i;
  QUEUE q, *queue = &q;
  
    /* Init a Queue */ 
    queue_init (queue);
  
    /* Add the state 0 transitions 1st */ 
    for (i = 0; i < ALPHABET_SIZE; i++)
    {
      s = acsm->acsmStateTable[0].NextState[i];
      if (s)
      {
        queue_add (queue, s);
      }
    }
  
    /* Start building the next layer of transitions */ 
    while (queue_count (queue) > 0)
    {
      r = queue_remove (queue);
      
      /* State is a branch state */ 
      for (i = 0; i < ALPHABET_SIZE; i++)
      {
        if ((s = acsm->acsmStateTable[r].NextState[i]) != ACSM_FAIL_STATE)
        {
            queue_add (queue, s);
        }
        else
        {
            acsm->acsmStateTable[r].NextState[i] =
            acsm->acsmStateTable[acsm->acsmStateTable[r].FailState].
            NextState[i];
        }
      }
    }
  
    /* Clean up the queue */ 
    queue_free (queue);
}


/*
*
*/ 
ACSM_STRUCT * acsmNew () 
{
  ACSM_STRUCT * p;
  init_xlatcase ();
  p = (ACSM_STRUCT *) AC_MALLOC (sizeof (ACSM_STRUCT));
  MEMASSERT (p, "acsmNew");
  if (p)
    memset (p, 0, sizeof (ACSM_STRUCT));
  return p;
}


/*
*   Add a pattern to the list of patterns for this state machine
*/ 
int
acsmAddPattern (ACSM_STRUCT * p, unsigned char *pat, int n, int nocase,
            int offset, int depth, void * id, int iid) 
{
  ACSM_PATTERN * plist;
  plist = (ACSM_PATTERN *) AC_MALLOC (sizeof (ACSM_PATTERN));
  MEMASSERT (plist, "acsmAddPattern");
  plist->patrn = (unsigned char *) AC_MALLOC (n);
  ConvertCaseEx (plist->patrn, pat, n);
  plist->casepatrn = (unsigned char *) AC_MALLOC (n);
  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;
}


/*
*   Compile State Machine
*/ 
int
acsmCompile (ACSM_STRUCT * acsm) 
{
    int i, k;
    ACSM_PATTERN * plist;
  
    /* Count number of states */ 
    acsm->acsmMaxStates = 1;
    for (plist = acsm->acsmPatterns; plist != NULL; plist = plist->next)
    {
        acsm->acsmMaxStates += plist->n;
    }
    acsm->acsmStateTable =
        (ACSM_STATETABLE *) AC_MALLOC (sizeof (ACSM_STATETABLE) *
                                        acsm->acsmMaxStates);
    MEMASSERT (acsm->acsmStateTable, "acsmCompile");
    memset (acsm->acsmStateTable, 0,
        sizeof (ACSM_STATETABLE) * acsm->acsmMaxStates);

    /* Initialize state zero as a branch */ 
    acsm->acsmNumStates = 0;

    /* Initialize all States NextStates to FAILED */ 
    for (k = 0; k < acsm->acsmMaxStates; k++)
    {
        for (i = 0; i < ALPHABET_SIZE; i++)
        {
            acsm->acsmStateTable[k].NextState[i] = ACSM_FAIL_STATE;
        }
    }
 
    /* Add each Pattern to the State Table */ 
    for (plist = acsm->acsmPatterns; plist != NULL; plist = plist->next)
    {
        AddPatternStates (acsm, plist);
    }
 
    /* Set all failed state transitions to return to the 0'th state */ 
    for (i = 0; i < ALPHABET_SIZE; i++)
    {
        if (acsm->acsmStateTable[0].NextState[i] == ACSM_FAIL_STATE)
        {
            acsm->acsmStateTable[0].NextState[i] = 0;
        }
    }
 
    /* Build the NFA  */ 
    Build_NFA (acsm);

    /* Convert the NFA to a DFA */ 
    Convert_NFA_To_DFA (acsm);

    /*
      printf ("ACSMX-Max Memory: %d bytes, %d states\n", max_memory,
        acsm->acsmMaxStates);
     */

    //Print_DFA( acsm );

    return 0;
}


static unsigned char Tc[64*1024];

/*
*   Search Text or Binary Data for Pattern matches
*/ 
int
acsmSearch (ACSM_STRUCT * acsm, unsigned char *Tx, int n,
            int (*Match) (void *  id, int index, void *data), void *data, 
            int* current_state ) 
{
    int state = 0;
    ACSM_PATTERN * mlist;
    unsigned char *Tend;
    ACSM_STATETABLE * StateTable = acsm->acsmStateTable;
    int nfound = 0;
    unsigned char *T;
    int index;
 
    /* Case conversion */ 
    ConvertCaseEx (Tc, Tx, n);
    T = Tc;
    Tend = T + n;

    if ( !current_state )
    {
        return 0;
    }

    state = *current_state;

    for (; T < Tend; T++)
    {
        state = StateTable[state].NextState[*T];

        if( StateTable[state].MatchList != NULL )
        {
            for( mlist=StateTable[state].MatchList; mlist!=NULL;
                 mlist=mlist->next )
            {
                index = T - mlist->n + 1 - Tc;
                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;
}


/*
*   Free all memory
*/ 
void
acsmFree (ACSM_STRUCT * acsm) 
{
    int i;
    ACSM_PATTERN * mlist, *ilist;
    for (i = 0; i < acsm->acsmMaxStates; i++)
    {
        mlist = acsm->acsmStateTable[i].MatchList;
        while (mlist)
        {
            ilist = mlist;
            mlist = mlist->next;
            AC_FREE (ilist);
        }
    }
    AC_FREE (acsm->acsmStateTable);
    mlist = acsm->acsmPatterns;
    while(mlist)
    {
        ilist = mlist;
        mlist = mlist->next;
        AC_FREE(ilist->patrn);
        AC_FREE(ilist->casepatrn);
        AC_FREE(ilist);
    }
    AC_FREE (acsm);
}

/*
 * 
 */ 
/*
static void Print_DFA( ACSM_STRUCT * acsm )
{
    int k;
    int i;
    int next;
    
    for (k = 0; k < acsm->acsmMaxStates; k++)
    {
      for (i = 0; i < ALPHABET_SIZE; i++)
    {
      next = acsm->acsmStateTable[k].NextState[i];

      if( next == 0 || next ==  ACSM_FAIL_STATE )
      {
           if( isprint(i) )
             printf("%3c->%-5d\t",i,next);
           else
             printf("%3d->%-5d\t",i,next);
      }
    }
      printf("\n");
    }
    
} 
*/
    

int acsmPrintDetailInfo(ACSM_STRUCT * p)
{
    if(p)
        p = p;
    return 0;
}
    
int acsmPrintSummaryInfo(void)
{
#ifdef XXXXX
    char * fsa[]={
      "TRIE",
      "NFA",
      "DFA",
    };

    ACSM_STRUCT2 * p = &summary.acsm;

    if( !summary.num_states )
        return;
    
    printf("+--[Pattern Matcher:Aho-Corasick Summary]----------------------\n");
    printf("| Alphabet Size    : %d Chars\n",p->acsmAlphabetSize);
    printf("| Sizeof State     : %d bytes\n",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");

#endif
    return 0;
}


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

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


/*
*
*/ 
  int
main (int argc, char **argv) 
{
  int i, nocase = 0;
  ACSM_STRUCT * acsm;
  if (argc < 3)
    
    {
      fprintf (stderr,
        "Usage: acsmx pattern word-1 word-2 ... word-n  -nocase\n");
      exit (0);
    }
  acsm = acsmNew ();
  strcpy (text, argv[1]);
  for (i = 1; i < argc; i++)
    if (strcmp (argv[i], "-nocase") == 0)
      nocase = 1;
  for (i = 2; i < argc; i++)
    
    {
      if (argv[i][0] == '-')
    continue;
      acsmAddPattern (acsm, argv[i], strlen (argv[i]), nocase, 0, 0,
            argv[i], i - 2);
    }
  acsmCompile (acsm);
  acsmSearch (acsm, text, strlen (text), MatchFound, (void *) 0);
  acsmFree (acsm);
  printf ("normal pgm end\n");
  return (0);
}
#endif /*  */