Flush and Reload

This is the second post in series of timing analysis. If you haven't read the first post - Timing Analysis (link opens a new tab), I highly recommend reading it to understand why these attacks are possible. If you have an idea of inclusive cache hierarchy and how OS loads shared library into virtual memory, you can continue with reading this article.

In this post, we will look at Flush and Reload

An illustration depicting flush and reload attack using timing diagram

 Alt: An illustration depicting flush and reload attack using timing diagram
Made with https://excalidraw.com/ (link opens a new tab)

 

Cache Placement

Cache can be designed in few different ways. Cache has to store address and the data at that address. We have to map an address to a particular cache line and depending on design, there is a tradeoff between data retention in case of conflict and time to access. The following are the popular mapping (taught at an undergraduate level) for mapping addresses to cache line:

  • Direct Mapping (1:1 associative) - Each address can be uniquely mapped to a particular cache line. For example, assume a system with 4 cache line that stores one byte each, (address % 4) gives the cache line to load data into.
  • Set Associative (1:m associative) - Each address can be mapped to m cache lines - This is known as a cache set. Modifying above example consider a cache set with 2 lines, the data at address will get loaded into (address % 2) cache set.
  • Fully associative - Here any address can be stored in any cache lines. The circuit used to resolved the correct cache line for a given address is more complicated than the other two.

 To read more about cache placement policies, you can read the Wikipedia article titled Cache Placement Policy (link opens a new tab).

The main takeaway here is, with most popular design, the cache set for a data can be determined from the address. In case a new data is to be brought in to a set that is occupied, data needs to be evicted to make room for the new data. To know more about cache replacement, you can read the Wikipedia article titled Cache Replacement Policy (link opens a new tab).

The diagram below depicts cache eviction in case of conflict for direct associative cache.

Data at address 400 is resolved to cahce line 0 
Alt: Address 400 is resolved to cache line 0
Data at address 400 is loaded in cache line 0 
Alt: Data at address 400 is loaded into cache line 0

Data at address 480 is resolved to cahce line 0 
Alt: Address 480 is resolved to cache line 0

Data at address 480 is loaded in cache line 0 overwriting data at address 400 
Alt: Data at address 480 is loaded into cache line 0 overwriting previous data
Data at address 400 is resolved to cahce line 0 
Alt: Address 400 is resolved to cache line 0
Data at address 400 is loaded in cache line 0 overwriting data at address 480 
Alt: Data at address 400 is loaded into cache line 0 overwriting previous data

Cache thrashing in case of directly mapped cache here consecutive loads are resolved to same cache line thus over writing one another and degrading performance
Made with https://excalidraw.com/ (link opens a new tab)


CLFLUSH

clflush is an x86 instruction that is used to flush a cache line corresponding to specific address through the entire cache hierarchy. If you are interested to learn more about clflush instruction, you can visit https://www.felixcloutier.com/x86/clflush (link opens a new tab).

The important point with clflush is that it can be used at any privilege level and hence ever a program running in userspace with basic execution privilege can still run the clflush instruction. This allows for attacker to exploit clflush without escalating privilege level.


Flush and Reload

In flush and reload, the attacker thread flushes a particular cache line or a cache set where the shared library will be loaded. As we know the address beforehand, we only have to observe a small part of cache which makes this an efficient technique.

Once flushed, the attacker waits for a small amount of time before loading the shared library themself. If the call resolves quicker than expected, we realize the routine is cached in the last level cache shared between the hardware threads. As the attacker had flushed this cache line previously, they can now determine that the victim thread has called the shared library routine.

Based on this timing analysis, the attacker thread can track events on the victim thread.

Alt: An image that illustrates how the timing changes with cached and un-cached data exaggerated for emphasis.
The picture is made using https://excalidraw.com/ (link will open a new tab)


Leaking secrets

To leak secrets, the victim thread must have a gadget that calls a shared library based on a secret. Consider the following code snippet:


unsigned int secret;

while (secret)

{

        if (secret & 1)

        {

                shared_library_routine();

        }

        secret = secret >> 1;

}


Based on timing analysis, the attacker thread can detect if shared_library_routine() is called by the victim and we know that this call happens only if the least significant bit of shifting secret is 1 and the attacker can decipher the entire secret just based on timing analysis.


Complications

Flush and reload have the following complications associated with it:

  • The attacker and victim should run on the same physical core on separate threads at the same time.
  • The attacker and victim should share the last level cache. Without shared cache, this type of attack will not work.
  • The micro-architecture must implement a form of clflush instruction to facilitate flush and reload.
  • The timing between the flush and reload is important. If the timing is not right, the attacker might misinterpret the secret.

 

