"Fossies" - the Fresh Open Source Software Archive

Member "snort3_extra-3.1.53.0/src/search_engines/lowmem/sfksearch.cc" (20 Dec 2022, 14002 Bytes) of package /linux/misc/snort3_extra-3.1.53.0.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "sfksearch.cc" see the Fossies "Dox" file reference documentation.

    1 //--------------------------------------------------------------------------
    2 // Copyright (C) 2001 Marc Norton
    3 // Copyright (C) 2014-2022 Cisco and/or its affiliates. All rights reserved.
    4 // Copyright (C) 2003-2013 Sourcefire, Inc.
    5 //
    6 // This program is free software; you can redistribute it and/or modify it
    7 // under the terms of the GNU General Public License Version 2 as published
    8 // by the Free Software Foundation.  You may not use, modify or distribute
    9 // this program under any other version of the GNU General Public License.
   10 //
   11 // This program is distributed in the hope that it will be useful, but
   12 // WITHOUT ANY WARRANTY; without even the implied warranty of
   13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   14 // General Public License for more details.
   15 //
   16 // You should have received a copy of the GNU General Public License along
   17 // with this program; if not, write to the Free Software Foundation, Inc.,
   18 // 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
   19 //--------------------------------------------------------------------------
   20 /*
   21 *  ksearch.c
   22 *
   23 *  Basic Keyword Search Trie - uses linked lists to build the finite automata
   24 *
   25 *  Keyword-Match: Performs the equivalent of a multi-string strcmp()
   26 *     - use for token testing after parsing the language tokens using lex or the like.
   27 *
   28 *  Keyword-Search: searches the input text for one of multiple keywords,
   29 *  and supports case sensitive and case insensitive patterns.
   30 */
   31 
   32 #include "sfksearch.h"
   33 
   34 #include <cassert>
   35 
   36 #include "main/thread.h"
   37 #include "utils/util.h"
   38 
   39 static void KTrieFree(KTRIENODE* n);
   40 
   41 static unsigned int mtot = 0;
   42 
   43 unsigned int KTrieMemUsed()
   44 {
   45     return mtot;
   46 }
   47 
   48 void KTrieInitMemUsed()
   49 {
   50     mtot = 0;
   51 }
   52 
   53 /*
   54 *  Allocate Memory
   55 */
   56 static void* KTRIE_MALLOC(int n)
   57 {
   58     assert(n > 0);
   59     void* p = snort_calloc(n);
   60     mtot += n;
   61     return p;
   62 }
   63 
   64 /*
   65 *  Free Memory
   66 */
   67 static void KTRIE_FREE(void* p)
   68 {
   69     if ( p )
   70         snort_free(p);
   71 }
   72 
   73 /*
   74 *   Local/Tmp nocase array
   75 */
   76 static THREAD_LOCAL uint8_t Tnocase[65*1024];
   77 
   78 /*
   79 ** Case Translation Table
   80 */
   81 static uint8_t xlatcase[256];
   82 
   83 /*
   84 *
   85 */
   86 void KTrie_init_xlatcase()
   87 {
   88     for (int i=0; i<256; i++)
   89     {
   90         xlatcase[ i ] =  (uint8_t)tolower(i);
   91     }
   92 }
   93 
   94 /*
   95 *
   96 */
   97 static inline void ConvertCaseEx(uint8_t* d, const uint8_t* s, int m)
   98 {
   99     int i;
  100     for ( i=0; i < m; i++ )
  101     {
  102         d[i] = xlatcase[ s[i] ];
  103     }
  104 }
  105 
  106 /*
  107 *
  108 */
  109 KTRIE_STRUCT* KTrieNew(int method, const MpseAgent* agent)
  110 {
  111     KTRIE_STRUCT* ts = (KTRIE_STRUCT*)KTRIE_MALLOC(sizeof(*ts));
  112 
  113     ts->memory = sizeof(*ts);
  114     ts->nchars = 0;
  115     ts->npats  = 0;
  116     ts->end_states = 0;
  117     ts->method = method; /* - old method, 1 = queue */
  118     ts->agent = agent;
  119 
  120     return ts;
  121 }
  122 
  123 int KTriePatternCount(KTRIE_STRUCT* k)
  124 {
  125     return k->npats;
  126 }
  127 
  128 /*
  129  * Deletes memory that was used in creating trie
  130  * and nodes
  131  */
  132 void KTrieDelete(KTRIE_STRUCT* k)
  133 {
  134     if ( !k )
  135         return;
  136 
  137     KTRIEPATTERN* p = k->patrn;
  138     KTRIEPATTERN* pnext = nullptr;
  139 
  140     while ( p )
  141     {
  142         pnext = p->next;
  143 
  144         if (k->agent)
  145         {
  146             if (p->user)
  147                 k->agent->user_free(p->user);
  148             if (p->rule_option_tree)
  149                 k->agent->tree_free(&p->rule_option_tree);
  150             if (p->neg_list)
  151                 k->agent->list_free(&p->neg_list);
  152         }
  153 
  154         KTRIE_FREE(p->P);
  155         KTRIE_FREE(p->Pcase);
  156         KTRIE_FREE(p);
  157 
  158         p = pnext;
  159     }
  160 
  161     for ( int i = 0; i < KTRIE_ROOT_NODES; i++ )
  162         KTrieFree(k->root[i]);
  163 
  164     KTRIE_FREE(k);
  165 }
  166 
  167 /*
  168  * Recursively delete all nodes in trie
  169  */
  170 static void KTrieFree(KTRIENODE* n)
  171 {
  172     if ( !n )
  173         return;
  174 
  175     KTrieFree(n->child);
  176     KTrieFree(n->sibling);
  177 
  178     KTRIE_FREE(n);
  179 }
  180 
  181 /*
  182 *
  183 */
  184 static KTRIEPATTERN* KTrieNewPattern(const uint8_t* P, unsigned n)
  185 {
  186     if (n < 1)
  187         return nullptr;
  188 
  189     KTRIEPATTERN* p = (KTRIEPATTERN*)KTRIE_MALLOC(sizeof(*p));
  190 
  191     /* Save as a nocase string */
  192     p->P = (uint8_t*)KTRIE_MALLOC(n);
  193 
  194     ConvertCaseEx(p->P, P, n);
  195 
  196     /* Save Case specific version */
  197     p->Pcase = (uint8_t*)KTRIE_MALLOC(n);
  198     memcpy(p->Pcase, P, n);
  199 
  200     p->n = n;
  201     p->next = nullptr;
  202 
  203     return p;
  204 }
  205 
  206 /*
  207 *  Add Pattern info to the list of patterns
  208 */
  209 int KTrieAddPattern(
  210     KTRIE_STRUCT* ts, const uint8_t* P, unsigned n,
  211     bool nocase, bool negative, void* user)
  212 {
  213     KTRIEPATTERN* pnew;
  214 
  215     if ( !ts->patrn )
  216     {
  217         pnew = ts->patrn = KTrieNewPattern(P, n);
  218 
  219         if ( !pnew )
  220             return -1;
  221     }
  222     else
  223     {
  224         pnew = KTrieNewPattern(P, n);
  225 
  226         if ( !pnew )
  227             return -1;
  228 
  229         pnew->next = ts->patrn; /* insert at head of list */
  230 
  231         ts->patrn = pnew;
  232     }
  233 
  234     pnew->nocase = nocase;
  235     pnew->negative = negative;
  236     pnew->user = user;
  237     pnew->mnext = nullptr;
  238 
  239     ts->npats++;
  240     ts->memory += sizeof(KTRIEPATTERN) + 2 * n;  /* Case and nocase */
  241 
  242     return 0;
  243 }
  244 
  245 /*
  246 *
  247 */
  248 static KTRIENODE* KTrieCreateNode(KTRIE_STRUCT* ts)
  249 {
  250     KTRIENODE* t = (KTRIENODE*)KTRIE_MALLOC(sizeof(*t));
  251     ts->memory += sizeof(*t);
  252     return t;
  253 }
  254 
  255 /*
  256 *  Insert a Pattern in the Trie
  257 */
  258 static int KTrieInsert(KTRIE_STRUCT* ts, KTRIEPATTERN* px)
  259 {
  260     int type = 0;
  261     int n = px->n;
  262     uint8_t* P = px->P;
  263     KTRIENODE* root;
  264 
  265     /* Make sure we at least have a root character for the tree */
  266     if ( !ts->root[*P] )
  267     {
  268         ts->root[*P] = root = KTrieCreateNode(ts);
  269         if ( !root )
  270             return -1;
  271         root->edge = *P;
  272     }
  273     else
  274     {
  275         root = ts->root[*P];
  276     }
  277 
  278     /* Walk existing Patterns */
  279     while ( n )
  280     {
  281         if ( root->edge == *P )
  282         {
  283             P++;
  284             n--;
  285 
  286             if ( n && root->child )
  287             {
  288                 root=root->child;
  289             }
  290             else     /* cannot continue */
  291             {
  292                 type = 0; /* Expand the tree via the child */
  293                 break;
  294             }
  295         }
  296         else
  297         {
  298             if ( root->sibling )
  299             {
  300                 root=root->sibling;
  301             }
  302             else     /* cannot continue */
  303             {
  304                 type = 1; /* Expand the tree via the sibling */
  305                 break;
  306             }
  307         }
  308     }
  309 
  310     /*
  311     * Add the next char of the Keyword, if any
  312     */
  313     if ( n )
  314     {
  315         if ( type == 0 )
  316         {
  317             /*
  318             *  Start with a new child to finish this Keyword
  319             */
  320             root->child= KTrieCreateNode(ts);
  321             if ( !root->child )
  322                 return -1;
  323             root=root->child;
  324             root->edge  = *P;
  325             P++;
  326             n--;
  327             ts->nchars++;
  328         }
  329         else
  330         {
  331             /*
  332             *  Start a new sibling branch to finish this Keyword
  333             */
  334             root->sibling= KTrieCreateNode(ts);
  335             if ( !root->sibling )
  336                 return -1;
  337             root=root->sibling;
  338             root->edge  = *P;
  339             P++;
  340             n--;
  341             ts->nchars++;
  342         }
  343     }
  344 
  345     /*
  346     *    Finish the keyword as child nodes
  347     */
  348     while ( n )
  349     {
  350         root->child = KTrieCreateNode(ts);
  351         if ( !root->child )
  352             return -1;
  353         root=root->child;
  354         root->edge  = *P;
  355         P++;
  356         n--;
  357         ts->nchars++;
  358     }
  359 
  360     if ( root->pkeyword )
  361     {
  362         px->mnext = root->pkeyword;  /* insert duplicates at front of list */
  363         root->pkeyword = px;
  364         ts->duplicates++;
  365     }
  366     else
  367     {
  368         root->pkeyword = px;
  369         ts->end_states++;
  370     }
  371 
  372     return 0;
  373 }
  374 
  375 /*
  376 *
  377 */
  378 static void Build_Bad_Character_Shifts(KTRIE_STRUCT* kt)
  379 {
  380     KTRIEPATTERN* plist;
  381 
  382     /* Calc the min pattern size */
  383     kt->bcSize = 32000;
  384 
  385     for ( plist=kt->patrn; plist; plist=plist->next )
  386     {
  387         if ( plist->n < kt->bcSize )
  388         {
  389             kt->bcSize = plist->n; /* smallest pattern size */
  390         }
  391     }
  392 
  393     /*
  394     *  Initialize the Bad Character shift table.
  395     */
  396     for ( int i = 0; i < KTRIE_ROOT_NODES; i++ )
  397     {
  398         kt->bcShift[i] = (unsigned short)kt->bcSize;
  399     }
  400 
  401     /*
  402     *  Finish the Bad character shift table
  403     */
  404     for ( plist=kt->patrn; plist; plist=plist->next )
  405     {
  406         for ( int k=0; k<kt->bcSize; k++ )
  407         {
  408             int shift = kt->bcSize - 1 - k;
  409             int cindex = plist->P[ k ];
  410 
  411             if ( shift < kt->bcShift[ cindex ] )
  412             {
  413                 kt->bcShift[ cindex ] = (unsigned short)shift;
  414             }
  415         }
  416     }
  417 }
  418 
  419 static int KTrieBuildMatchStateNode(
  420     snort::SnortConfig* sc, KTRIENODE* root, KTRIE_STRUCT* ts)
  421 {
  422     int cnt = 0;
  423     KTRIEPATTERN* p;
  424 
  425     if (!root)
  426         return 0;
  427 
  428     /* each and every prefix match at this root*/
  429     if (root->pkeyword)
  430     {
  431         for (p = root->pkeyword; p; p = p->mnext)
  432         {
  433             if (p->user)
  434             {
  435                 if (p->negative)
  436                 {
  437                     ts->agent->negate_list(p->user, &root->pkeyword->neg_list);
  438                 }
  439                 else
  440                 {
  441                     ts->agent->build_tree(sc, p->user, &root->pkeyword->rule_option_tree);
  442                 }
  443             }
  444 
  445             cnt++;
  446         }
  447 
  448         /* Last call to finalize the tree for this root */
  449         ts->agent->build_tree(sc, nullptr, &root->pkeyword->rule_option_tree);
  450     }
  451 
  452     /* for child of this root */
  453     if (root->child)
  454     {
  455         cnt += KTrieBuildMatchStateNode(sc, root->child, ts);
  456     }
  457 
  458     /* 1st sibling of this root -- other siblings will be processed from
  459      * within the processing for root->sibling. */
  460     if (root->sibling)
  461     {
  462         cnt += KTrieBuildMatchStateNode(sc, root->sibling, ts);
  463     }
  464 
  465     return cnt;
  466 }
  467 
  468 static int KTrieBuildMatchStateTrees(snort::SnortConfig* sc, KTRIE_STRUCT* ts)
  469 {
  470     int cnt = 0;
  471 
  472     /* Find the states that have a MatchList */
  473     for (int i = 0; i < KTRIE_ROOT_NODES; i++)
  474     {
  475         KTRIENODE* root = ts->root[i];
  476 
  477         /* each and every prefix match at this root*/
  478         if ( root and ts->agent )
  479         {
  480             cnt += KTrieBuildMatchStateNode(sc, root, ts);
  481         }
  482     }
  483 
  484     return cnt;
  485 }
  486 
  487 /*
  488 *  Build the Keyword TRIE
  489 *
  490 */
  491 static inline int _KTrieCompile(KTRIE_STRUCT* ts)
  492 {
  493     KTRIEPATTERN* p;
  494     /*
  495     static int  tmem=0;  // unused
  496     */
  497 
  498     /*
  499     *    Build the Keyword TRIE
  500     */
  501     for ( p=ts->patrn; p; p=p->next )
  502     {
  503         if ( KTrieInsert(ts, p) )
  504             return -1;
  505     }
  506 
  507     /*
  508     *    Build A Setwise Bad Character Shift Table
  509     */
  510     Build_Bad_Character_Shifts(ts);
  511 
  512     /*
  513     tmem += ts->memory;
  514     printf(" Compile stats: %d patterns, %d chars, %d duplicate patterns, %d bytes, %d total-bytes\n",ts->npats,ts->nchars,ts->duplicates,ts->memory,tmem);
  515     */
  516 
  517     return 0;
  518 }
  519 
  520 int KTrieCompile(snort::SnortConfig* sc, KTRIE_STRUCT* ts)
  521 {
  522     int rval;
  523 
  524     if ((rval = _KTrieCompile(ts)))
  525         return rval;
  526 
  527     if ( ts->agent )
  528         KTrieBuildMatchStateTrees(sc, ts);
  529 
  530     return 0;
  531 }
  532 
  533 void sfksearch_print_qinfo()
  534 {
  535 }
  536 
  537 /*
  538 *   Search - Algorithm
  539 *
  540 *   This routine will log any substring of T that matches a keyword,
  541 *   and processes all prefix matches. This is used for generic
  542 *   pattern searching with a set of keywords and a body of text.
  543 *
  544 *
  545 *
  546 *   kt- Trie Structure
  547 *   T - nocase text
  548 *   Tc- case specific text
  549 *   n - text length
  550 *
  551 *   returns:
  552 *   # pattern matches
  553 */
  554 static inline int KTriePrefixMatch(
  555     KTRIE_STRUCT* kt, const uint8_t* T, const uint8_t*, const uint8_t* bT, int n,
  556     MpseMatch match, void* context)
  557 {
  558     KTRIENODE* root   = kt->root[ *T ];
  559     int nfound = 0;
  560     KTRIEPATTERN* pk;
  561     int index;
  562 
  563     /* Check if any keywords start with this character */
  564     if ( !root )
  565         return 0;
  566 
  567     while ( n )
  568     {
  569         if ( root->edge == *T )
  570         {
  571             T++;
  572             n--;
  573 
  574             pk = root->pkeyword;
  575             if (pk)
  576             {
  577                 index = (int)(T - bT);
  578                 nfound++;
  579                 if (match (pk->user, pk->rule_option_tree, index, context, pk->neg_list) > 0)
  580                 {
  581                     return nfound;
  582                 }
  583             }
  584 
  585             if ( n && root->child )
  586             {
  587                 root = root->child;
  588             }
  589             else     /* cannot continue -- match is over */
  590             {
  591                 break;
  592             }
  593         }
  594         else
  595         {
  596             if ( root->sibling )
  597             {
  598                 root = root->sibling;
  599             }
  600             else     /* cannot continue */
  601             {
  602                 break;
  603             }
  604         }
  605     }
  606 
  607     return nfound;
  608 }
  609 
  610 /*
  611 *
  612 */
  613 static inline int KTrieSearchNoBC(
  614     KTRIE_STRUCT* ks, const uint8_t* Tx, int n, MpseMatch match, void* context)
  615 {
  616     int nfound = 0;
  617     const uint8_t* T, * bT;
  618 
  619     ConvertCaseEx(Tnocase, Tx, n);
  620 
  621     T  = Tnocase;
  622     bT = T;
  623 
  624     for (; n>0; n--, T++, Tx++ )
  625     {
  626         nfound += KTriePrefixMatch(ks, T, Tx, bT, n, match, context);
  627     }
  628 
  629     return nfound;
  630 }
  631 
  632 /*
  633 *
  634 */
  635 static inline int KTrieSearchBC(
  636     KTRIE_STRUCT* ks, const uint8_t* Tx, int n, MpseMatch match, void* context)
  637 {
  638     const uint8_t* Tend;
  639     const uint8_t* T, * bT;
  640     int nfound  = 0;
  641     short* bcShift = (short*)ks->bcShift;
  642     int bcSize  = ks->bcSize;
  643 
  644     ConvertCaseEx(Tnocase, Tx, n);
  645 
  646     T  = Tnocase;
  647     bT = T;
  648 
  649     Tend = T + n - bcSize;
  650 
  651     bcSize--;
  652 
  653     for (; T <= Tend; n--, T++, Tx++ )
  654     {
  655         int tshift;
  656 
  657         while ( (tshift = bcShift[ *( T + bcSize ) ]) > 0 )
  658         {
  659             T  += tshift;
  660             Tx += tshift;
  661             if ( T > Tend )
  662                 return nfound;
  663         }
  664 
  665         nfound += KTriePrefixMatch(ks, T, Tx, bT, n, match, context);
  666     }
  667 
  668     return nfound;
  669 }
  670 
  671 int KTrieSearch(
  672     KTRIE_STRUCT* ks, const uint8_t* T, int n, MpseMatch match, void* context)
  673 {
  674     if ( ks->bcSize < 3 )
  675         return KTrieSearchNoBC(ks, T, n, match, context);
  676     else
  677         return KTrieSearchBC(ks, T, n, match, context);
  678 }
  679