0 引言

随着信息化和网络化进程的加快,互联网的普及越来越深入，以数据发布的查询统计为主要应用的需求也日益增多,如何保证这些应用中数据隐私的安全性,成为了当前需要解决的问题。

在现有的云环境中,常见的隐私保护方法中数据匿名化方法^[1]研究较多,例如,通过元组泛化、抑制等数据处理的K系列匿名方案，以用户标识和属性特征、度、边增删扰动操作实现的匿名方案，通过实现数据的匿名化以确保在数据泄露的情况下隐私不被披露。因此为保证数据集发布的安全,可以根据环境的特殊性对数据集进行匿名化封装,当然这些都需要特殊的攻击假设和背景知识。但是，一旦这些攻击假设和背景知识被攻击者所拥有,这些数据很有可能在匿名化的过程中就会遭遇数据隐私的泄露。需要考虑如何保证这种情况下数据的安全性。其中数据集隐私泄露为数据匿名前的隐私泄露,过程隐私泄露为数据匿名化过程中遭遇的隐私泄露。目前,现有的安全隐私技术中不需要这种背景知识也可以保证数据安全的是差分隐私保护技术^[2-5]，即基于数据失真的隐私保护技术,该技术采用添加噪声机制使敏感数据失真但同时保证数据的有用性。它可以实现在数据集中添加或删除一条数据而不影响查询输出结果,因此可以保证这一条记录被识别或者敏感属性被泄漏的情况下结果的安全性；但是当前的差分隐私方法并没有考虑到数据之间的联系,因此无法有效地处理这类数据集。例如在社交网络数据中,每个用户都会和许多其他用户产生联系,因此即便从数据集中删除某个用户,仍可能从其他用户的联系中推断出该用户的信息。若同时考虑数据之间的联系,则查询敏感度会很高,从而引入过多的噪声。

为了改变数据在匿名化过程中出现的隐私泄露和只采用差分隐私导致数据失去语义的现状,本文提出一种基于差分隐私的数据匿名化隐私保护模型,在数据匿名化的过程中引入差分隐私概念,保障了数据的安全性和可用性,提高了数据处理的安全效率。

1 相关工作 1.1 差分隐私

差分隐私^[6-8]是一种通用且具有坚实的数学理论支持的隐私保护框架,可以在攻击者掌握任意背景知识的情况下对发布数据提供隐私保护。

定义1 差分隐私。设有随机算法M,P_M为M所有可能的输出构成的集合,对于任意两个相邻最多相差一条记录的近数据集D和D′即DΔD′≤1,以及P_M的任何子集S_M,若算法M满足下列不等式则称算法M提供ε-差分隐私保护;

