基于信息熵的數(shù)據(jù)集重標(biāo)識風(fēng)險評估方法*

陳 磊 ，薛見新 ，張潤滋 ，劉文懋

(1.綠盟科技集團股份有限公司，北京 100089；2.清華大學(xué) 自動化系，北京 100084)

0 引言

在大數(shù)據(jù)時代下，數(shù)據(jù)共享、發(fā)布和交易等場景需求變得越來越多，一方面促進了數(shù)據(jù)流通與價值利用，另一方面引發(fā)的個人數(shù)據(jù)與隱私安全事件近年來呈現(xiàn)爆發(fā)趨勢[1]。

為了應(yīng)對挑戰(zhàn)，在法規(guī)層面，全球掀起了數(shù)據(jù)隱私的立法熱潮，如歐盟《通用數(shù)據(jù)保護條例》(GDPR)、美國《加州消費者隱私法案》(CCPA)等。我國2017年實施的《網(wǎng)絡(luò)安全法》，其中一個章節(jié)專門明確個人信息安全；此外，我國《個人信息保護法》在加快立法與制定中。在技術(shù)層面，如何平衡數(shù)據(jù)利用與隱私保護問題，已經(jīng)成為學(xué)術(shù)界和工業(yè)界的一大研究熱點[2]。當(dāng)前，已經(jīng)發(fā)展出了保留格式加密(Format-Preserving Encryption，F(xiàn)PE)[3]、差分隱私(Differential Privacy，DP)[4]、K-匿名(K-Anonymity)[5]和L-多樣性(L-Diversity)[6]以及去標(biāo)識化(De-identification)[7]等技術(shù)。其中，去標(biāo)識化技術(shù)通過對原始個人信息進行部分屏蔽、泛化和失真等數(shù)據(jù)變換操作，是一種意圖消除“個人身份”的隱私保護技術(shù)。由于其處理規(guī)則簡單靈活且易于并行處理(高效)，目前在隱私保護的數(shù)據(jù)發(fā)布和數(shù)據(jù)挖掘等實際場景中有廣泛應(yīng)用與部署。通常，在工業(yè)界習(xí)慣稱為“數(shù)據(jù)脫敏”。

然而研究發(fā)現(xiàn)，去標(biāo)識化并不能達到理想的“完全消除個人身份”的狀態(tài)，例如歐盟29 條工作組在一份研究報告指出，去標(biāo)識化是緩解/降低重標(biāo)識風(fēng)險(mitigating the risks)的有效手段，但不能完全消除殘余風(fēng)險(Residual Risk)[8]。此外，隨著數(shù)據(jù)資源的公開或個人數(shù)據(jù)庫的泄露(攻擊者可通過各種渠道獲取更多的攻擊資源)，一些實際的攻擊案例證明經(jīng)過去標(biāo)識化處理后得到的數(shù)據(jù)集仍然存在重標(biāo)識攻擊(Re-identification Attack)的風(fēng)險與可能性。一個經(jīng)典的案例：美國馬薩諸塞州發(fā)布了醫(yī)療患者信息數(shù)據(jù)庫，去掉患者的姓名和地址信息，僅保留患者的ZIP、Birthday、Sex 和Diagnosis 等信息。研究人員發(fā)現(xiàn)，存在一個可訪問的公開數(shù)據(jù)庫是州選民的登記表，它包括選民的ZIP、Birthday、Sex、Name 以及Address 等詳細個人信息。將這兩個數(shù)據(jù)庫的同屬性段{ZIP，Birthday，Sex}進行關(guān)聯(lián)與鏈接操作，如圖1所示，可恢復(fù)出大部分選民的醫(yī)療健康信息，從而造成一起嚴重的醫(yī)療隱私泄露事故[5]。因此衡量和評估不同的去標(biāo)識數(shù)據(jù)的風(fēng)險程度與級別是一個重要的問題。

圖1 重標(biāo)識攻擊：兩個數(shù)據(jù)庫關(guān)聯(lián)

本文針對該問題，基于Shannon 信息熵和信息安全風(fēng)險評估框架，提出了一種綜合的重標(biāo)識風(fēng)險評估方法。

1 基于信息熵的重標(biāo)識風(fēng)險評估方法

