一種基于矩陣計算的數據開放隱私泄露評估方法

周旭晨 王智慧 王 宇 朱 云 李思勤 汪 衛

(復旦大學計算機科學技術學院 上海 201203)

(上海市數據科學重點實驗室(復旦大學) 上海 201203)

0 引 言

隨著大數據時代的來臨，數據的開放需求和使用價值日益提高，數據資源的開放和共享也成為熱門的研究方向。然而在現實中，數據開放和共享雖然是數據資源研究者共同的需求，但對數據擁有者而言，其帶來的隱私泄露風險是必須考慮的因素。

以醫療數據為例，醫院作為醫療數據擁有者，希望能夠開放醫療數據以支持醫療領域科學研究，也希望能夠共享到其他醫院或其他機構的醫療數據進行研究。但是，醫療數據通常包含較多的隱私信息，包括患者的個人信息、病情病史、就診情況和醫生的診斷情況等等。出于對隱私的考慮，醫院作為數據擁有者，不可避免地對數據開放持保留態度。

現有的隱私保護研究會對數據進行匿名化或其他擾動處理，使得數據開放后無法獲得原始數據，從而對數據隱私進行保護。但在當今對數據資源要求越來越高的情況下，擾動后的數據通常會影響數據使用者對數據的使用，進而影響相關研究成果。

數據擁有者有時在了解隱私泄露風險的情況下，愿意以一定的代價將數據開放。因此就需要研究者提供一套隱私泄露評估的手段，供數據擁有者了解數據開放可能帶來的隱私泄露風險，以此決定是否開放數據或以何種形式開放數據。本文將對現有的隱私保護研究進行概括總結，并提出一種基于矩陣計算的隱私泄露評估方法，以適應新的數據開放系統的需要。

1 相關工作

現有的隱私保護研究中有兩類比較重要的研究方向，其一是對數據進行匿名化處理，尤其是對其中的標識符等敏感信息。匿名化研究中，比較具有代表性的有文獻[1]提出的匿名化原則——k-匿名，文獻[2]提出的l-多樣性原則和文獻[3]提出的t-臨近原則等。從k-匿名到t-臨近，這些匿名化原則大多是將敏感屬性作為問題處理的關鍵，對其出現頻率、取值分布和取值多樣性，提出不同的限制，從而提出對應的原則來達到使個人隱私不被泄露的目的[4-5]。

基于匿名化的隱私保護模型，均會有不同的漏洞易被攻擊者利用。其原因在于模型的安全性都與攻擊者擁有的背景知識有關，而攻擊者擁有的背景知識很難被形式化地定義。因此，一個匿名化的隱私保護模型只能針對擁有特定假設下的背景知識的攻擊者。此外，以上的匿名化隱私保護模型沒有嚴格的數學理論作為依據，以有效地證明并表示隱私保護的強度，從而使得隱私保護的可靠性不夠強。

針對以上問題，Dwork等[6]在2006年首次提出了差分隱私保護模型。該模型具有嚴格的理論依據，并能夠嚴格地以參數表示隱私保護的強度。差分隱私描述的是一個對個體的承諾，即盡管攻擊者擁有較強的背景知識(主要來自于研究結果、發布數據集和其他信息來源)，個體的信息也不會因為其數據被用于研究而泄露。換言之，差分隱私保證了在從數據總體中獲得有效信息的同時，個體數據(即個人隱私)不會被泄露[7]。差分隱私的基本機制有拉普拉斯機制和指數機制兩大類，同時具有序列組合性和并行組合性兩大特性[8]。但差分隱私存在對背景知識的假設過強以及隱私預算分配比較困難，對專業知識要求較高等問題[9-11]。

2 數據開放中的隱私泄露評估

現有的隱私保護研究多致力于對數據中的敏感信息進行保護，但或多或少都會影響到數據的可用性，這在某些應用場景，尤其是要求使用原始數據的情形下，是不能被接受的。針對這種情況，本文對數據開放過程中的隱私泄露評估進行了研究。

