位置服务中查询隐私的匿名方法

第１３卷　第２期　２０１３年　２月　中　国水运　Ｏｈ　ｉ　ｎａ　Ｗａｔｅｒ　Ｔｒａｎｓｐｏｒｔ　ＶｏＩ．１３　Ｆｅｂｒｕａｒｙ　Ｎｏ．２　２Ｏ１３　

位置服务中查询隐私的匿名方法　

刘　鑫’，刘永山。　

（１中国移动通信集团河北有限公司秦皇岛分公司业务支撑中心，河北秦皇岛０６６０００；　

２燕山大学信息科学－９工程学院，河北秦皇岛０６６００４）　

摘要：论文针对位置服务中查询隐私保护问题，在ＬＢＳ　ｋ一匿名的基础上，对匿名集中查询内容进行语义分析，提　出ＬＢＳ（ｐ，ｋ）匿名模型来保护用户的查询隐私，此外，分析了目前匿名空间查找算法的不足，提出一种基于网格　

和密度的最小匿名空间查找算法ＭＡＳＳＡ（Ｍｉｎｉｍｕｍ　Ａｎｏｎｙｍｏｕｓ　Ｓｐａｃｅ　Ｓｅａｒｃｈ　Ａｌｇｏｒｉｔｈｍｓ）。　

关键词：基于位置服务；ｋ匿名；查询隐私；网格和密度　中图分类号：ＴＰ３１　１　文献标识码：Ａ　文章编号：１００６—７９７３（２０１３）０２—０１００—０３　

基于位置的服务（ＬＢＳ，Ｌｏｃａｔｉｏｎ—ｂａｓｅｄ　Ｓｅｒｖｉｃｅ）是指　通过移动网络与移动终端的配合，在地理信息系统（ＧＩＳ）的　

支持下，确定终端用户当前所在的地理位置，从而为用户提供　与位置相关的信息的一种增值业务＿１ｌ。基于位置的服务在给用　

户带来便捷服务的同时，也引发了令人担心的隐私泄露问题。　

因为要获得位置服务，首先就要将个人精确的位置信息和查询　

内容提交给不可信的位置服务提供商。因此，如何有效保护位　

置服务中的查询隐私成为位置服务中的一项重要内容。　目前大部分工作集中在位置隐私保护，并提出ＬＢＳ　ｋ一　

匿名模型保护用户的位置隐私。为了保护用户的位置隐私，　

Ｇｒｕｔｅｓｅｒ等人ｌ２　首先将ｋ一匿名技术引入到ＬＢＳ应用中来，　

主要思想是将用户的精确位置模糊化为一个包含至少ｋ个用　

户位置的匿名区域，使袭击者无法从这ｋ个用户里面区分出　

目标用户来达到隐私保护的目的，现有的ＬＢＳ　ｋ一匿名能改善　查询隐私保护＿３’　，但不能有效保护用户查询隐私。１一多样性　

匿名解决了匿名集中语义相似性太高的隐私问题，但由于　

没有考虑敏感信息所占比例，攻击者还是有可能以很高的概　

率获得用户的查询隐私。　

一、问题定义与ＬＢＳ（Ｐ，ｋ）匿名模型的提出　

文献＿６ｌ总结了目前常用的几种系统结构，本文采用目前　

应用较多的中心服务器结构｝２’３，　】，下面介绍中心服务器结　构查询请求处理过程及袭击模式，并提出面向查询隐私保护　

的ＬＢＳ（Ｐ，ｋ）匿名模型。　１．系统结构　

主要由３部分组成：移动用户，可信的匿名服务器，ＬＢＳ　

服务提供商。用户提出一个服务请求的过程是：移动用户首　

先将查询请求Ｑ（ｉｄ，１，ｑ）通过加密连接发送给匿名服务　

器，服务器收到信息后对信息进行解密，读取数据，并将直　

接能识别出用户的标识符ｉｄ移除，换做假名ｉｄ’，在接收到　

一批用户请求之后，匿名服务器通过匿名算法将用户的位置　

