Skip to content

Prime+Probe

Bir cache set'ini kendi line'larınla doldur, victim'in çalışmasına izin ver, sonra set'e tekrar eriş ("probe") ve süresini ölç — bir yavaşlama victim'in line'larından birini evict ettiği, yani o set'e dokunduğu anlamına gelir. Shared memory gerektirmez.

Mechanism

Neden çalışır

Bir set-associative cache her adresi tam olarak W way'den oluşan bir set'e map'ler. Set aynı anda en fazla W line tutabilir; aynı set'e map'lenen W+1'inci bir line getirmek bir eviction'a zorlar. Prime+Probe bu capacity conflict'ini bir ölçüme dönüştürür.

Attacker önce bir eviction set kurar: hepsi aynı target set'e map'lenen W adetlik bir adres grubu (congruent adresler). Invariant şu: eğer attacker bir set'i tamamen dolduruyorsa, o set'e sonradan yaptığı her erişim hızlıdır — ama arada victim aynı set'e dokunduysa hariç, o durumda bir attacker line'ı evict edilmiştir ve o erişim artık yavaştır. Re-access'i ölçmek bu yüzden victim ile herhangi bir memory paylaşmadan victim'in set'e erişip erişmediğini ortaya çıkarır.

Flush+Reload'un aksine Prime+Probe shared page ve clflush gerektirmez. Yalnızca cache capacity için contention'a dayanır, dolayısıyla security boundary'leri aşar (cross-VM, cross-process). Intel CPU'larda last-level cache (LLC) tarihsel olarak inclusive olmuştur: bir line'ı LLC'den evict etmek onu her core'un private L1/L2'sinden de evict eder, yani bir core'daki attacker LLC contention'ını kullanarak başka bir core'da çalışan bir victim'i gözetleyebilir. Bu, Liu, Yarom, Ge, Heiser ve Lee'nin (IEEE S&P 2015) pratik cross-core, cross-VM saldırısının temelidir; bu saldırı VM'ler arasında bir GnuPG El Gamal key'ini geri çıkarır. Orijinal cache-set contention fikri Osvik, Shamir ve Tromer'e (CT-RSA 2006) aittir; onlar bunu L1 cache'teki AES T-table'larına karşı kullanmıştır.

Walkthrough

İki primitive var: doğru bir timer (rdtscp) ve target set için congruent bir eviction set.

// gcc -O2 primeprobe.c -o pp   (x86-64)
#include <stdint.h>
#include <x86intrin.h>   // __rdtscp

// es[0..W-1] : W addresses that all map to the SAME cache set
void  *es[W];

static inline void prime(void) {
    for (int i = 0; i < W; i++)            // fill the target set with our lines
        (void)*(volatile char *)es[i];
}

static inline uint64_t probe(void) {
    unsigned aux;
    uint64_t t0 = __rdtscp(&aux);
    for (int i = 0; i < W; i++)            // re-access every line, timed
        (void)*(volatile char *)es[i];
    uint64_t t1 = __rdtscp(&aux);
    return t1 - t0;                         // slow => a line was evicted
}

Saldırı döngüsü prime → bekle → probe şeklindedir:

for (;;) {
    prime();                 // occupy the whole set
    nanosleep(&slot, NULL);  // give the victim a slot to run
    uint64_t t = probe();    // time the re-access
    record(t);               // t high => victim used this set
}

Eviction set'i kurmak kritik adımdır. 2 MB'lık huge page'lerle düşük 21 adres biti attacker-controlled olur, bu da cache-set index bitlerini sabitler ve (bilinen bir makinede) congruent adresleri sayıp çıkarmanı sağlar; aksi halde onları dinamik olarak keşfedersin (bkz. cache-eviction-set-construction). Kalibrasyondan sonra primed (her şey cache'te) ve contended re-access süreleri temiz biçimde ayrışır:

$ ./pp --calibrate
probe, no victim activity : ~120 cycles  (all W lines still cached)
probe, victim touched set : ~330 cycles  (>=1 line evicted -> DRAM refill)
threshold chosen          : ~220 cycles
Zaman içinde set başına aktivite trace'i (collapsed) 
set   timeline (one column = one probe slot;  # = contended)
0040  ....#...........#.........#.............
0041  ..........#..........#..........#.......
0042  #.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#  <- secret-dependent
0043  ...............................#........

Birçok set'i paralel olarak izlemek victim'in secret-dependent access pattern'ini yeniden kurar (örn. hangi table/exponentiation line'larına dokunduğunu).

Bu not vs. JavaScript Prime+Probe

Bu not, native kod (rdtscp, huge page'lerle congruent adresler) varsayan genel Prime+Probe primitive'idir — cross-VM/cross-process LLC contention'a odaklanır. Aynı primitive'in clflush/native-timer/physical-adres olmadan, sandbox'lı bir browser içinden çalıştırılan varyantı için bkz. JavaScript Prime+Probe (timer reconstruction + COOP/COEP mitigation'ları orada).

Non-inclusive cache'ler

Daha yeni Intel server CPU'ları (Skylake-SP ve sonrası) non-inclusive bir LLC kullanır, dolayısıyla düz LLC Prime+Probe artık victim'in private erişimlerini şeffaf biçimde göremez. Devam çalışmaları bunun yerine directory/snoop filter'ı hedef alır, Prime+Scope ise high-precision varyantı geliştirir.

Detection

  • HPC monitoring: yükselen LLC-load-misses / cache-misses ve sabit bir congruent adres set'i üzerinde tekrarlayan yürüyüşler davranışsal bir imzadır (perf stat -e LLC-load-misses,cache-misses).
  • Faydalı iş yapmayan sıkı rdtscp + eviction-set-walk döngüleri Flush+Reload imzasına benzer, ama clflush olmadan.

Mitigation

  • Constant-time code: secret-dependent memory adresi olmaması, böylece erişilen cache set'lerinin kümesi secret'tan bağımsız olur.
  • Cache partitioning / coloring (örn. Intel CAT) ile attacker'a victim'le paylaşılan, contended bir set vermemek.
  • Randomized cache'ler (ScatterCache, CEASER/CEASER-S) sabit address→set mapping'ini kırar, böylece eviction set kurmak zorlaşır — gerçi Prime+Prune+Probe bunlara hâlâ saldırır.

References