Worked examples — Spectre - Meltdown speculative side channels

5.3.15 · D3 · Hardware › Advanced Microarchitecture › Spectre - Meltdown speculative side channels

Yeh page parent topic ka "concrete banao" companion hai. Hum pehle se idea jaante hain: CPU guess karta hai, aage daudta hai, aur jab woh guess phek deta hai tab bhi cache mein crumbs chhod jaata hai. Yahan hum har tarah ke scenario ko grind karenge jo yeh idea produce kar sakta hai — timing ke har sign, har degenerate input, attack space ka har quadrant — jab tak kuch bhi surprise na kar sake.

Shuru karne se pehle, teen plain-word reminders (koi symbol use nahi hoga jab tak earn na ho):

Ab matrix.

The scenario matrix

Neeche har worked example ek labelled cell ko hit karta hai. Saath mein woh poori space cover karte hain: dono timing signs, degenerate/zero cases, boundary case, ek real word problem, aur ek exam twist.

Cell	Scenario class	Isse "yeh cell" kya banata hai
A	Positive result — ek byte leak hua	Ek read fast hai ($<T_{\text{thr}}$); value recover karo
B	Zero / null result — kuch leak nahi hua	Saare 256 reads slow hain; is round mein secret unrecovered
C	Degenerate secret = 0	Secret byte literally $0x00$ hai; kya attack phir bhi kaam karta hai?
D	Boundary timing ($T_{\text{thr}}$ ke bilkul paas)	Ek read threshold ke paas land karta hai — hit ya miss?
E	Noise / false positive	Do reads fast lagte hain; kaunsa real hai? Rounds par statistics
F	Meltdown arithmetic	Leak rate compute karo; kya ek poora page reasonable time mein dump ho sakta hai?
G	Spectre v1 window sizing	Speculation window kitni wide hai; kya leak fit hoti hai?
H	Spectre v2 BTB aliasing	Kya attacker aur victim branch addresses collide karte hain?
I	Real-world / exam twist	Real numbers ke saath KPTI overhead trade-off

Prerequisites jo aap open rakhna chahein: Cache Memory Hierarchy, Out-of-Order Execution, Branch Prediction, Privilege Levels and Protection Rings, Virtual Memory and Paging, TLB (Translation Lookaside Buffer), Hyperthreading and SMT.

Hum poore page ke liye yeh numbers fix karte hain taaki answers checkable hon:

---

Cell A — Ek byte leak hua (positive result)

Forecast: Aage padhne se pehle guess karo — ek mailbox fast hai, toh secret us mailbox ka index hai. Kaunsa, aur 65 hex mein kya hai?

1. Har read ko threshold se compare karo. Mailbox 65: $5<100$, toh yeh ek hit hai (cached). Baaki har mailbox: $200>100$, ek miss. Yeh step kyun? Threshold $T_{\text{thr}}$ hi poora point hai — yeh ek continuous time ko ek yes/no "kya yeh cached tha?" decision mein convert karta hai. Iske bina hamare paas bas 256 numbers hote.
2. Hit index hi secret hai. Speculation ke dauran victim ne probe[secret * 4096] = ... kiya, toh sirf ek warmed mailbox number secret hai. Yahan woh $65$ hai. Yeh step kyun? Opening figure ki geometry yaad karo: ek secret → ek warm mailbox. Index padhna matlab secret padhna.
3. Hex mein convert karo (bytes conventionally hex mein likhe jaate hain): $65=4\times 16+1=0x41$. Yeh step kyun? $0x41$ ASCII 'A' hai, isliye leaked text buffer letters ki tarah read hogi — yahi wajah hai ki demos recognizable strings print karte hain.

Verify: Ulta karo — $0x41=4\cdot 16+1=65$. Sirf ek read $100$ ns se neeche hai ($5$ ns wala), toh exactly ek byte claim kiya gaya. ✓

---

Cell B — Kuch leak nahi hua (zero result)

