More Web Proxy on the site http://driver.im/

research-article

SybilCast: Broadcast on the Open Airwaves

Authors:

Chaodong ZhengAuthors Info & Claims

ACM Transactions on Parallel Computing (TOPC), Volume 2, Issue 3

Article No.: 16, Pages 1 - 20

https://doi.org/10.1145/2809810

Published: 08 September 2015 Publication History

Abstract

Consider a scenario where many wireless users are attempting to download data from a single base station. While most of the users are honest, some users may be malicious and attempt to obtain more than their fair share of the bandwidth. One possible strategy for attacking the system is to simulate multiple fake identities, each of which is given its own equal share of the bandwidth. Such an attack is often referred to as a sybil attack. To counter such behavior, we propose SybilCast, a protocol for multichannel wireless networks that limits the number of fake identities and, in doing so, ensures that each honest user gets at least a constant fraction of his or her fair share of the bandwidth. As a result, each honest user can complete his or her data download in asymptotically optimal time. A key aspect of this protocol is balancing the rate at which new identities are admitted and the maximum number of fake identities that can coexist while keeping the overhead low. Besides sybil attacks, our protocol can also tolerate spoofing and jamming.

References

[1]

Baruch Awerbuch, Andrea Richa, and Christian Scheideler. 2008. A jamming-resistant MAC protocol for single-hop wireless networks. In Proceedings of the 27th ACM Symposium on Principles of Distributed Computing. 45--54.

Digital Library

[2]

Sanjoy K. Baruah, Neil K. Cohen, C. Greg Plaxton, and Donald A. Varvel. 1996. Proportionate progress: A notion of fairness in resource allocation. Algorithmica 15, 6, 600--625.

Digital Library

[3]

Todd Bishop. 2010. Here it comes: “Super WiFi.” http://www.bizjournals.com/seattle/blog/techflash/2010/09/here_it_comes _super_wifi.html.

[4]

Bluetooth Consortium. 2007. Bluetooth Specification Version 2.1. Bluetooth Consortium.

[5]

Shlomi Dolev, Seth Gilbert, Rachid Guerraoui, Fabian Kuhn, and Calvin Newport. 2009. The wireless synchronization problem. In Proceedings of the 28th ACM Symposium on Principles of Distributed Computing. 190--199.

Digital Library

[6]

John Douceur. 2002. The sybil attack. In Peer-to-Peer Systems. Lecture Notes in Computer Science, Vol. 2429. Springer, 251--260.

Digital Library

[7]

Cheng Tien Ee and Ruzena Bajcsy. 2004. Congestion control and fairness for many-to-one routing in sensor networks. In Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems. 148--161.

Digital Library

[8]

Kevin Hoffman, David Zage, and Cristina Nita-Rotaru. 2009. A survey of attack and defense techniques for reputation systems. Computer Surveys 42, 1 (December 2009), 1--31.

Digital Library

[9]

Xiao Long Huang and Brahim Bensaou. 2001. On max-min fairness and scheduling in wireless Ad-Hoc networks: Analytical framework and implementation. In Proceedings of the 2nd ACM International Symposium on Mobile Ad-Hoc Networking & Computing. 221--231.

Digital Library

[10]

Raj Jain, Dah-Ming Chiu, and William R. Hawe. 1984. A quantitative measure of fairness and discrimination for resource allocation in shared computer systems. Technical Report, DEC-TR-301. Digital Equipment Corporation.

[11]

Newso James, Elaine Shi, Dawn Song, and Adrian Perrig. 2004. The sybil attack in sensor networks: Analysis & defenses. In Proceedings of the 3rd International Symposium on Information Processing in Sensor Networks. 259--268.

Digital Library

[12]

Michael George Luby. 1996. Pseudorandomness and Cryptographic Applications. Princeton University Press.

Digital Library

[13]

Dominic Meier, Yvonne Anne Pignolet, Stefan Schmid, and Roger Wattenhofer. 2009. Speed dating despite jammers. In Proceedings of the 5th IEEE International Conference on Distributed Computing in Sensor Systems. 1--14.

Digital Library

[14]

Diogo Mónica. 2009. Thwarting the Sybil Attack in Wireless Ad-Hoc Networks. Master’s thesis. Instituto Superior Técnico, Universidade Técnica de Lisboa.

[15]

Diogo Mónica, Joao Leitao, Luis Rodrigues, and Carlos Ribeiro. 2009. On the use of radio resource tests in wireless ad-hoc networks. In Proceedings of the 3rd Workshop on Recent Advances on Intrusion-Tolerant Systems. F21--F26.

[16]

Diogo Mónica, Joao Leitao, Luis Rodrigues, and Carlos Ribeiro. 2010. Observable non-sybil quorums construction in one-hop wireless Ad Hoc networks. In Proceedings of the 40th Annual IEEE/IFIP International Conference on Dependable Systems and Networks.

