  Cache-based side channels enable a dedicated attacker to reveal program
secrets by measuring the cache access patterns. Practical attacks have been
shown against real-world crypto algorithm implementations such as RSA, AES, and
ElGamal. By far, identifying information leaks due to cache-based side
channels, either in a static or dynamic manner, remains a challenge: the
existing approaches fail to offer high precision, full coverage, and good
scalability simultaneously, thus impeding their practical use in real-world
scenarios.
  In this paper, we propose a novel static analysis method on binaries to
detect cache-based side channels. We use abstract interpretation to reason on
program states with respect to abstract values at each program point. To make
such abstract interpretation scalable to real-world cryptosystems while
offering high precision and full coverage, we propose a novel abstract domain
called the Secret-Augmented Symbolic domain (SAS). SAS tracks program secrets
and dependencies on them for precision, while it tracks only coarse-grained
public information for scalability.
  We have implemented the proposed technique into a practical tool named CacheS
and evaluated it on the implementations of widely-used cryptographic algorithms
in real-world crypto libraries, including Libgcrypt, OpenSSL, and mbedTLS.
CacheS successfully confirmed a total of 154 information leaks reported by
previous research and 54 leaks that were previously unknown. We have reported
our findings to the developers. And they confirmed that many of those unknown
information leaks do lead to potential side channels.
