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
dybl_lock(boolean_t * b)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
dybl_unlock(boolean_t b)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 *
alloc_hash_entry(void)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
hash_addr(uintptr_t addr)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 *
blacklist_hash_lookup(uintptr_t addr)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 *
blacklist_hash_add(uintptr_t addr,struct blacklist_entry * ble)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
hash_drop(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
range_tree_cmp(const struct range_tree_entry * e1,const struct range_tree_entry * e2)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");
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
kasan_dybl_load_kext(uintptr_t addr,const char * kextname)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(__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_type(struct range_tree_entry,
212 Z_WAITOK | Z_ZERO | Z_NOFAIL);
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
kasan_dybl_unload_kext(uintptr_t addr)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(__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 kfree_type(struct range_tree_entry, e);
266 }
267 }
268
269 cmd = (void *)((uintptr_t)cmd + cmd->cmdsize);
270 }
271 }
272
273 /*
274 * return the closest function name at or before addr
275 */
276 static const NOINLINE char *
addr_to_func(uintptr_t addr,const kernel_mach_header_t * mh)277 addr_to_func(uintptr_t addr, const kernel_mach_header_t *mh)
278 {
279 int i;
280 uintptr_t cur_addr = 0;
281
282 const struct load_command *cmd = NULL;
283 const struct symtab_command *st = NULL;
284 const kernel_segment_command_t *le = NULL;
285 const char *strings;
286 const kernel_nlist_t *syms;
287 const char *cur_name = NULL;
288
289 cmd = (const struct load_command *)&mh[1];
290
291 /*
292 * find the symtab command and linkedit segment
293 */
294 for (i = 0; i < (int)mh->ncmds; i++) {
295 if (cmd->cmd == LC_SYMTAB) {
296 st = (const struct symtab_command *)cmd;
297 } else if (cmd->cmd == LC_SEGMENT_KERNEL) {
298 const kernel_segment_command_t *seg = (const void *)cmd;
299 if (!strcmp(seg->segname, SEG_LINKEDIT)) {
300 le = (const void *)cmd;
301 }
302 }
303 cmd = (const void *)((uintptr_t)cmd + cmd->cmdsize);
304 }
305
306 /* locate the symbols and strings in the symtab */
307 strings = (const void *)((le->vmaddr - le->fileoff) + st->stroff);
308 syms = (const void *)((le->vmaddr - le->fileoff) + st->symoff);
309
310 /*
311 * iterate the symbols, looking for the closest one to `addr'
312 */
313 for (i = 0; i < (int)st->nsyms; i++) {
314 uint8_t n_type = syms[i].n_type;
315 const char *name = strings + syms[i].n_un.n_strx;
316
317 if (n_type & N_STAB) {
318 /* ignore debug entries */
319 continue;
320 }
321
322 n_type &= N_TYPE;
323 if (syms[i].n_un.n_strx == 0 || !(n_type == N_SECT || n_type == N_ABS)) {
324 /* only use named and defined symbols */
325 continue;
326 }
327
328 #if 0
329 if (mh != &_mh_execute_header) {
330 printf("sym '%s' 0x%x 0x%lx\n", name, (unsigned)syms[i].n_type, (unsigned long)syms[i].n_value);
331 }
332 #endif
333
334 if (*name == '_') {
335 name += 1;
336 }
337
338 /* this symbol is closer than the one we had */
339 if (syms[i].n_value <= addr && syms[i].n_value > cur_addr) {
340 cur_name = name;
341 cur_addr = syms[i].n_value;
342 }
343 }
344
345 /* best guess for name of function at addr */
346 return cur_name;
347 }
348
349 bool OS_NOINLINE
kasan_is_blacklisted(access_t type)350 kasan_is_blacklisted(access_t type)
351 {
352 uint32_t nframes = 0;
353 uintptr_t frames[MAX_FRAMES];
354 uintptr_t *bt = frames;
355
356 assert(__builtin_popcount(type) == 1);
357
358 if ((type & blacklisted_types) == 0) {
359 /* early exit for types with no blacklist entries */
360 return false;
361 }
362
363 struct backtrace_control ctl = {
364 .btc_frame_addr = (uintptr_t)__builtin_frame_address(0),
365 };
366 nframes = backtrace(bt, MAX_FRAMES, &ctl, 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
add_blacklist_entry(const char * kext,const char * func,access_t type)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");
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(ZFREE),
508 TS(FSFREE),
509 TS(UAF),
510 TS(POISON_GLOBAL),
511 TS(POISON_HEAP),
512 TS(MEM),
513 TS(STR),
514 TS(READ),
515 TS(WRITE),
516 TS(RW),
517 TS(FREE),
518 TS(NORMAL),
519 TS(DYNAMIC),
520 TS(POISON),
521 TS(ALL),
522
523 /* convenience aliases */
524 { .type = TYPE_POISON_GLOBAL, .str = "GLOB" },
525 { .type = TYPE_POISON_HEAP, .str = "HEAP" },
526 };
527 static size_t typemap_sz = sizeof(typemap) / sizeof(typemap[0]);
528
529 static inline access_t
map_type(const char * str)530 map_type(const char *str)
531 {
532 if (strlen(str) == 0) {
533 return TYPE_NORMAL;
534 }
535
536 /* convert type string to integer ID */
537 for (size_t i = 0; i < typemap_sz; i++) {
538 if (strcasecmp(str, typemap[i].str) == 0) {
539 return typemap[i].type;
540 }
541 }
542
543 printf("KASan: unknown blacklist type `%s', assuming `normal'\n", str);
544 return TYPE_NORMAL;
545 }
546
547 void
kasan_init_dybl(void)548 kasan_init_dybl(void)
549 {
550 simple_lock_init(&_dybl_lock, 0);
551
552 /*
553 * dynamic blacklist entries via boot-arg. Syntax is:
554 * kasan.bl=kext1:func1:type1,kext2:func2:type2,...
555 */
556 char buf[256] = {};
557 char *bufp = buf;
558 if (PE_parse_boot_arg_str("kasan.bl", bufp, sizeof(buf))) {
559 char *kext;
560 while ((kext = strsep(&bufp, ",")) != NULL) {
561 access_t type = TYPE_NORMAL;
562 char *func = strchr(kext, ':');
563 if (func) {
564 *func++ = 0;
565 }
566 char *typestr = strchr(func, ':');
567 if (typestr) {
568 *typestr++ = 0;
569 type = map_type(typestr);
570 }
571 add_blacklist_entry(kext, func, type);
572 }
573 }
574
575 /* collect bitmask of blacklisted types */
576 for (size_t j = 0; j < blacklist_entries; j++) {
577 struct blacklist_entry *ble = &blacklist[j];
578 blacklisted_types |= ble->type_mask;
579 }
580
581 /* add the fake kernel kext */
582 kasan_dybl_load_kext((uintptr_t)&_mh_execute_header, "__kernel__");
583 }
584
585 #else /* KASAN_DYNAMIC_BLACKLIST */
586
587 bool
kasan_is_blacklisted(access_t __unused type)588 kasan_is_blacklisted(access_t __unused type)
589 {
590 return false;
591 }
592 #endif
593