StarClique: guaranteeing user privacy in social networks against intersection attacks

Building on the popularity of online social networks (OSNs) such as Facebook, social content-sharing applications allow users to form communities around shared interests. Millions of users worldwide use them to share recommendations on everything from music and books to resources on the web. However, their increasing popularity is beginning to attract the attention of malicious attackers. As social network cre-dentials become valued targets of phishing attacks and social worms, attackers look to leverage compromised accounts for further financial gain. In this paper, we analyze the state of privacy protection in social content-sharing applications, describe effective pri-vacy attacks against today’s social networks, and propose anonymization techniques to protect users. We show that simple protection mechanisms such as anonymizing shared data can still leave users open to social intersection attacks, where a small number of compromised users can identify the originators of shared content. Modeling this as a graph anonymization problem, we propose to provide users with k-anonymity privacy guarantees by augmenting the social graph with “latent edges. ” We identify StarClique, a lo-cally minimal graph structure required for users to attain k-anonymity, where at worst, a user is identified as one of k possible contributors of a data object. We prove the correct-ness of our approach using detailed analysis. Finally, using detailed experiments driven by traces from the del.icio.us so-cial bookmark site, we demonstrate the practicality and ef-fectiveness of our approach on real-world systems. 1