位置服務與隱私保護

1、 位置位置 服務服務 簡言之，就是簡言之，就是基于地理位置數(shù)據(jù)基于地理位置數(shù)據(jù)而展開的服務。是指通而展開的服務。是指通 過移動終端和無線通訊網(wǎng)絡（或衛(wèi)星定位系統(tǒng)）的相互過移動終端和無線通訊網(wǎng)絡（或衛(wèi)星定位系統(tǒng)）的相互 配合，以空間數(shù)據(jù)庫為基礎，確定移動用戶的實際地理配合，以空間數(shù)據(jù)庫為基礎，確定移動用戶的實際地理 位置或坐標，并將其與其他信息整合起來，為用戶提供位置或坐標，并將其與其他信息整合起來，為用戶提供 所需要的與位置相關(guān)的增值服務。所需要的與位置相關(guān)的增值服務。 LBS LBS：Location Based Service Services that intergrate a mobi

2、le devices location or position with other information so as to provide added value to a user GPS SENSOR RFID 緊急救援服務緊急救援服務 信息娛樂服務信息娛樂服務 分發(fā)服分發(fā)服 務務 交通導航交通導航 跟蹤服務跟蹤服務 定位最近的救援者位置定位最近的救援者位置 查找距離我百米內(nèi)最近的銀行查找距離我百米內(nèi)最近的銀行 向我餐館向我餐館500500米范圍內(nèi)的用戶發(fā)送電子優(yōu)惠券米范圍內(nèi)的用戶發(fā)送電子優(yōu)惠券 查找到達目的地的最優(yōu)路徑查找到達目的地的最優(yōu)路徑 對航空物流進行追蹤對航空物流進行追蹤 位

3、置服務前景廣闊位置服務前景廣闊. 20072007年以來中國位置服務市場規(guī)模及增長年以來中國位置服務市場規(guī)模及增長 市場規(guī)模市場規(guī)模 位置服務前景廣闊位置服務前景廣闊. 用戶數(shù)量用戶數(shù)量 20072007年以來中國位置服務用戶規(guī)模及增長年以來中國位置服務用戶規(guī)模及增長 全球及國內(nèi)移動位置服務市場發(fā)展階段對比全球及國內(nèi)移動位置服務市場發(fā)展階段對比 位置服務位置服務 （LBS） 軍事產(chǎn)業(yè)軍事產(chǎn)業(yè) 政府事務政府事務 求助服務求助服務 追蹤監(jiān)控追蹤監(jiān)控 定位導航定位導航 休閑娛樂休閑娛樂 分發(fā)服務分發(fā)服務 Form oracle 位置服務前景廣闊位置服務前景廣闊. 使用領域 也許某天，當你經(jīng)過熟悉的星

4、巴克，也許某天，當你經(jīng)過熟悉的星巴克， 打開手機記錄你的位置，卻驚喜地發(fā)打開手機記錄你的位置，卻驚喜地發(fā) 現(xiàn)一位好友也正在這里享用咖啡。而現(xiàn)一位好友也正在這里享用咖啡。而 在不遠處的商場內(nèi)，某件你關(guān)注了很在不遠處的商場內(nèi)，某件你關(guān)注了很 久的名牌襯衫正在打折久的名牌襯衫正在打折 又或者你去一個遙遠的城市旅行，打又或者你去一個遙遠的城市旅行，打 開手機，卻發(fā)現(xiàn)自己瞬間對這個陌生開手機，卻發(fā)現(xiàn)自己瞬間對這個陌生 的地方變得如此熟悉，想去哪兒就能的地方變得如此熟悉，想去哪兒就能 隨心所欲，想玩什么立馬就能朝著目隨心所欲，想玩什么立馬就能朝著目 標出發(fā)標出發(fā)此時，你肯定會為位置服此時，你肯定會為位置服

5、 務所帶來的便捷生活方式而興奮！務所帶來的便捷生活方式而興奮！ 可是你又是否設想過，未來，無可是你又是否設想過，未來，無 論你走到哪里，上班，下班，旅論你走到哪里，上班，下班，旅 行亦或是散步，都會有漫天飛舞行亦或是散步，都會有漫天飛舞 的各種廣告鋪天蓋地向你席卷而的各種廣告鋪天蓋地向你席卷而 來，你無處躲藏，只能被淹沒在來，你無處躲藏，只能被淹沒在 信息的垃圾中煩惱嘆息信息的垃圾中煩惱嘆息 甚至有一天，對你而言，無論是熟甚至有一天，對你而言，無論是熟 悉的親朋還是陌生人，都沒有了秘悉的親朋還是陌生人，都沒有了秘 密，每天無論你走到哪兒，干了什密，每天無論你走到哪兒，干了什 么，將要去哪，甚至

