CN109121133B

CN109121133B - 一种位置隐私保护方法及装置

Info

Publication number: CN109121133B
Application number: CN201811035439.2A
Authority: CN
Inventors: 李凤华; 牛犇; 王瀚仪; 耿魁; 王竹
Original assignee: Institute of Information Engineering of CAS
Current assignee: Institute of Information Engineering of CAS
Priority date: 2018-09-06
Filing date: 2018-09-06
Publication date: 2020-09-15
Anticipated expiration: 2038-09-06
Also published as: CN109121133A

Abstract

本发明涉及一种位置隐私保护方法及装置，对位置隐私保护算法的服务质量影响和隐私保护效果进行了统一的建模；面向任意场景，通过对服务质量与位置隐私的需求，去选择甚至设计满足条件的位置隐私保护算法；对App从服务质量需求的角度进行划分，基于机器学习和自然语言处理的技术对App的需求进行学习训练，构建出分类效果较好的分类器；对当前不同的LPPM和针对不同LPPM的攻击方式进行实现和仿真，较合理的评估了现有LPPM的隐私保护效果和对服务质量的影响。本发明确保在对服务质量有不同需求的场景中能够提供满足该服务质量需求的服务，同时又能以最大力度保护位置隐私。

Description

一种位置隐私保护方法及装置

技术领域

本发明涉及一种位置隐私保护方法及装置，属于移动通讯领域。

背景技术

位置服务是基于当前GPS、北斗等定位系统而衍生出的一类以获取用户位置信息为基础，响应用户服务请求的移动服务技术。随着智能终端的普及，移动技术和通信技术的紧密结合和发展，各种新型的服务模式应运而生。基于位置的服务LBSs(Location BasedServices)作为新型移动服务的典型代表，迅速的被人们所接受认可，在智能终端上发展起来。使用LBSs过程中，LBS服务器一方面由于所提供服务的性质需要获知用户当前位置信息，另一方面为了提供更加个性化的服务需要记录用户历史位置信息以此推断用户偏好等；利用这些信息，服务商收到用户请求后，通过在后台服务器查询，利用移动通信网络对用户请求进行响应。拥有获取用户当前位置信息权限和大量敏感位置信息的服务商有损害用户隐私安全、牟取利益的动机，属于用户需要提防的不可信方；然而，服务商又需要以高度精确的位置信息为基础，提供高质量的位置服务。为权衡上述互相制约的两个问题，各种位置隐私保护技术在各类特定场景下被提出。

由于LBSs本身在隐私安全和服务质量两个方面相互对立的特质，位置隐私保护总是以牺牲位置服务质量为代价实现的，因而现有的位置隐私保护技术在特定的场景下能够以牺牲固定的服务质量为代价实现特定的隐私保护效果。然而通常在不同的场景下，对服务质量有不同的要求，如果总是采用相同的方法对位置信息进行保护，会造成服务质量过低影响用户体验或者服务质量过高产生不必要的冗余等后果。

发明内容

本发明的技术解决问题：克服现有技术的不足，提供一种基于服务质量动态识别的位置隐私保护方法及装置，确保在对服务质量有不同需求的场景中能够提供满足该服务质量需求的服务，同时又能以最大力度保护位置隐私。

本发明技术解决方案：一种位置隐私保护方法，包括以下步骤：

步骤1：对原始位置信息，使用若干位置隐私保护机制，即LPPM方法进行隐私保护，得到隐私保护后的位置信息；

步骤2：对位置隐私保护效果与服务质量影响进行统一的建模，并得到所述若干LPPM方法中每个LPPM方法的隐私保护效果的参数和服务质量影响的参数；所述服务质量影响的参数为App使用所述经隐私保护后的位置信息所提供的服务质量与App使用所述原始位置信息提供的服务质量之间距离即差距的分布期望，所述分布期望包括隐私保护信息前后的位置间的距离期望；所述位置隐私保护效果的参数为所述经隐私保护后的位置信息被攻击者试图重构还原后得到的位置，与所述原始位置信息之间距离分布的期望；

