[發明專利]數據發布環境下面向結構化數據的隱私衡量算法

在審

• 申請號: 202110738805.6
• 申請日: 2021-06-30
• 公開（公告）號: CN113378229A
• 公開（公告）日: 2021-09-10
• 發明（設計）人: 陳振宇;姚琳;吳國偉;閆鴻淼
• 申請（專利權）人: 大連理工大學
• 主分類號: G06F21/62
• 分類號: G06F21/62;G06F16/906
• 代理公司: 大連理工大學專利中心 21200
• 代理人: 溫福雪

1.一種數據發布環境下面向結構化數據的隱私衡量算法，其特征在于，步驟如下：

(1)首先數據源生成本地數據所涉及用戶的摘要，并獲取具有相似摘要已發布數據集，并與這些數據集進行屬性集合配對，然后對配對數目進行分類，以便分離數據源私有屬性；

數據集的時空屬性摘要生成與集合配對、分離私有屬性的具體過程如下：

(1.1)當數據源對某一特定用戶群體收集其相關信息時，數據源需生成統一格式的用戶摘要，摘要中的信息僅描述該數據集是哪一地區用戶收集的，又因其具有時效性，稱為時空摘要；首先定義數據集的組成如下：

D_S＝{I₁,I₂,...,I_i...,I_n}

D_s為數據源S所收集的待發布數據庫，I_i為數據庫中收集的有關用戶i的記錄，n為D_s中的記錄數目，每條記錄的組成如下：

I_i＝{Attr_i1,Attr_i2,...,Attr_ij...,Attr_im}

其中，Attr_ij為用戶i的第j個屬性的取值，而m＝|I_i|為用戶i的屬性個數，對于結構化數據集來說，任意記錄的屬性個數總是相同的，即m＝|I₁|＝|I₂|＝…＝|I_i|＝…＝|I_n|，類似的，把Attr_j定義為數據集中的第j個屬性，有n＝|Attr₁|＝|Attr₂|＝…＝|Attr_j|＝…＝|Attr_m|；其中，相同索引的屬性類型一致，即存在一個語義取值集合S_j，任意元素x,y∈S_j，x與y在語義上屬于相同類別，若有Attr_ij∈D_s，必然有Attr_ij∈S_j；

對于數據集D_s，其時空摘要定義如下：

Abstract(I_i)為用戶i所在的行政區，Abstract(D_s)則為一個行政區的集合，該集合覆蓋了數據集D_s中所有用戶的行政區；

(1.2)生成完數據集的摘要后，數據源向外搜索已發布數據集；如果已發布數據集的摘要與數據源的摘要具有超過閾值的重疊，則被用來與待發布數據集進行集合匹配，計算摘要重疊和集合匹配的過程如下：

對于一系列已經發布的數據集D₁,D₂,......,D_l，以及這些數據集的摘要Abstarct(D₁),Abstract(D₂,)......,Abstract(D_l)，計算如下值：

α_i為待發布數據集D_s的摘要和已發布數據集D_i的摘要相似度，其內在含義即為行政區重復的比例，當該比例α_i小于預設的閾值時，這類數據集被用作背景知識發動隱私攻擊造成實質性的隱私泄露的可能性較小，會被篩去；在篩除這部分數據之后，將剩余的已發布數據集進行合并，并依托該數據集分離待發布數據集的私有屬性和非私有屬性；首先定義合并后的數據集如下：

δ為預設的閾值，通過將所有未被篩除的數據集進行垂直上的合并，構成了合并數據集D_Union，為了使D_Union符合數據集的定義，首先讓不同記錄的屬性名稱進行比較，將相同類型的數據調整為同一屬性，并重排索引，在此過程中可能會出現某些記錄擁有的屬性而別的記錄沒有，僅需將未擁有該屬性的記錄添加相關屬性，但對屬性取值填為空即可，從而保證D_Union已經符合一個結構化數據集的定義；對于數據集D_Union和待發布數據集D_s，計算每一屬性Attr_j相似度如下：

隨后，通過對計算出來的β_j進行分類，根據分類結果將D_s中的屬性分為私有屬性和非私有屬性，分類的方法采用最小二乘法；由于是對一維數據進行分類，首先設擬合的點為p，定義誤差平方和如下：

