Monday, March 09, 2015

Some notes on DRAM (#rowhammer)

My twitter feed is full of comments about the "rowhammer" exploit. I thought I'd write some quick notes about DRAM. The TL;DR version is this: you probably don't need to worry about this, but we (the designers of security and of computer hardware/software) do.

There are several technologies for computer memory. The densest, and hence cheapest-per-bit, is "DRAM". It consists of a small capacitor for each bit of memory. The thing about capacitors is that they lose their charge over time and must be refreshed. In the case of DRAM, every bit of memory must be read them re-written every 64-milliseconds or it becomes corrupt.

These tiny capacitors are prone to corruption from other sources. One common source of corruption is cosmic rays. Another source is small amounts of radioactive elements in the materials used to construct memory chips. So, chips must be built with radioactive-free materials. The banana you eat has more radioactive material inside it than your DRAM chips.


The upshot is that capacitors are unreliable (albeit extremely cheap) technology for memory which readily get corrupted for a lot of reasons. This "rowhammer" exploit works by corrupting the capacitors by overwriting adjacent rows hundreds of thousands of times, hoping that some bits randomly flip. Like cosmic rays or radioactive hits, this only changes the temporary value within the cell, but has no permanent effect.

Because of this unreliability in capacitors, servers use ECC or error-correcting memory. This adds extra memory chips, so that 72 bits are read for every 64 bits of desired memory. If any single bit is flipped, the additional eight bits can be used to correct it.

The upshot of ECC memory is that it should also detect and correct rowhammer bit-flips just as well as cosmic-ray bit-flips. The problem is that ECC memory costs more. The memory itself is about 30% more expensive (although it contains only 12% more chips). An 8-gigabyte DIMM non-ECC costs $60 right now, whereas an ECC equivalent costs $80. The CPUs and motherboards that use ECC memory are also slightly more expensive. Update:  see below.

Note that the hacker doesn't have complete control over which bits will be flipped. They are highly likely to flip the wrong bits and crash the system rather than gain exploitation. However, hackers have lots of ways of mitigating this. For example, as described in the google post, hackers can do a memory spray. They can allocate a large amount of memory, and then set it up so that no matter which bits gets flipped, the resulting value will still point to something valid.

The upshot is that while this problem seems random like cosmic rays, one should realize that hackers can control things better than it would appear. Historically, bugs like stack and heap overflows were once considered too random for hackers to predict, but which were then proven to be solidly predictable. Likewise, address space layout randomization was a technique design to stop hackers, which they then start using memory spray to defeat.

DRAM capacitors are arranged in a rectangular grid or bank. A chip will have multiple banks (usually eight of them). Banks are rectangular rather than square, with more rows than columns. Rows are usually 1024 bits wide, so increasing capacity usually means increasing the number of rows. (The wider the row, the slower the access).

My computer has 16 gigabytes of RAM. It uses two channels, with two DIMMs per channel. Each DIMM is double-sided, which means it has two ranks. Each rank has eight chips acting together to produce 64 bits at a time (or 8 bytes). Each chip in a rank has eight banks. Each bank has 32k rows and 1k columns. Thus, an address might be broken down as follows:

  3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 
  4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |C|D|R|bank | row                           | column            |x x x|
 +-+++++-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  | | |
  | | +-- rank
  | +---- DIMM
  +------ channel

In practice, though, this precise arrangement would be inefficient. If physical addresses were truly laid out this way, then the second memory channel would only be used for the upper half of physical memory. For better performance, you want to interleave memory access, so that on average, half of all memory accesses are on one channel, and the other half on the other channel. Likewise, for best performance, you want to interleave access among the DIMMs, ranks, and banks, and rows. However, you don't want to interleave column access: once a row is open on a particular bank, it's most efficient to read sequentially from that row.

The upshot is that the for optimal performance, the memory controller will rearrange the physical addresses (except for the column portion). Knowledge of how the memory controller does this is needed for robust exploitation of this bug. In today's systems, the memory controller is built-in to the CPU, so exploitation will be different depending upon which CPU a system has.

In today's computers, software doesn't use physical addresses to memory. Instead, they use virtual addresses. This virtual memory means that when a bug causes a program to crash, it doesn't corrupt the memory of other programs, or the memory of the operating system. This is also a security feature, preventing one user account from meddling with another. (Indeed, rowhammer's goal is to bypass this security feature). In old computers, this was also used to trick applications into thinking they had more virtual memory than physical memory in the system. Infrequently used blocks of memory would be removed from the physical memory and saved to disk, and would automatically be read back into the system as needed.

Individual addresses aren't mapped on a one-to-one basis. Instead, the translation is done a page of 4096 addresses at a time. It's the operating system kernel that manages these page tables to create the mappings, and it's the CPU hardware that uses the page tables to do the translations automatically.

The upshot of this is that in order to exploit this bug, the hacker needs to know how virtual memory is translated to physical memory. This is easy on Linux, where a pseudo file /proc/PID/pagemap exists that contains this mapping. It may be harder in other systems.