步骤3：针对不同App，采用机器学习方法建立不同App的服务质量需求模型，以确定所述不同App的服务质量需求；

步骤4：针对某App与某原始位置信息，根据步骤3得到的所述若干App的服务质量需求与步骤2得到的所述每个LPPM方法的隐私保护效果的参数和服务质量影响的参数，从所述若干LPPM方法中选取所述服务质量影响参数满足所述某App的服务质量需求且所述隐私保护效果参数最大化的LPPM方法，对所述某原始位置信息进行隐私保护，得到经所述LPPM方法隐私保护后的位置信息。

所述步骤2中具体过程如下：

(1)已知被某LPPM方法保护后的位置，攻击者通过背景知识，如果已知LPPM的具体方法，分析推断保护前原始位置的可能概率分布，并根据所述概率分布，计算保护前位置与保护后可能位置的距离的期望值，即为所述LPPM方法的隐私保护效果；

(2)对所述LPPM方法进行判断，得到原始位置经所述LPPM方法保护后可能位置的概率分布，并根据所述概率分布，计算在保护前后的位置，服务商能够提供的服务的距离的期望值，即为所述LPPM方法的服务质量影响。

所述步骤2中，所述服务质量之间距离包括欧氏距离、马氏距离、汉明距离或广义Jaccard系数。

所述步骤3实现过程如下：

(1)收集若干App、每个App的描述文字段及功能分类，标记每个App的服务质量需求，得到样本集；

(2)从步骤(1)得到的所述每个App的描述文字段中提取特征向量；

(3)将步骤(1)得到的样本集按照一定比例划分为训练集与测试集；

(4)选取机器学习方法，构建机器学习模型，利用步骤(2)得到的特征向量与步骤(3)得到的所述训练集与所述测试集学习，所述机器学习模型经训练评估后，建立所述不同App的服务质量需求模型，以确定所述不同App的服务质量需求。

所述步骤3中，在步骤(4)后还包括，步骤(5)根据用户反馈更新所述样本集，得到更新后的样本集，重新训练或采用增强学习方法训练所述机器学习模型。

所述步骤3中，所述机器学习方法包括朴素贝叶斯或SVM或神经网络算法；对于朴素贝叶斯，利用贝叶斯定理，分别计算各个输入样本的先验概率；再计算该样本在各个独立特征下的条件概率。

所述步骤(1)中，从谷歌play store收集若干App及每个App的描述文字段。

所述步骤3的步骤(2)中，采用自然语言处理方法，对所述每个App的描述文字段进行关键词提取，将得到的关键词构造所述特征向量。

本发明的一种位置隐私保护装置，包括：

输入模块，用于获取某原始位置信息与某App；

LPPM方法参数确定模块，用于确定不同LPPM方法的隐私保护效果参数和服务质量影响参数；

App服务质量需求判别模块，用于建立App的服务质量需求模型，确定App的服务质量需求；

LPPM方法选取模块，针对所述输入模块获取的所述某App，根据所述LPPM方法参数确定模块提供的所述不同LPPM方法的隐私保护效果参数和服务质量影响参数与所述App服务质量需求判别模块提供的App的服务质量需求，选取所述服务质量影响的参数满足所述某App的服务质量需求且所述隐私保护效果参数最大化的LPPM方法；

隐私保护模块，针对所述输入模块获取的所述某原始位置信息，根据所述LPPM方法选取模块选取的LPPM方法，进行隐私保护，得到经隐私保护后的位置信息；

输出模块，用于输出所述隐私保护模块提供的所述经隐私保护后的位置信息；

其中，所述App服务质量需求确定模块中，所述建立App的服务质量模型包括：

(4)选取特定机器学习方法，构建机器学习模型，利用步骤(2)得到的特征向量与步骤(3)得到的所述训练集与所述测试集学习，所述机器学习模型经训练评估后，建立所述不同App的服务质量需求模型，以确定所述不同App的服务质量需求。

本发明与现有技术相比的优点在于：