Forecast: Koi read threshold ko beat nahi karta — toh humne kaunsi byte recover ki? (Trick: shayad koi nahi.)

1. Threshold se neeche reads count karo. $i$ ki count jahan $T(i)<100$ ns hai woh zero hai. Yeh step kyun? Hamara recovery rule sirf hit par fire karta hai. Koi hit nahi ⇒ koi claim nahi.
2. Zero ko interpret karo. Is round mein speculative load shayad hua hi nahi: branch predictor ne sahi guess kiya (gadget mein enter nahi kiya), ya speculation bahut short thi, ya probe line time karne se pehle kisi aur activity ne evict kar di. Yeh step kyun? Ek null round ek normal, expected outcome hai — attack probabilistic hai. Aap retry karte ho, panic nahi karte.
3. Action: round dobara chalao. Real attacks har byte ke liye tens to thousands of rounds average karte hain.

Verify: Zero reads threshold ke neeche, toh recovered-byte set empty hai; sanity: $0$ claimed bytes, koi contradiction nahi. Yeh woh "denominator" case hai jis par Cell E ki statistics build hoti hai. ✓

---

Cell C — Degenerate secret = 0x00

Forecast: $0\times 4096=0$, toh mailbox 0 warm hoga. Sahi lagta hai — lekin kya mailbox 0 ke saath specifically koi catch hai?

1. Touched mailbox compute karo. $s=0\Rightarrow$ offset $0\times 4096=0$, toh mailbox 0 warm hota hai. Yeh step kyun? Confirm karta hai ki multiply-by-4096 mapping zero end par bhi well-defined hai.
2. Catch yeh hai: mailbox 0 probe_array ke start par hai, jo often unrelated code (array base, loop setup) se prefetch ya touch hota hai. Yeh "hot" dikh sakta hai even jab secret zero nahi hai — byte 0 par false positive. Yeh step kyun? Woh degenerate corner cover karta hai jo multiply hide karta hai: value 0 mathematically nahi balki microarchitecturally special hai, kyunki address 0-offset high-traffic hai.
3. Real exploits jo fix use karte hain — ek fixed offset $\delta$. Yahan $\delta$ (Greek letter "delta") bas ek constant shift hai jo attacker ek baar choose karta hai, jaise $\delta =1$: mailbox $s$ ko touch karne ki jagah, victim gadget mailbox $(s+\delta )\mathrm{mod}256$ ko touch karta hai (yeh "$\mathrm{mod}256$" 255 ke baad wapas 0 par wrap karta hai, taaki hum kabhi 256 mailboxes ke end se bahar na jayein). Reader recovery ke baad $\delta$ wapas subtract karta hai. $\delta =1$ choose karna poori scheme ko ek mailbox upar shift kar deta hai, toh real value 0 ab mailbox 1 par land karta hai — noisy mailbox 0 se door. Yeh step kyun? Full-coverage ka matlab hai ki zero input silently results corrupt na kare — aap ise explicitly handle karte ho mailboxes ko relabel karke taaki high-traffic slot 0 kisi real byte value ke corresponding na rahe.

Verify: $\delta =1$ ke saath: secret $0$ mailbox $(0+1)\mathrm{mod}256=1$ par map hota hai; secret $255$ mailbox $(255+1)\mathrm{mod}256=0$ par map hota hai. 256 values mein se har ek phir bhi ek alag mailbox par land karti hai (shift ek bijection hai), toh koi information lost nahi — hum bas mailbox 0 ko "value 255" padhte hain. ✓ Saath hi, $s\times 4096$ offsets $s=0,\dots ,255$ ke liye saare alag hain (0 se $1,044,480$ tak), base mapping ke injective hone ki confirmation kisi bhi shift se pehle. ✓

---

Cell D — Boundary timing (threshold ke bilkul paas)

Forecast: 98, 100 se neeche hai... lekin sirf barely. Kya hum ise trust karte hain?

