全 文 ：第 33卷 第 5期 燕山大学学报 Vol. 33 No. 5
2009年 9月 Journal of Yanshan University Sept. 2009
0 引言
随着网络上电子信息量不断增多，针对特定数
据集的安全问题受到了人们的广泛关注。一般来
说，数据发布者会隐藏掉社会保险码等标识属性，
但是通过在多个公开的数据源间进行连接操作往
往会导致无意的隐私信息泄露问题，即连接攻击。
为此，人们提出了 -匿名模型 [1-3]。 -匿名是指发布
表中的每一条记录 ，都至少要有 1 ( 2)条记录
与其在准标识符上具有相同的属性值。这样，该组
记录中的个体身份将不能被唯一确定。通过降低根
据准标识符进行隐私推理的概率，实现隐私保护的
目的。
-匿名模型能够很好地解决准标识符导致的
隐私泄露问题，但是也存在着不足。如果攻击者感
兴趣的个体所在匿名组中的敏感属性值都相同，那
么攻击者就能以 100%的概率猜测出该个体的敏感
属性值，造成个体隐私信息的泄露。这种没有考虑
匿名后敏感属性值由于缺乏多样性而导致的隐私
泄露问题就是连接一致性攻击。针对此局限，文献
[4]提出了增强型 匿名模型—— -多样性，对敏感
属性在同一匿名组中的不同值个数进行限制。
目前大多数 -匿名方法都针对单敏感属性 [5-8]，
但是，现实中要保护的敏感属性可能不止一个。例
如病人的诊断记录表中，可能同时包含不愿让他人
知道的医疗费及家庭电话等。如果将现有方法直接
应用于多敏感属性，必将造成隐私信息的泄露。本
文研究多敏感属性保护问题，首先，按照多敏感属
性各维的不同取值，构造多敏感属性树；然后按照
最大叶子子树优先策略，选择各维敏感属性值都不
同的 棵最大子树，从中抽取记录进行分块；无法
再分块时，将剩余记录插入已分好的块中；最后，
对各分块中的记录进行匿名处理。这样得到的数据
各维敏感属性均满足 -多样性。实验证明，所提方
法能在确保信息损失率较小的情况下，有效地保护
数据隐私。
1 相关工作
1998年, L. Sweeney提出 -匿名技术 [1, 9]，它
要求发布后的数据中存在一定数量不可区分的个
体。使攻击者不能判别出隐私信息所属的具体个
体，从而防止了个人隐私的泄露。 -匿名自提出以
来, 得到了学术界的普遍关注。由于 -匿名化数据
会造成信息损失，如何在满足 -匿名约束的情况下
减少信息损失，成为研究的热点。
文献 [5]、[6] 分别证明了获得最高精度的 -
文章编号：1007-791X(2009)05-0433-05
基于最大叶子子树优先策略的多敏感属性保护方法
祁瑞丽 1，王 可 2，郭学涛 1，李金才 1，唐军军 1，刘国华 1, *
（1. 燕山大学信息科学与工程学院，河北秦皇岛 066004; 2. 大连理工大学 电子与信息工程学院，辽宁大连
116000）
摘 要：首先将多敏感属性隐私保护问题转化为多敏感属性 -多样性问题，然后给出了多敏感属性树构造方法
及最大叶子子树优先策略，在此基础上提出了一个多敏感属性保护算法。最后，通过实验对算法进行了验证和
分析。结果表明，该方法能有效地保护数据隐私，减少信息泄露。
关键词：隐私保护；多敏感属性树；最大叶子子树； -多样性
中图分类号：TP309.2 文献标识码：A
收稿日期：2009-06-08 基金项目：国家自然科学基金资助项目（60773100）；国家“十一五”科技支撑计划资助项目（2006BAK05BO2）；
河北省自然科学基金资助项目（F2009000475）
作者简介：祁瑞丽（1984- ），女，河北邢台人，硕士研究生，主要研究方向为数据库、视图安全；*通讯作者：刘国华（1966- ），
男，黑龙江齐齐哈尔人，教授，博士生导师，主要研究方向为数据库安全、模式匹配、系统仿真，Email：ghliu@ysu.edu.cn。
434 燕山大学学报 2009
匿名表是 NP困难问题, 并分别给出了概括单元数
为最小概括 log 倍和 倍的近似算法。研究
人员采用多种启发式方法来解决 -匿名问题，主要
的研究结果包括采用全局化最优匿名方法 [7] 以及
基于多维划分的方法 [8]。这些研究都是针对原始 -
匿名模型来进行的。
文献 [4] 提出的 -多样性算法是 -匿名的改进
模型。它保留了数据表中足够多的信息，不足之处
是该算法只适用于单个个体对应单条元组的数据
表，对单个个体对应多条元组的数据表的隐私信息
不能保证，而且该算法一次只能处理一个敏感属
性。
文献 [10] 提出了个性化匿名的概念，不仅使
要发布视图满足 -匿名，更综合考虑每个个体对隐
私属性保密程度的要求，针对不同的个体提供不同
粒度的保护，更有效地保护个体的隐私安全。
文献 [11] 提出了支持插入操作的动态匿名策
略，当有新元组到达时，并不是直接将其插入某个
等价组中进行匿名发布，而是当新数据达到一定量
并满足 -多样性时才进行发布。这样就可以有效地
避免攻击者对前后发布的多个视图进行差异比较
而导致的隐私泄露问题。
文献 [12] 根据多约束之间的关系，通过继承
Classfly算法的元组概括过滤思想，提出支持多约
束的 -匿名化方法 Classfly+及相应的 3种算法。
以上隐私保护方法都是针对单敏感属性的，如
果将其直接用于多敏感属性，必将造成隐私信息的
泄露。本文针对单敏感属性保护方法的不足，提出
了基于最大叶子子树优先策略的多敏感属性保护
算法，实验表明，该算法能在确保信息损失率较小
的情况下，有效地保护数据隐私。
2 多敏感属性保护问题
表 1为一个包含疾病与医药费的共享表, 假设
在该表中 Money 和 Disease 是敏感属性，需要对
其进行保护。若将单敏感属性 -多样性匿名方法直
接应用在该表上，设匿名参数 =3, 匿名结果如表
2所示。在第一个特征类{ 1, 2, 3}中，虽然 Disease
的值满足 3-多样性，但是Money的值违背 3-多样
性（都是 5000），这样，只要攻击者感兴趣的个体
在第一个匿名组，就会很容易得到该个体的Money
值，造成隐私信息泄露。所以，对多敏感属性进行
保护是很有必要的。
表 1 隐私数据为 Disease和 Money的医疗记录表
Tab. 1 Medical table with sensitive attibutes Disease and
Money
Name Sex Age Zipcode Disease Money
Mary F 35 47918 Flu 5000
Jack M 38 47916 Cancer 5000
Anne F 36 47913 HIV 5000
Bob M 32 47906 Cancer 6000
Nike M 34 47907 HIV 4500
LiLy F 33 47901 Gastritis 4000
表 2 3-匿名表
Tab. 2 3-anonymous table
ID Sex Age Zipcode Disease Money
1 Person [35-39] 4791* Flu 5000
2 Person [35-39] 4791* Cancer 5000
3 Person [35-39] 4791* HIV 5000
4 Person [30-34] 4790* Cancer 6000
5 Person [30-34] 4790* HIV 4500
6 Person [30-34] 4790* Gastritis 4000
下面对多敏感属性保护问题进行形式化定义。
假设要发布表 ，表中含有属性 1, 2, , ,
1, 2, , , 其中 1 为准标识符属性，
1 为敏感属性，敏感属性域 ，每条记
录记作 1 ，第 条记录的敏感属性值
。
定义 1 特征类：发布表 中，一个特征类是
指在准标识符属性 1, 2, , 上具有相同值的
一组数据记录构成的集合。
在准标识符属性 1, 2, , 上作投影，可
以得到一组特征类 1 ， = 1 ，
表 中的任一记录属于且仅属于一个特征类。
定义 2 多敏感属性 -多样性 [4]：对于一个多
敏感属性记录集 ，当把属性集 1, 2, , ,
1, 2, 1, +1, , 看作准标识符时，敏感属性
1 满足max 1，其中，max 为
中敏感属性的最大频繁取值出现次数， 为
中记录条数,则该记录集满足多敏感属性 -多样
性。
定理 1 如果表 满足多敏感属性 -多样性，则
该表的隐私泄露率不超过 1/ 。
第 5期 祁瑞丽 等 基于最大叶子子树优先策略的多敏感属性保护方法 435
证明 由定义 2知，一个特征类满足多敏感属
性 - 多样 性，则 它的 任一 敏感属 性满 足
max 1 1 )，即攻击者对于特征类中记
录的每一维敏感属性都无法以大于1/ 的概率推断
出其真实值。由于 = 1 ，所以攻击者对
于 中记录的每一维敏感属性都无法以大于1/ 的
概率推断出其真实值。得证。
例如，在上述表 2 中，假设攻击者想要得到
Bob 的 Disease 和 Money 值，通过外部知识推断
出 Bob 在第 2个特征类 4, 5, 6 中。由于该特征
类在敏感属性Disease和Money上满足 3-多样性，
所以攻击者得到 Bob真实信息的概率 1/3。
定义 3 多敏感属性子树: 将表 中记录在敏
感属性 1, 2, , 上做投影，以一组投影值 1,
2, , )为父结点，在这些敏感属性上取该值的
记录号为孩子结点形成的树称为多敏感属性子树。
多敏感属性表 的隐私泄露率不超过1/ 时，认
为表 是安全的。要保护多敏感属性表的隐私安全，
就是要使这个表满足多敏感属性 -多样性，即将这
个表划分成多敏感属性 -多样性特征类，其关键问
题是保证每个特征类中敏感属性的最大频繁值出
现次数满足max 1。
3 多敏感属性保护方法
多敏感属性保护问题的核心是敏感属性的处
理，本节给出多敏感属性树构造方法和最大叶子子
树优先策略，以及记录间距离测量方法和信息损失
函数。在此基础上，提出了基于最大叶子子树优先
策略的多敏感属性保护算法。
3.1 多敏感属性树构造方法及最大叶子子树优先
策略
多敏感属性树构造方法：根据敏感属性域
=1, 2, , ，将表 中记录在敏感属性
1, 2, , 上做投影，取值相等的记录按照定
义 3形成一棵多敏感属性子树，这样表 中的每条
记录属于且仅属于一棵多敏感属性子树
1 。再以 为孩子结点，以 Parent为父
亲结点，构造一棵多敏感属性树 Tree。Parent结点
有 个存储单元，其中第个单元存储指向子树 的
指针 和该子树的叶子结点数量 。
基于聚类的最大叶子子树优先策略：扫描根结
点，选择叶子数量最多且各维敏感属性值都不相同
的 棵子树，从最大子树中随机抽取一条记录 作为
聚类中心 ，形成分块。并删除叶子结点，修改根
结点中的相应值。再以插入前后信息损失差值最小
为原则，从其余的 1棵子树中每棵里面选取一条
记录，插入该块。并删除叶子结点，修改根结点中
的相应值。第 2次仍选择叶子数量最多且各维敏感
属性值都不相同的 棵子树，选取聚类中心时，要
求与前一个聚类中心 的距离最大，以保证类与类
之间的差别最大。重复以上过程，直到无法再形成
分块。这样，每个分块中都有 条各维敏感属性值
都不相同的记录。
以下给出记录间距离测量方法和信息损失函
数。
3.2 距离测量方法和信息损失函数
记录之间距离的计算依赖于其是数值型数据
还是分类型数据，本文采用文献 [13] 的距离计算
函数。
定义 4 两条记录间的距离：令 1, 2, , ,
1, 2, , , 1, 2, , )是表 的属性，其中，
=1, 2, , 是数值型属性， =1, 2, ,
是分类型属性， =1, 2, , 为敏感属性，那
么，对于记录 1, 2 ，它们之间的距离定义为
1, 2 =1
1 2
+ =1
1 , 2
, (1)
其中， 表示记录 在属性 上的值； 是 中
最大值与最小值之差， , 是以 和 的最小公共
祖先为根的子树； 代表树 的高度。
为了评价匿名表相对于原表的精确程度，需要
对信息损失程度进行度量。本文采用文献 [14] 的
信息损失度量函数
* =
+
=1
*包含的数值个数 1
所在域包含的数值个数， (2)
其中， 为一个准标识符属性； *是 概括后的值；
*为概括后的记录，它的信息损失为其各个准标识
符属性信息损失之和。若某条记录被隐匿，则其信
436 燕山大学学报 2009
息损失为 + 。
因此，概括表 *的信息损失率为：
* =
*
+
=1
1
。 (3)
3.3 基于最大叶子子树优先策略的多敏感属性保
护算法
根据构造的多敏感属性树对表 中记录进行分
块，确保每个分块满足多敏感属性 -多样性，同时
块内信息损失最小。算法描述如下：
基于最大叶子子树优先策略的多敏感属性保
护算法
输入：数据集 ，多样性参数 ，以及各属性的
概括树；
输出：满足多敏感属性 -多样性的匿名表 *;
1） if ( 或者任一敏感属性不同值个数 )
2） return ;
3） end if;
4） 以敏感属性值为标准, 将 中记录构造成多敏感属性树 Tree;
/*多敏感属性树构造阶段*/
5） if (各维敏感属性值都不相同的子树数量小于 )
6） 提示调整 , 退出程序;
7） else执行步骤 8）~29）;
8） *= ; =1; =NULL;
9） while 各维敏感属性值都不同的子树至少为 个 /*分块阶段*/
10） {扫描根结点, 选择叶子数量最多且各维敏感属性值都不
同的 棵子树 = 1, 2 , , ；
11） 从 中的最大子树 1中随机选取一条记录 , 使得 和 之
间的距离最大; /*选择一个聚类中心*/
12） = ; /*记录上一次的聚类中心*/
13） = ; = ; . 1 ; /*修改子树 和
根节点中对应该子树的叶子结点数*/
14） for =2; <= ; ++
15） {在子树 中选取一条记录 , 满足将 插入块 后与
插入前信息损失差值最小;
16） = ; = ; . ;
17） }
18） = +1; /*记录聚类编号*/
19） }
20） *= =1, 2, , ;
21） while (剩余记录不为空) /*处理剩余记录阶段*/
22） { 对于记录 tup
23） if存在将其插入后满足多敏感属性 -多样性的块
24） 从 中选择将 tup插入后与插入前信息损失差值最
小的块, 将 tup插入该块;
25） else
26） 将 tup隐匿;
27） }
28） 根据分块 =1, 2, , 对表 *的准标识符属性进行匿名处理;
29） return *;
算法分析：步骤 1）~3），对输入参数 进行判
断，不合理时直接返回表 ；步骤 4）~6），构造多
敏感属性树，按照 3.1中的方法将表 中记录构造
成一棵多敏感属性树；步骤 9）~20），分块，按照
最大叶子子树优先策略形成分块，直到各维敏感属
性值都不相同的子树数量小于 ；步骤 21）~27），
处理剩余记录，当剩余子树中记录无法再构成分块
时，对于每条记录，如果存在将其插入后满足多敏
感属性 -多样性的块，则选择插入后和插入前信息
损失差值最小的块将其插入，否则，抑制该记录发
布；步骤 28）~29），对得到的各个分块进行匿名
处理，并返回匿名表 *。
4 实验及分析
实验中所采用的原始表为 (age, sex, zipcode,
problem, money, telephone)，过滤掉原数据集中的
不完整记录。选取前 3个属性作为准标识符属性，
第 1次取 (problem, money) 作为敏感属性，第 2
次取 (problem, money, telephone)作为敏感属性。
对每种情况分别取 =2，3，4对算法进行验证，实
验结果如图 1 和图 2 所示。实验的硬件环境为：
Intel Pentium4 1.6 GHz CPU， 512 MB内存；操作
系统平台为：Microsoft Windows XP Professional；
编程环境为：Microsoft Visual C++ 6.0编译器。
由实验结果得知，对数据集进行匿名之后，多
敏感隐私属性泄露率不大于 1/ 。由于不同的匿名
参数 对准标识符的概括程度不同，因此最后的信
息损失程度也不一样。由图 1和图 2知：对于相等
数量的数据集，随着 值变大，信息损失率增大，
这是因为 值变大，隐私保护程度提高，同一个聚
类分块中的不同敏感属性个数增加，导致准标识符
属性的泛化程度增加，使得信息损失率变大；对于
相等的参数 ，随着数据集数量的增加，信息损失
率增大，这是因为数据集数量增大，导致同一分块
中需要处理的记录数增多，准标识符属性的泛化程
度增加。对比图 1和图 2得：当数据集数量相等，
参数 相等，敏感属性个数较多时，信息损失率较
高，这是由各维敏感属性多样性导致的。由上述分
析可知，所提出的多敏感属性保护方法是正确和有
效的。
第 5期 祁瑞丽 等 基于最大叶子子树优先策略的多敏感属性保护方法 437
图 1 信息损失率随 值和记录条数不同的变化情况
Fig. 1 Rate of information loss with and records number
varying ( =2)
图 2 信息损失率随 值和记录条数不同的变化情况
Fig. 2 Rate of information loss with and records number
varying ( =3)
5 结束语
本文提出的方法可以确保每维敏感属性的隐
私泄露率都不超过 1/ ，使发布视图达到 -匿名效
果，从而有效保证发布视图的安全。此外，由于综
合考虑信息损失，使每一块内的信息损失最小，提
高了数据精度。下一步研究工作是如何在 值偏大
时，对敏感属性进行概括以实现隐私保护。
参考文献
[1] Samarati P. Protecting respondents identities in microdata release
[J]. IEEE Trans on Knowledge and Data Engineering, 2001,13
(6): 1010-1027.
[2] Samarati P, Sweeney L. Protecting privacy when disclosing in-
formation: -anonymity and its enforcement through generalization
and suppression [R]. Technical Report SRI-CSL-98-04, SRI Com-
puter Science Laboratory, 1998.
[3] Sweeney L. -anonymity: a model for protecting privacy [J]. In-
ternational Journal on Uncertainty, Fuzziness and Knowledge bas-
ed Systems, 2002,10 (5): 557-570.
[4] Machanavajjhala A, Gehrke J, Kefer D. -diversity: privacy
beyond -anonymity [C] //Proceedings of the 22nd International
Conference on Data Engineering, Atlanta, 2006: 24.
[5]Meyerson A,Williams R.On the complexity of optimal -anonymity
[C] //Proc of PODS, New York, 2004: 223-228.
[6] AggarwaL G, Feder T, Kenthapadi K, et al.. -anonymity:
algorithms and hardness [R] //Stanford University, 2004: 124-135.
[7] LeFevre K, DeWitt D J, Ramakrishnan R. Incognito: efficient
full-domain -anonymity [C] //ACM SIGMOD International Con-
ference on Management of Data, Baltimore, 2005: 49-60.
[8] Lefevre K, Dewitt D, Ramakrishnan R. Mondrian multidimensional
-anonymity [C] //Proceedings of the 22nd International Confer-
ence on Data Engineering, Atlanta, 2006: 25.
[9] Samarati P, Sweeney L. Generalizing data to provide anonymity
when disclosing information [C] //Proc of the 17th ACMSIGMO-
DSIGAC-SIGART Symposium on the Principles of Database Sys-
tems, Seattle, 1998: 188.
[10]Xiao X,Tao Y.Personalized privacy preservation[C]//Proceedings
of ACM Conference on Management of Data (SIGMOD). New
York: ACM Press, 2006: 229-240.
[11] Byun J W, Sohn Y, Bertino E, et al.. Secure anonymization for
incremental datasets [C] // The 3rd VLDB Workshop on Secure
Data management (SDM). Germany: Springer Verlag,2006: 48-63.
[12] 杨晓春, 刘向宇, 王斌, 等. 支持多约束的 -匿名化方法 [J].
软件学报, 2006,17 (5): 1222-1231.
[13] Byun J W, Kamra A, Bertino E, et al.. Efficient -anonymization
using clustering techniques [C] //Internal Conference on Database
Systems for Advanced Applications, Hong Kong, 2007.
[14] Iyengar V S. Transforming data to satisfy privacy constraints
[C] //Proceedings of the eighth ACM SIGKDD international con-
ference on Knowledge discovery and data mining, Edmonton, Al-
berta, Canada, 2002: 279-288.
[15] Yang Ye, Qiao Deng, Chi Wang. BSGI: an effective algorithm
towards stronger -diversity [M] //Database and Expert Systems
Applications, Berlin/Heidelberg: Springer, 2008: 19-32.
[16] Dong Yalong, Li Zude, Ye Xiaojun. Privacy inference attacking
and prevention on multiple relative -anonymized microdata sets
[M] //Progress in WWW Research and Development. Berlin/Hei-
delberg: Springer, 2008: 263-274.
（下转第 443页）
400
记录条数
0
0.8
0.4
信
息
损
失
率
200 600 800
0.2
0.6
=2
=3
=4
400
记录条数
0
0.8
0.4
信
息
损
失
率
200 600 800
0.2
0.6
=2
=3
=4
第 5期 王 柠 等 外包数据库中字符数据的 -映射密文索引技术 443
[6] Bijit Hore, Sharad Mehrotra, Gene Tsudik. A privacy-index for
range queries [C] //Proceedings of the 30th VLDB conference,
Toronto, Canada, 2004: 223-235.
[7] Damiani E, Sabrina De Capitani di Vimercati, Finetti M, et al..
Implementation of a storage mechanism for untrusted DBMSs C //
Proc of the second International IEEE Security in Storage Wor-
kshop, Washington DC, USA, 2003: 38.
[8] Damiani E, Sabrina De Capitani di Vimercati, Jajodia S, et al..
Balancing confidentiality and efficiency in untrusted relational
DBMSs [C] // Proc of the 10th ACM Conference on Computer
and Communications Security,Washington DC,USA, 2003: 27-31.
[9] 赵丹枫, 金顺福, 刘国华, 等. DAS模型下基于查询概率的密
文索引技术 [J]. 燕山大学学报, 2008,32 (6): 477-482.
-mapping cipher index scheme as to character
data in outsourced databases
WANG Ning1,2, ZHAO Wei1, LIU Guo-hua1, ZHAO Chun-hong1
(1. College of Information Science and Engineering, Yanshan University, Qinhuangdao, Hebei 066004, China; 2. College of
Computer and Control Engineering; Qiqihar University, Qiqihar, Heilongjiang 161006, China)
Abstract: For the improvement of query efficiency in the outsourced database, cipher index scheme has appeared. But existing
index scheme has lowness of query hit rate, and unnecessary bandwidth occupancy is caused by network transmission crowding.
The reduction of redundant tuples is research hotspot in cipher index scheme of the outsourced database. Firstly all the characters
composed the domain of attribute are determined, then indices are assigned to each character through mapping function. Finally,
a cipher index is formed through contacting character indices with random characters appropriately. Based on above, a -mapping
cipher index scheme as to character data is presented. This scheme eliminates redundant tuples with supporting fuzzy queries.
Finally, cipher query strategy applied the outsourced database model is presented, and theory analyses as well as experiment veri-
fication are done.
Key words: outsourced database; -mapping; character data; cipher index
（上接第 437页）
A method for protecting multi-sensitive attributes based on
maximal-leaf-subtree-first strategy
QI Rui-li1, WANG Ke2, GUO Xue-tao1, LI Jin-cai1, TANG Jun-jun1 , LIU Guo-hua1
(1. College of Information Science and Engineering, Yanshan University, Qinhuangdao, Hebei 066004, China; 2. School of
Electronic and Information Engineering, Dalian University of Technology, Dalian, Liaoning 116024, China)
Abstract: First, the multi-sensitive attributes privacy protecting problem was transformed into the multi-sensitive attributes -di-
versity problem. Then, a method of construction for the multi-sensitive attributes tree and the maximal-leaf-subtree-first strategy
were presented. Based on this, a multi-sensitive attributes protecting algorithm was proposed. Finally, the algorithm was confirmed
and analyzed through experiment. The results show that the method can effectively protect data privacy and reducing information
disclosure.
Key words: privacy protecting; multi-sensitive attributes; maximal-leaf-subtree; -diversity