Skip to content

CTPP eviction set search

CTPP ("Conflict Testing with Probe+Prune"), Intel LLC'leri için hem accurate hem de detector-evading olacak şekilde Conflict Testing'i Prime+Prune+Probe ile melezleyen hızlı ve stealth bir eviction-set arama algoritmasıdır.

Mechanism

Teori / invariant

Bir eviction set, hepsi bir target ile congruent olan (aynı cache set'e map'lenen) bir adres grubudur. W-way bir cache için en az W congruent adrese ihtiyaç duyarsın; minimal bir set'in tam olarak W tanesi vardır ve en hızlı prime ettiği ve en az gürültü ürettiği için tercih edilir. Intel'de LLC belgelenmemiş bir hash ile slice'lara bölünmüştür; bu yüzden eviction set'ler blind search ile bulunmalıdır — bkz. cache eviction-set construction.

CTPP, stealth problemine dynamic cache randomization karşısında saldırır: address->set map'lemesini randomize edip periyodik olarak remap eden bir savunma, artı per-set eviction dağılımını izleyip bir arama algoritması düzensiz bir eviction izi bıraktığında fazladan bir remap tetikleyen bir detector. Önceki tüm hızlı aramalar o detector'a karşı başarısız olur. CTPP, hem hızlı hem de onun altından sıyrılacak şekilde tasarlanmıştır. İki ebeveyninin bir melezidir:

  • CT (Conflict Testing): yüksek başarı oranı ama ~10x daha yavaş — target'ı evict etmek için topladığı adres başına ~W-1 ekstra congruent adrese dokunur.
  • PPP (Prime+Prune+Probe): en düşük latency (RRIP'i istismar eder) ama düşük başarı — prime set W'den fazla congruent adres içerirse, prune adımı fazladan eleme eğilimindedir ve W'den az bırakır.

CTPP'nin iki içgörüsü: (1) CT'yi yalnızca mükemmel W boyutlu bir prime set kurmak için kullan (PPP'nin temel başarısızlık nedenini düzelterek), sonra probe+prune ile rafine et; ve (2) sırayı Probe+Prune'a çevir (her zamanki Prune+Probe değil) ki detector'ın anahtar aldığı eviction izi düzleştirilip silinsin.

Walkthrough

CTPP algoritması (kavramsal, Algorithm 1'den) 
# Inputs: target x, ways W. Output: eviction set E.

# --- Phase 1: CT — build a perfect, W-sized prime set C ---
prime(LLC); access(x)
while probe(x) is still a HIT:
    a = random_address(); access(a); C.add(a)
# C now holds exactly enough congruent addresses to evict x.

# --- Phase 2/3: iterate Probe then Prune until |C| == W ---
while |C| > W:
    flush(C); access(C)
    R = {}                      # PROBE
    access(x)
    for c in C:
        if probe(c) is a MISS:  # c was evicted -> congruent
            R.add(c)
    E = {}                      # PRUNE
    for c in R:
        if probe(c) confirms congruence:
            E.add(c)
    C = E                       # extra rounds absorb noise
return E

Sonuçlar (makale, 6 Intel CPU, her birinde 2000 deneme):

  • Aynı anda en hızlı ve en yüksek başarı oranı. Sub-millisecond ile birkaç ms arası — örn. i7-6700: huge page'lerle 0.29 ms / %100; test edilen tüm Intel işlemcilerinde < 5 ms.
  • GE (group-elimination baseline'ı) çok daha yavaştır; CT/CT-fast accurate ama ~10x daha yavaştır; PPP hızlı ama daha düşük başarılıdır.
  • Anti-detection: yeniden implemente edilmiş detector'a karşı CTPP çalışmaya devam eder (~%60 evasion); diğer tüm algoritmalar ise başarısız olur.

Tuzaklar

  • Tam ad "Conflict Testing with Probe+Prune," yani "Conflict-Testing Prime+Probe"un hafif bir parafrazıdır. Sıra Probe+Prune'dur, kasıtlı olarak PPP'den tersine çevrilmiştir — detector'ı atlatan da o tersine çevirmedir.
  • GE baseline'ı Vila, Köpf, Morales, "Theory and Practice of Finding Eviction Sets" (S&P 2019); CT-fast ise Prime+Scope'tan (Purnal ve ark., CCS 2021) gelir. CTPP kendini her ikisine karşı konumlar.
  • Non-skewed (set-associative / randomized) cache'ler üzerinde değerlendirildi; randomized skewed cache'ler kapsam dışıdır ve future work olarak bırakıldı.

Detection

CTPP'nin hedeflediği detector, per-set bir eviction z-score hesaplar, onu weighted moving average ile düzeltir ve threshold 5.0'ın üzerinde bir remap tetikler — GE'nin recursive pruning'ini ve PPP'nin probe adımını yakalar. CTPP onu probe/prune yeniden sıralamasıyla kısmen yener; bu yüzden sertleştirilmiş bir detector'ın CTPP'nin daha düz izini modellemesi gerekirdi.

Mitigation

Periyodik + tetiklenmiş remapping ile dynamic cache randomization, skewed randomized cache'ler (ScatterCache, Scatter-and-Split — ki CTPP bunları henüz ele almaz) ve fully-associative tarzı tasarımlar (MIRAGE). CTPP, randomization + remapping + detection'ın tek başına, co-designed bir hızlı-ve-stealth searcher'a karşı yetersiz olduğunu gösterir. Ayrıca bkz. set-associative cache eviction.

References