nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Defend the Clique-based Attack for Data Privacy

verfasst von : Meng Han, Dongjing Miao, Jinbao Wang, Liyuan Liu

Erschienen in: Combinatorial Optimization and Applications

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Clique, as the most compact cohesive component in a graph, has been employed to identify cohesive subgroups of entities and explore the sensitive information in the online social network, crowdsourcing network, and cyber physical network, etc. In this study, we focus on the defense of clique-based attack and target at reducing the risk of entities security/privacy issues in clique structure. Since the ultimate resolution for defending the clique-based attack and risk is wrecking the clique with minimum cost, we establish the problem of clique-destroying (CD) in the network from a fundamental algorithm aspect. Interestingly, we notice that the clique-destroying problem in the directed graph is still an unsolved problem, and complexity analysis also does not exist. Therefore, we propose an innovative formal clique-destroying problem and proof the NP-complete problem complexity with solid theoretical analysis, then present effective and efficient algorithms for both undirected and directed graph. Furthermore, we show how to extend our algorithm to data privacy protection applications with controllable parameter k, which could adjust the size of a clique we wish to destroy. By comparing our algorithm with the up-to-date anonymization approaches, the real data experiment demonstrates that our resolution could efficaciously defend the clique-based security and privacy attacks.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Practical and Easy-to-Understand Card-Based Implementation of Yao’s Millionaire Protocol

Nächstes Kapitel Exact Computation of Strongly Connected Reliability by Binary Decision Diagrams

Zhang, J., Li, Q., Schooler, E.M.: iHEMS: an information-centric approach to secure home energy management. In: 2012 IEEE Third International Conference on Smart Grid Communications (SmartGridComm), pp. 217–222. IEEE (2012)

Aberer, K., Alonso, G., Kossmann, D.: Data management for a smart earth: the swiss NCCR-MICS initiative. ACM SIGMOD Rec. 35(4), 40–45 (2006)CrossRef

Perera, C., Zaslavsky, A., Christen, P., Georgakopoulos, D.: Context aware computing for the internet of things: a survey. IEEE Commun. Surv. Tutor. 16(1), 414–454 (2014)CrossRef

Liang, Y., Cai, Z., Han, Q., Li, Y.: Location privacy leakage through sensory data. Secur. Commun. Netw. 2017, 1–12 (2017)CrossRef

Zheng, X., Cai, Z., Li, J., Gao, H.: Location-privacy-aware review publication mechanism for local business service systems. In: INFOCOM 2017-IEEE Conference on Computer Communications, pp. 1–9. IEEE (2017)

He, Z., Cai, Z., Yu, J., Wang, X., Sun, Y., Li, Y.: Cost-efficient strategies for restraining rumor spreading in mobile social networks. IEEE Trans. Veh. Technol. 66(3), 2789–2800 (2017)CrossRef

Narayanan, A., Shmatikov, V.: De-anonymizing social networks. In: 2009 30th IEEE Symposium on Security and Privacy, pp. 173–187. IEEE (2009)

Potharaju, R., Carbunar, B., Nita-Rotaru, C.: iFriendU: leveraging 3-cliques to enhance infiltration attacks in online social networks. In: Proceedings of the 17th ACM Conference on Computer and Communications Security. ACM (2010) 723–725

Gulyás, G.G., Simon, B., Imre, S.: An efficient and robust social network de-anonymization attack. In: Proceedings of the 2016 ACM on Workshop on Privacy in the Electronic Society, pp. 1–11. ACM (2016)

10.

Dwork, C.: Differential privacy: a survey of results. In: Agrawal, M., Du, D., Duan, Z., Li, A. (eds.) TAMC 2008. LNCS, vol. 4978, pp. 1–19. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-79228-4_1CrossRefMATH

11.

Niu, B., Li, Q., Zhu, X., Cao, G., Li, H.: Achieving k-anonymity in privacy-aware location-based services. In: 2014 Proceedings IEEE INFOCOM, pp. 754–762. IEEE (2014)

12.

