顏 飛 張 興 李 暢 李萬杰 李 帥

(遼寧工業(yè)大學(xué)電子與信息工程學(xué)院 遼寧 錦州 121001)

0 引 言

隨著信息技術(shù)，特別是大數(shù)據(jù)技術(shù)和人工智能領(lǐng)域研究的飛速發(fā)展，海量數(shù)據(jù)的收集、存儲、發(fā)布和分析變得越來越容易。但從數(shù)據(jù)安全和個(gè)人隱私保護(hù)層面來看，大數(shù)據(jù)應(yīng)用也帶來了很大的數(shù)據(jù)安全隱患。而且數(shù)據(jù)的安全和隱私數(shù)據(jù)的泄露不僅會影響到個(gè)人利益，甚至?xí){到國家的網(wǎng)絡(luò)空間安全。面對如此復(fù)雜的大數(shù)據(jù)背景，大數(shù)據(jù)面臨著諸多安全問題，其中如何從大數(shù)據(jù)中分析挖掘出更多的價(jià)值而又很好地保護(hù)數(shù)據(jù)的隱私安全顯得尤為重要[1]。

從個(gè)人隱私安全層面來看，一旦隱私信息被泄露，用戶個(gè)人隱私無異于“裸奔”。對于企業(yè)來說，確保用戶數(shù)據(jù)安全和隱私安全是必須面對和解決的問題，若數(shù)據(jù)安全和隱私保障存在問題，將會影響大數(shù)據(jù)和人工智能的進(jìn)一步推廣應(yīng)用。在未來發(fā)展中，如果國家在數(shù)據(jù)安全控制方面失去了主動(dòng)權(quán)，那么必將受制于他人。因此，確保大數(shù)據(jù)安全和隱私安全十分重要，針對大數(shù)據(jù)安全和隱私保護(hù)的關(guān)鍵技術(shù)的研究值得更進(jìn)一步探索，而且大數(shù)據(jù)安全和隱私保護(hù)也將逐漸上升至國家戰(zhàn)略層面。

為了有效地保護(hù)個(gè)人隱私安全，研究人員提出了許多隱私保護(hù)模型，例如基于匿名技術(shù)的K-anonymity[2]、L-diversity[3]、M-invariance[4]、T-closeness[5]等。由于以匿名為基礎(chǔ)的隱私保護(hù)模型均需特殊的攻擊假設(shè)和一定的背景知識，且未能對隱私保護(hù)強(qiáng)度進(jìn)行量化分析，因此在實(shí)際應(yīng)用中具有較大的局限性。尤其是在海量數(shù)據(jù)的背景下，用戶的原始信息可能在經(jīng)過數(shù)據(jù)挖掘分析和深度學(xué)習(xí)的某個(gè)過程中被非法者破壞、攻擊和篡改，用戶信息的隱私安全面臨著嚴(yán)重的威脅[6]。因此，差分隱私[7]作為一種新型、輕量級的隱私保護(hù)算法，引起了研究人員的關(guān)注。它通過對發(fā)布數(shù)據(jù)進(jìn)行隨意擾動(dòng)，使得在傳統(tǒng)意義上無論攻擊者具有何種背景知識都無法識別一條記錄是否在原數(shù)據(jù)表中[8]，可以解決數(shù)據(jù)發(fā)布所隱藏的潛在隱私威脅。但針對海量數(shù)據(jù)的隱私保護(hù)數(shù)據(jù)發(fā)布往往會出現(xiàn)數(shù)據(jù)敏感度增大、隱私預(yù)算枯竭和數(shù)據(jù)噪聲過大等問題，對后期的數(shù)據(jù)分析造成較嚴(yán)重影響。并且在采用直方圖發(fā)布方法存在離群點(diǎn)導(dǎo)致數(shù)據(jù)高敏感問題，更容易泄露隱私。因此，針對離群點(diǎn)的分組劃分問題，文獻(xiàn)[9]在等寬劃分的基礎(chǔ)上提出了一個(gè)差值集的概念來處理在分組時(shí)由于離群點(diǎn)存在可能會導(dǎo)致的劃分誤差。該方法在面對充滿離群點(diǎn)的數(shù)據(jù)集時(shí)有著很好的表現(xiàn)，但在分組劃分階段需計(jì)算所有數(shù)據(jù)的差值集，對于大數(shù)據(jù)集來說差值集計(jì)算效率問題成為必須解決的問題。

研究人員在提高大數(shù)據(jù)集的計(jì)算效率方面也做了許多研究工作。文獻(xiàn)[10]采用高效的MapReduce并行計(jì)算模型實(shí)現(xiàn)了k-means聚類算法，有效提高了k-means算法的運(yùn)行效率。針對云平臺的開放性使攻擊者擁有大量的攻擊背景知識[11]，攻擊者可以通過關(guān)聯(lián)背景知識和聚類結(jié)果來竊取數(shù)據(jù)隱私[12-13]。文獻(xiàn)[14-15]將隱私保護(hù)機(jī)制融入Hadoop平臺下的MapReduce分布式計(jì)算框架，實(shí)現(xiàn)了海量分布式數(shù)據(jù)的隱私保護(hù)算法。華為研究人員為滿足數(shù)據(jù)挖掘需求，實(shí)施部署了滿足差分隱私保護(hù)的大數(shù)據(jù)分析平臺[16]。

雖然MapReduce分布式計(jì)算框架的使用可高效處理海量數(shù)據(jù)，但該框架在算法迭代過程需多次讀寫硬盤數(shù)據(jù)，消耗大量I/O通信資源，并且過多的噪聲擾動(dòng)也會增加隱私保護(hù)算法的復(fù)雜度開銷[17]。針對以上分析，為了提高數(shù)據(jù)隱私保護(hù)程度和數(shù)據(jù)的可用性，解決差值集計(jì)算效率問題，本文以海量靜態(tài)數(shù)據(jù)的發(fā)布需求為出發(fā)點(diǎn)，提出一種滿足ε-差分隱私保護(hù)的適用于Spark內(nèi)存迭代的SPDP-GS(Spark Differential privacy-Grouping Smothing)算法。該方法可提高離群點(diǎn)判斷速度和差值集計(jì)算效率，并有效控制基于直方圖的數(shù)據(jù)發(fā)布方法中的離群點(diǎn)對數(shù)據(jù)發(fā)布的敏感度的影響，具有一定的應(yīng)用價(jià)值和理論研究意義。

1 差分隱私保護(hù)理論

差分隱私保護(hù)主要通過對發(fā)布數(shù)據(jù)進(jìn)行隨意擾動(dòng)，使得攻擊者使用傳統(tǒng)方法攻擊時(shí)，無論擁有何種背景知識均無法輕易識別出某條記錄是否一定在原數(shù)據(jù)表中。

1.1 差分隱私定義

定義1對于給定的2個(gè)至多相差1條記錄的數(shù)據(jù)集D1以及D2，f為隨機(jī)算法，range(f)表示算法f的所有輸出構(gòu)成的集合，S為range(f)的子集。若算法f滿足Pr[f(D1)∈S]≤eε×Pr[f(D2)∈S]，則算法f具有ε-差分隱私性。

其中，ε為隱私保護(hù)預(yù)算，代表算法的隱私保護(hù)水平，ε的取值越小，隱私保護(hù)水平越高。

1.2 Laplace噪聲機(jī)制

差分隱私保護(hù)的實(shí)現(xiàn)機(jī)制是采用數(shù)據(jù)擾動(dòng)，數(shù)據(jù)擾動(dòng)常用方法之一是采用Laplace[19]噪聲機(jī)制來實(shí)現(xiàn)數(shù)據(jù)加噪，該機(jī)制使用拉普拉斯分布所產(chǎn)生噪聲添加到真實(shí)輸出值中來實(shí)現(xiàn)差分隱私保護(hù)。

定義2對于任意一個(gè)函數(shù)f:D→Rd，算法Y滿足Y(D)=f(D)+。

其中，函數(shù)Lapi(Δf/ε)(1≤i≤d)表示拉普拉斯密度函數(shù)；Δf=maxD1,D1|f(D1)-f(D2)|為函數(shù)f(D)的查詢敏感度。D1、D2為兄弟數(shù)據(jù)集；d為查詢維度。

1.3 差分隱私組合特性

在差分隱私保護(hù)研究中，為證明算法滿足差分隱私，需滿足如下差分隱私組合特性：序列組合性和并列組合性。

性質(zhì)1[19]給定數(shù)據(jù)庫D與n個(gè)隨機(jī)算法fi，且fi滿足εi-差分隱私，那么fi(D)序列組合滿足ε-差分隱私，且ε=∑εi。

性質(zhì)2[19]設(shè)將給定數(shù)據(jù)庫D劃分成n個(gè)不相交的子集，D={D1,D2,…，Dn}，若任意算法fi滿足ε-差分隱私，則序列fi在D上的操作結(jié)果仍滿足ε-差分隱私。

2 Spark框架下SPDP-GS直方圖數(shù)據(jù)發(fā)布方法

為了提高對隱私數(shù)據(jù)的保護(hù)程度和挖掘結(jié)果的可用性，解決文獻(xiàn)[9]中差值集計(jì)算效率問題，以海量數(shù)據(jù)的統(tǒng)計(jì)特征為出發(fā)點(diǎn)，提出一種適用于Spark框架的滿足ε-差分隱私保護(hù)的海量靜態(tài)數(shù)據(jù)直方圖發(fā)布方法。

2.1 數(shù)據(jù)發(fā)布處理框架

本文提出一個(gè)滿足差分隱私保護(hù)需求的非交互式計(jì)算框架系統(tǒng)，其結(jié)構(gòu)示意如圖1所示。該框架主要由3個(gè)部分組成：原始數(shù)據(jù)收集和存儲，Spark框架下的數(shù)據(jù)處理和存儲，數(shù)據(jù)的隱私保護(hù)處理。

圖1 Spark框架下差分隱私保護(hù)模型

數(shù)據(jù)管理層，首先將原始數(shù)據(jù)集導(dǎo)入HDFS進(jìn)行數(shù)據(jù)的管理，然后數(shù)據(jù)從HDFS讀取到Spark框架形成RDD數(shù)據(jù)集，并進(jìn)行map操作、執(zhí)行join操作和Shuffle過程，最后將RDD處理結(jié)果輸出并保存到HDFS。

隱私處理，對待發(fā)布數(shù)據(jù)的隱私保護(hù)處理主要是借助Spark并行計(jì)算框架對經(jīng)過預(yù)處理的數(shù)據(jù)進(jìn)行分類統(tǒng)計(jì)、特征提取和聚類分組等計(jì)算任務(wù)，并對分組進(jìn)行添加Laplace噪聲。

2.2 Spark框架下k-means并行化改進(jìn)

1) 初始化k個(gè)初始聚類中心，形成樣本聚類。