(1)对位置隐私保护算法的服务质量影响和隐私保护效果进行了统一的建模；现有技术大多针对一种特定场景去设计特定的位置隐私保护算法，同时去度量其服务质量和位置隐私；本发明则面向任意场景，通过对服务质量与位置隐私的需求，去选择甚至设计满足条件的位置隐私保护算法。

(2)对App从服务质量需求的角度进行划分，基于机器学习和自然语言处理的技术对App的需求进行学习训练，构建出分类效果较好的分类器。

(3)对当前不同的LPPM和针对不同LPPM的攻击方式进行实现和仿真，较合理的评估了现有LPPM的隐私保护效果和对服务质量的影响。

附图说明

图1为本发明的框架示意图；

图2为本发明中分类器；

图3为本发明中LPPM选择优化算法的流程图。

具体实施方式

下面结合附图及实施例对本发明进行详细说明。

本发明提供的基于现有的位置隐私保护技术LPPMs(Location PrivacyPreserving Mechanisms)和机器学习技术的位置隐私保护方案，能够适应不同的场景需求，如图1所示，主要步骤包括：

(1)对位置隐私和服务质量进行建模描述。

LPPMs能达到的隐私保护效果Privacy_LPPM指，被该LPPM保护后的位置信息被攻击者试图重构还原后得到的位置loc_{reconstructed}和原始位置loc_original间距离的分布期望。

同理，LPPM对服务质量的影响QoS_LPPM是指，服务商利用被该LPPM保护后的位置信息提供的服务service_modified和使用原始位置信息提供的服务service_original的距离分布期望。该距离指广义的距离，在实例化中，可以使用地理位置上的欧氏距离、马氏距离或者返回服务内容之间的汉明距离、广义Jaccard系数等计算度量。

(2)对现有隐私保护方法根据(1)中的建模描述，从服务质量影响和隐私保护效果两方面进行评估，得到每个隐私保护方案能达到的隐私保护效果Privacy_LPPM和对服务质量的影响QoS_LPPM两个参数。

(3)训练分类器，输入为App的描述文字段，输出为App的服务质量需求。

(4)对于一个请求位置信息的App，将其根据描述字段进行服务质量需求分类，鉴别出该App对服务质量的要求。根据(2)中对现有LPPM的评估结果，选取可以满足该服务质量需求的同时，在该范围内保证隐私最大化的LPPM对位置信息进行保护。

如图2所示，其中，(3)中训练用以区分服务质量需求的分类器，该过程分为五步：

1)爬取谷歌play store中现有的top 500的App及其相应的描述文字段，根据其在play store中现有的功能分类，对其服务质量需求进行粗粒度的标记。

2)从描述文段中提取特征向量。对描述文段中的单词进行关键词提取，构造特征向量。其中，特征向量中的分量可以重复。

3)对样本按照随机采样的方法按照2：1的比例进行训练集和测试集的划分。

4)根据实验效果，从朴素贝叶斯、SVM等现有分类中选择计算简单并且效果较好的朴素贝叶斯分类器作为本方案的分类器选择。

5)在对用户提供过服务之后，得到用户的反馈数据，反馈数据构成一个新的标记过的训练样本，当新的样本积累到一定数量，对现有分类器进行更新。更新频率可以根据计算量大小而定；更新方式可以采用重新训练或者增量式训练等。

下面结合具体的实施例进行详细说明。

假设整张地图被均匀划分为m＝|G|个格子，G＝{g₁,g₂,…,g_m}为格子的集合，其中g_i表示第i个格子。用户的位置轨迹集合是T，表示用户在不同时间的位置集合。基于服务质量识别的位置隐私保护方法包括以下五个步骤：

(1)对LPPM的建模。

用户的某个位置g∈T在被LPPM保护过后，会被转化为新的一个格子、几个格子组成的范围或者空集，这些可能的转化都包含在原始位置集合的幂集当中，即生成了新的位置格子

其中

是G的幂集，即

因此，可合理的将现有的LPPM建模为从集合G到

的映射：

(2)对QoS的建模。

