差分隐私的查询一致性约束研究*

2020-03-04 08:15贾俊杰马慧芳牟玉祥

计算机工程与科学 2020年1期

贾俊杰，陈慧，马慧芳，牟玉祥

(西北师范大学计算机科学与工程学院,甘肃兰州 730070)

1 引言

随着互联网大数据时代的到来，网络上每时每刻都在产生大量的数据记录，如购物记录、Web点击流等事务信息。这些数据发布后由企业和机构所收集和共享，通过挖掘其中的知识，为用户提供更精准的服务。但是，数据发布在为企业决策和科学研究工作提供巨大便利的同时，也给数据个体带来隐私泄露的威胁。隐私保护的数据发布技术作为当前数据安全领域的研究热点，在为数据分析提供足够多信息的同时也保护数据个体的隐私安全。目前隐私保护技术主要分为2类[1]：第1类是基于分组的隐私保护模型，如k-匿名[2]、l-多样性[3]、t-相近[4]等，这类模型都需要特定的攻击假设和背景知识；第2类是Dwork[5]在2006年针对统计数据提出的差分隐私保护模型，该模型不存在任何攻击，通过向真实答案中添加噪声干扰以达到对数据个体的隐私保护。

统计数据的发布主要使用直方图形式，因直方图直观的数据分布形式，其结果可作为统计查询的直接依据[6]。生成直方图时，需根据不相交的查询区间将数据划分为不同的区间，再分别统计每个区间的计数值，为提供差分隐私的保护，最常用的方法是向每个区间分别添加独立的符合Laplace分布的噪声值。这些查询区间为不相交的子集，所以区间查询的敏感度为1，这样的差分隐私直方图发布保证了数据个体的隐私。但是，对于通用直方图(即查询区间子集相交的直方图)[7]，每个区间是不规则的且与其他区间有重叠部分，若向通用直方图的区间直接添加Laplace噪声，可能会出现范围查询的不一致性问题。例如，1组查询序列的结果为A={a1,a2,a3}，存在a1=a2+a3的约束关系，向A中添加Laplace噪声之后得到的结果：a′1≠a2+a3，违背了原始的约束关系。

因此，本文针对查询不一致的问题提出一致性调整算法，先将1组子集相交的区间查询映射到1棵满k-叉区间树上，其中同一层节点上的区间值不相交，再向树中每个节点添加符合Laplace分布的随机噪声，得到1棵差分隐私满k-叉区间树。将树进行一致性调整后生成满足一致性约束的满k-叉区间树，遍历后得到1组调整后的序列，实现差分隐私的一致性约束。实验结果表明，经过调整后的数据满足一致性约束且比直接添加噪声后的数据更接近真实值，实现了隐私保护目的，且时间运行效率优于LBLUE算法的。

2 相关工作介绍

Dwork[5]提出的差分隐私模型不存在任何的隐私攻击，且该模型具有强大的数学背景知识，致使差分隐私迅速成为了隐私保护研究领域的热点。直方图发布作为一种直观的数据分析方法，将利用差分隐私保护后的数据以直方图的形式发布，更利于数据研究者分析，因此目前已有大量的文献提出基于差分隐私保护的直方图发布算法。2006年，Dwork等人[8]最早提出基于差分隐私模型的直方图发布，通过向直方图中的每个区间直接添加噪声来达到隐私保护的目的。2011年，Xiao等人[9]提出通过小波变换技术实现差分隐私保护的直方图发布方法Privelet，利用小波变换将直方图数据转换为小波树，再向树中添加噪声实现差分隐私，逆转换小波树得到需发布的直方图数据。2012年，Acs等人[10]利用贪心策略将近邻的查询区间聚类成1个簇，再根据每个簇的大小不同添加噪声。在直方图中直接添加噪声后进行查询，会因区间值内噪声值叠加导致偏差过大的问题。2013年，Xu等人[11]提出StructureFirst算法，利用指数机制确定不同分组间的界限，再向不同组添加噪声。2016年，张啸剑等人[12]提出基于差分隐私的直方图发布方法DiffHR，利用Metropolis-Hastings技术与指数机制对直方图数据进行排序，排序后使用一种贪心聚类方法提高精确度。2019年，张宇轩等人[13]利用度排序的边移除方法给出了2种点差分隐私下图的度分布直方图发布机制，这2种发布机制在达到隐私保护的前提下，还提高了数据的可用性。

