基于位置社交网络的高效定位算法

王荣荣， 薛旻辉， 李祥学， 钱海峰

（华东师范大学计算机科学技术系，上海　200241）

基于位置社交网络的高效定位算法

王荣荣， 薛旻辉， 李祥学， 钱海峰

（华东师范大学计算机科学技术系，上海200241）

基于位置社交网络（Location-Based Social Network，LBSN）服务使得用户能够利用位置服务发现附近的人.原始的LBSN服务为用户提供确切的相对距离，而这种做法已被证实易于遭受三角定位攻击.为防御此类攻击，当今LBSN服务普遍采用以带宽的方式来报告距离.本文利用数论，通过技巧性地摆放虚拟探针，伪装地理位置，提出了一种不受地理位置限制、高精度、易于实现的定位目标算法.作为概念验证，本文使用微信进行实验最终验证了该攻击算法在实际部署中的有效性.本文的研究旨在呼吁LBSN服务提供商改进位置隐私保护技术，唤醒公众充分认识LBSN软件所带来的潜在隐私泄露.

基于位置社交网络； 定位攻击； 微信

0　引　言

随着智能手机和平板电脑的飞速发展以及随处可用的网络服务惠及大众，移动社交网络以前所未有的速度蓬勃壮大，用户能够通过移动设备，使用在线社交网络与其他用户进行互动.不仅如此，定位服务如全球定位系统（Global Positioning System，GPS）和移动设备的无线定位技术使得用户可以随时定位并且实时分享自己所处位置.从而，也促使利用基于位置的社交网络（Location-Based Social Network，LBSN）服务的用户数量突飞猛涨，如微信、陌陌、交友乐园、谷歌+、Badoo等都已有庞大的用户群.微信作为中国最受欢迎的一款LBSN软件，月活跃用户已达3亿多.另一款同样广受欢迎的LBSN软件陌陌，在不到3年的时间注册用户数已达1.5亿［1-2］.各类不同的LBSN应用软件被用来出售商品、认识附近的人或仅仅用来与其他用户聊天.

在LBSN广受欢迎的同时，用户隐私遭受泄露和攻击的机会也大大增加.通过对用户位置信息的收集，统计位置信息出现的频率，可实现用户的身份识别［3］.通过收集用户空间信息，文献［4］可实现高精确度的用户信息匹配.而与他人分享自己的位置信息，则会遭受移动轨迹泄露而对自身安全造成威胁［5］.即使是为保护用户隐私的匿名社交网络，在给予昵称与相对距离的情况下，仍会遭受定位攻击而导致隐私泄露［6］.文献［7］通过空间分割算法，可对微信用户进行定位.这些研究都说明了用户位置隐私的泄露问题.不仅如此，通过对用户的社交行为进行大数据分析也同样可得到用户的某些隐私［8］.意识到由LBSN的位置信息而引出的一系列隐私泄露问题，许多研究致力于位置隐私的保护.其中多数着重设计位置服务的隐私保护机制［9-10］，让用户在使用位置服务的同时限制敏感信息的泄露，例如基于用户感知的时钟轮换技术使用户轨迹难以预测［11］、权限管理技术限制敏感信息被获取［12］、位置隐私监视框架保护隐私泄露［13］、私人友邻检测技术防范位置隐私泄露［14］等等.尽管有各种保护措施，用户的隐私信息仍面临被泄露的潜在威胁.

为保护用户隐私，LBSN软件的通常做法是报告附近用户的距离，而非确切的经纬度坐标.第一代的LBSN软件，采用报告确切距离的做法；而这类做法使得LBSN用户容易遭受三角定位攻击.为进一步提高用户的位置隐私，现在一些广受欢迎的LBSN应用包括微信、陌陌等采用带宽的方式来报告位置，将位置限制在一定的环状区域中.该位置模糊处理技术，旨在使用户得以利用位置服务的同时保护位置隐私.然而，该技术仍无法切实保护用户的位置隐私，同时使得用户轻信自己的位置隐私得到保护从而降低防范意识.

本文采用一种通用的方法证明，即使是一个普通用户，也可以通过LBSN的位置服务定位任意地理位置的LBSN用户，甚至监视使用该位置服务的用户.并且，该攻击方法并不受带宽长度的限制，即使以10 km为带宽，也可以通过不断地迭代轮换来精确定位LBSN用户.要强调的是，只有使用位置服务的用户才能被定位和监测；如果一个用户只使用微信来与朋友发消息和照片，而从不使用“附近的人”功能，那么该用户是无法被本文所使用的方法定位的.

