check_arm64_tagged.c

   1 /*
   2  * Copyright (C) 2019 ARM.
   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_extra.h"
  20 #include "smatch_function_hashtable.h"
  21
  22 static bool expr_has_memory_addr(struct expression *expr);
  23
  24 static DEFINE_HASHTABLE_SEARCH(search_symbol, char, char);
  25 static DEFINE_HASHTABLE_INSERT(insert_symbol, char, char);
  26 static struct hashtable *symbols;
  27
  28 static void match_assign(struct expression *expr)
  29 {
  30         char *left_name;
  31         struct symbol *left_sym;
  32
  33         left_name = expr_to_var_sym(expr->left, &left_sym);
  34         if (!left_name || !left_sym)
  35                 return;
  36
  37         /*
  38          * Once we have spotted a symbol of interest (one that may hold
  39          * an untagged memory address), we keep track of any assignments
  40          * made, such that we can also treat the assigned symbol as something
  41          * of interest. This tracking is limited in scope to the function.
  42          */
  43         if (expr_has_memory_addr(expr->right))
  44                 insert_symbol(symbols, left_name, left_name);
  45 }
  46
  47 static void match_endfunc(struct symbol *sym)
  48 {
  49         destroy_function_hashtable(symbols);
  50         symbols = create_function_hashtable(4000);
  51 }
  52
  53 static bool expr_has_untagged_symbol(struct expression *expr)
  54 {
  55         char *name;
  56         struct symbol *sym;
  57
  58         if (expr->type != EXPR_SYMBOL)
  59                 return false;
  60
  61         name = expr_to_var_sym(expr, &sym);
  62         if (!name || !sym)
  63                 return false;
  64
  65         /* See if this is something we already know is of interest */
  66         if (search_symbol(symbols, name))
  67                 return true;
  68
  69         return false;
  70 }
  71
  72 static bool expr_has_untagged_member(struct expression *expr)
  73 {
  74         if (expr->type != EXPR_DEREF)
  75                 return false;
  76
  77         if (!strcmp(expr->member->name, "vm_start") ||
  78             !strcmp(expr->member->name, "vm_end") ||
  79             !strcmp(expr->member->name, "addr_limit"))
  80                 return true;
  81
  82         return false;
  83 }
  84
  85 static bool expr_has_macro_with_name(struct expression *expr, const char *macro_name)
  86 {
  87         char *name;
  88
  89         if (expr->type == EXPR_PREOP && expr->op == '~')
  90                 expr = strip_expr(expr->unop);
  91
  92         name = get_macro_name(expr->pos);
  93         return (name && !strcmp(name, macro_name));
  94 }
  95
  96 static bool expr_has_untagged_macro(struct expression *expr)
  97 {
  98         if (expr_has_macro_with_name(expr, "PAGE_SIZE") ||
  99             expr_has_macro_with_name(expr, "PAGE_MASK") ||
 100             expr_has_macro_with_name(expr, "TASK_SIZE"))
 101                 return true;
 102
 103         /**
 104          * We can't detect a marco (such as PAGE_MASK) inside another macro
 105          * such as offset_in_page, therefore we have to detect the outer macro
 106          * instead.
 107          */
 108         if (expr_has_macro_with_name(expr, "offset_in_page"))
 109                 return true;
 110
 111         return false;
 112 }
 113
 114 /*
 115  * Identify expressions that contain memory addresses, in the future
 116  * we may use annotations on symbols or function parameters.
 117  */
 118 static bool expr_has_memory_addr(struct expression *expr)
 119 {
 120         if (expr->type == EXPR_PREOP || expr->type == EXPR_POSTOP)
 121                 expr = strip_expr(expr->unop);
 122
 123         if (expr_has_untagged_member(expr))
 124                 return true;
 125
 126         if (expr_has_untagged_macro(expr))
 127                 return true;
 128
 129         if (expr_has_untagged_symbol(expr))
 130                 return true;
 131
 132         return false;
 133 }
 134
 135 int rl_is_larger_or_equal(struct range_list *rl, sval_t sval)
 136 {
 137         struct data_range *tmp;
 138
 139         FOR_EACH_PTR(rl, tmp) {
 140                 if (sval_cmp(tmp->max, sval) >= 0)
 141                         return 1;
 142         } END_FOR_EACH_PTR(tmp);
 143         return 0;
 144 }
 145
 146 int rl_range_has_min_value(struct range_list *rl, sval_t sval)
 147 {
 148         struct data_range *tmp;
 149
 150         FOR_EACH_PTR(rl, tmp) {
 151                 if (!sval_cmp(tmp->min, sval)) {
 152                         return 1;
 153                 }
 154         } END_FOR_EACH_PTR(tmp);
 155         return 0;
 156 }
 157
 158 static bool rl_is_tagged(struct range_list *rl)
 159 {
 160         sval_t invalid = { .type = &ullong_ctype, .value = (1ULL << 56) };
 161         sval_t invalid_kernel = { .type = &ullong_ctype, .value = (0xff8ULL << 52) };
 162
 163         /*
 164          * We only care for tagged addresses, thus ignore anything where the
 165          * ranges of potential values cannot possibly have any of the top byte
 166          * bits set.
 167          */
 168         if (!rl_is_larger_or_equal(rl, invalid))
 169                 return false;
 170
 171         /*
 172          * Tagged addresses are untagged in the kernel by using sign_extend64 in
 173          * the untagged_addr macro. For userspace addresses bit 55 will always
 174          * be 0 and thus this has the effect of clearing the top byte. However
 175          * for kernel addresses this is not true and the top bits end up set to
 176          * all 1s. The untagged_addr macro results in leaving a gap in the range
 177          * of possible values which can exist, thus let's look for a tell-tale
 178          * range which starts from (0xff8ULL << 52).
 179          */
 180         if (rl_range_has_min_value(rl, invalid_kernel))
 181                 return false;
 182
 183         return true;
 184 }
 185
 186 static void match_condition(struct expression *expr)
 187 {
 188         struct range_list *rl = NULL;
 189         struct expression *val = NULL;
 190         struct symbol *type;
 191         char *var_name;
 192
 193         /*
 194          * Match instances where something is compared against something
 195          * else - we include binary operators as these are commonly used
 196          * to make a comparison, e.g. if (start & ~PAGE_MASK).
 197          */
 198         if (expr->type != EXPR_COMPARE &&
 199             expr->type != EXPR_BINOP)
 200                 return;
 201
 202         /*
 203          * Look on both sides of the comparison for something that shouldn't
 204          * be compared with a tagged address, e.g. macros such as PAGE_MASK
 205          * or struct members named .vm_start.
 206          */
 207         if (expr_has_memory_addr(expr->left))
 208                 val = expr->right;
 209
 210         /*
 211          * The macro 'offset_in_page' has the PAGE_MASK macro inside it, this
 212          * results in 'expr_has_memory_addr' returning true for both sides. To
 213          * work around this we assume PAGE_MASK (or similar) is on the right
 214          * side, thus we do the following test last.
 215          */
 216         if (expr_has_memory_addr(expr->right))
 217                 val = expr->left;
 218
 219         if (!val)
 220                 return;
 221
 222         /* We only care about memory addresses which are 64 bits */
 223         type = get_type(val);
 224         if (!type || type_bits(type) != 64)
 225                 return;
 226
 227         /* We only care for comparison against user originated data */
 228         if (!get_user_rl(val, &rl))
 229                 return;
 230
 231         /* We only care for tagged addresses */
 232         if (!rl_is_tagged(rl))
 233                 return;
 234
 235         /* Finally, we believe we may have spotted a risky comparison */
 236         var_name = expr_to_var(val);
 237         if (var_name)
 238                 sm_warning("comparison of a potentially tagged address (%s, %d, %s)", get_function(), get_param_num(val), var_name);
 239 }
 240
 241 void check_arm64_tagged(int id)
 242 {
 243         char *arch;
 244
 245         if (option_project != PROJ_KERNEL)
 246                 return;
 247
 248         /* Limit to aarch64 */
 249         arch = getenv("ARCH");
 250         if (!arch || strcmp(arch, "arm64"))
 251                 return;
 252
 253         symbols = create_function_hashtable(4000);
 254
 255         add_hook(&match_assign, ASSIGNMENT_HOOK);
 256         add_hook(&match_condition, CONDITION_HOOK);
 257         add_hook(&match_endfunc, END_FUNC_HOOK);
 258 }