1. Rule literally apply karo. $98<100$ ⇒ hit classify hua. Yeh step kyun? Rule ek strict inequality $T(i)<T_{\text{thr}}$ hai; 98 ise satisfy karta hai, toh mechanically yeh hit hai.
2. Khatara. Line ke itna paas value woh jagah hai jahan misclassification rehti hai. Cache-hit times $4$ ns ke paas cluster karte hain aur misses $200$ ns ke paas; ek $98$ ns reading dono nahi hai — likely ek partially-cached line (L2/L3 hit, L1 nahi) ya ek slow-but-uncached fluke. Yeh step kyun? Limiting case cover karta hai jahan do timing populations almost touch karte hain — "grey zone."
3. Exactly 100 ns ka kya? Strict "$<$" ke saath, $100$ ek miss hai (line ke neeche nahi). Yeh ek definition boundary hai — aapko clearly batana hoga ki aapka threshold $<$ hai ya $\le$; ise palto aur answer palat jaata hai. Yeh step kyun? Boundary cases hidden assumptions expose karte hain. Inequality direction explicitly state karo.
4. Robust practice: ek hard line use mat karo — read ko baar baar repeat karo aur minimum time lo (min, interrupts/contention ko filter karta hai). Ek true hit ka min $4$ ns ke paas rehta hai; miss ka min $200$ ns ke paas; $98$ ns grey case gayab ho jaata hai.

Verify: Strict $<$ ke under: $98<100$ ⇒ hit; $100<100$ false hai ⇒ miss. 2 ns ke difference se do alag classifications confirm karta hai ki yeh ek genuine boundary hai. ✓

---

Cell E — Noise aur false positives (rounds par statistics)

Is example se pehle humein ek naya symbol chahiye, kyunki ek page kabhi aisi notation use nahi kar sakta jo usne earn nahi ki.

Forecast: 65 bahut badi lead se jeet raha hai — lekin 200 ke 6 hits zero nahi hain. Hum 65 choose karne ko kaise justify karte hain?

1. Hit-counts ka histogram banao. Mailbox 65 → 83; mailbox 200 → 6; noise floor $\le 2$. Yeh step kyun? Ek round noisy hota hai (Cell B ne dikhaya ki rounds blank ho sakte hain). Aggregate karna ek coin-flip ko landslide mein badal deta hai.
2. Argmax chuno. Secret woh byte hai jiska mailbox sabse zyada baar fast hota hai: $\arg {\max }_i\text{count}(i)=65$ — yani index 65, number 83 nahi. Yeh step kyun? Random cache activity (prefetch, neighbours) har jagah kuch false hits chirakte hain; true signal unke upar towering hota hai. Hum winning label chahte hain, jo exactly wahi hai jo $\arg \max$ return karta hai.
3. Confidence check. Signal-to-noise: true byte 83 hits vs. next-highest 6 hits. Ratio $83/6\approx 13.8\times$. ~3–5 se kaafi upar ratio ek confident recovery hai. Yeh step kyun? "Bahut badi lead" ko quantify karta hai taaki exam answer hand-wavy na ho.

Verify: $\arg \max \{83,6,2,\dots \}=65$; ratio $83/6=13.833\dots >5$. Confident. ✓

---

Cell F — Meltdown leak-rate arithmetic

Forecast: Pehle apne dimaag mein rough karo — thousands of bytes, tens of rounds each, tens of µs per round... seconds? Dekho.

1. Poore page ke liye rounds. $4096\text{ bytes}\times 10\text{ rounds/byte}=40,960$ rounds. Yeh step kyun? Total kaam = bytes × rounds-per-byte. Linear, kyunki har byte independent hai.
2. Total time. $40,960\text{ rounds}\times 50\mu \text{s}=2,048,000\mu \text{s}=2.048$ seconds. Yeh step kyun? µs ko seconds mein convert karo ($1\text{s}=10^6\mu \text{s}$) ek human-scale number paane ke liye.
3. Rate. $4096\text{ bytes}/2.048\text{ s}=2000\text{ bytes/s}\approx 1.95$ KB/s ($1\text{ KB}=1024$ B use karte hue). Yeh step kyun? Rate = data / time; yahi woh number hai jo papers quote karte hain (original Meltdown ne optimizations ke saath hundreds of KB/s report kiya — hamara deliberately pessimistic hai).

