基于随机偏移和零交集偏移的匿名区域切换算法

王智明

(莆田学院 信息工程学院，福建 莆田 351100)

随着移动设备、智能终端、传感器等相关信息技术的快速发展，数据规模呈现出爆炸式增长，人类进入了大数据时代。那些海量的数据成为工业界和学术界研究的香饽饽。政府机构和各类企业争先恐后，试图从这些结构化、非结构化的数据海洋中挖掘更多隐藏的价值，进而获取社会效益或经济利益。基于位置的服务(LBS)集成了测绘、卫星导航、GIS、无线通信网络等相关技术，能为我们提供丰富的有关个人位置的各类服务，LBS 提高了个人活动的效率和方便性、提高了人与人、客户与商家的互动交流，极大地改变了我们的生活方式[1]。据业内预测，全球LBS市场规模将以40%左右的复合年增长率增长，到2020年市场容量有望达到348亿欧元。

而作为硬币的另一面，这些海量数据中既有巨大的价值，当然也会包含大量企业和个人不愿对外公布的隐私信息。一旦这些敏感信息泄露，将会给个人和企业带来名誉、经济上的损失，如何有效保护隐私信息，将会是越来越严峻的考验。用户个人隐私泄露的主要途径有：①用户的LBS查询，在发往服务器途中被截获；②黑客攻破服务器，直接获知用户LBS查询信息；③中间服务提供商或个人为获利将用户信息出售。通过非法获得这些用户信息，就可能获取或推断出用户兴趣爱好、生活习惯、宗教信仰、疾病历史等隐私信息[2]。因此位置隐私保护问题日益引起学术界的关注，也提出了不少关于位置隐私保护的解决方案，有些方案侧重保护用户标识符、查询内容[3]，但更多还是基于用户位置的隐私保护。

1 相关算法分析

2002年L.Sweeney提出了k-匿名(k-anonymity)模型[4]，要求匿名区域用户数量不少于k个，这样攻击者就不能从k个用户中找出真正用户。Gruteser等人[5]将k-匿名技术应用于LBS的隐私保护，对真实的用户位置概化处理，以达到模糊用户空间位置的目的。k-匿名被研究者们广泛接受使用，但是该模型没有对等价类中的敏感属性值数量加以限制，容易被攻击。为解决此问题，2006年，Machanavajjhala[6]改进了k-匿名模式提出了L-diversity，即L多样化，规定用户发布的每个信息属性等价类，必须包含不少于L个对应的敏感属性值。Ferrer等[7]于2008年提出了p-sensitive，在k-匿名技术的基础上,规定每个等价类中要有不少于p个敏感属性值。2016年，LI 等[8]提出了在连续LSB请求情形下的需求感知位置保护方案，通过删除最远足迹的方式来减小匿名区域的范围，提高了LBS查询服务质量。在确保第三方可信的前提下，SCHLEGEL等[9]提出了基于密文匹配的隐私保护方案，较好抵御查询跟踪攻击。Palanisamy等[10]则利用Mixzone概念，要求用户离开Mixzone时必须使用假名，这样避免攻击者通过分析区域关联性来获取真实用户信息。

在基于匿名区域的位置隐私保护的算法中，用户可以通过改变参数k的值来满足用户对隐私度高低的要求，但在进行匿名区域大小调整过程中，攻击者可能通过匿名区域切换前后的信息，推测出用户真实位置，进而导致隐私度切换失败。为解决上述问题，本文提出两个优化算法：①匿名区域随机偏移切换算法：对所产生的匿名区域进行偏移，具体偏移幅度由当时周围用户点的分布情况决定，具有随机性，能较好抵御中心点攻击；②匿名区域零交集偏移切换算法：匿名区域随机偏移切换算法面对等比缩放攻击，若缩放计算后、切换前的匿名区域存在交集，则用户真实位置可能会泄露。针对此情况，对偏移量作进一步限制，确保攻击者猜测的切换前匿名区域与实际的切换前匿名区域无交集，进而有效抵抗等比缩放攻击。

2 普通匿名区域生成算法的抗攻击分析

2.1 中心点攻击

中心点攻击步骤：有用户提交查询请求时，记录隐私度k和相应的匿名区域CK1，当用户切换隐私度为k′(k′>k)的匿名区域CK2时，分别计算隐私度切换前匿名区域CK1的中心点O1、切换后匿名区域CK2的中心点O2，判断切换前后的中心点O1、O2位置是否一致，不一致就放弃攻击。如果中心点O1、O2位置一致，则认为匿名区域来自同一个用户请求，缩小切换后的匿名区域CK2到切换前的大小，输出切换前的匿名区域CK1，用户的隐私度切换失败。

