王 濤,溫 蜜

(上海電力學院 計算機科學與技術學院,上海 200090)

1 引言

現代社會已經邁入了大數據時代,海量數據帶來的巨大研究價值無論對于國家的宏觀調控,企業(yè)的決策分析還是疾病的預防控制等方面的影響都不容忽視.因此,政府、企業(yè)或者社會機構每年都會收集或者發(fā)布大量的數據以供分析研究之用,而這些數據中通常含有個人不想被公開的敏感信息,包括個人的疾病、收入等等.因此,如何在數據發(fā)布時防止個人敏感信息的泄露就成為了一個重要的研究議題.為此k-匿名模型[1-4]、l-多樣性模型[5-7]和t-接近模型[8,9]等匿名模型相繼被提出,這些模型大多采用將準標識符屬性泛化和增加敏感屬性多樣性的方式,使得攻擊者無法確切地推斷出一個分組內的某條記錄具體屬于哪個人,從而達到防止個人敏感信息泄露的目的.這些模型針對分類型敏感信息可以起到良好的保護作用,但是對于數值型敏感屬性卻不能起到抗近鄰泄露的作用.近鄰泄露的概念在文獻[10]中被首次提出,主要是指由于同一個分組內不同記錄的數值型敏感屬性值之間距離太過接近,使得攻擊者可以以較大概率推測出其中某條記錄的敏感屬性值的所在區(qū)間而導致敏感信息泄露的情況.由于數值型敏感屬性的特點,原始數據即便經過以上幾種匿名模型的處理,敏感信息仍然會有發(fā)生近鄰泄漏的風險,因為只是增加一個分組內敏感屬性值的多樣性而不對敏感屬性值間的距離加以限制,如果一個分組內的敏感屬性值集中分布在一個較小區(qū)間內,那么攻擊者通過背景信息確定被攻擊者所在的分組后,就可以在不需要知道被攻擊者的確切敏感屬性值的情況下獲取到被攻擊者敏感屬性值的大致范圍,從而導致近鄰泄漏發(fā)生.針對數值型敏感屬性易發(fā)生近鄰泄漏這一問題,本文提出了一種新的匿名模型——(εi,k)-匿名模型,該模型首先基于聚類方法將按照升序排列的敏感屬性值劃分到多個值域區(qū)間內,然后通過對每個值域區(qū)間設置相應的閾值εi來控制該子區(qū)間內敏感屬性值的接近程度,最后通過將準標識屬性和敏感屬性分開發(fā)布的方式來提高數據的可用性.

2 相關工作

針對抗數值型敏感屬性近鄰泄漏問題,文獻[11]提出了(k,e)-匿名模型,該模型要求每個分組內至少要包含k條記錄,并且要求每個分組內最大和最小敏感屬性值的差值要大于等于閾值e,以此來達到擴大分組內敏感屬性值分布范圍的目的.但是由于沒有對分組內的敏感屬性值的分布情況加以限制,在閾值e設置的足夠大的條件下,如果分組內的大部分敏感屬性值集中分布在一個密集區(qū)域內,那么攻擊者仍然可以以較大的概率推斷出某個人的敏感屬性值所在的大致區(qū)間,從而導致近鄰泄露的發(fā)生.文獻[10]提出了(ε,m)-匿名模型,該模型要求對于每個分組內的每條記錄t,若其敏感屬性值是x,那么在這個分組中,敏感屬性值落在區(qū)間[x-ε,x+ε]內的記錄數不能超過該分組內元組總數的1/m,其中ε是為了控制每個分組內敏感屬性值之間的接近程度而設置的閾值.該模型對整個敏感屬性值值域區(qū)間只設置一個閾值ε,這種單一的閾值ε可能無法滿足實際使用需求,尤其是當敏感屬性值集中分布在幾個相距較遠的區(qū)間時.因為不同敏感屬性值的敏感度不同,相距較遠的不同區(qū)間內的敏感屬性間敏感度的差異則更大,單一的閾值ε無法滿足敏感屬性值敏感度多樣性所帶來的閾值多樣性的要求.文獻[12]提出了分級l-多樣性模型,該模型首先需要將數值型敏感屬性值域分級,再基于分級信息實現數值型敏感屬性的l-多樣性.由于該模型增加了分組內分級域多樣性的要求,可以看作是加強的l-多樣性模型,主要目的是提高同一個分組內敏感屬性值的相異度以達到抵抗近鄰泄露的目的.該文獻要求等距離對敏感屬性值域進行區(qū)間劃分,然后再對每個區(qū)間設置等級,按照等距離原則劃分區(qū)間沒有考慮區(qū)間內敏感屬性值的分布情況,這樣還是可能導致出現一個分組內敏感屬性值過于接近的問題,從而引發(fā)近鄰泄露.

