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