基于敏感度判定的位置隐私保护方法

刘 琨,王希孔,王 辉,周 超,刘沛骞

(河南理工大学 计算机科学与技术学院,河南 焦作 454002)

1 引 言

随着移动通信网络技术的不断发展,它在改变人们生活方式的同时,也给用户提供了丰富的信息服务和信息资源.用户在社交网络平台、移动定位终端、LBS(Location Based Services)服务[1]以及其他移动信息通信网络服务中产生的各项信息也日益增加.用户在享受网络信息服务的同时,也面临隐私泄露的安全问题.例如,2019年Greenbone Networks分析了全球约2300个在线PACC服务系统,其中包含52个国家中2400多万份患者数据记录,数据中所包含的用户身份信息、出生日期、放射图像、主治医生等信息都可以在网页轻松下载;迪拜打车巨头Careem Networks在2018年遭受网络攻击,导致1400万用户位置数据、姓名、手机号等都遭到泄露.K-匿名[2]是在位置隐私保护中常用的方法之一.K-匿名分为集中式和分布式,集中式是在用户和LBS服务商中间添加可信第三方,该可信第三方来完成匿名处理和查询.差分隐私在位置隐私保护中运用也十分广泛.2006年Dwork[3]等人提出差分隐私模型,差分隐私运用数学模型,结合Laplace机制以及指数机制、高斯机制等可以对原始数据进行加噪处理,从而达到隐私保护目的.陈[4]等利用k-means聚类算法进行数据抽样,借助差分隐私对轨迹数据进行干扰,在不同位置对隐私预算进行平均分配,缺乏对不同敏感位置的区分保护.Yin[5]等人根据位置点访问频率来判断敏感度,该方法由于缺少对用户偏好的分类判断,难以满足用户个性化的位置隐私保护需求.为了有效解决上述轨迹隐私保护中存在的问题,本文提出了一种基于OTM概率相似性度量的差分隐私算法(Differential privacy algorithm based on the OTM probabilistic similarity measure,DPBO).简单来说,根据每个真实位置点的敏感度,来分配隐私预算,并加入相应的噪声.通过在真实数据集上的实验结果,证明了该方案使隐私保护强度增强,且时间开销更低.

本文各章节安排如下:第2节主介绍国内外位置隐私保护研究现状;第3节列出本文中所需的问题定义.第4节描述了本文提出的基于OTM概率相似性度量的隐私预算分配方法以及基于该方法的位置隐私保护方法.第5节对实验结果进行了分析.第6节总结了全文.

2 相关工作

3 问题定义

3.1 差分隐私相关定义

定义1.差分隐私

有两个数据集X和X′,当X和X′结构相同,有且只有一条数据不相同时,则称X和X′为相邻数据集.F是相邻数据集上的随机查询算法,M是算法F在相邻数据集X和X′上任意的输出结果,若F满足公式(1),则称F满足ε-差分隐私.

(1)

其中ε表示隐私预算,在一般差分隐私中,ε往往取一个很小的值,例如0.01、0.1、ln2等,ε值越小,隐私保护程度就越高.

定义2.全局敏感度

假设任意函数F,数据集X和X′分别为两个输入数据集,输出为d维实向量,满足公式(2):

G=maxx,x′‖f(x)-f(x′)‖i,i=1

(2)

其中‖f(x)-f(x′)‖i,i=1表示f(x)和f(x′)的一阶范数距离.不同的查询函数具有不同的全局敏感度,全局敏感度和数据集无关.

定义3.Laplace机制

Laplace分布[13]是统计学中的一种连续的概率分布.而在位置隐私领域,Laplace机制可以通过在位置查询结果f(x)中添加噪声来满足ε-差分隐私,从而保护位置隐私.

给出数据集X,且假设存在一个灵敏度为ΔG的函数,使得在输入数据集为X的情况下,输出结果为d维实向量Rd,随机算法M(X)=f(X)+Y提供ε-差分隐私保护,其中Y～Lap(ΔG/ε)为随机噪声,服从参数为ΔG/ε的Laplace分布.

(3)

公式(3)是拉普拉斯概率密度函数,其中当u=0时,尺度参数越大,概率分布越均匀,尺度参数越小,概率分布越集中.噪声添加量和ΔG的大小成正相关,噪声添加量和ε呈负相关.ΔG越小,加入噪声的量越少,算法效果更好.

3.2 基于概率模型的相关定义

定义4.TR概率特征

对于有i个位置的轨迹TR,设轨迹TR={tr1,tr2,tr3,…,tri},其中tr1,tr2,tr3,…,tri代表轨迹TR中的位置点.用户User访问tri的概率为Pv(访问概率),User从tri-1到tri的概率为Ps(转移概率),则PA(tri)=(V,S)为tri的概率特征,其中V=Pv(tri),S=Ps(tri).

