(s，d)-个性化K-匿名隐私保护模型

傅鹤岗，杨 波

(重庆大学 计算机学院，重庆 400044)

随着互联网技术的飞速发展，基于网络的虚拟社会逐步形成，信息的收集、加工、传播更加快捷。现代社会是信息高度共享的社会，使得数据库安全问题日益突出，其中对数据的窃取、篡改和破坏直接危害着数据库的安全，成为亟待解决的问题。随着数据挖掘技术的兴起，大量的信息如：病人就诊信息、学生学籍信息、员工工资及档案信息等面临着泄漏的风险。对个人、企业甚至国家的危害是不容小觑的，个人信息的泄露容易造成诈骗的发生；企业和国家信息的泄露容易造成国家机密的暴露，直接危害国家安全。

自由保护型的数据库隐私保护处理的隐私信息是对外公开的，所有人都可以使用，主要保护隐私信息和个人的对应关系[1]。即攻击者可以轻松获取数据库中的记录，攻击的目标是某条隐私信息和某个体的一对一关系。典型的攻击方法是链接攻击(Linking Attack)[2]。

1 K-匿名技术

较好地解决链接攻击的方法是参考文献 [2]中Samarati和Sweeney引入的K-匿名机制。它要求公布后的数据中存在一定数量的不可区分的个体，从而使攻击者无法判断出敏感属性的具体个数，以此达到保护个人隐私的目的。为了使数据表满足K匿名性质，需要对原始表在准标识符上进行加工，如采用抑制或者泛化技术。

K-匿名技术通过生成若干等价组，使等价组内QI属性和隐私属性不再是一一对应的关系，从而保证了个人隐私信息不被泄露。等价组的概念为：在准标识符上的投影完全相同的、记录组成的记录集合，即等价组内所有的记录在准标识符上的属性值完全相同，但是其他属性可以不同。

定义 1 K-匿名。 给定数据表 A(B1，B2，……Bn)，QI是与A相关联的准标识符，当且仅当在A[QI]中出现的每个值序列至少在 A[QI]中出现 K次，则A满足K-匿名。A[QI]表示A表中的元组在QI上的投影[3]。

表1为原始数据表，其中年龄、性别、地区编码为准标识符，疾病为敏感属性，没有任何可以唯一标识个体身份的属性存在，如身份证号码、姓名等。经过3-匿名化处理后如表2所示，每一条记录都有另外两条记录在准标识符上与其相同。即使攻击者知道某条记录在表2中，也无法确定哪条记录与其对应，但这样并不能完全防止隐私泄露。因此参考文献[3]提出了1-多样性概念，即把等价组内出现频率最高的敏感属性限制在1/1以内。p-sensitive K-匿名模型[4]是在K-匿名模型的基础上要求每个等价组内至少要有p个不同的敏感属性值，在一定程度上抵御了属性泄漏问题，但是当K值很大的时候就表现得不是很好。(a，k)-匿名模型[5]限制了等价组内敏感属性出现的频率不高于a，在一定程度上防止了一致性攻击，但是它对所有敏感属性采用相同的约束，无法达到实用的目的。参考文献[6]提出了一种不基于概括和隐匿的新方法——Anatomy，通过将原始关系的准标志符属性和敏感属性以两个不同的关系发布，利用它们之间的有损连接保护隐私数据的安全。这些模型都没有考虑敏感属性敏感度问题，而且无法抵御背景知识攻击。

表1 原始数据表

表2 3-匿名化数据表

2 (s，d)-个性化K-匿名隐私保护模型

K-匿名的主要缺陷：(1)K-匿名没有考虑到匿名后可信属性由于缺乏多样性而导致的隐私泄露问题(同质性攻击)；(2)默认所有属性都有相同的重要性；(3)不能抵御背景知识攻击。

本文介绍的 (s，d)-个性化K-匿名隐私保护模型就是为了解决这些问题而提出来的。在介绍(s，d)-个性化K-匿名隐私保护模型前需要给出的定义：s-相似等价组、临界敏感度、高危敏感度、d-非关联约束。

定义2 s-相似等价组。是指在敏感属性值上相似的至少s个记录组成的等价组，在这里相似的定义根据具体的应用会有所不同。例如：如果敏感信息是疾病，则可以将病变器官作为相似划分标准，如胃部疾病，肝部疾病等。

定义3 临界敏感度。由专家确定或者根据具体应用领域灵活确定的、能够较好体现对敏感属性保护程度的一个数值度量，其值在0～1之间。

定义4 高危敏感度。高危敏感度是指敏感属性值的敏感度大于、等于临界敏感度，其值在0～1之间。

定义5 d-非关联约束。对于s-相似等价组E，在E中高危敏感度属性值出现的频率f不高于d，即|f|/|E|＜d(0≤d≤1)，其中d是用户确定的参数。但其必须满足d不能等于1且不能过大，即不能太接近1。

定义6 (s，d)-个性化K-匿名隐私保护模型。如果一等价组由位于不同相似组的s-相似等价组组成，每个s-相似等价组都满足d-非关联约束，并且每个等价组至少由K条记录组成，如果数据表T中的每个等价组都满足以上条件，那么就称数据表 T满足(s，d)-个性化K-匿名隐私保护模型。

(s，d)-个性化K-匿名隐私保护模型就是利用一个等价组中如果包含了多组s-相似等价组，并且每个s-相似等价组都满足d-非关联约束，就可以更加有效地抵御同质性攻击及属性泄漏。另外如果每组相异值包含了多组相似值，可更加有效地抵御背景知识攻击，从而大大降低隐私信息泄漏的风险。本文阐述的(s，d)-个性化K-匿名隐私保护模型如表3所示。

