  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 being not scalable.
  In this work, we aim to overcome these drawbacks. Towards 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.