本文定量分析了对LBSN软件限制在一维直线上的攻击.我们利用数论证明了，在满足一些条件时，目标用户可以被定位在1 m的范围内；并且利用虚拟GPS软件进行实际的实验操作，可将用户定位在平均误差为33.72 m的范围内.我们用理论与实验表明，基于带宽的LBSN服务不能保护用户的隐私，并希望用户和LBSN服务提供商都能提高警觉，确保自己的隐私得到保护.

本文的内容组织：第1节介绍背景知识；第2节介绍预备知识；第3节介绍攻击算法；第4节评估实验和提出防御策略；第5节总结全文.

1　背景知识

1.1LBSN软件和三角定位

LBSN软件使用户可以在软件上寻找附近用户.以用户数占优的微信为例，它提供“附近的人”功能服务，在用户使用该功能的时候，用户的地理位置信息被读取，并返回给用户一个包含附近用户的用户名和距离的列表，从而建立点对多点的连接.采用报告具体距离的LBSN应用软件容易遭受三角定位的攻击.图1所示为一个三角定位的例子.在欧几里得几何中，三角定位就是一个通过画几何圆来获取点与点之间的相对距离的过程.进行此类攻击，只需知道3个测试点的辐射半径，根据三圆交汇原理确定目标所在的位置.

图1　三角定位攻击Fig.1　Trilateration attack

只要用户使用位置服务，LBSN应用就可读取用户的位置信息.而如果一个用户从不使用位置服务，那么他的位置信息则不受攻击的威胁.然而，Chen等人的研究表明仅有6%的用户完全隐藏自己的位置信息［4］.

为防御三角定位攻击，当今的LBSN软件如微信、陌陌、交友乐园等采用模糊位置信息的方式，提供给用户以带宽为基础的位置信息而非确切的位置信息.例如，微信的位置信息以100 m为带宽.当一个微信用户显示距离600 m的时候，说明该微信用户在距离以当前用户为圆心的500 m到600 m的环状区域内.于是，我们可假设一个LBSN软件提供的相对距离以K为带宽（例如在微信中，K=100 m），那么报告距离wd和实际距离d的关系则可用

来表示.

1.2攻击模型

使用带宽的距离报告模式使得简单的三角定位攻击不再起作用.本文介绍一种针对一维的LBSN用户的带宽距离报告模式的高精度定位攻击方法.在攻击模型中，一个敌手首先在任意远的区域内的一条直线上放置多个虚拟探针，这些探针可伪装成GPS骗过LBSN软件从而获取伪装位置附近人的列表.每个虚拟探针收集附近的LBSN用户与对应探针的相对距离.探针的位置摆放可任意，我们不妨假定直线上相邻两个探针的距离相等.我们利用数论证明指出，通过人为摆放特定的位置方案获取虚拟位置信息可高精度地定位目标.

简洁起见，我们将问题描述为：

（1）一条直线被等距离的探针分割为线段，每个探针距离为x；

（2）每个探针采用以K为带宽来报告目标的相对距离；

（3）x满足gcd（x，K）=1，且x，K∈Z，x，K≥1.

2　预备知识

下面，我们通过3个引理的证明来得到我们的理论基础.

引理1对a，b∈Z，存在s，t∈Z，使得as+bt=1当且仅当gcd（a，b）=1.

引理2对任意y∈Z满足1≤y≤K-1和任意正整数x使得gcd（x，K）=1，存在n∈Z且1≤n≤K-1，有

证明对任意正整数x满足gcd（x，K）=1，存在s，t∈Z使得

观察y·s·x+y·t·K=y，可知y·s·x≡y（mod K）.令n=y·s（mod K），则有n·x≡y（mod K）.

引理3对任意y∈Z满足1≤y≤K-1和任意正整数x使得gcd（x，K）=1，存在唯一的n∈Z满足1≤n≤K-1，使得

证明假设存在1≤n＜n'≤K-1，使得

得到

又gcd（x，K）=1，则可得K|（n'-n）.然而，由于1≤（n-n'）＜K，则K|（n'-n）不可能成立.因此可得n=n'.

