Skip to content

Prime+Prune+Probe

Randomized cache'ler için üç fazlı bir Prime+Probe varyantı: priming'den sonra bir prune fazı attacker'ın kendi self-eviction'larını ayıklar, böylece hayatta kalan line'lar stabil, contention'a hazır bir set oluşturur — ScatterCache/CEASER-S eviction-set savunmalarını alt eder.

Mechanism

Neden çalışır

Randomized cache'ler (ScatterCache, CEASER, CEASER-S) sabit address→set mapping'ini bir keyed cryptographic function ile değiştirir, böylece attacker artık congruent adreslerden temiz bir eviction set hesaplayamaz. Daha kötüsü, skewed tasarımlarda tek bir adres birden çok olası konuma map'lenir ve bir candidate grubu priming sırasında kendini rastgele evict eder, bu da victim'in sinyalini bastıran gürültü ekler.

Prime+Prune+Probe (PPP) bunu ekstra bir adımla çözer. Büyük bir candidate set'i prime ettikten sonra attacker prune eder: set'e tekrar tekrar erişir ve miss eden her line'ı atar, çünkü bir miss o line'ın başka bir candidate tarafından self-evict edildiği anlamına gelir. Tekrar erişip atmayı iteratif olarak yapmak, üyeleri artık birbirini evict etmeyen bir alt kümeye yakınsar — randomized cache içinde self-consistent bir "primed" duruma ulaşmışlardır. Invariant şu: bir pruned set stabil hale geldiğinde, probe'daki sonraki herhangi bir miss self-contention'dan değil, dışarıdan bir erişimden (victim) kaynaklanır. Bu, hiçbir iki adresin congruent olduğu garanti edilmese bile güvenilir bir probabilistic eviction set verir.

PPP, randomization tabanlı cache'lerin güvenlik analizinde tanıtıldı/kullanıldı: Purnal ve Verbauwhede'nin ScatterCache profiling üzerine notu (2019) ve Purnal, Giner, Gruss ve Verbauwhede'un systematic analizi (IEEE S&P 2021). Bu çalışma ScatterCache'in kendi "generalized eviction" analizini PPP'nin bir köşe durumu olarak yeniden çerçeveler ve PPP'nin rekeying period içinde yüksek kaliteli generalized eviction set'leri elde ettiğini gösterir, böylece daha önce infeasible sayılan saldırıları pratik hale getirir.

Walkthrough

Üç faz, kavramsal olarak:

PRIME : access a large candidate pool C, loading it into the (randomized) cache.
PRUNE : repeatedly re-walk C; on each pass discard every line that MISSES.
        A miss => that line was evicted by another candidate (self-eviction).
        Repeat until a full pass produces no misses  => set P is now stable.
PROBE : let the victim run, then re-walk P.
        Any miss now is victim-induced (an outside access collided with P).

Pseudocode olarak:

// 1) PRIME: bring the whole candidate pool in
for (line *x = C; x < C + N; x++) touch(x);

// 2) PRUNE: iterate to a self-stable working set P
do {
    progress = 0;
    for (line *x in current_set) {
        if (is_miss(time_access(x))) {   // self-evicted by a sibling
            drop(x);                     // remove from the set
            progress = 1;
        }
    }
} while (progress);                       // until a clean full pass: P is stable

// 3) PROBE: detect victim contention
victim_runs();
for (line *x in P)
    if (is_miss(time_access(x))) report_victim_access();

address→set mapping'i secret olduğundan PPP istatistiksel çalışır: stabil bir pruned set cache'in bir kısmını kapsar ve bir victim erişiminin onunla çakışma olasılığı bilinir. Birçok deneme üzerinden toplama yapmak secret-dependent erişimi geri çıkarır. Verimlilik kazancı büyüktür — ScatterCache profiling notu, 8-way, 11-index-bit bir konfigürasyonda güvenilir bir eviction set kurmak için gereken gözlemlenebilir victim erişimi sayısını kabaca 2^25'ten 2^10'un altına indirdiğini, yani birkaç kat (mertebe) daha az olduğunu raporluyor.

Probabilistic ve rekey ile yarış

PPP set'leri hiçbir zaman tam olarak congruent değildir, dolayısıyla detection istatistikseldir ve tekrar gerektirir. Randomized cache'ler ayrıca periyodik olarak rekey yapar; profile-sonra-exploit dizisinin tamamı tek bir rekeying epoch'u içinde tamamlanmalıdır, bu yüzden bu çalışma kolunda profiling verimliliği merkezî metriktir.

Mitigation

  • Kısa epoch'lu sık rekeying, bir pruned set'in geçerli kaldığı pencereyi daraltır (PPP'nin açıkça geçmek üzere tasarlandığı savunma).
  • Daha fazla skew'lu skewed randomization (örn. CEASER-S) profiling maliyetini artırır ama systematic analize göre tek başına PPP'yi durdurmaz.
  • Randomization'ı partitioning / constant-time code ile eşleştir, böylece kurulan bir eviction set bile secret-dependent sinyal taşımaz.

References