2) 遍歷數(shù)據(jù)樣本，若boundDistance

3) 計(jì)算各聚類內(nèi)數(shù)據(jù)均值，更新聚類中心。

4) 循環(huán)Step1-Step3，直到達(dá)到指定迭代次數(shù)或聚類收斂聚類中心不再變化。

5) 輸出聚類處理結(jié)果。

2.3 SPDP-GS算法設(shè)計(jì)

在大數(shù)據(jù)應(yīng)用背景下，基于Spark框架的差分隱私保護(hù)直方圖發(fā)布方法主要目的在于滿足海量數(shù)據(jù)計(jì)算效率的要求下，提供有效的隱私保護(hù)方法。對于滿足差分隱私保護(hù)的直方圖發(fā)布方法，文獻(xiàn)[21]通過對數(shù)據(jù)集進(jìn)行排序、分組以及求各分組均值，再添加Laplace噪聲。但是在可能會存在大量離群點(diǎn)數(shù)據(jù)集時(shí)，會導(dǎo)致隱私泄露，而且簡單的等寬分組方法容易導(dǎo)致誤差增大問題。所以，文獻(xiàn)[9]在文獻(xiàn)[21]的基礎(chǔ)之上提出了采用插值集概念處理分組過程中由于離散點(diǎn)問題而導(dǎo)致的劃分誤差問題。但該方法對于海量數(shù)據(jù)集的處理來說差值集的計(jì)算量巨大。

