位置大數(shù)據(jù)服務中基于差分隱私的數(shù)據(jù)發(fā)布技術

張琳，劉彥，王汝傳

（1. 南京郵電大學計算機學院，江蘇 南京 210003；2. 江蘇省無線傳感網(wǎng)高技術研究重點實驗室，江蘇 南京 210003；3. 南京郵電大學寬帶無線通信與傳感網(wǎng)技術教育部重點實驗室，江蘇 南京 210003）

位置大數(shù)據(jù)服務中基于差分隱私的數(shù)據(jù)發(fā)布技術

張琳1,2,3，劉彥1，王汝傳1,2,3

（1. 南京郵電大學計算機學院，江蘇 南京 210003；2. 江蘇省無線傳感網(wǎng)高技術研究重點實驗室，江蘇 南京 210003；3. 南京郵電大學寬帶無線通信與傳感網(wǎng)技術教育部重點實驗室，江蘇 南京 210003）

應對多組合復雜攻擊及前景知識攻擊，提出一種新的基于差分隱私保護機制的位置大數(shù)據(jù)發(fā)布模型，創(chuàng)新設計可用性評估反饋機制模塊，引入時間變量動態(tài)地針對敏感屬性以及身份識別等分析模型的服務質(zhì)量，能在位置大數(shù)據(jù)與非位置大數(shù)據(jù)相結(jié)合、用戶背景知識不確定等情況下保護用戶的位置隱私。仿真實驗基于多種空間索引技術驗證了新發(fā)布模型能夠在指定的私密性條件下，為位置查詢服務發(fā)布具有更高準確率的匿名數(shù)據(jù)。

位置服務；大數(shù)據(jù)；差分隱私；數(shù)據(jù)發(fā)布；隱私保護

1 引言

移動通信與傳感設備等位置感知技術的快速發(fā)展使人們正式步入大數(shù)據(jù)信息時代，位置大數(shù)據(jù)服務產(chǎn)品不僅為用戶提供了便捷的服務，如興趣點（POI，points of interest）查找、社交網(wǎng)絡位置分享等，針對收集到的海量位置數(shù)據(jù)也為企業(yè)提供了分析數(shù)據(jù)特點的查詢業(yè)務，為企業(yè)挖掘有價值的商業(yè)信息提供便利。隨著個人隱私保護意識的不斷提高，對海量異構(gòu)數(shù)據(jù)的安全發(fā)布與分析成為大多數(shù)企業(yè)亟待解決的問題。對位置大數(shù)據(jù)服務的惡意訪問可能泄露個人大量的敏感信息[1,2]，如觀察到用戶出現(xiàn)在醫(yī)院附近，可以推測出用戶大致的健康狀況；查詢用戶對興趣地點的訪問頻率，可分析用戶偏好和經(jīng)濟狀況；此外，還可考慮用戶軌跡開始和結(jié)束的地點，推測出用戶的家庭住址等信息。特別是對大數(shù)據(jù)服務中的位置信息與社交網(wǎng)絡中非位置信息相結(jié)合的攻擊，將暴露用戶更多個人信息。

針對以上問題，現(xiàn)有位置大數(shù)據(jù)的隱私保護技術可分為 3類：基于啟發(fā)式隱私度量、基于概率推測以及基于隱私信息檢索的位置大數(shù)據(jù)隱私保護技術[3,6]。差分隱私[7,8]具有完全獨立于攻擊者背景知識的強隱私保護性質(zhì)，已經(jīng)有不少研究[9～11]將其應用到面向發(fā)布的數(shù)據(jù)模型中。文獻[12]將差分技術與位置大數(shù)據(jù)服務相結(jié)合，針對發(fā)布數(shù)據(jù)聚集易受相似性攻擊的問題，提出一種最大化差分隱私效果的匿名算法。文獻[13]利用位置服務查詢結(jié)果的相似性來輔助匿名服務器構(gòu)造匿名區(qū)域，提出具有較高平衡性的 k-匿名位置隱私保護方法。為提高位置數(shù)據(jù)模式挖掘中差分技術的保護性能，文獻[14]基于四叉樹空間分解技術保持了位置數(shù)據(jù)的語義。社交網(wǎng)絡中考慮推薦系統(tǒng)存在的隱私安全問題，文獻[15]通過差分技術提出保護位置軌跡數(shù)據(jù)集隱私的解決方案。但它們的缺點在于忽略了將位置數(shù)據(jù)與非位置數(shù)據(jù)匹配的攻擊模式，針對這個問題，本文提出差分保護下一種新的位置大數(shù)據(jù)服務的數(shù)據(jù)發(fā)布模型，在提供大數(shù)據(jù)查詢服務中的同時保護位置數(shù)據(jù)和非位置數(shù)據(jù)的敏感信息，仿真實驗證明算法能夠在指定的私密性條件下，為查詢服務發(fā)布具有更高準確率的位置數(shù)據(jù)。

2 問題描述

2.1 位置大數(shù)據(jù)服務中的隱私威脅

