skip to main content
10.1145/3064176.3064212acmconferencesArticle/Chapter ViewAbstractPublication PageseurosysConference Proceedingsconference-collections
research-article
Public Access

One Primitive to Diagnose Them All: Architectural Support for Internet Diagnostics

Published: 23 April 2017 Publication History

Abstract

Today, network operators are increasingly playing the role of part-time detectives: they must routinely diagnose intricate problems and malfunctions, e.g., routing or performance issues, and they must often perform forensic investigations of past misbehavior, e.g., intrusions or cybercrimes. However, the current Internet architecture offers little direct support for them. A variety of solutions have been proposed, but each solution tends to address only one specific problem. Moreover, each solution proposes a different fix that is incompatible with the others, which complicates deployment.
In this paper, we make the observation that most of the existing solutions share a common "functional core", which suggests that it may be possible to add a single primitive to the Internet architecture that can support a wide variety of diagnostic and forensic tasks. We then present one specific candidate that we call secure packet provenance (SPP). We show that SPP is easy to add to the current architecture, that it can be implemented efficiently in both software and hardware, and that it can be used to approximate (and sometimes surpass) the capabilities offered by a variety of existing diagnostic and forensic systems.

References

[1]
NTT SLA. http://www.ntt.net/english/service/sla_ts.html.
[2]
Police face £750k bill for false Operation Ore charges. http://www.telegraph.co.uk/technology/news/8422200/Police-face-750k-bill-for-false-Operation-Ore-charges.html.
[3]
Sprint SLA. https://www.sprint.net/sla_performance.php.
[4]
Symantec says hackers tried extortion. http://bits.blogs.nytimes.com/2012/02/07/symantec-says-hackers-tried-extortion/.
[5]
Techie lands in jail due to Airtel, sues it. http://ibnlive.in.com/news/techie-lands-in-jail-due-to-airtelsues-it/101343-3.html.
[6]
M. Afanasyev, T. Kohno, J. Ma, N. Murphy, S. Savage, A. C. Snoeren, and G. M. Voelker. Privacy-preserving network forensics. Commun. ACM, 54(5):78--87, May 2011.
[7]
D. G. Andersen, H. Balakrishnan, N. Feamster, T. Koponen, D. Moon, and S. Shenker. Accountable Internet protocol (AIP). In Proc. SIGCOMM, 2008.
[8]
K. Argyraki, P. Maniatis, D. R. Cheriton, and S. Shenker. Providing packet obituaries. In Proc. HotNets, 2004.
[9]
K. Argyraki, P. Maniatis, O. Irzak, S. Ashish, and S. Shenker. Loss and delay accountability for the Internet. In Proc. ICNP, 2007.
[10]
K. Argyraki, P. Maniatis, and A. Singla. Verifiable networkperformance measurements. In Proc. CoNEXT, 2010.
[11]
B. Augustin, X. Cuvellier, B. Orgogozo, F. Viger, T. Friedman, M. Latapy, C. Magnien, and R. Teixeira. Avoiding traceroute anomalies with Paris traceroute. In Proc. IMC, 2006.
[12]
B. Baldwin, N. Hanley, M. Hamilton, L. Lu, A. Byrne, M. Neill, and W. P. Marnane. FPGA implementations of the round two SHA-3 candidates. In Proc. Second SHA-3 Candidate Conference, 2010.
[13]
M. Blott, J. Ellithorpe, N. McKeown, K. Visssers, and H. Zeng. FPGA research design platform fuels network advances. Xilinx Xcell Journal, 2010.
[14]
P. Buneman, S. Khanna, and W.-C. Tan. Why and where: A characterization of data provenance. In Proc. ICDT, 2001.
[15]
A. Chen, A. Haeberlen, W. Zhou, and B. T. Loo. One primitive to diagnose them all: Architectural support for Internet diagnostics. Technical Report MS-CIS-17-04, University of Pennsylvania, 2017.
[16]
A. Chen, Y. Wu, A. Haeberlen, W. Zhou, and B. T. Loo. The good, the bad, and the differences: Better network diagnostics with differential provenance. In Proc. SIGCOMM, 2016.
[17]
D. Clark. The design philosophy of the DARPA Internet protocols. ACM Computer Communication Review, 18(4):106--114, 1988.
[18]
M. Dischinger, M. Marcon, S. Guha, K. P. Gummadi, R. Mahajan, and S. Saroiu. Glasnost: Enabling end users to detect traffic differentiation. In Proc. NSDI, 2010.
[19]
N. G. Duffield and M. Grossglauser. Trajectory sampling for direct traffic observation. IEEE/ACM Trans. Netw., 9(13):280--292, 2001.
[20]
A. Feldmann, O. Maennel, Z. M. Mao, A. Berger, and B. Maggs. Locating Internet routing instabilities. In Proc. SIGCOMM, 2004.
[21]
K. Gaj, E. Homsirikamol, and M. Rogawski. Comprehensive comparison of hardware performance of fourteen round 2 SHA-3 candidates with 512-bit outputs using field programmable gate arrays. In Proc. Second SHA-3 Candidate Conference, 2010.
[22]
K. Gaj, E. Homsirikamol, M. Rogawski, R. Shahid, and M. U. Sharif. Comprehensive evaluation of high-speed and mediumspeed implementations of five SHA-3 finalists using Xilinx and Altera FPGAs. https://eprint.iacr.org/2012/368.pdf.
[23]
A. Greenberg, J. Hamilton, D. A. Maltz, and P. Patel. The cost of a cloud: Research problems in data center networks. ACM Computer Communication Review, 39(1):68--73, Dec. 2008.
[24]
A. Haeberlen, I. Avramopoulos, J. Rexford, and P. Druschel. NetReview: Detecting when interdomain routing goes wrong. In Proc. NSDI, 2009.
[25]
A. Haeberlen, M. Dischinger, K. P. Gummadi, and S. Saroiu. Monarch: A tool to emulate transport protocol flows over the Internet at large. In Proc. IMC, 2006.
[26]
A. Haeberlen, P. Fonseca, R. Rodrigues, and P. Druschel. Fighting cybercrime with packet attestation. Technical Report MPI-SWS-2011-002, Max Planck Institute for Software Systems, July 2011.
[27]
A. Haeberlen and P. Kuznetsov. The fault detection problem. In Proc. OPODIS, 2009.
[28]
A. Haeberlen, P. Kuznetsov, and P. Druschel. PeerReview: Practical accountability for distributed systems. In Proc. SOSP, 2007.
[29]
N. Handigol, B. Heller, V. Jeyakumar, D. Mazières, and N. McKeown. I know what your packet did last hop: Using packet histories to troubleshoot networks. In Proc. NSDI, 2014.
[30]
S. Hao, M. Thomas, V. Paxson, N. Feamster, C. Kreibich, C. Grier, and S. Hollenbeck. Understanding the domain registration behavior of spammers. In Proc. IMC, 2013.
[31]
R. Hasan, R. Sion, and M. Winslett. The case of the fake picasso: Preventing history forgery with secure provenance. In Proc. FAST, 2009.
[32]
X. Inc. Virtex-5 family overview. http://www.xilinx.com/support/documentation/data_sheets/ds100.pdf, Feb. 2009.
[33]
V. Jacobson. Traceroute. ftp://ftp.ee.lbl.gov/traceroute.tar.gz.
[34]
A. Juels and J. Brainard. Client puzzles: A cryptographic countermeasure against connection depletion attacks. In Proc. NDSS, 1999.
[35]
Juniper Networks. Packets per second. http://kb.juniper.net/InfoCenter/index?page=content&id=KB14737.
[36]
E. Katz-Bassett, H. V. Madhyastha, V. K. Adhikari, C. Scott, J. Sherry, P. Van Wesep, T. Anderson, and A. Krishnamurthy. Reverse traceroute. In Proc. NSDI, 2010.
[37]
E. Katz-Bassett, H. V. Madhyastha, J. P. John, A. Krishnamurthy, D. Wetherall, and T. Anderson. Studying black holes in the Internet with Hubble. In Proc. NSDI, 2008.
[38]
T. H.-J. Kim, C. Basescu, L. Jia, S. B. Lee, Y.-C. Hu, and A. Perrig. Lightweight source authentication and path validation. In Proc. SIGCOMM, 2014.
[39]
E. Kohler, R. Morris, B. Chen, J. Jannotti, and M. F. Kaashoek. The Click modular router. ACM Trans. on Computer Systems, 18(3):263--297, 2000.
[40]
M. Kotadia. Trojan horse found responsible for child porn. ZDNet, 8/1/2003.
[41]
R. Krishnan, H. V. Madhyastha, S. Srinivasan, S. Jain, A. Krishnamurthy, T. Anderson, and J. Gao. Moving beyond end-to-end path information to optimize CDN performance. In Proc. IMC, 2009.
[42]
M. Liberatore, B. N. Levine, and C. Shields. Strengthening forensic investigations of child pornography on P2P networks. In Proc. CoNEXT, 2010.
[43]
X. Liu, A. Li, X. Yang, and D. Wetherall. Passport: Secure and adoptable source authentication. In Proc. NSDI, 2008.
[44]
Z. Liu, A. Manousis, G. Vorsanger, V. Sekar, and V. Braverman. One sketch to rule them all: Rethinking network flow monitoring with UnivMon. In Proc. SIGCOMM, 2016.
[45]
R. Mahajan, N. Spring, D. Wetherall, and T. Anderson. Userlevel Internet path diagnosis. In Proc. SOSP, 2003.
[46]
R. Mahajan, M. Zhang, L. Poole, and V. Pai. Uncovering performance differences among backbone ISPs with Netdiff. In Proc. NSDI, 2008.
[47]
P. Maniatis and M. Baker. Secure history preservation through timeline entanglement. In Proc. USENIX Security, 2002.
[48]
S. Matsuo, M. Knezevic, P. Schaumont, I. Verbauwhede, A. Satoh, K. Sakiyama, and K. Ota. How can we conduct fair and consistent hardware evaluation for SHA-3 candidate? In Proc. Second SHA-3 Candidate Conference, 2010.
[49]
R. Merkle. Protocols for public key cryptosystems. In Proc. IEEE S&P, 1980.
[50]
H. E. Michail, L. Ioannou, and A. G. Voyiatzis. Pipelined SHA-3 implementations on FPGA: Architecture and performance analysis. In Proc. CS2, 2015.
[51]
A. Mizrak, S. Savage, and K. Marzullo. Detecting compromised routers via packet forwarding behavior. IEEE Network, 22(2):34--39, 2008.
[52]
J. Naous, D. Erickson, G. A. Covington, G. Appenzeller, and N. McKeown. Implementing an openflow switch on the NetFPGA platform. In Proc. ANCS, 2008.
[53]
J. Naous, M. Walfish, A. Nicolosi, D. Mazières, M. Miller, and A. Seehra. Verifying and enforcing network paths with ICING. In Proc. CoNEXT, 2011.
[54]
D. Naylor, M. K. Mukerjee, and P. Steenkiste. Balancing accountability and privacy in the network. In Proc. SIGCOMM, 2014.
[55]
M. Piatek, T. Kohno, and A. Krishnamurthy. Challenges and directions for monitoring P2P file sharing networks. In Proc. HotSec, 2008.
[56]
A. Ramachandran, K. Bhandankar, M. B. Tariq, and N. Feamster. Packets with provenance. In Proc. SIGCOMM Poster, 2008.
[57]
A. Ramachandran and N. Feamster. Understanding the network-level behavior of spammers. In Proc. SIGCOMM, 2006.
[58]
C. Reis, S. D. Gribble, T. Kohno, and N. C. Weaver. Detecting in-flight page changes with web tripwires. In Proc. NSDI, 2008.
[59]
S. Savage, D. Wetherall, A. Karlin, and T. Anderson. Practical network support for IP traceback. In Proc. SIGCOMM, 2000.
[60]
R. Sherwood, A. Bender, and N. Spring. DisCarte: A disjunctive Internet cartographer. In Proc. SIGCOMM, 2008.
[61]
R. Sinha, C. Papadopoulos, and J. Heidemann. Internet packet size distributions: Some observations. Technical Report ISITR-2007-643, USC ISI, 2007.
[62]
A. Snoeren, C. Partridge, L. Sanchez, C. Jones, F. Tchakountio, B. Schwartz, S. Kent, and W. Strayer. Single-packet IP traceback. IEEE/ACM Trans. Netw., 10(6):721--734, 2002.
[63]
M. Stevens, E. Bursztein, P. Karpman, A. Albertini, and Y.Markov. The first collision for full SHA-1. Cryptology ePrint Archive, Report 2017/190, 2017.
[64]
L. Subramanian, V. Roth, I. Stoica, S. Shenker, and R. H. Katz. Listen and Whisper: Security mechanisms for BGP. In Proc. NSDI, 2004.
[65]
R. Sylvester. IP address typo leads to a false arrest in Kansas. The Wichita Eagle, http://www.kansas.com/mld/eagle/news/local/crime_courts/12620843.htm.
[66]
R. Teixeira and J. Rexford. A measurement framework for pin-pointing routing changes. In Proc. NetT, 2004.
[67]
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.
[68]
M. Yu, L. Jose, and R. Miao. Software defined traffic measurement with OpenSketch. In Proc. NSDI, 2013.
[69]
X. Zhang, A. Jain, and A. Perrig. Packet-dropping adversary identification for data plane security. In CoNEXT, 2008.
[70]
Y. Zhang, Z. M. Mao, and M. Zhang. Detecting traffic differentiation in backbone ISPs with NetPolice. In Proc. IMC, 2009.
[71]
Z. Zhang, Y. Zhang, Y. C. Hu, Z. M. Mao, and R. Bush. iSPY: Detecting IP prefix hijacking on my own. IEEE/ACM Trans. Netw., 18(6):1815--1828, Dec. 2010.
[72]
W. Zhou, Q. Fei, A. Narayan, A. Haeberlen, B. T. Loo, and M. Sherr. Secure network provenance. In Proc. SOSP, 2011.
[73]
W. Zhou, Q. Fei, S. Sun, T. Tao, A. Haeberlen, Z. Ives, B. T. Loo, and M. Sherr. NetTrails: A declarative platform for provenance maintenance and querying in distributed systems. In Proc. SIGMOD Demo, 2011.
[74]
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, 2013.
[75]
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.
[76]
N. Zilberman, Y. Audzevich, G. A. Covington, and A. W. Moore. NetFPGA SUME: Toward 100 Gbps as research commodity. IEEE Micro, 34(5):32--41, 2014.

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
  • (2022)The case for an internet primitive for fault localizationProceedings of the 21st ACM Workshop on Hot Topics in Networks10.1145/3563766.3564105(160-166)Online publication date: 14-Nov-2022
  • (2022)LRVP: Lightweight Real-Time Verification of Intradomain Forwarding PathsIEEE Systems Journal10.1109/JSYST.2022.316582616:4(6309-6320)Online publication date: Dec-2022
  • Show More Cited By
  1. One Primitive to Diagnose Them All: Architectural Support for Internet Diagnostics

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    EuroSys '17: Proceedings of the Twelfth European Conference on Computer Systems
    April 2017
    648 pages
    ISBN:9781450349383
    DOI:10.1145/3064176
    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: 23 April 2017

    Permissions

    Request permissions for this article.

    Check for updates

    Qualifiers

    • Research-article
    • Research
    • Refereed limited

    Funding Sources

    Conference

    EuroSys '17
    Sponsor:
    EuroSys '17: Twelfth EuroSys Conference 2017
    April 23 - 26, 2017
    Belgrade, Serbia

    Acceptance Rates

    Overall Acceptance Rate 241 of 1,308 submissions, 18%

    Upcoming Conference

    EuroSys '25
    Twentieth European Conference on Computer Systems
    March 30 - April 3, 2025
    Rotterdam , Netherlands

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)55
    • Downloads (Last 6 weeks)20
    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
    • (2022)The case for an internet primitive for fault localizationProceedings of the 21st ACM Workshop on Hot Topics in Networks10.1145/3563766.3564105(160-166)Online publication date: 14-Nov-2022
    • (2022)LRVP: Lightweight Real-Time Verification of Intradomain Forwarding PathsIEEE Systems Journal10.1109/JSYST.2022.316582616:4(6309-6320)Online publication date: 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
    • (2020)Unveiling the Mystery of Internet Packet ForwardingACM Computing Surveys10.1145/340979653:5(1-34)Online publication date: 28-Sep-2020
    • (2020)Grasp the Root Causes in the Data PlaneProceedings of the Symposium on SDN Research10.1145/3373360.3380835(55-61)Online publication date: 3-Mar-2020
    • (2018)MaelstromProceedings of the 13th USENIX conference on Operating Systems Design and Implementation10.5555/3291168.3291196(373-389)Online publication date: 8-Oct-2018
    • (2018)Towards Fine-grained Network Security Forensics and Diagnosis in the SDN EraProceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security10.1145/3243734.3243749(3-16)Online publication date: 15-Oct-2018
    • (2017)PVad: Privacy-Preserving Verification for Secure Routing in Ad Hoc Networks2017 International Conference on Networking and Network Applications (NaNA)10.1109/NaNA.2017.21(5-10)Online publication date: Oct-2017

    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