Shokri, R., Shmatikov, V.: Privacy-preserving deep learning. In: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, pp. 1310–1321. ACM (2015)

13.

Dalenius, T.: Towards a methodology for statistical disclosure control. Statistik Tidskrift 15, 429–444 (1977)

14.

Dwork, C., Naor, M.: On the difficulties of disclosure prevention in statistical databases or the case for differential privacy. J. Priv. Confid. 2(1), 8 (2008)

15.

Yannakakis, M.: Edge-deletion problems. SIAM J. Comput. 10(2), 297–309 (1981)MathSciNetCrossRef

16.

Sweeney, L.: k-anonymity: a model for protecting privacy. Int. J. Uncertain. Fuzziness Knowl. Based Syst. 10(05), 557–570 (2002)MathSciNetCrossRef

17.

Dwork, C., Roth, A., et al.: The algorithmic foundations of differential privacy. Found. Trends® Theor. Comput. Sci. 9(3–4), 211–407 (2014)MathSciNetMATH

18.

Acquisti, A., Brandimarte, L., Loewenstein, G.: Privacy and human behavior in the age of information. Science 347(6221), 509–514 (2015)CrossRef

19.

Young, A.L., Quan-Haase, A.: Privacy protection strategies on facebook: the internet privacy paradox revisited. Inf. Commun. Soc. 16(4), 479–500 (2013)CrossRef

20.

Bettini, C., Riboni, D.: Privacy protection in pervasive systems: state of the art and technical challenges. Pervasive Mob. Comput. 17, 159–174 (2015)CrossRef

21.

Zhao, J., Liu, J., Qin, Z., Ren, K.: Privacy protection scheme based on remote anonymous attestation for trusted smart meters. IEEE Trans. Smart Grid 9, 3313–3320 (2016)CrossRef

22.

Naor, M., Nissim, K.: Communication preserving protocols for secure function evaluation. In: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, pp. 590–599. ACM (2001)

23.

Goldwasser, S.: Multi party computations: past and present. In: Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing, pp. 1–6. ACM (1997)

24.

Han, M., Li, J., Cai, Z., Han, Q.: Privacy reserved influence maximization in GPS-enabled cyber-physical and online social networks. In: 2016 IEEE International Conferences on Big Data and Cloud Computing (BDCloud), Social Computing and Networking (SocialCom), Sustainable Computing and Communications (SustainCom) (BDCloud-SocialCom-SustainCom), pp. 284–292. IEEE (2016)

25.

Albinali, H., Han, M., Wang, J., Gao, H., Li, Y.: The roles of social network mavens. In: 2016 12th International Conference on Mobile Ad-Hoc and Sensor Networks (MSN), pp. 1–8. IEEE (2016)

26.

Cai, Z., Zheng, X.: A private and efficient mechanism for data uploading in smart cyber-physical systems. IEEE Trans. Netw. Sci. Eng. (2018)

27.

Zheng, X., Luo, G., Cai, Z.: A fair mechanism for private data publication in online social networks. IEEE Trans. Netw. Sci. Eng. (2018)

28.

Li, J., Cai, Z., Wang, J., Han, M., Li, Y.: Truthful incentive mechanisms for geographical position conflicting mobile crowdsensing systems. IEEE Trans. Comput. Soc. Syst. 5(2), 324–334 (2018)CrossRef

29.

Han, M., Wang, J., Yan, M., Ai, C., Duan, Z., Hong, Z.: Near-complete privacy protection: cognitive optimal strategy in location-based services. Procedia Comput. Sci. 129, 298–304 (2018)CrossRef

30.

Ling, X., Wu, C., Ji, S., Han, M.: H\(_{2}\)DoS: an application-layer DoS attack towards HTTP/2 protocol. In: Lin, X., Ghorbani, A., Ren, K., Zhu, S., Zhang, A. (eds.) SecureComm 2017. LNICST, vol. 238, pp. 550–570. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78813-5_28CrossRef

31.

