抵制敏感属性相似攻击的个性化（α k m d）-匿名模型

邓博允

摘要：目前，在数据发布领域很少有隐私保护模型满足对敏感属性的个性化保护多数隐私保护，同时又能防御相似攻击。该文针对个性化（α，k）-匿名模型不能抵制敏感属性相似攻击的问题，提出了一种可抵制敏感属性相似攻击的个性化（α，k，m，d）-匿名模型。该模型为敏感属性值建立语义层次树，对敏感属性之间的相异度进行度量，使每个等价类满足个性化（α，k）-匿名模型，同时为了防止等价类遭受相似攻击，要求等价类中满足相异性度量的敏感属性个数大于m。实验数据表明，该文提出的个性化（α，k，m，d）-匿名模型相对于（α，k）-匿名模型在差不多的时间花销，能防御相似攻击，更具安全性。

关键词：隐私保护;个性化;相似性攻击;（α，k）-匿名模型;（α，k，m，d）-匿名模型

中图分类号：TP393        文献标识码：A

文章编号：1009-3044（2020）16-0038-04

Abstract： At present， there are very few privacy protection models in the field of data publishing that can meet most privacy protections for personalized protection of sensitive attributes， and at the same time can prevent similar attacks. Aiming at the problem that the personalized （α， k） -anonymous model cannot resist similar attacks on sensitive attributes， this paper proposes a personalized （α， k， m， d） -anonymous model that can resist similar attacks on sensitive attributes. This model establishes a semantic hierarchy tree for sensitive attribute values， measures the dissimilarity between sensitive attributes， and enables each equivalent class to meet a personalized （α， k） -anonymous model， while protecting the equivalent classes from similar attacks ， Requires that the number of sensitive attributes in the equivalence class that satisfy the dissimilarity measure is greater than m. The experimental data show that the personalized （α， k， m， d） -anonymous model proposed in this paper costs approximately the same time as the （α， k） -anonymous model and can defend similar attacks and is more secure.

Key words： privacy protection; personalization; similarity attack; （α， k） -anonymous model; （α， k， m， d） -anonymous model

1 引言

公共部门、企业部门和个人等无数部门不断提供数字信息，促进知识发现和基于信息的决策制造。发布数据进行分析，同时维护个人隐私，已成为当今处理数据的一项艱巨任务。主要目标是将隐私披露风险降低在可接受水平，同时最大限度地提高发布数据的可用性。匿名化的传统方法是删除凭证字段，例如：姓名和身份证号码。通用的匿名方法是泛化，即使属性在语义上一致。这样，更多的记录会具有相同的准表识符集，在某种程度上保护了某个个体不会被发现。

在文献[1]中讲到了k-匿名模型。Sweeney明确指出在匿名表中，所有记录都必须最少有k个同样的准标识符集。基于k-匿名还有许多成功的应用[2-4]。但是，尽管k匿名保护数据免受身份泄露，但不足以防止属性泄露。为了解决k匿名性的这种局限性，Machanavajjhala等人[5]引入了一个新的隐私概念，称为l-多样性，它要求每个等价类中至少要有l个不同的敏感属性值。Li等人[6]提出了t -closeness概念，这是一种全新的隐私概念，对于此种概念，在任一等价类中，它的敏感属性与整体属性分布非常接近，也就是每两个分布阈值相距小于t）。在文献[7]中讲到了（α，k）-匿名模 型，对于该模型而言，在等价类中，所有的敏感属性值存在频率都必须小于α; 在文献[8]中讲到了p-Sensitive k-匿名模型，对于该模型，首先要保证为k- 匿名，并且在等价类中，最少有 p 个不一样的敏感属性值。通过此种k-匿名模型，可以防止受到背景知识攻击以及一致性攻击。

但是在上述研究过程中，没有考虑不同个体对同一敏感属性进行不同的隐私保护，也就是个性化的隐私保护。在文献[9]中讲到了（α，k）-匿名模型，对于该模型，需要给不同的敏感值定义不同的敏感约束，从而实现个性化保护;文献[10]对p-sensitive k匿名模型做出了改进，在进行敏感属性分级时，参照的是用户自身不同的敏感程度，从而实现个性化保护。以上模型虽能在有效防御一致性攻击和背景知识攻击的情况下实现个性化保护，但不足以防止相似性攻击。