定义5.PPTLT范围度量

PPTLT范围度量指的是对两个不同的位置点从转移概率Ps、访问概率Pv、时间T、地理位置LT4个方面进行评判,若相似度在设定阈值之间,则代表两个位置点相似.设地理坐标为LT(Lo,La),其中其中Lo为经度,La为纬度设历史轨迹H={h1,h2,h3,…,hi},其中h1,h2,h3,…,hi为历史轨迹中的位置点,若hi和tri满足以下关系,则他们具有位置点相似性:

|Pv(hi)-Pv(tri)|≤ΔPv

(4)

|Ps(hi)-Ps(tri)|≤ΔPs

(5)

|T(hi)-T(tri)|≤ΔT

(6)

|La(hi)-La(tri)|≤ΔLa&&|Lo(hi)-Lo(tri)|≤ΔLo

(7)

其中ΔPv为访问概率之差的阈值,ΔPs为转移概率之差的阈值,ΔT为时间差的阈值,ΔLa和ΔLo分别是纬度和经度的差的阈值.

定义6.位置点库LPLh

设存储位置点的数据库为LPLh,(ID,PA,LT(Lo,La),T)为位置点库中的一条数据,ID为位置点存储入库时的id,每条数据都有唯一id,PA为位置点概率特征,LT(Lo,La)为位置点的经纬度信息,T为数据申请时的时间.

定义7.OTM概率相似性度量

本文中概率相似性度量针对一个位置点集合与单个位置进行概率比对,即一对多(One To Many,OTM)概率相似性度量.设单个位置点为r0,设位置点集合为X={x1,x2,x3,…,xi},i=n,下列式子表示该位置点集合与单个位置点r0的概率相似度指数:

(8)

SML(r0,X)代表r0与X的相似度指数,λ是一个可变常数,用于规范化相似度指数,把相似度指数控制在[0,1]范围之内.

3.3 加权有向图结构

在位置隐私保护中,位置点信息的存储整合是至关重要.本文使用加权有向图[14]来整合存储位置点信息.设有向图为Gr,Gr=(N(R,SET),E,Ve,Vn),N代表Gr中所有节点集合,即N={n1,n2,n3,…,ni},ni表示Gr中的i个节点,N中的R代表真实位置点,即R={r1,r2,r3,…,ri},SET代表与R点相似的位置点集合,即SET={set1,set2,set3,…,seti},如图1所示.

图1 图节点结构Fig.1 Figure node structure

其中r包含:

(ID,PA,LT(Lo,La),T)即r(ID,PA,LT(Lo,La),T),其中:

set={q1(ID,PA,LT(Lo,La),T),

q2(ID,PA,LT(Lo,La),T),

q3(ID,PA,LT(Lo,La),T),…,

qi(ID,PA,LT(Lo,La),T)}

代表set中有i个点,每个点都是位置点数据库中的记录.E为Gr中所有边S的集合,即E={e1,e2,e3,…,ei},图中一共有i条边.Ve和Vn分别为边与节点的权值的集合,即

Ve={ve1,ve2,ve3,…,ve4},Vn={vn1,vn2,vn3,…,vni}.加权有向图结构如图2所示.

图2 加权有向图Fig.2 Weighted directed graph

4 DPBO算法分析

基于差分隐私的位置保护,需要根据不同位置的敏感程度需求来分配隐私预算,这个位置敏感度判断方法需要位置信息、查询申请时间、概率特征等信息的支持.本文使用有向图来直观地反应用户的位置信息以及敏感度信息,本算法的整体流程如图3所示.

图3 DPBO算法流程图Fig.3 Flow chart of DPBO algorithm

4.1 基于PPTLT范围度量构建位置集合

为了对真实轨迹LTr进行位置点敏感度评判,本文采取从历史轨迹中选取位置信息,对历史位置点信息库进行遍历,利用PPTLT范围度量选取出与LTr中各位置点相似的位置点集,从而为下面计算LTr位置点敏感度做铺垫.下面是具体流程:

1)真实轨迹LTr采样.对LTr进行位置点分割,把轨迹向量LTr={r1,r2,r3,…,ri}中位置点ri以位置点库LPLh格式存放,即ri(ID,PA,LT(Lo,La),T),设链表Listr,对LTr取模,即|LTr|=M0,为Listr分配M0空间长度,位置向量ri中ID按轨迹中起始点到终点的顺序依次升序排列,把Listr先存入缓冲区buf,buf中计数参数a=1,起始a=0,根据LTr位置逻辑,构建图Gr=(N(r,set),ED,Ve,VN),遍历缓冲区,若a>0,则选择Listr数据,为其分配M0个节点,有向边的指向为轨迹中位置点逻辑方向,将Listr数据存放在N节点的r区域中,LTr采样完成.

