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 368