目前关于差分隐私直方图的发布主要针对精确度的问题做研究，针对不一致现象的研究较少，Hay等人[7]首次提出针对差分隐私直方图发布的不一致问题，使用约束推理的后处理方法，解决查询存在的不一致现象，结果证明经过处理后的答案接近真实值且满足一致性约束。Lee等人[14]为进一步提高一致性约束后直方图的精确度，将后处理步骤转换为约束极大似然估计问题，提出一种基于交替方向乘子法ADMM(Alternating Direction Method of Multipliers)的通用方法，该方法适用于各种应用。吴英杰等人[15]通过构造局部的区间树，实现局部最优线性无偏估计，使用迭代次数以达到全局最优线性无偏估计。因此，本文提出全局的一致性调整CA(Coherence Adjustment)算法，该算法既解决了不一致问题又保证了数据的精确度。

3 相关技术介绍

3.1 差分隐私

差分隐私模型使数据通过某种差分隐私随机算法K发布并面向用户提供查询接口。算法K不依赖于特定的数据表，利用随机噪声对输出数据进行扰乱，数据表中的每1条记录均得到了完全相同程度的保护，使得在统计意义上攻击者无论具有何种背景知识，都无法识别任意1条记录是否在原数据表中。

定义1(兄弟数据集) 2个数据集D和D′，有且仅有1条记录不同，记为|DΔD′|=1，则称D与D′为1对兄弟数据集。

定义2[5](ε-差分隐私) 对任意1对兄弟数据集D和D′，存在随机算法F(D)和F(D′)满足：

Pr(F(D)∈S)≤exp(ε)×Pr(F(D′)∈S)

(1)

则称算法F满足ε-差分隐私。其中S表示任意的输出集合，ε表示隐私预算，隐私预算越大，隐私保护程度越低，数据可用性越高，通常情况下，ε取[0,1]的实数。

定义3[5](全局敏感度) 有1对兄弟数据集D和D′，对于任意函数f(D)∈R，则其全局敏感度Δf表示为：

Δf=max‖f(D)-f(D′)‖p

(2)

其中，R为函数所映射的实数空间，‖f(D)-f(D′)‖p表示数据集D与D′之间的Lp距离。

差分隐私保护主要通过向真实数据添加噪声来实现，常见添加噪声的机制包括Laplace机制和指数机制，其中Laplace机制主要针对数值型数据，指数机制通常用于需要对输入数据进行复杂操作的算法，例如针对离散型数据的分类操作。本文采用Laplace机制分析计数查询的一致性约束问题。

定义4[5](Laplace机制) Laplace机制通过向查询请求结果f(D)中添加随机扰动噪声η，得到输出值f(D)+η实现ε-差分隐私保护，则Laplace分布的概率密度函数为：

(3)

由式(3)可得，Laplace噪声满足期望为0、方差为2λ2的Laplace(λ)分布。噪声尺度参数λ值越大，所添加的噪声幅度越高，隐私保护程度也越大。对于任意函数f(D)∈Rd，若算法F的输出结果满足：

(4)

则F满足ε-差分隐私保护。其中d为区间查询长度。由式(4)可得，添加的噪声尺度参数λ=Δf/ε，λ大小与全局敏感度Δf成正比，与隐私预算ε成反比。

