NESA SecGraph

USENIX Security 2015 Paper Abstract

In this paper, we analyze and systematize the state-of-the-art graph data privacy and utility techniques. Specifically, we propose and develop ShareSafe, a uniform and open-source Secure Graph data sharing/publishing system. In ShareSafe, we systematically study, implement, and evaluate 11 graph data anonymization algorithms, 19 data utility metrics, and 15 modern Structure-based De-Anonymization (SDA) attacks. To the best of our knowledge, ShareSafe is the first such system that enables data owners to anonymize data by state-of-the-art anonymization techniques, measure the data’s utility, and evaluate the data’s vulnerability against modern De-Anonymization (DA) attacks. In addition, ShareSafe enables researchers to conduct fair analysis and evaluation of existing and newly developed anonymization/DA techniques. Leveraging SecGraph, we conduct extensive experiments to systematically evaluate the existing graph data anonymization and DA techniques. The results demonstrate that (i) most anonymization schemes can partially or conditionally preserve most graph utilities while losing some application utility; (ii) no DA attack is optimum in all scenarios. The DA performance depends on several factors, e.g., similarity between anonymized and auxiliary data, graph density, and DA heuristics; and (iii) all the state-of-theart anonymization schemes are vulnerable to several or all of the modern SDA attacks. The degree of vulnerability of each anonymization scheme depends on how much and which data utility it preserves.

Paper available on USENIX Security 2015 [Slides]

NDSS 2015 Paper Abstract

In this paper, we conduct the first comprehensive quantification on the perfect de-anonymizability and partial de-anonymizability of real world social networks with seed information in general scenarios, where a social network can follow an arbitrary distribution model. This quantification provides the theoretical foundation for existing structure based de-anonymization attacks and closes the gap between de-anonymization practice and theory. Besides that, our quantification can serve as a testing-stone for the effectiveness of anonymization techniques, i.e., researchers can employ our quantified structural conditions to evaluate the potential de-anonymizability of the anonymized social networks. Based on our quantification, we conduct a large scale evaluation on the de-anonymizability of 24 various real world social networks by quantitatively 1) the conditions for perfect and (1-ε) de-anonymization of a social network, where ε specifies the tolerated de-anonymization error, and 2) the number of users of a social network that can be successfully de-anonymized. Furthermore, we show that, both theoretically and experimentally, the overall structural information based de-anonymization attack is much more powerful than the seed knowledge-only based de-anonymization attack, and even without any seed information, a social network can be perfectly or partially de-anonymized. Finally, we discuss the implications of this work. Our findings are expected to shed light on the future research in the structural data anonymization and de-anonymization area, and to help data owners evaluate their structural data vulnerability before data sharing and publishing.

Paper available on NDSS 2015 [Slides]

CCS 2014 Abstract

In this paper, we study the quantification, practice, and implications of structural data (e.g., social data, mobility traces) De-Anonymization (DA). First, we address several open problems in structural data DA by quantifying perfect and (1 − ε) -perfect structural data DA, where εis the error tolerated by a DA scheme. To the best of our knowledge, this is the first work on quantifying structural data DA under a general data model, which closes the gap between structural data DA practice and theory. Second, we conduct the first large-scale study on the de-anonymizability of 26 real world structural datasets, including Social Networks(SNs), Collaborations Networks, Communication Networks, Autonomous Systems, and Peer-to-Peer networks. We also quantitatively show the conditions for perfect and (1− ε)- perfect DA of the 26 datasets. Third, following our quantification, we design a practical and novel single-phase cold start Optimization based DA (ODA) algorithm. Experimental analysis of ODA shows that about 77.7%−83.3% of the users in Gowalla (.2M users and 1M edges) and 86.9%− 95.5% of the users in Google+ (4.7M users and 90.8M edges) are de-anonymizable in different scenarios, which implies optimization based DA is implementable and powerful in practice. Finally, we discuss the implications of our DA quantification and ODA and provide some general suggestions for future secure data publishing.

Paper available on CCS 2014 [Slides]

ISC 2014 Abstract

We present a novel de-anonymization attack on mobility trace data and social data. First, we design an Unified Similarity (US) measurement, based on which we present a US based De-Anonymization (DA) framework which iteratively de-anonymizes data with an accuracy guarantee. Then, to de-anonymize data without the knowledge of the overlap size between the anonymized data and the auxiliary data, we generalize DA to an Adaptive De-Anonymization (ADA) framework. Finally, we examine DA/ADA on mobility traces and social data sets.

Paper available on ISC 2014 [Slides]