面向位置大数据的差分隐私保护研究

张建坤，马永发，谢 蔚

(广东工业大学 自动化学院，广东 广州 510006)

0 引言

随着移动通信和互联网技术的飞速发展，世界进入了大数据时代。通过对大量数据的采集、处理和分析，从中能准确高效地提取所需要的信息，极大方便了人们的学习、生活。目前，智能手机、可穿戴设备、传感器和其它可视化设备已经将人与事物的地理位置数据化，从中可获得各种各样的服务和应用，如车载导航、社交软件的位置共享和签到，搜索附近的服务机构和实时查询交通信息等，这些服务在带来极大便利的同时也可能导致隐私泄露。移动终端和传感器能实时记录用户的位置和移动轨迹，并传入互联网和云端，这时用户的个人信息就暴露在互联网上[1]。一些服务商将这些位置数据倒卖，不法分子通过这些数据推断出用户工作角色、年龄、兴趣爱好、健康状况等个人隐私信息，极大威胁个人隐私安全。因此，如何保护好个人位置信息不被泄露成为急需解决的安全问题。

位置隐私保护研究很多，如数据扰乱[2]、数据加密[3-5]、数据匿名[6]等隐私保护技术。其中k-匿名模型[7-9]由于能保证所发布数据的真实性与安全性，受到了学术界的广泛关注[10]。位置大数据的隐私保护技术有3大类：基于启发式隐私度量、基于概率推测和基于隐私信息检索的位置大数据隐私保护技术[11]，但这些技术都忽视了基于背景知识的攻击。文献[12]通过将攻击者所掌握的背景知识进行分类，使用位置混淆隐形机制取得了隐私和服务精度的平衡；文献[13]提出了一种新的上下文感知和非上下文感知差异保密技术，耦合卡尔曼过滤和指数机制，确保隐私时空数据安全；文献[14]研究了一种基于差分的隐私机制，对位置数据进行清洗，获得了较高的数据可用性；文献[15]提出了“模糊化”查询数据操作，把位置数据藏在一个隐藏的磁盘中，防止位置服务器查询到确切位置；文献[16]开发了提供隐私保护策略的分析框架,设计衡量移动用户隐私的度量标准(称为隐私度量)，并量化服务质量；文献[17]将各种基于位置的服务(LBS)进行分类，分析各种隐私泄露类型，提出一种以保护查询内容为目的的安全方法；文献[18]提出了LBS群组用户位置扰乱算法(GPOL)，将群组最近邻查询转换为群组质心的最近邻查询，有效抵御了现有交叉攻击和组合攻击。上述方法能很好地从服务云端保证位置隐私安全，但都忽略了攻击者从相关非位置数据直接或间接地挖掘出个人敏感信息而导致位置隐私泄露的问题。

1 差分隐私保护模型

1.1 相关背景知识

差分隐私保护是一种可以防止攻击假设和一定背景知识攻击的隐私保护技术。通过添加噪声干扰敏感数据，输出中的每条记录均得到完全相同程度的保护，同时也保持数据属性不变，保证添加噪声后仍具有统计性。即使攻击者已经知道除一条记录外的所有记录，仍然无法推断出有关这条记录的任何敏感属性[19]。

定义1 (位置差分隐私)位置数据集D和D′存在且仅存在一条记录相异，随机算法M对D和D′的任意输出L⊆Range(M)均满足公式(1)，则称M满足ε-位置差分隐私[20]。

Pr[M(D)∈L]≤Pr[M(D′)∈L]eε

(1)

其中，概率Pr[]表示任意两个数据集经过算法M输出为L的概率；参数ε为隐私保护预算，衡量隐私保护强度，ε越小隐私保护程度越高。

定义2 (拉普拉斯噪音机制[21])对于任意一个函数f：D→Rd，算法Y满足：

1.2 位置隐私保护方法流程

现有位置大数据服务中，一般是把从各渠道采集的与位置数据相关的数据集存入云数据库中，用户通过查询函数调取所需数据。基于差分隐私的保护方法，就是将真实结果通过算法K获得加噪扰动后的结果返回给用户，此结果不会影响整体统计特性，具体保护框架如图1所示。

图1 差分隐私保护框架

以上隐私保护模型关键在于添加一个合理的噪声机制，构建差分隐私算法，将加噪后的数据结果返回给用户。

本文提出的位置差分隐私算法步骤如下：

(1)位置数据预处理。数据集包括位置数据和与之相关的非位置数据，因此需要分开处理。根据空间分解技术将空间维度的数据分解为基本数据集，保留含有位置元素的语义信息。

