StarClique: Guaranteeing User Privacy in Social Networks Against Intersection Attacks
Krishna P. N. Puttaswamy
Alessandra Sala
Ben Y. Zhao
ACM Conference on emerging Networking EXperiments and Technologies (CoNEXT 2009)
[Full Text in PDF Format, 328KB]
[Full Text in Compressed
Postscript Format, 290KB]
Paper Abstract
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 credentials 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 privacy 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 locally 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
correctness of our approach using analysis. Finally, using experiments
driven by traces from the del.icio.us social bookmark site, we
demonstrate the practicality and effectiveness of our approach on
real-world systems.