Skip to main content

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

Author(s): Goldberg, Sharon; Xiao, David; Tromer, Eran; Barak, Boaz; Rexford, Jennifer

To refer to this page use:
Abstract: 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.
Publication Date: 2014
Citation: Goldberg, Sharon, David Xiao, Eran Tromer, Boaz Barak, and Jennifer Rexford. "Path-quality monitoring in the presence of adversaries: The secure sketch protocols." IEEE/ACM Transactions on Networking 23, no. 6 (2014): 1729-1741. doi:10.1109/TNET.2014.2339853
DOI: 10.1109/TNET.2014.2339853
ISSN: 1063-6692
EISSN: 1558-2566
Pages: 1729 - 1741
Type of Material: Journal Article
Journal/Proceeding Title: IEEE/ACM Transactions on Networking
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.