Yang Zhang (CISPA Helmholtz Center for Information Security), Mathias Humbert (armasuisse Science and Technology), Bartlomiej Surma (CISPA Helmholtz Center for Information Security), Praveen Manoharan (CISPA Helmholtz Center for Information Security), Jilles Vreeken (CISPA Helmholtz Center for Information Security), Michael Backes (CISPA Helmholtz Center for Information Security)

Social graphs derived from online social interactions contain a wealth of information that is nowadays extensively used by both industry and academia. However, as social graphs contain sensitive information, they need to be properly anonymized before release. Most of the existing graph anonymization mechanisms rely on the perturbation of the original graph’s edge set. In this paper, we identify a fundamental weakness of these mechanisms: They neglect the strong structural proximity between friends in social graphs, thus add implausible fake edges for anonymization.
To exploit this weakness, we first propose a metric to quantify an edge’s plausibility by relying on graph embedding. Extensive experiments on three real-life social network datasets demonstrate that our plausibility metric can very effectively differentiate fake edges from original edges with AUC values above 0.95 in most of the cases. We then rely on a Gaussian mixture model to automatically derive the threshold on the edge plausibility values to determine whether an edge is fake, which enables us to recover to a large extent the original graph from the anonymized graph. Then, we demonstrate that our graph recovery attack jeopardizes the privacy guarantees provided by the considered graph anonymization mechanisms.
To mitigate this vulnerability, we propose a method to generate fake yet plausible edges given the graph structure and incorporate it into the existing anonymization mechanisms. Our evaluation demonstrates that the enhanced mechanisms decrease the chances of graph recovery, reduce the success of graph de-anonymization (up to 30%), and provide even better utility than the existing anonymization mechanisms.

View More Papers

When Match Fields Do Not Need to Match: Buffered...

Jiahao Cao (Tsinghua University; George Mason University), Renjie Xie (Tsinghua University), Kun Sun (George Mason University), Qi Li (Tsinghua University),...

Read More

Finding Safety in Numbers with Secure Allegation Escrows

Venkat Arun (Massachusetts Institute of Technology), Aniket Kate (Purdue University), Deepak Garg (Max Planck Institute for Software Systems), Peter Druschel...

Read More

TKPERM: Cross-platform Permission Knowledge Transfer to Detect Overprivileged Third-party...

Faysal Hossain Shezan (University of Virginia), Kaiming Cheng (University of Virginia), Zhen Zhang (Johns Hopkins University), Yinzhi Cao (Johns Hopkins...

Read More

HYPER-CUBE: High-Dimensional Hypervisor Fuzzing

Sergej Schumilo (Ruhr-Universität Bochum), Cornelius Aschermann (Ruhr-Universität Bochum), Ali Abbasi (Ruhr-Universität Bochum), Simon Wörner (Ruhr-Universität Bochum), Thorsten Holz (Ruhr-Universität Bochum)

Read More