对位置信息服务的连续查询攻击算法

摘要：为了解决连续查询攻击算法给位置信息服务（LBS）带来的安全隐患，基于已有的k匿名化Cloaking算法提出了一种新的连续查询攻击算法——CQACA。该算法首先利用熵和查询匿名度量定义了查询识别率的目标函数，并结合元胞蚁群给出了目标函数的求解算法。最后，利用移动对象数据生成器进行实验，深入研究了影响CQACA的关键因素，同时对比分析了该算法与Cloaking算法的性能差异：CQACA与实际数据的误差为13.27%，而Cloaking算法则为17.35%。结果表明CQACA具有一定的有效性。

关键词： 位置信息服务； 连续查询攻击算法； 查询匿名度量； 查询识别率； 元胞蚁群

中图分类号： TP309 文献标志码： A

0引言

随着定位技术的迅速发展，基于位置的服务（LocationBasedService，LBS）在通信网络中得以广泛应用[1-5]。LBS是根据用户的位置提供特定服务，但也存在诸如位置或隐私信息遭泄露或滥用等安全隐患。目前，位置隐私分为敏感位置隐私和位置ID隐私，敏感位置隐私通过模糊化或者加密位置来保护位置隐私，而位置ID隐私是通过k匿名技术来实现保护位置隐私的。k匿名是指当一个移动用户的位置无法与其他k-1个用户的位置区别时，称此位置满足位置k匿名。MGruteser首先将k匿名引入到位置隐私保护，为用户提供相同隐私要求的匿名服务。

目前，LBS匿名技术主要有错误或假的位置信息方法，区域化位置信息的方法和加密方法，典型代表算法有CliqueCloak、Casper、HilbertCloak和kNNCloak[6-10]。CliqueCloak主要是为用户建立一个无向图并寻找满足k匿名相互连通的小集团，但该算法缺乏灵活性。Casper作为QuadTree的经典方法在匿名器上广泛应用，但Casper盲目递归查找匿名空间时导致产生的较大匿名空间，为后期查询操作带来不便。而HilbertCloak则是用希尔伯特空间填充弧，将二维空间映射为k匿名组，该算法具有较高的安全性，但是系统开销较大。kNNCloak是根据k个最近邻居为匿名伙伴进行随机选择，以此改善匿名效果。对此，国内外学者也提出了大量改进算法。高枫等[11]深入研究了基于位置服务应用的隐私保护需求多样性，提出了一种以用户为中心的信任隐私保护模型，允许用户对隐私偏好进行自主设置。林欣等[12]通过融合查询发送时间的间隔模型，提出了一种连续查询发送模型，并结合两种k匿名算法CliqueCloaking和NoncliqueCloaking，分别提出了连续查询攻击算法。针对基于位置的服务中的k匿名机制的最小匿名度的QoS，杨朝晖等[13]提出一种新的QoS指标——匿名结果集势指标R*，用于度量和约束匿名服务和LBS为用户的每次查询所平均消耗的计算资源。王彩梅等[14]基于用户轨迹隐私保护方法SilentCascade，将用户运动轨迹用带权无向图描述，提出一种新的轨迹隐私度量方法，并从信息熵的角度来计算用户轨迹隐私。为了提高现有地点识别方法精确度，丰江帆等[15]基于速度剪枝、时间剪枝和空间剪枝相结合的VSTPruning算法提出了一种新的地点识别方法，并综合R*树空间索引机制和密度相交提出了基于密度的RTcluster聚类方法。

针对上述问题，本文基于k匿名集Cloaking算法提出了一种新的连续查询攻击算法（ContinuousQueriesAttackingalgorithmsbasedonCellularAnt，CQACA）。该算法首先定义了查询识别率以及查询匿名度量目标函数，并利用元胞蚁群算法对上述模型进行求解。利用移动对象数据生成器，通过仿真实验对比分析了CQACA与Cloaking算法之间的性能差异，同时深入研究了影响CQACA的关键因素。

同时，在图5中给出了不同蚁群搜索半径r下算法平均误差error的变化情况。类似于图3中曲线的变化趋势，在实验开始阶段，搜索半径r越小对应的平均误差error越小，而在后期搜索半径r越小对应的平均误差error越大。这是由于在开始阶段蚁群性能偏低时，半径r越大每个邻域所需要的搜索资源越大，系统收敛减缓。而在后期蚁群性能得到提高时，半径r越大可以有效避免陷入局部最优，从而降低平均误差。

