基于差分隐私的直方图发布方法

2022-09-20汤文兵张伟媛

现代计算机 2022年14期

汤文兵，张伟媛

（安徽理工大学计算机科学与工程学院，淮南 232001）

0 引言

近年来，保护隐私的数据分析受到越来越多的关注。而针对隐私问题所提出的隐私保护模型有很多，如k-anonymity、l-diversity、t-closeness等，可以解决有着不同知识背景的攻击者所发起的攻击。在各种隐私概念中，差分隐私在数学上提供了严格的隐私保障，并在本质上防止各种身份攻击，而不管攻击者可能获得的辅助信息是什么。差分隐私要求任何个人数据记录的存在或不存在都不会对结果产生很大的影响，因此用户很难从输出中了解任何个人数据记录，从而保护个人隐私。

例如，表1是某医院患者患病信息的原始数据库表。表1中的“?”表示攻击者知道该患者之外其他所有病人的患病信息，这个时候称这个攻击者有着表1中的最大背景知识。如果数据的拥有者在没有隐私保护的情况下直接发布数据，那么攻击者就能够在通过查询返回值的情况下执行差分攻击去推断Bob的病情信息。此时就称该病人的隐私发生了泄漏。

表1 病人患HIV情况

针对上述问题，本文将差分隐私应用到直方图发布技术中，通过在原始直方图上进行加噪处理来保护数据的隐私信息。在真实数据集进行实验测试，证明该方法能在满足差分隐私的同时进行数据发布，即在保护了个人信息的前提下，同时也保证了数据发布的可用性。

1 定义及相关概念

1.1 直方图

直方图是许多不同研究领域的基本工具，包括数据挖掘、计算机视觉等。给定数据库中一组元组，即={,…,x}，假设属性A上这些元组的值为{,…,x}，则属性A的直方图H由一组等宽的单元格（或桶）组成，每个桶的宽度代表一个查询范围，高度则代表了该范围的统计情况。通常，每个桶的范围不会相互重叠，并且它们的并集应该覆盖所有的属性A值。因此，有了这样一个直方图，可以实时回答属性A的一系列范围查询。

1.2 差分隐私

假设有两个数据集和'，两者的属性结构相同，当且仅当和'最多有一条记录不同时，我们称和'为相邻数据集。因此我们对差分隐私有如下定义：

对于任意两个相邻数据库和'，以及所有可能的输出值的集合，有随机算法，若算法满足：

则称算法提供-差分隐私保护，其中参数称为隐私保护预算。

1.3 隐私保护预算与敏感度

1.3.1 隐私保护预算

算法使用隐私保护预算控制相邻数据集输出相同的概率的比值。实际上反映了可以提供的隐私保护水平，其越小表示隐私性越强，同时数据可用性也就越低。因此，通常将的值与特定的要求结合起来，以实现输出结果的安全性和可用性之间的平衡。

1.3.2 敏感度

敏感度指删除数据集中任一记录对查询结果造成的最大改变，是决定加入噪声量大小的关键因素。在差分隐私中主要分为局部敏感度和全局敏感度。

对于任意函数:→R，全局敏感度为：

对于任意函数:→R，局部敏感度为：

1.4 差分隐私实现机制

拉普拉斯机制。有数据集，设函数:→R，其敏感度为Δ，那么随机算法

提供－差分隐私保护，其中Lap（）表示服从Laplace分布的随机噪声，尺度参数=Δ/。

当敏感数据不是数值的且拉普拉斯机制不适用时，可以采用另一种方法即指数机制实现。指数机制利用打分函数对每个输出进行评分，并对得分较高的输出分配指数级更大的概率。选择的实用函数应具有较低的灵敏度。

指数机制。对于数据库，（,）为打分函数，设随机算法的输入为数据集，输出为实体对象，且∈Range，R表示算法从Range中选择并输出R的概率，若：

则称算法提供ε－差分隐私保护，Δ为函数（，）的敏感度。

1.5 组合机制

给定个算法，…，M，每个均满足ε-差分隐私，对于同一个数据集，依次执行，…，M，由这些算法组成的组合算法满足（∑ε）差分隐私。

给定个算法，…，M，每个都满足ε-差分隐私，对于个互斥的数据集，…，D，分别执行算法，…，M，则由这些算法组成的组合算法满足（max{ε}）差分隐私。

2 算法设计

直方图中包含的个单位桶代表了个独立的范围计数查询。而对于相邻数据集的直方图H和H'，H的某个单元桶频数为，H'的某个单元桶频数则为'，根据相邻数据集定义可得|-|=1，所以在直方图中每个单元桶的敏感度Δ=1。因此，只需要向直方图的每个桶中加入部分服从拉普拉斯分布的噪声就可以满足差分隐私的需求。

输入：原始数据集H，隐私预算

输出：满足差分隐私的直方图H'

将数据集H按照不同阶段分为个桶（H={H，H，H，…，H}）。

For=1 to：

使用拉普拉斯机制对H加噪生成H'，敏感度Δ=1，=隐私预算，将H'写入H'数据集中。

得到满足差分隐私的直方图H'={H',H',H'，…，H'}。

3 实例分析

3.1 实验设置

实验所用硬件环境为11th Gen Intel（R）Core（TM）i5 2.40GHz，16 GB内存，使用Python编程语言实现，操作系统平台为Windows10，实验采用真实数据集adult和employee salary，均被广泛应用于数据发布。adult数据集共32560条数据，15个属性，这里采用age属性构建直方图，employee salary共244条记录，三个属性值，采用其中的salary属性构建直方图。这两个属性均为连续类型，实验中将每个属性均划分为5个桶，选择不同的隐私预算分别对原始直方图进行加噪，最终可以得到一个扰动的直方图。

3.2 实验分析

图1为在Adult数据集age属性上分成的五个子集，并在每个子集上添加一个服从拉普拉斯分布的噪声，可以看出在添加了噪声的情况下直方图的桶高发生了变化，也就是该查询范围的统计数值发生了改变，然而在此数据集上噪声的影响并不是很明显。观察图2中Employee Salary数据集中salary属性的扰动直方图，可以直观地发现噪声在此数据集上的作用比较明显。同时能够观察该数据集中扰动结果在不同隐私预算的作用下也是不同的，在隐私预算等于0.05时扰动直方图与原始直方图的差别最大，隐私预算等于5时，加噪的直方图与原始直方图的差别比较小。

图1 关于Adult数据集age属性的扰动直方图

图2 关于Employee Salary数据集salary属性的扰动直方图

本文采用KLD（kullback-leibler divergence）来衡量与原始直方图的误差，由于每次的实验结果具有随机性，所以本次实验数据取50次实验结果的平均值。如表2所示，在隐私预算相同的情况下Adult数据集的KLD要小于Employee Salary数据集。而在同一数据集上，KLD会随着隐私预算的增加而减小。