- A common attack on Online Social Networks involves the creation of multiple accounts that do not correspond to real users.
06 April 2014: This malicious behavior is commonly referred to as the Sybil attack. Recent Sybil defenses for Online Social Networks use the observation that Sybils often have disproportionally few social connections to non-Sybil nodes. This is because although it is easy to automate the creation of OSN accounts, establishing a social connection between users implies trust that requires effort to build.
We propose SybilRank as an effective and efficient social-network-based Sybil detection mechanism for centralised OSNs. SybilRank models efficiently computable random walks over the social graph and modifies them such that they can reliably detect Sybil (fake) accounts. Our simulation results show that SybilRank has both lower false positive and negative rates compared to state-of- the-art solutions. Furthermore, we implemented a SybilRank prototype based on Hadoop. With only 11 commodity machines on Amazon EC2, our prototype can process a graph with 160 million nodes within 33 hours.
SybilRank has been successfully deployed on Tuenti, which is the largest Online Social Network in Spain, with approximately 11 million users. Due to the diversity of reasons behind the creation of Sybils in OSNs, automated (e.g., Machine- Learning-based) approaches have thus far failed to yield high detection rates and result in numerous false positives. Consequently, Tuenti and other OSNs are currently employing a manual account verification process, driven by user reports – a process that requires a significant amount of time, and that leads to only a very small fraction of all fake accounts to be identified. We put SybilRank in the hands of Tuenti engineers and have verified that more than 90% of the what SybilRank classifies as fake accounts are indeed fake. More importantly, our tool has allowed Tuenti operations to identify 20 times as many fake accounts, as opposed to the manual process they have been following thus far.