2.1 問題分析與動機

本文提出的隱私泄露評估方法是基于數據開放背景的。所謂數據開放是指，數據擁有者上傳數據，數據使用者通過一定代價獲取自己需要的數據集進行使用。

數據開放能夠提供便利的數據共享服務，但這也引發了數據開放者對隱私問題的擔憂。數據開放者在上傳原始數據時，一定會考慮數據集里的敏感屬性是否會泄露，由此帶來的隱私風險如何。如果存在較大的風險，數據開放者會考慮是否開放這部分數據，或者需要數據使用者付出怎樣的代價來換取數據的使用權。

在這一過程中，數據開放帶來的隱私泄露風險能否被評估、能否被定量分析，就是數據開放者和數據擁有者共同關心的問題。因為只有能夠進行定量評估，才能供數據開放者參考，從而根據不同情況制定相應的開放策略。因此，數據開放過程中的隱私泄露評估是一個很值得研究的問題。

2.2 問題描述

圖1是隱私泄露評估系統的結構圖。數據開放者提供原始數據并根據自身隱私保護需求進行隱私等級標記。原始數據是指數據開放者希望進行開放共享的未經處理過的數據集，包含數據科學研究者感興趣的多方面內容。隱私等級標記f1,f2,…,fn是根據數據開放者自身的隱私保護需求，對開放數據集內包含的字段的隱私保護需求等級進行的標記，也包括了對字段間關聯關系的隱私等級標記。隱私等級標記可用來評估數據開放帶來的隱私泄露風險，等級越高，表示隱私泄露的風險越大。

圖1 隱私泄露風險評估系統

數據開放者通過接口上傳原始數據和隱私等級標記，系統進行隱私泄露風險等級評估后也將通過接口層將評估結果反饋給數據開放者，為其確定數據開放策略提供參考。數據使用者通過接口聲明自己的使用需求，包含需要使用的字段和對該字段進行的操作。

隱私泄露評估系統負責進行隱私泄露評估，在獲取數據開放者設定的隱私等級標記和數據使用者提出的使用需求后，利用評估算法進行隱私泄露的風險評估。

2.3 問題定義

數據開放過程中的隱私泄露評估問題，需要從數據開放者和數據擁有者兩個角度來綜合考慮，因此本文基于下述兩個前提假設。

首先，假設數據開放者對自己上傳的數據集有較為明確的隱私保護需求，即知道數據集中哪些字段是隱私保護等級較高或是哪些字段關聯后隱私保護等級較高。

這就是數據開放者的隱私等級標記，隱私等級標記可用來評估數據開放帶來的隱私風險，等級越高，表示數據開放的隱私風險越大。字段間關聯關系的標記被稱為關聯字段規則，用來表示當兩個或多個字段被同時使用時帶來的隱私風險，通常比單字段隱私等級更高。本文參考BNF范式的格式，定義數據開放者的標記語言如下：

定義1數據開放者的標記語言，是指數據開放者用來標記開放數據集內各字段以及操作隱私等級的語言，描述如下：

<數據開放者標記>::=(<對象>，<隱私等級>)

<對象>::=<字段>|<操作>

<字段>::=<單字段>|<多字段集合>

<隱私等級>::=1|2|…|N

這里，數據開放者的標記包含兩大類，其一是字段隱私等級標記，又包括兩類，一是單字段隱私等級，即單個字段的隱私等級；二是關聯字段規則。關聯字段規則的形式化定義如下：

定義2關聯字段隱私等級，表示兩個或多個字段關聯情況下的字段隱私等級，一般格式為：

r={f1,f2,…,fs,level}，其中s≥2

上式表示當兩個或多個字段f1,f2,…,fs同時出現在同一使用需求中時，這些字段的隱私等級將變為level，因為當兩個或多個字段關聯時，會暴露除單字段本身外更多的信息，因此level的值都大于或等于(通常是大于)單字段隱私等級。

