Mechanisms for measuring packet loss and identifying locations where packets were dropped are crucial for informing routing decisions on the Internet. However, if such mechanisms are to be relied upon, they must be designed to prevent Internet Service Providers (ISPs) from “gaming” measurements to their advantage (e.g. by hiding packet loss or by blaming packet loss on innocent ISPs). Here, we explore mechanisms for accurately detecting and localizing packet loss events on a data path in the Internet in the presence of both benign loss (normal congestion, link failure) and active adversaries (greedy ISPs trying to increase traffic through their networks, or malicious routers controlled by remote attackers).
We use present new results that can guide the placement of Internet measurement and security mechanisms in future networks, including (1) two new cryptographic protocols for fault detection, (2) a new protocol for fault localization, (3) new negative results that use techniques from cryptography and complexity theory to prove that any secure fault detection or localization protocol requires secret keys, cryptography and storage at every participating node.
Joint work with David Xiao, Boaz Barak, and Jennifer Rexford.
Gates 4B (opposite 490)