GULYÁS, Gábor György, Ph.D.

Blog

Our new paper at WPES 2016: a highly efficient social network de-anonymization attack

2016-11-22 | Gabor

Back to the archives

We have a new paper on a quite efficient social network de-anonymization attack, and I had the chance to present it at WPES’16, which was held in conjunction with CCS’16. In fact, it is not just an efficient attack, but the most efficient one up to date. (TLDR: see the plots below.)

It is even more interesting, how we got there: in the paper we argue that the similarity measure is a critical part of these attacks. We propose a new similarity measure which is intuitively more balanced than the state-of-the-art up to the date (Nar; find the paper here), and provably better in some cases. We call the resulting new attack Bumblebee, or Blb in short.

We benchmarked the performance of Bumblebee in the style of a recent USENIX survey that compared the elite of the attacks by simulation. This paper included scenarios with naive anonymization (only identifiers were removed from the data) and also with specific social network anonymization techniques which mess up the structure of the graph, too.

Below you can see our results. In order to maintain comparability, we’ve selected graph data, anonymization techniques, de-anonymization attacks and all parameters just as they were put in the USENIX survey. Figure 1 shows results with naive anonymization. In almost all cases our attack managed to re-identify the largest set of users. When it did not, other attacks did a quite poor job (regarding precision): while they provided a larger set of correct re-identification mappings, these were garbled with a very large amount of erroneous mappings (such as 1:1 or worse).

This was also what we observed in case of attacking anonymization schemes, as results shown on Figure 2. Here we used F1 scores for the simlicity of presentation. This metric is calculated based on both recall and precision:

Last, but not least, we have also released a framework for social network re-identification, called SALab. Where you can try out the attack yourself under many settings, and you can also compare it to others.

Our results in case of naive anonymization. In this case, no specific anonymization is applied; however, the background knowledge of the attacker is not perfect (this is the sampling probability). Results of our proposal is denoted with red.

Fig. 1. Our results in case of naive anonymization. In this case, no specific anonymization is applied; however, the background knowledge of the attacker is not perfect (this is the sampling probability). Results of our proposal is denoted with red. [source]

Our results against different anonymization techniques. F1-score values of our proposal is denoted with red.

Fig. 2. Our results against different anonymization techniques. F1-score values of our proposal is denoted with red. [source]

Tags: social network, re-identification, de-anonymization, code

Back to the archives

Blog tagcloud

CSP (1), Content-Security-Policy (1), ad industry (1), adblock (1), ads (1), advertising wars (1), amazon (1), announcement (1), anonymity (9), anonymity measure (2), anonymity paradox (3), anonymity set (1), boundary (1), bug (2), code (1), control (1), crawling (1), data privacy (1), data retention (1), data surveillance (1), de-anonymization (2), definition (1), demo (1), device fingerprint (2), device identifier (1), disposable email (1), ebook (1), el capitan (1), email privacy (1), encryption (1), end (1), extensions (1), fairness (1), false-beliefs (1), fingerprint (3), fingerprint blocking (1), fingerprinting (3), firefox (1), firegloves (1), font (1), future of privacy (2), google (1), google glass (1), home (1), hungarian keyboard layout (1), inkscape (1), interesting paper (1), internet measurement (1), keys (1), kmap (1), latex (1), location guard (1), location privacy (1), logins (1), mac (1), machine learning (3), neural networks (1), nsa (2), osx (2), paper (2), pet symposium (2), plot (1), price of privacy (1), prism (1), privacy (8), privacy enhancing technology (1), privacy-enhancing technologies (2), privacy-enhancing technology (1), profiling (2), projects (1), raising awareness (1), rationality (1), re-identification (1), simulation (1), social network (2), surveillance (2), tbb (1), thesis contest (1), tor (1), tracemail (1), tracking (12), tracking cookie (1), transparency (1), tresorit blog (4), uniqueness (3), visualization (1), web bug (3), web privacy (3), web security (1), web tracking (3), win (1), you are the product (1)

Gábor György Gulyás, PhD – © 2018 all rights reserved