smatch_strlen.c

   1 /*
   2  * Copyright (C) 2013 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 <stdlib.h>
  19 #include <errno.h>
  20 #include "parse.h"
  21 #include "smatch.h"
  22 #include "smatch_slist.h"
  23 #include "smatch_extra.h"
  24
  25 #define UNKNOWN_SIZE (-1)
  26
  27 static int my_strlen_id;
  28 /*
  29  * The trick with the my_equiv_id is that if we have:
  30  * foo = strlen(bar);
  31  * We don't know at that point what the strlen() is but we know it's equivalent
  32  * to "foo" so maybe we can find the value of "foo" later.
  33  */
  34 static int my_equiv_id;
  35
  36 static struct smatch_state *size_to_estate(int size)
  37 {
  38         sval_t sval;
  39
  40         sval.type = &int_ctype;
  41         sval.value = size;
  42
  43         return alloc_estate_sval(sval);
  44 }
  45
  46 static struct smatch_state *unmatched_strlen_state(struct sm_state *sm)
  47 {
  48         return size_to_estate(UNKNOWN_SIZE);
  49 }
  50
  51 static void set_strlen_undefined(struct sm_state *sm, struct expression *mod_expr)
  52 {
  53         set_state(sm->owner, sm->name, sm->sym, size_to_estate(UNKNOWN_SIZE));
  54 }
  55
  56 static void set_strlen_equiv_undefined(struct sm_state *sm, struct expression *mod_expr)
  57 {
  58         set_state(sm->owner, sm->name, sm->sym, &undefined);
  59 }
  60
  61 static void match_string_assignment(struct expression *expr)
  62 {
  63         struct range_list *rl;
  64
  65         if (expr->op != '=')
  66                 return;
  67         if (!get_implied_strlen(expr->right, &rl))
  68                 return;
  69         set_state_expr(my_strlen_id, expr->left, alloc_estate_rl(clone_rl(rl)));
  70 }
  71
  72 bool is_strlen(struct expression *expr)
  73 {
  74         if (!expr || expr->type != EXPR_CALL)
  75                 return false;
  76
  77         if (sym_name_is("strlen", expr->fn) ||
  78             sym_name_is("__builtin_strlen", expr->fn) ||
  79             sym_name_is("__fortify_strlen", expr->fn))
  80                 return true;
  81
  82         return false;
  83 }
  84
  85 static void match_strlen(const char *fn, struct expression *expr, void *unused)
  86 {
  87         struct expression *right;
  88         struct expression *str;
  89         struct expression *len_expr;
  90         char *len_name;
  91         struct smatch_state *state;
  92
  93         right = strip_expr(expr->right);
  94         str = get_argument_from_call_expr(right->args, 0);
  95         len_expr = strip_expr(expr->left);
  96
  97         len_name = expr_to_var(len_expr);
  98         if (!len_name)
  99                 return;
 100
 101         state = __alloc_smatch_state(0);
 102         state->name = len_name;
 103         state->data = len_expr;
 104
 105         set_state_expr(my_equiv_id, str, state);
 106 }
 107
 108 static void match_strlen_condition(struct expression *expr)
 109 {
 110         struct expression *left;
 111         struct expression *right;
 112         struct expression *str = NULL;
 113         int strlen_left = 0;
 114         int strlen_right = 0;
 115         sval_t sval;
 116         struct smatch_state *true_state = NULL;
 117         struct smatch_state *false_state = NULL;
 118         int op;
 119
 120         expr = strip_expr(expr);
 121         if (expr->type != EXPR_COMPARE)
 122                 return;
 123
 124         left = strip_expr(expr->left);
 125         right = strip_expr(expr->right);
 126
 127         if (left->type == EXPR_CALL && is_strlen(left)) {
 128                 str = get_argument_from_call_expr(left->args, 0);
 129                 strlen_left = 1;
 130         }
 131         if (right->type == EXPR_CALL && is_strlen(right)) {
 132                 str = get_argument_from_call_expr(right->args, 0);
 133                 strlen_right = 1;
 134         }
 135
 136         if (!strlen_left && !strlen_right)
 137                 return;
 138         if (strlen_left && strlen_right)
 139                 return;
 140
 141         op = expr->op;
 142         if (strlen_left) {
 143                 if (!get_value(right, &sval))
 144                         return;
 145         } else {
 146                 op = flip_comparison(op);
 147                 if (!get_value(left, &sval))
 148                         return;
 149         }
 150
 151         switch (op) {
 152         case '<':
 153         case SPECIAL_UNSIGNED_LT:
 154                 true_state = size_to_estate(sval.value - 1);
 155                 break;
 156         case SPECIAL_LTE:
 157         case SPECIAL_UNSIGNED_LTE:
 158                 true_state = size_to_estate(sval.value);
 159                 break;
 160         case SPECIAL_EQUAL:
 161                 true_state = size_to_estate(sval.value);
 162                 break;
 163         case SPECIAL_NOTEQUAL:
 164                 false_state = size_to_estate(sval.value);
 165                 break;
 166         case SPECIAL_GTE:
 167         case SPECIAL_UNSIGNED_GTE:
 168                 false_state = size_to_estate(sval.value - 1);
 169                 break;
 170         case '>':
 171         case SPECIAL_UNSIGNED_GT:
 172                 false_state = size_to_estate(sval.value);
 173                 break;
 174         }
 175
 176         set_true_false_states_expr(my_strlen_id, str, true_state, false_state);
 177 }
 178
 179 static void match_snprintf(const char *fn, struct expression *expr, void *unused)
 180 {
 181         struct expression *dest;
 182         struct expression *dest_size_expr;
 183         sval_t limit_size;
 184
 185         dest = get_argument_from_call_expr(expr->args, 0);
 186         dest_size_expr = get_argument_from_call_expr(expr->args, 1);
 187
 188         if (!get_implied_value(dest_size_expr, &limit_size))
 189                 return;
 190
 191         if (limit_size.value <= 0)
 192                 return;
 193
 194         set_state_expr(my_strlen_id, dest, size_to_estate(limit_size.value - 1));
 195 }
 196
 197 static void match_strlcpycat(const char *fn, struct expression *expr, void *unused)
 198 {
 199         struct expression *dest;
 200         struct expression *src;
 201         struct expression *limit_expr;
 202         int src_len;
 203         sval_t limit;
 204
 205         dest = get_argument_from_call_expr(expr->args, 0);
 206         src = get_argument_from_call_expr(expr->args, 1);
 207         limit_expr = get_argument_from_call_expr(expr->args, 2);
 208
 209         src_len = get_size_from_strlen(src);
 210
 211         if (!get_implied_max(limit_expr, &limit))
 212                 return;
 213         if (limit.value < 0 || limit.value > INT_MAX)
 214                 return;
 215         if (src_len != 0 && strcmp(fn, "strcpy") == 0 && src_len < limit.value)
 216                 limit.value = src_len;
 217
 218         set_state_expr(my_strlen_id, dest, size_to_estate(limit.value - 1));
 219 }
 220
 221 static void match_strcpy(const char *fn, struct expression *expr, void *unused)
 222 {
 223         struct expression *dest;
 224         struct expression *src;
 225         int src_len;
 226
 227         dest = get_argument_from_call_expr(expr->args, 0);
 228         src = get_argument_from_call_expr(expr->args, 1);
 229
 230         src_len = get_size_from_strlen(src);
 231         if (src_len == 0)
 232                 return;
 233
 234         set_state_expr(my_strlen_id, dest, size_to_estate(src_len - 1));
 235 }
 236
 237 static int get_strlen_from_string(struct expression *expr, struct range_list **rl)
 238 {
 239         sval_t sval;
 240         int len;
 241
 242         len = expr->string->length;
 243         sval = sval_type_val(&int_ctype, len - 1);
 244         *rl = alloc_rl(sval, sval);
 245         return 1;
 246 }
 247
 248
 249 static int get_strlen_from_state(struct expression *expr, struct range_list **rl)
 250 {
 251         struct smatch_state *state;
 252
 253         state = get_state_expr(my_strlen_id, expr);
 254         if (!state)
 255                 return 0;
 256         *rl = estate_rl(state);
 257         return 1;
 258 }
 259
 260 static int get_strlen_from_equiv(struct expression *expr, struct range_list **rl)
 261 {
 262         struct smatch_state *state;
 263
 264         state = get_state_expr(my_equiv_id, expr);
 265         if (!state || !state->data)
 266                 return 0;
 267         if (!get_implied_rl((struct expression *)state->data, rl))
 268                 return 0;
 269         return 1;
 270 }
 271
 272 /*
 273  * This returns the strlen() without the NUL char.
 274  */
 275 int get_implied_strlen(struct expression *expr, struct range_list **rl)
 276 {
 277
 278         *rl = NULL;
 279
 280         expr = strip_expr(expr);
 281         if (expr->type == EXPR_STRING)
 282                 return get_strlen_from_string(expr, rl);
 283
 284         if (get_strlen_from_state(expr, rl))
 285                 return 1;
 286         if (get_strlen_from_equiv(expr, rl))
 287                 return 1;
 288         return 0;
 289 }
 290
 291 int get_size_from_strlen(struct expression *expr)
 292 {
 293         struct range_list *rl;
 294         sval_t max;
 295
 296         if (!get_implied_strlen(expr, &rl))
 297                 return 0;
 298         max = rl_max(rl);
 299         if (sval_is_negative(max) || sval_is_max(max))
 300                 return 0;
 301
 302         return max.value + 1; /* add one because strlen doesn't include the NULL */
 303 }
 304
 305 void set_param_strlen(const char *name, struct symbol *sym, char *key, char *value)
 306 {
 307         struct range_list *rl = NULL;
 308         struct smatch_state *state;
 309         char fullname[256];
 310
 311         if (strncmp(key, "$", 1) != 0)
 312                 return;
 313
 314         snprintf(fullname, 256, "%s%s", name, key + 1);
 315
 316         str_to_rl(&int_ctype, value, &rl);
 317         if (!rl || is_whole_rl(rl))
 318                 return;
 319         state = alloc_estate_rl(rl);
 320         set_state(my_strlen_id, fullname, sym, state);
 321 }
 322
 323 static void match_call(struct expression *expr)
 324 {
 325         struct expression *arg;
 326         struct range_list *rl;
 327         int i;
 328
 329         i = 0;
 330         FOR_EACH_PTR(expr->args, arg) {
 331                 if (!get_implied_strlen(arg, &rl))
 332                         continue;
 333                 if (!is_whole_rl(rl))
 334                         sql_insert_caller_info(expr, STR_LEN, i, "$", show_rl(rl));
 335                 i++;
 336         } END_FOR_EACH_PTR(arg);
 337 }
 338
 339 static void struct_member_callback(struct expression *call, int param, char *printed_name, struct sm_state *sm)
 340 {
 341         if (sm->state == &merged)
 342                 return;
 343         sql_insert_caller_info(call, STR_LEN, param, printed_name, sm->state->name);
 344 }
 345
 346 void register_strlen(int id)
 347 {
 348         my_strlen_id = id;
 349
 350         set_dynamic_states(my_strlen_id);
 351
 352         add_unmatched_state_hook(my_strlen_id, &unmatched_strlen_state);
 353
 354         select_caller_info_hook(set_param_strlen, STR_LEN);
 355         add_hook(&match_string_assignment, ASSIGNMENT_HOOK);
 356
 357         add_modification_hook(my_strlen_id, &set_strlen_undefined);
 358         add_merge_hook(my_strlen_id, &merge_estates);
 359         add_hook(&match_call, FUNCTION_CALL_HOOK);
 360         add_member_info_callback(my_strlen_id, struct_member_callback);
 361         add_hook(&match_strlen_condition, CONDITION_HOOK);
 362
 363         add_function_hook("snprintf", &match_snprintf, NULL);
 364
 365         add_function_hook("strscpy", &match_strlcpycat, NULL);
 366         add_function_hook("strlcpy", &match_strlcpycat, NULL);
 367         add_function_hook("strlcat", &match_strlcpycat, NULL);
 368         add_function_hook("strcpy", &match_strcpy, NULL);
 369         add_function_hook("__builtin_strcpy", &match_strcpy, NULL);
 370 }
 371
 372 void register_strlen_equiv(int id)
 373 {
 374         my_equiv_id = id;
 375         set_dynamic_states(my_equiv_id);
 376         add_function_assign_hook("strlen", &match_strlen, NULL);
 377         add_function_assign_hook("__builtin_strlen", &match_strlen, NULL);
 378         add_function_assign_hook("__fortify_strlen", &match_strlen, NULL);
 379         add_modification_hook(my_equiv_id, &set_strlen_equiv_undefined);
 380 }
 381