[17]

Thyagarajan Nandagopal, Tae Eun Kim, Xia Gao, and Vaduvur Bharghavan. 2000. Achieving MAC layer fairness in wireless packet networks. In Proceedings of the 6th Annual International Conference on Mobile Computing and Networking. ACM, 87--98.

Digital Library

[18]

Saar Pilosof, Ramachandran Ramjee, Danny Raz, Yuval Shavitt, and Prasun Sinha. 2003. Understanding TCP fairness over wireless LAN. In 22nd Annual Joint Conference of the IEEE Computer and Communications, Vol. 2. 863--872.

[19]

Andrea Richa, Christian Scheideler, Stefan Schmid, and Jin Zhang. 2011. Competitive and fair medium access despite reactive jamming. In Proceedings of the 31st International Conference on Distributed Computing Systems. 507--516.

Digital Library

[20]

Andrea Richa, Christian Scheideler, Stefan Schmid, and Jin Zhang. 2012. Competitive and fair throughput for co-existing networks under adversarial interference. In Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing. 291--300.

Digital Library

[21]

Mario Strasser, Christina Pöpper, Srdjan Capkun, and Mario Cagalj. 2008. Jamming-resistant key establishment using uncoordinated frequency hopping. In Proceedings of the IEEE Symposium on Security and Privacy. 64--78.

Digital Library

[22]

Haifeng Yu, Phillip B. Gibbons, Michael Kaminsky, and Feng Xiao. 2008. SybilLimit: A near-optimal social network defense against sybil attacks. In Proceedings of the IEEE Symposium on Security and Privacy. 3--17.

Digital Library

[23]

Philip R. Zimmermann. 1995. The Official PGP User’s Guide. MIT Press.

Digital Library

Cited By

Anderton WChakraborty TYoung M(2021)Windowed backoff algorithms for WiFi: theory and performance under batched arrivalsDistributed Computing10.1007/s00446-021-00403-934:5(367-393)Online publication date: 1-Oct-2021
https://dl.acm.org/doi/10.1007/s00446-021-00403-9
Anantharamu LChlebus BKowalski DRokicki M(2019)Packet latency of deterministic broadcasting in adversarial multiple access channelsJournal of Computer and System Sciences10.1016/j.jcss.2018.07.00199(27-52)Online publication date: Feb-2019
https://doi.org/10.1016/j.jcss.2018.07.001

Index Terms

SybilCast: Broadcast on the Open Airwaves
1. Networks
  1. Network types
    1. Mobile networks
    2. Wireless access networks

Recommendations

SybilCast: broadcast on the open airwaves (extended abstract)
SPAA '13: Proceedings of the twenty-fifth annual ACM symposium on Parallelism in algorithms and architectures

Consider a scenario where many wireless users are attempting to download data from a single base station. While most of the users are honest, some users may be malicious and attempt to obtain more than their fair share of the bandwidth. One possible ...
SybilGuard: defending against sybil attacks via social networks
SIGCOMM '06: Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications

Peer-to-peer and other decentralized,distributed systems are known to be particularly vulnerable to sybil attacks. In a sybil attack,a malicious user obtains multiple fake identities and pretends to be multiple, distinct nodes in the system. By ...
SybilGuard: defending against sybil attacks via social networks
Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications

Peer-to-peer and other decentralized,distributed systems are known to be particularly vulnerable to sybil attacks. In a sybil attack,a malicious user obtains multiple fake identities and pretends to be multiple, distinct nodes in the system. By ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Parallel Computing

ACM Transactions on Parallel Computing Volume 2, Issue 3

Special Issue for SPAA 2013

October 2015

196 pages

ISSN:2329-4949

EISSN:2329-4957

DOI:10.1145/2821462

Editor:
Phillip B. Gibbons
Intel Labs, Pittsburgh, USA

Issue’s Table of Contents

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 September 2015

Accepted: 01 March 2015

Revised: 01 September 2014

Received: 01 October 2013

Published in TOPC Volume 2, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
143
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)1

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Anderton WChakraborty TYoung M(2021)Windowed backoff algorithms for WiFi: theory and performance under batched arrivalsDistributed Computing10.1007/s00446-021-00403-934:5(367-393)Online publication date: 1-Oct-2021
https://dl.acm.org/doi/10.1007/s00446-021-00403-9
Anantharamu LChlebus BKowalski DRokicki M(2019)Packet latency of deterministic broadcasting in adversarial multiple access channelsJournal of Computer and System Sciences10.1016/j.jcss.2018.07.00199(27-52)Online publication date: Feb-2019
https://doi.org/10.1016/j.jcss.2018.07.001

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents