Interaction-aware Actual Causation: A Building Block for Accountability in Security Protocols (CMU-CyLab-16-002)
Protocols involving multiple agents and their interactions are ubiquitous. Protocols for tasks such as authentication, electronic voting, and secure multi-party computation ensure desirable security properties if participating agents followtheir prescribed programs. However, if some agents choose to deviate from their prescribed programs and a security property is violated, it is important to hold agents accountable, i.e. assign blame for their choices and actions, and to fix deficiencies in the protocol design. Prior work in accountability has focused primarily on detecting or punishing deviations. This dissertation proposes a novel interaction-aware approach to actual causation (i.e., the identification of particular agents’ choices to deviate, and interactions which caused a specific violation). We propose this approach as a useful building block for accountability in interacting multi-agent systems, including but not limited to security protocols.
The definitions of actual cause in this dissertation are inspired by prior work on actual causation in philosophy, law, and computer science. However, prior frameworks do not account for the program dynamics that arise in protocol-based settings and do not naturally capture agent interactions and agents’ choices to deviate. Motivated by these applications and challenges, we make two main contributions. First, we propose a theory of actual causation with choice and interaction as key components. Specifically,we define in an interacting program model, what it means for a sequence of program expressions (modeling choices, actions and interactions) to be an actual cause of a violation. We demonstrate that our theory significantly advances the state-of-the-art in the research area of actual causation by combining process-oriented and counterfactual-based viewpoints in prior work. A careful treatment of interaction and choice enables us to cleanly deal with a known set of issues that plague extant theories, including expressing concise interaction models and over-permissive counterfactual-based definitions. Second, we demonstrate the value of this theory in the domain of security and privacy protocols, by proving that violations of a specific class of safety properties always have an actual cause. We also present a sound technique for establishing program actions as actual causes. Additionally, we provide a causal analysis of a representative protocol, designed to address weaknesses in the current public key certification infrastructure. Our theory clearly distinguishes between deviances and actual causes which is important from the standpoint of accountability.