在本发明的实例中，将QoS_LPPM定义中的distance实例化为被LPPM保护后的位置和原始位置格子中心的欧氏距离。每个位置由一个二元组表示：g＝(x,y)，x，y分别是该位置格子中心g的经度和纬度，对应的，被LPPM保护后的位置格子中心为

分别为

坐标的经度和纬度。

(3)对位置隐私保护效果的建模。

在对位置隐私保护效果建模的过程中，首先要标准化敌手模型和攻击方法。在本发明实例中，将现有的轨迹攻击方法应用到对单点位置进行攻击的场景下：

敌手模型构造如下：

在本发明实例化中对单点位置进行攻击，不考虑用户位置点之间的时间关系，即位置点之间是相互独立的。为了强化敌手模型，假设敌手拥有用户所有历史位置数据，敌手可以根据此知识构造出所有用户在各个位置点发送服务请求的频率分布：

其中，

指用户u在位置格子g_i处发送位置服务请求的频率。并且，敌手掌握所有LPPM技术以及我们所使用的LPPM的组合，并以此为参照，能够掌握每一个原始位置点转换后得到的被保护位置点，根据此知识可以构造一个保护前和保护后位置之间转换概率分布

表示原始位置为g_i的时候，经过该保护方法位置被转换为

的概率，即

具体攻击方法如下：

表示敌手对用户进行还原攻击，通过某种方法对观察到的

进行重构后，得到的用户原始位置的可能性分布。

是一个分布集合：

其中

表示攻击者重构后认为用户真实位置在g_i的概率。重构的位置集合记为

根据先验概率，当敌手观察到在时间点t，用户从位置

发送服务请求，则此时敌手认为用户真实位置处于g_i的概率为：

此时位置隐私保护效果Privacy的具体计算如下：

Privacy_LPPM是表示该LPPM在攻击者的攻击方法下，在每一个位置点g的保护效果分布集合。保护效果越好，隐私保护程度越高，攻击者对这个位置实施攻击的结果和原始位置相差越远，在该位置的Privacy值就越大。最终，用户轨迹集合上每个位置对应的Privacy值构成了Privacy_LPPM分布集合。

LPPM(Location Privacy Preserving Mechanism)：位置隐私保护机制；

T是用户的位置轨迹集合，表示用户在不同时间的位置集合；

t为某一时间点。

根据上述模型，使用不同的LPPM在标准数据集和统一建模的地图上对用户进行保护后，再模拟攻击者进行攻击，得到各个LPPM在隐私和QoS两个纬度上的得分。

(4)分类器建模

分类器的构建按照本发明的方案中步骤(3)的描述，首先提取每个App描述文段的特征向量。

采用短文本关键词提取方法，例如TextRank，得到App描述文段的关键词word₁,word₂,…，由此构造特征向量：(word₁,word₂,…)。

根据节(2)中对现有LPPM的QoS度量，得到QoS的取值范围，并由此对QoS需求进行人为划分，在本发明实施例中，根据现有App所拥有的功能，将QoS划分为十个需求等级，表示为QoS_i，1≤i≤10。

对App样本根据其功能进行标记，将得到的标记集合中的三分之二数据作为训练集，三分之一数据作为测试集，构建分类器，分类器中的初始化文本库：((word₁,word₂,…),QoS_i)。

对于一个新来的App，根据贝叶斯定理：

得到该App所属的QoS需求等级QoS_i。根据QoS需求进行步骤(5)中的LPPM选择算法，将最终被算法保护后的位置返回给请求位置的App。

用户享受过基于该次位置的服务后，对该次服务进行评分：“非常满意”、“满意”、“不满意”。评分后得到一个被用户标记过的样本：((word₁,word₂,…),QoS_i)，若评分为“不满意”，则i′＝i+1；若评分为“满意”，则i′＝i；否则，说明服务质量有一定的冗余空间，可以适当降低，于是i′＝i-1。

(5)LPPM选择算法。

利用(4)中的分类器，将一个App进行分类，可以得到该App对服务质量的需求范围，该范围被认为是该App可以接受的服务质量范围。在满足这个服务质量范围的LPPM中，选择隐私程度最高的一个LPPM，该LPPM即为保证QoS需求的条件下满足隐私保护程度最大化的LPPM。