3)检索图节点,保证LTr中ri与HTset中的seti对应关系正确.根据轨迹LTr的逻辑,对应图中进行深度优先搜索,每个搜索节点,都进行公式(4)～公式(7)的再次判断,进行LTr与HTset的对应验证.

4.2 R点敏感度评判

本文使用差分隐私进行位置隐私保护,在对隐私预算ε分配时,需要根据位置点敏感度进行按需分配,所以本节对轨迹LTr中位置点ri进行敏感度评判,为后文分配ε做准备,敏感度评判方法如下:

将HTset={set1,set2,set3,…,seti}先依次存入链表List′中,建立一个二维数组a[x][y],x代表行,y代表列,一行存储一个seti,seti中每一个位置点数据在一个列中,例如a[0][3]代表set1中第4个位置点数据,a[4][2]代表set5中第3个位置点数据.将LTr={r1,r2,r3,…,ri}中每个ri与对应的seti进行OTM概率相似度评判,将a[x][y]带入公式(8),即:

经过双层循环,得出每个ri与之对应的seti的相似度指数SML.计算LTr中位置点ri与seti的概率相似度的算法如下:

输入:真实轨迹点集合LTr={r1,r2,r3,…,ri},轨迹点个数n,缓存链表List′,存储HTset={set1,set2,set3,…,seti}的二维数组a[x][y],规范化系数λ.

1.List′=Initialize();//初始化

2.inti,j;

3.i=x,j=y;

4.List′=LTr={r1,r2,r3,…,ri};

5.//轨迹存入缓存链表

