Skip to content

Cache Eviction Set Construction

Hepsi tek bir cache set'ine map'lenen minimal bir adres grubu kur ki bir target line'ı clflush olmadan evict edebilesin — Prime+Probe ve birçok transient-execution saldırısının imkân sağlayıcısı.

Mechanism

Neden çalışır

S set ve W way'e sahip bir set-associative cache, bir physical address'i onun set-index bitleri tarafından seçilen sabit bir set'e yerleştirir. O index bitlerini paylaşan (congruent olan) ve tag'de karşılıklı farklı olan herhangi W adres, hepsi erişildiğinde o set'i tamamen doldurur ve oraya map'lenmiş başka her şeyi evict eder. Böyle bir congruent grup bir eviction set'tir.

Bir eviction set ile bir victim line'ı yalnızca sıradan load'lar kullanarak flush'layabilirsin — clflush yok, shared memory yok — ki bu, target unshared olduğunda (cross-VM, JavaScript, kernel) ya da clflush mevcut olmadığında saldırıların tam olarak ihtiyaç duyduğu şeydir.

Shared-memory kuzeni için bkz. Flush+Reload. Bu not, eviction-set'in construction/search algoritmasına (group reduction) odaklanır; altında yatan "congruent a+1 adres orada ne varsa evict eder" primitive'inin tanımı için bkz. Set-Associative Cache Eviction.

Zor kısım, yalnızca virtual address'leri kontrol ettiğinde congruent adresleri bulmaktır: LLC'deki set index physical bitlere bağlıdır ve Intel'de LLC belgelenmemiş bir hash ile slice'lara bölünmüştür. Naif şekilde devasa aday havuzlarını test etmen gerekirdi. Vila, Köpf ve Morales, bir group-reduction algoritmasıyla aramayı quadratic'ten linear zamana indirdi.

Walkthrough

Büyük bir aday adres havuzundan başla (örn. physical address'in düşük bitleri bilinsin diye bir 2 MB hugepage'den), sonra onu tek bir target için tam olarak W congruent line'a indir.

1. "x, C set'i tarafından evict ediliyor mu?" için bir timing testi kur.

// Access every address in candidate set C, then time the target x.
static int evicts(addr_t *C, size_t n, addr_t x) {
    volatile char s = *(volatile char*)x;   // bring x into cache
    for (size_t i = 0; i < n; i++) (void)*(volatile char*)C[i];
    uint64_t t = time_load(x);              // rdtscp around the load
    return t > MISS_THRESHOLD;              // slow => x was evicted
}

2. Group reduction (linear-time, Vila ve ark.) — aday set'i tekrar tekrar W+1 gruba böl; çıkarılması set'i hâlâ target'ı evict edebilir bırakan grup gereksizdir, o yüzden onu at.

function reduce(C, x):                  # C evicts x, |C| large
  while |C| > W:
    partition C into W+1 equal groups G_0..G_W
    for i in 0..W:
        if evicts(C \ G_i, x):          # x still evicted without G_i
            C = C \ G_i                 # G_i was redundant; discard it
            break
  return C                              # |C| == W : a minimal eviction set

3. Minimal set'i doğrula.

$ ./evset --target 0x7f...  --ways 16
candidate pool: 4096 lines
reduced to:     16 lines  (W=16)  in 41 ms
self-test: target reload after priming = 263 cycles (MISS)  -> OK
control:   target reload, no priming    =  74 cycles (HIT)

Hızlı bir control reload (priming yok) ile yavaş bir reload (set ile priming sonrası) karşılaştırması, 16 line'ın target'ı gerçekten evict ettiğini doğrular. O set artık unshared memory üzerinde Prime+Probe'un "prime" adımı olarak hizmet eder.

Slice hashing ve gürültü

Sliced Intel LLC'lerde aynı index bitleri farklı slice'lara düşebilir; reduction bunu, slice'ı hesaplamak yerine eviction'ı ampirik olarak test ederek örtük biçimde halleder. Prefetcher'ları devre dışı bırak (ya da stride erişimi yap) ve gürültüyü azaltmak için thread'i pin'le, aksi halde reduction gereksiz olmayan bir grubu atabilir.

Detection

Construction'ın kendisi yalnızca bellek erişimidir, ama eviction set'lerin kullanımı (Prime+Probe) perf LLC-miss counter'ları aracılığıyla gözlemlenebilen conflict-miss pattern'leri üretir — bu detection signature, Flush+Reload'unkine benzer olsa da mekanizma (clflush yerine capacity contention) farklıdır.

Mitigation

  • Randomized/encrypted cache indexing (örn. CEASER/CEASER-S, Intel'in sonraki randomized LLC'si) line'ları periyodik olarak remap'ler; böylece bulunmuş bir eviction set bozulur.
  • Cache partitioning (Intel CAT) güvenlik domain'lerini ayrı way'lere izole eder.

References