san/kasan_dynamic_blacklist.c

   1 #include <sys/queue.h>
   2 #include <kern/backtrace.h>
   3 #include <kern/kalloc.h>
   4 #include <kern/assert.h>
   5 #include <kern/debug.h>
   6 #include <kern/zalloc.h>
   7 #include <kern/simple_lock.h>
   8 #include <kern/locks.h>
   9 #include <machine/machine_routines.h>
  10 #include <libkern/libkern.h>
  11 #include <libkern/tree.h>
  12 #include <libkern/kernel_mach_header.h>
  13 #include <libkern/OSKextLib.h>
  14 #include <mach-o/loader.h>
  15 #include <mach-o/nlist.h>
  16
  17 #include "kasan.h"
  18 #include "kasan_internal.h"
  19
  20 #if KASAN_DYNAMIC_BLACKLIST
  21
  22 #define MAX_FRAMES 8
  23 #define HASH_NBUCKETS 128U
  24 #define HASH_MASK (HASH_NBUCKETS-1)
  25 #define HASH_CACHE_NENTRIES 128
  26
  27 struct blacklist_entry {
  28         const char *kext_name;
  29         const char *func_name;
  30         access_t type_mask;
  31
  32         /* internal */
  33         uint64_t count;
  34 };
  35
  36 #include "kasan_blacklist_dynamic.h"
  37 /* defines 'blacklist' and 'blacklist_entries' */
  38
  39 decl_simple_lock_data(static, _dybl_lock);
  40 static access_t blacklisted_types; /* bitmap of access types with blacklist entries */
  41
  42 static void
  43 dybl_lock(boolean_t *b)
  44 {
  45         *b = ml_set_interrupts_enabled(false);
  46         simple_lock(&_dybl_lock, LCK_GRP_NULL);
  47 }
  48
  49 static void
  50 dybl_unlock(boolean_t b)
  51 {
  52         simple_unlock(&_dybl_lock);
  53         ml_set_interrupts_enabled(b);
  54 }
  55
  56
  57 /*
  58  * blacklist call site hash table
  59  */
  60
  61 struct blacklist_hash_entry {
  62         SLIST_ENTRY(blacklist_hash_entry) chain; // next element in chain
  63         struct blacklist_entry *ble;             // blacklist entry that this caller is an instance of
  64         uintptr_t addr;                          // callsite address
  65         uint64_t count;                          // hit count
  66 };
  67
  68 struct hash_chain_head {
  69         SLIST_HEAD(, blacklist_hash_entry);
  70 };
  71
  72 unsigned cache_next_entry = 0;
  73 struct blacklist_hash_entry blhe_cache[HASH_CACHE_NENTRIES];
  74 struct hash_chain_head hash_buckets[HASH_NBUCKETS];
  75
  76 static struct blacklist_hash_entry *
  77 alloc_hash_entry(void)
  78 {
  79         unsigned idx = cache_next_entry++;
  80         if (idx >= HASH_CACHE_NENTRIES) {
  81                 cache_next_entry = HASH_CACHE_NENTRIES; // avoid overflow
  82                 return NULL;
  83         }
  84         return &blhe_cache[idx];
  85 }
  86
  87 static unsigned
  88 hash_addr(uintptr_t addr)
  89 {
  90         addr ^= (addr >> 7); /* mix in some of the bits likely to select the kext */
  91         return (unsigned)addr & HASH_MASK;
  92 }
  93
  94 static struct blacklist_hash_entry *
  95 blacklist_hash_lookup(uintptr_t addr)
  96 {
  97         unsigned idx = hash_addr(addr);
  98         struct blacklist_hash_entry *blhe;
  99
 100         SLIST_FOREACH(blhe, &hash_buckets[idx], chain) {
 101                 if (blhe->addr == addr) {
 102                         return blhe;
 103                 }
 104         }
 105
 106         return NULL;
 107 }
 108
 109 static struct blacklist_hash_entry *
 110 blacklist_hash_add(uintptr_t addr, struct blacklist_entry *ble)
 111 {
 112         unsigned idx = hash_addr(addr);
 113
 114         struct blacklist_hash_entry *blhe = alloc_hash_entry();
 115         if (!blhe) {
 116                 return NULL;
 117         }
 118
 119         blhe->ble = ble;
 120         blhe->addr = addr;
 121         blhe->count = 1;
 122
 123         SLIST_INSERT_HEAD(&hash_buckets[idx], blhe, chain);
 124
 125         return blhe;
 126 }
 127
 128 static void
 129 hash_drop(void)
 130 {
 131         if (cache_next_entry > 0) {
 132                 bzero(&hash_buckets, sizeof(hash_buckets));
 133                 bzero(&blhe_cache, sizeof(struct blacklist_hash_entry) * cache_next_entry);
 134                 cache_next_entry = 0;
 135         }
 136 }
 137
 138 /*
 139  * kext range lookup tree
 140  */
 141
 142 struct range_tree_entry {
 143         RB_ENTRY(range_tree_entry) tree;
 144
 145         uintptr_t base;
 146
 147         struct {
 148                 uint64_t size : 63;
 149                 uint64_t accessed : 1; // blacklist entry exists in this range
 150         };
 151
 152         /* kext name */
 153         const char *bundleid;
 154
 155         /* mach header for corresponding kext */
 156         kernel_mach_header_t *mh;
 157 };
 158
 159 static int NOINLINE
 160 range_tree_cmp(const struct range_tree_entry *e1, const struct range_tree_entry *e2)
 161 {
 162         if (e1->size == 0 || e2->size == 0) {
 163                 /* lookup */
 164                 if (e1->base + e1->size < e2->base) {
 165                         return -1;
 166                 } else if (e1->base > e2->base + e2->size) {
 167                         return 1;
 168                 } else {
 169                         return 0;
 170                 }
 171         } else {
 172                 /* compare */
 173                 if (e1->base + e1->size <= e2->base) {
 174                         return -1;
 175                 } else if (e1->base >= e2->base + e2->size) {
 176                         return 1;
 177                 } else {
 178                         panic("bad compare\n");
 179                         return 0;
 180                 }
 181         }
 182 }
 183
 184 RB_HEAD(range_tree, range_tree_entry) range_tree_root;
 185 RB_PROTOTYPE(range_tree, range_tree_entry, tree, range_tree_cmp);
 186 RB_GENERATE(range_tree, range_tree_entry, tree, range_tree_cmp);
 187
 188 /* for each executable section, insert a range tree entry */
 189 void
 190 kasan_dybl_load_kext(uintptr_t addr, const char *kextname)
 191 {
 192         int i;
 193
 194         struct load_command *cmd = NULL;
 195         kernel_mach_header_t *mh = (void *)addr;
 196
 197         cmd = (struct load_command *)&mh[1];
 198
 199         for (i = 0; i < (int)mh->ncmds; i++) {
 200                 if (cmd->cmd == LC_SEGMENT_KERNEL) {
 201                         kernel_segment_command_t *seg = (void *)cmd;
 202                         bool is_exec = seg->initprot & VM_PROT_EXECUTE;
 203
 204 #if defined(__arm__) || defined(__arm64__)
 205                         if (is_exec && strcmp("__TEXT_EXEC", seg->segname) != 0) {
 206                                 is_exec = false;
 207                         }
 208 #endif
 209
 210                         if (is_exec) {
 211                                 struct range_tree_entry *e = kalloc(sizeof(struct range_tree_entry));
 212                                 bzero(e, sizeof(*e));
 213
 214                                 e->base = seg->vmaddr;
 215                                 e->size = seg->vmsize;
 216                                 e->bundleid = kextname;
 217                                 e->mh = mh;
 218
 219                                 boolean_t flag;
 220                                 dybl_lock(&flag);
 221                                 RB_INSERT(range_tree, &range_tree_root, e);
 222                                 dybl_unlock(flag);
 223                         }
 224                 }
 225
 226                 cmd = (void *)((uintptr_t)cmd + cmd->cmdsize);
 227         }
 228 }
 229
 230 void
 231 kasan_dybl_unload_kext(uintptr_t addr)
 232 {
 233         int i;
 234
 235         struct load_command *cmd = NULL;
 236         kernel_mach_header_t *mh = (void *)addr;
 237
 238         cmd = (struct load_command *)&mh[1];
 239
 240         for (i = 0; i < (int)mh->ncmds; i++) {
 241                 if (cmd->cmd == LC_SEGMENT_KERNEL) {
 242                         kernel_segment_command_t *seg = (void *)cmd;
 243                         bool is_exec = seg->initprot & VM_PROT_EXECUTE;
 244 #if defined(__arm__) || defined(__arm64__)
 245                         if (is_exec && strcmp("__TEXT_EXEC", seg->segname) != 0) {
 246                                 is_exec = false;
 247                         }
 248 #endif
 249
 250                         if (is_exec) {
 251                                 struct range_tree_entry key = { .base = seg->vmaddr, .size = 0 };
 252                                 struct range_tree_entry *e;
 253                                 boolean_t flag;
 254                                 dybl_lock(&flag);
 255                                 e = RB_FIND(range_tree, &range_tree_root, &key);
 256                                 if (e) {
 257                                         RB_REMOVE(range_tree, &range_tree_root, e);
 258                                         if (e->accessed) {
 259                                                 /* there was a blacklist entry in this range */
 260                                                 hash_drop();
 261                                         }
 262                                 }
 263                                 dybl_unlock(flag);
 264
 265                                 if (e) {
 266                                         kfree(e, sizeof(*e));
 267                                 }
 268                         }
 269                 }
 270
 271                 cmd = (void *)((uintptr_t)cmd + cmd->cmdsize);
 272         }
 273 }
 274
 275 /*
 276  * return the closest function name at or before addr
 277  */
 278 static const NOINLINE char *
 279 addr_to_func(uintptr_t addr, const kernel_mach_header_t *mh)
 280 {
 281         int i;
 282         uintptr_t cur_addr = 0;
 283
 284         const struct load_command *cmd = NULL;
 285         const struct symtab_command *st = NULL;
 286         const kernel_segment_command_t *le = NULL;
 287         const char *strings;
 288         const kernel_nlist_t *syms;
 289         const char *cur_name = NULL;
 290
 291         cmd = (const struct load_command *)&mh[1];
 292
 293         /*
 294          * find the symtab command and linkedit segment
 295          */
 296         for (i = 0; i < (int)mh->ncmds; i++) {
 297                 if (cmd->cmd == LC_SYMTAB) {
 298                         st = (const struct symtab_command *)cmd;
 299                 } else if (cmd->cmd == LC_SEGMENT_KERNEL) {
 300                         const kernel_segment_command_t *seg = (const void *)cmd;
 301                         if (!strcmp(seg->segname, SEG_LINKEDIT)) {
 302                                 le = (const void *)cmd;
 303                         }
 304                 }
 305                 cmd = (const void *)((uintptr_t)cmd + cmd->cmdsize);
 306         }
 307
 308         /* locate the symbols and strings in the symtab */
 309         strings = (const void *)((le->vmaddr - le->fileoff) + st->stroff);
 310         syms    = (const void *)((le->vmaddr - le->fileoff) + st->symoff);
 311
 312         /*
 313          * iterate the symbols, looking for the closest one to `addr'
 314          */
 315         for (i = 0; i < (int)st->nsyms; i++) {
 316                 uint8_t n_type = syms[i].n_type;
 317                 const char *name = strings + syms[i].n_un.n_strx;
 318
 319                 if (n_type & N_STAB) {
 320                         /* ignore debug entries */
 321                         continue;
 322                 }
 323
 324                 n_type &= N_TYPE;
 325                 if (syms[i].n_un.n_strx == 0 || !(n_type == N_SECT || n_type == N_ABS)) {
 326                         /* only use named and defined symbols */
 327                         continue;
 328                 }
 329
 330 #if 0
 331                 if (mh != &_mh_execute_header) {
 332                         printf("sym '%s' 0x%x 0x%lx\n", name, (unsigned)syms[i].n_type, (unsigned long)syms[i].n_value);
 333                 }
 334 #endif
 335
 336                 if (*name == '_') {
 337                         name += 1;
 338                 }
 339
 340                 /* this symbol is closer than the one we had */
 341                 if (syms[i].n_value <= addr && syms[i].n_value > cur_addr) {
 342                         cur_name = name;
 343                         cur_addr = syms[i].n_value;
 344                 }
 345         }
 346
 347         /* best guess for name of function at addr */
 348         return cur_name;
 349 }
 350
 351 bool OS_NOINLINE
 352 kasan_is_blacklisted(access_t type)
 353 {
 354         uint32_t nframes = 0;
 355         uintptr_t frames[MAX_FRAMES];
 356         uintptr_t *bt = frames;
 357
 358         assert(__builtin_popcount(type) == 1);
 359
 360         if ((type & blacklisted_types) == 0) {
 361                 /* early exit for types with no blacklist entries */
 362                 return false;
 363         }
 364
 365         nframes = backtrace_frame(bt, MAX_FRAMES, __builtin_frame_address(0),
 366             NULL);
 367         boolean_t flag;
 368
 369         if (nframes >= 1) {
 370                 /* ignore direct caller */
 371                 nframes -= 1;
 372                 bt += 1;
 373         }
 374
 375         struct blacklist_hash_entry *blhe = NULL;
 376
 377         dybl_lock(&flag);
 378
 379         /* First check if any frame hits in the hash */
 380         for (uint32_t i = 0; i < nframes; i++) {
 381                 blhe = blacklist_hash_lookup(bt[i]);
 382                 if (blhe) {
 383                         if ((blhe->ble->type_mask & type) != type) {
 384                                 /* wrong type */
 385                                 continue;
 386                         }
 387
 388                         /* hit */
 389                         blhe->count++;
 390                         blhe->ble->count++;
 391                         // printf("KASan: blacklist cache hit (%s:%s [0x%lx] 0x%x)\n",
 392                         //              ble->kext_name ?: "" , ble->func_name ?: "", VM_KERNEL_UNSLIDE(bt[i]), mask);
 393                         dybl_unlock(flag);
 394                         return true;
 395                 }
 396         }
 397
 398         /* no hits - slowpath */
 399         for (uint32_t i = 0; i < nframes; i++) {
 400                 const char *kextname = NULL;
 401                 const char *funcname = NULL;
 402
 403                 struct range_tree_entry key = { .base = bt[i], .size = 0 };
 404                 struct range_tree_entry *e = RB_FIND(range_tree, &range_tree_root, &key);
 405
 406                 if (!e) {
 407                         /* no match at this address - kinda weird? */
 408                         continue;
 409                 }
 410
 411                 /* get the function and bundle name for the current frame */
 412                 funcname = addr_to_func(bt[i], e->mh);
 413                 if (e->bundleid) {
 414                         kextname = strrchr(e->bundleid, '.');
 415                         if (kextname) {
 416                                 kextname++;
 417                         } else {
 418                                 kextname = e->bundleid;
 419                         }
 420                 }
 421
 422                 // printf("%s: a = 0x%016lx,0x%016lx f = %s, k = %s\n", __func__, bt[i], VM_KERNEL_UNSLIDE(bt[i]), funcname, kextname);
 423
 424                 /* check if kextname or funcname are in the blacklist */
 425                 for (size_t j = 0; j < blacklist_entries; j++) {
 426                         struct blacklist_entry *ble = &blacklist[j];
 427                         uint64_t count;
 428
 429                         if ((ble->type_mask & type) != type) {
 430                                 /* wrong type */
 431                                 continue;
 432                         }
 433
 434                         if (ble->kext_name && kextname && strncmp(kextname, ble->kext_name, KMOD_MAX_NAME) != 0) {
 435                                 /* wrong kext name */
 436                                 continue;
 437                         }
 438
 439                         if (ble->func_name && funcname && strncmp(funcname, ble->func_name, 128) != 0) {
 440                                 /* wrong func name */
 441                                 continue;
 442                         }
 443
 444                         /* found a matching function or kext */
 445                         blhe = blacklist_hash_add(bt[i], ble);
 446                         count = ble->count++;
 447                         e->accessed = 1;
 448
 449                         dybl_unlock(flag);
 450
 451                         if (count == 0) {
 452                                 printf("KASan: ignoring blacklisted violation (%s:%s [0x%lx] %d 0x%x)\n",
 453                                     kextname, funcname, VM_KERNEL_UNSLIDE(bt[i]), i, type);
 454                         }
 455
 456                         return true;
 457                 }
 458         }
 459
 460         dybl_unlock(flag);
 461         return false;
 462 }
 463
 464 static void
 465 add_blacklist_entry(const char *kext, const char *func, access_t type)
 466 {
 467         assert(kext || func);
 468         struct blacklist_entry *ble = &blacklist[blacklist_entries++];
 469
 470         if (blacklist_entries > blacklist_max_entries) {
 471                 panic("KASan: dynamic blacklist entries exhausted\n");
 472         }
 473
 474         if (kext) {
 475                 size_t sz = __nosan_strlen(kext) + 1;
 476                 if (sz > 1) {
 477                         char *s = zalloc_permanent(sz, ZALIGN_NONE);
 478                         __nosan_strlcpy(s, kext, sz);
 479                         ble->kext_name = s;
 480                 }
 481         }
 482
 483         if (func) {
 484                 size_t sz = __nosan_strlen(func) + 1;
 485                 if (sz > 1) {
 486                         char *s = zalloc_permanent(sz, ZALIGN_NONE);
 487                         __nosan_strlcpy(s, func, sz);
 488                         ble->func_name = s;
 489                 }
 490         }
 491
 492         ble->type_mask = type;
 493 }
 494
 495 #define TS(x) { .type = TYPE_##x, .str = #x }
 496
 497 static const struct {
 498         const access_t type;
 499         const char * const str;
 500 } typemap[] = {
 501         TS(LOAD),
 502         TS(STORE),
 503         TS(MEMR),
 504         TS(MEMW),
 505         TS(STRR),
 506         TS(STRW),
 507         TS(KFREE),
 508         TS(ZFREE),
 509         TS(FSFREE),
 510         TS(UAF),
 511         TS(POISON_GLOBAL),
 512         TS(POISON_HEAP),
 513         TS(MEM),
 514         TS(STR),
 515         TS(READ),
 516         TS(WRITE),
 517         TS(RW),
 518         TS(FREE),
 519         TS(NORMAL),
 520         TS(DYNAMIC),
 521         TS(POISON),
 522         TS(ALL),
 523
 524         /* convenience aliases */
 525         { .type = TYPE_POISON_GLOBAL, .str = "GLOB" },
 526         { .type = TYPE_POISON_HEAP, .str = "HEAP" },
 527 };
 528 static size_t typemap_sz = sizeof(typemap) / sizeof(typemap[0]);
 529
 530 static inline access_t
 531 map_type(const char *str)
 532 {
 533         if (strlen(str) == 0) {
 534                 return TYPE_NORMAL;
 535         }
 536
 537         /* convert type string to integer ID */
 538         for (size_t i = 0; i < typemap_sz; i++) {
 539                 if (strcasecmp(str, typemap[i].str) == 0) {
 540                         return typemap[i].type;
 541                 }
 542         }
 543
 544         printf("KASan: unknown blacklist type `%s', assuming `normal'\n", str);
 545         return TYPE_NORMAL;
 546 }
 547
 548 void
 549 kasan_init_dybl(void)
 550 {
 551         simple_lock_init(&_dybl_lock, 0);
 552
 553         /*
 554          * dynamic blacklist entries via boot-arg. Syntax is:
 555          *  kasan.bl=kext1:func1:type1,kext2:func2:type2,...
 556          */
 557         char buf[256] = {};
 558         char *bufp = buf;
 559         if (PE_parse_boot_arg_str("kasan.bl", bufp, sizeof(buf))) {
 560                 char *kext;
 561                 while ((kext = strsep(&bufp, ",")) != NULL) {
 562                         access_t type = TYPE_NORMAL;
 563                         char *func = strchr(kext, ':');
 564                         if (func) {
 565                                 *func++ = 0;
 566                         }
 567                         char *typestr = strchr(func, ':');
 568                         if (typestr) {
 569                                 *typestr++ = 0;
 570                                 type = map_type(typestr);
 571                         }
 572                         add_blacklist_entry(kext, func, type);
 573                 }
 574         }
 575
 576         /* collect bitmask of blacklisted types */
 577         for (size_t j = 0; j < blacklist_entries; j++) {
 578                 struct blacklist_entry *ble = &blacklist[j];
 579                 blacklisted_types |= ble->type_mask;
 580         }
 581
 582         /* add the fake kernel kext */
 583         kasan_dybl_load_kext((uintptr_t)&_mh_execute_header, "__kernel__");
 584 }
 585
 586 #else /* KASAN_DYNAMIC_BLACKLIST */
 587
 588 bool
 589 kasan_is_blacklisted(access_t __unused type)
 590 {
 591         return false;
 592 }
 593 #endif