从引理2和引理3可得fx（N）=N·x（mod K）是ZK上的置换.对于上述的s，注意fs（N）=N·s（mod K）是ZK上关于fx（N）的逆变换.而由等式（1）可得y·s·x+y·t·K=y，即有x·s≡1（mod K），从而可得fs（fx（N））=N·x·s≡N（mod K）.

3　攻击算法

本节介绍的算法，解决的是一维上的目标定位问题.表1所示的是本节将出现的符号及其含义.

表1　符号概述Tab.1　Summary of notations

考虑目标所在的直线上，如图2所示，沿同一直线放置若干个等距探针（我们理论上证明了，可以通过收集探针的距离报数将目标定位在1 m范围内）.

图2　一维直线图Fig.2　One-dimensional line

于是有

选取合适的x，并且由软件特性得到具体的K值，通过布排探针获取一系列的｛wpi｝作为输入.之后进行一定的迭代计算，得到第一个探针与目标的实际距离.该目标定位的具体过程如图3所示，算法过程由图4总结给出.

图3　定位目标Fig.3　Pinpoint the target user

图4所示算法的核心是

图4　算法1：迭代攻击算法Fig.4　Algorithm 1：Iterative attack algorithm

用等式（2）作为目标位置的测试方程是因为

证明算法1的第一步是找到T使得Δ（T）=1，且Δ（T+1）=0，也就意味着且于是则有

由此可知目标点T的位置几乎与探针pN的带宽边缘重叠，N=fs（T）+1.最终，算法返回

从不等式（3）可得

4　实验评估和防御策略

为评估第3节算法策略的有效性和精确性，我们从普通用户的身份出发，利用普通用户能够获得的条件和软件来设计实验方案.首先，我们考查了市场上的虚拟位置软件，包括定位伪装设置、虚拟GPS、伪装位置等十几款软件，最终选择一款伪装效果最好的名为伪装地理位置标准版的软件作为虚拟探针.再次，我们选择微信作为实验的LBSN软件.接着，考虑到微信是以100 m为带宽单位进行报告距离，并且超过1 km的目标则开始以km为单位进行报告，所以我们的攻击目标为1 000 m（1 km）范围内的微信用户.最后，综合考虑微信与虚拟探针软件操作特性，我们令x=10，即相邻两个探针之间的距离为10 m.通过实际距离与实验计算结果的比较，我们得到定位算法的实际误差范围以及误差的分布.

4.1微信实验

针对微信“附近的人”这一功能所提供的位置信息，已有的实验方法是采用逆向工程获取应用程序编程接口（Application Programming Interface，API）的位置［7］，然而这并不符合弱敌手这一特性.借鉴文献［16］采用虚拟GPS软件的做法，本文不通过攻击微信服务器获取信息，而是仅利用微信客户端能收集到的信息，然后通过我们的算法策略进行定位攻击.首先将一台安卓手机A（此处为小米2S手机）登陆微信账号Alice并打开“附近的人”功能，然后放置在地点O，使O地附近的微信账号能够查看到Alice.接着在另一台手机B的伪装地理位置软件地图中，选取一条O点所在直线，在1 km范围内等距地布若干探针，探针数取决于第一个探针距目标的实际距离.此外，布点的同时会产生该探针所在点的GPS（软件自动报出），从而可获得各探针与目标位置的实际距离.利用软件的探针轮换功能，依次在每个探针上使用“附近的人”功能，记录每次Alice出现的距离读数.每个探针重复查询100次，记录Alice的距离（若个别情况下未出现Alice，则继续查询，直到Alice在该探针上出现100次），取出现次数最多的读数作为该探针的报数.收集记录完每个探针报数并与实际距离进行对比，记为1次实验.本文共在100个不同的地点重复进行这样的实验.图5为某次实验第一个探针的报数统计，300出现的次数最多，则取300作为该探针的报数.图6为某次实验七个探针的报数统计，由该图可看出距目标400 m的点落在第六和第五个探针之间.

图5　某次实验第一个探针报数Fig.5　Reported distances of the first probe in one experiment

图6　某次实验所有探针报数Fig.6　Reported distances of all the probes in one experiment

4.2结果评估

实验得到的探测距离与实际距离的误差统计如图7所示.从图中可知，92%的定位攻击可达到60 m以内的精确度，29%的攻击可达20 m以内的精确度.此外，通过实验可得平均每次实验放置7个探针便可得到结果，最多11个探针便可得到结果.图8为累积概率分布图，从图可知最大误差在120 m以内，并且超过50%的实验误差在40 m以内.由此可知，我们的算法策略能够达到高精度的定位攻击.同时，也意味着LBSN用户的位置隐私未得到有效的保护.

