1 /*
2 * Copyright (C) 2013-2022 Cisco Systems, Inc. and/or its affiliates. All rights reserved.
3 * Copyright (C) 2007-2013 Sourcefire, Inc.
4 *
5 * Authors: Tomasz Kojm
6 *
7 * This program is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License version 2 as
9 * published by the Free Software Foundation.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
19 * MA 02110-1301, USA.
20 */
21
22 #if HAVE_CONFIG_H
23 #include "clamav-config.h"
24 #endif
25
26 #include <stdio.h>
27 #include <string.h>
28 #include <stdlib.h>
29 #include <ctype.h>
30 #include <sys/stat.h>
31
32 #include <assert.h>
33 #ifdef HAVE_UNISTD_H
34 #include <unistd.h>
35 #endif
36
37 #include "clamav.h"
38 #include "others.h"
39 #include "matcher.h"
40 #include "matcher-ac.h"
41 #include "filetypes.h"
42 #include "str.h"
43 #include "readdb.h"
44 #include "default.h"
45 #include "filtering.h"
46
47 #include "mpool.h"
48
49 // clang-format off
50
51 #define AC_SPECIAL_ALT_CHAR 1
52 #define AC_SPECIAL_ALT_STR_FIXED 2
53 #define AC_SPECIAL_ALT_STR 3
54 #define AC_SPECIAL_LINE_MARKER 4
55 #define AC_SPECIAL_BOUNDARY 5
56 #define AC_SPECIAL_WORD_MARKER 6
57
58 #define AC_BOUNDARY_LEFT 0x0001
59 #define AC_BOUNDARY_LEFT_NEGATIVE 0x0002
60 #define AC_BOUNDARY_RIGHT 0x0004
61 #define AC_BOUNDARY_RIGHT_NEGATIVE 0x0008
62 #define AC_LINE_MARKER_LEFT 0x0010
63 #define AC_LINE_MARKER_LEFT_NEGATIVE 0x0020
64 #define AC_LINE_MARKER_RIGHT 0x0040
65 #define AC_LINE_MARKER_RIGHT_NEGATIVE 0x0080
66 #define AC_WORD_MARKER_LEFT 0x0100
67 #define AC_WORD_MARKER_LEFT_NEGATIVE 0x0200
68 #define AC_WORD_MARKER_RIGHT 0x0400
69 #define AC_WORD_MARKER_RIGHT_NEGATIVE 0x0800
70
71 static char boundary[256] = {
72 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 2, 0, 0,
73 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
74 3, 0, 2, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 3, 1, 3,
75 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 0,
76 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
77 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3,
78 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
79 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
80 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
81 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
82 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
83 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
84 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
85 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
86 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
87 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
88 };
89
90 // clang-format on
91
insert_list(struct cli_matcher * root,struct cli_ac_patt * pattern,struct cli_ac_node * pt)92 static inline int insert_list(struct cli_matcher *root, struct cli_ac_patt *pattern, struct cli_ac_node *pt)
93 {
94 struct cli_ac_list *new;
95 struct cli_ac_list **newtable;
96
97 new = (struct cli_ac_list *)MPOOL_CALLOC(root->mempool, 1, sizeof(struct cli_ac_list));
98 if (!new) {
99 cli_errmsg("cli_ac_addpatt: Can't allocate memory for list node\n");
100 return CL_EMEM;
101 }
102 new->me = pattern;
103 new->node = pt;
104
105 root->ac_lists++;
106 newtable = MPOOL_REALLOC(root->mempool, root->ac_listtable, root->ac_lists * sizeof(struct cli_ac_list *));
107 if (!newtable) {
108 root->ac_lists--;
109 cli_errmsg("cli_ac_addpatt: Can't realloc ac_listtable\n");
110 MPOOL_FREE(root->mempool, new);
111 return CL_EMEM;
112 }
113
114 root->ac_listtable = newtable;
115 root->ac_listtable[root->ac_lists - 1] = new;
116 return CL_SUCCESS;
117 }
118
119 #define RETURN_RES_IF_NE(uia, uib) \
120 do { \
121 if (uia < uib) return -1; \
122 if (uia > uib) return +1; \
123 } while (0)
124
patt_cmp_fn(const struct cli_ac_patt * a,const struct cli_ac_patt * b)125 static int patt_cmp_fn(const struct cli_ac_patt *a, const struct cli_ac_patt *b)
126 {
127 unsigned int i;
128 int res;
129 RETURN_RES_IF_NE(a->length[0], b->length[0]);
130 RETURN_RES_IF_NE(a->prefix_length[0], b->prefix_length[0]);
131 RETURN_RES_IF_NE(a->ch[0], b->ch[0]);
132 RETURN_RES_IF_NE(a->ch[1], b->ch[1]);
133 RETURN_RES_IF_NE(a->boundary, b->boundary);
134
135 res = memcmp(a->pattern, b->pattern, a->length[0] * sizeof(uint16_t));
136 if (res) return res;
137 res = memcmp(a->prefix, b->prefix, a->prefix_length[0] * sizeof(uint16_t));
138 if (res) return res;
139
140 RETURN_RES_IF_NE(a->special, b->special);
141 if (!a->special && !b->special)
142 return 0;
143
144 for (i = 0; i < a->special; i++) {
145 struct cli_ac_special *spcl_a = a->special_table[i], *spcl_b = b->special_table[i];
146
147 RETURN_RES_IF_NE(spcl_a->num, spcl_b->num);
148 RETURN_RES_IF_NE(spcl_a->negative, spcl_b->negative);
149 RETURN_RES_IF_NE(spcl_a->type, spcl_b->type);
150
151 if (spcl_a->type == AC_SPECIAL_ALT_CHAR) {
152 res = memcmp((spcl_a->alt).byte, (spcl_b->alt).byte, spcl_a->num);
153 if (res) return res;
154 } else if (spcl_a->type == AC_SPECIAL_ALT_STR_FIXED) {
155 unsigned int j;
156 RETURN_RES_IF_NE(spcl_a->len[0], spcl_b->len[0]);
157 for (j = 0; j < spcl_a->num; j++) {
158 res = memcmp((spcl_a->alt).f_str[j], (spcl_b->alt).f_str[j], spcl_a->len[0]);
159 if (res) return res;
160 }
161 } else if (spcl_a->type == AC_SPECIAL_ALT_STR) {
162 struct cli_alt_node *alt_a = (spcl_a->alt).v_str, *alt_b = (spcl_b->alt).v_str;
163 while (alt_a && alt_b) {
164 RETURN_RES_IF_NE(alt_a->len, alt_b->len);
165 res = memcmp(alt_a->str, alt_b->str, alt_a->len);
166 if (res) return res;
167 alt_a = alt_a->next;
168 alt_b = alt_b->next;
169 }
170 RETURN_RES_IF_NE(alt_a, alt_b);
171 }
172 }
173 return 0;
174 }
175
sort_list_fn(const void * a,const void * b)176 static int sort_list_fn(const void *a, const void *b)
177 {
178 const struct cli_ac_node *node_a = (*(const struct cli_ac_list **)a)->node;
179 const struct cli_ac_node *node_b = (*(const struct cli_ac_list **)b)->node;
180 const struct cli_ac_patt *patt_a = (*(const struct cli_ac_list **)a)->me;
181 const struct cli_ac_patt *patt_b = (*(const struct cli_ac_list **)b)->me;
182 int res;
183
184 /* 1. Group by owning node
185 * (this is for assigning entries to nodes) */
186 RETURN_RES_IF_NE(node_a, node_b);
187
188 /* 2. Group together equal pattern in a node
189 * (this is for building the next_same list) */
190 res = patt_cmp_fn(patt_a, patt_b);
191 if (res)
192 return res;
193
194 /* 3. Sort equal patterns in a node by partno in ascending order
195 * (this is required by the matcher) */
196 RETURN_RES_IF_NE(patt_a->partno, patt_b->partno);
197
198 /* 4. Keep close patterns close
199 * (this is for performace) */
200 RETURN_RES_IF_NE(patt_a, patt_b);
201
202 return 0;
203 }
204
sort_heads_by_partno_fn(const void * a,const void * b)205 static int sort_heads_by_partno_fn(const void *a, const void *b)
206 {
207 const struct cli_ac_list *list_a = *(const struct cli_ac_list **)a;
208 const struct cli_ac_list *list_b = *(const struct cli_ac_list **)b;
209 const struct cli_ac_patt *patt_a = list_a->me;
210 const struct cli_ac_patt *patt_b = list_b->me;
211
212 /* 1. Sort heads by partno
213 * (this is required by the matcher) */
214 RETURN_RES_IF_NE(patt_a->partno, patt_b->partno);
215
216 /* 2. Place longer lists earlier
217 * (this is for performance) */
218
219 while (1) {
220 if (!list_a->next_same) {
221 if (!list_b->next_same)
222 break;
223 return +1;
224 }
225 if (!list_b->next_same)
226 return -1;
227 list_a = list_a->next_same;
228 list_b = list_b->next_same;
229 }
230
231 /* 3. Keep close patterns close
232 * (this is for performace) */
233 RETURN_RES_IF_NE(patt_a, patt_b);
234
235 return 0;
236 }
237
link_node_lists(struct cli_ac_list ** listtable,unsigned int nentries)238 static inline void link_node_lists(struct cli_ac_list **listtable, unsigned int nentries)
239 {
240 struct cli_ac_list *prev = listtable[0];
241 struct cli_ac_node *node = prev->node;
242 unsigned int i, nheads = 1;
243
244 /* Link equal patterns in the next_same list (entries are already sorted by partno asc) */
245 for (i = 1; i < nentries; i++) {
246 int ret = patt_cmp_fn(prev->me, listtable[i]->me);
247 if (ret) {
248 /* This is a new head of a next_same chain */
249 prev = listtable[i];
250 if (i != nheads) {
251 /* Move heads towards the beginning of the table */
252 listtable[i] = listtable[nheads];
253 listtable[nheads] = prev;
254 }
255 nheads++;
256 } else {
257 prev->next_same = listtable[i];
258 prev->next = NULL;
259 prev = listtable[i];
260 }
261 }
262
263 cli_qsort(listtable, nheads, sizeof(listtable[0]), sort_heads_by_partno_fn);
264
265 /* Link heads in the next list */
266 node->list = listtable[0];
267 for (i = 1; i < nheads; i++)
268 listtable[i - 1]->next = listtable[i];
269 listtable[nheads - 1]->next = NULL;
270 }
271
link_lists(struct cli_matcher * root)272 static void link_lists(struct cli_matcher *root)
273 {
274 struct cli_ac_node *curnode;
275 unsigned int i, grouplen;
276
277 if (!root->ac_lists)
278 return;
279
280 /* Group the list by owning node, pattern equality and sort by partno */
281 cli_qsort(root->ac_listtable, root->ac_lists, sizeof(root->ac_listtable[0]), sort_list_fn);
282
283 curnode = root->ac_listtable[0]->node;
284 for (i = 1, grouplen = 1; i <= root->ac_lists; i++, grouplen++) {
285 if (i == root->ac_lists || root->ac_listtable[i]->node != curnode) {
286 link_node_lists(&root->ac_listtable[i - grouplen], grouplen);
287 if (i < root->ac_lists) {
288 grouplen = 0;
289 curnode = root->ac_listtable[i]->node;
290 }
291 }
292 }
293 }
294
add_new_node(struct cli_matcher * root,uint16_t i,uint16_t len)295 static inline struct cli_ac_node *add_new_node(struct cli_matcher *root, uint16_t i, uint16_t len)
296 {
297 struct cli_ac_node *new;
298 struct cli_ac_node **newtable;
299
300 new = (struct cli_ac_node *)MPOOL_CALLOC(root->mempool, 1, sizeof(struct cli_ac_node));
301 if (!new) {
302 cli_errmsg("cli_ac_addpatt: Can't allocate memory for AC node\n");
303 return NULL;
304 }
305
306 if (i != len - 1) {
307 new->trans = (struct cli_ac_node **)MPOOL_CALLOC(root->mempool, 256, sizeof(struct cli_ac_node *));
308 if (!new->trans) {
309 cli_errmsg("cli_ac_addpatt: Can't allocate memory for new->trans\n");
310 MPOOL_FREE(root->mempool, new);
311 return NULL;
312 }
313 }
314
315 root->ac_nodes++;
316 newtable = MPOOL_REALLOC(root->mempool, root->ac_nodetable, root->ac_nodes * sizeof(struct cli_ac_node *));
317 if (!newtable) {
318 root->ac_nodes--;
319 cli_errmsg("cli_ac_addpatt: Can't realloc ac_nodetable\n");
320 if (new->trans)
321 MPOOL_FREE(root->mempool, new->trans);
322 MPOOL_FREE(root->mempool, new);
323 return NULL;
324 }
325
326 root->ac_nodetable = newtable;
327 root->ac_nodetable[root->ac_nodes - 1] = new;
328
329 return new;
330 }
331
cli_ac_addpatt_recursive(struct cli_matcher * root,struct cli_ac_patt * pattern,struct cli_ac_node * pt,uint16_t i,uint16_t len)332 static int cli_ac_addpatt_recursive(struct cli_matcher *root, struct cli_ac_patt *pattern, struct cli_ac_node *pt, uint16_t i, uint16_t len)
333 {
334 struct cli_ac_node *next;
335 int ret;
336
337 /* last node, insert pattern here (base case)*/
338 if (i >= len) {
339 return insert_list(root, pattern, pt);
340 }
341
342 /* if current node has no trans table, generate one */
343 if (!pt->trans) {
344 pt->trans = (struct cli_ac_node **)MPOOL_CALLOC(root->mempool, 256, sizeof(struct cli_ac_node *));
345 if (!pt->trans) {
346 cli_errmsg("cli_ac_addpatt: Can't allocate memory for pt->trans\n");
347 return CL_EMEM;
348 }
349 }
350
351 /* if pattern is nocase, we need to enumerate all the combinations if applicable
352 * it's why this function was re-written to be recursive
353 */
354 if ((pattern->sigopts & ACPATT_OPTION_NOCASE) && (pattern->pattern[i] & 0xff) < 0x80 && isalpha((unsigned char)(pattern->pattern[i] & 0xff))) {
355 next = pt->trans[CLI_NOCASEI((unsigned char)(pattern->pattern[i] & 0xff))];
356 if (!next)
357 next = add_new_node(root, i, len);
358 if (!next)
359 return CL_EMEM;
360 else
361 pt->trans[CLI_NOCASEI((unsigned char)(pattern->pattern[i] & 0xff))] = next;
362
363 if ((ret = cli_ac_addpatt_recursive(root, pattern, next, i + 1, len)) != CL_SUCCESS)
364 return ret;
365 }
366
367 /* normal transition, also enumerates the 'normal' nocase */
368 next = pt->trans[(unsigned char)(pattern->pattern[i] & 0xff)];
369 if (!next)
370 next = add_new_node(root, i, len);
371 if (!next)
372 return CL_EMEM;
373 else
374 pt->trans[(unsigned char)(pattern->pattern[i] & 0xff)] = next;
375
376 return cli_ac_addpatt_recursive(root, pattern, next, i + 1, len);
377 }
378
cli_ac_addpatt(struct cli_matcher * root,struct cli_ac_patt * pattern)379 cl_error_t cli_ac_addpatt(struct cli_matcher *root, struct cli_ac_patt *pattern)
380 {
381 struct cli_ac_patt **newtable;
382 uint16_t len = MIN(root->ac_maxdepth, pattern->length[0]);
383 uint16_t i;
384
385 for (i = 0; i < len; i++) {
386 if (pattern->pattern[i] & CLI_MATCH_WILDCARD) {
387 len = i;
388 break;
389 }
390 }
391
392 if (len < root->ac_mindepth) {
393 /* cli_errmsg("cli_ac_addpatt: Signature for %s is too short\n", pattern->virname); */
394 return CL_EMALFDB;
395 }
396
397 /* pattern added to master list */
398 root->ac_patterns++;
399 newtable = MPOOL_REALLOC(root->mempool, root->ac_pattable, root->ac_patterns * sizeof(struct cli_ac_patt *));
400 if (!newtable) {
401 root->ac_patterns--;
402 cli_errmsg("cli_ac_addpatt: Can't realloc ac_pattable\n");
403 return CL_EMEM;
404 }
405
406 root->ac_pattable = newtable;
407 root->ac_pattable[root->ac_patterns - 1] = pattern;
408
409 pattern->depth = len;
410
411 return cli_ac_addpatt_recursive(root, pattern, root->ac_root, 0, len);
412 }
413
414 struct bfs_list {
415 struct cli_ac_node *node;
416 struct bfs_list *next;
417 };
418
bfs_enqueue(struct bfs_list ** bfs,struct bfs_list ** last,struct cli_ac_node * n)419 static int bfs_enqueue(struct bfs_list **bfs, struct bfs_list **last, struct cli_ac_node *n)
420 {
421 struct bfs_list *new;
422
423 new = (struct bfs_list *)cli_malloc(sizeof(struct bfs_list));
424 if (!new) {
425 cli_errmsg("bfs_enqueue: Can't allocate memory for bfs_list\n");
426 return CL_EMEM;
427 }
428
429 new->next = NULL;
430 new->node = n;
431
432 if (*last) {
433 (*last)->next = new;
434 *last = new;
435 } else {
436 *bfs = *last = new;
437 }
438
439 return CL_SUCCESS;
440 }
441
bfs_dequeue(struct bfs_list ** bfs,struct bfs_list ** last)442 static struct cli_ac_node *bfs_dequeue(struct bfs_list **bfs, struct bfs_list **last)
443 {
444 struct bfs_list *lpt;
445 struct cli_ac_node *pt;
446
447 if (!(lpt = *bfs)) {
448 return NULL;
449 } else {
450 *bfs = (*bfs)->next;
451 pt = lpt->node;
452
453 if (lpt == *last)
454 *last = NULL;
455
456 free(lpt);
457 return pt;
458 }
459 }
460
ac_maketrans(struct cli_matcher * root)461 static int ac_maketrans(struct cli_matcher *root)
462 {
463 struct bfs_list *bfs = NULL, *bfs_last = NULL;
464 struct cli_ac_node *ac_root = root->ac_root, *child, *node, *fail;
465 int i, ret;
466
467 for (i = 0; i < 256; i++) {
468 node = ac_root->trans[i];
469 if (!node) {
470 ac_root->trans[i] = ac_root;
471 } else {
472 node->fail = ac_root;
473 if ((ret = bfs_enqueue(&bfs, &bfs_last, node)))
474 return ret;
475 }
476 }
477
478 while ((node = bfs_dequeue(&bfs, &bfs_last))) {
479 if (IS_LEAF(node)) {
480 struct cli_ac_node *failtarget = node->fail;
481
482 while (NULL != failtarget && (IS_LEAF(failtarget) || !IS_FINAL(failtarget)))
483 failtarget = failtarget->fail;
484
485 if (NULL != failtarget)
486 node->fail = failtarget;
487
488 continue;
489 }
490
491 for (i = 0; i < 256; i++) {
492 child = node->trans[i];
493 if (child) {
494 fail = node->fail;
495
496 while (IS_LEAF(fail) || !fail->trans[i])
497 fail = fail->fail;
498
499 child->fail = fail->trans[i];
500
501 if ((ret = bfs_enqueue(&bfs, &bfs_last, child)) != 0)
502 return ret;
503 }
504 }
505 }
506
507 bfs = bfs_last = NULL;
508 for (i = 0; i < 256; i++) {
509 node = ac_root->trans[i];
510 if (node != ac_root) {
511 if ((ret = bfs_enqueue(&bfs, &bfs_last, node)))
512 return ret;
513 }
514 }
515
516 while ((node = bfs_dequeue(&bfs, &bfs_last))) {
517 if (IS_LEAF(node))
518 continue;
519 for (i = 0; i < 256; i++) {
520 child = node->trans[i];
521 if (!child || (!IS_FINAL(child) && IS_LEAF(child))) {
522 struct cli_ac_node *failtarget = node->fail;
523
524 while (IS_LEAF(failtarget) || !failtarget->trans[i])
525 failtarget = failtarget->fail;
526
527 failtarget = failtarget->trans[i];
528 node->trans[i] = failtarget;
529 } else if (IS_FINAL(child) && IS_LEAF(child)) {
530 struct cli_ac_list *list;
531
532 list = child->list;
533 if (list) {
534 while (list->next)
535 list = list->next;
536
537 list->next = child->fail->list;
538 } else {
539 child->list = child->fail->list;
540 }
541
542 child->trans = child->fail->trans;
543 } else {
544 if ((ret = bfs_enqueue(&bfs, &bfs_last, child)) != 0)
545 return ret;
546 }
547 }
548 }
549
550 return CL_SUCCESS;
551 }
552
cli_ac_buildtrie(struct cli_matcher * root)553 cl_error_t cli_ac_buildtrie(struct cli_matcher *root)
554 {
555 if (!root)
556 return CL_EMALFDB;
557
558 if (!(root->ac_root)) {
559 cli_dbgmsg("cli_ac_buildtrie: AC pattern matcher is not initialised\n");
560 return CL_SUCCESS;
561 }
562
563 if (root->filter)
564 cli_dbgmsg("Using filter for trie %d\n", root->type);
565
566 link_lists(root);
567
568 return ac_maketrans(root);
569 }
570
cli_ac_init(struct cli_matcher * root,uint8_t mindepth,uint8_t maxdepth,uint8_t dconf_prefiltering)571 cl_error_t cli_ac_init(struct cli_matcher *root, uint8_t mindepth, uint8_t maxdepth, uint8_t dconf_prefiltering)
572 {
573 #ifdef USE_MPOOL
574 assert(root->mempool && "mempool must be initialized");
575 #endif
576
577 root->ac_root = (struct cli_ac_node *)MPOOL_CALLOC(root->mempool, 1, sizeof(struct cli_ac_node));
578 if (!root->ac_root) {
579 cli_errmsg("cli_ac_init: Can't allocate memory for ac_root\n");
580 return CL_EMEM;
581 }
582
583 root->ac_root->trans = (struct cli_ac_node **)MPOOL_CALLOC(root->mempool, 256, sizeof(struct cli_ac_node *));
584 if (!root->ac_root->trans) {
585 cli_errmsg("cli_ac_init: Can't allocate memory for ac_root->trans\n");
586 MPOOL_FREE(root->mempool, root->ac_root);
587 return CL_EMEM;
588 }
589
590 root->ac_mindepth = mindepth;
591 root->ac_maxdepth = maxdepth;
592
593 if (cli_mtargets[root->type].enable_prefiltering && dconf_prefiltering) {
594 root->filter = MPOOL_MALLOC(root->mempool, sizeof(*root->filter));
595 if (!root->filter) {
596 cli_errmsg("cli_ac_init: Can't allocate memory for ac_root->filter\n");
597 MPOOL_FREE(root->mempool, root->ac_root->trans);
598 MPOOL_FREE(root->mempool, root->ac_root);
599 return CL_EMEM;
600 }
601 filter_init(root->filter);
602 }
603
604 return CL_SUCCESS;
605 }
606
607 #ifdef USE_MPOOL
608 #define mpool_ac_free_special(a, b) ac_free_special(a, b)
ac_free_special(mpool_t * mempool,struct cli_ac_patt * p)609 static void ac_free_special(mpool_t *mempool, struct cli_ac_patt *p)
610 #else
611 #define mpool_ac_free_special(a, b) ac_free_special(b)
612 static void ac_free_special(struct cli_ac_patt *p)
613 #endif
614 {
615 unsigned int i, j;
616 struct cli_ac_special *a1;
617 struct cli_alt_node *b1, *b2;
618
619 if (!p->special)
620 return;
621
622 for (i = 0; i < p->special; i++) {
623 a1 = p->special_table[i];
624 if (a1->type == AC_SPECIAL_ALT_CHAR) {
625 MPOOL_FREE(mempool, (a1->alt).byte);
626 } else if (a1->type == AC_SPECIAL_ALT_STR_FIXED) {
627 for (j = 0; j < a1->num; j++)
628 MPOOL_FREE(mempool, (a1->alt).f_str[j]);
629 MPOOL_FREE(mempool, (a1->alt).f_str);
630 } else if (a1->type == AC_SPECIAL_ALT_STR) {
631 b1 = (a1->alt).v_str;
632 while (b1) {
633 b2 = b1->next;
634 MPOOL_FREE(mempool, b1->str);
635 MPOOL_FREE(mempool, b1);
636 b1 = b2;
637 }
638 }
639 MPOOL_FREE(mempool, a1);
640 }
641 MPOOL_FREE(mempool, p->special_table);
642 }
643
cli_ac_free(struct cli_matcher * root)644 void cli_ac_free(struct cli_matcher *root)
645 {
646 uint32_t i;
647 struct cli_ac_patt *patt;
648
649 for (i = 0; i < root->ac_patterns; i++) {
650 patt = root->ac_pattable[i];
651 MPOOL_FREE(root->mempool, patt->prefix ? patt->prefix : patt->pattern);
652 MPOOL_FREE(root->mempool, patt->virname);
653 if (patt->special)
654 mpool_ac_free_special(root->mempool, patt);
655 MPOOL_FREE(root->mempool, patt);
656 }
657
658 if (root->ac_pattable)
659 MPOOL_FREE(root->mempool, root->ac_pattable);
660
661 if (root->ac_reloff)
662 MPOOL_FREE(root->mempool, root->ac_reloff);
663
664 /* Freeing trans nodes must be done before freeing table nodes! */
665 for (i = 0; i < root->ac_nodes; i++) {
666 if (!IS_LEAF(root->ac_nodetable[i]) &&
667 root->ac_nodetable[i]->fail &&
668 root->ac_nodetable[i]->trans != root->ac_nodetable[i]->fail->trans) {
669 MPOOL_FREE(root->mempool, root->ac_nodetable[i]->trans);
670 }
671 }
672
673 for (i = 0; i < root->ac_lists; i++)
674 MPOOL_FREE(root->mempool, root->ac_listtable[i]);
675
676 if (root->ac_listtable)
677 MPOOL_FREE(root->mempool, root->ac_listtable);
678
679 for (i = 0; i < root->ac_nodes; i++)
680 MPOOL_FREE(root->mempool, root->ac_nodetable[i]);
681
682 if (root->ac_nodetable)
683 MPOOL_FREE(root->mempool, root->ac_nodetable);
684
685 if (root->ac_root) {
686 MPOOL_FREE(root->mempool, root->ac_root->trans);
687 MPOOL_FREE(root->mempool, root->ac_root);
688 }
689
690 if (root->filter)
691 MPOOL_FREE(root->mempool, root->filter);
692 }
693
694 /*
695 * In parse_only mode this function returns -1 on error or the max subsig id
696 */
cli_ac_chklsig(const char * expr,const char * end,uint32_t * lsigcnt,unsigned int * cnt,uint64_t * ids,unsigned int parse_only)697 int cli_ac_chklsig(const char *expr, const char *end, uint32_t *lsigcnt, unsigned int *cnt, uint64_t *ids, unsigned int parse_only)
698 {
699 unsigned int i, len = end - expr, pth = 0, opoff = 0, op1off = 0, val;
700 unsigned int blkend = 0, id, modval1, modval2 = 0, lcnt = 0, rcnt = 0, tcnt, modoff = 0;
701 uint64_t lids = 0, rids = 0, tids;
702 int ret, lval, rval;
703 char op = 0, op1 = 0, mod = 0, blkmod = 0;
704 const char *lstart = expr, *lend = NULL, *rstart = NULL, *rend = end, *pt;
705
706 for (i = 0; i < len; i++) {
707 switch (expr[i]) {
708 case '(':
709 pth++;
710 break;
711
712 case ')':
713 if (!pth) {
714 cli_errmsg("cli_ac_chklsig: Syntax error: Missing opening parenthesis\n");
715 return -1;
716 }
717 pth--;
718
719 case '>':
720 case '<':
721 case '=':
722 mod = expr[i];
723 modoff = i;
724 break;
725
726 default:
727 if (strchr("&|", expr[i])) {
728 if (!pth) {
729 op = expr[i];
730 opoff = i;
731 } else if (pth == 1) {
732 op1 = expr[i];
733 op1off = i;
734 }
735 }
736 }
737
738 if (op)
739 break;
740
741 if (op1 && !pth) {
742 blkend = i;
743 if (expr[i + 1] == '>' || expr[i + 1] == '<' || expr[i + 1] == '=') {
744 blkmod = expr[i + 1];
745
746 ret = sscanf(&expr[i + 2], "%u,%u", &modval1, &modval2);
747 if (ret != 2)
748 ret = sscanf(&expr[i + 2], "%u", &modval1);
749
750 if (!ret || ret == EOF) {
751 cli_errmsg("chklexpr: Syntax error: Missing number after '%c'\n", expr[i + 1]);
752 return -1;
753 }
754
755 for (i += 2; i + 1 < len && (isdigit(expr[i + 1]) || expr[i + 1] == ','); i++)
756 ;
757 }
758
759 if (&expr[i + 1] == rend)
760 break;
761 else
762 blkmod = 0;
763 }
764 }
765
766 if (pth) {
767 cli_errmsg("cli_ac_chklsig: Syntax error: Missing closing parenthesis\n");
768 return -1;
769 }
770
771 if (!op && !op1) {
772 if (expr[0] == '(')
773 return cli_ac_chklsig(++expr, --end, lsigcnt, cnt, ids, parse_only);
774
775 ret = sscanf(expr, "%u", &id);
776 if (!ret || ret == EOF) {
777 cli_errmsg("cli_ac_chklsig: Can't parse %s\n", expr);
778 return -1;
779 }
780
781 if (parse_only)
782 val = id;
783 else
784 val = lsigcnt[id];
785
786 if (mod) {
787 pt = expr + modoff + 1;
788 ret = sscanf(pt, "%u", &modval1);
789 if (!ret || ret == EOF) {
790 cli_errmsg("chklexpr: Syntax error: Missing number after '%c'\n", mod);
791 return -1;
792 }
793
794 if (!parse_only) {
795 switch (mod) {
796 case '=':
797 if (val != modval1)
798 return 0;
799 break;
800 case '<':
801 if (val >= modval1)
802 return 0;
803 break;
804 case '>':
805 if (val <= modval1)
806 return 0;
807 break;
808 default:
809 return 0;
810 }
811
812 *cnt += val;
813 *ids |= (uint64_t)1 << id;
814 return 1;
815 }
816 }
817
818 if (parse_only) {
819 return val;
820 } else {
821 if (val) {
822 *cnt += val;
823 *ids |= (uint64_t)1 << id;
824 return 1;
825 } else {
826 return 0;
827 }
828 }
829 }
830
831 if (!op) {
832 op = op1;
833 opoff = op1off;
834 lstart++;
835 rend = &expr[blkend];
836 }
837
838 if (!opoff) {
839 cli_errmsg("cli_ac_chklsig: Syntax error: Missing left argument\n");
840 return -1;
841 }
842
843 lend = &expr[opoff];
844 if (opoff + 1 == len) {
845 cli_errmsg("cli_ac_chklsig: Syntax error: Missing right argument\n");
846 return -1;
847 }
848
849 rstart = &expr[opoff + 1];
850
851 lval = cli_ac_chklsig(lstart, lend, lsigcnt, &lcnt, &lids, parse_only);
852 if (lval == -1) {
853 cli_errmsg("cli_ac_chklsig: Calculation of lval failed\n");
854 return -1;
855 }
856
857 rval = cli_ac_chklsig(rstart, rend, lsigcnt, &rcnt, &rids, parse_only);
858 if (rval == -1) {
859 cli_errmsg("cli_ac_chklsig: Calculation of rval failed\n");
860 return -1;
861 }
862
863 if (parse_only) {
864 switch (op) {
865 case '&':
866 case '|':
867 return MAX(lval, rval);
868 default:
869 cli_errmsg("cli_ac_chklsig: Incorrect operator type\n");
870 return -1;
871 }
872 } else {
873 switch (op) {
874 case '&':
875 ret = lval && rval;
876 break;
877 case '|':
878 ret = lval || rval;
879 break;
880 default:
881 cli_errmsg("cli_ac_chklsig: Incorrect operator type\n");
882 return -1;
883 }
884
885 if (!blkmod) {
886 if (ret) {
887 *cnt += lcnt + rcnt;
888 *ids |= lids | rids;
889 }
890
891 return ret;
892 } else {
893 if (ret) {
894 tcnt = lcnt + rcnt;
895 tids = lids | rids;
896 } else {
897 tcnt = 0;
898 tids = 0;
899 }
900
901 switch (blkmod) {
902 case '=':
903 if (tcnt != modval1)
904 return 0;
905 break;
906 case '<':
907 if (tcnt >= modval1)
908 return 0;
909 break;
910 case '>':
911 if (tcnt <= modval1)
912 return 0;
913 break;
914 default:
915 return 0;
916 }
917
918 if (modval2) {
919 val = 0;
920 while (tids) {
921 val += tids & (uint64_t)1;
922 tids >>= 1;
923 }
924
925 if (val < modval2)
926 return 0;
927 }
928
929 *cnt += tcnt;
930 return 1;
931 }
932 }
933 }
934
935 inline static int ac_findmatch_special(const unsigned char *buffer, uint32_t offset, uint32_t bp, uint32_t fileoffset, uint32_t length,
936 const struct cli_ac_patt *pattern, uint32_t pp, uint16_t specialcnt, uint32_t *start, uint32_t *end, int rev);
937 static int ac_backward_match_branch(const unsigned char *buffer, uint32_t bp, uint32_t offset, uint32_t length, uint32_t fileoffset,
938 const struct cli_ac_patt *pattern, uint32_t pp, uint16_t specialcnt, uint32_t *start, uint32_t *end);
939 static int ac_forward_match_branch(const unsigned char *buffer, uint32_t bp, uint32_t offset, uint32_t length, uint32_t fileoffset,
940 const struct cli_ac_patt *pattern, uint32_t pp, uint16_t specialcnt, uint32_t *start, uint32_t *end);
941
942 /* call only by ac_findmatch_special! Does not handle recursive specials */
943 #define AC_MATCH_CHAR2(p, b) \
944 switch (wc = p & CLI_MATCH_METADATA) { \
945 case CLI_MATCH_CHAR: \
946 if ((unsigned char)p != b) \
947 match = 0; \
948 break; \
949 \
950 case CLI_MATCH_NOCASE: \
951 if ((unsigned char)(p & 0xff) != CLI_NOCASE(b)) \
952 match = 0; \
953 break; \
954 \
955 case CLI_MATCH_IGNORE: \
956 break; \
957 \
958 case CLI_MATCH_NIBBLE_HIGH: \
959 if ((unsigned char)(p & 0x00f0) != (b & 0xf0)) \
960 match = 0; \
961 break; \
962 \
963 case CLI_MATCH_NIBBLE_LOW: \
964 if ((unsigned char)(p & 0x000f) != (b & 0x0f)) \
965 match = 0; \
966 break; \
967 \
968 default: \
969 cli_errmsg("ac_findmatch: Unknown metatype 0x%x\n", wc); \
970 match = 0; \
971 }
972
973 /* call only by ac_XX_match_branch! */
974 #define AC_MATCH_CHAR(p, b, rev) \
975 switch (wc = p & CLI_MATCH_METADATA) { \
976 case CLI_MATCH_CHAR: \
977 if ((unsigned char)p != b) \
978 match = 0; \
979 break; \
980 \
981 case CLI_MATCH_NOCASE: \
982 if ((unsigned char)(p & 0xff) != CLI_NOCASE(b)) \
983 match = 0; \
984 break; \
985 \
986 case CLI_MATCH_IGNORE: \
987 break; \
988 \
989 case CLI_MATCH_SPECIAL: \
990 /* >1 = movement, 0 = fail, <1 = resolved in branch */ \
991 if ((match = ac_findmatch_special(buffer, offset, bp, fileoffset, length, \
992 pattern, i, specialcnt, start, end, rev)) <= 0) \
993 return match; \
994 \
995 if (!rev) { \
996 bp += (match - 1); /* -1 is for bp++ in parent loop */ \
997 specialcnt++; \
998 } else { \
999 bp = bp + 1 - match; /* +1 is for bp-- in parent loop */ \
1000 specialcnt--; \
1001 } \
1002 \
1003 break; \
1004 \
1005 case CLI_MATCH_NIBBLE_HIGH: \
1006 if ((unsigned char)(p & 0x00f0) != (b & 0xf0)) \
1007 match = 0; \
1008 break; \
1009 \
1010 case CLI_MATCH_NIBBLE_LOW: \
1011 if ((unsigned char)(p & 0x000f) != (b & 0x0f)) \
1012 match = 0; \
1013 break; \
1014 \
1015 default: \
1016 cli_errmsg("ac_findmatch: Unknown metatype 0x%x\n", wc); \
1017 match = 0; \
1018 }
1019
1020 /* special handler */
ac_findmatch_special(const unsigned char * buffer,uint32_t offset,uint32_t bp,uint32_t fileoffset,uint32_t length,const struct cli_ac_patt * pattern,uint32_t pp,uint16_t specialcnt,uint32_t * start,uint32_t * end,int rev)1021 inline static int ac_findmatch_special(const unsigned char *buffer, uint32_t offset, uint32_t bp, uint32_t fileoffset, uint32_t length,
1022 const struct cli_ac_patt *pattern, uint32_t pp, uint16_t specialcnt, uint32_t *start, uint32_t *end, int rev)
1023 {
1024 int match, cmp;
1025 uint16_t j, b = buffer[bp];
1026 uint16_t wc;
1027 uint32_t subbp;
1028 struct cli_ac_special *special = pattern->special_table[specialcnt];
1029 struct cli_alt_node *alt = NULL;
1030
1031 match = special->negative;
1032
1033 switch (special->type) {
1034 case AC_SPECIAL_ALT_CHAR: /* single-byte */
1035 for (j = 0; j < special->num; j++) {
1036 cmp = b - (special->alt).byte[j];
1037 if (cmp == 0) {
1038 match = !special->negative;
1039 break;
1040 } else if (cmp < 0)
1041 break;
1042 }
1043 break;
1044
1045 case AC_SPECIAL_ALT_STR_FIXED: /* fixed length multi-byte */
1046 if (!rev) {
1047 if (bp + special->len[0] > length)
1048 break;
1049 subbp = bp;
1050 } else {
1051 if (bp < (special->len[0] - 1))
1052 break;
1053 subbp = bp - (special->len[0] - 1);
1054 }
1055
1056 match *= special->len[0];
1057 for (j = 0; j < special->num; j++) {
1058 cmp = memcmp(&buffer[subbp], (special->alt).f_str[j], special->len[0]);
1059 if (cmp == 0) {
1060 match = (!special->negative) * special->len[0];
1061 break;
1062 } else if (cmp < 0)
1063 break;
1064 }
1065 break;
1066
1067 case AC_SPECIAL_ALT_STR: /* generic */
1068 alt = (special->alt).v_str;
1069 while (alt) {
1070 if (!rev) {
1071 if (bp + alt->len > length) {
1072 alt = alt->next;
1073 continue;
1074 }
1075 subbp = bp;
1076 } else {
1077 if (bp < (alt->len - 1)) {
1078 alt = alt->next;
1079 continue;
1080 }
1081 subbp = bp - (alt->len - 1);
1082 }
1083
1084 /* note that generic alternates CANNOT be negated */
1085 match = 1;
1086 for (j = 0; j < alt->len; j++) {
1087 AC_MATCH_CHAR2(alt->str[j], buffer[subbp + j]);
1088 if (!match)
1089 break;
1090 }
1091 if (match) {
1092 /* if match is unique (has no derivatives), we can pass it directly back */
1093 if (alt->unique) {
1094 match = alt->len;
1095 break;
1096 }
1097 /* branch for backtracking */
1098 if (!rev)
1099 match = ac_forward_match_branch(buffer, subbp + alt->len, offset, fileoffset, length, pattern, pp + 1, specialcnt + 1, start, end);
1100 else
1101 match = ac_backward_match_branch(buffer, subbp - 1, offset, fileoffset, length, pattern, pp - 1, specialcnt - 1, start, end);
1102 if (match)
1103 return -1; /* alerts caller that match has been resolved in child callee */
1104 }
1105
1106 alt = alt->next;
1107 }
1108 break;
1109
1110 case AC_SPECIAL_LINE_MARKER:
1111 if (b == '\n')
1112 match = !special->negative;
1113 else if (b == '\r' && (bp + 1 < length && buffer[bp + 1] == '\n'))
1114 match = (!special->negative) * 2;
1115 break;
1116
1117 case AC_SPECIAL_BOUNDARY:
1118 if (boundary[b])
1119 match = !special->negative;
1120 break;
1121
1122 case AC_SPECIAL_WORD_MARKER:
1123 if (!isalnum(b))
1124 match = !special->negative;
1125 break;
1126
1127 default:
1128 cli_errmsg("ac_findmatch: Unknown special\n");
1129 match = 0;
1130 }
1131
1132 return match;
1133 }
1134
1135 /* state should reset on call, recursion depth = number of alternate specials */
1136 /* each loop iteration starts on the NEXT sequence to be validated */
ac_backward_match_branch(const unsigned char * buffer,uint32_t bp,uint32_t offset,uint32_t fileoffset,uint32_t length,const struct cli_ac_patt * pattern,uint32_t pp,uint16_t specialcnt,uint32_t * start,uint32_t * end)1137 static int ac_backward_match_branch(const unsigned char *buffer, uint32_t bp, uint32_t offset, uint32_t fileoffset, uint32_t length,
1138 const struct cli_ac_patt *pattern, uint32_t pp, uint16_t specialcnt, uint32_t *start, uint32_t *end)
1139 {
1140 int match = 0;
1141 uint16_t wc, i;
1142 uint32_t filestart;
1143
1144 /* backwards (prefix) validation, determines start */
1145 if (pattern->prefix && pattern->prefix_length[0]) {
1146 match = 1;
1147
1148 for (i = pp; 1; i--) {
1149 AC_MATCH_CHAR(pattern->prefix[i], buffer[bp], 1);
1150 if (!match)
1151 return 0;
1152
1153 /* needs to perform check before decrement due to unsignedness */
1154 if (i == 0 || bp == 0)
1155 break;
1156
1157 bp--;
1158 }
1159
1160 *start = bp;
1161 filestart = fileoffset - offset + bp;
1162 } else {
1163 /* bp is set to buffer offset */
1164 *start = bp = offset;
1165 filestart = fileoffset;
1166 }
1167
1168 /* left-side special checks, bp = start */
1169 if (pattern->boundary & AC_BOUNDARY_LEFT) {
1170 match = !!(pattern->boundary & AC_BOUNDARY_LEFT_NEGATIVE);
1171 if (!filestart || (bp && (boundary[buffer[bp - 1]] == 1 || boundary[buffer[bp - 1]] == 3)))
1172 match = !match;
1173
1174 if (!match)
1175 return 0;
1176 }
1177
1178 if (pattern->boundary & AC_LINE_MARKER_LEFT) {
1179 match = !!(pattern->boundary & AC_LINE_MARKER_LEFT_NEGATIVE);
1180 if (!filestart || (bp && (buffer[bp - 1] == '\n')))
1181 match = !match;
1182
1183 if (!match)
1184 return 0;
1185 }
1186
1187 if (pattern->boundary & AC_WORD_MARKER_LEFT) {
1188 match = !!(pattern->boundary & AC_WORD_MARKER_LEFT_NEGATIVE);
1189 if (!filestart)
1190 match = !match;
1191 else if (pattern->sigopts & ACPATT_OPTION_WIDE) {
1192 if (filestart - 1 == 0)
1193 match = !match;
1194 if (bp - 1 && bp && !(isalnum(buffer[bp - 2]) && buffer[bp - 1] == '\0'))
1195 match = !match;
1196 } else if (bp && !isalnum(buffer[bp - 1]))
1197 match = !match;
1198
1199 if (!match)
1200 return 0;
1201 }
1202
1203 /* bp is shifted for left anchor check, thus invalidated as pattern start */
1204 if (!(pattern->ch[0] & CLI_MATCH_IGNORE)) {
1205 if (pattern->ch_mindist[0] + (uint32_t)1 > bp)
1206 return 0;
1207
1208 bp -= pattern->ch_mindist[0] + 1;
1209 for (i = pattern->ch_mindist[0]; i <= pattern->ch_maxdist[0]; i++) {
1210 match = 1;
1211 AC_MATCH_CHAR(pattern->ch[0], buffer[bp], 1);
1212 if (match)
1213 break;
1214
1215 if (!bp)
1216 return 0;
1217 else
1218 bp--;
1219 }
1220 if (!match)
1221 return 0;
1222 }
1223
1224 return 1;
1225 }
1226
1227 /* state should reset on call, recursion depth = number of alternate specials */
1228 /* each loop iteration starts on the NEXT sequence to validate */
ac_forward_match_branch(const unsigned char * buffer,uint32_t bp,uint32_t offset,uint32_t fileoffset,uint32_t length,const struct cli_ac_patt * pattern,uint32_t pp,uint16_t specialcnt,uint32_t * start,uint32_t * end)1229 static int ac_forward_match_branch(const unsigned char *buffer, uint32_t bp, uint32_t offset, uint32_t fileoffset, uint32_t length,
1230 const struct cli_ac_patt *pattern, uint32_t pp, uint16_t specialcnt, uint32_t *start, uint32_t *end)
1231 {
1232 int match;
1233 uint16_t wc, i;
1234
1235 match = 1;
1236
1237 /* forward (pattern) validation; determines end */
1238 for (i = pp; i < pattern->length[0] && bp < length; i++) {
1239 AC_MATCH_CHAR(pattern->pattern[i], buffer[bp], 0);
1240 if (!match)
1241 return 0;
1242
1243 bp++;
1244 }
1245 *end = bp;
1246
1247 /* right-side special checks, bp = end */
1248 if (pattern->boundary & AC_BOUNDARY_RIGHT) {
1249 match = !!(pattern->boundary & AC_BOUNDARY_RIGHT_NEGATIVE);
1250 if ((length <= SCANBUFF) && (bp == length || boundary[buffer[bp]] >= 2))
1251 match = !match;
1252
1253 if (!match)
1254 return 0;
1255 }
1256
1257 if (pattern->boundary & AC_LINE_MARKER_RIGHT) {
1258 match = !!(pattern->boundary & AC_LINE_MARKER_RIGHT_NEGATIVE);
1259 if ((length <= SCANBUFF) && (bp == length || buffer[bp] == '\n' || (buffer[bp] == '\r' && bp + 1 < length && buffer[bp + 1] == '\n')))
1260 match = !match;
1261
1262 if (!match)
1263 return 0;
1264 }
1265
1266 if (pattern->boundary & AC_WORD_MARKER_RIGHT) {
1267 match = !!(pattern->boundary & AC_WORD_MARKER_RIGHT_NEGATIVE);
1268 if (length <= SCANBUFF) {
1269 if (bp == length)
1270 match = !match;
1271 else if ((pattern->sigopts & ACPATT_OPTION_WIDE) && (bp + 1 < length)) {
1272 if (!(isalnum(buffer[bp]) && buffer[bp + 1] == '\0'))
1273 match = !match;
1274 } else if (!isalnum(buffer[bp]))
1275 match = !match;
1276 }
1277
1278 if (!match)
1279 return 0;
1280 }
1281
1282 /* bp is shifted for right anchor check, thus invalidated as pattern right-side */
1283 if (!(pattern->ch[1] & CLI_MATCH_IGNORE)) {
1284 bp += pattern->ch_mindist[1];
1285
1286 for (i = pattern->ch_mindist[1]; i <= pattern->ch_maxdist[1]; i++) {
1287 if (bp >= length)
1288 return 0;
1289
1290 match = 1;
1291 AC_MATCH_CHAR(pattern->ch[1], buffer[bp], 0);
1292 if (match)
1293 break;
1294
1295 bp++;
1296 }
1297
1298 if (!match)
1299 return 0;
1300 }
1301
1302 return ac_backward_match_branch(buffer, offset - 1, offset, fileoffset, length, pattern, pattern->prefix_length[0] - 1, pattern->special_pattern - 1, start, end);
1303 }
1304
ac_findmatch(const unsigned char * buffer,uint32_t offset,uint32_t fileoffset,uint32_t length,const struct cli_ac_patt * pattern,uint32_t * start,uint32_t * end)1305 inline static int ac_findmatch(const unsigned char *buffer, uint32_t offset, uint32_t fileoffset, uint32_t length, const struct cli_ac_patt *pattern, uint32_t *start, uint32_t *end)
1306 {
1307 int match;
1308 uint16_t specialcnt = pattern->special_pattern;
1309
1310 /* minimal check as the maximum variable length may exceed the buffer */
1311 if ((offset + pattern->length[1] > length) || (pattern->prefix_length[1] > offset))
1312 return 0;
1313
1314 match = ac_forward_match_branch(buffer, offset + pattern->depth, offset, fileoffset, length, pattern, pattern->depth, specialcnt, start, end);
1315 if (match)
1316 return 1;
1317 return 0;
1318 }
1319
cli_ac_initdata(struct cli_ac_data * data,uint32_t partsigs,uint32_t lsigs,uint32_t reloffsigs,uint8_t tracklen)1320 cl_error_t cli_ac_initdata(struct cli_ac_data *data, uint32_t partsigs, uint32_t lsigs, uint32_t reloffsigs, uint8_t tracklen)
1321 {
1322 unsigned int i, j;
1323
1324 UNUSEDPARAM(tracklen);
1325
1326 if (!data) {
1327 cli_errmsg("cli_ac_init: data == NULL\n");
1328 return CL_ENULLARG;
1329 }
1330 memset((void *)data, 0, sizeof(struct cli_ac_data));
1331
1332 data->reloffsigs = reloffsigs;
1333 if (reloffsigs) {
1334 data->offset = (uint32_t *)cli_malloc(reloffsigs * 2 * sizeof(uint32_t));
1335 if (!data->offset) {
1336 cli_errmsg("cli_ac_init: Can't allocate memory for data->offset\n");
1337 return CL_EMEM;
1338 }
1339 for (i = 0; i < reloffsigs * 2; i += 2)
1340 data->offset[i] = CLI_OFF_NONE;
1341 }
1342
1343 data->partsigs = partsigs;
1344 if (partsigs) {
1345 data->offmatrix = (uint32_t ***)cli_calloc(partsigs, sizeof(uint32_t **));
1346 if (!data->offmatrix) {
1347 cli_errmsg("cli_ac_init: Can't allocate memory for data->offmatrix\n");
1348
1349 if (reloffsigs)
1350 free(data->offset);
1351
1352 return CL_EMEM;
1353 }
1354 }
1355
1356 data->lsigs = lsigs;
1357 if (lsigs) {
1358 data->lsigcnt = (uint32_t **)cli_malloc(lsigs * sizeof(uint32_t *));
1359 if (!data->lsigcnt) {
1360 if (partsigs)
1361 free(data->offmatrix);
1362
1363 if (reloffsigs)
1364 free(data->offset);
1365
1366 cli_errmsg("cli_ac_init: Can't allocate memory for data->lsigcnt\n");
1367 return CL_EMEM;
1368 }
1369 data->lsigcnt[0] = (uint32_t *)cli_calloc(lsigs * 64, sizeof(uint32_t));
1370 if (!data->lsigcnt[0]) {
1371 free(data->lsigcnt);
1372 if (partsigs)
1373 free(data->offmatrix);
1374
1375 if (reloffsigs)
1376 free(data->offset);
1377
1378 cli_errmsg("cli_ac_init: Can't allocate memory for data->lsigcnt[0]\n");
1379 return CL_EMEM;
1380 }
1381 for (i = 1; i < lsigs; i++)
1382 data->lsigcnt[i] = data->lsigcnt[0] + 64 * i;
1383 data->yr_matches = (uint8_t *)cli_calloc(lsigs, sizeof(uint8_t));
1384 if (data->yr_matches == NULL) {
1385 free(data->lsigcnt[0]);
1386 free(data->lsigcnt);
1387 if (partsigs)
1388 free(data->offmatrix);
1389
1390 if (reloffsigs)
1391 free(data->offset);
1392 return CL_EMEM;
1393 }
1394
1395 /* subsig offsets */
1396 data->lsig_matches = (struct cli_lsig_matches **)cli_calloc(lsigs, sizeof(struct cli_lsig_matches *));
1397 if (!data->lsig_matches) {
1398 free(data->yr_matches);
1399 free(data->lsigcnt[0]);
1400 free(data->lsigcnt);
1401 if (partsigs)
1402 free(data->offmatrix);
1403
1404 if (reloffsigs)
1405 free(data->offset);
1406
1407 cli_errmsg("cli_ac_init: Can't allocate memory for data->lsig_matches\n");
1408 return CL_EMEM;
1409 }
1410 data->lsigsuboff_last = (uint32_t **)cli_malloc(lsigs * sizeof(uint32_t *));
1411 data->lsigsuboff_first = (uint32_t **)cli_malloc(lsigs * sizeof(uint32_t *));
1412 if (!data->lsigsuboff_last || !data->lsigsuboff_first) {
1413 free(data->lsig_matches);
1414 free(data->lsigsuboff_last);
1415 free(data->lsigsuboff_first);
1416 free(data->yr_matches);
1417 free(data->lsigcnt[0]);
1418 free(data->lsigcnt);
1419 if (partsigs)
1420 free(data->offmatrix);
1421
1422 if (reloffsigs)
1423 free(data->offset);
1424
1425 cli_errmsg("cli_ac_init: Can't allocate memory for data->lsigsuboff_(last|first)\n");
1426 return CL_EMEM;
1427 }
1428 data->lsigsuboff_last[0] = (uint32_t *)cli_calloc(lsigs * 64, sizeof(uint32_t));
1429 data->lsigsuboff_first[0] = (uint32_t *)cli_calloc(lsigs * 64, sizeof(uint32_t));
1430 if (!data->lsigsuboff_last[0] || !data->lsigsuboff_first[0]) {
1431 free(data->lsig_matches);
1432 free(data->lsigsuboff_last[0]);
1433 free(data->lsigsuboff_first[0]);
1434 free(data->lsigsuboff_last);
1435 free(data->lsigsuboff_first);
1436 free(data->yr_matches);
1437 free(data->lsigcnt[0]);
1438 free(data->lsigcnt);
1439 if (partsigs)
1440 free(data->offmatrix);
1441
1442 if (reloffsigs)
1443 free(data->offset);
1444
1445 cli_errmsg("cli_ac_init: Can't allocate memory for data->lsigsuboff_(last|first)[0]\n");
1446 return CL_EMEM;
1447 }
1448 for (j = 0; j < 64; j++) {
1449 data->lsigsuboff_last[0][j] = CLI_OFF_NONE;
1450 data->lsigsuboff_first[0][j] = CLI_OFF_NONE;
1451 }
1452 for (i = 1; i < lsigs; i++) {
1453 data->lsigsuboff_last[i] = data->lsigsuboff_last[0] + 64 * i;
1454 data->lsigsuboff_first[i] = data->lsigsuboff_first[0] + 64 * i;
1455 for (j = 0; j < 64; j++) {
1456 data->lsigsuboff_last[i][j] = CLI_OFF_NONE;
1457 data->lsigsuboff_first[i][j] = CLI_OFF_NONE;
1458 }
1459 }
1460 }
1461 for (i = 0; i < 32; i++)
1462 data->macro_lastmatch[i] = CLI_OFF_NONE;
1463
1464 data->min_partno = 1;
1465
1466 return CL_SUCCESS;
1467 }
1468
cli_ac_caloff(const struct cli_matcher * root,struct cli_ac_data * data,const struct cli_target_info * info)1469 cl_error_t cli_ac_caloff(const struct cli_matcher *root, struct cli_ac_data *data, const struct cli_target_info *info)
1470 {
1471 int ret;
1472 unsigned int i;
1473 struct cli_ac_patt *patt;
1474
1475 if (info)
1476 data->vinfo = &info->exeinfo.vinfo;
1477
1478 for (i = 0; i < root->ac_reloff_num; i++) {
1479 patt = root->ac_reloff[i];
1480 if (!info) {
1481 data->offset[patt->offset_min] = CLI_OFF_NONE;
1482 } else if ((ret = cli_caloff(NULL, info, root->type, patt->offdata, &data->offset[patt->offset_min], &data->offset[patt->offset_max]))) {
1483 cli_errmsg("cli_ac_caloff: Can't calculate relative offset in signature for %s\n", patt->virname);
1484 return ret;
1485 } else if ((data->offset[patt->offset_min] != CLI_OFF_NONE) && (data->offset[patt->offset_min] + patt->length[1] > info->fsize)) {
1486 data->offset[patt->offset_min] = CLI_OFF_NONE;
1487 }
1488 }
1489
1490 return CL_SUCCESS;
1491 }
1492
cli_ac_freedata(struct cli_ac_data * data)1493 void cli_ac_freedata(struct cli_ac_data *data)
1494 {
1495 uint32_t i;
1496
1497 if (!data)
1498 return;
1499
1500 if (data->partsigs) {
1501 for (i = 0; i < data->partsigs; i++) {
1502 if (data->offmatrix[i]) {
1503 free(data->offmatrix[i][0]);
1504 free(data->offmatrix[i]);
1505 }
1506 }
1507 free(data->offmatrix);
1508 data->offmatrix = NULL;
1509 data->partsigs = 0;
1510 }
1511
1512 if (data->lsigs) {
1513 if (data->lsig_matches) {
1514 for (i = 0; i < data->lsigs; i++) {
1515 struct cli_lsig_matches *ls_matches;
1516 if ((ls_matches = data->lsig_matches[i])) {
1517 uint32_t j;
1518 for (j = 0; j < ls_matches->subsigs; j++) {
1519 if (ls_matches->matches[j]) {
1520 free(ls_matches->matches[j]);
1521 ls_matches->matches[j] = 0;
1522 }
1523 }
1524 free(data->lsig_matches[i]);
1525 data->lsig_matches[i] = 0;
1526 }
1527 }
1528 free(data->lsig_matches);
1529 data->lsig_matches = 0;
1530 }
1531 free(data->yr_matches);
1532 free(data->lsigcnt[0]);
1533 free(data->lsigcnt);
1534 free(data->lsigsuboff_last[0]);
1535 free(data->lsigsuboff_last);
1536 free(data->lsigsuboff_first[0]);
1537 free(data->lsigsuboff_first);
1538 data->lsigs = 0;
1539 }
1540
1541 if (data->reloffsigs) {
1542 free(data->offset);
1543 data->reloffsigs = 0;
1544 }
1545 }
1546
1547 /* returns only CL_SUCCESS or CL_EMEM */
ac_addtype(struct cli_matched_type ** list,cli_file_t type,off_t offset,const cli_ctx * ctx)1548 inline static int ac_addtype(struct cli_matched_type **list, cli_file_t type, off_t offset, const cli_ctx *ctx)
1549 {
1550 struct cli_matched_type *tnode, *tnode_last;
1551
1552 if (type == CL_TYPE_ZIPSFX) {
1553 if (*list && ctx && ctx->engine->maxfiles && (*list)->cnt > ctx->engine->maxfiles)
1554 return CL_SUCCESS;
1555 } else if (*list && (*list)->cnt >= MAX_EMBEDDED_OBJ) {
1556 return CL_SUCCESS;
1557 }
1558
1559 if (!(tnode = cli_calloc(1, sizeof(struct cli_matched_type)))) {
1560 cli_errmsg("cli_ac_addtype: Can't allocate memory for new type node\n");
1561 return CL_EMEM;
1562 }
1563
1564 tnode->type = type;
1565 tnode->offset = offset;
1566
1567 tnode_last = *list;
1568 while (tnode_last && tnode_last->next)
1569 tnode_last = tnode_last->next;
1570
1571 if (tnode_last)
1572 tnode_last->next = tnode;
1573 else
1574 *list = tnode;
1575
1576 (*list)->cnt++;
1577 return CL_SUCCESS;
1578 }
1579
lsig_sub_matched(const struct cli_matcher * root,struct cli_ac_data * mdata,uint32_t lsigid1,uint32_t lsigid2,uint32_t realoff,int partial)1580 cl_error_t lsig_sub_matched(const struct cli_matcher *root, struct cli_ac_data *mdata, uint32_t lsigid1, uint32_t lsigid2, uint32_t realoff, int partial)
1581 {
1582 const struct cli_ac_lsig *ac_lsig = root->ac_lsigtable[lsigid1];
1583 const struct cli_lsig_tdb *tdb = &ac_lsig->tdb;
1584
1585 if (realoff != CLI_OFF_NONE) {
1586 if (mdata->lsigsuboff_first[lsigid1][lsigid2] == CLI_OFF_NONE)
1587 mdata->lsigsuboff_first[lsigid1][lsigid2] = realoff;
1588
1589 if (mdata->lsigsuboff_last[lsigid1][lsigid2] != CLI_OFF_NONE && ((!partial && realoff <= mdata->lsigsuboff_last[lsigid1][lsigid2]) || (partial && realoff < mdata->lsigsuboff_last[lsigid1][lsigid2])))
1590 return CL_SUCCESS;
1591
1592 mdata->lsigcnt[lsigid1][lsigid2]++;
1593 if (mdata->lsigcnt[lsigid1][lsigid2] <= 1 || !tdb->macro_ptids || !tdb->macro_ptids[lsigid2])
1594 mdata->lsigsuboff_last[lsigid1][lsigid2] = realoff;
1595 }
1596
1597 if (ac_lsig->type & CLI_YARA_OFFSET && realoff != CLI_OFF_NONE) {
1598 struct cli_subsig_matches *ss_matches;
1599 struct cli_lsig_matches *ls_matches;
1600 cli_dbgmsg("lsig_sub_matched lsig %u:%u at %u\n", lsigid1, lsigid2, realoff);
1601
1602 ls_matches = mdata->lsig_matches[lsigid1];
1603 if (ls_matches == NULL) { /* allocate cli_lsig_matches */
1604 ls_matches = mdata->lsig_matches[lsigid1] = (struct cli_lsig_matches *)cli_calloc(1, sizeof(struct cli_lsig_matches) +
1605 (ac_lsig->tdb.subsigs - 1) * sizeof(struct cli_subsig_matches *));
1606 if (ls_matches == NULL) {
1607 cli_errmsg("lsig_sub_matched: cli_calloc failed for cli_lsig_matches\n");
1608 return CL_EMEM;
1609 }
1610 ls_matches->subsigs = ac_lsig->tdb.subsigs;
1611 }
1612 ss_matches = ls_matches->matches[lsigid2];
1613 if (ss_matches == NULL) { /* allocate cli_subsig_matches */
1614 ss_matches = ls_matches->matches[lsigid2] = cli_malloc(sizeof(struct cli_subsig_matches));
1615 if (ss_matches == NULL) {
1616 cli_errmsg("lsig_sub_matched: cli_malloc failed for cli_subsig_matches struct\n");
1617 return CL_EMEM;
1618 }
1619 ss_matches->next = 0;
1620 ss_matches->last = sizeof(ss_matches->offsets) / sizeof(uint32_t) - 1;
1621 }
1622 if (ss_matches->next > ss_matches->last) { /* cli_matches out of space? realloc */
1623 ss_matches = ls_matches->matches[lsigid2] = cli_realloc(ss_matches, sizeof(struct cli_subsig_matches) + sizeof(uint32_t) * ss_matches->last * 2);
1624 if (ss_matches == NULL) {
1625 cli_errmsg("lsig_sub_matched: cli_realloc failed for cli_subsig_matches struct\n");
1626 return CL_EMEM;
1627 }
1628 ss_matches->last = sizeof(ss_matches->offsets) / sizeof(uint32_t) + ss_matches->last * 2 - 1;
1629 }
1630
1631 ss_matches->offsets[ss_matches->next] = realoff; /* finally, store the offset */
1632 ss_matches->next++;
1633 }
1634
1635 if (mdata->lsigcnt[lsigid1][lsigid2] > 1) {
1636 /* Check that the previous match had a macro match following it at the
1637 * correct distance. This check is only done after the 1st match.*/
1638 const struct cli_ac_patt *macropt;
1639 uint32_t id, last_macro_match, smin, smax, last_macroprev_match;
1640
1641 if (!tdb->macro_ptids)
1642 return CL_SUCCESS;
1643
1644 id = tdb->macro_ptids[lsigid2];
1645 if (!id)
1646 return CL_SUCCESS;
1647
1648 macropt = root->ac_pattable[id];
1649 smin = macropt->ch_mindist[0];
1650 smax = macropt->ch_maxdist[0];
1651 /* start of last macro match */
1652 last_macro_match = mdata->macro_lastmatch[macropt->sigid];
1653 /* start of previous lsig subsig match */
1654 last_macroprev_match = mdata->lsigsuboff_last[lsigid1][lsigid2];
1655 if (last_macro_match != CLI_OFF_NONE)
1656 cli_dbgmsg("Checking macro match: %u + (%u - %u) == %u\n",
1657 last_macroprev_match, smin, smax, last_macro_match);
1658
1659 if (last_macro_match == CLI_OFF_NONE ||
1660 last_macroprev_match + smin > last_macro_match ||
1661 last_macroprev_match + smax < last_macro_match) {
1662 cli_dbgmsg("Canceled false lsig macro match\n");
1663 /* Previous match was false - cancel it */
1664 mdata->lsigcnt[lsigid1][lsigid2]--;
1665 mdata->lsigsuboff_last[lsigid1][lsigid2] = realoff;
1666 } else {
1667 /* mark the macro sig itself matched */
1668 mdata->lsigcnt[lsigid1][lsigid2 + 1]++;
1669 mdata->lsigsuboff_last[lsigid1][lsigid2 + 1] = last_macro_match;
1670 }
1671 }
1672 return CL_SUCCESS;
1673 }
1674
cli_ac_chkmacro(struct cli_matcher * root,struct cli_ac_data * data,unsigned lsigid1)1675 cl_error_t cli_ac_chkmacro(struct cli_matcher *root, struct cli_ac_data *data, unsigned lsigid1)
1676 {
1677 const struct cli_lsig_tdb *tdb = &root->ac_lsigtable[lsigid1]->tdb;
1678 unsigned i;
1679 cl_error_t rc;
1680
1681 /* Loop through all subsigs, and if they are tied to macros check that the
1682 * macro matched at a correct distance */
1683 for (i = 0; i < tdb->subsigs; i++) {
1684 rc = lsig_sub_matched(root, data, lsigid1, i, CLI_OFF_NONE, 0);
1685 if (rc != CL_SUCCESS)
1686 return rc;
1687 }
1688 return CL_SUCCESS;
1689 }
1690
cli_ac_scanbuff(const unsigned char * buffer,uint32_t length,const char ** virname,void ** customdata,struct cli_ac_result ** res,const struct cli_matcher * root,struct cli_ac_data * mdata,uint32_t offset,cli_file_t ftype,struct cli_matched_type ** ftoffset,unsigned int mode,cli_ctx * ctx)1691 cl_error_t cli_ac_scanbuff(
1692 const unsigned char *buffer,
1693 uint32_t length,
1694 const char **virname,
1695 void **customdata,
1696 struct cli_ac_result **res,
1697 const struct cli_matcher *root,
1698 struct cli_ac_data *mdata,
1699 uint32_t offset,
1700 cli_file_t ftype,
1701 struct cli_matched_type **ftoffset,
1702 unsigned int mode,
1703 cli_ctx *ctx)
1704 {
1705 struct cli_ac_node *current;
1706 struct cli_ac_list *pattN, *ptN;
1707 struct cli_ac_patt *patt, *pt;
1708 uint32_t i, bp, exptoff[2], realoff, matchstart, matchend;
1709 uint16_t j;
1710 uint8_t found, viruses_found = 0;
1711 uint32_t **offmatrix, swp;
1712 int type = CL_CLEAN;
1713 struct cli_ac_result *newres;
1714 cl_error_t rc;
1715 cl_error_t ret;
1716
1717 if (!root->ac_root)
1718 return CL_CLEAN;
1719
1720 if (!mdata && (root->ac_partsigs || root->ac_lsigs || root->ac_reloff_num)) {
1721 cli_errmsg("cli_ac_scanbuff: mdata == NULL\n");
1722 return CL_ENULLARG;
1723 }
1724
1725 current = root->ac_root;
1726
1727 for (i = 0; i < length; i++) {
1728 current = current->trans[buffer[i]];
1729
1730 if (UNLIKELY(IS_FINAL(current))) {
1731 struct cli_ac_list *faillist = current->fail->list;
1732 pattN = current->list;
1733 while (pattN) {
1734 patt = pattN->me;
1735 if (patt->partno > mdata->min_partno) {
1736 pattN = faillist;
1737 faillist = NULL;
1738 continue;
1739 }
1740 bp = i + 1 - patt->depth;
1741 if (patt->offdata[0] != CLI_OFF_VERSION && patt->offdata[0] != CLI_OFF_MACRO && !pattN->next_same && (patt->offset_min != CLI_OFF_ANY) && (!patt->sigid || patt->partno == 1)) {
1742 if (patt->offset_min == CLI_OFF_NONE) {
1743 pattN = pattN->next;
1744 continue;
1745 }
1746 exptoff[0] = offset + bp - patt->prefix_length[2]; /* lower offset end */
1747 exptoff[1] = offset + bp - patt->prefix_length[1]; /* higher offset end */
1748 if (patt->offdata[0] == CLI_OFF_ABSOLUTE) {
1749 if (patt->offset_max < exptoff[0] || patt->offset_min > exptoff[1]) {
1750 pattN = pattN->next;
1751 continue;
1752 }
1753 } else {
1754 if (mdata->offset[patt->offset_min] == CLI_OFF_NONE || mdata->offset[patt->offset_max] < exptoff[0] || mdata->offset[patt->offset_min] > exptoff[1]) {
1755 pattN = pattN->next;
1756 continue;
1757 }
1758 }
1759 }
1760
1761 ptN = pattN;
1762 if (ac_findmatch(buffer, bp, offset + bp, length, patt, &matchstart, &matchend)) {
1763 while (ptN) {
1764 pt = ptN->me;
1765 if (pt->partno > mdata->min_partno)
1766 break;
1767
1768 if ((pt->type && !(mode & AC_SCAN_FT)) || (!pt->type && !(mode & AC_SCAN_VIR))) {
1769 ptN = ptN->next_same;
1770 continue;
1771 }
1772
1773 realoff = offset + matchstart;
1774 if (pt->offdata[0] == CLI_OFF_VERSION) {
1775 if (!cli_hashset_contains_maybe_noalloc(mdata->vinfo, realoff)) {
1776 ptN = ptN->next_same;
1777 continue;
1778 }
1779 cli_dbgmsg("cli_ac_scanbuff: VI match for offset %x\n", realoff);
1780 } else if (pt->offdata[0] == CLI_OFF_MACRO) {
1781 mdata->macro_lastmatch[patt->offdata[1]] = realoff;
1782 ptN = ptN->next_same;
1783 continue;
1784 } else if (pt->offset_min != CLI_OFF_ANY && (!pt->sigid || pt->partno == 1)) {
1785 if (pt->offset_min == CLI_OFF_NONE) {
1786 ptN = ptN->next_same;
1787 continue;
1788 }
1789 if (pt->offdata[0] == CLI_OFF_ABSOLUTE) {
1790 if (pt->offset_max < realoff || pt->offset_min > realoff) {
1791 ptN = ptN->next_same;
1792 continue;
1793 }
1794 } else {
1795 if (mdata->offset[pt->offset_min] == CLI_OFF_NONE || mdata->offset[pt->offset_max] < realoff || mdata->offset[pt->offset_min] > realoff) {
1796 ptN = ptN->next_same;
1797 continue;
1798 }
1799 }
1800 }
1801
1802 if (pt->sigid) { /* it's a partial signature */
1803
1804 /* if 2nd or later part, confirm some prior part has matched */
1805 if (pt->partno != 1 && (!mdata->offmatrix[pt->sigid - 1] || !mdata->offmatrix[pt->sigid - 1][pt->partno - 2][0])) {
1806 ptN = ptN->next_same;
1807 continue;
1808 }
1809
1810 if (pt->partno + 1 > mdata->min_partno)
1811 mdata->min_partno = pt->partno + 1;
1812
1813 /* sparsely populated matrix, so allocate and initialize if NULL */
1814 if (!mdata->offmatrix[pt->sigid - 1]) {
1815 mdata->offmatrix[pt->sigid - 1] = cli_malloc(pt->parts * sizeof(int32_t *));
1816 if (!mdata->offmatrix[pt->sigid - 1]) {
1817 cli_errmsg("cli_ac_scanbuff: Can't allocate memory for mdata->offmatrix[%u]\n", pt->sigid - 1);
1818 return CL_EMEM;
1819 }
1820
1821 mdata->offmatrix[pt->sigid - 1][0] = cli_malloc(pt->parts * (CLI_DEFAULT_AC_TRACKLEN + 2) * sizeof(uint32_t));
1822 if (!mdata->offmatrix[pt->sigid - 1][0]) {
1823 cli_errmsg("cli_ac_scanbuff: Can't allocate memory for mdata->offmatrix[%u][0]\n", pt->sigid - 1);
1824 free(mdata->offmatrix[pt->sigid - 1]);
1825 mdata->offmatrix[pt->sigid - 1] = NULL;
1826 return CL_EMEM;
1827 }
1828 memset(mdata->offmatrix[pt->sigid - 1][0], (uint32_t)-1, pt->parts * (CLI_DEFAULT_AC_TRACKLEN + 2) * sizeof(uint32_t));
1829 mdata->offmatrix[pt->sigid - 1][0][0] = 0;
1830 for (j = 1; j < pt->parts; j++) {
1831 mdata->offmatrix[pt->sigid - 1][j] = mdata->offmatrix[pt->sigid - 1][0] + j * (CLI_DEFAULT_AC_TRACKLEN + 2);
1832 mdata->offmatrix[pt->sigid - 1][j][0] = 0;
1833 }
1834 }
1835 offmatrix = mdata->offmatrix[pt->sigid - 1];
1836
1837 found = 0;
1838 if (pt->partno != 1) {
1839 for (j = 1; (j <= CLI_DEFAULT_AC_TRACKLEN + 1) && (offmatrix[pt->partno - 2][j] != (uint32_t)-1); j++) {
1840 found = j;
1841 if (realoff < offmatrix[pt->partno - 2][j])
1842 found = 0;
1843
1844 if (found && pt->maxdist)
1845 if (realoff - offmatrix[pt->partno - 2][j] > pt->maxdist)
1846 found = 0;
1847
1848 if (found && pt->mindist)
1849 if (realoff - offmatrix[pt->partno - 2][j] < pt->mindist)
1850 found = 0;
1851
1852 if (found)
1853 break;
1854 }
1855 }
1856
1857 if (pt->partno == 2 && found > 1) {
1858 swp = offmatrix[0][1];
1859 offmatrix[0][1] = offmatrix[0][found];
1860 offmatrix[0][found] = swp;
1861
1862 if (pt->type != CL_TYPE_MSEXE) {
1863 swp = offmatrix[pt->parts - 1][1];
1864 offmatrix[pt->parts - 1][1] = offmatrix[pt->parts - 1][found];
1865 offmatrix[pt->parts - 1][found] = swp;
1866 }
1867 }
1868
1869 if (pt->partno == 1 || (found && (pt->partno != pt->parts))) {
1870 if (offmatrix[pt->partno - 1][0] == CLI_DEFAULT_AC_TRACKLEN + 1)
1871 offmatrix[pt->partno - 1][0] = 1; /* wrap, ends up at 2 */
1872 offmatrix[pt->partno - 1][0]++;
1873 offmatrix[pt->partno - 1][offmatrix[pt->partno - 1][0]] = offset + matchend;
1874
1875 if (pt->partno == 1) /* save realoff for the first part */
1876 offmatrix[pt->parts - 1][offmatrix[pt->partno - 1][0]] = realoff;
1877 } else if (found && pt->partno == pt->parts) {
1878 if (pt->type) {
1879
1880 if (pt->type == CL_TYPE_IGNORED && (!pt->rtype || ftype == pt->rtype))
1881 return CL_TYPE_IGNORED;
1882
1883 if ((pt->type > type || pt->type >= CL_TYPE_SFX || pt->type == CL_TYPE_MSEXE) && (!pt->rtype || ftype == pt->rtype)) {
1884 cli_dbgmsg("Matched signature for file type %s\n", pt->virname);
1885 type = pt->type;
1886 if (ftoffset &&
1887 (!*ftoffset || (*ftoffset)->cnt < MAX_EMBEDDED_OBJ || type == CL_TYPE_ZIPSFX) &&
1888 (type >= CL_TYPE_SFX || ((ftype == CL_TYPE_MSEXE || ftype == CL_TYPE_ZIP || ftype == CL_TYPE_MSOLE2) && type == CL_TYPE_MSEXE))) {
1889 /* FIXME: the first offset in the array is most likely the correct one but
1890 * it may happen it is not
1891 */
1892 for (j = 1; j <= CLI_DEFAULT_AC_TRACKLEN + 1 && offmatrix[0][j] != (uint32_t)-1; j++)
1893 if (ac_addtype(ftoffset, type, offmatrix[pt->parts - 1][j], ctx))
1894 return CL_EMEM;
1895 }
1896
1897 memset(offmatrix[0], (uint32_t)-1, pt->parts * (CLI_DEFAULT_AC_TRACKLEN + 2) * sizeof(uint32_t));
1898 for (j = 0; j < pt->parts; j++)
1899 offmatrix[j][0] = 0;
1900 }
1901
1902 } else { /* !pt->type */
1903 if (pt->lsigid[0]) {
1904 rc = lsig_sub_matched(root, mdata, pt->lsigid[1], pt->lsigid[2], offmatrix[pt->parts - 1][1], 1);
1905 if (rc != CL_SUCCESS)
1906 return rc;
1907 ptN = ptN->next_same;
1908 continue;
1909 }
1910
1911 if (res) {
1912 newres = (struct cli_ac_result *)malloc(sizeof(struct cli_ac_result));
1913 if (!newres) {
1914 cli_errmsg("cli_ac_scanbuff: Can't allocate memory for newres %lu\n", (unsigned long)sizeof(struct cli_ac_result));
1915 return CL_EMEM;
1916 }
1917 newres->virname = pt->virname;
1918 newres->customdata = pt->customdata;
1919 newres->next = *res;
1920 newres->offset = (off_t)offmatrix[pt->parts - 1][1];
1921 *res = newres;
1922
1923 ptN = ptN->next_same;
1924 continue;
1925 } else {
1926 if (ctx && SCAN_ALLMATCHES) {
1927 ret = cli_append_virus(ctx, (const char *)pt->virname);
1928 if (ret == CL_VIRUS) {
1929 viruses_found = 1;
1930 }
1931 }
1932 if (virname)
1933 *virname = pt->virname;
1934 if (customdata)
1935 *customdata = pt->customdata;
1936 if (!ctx || !SCAN_ALLMATCHES)
1937 return CL_VIRUS;
1938 ptN = ptN->next_same;
1939 continue;
1940 }
1941 }
1942 }
1943
1944 } else { /* old type signature */
1945 if (pt->type) {
1946 if (pt->type == CL_TYPE_IGNORED && (!pt->rtype || ftype == pt->rtype))
1947 return CL_TYPE_IGNORED;
1948
1949 if ((pt->type > type || pt->type >= CL_TYPE_SFX || pt->type == CL_TYPE_MSEXE) && (!pt->rtype || ftype == pt->rtype)) {
1950
1951 cli_dbgmsg("Matched signature for file type %s at %u\n", pt->virname, realoff);
1952 type = pt->type;
1953 if (ftoffset && (!*ftoffset || (*ftoffset)->cnt < MAX_EMBEDDED_OBJ || type == CL_TYPE_ZIPSFX) && (type == CL_TYPE_MBR || type >= CL_TYPE_SFX || ((ftype == CL_TYPE_MSEXE || ftype == CL_TYPE_ZIP || ftype == CL_TYPE_MSOLE2) && type == CL_TYPE_MSEXE))) {
1954
1955 if (ac_addtype(ftoffset, type, realoff, ctx))
1956 return CL_EMEM;
1957 }
1958 }
1959 } else {
1960 if (pt->lsigid[0]) {
1961 rc = lsig_sub_matched(root, mdata, pt->lsigid[1], pt->lsigid[2], realoff, 0);
1962 if (rc != CL_SUCCESS)
1963 return rc;
1964 ptN = ptN->next_same;
1965 continue;
1966 }
1967
1968 if (res) {
1969 newres = (struct cli_ac_result *)malloc(sizeof(struct cli_ac_result));
1970 if (!newres) {
1971 cli_errmsg("cli_ac_scanbuff: Can't allocate memory for newres %lu\n", (unsigned long)sizeof(struct cli_ac_result));
1972 return CL_EMEM;
1973 }
1974 newres->virname = pt->virname;
1975 newres->customdata = pt->customdata;
1976 newres->offset = (off_t)realoff;
1977 newres->next = *res;
1978 *res = newres;
1979
1980 ptN = ptN->next_same;
1981 continue;
1982 } else {
1983 if (ctx && SCAN_ALLMATCHES) {
1984 ret = cli_append_virus(ctx, (const char *)pt->virname);
1985 if (ret == CL_VIRUS) {
1986 viruses_found = 1;
1987 }
1988 }
1989
1990 if (virname)
1991 *virname = pt->virname;
1992
1993 if (customdata)
1994 *customdata = pt->customdata;
1995
1996 if (!ctx || !SCAN_ALLMATCHES)
1997 return CL_VIRUS;
1998
1999 ptN = ptN->next_same;
2000 continue;
2001 }
2002 }
2003 }
2004 ptN = ptN->next_same;
2005 }
2006 }
2007 pattN = pattN->next;
2008 }
2009 }
2010 }
2011
2012 if (viruses_found)
2013 return CL_VIRUS;
2014
2015 return (mode & AC_SCAN_FT) ? type : CL_CLEAN;
2016 }
2017
qcompare_byte(const void * a,const void * b)2018 static int qcompare_byte(const void *a, const void *b)
2019 {
2020 return *(const unsigned char *)a - *(const unsigned char *)b;
2021 }
2022
qcompare_fstr(const void * arg,const void * a,const void * b)2023 static int qcompare_fstr(const void *arg, const void *a, const void *b)
2024 {
2025 uint16_t len = *(uint16_t *)arg;
2026 return memcmp(*(const unsigned char **)a, *(const unsigned char **)b, len);
2027 }
2028
2029 /* returns if level of nesting, end set to MATCHING paren, start AFTER staring paren */
find_paren_end(char * hexstr,char ** end)2030 inline static size_t find_paren_end(char *hexstr, char **end)
2031 {
2032 size_t i;
2033 size_t nest = 0, level = 0;
2034
2035 *end = NULL;
2036 for (i = 0; i < strlen(hexstr); i++) {
2037 if (hexstr[i] == '(') {
2038 nest++;
2039 level++;
2040 } else if (hexstr[i] == ')') {
2041 if (!level) {
2042 *end = &hexstr[i];
2043 break;
2044 }
2045 level--;
2046 }
2047 }
2048
2049 return nest;
2050 }
2051
2052 /* analyzes expr, returns number of subexpr, if fixed length subexpr and longest subexpr len *
2053 * goes to either end of string or to closing parenthesis; allowed to be unbalanced *
2054 * counts applied to start of expr (not end, i.e. numexpr starts at 1 for the first expr */
ac_analyze_expr(char * hexstr,int * fixed_len,int * sub_len)2055 inline static int ac_analyze_expr(char *hexstr, int *fixed_len, int *sub_len)
2056 {
2057 unsigned long i;
2058 int level = 0, len = 0, numexpr = 1;
2059 int flen, slen;
2060
2061 flen = 1;
2062 slen = 0;
2063 for (i = 0; i < strlen(hexstr); i++) {
2064 if (hexstr[i] == '(') {
2065 flen = 0;
2066 level++;
2067 } else if (hexstr[i] == ')') {
2068 if (!level) {
2069 if (!slen) {
2070 slen = len;
2071 } else if (len != slen) {
2072 flen = 0;
2073 if (len > slen)
2074 slen = len;
2075 }
2076 break;
2077 }
2078 level--;
2079 }
2080 if (!level && hexstr[i] == '|') {
2081 if (!slen) {
2082 slen = len;
2083 } else if (len != slen) {
2084 flen = 0;
2085 if (len > slen)
2086 slen = len;
2087 }
2088 len = 0;
2089 numexpr++;
2090 } else {
2091 if (hexstr[i] == '?')
2092 flen = 0;
2093 len++;
2094 }
2095 }
2096 if (!slen) {
2097 slen = len;
2098 } else if (len != slen) {
2099 flen = 0;
2100 if (len > slen)
2101 slen = len;
2102 }
2103
2104 if (sub_len)
2105 *sub_len = slen;
2106 if (fixed_len)
2107 *fixed_len = flen;
2108
2109 return numexpr;
2110 }
2111
ac_uicmp(uint16_t * a,size_t alen,uint16_t * b,size_t blen,int * wild)2112 inline static int ac_uicmp(uint16_t *a, size_t alen, uint16_t *b, size_t blen, int *wild)
2113 {
2114 uint16_t awild, bwild, side_wild;
2115 size_t i, minlen = MIN(alen, blen);
2116
2117 side_wild = 0;
2118
2119 for (i = 0; i < minlen; i++) {
2120 awild = a[i] & CLI_MATCH_WILDCARD;
2121 bwild = b[i] & CLI_MATCH_WILDCARD;
2122
2123 if (awild == bwild) {
2124 switch (awild) {
2125 case CLI_MATCH_CHAR:
2126 if ((a[i] & 0xff) != (b[i] & 0xff)) {
2127 return (b[i] & 0xff) - (a[i] & 0xff);
2128 }
2129 break;
2130 case CLI_MATCH_IGNORE:
2131 break;
2132 case CLI_MATCH_NIBBLE_HIGH:
2133 if ((a[i] & 0xf0) != (b[i] & 0xf0)) {
2134 return (b[i] & 0xf0) - (a[i] & 0xf0);
2135 }
2136 break;
2137 case CLI_MATCH_NIBBLE_LOW:
2138 if ((a[i] & 0x0f) != (b[i] & 0x0f)) {
2139 return (b[i] & 0x0f) - (a[i] & 0x0f);
2140 }
2141 break;
2142 default:
2143 cli_errmsg("ac_uicmp: unhandled wildcard type\n");
2144 return 1;
2145 }
2146 } else { /* not identical wildcard types */
2147 if (awild == CLI_MATCH_CHAR) { /* b is only wild */
2148 switch (bwild) {
2149 case CLI_MATCH_IGNORE:
2150 side_wild |= 2;
2151 break;
2152 case CLI_MATCH_NIBBLE_HIGH:
2153 if ((a[i] & 0xf0) != (b[i] & 0xf0)) {
2154 return (b[i] & 0xf0) - (a[i] & 0xff);
2155 }
2156 side_wild |= 2;
2157 break;
2158 case CLI_MATCH_NIBBLE_LOW:
2159 if ((a[i] & 0x0f) != (b[i] & 0x0f)) {
2160 return (b[i] & 0x0f) - (a[i] & 0xff);
2161 }
2162 side_wild |= 2;
2163 break;
2164 default:
2165 cli_errmsg("ac_uicmp: unhandled wildcard type\n");
2166 return -1;
2167 }
2168 } else if (bwild == CLI_MATCH_CHAR) { /* a is only wild */
2169 switch (awild) {
2170 case CLI_MATCH_IGNORE:
2171 side_wild |= 1;
2172 break;
2173 case CLI_MATCH_NIBBLE_HIGH:
2174 if ((a[i] & 0xf0) != (b[i] & 0xf0)) {
2175 return (b[i] & 0xff) - (a[i] & 0xf0);
2176 }
2177 side_wild |= 1;
2178 break;
2179 case CLI_MATCH_NIBBLE_LOW:
2180 if ((a[i] & 0x0f) != (b[i] & 0x0f)) {
2181 return (b[i] & 0xff) - (a[i] & 0x0f);
2182 }
2183 side_wild |= 1;
2184 break;
2185 default:
2186 cli_errmsg("ac_uicmp: unhandled wild typing\n");
2187 return 1;
2188 }
2189 } else { /* not identical, both wildcards */
2190 if (awild == CLI_MATCH_IGNORE || bwild == CLI_MATCH_IGNORE) {
2191 if (awild == CLI_MATCH_IGNORE) {
2192 side_wild |= 1;
2193 } else if (bwild == CLI_MATCH_IGNORE) {
2194 side_wild |= 2;
2195 }
2196 } else {
2197 /* only high and low nibbles should be left here */
2198 side_wild |= 3;
2199 }
2200 }
2201 }
2202
2203 /* both sides contain a wildcard that contains the other, therefore unique by wildcards */
2204 if (side_wild == 3)
2205 return 1;
2206 }
2207
2208 if (wild)
2209 *wild = side_wild;
2210 return 0;
2211 }
2212
2213 /* add new generic alternate node to special */
ac_addspecial_add_alt_node(const char * subexpr,uint8_t sigopts,struct cli_ac_special * special,struct cli_matcher * root)2214 inline static int ac_addspecial_add_alt_node(const char *subexpr, uint8_t sigopts, struct cli_ac_special *special, struct cli_matcher *root)
2215 {
2216 struct cli_alt_node *newnode, **prev, *ins;
2217 uint16_t *s;
2218 int i, cmp, wild;
2219
2220 #ifndef USE_MPOOL
2221 UNUSEDPARAM(root);
2222 #endif
2223
2224 newnode = (struct cli_alt_node *)MPOOL_CALLOC(root->mempool, 1, sizeof(struct cli_alt_node));
2225 if (!newnode) {
2226 cli_errmsg("ac_addspecial_add_alt_node: Can't allocate new alternate node\n");
2227 return CL_EMEM;
2228 }
2229
2230 s = CLI_MPOOL_HEX2UI(root->mempool, subexpr);
2231 if (!s) {
2232 MPOOL_FREE(root->mempool, newnode);
2233 return CL_EMALFDB;
2234 }
2235
2236 newnode->str = s;
2237 newnode->len = (uint16_t)strlen(subexpr) / 2;
2238 newnode->unique = 1;
2239
2240 /* setting nocase match */
2241 if (sigopts & ACPATT_OPTION_NOCASE) {
2242 for (i = 0; i < newnode->len; ++i)
2243 if ((newnode->str[i] & CLI_MATCH_METADATA) == CLI_MATCH_CHAR) {
2244 newnode->str[i] = CLI_NOCASE(newnode->str[i] & 0xff);
2245 newnode->str[i] += CLI_MATCH_NOCASE;
2246 }
2247 }
2248
2249 /* search for uniqueness, TODO: directed acyclic word graph */
2250 prev = &((special->alt).v_str);
2251 ins = (special->alt).v_str;
2252 while (ins) {
2253 cmp = ac_uicmp(ins->str, ins->len, newnode->str, newnode->len, &wild);
2254 if (cmp == 0) {
2255 if (newnode->len != ins->len) { /* derivative */
2256 newnode->unique = 0;
2257 ins->unique = 0;
2258 } else if (wild == 0) { /* duplicate */
2259 MPOOL_FREE(root->mempool, newnode);
2260 return CL_SUCCESS;
2261 }
2262 } /* TODO - possible sorting of altstr uniques and derivative groups? */
2263
2264 prev = &(ins->next);
2265 ins = ins->next;
2266 }
2267
2268 *prev = newnode;
2269 newnode->next = ins;
2270 if ((special->num == 0) || (newnode->len < special->len[0]))
2271 special->len[0] = newnode->len;
2272 if ((special->num == 0) || (newnode->len > special->len[1]))
2273 special->len[1] = newnode->len;
2274 special->num++;
2275 return CL_SUCCESS;
2276 }
2277
2278 /* recursive special handler for expanding and adding generic alternates */
ac_special_altexpand(char * hexpr,char * subexpr,uint16_t maxlen,int lvl,int maxlvl,uint8_t sigopts,struct cli_ac_special * special,struct cli_matcher * root)2279 static int ac_special_altexpand(char *hexpr, char *subexpr, uint16_t maxlen, int lvl, int maxlvl, uint8_t sigopts, struct cli_ac_special *special, struct cli_matcher *root)
2280 {
2281 int ret, scnt = 0, numexpr;
2282 char *ept, *sexpr, *end, term;
2283 char *fp;
2284
2285 ept = sexpr = hexpr;
2286 fp = subexpr + strlen(subexpr);
2287
2288 numexpr = ac_analyze_expr(hexpr, NULL, NULL);
2289
2290 /* while there are expressions to resolve */
2291 while (scnt < numexpr) {
2292 scnt++;
2293 while ((*ept != '(') && (*ept != '|') && (*ept != ')') && (*ept != '\0'))
2294 ept++;
2295
2296 /* check for invalid negation */
2297 term = *ept;
2298 if ((*ept == '(') && (ept >= hexpr + 1)) {
2299 if (ept[-1] == '!') {
2300 cli_errmsg("ac_special_altexpand: Generic alternates cannot contain negations\n");
2301 return CL_EMALFDB;
2302 }
2303 }
2304
2305 /* appended token */
2306 *ept = 0;
2307 if (cli_strlcat(subexpr, sexpr, maxlen) >= maxlen) {
2308 cli_errmsg("ac_special_altexpand: Unexpected expression larger than expected\n");
2309 return CL_EMEM;
2310 }
2311
2312 *ept++ = term;
2313 sexpr = ept;
2314
2315 if (term == '|') {
2316 if (lvl == 0) {
2317 if ((ret = ac_addspecial_add_alt_node(subexpr, sigopts, special, root)) != CL_SUCCESS)
2318 return ret;
2319 } else {
2320 find_paren_end(ept, &end);
2321 if (!end) {
2322 cli_errmsg("ac_special_altexpand: Missing closing parenthesis\n");
2323 return CL_EMALFDB;
2324 }
2325 end++;
2326
2327 if ((ret = ac_special_altexpand(end, subexpr, maxlen, lvl - 1, lvl, sigopts, special, root)) != CL_SUCCESS)
2328 return ret;
2329 }
2330
2331 *fp = 0;
2332 } else if (term == ')') {
2333 if (lvl == 0) {
2334 cli_errmsg("ac_special_altexpand: Unexpected closing parenthesis\n");
2335 return CL_EPARSE;
2336 }
2337
2338 if ((ret = ac_special_altexpand(ept, subexpr, maxlen, lvl - 1, lvl, sigopts, special, root)) != CL_SUCCESS)
2339 return ret;
2340 break;
2341 } else if (term == '(') {
2342 int inner, found;
2343 find_paren_end(ept, &end);
2344 if (!end) {
2345 cli_errmsg("ac_special_altexpand: Missing closing parenthesis\n");
2346 return CL_EMALFDB;
2347 }
2348 end++;
2349
2350 if ((ret = ac_special_altexpand(ept, subexpr, maxlen, lvl + 1, lvl + 1, sigopts, special, root)) != CL_SUCCESS)
2351 return ret;
2352
2353 /* move ept to end of current alternate expression (recursive call already populates them) */
2354 ept = end;
2355 inner = 0;
2356 found = 0;
2357 while (!found && *ept != '\0') {
2358 switch (*ept) {
2359 case '|':
2360 if (!inner)
2361 found = 1;
2362 break;
2363 case '(':
2364 inner++;
2365 break;
2366 case ')':
2367 inner--;
2368 break;
2369 }
2370 ept++;
2371 }
2372 if (*ept == '|')
2373 ept++;
2374
2375 sexpr = ept;
2376 *fp = 0;
2377 } else if (term == '\0') {
2378 if ((ret = ac_addspecial_add_alt_node(subexpr, sigopts, special, root)) != CL_SUCCESS)
2379 return ret;
2380 break;
2381 }
2382
2383 if (lvl != maxlvl)
2384 return CL_SUCCESS;
2385 }
2386 if (scnt != numexpr) {
2387 cli_errmsg("ac_addspecial: Mismatch in parsed and expected signature\n");
2388 return CL_EMALFDB;
2389 }
2390
2391 return CL_SUCCESS;
2392 }
2393
2394 /* alternate string specials (so many specials!) */
ac_special_altstr(const char * hexpr,uint8_t sigopts,struct cli_ac_special * special,struct cli_matcher * root)2395 inline static int ac_special_altstr(const char *hexpr, uint8_t sigopts, struct cli_ac_special *special, struct cli_matcher *root)
2396 {
2397 char *hexprcpy, *h, *c;
2398 int i, ret, num, fixed, slen;
2399
2400 if (!(hexprcpy = cli_strdup(hexpr))) {
2401 cli_errmsg("ac_special_altstr: Can't duplicate alternate expression\n");
2402 return CL_EDUP;
2403 }
2404
2405 num = ac_analyze_expr(hexprcpy, &fixed, &slen);
2406
2407 if (!sigopts && fixed) {
2408 special->num = 0;
2409 special->len[0] = special->len[1] = slen / 2;
2410 /* single-bytes are len 2 in hex */
2411 if (slen == 2) {
2412 special->type = AC_SPECIAL_ALT_CHAR;
2413 (special->alt).byte = (unsigned char *)MPOOL_MALLOC(root->mempool, num);
2414 if (!((special->alt).byte)) {
2415 cli_errmsg("cli_ac_special_altstr: Can't allocate newspecial->str\n");
2416 free(hexprcpy);
2417 return CL_EMEM;
2418 }
2419 } else {
2420 special->type = AC_SPECIAL_ALT_STR_FIXED;
2421 (special->alt).f_str = (unsigned char **)MPOOL_MALLOC(root->mempool, num * sizeof(unsigned char *));
2422 if (!((special->alt).f_str)) {
2423 cli_errmsg("cli_ac_special_altstr: Can't allocate newspecial->str\n");
2424 free(hexprcpy);
2425 return CL_EMEM;
2426 }
2427 }
2428
2429 for (i = 0; i < num; i++) {
2430 if (num == 1) {
2431 c = CLI_MPOOL_HEX2STR(root->mempool, hexprcpy);
2432 } else {
2433 if (!(h = cli_strtok(hexprcpy, i, "|"))) {
2434 free(hexprcpy);
2435 return CL_EMEM;
2436 }
2437 c = CLI_MPOOL_HEX2STR(root->mempool, h);
2438 free(h);
2439 }
2440 if (!c) {
2441 free(hexprcpy);
2442 return CL_EMALFDB;
2443 }
2444
2445 if (special->type == AC_SPECIAL_ALT_CHAR) {
2446 (special->alt).byte[i] = (unsigned char)*c;
2447 MPOOL_FREE(root->mempool, c);
2448 } else {
2449 (special->alt).f_str[i] = (unsigned char *)c;
2450 }
2451 special->num++;
2452 }
2453 /* sorting byte alternates */
2454 if (special->num > 1 && special->type == AC_SPECIAL_ALT_CHAR)
2455 cli_qsort((special->alt).byte, special->num, sizeof(unsigned char), qcompare_byte);
2456 /* sorting str alternates */
2457 if (special->num > 1 && special->type == AC_SPECIAL_ALT_STR_FIXED)
2458 cli_qsort_r((special->alt).f_str, special->num, sizeof(unsigned char *), qcompare_fstr, &(special->len));
2459 } else { /* generic alternates */
2460 char *subexpr;
2461 if (special->negative) {
2462 cli_errmsg("ac_special_altstr: Can't apply negation operation to generic alternate strings\n");
2463 free(hexprcpy);
2464 return CL_EMALFDB;
2465 }
2466
2467 special->type = AC_SPECIAL_ALT_STR;
2468
2469 /* allocate reusable subexpr */
2470 if (!(subexpr = cli_calloc(slen + 1, sizeof(char)))) {
2471 cli_errmsg("ac_special_altstr: Can't allocate subexpr container\n");
2472 free(hexprcpy);
2473 return CL_EMEM;
2474 }
2475
2476 ret = ac_special_altexpand(hexprcpy, subexpr, slen + 1, 0, 0, sigopts, special, root);
2477
2478 free(subexpr);
2479 free(hexprcpy);
2480 return ret;
2481 }
2482
2483 free(hexprcpy);
2484 return CL_SUCCESS;
2485 }
2486
2487 /* FIXME: clean up the code */
cli_ac_addsig(struct cli_matcher * root,const char * virname,const char * hexsig,uint8_t sigopts,uint32_t sigid,uint16_t parts,uint16_t partno,uint16_t rtype,uint16_t type,uint32_t mindist,uint32_t maxdist,const char * offset,const uint32_t * lsigid,unsigned int options)2488 cl_error_t cli_ac_addsig(struct cli_matcher *root, const char *virname, const char *hexsig, uint8_t sigopts, uint32_t sigid, uint16_t parts, uint16_t partno, uint16_t rtype, uint16_t type, uint32_t mindist, uint32_t maxdist, const char *offset, const uint32_t *lsigid, unsigned int options)
2489 {
2490 struct cli_ac_patt *new;
2491 char *pt, *pt2, *hex = NULL, *hexcpy = NULL;
2492 uint16_t i, j, ppos = 0, pend, *dec, nzpos = 0;
2493 uint8_t wprefix = 0, zprefix = 1, plen = 0, nzplen = 0;
2494 struct cli_ac_special *newspecial, **newtable;
2495 int ret, error = CL_SUCCESS;
2496
2497 if (!root) {
2498 cli_errmsg("cli_ac_addsig: root == NULL\n");
2499 return CL_ENULLARG;
2500 }
2501
2502 if (strlen(hexsig) / 2 < root->ac_mindepth) {
2503 cli_errmsg("cli_ac_addsig: Signature for %s is too short\n", virname);
2504 return CL_EMALFDB;
2505 }
2506
2507 if ((new = (struct cli_ac_patt *)MPOOL_CALLOC(root->mempool, 1, sizeof(struct cli_ac_patt))) == NULL)
2508 return CL_EMEM;
2509
2510 new->rtype = rtype;
2511 new->type = type;
2512 new->sigid = sigid;
2513 new->parts = parts;
2514 new->partno = partno;
2515 new->mindist = mindist;
2516 new->maxdist = maxdist;
2517 new->customdata = NULL;
2518 new->ch[0] |= CLI_MATCH_IGNORE;
2519 new->ch[1] |= CLI_MATCH_IGNORE;
2520 if (lsigid) {
2521 new->lsigid[0] = 1;
2522 memcpy(&new->lsigid[1], lsigid, 2 * sizeof(uint32_t));
2523 }
2524
2525 if (strchr(hexsig, '[')) {
2526 if (!(hexcpy = cli_strdup(hexsig))) {
2527 MPOOL_FREE(root->mempool, new);
2528 return CL_EMEM;
2529 }
2530
2531 hex = hexcpy;
2532 for (i = 0; i < 2; i++) {
2533 unsigned int n, n1, n2;
2534
2535 if (!(pt = strchr(hex, '[')))
2536 break;
2537
2538 *pt++ = 0;
2539
2540 if (!(pt2 = strchr(pt, ']'))) {
2541 cli_dbgmsg("cli_ac_addsig: missing closing square bracket\n");
2542 error = CL_EMALFDB;
2543 break;
2544 }
2545
2546 *pt2++ = 0;
2547
2548 n = sscanf(pt, "%u-%u", &n1, &n2);
2549 if (n == 1) {
2550 n2 = n1;
2551 } else if (n != 2) {
2552 cli_dbgmsg("cli_ac_addsig: incorrect range inside square brackets\n");
2553 error = CL_EMALFDB;
2554 break;
2555 }
2556
2557 if ((n1 > n2) || (n2 > AC_CH_MAXDIST)) {
2558 cli_dbgmsg("cli_ac_addsig: incorrect range inside square brackets\n");
2559 error = CL_EMALFDB;
2560 break;
2561 }
2562
2563 if (strlen(hex) == 2) {
2564 if (i) {
2565 error = CL_EMALFDB;
2566 break;
2567 }
2568
2569 dec = cli_hex2ui(hex);
2570 if (!dec) {
2571 error = CL_EMALFDB;
2572 break;
2573 }
2574
2575 if ((sigopts & ACPATT_OPTION_NOCASE) && ((*dec & CLI_MATCH_METADATA) == CLI_MATCH_CHAR))
2576 new->ch[i] = CLI_NOCASE(*dec) | CLI_MATCH_NOCASE;
2577 else
2578 new->ch[i] = *dec;
2579 free(dec);
2580 new->ch_mindist[i] = n1;
2581 new->ch_maxdist[i] = n2;
2582 hex = pt2;
2583 } else if (strlen(pt2) == 2) {
2584 i = 1;
2585 dec = cli_hex2ui(pt2);
2586 if (!dec) {
2587 error = CL_EMALFDB;
2588 break;
2589 }
2590
2591 if ((sigopts & ACPATT_OPTION_NOCASE) && ((*dec & CLI_MATCH_METADATA) == CLI_MATCH_CHAR))
2592 new->ch[i] = CLI_NOCASE(*dec) | CLI_MATCH_NOCASE;
2593 else
2594 new->ch[i] = *dec;
2595 free(dec);
2596 new->ch_mindist[i] = n1;
2597 new->ch_maxdist[i] = n2;
2598 } else {
2599 error = CL_EMALFDB;
2600 break;
2601 }
2602 }
2603
2604 if (error) {
2605 free(hexcpy);
2606 MPOOL_FREE(root->mempool, new);
2607 return error;
2608 }
2609
2610 hex = cli_strdup(hex);
2611 free(hexcpy);
2612 if (!hex) {
2613 MPOOL_FREE(root->mempool, new);
2614 return CL_EMEM;
2615 }
2616 }
2617
2618 if (strchr(hexsig, '(')) {
2619 char *hexnew, *start;
2620 size_t nest;
2621 size_t hexnewsz;
2622
2623 if (hex) {
2624 hexcpy = hex;
2625 } else if (!(hexcpy = cli_strdup(hexsig))) {
2626 MPOOL_FREE(root->mempool, new);
2627 return CL_EMEM;
2628 }
2629
2630 hexnewsz = strlen(hexsig) + 1;
2631 if (!(hexnew = (char *)cli_calloc(1, hexnewsz))) {
2632 free(new);
2633 free(hexcpy);
2634 return CL_EMEM;
2635 }
2636
2637 start = pt = hexcpy;
2638 while ((pt = strchr(start, '('))) {
2639 *pt++ = 0;
2640
2641 if (!start) {
2642 error = CL_EMALFDB;
2643 break;
2644 }
2645 newspecial = (struct cli_ac_special *)MPOOL_CALLOC(root->mempool, 1, sizeof(struct cli_ac_special));
2646 if (!newspecial) {
2647 cli_errmsg("cli_ac_addsig: Can't allocate newspecial\n");
2648 error = CL_EMEM;
2649 break;
2650 }
2651 if (pt >= hexcpy + 2) {
2652 if (pt[-2] == '!') {
2653 newspecial->negative = 1;
2654 pt[-2] = 0;
2655 }
2656 }
2657 cli_strlcat(hexnew, start, hexnewsz);
2658
2659 nest = find_paren_end(pt, &start);
2660 if (!start) {
2661 cli_errmsg("cli_ac_addsig: Missing closing parenthesis\n");
2662 MPOOL_FREE(root->mempool, newspecial);
2663 error = CL_EMALFDB;
2664 break;
2665 }
2666 *start++ = 0;
2667 if (!strlen(pt)) {
2668 cli_errmsg("cli_ac_addsig: Empty block\n");
2669 MPOOL_FREE(root->mempool, newspecial);
2670 error = CL_EMALFDB;
2671 break;
2672 }
2673
2674 if (nest > ACPATT_ALTN_MAXNEST) {
2675 cli_errmsg("ac_addspecial: Expression exceeds maximum alternate nesting limit\n");
2676 MPOOL_FREE(root->mempool, newspecial);
2677 error = CL_EMALFDB;
2678 break;
2679 }
2680
2681 if (!strcmp(pt, "B")) {
2682 if (!*start) {
2683 new->boundary |= AC_BOUNDARY_RIGHT;
2684 if (newspecial->negative)
2685 new->boundary |= AC_BOUNDARY_RIGHT_NEGATIVE;
2686 MPOOL_FREE(root->mempool, newspecial);
2687 continue;
2688 } else if (pt - 1 == hexcpy) {
2689 new->boundary |= AC_BOUNDARY_LEFT;
2690 if (newspecial->negative)
2691 new->boundary |= AC_BOUNDARY_LEFT_NEGATIVE;
2692 MPOOL_FREE(root->mempool, newspecial);
2693 continue;
2694 }
2695 } else if (!strcmp(pt, "L")) {
2696 if (!*start) {
2697 new->boundary |= AC_LINE_MARKER_RIGHT;
2698 if (newspecial->negative)
2699 new->boundary |= AC_LINE_MARKER_RIGHT_NEGATIVE;
2700 MPOOL_FREE(root->mempool, newspecial);
2701 continue;
2702 } else if (pt - 1 == hexcpy) {
2703 new->boundary |= AC_LINE_MARKER_LEFT;
2704 if (newspecial->negative)
2705 new->boundary |= AC_LINE_MARKER_LEFT_NEGATIVE;
2706 MPOOL_FREE(root->mempool, newspecial);
2707 continue;
2708 }
2709 } else if (!strcmp(pt, "W")) {
2710 if (!*start) {
2711 new->boundary |= AC_WORD_MARKER_RIGHT;
2712 if (newspecial->negative)
2713 new->boundary |= AC_WORD_MARKER_RIGHT_NEGATIVE;
2714 MPOOL_FREE(root->mempool, newspecial);
2715 continue;
2716 } else if (pt - 1 == hexcpy) {
2717 new->boundary |= AC_WORD_MARKER_LEFT;
2718 if (newspecial->negative)
2719 new->boundary |= AC_WORD_MARKER_LEFT_NEGATIVE;
2720 MPOOL_FREE(root->mempool, newspecial);
2721 continue;
2722 }
2723 }
2724 cli_strlcat(hexnew, "()", hexnewsz);
2725 new->special++;
2726 newtable = (struct cli_ac_special **)MPOOL_REALLOC(root->mempool, new->special_table, new->special * sizeof(struct cli_ac_special *));
2727 if (!newtable) {
2728 new->special--;
2729 MPOOL_FREE(root->mempool, newspecial);
2730 cli_errmsg("cli_ac_addsig: Can't realloc new->special_table\n");
2731 error = CL_EMEM;
2732 break;
2733 }
2734 newtable[new->special - 1] = newspecial;
2735 new->special_table = newtable;
2736
2737 if (!strcmp(pt, "B")) {
2738 newspecial->type = AC_SPECIAL_BOUNDARY;
2739 } else if (!strcmp(pt, "L")) {
2740 newspecial->type = AC_SPECIAL_LINE_MARKER;
2741 } else if (!strcmp(pt, "W")) {
2742 newspecial->type = AC_SPECIAL_WORD_MARKER;
2743 } else {
2744 if ((ret = ac_special_altstr(pt, sigopts, newspecial, root)) != CL_SUCCESS) {
2745 error = ret;
2746 break;
2747 }
2748 }
2749 }
2750
2751 if (start)
2752 cli_strlcat(hexnew, start, hexnewsz);
2753
2754 hex = hexnew;
2755 free(hexcpy);
2756
2757 if (error) {
2758 free(hex);
2759 if (new->special) {
2760 mpool_ac_free_special(root->mempool, new);
2761 }
2762 MPOOL_FREE(root->mempool, new);
2763 return error;
2764 }
2765 }
2766
2767 new->pattern = CLI_MPOOL_HEX2UI(root->mempool, hex ? hex : hexsig);
2768 if (new->pattern == NULL) {
2769 if (new->special)
2770 mpool_ac_free_special(root->mempool, new);
2771
2772 MPOOL_FREE(root->mempool, new);
2773 free(hex);
2774 return CL_EMALFDB;
2775 }
2776
2777 new->length[0] = (uint16_t)strlen(hex ? hex : hexsig) / 2;
2778 for (i = 0, j = 0; i < new->length[0]; i++) {
2779 if ((new->pattern[i] & CLI_MATCH_METADATA) == CLI_MATCH_SPECIAL) {
2780 new->length[1] += new->special_table[j]->len[0];
2781 new->length[2] += new->special_table[j]->len[1];
2782 j++;
2783 } else {
2784 new->length[1]++;
2785 new->length[2]++;
2786 }
2787 }
2788
2789 free(hex);
2790
2791 new->sigopts = sigopts;
2792 /* setting nocase match */
2793 if (sigopts & ACPATT_OPTION_NOCASE) {
2794 for (i = 0; i < new->length[0]; i++)
2795 if ((new->pattern[i] & CLI_MATCH_METADATA) == CLI_MATCH_CHAR) {
2796 new->pattern[i] = CLI_NOCASE(new->pattern[i] & 0xff);
2797 new->pattern[i] += CLI_MATCH_NOCASE;
2798 }
2799 }
2800
2801 /* TODO - sigopts affect on filters? */
2802 if (root->filter) {
2803 /* so that we can show meaningful messages */
2804 new->virname = (char *)virname;
2805 if (filter_add_acpatt(root->filter, new) == -1) {
2806 cli_warnmsg("cli_ac_addpatt: cannot use filter for trie\n");
2807 MPOOL_FREE(root->mempool, root->filter);
2808 root->filter = NULL;
2809 }
2810
2811 /* TODO: should this affect maxpatlen? */
2812 }
2813
2814 for (i = 0; i < root->ac_maxdepth && i < new->length[0]; i++) {
2815 if (new->pattern[i] & CLI_MATCH_WILDCARD) {
2816 wprefix = 1;
2817 break;
2818 }
2819
2820 if (zprefix && new->pattern[i])
2821 zprefix = 0;
2822 }
2823
2824 if (wprefix || zprefix) {
2825 pend = new->length[0] - root->ac_mindepth + 1;
2826 for (i = 0; i < pend; i++) {
2827 for (j = i; j < i + root->ac_maxdepth && j < new->length[0]; j++) {
2828 if (new->pattern[j] & CLI_MATCH_WILDCARD) {
2829 break;
2830 } else {
2831 if (j - i + 1 >= plen) {
2832 plen = j - i + 1;
2833 ppos = i;
2834 }
2835 }
2836
2837 if (new->pattern[ppos] || new->pattern[ppos + 1]) {
2838 if (plen >= root->ac_maxdepth) {
2839 break;
2840 } else if (plen >= root->ac_mindepth && plen > nzplen) {
2841 nzplen = plen;
2842 nzpos = ppos;
2843 }
2844 }
2845 }
2846
2847 if (plen >= root->ac_maxdepth && (new->pattern[ppos] || new->pattern[ppos + 1]))
2848 break;
2849 }
2850
2851 if (!new->pattern[ppos] && !new->pattern[ppos + 1] && nzplen) {
2852 plen = nzplen;
2853 ppos = nzpos;
2854 }
2855
2856 if (plen < root->ac_mindepth) {
2857 cli_errmsg("cli_ac_addsig: Can't find a static subpattern of length %u\n", root->ac_mindepth);
2858 mpool_ac_free_special(root->mempool, new);
2859 MPOOL_FREE(root->mempool, new->pattern);
2860 MPOOL_FREE(root->mempool, new);
2861 return CL_EMALFDB;
2862 }
2863
2864 new->prefix = new->pattern;
2865 new->prefix_length[0] = ppos;
2866 for (i = 0, j = 0; i < new->prefix_length[0]; i++) {
2867 if ((new->prefix[i] & CLI_MATCH_WILDCARD) == CLI_MATCH_SPECIAL)
2868 new->special_pattern++;
2869
2870 if ((new->prefix[i] & CLI_MATCH_METADATA) == CLI_MATCH_SPECIAL) {
2871 new->prefix_length[1] += new->special_table[j]->len[0];
2872 new->prefix_length[2] += new->special_table[j]->len[1];
2873 j++;
2874 } else {
2875 new->prefix_length[1]++;
2876 new->prefix_length[2]++;
2877 }
2878 }
2879
2880 new->pattern = &new->prefix[ppos];
2881 new->length[0] -= new->prefix_length[0];
2882 new->length[1] -= new->prefix_length[1];
2883 new->length[2] -= new->prefix_length[2];
2884 }
2885
2886 if (new->length[2] + new->prefix_length[2] > root->maxpatlen)
2887 root->maxpatlen = new->length[2] + new->prefix_length[2];
2888
2889 new->virname = CLI_MPOOL_VIRNAME(root->mempool, virname, options & CL_DB_OFFICIAL);
2890 if (!new->virname) {
2891 MPOOL_FREE(root->mempool, new->prefix ? new->prefix : new->pattern);
2892 mpool_ac_free_special(root->mempool, new);
2893 MPOOL_FREE(root->mempool, new);
2894 return CL_EMEM;
2895 }
2896
2897 if (new->lsigid[0])
2898 root->ac_lsigtable[new->lsigid[1]]->virname = new->virname;
2899
2900 ret = cli_caloff(offset, NULL, root->type, new->offdata, &new->offset_min, &new->offset_max);
2901 if (ret != CL_SUCCESS) {
2902 MPOOL_FREE(root->mempool, new->prefix ? new->prefix : new->pattern);
2903 mpool_ac_free_special(root->mempool, new);
2904 MPOOL_FREE(root->mempool, new->virname);
2905 MPOOL_FREE(root->mempool, new);
2906 return ret;
2907 }
2908
2909 if ((ret = cli_ac_addpatt(root, new))) {
2910 MPOOL_FREE(root->mempool, new->prefix ? new->prefix : new->pattern);
2911 MPOOL_FREE(root->mempool, new->virname);
2912 mpool_ac_free_special(root->mempool, new);
2913 MPOOL_FREE(root->mempool, new);
2914 return ret;
2915 }
2916
2917 if ((new->offdata[0] != CLI_OFF_ANY) &&
2918 (new->offdata[0] != CLI_OFF_ABSOLUTE) &&
2919 (new->offdata[0] != CLI_OFF_MACRO)) {
2920
2921 root->ac_reloff = (struct cli_ac_patt **)MPOOL_REALLOC2(root->mempool, root->ac_reloff, (root->ac_reloff_num + 1) * sizeof(struct cli_ac_patt *));
2922 if (!root->ac_reloff) {
2923 cli_errmsg("cli_ac_addsig: Can't allocate memory for root->ac_reloff\n");
2924 return CL_EMEM;
2925 }
2926
2927 root->ac_reloff[root->ac_reloff_num] = new;
2928 new->offset_min = root->ac_reloff_num * 2;
2929 new->offset_max = new->offset_min + 1;
2930 root->ac_reloff_num++;
2931 }
2932
2933 return CL_SUCCESS;
2934 }
2935