n networks such as the IP-based networks that run the Internet, nodes trust one another to properly execute routing and forwarding. When a node is compromised (i.e. Byzantine failure), this trust can be exploited by such compromised nodes to launch routing attacks that can disrupt communication throughout the network. In addition, a compromised node can drop, delay, reorder, replay, or duplicate messages, or inject its own messages into the network to consume resources. While these attacks are examples related to networking, in fact, a compromised node can perform any arbitrary action. Therefore, addressing this vulnerability requires an attack-agnostic approach that maintains network functionality even in the presence of compromised nodes.
We introduce the first practical solution for intrusion-tolerant networking. Our approach guarantees well-defined semantics to applications, rather than solely routing packets, and allows multiple different semantics to coexist. Specifically, we define two semantics that fit the needs of many applications: one guarantees prioritized timely delivery, and the other guarantees reliable delivery. We introduce a Maximal Topology with Minimal Weights to prevent routing attacks, and provide generic support for source-based routing, limiting the power of the adversary. Specifically, we discuss two source-based routing techniques: K Node-Disjoint Paths, which is resilient to K-1 compromised nodes, and Constrained Flooding, which provides the optimal guarantee that it will deliver messages if there exists a correct path from source to destination. We also describe the resilient overlay architecture necessary for the deployment of these ideas and to make the solution holistic, allowing the resulting system to overcome benign faults as well as malicious and resource-consumption attacks in the underlying network. We present a formal specification of the guarantees and evaluate an implementation deployed on a global cloud spanning 12 data centers from East Asia to North America to Europe.
Daniel Obenshain is a final year PhD candidate in Computer Science at Johns Hopkins University, advised by Yair Amir, and is a Beauchamp Fellow. His research focuses on creating systems that are highly resilient, even to the point of tolerating intrusions, and applying theoretical analysis to give provable guarantees for those systems. He holds a Bachelor’s degree in Computer Science from the California Institute of Technology (Caltech). He will start at Facebook in January, working in their infrastructure team.