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 (constraint_met(array_expr, offset))
 275                 return 0;
 276
 277         if (array_size > rl_max(abs_rl).uvalue)
 278                 return 0;
 279
 280         if (definitely_just_used_as_limiter(array_expr, offset))
 281                 return 0;
 282
 283         array_expr = strip_expr(array_expr);
 284         if (common_false_positives(array_expr, max))
 285                 return 0;
 286
 287         if (impossibly_high_comparison(offset))
 288                 return 0;
 289
 290         if (is_zero_size_memcpy(expr, array_size, abs_rl))
 291                 return 0;
 292         return 1;
 293
 294 }
 295
 296 static int is_because_of_no_break(struct expression *offset)
 297 {
 298         if (get_state_expr(loop_id, offset) == &loop_end)
 299                 return 1;
 300         return 0;
 301 }
 302
 303 static void array_check(struct expression *expr)
 304 {
 305         struct expression *array_expr;
 306         struct range_list *abs_rl;
 307         struct range_list *user_rl = NULL;
 308         sval_t hard_max = { .type = &int_ctype, };
 309         sval_t fuzzy_max = { .type = &int_ctype, };
 310         int array_size;
 311         struct expression *array_size_value, *comparison;
 312         struct expression *offset;
 313         sval_t max;
 314         char *name;
 315         int no_break = 0;
 316
 317         if (!should_warn(expr))
 318                 return;
 319
 320         expr = strip_expr(expr);
 321         array_expr = get_array_base(expr);
 322         array_size = get_array_size(array_expr);
 323         offset = get_array_offset(expr);
 324
 325         /*
 326          * Perhaps if the offset is out of bounds that means a constraint
 327          * applies or maybe it means we are on an impossible path.  So test
 328          * again based on that assumption.
 329          *
 330          */
 331         array_size_value = value_expr(array_size);
 332         comparison = compare_expression(offset, SPECIAL_GTE, array_size_value);
 333         if (assume(comparison)) {
 334                 if (!should_warn(expr)) {
 335                         end_assume();
 336                         return;
 337                 }
 338                 no_break = is_because_of_no_break(offset);
 339                 end_assume();
 340         }
 341
 342         get_absolute_rl(offset, &abs_rl);
 343         get_user_rl(offset, &user_rl);
 344         fake_get_hard_max(offset, &hard_max);
 345         get_fuzzy_max(offset, &fuzzy_max);
 346
 347         array_expr = strip_expr(array_expr);
 348         name = expr_to_str(array_expr);
 349
 350         if (user_rl)
 351                 max = rl_max(user_rl);
 352         else
 353                 max = rl_max(abs_rl);
 354
 355         if (!option_spammy && is_subtract(offset))
 356                 return;
 357
 358         if (no_break) {
 359                 sm_error("buffer overflow '%s' %d <= %s (assuming for loop doesn't break)",
 360                         name, array_size, sval_to_str(max));
 361         } else if (user_rl) {
 362                 sm_error("buffer overflow '%s' %d <= %s user_rl='%s'%s",
 363                         name, array_size, sval_to_str(max), show_rl(user_rl),
 364                         is_subtract(offset) ? " subtract" : "");
 365         } else {
 366                 sm_error("buffer overflow '%s' %d <= %s%s",
 367                         name, array_size, sval_to_str(max),
 368                         is_subtract(offset) ? " subtract" : "");
 369         }
 370
 371         free_string(name);
 372 }
 373
 374 void check_index_overflow(int id)
 375 {
 376         add_hook(&array_check, OP_HOOK);
 377 }
 378
 379 static void match_condition(struct expression *expr)
 380 {
 381         struct statement *stmt;
 382
 383         if (expr->type != EXPR_COMPARE)
 384                 return;
 385         if (expr->op != '<' && expr->op != SPECIAL_UNSIGNED_LT)
 386                 return;
 387
 388         stmt = expr_get_parent_stmt(expr);
 389         if (!stmt || stmt->type != STMT_ITERATOR)
 390                 return;
 391
 392         set_true_false_states_expr(loop_id, expr->left, NULL, &loop_end);
 393 }
 394
 395 static void set_undefined(struct sm_state *sm, struct expression *mod_expr)
 396 {
 397         if (sm->state == &loop_end)
 398                 set_state(loop_id, sm->name, sm->sym, &undefined);
 399 }
 400
 401 void check_index_overflow_loop_marker(int id)
 402 {
 403         loop_id = id;
 404
 405         add_hook(&match_condition, CONDITION_HOOK);
 406         add_modification_hook(loop_id, &set_undefined);
 407 }
 408