隨著互聯(lián)網(wǎng)大數(shù)據(jù)技術的不斷發(fā)展和基于位置服務（LBS, location-based services）應用的不斷增多，利用全球衛(wèi)星導航定位系統(tǒng)和地面通信基站，結(jié)合云計算、海量數(shù)據(jù)處理技術，把數(shù)以億計甚至數(shù)以千億計的數(shù)據(jù)實時、安全地存儲下來，再以可視化的方式展現(xiàn)給用戶，這將產(chǎn)生巨大的社會價值和商業(yè)價值。通過手機、車載導航、內(nèi)置傳感器等移動設備中的GPS、Wi-Fi等定位設備，將LBS與大數(shù)據(jù)概念結(jié)合產(chǎn)生的產(chǎn)品越來越多。從國內(nèi)看，2014年，央視與百度合作在春運期間推出“百度遷徙”位置服務應用，啟用百度地圖定位可視化大數(shù)據(jù)播報國內(nèi)春節(jié)人口遷徙情況，該項目利用百度LBS定位數(shù)據(jù)進行計算分析，展現(xiàn)春節(jié)前后人口大遷徙軌跡與特征位置，成為大數(shù)據(jù)位置服務進入大眾生活的成功案例。

然而，位置大數(shù)據(jù)應用服務在提供相應查詢并發(fā)布相關用戶信息時，將面臨泄露客戶個人隱私的危機。大數(shù)據(jù)時代，位置數(shù)據(jù)的來源極為廣泛，據(jù)統(tǒng)計，每天使用百度定位服務產(chǎn)生的定位請求由2013年的35億次上漲到2015年的150億次，如果對其收集到的海量位置信息不加以控制地發(fā)布、不提供安全的挖掘分析機制，對于含大量敏感信息如醫(yī)療、金融行業(yè)以及情報收集等部門的隱私泄露將引發(fā)嚴重的社會恐慌。同時，將位置大數(shù)據(jù)中包含的移動對象不同時刻的位置信息與背景知識結(jié)合，可以讓攻擊者有效推測用戶的行為模式，會泄露用戶的健康狀況、行為習慣、社會地位等敏感信息。攻擊者可以根據(jù)在任意時刻t之前收集到歷史位置數(shù)據(jù)L，推測用戶在t時刻處于某個敏感位置ln的概率為為了量化位置大數(shù)據(jù)的隱私保護效果，對位置大數(shù)據(jù)的θ隱私定義如下。

定義1 設任意用戶U在任意時刻t處于位置ln的推測概率為，在t時刻之前收集到關于用戶U的歷史位置數(shù)據(jù)為，則

其中，θ是用戶給定的隱私需求，也是攻擊者能夠獲得的最大攻擊效果。攻擊者根據(jù)t時刻之前獲取到的歷史位置數(shù)據(jù)推測用戶在 t時刻處于位置ln的后驗概率與其先驗概率之差不能超過隱私需求θ，從而量化了隱私保護效果，當θ=0時隱私保護效果達到最大，稱為完美隱私。

2.2 位置服務基于差分隱私的數(shù)據(jù)發(fā)布模型

差分隱私是一種新的基于嚴格數(shù)學背景的隱私保護機制，提供了使隱私保護程度可量化、可評估、可證明的方法。差分隱私保護技術通過添加隨機噪聲擾動敏感數(shù)據(jù)，使某些數(shù)據(jù)在失真的同時保持其具有的統(tǒng)計性質(zhì)，以便在進行數(shù)據(jù)挖掘等操作后得到高度近似的價值知識。將差分隱私技術運用到位置大數(shù)據(jù)發(fā)布模型中，能有效防止基于背景知識的惡意攻擊。大多數(shù)位置數(shù)據(jù)發(fā)布系統(tǒng)結(jié)構(gòu)基于“先收集、再匿名、后發(fā)布”的原則，即由一個數(shù)據(jù)收集服務器收集位置數(shù)據(jù)，并將海量原始數(shù)據(jù)存儲到軌跡數(shù)據(jù)庫中，然后結(jié)合云計算技術與一定的隱私保護機制進行隱私保護處理，最后為查詢客戶提供可發(fā)布、可分析的安全軌跡數(shù)據(jù)。本文提出的差分隱私保護下位置大數(shù)據(jù)處理服務器主要有 3個模塊：數(shù)據(jù)預清洗模塊、敏感信息隱藏模塊和可用性評估模塊，如圖1所示。數(shù)據(jù)預清洗模塊負責對收集到的軌跡數(shù)據(jù)進行等價類劃分、軌跡同步等預處理操作；敏感信息隱藏模塊結(jié)合差分隱私保護技術，負責對預處理后的隱私數(shù)據(jù)匿名操作；由可用性評估模塊反饋隱私處理后的數(shù)據(jù)可用性，實現(xiàn)在高效挖掘信息蘊含知識與控制隱私泄露隱患之間找到最佳平衡點。最后將處理后的位置大數(shù)據(jù)發(fā)布給查詢客戶。

Dwork等[7,8]在2006年首次提出差分隱私技術，根據(jù)這種強隱私保護模型，本文定義位置數(shù)據(jù)差分隱私如下。

定義 2 （位置差分隱私）對于至多相差一條位置記錄的2個數(shù)據(jù)集D和D＇，即兩者的線性相異距離M 為給定提供ε?差分隱私保護的隨機查詢函數(shù)，Range(M)代表算法M的取值范圍，若軌跡數(shù)據(jù)集D和D＇在查詢函數(shù)M下得到的任意位置滿足式(2)，則M滿足ε?位置差分隱私。

其中，概率Pr[?]表示隱私被泄露的風險，由算法 M的隨機性控制；參數(shù)ε為隱私保護預算，ε越小隱私保護程度越高。