4结语

针对查询隐私存在的安全隐患，本文在已有的k匿名集Cloaking算法基础上，结合元胞蚁群算法进行改进，提出了一种基于LBS的连续查询攻击算法CQACA。该算法利用熵和查询匿名度量定义了查询识别率的计算模型，并给出了元胞蚁群的演化规则以及算法流程。最后，利用移动对象数据生成器来进行实验，对比分析了CQACA与Cloaking算法的性能差异，同时深入研究了影响CQACA的关键因素，结果表明该算法具有一定的适应性。在以后的研究工作中，可以考虑采用多种人工智能和聚类算法针对各类轨迹距离度量进行研究，以设计和建立完善有效的隐私保护轨迹数据模型。

参考文献：

[1]MOURATIDISK，YIUML.Anonymousqueryprocessinginroadnetworks[J].IEEETransactionsonKnowledgeandDataEngineering，2010，22（1）：2-15.

[2]GUTINGRH，BOHLENMH，ERWIGM，etal.Afoundationforrepresentingandqueringmovingobjects[J].ACMTransactionsonDatabaseSystems，2000，25（1）：1-42.

[3]ARDAGNAC.Anobfuscationbasedapproachforprotectinglocationprivacy[J].IEEETransactionsonDependableandSecureComputing，2011，8（1）：13-27.

[4]XUJ，TANGX，DUJ.Privacyconsciouslocationbasedqueriesinmobileenvironments[J].IEEETransactionsonParallelandDistributedSystems，2010，21（3）：313-326.

[5]ABULO，BONCHIF，NANNIM.Anonymizationofmovingobjectsdatabasesbyclusteringandperturbation[J].InformationSystems，2010，35（8）：884-910.

[6]DOMINGOFERRERJ，TRUJILLORASUAR.Microaggregationandpermutationbasedanonymizationofmovementdata[J].InformationSciences，2012，208：55-80.

[7]HUH，XUJ.PASS：bandwidthoptimizedlocationcloakingforanonymouslocationbasedservices[J].IEEETransactionsonParallelandDistributedSystems，2010，21（10）：1458-1472.

[8]PANX，HAOX，MENGX.Privacypreservingtowardscontinuousqueryinlocationbasedservices[J].JournalofComputerResearchandDevelopment，2010，47（1）：121-129.

[9]REBOLLOD.Privatelocationbasedinformationretrievalthroughusercollaboration[J].ComputerCommunications，2010，33（6）：762-744.

[10]HASHERNT，KULIKL.Donttrustanyone：privacyprotectionforlocationbasedservices[J].PervasiveandMobileComputing，2011，7（1）：44-59.

[11]GAOF，HEJ，ZHANGF，etal.TrustbasedprivacyprotectionmethodinLBS[J].JournalonCommunications，2011，32（11A）：63-70.

[12]LINX，LIS，YANGZ.AttackingalgorithmsagainstcontinuousqueriesinLBSandanonymitymeasurement[J].JournalofSoftware，2009，20（4）：1058-1068.

[13]YANGZ，LIS，LINX.AnonymityleveladaptationalgorithmtomeetresourceconstraintofKanonymityserviceinLBS[J].JournalofZhejiangUniversity：EngineeringScience，2011，45（7）：1154-1160.

[14]WANGC，GUOY，GUOY.Privacymetricforuserstrajectoryinlocationbasedservices[J].JournalofSoftware，2012，23（2）：352-360.

[15]FENGJ，XIONGY.AnimportantplaceidentificationalgorithmbasedonpersonalGPSlocation[J].JournalofChineseComputerSystems，2013，34（3）：503-507.

[16]SONGY，JIANGG，XUJ.Anepidemicspreadingmodelinadaptivenetworksbasedoncellularautomata[J].ActaPhysicaSinica，2011，60（12）：110-119.

[17]CAOC，WANGL，ZHAOD.Theresearchbasedonthediscretecellularantalgorithminthegeometricconstraintsolving[J].ActaElectronicaSinica，2011，38（5）：1127-1130.

[18]BRINKHOFFT.Aframeworkforgeneratingnetworkbasedmovingobjects[J].Geoinformatica，2002，6（2）：153-180.

[19]ZOUY，ZHANGY.Locationcloakingalgorithmbasedongriddividedspace[J].ApplicationResearchofComputers，2012，29（8）：3059-3061.