Structural Data De-anonymization: Quantification, Practice, and Implications
Structural Data De-anonymization: Quantification, Practice, and Implications
复制标题
DOI：
10.1145/2660267.2660278
复制
发表时间：
2014-11
期刊：
影响因子：
--
通讯作者：
S. Ji;Weiqing Li;M. Srivatsa;R. Beyah
中科院分区：
文献类型：
--
作者：
S. Ji;Weiqing Li;M. Srivatsa;R. Beyah
在本文中，我们研究了结构数据的量化、实践和含义（例如，社会数据、移动轨迹）去Anchorization（DA）。首先，我们通过量化完美和（1-ε）-完美结构数据DA}来解决结构数据DA中的几个公开问题，其中ε是DA方案所容许的误差。据我们所知，这是第一个量化结构数据DA下的一般数据模型，它关闭结构数据DA实践和理论之间的差距的工作。其次，我们对26个真实的世界结构数据集进行了首次大规模的去匿名性研究，包括社交网络（SN），协作网络，通信网络，自治系统和对等网络。我们还定量地给出了26个数据集的完美和（1-ε）-完美DA的条件。第三，在定量分析的基础上，设计了一种实用新颖的单相冷起动优化DA（ODA）算法。ODA的实验分析表明，Gowalla中约有77.7% - 83.3%的用户（0.2M用户和1 M边缘）和Google+中约有86.9% - 95.5%的用户（4.7M用户和90.8M边缘）在不同场景下是可去匿名的，这意味着基于优化的DA在实践中是可实现的和强大的。最后，我们讨论了我们的DA量化和ODA的影响，并为未来的安全数据发布提供了一些一般性的建议。
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.