Department of Computer Science & Engineering

Network routers occupy a unique role in modern distributed systems. They are responsible for cooperatively shuttling packets amongst themselves in order to provide the illusion of a network with universal point-to-point connectivity. However, this illusion is shattered -- as are implicit assumptions of availability, confidentiality or integrity -- when network routers act in a malicious fashion. By manipulating, diverting or dropping packets arriving at a compromised router, an attacker can trivially mount denial-of-service, surveillance or man-in-the-middle attacks on end host systems. Consequently, Internet routers have become a choice target for would-be attackers and thousands have been subverted to these ends. In this paper, we specify this problem of detecting routers with incorrect packet forwarding behavior and we explore the design space of protocols that implement such a detector. We further present two concrete protocols that differ in accuracy, completeness, and overhead -- one of which is likely inexpensive enough for practical implementation at scale. We believe our work is an important step in being able to tolerate attacks on key network infrastructure components.

Pre-2018 CSE ID: CS2004-0789