More Web Proxy on the site http://driver.im/

research-article

Secure network provenance

Authors:

Andreas Haeberlen,

Micah SherrAuthors Info & Claims

SOSP '11: Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles

Pages 295 - 310

https://doi.org/10.1145/2043556.2043584

Published: 23 October 2011 Publication History

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.

References

[1]

G. Altekar and I. Stoica. ODR: Output-deterministic replay for multicore debugging. In Proc. ACM Symposium on Operating Systems Principles (SOSP), Oct. 2009.

Digital Library

[2]

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.

Digital Library

[3]

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.

[4]

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.

Digital Library

[5]

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.

Digital Library

[6]

M. Castro and B. Liskov. Practical Byzantine fault tolerance and proactive recovery. ACM Transactions on Computer Systems (TOCS), 20(4):398--461, 2002.

Digital Library

[7]

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.

Digital Library

[8]

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.

Digital Library

[9]

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.

Digital Library

[10]

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.

Digital Library

[11]

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.

Digital Library

[12]

Hadoop. http://hadoop.apache.org/.

[13]

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.

Digital Library

[14]

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.

Digital Library

[15]

A. Haeberlen and P. Kuznetsov. The Fault Detection Problem. In Proc. Intl. Conference on Principles of Distributed Systems (OPODIS), Dec. 2009.

Digital Library

[16]

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.

Digital Library

[17]

A. Haeberlen, P. Kuznetsov, and P. Druschel. PeerReview: Practical accountability for distributed systems. In Proc. ACM Symposium on Operating Systems Principles (SOSP), Oct. 2007.

Digital Library

[18]

R. Hasan, R. Sion, and M. Winslett. Preventing history forgery with secure provenance. ACM Transactions on Storage (TOS), 5(4):1AB@--43, 2009.

Digital Library

[19]

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.

[20]

B. Kauer. OSLO: Improving the security of Trusted Computing. In Proc. 16th USENIX Security Symposium, Aug 2007.

Digital Library

[21]

S. T. King and P. M. Chen. Backtracking intrusions. ACM Transactions on Computer Systems (TOCS), 23(1):51--76, 2005.

Digital Library

[22]

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.

[23]

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.

Digital Library

[24]

L. Lamport, R. Shostak, and M. Pease. The Byzantine generals problem. ACM Trans. on Prog. Lang. and Systems (TOPLAS), 4(3):382--401, 1982.

Digital Library

[25]

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.

Digital Library

[26]

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.

Digital Library

[27]

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.

Digital Library

[28]

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.

[29]

K.-K. Muniswamy-Reddy, D. A. Holland, U. Braun, and M. Seltzer. Provenance-aware storage systems. In Proc. USENIX Annual Technical Conference, 2006.

Digital Library

[30]

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.

[31]

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.

[32]

O. Nordstroem and C. Dovrolis. Beware of BGP attacks. ACM Comp. Comm. Rev. (CCR), Apr 2004.

Digital Library

[33]

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.

Digital Library

[34]

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.

Digital Library

[35]

Quagga Routing Suite. http://www.quagga.net/.

[36]

A. Ramachandran, K. Bhandankar, M. Bin Tariq, and N. Feamster. Packets with provenance. Technical Report GT-CS-08-02, Georgia Tech, 2008.

[37]

RapidNet. http://netdb.cis.upenn.edu/rapidnet/.

[38]

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.

Digital Library

[39]

RouteViews project. http://www.routeviews.org/.

[40]

Secure BGP. http://www.ir.bbn.com/sbgp/.

[41]

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.

[42]

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.

Digital Library

[43]

A. Singh, P. Maniatis, T. Roscoe, and P. Druschel. Using queries for distributed monitoring and forensics. In Proc. EuroSys Conference, Apr. 2006.

Digital Library

[44]

R. Teixeira and J. Rexford. A measurement framework for pin-pointing routing changes. In Proc. SIGCOMM Network Troubleshooting Workshop, Sep 2004.

Digital Library

[45]

Vistrails. http://www.vistrails.org/.

[46]

The Stanford WebBase Project. http://diglib.stanford.edu/~testbed/doc2/WebBase/.

[47]

J. Widom. Trio: A system for integrated management of data, accuracy, and lineage. In Proc. Conference on Innovative Data Systems Research (CIDR), Jan. 2005.

[48]

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.

Digital Library

[49]

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.

[50]

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/.

Digital Library

[51]

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.

Digital Library

Cited By

Andrade Pineda RDuque Prieto A(2024)Listeria monocytogenes y mecanismo de caballo de Troya a través de la barrera hematoencefálicaRevista Digital de Postgrado10.37910/RDP.2024.13.1.e38913:1Online publication date: 6-May-2024
https://doi.org/10.37910/RDP.2024.13.1.e389
Nazari AZhang YRaghothaman MChen H(2024)Localized Explanations for Automatically Synthesized Network ConfigurationsProceedings of the 23rd ACM Workshop on Hot Topics in Networks10.1145/3696348.3696888(52-59)Online publication date: 18-Nov-2024
https://dl.acm.org/doi/10.1145/3696348.3696888
Zhang CZeng JZhang YAhmad AZhang FJin HLiang ZLuo BLiao XXu JKirda ELie D(2024)The HitchHiker's Guide to High-Assurance System Observability Protection with Efficient Permission SwitchesProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690188(3898-3912)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690188
Show More Cited By

