check_index_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 static int loop_id;
  25
  26 STATE(loop_end);
  27
  28 static int definitely_just_used_as_limiter(struct expression *array, struct expression *offset)
  29 {
  30         sval_t sval;
  31         struct expression *tmp;
  32
  33         if (!get_implied_value(offset, &sval))
  34                 return 0;
  35         if (get_array_size(array) != sval.value)
  36                 return 0;
  37
  38         tmp = array;
  39         while ((tmp = expr_get_parent_expr(tmp))) {
  40                 if (tmp->type == EXPR_PREOP && tmp->op == '&')
  41                         return 1;
  42         }
  43
  44         return 0;
  45 }
  46
  47 static int fake_get_hard_max(struct expression *expr, sval_t *sval)
  48 {
  49         struct range_list *implied_rl;
  50
  51         if (!get_hard_max(expr, sval))
  52                 return 0;
  53
  54         /*
  55          * The problem is that hard_max doesn't care about minimums
  56          * properly.  So if you give it thing like:
  57          *      err = (-10)-(-1)
  58          *      __smatch_hard_max(-err);
  59          *
  60          * Then it returns s32max instead of 10.
  61          */
  62
  63         if (get_implied_rl(expr, &implied_rl) &&
  64             sval_cmp(rl_max(implied_rl), *sval) < 0)
  65                 *sval = rl_max(implied_rl);
  66         return 1;
  67 }
  68
  69 static int get_the_max(struct expression *expr, sval_t *sval)
  70 {
  71         struct range_list *rl;
  72
  73         if (get_hard_max(expr, sval)) {
  74                 struct range_list *implied_rl;
  75
  76                 /*
  77                  * The problem is that hard_max doesn't care about minimums
  78                  * properly.  So if you give it thing like:
  79                  *      err = (-10)-(-1)
  80                  *      __smatch_hard_max(-err);
  81                  *
  82                  * Then it returns s32max instead of 10.
  83                  */
  84
  85                 if (get_implied_rl(expr, &implied_rl) &&
  86                     sval_cmp(rl_max(implied_rl), *sval) < 0)
  87                         *sval = rl_max(implied_rl);
  88                 return 1;
  89         }
  90         if (!option_spammy)
  91                 return 0;
  92
  93         /* Fixme:  use fuzzy max */
  94
  95         if (!get_user_rl(expr, &rl))
  96                 return 0;
  97         if (rl_max(rl).uvalue > sval_type_max(rl_type(rl)).uvalue - 4 &&
  98             is_capped(expr))
  99                 return 0;
 100
 101         *sval = rl_max(rl);
 102         return 1;
 103 }
 104
 105 static int common_false_positives(struct expression *array, sval_t max)
 106 {
 107         char *name;
 108         int ret;
 109
 110         name = expr_to_str(array);
 111
 112         /* Smatch can't figure out glibc's strcmp __strcmp_cg()
 113          * so it prints an error every time you compare to a string
 114          * literal array with 4 or less chars.
 115          */
 116         if (name &&
 117             (strcmp(name, "__s1") == 0 || strcmp(name, "__s2") == 0)) {
 118                 ret = 1;
 119                 goto free;
 120         }
 121
 122         /* Ugh... People are saying that Smatch still barfs on glibc strcmp()
 123          * functions.
 124          */
 125         if (array) {
 126                 char *macro;
 127
 128                 /* why is this again??? */
 129                 if (array->type == EXPR_STRING &&
 130                     max.value == array->string->length) {
 131                         ret = 1;
 132                         goto free;
 133                 }
 134
 135                 macro = get_macro_name(array->pos);
 136                 if (macro && max.uvalue < 4 &&
 137                     (strcmp(macro, "strcmp")  == 0 ||
 138                      strcmp(macro, "strncmp") == 0 ||
 139                      strcmp(macro, "streq")   == 0 ||
 140                      strcmp(macro, "strneq")  == 0 ||
 141                      strcmp(macro, "strsep")  == 0)) {
 142                         ret = 1;
 143                         goto free;
 144                 }
 145         }
 146
 147         /*
 148          * passing WORK_CPU_UNBOUND is idiomatic but Smatch doesn't understand
 149          * how it's used so it causes a bunch of false positives.
 150          */
 151         if (option_project == PROJ_KERNEL && name &&
 152             strcmp(name, "__per_cpu_offset") == 0) {
 153                 ret = 1;
 154                 goto free;
 155         }
 156         ret = 0;
 157
 158 free:
 159         free_string(name);
 160         return ret;
 161 }
 162
 163 static int is_subtract(struct expression *expr)
 164 {
 165         struct expression *tmp;
 166         int cnt = 0;
 167
 168         expr = strip_expr(expr);
 169         while ((tmp = get_assigned_expr(expr))) {
 170                 expr = strip_expr(tmp);
 171                 if (++cnt > 5)
 172                         break;
 173         }
 174
 175         if (expr->type == EXPR_BINOP && expr->op == '-')
 176                 return 1;
 177         return 0;
 178 }
 179
 180 static int constraint_met(struct expression *array_expr, struct expression *offset)
 181 {
 182         char *data_str, *required, *unmet;
 183         int ret = 0;
 184
 185         data_str = get_constraint_str(array_expr);
 186         if (!data_str)
 187                 return 0;
 188
 189         required = get_required_constraint(data_str);
 190         if (!required)
 191                 goto free_data_str;
 192
 193         unmet = unmet_constraint(array_expr, offset);
 194         if (!unmet)
 195                 ret = 1;
 196         free_string(unmet);
 197         free_string(required);
 198
 199 free_data_str:
 200         free_string(data_str);
 201         return ret;
 202 }
 203
 204 static bool is_zero_size_memcpy(struct expression *expr, int size, struct range_list *rl)
 205 {
 206         struct expression *parent;
 207
 208         /*
 209          * Often times we have code like this:
 210          *      memcpy(array[idx], src, size)
 211          * In this example if "idx == ARRAY_SIZE()" then "size" is zero so
 212          * nothing is copied and the code is fine and Smatch should not
 213          * print a warning even though the idx is one element out of bounds.
 214          *
 215          * TODO: if we wanted to be very accurate we could find the length
 216          * expression and assume() that offset == rl_max() and then test that
 217          * the length expression is zero.  But that seems like a lot of work.
 218          * HashtagLazy.
 219          */
 220
 221         if (rl_max(rl).value != size)
 222                 return false;
 223
 224         parent = expr;
 225         while ((parent = expr_get_parent_expr(parent))) {
 226                 if (parent->type == EXPR_PREOP &&
 227                     (parent->op == '(' || parent->op == '&'))
 228                         continue;
 229                 if (parent->type == EXPR_CAST)
 230                         continue;
 231                 break;
 232         }
 233         if (!parent || parent->type != EXPR_CALL ||
 234             parent->fn->type != EXPR_SYMBOL || !parent->fn->symbol_name)
 235                 return false;
 236
 237         if (strstr(parent->fn->symbol_name->name, "memcpy") ||
 238             strstr(parent->fn->symbol_name->name, "memset"))
 239                 return true;
 240
 241         return false;
 242 }
 243
 244 static int should_warn(struct expression *expr)
 245 {
 246         struct expression *array_expr;
 247         struct range_list *abs_rl;
 248         sval_t hard_max = { .type = &int_ctype, };
 249         sval_t fuzzy_max = { .type = &int_ctype, };
 250         int array_size;
 251         struct expression *offset;
 252         sval_t max;
 253
 254         expr = strip_expr(expr);
 255         if (!is_array(expr))
 256                 return 0;
 257
 258         if (is_impossible_path())
 259                 return 0;
 260         array_expr = get_array_base(expr);
 261         array_size = get_array_size(array_expr);
 262         if (!array_size || array_size == 1)
 263                 return 0;
 264
 265         offset = get_array_offset(expr);
 266         get_absolute_rl(offset, &abs_rl);
 267         fake_get_hard_max(offset, &hard_max);
 268         get_fuzzy_max(offset, &fuzzy_max);
 269
 270         if (!get_the_max(offset, &max))
 271                 return 0;
 272         if (array_size > max.value)
 273                 return 0;
 274         if (buf_comparison_index_ok(expr))
 275                 return 0;
 276         if (constraint_met(array_expr, offset))
 277                 return 0;
 278
 279         if (array_size > rl_max(abs_rl).uvalue)
 280                 return 0;
 281
 282         if (definitely_just_used_as_limiter(array_expr, offset))
 283                 return 0;
 284
 285         array_expr = strip_expr(array_expr);
 286         if (common_false_positives(array_expr, max))
 287                 return 0;
 288
 289         if (impossibly_high_comparison(offset))
 290                 return 0;
 291
 292         if (is_zero_size_memcpy(expr, array_size, abs_rl))
 293                 return 0;
 294         return 1;
 295
 296 }
 297
 298 static int is_because_of_no_break(struct expression *offset)
 299 {
 300         if (get_state_expr(loop_id, offset) == &loop_end)
 301                 return 1;
 302         return 0;
 303 }
 304
 305 static void array_check(struct expression *expr)
 306 {
 307         struct expression *array_expr;
 308         struct range_list *abs_rl;
 309         struct range_list *user_rl = NULL;
 310         sval_t hard_max = { .type = &int_ctype, };
 311         sval_t fuzzy_max = { .type = &int_ctype, };
 312         int array_size;
 313         struct expression *array_size_value, *comparison;
 314         struct expression *offset;
 315         sval_t max;
 316         char *name;
 317         int no_break = 0;
 318
 319         if (!should_warn(expr))
 320                 return;
 321
 322         expr = strip_expr(expr);
 323         array_expr = get_array_base(expr);
 324         array_size = get_array_size(array_expr);
 325         offset = get_array_offset(expr);
 326
 327         /*
 328          * Perhaps if the offset is out of bounds that means a constraint
 329          * applies or maybe it means we are on an impossible path.  So test
 330          * again based on that assumption.
 331          *
 332          */
 333         array_size_value = value_expr(array_size);
 334         comparison = compare_expression(offset, SPECIAL_GTE, array_size_value);
 335         if (assume(comparison)) {
 336                 if (!should_warn(expr)) {
 337                         end_assume();
 338                         return;
 339                 }
 340                 no_break = is_because_of_no_break(offset);
 341                 end_assume();
 342         }
 343
 344         get_absolute_rl(offset, &abs_rl);
 345         get_user_rl(offset, &user_rl);
 346         fake_get_hard_max(offset, &hard_max);
 347         get_fuzzy_max(offset, &fuzzy_max);
 348
 349         array_expr = strip_expr(array_expr);
 350         name = expr_to_str(array_expr);
 351
 352         if (user_rl)
 353                 max = rl_max(user_rl);
 354         else
 355                 max = rl_max(abs_rl);
 356
 357         if (!option_spammy && is_subtract(offset))
 358                 return;
 359
 360         if (no_break) {
 361                 sm_error("buffer overflow '%s' %d <= %s (assuming for loop doesn't break)",
 362                         name, array_size, sval_to_str(max));
 363         } else if (user_rl) {
 364                 sm_error("buffer overflow '%s' %d <= %s user_rl='%s'%s",
 365                         name, array_size, sval_to_str(max), show_rl(user_rl),
 366                         is_subtract(offset) ? " subtract" : "");
 367         } else {
 368                 sm_error("buffer overflow '%s' %d <= %s%s",
 369                         name, array_size, sval_to_str(max),
 370                         is_subtract(offset) ? " subtract" : "");
 371         }
 372
 373         free_string(name);
 374 }
 375
 376 void check_index_overflow(int id)
 377 {
 378         add_hook(&array_check, OP_HOOK);
 379 }
 380
 381 static void match_condition(struct expression *expr)
 382 {
 383         struct statement *stmt;
 384
 385         if (expr->type != EXPR_COMPARE)
 386                 return;
 387         if (expr->op != '<' && expr->op != SPECIAL_UNSIGNED_LT)
 388                 return;
 389
 390         stmt = expr_get_parent_stmt(expr);
 391         if (!stmt || stmt->type != STMT_ITERATOR)
 392                 return;
 393
 394         set_true_false_states_expr(loop_id, expr->left, NULL, &loop_end);
 395 }
 396
 397 void check_index_overflow_loop_marker(int id)
 398 {
 399         loop_id = id;
 400
 401         add_hook(&match_condition, CONDITION_HOOK);
 402         add_modification_hook(loop_id, &set_undefined);
 403 }
 404