數據開放者標記的第二類是操作隱私等級標記，用來標記不同操作的隱私等級，這一類標記有時也可以使用事先設定好的缺省值。

下面說明第一類字段隱私等級標記。假設某醫院數據集有姓名、年齡、性別、診斷結果四個字段，醫院對這一數據集進行了字段隱私等級標記，如表1所示(這里N=5)，其中最后一條為關聯字段規則。使用本文的數據開放標記語言可以形式化描述如下：

字段標記1：(姓名，4)；

字段標記2：(年齡，3)；

字段標記3：(性別，1)；

字段標記4：(診斷結果，4)；

字段標記5：({姓名，診斷結果}，5)。

表1 某醫院數據集字段隱私等級標記

下面說明第二類操作隱私等級標記。假設某醫院數據集支持的操作有取值、求和、計數、求最值，醫院對這些操作進行了隱私等級標記，如表2所示(這里N=3)。使用本文的數據開放者標記語言可以形式化描述如下：

操作標記1：(取值，3)；

操作標記2：(求和，2)；

操作標記3：(計數，1)；

操作標記4：(求最值，2)。

表2 某醫院數據集操作隱私等級標記

以上，是對數據開放者標記的定義。

其次，假設數據使用者有明確的使用需求，即能夠描述對需要的數據集內每個字段進行什么操作。

數據使用者的使用需求語言定義如下：

定義3數據使用者的使用需求語言，是指數據使用者用來描述具體使用需求的語言，描述如下：

<使用需求>::=<需求元組>|<需求元組列表>

<需求元組>::=(字段，操作集合)

下面結合表1和表2，說明這一使用需求描述語言。假設醫院在開放如表1、表2所示的一個數據集后，一位數據使用者提出了這樣的使用需求：需要對年齡進行求和、計數和求最值的操作，需要對性別和診斷結果進行取值操作。可以形式化地描述這個使用需求如下：

需求元組1：(年齡，{求和，計數，求最值})；

需求元組2：(性別，{取值})；

需求元組3：(診斷結果，{取值})。

以上是對數據使用需求描述的定義。在此基礎上，可以形式化地描述數據開放過程中的隱私泄露評估：

所謂隱私泄露評估，就是給定數據開放者標記集合R和數據使用者需求集合U，求隱私泄露評估等級l=f(R,U)，其中映射f就是隱私泄露評估的過程。

隱私泄露評估就是綜合考慮數據開放者進行的隱私等級標記和數據使用者提出的使用需求，對此次數據開放進行評估后得出隱私泄露風險等級，并反饋給數據開放者的過程。

例如，某醫院作為數據擁有者，考慮開放一個數據集，其中包含患者ID、性別、年齡、病癥和治療方案等若干字段。作為數據擁有者，醫院認為患者ID、治療方案都是隱私保護等級較高的字段，而患者ID和病癥關聯后，二者的隱私保護等級還會更高。某科研機構作為數據使用者，希望研究某種疾病與性別和年齡的相關性，那么就需要對性別、年齡和病癥三個字段進行取值、計數等操作。將這些信息作為輸入參數進行隱私泄露評估后得到一個隱私泄露風險等級，并將這個等級反饋給醫院，為其制定相應的數據開放策略提供參考。

3 基于矩陣計算的隱私泄露評估方法

3.1 評估方法

在數據開放的時代背景下，大量數據擁有者希望開放共享自己擁有的數據，供數據科學研究者進行研究。但數據開放帶來的隱私泄露風險，是困擾數據擁有者的重要問題。因此本文基于前述提到的數據開放中的隱私泄露評估思想，提出一種數據開放模式下的隱私泄露評估方法，以評估數據開放過程中可能帶來的隱私泄露風險等級，供數據開放者參考，進而制定相應的數據開放策略。