本節(jié)首先介紹構(gòu)建的重標(biāo)識風(fēng)險評估模型，接著分別對模型的三因素進行評估與刻畫，最后闡述重標(biāo)識風(fēng)險綜合評估方法與步驟。

1.1 評估模型

基于信息安全風(fēng)險評估框架[9]，本文對重標(biāo)識攻擊場景的風(fēng)險進行建模：重標(biāo)識風(fēng)險值由重標(biāo)識攻擊發(fā)生的可能性(記為prob)以及導(dǎo)致的危害性(記為impact)兩部分組成。進一步地，風(fēng)險的可能性由去標(biāo)識數(shù)據(jù)集的脆弱性的嚴重程度(簡稱脆弱性的嚴重程度，記為v)和利用該脆弱性發(fā)起重標(biāo)識攻擊的頻率(也稱特定脆弱性的攻擊頻率，記為f)兩個因素有關(guān)；基于“屬性越敏感，對攻擊者的價值越大，其危害也越大”事實，風(fēng)險的危害性可描述為與脆弱性的嚴重程度，以及利用該脆弱性實施攻擊導(dǎo)致的隱私泄露程度(也稱特定脆弱性的隱私泄露程度，記為l)兩個因素相關(guān)。評估模型綜合以上風(fēng)險的多個要素，采用乘法原則，那么某個脆弱性導(dǎo)致的風(fēng)險分數(shù)可表述為：

其中，prob=v×f，impact=v×l。風(fēng)險值Riskscore 的取值區(qū)間為[0，1]，其分值越大，表示風(fēng)險越大。

由上述模型可知，脫敏數(shù)據(jù)集的脆弱性分析與評估是關(guān)鍵。下面通過例子進行闡述。如圖2(a)所示，假設(shè)有一個公開可訪問的去標(biāo)識數(shù)據(jù)集，它有5 條記錄(它實際依次對應(yīng)的身份為“Zhang Shan”、“Li Si”、“Wang Wu”、“Zhao Liu”和“Chen Qi”)，列屬性有3 個準標(biāo)識符(Sex、Age 和Address)和1 個敏感屬性(Income)。此外，假設(shè)存在掌握不同身份數(shù)據(jù)表的攻擊者，如圖2(b)～(d)所示：攻擊者Λ1掌握了“Name-Sex”身份數(shù)據(jù)表；攻擊者Λ2掌握了“Name-Age”身份數(shù)據(jù)表；攻擊者Λ3掌握了“Name-Sex-Age-Address”身份數(shù)據(jù)表。根據(jù)“Sex”的關(guān)聯(lián)性，攻擊者Λ1可恢復(fù)出圖2(a)表的第二行記錄的身份——“Li Si”，同時獲得她的敏感屬性Income 為“20K”，以及其他的身份屬性信息，即她的“Age”和“Address”。類似地，根據(jù)“Age”的關(guān)聯(lián)性，攻擊者Λ2可重新標(biāo)識出圖2(a)表的第一行記錄的身份——“Zhang Shan”。攻擊者Λ3根據(jù)“Sex”、“Age”和“Address”的關(guān)聯(lián)性，可重新標(biāo)識出圖2(a)表的第一、二、三行記錄的身份——“Zhang Shan”、“Li Si”和“Wang Wu”。由此可見，攻擊者Λ1根據(jù)去標(biāo)識數(shù)據(jù)表的“Sex”列，攻擊者Λ2根據(jù) “Age”列，攻擊者Λ3根據(jù)“Sex”列、“Age”列和“Address”列分別重新標(biāo)識出部分記錄的身份，造成一定的隱私泄露。攻擊者利用的這些“單列”以及“列組合”可以看作是去標(biāo)識數(shù)據(jù)集上客觀存在的各種不同的脆弱性。

定義1去標(biāo)識數(shù)據(jù)集的脆弱性(簡稱脆弱性)：去標(biāo)識化數(shù)據(jù)集D(A1，A2，…，Am)準標(biāo)識符屬性(包括A1，A2，…，Aω)中的一列或多列組合的關(guān)聯(lián)特性可能被掌握不同攻擊資源的攻擊者利用，它們統(tǒng)稱為去標(biāo)識數(shù)據(jù)集的脆弱性。它們可分別表示為脆弱性#(A1)、#(A2)、#(A1，A2)和#(A1，A2，…，Aω)。