為了更加有效地解決數值型敏感屬性近鄰泄露問題,在之前文獻工作的基礎上,本文面向數值型敏感屬性提出了一種新的匿名模型——(εi,k)-匿名模型.首先該模型通過按照敏感屬性的靈敏度劃分敏感屬性值域區(qū)間,克服了以往區(qū)間劃分方案的不足之處；其次,通過對每個值域區(qū)間設置不同的閾值εi克服了以往設置單一閾值沒有考慮不同敏感屬性值敏感度不同的缺點.最后通過理論分析和仿真實驗驗證了本文所提出的(εi,k)-匿名模型在信息可用性和執(zhí)行效率方面的優(yōu)越性.

3 面向數值型敏感屬性(εi,k)-匿名模型

本文提出的(εi,k)-匿名模型主要包括以下內容:敏感屬性值域區(qū)間劃分算法、(εi,k)-匿名原則和最大桶優(yōu)先提取算法.首先根據基于敏感屬性值間的距離將敏感屬性值劃分到若干值域區(qū)間內,然后為每個區(qū)間設置一個閾值εi,通過最大桶優(yōu)先提取算法使生成的匿名表中的每個分組滿足(εi,k)-匿名原則,以此來降低每個分組內敏感屬性值的近鄰泄露風險.接下來將對提出的(εi,k)-匿名模型展開詳細的介紹.

3.1 敏感屬性值域區(qū)間劃分算法

解決數值型敏感屬性近鄰泄漏問題,首要的工作是對敏感屬性值值域區(qū)間進行劃分.文獻[12]采用等間距法劃分區(qū)間,將敏感屬性值值域劃分成若干個長度相同的區(qū)間,該方法簡單易行但缺點明顯,就是沒有考慮敏感屬性值的分布情況和不同敏感屬性值敏感度的不同,從而可能導致大量的信息損失.文獻[13]中的極大熵法采取了一個使熵最大化、信息損失量最小化的原則來劃分區(qū)間.一般來說區(qū)間的個數越多,信息損失量就越小.然而,該方法受到樣本容量、最多區(qū)間個數等方面的制約,很難做到使熵最大化[14].

為了彌補以上辦法的不足,本文按照“高內聚低耦合”的原則基于敏感屬性值間的距離對區(qū)間進行劃分,使得同一區(qū)間內的屬性值盡量集中分布,不同區(qū)間的屬性值則盡量遠離.在正式提出本文的區(qū)間劃分算法之前,先給出以下定義.

定義1(敏感屬性值的敏感度).敏感屬性值間的距離對敏感屬性值近鄰泄露風險程度的影響隨著敏感屬性值的增大而增大,敏感屬性的這種性質被稱為“敏感度”.

定義2(相對歐氏距離).對于單維數值型敏感屬性值v1、v2(為了方便說明假設v2≥v1≥0)而言,其歐氏距離[14]d12=v2-v1,則v1和v2之間的相對歐氏距離表示為

下面給出如下定理.

定理1.任意兩個敏感屬性值間的相對歐氏距離在區(qū)間[0,1)內.

推論1.兩點之間的相對歐氏距離與歐氏距離之間不具有正相關性.

