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
 205 static int should_warn(struct expression *expr)
 206 {
 207         struct expression *array_expr;
 208         struct range_list *abs_rl;
 209         sval_t hard_max = { .type = &int_ctype, };
 210         sval_t fuzzy_max = { .type = &int_ctype, };
 211         int array_size;
 212         struct expression *offset;
 213         sval_t max;
 214
 215         expr = strip_expr(expr);
 216         if (!is_array(expr))
 217                 return 0;
 218
 219         if (is_impossible_path())
 220                 return 0;
 221         array_expr = get_array_base(expr);
 222         array_size = get_array_size(array_expr);
 223         if (!array_size || array_size == 1)
 224                 return 0;
 225
 226         offset = get_array_offset(expr);
 227         get_absolute_rl(offset, &abs_rl);
 228         fake_get_hard_max(offset, &hard_max);
 229         get_fuzzy_max(offset, &fuzzy_max);
 230
 231         if (!get_the_max(offset, &max))
 232                 return 0;
 233         if (array_size > max.value)
 234                 return 0;
 235         if (constraint_met(array_expr, offset))
 236                 return 0;
 237
 238         if (array_size > rl_max(abs_rl).uvalue)
 239                 return 0;
 240
 241         if (definitely_just_used_as_limiter(array_expr, offset))
 242                 return 0;
 243
 244         array_expr = strip_expr(array_expr);
 245         if (common_false_positives(array_expr, max))
 246                 return 0;
 247
 248         if (impossibly_high_comparison(offset))
 249                 return 0;
 250
 251         return 1;
 252
 253 }
 254
 255 static int is_because_of_no_break(struct expression *offset)
 256 {
 257         if (get_state_expr(loop_id, offset) == &loop_end)
 258                 return 1;
 259         return 0;
 260 }
 261
 262 static void array_check(struct expression *expr)
 263 {
 264         struct expression *array_expr;
 265         struct range_list *abs_rl;
 266         struct range_list *user_rl = NULL;
 267         sval_t hard_max = { .type = &int_ctype, };
 268         sval_t fuzzy_max = { .type = &int_ctype, };
 269         int array_size;
 270         struct expression *array_size_value, *comparison;
 271         struct expression *offset;
 272         sval_t max;
 273         char *name;
 274         int no_break = 0;
 275
 276         if (!should_warn(expr))
 277                 return;
 278
 279         expr = strip_expr(expr);
 280         array_expr = get_array_base(expr);
 281         array_size = get_array_size(array_expr);
 282         offset = get_array_offset(expr);
 283
 284         /*
 285          * Perhaps if the offset is out of bounds that means a constraint
 286          * applies or maybe it means we are on an impossible path.  So test
 287          * again based on that assumption.
 288          *
 289          */
 290         array_size_value = value_expr(array_size);
 291         comparison = compare_expression(offset, SPECIAL_GTE, array_size_value);
 292         if (assume(comparison)) {
 293                 if (!should_warn(expr)) {
 294                         end_assume();
 295                         return;
 296                 }
 297                 no_break = is_because_of_no_break(offset);
 298                 end_assume();
 299         }
 300
 301         get_absolute_rl(offset, &abs_rl);
 302         get_user_rl(offset, &user_rl);
 303         fake_get_hard_max(offset, &hard_max);
 304         get_fuzzy_max(offset, &fuzzy_max);
 305
 306         array_expr = strip_expr(array_expr);
 307         name = expr_to_str(array_expr);
 308
 309         if (user_rl)
 310                 max = rl_max(user_rl);
 311         else
 312                 max = rl_max(abs_rl);
 313
 314         if (!option_spammy && is_subtract(offset))
 315                 return;
 316
 317         if (no_break) {
 318                 sm_error("buffer overflow '%s' %d <= %s (assuming for loop doesn't break)",
 319                         name, array_size, sval_to_str(max));
 320         } else if (user_rl) {
 321                 sm_error("buffer overflow '%s' %d <= %s user_rl='%s'%s",
 322                         name, array_size, sval_to_str(max), show_rl(user_rl),
 323                         is_subtract(offset) ? " subtract" : "");
 324         } else {
 325                 sm_error("buffer overflow '%s' %d <= %s%s",
 326                         name, array_size, sval_to_str(max),
 327                         is_subtract(offset) ? " subtract" : "");
 328         }
 329
 330         free_string(name);
 331 }
 332
 333 void check_index_overflow(int id)
 334 {
 335         add_hook(&array_check, OP_HOOK);
 336 }
 337
 338 static void match_condition(struct expression *expr)
 339 {
 340         struct statement *stmt;
 341
 342         if (expr->type != EXPR_COMPARE)
 343                 return;
 344         if (expr->op != '<' && expr->op != SPECIAL_UNSIGNED_LT)
 345                 return;
 346
 347         stmt = expr_get_parent_stmt(expr);
 348         if (!stmt || stmt->type != STMT_ITERATOR)
 349                 return;
 350
 351         set_true_false_states_expr(loop_id, expr->left, NULL, &loop_end);
 352 }
 353
 354 static void set_undefined(struct sm_state *sm, struct expression *mod_expr)
 355 {
 356         if (sm->state == &loop_end)
 357                 set_state(loop_id, sm->name, sm->sym, &undefined);
 358 }
 359
 360 void check_index_overflow_loop_marker(int id)
 361 {
 362         loop_id = id;
 363
 364         add_hook(&match_condition, CONDITION_HOOK);
 365         add_modification_hook(loop_id, &set_undefined);
 366 }
 367