定義2去標(biāo)識數(shù)據(jù)集的脆弱性維度(簡稱脆弱性維度)：去標(biāo)識數(shù)據(jù)集的脆弱性對應(yīng)的準標(biāo)識符個數(shù)。例如脆弱性#(A1)的維度為1，#(A1，A2)的維度為2。

定義3特定脆弱性被攻擊頻率：去標(biāo)識化數(shù)據(jù)集D(A1，A2，…，Am)的某個特定脆弱性被攻擊者攻擊的總次數(shù)。

定義4特定脆弱性的隱私泄露程度：攻擊者利用去標(biāo)識化數(shù)據(jù)集D(A1，A2，…，Am)的某個特定脆弱性，比如#(A1)、#(A2)和#(A1，A2)，發(fā)起重標(biāo)識攻擊，導(dǎo)致敏感屬性和準標(biāo)識符屬性數(shù)據(jù)泄漏的情況。

1.2 風(fēng)險三因素的評估與刻畫

為了方便后續(xù)的風(fēng)險評估，作以下的攻擊場景假設(shè)：

假設(shè)1(可獲取去標(biāo)識數(shù)據(jù)集)：攻擊者可以訪問、查詢或下載去標(biāo)識數(shù)據(jù)集。比如數(shù)據(jù)發(fā)布場景中，攻擊者隱藏在接收者中接收到數(shù)據(jù)集。

假設(shè)2(攻擊者目標(biāo))：攻擊者發(fā)起重標(biāo)識攻擊的目標(biāo)是為了恢復(fù)去標(biāo)識數(shù)據(jù)集D(A1，A2，…，Am)記錄對應(yīng)的身份，以及獲取該身份關(guān)聯(lián)的敏感屬性值和準標(biāo)識符屬性值。

假設(shè)3(攻擊者能力)：攻擊者掌握身份數(shù)據(jù)集，且該數(shù)據(jù)集屬性包括去標(biāo)識數(shù)據(jù)集的準標(biāo)識符屬性字段列，假設(shè)掌握任意該屬性列的概率為p。

1.2.1 脆弱性的嚴重程度

由定義2 可知，對于去標(biāo)識數(shù)據(jù)集D(A1，A2，…，Am)(前ω 列是準標(biāo)識符對應(yīng)的屬性列)，維度為1的脆弱性為#(A1)，#(A2)，…，#(Aω)，即該類型脆弱性的個數(shù)為；維度為2 的脆弱性為#(A1，A2)，#(A1，A3)，…，#(Aω-1，Aω)，即該類型脆弱性的個數(shù)為。依次類推，維度分別為3，4，…，ω 的脆弱性個數(shù)為。因此，脆弱性總個數(shù)為：

對以上W 個脆弱性的嚴重程度進行評估。定性地分析，脆弱性的嚴重程度與數(shù)據(jù)集的分布密切相關(guān)：若脆弱性對應(yīng)的列或列組合的數(shù)據(jù)分布越集中(即每條記錄的取值趨向唯一)，攻擊越有可能發(fā)起重標(biāo)識攻擊，即重新標(biāo)識出大部分記錄對應(yīng)的身份。綜合考慮，本文選取信息熵[10]對脆弱性的嚴重程度進行刻畫，有兩點原因：(1)信息熵可有效反映數(shù)據(jù)分布情況。熵值越大，數(shù)據(jù)分布越集中，脆弱性嚴重性越大。(2)信息熵可有效反映攻擊者獲取的信息量。熵值越大，獲取平均信息量越大，脆弱性嚴重性越大。因此，使用信息熵公式可以對每一種脆弱性#()的嚴重程度進行逐一刻畫與度量。假設(shè)去標(biāo)識數(shù)據(jù)集總共有n 條記錄，為了方便統(tǒng)一評估與比較，對信息熵進行歸一化，可得：

