SybilBelief: A semi-supervised learning approach for structure-based sybil detection

Neil Zhenqiang Gong, Mario Frank, Prateek Mittal

Research output: Contribution to journalArticlepeer-review

137 Scopus citations


Sybil attacks are a fundamental threat to the security of distributed systems. Recently, there has been a growing interest in leveraging social networks to mitigate Sybil attacks. However, the existing approaches suffer from one or more drawbacks, including bootstrapping from either only known benign or known Sybil nodes, failing to tolerate noise in their prior knowledge about known benign or Sybil nodes, and not being scalable. In this paper, we aim to overcome these drawbacks. Toward this goal, we introduce SybilBelief, a semi-supervised learning framework, to detect Sybil nodes. SybilBelief takes a social network of the nodes in the system, a small set of known benign nodes, and, optionally, a small set of known Sybils as input. Then, SybilBelief propagates the label information from the known benign and/or Sybil nodes to the remaining nodes in the system. We evaluate SybilBelief using both synthetic and real-world social network topologies. We show that SybilBelief is able to accurately identify Sybil nodes with low false positive rates and low false negative rates. SybilBelief is resilient to noise in our prior knowledge about known benign and Sybil nodes. Moreover, SybilBelief performs orders of magnitudes better than existing Sybil classification mechanisms and significantly better than existing Sybil ranking mechanisms.

Original languageEnglish (US)
Article number6787042
Pages (from-to)976-987
Number of pages12
JournalIEEE Transactions on Information Forensics and Security
Issue number6
StatePublished - Jun 2014

All Science Journal Classification (ASJC) codes

  • Safety, Risk, Reliability and Quality
  • Computer Networks and Communications


  • Markov random fields
  • Sybil detection
  • belief propagation
  • semi-supervised learning


Dive into the research topics of 'SybilBelief: A semi-supervised learning approach for structure-based sybil detection'. Together they form a unique fingerprint.

Cite this