在查詢函數(shù)的返回值中添加適量隨機噪聲是實現(xiàn)差分隱私的主要技術，常用的噪聲機制有拉普拉斯機制[16]和指數(shù)機制[17]，給出定義3和定義4。任意函數(shù)，全局敏感度是決定噪聲適量添加的關鍵參數(shù)，其中，是相鄰數(shù)據(jù)集D和D＇函數(shù)輸出值的一階范數(shù)距離。敏感度指添加或刪除數(shù)據(jù)集中任一記錄對函數(shù)輸出值造成的最大改變。查詢函數(shù)f的全局敏感度S(f)由函數(shù)本身性質(zhì)決定，與數(shù)據(jù)集無關。

定義3 （拉普拉斯機制）任意函數(shù)f:D→?d，若函數(shù)f的輸出結(jié)果滿足式(3)，則f滿足ε?差分隱私。

其中，S(q)為可用函數(shù)的全局敏感度，對象被選中的概率正比于可用函數(shù) q的打分。指數(shù)機制以正比于的概率返回實體對象。

圖1 差分隱私保護下位置大數(shù)據(jù)發(fā)布模型

3 基于差分隱私的位置大數(shù)據(jù)發(fā)布方法

位置數(shù)據(jù)基于二維空間索引技術發(fā)布所處的地點信息，常見存儲空間數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)包括四叉樹（Quad-tree）、R樹及R+樹系列（R-tree）、k-d tree（k-dimensional tree）等。這些數(shù)據(jù)結(jié)構(gòu)大體可以分為2類[18]：數(shù)據(jù)無關的分解結(jié)構(gòu)（data-independent decomposition）和數(shù)據(jù)相關的分解結(jié)構(gòu)(data-dependent decomposition)。如當對同一位置信息數(shù)據(jù)庫構(gòu)造索引樹時，四叉樹按固定的遞歸算法分裂節(jié)點，樹的構(gòu)造結(jié)果與數(shù)據(jù)無關；而R-tree，k-d tree的節(jié)點分裂性質(zhì)取決于位置覆蓋面積大小以及分布方式的不同，其分裂形態(tài)將與數(shù)據(jù)庫中的具體位置信息相關。因為地點信息的語義具有明顯的垂直分層結(jié)構(gòu)并且地點之間存在包含關系，所以用樹結(jié)構(gòu)存儲的位置信息可以被劃分保存，空間的分解也減少了訪問查詢的復雜度。由于空間數(shù)據(jù)的特殊性（海量、多維、空間拓撲特征、時間特征），空間分解技術采用分割原理，把查詢空間劃分為若干區(qū)域，同時將位置信息分層儲存，形成可唯一標識空間要素。然后利用不同的數(shù)據(jù)結(jié)構(gòu)對分割的區(qū)域進行組織，以達到快速訪問數(shù)據(jù)項的目的。

本文提出的位置信息發(fā)布方法在基于空間分解技術的位置大數(shù)據(jù)添加差分隱私匿名泛化技術，使最終發(fā)布的數(shù)據(jù)在保持一定挖掘準確率的條件下保護個人隱私，達到安全訪問的目的。圖2為基于四叉樹二維空間分解技術的位置興趣點分布，其中，Q和Q'為對外提供的查詢函數(shù)。按此數(shù)據(jù)結(jié)構(gòu)實施差分隱私保護，為索引樹添加噪聲的過程如圖3所示。

如圖2所示，假設某用戶在一段時間內(nèi)形成移動軌跡，攻擊方聯(lián)合收集用戶在該區(qū)域出現(xiàn)的標記點數(shù)量，基于統(tǒng)計背景知識對該區(qū)域包含的部分區(qū)域請求位置大數(shù)據(jù)服務，發(fā)出連續(xù)的查詢函數(shù) Q、Q'等，攻擊方對比背景知識與連續(xù)查詢函數(shù)的結(jié)果，可以分析推測用戶在某個時間點出現(xiàn)的具體位置。所以，基于這種位置數(shù)據(jù)發(fā)布可能出現(xiàn)隱私泄露的問題，本文提出的算法在位置大數(shù)據(jù)服務中結(jié)合差分隱私技術，可實現(xiàn)隱私四叉樹的安全發(fā)布。如圖3所示，標記位置L1～L7為用戶的興趣位置查詢點，給此用戶標記的位置信息添加拉普拉斯或指數(shù)噪聲，方框中的數(shù)據(jù)是對真實數(shù)據(jù)匿名化的結(jié)果，其中，P定義為某個位置興趣點被查詢的概率，a～e定義為位置分割節(jié)點。使位置服務發(fā)布的匿名化數(shù)據(jù)能在實現(xiàn)隱私保護的同時保證給查詢函數(shù)提供一定可用性數(shù)據(jù)是本文算法的研究重點。

圖2 基于四叉樹空間分解的位置分布

圖3 添加噪聲的索引樹數(shù)據(jù)

3.1 隱私位置數(shù)據(jù)發(fā)布流程

