0 引言

随着数据共享和分析等应用需求的发展，如何保护数据隐私和防止敏感信息泄露成为当前面临的重大挑战^[1-3].在数据发布过程中的隐私保护技术主要有基于泛化、抑制和聚类技术的k-匿名模型^[4]，k代表通过处理后，每个等价组中，除敏感属性外准标识符完全一样，这样当敏感数据都不相同时隐私披露的风险为1/k, 但当敏感属性的取值过少时，会大大提高隐私披露的风险，即无法防御同质攻击.研究人员在k-匿名的基础上提出了l-多样性^[5]，提出了解决同质攻击的方法，参数l代表在等价组中敏感属性最小取值范围，要求每个等价组至少包含l个表现良好的敏感属性，这样隐私披露的风险最高不超过1/l.基于k-匿名技术的扩展还有t-closeness^[6]、(a, k)-anonymity^[7]等.差分隐私^[8]是基于数据失真的隐私保护技术，通过对敏感数据添加噪音使得敏感数据失真，并通过严谨的理论证明，当满足差分隐私的条件时，可以在保护隐私的同时维持数据某些方面的统计特性.研究人员在差分隐私的基础上也进行了一些研究工作^[9].文献[10-11]提出了一种交通时序数据的隐私保护发布技术，但是系统的计算复杂度较高.文献[12]分析了大数据时代的到来对隐私保护的新挑战.文献[13]指出解决大数据隐私问题的当务之急是针对不同的风险，建立混合式与综合性的隐私管理框架，并积极拓展隐私管理的关键技术研究.

本文的主要贡献：提出了基于身份替代的保护方法(privacy protection based on identity replacement，PPIR).总结并提出了数据身份和数据特征2个概念.设计了衡量数据身份相似度和数据特征相似度的数学模型.从隐私泄露风险、数据可用性和时间复杂度3个方面验证了该方法可行且有效.

1 相关知识

背景知识攻击  假设攻击者获取了一张包含攻击目标A病例信息的数据表，经过一番筛选，挑选出了3条记录，对应的疾病信息为{乳腺癌，骨折，艾滋病}，攻击者有关于A的背景知识{A是男性，最近经常晨跑}，因为男性患乳腺癌的几率很低，基本排除，再根据A最近经常晨跑的背景知识可以断定A没有骨折，由此基本可以断定A患了艾滋病，攻击者就实现了获取A疾病信息的目标.

泄露风险  表示根据发布的数据和背景知识披露隐私造成隐私泄露的概率.记敏感数据为p, 背景知识为b, 则在背景知识b的帮助下隐私泄露风险Risk(p, b)可以表示为Risk(p, b)=P(p|b), 其中P表示概率.

欧几里得距离  欧几里得距离又称欧氏距离，是衡量多维空间中2个点之间的绝对距离最常见的距离度量方法.$dist\left({X, Y} \right) = \sqrt {\sum\limits_{i = 1}^n {{{\left({{x_i}{\rm{ -}}{y_i}} \right)}^2}} } \; $.

向量空间余弦相似度  用向量空间中2个向量夹角的余弦值作为衡量2个个体间差异的大小.相比距离度量，余弦相似度更加注重2个向量在方向上的差异，而非从距离或角度出发.公式为

$ sim{\rm{ }}\left( {\vec x, \vec y} \right) = {\rm{cos}}\theta = \frac{{\vec x \cdot \vec y}}{{\left\| {\vec x} \right\| \cdot \left\| {\vec y} \right\|}}. $

2 基于身份替代的隐私保护方法

PPIR数据发布流程如图 1所示.数据发布流程分为3个部分：数据收集，数据处理，数据发布.

数据收集：收集来的数据经过简单的预处理后成为存储在本地的高敏感数据.

数据处理：通过身份替代处理，用虚拟身份替代原始身份，并通过阈值判定对处理后不符合条件的数据重新处理.

数据发布：用虚拟身份替代原始身份添加到发布数据中，发布数据.

2.1 PPIR的相关定义

为了简化描述和方便理解，本文处理的属性值均取数值型数据.

定义1  数据身份  身份信息是描述一条数据区别于其他数据的信息，一条数据的所有属性，都属于数据身份的一部分.攻击者的攻击目标本质就是获取数据身份信息，并进一步获取目标的敏感属性.

定义2  数据特征  特征信息用于描述数据的特征，不同于数据身份，数据的特征是一个更加宽泛的概念，一条数据的身份只有一个，但是该条数据的特征并不唯一.数据分析的过程大部分都要先进行分类处理，对数据进行分类依赖的是数据的特征而不是数据身份.