證明.采用反證法,設坐標軸上有以下四個點P1、P2、P3、P4,其坐標值依次為10、20、1000、1020,則P1和P2之間的歐氏距離d12等于10,相對歐氏距離等于0.33,P3和P4之間的歐氏距離d34等于20,相對歐氏距離等于0.01,由此可見,雖然P1和P2間的歐氏距離小于P3和P4之間的歐氏距離,但是P1和P2點之間的相對歐氏距離卻大于P3和P4點之間的相對歐氏距離,證明完畢.

推論2.如果兩點間的歐氏距離相同,那么敏感屬性值取值越大,則相應的相對歐氏距離越小.

證明.假設兩點間的歐氏距離d12=v2-v1,則v2=v1+d12,則由于當d12固定不變時,是關于v1的增函數,而d˙12在的值域上關于是遞減的,所以當d12是常量時,敏感值取值越大,相應的相對歐氏距離越小.

有了相對歐氏距離作為距離度量標準之后,下面正式提出本文的敏感屬性值域區(qū)間劃分算法(假定數軸上一共存在有b個點).

1)將各條記錄的敏感屬性值提取出來按照升序方式以此排列在數軸上.

2)計算數軸上每兩個相鄰點之間的相對歐氏距離(i=1,2,···,b-1,j=i+1).

4)比較每兩個敏感屬性值間的相對歐氏距離(將第一個點和最后一個點默認為第一個值域區(qū)間的左端點和最后一個區(qū)間的右端點) 與平均相對歐氏距離的 大小,如果≤,則說明這兩個點可以劃分到同一個區(qū)間內,這兩點不作為值域區(qū)間端點,如果≥,則說明這兩點距離過大,應在這兩個點處對區(qū)間進行拆分,i點作為生成的左側區(qū)間的右端點,j點作為生成的右側區(qū)間的左端點.

5)當步驟4)全部完成后,生成所有的敏感屬性值域區(qū)間.

值得注意的是,在第4)步中,本文以平均相對歐氏距離作為比較的基準,用戶也可以根據實際需要,將平均相對歐氏距離乘以參數w(w的取值在0.5 到1 之間為宜)來作為比較時的參照距離.下面通過一個示例來對算法的執(zhí)行過程進行說明.若原始數據表包含如下敏感屬性值100、150、4500、5200、4800、200,首先將這些敏感屬性值按升序排列成100、150、200、4500、4800、5200 的形式,計算出相鄰兩點間的相對歐氏距離分別為0.2、0.143、0.915、0.032、0.04,取平均相對歐氏距離(=0.266)作為比較時的參照距離,由于200 和4500 間的相對歐氏距離大于平均相對歐氏距離,所以需要在這兩點處對區(qū)間進行拆分,由此形成 兩個分別包含100、150、200 和4500、4800、5200 三個敏感屬性值的值域區(qū)間.

3.2 (εi,k)-匿名原則

在正式提出本文的(εi,k)-匿名原則之前,首先給出以下定義.給定數據表T,SA是T的敏感屬性,其中記錄t的敏感屬性值為V,用t.SA來表示記錄t的敏感屬性值大小.

定義3(區(qū)間閾值εi).在劃分完敏感屬性值域區(qū)間后,需要為每個敏感屬性值域區(qū)間Pi(i=1,…,n)設置一個閾值εi(i=1,…,n)來控制該值域區(qū)間內數值之間的接近程度.

定義4(t的εi鄰域I(t)).對于區(qū)間Pi(i=1,…,n)中的記錄t來說,其εi鄰域表示為I(t)= [t.SA-εi,t.SA+εi].

定義5(t的εi鄰域集N(t)).給定數據表T’,t是分組E中的任意元組,記錄t的εi鄰域集N(t)表示在敏感屬性值域區(qū)間內落在記錄t 的εi鄰域I(t)內的記錄的集合,N(t)={t’|t’≠t,t’.SA=Vj,Vj? [t.SA-εi,t.SA+εi]}.用|N(t)|表示t的εi鄰域集中所包含元組的數目.