图7　定位精确度评估Fig.7　Evaluation on localization accuracy

图8　定位精确度累积概率分布图Fig.8　C.D.F.of localization accuracy

4.3结果比较

文献［7］使用逆向工程的方法，开发了一套复杂的系统工具，即在已知用户ID（IDentity，ID）（身份标识码）的情况下，通过微信“附近的人”功能收集位置信息，使用空间分割算法来定位用户.该方法需要攻击者精通应用软件内部实现方式，并要求已知用户ID，而非针对任意用户.

文献［16］则使用现有的应用软件，通过自动化图形界面工具在一段持续的时间范围对特定区域进行检测查询，并采用“类三角定位”方法，从不同监测点对同一目标的覆盖区域重叠部分推测出用户位置.该方法的优点在于完全借助于现有软件，符合弱敌手特性，可大量收集用户数据，但缺点在于时间成本太大.本文所采用的方法无需知晓用户ID，只要用户活动在探针检测范围（探针可以任意设定位置）内，即可通过本文方法定位.本文所采用实验方法需用到实际手机触屏操作，可在短时间内对用户进行定位，但无法同时定位大量用户，后续工作可借鉴文献［7］所采用的图形自动化工具与手机模拟器结合的方式进行大规模实验.

表2所示为本文所述方法与几种针对微信的定位方法的结果比较.从表2可知，虽然本文所论述算法在维度上不如类三角定位和空间分割算法，但实验精确度明显比后两者高，并利用数论给出了误差理论值上界.

表2　方法比较Tab.2　Methodology comparison

4.4防御策略

为应对最原始的三角攻击策略，LBSN服务提供商引入了带宽定位这种方案.然而，这类统计型的攻击不能仅仅依靠增加噪声来进行抵制.理论上即使将带宽增加到10 km，也可以利用我们的算法来进行高精度定位.由大数定律，攻击者总是可以通过增加数据量和利用数据挖掘工具来消除噪声，从而进行定位攻击.抵制这类攻击，关键在于限制用户的查询次数，亦即在时间和数量上限制用户使用“附近的人”功能.下面给出几种可有效保护位置隐私的措施.

（1）限制次数.限制同一手机在一个时间段内最多只能查看附近的人列表的次数.通过这种做法，可以有效地解决用户位置信息持续暴露问题.

（2）提高对虚拟GPS的检测技术.提高检测虚拟GPS的技术来检测位置是否真实可靠，判断该请求用户的行为模式是否现实，从而决定是否对该位置的请求给予应答.

（3）移除距离.最彻底的措施是移除距离的显示，仅列出用户列表和所在区域例如上海市闵行区，但这种做法显然是以降低用户体验为代价.

5　结　论

近年来LBSN成为最受欢迎的社交应用.然而，多数用户并未意识到位置隐私的泄露问题.我们提出了一种不受地理位置限制、高精度、易于实现的定位算法，并以微信为例进行实验表明，即使是一个普通的LBSN用户也可以仅通过客户端的公开信息而无需攻破服务器、无需使用任何API就可对某区域范围的用户进行高精确度的定位.需要强调的是，只有使用位置服务的用户才能被定位和监测.如果一个用户只使用微信与朋友发消息和照片，而从不使用“附近的人”功能，那么使用本文的方法该用户是无法被发现的.

据我们所知，这是第一次利用数论来定量研究LBSN软件，目标用户可以被定位在1 m的范围内，未来的工作会注重在高维情况下的定量和定性分析.我们的理论与实验表明，基于带宽的LBSN服务不能保护用户的隐私.本研究旨在呼吁LBSN服务提供商改进位置隐私保护技术，更重要的是，唤醒公众充分认识LBSN软件所带来的潜在隐私泄露.本文的建议对未来LBSN软件的改进有一定的指导意义.

［1］CIW TEAM.Tencent：438M Wechat users and 645M QZone users by Q2 2014［EB/OL］.China Internet Watch，2014［2015-1-25］.http：∥www.chinainternetwatch.com/8229/tencent-q2-2014/.

［2］XIANG T.Momo：China's next social conglomerate？［EB/OL］.TechNode，2014［2015-1-25］.http：∥technode.com/ 2014/10/13/momo-china-next-social-conglomerate/.

