2020, Vol. 31
2. 中国人民大学 信息学院, 北京 100872;
3. 河南大学 计算机与信息工程学院, 河南 开封 475001
2. School of Information, Renmin University of China, Beijing 100872, China;
3. School of Computer and Information Engineering, He'nan University, Kaifeng 475001, China
随着信息技术的发展及物联网技术的兴起, 出现了越来越多的持续监控应用场景, 如健康管理、交通管理、智能建筑、智能基础设施与应急响应等.在这些场景中, 持续监控的成功实施依赖于对参与者持续共享的个体信息或大量密集传感器(例如照相机、手机、WiFi接入点、信标)传输的流式数据进行实时监控和分析.由于持续监控下持续共享的数据中包含大量个体隐私数据, 如果不对其进行隐私保护, 会存在隐私泄露的风险.用户对隐私泄露的顾虑会限制参与者分享个体信息的意愿, 从而阻碍持续监控应用的发展[1, 2].
为保护用户数据隐私, 近两年, 很多国家和企业针对数据保护和个人信息的隐私保护问题制定了相关的法律政策.如:2016年, 欧盟制定的GDPR (general data protection regulation)(https://en.wikipedia.org/wiki/General_Data_Protection_Regulation)中, 明确了规定了用户对个人信息的知情权及被遗忘权; 2017年, 我国在《中华人民共和国网络安全法》(http://www.spp.gov.cn/xwfbh/wsfbt/201705/t20170509190088.shtml)中, 加强了对个人信息保护的政策规定.很多信息交流平台及各种APP, 如Facebook、Twitter、美团、京东, 都制定并发布了自己的用户隐私保护政策.除制定相关法律政策, 隐私保护问题的相关技术研究也逐渐受到重视.
差分隐私是一种定义极为严格的隐私保护模型, 相比于近年来k-匿名[3]、l-多样性[4]和t-紧密性[5]等需要基于特殊攻击假设和背景知识的隐私保护技术, 差分隐私因能够防止攻击者拥有任意背景知识下的攻击并提供有力的隐私保护, 受到了极大关注并被广泛研究.早期的差分隐私研究[6-10]主要是基于一个可信的管理者持有一个大规模、静态的数据集, 面向特定查询任务, 研究如何在保证用户隐私的前提下提高查询结果的可用性.由于基于的数据集是静态的, 因此计算都是一次性的.然而, 持续监控下差分隐私保护是一个新的差分隐私应用场景.在该场景中, 需对动态数据做持续计算和发布, 如何保护参与者持续更新的个体信息面临重大挑战.下面以几个具体持续监控下场景示例分析持续监控下差分隐私保护的必要性及挑战.
在交通实时监控[11, 12]中, 各种车辆实时提供位置给Google等数据统计公司, 公司统计大量参与者位置信息后, 实时发布交通区域图.基于上述统计结果, 无人驾驶汽车可以进行最优路线规划, 城市交通管理部门也可提供实时事故管理来保证道路通行能力.车辆的一次位置分享, 称为一次事件, 如何能提高持续发布统计结果的可用性, 同时保护用户参与事件不泄露, 是隐私保护目标.除上述示例, 还有很多应用场景都需进行持续监控下隐私保护.如:在疾病实时监控(https://h1n1.cloudapp.net)中, 用户通过与APP实时交互, 持续回答一些关于症状的查询, 可以确定自己是否患有该疾病; APP通过持续统计参与用户的信息, 实时监控区域疾病人数并提高疾病管理响应时间.在能源部门[13-16], 智能电网革命根据对能源供应和需求进行严格和高粒度的实时计量, 从而提高实时需求响应质量, 并对不可预测的能源需求来保证电网的稳定性和可靠性.在搜索引擎、在线零售商和社交网络中[17], 需要持续统计用户数据来及时发现有社会价值和经济价值的信息; 在一些政治活动中, 网站持续调查民众意见并持续更新候选人支持率.在上述应用中, 用户持续参与统计, 计量设备持续输送流式数据都会增加隐私泄露风险.如果没有用户隐私保护机制, 参与者分享个体信息的意愿会受到限制.
传统差分隐私场景下, 往往根据一次参与事件对发布结果的最大影响(敏感度)添加噪声.以简单计数任务为例, 一次事件的参与与否所带来的发布结果敏感度为1, 添加O(1/ε)的拉普拉斯噪声即可满足ε-差分隐私.但在持续监控下(如交通实时监控任务), 一次参与事件不仅对当前发布值有影响, 对后续时刻发布值都会有影响.假设时序长度为T, 添加O(T/ε)的拉普拉斯噪声才能实现一次事件的差分隐私保护.同时, 由于时序上往往存在个体的多次参与事件, 所带来的隐私泄露风险更大, 需添加更多的噪声才能实现对多个事件的隐私保护.这就存在以下问题:一是随着时序长度的增加, 发布结果可用性变差, 如何降低噪声量对时序长度的依赖面临较大的挑战; 二是为保护个体的多次参与事件, 隐私预算需在时序上进行分配, 如何提高时序上隐私预算利用率也是一个挑战; 三是如果面向的是复杂分析任务的持续监控保护, 因监控任务的发布敏感度大, 所需添加的噪声量会更大, 在这种情况下, 如何保证发布结果可用性也存在很大挑战.
持续监控下差分隐私保护研究具有实际的应用背景和重要的研究意义.目前已有一些持续监控下差分隐私保护的研究成果.本文综述持续监控下差分隐私保护的最新研究进展和研究方向:一方面对持续监控下差分隐私的定义、实现机制和持续监控方案的评估标准进行总结; 另一方面, 对当前持续监控下差分隐私保护的已有研究方案进行总结分析, 其中着重总结满足event级、user级和w-event级隐私保护的实现方案.最后, 提出持续监控下差分隐私保护的未来研究展望.
本文第1节总结持续监控下差分隐私保护模型.第2节总结主要研究方案分类.第3节~第5节分别对持续监控下差分隐私保护的现有研究方案进行概括, 并对研究方法进行对比和分析.第6节提出持续监控下差分隐私保护的未来研究展望.最后, 第7节总结全文.
1 持续监控下差分隐私保护模型本节主要对持续监控下的差分隐私定义、实现机制及隐私保护方案评估标准等几个方面进行总结.
1.1 传统差分隐私定义设数据集D和D', D和D'数据集属性结构相同, 如果两者的对称差|D-D'|=1, 则称D和D'为邻居数据集.也就是说, D和D'相差一条记录信息.
定义1(差分隐私)[18].给定一个随机化的算法M, PM为M的所有可能的输出集合, 如果算法M在任意邻居数据集D和D'上的输出结果O(O∈PM)满足下列不等式, 则M满足ε-差分隐私:
| $ \operatorname{Pr}[M(D) \in O] \leqslant \operatorname{Pr}\left[M\left(D^{\prime}\right) \in O\right] \times e^{\varepsilon} $ | (1) |
隐私预算参数ε表示隐私保护程度, ε越小, 隐私保护程度越高.
1.2 持续监控下差分隐私定义直观地讲, 持续监控下的数据发布[19]可以看作是在一个离散的时间间隔序列t={t1, t2, …, tn}上, 针对每个时间间隔ti, 算法重复接受输入、计算、然后输出的过程, 而其差分隐私保护则是对时间序列上这个重复的过程及发布结果序列进行差分隐私处理以满足隐私保护要求.
在上节传统差分隐私定义中, 差分隐私要保证基于邻居数据集上统计结果的概率比值不大于eε, 也就意味着在数据集中添加或删除某用户的参与信息后, 发布结果变化不大, 从而实现个体在静态数据集上一次参与事件的隐私保护.在持续监控下, 差分隐私也要保证基于邻居数据集的统计结果满足上述要求.但该场景中, 用户在不同的时间会有多次的参与事件.随着参与事件的增加, 隐私泄露风险往往更大.如何在时序上对用户多次参与事件进行保护, 是持续监控下隐私保护的目标.如图 1中持续监控场景示例, 在时间序列t={t1, t2, …, tn}上, 针对每个ti, 监控该时刻位置L的人数.
|
Fig. 1 Example of continual monitoring 图 1 持续监控场景示例 |
假设图 1中Di代表ti时刻的数据集, Di中每行代表一个参与者在该时刻是否在位置L, 其值为0或1:1表示在, 0表示不在.在持续监控下, 数据集为一个动态序列D={D1, D2, …, Dn}.每个时刻ti需要发布数据Di中位置L属性列上的count计数值.用户在某时刻Di中的一条记录称之为一次参与事件.随着时间的更新, 每个Di中都会存在某个参与者的参与事件, 也就是说, D中存在用户的多次参与事件, 它们是持续监控下要保护的用户隐私.
结合具体问题的监控事件, 持续监控下差分隐私保护需要对基于监控事件数据流的统计分析做差分隐私保护处理.假设用S={x1x2x1x1x3…}表示一个持续监控事件数据流, X表示数据流S中元素的值域, xi∈X表示某用户一次参与事件.持续监控下差分隐私保护是基于邻居数据流进行定义.根据现有方案能提供的差分隐私保护级别, 邻居数据流分为3种级别:event-级、user-级和w-event级.3种隐私保护级别的邻居数据流及相应的差分隐私保护定义如下.
1.2.1 Event-级差分隐私Event级邻居数据流:在持续监控下, 如果存在x, x'∈X, 从S中任意将某个x替换为x'后变为S', 称S和S'为持续监控下event级邻居数据流.其含义是从监控数据流中添加(删除)某用户的一次参与事件.
定义2(Event-级差分隐私)[20].给定一个随机化的算法M, PM为M的所有可能的输出集合, 对于算法M在任意event邻居数据流S和S'上任意的输出结果O(O∈PM), 如果其满足下列不等式, 则M满足ε-差分隐私:
| $\operatorname{Pr}[M(S) \in O] \leqslant \operatorname{Pr}\left[M\left(S^{\prime}\right) \in O\right] \times e^{\varepsilon} $ | (2) |
Event级差分隐私保护能保证在持续监控生命期中, 用户的一次事件对整个监控结果影响受隐私预算ε的控制.ε越小, 隐私泄露风险越低; 反之越高.
1.2.2 User-级差分隐私User级邻居数据流:在持续监控下, 如果存在x, x'∈X, 从S中将某用户对应的所有事件x替换为x'后变为S', 称S和S'为持续监控下的user级邻居数据流.其含义是, 从监控数据流中添加(删除)某用户的所有参与事件.
定义3(User-级差分隐私)[20].给定一个随机化的算法M, PM为M的所有可能输出集合, 对于算法M在任意user级邻居数据流S和S'上的输出结果O(O∈PM)满足下列不等式, 则M满足ε-差分隐私:
| $ \operatorname{Pr}[M(S) \in O] \leqslant \operatorname{Pr}\left[M\left(S^{\prime}\right) \in O\right] \times e^{\varepsilon} $ | (3) |
User级差分隐私保护是对持续监控生命期中某用户的所有参与事件对整个监控结果的影响进行控制, 也就是对持续发布统计结果的隐私泄露风险进行了限制.
1.2.3 w-event级差分隐私w-event级邻居数据流:给定一个正整数w, 如果两个流前缀St和
定义4(w-event级差分隐私)[21].给定一个随机化的算法M, PM为M的所有可能的输出集合, 对于算法M在任意w-event级邻居数据流St和
| $\Pr [M({S_t}) \in O] \leqslant \Pr [M({S'_t}) \in O] \times {e^\varepsilon }$ | (4) |
w-event级隐私可以看作是user级隐私的拓展, 它实现在任意w滑动窗口内用户的user级隐私保护.它也是event和user级的一个中间级隐私保护, 当w=1时, 保护级别下降为event级; 当w为T时, 则为user级隐私.
在上述的3种定义中, event级所提供的隐私保护强度最小, user级隐私保护强度最大, 而w-event级隐私保护是上述两种方案的折衷.隐私预算参数ε用来控制对持续监控下基于不同级别邻居数据集的输出结果的概率比值, 也就是方案的隐私保护程度, ε越小, 隐私保护程度越高; 反之越低.ε的取值往往要结合监控所需要达到的隐私保护度和发布结果的可用性两个因素进行综合的衡量.
1.3 噪声机制噪声机制是实现差分隐私保护的主要技术, 常用的噪声添加机制分别为拉普拉斯机制[22]与指数机制[23].添加的噪声量与查询任务的全局敏感度和隐私预算大小密切相关.
定义5(全局敏感度)[22].设有函数f:D
| $ G S_{f}=\max _{D, D^{\prime}}\left\|f(D)-f\left(D^{\prime}\right)\right\|_{1} $ | (5) |
称为函数f的全局敏感度, ||f(D)-f(D')||1指的是f(D)和f(D')的1-阶范数距离.函数的全局敏感度由函数本身决定, 不同的函数有不同的全局敏感度.敏感度越小, 所需添加的噪声越少.
定理1(Laplace机制)[22].给定数据集D, 设有函数f:D
| $ M(D)=f(D)+{Lap}\left(\frac{\Delta f}{\varepsilon}\right)^{d} $ | (6) |
其中, Lap((Δf)/ε)d为独立拉普拉斯噪声, 噪声服从b=Δf/ε的拉普拉斯分布.Lap(b)的概率密度函数为
| $p(x) = \frac{1}{{2b}}\exp \left( { - \frac{{|x|}}{b}} \right).$ |
拉普拉斯机制只适合于数值型输出的查询函数.许多应用中查询输出为非数值型.对此, McSherry等人提出了指数机制.其实现核心是设计打分函数u, 为输出域中每个输出项打分, 分值越高, 被选择输出的概率越大.
定理2(指数机制)[23].设定一个打分函数u:(D×O)
| $M(D, u) = \left\{ {r:\Pr [r \in R] \propto \exp \left( {\frac{{\varepsilon u(D, r)}}{{2\Delta u}}} \right)} \right\}$ | (7) |
其中, r∈O, 表示从输出域O中选择的输出项; Δu为打分函数u的全局敏感度.
1.4 组合特性差分隐私保护具有两个组合性质:序列组合性和并行组合性, 在持续监控下仍然适用.
性质1(序列组合性)[22].设有算法M1, M2, …, Mn, 其隐私预算分别为ε1, ε2, …, εn.那么对于同一数据集D, 由这些算法构成的组合算法M(M1(D), M2(D), …, Mn(D))提供
性质2(并行组合性)[22].算法M1, M2, …, Mn, 其隐私预算分别为ε1, ε2, …, εn.那么对于不相交的数据集D1, D2, …, Dn, 由这些算法构成的组合算法M(M1(D1), M2(D2), …, Mn(Dn))提供maxεi-差分隐私保护.
序列组合性表示对同一数据集多个差分隐私保护算法的序列组合算法, 所提供的保护水平为全部隐私预算之和.并行组合性表示对不同数据集保护的多个差分隐私保护算法的组合算法, 所提供的保护水平为算法中的最低的保护水平, 也就是隐私预算的最大值.
1.5 持续监控下差分隐私保护方案评估满足差分隐私保护的方案在实现隐私保护同时, 也要兼顾发布结果的可用性.因此, 方案的评估包含以下两个方面.
(1) 隐私保护评估:差分隐私处理核心是隐私预算分配和敏感度计算; 隐私预算ε代表着发布任务的隐私保护程度.隐私预算一旦耗尽, 方案的差分隐私保护特性将被破坏.评估方案是否能实现隐私保护, 主要是对其差分隐私处理过程中的隐私预算分配策略进行分析, 计算发布过程所分配的隐私预算是否符合隐私预算的要求, 同时分析敏感度的计算是否正确;
(2) 算法结果误差:为评估方案发布结果的可用性, 往往计算真实结果与经差分隐私处理后的结果之间的误差.根据持续监控下问题的不同, 误差采用的衡量方法往往不同.如:简单聚集统计发布问题中, 常对发布结果误差上界进行证明, 并在实验评估中采用相对误差、绝对误差等度量标准; 而其他问题会根据自身问题特点定义不同的标准, 如轨迹保护中, 采用JS散度、F-Score等可用性衡量标准.
2 持续监控下差分隐私保护方案分类持续监控下差分隐私保护研究对推动智能信息技术的发展具有重要的意义, 其隐私保护问题也是急需解决的问题.本文将现有持续监控下差分隐私保护方案分为3类, 分别为持续监控下event级别保护方案、持续监控下user级别保护方案和持续监控下w-event级别保护方案.其中:持续监控下event级别差分隐私保护方案主要围绕单值计数和持续发布、直方图持续发布、heavy hitter持续监控和位置发布等持续监控问题, 针对如何降低持续发布的高敏感度提出相应的解决方案; 持续监控下user级别和w-event级别的保护方案主要围绕简单聚集信息持续发布、分布式数据流阈值函数持续监控、集值对更新发布和轨迹发布问题, 针对如何提高时序上隐私预算的利用率, 同时降低发布任务的高敏感度提出相应的解决方案.每个分类对应的方案示例见表 1.
|
Table 1 Existing research on differential privacyunder continual observation 表 1 持续监控下差分隐私保护方案分类 |
3 持续监控下event-级隐私保护方案
Event-级别持续监控隐私保护主要基于count计数的发布任务进行研究, 主要包括单值计数和的持续监控保护、直方图持续发布的隐私保护、heavy hitter和位置信息发布等特定任务的持续监控保护.
3.1 单值计数和持续监控保护目前, 大部分event-级别的持续监控保护研究都是基于单值计数和的持续监控保护问题, 如图 2所示, 假设存在一个随时间不断更新的事件(event)数据流-基于动态数据抽象得到, 其中, 0代表监控的事件没有发生, 1代表事件发生.如何能持续更新发布数据流中1的计数和, 同时保证持续发布满足差分隐私要求是隐私保护目标.该问题形式化如下:时间序列上对应的事件数据流σ∈{0, 1}N, N={1, 2, 3…, n}为一组正整数的集合; σt∈{0, 1}N代表σ的长度为T的前缀数据流; [T]={1, 2, 3, …, T}表示数据流长度; σ(t)∈{0, 1}表示时间ti(i∈N)对应的数据流段中1的计数值.
|
Fig. 2 Continual release of the running sum 图 2 单值计数和的持续发布 |
单值计数和问题在很多应用场景上都可适用, 如特定位置的交通实时监控、特定网页的用户点击行为实时监控、传感器网络中某IP地址访问的持续监控、智能基础设施的持续监控、疾病控制中心对患某种疾病人数的持续监控、满足特定谓词条件的持续查询等等.
3.1.1 基本发布方案● 方案1
方案1是文献[18, 22]中差分隐私实现机制的直接应用, 其基本思想是:根据已知的数据流长度T, 在每个发布时t∈T, 对前缀数据流σt的真实计数和c(t)加上拉普拉斯噪声后发布.在该方案中, 每个发布时刻t分配的隐私预算为ε, 发布任务的敏感度为T.随机化算法M在每个时间t生成一个独立随机噪声Lap(T/ε), 发布结果为c(t)+ Lap(T/ε).根据差分隐私的组合性质, 该方案满足event级ε-差分隐私.经分析证明, 发布结果的渐近误差上界为O(T/ε).方案有如下两个缺点:(1)由于每个发布时刻添加的噪声量与数据流长度T成正比, 所以数据流长度越大, 算法发布结果的可用性越差; (2)由于要根据数据流长度来对发布结果添加噪声, 该方案只能对长度上限已知的数据流进行隐私保护, 无法对无限数据流进行差分隐私保护.
● 方案2
方案2则是差分隐私实现机制[22]与文献[24]思想的结合应用, 其基本思想是:在每个时刻t∈T, 对t对应的数据流段中的真实计数值σ(t)进行噪声干扰.每个时间t所分配的隐私预算为ε, 由于σ(t)只跟当前时间有关, 跟前后时间所对应的计数值都无关, 所以计数任务的敏感度为1.因此在每个时刻, 随机化算法M都生成一个独立随机噪声Lap(1/ε), 对σ(t)加上拉普拉斯噪声为αt=σ(t)+Lap(1/ε).由于监控目标是每个时刻的计数和c(t), 所以差分隐私保护机制M在时刻t的发布结果为
● Two-level方案[25]
为降低发布结果误差对T的依赖, Two-level方案对方案2进行了拓展, 核心思想是:对数据流进行分组, 每组是一个连续的时间区间.不够一组的元素采用方案2进行差分隐私保护; 分组之上, 将每个组计数和看作一个元素, 再次采用方案2思想对每组计数进行隐私保护.假设每组大小为B, 数据流长度为T, 在发布时刻ti, 首先将ti拆分为组:ti=qB+r.然后以组为单位, 对每个组计数加上Lap(1/ε)噪声:
|
Fig. 3 Example of Two-level 图 3 Two-level方案示例 |
由于每个时刻ti的值σ(ti)只会影响其所在的组或αt, Two-level满足event级2ε-差分隐私.经分析证明, 该方案发布结果渐近误差上界为
上述3种基本方案的发布结果误差对数据流长度T都有较大的依赖性, 发布结果可用性较低.Tree Counter[20, 25]方案基于上述问题进行了改进, 其核心思想是:将长度为T的数据流构造成一棵完全二叉树, 树的叶节点存储ti时刻的元素计数值σ(ti), 内部节点Psum则存储其覆盖区间[i, j]的叶节点的计数和, 其值为Psum=
对任意时刻ti, c(ti)都可以表示为一组Psum节点值的求和.如图 4中:当ti=7时, c(7)可以由Psum节点[1, 4], [5, 6]和σ(7)求和.根据二叉树的性质, ti时刻发布值的计算中参与求和的Psum节点数最多为logT+1.根据Psum节点计算c(ti), 发布任务的敏感度为logT+1.算法为每个参与求和的Psum节点添加满足Lap((logT+1)/ε)的噪声, 即可保证发布结果满足event级ε-差分隐私.可以看出:采用二叉树的发布方案, 使持续发布任务的敏感度由O(t)降为了O(logT).经分析证明, Tree Counter发布结果的渐近误差上界为O((logT)1.5/ε), 进一步提高了发布结果的可用性.但其有以下两个缺点:(1)处理的数据流必须是有限长度, 不能处理无限长的情况; (2)提供的是event级别的隐私保护, 隐私保护级别较弱.
针对Tree Counter第1个缺点, 文献[25]以Tree Counter和two-level两种机制为基础, 提出一种混合机制Hybrid机制, 该方案可以实现对无限数据流event级的差分隐私保护.其主要思想是, 将所有待发布的时间分为两类:第1类是可以表示为2的幂集的时间点集合, 第2类是非2幂集的时间点集合.对每个发布时刻ti, 随机化发布机制H根据ti类别采用不同的保护机制.如果ti为2的幂级, 采用L机制(改进的two-level机制)发布; 如果ti不为2的幂级, 采用M(Tree Counter机制)发布.L机制算法思想类似于two-level机制, 不同的是:two-level机制采用定长分组, 而L机制则采用变长分组, 只要时间点为2的幂集(2k(k∈Z)), 就把此前的时间区间分为一组.基于分组, 添加Lap(1/ε).对非2的幂集的时刻ti, 如ti∈(2k, 2k+1)则采用长度上限为T=2k的M(Tree Counter)机制发布方案.假设τ=ti-T, 则ti时刻的发布为H(ti)=L(T)+MT(τ).Hybrid机制提高了发布结果可用性, 也解决了Tree Counter只能处理有限长数据流的问题.
虽然上述方案解决了数据流长度受限问题, 但还有以下缺点:(1)由于发布结果包含噪声, 出现了相邻时刻发布结果不满足实际统计约束的不一致问题; (2)面向数据流的数据统计涉及到中间统计值的保存, 如果中间值被攻击者捕获, 则不能提供有力的保护.针对缺点(1), 文献[25]对单值计数和持续发布中的一致性问题进行了定义.针对缺点(2), 文献[20, 25]设计了可以实现Pan-privacy的持续发布方案, Pan-privacy的含义指攻击者即使获取了数据流处理的中间值, 结合持续观察的发布结果, 也无法判断个体事件是否发生, 从而实现了隐私与安全的结合.
在很多实时监控的应用场景中, 往往近期发生的事件对监控更有意义, 而发生时间较远的事件对监控价值较低.针对这个问题, 文献[26]提出了基于衰减的单值计数和持续监控保护方案DecayedSum, 并分析证明了方案中发布结果误差上界.方案中提出了3种数据衰减模型的差分隐私保护机制, 分别是基于滑动窗口的保护、基于指数机制衰减和基于多项式衰减的保护.第1种方案提出了对最近W宽度窗口内的单值统计和发布的event级ε差分隐私方案, 发布结果误差上界为O(logW/ε).第2种方案提出了基于指数衰减模型单值计数和持续发布的event级ε-差分隐私方案, 发布结果误差上界为O(log(α/(1-α))/ε), 其中, α为指数衰减因子.第3种方案提出了基于多项式衰减模型单值计数和持续发布的event级ε-差分隐私保护方案, 发布结果误差上界为
| $ O\left((1 / \varepsilon)\left(1 / c \beta^{2}\right) \log (1 /(1-\beta))\right), $ |
其中, c为多项式衰减因子, β为错误控制参数.3种隐私保护方案都是基于Tree Counter方案的拓展.DecayedSum可以实现对无限长数据流的隐私保护, 更符合实时监控的场景.
3.1.3 基于分区的发布方案基本方案和二叉树方案中没有考虑数据流自身特点对发布结果的影响.文献[27]提出了一种适合稀疏数据流的自适应分区方案Partition, 该方案通过结合数据流的变化特点降低发布问题的敏感度, 提高发布结果的可用性.Partition的基本思想为:按提前设定的阈值, 将长度为T的稀疏数据流划为一组连续分区的集合, 每个分区的计数和基本相同, 为接近于阈值的一个统计值.假设分区后分区个数为m(m < < T), 用分区的计数和来代替Tree Counter的叶节点, 然后基于Tree Counter的基本思想进行隐私保护.由于持续监控发布结果基于分区的统计值进行计算, 分区个数m又远远小于T, 因此发布任务的敏感度降低, 提高了算法的可用性.算法过程描述如下:对每个区j, 首先设置一个countj用来记录分区j内的计数和; 从j-1分区的后续时刻t开始, 依次统计分区j的真实计数和countj:countj+=σ(t); 计算当前分区j的噪声计数值:
|
Fig. 5 Example of adaptive partition 图 5 Partition自适应分区示例 |
在发布某个时刻t的统计值时, 结合Tree Counter的思想, 将每个分区的统计值作为叶节点, 构造完全二叉树, 发布结果的计算就依赖于每个分区的结果统计.经分析证明, 算法的渐近误差上界降为O(logT+(log2n)/ε).其中, n是数据流中1的总计数, 在稀疏数据流中, n < < T.该方案只适用于稀疏数据流的应用环境.
文献[28]提出的PeGaSus方案同样采用分区思想对面向数据流的持续监控问题进行了研究.PeGaSus方案由3个构件组成:Pertuber, Grouper和Smoother.为保证ε-差分隐私, 隐私预算ε分为两部分:ε=εp+εg.εp用于Pertuber, εg用于Grouper, Smoother是后处理过程, 不需要分配隐私预算(如图 6所示).
Pertuber用来对每个时刻t的计数进行噪声处理:σ(t)+Lap(1/εp).Grouper根据数据特点对数据进行自适应的分区, 分区原则是将统计值变化不大的连续时间分成一个区, 数据流被分成一组分区的集合.为了捕捉统计值的变化, 方案设计一个偏差函数用来获取分区值的变化信息; 如果变化大于设定的阈值θ, 则当前分区分配完毕; 从下个时刻开始, 重新开始新分区的划分.分区后, Smoother结合分区结果和Pertuber的噪声统计值, 采用分区平均值、中位数等平滑处理技术, 提高特定查询任务发布结果可用性.
PeGaSus与Partition分区策略不同点在于:(1) Partition是将数据流分为一组连续分区, 每个分区内的计数和基本相同; (2)而PeGaSus分区的思想是将计数值相似的的时间点分到一个分区, 不同分区间计数和可能变化较大; (3) Partition基于分区的计数和做噪声处理, 而PeGaSus则是对每个时间点的计数值做噪声处理;(4) PeGaSus采用了偏差函数帮助Grouper分区, 而Partition是通过提前设定的阈值进行分区; (5) Partition只针对单值计数和发布问题做隐私保护, 但PeGaSus面向的是多种查询任务类型, 如多目标持续查询和多时间跨度的持续查询等.
PeGaSus方案中, 因其支持多种查询类型, 提出对具有层次关系的查询任务关系进一步降低查询任务的敏感度, 提高发布结果的可用性.文献[29]则也利用查询任务之间的关系来降低查询结果的噪声, 文中提出了两种方案.
● SampleDP是针对查询任务的步长满足一定约束条件(长步长是短步长的整数倍)的情况下, 采用动态规划算法找出能使添加噪声量最小的步长组合;
● 而SampleEMD是将第1种方案扩展到更一般的情况:采用EMD相似性计算方法来选取与原有步长集分布相似的抽样步长集, 达到降低噪声、提高查询结果可用性的目的.
3.2 直方图发布的持续监控保护直方图是一种直观的数据分布表示形式, 它按照某属性或属性集将数据集信息划分成不相交的桶, 每个桶内有一个统计数字表示其特征.直方图的持续发布是基于时间序列上的动态数据, 持续发布直方图统计信息.图 7表示在时间序列上, 持续监控位置L1~L7上人数的直方图示例.
|
Fig. 7 Example of histogram publication under continual monitoring 图 7 持续监控下直方图发布示例 |
文献[30]针对无限数据流中直方图的持续发布问题, 提出一种满足event级的隐私保护方案RetroGroup.跟单值计数和持续监控保护方案一样, RetroGroup在时间序列上每个发布点所分配的隐私预算也为ε.但为了提高时序上发布结果的可用性, RetroGroup采用回溯分组来降低持续发布任务的敏感度.其基本思想是:根据相邻时间直方图的相似性, 将发布数据相似的连续时间分为一组, 以组为单位对要发布的直方图加拉普拉斯噪声.因此, RetroGroup方案包含两个过程:相似性计算和直方图发布.为满足ε差分隐私, 相似性计算过程分配的隐私预算为ε1, 发布过程分配隐私预算为ε2=ε-ε1.根据差分隐私的序列组合性质, 该方案满足ε-差分隐私.
假设用Hi代表ti时刻要发布的直方图, Hi[j]表示直方图的第j个桶的统计值.在每个时刻ti, 计算直方图的每个桶Bj的统计值Hi[j]和Hi-1[j]的差异d[j], 将d[j]变化不大的连续时间分为一组G(Bj).为了提高相似性计算效率, 方案采用抽样技术在提高效率的同时增大隐私预算的效用, 从而会降低拉普拉斯噪声.但抽样也会带来抽样误差, 因此方案中对抽样误差和差分隐私误差做了定量化分析.基于相似性计算进行分组后, 每个组包含多个时间点, 大小为|G(Bj)|.基于分组发布结果时, 对组内的平均计数值添加的拉普拉斯噪声量由Lap(1/ε2)降为了Lap(1/(|G(Bj)|ε2)), 发布结果可用性得到了提高.
RetroGroup与PeGaSus分区有些相似, 都是将数据变化不大的时间序列分为一组; 但RetroGroup是基于分组平均值做噪声处理, 而PeGaSus是基于每个时间点值做噪声处理, 而后针对特定查询任务进行分组平滑处理.
3.3 Heavy hitter的持续监控保护Heavy hitter的持续监控是指对数据流中的元素及其频数进行统计, 实时发布超出阈值的元素及其频数, 即heavy hitter.在该问题中, heavy hitter元素及其频数都是需要保护的隐私.文献[31]针对3种监控场景提出了对应的隐私保护方案:面向单数据流heavy hitter持续监控的隐私保护方案PMG、面向单数据流滑动窗口内heavy hitter持续监控的隐私保护方案PCC和面向分布式数据流滑动窗口内heavy hitter持续监控的隐私保护方案PDCH-LU.
PMG方案基于未做隐私保护的面向数据流中heavy hitter统计的算法MG[32], 采用差分隐私技术对其进行隐私保护.在MG算法中, 给定数据流长度T和错误控制参数λ, 算法执行过程中会持续维护一个长度为β=O(1/λ)的计数器组, 通过计数值可以统计出heavy hitter及其频数.为满足event级ε-差分隐私, PMG在每个发布时刻分配的隐私预算为ε, 由于MG算法的发布敏感度为β, 因此对发布结果添加隐私预算为ε, 敏感度为β的噪声, 即可满足ε差分隐私保护.
基于PMG, PCC方案按照时间宽度W将整个数据流分为了一系列的窗口.在每个窗口内, 采用二叉树结构统计其窗口内的heavy hitter, 其中, 二叉树叶节点代表w0=λw/4个时间点的统计值, 内部节点代表其覆盖的叶节点的时间区间内的统计值.如果持续发布W滑动窗口内的heavy hitter统计信息, 需要基于这组二叉树进行统计.而每次的发布参与统计的二叉树的节点数最多为logW+1.
根据二叉树中参与统计的节点创建时间, 所有节点可以分为图 8中所示的4类:过期、活动、正在创建和即将创建.由于实时发布只关注W宽度的统计值, 因此每次发布时最多只会关注最近两个窗口内的二叉树的统计信息.只有活动节点才需要占用内存空间.因此, PCC的空间代价为O((1/λ)log2(1/λ)), 计算性能较快.同时, 由于每个节点记录w0个时间间隔, 每隔w0才需要和分布式系统的中心节点进行通信, 因此降低了通信带宽.
PDCH-LU[31]则基于PCC做了进一步的改进, 将其改为面向分布式环境.为了进一步降低通信带宽, PDCH- LU首先采用Lazy更新策略降低总的通信代价:只有各分布式节点的统计值更新够大的情况下才与中心节点进行统计信息的通信; 其次, 在每次通信时, 采用Bloom Filter技术[33]降低每次的通信带宽.在隐私保护方面, 各分布式节点的单数据流采用PCC的隐私保护方案, 为了对统计信息来源的各分布式节点进行保护, 该方案采用了加密保护方案.
文献[34]基于抽样和随机响应技术对数据流中heavy hitter元素频数信息的持续发布进行差分隐私保护.该方案首先对所有元素集合X随机抽样出m个元素, 其计数值存放在数组M中.统计之前, 采用随机响应技术对数组M的每一个计数值初始化为:bx~D0(ε), D0(ε)指以等概率初始化为‘0’或‘1’; 统计中, 对数据流中出现的每个元素, 如果在M中, 则其对应的统计值做更新:bx~D1(ε), D1(ε)指产生1的概率为1/2+ε/4, 产生0的概率为1/2-ε/4.基于M, 持续计算并发布heavy hitter元素频数.
文献[35]同样对数据流中heavy hitter元素频数的持续发布进行差分隐私保护.主要实现技术是数据流处理的sketch技术和指数机制.由于基于sketch的数据流处理会维护一个记录中间统计值的sketch向量sk(a), 为实现差分隐私, 先采用服从με=exp(ε/4·q(sk(a), sk(a)priv))的指数机制噪声对sk(a)进行初始化, q(sk(a), sk(a)priv)是指数机制的效用函数; 然后, 基于初始化后的sk(a), 采用数据流统计算法对sk(a)中的元素统计值进行更新; 最后, 再对sk(a)进行满足με指数机制的噪声处理.基于噪声处理后的sk(a), 持续发布heavy hitter元素频数信息.
文献[34, 35]都考虑了攻击者获取到中间统计值时的隐私保护处理, 所以方案满足pan-privacy[19], 实现了差分隐私与安全的结合, 其隐私保护强度更高.两种方案的区别是:文献[34]只能对计数值增量更新情况下进行隐私保护, 而文献[35]却可以处理全动态更新情况下(计数值可以增加, 也可以减少)的隐私保护.
3.4 位置发布的持续监控保护文献[36, 37]提出一种基于时序关联的位置持续发布的隐私保护方案PIM.方案中, 相邻时刻用户位置的关联关系用马尔可夫模型建模和预测.在每个时刻, 找出用户的“δ-位置集”ΔX(t时刻用户可能会存在的位置及其对应的概率).差分隐私发布机制保证:在每个时刻t, 用户的真实位置与ΔX中任一位置出现的概率基本一样.即使攻击者能根据转移概率推测出ΔX, 也不能发现用户的真实位置.具体实现方案是:在每个时刻t, 基于t-1时刻的后验概率
文献[38]则针对位置聚集统计信息持续发布的隐私保护问题, 对时序关联所造成的隐私泄露做了定量的分析.用TPL代表该方案.方案问题场景如下:假设攻击目标ui在t时刻的位置为
基于上述信息, 方案中对时序数据相关性所造成的隐私泄露量给出了定量化的计算公式, 即为所有用户中最大的隐私泄露风险值.该隐私泄露量的计算包含前向转移关系隐私泄露的计算和后向转移关系隐私泄露的计算, 为了提高计算效率, 方案将隐私泄露量的求解问题转换为一个线性分式规划问题, 并提出了多项式时间内的求解算法.
上述方案都是考虑了时序数据相关性的隐私保护方案.目前, 关联数据发布的隐私保护研究提出了新的隐私保护模型Pufferfish[39, 40]和Blowfish[41].同时, 也有一些面向关联数据发布的差分隐私保护文献, 如文献[42, 43]针对静态社交网络和关联数据集的发布问题提出了相应的解决方案, 其主要思想是对数据之间的关联进行建模, 根据模型确定关联敏感度, 基于关联敏感度确定关联数据的噪声添加方案.虽然这些方案不是直接针对时序关联数据发布的隐私保护方案, 但可以拓展到持续监控场景下.
3.5 Event级隐私保护方案小结总结来说, 持续监控下event级隐私保护方案核心都是围绕如何提高时序数据发布的可用性问题进行研究, 其目标都是满足event级ε-差分隐私的前提下, 如何能降低发布结果误差, 提高发布结果可用性.本节从方案优缺点、发布结果误差等方面对现有event级隐私保护方案进行总结对比分析, 详细见表 2;然后指出现有方案的不足及未来研究趋势.
|
|
Table 2 Comparation of schemes on event-level privacy under continual monitoring 表 2 Event级别持续监控保护方案对比 |
(1) 从持续监控生命期上看, 所有event级别持续监控保护方案中, 不需要在时序上进行隐私预算分配.但由于时序发布任务的高敏感度, 数据流的持续监控保护长度受限.如在方案1和Tree Counter中, 必须根据数据流长度T添加噪声, 所以只能保护定长数据流; 其余方案虽然噪声添加方案与数据流长度无关, 但随着处理数据流长度的增加, 大部分方案发布结果可用性变差.只有Decayed Sum中隐私保护方案更符合实时监控特点, 能实现对无限长数据流的监控保护.因此, 如何在保证event级隐私和高可用性的前提下实现对无限长数据流的持续监控保护, 值得进一步研究;
(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级隐私保护方案, 也值得进一步研究.
4 持续监控下user-级隐私保护方案User级的持续监控保护方案主要围绕简单聚集统计信息的持续发布、分布式数据流的阈值函数持续监控、集值对的增量更新发布、轨迹数据发布等几个问题进行分析总结.
4.1 简单聚集统计信息的持续发布保护方案简单聚集统计指基于count、sum、average等聚集函数的信息统计.实时发布简单聚集统计信息对很多重要的数据挖掘应用具有很重要的意义.
如图 10所示:假设一个GPS服务提供商实时收集用户位置、速度、活动类型等信息, 然后统计出如某时段特定区域的用户数等统计信息, 提供给第三方研究机构; 第三方基于这些信息, 可以挖掘用户的常去区域、公众的兴趣、路段的交通堵塞等信息.但第三方机构往往是不可信的, 因此在简单聚集统计信息的持续发布过程中, 有必要对其进行隐私保护.本节主要针对简单聚集统计信息的持续发布问题, 对现有的几种user级隐私保护方案进行总结和对比分析.
4.1.1 基本发布方案
基本发布方案是差分隐私实现机制[22]的直接应用, 为满足user级的差分隐私, 基本方案是将隐私预算ε平均分配到时间序列上每个发布时间点.假设时间序列长度为T, 则每个发布点所分配的预算为ε/T.根据差分隐私的序列组合性质, 则整个时间序列上的持续发布满足ε差分隐私.由于每个发布点所分配的隐私预算跟T成反比, 发布结果误差为θ(T), 发布结果可用性较低.为提高可用性, 降低误差, 很多文献基于采样的方法, 选出有代表性的采样点进行发布, 具体方案如下.
4.1.2 基于傅里叶级数变换的采样发布方案文献[44]提出一种基于傅里叶级数变换的采样发布方案DFT, 该方案满足user级隐私.其基本思想是:选取d(d < < T)个最具有代表性的时刻进行发布, 其他时刻的结果用相邻时刻结果近似计算获得.对每个代表性的时刻, 添加满足ε/d的拉普拉斯噪声, 整个发布结果序列满足ε差分隐私.具体过程为:根据用户预先设定的傅里叶系数个数d, 先对时间序列上的真实统计值X做离散傅里叶变换, 取其前d个傅里叶系数Fd; 然后对Fd中每个系数添加满足隐私预算为ε/d的拉普拉斯噪声, 生成噪声
文献[46]提出了一种基于PID机制[45]的自适应抽样发布方案FAST, 该方案满足user级隐私保护.与DFT不同, 该方案可以处理实时数据流, 效率较快.FAST的核心策略是, 采用自适应采样技术和滤波技术来提高发布结果的可用性.其基本框架如图 11所示, 其中:自适应采样技术是为了降低时间序列上总的隐私预算消耗, 而滤波技术是为了提高每个发布点上发布结果的可用性.
自适应抽样机制的核心思想是:设定整个时序发布次数上限值为M(M < < T), 基于PID控制原理, 根据历史采样频率和反馈信息来调整新的抽样频率, 选择代表性的抽样点进行发布, 使得最终的采样发布次数保持为M.由此, 每个采样点所分配到的隐私预算由ε/T增大为ε/M, 提高了时序上隐私预算的利用率.而PID技术的实现核心是:设置反馈信息, 定义为每个采样时刻的发布结果误差值
滤波技术的核心思想是:建立一个状态空间模型, 根据模型预测值和观测到的噪声统计值, 采用后验估计对要发布的结果进行校正, 提高发布结果的可用性.所建立的状态空间模型包括相邻时刻统计值预测模型和噪声处理模型, 相邻时刻处理模型为xk=xk-1+ω, ω~N(0, Q), xk代表k时刻的真实值; ω为高斯白噪声, 也称为处理噪声; Q为方差.噪声处理模型为zk=xk-1+υ, ν~Lap(0, M/ε), zk为k时刻噪声统计值, ν是拉普拉斯噪声.在每个抽样发布时刻k, 基于状态空间模型获得xk和zk, 然后采用卡尔曼滤波的后验估计方法对要发布的结果
文献[47]将FAST应用到了二维空间的区域实时计数监控问题中, 文献提出了两种估计算法来降低噪声误差:一个是时序估计算法, 核心思想就是FAST的应用, 基于采样和卡尔曼滤波后验估计方法去降低时序数据发布的总误差; 另一个是空间估计算法, 基于quadtree建立一个空间索引结构, 基于该结构对具有相似统计值的区域进行分组, 然后基于分组添加拉普拉斯噪声, 降低由于数据稀疏所造成的添加噪声过大的问题.
文献[48]则将FAST应用到了用户的网页浏览行为的持续监控问题中.文献将网页监控问题分为了单值持续监控和多值持续监控两种情况:在单值持续监控方案中, 基于FAST的思想建立状态空间模型, 采用卡尔曼滤波方法对观测的噪声值进行校正, 提高发布结果可用性; 在多值目标监控中, 时序处理模型结合了网页的马尔可夫转移矩阵来进行预测.虽然方案满足user级隐私保护, 也提高了发布结果的可用性, 但还有一些缺点可进一步改进.如:随着监控的网页数目m的增加, 多变量的时序空间模型处理的时间复杂度非常大, 达到O(m3), 因此可以考虑采用如稀疏矩阵、矩阵的秩和矩阵分解技术来进一步提高发布效率.
文献[49]基于滤波技术提出了一种时序关联数据的发布方案CTS-DP, 保证在数据关联的情况下, 发布的结果序列与添加关联噪声后的序列满足差分隐私要求; 同时, 攻击者不能通过修正技术清洗掉添加的噪声, 还原真实数据.文献[50]则将滤波技术应用到多输入输出(MIMO)事件数据流中, 利用滤波降低发布结果噪声.文献[51-53]将滤波应用到监控实例(实时交通速度估计和建筑物占用情况预测)中, 并提出了噪声添加的优化方案.
上述方案都是面向无限数据流实时发布方案, 文献[54]借鉴PID反馈机制提出一种面向离线动态数据集的直方图发布的隐私保护方案DSAT, 该方案实现user级隐私保护.方案的基本思想是:基于PID反馈机制进行动态调整抽样发布的频率, 反馈公式为Ei=|Ci/i-C/N|.Ci是当前已发布次数, 如果在该时间点之前发布频率过高, 则调大阈值, 降低采样频率; 反之调小阈值, 增加采样频率, 以保证在时间序列内固定发布C次数据.与FAST方案相同的是, DSAT也采用PID机制进行采样发布, 都能实现user级的隐私保护; 不同的是, 两者的PID反馈公式设计不同; 同时, FAST是一种实时处理方案, 而DSAT是离线数据处理方案.
4.2 分布式数据流阈值函数的持续监控保护上述所有方案是基于简单聚集函数的持续监控保护方案.在数据流的实时监控任务中, 往往存在一些复杂的统计分析任务(如阈值函数监控), 也需要对其进行隐私保护.文献[55, 56]以分布式数据流为应用场景, 分别对数据流中元素信息增益值的阈值函数和统计值列表中r百分位值的阈值函数进行持续监控保护.问题可以抽象化为f(·) > τ, f(·)表示基于计数的统计任务, τ表示阈值.在文献[55]中, f(·)表示某元素的信息增益值的持续计算; 在文献[56]中, 则表示对基于所有分布式站点生成的统计值列表中不小于r%个列表元素的最小值的持续计算.阈值函数监控就是持续监控上述统计值是否大于提前设定的阈值τ.
文献[55]中信息增益阈值函数的持续监控以垃圾邮件关键词监控场景为例, 描述如下:假设存在k个分布式站点, 1个中心节点, 持续监控关键词t在各分布式数据流滑动窗口(宽度为W)内的邮件中出现的信息增益值
由于统计过程中涉及到用户隐私, 需设计隐私保护方案.两个方案的核心策略都是采用Safe Zone(安全区域)局部约束技术[57]来最大化时间序列上的隐私预算的利用率, 并且降低各分布式节点与中心节点的通信代价, 延长差分隐私下持续监控生命期.因此, 用Safe Zone代表两种方案, 其基本思想:将中心节点的整体监控条件转换成一组各分布式站点的局部约束条件(被称为安全区域).如果每个分布式站点的局部统计值在安全区域内, 则表示近期的统计值变化不大, 不需要中心节点进行通信, 节约了一定的隐私预算; 否则, 花费一定的隐私预算将各分布式站点的局部统计值发送到中间节点, 中间结点计算并进行判断.虽然两个方案都采用Safe Zone技术实现, 但文献[55]采用球状安全区域, 在每个时间间隔做隐私保护处理时, 对球状区域半径初始化、各分步式站点与中心节点通信的统计信息和中心节点的信息增益值判断这3个过程都添加了拉普拉斯噪声对其隐私进行保护.文献[56]则采用设置一组安全区间{[li(t1), ri(t1)]}(1≤i≤θ), li和ri对应i区间的左右临界值.做隐私保护处理时, 对安全区间的左右临界值分别加拉普拉斯噪声, 然后采用指数机制确定各分布式站点统计值所属的安全区间.最后, 中心节点根据各分布式站点发送的安全区间索引号进行阈值判断.
上述两种方案采用Safe Zone技术与拉普拉斯机制或指数机制相结合, 不仅降低了通信量, 也延长了持续监控生命期.持续监控保护方案满足user级差分隐私保护.两个方案的缺点是只能进行有限长的持续监控, 如何实现无限长分布式数据流的持续监控保护, 依然是具有挑战性的研究问题.
4.3 集值对的增量更新发布保护方案针对集值的持续发布问题, 文献[58]提出一种增量更新发布隐私保护方案IncBuildTBP, 可满足的user级隐私保护.方案采用基本隐私预算分配方案:设定数据库更新发布次数上限为U, 每次发布分配隐私预算ε/(U+1).由于集值对发布问题敏感度很高, 文献借助一棵基于划分的分类树TBP-Tree来对庞大的集值对输出空间进行压缩, 以降低集值对发布问题的高敏感度; 同时, 由于每次更新可能会产生大量值为0的空节点, 为空节点分配隐私预算会影响发布数据的可用性, 所以每次更新都对这些节点进行剪枝, 以提高发布数据的可用性.文献虽然实现了集值数据的动态的差分隐私发布, 但是发布结果的可用性比较低, 并且只能实现离线数据的处理.
4.4 轨迹发布的差分隐私保护方案轨迹是具有时序关系的位置序列, 攻击者通过对用户位置的持续监控(轨迹的监控), 可以获取隐私信息.现有轨迹数据发布的差分隐私保护方案都是针对离线轨迹数据集, 经差分隐私保护处理后, 发布“净化版”的轨迹数据, 隐私保护级别为user级.攻击者通过监控发布的轨迹信息, 无法获得个体隐私.在该问题中, 假设所有位置总数为m, 轨迹最大长度为l, 则可能生成的轨迹数目最多为
文献[59]提出一种轨迹发布的隐私保护方案Perfix, 方案采用前缀树对输出空间进行压缩并添加噪声, 发布净化版的轨迹数据集.其基本思想是:假设很多轨迹数据具有相同前缀, 将所有具有相同前缀的轨迹分到前缀树的同一个分支上, 从而避免隐私预算的重复分配.根据前缀树的高度h, 隐私预算ε被平均分配到各层, 每层所分配的隐私预算ε/h, 从根节点到各层每个节点都对应一条轨迹, 每个节点的计数加上满足
了提高发布效率, 方案采用阈值剪枝策略, 尽早删除不能继续扩展的分支节点.由于噪声计数会违背一致性约束, 方案利用前缀树父子节点之间的约束关系对计数值进行了一致性处理, 进一步提高了发布结果的可用性.如果位置空间域较小, 前缀树高度较低, Perfix方案发布结果的可用性较好; 如果空间域较大, 前缀树高度增加, 被划分到同一分支的轨迹将大幅度减少, 因此造成发布结果的可用性变低.
为解决Perfix方案的问题, 文献[60]提出了改进的轨迹发布方案N-Grams, 核心思想是:采用变长n-gram模型和马尔可夫模型来发布轨迹数据库.首先, 基于轨迹数据库, 采用n-gram(n≤nmax)模型统计空间域中位置之间的转移概率, 并记录在自定义的数据结构-探索树中(前缀树结构, 高度为nmax).隐私预算分配方案如下:和Perfix分配方案一样, 探索树每一层节点初始化分配的隐私预算ε/nmax.但由于探索树很多分支长度不够nmax, 为提高隐私预算利用率, 从第2层的节点开始, 方案对当前节点所在分支的底层长度hv预测, 根据预测值, 将剩余隐私预算平均分配到该分支剩下的几层节点中, 每层节点分配到的隐私预算会有增加, 从而能提高了发布结果的可用性.在发布轨迹时, 长度不大于nmax的轨迹通过遍历探索树进行发布, 长度超出nmax的轨迹则采用马尔可夫模型预测其计数.由于探索树的高度远远小于Perfix中前缀树的高度, 该方案解决了前缀树过高带来的低可用性问题.但由于探索树只记录最大长度受限的轨迹的n-gram信息, 造成了一定的信息丢失, 影响发布结果的可用性.
Prefix和N-Grams方案都是基于轨迹中有相同前缀的前提下, 采用n-gram或前缀树对输出空间进行压缩, 来提高发布数据的可用性.然而, 由于轨迹的异质性, 很少轨迹有相同的前缀, Cluster[61, 62]在取消上述假设的前提下, 设计一种基于聚类的轨迹发布保护方案.该方案的核心思想是:首先, 采用指数机制对同一时间的位置进行差分隐私下聚类, 每个时间对应的位置聚类为k类; 然后, 基于聚类后的位置发布轨迹数据集.经过聚类, 轨迹输出空间大大降低, 从而也降低了发布的敏感度, 提高了可用性.
文献[63-65]则提出:利用二维空间的参照系统来缩小轨迹输出空间, 降低发布敏感度.Homogeneous[63]采用同质参照系统来对用户轨迹进行采样, 降低位置空间中位置之间转移的规模.参照系统中, 如果设置的粒度越大, 轨迹输出空间就越小; 反之越大.如将二维空间划分为网格, 基于网格参照系统抽样轨迹, 网格越大, 轨迹就越短, 轨迹的输出空间就越小; 反之越大.由于同质的参照系统不能很好地反映用户不同速度的轨迹模式, 也会造成一定的信息丢失, 对此, Hierarchical[64]提出建立层次参照系统HRS来捕捉用户不同速度的轨迹, 速度较快的轨迹模式采用粗粒度的参照系统进行抽样, 速度较慢的采用细粒度的参照系统.基于HRS对位置空间域进行离散化, 对每种参照系统维护一个轨迹前缀树模型.为使这组前缀树更好地体现轨迹特点, 方案根据轨迹数据库设计了满足隐私保护的模型选择机制, 其任务是从这组前缀树模型中选择合适的前缀树表示不同速度的轨迹; 同时, 对选择的前缀树模型设计更合适的树高和节点间的转移概率, 添加拉普拉斯噪声以满足隐私保护要求.最后, 方案采用基于方向的权重抽样技术修复添加噪声后的轨迹的方向性信息, 进一步提高了发布结果的可用性. Hierarchical和文献[63]方案中的参照系统都是基于空间区域的网格划分, 然后基于网格的关键点(achor)对轨迹进行抽样.两种方案的参照系统都没有做隐私保护, 对此, PTCP[65]提出对参照系统聚类后, 对聚类后的achors添加拉普拉斯噪声保护.然后, 基于achors对轨迹抽样, 基于前缀树结构实现轨迹数据发布的差分隐私保护.
4.5 User级隐私保护方案小结本小节对所有user级隐私保护方案从其优缺点、监控任务类型和面向的发布任务等几个方面进行总结和对比分析(见表 3), 然后指出现有方案的不足及未来研究趋势.
|
|
Table 3 Comparation of schemes on user-level privacy under continual monitoring 表 3 持续监控下user级隐私方案的对比分析 |
(1) 在简单聚集统计信息的持续发布方案中, 为最大化时间序列上的隐私预算利用率, 大部分方案采用抽样技术来提高发布结果的可用性, 其原理是结合时序数据的特点, 选出代表性的发布点进行发布, 降低发布次数, 增大每个发布点所分配的隐私预算.但这种方案只是延长持续监控生命期, 持续监控数据流长度依然有限.如何能实现对无限长动态数据的持续监控保护, 是需要解决的问题;
(2) 在分布式数据流持续监控保护中, 现有的持续监控保护方案为延长持续监控保护期, 采用一系列将全局监控条件转换为局部监控条件的分解技术.但这些技术的时间和空间复杂度很高, 极大降低了分布式数据流处理效率.可以对分解技术作进一步的改进处理, 如:基于凸分解或滤波技术提高分解效率; 也可以基于衰减模型的数据流处理模型设计基于隐私衰减的隐私保护方案, 实现对无限长数据流的处理;
(3) 在轨迹数据的发布问题中, 由于发布任务的输出空间太大, 对其进行隐私保护的敏感度和复杂度很高.所以现有轨迹数据的发布方案提出了各种降低输出空间, 降低发布任务敏感度的策略, 如:基于前缀树、n-gram模型和马尔可夫模型、聚类和参照系统等技术来缩小输出空间后, 对其进行差分隐私处理.现有方案发布结果的可用性与实际应用仍有一定的差距, 进一步提高发布结果可用性是值得继续研究的问题.同时, 所有方案都是离线轨迹数据的处理, 对于实时轨迹数据的差分隐私发布是值得下一步研究的问题;
(4) 所有user级隐私保护方案也分为实时在线处理和离线处理两种方式.除FAST和SafeZone可以进行在线数据流的处理, 其余所有方案都为离线数据处理.同时, 大多数持续监控任务还都是基于count的简单统计, 但实际应用中往往存在一些复杂的数据分析任务.静态数据集上已有针对这些复杂分析任务的差分隐私保护研究工作[66-70], 但持续监控下的相关工作还很少.因此, 持续监控下差分隐私保护与复杂监控任务的结合还有待进一步的研究.
5 持续监控下w-event隐私保护方案从隐私保护强度上看, w-event隐私是介于user级隐私和event隐私之间的一种隐私保护方案, 本节对持续监控下w-event隐私保护方案进行总结和分析.
5.1 w-event级隐私保护方案针对第4.1节中的简单聚集统计信息持续监控保护问题, 文献[21]提出了两种满足w-event ε-差分隐私的保护方案:BA和BD.两种方案都能实现对无限长数据流的持续监控保护.根据第1.2.3节中的w-event ε-差分隐私定义, 为保证ε隐私, 在时间序列上的任意w滑动窗口内, 分配的隐私预算都必须小于等于ε.隐私预算的基本分配方案是将ε平均分配到每个窗口内的w个时间点上, 每个点的隐私预算为ε/w.但该分配方案数据可用性较低, 为提高滑动窗口内的隐私预算利用率, 方案也采用了采样发布策略, 即选出窗口内有代表性的时间点(数据变化较大)作为主动发布点, 只有主动发布点上才分配隐私预算; 其他时刻做被动发布, 不分配隐私预算.两种隐私保护方案都包含两个核心过程, 分别是相邻时刻发布值的相似性计算过程和差分隐私发布过程.隐私预算被平均分配到两个过程:ε=ε1+ε2, ε1=ε/2用于数据相似性计算; ε2=ε-ε1用作差分隐私发布.
BD(隐私预算指数机制分配)和BA(隐私预算吸收)都基于上述两个基本过程实现, 不同的是窗口内每个采样点的隐私分配方案有区别.下面分别介绍两种方案的具体实现.
BD方案的特点是将ε1平均分配到每个窗口内的w个时间点上, 对于每个时间i, 用εi, 1=ε/(2·w)做相邻时间数据相似性的计算.如果变化够大, 则将ε2按指数递减方式分配给采样点, 每个采样点i得到εi, 2=εrm/2.计算方法是:先找出当前活动窗口[i-w+1, i]内还可用的隐私预算
而在BA方案中, 用于相似性计算的隐私预算分配方案与BD方案相同, 窗口内每个时间点的εi, 1=ε/(2·w); 但窗口内用于差分隐私发布的隐私预算分配方案与BD不同.BA将用于发布的隐私预算ε2先初始化平均分配到窗口内的各时间点上εi, 2=ε/(2·w).如果某个时间点i数据变化不大, 则该时间点的εi, 2被节约下来, 重新设置εi, 2=0;节约下的隐私预算用于被后续采样点吸收, 以提高后续发布时刻结果的可用性.如果i数据变化大, 则计算在该时刻可以吸收的隐私预算, 然后加上i上已有的隐私预算进行发布.图 12的BA方案示例中, 时刻2是被动发布, 所以该时刻的发布预算由ε/6变为0;时刻3采样发布点吸收了时刻2的隐私预算, 因此隐私预算由ε/6变为了ε/3.在BA方案中, 有两种被动发布状态:一是skipped点, 表示数据变化不大需被动发布; 二是nullified点, 表示因窗口内隐私预算用完而被动发布.如图 12的BA示例中, 由于时刻3吸收了时刻2隐私预算, 所以时刻4即使数据变化较大, 但由于没有可以分配的隐私预算, 也做了被动发布.BA方案的缺点是会出现预算使用完而某些时间点没有隐私预算只能做被动发布的情况.两个方案共同的缺点是时序上隐私预算分配不均衡, 造成每个发布时刻发布结果添加的噪声量不一致.
文献[71]面向无限轨迹流的数据发布提出了一种满足w-event的隐私保护方案GA+MMD.该方案基本思想和BD基本相同, 但对其做出了以下两个改进:一是考虑了每个用户对个体轨迹长度的隐私保护强度不同, 所以提出了个性化轨迹长度li的隐私保护要求, 在窗口内的每个时刻, 用于相似性计算的隐私预算为ε1/lmax, lmax是所有用户中最长的轨迹隐私长度, 每个时刻用于发布的隐私预算εi, 2还是采用指数递减的形式进行分配; 二是与BD方案中被动发布时刻采用相邻时刻的发布结果代替不同, GA+MMD中采用贪心算法找出活动窗口内与该时刻发布结果最相近的结果进行被动发布.通过上述两种策略, GA+MMD进一步提高了发布结果的可用性.但方案中对用户的个性化隐私处理比较简单, 如何结合现有的个性化差分隐私方案[72-74]实现真正的持续监控下的个性化的轨迹发布, 值得进一步研究.
5.2 w-event级隐私保护方案的对比分析本节先从主要优缺点上对持续监控下w-event隐私保护方案进行对比分析(见表 4), 然后指出现有方案不足及未来研究趋势.
|
|
Table 4 Comparation of schemes on w-event privacy under continual monitoring 表 4 持续监控下w-event隐私保护方案对比分析 |
目前, w-event隐私保护方案相对较少.上述3种方案都可以实现对无限长数据流的持续监控保护, 其保护强度介于event级别和user级别隐私之间.3种方案的实现核心都是考虑如何在w滑动窗口内提高隐私预算的利用率, 提高发布结果的可用性.但都存在以下缺点:时序上隐私预算不能充分利用, 如何充分利用隐私预算, 提高持续发布结果可用性, 是值得进一步研究的问题; 同时, 这些方案都是面向简单聚集统计信息的持续监控保护, 如何拓展相应方案到更复杂的持续监控任务中值得进一步研究.
6 未来研究展望本节探讨持续监控下差分隐私保护的未来研究展望, 主要分为持续监控下面向分布式数据流的隐私保护研究、持续监控下差分隐私算法通用评价标准的研究、持续监控下关联数据发布的隐私保护研究、持续监控下面向复杂统计任务的隐私保护研究、持续监控下个性化差分隐私保护研究和持续监控下本地化差分隐私保护研究.
6.1 持续监控下面向分布式数据流的隐私保护研究大数据环境下, 很多持续监控场景都是基于分布式数据流的实时处理, 如Web网页的用户点击、网络入侵检测、heavy hitter实时监控和智能基础设施的实时监控等.在这些应用中, 隐私保护问题非常重要.目前虽然已有一些分布式数据流持续监控保护方案, 如垃圾邮件关键词的持续监控、r百分位值的持续监控等, 但方案还很少.持续监控下分布式数据流统计的隐私保护研究应考虑了以下问题:一是对局部节点的统计过程做隐私保护; 二是对中心节点的计算过程做隐私保护; 三是要尽量延长持续监控生命期并降低局部站点与中心节点的总通信量.为解决上述问题, 现有方案大多先对局部节点和中心节点的计算过程采用噪声机制进行隐私保护, 然后采用安全区域分解技术将中心站点的全局监控条件转换为各分布式站点的局部监控条件, 只有违反局部监控条件的情况下才分配隐私预算和中心节点通信, 从而降低总通信量和隐私预算分配次数.分布式数据流持续监控保护可从以下几个方面进行研究:一是现有方案中分解技术的时间复杂度和空间复杂度很高, 可以进一步改进; 二是现有方案都是基于对元素精确统计算法做隐私保护处理, 由于数据流的处理对时间和空间有严格要求, 现有很多数据流处理算法都基于近似技术的统计, 如滑动窗口技术、随机采样技术和sketch技术等, 可以考虑基于这些算法做隐私保护处理, 使得持续监控隐私保护方案更符合实际监控场景要求; 三是目前很多分布式数据流的持续监控任务如分布式数据流的top-k元素监控、网络流量的异常检测、分布式数据流的频繁模式监控等, 目前都还没有相关研究.因此, 持续监控下分布式数据流统计任务的隐私保护是未来的一个研究方向.
6.2 持续监控下差分隐私算法通用评价标准的研究在对持续监控下差分隐私发布方案进行评价时, 现有方案提出了不同的参数设置以及评估标准.如在面向简单聚集统计发布的持续监控保护方案中, 虽然都采用发布结果的误差上界进行评估, 却没有考虑相同的评估条件, 如采用的实验数据集是否一样, 设定的空间约束条件是否一样、算法中一些通用参数(如ε)的设置和调整是否一致.上述因素都会影响算法的评估性能, 目前, 这些方案缺乏在统一标准下的相关评估.在面向复杂任务的持续监控保护方案中, 为提高发布结果可用性, 通常利用数据依赖关系降低噪声.但数据集不同, 数据依赖关系也不一样, 导致发布结果误差不同.因此, 这类隐私保护方案都不包含发布结果误差的对比分析.在实际方案部署时, 没有统一的方案对比分析, 如何选择一个更好的方案面临重大挑战.开发通用的评价标准对于这类方案也尤为重要.在通用标准的制定中, 不仅应考虑通用参数的调整与设置、数据集的特点对发布结果的影响, 同时要考虑多样化多角度的评估标准, 考虑各种发布问题的情况.所以, 持续监控下通用差分隐私算法标准的研究是一个未来研究方向.
6.3 持续监控下关联数据发布的隐私保护研究现有的持续监控下隐私保护方案中, 已有一些关联数据发布的隐私保护研究.如在位置发布的event级别保护方案中考虑了时序上用户位置之间关联, 并对此进行建模, 依据模型对关联关系所造成的隐私泄露量进行分析, 降低位置持续发布任务的敏感度.在简单聚集信息发布的user级别保护方案中, 基于时序数据关联, 利用滤波技术提高了发布结果的可用性.在轨迹数据发布问题中, 基于时序上用户位置之间关系的假设前提, 降低了发布问题的敏感度.针对实际问题中数据关联关系建模, 根据模型设计持续监控下隐私保护方案.该类方案具有以下优点:一是更符合真实的应用场景; 二是能抵御攻击者具备这些关联信息的攻击, 隐私保护更强; 三是根据模型的发布往往可以降低发布问题的敏感度, 可用性更高.目前, 持续监控下该类研究工作还较少, 方案中对数据关联性的建模方法也比较单一.针对相关数据的隐私保护问题, 已有研究工作提出了面向语义的差分隐私保护模型Pufferfish和Blowfish.在持续监控场景下, 针对特定监控问题中的关联数据, 建立多样化的时序数据关联模型, 基于面向语义的差分隐私保护模型, 设计更灵活且具有语义的隐私保护方案是一个未来的研究方向.
6.4 持续监控下面向复杂分析任务的隐私保护研究现有的持续监控下差分隐私保护研究大都是基于count计数的简单统计和分析任务.面向复杂分析任务的持续监控保护研究不仅方案少, 发布结果可用性也有待进一步提高.实际应用场景中往往存在更多的复杂监控任务, 如频繁模式和频繁序列模式监控、持续分类和聚类监控等, 这类持续监控任务暂时没有相关研究.持续监控下面向复杂分析任务的隐私保护研究具有以下两个难题:一是复杂分析任务本身输出结果空间就比较大, 发布敏感度和复杂度比较高, 如何降低发布任务的敏感度, 提高发布结果的可用性是一个难题; 二是在时序上, 随着时间的增加, 发布结果的噪声会累积增加, 发布结果可用性逐渐变差.针对第一个难题, 可以对未作隐私保护的原始算法进行分析, 根据算法所采用的数据结构及处理过程, 计算其敏感度; 同时, 可改进相关任务在静态数据集上已有的降低敏感度技术[66-70], 使其适用于动态发布环境.通过以上策略, 提高发布结果的可用性.针对第二个难题, 可以考虑利用时序上的数据依赖关系, 自适应分配时序上的隐私预算, 提高隐私预算的利用率.复杂分析任务的持续监控保护研究是未来的一个研究方向.
6.5 持续监控下个性化差分隐私保护研究在持续监控场景中, 通常参与者对自己的数据有不同的隐私要求, 用统一要求来处理所有参与者的信息, 可能对一些用户来说隐私保障太低, 而对另外一些用户又可能要求太高.因此, 如何结合用户隐私需求, 让用户定义个人的隐私级别, 是一个值得研究的问题[72-74].持续监控下, 个性化的隐私保护研究需要考虑以下问题:一是不同用户具有不同的隐私保护要求; 二是对同一用户, 不同的项目也会有不同的隐私保护要求; 三是持续监控下, 随着时间的推移, 用户和项目的隐私级别也会有相应的变化.个性化差分隐私的隐私保护级别跟隐私预算大小相关, 隐私预算越小, 隐私保护强度越高; 隐私预算越大, 隐私保护强度越低.在该类研究中, 如何针对多个隐私预算, 采用随机响应技术或噪声机制等差分隐私实现技术, 设计满足所有隐私预算要求的实现方案是重点问题.
6.6 持续监控下本地化差分隐私保护研究目前, 持续监控下的差分隐私保护都是基于中心化差分隐私保护技术实现, 该技术的前提是数据收集者必须是可信的第三方.随着智能基础设施的普及和GPS定位技术的应用, 现有持续监控下的应用场景多为分布式的应用.在这种场景下, 数据的收集往往类似于问卷调查, 数据的管理者往往是不可信的第三方.同时, 由于分布式场景中收集的数据量特别大并且计算代价非常高, 中心化的差分隐私技术不适合这种场景.目前, 一些研究工作[75, 76]提出了本地化差分隐私技术(LDP)方案, 通过采用随机响应技术对个体数据进行正向和负向的扰动, 最终通过聚合大量的扰动结果来抵消添加在其中的正负向噪声, 从而得到有效的统计结果.如何将LDP技术应用到持续监控下的数据发布和分析任务中, 是未来值得研究的一个方向.
7 结束语随着信息技术的发展及物联网技术的兴起, 出现了越来越多的持续监控应用场景.在这些场景中, 如何对参与者持续分享的数据进行隐私保护面临重大挑战.本文对持续监控下差分隐私保护领域已有的研究成果进行了总结, 首先介绍了持续监控下隐私保护模型, 包括不同保护级别的差分隐私模型定义、实现机制和持续监控下差分隐私保护方案的评估原则; 然后重点对event级、user级和w-event级这3种隐私保护级别的方案进行总结和分析.在对已有研究成果深入对比分析的基础上, 指出了持续监控下差分隐私保护的未来研究方向.持续监控下差分隐私保护的研究成果还较少, 仍有诸多关键问题需要进一步的研究.希望本文工作可以为持续监控下差分隐私保护的相关研究人员提供参考.
| [1] |
Ghayyur S, Chen Y, Yus R, Machanavajjhala A, Hay M, Miklau G, Mehrotra S. IoT-Detective: Analyzing IoT data under differential privacy. In: Proc. of the 2018 Int'l Conf. on Management of Data Conf. (SIGMOD). ACM, 2018. 1725-1728.[doi: 10.1145/3183713.3193571]
|
| [2] |
Dwork C. Differential privacy and the US census. In: Proc. of the 38th ACM SIGMOD-SIGACT-SIGAI Symp. on Principles of Database Systems (PODS). ACM, 2019. 1.[doi: 10.1145/3294052.3322188]
|
| [3] |
Samarati P, Sweeney L. Generalizing data to provide anonymity when disclosing information. In: Proc. of the 17th ACM SIGACT- SIGMOD-SIGART Symp. on Principles of Database Systems (PODS). ACM, 1998. 188.[doi: 10.1145/275487.275508]
|
| [4] |
Machanavajjhala A, Kifer D, Gehrke J, Venkitasubramaniam M. l-Diversity: Privacy beyond k-anonymity. ACM Trans. on Knowledge Discovery from Data (TKDD), 2007, 1(1): 3.[doi: 10.1145/1217299.1217302]
|
| [5] |
Li N, Li T, Venkatasubramanian S. 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]
|
| [6] |
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] |
| [7] |
Zhu TQ, Li G, Zhou WL, Yu PS. Differential privacy and applications. In: Proc. of the Advances in Information Security, Vol.69. 2017.[doi: 10.1007/978-3-319-62004-6]
|
| [8] |
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.
|
| [9] |
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] |
| [10] |
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.
|
| [11] |
Camacho J, Garcia-Teodoro P, Maciá-Fernández G. Traffic monitoring and diagnosis with multivariate statistical network monitoring: A case study. In: Proc. of the IEEE Symp. on Security and Privacy Workshops. 2017. 241-246.[doi: 10.1109/SPW.2017.11]
|
| [12] |
Dwork C, Pappas GJ. Privacy in information-rich intelligent infrastructure. CoRR abs/1706.01985, 2017.
|
| [13] |
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] |
| [14] |
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] |
| [15] |
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.
|
| [16] |
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] |
| [17] |
Calandrino JA, Kilzer A, Narayanan A, Felten EW, Shmatikov V. You might also like: Privacy risks of collaborative filtering. In: Proc. of the IEEE Symp. on Security and Privacy. IEEE, 2011. 231-246.[doi: 10.1109/SP.2011.40]
|
| [18] |
Dwork C. Differential privacy. In: Proc. of the 2nd ACM Workshop on Security of Ad Hoc and Sensor Networks (ICALP). ACM, 2006. 88-93.[doi: 10.1007/11787006.1]
|
| [19] |
Dwork C. Differential privacy in new settings. In: Proc. of the 21st Annual ACM-SIAM Symp. on Discrete Algorithms (SODA). ACM, 2010. 174-183.[doi: 10.1137/1.9781611973075.16]
|
| [20] |
Dwork C, Naor M, Pitassi T, Rothblum GN. Differential privacy under continual observation. In: Proc. of the 42nd ACM Symp. on Theory of Computing (STOC). ACM, 2010. 88-93.[doi: 10.1145/1806689.1806787]
|
| [21] |
Kellaris G, Papadopoulos S, Xiao XK, Papadias D. Differentially private event sequences over infinite streams. Proc. of the VLDB Endowment, 2014, 7(12): 1155-1166.[doi: 10.14778/2732977.2732989]
|
| [22] |
Dwork C, McSherry F, Nissim K, Smith A. Calibrating noise to sensitivityin private data analysis. In: Proc. of the Theory of Cryptography Conf. (TCC). Springer-Verlag, 2006. 265-284.[doi: 10.1007/11681878_14]
|
| [23] |
McSherry F, Talwar K. Mechanism design via differential privacy. In: Proc. of the 48th Annual IEEE Symp. on Foundations of Computer Science (FOCS). IEEE, 2007. 94-103.[doi: 10.1109/FOCS.2007.66]
|
| [24] |
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] |
| [25] |
Chan THH, Shi E, Song D. Private and continual release of statistics. ACM Trans. on Information and System Security, 2011, 14(3): 26: 1-26: 24.[doi: 10.1145/2043621.2043626]
|
| [26] |
Bolot J, Fawaz N, Muthukrishnan S, Nikolov A, Taft N. Private decayed predicate sums on streams. In: Proc. of the 16th Int'l Conf. on Database Theory (ICDT). ACM, 2013. 284-295.[doi: 10.1145/2448496.2448530]
|
| [27] |
Dwork C, Naor M, Reingold O, Rothblum GN. Pure differential privacy for rectangle queries via private partitions. In: Proc. of the Int'l Conf. on the Theory and Application of Cryptology and Information Security (ASIACRYPT). Springer-Verlag, 2015. 735-751.[doi: 10.1007/978-3-662-48800-3_30]
|
| [28] |
Chen Y, Machanavajjhala A, Hay M, Miklau G. PeGaSus_ Data-Adaptive differentially private stream. In: Proc. of the 2017 ACM Conf. on Computer and Communications (CCS). ACM, 2017. 1375-1388.[doi: 10.1145/3133956.3134102]
|
| [29] |
Cao JN, Xiao Q, Ghinita G, Li NH. Efficient and accurate strategies for differentially-private sliding window queries. In: Proc. of the 16th Int'l Conf. on Extending Database Technology (EDBT). ACM, 2013. 191-202.[doi: 10.1145/2452376.2452400]
|
| [30] |
Chen R, Shen YL, Jin HX. Private analysis of infinite data streamsvia retroactive grouping. In: Proc. of the 24st ACM Int'l Conf. on Informationand Knowledge Management (CIKM). ACM, 2015. 1061-1070.[doi: 10.1145/2806416.2806454]
|
| [31] |
Chan THH, Li MF, Shi E, Xu WC. Differentially private continual monitoring of heavy hitters from distributed streams. In: Proc. of the Int'l Symp. on Privacy Enhancing Technologies Symp. (PETS). ACM, 2012. 140-159.[doi: 10.1007/978-3-642-31680-7_8]
|
| [32] |
Misra J, Gries D. Finding repeated elements. Science of Computer Programming, 1982, 2(2): 143-152.
[doi:10.1016/0167-6423(82)90012-0] |
| [33] |
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] |
| [34] |
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.
|
| [35] |
Mir DJ, Muthukrishnan S, Nikolov A, Wright RN. Pan-Private algorithms via statistics on sketches. In: Proc. of the 30th ACM SIGMOD-SIGACT-SIGART Symp. on Principles of Database Systems (PODS). ACM, 2011. 37-48.[doi: 10.1145/1989284.1989290]
|
| [36] |
Xiao YH, Xiong L. Protecting locations with differential privacy under temporal correlations. In: Proc. of the ACM Conf. on Computer and Communications Security (CCS). ACM, 2015. 1298-1309.[doi: 10.1145/2810103.2813640]
|
| [37] |
Xiao YH, Xiong L, Zhang S, Cao Y. LocLok: Location cloaking with differential privacy via hidden Markov model. Proc. of the VLDB Endowment (PVLDB), 2017, 10(12): 1901-1904.[doi: 10.14778/3137765.3137804]
|
| [38] |
Cao Y, Yoshikawa M, Xiao YH, Xiong L. Quantifying differential privacy under temporal correlations. In: Proc. of the 2017 IEEE 33rd Int'l Conf. on Data Engineering (ICDE). IEEE, 2017. 821-832.[doi: 10.1109/ICDE.2017.132]
|
| [39] |
Kifer D, Machanavajjhala A. Pufferfish: A framework for mathematical privacydefinitions. ACM Trans. on Database Systems, 2014, 39(1): 3: 1-3: 36.[doi: 10.1145/2514689]
|
| [40] |
Song S, Wang YZ, Chaudhuri K. Pufferfish privacy mechanisms for correlated data. In: Proc.of the 2017 ACM Int'l Conf. on Management of Data (SIGMOD). ACM, 2017. 1291-1306.[doi: 10.1145/3035918.3064025]
|
| [41] |
He X, Machanavajjhala A, Ding B. Blowfish privacy: Tuning privacy-utility tradeoffsusing policies. In: Proc. of the 2014 SIGMOD Int'l Conf. on Management of Data (SIGMOD). ACM, 2014. 1447-1458.[doi: 10.1145/2588555.2588581]
|
| [42] |
Zhu T, Xiong P, Li G, Zhou W. Correlated differential privacy: Hiding information innon-iid data set. IEEE Trans. on Information Forensics and Security, 2015, 10(2): 229-242.[doi: 10.1109/TIFS.2014.2368363]
|
| [43] |
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] |
| [44] |
Rastogi V, Nath S. Differentially private aggregation of distributedtime-series with transformation and encryption (DFT). In: Proc. of the 2010 ACM SIGMOD Int'l Conf. on Management of Data (SIGMOD). ACM, 2010. 735-746.[doi: 10.1145/1807167.1807247]
|
| [45] |
King M. Process Control: A Practical Approach. Chichester: U.K.Wiley, 2010.[doi: 10.1002/9780470976562.ch6]
|
| [46] |
Fan LY, Xiong L. An adaptive approach to real-time aggregate monitoring with differential privacy. IEEE Trans. on Knowledge & Data Engineering, 2014, 26(9): 2094-2106.[doi: 10.1109/TKDE.2013.96]
|
| [47] |
Fan LY, Xiong L, Sunderam VS. Differentially private multi-dimensional time series release for traffic monitoring. In: Proc. of the IFIP Annual Conf. on Data and Applications Security and Privacy (DBSec). Springer-Verlag, 2013. 33-48.[doi: 10.1007/978-3-642-39256-6_3]
|
| [48] |
Fan LY, Bonomi L, Xiong L, Sunderam VS. Monitoring Web browsing behavior with differential privacy. In: Proc. of the 23rd Int'l Conf. on World Wide Web (WWW). ACM, 2014. 177-188.[doi: 10.1145/2566486.2568038]
|
| [49] |
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] |
| [50] |
Le Ny J, Mohammady M. Differentially private MIMO filtering for event streams. IEEE Trans. on Automatic Control, 2018, 63(1): 145-157.[doi: 10.1109/TAC.2017.2713643]
|
| [51] |
Le Ny J, Touati A, Pappas GJ. Real-Time privacy-preserving model-based estimation of traffic flows. In: Proc. of the 2014 Int'l Conf. on Cyber-Physical Systems (ICCPS). ACM/IEEE, 2014. 92-100.[doi: 10.1109/ICCPS.2014.6843714]
|
| [52] |
Andre H, Le Ny J. A differentially private ensemble Kalman filter for road traffic estimation. In: Proc. of the Int'l Conf. on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2017. 6409-6413.[doi: 10.1109/ICASSP.2017.7953390]
|
| [53] |
Wang J, Zhu RB, Liu SB. A differentially private unscented Kalman filter for streaming data in IoT. In: Proc. of the IEEE Access 6. 2018. 6487-6495.[doi: 10.1109/ACCESS.2018.2797159]
|
| [54] |
Li HR, Xiong L, Jiang XQ, Liu JF. Differentially private histogram publication for dynamic datasets: An adaptive sampling approach. In: Proc. of the 24th ACM Int'l Conf. on Information and Knowledge Management (CIKM). ACM, 2015. 1001-1010.[doi: 10.1145/2806416.2806441]
|
| [55] |
Friedman A, Sharfman I, Keren D, Schuster A. Privacy-Preserving distributed stream monitoring. In: Proc. of the 2014 Network and Distributed System Security (NDSS) Symp. 2014. 1-14.[doi: 10.14722/ndss.2014.23128]
|
| [56] |
Sun JC, Zhang R, Zhang JX, Zhang YC. PriStream: Privacy-preserving distributed stream monitoring of thresholded PERCENTILE statistics. In: Proc. of the 35th Annual IEEE Int'l Conf. on Computer Communications (INFOCOM). IEEE, 2016. 1-9.[doi: 10.1109/INFOCOM.2016.7524461]
|
| [57] |
Keren D, Sharfman I, Schuster A, Livne A. Shape sensitivegeometric monitoring. IEEE Trans. on Knowledge and Data Engineering, 2012, 24(8): 1520-1535.[doi: 10.1109/TKDE.2011.102]
|
| [58] |
Zhang XJ, Meng XF, Chen R. Differentially private set-valued data releaseagainst incremental updates. In: Proc. of the Int'l Conf. on Database Systems for Advanced Applications (DASFAA). Springer-Verlag, 2013. 392-406.[doi: 10.1007/2F978-3-642-37487-6_30]
|
| [59] |
Chen R, Fung BCM, Desai BC, Sossou NM. Differentially private transit data publication: A case study on the Montreal transportation system. In: Proc. of the 18th ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining (KDD). ACM, 2012. 213-221.[doi: 10.1145/2339530.2339564]
|
| [60] |
Chen R, Ács G, Castelluccia C. Differentially private sequential data publicationvia variable-length N-grams. In: Proc. of the ACM Conf. on Computer and Communications Security (CCS). ACM, 2012. 638-649.[doi: 10.1145/2382196.2382263]
|
| [61] |
Hua JY, Gao Y, Zhong S. Differentially private publication of general time-serial trajectory data. In: Proc. of the 2015 IEEE Conf. on Computer Communications (INFOCOM). IEEE, 2015. 549-557.[doi: 10.1109/INFOCOM.2015.7218422]
|
| [62] |
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] |
| [63] |
Pelekis N, Gkoulalas-Divanis A, et al. Privacy-Aware querying over sensitive trajectory data. In: Proc. of the 20th ACM Conf. on Information and Knowledge Management (CIKM). ACM, 2011. 895-904.[doi: 10.1145/2063576.2063706]
|
| [64] |
He X, Cormode G, Machanavajjhala A, et al. DPT: Differentially private trajectory synthesis using hierarchical reference systems. Proc. of the VLDB Endowment (PVLDB), 2015, 8(11): 1154-1165.[doi: 10.14778/2809974.2809978]
|
| [65] |
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] |
| [66] |
Su S, Xu SZ, et al. Differentially private frequent itemset mining via transaction splitting. In: Proc. of the 2016 IEEE 36rd Int'l Conf. on Data Engineering (ICDE). IEEE, 2016. 1564-1565.[doi: 10.1109/ICDE.2016.7498427]
|
| [67] |
Wang N, Xiao XK, et al. PrivSuper: A superset-first approachto frequent itemset mining under differential privacy. In: Proc. of the IEEE 37rd Int'l Conf. on Data Engineering (ICDE). IEEE, 2017. 809-820.[doi: 10.1109/ICDE.2017.131]
|
| [68] |
Su D, Cao JN, Li NH, Bertino E, Lyu M, Jin HX. Differentially private K-means clustering and a hybrid approach to private optimization. ACM Trans. on Privacy and Security, 2017, 20(4): 16:1-16:33.
[doi:10.1145/3133201] |
| [69] |
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] |
| [70] |
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] |
| [71] |
Cao Y, Yoshikawa M. Differentially private real-time data release over infinite trajectory streams. In: Proc. of the 16th IEEE Int'l Conf. on Mobile Data Management (MDM). IEEE, 2015. 68-73.[doi: 10.1109/MDM.2015.15]
|
| [72] |
Ebadi H, Sands D, Schneider G. Differential privacy: Now it's getting personal. In: Proc. of the ACM-SIGACT Symp. on Principles of Programming Languages (POPL). ACM, 2015. 69-81.[doi: 10.1145/2775051.2677005]
|
| [73] |
Jorgensen Z, Yu T, Cormode G. Conservative or liberal? Personalized differentialprivacy. In: Proc. of the 2015 IEEE 35rd Int'l Conf. on Data Engineering (ICDE). IEEE, 2015. 1023-1034.[doi: 10.1109/ICDE.2015.7113353]
|
| [74] |
Alaggan M, Gambs S, Kermarrec A. Heterogeneous differential privacy. Journal of Privacy and Confidentiality, 2016, 7(2): 1-28.
[doi:10.1145/2806416.2806546] |
| [75] |
Chen R, Li H, Qin AK, Kasiviswanathan SP, Jin H. Private spatial data aggregationin the local setting. In: Proc. of the 2017 IEEE 36rd Int'l Conf. on Data Engineering (ICDE). IEEE, 2016. 289-300.[doi: 10.1109/ICDE.2016.7498248]
|
| [76] |
Erlingsson Ú, Pihur V, Korolova A. RAPPOR: Randomized aggregatable privacy-preserving ordinal response. In: Proc. of the ACM Conf. on Computer and Communications Security. ACM, 2014. 1054-1067.[doi: 10.1145/2660267.2660348]
|