skip to main content
10.1145/2834050.2834111acmconferencesArticle/Chapter ViewAbstractPublication PagescommConference Proceedingsconference-collections
research-article
Free access

Differential Provenance: Better Network Diagnostics with Reference Events

Published: 16 November 2015 Publication History

Abstract

In this paper, we propose a new approach to diagnosing problems in complex networks. Our approach is based on the insight that many of the trickiest problems are anomalies -- they affect only a small fraction of the traffic (e.g., perhaps a certain subnet), or they only manifest infrequently. Thus, it is quite common for the network operator to have "examples" of both working and non-working traffic readily available -- perhaps a packet that was misrouted, and a similar packet that was routed correctly. In this case, the cause of the problem is likely to be wherever the two packets were treated differently by the network.
We sketch the design of a network debugger that can leverage this information using a novel concept that we call differential provenance. Like classical provenance, differential provenance tracks the causal connections between network and configuration states and the packets that were affected by them; however, it can additionally reason about the causes of any discrepancies between different provenances. We have performed a case study in the context of software-defined networks, and our initial results are encouraging: they suggest that differential provenance can often identify the root cause of even very subtle network issues.

Supplementary Material

MP4 File (a25.mp4)

References

[1]
RapidNet. http://netdb.cis.upenn.edu/rapidnet/.
[2]
P. Bille. A survey on tree edit distance and related problems. Theor. Comput. Sci., 337(1-3):217--239, June 2005.
[3]
P. Buneman, S. Khanna, and W.-C. Tan. Why and where: A characterization of data provenance. In Proc. ICDT, Jan. 2001.
[4]
M. Dietz, S. Shekhar, Y. Pisetsky, A. Shu, and D. S. Wallach. Quire: Lightweight provenance for smart phone operating systems. In Proc. USENIX Security, 2011.
[5]
R. Durairajan, J. Sommers, and P. Barford. Controller-agnostic SDN debugging. In Proc. CoNEXT, 2014.
[6]
A. Gehani and D. Tariq. SPADE: Support for provenance auditing in distributed environments. In Proc. Middleware, 2012.
[7]
T. G. Griffin, F. B. Shepherd, and G. Wilfong. The stable paths problem and interdomain routing. IEEE/ACM Trans. Netw., 10(2):232--243, Apr. 2002.
[8]
P. Kazemian, G. Varghese, and N. McKeown. Header space analysis: Static checking for networks. In Proc. NSDI, 2012.
[9]
T. Kim, R. Chandra, and N. Zeldovich. Efficient patch-based auditing for web application vulnerabilities. In Proc. OSDI, 2012.
[10]
B. T. Loo, T. Condie, M. Garofalakis, D. E. Gay, J. M. Hellerstein, P. Maniatis, R. Ramakrishnan, T. Roscoe, and I. Stoica. Declarative networking. Communications of the ACM, 52(11):87--95, Nov. 2009.
[11]
H. Mai, A. Khurshid, R. Agarwal, M. Caesar, P. B. Godfrey, and S. T. King. Debugging the data plane with Anteater. In Proc. SIGCOMM, 2012.
[12]
R. Merkle. Protocols for public key cryptosystems. In Proc. IEEE Symposium on Security and Privacy, 1980.
[13]
K.-K. Muniswamy-Reddy, U. Braun, D. A. Holland, P. Macko, D. Maclean, D. Margo, M. Seltzer, and R. Smogor. Layering in provenance systems. In Proc. USENIX Annual Technical Conference, 2009.
[14]
C. Scott, A. Wundsam, B. Raghavan, A. Panda, A. Or, J. Lai, E. Huang, Z. Liu, A. El-Hassany, S. Whitlock, H. Acharya, K. Zarifis, and S. Shenker. Troubleshooting blackbox SDN control software with minimal causal sequences. In Proc. SIGCOMM, 2014.
[15]
H. J. Wang, J. C. Platt, Y. Chen, R. Zhang, and Y.-M. Wang. Automatic misconfiguration troubleshooting with PeerPressure. In Proc. OSDI, 2004.
[16]
Y. Wu, M. Zhao, A. Haeberlen, W. Zhou, and B. T. Loo. Diagnosing missing events in distributed systems with negative provenance. In Proc. SIGCOMM, 2014.
[17]
A. Wundsam, D. Levin, S. Seetharaman, and A. Feldmann. OFRewind: Enabling record and replay troubleshooting for networks. In Proc. USENIX Annual Technical Conference, 2011.
[18]
H. Zeng, P. Kazemian, G. Varghese, and N. McKeown. Automatic test packet generation. In Proc. CoNEXT, 2012.
[19]
W. Zhou, Q. Fei, A. Narayan, A. Haeberlen, B. T. Loo, and M. Sherr. Secure network provenance. In Proc. SOSP, Oct. 2011.
[20]
W. Zhou, S. Mapara, Y. Ren, Y. Li, A. Haeberlen, Z. Ives, B. T. Loo, and M. Sherr. Distributed time-aware provenance. In Proc. VLDB, Aug. 2013.
[21]
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. SIGMOD, 2010.

