（计算机应用技术专业论文）位置服务中轨迹隐私保护方法的研究.pdf

硕士学位论文 m a s t e r st h e s i s i i i l llli iill lli ii l liiil y 18 9 9 4 0 8 r e s e a r c ho nt r a j e c t o r yp r i v a c y p r o t e c t i n gm e t h o d i nl b s at h e s i s s u b m i t t e d 觑p a r t i a lf u l f i l l m e n to f t h er e q u i r e m e n t f o rt h em s d e g r e ei nc o m p u t e r a p p l i c a t i o n b y g n oy a n h u a p o s t g r a d u a t ep r o g r a m d e p a r t m e n to fc o m p u t e r s c i e n c e h u a z h o n gn o r m a lu n i v e r s i t y r s i g n a t u r e 匦垃堕竺! 型坠 a p p r o v e d m a y 2 0 1 1 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名： 帮料 日期：驯年歹月日 学位论文版权使用授权书 学位论文作者完全了解华中师范大学有关保留、使用学位论文的规定，即：研 究生在校攻读学位期间论文工作的知识产权单位属华中师范大学。学校有权保留并 向国家有关部门或机构送交论文的复印件和电子版，允许学位论文被查阅和借阅； 学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它复制手 段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密，在年解密后适用本授权书。 非保密论文注释：本学位论文不属于保密范围，适用本授权书。 作者叛秆样 日期：弘i f 年占月j 日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程 ，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库 中全文发布，并可按“章程 中的 规定享受相关权益。园童途塞握童后进卮；旦坐生；旦二生；旦三生蕉查! 篇章砦尊 作者签名：多p 寺毯平 日期弘f f 年6 月j 日 导师张卯砂均 日期：砂f 降月日 珈弓 碜白、泖球 经 秒 签 ： 煨期 字玑 硕士学位论文 m a s t e r st h e s i s 摘要 近年来，随着移动计算技术和传感网络技术的蓬勃发展，基于位置的服务 ( l o c a t i o nb a s e ds e r v i c e ，l b s ) 应用越来越广泛，用户的位置隐私成为人们关注的 问题。轨迹隐私是位置服务中一类特殊的位置隐私。研究者们提出了大量的匿名算 法和方案来保护用户的轨迹隐私信息。现有的轨迹隐私保护的方法大多数是关于切 断用户的连续两次或多次服务请求中位置信息的联系性，使攻击者即使截获了位置 服务请求也难以推断出用户的轨迹，这些方法只在一定程度上保护了用户的轨迹隐 私信息。 针对轨迹隐私保护问题，本文提出的一种应用于混杂分布式网络环境下的基于 转发查询的轨迹隐私保护方法。在实现基于转发查询的方法中，主要使用了两种算 法：利用希尔伯特空间算法将用户所在的二维空间位置坐标映射为按关键字大小 排列的维序列。采用c h o r d 分布式协议把用户根据关键字自组织到一个混杂 p 2 p 网络中，构成一个c h o r d 环的结构。每个用户都在一个簇( 簇的大小与系统参 数口有关) 中，c h o r d 环上的用户为簇头节点及其前驱或后继节点，簇中的成员节 点及其信息由簇头来维护。提出k 匿名查询请求的用户由其簇头节点通知其簇成员 节点来构建k 匿名区域，如果簇成员节点的数量不足k ，则簇头节点通知其前驱列 表或后继列表中的用户直到找到k 个用户。在簇头节点处构建k 匿名集合和包含k 个用户的最小边界矩形，最后由簇头节点的前驱或后继节点把匿名集合查询请求转 发到位置服务器进行查询处理。查询处理的结果直接返回到簇头节点完成查询结果 的求精。 实验对采用基于转发查询方法的系统在抵抗中心k 匿名区域攻击和关联攻击的 能力、移动用户进出系统的时延和通信开销及负载均衡等方面的性能与m o b i h i d e 系统做了比较，显示了该方法在位置隐私和轨迹隐私保护方面的优越性。它能够保 证当用户的位置连续更新时，攻击者很难得到用户的位置信息，也就无法将位置信 息联系起来，从而达到轨迹隐私保护的目的。 关键词：轨迹隐私；位置隐私；转发查询；c h o r d 硕士学位论文 m a s t e r st h e s i s a b s t r a c t a st h ed e v e l o p m e n to fm o b i l ec o m p u t i n ga n ds e n s o rn e t w o r k ，l o c a t i o nb a s e d s e r v i c e ( l b s ) i sa p p l i e dw i d e l yi nr e c e n ty e a r s u s e r sl o c a t i o np r i v a c yr e c e i v e sm o r e a n dm o r ea t t e n t i o n t r a j e c t o r yp r i v a c yp r o t e c t i o ni sa l li m p o r t a n ti s s u ei nl b s r e s e a r c h e r sp r o p o s e dal o to fa l g o r i t h m sa n di d e a st h a ta r eu s e dt op r o t e c tt h el o c a t i o n i n f o r m a t i o n t h ee x i s t i n gm e t h o d sa r em o s t l yi n v o l v e di nc u t t i n gt h er e l a t i o n s h i p b e t w e e nu s e r sc o n s e c u t i v el o c a t i o ni n f o r m a t i o n ：i n c l u d e di nt h eq u e r i e s t h e s em e t h o d s m a k ei td i f f i c u l tt og e tt h et r a j e c t o r yf o rt h ea t t a c k e r sa n dc a ne f f e c t i v e l yp r o t e c tu s e r s t r a j e c t o r yp r i v a c yi n f o r m a t i o nt oa c e r t a i ne x t e n t f o rt h ep r o b l e m sa b o v e ，t h i sp a p e rp r o p o s eb f q ( b a s e do nf o r w a r d i n gq u e r i e s ) w h i c hi sat r a j e c t o r yp r i v a c yp r o t e c t i n gm e t h o di nap e e r - t o - p e e r ( p 2 p ) s y s t e m b f q i n t r o d u c e st w oe s s e n t i a la l g o r i t h m s ：1 ) h i l b e r ts p a c e f i l l i n gc u r v ei su s e dt om a pt h e2 一d l o c a t i o n so fm o b i l eu s e r si n t o l ds p a c e t h et r a n s f o r m e dl o c a t i o n sa r ei n d e x e da n d o r d e r e dt of o r mah i l b e r ts e q u e n c e 2 ) t h ec h o r dd i s t r i b u t e dp r o t o c o li su s e dt oo r g a n i z e t h eo r d e r dm o b i l eu s e r si n t oap 2 ps y s t e m t h ep 2 ps y s t e mi sac h o r dr i n gw h i c h i n c l u d e sa l lm o b i l eu s e r sw h ow a n t st or e c e i v el b s e v e r yu s e rb e l o n g st oac l u s t e ri n w h i c hh a s3 口( s y s t e mp a r a m e t e r ) u s e r s t h e r ea r ec l u s t e rh e a d sa n dt h e i rs u c c e s s o r sa n d p r e d e c e s s o r so nt h ec h o r dr i n g t h ei n f o r m a t i o no ft h ec l u s t e rm e m b e r si sm a i n t a i n e db y t h ec l u s t e rh e a d w h e nau s e ri s s u e saq u e r y , h i sc l u s t e rh e a dn o t i f i e se v e r yc l u s t e r m e m b e r st oi n i t i a t st h ek - a n o n i m i t ys p a t i a la r e a ( k - a s r ) c o n s t r u c t i o np r o c e s s i fku s e r s a r en o tf o u n di nt h ec l u s t e r , t h ec l u s t e rh e a dw i l li s s u ear e q u e s tf o rt h en o d e si nh i s p r e d e c e s s o rl i s t o rs u c e s s o rl i s t t h e nt h ek - a s ra n dt h em i n i m u mb o u n d a r y r e c t a n g l e ( m b r ) w h i c hc o n t a i n st h ea n o n i m i t ys e t sa r ef o r m e d f i n a l l yt h es u c c e s s o ro r p r e d e c e s s o ro f t h ec l u s t e rh e a di ss e l e c t e dt of o r w a r dt h eq u e r i e st ol b s t h ee x p e r i m e n t sa r ec o n d u c t e dt os h o wt 1 1 a tb f qo u t p e r f o r m sm o b i h i d ei n a b i l i t i e so fr e s i s t i n gt h ec e n t e r - o f - k - a s ra t t a c ka n dt h ec o r r e l a t i o na t t a c k ，t h eo p e r a t i o n o fm o b i l eu s e r s j o i n i n ga n dd e p a r t u r i n gt h es y s t e ma n ds y s t e ml o a db a l a n c i n g b f q m a k e si td i f f i c u l tt og e tt h es o u r c eq u e r i e sa n dl o c a t i o ni n f o r m a t i o nf o ra t t a c k e r sw h e n u s e r su p d a t et h e i rq u e r i e sc o n t i n u o u s l y t h e r e f o r ei tc a np r o t e c tt h eu s e r st r a j e c t o r y p r i v a c ye f f e c t i v e l y k e yw o r d s ：t r a j e c t o r yp r i v a c y ；l o c a t i o np n v a c y ；f o r w a r d i n gq u e r y ；c h o r d 摘要 目录 a b s t r a c t 第一章绪论 l 1 1 选题背景和意义1 1 2 国内外研究现状2 1 3 本文的主要研究内容5 1 4 本文的内容安排6 第二章位置服务中的隐私保护 2 1l b s 概述7 2 1 1l b s 的概念7 2 1 2l b s 的应用8 2 1 3l b s 中的安全问题。9 2 2 位置服务中的隐私保护1 0 2 2 1 位置隐私保护1 0 2 2 2 位置隐私保护方法“1 0 2 2 3l b s 中隐私保护的常见系统结构介绍1 3 2 3 轨迹隐私保护1 4 2 4 本章小节。16 第三章基于转发查询的轨迹隐私保护系统” 1 7 3 1 轨迹隐私保护的相关定义1 7 3 2 基于转发查询的轨迹隐私保护系统结构原理1 8 3 3 基于转发查询的轨迹隐私保护系统的实现1 9 3 3 1 希尔伯特算法1 9 3 3 2 基于转发查询系统的实现2 2 第四章实验与分析 4 1 实验环境3 0 4 2 实验结果与分析3 0 4 2 1 匿名的强度3 l 4 2 2 用户加入网络系统时的时延和通信开销3 3 硕士学位论文 m a s t e r st h e s i s 4 2 3 负载均衡3 3 4 3 本章小节3 4 第五章结论和展望 3 5 5 1 总结3 5 5 2 展望3 6 参考文献 在校期间发表的论文、科研成果等 致谢” 4 2 4 3 硕士学位论文 m a s t e r 。st h e s i s 1 1 选题背景和意义 第一章绪论 移动计算技术和传感网络技术使得移动用户在任何时间、地点享受信息服务的 愿望成为了现实。随着位置探测设备( 例如手机、g p s 、r f i d 、传感器等) 和地理 信息系统的开发、应用及推广，基于位置的服务( l o c a t i o n b a s e ds e r v i c e ，l b s ) 的 应用越来越广泛，例如信息娱乐服务( 查找距离用户百米内最近的电影院、商店或 餐厅) 、交通导航( 查找到达事故地点的最优路径) 和基于位置的广告分发( 向餐 馆5 0 0 m 内的用户发送电子优惠券) 、路线跟踪( 对某航班飞机进行追踪) 等服务。 位置服务是与用户提出查询请求的位置信息有关的一种服务。如果用户要享受位置 服务，首先需要向位置服务器提供自身的位置信息以及查询请求的内容，位置服务 器根据该位置信息对查询请求的内容进行查询处理，处理得到的结果返回给用户。 基于位置的服务能够通过移动设备定位用户的位置信息，使用户能够享受自身 位置附近的便利服务。移动用户通常配备手机等移动定位装置，当需要使用某种位 置服务时，可以使用定位装置获得自己的位置信息，并将查询请求及自身的位置信 息传递给位置服务器进行查询处理。位置信息是位置服务器处理服务请求的主要依 据，位置信息越准确，经过位置服务器查询处理后返回给用户的服务信息将越准确。 可见，位置服务的质量很大程度上取决于用户位置信息的准确性。尽管位置服务和 定位技术为人们的生活带来了便利的服务，方便了人们的生活，但其应用由于安全 问题受到限制。如果位置服务器是不可信的，比如某些服务提供商出于某种商业目 的出卖用户发送来的位置信息，从而对用户的位置隐私安全造成威胁。因此，如何 保证用户在使用位置服务时的位置隐私的安全是个亟待解决的问题。 轨迹隐私保护是用户为避免用户自身以外的其他人员通过各种途径( 如长时间 观察，手机跟踪等) 获得其轨迹信息的能力。文献 1 】首次提出了如何防止用户被跟 踪，保护用户轨迹隐私的问题。目的是防止恶意攻击者在掌握用户的轨迹之后，威 胁用户的安全。当用户在敏感区域内运动时，必须有能力来隐藏他她的位置信息。 在一般的位置服务中，用户将含有自身位置信息和查询内容的请求信息发送给位置 服务器处理，一旦信息在传递到服务器的过程中被恶意攻击者窃听，那么恶意的攻 击者就会获得用户的位置信息。如果用户此时提出的是连续的查询服务请求，恶意 攻击者通过连续的窃听此用户的位置信息，掌握了该用户在不同时刻的位置信息， 能够很容易推断出该用户在这段时间内的运动轨迹。通常可以通过该用户的轨迹信 硕士学位论文 m a s t e r st h e s i s 息推断出许多隐私信息，例如可以推测出其工作地点、家庭住址、某些个人习惯等； 如果知道用户去了某个医院科室或者某个政治场所，能够推断出其健康状况、政治 宗教信仰等敏感信息。有报道称有人利用g p s 跟踪前女友，追踪监视本公司雇员行 踪等。用户轨迹隐私泄露甚至有可能使用户受到恶意攻击者的人身骚扰和人身攻 击，严重威胁用户的安全。这说明人们在享受位置服务的同时，也可能被人跟踪和 监视。因此，位置服务中如何保护用户的轨迹隐私不受侵犯是很有意义的研究课题。 1 2 国内外研究现状 关于位置隐私保护的方法和技术，国际上的研究已有很多，但仍有大量的关键 问题还需要进一步深入细致的研究。目前研究者们主要针对位置隐私保护系统的结 构、匿名方法和查询处理等三个方面做了很多工作。下面是位置服务中隐私保护方 法的研究进展。 s w e e n e y 2 l 最早提出的k 匿名方法是一种数据隐私保护技术，常应用于关系数据 库的数据发布。这种方法首先泛化数据记录的非敏感属性，使得发布后的数据中的 每条记录表示的个人信息都无法和其他肛l 条记录相区别，在一定程度上保护了数 据的隐私。但由于泛化后的数据记录中的敏感信息可能完全相同，恶意攻击者还可 能从表格中的记录推断出某个记录的敏感信息。针对这个问题，a s h w i n t 3 等人提出 - d i v e r s i t y 的隐私保护标准，在数据可用的情况下原始数据被分成多个等价类，每个 等价类中至少有，个不同的敏感值，使得在发布带有隐私信息的数据时，每条记录 无法与确定的个人匹配。文献【4 】通过理论和实验证明了- d i v e r s i t y 能提供更强的隐 私保护。这种k 匿名方法主要保护以记录形式记录在数据库中的数据的隐私，而数 据隐私与位置服务中的位置隐私有些很大区别，在第二章中会详细讲到。 g r u t e s e r 5 】最早提出把肛匿名方法用来解决位置隐私保护问题。位置k 匿名主要 是降低了用户的位置信息和身份标识i d 信息的可联系性，当至少k 个用户同时存 在于某个位置区域内时，如果这些用户之间无法通过标识信息相互区别，那么即便 攻击者获取了某个具体的位置信息，也很难从k 个用户中定位到该用户。用一个三 元组形式化的描述位置服务中的查询请求为：( i d ，l o c a t i o n , q u e r y ) ，其中i d 指用户 的标识信息，l o c a t i o n 指用户的位置信息，q u e r y 是用户提出的查询内容，三元组表 示用户i d 在位置l o c a t i o n 处提出了请求q u e r y 。假名1 6 】是一种特殊的匿名，用来隐藏 用户的真实i d ，即将查询信息提交给服务器的时候，用假名耐替换真实标识i d 。 这样即使恶意攻击者从服务器端得到用户的位置信息，也不知道是谁在此位置发出 了查询，达到了保护用户隐私的目的。 2 硕士学位论文 m a s t e r st h e s i s 从实现位置服务的过程来看，保护位置隐私主要从两个方面着手：第一，在查 询信息传到服务器之前进行位置匿名。位置匿名【_ 7 j 系统能够保证在攻击者获知某些 位置信息的情况下也无法将某个位置信息通过推理攻击的方式与确切的个人组织 机构相对应。在l b s 中对用户的位置运用某种方法进行匿名后能够保护用户的位置 隐私。第二，在位置服务器处进行隐私查询处理。由于经过匿名处理的位置信息是 多个位置的集合或者是一个模糊化的位置区域，而不是用户的准确位置信息。所以 传统移动对象数据库中的查询处理方式已经不再适用位置服务中处理器的查询处 理方式，而应当采用能够适应动态特征的位置隐私保护需求的查询处理方式，因为 前者的技术均以确切的位置信息为基础。因此，需要研究出新的适应这些动态特征 的隐私保护方法。 m o k b e l 等【8 】将位置区域化的思想与肛匿名方法相结合，提出了使用位置匿名 器，来处理大量并发用户的位置隐私保护方法。位置匿名器记录了所有订阅位置服 务的用户的信息，负责接收用户的位置请求并随着用户的移动不断更新位置信息。 这种在用户与位置服务器之间设置了第三方可信中间服务器( 即位置匿名器) 的中 心化体系结构有很明显的的缺点。第一，移动用户位置频繁的发生变化使得位置匿 名器容易成为系统处理的瓶颈。由于位置匿名器需要负责收集用户的位置信息，对 位置信息进行匿名处理以及查询结果的求精等工作，其处理速度将直接影响到整个 系统。如果位置匿名器由于负载过重而出现问题将会导致整个系统无法使用。第二， 一旦位置匿名器因为受到攻击者攻击而变的不可信，由于它掌握着所有用户的位置 信息和背景知识，将会导致严重的隐私泄漏。因此，研究者们大多采用分布式网络 系统结构。这种结构主要由移动用户和位置数据库服务器两部分组成。每个移动用 户都具有一定的计算能力和存储能力，都能够完成位置匿名和查询结果求精等工 作，节点用户之间相互信任、平等合作，能够避免中心服务器结构中位置匿名器的 两大缺点。位置数据库服务器提供基于位置的服务。下面介绍几种隐私保护方法。 1 、c l o a k p 2 p 1 9 】系统是在请求服务用户附近构建k 位置空间匿名区域的分布式系 统。欲发送请求的用户u 连接所有给定的物理半径，( 其中，是固定的系统参数) 之内的用户节点，如果节点数s 大于k ，就选择离材最近的k 个节点构成k 匿名空 间区域，完成位置匿名。然而这种方法有些缺陷，因为u 靠近匿名空间区域的中心， 攻击者通常能够以较高于1 k 的概率分辨出用户甜，这种攻击常被成为中心k 匿名 空间区域攻击，c l o a k p 2 p 方法比较容易遭受这种攻击。 2 、另一种是基于位置匿名查询的p r i v e l lu j ( 隐私保护) 方法。作者引入一种 分布式协议将用户聚集在类似b + 树的分层覆盖网络中( 每个用户对应一个数据点) ， 3 使用基于希尔伯特空间填充曲线的高级k 匿名空间区域构建方法，能够抵抗基于位 置的攻击。尽管p r i v e 系统具有良好的容错性及均衡负载的机制，但是由于对每 个用户的请求，必须从树根开始搜索用户信息，当用户数量或查询速率增加时，树 根不可避免的成为系统处理的瓶颈。 3 、可扩展的基于匿名位置查询的m o b i h i d e l l l j ( 移动位置保护) 方法。 m o b i h i d e 方法能够保证k 匿名并达到很高的隐私保护水平，同时具有较好的均衡 负载和容错特性，消除p r i v e 系统中的瓶颈问题，比较适合大量移动用户的实时 应用中，尤其强调了m o b i h i d e 对位置关联攻击的有效性，能够很好地保护用户 的轨迹隐私。不久，有研究者又提出了不使用匿名器而直接对位置服务器进行隐私 信息查询( p r i v a c yi n f o r m a t i o nr e t r i v e ，p i r ) t 1 6 j 的方法，服务器在不知道用户位置信 息的情况下执行隐私信息查询返回一个查询的范围，在用户端完成查询结果的求 精。这种方法使用加密思想来保护用户的位置隐私和轨迹隐私。 轨迹隐私是位置隐私保护的一个方面，近几年来越来越受到研究者们的关注。 t h o m a sj 和l i ul i n g t l 2 】提出了一种运用个性化位置k 匿名模型来保护用户的位置隐 私信息的方法。在l b s s 与用户之间设置了可信的位置匿名器，移动用户在提出位 置服务请求时可以指定想要的k 匿名水平和可接受的最大时间和空间容忍度，在匿 名器中执行位置匿名处理，比如分离位置信息与身份标识等。该方法的另一个特点 是在可信的匿名服务器上设置了高效的位置信息扰动引擎，它可以运用位置隐形算 法对信息进行模糊处理，使匿名服务器增加了将身份与位置信息关联的难度。位置 信息扰动算法适当降低了位置信息的精确性防止服务提供方滥用真实的位置信息， 同时又能保证一定的服务质量。文献 1 3 ，1 4 】提出了s i l e n tp e r i o d 轨迹隐私保护方法， 该方法把用户所在的空间区域分为混合区域( m i x z o n e ) 和应用区域。该方法的 主要思想是在相互邻近的多个用户之间构造混合区域，当用户在混合区域中运动时 ( 也被称为s i l e n tp e r i o d ) 不会提出查询请求，也不会接收服务信息。用户在混合区 域中交换标识信息i d ，进出混合区域前后使用不同的身份标识，这样即使攻击者得 到了用户的位置信息，也难以将用户进入混合区域前后的位置信息与其身份标识联 系起来，保护了用户的轨迹隐私。用户在应用区域时才能正常通信，接受位置服务。 显然，用户在s i l e n tp e r i o d 期间没有任何通信，轨迹隐私保护将会导致通信服务质 量的下降，这对某些对服务质量有很高要求的应用是不合适的。h u a n g 等人1 9 1 扩展 了s i l e n tp e r i o d 的思想，提出了s i l e n tc a s c a d e 的方法，将多个m i x z o n e 级联形成m i x 网络模型，利用得到的网络模型可以构建最佳的s i l e n tc a s c a d e 结构。主要思想是从 时间和空间两个方面来对用户的位置信息进行匿名处理，通过平衡用户在混合区域 4 中的停留时间和用户的匿名程度，在不降低服务质量的前提下，使恶意攻击者难以 将任何两个或多个用户的位置信息连接起来，从而对用户的轨迹隐私提供了更强的 保护。 h u b e r t 和r o b e r t l l 5 】中利用了g p s 定位系统的模糊性质，提出了可变区域的概 念，当两个用户距离很近时，g p s 系统由于误差不能准确地辨别用户的身份，返回 的两个用户的位置区域可能是重合的或者离的很近，这个区域被称作可变区域，此 时双方的轨迹也可能重合或相近。这样，在可变区域内根据真实的轨迹信息自动形 成虚拟的用户，多个用户的运动轨迹( 真实的和虚拟的) 相交形成的轨迹记录使攻 击者分析辨别目标用户的真实轨迹更加困难，从而很好的保护了用户的轨迹隐私。 g r u t e s e r 1 6 等人提出了强匿名和弱匿名的概念，强匿名即k 匿名，其保护作用取决 于k 值的大小。弱匿名采用路径分割或微型压缩两种保护方案切断位置信息间的联 系来达到保护轨迹隐私的目的。路径分割把用户走过的道路分割成几个段，攻击者 能在一个路段鉴别出用户，但是无法了解到用户经过的其他路段的位置。微型压缩 则试图隐藏轨迹信息的显著特征。 分析以上的这些方法可以看出当前研究者主要从考虑切断用户的连续两个或 多个位置的可连接性，通过增加连接用户多个位置的难度的角度来考虑保护移动用 户的轨迹隐私。因为在位置匿名系统中攻击者一般是截取向l b s s 发送的服务请求， 其中携带的一定是多个用户的真实位置信息，所以通过位置信息的关联性有可能推 断出用户真实的轨迹信息。针对这个问题，我们将匿名技术用于分布式点对点网络 环境下，提出了基于转发查询的轨迹隐私保护方法。 1 3 本文的主要研究内容 随着l b s 的大量应用，其中的安全问题也越来越突出。用户对位置隐私的保护 需求越来越强。本文主要是针对位置服务中的轨迹隐私提出一种基于转发查询的轨 迹隐私保护方法，并阐述了该方法在移动用户使用位置服务时如何保护位置信息的 隐私，最后通过仿真实验和比较验证了该方法的有效性。本文的具体内容有以下几 个方面： ( 1 )了解位置服务中位置隐私保护的重要性。深入了解位置隐私保护方法的 研究背景和现状，综合归纳当前现有的位置隐私保护方法和策略，提出 了连续位置服务中的轨迹隐私保护是当前需要研究的一个重要课题。 ( 2 ) 提出位置隐私的概念，对移动环境下位置隐私进行分析。概括当前存在 硕士学位论文 m a s t e r st h e s i s 的各种位置隐私保护方法及其优缺点。提出轨迹隐私的概念，研究当前 轨迹隐私保护方法的主要思想，针对连续位置服务中的轨迹隐私保护方 法的研究，提出了基于转发查询的轨迹隐私保护策略，然后详细介绍了 此方法所使用的算法和实现过程。 ( 3 ) 通过仿真实验证明了采用基于转发查询的轨迹隐私保护方法的位置服务 系统在匿名强度、用户加入或退出网络系统时的时延和通信代价以及和 负载均衡能力方面的有效性，与已有的m o b i h i d e 方法相比，能提供更 强的轨迹隐私保护能力。 1 4 本文的内容安排 本文的结构可以将本文分为五个章节来阐述： 第一章是绪论。首先阐述了论文课题研究的重要性和意义，然后介绍和分析了 国内外研究的现状，最后提出了本文主要研究的内容与各章节的安排。 第二章是对位置隐私保护的综述。首先提出了位置服务的概念和实际应用，指 出了位置服务中的安全问题，阐述了位置隐私保护的重要性。其次文中详细的介绍 了移动环境下位置隐私的特点以及三种用于保护位置隐私的思想方法及其优缺点。 最后提出了本文主要研究的位置服务中轨迹隐私保护的概念以及目前最新的轨迹 隐私保护方法。 第三章提出了一种基于转发查询的轨迹隐私保护方法。通过使用希尔伯特算法 将移动用户的二维的位置信息转化成一维的用户关键字序列，然后用c h o r d 分布式 协议将用户自组织成一个p 2 p 系统。采用转发查询的思想切断了用户前后位置信息 的连接性，从而保护了用户的轨迹隐私。 第四章对基于转发查询的轨迹隐私保护方法进行仿真实验，通过与其他系统的 比较验证其对轨迹隐私保护的有效性。 第五章：总结与展望。对本文所做的工作进行了总结，并指出需要进一步完善 和改进的地方。 6 硕士学位论文 m a s t e r st h e s i s 第二章位置服务中的隐私保护 近年来，随着移动通讯技术和无线传感网络技术的进步，定位技术不断成熟， l b s 提供商不断增加，l b s 的应用领域不断扩大。l b s 不仅能够为人们社会生活带 来方便的服务，还将给市场带来很大的商业利益。基于位置的服务通常借助互联网 或无线网络，在固定用户或移动用户之间，完成定位和服务这两大功能。通常l b s 在应用中存在各种各样的安全问题，用户担心在使用位置服务时会泄露个人隐私信 息。因此，隐私保护问题是位置服务中的一项重要的研究内容。本章将详细介绍位 置服务中的隐私保护问题。 2 1l b s 概述 2 1 1l b s 的概念 位置服务是指通过无线通信设备和定位技术获得移动用户的位置信息( 如经纬 度的坐标数据) ，将此信息提供给移动用户本人、他人或应用系统，以实现各种与 当前用户位置相关的服务。据微软的最新调查结果显示l b s 位置服务拥有很大的用 户群，其中7 0 使用g p s 导航，4 6 使用天气提醒功能，3 8 想要获取更新的路况 信息，3 8 想要获取饭店信息及点评，3 6 用来查找附近便利服务，只有1 8 的用 户使用l b s 社交服务和1 0 的用户玩l b s 游戏。随着l b s 能够不断的为人们解决 许多实际问题，将会产生巨大的商业价值，近1 5 的受访者把基于地理的零售视为 广告，其中4 6 的用户表示会因为这些广告去访问店铺或者使用折扣券。 一个l b s 系统中，通信主体通常是移动用户、基站和位置数据库服务器，结构 如图2 1 。移动用户是网络位置服务的请求者，通常携带带有定位功能的移动设备 ( 如手机，导航仪等) ；基站是向用户提供位置应用服务的实体，它收集用户的个 人信息( 包括位置信息) 并根据用户的标识信息确定是否给予对位置服务器的访问 权限，然后把合法的位置服务请求发送到位置服务器；位置服务器运用定位系统来 得到用户的位置信息，提供不同服务质量和不同水平的位置信息。位置服务器可以 完成的位置服务请求的类型取决于所使用的移动技术、定位技术和环境条件。 7 硕士学位论文 m a s t e r st h e s i s 侈动用户 服务请求回应 i - 白 一曰 位置服务器 图2 - 1l b s 系统的结构图 三个通信主体之间是通过相互发送请求回应信息来交换的。当基站接收到请求 者的关于位置信息的服务请求，就请求位置服务器查找相关的位置信息，同时要采 用一些通信协议来协商服务质量、服务代价和其他相关的应用参数。位置服务器根 据请求处理相关的请求，基站接收到来自位置服务器位置信息后，将要查询的信息 发给请求者。实质上，定位功能是完全嵌入到具体的可以提供类似位置服务的实体 中的，能够根据不同的技术达到不同程度的服务水平。 2 1 2l b s 的应用 学术界和企业界已经提出了多种l b s 在商业、社交和情报收集等方面的应用。 大体上，l b s 服务可以分为以下几类： ( 1 ) 定位服务。这种服务是基站返回查询用户的具体位置信息，通常用于第 三方需要知道用户位置才能执行任务的情况。定位服务是l b s 服务的基础服务。 ( 2 ) 查找附近的便利服务。这种服务提供用户位置周围感兴趣的便利服务， 比如相关的旅行指导，天气提醒和附近的交通状况等。只要订阅了这些服务的用户 都能通过携带的移动设备接收到实时的服务信息。 ( 3 ) 社交服务。这种服务可以实时地提供用户位黄附近使用l b s 服务的用户 信息，可用于社会网络交友、发送免费电子购物券或折扣券、电子广告等商业应用。 用户会根据这些广告去访问店铺或者使用折扣券。 ( 4 ) 跟踪服务。l b s 可用于监控用户的运动和遥感勘测服务( 比如观察移动 对象的运动速度，方向等) 。例如车辆跟踪解救过迷途的司机，看护孩子、监控雇 员的行为、危险区域提醒等。据海外媒体报道，美国联邦通信委员会( f e d e r a l c o m m u n i c a t i o n sc o m m i s s i o n ) 要求美国运营商网络中9 5 的手机必须能由卫星或通 讯基站网络跟踪，其目的是让人在处于紧急情况下更容易得到帮助。 ( 5 ) 导航服务。移动用户可以查询从当前位置到达目的地所要走的路线，这 种服务也需要跟踪服务来不断地收集移动用户的当前位置。 l b s 应用非常广泛，尤其重要和关键的个应用是提供精确的位置信息能够保 8 硕士学位论文 m a s t e r st h e s i s 护人的生命。比如配备g p s 功能的手机可以向卫星传送信号，在中国的1 1 0 ( 报警) 、 1 2 0 ( 紧急医疗救助) 、1 1 9 ( 火灾救援) 服务中，可以使警察和救援人员能够确定 需要救助者的位置。 2 1 3l b s 中的安全问题 位置服务中通常需要将移动用户自身的位置信息提供给基站和位置服务器才 能享受到相应的服务。位置信息的精确度会影响到服务的质量，但这样也为恶意攻 击者窃取用户的位置隐私敞开了大门，不法人员会利用这些隐私信息威胁用户的安 全。位置隐私威胁【7 】是指攻击者出于某种利益或恶意目的在未用户经授权的情况下， 通过窃听位置信息传输通道、攻击位置服务器等方式获得用户原始的位置数据或者 请求信息内容，从而对用户个人隐私造成的威胁。一般来讲位置服务中的隐私可以 分为两种：位置隐私和查询隐私。如张某提出“寻找1 5 分钟内距离我最近的肿瘤 医院”。这是位置服务中常见的连续最近邻查询。一方面，用户不愿意其他人知道 他现在的位置( 如“医院 ) ，属于位置隐私范畴；另一方面用户也不想让任何人获 知自己提出了什么内容的查询请求，如与某特定肿瘤相关的医院查询，这属于查询 隐私范畴。 泄露位置隐私通常有三种途径【7 】：( 1 ) 从位置设备或者从位置服务器中直接获 取用户的位置信息；( 2 ) 通过观察被攻击者行为直接获取位置信息；( 3 ) 通过与位 置相关的背景知识分析推理来确定在某位置发送某消息的用户。在基于位置的服务 中主要存在两类位置隐私问题，一是攻击者知道用户某个时刻位置信息，即位置隐 私。另一类是攻击者知道用户的多个连续位置信息，即轨迹隐私。攻击者如果多次 截取了用户的位置服务请求信息，就能将用户在不同时刻的位置信息连接起来得到 用户在某段时间内的运动轨迹，通过用户的轨迹信息有可能推测出用户的行为模 式，威胁到用户的隐私。例如，用户去某个医院或者政治场所，能够推断出其健康 状况、政治宗教信仰等敏感信息；获得用户的轨迹还可能了解到其工作地点、家庭 住址、个人习惯等，甚至有可能使用户受到恶意攻击者的人身骚扰和攻击，严重威 胁用户的隐私。 位置服务中的隐私安全问题是位置服务未能广泛使用的主要因素，很多潜在的 用户担心自己的隐私受到威胁而放弃使用。在未来的移动网络环境下，位置服务将 会创造更多的商业价值，因此本文对位置服务中隐私保护问题的研究有很大的意 义。 9 硕士学位论文 m a s t e r st h e s i s 2 2 位置服务中的隐私保护 2 2 1 位置隐私保护 信息隐私【l 】是由移动对象自身定义的与他人共享信息的方式和内容；位置隐私 【5 】是一种与位置信息相关的信息隐私，指的是保护移动对象自身的位置信息不被其 他人通过任何手段获得。位置隐私保护是阻止其他任何对象知道其当前或历史位置 信息的能力。缺少位置隐私保护有时会使用户成为被欺骗攻击的目标，比如1 ) 收 到了垃圾短信，这表示在未经用户同意的情况下某些不可信服务者就发现了用户的 位置，并提供虚假信息；2 ) 受到攻击或者骚扰。如果是不法人员知道了用户的位 置可能会实施物理攻击或者人身骚扰，严重危害用户的人身安全；3 ) 用户的资料 分析，如果恶意攻击者还掌握了用户的身份等数据，又能知道其位置信息，有时可 以推断出用户其他的敏感信息。 位置服务中的主体是服务提供者和提出查询的用户。用户提供相关的位置信息 才能获得相应的位置服务。有时用户为了保护其位置隐私，会提供不准确的或者不 正确的位置信息给位置服务器，位置服务器根据这种位置信息查询处理得到的结果 可能会是用户不感兴趣的，这样就失去了位置服务存在的意义；反之，位置服务器 需要获得用户的准确位置信息，才能提供高质量的服务，同时减轻位置服务器信息 处理的负载。因此，如何平衡位置隐私保护和服务质量之间的矛盾是位置服务中位 置隐私保护的核心问题。 位置隐私信息由标识信息和位置信息组成【4 】。根据组成位置隐私的两种信息可 将位置隐私保护方法分为两类，一类是隐藏用户的标识而提供真实的位置信息，得 到高质量的服务；另一类是公开用户的真实标识信息，但隐藏用户具体位置信息， 即把构建的包含用户的位置区域( 比如k 匿名区域) 作为位置信息提