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         data_size = get_array_size_bytes(data);
 238
 239         if (!dest_size)
 240                 return;
 241
 242         /* If the size of both arrays is known and the destination
 243          * buffer is larger than the source buffer, we're okay.
 244          */
 245         if (data_size && dest_size >= data_size)
 246                 return;
 247
 248         dest_name = expr_to_str(dest);
 249         data_name = expr_to_str(data);
 250
 251         if (data_size)
 252                 sm_msg("error: %s() '%s' too large for '%s' (%d vs %d)",
 253                         fn, data_name, dest_name, data_size, dest_size);
 254         else if (option_spammy)
 255                 sm_msg("warn: %s() '%s' of unknown size might be too large for '%s'",
 256                         fn, data_name, dest_name);
 257
 258         free_string(dest_name);
 259         free_string(data_name);
 260 }
 261
 262 static void match_snprintf(const char *fn, struct expression *expr, void *unused)
 263 {
 264         struct expression *dest;
 265         struct expression *dest_size_expr;
 266         struct expression *format_string;
 267         struct expression *data;
 268         char *data_name = NULL;
 269         int dest_size;
 270         sval_t limit_size;
 271         char *format;
 272         int data_size;
 273
 274         dest = get_argument_from_call_expr(expr->args, 0);
 275         dest_size_expr = get_argument_from_call_expr(expr->args, 1);
 276         format_string = get_argument_from_call_expr(expr->args, 2);
 277         data = get_argument_from_call_expr(expr->args, 3);
 278
 279         dest_size = get_array_size_bytes(dest);
 280         if (!get_implied_value(dest_size_expr, &limit_size))
 281                 return;
 282         if (dest_size && dest_size < limit_size.value)
 283                 sm_msg("error: snprintf() is printing too much %s vs %d",
 284                        sval_to_str(limit_size), dest_size);
 285         format = expr_to_var(format_string);
 286         if (!format)
 287                 return;
 288         if (strcmp(format, "\"%s\""))
 289                 goto free;
 290         data_name = expr_to_str(data);
 291         data_size = get_array_size_bytes(data);
 292         if (limit_size.value < data_size)
 293                 sm_msg("error: snprintf() chops off the last chars of '%s': %d vs %s",
 294                        data_name, data_size, sval_to_str(limit_size));
 295 free:
 296         free_string(data_name);
 297         free_string(format);
 298 }
 299
 300 static void match_sprintf(const char *fn, struct expression *expr, void *unused)
 301 {
 302         struct expression *dest;
 303         struct expression *format_string;
 304         struct expression *data;
 305         char *data_name = NULL;
 306         int dest_size;
 307         char *format;
 308         int data_size;
 309
 310         dest = get_argument_from_call_expr(expr->args, 0);
 311         format_string = get_argument_from_call_expr(expr->args, 1);
 312         data = get_argument_from_call_expr(expr->args, 2);
 313
 314         dest_size = get_array_size_bytes(dest);
 315         if (!dest_size)
 316                 return;
 317         format = expr_to_var(format_string);
 318         if (!format)
 319                 return;
 320         if (strcmp(format, "\"%s\""))
 321                 goto free;
 322         data_name = expr_to_str(data);
 323         data_size = get_array_size_bytes(data);
 324         if (dest_size < data_size)
 325                 sm_msg("error: sprintf() copies too much data from '%s': %d vs %d",
 326                        data_name, data_size, dest_size);
 327 free:
 328         free_string(data_name);
 329         free_string(format);
 330 }
 331
 332 static void match_limited(const char *fn, struct expression *expr, void *_limiter)
 333 {
 334         struct limiter *limiter = (struct limiter *)_limiter;
 335         struct expression *dest;
 336         struct expression *data;
 337         char *dest_name = NULL;
 338         sval_t needed;
 339         int has;
 340
 341         dest = get_argument_from_call_expr(expr->args, limiter->buf_arg);
 342         data = get_argument_from_call_expr(expr->args, limiter->limit_arg);
 343         if (!get_the_max(data, &needed))
 344                 return;
 345         has = get_array_size_bytes_max(dest);
 346         if (!has)
 347                 return;
 348         if (has >= needed.value)
 349                 return;
 350
 351         dest_name = expr_to_str(dest);
 352         sm_msg("error: %s() '%s' too small (%d vs %s)", fn, dest_name, has, sval_to_str(needed));
 353         free_string(dest_name);
 354 }
 355
 356 static void db_returns_buf_size(struct expression *expr, int param, char *unused, char *math)
 357 {
 358         struct expression *call;
 359         struct symbol *left_type, *right_type;
 360         int bytes;
 361         sval_t sval;
 362
 363         if (expr->type != EXPR_ASSIGNMENT)
 364                 return;
 365         right_type = get_pointer_type(expr->right);
 366         if (!right_type || type_bits(right_type) != -1)
 367                 return;
 368
 369         call = strip_expr(expr->right);
 370         left_type = get_pointer_type(expr->left);
 371
 372         if (!parse_call_math(call, math, &sval) || sval.value == 0)
 373                 return;
 374         if (!left_type)
 375                 return;
 376         bytes = type_bytes(left_type);
 377         if (bytes <= 0)
 378                 return;
 379         if (sval.uvalue >= bytes)
 380                 return;
 381         sm_msg("error: not allocating enough data %d vs %s", bytes, sval_to_str(sval));
 382 }
 383
 384 static void register_funcs_from_file(void)
 385 {
 386         char name[256];
 387         struct token *token;
 388         const char *func;
 389         int size, buf;
 390         struct limiter *limiter;
 391
 392         snprintf(name, 256, "%s.sizeof_param", option_project_str);
 393         name[255] = '\0';
 394         token = get_tokens_file(name);
 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                 if (token_type(token) != TOKEN_IDENT)
 402                         return;
 403                 func = show_ident(token->ident);
 404
 405                 token = token->next;
 406                 if (token_type(token) != TOKEN_NUMBER)
 407                         return;
 408                 size = atoi(token->number);
 409
 410                 token = token->next;
 411                 if (token_type(token) != TOKEN_NUMBER)
 412                         return;
 413                 buf = atoi(token->number);
 414
 415                 limiter = malloc(sizeof(*limiter));
 416                 limiter->limit_arg = size;
 417                 limiter->buf_arg = buf;
 418
 419                 add_function_hook(func, &match_limited, limiter);
 420
 421                 token = token->next;
 422         }
 423         clear_token_alloc();
 424 }
 425
 426 void check_overflow(int id)
 427 {
 428         my_used_id = id;
 429         register_funcs_from_file();
 430         add_hook(&match_function_def, FUNC_DEF_HOOK);
 431         add_hook(&array_check, OP_HOOK);
 432         add_hook(&match_condition, CONDITION_HOOK);
 433         add_function_hook("strcpy", &match_strcpy, NULL);
 434         add_function_hook("snprintf", &match_snprintf, NULL);
 435         add_function_hook("sprintf", &match_sprintf, NULL);
 436         add_function_hook("memcmp", &match_limited, &b0_l2);
 437         add_function_hook("memcmp", &match_limited, &b1_l2);
 438         select_return_states_hook(BUF_SIZE, &db_returns_buf_size);
 439         add_modification_hook(my_used_id, &delete);
 440         if (option_project == PROJ_KERNEL) {
 441                 add_function_hook("copy_to_user", &match_limited, &b1_l2);
 442                 add_function_hook("_copy_to_user", &match_limited, &b1_l2);
 443                 add_function_hook("__copy_to_user", &match_limited, &b1_l2);
 444                 add_function_hook("copy_from_user", &match_limited, &b0_l2);
 445                 add_function_hook("_copy_from_user", &match_limited, &b0_l2);
 446                 add_function_hook("__copy_from_user", &match_limited, &b0_l2);
 447         }
 448 }