An Analysis of Social Network-based Sybil Defenses

Recently, there has been much excitement in the research
community over using social networks to mitigate multiple
identity, or Sybil, attacks. A number of schemes have been
proposed, but they differ greatly in the algorithms they use
and in the networks upon which they are evaluated. As a
result, the research community lacks a clear understanding
of how these schemes compare against each other, how well
they would work on real-world social networks with different
structural properties, or whether there exist other (poten-
tially better) ways of Sybil defense.
In this paper, we show that, despite their considerable dif-
ferences, existing Sybil defense schemes work by detecting
local communities (i.e., clusters of nodes more tightly knit
than the rest of the graph) around a trusted node. Our
finding has important implications for both existing and fu-
ture designs of Sybil defense schemes. First, we show that
there is an opportunity to leverage the substantial amount
of prior work on general community detection algorithms in
order to defend against Sybils. Second, our analysis reveals
the fundamental limits of current social network-based Sybil
defenses: We demonstrate that networks with well-defined
community structure are inherently more vulnerable to Sybil
attacks, and that, in such networks, Sybils can carefully tar-
get their links in order make their attacks more effective.