Scenarios with Flush and Reload

The following images depicts the optimal flush and reload scenario:

The attacker runs the flush, the victim runs the shared routine, the attacker then loads the same routine to find that it is cached based on timing and interprets a part of secret. 
Alt: The attacker runs the flush, the victim runs the shared routine, the attacker then loads the same routine to find that it is cached based on timing and interprets a part of secret.

The attacker runs the flush, the victim doesn't the shared routine, the attacker then loads the same routine to find that it is not cached based on timing and interprets a part of secret. 
Alt: The attacker runs the flush, the victim doesn't the shared routine, the attacker then loads the same routine to find that it is not cached based on timing and interprets a part of secret.

The following are scenarios where attacker didn't time the flush and reload correctly:

The attacker runs the flush, the victim runs the shared routine twice by the time the attacker loads the same routine to find that it is cached based on timing. In doing so attacker misses a part of the leak. 
Alt: The attacker runs the flush, the victim runs the shared routine twice by the time the attacker loads the same routine to find that it is cached based on timing. In doing so attacker misses a part of the leak.

The attacker runs the flush, the victim runs the shared routine but the attacker's load of the same routine is too quick and overlaps with the load of the victim. In doing so attacker misses interprets a part of the leak as the time taken is closer to that of a cache miss.
Alt: The attacker runs the flush, the victim runs the shared routine but the attacker's load of the same routine is too quick and overlaps with the load of the victim. In doing so attacker misses interprets a part of the leak as the time taken is closer to that of a cache miss.
 
All images are made using https://excalidraw.com/ (link will open a new tab)
 
 

Coming up next

In the next post we'll look at Prime and Probe - a an alternative to Flush are Reload technique that works on systems that don't implement a variant of clflush instruction.


Thank you for reading till the end. I'm an undergraduate student keenly interested in Computer Architecture and I look at micro-architectural based attacks to understand more about the working of our hardware. If you find any inaccuracies in the above post, please leave a comment and I'll address it in the next edit. Have a nice day!

Comments

Post a Comment

Popular posts from this blog

Prime and Probe

Image
This is the third post in our series of Timing Analysis and I high recommend reading the first two posts - Timing Analysis (link opens a new tab), and Flush and Reload (link opens a new tab). That said if you are aware about cache hierarchy, shared libraries, shared pages, and cache placement policies, you can continue reading this article. In this post we look at Prime and Probe . Alt: An illustration of prime and probe Made with https://excalidraw.com/ (link opens a new tab) Cache Replacement Strategies The placement of data in cache is discussed briefly in Flush and Reload post. Here we will take a look at how data is replaced in cache. There are many different strategies to evict data from cache when a new data is needed to be stored in a filled cache set. Some of them are (some more practical than others): First In First Out (FIFO) - The logic behind the First In First Out is that the data that came first is probably the one that won't be used again for long time and henc
Read more

Row Hammer: Flipping Bits in Memory Without Accessing Them

Image
 This post we'll take a look at Row Hammer, a read disturbance phenomenon observed in commodity DRAM, first unearthed in the paper: Y. Kim et al., "Flipping bits in memory without accessing them: An experimental study of DRAM disturbance errors," 2014 ACM/IEEE 41st International Symposium on Computer Architecture (ISCA '14) (Link opens a new tab with PDF ~ 828KB) IEEE Page (link opens a new tab): https://ieeexplore.ieee.org/document/6853210 In this post I'll only betaking a brief look at the issue and I highly encourage you all to read the paper to find more insights and nitty gritty details of this vulnerability.   Alt: An illustration of Row Hammer showing how an activate of one row can influence the data stored in the adjacent row. The picture is made using https://excalidraw.com/ (link will open a new tab)   Structure of DRAM To fully understand the vulnerability, we must first take a look at the how modern DRAM are structured. All digital data can be represe
Read more

Speculative Execution

Image
 Most of the recent CPU vulnerability discovered depend on the property of modern processors known as Speculative Execution. In this post, we'll take a deeper look at where and why modern processors speculate. Alt: A illustration that shows speculative execution and how the results are committed or discarded based on result of speculation - whether it was correct or not respectively. The picture is made using https://excalidraw.com/ (link will open a new tab) Pipelined Execution Most modern processors are pipelined and are often superscalar in nature running instructions out of order, with multiple stages of execution of instruction running concurrently. Alt: Pipeline of a supersalar processor with 2 instruction fetch every clock cycle and a 5 stage pipeline. Source (link opens a new tab): https://en.wikipedia.org/wiki/Superscalar_processor In case of a long latency cache miss, permission check for an access or conditional branches, the processor generally has to stall waiting for
Read more