smatch_kernel_user_data.c

   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 unsigned long 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 struct stree *start_states;
  52 static void save_start_states(struct statement *stmt)
  53 {
  54         start_states = clone_stree(__get_cur_stree());
  55 }
  56
  57 static void free_start_states(void)
  58 {
  59         free_stree(&start_states);
  60 }
  61
  62 static struct smatch_state *empty_state(struct sm_state *sm)
  63 {
  64         return alloc_estate_empty();
  65 }
  66
  67 static struct smatch_state *new_state(struct symbol *type)
  68 {
  69         struct smatch_state *state;
  70
  71         if (!type || type_is_ptr(type))
  72                 return NULL;
  73
  74         state = alloc_estate_whole(type);
  75         estate_set_new(state);
  76         return state;
  77 }
  78
  79 static void pre_merge_hook(struct sm_state *cur, struct sm_state *other)
  80 {
  81         struct smatch_state *user = cur->state;
  82         struct smatch_state *extra;
  83         struct smatch_state *state;
  84         struct range_list *rl;
  85
  86         extra = __get_state(SMATCH_EXTRA, cur->name, cur->sym);
  87         if (!extra)
  88                 return;
  89         rl = rl_intersection(estate_rl(user), estate_rl(extra));
  90         state = alloc_estate_rl(clone_rl(rl));
  91         if (estate_capped(user) || is_capped_var_sym(cur->name, cur->sym))
  92                 estate_set_capped(state);
  93         if (estate_treat_untagged(user))
  94                 estate_set_treat_untagged(state);
  95         if (estates_equiv(state, cur->state))
  96                 return;
  97         set_state(my_id, cur->name, cur->sym, state);
  98 }
  99
 100 static void extra_nomod_hook(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state)
 101 {
 102         struct smatch_state *user, *new;
 103         struct range_list *rl;
 104
 105         user = __get_state(my_id, name, sym);
 106         if (!user)
 107                 return;
 108         rl = rl_intersection(estate_rl(user), estate_rl(state));
 109         if (rl_equiv(rl, estate_rl(user)))
 110                 return;
 111         new = alloc_estate_rl(rl);
 112         if (estate_capped(user))
 113                 estate_set_capped(new);
 114         if (estate_treat_untagged(user))
 115                 estate_set_treat_untagged(new);
 116         set_state(my_id, name, sym, new);
 117 }
 118
 119 static bool user_rl_known(struct expression *expr)
 120 {
 121         struct range_list *rl;
 122         sval_t close_to_max;
 123
 124         if (!get_user_rl(expr, &rl))
 125                 return true;
 126
 127         close_to_max = sval_type_max(rl_type(rl));
 128         close_to_max.value -= 100;
 129
 130         if (sval_cmp(rl_max(rl), close_to_max) >= 0)
 131                 return false;
 132         return true;
 133 }
 134
 135 static bool is_array_index_mask_nospec(struct expression *expr)
 136 {
 137         struct expression *orig;
 138
 139         orig = get_assigned_expr(expr);
 140         if (!orig || orig->type != EXPR_CALL)
 141                 return false;
 142         return sym_name_is("array_index_mask_nospec", orig->fn);
 143 }
 144
 145 static bool binop_capped(struct expression *expr)
 146 {
 147         struct range_list *left_rl;
 148         int comparison;
 149         sval_t sval;
 150
 151         if (expr->op == '-' && get_user_rl(expr->left, &left_rl)) {
 152                 if (user_rl_capped(expr->left))
 153                         return true;
 154                 comparison = get_comparison(expr->left, expr->right);
 155                 if (comparison && show_special(comparison)[0] == '>')
 156                         return true;
 157                 return false;
 158         }
 159
 160         if (expr->op == '&' || expr->op == '%') {
 161                 bool left_user, left_capped, right_user, right_capped;
 162
 163                 if (!get_value(expr->right, &sval) && is_capped(expr->right))
 164                         return true;
 165                 if (is_array_index_mask_nospec(expr->right))
 166                         return true;
 167                 if (is_capped(expr->left))
 168                         return true;
 169                 left_user = is_user_rl(expr->left);
 170                 right_user = is_user_rl(expr->right);
 171                 if (!left_user && !right_user)
 172                         return true;
 173
 174                 left_capped = user_rl_capped(expr->left);
 175                 right_capped = user_rl_capped(expr->right);
 176
 177                 if (left_user && left_capped) {
 178                         if (!right_user)
 179                                 return true;
 180                         if (right_user && right_capped)
 181                                 return true;
 182                         return false;
 183                 }
 184                 if (right_user && right_capped) {
 185                         if (!left_user)
 186                                 return true;
 187                         return false;
 188                 }
 189                 return false;
 190         }
 191
 192         /*
 193          * Generally "capped" means that we capped it to an unknown value.
 194          * This is useful because if Smatch doesn't know what the value is then
 195          * we have to trust that it is correct.  But if we known cap value is
 196          * 100 then we can check if 100 is correct and complain if it's wrong.
 197          *
 198          * So then the problem is with BINOP when we take a capped variable
 199          * plus a user variable which is clamped to a known range (uncapped)
 200          * the result should be capped.
 201          */
 202         if ((user_rl_capped(expr->left) || user_rl_known(expr->left)) &&
 203             (user_rl_capped(expr->right) || user_rl_known(expr->right)))
 204                 return true;
 205
 206         return false;
 207 }
 208
 209 bool user_rl_capped(struct expression *expr)
 210 {
 211         struct smatch_state *state;
 212         struct range_list *rl;
 213         sval_t sval;
 214
 215         expr = strip_expr(expr);
 216         if (!expr)
 217                 return false;
 218         if (get_value(expr, &sval))
 219                 return true;
 220         if (expr->type == EXPR_BINOP)
 221                 return binop_capped(expr);
 222         if ((expr->type == EXPR_PREOP || expr->type == EXPR_POSTOP) &&
 223             (expr->op == SPECIAL_INCREMENT || expr->op == SPECIAL_DECREMENT))
 224                 return user_rl_capped(expr->unop);
 225         state = get_state_expr(my_id, expr);
 226         if (state)
 227                 return estate_capped(state);
 228
 229         if (!get_user_rl(expr, &rl)) {
 230                 /*
 231                  * The non user data parts of a binop are capped and
 232                  * also empty user rl states are capped.
 233                  */
 234                 return true;
 235         }
 236
 237         if (rl_to_sval(rl, &sval))
 238                 return true;
 239
 240         return false;  /* uncapped user data */
 241 }
 242
 243 bool user_rl_treat_untagged(struct expression *expr)
 244 {
 245         struct smatch_state *state;
 246         struct range_list *rl;
 247         sval_t sval;
 248
 249         expr = strip_expr(expr);
 250         if (!expr)
 251                 return false;
 252         if (get_value(expr, &sval))
 253                 return true;
 254
 255         state = get_state_expr(my_id, expr);
 256         if (state)
 257                 return estate_treat_untagged(state);
 258
 259         if (get_user_rl(expr, &rl))
 260                 return false;  /* uncapped user data */
 261
 262         return true;  /* not actually user data */
 263 }
 264
 265 static void tag_inner_struct_members(struct expression *expr, struct symbol *member)
 266 {
 267         struct expression *edge_member;
 268         struct symbol *base = get_real_base_type(member);
 269         struct symbol *tmp;
 270
 271         if (member->ident)
 272                 expr = member_expression(expr, '.', member->ident);
 273
 274         FOR_EACH_PTR(base->symbol_list, tmp) {
 275                 struct symbol *type;
 276
 277                 type = get_real_base_type(tmp);
 278                 if (!type)
 279                         continue;
 280
 281                 if (type->type == SYM_UNION || type->type == SYM_STRUCT) {
 282                         tag_inner_struct_members(expr, tmp);
 283                         continue;
 284                 }
 285
 286                 if (!tmp->ident)
 287                         continue;
 288
 289                 edge_member = member_expression(expr, '.', tmp->ident);
 290                 set_state_expr(my_id, edge_member, new_state(type));
 291         } END_FOR_EACH_PTR(tmp);
 292 }
 293
 294 void __set_user_string(struct expression *expr);
 295 static void tag_struct_members(struct symbol *type, struct expression *expr)
 296 {
 297         struct symbol *tmp;
 298         struct expression *member;
 299         int op = '*';
 300
 301         if (expr->type == EXPR_PREOP && expr->op == '&') {
 302                 expr = strip_expr(expr->unop);
 303                 op = '.';
 304         }
 305
 306         FOR_EACH_PTR(type->symbol_list, tmp) {
 307                 type = get_real_base_type(tmp);
 308                 if (!type)
 309                         continue;
 310
 311                 if (type->type == SYM_UNION || type->type == SYM_STRUCT) {
 312                         tag_inner_struct_members(expr, tmp);
 313                         continue;
 314                 }
 315
 316                 if (!tmp->ident)
 317                         continue;
 318
 319                 member = member_expression(expr, op, tmp->ident);
 320                 if (type->type == SYM_ARRAY) {
 321                         set_points_to_user_data(member);
 322                 } else {
 323                         set_state_expr(my_id, member, new_state(get_type(member)));
 324                 }
 325         } END_FOR_EACH_PTR(tmp);
 326 }
 327
 328 static void tag_base_type(struct expression *expr)
 329 {
 330         if (expr->type == EXPR_PREOP && expr->op == '&')
 331                 expr = strip_expr(expr->unop);
 332         else
 333                 expr = deref_expression(expr);
 334         set_state_expr(my_id, expr, new_state(get_type(expr)));
 335 }
 336
 337 static void tag_as_user_data(struct expression *expr)
 338 {
 339         struct symbol *type;
 340
 341         expr = strip_expr(expr);
 342
 343         type = get_type(expr);
 344         if (!type || type->type != SYM_PTR)
 345                 return;
 346         type = get_real_base_type(type);
 347         if (!type)
 348                 return;
 349         if (type == &void_ctype) {
 350                 set_state_expr(my_id, deref_expression(expr), new_state(&ulong_ctype));
 351                 return;
 352         }
 353         if (type->type == SYM_BASETYPE) {
 354                 if (expr->type != EXPR_PREOP && expr->op != '&')
 355                         set_points_to_user_data(expr);
 356                 tag_base_type(expr);
 357                 return;
 358         }
 359         if (type->type == SYM_STRUCT || type->type == SYM_UNION) {
 360                 if (expr->type != EXPR_PREOP || expr->op != '&')
 361                         expr = deref_expression(expr);
 362                 else
 363                         set_state_expr(my_id, deref_expression(expr), new_state(&ulong_ctype));
 364                 tag_struct_members(type, expr);
 365         }
 366 }
 367
 368 static void match_user_copy(const char *fn, struct expression *expr, void *_param)
 369 {
 370         int param = PTR_INT(_param);
 371         struct expression *dest;
 372
 373         func_gets_user_data = true;
 374
 375         dest = get_argument_from_call_expr(expr->args, param);
 376         dest = strip_expr(dest);
 377         if (!dest)
 378                 return;
 379         tag_as_user_data(dest);
 380 }
 381
 382 static int is_dev_attr_name(struct expression *expr)
 383 {
 384         char *name;
 385         int ret = 0;
 386
 387         name = expr_to_str(expr);
 388         if (!name)
 389                 return 0;
 390         if (strstr(name, "->attr.name"))
 391                 ret = 1;
 392         free_string(name);
 393         return ret;
 394 }
 395
 396 static int ends_in_n(struct expression *expr)
 397 {
 398         struct string *str;
 399
 400         if (!expr)
 401                 return 0;
 402         if (expr->type != EXPR_STRING || !expr->string)
 403                 return 0;
 404
 405         str = expr->string;
 406         if (str->length < 3)
 407                 return 0;
 408
 409         if (str->data[str->length - 3] == '%' &&
 410             str->data[str->length - 2] == 'n')
 411                 return 1;
 412         return 0;
 413 }
 414
 415 static void match_sscanf(const char *fn, struct expression *expr, void *unused)
 416 {
 417         struct expression *str, *format, *arg;
 418         int i, last;
 419
 420         func_gets_user_data = true;
 421
 422         str = get_argument_from_call_expr(expr->args, 0);
 423         if (is_dev_attr_name(str))
 424                 return;
 425
 426         format = get_argument_from_call_expr(expr->args, 1);
 427         if (is_dev_attr_name(format))
 428                 return;
 429
 430         last = ptr_list_size((struct ptr_list *)expr->args) - 1;
 431
 432         i = -1;
 433         FOR_EACH_PTR(expr->args, arg) {
 434                 i++;
 435                 if (i < 2)
 436                         continue;
 437                 if (i == last && ends_in_n(format))
 438                         continue;
 439                 tag_as_user_data(arg);
 440         } END_FOR_EACH_PTR(arg);
 441 }
 442
 443 static int get_rl_from_function(struct expression *expr, struct range_list **rl)
 444 {
 445         int i;
 446
 447         if (expr->type != EXPR_CALL || expr->fn->type != EXPR_SYMBOL ||
 448             !expr->fn->symbol_name || !expr->fn->symbol_name->name)
 449                 return 0;
 450
 451         for (i = 0; i < ARRAY_SIZE(returns_user_data); i++) {
 452                 if (strcmp(expr->fn->symbol_name->name, returns_user_data[i]) == 0) {
 453                         *rl = alloc_whole_rl(get_type(expr));
 454                         return 1;
 455                 }
 456         }
 457         return 0;
 458 }
 459
 460 static int comes_from_skb_data(struct expression *expr)
 461 {
 462         expr = strip_expr(expr);
 463         if (!expr || expr->type != EXPR_PREOP || expr->op != '*')
 464                 return 0;
 465
 466         expr = strip_expr(expr->unop);
 467         if (!expr)
 468                 return 0;
 469         if (expr->type == EXPR_BINOP && expr->op == '+')
 470                 expr = strip_expr(expr->left);
 471
 472         return is_skb_data(expr);
 473 }
 474
 475 static int handle_get_user(struct expression *expr)
 476 {
 477         char *name;
 478         int ret = 0;
 479
 480         name = get_macro_name(expr->pos);
 481         if (!name || strcmp(name, "get_user") != 0)
 482                 return 0;
 483
 484         name = expr_to_var(expr->right);
 485         if (!name || (strcmp(name, "__val_gu") != 0 && strcmp(name, "__gu_val") != 0))
 486                 goto free;
 487         set_state_expr(my_id, expr->left, new_state(get_type(expr->left)));
 488         ret = 1;
 489 free:
 490         free_string(name);
 491         return ret;
 492 }
 493
 494 static bool state_is_new(struct expression *expr)
 495 {
 496         struct smatch_state *state;
 497
 498         state = get_state_expr(my_id, expr);
 499         if (estate_new(state))
 500                 return true;
 501
 502         if (expr->type == EXPR_BINOP) {
 503                 if (state_is_new(expr->left))
 504                         return true;
 505                 if (state_is_new(expr->right))
 506                         return true;
 507         }
 508         return false;
 509 }
 510
 511 static bool handle_op_assign(struct expression *expr)
 512 {
 513         struct expression *binop_expr;
 514         struct smatch_state *state;
 515         struct range_list *rl;
 516
 517         switch (expr->op) {
 518         case SPECIAL_ADD_ASSIGN:
 519         case SPECIAL_SUB_ASSIGN:
 520         case SPECIAL_AND_ASSIGN:
 521         case SPECIAL_MOD_ASSIGN:
 522         case SPECIAL_SHL_ASSIGN:
 523         case SPECIAL_SHR_ASSIGN:
 524         case SPECIAL_OR_ASSIGN:
 525         case SPECIAL_XOR_ASSIGN:
 526         case SPECIAL_MUL_ASSIGN:
 527         case SPECIAL_DIV_ASSIGN:
 528                 binop_expr = binop_expression(expr->left,
 529                                               op_remove_assign(expr->op),
 530                                               expr->right);
 531                 if (!get_user_rl(binop_expr, &rl))
 532                         return true;
 533
 534                 rl = cast_rl(get_type(expr->left), rl);
 535                 state = alloc_estate_rl(rl);
 536                 if (user_rl_capped(binop_expr))
 537                         estate_set_capped(state);
 538                 if (user_rl_treat_untagged(expr->left))
 539                         estate_set_treat_untagged(state);
 540                 if (state_is_new(binop_expr))
 541                         estate_set_new(state);
 542                 set_state_expr(my_id, expr->left, state);
 543                 return true;
 544         }
 545         return false;
 546 }
 547
 548 static void match_assign(struct expression *expr)
 549 {
 550         struct symbol *left_type, *right_type;
 551         struct range_list *rl;
 552         static struct expression *handled;
 553         struct smatch_state *state;
 554         struct expression *faked;
 555         bool is_capped = false;
 556         bool is_new = false;
 557
 558         left_type = get_type(expr->left);
 559         if (left_type == &void_ctype)
 560                 return;
 561
 562         faked = get_faked_expression();
 563
 564         /* FIXME: handle fake array assignments frob(&user_array[x]); */
 565
 566         if (is_fake_call(expr->right) && faked &&
 567             faked->type == EXPR_ASSIGNMENT &&
 568             points_to_user_data(faked->right)) {
 569                 if (is_skb_data(faked->right))
 570                         func_gets_user_data = true;
 571                 rl = alloc_whole_rl(get_type(expr->left));
 572                 is_new = true;
 573                 goto set;
 574         }
 575
 576         if (faked && faked == handled)
 577                 return;
 578         if (is_fake_call(expr->right))
 579                 goto clear_old_state;
 580         if (handle_get_user(expr))
 581                 return;
 582         if (points_to_user_data(expr->right) &&
 583             is_struct_ptr(get_type(expr->left))) {
 584                 handled = expr;
 585                 // This should be handled by smatch_points_to_user_data.c
 586                 // set_points_to_user_data(expr->left);
 587         }
 588
 589         if (handle_op_assign(expr))
 590                 return;
 591         if (expr->op != '=')
 592                 goto clear_old_state;
 593
 594         /* Handled by DB code */
 595         if (expr->right->type == EXPR_CALL || __in_fake_parameter_assign)
 596                 return;
 597
 598         if (!get_user_rl(expr->right, &rl))
 599                 goto clear_old_state;
 600         is_capped = user_rl_capped(expr->right);
 601         is_new = state_is_new(expr->right);
 602
 603 set:
 604         if (type_is_ptr(left_type)) {
 605                 right_type = get_type(expr->right);
 606                 if (right_type && right_type->type == SYM_ARRAY)
 607                         set_points_to_user_data(expr->left);
 608                 return;
 609         }
 610
 611         rl = cast_rl(left_type, rl);
 612         state = alloc_estate_rl(rl);
 613         if (is_new)
 614                 estate_set_new(state);
 615         if (is_capped)
 616                 estate_set_capped(state);
 617         if (user_rl_treat_untagged(expr->right))
 618                 estate_set_treat_untagged(state);
 619
 620         set_state_expr(my_id, expr->left, state);
 621
 622         return;
 623
 624 clear_old_state:
 625
 626         /*
 627          * HACK ALERT!!!  This should be at the start of the function.  The
 628          * the problem is that handling "pointer = array;" assignments is
 629          * handled in this function instead of in kernel_points_to_user_data.c.
 630          */
 631         if (type_is_ptr(left_type))
 632                 return;
 633
 634         if (get_state_expr(my_id, expr->left))
 635                 set_state_expr(my_id, expr->left, alloc_estate_empty());
 636 }
 637
 638 static void handle_eq_noteq(struct expression *expr)
 639 {
 640         struct smatch_state *left_orig, *right_orig;
 641
 642         left_orig = get_state_expr(my_id, expr->left);
 643         right_orig = get_state_expr(my_id, expr->right);
 644
 645         if (!left_orig && !right_orig)
 646                 return;
 647         if (left_orig && right_orig)
 648                 return;
 649
 650         if (left_orig) {
 651                 set_true_false_states_expr(my_id, expr->left,
 652                                 expr->op == SPECIAL_EQUAL ? alloc_estate_empty() : NULL,
 653                                 expr->op == SPECIAL_EQUAL ? NULL : alloc_estate_empty());
 654         } else {
 655                 set_true_false_states_expr(my_id, expr->right,
 656                                 expr->op == SPECIAL_EQUAL ? alloc_estate_empty() : NULL,
 657                                 expr->op == SPECIAL_EQUAL ? NULL : alloc_estate_empty());
 658         }
 659 }
 660
 661 static struct range_list *strip_negatives(struct range_list *rl)
 662 {
 663         sval_t min = rl_min(rl);
 664         sval_t minus_one = { .type = rl_type(rl), .value = -1 };
 665         sval_t over = { .type = rl_type(rl), .value = INT_MAX + 1ULL };
 666         sval_t max = sval_type_max(rl_type(rl));
 667
 668         if (!rl)
 669                 return NULL;
 670
 671         if (type_unsigned(rl_type(rl)) && type_bits(rl_type(rl)) > 31)
 672                 return remove_range(rl, over, max);
 673
 674         return remove_range(rl, min, minus_one);
 675 }
 676
 677 static void handle_compare(struct expression *expr)
 678 {
 679         struct expression  *left, *right;
 680         struct range_list *left_rl = NULL;
 681         struct range_list *right_rl = NULL;
 682         struct range_list *user_rl;
 683         struct smatch_state *capped_state;
 684         struct smatch_state *left_true = NULL;
 685         struct smatch_state *left_false = NULL;
 686         struct smatch_state *right_true = NULL;
 687         struct smatch_state *right_false = NULL;
 688         struct symbol *type;
 689         sval_t sval;
 690
 691         left = strip_expr(expr->left);
 692         right = strip_expr(expr->right);
 693
 694         while (left->type == EXPR_ASSIGNMENT)
 695                 left = strip_expr(left->left);
 696
 697         /*
 698          * Conditions are mostly handled by smatch_extra.c, but there are some
 699          * times where the exact values are not known so we can't do that.
 700          *
 701          * Normally, we might consider using smatch_capped.c to supliment smatch
 702          * extra but that doesn't work when we merge unknown uncapped kernel
 703          * data with unknown capped user data.  The result is uncapped user
 704          * data.  We need to keep it separate and say that the user data is
 705          * capped.  In the past, I would have marked this as just regular
 706          * kernel data (not user data) but we can't do that these days because
 707          * we need to track user data for Spectre.
 708          *
 709          * The other situation which we have to handle is when we do have an
 710          * int and we compare against an unknown unsigned kernel variable.  In
 711          * that situation we assume that the kernel data is less than INT_MAX.
 712          * Otherwise then we get all sorts of array underflow false positives.
 713          *
 714          */
 715
 716         /* Handled in smatch_extra.c */
 717         if (get_implied_value(left, &sval) ||
 718             get_implied_value(right, &sval))
 719                 return;
 720
 721         get_user_rl(left, &left_rl);
 722         get_user_rl(right, &right_rl);
 723
 724         /* nothing to do */
 725         if (!left_rl && !right_rl)
 726                 return;
 727         /* if both sides are user data that's not a good limit */
 728         if (left_rl && right_rl)
 729                 return;
 730
 731         if (left_rl)
 732                 user_rl = left_rl;
 733         else
 734                 user_rl = right_rl;
 735
 736         type = get_type(expr);
 737         if (type_unsigned(type))
 738                 user_rl = strip_negatives(user_rl);
 739         capped_state = alloc_estate_rl(user_rl);
 740         estate_set_capped(capped_state);
 741
 742         switch (expr->op) {
 743         case '<':
 744         case SPECIAL_UNSIGNED_LT:
 745         case SPECIAL_LTE:
 746         case SPECIAL_UNSIGNED_LTE:
 747                 if (left_rl)
 748                         left_true = capped_state;
 749                 else
 750                         right_false = capped_state;
 751                 break;
 752         case '>':
 753         case SPECIAL_UNSIGNED_GT:
 754         case SPECIAL_GTE:
 755         case SPECIAL_UNSIGNED_GTE:
 756                 if (left_rl)
 757                         left_false = capped_state;
 758                 else
 759                         right_true = capped_state;
 760                 break;
 761         }
 762
 763         set_true_false_states_expr(my_id, left, left_true, left_false);
 764         set_true_false_states_expr(my_id, right, right_true, right_false);
 765 }
 766
 767 static void match_condition(struct expression *expr)
 768 {
 769         if (expr->type != EXPR_COMPARE)
 770                 return;
 771
 772         if (expr->op == SPECIAL_EQUAL ||
 773             expr->op == SPECIAL_NOTEQUAL) {
 774                 handle_eq_noteq(expr);
 775                 return;
 776         }
 777
 778         handle_compare(expr);
 779 }
 780
 781 static void match_returns_user_rl(const char *fn, struct expression *expr, void *unused)
 782 {
 783         func_gets_user_data = true;
 784 }
 785
 786 static int get_user_macro_rl(struct expression *expr, struct range_list **rl)
 787 {
 788         struct expression *parent;
 789         char *macro;
 790
 791         if (!expr)
 792                 return 0;
 793
 794         macro = get_macro_name(expr->pos);
 795         if (!macro)
 796                 return 0;
 797
 798         /* handle ntohl(foo[i]) where "i" is trusted */
 799         parent = expr_get_parent_expr(expr);
 800         while (parent && parent->type != EXPR_BINOP)
 801                 parent = expr_get_parent_expr(parent);
 802         if (parent && parent->type == EXPR_BINOP) {
 803                 char *parent_macro = get_macro_name(parent->pos);
 804
 805                 if (parent_macro && strcmp(macro, parent_macro) == 0)
 806                         return 0;
 807         }
 808
 809         if (strcmp(macro, "ntohl") == 0) {
 810                 *rl = alloc_whole_rl(&uint_ctype);
 811                 return 1;
 812         }
 813         if (strcmp(macro, "ntohs") == 0) {
 814                 *rl = alloc_whole_rl(&ushort_ctype);
 815                 return 1;
 816         }
 817         return 0;
 818 }
 819
 820 static int has_user_data(struct symbol *sym)
 821 {
 822         struct sm_state *tmp;
 823
 824         FOR_EACH_MY_SM(my_id, __get_cur_stree(), tmp) {
 825                 if (tmp->sym == sym)
 826                         return 1;
 827         } END_FOR_EACH_SM(tmp);
 828         return 0;
 829 }
 830
 831 bool we_pass_user_data(struct expression *call)
 832 {
 833         struct expression *arg;
 834         struct symbol *sym;
 835
 836         FOR_EACH_PTR(call->args, arg) {
 837                 if (points_to_user_data(arg))
 838                         return true;
 839                 sym = expr_to_sym(arg);
 840                 if (!sym)
 841                         continue;
 842                 if (has_user_data(sym))
 843                         return true;
 844         } END_FOR_EACH_PTR(arg);
 845
 846         return false;
 847 }
 848
 849 static int db_returned_user_rl(struct expression *call, struct range_list **rl)
 850 {
 851         struct smatch_state *state;
 852         char buf[48];
 853
 854         if (is_fake_call(call))
 855                 return 0;
 856         snprintf(buf, sizeof(buf), "return %p", call);
 857         state = get_state(my_id, buf, NULL);
 858         if (!state || !estate_rl(state))
 859                 return 0;
 860         *rl = estate_rl(state);
 861         return 1;
 862 }
 863
 864 struct stree *get_user_stree(void)
 865 {
 866         return get_all_states_stree(my_id);
 867 }
 868
 869 static int user_data_flag;
 870 static int no_user_data_flag;
 871 struct range_list *var_user_rl(struct expression *expr)
 872 {
 873         struct smatch_state *state;
 874         struct range_list *rl;
 875         struct range_list *absolute_rl;
 876
 877         if (expr->type == EXPR_PREOP && expr->op == '&') {
 878                 no_user_data_flag = 1;
 879                 return NULL;
 880         }
 881
 882         if (expr->type == EXPR_BINOP && expr->op == '%') {
 883                 struct range_list *left, *right;
 884
 885                 if (!get_user_rl(expr->right, &right))
 886                         return NULL;
 887                 get_absolute_rl(expr->left, &left);
 888                 rl = rl_binop(left, '%', right);
 889                 goto found;
 890         }
 891
 892         if (expr->type == EXPR_BINOP && expr->op == '/') {
 893                 struct range_list *left = NULL;
 894                 struct range_list *right = NULL;
 895                 struct range_list *abs_right;
 896
 897                 /*
 898                  * The specific bug I'm dealing with is:
 899                  *
 900                  * foo = capped_user / unknown;
 901                  *
 902                  * Instead of just saying foo is now entirely user_rl we should
 903                  * probably say instead that it is not at all user data.
 904                  *
 905                  */
 906
 907                 get_user_rl(expr->left, &left);
 908                 get_user_rl(expr->right, &right);
 909                 get_absolute_rl(expr->right, &abs_right);
 910
 911                 if (left && !right) {
 912                         rl = rl_binop(left, '/', abs_right);
 913                         if (sval_cmp(rl_max(left), rl_max(rl)) < 0)
 914                                 no_user_data_flag = 1;
 915                 }
 916
 917                 return NULL;
 918         }
 919
 920         if (get_rl_from_function(expr, &rl))
 921                 goto found;
 922
 923         if (get_user_macro_rl(expr, &rl))
 924                 goto found;
 925
 926         if (comes_from_skb_data(expr)) {
 927                 rl = alloc_whole_rl(get_type(expr));
 928                 goto found;
 929         }
 930
 931         state = get_state_expr(my_id, expr);
 932         if (state && estate_rl(state)) {
 933                 rl = estate_rl(state);
 934                 goto found;
 935         }
 936
 937         if (expr->type == EXPR_CALL && db_returned_user_rl(expr, &rl))
 938                 goto found;
 939
 940         if (expr->type == EXPR_PREOP && expr->op == '*' &&
 941             points_to_user_data(expr->unop)) {
 942                 rl = var_to_absolute_rl(expr);
 943                 goto found;
 944         }
 945
 946         if (is_array(expr)) {
 947                 struct expression *array = get_array_base(expr);
 948
 949                 if (!get_state_expr(my_id, array)) {
 950                         no_user_data_flag = 1;
 951                         return NULL;
 952                 }
 953         }
 954
 955         return NULL;
 956 found:
 957         user_data_flag = 1;
 958         absolute_rl = var_to_absolute_rl(expr);
 959         return clone_rl(rl_intersection(rl, absolute_rl));
 960 }
 961
 962 static bool is_ptr_subtract(struct expression *expr)
 963 {
 964         expr = strip_expr(expr);
 965         if (!expr)
 966                 return false;
 967         if (expr->type == EXPR_BINOP && expr->op == '-' &&
 968             type_is_ptr(get_type(expr->left))) {
 969                 return true;
 970         }
 971         return false;
 972 }
 973
 974 int get_user_rl(struct expression *expr, struct range_list **rl)
 975 {
 976         if (is_ptr_subtract(expr))
 977                 return 0;
 978
 979         user_data_flag = 0;
 980         no_user_data_flag = 0;
 981         custom_get_absolute_rl(expr, &var_user_rl, rl);
 982         if (!user_data_flag || no_user_data_flag)
 983                 *rl = NULL;
 984
 985         return !!*rl;
 986 }
 987
 988 int is_user_rl(struct expression *expr)
 989 {
 990         struct range_list *tmp;
 991
 992         return get_user_rl(expr, &tmp) && tmp;
 993 }
 994
 995 int get_user_rl_var_sym(const char *name, struct symbol *sym, struct range_list **rl)
 996 {
 997         struct smatch_state *state;
 998
 999         state = get_state(my_id, name, sym);
1000         if (state && estate_rl(state)) {
1001                 *rl = estate_rl(state);
1002                 return 1;
1003         }
1004         return 0;
1005 }
1006
1007 static void return_info_callback(int return_id, char *return_ranges,
1008                                  struct expression *returned_expr,
1009                                  int param,
1010                                  const char *printed_name,
1011                                  struct sm_state *sm)
1012 {
1013         struct smatch_state *extra;
1014         struct range_list *rl;
1015         char buf[64];
1016
1017         if (param >= 0) {
1018                 if (strcmp(printed_name, "$") == 0)
1019                         return;
1020                 if (!param_was_set_var_sym(sm->name, sm->sym))
1021                         return;
1022         }
1023         rl = estate_rl(sm->state);
1024         if (!rl)
1025                 return;
1026         extra = get_state(SMATCH_EXTRA, sm->name, sm->sym);
1027         if (estate_rl(extra))
1028                 rl = rl_intersection(estate_rl(sm->state), estate_rl(extra));
1029         if (!rl)
1030                 return;
1031
1032         snprintf(buf, sizeof(buf), "%s%s%s",
1033                  show_rl(rl),
1034                  estate_capped(sm->state) ? "[c]" : "",
1035                  estate_treat_untagged(sm->state) ? "[u]" : "");
1036         sql_insert_return_states(return_id, return_ranges,
1037                                  estate_new(sm->state) ? USER_DATA_SET : USER_DATA,
1038                                  param, printed_name, buf);
1039 }
1040
1041 static void caller_info_callback(struct expression *call, int param, char *printed_name, struct sm_state *sm)
1042 {
1043         struct smatch_state *state;
1044         struct range_list *rl;
1045         struct symbol *type;
1046         char buf[64];
1047
1048         /*
1049          * Smatch uses a hack where if we get an unsigned long we say it's
1050          * both user data and it points to user data.  But if we pass it to a
1051          * function which takes an int, then it's just user data.  There's not
1052          * enough bytes for it to be a pointer.
1053          *
1054          */
1055         type = get_arg_type(call->fn, param);
1056         if (strcmp(printed_name, "$") != 0 && type && type_bits(type) < type_bits(&ptr_ctype))
1057                 return;
1058
1059         if (strcmp(sm->state->name, "") == 0)
1060                 return;
1061
1062         state = __get_state(SMATCH_EXTRA, sm->name, sm->sym);
1063         if (!state || !estate_rl(state))
1064                 rl = estate_rl(sm->state);
1065         else
1066                 rl = rl_intersection(estate_rl(sm->state), estate_rl(state));
1067
1068         if (!rl)
1069                 return;
1070
1071         snprintf(buf, sizeof(buf), "%s%s%s", show_rl(rl),
1072                  estate_capped(sm->state) ? "[c]" : "",
1073                  estate_treat_untagged(sm->state) ? "[u]" : "");
1074         sql_insert_caller_info(call, USER_DATA, param, printed_name, buf);
1075 }
1076
1077 static void db_param_set(struct expression *expr, int param, char *key, char *value)
1078 {
1079         struct expression *arg;
1080         char *name;
1081         struct symbol *sym;
1082         struct smatch_state *state;
1083
1084         while (expr->type == EXPR_ASSIGNMENT)
1085                 expr = strip_expr(expr->right);
1086         if (expr->type != EXPR_CALL)
1087                 return;
1088
1089         arg = get_argument_from_call_expr(expr->args, param);
1090         if (!arg)
1091                 return;
1092         name = get_variable_from_key(arg, key, &sym);
1093         if (!name || !sym)
1094                 goto free;
1095
1096         state = get_state(my_id, name, sym);
1097         if (!state)
1098                 goto free;
1099
1100         set_state(my_id, name, sym, alloc_estate_empty());
1101 free:
1102         free_string(name);
1103 }
1104
1105 static bool param_data_capped(const char *value)
1106 {
1107         if (strstr(value, ",c") || strstr(value, "[c"))
1108                 return true;
1109         return false;
1110 }
1111
1112 static bool param_data_treat_untagged(const char *value)
1113 {
1114         if (strstr(value, ",u") || strstr(value, "[u"))
1115                 return true;
1116         return false;
1117 }
1118
1119 static void set_param_user_data(const char *name, struct symbol *sym, char *key, char *value)
1120 {
1121         struct expression *expr;
1122         struct range_list *rl = NULL;
1123         struct smatch_state *state;
1124         struct symbol *type;
1125         char *fullname;
1126
1127         expr = symbol_expression(sym);
1128         fullname = get_variable_from_key(expr, key, NULL);
1129         if (!fullname)
1130                 return;
1131
1132         type = get_member_type_from_key(expr, key);
1133         if (type && type->type == SYM_STRUCT)
1134                 return;
1135
1136         // FIXME: This is temporary.  Just run this on Thursday and then
1137         // let's make it a printf() and then delete it.
1138         if (!type)
1139                 return;
1140
1141         str_to_rl(type, value, &rl);
1142         rl = swap_mtag_seed(expr, rl);
1143         state = alloc_estate_rl(rl);
1144         if (param_data_capped(value) || is_capped(expr))
1145                 estate_set_capped(state);
1146         if (param_data_treat_untagged(value) || sym->ctype.as == 5)
1147                 estate_set_treat_untagged(state);
1148         set_state(my_id, fullname, sym, state);
1149 }
1150
1151 static void set_called(const char *name, struct symbol *sym, char *key, char *value)
1152 {
1153         set_state(my_call_id, "this_function", NULL, &called);
1154 }
1155
1156 static void match_syscall_definition(struct symbol *sym)
1157 {
1158         struct symbol *arg;
1159         char *macro;
1160         char *name;
1161         int is_syscall = 0;
1162
1163         macro = get_macro_name(sym->pos);
1164         if (macro &&
1165             (strncmp("SYSCALL_DEFINE", macro, strlen("SYSCALL_DEFINE")) == 0 ||
1166              strncmp("COMPAT_SYSCALL_DEFINE", macro, strlen("COMPAT_SYSCALL_DEFINE")) == 0))
1167                 is_syscall = 1;
1168
1169         name = get_function();
1170         if (!option_no_db && get_state(my_call_id, "this_function", NULL) != &called) {
1171                 if (name && strncmp(name, "sys_", 4) == 0)
1172                         is_syscall = 1;
1173         }
1174
1175         if (name && strncmp(name, "compat_sys_", 11) == 0)
1176                 is_syscall = 1;
1177
1178         if (!is_syscall)
1179                 return;
1180
1181         FOR_EACH_PTR(sym->ctype.base_type->arguments, arg) {
1182                 set_state(my_id, arg->ident->name, arg, alloc_estate_whole(get_real_base_type(arg)));
1183         } END_FOR_EACH_PTR(arg);
1184 }
1185
1186 #define OLD 0
1187 #define NEW 1
1188
1189 static void store_user_data_return(struct expression *expr, char *key, char *value, bool is_new)
1190 {
1191         struct smatch_state *state;
1192         struct range_list *rl;
1193         struct symbol *type;
1194         char buf[48];
1195
1196         if (key[0] != '$')
1197                 return;
1198
1199         type = get_type(expr);
1200         snprintf(buf, sizeof(buf), "return %p%s", expr, key + 1);
1201         call_results_to_rl(expr, type, value, &rl);
1202
1203         state = alloc_estate_rl(rl);
1204         if (is_new)
1205                 estate_set_new(state);
1206
1207         set_state(my_id, buf, NULL, state);
1208 }
1209
1210 static void set_to_user_data(struct expression *expr, char *key, char *value, bool is_new)
1211 {
1212         struct smatch_state *state;
1213         char *name;
1214         struct symbol *sym;
1215         struct symbol *type;
1216         struct range_list *rl = NULL;
1217
1218         type = get_member_type_from_key(expr, key);
1219         name = get_variable_from_key(expr, key, &sym);
1220         if (!name || !sym)
1221                 goto free;
1222
1223         call_results_to_rl(expr, type, value, &rl);
1224
1225         state = alloc_estate_rl(rl);
1226         if (param_data_capped(value))
1227                 estate_set_capped(state);
1228         if (param_data_treat_untagged(value))
1229                 estate_set_treat_untagged(state);
1230         if (is_new)
1231                 estate_set_new(state);
1232         set_state(my_id, name, sym, state);
1233 free:
1234         free_string(name);
1235 }
1236
1237 static void returns_param_user_data(struct expression *expr, int param, char *key, char *value)
1238 {
1239         struct expression *arg;
1240         struct expression *call;
1241
1242         call = expr;
1243         while (call->type == EXPR_ASSIGNMENT)
1244                 call = strip_expr(call->right);
1245         if (call->type != EXPR_CALL)
1246                 return;
1247
1248         if (!we_pass_user_data(call))
1249                 return;
1250
1251         if (param == -1) {
1252                 if (expr->type != EXPR_ASSIGNMENT) {
1253                         store_user_data_return(expr, key, value, OLD);
1254                         return;
1255                 }
1256                 set_to_user_data(expr->left, key, value, OLD);
1257                 return;
1258         }
1259
1260         arg = get_argument_from_call_expr(call->args, param);
1261         if (!arg)
1262                 return;
1263         set_to_user_data(arg, key, value, OLD);
1264 }
1265
1266 static void returns_param_user_data_set(struct expression *expr, int param, char *key, char *value)
1267 {
1268         struct expression *arg;
1269
1270         func_gets_user_data = true;
1271
1272         if (param == -1) {
1273                 if (expr->type != EXPR_ASSIGNMENT) {
1274                         store_user_data_return(expr, key, value, NEW);
1275                         return;
1276                 }
1277                 set_to_user_data(expr->left, key, value, NEW);
1278                 return;
1279         }
1280
1281         while (expr->type == EXPR_ASSIGNMENT)
1282                 expr = strip_expr(expr->right);
1283         if (expr->type != EXPR_CALL)
1284                 return;
1285
1286         arg = get_argument_from_call_expr(expr->args, param);
1287         if (!arg)
1288                 return;
1289         set_to_user_data(arg, key, value, NEW);
1290 }
1291
1292 static void returns_param_capped(struct expression *expr, int param, char *key, char *value)
1293 {
1294         struct smatch_state *state, *new;
1295         struct symbol *sym;
1296         char *name;
1297
1298         name = get_name_sym_from_key(expr, param, key, &sym);
1299         if (!name || !sym)
1300                 goto free;
1301
1302         state = get_state(my_id, name, sym);
1303         if (!state || estate_capped(state))
1304                 goto free;
1305
1306         new = clone_estate(state);
1307         estate_set_capped(new);
1308
1309         set_state(my_id, name, sym, new);
1310 free:
1311         free_string(name);
1312 }
1313
1314 static void match_function_def(struct symbol *sym)
1315 {
1316         if (is_user_data_fn(sym))
1317                 func_gets_user_data = true;
1318 }
1319
1320 void register_kernel_user_data(int id)
1321 {
1322         int i;
1323
1324         my_id = id;
1325
1326         if (option_project != PROJ_KERNEL)
1327                 return;
1328
1329         set_dynamic_states(my_id);
1330
1331         add_function_data(&func_gets_user_data);
1332         add_hook(&match_function_def, FUNC_DEF_HOOK);
1333
1334         add_hook(&save_start_states, AFTER_DEF_HOOK);
1335         add_hook(&free_start_states, AFTER_FUNC_HOOK);
1336         add_function_data((unsigned long *)&start_states);
1337
1338         add_unmatched_state_hook(my_id, &empty_state);
1339         add_extra_nomod_hook(&extra_nomod_hook);
1340         add_pre_merge_hook(my_id, &pre_merge_hook);
1341         add_merge_hook(my_id, &merge_estates);
1342
1343         add_function_hook("copy_from_user", &match_user_copy, INT_PTR(0));
1344         add_function_hook("__copy_from_user", &match_user_copy, INT_PTR(0));
1345         add_function_hook("memcpy_fromiovec", &match_user_copy, INT_PTR(0));
1346         for (i = 0; i < ARRAY_SIZE(kstr_funcs); i++)
1347                 add_function_hook(kstr_funcs[i], &match_user_copy, INT_PTR(2));
1348         add_function_hook("usb_control_msg", &match_user_copy, INT_PTR(6));
1349
1350         for (i = 0; i < ARRAY_SIZE(returns_user_data); i++)
1351                 add_function_hook(returns_user_data[i], &match_returns_user_rl, NULL);
1352
1353         add_function_hook("sscanf", &match_sscanf, NULL);
1354
1355         add_hook(&match_syscall_definition, AFTER_DEF_HOOK);
1356
1357         add_hook(&match_assign, ASSIGNMENT_HOOK);
1358         select_return_states_hook(PARAM_SET, &db_param_set);
1359         add_hook(&match_condition, CONDITION_HOOK);
1360
1361         add_caller_info_callback(my_id, caller_info_callback);
1362         add_return_info_callback(my_id, return_info_callback);
1363         select_caller_info_hook(set_param_user_data, USER_DATA);
1364         select_return_states_hook(USER_DATA, &returns_param_user_data);
1365         select_return_states_hook(USER_DATA_SET, &returns_param_user_data_set);
1366         select_return_states_hook(CAPPED_DATA, &returns_param_capped);
1367 }
1368
1369 void register_kernel_user_data2(int id)
1370 {
1371         my_call_id = id;
1372
1373         if (option_project != PROJ_KERNEL)
1374                 return;
1375         select_caller_info_hook(set_called, INTERNAL);
1376 }
1377