定義6(t的近鄰泄露風險).對于給定的數據表T’,分組E中的任意一條記錄t的近鄰泄露風險定義為:Pbrh(t,εi)=|N(t)|/|E|,其中|E|表示分組E中所包含元組的數目.

給出以上定義之后,下面正式提出(εi,k)-匿名原則.給定數據表T’,如果對于T’中的所有的分組E都滿足以下條件,則稱T’是滿足(εi,k)-匿名原則的:

1) 每個分組內包含的元組數|E|在區(qū)間[k,2k]之間.

2) 每個分組內至少包含k條εi鄰域沒有交集的記錄.

定理2.若給定數據表T’滿足(εi,k)-匿名原則,那么對于表中任意元組E 中的每條記錄t來說,其敏感屬性值近鄰泄露風險≤1/2.

證明.由于滿足(εi,k)-匿名原則的每個分組內元組數目|E|限定在[k,2k]區(qū)間內,且每個分組內至少包含k條εi鄰域沒有交集的記錄,那么單就看這k條記錄是不存在近鄰泄露風險的,考慮在最壞情況下,剩余的|E|-k條記錄全部落在記錄t的εi鄰域內,那么在該分組內,記錄t的近鄰泄露風險最大,Pbrh(t,εi)=(|E|-k)/|E|=1-k/|E|,當|E|=2k時,Pbrh(t,εi)取得最大值1/2,證畢.

3.3 最大桶優(yōu)先提取算法

為了生成滿足(εi,k)-匿名原則的匿名數據表T’,本文提出了一種最大桶優(yōu)先提取算法,該算法首先桶按照桶內元組的數目降序排列,然后從前k個桶中提取出k條εi鄰域沒有交集的記錄,依次迭代進行,最后將未分配分組的元組按(εi,k)-匿名原則的要求分配到合適的桶中,從而生成滿足(εi,k)-匿名原則的匿名數據表T’.在介紹算法之前,先引出相關概念.

定義7(桶).將敏感屬性值域區(qū)間Pi(i=1,…,n)以其設定閾值εi(i=1,…,n) 為間隔劃分形成的小區(qū)間Sij(i=1,…,n,lmodεi≥j-1≥0,l是區(qū)間長度)稱為桶.

定義8(相鄰桶).來自同一個值域區(qū)間Pi(i=1,…,n)的兩個桶Sij(i=1,…,n,lmodεi≥j-1≥0)如果是相鄰的,則稱這兩個桶是相鄰桶.

定義9(桶的容量).桶的容量 每個桶內所包含元組的數目稱之為桶的容量.

給出了以上定義之后,下面給出最大桶優(yōu)先提取算法,具體算法如下.

輸入:原始數據表T,每個分組內至少包含的元組數k.輸出:只包含準標識符屬性的數據表QIT,只包含敏感屬性的數據表ST.1) 首先對原始表T 中的記錄根據其敏感屬性值的大小進行升序排列2)第一次劃分區(qū)間:見3.1 節(jié)敏感屬性值域區(qū)間劃分算法.3)為每個值域區(qū)間設置相應的閾值εi(由于數值敏感度的影響,值域區(qū)間內的數值越大,相應的該區(qū)間的閾值設置越高).4)第二次劃分區(qū)間:對每個值域區(qū)間以對應的閾值為間隔再次劃分生成若干個桶.5)根據桶內元組的數目,對得到的桶按降序處理.6)將前k 個桶的第一條記錄都提取出來.7)判斷:如果這k 個桶全部是非相鄰的,那么則可以直接將這k 條記錄放到第一個分組內.如果這k 個桶中含有相鄰桶,則需要進行判斷,如果這兩個敏感屬性值來自同一個值域區(qū)間,那么比較其差值是否大于該區(qū)間設定的閾值,如果大于則滿足提取條件可以直接提取,如果差值小于閾值,那么值域較小桶內提取記錄不變,從值域較大桶內的第二條記錄開始逐次提取,直到滿足兩條記錄的差值大于該區(qū)間設定的閾值.如果無法找到這樣的兩條記錄,那么說明這兩個桶內的數據分布過于接近,則隱藏其中的一個桶,提取第k+1 個桶重新比較,直到找到滿足條件的k 條記錄為止.8)提取結束之后,將提取出來的記錄從桶內剔除,按桶內元組的數量將桶重新降序排序.9)如果含有元組的桶的數量大于k 個,則重復執(zhí)行6)至8)步驟,每經過一個循環(huán)就會形成一個新的分組,直到含有記錄的桶的數目小于k 個為止或者剩余k 個但是提取不出滿足條件的記錄為止.10)對于剩余桶內的記錄,將其插入到已經存在的分組內,使得每個分組都滿足(εi,k)- 匿名原則.11)輸出一個準標識符表格QIT 和敏感屬性表ST,這樣就得到了滿足(εi,k)- 匿名原則的數據表格..,

