Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Robust Protocol B robust <s> Much work has focused on the Byzantine Generals (or secure broadcast) problem in the standard model in which pairwise communication is available between all parties in the network. Some research has also explored the problem when pairwise channels exist only between selected pairs of players, or under the assumption of "k-cast channels" shared by all subsets of players of size k. However, none of these models are appropriate for radio networks in which a player can communicate only by multicasting a message which is then received by all players within some radius r (i.e., the neighbors of the transmitting node). Yet, as far as we are aware, obtaining secure broadcast in radio networks in the presence of a Byzantine adversary has not been studied before.This paper corrects this omission, and provides the first analysis of secure broadcast in radio networks for the case of Byzantine adversaries. We note that secure broadcast is impossible in the presence of an omnipotent adversary. To bypass this barrier, we make the following assumption: there exists a prefixed schedule for players to communicate and everyone (including corrupted ones) adheres to this schedule. Under this assumption, we give a simple broadcast protocol which is provably secure whenever the adversary corrupts at most 1 4 r(r+√rover2 + 1)-3 neighbors (roughly a 1/4π fraction) of any honest player. On the other hand, we show that it is impossible to achieve secure broadcast when the adversary corrupts ⌈1/2 r(2r+1)⌉ (roughly a 1/π fraction) neighbors of any honest player. <s> BIB001 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Robust Protocol B robust <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> BIB002 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Robust Protocol B robust <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> BIB003 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Robust Protocol B robust <s> We consider message-efficient broadcast tolerating Byzantine faults in a multi-hop wireless sensor network. Assuming a grid network where all nodes have a communication range of $r$, and a single neighborhood contains at most $t$ dishonest and collision-capable (bad) nodes, each with a message budget $m_f$, we investigate the minimum message budget $m$ that each honest (good) node must have in order to achieve reliable broadcast. We consider three cases: (1) $m_f$ is known in advance and $m$ is homogeneous among all good nodes, (2) $m_f$ is known in advance and $m$ is heterogeneous among good nodes, (3) $m_f$ is unknown. For the first two cases, we present possibility results and broadcast protocols that have message costs within twice the lower bound. For the third case, we present a coding scheme that helps verify the integrity of messages at a receiving node without using any cryptographic techniques. This code leads to a {\em reactive local broadcast} primitive that has probabilistic reliability guarantees. Combined with a previously proposed scheme, it results in a broadcast protocol for $t <s> BIB004 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Robust Protocol B robust <s> We address the problem of minimizing power consumption when broadcasting a message from one node to all the other nodes in a radio network. To enable power savings for such a problem, we introduce a compelling new data streaming problem which we call the Bad Santa problem. Our results on this problem apply for any situation where: (1) a node can listen to a set of n nodes, out of which at least half are non-faulty and know the correct message; and (2) each of these n nodes sends according to some predetermined schedule which assigns each of them its own unique time slot. In this situation, we show that in order to receive the correct message with probability 1, it is necessary and sufficient for the listening node to listen to a $\Theta(\sqrt{n})$ expected number of time slots. Moreover, if we allow for repetitions of transmissions so that each sending node sends the message O(log ∗ n) times (i.e. in O(log ∗ n) rounds each consisting of the n time slots), then listening to O(log ∗ n) expected number of time slots suffices. We show that this is near optimal. ::: ::: We describe an application of our result to the popular grid model for a radio network. Each node in the network is located on a point in a two dimensional grid, and whenever a node sends a message m, all awake nodes within L ∞ distance r receive m. In this model, up to $t 0, we can achieve an even better energy savings. In particular, if we allow each node to send O(log ∗ n) times, we achieve reliable broadcast with each node sending O(nlog 2|m|+(log ∗ n)|m|) bits and receiving an expected O(nlog 2|m|+(log ∗ n)|m|) bits and, after broadcasting a fingerprint of m, each node is awake for only an expected O(log ∗ n) time slots. Our results compare favorably with previous protocols that required each node to send Θ(|m|) bits, receive Θ(n|m|) bits and be awake for Θ(n) time slots. <s> BIB005 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Robust Protocol B robust <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> BIB006
1) In each case that node i would send a message m in B norm , i sends m for a total of t(n c + n s ) + 1 times. 2) In each case that i would perform an action when receiving a message m from node j in B norm , i performs this action only when it receives the message t · n s + 1 times from j for the first time. By using an almost identical argument to that given in  , it can be shown that by having every node in N (d) execute the above protocol, all nodes in N (d) will come to agreement upon v within a bounded amount of time. Intuitively, if a node i has received at least t · n s + 1 instances of the same value v, then, given that there are at most t faulty nodes in N (i), node i is assured that v is the correct value. Similarly, by sending the value t(n c + n s ) + 1 times, node i guarantees that a listening neighbor will receive the v at least t · n s + 1 identical copies of the value, and thus can determine that v is legitimate. Now, for every instance that the peer-to-peer protocol would dictate that a peer send a message to all other peers, a node i in N (d) uses the above robust protocol. Now that all nodes in N (d) can agree upon a value, it remains to be seen how this value is propagated throughout the network. However, this also follows from B robust using the same proof structure as was used to prove correctness of the protocol of B norm . The authors also show how, with slight modifications to B robust , reliable broadcast is feasible when nodes cannot detect collisions. There is one more important point to be made regarding the protocol described in BIB003 . Note that the adversary can force a correct node to send Ω(t(n c + n s )) messages. However, a faulty node sends only Ω(n c +n s ) before its malicious actions are exhausted. Therefore, correct nodes are assumed to be able to send more messages than faulty nodes. In other words, correct nodes are required to possess more energy than faulty nodes. This is a rather strong assumption and it has motivated research into how to reduce the cost of reliable broadcast. Bertier et al. BIB004 ,  Until this point, the results we have surveyed have primarily focused on the feasibility of reliable broadcast in the context of obtaining upper and lower bounds on the number of faults. However, as we saw in the work by Koo et al. BIB003 , the addition of message collisions to the grid model motivates the consideration of energy efficiency. In BIB004 , Bertier et al. extend their initial findings in  and focus on this issue by examining the number of messages both the correct nodes and adversarial nodes can send. In particular, a correct node is allowed to send m messages while a Byzantine node may send m f messages; these message budgets are motivated by the energy contraints of sensor networks. The costs, in terms of message efficiency, for achieving reliable broadcast are then expressed in terms of these budgets. Reducing The authors go on to show that for m ≥ 2m 0 , this protocol achieves reliable broadcast for t < r(2r + 1). Importantly, this bound on t exceeds that of the previous works we have examined by a factor of 2 in the Byzantine case. This increased tolerance is due to the fact that Byzantine faults can be overcome when correct nodes possess a higher message budget than faulty nodes as this allows for the correct message to be received in the majority. This result clearly improves on the message efficiency as it reduces the number of sent messages by a factor of (1/2)(r(2r +1)− t) in comparison to the protocol by Koo et al. BIB003 . It is unknown whether reliable broadcast is feasible for the intermediate case where m ∈ [m 0 , 2m 0 ]. An interesting additional case to consider is when m is still known but is heterogeneous; that is, when the message budget differs between correct nodes. Here, the authors demonstrate a modified protocol that guarantees reliable broadcast so long as Θ(r 3 ) correct nodes have a budget of m = 2·t·m f +1 (r(2r+1)−t)/2 and the remaining correct nodes have a budget of m 0 . Notably, m ≤ 2m 0 , implying that the heterogeneous case offers a strict improvement over the situation where m is homogeneous; this improvement arises due to a more careful analysis of how the correct value is propagated throughout the network. When m f is Unknown -A Reactive Protocol: Recall that in BIB003 , Koo et al. discussed the problematic aspect of their protocol that requires correct nodes to incur a higher cost relative to the adversary. To address this issue, Koo et al. suggested that a reactive strategy, rather than a proactive strategy, might overcome this discrepancy. That is, rather than having correct nodes send redundantly using the protocol of BIB003 , it might be possible to have nodes resend values only when malicious interference is detected. Such a strategy would conserve energy by not engaging in otherwise wasteful redundant transmissions. Here, Bertier et al. devise a reactive strategy that relies on error-detecting codes. By employing results from AllUnidirectional Error-Detecting codes, the authors show how to encode messages such that a receiver can detect when a message has been tampered with by the adversary with high probability. Combining this feature with the protocol of Bhandari and Vaidya BIB002 , the authors devise a reactive protocol that achieves reliable broadcast with probability at least 1−1/n, where n is the network size, and requires no more than m = 2(t · m f + 1)(2 log n + log t + log m max )(k + 2 + 2 log k) transmissions per correct node where t < (r/2)(2r + 1) and m max is a loose upper bound on the budget of a faulty node. This protocol incurs a higher message complexity than the bounded collision case due to the fact that m f is largely unknown and collision detection is not employed. Of course, m f is not completely unknown to the nodes as m max is known to the correct nodes and is a parameter in the coding of the messages. However, m max is allowed to exceed m f by orders of magnitude and, noting the logarithmic term in the protocol's cost, the impact of this is fairly limited. Finally, it is important to note that while all of these results improve on the tranmission costs, they do not address listening costs. In fact, the listening costs of the protocols presented by Bertier et al. appear to be asymptotically equal to those presented by Bhandari and Vaidya BIB002 . As discussed earlier, listening costs are significant and, therefore, reducing the amount of time a correct node must listen to the communication medium is an equally important problem. King et al. BIB005 , BIB005 As we have seen, the issue of energy-efficient reliable broadcast was first raised in the work by Koo et al. BIB003 and pursued by Bertier et al. BIB004 . The work by King et al. BIB005 , BIB005 addresses energy efficiency in the original model analyzed in BIB001 , BIB002 where all nodes, both correct and faulty, obey a global broadcast schedule. Therefore, the main obstacle to reliable broadcast is again misinformation and routing failures caused by Byzantine nodes. In contrast to previous results, King et al. assume that the adversary is computationally bounded; in particular, they assume that the adversary cannot easily invert a secure hash function. As we will see, this property essentially allows for Byzantine faults to be treated as crash failures. We first begin by describing a key subproblem. The Bad Santa Problem: The authors begin by analyzing the Bad Santa Problem which is described as follows. A child is presented with n boxes, one after another. When presented with each box, the child must immediately decide whether or not to open it. If the child decides not to open a box, he is never allowed to revisit it. At least half the boxes have presents in them, but the decision as to which boxes have presents is made by an adversarial Santa who wants the child to open as many empty boxes as possible. The child must obtain a present, while opening the smallest number of boxes in expectation. The authors apply this problem to a single-hop sensor network scenario where a receiver aims to awaken from the energy-efficient sleep state and listen to the communication channel. Each box in the Bad Santa problem corresponds to a time slot and the cost of opening of a box corresponds to the cost of listening. There is assumed to be a set of senders in the broadcast neighborhood of the receiver, each assigned their respective time slot by the global broadcast schedule. The adversary may select up to half of the senders to suffer a crash failure prior to the receiver making its choices about which boxes to open, and the receiver seeks to receive a message by listening to as few time slots as possible in expectation. Importantly, an algorithm for solving the Bad Santa Problem must succeed with probability 1. Without this constraint, a simple random sampling algorithm is sufficient as this can provide a high probability guarantee that the child obtains a toy. The reason for insisting on a Las Vegas algorithm is the same as discussed in our examination of BIB006 . The authors show asymptotically tight upper and lower bounds for the Bad Santa problem. Surprisingly, the optimal expected number of opened boxes is Θ( √ n). An extension called the k-Stream Bad Santa Problem is also examined. In this case, k + 1 streams of n boxes each are presented consecutively to the child who must obtain a toy by the last stream; the order of the full and empty boxes can differ arbitrarily from stream to stream. Here, the optimal expected number of opened boxes is O(log (k) (n) + k) and Ω(log (2k) n). In particular, for k = Θ(log * n), the expected number of opened boxes is O(log * n).