\HeadingLevelB{Cache Timing Attacks}
\label{sec:cache_timing}

Cache timing attacks~\citep{banescu2011cache} are a powerful class of software attacks that can be mounted entirely by an unprivileged attacker
(ring 3, \S~\ref{sec:rings}).
Cache timing attacks do not reveal information by directly reading the victim's memory, but by indirectly observing the victim's memory access pattern via their use of the system's caches.
These attacks therefore sidestep address translation-based isolation measures (\S~\ref{sec:paging}) implemented in modern kernels and hypervisors.


\HeadingLevelC{Theory}

Cache timing attacks exploit the unfortunate dependency between the part of a computer's memory subsystem hosting the freshest copy of a chunk of memory, and the latency of the corresponding access. A cache miss requires at the minimum a lookup in the core's L1 cache, and accesses to subsequent caches in the memory hierarchy if the address is not present in the L1. If the cache is full and dirty eviction must occur, further latency is incurred due to a write-back of evicted data.
On the Intel architecture, the latency between a cache hit and a miss can be easily resolved via the \texttt{RDTSC} and \texttt{RDTSCP} instructions (\S~\ref{sec:address_spaces}), which expose a high-frequency cycle counter.
These instructions have been designed for benchmarking and optimizing software, and provide a high-resolution measure of time to unprivileged (ring 3) software.

The fundamental tool of a cache timing attack is the attacker's facility to measure the latency of their own memory accesses, as affected by the victim's use of the cache.
A large multitude of addresses compete for any given cache set, giving the attacker ample room to arrange this interference, and observe the victim's use of the contested cache sets by monitoring the latency of the attacker's memory operations.
The memory locations are chosen so that they map to the same cache lines as those of some interesting memory locations in a victim process, in a cache that is shared between the attacker and the victim.
This family of attacks (as exemplified in Figure~\ref{fig:cache_timing_attack}) generally requires the attacker to know cache sizes, organization, and eviction behavior (\S~\ref{sec:cache_org}), all of which are readily available.

\begin{figure}[htpb]
  \centering
  \includegraphics[width=75mm]{figures/cache_timing_attack.pdf}
  \caption{
    A cache timing attack via shared cache sets corresponding to disjoint physical addresses.
    The attacker measures the availability of their own cache sets to indirectly observe the victim's use of specific cache sets and therefore the victim's memory access pattern.
  }
  \label{fig:cache_timing_attack}
\end{figure}

Armed with this knowledge, the attacker process begins with a series of operations that forces evictions on all cache sets corresponding to an address of interest in the victim's memory.
The exact mechanism varies by attack.
A straightforward eviction via dedicated instructions is available to the attacker on shared pages (such as shared library code, or pages de-duplicated by system software for efficiency).
The attacker can also exploit their knowledge of the cache eviction behavior by performing a series of memory accesses on their own virtual address space in a way that fills all cache sets competing with the victim's address of interest, causing these to be evicted.

This forces the victim's cache lines out of the cache and into DRAM (or lower levels of the cache hierarchy).
When the victim process is scheduled and executes, any accesses to the monitored addresses must bring the corresponding lines back into the cache.

The attacker periodically repeats their forced eviction of the victim's lines, and measures the victim's use of the cache since last eviction.
This is accomplished in one of several ways, again depending on the attack.
In case of shared physical pages, the attacker is able to measure the latency of a direct read to the address of interest.
A high latency indicates the victim has not accessed the address of interest, while a low latency indicates the line was re-introduced into the cache by the victim's execution.
In other cases, the attacker must infer the victim's use of the cache by monitoring the latency of accesses to the attacker's own competing cache sets.
By monitoring the time needed to re-fill all relevant cache sets with the attacker's lines, they can and detect evictions caused by the victim's execution.
In some cases, the attacker can further resolve victim stores from loads, as evictions of dirty cache lines are slower than clean ones.

Over time, the attacker collects evidence of the victim's execution and learns partial information of the victim's memory access pattern.
If the victim processes sensitive information using data-dependent control flow or data access pattern, the attacker may be able to infer this information from the observed memory access pattern.


\HeadingLevelC{Practical Considerations}

Cache timing attacks require control over a software process that shares cache sets with the victim process in any of the system's cache hierarchy.
A cache timing attack that targets the L2 cache relies on the system software to co-locate the attacker thread with the victim thread on the same physical core, whereas an attack on the L3 (last level) cache can be performed by any logical processor on the same CPU.
The latter attack relies on the fact that the L3 cache is inclusive, which greatly simplifies the processor's cache coherence implementation (\S~\ref{sec:cache_coherence}).

