|
Of Malicious Nodes and Suspicious
Sensors
Gilbert, Guerraoui, & Newport
Abstract
How much damage can a malicious adversary cause in a wireless network?
Imagine two honest players, Alice and Bob, who want to exchange information.
Collin, a malicious adversary, wants to prevent them from communicating.
By broadcasting in the same round as an honest player, Collin can destroy
an honest message or overwhelm it with his own malicious data. Being a
tiny device, however, Collin can only broadcast up to B messages. Given
that Alice and Bob do not know B, and cannot distinguish honest from malicious
messages, How long can Collin prevent them from communicating? We show
that Collin can delay Alice and Bob from exchanging any information for
2B+O(log|V|) communication rounds, where V is the set of values that Alice
and Bob may transmit. We show that this is optimal by deriving an algorithm
that matches our lower bound, even in the case where Alice and Bob do
not start the game at the same time, and even when Collin knows a priori
who is trying to transmit information. We argue that our 3-player communication
game captures a fundamental ability of a malicious adversary to disrupt
coordination in a single-hop wireless network. We support this claim by
deriving new bounds---via reduction to the 3-player game---for several
classical n-player problems: reliable broadcast, leader election, and
static k-selection. These represent the first such bounds for these problems
in a wireless network with a genuinely malicious adversary.
|
|
