6.1810 2025 Lecture 23: Meltdown

Meltdown: Reading Kernel Memory from User Space, Lipp et. al., 2018.

Reminder: security is a top-level O/S goal
  Malicious user code is one source of attacks
  The kernel's main strategy: isolation
    User/supervisor mode, page tables, careful system calls, containers, &c
  If you set it all up correctly, what could go wrong?

Why this Meltdown paper?
  allowed malicious user code to read kernel memory, despite page protections.
  surprising and disturbing
  one of a number of recent "micro-architectural" attacks
    exploiting hidden implementation details of CPUs
  fixable, but people fear an open-ended supply of related surprises
    Linux:  grep . /sys/devices/system/cpu/vulnerabilities/*

Ask questions!
  The situation is complex and largely hidden from view.
  Only Intel designers know the details of why attacks do/don't work.
  The rest of us are only guessing.

Here's the core of the attack (this is user code):
1.  char buf[8192]
2.  r1 = <a kernel virtual address>
3.  r2 = *r1
4.  r2 = r2 & 1
5.  r2 = r2 * 4096
6.  r3 = *(buf + r2)
(these are meant to represent machine instructions)

What happens if user code tries to use a kernel address, as at line 3?
  The load will cause a page fault.

This paper assumes the kernel is mapped in each user page table.
  With PTE_U clear.
  [diagram: 0 to 2^64]
  user memory starts at zero; kernel in high addresses.
  this was near universal until these attacks were discovered.
  mapping both user and kernel makes system calls faster.
  the point: *r1 is meaningful, even if forbidden.

So how can this code be useful to an attacker?
  The answer has to do with a bunch of mostly-hidden CPU implementation details.
  Speculative execution and CPU caches.

First, speculative execution.
  This is not yet about security.
  Imagine this ordinary code.
  "r0" &c are registers, and "*r0" is a memory reference.

  r0 = <some address>
  r1 = load x // r1 is a register; x is a variable in RAM
  if(r1 == 1){
    r2 = *r0
    r3 = r2 + 1
  } else {
    r3 = 0
  }

  The "r1 = x" takes 100s of cycles if x has to be fetched from RAM.
  The "if(r1 == 1)" needs that RAM content.
  It would be too bad if the CPU had to pause until the RAM fetch completed.
  Instead, the CPU predicts which way the branch is likely to go,
    and continues executing.
  This is called "speculation".
  So before the "r1 == 1" is resolved,
    the CPU may predict it will be true,
    and speculatively execute the "r2 = *r0",
    and then the "r3 = r2 + 1".

What if the CPU mis-predicts a branch, e.g. x turns out to be zero?
  Register updates of speculative instructions are tentative until commit.
  CPU discards tentative update if it realizes branch was mid-predicted.
  And re-starts execution, in the "else" branch.

Speculative execution helps performance, since it helps
  avoid stalls while the CPU is waiting for slow memory.

What if the CPU predicts r1 == 1,
  and speculatively executes r2 = *r0,
  but r0 holds an invalid pointer?
  If it turns out x == 1, the "r2 = *r0" should raise an exception.
  If it turns out x == 0, the "r2 = *r0" should not raise an exception.

The CPU "retires" instructions only after it is sure they
  won't need to be canceled due to mis-speculation.
  And the CPU retires instructions in order, only after all
    previous instructions have retired, since only then does it
    know that no previous instruction faulted.

Thus a fault by an instruction that was speculatively
  executed may not occur until a while after the instruction finishes.

Speculation is, in principle, transparent.
  Part of the CPU implemention, but not visible in the specification.
  That is, speculation is intended to increase performance without
    changing the results that programs compute.
  The CPU makes speculation transparent by un-doing register
    assignments if it realizes it speculated incorrectly, and doesn't
    raise exceptions from instructions incorrectly speculated.

Some jargon:
  "Architectural features" -- things in the CPU manual, visible to programmers.
  "Micro-architectural" -- not in the manual, intended to be invisible.
    this is most of the billions of transistors on a chip

Another micro-architectural feature: CPU data and TLB caches.
  core
  L1: va,pa | data / TLB: va | pa
  L2: pa    | data
  RAM
Cache split into "cache lines" of e.g. 64 bytes.
If a load misses, data is fetched, and put into the cache.
L1 ("level one") cache is indexed by virtual low bits, for speed.
CPU must consult both L1 and TLB, the latter for permissions
  and physical address for L1 associativity tag,
  to decide if a load hits in the L1.
  (Intel L1 is Virtually Indexed, Physically Tagged (VIPT))
On L1 miss: TLB lookup, L2 lookup with phys addr.
Times:
  L1 hit -- a few cycles.
  L2 hit -- a dozen or two cycles.
  RAM -- 300 cycles.
  TLB miss -- up to 100s of cycles, to walk page table tree.
  A cycle is 1/clockrate, e.g 0.5 nanosecond.

A system call leaves kernel data in L1 cache, after return to user space.
  (Assuming page table has both user and kernel mappings)

Why is it safe for L1 to contain kernel data while executing user code?
  Can user programs read kernel data directly out of the cache?

In real life, micro-architecture is not entirely invisible.
  It affects how long instructions and programs take.
  It's of intense interest to people who write performance-critical code.
  And to compiler writers.
  Intel &c publish optimization guides, advice but few details.

A useful trick: sense whether something is cached.
  This is the paper's Flush+Reload.
  You want to know if function f() uses the memory at address Z.
  1) ensure that Z is not cached.
     Intel CPUs have a clflush instruction.
     Or load enough memory locations to force everything else out of the cache.
  2) call f()
  3) Record the time.
     Modern CPUs let you read a cycle counter.
     For Intel CPUs, it's the rdtsc instruction.
  4) load a byte from address Z
     (you need memory fences to ensure the load really happens)
  5) Record the time again.
  6) If the difference in times is < (say) 50, the load in #4 hit,
     which means f() probably used memory at address Z.
     Otherwise not.

Back to Meltdown -- this time with more detail:

    // in user memory
    char buf[8192]

    // the Flush of Flush+Reload
    clflush buf[0]
    clflush buf[4096]

1.  r1 = <a kernel virtual address>
2.  r2 = *r1
3.  r2 = r2 & 1      // speculated
4.  r2 = r2 * 4096   // speculated
5.  r3 = *(buf+r2)   // speculated

    <eventual fault from *r1; r2 and r3 rolled back, but data left in cache>
    <handle the page fault>

    // the Reload of Flush+Reload
    a = rdtsc
    r0 = buf[0]
    b = rdtsc
    r1 = buf[4096]
    c = rdtsc
    if c-b < b-a:
      low bit was probably a 1

That is, user code can deduce the low bit of the kernel data based on which
of two user cache lines was loaded (buf[0] vs buf[4096]).
  
Point: the fault from "r2 = *r1" is delayed until the load retires,
  which may take a while, giving time for the subsequent speculative
  instructions to execute.

Point: apparently the "r2 = *r1" does the load, even if the PTE
  forbids it, and puts the result into r2, though only temporarily since
  reverted by the fault at retirement.

Point: the "r3 = buf[r2]" loads some of buf[] into the cache,
  even though change to r3 is canceled due to mis-speculation.
  Since Intel views the cache content as hidden micro-architecture.

This attack does work, and many people have reproduced it.

But it often doesn't work:
  Each XX in Listing 3/4 is a failure
    I.e. line 5 didn't cause any of the cache lines to be loaded.
    It's not clear why the failures occur.
    Perhaps the desired kernel data isn't in the cache?
      And isn't fetched from RAM due to PTE permissions?
      Or the load retires and faults before RAM fetch completes?
    Perhaps cache conflicts kick out the array?
    Perhaps TLB misses?
    Perhaps other activity on the machine?
    Perhaps a race between fault retiring and return of data,
      and exact timings vary?
  Section 6.2 says 10 bytes/second if kernel data not cached
    Retries help -- why? Section 5.2, List 2
    Maybe if kernel data not cached, CPU speculates zero.
  The conditions for success are not clear.

How could Meltdown be used in a real-world attack?
  The attacker needs to run their code on the victim machine.
  Timesharing: kernel may have other users' secrets, e.g. passwords, keys.
    And kernel may map all of physical memory, including other processes.
  Cloud: some container and VMM systems might be vulnerable,
    so you could steal data from other cloud customers.
  Your browser: it runs untrusted code in sandboxes, e.g. plug-ins,
    maybe a plug-in can steal your password from your kernel.

Why useful to an attacker if it often (even usually!) doesn't work?
  The rules of the security game:
    Defense must aim to win 100% of the time.
    If the attacker wins 1% of the time, that's a disaster for defense.
  E.g. if attacker can steal passwords of only 1% of users.
  Also, attacker may be able to influence what's in the cache.
    E.g. make system calls, send network requests.

Meltdown is not known to have been used in any actual attack.
  But it has spurred much remedial effort.

What about defenses?

A software fix:
  Don't map the kernel in user page tables.
    The paper calls this "KAISER"; Linux now calls it KPTI.
  Requires a page table switch on each system call entry/exit.
    This is how RISC-V xv6 works.
  The page table switch can be slow -- it may require TLB flushes.
    PCID can avoid TLB flush, though still some expense.
  Many kernels adopted KAISER/KPTI soon after Meltdown was known.

A hardware fix:
  Only return permitted data from speculative loads!
    If PTE_U/R/V is clear, return zero, not the actual data.
  This probably has little cost since CPU must look
    at PTE in TLB anyway for every L1 hit.
  AMD CPUs apparently worked like this all along.
  Modern Intel CPUs seem to do this (called RDCL_NO).

These defenses are deployed and are believed to work; but:
  It was disturbing that page protections turned out to not be solid!
  More micro-architectural surprises have been emerging.
  Is the underlying issue just fixable bugs? Or an error in strategy?
  Stay tuned, this is still playing out.

Next week -- Exam!

References:
https://googleprojectzero.blogspot.com/2018/01/reading-privileged-memory-with-side.html
https://cyber.wtf/2017/07/28/negative-result-reading-kernel-memory-from-user-mode/
https://eprint.iacr.org/2013/448.pdf
https://gruss.cc/files/kaiser.pdf
https://en.wikipedia.org/wiki/Kernel_page-table_isolation
https://spectrum.ieee.org/computing/hardware/how-the-spectre-and-meltdown-hacks-really-worked
https://lwn.net/Articles/741878/
https://blog.stuffedcow.net/2018/05/meltdown-microarchitecture/