Cited By

View all
  • (2023)PUMMProceedings of the 32nd USENIX Conference on Security Symposium10.5555/3620237.3620284(823-840)Online publication date: 9-Aug-2023
  • (2023)Graph Neural Networks for Intrusion Detection: A SurveyIEEE Access10.1109/ACCESS.2023.327578911(49114-49139)Online publication date: 2023
  • (2022)FAuST: Striking a Bargain between Forensic Auditing’s Security and ThroughputProceedings of the 38th Annual Computer Security Applications Conference10.1145/3564625.3567990(813-826)Online publication date: 5-Dec-2022
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
HotNets-XIV: Proceedings of the 14th ACM Workshop on Hot Topics in Networks
November 2015
189 pages
ISBN:9781450340472
DOI:10.1145/2834050
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 the author(s) 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 November 2015

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Debugging
  2. Diagnostics
  3. Provenance

Qualifiers

  • Research-article
  • Research
  • Refereed limited

Funding Sources

Conference

HotNets-XIV
Sponsor:
HotNets-XIV: The 14th ACM Workshop on Hot Topics in Networks
November 16 - 17, 2015
PA, Philadelphia, USA

Acceptance Rates

Overall Acceptance Rate 110 of 460 submissions, 24%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)109
  • Downloads (Last 6 weeks)12
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2023)PUMMProceedings of the 32nd USENIX Conference on Security Symposium10.5555/3620237.3620284(823-840)Online publication date: 9-Aug-2023
  • (2023)Graph Neural Networks for Intrusion Detection: A SurveyIEEE Access10.1109/ACCESS.2023.327578911(49114-49139)Online publication date: 2023
  • (2022)FAuST: Striking a Bargain between Forensic Auditing’s Security and ThroughputProceedings of the 38th Annual Computer Security Applications Conference10.1145/3564625.3567990(813-826)Online publication date: 5-Dec-2022
  • (2021)Validating the Integrity of Audit Logs Against Execution Repartitioning AttacksProceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security10.1145/3460120.3484551(3337-3351)Online publication date: 12-Nov-2021
  • (2021)PROV-GEM: Automated Provenance Analysis Framework using Graph Embeddings2021 20th IEEE International Conference on Machine Learning and Applications (ICMLA)10.1109/ICMLA52953.2021.00273(1720-1727)Online publication date: Dec-2021
  • (2020)Provenance for Intent-Based Networking2020 6th IEEE Conference on Network Softwarization (NetSoft)10.1109/NetSoft48620.2020.9165519(195-199)Online publication date: Jun-2020
  • (2018)Cross-model convolutional neural network for multiple modality data representationNeural Computing and Applications10.1007/s00521-016-2824-430:8(2343-2353)Online publication date: 1-Oct-2018
  • (2018)CompoSAT: Specification-Guided Coverage for Model FindingFormal Methods10.1007/978-3-319-95582-7_34(568-587)Online publication date: 12-Jul-2018
  • (2017)The power of "why" and "why not": enriching scenario exploration with provenanceProceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering10.1145/3106237.3106272(106-116)Online publication date: 21-Aug-2017
  • (2016)The Good, the Bad, and the DifferencesProceedings of the 2016 ACM SIGCOMM Conference10.1145/2934872.2934910(115-128)Online publication date: 22-Aug-2016

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media