Rational Inattention and a Causal Account of Program Security

Abstract

This thesis consists of two parts, representing two separate strands of research.The first part is concerned with the formal analysis of program security. We argue that security properties of computer systems can be thought of causally, and use a formal model of causality, the Halpern-Pearl (HP) model, to represent programs and capture a variety of security properties such as noninterference, robust declassification and endorsement. This provides new insights into both causality, where security-inspired scenarios put the existing theory to the test and motivate us to consider various extensions, and security, where causality lets us express security properties in intuitive terms and see what they denote in natural settings. In the second part, we introduce a theoretical model of information acquisition under resource limitations in a noisy environment. An agent must guess the truth value of a given Boolean formula φ after performing a bounded number of noisy tests of the truth values of variables in the formula. We observe that, in general, the problem of finding an optimal testingstrategy for $\phi$ is hard, but we suggest a useful heuristic. The techniques we use also give insight into two apparently unrelated, but well-studied problems: (1) rational inattention, that is, when it is rational to ignore pertinent information (the optimal strategy may involve hardly ever testing variables that are clearly relevant to φ), and (2) what makes a formula hard to learn/remember.