Verify: $4096\times 10\times 50\mu \text{s}=2.048\text{s}$; $4096/2.048=2000$ B/s; $2000/1024=1.953125$ KB/s. Feasible — ~2 s mein ek page bahut practical hai. ✓

---

Cell G — Spectre v1 speculation-window sizing

Forecast: Window 200 ns hai; hum chahte hain ki branch resolve hone se pehle 4 ns + 20 ns ka useful kaam ho. Comfortable hai ya tight?

1. Window length = branch resolve hone tak ka time. Compare tab resolve hota hai jab array1_size memory se aata hai: branch fetch hone ke $200$ ns baad. Yeh step kyun? Speculation exactly tab tak chalta hai jab tak CPU ko true branch direction pata na ho — wahi woh moment hai jab flushed operand land karta hai. Yeh Branch Prediction mispredict-penalty gap hai, aur yahi poora budget hai jo hume milta hai kaam karne ke liye.
2. 20 ns issue latency justify karo. t = array1[x] apni value produce karne ke baad, CPU probe[t*4096] instantly fire nahi kar sakta: usse (a) address t*4096 compute karna hoga (ek shift/multiply, ~1 cycle), (b) ek free load port dhundhna hoga aur load-buffer entry allocate karni hogi, aur (c) TLB (Translation Lookaside Buffer) se address translate karna hoga. 3 GHz CPU par (1 cycle $\approx 0.33$ ns) yeh ~60 cycles of address-gen + port-allocation + TLB lookup $60\times 0.33\approx 20$ ns hote hain. Yeh step kyun? Window budget meaningless hai jab tak hum cost na jaanein jo kaam hum fit karna chahte hain — 20 ns real pipeline stages se derive hua hai, assert nahi kiya gaya.
3. Woh kaam add karo jo fit hona chahiye. Load array1[x] (4 ns, cached) → phir probe load issue karo (20 ns): needed $=4+20=24$ ns. Hume sirf probe access start karna hai; iska cache footprint rollback ke baad bhi persist karta hai (yahi poora trick hai). Yeh step kyun? Secret encode karne ke liye probe load ko sirf apni cache line touch karni hai; completion zaruri nahi, toh 24 ns hi true requirement hai.
4. Compare aur conclude. $24\text{ ns}\ll 200\text{ ns}$, slack $=200-24=176$ ns ke saath. Leak comfortably fit hoti hai. Aur yahi wajah hai ki attackers array1_size flush karte hain: flush ke bina compare khud ek cached ~4 ns operation hoti, sirf $4$ ns ka window deti — $24$ ns kaam se chhoti — toh leak nahi fit hoti. Flushing window ko ~4 ns se 200 ns tak badha deta hai, "impossible" ko "easy" mein badal deta hai. Out-of-Order Execution se: ek lambi window ka matlab hai zyada speculative instructions apne microarchitectural effects retire kar sakti hain.

Verify: $4+20=24$; $24<200$ ⇒ fit; slack $200-24=176$ ns $>0$. Counter-case: flush ke bina, window $\approx 4$ ns aur $4<24$ ⇒ leak nahi fit hoti — confirming karta hai ki flush essential hai. ✓

---

Cell H — Spectre v2 BTB aliasing

Forecast: Same slot ⇔ same low 12 bits ⇔ same address mod 4096. Har address ke last teen hex digits dekho...

