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