Exercises — Spectre - Meltdown speculative side channels

• Woh state jo roll back hoti hai = architectural state (registers, aur memory jaisi programs dekhti hain).
• Woh state jo footprints rakhti hai = microarchitectural state (caches, branch predictor tables, TLB).
• Meltdown microarchitectural state padhta hai — specifically cache timing — ek aisa byte recover karne ke liye jo architectural state already throw away kar chuka hai.

Do states kyun exist karte hain: ek out-of-order core ko try karne aur sasti undo karne ki freedom honi chahiye. Registers undo karna sasta hai; galat path par touch ki gayi har cache line scrub karna bahut expensive tha — yahi omission bug hai.

• (a) Meltdown → 2 (CVE-2017-5754). privilege check timing use karta hai.
• (b) Spectre v1 → 3 (CVE-2017-5753), Bounds Check Bypass.
• (c) Spectre v2 → 1 (CVE-2017-5715), Branch Target Injection.

Key distinction: Meltdown mein attacker ka apna code forbidden read karta hai; Spectre mein victim ka code use trick kiya jaata hai ki woh khud yeh kare.

clflush us cache line ko evict karta hai — use main memory mein wapas push karta hai taaki woh "hot" na rahe.

Kyun zaroori hai: poora trick yeh hai ki speculation ke baad, exactly ek probe line cached ho jaati hai. Agar lines pehle se cached hoti, toh har ek fast lagti aur tum nahi bata paate ki secret kaun sa byte tha. Flushing ek clean canvas deta hai taaki woh single hot line stand out kare.

Printable ASCII letters 0x41–0x5A (A–Z) aur 0x61–0x7A (a–z) mein rehte hain.

• 0x00 → NUL, letter nahi.
• 0x41 → 'A' ✅ printable letter.
• 0x80, 0xC3, 0xFF → sab 0x7F se upar, non-ASCII.

Secret byte = 0x41 = 'A' = decimal 65.

Isliye real attacks measurement ko kai baar repeat karke vote karte hain: hardware prefetchers neighbours ko cache karte hain, isliye kuch false hits normal hain.

Hardware prefetcher ko adjacent cache lines fetch karna pasand hai. 64-byte stride ke saath, byte value $i$ aur byte value $i+1$ back-to-back cache lines par baithte hain — ek ko touch karne se trigger hua prefetch doosre ko bhi warm kar deta hai. Isse false hits create hote hain.

4096-byte stride ke saath, consecutive byte values $4096/64=64$ cache lines door hain — usual prefetch stream se bahut bahar, isliye simple prefetch false-sharing avoid hoti hai.

Caveat — yeh zaroori hai, sufficient nahi. "Distinct cache line" aur "distinct cache set" ek nahi hai. Ek set-associative L1 ek address ko 6 line-offset bits ke upar ke bits use karke ek set par map karta hai. Kyunki $4096=2^{12}$ ek bada power of two hai, saare 256 probe pages ek hi kuch sets mein land kar sakte hain (unke differing bits page-number bits hain, jinhein set-index function ignore kar sakta hai). Agar unme se (associativity) se zyada ek set share karte hain, toh woh ek doosre ko evict karte hain — tumhara signal gayab ho jaata hai. Real exploits isliye (a) probe array ko page-align karte hain, aur (b) ek small per-page offset ya non-power-of-two effective stride add karte hain taaki 256 lines kai sets mein spread ho jaayein. Toh rule yeh hai: prefetcher se bachne ke liye 4096 stride, aur saath hi self-eviction se bachne ke liye alignment aur set-spreading.

Basic scheme ka cost: $256\times 4096=1,048,576$ bytes = 1 MiB probe array. Memory, signal clarity ke badle mein.

Window length: $\Delta t_{\text{spec}}=t_{\text{compute}}-t_{\text{predict}}=200-1=199\text{ cycles}.$ Instructions jo fit hongi: $N=\lfloor \frac{199}{4}\rfloor =49.$ Toh ~49 instructions — array2[array1[x]*4096] ek dependent load karne aur byte encode karne ke liye kaafi hain. Isliye attack array_size ko flush karta hai: condition par cache miss window ko kuch cycles se kheench kar hundreds tak le jaata hai.

Sirf low 12 bits matter karte hain. $2^{12}=4096=\text{0x1000}$, isliye index = last teen hex digits.

• Victim index = 0x234.
• Colliding attacker address: koi bhi address jo 0x234 par khatam ho, jaise 0x0000_0234 ya 0xDEAD_1234. Dono index 0x234 dete hain.
• Non-colliding: koi bhi address jiske low 12 bits alag hon, jaise 0xDEAD_1235 (index 0x235).

Yeh kyun dangerous hai: attacker ko victim ka full address share nahi karna — bas low bits. Isliye ek bilkul alag region mein attacker code ek fake target plant kar sakta hai jis par victim ka predictor baad mein trust karta hai.

