Change of Guard: The Next Generation of Social Graph De-anonymization Attacks

Abstract

Past decade has seen active research in social graph de-anonymization with a variety of algorithms proposed. Previous algorithms used handcrafted tricks and were locked in a co-evolution of attack and defense with design of anonymization systems. We present a radically improved algorithm for re-identifying social network data. We use a machine learning system based on random forests to identify nodes using their structural features. The algorithm can handle a variety of threat models and is agnostic to the de-anonymization scheme employed. This is substantiated by our evaluation using three real-world social graph datasets under four threat models. Our algorithm is consistently better than the previous generation of algorithms as confirmed by comparison with seven seed-based and seedless attacks based on two real-world social networks. It is time for attacks based on heuristics to be replaced by learning models.

Publication
In Workshop on Artificial Intelligence and Security (AISec). Vienna, Austria.
Date
Links

Bibtex

@inproceedings{Sharad:2016:CGN:2996758.2996763,
author = {Sharad, Kumar},
title = {Change of Guard: The Next Generation of Social Graph De-anonymization Attacks},
booktitle = {Proceedings of the 2016 ACM Workshop on Artificial Intelligence and Security},
series = {AISec '16},
year = {2016},
isbn = {978-1-4503-4573-6},
location = {Vienna, Austria},
pages = {105--116},
numpages = {12},
url = {http://doi.acm.org/10.1145/2996758.2996763},
doi = {10.1145/2996758.2996763},
acmid = {2996763},
publisher = {ACM},
address = {New York, NY, USA},
keywords = {de-anonymization, machine learning, privacy, social networks},
}