对于（α，k）-匿名模型而言，它无法抵制相似性攻击，本文利用这一特点，在保证实现个性化保护的前提下，构建出了（α，k，m，d）-匿名模型，它能够抵制相似性攻击。它通过限制敏感属性值在等价类中出现的频率以及基于敏感属性的语义分层树并定义了敏感属性相异性的度量方法控制语义相近的敏感属性个数来实现个性化保护和防止相似性攻击。

2 基本概念和相关技术

2.1 基本概念

将原始数据表1属性分为三类：

（1）标识符：即唯一能够反映个体属性的标志，比如：身份证、姓名等。在进行数据处理工作时，一般先删除掉这些属性。

（2）准标识符：无法直接分辨出个体，但是能够利用外部表链接识别个体的属性。比如说：性别、生日等。

（3）敏感属性：人们极力保护的个人隐私信息的属性，如：疾病、收入等。

2.2 抵制敏感属性相似攻击的个性化（α，k，m，d）-匿名模型

定义6：所谓敏感属性语义层次树，指的是利用h高的树来反映不同敏感属性之间的语义关系，其中，1，2，...，h-1，h依次代表的是根节点到叶节点。根节点属于全集泛化，父节点属于子节点的泛化，此外，子节点属于父节点中的子类，叶子节点代表一定的属性值。

3 抵制敏感属性相似攻击的个性化（α，k，m，d）-匿名算法

3.1 α-约束

对于敏感值的个性化α-约束而言，需要按照以下两个原则来实施：（1）如果属性值具有较低的敏感性，就把α数值设定得大一些，如果属性值的敏感程度较高，就把α数值设定得小一点;（2）对于任一敏感值的频率约束α，都必须大于原始数据对应的频率。

3.2 距离度量

定义9（加权层次距离）[11]首先确定一棵泛化树T，h代表的是树的高度，1，2，...，h-1，h，依次代表根节点到叶子节点的层次。其中wj，j-1为节点vj与vj-1之间的权重（2≤j≤h），可用公式（1）定义一个属性从p层泛化到q层（1≤q

3.3 算法描述

个性化（α，k，m，d）-匿名算法思想步骤：（1）基于敏感性度量对各个敏感属性值个性化分配频率约束值α，同时对敏感属性值进行语义分析，生成语义类hash桶，将属于同一类别的敏感属性划分在一个桶里，然后对hash桶按照元组个数进行降序排列;（2）从记录数最大的hash桶中任选一个记录作为等价类的初始质心，并根据距离初始质心最近的要求依次选择k条记录，每次选择元组构成新的等价类都要计算等价类中的α约束值，如果满足就加入等价类，若不满足，则重新选择新元组。（3）对初始等价类进行d-相异判断：若等价类满足d-相异的元组个数不小于m个，则构建满足要求的等价类成功。相反，就需要在等价类中加入新的元组;（4）不断重复（2）、（3）步骤，直到最终不符合个性化（α，k，m，d）-匿名要求;（5）针对符合个性化（α，k，m，d）-匿名约束，实施泛化处理，并且隐藏不符合要求的元组，最终得到一张匿名表。

算法第（1）步是对频率约束值α进行分配，用O（n）表示时间复杂度，然后对时间复杂度进行降序，用O（n?log n）表示;在步骤（2）中，符合α约束值的是k/n×O（k）=O（n），O（（k-1）×k/2）表示的是d-相异的度量间复杂度;在循环过程中，O（n2）代表的是时间复杂度;在步骤（5）中，O（n）表示的是泛化处理时间复杂度，此外，O（m）表示的是其他元组的时间复杂度，m代表的是其他元组的个数。最终时间开销为：O（n）+O（n?log n）+O（n）+O（（k-1）×k/2）+O（n2）+O（n）+O（m）=O（n2）。

4 实验与结果分析

4.1 实验环境

实验环境：操作系统为 Windows 操作系统，具体型号为Intel Core i5-7500 CPU， 3.40GHz ，8.0GB RAM 。在实验过程中，應用的是人口普查adult数据集，存储于UCI机器学习数据库中。实验中我们采用了其中的7个属性，其中准表识符6个，敏感属性一个：occupation。表4为根据敏感属性值的敏感程度个性化设置的频率约束α的参数表。