2.2 等比缩放攻击

等比缩放攻击步骤：在服务器上开始恶意观察，对切换后的匿名区域，保持中心点不变依据切换前后隐私度k的比例进行等比缩放，将缩放后的匿名区域作为切换前的匿名区域对待。

2.3 线性偏移攻击

攻击者在服务器上获取用户发来的匿名区域，记录该匿名区域信息，并计算匿名区域的中心点，根据一段时间的观察，可以计算出匿名区域中心点切换前后的线性关系参数值，破解中心点线性偏移函数y=ax+c。若切换前后匿名区域中心点满足该线性函数，则可以判定请求来自同一用户，用户向更高隐私度匿名区域的切换失败。线性偏移攻击，在攻击初期需要对用户匿名区域中心点偏移规律的线性函数进行推断，这阶段属于用户安全期，不会被攻击，所以对于请求总次数少的用户，不用担心被攻击。

2.4 普通匿名区域生成算法的安全性

普通匿名区域生成算法的核心思想是，按匿名区域切换前后的隐私度k的比值，等比例扩大原匿名区域大小，切换前后的匿名区域中心点不变。从上述的攻击模型描述来看，普通匿名区域生成算法对中心点攻击和等比缩放攻击的防范性很差，攻击者可通过切换后的匿名区域，得到切换前的匿名区域。而如果我们对切换后的匿名区域中心点按偏移函数y=ax+c进行线性偏移，攻击者也很可能通过一段时间的观察，获得线性偏移函数的表达式。因此,普通匿名区域生成算法对于中心点攻击、线性偏移攻击、等比缩放攻击，防御性都很弱[11]。

3 普通匿名区域生成算法的改进

普通匿名区域生成算法简单，运行效率高，但是因为其不能很好抵御攻击，在有一定隐私安全要求的场景不适于使用，本文根据常见的三种攻击，对普通匿名区域生成算法进行改进，提出两种更具有抗攻击的改进算法：匿名区域偏移切换算法、匿名区域零交集偏移切换算法。

3.1 匿名区域偏移切换算法

匿名区域偏移切换算法是对普通匿名区域生成算法进行改进，普通匿名区域生成算法对攻击防御能力较差，特别是从低隐私度切换到高隐私度时，位置隐私很容易被攻击者获取。匿名区域偏移切换算法对普通匿名区域生成算法改进，对生成的匿名区域进行动态偏移，以提高抵御攻击的能力。该算法的思路是对切换后的匿名区域根据用户分布情况进行一定的偏移。匿名区域偏移切换算法以切换前隐私区域的中心点(矩形区域对角线的交点)为圆心，以用户提供的参数r为半径画圆，形成一个包含原匿名区域的更大的圆形匿名区域，由匿名区域圆中的用户点，重新构建新的矩形匿名区域。

匿名区域偏移切换算法的详细步骤：

(1)接收用户参数半径r，步长扩展a，初始化切换前匿名区域用户集合U1。

(2)对切换前矩形匿名区域CK1确定中心点，并以中心点为圆心，半径r画圆。

(3)添加位于圆内且匿名区域外的用户，扩充U1建立新用户集U2。

(4)将U2中的所有用户点映射到x、y坐标轴，获取映射于坐标轴上的极值xmin、xmax、ymin、ymax。

(5)将U2中的所有用户点映射到x、y坐标轴，以(xmin，ymin)、(xmin，ymax)、(xmax，ymax)、(xmax，ymin)为四个顶点，构建切换后的矩形匿名区域CK2。

(6)若CK2中用户数N大于或等于切换后隐私度k，且CK2的面积S(CK2)小于或等于用户可接受的最大隐私区域大小(Smax)，则算法结束，跳到(10)。

(7)若用户数N小于切换后隐私度k，且S(CK2)

(8)若N>=k，S(CK2)>Smax，则等比缩小匿名区域CK2至Smax，即S(CK2)=Smax，重新计算用户数并返回(6) 步骤。

(9)若用户数N

(10)返回匿名区域CK2，算法结束。

匿名区域偏移切换算法算法简单，开销小，容易实现且响应时间快，算法最终生成的匿名区域CK2，与原匿名区域周围的用户点分布有关，因此匿名区域偏移量是个随机数，无规律可循，攻击者无法通过获取的数据，推算出矩形中心点线性位移函数，所以匿名区域偏移切换算法能较好应对中心点攻击、线性偏移攻击。匿名区域偏移切换算法得出与普通匿名区域法生成的匿名区域相比，位置偏移不大，在保证服务质量的同时，隐私度有较大的提升[12]。