表3 包含2个2-相似等价组的4-匿名等价组

根据病变器官这一相似性进行2-相似分组，可以看出该等价组满足2-相似条件，从K=4的匿名表可以看出，由于敏感属性疾病这一列都是高危敏感度属性值，敏感度高达0.9，即使其满足匿名条件，但是该等价组的隐私信息也已经暴露出来了，攻击者很容易得出该等价组对应的个体患有很严重的疾病，也就造成了属性泄漏。虽然从某种程度上来说还没有造成身份泄露，但这也是人们所不希望的。

根据(s，d)-个性化K-匿名隐私保护模型的规定，调整如表 4、表 5所示。

表4 s=2，d=0.5，K=4 的例子 1

表5 s=2，d=0.5，K=4 的例子 2

表4、表 5中的每个等价组都满足 s=2，d=0.5(即sensitivity>0.70的敏感属性值出现在每个2-相似等价组中的频率≤0.5)，K=4条件，但是可以较好地防止属性泄漏问题。从敏感属性敏感度的分布来看，经过调整记录得到的这两个表其实就是减少了每个2-相似分组中高危属性值的出现频率。表4中将癌症的出现频率控制在了50%以内，表5中也将癌症的出现频率控制在了50%以内。本文提出的(s，d)-个性化K-匿名隐私保护模型，在K-匿名模型基础上做出了改进，有效地解决了由高危属性值出现频率过高而导致的属性泄漏问题，同时能很好地抵御同质性攻击和背景知识攻击。

3 (s，d)-个性化K-匿名隐私保护模型算法

输入：数据表T，对敏感属性的敏感度进行标记s={S1，S2……Sn}，敏感属性按相似性分组 g=(g1，g2，…，gn)，准标识符各个属性的权重 W=(w1，w2，…，wn)，参数为 s，d，K。

输出：满足(s，d)-个性化K-匿名隐私保护模型的数据表 Ta’。

处理过程：

(1)生成s-相似等价组，并且这些等价组满足 d-非关联约束。

(2)对生成的s-相似等价组寻找使泛化信息损失最少的、K/s个不位于相同相似组内的s-相似等价组：

Ta’={}

For(对于 Ga中的每一个分组 Ga’)

Gt={}，在 Ga’中取一条记录

If(|Gt|!=K/s)

在 Gt中找一分块 Gt’，使得 Gt’中的记录 t’和 t的敏感属性值不属于同一个敏感属性组，并且dist(QI[t]，QI[t’])最小 ，Gt=Gt∪Gt’， Ga=Ga/Gt。

End if Ta’= Ta’∪Gt

End for

(3)对生成的满足(s，d)-个性化K-匿名隐私保护模型条件的各等价组进行泛化处理，即对Ta’中的每个分块进行泛化处理。

4 实验

实验所使用的数据集来自UCI机器学习数据库[7]中的adult数据库，该数据库在研究K-匿名应用最多，已经成为该领域事实上的标准测试集。数据库大小为5.5MB，本文选取其中的30 704条记录及15个属性，其中准标识符数量选择6个，将职业(WORKCLASS)作为敏感属性。敏感属性泄漏分析如表6所示。

表6 敏感属性泄漏分析

实验软硬件环境：

硬件环境：Intel Pentium(R)Dual-Core CPU，2GB RAM。

操作系统：Microsoft Windows XP。

编程环境：Eclipse+Mysql Server 5.1。

执行时间分析如图1所示。

图1 两种模型下执行时间的对比

本文针对K-匿名没有考虑到匿名后可信属性由于缺乏多样性而导致的隐私泄露、默认所有属性都有相同的重要性、不能抵御背景知识攻击等问题，提出了一种新的(s，d)-个性化K-匿名隐私保护模型。该模型通过s-相似分组，并且限制每个s-相似等价组内的高危敏感属性值出现的频率小于d，然后组合不同相似分组内的s-相似分组使其满足K-匿名条件。实验证明该模型能很好地弥补K-匿名的不足，有效地防止了隐私泄露。

[1]刘喻，吕大鹏，冯建华，等.数据发布中的匿名化技术研究综述[J].计算机应用，2007，27(10)：2361-2364.

[2]SWEENEY L.K-anonymity：a model for protecting privacy[J].International Journal on Uncertainty，Fuzzi-ness and Knowledge-based Systems，2002，10(5)：557-570.

[3]MACHANAVAJJHALA A， GEHRKE J， KIFER D， et al.L-diversity：Privacy beyond K-anonymity[C]//Proc of the 22 nd International Conference on Data Engineering New York： ACM Press， 2006.

[4]TRAIAN T M， BNDU V.Privacy protection： p-sensitive k-anonymity property[C]//.Proc of the 22 nd International Conference on Data Engineering New York： ACM Press，2006.

[5]WONG R C， LiJinyong， FU A W， etal. (a，k)-anonymity：an enhanced k-anonymity model for privacy preserving [C]//.Proc ofthe 12 th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining New York： ACM Press， 2006.

[6]Xiao Xiaokui， Tao Yufei.Anatomy： simple and effective privacy preservation[C]//Proc of the 32 nd International Conference on Very Large Data Bases[SI]：VLDB Endowment， 2006：139-150.

[7]HETTICH C B S，MERZ C.UCI repository of machine learning databases[EB/OL]. (1996-05-01)[2008-04-20].http：//archiveics uci edu/ml/datasets/Adult.