Social Networks Meet Distributed Systems: Towards a Robust Sybil Defense under Churn

Nitin Chiluka, Nazareno Andrade, Johan Pouwelse, Henk Sips

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

3 Citations (Scopus)

Abstract

This paper examines the impact of heavy churn on the robustness of decentralized social network-based Sybil defense (SNSD) schemes. Our analysis reveals that (i) heavy churn disintegrates the social overlay network that is fundamental to these schemes into multiple disconnected components, resulting in poor network connectivity, and (ii) a naive solution that adds links from each node to all its 2-hop neighbors improves network connectivity but comes at a significant cost of poor attack resilience of these schemes.

We propose a new design point in the trade-off between network connectivity and attack resilience of SNSD schemes, where each node adds links to only a selective few of all its 2-hop neighbors based on a minimum expansion contribution (MinEC) heuristic. Extensive evaluation through simulations shows that our approach fares as good as the naive 2-hop solution in terms of network connectivity, while making little compromise on the attack resilience. Moreover, our approach preserves the fast-mixing property that is fundamental to many SNSD schemes even at high levels of churn. This result suggests that existing and potential future SNSD schemes relying on this property can incorporate our approach into their designs with minimal changes.
Original languageEnglish
Title of host publicationASIA CCS'15
Subtitle of host publicationProceedings of the 10th ACM Symposium on Information, Computer and Communications Security
Place of PublicationNew York, NY
PublisherAssociation for Computing Machinery (ACM)
Pages507-518
Number of pages12
ISBN (Print)978-1-4503-3245-3
DOIs
Publication statusPublished - 1 Apr 2015
EventASIA CCS 2015: The 10th ACM Symposium on Information, Computer and Communications Security - Singapore, Singapore
Duration: 14 Apr 201517 Apr 2015
Conference number: 10th

Conference

ConferenceASIA CCS 2015
CountrySingapore
CitySingapore
Period14/04/1517/04/15

Keywords

  • Social overlay network
  • Churn
  • Sybil attack

Fingerprint Dive into the research topics of 'Social Networks Meet Distributed Systems: Towards a Robust Sybil Defense under Churn'. Together they form a unique fingerprint.

Cite this