A Two-Stage Deanonymization Attack against Anonymized Social Networks
Authors:
- 20 August 2012
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 63 (2) , 290-303
Abstract
Digital traces left by users of online social networking services, even after anonymization, are susceptible to privacy breaches. This is exacerbated by the increasing overlap in user-bases among various services. To alert fellow researchers in both the academia and the industry to the feasibility of such an attack, we propose an algorithm, Seed-and-Grow, to identify users from an anonymized social graph, based solely on graph structure. The algorithm first identifies a seed subgraph, either planted by an attacker or divulged by a collusion of a small group of users, and then grows the seed larger based on the attacker's existing knowledge of the users' social relations. Our work identifies and relaxes implicit assumptions taken by previous works, eliminates arbitrary parameters, and improves identification effectiveness and accuracy. Simulations on real-world collected data sets verify our claim.Keywords
This publication has 28 references indexed in Scilit:
- An analysis of social network-based Sybil defensesACM SIGCOMM Computer Communication Review, 2010
- A brief survey on anonymization techniques for privacy preserving publishing of social network dataACM SIGKDD Explorations Newsletter, 2008
- Resisting structural re-identification in anonymized social networksProceedings of the VLDB Endowment, 2008
- Statistical properties of community structure in large social and information networks2008
- Measurement and analysis of online social networks2007
- Wherefore art thou r3579x?2007
- SybilGuardACM SIGCOMM Computer Communication Review, 2006
- Preferential attachment growth model and nonextensive statistical mechanicsEurophysics Letters, 2005
- Reactive Tabu Search for Measuring Graph Similarity2005
- The Sybil Attack2002