現(xiàn)有的位置大數(shù)據(jù)服務中，攻擊者可以從多種渠道獲得用戶和位置數(shù)據(jù)相關的其他類型數(shù)據(jù)，并結(jié)合位置數(shù)據(jù)共同推測用戶的隱私信息。如許多社交軟件的簽到服務、分享定位等操作，通過用戶的個性設置或者行為模式對其位置數(shù)據(jù)與非位置數(shù)據(jù)進行匹配，會將用戶大量敏感的個人信息發(fā)布給基于位置服務的攻擊者，帶來隱私泄露的潛在危機。本文對基于位置大數(shù)據(jù)服務器的惡意攻擊途徑主要為獲取對系統(tǒng)的先驗知識，攻擊者對不同知識掌握的準備度也直接影響著攻擊者的攻擊能力。為解決上述問題，構(gòu)建基于含有安全客戶信任中間件的LBS 系統(tǒng)，實現(xiàn)差分隱私保護下位置大數(shù)據(jù)服務器對隱私位置數(shù)據(jù)的安全發(fā)布，本文提出差分位置發(fā)布（Diff_PriLocation）算法步驟如下。

步驟 1 位置數(shù)據(jù)預處理。根據(jù)空間分解技術（SD）將二維位置分解為基本數(shù)據(jù)集，依據(jù)空間位置自然的包含關系劃層次存儲每個位置元素，保留位置元素的語義信息得到相應完整的樹形數(shù)據(jù)結(jié)構(gòu)，為以后目標點搜索提高了執(zhí)行效率。

步驟2 合理分配隱私預算ε。根據(jù)數(shù)據(jù)預處理過后的樹高度 h和葉子節(jié)點的數(shù)量Nleaf合理分配迭代過程中的隱私預算。

步驟3 數(shù)據(jù)匿名化處理?；诓煌目臻g分解方法遍歷樹的所有節(jié)點，獲取每個標記點的位置數(shù)據(jù)L與非位置數(shù)據(jù)D。用差分隱私技術分別對位置和非位置數(shù)據(jù)添加噪聲，對不同屬性類別的敏感信息采取不同匿名化處理機制。

步驟4 反饋機制。為了保證發(fā)布數(shù)據(jù)具有較高的數(shù)據(jù)可用性，建立查詢函數(shù)Q的反饋機制。根據(jù)查詢用戶的反饋信息分析數(shù)據(jù)的泛化程度，調(diào)節(jié)發(fā)布數(shù)據(jù)的隱私預算ε。

步驟5 安全發(fā)布位置大數(shù)據(jù)。對數(shù)據(jù)庫中位置數(shù)據(jù)與非位置數(shù)據(jù)的分類處理，是為了保證基于位置大數(shù)據(jù)的服務質(zhì)量。重組匿名處理后的位置數(shù)據(jù)，最后對查詢函數(shù)發(fā)布滿足差分隱私的數(shù)據(jù)。

在算法的整個流程中，創(chuàng)新提出綜合考慮位置數(shù)據(jù)與非位置數(shù)據(jù)來保護用戶隱私，設計新的應對多組合復雜攻擊及前景知識攻擊的差分隱私保護數(shù)據(jù)發(fā)布方案，針對敏感屬性以及身份識別等提出相應的數(shù)據(jù)細節(jié)處理方案，使發(fā)布框架具有良好的開放性。

3.2 平衡隱私預算

隱私預算ε的不合理分配會破壞算法的隱私保護性能，算法本身也就失去了意義。本算法依據(jù)位置數(shù)據(jù)提供者對隱私保護的需求B以及空間分解后輸出的索引樹高度h，合理分配迭代過程中的隱私預算ε。對于數(shù)據(jù)不相關的空間分解技術，如基于四叉樹索引的空間分解算法，由于其輸出的數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)性質(zhì)無關，僅與索引樹的高度以及葉子節(jié)點包含的標記點數(shù) n有關，所以對每次匿名迭代分配的隱私預算為。而對于數(shù)據(jù)相關的空間分解方法數(shù)據(jù)的性質(zhì)會直接影響隱私預算的分配，所以平衡隱私預算的方法要具體考慮如樹根節(jié)點到某葉子節(jié)點路徑上的中位數(shù)、節(jié)點數(shù)等參數(shù)。索引樹高度h（1≤i≤h），取路徑上每個節(jié)點消耗隱私的預算最大和為ε，且令根到葉子的每條路徑上隱私消耗相等，定義為

3.3 匿名處理

給定隱私預算ε，對遍歷收集到的位置數(shù)據(jù)L和非位置數(shù)據(jù)D添加噪聲，使之滿足差分隱私的要求。對于非位置數(shù)據(jù)D的屬性集，其屬性類別包括連續(xù)值屬性和非連續(xù)值屬性，針對數(shù)據(jù)屬性的不同分別采取不同的差分噪聲機制。對連續(xù)值添加拉普拉斯噪聲LapNoiseε擾動真實值，指數(shù)機制以正比于的概率輸出離散值，其中，Q為查詢函數(shù)。差分隱私保護下的數(shù)據(jù)匿名處理（Diff_Anonmity）算法描述如算法1所示。

算法1 差分隱私保護下的數(shù)據(jù)匿名處理算法

輸入 ε—隱私保護預算，L—位置數(shù)據(jù)集，D—非位置數(shù)據(jù)集—數(shù)據(jù)屬性集合，—連續(xù)屬性數(shù)據(jù)集合，—離散屬性數(shù)據(jù)集合

輸出 滿足差分隱私保護要求的匿名化數(shù)據(jù)集Diff_AnonymData

1) begin Procedure Diff_Anonmity(ε, L, D,

3) if 數(shù)據(jù)屬于位置數(shù)據(jù)L

4) for L集合中任一元素Li

6) end for

7) else if 數(shù)據(jù)屬于非位置數(shù)據(jù)D