信息匿名化为一个包含多个用户的区域Ｒ（Ｒｅｇｉｏｎ），将查　

询Ｑ’　（ｉｄ’，Ｒ，ｑ）提交给ＬＢＳ服务提供商，服务提供　商对查询请求进行查询处理，并将查询结果候选集发送给匿　名服务器，匿名服务器对查询结果求精后返回给移动用户。　

２．攻击模式　

本节假设一个实例来描述攻击模型。如表１分别为经过　

匿名服务器匿名的查询表和攻击者通过定位技术获得的用户　

位置信息表。　表Ｉ　实例化的匿名表和外联表　

ａ）匿名表Ｔ’　

假设攻击者的攻击目标为ｕ４，通过外联表　，攻击者　

得知目标用户的位置为（２，６），从匿名表中得到的此区域　

内的查询表Ｔ’，满足位置ｋ一匿名，通过对其中的查询内容　

进行语义分析，可以观察出其中查询内容全是关于医院或疾　病的敏感查询，用户不想与其中任何一个查询联系起来，而　

袭击者通过将这两个表链接，就能判断出目标用户ｕ４一定　

得了某种疾病。　

３．ＬＢＳ（ｐ，ｋ）匿名模型　

针对１．２中的攻击模式，关系数据隐私保护领域阚莹莹　

１８１提出的改进的ｋ一匿名方法，她将数据表中所有数据按敏感　

收稿日期：２０１２—０９—１２　作者简介：刘鑫（１９７８．），男，河北省秦皇岛人，中国移动通信集团河北有限公司秦皇岛分公司业务支撑中心通信工程师，　

硕士，主要研究方向为电信运营商业务支撑系统和管理信息系统。　刘永山（１９６３一），男，燕山大学信息科学与工程学院教授，博导，主要研究方向为数据库理论、计算机应用技术。

　第２期　刘鑫等：位置服务中查询隐私的匿名方法　１０１　

信息隐私程度进行分类，并限定每个类别所占比例小于Ｐ，　

由于ＬＢＳ实时应用中，一个查询请求时间内记录个数远远小　

于关系数据表中的数据，且ＬＢＳ应用对时间响应速度要求较　

高，在提出的ＬＢＳ（Ｐ，ｋ）匿名模型中，通过对匿名集中的　

查询内容进行语义分析，将查询内容区分为敏感查询和非敏　

感查询两类，并限定每个匿名集中敏感查询所占比例不超过　Ｐ，这样，计算攻击者能获得外联表和匿名表，他推断出用户　

提出某个敏感查询的概率也不会超过概率Ｐ，从而达到查询　

隐私保护的目的。　

二、一种满足ＬＢＳ（Ｐ，ｋ）匿名的匿名空间查找算法　

本文提出基于网格和密度的最小匿名空间查找算法　ＭＡＳＳＡ　（Ｍｉｎｉｍｕｍ　Ａｎｏｎｙｍｏｕｓ　Ｓｐａｃｅ　Ｓｅａｒｃｈ　

Ａｌｇｏｒｉｔｈｍｓ），并在ＭＡＳＳＡ算法的基础上，加入Ｐ敏感约　束，提出ｐ－ＭＡＳＳＡ算法。　

定义２．ｉ：相邻网格当前网格所处空间位置为ｉ行ｊ列，　

坐标为ｓｉ，ｊ，则坐标为　土ｌＩ｛或ｓｉ，ｊ±１的网格称为当前网　

格的相邻网格。　定义２．２：邻域空间当前网格坐标为ｓｉ，ｊ，当前网格和　

其所有相邻网格构成的网格集合构成当前网格的邻域空间，表　

示为（Ｓｉ一１，ｊ—Ｉ，Ｓ　ｉ＋ｉ，ｊ＋Ｉ），计算方法见公式ｌ所示。　Ｓ　＝｛Ｓ　Ｊｉ一１　Ｘ≤ｉ＋ｌ，ｉ一１≤Ｙ　Ｊ＋１）　（１）　

定义２．３：最小包含空间若应用空间Ｓ满足匿名要求，　