通過求解該誤差函數的最小值，即獲得對相似度β_j的最小點擬合，以該點作為閾值，取其中大于閾值的相關數據為非私有屬性，而小于閾值的相關數據為私有屬性；求解最小值的方法為對誤差函數求對點p的駐點，由于該函數是開口向上的二次函數，駐點即為最小值點，求解得：

從而將D_s中的屬性分為兩類如下：

對于待發布數據集中取值和已發布數據集大部分重復的屬性，認為其中已經有大量的知識被獲取，足夠用于作為發動隱私攻擊的背景知識，在這里體現的即為滿足β_j≥b的屬性，而對于滿足β_jb的屬性，其取值和已發布數據集中取值重疊較少，認為其他發布的數據集缺少這部分的相關知識，歸類為私有屬性，重點保護；

(2)對私有屬性應用信息熵進行定價，將私有屬性分為敏感屬性和非敏感屬性，對剩余的非敏感屬性和非私有屬性應用最大熵原理提取其中的關鍵準標識符；具體過程如下：

(2.1)對私有屬性的定價主要從三個方面來考慮：對于內部數據的定價、對于外部數據的定價以及分布定價；為方便應用信息熵并幫助表達，首先對私有屬性的內部概率進行定義：

其中，|Attr_ij|表示數據集D_s中取值為Attr_ij的個數，實際中的概率對于人們來說難以獲知，因此將D_s中Attr_ij的頻率作為概率的近似估計，當D_s中數據越多時，根據大數定律，該結果趨近于真實概率；

通過引入該內部概率，計算某一私有屬性的信息熵如下：

若外界數據分布與該數據集分布一致，利用該熵值直接對私有屬性定價，以表示從該數據集獲取一條數據的平均信息量；在考慮的場景中，外界數據與本地數據集的分布不一致，因此還需要對私有屬性考慮外部數據場景，以明確外部定價；首先定義數據外部分布的概率：

其中，N表示待發布數據集和已發布數據的總記錄數，計算其平均信息量如下：

最后，定義該部分數據的分布概率如下：

其中，C(n,|Attr_ij|)為組合數，代表某一私有屬性Attr_j在結合了外部數據分布的情形下，其在數據集中出現的概率，計算其信息量如下：

I_d(Attr_j)＝-log(Probability_d(Attr_j))

根據以上三個過程計算出的信息量或熵值，將私有屬性定價如下：

其中，a是衰減因子，而c是一個與需求有關的常數，γ是用戶調節分布定價和外部定價比例的常數，e是自然對數的底；同時，我們引入了t代表時間，私有屬性的定價會隨著時間的不同而發生變化；通過將時間跨度定在[0，1]之間，代表發布數據的有效期，并在有效期內對數據定價進行采樣，形成每一私有屬性的多維定價組，從而根據其對私有屬性進行分類；當采樣次數為k時，將私有屬性Attr_j的多維定價組表示如下：

Price_sequence(Attr_j)＝[ξ_j1，...，ξ_ji，...ξ_jk]s.t.1≤i≤k

同時，取前k-1項，將其記為Y_j＝[ξ_j1，...，ξ_ji，...ξ_j(k-1)]；

(2.2)在對私有屬性進行準確定價后，應用最小二乘法對定價后的私有屬性進行分類，分為高價類和低價類，并將高價類作為敏感屬性，而低價類作為非敏感屬性；隨即應用最大熵原理提取準標識符，完成對數據中風險要素的識別；對各個私有屬性的多維定價組，設擬合超平面為：

ζ_k＝ζ₁x₁+…+ζ_ix_i+…+ζ_k-1x_k-1＝XZ s.t.1≤i≤k

定義誤差平方和函數如下：

對該誤差平方和函數求最值，解得：

由此，將私有屬性分類如下：

(2.3)然后，應用最大熵原理提取數據中的準標識符，在數據集中，準標識符會起到區分記錄的作用，而攻擊者也常常利用準標識符作為背景知識發動隱私攻擊，因此對于準標識符的準確提取意味著對于攻擊者背景知識的精準估量，對于后續的隱私保護工作具有重要意義；計算剩余屬性的熵如下：