6、你最近喜歡什么，將要去哪，甚至你最近喜歡什 么，想要計劃什么，大家都能知道么，想要計劃什么，大家都能知道 的時候，你會不會又對這一新興的的時候，你會不會又對這一新興的 服務產(chǎn)生恐懼呢。服務產(chǎn)生恐懼呢。 如何解決位置服務如何解決位置服務 中堪憂的隱私保護中堪憂的隱私保護 問題呢？問題呢？ 內(nèi)內(nèi) 容容 導導 覽覽 導引：隱私保護問題導引：隱私保護問題 隱私保護的系統(tǒng)結(jié)構(gòu)隱私保護的系統(tǒng)結(jié)構(gòu) 隱私保護模型與匿名技術(shù)隱私保護模型與匿名技術(shù) 隱私保護的算法實現(xiàn)隱私保護的算法實現(xiàn) 4 隱私問題舉例隱私問題舉例 生活中這樣的例子很常見：張某利用自己 帶有GPS的手機提出了“尋找距離我（現(xiàn)在 所在位置）最近的腫

7、瘤醫(yī)院”的查詢。這 是導航系統(tǒng)中一個普通的最近鄰查詢（即 NN查詢）。此查詢被提交給服務提供商， 比如Google Maps，再由服務提供商通過查 詢空間數(shù)據(jù)庫返回給用戶查詢結(jié)果。 此時涉及到的隱私問題包含兩個方面：一是用此時涉及到的隱私問題包含兩個方面：一是用 戶不想讓人知道他此刻所在的位置戶不想讓人知道他此刻所在的位置, ,比如銀行。比如銀行。 二是用戶不想讓任何人知道自己提出了某方面二是用戶不想讓任何人知道自己提出了某方面 的查詢，如張某不想讓人知道自己將去腫瘤醫(yī)的查詢，如張某不想讓人知道自己將去腫瘤醫(yī) 院。院。 4 位置服務中的隱私泄露位置服務中的隱私泄露 查詢隱私泄露查詢隱私泄露 其

8、他人以任何方式獲知對象過去或現(xiàn)在的位置。 位置隱私泄露位置隱私泄露 查詢請求的內(nèi)容，可能透露用戶的行為模式（如經(jīng)常走的 道路及經(jīng)過的頻率）、興趣愛好（如喜歡去哪個商店、哪 種俱樂部）、健康狀況（如經(jīng)常去的心理咨詢診所）以及 政治傾向等個人隱私信息。 4 隱私泄露的三種途徑隱私泄露的三種途徑 觀察（觀察（Observation） 攻擊者從位置設備或者位置服務器中直接獲取用戶的位置信 息。（如利用手機內(nèi)置GPS定位導致的位置信息泄露） 直接交流（直接交流（Direct Communication） 攻擊者通過“位置”連接外部的數(shù)據(jù)源（或者背景知識） 從而確定在該位置或者發(fā)送該消息的用戶。（如查詢信

9、息A 是從別墅B發(fā)出的，當攻擊者知道別墅B的主人是C這一背景 時，那么就能確定A是由C發(fā)出的） 攻擊者通過觀察被攻擊者的行為直接獲取位置信息。（如 攻擊者跟蹤被攻擊者） 連接泄露（連接泄露（Link Attack） 4 位置服務中的隱私保護位置服務中的隱私保護 查詢隱私保護查詢隱私保護 避免用戶與某一精確位置匹配。避免用戶與某一精確位置匹配。 位置隱私保護位置隱私保護 避免用戶與某一敏感查詢匹配。避免用戶與某一敏感查詢匹配。 4 尋找一種狀態(tài)，在這種尋找一種狀態(tài)，在這種 狀態(tài)下很多對象組成一狀態(tài)下很多對象組成一 個集合（匿名集），從個集合（匿名集），從 集合的外面向里看，組集合的外面向里看，組

10、 成集合的各個對象無法成集合的各個對象無法 被區(qū)分，使得某一個位被區(qū)分，使得某一個位 置的信息無法與確切的置的信息無法與確切的 個人個人/ /組織組織/ /機構(gòu)相匹配機構(gòu)相匹配 。 位置信息經(jīng)過匿名處理位置信息經(jīng)過匿名處理 后不再是用戶的真實位后不再是用戶的真實位 置，可能是多個位置的置，可能是多個位置的 集合或者一個模糊化的集合或者一個模糊化的 位置，查詢系統(tǒng)應該對位置，查詢系統(tǒng)應該對 應地返回包含真實查詢應地返回包含真實查詢 信息的模糊信息集信息的模糊信息集 隱私保護的工作隱私保護的工作 位置匿名位置匿名查詢處理查詢處理 4 位置服務位置服務VS隱私保護隱私保護 魚與熊掌可否兼得？魚與熊掌