对空间Ｓ进行网格划分后，用户ｕ的邻域空间所包含的用户　

数小于匿名要求，称空间Ｓ为用户最小匿名空间的包含空间，　

简称最小包含空间。　以ｋ＝４为例，ＭＡＳＳＡ算法过程如下：　

首先对空间进行网格划分，并生成用户分布矩阵，如图　

ｉ，在空间Ｓ寻找用户ｕ所在网格ｕ２３，计算用户的邻域空　间Ｓ’＝【（１－３），（２—４）１，如图２—１　ａ），计算Ｓ’内用户数　

（Ｉ　Ｓ’１），若满足Ｊ　Ｓ’ｌ＞４，则令Ｓ’＝ｓ迭代划分网格，　

如图ｌ，直到ｌＳ’Ｊ＜＝４，本例为Ｓ２。　

ａ）Ｓ的分布矩阵　ｂ）ｓ２的分布矩阵　图１用户空间分布矩阵　

定义２．４：用户分布相对密度假设两用户ｕ，ｖ所在网　

格分别为（ｉ，ｊ），（Ｘ，Ｙ），两用户分布相对密度为从用户Ｕ　所在网格到用户ｖ所在网格覆盖的矩形框内用户数与矩形框　

覆盖网格数的比值。见公式（２）：　

／　＝—ａｂｓ—［（ｘ—－　ｉ＋　１）＊Ｌ（ｙ—－ｊ一＋１）］　（２）　

根据公式（２）计算用户的相对分布密度矩阵如图２：　

０．４ｌ　７　０．４４４　０　０　０．５　０　０　Ｏ　０．６６７　０．５　０　０　ｌ　Ｏ　１　Ｏ　０．３３３　０　Ｏ　０　Ｏ　０　０．３３３　Ｏ　０．５　

图２用户分布相对密度矩阵　为了避免极端情况下，用户过于密集，匿名空间过小导　

致的位置隐私泄露，给最小空间限定条件最小面积不能小于　

定值Ｓｍｉｎ（匿名空间最小粒度）。　根据用户分布相对密度矩阵，以用户ｕ为中心，由远及　

近依次删除用户分布相对密度最小的行或列，直到剥离某条　

边缘后，得到的匿名空间不满足条件（Ｉ　Ｓ　ｌ　４＆＆　

ａｒｅａＳＭＣＲ＞Ｓｍｉｎ）。　

算法２．１：ＭＡＳＳＡ算法。　输入：隐私度要求ｋ，应用空间Ｓ；　

输出：最小匿名空间ＳＭＣＲ。　ＭＡＳＳＡ（ｋ，Ｓ）　

Ｂｅｇｉｎ：　（１）Ｗｈｉｌｅ（１Ｓｆ＞ｋ＆＆ａｒｅａ（Ｓ）＞Ｓｍｉｎ）｛　

（２）Ｓｍ＝Ｓ；／／Ｓｍ是包含ＳＭＣＲ的最小空间　

（３）根据公式（Ｉ）查找Ｓ的邻域空间Ｓ’；　（４）Ｓ＝Ｓ’；　（５）｝／／寻找ＳＭＣＲ的最小包含空间　

（６）　ＳＭＣＲ＝Ｓｍ；　ｉｎｔ　ｉ＝ｌ；　（７）Ｗｈｉｌｅ（Ｉ　ＳＭＣＲ　ｌ＞ｋ＆＆ａｒｅａ（ＳＭＣＲ）＞Ｓｔａｉｎ）　

｛　（８）根据用户分布密度矩阵依次查找用户分布密度最小　

的第ｉ个冗余边缘Ｓｉ；　

（９）ＳＭＣＲ＝ＳＭＣＲ－Ｓｉ；　

（１０）ｉ＋　；　（１１）｝／／依次删除冗余边　（１２）Ｒｅｔｕｒｎ　ＳＭＣＲ　

Ｅｎｄ　算法２．１描述了基于网格和密度的ＬＢＳ　ｋ一匿名空间查找　

算法。　对于用户提交的敏感查询和非敏感查询，分别用１和０　