例1标识符、准标识符、数据身份和数据特征  设一条记录{编号：45337，姓名:张三，年龄：18岁，身高：172 cm，体重：55 kg}，针对这条记录，{编号：45337}为其标识符，通过编号可以从数据集中确定该条记录(虽然存在同名同姓的情况，一般的姓名也被视为标识符)；{年龄：18岁，身高：172 cm，体重：55 kg }为该记录的准标识符，通过准标识符可以从数据集筛选出少量相符的记录，甚至与标识符一样唯一确定一条记录；{编号：45337，姓名:张三，年龄：18岁，身高：172 cm，体重：55 kg}是这条记录的数据身份，能够唯一确定一条记录，并包含记录的所有信息；该记录的数据特征并不唯一，例如{年龄：20岁左右，身高170 cm左右，体重：55 kg左右}或者{身高170 cm左右体型匀称的青少年}都可以是这条记录的数据特征.

定义3  单属性偏移δ  δ∈[0, 1]，表示属性改变之后相对原来的值的偏移，计算方法为

$ \delta = \frac{{\left| {x'{\rm{-}}x} \right|}}{x} $

(1)

其中：x′代表改变后的值；x代表原始值.

注：理论上δ∈[0, +∞)，但在实际处理过程中，一般δ∈[0, 1].

定义4  单属性相似度λ  λ∈[0, 1]，用于表示改变之后的值与原始值的相似程度，λ=1时，x′=x.计算方法为

$ \lambda = 1{\rm{-}}\delta $

(2)

定义5  影响因子ξ  实际生活中每个属性的变化对记录身份和特征的影响是不同的，有的对记录的影响比较大，有的影响比较小.为了简化，假设所有属性的影响因子ξ=1.

定义6  身份相似度α  鉴于人们认识事物的思维习惯，设计衡量身份相似度的计算公式为

$ \alpha = {\zeta _1}{\lambda _1}\; \cdot {\zeta _2}{\lambda _2} \cdot \;\; \cdots \;\; \cdot {\zeta _n}{\lambda _n} = \prod\limits_{i = 1}^n {{\zeta _i}{\lambda _i}} . $

(3)

定义7  特征相似度β  为了衡量特征相似度，在余弦相似的基础上加以改进，计算公式为

$ \beta = \frac{{\left\| {\vec a} \right\| \cdot sim\;\left( {\vec a, \vec b} \right)}}{{\left\| {\overrightarrow {} } \right\| \cdot sim\;\left( {\vec b, \vec b} \right)}} = \frac{{\left\| {\vec a} \right\| \cdot \cos \;\left( {\vec a, \vec b} \right)}}{{\left\| {\overrightarrow {} } \right\| \cdot \cos \;\left( {\vec b, \vec b} \right)}}\; $

(4)

定义8  身份偏移Δ_id  累积各个属性对整条数据的影响，通过累积属性偏移计算公式为

$ {\Delta _{{\rm{id}}}} = 1-\alpha . $

(5)

定义9  特征偏移Δ_ch  用于表示处理后数据特征与原始数据特征的差别, 计算公式为

$ {\Delta _{{\rm{ch}}}} = 1{\rm{-}}\beta .\; $

(6)

2.2 身份替代算法的设计思路 2.2.1 身份替代算法的核心

身份替代(identity replace，IR)算法的核心：1)根据数据本身的特征生成一个虚拟的身份，这样可以很大程度上保存数据原有的特征.2)用虚拟身份将原始数据从发布数据中替换掉，原始身份不出现在发布数据中.3)原始数据虽然不出现在发布数据中，但是代表原始数据的特征的虚拟身份存在于发布数据中，能够保证数据的可用性，并且提高隐私保护的强度.IR算法的流程如图 2所示.

Step 1:通过对原始数据的每个属性添加指定范围内的随机噪音数据, 再生成虚拟身份Vid(注:指定范围根据数据不同属性的具体情况由人为指定，如身高的范围指定为±3 cm).

Step 2：首先根据式(1)和(2)计算单属性相似度λ，再根据式(3)和(4)分别计算Vid与原始数据的身份相似度α和特征相似度β.

Step 3：根据式(5)和(6)分别计算身份偏移Δ_id和特征偏移Δ_ch.

Step 4：人为设置阈值用于控制隐私保护程度和数据可用性高低程度，对于符合阈值范围的添加到发布数据中，不符合阈值范围的返回重新生成虚拟身份.

2.2.2 身份替代算法分析

1) 抵御背景知识攻击方面相较于k-匿名，身份替代利用虚拟身份替代原始身份，当攻击者直接使用背景知识时，虚拟身份可以起到对攻击者进行误导的作用，这在很大程度上降低了攻击者获取到目标敏感信息的概率，如果攻击者采用背景知识推理的方法，会增加分析的工作量，这间接降低了隐私泄露的风险.使得攻击者无法直接使用背景知识，能够抵御一定程度的背景知识攻击.

