  Detecting fake users (also called Sybils) in online social networks is a
basic security research problem. State-of-the-art approaches rely on a large
amount of manually labeled users as a training set. These approaches suffer
from three key limitations: 1) it is time-consuming and costly to manually
label a large training set, 2) they cannot detect new Sybils in a timely
fashion, and 3) they are vulnerable to Sybil attacks that leverage information
of the training set. In this work, we propose SybilBlind, a structure-based
Sybil detection framework that does not rely on a manually labeled training
set. SybilBlind works under the same threat model as state-of-the-art
structure-based methods. We demonstrate the effectiveness of SybilBlind using
1) a social network with synthetic Sybils and 2) two Twitter datasets with real
Sybils. For instance, SybilBlind achieves an AUC of 0.98 on a Twitter dataset.
