Skip to content

Set-Associative Cache Eviction

Cache saldırılarının arkasındaki temel primitive: a-way set-associative bir cache'te, aynı set'e map'lenen a+1 adrese erişmek orada ne varsa onu evict eder.

Mechanism

Note

a-way set-associative bir cache'te her adres tam olarak bir cache set'ine map'lenir ve bu set a line (way) tutar. Bir set zaten a line tutarken yeni bir congruent line'a erişilirse, cache yer açmak için yerleşik line'lardan birini evict etmek zorundadır. Bir eviction set, en az a+1 karşılıklı congruent adres (aynı set'e map'lenen adresler) içeren bir adres koleksiyonudur; bunlara erişmek o set'teki önceki içeriği temizler. Bu, Prime+Probe, Rowhammer eviction-tabanlı hammering ve transient-execution saldırıları için çekirdek primitive'dir: saldırgana bilinen bir set durumunu zorlama ve ardından bir victim'in erişimini sonraki bir probe'un latency'siyle tespit etme imkânı verir. Küçük rastgele bir set'in eviction set olma ihtimali düşüktür, ama bu olasılık boyutla birlikte hızla artar — bu da "büyük bir aday set topla, sonra onu minimize et" yaklaşımını motive eder.

Bu not yalnızca primitive'i (eviction set nedir, neden çalışır) tanımlar; aday havuzdan minimal congruent set'i bulan somut linear-time construction algoritması (group reduction, virtual-only adreslerle slice hashing) için bkz. Cache Eviction Set Construction.

Walkthrough

Klasik minimizasyon bir adresi çıkarır ve kalan set'in hâlâ target'ı evict edip etmediğini yeniden test eder; bu O(N^2) erişim demektir. Bir group-testing yeniden formülasyonu, N boyutlu bir eviction set'i minimal çekirdeğine O(N) içinde indirger:

// prime: access every line in the candidate set
for (line in evset) access(line);
// later, probe target; if it is slow, the set evicted it (set is an eviction set)
t0 = rdtsc(); access(target); t1 = rdtsc();
bool evicted = (t1 - t0) > THRESHOLD;
Analizde kullanılan cache modeli (Intel Skylake LLC)
  • 8 slice, slice başına 1024 set, 64-byte line'lar, associativity a = 12.
  • Naive reduction O(N^2)'dir; bir threshold group-test bunu O(N)'e indirir, Skylake'te pratikte doğrusal büyüdüğü doğrulanmıştır ve virtual-to-set mapping üzerinde hiçbir kontrol olmadan bile çalışır.

Mitigation

Daha büyük associativity, randomize/skew edilmiş cache indexing (örn. CEASER tarzı mapping'ler) ve cache partitioning, eviction set bulma ve kullanma maliyetini yükseltir. Adaptive replacement policy'leri ve TLB thrashing de güvenilirliği düşürür.

References