check_overflow.c

   1 /*
   2  * smatch/check_deference.c
   3  *
   4  * Copyright (C) 2006 Dan Carpenter.
   5  *
   6  * Licensed under the Open Software License version 1.1
   7  *
   8  */
   9
  10 #include <stdlib.h>
  11 #include "parse.h"
  12 #include "smatch.h"
  13 #include "smatch_slist.h"
  14 #include "smatch_extra.h"
  15
  16 struct bound {
  17         int param;
  18         int size;
  19 };
  20
  21 /*
  22  * This check has two smatch IDs.
  23  * my_size_id - used to store the size of arrays.
  24  * my_used_id - keeps a record of array offsets that have been used.
  25  *              If the code checks that they are within bounds later on,
  26  *              we complain about using an array offset before checking
  27  *              that it is within bounds.
  28  */
  29 static int my_size_id;
  30 static int my_used_id;
  31 static int my_strlen_id;
  32
  33 static struct symbol *this_func;
  34
  35 static int get_array_size(struct expression *expr);
  36
  37 static void match_function_def(struct symbol *sym)
  38 {
  39         this_func = sym;
  40 }
  41
  42 struct limiter {
  43         int buf_arg;
  44         int limit_arg;
  45 };
  46 struct limiter b0_l2 = {0, 2};
  47 struct limiter b1_l2 = {1, 2};
  48
  49 static void print_args(struct expression *expr, int size)
  50 {
  51         struct symbol *sym;
  52         char *name;
  53         struct symbol *arg;
  54         const char *arg_name;
  55         int i;
  56
  57         if (!option_info)
  58                 return;
  59
  60         name = get_variable_from_expr(expr, &sym);
  61         if (!name || !sym)
  62                 goto free;
  63
  64         i = 0;
  65         FOR_EACH_PTR(this_func->ctype.base_type->arguments, arg) {
  66                 arg_name = (arg->ident?arg->ident->name:"-");
  67                 if (sym == arg && !strcmp(name, arg_name)) {
  68                         sm_info("param %d array index. size %d", i, size);
  69                         goto free;
  70                 }
  71                 i++;
  72         } END_FOR_EACH_PTR(arg);
  73 free:
  74         free_string(name);
  75 }
  76
  77 static char *alloc_num(long long num)
  78 {
  79         static char buff[256];
  80
  81         if (num == whole_range.min)
  82                 snprintf(buff, 255, "min");
  83         else if (num == whole_range.max)
  84                 snprintf(buff, 255, "max");
  85         else if (num < 0)
  86                 snprintf(buff, 255, "(%lld)", num);
  87         else
  88                 snprintf(buff, 255, "%lld", num);
  89
  90         buff[255] = '\0';
  91         return alloc_sname(buff);
  92 }
  93
  94 static void delete(const char *name, struct symbol *sym, struct expression *expr, void *unused)
  95 {
  96         delete_state(my_used_id, name, sym);
  97 }
  98
  99 static struct smatch_state *alloc_my_state(int val)
 100 {
 101         struct smatch_state *state;
 102
 103         state = __alloc_smatch_state(0);
 104         state->name = alloc_num(val);
 105         state->data = malloc(sizeof(int));
 106         *(int *)state->data = val;
 107         return state;
 108 }
 109
 110 static int get_initializer_size(struct expression *expr)
 111 {
 112         switch(expr->type) {
 113         case EXPR_STRING:
 114                 return expr->string->length;
 115         case EXPR_INITIALIZER: {
 116                 struct expression *tmp;
 117                 int i = 0;
 118                 int max = 0;
 119
 120                 FOR_EACH_PTR(expr->expr_list, tmp) {
 121                         if (tmp->type == EXPR_INDEX && tmp->idx_to > max)
 122                                 max = tmp->idx_to;
 123                         i++;
 124                 } END_FOR_EACH_PTR(tmp);
 125                 if (max)
 126                         return max + 1;
 127                 return i;
 128         }
 129         case EXPR_SYMBOL:
 130                 return get_array_size(expr);
 131         }
 132         return 0;
 133 }
 134
 135 static float get_cast_ratio(struct expression *unstripped)
 136 {
 137         struct expression *start_expr;
 138         struct symbol *start_type;
 139         struct symbol *end_type;
 140         int start_bytes = 0;
 141         int end_bytes = 0;
 142
 143         start_expr = strip_expr(unstripped);
 144         start_type  =  get_type(start_expr);
 145         end_type = get_type(unstripped);
 146         if (!start_type || !end_type)
 147                 return 1;
 148
 149         if (start_type->type == SYM_PTR)
 150                 start_bytes = (get_base_type(start_type))->ctype.alignment;
 151         if (start_type->type == SYM_ARRAY)
 152                 start_bytes = (get_base_type(start_type))->bit_size / 8;
 153         if (end_type->type == SYM_PTR)
 154                 end_bytes = (get_base_type(end_type))->ctype.alignment;
 155         if (end_type->type == SYM_ARRAY)
 156                 end_bytes = (get_base_type(end_type))->bit_size / 8;
 157
 158         if (!start_bytes || !end_bytes)
 159                 return 1;
 160         return start_bytes / end_bytes;
 161 }
 162
 163 static int get_array_size(struct expression *expr)
 164 {
 165         struct symbol *tmp;
 166         struct smatch_state *state;
 167         int ret = 0;
 168         float cast_ratio;
 169         long long len;
 170
 171         if (expr->type == EXPR_STRING)
 172                 return expr->string->length;
 173
 174         cast_ratio = get_cast_ratio(expr);
 175         expr = strip_expr(expr);
 176         tmp = get_type(expr);
 177         if (!tmp)
 178                 return 0;
 179
 180         if (tmp->type == SYM_ARRAY) {
 181                 ret = get_expression_value(tmp->array_size);
 182                 if (ret == 1)
 183                         return 0;
 184                 if (ret)
 185                         return ret * cast_ratio;
 186         }
 187
 188         state = get_state_expr(my_size_id, expr);
 189         if (state == &merged)
 190                 return 0;
 191         if (state && state->data) {
 192                 if (tmp->type == SYM_PTR)
 193                         tmp = get_base_type(tmp);
 194                 if (!tmp->ctype.alignment)
 195                         return 0;
 196                 ret = *(int *)state->data / tmp->ctype.alignment;
 197                 return ret * cast_ratio;
 198         }
 199
 200         if (expr->type == EXPR_SYMBOL && expr->symbol->initializer) {
 201                 if (expr->symbol->initializer != expr) /* int a = a; */
 202                         return get_initializer_size(expr->symbol->initializer) * cast_ratio;
 203         }
 204
 205         state = get_state_expr(my_strlen_id, expr);
 206         if (!state || !state->data)
 207                 return 0;
 208         if (get_implied_max((struct expression *)state->data, &len))
 209                 return len + 1; /* add one because strlen doesn't include the NULL */
 210         return 0;
 211 }
 212
 213 static int get_array_size_bytes(struct expression *expr)
 214 {
 215         struct symbol *tmp;
 216         int array_size;
 217         int element_size;
 218
 219         if (expr->type == EXPR_STRING)
 220                 return expr->string->length;
 221
 222         tmp = get_type(expr);
 223         if (!tmp)
 224                 return 0;
 225
 226         if (tmp->type == SYM_ARRAY) {
 227                 tmp = get_base_type(tmp);
 228                 element_size = tmp->bit_size / 8;
 229         } else if (tmp->type == SYM_PTR) {
 230                 tmp = get_base_type(tmp);
 231                 element_size = tmp->ctype.alignment;
 232         } else {
 233                 return 0;
 234         }
 235         array_size = get_array_size(expr);
 236         return array_size * element_size;
 237 }
 238
 239 static int definitely_just_used_as_limiter(struct expression *array, struct expression *offset)
 240 {
 241         long long val;
 242         struct expression *tmp;
 243         int step = 0;
 244         int dot_ops = 0;
 245
 246         if (!get_implied_value(offset, &val))
 247                 return 0;
 248         if (get_array_size(array) != val)
 249                 return 0;
 250
 251         FOR_EACH_PTR_REVERSE(big_expression_stack, tmp) {
 252                 if (step == 0) {
 253                         step = 1;
 254                         continue;
 255                 }
 256                 if (tmp->type == EXPR_PREOP && tmp->op == '(')
 257                         continue;
 258                 if (tmp->op == '.' && !dot_ops++)
 259                         continue;
 260                 if (step == 1 && tmp->op == '&') {
 261                         step = 2;
 262                         continue;
 263                 }
 264                 if (step == 2 && tmp->type == EXPR_COMPARE)
 265                         return 1;
 266                 return 0;
 267         } END_FOR_EACH_PTR_REVERSE(tmp);
 268         return 0;
 269 }
 270
 271 static void array_check(struct expression *expr)
 272 {
 273         struct expression *array_expr;
 274         int array_size;
 275         struct expression *offset;
 276         long long max;
 277         char *name;
 278
 279         expr = strip_expr(expr);
 280         if (!is_array(expr))
 281                 return;
 282
 283         array_expr = strip_parens(expr->unop->left);
 284         array_size = get_array_size(array_expr);
 285         if (!array_size || array_size == 1)
 286                 return;
 287
 288         offset = get_array_offset(expr);
 289         if (!get_fuzzy_max(offset, &max)) {
 290                 if (getting_address())
 291                         return;
 292                 set_state_expr(my_used_id, offset, alloc_state_num(array_size));
 293                 add_modification_hook_expr(my_used_id, offset, &delete, NULL);
 294                 print_args(offset, array_size);
 295         } else if (array_size <= max) {
 296                 const char *level = "error";
 297
 298                 if (getting_address())
 299                         level = "warn";
 300
 301                 if (definitely_just_used_as_limiter(array_expr, offset))
 302                         return;
 303
 304                 if (!option_spammy) {
 305                         struct smatch_state *state;
 306
 307                         state = get_state_expr(SMATCH_EXTRA, offset);
 308                         if (state && is_whole_range(state))
 309                                 return;
 310                 }
 311
 312                 name = get_variable_from_expr_complex(array_expr, NULL);
 313                 /* Blast.  Smatch can't figure out glibc's strcmp __strcmp_cg()
 314                  * so it prints an error every time you compare to a string
 315                  * literal array with 4 or less chars.
 316                  */
 317                 if (name && strcmp(name, "__s1") && strcmp(name, "__s2")) {
 318                         sm_msg("%s: buffer overflow '%s' %d <= %lld",
 319                                 level, name, array_size, max);
 320                 }
 321                 free_string(name);
 322         }
 323 }
 324
 325 static void match_condition(struct expression *expr)
 326 {
 327         int left;
 328         long long val;
 329         struct state_list *slist;
 330         struct sm_state *tmp;
 331         int boundary;
 332
 333         if (!expr || expr->type != EXPR_COMPARE)
 334                 return;
 335         if (get_implied_value(expr->left, &val))
 336                 left = 1;
 337         else if (get_implied_value(expr->right, &val))
 338                 left = 0;
 339         else
 340                 return;
 341
 342         if (left)
 343                 slist = get_possible_states_expr(my_used_id, expr->right);
 344         else
 345                 slist = get_possible_states_expr(my_used_id, expr->left);
 346         if (!slist)
 347                 return;
 348         FOR_EACH_PTR(slist, tmp) {
 349                 if (tmp->state == &merged)
 350                         continue;
 351                 boundary = (int)tmp->state->data;
 352                 boundary -= val;
 353                 if (boundary < 1 && boundary > -1) {
 354                         char *name;
 355
 356                         name = get_variable_from_expr((left ? expr->right : expr->left), NULL);
 357                         sm_msg("error: testing array offset '%s' after use.", name);
 358                         return;
 359                 }
 360         } END_FOR_EACH_PTR(tmp);
 361 }
 362
 363 static void match_strlen_condition(struct expression *expr)
 364 {
 365         struct expression *left;
 366         struct expression *right;
 367         struct expression *str;
 368         int strlen_left = 0;
 369         int strlen_right = 0;
 370         long long val;
 371         struct smatch_state *true_state = NULL;
 372         struct smatch_state *false_state = NULL;
 373
 374         if (expr->type != EXPR_COMPARE)
 375                 return;
 376         left = strip_expr(expr->left);
 377         right = strip_expr(expr->right);
 378
 379         if (left->type == EXPR_CALL && sym_name_is("strlen", left->fn)) {
 380                 str = get_argument_from_call_expr(left->args, 0);
 381                 strlen_left = 1;
 382         }
 383         if (right->type == EXPR_CALL && sym_name_is("strlen", right->fn)) {
 384                 str = get_argument_from_call_expr(right->args, 0);
 385                 strlen_right = 1;
 386         }
 387
 388         if (!strlen_left && !strlen_right)
 389                 return;
 390         if (strlen_left && strlen_right)
 391                 return;
 392
 393         if (strlen_left) {
 394                 if (!get_value(right, &val))
 395                         return;
 396         }
 397         if (strlen_right) {
 398                 if (!get_value(left, &val))
 399                         return;
 400         }
 401
 402         if (expr->op == SPECIAL_EQUAL) {
 403                 set_true_false_states_expr(my_size_id, str, alloc_my_state(val + 1), NULL);
 404                 return;
 405         }
 406         if (expr->op == SPECIAL_NOTEQUAL) {
 407                 set_true_false_states_expr(my_size_id, str, NULL, alloc_my_state(val + 1));
 408                 return;
 409         }
 410
 411         switch (expr->op) {
 412         case '<':
 413         case SPECIAL_UNSIGNED_LT:
 414                 if (strlen_left)
 415                         true_state = alloc_my_state(val);
 416                 else
 417                         false_state = alloc_my_state(val + 1);
 418                 break;
 419         case SPECIAL_LTE:
 420         case SPECIAL_UNSIGNED_LTE:
 421                 if (strlen_left)
 422                         true_state = alloc_my_state(val + 1);
 423                 else
 424                         false_state = alloc_my_state(val);
 425                 break;
 426         case SPECIAL_GTE:
 427         case SPECIAL_UNSIGNED_GTE:
 428                 if (strlen_left)
 429                         false_state = alloc_my_state(val);
 430                 else
 431                         true_state = alloc_my_state(val + 1);
 432                 break;
 433         case '>':
 434         case SPECIAL_UNSIGNED_GT:
 435                 if (strlen_left)
 436                         false_state = alloc_my_state(val + 1);
 437                 else
 438                         true_state = alloc_my_state(val);
 439                 break;
 440         }
 441         set_true_false_states_expr(my_size_id, str, true_state, false_state);
 442 }
 443
 444 static struct expression *strip_ampersands(struct expression *expr)
 445 {
 446         struct symbol *type;
 447
 448         if (expr->type != EXPR_PREOP)
 449                 return expr;
 450         if (expr->op != '&')
 451                 return expr;
 452         type = get_type(expr->unop);
 453         if (!type || type->type != SYM_ARRAY)
 454                 return expr;
 455         return expr->unop;
 456 }
 457
 458 static void match_array_assignment(struct expression *expr)
 459 {
 460         struct expression *left;
 461         struct expression *right;
 462         int array_size;
 463
 464         if (expr->op != '=')
 465                 return;
 466         left = strip_expr(expr->left);
 467         right = strip_expr(expr->right);
 468         right = strip_ampersands(right);
 469         array_size = get_array_size_bytes(right);
 470         if (array_size)
 471                 set_state_expr(my_size_id, left, alloc_my_state(array_size));
 472 }
 473
 474 static void match_malloc(const char *fn, struct expression *expr, void *unused)
 475 {
 476         struct expression *right;
 477         struct expression *arg;
 478         long long bytes;
 479
 480         right = strip_expr(expr->right);
 481         arg = get_argument_from_call_expr(right->args, 0);
 482         if (!get_implied_value(arg, &bytes))
 483                 return;
 484         set_state_expr(my_size_id, expr->left, alloc_my_state(bytes));
 485 }
 486
 487 static void match_calloc(const char *fn, struct expression *expr, void *unused)
 488 {
 489         struct expression *right;
 490         struct expression *arg;
 491         long long elements;
 492         long long size;
 493
 494         right = strip_expr(expr->right);
 495         arg = get_argument_from_call_expr(right->args, 0);
 496         if (!get_implied_value(arg, &elements))
 497                 return;
 498         arg = get_argument_from_call_expr(right->args, 1);
 499         if (!get_implied_value(arg, &size))
 500                 return;
 501         set_state_expr(my_size_id, expr->left, alloc_my_state(elements * size));
 502 }
 503
 504 static void match_strlen(const char *fn, struct expression *expr, void *unused)
 505 {
 506         struct expression *right;
 507         struct expression *str;
 508         struct expression *len_expr;
 509         char *len_name;
 510         struct smatch_state *state;
 511
 512         right = strip_expr(expr->right);
 513         str = get_argument_from_call_expr(right->args, 0);
 514         len_expr = strip_expr(expr->left);
 515
 516         len_name = get_variable_from_expr(len_expr, NULL);
 517         if (!len_name)
 518                 return;
 519
 520         state = __alloc_smatch_state(0);
 521         state->name = len_name;
 522         state->data = len_expr;
 523         set_state_expr(my_strlen_id, str, state);
 524 }
 525
 526 static void match_strcpy(const char *fn, struct expression *expr, void *unused)
 527 {
 528         struct expression *dest;
 529         struct expression *data;
 530         char *dest_name = NULL;
 531         char *data_name = NULL;
 532         int dest_size;
 533         int data_size;
 534
 535         dest = get_argument_from_call_expr(expr->args, 0);
 536         data = get_argument_from_call_expr(expr->args, 1);
 537         dest_size = get_array_size_bytes(dest);
 538         data_size = get_array_size_bytes(data);
 539
 540         if (!dest_size)
 541                 return;
 542
 543         /* If the size of both arrays is known and the destination
 544          * buffer is larger than the source buffer, we're okay.
 545          */
 546         if (data_size && dest_size >= data_size)
 547                 return;
 548
 549         dest_name = get_variable_from_expr_complex(dest, NULL);
 550         data_name = get_variable_from_expr_complex(data, NULL);
 551
 552         if (data_size)
 553                 sm_msg("error: %s() '%s' too large for '%s' (%d vs %d)",
 554                         fn, data_name, dest_name, data_size, dest_size);
 555         else
 556                 sm_msg("warn: %s() '%s' of unknown size might be too large for '%s'",
 557                         fn, data_name, dest_name);
 558
 559         free_string(dest_name);
 560         free_string(data_name);
 561 }
 562
 563 static void match_limited(const char *fn, struct expression *expr, void *_limiter)
 564 {
 565         struct limiter *limiter = (struct limiter *)_limiter;
 566         struct expression *dest;
 567         struct expression *data;
 568         char *dest_name = NULL;
 569         long long needed;
 570         int has;
 571
 572         dest = get_argument_from_call_expr(expr->args, limiter->buf_arg);
 573         data = get_argument_from_call_expr(expr->args, limiter->limit_arg);
 574         if (!get_fuzzy_max(data, &needed))
 575                 return;
 576         has = get_array_size_bytes(dest);
 577         if (!has)
 578                 return;
 579         if (has >= needed)
 580                 return;
 581
 582         dest_name = get_variable_from_expr_complex(dest, NULL);
 583         sm_msg("error: %s() '%s' too small (%d vs %lld)", fn, dest_name, has, needed);
 584         free_string(dest_name);
 585 }
 586
 587 static void match_array_func(const char *fn, struct expression *expr, void *info)
 588 {
 589         struct bound *bound_info = (struct bound *)info;
 590         struct expression *arg;
 591         long long offset;
 592
 593         arg = get_argument_from_call_expr(expr->args, bound_info->param);
 594         if (!get_implied_value(arg, &offset))
 595                 return;
 596         if (offset >= bound_info->size)
 597                 sm_msg("error: buffer overflow calling %s. param %d.  %lld >= %d",
 598                         fn, bound_info->param, offset, bound_info->size);
 599 }
 600
 601 static void register_array_funcs(void)
 602 {
 603         struct token *token;
 604         const char *func;
 605         struct bound *bound_info = NULL;
 606
 607         token = get_tokens_file("kernel.array_bounds");
 608         if (!token)
 609                 return;
 610         if (token_type(token) != TOKEN_STREAMBEGIN)
 611                 return;
 612         token = token->next;
 613         while (token_type(token) != TOKEN_STREAMEND) {
 614                 bound_info = malloc(sizeof(*bound_info));
 615                 if (token_type(token) != TOKEN_IDENT)
 616                         break;
 617                 func = show_ident(token->ident);
 618                 token = token->next;
 619                 if (token_type(token) != TOKEN_NUMBER)
 620                         break;
 621                 bound_info->param = atoi(token->number);
 622                 token = token->next;
 623                 if (token_type(token) != TOKEN_NUMBER)
 624                         break;
 625                 bound_info->size = atoi(token->number);
 626                 add_function_hook(func, &match_array_func, bound_info);
 627                 token = token->next;
 628         }
 629         if (token_type(token) != TOKEN_STREAMEND)
 630                 free(bound_info);
 631         clear_token_alloc();
 632 }
 633
 634 void check_overflow(int id)
 635 {
 636         my_size_id = id;
 637         add_hook(&match_function_def, FUNC_DEF_HOOK);
 638         add_hook(&array_check, OP_HOOK);
 639         add_hook(&match_array_assignment, ASSIGNMENT_HOOK);
 640         add_hook(&match_condition, CONDITION_HOOK);
 641         add_hook(&match_strlen_condition, CONDITION_HOOK);
 642         add_function_assign_hook("malloc", &match_malloc, NULL);
 643         add_function_assign_hook("calloc", &match_calloc, NULL);
 644         add_function_assign_hook("strlen", &match_strlen, NULL);
 645         add_function_hook("strcpy", &match_strcpy, NULL);
 646         add_function_hook("strncpy", &match_limited, &b0_l2);
 647         add_function_hook("memset", &match_limited, &b0_l2);
 648         if (option_project == PROJ_KERNEL) {
 649                 add_function_assign_hook("kmalloc", &match_malloc, NULL);
 650                 add_function_assign_hook("kzalloc", &match_malloc, NULL);
 651                 add_function_assign_hook("vmalloc", &match_malloc, NULL);
 652                 add_function_assign_hook("__vmalloc", &match_malloc, NULL);
 653                 add_function_assign_hook("kcalloc", &match_calloc, NULL);
 654                 add_function_assign_hook("drm_malloc_ab", &match_calloc, NULL);
 655                 add_function_assign_hook("drm_calloc_large", &match_calloc, NULL);
 656                 add_function_hook("copy_to_user", &match_limited, &b0_l2);
 657                 add_function_hook("copy_to_user", &match_limited, &b1_l2);
 658                 add_function_hook("_copy_to_user", &match_limited, &b0_l2);
 659                 add_function_hook("_copy_to_user", &match_limited, &b1_l2);
 660                 add_function_hook("__copy_to_user", &match_limited, &b0_l2);
 661                 add_function_hook("__copy_to_user", &match_limited, &b1_l2);
 662                 add_function_hook("copy_from_user", &match_limited, &b0_l2);
 663                 add_function_hook("copy_from_user", &match_limited, &b1_l2);
 664                 add_function_hook("_copy_from_user", &match_limited, &b0_l2);
 665                 add_function_hook("_copy_from_user", &match_limited, &b1_l2);
 666                 add_function_hook("__copy_from_user", &match_limited, &b0_l2);
 667                 add_function_hook("__copy_from_user", &match_limited, &b1_l2);
 668                 add_function_hook("__builtin_memset", &match_limited, &b0_l2);
 669         }
 670         register_array_funcs();
 671 }
 672
 673 void register_check_overflow_again(int id)
 674 {
 675         my_used_id = id;
 676 }
 677
 678 void register_check_overflow_3(int id)
 679 {
 680         my_strlen_id = id;
 681 }