Skip to content

Pattern History Table Collision

Spectre Variant 1 (Bounds Check Bypass, CVE-2017-5753): conditional-branch Pattern History Table'ı mistrain ederek bir victim'in bir bounds check'i speculatively geçmesini sağla, sonra out-of-bounds veriyi bir cache covert channel üzerinden sızdır.

Mechanism

Conditional branch sonuçları Pattern History Table (PHT) tarafından tahmin edilir — yakın branch history'nin bir hash'i ile indexlenmiş saturating counter'lar. Predictor bir branch'in taken olduğundan eminse, CPU koşul gerçekten resolve edilmeden önce taken yolu speculatively yürütür. Tahmin yanlışsa architectural sonuçlar atılır — ama microarchitectural yan etkiler (cache state) geri alınmaz.

Neden çalışır

Bir bounds check (if (x < array1_size)) yalnızca bir conditional branch'tir. PHT onu hangi x'in train ettiğini ayırt etmez — sadece branch'in yakın taken/not-taken desenini. Victim gadget'ı tekrar tekrar in-bounds x ile çağıran bir attacker, PHT'yi "taken" tahmin etmeye train eder. Sonra out-of-bounds bir x verir. CPU "in bounds" diye mispredict eder ve bir secret'a işaret eden bir x için array1[x]'i speculatively dereference eder, sonra o secret byte'ı ikinci bir array'i indexlemek için kullanır — cache'te misprediction rollback'ini atlatan secret-bağımlı bir ayak izi bırakır. Architectural bounds check doğrudur; sızıntı tamamen speculative pencerede gerçekleşir.

Walkthrough

Kocher et al.'dan kanonik Spectre v1 gadget'ı:

if (x < array1_size)
    y = array2[array1[x] * 512];

Saldırı adımları:

1. Train:   call the gadget many times with valid x (x < array1_size)
            -> PHT learns to predict the branch TAKEN.

2. Flush:   clflush every cache line of array2[ i * 512 ]  (i = 0..255)
            -> probe array starts uncached.

3. Trigger: call the gadget with a malicious out-of-bounds x such that
            &array1[x] points at the target secret byte k.
            The CPU mispredicts "in bounds" and speculatively computes
                array2[k * 512]
            pulling exactly ONE secret-dependent line of array2 into cache.

4. Reload:  time access to array2[ i * 512 ] for every i.
            The i with the fast (cached) access == the secret byte value k.

* 512 stride'ı her aday byte değerini ayrı bir cache line'a yerleştirir — aday değerler birbirinden 512 byte, yani 8 cache line (512 / 64-byte line) uzakta durur, dolayısıyla array2 toplamda 256 × 512 = 128 KB'dir — ki adjacent-line hardware prefetcher komşu adayları bulanıklaştırmasın ve Flush+Reload tek bir belirgin cache line'ı çözebilsin. (Kocher et al.'ın orijinal PoC listing'i bu 512-byte stride'ı kullanır; bazı varyantlar her adayı ayrı bir page'e düşürmek için 4096-byte page stride tercih eder.)

// Step 4: Flush+Reload recovery of the leaked byte
for (i = 0; i < 256; i++) {
    addr = &array2[i * 512];
    t0 = rdtscp();
    junk = *addr;                 // time the reload
    delta = rdtscp() - t0;
    if (delta < CACHE_HIT_THRESHOLD)
        results[i]++;             // i is a likely secret-byte value
}

Warning

Bounds check işlevsel olarak doğrudur — code review ve çoğu statik analiz gadget'ı işaretlemez, çünkü sızıntı yalnızca misprediction sırasında geçici olarak vardır. Spectre v1, conditional-branch speculation yapan Intel, AMD ve ARM işlemcilerini etkiler.

Detection

Temiz bir architectural imza yoktur; speculative erişimler squash edilir. Pratikte tespit (a) kaynak/binary içinde Spectre-v1 gadget'larını bulmaya (Microsoft'un /Qspectre'i, oo7, Spectector) ve (b) anormal mispredict + cache-miss desenleri gösteren hardware performance counter'larına dayanır.

Mitigation

  • lfence (speculation barrier) — bounds check ile ona bağlı load arasında; gadget'ın speculative yürütülmesini durdurur. __builtin_load_no_speculate / Linux barrier_nospec() tarafından kullanılır.
  • Index masking — x'i array sınırlarına clamp et (power-of-two boyutlar için x & (array1_size - 1), ya da array_index_nospec()), böylece misspeculate edilen bir load bile sınırlar içinde kalır.
  • Compiler mitigation'ları — MSVC /Qspectre, GCC/Clang Speculative Load Hardening.

Microcode tek başına v1'i düzeltmez; Spectre v2'nin (branch target injection) aksine software'de gadget bazında mitige edilir.

References