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