${{P}_{r}}\left[ M\left( D \right)\in {{S}_{M}} \right]\le \exp \left( \varepsilon \right)\times {{P}_{r}}\left[ M\left( {{D}^{'}} \right)\in {{S}_{M}} \right]$

(1)

其中:P_r[·]由算法M随机控制,表示隐私披露的风险;参数ε称为隐私保护预算,用来控制算法M在两个邻近数据集上获得相同输出的概率的比值,反映M所能够提供的隐私保护水平。

要实现差分隐私保护需要噪声机制的介入,本文选用的噪声机制为拉普拉斯(Laplace)机制。该机制通过向确切的查询结果中加入服从Laplace分布的随机噪声来实现ε-差分隐私保护,记位置参数为0,尺度参数为b的Laplace分布为Lap(b),其密度函数为:

$p\left( x \right)=b/2\exp \left( -\left| x \right|/b \right)$

(2)

定义2 Laplace机制。给定数据集D,设有函数f:D→R^d,其敏感度为Δf,那么随机算法M(D)= f[D]+Y提供ε-差分隐私保护,其中Y~Lap(Δf/ε)为随机噪声,服从尺度参数为Δf/ε的Laplace分布。

1.2 匿名化

数据匿名化^[9-11]是将数据集经过一定的变换之后,生成一种在一定范围内无差别的新数据集然后进行发布,使得攻击者无法根据发布出来的新数据集推导出某个个体是否具有敏感信息,从而实现对数据的隐私保护。如图 1所示。

对于数据匿名化主要从三个层面进行匿名保护:实体对象隐私、实体对象与实体对象之间的关联关系隐私、实体属性隐私。实体对象是指网络环境中虚拟节点所对应的主体信息,如社交网络中真实身份信息;关联关系是指实体与实体之间的联系和以实体为中心的关系网络边,如社交网络中朋友圈信息;实体属性是指实体的个性化信息,如个人爱好、习惯等。本文主要从实体属性隐私保护方面进行匿名化。

目前匿名化方案主要有泛化/隐匿技术和基于微聚集匿名化技术两种,其中泛化/隐匿技术是基于数据匿名化的一种典型技术,但存在的问题是不区分数值型数据与分类型数据,使得数据泛化后丢失了更多其数据的语义;其次是泛化的计算复杂度非常高。另外在处理大数据集的时候,尤其是属性比较多的大数据集时,泛化带来大量的数据信息的丢失也相当严重,被称为维度灾难^[12];当在高维空间进行泛化时候,因为数据集维度造成泛化值具有比较大的区间。因此从两方面造成数据的丢失都是非常可观的,这种情况下发布的数据集虽然保证了数据的安全性,但数据集的可用性丢失殆尽。

为了弥补泛化/隐匿技术的缺陷,本文提出将微聚集^[13]技术引入到数据匿名化中。微聚集技术早先是微观数据统计披露控制技术,将其引入到数据匿名化的主要思想是通过微聚集技术将原始数据集分成若干个类,每个类包含至少k个元组,使得每个类内的数据最大限度地相似,类与类之间的数据最大限度地不同,然后用类的质心替代类内所有元组,实现数据集的k-匿名化。

1.3 微聚集

微聚集分为k-划分和聚集两部分,k-划分实现类内同质性尽可能大,类间同质性尽可能小,类内同质性的测度则由相应的衡量标准来决定,本文采用的测度计算方法是相异度矩阵。以下是关于k-划分和聚集的两部分定义。

首先将数据集的各个属性根据不同的特性用一个四元组表示:{显示标识符,准标识符,敏感属性,非敏感属性}。显示标识符(ExplicitIdentifier)指可直接准确(或唯一)识别数据个体信息的属性,如姓名等属性;准标识符(QuasiIdentifier)指同时存在于这个数据表和其他外表中,攻击者可以通过链接攻击获取个体信息的属性,如生日等属性;敏感属性(SensitiveAttributes)指包含了丰富的敏感信息,需要进行保护的属性,如病史等属性;非敏感属性(Non-Sensitive Attributes)指虽不需要进行保护,但是与其他准标识符组合后仍有可能被攻击的属性。

定义3 k-划分。给定数据表T,Ql是T的准标识符,Ql包含p个属性,将数据表T基于Ql划分g个类,n_i为第i个类的元组数,要求对∀i,n_i≥k,且$n=\sum\limits_{i=1}^{g}{{{n}_{i}}}$,则称该划分为数据表T基于Ql的k-划分。其中，k-最优划分等价类的大小应在[k,2k]。

定义4 聚集。给定数据表T,Ql是T的准标识符,基于Ql的一个k-划分为g个类,设c_i为第i个类元组类质心,对所有i,则称用c_i取代所在类的所有元素的操作为聚集。

定义5 相异度矩阵。相异度矩阵存储n个对象两两之间的相似性,表现形式是一个n×n维的矩阵。d(j,i)是对象i和j之间相异性的量化表示,通常为非负值,两个对象越相似或“接近”,其值越接近0;越不同,其值越大,且d(i,j)=d(j,i),d(i,i)=0。其中d值引用欧氏距离公式进行运算:

$d\left( X,Y \right)={{\left( \sum\limits_{i=1}^{n}{{{\left( {{X}_{\text{i}}}-{{Y}_{i}} \right)}^{2}}} \right)}^{1/2}}$

(3)

其中:X_i、Y_i为X、Y向量第i个属性。

2 基于差分隐私的数据匿名化隐私保护算法 2.1 隐私保护模型

本文针对数据集隐私泄漏和过程隐私泄漏两方面提出了基于差分隐私的数据匿名化隐私保护模型,该模型的框架如图 2所示。

原始数据集(以数值型数据集为主要研究对象,也可面向其他数据类型,但本文不作额外处理)通过微聚集匿名化技术进行隐私保护,同时对整个微聚集匿名化过程进行差分隐私的保护得到最终的净化集,由此得到的数据集发布后,用以查询等操作。该框架的主体是对数据集的匿名化保护,其次是对整个微聚集匿名化过程进行差分隐私的保护。

基于微聚集匿名化保护的步骤是:对原始数据集T进行k-划分,将数据集划分成了若干个等价类,然后对每一个等价类进行聚集操作,计算出类质心并用类质心替代类内的其他值,将这些变化后的数据组合形成新的数据集匿名表。

计算类质心的过程势必导致隐私的泄漏即生成的匿名表不能抵制同质性攻击和背景知识的攻击,利用差分隐私进行控制,利用合适的噪声机制进行添噪处理,从而保证数据在匿名化过程中的安全性。

2.2 隐私保护方法

根据上文提出的基于差分隐私的匿名化隐私保护模型,针对上述的数据集隐私泄漏和过程隐私泄漏两方面设计解决思路:首先利用MDAV(Maximum Distance to Average Vector)算法对数据集进行微聚集k-划分,即通过一个相异度矩阵来表示数据集内各个元组之间的距离,用数据集的众值替代数据集的中心点,从离整个数据集中心点最远的地方开始对数据集进行划分,每K个元组组成一个等价类,定位等价类中心取代类内敏感属性值,在定位类中心的过程中会导致隐私的泄漏,所以采用差分隐私技术进行添噪处理(选用Laplace噪声机制)保护,应用子线性查询统计(Sub-linear Queries，SuLQ)框架^[14]设计基于差分隐私的微聚集算法。方法流程如图 3示,其中虚线部分为本文工作重点。

2.3 算法设计与实现

在定位每一个等价类的质心过程中会导致隐私的泄露即生成的匿名表不能抵制同质性攻击和背景知识的攻击,因此本文基于一个SuLQ框架设计差分隐私的微聚集匿名化算法,使得该过程满足差分隐私。

SuLQ框架:令N(0,R)为一个满足期望值为0,方差为R=R(ε,δ,T)的正态分布的随机数,SuLQ应用算法A(R)的输入为一个查询 (g:D→[0,1],S⊆[n]),输出为$\sum\limits_{i\in S}{g\left( {{d}_{i}} \right)}+N\left( 0,R \right)$。将所有通过MDAV基础算法划分的等价类添加随机噪声,形成S₁,S₂,…,S_k,k个等价类集合。

SuLQ基于隐私保护的MDAV算法(x₁,x₂,…,x_k):首先,对于1≤j≤k,计算集合S_j中所有含元组数目的近似值n_j;其次,对于1≤j≤k,计算集合S_j中所有元组值之和的近似值s_j;最后,对于1≤j≤k,计算所有等价类质心x_j=s_j/n_j,其中本文采用均值运算法计算等价类的质心。

如果等价类的所有元组数远远超过R^1/2,则n_j=|S_j|是一个好的估计值,而x_j也是无隐私保护方法下x_j的一个精确估计。所以,对于1≤j≤k,如果|S_j|[gg ]R^1/2,则在一个很高的概率下‖x_j-x_j‖是O((‖x_j‖+d^1/2)R^1/2/|S_j|)的。

因此ε-MDAV算法继承了MDAV算法的高效性,增加了差分隐私的保护,使得得到的匿名表安全性更强,基于差分隐私的ε-MDAV算法步骤如下:

输入 原始数据集T。

输出 获取ε保护的匿名数据集T′。

步骤1 计算类内同质性测度相异度矩阵A,元组数为n,见式(3)。

步骤2 根据相异度矩阵计算数据集的中心a,找到距离最远的点r,r为max{d(a,b)}中b点,再找到距离r最远的点s,s为max{d(b,c)}中c点。

步骤3 以r为中心选择距离r最近的k-1个点组成一个等价类;以t为中心选择距离s最近的k-1个点组成一个等价类。

步骤4

if n>2k then

 返回步骤1

  else if k ＜n＜2k then

   自成一类

   else

    归入最近的类

步骤5 聚集操作:

1) 根据计算的中心点将样本划分为带有噪声的等价类 S′₁,S′₂,…,S′_k,k个等价类集合。

2) 对于1≤j≤k,计算集合S′_j内元组值之和$sum=\sum\limits_{i\in {{S}_{j}}}{{{x}_{i}}}$和数目num=S_j,分别添加噪声得到 sum′和num′,更新等价类的质心值:x′_j=sum′/num′。

步骤6 计算出类质心代替其他值。

$\overline{X}\text{=}\frac{1}{n}\sum\limits_{i=1}^{n}{{{X}_{i}}}$

其中：设 X_i为等价类内n个元组中第i个元组,则类内质心用 X表示。

步骤7 返回 T′。

2.4 算法分析 2.4.1 时间分析

设数据集T的记录总数为n,ε-MDAV算法步骤1计算相异度矩阵时间花费为O(n²),步骤2~4需要的时间花费为O(n²/k),步骤5对数据进行加噪处理时间花费为O(n²/k),步骤6替换操作时间可忽略不计,因此该算法总的时间复杂度为O(n²)+O(n²/k)+O(n²/k)=O(n²)。原基础算法MDAV时间复杂度为O(n²),因此ε-MDAV算法在增加安全性的同时并没有额外增加时间的开销。

2.4.2 可用性分析

ε-MDAV主要通过将数据划分为若干个类组实现的,在每一个类组内所属记录是均匀一致的,但是类组之间记录是异构的,该特征使得信息丢失率很低;通过差分隐私对其提供严格可靠的隐私保护,虽然增加了部分噪声但是得到的数据集类质心偏移不大,使得等价类的信息损失率也很低,对总体的数据集而言可用性依旧很高。

2.4.3 安全分析

设D₁和D₂为互相之间只相差一条记录的两个数据集，查询空间维度即数据集维度为d：

1) 为了计算查询敏感度的方便，分析中利用直方图法为此次保护提供响应,由于num′的Δf=1,那么sum′的Δf最大为d;

2) 由1)可得，在d维数据集中添加或删除一条记录,对于每一维的和来讲,其敏感度为1,对于整个查询序列而言,其敏感度为维度+1，即d+1;

