Of malicious motes and suspicious sensors
How efficiently can a malicious device disrupt a single-hop wireless network? Imagine two honest players attempting to exchange information in the presence of a malicious adversary that can disrupt communication by jamming or overwriting messages. Assume the adversary has a broadcast budget of β—unk...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Elsevier
2015
|
| Online Access: | http://hdl.handle.net/1721.1/96286 |
| _version_ | 1826202964497268736 |
|---|---|
| author | Gilbert, Seth Guerraoui, Rachid Newport, Calvin Charles |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Gilbert, Seth Guerraoui, Rachid Newport, Calvin Charles |
| author_sort | Gilbert, Seth |
| collection | MIT |
| description | How efficiently can a malicious device disrupt a single-hop wireless network? Imagine two honest players attempting to exchange information in the presence of a malicious adversary that can disrupt communication by jamming or overwriting messages. Assume the adversary has a broadcast budget of β—unknown to the honest players. We show that communication can be delayed for 2β+Θ(lg|V|) rounds, where V is the set of values that the honest players may transmit. We then derive, via reduction to this 3-player game, round complexity lower bounds for several classical nn-player problems: 2β+Ω(lg|V| for reliable broadcast, 2β+Ω(logn) for leader election, and 2β+Ω(klg|V| [over k]) for static k-selection. We also consider an extension of our adversary model that includes up to t crash failures. Here we show a bound of 2β+Θ(t) rounds for binary consensus. We provide tight, or nearly tight, upper bounds for all four problems. From these results we can derive bounds on the efficiency of malicious disruption, stated in terms of two new metrics: jamming gain (the ratio of rounds delayed to adversarial broadcasts) and disruption-free complexity (the rounds required to terminate in the special case of no disruption). Two key conclusions of this study: (1) all the problems considered feature semantic vulnerabilities that allow an adversary to disrupt termination more efficiently than simple jamming (i.e., all have a jamming gain greater than 1); and (2) for all the problems considered, the round complexity grows linearly with the number of bits to be communicated (i.e., all have a Ω(lg|V|) or Ω(lgn) disruption-free complexity.) |
| first_indexed | 2024-09-23T12:28:42Z |
| format | Article |
| id | mit-1721.1/96286 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:28:42Z |
| publishDate | 2015 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | mit-1721.1/962862022-10-01T09:15:16Z Of malicious motes and suspicious sensors Gilbert, Seth Guerraoui, Rachid Newport, Calvin Charles Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Newport, Calvin Charles How efficiently can a malicious device disrupt a single-hop wireless network? Imagine two honest players attempting to exchange information in the presence of a malicious adversary that can disrupt communication by jamming or overwriting messages. Assume the adversary has a broadcast budget of β—unknown to the honest players. We show that communication can be delayed for 2β+Θ(lg|V|) rounds, where V is the set of values that the honest players may transmit. We then derive, via reduction to this 3-player game, round complexity lower bounds for several classical nn-player problems: 2β+Ω(lg|V| for reliable broadcast, 2β+Ω(logn) for leader election, and 2β+Ω(klg|V| [over k]) for static k-selection. We also consider an extension of our adversary model that includes up to t crash failures. Here we show a bound of 2β+Θ(t) rounds for binary consensus. We provide tight, or nearly tight, upper bounds for all four problems. From these results we can derive bounds on the efficiency of malicious disruption, stated in terms of two new metrics: jamming gain (the ratio of rounds delayed to adversarial broadcasts) and disruption-free complexity (the rounds required to terminate in the special case of no disruption). Two key conclusions of this study: (1) all the problems considered feature semantic vulnerabilities that allow an adversary to disrupt termination more efficiently than simple jamming (i.e., all have a jamming gain greater than 1); and (2) for all the problems considered, the round complexity grows linearly with the number of bits to be communicated (i.e., all have a Ω(lg|V|) or Ω(lgn) disruption-free complexity.) 2015-03-31T17:44:45Z 2015-03-31T17:44:45Z 2008-10 Article http://purl.org/eprint/type/JournalArticle 03043975 http://hdl.handle.net/1721.1/96286 Gilbert, Seth, Rachid Guerraoui, and Calvin Newport. “Of Malicious Motes and Suspicious Sensors.” Theoretical Computer Science 410, no. 6–7 (February 2009): 546–569. © 2008 Elsevier B.V. en_US http://dx.doi.org/10.1016/j.tcs.2008.10.008 Theoretical Computer Science Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Elsevier Elsevier |
| spellingShingle | Gilbert, Seth Guerraoui, Rachid Newport, Calvin Charles Of malicious motes and suspicious sensors |
| title | Of malicious motes and suspicious sensors |
| title_full | Of malicious motes and suspicious sensors |
| title_fullStr | Of malicious motes and suspicious sensors |
| title_full_unstemmed | Of malicious motes and suspicious sensors |
| title_short | Of malicious motes and suspicious sensors |
| title_sort | of malicious motes and suspicious sensors |
| url | http://hdl.handle.net/1721.1/96286 |
| work_keys_str_mv | AT gilbertseth ofmaliciousmotesandsuspicioussensors AT guerraouirachid ofmaliciousmotesandsuspicioussensors AT newportcalvincharles ofmaliciousmotesandsuspicioussensors |