Line data Source code
1 : #include "../burp.h"
2 : #include "../alloc.h"
3 : #include "../handy.h"
4 : #include "../conf.h"
5 : #include "../conffile.h"
6 : #include "../regexp.h"
7 : #include "../strlist.h"
8 : #include "../log.h"
9 : #include "find.h"
10 : #include "find_logic.h"
11 :
12 : #include <uthash.h>
13 :
14 : #ifdef HAVE_LINUX_OS
15 : #include <sys/statfs.h>
16 : #endif
17 : #ifdef HAVE_SUN_OS
18 : #include <sys/statvfs.h>
19 : #endif
20 :
21 : typedef struct _node node;
22 : typedef struct _dllist dllist;
23 : typedef int TOKENS;
24 :
25 : // define our tokens as 'flags' to ease the parsing
26 : #define EVAL_FALSE 0 // The evaluated function returned FALSE
27 : #define EVAL_TRUE 1 // The evaluated function returned TRUE
28 : #define LEFT_PARENS 2 // (
29 : #define RIGHT_PARENS 3 // )
30 : #define AND_FUNC 4 // and
31 : #define OR_FUNC 5 // or
32 : #define NOT 6 // not
33 : #define GTE 7 // >=
34 : #define GT 8 // >
35 : #define LTE 9 // <=
36 : #define LT 10 // <
37 : #define EQ 11 // =
38 : #define PLACEHOLDER 99 // placeholder value
39 :
40 : // a node contains a TOKEN with a reference to its successor and ancestor
41 : struct _node
42 : {
43 : TOKENS val;
44 :
45 : node *next;
46 : node *prev;
47 : };
48 :
49 : // our expression will be converted in a doubly-linked list of nodes to ease
50 : // its evaluation
51 : struct _dllist
52 : {
53 : node *head;
54 : node *tail;
55 : size_t len;
56 : };
57 :
58 : // the first parsing will split the string expression in string tokens
59 : // ie. 'file_size>10Kb and (file_ext=pst or file_ext=ost)' =>
60 : // {"file_size>10Kb", "and", "(", "file_ext=pst", "or", "file_ext=ost", ")"}
61 : struct tokens
62 : {
63 : char **list;
64 : size_t size;
65 : int valid;
66 : };
67 :
68 : // an expression is a hash record to retrieve already parsed records
69 : struct expression
70 : {
71 : char *id;
72 : struct tokens *tokens;
73 : UT_hash_handle hh;
74 : };
75 :
76 : // a cregex is a pre-compiled regex
77 : struct cregex
78 : {
79 : char *id;
80 : regex_t *compiled;
81 : UT_hash_handle hh;
82 : };
83 :
84 : // these are some caches
85 : struct expression *cache=NULL;
86 : struct cregex *regex_cache=NULL;
87 :
88 6 : static void free_tokens(struct tokens *ptr)
89 : {
90 6 : if(!ptr) return;
91 6 : free_list_w(&ptr->list, ptr->size);
92 6 : free_v((void **)&ptr);
93 : }
94 :
95 6 : static void free_expression(struct expression *ptr)
96 : {
97 6 : if(!ptr) return;
98 6 : free_tokens(ptr->tokens);
99 6 : free_v((void **)&ptr);
100 : }
101 :
102 : static void free_cregex(struct cregex *ptr)
103 : {
104 : if(!ptr) return;
105 2 : regex_free(&(ptr->compiled));
106 2 : free_v((void **)&ptr);
107 : }
108 :
109 : static void free_node(node **ptr)
110 : {
111 0 : if(!*ptr) return;
112 498 : free_v((void **)ptr);
113 : }
114 :
115 : // append a node to a given list
116 : static void list_append(dllist **list, node *data)
117 : {
118 462 : dllist *l=*list;
119 462 : if(!l || !data) return;
120 462 : if(!l->tail)
121 : {
122 148 : l->head=data;
123 148 : l->tail=data;
124 148 : data->prev=NULL;
125 148 : data->next=NULL;
126 : }
127 : else
128 : {
129 314 : l->tail->next=data;
130 314 : data->prev=l->tail;
131 314 : l->tail=data;
132 314 : data->next=NULL;
133 : }
134 462 : l->len++;
135 : }
136 :
137 : // retrieve a node by its position in the list
138 : static node *list_get_node_by_id(dllist *list, int id)
139 : {
140 72 : node *ret=NULL;
141 72 : int cpt=0;
142 72 : if(!list || id<0 || id>(int)list->len) return ret;
143 72 : ret=list->head;
144 72 : for(cpt=0, ret=list->head; ret && cpt<id; cpt++, ret=ret->next);
145 72 : if(cpt<id) return NULL; // id out of range
146 : return ret;
147 : }
148 :
149 : // empty list
150 189 : static void list_reset(dllist **list)
151 : {
152 : node *tmp;
153 189 : dllist *l=*list;
154 230 : if(!l || l->len==0) return;
155 148 : tmp=l->tail;
156 466 : while(tmp)
157 : {
158 318 : node *buf=tmp->prev;
159 318 : l->tail=buf;
160 318 : if(l->tail)
161 170 : l->tail->next=NULL;
162 318 : l->len--;
163 318 : tmp->prev=NULL;
164 318 : free_node(&tmp);
165 318 : tmp=buf;
166 : }
167 : }
168 :
169 : static dllist *new_list(void)
170 : {
171 : dllist *ret;
172 147 : if(!(ret=(dllist *)malloc_w(sizeof(*ret), __func__))) return NULL;
173 147 : ret->len=0;
174 147 : ret->head=NULL;
175 147 : ret->tail=NULL;
176 : return ret;
177 : }
178 :
179 : static node *new_node(int value)
180 : {
181 : node *ret;
182 498 : if(!(ret=(node *)malloc_w(sizeof(*ret), __func__))) return NULL;
183 498 : ret->val=value;
184 498 : ret->next=NULL;
185 498 : ret->prev=NULL;
186 : return ret;
187 : }
188 :
189 : // here we actually convert our expression into a list of string tokens
190 6 : static struct tokens *create_token_list(char *expr)
191 : {
192 6 : char *n=NULL;
193 6 : char *n2=NULL;
194 6 : char **toks=NULL;
195 6 : size_t nb_elements=0;
196 6 : struct tokens *ret=NULL;
197 : int opened, closed;
198 :
199 6 : if(!(n=charreplace_noescaped_w(expr, '(', " ( ", &opened, __func__))) goto end;
200 6 : if(!(n2=charreplace_noescaped_w(n, ')', " ) ", &closed, __func__))) goto end;
201 6 : if(!(toks=charsplit_noescaped_w(n2, ' ', &nb_elements, __func__))) goto end;
202 6 : if(!(ret=(struct tokens *)malloc_w(sizeof(*ret), __func__))) goto end;
203 :
204 6 : ret->list=toks;
205 6 : ret->size=nb_elements;
206 6 : ret->valid=(opened==closed);
207 : end:
208 6 : free_w(&n);
209 6 : free_w(&n2);
210 6 : return ret;
211 : }
212 :
213 : // we create our "expression" record to be cached
214 6 : static struct expression *parse_expression(char *expr)
215 : {
216 6 : struct expression *ret=NULL;
217 : struct tokens *toks;
218 6 : if(!(toks=create_token_list(expr))) return ret;
219 6 : if(!(ret=(struct expression *)malloc_w(sizeof(*ret), __func__))) goto error;
220 6 : ret->tokens=toks;
221 6 : ret->id=expr;
222 6 : return ret;
223 : error:
224 0 : free_tokens(toks);
225 0 : return ret;
226 : }
227 :
228 : // search for the positions of the 'what' token in our tokens list
229 107 : static void find(dllist *toks, TOKENS what, int start, dllist **positions)
230 : {
231 : int i;
232 : node *tmp;
233 865 : for(i=0, tmp=toks->head; i<(int)toks->len; i++, tmp=tmp->next)
234 : {
235 758 : if(i<start) continue; // skip the unwanted positions
236 596 : if(tmp && tmp->val==what) list_append(positions, new_node(i));
237 : }
238 107 : }
239 :
240 : // search for parentheses and return their positions
241 : // always return the deepest parentheses first
242 : // example:
243 : // false or ( false or ( true or false ) )
244 : // 1 => ^ ^ (true, 5, 9)
245 : // 2 => ^ ^ (true, 2, 10)
246 71 : static void parens(dllist *toks, int *has, int *left, int *right)
247 : {
248 : dllist *positions;
249 71 : if(!(positions=new_list()))
250 : {
251 0 : *has=0;
252 0 : *left=-1;
253 0 : *right=-1;
254 0 : return;
255 : }
256 71 : find(toks, LEFT_PARENS, 0, &positions);
257 71 : if(positions->len==0)
258 : {
259 35 : *has=0;
260 35 : *left=-1;
261 35 : *right=-1;
262 35 : goto end;
263 : }
264 36 : *left=positions->tail->val;
265 36 : list_reset(&positions);
266 36 : find(toks, RIGHT_PARENS, *left+4, &positions);
267 36 : if(positions->len==0)
268 : {
269 : // special case (token) instead of ( token or/and token )
270 0 : list_reset(&positions);
271 0 : find(toks, RIGHT_PARENS, *left+1, &positions);
272 : }
273 36 : *right=positions->head->val;
274 36 : *has=1;
275 : end:
276 71 : list_reset(&positions);
277 71 : free_v((void **)&positions);
278 : }
279 :
280 : // utility function
281 68 : static char *strip_quotes(char *src)
282 : {
283 : int len;
284 68 : char *strip=NULL;
285 68 : if(!(len=strlen(src))) goto end;
286 68 : if((*src=='\'' || *src=='"') && *src==src[len-1]) // strip the quotes
287 : {
288 1 : if(!(strip=(char *)malloc_w(len-1, __func__))) goto end;
289 1 : strip=strncpy(strip, src+1, len-2);
290 1 : strip[len-2]='\0';
291 : }
292 : end:
293 68 : return strip;
294 : }
295 :
296 : // function 'file_ext'
297 16 : static int eval_file_ext(char *tok, const char *fname)
298 : {
299 : const char *cp;
300 : int len;
301 16 : char *strip=NULL;
302 16 : if(!(len=strlen(tok))) goto end;
303 16 : for(; *tok=='='; ++tok);
304 16 : if(!(len=strlen(tok))) goto end; // test again after we trimmed the '='
305 16 : strip=strip_quotes(tok);
306 302 : for(cp=fname+strlen(fname)-1; cp>=fname; cp--)
307 : {
308 288 : if(*cp!='.') continue;
309 4 : if((strip && !strcasecmp(strip, cp+1))
310 4 : || (!strip && !strcasecmp(tok, cp+1)))
311 : return EVAL_TRUE;
312 : }
313 : end:
314 14 : free_w(&strip);
315 14 : return EVAL_FALSE;
316 : }
317 :
318 : // function 'path_match'
319 18 : static int eval_path_match(char *tok, const char *fname)
320 : {
321 18 : int ret=EVAL_FALSE;
322 : struct cregex *reg;
323 18 : char *strip=NULL;
324 18 : if(strlen(tok)==0) goto end;
325 18 : for(; *tok=='='; ++tok);
326 18 : if(strlen(tok)==0) goto end; // test again after we trimmed the '='
327 18 : if(regex_cache)
328 17 : HASH_FIND_STR(regex_cache, tok, reg);
329 : else
330 : reg=NULL;
331 18 : if(!reg)
332 : {
333 : regex_t *tmp;
334 2 : if((strip=strip_quotes(tok)))
335 1 : tmp=regex_compile(strip);
336 : else
337 1 : tmp=regex_compile(tok);
338 2 : if(!(reg=(struct cregex *)malloc_w(sizeof(*reg), __func__)))
339 : {
340 0 : regex_free(&tmp);
341 0 : goto end;
342 : }
343 2 : reg->id=strdup_w(tok, __func__);
344 2 : reg->compiled=tmp;
345 2 : HASH_ADD_KEYPTR(hh, regex_cache, reg->id, strlen(reg->id), reg);
346 : }
347 18 : if(regex_check(reg->compiled, fname))
348 4 : ret=EVAL_TRUE;
349 : end:
350 18 : free_w(&strip);
351 18 : return ret;
352 : }
353 :
354 : // function 'file_match'
355 10 : static int eval_file_match(char *tok, const char *fname)
356 : {
357 10 : int len=strlen(fname);
358 10 : for(; len>0 && fname[len-1]!='/'; len--);
359 10 : return eval_path_match(tok, fname+len);
360 : }
361 :
362 : // function 'file_size'
363 50 : static int eval_file_size(char *tok, uint64_t filesize)
364 : {
365 50 : int ret=EVAL_FALSE;
366 50 : char *strip=NULL;
367 50 : TOKENS eval=PLACEHOLDER;
368 50 : uint64_t s=0;
369 50 : if(strlen(tok)==0) goto end;
370 92 : for(; ; tok++)
371 : {
372 234 : if(*tok!='>' && *tok!='<' && *tok!='=') break;
373 92 : switch(*tok)
374 : {
375 : case '<':
376 18 : eval=LT;
377 18 : break;
378 : case '>':
379 24 : eval=GT;
380 24 : break;
381 : case '=':
382 50 : switch(eval)
383 : {
384 : case LT:
385 : eval=LTE;
386 : break;
387 : case GT:
388 24 : eval=GTE;
389 24 : break;
390 : case PLACEHOLDER:
391 : case EQ:
392 8 : eval=EQ;
393 8 : break;
394 : default:
395 0 : eval=EVAL_FALSE;
396 : }
397 : break;
398 : }
399 : }
400 50 : if((strip=strip_quotes(tok)))
401 0 : get_file_size(strip, &s, NULL, -1);
402 : else
403 50 : get_file_size(tok, &s, NULL, -1);
404 50 : switch(eval)
405 : {
406 : case LT:
407 0 : ret=filesize<s;
408 0 : break;
409 : case LTE:
410 18 : ret=filesize<=s;
411 18 : break;
412 : case GT:
413 0 : ret=filesize>s;
414 0 : break;
415 : case GTE:
416 24 : ret=filesize>=s;
417 24 : break;
418 : case EQ:
419 8 : ret=filesize==s;
420 8 : break;
421 : default:
422 : ret=EVAL_FALSE;
423 : }
424 : end:
425 50 : free_w(&strip);
426 50 : return ret;
427 : }
428 :
429 : // search what function to use
430 122 : static int eval_func(char *tok, const char *filename, uint64_t filesize)
431 : {
432 : int ret;
433 122 : if(!strncmp(tok, "file_ext", 8))
434 16 : ret=eval_file_ext(tok+8, filename);
435 106 : else if(!strncmp(tok, "file_match", 10))
436 10 : ret=eval_file_match(tok+10, filename);
437 96 : else if(!strncmp(tok, "path_match", 10))
438 8 : ret=eval_path_match(tok+10, filename);
439 88 : else if(!strncmp(tok, "file_size", 9))
440 50 : ret=eval_file_size(tok+9, filesize);
441 : else
442 : ret=EVAL_FALSE;
443 122 : return ret;
444 : }
445 :
446 : // convert a string token into a TOKENS
447 254 : static node *str_to_node(char *tok, const char *filename, uint64_t filesize)
448 : {
449 : int ret;
450 254 : if(!strncmp(tok, "and", 3))
451 : ret=AND_FUNC;
452 212 : else if(!strncmp(tok, "or", 2))
453 : ret=OR_FUNC;
454 194 : else if(!strncmp(tok, "(", 1))
455 : ret=LEFT_PARENS;
456 158 : else if(!strncmp(tok, ")", 1))
457 : ret=RIGHT_PARENS;
458 122 : else if(!strncmp(tok, "not", 3))
459 : ret=NOT;
460 : else
461 122 : ret=eval_func(tok, filename, filesize);
462 254 : return new_node(ret);
463 : }
464 :
465 : // evaluate a trio of tokens like 'true or false'
466 : static int eval_triplet(node *head, int def)
467 : {
468 : TOKENS left, func, right;
469 71 : left=head->val;
470 71 : func=head->next->val;
471 71 : right=head->next->next->val;
472 71 : switch(func)
473 : {
474 : case AND_FUNC:
475 42 : return left && right;
476 : case OR_FUNC:
477 18 : return left || right;
478 : default:
479 : return def;
480 : }
481 : }
482 :
483 : // factorise tokens by recursively evaluating them
484 76 : static int bool_eval(dllist **tokens, int def)
485 : {
486 76 : dllist *toks=*tokens;
487 76 : if(toks->len==1)
488 0 : return toks->head->val;
489 76 : else if(toks->len==2)
490 : {
491 5 : switch(toks->head->val)
492 : {
493 : case NOT:
494 0 : return !toks->tail->val;
495 : default:
496 5 : return toks->tail->val;
497 : }
498 : }
499 : /* here we search for 'not' tokens */
500 71 : if(toks->len>3)
501 : {
502 : dllist *new_tokens;
503 : node *tmp;
504 5 : int negate=0, is_negation=0;
505 25 : for(tmp=toks->head; tmp; tmp=tmp->next)
506 : {
507 20 : if(tmp->val==NOT)
508 : {
509 : is_negation=1;
510 : break;
511 : }
512 : }
513 5 : if(is_negation)
514 : {
515 0 : if(!(new_tokens=new_list())) return 0;
516 0 : for(tmp=toks->head; tmp; tmp=tmp->next)
517 : {
518 0 : if(tmp->val==NOT)
519 0 : negate=!negate;
520 : else
521 : {
522 0 : if(negate)
523 : {
524 0 : list_append(&new_tokens, new_node(!(tmp->val)));
525 : negate=0;
526 : }
527 : else
528 : {
529 0 : list_append(&new_tokens, new_node(tmp->val));
530 : }
531 : }
532 : }
533 0 : list_reset(tokens);
534 0 : free_v((void **)tokens);
535 0 : *tokens=new_tokens;
536 0 : toks=*tokens;
537 : }
538 : }
539 : /* here we don't have any negations anymore, but we may have chains of
540 : * expressions to evaluate recursively */
541 71 : if(toks->len>3)
542 : {
543 : node *tmp;
544 : dllist *new_tokens;
545 : int i;
546 15 : tmp=new_node(eval_triplet(toks->head, def));
547 5 : if(!(new_tokens=new_list()))
548 : {
549 : free_node(&tmp);
550 : return 0;
551 : }
552 10 : list_append(&new_tokens, tmp);
553 25 : for(tmp=toks->head, i=0; tmp; tmp=tmp->next, i++)
554 : {
555 20 : if(i<3) continue;
556 10 : list_append(&new_tokens, new_node(tmp->val));
557 : }
558 5 : list_reset(tokens);
559 5 : free_v((void **)tokens);
560 5 : *tokens=new_tokens;
561 5 : toks=*tokens;
562 5 : return bool_eval(tokens, def);
563 : }
564 66 : if(toks->len%3!=0) return def;
565 66 : return eval_triplet(toks->head, def);
566 : }
567 :
568 : // evaluate our list of tokens
569 71 : static int eval_parsed_expression(dllist **tokens, int def)
570 : {
571 71 : dllist *toks=*tokens, *sub;
572 : node *begin, *end, *tmp;
573 : int has, left, right, count;
574 71 : if(!toks || toks->len==0) return def;
575 71 : if(toks->len==1) return toks->head->val;
576 71 : parens(toks, &has, &left, &right);
577 : // we don't have parentheses, we can evaluate the tokens
578 71 : if(!has)
579 35 : return bool_eval(tokens, def);
580 : // we have parentheses
581 : // we retrieve the two nodes '(' and ')'
582 72 : begin=list_get_node_by_id(toks, left);
583 72 : end=list_get_node_by_id(toks, right);
584 : // then we capture only the tokens surrounded by the parentheses
585 36 : if(!(sub=new_list())) return def;
586 36 : tmp=begin->next;
587 36 : count=0;
588 180 : while(tmp && count<right-left-1)
589 : {
590 324 : list_append(&sub, new_node(tmp->val));
591 108 : tmp=tmp->next;
592 108 : count++;
593 : }
594 36 : count++;
595 : // evaluate the inner expression
596 72 : tmp=new_node(bool_eval(&sub, def));
597 : // we replace all the tokens parentheses included with the new computed node
598 : // first element of the list
599 36 : if(!begin->prev)
600 18 : (*tokens)->head=tmp;
601 18 : else if (!end->next) // last element of the list
602 18 : (*tokens)->tail=tmp;
603 36 : toks->len-=count; // decrement our list size
604 36 : tmp->prev=begin->prev;
605 36 : tmp->next=end->next;
606 36 : if(begin->prev)
607 18 : begin->prev->next=tmp;
608 18 : else if(end->next)
609 18 : end->next->prev=tmp;
610 : // cleanup "orphans" nodes
611 36 : tmp=begin;
612 252 : while(tmp && count>=0)
613 : {
614 180 : if(tmp)
615 : {
616 180 : node *buf=tmp->next;
617 180 : free_node(&tmp);
618 180 : tmp=buf;
619 180 : count--;
620 : }
621 : }
622 36 : list_reset(&sub);
623 36 : free_v((void **)&sub);
624 36 : return eval_parsed_expression(tokens, def);
625 : }
626 :
627 41 : static int eval_expression(char *expr, const char *filename, uint64_t filesize, int def)
628 : {
629 41 : int ret=def, i;
630 : struct expression *parsed;
631 41 : dllist *tokens=NULL;
632 41 : if(cache)
633 40 : HASH_FIND_STR(cache, expr, parsed);
634 : else
635 : parsed=NULL;
636 41 : if(!parsed)
637 : {
638 6 : if(!(parsed=parse_expression(expr))) return def;
639 6 : HASH_ADD_KEYPTR(hh, cache, parsed->id, strlen(parsed->id), parsed);
640 : }
641 41 : if(!parsed || !parsed->tokens->valid) goto end;
642 35 : if(!(tokens=new_list())) goto end;
643 254 : for(i=0; i<(int)parsed->tokens->size; i++)
644 508 : list_append(&tokens, str_to_node(parsed->tokens->list[i], filename, filesize));
645 35 : ret=eval_parsed_expression(&tokens, def);
646 : end:
647 41 : list_reset(&tokens);
648 41 : free_v((void **)&tokens);
649 41 : return ret;
650 : }
651 :
652 : // cleanup our caches
653 15 : void free_logic_cache(void)
654 : {
655 : struct expression *parsed, *tmp;
656 : struct cregex *reg, *tmp2;
657 15 : if(cache)
658 : {
659 7 : HASH_ITER(hh, cache, parsed, tmp)
660 : {
661 6 : HASH_DEL(cache, parsed);
662 6 : free_expression(parsed);
663 : }
664 : }
665 15 : if(regex_cache)
666 : {
667 3 : HASH_ITER(hh, regex_cache, reg, tmp2)
668 : {
669 2 : HASH_DEL(regex_cache, reg);
670 2 : free_w(&(reg->id));
671 2 : free_cregex(reg);
672 : }
673 : }
674 15 : }
675 :
676 : /* return 1 if there is a match, 'def' is there isn't any match, and 'miss' if
677 : * there are no rules to eval */
678 77 : static int is_logic(struct strlist *list, struct FF_PKT *ff, int miss, int def)
679 : {
680 77 : if(!list) return miss;
681 11 : if(!S_ISREG(ff->statp.st_mode)) return def; // ignore directories
682 36 : for(; list; list=list->next)
683 41 : if(eval_expression(list->path, ff->fname, (uint64_t)ff->statp.st_size, miss))
684 : return 1;
685 : return def;
686 : }
687 :
688 77 : int is_logic_excluded(struct conf **confs, struct FF_PKT *ff)
689 : {
690 77 : return is_logic(get_strlist(confs[OPT_EXCLOGIC]), ff, /* missing */ 0, /* default */ 0);
691 : }
692 :
693 0 : int is_logic_included(struct conf **confs, struct FF_PKT *ff)
694 : {
695 0 : return is_logic(get_strlist(confs[OPT_INCLOGIC]), ff, /* missing */ 1, /* default */ 0);
696 : }
|