来表示，构建匿名区域内用户查询敏感度矩阵，矩阵每个坐　

标的值表示对应网格内敏感查询的个数，为了简化计算，将　匿名集中敏感查询所占比例不超过Ｐ的条件修改为匿名集中　

敏感查询个数不超过ｆｌｏｏｒ（ｋ×Ｐ），仍以上面的例子为例，　

假设查询敏感度矩阵如图３，若用户敏感度要求为０．３，即空　

间内敏感查询的个数不超过ｆｌｏｏｒ（４×０．３）＝１。　

图３敏感度矩阵　

算法２．２：Ｐ—ＭＡＳＳＡ算法。　输入：隐私度要求ｋ，敏感度要求Ｐ，应用空间Ｓ；　

输出：最小匿名空间ＳＭＣＲ。　

ｐ－ＭＡＳＳＡ（ｋ，Ｐ，Ｓ）　

Ｂｅｇｉｎ：　（１）执行算法ＭＡＳＳＡ步骤（１）一（５）寻找最小包含　

空间；　（２）ＳＭＣＲ＝Ｓｍ；ｉｎｔ　ｉ＝１；　（３）Ｗｈｉｌｅ（Ｉ　ＳＭＣＲ　Ｉ＞ｋ＆＆ａｒｅａ（ＳＭＣＲ）＞Ｓｍｉ

ｎ　１Ｏ２　中国水运　第１３卷　

＆＆Ｓｉｄ＞ｆｌｏｏｒ（ｋ×Ｐ））｛　（４）用户分布密度矩阵和敏感度矩阵依次查找用户分布　

密度最小敏感度最大的第ｉ个冗余边缘Ｓｉ；　

（５）ＳＭＣＲ＝ＳＭＣＲ—Ｓｉ；　（６）｝／／剥离冗余边缘　（７）Ｉｆ（Ｓｉｄ＜＝ｆｌｏｏｒ（ｋ×Ｐ）　）｛　

（８）执行算法ＭＡＳＳＡ步骤（７）一（１２）；　

（９）｝／／ｉｆ　

（１０）Ｅｌｓｅ｛　（１１）匿名失败，拒绝此次查询请求；　

（１２）｝／／Ｅｌｓｅ　

Ｅｎｄ　算法２．２描述了基于一般ＬＢＳ（ｐ，ｋ）模型的匿名空　间查找算法。　三、结束语　

本文分析了目前的ＬＢＳ　ｋ一匿名算法不能有效保护查询　

隐私的不足，提出一种ＬＢＳ（Ｐ，ｋ）匿名模型，此方法考虑　了ｋ一匿名集中查询语义敏感性，将查询属性分为敏感查询和　

非敏感查询，通过约束敏感查询在匿名集中所占比例，保证　

了攻击者不能以超过Ｐ的概率判断出用户提出了某个敏感查　

询，达到了查询隐私保护的目的，还提出基于网格和密度的　

匿名空间查找算法计算最小匿名空间。　

参考文献　

【Ｉ１王明才，姚承宽．位置服务在我国的应用与发展Ｕ１．河北师　

范大学学报（自然科学版），２００９，３３（５）：６８８—６９２．　

［２］Ｇｒｕｔｅｓｅｒ　Ｍ，Ｇｍｎｗａｌｄ　Ｄ．Ａｎｏｎｙｍｏｕｓ　Ｕｓａｇｅ　ｏｆ　Ｌｏｃａｔｉｏｎ一　

（上接第９９页）　

第一步：在工程开工之前应综合考虑所有影响因素，尽　

量准确核算目标成本，但目标成本并不作为成本考核的依据。　

第二步：一般情况下，动态成本考核分为月度考核、季　

度考核、年度考核及竣工考核四个阶段，根据工程进度，核　

算每个阶段的目标成本、实际成本及其差值，并分析产生差　值的影响因素，依据影响因素与项目部之间的关系程度赋予　

权重系数，以此计算成本节约额。　

第三步：依据成本节约额判断项目部成本考核绩效，并