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
  32 static struct symbol *this_func;
  33
  34 static int get_array_size(struct expression *expr);
  35
  36 static void match_function_def(struct symbol *sym)
  37 {
  38         this_func = sym;
  39 }
  40
  41 struct limiter {
  42         int buf_arg;
  43         int limit_arg;
  44 };
  45 struct limiter b0_l2 = {0, 2};
  46 struct limiter b1_l2 = {1, 2};
  47
  48 static void print_args(struct expression *expr, int size)
  49 {
  50         struct symbol *sym;
  51         char *name;
  52         struct symbol *arg;
  53         const char *arg_name;
  54         int i;
  55
  56         if (!option_info)
  57                 return;
  58
  59         name = get_variable_from_expr(expr, &sym);
  60         if (!name || !sym)
  61                 goto free;
  62
  63         i = 0;
  64         FOR_EACH_PTR(this_func->ctype.base_type->arguments, arg) {
  65                 arg_name = (arg->ident?arg->ident->name:"-");
  66                 if (sym == arg && !strcmp(name, arg_name)) {
  67                         sm_info("param %d array index. size %d", i, size);
  68                         goto free;
  69                 }
  70                 i++;
  71         } END_FOR_EACH_PTR(arg);
  72 free:
  73         free_string(name);
  74 }
  75
  76 static char *alloc_num(long long num)
  77 {
  78         static char buff[256];
  79
  80         if (num == whole_range.min)
  81                 snprintf(buff, 255, "min");
  82         else if (num == whole_range.max)
  83                 snprintf(buff, 255, "max");
  84         else if (num < 0)
  85                 snprintf(buff, 255, "(%lld)", num);
  86         else
  87                 snprintf(buff, 255, "%lld", num);
  88
  89         buff[255] = '\0';
  90         return alloc_sname(buff);
  91 }
  92
  93 static void delete(const char *name, struct symbol *sym, struct expression *expr, void *unused)
  94 {
  95         delete_state(my_used_id, name, sym);
  96 }
  97
  98 static struct smatch_state *alloc_my_state(int val)
  99 {
 100         struct smatch_state *state;
 101
 102         state = __alloc_smatch_state(0);
 103         state->name = alloc_num(val);
 104         state->data = malloc(sizeof(int));
 105         *(int *)state->data = val;
 106         return state;
 107 }
 108
 109 static int get_initializer_size(struct expression *expr)
 110 {
 111         switch(expr->type) {
 112         case EXPR_STRING:
 113                 return expr->string->length;
 114         case EXPR_INITIALIZER: {
 115                 struct expression *tmp;
 116                 int i = 0;
 117                 int max = 0;
 118
 119                 FOR_EACH_PTR(expr->expr_list, tmp) {
 120                         if (tmp->type == EXPR_INDEX && tmp->idx_to > max)
 121                                 max = tmp->idx_to;
 122                         i++;
 123                 } END_FOR_EACH_PTR(tmp);
 124                 if (max)
 125                         return max + 1;
 126                 return i;
 127         }
 128         case EXPR_SYMBOL:
 129                 return get_array_size(expr);
 130         }
 131         return 0;
 132 }
 133
 134 static float get_cast_ratio(struct expression *unstripped)
 135 {
 136         struct expression *start_expr;
 137         struct symbol *start_type;
 138         struct symbol *end_type;
 139         int start_bytes = 0;
 140         int end_bytes = 0;
 141
 142         start_expr = strip_expr(unstripped);
 143         start_type  =  get_type(start_expr);
 144         end_type = get_type(unstripped);
 145         if (!start_type || !end_type)
 146                 return 1;
 147
 148         if (start_type->type == SYM_PTR)
 149                 start_bytes = (get_base_type(start_type))->ctype.alignment;
 150         if (start_type->type == SYM_ARRAY)
 151                 start_bytes = (get_base_type(start_type))->bit_size / 8;
 152         if (end_type->type == SYM_PTR)
 153                 end_bytes = (get_base_type(end_type))->ctype.alignment;
 154         if (end_type->type == SYM_ARRAY)
 155                 end_bytes = (get_base_type(end_type))->bit_size / 8;
 156
 157         if (!start_bytes || !end_bytes)
 158                 return 1;
 159         return start_bytes / end_bytes;
 160 }
 161
 162 static int get_array_size(struct expression *expr)
 163 {
 164         struct symbol *tmp;
 165         struct smatch_state *state;
 166         int ret = 0;
 167         float cast_ratio;
 168
 169         if (expr->type == EXPR_STRING)
 170                 return expr->string->length;
 171
 172         cast_ratio = get_cast_ratio(expr);
 173         expr = strip_expr(expr);
 174         tmp = get_type(expr);
 175         if (!tmp)
 176                 return 0;
 177
 178         if (tmp->type == SYM_ARRAY) {
 179                 ret = get_expression_value(tmp->array_size);
 180                 if (ret == 1)
 181                         return 0;
 182                 if (ret)
 183                         return ret * cast_ratio;
 184         }
 185
 186         state = get_state_expr(my_size_id, expr);
 187         if (state == &merged)
 188                 return 0;
 189         if (state && state->data) {
 190                 if (tmp->type == SYM_PTR)
 191                         tmp = get_base_type(tmp);
 192                 if (!tmp->ctype.alignment)
 193                         return 0;
 194                 ret = *(int *)state->data / tmp->ctype.alignment;
 195                 return ret * cast_ratio;
 196         }
 197
 198         if (expr->type == EXPR_SYMBOL && expr->symbol->initializer) {
 199                 if (expr->symbol->initializer != expr) /* int a = a; */
 200                         return get_initializer_size(expr->symbol->initializer) * cast_ratio;
 201         }
 202         return 0;
 203 }
 204
 205 static int get_array_size_bytes(struct expression *expr)
 206 {
 207         struct symbol *tmp;
 208         int array_size;
 209         int element_size;
 210
 211         if (expr->type == EXPR_STRING)
 212                 return expr->string->length;
 213
 214         tmp = get_type(expr);
 215         if (!tmp)
 216                 return 0;
 217
 218         if (tmp->type == SYM_ARRAY) {
 219                 tmp = get_base_type(tmp);
 220                 element_size = tmp->bit_size / 8;
 221         } else if (tmp->type == SYM_PTR) {
 222                 tmp = get_base_type(tmp);
 223                 element_size = tmp->ctype.alignment;
 224         } else {
 225                 return 0;
 226         }
 227         array_size = get_array_size(expr);
 228         return array_size * element_size;
 229 }
 230
 231 static int definitely_just_used_as_limiter(struct expression *array, struct expression *offset)
 232 {
 233         long long val;
 234         struct expression *tmp;
 235         int step = 0;
 236         int dot_ops = 0;
 237
 238         if (!get_implied_value(offset, &val))
 239                 return 0;
 240         if (get_array_size(array) != val)
 241                 return 0;
 242
 243         FOR_EACH_PTR_REVERSE(big_expression_stack, tmp) {
 244                 if (step == 0) {
 245                         step = 1;
 246                         continue;
 247                 }
 248                 if (tmp->type == EXPR_PREOP && tmp->op == '(')
 249                         continue;
 250                 if (tmp->op == '.' && !dot_ops++)
 251                         continue;
 252                 if (step == 1 && tmp->op == '&') {
 253                         step = 2;
 254                         continue;
 255                 }
 256                 if (step == 2 && tmp->type == EXPR_COMPARE)
 257                         return 1;
 258                 return 0;
 259         } END_FOR_EACH_PTR_REVERSE(tmp);
 260         return 0;
 261 }
 262
 263 static void array_check(struct expression *expr)
 264 {
 265         struct expression *array_expr;
 266         int array_size;
 267         struct expression *offset;
 268         long long max;
 269         char *name;
 270
 271         expr = strip_expr(expr);
 272         if (!is_array(expr))
 273                 return;
 274
 275         array_expr = strip_parens(expr->unop->left);
 276         array_size = get_array_size(array_expr);
 277         if (!array_size || array_size == 1)
 278                 return;
 279
 280         offset = get_array_offset(expr);
 281         if (!get_fuzzy_max(offset, &max)) {
 282                 if (getting_address())
 283                         return;
 284                 set_state_expr(my_used_id, offset, alloc_state_num(array_size));
 285                 add_modification_hook_expr(my_used_id, offset, &delete, NULL);
 286                 print_args(offset, array_size);
 287         } else if (array_size <= max) {
 288                 const char *level = "error";
 289
 290                 if (getting_address())
 291                         level = "warn";
 292
 293                 if (definitely_just_used_as_limiter(array_expr, offset))
 294                         return;
 295
 296                 if (!option_spammy) {
 297                         struct smatch_state *state;
 298
 299                         state = get_state_expr(SMATCH_EXTRA, offset);
 300                         if (state && is_whole_range(state))
 301                                 return;
 302                 }
 303
 304                 name = get_variable_from_expr_complex(array_expr, NULL);
 305                 /* Blast.  Smatch can't figure out glibc's strcmp __strcmp_cg()
 306                  * so it prints an error every time you compare to a string
 307                  * literal array with 4 or less chars.
 308                  */
 309                 if (name && strcmp(name, "__s1") && strcmp(name, "__s2")) {
 310                         sm_msg("%s: buffer overflow '%s' %d <= %lld",
 311                                 level, name, array_size, max);
 312                 }
 313                 free_string(name);
 314         }
 315 }
 316
 317 static void match_condition(struct expression *expr)
 318 {
 319         int left;
 320         long long val;
 321         struct state_list *slist;
 322         struct sm_state *tmp;
 323         int boundary;
 324
 325         if (!expr || expr->type != EXPR_COMPARE)
 326                 return;
 327         if (get_implied_value(expr->left, &val))
 328                 left = 1;
 329         else if (get_implied_value(expr->right, &val))
 330                 left = 0;
 331         else
 332                 return;
 333
 334         if (left)
 335                 slist = get_possible_states_expr(my_used_id, expr->right);
 336         else
 337                 slist = get_possible_states_expr(my_used_id, expr->left);
 338         if (!slist)
 339                 return;
 340         FOR_EACH_PTR(slist, tmp) {
 341                 if (tmp->state == &merged)
 342                         continue;
 343                 boundary = (int)tmp->state->data;
 344                 boundary -= val;
 345                 if (boundary < 1 && boundary > -1) {
 346                         char *name;
 347
 348                         name = get_variable_from_expr((left ? expr->right : expr->left), NULL);
 349                         sm_msg("error: testing array offset '%s' after use.", name);
 350                         return;
 351                 }
 352         } END_FOR_EACH_PTR(tmp);
 353 }
 354
 355 static struct expression *strip_ampersands(struct expression *expr)
 356 {
 357         struct symbol *type;
 358
 359         if (expr->type != EXPR_PREOP)
 360                 return expr;
 361         if (expr->op != '&')
 362                 return expr;
 363         type = get_type(expr->unop);
 364         if (!type || type->type != SYM_ARRAY)
 365                 return expr;
 366         return expr->unop;
 367 }
 368
 369 static void match_array_assignment(struct expression *expr)
 370 {
 371         struct expression *left;
 372         struct expression *right;
 373         int array_size;
 374
 375         if (expr->op != '=')
 376                 return;
 377         left = strip_expr(expr->left);
 378         right = strip_expr(expr->right);
 379         right = strip_ampersands(right);
 380         array_size = get_array_size_bytes(right);
 381         if (array_size)
 382                 set_state_expr(my_size_id, left, alloc_my_state(array_size));
 383 }
 384
 385 static void match_malloc(const char *fn, struct expression *expr, void *unused)
 386 {
 387         struct expression *right;
 388         struct expression *arg;
 389         long long bytes;
 390
 391         right = strip_expr(expr->right);
 392         arg = get_argument_from_call_expr(right->args, 0);
 393         if (!get_implied_value(arg, &bytes))
 394                 return;
 395         set_state_expr(my_size_id, expr->left, alloc_my_state(bytes));
 396 }
 397
 398 static void match_calloc(const char *fn, struct expression *expr, void *unused)
 399 {
 400         struct expression *right;
 401         struct expression *arg;
 402         long long elements;
 403         long long size;
 404
 405         right = strip_expr(expr->right);
 406         arg = get_argument_from_call_expr(right->args, 0);
 407         if (!get_implied_value(arg, &elements))
 408                 return;
 409         arg = get_argument_from_call_expr(right->args, 1);
 410         if (!get_implied_value(arg, &size))
 411                 return;
 412         set_state_expr(my_size_id, expr->left, alloc_my_state(elements * size));
 413 }
 414
 415 static void match_strcpy(const char *fn, struct expression *expr, void *unused)
 416 {
 417         struct expression *dest;
 418         struct expression *data;
 419         char *dest_name = NULL;
 420         char *data_name = NULL;
 421         int dest_size;
 422         int data_size;
 423
 424         dest = get_argument_from_call_expr(expr->args, 0);
 425         data = get_argument_from_call_expr(expr->args, 1);
 426         dest_size = get_array_size_bytes(dest);
 427         data_size = get_array_size_bytes(data);
 428         if (!dest_size || !data_size)
 429                 return;
 430         if (dest_size >= data_size)
 431                 return;
 432
 433         dest_name = get_variable_from_expr_complex(dest, NULL);
 434         data_name = get_variable_from_expr_complex(data, NULL);
 435         sm_msg("error: %s() '%s' too large for '%s' (%d vs %d)",
 436                 fn, data_name, dest_name, data_size, dest_size);
 437         free_string(dest_name);
 438         free_string(data_name);
 439 }
 440
 441 static void match_limited(const char *fn, struct expression *expr, void *_limiter)
 442 {
 443         struct limiter *limiter = (struct limiter *)_limiter;
 444         struct expression *dest;
 445         struct expression *data;
 446         char *dest_name = NULL;
 447         long long needed;
 448         int has;
 449
 450         dest = get_argument_from_call_expr(expr->args, limiter->buf_arg);
 451         data = get_argument_from_call_expr(expr->args, limiter->limit_arg);
 452         if (!get_fuzzy_max(data, &needed))
 453                 return;
 454         has = get_array_size_bytes(dest);
 455         if (!has)
 456                 return;
 457         if (has >= needed)
 458                 return;
 459
 460         dest_name = get_variable_from_expr_complex(dest, NULL);
 461         sm_msg("error: %s() '%s' too small (%d vs %lld)", fn, dest_name, has, needed);
 462         free_string(dest_name);
 463 }
 464
 465 static void match_array_func(const char *fn, struct expression *expr, void *info)
 466 {
 467         struct bound *bound_info = (struct bound *)info;
 468         struct expression *arg;
 469         long long offset;
 470
 471         arg = get_argument_from_call_expr(expr->args, bound_info->param);
 472         if (!get_implied_value(arg, &offset))
 473                 return;
 474         if (offset >= bound_info->size)
 475                 sm_msg("error: buffer overflow calling %s. param %d.  %lld >= %d",
 476                         fn, bound_info->param, offset, bound_info->size);
 477 }
 478
 479 static void register_array_funcs(void)
 480 {
 481         struct token *token;
 482         const char *func;
 483         struct bound *bound_info = NULL;
 484
 485         token = get_tokens_file("kernel.array_bounds");
 486         if (!token)
 487                 return;
 488         if (token_type(token) != TOKEN_STREAMBEGIN)
 489                 return;
 490         token = token->next;
 491         while (token_type(token) != TOKEN_STREAMEND) {
 492                 bound_info = malloc(sizeof(*bound_info));
 493                 if (token_type(token) != TOKEN_IDENT)
 494                         break;
 495                 func = show_ident(token->ident);
 496                 token = token->next;
 497                 if (token_type(token) != TOKEN_NUMBER)
 498                         break;
 499                 bound_info->param = atoi(token->number);
 500                 token = token->next;
 501                 if (token_type(token) != TOKEN_NUMBER)
 502                         break;
 503                 bound_info->size = atoi(token->number);
 504                 add_function_hook(func, &match_array_func, bound_info);
 505                 token = token->next;
 506         }
 507         if (token_type(token) != TOKEN_STREAMEND)
 508                 free(bound_info);
 509         clear_token_alloc();
 510 }
 511
 512 void check_overflow(int id)
 513 {
 514         my_size_id = id;
 515         add_hook(&match_function_def, FUNC_DEF_HOOK);
 516         add_hook(&array_check, OP_HOOK);
 517         add_hook(&match_array_assignment, ASSIGNMENT_HOOK);
 518         add_hook(&match_condition, CONDITION_HOOK);
 519         add_function_assign_hook("malloc", &match_malloc, NULL);
 520         add_function_assign_hook("calloc", &match_calloc, NULL);
 521         add_function_hook("strcpy", &match_strcpy, NULL);
 522         add_function_hook("strncpy", &match_limited, &b0_l2);
 523         add_function_hook("memset", &match_limited, &b0_l2);
 524         if (option_project == PROJ_KERNEL) {
 525                 add_function_assign_hook("kmalloc", &match_malloc, NULL);
 526                 add_function_assign_hook("kzalloc", &match_malloc, NULL);
 527                 add_function_assign_hook("vmalloc", &match_malloc, NULL);
 528                 add_function_assign_hook("__vmalloc", &match_malloc, NULL);
 529                 add_function_assign_hook("kcalloc", &match_calloc, NULL);
 530                 add_function_assign_hook("drm_malloc_ab", &match_calloc, NULL);
 531                 add_function_assign_hook("drm_calloc_large", &match_calloc, NULL);
 532                 add_function_hook("copy_to_user", &match_limited, &b0_l2);
 533                 add_function_hook("copy_to_user", &match_limited, &b1_l2);
 534                 add_function_hook("_copy_to_user", &match_limited, &b0_l2);
 535                 add_function_hook("_copy_to_user", &match_limited, &b1_l2);
 536                 add_function_hook("__copy_to_user", &match_limited, &b0_l2);
 537                 add_function_hook("__copy_to_user", &match_limited, &b1_l2);
 538                 add_function_hook("copy_from_user", &match_limited, &b0_l2);
 539                 add_function_hook("copy_from_user", &match_limited, &b1_l2);
 540                 add_function_hook("_copy_from_user", &match_limited, &b0_l2);
 541                 add_function_hook("_copy_from_user", &match_limited, &b1_l2);
 542                 add_function_hook("__copy_from_user", &match_limited, &b0_l2);
 543                 add_function_hook("__copy_from_user", &match_limited, &b1_l2);
 544                 add_function_hook("__builtin_memset", &match_limited, &b0_l2);
 545         }
 546         register_array_funcs();
 547 }
 548
 549 void register_check_overflow_again(int id)
 550 {
 551         my_used_id = id;
 552 }