近年来,随着信息技术的发展及物联网技术的兴起,出现了越来越多的持续监控应用场景,如智能交通实时监控、疾病实时监控、智能基础设施应用等.在这些场景中,如何对参与者持续分享的数据进行隐私保护面临重大挑战.差分隐私是一种严格和可证明的隐私定义,早期差分隐私研究大都基于一个大规模、静态的数据集做一次性的计算和发布.而持续监控下差分隐私保护需对动态数据做持续计算和发布.目前,持续监控下差分隐私保护是差分隐私领域新的研究热点之一.对持续监控下差分隐私保护的已有研究成果进行总结.首先,对该场景下差分隐私保护模型进行阐述;然后,重点介绍了持续监控下满足event级、user级和w-event级隐私保护的实现方案.在对已有研究成果深入对比分析的基础上,指出了持续监控下差分隐私保护的未来研究方向.
With the development of information technologies and Internet of things (IoT) technologies, there are more and more scenarios under continual monitoring, such as transportation monitoring, disease monitoring, smart infrastructure etc. In these scenarios, how to protect the privacy of continuous sharing data is facing major challenges. Differential privacy is arigorous and provable privacy definition. Earlier research on differential privacy has focused on "one-shot" release on a static dataset. However, differential privacy under continual observation focuses on the continuous computationon the dynamic dataset. Now it has become one of the research hotspots. This study surveys the state-of-the-art techniqueson differential privacy under continual observation, and focuses on summarizing existing schemes that provide event-levelprivacy, user-levelprivacy, and w-event privacy. Following a comprehensive comparison and analysis of existing techniques, further research prospectsare put forward.
随着信息技术的发展及物联网技术的兴起, 出现了越来越多的持续监控应用场景, 如健康管理、交通管理、智能建筑、智能基础设施与应急响应等.在这些场景中, 持续监控的成功实施依赖于对参与者持续共享的个体信息或大量密集传感器(例如照相机、手机、WiFi接入点、信标)传输的流式数据进行实时监控和分析.由于持续监控下持续共享的数据中包含大量个体隐私数据, 如果不对其进行隐私保护, 会存在隐私泄露的风险.用户对隐私泄露的顾虑会限制参与者分享个体信息的意愿, 从而阻碍持续监控应用的发展[
https://en.wikipedia.org/wiki/General_Data_Protection_Regulation)中, 明确了规定了用户对个人信息的知情权及被遗忘权; 2017年, 我国在《中华人民共和国网络安全法》(http://www.spp.gov.cn/xwfbh/wsfbt/201705/t20170509190088.shtml)中, 加强了对个人信息保护的政策规定.很多信息交流平台及各种APP, 如Facebook、Twitter、美团、京东, 都制定并发布了自己的用户隐私保护政策.除制定相关法律政策, 隐私保护问题的相关技术研究也逐渐受到重视.]]>
差分隐私是一种定义极为严格的隐私保护模型, 相比于近年来
[
传统差分隐私场景下, 往往根据一次参与事件对发布结果的最大影响(敏感度)添加噪声.以简单计数任务为例, 一次事件的参与与否所带来的发布结果敏感度为1, 添加
持续监控下差分隐私保护研究具有实际的应用背景和重要的研究意义.目前已有一些持续监控下差分隐私保护的研究成果.本文综述持续监控下差分隐私保护的最新研究进展和研究方向:一方面对持续监控下差分隐私的定义、实现机制和持续监控方案的评估标准进行总结; 另一方面, 对当前持续监控下差分隐私保护的已有研究方案进行总结分析, 其中着重总结满足event级、user级和w-event级隐私保护的实现方案.最后, 提出持续监控下差分隐私保护的未来研究展望.
本文第1节总结持续监控下差分隐私保护模型.第2节总结主要研究方案分类.第3节~第5节分别对持续监控下差分隐私保护的现有研究方案进行概括, 并对研究方法进行对比和分析.第6节提出持续监控下差分隐私保护的未来研究展望.最后, 第7节总结全文.
本节主要对持续监控下的差分隐私定义、实现机制及隐私保护方案评估标准等几个方面进行总结.
设数据集
隐私预算参数
直观地讲, 持续监控下的数据发布[
在上节传统差分隐私定义中, 差分隐私要保证基于邻居数据集上统计结果的概率比值不大于
持续监控场景示例
Example of continual monitoring
假设
结合具体问题的监控事件, 持续监控下差分隐私保护需要对基于监控事件数据流的统计分析做差分隐私保护处理.假设用
Event级邻居数据流:在持续监控下, 如果存在
Event级差分隐私保护能保证在持续监控生命期中, 用户的一次事件对整个监控结果影响受隐私预算
User级邻居数据流:在持续监控下, 如果存在
User级差分隐私保护是对持续监控生命期中某用户的所有参与事件对整个监控结果的影响进行控制, 也就是对持续发布统计结果的隐私泄露风险进行了限制.
w-event级邻居数据流:给定一个正整数
w-event级隐私可以看作是user级隐私的拓展, 它实现在任意
在上述的3种定义中, event级所提供的隐私保护强度最小, user级隐私保护强度最大, 而w-event级隐私保护是上述两种方案的折衷.隐私预算参数
噪声机制是实现差分隐私保护的主要技术, 常用的噪声添加机制分别为拉普拉斯机制[
称为函数
其中,
拉普拉斯机制只适合于数值型输出的查询函数.许多应用中查询输出为非数值型.对此, McSherry等人提出了指数机制.其实现核心是设计打分函数
其中,
差分隐私保护具有两个组合性质:序列组合性和并行组合性, 在持续监控下仍然适用.
序列组合性表示对同一数据集多个差分隐私保护算法的序列组合算法, 所提供的保护水平为全部隐私预算之和.并行组合性表示对不同数据集保护的多个差分隐私保护算法的组合算法, 所提供的保护水平为算法中的最低的保护水平, 也就是隐私预算的最大值.
满足差分隐私保护的方案在实现隐私保护同时, 也要兼顾发布结果的可用性.因此, 方案的评估包含以下两个方面.
(1) 隐私保护评估:差分隐私处理核心是隐私预算分配和敏感度计算; 隐私预算
(2) 算法结果误差:为评估方案发布结果的可用性, 往往计算真实结果与经差分隐私处理后的结果之间的误差.根据持续监控下问题的不同, 误差采用的衡量方法往往不同.如:简单聚集统计发布问题中, 常对发布结果误差上界进行证明, 并在实验评估中采用相对误差、绝对误差等度量标准; 而其他问题会根据自身问题特点定义不同的标准, 如轨迹保护中, 采用JS散度、F-Score等可用性衡量标准.
持续监控下差分隐私保护研究对推动智能信息技术的发展具有重要的意义, 其隐私保护问题也是急需解决的问题.本文将现有持续监控下差分隐私保护方案分为3类, 分别为持续监控下event级别保护方案、持续监控下user级别保护方案和持续监控下w-event级别保护方案.其中:持续监控下event级别差分隐私保护方案主要围绕单值计数和持续发布、直方图持续发布、heavy hitter持续监控和位置发布等持续监控问题, 针对如何降低持续发布的高敏感度提出相应的解决方案; 持续监控下user级别和w-event级别的保护方案主要围绕简单聚集信息持续发布、分布式数据流阈值函数持续监控、集值对更新发布和轨迹发布问题, 针对如何提高时序上隐私预算的利用率, 同时降低发布任务的高敏感度提出相应的解决方案.每个分类对应的方案示例见
持续监控下差分隐私保护方案分类
Existing research on differential privacyunder continual observation
主要方案分类 | 方案示例 |
持续监控下event级隐私保护方案 | Two-level[ |
持续监控下user级隐私保护方案 | DFT[ |
持续监控下w-event级隐私保护方案 | BA[ |
Event-级别持续监控隐私保护主要基于count计数的发布任务进行研究, 主要包括单值计数和的持续监控保护、直方图持续发布的隐私保护、heavy hitter和位置信息发布等特定任务的持续监控保护.
目前, 大部分event-级别的持续监控保护研究都是基于单值计数和的持续监控保护问题, 如
单值计数和的持续发布
Continual release of the running sum
单值计数和问题在很多应用场景上都可适用, 如特定位置的交通实时监控、特定网页的用户点击行为实时监控、传感器网络中某IP地址访问的持续监控、智能基础设施的持续监控、疾病控制中心对患某种疾病人数的持续监控、满足特定谓词条件的持续查询等等.
● 方案1
方案1是文献[
● 方案2
方案2则是差分隐私实现机制[
● Two-level方案[
为降低发布结果误差对
Two-level方案示例
Example of Two-level
由于每个时刻
上述3种基本方案的发布结果误差对数据流长度
Tree Counter方案示例[
Example of Tree Counter[
对任意时刻
针对Tree Counter第1个缺点, 文献[
虽然上述方案解决了数据流长度受限问题, 但还有以下缺点:(1)由于发布结果包含噪声, 出现了相邻时刻发布结果不满足实际统计约束的不一致问题; (2)面向数据流的数据统计涉及到中间统计值的保存, 如果中间值被攻击者捕获, 则不能提供有力的保护.针对缺点(1), 文献[
在很多实时监控的应用场景中, 往往近期发生的事件对监控更有意义, 而发生时间较远的事件对监控价值较低.针对这个问题, 文献[
其中,
基本方案和二叉树方案中没有考虑数据流自身特点对发布结果的影响.文献[
Partition自适应分区示例
Example of adaptive partition
在发布某个时刻
文献[
PeGaSus过程图[
Process of PeGaSus[
Pertuber用来对每个时刻
PeGaSus与Partition分区策略不同点在于:(1) Partition是将数据流分为一组连续分区, 每个分区内的计数和基本相同; (2)而PeGaSus分区的思想是将计数值相似的的时间点分到一个分区, 不同分区间计数和可能变化较大; (3) Partition基于分区的计数和做噪声处理, 而PeGaSus则是对每个时间点的计数值做噪声处理;(4) PeGaSus采用了偏差函数帮助Grouper分区, 而Partition是通过提前设定的阈值进行分区; (5) Partition只针对单值计数和发布问题做隐私保护, 但PeGaSus面向的是多种查询任务类型, 如多目标持续查询和多时间跨度的持续查询等.
PeGaSus方案中, 因其支持多种查询类型, 提出对具有层次关系的查询任务关系进一步降低查询任务的敏感度, 提高发布结果的可用性.文献[
● SampleDP是针对查询任务的步长满足一定约束条件(长步长是短步长的整数倍)的情况下, 采用动态规划算法找出能使添加噪声量最小的步长组合;
● 而SampleEMD是将第1种方案扩展到更一般的情况:采用EMD相似性计算方法来选取与原有步长集分布相似的抽样步长集, 达到降低噪声、提高查询结果可用性的目的.
直方图是一种直观的数据分布表示形式, 它按照某属性或属性集将数据集信息划分成不相交的桶, 每个桶内有一个统计数字表示其特征.直方图的持续发布是基于时间序列上的动态数据, 持续发布直方图统计信息.
持续监控下直方图发布示例
Example of histogram publication under continual monitoring
文献[
假设用
RetroGroup与PeGaSus分区有些相似, 都是将数据变化不大的时间序列分为一组; 但RetroGroup是基于分组平均值做噪声处理, 而PeGaSus是基于每个时间点值做噪声处理, 而后针对特定查询任务进行分组平滑处理.
Heavy hitter的持续监控是指对数据流中的元素及其频数进行统计, 实时发布超出阈值的元素及其频数, 即heavy hitter.在该问题中, heavy hitter元素及其频数都是需要保护的隐私.文献[
PMG方案基于未做隐私保护的面向数据流中heavy hitter统计的算法MG[
基于PMG, PCC方案按照时间宽度
根据二叉树中参与统计的节点创建时间, 所有节点可以分为
PMG方案示例(
Example of PMG (
PDCH-LU[
文献[
文献[
文献[
文献[
文献[
时序关联关系示例[
Example of temporal correlations[
基于上述信息, 方案中对时序数据相关性所造成的隐私泄露量给出了定量化的计算公式, 即为所有用户中最大的隐私泄露风险值.该隐私泄露量的计算包含前向转移关系隐私泄露的计算和后向转移关系隐私泄露的计算, 为了提高计算效率, 方案将隐私泄露量的求解问题转换为一个线性分式规划问题, 并提出了多项式时间内的求解算法.
上述方案都是考虑了时序数据相关性的隐私保护方案.目前, 关联数据发布的隐私保护研究提出了新的隐私保护模型Pufferfish[
总结来说, 持续监控下event级隐私保护方案核心都是围绕如何提高时序数据发布的可用性问题进行研究, 其目标都是满足event级
Event级别持续监控保护方案对比
Comparation of schemes on event-level privacy under continual monitoring
算法 | 主要优点 | 主要缺点 | 保护等级 | 算法误差 |
方案1[ |
实现简单, 没有中间值的存储 | 算法可用性差, 只能处理定长数据流, 对 |
event级 | |
方案2[ |
实现简单, 可以实现无限长数据流处理 | 算法可用性较差, 需存储中间值, 对 |
event级 | |
Two-level[ |
采用分区提高可用性, 可以实现无限长数据流处理 | 算法可用性较差, 需存储中间分组节点统计值 | event级 | |
Tree Counter[ |
采用二叉树结构提高了算法的可用性 | 只能处理定长数据流, 需存储二叉树内部节点 |
event级 | |
Hybrid[ |
采用混合策略提高算法可用性, 能处理无限长数据流, 具有一致性处理 | 需存储中间节点分组计数值和 |
event级 | |
Decayed Sum[ |
离当前时间越近的数据占的统计比重越大, 采用二叉树结构提高可用性 | 只适用于单值计数和持续发布问题, 不能适用于复杂统计分析发布 | event级 | |
Partition[ |
采用自适应分区进一步提高了算法可用性, 能处理无限长数据流 | 只适用于稀疏数据流的发布统计 | event级 | |
PeGaSus[ |
(分区+平滑技术+查询任务关系)策略提高了可用性, 能处理无限长数据流 | 数据变化较快情况下, 可用性提高不明显 | event级 | |
SampleEMD[ |
利用查询任务关系提高发布可用性 | 只适合多种查询任务步长之间具有关系的发布分析 | event级 | 无分析 |
RetroGroup[ |
采用相似性计算和回溯分组, 降低了发布敏感度 | 统计值变化较快情况下可用性提高不明显 | event级 | 无分析 |
PDCH-LU[ |
能处理无限长数据流, 适用于分布式环境 | 只适用于heavy hitter特定问题发布 | event级 | 无分析 |
文献[ |
能在增量更新下处理无限长数据流, 能实现pan-privacy | 只适用于简单聚集统计问题 | event级 | 无分析 |
文献[ |
能在全动态更新下处理无限长数据流, 实现pan-privacy | 只适用于简单聚集统计问题 | event级 | 无分析 |
PIM[ |
利用数据相关性提高隐私保护强度 | 计算敏感度耗费时间 | event级 | 无分析 |
TPL[ |
对数据相关性所造成的隐私泄露进行定量分析 | 预处理过程耗费时间 | event级 | 无分析 |
(1) 从持续监控生命期上看, 所有event级别持续监控保护方案中, 不需要在时序上进行隐私预算分配.但由于时序发布任务的高敏感度, 数据流的持续监控保护长度受限.如在方案1和Tree Counter中, 必须根据数据流长度
(2) 从降低敏感度技术来看, event发布方案主要采用分区技术或二叉树技术来降低发布敏感度.其中, 基于分区的方案有Two-level, Hybrid, Partition, PeGaSus, RetroGroup.虽然都是分区, 但是分区原则不一样: Two-level是定长分区, Hybrid是非定长分区, Partition是每个分区计数和大致相同, 而PeGaSus和RetroGroup则是将数据变化不大的连续时间分为一组.基于二叉树的方案有Tree Counter, Hybrid, Decayed Sum, PDCH-LU.所有的分区方案和二叉树方案只适用于简单计数统计的查询任务.虽然采用降低敏感度技术提高了发布结果可用性, 但随着数据流的增加, 发布结果的可用性依然会变差.如何结合特定持续发布任务设计更好的降低敏感度方案来提高发布结果的可用性, 值得进一步研究;
(3) 在PeGaSus和RetroGroup中的分区方案采用了平滑技术提高发布结果可用性, 如采用分区内平均值或中间值来对发布结果进行近似处理.分区技术是为降低时序上的噪声误差的常用技术, 如何结合更好的平滑技术提高基于分区的发布结果的可用性, 值得进一步研究;
(4) 从数据处理方式上看, 根据时序数据的处理方式, 方案分为离线处理和在线处理.所有方案都可实现实时在线处理.结合特定持续发布任务实现在线处理的event级隐私保护方案, 也值得进一步研究.
User级的持续监控保护方案主要围绕简单聚集统计信息的持续发布、分布式数据流的阈值函数持续监控、集值对的增量更新发布、轨迹数据发布等几个问题进行分析总结.
简单聚集统计指基于count、sum、average等聚集函数的信息统计.实时发布简单聚集统计信息对很多重要的数据挖掘应用具有很重要的意义.
如
简单聚集统计信息持续发布[
Contimual release of simple aggregation statistics[
基本发布方案是差分隐私实现机制[
文献[
文献[
FAST框架[
Framework of FAST[
自适应抽样机制的核心思想是:设定整个时序发布次数上限值为
滤波技术的核心思想是:建立一个状态空间模型, 根据模型预测值和观测到的噪声统计值, 采用后验估计对要发布的结果进行校正, 提高发布结果的可用性.所建立的状态空间模型包括相邻时刻统计值预测模型和噪声处理模型, 相邻时刻处理模型为
文献[
文献[
文献[
上述方案都是面向无限数据流实时发布方案, 文献[
上述所有方案是基于简单聚集函数的持续监控保护方案.在数据流的实时监控任务中, 往往存在一些复杂的统计分析任务(如阈值函数监控), 也需要对其进行隐私保护.文献[
文献[
由于统计过程中涉及到用户隐私, 需设计隐私保护方案.两个方案的核心策略都是采用Safe Zone(安全区域)局部约束技术[
上述两种方案采用Safe Zone技术与拉普拉斯机制或指数机制相结合, 不仅降低了通信量, 也延长了持续监控生命期.持续监控保护方案满足user级差分隐私保护.两个方案的缺点是只能进行有限长的持续监控, 如何实现无限长分布式数据流的持续监控保护, 依然是具有挑战性的研究问题.
针对集值的持续发布问题, 文献[
轨迹是具有时序关系的位置序列, 攻击者通过对用户位置的持续监控(轨迹的监控), 可以获取隐私信息.现有轨迹数据发布的差分隐私保护方案都是针对离线轨迹数据集, 经差分隐私保护处理后, 发布“净化版”的轨迹数据, 隐私保护级别为user级.攻击者通过监控发布的轨迹信息, 无法获得个体隐私.在该问题中, 假设所有位置总数为
文献[
了提高发布效率, 方案采用阈值剪枝策略, 尽早删除不能继续扩展的分支节点.由于噪声计数会违背一致性约束, 方案利用前缀树父子节点之间的约束关系对计数值进行了一致性处理, 进一步提高了发布结果的可用性.如果位置空间域较小, 前缀树高度较低, Perfix方案发布结果的可用性较好; 如果空间域较大, 前缀树高度增加, 被划分到同一分支的轨迹将大幅度减少, 因此造成发布结果的可用性变低.
为解决Perfix方案的问题, 文献[
Prefix和
文献[
本小节对所有user级隐私保护方案从其优缺点、监控任务类型和面向的发布任务等几个方面进行总结和对比分析(见
持续监控下user级隐私方案的对比分析
Comparation of schemes on user-level privacy under continual monitoring
算法 | 主要优点 | 主要缺点 | 保护等级 | 发布任务 |
基本方案[ |
平均分配, 隐私预算分配简单 | 噪声大, 发布结果可用性低 | user级 | 简单聚集信息发布 |
DFT[ |
基于傅里叶级数变换选取抽样点进行发布 | 计算开销大, 只能处理离线数据, 只能处理定长时序数据 | user级 | 简单聚集信息发布 |
FAST[ |
基于PID和滤波技术采样发布, 可以实时发布数据, 效率高, 算法误差小 | 需提前设定发布次数 | user级 | 简单聚集信息发布 |
CTS-DP[ |
利用滤波处理相关数据发布 | 只能处理离线数据 | user级 | 简单聚集信息发布 |
DSAT[ |
基于PID采样和相邻时刻直方图的相似性计算发布, 提高了隐私预算利用 | 只能处理离线数据和定长更新发布 | user级 | 直方图发布 |
SafeZone[ |
基于SafeZone采样发布, 降低通信量, 延长了监控保护生命期 | 持续监控生命期有限 | user级 | 阈值函数的监控 |
IncBuildTBP[ |
时序上平均分配隐私预算, 利用TBP树降低敏感度 | 只能处理离线数据, 可用性较低 | user级 | 集值对发布 |
Prefix[ |
利用前缀树, 降低敏感度压缩轨迹 | 只能处理离线数据, 轨迹需有大量相同前缀, 可用性低 | user级 | 轨迹发布 |
N-Grams[ |
利用n-gram和马尔可夫模型降低输出空间, 降低敏感度 | 只能处理离线数据, 轨迹子序列需有相同前缀, 可用性较低 | user级 | 轨迹发布 |
Cluster[ |
利用聚类降低输出空间, 降低敏感度 | 只能处理离线数据, 聚类造成信息丢失 | user级 | 轨迹发布 |
Homogeneous[ |
用同质参照系统降低输出空间, 降低敏感度 | 只能处理离线数据, 参照系统造成信息丢失 | user级 | 轨迹发布 |
Hierarchical[ |
用层次参照系统降低输出空间, 降低敏感度 | 只能处理离线数据, 参照系统造成信息丢失 | user级 | 轨迹发布 |
PTCP[ |
增加了对参照系统的隐私保护 | 只能处理离线数据, 参照系统造成信息丢失 | user级 | 轨迹发布 |
(1) 在简单聚集统计信息的持续发布方案中, 为最大化时间序列上的隐私预算利用率, 大部分方案采用抽样技术来提高发布结果的可用性, 其原理是结合时序数据的特点, 选出代表性的发布点进行发布, 降低发布次数, 增大每个发布点所分配的隐私预算.但这种方案只是延长持续监控生命期, 持续监控数据流长度依然有限.如何能实现对无限长动态数据的持续监控保护, 是需要解决的问题;
(2) 在分布式数据流持续监控保护中, 现有的持续监控保护方案为延长持续监控保护期, 采用一系列将全局监控条件转换为局部监控条件的分解技术.但这些技术的时间和空间复杂度很高, 极大降低了分布式数据流处理效率.可以对分解技术作进一步的改进处理, 如:基于凸分解或滤波技术提高分解效率; 也可以基于衰减模型的数据流处理模型设计基于隐私衰减的隐私保护方案, 实现对无限长数据流的处理;
(3) 在轨迹数据的发布问题中, 由于发布任务的输出空间太大, 对其进行隐私保护的敏感度和复杂度很高.所以现有轨迹数据的发布方案提出了各种降低输出空间, 降低发布任务敏感度的策略, 如:基于前缀树、
(4) 所有user级隐私保护方案也分为实时在线处理和离线处理两种方式.除FAST和SafeZone可以进行在线数据流的处理, 其余所有方案都为离线数据处理.同时, 大多数持续监控任务还都是基于count的简单统计, 但实际应用中往往存在一些复杂的数据分析任务.静态数据集上已有针对这些复杂分析任务的差分隐私保护研究工作[
从隐私保护强度上看, w-event隐私是介于user级隐私和event隐私之间的一种隐私保护方案, 本节对持续监控下w-event隐私保护方案进行总结和分析.
针对第4.1节中的简单聚集统计信息持续监控保护问题, 文献[
BD(隐私预算指数机制分配)和BA(隐私预算吸收)都基于上述两个基本过程实现, 不同的是窗口内每个采样点的隐私分配方案有区别.下面分别介绍两种方案的具体实现.
BD方案的特点是将
w-event隐私预算分配方案示例[
Example of budget allocation under w-event privacy[
而在BA方案中, 用于相似性计算的隐私预算分配方案与BD方案相同, 窗口内每个时间点的
文献[
本节先从主要优缺点上对持续监控下w-event隐私保护方案进行对比分析(见
持续监控下w-event隐私保护方案对比分析
Comparation of schemes on w-event privacy under continual monitoring
算法 | 主要优点 | 主要缺点 | 保护等级 | 发布问题 |
BA[ |
回收被动发布点的隐私预算用于采样点发布, 能处理无限数据流 | 有发布点因隐私预算耗尽不能发布 | w-event | 简单聚集统计 |
BD[ |
采用指数机制分配隐私预算, 能处理无限数据流 | 各抽样点隐私预算分布不均匀, 隐私预算不能充分利用 | w-event | 简单聚集统计 |
GA+MMD[ |
考虑用户的个性化的要求, 能处理无限数据流 | 各抽样点隐私预算分布不均匀, 隐私预算不能充分利用 | w-event | 简单聚集统计 |
目前, w-event隐私保护方案相对较少.上述3种方案都可以实现对无限长数据流的持续监控保护, 其保护强度介于event级别和user级别隐私之间.3种方案的实现核心都是考虑如何在
本节探讨持续监控下差分隐私保护的未来研究展望, 主要分为持续监控下面向分布式数据流的隐私保护研究、持续监控下差分隐私算法通用评价标准的研究、持续监控下关联数据发布的隐私保护研究、持续监控下面向复杂统计任务的隐私保护研究、持续监控下个性化差分隐私保护研究和持续监控下本地化差分隐私保护研究.
大数据环境下, 很多持续监控场景都是基于分布式数据流的实时处理, 如Web网页的用户点击、网络入侵检测、heavy hitter实时监控和智能基础设施的实时监控等.在这些应用中, 隐私保护问题非常重要.目前虽然已有一些分布式数据流持续监控保护方案, 如垃圾邮件关键词的持续监控、
在对持续监控下差分隐私发布方案进行评价时, 现有方案提出了不同的参数设置以及评估标准.如在面向简单聚集统计发布的持续监控保护方案中, 虽然都采用发布结果的误差上界进行评估, 却没有考虑相同的评估条件, 如采用的实验数据集是否一样, 设定的空间约束条件是否一样、算法中一些通用参数(如
现有的持续监控下隐私保护方案中, 已有一些关联数据发布的隐私保护研究.如在位置发布的event级别保护方案中考虑了时序上用户位置之间关联, 并对此进行建模, 依据模型对关联关系所造成的隐私泄露量进行分析, 降低位置持续发布任务的敏感度.在简单聚集信息发布的user级别保护方案中, 基于时序数据关联, 利用滤波技术提高了发布结果的可用性.在轨迹数据发布问题中, 基于时序上用户位置之间关系的假设前提, 降低了发布问题的敏感度.针对实际问题中数据关联关系建模, 根据模型设计持续监控下隐私保护方案.该类方案具有以下优点:一是更符合真实的应用场景; 二是能抵御攻击者具备这些关联信息的攻击, 隐私保护更强; 三是根据模型的发布往往可以降低发布问题的敏感度, 可用性更高.目前, 持续监控下该类研究工作还较少, 方案中对数据关联性的建模方法也比较单一.针对相关数据的隐私保护问题, 已有研究工作提出了面向语义的差分隐私保护模型Pufferfish和Blowfish.在持续监控场景下, 针对特定监控问题中的关联数据, 建立多样化的时序数据关联模型, 基于面向语义的差分隐私保护模型, 设计更灵活且具有语义的隐私保护方案是一个未来的研究方向.
现有的持续监控下差分隐私保护研究大都是基于count计数的简单统计和分析任务.面向复杂分析任务的持续监控保护研究不仅方案少, 发布结果可用性也有待进一步提高.实际应用场景中往往存在更多的复杂监控任务, 如频繁模式和频繁序列模式监控、持续分类和聚类监控等, 这类持续监控任务暂时没有相关研究.持续监控下面向复杂分析任务的隐私保护研究具有以下两个难题:一是复杂分析任务本身输出结果空间就比较大, 发布敏感度和复杂度比较高, 如何降低发布任务的敏感度, 提高发布结果的可用性是一个难题; 二是在时序上, 随着时间的增加, 发布结果的噪声会累积增加, 发布结果可用性逐渐变差.针对第一个难题, 可以对未作隐私保护的原始算法进行分析, 根据算法所采用的数据结构及处理过程, 计算其敏感度; 同时, 可改进相关任务在静态数据集上已有的降低敏感度技术[
在持续监控场景中, 通常参与者对自己的数据有不同的隐私要求, 用统一要求来处理所有参与者的信息, 可能对一些用户来说隐私保障太低, 而对另外一些用户又可能要求太高.因此, 如何结合用户隐私需求, 让用户定义个人的隐私级别, 是一个值得研究的问题[
目前, 持续监控下的差分隐私保护都是基于中心化差分隐私保护技术实现, 该技术的前提是数据收集者必须是可信的第三方.随着智能基础设施的普及和GPS定位技术的应用, 现有持续监控下的应用场景多为分布式的应用.在这种场景下, 数据的收集往往类似于问卷调查, 数据的管理者往往是不可信的第三方.同时, 由于分布式场景中收集的数据量特别大并且计算代价非常高, 中心化的差分隐私技术不适合这种场景.目前, 一些研究工作[
随着信息技术的发展及物联网技术的兴起, 出现了越来越多的持续监控应用场景.在这些场景中, 如何对参与者持续分享的数据进行隐私保护面临重大挑战.本文对持续监控下差分隐私保护领域已有的研究成果进行了总结, 首先介绍了持续监控下隐私保护模型, 包括不同保护级别的差分隐私模型定义、实现机制和持续监控下差分隐私保护方案的评估原则; 然后重点对event级、user级和w-event级这3种隐私保护级别的方案进行总结和分析.在对已有研究成果深入对比分析的基础上, 指出了持续监控下差分隐私保护的未来研究方向.持续监控下差分隐私保护的研究成果还较少, 仍有诸多关键问题需要进一步的研究.希望本文工作可以为持续监控下差分隐私保护的相关研究人员提供参考.
doi: 10.1145/3183713.3193571]]]>
doi: 10.1145/3294052.3322188]]]>
doi: 10.1145/275487.275508]]]>
k-anonymity. ACM Trans. on Knowledge Discovery from Data (TKDD), 2007, 1(1): 3.[doi: 10.1145/1217299.1217302]]]>
t-Closeness: Privacy beyond k-anonymity and l-diversity. In: Proc. of the IEEE 23rd Int'l Conf. on Data Engineering (ICDE). IEEE, 2007. 106-115.[doi: 10.1109/ICDE.2007.367856]]]>
Dwork C, Roth A. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 2014, 9(3-4):211-407.[doi: 10.1561/0400000042]
doi: 10.1007/978-3-319-62004-6]]]>
Xiao YH, Xiong L, Fan LY, Goryczka S, Li HR. DPCube: Differentially private histogram release through multidimensional partitioning. Trans. on Data Privacy, 2014, 7(3): 195-222.
Li C, Miklau G, Hay M, McGregor A, Rastogi V. The matrix mechanism: Optimizing linear counting queries under differential privacy. VLDBJ, 2015, 24(6):757-781.[doi: 10.1007/s00778-015-0398-x]
Yuan GZ, Zhang ZJ, Winslett M, Xiao XK, Yang Y, Hao ZF. Low-Rank mechanism: Optimizing batch queries under differential privacy. Proc. of the VLDB Endowment (PVLDB), 2012, 5(11): 1352-1363.
doi: 10.1109/SPW.2017.11]]]>
Dwork C, Pappas GJ. Privacy in information-rich intelligent infrastructure. CoRR abs/1706.01985, 2017.
Barbosa P, Brito A, Almeida H. A technique to provide differential privacy for appliance usage in smart metering. Information Sciences, 2016, 370–371:355-367.[doi: 10.1016/j.ins.2016.08.011]
Eibl G, Engel D. Differential privacy for real smart metering data. Computer Science-Research and Development, 2017, 32(1-2): 173-182.[doi: 10.1007/s00450-016-0310-y]
Li DH, Yang QY, Yu W, An D, Zhang Y, Zhao W. Towards differential privacy-based online double auction for smart grid. IEEE Trans. on Information Forensics and Security, 2020, 15: 971-986.
Cao H, Liu SB, Wu LF, Guan ZT, Du XJ. Achieving differential privacy against non-intrusive load monitoring in smart grid: A fog computing approach. Concurrency and Computation: Practice and Experience, 2019, 31(22).[doi: 10.1002/cpe.4528]
doi: 10.1109/SP.2011.40]]]>
doi: 10.1007/11787006.1]]]>
doi: 10.1137/1.9781611973075.16]]]>
doi: 10.1145/1806689.1806787]]]>
doi: 10.14778/2732977.2732989]]]>
doi: 10.1007/11681878_14]]]>
doi: 10.1109/FOCS.2007.66]]]>
Warner SL. Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American Statistical Association, 1965. 63-69.[doi: 10.2307/2283137]
doi: 10.1145/2043621.2043626]]]>
doi: 10.1145/2448496.2448530]]]>
doi: 10.1007/978-3-662-48800-3_30]]]>
doi: 10.1145/3133956.3134102]]]>
doi: 10.1145/2452376.2452400]]]>
doi: 10.1145/2806416.2806454]]]>
doi: 10.1007/978-3-642-31680-7_8]]]>
Misra J, Gries D. Finding repeated elements. Science of Computer Programming, 1982, 2(2):143-152.[doi: 10.1016/0167-6423 (82)90012-0]
Bloom BH. Space/Time trade-offs in Hash coding with allowable errors. Communications of ACM, 1970, 13(7):422-426.[doi: 10.1145/ 362686.362692]
Dwork C, Naor M, Pitassi T, Rothblum GN, Yekhanin S. Pan-Private streaming algorithms. In: Proc. of the Innovations in Computer Science (ISC). 2010. 66-80.
doi: 10.1145/1989284.1989290]]]>
doi: 10.1145/2810103.2813640]]]>
doi: 10.14778/3137765.3137804]]]>
doi: 10.1109/ICDE.2017.132]]]>
doi: 10.1145/2514689]]]>
doi: 10.1145/3035918.3064025]]]>
doi: 10.1145/2588555.2588581]]]>
doi: 10.1109/TIFS.2014.2368363]]]>
Chen R, Fung BC, Philip SY, Desai BC. Correlated network data publication viadifferential privacy. The Int'l Journal on Very Large Data Bases (VLDB J), 2014, 23(4):653-676.[doi: 10.1007/s00778-013-0344-8]
doi: 10.1145/1807167.1807247]]]>
doi: 10.1002/9780470976562.ch6]]]>
doi: 10.1109/TKDE.2013.96]]]>
doi: 10.1007/978-3-642-39256-6_3]]]>
doi: 10.1145/2566486.2568038]]]>
Wang H, Xu ZQ. CTS-DP: Publishing correlated time-series data via differential privacy. Knowledge-Based Systems, 2017, 122:167-179.[doi: 10.1016/j.knosys.2017.02.004]
doi: 10.1109/TAC.2017.2713643]]]>
doi: 10.1109/ICCPS.2014.6843714]]]>
doi: 10.1109/ICASSP.2017.7953390]]]>
doi: 10.1109/ACCESS.2018.2797159]]]>
doi: 10.1145/2806416.2806441]]]>
doi: 10.14722/ndss.2014.23128]]]>
doi: 10.1109/INFOCOM.2016.7524461]]]>
doi: 10.1109/TKDE.2011.102]]]>
doi: 10.1007/2F978-3-642-37487-6_30]]]>
doi: 10.1145/2339530.2339564]]]>
N-grams. In: Proc. of the ACM Conf. on Computer and Communications Security (CCS). ACM, 2012. 638-649.[doi: 10.1145/2382196.2382263]]]>
doi: 10.1109/INFOCOM.2015.7218422]]]>
Li M, Zhu LH, Zhang ZJ, Xu RX. Achieving differential privacy of trajectory data publishing in participatory sensing. Journal of Information Science, 2017, 400:1-13.[doi: 10.1016/j.ins.2017.03.015]
et
et
Wang S, Sinnott RO. Protecting personal trajectories of socialmedia users through differential privacy. Computers & Security, 2017, 67:142-163.[doi: 10.1016/j.cose.2017.02.002]
et
et
Su D, Cao JN, Li NH, Bertino E, Lyu M, Jin HX. Differentially private
Gursoy ME, Inan A, Nergiz ME, Saygin Y. Differentially private nearest neighbor classification. Data Mining and Knowledge Discovery, 2017, 31(5):1544-1575.[doi: 10.1007/s10618-017-0532-z]
Su D, Cao JN, Li NH, Lyu M. PrivPfC: Differentially private data publication for classification. The Int'l Journal on Very Large Data Bases (VLDBJ), 2018, 27(2):201-223.[doi: 10.1007/s00778-017-0492-3]
doi: 10.1109/MDM.2015.15]]]>
doi: 10.1145/2775051.2677005]]]>
doi: 10.1109/ICDE.2015.7113353]]]>
Alaggan M, Gambs S, Kermarrec A. Heterogeneous differential privacy. Journal of Privacy and Confidentiality, 2016, 7(2):1-28.[doi: 10.1145/2806416.2806546]
doi: 10.1109/ICDE.2016.7498248]]]>
doi: 10.1145/2660267.2660348]]]>