Sybil Defense For Online Social Networks Using Partial Graph Information

Abstract

Online social networks (OSNs) today are proprietary, in the sense that communication between users requires the users to be part of the same OSN. This raises privacy issues and reliability concerns among users, and calls for an open, interoperable, and distributed OSN infrastructure that is similar to email and would link different OSNs together. Any decentralized system, however, is vulnerable to Sybil attacks, in which an attacker claims multiple identities, called Sybils, to overwhelm the OSNs and defeat standard techniques used to protect against attacks such as message spam. The state of the art defense against these attacks is SybilInfer, which utilizes the fast mixing property of social networks to distinguish between Sybil nodes and honest nodes. SybilInfer, however, assumes a centralized system with a complete view of the social network. In this thesis, we investigate the effectiveness of applying SybilInfer on open and decentralized networks, and we propose improvements that would make SybilInfer deployable in such a scenario. These improvements facilitate a user of one OSN to listen to messages from other users of another OSN without the fear of spam due to a Sybil attack. We show that the proposed improvements greatly reduce the number of Sybil nodes misclassified as honest users and make SybilInfer more accurate in classifying members of other OSNs.