文摘
基于位置的服务(磅)应用为人们的生活和工作提供便利,但收集位置信息可能暴露用户的隐私。因为这些收集的数据包含关于用户私人信息,位置信息的隐私保护方案是迫在眉睫的需要。在这篇文章中,一个保护方案DPL-Hc提出了。首先,用户的位置在地图上是映射到一维空间利用希尔伯特曲线映射技术。然后,拉普拉斯噪声添加到一维空间扰动的位置信息,认为70%以上的nonlocation信息的用户;与此同时,干扰效应是通过添加噪声。最后,干扰位置提交到服务提供者的用户的实际位置,以保护用户的位置隐私。理论分析和仿真结果表明,该方案可以保护用户的位置隐私不受信任的第三方有效。它有优势在数据可用性、隐私保护的程度,和匿名数据集的生成时间,基本上实现隐私保护和服务质量之间的平衡。
1。介绍
随着智能移动设备和无线通信技术的快速发展,基于位置的服务(磅)应用程序不仅为用户带来方便,也给用户造成严重的隐私和安全风险。在磅用户提供位置信息,位置服务提供商而获取位置服务,这可能会导致用户的敏感信息的泄漏1,2];例如,用户的兴趣点的访问频率可以分析用户的偏好和经济地位。与此同时,如果攻击者将用户的位置信息和nonlocation信息,将暴露更多的用户的个人信息(3]。的持续改进人们的隐私保护意识,保护用户的位置信息成为一个迫切需要解决的问题。
目前,主要包括位置隐私保护方法k匿名技术和(α,k)匿名技术。k匿名技术(4- - - - - -6)使用受信任的第三方(TTP)服务器扩展用户的实际位置变成一个看不见的地理位置,包括其他领域k - 1用户,不可信太阳能发电无法区分用户的实际位置和其他的地理位置k - 1用户然后发送位置信息的混淆太阳能发电(位置服务提供者)TTP。k匿名隐私保护提供了基础技术研究。然而,k匿名技术不限制用户的数据集和敏感属性是容易链接攻击。要解决这些问题,作者(7,8]提出(α,k)匿名技术的基础上k匿名技术。(α,k)匿名技术预设阈值α,所以敏感属性值在每一个等价类的比例不会超过这个阈值,模糊之间的链接关系敏感属性和quasi-identifiers和增强用户的匿名效果数据集。(α,k)匿名技术可以提高用户的位置隐私保护匿名化的数据集TTP。TTP掌握了所有知识的用户的磅查询和很容易遭受一个单点故障。如果攻击者捕获TTP,那么用户的位置隐私泄露。为了保护用户的位置隐私不依赖第三方,微分隐私技术(9- - - - - -11提出了]。在[2,12),微分隐私和匿名集k位置是用来计算干扰的位置,可以抵抗敌人的攻击提供有用的背景资料。在[13),一个 - - - - - -位置设置提出了基于微分隐私保护用户的实际位置在每个时间点在时间相关。但是它的缺点是,它忽略了攻击模式与nonlocation数据相结合的位置数据。如果攻击者把用户的位置信息在不同的时间和一些nonlocation信息,用户的私人信息将严重暴露。
剩下的纸是组织如下:第二部分描述了一些相关的定义位置隐私。在第三部分中,架构和威胁模型磅系统进行了详细分析,然后微分隐私位置保护机制的具体实现算法基于希尔伯特曲线(DPL-Hc介绍了)。在第四部分,DPL-Hc方案评估,包括隐私分析、安全分析和算法复杂性分析。第五部分从可用性验证算法的有效性发表的数据集,数据集的隐私保护程度,匿名数据集的生成效率。第六部分总结了DPL-Hc计划,加强隐私保护和隐私保护之间的平衡程度,有效地解决了系统中存在的服务质量。第七部分是本文中所使用的引用。
2。相关定义
定义1(希尔伯特曲线)。希尔伯特曲线作为空间的映射年代讨论一维空间R,表示 。如果点 ,然后 ;也就是说,H (p)是H的价值点p。对点集 , 。编码规则的一阶、二阶和三阶希尔伯特曲线所示,分别在图1。
定义2(位置微分隐私)。两个数据集D和最多相差一个位置记录,也就是说, ,给定一个微分隐私保护算法一个,范围(一个)的范围是一个。算法一个提供了 - - - - - -微分隐私,是隐私的预算,它代表了隐私保护的程度。如果任意位置 通过算法一个从任意轨迹数据集D沙子满足如下不等式,那么算法一个满足 - - - - - -微分隐私。 概率公关(.)表示用户的位置隐私被暴露的风险,它是随机控制的算法一个;参数是隐私的预算。从上面的公式可以看出,较小的参数,类似的返回的查询结果的概率分布的微分隐私算法作用于一对相邻轨迹数据集,越困难的攻击者区分这两相邻轨迹数据集。在极端情况下,当 ,隐私保护是最高的学位。相反,参数的值就越高 ,隐私保护程度越低。
定义3(全局灵敏度)。对于任何函数 ,的全球灵敏度函数f是 在哪里代表函数的一阶范数距离输出值的相邻数据集D和 ,和敏感是指函数的最大输出值的变化引起的添加或删除任何记录查询的数据集。全球灵敏度函数是由函数本身的性质决定的,是独立的数据集。
定义4(拉普拉斯机制)。给定一个函数f被定义为,拉普拉斯机制 在哪里是一个随机变量的拉普拉斯分布呢 。拉普拉斯分布的位置参数是0,尺度参数 ,和它的概率密度函数 添加噪声正比于全局灵敏度和隐私预算成反比 。拉普拉斯机制仅限于函数的返回值是真实的,和指数噪声机制提出了非数值的查询功能。
定义5(指数机制)。给定一个效用函数 ,r是一个实体对象输出域范围内可用的函数。如果输出的功能u满足方程(5),那么 - - - - - -微分隐私是满意。 在哪里是全球敏感性的效用函数,指数回报机制实体对象的概率成正比吗 。
3所示。微分隐私保护机制基于希尔伯特曲线位置
3.1。系统架构和威胁模型分析
本文中使用的系统架构图所示2。系统架构主要由四个部分组成:定位系统、移动终端、通信网络磅服务器。移动用户拥有移动定位设备(智能手机和车载移动终端)获得个人通过互联网或准确的地理位置信息全球定位系统(GPS)和其他定位技术,然后将查询请求发送到磅服务器通过Wi- - - - - -Fi和其他通信网络。后磅服务器接收来自用户的查询请求,它将服务信息发送到用户的移动终端作为响应来完成请求服务和响应服务的一个连贯的过程。
通过移动终端用户发出查询请求,和磅可能会暴露隐私泄漏的威胁的过程中响应请求。系统中几种类型的攻击者在图所示3。攻击者包括不可信太阳能发电本身,在系统内部攻击和外部攻击者。一般来说,太阳能发电诚实但好奇,可为用户提供查询服务诚实根据协议。然而,为了提高自己的商业利益,服务提供者收集用户位置信息通过观察接收到的干扰的位置。此外,可能还有攻击者在组织内提供服务,发送用户的干扰位置其他外部组织为了他们自己的利益;外部攻击者可以通过窃听用户的个人或组织数据或攻击服务器访问服务器。
当用户发出查询请求时,微分扰动机制上实现用户的移动。拉普拉斯噪声添加到用户的地理位置,提供扰动的位置太阳能发电。当太阳能发电响应用户的查询,并将查询结果返回给用户,它不能推断出用户的真实地理位置加上一些背景信息,这在很大程度上保护用户的位置隐私。
3.2。实现机制和算法
在这篇文章中,兴趣点被定义为真正的感兴趣点的地理空间。每个兴趣点l可以近似表示为l(x,y,z),(x,y)是兴趣点的位置坐标l和z代表的语义位置的兴趣点l。用户的隐私保护是实现上下文感知。的DPL-Hc计划获得上下文(比如相同的密度)通过用户的兴趣点的分布。最优数据聚类和距离保持特性的希尔伯特曲线在二维空间两个相邻点更容易在一维空间相邻;也就是说,所有的兴趣点在一维空间齐次上下文。当用户请求磅二维空间查询服务,用户的兴趣点是第一个映射到一维空间;然后添加到拉普拉斯噪声 位置包含用户的实际位置;干扰的位置位置点集是几乎相同的,攻击者无法区分用户的实际位置。如图4,三阶希尔伯特曲线编码规则是采用本文和圆圈点 图的投影后的兴趣点。数量在每一个原子单位代表了希尔伯特的价值原子单元。
在本文中,我们首先使用四叉树索引结构索引的用户的位置和分区域包含所有用户的位置为一个四叉树,并获得四叉树索引QT与位置设置l。位置数据处理。根据希尔伯特曲线技术上面所提到的,用户的二维地理位置映射到一维空间,保留位置元素的语义信息来获取相应的完整的树的数据结构,提高了搜索的效率目标点在未来。后的四叉树希尔伯特曲线映射显示在图5。
地理区域的网格划分是一个有效的方法来描述兴趣点的位置。如图4,DPL-Hc方案从该区域包含用户的位置和地理空间分为4网格一次,然后迭代获得网格(h是部门的高度),直到某一粒度是满足。它分为一些原子区域不能被分割,和原子的大小是由用户的位置C该地区可以容纳。在图4包含用户的位置,面积分为88网格,每个兴趣点独特的属于一个网格。在本文中,我们设置 。的DPL-Hc计划使用四叉树结构来生成用户的位置指数,见算法1。为方便描述,该算法所涉及的符号定义如表所示1。
|
该算法将地理区域划分为四个部分根据一组感兴趣的点P和四叉树的层数和索引 用户的位置。如果划分的数量层创建了四个新子节点的节点层,如步骤1 - 6所示,如果它创建了四个新子节点为其他节点分割层,如步骤10所示,然后,属于每个兴趣点 ,如果存储在该地区的利益点我th四叉树节点的子节点 ,这些兴趣点是搬到各自的子节点,如步骤11 - 13所示。最后,确认节点的点p属于,然后递归地调用插入p为节点D16日和17日,见步骤。上面的语句(1)执行循环直到所有兴趣点插入节点D,最后的四叉树QT与位置设置输出。
的DPL-Hc计划遍历和搜索树形成位置处理后,得到的位置数据l和nonlocation数据B每个标记点,应用微分隐私技术分别添加噪声位置数据和超过70%的nonlocation数据。
的DPL-Hc计划需要将用户的位置信息,有超过70%的nonlocation信息来保护用户的隐私信息。感兴趣点的坐标分别添加噪声提供了隐私保护程度高于单独添加噪声点。正式让 表示k兴趣点, 是用户的真正的兴趣点, 是被利益点。对于任意两个兴趣点和 ,生成的概率摄动的兴趣点 应该满足以下方程:
超过70%的nonlocation信息,考虑到隐私的预算 ,噪声添加到nonlocation遍历收集的信息来满足微分隐私的要求。的属性设置 nonlocation数据D,它被标记为连续值属性 ,及其noncontinuous-valued属性标记为 。不同的机制的噪音被添加到nonlocation不同属性的信息。拉普拉斯噪声添加到连续的价值被打扰,和指数噪声添加到不连续的值被打扰。指数机制输出离散值的概率成正比 。在DPL-Hc计划,所示的匿名数据处理过程的算法2。
|
||||||||||||||||||||||||||||||||||||||
算法的输入参数是用户的位置数据集l考虑到隐私,预算 ,用户的nonlocation数据集Dnonlocation数据属性设置B、连续属性的数据集 ,离散属性的数据集 ,与树高h。处理对象的位置数据集l和nonlocation数据集D。该算法首先在步骤2中隐私预算分配;位置数据和nonlocation数据进行分类。对于任何一个元素数据集的位置l、拉普拉斯噪声添加到其横坐标和纵坐标,分别为微分扰动在步骤3 - 5;接下来,nonlocation根据属性数据集划分在步骤8。如果nonlocation数据属于连续值属性,拉普拉斯微分扰动噪声添加的步骤9和10;如果nonlocation数据属于discrete-valued属性,添加噪声指数差扰动的步骤11和12。执行上面的语句(3 - 12)循环直到所有位置数据进行匿名处理,超过70%的nonlocation数据。最后,匿名数据集 16步中输出。
4所示。算法的理论分析
4.1。隐私分析
在本文中,用户的位置点是由特定的横坐标和纵坐标表示。考虑到用户的位置点集 ,其中一个是用户的实际位置 ,拉普拉斯噪声添加到用户的位置点打扰用户的实际位置,和 扰动后的兴趣点。对于任意两个兴趣点 和 在k兴趣点,根据拉普拉斯机制,有
让b是 生产和 生产 ,在哪里是最大的 和是最低的 。因此,摄动的兴趣点 可以获得。
兴趣点 , , ,我们可以从三角不等式得到以下结果:
重新排列公式(8),两边同时除以并提高他们与基地幂指数 ;然后两边同时乘以 得到
为坐标和 ,方程(10)可以表示为
通过设置指数方程的边界(11)和(12),我们可以得到 也就是说,
从上面可以看出,匿名数据处理算法DPL-Hc方案满足 - - - - - -微分隐私。
4.2。安全分析
在位置隐私保护方法提供了在这篇文章中,用户提交的查询服务磅服务器为了查询兴趣点离当前位置;例如,查询用户的位置最近的电影院。在理想的情况下,由于干扰,攻击者不能识别任何干扰之间的连接位置和用户的实际位置。然而,当攻击者知道密度的兴趣点在地图上,用户的近似位置知识,和噪声分布,攻击者可以根据这些信息推断出用户的真实位置。在匿名的过程中,拉普拉斯分布机制与尺度参数 用于计算的概率相同的扰动位置吗从位置点集 这是局限于一个小的常数因子 。考虑到微扰点 ,无论利益点是用来实现扰动,的概率兴趣点产生扰动是相同的(在常数因子的范围 ),和攻击者不能使用上述信息来提高猜测用户的实际位置的概率。因此,DPL-Hc方案可以有效地保护用户的位置隐私。
4.3。算法复杂性分析
首先,本文中的匿名数据处理算法使用一个贪婪的方法递归四叉树从上到下,和时间复杂度 。然后算法分类数据信息中包含的每个节点,并添加噪声的时间复杂度位置数据集 。nonlocation数据连续属性的数据集,添加拉普拉斯噪音的时间复杂度 ;nonlocation数据和离散属性的数据集,添加噪声指数的时间复杂度 。
5。实验结果和分析
5.1。实验装置
为了研究本文提出的算法的可行性,采用的系统硬件配置是一个英特尔(右)核心(TM)我7兼容个人电脑主要频率为3.4GHz4GB的内存,以及超过200 GB的空闲磁盘空间;软件配置平台Windows 7操作系统,微软SQL服务器数据库系统,C / S结构的操作模式。实验是基于三个数据集:Geolife,亚马逊访问样本和多样化数据集Div400。Geolife源数据库的数据集全球定位系统(GPS)轨迹的商店,UCI机器学习库,马塞诸斯州大学的跟踪存储库。实验数据集包括用户的位置信息和nonlocation信息。数据集的大小和属性特征如表所示2。
5.2。实验结果
常用的空间索引技术可以提高空间信息数据库的运行效率。的DPL-Hc计划增加微分隐私匿名技术基于四叉树空间索引技术和位置空间递归分为不同层次的树结构。当空间数据对象是均匀分布的,他们有更高的空间数据插入和查询效率。的KDCK-medoids算法(14)增加微分隐私匿名技术的基础上k d树空间索引技术。的k d树是一种结构性的多维检索。它把位置点的k维空间,使得相应的分支决策对象的鉴别器层在每一层。它良好的性能相同的二叉树匹配和找到确切的点(平均搜索长度 )。的PR-CAN算法(15]介绍了r树空间索引技术使本地索引满足微分隐私的要求。所有的叶子节点的重叠区域r树被改变成不相交的区域。为叶节点互斥的地区,独立噪声添加机制公关树满足微分隐私的要求。本文的数据可用性、隐私保护的程度,世代时间的匿名数据集用于验证该方案的有效性。
5.2.1。数据可用性
在仿真实验中,逐渐增加的情况下的隐私预算 ,我们测试三个数据集满足隐私需求,比较了匿名数据输出精度的算法,并分析算法的数据可用性在不同的隐私预算 。选择不同的尺度转换参数 ,全球灵敏度噪声的数量成正比和隐私预算成反比。验证的影响DPL-Hc计划,KDCK-medoids算法,PR-CAN算法在数据可用性微分隐私保护的需求下,算法的性能在不同的数据集和测试不同的隐私的预算需求。精密的分析发表的数据能反映算法的可用性来处理数据集的情况下满足查询的要求。每个实验数据集的出版数据精度数据所示6- - - - - -8。
隐私的预算是隐私保护的程度成反比。当隐私预算较小,数据保护的程度更大,当隐私保护的程度 ,完美的隐私。从数据可以看出6- - - - - -8隐私保护的增加预算,微分算法对出版数据的保护程度减少,所以数据可用性的三个算法增加了。空间四叉树生成的树结构索引的位置与本文无关的性质实验的数据集,所以微分隐私发布数据的精度提高基于四叉树索引和隐私的增加预算。相比KDCK-medoids算法和PR-CAN算法,DPL-Hc方案具有较高的数据可用性,同时保持一定的算法稳定。然而,随着隐私的增加预算,精密的KDCK-medoids算法和PR-CAN算法比低DPL-Hc方案;也就是说,他们有可怜的数据可用性和算法的稳定性。
5.2.2。隐私保护的程度
(1)之间的关系程度的隐私保护和拉普拉斯变换尺度参数b。隐私保护算法的性能和研究之间找到最佳平衡数据可用性和隐私保护的程度、实验分析和比较每个数据集的平均隐私保护程度在不同的拉普拉斯变换尺度参数 ,和更大的尺度参数b,隐私保护的程度就越高。比较DPL-Hc计划与KDCK-medoids算法和PR-CAN算法,实验的结果数据集被匿名差动保护隐私数据所示9- - - - - -11。从实验结果中,我们可以看到,拉普拉斯变换的尺度参数b的隐私保护程度DPL-Hc方案可以达到80%以上,与匿名性要求的提高,算法的执行效率不会大大减少。然而,隐私保护的程度KDCK-medoids算法和PR-CAN尺度参数时算法是不到80%b相对较小。从图也可以看出,当尺度参数b的隐私保护程度,确定吗DPL-Hc计划比高KDCK-medoids算法和PR-CAN算法,随着规模的增加参数b的隐私保护性能DPL-Hc方案更稳定。
(2)之间的关系程度的隐私保护和匿名Nonlocation数据比k。为了保护用户的位置隐私更好,DPL-Hc方案考虑用户的位置隐私的推理nonlocation信息和执行微分对超过70%的nonlocation数据匿名处理。更大的比例k的匿名nonlocation数据,用户的位置隐私保护就越高。假设每个数据的敏感用户的nonlocation数据集是平等的,人物12显示的影响DPL-Hc计划在位置隐私保护的程度不同的匿名nonlocation数据比例k和数据集的需求。
通过实验比较,我们可以看到,随着比例的增加k匿名nonlocation数据,每个数据集的隐私保护程度提高。从实验中也可以看出,当匿名nonlocation数据比例k是固定的,每个数据集的隐私保护程度并没有太大的区别;也就是说,DPL-Hc方案具有良好的算法稳定的前提下,确保隐私保护程度。然而,从数据可用性的角度来看,匿名nonlocation数据比例k将数据可用性有一定的影响,所以nonlocation数据比例k不应过高,k设置为75%。
5.2.3。匿名数据集的生成时间
考虑添加微分隐私匿名方法的选择,不同的空间索引树,所采取的平均时间DPL-Hc计划,KDCK-medoids算法,PR-CAN算法来生成匿名数据集如表所示3- - - - - -5。数据13- - - - - -15显示比较结果世代时间的三种方法在不同的数据集和隐私的预算 ,在哪里 。
从数据可以看出13- - - - - -15,增加隐私的预算 ,也就是说,隐私保护程度的减少DPL-Hc计划需要更少的时间来生成匿名数据集比PR-CAN算法,DPL-Hc方案更有效生成匿名数据集。因为DPL-Hc方案采用四叉树空间索引技术,这种技术与数据无关的过程中构建四叉树和构建四叉树的过程中避免不必要的开销。当 ,设定的时间生成匿名数据DPL-Hc计划是由略高于KDCK-medoids算法。当 ,设定的时间生成匿名数据DPL-Hc计划是低于KDCK-medoids算法。
通过比较,我们也可以看到,减少 ,时间的三个算法生成匿名数据集越来越多,但是DPL-Hc计划显然是小于KDCK-medoids算法和PR-CAN算法。换句话说,增加 ,的DPL-Hc计划花费更少的时间,更有明显的优势,更实用。
通过以上实验比较,发现DPL-Hc方案具有较高的数据可用性和生成时间短的匿名数据集的前提下尽量满足隐私保护。的DPL-Hc方案可以保护用户的位置隐私和有效提高定位服务的质量。
6。结论
针对平衡隐私保护的程度和服务质量磅系统,一个微分隐私位置保护计划基于希尔伯特曲线的基础上提出现有微分隐私模型。该计划不再依赖TTP并将拉普拉斯噪声添加到用户的位置在一维空间中映射的希尔伯特曲线。它可以防止敌人的袭击与背景信息和具有强大的隐私保护的力量。它可以有效地解决隐私保护程度之间的平衡问题和质量的服务。实验结果表明,该DPL-Hc方案有明显的优势在数据可用性、隐私保护的程度,世代时间的匿名数据集。
数据可用性
使用的数据来支持本研究的发现可以从相应的作者。
的利益冲突
作者宣称没有利益冲突。
确认
这项工作得到了国家自然科学基金(批准号61702316)和山西省自然科学基金(批准号201801 d221177和201801 d111280)。