Service Assurance in Insecure Networks with Byzantine Adversaries

Abstract

This dissertation describes research into security threats in new communication environ- ments and methods to counter them. More specifically, we consider networks where some nodes perform an important application function such as routing, filtering, aggregation, etc., and may become compromised while doing so. We consider three types of networks: Internet-scale publish/subscribe networks, ag- gregating sensor networks, and peer-to-peer massively multiplayer online games (MMOG) and virtual environments. These environments are complementary to each other in many respects. A publish/subscribe network is responsible for disseminating data objects pro- duced by one set of nodes (publishers) to another set of nodes (subscribers). Subscribers want to receive those and only those objects that satisfy their interests. A large-scale pub- lish/subscribe network using many network providers, each under its own administrative control, presents numerous opportunities for mischief. In many cases the network providers will not trust one another and will not be fully trusted by the end users. A malicious network provider may insert, delete, modify, reorder, misdirect, or delay messages, and re- main undetected. The first topic of our research is how to assure service integrity in such networks if some of the intermediate nodes may attack the system in an arbitrary fashion. We solve the problem by creating filtering agents corresponding to user subscriptions, and mapping these agents to either hosts from trusted providers or to clusters of hosts taken from multiple non-trusted providers. As a whole, each cluster can be trusted since only a relatively small number of providers are assumed to be malicious. A sensor network is a network connecting hundreds or thousands of sensors, tiny battery- powered computers equipped with units measuring some physical phenomena (e.g., light intensity, temperature, humidity, ambient chemical composition, etc.) and wireless ra- dio transceivers. We study aggregating sensor networks that do not fully propagate raw measurements to their users but rather perform in-network aggregation with the intent of lowering the total amount of transmitted data thus preserving bandwidth and energy. As sensor networks are frequently placed in hostile environments (for instance, in military applications) it is important to devise mechanisms guaranteeing integrity of their service under attack, and their survivability. In this dissertation we discuss CoDeX, a collect-detect- exclude framework for secure aggregation in sensor networks. Our approach to solving the problem is based on the fact that many physical phenomena exhibit strong spatial corre- lation. Sensor nodes can take advantage of the broadcast nature of radio transmissions, receive measurements from their neighbors, and compare them with their own results. If the values significantly differ, the fact can be reported to the user (the "collect" phase). If a node is a subject of many such reports, it is, probably, compromised (the "detect" phase) and should be removed from the network (the "exclude" phase). We complement this approach with the use of randomized delivery (aggregation) trees, cryptography, and repeated aggregation of the same data in different configurations Peer-to-peer massively multiplayer online games and virtual environments pose chal- lenges similar to those in the other two types of networks: all three lack centralized control and run autonomously. Like pub-sub networks, P2P-based MMOGs may span the Inter- net and contain thousands and, potentially, hunderds of thousands of nodes. Like sensor networks, these systems almost completely rely on end nodes for providing infrastructure services. Unfortunately, most games do not provide sufficient safeguards against cheating and fraud perpetrated by the players. We developed FRAPPE, an architecture that significantly reduces this vulnerability by forming trusted "supernodes" out of non-trusted peer machines, employing authentication, confidentiality and pseudonymity services, using secret sharing and other secure multiparty computation techniques, and constructing anonymizing tunnels to hide identities of communicating parties. We also introduce a useful primitive, called local broadcast with verification(LBV), used to solicit services of peers in a particular neighborhood and subsequently verify that the peers properly executed the protocol. Using a combination of analysis and experimental results we demonstrate that all three approaches provide strong service assurance guarantees for their respective types of net- works.