The cache sharing requirement implies that L3 cache attacks are feasible in an
IaaS environment, whereas L1 and L2 cache attacks are a significant concern when untrusted software runs at any privilege level alongside a sensitive process managed by the same operating system.

Out-of-order execution (\S~\ref{sec:out_of_order}) can introduce noise in cache timing attacks.
First, memory accesses may not be performed in program order, which can impact the lines selected by the cache eviction algorithms.
Second, out-of-order execution may result in cache fills that do not correspond to executed instructions.
For example, a load that follows a faulting instruction may be scheduled and executed before the fault is detected.

Cache timing attacks must account for speculative execution, as mispredicted memory accesses may cause cache fills, causing the
attacker to observe cache fills that do not correspond to instructions executed by the victim software.
Memory prefetching adds further noise in form of cache fills that are informed by but are not the result of instructions in the victim code.


\HeadingLevelC{Known Cache Timing Attacks}

Despite these difficulties, cache timing attacks are known to retrieve cryptographic keys used by numerous cryptosystems, including at the time of this writing AES~\citep{osvik2006aes, bonneau2006aes},
RSA~\citep{brumley2005rsa}, Diffie-Hellman~\citep{kocher1996timing}, and elliptic-curve cryptography~\citep{brumley2011ecc}.

Early attacks required access to the victim's CPU core, but more sophisticated recent attacks~\citep{yarom2013llctiming, liu2015llctiming} are able to use the
L3 (last-level) cache, which is shared by all cores on a CPU die.
L3-based attacks can be particularly devastating in cloud computing scenarios, where running software on the same computer as a victim application only requires modest statistical analysis and a small payment~\citep{ristenpart2009colocation}.
Another recently demonstrated class of cache timing attacks uses JavaScript code loaded as part of a web page visited by a Web browser~\citep{oren2015jstiming}, meaning these attacks are extremely easy to deploy.

Given this pattern of vulnerabilities, ignoring cache timing attacks is dangerously similar to ignoring the string of demonstrated attacks which led to the deprecation of SHA-1~\citep{nist2014sha1policy, google2014sha1deprecation, microsoft2014sha1deprecation}.


\HeadingLevelC{Defending against Cache Timing Attacks}
\label{sec:cache_timing_workarounds}

Fortunately, invalidating any of the preconditions for cache timing attacks is sufficient for defending against them.
The easiest precondition to focus on is that the attacker must have access to memory locations that map to the same sets in a cache as the victim's memory.
This assumption can be invalidated by the judicious use of a cache partitioning scheme.

Performance concerns aside, the main difficulty associated with cache partitioning schemes is that they must be implemented by a trusted party.
When the system software is trusted, it can (for example) use the principles behind page coloring~\citep{taylor1990coloring, kessler1992coloring} to partition the caches~\citep{lin2008coloring} between mutually distrusting parties.
This comes down to setting up the page tables in such a way that no two mutually distrusting software modules are stored in physical pages that map to the same sets in any cache.
 However, if the system software cannot be trusted, the cache partitioning scheme must be implemented by hardware.

The other interesting precondition is that the victim must access its memory in a data-dependent fashion that allows the attacker to infer private information from the observed memory access pattern.
It becomes tempting to think that cache timing attacks can be prevented by eliminating data-dependent memory accesses from all code handling sensitive data.

However, removing data-dependent memory accesses is difficult to accomplish in practice because instruction fetches must also be taken into consideration.
\citep{kasper2009aes} gives an idea of the level of effort required to remove data-dependent accesses from AES, which is a relatively simple data processing algorithm.
At the time of this writing, we are not aware of any approach that scales to large pieces of software.

While the focus of this section is on cache timing attacks, we must emphasize that that any sharing of resources among mutually distrusting entities may leak private information via the availability of the shared resource over time.
One worrying example is hyper-threading (\S~\ref{sec:cpu_core}), where each CPU core implements two logical processors, and the threads executing on these two logical processors share execution units.
An attacker able to run a process on a logical processor co-located on a core with a victim process can use \texttt{RDTSCP}~\citep{petters1999making} to learn which execution units are in use, and infer information about the instructions executed by the victim process.
