LBS中连续查询攻击算法及匿名性度量  

Attacking Algorithms Against Continuous Queries in LBS and Anonymity Measurement

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

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

出　　处：《软件学报》2009年第4期1058-1068,共11页Journal of Software

基　　金：国家自然科学基金Nos.60473052,60773180;浙江省自然科学基金No.Y106427;上海市国际科技合作基金No.075107006~~

摘　　要：k-匿名机制是LBS(location based service)中保证查询隐私性的重要手段.已有文献指出,现有的k-匿名机制不能有效保护连续性查询的隐私性.提出一种连续查询发送模型,该模型融合了查询发送时间的间隔模型和连续性模型,针对此模型下的两种k-匿名算法Clique Cloaking和Non-clique Cloaking,分别提出了一种连续查询攻击算法.在此攻击算法下,匿名集的势不再适合作为查询匿名性的度量,因此提出一种基于熵理论的度量方式AD(anonymityd egree).实验结果表明,对连续性很强的查询,攻击算法重识别用户身份的成功率极高;AD比匿名集的势更能反映查询的匿名性.k-Anonymity is an important solution to protecting privacy of queries in LBS （location-based service）. However, it is pointed out in literatures that k-anonymity cannot protect privacy of continuous queries effectively. A continuous query issuing model is proposed, which incorporates a query issuing interval model and a consecutive queries relationship model. Under this continuous query issuing model, two attacking algorithms are proposed for Clique Cloaking and Non-clique Cloaking respectively. Then this paper argues that the cardinality of anonymity-set is not a good anonymity measurement under such attack and an entropy-based anonymity measurement AD （anonymity degree） is proposed. Experimental results demonstrate that the attacking algorithms have high success rate in identifying query senders when the consecutive queries have strong relationship, and that AD is a better anonymity measurement than the cardinality of anonymity-set.

关 键 词：LBS(location-based service) K-匿名 连续查询 攻击算法 匿名性度量 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]