在此次实例化中，将LPPM类型限制在具有不同参数的泛化方法中，泛化的参数为μ_x,μ_y，表示对位置坐标的经纬度去掉的小数点位数。LPPM(μ_x,μ_y)表示一个具体的位置隐私保护算法以及确定的参数设置。需要由本发明确定的参数为μ_x，μ_y。根据QoS需求，找到每个参数符合QoS需求的取值范围Γ(μ_x)，Γ(μ_y)。从该取值范围中，找到一个使Privacy最大的参数取值。

求极值最原始的方法是遍历自变量取值范围中所有取值可能性，即遍历Γ(μ_x)，Γ(μ_y)中所有取值，复杂度为|Γ(μ_x)|×|Γ(μ_y)|。在备选方案数量增加，备选参数取值范围增加的时候，原始的遍历方法可扩展性较低，于是这里提出采用模拟退火的优化算法进行参数选择，算法的具体过程如下：

步骤1：初始化参数，随机为参数赋值，要求所赋值在参数的取值范围中，令μ_x＝a₁,μ_y＝a₂。

步骤2：初始化Step为每次迭代时参数可改变的范围区间，在本实例中，Step＝[-m,k-m]是一个动态区间，其中m为参数μ_x或μ_y当前的值，k为参数能达到的最大值，即为泛化前坐标的小数点位数。

步骤3：给定隐私保护程度函数privacy(·)；给定退火算法的初始温度t₀，每次循环降低温度比率cool，每次循环迭代次数N；令当前LPPM的隐私保护程度f_max＝privacy(LPPM(a₁,a2))。

步骤4：根据模拟退火的优化算法原理，当温度参数t大于t₀时，转到步骤5，否则，执行步骤7。

步骤5：对位置坐标的经纬度去掉的小数点位数参数μ_x,μ_y进行迭代，迭代μ_x＝μ_x+k₁·random(Step)，μ_y＝μ_y+k₂·random(Step)，其中k₁，k₂是调节参数，设置为0.25。在迭代次数不超过N的条件下，执行步骤6；若迭代次数超过N，则令温度参数t＝t·cool，并转到步骤4。

步骤6：计算本次迭代后的隐私保护程度f_tmp＝privacy(LPPM(μ_x,μ_y))，若f_tmp＞f_max，则完全接受本次迭代结果；若f_tmp＜f_max，则以概率

接受这次迭代，否则维持迭代前的结果。迭代次数增加1，并转到步骤5。

f_max：隐私保护程度；

cool：每次循环降低温度比率；

e：自然常数。

步骤7：返回当前μ_x，μ_y的值。

该算法以privacy(LPPM(a₁,a₂))最大化为目标，复杂度控制在

内。循环内部，构造新的参数取值方案，求privacy函数值的复杂度都为1，循环次数为

即复杂度为

根据试验中极值的求解效果，选取能极大程度找到最优解同时保证循环次数最少的平稳点的参数，作为最终的选择LPPM优化算法的参数选取。

提供以上实施例仅仅是为了描述本发明的目的，而并非要限制本发明的范围。本发明的范围由所附权利要求限定。不脱离本发明的精神和原理而做出的各种等同替换和修改，均应涵盖在本发明的范围之内。

Claims

1.一种位置隐私保护方法，其特征在于，包括以下步骤：

步骤3：针对不同App，采用机器学习方法根据每个App的描述文字及功能分类，以及对应的服务质量需求建立不同App的服务质量需求模型，根据某App的描述文字及功能分类采用服务质量需求模型确定所述某App的服务质量需求；根据用户对位置服务的评价调整App的服务质量需求，根据调整后的App的服务质量需求重新训练服务质量需求模型；

步骤4：针对某App与某原始位置信息，根据步骤3得到的所述某App的服务质量需求与步骤2得到的所述每个LPPM方法的隐私保护效果的参数和服务质量影响的参数，从所述若干LPPM方法中选取所述服务质量影响的参数满足所述某App的服务质量需求且所述隐私保护效果的参数最大化的LPPM方法，对所述某原始位置信息进行隐私保护，得到经所述LPPM方法隐私保护后的位置信息。

