Skip to content

BTB Collision

İki farklı branch aynı Branch Target Buffer entry'sine map'lenir çünkü BTB yalnızca kısmi adres bitleri üzerinden index ve tag yapar — cross-address-space Spectre v2 mistraining'i mümkün kılan aliasing.

Mechanism

Neden çalışır

BTB sonlu, set-associative bir yapıdır: bir branch'in adresi küçük bir index'e (bir set seçen) ve küçük bir tag'e (set içinde kontrol edilen) katlanır. Alan ve latency'den tasarruf etmek için ikisi de tam virtual address'i kullanmaz — index birkaç düşük bit, tag ise kısmi (folded/hashed) bir tag'dir. Bir predictor için tam adres çözümlemesi gereksizdir: yanlış bir tahmin, branch çözüldüğünde düzeltilir; bu yüzden tasarımcılar aliasing'i bilerek kabul eder.

Sonuç olarak, adresleri index'lenen/tag'lenen bitlerde uyuşan ama kesilen üst bitlerde farklılaşan iki branch aynı entry'ye iner. Bir branch'in öğrenilmiş target'ı sonra diğerine sunulur. İki branch farklı process'lerde ya da privilege seviyelerinde yaşadığında bu, basit bir misprediction yerine bir güvenlik sınırı aşımı haline gelir.

Spectre v2 makalesinde Kocher ve arkadaşları, mistraining için "yalnızca virtual address'lerin taklit edilmesi gerektiğini" gözlemledi — kısmi-bit index'lemenin doğrudan bir sonucu. Yakın tarihli Intel çekirdeklerinin Indirector reverse-engineering'i, indirect predictor'ın history'yi bir 9-bit index ve bir 11-bit tag'e katladığını, "tag'in 10 bitinin doğrudan PC bitleriyle XOR'landığını" ve her tablonun way başına 512 entry ile 2-way set-associative olduğunu buldu — collision'ları kasıtlı olarak provoke etmek için yeterince küçük.

Walkthrough

Amaç, aynı BTB entry'sinde collide eden iki virtual address bulmaktır; bu, zehirlenmiş bir target yerleştirmenin önkoşuludur (bkz. Branch Target Buffer Poisoning).

1. Bir victim branch VA'sı seç ve düşük index bitlerini paylaşan ama üstte farklılaşan aday "collide eden" VA'ları numaralandır:

victim_branch_va = 0x...._XYZ          # low bits select the BTB set
for hi in 0..K:                        # vary only the truncated upper bits
    cand = (hi << HIGH_SHIFT) | (victim_branch_va & LOW_MASK)
    test_collision(cand, victim_branch_va)

2. Collision'ı ampirik olarak test et. Adayı bilinen bir target'a train et, victim'i çalıştır ve victim'in adayın target'ına mispredict edip etmediğini kontrol et (timing ya da bir marker gadget bunu açığa çıkarır):

function test_collision(cand, victim):
    train branch@cand -> marker_target  (repeat to lock the entry)
    execute branch@victim
    if victim transiently executed marker_target:
        return COLLIDES        # cand and victim share a BTB entry

3. Indirect branch'ler için global history'yi (BHB) de eşleştir. Folding, effective index'i history'ye bağımlı kılar; bu yüzden özdeş düşük PC bitleri yeterli değildir:

$ ./btb-collide --victim 0x5555_5555_1080
matched VA 0x1080 (same low 12 bits), BHB replayed: COLLIDES
control VA 0x2080 (differs in low bits):              no collision

Collision'lar modele özgüdür

Index genişliği, tag folding, history uzunluğu ve SMT-thread/core-ID'nin tag'in parçası olup olmadığı — hepsi mikromimariye göre değişir. Bir çekirdekte çalışan bir collision reçetesi, başka bir çekirdekte yeniden türetilmeyi gerektirebilir (örn. Branch History Buffer Fingerprinting aracılığıyla).

Mitigation

  • IBPB, predictor state'ini flush'lar; böylece cross-context collision'lar bir privilege/context sınırı boyunca kalıcı olamaz.
  • Retpoline, indirect branch'ler için BTB'yi tamamen es geçer ve o noktalarda collision'ları alakasız kılar.
  • Daha büyük / tamamen tag'lenmiş predictor'lar ve bir security-domain tag'i eklemek, alan/latency maliyetiyle istenmeyen aliasing'i azaltır.

References