Top

Journal of Combinatorial Optimization

Published in:

30-01-2020

A balm: defend the clique-based attack from a fundamental aspect

Authors: Meng Han, Dongjing Miao, Jinbao Wang, Liyuan Liu

Published in: Journal of Combinatorial Optimization | Issue 3/2022

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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 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.

previous article On the approximability of Time Disjoint Walks

next article Isolation branching: a branch and bound algorithm for the k-terminal cut problem

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

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

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

Albinali H, Han M, Wang J, Gao H, Li Y (2016) The roles of social network mavens. In: 2016 12th International conference on mobile ad-hoc and sensor networks (MSN). IEEE, pp 1–8

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

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

Cai Z, Zheng X (2018) A private and efficient mechanism for data uploading in smart cyber-physical systems. IEEE Trans Netw Sci Eng. https://doi.org/10.1109/TNSE.2018.2830307CrossRef

Cai Z, He Z (2019) Trading private range counting over big IoT data. In: 2019 IEEE 39th international conference on distributed computing systems (ICDCS). IEEE, pp 144–153

Cai Z, He Z, Guan X, Li Y (2016) Collective data-sanitization for preventing sensitive information inference attacks in social networks. IEEE Trans Dependable Secure Comput 15(4):577–590

Cai Z, Zheng X, Yu J (2019) A differential-private framework for urban traffic flows estimation via taxi companies. IEEE Trans Ind Inform 15(12):6492–6499CrossRef

Chaudhuri K, Monteleoni C (2009) Privacy-preserving logistic regression. In: Koller D, Schuurmans D, Bengio Y, Bottou L (eds) Advances in neural information processing systems, pp 289–296

Chaudhuri K, Sarwate A, Sinha K (2012) Near-optimal differentially private principal components. In: Pereira F, Burges CJC, Bottou L, Weinberger KQ (eds) Advances in neural information processing systems, pp 989–997

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

Dankar FK, El Emam K (2012) The application of differential privacy to health data. In: Proceedings of the 2012 joint EDBT/ICDT workshops. ACM, pp 158–166

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

Dwork C (2008) Differential privacy: a survey of results. In: International conference on theory and applications of models of computation. Springer, pp. 1–19

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

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

Dwork C, Rothblum GN, Vadhan S (2010) Boosting and differential privacy. In: 2010 51st Annual IEEE symposium on foundations of computer science (FOCS). IEEE, pp 51–60

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

Goldwasser S (1997) Multi party computations: past and present. In: Proceedings of the sixteenth annual ACM symposium on principles of distributed computing. ACM, pp 1–6

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

Gulyás GG, Simon B, Imre S (2016) An efficient and robust social network de-anonymization attack. In: Proceedings of the 2016 ACM on workshop on privacy in the electronic society. ACM, pp 1–11

Han M, Li J, Cai Z, Han Q (2016) Privacy reserved influence maximization in gps-enabled cyber-physical and online social networks. In: IEEE international conferences on social computing and networking (SocialCom). IEEE 2016, pp 284–292

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

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

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

Ji S, Li W, Srivatsa M, He JS, Beyah R (2014) Structure based data de-anonymization of social networks and mobility traces. In: International conference on information security. Springer, pp 237–254

Ji S, Li W, Mittal P, Hu X, Beyah RA (2015) Secgraph: a uniform and open-source evaluation system for graph data anonymization and de-anonymization. In: USENIX security symposium, pp 303–318

Ji S, Mittal P, Beyah R (2016) Graph data anonymization, de-anonymization attacks, and de-anonymizability quantification: a survey. IEEE Commun Surv Tutor 19(2):1305–1326CrossRef

Karp RM (1972) Reducibility among combinatorial problems. In: Miller RE, Thatcher JW, Bohlinger JD (eds) Complexity of computer computations. Springer, pp 85–103

Leskovec J, Mcauley JJ (2012) Learning to discover social circles in ego networks. In: Pereira F, Burges CJC, Bottou L, Weinberger KQ (eds) Advances in neural information processing systems (NIPS), pp 539–547

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

