Wenchao Zhou
Arjun Narayan
Andreas Haeberlen
ABSTRACT
This paper introduces secure network provenance (SNP), a novel technique that enables networked systems to explain to their operators why they are in a certain state -- e.g., why a suspicious routing table entry is present on a certain router, or where a given cache entry originated. SNP provides network forensics capabilities by permitting operators to track down faulty or misbehaving nodes, and to assess the damage such nodes may have caused to the rest of the system. SNP is designed for adversarial settings and is robust to manipulation; its tamper-evident properties ensure that operators can detect when compromised nodes lie or falsely implicate correct nodes.
We also present the design of SNooPy, a general-purpose SNP system. To demonstrate that SNooPy is practical, we apply it to three example applications: the Quagga BGP daemon, a declarative implementation of Chord, and Hadoop MapReduce. Our results indicate that SNooPy can efficiently explain state in an adversarial setting, that it can be applied with minimal effort, and that its costs are low enough to be practical.
- G. Altekar and I. Stoica. ODR: Output-deterministic replay for multicore debugging. In Proc. ACM Symposium on Operating Systems Principles (SOSP), Oct. 2009. Google Scholar
Digital Library
- P. Barham, A. Donnelly, R. Isaacs, and R. Mortier. Using Magpie for request extraction and workload modelling. In Proc. USENIX Symposium on Operating System Design and Implementation (OSDI), Dec. 2004. Google ScholarDigital Library
- M. Basrai and P. M. Chen. Cooperative ReVirt: adapting message logging for intrusion analysis. Technical Report University of Michigan CSE-TR-504-04, Nov 2004.Google Scholar
- P. Buneman, S. Khanna, and W.-C. Tan. Why and where: A characterization of data provenance. In Proc. International Conference on Database Theory (ICDT), Jan. 2001. Google ScholarDigital Library
- S. Callahan, J. Freire, E. Santos, C. Scheidegger, C. Silva, and H. Vo. VisTrails: Visualization meets data management. In Proc. ACM SIGMOD Conference, June 2006. Google ScholarDigital Library
- M. Castro and B. Liskov. Practical Byzantine fault tolerance and proactive recovery. ACM Transactions on Computer Systems (TOCS), 20(4):398--461, 2002. Google ScholarDigital Library
- B.-G. Chun, P. Maniatis, S. Shenker, and J. Kubiatowicz. Attested append-only memory: Making adversaries stick to their word. In Proc. ACM Symposium on Operating Systems Principles (SOSP), Oct. 2007. Google ScholarDigital Library
- Y. Fu, J. Chase, B. Chun, S. Schwab, and A. Vahdat. SHARP: An architecture for secure resource peering. In Proc. ACM Symposium on Operating Systems Principles (SOSP), Oct. 2003. Google ScholarDigital Library
- D. Geels, G. Altekar, P. Maniatis, T. Roscoe, and I. Stoica. Friday: Global comprehension for distributed replay. In Proc. USENIX Symp. on Networked Systems Design and Implementation (NSDI), Apr. 2007. Google ScholarDigital Library
- T. J. Green, G. Karvounarakis, Z. G. Ives, and V. Tannen. Update exchange with mappings and provenance. In Proc. International Conference on Very Large Data Bases (VLDB), Sept. 2007. Google ScholarDigital Library
- T. G. Griffin, F. B. Shepherd, and G. Wilfong. The stable paths problem and interdomain routing. IEEE/ACM Transactions on Networking (ToN), 10(2):232--243, Apr. 2002. Google ScholarDigital Library
- Hadoop. http://hadoop.apache.org/.Google Scholar
- A. Haeberlen, P. Aditya, R. Rodrigues, and P. Druschel. Accountable virtual machines. In Proc. USENIX Symposium on Operating System Design and Implementation (OSDI), Oct. 2010. Google ScholarDigital Library
- A. Haeberlen, I. Avramopoulos, J. Rexford, and P. Druschel. NetReview: Detecting when interdomain routing goes wrong. In Proc. USENIX Symposium on Networked Systems Design and Implementation (NSDI), Apr. 2009. Google ScholarDigital Library
- A. Haeberlen and P. Kuznetsov. The Fault Detection Problem. In Proc. Intl. Conference on Principles of Distributed Systems (OPODIS), Dec. 2009. Google ScholarDigital Library
- A. Haeberlen, P. Kuznetsov, and P. Druschel. The case for Byzantine fault detection. In Proc. Workshop on Hot Topics in System Dependability (HotDep), Nov. 2006. Google ScholarDigital Library
- A. Haeberlen, P. Kuznetsov, and P. Druschel. PeerReview: Practical accountability for distributed systems. In Proc. ACM Symposium on Operating Systems Principles (SOSP), Oct. 2007. Google ScholarDigital Library
- R. Hasan, R. Sion, and M. Winslett. Preventing history forgery with secure provenance. ACM Transactions on Storage (TOS), 5(4):1AB@--43, 2009. Google ScholarDigital Library
- R. Ikeda, H. Park, and J. Widom. Provenance for generalized map and reduce workflows. In Proc. Conference on Innovative Data Systems Research (CIDR), Jan. 2011.Google Scholar
- B. Kauer. OSLO: Improving the security of Trusted Computing. In Proc. 16th USENIX Security Symposium, Aug 2007. Google ScholarDigital Library
- S. T. King and P. M. Chen. Backtracking intrusions. ACM Transactions on Computer Systems (TOCS), 23(1):51--76, 2005. Google ScholarDigital Library
- S. T. King, Z. M. Mao, D. Lucchetti, and P. Chen. Enriching intrusion alerts through multi-host causality. In Proc. Annual Network and Distributed Systems Security Symposium (NDSS), Feb. 2005.Google Scholar
- R. Kotla, L. A. M. Dahlin, A. Clement, and E. Wong. Zyzzyva: Speculative Byzantine fault tolerance. ACM Trans. on Comp. Syst. (TOCS), 27(4), Dec. 2009. Google ScholarDigital Library
- L. Lamport, R. Shostak, and M. Pease. The Byzantine generals problem. ACM Trans. on Prog. Lang. and Systems (TOPLAS), 4(3):382--401, 1982. Google ScholarDigital Library
- X. Liu, Z. Guo, X. Wang, F. Chen, X. Lian, J. Tang, M. Wu, M. F. Kaashoek, and Z. Zhang. D3S: debugging deployed distributed systems. In Proc. USENIX Symposium on Networked Systems Design and Implementation (NSDI), Apr. 2008. Google ScholarDigital Library
- B. T. Loo, T. Condie, M. Garofalakis, D. E. Gay, J. M. Hellerstein, P. Maniatis, R. Ramakrishnan, T. Roscoe, and I. Stoica. Declarative Networking. CACM, 2009. Google ScholarDigital Library
- P. McDaniel, K. Butler, S. McLaughlin, R. Sion, E. Zadok, and M. Winslett. Towards a Secure and Efficient System for End-to-End Provenance. In Proc. USENIX Workshop on the Theory and Practice of Provenance (TaPP), Feb. 2010. Google ScholarDigital Library
- A. Meliou, W. Gatterbauer, K. M. Moore, and D. Suciu. The complexity of causality and responsibility for query answers and non-answers. In Proc. International Conference on Very Large Data Bases (VLDB), Aug. 2011.Google Scholar
- K.-K. Muniswamy-Reddy, D. A. Holland, U. Braun, and M. Seltzer. Provenance-aware storage systems. In Proc. USENIX Annual Technical Conference, 2006. Google ScholarDigital Library
- J. Newsome and D. Song. Dynamic taint analysis for automatic detection, analysis, and signature generation of exploits on commodity software. In Proc. Annual Network and Distributed Systems Security Symposium (NDSS), Feb. 2005.Google Scholar
- T.-W. Ngan, D. Wallach, and P. Druschel. Enforcing fair sharing of peer-to-peer resources. In Proc. International Workshop on Peer-to-Peer Systems (IPTPS), Feb. 2003.Google ScholarCross Ref
- O. Nordstroem and C. Dovrolis. Beware of BGP attacks. ACM Comp. Comm. Rev. (CCR), Apr 2004. Google ScholarDigital Library
- A. J. Oliner and A. Aiken. A query language for understanding component interactions in production systems. In Proc. International Conference on Supercomputing (ICS), June 2010. Google ScholarDigital Library
- H. Pang and K.-L. Tan. Verifying Completeness of Relational Query Answers from Online Servers. ACM Transactions on Information and System Security (TISSEC), 11:5:1--5:50, May 2008. Google ScholarDigital Library
- Quagga Routing Suite. http://www.quagga.net/.Google Scholar
- A. Ramachandran, K. Bhandankar, M. Bin Tariq, and N. Feamster. Packets with provenance. Technical Report GT-CS-08-02, Georgia Tech, 2008.Google Scholar
- RapidNet. http://netdb.cis.upenn.edu/rapidnet/.Google Scholar
- P. Reynolds, C. Killian, J. L. Wiener, J. C. Mogul, M. A. Shah, and A. Vahdat. Pip: Detecting the unexpected in distributed systems. In Proc. USENIX Symposium on Networked Systems Design and Implementation (NSDI), May 2006. Google ScholarDigital Library
- RouteViews project. http://www.routeviews.org/.Google Scholar
- Secure BGP. http://www.ir.bbn.com/sbgp/.Google Scholar
- K. Shanmugasundaram, N. Memon, A. Savant, and H. Bronnimann. ForNet: A distributed forensics network. In Proc. Intl. Workshop on Mathematical Methods, Models and Architectures for Computer Networks Security (MMM-ACNS), Sept. 2003.Google ScholarCross Ref
- A. Singh, M. Castro, P. Druschel, and A. Rowstron. Defending against the Eclipse attack in overlay networks. In Proc. ACM SIGOPS European Workshop, Sept. 2004. Google ScholarDigital Library
- A. Singh, P. Maniatis, T. Roscoe, and P. Druschel. Using queries for distributed monitoring and forensics. In Proc. EuroSys Conference, Apr. 2006. Google ScholarDigital Library
- R. Teixeira and J. Rexford. A measurement framework for pin-pointing routing changes. In Proc. SIGCOMM Network Troubleshooting Workshop, Sep 2004. Google ScholarDigital Library
- Vistrails. http://www.vistrails.org/.Google Scholar
- The Stanford WebBase Project. http://diglib.stanford.edu/~testbed/doc2/WebBase/.Google Scholar
- J. Widom. Trio: A system for integrated management of data, accuracy, and lineage. In Proc. Conference on Innovative Data Systems Research (CIDR), Jan. 2005.Google Scholar
- Y. Xie, V. Sekar, M. Reiter, and H. Zhang. Forensic analysis for epidemic attacks in federated networks. In Proc. IEEE International Conference on Network Protocols (ICNP), Nov. 2006. Google ScholarDigital Library
- W. Zhou, L. Ding, A. Haeberlen, Z. Ives, and B. T. Loo. TAP: Time-aware provenance for distributed systems. In Proc. USENIX Workshop on the Theory and Practice of Provenance (TaPP), June 2011.Google Scholar
- W. Zhou, Q. Fei, A. Narayan, A. Haeberlen, B. T. Loo, and M. Sherr. Secure network provenance. Technical Report MS-CIS-11-14, University of Pennsylvania, 2011. Available at http://snp.cis.upenn.edu/.Google ScholarDigital Library
- W. Zhou, M. Sherr, T. Tao, X. Li, B. T. Loo, and Y. Mao. Efficient querying and maintenance of network provenance at Internet-scale. In Proc. ACM SIGMOD Conference, June 2010. Google ScholarDigital Library
Index Terms
- Secure network provenance
Recommendations
PeerReview: practical accountability for distributed systems
SOSP '07: Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principlesWe describe PeerReview, a system that provides accountability in distributed systems. PeerReview ensures that Byzantine faults whose effects are observed by a correct node are eventually detected and irrefutably linked to a faulty node. At the same time,...
PeerReview: practical accountability for distributed systems
SOSP '07We describe PeerReview, a system that provides accountability in distributed systems. PeerReview ensures that Byzantine faults whose effects are observed by a correct node are eventually detected and irrefutably linked to a faulty node. At the same time,...
Securing Structured Overlays against Identity Attacks
Structured overlay networks can greatly simplify data storage and management for a variety of distributed applications. Despite their attractive features, these overlays remain vulnerable to the Identity attack, where malicious nodes assume control of ...
Comments