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