一种针对LBS中k-匿名连续查询的攻击算法  

Attacking algorithm against k-anonymized continuous queries in location based service

作　　者：林欣[1,2] 李善平[1] 杨朝晖[1] 

机构地区：[1]浙江大学计算机科学与技术学院,浙江杭州310027 [2]华东师范大学计算机科学技术系,上海200241

出　　处：《浙江大学学报（工学版）》2009年第12期2136-2141,2170,共7页Journal of Zhejiang University：Engineering Science

基　　金：国家自然科学基金资助项目(60473052;60773180;60903169);浙江省自然科学基金资助项目(Y106427)

摘　　要：针对k-匿名机制无法保证位置信息服务(LBS)中连续查询隐私性的问题,提出一种连续查询发送模型,该模型融合了查询发送时间的间隔模型和连续性模型.在该模型的基础上针对k-匿名算法,提出一种连续查询攻击算法,该算法将和连续查询相关的一系列快照互相关联,计算出快照的匿名集内每个用户发送查询的概率,从而估计出查询真正的发送者.仿真实验模拟在不同的连续性参数、匿名集的势的情况下,使用连续查询攻击算法重识别受k-匿名保护的查询.通过对被恶意攻击者重识别的查询数量统计,结果表明,对连续性很强的查询,攻击算法重识别用户身份的成功率极高(85%),比不使用攻击算法所获得的重识别率提高了1·5倍以上,严重破坏了查询的匿名性.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 anonymityset. 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.

关 键 词：位置信息服务 K-匿名 连续查询 攻击算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]