Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Reliable Broadcast Protocols: <s> We consider the problem of reliable broadcast in an infinite grid (or finite toroidal) radio network under Byzantine and crash-stop failures. We present bounds on the maximum number of failures that may occur in any given neighborhood without rendering reliable broadcast impossible. We improve on previously proved bounds for the number of tolerable Byzantine faults [6]. Our results indicate that it is possible to achieve reliable broadcast if slightly less than one fourth fraction of nodes in any neighborhood are faulty, and impossible otherwise. We also show that reliable broadcast is achievable with crash-stop failures if slightly less than half the nodes in any given neighborhood may be faulty. In particular, we establish exact thresholds under a specific distance metric. <s> BIB001 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Reliable Broadcast Protocols: <s> We study the problem of achieving global broadcast in a radio network where a node can multicast messages to all of its neighbors (that is, nodes within some given distance r), and up to t nodes in any single neighborhood may be corrupted. Previous work assumes that corrupted nodes can neither cause collisions nor spoof addresses of honest nodes. In this work, we eliminate these assumptions and allow each faulty node to cause a (known) bounded number of collisions and spoof the addresses of arbitrary other nodes. We show that the maximum tolerable t in this case is identical to the maximum tolerable t when collisions and address spoofing are not allowed. Thus, by causing collisions and spoofing addresses an adversary may be able to degrade the efficiency of achieving broadcast, but it cannot affect the feasibility of this task. <s> BIB002 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Reliable Broadcast Protocols: <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> BIB003 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Reliable Broadcast Protocols: <s> We consider the problem of reliable broadcast in a wireless network in which nodes are prone to failure. Each node can fail independently with probability p. Failures are permanent. The primary focus is on Byzantine failures, but we also handle crash-stop failures. We consider two network models: a regular grid, and a random network. Our necessary and sufficient conditions for the Byzantine failure model indicate that p should be less than frac12, and the critical node degree is Theta(dmin+(lnn/ln(1/2p))+ln(1/2(1-p))) (where dmin is the minimum node degree associated with a non-empty neighborhood, and is a small constant). For a random network we prove that, for failure probability less than frac12, the critical average degree for reliable broadcast is O(lnn/frac12-p+frac12ln(1/2(1-p))). We briefly discuss the issue of crash-stop failures for which we have results that improve upon previously existing results for this model, when p approaches 0. We also identify an interesting similarity in the structure of various known results in the literature pertaining to a set of related problems in the realm of connectivity and reliable broadcast. <s> BIB004 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Reliable Broadcast Protocols: <s> Requirements for Wireless Sensor networks will increase in the future. Requirements are demanding, especially in industrial real time networks which require high reliability and performance. Network simulation tools are often needed in the network design phase before actual implementation. In this paper, we selected 5 common wireless sensor networks simulation tools and estimated their suitability for high-performance network planning and verification. According to the study, some tools managed the requirements for demanding simulation but needed some extension. <s> BIB005 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Reliable Broadcast Protocols: <s> Simulators, emulators and testbeds are invaluable tools for performance evaluation of algorithms and protocols in wireless sensor networks (WSNs). It is extremely difficult to choose an appropriate tool for performance testing without the horizontal and vertical analysis of existing tools. This paper presents a survey of thirty five performance evaluation tools for WSNs. Unlike most other studies, tools were selected based on their popularity, support for WSNs, active maintenance and the help available. On the horizontal dimension, prominent competitors at each stage were selected. For vertical analysis, tools for simulation, emulation and testbeds were categorized accordingly. We believe that this survey will aid researchers, application and tool developers while selecting an appropriate tool for their implementation. We have highlighted an open research issue to have an integrated tool that supports modeling, simulation, emulation and testbed implementation for algorithm validation, performance evaluation and proof-of-concept implementation in WSNs. <s> BIB006
Using the solution to the single stream Bad Santa Problem, the authors provide a reliable broadcast protocol tolerating Byzantine faults that runs in two stages. In the first stage, the source propagates a fingerprint f (m) of the message m it wants to broadcast. This fingerprint is assumed to be of size at least lg 2 |m| bits and generated using a secure hash function. Propagation of f (m) is again done using the algorithm in  and every node is assured of committing to the correct fingerprint. In the second stage, the source broadcasts m at a prespecified time slot t start and all correct nodes in N (0, 0) are assumed to receive m from the source and commit internally. Each node q(x , y ) ∈ N (0, 0) then broadcasts its committal to m over the next 2r consecutive rounds. Recall that the proof of completeness given in  is constructive. That is, the set of nodes to which p should listen is specified exactly; call this set G p . Node p selects nodes to listen to from G p using the solution to the Bad Santa Problem and, upon receiving any message m , checks f (m ) against the fingerprint to which it committed in the first stage. If they match, p commits to m internally and executes the broadcast instructions mentioned previously. Let s be the number of times the adversary can create an input x , apply a hash function f to x and check for a match between the output fingerprint f (x ) and some other fingerprint for which the adversary is attempting to generate a collision. Assuming t < There are two important points to note. First, nodes must be awake as normal for the first stage. However, the transmission of a fingerprint should require significantly smaller time slots for moderately sized messages or larger. The authors argue that the network could be set up to alternate between the first stage, where nodes are constantly awake, and the second stage, where nodes are achieving significant power savings. Second, in the latter protocol, nodes are sending more bits by a factor of k; however, the expected amount of times the full message must be received decreases by far more. Therefore, there is a significant overall savings in expectation. To contrast these results with previous work, note that under the previous algorithms for reliable broadcast BIB001 ,  , each node 1) is awake for (2t + 1) = Θ(n) time slots, 2) broadcasts Θ(|m|) bits; 3) receives Θ(|m|) bits in the fail-stop model; and 4) can be forced by the adversary to receive Θ(n|m|) bits in the Byzantine fault model. Of course, these results on reliable broadcast allow for a probability of failure, but the authors also note that |m| need not be large to make the probability of finding a message with the same fingerprint very small. For example, if |m| = 1 kB, the probability of a collision is already less than 10 −30 . Therefore, these algorithms save substantially on the overall amount of time a node must be awake in order to achieve reliable broadcast. However, there are trade-offs: the latency of the protocol is increased due to the need for two-stages and the need for synchronization is even more important here due to the use of t start as an initial time step in the protocol. Furthermore, while this work makes progress on the issue of energy-efficient reliable broadcast, it remains to be seen whether these results can be applied to situations where the adversary can cause message collisions or spoof correct nodes. Alistarh et al.  As discussed in Section II-C, cryptographic techniques can offer protection against certain attacks in the wireless domain. In particular, cryptographic authentication can prevent malicious behavior where messages are corrupted or correct nodes are spoofed. However, because sensor networks are energy-starved, there has been significant research into lightweight authentication. Here, Alistarh et al. examine reliable broadcast in the absence of such cryptographic authentication. As we saw earlier, Koo et al. BIB002 also addressed this problem and Alistarh et al. adopt the grid model. However, the model of BIB002 assumes that the instances of spoofing and message collisions are known a priori while Alistarh et al. do not make this assumption. Non-Cryptographic Authenticated Broadcast: The authors provide two non-authenticated reliable broadcast protocols called NEIGHBORWATCHRB and MULTIPATHRB. Both protocols rely on a critical subroutine called the 1HOP-PROTOCOL which, in turn, is based on the 2BIT-PROTOCOL and we describe both subroutines now. The 2BIT-PROTOCOL addresses the problem of a sender which wishes to transmit two bits to a receiver in the presence of message collisions and spoofing attacks. This protocol is similar to the communication protocol between Alice and Bob used by Gilbert et al. BIB003 . Again, Alice and Bob can detect message collisions and the unforgeability of silence allows the players to detect interference and indicate this in a veto round. If a veto message is sent, then the 2BIT-PROTOCOL fails. By stringing together executions of the 2BIT-PROTOCOL, the entire message can be sent; this is the 1HOP-PROTOCOL as it accomplishes communication within a local broadcast neighborhood. The first protocol NEIGHBORWATCHRB uses the 1HOP-PROTOCOL to achieve a multi-hop protocol by partitioning the grid into r/2 × r/2 squares. Each node belongs to exactly one square and is aware of the other members of the same square. The devices in each square act in concert, either all broadcasting or all listening in unison; in this sense, a square becomes the new atomic unit in the grid and the authors refer to these as meta-nodes. Each meta-node is assigned a broadcasting time slot according to some global schedule. When a meta-node is scheduled, it executes a step of the 1HOP-PROTOCOL with neighboring meta-nodes; otherwise, for a significant amount of the time it is listening to neighboring meta-nodes. An interesting property of this protocol is that the fault-tolerance is fairly high; specifically, if t < r/2 2 , NEIGHBORWATCHRB achieves broadcast with an asymptotically optimal running time of O(βD + log |Σ|) where Σ is the set of all possible messages. The second protocol MULTIPATHRB achieves the optimal fault-tolerance t < (r/2)(2r + 1) by combining the 1HOP-PROTOCOL with the reliable broadcast protocol of Bhandari and Vaidya  . In contrast to the proactive protocol by Koo et al. BIB002 , MULTIPATHRB is reactive which avoids the waste of unnecessary retransmissions. Finally, the authors conduct simulations to evaluate their protocols under more realistic conditions. Notably, instead of deployment on the grid, nodes are placed uniformly at random in the plane. Both NEIGHBORWATCHRB and MUL-TIPATHRB exhibit promising performance. Not surprisingly, as node density increases, tolerance to both crash failures and Byzantine faults increases. Although the analysis of NEIGHBORWATCHRB does not admit optimal fault tolerance, this protocol achieves superior tolerance in practice over MULTIPATHRB, for high node density. Moreover, and in line with the theoretical analysis, NEIGHBORWATCHRB achieves significantly lower latency. Given the previous works we have surveyed, this paper is one of the few where the authors take significant steps to bridge the gap between their theoretical results and the practical performance of their protocols. Two final comments are in order. Notably, while noncryptographic authentication is achieved, both MULTIPATHRB and NEIGHBORWATCHRB require devices to spend significant time in the receive state so that they may detect interference or veto messages. Another issue that deserves some discussion is that of simulation itself, which allows for a evaluation of protocols while avoiding the typically high costs of deploying a sizable real-world test-bed. Here, the authors use the WSNet Worldsense simulator [98] . There are also a host of other popular simulators such as ns-3 [99], QualNet [100] , OPNET Modeler [101] , OMNet [102] which can be used in tandem with Castalia [103] and many others. We refer the interested reader to the surveys of Korkalainen et al. BIB005 and Imran et al. BIB006 for more information on available sensor network simulators. BIB004 , BIB004 Much of the previous work has focused on the locally bounded fault scenario in the grid model. Here in BIB004 , the authors examine the probabilistic scenario in both the grid and in a network where nodes are distributed uniformly at random in the plane. In both cases, the network size is bounded by √ n× √ n. The aim of this analysis is to identify the maximum probability of failure p max along with the critical node degree d critical for which reliable broadcast remains feasible.