Why does this cache attack work?

Question

I was recently reading the following paper about doing a cache attack in Javascript:

https://arxiv.org/pdf/1502.07373v2.pdf

But I was confused by how it could work. In the paper, an 8 MB buffer was enough to have a high success rate for finding an eviction set (for a 12-way cache). I'm not exactly sure how this is possible.

I worked out the numbers for my own computer, and it doesn't seem like it would work (3MB cache, 12-way):

• The eviction buffer can be 4 MB instead of 8 MB
• This is what the buffer index would store:
  • Bits 0 - 6: byte within cache line
  • Bits 6 - 12: first 6 bits of set index
  • Bits after 12: not useful, since this can be mapped to any physical address
• There are 1024 pages in eviction buffer
• Out of these 1024 pages, there need to be 12 that map to a physical page that shares the same value for bits 12 - 18 as the victim address. I'm not good with probability, but this seems pretty unreliable

Why does it work?

I tried it on my own computer, and it seems to be able to evict the victim address 70% of the time (though even if I don't don't run any eviction stuff at all, the victim address still seems to get a miss rate of around 20%).

Answer 1

Assuming the operating system allocates pages completely randomly, my best calculation says that there's about a 11% chance that any given victim address will have at least 12 matching pages in your 4MB buffer. That's not very likely, and certainly doesn't agree with the 70% success rate you saw.

However, there are good reasons for an operating system to avoid mapping pages randomly, and instead to try its best to map contiguous pages. One reason for this is that the OS sometimes needs to allocate large contiguous buffers (to support huge pages or large DMA buffers, for example), and random allocation of physical pages would make it really hard to find a large enough region. This is known as memory fragmentation.

But in the context of this discussion, a more interesting benefit of contiguous allocation is (ironically enough) the level-3 cache performance. If you're running an algorithm that uses a large memory buffer, the way to get the best performance is to allocate contiguous physical memory, so that the individual pages don't evict each other from the cache. If the OS succeeds in maximizing performance this way, then it will also succeed in maximizing the attack's effectiveness: your 4MB buffer will cover the entire cache, and you'll have a 100% chance of evicting a victim page. So your observed 70% success rate is less a measure of chance, and more a rough measure of how effective the OS is at allocating pages for good cache performance.

---

If you want to see an example of an OS working this way in practice, read about Linux's buddy allocator. It starts by breaking memory into a set of large free blocks. Then, if it wants to allocate a page, it takes one of those large blocks and splits it in half. It then takes one of the halves and splits it in half again, and continues until it's got a pair of 1-page-sized block -- at which point it's also got one 2-page-sized block, one 4-sized, one 8-sized, etc. The first two allocations will be those two 1-page blocks, which are right next to each other because they are the result of breaking a 2-page block in half. The third allocation will break the other 2-page block in half, which again will be next to the other two for the same reasons.

So whenever it needs a new page, the allocator takes the smallest block it can find and breaks it down until it's got a single page. Finally, when a page is freed, the allocator checks to see if there is a free page right next to it, so it can form those two pages back into a larger block. The net effect is to keep allocations roughly contiguous when possible.