因此，本文提出了借助Spark平臺采用k-means改進(jìn)算法對分組進(jìn)行最優(yōu)劃分，對每個(gè)分組求均值，再在各分組的平均數(shù)上添加Laplace噪聲，對隱私算法保護(hù)處理后的數(shù)據(jù)進(jìn)行發(fā)布?；赟park框架的SPDP-GS算法主要由：統(tǒng)計(jì)分類和DP-protection兩部分，主要步驟描述如下：

1) 采用Hash_map按屬性進(jìn)行分類統(tǒng)計(jì)。

3) 采用Laplace機(jī)制添加噪聲：Y(D)=f(D)+lap(Δf/ε)。

4) 對待發(fā)布數(shù)據(jù)進(jìn)行直方圖發(fā)布。

2.4 SPDP-GS算法描述

本節(jié)描述SPDP-GS算法包括：數(shù)據(jù)的類型統(tǒng)計(jì)、k-means聚類分組、分組求均值和添加Laplace噪聲，具體過程如下所述：

算法1k-means聚類分組劃分算法

輸入：經(jīng)Hash_map算法統(tǒng)計(jì)分類后數(shù)據(jù)集D{x1,x2,…,xn}，聚類簇?cái)?shù)k。

輸出：聚類分組C={c1,c2,…，ck}，組內(nèi)均值ucj，組內(nèi)數(shù)據(jù)數(shù)量numcj。

