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 int 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 int rc;
1715
1716 if (!root->ac_root)
1717 return CL_CLEAN;
1718
1719 if (!mdata && (root->ac_partsigs || root->ac_lsigs || root->ac_reloff_num)) {
1720 cli_errmsg("cli_ac_scanbuff: mdata == NULL\n");
1721 return CL_ENULLARG;
1722 }
1723
1724 current = root->ac_root;
1725
1726 for (i = 0; i < length; i++) {
1727 current = current->trans[buffer[i]];
1728
1729 if (UNLIKELY(IS_FINAL(current))) {
1730 struct cli_ac_list *faillist = current->fail->list;
1731 pattN = current->list;
1732 while (pattN) {
1733 patt = pattN->me;
1734 if (patt->partno > mdata->min_partno) {
1735 pattN = faillist;
1736 faillist = NULL;
1737 continue;
1738 }
1739 bp = i + 1 - patt->depth;
1740 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)) {
1741 if (patt->offset_min == CLI_OFF_NONE) {
1742 pattN = pattN->next;
1743 continue;
1744 }
1745 exptoff[0] = offset + bp - patt->prefix_length[2]; /* lower offset end */
1746 exptoff[1] = offset + bp - patt->prefix_length[1]; /* higher offset end */
1747 if (patt->offdata[0] == CLI_OFF_ABSOLUTE) {
1748 if (patt->offset_max < exptoff[0] || patt->offset_min > exptoff[1]) {
1749 pattN = pattN->next;
1750 continue;
1751 }
1752 } else {
1753 if (mdata->offset[patt->offset_min] == CLI_OFF_NONE || mdata->offset[patt->offset_max] < exptoff[0] || mdata->offset[patt->offset_min] > exptoff[1]) {
1754 pattN = pattN->next;
1755 continue;
1756 }
1757 }
1758 }
1759
1760 ptN = pattN;
1761 if (ac_findmatch(buffer, bp, offset + bp, length, patt, &matchstart, &matchend)) {
1762 while (ptN) {
1763 pt = ptN->me;
1764 if (pt->partno > mdata->min_partno)
1765 break;
1766
1767 if ((pt->type && !(mode & AC_SCAN_FT)) || (!pt->type && !(mode & AC_SCAN_VIR))) {
1768 ptN = ptN->next_same;
1769 continue;
1770 }
1771
1772 realoff = offset + matchstart;
1773 if (pt->offdata[0] == CLI_OFF_VERSION) {
1774 if (!cli_hashset_contains_maybe_noalloc(mdata->vinfo, realoff)) {
1775 ptN = ptN->next_same;
1776 continue;
1777 }
1778 cli_dbgmsg("cli_ac_scanbuff: VI match for offset %x\n", realoff);
1779 } else if (pt->offdata[0] == CLI_OFF_MACRO) {
1780 mdata->macro_lastmatch[patt->offdata[1]] = realoff;
1781 ptN = ptN->next_same;
1782 continue;
1783 } else if (pt->offset_min != CLI_OFF_ANY && (!pt->sigid || pt->partno == 1)) {
1784 if (pt->offset_min == CLI_OFF_NONE) {
1785 ptN = ptN->next_same;
1786 continue;
1787 }
1788 if (pt->offdata[0] == CLI_OFF_ABSOLUTE) {
1789 if (pt->offset_max < realoff || pt->offset_min > realoff) {
1790 ptN = ptN->next_same;
1791 continue;
1792 }
1793 } else {
1794 if (mdata->offset[pt->offset_min] == CLI_OFF_NONE || mdata->offset[pt->offset_max] < realoff || mdata->offset[pt->offset_min] > realoff) {
1795 ptN = ptN->next_same;
1796 continue;
1797 }
1798 }
1799 }
1800
1801 if (pt->sigid) { /* it's a partial signature */
1802
1803 /* if 2nd or later part, confirm some prior part has matched */
1804 if (pt->partno != 1 && (!mdata->offmatrix[pt->sigid - 1] || !mdata->offmatrix[pt->sigid - 1][pt->partno - 2][0])) {
1805 ptN = ptN->next_same;
1806 continue;
1807 }
1808
1809 if (pt->partno + 1 > mdata->min_partno)
1810 mdata->min_partno = pt->partno + 1;
1811
1812 /* sparsely populated matrix, so allocate and initialize if NULL */
1813 if (!mdata->offmatrix[pt->sigid - 1]) {
1814 mdata->offmatrix[pt->sigid - 1] = cli_malloc(pt->parts * sizeof(int32_t *));
1815 if (!mdata->offmatrix[pt->sigid - 1]) {
1816 cli_errmsg("cli_ac_scanbuff: Can't allocate memory for mdata->offmatrix[%u]\n", pt->sigid - 1);
1817 return CL_EMEM;
1818 }
1819
1820 mdata->offmatrix[pt->sigid - 1][0] = cli_malloc(pt->parts * (CLI_DEFAULT_AC_TRACKLEN + 2) * sizeof(uint32_t));
1821 if (!mdata->offmatrix[pt->sigid - 1][0]) {
1822 cli_errmsg("cli_ac_scanbuff: Can't allocate memory for mdata->offmatrix[%u][0]\n", pt->sigid - 1);
1823 free(mdata->offmatrix[pt->sigid - 1]);
1824 mdata->offmatrix[pt->sigid - 1] = NULL;
1825 return CL_EMEM;
1826 }
1827 memset(mdata->offmatrix[pt->sigid - 1][0], (uint32_t)-1, pt->parts * (CLI_DEFAULT_AC_TRACKLEN + 2) * sizeof(uint32_t));
1828 mdata->offmatrix[pt->sigid - 1][0][0] = 0;
1829 for (j = 1; j < pt->parts; j++) {
1830 mdata->offmatrix[pt->sigid - 1][j] = mdata->offmatrix[pt->sigid - 1][0] + j * (CLI_DEFAULT_AC_TRACKLEN + 2);
1831 mdata->offmatrix[pt->sigid - 1][j][0] = 0;
1832 }
1833 }
1834 offmatrix = mdata->offmatrix[pt->sigid - 1];
1835
1836 found = 0;
1837 if (pt->partno != 1) {
1838 for (j = 1; (j <= CLI_DEFAULT_AC_TRACKLEN + 1) && (offmatrix[pt->partno - 2][j] != (uint32_t)-1); j++) {
1839 found = j;
1840 if (realoff < offmatrix[pt->partno - 2][j])
1841 found = 0;
1842
1843 if (found && pt->maxdist)
1844 if (realoff - offmatrix[pt->partno - 2][j] > pt->maxdist)
1845 found = 0;
1846
1847 if (found && pt->mindist)
1848 if (realoff - offmatrix[pt->partno - 2][j] < pt->mindist)
1849 found = 0;
1850
1851 if (found)
1852 break;
1853 }
1854 }
1855
1856 if (pt->partno == 2 && found > 1) {
1857 swp = offmatrix[0][1];
1858 offmatrix[0][1] = offmatrix[0][found];
1859 offmatrix[0][found] = swp;
1860
1861 if (pt->type != CL_TYPE_MSEXE) {
1862 swp = offmatrix[pt->parts - 1][1];
1863 offmatrix[pt->parts - 1][1] = offmatrix[pt->parts - 1][found];
1864 offmatrix[pt->parts - 1][found] = swp;
1865 }
1866 }
1867
1868 if (pt->partno == 1 || (found && (pt->partno != pt->parts))) {
1869 if (offmatrix[pt->partno - 1][0] == CLI_DEFAULT_AC_TRACKLEN + 1)
1870 offmatrix[pt->partno - 1][0] = 1; /* wrap, ends up at 2 */
1871 offmatrix[pt->partno - 1][0]++;
1872 offmatrix[pt->partno - 1][offmatrix[pt->partno - 1][0]] = offset + matchend;
1873
1874 if (pt->partno == 1) /* save realoff for the first part */
1875 offmatrix[pt->parts - 1][offmatrix[pt->partno - 1][0]] = realoff;
1876 } else if (found && pt->partno == pt->parts) {
1877 if (pt->type) {
1878
1879 if (pt->type == CL_TYPE_IGNORED && (!pt->rtype || ftype == pt->rtype))
1880 return CL_TYPE_IGNORED;
1881
1882 if ((pt->type > type || pt->type >= CL_TYPE_SFX || pt->type == CL_TYPE_MSEXE) && (!pt->rtype || ftype == pt->rtype)) {
1883 cli_dbgmsg("Matched signature for file type %s\n", pt->virname);
1884 type = pt->type;
1885 if (ftoffset &&
1886 (!*ftoffset || (*ftoffset)->cnt < MAX_EMBEDDED_OBJ || type == CL_TYPE_ZIPSFX) &&
1887 (type >= CL_TYPE_SFX || ((ftype == CL_TYPE_MSEXE || ftype == CL_TYPE_ZIP || ftype == CL_TYPE_MSOLE2) && type == CL_TYPE_MSEXE))) {
1888 /* FIXME: the first offset in the array is most likely the correct one but
1889 * it may happen it is not
1890 */
1891 for (j = 1; j <= CLI_DEFAULT_AC_TRACKLEN + 1 && offmatrix[0][j] != (uint32_t)-1; j++)
1892 if (ac_addtype(ftoffset, type, offmatrix[pt->parts - 1][j], ctx))
1893 return CL_EMEM;
1894 }
1895
1896 memset(offmatrix[0], (uint32_t)-1, pt->parts * (CLI_DEFAULT_AC_TRACKLEN + 2) * sizeof(uint32_t));
1897 for (j = 0; j < pt->parts; j++)
1898 offmatrix[j][0] = 0;
1899 }
1900
1901 } else { /* !pt->type */
1902 if (pt->lsigid[0]) {
1903 rc = lsig_sub_matched(root, mdata, pt->lsigid[1], pt->lsigid[2], offmatrix[pt->parts - 1][1], 1);
1904 if (rc != CL_SUCCESS)
1905 return rc;
1906 ptN = ptN->next_same;
1907 continue;
1908 }
1909
1910 if (res) {
1911 newres = (struct cli_ac_result *)malloc(sizeof(struct cli_ac_result));
1912 if (!newres) {
1913 cli_errmsg("cli_ac_scanbuff: Can't allocate memory for newres %lu\n", (unsigned long)sizeof(struct cli_ac_result));
1914 return CL_EMEM;
1915 }
1916 newres->virname = pt->virname;
1917 newres->customdata = pt->customdata;
1918 newres->next = *res;
1919 newres->offset = (off_t)offmatrix[pt->parts - 1][1];
1920 *res = newres;
1921
1922 ptN = ptN->next_same;
1923 continue;
1924 } else {
1925 if (ctx && SCAN_ALLMATCHES) {
1926 cli_append_virus(ctx, (const char *)pt->virname);
1927 viruses_found = 1;
1928 }
1929 if (virname)
1930 *virname = pt->virname;
1931 if (customdata)
1932 *customdata = pt->customdata;
1933 if (!ctx || !SCAN_ALLMATCHES)
1934 return CL_VIRUS;
1935 ptN = ptN->next_same;
1936 continue;
1937 }
1938 }
1939 }
1940
1941 } else { /* old type signature */
1942 if (pt->type) {
1943 if (pt->type == CL_TYPE_IGNORED && (!pt->rtype || ftype == pt->rtype))
1944 return CL_TYPE_IGNORED;
1945
1946 if ((pt->type > type || pt->type >= CL_TYPE_SFX || pt->type == CL_TYPE_MSEXE) && (!pt->rtype || ftype == pt->rtype)) {
1947
1948 cli_dbgmsg("Matched signature for file type %s at %u\n", pt->virname, realoff);
1949 type = pt->type;
1950 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))) {
1951
1952 if (ac_addtype(ftoffset, type, realoff, ctx))
1953 return CL_EMEM;
1954 }
1955 }
1956 } else {
1957 if (pt->lsigid[0]) {
1958 rc = lsig_sub_matched(root, mdata, pt->lsigid[1], pt->lsigid[2], realoff, 0);
1959 if (rc != CL_SUCCESS)
1960 return rc;
1961 ptN = ptN->next_same;
1962 continue;
1963 }
1964
1965 if (res) {
1966 newres = (struct cli_ac_result *)malloc(sizeof(struct cli_ac_result));
1967 if (!newres) {
1968 cli_errmsg("cli_ac_scanbuff: Can't allocate memory for newres %lu\n", (unsigned long)sizeof(struct cli_ac_result));
1969 return CL_EMEM;
1970 }
1971 newres->virname = pt->virname;
1972 newres->customdata = pt->customdata;
1973 newres->offset = (off_t)realoff;
1974 newres->next = *res;
1975 *res = newres;
1976
1977 ptN = ptN->next_same;
1978 continue;
1979 } else {
1980 if (ctx && SCAN_ALLMATCHES) {
1981 cli_append_virus(ctx, (const char *)pt->virname);
1982 viruses_found = 1;
1983 }
1984
1985 if (virname)
1986 *virname = pt->virname;
1987
1988 if (customdata)
1989 *customdata = pt->customdata;
1990
1991 if (!ctx || !SCAN_ALLMATCHES)
1992 return CL_VIRUS;
1993
1994 ptN = ptN->next_same;
1995 continue;
1996 }
1997 }
1998 }
1999 ptN = ptN->next_same;
2000 }
2001 }
2002 pattN = pattN->next;
2003 }
2004 }
2005 }
2006
2007 if (viruses_found)
2008 return CL_VIRUS;
2009
2010 return (mode & AC_SCAN_FT) ? type : CL_CLEAN;
2011 }
2012
qcompare_byte(const void * a,const void * b)2013 static int qcompare_byte(const void *a, const void *b)
2014 {
2015 return *(const unsigned char *)a - *(const unsigned char *)b;
2016 }
2017
qcompare_fstr(const void * arg,const void * a,const void * b)2018 static int qcompare_fstr(const void *arg, const void *a, const void *b)
2019 {
2020 uint16_t len = *(uint16_t *)arg;
2021 return memcmp(*(const unsigned char **)a, *(const unsigned char **)b, len);
2022 }
2023
2024 /* returns if level of nesting, end set to MATCHING paren, start AFTER staring paren */
find_paren_end(char * hexstr,char ** end)2025 inline static size_t find_paren_end(char *hexstr, char **end)
2026 {
2027 size_t i;
2028 size_t nest = 0, level = 0;
2029
2030 *end = NULL;
2031 for (i = 0; i < strlen(hexstr); i++) {
2032 if (hexstr[i] == '(') {
2033 nest++;
2034 level++;
2035 } else if (hexstr[i] == ')') {
2036 if (!level) {
2037 *end = &hexstr[i];
2038 break;
2039 }
2040 level--;
2041 }
2042 }
2043
2044 return nest;
2045 }
2046
2047 /* analyzes expr, returns number of subexpr, if fixed length subexpr and longest subexpr len *
2048 * goes to either end of string or to closing parenthesis; allowed to be unbalanced *
2049 * 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)2050 inline static int ac_analyze_expr(char *hexstr, int *fixed_len, int *sub_len)
2051 {
2052 unsigned long i;
2053 int level = 0, len = 0, numexpr = 1;
2054 int flen, slen;
2055
2056 flen = 1;
2057 slen = 0;
2058 for (i = 0; i < strlen(hexstr); i++) {
2059 if (hexstr[i] == '(') {
2060 flen = 0;
2061 level++;
2062 } else if (hexstr[i] == ')') {
2063 if (!level) {
2064 if (!slen) {
2065 slen = len;
2066 } else if (len != slen) {
2067 flen = 0;
2068 if (len > slen)
2069 slen = len;
2070 }
2071 break;
2072 }
2073 level--;
2074 }
2075 if (!level && hexstr[i] == '|') {
2076 if (!slen) {
2077 slen = len;
2078 } else if (len != slen) {
2079 flen = 0;
2080 if (len > slen)
2081 slen = len;
2082 }
2083 len = 0;
2084 numexpr++;
2085 } else {
2086 if (hexstr[i] == '?')
2087 flen = 0;
2088 len++;
2089 }
2090 }
2091 if (!slen) {
2092 slen = len;
2093 } else if (len != slen) {
2094 flen = 0;
2095 if (len > slen)
2096 slen = len;
2097 }
2098
2099 if (sub_len)
2100 *sub_len = slen;
2101 if (fixed_len)
2102 *fixed_len = flen;
2103
2104 return numexpr;
2105 }
2106
ac_uicmp(uint16_t * a,size_t alen,uint16_t * b,size_t blen,int * wild)2107 inline static int ac_uicmp(uint16_t *a, size_t alen, uint16_t *b, size_t blen, int *wild)
2108 {
2109 uint16_t awild, bwild, side_wild;
2110 size_t i, minlen = MIN(alen, blen);
2111
2112 side_wild = 0;
2113
2114 for (i = 0; i < minlen; i++) {
2115 awild = a[i] & CLI_MATCH_WILDCARD;
2116 bwild = b[i] & CLI_MATCH_WILDCARD;
2117
2118 if (awild == bwild) {
2119 switch (awild) {
2120 case CLI_MATCH_CHAR:
2121 if ((a[i] & 0xff) != (b[i] & 0xff)) {
2122 return (b[i] & 0xff) - (a[i] & 0xff);
2123 }
2124 break;
2125 case CLI_MATCH_IGNORE:
2126 break;
2127 case CLI_MATCH_NIBBLE_HIGH:
2128 if ((a[i] & 0xf0) != (b[i] & 0xf0)) {
2129 return (b[i] & 0xf0) - (a[i] & 0xf0);
2130 }
2131 break;
2132 case CLI_MATCH_NIBBLE_LOW:
2133 if ((a[i] & 0x0f) != (b[i] & 0x0f)) {
2134 return (b[i] & 0x0f) - (a[i] & 0x0f);
2135 }
2136 break;
2137 default:
2138 cli_errmsg("ac_uicmp: unhandled wildcard type\n");
2139 return 1;
2140 }
2141 } else { /* not identical wildcard types */
2142 if (awild == CLI_MATCH_CHAR) { /* b is only wild */
2143 switch (bwild) {
2144 case CLI_MATCH_IGNORE:
2145 side_wild |= 2;
2146 break;
2147 case CLI_MATCH_NIBBLE_HIGH:
2148 if ((a[i] & 0xf0) != (b[i] & 0xf0)) {
2149 return (b[i] & 0xf0) - (a[i] & 0xff);
2150 }
2151 side_wild |= 2;
2152 break;
2153 case CLI_MATCH_NIBBLE_LOW:
2154 if ((a[i] & 0x0f) != (b[i] & 0x0f)) {
2155 return (b[i] & 0x0f) - (a[i] & 0xff);
2156 }
2157 side_wild |= 2;
2158 break;
2159 default:
2160 cli_errmsg("ac_uicmp: unhandled wildcard type\n");
2161 return -1;
2162 }
2163 } else if (bwild == CLI_MATCH_CHAR) { /* a is only wild */
2164 switch (awild) {
2165 case CLI_MATCH_IGNORE:
2166 side_wild |= 1;
2167 break;
2168 case CLI_MATCH_NIBBLE_HIGH:
2169 if ((a[i] & 0xf0) != (b[i] & 0xf0)) {
2170 return (b[i] & 0xff) - (a[i] & 0xf0);
2171 }
2172 side_wild |= 1;
2173 break;
2174 case CLI_MATCH_NIBBLE_LOW:
2175 if ((a[i] & 0x0f) != (b[i] & 0x0f)) {
2176 return (b[i] & 0xff) - (a[i] & 0x0f);
2177 }
2178 side_wild |= 1;
2179 break;
2180 default:
2181 cli_errmsg("ac_uicmp: unhandled wild typing\n");
2182 return 1;
2183 }
2184 } else { /* not identical, both wildcards */
2185 if (awild == CLI_MATCH_IGNORE || bwild == CLI_MATCH_IGNORE) {
2186 if (awild == CLI_MATCH_IGNORE) {
2187 side_wild |= 1;
2188 } else if (bwild == CLI_MATCH_IGNORE) {
2189 side_wild |= 2;
2190 }
2191 } else {
2192 /* only high and low nibbles should be left here */
2193 side_wild |= 3;
2194 }
2195 }
2196 }
2197
2198 /* both sides contain a wildcard that contains the other, therefore unique by wildcards */
2199 if (side_wild == 3)
2200 return 1;
2201 }
2202
2203 if (wild)
2204 *wild = side_wild;
2205 return 0;
2206 }
2207
2208 /* 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)2209 inline static int ac_addspecial_add_alt_node(const char *subexpr, uint8_t sigopts, struct cli_ac_special *special, struct cli_matcher *root)
2210 {
2211 struct cli_alt_node *newnode, **prev, *ins;
2212 uint16_t *s;
2213 int i, cmp, wild;
2214
2215 #ifndef USE_MPOOL
2216 UNUSEDPARAM(root);
2217 #endif
2218
2219 newnode = (struct cli_alt_node *)MPOOL_CALLOC(root->mempool, 1, sizeof(struct cli_alt_node));
2220 if (!newnode) {
2221 cli_errmsg("ac_addspecial_add_alt_node: Can't allocate new alternate node\n");
2222 return CL_EMEM;
2223 }
2224
2225 s = CLI_MPOOL_HEX2UI(root->mempool, subexpr);
2226 if (!s) {
2227 MPOOL_FREE(root->mempool, newnode);
2228 return CL_EMALFDB;
2229 }
2230
2231 newnode->str = s;
2232 newnode->len = (uint16_t)strlen(subexpr) / 2;
2233 newnode->unique = 1;
2234
2235 /* setting nocase match */
2236 if (sigopts & ACPATT_OPTION_NOCASE) {
2237 for (i = 0; i < newnode->len; ++i)
2238 if ((newnode->str[i] & CLI_MATCH_METADATA) == CLI_MATCH_CHAR) {
2239 newnode->str[i] = CLI_NOCASE(newnode->str[i] & 0xff);
2240 newnode->str[i] += CLI_MATCH_NOCASE;
2241 }
2242 }
2243
2244 /* search for uniqueness, TODO: directed acyclic word graph */
2245 prev = &((special->alt).v_str);
2246 ins = (special->alt).v_str;
2247 while (ins) {
2248 cmp = ac_uicmp(ins->str, ins->len, newnode->str, newnode->len, &wild);
2249 if (cmp == 0) {
2250 if (newnode->len != ins->len) { /* derivative */
2251 newnode->unique = 0;
2252 ins->unique = 0;
2253 } else if (wild == 0) { /* duplicate */
2254 MPOOL_FREE(root->mempool, newnode);
2255 return CL_SUCCESS;
2256 }
2257 } /* TODO - possible sorting of altstr uniques and derivative groups? */
2258
2259 prev = &(ins->next);
2260 ins = ins->next;
2261 }
2262
2263 *prev = newnode;
2264 newnode->next = ins;
2265 if ((special->num == 0) || (newnode->len < special->len[0]))
2266 special->len[0] = newnode->len;
2267 if ((special->num == 0) || (newnode->len > special->len[1]))
2268 special->len[1] = newnode->len;
2269 special->num++;
2270 return CL_SUCCESS;
2271 }
2272
2273 /* 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)2274 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)
2275 {
2276 int ret, scnt = 0, numexpr;
2277 char *ept, *sexpr, *end, term;
2278 char *fp;
2279
2280 ept = sexpr = hexpr;
2281 fp = subexpr + strlen(subexpr);
2282
2283 numexpr = ac_analyze_expr(hexpr, NULL, NULL);
2284
2285 /* while there are expressions to resolve */
2286 while (scnt < numexpr) {
2287 scnt++;
2288 while ((*ept != '(') && (*ept != '|') && (*ept != ')') && (*ept != '\0'))
2289 ept++;
2290
2291 /* check for invalid negation */
2292 term = *ept;
2293 if ((*ept == '(') && (ept >= hexpr + 1)) {
2294 if (ept[-1] == '!') {
2295 cli_errmsg("ac_special_altexpand: Generic alternates cannot contain negations\n");
2296 return CL_EMALFDB;
2297 }
2298 }
2299
2300 /* appended token */
2301 *ept = 0;
2302 if (cli_strlcat(subexpr, sexpr, maxlen) >= maxlen) {
2303 cli_errmsg("ac_special_altexpand: Unexpected expression larger than expected\n");
2304 return CL_EMEM;
2305 }
2306
2307 *ept++ = term;
2308 sexpr = ept;
2309
2310 if (term == '|') {
2311 if (lvl == 0) {
2312 if ((ret = ac_addspecial_add_alt_node(subexpr, sigopts, special, root)) != CL_SUCCESS)
2313 return ret;
2314 } else {
2315 find_paren_end(ept, &end);
2316 if (!end) {
2317 cli_errmsg("ac_special_altexpand: Missing closing parenthesis\n");
2318 return CL_EMALFDB;
2319 }
2320 end++;
2321
2322 if ((ret = ac_special_altexpand(end, subexpr, maxlen, lvl - 1, lvl, sigopts, special, root)) != CL_SUCCESS)
2323 return ret;
2324 }
2325
2326 *fp = 0;
2327 } else if (term == ')') {
2328 if (lvl == 0) {
2329 cli_errmsg("ac_special_altexpand: Unexpected closing parenthesis\n");
2330 return CL_EPARSE;
2331 }
2332
2333 if ((ret = ac_special_altexpand(ept, subexpr, maxlen, lvl - 1, lvl, sigopts, special, root)) != CL_SUCCESS)
2334 return ret;
2335 break;
2336 } else if (term == '(') {
2337 int inner, found;
2338 find_paren_end(ept, &end);
2339 if (!end) {
2340 cli_errmsg("ac_special_altexpand: Missing closing parenthesis\n");
2341 return CL_EMALFDB;
2342 }
2343 end++;
2344
2345 if ((ret = ac_special_altexpand(ept, subexpr, maxlen, lvl + 1, lvl + 1, sigopts, special, root)) != CL_SUCCESS)
2346 return ret;
2347
2348 /* move ept to end of current alternate expression (recursive call already populates them) */
2349 ept = end;
2350 inner = 0;
2351 found = 0;
2352 while (!found && *ept != '\0') {
2353 switch (*ept) {
2354 case '|':
2355 if (!inner)
2356 found = 1;
2357 break;
2358 case '(':
2359 inner++;
2360 break;
2361 case ')':
2362 inner--;
2363 break;
2364 }
2365 ept++;
2366 }
2367 if (*ept == '|')
2368 ept++;
2369
2370 sexpr = ept;
2371 *fp = 0;
2372 } else if (term == '\0') {
2373 if ((ret = ac_addspecial_add_alt_node(subexpr, sigopts, special, root)) != CL_SUCCESS)
2374 return ret;
2375 break;
2376 }
2377
2378 if (lvl != maxlvl)
2379 return CL_SUCCESS;
2380 }
2381 if (scnt != numexpr) {
2382 cli_errmsg("ac_addspecial: Mismatch in parsed and expected signature\n");
2383 return CL_EMALFDB;
2384 }
2385
2386 return CL_SUCCESS;
2387 }
2388
2389 /* alternate string specials (so many specials!) */
ac_special_altstr(const char * hexpr,uint8_t sigopts,struct cli_ac_special * special,struct cli_matcher * root)2390 inline static int ac_special_altstr(const char *hexpr, uint8_t sigopts, struct cli_ac_special *special, struct cli_matcher *root)
2391 {
2392 char *hexprcpy, *h, *c;
2393 int i, ret, num, fixed, slen;
2394
2395 if (!(hexprcpy = cli_strdup(hexpr))) {
2396 cli_errmsg("ac_special_altstr: Can't duplicate alternate expression\n");
2397 return CL_EDUP;
2398 }
2399
2400 num = ac_analyze_expr(hexprcpy, &fixed, &slen);
2401
2402 if (!sigopts && fixed) {
2403 special->num = 0;
2404 special->len[0] = special->len[1] = slen / 2;
2405 /* single-bytes are len 2 in hex */
2406 if (slen == 2) {
2407 special->type = AC_SPECIAL_ALT_CHAR;
2408 (special->alt).byte = (unsigned char *)MPOOL_MALLOC(root->mempool, num);
2409 if (!((special->alt).byte)) {
2410 cli_errmsg("cli_ac_special_altstr: Can't allocate newspecial->str\n");
2411 free(hexprcpy);
2412 return CL_EMEM;
2413 }
2414 } else {
2415 special->type = AC_SPECIAL_ALT_STR_FIXED;
2416 (special->alt).f_str = (unsigned char **)MPOOL_MALLOC(root->mempool, num * sizeof(unsigned char *));
2417 if (!((special->alt).f_str)) {
2418 cli_errmsg("cli_ac_special_altstr: Can't allocate newspecial->str\n");
2419 free(hexprcpy);
2420 return CL_EMEM;
2421 }
2422 }
2423
2424 for (i = 0; i < num; i++) {
2425 if (num == 1) {
2426 c = CLI_MPOOL_HEX2STR(root->mempool, hexprcpy);
2427 } else {
2428 if (!(h = cli_strtok(hexprcpy, i, "|"))) {
2429 free(hexprcpy);
2430 return CL_EMEM;
2431 }
2432 c = CLI_MPOOL_HEX2STR(root->mempool, h);
2433 free(h);
2434 }
2435 if (!c) {
2436 free(hexprcpy);
2437 return CL_EMALFDB;
2438 }
2439
2440 if (special->type == AC_SPECIAL_ALT_CHAR) {
2441 (special->alt).byte[i] = (unsigned char)*c;
2442 MPOOL_FREE(root->mempool, c);
2443 } else {
2444 (special->alt).f_str[i] = (unsigned char *)c;
2445 }
2446 special->num++;
2447 }
2448 /* sorting byte alternates */
2449 if (special->num > 1 && special->type == AC_SPECIAL_ALT_CHAR)
2450 cli_qsort((special->alt).byte, special->num, sizeof(unsigned char), qcompare_byte);
2451 /* sorting str alternates */
2452 if (special->num > 1 && special->type == AC_SPECIAL_ALT_STR_FIXED)
2453 cli_qsort_r((special->alt).f_str, special->num, sizeof(unsigned char *), qcompare_fstr, &(special->len));
2454 } else { /* generic alternates */
2455 char *subexpr;
2456 if (special->negative) {
2457 cli_errmsg("ac_special_altstr: Can't apply negation operation to generic alternate strings\n");
2458 free(hexprcpy);
2459 return CL_EMALFDB;
2460 }
2461
2462 special->type = AC_SPECIAL_ALT_STR;
2463
2464 /* allocate reusable subexpr */
2465 if (!(subexpr = cli_calloc(slen + 1, sizeof(char)))) {
2466 cli_errmsg("ac_special_altstr: Can't allocate subexpr container\n");
2467 free(hexprcpy);
2468 return CL_EMEM;
2469 }
2470
2471 ret = ac_special_altexpand(hexprcpy, subexpr, slen + 1, 0, 0, sigopts, special, root);
2472
2473 free(subexpr);
2474 free(hexprcpy);
2475 return ret;
2476 }
2477
2478 free(hexprcpy);
2479 return CL_SUCCESS;
2480 }
2481
2482 /* 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)2483 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)
2484 {
2485 struct cli_ac_patt *new;
2486 char *pt, *pt2, *hex = NULL, *hexcpy = NULL;
2487 uint16_t i, j, ppos = 0, pend, *dec, nzpos = 0;
2488 uint8_t wprefix = 0, zprefix = 1, plen = 0, nzplen = 0;
2489 struct cli_ac_special *newspecial, **newtable;
2490 int ret, error = CL_SUCCESS;
2491
2492 if (!root) {
2493 cli_errmsg("cli_ac_addsig: root == NULL\n");
2494 return CL_ENULLARG;
2495 }
2496
2497 if (strlen(hexsig) / 2 < root->ac_mindepth) {
2498 cli_errmsg("cli_ac_addsig: Signature for %s is too short\n", virname);
2499 return CL_EMALFDB;
2500 }
2501
2502 if ((new = (struct cli_ac_patt *)MPOOL_CALLOC(root->mempool, 1, sizeof(struct cli_ac_patt))) == NULL)
2503 return CL_EMEM;
2504
2505 new->rtype = rtype;
2506 new->type = type;
2507 new->sigid = sigid;
2508 new->parts = parts;
2509 new->partno = partno;
2510 new->mindist = mindist;
2511 new->maxdist = maxdist;
2512 new->customdata = NULL;
2513 new->ch[0] |= CLI_MATCH_IGNORE;
2514 new->ch[1] |= CLI_MATCH_IGNORE;
2515 if (lsigid) {
2516 new->lsigid[0] = 1;
2517 memcpy(&new->lsigid[1], lsigid, 2 * sizeof(uint32_t));
2518 }
2519
2520 if (strchr(hexsig, '[')) {
2521 if (!(hexcpy = cli_strdup(hexsig))) {
2522 MPOOL_FREE(root->mempool, new);
2523 return CL_EMEM;
2524 }
2525
2526 hex = hexcpy;
2527 for (i = 0; i < 2; i++) {
2528 unsigned int n, n1, n2;
2529
2530 if (!(pt = strchr(hex, '[')))
2531 break;
2532
2533 *pt++ = 0;
2534
2535 if (!(pt2 = strchr(pt, ']'))) {
2536 cli_dbgmsg("cli_ac_addsig: missing closing square bracket\n");
2537 error = CL_EMALFDB;
2538 break;
2539 }
2540
2541 *pt2++ = 0;
2542
2543 n = sscanf(pt, "%u-%u", &n1, &n2);
2544 if (n == 1) {
2545 n2 = n1;
2546 } else if (n != 2) {
2547 cli_dbgmsg("cli_ac_addsig: incorrect range inside square brackets\n");
2548 error = CL_EMALFDB;
2549 break;
2550 }
2551
2552 if ((n1 > n2) || (n2 > AC_CH_MAXDIST)) {
2553 cli_dbgmsg("cli_ac_addsig: incorrect range inside square brackets\n");
2554 error = CL_EMALFDB;
2555 break;
2556 }
2557
2558 if (strlen(hex) == 2) {
2559 if (i) {
2560 error = CL_EMALFDB;
2561 break;
2562 }
2563
2564 dec = cli_hex2ui(hex);
2565 if (!dec) {
2566 error = CL_EMALFDB;
2567 break;
2568 }
2569
2570 if ((sigopts & ACPATT_OPTION_NOCASE) && ((*dec & CLI_MATCH_METADATA) == CLI_MATCH_CHAR))
2571 new->ch[i] = CLI_NOCASE(*dec) | CLI_MATCH_NOCASE;
2572 else
2573 new->ch[i] = *dec;
2574 free(dec);
2575 new->ch_mindist[i] = n1;
2576 new->ch_maxdist[i] = n2;
2577 hex = pt2;
2578 } else if (strlen(pt2) == 2) {
2579 i = 1;
2580 dec = cli_hex2ui(pt2);
2581 if (!dec) {
2582 error = CL_EMALFDB;
2583 break;
2584 }
2585
2586 if ((sigopts & ACPATT_OPTION_NOCASE) && ((*dec & CLI_MATCH_METADATA) == CLI_MATCH_CHAR))
2587 new->ch[i] = CLI_NOCASE(*dec) | CLI_MATCH_NOCASE;
2588 else
2589 new->ch[i] = *dec;
2590 free(dec);
2591 new->ch_mindist[i] = n1;
2592 new->ch_maxdist[i] = n2;
2593 } else {
2594 error = CL_EMALFDB;
2595 break;
2596 }
2597 }
2598
2599 if (error) {
2600 free(hexcpy);
2601 MPOOL_FREE(root->mempool, new);
2602 return error;
2603 }
2604
2605 hex = cli_strdup(hex);
2606 free(hexcpy);
2607 if (!hex) {
2608 MPOOL_FREE(root->mempool, new);
2609 return CL_EMEM;
2610 }
2611 }
2612
2613 if (strchr(hexsig, '(')) {
2614 char *hexnew, *start;
2615 size_t nest;
2616 size_t hexnewsz;
2617
2618 if (hex) {
2619 hexcpy = hex;
2620 } else if (!(hexcpy = cli_strdup(hexsig))) {
2621 MPOOL_FREE(root->mempool, new);
2622 return CL_EMEM;
2623 }
2624
2625 hexnewsz = strlen(hexsig) + 1;
2626 if (!(hexnew = (char *)cli_calloc(1, hexnewsz))) {
2627 free(new);
2628 free(hexcpy);
2629 return CL_EMEM;
2630 }
2631
2632 start = pt = hexcpy;
2633 while ((pt = strchr(start, '('))) {
2634 *pt++ = 0;
2635
2636 if (!start) {
2637 error = CL_EMALFDB;
2638 break;
2639 }
2640 newspecial = (struct cli_ac_special *)MPOOL_CALLOC(root->mempool, 1, sizeof(struct cli_ac_special));
2641 if (!newspecial) {
2642 cli_errmsg("cli_ac_addsig: Can't allocate newspecial\n");
2643 error = CL_EMEM;
2644 break;
2645 }
2646 if (pt >= hexcpy + 2) {
2647 if (pt[-2] == '!') {
2648 newspecial->negative = 1;
2649 pt[-2] = 0;
2650 }
2651 }
2652 cli_strlcat(hexnew, start, hexnewsz);
2653
2654 nest = find_paren_end(pt, &start);
2655 if (!start) {
2656 cli_errmsg("cli_ac_addsig: Missing closing parenthesis\n");
2657 MPOOL_FREE(root->mempool, newspecial);
2658 error = CL_EMALFDB;
2659 break;
2660 }
2661 *start++ = 0;
2662 if (!strlen(pt)) {
2663 cli_errmsg("cli_ac_addsig: Empty block\n");
2664 MPOOL_FREE(root->mempool, newspecial);
2665 error = CL_EMALFDB;
2666 break;
2667 }
2668
2669 if (nest > ACPATT_ALTN_MAXNEST) {
2670 cli_errmsg("ac_addspecial: Expression exceeds maximum alternate nesting limit\n");
2671 MPOOL_FREE(root->mempool, newspecial);
2672 error = CL_EMALFDB;
2673 break;
2674 }
2675
2676 if (!strcmp(pt, "B")) {
2677 if (!*start) {
2678 new->boundary |= AC_BOUNDARY_RIGHT;
2679 if (newspecial->negative)
2680 new->boundary |= AC_BOUNDARY_RIGHT_NEGATIVE;
2681 MPOOL_FREE(root->mempool, newspecial);
2682 continue;
2683 } else if (pt - 1 == hexcpy) {
2684 new->boundary |= AC_BOUNDARY_LEFT;
2685 if (newspecial->negative)
2686 new->boundary |= AC_BOUNDARY_LEFT_NEGATIVE;
2687 MPOOL_FREE(root->mempool, newspecial);
2688 continue;
2689 }
2690 } else if (!strcmp(pt, "L")) {
2691 if (!*start) {
2692 new->boundary |= AC_LINE_MARKER_RIGHT;
2693 if (newspecial->negative)
2694 new->boundary |= AC_LINE_MARKER_RIGHT_NEGATIVE;
2695 MPOOL_FREE(root->mempool, newspecial);
2696 continue;
2697 } else if (pt - 1 == hexcpy) {
2698 new->boundary |= AC_LINE_MARKER_LEFT;
2699 if (newspecial->negative)
2700 new->boundary |= AC_LINE_MARKER_LEFT_NEGATIVE;
2701 MPOOL_FREE(root->mempool, newspecial);
2702 continue;
2703 }
2704 } else if (!strcmp(pt, "W")) {
2705 if (!*start) {
2706 new->boundary |= AC_WORD_MARKER_RIGHT;
2707 if (newspecial->negative)
2708 new->boundary |= AC_WORD_MARKER_RIGHT_NEGATIVE;
2709 MPOOL_FREE(root->mempool, newspecial);
2710 continue;
2711 } else if (pt - 1 == hexcpy) {
2712 new->boundary |= AC_WORD_MARKER_LEFT;
2713 if (newspecial->negative)
2714 new->boundary |= AC_WORD_MARKER_LEFT_NEGATIVE;
2715 MPOOL_FREE(root->mempool, newspecial);
2716 continue;
2717 }
2718 }
2719 cli_strlcat(hexnew, "()", hexnewsz);
2720 new->special++;
2721 newtable = (struct cli_ac_special **)MPOOL_REALLOC(root->mempool, new->special_table, new->special * sizeof(struct cli_ac_special *));
2722 if (!newtable) {
2723 new->special--;
2724 MPOOL_FREE(root->mempool, newspecial);
2725 cli_errmsg("cli_ac_addsig: Can't realloc new->special_table\n");
2726 error = CL_EMEM;
2727 break;
2728 }
2729 newtable[new->special - 1] = newspecial;
2730 new->special_table = newtable;
2731
2732 if (!strcmp(pt, "B")) {
2733 newspecial->type = AC_SPECIAL_BOUNDARY;
2734 } else if (!strcmp(pt, "L")) {
2735 newspecial->type = AC_SPECIAL_LINE_MARKER;
2736 } else if (!strcmp(pt, "W")) {
2737 newspecial->type = AC_SPECIAL_WORD_MARKER;
2738 } else {
2739 if ((ret = ac_special_altstr(pt, sigopts, newspecial, root)) != CL_SUCCESS) {
2740 error = ret;
2741 break;
2742 }
2743 }
2744 }
2745
2746 if (start)
2747 cli_strlcat(hexnew, start, hexnewsz);
2748
2749 hex = hexnew;
2750 free(hexcpy);
2751
2752 if (error) {
2753 free(hex);
2754 if (new->special) {
2755 mpool_ac_free_special(root->mempool, new);
2756 }
2757 MPOOL_FREE(root->mempool, new);
2758 return error;
2759 }
2760 }
2761
2762 new->pattern = CLI_MPOOL_HEX2UI(root->mempool, hex ? hex : hexsig);
2763 if (new->pattern == NULL) {
2764 if (new->special)
2765 mpool_ac_free_special(root->mempool, new);
2766
2767 MPOOL_FREE(root->mempool, new);
2768 free(hex);
2769 return CL_EMALFDB;
2770 }
2771
2772 new->length[0] = (uint16_t)strlen(hex ? hex : hexsig) / 2;
2773 for (i = 0, j = 0; i < new->length[0]; i++) {
2774 if ((new->pattern[i] & CLI_MATCH_METADATA) == CLI_MATCH_SPECIAL) {
2775 new->length[1] += new->special_table[j]->len[0];
2776 new->length[2] += new->special_table[j]->len[1];
2777 j++;
2778 } else {
2779 new->length[1]++;
2780 new->length[2]++;
2781 }
2782 }
2783
2784 free(hex);
2785
2786 new->sigopts = sigopts;
2787 /* setting nocase match */
2788 if (sigopts & ACPATT_OPTION_NOCASE) {
2789 for (i = 0; i < new->length[0]; i++)
2790 if ((new->pattern[i] & CLI_MATCH_METADATA) == CLI_MATCH_CHAR) {
2791 new->pattern[i] = CLI_NOCASE(new->pattern[i] & 0xff);
2792 new->pattern[i] += CLI_MATCH_NOCASE;
2793 }
2794 }
2795
2796 /* TODO - sigopts affect on filters? */
2797 if (root->filter) {
2798 /* so that we can show meaningful messages */
2799 new->virname = (char *)virname;
2800 if (filter_add_acpatt(root->filter, new) == -1) {
2801 cli_warnmsg("cli_ac_addpatt: cannot use filter for trie\n");
2802 MPOOL_FREE(root->mempool, root->filter);
2803 root->filter = NULL;
2804 }
2805
2806 /* TODO: should this affect maxpatlen? */
2807 }
2808
2809 for (i = 0; i < root->ac_maxdepth && i < new->length[0]; i++) {
2810 if (new->pattern[i] & CLI_MATCH_WILDCARD) {
2811 wprefix = 1;
2812 break;
2813 }
2814
2815 if (zprefix && new->pattern[i])
2816 zprefix = 0;
2817 }
2818
2819 if (wprefix || zprefix) {
2820 pend = new->length[0] - root->ac_mindepth + 1;
2821 for (i = 0; i < pend; i++) {
2822 for (j = i; j < i + root->ac_maxdepth && j < new->length[0]; j++) {
2823 if (new->pattern[j] & CLI_MATCH_WILDCARD) {
2824 break;
2825 } else {
2826 if (j - i + 1 >= plen) {
2827 plen = j - i + 1;
2828 ppos = i;
2829 }
2830 }
2831
2832 if (new->pattern[ppos] || new->pattern[ppos + 1]) {
2833 if (plen >= root->ac_maxdepth) {
2834 break;
2835 } else if (plen >= root->ac_mindepth && plen > nzplen) {
2836 nzplen = plen;
2837 nzpos = ppos;
2838 }
2839 }
2840 }
2841
2842 if (plen >= root->ac_maxdepth && (new->pattern[ppos] || new->pattern[ppos + 1]))
2843 break;
2844 }
2845
2846 if (!new->pattern[ppos] && !new->pattern[ppos + 1] && nzplen) {
2847 plen = nzplen;
2848 ppos = nzpos;
2849 }
2850
2851 if (plen < root->ac_mindepth) {
2852 cli_errmsg("cli_ac_addsig: Can't find a static subpattern of length %u\n", root->ac_mindepth);
2853 mpool_ac_free_special(root->mempool, new);
2854 MPOOL_FREE(root->mempool, new->pattern);
2855 MPOOL_FREE(root->mempool, new);
2856 return CL_EMALFDB;
2857 }
2858
2859 new->prefix = new->pattern;
2860 new->prefix_length[0] = ppos;
2861 for (i = 0, j = 0; i < new->prefix_length[0]; i++) {
2862 if ((new->prefix[i] & CLI_MATCH_WILDCARD) == CLI_MATCH_SPECIAL)
2863 new->special_pattern++;
2864
2865 if ((new->prefix[i] & CLI_MATCH_METADATA) == CLI_MATCH_SPECIAL) {
2866 new->prefix_length[1] += new->special_table[j]->len[0];
2867 new->prefix_length[2] += new->special_table[j]->len[1];
2868 j++;
2869 } else {
2870 new->prefix_length[1]++;
2871 new->prefix_length[2]++;
2872 }
2873 }
2874
2875 new->pattern = &new->prefix[ppos];
2876 new->length[0] -= new->prefix_length[0];
2877 new->length[1] -= new->prefix_length[1];
2878 new->length[2] -= new->prefix_length[2];
2879 }
2880
2881 if (new->length[2] + new->prefix_length[2] > root->maxpatlen)
2882 root->maxpatlen = new->length[2] + new->prefix_length[2];
2883
2884 new->virname = CLI_MPOOL_VIRNAME(root->mempool, virname, options & CL_DB_OFFICIAL);
2885 if (!new->virname) {
2886 MPOOL_FREE(root->mempool, new->prefix ? new->prefix : new->pattern);
2887 mpool_ac_free_special(root->mempool, new);
2888 MPOOL_FREE(root->mempool, new);
2889 return CL_EMEM;
2890 }
2891
2892 if (new->lsigid[0])
2893 root->ac_lsigtable[new->lsigid[1]]->virname = new->virname;
2894
2895 ret = cli_caloff(offset, NULL, root->type, new->offdata, &new->offset_min, &new->offset_max);
2896 if (ret != CL_SUCCESS) {
2897 MPOOL_FREE(root->mempool, new->prefix ? new->prefix : new->pattern);
2898 mpool_ac_free_special(root->mempool, new);
2899 MPOOL_FREE(root->mempool, new->virname);
2900 MPOOL_FREE(root->mempool, new);
2901 return ret;
2902 }
2903
2904 if ((ret = cli_ac_addpatt(root, new))) {
2905 MPOOL_FREE(root->mempool, new->prefix ? new->prefix : new->pattern);
2906 MPOOL_FREE(root->mempool, new->virname);
2907 mpool_ac_free_special(root->mempool, new);
2908 MPOOL_FREE(root->mempool, new);
2909 return ret;
2910 }
2911
2912 if (new->offdata[0] != CLI_OFF_ANY &&new->offdata[0] != CLI_OFF_ABSOLUTE &&new->offdata[0] != CLI_OFF_MACRO) {
2913 root->ac_reloff = (struct cli_ac_patt **)MPOOL_REALLOC2(root->mempool, root->ac_reloff, (root->ac_reloff_num + 1) * sizeof(struct cli_ac_patt *));
2914 if (!root->ac_reloff) {
2915 cli_errmsg("cli_ac_addsig: Can't allocate memory for root->ac_reloff\n");
2916 return CL_EMEM;
2917 }
2918
2919 root->ac_reloff[root->ac_reloff_num] = new;
2920 new->offset_min = root->ac_reloff_num * 2;
2921 new->offset_max = new->offset_min + 1;
2922 root->ac_reloff_num++;
2923 }
2924
2925 return CL_SUCCESS;
2926 }
2927