Leskovec J, Huttenlocher D, Kleinberg J (2010) Predicting positive and negative links in online social networks. In: Proceedings of the 19th international conference on world wide web. ACM, pp 641–650

Leskovec J, Huttenlocher D, Kleinberg J (2010) Signed networks in social media. In: Proceedings of the SIGCHI conference on human factors in computing systems. ACM, pp 1361–1370

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

Li K, Tian L, Li W, Luo G, Cai Z (2019) Incorporating social interaction into three-party game towards privacy protection in IoT. Computer Netw 150:90–101CrossRef

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

Liu K, Terzi E (2008) Towards identity anonymization on graphs. In: Proceedings of the 2008 ACM SIGMOD international conference on management of data. ACM, pp 93–106

Naor M, Nissim K (2001) Communication preserving protocols for secure function evaluation. In: Proceedings of the thirty-third annual ACM symposium on theory of computing. ACM, pp 590–599

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

Narayanan A, Shi E, Rubinstein BI (2011) Link prediction by de-anonymization: how we won the kaggle social network challenge. In: The 2011 international joint conference on neural networks (IJCNN). IEEE, pp 1825–1834

Niedermeier R (2006) Invitation to fixed-parameter algorithms. University Press, OxfordCrossRef

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

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

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

Potharaju R, Carbunar B, Nita-Rotaru C (2010) 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, pp 723–725

Richardson M, Agrawal R, Domingos P (2003) Trust management for the semantic web. Semant Web-ISWC 2003:351–368

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 conference. ACM, pp 81–98

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

Shokri R, Shmatikov V (2015) Privacy-preserving deep learning. In: Proceedings of the 22nd ACM SIGSAC conference on computer and communications security. ACM, pp 1310–1321

Srivatsa M, Hicks M (2012) Deanonymizing mobility traces: using social network as a side-channel. In: Proceedings of the 2012 ACM conference on computer and communications security. ACM, pp 628–637

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

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

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

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

Yartseva L, Grossglauser M (2013) On the performance of percolation graph matching. In: Proceedings of the first ACM conference on online social networks. ACM, pp 119–130

Yildiz H, Kruegel C (2012) Detecting social cliques for automated privacy control in online social networks. In: 2012 IEEE international conference on pervasive computing and communications workshops (PERCOM Workshops). IEEE, pp 353–359

Ying X, Wu X (2008) Randomizing social networks: a spectrum preserving approach. In: Proceedings of the 2008 SIAM international conference on data mining. SIAM, pp 739–750

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

Zhang J, Li Q, Schooler EM (2012) iHEMS: An information-centric approach to secure home energy management. In: 2012 IEEE third international conference on smart grid communications (SmartGridComm). IEEE, pp 217–222

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

Zheng X, Cai Z, Li Y (2018) Data linkage in smart internet of things systems: a consideration from a privacy perspective. IEEE Commun Magazine 56(9):55–61CrossRef

Zhou Y, Han M, Liu L, He JS, Wang Y (2018) Deep learning approach for cyberattack detection. In: IEEE INFOCOM 2018-IEEE conference on computer communications workshops (INFOCOM WKSHPS). IEEE, pp 262–267

Zhu S, Li W, Li H, Tian L, Luo G, Cai Z (2018) Coin hopping attack in blockchain-based IoT. IEEE Internet of Things Journal 6:4614–4626CrossRef

Title: A balm: defend the clique-based attack from a fundamental aspect
Authors: Meng Han
Dongjing Miao
Jinbao Wang
Liyuan Liu
Publication date: 30-01-2020
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 3/2022
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-020-00527-x

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 3/2022

Robustly assigning unstable items

Tighter price of anarchy for selfish task allocation on selfish machines

Online traveling salesman problem with time cost and non-zealous server

On the approximability of Time Disjoint Walks

Randomized selection algorithm for online stochastic unrelated machines scheduling

Algorithmic aspect on the minimum (weighted) doubly resolving set problem of graphs

Premium Partner