Quantifying information flow

The main problem addressed by this thesis is that of characterising information leakage channels in interactive systems as either 'dangerous' or 'safe', on the basis of the amount of information that can be leaked. We define information information leakage in a fashion very similar to the classical definition of Goguen and Meseguer, modeling systems as finite state transducers. Interesting issues arise in the selection of the appropriate measure of information, and we propose some novel definitions which address the problems which have been identified with the traditional notion of mutual information. We show that for deterministic systems, the problem of quantifying information flow can be reduced to a natural combinatorial problem on regular languages, namely that of computing their 'width' with respect to the lexicographic partial order. We solve this problem, and show that there is a dichotomy between exponential and polynomial width, corresponding to linear and logarithmic information flow (which we characterise as 'dangerous' and 'safe' respectively). We give a polynomial time algorithm to distinguish the two cases, as well as to compute the precise rate of logarithmic information flow. We also study the analagous question for some other partially ordered structures: we show that for context-free languages there is a similar dichotomy but the problem of distinguishing the two cases is undecidable, and that for regular tree languages there is a trichotomy between doubly exponential, singly exponential and polynomial growth. Finally we consider information flow in the setting of the process algebra CSP. In order to reduce to the framework of languages and automata, we establish a general theorem showing that a wide class of finite observational models of CSP (including all known models) can be reduced to the traces model using the `priority' operator.