基于信息熵的數據集重標識風險評估方法*

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

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

0 引言

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

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

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

圖1 重標識攻擊：兩個數據庫關聯

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

1 基于信息熵的重標識風險評估方法

本節首先介紹構建的重標識風險評估模型，接著分別對模型的三因素進行評估與刻畫，最后闡述重標識風險綜合評估方法與步驟。

1.1 評估模型

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

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

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

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

定義2去標識數據集的脆弱性維度(簡稱脆弱性維度)：去標識數據集的脆弱性對應的準標識符個數。例如脆弱性#(A1)的維度為1，#(A1，A2)的維度為2。

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

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

1.2 風險三因素的評估與刻畫

為了方便后續的風險評估，作以下的攻擊場景假設：

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

假設2(攻擊者目標)：攻擊者發起重標識攻擊的目標是為了恢復去標識數據集D(A1，A2，…，Am)記錄對應的身份，以及獲取該身份關聯的敏感屬性值和準標識符屬性值。

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

1.2.1 脆弱性的嚴重程度

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

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

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

1.2.2 特定脆弱性的攻擊頻率

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

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

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

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

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

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

對于數值型的屬性：

其中：

對于類別型的屬性：

其中：

1.3 重標識風險綜合評估方法

1.3.1 特定脆弱性的風險與平均風險分數評估

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

其中，probi和impacti分別表示該脆弱性帶來風險發生可能性以及導致的危害性。

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

1.3.2 綜合風險分數快速評估新方法

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

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

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

算法1.脆弱性增量發現算法

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

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

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

(4)整體數據集的重標識數據風險綜合評估。結合式(13)、(14)，得：

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

2 實驗結果與分析

2.1 數據集與參數設置

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

2.2 重標識風險評估實驗

(1)實驗1：敏感屬性對重標識風險的影響

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

圖3 兩個數據集的重標識風險分布

(2)實驗2：不同維度數據集對重標識風險的影響

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

圖4 不同維度的數據集對重標識風險的影響

(3)實驗3：不同去標識程度對重標識風險的影響

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

圖5 不同的去標識程度對重標識風險的影響

3 結論

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