check_memcpy_overflow.c

   1 /*
   2  * Copyright (C) 2010 Dan Carpenter.
   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 "parse.h"
  20 #include "smatch.h"
  21 #include "smatch_slist.h"
  22 #include "smatch_extra.h"
  23
  24 struct limiter {
  25         int buf_arg;
  26         int limit_arg;
  27 };
  28 static struct limiter b0_l2 = {0, 2};
  29 static struct limiter b1_l2 = {1, 2};
  30
  31 struct string_list *ignored_structs;
  32
  33 static int get_the_max(struct expression *expr, sval_t *sval)
  34 {
  35         struct range_list *rl;
  36
  37         if (get_hard_max(expr, sval))
  38                 return 1;
  39         if (!option_spammy)
  40                 return 0;
  41         if (get_fuzzy_max(expr, sval))
  42                 return 1;
  43         if (!is_user_data(expr))
  44                 return 0;
  45         if (!get_user_rl(expr, &rl))
  46                 return 0;
  47         *sval = rl_max(rl);
  48         return 1;
  49 }
  50
  51 static int bytes_to_end_of_struct(struct expression *expr)
  52 {
  53         struct expression *deref;
  54         struct symbol *type;
  55         int struct_bytes;
  56         int offset;
  57
  58         if (expr->type == EXPR_PREOP && expr->op == '&')
  59                 expr = strip_parens(expr->unop);
  60         else {
  61                 type = get_type(expr);
  62                 if (!type || type->type != SYM_ARRAY)
  63                         return 0;
  64         }
  65         if (expr->type != EXPR_DEREF || !expr->member)
  66                 return 0;
  67         deref = expr->deref;
  68         if (deref->type == EXPR_PREOP && deref->op == '*')
  69                 deref = deref->unop;
  70         struct_bytes = get_array_size_bytes_max(deref);
  71         if (struct_bytes <= 0) {
  72                 type = get_type(expr->deref);
  73                 struct_bytes = type_bytes(type);
  74         }
  75         offset = get_member_offset_from_deref(expr);
  76         if (offset <= 0)
  77                 return 0;
  78         return struct_bytes - expr->member_offset;
  79 }
  80
  81 static int size_of_union(struct expression *expr)
  82 {
  83         struct symbol *type;
  84
  85         if (expr->type != EXPR_PREOP || expr->op != '&')
  86                 return 0;
  87         expr = strip_parens(expr->unop);
  88         if (expr->type != EXPR_DEREF || !expr->member)
  89                 return 0;
  90         expr = expr->unop;
  91         type = get_type(expr);
  92         if (!type || type->type != SYM_UNION)
  93                 return 0;
  94         return type_bytes(type);
  95 }
  96
  97 static int is_likely_multiple(int has, int needed, struct expression *limit)
  98 {
  99         sval_t mult;
 100
 101         limit = strip_parens(limit);
 102         if (limit->type != EXPR_BINOP || limit->op != '*')
 103                 return 0;
 104         if (!get_value(limit->left, &mult))
 105                 return 0;
 106         if (has * mult.value == needed)
 107                 return 1;
 108         if (!get_value(limit->right, &mult))
 109                 return 0;
 110         if (has * mult.value == needed)
 111                 return 1;
 112
 113         return 0;
 114 }
 115
 116 static int name_in_union(struct symbol *type, const char *name)
 117 {
 118         struct symbol *tmp;
 119
 120         if (type->type == SYM_NODE)
 121                 type = get_real_base_type(type);
 122         if (!type || type->type != SYM_UNION)
 123                 return 0;
 124
 125         FOR_EACH_PTR(type->symbol_list, tmp) {
 126                 if (tmp->ident &&
 127                     strcmp(name, tmp->ident->name) == 0)
 128                         return 1;
 129         } END_FOR_EACH_PTR(tmp);
 130
 131         return 0;
 132 }
 133
 134 static int ends_on_struct_member_boundary(struct expression *expr, int needed)
 135 {
 136         struct symbol *type, *tmp;
 137         int offset;
 138         int size;
 139         int found = 0;
 140
 141         expr = strip_expr(expr);
 142         if (expr->type == EXPR_PREOP && expr->op == '&') {
 143                 expr = strip_parens(expr->unop);
 144         } else {
 145                 type = get_type(expr);
 146                 if (!type || type->type != SYM_ARRAY)
 147                         return 0;
 148         }
 149         if (expr->type != EXPR_DEREF || !expr->member)
 150                 return 0;
 151
 152         type = get_type(expr->unop);
 153         if (!type)
 154                 return 0;
 155         if (type->type == SYM_UNION) {
 156                 struct expression *unop = strip_expr(expr->unop);
 157
 158                 if (unop->type != EXPR_DEREF)
 159                         return 0;
 160                 type = get_type(unop->unop);
 161                 if (!type)
 162                         return 0;
 163         }
 164         if (type->type != SYM_STRUCT)
 165                 return 0;
 166
 167         offset = 0;
 168         FOR_EACH_PTR(type->symbol_list, tmp) {
 169                 if (!found) {
 170                         if ((tmp->ident &&
 171                              strcmp(expr->member->name, tmp->ident->name) == 0) ||
 172                             name_in_union(tmp, expr->member->name))
 173                                 found = 1;
 174
 175                         if (!type->ctype.attribute->is_packed)
 176                             offset = ALIGN(offset, tmp->ctype.alignment);
 177
 178                         offset += type_bytes(tmp);
 179                         size = type_bytes(tmp);
 180                         continue;
 181                 }
 182
 183                 /* if there is a hole then fail. */
 184                 if (!type->ctype.attribute->is_packed &&
 185                     offset != ALIGN(offset, tmp->ctype.alignment))
 186                         return 0;
 187                 offset += type_bytes(tmp);
 188                 size += type_bytes(tmp);
 189
 190                 if (size == needed)
 191                         return 1;
 192                 if (size > needed)
 193                         return 0;
 194         } END_FOR_EACH_PTR(tmp);
 195         return 0;
 196 }
 197
 198 static int is_one_element_array(struct expression *expr)
 199 {
 200         struct symbol *type;
 201         sval_t sval;
 202
 203         if (expr->type == EXPR_PREOP && expr->op == '&')
 204                 expr = expr->unop;
 205         if (expr->type == EXPR_BINOP) /* array elements foo[5] */
 206                 return 0;
 207
 208         type = get_type(expr);
 209         if (!type)
 210                 return 0;
 211         if (!type || type->type != SYM_ARRAY)
 212                 return 0;
 213
 214         if (!get_implied_value(type->array_size, &sval))
 215                 return 0;
 216
 217         if (sval.value == 1)
 218                 return 1;
 219         return 0;
 220 }
 221
 222 static int is_ignored_struct(struct expression *expr)
 223 {
 224         struct symbol *type;
 225
 226         type = get_type(expr);
 227         if (!type)
 228                 return 0;
 229         if (type->type == SYM_PTR)
 230                 type = get_real_base_type(type);
 231         if (type->type != SYM_STRUCT)
 232                 return 0;
 233         if (!type->ident)
 234                 return 0;
 235         if (list_has_string(ignored_structs, type->ident->name))
 236                 return 1;
 237         return 0;
 238 }
 239
 240 static void match_limited(const char *fn, struct expression *expr, void *_limiter)
 241 {
 242         struct limiter *limiter = (struct limiter *)_limiter;
 243         struct expression *dest;
 244         struct expression *limit;
 245         char *dest_name = NULL;
 246         sval_t needed;
 247         int has;
 248
 249         dest = get_argument_from_call_expr(expr->args, limiter->buf_arg);
 250         limit = get_argument_from_call_expr(expr->args, limiter->limit_arg);
 251         if (!get_the_max(limit, &needed))
 252                 return;
 253         has = get_array_size_bytes_max(dest);
 254         if (!has)
 255                 return;
 256         if (has >= needed.value)
 257                 return;
 258
 259         if (needed.value == bytes_to_end_of_struct(dest))
 260                 return;
 261
 262         if (needed.value <= size_of_union(dest))
 263                 return;
 264
 265         if (is_likely_multiple(has, needed.value, limit))
 266                 return;
 267
 268         if (ends_on_struct_member_boundary(dest, needed.value))
 269                 return;
 270
 271         if (is_one_element_array(dest))
 272                 return;
 273
 274         if (is_ignored_struct(dest))
 275                 return;
 276
 277         dest_name = expr_to_str(dest);
 278         sm_msg("error: %s() '%s' too small (%d vs %s)", fn, dest_name, has, sval_to_str(needed));
 279         free_string(dest_name);
 280 }
 281
 282 static void register_funcs_from_file(void)
 283 {
 284         char name[256];
 285         struct token *token;
 286         const char *func;
 287         int size, buf;
 288         struct limiter *limiter;
 289
 290         snprintf(name, 256, "%s.sizeof_param", option_project_str);
 291         name[255] = '\0';
 292         token = get_tokens_file(name);
 293         if (!token)
 294                 return;
 295         if (token_type(token) != TOKEN_STREAMBEGIN)
 296                 return;
 297         token = token->next;
 298         while (token_type(token) != TOKEN_STREAMEND) {
 299                 if (token_type(token) != TOKEN_IDENT)
 300                         break;
 301                 func = show_ident(token->ident);
 302
 303                 token = token->next;
 304                 if (token_type(token) != TOKEN_NUMBER)
 305                         break;
 306                 size = atoi(token->number);
 307
 308                 token = token->next;
 309                 if (token_type(token) == TOKEN_SPECIAL) {
 310                         if (token->special != '-')
 311                                 break;
 312                         token = token->next;
 313                         if (token_type(token) != TOKEN_NUMBER)
 314                                 break;
 315                         token = token->next;
 316                         continue;
 317
 318                 }
 319                 if (token_type(token) != TOKEN_NUMBER)
 320                         break;
 321                 buf = atoi(token->number);
 322
 323                 limiter = malloc(sizeof(*limiter));
 324                 limiter->limit_arg = size;
 325                 limiter->buf_arg = buf;
 326
 327                 add_function_hook(func, &match_limited, limiter);
 328
 329                 token = token->next;
 330         }
 331         if (token_type(token) != TOKEN_STREAMEND)
 332                 printf("internal: error parsing '%s'\n", name);
 333         clear_token_alloc();
 334 }
 335
 336 static void register_ignored_structs_from_file(void)
 337 {
 338         char name[256];
 339         struct token *token;
 340         const char *struct_type;
 341
 342         snprintf(name, 256, "%s.ignore_memcpy_struct_overflows", option_project_str);
 343         name[255] = '\0';
 344         token = get_tokens_file(name);
 345         if (!token)
 346                 return;
 347         if (token_type(token) != TOKEN_STREAMBEGIN)
 348                 return;
 349         token = token->next;
 350         while (token_type(token) != TOKEN_STREAMEND) {
 351                 if (token_type(token) != TOKEN_IDENT)
 352                         return;
 353
 354                 struct_type = show_ident(token->ident);
 355                 insert_string(&ignored_structs, alloc_string(struct_type));
 356
 357                 token = token->next;
 358         }
 359         clear_token_alloc();
 360 }
 361
 362 void check_memcpy_overflow(int id)
 363 {
 364         register_funcs_from_file();
 365         register_ignored_structs_from_file();
 366         add_function_hook("memcmp", &match_limited, &b0_l2);
 367         add_function_hook("memcmp", &match_limited, &b1_l2);
 368         if (option_project == PROJ_KERNEL) {
 369                 add_function_hook("copy_to_user", &match_limited, &b1_l2);
 370                 add_function_hook("_copy_to_user", &match_limited, &b1_l2);
 371                 add_function_hook("__copy_to_user", &match_limited, &b1_l2);
 372                 add_function_hook("copy_from_user", &match_limited, &b0_l2);
 373                 add_function_hook("_copy_from_user", &match_limited, &b0_l2);
 374                 add_function_hook("__copy_from_user", &match_limited, &b0_l2);
 375         }
 376 }