Operators of distributed systems often find themselves needing to answer forensic questions, in order to perform a variety of managerial tasks including fault detection, system debugging, accountability enforcement, and attack analysis. In this talk, we will introduce Secure Network Provenance (SNP), an approach that provides the fundamental functionality required for answering such forensic questions -- the capability to "explain'' the existence (or change) of a certain distributed system state in a potentially adversarial environment. 

 

We model provenance maintenance and querying as recursive queries over distributed relations, and propose security extensions to allow operators to reliably query provenance information in adversarial environments. The extensions guarantee that operators can eventually detect the presence of compromised nodes that lie or falsely implicate correct nodes. Finally, we discuss our work in the context of our longer term vision towards provably secure distributed systems.