11、可否兼得？ 位置服務位置服務隱私保護隱私保護 提供精確位置提供精確位置隱藏用戶位置隱藏用戶位置 不能兼得！只能尋找平衡點！不能兼得！只能尋找平衡點！ 在最少的位置暴露下獲得最好的服務，使在最少的位置暴露下獲得最好的服務，使 隱私暴露處于隱私暴露處于“可控狀態(tài)可控狀態(tài)”！ 隱私保護的特點隱私保護的特點 保護位置隱私與享受服務是一對矛盾保護位置隱私與享受服務是一對矛盾 位置信息的多維性特點位置信息的多維性特點 位置匿名的即時性特點位置匿名的即時性特點 基于位置匿名的查詢處理基于位置匿名的查詢處理 位置隱私需求個性化位置隱私需求個性化 隱私保護的系統(tǒng)結(jié)構(gòu)隱私保護的系統(tǒng)結(jié)構(gòu) Non-cooperati

12、ve Architecture 獨立結(jié)構(gòu)獨立結(jié)構(gòu) 中心服務器結(jié)構(gòu)中心服務器結(jié)構(gòu) Centralized Architecture 分布式點對點結(jié)構(gòu)分布式點對點結(jié)構(gòu) Peer-to-peer Architecture 僅有客戶端與位置數(shù)據(jù)庫服務器的僅有客戶端與位置數(shù)據(jù)庫服務器的C/SC/S結(jié)構(gòu)。該結(jié)構(gòu)需結(jié)構(gòu)。該結(jié)構(gòu)需 要移動用戶擁有具有強大定位、計算、存儲能力的設要移動用戶擁有具有強大定位、計算、存儲能力的設 備，自己完成位置匿名和查詢結(jié)果求精。備，自己完成位置匿名和查詢結(jié)果求精。 在用戶和位置數(shù)據(jù)庫服務器之間加入第三方可信中間在用戶和位置數(shù)據(jù)庫服務器之間加入第三方可信中間 件件位置匿名服務器，

13、并由位置匿名服務器完成匿位置匿名服務器，并由位置匿名服務器完成匿 名處理和查詢結(jié)果求精。名處理和查詢結(jié)果求精。 由客戶端和位置數(shù)據(jù)庫服務器組成，移動客戶端根據(jù)由客戶端和位置數(shù)據(jù)庫服務器組成，移動客戶端根據(jù) 匿名算法找到其他一些移動用戶組成一個匿名組，以匿名算法找到其他一些移動用戶組成一個匿名組，以 此進行位置匿名。同時組內(nèi)的客戶端之間的節(jié)點具有此進行位置匿名。同時組內(nèi)的客戶端之間的節(jié)點具有 平等性，共同協(xié)調(diào)完成查詢結(jié)果求精。平等性，共同協(xié)調(diào)完成查詢結(jié)果求精。 獨獨 立立 結(jié)結(jié) 構(gòu)構(gòu) 缺點：缺點：對客戶端要求高；對客戶端要求高； 缺乏全局信息，隱蔽性弱缺乏全局信息，隱蔽性弱 優(yōu)點：優(yōu)點：結(jié)構(gòu)簡單

14、，易于配置結(jié)構(gòu)簡單，易于配置 處理流程：處理流程：將匿名后的位置連帶查詢一起發(fā)送將匿名后的位置連帶查詢一起發(fā)送 給位置數(shù)據(jù)庫服務器；位置服務器根據(jù)匿名的給位置數(shù)據(jù)庫服務器；位置服務器根據(jù)匿名的 位置進行查詢處理并將候選結(jié)果集返回給用戶；位置進行查詢處理并將候選結(jié)果集返回給用戶； 用戶根據(jù)真實位置挑選出真正的結(jié)果。用戶根據(jù)真實位置挑選出真正的結(jié)果。 獨立結(jié)構(gòu)示意圖獨立結(jié)構(gòu)示意圖 優(yōu)優(yōu) 點點缺缺 點點 中心服務器結(jié)構(gòu)中心服務器結(jié)構(gòu) 處理過程處理過程：（：（1 1）用戶發(fā)送包含精確位置的查詢請求給位置匿名服務器。（用戶發(fā)送包含精確位置的查詢請求給位置匿名服務器。（2 2）匿）匿 名服務器使用某種匿名