(2)合理分配隐私预算。对数据预处理后的结果根据其大小、类型和语义对隐私预算ε进行合理分配，防止隐私预算过度消耗使算法失效。

(3)构建差分隐私算法K。用差分隐私技术分别对不同类别的数据添加噪声，找到最佳噪声比，保证位置数据的服务质量。

(4)安全返回查询结果。将分类处理的位置数据重组，计算其统计特性返回给用户。

1.3 差分隐私保护算法

根据保护强度选定隐私预算ε，对用户查询相关的数据集添加噪声，使之满足差分隐私要求。其中包括位置数据集L={L1,…,LK}和非位置数据集D={D1,…,DK}，分别添加拉普拉斯噪声LapNoise扰动真实值，Q为查询函数。

差分隐私保护算法如下：

输入隐私保护预算ε0，位置数据集L，非位置数据集D，变量i、k、Diff-PrivacyData、T

for Δf≤T

if 数据集属于位置数据L∈{L1,…,LK}

RL=LapNoiseQ(L)，其中RL为加噪后的结果，Q(L)为包含查询需要的位置数据

else 数据集属于非位置数据D∈{D1,…,DK}

Rd=LapNoiseQ(D)，其中Rd为加噪后的结果，Q(D)为包含查询需要的非位置数据

end if

ifε≤ε0

return Diff-PrivacyData(RL，Rd)

else

return 隐私预算ε超出范围

end

1.4 算法性能分析

考虑到大数据背景下位置数据体量大、更新速度快的特点，敏感属性数据会随着时间的变化影响系统性能，动态数据集的敏感度会发生改动，本算法创新加入了一个敏感度Δf的阈值T。一旦由于数据集中目录的增减、修改导致敏感度超过了阈值，就可对隐私预算进行可控调节，实时监管数据的更新信息。

评估算法性能优劣的一个重要标准，就是对用户的服务质量也就是用户查询返回的结果是否达到预期进行评价。对同一查询函数Q，敏感数据在匿名前后输出R(Q)和R(Q′)的近似程度表示算法的可用性，近似程度越高表明服务质量越高，误差越小。误差SR可定义为两输出结果的一阶范数值SR=‖R(Q)-R′(Q)‖。

对于位置服务，通常都是连续查询Qi∈{Q1…QK…}。定义数据可用性参数满足：

(2)

当匿名发布数据的可用性参数E低于用户查询要求时，可通过调节隐私预算ε保证算法的可用性能，从而获得算法的高效性、实用性。

2 实验结果与分析

对本文隐私保护算法是否可行进行验证，实验环境：Inter Core i5处理器，2.4GHz的主频CPU，Win7操作系统，程序运行环境为Python2.6.6。针对实验所需真实数据集，在数据库GeoLife GPS Trajectories中下载了数据集GeoLife，其中包括经纬度、地理、城市规划等位置数据，也包括交通方式、生活服务和社交信息等非位置数据，完全符合实验要求。

对于经过匿名算法后的数据集Diff-PrivacyData，分析数据在发布前后的误差和可用性是衡量该算法可行性的最基本标准，否则就失去了大数据本身的价值。为了找到数据可用性与隐私保护程度的最佳试配比，在固定ε=0.8的情况下，分析出合理的变换尺度a和数据隐私保护程度的关系，实验结果如图2所示。

图2 数据相对误差

图3 数据可用性

图4 隐私保护程度

从图2可以看出，算法前后的输出误差和隐私预算有着紧密联系，大致形成一个波谷形式。在ε=0.8时数据相对误差最小，此时的数据准确性最高。结合图2、图3可以看出，数据误差和可用性是彼此吻合的，数据误差小其可用性就高。图4显示变换尺度和隐私保护程度呈反比。随着隐私预算的递增，差分算法对数据的泛化程度减小，数据可用性也随之增加；但当隐私预算一定时，随着变换尺度的增加，意味着用户有较高的匿名要求，隐私保护的程度却相对减弱，因此选择一个合适的隐私预算至关重要。总体来看，数据可用性和隐私保护程度都基本保持在80%以上，说明该隐私保护算法具有较好的稳定性。

3 结语

本文提出一种能有效防止基于背景知识攻击的差分隐私算法，引入随机噪声分别对不同类型的数据进行扰动，将加噪后的数据准确返回给用户，保证了大数据的价值和位置服务质量。实验结果表明，该位置隐私保护算法实现了数据可用性和隐私保护维度的有效平衡，对位置大数据隐私保护有一定的研究价值。与其它匿名隐私保护模型相比，基于差分隐私的保护方法能保证高质量数据运用于位置信息服务系统中，高效处理数据的定位、查询、分析和发布，是未来隐私保护数据方法的研究方向。