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 = malloc(sizeof(*state));
  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_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                 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 struct expression *strip_ampersands(struct expression *expr)
 364 {
 365         struct symbol *type;
 366
 367         if (expr->type != EXPR_PREOP)
 368                 return expr;
 369         if (expr->op != '&')
 370                 return expr;
 371         type = get_type(expr->unop);
 372         if (!type || type->type != SYM_ARRAY)
 373                 return expr;
 374         return expr->unop;
 375 }
 376
 377 static void match_array_assignment(struct expression *expr)
 378 {
 379         struct expression *left;
 380         struct expression *right;
 381         int array_size;
 382
 383         if (expr->op != '=')
 384                 return;
 385         left = strip_expr(expr->left);
 386         right = strip_expr(expr->right);
 387         right = strip_ampersands(right);
 388         array_size = get_array_size_bytes(right);
 389         if (array_size)
 390                 set_state_expr(my_size_id, left, alloc_my_state(array_size));
 391 }
 392
 393 static void match_malloc(const char *fn, struct expression *expr, void *unused)
 394 {
 395         struct expression *right;
 396         struct expression *arg;
 397         long long bytes;
 398
 399         right = strip_expr(expr->right);
 400         arg = get_argument_from_call_expr(right->args, 0);
 401         if (!get_implied_value(arg, &bytes))
 402                 return;
 403         set_state_expr(my_size_id, expr->left, alloc_my_state(bytes));
 404 }
 405
 406 static void match_strcpy(const char *fn, struct expression *expr, void *unused)
 407 {
 408         struct expression *dest;
 409         struct expression *data;
 410         char *dest_name = NULL;
 411         char *data_name = NULL;
 412         int dest_size;
 413         int data_size;
 414
 415         dest = get_argument_from_call_expr(expr->args, 0);
 416         data = get_argument_from_call_expr(expr->args, 1);
 417         dest_size = get_array_size_bytes(dest);
 418         data_size = get_array_size_bytes(data);
 419         if (!dest_size || !data_size)
 420                 return;
 421         if (dest_size >= data_size)
 422                 return;
 423
 424         dest_name = get_variable_from_expr_complex(dest, NULL);
 425         data_name = get_variable_from_expr_complex(data, NULL);
 426         sm_msg("error: %s() %s too large for %s (%d vs %d)",
 427                 fn, data_name, dest_name, data_size, dest_size);
 428         free_string(dest_name);
 429         free_string(data_name);
 430 }
 431
 432 static void match_limitted(const char *fn, struct expression *expr, void *limit_arg)
 433 {
 434         struct expression *dest;
 435         struct expression *data;
 436         char *dest_name = NULL;
 437         long long needed;
 438         int has;
 439
 440         dest = get_argument_from_call_expr(expr->args, 0);
 441         data = get_argument_from_call_expr(expr->args, PTR_INT(limit_arg));
 442         if (!get_fuzzy_max(data, &needed))
 443                 return;
 444         has = get_array_size_bytes(dest);
 445         if (!has)
 446                 return;
 447         if (has >= needed)
 448                 return;
 449
 450         dest_name = get_variable_from_expr_complex(dest, NULL);
 451         sm_msg("error: %s() %s too small (%d vs %lld)", fn, dest_name, has, needed);
 452         free_string(dest_name);
 453 }
 454
 455 static void match_array_func(const char *fn, struct expression *expr, void *info)
 456 {
 457         struct bound *bound_info = (struct bound *)info;
 458         struct expression *arg;
 459         long long offset;
 460
 461         arg = get_argument_from_call_expr(expr->args, bound_info->param);
 462         if (!get_implied_value(arg, &offset))
 463                 return;
 464         if (offset >= bound_info->size)
 465                 sm_msg("error: buffer overflow calling %s. param %d.  %lld >= %d",
 466                         fn, bound_info->param, offset, bound_info->size);
 467 }
 468
 469 static void register_array_funcs(void)
 470 {
 471         struct token *token;
 472         const char *func;
 473         struct bound *bound_info;
 474
 475         token = get_tokens_file("kernel.array_bounds");
 476         if (!token)
 477                 return;
 478         if (token_type(token) != TOKEN_STREAMBEGIN)
 479                 return;
 480         token = token->next;
 481         while (token_type(token) != TOKEN_STREAMEND) {
 482                 bound_info = malloc(sizeof(*bound_info));
 483                 if (token_type(token) != TOKEN_IDENT)
 484                         return;
 485                 func = show_ident(token->ident);
 486                 token = token->next;
 487                 if (token_type(token) != TOKEN_NUMBER)
 488                         return;
 489                 bound_info->param = atoi(token->number);
 490                 token = token->next;
 491                 if (token_type(token) != TOKEN_NUMBER)
 492                         return;
 493                 bound_info->size = atoi(token->number);
 494                 add_function_hook(func, &match_array_func, bound_info);
 495                 token = token->next;
 496         }
 497         clear_token_alloc();
 498 }
 499
 500 void check_overflow(int id)
 501 {
 502         my_size_id = id;
 503         add_hook(&match_function_def, FUNC_DEF_HOOK);
 504         add_hook(&array_check, OP_HOOK);
 505         add_hook(&match_array_assignment, ASSIGNMENT_HOOK);
 506         add_hook(&match_condition, CONDITION_HOOK);
 507         add_function_assign_hook("malloc", &match_malloc, NULL);
 508         add_function_hook("strcpy", &match_strcpy, NULL);
 509         add_function_hook("strncpy", &match_limitted, (void *)2);
 510         add_function_hook("memset", &match_limitted, (void *)2);
 511         if (option_project == PROJ_KERNEL) {
 512                 add_function_assign_hook("kmalloc", &match_malloc, NULL);
 513                 add_function_assign_hook("kzalloc", &match_malloc, NULL);
 514                 add_function_assign_hook("vmalloc", &match_malloc, NULL);
 515                 add_function_hook("copy_to_user", &match_limitted, (void *)2);
 516                 add_function_hook("copy_from_user", &match_limitted, (void *)2);
 517                 add_function_hook("__builtin_memset", &match_limitted, (void *)2);
 518         }
 519         register_array_funcs();
 520 }
 521
 522 void register_check_overflow_again(int id)
 523 {
 524         my_used_id = id;
 525 }