2.根据权利要求1中所述一种位置隐私保护方法，其特征在于：所述步骤2中具体过程如下：

（1）已知被某LPPM方法保护后的位置，攻击者通过背景知识，如果已知LPPM的具体方法，分析推断保护前原始位置的可能概率分布，并根据所述概率分布，计算保护前位置与保护后可能位置的距离的期望值，即为所述LPPM方法的隐私保护效果；

（2）对所述LPPM方法进行判断，得到原始位置经所述LPPM方法保护后可能位置的概率分布，并根据所述概率分布，计算在保护前后的位置，服务商能够提供的服务的距离的期望值，即为所述LPPM方法的服务质量影响。

3.根据权利要求1所述的一种位置隐私保护方法，其特征在于：所述步骤2中，所述服务质量之间距离包括欧氏距离、马氏距离、汉明距离或广义Jaccard系数。

4.根据权利要求1所述的一种位置隐私保护方法，其特征在于：所述步骤3实现过程包括如下步骤：

（1）收集若干App、每个App的描述文字段及功能分类，标记每个App的服务质量需求，得到样本集；

（2）从步骤（1）得到的所述每个App的描述文字段中提取特征向量；

（3）将步骤（1）得到的样本集按照一定比例划分为训练集与测试集；

（4）选取机器学习方法，构建机器学习模型，利用步骤（2）得到的特征向量与步骤（3）得到的所述训练集与所述测试集学习，所述机器学习模型经训练评估后，建立所述不同App的服务质量需求模型，根据某App的描述文字及功能分类采用服务质量需求模型确定所述某App的服务质量需求。

5.根据权利要求4所述的一种位置隐私保护方法，其特征在于：所述步骤3中，在步骤（4）后还包括，步骤（5）根据用户反馈更新所述样本集，得到更新后的样本集，重新训练或采用增强学习方法训练所述机器学习模型。

6.根据权利要求1所述的一种位置隐私保护方法，其特征在于：所述步骤3中，所述机器学习方法包括朴素贝叶斯或SVM或神经网络算法；对于朴素贝叶斯，利用贝叶斯定理，分别计算各个输入样本的先验概率；再计算该样本在各个独立特征下的条件概率。

7. 根据权利要求4或5所述的一种位置隐私保护方法，其特征在于：所述步骤（1）中，从谷歌play store收集若干App及每个App的描述文字段。

8.根据权利要求4或5所述的一种位置隐私保护方法，其特征在于：所述步骤3的步骤（2）中，采用自然语言处理方法，对所述每个App的描述文字段进行关键词提取，将得到的关键词构造所述特征向量。

9.一种位置隐私保护装置，其特征在于，包括：

输入模块，用于获取某原始位置信息与某App；

App服务质量需求判别模块，用于根据每个App的描述文字及功能分类，以及对应的服务质量需求建立App的服务质量需求模型，根据某App的描述文字及功能分类采用服务质量需求模型确定某App的服务质量需求；根据用户对位置服务的评价调整App的服务质量需求，根据调整后的App的服务质量需求重新训练服务质量需求模型；

LPPM方法选取模块，针对所述输入模块获取的所述某App，根据所述LPPM方法参数确定模块提供的所述不同LPPM方法的隐私保护效果的参数和服务质量影响的参数与所述App服务质量需求判别模块提供的App的服务质量需求，选取所述服务质量影响的参数满足所述某App的服务质量需求且所述隐私保护效果的参数最大化的LPPM方法；

其中，所述App服务质量需求确定模块中，所述建立App的服务质量模型包括如下步骤：

（4）选取特定机器学习方法，构建机器学习模型，利用步骤（2）得到的特征向量与步骤（3）得到的所述训练集与所述测试集学习，所述机器学习模型经训练评估后，建立不同App的服务质量需求模型，根据某App的描述文字及功能分类采用服务质量需求模型确定所述某App的服务质量需求。