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