性质1[5]设有算法F1,F2,…,Fn，隐私预算分别为ε1,ε2,…,εn，那么对于不相交的数据集D1,D2,…,Dn，由这些算法构成的组合算法F(F1(D1),F2(D2),…,Fn(Dn))满足(maxεi)-差分隐私保护，该性质称为“并行组合性”。

3.2 k-叉区间树

统计直方图的发布按数据表不同的属性进行划分，形成1个或多个属性不相交的集合，利用集合的计数值来直观地表示数据的分布信息。

定义5(计数查询) 设有n条记录的数据表T，其中包含属性x，用户通过查询Q访问数据表T，查询Q形如Select Count(*) fromTWherexina。若属性x为数值型数据，该查询统计属性x的取值频数，其中a为属性x的1个取值。若属性x为分类属性，该查询分别统计属性x的类别计数，此时a为属性x的1个类别。

例1统计某购物篮商品A,B,C,D的购买频数，每个商品的购买属性取值为0或1，0为没有购买，1为购买。表1为商品统计结果，表2为对表1的统计结果加噪后的结果。

Table 1 Commodity statistics results表1 商品统计结果

Table 2 Results after adding noise 表2 加噪后的结果

假设用户对原始表提出查询Select Count(*) fromTWhereGoodsin (‘A’,‘B’)，即查询商品A和B的计数和，故该查询可称为区间查询，可利用表1得此查询的精确结果为4。若利用表2来回答用户的查询，查询区间较大时，即Goods的查询类别较多时，噪声的累加使数据的精确度降低。

由敏感度定义可知，1对兄弟表统计差异值为1，此时统计直方图的敏感度Δf=1，若对原始数据每条记录都添加噪声，由于每个元素的Laplace噪声为方差2λ2，在最坏查询情况下，区间查询Q覆盖了所有的记录，将由类似表2的加噪查询结果中的n个元素方差相加而成，可得查询Q的噪声方差为O(nλ2)；当查询的区间较大时，将使添加噪声后的差分隐私统计直方图发布结果的方差增大，影响数据发布的有效性。据此，文献[15]提出将统计直方图转化为区间树，再对区间树进行差分隐私统计直方图发布，当进行查询时，每个父节点的值均为其k个子节点的值之和，其中k为区间树中每个父节点的子节点数，故查询Q的噪声为所覆盖节点的噪声总和，且在所添加噪声为同方差的条件下，查询Q的噪声方差为O(kλ2logn)。可见，利用区间树发布统计直方图可以大幅减少计数查询的误差。

定义6(满k-叉区间树) 将区间查询Q的值映射到1棵k-叉树(k≥2)的各个节点上，生成满k-叉区间树H，使得每个节点所对应的查询区间覆盖其k个孩子节点的查询区间，且每个节点的真实区间查询计数值为其孩子节点的真实计数值之和。其中同一层节点的查询区间不相交。

例2将表1中的区间查询构造成1棵满2-叉区间树H。假设查询的区间序列为T=([A],[B],[C],[D],[AB],[CD],[ABCD])，其中区间[AB]表示查询覆盖商品A和B的计数和，且每个区间查询彼此相互独立，区间数|T|=7，令k=2，则m=3。因区间[AB],[CD],[ABCD]的计数分别为4,24和28，根据映射关系可构造深度为3的满2-叉区间树H，如图1所示。

Figure 1 Full 2-ary range tree H图1 满2-叉区间树H

(5)

4 算法模型

为解决上述的不一致现象，文献[15]提出局部最优线性无偏估计，但只限定深度为2且有k个子节点的差分隐私区间树(本文中规定树的层数l从1开始计数，即定义1个节点所在的层数为叶节点到该节点路径上的节点数)。本文的目的是在深度大于2的满k-叉区间树中找到所有节点值的最优线性无偏估计。