8) for D集合中任一元素Di，并且元素滿足

9) if Aj為連續(xù)值屬性，則

11) else ifAj為離散值屬性，則

13) end if

14) end for

15) end if

17) end Procedure

3.4 性能分析及反饋機制

3.4.1 反饋機制

本文提出位置大數(shù)據(jù)處理服務器的可用性評估模塊包含反饋機制以及性能分析模塊，反饋機制針對敏感屬性以及身份識別等提出相應的數(shù)據(jù)細節(jié)處理方案。在位置大數(shù)據(jù)動態(tài)發(fā)布的背景下，考慮準標識符和敏感屬性隨著時間發(fā)生變化會影響構(gòu)建模型的服務質(zhì)量，可引入時間變量 t標記數(shù)據(jù)集的改動，并在一定時間內(nèi)分析動態(tài)集改動操作的敏感度，若在統(tǒng)計過程中敏感度超過設定的閾值Γ，則需重新迭代位置索引樹獲取更新的數(shù)據(jù)信息，并結(jié)合用戶反饋信息發(fā)布新的數(shù)據(jù)模型。由于動態(tài)發(fā)布的記錄數(shù)據(jù)集中項目的增加、刪除、修改等操作都會影響執(zhí)行效率并導致查詢結(jié)果的不同，確立適當?shù)姆答仚C制實時監(jiān)管變化的數(shù)據(jù)，實施可控地隱私保護，可防止惡意攻擊方聯(lián)合位置數(shù)據(jù)與非位置數(shù)據(jù)對用戶身份識別，同時將對整體發(fā)布數(shù)據(jù)的壓縮和匿名化處理的影響降到最低，使整體設計的發(fā)布框架具有良好的開放性。

3.4.2 數(shù)據(jù)可用性分析

分析算法的性能以及收集用戶對服務質(zhì)量的反饋信息，提供交互接口可對位置數(shù)據(jù)的發(fā)布過程進行優(yōu)化。根據(jù)位置大數(shù)據(jù)服務對象對查詢精確度的要求，可以適當調(diào)整發(fā)布數(shù)據(jù)的隱私保護程度。對于相同的查詢函數(shù)Q，數(shù)據(jù)在匿名前和匿名后輸出查詢結(jié)果的近似度體現(xiàn)了隱私保護算法對數(shù)據(jù)的可用性的影響。設G(Q)為原始數(shù)據(jù)的查詢結(jié)果，為匿名后數(shù)據(jù)的查詢結(jié)果，則近似度SQ可定義為兩輸出結(jié)果的一階范數(shù)距離對連續(xù)查詢，位置服務發(fā)布數(shù)據(jù)的可用性定義為

服務對象可定義允許的誤差范圍δ，則可容忍的信息丟失率為1?δ，誤差范圍δ與數(shù)據(jù)可用性 E成反比。其中，基于空間距離的查詢函數(shù)敏感度為，而針對海量位置數(shù)據(jù)集中一組連續(xù)分區(qū)查詢策略，定義其全局敏感度為其中任意查詢函數(shù)敏感度的最大值，表示為。當匿名發(fā)布數(shù)據(jù)可用性低于用戶的查詢要求時，可以對發(fā)布模型反饋誤差信息，在差分保護范圍內(nèi)要求適當降低隱私保護干擾，從而降低差分隱私對數(shù)據(jù)集的泛化程度，發(fā)布可用性更高的數(shù)據(jù)。數(shù)據(jù)可用性和算法復雜度是評判發(fā)布算法性能的重要標志，能在提高添加噪聲執(zhí)行效率的同時減少噪聲帶來的誤差，兼顧發(fā)布數(shù)據(jù)安全性與可用性。

3.4.3 算法復雜度分析

最優(yōu)化差分技術為數(shù)據(jù)原項添加噪聲的算法復雜度，會直接影響匿名發(fā)布模型的執(zhí)行效率。首先Diff_Anonmity算法采用貪心方法自頂而下遞歸索引樹的時間復雜度為O(lbn)，然后分類處理每個節(jié)點包含的數(shù)據(jù)信息。針對位置數(shù)據(jù)集添加噪聲消耗時間復雜度為，對于非位置數(shù)據(jù)集中每個連續(xù)值屬性中出現(xiàn)的值要逐一排序并統(tǒng)計重復值出現(xiàn)的次數(shù)，處理連續(xù)值屬性找出最佳斷點并加入拉普拉斯噪聲的時間復雜度為，完成對連續(xù)值屬性的泛化處理后，Diff_Anonmity算法最后再對離散值屬性處理平均消耗的時間復雜度整個算法過程消耗的總時間復雜度還受到空間分解生成樹高度的影響。因為大數(shù)據(jù)服務的海量信息結(jié)構(gòu)復雜多樣，所以收集服務器在前期對異構(gòu)集合進行必要的數(shù)據(jù)清洗處理，將大幅降低匿名算法迭代處理的復雜程度。

4 仿真實驗

為了研究本文提出算法的可行性，采用的系統(tǒng)硬件配置為主頻2.4 GHz的Intel(R)Core(TM)i3兼容PC機，2 GB內(nèi)存，200 GB以上的可用磁盤空間；軟件配置平臺為WIN 2008 Server操作系統(tǒng)以及Microsoft SQL Server數(shù)據(jù)庫系統(tǒng)，C/S結(jié)構(gòu)的運行模式。實驗基于 3個數(shù)據(jù)集 GeoLife、Amazon Access Samples以及Diversification Dataset Div400。數(shù)據(jù)集的來源數(shù)據(jù)庫分別是：GeoLife GPS Trajectories，UCI Machine Learning Repository和UMass Trace Repository。實驗的數(shù)據(jù)集都包括用戶的位置信息和非位置信息，其數(shù)據(jù)集大小以及屬性特征如表1所示。

