Path-Quality Monitoring in the Presence of Adversaries: The Secure Sketch Protocols

Sharon Goldberg, David Xiao, Eran Tromer, Boaz Barak, Jennifer L. Rexford

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


Edge networks connected to the Internet need effective monitoring techniques to inform routing decisions and detect violations of Service Level Agreements (SLAs). However, existing measurement tools, like ping, traceroute, and trajectory sampling, are vulnerable to attacks that can make a path look better than it really is. Here, we design and analyze a lightweight path-quality monitoring protocol that reliably raises an alarm when the packet-loss rate exceed a threshold, even when an adversary tries to bias monitoring results by selectively delaying, dropping, modifying, injecting, or preferentially treating packets. Our protocol is based on sublinear algorithms for sketching the second moment of stream of items and can monitor billions of packets using only 250-600 B of storage and the periodic transmission of a comparably sized IP packet. We also show how this protocol can be used to construct a more sophisticated protocol that allows the sender to localize the link responsible for the dropped packets. We prove that our protocols satisfy a precise definition of security, analyze their performance using numerical experiments, and derive analytic expressions for the tradeoff between statistical accuracy and system overhead. This paper contains a deeper treatment of results from earlier conference papers and several new results.

Original languageEnglish (US)
Article number6868307
Pages (from-to)1729-1741
Number of pages13
JournalIEEE/ACM Transactions on Networking
Issue number6
StatePublished - Dec 2015

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


  • Network measurement
  • next-generation networking
  • security


Dive into the research topics of 'Path-Quality Monitoring in the Presence of Adversaries: The Secure Sketch Protocols'. Together they form a unique fingerprint.

Cite this