4 實驗結果及分析

本章節(jié)通過實驗分析驗證(εi,k)- 匿名模型的性能,并將其同文獻[10]中的(ε,m)-anonymity 模型和文獻[12]中的分級l-多樣性模型進行比較.實驗所采用的數據集是真實數據集SAL,數據集來自http://ipums.org/.該數據集被廣泛應用作為實驗測試數據集.該數據集共包含了50 萬個元組,每個元組記錄了一個美國人的個人信息,本文提取了其中七個屬性進行研究,其中{Age,Sex,Race,Country,Birthplace,Occupation}作為準標識符屬性,Income 作為敏感屬性進行研究.本文將從信息可用性、算法執(zhí)行效率和兩個方面對三種方案進行比較.

4.1 信息可用性分析

在分析數據的可用性時,可以通過文獻[15]中的構造集合查詢語句的方式進行分析.查詢語句的形式如下所示:

select count(*) from SAL

where A1∈ b1and A2∈ b2and …Aw-1∈bw-1and Aw∈bw

其中,參數w被稱作查詢維度.A1,A2,…,Aw-1是w-1 個準標識符屬性,Aw是敏感屬性,bi(1≤i≤w)是屬性Ai的值域中的一個隨機區(qū)間.

信息可用性的高低采用平均相對誤差進行衡量.平均相對誤差用公式表示為ARErr= (act-est)/act.其中,act 表示查詢原始數據表得到的精確結果,est 表示查詢匿名后的數據表得到的結果.平均相對誤差越低說明信息可用性越高；否則,信息可用性越差.

圖1～圖3分別描述了數據集大小、準標識符屬性維數和ε(εi) 值的變化對(εi,k)-匿名模型、(ε,m)-anonymity 和分級l-多樣性模型的影響.

圖1 數據集大小對信息可用性的影響

由圖1可知,隨著數據集大小逐漸增大,(ε,m)-anonymity 和分級l-多樣性模型的相對錯誤率逐漸增大,這是由于隨著數據集的增加,準標識符屬性的泛化區(qū)間增加,這樣就會造成更多的信息損失,導致數據可用性下降.而(εi,k)-匿名模型的相對錯誤率則隨著數據集的增大而波動較小且其相對錯誤率一直低于(ε,m)-anonymity 和分級l-多樣性,這是因為(εi,k)-匿名模型并未采用對準標識符屬性泛化的方式來保護隱私,而是采用有損鏈接的方式將準確的準標識符屬性和敏感屬性分開發(fā)布,這樣就減少了泛化所帶來的信息損失,同時也減少了數據集大小變化所帶來的影響.

圖2 準標識符屬性個數對信息可用性的影響

