Quantitative Information Flow

Lead Research Organisation: King's College London
Department Name: Computer Science


Consider the idea of interference, the capacity of one part of a system to affect the behaviour of another part. Non-interference, i.e. absence of interference, is often used in proving that a software system is well-behaved, whereas interference can lead to obscure (mis-)behaviours. However misbehaviour in the presence of interference will generally happen only when there is enough interference. Think in terms of electric current: non-interference between X and Y is the absence of a circuit involving X and Y; interference is the existence of a circuit; this however doesn't imply that there is enough ``current'' in the circuit to adversely affect the behaviour of the system.In this work we will use Shannon's Information Theory to measure the amount of interference between X and Y by considering it as a flow of information. In previous work we have had considerable success in applying this approach to simple programming languages.We aim to widen the current scope of our methods of reasoning and analysis so that we can consider more sophisticated forms of information flow (such as flows caused by variation in timing behaviours), and reason about more complex systems that may be reactive, object oriented, or incorporate probabilistic aspects.We further aim to improve the quality of our analyses by calculating tighter bounds on the amount of information that flows.We have identified the following threads of investigation as being key to these aims: expressivity (extension of our work to a wider class of languages), time (extension to reasoning about time), and partial equivalence relations (using relations as a reasoning tool).A successful outcome of our proposed research in the above three threads will provide conceptual tools for quantitative analyses of information flow in a typed higher-order object-oriented multi-threaded language. Such research would be sufficient for the analysis of software applications like password protected systems and spyware.