Using information theory to measure information flow.

David Clark

abstract:

Recently there has been an upsurge of interest in developing
quantitative approaches to information flow, usually in the context of
providing language-based security. One approach to this, building on
older work by Denning, McLean and Gray, is to view a program simply as a
transformer of inputs. Any probability distribution on the program
inputs is then transformed into one on outputs. In joint work with
Sebastian Hunt and Pasquale Malacaria we have developed a program
analysis which conservatively finds bounds on information leakage into
individual variables at the end of the program/transformation.

We have demonstrated how this can work in the context of rewriting and
have developed a syntax based analysis for a simple imperative language.
The analysis makes assumptions about the size of the secret, the
abilities of the attacker, the semantics of the program and the
relationship between the secret and non-secret inputs. In return it
provides guaranteed bounds on the amount of the secret that is leaked
into a given variable as a result of program execution and a clear
relationship between the quantitative measure and traditional concepts
of program security.

The program analysis itself is not a fixed thing but something that has
incrementally improved over time. We present the current state of this
analysis, its weaknesses and its strengths. We conclude with current
research directions in this area.