下面對評估方法進行具體說明：

(1) 評估方法的輸入包含四個部分，首先對數據開放過程中所支持的m種操作的隱私等級進行預標記(例如，1-3級，隱私等級依次提高)，記為o1,o2,…,om；其次數據開放者對擬開放的n個數據字段進行隱私等級標記(例如，1-5級，隱私保護需求依次升高)，記為f1,f2,…,fn，如不進行標記則可以使用設定的缺省值，數據開放者同時會提出關聯字段規則集合R；數據使用者針對開放數據提出使用需求集合U。

(2) 建立一個m×n的矩陣A，并均以最低的隱私等級(例如，1)填充。

(3) 遍歷使用需求集合U中的每一個使用請求u，以操作為行，字段為列，若使用需求中涉及第i種操作和第j個字段，則在矩陣第i行第j列的位置存放oi×fj的值(即aij=oi×fj)，其中若某些字段觸發了關聯字段規則集合R中的某一條r，則將會以關聯字段規則下的隱私等級替換原始的單字段隱私等級。例如，姓名和診斷結果單字段隱私等級均為4級，而二者關聯后隱私等級為5級，若在使用需求中同時用到這兩個字段時，則將這兩個字段的隱私等級均設為5級。

3.2 正確性證明

評估方法的正確性主要由以下三個定理證明：

定理1在字段隱私等級、操作隱私等級相同，針對字段進行的操作數目相同的情況下，使用者兩次使用請求要求使用的字段數目分別為t1和t2，若t2>t1，則p2>p1。

證明：由數據使用需求定義，使用者要求使用的字段越多，矩陣中就有更多元素由1替換為較大值，由隱私泄露風險等級系數的計算公式p=(asum-amin)/(amax-amin)可知，asum2>asum1，而amin和amax不變，因此p2>p1。

證畢。

定理2在字段隱私等級、操作隱私等級相同，要求使用字段數目相同的情況下，使用者兩次使用請求要求對字段進行的操作數目分別為st1和st2，若st2>st1，則p2>p1。

證明：證明過程類似定理1。

以上兩個定理描述的是只考慮單字段的情況下評估算法的正確性，下述定理考慮關聯字段規則下評估算法的正確性。

定理3在其他條件相同的情況下，加入關聯字段規則集合R，且使用請求觸發關聯字段規則時，新的隱私泄露風險等級系數大于或等于原隱私泄露風險等級系數。

證明：因為前文提到的關聯字段規則中提出，關聯字段規則涉及到的字段隱私等級會提高，加入越多的關聯字段規則會使得隱私泄露風險等級系數越高，因此不失一般性，考慮加入兩個字段的關聯字段規則時，隱私泄露風險等級的變化情況。

證畢。

以上證明了該評估方法的正確性，能夠根據隱私等級標記和使用者的使用需求，對數據開放的隱私泄露風險進行有效評估。

4 實驗分析

為了驗證方法的運行效率和正確性，本文進行了一系列實驗。實驗中我們給定操作隱私等級(見表2)、字段隱私等級和關聯字段規則集合，通過改變使用需求集合，根據上文提出的算法構造不同的矩陣，計算相應的隱私泄露風險等級系數來驗證評估方法的正確性。

實驗采用UCI數據集Adult作為實驗數據集[12]，選取了其中“年齡(1)”“受教育時間(3)”“資本收益(4)”“資本損失(4)”“每周工作小時數(2)”“fnlwgt(5)”總計6個數值型字段進行實驗，括號中為設定的字段隱私等級。

實驗環境如下：CPU配置為Intel(R) Core(TM) i5- 4590 @ 3.30 GHz，內存8 GB，該計算機運行Windows 10操作系統，所有算法和實驗程序由Python語言開發實現。

4.1 運行效率

