Quantitative Mitigation of Timing Side Channels
  Timing side channels pose a significant threat to the security and privacy of
software applications. We propose an approach for mitigating this problem by
decreasing the strength of the side channels as measured by entropy-based
objectives, such as min-guess entropy. Our goal is to minimize the information
leaks while guaranteeing a user-specified maximal acceptable performance
overhead. We dub the decision version of this problem Shannon mitigation, and
consider two variants, deterministic and stochastic. First, we show the
deterministic variant is NP-hard. However, we give a polynomial algorithm that
finds an optimal solution from a restricted set. Second, for the stochastic
variant, we develop an algorithm that uses optimization techniques specific to
the entropy-based objective used. For instance, for min-guess entropy, we used
mixed integer-linear programming. We apply the algorithm to a threat model
where the attacker gets to make functional observations, that is, where she
observes the running time of the program for the same secret value combined
with different public input values. Existing mitigation approaches do not give
confidentiality or performance guarantees for this threat model. We evaluate
our tool SCHMIT on a number of micro-benchmarks and real-world applications
with different entropy-based objectives. In contrast to the existing mitigation
approaches, we show that in the functional-observation threat model, SCHMIT is
scalable and able to maximize confidentiality under the performance overhead
bound.