然后，對計算出來的屬性按照熵值排序，以具有最大熵值的屬性Attr_j為基，記其為Base，計算其與其他剩余屬性的聯合熵如下：

其中，Probability(Attr_ij,Attr_ik)為對應取值Attr_ij和Attr_ik的聯合概率；選取與屬性Attr_j聯合熵最大的屬性Attr_k，構成一組新的基Attr_j，Attr_k更新Base，并計算基與其他剩余屬性的聯合熵如下：

其中，Base_i是用戶i對應Base屬性的取值組合，而Probability(Base_i,Attr_il)即為Base_i與Attr_il的聯合概率；重復上述步驟，并對基進行更新，直到基的熵為內部數據的最大熵終止，便尋找到一個最短準標識符組合作為基，其取值可唯一區分數據集中的任意記錄，顯然，攻擊者的背景知識達到基的長度時，數據中的所有信息都會泄露；因此，對于隱私衡量來說，考慮攻擊者的最大背景知識長度為基的長度即可；

(3)構造一個隱私模型用于描述數據分布對于數據隱私的影響以及對隱私攻擊的抵御能力，并給出了一個隱私安全標準用于判斷數據集中的哪部分數據被重點保護；

(3.1)在討論數據隱私時，往往作如下考慮，在基于推斷的攻擊下，若確切信息泄露的可能性越低，則認為數據隱私越好；因此，將隱私模型定義如下：

p(unknow|know)≤η

該式定義了已知信息作為背景知識推斷數據中未知信息的概率上界，若對于數據集中外界確切的已知和未知信息，用已知信息推斷準確未知信息的概率小于等于η，則稱數據滿足η隱私模型；若存在算法對數據集進行操作使其滿足η隱私模型，則稱該算法滿足η推斷隱私；

如前所述，考慮的是數據發布場景中最普遍的情形，即準標識符充當數據集中的背景知識用于推斷其他信息，任意準標識符都有可能充當背景知識，因此，在該隱私模型中，已知信息便是準標識符，相應的，未知信息是敏感屬性，對于非敏感屬性，并不將其作為需要推知的未知信息，因為其包含的內容不具有一定的信息量，不被稱作為隱私數據；

(3.2)接著，尋找致使數據不滿足η隱私的準標識符或準標識符的組合，將這些準標識符加入威脅集合中，同時，將能被推斷出的信息加入風險集合中，在尋找過程中的背景知識長度小于等于|Base|，其中|Base|是Base的長度；

對于已知信息的推斷采取鏈接操作，即以某一準標識符組合鏈接數據集，獲取匹配和不匹配的記錄，然后將已知信息從這些記錄中移除，剩余的信息即為鏈接得到的信息，隨后應用隱私模型判斷該部分是否滿足η隱私；

在前面提取關鍵準標識符的過程中，發現一個Base，其在數據集中唯一得區分一條記錄，除非當η大于等于1，否則應用該組關鍵準標識符作為背景知識，必然不會有滿足η推斷隱私的算法；因此，當不斷增長背景知識到|Base|時，必然會出現某些準標識符的組合使得數據不滿足η隱私，即上述過程收斂；

(3.3)構建背景知識推斷圖，將威脅集合中的每一個元素都映射成為圖上的一個點，對于構成父子序列的準標識符序列，為對應的點填上一條邊，最后構成一個|Base|部圖；

通過調整該|Base|部圖中節點的排列順序，將其表示為一個分層的結構，每一層父序列在上，而子序列在下，顯然最高層的序列即為引起數據不滿足η推斷隱私的關鍵因素，攻擊者應用圖中任意節點作為背景知識均能引起超過η的隱私泄露，而對于這一問題考慮背景知識分離的方法以提高數據的隱私性；

(3.4)背景知識分離的主要目的在于將任意背景知識限制在|Base|部圖中最高層節點的父序列中，從而確保數據滿足η隱私；背景知識分離的過程中，采用計算節點相似度的方式來規劃背景知識分離的路徑，從而找到一種只需進行最少操作劃分的方法，最大的保持數據的可用性。