3.2 匿名区域零交集偏移切换算法

匿名区域零交集偏移切换算法的核心思想是对匿名区域偏移切换算法进行改进，对匿名区域的偏移量进行限制，使切换前、后的匿名区域无交集部分，有效防止等比缩放攻击。

匿名区域零交集偏移切换算法具体过程如下：

(1)对原匿名区域CK1四条边按东西南北顺时针方向编号[1～4]，根据随机函数产生的值[1～4]，决定构造匿名区域CK1的边L；

(2)取边L的中点O，以O为圆心，r为半径画圆；

(3)获取以边长L(包括延长线)为中线，位于匿名区域另一侧的半圆区域S′；

(4)建立空用户集U，将半圆区域S′内用户逐一添加到用户集U；

(5)将用户集U内所有的用户点，映射于坐标轴，得到用户点x坐标的极值xmin、xmax，y坐标的极值ymin、ymax；

(6)以(xmin，ymin)、(xmin，ymax)、(xmax，ymax)、(xmax，ymin)为四个顶点，建立切换后的匿名区域CK2；

(7)若CK2中用户数N大于或等于切换后隐私度k，且CK2的面积S(CK2)小于或等于用户可接受的最大隐私区域大小(Smax)，跳到(11)步骤；

(8)若用户数N小于切换后隐私度k，且S(CK2)

(9)若N>=k，S(CK2)>Smax，则等比缩小匿名区域CK2至Smax，即S(CK2)=Smax，重新计算用户数，返回(7) 步骤；

(10)若用户数N

(11)返回匿名区域CK2，算法结束。

匿名区域零交集偏移切换算法最后生成的切换后的匿名区域CK2产生方位具有随机性，所以能较好应对中心点攻击、线性偏移攻击，而匿名区域CK2与切换前的匿名区域CK1相邻且无交集，使得本算法相对匿名区域偏移切换算法，在抵御等比缩放攻击时具有明显优势。

4 实验和结果分析

实验环境: 处理器Intel(R) Core(TM )i3-4170 CPU @3.70GHz，内存8GB，Ubuntu 14.10，Python 2.7.12。

4.1 匿名区域切换耗时比较

当用户想要提高匿名区域隐私度K时，匿名区域相应就需要进行切换，匿名区域切换的耗时是衡量算法优劣的一个重要指标，体现了算法的效率，也直接影响到用户的体验，本实验耗时是指从接收到切换前后隐私度k参数开始，一直到切换后的匿名区域生成，整个过程消耗的时间，单位为微秒(μs)，即10-6秒。实验结果如表1所示。

表1 不同算法的匿名区域切换耗时比较Tab.1 Time comparison of anonymous regions switching for different algorithms

表1前两列表示匿名区域切换前后所对应的匿名隐私度k的值，从表1的数据中我们可以看到，普通匿名区域生成算法耗费时间明显小于匿名区域偏移切换算法和匿名区域零交集偏移切换算法，在匿名区域切换前隐私度k较小(k=1)的情况下，随着切换后隐私度k值的增加，所需的耗时有所增加，但并没有与k值成正比例地显著增加。同样当匿名区域切换前隐私度k较大(k=1000)的情况，只要切换前后k值变化不大，所需的耗时也是很小。

随着k值的增加，匿名区域偏移切换算法和匿名区域零交集偏移切换算法的耗时逐步缓慢增加，耗时在用户可接受的范围，能给用户提供较为满意的服务。从表1可以看出，三种算法耗时具体的数值变化主要取决于切换前后k值的变化量有关，而与匿名区域隐私度k的具体数值大小无关。

综上情况，在体现算法效率的耗时方面，普通匿名区域生成算法最优，然后依次是匿名区域偏移切换算法、匿名区域零交集偏移切换算法。其中普通匿名区域生成算法耗时明显优于其他两种算法，但三算法的耗时都在可接受范围，普通匿名区域生成算法适用于注重用户体验性且安全性要求不高的情况。

4.2 匿名区域切换成功率

匿名区域切换成功率是指匿名区域在不同隐私度k值间切换时，重新构建匿名区域的成功概率。匿名区域切换成功率能够体现算法切换的质量和抗攻击性的能力。