Han, M., Li, L., Peng, X., Hong, Z., Li, M.: Information privacy of cyber transportation system: opportunities and challenges. In: Proceedings of the 6th Annual Conference on Research in Information Technology, pp. 23-28. ACM (2017). https://dl.acm.org/citation.cfm?id=31256

32.

Zheng, X., Cai, Z., Yu, J., Wang, C., Li, Y.: Follow but no track: privacy preserved profile publishing in cyber-physical social systems. IEEE Internet Things J. 4(6), 1868–1878 (2017)CrossRef

33.

Zhou, Y., Han, M., Liu, L., He, J.S., Wang, Y.: Deep learning approach for cyberattack detection. In: IEEE INFOCOM 2018-IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), pp. 262–267. IEEE (2018)

34.

Han, M., Duan, Z., Li, Y.: Privacy issues for transportation cyber physical systems. In: Sun, Y., Song, H. (eds.) Secure and Trustworthy Transportation Cyber-Physical Systems. SCS, pp. 67–86. Springer, Singapore (2017). https://doi.org/10.1007/978-981-10-3892-1_4CrossRef

35.

Joshi, A.P., Han, M., Wang, Y.: A survey on security and privacy issues of blockchain technology. Math. Found. Comput. 1(2), 121–147 (2018)CrossRef

36.

Liu, L., Han, M., Wang, Y., Zhou, Y.: Understanding data breach: a visualization aspect. In: Chellappan, S., Cheng, W., Li, W. (eds.) WASA 2018. LNCS, vol. 10874, pp. 883–892. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-94268-1_81CrossRef

37.

Liang, Y., Cai, Z., Yu, J., Han, Q., Li, Y.: Deep learning based inference of private information using embedded sensors in smart devices. IEEE Netw. 32(4), 8–14 (2018)CrossRef

38.

Wang, J., Cai, Z., Li, Y., Yang, D., Li, J., Gao, H.: Protecting query privacy with differentially private k-anonymity in location-based services. Pers. Ubiquit. Comput. 22, 1–17 (2018)CrossRef

39.

Dwork, C.: A firm foundation for private data analysis. Commun. ACM 54(1), 86–95 (2011)CrossRef

40.

Dwork, C., Rothblum, G.N., Vadhan, S.: Boosting and differential privacy. In: 2010 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 51–60. IEEE (2010)

41.

Chaudhuri, K., Monteleoni, C.: Privacy-preserving logistic regression. In: Advances in Neural Information Processing Systems pp. 289–296 (2009)

42.

Chaudhuri, K., Sarwate, A., Sinha, K.: Near-optimal differentially private principal components. In: Advances in Neural Information Processing Systems, pp. 989–997 (2012)

43.

Sarwate, A.D., Chaudhuri, K.: Signal processing and machine learning with differential privacy: algorithms and challenges for continuous data. IEEE Sig. Process. Mag. 30(5), 86–94 (2013)CrossRef

44.

Ho, S.S., Ruan, S.: Differential privacy for location pattern mining. In: Proceedings of the 4th ACM SIGSPATIAL International Workshop on Security and Privacy in GIS and LBS, pp. 17–24. ACM (2011)

45.

Dewri, R.: Local differential perturbations: location privacy under approximate knowledge attackers. IEEE Trans. Mob. Comput. 12(12), 2360–2372 (2013)CrossRef

46.

Xiao, Y., Xiong, L.: Protecting locations with differential privacy under temporal correlations. In: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, pp. 1298–1309. ACM (2015)

47.

Yildiz, H., Kruegel, C.: Detecting social cliques for automated privacy control in online social networks. In: 2012 IEEE International Conference on Pervasive Computing and Communications Workshops (PERCOM Workshops), pp. 353–359. IEEE (2012)

48.

Pan, X., Xu, J., Meng, X.: Protecting location privacy against location-dependent attacks in mobile services. IEEE Trans. Knowl. Data Eng. 24(8), 1506–1519 (2012)CrossRef

49.