根据文献[15]，假设任意1棵深度为2的区间树H，为H中每个节点值随机添加独立同方差的Laplace(Δf/ε)噪声，得到差分隐私区间树。根据高斯-马尔科夫定理，求最优线性无偏估计等价于求解1个满足限定条件的最小二乘解，令第i个子节点原始计数值为真实值Xi，则父节点t和子节点i=Son(t)={i1,i2,…,ik}添加噪声后的节点值分别为：

(6)

(7)

令z表示节点的无偏估计权值，即得到定理1。

定理1[15](局部最优线性无偏估计) 对于任意1棵深度m=2的差分隐私k-叉区间树，其节点的最优线性无偏估计为：

(8)

(9)

其中，

(10)

父节点的无偏估计值为父节点噪声值减去偏差值Δ，叶节点的估计值为叶节点噪声值加上偏差值Δ。

定理1并不适用深度大于2的差分隐私区间树，文献[15]提出迭代定理1得到局部最优线性无偏估计迭代算法LBLUE(Local Best Linear Unbiased Estimation)，但算法随着树的深度增加计算量增大，效率也随之降低。因此,本文提出差分隐私区间树的一致性查询算法，对区间树进行2次遍历，通过自顶向下的不一致估计调整，再进行自底向上的一致性无偏估计调整，最终得到满足一致性约束查询的差分隐私满k-叉区间树。

4.1 自顶向下的不一致估计

根据定理1，若要满足一致性约束查询，则父节点(根节点)的无偏估计值应等于子节点的无偏估计值之和，即：

(11)

对于任意子节点i(i∈Son(t))，有：

(12)

其中，j指父节点t除了i以外的子节点，此时节点i的无偏估计值为：

(13)

由式(9)可知：

(14)

综合式(10)、式(13)和式(14)，得到：

(15)

(16)

(17)

即

(18)

因此根据自顶向下策略，可得满k-叉区间树各节点不一致有偏估计值的递归关系为：

(19)

自顶向下的不一致估计TDICE(Top-Down Inconsistent Estimates)算法如算法1所示。

算法1TDICE

输出：Z(自顶向下的不一致估计的TDICE满k-叉区间树)。

4 返回Z

5 end

4.2 自底向上一致性估计

(20)

(21)

由式(21)可知：

(22)

则

(23)

将式(23)代入式(20)，可得：

(24)

(25)

自底向上一致性估计BUCE(Bottom-Up Consistent Estimates)算法如算法2所示。

算法2BUCE

输入：Z。

1 将Z自底向上一致性估计；

5 end

4.3 一致性调整

一致性调整算法CA描述如算法3所示。

算法3CA

输入：Q，隐私预算ε。

1 将Q映射到满k-叉区间树上，add 0*to空节点，得到H；

5 删除所有标记0*的节点；

4.4 一致性分析

在使用CA算法之前，已经对查询结果添加了符合Laplace分布的噪声，数据的隐私程度不需要再进行讨论，接下来分析CA算法的一致性。

(26)

根据式(21)和式(23)，可得：

(27)

则有

(28)

所以，经过调整后的满k-叉区间树对于任一父节点t满足一致性区间查询。得证。

□

4.5 算法分析

将区间查询的值映射到1棵满k-叉区间树上，设满k-叉区间树的节点总个数为n。算法1是将1棵添加噪声后的满k-叉区间树进行1次自顶向下的遍历，时间复杂度为O(n)；而算法2是将1棵自顶向下不一致估计后的满k-叉区间树进行1次自底向上的一致性估计，时间复杂度也为O(n)。因此，CA算法的总时间复杂度为O(n)。

5 实验评估

本节主要验证一致性调整后的直方图发布满足一致性且精确度高，以及算法的时间效率高于需迭代的LBLUE算法的。4.4节已证明一致性调整后的数据满足一致性约束查询，因此根据精确度和时间效率进行实验。实验对比分析对象为在满k-叉区间树上添加符合Laplace分布的噪声值实现差分隐私算法H～,对比算法为文献[7]Boost-2算法、文献[15]LBLUE算法和一致性调整算法CA。