Index Terms

Secure network provenance

Recommendations

PeerReview: practical accountability for distributed systems
SOSP '07: Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles

We 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 '07

We 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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SOSP '11: Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles

October 2011

417 pages

ISBN:9781450309776

DOI:10.1145/2043556

General Chair:
Ted Wobber
MSR Silicon Valley
,
Program Chair:
Peter Druschel
MPI-SWS

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

INESC: Systems and Computer Engineering Institute
SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 October 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

SOSP '11

Sponsor:

INESC
SIGOPS

SOSP '11: ACM SIGOPS 23nd Symposium on Operating Systems Principles

October 23 - 26, 2011

Cascais, Portugal

Acceptance Rates

Overall Acceptance Rate 174 of 961 submissions, 18%

Upcoming Conference

SOSP '25

Sponsor:
sigops

ACM SIGOPS 31st Symposium on Operating Systems Principles

October 13 - 16, 2025

Seoul , Republic of Korea

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

117
Total Citations
View Citations
678
Total Downloads

Downloads (Last 12 months)42
Downloads (Last 6 weeks)6

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Andrade Pineda RDuque Prieto A(2024)Listeria monocytogenes y mecanismo de caballo de Troya a través de la barrera hematoencefálicaRevista Digital de Postgrado10.37910/RDP.2024.13.1.e38913:1Online publication date: 6-May-2024
https://doi.org/10.37910/RDP.2024.13.1.e389
Nazari AZhang YRaghothaman MChen H(2024)Localized Explanations for Automatically Synthesized Network ConfigurationsProceedings of the 23rd ACM Workshop on Hot Topics in Networks10.1145/3696348.3696888(52-59)Online publication date: 18-Nov-2024
https://dl.acm.org/doi/10.1145/3696348.3696888
Zhang CZeng JZhang YAhmad AZhang FJin HLiang ZLuo BLiao XXu JKirda ELie D(2024)The HitchHiker's Guide to High-Assurance System Observability Protection with Efficient Permission SwitchesProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690188(3898-3912)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690188
Pacherkar HYan GKim YKim JKoushanfar FRasmussen K(2024)PROV5GC: Hardening 5G Core Network Security with Attack Detection and Attribution Based on Provenance GraphsProceedings of the 17th ACM Conference on Security and Privacy in Wireless and Mobile Networks10.1145/3643833.3656129(254-264)Online publication date: 27-May-2024
https://dl.acm.org/doi/10.1145/3643833.3656129
Chen XLiu HHuang QZhang DZhou HWu CLiu XKhan M(2023)Stalker Attacks: Imperceptibly Dropping Sketch Measurement Accuracy on Programmable SwitchesIEEE Transactions on Information Forensics and Security10.1109/TIFS.2023.331512818(5832-5847)Online publication date: 2023
https://doi.org/10.1109/TIFS.2023.3315128
Wu YXie YLiao XZhou PFeng DWu LLi XWildani ALong D(2023)Paradise: Real-Time, Generalized, and Distributed Provenance-Based Intrusion DetectionIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2022.316087920:2(1624-1640)Online publication date: 1-Mar-2023
https://doi.org/10.1109/TDSC.2022.3160879
Falowo OKropczynski JLi C(2023)Protecting Critical Infrastructure: Strategies for Managing Cybersecurity Risks in Nuclear Fusion Facilities2023 IEEE Intl Conf on Parallel & Distributed Processing with Applications, Big Data & Cloud Computing, Sustainable Computing & Communications, Social Computing & Networking (ISPA/BDCloud/SocialCom/SustainCom)10.1109/ISPA-BDCloud-SocialCom-SustainCom59178.2023.00170(1050-1061)Online publication date: 21-Dec-2023
https://doi.org/10.1109/ISPA-BDCloud-SocialCom-SustainCom59178.2023.00170
Bilot TMadhoun NAgha KZouaoui A(2023)Graph Neural Networks for Intrusion Detection: A SurveyIEEE Access10.1109/ACCESS.2023.327578911(49114-49139)Online publication date: 2023
https://doi.org/10.1109/ACCESS.2023.3275789
Liu DShen XLiu DShen X(2023)Reliable Data Provenance in HCNBlockchain-Based Data Security in Heterogeneous Communications Networks10.1007/978-3-031-52477-6_3(57-90)Online publication date: 19-Dec-2023
https://doi.org/10.1007/978-3-031-52477-6_3
Liu DShen XLiu DShen X(2023)IntroductionBlockchain-Based Data Security in Heterogeneous Communications Networks10.1007/978-3-031-52477-6_1(1-22)Online publication date: 19-Dec-2023
https://doi.org/10.1007/978-3-031-52477-6_1
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents