Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> A Faulty Dealer with Collisions, Spoofing by Faulty Nodes: <s> The problem addressed here concerns a set of isolated processors, some unknown subset of which may be faulty, that communicate only by means of two-party messages. Each nonfaulty processor has a private value of information that must be communicated to each other nonfaulty processor. Nonfaulty processors always communicate honestly, whereas faulty processors may lie. The problem is to devise an algorithm in which processors communicate their own values and relay values received from others that allows each nonfaulty processor to infer a value for each other processor. The value inferred for a nonfaulty processor must be that processor's private value, and the value inferred for a faulty one must be consistent with the corresponding value inferred by each other nonfaulty processor. It is shown that the problem is solvable for, and only for, n ≥ 3 m + 1, where m is the number of faulty processors and n is the total number. It is also shown that if faulty processors can refuse to pass on information but cannot falsely relay information, the problem is solvable for arbitrary n ≥ m ≥ 0. This weaker assumption can be approximated in practice using cryptographic methods. <s> BIB001 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> A Faulty Dealer with Collisions, Spoofing by Faulty Nodes: <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
In the works we have surveyed so far, it has been assumed that the dealer is honest. In the absence of message collisions, the dealer cannot cause confusion over what value is being broadcast. This is because all nodes in the neighborhood N (d) will immediately commit to the first value they hear from d; whether d is controlled by the adversary is of no consequence. However, now consider the following situation in which message collisions can occur: 1) The adversary uses a Byzantine node at location (0, r + 1) to broadcast a null value as d broadcasts v. 2) The adversary then causes a node at location (0, −r) to broadcast a null value as d broadcasts v where v = v. In step 1, all nodes in the top r rows of N (d) will receive only noise due to a message collision. However, all nodes in the bottom r+1 rows of N (d) will commit to v. In the second step, the reverse will happen with the nodes in the top half of N (d) (inclusive) committing to v . Due to the collisions, the nodes in N (d) will be unaware that conflicting values have been initiated by the dealer and, therefore, reliable broadcast will not be achieved. The challenge of address spoofing is fairly obvious. Under the protocol by Bhandari and Vaidya, a node p will take action only upon receiving t + 1 messages with identical values from distinct nodes in a single neighborhood. Therefore, a faulty node may simply claim to be t + 1 other nodes, all within a single neighborhood, and trick p. A Robust Protocol: We assume that the total number of message collisions and address spoofing instances afforded to each faulty node is n c and n s , respectively. The protocol of BIB002 can be broken into two parts as follows: 1) Agreement in N (d): all nodes in N (d) will come to an agreement prior to propagating the message to other nodes. 2) Robust Propagation: the value agreed upon in the first step will be propagated in such a way that n c message collisions and n s spoofing attempts by the adversary do not prevent the correct nodes from committing to the correct value indefinitely. To achieve agreement in N (d), all nodes in the neighborhood emulate a peer-to-peer protocol appearing in BIB001 ,  . However, this protocol assumes that the network is fully connected. In contrast, the nodes in N (d) are not fully connected (in a single hop sense) due to the limited broadcast radius. However, the authors show that it is possible for a node i ∈ N (d) to set up a virtual connection to all other nodes in N (d) by initiating the protocol B robust below in the case that spoofing is allowed and nodes can detect collisions. In the following, B norm is the protocol of Bhandari and Vaidya presented in  .