The hypervisor hosting virtual machines (VMs) use yet another layer of page tables. Unlike operating systems, hypervisors don't expose the physical mapping to the virtual machines. The upshot of this is that people running VMs in the cloud do not have to worry about other customers using this technique to hack them. It's probably not a concern anyway, since most cloud systems use error correcting memory, but the VM translation makes it extra hard to crack.

Thus, the only real vector of exploitation is where a hostile person can run native code on a system. There are some cheap hosting environments where this is possible, running cheap servers without ECC memory, with separate user accounts instead of using virtual machines. However, such environments tend to be so riddled with holes that there are likely easier routes to exploitation than this one.

The biggest threat at the moment appears to be to desktops/laptops, because they have neither ECC memory nor virtual machines. In particular, there seems to be a danger with Google's native client (NaCl) code execution. This a clever sandbox that allows the running of native code within the Chrome browser, so that web pages can run software as fast as native software on the system. This memory corruption defeats one level of protection in NaCl. Nobody has yet demonstrated how to use this technique in practice to fully defeat NaCl, but it's likely somebody will discover a way eventually. In the meanwhile, it's likely Google will update Chrome to defeat this, such as getting rid of the cache flush operation that forces memory overwrites.

The underlying issue is an analog one. It's not a bug in the code, or in the digital design of the chips, but a problem at a deeper layer. Rowhammer is not the first to exploit issues like this. For example, I own domains that are one bit different than Google's as a form of bit-squatting, with traffic arriving on my domain when a bit-flip causes a domain-name to change, such as when "google.com" becomes "foogle.com". Travis Goodspeed's packet-in-packet work show the flaw when bits (well, symbols) get flipped in radio waves.




Update: This is really just meant as a primer, as background on the issue, not really trying to derive any conclusions. I chatted a bit Chris Evans (@scarybeasts) from google about some of those conclusion, so I thought I'd expand a bit on them.

Does ECC protect you? Maybe not. While it will correct single bit flips most of the time, it won't protect when multiple bits flip at once. The hacker may be able to achieve this with enough tries. Remember: the hacker's code can keep retrying this until it succeeds, even if that takes hours. Since ECC is correcting the memory, nothing will crash. You won't see anything wrong except high CPU usage -- until the hacker eventually gets multiple bit-flips, and either the system crashes or the hacker gets successful exploitation. I forget the exact details. I think Intel CPUs correct single bit errors, crash on two bit errors, and that three bit errors might go through. Also, this would depend upon the percentage of time that the hacker can successfully get two/three bit flips instead of a single one.

By itself, this bug may not endanger you. However, it's much more dangerous when used within conjunction with other bugs. Browsers have "sand boxes" that keep hackers contained even if the first layer of defense breaks. This may provide a way of escaping the sand box (sandbox escape) when used in conjunction with other exploits.

Cache eviction is pretty predictable and may be exploitable from JavaScript even without access to the cache-flush instruction. Intel has a 32-kilobyte L1 cache for data. This is divided into 64 sets, each holding 8 items in a set, with each item being a 64 byte cache-line (64 times 8 times 64 equals 32k). Using JavaScript, one could easily create an array of bytes just long enough to force accessing 9 items in a set -- thus forcing the least-recently-used chunk to be flushed out to memory. Well, it gets tricky, because the L1 cache lines get bumped down to L2 cache, which get bumped down to L3, so code would have to navigate the entire cache hierarchy, which changes per processor. But it's probably doable, meaning that a JavaScript program may be able to cause havoc with the system.

I misread the paper. It says that Chrome's NaCl already removed the cache-flush operation a while ago, so Chrome is "safe". However, I wonder about that whether that cache eviction strategy might work.



4 comments:

Unknown said...

ECC isn't a panacea, as it can only correct a single bit error, and rowhammer can in some cases affect many bits in a single row.

Unknown said...

Not have the CLFLUSH doesn't make things impossible. Keep in mind the set-associative nature of the caches. We can find certain memory access patterns where the cache is exhausted in as little as 8 line references. On an 8-core HT socket, that could be exploited by having each socket accessing an exact by-way address and completely disable the cache features, effectively doing a constant CLFLUSH without the need for bus-sync that a CLFLUSH introduces.

Michael Sporer said...

Row hammer is not random, nor single bit upset, so ECC does not handle it. That's why it can be exploited and why this is a big deal. Row hammer was well understood in the 1980's because DRAM were susceptible to it back then. It has nothing to do with process geometry, it is quite simple that they cut the corner too close on the bitcell/array design. In the '80s the CPU had direct access to the DRAM (no cache), but as caches were introduced the statistical likelihood of row hammer went away. In a normal system it is not an issue, but if you bypass the cache, or deliberately write code that can hammer rows you are going to have problems if it is a crappy DRAM design.

Unknown said...

Ditto to the above comments. ECC WILL NOT SAVE YOU! It is single bit detection/correction and double bit detection....that's it! In fact I was told that multi bit errors can look like single bit correction giving the user a false sense of security. We make a tool that actually sits silently in the DIMM socket and counts the ACT commands thus we can tell if an application is susceptible to 'hammering' a memory. See us at www.DDRDetective.com