6.for(i=0,j=0;i

7.for(i=1;i<=x;i++)

8. //双重循环计算ri与seti相似度指数

10.SML0[i]=sum;

11.for(i=0;i

13.//使每个位置点相似度指数存入数组

14.returnSML[i];

SML[i]即是LTr={r1,r2,r3,…,ri}中每个ri与对应的seti的概率相度性指数的集合,设为SMLI={sml1,sml2,sml3,…,smli}.smli越大说明真实位置点与对应的seti越相似,表示该真实位置点在历史位置中越具有普遍性,例如,某学生12:00时,位置在餐厅周边,在历史位置集中,12:00该学生很大概率都在餐厅或餐厅周边,所以12:00的餐厅对于该学生是极其敏感的位置点.所以真实位置点smli越大即越敏感,则ΔG设定值就越高.ΔG分配策略如下:根据smli在所有SML中的百分比,按正比设定ΔG,例如,若甲位置smli占SML的25%,则该位置为1/4ΔG.假设SML为0.8,分配示意表如表1所示.

表1 OTM概率相似度与ΔG关系表Table 1 Relationship between OTM probability similarity and ΔG

4.3 分配隐私预算ε并加噪

本文通过4.2节来得到每个被保护位置点的敏感度,该部分根据敏感度的不同,分配不同的隐私预算,然后根据隐私预算,进行加噪,使攻击者很难对位置信息进行攻击.

设每个位置节点的敏感度为ΔGi,为了按需分配隐私预算,需要对ΔGi进行权重计算,权重计算公式为:

(9)

表2 节点敏感度和分配隐私预算的关系表Table 2 Relationship between node sensitivity and allocated privacy budget

分配ε与加噪流程为:

步骤1.获取图节点中的位置点信息,采用深度优先遍历,根据轨迹逻辑,取出轨迹位置点存入链表List″={r1,r2,r3,…,ri,}.

步骤2.遍历链表List″,获取节点ΔGi,根据不同节点ΔGi的值,动态分配ε.

步骤3.成功分配ε的List″按序存入图Gr中,每个节点的ε,存入节点权值Vn.

步骤4.深度优先遍历图Gr,根据不同ε,加入相应大小的Laplace噪声.

步骤5.输出加噪后的图Gr.

输出Gr的即为经DPBO算法位置隐私保护处理后的格式化位置信息.

5 实验与分析

将本文基于位置相似性分析的差分隐私算法DPBO、根据签到频率分配隐私预算的算法Yin[5](由于文献中没有对该算法命名,则本文用作者名字命名),基于概率模型的K-匿名保护方法LRM[15],基于多匿名器的轨迹保护方法TPMA[8],进行对比试验.在相同实验环境下,对算法进行数据可用性分析、隐私保护强度分析、时间开销分析、参数对算法的性能影响分析.

5.1 实验设置

DPBO算法均采用Python实现,实验环境是8.00GBRAM的Windows10操作系统和2.40GHzCPU.本文采用的实验数据是Checkin数据集和Geolife[16]数据集.Checkin数据集从基于LBS的社交网站Gowalla获取,数据集包含由美国纽约超过49000名和洛杉矶31000名社交用户的位置签到信息.Geolife是由微软亚洲研究所提供的数据集,其中包含182个志愿者提供的17621条轨迹数据.

5.2 数据可用性分析

在本节中,为了评估DPBO机制的数据可用性,通过比较真实数据和发布数据的模糊查询结果的误差来定义.假设时间戳T发布数据的模糊查询结果为uT,时间戳T的真实数据为kT,uT与kT之间的误差定义为δ,该机制的总误差定义为L.

(10)

(11)

选择Geolife数据集,通过在相同地图精度下,改变覆盖范围来比较DPBO算法与Yin算法、LRM算法、TPMA算法的L,从而衡量各算法的数据可用性,即相同条件下L越小,数据可用性越强.数据结果图如图4所示.

图4 各算法L随覆盖范围变化关系Fig.4 Variation of L with coverage for each algorithm

随着覆盖范围的扩大,4种算法的L均呈上升趋势.在相同覆盖范围内,由于Yin算法采取按签到频率分配ε,没有对位置点进行敏感度评判,所以L略大于DPBO算法;LRM算法对数据概率相似性以及地理相似性进行判断,所以LRM的L略大于Yin算法,小于TPMA算法;TPMA算法未考虑概率相似性以及地理相似性,在相同条件下L最大.综上对比实验,相同条件下,DPBO算法L最小,数据可用性最强.

5.3 隐私保护强度分析

图5中表明了在相同攻击[17]算法下,隐私保护强度SOPP随着不同保护强度等级R的变化而变化的关系.实验表明:随着R的增大,所有算法的SOPP都呈下降趋势.由于Yin算法按照签到频率来分配隐私预算,没有对位置敏感度检验,所以SOPP值在4个算法中是最高的,隐私保护强度最低.LRM和TPMA算法均是对位置轨迹进行K-匿名,但是LRM算法考虑位置信息的概率相似性以及地理相似性,所以LRM算法隐私保护强度SOPP优于TPMA.DPBO算法根据概率特征,得出位置敏感度差异,进行隐私预算分配,所以DPBO算法SOPP值明显低于其他算法.

图5 各算法SOPP值随保护等级变化的规律Fig.5 Law of SOPP value of each algorithm with protection level

5.4 时间开销分析

由于隐私保护算法都需要一定的时间进行计算.所以假位置生成所需时间则是判断算法性能的一个重要标准.本实验通过对在不同隐私保护度R下,本算法与Yin算法、LRM算法、TPMA算法进行对比实验,对各算法的时间开销进行分析.图6中表明,随着隐私保护等级R增大,4个算法的运行时间都增加.由于DPBO算法采用概率相似性选择敏感位置,而Yin采用签到频率来判断敏感位置,所以在相同条件下Yin的运行时间略低于DPBO算法.由于TPMA与LRM均采用匿名来制造假位置,所以相同条件下运行时间大于运用差分隐私的Yin和DPBO算法,并且TPMA算法采用多匿名器方式,使得运行时间在相同条件下4个算法中最大.

图6 运行时间与保护等级的变化规律Fig.6 Variation law of operation time and protection level

5.5 阈值对SOPP的影响

在本研究中,SOPP值越大,被识别位置点占总位置点的比重就越大,隐私保护程度就越低,SOPP值越小,被识别位置点占总位置点的比重就越小,隐私保护程度就越高.本研究中阈值是影响SOPP大小的重要因素,其中ΔPv、ΔPs、ΔLa和ΔLo均是本文中重要的阈值.本部分通过对阈值参数进行控制变量实验,分析改变不同阈值对SOPP值影响.

由图7(a)和图7(b)可知,SOPP根据ΔPv值的增加而逐步平稳下降,并且下降斜率大致呈增加趋势;随着ΔPs值的增加,SOPP呈现下降趋势,但是下降速率在逐步降低.根据图7(c)所知,SOPP随着ΔLa和ΔLo的增加而降低.本模块中,SOPP都随着ΔPv、ΔPs、ΔLa和ΔLo的增大而减少,是因为ΔPv、ΔPs、ΔLa和ΔLo的增大意味着相似范围的扩大,范围的扩大导致经度下降,从而导致SOPP减小.

图7 SOPP根据阈值参数的变化关系Fig.7 Relationship between SOPP and threshold parameters

6 总 结

本文利用加权有向图收集表示历史位置信息,通过位置点相似度找出历史位置点与真实位置点的相似位置点集,提出DPBO算法来区分敏感度等级,通过整合加权有向图,根据不同敏感度分配相应隐私预算,最后运用Laplace机制进行加噪,从而实现位置隐私保护.本算法在未来位置隐私保护研究中,可以解决移动群智感知[18]中数据感知阶段的位置数据保护问题,通过对感知用户的历史轨迹归类,进行对真实数据的动态加噪,从而对感知用户的位置数据进行隐私保护.从细节角度来看,如何更加智能化[19]、动态化[20]、合理化为敏感位置分配隐私预算,是未来研究需要关注的重点.