3) 由2)可知，设[M(D₁)]和[M(D₂)]分别为D₁和D₂添加噪声之后作用基于隐私保护MDAV算法的结果,则[M(D₁)]敏感度为d,[M(D₂)]敏感度为d+1;

4) 结合定义1，得出P_r[M(D₁)]/P_r[M(D₂)]=d/d+1≤1≤e^ε,其中敏感度越大,则披露的风险越大,P_r越大;

综上所述，ε-MDAV算法满足ε-差分隐私保护。通过获取上述算法隐私保护的数据集即为最终发布的净化集。

3 实验与分析

本次实验采用SuLQ框架模式,实验算法使用Java语言实现,编程环境为MyEclipse10,实验的环境配置为2.20GHz i7-4702MQ、8GB内存、1TB硬盘,Windows 8.1操作系统。

实验所采用的数据集DS1为“MHEATH”，来源于格拉纳达大学,该数据集拥有120个实例,23个数据类型为real的属性;数据集DS2为“Census”，来源于CASC(欧洲工程),该数据集拥有1080个实例,13个数值类型的属性。

为了验证本文最终所提出的ε-MDAV算法在数据安全性方面的优势,尤其在保证数据原有的可用性方面,选取MDAV算法作为其可用性精确性的对比算法。首先微聚集可用性可采用F(F-Measure)^[15]评价指标衡量,分别对MDAV算法和ε-MDAV算法进行微聚集操作,使用其微聚集结果计算F值,F值越大,两者的相似度也就越大,则在ε-MDAV算法作用下的数据可用性越高。其次数据集安全性可采用相反的风险值来评估,本次实验采用基于距离的记录链接模型。该模型指出,属性越多,数据空间维度越大,则敏感度越高,隐私披露的风险也就越大,属性多涉外链接的密度较大,则被链接成功的可能性也就越多,针对任何隐私保护模型,属性越少,维度越少,安全性则越高^[16]。即用匿名表中的链接成功地记录所占的比率作为风险值的测度R,那么风险概率R越大,泄露的风险越大,算法的安全性也就越低。由于MDAV没有对隐私级别进行数学定义,因此本文在实验时,选取ε=1这一常规的差分隐私保护级别,在此基础上对两种算法进行比较。在MDAV算法和ε-MDAV算法在DS1和DS2上的可用性对比如图 4(a)、(b)所示;风险披露程度对比如图 4(c)、(d)所示;ε-MDAV算法作用于不同维度的数据集安全性对比如图 4(e)所示。

