SybilShield: An agent-aided social network-based Sybil defense among multiple communities

Lu Shi, Shucheng Yu, Wenjing Lou, Y. Thomas Hou

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

47 Scopus citations

Abstract

Lacking trusted central authority, distributed systems have received serious security threats from Sybil attack, where an adversary forges identities of more than one node and attempts to control the system. By utilizing the real-world trust relationships between users, social network-based defense schemes have been proposed to mitigate the impact of Sybil attacks. These solutions are mostly built on the assumption that the social network graph can be partitioned into two loosely linked regions - a tightly connected non-Sybil region and a Sybil region. Although such an assumption may hold in certain settings, studies have shown that the real-world social connections tend to divide users into multiple inter-connected small worlds instead of a single uniformly connected large region. Given this fact, the applicability of existing schemes would be greatly undermined for inability to distinguish Sybil users from valid ones in the small non-Sybil regions. This paper addresses this problem and presents SybilShield, the first protocol that defends against Sybil attack utilizing multicommunity social network structure in real world. Our scheme leverages the sociological property that the number of cutting edges between a non-Sybil community and a Sybil community, which represent human-established trust relationships, is much smaller than that among non-Sybil communities. With the help of agent nodes, SybilShield greatly reduces false positive rate of non-Sybils among multiple communities, while effectively identifying Sybil nodes. Analytical results prove the superiority of SybilShield. Our experiments on a real-world social network graph with 100,000 nodes also validate the effectiveness of SybilShield.

Original languageEnglish
Title of host publication2013 Proceedings IEEE INFOCOM 2013
Pages1034-1042
Number of pages9
DOIs
StatePublished - 2013
Event32nd IEEE Conference on Computer Communications, IEEE INFOCOM 2013 - Turin, Italy
Duration: 14 Apr 201319 Apr 2013

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X

Conference

Conference32nd IEEE Conference on Computer Communications, IEEE INFOCOM 2013
Country/TerritoryItaly
CityTurin
Period14/04/1319/04/13

Fingerprint

Dive into the research topics of 'SybilShield: An agent-aided social network-based Sybil defense among multiple communities'. Together they form a unique fingerprint.

Cite this