1)KMeansCluster(hashmapResult)

2) {Kmeans.setMax(k);

//設(shè)定聚類中心數(shù)k

3)

sourcedata=kmeans.loadData(hashmapresult);

//讀取統(tǒng)計(jì)分類結(jié)果數(shù)據(jù)集

4) fori=1 ton

5) { forj=1 tok

6) {

7) if (boundDistance

8) thenbestDistance←realDistance;

//計(jì)算xi與各均值向量uj距離

//將對應(yīng)值加入相應(yīng)簇

//更新均值向量

12)numcj=numcj+1;

//類內(nèi)數(shù)據(jù)個(gè)數(shù)統(tǒng)計(jì)

13) }

14) }

15)result:RDD[(int,Ck)]; //聚類結(jié)果存入RDD

16) 輸出：組內(nèi)均值ucj，組內(nèi)數(shù)據(jù)數(shù)量numcj

17) }

算法2差分隱私直方圖發(fā)布

輸入：聚類分組C={c1,c2,…，ck}，查詢?nèi)蝿?wù)Q，查詢敏感度Δf(Q)。

輸出：滿足ε-差分隱私的數(shù)據(jù)集Dε。

1) 依據(jù)查詢?nèi)蝿?wù)f(Q)返回分組C中對應(yīng)查詢記錄；

2.5 SPDP-GS數(shù)據(jù)發(fā)布方法

針對待發(fā)布數(shù)據(jù)集可能存在大量離群點(diǎn)導(dǎo)致隱私泄露風(fēng)險(xiǎn)增大和海量數(shù)據(jù)集的差值計(jì)算效率低的問題，滿足差分隱私保護(hù)的海量數(shù)據(jù)發(fā)布成為本文研究的著眼點(diǎn)。通常，數(shù)據(jù)集中難以避免地存在一些離群點(diǎn)，離群點(diǎn)的存在可能誘發(fā)隱私泄露和誤差增大問題。

例如，某疾病監(jiān)控中心，需周期性更新某些疾病確診患者，而所發(fā)布數(shù)據(jù)又不能泄露確診患者年齡、住址等隱私信息。因此，可采用差分隱私保護(hù)方法對發(fā)布數(shù)據(jù)進(jìn)行處理，數(shù)據(jù)隱私保護(hù)后再發(fā)布。實(shí)例具體說明如下：若將圖2(a)所示數(shù)據(jù)直接發(fā)布，擁有相關(guān)背景知識的人很容易推斷離散點(diǎn)數(shù)據(jù)的隱私信息。采用文獻(xiàn)[21]和本文所提出的方法將數(shù)據(jù)集D={32,28,43,45,48,2}進(jìn)行分組劃分，可有效解決隱私泄露問題。

(a) 原始直方圖(b) 排序后直方圖

(c) 采用GS劃分 (d) 采用SPDP-GS劃分圖2 不同方法所得直方圖劃分圖

2.6 數(shù)據(jù)隱私安全性分析

2.6.1 隱私驗(yàn)證