4.2 执行效率对比

当|QI|=6，d=1时，对比分析k值的个性化（α，k）-匿名模型、个性化（α，k，m，d）-匿名模型，具体情况如图2所示。随着执行时间的不断增加，算法的k值也会不断增加，从而使聚类次数越来越多。为使模型能够防御相似攻击，寻找满足d-相异条件的元组，所以个性化（α，k，m，d）-匿名模型得执行时间相对较长。因此（α，k，m，d）-匿名模型也更具安全性，所以花费多点的执行时间也可接受。

4.3 数据信息保护程度分析

图2为|QI|=6，d=1时两种算法所遭受攻击的记录个数对比。由图可知，本文提出的算法所遭受的攻击数更少，更具有安全性。新算法不仅对单个敏感值使用了频率约束来防御背景知识攻击和一致性攻击，同时运用d-相异条件，针对敏感属性值的语义分析，有效地防御了数据的相似性攻击。由图可见，随着k值的增大，数据被攻击的个数在减少，受保护程度增加。

5 结束语

敏感属性值需要进行个性化保护，而传统模型并不能防止相似攻击，为此本文构建了一个个性化（α，k，m，d）-匿名模型，它能够抵制相似攻击，主要原理是等价类中存在不同的个性化约束敏感值，从而进行个性化保护，此外，还能够根据不同的敏感属性语义层次树，来调控敏感值的出现次数，从而抵制相似攻击。对于该算法而言，它充分发挥了聚类的思想，使数据信息损失最小化。通过大量研究发现，虽然个性化（α，k）-匿名与其执行时间基本一致，但是该算法对数据的保护效果更好。

本文主要研究的是如何保护单一的敏感属性，怎样保护多敏感属性的个性化隐私将是未来重要的研究方向。

参考文献：

[1] Sweeney L. k-anonymity： A model for protecting privacy[J]. International Journal of Uncertainty， Fuzziness and Knowledge-Based Systems， 2002， 10（05）： 557-570.

[2] Stokes K， Torra V. n-Confusion： a generalization of k-anonymity[C]//Proceedings of the 2012 Joint EDBT/ICDT Workshops，2012： 211-215.

[3] Liu J， Wang K. Enforcing vocabulary k-anonymity by semantic similarity based clustering[C]//2010 IEEE International Conference on Data Mining. IEEE， 2010： 899-904.

[4] Wang C， Liu L Z， Gao L J. Research on k-Anonymity algorithm in privacy protection[C]//Advanced Materials Research. Trans Tech Publications Ltd， 2013， 756： 3471-3475.

[5] Machanavajjhala A， Kifer D， Gehrke J， et al. l-diversity： Privacy beyond k-anonymity[J]. ACM Transactions on Knowledge Discovery from Data （TKDD）， 2007， 1（1）： 3.

[6] Li N， Li T， Venkatasubramanian S. t-closeness： Privacy beyond k-anonymity and l-diversity[C]//2007 IEEE 23rd International Conference on Data Engineering. IEEE， 2007： 106-115.

[7] Wong R C W， Li J， Fu A W C， et al. （α， k）-anonymity： an enhanced k-anonymity model for privacy preserving data publishing[C]//Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining. 2006： 754-759.

[8] Truta T M， Vinay B. Privacy protection： p-sensitive k-anonymity property[C]//22nd International Conference on Data Engineering Workshops （ICDEW'06）. IEEE， 2006： 94-94.

[9] 韓建民，于娟，虞慧群，贾泂.面向敏感值的个性化隐私保护[J].电子学报，2010，38（07）：1723-1728.

[10] 贾俊杰， 闫国蕾. 一种个性化 （P， k） 匿名隐私保护算法[J]. 计算机工程， 2018， 44（1）： 176-181.

[11] Li J， Wong R C W， Fu A W C， et al. Achieving k-anonymity by clustering in attribute hierarchical structures[C]//International Conference on Data Warehousing and Knowledge Discovery. Springer， Berlin， Heidelberg， 2006： 405-416.

【通联编辑：代影】