表1 實驗數(shù)據(jù)集

常用的空間索引技術可以提高空間信息數(shù)據(jù)庫的操作效率，Quad-tree將位置空間遞歸劃分為不同層次的樹結(jié)構(gòu)，當空間數(shù)據(jù)對象分布比較均勻時，具有比較高的空間數(shù)據(jù)插入和查詢效率；R-tree廣泛應用于原型研究和商業(yè)應用中，為了使 R-tree能在海量的空間數(shù)據(jù)庫中發(fā)揮重要作用，將優(yōu)化插入路徑選擇減少R-tree插入節(jié)點后目錄矩形重疊面積，以及保持在當前層實現(xiàn)節(jié)點分裂的獨立性；k-d tree索引用于多維檢索的結(jié)構(gòu)形式，對數(shù)據(jù)點在 k維空間中劃分，并在每一層都根據(jù)該層的分辨器對相應對象做出分枝決策，對于精確的點能匹配查找具有和二叉樹一樣良好的性能（平均查找長度為1+4lbn）；本文提出的發(fā)布框架基于以上3種空間索引技術Quad-tree、R-tree、k-d tree，對實驗的3種數(shù)據(jù)集進行了2類實驗分別測試差分隱私保護下的發(fā)布算法與傳統(tǒng)位置數(shù)據(jù)發(fā)布算法的數(shù)據(jù)可用性以及安全性能，并對實驗結(jié)果進行分析，驗證本文算法Diff_PriLocation和Diff_Anonmity的有效性。

仿真實驗在隱私預算ε逐步遞增的條件下，比較經(jīng)過本文發(fā)布框架輸出的匿名化數(shù)據(jù)的準確程度，滿足隱私要求在同等測試環(huán)境下分析3個數(shù)據(jù)集的實驗結(jié)果，分析本文算法在不同隱私保護預算ε下的數(shù)據(jù)可用性，其中，差分隱私的可用函數(shù)取查詢函數(shù)的信息熵增益值Gain(Q )，考慮算法中拉普拉斯變換對海量數(shù)據(jù)的噪聲敏感度問題，選取不同的變換尺度參數(shù)，噪聲量大小與全局敏感度成正比，與隱私預算ε成反比。算法首先根據(jù)給定的數(shù)據(jù)集及其n個屬性集產(chǎn)生原始的空間劃分，得到所有區(qū)域單位格為celli，則其中的位置點頻數(shù)。當采用樹劃分算法為所有頻數(shù)加入Laplace噪聲時，在每一次的遞歸迭代中，首先計算當前分區(qū)Pi中頻數(shù)分布的緊密程度，其中，ai是Pi中所有數(shù)據(jù)格頻數(shù)的平均值，若大于預定義的閾值，則將該分區(qū)劃分為 2個子分區(qū)。利用樹的層次特征分而治之地把海量數(shù)據(jù)集分割處理，并根據(jù)樹的高度1+logmn調(diào)整分區(qū)方案的敏感性，能精確地響應較長范圍的計數(shù)查詢。

對于依賴樹劃分的海量空間數(shù)據(jù)，添加的拉普拉斯噪聲量將與空間分區(qū)方案密切相關。使用基于區(qū)域密度的分割停止條件來構(gòu)造差分隱私保護技術，使分區(qū)中數(shù)據(jù)格的頻度彼此接近，從而在大型數(shù)據(jù)集中可僅通過添加少量的噪聲，就能達到高級別的隱私保護。同時，為了驗證Diff_PriLocation算法對不同空間分解技術的開放性，實驗分別基于Quad-tree、R-tree以及k-d tree這3種常用的空間索引技術，設計20組實驗，分別在不同數(shù)量級和不同隱私預算要求下測試算法的性能，實驗結(jié)果取平均值。對3個實驗數(shù)據(jù)集匿名化處理后，得到滿足差分隱私保護要求的可發(fā)布數(shù)據(jù)Diff_AnonymData，分析Diff_AnonymData的準確率可體現(xiàn)本文位置大數(shù)據(jù)處理服務器在滿足查詢要求的條件下處理發(fā)布的數(shù)據(jù)集可用性。各實驗數(shù)據(jù)集的發(fā)布數(shù)據(jù)準確性如圖4～圖6所示。

圖4 GeoLife數(shù)據(jù)集可用性

圖5 Amazon Access Samples數(shù)據(jù)集可用性

圖6 Div400數(shù)據(jù)集可用性