• Meltdown (host kernel ko guest se padhna): largely blocked, kyunki KPTI kernel pages ko user page tables se unmap karta hai — forbidden address map hi nahi hai, isliye speculatively load karne ke liye kuch nahi.
• Spectre v1/v2 abhi bhi kaam karte hain. KPTI sirf page tables isolate karta hai; yeh branch predictor / BTB ke liye kuch nahi karta, jo contexts mein (SMT threads ke across bhi) shared hai. Attacker abhi bhi ek branch poison kar sakta hai taaki victim ka khud ka code victim ka secret speculatively padhle.

Key insight: KPTI addresses chhupata hai. Spectre ko forbidden addresses ki zaroorat nahi — yeh legitimate code ko apne khud ke legitimate access galat tarike se use karne ke liye trick karta hai. Alag bimari, alag ilaaj.

• Ek direct branch apna target instruction ke andar encode karta hai (jmp label → address wahan hi hai). CPU ko sirf taken/not-taken predict karna hai — ek 1-bit-ish guess.
• Ek indirect branch (jmp *rax) ka target ek register ya memory mein hota hai jo ready nahi ho sakta. CPU ko BTB se poora 64-bit destination predict karna hoga: $(\text{branch addr},\text{history})\to \text{target addr}$.

Ek full address predict karna attacker ko poison karne ke liye bahut zyada rich cheez deta hai: sirf direction flip karne ki jagah, woh speculation ko BTB mein inject ki gayi kisi bhi gadget ki taraf steer kar sakte hain. Yahi Branch Target Injection ki poori power hai.

Cycles lost per second: $150\times 20,000=3,000,000\text{ cycles/s}.$ Total cycles per second: $3\times 10^9\text{ cycles/s}.$ Fraction: $\frac{3\times 10^6}{3\times 10^9}=10^{-3}=0.1\%.$ Yeh sirf 0.1 % hai — parent ke 5–30 % band se neeche, kyunki humari syscall rate modest hai. 5–30 % figures syscall-heavy workloads (databases, strace-like patterns) se aate hain jo millions of syscalls/sec karte hain, jahan flush aur re-entry par resulting TLB/cache misses pile up karte hain. Frequency sab kuch hai.

Retpoline pattern:

    call set_up_target      ; (1) push return addr; RSB now predicts 'capture_spec'
capture_spec:
    pause                   ; (3) benign spin if speculation lands here
    jmp capture_spec
set_up_target:
    mov %rax, (%rsp)        ; (2) overwrite the return address with the real target
    ret                     ; (4) RET pops -> real target

Mechanism ko order mein walk karo:

1. call RSB ko train karta hai. Ek call do kaam karta hai: yeh next instruction (capture_spec) ka address memory stack par push karta hai, aur wahi address Return Stack Buffer par push karta hai, jo CPU ka private hardware predictor hai ret ke liye. Isliye RSB ab firmly predict karta hai: "matching ret capture_spec par return karega."
2. Speculation capture_spec kyun jaati hai. Jab CPU step (4) mein ret tak pahunchta hai, woh speculatively RSB jo predict kare wahan jump karega — aur RSB abhi abhi (step 1 mein) capture_spec predict karne ke liye train hua tha, kisi bhi attacker-injected BTB target ko nahi. Crucially, ret RSB use karta hai, jise sirf ek actual call fill kar sakta hai; attacker ise BTB ki tarah poke nahi kar sakta. Isliye wrong-path speculation pause/jmp loop mein land hoti hai — ek dead end jo koi secret ya probe array touch nahi karta. Speculative path par kuch leak nahi hota.
3. Architectural path abhi bhi correct kyun hai. Dauraan, memory stack par real return address step (2) mein %rax ke true target se overwrite ho gaya. Jab ret architecturally finally resolve hota hai, woh us overwritten value ko pop karta hai aur correct destination par land karta hai. Toh: speculation → harmless loop; retirement → correct target. Dono ka best.

Ek line mein: attacker-controllable prediction (BTB) ko ek benign, self-contained prediction (RSB) mein convert karo jo sirf apne khud ke spin-loop ki taraf aim kar sakti hai.

Safety is baat par depend nahi karti ki store "in time" finish ho jaaye ret steer karne ke liye. Yeh is baat par depend karti hai ki kaun sa predictor ret use karta hai:

