?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
math: remove the get_implied_value_low_overhead() function
[smatch.git] / smatch_kernel_user_data.c
blob879b286c5a62520ba28006d65f1fbe23f2248b7d
1 /*
2 * Copyright (C) 2011 Dan Carpenter.
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License
6 * as published by the Free Software Foundation; either version 2
7 * of the License, or (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
16 */
17
18 /*
19 * There are a couple checks that try to see if a variable
20 * comes from the user. It would be better to unify them
21 * into one place. Also it we should follow the data down
22 * the call paths. Hence this file.
23 */
24
25 #include "smatch.h"
26 #include "smatch_slist.h"
27 #include "smatch_extra.h"
28
29 static int my_id;
30 static int my_call_id;
31
32 STATE(called);
33 static bool func_gets_user_data;
34
35 static const char *kstr_funcs[] = {
36 "kstrtoull", "kstrtoll", "kstrtoul", "kstrtol", "kstrtouint",
37 "kstrtoint", "kstrtou64", "kstrtos64", "kstrtou32", "kstrtos32",
38 "kstrtou16", "kstrtos16", "kstrtou8", "kstrtos8", "kstrtoull_from_user"
39 "kstrtoll_from_user", "kstrtoul_from_user", "kstrtol_from_user",
40 "kstrtouint_from_user", "kstrtoint_from_user", "kstrtou16_from_user",
41 "kstrtos16_from_user", "kstrtou8_from_user", "kstrtos8_from_user",
42 "kstrtou64_from_user", "kstrtos64_from_user", "kstrtou32_from_user",
43 "kstrtos32_from_user",
44 };
45
46 static const char *returns_user_data[] = {
47 "simple_strtol", "simple_strtoll", "simple_strtoul", "simple_strtoull",
48 "kvm_register_read",
49 };
50
51 static const char *returns_pointer_to_user_data[] = {
52 "nlmsg_data", "nla_data", "memdup_user", "kmap_atomic", "skb_network_header",
53 };
54
55 static void set_points_to_user_data(struct expression *expr);
56
57 static struct stree *start_states;
58 static struct stree_stack *saved_stack;
59 static void save_start_states(struct statement *stmt)
60 {
61 start_states = clone_stree(__get_cur_stree());
62 }
63
64 static void free_start_states(void)
65 {
66 free_stree(&start_states);
67 }
68
69 static void match_save_states(struct expression *expr)
70 {
71 push_stree(&saved_stack, start_states);
72 start_states = NULL;
73 }
74
75 static void match_restore_states(struct expression *expr)
76 {
77 free_stree(&start_states);
78 start_states = pop_stree(&saved_stack);
79 }
80
81 static struct smatch_state *empty_state(struct sm_state *sm)
82 {
83 return alloc_estate_empty();
84 }
85
86 static void pre_merge_hook(struct sm_state *sm)
87 {
88 struct smatch_state *user;
89 struct smatch_state *extra;
90 struct range_list *rl;
91 sval_t dummy, max;
92
93 user = get_state(my_id, sm->name, sm->sym);
94 if (!user || !estate_rl(user))
95 return;
96
97 if (!__in_function_def && !estate_rl(sm->state)) {
98 /* The situation here looks like:
99 *
100 * if (user_var > trusted)
101 * user_var = trusted; <-- empty state
102 * else
103 * <-- capped (but to an unknown)
104 *
105 * The one side is capped and the other side is set to an
106 * unknown limit. In that case, we want to set the capped side
107 * to an empty rl.
108 *
109 * The difficulty lies in knowing that the limit is unknown
110 * because we just have a binary capped vs uncapped. Also the
111 * API doesn't let us select the extra state from the other
112 * stree. (FIXME?).
113 *
114 */
115 max = estate_max(user);
116
117 if (is_capped_var_sym(sm->name, sm->sym) && sval_is_a_max(max)) {
118 set_state(my_id, sm->name, sm->sym, alloc_estate_empty());
119 return;
120 }
121 }
122 extra = get_state(SMATCH_EXTRA, sm->name, sm->sym);
123 if (!extra)
124 return;
125 rl = rl_intersection(estate_rl(user), estate_rl(extra));
126 if (rl_to_sval(rl, &dummy))
127 rl = NULL;
128 set_state(my_id, sm->name, sm->sym, alloc_estate_rl(clone_rl(rl)));
129 }
130
131 static void extra_nomod_hook(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state)
132 {
133 struct smatch_state *user;
134 struct range_list *rl;
135
136 user = get_state(my_id, name, sym);
137 if (!user)
138 return;
139 rl = rl_intersection(estate_rl(user), estate_rl(state));
140 if (rl_equiv(rl, estate_rl(user)))
141 return;
142 set_state(my_id, name, sym, alloc_estate_rl(rl));
143 }
144
145 static void tag_inner_struct_members(struct expression *expr, struct symbol *member)
146 {
147 struct expression *edge_member;
148 struct symbol *base = get_real_base_type(member);
149 struct symbol *tmp;
150
151 if (member->ident)
152 expr = member_expression(expr, '.', member->ident);
153
154 FOR_EACH_PTR(base->symbol_list, tmp) {
155 struct symbol *type;
156
157 type = get_real_base_type(tmp);
158 if (!type)
159 continue;
160
161 if (type->type == SYM_UNION || type->type == SYM_STRUCT) {
162 tag_inner_struct_members(expr, tmp);
163 continue;
164 }
165
166 if (!tmp->ident)
167 continue;
168
169 edge_member = member_expression(expr, '.', tmp->ident);
170 set_state_expr(my_id, edge_member, alloc_estate_whole(type));
171 } END_FOR_EACH_PTR(tmp);
172 }
173
174 static void tag_struct_members(struct symbol *type, struct expression *expr)
175 {
176 struct symbol *tmp;
177 struct expression *member;
178 int op = '*';
179
180 if (expr->type == EXPR_PREOP && expr->op == '&') {
181 expr = strip_expr(expr->unop);
182 op = '.';
183 }
184
185 FOR_EACH_PTR(type->symbol_list, tmp) {
186 type = get_real_base_type(tmp);
187 if (!type)
188 continue;
189
190 if (type->type == SYM_UNION || type->type == SYM_STRUCT) {
191 tag_inner_struct_members(expr, tmp);
192 continue;
193 }
194
195 if (!tmp->ident)
196 continue;
197
198 member = member_expression(expr, op, tmp->ident);
199 set_state_expr(my_id, member, alloc_estate_whole(get_type(member)));
200
201 if (type->type == SYM_ARRAY)
202 set_points_to_user_data(member);
203 } END_FOR_EACH_PTR(tmp);
204 }
205
206 static void tag_base_type(struct expression *expr)
207 {
208 if (expr->type == EXPR_PREOP && expr->op == '&')
209 expr = strip_expr(expr->unop);
210 else
211 expr = deref_expression(expr);
212 set_state_expr(my_id, expr, alloc_estate_whole(get_type(expr)));
213 }
214
215 static void tag_as_user_data(struct expression *expr)
216 {
217 struct symbol *type;
218
219 expr = strip_expr(expr);
220
221 type = get_type(expr);
222 if (!type || type->type != SYM_PTR)
223 return;
224 type = get_real_base_type(type);
225 if (!type)
226 return;
227 if (type == &void_ctype) {
228 set_state_expr(my_id, deref_expression(expr), alloc_estate_whole(&ulong_ctype));
229 return;
230 }
231 if (type->type == SYM_BASETYPE)
232 tag_base_type(expr);
233 if (type->type == SYM_STRUCT || type->type == SYM_UNION) {
234 if (expr->type != EXPR_PREOP || expr->op != '&')
235 expr = deref_expression(expr);
236 else
237 set_state_expr(my_id, deref_expression(expr), alloc_estate_whole(&ulong_ctype));
238 tag_struct_members(type, expr);
239 }
240 }
241
242 static void match_user_copy(const char *fn, struct expression *expr, void *_param)
243 {
244 int param = PTR_INT(_param);
245 struct expression *dest;
246
247 func_gets_user_data = true;
248
249 dest = get_argument_from_call_expr(expr->args, param);
250 dest = strip_expr(dest);
251 if (!dest)
252 return;
253 tag_as_user_data(dest);
254 }
255
256 static int is_dev_attr_name(struct expression *expr)
257 {
258 char *name;
259 int ret = 0;
260
261 name = expr_to_str(expr);
262 if (!name)
263 return 0;
264 if (strstr(name, "->attr.name"))
265 ret = 1;
266 free_string(name);
267 return ret;
268 }
269
270 static int ends_in_n(struct expression *expr)
271 {
272 struct string *str;
273
274 if (!expr)
275 return 0;
276 if (expr->type != EXPR_STRING || !expr->string)
277 return 0;
278
279 str = expr->string;
280 if (str->length < 3)
281 return 0;
282
283 if (str->data[str->length - 3] == '%' &&
284 str->data[str->length - 2] == 'n')
285 return 1;
286 return 0;
287 }
288
289 static void match_sscanf(const char *fn, struct expression *expr, void *unused)
290 {
291 struct expression *str, *format, *arg;
292 int i, last;
293
294 func_gets_user_data = true;
295
296 str = get_argument_from_call_expr(expr->args, 0);
297 if (is_dev_attr_name(str))
298 return;
299
300 format = get_argument_from_call_expr(expr->args, 1);
301 if (is_dev_attr_name(format))
302 return;
303
304 last = ptr_list_size((struct ptr_list *)expr->args) - 1;
305
306 i = -1;
307 FOR_EACH_PTR(expr->args, arg) {
308 i++;
309 if (i < 2)
310 continue;
311 if (i == last && ends_in_n(format))
312 continue;
313 tag_as_user_data(arg);
314 } END_FOR_EACH_PTR(arg);
315 }
316
317 static int is_skb_data(struct expression *expr)
318 {
319 struct symbol *sym;
320
321 if (!expr)
322 return 0;
323
324 if (expr->type == EXPR_BINOP && expr->op == '+')
325 return is_skb_data(expr->left);
326
327 expr = strip_expr(expr);
328 if (!expr)
329 return 0;
330 if (expr->type != EXPR_DEREF || expr->op != '.')
331 return 0;
332
333 if (!expr->member)
334 return 0;
335 if (strcmp(expr->member->name, "data") != 0)
336 return 0;
337
338 sym = expr_to_sym(expr->deref);
339 if (!sym)
340 return 0;
341 sym = get_real_base_type(sym);
342 if (!sym || sym->type != SYM_PTR)
343 return 0;
344 sym = get_real_base_type(sym);
345 if (!sym || sym->type != SYM_STRUCT || !sym->ident)
346 return 0;
347 if (strcmp(sym->ident->name, "sk_buff") != 0)
348 return 0;
349
350 return 1;
351 }
352
353 static bool is_points_to_user_data_fn(struct expression *expr)
354 {
355 int i;
356
357 expr = strip_expr(expr);
358 if (expr->type != EXPR_CALL || expr->fn->type != EXPR_SYMBOL ||
359 !expr->fn->symbol)
360 return false;
361 expr = expr->fn;
362 for (i = 0; i < ARRAY_SIZE(returns_pointer_to_user_data); i++) {
363 if (sym_name_is(returns_pointer_to_user_data[i], expr))
364 return true;
365 }
366 return false;
367 }
368
369 static int get_rl_from_function(struct expression *expr, struct range_list **rl)
370 {
371 int i;
372
373 if (expr->type != EXPR_CALL || expr->fn->type != EXPR_SYMBOL ||
374 !expr->fn->symbol_name || !expr->fn->symbol_name->name)
375 return 0;
376
377 for (i = 0; i < ARRAY_SIZE(returns_user_data); i++) {
378 if (strcmp(expr->fn->symbol_name->name, returns_user_data[i]) == 0) {
379 *rl = alloc_whole_rl(get_type(expr));
380 return 1;
381 }
382 }
383 return 0;
384 }
385
386 int points_to_user_data(struct expression *expr)
387 {
388 struct smatch_state *state;
389 struct range_list *rl;
390 char buf[256];
391 struct symbol *sym;
392 char *name;
393 int ret = 0;
394
395 expr = strip_expr(expr);
396 if (!expr)
397 return 0;
398 if (is_skb_data(expr))
399 return 1;
400 if (is_points_to_user_data_fn(expr))
401 return 1;
402 if (get_rl_from_function(expr, &rl))
403 return 1;
404
405 if (expr->type == EXPR_BINOP && expr->op == '+') {
406 if (points_to_user_data(expr->left))
407 return 1;
408 if (points_to_user_data(expr->right))
409 return 1;
410 return 0;
411 }
412
413 name = expr_to_var_sym(expr, &sym);
414 if (!name || !sym)
415 goto free;
416 snprintf(buf, sizeof(buf), "*%s", name);
417 state = get_state(my_id, buf, sym);
418 if (state && estate_rl(state))
419 ret = 1;
420 free:
421 free_string(name);
422 return ret;
423 }
424
425 static void set_points_to_user_data(struct expression *expr)
426 {
427 char *name;
428 struct symbol *sym;
429 char buf[256];
430 struct symbol *type;
431
432 name = expr_to_var_sym(expr, &sym);
433 if (!name || !sym)
434 goto free;
435 snprintf(buf, sizeof(buf), "*%s", name);
436 type = get_type(expr);
437 if (type && type->type == SYM_PTR)
438 type = get_real_base_type(type);
439 if (!type || type->type != SYM_BASETYPE)
440 type = &llong_ctype;
441 set_state(my_id, buf, sym, alloc_estate_whole(type));
442 free:
443 free_string(name);
444 }
445
446 static int comes_from_skb_data(struct expression *expr)
447 {
448 expr = strip_expr(expr);
449 if (!expr || expr->type != EXPR_PREOP || expr->op != '*')
450 return 0;
451
452 expr = strip_expr(expr->unop);
453 if (!expr)
454 return 0;
455 if (expr->type == EXPR_BINOP && expr->op == '+')
456 expr = strip_expr(expr->left);
457
458 return is_skb_data(expr);
459 }
460
461 static int handle_struct_assignment(struct expression *expr)
462 {
463 struct expression *right;
464 struct symbol *left_type, *right_type;
465
466 left_type = get_type(expr->left);
467 if (!left_type || left_type->type != SYM_PTR)
468 return 0;
469 left_type = get_real_base_type(left_type);
470 if (!left_type)
471 return 0;
472 if (left_type->type != SYM_STRUCT &&
473 left_type->type != SYM_UNION)
474 return 0;
475
476 /*
477 * Ignore struct to struct assignments because for those we look at the
478 * individual members.
479 */
480 right = strip_expr(expr->right);
481 right_type = get_type(right);
482 if (!right_type || right_type->type != SYM_PTR)
483 return 0;
484
485 /* If we are assigning struct members then normally that is handled
486 * by fake assignments, however if we cast one struct to a different
487 * of struct then we handle that here.
488 */
489 right_type = get_real_base_type(right_type);
490 if (right_type == left_type)
491 return 0;
492
493 if (!points_to_user_data(right))
494 return 0;
495
496 tag_as_user_data(expr->left);
497 return 1;
498 }
499
500 static int handle_get_user(struct expression *expr)
501 {
502 char *name;
503 int ret = 0;
504
505 name = get_macro_name(expr->pos);
506 if (!name || strcmp(name, "get_user") != 0)
507 return 0;
508
509 name = expr_to_var(expr->right);
510 if (!name || strcmp(name, "__val_gu") != 0)
511 goto free;
512 set_state_expr(my_id, expr->left, alloc_estate_whole(get_type(expr->left)));
513 ret = 1;
514 free:
515 free_string(name);
516 return ret;
517 }
518
519 static void match_assign(struct expression *expr)
520 {
521 struct range_list *rl;
522 static struct expression *handled;
523 struct expression *faked;
524
525 faked = get_faked_expression();
526 if (faked && faked == handled)
527 return;
528 if (is_fake_call(expr->right))
529 goto clear_old_state;
530 if (handle_get_user(expr))
531 return;
532 if (points_to_user_data(expr->right)) {
533 handled = expr;
534 set_points_to_user_data(expr->left);
535 }
536 if (handle_struct_assignment(expr))
537 return;
538
539 if (!get_user_rl(expr->right, &rl))
540 goto clear_old_state;
541
542 rl = cast_rl(get_type(expr->left), rl);
543 set_state_expr(my_id, expr->left, alloc_estate_rl(rl));
544
545 return;
546
547 clear_old_state:
548 if (get_state_expr(my_id, expr->left))
549 set_state_expr(my_id, expr->left, alloc_estate_empty());
550 }
551
552 static void handle_eq_noteq(struct expression *expr)
553 {
554 struct smatch_state *left_orig, *right_orig;
555
556 left_orig = get_state_expr(my_id, expr->left);
557 right_orig = get_state_expr(my_id, expr->right);
558
559 if (!left_orig && !right_orig)
560 return;
561 if (left_orig && right_orig)
562 return;
563
564 if (left_orig) {
565 set_true_false_states_expr(my_id, expr->left,
566 expr->op == SPECIAL_EQUAL ? alloc_estate_empty() : NULL,
567 expr->op == SPECIAL_EQUAL ? NULL : alloc_estate_empty());
568 } else {
569 set_true_false_states_expr(my_id, expr->right,
570 expr->op == SPECIAL_EQUAL ? alloc_estate_empty() : NULL,
571 expr->op == SPECIAL_EQUAL ? NULL : alloc_estate_empty());
572 }
573 }
574
575 static void handle_unsigned_lt_gt(struct expression *expr)
576 {
577 struct symbol *type;
578 struct range_list *left;
579 struct range_list *right;
580 struct range_list *non_negative;
581 sval_t min, minus_one;
582
583 /*
584 * conditions are mostly handled by smatch_extra.c. The special case
585 * here is that say you have if (user_int < unknown_u32) {
586 * In Smatch extra we say that, We have no idea what value
587 * unknown_u32 is so the only thin we can say for sure is that
588 * user_int is not -1 (UINT_MAX). But in check_user_data2.c we should
589 * assume that unless unknown_u32 is user data, it's probably less than
590 * INT_MAX.
591 *
592 */
593
594 type = get_type(expr);
595 if (!type_unsigned(type))
596 return;
597
598 /*
599 * Assume if (user < trusted) { ... because I am lazy and because this
600 * is the correct way to write code.
601 */
602 if (!get_user_rl(expr->left, &left))
603 return;
604 if (get_user_rl(expr->right, &right))
605 return;
606
607 if (!sval_is_negative(rl_min(left)))
608 return;
609 min = rl_min(left);
610 minus_one.type = rl_type(left);
611 minus_one.value = -1;
612 non_negative = remove_range(left, min, minus_one);
613
614 switch (expr->op) {
615 case '<':
616 case SPECIAL_UNSIGNED_LT:
617 case SPECIAL_LTE:
618 case SPECIAL_UNSIGNED_LTE:
619 set_true_false_states_expr(my_id, expr->left,
620 alloc_estate_rl(non_negative), NULL);
621 break;
622 case '>':
623 case SPECIAL_UNSIGNED_GT:
624 case SPECIAL_GTE:
625 case SPECIAL_UNSIGNED_GTE:
626 set_true_false_states_expr(my_id, expr->left,
627 NULL, alloc_estate_rl(non_negative));
628 break;
629 }
630 }
631
632 static void match_condition(struct expression *expr)
633 {
634 if (expr->type != EXPR_COMPARE)
635 return;
636
637 if (expr->op == SPECIAL_EQUAL ||
638 expr->op == SPECIAL_NOTEQUAL) {
639 handle_eq_noteq(expr);
640 return;
641 }
642
643 handle_unsigned_lt_gt(expr);
644 }
645
646 static void match_user_assign_function(const char *fn, struct expression *expr, void *unused)
647 {
648 tag_as_user_data(expr->left);
649 set_points_to_user_data(expr->left);
650 }
651
652 static void match_returns_user_rl(const char *fn, struct expression *expr, void *unused)
653 {
654 func_gets_user_data = true;
655 }
656
657 static int get_user_macro_rl(struct expression *expr, struct range_list **rl)
658 {
659 struct expression *parent;
660 char *macro;
661
662 if (!expr)
663 return 0;
664
665 macro = get_macro_name(expr->pos);
666 if (!macro)
667 return 0;
668
669 /* handle ntohl(foo[i]) where "i" is trusted */
670 parent = expr_get_parent_expr(expr);
671 while (parent && parent->type != EXPR_BINOP)
672 parent = expr_get_parent_expr(parent);
673 if (parent && parent->type == EXPR_BINOP) {
674 char *parent_macro = get_macro_name(parent->pos);
675
676 if (parent_macro && strcmp(macro, parent_macro) == 0)
677 return 0;
678 }
679
680 if (strcmp(macro, "ntohl") == 0) {
681 *rl = alloc_whole_rl(&uint_ctype);
682 return 1;
683 }
684 if (strcmp(macro, "ntohs") == 0) {
685 *rl = alloc_whole_rl(&ushort_ctype);
686 return 1;
687 }
688 return 0;
689 }
690
691 struct db_info {
692 struct range_list *rl;
693 struct expression *call;
694 };
695 static int returned_rl_callback(void *_info, int argc, char **argv, char **azColName)
696 {
697 struct db_info *db_info = _info;
698 struct range_list *rl;
699 char *return_ranges = argv[0];
700 char *user_ranges = argv[1];
701 struct expression *arg;
702 int comparison;
703
704 if (argc != 2)
705 return 0;
706
707 call_results_to_rl(db_info->call, get_type(db_info->call), user_ranges, &rl);
708 if (str_to_comparison_arg(return_ranges, db_info->call, &comparison, &arg) &&
709 comparison == SPECIAL_EQUAL) {
710 struct range_list *orig_rl;
711
712 if (!get_user_rl(arg, &orig_rl))
713 return 0;
714 rl = rl_intersection(rl, orig_rl);
715 if (!rl)
716 return 0;
717 }
718 db_info->rl = rl_union(db_info->rl, rl);
719
720 return 0;
721 }
722
723 static int has_user_data(struct symbol *sym)
724 {
725 struct sm_state *tmp;
726
727 FOR_EACH_MY_SM(my_id, __get_cur_stree(), tmp) {
728 if (tmp->sym == sym)
729 return 1;
730 } END_FOR_EACH_SM(tmp);
731 return 0;
732 }
733
734 static int we_pass_user_data(struct expression *call)
735 {
736 struct expression *arg;
737 struct symbol *sym;
738
739 FOR_EACH_PTR(call->args, arg) {
740 sym = expr_to_sym(arg);
741 if (!sym)
742 continue;
743 if (has_user_data(sym))
744 return 1;
745 } END_FOR_EACH_PTR(arg);
746
747 return 0;
748 }
749
750 static int db_returned_user_rl(struct expression *call, struct range_list **rl)
751 {
752 struct db_info db_info = {};
753
754 /* for function pointers assume everything is used */
755 if (call->fn->type != EXPR_SYMBOL || !call->fn->symbol)
756 return 0;
757 if (is_fake_call(call))
758 return 0;
759
760 db_info.call = call;
761 run_sql(&returned_rl_callback, &db_info,
762 "select return, value from return_states where %s and type = %d and parameter = -1 and key = '$';",
763 get_static_filter(call->fn->symbol), USER_DATA3_SET);
764 if (db_info.rl) {
765 func_gets_user_data = true;
766 *rl = db_info.rl;
767 return 1;
768 }
769
770 run_sql(&returned_rl_callback, &db_info,
771 "select return, value from return_states where %s and type = %d and parameter = -1 and key = '$';",
772 get_static_filter(call->fn->symbol), USER_DATA3);
773 if (db_info.rl) {
774 if (!we_pass_user_data(call))
775 return 0;
776 *rl = db_info.rl;
777 return 1;
778 }
779
780 return 0;
781 }
782
783 struct stree *get_user_stree(void)
784 {
785 return get_all_states_stree(my_id);
786 }
787
788 static int user_data_flag;
789 static int no_user_data_flag;
790 static struct range_list *var_user_rl(struct expression *expr)
791 {
792 struct smatch_state *state;
793 struct range_list *rl;
794 struct range_list *absolute_rl;
795
796 if (expr->type == EXPR_BINOP && expr->op == '%') {
797 struct range_list *left, *right;
798
799 if (!get_user_rl(expr->right, &right))
800 return NULL;
801 get_absolute_rl(expr->left, &left);
802 rl = rl_binop(left, '%', right);
803 goto found;
804 }
805
806 if (!option_spammy && expr->type == EXPR_BINOP && expr->op == '/') {
807 struct range_list *left = NULL;
808 struct range_list *right = NULL;
809 struct range_list *abs_right;
810
811 /*
812 * The specific bug I'm dealing with is:
813 *
814 * foo = capped_user / unknown;
815 *
816 * Instead of just saying foo is now entirely user_rl we should
817 * probably say instead that it is not at all user data.
818 *
819 */
820
821 get_user_rl(expr->left, &left);
822 get_user_rl(expr->right, &right);
823 get_absolute_rl(expr->right, &abs_right);
824
825 if (left && !right) {
826 rl = rl_binop(left, '/', abs_right);
827 if (sval_cmp(rl_max(left), rl_max(rl)) < 0)
828 no_user_data_flag = 1;
829 }
830
831 return NULL;
832 }
833
834 if (get_rl_from_function(expr, &rl))
835 goto found;
836
837 if (get_user_macro_rl(expr, &rl))
838 goto found;
839
840 if (comes_from_skb_data(expr)) {
841 rl = alloc_whole_rl(get_type(expr));
842 goto found;
843 }
844
845 state = get_state_expr(my_id, expr);
846 if (state && estate_rl(state)) {
847 rl = estate_rl(state);
848 goto found;
849 }
850
851 if (expr->type == EXPR_CALL && db_returned_user_rl(expr, &rl))
852 goto found;
853
854 if (is_array(expr)) {
855 struct expression *array = get_array_base(expr);
856
857 if (!get_state_expr(my_id, array)) {
858 no_user_data_flag = 1;
859 return NULL;
860 }
861 }
862
863 if (expr->type == EXPR_PREOP && expr->op == '*' &&
864 is_user_rl(expr->unop)) {
865 rl = var_to_absolute_rl(expr);
866 goto found;
867 }
868
869 return NULL;
870 found:
871 user_data_flag = 1;
872 absolute_rl = var_to_absolute_rl(expr);
873 return clone_rl(rl_intersection(rl, absolute_rl));
874 }
875
876 int get_user_rl(struct expression *expr, struct range_list **rl)
877 {
878 user_data_flag = 0;
879 no_user_data_flag = 0;
880 custom_get_absolute_rl(expr, &var_user_rl, rl);
881 if (!user_data_flag || no_user_data_flag)
882 *rl = NULL;
883
884 return !!*rl;
885 }
886
887 int get_user_rl_spammy(struct expression *expr, struct range_list **rl)
888 {
889 int ret;
890
891 option_spammy++;
892 ret = get_user_rl(expr, rl);
893 option_spammy--;
894
895 return ret;
896 }
897
898 int is_user_rl(struct expression *expr)
899 {
900 struct range_list *tmp;
901
902 return get_user_rl_spammy(expr, &tmp);
903 }
904
905 int get_user_rl_var_sym(const char *name, struct symbol *sym, struct range_list **rl)
906 {
907 struct smatch_state *state;
908
909 state = get_state(my_id, name, sym);
910 if (state && estate_rl(state)) {
911 *rl = estate_rl(state);
912 return 1;
913 }
914 return 0;
915 }
916
917 static void match_call_info(struct expression *expr)
918 {
919 struct range_list *rl;
920 struct expression *arg;
921 struct symbol *type;
922 int i = 0;
923
924 i = -1;
925 FOR_EACH_PTR(expr->args, arg) {
926 i++;
927 type = get_arg_type(expr->fn, i);
928
929 if (!get_user_rl(arg, &rl))
930 continue;
931
932 rl = cast_rl(type, rl);
933 sql_insert_caller_info(expr, USER_DATA3, i, "$", show_rl(rl));
934 } END_FOR_EACH_PTR(arg);
935 }
936
937 static int is_struct_ptr(struct symbol *sym)
938 {
939 struct symbol *type;
940
941 if (!sym)
942 return 0;
943 type = get_real_base_type(sym);
944 if (!type || type->type != SYM_PTR)
945 return 0;
946 type = get_real_base_type(type);
947 if (!type || type->type != SYM_STRUCT)
948 return 0;
949 return 1;
950 }
951
952 static void struct_member_callback(struct expression *call, int param, char *printed_name, struct sm_state *sm)
953 {
954 struct smatch_state *state;
955 struct range_list *rl;
956 struct symbol *type;
957
958 /*
959 * Smatch uses a hack where if we get an unsigned long we say it's
960 * both user data and it points to user data. But if we pass it to a
961 * function which takes an int, then it's just user data. There's not
962 * enough bytes for it to be a pointer.
963 *
964 */
965 type = get_arg_type(call->fn, param);
966 if (type && type_bits(type) < type_bits(&ptr_ctype))
967 return;
968
969 if (strcmp(sm->state->name, "") == 0)
970 return;
971
972 if (strcmp(printed_name, "*$") == 0 &&
973 is_struct_ptr(sm->sym))
974 return;
975
976 state = get_state(SMATCH_EXTRA, sm->name, sm->sym);
977 if (!state || !estate_rl(state))
978 rl = estate_rl(sm->state);
979 else
980 rl = rl_intersection(estate_rl(sm->state), estate_rl(state));
981
982 sql_insert_caller_info(call, USER_DATA3, param, printed_name, show_rl(rl));
983 }
984
985 static void set_param_user_data(const char *name, struct symbol *sym, char *key, char *value)
986 {
987 struct range_list *rl = NULL;
988 struct smatch_state *state;
989 struct symbol *type;
990 char fullname[256];
991
992 if (strcmp(key, "*$") == 0)
993 snprintf(fullname, sizeof(fullname), "*%s", name);
994 else if (strncmp(key, "$", 1) == 0)
995 snprintf(fullname, 256, "%s%s", name, key + 1);
996 else
997 return;
998
999 type = get_member_type_from_key(symbol_expression(sym), key);
1000
1001 /* if the caller passes a void pointer with user data */
1002 if (strcmp(key, "*$") == 0 && type && type != &void_ctype) {
1003 struct expression *expr = symbol_expression(sym);
1004
1005 tag_as_user_data(expr);
1006 set_points_to_user_data(expr);
1007 return;
1008 }
1009 str_to_rl(type, value, &rl);
1010 state = alloc_estate_rl(rl);
1011 set_state(my_id, fullname, sym, state);
1012 }
1013
1014 static void set_called(const char *name, struct symbol *sym, char *key, char *value)
1015 {
1016 set_state(my_call_id, "this_function", NULL, &called);
1017 }
1018
1019 static void match_syscall_definition(struct symbol *sym)
1020 {
1021 struct symbol *arg;
1022 char *macro;
1023 char *name;
1024 int is_syscall = 0;
1025
1026 macro = get_macro_name(sym->pos);
1027 if (macro &&
1028 (strncmp("SYSCALL_DEFINE", macro, strlen("SYSCALL_DEFINE")) == 0 ||
1029 strncmp("COMPAT_SYSCALL_DEFINE", macro, strlen("COMPAT_SYSCALL_DEFINE")) == 0))
1030 is_syscall = 1;
1031
1032 name = get_function();
1033 if (!option_no_db && get_state(my_call_id, "this_function", NULL) != &called) {
1034 if (name && strncmp(name, "sys_", 4) == 0)
1035 is_syscall = 1;
1036 }
1037
1038 if (name && strncmp(name, "compat_sys_", 11) == 0)
1039 is_syscall = 1;
1040
1041 if (!is_syscall)
1042 return;
1043
1044 FOR_EACH_PTR(sym->ctype.base_type->arguments, arg) {
1045 set_state(my_id, arg->ident->name, arg, alloc_estate_whole(get_real_base_type(arg)));
1046 } END_FOR_EACH_PTR(arg);
1047 }
1048
1049 static void set_to_user_data(struct expression *expr, char *key, char *value)
1050 {
1051 char *name;
1052 struct symbol *sym;
1053 struct symbol *type;
1054 struct range_list *rl = NULL;
1055
1056 type = get_member_type_from_key(expr, key);
1057 name = get_variable_from_key(expr, key, &sym);
1058 if (!name || !sym)
1059 goto free;
1060
1061 call_results_to_rl(expr, type, value, &rl);
1062
1063 set_state(my_id, name, sym, alloc_estate_rl(rl));
1064 free:
1065 free_string(name);
1066
1067 }
1068
1069 static void returns_param_user_data(struct expression *expr, int param, char *key, char *value)
1070 {
1071 struct expression *arg;
1072 struct expression *call;
1073
1074 call = expr;
1075 while (call->type == EXPR_ASSIGNMENT)
1076 call = strip_expr(call->right);
1077 if (call->type != EXPR_CALL)
1078 return;
1079
1080 if (!we_pass_user_data(call))
1081 return;
1082
1083 if (param == -1) {
1084 if (expr->type != EXPR_ASSIGNMENT)
1085 return;
1086 set_to_user_data(expr->left, key, value);
1087 return;
1088 }
1089
1090 arg = get_argument_from_call_expr(call->args, param);
1091 if (!arg)
1092 return;
1093 set_to_user_data(arg, key, value);
1094 }
1095
1096 static void returns_param_user_data_set(struct expression *expr, int param, char *key, char *value)
1097 {
1098 struct expression *arg;
1099
1100 func_gets_user_data = true;
1101
1102 if (param == -1) {
1103 if (expr->type != EXPR_ASSIGNMENT)
1104 return;
1105 if (strcmp(key, "*$") == 0) {
1106 set_points_to_user_data(expr->left);
1107 tag_as_user_data(expr->left);
1108 } else {
1109 set_to_user_data(expr->left, key, value);
1110 }
1111 return;
1112 }
1113
1114 while (expr->type == EXPR_ASSIGNMENT)
1115 expr = strip_expr(expr->right);
1116 if (expr->type != EXPR_CALL)
1117 return;
1118
1119 arg = get_argument_from_call_expr(expr->args, param);
1120 if (!arg)
1121 return;
1122 set_to_user_data(arg, key, value);
1123 }
1124
1125 static int has_empty_state(struct sm_state *sm)
1126 {
1127 struct sm_state *tmp;
1128
1129 FOR_EACH_PTR(sm->possible, tmp) {
1130 if (!estate_rl(tmp->state))
1131 return 1;
1132 } END_FOR_EACH_PTR(tmp);
1133
1134 return 0;
1135 }
1136
1137 static void param_set_to_user_data(int return_id, char *return_ranges, struct expression *expr)
1138 {
1139 struct sm_state *sm;
1140 struct smatch_state *start_state;
1141 struct range_list *rl;
1142 int param;
1143 char *return_str;
1144 const char *param_name;
1145 struct symbol *ret_sym;
1146 bool return_found = false;
1147
1148 expr = strip_expr(expr);
1149 return_str = expr_to_str(expr);
1150 ret_sym = expr_to_sym(expr);
1151
1152 FOR_EACH_MY_SM(my_id, __get_cur_stree(), sm) {
1153 if (has_empty_state(sm))
1154 continue;
1155
1156 param = get_param_num_from_sym(sm->sym);
1157 if (param < 0)
1158 continue;
1159
1160 /* The logic here was that if we were passed in a user data then
1161 * we don't record that. It's like the difference between
1162 * param_filter and param_set. When I think about it, I'm not
1163 * sure it actually works. It's probably harmless because we
1164 * checked earlier that we're not returning a parameter...
1165 * Let's mark this as a TODO.
1166 */
1167 start_state = get_state_stree(start_states, my_id, sm->name, sm->sym);
1168 if (start_state && rl_equiv(estate_rl(sm->state), estate_rl(start_state)))
1169 continue;
1170
1171 param_name = get_param_name(sm);
1172 if (!param_name)
1173 continue;
1174 if (strcmp(param_name, "$") == 0) /* The -1 param is handled after the loop */
1175 continue;
1176
1177 sql_insert_return_states(return_id, return_ranges,
1178 func_gets_user_data ? USER_DATA3_SET : USER_DATA3,
1179 param, param_name, show_rl(estate_rl(sm->state)));
1180 } END_FOR_EACH_SM(sm);
1181
1182 if (points_to_user_data(expr)) {
1183 sql_insert_return_states(return_id, return_ranges,
1184 (is_skb_data(expr) || !func_gets_user_data) ?
1185 USER_DATA3_SET : USER_DATA3,
1186 -1, "*$", "");
1187 goto free_string;
1188 }
1189
1190
1191 FOR_EACH_MY_SM(my_id, __get_cur_stree(), sm) {
1192 if (!ret_sym)
1193 break;
1194 if (ret_sym != sm->sym)
1195 continue;
1196
1197 param_name = state_name_to_param_name(sm->name, return_str);
1198 if (!param_name)
1199 continue;
1200 if (strcmp(param_name, "$") == 0)
1201 return_found = true;
1202 sql_insert_return_states(return_id, return_ranges,
1203 func_gets_user_data ? USER_DATA3_SET : USER_DATA3,
1204 -1, param_name, show_rl(estate_rl(sm->state)));
1205 } END_FOR_EACH_SM(sm);
1206
1207
1208 if (!return_found && get_user_rl(expr, &rl)) {
1209 sql_insert_return_states(return_id, return_ranges,
1210 func_gets_user_data ? USER_DATA3_SET : USER_DATA3,
1211 -1, "$", show_rl(rl));
1212 goto free_string;
1213 }
1214
1215 free_string:
1216 free_string(return_str);
1217 }
1218
1219 static struct int_stack *gets_data_stack;
1220 static void match_function_def(struct symbol *sym)
1221 {
1222 func_gets_user_data = false;
1223 }
1224
1225 static void match_inline_start(struct expression *expr)
1226 {
1227 push_int(&gets_data_stack, func_gets_user_data);
1228 }
1229
1230 static void match_inline_end(struct expression *expr)
1231 {
1232 func_gets_user_data = pop_int(&gets_data_stack);
1233 }
1234
1235 void register_kernel_user_data2(int id)
1236 {
1237 int i;
1238
1239 my_id = id;
1240
1241 if (option_project != PROJ_KERNEL)
1242 return;
1243
1244 set_dynamic_states(my_id);
1245
1246 add_hook(&match_function_def, FUNC_DEF_HOOK);
1247 add_hook(&match_inline_start, INLINE_FN_START);
1248 add_hook(&match_inline_end, INLINE_FN_END);
1249
1250 add_hook(&save_start_states, AFTER_DEF_HOOK);
1251 add_hook(&free_start_states, AFTER_FUNC_HOOK);
1252 add_hook(&match_save_states, INLINE_FN_START);
1253 add_hook(&match_restore_states, INLINE_FN_END);
1254
1255 add_unmatched_state_hook(my_id, &empty_state);
1256 add_extra_nomod_hook(&extra_nomod_hook);
1257 add_pre_merge_hook(my_id, &pre_merge_hook);
1258 add_merge_hook(my_id, &merge_estates);
1259
1260 add_function_hook("copy_from_user", &match_user_copy, INT_PTR(0));
1261 add_function_hook("__copy_from_user", &match_user_copy, INT_PTR(0));
1262 add_function_hook("memcpy_fromiovec", &match_user_copy, INT_PTR(0));
1263 for (i = 0; i < ARRAY_SIZE(kstr_funcs); i++)
1264 add_function_hook(kstr_funcs[i], &match_user_copy, INT_PTR(2));
1265 add_function_hook("usb_control_msg", &match_user_copy, INT_PTR(6));
1266
1267 for (i = 0; i < ARRAY_SIZE(returns_user_data); i++) {
1268 add_function_assign_hook(returns_user_data[i], &match_user_assign_function, NULL);
1269 add_function_hook(returns_user_data[i], &match_returns_user_rl, NULL);
1270 }
1271
1272 add_function_hook("sscanf", &match_sscanf, NULL);
1273
1274 add_hook(&match_syscall_definition, AFTER_DEF_HOOK);
1275
1276 add_hook(&match_assign, ASSIGNMENT_HOOK);
1277 add_hook(&match_condition, CONDITION_HOOK);
1278
1279 add_hook(&match_call_info, FUNCTION_CALL_HOOK);
1280 add_member_info_callback(my_id, struct_member_callback);
1281 select_caller_info_hook(set_param_user_data, USER_DATA3);
1282 select_return_states_hook(USER_DATA3, &returns_param_user_data);
1283 select_return_states_hook(USER_DATA3_SET, &returns_param_user_data_set);
1284 add_split_return_callback(&param_set_to_user_data);
1285 }
1286
1287 void register_kernel_user_data3(int id)
1288 {
1289 my_call_id = id;
1290
1291 if (option_project != PROJ_KERNEL)
1292 return;
1293 select_caller_info_hook(set_called, INTERNAL);
1294 }
1295
Static analysis for C