Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Meier et al. [65] <s> How efficiently can a malicious device disrupt communication in a wireless network? Imagine a basic game involving two honest players, Alice and Bob, who want to exchange information, and an adversary, Collin, who can disrupt communication using a limited budget of β broadcasts. How long can Collin delay Alice and Bob from communicating? In fact, the trials and tribulations of Alice and Bob capture the fundamental difficulty shared by several n–player problems, including reliable broadcast, leader election, static k–selection, and t–resilient consensus. We provide round complexity lower bounds—and (nearly) tight upper bounds—for each of those problems. These results imply bounds on adversarial efficiency, which we analyze in terms of jamming gain and disruption–free complexity. <s> BIB001 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Meier et al. [65] <s> 802.11a, b, and g standards were designed for deployment in cooperative environments, and hence do not include mechanisms to protect from jamming attacks. In this paper, we explore how to protect 802.11 networks from jamming attacks by having the legitimate transmission hop among channels to hide the transmission from the jammer. Using a combination of mathematical analysis and prototype experimentation in an 802.11a environment, we explore how much throughput can be maintained in comparison to the maintainable throughput in a cooperative, jam-free environment. Our experimental and analytical results show that in today's conventional 802.11a networks, we can achieve up to 60% of the original throughput. Our mathematical analysis allows us to extrapolate the throughput that can be maintained when the constraint on the number of orthogonal channels used for both legitimate communication and for jamming is relaxed. <s> BIB002 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Meier et al. [65] <s> In this paper, we address the problem of cross-layer denial of service attack in wireless data networks. We introduce SPREAD -a novel adaptive diversification approach to provide resiliency against such attacks. SPREAD relies on a mechanism-hopping technique, which can be seen as a multi-layer extension of the frequency-hopping technique. We apply a game-theoretic framework for modeling the interaction of the communicating nodes and the adversaries and analyze the proposed approach. We reason about the advantages of SPREAD against various types of jammers and demonstrate the effectiveness of our approach in the case of IEEE 802.11 protocol stack by studying the EIFS attack, periodical jamming and a Packet-Size Game. As an example, we show that mechanism-hopping over two instances of IEEE 802.11 can achieve several orders of magnitude gain in throughput over a single-instance network under the EIFS attack. <s> BIB003 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Meier et al. [65] <s> In this paper we consider the problem of designing a medium access control (MAC) protocol for single-hop wireless networks that is provably robust against adaptive adversarial jamming. The wireless network consists of a set of honest and reliable nodes that are within the transmission range of each other. In addition to these nodes there is an adversary. The adversary may know the protocol and its entire history and use this knowledge to jam the wireless channel at will at any time. It is allowed to jam a (1-epsilon)-fraction of the time steps, for an arbitrary constant epsilon>0, but it has to make a jamming decision before it knows the actions of the nodes at the current step. The nodes cannot distinguish between the adversarial jamming or a collision of two or more messages that are sent at the same time. We demonstrate, for the first time, that there is a local-control MAC protocol requiring only very limited knowledge about the adversary and the network that achieves a constant throughput for the non-jammed time steps under any adversarial strategy above. We also show that our protocol is very energy efficient and that it can be extended to obtain a robust and efficient protocol for leader election and the fair use of the wireless channel. <s> BIB004 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Meier et al. [65] <s> Imagine that Alice wants to send a message m to Bob, and that Carol wants to prevent this. Assume there is a communication channel between Alice and Bob, but that Carol is capable of blocking this channel. Furthermore, there is a cost of S dollars to send on the channel, L dollars to listen on the channel and J to block the channel. How much will Alice and Bob need to spend in order to guarantee transmission of m? This problem abstracts many types of conflict in information networks including: jamming attacks in wireless networks and distributed denial-of-service (DDoS) attacks on the Internet, where the costs to Alice, Bob and Carol represent an expenditure of energy or network resources. The problem allows us to quantitatively analyze the economics of information exchange in an adversarial setting and ask: Is communication cheaper than censorship? We answer this question in the affirmative by showing that it is significantly more costly for Carol to block communication of m than for Alice to communicate it to Bob. Specifically, if S, L and J are fixed constants, and Carol spends a total of B dollars trying to block m, then Alice and Bob must spend only O(Bφ - 1 + 1)=O(B.62+1) dollars in expectation to transmit m, where φ = (1 + √5)/2 is the golden ratio. Surprisingly, this result holds even if (1) B is unknown to both Alice and Bob; (2) Carol knows the algorithms of Alice and Bob, but not their random bits; and (3) Carol has total knowledge of past actions of both players. Finally, we apply our work to two problems: (1) DoS attacks in wireless sensor networks and (2) application-level DDoS attacks in a wired client-server scenario. Our applications show how our results can provide an additional tool in mitigating such attacks. <s> BIB005
The ability to transmit over more than one channel is critical to a number of methods aimed at mitigating jamming attacks. For instance, channel-hopping defenses have been shown to be effective in permitting communication in the presence of jamming adversaries BIB002 , BIB003 . However, a prerequisite for any multi-hop network communication is often the discovery of the local topology. That is, a node requires some knowledge regarding the existence of its neighbors in order to facilitate successful routing. In this work, Meier et al. focus on the problem of node discovery in the presence of a jamming adversary. Formally, two nodes v 1 and v 2 discover each other if the following criteria hold: (1) v 1 and v 2 are on the same channel c, (2) v 1 is in the listening state and v 2 sends its contact information on channel c (or vice versa) and (3) the channel c is not jammed. The adversary has the ability to jam t out of m channels that would otherwise minimize the number of time slots prior to v 1 and v 2 from discovering each other; the authors label the expected amount of time prior to discovery as the discovery time. The reactive capability of the adversary to select its jammed channels in this fashion makes the problem challenging. A key metric in evaluating the performance of the discovery algorithms is competitiveness which is defined as follows. Let  2 /(m − t). Therefore, the behavior of the optimal algorithm REF is established. The stateless and independent nature of this randomized algorithm is clearly well-suited to sensor networks. The next step is to consider a particular type of algorithm when t is unknown. Lett denote the set of channels c 1 , ..., c 2t which are referred to as a class of channels. The authors examine algorithms that: (1) select each class of channels i uniformly at random, and then (2) select uniformly at random a particular channel on which to transmit. This general approach to a discovery algorithm leads to the notion of ALG k which selects randomly from the classeŝ The authors demonstrate that for k = log m , the competitive ratio is O(log 2 m). It is then shown that the optimal competitive ratio in this scenario can be formulated as an optimization problem and yields an algorithm OP T with ρ = Θ(log 2 m) which illustrates that ALG log m is indeed asymptotically optimal. Extensions and Experimental Results: As an intermediate step, the authors next consider the case when we have partial knowledge of t in the sense that the distribution for the number of jammed channels is known a priori. The analysis of this case yields a non-linear optimization formulation that can only be solved numerically. A multi-player setting is also considered. Here, the objective is to minimize the expected discovery time for two nodes in the presence of other nodes that are similarly attempting to discover each other. It is shown that for n nodes, when t is known, if Ω(n + t) channels are available, then the asymptotically optimal expected discovery time is Θ(n + t). Finally, the authors experiment with their algorithms. For a random jamming adversary, they observe improved performance of ALG log m and OP T over the algorithms that simply select channels uniformly at random (U N I) when the number of jammed channels is not excessive (roughly 100 out of the total 128 channels). The authors also experiment with a situation where interference occurs due to non-malicious radio interference. To this end, they experiment with the upper-end Bluetooth channels which are subject to interference from a microwave oven. Experiments with a Bluetooth device discovery algorithm illustrate that OPT achieves a substantial reduction in discovery time; up to 1/3 of the Bluetooth algorithm when interference is present. King et al. BIB005 Several of the results we have surveyed consider the energy expenditures of the adversary and the correct players in isolation. However, if energy is a scarce resource for both the adversary and correct nodes, then it seems reasonable to consider a notion of relative cost. In BIB005 , the authors pursue this idea by looking at the expected cost of a correct node relative to the cost incurred by the adversary, where cost is measured in the number of time slots spent in either the transmit or receive state. The overall goal is to design a communication algorithm that yields a relative cost that is in favor of the players; such an algorithm is called favorable. A Simple Scenario: Similar to that considered in BIB001 the authors first examine a simple two-player scenario in a single-channel time-slotted network where the players, Alice and Bob, can detect collisions. Alice (the sender) wishes to transmit a message m to Bob (the receiver) and there is a jamming adversary who aims to prevent communication. The jamming adversary is allowed to follow any jamming strategy it wishes (i.e. constant, random, adaptive, reactive) and incurs a cost of T by either (1) jamming the channel or (2) forging collisions whereby a correct player will detect that a message collision has occurred. A significant deviation from the work in BIB001 is that cryptographic authentication is assumed; recall the discussion in Section II-C. Therefore, the adversary is unable to spoof either the sender or receiver. In contrast to other work, another important difference is that communication must be guaranteed with probability 1 instead of with high probability. As we have seen in BIB004 and  , high probability guarantees are provided in terms of n. When n is large, then the probability of failure can easily be made quite small. However, in sensor networks, n will likely correspond to the number of nodes within a broadcast radius which can be small relative to the total number of nodes N . Consider the situation where the probability of failure is at most O(n −c ), but the total number of nodes is exponential in n (i.e. N = Θ(2 n )). Then for a message that transits Ω(N ) hops, the probability of failure along the path of traversal is substantial. The protocol specified by the authors achieves communication in the following general way. The protocol proceeds in rounds each consisting of a pair of phases where the number of time slots per phase increases geometrically per round. In phase 1, Alice transmits m randomly while Bob listens randomly. If Bob receives m, he terminates the protocol. Otherwise, in phase 2, Bob sends a request to Alice for m to be retransmitted in the next round. Alice listens to a sampling of slots in phase 2 and, if a retransmission request is received or a collision is detected, she proceeds to the next round and begins transmitting again in phase 1; otherwise, Alice terminates the protocol. The adversary can prevent termination of the players in more than one fashion. In order to prevent Bob from terminating, the adversary can jam the transmission of m. However, the analysis shows that this is difficult to do without the adversary incurring far more cost than either correct player. On the other hand, the adversary can prevent Alice from terminating by simply forging collisions which Alice will interpret as having originated from Bob. This can be achieved by having two Byzantine devices broadcast simultaneously or replaying noise from a previous message collision over the channel. Despite these challenges, the authors prove that their protocol requires the players to incur an expected cost of O(T ϕ−1 + 1) where ϕ =