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