［3］ZANG H，BOLOT J.Anonymization of location data does not work：A large-scale measurement study［C］∥Proceedings of the 17th Annual International Conference on Mobile Computing and Networking.ACM，2011：145-156.

［4］CHEN T，KAAFAR M，BORELI R.The where and when of finding new friends：Analysis of a location-based social discovery network［C］∥Proceedings of the International AAAI Conference on Weblogs and Social Media.2013.

［5］XUE M，LIU Y，ROSS K W，et al.I know where you are：Thwarting privacy protection in location-based social discovery services［C］∥Proceedings of the 2015 IEEE Conference on Computer Communications Workshops（INFOCOM WKSHPS）.IEEE，2015：179-184.

［6］WANG G，WANG B，WANG T，et al.Whispers in the dark：Analysis of an anonymous social network［C］∥Proceedings of the 2014 Conference on Internet Measurement Conference.ACM，2014：137-150.

［7］LI M，ZHU H，GAO Z，et al.All your location are belong to us：Breaking mobile social networks for automated user loca-tion tracking［C］∥Proceedings of the 15th ACM International Symposium on Mobile ad Hoc Networking and Computing. ACM，2014：43-52.

［8］RUTHS D，PFEFFER J.Social media for large studies of behavior［J］.Science，2014，（6213）346：1063-1064.

［9］BINDSCHAEDLER L，JADLIWALA M，BILOGREVIC I，et al.Track me if you can：On the effectiveness of contextbased identifier changes in deployed mobile networks［C/OL］.NDSS，2012［2015-1-25］.http：∥www.internetsociety. org.

［10］SHOKRI R，THEODORAKOPOULOS G，BOUDEC J Y L，et al.Quantifying location privacy［J］.IEEE Symposium on Security and Privacy（SP），2011，42（12）：247-262.

［11］XU T，CAI Y.Feeling-based location privacy protection for location-based services［C］∥Proceedings of the 16th ACM conference on Computer and communications security.ACM，2009：348-357.

［12］ALMUHIMEDI H，SCHAUB F，SADEH N，et al.Your location has been shared 5 398 times！［C］∥Proceedings of the 33rd Annual ACM Conference on Factors in Computing System.ACM，2015：787-796.

［13］FAWAZ K，SHIN K G.Location privacy protection for smartphone users［C］∥Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security.ACM，2014：239-250.

［14］ED N，QUN L.Near-pri：Private，proximity based location sharing［C］∥Proceedings of the IEEE INFOCOM 2014-IEEE Conference on Computer Communications.IEEE，2014：43-52.

［15］SHOUP V.A Computational Introduction to Number Theory and Algebra［M］.London：Cambridge University Press，2009.

［16］DING Y，PEDDINTI S T，ROSS K W.Stalking Beijing from Timbuktu：A generic measurement approach for exploiting location-based social discovery［C］∥Proceedings of the 4th ACM Workshop on Security and Privacy in Smartphones and Mobile Devices.ACM，2014：75-80.

（责任编辑：李艺）

An effective localization attack in location-based social network

WANG Rong-rong， XUE Min-hui， LI Xiang-xue， QIAN Hai-feng
（Department of Computer Science and Technology，East China Normal University，Shanghai200241，China）

Location-based social network（LBSN）services enable users to discover nearby people. Original LBSN services provide the exact distances for nearby users.Existing studies have shown that it is easy to localize target users by using trilateration methodology.To defend against the trilateration attack，current LBSN services adopt the concentric band-based approach when reporting distances.In this paper，by using number theory，we analytically show that by strategically placing multiple virtual probes as fake GPS，one can accurately pinpoint user locations with either accurate or coarse bandbased distances.As a proof of this concept，WeChat is examplified to validate that our attack methodology is effective in a real-world deployment.Our study is expected to draw more public attention to this serious privacy issue and hopefully motivate better privacy-preserving LBSN designs.

location-based social network； localization attack； WeChat

TP393

A

10.3969/j.issn.1000-5641.2016.02.009

1000-5641（2016）02-0062-11

2015-02

国家自然科学基金（61172085）

王荣荣，女，硕士研究生，研究方向为信息安全.E-mail：ghghgh8032@126.com.

钱海峰，男，研究员，博士生导师，研究方向为密码学、信息安全. E-mail：hfqian@cs.ecnu.edu.cn.