Author(s): Yazan Boshmaf, Dionysios Logothetis, Georgos Siganos, Jorge Lería, Jose Lorenzo, Matei Ripeanu, Konstantin Beznosov

Download: Paper (PDF)

Date: 7 Feb 2015

Document Type: Briefing Papers

Additional Documents: Slides

Associated Event: NDSS Symposium 2015


Detecting fake accounts in online social networks (OSNs) protects OSN operators and their users from various malicious activities. Most detection mechanisms attempt to predict and classify user accounts as real (i.e., benign, honest) or fake (i.e., malicious, Sybil) by analyzing user-level activities or graph-level structures. These mechanisms, however, are not robust against adversarial attacks in which fake accounts cloak their operation with patterns resembling real user behavior.

We herein demonstrate that victims, benign users who control real accounts and have befriended fakes, form a distinct classification category that is useful for designing robust detection mechanisms. First, as attackers have no control over victim accounts and cannot alter their activities, a victim account classifier which relies on user-level activities is relatively harder to circumvent. Second, as fakes are directly connected to victims, a fake account detection mechanism that integrates victim prediction into graph-level structures is more robust against manipulations of the graph.

To validate this new approach, we designed Integro, a scalable defense system that helps OSNs detect fake accounts using a meaningful a user ranking scheme. Integro starts by predicting victim accounts from user-level activities. After that, it integrates these predictions into the graph as weights, so that edges incident to predicted victims have much lower weights than others. Finally, Integro ranks user accounts based on a modified random walk that starts from a known real account. Integro guarantees that most real accounts rank higher than fakes so that OSN operators can take actions against low-ranking fake accounts.

We implemented Integro using widely-used, open-source distributed computing platforms in which it scaled nearly linearly. We evaluated Integro against SybilRank, the state-of-the-art in fake account detection, using real-world datasets and a large-scale deployment at Tuenti, the largest OSN in Spain. We show that Integro significantly outperforms SybilRank in user ranking quality, where the only requirement is to employ a victim classifier is better than random. Moreover, the deployment of Integro at Tuenti resulted in up to an order of magnitude higher precision in fake accounts detection, as compared to SybilRank.