其中，由于0≤H(#)≤Hmax=logn，那么歸一化熵值為v∈[0，1]。

1.2.2 特定脆弱性的攻擊頻率

定性地分析，對于任意一種特定的脆弱性，其攻擊的頻率與脆弱性被利用的難易程度成反比關(guān)系：脆弱性被利用的難度系數(shù)ρ 越小，其攻擊頻率f越大，所以可刻畫為倒數(shù)關(guān)系：

而脆弱性被利用的難度系數(shù)ρ 與脆弱性的維度φ 密切相關(guān)：脆弱性的維度φ 越大，即包含的準標(biāo)識符個數(shù)越多，其被利用的難度系數(shù)ρ 越大。因此，需設(shè)計一條衰減函數(shù)ρ=F(φ)，可充分反映兩者相互影響的關(guān)系趨勢。

基于假設(shè)2，攻擊者掌握的準標(biāo)識符個數(shù)可看成n 次(最多掌握n 個準標(biāo)識符)獨立重復(fù)的伯努利試驗，其每個屬性掌握的概率為p，即建模為二項分布(n，p)。從攻擊者角度看，大部分攻擊者掌握的準標(biāo)識符個數(shù)在np 附近，掌握t 個準標(biāo)識符的概率為。從脆弱性角度看，對于一個維度為φ 的脆弱性，掌握φ 個及以上的準標(biāo)識符的攻擊者均可利用。因此，難度系數(shù)ρ 可賦值為所有可能的攻擊者利用該脆弱性的概率累加和的倒數(shù)，即：

聯(lián)合式(4)和式(5)，維度為φ 脆弱性的攻擊頻率可表述為：

1.2.3 特定脆弱性的隱私泄露程度

定性地分析，對于任意一種特定的脆弱性，其成功攻擊后導(dǎo)致的隱私泄露包括兩方面：敏感屬性和準標(biāo)識符屬性的泄露數(shù)據(jù)。對于以上任意一種類型的屬性，本文定義其隱私泄露程度為“屬性的敏感程度”和“去標(biāo)識化程度”相乘得到。敏感屬性敏感程度sSA和準標(biāo)識符屬性敏感程度sQID可人工進行預(yù)定義(滿足0 ＜sQID＜sSA≤1.0)，比如敏感屬性sSA=1.0，sQID=0.05。而對于“去標(biāo)識程度”，定義以下的評估指標(biāo)進行刻畫：

對于數(shù)值型的屬性：

其中：

對于類別型的屬性：

其中：

1.3 重標(biāo)識風(fēng)險綜合評估方法

1.3.1 特定脆弱性的風(fēng)險與平均風(fēng)險分數(shù)評估

對于去標(biāo)識數(shù)據(jù)集D(A1，A2，…，Am)的第i 個脆弱性可表示為#i，假設(shè)使用上一節(jié)的評估方法，分別得到脆弱性的嚴重程度、攻擊頻率和隱私泄露頻率分別為vi、fi和li，那么該脆弱性導(dǎo)致的風(fēng)險分數(shù)可表述為：

其中，probi和impacti分別表示該脆弱性帶來風(fēng)險發(fā)生可能性以及導(dǎo)致的危害性。

分別計算去標(biāo)識數(shù)據(jù)集D(A1，A2，…，Am)所有脆弱性的風(fēng)險分數(shù)，然后綜合風(fēng)險分數(shù)求平均，可得到該去標(biāo)識數(shù)據(jù)集的平均風(fēng)險分數(shù)：

1.3.2 綜合風(fēng)險分數(shù)快速評估新方法

上一小節(jié)風(fēng)險分數(shù)求平均是一種簡單的綜合評估方法，然而它存在以下的缺陷：(1)高維數(shù)據(jù)集的評估消耗時間長。由式(2)知，風(fēng)險分數(shù)評估為W=2ω-1，評估時間復(fù)雜度隨準標(biāo)識符維度ω 指數(shù)級增長。(2)求平均使所有的脆弱性帶來風(fēng)險權(quán)重相同，無法客觀地凸顯風(fēng)險的主要來源。

針對以上缺陷，本文繼續(xù)提出了一種新的替代方法——基于增量的快速綜合風(fēng)險評估方法。主要思想是低維的脆弱性風(fēng)險賦予更多的權(quán)重，這符合低維的脆弱性在實際攻擊場景中更容易發(fā)生。具體步驟描述如下：

(1)識別去標(biāo)識數(shù)據(jù)集D(A1，A2，…，Am)的脆弱性增量方向及增量大小Φ=(Δv1，Δv2，…，Δvm0)。脆弱性增量發(fā)現(xiàn)算法如算法1 所示。

算法1.脆弱性增量發(fā)現(xiàn)算法

輸入：去標(biāo)識數(shù)據(jù)集D(A1，A2，…，Am)和準標(biāo)識符屬性集(A1，A2，…，Aw)。

(2)脆弱性發(fā)生的可能性綜合評估。表示熵值增量及利用概率的累加，即：

(3)脆弱性導(dǎo)致的隱私泄露危害性綜合評估。表示熵值增量及隱私泄露的累加，即：

(4)整體數(shù)據(jù)集的重標(biāo)識數(shù)據(jù)風(fēng)險綜合評估。結(jié)合式(13)、(14)，得：

對本節(jié)兩種綜合評估算法的計算復(fù)雜度進行簡單的分析與比較：對于平均風(fēng)險評估，其信息熵(數(shù)據(jù)集分布)的計算次數(shù)為M=2m0，時間復(fù)雜度為O(2m0)，而快速綜合風(fēng)險計算信息熵的次數(shù)為m0，時間復(fù)雜度為O(m0)。一般來說，m0≥5，因此效率上后者顯然優(yōu)于前者。

2 實驗結(jié)果與分析

2.1 數(shù)據(jù)集與參數(shù)設(shè)置

在試驗仿真環(huán)境中，使用PC，其參數(shù)為Intel?CoreTMi7-6700 CPU@3.40 GHz 處理器，8.00 GB 內(nèi)存，64 位Windows 7 操作系統(tǒng)。評估算法通過Python代碼實現(xiàn)。數(shù)據(jù)集使用公開的UCI-Adult 數(shù)據(jù)集，它是在美國1994 年人口普查數(shù)據(jù)庫中抽樣得到的子數(shù)據(jù)集，共有32 561 條記錄，已經(jīng)去除標(biāo)識符字段，可以看成一個去標(biāo)識數(shù)據(jù)集。UCI-Adult 數(shù)據(jù)集包含15 個描述屬性，本文選擇其中的10 個準標(biāo)識符屬性(Quasi-Identification，QID)和1 個敏感屬性(Sensitive Attribute，SA)——income 屬性(取值為‘＜=50K’和‘＞50K’)作為待評估的原始數(shù)據(jù)集。實驗過程采用的參數(shù)p=0.3，num=20。此外，QID 和SA 的敏感程度分別假設(shè)為sQID=0.05，sSA=0.5。

2.2 重標(biāo)識風(fēng)險評估實驗

(1)實驗1：敏感屬性對重標(biāo)識風(fēng)險的影響

該實驗有兩個數(shù)據(jù)集，一個為原始的UCI-Adult數(shù)據(jù)集，另一個是不包含‘income’屬性列的UCIAdult 數(shù)據(jù)集。使用1.3.2 節(jié)提出的快速評估方法，首先將根據(jù)算法1 得到的脆弱性增量屬性方向作為脆弱性增量屬性Ψ=(age，occupation，hours-perweek，education，relationship，workclass，race，sex，marital -status，native-country)，其對應(yīng)的熵值增量為Φ=(0.379 1，0.226 2，0.178 9，0.101 2，0.049 4，0.017 9，0.008 8，0.005 6，0.003 0，0.002 6)。對兩個數(shù)據(jù)集分別進行重標(biāo)識風(fēng)險評估，分別得到風(fēng)險分數(shù)為0.747 5、0.324 0。將其通過式(13)、(14)展開為可能性和危害性兩個維度，風(fēng)險分布可視化結(jié)果如圖3 所示。由圖可知，兩個數(shù)據(jù)集的可能性值相等，而包含income的數(shù)據(jù)集的危害值相比更大。這說明去除數(shù)據(jù)集的敏感屬性，重標(biāo)識攻擊發(fā)生可能性不變，但重標(biāo)識攻擊發(fā)生后造成的隱私泄露危害顯著地降低，這符合預(yù)期的評估目標(biāo)，因為后者沒有敏感屬性的泄露。

圖3 兩個數(shù)據(jù)集的重標(biāo)識風(fēng)險分布

(2)實驗2：不同維度數(shù)據(jù)集對重標(biāo)識風(fēng)險的影響

該實驗在10 個不同維度的去標(biāo)識數(shù)據(jù)集(下文簡稱數(shù)據(jù)集)上進行重標(biāo)識風(fēng)險評估。具體來說，它們的維度分別為2，3，4，…，11，它們均包含敏感屬性‘income’列，其他屬性從集合Ψ=(age，occupation，hours-per-week，education，relationship，workclass，race，sex，marital-status，native-country)中按順序獲取1，2，3，…，10 個準標(biāo)識符。對這10 個數(shù)據(jù)集分別進行評估，可得到可能值、危害值以及風(fēng)險分數(shù)，繪制的趨勢曲線如圖4 所示?？梢钥闯?，可能值、危害值以及風(fēng)險分數(shù)均隨著數(shù)據(jù)集維度的增大而增大，且維度達到一定數(shù)目(大于6)時三個值增長趨向穩(wěn)定。這在一定程度上反映了重標(biāo)識攻擊的風(fēng)險趨勢：①高維度數(shù)據(jù)集存在更多的脆弱性，且它包含低維子數(shù)據(jù)集所有的脆弱性，因此高維的風(fēng)險更大；②高維相比低維數(shù)據(jù)集，引入了新的脆弱性，但該脆弱性維度也隨之增大。根據(jù)1.2.2 節(jié)分析，可被攻擊者成功利用的概率更低，因此風(fēng)險隨著維度的增加將趨向平緩。進一步地，可得實際應(yīng)用的啟示：應(yīng)盡量避免高維數(shù)據(jù)集的發(fā)布與共享，遵循“最小化可用原則”，進而可降低隱私泄露的風(fēng)險。

圖4 不同維度的數(shù)據(jù)集對重標(biāo)識風(fēng)險的影響

(3)實驗3：不同去標(biāo)識程度對重標(biāo)識風(fēng)險的影響

該實驗在原始UCI-Adult 數(shù)據(jù)集以及三個不同去標(biāo)識化程度的數(shù)據(jù)集上進行。定義三個不同去標(biāo)識化處理的數(shù)據(jù)集：①低去標(biāo)識程度的數(shù)據(jù)集。它的2 個數(shù)值型屬性均進行量化處理，其量化步長為5，8 個類別型屬性進行隨機替換“*”屏蔽處理，屏蔽比例5%。②中去標(biāo)識程度數(shù)據(jù)集。同①的處理，其量化步長為10，屏蔽比例20%。③高去標(biāo)識程度數(shù)據(jù)集。同①的處理，其量化步長為10，屏蔽比例為60%。將這四個數(shù)據(jù)集進行重標(biāo)識風(fēng)險評估，其風(fēng)險可能性和危害性可展示為二維坐標(biāo)圖，如圖5所示。由圖可以看出，去標(biāo)識化程度越強，重標(biāo)識風(fēng)險攻擊發(fā)生的可能性以及危害性均呈現(xiàn)出下降趨勢。這可以客觀反映風(fēng)險的下降趨勢：一是數(shù)據(jù)集的去標(biāo)識化程度越大，那么記錄對應(yīng)的個人屬性組合的區(qū)分度越差，因此攻擊者成功實施重標(biāo)識攻擊的可能性更??；二是即使攻擊者通過重標(biāo)識攻擊可以將數(shù)據(jù)集的部分記錄對應(yīng)身份復(fù)原出來，由于大部分記錄的屬性已經(jīng)進行屏蔽和量化處理，因此對隱私泄露的危害相比更低一些。

圖5 不同的去標(biāo)識程度對重標(biāo)識風(fēng)險的影響

3 結(jié)論

本文基于Shannon 信息熵和信息安全風(fēng)險評估框架，提出了一種更為綜合的重標(biāo)識風(fēng)險評估方法，不僅刻畫了風(fēng)險的可能性維度，同時刻畫了其危害性維度。在具體評估中，首先將去標(biāo)識數(shù)據(jù)集的若干屬性組合建模為不同的脆弱性，然后針對每一種脆弱性進行多個維度的評估與刻畫。最后，為了評估整體數(shù)據(jù)集，構(gòu)造了一種基于信息熵值增量和加權(quán)的評估算法，實驗結(jié)果驗證了提出方案的有效性與可行性。