隱私預算ε與隱私保護程度成反比，當隱私預算越小、數(shù)據(jù)泛化程度越大且當隱私保護程度ε=0時，即達到完美隱私。從實驗結(jié)果可以看出，隨著隱私保護預算的遞增，差分算法對分布數(shù)據(jù)的泛化程度減小，所以數(shù)據(jù)的可用性都有所上升。從仿真實驗結(jié)果中也可以看出，因為基于四叉樹索引生成的位置空間樹結(jié)構(gòu)與實驗數(shù)據(jù)集的性質(zhì)無關，所以基于四叉樹索引的差分隱私發(fā)布數(shù)據(jù)會具有相對較高的數(shù)據(jù)可用性，同時保持一定的算法穩(wěn)定性。從表1可以看出3個實驗數(shù)據(jù)集所含的數(shù)據(jù)項呈上升趨勢，隨著實驗數(shù)據(jù)集的增加，與數(shù)據(jù)相關的R-tree、k-d tree空間索引技術受到數(shù)據(jù)統(tǒng)計性質(zhì)的影響，在隱私保護程度要求較高的情況下會具有較差的數(shù)據(jù)可用性，而且Diff_Anonmity算法的執(zhí)行效率也趨向下降。同時，較一般非差分隱私保護的安全發(fā)布算法[19]，本文算法也維持了近似的信息損失度和數(shù)據(jù)可用性。

為了研究算法的隱私保護性能，在數(shù)據(jù)可用性與隱私保護程度之間找到最佳平衡，考慮海量數(shù)據(jù)集的噪聲敏感度問題，實驗在不同拉普拉斯變換尺度參數(shù)下分析比較各個數(shù)據(jù)集的平均隱私保護程度。在基于數(shù)據(jù)相關與數(shù)據(jù)無關2類不同的空間分解技術下，實驗數(shù)據(jù)集被差分隱私匿名保護的結(jié)果如圖7和圖8所示。從實驗結(jié)果可以看出，Diff_Anonmity算法的隱私保護程度基本能達到80%以上，隨著匿名要求的提高不會大幅降低算法的執(zhí)行效率，在隱私保護程度要求比較高的情況下，差分隱私的性能具有較好的穩(wěn)定性。

圖7 基于數(shù)據(jù)無關分解結(jié)構(gòu)

圖8 基于數(shù)據(jù)相關分解結(jié)構(gòu)

面向單一攻擊的安全數(shù)據(jù)發(fā)布框架已經(jīng)無法適應多組合復雜攻擊的大數(shù)據(jù)環(huán)境。一方面，大部分數(shù)據(jù)發(fā)布框架設計忽略了真實環(huán)境數(shù)據(jù)的動態(tài)變化，單一考慮位置數(shù)據(jù)而忽略了非位置數(shù)據(jù)的隱私保護，無法估計數(shù)據(jù)多次發(fā)布所帶來的潛在風險；另一方面，現(xiàn)有數(shù)據(jù)發(fā)布模型無法兼顧數(shù)據(jù)安全性與可用性，及時對用戶的反饋做出調(diào)整，未能高效地添加適當噪聲減少匿名泛化過程中帶來的誤差，以提高數(shù)據(jù)的可用性。本文算法在實驗過程中表現(xiàn)的穩(wěn)定性有效解決了以上問題，實現(xiàn)了在未來大數(shù)據(jù)位置服務中應用差分隱私保護技術的可能性。

5 結(jié)束語

針對現(xiàn)有海量位置信息服務中的不足，本文提出了一種基于差分隱私保護機制的位置大數(shù)據(jù)發(fā)布算法，將位置數(shù)據(jù)與非位置數(shù)據(jù)區(qū)別分析，同時引入隨機噪聲干擾敏感數(shù)據(jù)，有效地降低數(shù)據(jù)挖掘過程中隱私泄露的風險。仿真實驗基于不同數(shù)據(jù)集、不同的空間索引方法驗證了本文提出算法的有效性。從實驗結(jié)果可看出發(fā)布數(shù)據(jù)匿名算法Diff_Anonmity在實現(xiàn)隱私保護的同時具有更良好的數(shù)據(jù)可用性。研究如何保護位置大數(shù)據(jù)隱私的技術將具有廣闊的研究前景和實用價值，現(xiàn)將差分隱私技術運用在大數(shù)據(jù)服務上的有關研究還比較少，本文后續(xù)工作將繼續(xù)深入對該方向的研究，提出滿足更高要求的大數(shù)據(jù)安全訪問方法。

[1] 王璐, 孟小峰. 位置大數(shù)據(jù)隱私保護研究綜述[J].軟件學報，2014,25(4):693-712.WANG L，MENG X F. Location privacy preservation in big data era: a survey[J]. Journal of Software, 2014,25(4):693-712.

[2] 霍崢, 孟小峰.軌跡隱私保護技術研究[J]. 計算機學報, 2011, 34(10):1820-1830.HUO Z, MENG X F. A survey of trajectory privacy-preserving techniques[J]. Chinese Journal of Computers, 2011, 34(10): 1820-1830.

[3] KIDO H, YANAGISAWA Y, SATOH T. Protection of location privacy using dummies for location-based services[C]//The 21st International Conference on Data Engineering Workshops, ICDEW IEEE Computer Society. Washington, DC, 2005: 1248-1254.

[4] MOKBEL M F, CHOW C Y, AREF W G. The new casper: query processing for location services without compromising privacy[C]//The 32nd International Conference on Very Large Data Bases,VLDB Endowment. 2006: 763-774.

[5] CHOW C Y, MOKBEL M F. Trajectory privacy in location-based services and data publication[J]. ACM SIGKDD Explorations Newsletter, 2011,13(1):19-29.

[6] BAMBA B, LIU L, PESTI P, et al. Supporting anonymous location queries in mobile environments with privacygrid[C]//WWW, ACM,2008: 237-246.

[7] DWORK C. Differential privacy[C]//The 33rd International Colloquium on Automata, Languages and Programming (ICALP). Venice,Italy, 2006:1-12.

