TY - JOUR
T1 - Path-Quality Monitoring in the Presence of Adversaries
T2 - The Secure Sketch Protocols
AU - Goldberg, Sharon
AU - Xiao, David
AU - Tromer, Eran
AU - Barak, Boaz
AU - Rexford, Jennifer L.
N1 - Funding Information:
The work of S. Goldberg was supported by the NSF under Grant CNS-0627526. The work of S. Goldberg and J. Rexford was supported by HSARPA Grant 1756303. The work of D. Xiao was supported by an NDSEG Graduate Fellowship and an NSF Graduate Research Fellowship. The work of E. Tromer was supported by a Rothschild Fellowship. The work of B. Barak was supported by the NSF under Grants CNS-0627526 and CCF-0426582, US-Israel BSF Grant 2004288, and Packard and Sloan fellowships.
Publisher Copyright:
© 2015 IEEE.
PY - 2015/12
Y1 - 2015/12
N2 - 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.
AB - 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.
KW - Network measurement
KW - next-generation networking
KW - security
UR - http://www.scopus.com/inward/record.url?scp=84961908108&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84961908108&partnerID=8YFLogxK
U2 - 10.1109/TNET.2014.2339853
DO - 10.1109/TNET.2014.2339853
M3 - Article
AN - SCOPUS:84961908108
SN - 1063-6692
VL - 23
SP - 1729
EP - 1741
JO - IEEE/ACM Transactions on Networking
JF - IEEE/ACM Transactions on Networking
IS - 6
M1 - 6868307
ER -