  Information leaks through side channels are a pervasive problem, even in
security-critical applications. Functional side channels arise when an attacker
knows that a secret value of a server stays fixed for a certain time. Then, the
attacker can observe the server executions on a sequence of different public
inputs, each paired with the same secret input. Thus for each secret, the
attacker observes a function from public inputs to execution time, for
instance, and she can compare these functions for different secrets. First, we
introduce a notion of noninterference for functional side channels. We focus on
the case of noisy observations, where we demonstrate with examples that there
is a practical functional side channel in programs that would be deemed
information-leak-free or be underestimated using the standard definition.
Second, we develop a framework and techniques for debugging programs for
functional side channels. We extend evolutionary fuzzing techniques to generate
inputs that exploit functional dependencies of response times on public inputs.
We adapt existing results and algorithms in functional data analysis to model
the functions and discover the existence of side channels. We use a functional
extension of standard decision tree learning to pinpoint the code fragments
causing a side channel if there is one. We empirically evaluate the performance
of our tool FUCHSIA on a series of micro-benchmarks and realistic Java
programs. On the set of benchmarks, we show that FUCHSIA outperforms the
state-of-the-art techniques in detecting side channel classes. On the realistic
programs, we show the scalability of FUCHSIA in analyzing functional side
channels in Java programs with thousands of methods. Also, we show the
usefulness of FUCHSIA in finding side channels including a zero-day
vulnerability in OpenJDK and another vulnerability in Jetty that was since
fixed by the developers.
