Probabilistic Point-to-Point Information Leakage

Tom Chothia

The outputs of a program that processes secret data may reveal information about the values of these secrets. We present an information leakage model that measures the leakage between specific points in a probabilistic program. To make our model precise, we base it on a simple probabilistic imperative language in which the values of variables may arbitrarily be marked as secret or observable by an attacker, and give semantics to the language that correspond to our leakage model. We then extend our model to address both non-terminating programs (with potentially infinite numbers of secret and observable values) and user input. Finally, we show how statistical approximation techniques can be used to estimate our leakage measures in real-world Java programs using our "LeakWatch" tool.

Joint work with Chris Novakovic, Yusuke Kawamoto and Dave Parker.