check_overflow.c

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