Please wait a minute...
J4  2009, Vol. 43 Issue (12): 2136-2141    DOI: 10.3785/j.issn.1008-973X.2009.12.002
Attacking algorithm against  k-anonymized continuous queries in location based service
LIN Xin1,2, LI Shan-ping1, YANG Zhao-hui1
(1. College of Computer Science and Technology, Zhejiang University, Hangzhou 310027, China;
2. Department of Computer Science and Technology, East China Normal University, Shanghai  200241, China)
Download:   PDF(951KB) HTML
Export: BibTeX | EndNote (RIS)      


K-anonymization cannot effectively protect anonymity of continuous queries in location-based service (LBS). A continuous query issuing model aimed at the problem was proposed. The model incorporated a query issuing interval model and a consecutive queries relationship model. An attacking algorithm aimed at the k-anonymization algorithm  was presented based on the model. The algorithm associated a series of snapshots related to continuous queries in order to calculate the probability of each user in the anonymity-set. Then the true query sender was identified by choosing the user with the highest probability. K-anonymized queries were re-identified with different continuity arguments and cardinalities of anonymity-set. Experiments demonstrate that the algorithm has high success rate (85%)in identifying query senders when the continuous queries have strong relationship, which is 1.5 times higher than the success rate without the attacking algorithm and severely undermines the anonymity of the queries.

Published: 16 January 2010
CLC:  TP 393  
Cite this article:

LIN Xin, LI Shan-Beng, YANG Chao-Hui. Attacking algorithm against  k-anonymized continuous queries in location based service. J4, 2009, 43(12): 2136-2141.

URL:     OR



[[1]]   BISDIKIAN C, CHRISTENSEN J, DAVIS J, et al. Enabling location-based applications
[[C]]   ∥1st Workshop on Mobile Commerce. Rome, Italy: ACM, 2001: 38-42.
[[2]]   JOSE R, DAVIES N. Scalable and flexible location-based services for ubiquitous information access
[[C]]   ∥Proceedings of First International Symposium on Hand-held and Ubiquitous Computing, HUC’99. Karlsruhe, Germany: Springer Verlag, 1999: 52-66.
[[3]]   GRUTESER M,GRUNWALD D. Anonymous usage of location based services through spatial and temporal cloaking
[[C]]   ∥ACM/USENIX Mobile Systems, Applications and Service.San Francisco, California, USA: ACM, 2003: 31-42.
[[4]]   GEDIK B, LIU L. Location privacy in mobile systems: a personalized anonymization model
[[C]]   ∥Proceedings of International Conference on Distributed Computing Systems. Columbus, Ohio, USA: IEEE, 2005: 620-629.
[[5]]   GHINITA G, KALNIS P, SKIADOPOULOS S. PRIVE: anonymous location-based queries in distributed mobile systems
[[C]]   ∥Proceedings of the International World Wide Web Conference. Banff, Canada: ACM, 2007: 371-380.
[[6]]   CHOW C, MOKBEL M. Enabling private continuous queries for revealed user locations
[[C]]   ∥Advances in Spatial and Temporal Databases. Boston, MA, USA: Springer Verlag, 2007: 258-275.
[[7]]   MOHAMMAD R, KOLAHDOUZAN C S. Alternative solutions for continuous K nearest neighbor queries in spatial network databases
[[J]]   GeoInformatica, 2005, 9(4):321-341.
[[8]]   XIONG X, MOKBEL, AREF W. SEA-CNN: scalable processing of continuous K-nearest neighbor queries in spatio-temporal databases
[[C]]   ∥In Proceeding of the International Conference on Data Engineering. Tokyo: IEEE, 2005: 643-654.
[[9]]   HUANG X, JENSEN C. Towards a streams-based framework for defining location-based queries
[[C]]   ∥Proceedings of the International Workshop on Spatio-temporal Database Management. Toronto, Canada: ACM, 2004:73-80.
[[10]]   MOKBEL M, AREF W. SOLE: scalable online execution of continuous queries on spatiotemporal data streams
[[J]]   Journal on Very Large Database, 2008,17(5):971-995.
[[11]]   BRINKHOFF T. A framework for generating network-based moving objects
[1] GUO Tong,LIN Feng. Bayesian network structure learning based on hybrid genetic
and fish swarm algorithm
[J]. J4, 2014, 48(1): 130-135.
[2] I De-jun,WANG Gang,YANG Can-jun,JIN Bo,CHEN Yan-hu. NTP/IEEE1588-based time synchronization system in seafloor observatory network[J]. J4, 2014, 48(1): 1-7.
[3] DU Rui-zhong, TIAN Jun-feng, ZHANG Huan-guo. Cloud service selection model based on trust and personality preferences[J]. J4, 2013, 47(1): 53-61.
[4] ZHANG Shuai, SUN Jian-ling, XU Bin, HUANG Chao, KAVS Aleksander J.. RBAC based access control model for services compositions
cross multiple enterprises
[J]. J4, 2012, 46(11): 2035-2043.
[5] Chen Sui-sheng,Lu Jian-gang,Lou Xiao-chun. Localization algorithm for wireless sensor networks
based on MDS-MAP and nonlinear filtering
[J]. J4, 2012, 46(5): 866-872.
[6] YANG Zhao-hui, LI Shan-ping, LIN Xin. Quality optimizing real-time scheduling for incremental context services[J]. J4, 2012, 46(1): 90-97.
[7] PAN Ju-long, LI Shan-ping, ZHANG Dao-yuan. Detecting suspicious node within one cluster in wireless sensor network
using game theoretic approach
[J]. J4, 2012, 46(1): 72-78.
[8] GAO Qing,LI Shan-ping,YANG Zhao-hui. Virtual force-field based energy efficient geo-routing in
wireless sensor network
[J]. J4, 2012, 46(1): 98-104.
[9] QIAN Jian-feng, YIN Jian-wei, DONG Jin-xiang. Load balancing algorithms of semantic publish/subscribe system
over structured P2P networks
[J]. J4, 2011, 45(10): 1710-1719.
[10] YANG Zhao-hui, LI Shan-ping, LIN Xin. Anonymity level adaptation algorithm to meet resource constraint
of K-anonymity service in LBS
[J]. J4, 2011, 45(7): 1154-1160.
[11] PAN Gang, LI Shi-jian, CHEN Yun-xing. ScudContext: large-scale environmental context services infrastructure
towards cyber-physical space integration
[J]. J4, 2011, 45(6): 991-998.
[12] CHE Jian-hua, HE Qin-ming, CHEN Jian-hai, WANG Bei. Software simulation-based fault injection tool of
virtual machine system
[J]. J4, 2011, 45(4): 614-620.
[13] ZHANG Li-ping, PAN Gang, ZHENG Neng-gan, YANG Guo-qing, LI Hong, ZHAO Min-de. Consistent bidirectional generation method and  development
platform based on SmartC models and codes
[J]. J4, 2011, 45(1): 20-29.
[14] LI Jian-ting, JIN Xin-yu, TANG Jun, ZHANG Yu. Target localization method based on wireless multimedia sensor network[J]. J4, 2011, 45(1): 45-49.
[15] SHU Ting, SUN Shou-qian, WANG Hai-ning, XU Wei-qiang. Adaptive generation algorithm for executable state identification
sequences in EFSM model
[J]. J4, 2010, 44(11): 2183-2187.