Provenance for Forensics in Distributed Systems

Distributed systems have rapidly evolved, from simple client/server applications in local area networks, to Internet-scale peer-to-peer networks and large-scale cloud platforms deployed on thousands of nodes across multiple administrative domains and geographical areas. Despite of the growing popularity and interests, designing and deploying distributed systems remain challenging, due to their ever-increasing scales and the complexity and unpredictability of the system executions.

Operators of distributed systems often find themselves needing to answer forensic questions, to perform a variety of managerial tasks including fault detection, system debugging, accountability enforcement, and attack analysis. We present NetTrails, a novel provenance-based 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 at a given time in a potentially adversarial environment.

The NetTrails project makes several contributions, including distributed provenance maintenance and querying, secure provenance support in dynamic and adversarial environments, and a visualization toolkit that allows users to explore and understand provenance in an interactive manner.

Code Release

An initial prototype of NetTrails has been developed using the RapidNet declarative networking system. This release includes support for Network Provenance [NetDB08, SIGMOD10].


NetTrails makes the following contributions:

Distributed Provenance Maintenance and Querying

We present ExSPAN, a scalable framework for achieving network provenance [NetDB08, SIGMOD10] in a distributed environment. ExSPAN utilizes declarative networking techniques and rewrite rules to efficiently affix provenance information to tuples communicated between nodes. ExSPAN significantly reduces communication overhead by distributing provenance information among nodes, and appending only short provenance pointers to tuples to identify the nodes that maintain the relevant provenance information. Provenance queries are evaluated by performing recursive traversal of the provenance graph in a distributed fashion. We show that several optimization techniques are available for further reduce the overhead of provenance querying.

Provenance in Dynamic Environments

To enable consistent and complete provenance query results in highly-dynamic networks, we propose the Time-aware provenance (TAP) [TaPP11] model, which contains an additional temporal dimension that enables time-travelling in the provenance graph. In addition, the enhanced model explicitly supports provenance of state changes by attributing each state change to a previously occurred change and the existences of other states at that time. Aware of the large maintenance overhead introduced by the additional temporal dimension, we explore alternative replay-based provenance maintenance techniques with different performance tradeoffs, and further discuss their applicability in workload with different characteristics.

Secure Provenance in Adversarial Environments

Getting correct answers to provenance queries is difficult in an adversarial setting because compromised nodes can fabricate plausible (but incorrect) responses to conceal their misbehavior. We propose a secure network provenance model (SNP) [NSDI11 Poster, SOSP11] that is made possible by adopting the tamper-evident logs and replay-based auditing in a complete untrusted environment where an unknown subset of nodes is controlled by a Byzantine adversary. Our results show that SNP can be easily applied to diverse network protocols and systems. Our SNP implementation, incurs low processing, bandwidth, and latency overheads, while enabling tamper-evident provenance queries for any system state when applied to interdomain routing (BGP), the Chord DHT, and MapReduce executions in Hadoop.

Interactive Exploration Toolkit

We develop a visualization toolkit [SIGMOD11 Demo] that allows interactive exploration of system state and the corresponding provenance graph. We plan to further enhance the toolkit by adding the support for the TAP and SNP enhancements that enable the toolkit to be applied to a wider range of applications and scenarios.

Pair-wise Minimal Cost (MinCost) Protocol




  • Qiong Fei, Amazon
  • Tao Tao, Microsoft
  • Xiaozhou Li, Princeton University


  • Distributed Time-aware Provenance. [Paper]
    Wenchao Zhou, Suyog Mapara, Yiqing Ren, Yang Li, Andreas Haeberlen, Zachary Ives, Boon Thau Loo, and Micah Sherr.
    39th International Conference on Very Large Databases (VLDB), Aug 2013.
  • Secure Network Provenance. [Paper]
    Wenchao Zhou, Qiong Fei, Arjun Narayan, Andreas Haeberlen, Boon Thau Loo, and Micah Sherr.
    23rd ACM Symposium on Operating Systems Principles (SOSP ’11), Cascais, Portugal, Oct 2011.
  • TAP: Time-aware Provenance for Distributed Systems. [Paper]
    Wenchao Zhou, Ling Ding, Andreas Haeberlen, Zachary Ives, and Boon Thau Loo.
    In the 3rd USENIX Workshop on the Theory and Practice of Provenance (TaPP), Heraklion, Greece, Jun, 2011.
  • NetTrails: A Declarative Platform for Provenance Maintenance and Querying in Distributed Systems. [Paper]
    Wenchao Zhou, Qiong Fei, Shengzhi Sun, Tao Tao, Andreas Haeberlen, Zachary Ives, Boon Thau Loo, and Micah Sherr
    In the 30th ACM SIGMOD International Conference on Management of Data (SIGMOD) – Demo, Athens, Greece, Jun 2011.
  • Secure Forensics without Trusted Components [Paper]
    Wenchao Zhou, Qiong Fei, Arjun Narayan, Andreas Haeberlen, Boon Thau Loo, and Micah Sherr.
    In the 8th USENIX Symposium on Networked Systems Design and Implementation (NSDI) – Poster, Boston, MA, Mar, 2011
  • Towards a Data-centric View of Cloud Security. [Paper]
    Wenchao Zhou, Micah Sherr, William R. Marczak, Zhuoyao Zhang, Tao Tao, Boon Thau Loo, and Insup Lee.
    In the 2nd International Workshop on Cloud Data Management (CloudDB), in conjunction with CIKM, Toronto, Canada, Oct 2010.
  • Efficient Querying and Maintenance of Network Provenance at Internet-Scale. [Paper] [Talk]
    Wenchao Zhou, Micah Sherr, Tao Tao, Xiaozhou Li, Boon Thau Loo, and Yun Mao.
    In the 29th ACM SIGMOD International Conference on Management of Data (SIGMOD), Indianapolis, IN, June 2010.
  • Provenance-aware Secure Networks [Paper] [Talk]
    Wenchao Zhou, Eric Cronin, and Boon Thau Loo.
    In the 4th International Workshop on Networking meets Databases (NetDB), in conjunction with ICDE, Cancun, Mexico, Apr 2008.


This work is partially supported by NSF Grants IIS-0812270, CCF-0820208, CNS-0845552, CNS-1040672, CNS-1054229, CNS-1065130, and OSD/AFOSR MURI Collaborative Policies and Assured Information Sharing.