表2为中心点攻击下匿名区域切换成功率比较表，表3为等比缩放攻击下区域切换成功率比较，从两表可以看出，普通匿名区域生成算法的切换成功率最差，在两种攻击情况下，切换的成功率都接近零。这是因为普通匿名区域生成算法切换前后的匿名区域中心点是重合的，在中心点攻击和等比缩放攻击时，很容易被非法攻击者获得匿名区域信息，抗攻击性弱，不具有防御性。

匿名区域偏移切换算法在中心点攻击时，具有很高的切换成功率，都在95%以上，大部分数据接近100%，这是因为该算法对匿名区域的中心点进行了偏移，能有效地躲过了中心点的攻击，因为算法的偏移量具有随机性，很小概率的情况下，区域的切换前后中心点会重合。而在等比缩放攻击时，匿名区域偏移切换算法随着切换后匿名度k值增加，切换成功率也相应提高，但随着匿名度k值变大，切换前后k之间的差值较大，切换成功率开始下降。这是由于在用户均匀分布情况下，k差值达到一定阈值后，用户整体分布均匀，偏移量也相应变小。同样地，当匿名度k值比较大，且切换前后匿名度k差值很小时，偏移量其实很小，切换成功率也很不理想，接近于0%。等比缩放攻击是对切换后的隐私区域进行等比缩小，猜测切换前隐私区域的大小，匿名区域偏移切换算法虽然对于普通匿名区域生成算法进行改进，对中心点进行了偏移，但切换前后的隐私区域依然存在较多的重合部分，故容易被攻击，导致匿名区域的切换失败。

表2 中心点攻击下匿名区域切换成功率比较Tab.2 Comparison of success rate of anonymous areas conversion under center attack

表3 等比缩放攻击下区域切换成功率比较Tab.3 Comparison of the success rate of area conversion under equal scaling attacks

相比匿名区域偏移切换算法，匿名区域零交集偏移切换算法在中心点攻击和等比缩放攻击都有很好的表现，从两表的测试数据来看，切换成功率都达到了100%。这是由于匿名区域零交集偏移切换算法相比匿名区域偏移切换算法，加大了切换后匿名区域的偏移量，切换前后的隐私区域无交集，切换前后的匿名区域中心点更不可能重合，所以抗攻击性表现最好，匿名区域的切换成功率也最好。

4.3 用户体验满意度

用户体验满意度指用户对经过匿名区域切换后获取的最终服务结果的满意程度，也是衡量隐私匿名区域算法的一项重要参考指标。令匿名区域切换后所得到的服务器返回的服务点P1，实际最佳服务点P2，用户所在位置为U，则用户体验满意度MU可以通过用户与P1、P2两点的距离比值来体现，记作：MU=(|P1U|/|P2U|)×100%，用户体验满意度MU越接近1表示服务质量越高，相应用户体验满意度最佳。趋近于0时，代表用户满意度最差。

表4 各算法的用户体验满意度比较Tab.4 Comparison of user experience satisfaction of different algorithms

3种匿名区域生成算法实现的用户体验满意度如表4所示。普通匿名区域生成算法仅仅对切换前匿名区域按比例扩大，算法复杂度小，获取服务结果实时性强，最终用户获得的服务质量下降少，用户满意度高。匿名区域偏移切换算法对切换前匿名区域进行位移，但是位移量比较小，用户的服务质量受到的影响不大，能达到用户的满意度。匿名区域零交集偏移切换算法将切换后匿名区域移到切换前匿名区域的外部，偏移量的大小取决于切换前匿名区域的面积大小。切换前匿名区域面积越大，意味着偏移量将越大，算法运行时间也较长，用户获取服务结果的满意度也就越低。从表4中可以看到，当切换前k=1000时，算法的用户体验满意度下降明显，只有60%左右。

综上可以看出，普通匿名区域生成算法和匿名区域偏移切换算法，能都获得较好的用户体验满意度，匿名区域零交集偏移切换算法用户体验满意度相对比较低，特别是切换前匿名区域的隐私度k很大时，用户体验比较差。

5 结语

随着基于位置的服务应用的不断发展，个人隐私问题日益受到人们重视。在对当前位置隐私保护技术进行较全面了解的基础上，通过对普通匿名区域生成算法的分析和改进，首先提出了匿名区域偏移切换算法，该算法既保留了原算法开销小的优点，同时增强了抵御中心点攻击和线性偏移攻击的能力。接着，为了抵御等比缩放攻击，在匿名区域偏移切换算法基础上，进一步提出了匿名区域零交集偏移切换算法。两种新算法各有优劣，可适用于不同的应用场景。