01 数据库隐私威胁模型
目前，隐私保护技术在数据库中的应用主要集中在数据挖掘和数据发布两个领域。数据挖掘中的隐私保护（Privacy Protection Data Mining，PPDM）指如何在保护用户隐私的前提下有效挖掘数据；数据发布中的隐私保护（Privacy Protection Data Publish，PPDP）指如何在保护用户隐私的前提下发布用户数据，供第三方有效研究和使用。
图1描述了数据收集和数据发布的典型场景。
图1 数据收集和数据发布
在数据收集阶段，数据发布者从数据所有者(如Alice，Bob等）收集了大量的数据。在数据发布阶段，数据发布者向挖掘用户或公共用户发布收集的数据，也称为数据接收者，可以有效地挖掘发布的数据，以便于研究和使用。这里的数据挖掘具有广泛的意义，不仅限于模型挖掘和模型构建。例如，疾病控制中心必须收集各医疗机构的病历信息，以防止和控制疾病。一家医疗机构从患者那里收集了大量的数据，并向疾病控制中心发布了这些数据。在这种情况下，医疗机构是数据发布者，患者是数据记录所有者，疾病控制中心是数据接收者。疾病控制中心的数据挖掘可以从糖尿病患者的简单计数到任何事情的聚类分析。
数据出版商有两种计算模型。在不可信的计算模型中，数据出版商是不可信的，它可能会尝试从数据所有者那里识别敏感的信息。各种加密方法、匿名通信方法和统计方法都可以用来从数据所有者那里匿名收集数据而不泄露数据所有者的身份标志。在可信的计算模式中，数据出版商是可信的，数据所有者愿意向数据出版商提供他们的数据。然而，数据接收器是不可信的。
数据挖掘和知识发现在各个领域都发挥着非常重要的作用。数据挖掘的目的是从大量的数据中提取潜在和有价值的知识（模型或规则）。传统的数据挖掘技术在发现知识时会对数据隐私构成严重威胁。例如，在收集医疗机构病历信息的过程中，传统的数据挖掘技术将不可避免地暴露患者的敏感数据（如疾病），而数据所有者（医疗机构和患者）不想被披露或被他人知道。
02 数据库隐私保护技术
隐私保护技术旨在解决数据挖掘和数据发布中的数据隐私暴露问题。在具体实施隐私保护技术时，应考虑以下两个方面：① 如何保证数据隐私在数据应用过程中不泄露；② 如何更有利于数据的应用。详细介绍了基于数据失真的隐私保护技术、基于数据加密的隐私保护技术和基于限制发布的隐私保护技术。
1. 基于数据失真的隐私保护技术
数据失真技术是通过扰动原始数据来实现隐私保护的，扰动后的数据需要满足：① 攻击者无法找到真实的原始数据，即攻击者无法通过发布的失真数据和一定的背景知识重建真实的原始数据；② 失真处理后的数据应能够保持某些性质不变，即使用失真数据获得的某些信息与从原始数据获得的信息相同，如一些统计特征，确保基于失真数据的某些应用程序是可行的。
以失真为基础的隐私保护技术主要采用随机化、堵塞、凝聚等技术。
（1）随机化
数据随机化就是在原始数据中加入随机噪声，然后发布扰动后的数据。随机化技术包括随机扰动和随机应答两类。
① 随机扰动。利用随机技术修改敏感数据，保护数据隐私。2（a）给出随机扰动的过程。攻击者只能拦截或观察扰动后的数据，从而实现真实数据X然而，扰动后的数据仍然保留了原始数据的分布信息。通过重构扰动数据，如图所示2（b）原始数据可以恢复X但不能重构原始数据的准确值x1,x2,…,xn。
图2
随机扰动技术可以在不暴露原始数据的情况下挖掘各种数据。由于扰动数据通过重构获得的数据分布几乎与原始数据相同，因此在使用重构数据分布进行决策树分类器训练后，获得的决策树可以很好地对数据进行分类。在相关规则挖掘中，可以通过在原始数据中添加大量伪项来隐藏频繁项集，然后通过估计随机扰动后数据中项集的支持来找到相关规则。此外，随机扰动技术也可以应用于在线分析和处理（Online Analytical Processing，OLAP）实现隐私保护。
② 随机应答。随机响应是指数据所有者在扰动原始数据后发布，使攻击者无法以高于预定阈值的概率得出原始数据是否包含一些真实信息或伪信息。虽然发布的数据不再真实，但在数据量相对较大的情况下，统计信息和收集信息仍然可以更准确地估计。随机响应和随机干扰的区别在于，敏感数据通过响应特定问题向外界提供。
（2）阻塞与凝聚
随机技术的一个不可避免的缺点是，不同的应用程序需要设计特定的算法来处理转换后的数据，因为所有的应用程序都需要重建数据的分布。凝聚技术可以克服随机技术的这一缺点，其基本思想是将原始数据分成组，每组存储k条记录产生的统计信息，包括每个属性的平均值、协议差等。这样，只要采用凝聚技术处理的数据，就可以通过一般的重构算法处理，重构后的数据不会披露原始数据的隐私，因为在同一组中k两两不能区分条记录。
与随机技术修改敏感数据和提供非真实数据的方法不同，阻塞技术采用不发布特定数据的方法，因为一些应用程序更喜欢基于真实数据进行研究。例如，可以引入代表不确定值的符号“？”隐藏布尔关联规则。因为某些值被隐藏了。“？”因此，在最小估计值和最大估计值之间，对某些项集的计数是一个不确定值。因此，隐藏敏感关联规则是将敏感关联规则的可能支持和可信度控制在预定阈值以下，当数据中的阻塞尽可能少时。此外，阻塞技术还可以隐藏分类规则。
2. 基于数据加密的隐私保护技术
基于数据加密的隐私保护技术主要用于分布式应用，如分布式数据挖掘、安全查询、几何计算、科学计算等。分布式应用程序的功能实现通常取决于数据存储模式、网站的可信度和行为。
分布式应用程序使用两种数据模式来存储数据：垂直划分和水平划分。垂直划分数据是指分布式环境中每个网站只存储部分属性的数据，所有网站存储的数据不重复；水平划分数据是将数据记录存储在分布式环境中的多个网站，所有网站存储的数据不重复。根据其行为，分布式环境中的网站可分为准诚信攻击者和恶意攻击者。准诚信攻击者是遵守相关计算协议但仍试图攻击的网站；恶意攻击者是不遵守相关计算协议并试图披露隐私的网站。一般来说，假设所有网站都是准诚信攻击者。
基于加密技术的隐私保护技术主要包括安全多方计算、分布式匿名化、分布式相关规则挖掘、分布式聚类等。
(1)安全多方计算
安全多方计算协议是密码学中一个非常活跃的学术领域，具有很强的理论和现实意义。一个简单、安全、多方计算的例子是中国著名科学家姚志志提出的百万富翁问题：两个百万富翁Alice和Bob他们都想知道谁更富有，但他们不想让对方知道任何关于自己财富的信息。
按照常规安全协议运行后，双方只知道谁更富有，而对方具体有多少财产却一无所知。
一般来说，安全多方计算可以描述为一个计算过程：两个或多个协议参与者根据秘密输入计算函数。安全多方计算假设参与者愿意共享一些计算数据。然而，每个参与者都不希望其他参与者或任何第三方知道他们的输入。
一般来说，安全多方计算可以看作是有的n个人参与者分布式网络中的私人输入是x1,x2,…,xn的计算函数f（x1,x2,…,xn），其中参与者i只知道自己的输入xi和输出f（x1,x2,…,xn），没有其他多余的信息。如果有可信的第三方，解决这个问题将变得非常容易。参与者只需通过秘密通道将其输入传输给可信的第三方，并由可信的第三方计算函数，然后将计算结果广播给每个参与者。但在现实中，很难找到一个可信的第三方，让所有的参与者都信任它。因此，安全多方计算协议主要针对在没有可信第三方的情况下安全计算
众多分布式环境下基于隐私保护的数据挖掘应用都可以抽象成无可信第三方参与的安全多方计算问题，即如何使两个或多个站点通过某种协议完成计算后，每一方都只知道自己的输入和所有数据计算后的结果。
基于安全多方计算“准诚信模型”因此，该假设的应用范围有限。
(2)分布式匿名化
匿名是隐藏数据或数据源，因为大多数应用程序需要匿名处理原始数据，以确保敏感信息的安全，然后在此基础上进行数据挖掘和发布。分布式数据匿名面临着如何确保网站数据隐私和收集足够的信息，以实现数据匿名的问题。
在垂直分割的数据环境中实现两种分布式k-以匿名为例，解释分布式匿名。假设有两个网站S1、S2，他们拥有的数据分别是{ID,A1,A2,…,An}和{ID,B1,B2,…,Bn}，其中，Ai为S1拥有数据的第一i个性属性。利用可交换加密在通信过程中隐藏原始信息，判断是否构建完整的匿名表“满足k-匿名条件”先实现。分布式k-匿名算法如下所示。
输入：站点S1、S2，数据{ID,A1,A2,…,An}、{ID,B1,B2,…,Bn}
输出：k-匿名数据表T×
过程：
① 私钥密钥分别产生在两个站点K1和K2，且须满足：EK1（EK2（D））=EK2（EK1（D）），其中D任何数据。
② 表T×←NULL。
③ while T×数据不满意k-匿名条件 do。
④ 站点i（i=1或2）
a. 泛化{ID,A1,A2,…,An}为{ID,A1×,A2×,…,An×}，其中A1×表示A1泛化值；
b. {ID,A1,A2,…,An}←{ID,A1×,A2×,…,An×}；
c. 用Ki加密{ID,A1×,A2×,…,An×}并将其传递给另一站点；
d. 用Ki加密另一站点加密的泛化数据并回传；
e. 根据两个站点加密ID值匹配数据，构建经典K1和K2加密数据表T×{ID,A1×,A2×,…,An×，ID,B1,B2,…,Bn}。
⑤ end while。
在水平划分的数据环境中，数据可以通过引入第三方和使用质的密钥来实现k-匿名化：每个站点加密私有数据并将其传递给第三方，并且只有k当条数据记录的准标志符属性值相同时，第三方的密钥可以使用k解密条数据记录。
(3)挖掘分布式相关规则
在分布式环境中，挖掘相关规则的关键是计算项集的全局计数，加密技术可以确保在计算项集计数时不会泄露隐私信息。例如，在垂直数据划分的分布式环境中，需要解决的问题是：如何使用分布在不同网站上的数据来计算项集的计数，以找出支持大于阈值的频繁项集。此时，不同网站之间的计数问题被简化为在保护隐私数据的同时计算不同网站之间的标量积。
(4)分布式聚类
基于隐私保护的分布式聚类的关键是安全计算数据之间的距离。聚类模型有Naïve聚类模型（K-means）采用加密技术和多种聚类模型实现信息的安全传输。
① Naïve聚类模型：每个站点安全地将数据加密模式传递给可信第三方，可信第三方聚类后返回结果。
② 多聚类模型：首先，每个站点对当地数据进行聚类并发布结果，然后对每个站点发布的结果进行二次处理，实现分布式聚类。
3. 基于限制发布的隐私保护技术
限制发布是指有选择地发布原始数据、不发布或低精度的敏感数据，以实现隐私保护。目前，基于限制发布的隐私保护技术主要采用数据匿名技术，即在隐私披露风险和数据精度之间妥协，有选择地发布敏感数据和可能披露敏感数据的信息，但确保敏感数据和隐私的披露风险在可容忍的范围内。
数据匿名化一般采用两种基本操作。
① 抑制。抑制数据项，即不发布数据项。
② 泛化。泛化是指对数据的更抽象和概括的描述。例如，30岁可以泛化为范围[20,40]，因为30在范围[20,40]。
匿名数据处理的原始数据一般以数据表的形式进行，表中的每一行都有一个记录，对应于一个人。每个记录包含多个属性（数据项），可分为三类。
① 显式标志符（explicit identifier），身份证、姓名等可以唯一表示单一个体的属性。
② 准标志符（quasi-identifiers），几个属性可以联合起来，只能标志一个人，比如邮编、性别、出生年份等。
③ 敏感属性（sensitive attribute），疾病、收入、宗教信仰等信仰等用户隐私数据的属性。
表1显示了医院的原始诊断记录，每个记录(行)对应于一个唯一的病人，其中{“姓名”}显示标志符属性，{“年龄”“性别”“邮编”}标志符属性为标准，{“疾病”}敏感属性。
表1
传统的隐私保护方法是删除表1中显示的标志“姓名”，然后发布。表2给出了表1的匿名数据。假设攻击者知道表2中有Betty攻击者知道诊断记录Betty年龄为25岁，性别为女性，邮编为12300，根据表2，攻击者确定Betty对应表中的第一条记录。因此，攻击者可以肯定Betty患了肿瘤。
表2 某医院原诊断记录(匿名)
显然，通过传统的数据隐私保护算法获得匿名数据并不能很好地防止攻击者根据标志符信息推测目标个体的敏感信息。因此，有必要有更严格的匿名处理方法来保护数据隐私。
(1)数据匿名算法
大多数匿名算法致力于解决如何根据一般匿名原则更好地发布匿名数据的问题，另一方面，如何使匿名数据更有利于应用。
① 基于一般原则的匿名算法
基于一般原则的匿名算法通常包括泛化空间枚举、空间修剪、选择优化泛化、结果判断和输出。基于一般原则的匿名算法大多是基于k-匿名算法的区别在于判断算法结束的条件，泛化策略和空间修剪基本相同。
② 匿名算法是针对特定目标的
在特定的应用场景中，一般的匿名算法可能不能满足特定目标的要求。针对特定目标的匿名算法是针对特定应用场景的隐私算法。例如，考虑到数据应用程序需要使用发布的匿名数据来构建分类器，因此在设计匿名算法时，需要考虑如何使发布的数据更有利于分类器的构建，测量指标应该能够直接反映对分类器构建的影响。现有的自下而上的匿名算法和自上而下的匿名算法都以信息增益为衡量因素。发布的数据信息丢失越少，构建的分类器的分类效果就越好。每次搜索泛化空间时，自下而上的匿名算法都会使用信息丢失最少的泛化方案进行泛化，并重复上述操作，直到数据满足匿名原则的要求。自上而下的匿名算法操作过程相反。
③ 基于聚类的匿名算法
基于聚类的匿名算法将原始记录映射到特定的测量空间，然后将空间中的点聚类以实现数据匿名。k-匿名算法保证每个聚类中至少有一个k数据点。根据不同的测量，有r-gather和r-cellular两种聚类算法r-gather在算法中，所有数据点都以所有聚类的最大半径进行聚类，以确保每个聚类至少包含k所有聚类的最大半径越小越好。
匿名算法主要面临以下两个挑战。
a. 如何加权原始数据的不同属性(因为对属性的测量越准确，聚类效果越好)？
b. 如何同意将不同性质的属性映射到同一度量空间？
数据匿名可以满足许多实际应用程序的需求，因为它可以处理各种类型的数据并发布真实的数据。图3显示了数据匿名场景和相关隐私匿名实例。可以看出，数据匿名是一个复杂的过程，需要权衡许多因素，如原始数据、匿名技术、匿名数据、背景知识、攻击者等。
图3 数据匿名场景
（2）k-匿名规则
基于k-将原始数据表中的属性分为以下三类原始数据表中的属性分为以下三类。
① 标志符属性
标志符属性是指标志身份的唯一个人属性，必须在数据发布前从数据表中删除，如用户姓名、电话号码、身份证号码、联系方式等。
② 敏感属性
通常，包含个人隐私信息的属性称为敏感属性，如健康状况、收入水平、年龄、籍贯等。
③ 标准标志符属性
通过连接一些单个属性来标记个人身份的唯一属性，称为标志符属性，可以共享，也可以通过连接到其他外部数据表来泄露隐私信息。
k-匿名规则：指要求其发布的数据表中的每个记录，与其他记录不同k-1（k记录为正整数)条，不能相互区分k条记录称为等价类。
等价类:是由投影在准标志符上完全相同的记录组成的等价组，是针对非敏感属性值而无法区分的。
全局泛化:指每个相同的簇，至少包含k个元组，它们对于簇中准标志符的属性的取值完全相同，即属性均被泛化。如表3所示，这是一个对于年龄属性全局泛化的例子，年龄在所有簇中的取值相同。
表3 年龄属性全局泛化k-匿名表
局部泛化：指每个簇中的标志符属性相同，且大于k，但是簇间属性泛化后的值是不同的。局部泛化k-匿名表如表4所示。
表4 局部泛化k-匿名表
在传统k-人们在匿名的基础上，从多方面面面对k-匿名优化改进。改进后的算法主要是多维的k-匿名算法、Datefly 算法、Incognito 算法、Classfly 算法、Mingen 算法等。
k-匿名方法通常采用泛化和压缩技术匿名处理原始数据k-匿名规则的匿名数据使攻击者无法根据发布的匿名数据准确识别目标个体的记录。
k-匿名规则要求每个等价类至少包含在内k条记录，即匿名数据中的每条记录都至少不能和其他k-1区分条记录，防止攻击者根据标志符属性识别目标个体对应的记录。k保护隐私的价值越大，但丢失的信息越多，数据恢复就越困难。
使用泛化技术用泛化技术获得的表2k=4时的k-匿名数据(简称4-匿名数据)。
表5 4-匿名数据
k-匿名规则切断了个体与数据库中某条具体记录的联系，可以防止敏感属性值泄露，而且每个个体身份被准确标志的概率最大为1/k，这在一定程度上保护了个人隐私。但数据表在匿名过程中对敏感属性没有约束，也可能导致隐私泄露。k-匿名泛化技术的理念是将原始数据中的记录分为多个等价类，用更抽象的值替换同一等价类中记录的准标志属性值，使每个等价类中的记录具有相同的准标志属性值。这样，如果同一等价类中的敏感属性值相对集中，甚至完全相同（可能在形式或语义上），即使满足k-匿名要求也很容易推断出与指定个体相对应的敏感属性值。此外，攻击者还可以通过掌握足够的相关背景知识来确定敏感数据与个人之间的相应关系，从而导致隐私泄露。因此，攻击者可以根据标志符的属性值来区分所有相同类别的记录。
k-匿名方法的缺点是不考虑敏感属性的多样性，攻击者可以使用一致性攻击（homogeneity attack）攻击背景知识（background knowledge attack）确认敏感数据与个人的联系，导致隐私泄露。
匿名模型有四种常见的攻击方法。
① 链接攻击：一些数据集存在于其自身的安全性中，即在孤立的情况下不会泄露任何隐私信息，但当恶意攻击者使用其他重叠属性的数据集进行链接操作时，只能识别特定的个人，以获取个人的隐私信息。将医疗信息与选举人信息结合起来，可以找到两个数据集的共同属性，使恶意攻击者很容易通过链接攻击确定选举人的医疗信息。因此，这种攻击会导致极其严重的隐私泄露。
② 同质攻击：当链接攻击仍然不能确认个人时，有相应的多个记录具有相同的敏感隐私信息，导致隐私泄露，称为同质攻击。
③ 类似攻击：由于敏感信息通常具有类似的敏感性，虽然攻击者不能唯一确定个体，但如果个体对应的多个记录具有类似的敏感信息，则可以推断出个体的一般隐私。例如，一个人患有一种非常不知名的疾病，这也是一种不可避免的严重攻击。虽然攻击类似于同质攻击，不像同质攻击那样直接泄露，但它很有可能发生，对泄露者的心理压力往往是不可预测的，因此需要特别注意这种攻击手段。
④ 背景知识攻击：指攻击者掌握一些特定的信息，通过链接攻击，即使只能获得相应的信息记录，记录室的敏感属性完全不同或不相似，也可以根据背景知识，从多个信息记录中找到唯一相应的信息记录，以获取个人的隐私信息。
（a,k）-匿名规则、l-多样性规则，t-在此基础上，对接近规则等算法进行了相应程度的改进。
（3）（a,k）-匿名模型
（a,k）-匿名模型是扩展后的一种k-匿名模型的目的是保护标志属性与敏感信息之间的关系不被泄露，防止攻击者根据已知标志属性的信息找到敏感属性值。该模型要求的数据值正在满足要求k-在匿名原则的同时，还需要确保这些数据中包含的任何敏感属性值的数量和等价类数的百分比小于a。
a表示敏感属性可接受的最大泄漏概率，反映了隐私属性值的保护程度，因此a根据每个敏感属性值的重要性，设置其设置非常重要。a敏感属性值的泄露概率越小，隐私保护程度越高。a敏感属性值的泄漏概率越大。
例如，在处理工资信息时，我们需要关注超高收入人群和超低收入人群，因为这两个群体往往更关心他们的工资信息是否被泄露。然而，对于那些工资处于平均水平的人来说，他们对个人工资信息的保护欲望较低。在这种情况下，敏感属性值可以设置得更大，甚至可以设置为1。可以理解，敏感属性值与保护等级有关。设置阈值a，能更有效地防止隐私信息泄露，从而提高隐私信息的保护。
如表6所示，在外部数据表中，姓名为标志符属性，已经将其删除。年龄、性别、国籍为准标志符属性，年收入为敏感属性。给定数据表RT（A1,A2,…,An），QI是与RT相关标志符。如果只在RT [QI]每个值序列至少出现在中间RT[QI]中出现过k次，这里的k=2，则RT就满足k-匿名。如果敏感属性中每个值的频率小于a，这里a设置为0.5，则RT就满足（a,k）-匿名。
表6 （0.5,2）-匿名表
（4）l-多样性规则
研究人员正在解决同质性攻击和背景知识攻击造成的隐私泄露问题k-在匿名规则的基础上提出l-多样性（l-diversity）规则。
假如数据表RT′满足k-匿名规则，在同一等价类中，元组至少有l不同的敏感属性称为数据表RT′满足l-多样性规则。
l-基于多样性的规则k-在匿名规则的基础上，其意义在于解决属性链接，降低敏感属性与标准标志属性之间的相关性。该规则要求等价类中的元组数大于k此外，每组元组至少应满足要求l不同的敏感属性。在某种程度上，l-多样性规则与（a,k）-匿名规则的意义类似。表7所示是满足2-匿名信息表的多样性规则，在每个等价类别中，敏感属性的收入值大于或等于2，所以我们可以说表7满足2-多样性规则。
表7 2-多样性表
同样，表5发布的数据也不仅令人满意4-匿名规则，这种满足3-多样性规则，即每个等价类至少有3个不同的敏感属性。
显然，l-多样性规则仍将原始数据中的记录分为多个等价类，并利用泛化技术使每个等价类中的记录具有相同的准标志符属性，但l-多样性规则至少要求每个等价类l不同的敏感属性。l-多样性规则使攻击者最多1/l确认个体敏感信息的概率。
此外，l-泛化技术的根本缺点是在原始数据中丢失了大量信息。l-多样性规则尚未解决k-匿名规则会在原始数据中丢失大量信息。l-多样性规则不能阻止类似的攻击（similarity attack）。
（5）t-逼近规则
t-逼近（t-closeness）该规则要求匿名数据中敏感属性值的分布接近原始数据中敏感属性值的分布，两种分布之间的距离不超过阈值t。t-closeness规则可以保证每个等价类中的敏感属性值多样，语义上不相似，从而防止类似攻击。t-closeness规则只能防止属性泄露，但不能防止身份泄露。t-closeness规则通常与k-同时使用匿名规则，防止身份泄露。t-closeness该规则仍然是泛化技术的隐私规则，大大降低了数据发布的准确性。
（6）Anatomy方法
Anatomy是肖小奎等人提出的一种高精度数据发布隐私保护方法。Anatomy首先，使用原始数据来满足l-多样性规则的数据划分，然后将结果分为两个数据表发布。一个表包含每个记录的准标志符属性值和记录的等价类别ID，另一张表包含等价类ID、每个等价类的敏感属性值及其计数。这将导致结果“切开”在提高标志符属性值的同时，发布方法确保发布的数据得到满足l-对敏感数据为敏感数据提供了良好的保护。