smatch_integer_overflow.c

   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 = 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
 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 }