由于在實際運用中，相比數據集的字段數目，通常考慮支持的操作數目數量級較小，因此在測試算法運行效率時，不考慮使用需求中涉及到的操作數目，而將其作為常數，考慮涉及到的字段數目對算法運行效率的影響。

在實驗過程中發現算法運行時間與字段數基本呈線性正相關，算法在Adult數據集上運行時間很短，而在我們人工合成的包含100個字段的數據集上，算法運行時間也不到1毫秒，實際運用中，數據集的字段數通常達不到100個，因此該算法具有較高的運行效率。

4.2 正確性

首先對定理1進行驗證，考慮在字段隱私等級、操作隱私等級相同，針對字段進行的操作數目相同的情況下，使用請求要求使用的字段數目越多，則隱私泄露風險等級系數應該越高。實驗采用的Adult數據集總字段數為6，只改變每次請求要求使用的字段數目，要求對使用字段進行的操作均為“取值”和“計數”(支持操作還包含“求和”、“求最值”，詳見表2)，計算隱私泄露風險等級系數。實驗結果如圖2所示。

圖2 請求字段數

圖2表明，在字段隱私等級、操作隱私等級相同，使用請求要求對字段進行的操作數目相同的情況下，隨著要求使用字段數目的增多，隱私泄露風險等級系數也在不斷提高。

下面對定理2進行驗證。考慮在字段隱私等級、操作隱私等級相同，要求使用字段數目相同的情況下，使用請求要求對字段進行的操作數目越多，隱私泄露風險等級系數應該越高。實驗依然采用總字段數為6個的Adult數據集，且固定請求使用其中的4個字段(“受教育時間”，“資本收益”，“資本損失”，“每周工作小時數”)，從支持操作集合{“取值”，“求和”，“計數”，“求最值”}中依次選取包含不同個數的操作子集作為操作使用請求，計算隱私泄露風險等級系數，實驗結果如圖3所示。

圖3 請求操作數

圖3表明，在字段隱私等級、操作隱私等級相同，要求使用字段數目相同的情況下，隨著使用請求要求對字段進行的操作數目增多，隱私泄露風險等級系數在不斷提高。

下面對定理3進行驗證。考慮在其他條件相同的情況下，加入關聯字段規則集合R，且使用請求觸發關聯字段規則時，應當會使隱私泄露風險等級系數提高。實驗采用若干字段數不同的數據集，且假設數據使用者請求使用所有字段，對每個字段進行的操作固定且一致。然后隨機生成一系列的關聯字段規則，構成不同的關聯字段規則集合，因為使用者請求使用全部字段，因此所有規則會被觸發。此外，由于原始數據集中單字段隱私等級為隨機生成的，為了保證關聯字段規則中隱私等級比單字段隱私等級高，將關聯字段規則中的隱私等級全部設為最高級，實際應用場景中通常會要求數據開放者在進行標記時保證關聯字段規則中隱私等級不低于單字段隱私等級。最后，計算關聯字段規則觸發下的隱私泄露風險等級系數，結果如圖4所示。

圖4 關聯字段規則

圖4表明，在其他條件相同的情況下，加入關聯字段規則集合R，且使用請求觸發關聯字段規則時，隱私泄露風險等級系數均有不同程度的提高。

綜合而言，本文提出的隱私泄露評估方法的效率和正確性驗證結果均符合預期。

5 結 語

本文結合當前數據開放的需要，提出了一種基于矩陣計算的數據開放隱私泄露評估方法。該方法綜合考慮開放數據集中單字段和關聯字段的隱私等級所涉及操作的隱私等級以及數據使用者的使用需求，采用矩陣計算的方法，對數據開放的隱私泄露風險進行評估，為數據擁有者決定是否開放數據以及開放形式提供參考，為數據開放提供了有力保障。

在今后的研究中，我們將會對數據使用需求描述語言繼續進行擴展，以支持更為復雜的數據使用需求描述，進一步提高評估結果的精細化程度。