[en] Active re-identification attacks constitute a serious threat to privacy-preserving social graph publication, because of the ability of active adversaries to leverage fake accounts, a.k.a. sybil nodes, to enforce structural patterns that can be used to re-identify their victims on anonymised graphs. Several formal privacy properties have been enunciated with the purpose of characterising the resistance of a graph against active attacks. However, anonymisation methods devised on the basis of these properties have so far been able to address only restricted special cases, where the adversaries are assumed to leverage a very small number of sybil nodes. In this paper, we present a new probabilistic interpretation of active re-identification attacks on social graphs. Unlike the aforementioned privacy properties, which model the protection from active adversaries as the task of making victim nodes indistinguishable in terms of their fingerprints with respect to all potential attackers, our new formulation introduces a more complete view, where the attack is countered by jointly preventing the attacker from retrieving the set of sybil nodes, and from using these sybil nodes for re-identifying the victims. Under the new formulation, we show that k-symmetry, a privacy property introduced in the context of passive attacks, provides a sufficient condition for the protection against active re-identification attacks leveraging an arbitrary number of sybil nodes. Moreover, we show that the algorithm K-Match, originally devised for efficiently enforcing the related notion of k-automorphism, also guarantees k-symmetry. Empirical results on real-life and synthetic graphs demonstrate that our formulation allows, for the first time, to publish anonymised social graphs (with formal privacy guarantees) that effectively resist the strongest active re-identification attack reported in the literature, even when it leverages a large number of sybil nodes.
Disciplines :
Sciences informatiques
Auteur, co-auteur :
MAUW, Sjouke ; University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Computer Science (DCS)
RAMIREZ CRUZ, Yunior ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > PI Mauw
TRUJILLO RASUA, Rolando ; Universitat Rovira i Virgili > Department of Computer Sciences and Mathematics
Co-auteurs externes :
yes
Langue du document :
Anglais
Titre :
Preventing active re-identification attacks on social graphs via sybil subgraph obfuscation
FNR11685812 - Privacy-preserving Publication Of Dynamic Social Network Data In The Presence Of Active Adversaries, 2017 (01/06/2018-31/05/2021) - Yunior Ramirez-cruz
Abawajy JH, Ninggal MIH, Herawan T (2016) Privacy preserving social network data publication. IEEE Commun Surveys Tutor 18(3):1974–1997 DOI: 10.1109/COMST.2016.2533668
Backstrom L, Dwork C, Kleinberg J (2007) Wherefore art thou r3579x?: Anonymized social networks, hidden patterns, and structural steganography. In: Proceedings of the 16th international conference on world wide web, pp. 181–190, New York, NY, USA
Barabási A, Albert R (1999) Emergence of scaling in random networks. Science 286(5439):509–512
Bonchi F, Gionis A, Tassa T (2014) Identity obfuscation in graphs through the information theoretic lens. Inf Sci 275:232–256 DOI: 10.1016/j.ins.2014.02.035
Casas-Roma J, Herrera-Joancomartí J, Torra V (2013) An algorithm for k-degree anonymity on large networks. In: Proceedings of the 2013 IEEE/ACM international conference on advances in social networks analysis and mining, pp. 671–675
Casas-Roma J, Herrera-Joancomartí Jordi, Torra V (2017) k-degree anonymity and edge selection: improving data utility in large networks. Knowl Inf Syst 50(2):447–474 DOI: 10.1007/s10115-016-0947-7
Casas-Roma Jordi, Herrera-Joancomartí Jordi, Torra Vicenç (2017) A survey of graph-modification techniques for privacy-preserving on networks. Artif Intell Rev 47(3):341–366 DOI: 10.1007/s10462-016-9484-8
Chen B-C, LeFevre K, Ramakrishnan R (2007) Privacy skyline: privacy with multidimensional adversarial knowledge. In: Proceedings of the 33rd international conference on very large data bases, VLDB ’07, pp. 770–781. VLDB Endowment
Chen X, Këpuska E, Mauw S, Ramírez-Cruz Y (2020) Active re-identification attacks on periodically released dynamic social graphs. In Computer Security – ESORICS 2020, volume 12309 of Lecture Notes in Computer Science, pp. 185–205. Springer
Chen X, Mauw S, Ramírez-Cruz Y (2020) Publishing community-preserving attributed social graphs with a differential privacy guarantee. Proc Privacy Enhancing Technol 4:2020
Cheng J, Wai-chee FA, Liu J (2010) K-isomorphism: privacy preserving network publication against structural attacks. In: Proceedings of the 2010 ACM SIGMOD international conference on management of data, pp. 459–470
Chester S, Kapron BM, Ramesh G, Srivastava G, Thomo A, Venkatesh S (2013) Why Waldo befriended the dummy? k-anonymization of social networks with pseudo-nodes. Social Netw Anal Min 3(3):381–399 DOI: 10.1007/s13278-012-0084-6
Dwork C, Roth A (2014) The algorithmic foundations of differential privacy. Found Trends Theor Comput Sci 9(3–4):211–407
Erdős P, Rényi A (1959) On random graphs. Publicationes Mathematicae Debrecen 6:290–297
Evfimievski A, Gehrke J, Srikant R (2003) Limiting privacy breaches in privacy preserving data mining. In: Proceedings of the Twenty-second ACM SIGMOD-SIGACT-SIGART symposium on principles of database systems, PODS ’03, pp. 211–222, New York, NY, USA, ACM
Feder T, Nabar SU, Terzi E (2008) Anonymizing graphs
Guimera R, Danon L, Diaz-Guilera A, Giralt F, Arenas A (2003) Self-similar community structure in a network of human interactions. Phys Rev E 68(6):065103 DOI: 10.1103/PhysRevE.68.065103
Hay M, Li C, Miklau G, Jensen DD (2009) Accurate estimation of the degree distribution of private networks. In: Proceedings 19th IEEE international conference on data mining (ICDM), pp. 169–178. IEEE Computer Society
Ji S, Li W, Mittal P, Hu X, Beyah R (2015) Secgraph: a uniform and open-source evaluation system for graph data anonymization and de-anonymization. In: Proceedings of the 24th USENIX security symposium, pp. 303–318, Washington DC, USA
Jorgensen Z, Yu T, Cormode G (2016) Publishing attributed social graphs with formal privacy guarantees. In: Proceedings of the 2016 international conference on management of data, pp. 107–122
Karwa V, Raskhodnikova S, Smith AD, Yaroslavtsev G (2014) Private analysis of graph structure. ACM Trans Database Syst 39(3):1–33 DOI: 10.1145/2611523
Karwa V, Slavković AB (2012) Differentially private graphical degree sequences and synthetic graphs. In: Proceedings of the international conference on privacy in statistical databases, pp. 273–285
Karypis George, Kumar V (1998) A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J Sci Comput 20(1):359–392 DOI: 10.1137/S1064827595287997
Li N, Li T, Venkatasubramanian S (2007) t-closeness: privacy beyond k-anonymity and l-diversity. In: Proceedings of the 23rd International conference on data engineering, ICDE 2007, The Marmara Hotel, Istanbul, Turkey, April 15-20, 2007, pp. 106–115
Liu K, Terzi E (2008) Towards identity anonymization on graphs. In: Proceedings of the 2008 ACM SIGMOD international conference on management of data, pp. 93–106, New York, NY, USA
Lu X, Song Y, Bressan S (2012) Fast identity anonymization on graphs. In: Proceedings of the international conference on database and expert systems applications, pp. 281–295
Ma T, Zhang Y, Cao J, Shen J, Tang M, Tian Y, Al-Dhelaan A, Al-Rodhaan M (2015) Kdvem: a k-degree anonymity with vertex and edge modification algorithm. Computing 97(12):1165–1184 DOI: 10.1007/s00607-015-0453-x
Machanavajjhala A, Gehrke J, Götz M (2009) Data publishing against realistic adversaries. Proc VLDB Endow 2(1):790–801 DOI: 10.14778/1687627.1687717
Martin DJ, Kifer D, Machanavajjhala A, Gehrke J, Halpern JY (2007) Worst-case background knowledge for privacy-preserving data publishing. In: Proceedings of the 23rd international conference on data engineering, ICDE 2007, The Marmara Hotel, Istanbul, Turkey, April 15-20, 2007, pp. 126–135
Mauw S, Ramírez-Cruz Y, Trujillo-Rasua R (2018) Anonymising social graphs in the presence of active attackers. Trans Data Privacy 11(2):169–198
Mauw Sjouke, Ramírez-Cruz Yunior, Trujillo-Rasua Rolando (2019) Conditional adjacency anonymity in social graphs under active attacks. Knowl Inf Syst 61(1):485–511 DOI: 10.1007/s10115-018-1283-x
Mauw S, Ramírez-Cruz Y, Trujillo-Rasua R (2019) Robust active attacks on social graphs. Data Mining Knowl Discov 33(5):1357–1392 DOI: 10.1007/s10618-019-00631-5
Mauw S, Trujillo-Rasua R, Xuan B (2016) Counteracting active attacks in social network graphs. In: Proceedings of DBSec 2016, vol. 9766 of Lecture Notes in Computer Science, pp. 233–248
Mir DJ, Wright RN (2009) A differentially private graph estimator. In: Proceedings 2009 ICDM international workshop on privacy aspects of data mining (ICDM), pages 122–129. IEEE Computer Society
Narayanan A, Shmatikov V (2009) De-anonymizing social networks. In: Proceedings of the 30th IEEE symposium on security and privacy, pp. 173–187
Panzarasa Pietro, Opsahl Tore, Carley Kathleen M (2009) Patterns and dynamics of users’ behavior and interaction: network analysis of an online community. J Assoc Inf Sci Technol 60(5):911–932 DOI: 10.1002/asi.21015
Peng W, Li F, Zou X, Wu J (2012) Seed and grow: an attack against anonymized social networks. In: Proceedings of the 9th Annual IEEE communications society conference on sensor, mesh and Ad Hoc communications and networks, pp. 587–595
Peng Wei, Li F, Zou X, Jie W (2014) A two-stage deanonymization attack against anonymized social networks. IEEE Trans Comput 63(2):290–303 DOI: 10.1109/TC.2012.202
Rousseau F, Casas-Roma Jordi, Vazirgiannis M (2017) Community-preserving anonymization of graphs. Knowl Inf Syst 54(2):315–343 DOI: 10.1007/s10115-017-1064-y
Sala A, Zhao X, Wilson C, Zheng H, Zhao BY (2011) Sharing graphs using differentially private graph models. In: Proceedings of the 2011 ACM SIGCOMM conference on internet measurement, pp. 81–98
Salas J, Torra V (2015) Graphic sequences, distances and k-degree anonymity. Discr Appl Math 188:25–31 DOI: 10.1016/j.dam.2015.03.005
Salas Julián, Torra Vicenç (2020) Differentially private graph publishing and randomized response for collaborative filtering. Proc Secrypt 2020:407–414
Samarati Pierangela (2001) Protecting respondents’ identities in microdata release. IEEE Trans Knowl Data Eng 13(6):1010–1027
Stokes Klara, Torra V (2012) Reidentification and k-anonymity: a model for disclosure risk in graphs. Soft Comput 16(10):1657–1670 DOI: 10.1007/s00500-012-0850-4
Sweeney Latanya (2002) k-anonymity: a model for protecting privacy. Int J Uncertain Fuzz Knowl Based Syst 10(5):557–570 DOI: 10.1142/S0218488502001648
Rolando T-R, Ismael GY (2016) k-metric antidimension: a privacy measure for social graphs. Inf Sci 328:403–417 DOI: 10.1016/j.ins.2015.08.048
Varrette S, Bouvry P, Cartiaux H, Georgatos F (2014) Management of an academic HPC cluster: The UL experience. In: Proceedings of the 2014 International conference on high performance computing and simulation, pp. 959–967, Bologna, Italy
Wang Y, Xie L, Zheng B, Lee KCK (2014) High utility k-anonymization for social network publishing. Knowl Inf Syst 41(3):697–725 DOI: 10.1007/s10115-013-0674-2
Wang Yue, Xintao Wu (2013) Preserving differential privacy in degree-correlation based graph generation. Trans Data Privacy 6(2):127–145
Wu W, Xiao Y, Wang W, He Z, Wang Z (2010) K-symmetry model for identity anonymization in social networks. In: Proceedings of the 13th international conference on extending database technology, pp. 111–122
Xiao Q, Chen R, Tan K-L (2014) Differentially private network data release via structural inference. In: Proceedings 20th ACM SIGKDD international conference on knowledge discovery and data mining (KDD), pp. 911–920. ACM Press
Zhang J, Cormode G, Procopiuc CM, Srivastava D, Xiao X (2015) Private release of graph statistics using ladder functions. In: Proceedings of the 2015 ACM SIGMOD international conference on management of data, pp. 731–745
Zhou B, Pei J (2008) Preserving privacy in social networks against neighborhood attacks. In: Proceedings of the 2008 IEEE 24th international conference on data engineering, pp. 506–515, Washington, DC, USA
Zou L, Chen Lei, Tamer Özsu M (2009) K-automorphism: a general framework for privacy preserving network publication. Proc VLDB Endow 2(1):946–957 DOI: 10.14778/1687627.1687734