• Speculative direction RSB se fix hoti hai, stack value se nahi. Jab ret speculatively encounter hota hai, CPU (%rsp) ko memory se padhne ka wait nahi karta — yeh RSB ki already-trained prediction (capture_spec) use karta hai. Isliye bhale hi mov store abhi in flight ho, speculative target harmless loop hoga hi. Attacker ka poisoned BTB entry ret ke liye kabhi consult nahi hota.
• Architectural direction store se fix hoti hai, in order resolve hoti hai. ret ko retire hone ki permission nahi milti jab tak uska true operand — (%rsp) par value — nahi pata, aur mov jo ise likhta hai ret se pehle retire hota hai (same stack slot par program order load side ko store ka result store-to-load forwarding se dekhne par majboor karta hai). Isliye jab ret finally commit hota hai, woh correct %rax target padhta hai. Agar RSB guess galat tha (hai, jab tak real target capture_spec ke equal nahi), pipeline harmless-loop work squash karke redirect karta hai — lekin woh squash hua kaam kabhi kisi secret ko touch nahi kiya.

Key "kuch leak kyun nahi hota": speculation sirf fenced pause loop mein ja sakti hai, kyunki woh path RSB se choose hota hai, jo ek unpoisonable structure hai. Koi aisa speculative window nahi hai jismein ret attacker-chosen gadget code par jump kare, isliye koi secret-dependent load kabhi wrong path par run nahi ho sakta. Final jump ki correctness alag se store ki in-order retirement phir return se guarantee hoti hai.

Serial dependency (har ek pichle ka wait karta hai):

• Step 1 array1[x] padho: cache miss → 200 cycles. Pehle hi 199-cycle window exceed ho gayi.

Isliye agar step 1 miss kare, window step 3 kuch encode karne se pehle band ho jaati hai — koi leak nahi. Isliye ek real attacker array1[x] pre-cache karta hai (ya arrange karta hai ki yeh hit ho), step 1 ko ~30 cycles ke paas rakhta hai: $30+\sim 4(\text{multiply})+30=\sim 64\text{ cycles}<199.✓$ Sirf jab dependency chain fit karti hai tabhi secret cache tak pahunchta hai. Timing attack ka true constraint hai.

Koi bhi shared, timing-observable, speculation-touchable resource kaam karta hai. Strong candidates:

• TLB (Translation Lookaside Buffer): page $P_{\text{secret}}$ par ek speculative load ek TLB entry install karta hai. Encode: secret byte select karta hai ki 256 candidate pages mein se kaun sa touch kiya jaaye. Decode: baad mein, har candidate page ka access time karo — ek TLB hit page-table walk skip karta hai aur TLB miss se faster hota hai. Data cache flush karna TLB flush nahi karta, isliye signal survive karta hai.
• BTB / predictor state: ek aisa branch speculatively execute karo jiska presence/direction secret bit par depend karta ho; baad mein us branch ke liye prediction latency measure karo bit wapas padhne ke liye.
• Port contention ek SMT sibling thread par: secret steer karta hai ki victim kaun sa execution port use kare; ek co-resident attacker thread us port par apna slowdown measure karta hai.

Moral: vulnerability speculation leaving footprints hai, cache specifically nahi. Ek channel plug karo aur signal migrate ho jaata hai. Isliye durable fixes speculation ko limit karte hain (barriers, lfence) individual channels ka peecha karne ki jagah.

• Bytes to leak: $512$.
• Rounds per byte: $10$.
• Time per round: $30\mu s=30\times 10^{-6}$ s. $T=512\times 10\times 30\times 10^{-6}=512\times 300\times 10^{-6}=0.1536\text{ s}.$ Lagbhag 0.15 seconds — ek fifth of a second se bhi kam. Isliye speculative side channels practical hain, theoretical nahi: even ek slow, redundant attack ek private key ek blink se faster khaali kar deta hai.

lfence pehle instructions ko baad wale issue hone se pehle complete hone par majboor karta hai — yeh us point par $\Delta t_{\text{spec}}\to 0$ collapse karta hai, isliye koi speculative leak chain wahan run nahi kar sakti. Attacker sahi hai ki ek fenced branch par channel mar jaata hai.

Lekin tum har branch fence nahi kar sakte: modern code billions of branches execute karta hai, aur har lfence pipeline serialize karta hai (out-of-order parallelism khatam karta hai jo CPU ko fast banata tha). Sab jagah fencing karna 2×–10× slowdown cost kar sakta hai — practice mein unacceptable.

Honest trade-off: defenders sirf security-critical branches fence karte hain (bounds checks jo secret-indexed loads guard karte hain), jo compilers/analysis dhoondhe. Yeh ek targeted patch hai, blanket cure nahi — isliye Spectre ko bugs ki ek class kaha jaata hai jo nayi variants produce karta rehta hai.

Do CPU states hain architectural aur microarchitectural. Meltdown privilege boundary cross karta hai; Spectre branch predictor ko poison karta hai. Probe stride 4096 bytes hai prefetcher se bachne ke liye. BTB index low address bits use karta hai, aliasing collisions enable karta hai. KPTI Meltdown defend karta hai; retpoline Spectre v2 defend karta hai RSB use karke.