[8] DWORK C. Differential privacy: a survey of results[C]//The 5th International Conference on Theory and Applications of Models of Computation (TAMC). Xi’an, China, 2008:1-19.

[9] 張嘯劍, 孟小峰. 面向數(shù)據(jù)發(fā)布和分析的差分隱私保護[J]. 計算機學報, 2014, 37(4): 927-949.ZHANG X J, MENG X F. Differential privacy in data publication and analysis[J]. Chinese Journal of Computers, 2014, 37(4):927-949.

[10] 丁麗萍, 盧國慶. 面向頻繁模式挖掘的差分隱私保護研究綜述[J].通信學報，2014,35(10):200-209.DING L P, LU G Q. Survey of differential privacy in frequent pattern mining[J]. Journal on Communications, 2014, 35(10):200-209.

[11] CHEN R, ACS G, CASTELLUCCIA C. Differentially private sequential data publication via variable-length n-grams[C]//The 2012 ACM Conferenceon Computer and Communications Security, CCS, ACM,NewYork, 2012: 638-649.

[12] DEWRI R. Local differential perturbations: location privacy under approximate knowledge attackers[J]. IEEE Trans on Mobile Computing, 2013,12(12): 2360-2372.

[13] 葉阿勇, 李亞成, 馬建峰, 等. 基于服務相似性的 k-匿名位置隱私保護方法[J]. 通信學報, 2014,35(11):162-169.YE A Y, LI Y C, MA J F, et al. Location privacy-preserving method of k-anonymous based on service similarity[J]. Journal on Communications, 2014, 35(11): 162-169.

[14] HO S S, RUAN S. Differential privacy for location pattern mining[C]//SPRINGL, ACM. 2011: 17-24.

[15] ZHANG J D, GHINITA G, CHOW C Y. Differentially private location recommendations in geosocial networks[C]//IEEE 15th International Conference on MDM, 2014:59-68.

[16] DWORK C, MCSHERRY F, NISSIM K, et al. Calibrating noise to sensitivity in private data analysis[C]//The 3th Theory of Cryptography Conference (TCC). New York, USA, 2006:363-385.

[17] MCSHERRY F, TALWAR K. Mechanism design via differential privacy[C]//The 48th Annual IEEE symposium on Foundations of Computer Science (FOCS). Providence, RI, USA, 2007:94-103.

[18] CORMODE G, PROCOPIUC C, SRIVASTAVA D. Differentially private spatial decompositions[C]//IEEE 28th International Conference on Data Engineering (ICDE). 2012:20-31.

[19] 楊曉春, 王雅哲, 王斌, 等. 數(shù)據(jù)發(fā)布中面向多敏感屬性的隱私保護方法[J]. 計算機學報, 2008,31(4):574-587.YANG X C, WANG Y Z, WANG B, et al. Privacy preserving approaches for multiple sensitive attributes in data publishing[J]. Chinese Journal of Computers, 2008, 31(4): 574-587.

Location publishing technology based on differential privacy-preserving for big data services

ZHANG Lin1,2,3, LIU Yan1, WANG Ru-chuan1,2,3
(1.College of Computer, Nanjing University of Posts and Telecommunications, Nanjing 210003, China;2.Jiangsu High Technology Research Key Laboratory for Wireless Sensor Networks, Nanjing 210003, China;3. Key Lab of Ministry of Education Broadband Wireless Communication and Sensor Network Technology of Nanjing University of Posts and Telecommunications, Nanjing 210003, China)

Aiming at dealing with prospect knowledge and complex combinatorial attack, a new location big data publishing mechanism under differential privacy technology was given. And innovative usability evaluation feedback mechanism was designed. It gave corresponding solution details for the sensitive attributes and the identity recognition to analyze the quality of service, aimed at privacy protecting for location based big data under situations like combination of location information and non-location information and attacker’s arbitrary background knowledge. Simulation results based on different spatial indexing technology proved that the new publishing model has a higher accuracy under specified privacy conditions for the location query service.

location service, big data, differential privacy, data publishing, privacy-preserving

s: The National Natural Science Foundation of China (No.61402241, No.61572260, No.61373017, No.61572261,No.61472192), Scientific and Technological Support Project of Jiangsu Province (No.BE2015702), Natural Science Key Fund for Colleges and Universities of Jiangsu Province (No.12KJA520002, No.14KJA520002)

TP393

A

10.11959/j.issn.1000-436x.2016176

2015-10-26

2016-08-11

國家自然科學基金資助項目（No.61402241, No.61572260, No.61373017, No.61572261, No.61472192）；江蘇省科技支撐計劃基金資助項目（No.BE2015702）；江蘇省屬高校自然科學研究重大基金資助項目（No.12KJA520002, No.14KJA520002）

張琳（1980-），女，江蘇豐縣人，博士，南京郵電大學副教授、碩士生導師，主要研究方向為分布式計算、網(wǎng)絡安全、可信計算、隱私保護等。

劉彥（1992-），女，四川成都人，南京郵電大學碩士生，主要研究方向為分布式計算、數(shù)據(jù)挖掘、隱私保護等。

王汝傳（1943-），男，安徽合肥人，南京郵電大學教授、博士生導師，主要研究方向為計算機軟件、計算機網(wǎng)絡和網(wǎng)格、信息安全、無線傳感器網(wǎng)絡、移動代理和虛擬現(xiàn)實技術等。