1*1f5207b7SJohn Levon /*
2*1f5207b7SJohn Levon * Copyright (C) 2010 Dan Carpenter.
3*1f5207b7SJohn Levon *
4*1f5207b7SJohn Levon * This program is free software; you can redistribute it and/or
5*1f5207b7SJohn Levon * modify it under the terms of the GNU General Public License
6*1f5207b7SJohn Levon * as published by the Free Software Foundation; either version 2
7*1f5207b7SJohn Levon * of the License, or (at your option) any later version.
8*1f5207b7SJohn Levon *
9*1f5207b7SJohn Levon * This program is distributed in the hope that it will be useful,
10*1f5207b7SJohn Levon * but WITHOUT ANY WARRANTY; without even the implied warranty of
11*1f5207b7SJohn Levon * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12*1f5207b7SJohn Levon * GNU General Public License for more details.
13*1f5207b7SJohn Levon *
14*1f5207b7SJohn Levon * You should have received a copy of the GNU General Public License
15*1f5207b7SJohn Levon * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
16*1f5207b7SJohn Levon */
17*1f5207b7SJohn Levon
18*1f5207b7SJohn Levon #include <stdlib.h>
19*1f5207b7SJohn Levon #include "parse.h"
20*1f5207b7SJohn Levon #include "smatch.h"
21*1f5207b7SJohn Levon #include "smatch_slist.h"
22*1f5207b7SJohn Levon #include "smatch_extra.h"
23*1f5207b7SJohn Levon
24*1f5207b7SJohn Levon static int loop_id;
25*1f5207b7SJohn Levon
26*1f5207b7SJohn Levon STATE(loop_end);
27*1f5207b7SJohn Levon
definitely_just_used_as_limiter(struct expression * array,struct expression * offset)28*1f5207b7SJohn Levon static int definitely_just_used_as_limiter(struct expression *array, struct expression *offset)
29*1f5207b7SJohn Levon {
30*1f5207b7SJohn Levon sval_t sval;
31*1f5207b7SJohn Levon struct expression *tmp;
32*1f5207b7SJohn Levon
33*1f5207b7SJohn Levon if (!get_implied_value(offset, &sval))
34*1f5207b7SJohn Levon return 0;
35*1f5207b7SJohn Levon if (get_array_size(array) != sval.value)
36*1f5207b7SJohn Levon return 0;
37*1f5207b7SJohn Levon
38*1f5207b7SJohn Levon tmp = array;
39*1f5207b7SJohn Levon while ((tmp = expr_get_parent_expr(tmp))) {
40*1f5207b7SJohn Levon if (tmp->type == EXPR_PREOP && tmp->op == '&')
41*1f5207b7SJohn Levon return 1;
42*1f5207b7SJohn Levon }
43*1f5207b7SJohn Levon
44*1f5207b7SJohn Levon return 0;
45*1f5207b7SJohn Levon }
46*1f5207b7SJohn Levon
fake_get_hard_max(struct expression * expr,sval_t * sval)47*1f5207b7SJohn Levon static int fake_get_hard_max(struct expression *expr, sval_t *sval)
48*1f5207b7SJohn Levon {
49*1f5207b7SJohn Levon struct range_list *implied_rl;
50*1f5207b7SJohn Levon
51*1f5207b7SJohn Levon if (!get_hard_max(expr, sval))
52*1f5207b7SJohn Levon return 0;
53*1f5207b7SJohn Levon
54*1f5207b7SJohn Levon /*
55*1f5207b7SJohn Levon * The problem is that hard_max doesn't care about minimums
56*1f5207b7SJohn Levon * properly. So if you give it thing like:
57*1f5207b7SJohn Levon * err = (-10)-(-1)
58*1f5207b7SJohn Levon * __smatch_hard_max(-err);
59*1f5207b7SJohn Levon *
60*1f5207b7SJohn Levon * Then it returns s32max instead of 10.
61*1f5207b7SJohn Levon */
62*1f5207b7SJohn Levon
63*1f5207b7SJohn Levon if (get_implied_rl(expr, &implied_rl) &&
64*1f5207b7SJohn Levon sval_cmp(rl_max(implied_rl), *sval) < 0)
65*1f5207b7SJohn Levon *sval = rl_max(implied_rl);
66*1f5207b7SJohn Levon return 1;
67*1f5207b7SJohn Levon }
68*1f5207b7SJohn Levon
get_the_max(struct expression * expr,sval_t * sval)69*1f5207b7SJohn Levon static int get_the_max(struct expression *expr, sval_t *sval)
70*1f5207b7SJohn Levon {
71*1f5207b7SJohn Levon struct range_list *rl;
72*1f5207b7SJohn Levon
73*1f5207b7SJohn Levon if (get_hard_max(expr, sval)) {
74*1f5207b7SJohn Levon struct range_list *implied_rl;
75*1f5207b7SJohn Levon
76*1f5207b7SJohn Levon /*
77*1f5207b7SJohn Levon * The problem is that hard_max doesn't care about minimums
78*1f5207b7SJohn Levon * properly. So if you give it thing like:
79*1f5207b7SJohn Levon * err = (-10)-(-1)
80*1f5207b7SJohn Levon * __smatch_hard_max(-err);
81*1f5207b7SJohn Levon *
82*1f5207b7SJohn Levon * Then it returns s32max instead of 10.
83*1f5207b7SJohn Levon */
84*1f5207b7SJohn Levon
85*1f5207b7SJohn Levon if (get_implied_rl(expr, &implied_rl) &&
86*1f5207b7SJohn Levon sval_cmp(rl_max(implied_rl), *sval) < 0)
87*1f5207b7SJohn Levon *sval = rl_max(implied_rl);
88*1f5207b7SJohn Levon return 1;
89*1f5207b7SJohn Levon }
90*1f5207b7SJohn Levon if (!option_spammy)
91*1f5207b7SJohn Levon return 0;
92*1f5207b7SJohn Levon
93*1f5207b7SJohn Levon /* Fixme: use fuzzy max */
94*1f5207b7SJohn Levon
95*1f5207b7SJohn Levon if (!get_user_rl(expr, &rl))
96*1f5207b7SJohn Levon return 0;
97*1f5207b7SJohn Levon if (rl_max(rl).uvalue > sval_type_max(rl_type(rl)).uvalue - 4 &&
98*1f5207b7SJohn Levon is_capped(expr))
99*1f5207b7SJohn Levon return 0;
100*1f5207b7SJohn Levon
101*1f5207b7SJohn Levon *sval = rl_max(rl);
102*1f5207b7SJohn Levon return 1;
103*1f5207b7SJohn Levon }
104*1f5207b7SJohn Levon
common_false_positives(struct expression * array,sval_t max)105*1f5207b7SJohn Levon static int common_false_positives(struct expression *array, sval_t max)
106*1f5207b7SJohn Levon {
107*1f5207b7SJohn Levon char *name;
108*1f5207b7SJohn Levon int ret;
109*1f5207b7SJohn Levon
110*1f5207b7SJohn Levon name = expr_to_str(array);
111*1f5207b7SJohn Levon
112*1f5207b7SJohn Levon /* Smatch can't figure out glibc's strcmp __strcmp_cg()
113*1f5207b7SJohn Levon * so it prints an error every time you compare to a string
114*1f5207b7SJohn Levon * literal array with 4 or less chars.
115*1f5207b7SJohn Levon */
116*1f5207b7SJohn Levon if (name &&
117*1f5207b7SJohn Levon (strcmp(name, "__s1") == 0 || strcmp(name, "__s2") == 0)) {
118*1f5207b7SJohn Levon ret = 1;
119*1f5207b7SJohn Levon goto free;
120*1f5207b7SJohn Levon }
121*1f5207b7SJohn Levon
122*1f5207b7SJohn Levon /* Ugh... People are saying that Smatch still barfs on glibc strcmp()
123*1f5207b7SJohn Levon * functions.
124*1f5207b7SJohn Levon */
125*1f5207b7SJohn Levon if (array) {
126*1f5207b7SJohn Levon char *macro;
127*1f5207b7SJohn Levon
128*1f5207b7SJohn Levon /* why is this again??? */
129*1f5207b7SJohn Levon if (array->type == EXPR_STRING &&
130*1f5207b7SJohn Levon max.value == array->string->length) {
131*1f5207b7SJohn Levon ret = 1;
132*1f5207b7SJohn Levon goto free;
133*1f5207b7SJohn Levon }
134*1f5207b7SJohn Levon
135*1f5207b7SJohn Levon macro = get_macro_name(array->pos);
136*1f5207b7SJohn Levon if (macro && max.uvalue < 4 &&
137*1f5207b7SJohn Levon (strcmp(macro, "strcmp") == 0 ||
138*1f5207b7SJohn Levon strcmp(macro, "strncmp") == 0 ||
139*1f5207b7SJohn Levon strcmp(macro, "streq") == 0 ||
140*1f5207b7SJohn Levon strcmp(macro, "strneq") == 0 ||
141*1f5207b7SJohn Levon strcmp(macro, "strsep") == 0)) {
142*1f5207b7SJohn Levon ret = 1;
143*1f5207b7SJohn Levon goto free;
144*1f5207b7SJohn Levon }
145*1f5207b7SJohn Levon }
146*1f5207b7SJohn Levon
147*1f5207b7SJohn Levon /*
148*1f5207b7SJohn Levon * passing WORK_CPU_UNBOUND is idiomatic but Smatch doesn't understand
149*1f5207b7SJohn Levon * how it's used so it causes a bunch of false positives.
150*1f5207b7SJohn Levon */
151*1f5207b7SJohn Levon if (option_project == PROJ_KERNEL && name &&
152*1f5207b7SJohn Levon strcmp(name, "__per_cpu_offset") == 0) {
153*1f5207b7SJohn Levon ret = 1;
154*1f5207b7SJohn Levon goto free;
155*1f5207b7SJohn Levon }
156*1f5207b7SJohn Levon ret = 0;
157*1f5207b7SJohn Levon
158*1f5207b7SJohn Levon free:
159*1f5207b7SJohn Levon free_string(name);
160*1f5207b7SJohn Levon return ret;
161*1f5207b7SJohn Levon }
162*1f5207b7SJohn Levon
is_subtract(struct expression * expr)163*1f5207b7SJohn Levon static int is_subtract(struct expression *expr)
164*1f5207b7SJohn Levon {
165*1f5207b7SJohn Levon struct expression *tmp;
166*1f5207b7SJohn Levon int cnt = 0;
167*1f5207b7SJohn Levon
168*1f5207b7SJohn Levon expr = strip_expr(expr);
169*1f5207b7SJohn Levon while ((tmp = get_assigned_expr(expr))) {
170*1f5207b7SJohn Levon expr = strip_expr(tmp);
171*1f5207b7SJohn Levon if (++cnt > 5)
172*1f5207b7SJohn Levon break;
173*1f5207b7SJohn Levon }
174*1f5207b7SJohn Levon
175*1f5207b7SJohn Levon if (expr->type == EXPR_BINOP && expr->op == '-')
176*1f5207b7SJohn Levon return 1;
177*1f5207b7SJohn Levon return 0;
178*1f5207b7SJohn Levon }
179*1f5207b7SJohn Levon
constraint_met(struct expression * array_expr,struct expression * offset)180*1f5207b7SJohn Levon static int constraint_met(struct expression *array_expr, struct expression *offset)
181*1f5207b7SJohn Levon {
182*1f5207b7SJohn Levon char *data_str, *required, *unmet;
183*1f5207b7SJohn Levon int ret = 0;
184*1f5207b7SJohn Levon
185*1f5207b7SJohn Levon data_str = get_constraint_str(array_expr);
186*1f5207b7SJohn Levon if (!data_str)
187*1f5207b7SJohn Levon return 0;
188*1f5207b7SJohn Levon
189*1f5207b7SJohn Levon required = get_required_constraint(data_str);
190*1f5207b7SJohn Levon if (!required)
191*1f5207b7SJohn Levon goto free_data_str;
192*1f5207b7SJohn Levon
193*1f5207b7SJohn Levon unmet = unmet_constraint(array_expr, offset);
194*1f5207b7SJohn Levon if (!unmet)
195*1f5207b7SJohn Levon ret = 1;
196*1f5207b7SJohn Levon free_string(unmet);
197*1f5207b7SJohn Levon free_string(required);
198*1f5207b7SJohn Levon
199*1f5207b7SJohn Levon free_data_str:
200*1f5207b7SJohn Levon free_string(data_str);
201*1f5207b7SJohn Levon return ret;
202*1f5207b7SJohn Levon }
203*1f5207b7SJohn Levon
204*1f5207b7SJohn Levon
should_warn(struct expression * expr)205*1f5207b7SJohn Levon static int should_warn(struct expression *expr)
206*1f5207b7SJohn Levon {
207*1f5207b7SJohn Levon struct expression *array_expr;
208*1f5207b7SJohn Levon struct range_list *abs_rl;
209*1f5207b7SJohn Levon sval_t hard_max = { .type = &int_ctype, };
210*1f5207b7SJohn Levon sval_t fuzzy_max = { .type = &int_ctype, };
211*1f5207b7SJohn Levon int array_size;
212*1f5207b7SJohn Levon struct expression *offset;
213*1f5207b7SJohn Levon sval_t max;
214*1f5207b7SJohn Levon
215*1f5207b7SJohn Levon expr = strip_expr(expr);
216*1f5207b7SJohn Levon if (!is_array(expr))
217*1f5207b7SJohn Levon return 0;
218*1f5207b7SJohn Levon
219*1f5207b7SJohn Levon if (is_impossible_path())
220*1f5207b7SJohn Levon return 0;
221*1f5207b7SJohn Levon array_expr = get_array_base(expr);
222*1f5207b7SJohn Levon array_size = get_array_size(array_expr);
223*1f5207b7SJohn Levon if (!array_size || array_size == 1)
224*1f5207b7SJohn Levon return 0;
225*1f5207b7SJohn Levon
226*1f5207b7SJohn Levon offset = get_array_offset(expr);
227*1f5207b7SJohn Levon get_absolute_rl(offset, &abs_rl);
228*1f5207b7SJohn Levon fake_get_hard_max(offset, &hard_max);
229*1f5207b7SJohn Levon get_fuzzy_max(offset, &fuzzy_max);
230*1f5207b7SJohn Levon
231*1f5207b7SJohn Levon if (!get_the_max(offset, &max))
232*1f5207b7SJohn Levon return 0;
233*1f5207b7SJohn Levon if (array_size > max.value)
234*1f5207b7SJohn Levon return 0;
235*1f5207b7SJohn Levon if (constraint_met(array_expr, offset))
236*1f5207b7SJohn Levon return 0;
237*1f5207b7SJohn Levon
238*1f5207b7SJohn Levon if (array_size > rl_max(abs_rl).uvalue)
239*1f5207b7SJohn Levon return 0;
240*1f5207b7SJohn Levon
241*1f5207b7SJohn Levon if (definitely_just_used_as_limiter(array_expr, offset))
242*1f5207b7SJohn Levon return 0;
243*1f5207b7SJohn Levon
244*1f5207b7SJohn Levon array_expr = strip_expr(array_expr);
245*1f5207b7SJohn Levon if (common_false_positives(array_expr, max))
246*1f5207b7SJohn Levon return 0;
247*1f5207b7SJohn Levon
248*1f5207b7SJohn Levon if (impossibly_high_comparison(offset))
249*1f5207b7SJohn Levon return 0;
250*1f5207b7SJohn Levon
251*1f5207b7SJohn Levon return 1;
252*1f5207b7SJohn Levon
253*1f5207b7SJohn Levon }
254*1f5207b7SJohn Levon
is_because_of_no_break(struct expression * offset)255*1f5207b7SJohn Levon static int is_because_of_no_break(struct expression *offset)
256*1f5207b7SJohn Levon {
257*1f5207b7SJohn Levon if (get_state_expr(loop_id, offset) == &loop_end)
258*1f5207b7SJohn Levon return 1;
259*1f5207b7SJohn Levon return 0;
260*1f5207b7SJohn Levon }
261*1f5207b7SJohn Levon
array_check(struct expression * expr)262*1f5207b7SJohn Levon static void array_check(struct expression *expr)
263*1f5207b7SJohn Levon {
264*1f5207b7SJohn Levon struct expression *array_expr;
265*1f5207b7SJohn Levon struct range_list *abs_rl;
266*1f5207b7SJohn Levon struct range_list *user_rl = NULL;
267*1f5207b7SJohn Levon sval_t hard_max = { .type = &int_ctype, };
268*1f5207b7SJohn Levon sval_t fuzzy_max = { .type = &int_ctype, };
269*1f5207b7SJohn Levon int array_size;
270*1f5207b7SJohn Levon struct expression *array_size_value, *comparison;
271*1f5207b7SJohn Levon struct expression *offset;
272*1f5207b7SJohn Levon sval_t max;
273*1f5207b7SJohn Levon char *name;
274*1f5207b7SJohn Levon int no_break = 0;
275*1f5207b7SJohn Levon
276*1f5207b7SJohn Levon if (!should_warn(expr))
277*1f5207b7SJohn Levon return;
278*1f5207b7SJohn Levon
279*1f5207b7SJohn Levon expr = strip_expr(expr);
280*1f5207b7SJohn Levon array_expr = get_array_base(expr);
281*1f5207b7SJohn Levon array_size = get_array_size(array_expr);
282*1f5207b7SJohn Levon offset = get_array_offset(expr);
283*1f5207b7SJohn Levon
284*1f5207b7SJohn Levon /*
285*1f5207b7SJohn Levon * Perhaps if the offset is out of bounds that means a constraint
286*1f5207b7SJohn Levon * applies or maybe it means we are on an impossible path. So test
287*1f5207b7SJohn Levon * again based on that assumption.
288*1f5207b7SJohn Levon *
289*1f5207b7SJohn Levon */
290*1f5207b7SJohn Levon array_size_value = value_expr(array_size);
291*1f5207b7SJohn Levon comparison = compare_expression(offset, SPECIAL_GTE, array_size_value);
292*1f5207b7SJohn Levon if (assume(comparison)) {
293*1f5207b7SJohn Levon if (!should_warn(expr)) {
294*1f5207b7SJohn Levon end_assume();
295*1f5207b7SJohn Levon return;
296*1f5207b7SJohn Levon }
297*1f5207b7SJohn Levon no_break = is_because_of_no_break(offset);
298*1f5207b7SJohn Levon end_assume();
299*1f5207b7SJohn Levon }
300*1f5207b7SJohn Levon
301*1f5207b7SJohn Levon get_absolute_rl(offset, &abs_rl);
302*1f5207b7SJohn Levon get_user_rl(offset, &user_rl);
303*1f5207b7SJohn Levon fake_get_hard_max(offset, &hard_max);
304*1f5207b7SJohn Levon get_fuzzy_max(offset, &fuzzy_max);
305*1f5207b7SJohn Levon
306*1f5207b7SJohn Levon array_expr = strip_expr(array_expr);
307*1f5207b7SJohn Levon name = expr_to_str(array_expr);
308*1f5207b7SJohn Levon
309*1f5207b7SJohn Levon if (user_rl)
310*1f5207b7SJohn Levon max = rl_max(user_rl);
311*1f5207b7SJohn Levon else
312*1f5207b7SJohn Levon max = rl_max(abs_rl);
313*1f5207b7SJohn Levon
314*1f5207b7SJohn Levon if (!option_spammy && is_subtract(offset))
315*1f5207b7SJohn Levon return;
316*1f5207b7SJohn Levon
317*1f5207b7SJohn Levon if (no_break) {
318*1f5207b7SJohn Levon sm_error("buffer overflow '%s' %d <= %s (assuming for loop doesn't break)",
319*1f5207b7SJohn Levon name, array_size, sval_to_str(max));
320*1f5207b7SJohn Levon } else if (user_rl) {
321*1f5207b7SJohn Levon sm_error("buffer overflow '%s' %d <= %s user_rl='%s'%s",
322*1f5207b7SJohn Levon name, array_size, sval_to_str(max), show_rl(user_rl),
323*1f5207b7SJohn Levon is_subtract(offset) ? " subtract" : "");
324*1f5207b7SJohn Levon } else {
325*1f5207b7SJohn Levon sm_error("buffer overflow '%s' %d <= %s%s",
326*1f5207b7SJohn Levon name, array_size, sval_to_str(max),
327*1f5207b7SJohn Levon is_subtract(offset) ? " subtract" : "");
328*1f5207b7SJohn Levon }
329*1f5207b7SJohn Levon
330*1f5207b7SJohn Levon free_string(name);
331*1f5207b7SJohn Levon }
332*1f5207b7SJohn Levon
check_index_overflow(int id)333*1f5207b7SJohn Levon void check_index_overflow(int id)
334*1f5207b7SJohn Levon {
335*1f5207b7SJohn Levon add_hook(&array_check, OP_HOOK);
336*1f5207b7SJohn Levon }
337*1f5207b7SJohn Levon
match_condition(struct expression * expr)338*1f5207b7SJohn Levon static void match_condition(struct expression *expr)
339*1f5207b7SJohn Levon {
340*1f5207b7SJohn Levon struct statement *stmt;
341*1f5207b7SJohn Levon
342*1f5207b7SJohn Levon if (expr->type != EXPR_COMPARE)
343*1f5207b7SJohn Levon return;
344*1f5207b7SJohn Levon if (expr->op != '<' && expr->op != SPECIAL_UNSIGNED_LT)
345*1f5207b7SJohn Levon return;
346*1f5207b7SJohn Levon
347*1f5207b7SJohn Levon stmt = expr_get_parent_stmt(expr);
348*1f5207b7SJohn Levon if (!stmt || stmt->type != STMT_ITERATOR)
349*1f5207b7SJohn Levon return;
350*1f5207b7SJohn Levon
351*1f5207b7SJohn Levon set_true_false_states_expr(loop_id, expr->left, NULL, &loop_end);
352*1f5207b7SJohn Levon }
353*1f5207b7SJohn Levon
set_undefined(struct sm_state * sm,struct expression * mod_expr)354*1f5207b7SJohn Levon static void set_undefined(struct sm_state *sm, struct expression *mod_expr)
355*1f5207b7SJohn Levon {
356*1f5207b7SJohn Levon if (sm->state == &loop_end)
357*1f5207b7SJohn Levon set_state(loop_id, sm->name, sm->sym, &undefined);
358*1f5207b7SJohn Levon }
359*1f5207b7SJohn Levon
check_index_overflow_loop_marker(int id)360*1f5207b7SJohn Levon void check_index_overflow_loop_marker(int id)
361*1f5207b7SJohn Levon {
362*1f5207b7SJohn Levon loop_id = id;
363*1f5207b7SJohn Levon
364*1f5207b7SJohn Levon add_hook(&match_condition, CONDITION_HOOK);
365*1f5207b7SJohn Levon add_modification_hook(loop_id, &set_undefined);
366*1f5207b7SJohn Levon }
367*1f5207b7SJohn Levon
368