xref: /illumos-gate/usr/src/tools/smatch/src/smatch_integer_overflow.c (revision c85f09cc92abd00c84e58ec9f0f5d942906cb713)
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 
safe_state(struct expression * expr)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 
save_links(struct expression * expr,struct symbol ** sym,struct var_sym_list ** vsl)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 
match_divide(struct expression * expr)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 
match_overflow_to_less_than(struct expression * expr)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 
match_condition(struct expression * expr)131 static void match_condition(struct expression *expr)
132 {
133 	match_overflow_to_less_than(expr);
134 	match_divide(expr);
135 }
136 
can_integer_overflow(struct symbol * type,struct expression * expr)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 
can_integer_overflow_expr(struct expression * expr)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 = 1;
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 
get_arg_nr(struct expression * call,struct expression * expr)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 
check_links(struct expression * call,struct expression * arg,int nr,struct sm_state * sm,void * _vsl)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 
match_call_info(struct expression * call)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 
register_integer_overflow(int id)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 
register_integer_overflow_links(int id)288 void register_integer_overflow_links(int id)
289 {
290 	link_id = id;
291 	set_up_link_functions(my_id, link_id);
292 }
293