2) 数据可用性维持方面.差分隐私的隐私保护机制从数据的整体出发，添加噪音后的数据集与原始数据集的分布相似，但是由于添加的噪音是由不同噪音机制产生的随机噪音，虽然能够保证整体分布几乎不变，却无法保证单条数据的特性不变，这又可能造成单条数据严重失真.身份替代从单条数据出发，基于数据本身的特征生成虚拟身份，然后利用阈值控制生成的身份确保虚拟数据不会过度失真.假设单条数据的变化被控制在±a范围之内，那么数据集的整体分布S₁就一定在原始分布S₀的±a范围之内，这样不仅保证单条数据的特性得以保存，也能够保证处理后的数据集在整体分布上与原始数据集的分布相似.

3) 算法复杂度.时间复杂度方面：最坏情况下，程序所有生成的虚拟身份均无法通过阈值判断，但最坏情况只有当生成虚拟身份指定的范围和阈值判断条件设计不合适的时候才会发生，适当调整这2个参数即可防止最坏情况的发生，也可以通过设置最大循环次数m来防止发生死循环.对于一条有n个属性的数据，算法平均时间复杂度为O(n), 最坏的情况下算法时间复杂度为O(mn)，由于m是常数，所以算法的整体时间复杂度为O(n).空间复杂度方面：身份替代算法在处理过程中需要的内存空间为常数(只需要几个临时变量用于记录各个参数).

3 实验与分析 3.1 实验环境

实验平台采用Windows 10，开发环境为Idea(Java)+MySQL.实验数据在美国UCI Machine Learning Repository中的Adult数据集^[14]的基础上随机生成疾病信息，作为敏感信息合成模拟病例数据，实验数据包含字段{性别，年龄，身高，体重，疾病}.

3.2 实验内容与结果分析

1) 数据可用性测试.通过对大数据集(10万条)和小数据集(1万条)进行处理，测试处理后的数据与原始数据在数据分布中的相似度，验证数据的可用性，以及数据量变化对本方法处理结果数据可用性的影响.

结果分析：由图 3和图 4的对比(小数据集)，以及图 5和图 6的对比(大数据集)可以看出，除部分处理前后存在少量差异，其余部分处理后的数据分布与处理前的数据分布基本能够保持一致.可以看出通过身份替代的方法处理后的数据很好地保留了原始数据的分布特征.通过4张图的对比可以看出，从数值上分析大数据集相对于小数据集的误差有所增加，但是由于大数据集的基数比小数据集基数大，前者的相对误差实际上是小于后者.由此可见，当数据量越大时，身份替代方法处理后的数据可用性会有一定程度的提高.

2) 泄露风险测试.取隐私泄露的基准为身份相似度大于等于95%, 针对不同的属性处理范围T, 选取100个抽样点进行隐私泄露风险测试.选取T₁{0, ±3，±5，±5}和T₂{0, ±5，±10，±10}两组数据进行对比(注: T₁范围中0, ±3，±5，±5分别代表模拟身份与原身份性别相同；年龄在原数据[-3, +3]范围内；身高在原数据[-5, +5]范围内；体重在原数据[-5, +5]范围内).

图 7和图 8分别显示了不同的属性处理范围T₁和T₂处理后虚拟身份与原始身份的相似度情况，超出基准线的认为造成了隐私泄露，经统计图 7中发生泄漏的有25条，泄露比例为25%, 图 8中发生泄漏的有4条，泄露比例4%.通过两图对比可得通过对属性处理范围T可以控制隐私泄露风险，当T的范围越大，隐私泄露比例越小.

3) 程序运行时间测试.取1万条数据作为测试数据，在整个处理过程中设置了50个采样点，对于每个采样点，测量了处理用时以及处理速度两个观测值，为了方便在同一个图中展示，以当前时间点速度处理1 000条数据所需的时间，来代表该时间段内处理数据的效率(为了准确，只测量核心算法模块的计算时间不包含程序与数据库交互部分).测量结果如图 9所示.

由图 9可以看出，随着数据量的增加，程序运行时间基本保持线性增长，而处理1 000条数据的用时在最初较高的情况下，逐渐降低，并最终维持在较低水平.以上可以表明，算法的时间复杂度较低并且是线性的，算法时间复杂度近似O(n).

4 总结

本文研究了数据发布过程中的隐私泄露问题，分析了现有方法的不足，提出了基于数据失真技术身份替代方法来保护隐私信息，总结并提出了数据身份和数据特征两个概念，设计了衡量身份相似度和特征相似度的数学模型来维持数据可用性.最后从数据可用性、隐私泄露风险和时间复杂度3个方面对该方法进行了测试，证明该方法能在较低的时间消耗下保证良好的隐私保护强度和较高的数据可用性.下一步工作将重点研究属性处理域T的自适应方法，以及该方法在动态数据发布方面的应用.