Exercises — Spectre - Meltdown speculative side channels

• The state that rolls back = architectural state (registers, and memory as programs see it).
• The state that keeps footprints = microarchitectural state (caches, branch predictor tables, TLB).
• Meltdown reads the microarchitectural state — specifically cache timing — to recover a byte that the architectural state already threw away.

Why two states exist: an out-of-order core must be free to try work and undo it cheaply. Undoing registers is cheap; scrubbing every cache line touched on a wrong path was judged too expensive — that omission is the bug.

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

Key distinction: in Meltdown the attacker's own code does the forbidden read; in Spectre the victim's code is tricked into doing it.

clflush evicts that cache line — pushes it back to main memory so it is no longer "hot".

Why necessary: the whole trick is that after speculation, exactly one probe line becomes cached. If lines were already cached from before, every one would look fast and you couldn't tell which byte the secret was. Flushing gives a clean canvas so the single hot line stands out.

Printable ASCII letters live in 0x41–0x5A (A–Z) and 0x61–0x7A (a–z).

• 0x00 → NUL, not a letter.
• 0x41 → 'A' ✅ printable letter.
• 0x80, 0xC3, 0xFF → all above 0x7F, non-ASCII.

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

This is why real attacks repeat the measurement many times and vote: hardware prefetchers cache neighbours, so a few false hits are normal.

The hardware prefetcher loves fetching adjacent cache lines. With 64-byte stride, byte value $i$ and byte value $i+1$ sit on back-to-back cache lines — a prefetch triggered by touching one warms the other. That creates false hits.

With 4096-byte stride, consecutive byte values are $4096/64=64$ cache lines apart — far outside the usual prefetch stream, so simple prefetch false-sharing is avoided.

Caveat — this is necessary, not sufficient. "Distinct cache line" is not the same as "distinct cache set". A set-associative L1 maps an address to a set using bits above the 6 line-offset bits. Because $4096=2^{12}$ is a large power of two, all 256 probe pages can land in the same few sets (their differing bits are the page-number bits, which the set-index function may ignore). If more than (associativity) of them share a set, they evict each other — your signal vanishes. Real exploits therefore also (a) page-align the probe array, and (b) add a small per-page offset or use a non-power-of-two effective stride so the 256 lines spread across many sets. So the rule is: 4096 stride to dodge the prefetcher, plus alignment and set-spreading to dodge self-eviction.

Cost of the basic scheme: $256\times 4096=1,048,576$ bytes = 1 MiB of probe array. Memory traded for signal clarity.

Window length: $\Delta t_{\text{spec}}=t_{\text{compute}}-t_{\text{predict}}=200-1=199\text{ cycles}.$ Instructions that fit: $N=\lfloor \frac{199}{4}\rfloor =49.$ So ~49 instructions — plenty to do a dependent load array2[array1[x]*4096] and encode the byte. This is exactly why the attack flushes array_size: a cache miss on the condition stretches the window from a few cycles to hundreds.

Only the low 12 bits matter. $2^{12}=4096=\text{0x1000}$, so the index = the last three hex digits.

• Victim index = 0x234.
• Colliding attacker address: any address ending in 0x234, e.g. 0x0000_0234 or 0xDEAD_1234. Both give index 0x234.
• Non-colliding: any address whose low 12 bits differ, e.g. 0xDEAD_1235 (index 0x235).

Why this is dangerous: the attacker doesn't need to share the victim's full address — just the low bits. So attacker code in a completely different region can plant a fake target that the victim's predictor later trusts.

• Meltdown (reading the host kernel from the guest): largely blocked, because KPTI unmaps kernel pages from the user page tables — the forbidden address isn't even mapped, so there's nothing to speculatively load.
• Spectre v1/v2 still work. KPTI only isolates page tables; it does nothing to the branch predictor / BTB, which is shared across contexts (and across SMT threads). An attacker can still poison a branch so the victim's own code speculatively reads the victim's secret.

Key insight: KPTI hides addresses. Spectre doesn't need forbidden addresses — it tricks legitimate code into misusing its own legitimate access. Different disease, different cure.

• A direct branch encodes its target inside the instruction (jmp label → the address is right there). The CPU only has to predict taken/not-taken — a 1-bit-ish guess.
• An indirect branch (jmp *rax) has its target in a register or memory that may not be ready. The CPU must predict the whole 64-bit destination from the BTB: $(\text{branch addr},\text{history})\to \text{target addr}$.

Predicting a full address gives the attacker a much richer thing to poison: instead of just flipping a direction, they can steer speculation to any gadget whose address they inject into the BTB. That's the whole power of Branch Target Injection.

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\%.$ That's only 0.1 % — below the parent's 5–30 % band, because our syscall rate is modest. The 5–30 % figures come from syscall-heavy workloads (databases, strace-like patterns) doing millions of syscalls/sec, where the flush and the resulting TLB/cache misses on re-entry pile up. Frequency is everything.

The 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

Walk the mechanism in order:

1. The call trains the RSB. A call does two things: it pushes the address of the next instruction (capture_spec) onto the memory stack, and it pushes that same address onto the Return Stack Buffer, the CPU's private hardware predictor for ret. So the RSB now firmly predicts: "the matching ret will return to capture_spec."
2. Why speculation goes to capture_spec. When the CPU reaches the ret in step (4), it will speculatively jump to whatever the RSB predicts — and the RSB was just trained (step 1) to predict capture_spec, not any attacker-injected BTB target. Crucially, ret uses the RSB, which only an actual call can fill; the attacker cannot poke it the way they poke the BTB. So the wrong-path speculation lands in the pause/jmp loop — a dead end that touches no secret and no probe array. Nothing leaks on the speculative path.
3. Why the architectural path is still correct. Meanwhile, the real return address on the memory stack was overwritten in step (2) with the true target from %rax. When the ret finally resolves architecturally, it pops that overwritten value and lands on the correct destination. So: speculation → harmless loop; retirement → correct target. Best of both.

One line: convert an attacker-controllable prediction (BTB) into a benign, self-contained one (RSB) that can only ever aim at our own spin-loop.

The safety does not depend on the store finishing "in time" to steer the ret. It rests on which predictor the ret uses:

• Speculative direction is fixed by the RSB, not by the stack value. When ret is encountered speculatively, the CPU does not wait to read (%rsp) from memory — it uses the RSB's already-trained prediction (capture_spec). So even if the mov store is still in flight, the speculative target is guaranteed to be the harmless loop. The attacker's poisoned BTB entry is simply never consulted for a ret.
• Architectural direction is fixed by the store, resolved in order. The ret is not allowed to retire until its true operand — the value at (%rsp) — is known, and the mov that writes it retires before the ret (program order on the same stack slot forces the load side of ret to see the store's result via store-to-load forwarding). So when ret finally commits, it reads the correct %rax target. If the RSB guess was wrong (it is, unless the real target equals capture_spec), the pipeline squashes the harmless-loop work and redirects — but that squashed work never touched a secret.

The key "why nothing leaks": the only path speculation can take here is into the fenced pause loop, because that path is chosen by the RSB, an unpoisonable structure. There is no speculative window in which ret jumps to attacker-chosen gadget code, so no secret-dependent load can ever run on the wrong path. Correctness of the final jump is guaranteed separately by in-order retirement of the store then the return.

Serial dependency (each waits for the previous):

• Step 1 read array1[x]: cache miss → 200 cycles. Already exceeds the 199-cycle window.

So if step 1 misses, the window closes before step 3 encodes anything — no leak. That's why a real attacker pre-caches array1[x] (or arranges it to be a hit), keeping step 1 near 30 cycles: $30+\sim 4(\text{multiply})+30=\sim 64\text{ cycles}<199.✓$ Only when the dependency chain fits does the secret reach the cache. Timing is the attack's true constraint.

Any shared, timing-observable, speculation-touchable resource works. Strong candidates:

• TLB (Translation Lookaside Buffer): a speculative load to page $P_{\text{secret}}$ installs a TLB entry. Encode: the secret byte selects which of 256 candidate pages is touched. Decode: later, time an access to each candidate page — a TLB hit skips the page-table walk and is faster than a TLB miss. Flushing the data cache doesn't flush the TLB, so the signal survives.
• BTB / predictor state: speculatively execute a branch whose presence/direction depends on the secret bit; later measure prediction latency for that branch to read the bit back.
• Port contention on an SMT sibling thread: the secret steers which execution port the victim uses; a co-resident attacker thread measures its own slowdown on that port.

The moral: the vulnerability is speculation leaving footprints, not cache specifically. Plug one channel and the signal migrates. That is why durable fixes limit speculation itself (barriers, lfence) rather than chasing individual channels.

• 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}.$ About 0.15 seconds — well under a fifth of a second. This is what makes speculative side channels practical, not theoretical: even a slow, redundant attack empties a private key faster than you can blink.

lfence forces earlier instructions to complete before later ones issue — it collapses $\Delta t_{\text{spec}}\to 0$ at that point, so no speculative leak chain can run there. The attacker is right that at a fenced branch the channel dies.

But you cannot fence every branch: modern code executes billions of branches, and each lfence serialises the pipeline (throws away the out-of-order parallelism that made the CPU fast). Fencing everywhere can cost 2×–10× slowdown — unacceptable in practice.

Honest trade-off: defenders fence only security-critical branches (bounds checks guarding secret-indexed loads), found by compilers/analysis. It's a targeted patch, not a blanket cure — which is precisely why Spectre is called a class of bugs that keeps producing new variants.

The two CPU states are architectural and microarchitectural. Meltdown reads across the privilege boundary; Spectre poisons the branch predictor. The probe stride is 4096 bytes to dodge the prefetcher. BTB index uses the low address bits, enabling aliasing collisions. KPTI defends Meltdown; retpoline defends Spectre v2 using the RSB.