由圖2可知,隨著準標識符屬性的增加,(ε,m)-anonymity 和分級l-多樣性模型的相對錯誤率逐漸增大,這是因為準標識符屬性維數的增大使在每個元組上進行泛化的屬性數目增加,在泛化過程中的信息損失也將增大,但是(εi,k)-匿名模型的相對錯誤率則受準標識符屬性維數變化的影響較小且低于(ε,m)-anonymity 和分級l-多樣性,理由同上.

圖3 ε(εi)值的變化對信息可用性的影響

在圖3中,由于l-多樣性模型沒有參數ε(εi),因此只比較了ε(εi)的變化對(ε,m)-anonymity 和(εi,k)-匿名模型的影響,為了方便比較,對于(ε,m)-anonymity,選擇參數β,令ε=βr,r表示整個敏感屬性值區(qū)間的長度,對于(εi,k)-匿名模型,令εi=βri(1≤i≤n) ,ri表示每個敏感屬性值域區(qū)間的長度,由圖3可知,隨著參數β的增大(ε和εi也隨之增大),(ε,m)-anonymity 和(εi,k)-匿名模型的相對錯誤率都會隨之增大,這是因為閾值ε(εi)越大,對敏感屬性的保護程度越高,不可避免的會導致信息的可用性下降.

綜合上面對圖1～圖3的分析可以看出,本文所提出的(εi,k)-匿名模型同文獻[1 0]中的(ε,m)-anonymity 和文獻[12]所提出的l-多樣性模型相比,在數據集大小、準標識符屬性個數和ε(εi)值變化三者的影響下,(εi,k)-匿名模型的信息的可用性都是最高的.

4.2 算法執(zhí)行效率分析

圖4表示準標識符屬性維數對算法執(zhí)行時間的影響,由圖4可知,隨著準標識符屬性維數的增加,分級l-多樣性和(ε,m)-anonymity 執(zhí)行時間增加明顯,(εi,k)-匿名模型則基本保持不變.這是由于(εi,k)-匿名模型不需要對準標識符屬性進行泛化,所以基本不受準標識符屬性維數增加的影響,而隨著準標識符屬性的增加,分級l-多樣性和(ε,m)-anonymity 需要泛化的屬性增多,導致執(zhí)行時間上升.值得注意的是,當敏感屬性值維數較少時,(εi,k)-匿名模型的執(zhí)行時間大于分級l-多樣性和(ε,m)-anonymity,這是由于(εi,k)-匿名模型增加了對敏感屬性值劃分區(qū)間的算法,導致其執(zhí)行時間增加.

圖5表示數據集大小對三種方案執(zhí)行時間的影響,由圖可知,隨著數據集的增大,三種方案需要處理的元組 增加,執(zhí)行時間都呈上升趨勢.

圖4 準標識符屬性個數對算法執(zhí)行時間的影響

圖5 數據集大小對算法執(zhí)行時間的影響

綜合上面對圖4～圖5的分析可以看出,在算法執(zhí)行效率方面,(εi,k)-匿名模型同(ε,m)-anonymity 和分級l-多樣性模型相比,在準標識符屬性較少時,(εi,k)-匿名模型的執(zhí)行效率略低于(ε,m)-anonymity 和分級l-多樣性模型,但是隨著準標識符屬性個數的增加,(εi,k)-匿名模型執(zhí)行效率開始反超(ε,m)-anonymity 和分級l-多樣性模型；隨著數據集的逐漸增大,(εi,k)-匿名模型的執(zhí)行效率總是略低于l-多樣性模型,但總是高于(ε,m)-anonymity.

5 結論

本文針對數值型敏感屬性近鄰泄露問題,提出了一種新的匿名模型——(εi,k)-匿名模型,該模型通過劃分敏感屬性值域區(qū)間,為每個敏感值域區(qū)間設定相應的閾值εi來控制每個值域區(qū)間內敏感值的近鄰泄露風險.理論分析和試驗結果表明,該模型能夠在有效抵御數值型敏感屬性近鄰泄露攻擊的同時保證了較高的數據可用性和較高的執(zhí)行效率,可以作為現有隱私保護技術手段的有效補充.