Abstract

Robbert Van Renesse: Making Self-Organizing Systems Secure

Network overlays provide important routing functionality not supported directly by the Internet. Such functionality includes multicast routing, content-based routing, and resilient routing, as well as combinations thereof. As network overlays are starting to be deployed for critical applications such as Internet telephony (e.g., Skype), web casting/distance education, web conferencing (e.g., NetMeeting), and even DNS replacements (CoDons), efficiency and security are becoming important attributes. For example, a web cast of a political conference may be an attractive target. Alas, most current network overlays are built from Distributed Hash Tables and spanning trees, resulting in infrastructures that are easily compromised. But traditional protocols based on Byzantine agreement do not scale to the sizes required.

We are exploring the use of randomized protocols for network overlays. Such protocols are often highly tolerant of benign failures such as crashes and message loss. We modify these protocols in non-trivial ways in order to make them tolerant of intrusions. In particular, we use epidemic protocols to build a pseudo-random mesh of participants, and use controlled flooding for disseminating information efficiently and reliably in the face of compromised participants. Note that we do not attempt to detect (Intrusion Detection, Reputation) or prevent intrusions (Access Control). Doing so would lead to an arms race that may not be productive. Instead, we only tolerate intrusions. Unlike Byzantine protocols, our protocols degrade gracefully as a larger percentage of participants is compromised.