"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