Narayanan, A., Shi, E., Rubinstein, B.I.: Link prediction by de-anonymization: How we won the Kaggle social network challenge. In: The 2011 International Joint Conference on Neural Networks (IJCNN), pp. 1825–1834. IEEE (2011)

50.

Srivatsa, M., Hicks, M.: Deanonymizing mobility traces: using social network as a side-channel. In: Proceedings of the 2012 ACM Conference on Computer and Communications Security, pp. 628–637. ACM (2012)

51.

Ji, S., Li, W., Srivatsa, M., He, J.S., Beyah, R.: Structure based data de-anonymization of social networks and mobility traces. In: Chow, S.S.M., Camenisch, J., Hui, L.C.K., Yiu, S.M. (eds.) ISC 2014. LNCS, vol. 8783, pp. 237–254. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-13257-0_14CrossRef

52.

Gulyás, G.G., Imre, S.: Analysis of identity separation against a passive clique-based de-anonymization attack. Infocommunications J. 4(3), 11–20 (2011)

53.

Niedermeier, R.: Invitation to Fixed-parameter Algorithms (2006)CrossRef

54.

Brügmann, D., Komusiewicz, C., Moser, H.: On generating triangle-free graphs. Electron. Notes Discret. Math. 32, 51–58 (2009)MathSciNetCrossRef

55.

Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations, pp. 85–103. Springer, Heidelberg (1972). https://doi.org/10.1007/978-1-4684-2001-2_9CrossRef

56.

Yang, J., Leskovec, J.: Defining and evaluating network communities based on ground-truth. Knowl. Inf. Syst. 42(1), 181–213 (2015)CrossRef

57.

Leskovec, J., Lang, K.J., Dasgupta, A., Mahoney, M.W.: Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters. Internet Math. 6(1), 29–123 (2009)MathSciNetCrossRef

58.

Leskovec, J., Mcauley, J.J.: Learning to discover social circles in ego networks. In: Advances in Neural Information Processing Systems, pp. 539–547 (2012)

59.

Richardson, M., Agrawal, R., Domingos, P.: Trust management for the semantic web. In: Fensel, D., Sycara, K., Mylopoulos, J. (eds.) ISWC 2003. LNCS, vol. 2870, pp. 351–368. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-39718-2_23CrossRef

60.

Leskovec, J., Huttenlocher, D., Kleinberg, J.: Predicting positive and negative links in online social networks. In: Proceedings of the 19th International Conference on World Wide Web, pp. 641–650. ACM (2010)

61.

Leskovec, J., Huttenlocher, D., Kleinberg, J.: Signed networks in social media. In: Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, pp. 1361–1370. ACM (2010)

62.

Ji, S., Li, W., Mittal, P., Hu, X., Beyah, R.A.: SecGraph: a uniform and open-source evaluation system for graph data anonymization and de-anonymization. In: USENIX Security Symposium, pp. 303–318 (2015)

63.

Ying, X., Wu, X.: Randomizing social networks: a spectrum preserving approach. In: Proceedings of the 2008 SIAM International Conference on Data Mining, pp. 739–750. SIAM (2008)

64.

Liu, K., Terzi, E.: Towards identity anonymization on graphs. In: Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, pp. 93–106. ACM (2008)

65.

Sala, A., Zhao, X., Wilson, C., Zheng, H., Zhao, B.Y.: Sharing graphs using differentially private graph models. In: Proceedings of the 2011 ACM SIGCOMM Conference on Internet Measurement Conference, pp. 81–98. ACM (2011)

66.

Yartseva, L., Grossglauser, M.: On the performance of percolation graph matching. In: Proceedings of the First ACM Conference on Online Social Networks, pp. 119–130. ACM (2013)

Titel: Defend the Clique-based Attack for Data Privacy
verfasst von: Meng Han
Dongjing Miao
Jinbao Wang
Liyuan Liu
Verlag: Springer International Publishing
Buch: Combinatorial Optimization and Applications
Print ISBN: 978-3-030-04650-7

Electronic ISBN: 978-3-030-04651-4

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-030-04651-4_18

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"