本文所述算法的隱私性主要從算法滿足ε-差分隱私的定義和性質(zhì)角度加以論證。由于噪聲添加在分組劃分后的各分組之中，所以主要證明直方圖發(fā)布算法是否滿足ε-差分隱私。

定理1算法SPDP-GS滿足ε-差分隱私。

證明：由算法1中分組策略和噪聲添加方法可知，每次滑動(dòng)窗口的經(jīng)過將會產(chǎn)生d個(gè)分組，而每分組所分得的隱私預(yù)算為d/ε。差分隱私方法中敏感度Q設(shè)置為1，即Δ(Q)=1。假設(shè)數(shù)據(jù)集D1和D2最多相差一條記錄，即|D1-D2|≤1，|D2-D1|≤1。由定義1可知，Pr[f(D1=D′)]≤eε×Pr[f(D2=D′)]。由性質(zhì)2可知該直方圖發(fā)布算法滿足ε-差分隱私。

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

本節(jié)所述算法采用聚類方法對數(shù)據(jù)進(jìn)行聚類分組，將相似數(shù)組(相似分組指的是直方圖數(shù)值相近的若干個(gè)桶)劃分在一個(gè)分組內(nèi)，并對同一分組內(nèi)的數(shù)據(jù)以平均值表示。因此，發(fā)布數(shù)據(jù)會產(chǎn)生兩種誤差：一是由各分組均值產(chǎn)生的近似誤差SSE(Sum Squared Error)；二是因添加拉普拉斯噪聲而產(chǎn)生的誤差。

(1)

3 實(shí)驗(yàn)設(shè)計(jì)與分析

3.1 實(shí)驗(yàn)環(huán)境

本文實(shí)驗(yàn)對算法的運(yùn)行效率以及隱私保護(hù)數(shù)據(jù)的結(jié)果可用性進(jìn)行考慮。實(shí)驗(yàn)選取3臺主機(jī)搭建Spark平臺，每臺機(jī)器均為雙核IntelCorei3處理器，4 GB內(nèi)存，操作系統(tǒng)選用Ubuntu，hadoop-2.7.2和Spark 2.2.0；JDK的版本是1.8.0_121，Scala-2.12.3。

本實(shí)驗(yàn)所用數(shù)據(jù)集來自“Kaggle：The Home of Data Science”網(wǎng)站所以提供的Transactions商場交易數(shù)據(jù)，包括商品類型、品牌、交易日期、采購量和交易金額；另一個(gè)數(shù)據(jù)集為US Census 1990 raw data，該數(shù)據(jù)集包含了來自1990年美國人口普查數(shù)據(jù)(PUMS) 1%的樣本，詳細(xì)信息見表1。

表1實(shí)驗(yàn)數(shù)據(jù)集

名稱大小/GB記錄數(shù)/個(gè)屬性類型數(shù)/個(gè)Transactions19.6349 655 790836US-Census8232 458 28568

3.2 數(shù)據(jù)預(yù)處理

本實(shí)驗(yàn)選取交易數(shù)據(jù)集的category(商品類型)和US Census的age屬性作為數(shù)據(jù)處理對象。對數(shù)據(jù)集中category和age字段的各種商品類型進(jìn)行統(tǒng)計(jì)。但category字段的值不應(yīng)該為0值，因此需在數(shù)據(jù)統(tǒng)計(jì)過程中對取值為0的記錄予以清除，不納入統(tǒng)計(jì)。

3.3 數(shù)據(jù)可用性度量

本文選取選取交易數(shù)據(jù)集的category屬性和US Census的age屬性作為敏感屬性進(jìn)行數(shù)據(jù)組劃分。主要采用和方差[23]和絕對誤差(AE)兩種評估標(biāo)準(zhǔn)度量算法的可用性。表達(dá)式如下：

(2)

首先，本實(shí)驗(yàn)選取Transactions數(shù)據(jù)集，對隱私預(yù)算ε所產(chǎn)生的數(shù)據(jù)可用性的影響展開研究。實(shí)驗(yàn)過程中分別取隱私預(yù)算參數(shù)ε為0.5、0.75、1和1.5。

