Mistaking friends for foes: An analysis of a social network-based Sybil defense in mobile networks

Abedelaziz Mohaisen, Tamer AbuHmed, Hun Jeong Kang, Yongdae Kim, Dae Hun Nyang

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

3 Scopus citations

Abstract

The Sybil attack is very challenging in the context of distributed systems; Sybil nodes with multiple identities try to deviate the behavior of the overall system from normal behavior. Recently, there have been a lot of interests in social-network based Sybil defenses weighing the trust in social networks to detect Sybil nodes. Such defenses use some algorithmic properties relating to the topological structure of the social networks. However, the use of those properties without validating them in realistic settings makes their applicability impossible in the real-world applications. In this paper, we discuss such inapplicability by analyzing MobID, a recently proposed defense for mobile environments which claims that existing defenses have largely been designed for peer-to-peer networks. MobID uses the betweenness, a graph-theoretic property in the social graph, as a metric of the goodness of nodes in order to defend against the Sybil attacks. By using this betweenness, MobID operates on two fundamental assumptions: i) highly enmeshed nodes in the social graphs have a nonzero betweenness, and ii) verifiers and suspects in an honest social graph have common friends. However, extensive experiments and detailed analysis with real-world social network traces show that these assumptions do not hold well. Accordingly, MobID does not work for a great portion of the network, which is in some cases greater than 50% of the network size, even when not using a threshold on the betweenness. By setting a very low, highly-precise threshold of the betweenness (e.g., less than 10-4), we observe a dramatic loss in the performance of MobID, which corresponds to 8%-30% overall acceptance rates of honest nodes (and the remaining nodes are rejected). On the other hand, we observe that existing work, as well as other recently proposed work that is based on the community structure, can be used as an alternative for Sybil defenses in the same context.

Original languageEnglish
Title of host publicationProceedings of the 5th International Conference on Ubiquitous Information Management and Communication, ICUIMC 2011
DOIs
StatePublished - 2011
Event5th International Conference on Ubiquitous Information Management and Communication, ICUIMC 2011 - Seoul, Korea, Republic of
Duration: 21 Feb 201123 Feb 2011

Publication series

NameProceedings of the 5th International Conference on Ubiquitous Information Management and Communication, ICUIMC 2011

Conference

Conference5th International Conference on Ubiquitous Information Management and Communication, ICUIMC 2011
Country/TerritoryKorea, Republic of
CitySeoul
Period21/02/1123/02/11

Keywords

  • Betweenness
  • Measurement
  • Mobile networks
  • Social networks
  • Sybil defenses

Fingerprint

Dive into the research topics of 'Mistaking friends for foes: An analysis of a social network-based Sybil defense in mobile networks'. Together they form a unique fingerprint.

Cite this