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 int get_array_size(struct expression *expr)
 151 {
 152         struct symbol *tmp;
 153         struct smatch_state *state;
 154         int ret = 0;
 155
 156         if (expr->type == EXPR_STRING)
 157                 return expr->string->length;
 158
 159         tmp = get_type(expr);
 160         if (!tmp)
 161                 return 0;
 162
 163         if (tmp->type == SYM_ARRAY) {
 164                 ret = get_expression_value(tmp->array_size);
 165                 if (ret == 1 && is_last_struct_member(expr))
 166                         return 0;
 167                 if (ret)
 168                         return ret;
 169         }
 170
 171         if (expr->type == EXPR_SYMBOL && expr->symbol->initializer) {
 172                 if (expr->symbol->initializer != expr) /* int a = a; */
 173                         return get_initializer_size(expr->symbol->initializer);
 174         }
 175         state = get_state_expr(my_size_id, expr);
 176         if (!state || !state->data)
 177                 return 0;
 178         if (tmp->type == SYM_PTR)
 179                 tmp = get_base_type(tmp);
 180         if (!tmp->ctype.alignment)
 181                 return 0;
 182         ret = *(int *)state->data / tmp->ctype.alignment;
 183         return ret;
 184 }
 185
 186 static int get_array_size_bytes(struct expression *expr)
 187 {
 188         struct symbol *tmp;
 189         int array_size;
 190
 191         if (expr->type == EXPR_STRING)
 192                 return expr->string->length;
 193
 194         tmp = get_type(expr);
 195         if (!tmp)
 196                 return 0;
 197         array_size = get_array_size(expr);
 198         return array_size * tmp->ctype.alignment;
 199 }
 200
 201 static int definitely_just_used_as_limiter(struct expression *array, struct expression *offset)
 202 {
 203         long long val;
 204         struct expression *tmp;
 205         int step = 0;
 206         int dot_ops = 0;
 207
 208         if (!get_value(offset, &val))
 209                 return 0;
 210         if (get_array_size(array) != val)
 211                 return 0;
 212
 213         FOR_EACH_PTR_REVERSE(big_expression_stack, tmp) {
 214                 if (step == 0) {
 215                         step = 1;
 216                         continue;
 217                 }
 218                 if (tmp->type == EXPR_PREOP && tmp->op == '(')
 219                         continue;
 220                 if (tmp->op == '.' && !dot_ops++)
 221                         continue;
 222                 if (step == 1 && tmp->op == '&') {
 223                         step = 2;
 224                         continue;
 225                 }
 226                 if (step == 2 && tmp->type == EXPR_COMPARE)
 227                         return 1;
 228                 return 0;
 229         } END_FOR_EACH_PTR_REVERSE(tmp);
 230         return 0;
 231 }
 232
 233 static void array_check(struct expression *expr)
 234 {
 235         struct expression *array_expr;
 236         int array_size;
 237         struct expression *offset;
 238         long long max;
 239         char *name;
 240
 241         expr = strip_expr(expr);
 242         if (!is_array(expr))
 243                 return;
 244
 245         array_expr = get_array_name(expr);
 246         array_size = get_array_size(array_expr);
 247         if (!array_size)
 248                 return;
 249
 250         offset = get_array_offset(expr);
 251         if (!get_fuzzy_max(offset, &max)) {
 252                 if (getting_address())
 253                         return;
 254                 set_state_expr(my_used_id, offset, alloc_state_num(array_size));
 255                 add_modification_hook_expr(my_used_id, offset, &delete, NULL);
 256                 print_args(offset, array_size);
 257         } else if (array_size <= max) {
 258                 const char *level = "error";
 259
 260                 if (getting_address())
 261                         level = "warn";
 262
 263                 if (definitely_just_used_as_limiter(array_expr, offset))
 264                         return;
 265
 266                 name = get_variable_from_expr_complex(array_expr, NULL);
 267                 /* Blast.  Smatch can't figure out glibc's strcmp __strcmp_cg()
 268                  * so it prints an error every time you compare to a string
 269                  * literal array with 4 or less chars.
 270                  */
 271                 if (name && strcmp(name, "__s1") && strcmp(name, "__s2")) {
 272                         sm_msg("%s: buffer overflow '%s' %d <= %lld",
 273                                 level, name, array_size, max);
 274                 }
 275                 free_string(name);
 276         }
 277 }
 278
 279 static void match_condition(struct expression *expr)
 280 {
 281         int left;
 282         long long val;
 283         struct state_list *slist;
 284         struct sm_state *tmp;
 285         int boundary;
 286
 287         if (!expr || expr->type != EXPR_COMPARE)
 288                 return;
 289         if (get_implied_value(expr->left, &val))
 290                 left = 1;
 291         else if (get_implied_value(expr->right, &val))
 292                 left = 0;
 293         else
 294                 return;
 295
 296         if (left)
 297                 slist = get_possible_states_expr(my_used_id, expr->right);
 298         else
 299                 slist = get_possible_states_expr(my_used_id, expr->left);
 300         if (!slist)
 301                 return;
 302         FOR_EACH_PTR(slist, tmp) {
 303                 if (tmp->state == &merged)
 304                         continue;
 305                 boundary = (int)tmp->state->data;
 306                 boundary -= val;
 307                 if (boundary < 1 && boundary > -1) {
 308                         char *name;
 309
 310                         name = get_variable_from_expr((left ? expr->right : expr->left), NULL);
 311                         sm_msg("error: testing array offset '%s' after use.", name);
 312                         return;
 313                 }
 314         } END_FOR_EACH_PTR(tmp);
 315 }
 316
 317 static void match_string_assignment(struct expression *expr)
 318 {
 319         struct expression *left;
 320         struct expression *right;
 321
 322         left = strip_expr(expr->left);
 323         right = strip_expr(expr->right);
 324         if (right->type != EXPR_STRING || !right->string)
 325                 return;
 326         set_state_expr(my_size_id, left, alloc_my_state(right->string->length));
 327 }
 328
 329 static void match_array_assignment(struct expression *expr)
 330 {
 331         struct expression *left;
 332         struct expression *right;
 333         struct symbol *left_type;
 334         int array_size;
 335
 336         if (expr->op != '=')
 337                 return;
 338         left = strip_expr(expr->left);
 339         left_type = get_type(left);
 340         if (!left_type || left_type->type != SYM_PTR)
 341                 return;
 342         left_type = get_base_type(left_type);
 343         if (!left_type)
 344                 return;
 345         right = strip_expr(expr->right);
 346         array_size = get_array_size(right);
 347         if (array_size)
 348                 set_state_expr(my_size_id, left,
 349                         alloc_my_state(array_size * left_type->ctype.alignment));
 350 }
 351
 352 static void match_malloc(const char *fn, struct expression *expr, void *unused)
 353 {
 354         struct expression *right;
 355         struct expression *arg;
 356         long long bytes;
 357
 358         right = strip_expr(expr->right);
 359         arg = get_argument_from_call_expr(right->args, 0);
 360         if (!get_implied_value(arg, &bytes))
 361                 return;
 362         set_state_expr(my_size_id, expr->left, alloc_my_state(bytes));
 363 }
 364
 365 static void match_strcpy(const char *fn, struct expression *expr, void *unused)
 366 {
 367         struct expression *dest;
 368         struct expression *data;
 369         char *dest_name = NULL;
 370         char *data_name = NULL;
 371         int dest_size;
 372         int data_size;
 373
 374         dest = get_argument_from_call_expr(expr->args, 0);
 375         data = get_argument_from_call_expr(expr->args, 1);
 376         dest_size = get_array_size_bytes(dest);
 377         data_size = get_array_size_bytes(data);
 378         if (!dest_size || !data_size)
 379                 return;
 380         if (dest_size >= data_size)
 381                 return;
 382
 383         dest_name = get_variable_from_expr_complex(dest, NULL);
 384         data_name = get_variable_from_expr_complex(data, NULL);
 385         sm_msg("error: %s() %s too large for %s (%d vs %d)",
 386                 fn, data_name, dest_name, data_size, dest_size);
 387         free_string(dest_name);
 388         free_string(data_name);
 389 }
 390
 391 static void match_limitted(const char *fn, struct expression *expr, void *limit_arg)
 392 {
 393         struct expression *dest;
 394         struct expression *data;
 395         char *dest_name = NULL;
 396         long long needed;
 397         int has;
 398
 399         dest = get_argument_from_call_expr(expr->args, 0);
 400         data = get_argument_from_call_expr(expr->args, PTR_INT(limit_arg));
 401         if (!get_fuzzy_max(data, &needed))
 402                 return;
 403         has = get_array_size_bytes(dest);
 404         if (!has)
 405                 return;
 406         if (has >= needed)
 407                 return;
 408
 409         dest_name = get_variable_from_expr_complex(dest, NULL);
 410         sm_msg("error: %s() %s too small (%d vs %lld)", fn, dest_name, has, needed);
 411         free_string(dest_name);
 412 }
 413
 414 static void match_array_func(const char *fn, struct expression *expr, void *info)
 415 {
 416         struct bound *bound_info = (struct bound *)info;
 417         struct expression *arg;
 418         long long offset;
 419
 420         arg = get_argument_from_call_expr(expr->args, bound_info->param);
 421         if (!get_implied_value(arg, &offset))
 422                 return;
 423         if (offset >= bound_info->size)
 424                 sm_msg("error: buffer overflow calling %s. param %d.  %lld >= %d",
 425                         fn, bound_info->param, offset, bound_info->size);
 426 }
 427
 428 static void register_array_funcs(void)
 429 {
 430         struct token *token;
 431         const char *func;
 432         struct bound *bound_info;
 433
 434         token = get_tokens_file("kernel.array_bounds");
 435         if (!token)
 436                 return;
 437         if (token_type(token) != TOKEN_STREAMBEGIN)
 438                 return;
 439         token = token->next;
 440         while (token_type(token) != TOKEN_STREAMEND) {
 441                 bound_info = malloc(sizeof(*bound_info));
 442                 if (token_type(token) != TOKEN_IDENT)
 443                         return;
 444                 func = show_ident(token->ident);
 445                 token = token->next;
 446                 if (token_type(token) != TOKEN_NUMBER)
 447                         return;
 448                 bound_info->param = atoi(token->number);
 449                 token = token->next;
 450                 if (token_type(token) != TOKEN_NUMBER)
 451                         return;
 452                 bound_info->size = atoi(token->number);
 453                 add_function_hook(func, &match_array_func, bound_info);
 454                 token = token->next;
 455         }
 456         clear_token_alloc();
 457 }
 458
 459 void check_overflow(int id)
 460 {
 461         my_size_id = id;
 462         add_hook(&match_function_def, FUNC_DEF_HOOK);
 463         add_hook(&array_check, OP_HOOK);
 464         add_hook(&match_string_assignment, ASSIGNMENT_HOOK);
 465         add_hook(&match_array_assignment, ASSIGNMENT_HOOK);
 466         add_hook(&match_condition, CONDITION_HOOK);
 467         add_function_assign_hook("malloc", &match_malloc, NULL);
 468         add_function_hook("strcpy", &match_strcpy, NULL);
 469         add_function_hook("strncpy", &match_limitted, (void *)2);
 470         if (option_project == PROJ_KERNEL) {
 471                 add_function_assign_hook("kmalloc", &match_malloc, NULL);
 472                 add_function_assign_hook("kzalloc", &match_malloc, NULL);
 473                 add_function_assign_hook("vmalloc", &match_malloc, NULL);
 474                 add_function_hook("copy_to_user", &match_limitted, (void *)2);
 475                 add_function_hook("copy_from_user", &match_limitted, (void *)2);
 476         }
 477         register_array_funcs();
 478 }
 479
 480 void register_check_overflow_again(int id)
 481 {
 482         my_used_id = id;
 483 }