This dissertation presents algorithms for achieving communication in the presence of adversarial attacks in large, decentralized, resource-constrained networks. We consider abstract single-hop communication settings where a set of senders ๐ wishes to directly communicate with a set of receivers ๐. These results are then extended to provide resource-efficient, multi-hop communication in wireless sensor networks (WSNs), where energy is critically scarce, and peer-to-peer (P2P) networks, where bandwidth and computational power are limited. Our algorithms are provably correct in the face of attacks by a computationally bounded adversary who seeks to disrupt communication between correct participants.
The first major result in this dissertation addresses a general scenario involving single-hop communication in a time-slotted network where a single sender in ๐ wishes to transmit a message ๐ฎ to a single receiver in ๐. The two players share a communication channel; however, there exists an adversary who aims to prevent the transmission of ๐ฎ by periodically blocking this channel. There are costs to send, receive or block ๐ฎ on the channel, and we ask: How much do the two players need to spend relative to the adversary in order to guarantee transmission of the message?
This problem abstracts many types of conflict in information networks, and the associated costs represent an expenditure of network resources. We show that it is significantly more costly for the adversary to block ๐ฎ than for the two players to achieve communication. Specifically, if the cost to send, receive and block ๐ฎ in a slot are fixed constants, and the adversary spends a total of ๐ slots to try to block the message, then both the sender and receiver must be active in only O(๐แต โปยน + 1) slots in expectation to transmit ๐ฎ, where ฯ = (1+ โ5)/2 is the golden ratio. Surprisingly, this result holds even if (1) the value of ๐ is unknown to either player; (2) the adversary knows the algorithms of both players, but not their random bits; and (3) the adversary is able to launch attacks using total knowledge of past actions of both players. Finally, these results are applied to two concrete problems. First, we consider jamming attacks in WSNs and address the fundamental task of propagating ๐ฎ from a single device to all others in a WSN in the presence of faults; this is the problem of reliable broadcast. Second, we examine how our algorithms can mitigate application-level distributed denial-of-service attacks in wired client-server scenarios.
The second major result deals with a single-hop communication problem where now ๐ consists of multiple senders and there is still a single receiver who wishes to obtain a message ๐ฎ. However, many of the senders (strictly less than half) can be faulty, failing to send ๐ฎ or sending incorrect messages. While the majority of the senders possess ๐ฎ, rather than listening to all of ๐ and majority filtering on the received data, we desire an algorithm that allows the single receiver to decide on ๐ฎ in a more efficient manner. To investigate this scenario, we define and devise algorithms for a new data streaming problem called the Bad Santa problem which models the selection dilemma faced by the receiver.
With our results for the Bad Santa problem, we consider the problem of energy-efficient reliable broadcast. All previous results on reliable broadcast require devices to spend significant time in the energy-expensive receiving state which is a critical problem in WSNs where devices are typically battery powered. In a popular WSN model, we give a reliable broadcast protocol that achieves optimal fault tolerance (i.e., tolerates the maximum number of faults in this WSN model)
and improves over previous results by achieving an expected quadratic decrease in the cost to each device. For the case where the number of faults is within a (1-โ)-factor of the optimal fault tolerance, for any constant โ>0, we give a reliable broadcast protocol that improves further by achieving an expected (roughly) exponential decrease in the cost to each device.
The third and final major result of this dissertation addresses single-hop communication where ๐ and ๐ both consist of multiple peers that need to communicate in an attack-resistant P2P network. There are several analytical results on P2P networks that can tolerate an adversary who controls a large number of peers and uses them to disrupt network functionality. Unfortunately, in such systems, operations such as data retrieval and message sending incur significant communication costs. Here, we employ cryptographic techniques to define two protocols both of which are more efficient than existing solutions. For a network of ๐ฏ peers, our first protocol is deterministic with O(logยฒ๐ฏ) message complexity and our second protocol is randomized with expected O(log ๐ฏ) message complexity; both improve over all previous results. The hidden constants and setup costs for our protocols are small and no trusted third party is required. Finally, we present an analysis showing that our protocols are practical for deployment under significant churn and adversarial behaviour.
| Identifer | oai:union.ndltd.org:WATERLOO/oai:uwspace.uwaterloo.ca:10012/6101 |
| Date | January 2011 |
| Creators | Young, Maxwell |
| Source Sets | University of Waterloo Electronic Theses Repository |
| Language | English |
| Detected Language | English |
| Type | Thesis or Dissertation |
Page generated in 0.002 seconds