Research Abstracts - 2007

Overview

Ad hoc networks of wireless devices hold significant promise for the future of ubiquitous computing. Unfortunately, such networks are particularly vulnerable to adversarial interference due to their use of a shared, public communication medium and their deployment in unprotected environments. For example, a committed adversary can disrupt an ad hoc network by jamming the communication channel with noise. Continuous jamming, however, might be unwise for the adversary: it depletes the adversary's energy, allows the honest devices to detect its presence, and simplifies its localization---and subsequent destruction. The adversary, therefore, would rather be more efficient, disrupting the protocol using a minimal number of transmissions.

The efficiency of the adversary can be quantified, roughly speaking, by comparing the duration of the disruption to the adversary's cost for causing the disruption. In the systems literature, this metric has been informally referred to as jamming gain. For example, if the adversary must broadcast in every round, the jamming gain is 1. By contrast, if the adversary need never broadcast to prevent termination, then the jamming gain is infinite. A jamming gain of 100 implies that the adversary need only broadcast in one percent of the rounds to disrupt the protocol.

A second metric, disruption-free complexity, measures how long the adversary can disrupt a protocol without performing even one broadcast. The uncertainty introduced by the possibility of adversarial broadcasts is sufficient to slow down many protocols. If a protocol has large disruption-free complexity, then the adversary can significantly reduce the throughput of multiple consecutive executions, while avoiding the disadvantages of actually jamming.

This project is the first theoretical examination of the efficiency of malicious disruption in a wireless ad hoc network. We begin by analyzing a 3-player game that captures many of the fundamental difficulties of wireless coordination. We then extend these results to several classical problems: reliable broadcast, leader election, static k-selection and consensus. For each problem, we present fundamental limits on the robustness to malicious interference, and we present algorithms that match these standards of robustness. The research discussed below appears in [1].

Results: The 3-Player Game

The 3-player game consists of two honest players---Alice and Bob, and a third malicious player, Collin (the Collider). All three players share a time-slotted single-hop wireless radio channel. Alice and Bob each begin with a value to communicate. Colin is determined to prevent them from communicating, in either direction, for as long as possible. Collin can broadcast in any time slot (i.e., round), potentially destroying honest messages or overwhelming them with malicious data. In order to precisely measure the efficiency of a malicious adversary, we endow Collin with a budget of B messages, and analyze how long Alice and Bob can be disrupted. The size of B is not known a priori to Alice and Bob. (If it were, then Alice and Bob could communicate reliably by repeating each message 2B+1 times.)

We show that Collin can delay Alice and Bob's communication for 2B+lg|V|/2 rounds, where V is the set of possible values that Alice and Bob may communicate. An immediate corollary is that no protocol for Alice and Bob can achieve a jamming gain better than 2. This result is surprising as it implies that every protocol has some semantic vulnerability that the adversary can exploit to gain extra efficiency. A second corollary is that the disruption-free complexity is Theta(lg|V|). Therefore for large V, the passive presence of Collin can significantly reduce Alice and Bob's communication throughput. We prove these lower bounds by exhibiting a strategy for Collin to delay Alice and Bob, exploiting the fact that they can never trust any message, since Collin could have overwhelmed it with a fake message.

For our upper bound, we consider a (harder) setting where Alice needs to transmit a value to Bob, who does not broadcast any messages. We exhibit a protocol that allows Alice to transmit her value to Bob in 2B + 4lg|V| rounds. (We also analyze the trade-off between the energy expended by Alice and the transmission time.)

Finally, we consider a variant of the 3-player game in which Alice and Bob do not start in the same round; Bob is activated asynchronously by the adversary. We present a protocol that solves this problem and still terminates within 2B + Theta(lg|V|) rounds (assuming Alice has an unrestricted message budget).

Results: n-Player Games

The trials and tribulations of Alice and Bob capture something fundamental about how efficiently malicious devices can disrupt wireless coordination. We derive new lower bounds---via reduction to our 3-player game---for several classical n-player problems: reliable broadcast: 2B + Theta(lg|V|); leader election: 2B + Omega(log(n/k)); static k-selection: 2B + Omega(k lg(|V|/k)). For the latter two cases, k represents the number of participants contending to become leader and to transmit their initial value, respectively. As before, we draw immediate corollaries regarding the jamming gain and disruption-free complexity.

We also consider a more general framework that also includes crash failures: the malicious adversary can both broadcast B messages and also crash up to t honest devices. We study binary consensus as an archetypal problem in this framework, and derive a lower bound of 2B + Theta(t) rounds. The Theta(t) factor is established by a technique that maintains the indistinguishability of two univalent configurations for t rounds. The 2B factor then follows from a (partial) reduction to consensus. This shows a jamming gain of 2, as before. By contrast, the disruption-free complexity, Theta(t), is significantly larger than for the crash-free models. (Notice that if the adversary is benign, then crash failures have no effect on the complexity.)

Finally, we present tight upper bounds for reliable broadcast and consensus and nearly tight bounds for leader election and static k-selection.

Assumptions and interpretations

Underlying our results on jamming gain and disruption-free complexity is an analysis of how long the adversary can disrupt communication given a limited broadcast budget. This interpretation is interesting in its own right: a limited broadcast budget models the (limited) energy available to a set of malicious devices.

Clearly, authentication---for example, using cryptographic keys---impacts our lower bounds. With authentication, the 3-player communication game completes in B+1 rounds, resulting in a jamming gain and disruption-free complexity of 1. Intuitively, a jamming gain arises from semantic vulnerabilities in the protocol; cryptographic techniques can eliminate this vulnerability. In general, however, deploying cryptographic solutions in wireless networks can be difficult. Public key authentication schemes are often expensive both in computation and, to some extent, communication. Symmetric key schemes (such as MACs) have been deployed in wireless networks, yet the focus has generally been link-level security, rather than authenticated broadcast, and there remain issues with key distribution. For example, if only a single key is used, the system is easily compromised by a single corrupted node; if multiple keys are used, then keys must be exchanged and communication is complicated. One interpretation of our bound is that authentication should be deployed only if its cost is less than the cost of waiting an additional B+Theta(lg|V|) rounds.

Future Work

There remain a variety of interesting open questions. First, notice that our lower bounds hold for weaker game than those discussed here, for example, computing the bitwise-and or bitwise-or of the players' initial values. It remains interesting to determine the exact set of problems for which these bounds hold.

Also, we have to this point considered only deterministic protocols We conjecture that randomization does not help Alice and Bob to defeat Collin. That is, we believe that even in the randomized case, Collin can still successfully delay Alice and Bob for 2B+Theta(log|V|) rounds.

Finally, we would like to extend our results to multi-hop environments. In deriving multi-hop algorithms, there are several new challenges: for example, nodes must cope with the "hidden terminal" problem; as another example, nodes must cope with the case where the source of the original broadcast is itself corrupt. In deriving lower bounds, the main challenge is determining the worst-case distribution of adversaries, and the worst-case distribution of each adversaries broadcsts.

Support:

This work is supported in part by NSF Award #CCR-0326277 and USAF, AFRL Award #FA9550-04-1-0121.

References

[1] Seth Gilbert, Rachid Guerraoui, and Calvin Newport. Of malicious motes and suspicious sensors: On the efficiency of malicious interference in wireless networks. In Proceedings of the International Conference on Principles of Distributed Systems (OPODIS), December 2006.