应对间接攻击的方法

1）匿名

匿名技术防止了链接攻击。假设身份信息，例如姓名、地址、ID等都从数据集中删除，攻击者还是可以通过在公开数据集中存在的其他属性恢复身份信息，例如邮编、生日、姓名。这些属性称为准标识符（quasi-identifier）。例如，图11-4是一个删除了病人姓名的医疗数据集。然而，攻击者可以将这个表和图11-4中的投票人数据集相链接，就可以唯一地标识出一个人的身份。例如，攻击者可以发现第六个病人就是Bob，他患有皮肤癌。

图11-4　匿名技术示例数据集

阻止链接攻击最常见的方法是K-匿名（K-anonymity）［ 3］，基本思想是确保在准标识符属性（例如邮编、生日和性别）上至少有K个人有相同的值。图11-5的表满足了2-匿名，因为在邮编、生日和性别上至少有两个病人有相同的值。K-匿名通常通过概括数值来实现（即，用大体的数值或是数值范围来代替具体的值）。例如，图11-5中邮编删除了最后一位，出生日期被年份范围代替。

K-匿名模型有如下好处：

（1）模型易于理解。

（2）匿名后的数据可以共享。

（3）数据的精确度下降但仍然可信（例如，用数值范围代替具体的值，这个数值仍然在该范围内）。

图11-5　匿名技术示例

K-匿名的最大问题在于不能提供足够有力的隐私保护。如果攻击者知道一些额外信息，那么这种模型就会失效。例如，在图11-5中的匿名数据集中，有三个病人有Bob一样的准标识符属性（邮件、生日、性别），其中两个人患了肺癌，一个有皮肤癌。如果攻击者知道Bob不吸烟，那么他患肺癌的概率就很小。这样就可以推测出他更有可能患了皮肤癌。对于K-匿名的改进有其他方法，例如L-多样性（L-diversity）［ 4］。例如，L-多样性方法要求对于有相同准标识符属性的人，还必须有至少L个能充分表示疾病（或其他敏感属性值）的数值。然而，这些模型仍然基于攻击者不具有其他信息的假设，如果这个假设不成立，那么这些模型还是很容易被攻击。

2）差别隐私（differential privacy）

差别隐私［5］是一种非常强大的隐私保护模型，即使是在最糟糕的情况下，攻击者获得了数据集中除了一行之外的所有行数据，也能保护隐私。在差别隐私模型下，即使是在最糟糕的情况下，攻击者仍然无法推测出他们所没有的那一行的有用信息。

差别隐私通常适用于交互式环境下，用户对数据集进行统计查询（例如，查询上海家庭的平均收入）。就算只允许用户进行统计查询（而不可以查询具体行），攻击者还是有可能推测出数据集中个人的信息。例如，假设房间里有100个人，用户只允许查询平均年龄。攻击者可以这样问两个问题，第一个问所有人的平均年龄，第二个问除了X之外所有人的平均年龄。这样攻击者就可以根据两次查询结果的差值推测出X的准确年龄（100×查询结果1—99×查询结果2）。

差别隐私的过程如下。它对统计查询的结果添加随机噪声，噪声必须服从特定的分布（例如拉普拉斯分布）。噪声可以防止攻击者从两个数据库（一个包含X，另一个不包含）查询结果的差别中作出推测。也就是说，X对结果的影响被隐藏了。更正式地，如果两个只差一行的数据库D1和D2满足，则称满足了ε-差别隐私。这里，P（D1→r）是指从D1中得到带噪声的结果r的概率。通常，我们把ε设为一个比较小的值，例如0.1或0.01。对于比较小的ε，接近于1+ε。所以攻击者无法从结果r中辨别出x是否在数据库中。

拉普拉斯分布满足概率密度函数，其中x是噪声的值，b是噪声的规模。通常设置，△是单独一行最查询结果的最大影响（称为敏感度）。例如，一个人对平均年龄的最大影响就是他最大可能的年龄（比如150）除以人数。(www.xing528.com)

差别隐私模型有如下好处：

（1）在所有隐私保护模型中它的保护性最强，不依赖于攻击者所获信息的假设（事实上就是攻击者知道了数据库中其他所有人的信息，也无法判断出剩下的那个人是否在数据库中）。

（2）相对误差（噪声）随着数据库中行数的增加而降低。例如，对于平均年龄查询的最大影响等于，n是人数。如果n= 1000，ε=0.01，则噪声等级b=15，这个值很大。而对于n = 1000000，则b = 0.015，这个值就很小。

（3）可组合性。当对同一个数据集进行多项查询时，假设对每个查询都有一个差别隐私保证εi，则所有查询总的差别隐私保证就是。例如，假如有两项查询，每一个都有0.01的隐私保证，那么总的隐私保证值=0.01+0.01=0.02。

但是差别隐私模型有如下问题：

（1）用户不能直接获得数据，只能进行统计查询。

（2）有时噪声等级会很高（尤其是单个行对最终结果有巨大影响时）。例如，如果想要计算最大年龄，那么每个人对结果的影响并不能随着数据集的增大而减小，因为每个人都有可能改变最大年龄。对于小数据集（例如，小于10000行的数据集），差别隐私模型会增加非常大的噪声。

（3）由于结果是失真的，并不清楚用户是否会相信这些带噪声的结果。

3）安全多方计算（securemulti-party computation， SMC）

安全多方计算［6］针对的情形是多个各自拥有一些数据的组织想要将数据组合在一起进行数据挖掘，但不想直接共享数据。数据通常或是水平分区（每个组织有数据中的相同列、不同行），或是竖直分区（每个组织拥有相同数量的数据但属性值不同）。例如，多个商店可能有不同水平分区的顾客数据，电话公司和电商公司可能有相同的顾客但是不同的属性（竖直分区）。

SMC技术使用密码学技术（同态加密）来直接对加密数据进行计算，而无需解密。由于同态加密无法处理复杂计算，因此需要将数据挖掘过程分成小的步骤（例如，计算和、均值、内积、最大最小值），每一步都用加密协议进行计算。

SMC技术有两个问题：

（1）加密协议的代价很高（在CPU运算时间和网络传输两方面），这就阻碍了SMC在大规模数据集上的应用。

（2） SMC受制于勾结（即两家组织合作窃取第三方的数据）。

由于这两点局限性（尤其是第一点）， SMC技术很大程度上仍处于研究阶段，并未在成熟的商业产品中应用。

4）规则隐藏

存在一些对隐藏敏感关联规则的研究［7，8］。假设有一系列数据集，其中存在一些数据拥有者不愿被发现的敏感的关联规则。而另一方面，他们又希望有人（比如咨询公司）可以从数据集中挖掘出非敏感的关联规则。常见的解决方法就是通过修改数据集（例如，增加或删除数据或交易）来降低那些不愿被发现的敏感规则的置信度，同时将对非敏感规则的影响降到最小。