面向位置数据划分的差分隐私保护研究进展.pdf

收稿日期:修回日期:基金项目:科技创新 重大项目()教育部 年第二批产学合作协同育人项目()安徽信息工程学院青年科研基金资助项目()作者简介:韩慧慧()女助教硕士主要研究方向为信息安全:.:/面向位置数据划分的差分隐私保护研究进展韩慧慧 刘晴晴 吴锦华 孟令兵(安徽信息工程学院 计算机与软件工程学院安徽 芜湖)摘要:移动定位技术的发展促进了位置数据的收集和共享导致位置数据集隐私面临泄露风险而现有的隐私保护技术难以抵抗攻击者背景知识的攻击 差分隐私作为一种严格可证明的隐私保护模型可以有效防止任意背景知识攻击 对差分隐私基础理论以及它在位置数据划分的应用进行综述重点阐述了差分隐私预算分配策略和位置数据划分方法并对其方法进行分析总结 在现有技术对比分析的基础上指出了需要进一步深入研究的方向关键词:差分隐私位置数据隐私保护数据划分中图分类号:.文献标识码:文章编号:().引言移动互联网和全球定位技术促进了位置服务发展产生大量的位置信息 此类信息可用于各种数据挖掘任务帮助企业提升用户体验、调整营销策略、为新设施选择最佳位置等 然而这些位置数据中包含敏感信息如果服务提供商直接与研究人员或企业共享数据集轻则泄露用户的家庭住址、兴趣爱好等敏感信息重则威胁用户人身安全 因此如何在享受位置服务带来便利的同时保护自己的位置隐私不被泄露有着重要意义现有的位置隐私保护技术如加密技术、假位置技术、空间匿名技术等大多缺乏严密的隐私概念攻击者从中获取用户的敏感信息可能只需要很少的背景知识 与之相比差分隐私是一种严格可证明和安全控制的方法可以有效地保护用户的隐私 自从它在数据库领域中被提出后就被迅速广泛地引入到其他数据应用领域如推荐系统中应用差分隐私实现个性化推荐信息服务、知识图谱中引入差分隐私以提高嵌入的效用和社第 卷第 期 年 月信 息 工 程 大 学 学 报 .交网络在差分隐私保护下以提高图数据的可用性等近年来差分隐私技术取得了大量研究成果本文在这些最新研究进展的基础上首先介绍差分隐私基本概念、实现机制和基本性质并对差分隐私保护中衡量数据可用性的方法进行总结然后重点阐述差分隐私预算的最新分配方法和位置数据划分方法最后总结和展望基于差分隐私的位置隐私保护面临的主要问题 差分隐私保护模型.差分隐私的定义差分隐私通过加入噪声使数据失真使攻击者无法辨别真实数据是一种严格可证明和定量表示的攻击模型 扰动后的数据保持其数据挖掘功能的同时确保数据隐私受到保护定义 相邻数据集 对于任意两个属性结构相同的数据集 和 如果它们之间至多相差一条数据记录则 和 是相邻数据集记为定义 差分隐私 如果 是一个随机算法是 所有可能输出的结果集是 的子集 对于给定的任意相邻数据集 和 如果算法 满足如式()则称算法 满足 差分隐私保护:()()()()式中 称为差分隐私预算它是一个常数只要它足够小就很难用相同的输出 判断查询函数是否在 或 上起作用 一般情况下 时才有意义且越小越能保护隐私但相对来说数据可用性要差些 因此信息安全性和数据可用性两个方面都需要在选取 值时加以考虑差分隐私通过添加噪声来实现隐私保护所需噪声量取决于查询函数的全局灵敏度定义 全局敏感度 假设有 个查询函数:对于任意两个相邻的数据集 和 的全局敏感度如式()所示:()()()式中:表示输出结果最大改变值它是由于删除或添加数据集中的任意数据记录而导致查询结果的变化由查询函数本身决定不依赖于输入的数据集()()是 在数据集 和 上的曼哈顿距离或者称为 阶范数距离.差分隐私的实现机制差分隐私中常用的隐私保护机制是拉普拉斯机制和指数机制分别以输出数值结果和非数值结果为主定理 拉普拉斯机制 对于任意函数:如果随机算法 满足式()则该算法实现 差分隐私保护:()()(/)()式中:拉普拉斯噪声的概率密度函数是()由拉普拉斯噪声引起的方差是(/)/标准方差是(/)/是位置参数 是尺度参数通常/从定理 可知拉普拉斯机制通过引入拉普拉斯噪声加入到查询结果中实现差分隐私保护其中 和 直接影响添加的噪声大小因此如何选择查询函数和隐私预算策略是该机制的关键技术定理 指数机制 对于任意函数:()如果随机算法 以正比于()概率选择输出则说明算法 满足 差分隐私保护其中()为可用性函数它为每个输出 分配一个实值的可用性分数打分越高被选择输出的概率则越大而 为函数()的敏感度从定理 可知指数机制将更高概率分配给更高效用分数的输出这样最终的输出就会接近最优值 因此如何设计可用性函数是指数机制的关键.差分隐私的基本性质串行组合和并行组合是差分隐私的两个基本性质其中串行组合性质是指将各算法序列按顺序组合起来为序列组合算法提供差分隐私保护所提供的隐私保护水平为全部隐私预算的累积并行组合性质是指每个算法序列在不相交的数据集上执行隐私预算不会累积算法序列中隐私预算最大的那个决定了提供的隐私保护水平性质 串行组合 给定一系列关于任意数据集 的差分隐私算法()()()()任意两个算法相互独立且每个()算法均满足 差分隐私这些算法组合起来满足 差分隐私如图 所示 信 息 工 程 大 学 学 报 年图 串行组合解析图 性质 并行组合 将任意一个数据集 划分成 个互不相交的子集 设有任意两个相互独立的算法 每个差分隐私算法()()()()均能满足 差分隐私这些算法组合在一起满足差分隐私保护如图 所示图 并行组合解析图 在证明算法是否满足差分隐私保护和隐私预算分配是否合理的情况下上述两个性质在差分隐私中发挥着重要作用.差分隐私保护中衡量数据可用性的方法差分隐私技术进行保护后数据的可用性取决于 值 值越大查询结果中加入的噪声越小数据的可用性就越高但数据的隐私安全性越差反之亦然即数据的可用性与安全性是矛盾的 因此隐私保护的目的是确保较高的隐私保护水平同时提供极其准确的查询结果 为了平衡数据的安全性和实用性如何在耗尽 之前使用最小预算来满足最大数量的查询或如何在给定 的情况下提高查询的准确性都是需要考虑的 现有研究中并没有给出特定的差分隐私数据可用性衡量标准而是通常采用相对误差、绝对误差、方差等来评估差分隐私算法的合理性其中最常用的采用相对误差来衡量假设数据集 是在 上进行的任意查询函数()表示对 的真实结果()表示对 加入噪声后的扰动结果相对误差的定义为:()()()/()其中为了避免()的情况设置一个参数 它的值由用户根据采用的索引结构设置 其相对误差越小越能准确得到查询结果绝对误差的定义为:()()()其绝对误差越大扰动后的查询结果越偏离真实的结果方差是查询准确性的有力指标该方差一般用所选用的差分隐私机制的噪声方差表示 通常查询精度越大方差越小反之则相反 位置数据差分隐私保护差分隐私保护技术的实现主要考虑两个问题一是如何使设计的算法能够满足差分隐私而满足差分隐私的关键技术是隐私预算分配二是如何降低噪声误差提高数据可用性而选择合适的数据划分结构是降低噪声误差的重要途径 因此本文重点介绍差分隐私的预算分配和支持数据划分的索引结构.隐私预算分配差分隐私是一种严格的隐私保护模型独立于任何攻击者的背景知识但其缺点在于每次查询都会消耗隐私预算 如果分配给某个查询的隐私预算越大它的查询结果越准确然而这会增加隐私预算并在查询处理中产生限制 反之如果分配给每个查询的隐私预算过小则添加的噪声会非常大从而导致查询结果的准确性和数据效用很差因此实现差分隐私的关键在于如何合理分配隐私预算 本文分析并总结差分隐私预算分配策略的研究成果将差分隐私分配策略大致分为 类:统 第 期韩慧慧等:面向位置数据划分的差分隐私保护研究进展一策略分配、非统一策略分配和混合策略分配它们之间的分类比较如表 所示表 不同隐私预算分配策略分类比较分配策略方式优点不足统一分配策略均匀预算分配操作简单部分隐私预算被浪费查询结果不太准确非统一分配策略几何预算分配查询精确度较高添加的噪声受到树高度影响自适应预算分配自适应分配隐私预算较灵活只能适应特定的数据应用斐波那契预算分配查询精确度高主要适用于树结构下层节点的计数查询动态预算分配节省隐私预算只适用于近期预测混合分配策略统一和非统一分配策略组合只对敏感数据进行扰动数据可用性好隐私预算重复分配.统一分配策略统一策略分配也称为均匀预算分配它是最早出现的隐私预算分配策略其主要思想是将给定的总的隐私预算平均分成 份这是最简单的一种常用方法但是它会导致一部分隐私预算被浪费一般需要进行后续处理来进一步提高查询精确度其具体描述如算法 所示算法 隐私预算统一分配策略算法输入:原始数据集 给定的隐私预算 输出:扰动后的数据.:/.(/)(/)(/).().输出.非统一分配策略地理空间的不同子区域可能需要不同量的隐私保护如果针对不同子区域再使用统一分配策略来分配隐私预算将导致具有低隐私保护要求的子区域的错误度量明显增加或者具有高隐私保护要求的子区域的隐私度量大幅减少这些促进了隐私预算非统一分配策略的产生 非统一预算分配策略的主要思想是根据用户对隐私安全和数据可用性要求将给定的总的隐私预算划分成大小不同份进行分配其具体描述如算法 所示算法 隐私预算非统一分配策略算法输入:原始数据集 给定的隐私预算 输出:扰动后的数据.:其中.(/)(/)(/).输出 非统一预算分配策略又主要包含几何预算分配、自适应预算分配、动态预算分配和斐波那契预算分配等 几何预算分配是通过预测节点的高度把剩余的隐私预算分配给当前节点的子树从父节点到子节点隐私预算以 的指数增加从而使较少的噪声添加到叶子节点的计数中文献认为对于树结构这种分配方式能使效果达到最佳 但是文献认为当实际查询中包含很少节点时这种方式并不是最佳的为了解决这个问题提出一种斐波那契分配策略将总的隐私预算根据斐波那契分配数列特征分配给四叉树结构的每一层但这种方法主要适用于树结构下层节点的计数查询极端情况下会导致几乎所有隐私预算都归叶子节点所有从而破坏噪声和真实计数之间的平衡 为了平衡噪声和真实计数文献利用基于第 次谐波数划分隐私预算让更多的隐私预算处理更深层次的节点也就是越靠近根节点的内部节点所分配的隐私预算份额就越小随着用户对隐私安全和数据可用性有更多要求逐渐出现自适应预算分配和动态预算分配 文献设计了一种自适应采样机制和自适应预算分配机制根据数据变化动态调整采样率并将适当比例的隐私预算分配给任何连续的 时间戳窗口内的采样点以便使每个采样点自适应地分配预算的一部分 文献提出了一种基于区块链的数据共享方法通过利用区块链自主智能合约存储不断检查和验证剩余隐私预算是否足以执行任务并据此更新隐私预算进行自适应性的隐私预算分配 然而这两种不同方式的自适应预算分配方式适用于特定的数据应用 为了更好地节省隐私预算文献提出一种动态预算分配根据移动平均策略来分配隐私预算如果之前发布的噪声数据与当前时间戳上的真实统计数据接近则重新发布它从而节省了当前时间戳上的隐私预算但是该方法只能用于近期预测.混合分配策略混合分配策略常在满足差分隐私的频繁 信 息 工 程 大 学 学 报 年模式数据挖掘中出现它的主要思想是将给定的总的隐私预算分成两部分一部分通过指数机制来选择频繁模式另一部分通过拉普拉斯机制将噪声加入到选出的频繁模式真实计数中以满足差分隐私保护其具体描述如算法 所示算法 隐私预算混合分配策略算法输入:原始数据集 给定的隐私预算 输出:扰动后的数据.(/)(/)(/).输出.数据划分方法近年来如何设计支持数据划分的索引结构并基于此索引结构来保护隐私数据从而提高数据的效用和查询的准确性已成为差分隐私保护的研究热点 差分隐私中经常使用的划分结构有网格结构和树结构两种.基于网格结构基于网格结构的划分方法需要选择合适的划分粒度保持噪声误差和均匀假设误差之间的平衡噪声误差是由于数据区域划分后向每个单元格添加噪声引起的一般情况下数据区域划分粒度越细查询区域中包含的单元格越多所产生的噪声误差就越大 均匀假设误差是由于需要假设数据点是均匀分布的并估计查询矩形与查询区域相交单元中的数据点数量当数据点不均匀分布时此估计将会出现错误 一般而言任何相交单元中非均匀误差的大小取决于数据集中点的分布和划分与数据集本身性质无关 因此粒度划分得越细均匀假设误差就越小 总而言之扰动数据的可用性与划分粒度有关如何选择正确的划分粒度是基于网格结构的划分方法的关键文献首次使用划分粒度方案创建差分隐私空间数据对二维空间数据采用均匀网格模型()进行划分然后将噪声添加到每个网格单元中 该方法的划分粒度虽然被合理设置但数据分布的稀疏性没有被考虑会导致过多的噪声误差或均匀假设误差 为了解决这个问题文献进一步提出一种自适应网格模型()该模型能够根据数据稀疏程度自适应地设置划分粒度但未给出相应启发式规则来区分密集和稀疏数据 同时上述均匀网格模型和自适应网格模型均没有对划分粒度进行具体分析 因此文献在对划分粒度全面分析的基础上提出了一种新的数据域粒度划分模型()该模型可以更加准确地选择网格大小并基于此模型又提出一种均匀网格发布方法将相似的单元格合并然后将满足差分隐私要求的噪声加入合并的单元格 但是这种方法需要多个样本查询结果从而导致潜在的隐私泄露并将其划分粒度过度拟合到输入数据集 为了解决这个问题文献 提 出 了 一 种 偏 斜 感 知 网 格 划 分 方 法()它利用热点的概念通过对每个热点区域布置一个均匀的网格进一步优化错误并将热点和均匀网格组合把整个空间域划分为一组更容忍偏斜的子区域、和 这 种方法对比分析如表 所示 表 中分割粒度公式中的参数分别为:表示数据集的大小 表示分配的总的隐私预算 是一个依赖于数据集而定的小常数表示单元格中的噪声计数 是大于 小于 的常数它决定了如何在两个级别之间分配隐私预算表示相对误差与面积之间的比例系数 和 分别表示数据集域的宽度和长度表 基于网格结构划分的不同方法对比分析主要方法分割粒度/优点缺点 方法/可以合理地设置划分粒度没有考虑数据分布的稀疏性 方法(./)()/划分粒度按数据稀疏自适应设置未给出相应启发式规则来区分密集和稀疏数据 方法/更加准确地选择网格大小划分粒度过度拟合到输入数据集 方法/关注输入数据集的域大小同时当数据集分布偏斜时可以避免产生无意义的单元格对于不包含任何热点的子区域无法准确估计对象的数量.基于树结构基于树结构的划分又可以分为数据无关划分和数据相关划分 如果不考虑数据分布的情况下划分空间区域则称为数据无关划分 数据相关划 第 期韩慧慧等:面向位置数据划分的差分隐私保护研究进展分则是以数据分布为依据对空间区域进行划分.数据相关划分数据相关划分依赖于数据分布情况节点的层次划分基于输入主要为了更好地捕捉数据分布文献提出的 树是数据相关划分的早期代表这种方法先用网格来划分数据然后把噪声加入到每个网格单元再使用 树进行索引树中的节点沿某个维度递归地分裂 然而该算法仅在数据分布均匀时才有效 为了减少非均匀性误差文献提出类似的方法树中的节点沿着分区维度的中位数分割节点 然而就数据效用而言文献认为这种分层 树算法被证明不如 和 算法提出自适应分区策略在密集区域上采用较细的粒度进行分区同时在稀疏区域上采用较粗的粒度进行分区然后对数据库的计数查询进行两级分区回答 文献提出基于 树的差分隐私二维空间数据划分发布方法使用二次和的误差衡量当前网格单元的均匀性并在 方法的两阶段划分后启发式地合并具有相似信息的相邻网格单元 但是该方法在比较合并过程需要遍历所有网格单元的分割边界计算复杂度较高 为了平衡噪声误差和非均匀性误差文献提出基于同质性分区构建的索引结构将一个节点在一个分割维度上分成两个子区域这些子区域通过树的连续级别交替根节点覆盖整个数据空间以使每个结果分区内的数据密度是同质的但是这种方法的噪声大小受树深度影响 针对不同数据相关的划分方法分析划分的关键在于确定分割线.数据无关划分数据无关划分的特征是它们的结构是预先定义好的只依赖于属性域 其中数据无关的划分方法中四叉树因其查询效率高而被广泛应用于空间数据查询 文献采用完全四叉树自上而下地分解二维空间数据并使用几何预算分配策略对隐私预算进行分配再对噪声通过最小二乘法无偏估计进行后处理该方法降低了噪声误差提高了查询精度但是它没有考虑当树深度相对较大和原始数据分布不均匀的情况分别会导致最终查询精度很低和均匀假设误差相对较高 文献使用四叉树划分动态空间数据以启发式阈值判断各单元经过划分后是否稀疏或密集 如果该单元还是密集则将它继续连续划分 但是这种方法的缺点类似于文献的不足利用树深度控制噪声值 与前两种方法相比 文献 提出的 算法它采用完全四叉树进行空间分解消除了对树深度的依赖通过节点计数的偏移值对噪声进行降低然后使用噪声常数去判定是否划分子域 同时该方法使用稀疏矢量技术对节点划分阈值进行计算 文献将直方图重新组织转化成二叉树结构然后利用一致性约束来改变噪声输出该方法可以支持任意范围查询但是主要依靠后置处理来实现查询精度 与文献不同文献利用小波变换方法将直方图转换为完整的二叉树以减少错误并提供远程查询但是这种方法构建的树深度会影响查询敏感度从而影响查询精度 为了克服上述树深度对噪声值的影响文献提出一种新的基于四叉树空间分解算法使用随机采样算法来获取足够的空间数据以平衡大规模空间数据和噪声量并利用稀疏矢量技术来控制何时对树节点进行分区但是该方法主要用来处理偏斜数据 结束语本文结合对隐私预算分配策略和数据划分方法面临的种种困难提出以下需要继续深入研究的地方)个性化隐私预算分配策略 合适的隐私预算分配策略既决定隐私预算是否有效分配也影响数据的可用性 但是现有的统一分配策略、非统一分配策略和混合分配策略均只能适用于特定的空间数据应用 因此能够设计出一种新的隐私预算策略它能够根据用户对数据隐私保护的个性化需求来灵活分配隐私预算具有重要意义)选择合适的位置数据划分结构 差分隐私模型常采用网格结构和树结构对位置数据进行空间区域划分而现有的基于树结构的数据划分方法设置合适的树深度来控制噪声存在着很大的难度以及现有的基于网格结构的划分方法选择最优的划分粒度平衡噪声误差和非均匀性误差却非常困难 因此如何选择合适的位置数据划分结构以更好地控制噪声的添加是一个很大的挑战参考文献:./.:./.信 息 工 程 大 学 学 报 年 .:.():.:.:.:.林子杰张宇轩刘文芬等.点差分隐私下基于度序列的图生成模型.信息工程大学学报():.:.:.田丰吴振强鲁来凤等.面向轨迹数据发布的个性化差分隐私保护机制.计算机学报():./:.:.:.():.:.:.:.:.():.():.():.():.():.卢国庆张啸剑丁丽萍等.差分隐私下的一种频繁序列模式挖掘方法.计算机研究与发展():.():.():.:.黄泗勇陈婷婷卢清等.基于 树的差分隐私二维空间数据划分发布方法.山东大学学报(工学版)():.:.:.第 期韩慧慧等:面向位置数据划分的差分隐私保护研究进展.:.:.:.:.():.():.():.(编辑:冯 春)(上接第 页).:.:.:.:/.().:./.刘微宁维奇.基于迁移学习的人脸口罩穿戴识别研究及应用.吉林师范大学学报(自然科学版)():.:.:.:./.().:./.张爱民.优化卷积神经网络在复杂验证码图片识别中的应用.信息工程大学学报():.:/.().:./.:/.().:./.(编辑:李志豪)信 息 工 程 大 学 学 报 年