圖3給出了隱私預(yù)算ε變化下絕對誤差的變化趨勢。結(jié)果表明，算法絕對誤差隨著隱私預(yù)算ε的增大而減少。而且，本文所述方法的隱私保護(hù)效果和數(shù)據(jù)可用性上相較于GS方法和S-GS方法更優(yōu)。

圖3 不同ε值下的絕對誤差

接下來分別在Transactions和US-Census數(shù)據(jù)集上，通過改變離群點(diǎn)數(shù)量num來對AE結(jié)果進(jìn)行研究,從而判斷本文所述方法與文獻(xiàn)[9,21]所述方法在數(shù)據(jù)發(fā)布結(jié)果可用性上的優(yōu)劣情況。

實(shí)驗(yàn)過程中ε取值設(shè)置為1.5，實(shí)驗(yàn)結(jié)果如圖4和圖5所示。在Transactions和US-Census數(shù)據(jù)集上，存在隨著離群點(diǎn)的個(gè)數(shù)的增加，導(dǎo)致發(fā)布結(jié)果的絕對誤差增大的現(xiàn)象。由絕對誤差計(jì)算公式可得，離群點(diǎn)的數(shù)量的增多會導(dǎo)致分組劃分的誤差增大。本文方法比文獻(xiàn)[9,21]所述方法表現(xiàn)更好的主要原因?yàn)椴捎霉潭ǖ姆纸M劃分不可避免的出現(xiàn)離群點(diǎn)分組劃分不合理的問題，從而導(dǎo)致分組過程中誤差增大的問題。

圖4 數(shù)據(jù)集Transactions下不同離群點(diǎn)的絕對誤差

圖5 數(shù)據(jù)集US-Census下不同離群點(diǎn)的絕對誤差

3.4 算法時(shí)間效率分析

本文采用了對原始數(shù)據(jù)集進(jìn)行Hash_map算法進(jìn)行分類統(tǒng)計(jì)，將統(tǒng)計(jì)結(jié)果進(jìn)行數(shù)據(jù)對外發(fā)布。而數(shù)據(jù)發(fā)布之前，對其中離散點(diǎn)的處理采用k-means聚類方法進(jìn)行合理組聚類，對同一類內(nèi)數(shù)據(jù)進(jìn)行求均值，從而減少S-GS方法在大數(shù)據(jù)背景下的差值集計(jì)算量巨大的問題。

每組實(shí)驗(yàn)分別做了5次測試，取5次平均時(shí)間作為最終結(jié)果，如圖6所示。

圖6 算法時(shí)間效率

由圖6可知，Spark平臺參與運(yùn)算的子節(jié)點(diǎn)數(shù)量越多，算法執(zhí)行時(shí)間顯著減少，說明Spark平臺可以較好地解決大數(shù)據(jù)的運(yùn)行效率問題。采用Spark平臺進(jìn)行差分隱私數(shù)據(jù)發(fā)布可有效保證發(fā)布數(shù)據(jù)的隱私安全及運(yùn)算效率。

4 結(jié) 語

為了提高隱私數(shù)據(jù)的保護(hù)程度和保證數(shù)據(jù)挖掘結(jié)果的可用性，解決海量靜態(tài)數(shù)據(jù)直方圖發(fā)布過程中差值集計(jì)算效率低、存在隱私泄露安全隱患問題，研究了大數(shù)據(jù)背景下的差分隱私保護(hù)數(shù)據(jù)發(fā)布方法，提出一種Spark框架下的滿足差分隱私保護(hù)的直方圖數(shù)據(jù)發(fā)布方法。本文借助Spark計(jì)算平臺實(shí)現(xiàn)對海量數(shù)據(jù)的分類統(tǒng)計(jì)、聚類分析和分析結(jié)果的差分隱私保護(hù)。文中給出了數(shù)據(jù)處理的計(jì)算框架，并對各部分做了簡要闡述。通過對實(shí)驗(yàn)結(jié)果中的總體誤差和隱私預(yù)算ε進(jìn)行分析，相較于GS方法和S-GS方法數(shù)據(jù)可用性上更佳，而且解決了S-GS方法在海量數(shù)據(jù)計(jì)算中的差值集計(jì)算問題，滿足數(shù)據(jù)隱私安全性需求，同時(shí)保證發(fā)布數(shù)據(jù)具有較好的可用性，具有一定的應(yīng)用價(jià)值。