1 /*
2 * Copyright (C) 2015 Oracle.
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 "smatch.h"
19 #include "smatch_slist.h"
20 #include "smatch_extra.h"
21
22 static int my_id;
23 static int link_id;
24
25 static struct smatch_state *safe_state(struct expression *expr)
26 {
27 struct smatch_state *state;
28
29 state = __alloc_smatch_state(0);
30 expr = strip_expr(expr);
31 state->name = alloc_sname("safe");
32 state->data = expr;
33 return state;
34 }
35
36 static char *save_links(struct expression *expr, struct symbol **sym, struct var_sym_list **vsl)
37 {
38 struct var_sym *vs;
39 char *name;
40
41 name = expr_to_chunk_sym_vsl(expr, sym, vsl);
42 if (!name || !*vsl) {
43 free_string(name);
44 return NULL;
45 }
46
47 FOR_EACH_PTR(*vsl, vs) {
48 store_link(link_id, vs->var, vs->sym, name, *sym);
49 } END_FOR_EACH_PTR(vs);
50
51 return name;
52 }
53
54 static void match_divide(struct expression *expr)
55 {
56 struct expression *left, *right, *binop;
57 struct symbol *type;
58 char *name;
59 struct symbol *sym;
60 struct var_sym_list *vsl;
61 sval_t max;
62
63 if (expr->type != EXPR_COMPARE)
64 return;
65 if (expr->op != '>' && expr->op != SPECIAL_UNSIGNED_GT &&
66 expr->op != SPECIAL_GTE && expr->op != SPECIAL_UNSIGNED_GTE)
67 return;
68
69 left = strip_parens(expr->left);
70 right = strip_parens(expr->right);
71
72 if (right->type != EXPR_BINOP || right->op != '/')
73 return;
74 if (!get_value(right->left, &max))
75 return;
76 if (max.value != INT_MAX && max.value != UINT_MAX &&
77 max.value != LLONG_MAX && max.uvalue != ULLONG_MAX)
78 return;
79
80 type = get_type(expr);
81 if (!type)
82 return;
83 if (type_bits(type) != 32 && type_bits(type) != 64)
84 return;
85
86
87 binop = binop_expression(left, '*', right->right);
88
89 name = save_links(binop, &sym, &vsl);
90 if (!name)
91 return;
92 set_true_false_states(my_id, name, sym, NULL, safe_state(binop));
93 free_string(name);
94 }
95
96 static void match_overflow_to_less_than(struct expression *expr)
97 {
98 struct expression *left, *right;
99 struct symbol *type;
100 char *name;
101 struct symbol *sym;
102 struct var_sym_list *vsl;
103
104 if (expr->type != EXPR_COMPARE)
105 return;
106 if (expr->op != '<' && expr->op != SPECIAL_UNSIGNED_LT)
107 return;
108
109 left = strip_parens(expr->left);
110 right = strip_parens(expr->right);
111
112 if (left->op != '+')
113 return;
114
115 type = get_type(expr);
116 if (!type)
117 return;
118 if (type_bits(type) != 32 && type_bits(type) != 64)
119 return;
120
121 if (!expr_equiv(left->left, right) && !expr_equiv(left->right, right))
122 return;
123
124 name = save_links(left, &sym, &vsl);
125 if (!name)
126 return;
127 set_true_false_states(my_id, name, sym, NULL, safe_state(left));
128 free_string(name);
129 }
130
131 static void match_condition(struct expression *expr)
132 {
133 match_overflow_to_less_than(expr);
134 match_divide(expr);
135 }
136
137 int can_integer_overflow(struct symbol *type, struct expression *expr)
138 {
139 int op;
140 sval_t lmax, rmax, res;
141
142 if (!type)
143 type = &int_ctype;
144
145 expr = strip_expr(expr);
146
147 if (expr->type == EXPR_ASSIGNMENT) {
148 switch(expr->op) {
149 case SPECIAL_MUL_ASSIGN:
150 op = '*';
151 break;
152 case SPECIAL_ADD_ASSIGN:
153 op = '+';
154 break;
155 case SPECIAL_SHL_ASSIGN:
156 op = SPECIAL_LEFTSHIFT;
157 break;
158 default:
159 return 0;
160 }
161 } else if (expr->type == EXPR_BINOP) {
162 if (expr->op != '*' && expr->op != '+' && expr->op != SPECIAL_LEFTSHIFT)
163 return 0;
164 op = expr->op;
165 } else {
166 return 0;
167 }
168
169 get_absolute_max(expr->left, &lmax);
170 get_absolute_max(expr->right, &rmax);
171
172 if (sval_binop_overflows(lmax, op, rmax))
173 return 1;
174
175 res = sval_binop(lmax, op, rmax);
176 if (sval_cmp(res, sval_type_max(type)) > 0)
177 return 1;
178 return 0;
179 }
180
181 int can_integer_overflow_expr(struct expression *expr)
182 {
183 struct symbol *type;
184 struct smatch_state *state;
185 char *name;
186 struct symbol *sym;
187 int ret;
188
189 type = get_type(expr);
190 if (!type)
191 return 0;
192
193 if (!can_integer_overflow(type, expr))
194 return 0;
195
196 name = expr_to_known_chunk_sym(expr, &sym);
197 if (!name || !sym)
198 goto free;
199
200 state = get_state(my_id, name, sym);
201 if (state && state->data)
202 ret = 0;
203 free:
204 free_string(name);
205 return ret;
206 }
207
208 static int get_arg_nr(struct expression *call, struct expression *expr)
209 {
210 struct expression *arg;
211 int i;
212
213 i = -1;
214 FOR_EACH_PTR(call->args, arg) {
215 i++;
216 if (expr_equiv(arg, expr))
217 return i;
218 } END_FOR_EACH_PTR(arg);
219
220 return -1;
221 }
222
223 static void check_links(struct expression *call, struct expression *arg, int nr, struct sm_state *sm, void *_vsl)
224 {
225 struct var_sym_list *vsl = _vsl;
226 struct var_sym *vs;
227 struct smatch_state *state;
228 struct expression *expr;
229 int left = -1;
230 int right = -1;
231
232 FOR_EACH_PTR(vsl, vs) {
233 state = get_state(my_id, vs->var, vs->sym);
234 if (!state || !state->data)
235 continue;
236
237 expr = state->data;
238
239 if (expr_equiv(arg, expr->left)) {
240 left = nr;
241 right = get_arg_nr(call, expr->right);
242 } else if (expr_equiv(arg, expr->right)) {
243 left = get_arg_nr(call, expr->left);
244 right = nr;
245 }
246
247 if (left == -1 || right == -1)
248 continue;
249
250 left = -1;
251 right = -1;
252 } END_FOR_EACH_PTR(vs);
253 }
254
255 static void match_call_info(struct expression *call)
256 {
257 struct expression *arg;
258 struct sm_state *link;
259 struct stree *done = NULL;
260 int i;
261
262 i = -1;
263 FOR_EACH_PTR(call->args, arg) {
264 i++;
265
266 link = get_sm_state_expr(link_id, arg);
267 if (!link)
268 continue;
269
270 if (get_state_stree(done, my_id, link->state->name, NULL))
271 continue;
272 // set_state_stree(&done, my_id, link->state->name, NULL, &undefined);
273
274 check_links(call, arg, i, link, link->state->data);
275 } END_FOR_EACH_PTR(arg);
276
277 free_stree(&done);
278 }
279
280 void register_integer_overflow(int id)
281 {
282 my_id = id;
283 set_dynamic_states(my_id);
284 add_hook(&match_condition, CONDITION_HOOK);
285 add_hook(&match_call_info, FUNCTION_CALL_HOOK);
286 }
287
288 void register_integer_overflow_links(int id)
289 {
290 link_id = id;
291 set_up_link_functions(my_id, link_id);
292 }