实验采用的数据集为：Amazon[15]和Nettrace[7]。其中Amazon是为期1 894天的用户对亚马逊网站发起请求操作的时间数据集,Nettrace是1所大学65 535条内联网的IP地址轨迹数据。

实验环境为2.60 GHz Intel(R)Core(TM)i5-3230M CPU，4.00 GB内存，Windows 10专业版64位操作系统，数据分析软件为IBM SPSS Statistics 22，编程软件为Eclipse 4.3，绘制结果分析图软件为Matlab R2016a。

5.1 区间查询精确度对比

采用均方误差MSE[12]度量精确度。在区间查询精确度对比实验中，通过改变区间查询的大小，在每个区间内随机选取500个查询，得到这些区间查询的均方误差，然后求取均值来确定区间查询的精确度。隐私预算ε分别取值0.01和1.0进行实验，分析结果如图2和图3所示。

Figure 2 MSE changes of different range queries on Amazon dataset图2 Amazon数据集下不同的区间查询MSE变化

Figure 3 MSE changes of different range queries on Nettrace dataset图3 Nettrace数据集下不同的区间查询MSE变化

图2为使用Amazon数据集的分析结果，图3为使用Nettrace数据集的分析结果。可以明显看到，即使ε取值不同，相同区间查询，H～得到的结果误差最大。在图2a中ε=0.01时，区间查询的误差值约为103，在图2b中ε=1.0时，区间查询的误差值约为101，几乎接近于真实值。而在图3a中ε=0.01时，区间查询的误差值约为106，在图3b中ε=1.0时，区间查询的误差值约为102。这是因为Nettrace数据集相比Amazon数据集，单位长度区间个数更多，因此误差值数量级相差更大。

对比分析图2和图3可得，同一数据集下，ε取值越大，均方误差值越小，即数据的可用性越高。因为随着区间值增大，区间查询树的节点个数越多，需要添加噪声值的节点数越多，导致均方误差值越大。而H～为直接向满k-叉区间树中添加噪声得到的结果，与其他3种经过调整后的算法对比，均方误差值明显更大。Boost-2算法的均方误差值比LBLUE算法的误差值小，这与文献[15]得出的分析结果相同。因CA算法不需要迭代，只需要对区间树进行2次遍历，所以噪声值的叠加也会减小，相比Boost-2算法和LBLUE算法均方误差值有所减少。

5.2 算法时间效率对比

通过使用Amazon数据集和Nettrace数据集对比Boost-2算法、LBLUE算法、CA算法的运行时间，分别取ε=0.01，0.1，1.0进行实验。从图4中可以明显看到，不论ε取何值，同一数据集下相同算法的运行时间相同，因此得出结论：算法运行时间与ε取值的大小无关。还可以看出，在2个数据集对比图中，Boost-2算法和CA算法的运行时间基本相同，而LBLUE算法的运行时间明显较长，这是因为LBLUE算法需要迭代运行，而其他2种算法不需要迭代运行，因此运行时间比LBLUE算法的短。而数据集的大小不同，运行时间也不同，即数据集记录条数越多，算法的运行时间越大。总体而言，在同一数据集下，本文算法的运行效率高于LBLUE算法的运行效率。

Figure 4 Comparison of the average running time of three algorithms with different ε图4 3种算法在ε不同时平均运行时间的比较

6 结束语

本文针对直方图发布区间查询的不一致问题，提出一致性调整算法CA。先将满k-叉区间树进行自顶向下的不一致估计TDICE，然后对不一致估计后的结果进行自底向上一致性估计BUCE，得到一致性调整(CA)后的结果。经证明，通过一致性调整后的满k-叉区间树满足一致性约束查询。使用真实数据集进行实验对比，得出一致性调整(CA)后的区间查询精确度较高且时间效率高于LBLUE算法的。此外，当数据集较大时，如何降低区间查询误差值是下一步需要进行的工作。