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