由图 4可知:在算法ε-MDAV中，当ε=0.05时,即噪声较大,算法的可用性较低,但风险值较低,安全性较高;随着ε的增大，即噪声较低，可用性也慢慢趋近于高可用性程度,风险值增大,安全则随之减弱。因此在现有的环境中该算法可保证原有高可用性的情况下提高安全性的要求。但缺陷是,首先随着噪声的加大,无法避免数据精确性的丢失,安全风险也随着噪声的影响因素较大。另外在上述实验采取的风险模型中,DS1的属性较DS2稍多即其数据维度略高,但区别较小,原因是两数据集维度总体都不高。实验结果验证了算法在低维度适应性较强,当数据维度较高或慢慢扩大时,ε-MDAV算法作用下的数据披露风险增加,适用性减弱。

4 结语

本文分别研究匿名隐私保护和差分隐私保护两种数据隐私保护技术,在这两种技术特点的基础上提出一种基于差分隐私的数据匿名化隐私保护方法,得出最终的基于差分隐私的ε-MDAV算法。本文方法与基于MDAV的匿名化系列算法相比,主要有两处改进:第一点是将匿名隐私保护与差分隐私保护有效地结合,将差分隐私技术引入到匿名化过程中;第二点是根据数据的特征将Laplace噪声引入微聚集MDAV算法中构建ε-MDAV。实验结果表明,本文提出基于差分隐私的数据匿名化隐私保护方法可以有效地保证数据的安全性与可用性。