Integro: Leveraging victim prediction for robust fake account detection in large scale OSNs

Detecting fake accounts in online social networks (OSNs) protects both OSN operators and their users from various malicious activities. Most detection mechanisms attempt to classify user accounts as real (i.e., benign, honest) or fake (i.e., malicious, Sybil) by analyzing either 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. In this article, we show that victims real accounts whose users have accepted friend requests sent by fakes form a distinct classification category that is useful for designing robust detection mechanisms. In particular, we present Integro - a robust and scalable defense system that leverages victim classification to rank most real accounts higher than fakes, so that OSN operators can take actions against low-ranking fake accounts. fntegro starts by identifying potential victims from user-level activities using supervised machine learning. After that, it annotates the graph by assigning lower weights to edges incident to potential victims. Finally, fntegro ranks user accounts based on the landing probability of a short random walk that starts from a known real account. As this walk is unlikely to traverse low-weight edges in a few steps and land on fakes, fntegro achieves the desired ranking. We implemented fntegro using widely-used, open-source distributed computing platforms, where it scaled nearly linearly. We evaluated fntegro against SybilRank, which is 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 with more than 15 million active users. We show that fntegro significantly outperforms SybilRank in user ranking quality, with the only requirement that the employed victim classifier is better than random. Moreover, the deployment of fntegro at Tuenti resulted in up to an order of magnitude higher precision in fake account detection, as compared to SybilRank. (C) 2016 Elsevier Ltd. All rights reserved.