1. Har BTB index compute karo $=\text{addr}\mathrm{mod}{2}^{12}$. Kyunki $2^{12}=4096=0x1000$, ek address ko mod 4096 lena exactly low 3 hex digits rakhta hai.
   • Victim: 0x4FF230 → low 3 digits 0x230 $=2\cdot 256+3\cdot 16+0=560$.
   • Attacker: 0x120230 → low 3 digits 0x230 $=560$. Yeh step kyun? BTB ek chhoti hardware table hai; ise cheaply index karne ke liye CPU sirf branch address ke bottom bits use karta hai. Yeh wahi partial-address aliasing idea hai jaise Cache Memory Hierarchy mein cache indexing.
2. Dono indices compare karo. $560=560$ ⇒ same slot. High bits (0x4FF vs 0x120) store/check nahi hote, toh hardware dono branches mein farq nahi kar sakta. Yeh step kyun? BTB ek predicted target store karta hai, full source address nahi — wahi missing tag exact vulnerability hai.
3. Consequence state karo. Attacker apna branch train karta hai chosen "gadget" address par jump karne ke liye; victim ka call, slot share karte hue, woh target inherit karta hai aur attacker-chosen code ko victim ke privilege context mein speculatively execute karta hai. (Retpoline ise defeat karta hai BTB ki jagah indirect jumps ko return-stack buffer ke through route karke.) Yeh step kyun? Collision akela harmless hai; payoff yeh hai ki victim attacker-chosen code speculatively run karta hai.

Verify: Kya $0x4FF230\mathrm{mod}4096=0x120230\mathrm{mod}4096$? Dono $0x230=560$ ke barabar hain ⇒ collision confirmed. Counter-case: 0x4FF231 $561\ne 560$ deta hai ⇒ koi poison nahi, dikhata hai ki test discriminating hai. ✓

---

Cell I — Real-world / exam twist: KPTI overhead

Forecast: 200k syscalls × 150 cycles 30 million cycles/s hai 3 billion mein se — roughly 1%? Confirm karo aur interpret karo.

1. Extra cycles per second. $200,000\times 150=30,000,000$ cycles/s purely KPTI TLB flushes par spend hue. Yeh step kyun? Overhead = (event frequency) × (per-event cost) — same shape jaise Cell F ki leak-rate arithmetic.
2. 3 GHz budget ke fraction ke roop mein. $\frac{30,000,000}{3,000,000,000}=0.01=1\%$. Yeh step kyun? Time lost ka fraction = extra cycles ÷ total cycles available per second; "per second" cancel ho jaata hai, sirf ek pure ratio bachta hai.
3. Range ke against interpret karo. $1\%$ 5–30% band se neeche hai. Woh band syscall-heavy workloads assume karta hai (databases, network servers jo millions of syscalls/s karte hain); hamara 200k/s server comparatively syscalls par light hai, toh yeh kam pay karta hai. Yeh step kyun? Exam twist: "5–30%" workload-dependent hai, koi fixed constant nahi. Sahi answer us assumption ko name karta hai jo ise drive karta hai.

Verify: $200000\times 150=30\times 10^6$; $30\times 10^6/3\times 10^9=0.01=1\%$, jo $<5\%$ hai ⇒ quoted band se neeche, light syscall load ke saath consistent. ✓

---

Recall Self-test — answers cover karo

Threshold se faster ek probe read ka matlab kya hai? ::: Us mailbox ki cache line hot hai ⇒ uska index leaked secret byte ke barabar hai. Probe mailboxes ko 4096 bytes se kyun space karte hain? ::: Ek page apart ⇒ har byte value ek alag cache line par map hoti hai, toh koi do values alias nahi karte (false sharing se bachte hain). Spectre v1 mein ek attacker array1_size ko flush kyun karta hai? ::: Bounds compare ko cache miss aur ~200 ns stall banane ke liye, speculation window ko widen karte hue taaki leak fit ho (Cell G). Do indirect branches BTB mein ek doosre ko kab poison karte hain? ::: Jab unke addresses $2^n$ ke modulo barabar hon (same low index bits), high bits se independent (Cell H). Threshold ke paas ek single fast read — trust karo? ::: Nahi; bahut saare reads par minimum lo aur rounds par aggregate karo (Cells D, E).