check_overflow.c

   1 /*
   2  * Copyright (C) 2010 Dan Carpenter.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License
   6  * as published by the Free Software Foundation; either version 2
   7  * of the License, or (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
  16  */
  17
  18 #include <stdlib.h>
  19 #include "parse.h"
  20 #include "smatch.h"
  21 #include "smatch_slist.h"
  22 #include "smatch_extra.h"
  23
  24 struct bound {
  25         int param;
  26         int size;
  27 };
  28
  29 /*
  30  * This check has two smatch IDs.
  31  * my_used_id - keeps a record of array offsets that have been used.
  32  *              If the code checks that they are within bounds later on,
  33  *              we complain about using an array offset before checking
  34  *              that it is within bounds.
  35  */
  36 static int my_used_id;
  37
  38 static struct symbol *this_func;
  39
  40 static void match_function_def(struct symbol *sym)
  41 {
  42         this_func = sym;
  43 }
  44
  45 struct limiter {
  46         int buf_arg;
  47         int limit_arg;
  48 };
  49 static struct limiter b0_l2 = {0, 2};
  50 static struct limiter b1_l2 = {1, 2};
  51
  52 static void delete(struct sm_state *sm, struct expression *mod_expr)
  53 {
  54         set_state(my_used_id, sm->name, sm->sym, &undefined);
  55 }
  56
  57 static int definitely_just_used_as_limiter(struct expression *array, struct expression *offset)
  58 {
  59         sval_t sval;
  60         struct expression *tmp;
  61         int step = 0;
  62         int dot_ops = 0;
  63
  64         if (!get_implied_value(offset, &sval))
  65                 return 0;
  66         if (get_array_size(array) != sval.value)
  67                 return 0;
  68
  69         FOR_EACH_PTR_REVERSE(big_expression_stack, tmp) {
  70                 if (step == 0) {
  71                         step = 1;
  72                         continue;
  73                 }
  74                 if (tmp->type == EXPR_PREOP && tmp->op == '(')
  75                         continue;
  76                 if (tmp->op == '.' && !dot_ops++)
  77                         continue;
  78                 if (step == 1 && tmp->op == '&') {
  79                         step = 2;
  80                         continue;
  81                 }
  82                 if (step == 2 && tmp->type == EXPR_COMPARE)
  83                         return 1;
  84                 if (step == 2 && tmp->type == EXPR_ASSIGNMENT)
  85                         return 1;
  86                 return 0;
  87         } END_FOR_EACH_PTR_REVERSE(tmp);
  88         return 0;
  89 }
  90
  91 static int get_the_max(struct expression *expr, sval_t *sval)
  92 {
  93         if (get_hard_max(expr, sval))
  94                 return 1;
  95         if (!option_spammy)
  96                 return 0;
  97         if (get_fuzzy_max(expr, sval))
  98                 return 1;
  99         if (is_user_data(expr))
 100                 return get_absolute_max(expr, sval);
 101         return 0;
 102 }
 103
 104 static int common_false_positives(struct expression *array, char *name, sval_t max)
 105 {
 106         if (!name)
 107                 return 0;
 108
 109         /* Smatch can't figure out glibc's strcmp __strcmp_cg()
 110          * so it prints an error every time you compare to a string
 111          * literal array with 4 or less chars.
 112          */
 113         if (strcmp(name, "__s1") == 0 || strcmp(name, "__s2") == 0)
 114                 return 1;
 115
 116         /* Ugh... People are saying that Smatch still barfs on glibc strcmp()
 117          * functions.
 118          */
 119         if (array && array->type == EXPR_STRING) {
 120                 char *macro;
 121
 122                 if (max.value == array->string->length)
 123                         return 1;
 124
 125                 macro = get_macro_name(array->pos);
 126                 if (macro &&
 127                     (strcmp(macro, "strcmp") == 0 ||
 128                      strcmp(macro, "strncmp") == 0))
 129                     return 1;
 130         }
 131
 132         /*
 133          * passing WORK_CPU_UNBOUND is idiomatic but Smatch doesn't understand
 134          * how it's used so it causes a bunch of false positives.
 135          */
 136         if (option_project == PROJ_KERNEL &&
 137             strcmp(name, "__per_cpu_offset") == 0)
 138                 return 1;
 139         return 0;
 140 }
 141
 142 static void array_check(struct expression *expr)
 143 {
 144         struct expression *array_expr;
 145         int array_size;
 146         struct expression *offset;
 147         sval_t max;
 148         char *name;
 149
 150         expr = strip_expr(expr);
 151         if (!is_array(expr))
 152                 return;
 153
 154         array_expr = get_array_base(expr);
 155         array_size = get_array_size(array_expr);
 156         if (!array_size || array_size == 1)
 157                 return;
 158
 159         offset = get_array_offset(expr);
 160         if (!get_the_max(offset, &max)) {
 161                 if (getting_address())
 162                         return;
 163                 if (is_capped(offset))
 164                         return;
 165                 set_state_expr(my_used_id, offset, alloc_state_num(array_size));
 166         } else if (array_size <= max.value) {
 167                 const char *level = "error";
 168
 169                 if (getting_address())
 170                         level = "warn";
 171
 172                 if (definitely_just_used_as_limiter(array_expr, offset))
 173                         return;
 174
 175                 array_expr = strip_expr(array_expr);
 176                 name = expr_to_str(array_expr);
 177                 if (!common_false_positives(array_expr, name, max)) {
 178                         sm_msg("%s: buffer overflow '%s' %d <= %s",
 179                                 level, name, array_size, sval_to_str(max));
 180                 }
 181                 free_string(name);
 182         }
 183 }
 184
 185 static void match_condition(struct expression *expr)
 186 {
 187         int left;
 188         sval_t sval;
 189         struct state_list *slist;
 190         struct sm_state *tmp;
 191         int boundary;
 192
 193         if (!expr || expr->type != EXPR_COMPARE)
 194                 return;
 195         if (get_macro_name(expr->pos))
 196                 return;
 197         if (get_implied_value(expr->left, &sval))
 198                 left = 1;
 199         else if (get_implied_value(expr->right, &sval))
 200                 left = 0;
 201         else
 202                 return;
 203
 204         if (left)
 205                 slist = get_possible_states_expr(my_used_id, expr->right);
 206         else
 207                 slist = get_possible_states_expr(my_used_id, expr->left);
 208         if (!slist)
 209                 return;
 210         FOR_EACH_PTR(slist, tmp) {
 211                 if (tmp->state == &merged || tmp->state == &undefined)
 212                         continue;
 213                 boundary = PTR_INT(tmp->state->data);
 214                 boundary -= sval.value;
 215                 if (boundary < 1 && boundary > -1) {
 216                         char *name;
 217
 218                         name = expr_to_var(left ? expr->right : expr->left);
 219                         sm_msg("error: testing array offset '%s' after use.", name);
 220                         return;
 221                 }
 222         } END_FOR_EACH_PTR(tmp);
 223 }
 224
 225 static void match_strcpy(const char *fn, struct expression *expr, void *unused)
 226 {
 227         struct expression *dest;
 228         struct expression *data;
 229         char *dest_name = NULL;
 230         char *data_name = NULL;
 231         int dest_size;
 232         int data_size;
 233
 234         dest = get_argument_from_call_expr(expr->args, 0);
 235         data = get_argument_from_call_expr(expr->args, 1);
 236         dest_size = get_array_size_bytes(dest);
 237         if (!dest_size)
 238                 return;
 239
 240         data_size = get_size_from_strlen(data);
 241         if (!data_size)
 242                 data_size = get_array_size_bytes(data);
 243
 244         /* If the size of both arrays is known and the destination
 245          * buffer is larger than the source buffer, we're okay.
 246          */
 247         if (data_size && dest_size >= data_size)
 248                 return;
 249
 250         dest_name = expr_to_str(dest);
 251         data_name = expr_to_str(data);
 252
 253         if (data_size)
 254                 sm_msg("error: %s() '%s' too large for '%s' (%d vs %d)",
 255                         fn, data_name, dest_name, data_size, dest_size);
 256         else if (option_spammy)
 257                 sm_msg("warn: %s() '%s' of unknown size might be too large for '%s'",
 258                         fn, data_name, dest_name);
 259
 260         free_string(dest_name);
 261         free_string(data_name);
 262 }
 263
 264 static void match_snprintf(const char *fn, struct expression *expr, void *unused)
 265 {
 266         struct expression *dest;
 267         struct expression *dest_size_expr;
 268         struct expression *format_string;
 269         struct expression *data;
 270         char *data_name = NULL;
 271         int dest_size;
 272         sval_t limit_size;
 273         char *format;
 274         int data_size;
 275
 276         dest = get_argument_from_call_expr(expr->args, 0);
 277         dest_size_expr = get_argument_from_call_expr(expr->args, 1);
 278         format_string = get_argument_from_call_expr(expr->args, 2);
 279         data = get_argument_from_call_expr(expr->args, 3);
 280
 281         dest_size = get_array_size_bytes(dest);
 282         if (!get_implied_value(dest_size_expr, &limit_size))
 283                 return;
 284         if (dest_size && dest_size < limit_size.value)
 285                 sm_msg("error: snprintf() is printing too much %s vs %d",
 286                        sval_to_str(limit_size), dest_size);
 287         format = expr_to_var(format_string);
 288         if (!format)
 289                 return;
 290         if (strcmp(format, "\"%s\""))
 291                 goto free;
 292         data_name = expr_to_str(data);
 293         data_size = get_size_from_strlen(data);
 294         if (!data_size)
 295                 data_size = get_array_size_bytes(data);
 296         if (limit_size.value < data_size)
 297                 sm_msg("error: snprintf() chops off the last chars of '%s': %d vs %s",
 298                        data_name, data_size, sval_to_str(limit_size));
 299 free:
 300         free_string(data_name);
 301         free_string(format);
 302 }
 303
 304 static void match_sprintf(const char *fn, struct expression *expr, void *unused)
 305 {
 306         struct expression *dest;
 307         struct expression *format_string;
 308         struct expression *data;
 309         char *data_name = NULL;
 310         int dest_size;
 311         char *format;
 312         int data_size;
 313
 314         dest = get_argument_from_call_expr(expr->args, 0);
 315         format_string = get_argument_from_call_expr(expr->args, 1);
 316         data = get_argument_from_call_expr(expr->args, 2);
 317
 318         dest_size = get_array_size_bytes(dest);
 319         if (!dest_size)
 320                 return;
 321         format = expr_to_var(format_string);
 322         if (!format)
 323                 return;
 324         if (strcmp(format, "\"%s\""))
 325                 goto free;
 326         data_name = expr_to_str(data);
 327         data_size = get_size_from_strlen(data);
 328         if (!data_size)
 329                 data_size = get_array_size_bytes(data);
 330         if (dest_size < data_size)
 331                 sm_msg("error: sprintf() copies too much data from '%s': %d vs %d",
 332                        data_name, data_size, dest_size);
 333 free:
 334         free_string(data_name);
 335         free_string(format);
 336 }
 337
 338 static void match_limited(const char *fn, struct expression *expr, void *_limiter)
 339 {
 340         struct limiter *limiter = (struct limiter *)_limiter;
 341         struct expression *dest;
 342         struct expression *data;
 343         char *dest_name = NULL;
 344         sval_t needed;
 345         int has;
 346
 347         dest = get_argument_from_call_expr(expr->args, limiter->buf_arg);
 348         data = get_argument_from_call_expr(expr->args, limiter->limit_arg);
 349         if (!get_the_max(data, &needed))
 350                 return;
 351         has = get_array_size_bytes_max(dest);
 352         if (!has)
 353                 return;
 354         if (has >= needed.value)
 355                 return;
 356
 357         dest_name = expr_to_str(dest);
 358         sm_msg("error: %s() '%s' too small (%d vs %s)", fn, dest_name, has, sval_to_str(needed));
 359         free_string(dest_name);
 360 }
 361
 362 static void db_returns_buf_size(struct expression *expr, int param, char *unused, char *math)
 363 {
 364         struct expression *call;
 365         struct symbol *left_type, *right_type;
 366         int bytes;
 367         sval_t sval;
 368
 369         if (expr->type != EXPR_ASSIGNMENT)
 370                 return;
 371         right_type = get_pointer_type(expr->right);
 372         if (!right_type || type_bits(right_type) != -1)
 373                 return;
 374
 375         call = strip_expr(expr->right);
 376         left_type = get_pointer_type(expr->left);
 377
 378         if (!parse_call_math(call, math, &sval) || sval.value == 0)
 379                 return;
 380         if (!left_type)
 381                 return;
 382         bytes = type_bytes(left_type);
 383         if (bytes <= 0)
 384                 return;
 385         if (sval.uvalue >= bytes)
 386                 return;
 387         sm_msg("error: not allocating enough data %d vs %s", bytes, sval_to_str(sval));
 388 }
 389
 390 static void register_funcs_from_file(void)
 391 {
 392         char name[256];
 393         struct token *token;
 394         const char *func;
 395         int size, buf;
 396         struct limiter *limiter;
 397
 398         snprintf(name, 256, "%s.sizeof_param", option_project_str);
 399         name[255] = '\0';
 400         token = get_tokens_file(name);
 401         if (!token)
 402                 return;
 403         if (token_type(token) != TOKEN_STREAMBEGIN)
 404                 return;
 405         token = token->next;
 406         while (token_type(token) != TOKEN_STREAMEND) {
 407                 if (token_type(token) != TOKEN_IDENT)
 408                         return;
 409                 func = show_ident(token->ident);
 410
 411                 token = token->next;
 412                 if (token_type(token) != TOKEN_NUMBER)
 413                         return;
 414                 size = atoi(token->number);
 415
 416                 token = token->next;
 417                 if (token_type(token) != TOKEN_NUMBER)
 418                         return;
 419                 buf = atoi(token->number);
 420
 421                 limiter = malloc(sizeof(*limiter));
 422                 limiter->limit_arg = size;
 423                 limiter->buf_arg = buf;
 424
 425                 add_function_hook(func, &match_limited, limiter);
 426
 427                 token = token->next;
 428         }
 429         clear_token_alloc();
 430 }
 431
 432 void check_overflow(int id)
 433 {
 434         my_used_id = id;
 435         register_funcs_from_file();
 436         add_hook(&match_function_def, FUNC_DEF_HOOK);
 437         add_hook(&array_check, OP_HOOK);
 438         add_hook(&match_condition, CONDITION_HOOK);
 439         add_function_hook("strcpy", &match_strcpy, NULL);
 440         add_function_hook("snprintf", &match_snprintf, NULL);
 441         add_function_hook("sprintf", &match_sprintf, NULL);
 442         add_function_hook("memcmp", &match_limited, &b0_l2);
 443         add_function_hook("memcmp", &match_limited, &b1_l2);
 444         select_return_states_hook(BUF_SIZE, &db_returns_buf_size);
 445         add_modification_hook(my_used_id, &delete);
 446         if (option_project == PROJ_KERNEL) {
 447                 add_function_hook("copy_to_user", &match_limited, &b1_l2);
 448                 add_function_hook("_copy_to_user", &match_limited, &b1_l2);
 449                 add_function_hook("__copy_to_user", &match_limited, &b1_l2);
 450                 add_function_hook("copy_from_user", &match_limited, &b0_l2);
 451                 add_function_hook("_copy_from_user", &match_limited, &b0_l2);
 452                 add_function_hook("__copy_from_user", &match_limited, &b0_l2);
 453         }
 454 }