15、算法完成位置匿名后，將匿名后的請求發(fā)送給位置數(shù)據(jù)庫名服務器使用某種匿名算法完成位置匿名后，將匿名后的請求發(fā)送給位置數(shù)據(jù)庫 服務器。（服務器。（3 3）位置數(shù)據(jù)庫服務器根據(jù)匿名區(qū)域進行查詢處理，并將查詢結(jié)果的）位置數(shù)據(jù)庫服務器根據(jù)匿名區(qū)域進行查詢處理，并將查詢結(jié)果的 候選集返回給位置匿名服務器。（候選集返回給位置匿名服務器。（4 4）位置匿名服務器從候選結(jié)果集中挑出真正）位置匿名服務器從候選結(jié)果集中挑出真正 的結(jié)果返回給移動用戶。的結(jié)果返回給移動用戶。 具有全局信息，具有全局信息， 隱私保護效果好。隱私保護效果好。 位置匿名服務器位置匿名服務器 成為系統(tǒng)的瓶頸；成為系統(tǒng)的瓶頸； 位置匿名服務器位

16、置匿名服務器 還可以成為隱私還可以成為隱私 泄露的唯一攻擊泄露的唯一攻擊 點。點。 分布式點對點結(jié)構(gòu)分布式點對點結(jié)構(gòu) ThemeGallery is a Design Digital Content S=S (ID，xr,yr，vmax，tr，h) ; 返回S 到服務的請求者； （1 1）當請求的接收者）當請求的接收者 r r 接收到來自服接收到來自服 務請求者務請求者m m（可能是請求的發(fā)起者，也可（可能是請求的發(fā)起者，也可 能是請求的轉(zhuǎn)發(fā)者）的查找請求后：首能是請求的轉(zhuǎn)發(fā)者）的查找請求后：首 先基于消息序號先基于消息序號 ID ID 請求的接收者請求的接收者 r r檢檢 查該請求是否為一個

17、重復的請求。若是，查該請求是否為一個重復的請求。若是， 則返回一個則返回一個 ACK ACK 消息。否則，基于消息。否則，基于 h h 的大小處理請求。的大小處理請求。 （2 2）當）當 h=1h=1（單跳單跳） 時，時，r r 返回一個返回一個 包含包含 IDID、當前位置、最大運動速度、時、當前位置、最大運動速度、時 間戳和跳數(shù)的元組間戳和跳數(shù)的元組(ID(ID，xxr r,y,yr r ，v vmax max， ， t tr r，h)h)給請求者；給請求者； （3 3）當）當 h1 h1 （多跳多跳）時，）時，r r 遞減遞減 h h 的的 值，再向周圍用戶發(fā)送原始的消息序號值，再向周圍

18、用戶發(fā)送原始的消息序號 ID ID 來廣播查找請求。來廣播查找請求。r r 監(jiān)聽整個網(wǎng)絡，監(jiān)聽整個網(wǎng)絡， 等待周圍用戶的響應，直到收集到所有等待周圍用戶的響應，直到收集到所有 其周圍用戶的回復。最后，其周圍用戶的回復。最后，r r 分別遞增分別遞增 收集到的元組中的收集到的元組中的 h h 值，同時將自己的值，同時將自己的 元組信息一起添加到已收集的元組中構(gòu)元組信息一起添加到已收集的元組中構(gòu) 成集合成集合 S S，返回給請求的發(fā)起者或轉(zhuǎn)發(fā)，返回給請求的發(fā)起者或轉(zhuǎn)發(fā) 者者 r r。 基于基于P2P的位置匿名算法實現(xiàn)的位置匿名算法實現(xiàn) do 以以多跳多跳形式開始廣播查找請求；形式開始廣播查找請求；

19、 S 是經(jīng)過多跳形式返回的已找到的用戶集合，則是經(jīng)過多跳形式返回的已找到的用戶集合，則 k=s； if (flag = = 0) then 服務請求者服務請求者中心位置的調(diào)整中心位置的調(diào)整； flag=1； if ( k k-1) then if (S = S| h=hmax) then 請求掛起；請求掛起； h = h+1； S =S； while (k= k-1)； 當請求的發(fā)起者當請求的發(fā)起者 m 經(jīng)過一次查經(jīng)過一次查 找請求后得到的用戶數(shù)小于找請求后得到的用戶數(shù)小于 k-1 時，時， 它將繼續(xù)遞增它將繼續(xù)遞增 h的值，并且以一個的值，并且以一個 新的消息序號新的消息序號 ID 重新廣播請求，重新廣播請求， 重復此過程，直到找到重復此過程，直到找到 k-1 個用戶。個用戶。 值得注意的是，如果在兩次連值得注意的是，如果在兩次連 續(xù)的廣播后得到的結(jié)果集相同，或續(xù)的廣播后得到的結(jié)果集相同，或 者，當跳數(shù)者，當跳數(shù) h 的值超過規(guī)定的最大的值超過規(guī)定的最大 跳數(shù)時，跳數(shù)時，m 則需要釋放他的隱私檔則需要釋放他的隱私檔 案，選擇一個更小的案，選擇一個更小的 k 值，或是將值，或是將 請求掛起一段時間，隨即再次發(fā)出請求掛起一