动态社交网络中的数据发布隐私保护技术

金凌竹，韩启龙

(哈尔滨工程大学 计算机科学技术学院，哈尔滨 150001)

0 引 言

随着网络的快速发展，国内外的社交网络应用层出不穷，如Facebook、微博等。这些应用在促进人们社交生活的同时，也在收集社交网络数据进行分析和挖掘。然而数据中含有大量的个人隐私信息，直接发布会造成用户隐私泄露。为了防止社交网络中个人信息、个体之间的隐私联系等信息暴露。在保证整个网络结构有用性的前提下，如何以最小的信息丢失代价实现信息隐藏已成为当前社交网络隐私保护研究领域一个重要课题。时空隐私信息可界定为用户不愿意被外部知晓的时空信息，将这些时空信息称为隐私兴趣点。在社交网络中，用户自行设置时空信息的访问权限，用户的隐私需求具有个性化、动态化的特点[1-2]。如一些用户将学校视为隐私兴趣点，认为可能泄露他的学校信息；但另一些用户却愿意在学校共享自己的位置，以便于与校友互动交流。

由此，引入可信度来形式化地描述用户的隐私需求，度量隐私泄露的风险程度，提出一种动态的时空隐私保护框架，将时空信息、社交关系、个人信息引入到知识构建算法中以计算兴趣点之间的相关性，并利用该相关性及时空信息实时判断发布当前位置是否满足用户的隐私需求，实现隐私保护与服务质量间的平衡。

1 动态社交网络隐私保护

1.1 动态社交网络中的隐私信息

在移动互联网时代，动态社交网络中的用户可以使用移动设备快速、连续地收集数据，例如个人签到数据、个人轨迹数据等。同时，网络中的数据收集者需要得到所有用户数据的汇聚结果，但是数据收集者并不是完全可信的，数据收集者会根据自身所掌握的信息，来推测其他用户的隐私数据[3]。对这些数据进行隐私保护的汇聚，可以在保护用户个人数据隐私的前提下，实现数据的有效利用[4]。动态社交网络的隐私主要分为用户隐私，位置隐私，轨迹隐私，社交关系隐私。

1.2 动态社交网络图

动态社交网络根据时间划分为一个个快照，以有向图G=(V,E,R)来表示，V为点类型的集合，代表所有用户数目的集合，V中的每个用户均由其特有的标识vi表示。根据用户对消息的隐私设置策略，将所有的节点归纳为3种类型：①Vpub，公共节点类型，代表对消息采用无隐私保护设置策略的这类用户，社交网络中所有用户都能够获取到此类用户发布在社交网络中的消息。Vpub的所有消息都是没有隐私保护的;②Vpri，私有节点类型，代表对消息采用部分隐私保护设置策略的这类用户，社交网络中的特定的用户都能够获取到此类用户发布在社交网络中的消息。Vpri的所有消息都是半隐私保护的;③Vn，独立节点类型，代表对消息采用严格的隐私保护设置策略的这类用户，社交网络中的其他用户均无法获取到此类用户发布在社交网络中的消息。Vn的所有消息都是严格隐私保护的。

R为社交网络中用户关系类型的集合。按照相互获取消息能力的权限，R能够归纳成5种类型：①Rnbr，双向邻居关系类型，代表此类型的用户能够相互的获取对方的消息;②Ro-nbr，单向邻居关系类型，代表此类型的用户能够单向的获取信息。例如，用户A关注了用户B，但是用户B没有回关用户A，那么用户A可以收到A的动态而B不会在首页刷到，但是如果用户B从粉丝列表访问，可以看到A的主页信息。说明用户形成了邻居关系，但是获取信息是单向的;③Rn-nbr，无邻居关系类型，代表此类型的用户无法获取其他用户的消息。用户可能没有关注任何人，也没有粉丝关注，账号可能为初级注册账号或者是不想被他人发现的小号;④Rs-nbr,陌生邻居关系类型，代表此类型的用户能够单向的访问信息。例如：用户A在广场搜索信息相关访问用户B主页，用户A为陌生人访问，因为用户B为开放的公共节点类型;⑤Rb-nbr，屏蔽邻居关系类型，代表此类型的用户因被屏蔽无法访问邻居节点信息[5-7]。

用不同的有向带箭头线段表示见图1。关系表示：如果用户之间为关注或被关注的关系，均用实线箭头连接，箭头方向指向关注的对象。行为表示：如果用户访问另一个用户信息，则用点短线箭头连接，箭头方向指向被访问的对象；如果用户对另一个用户进行屏蔽，则用虚线箭头连接，箭头方向指向被屏蔽的对象。由图1可见，分别为t1,t2,t3时刻的社交网络图，可通过观察动态社交网络图变化来分析隐私泄漏问题。

图1 动态社交网络图变化

通过观察动态社交网络图变化，发现在社交网络中，用户节点的度数是非常重要的信息，如v3,因为与其他多个用户节点存在连接、度数高，其本身存在隐私泄露的风险也高，并且通过攻击其节点和边信息，也会造成其他节点的信息泄露[8]。

Vn集合中的每个节点和其他节点的关系类型一定是半邻居关系类型或者无邻居关系类型，即此集合中的节点只有出度关系,见图2。在Vpub集合中的每个节点和其他节点的关系类型一般是邻居关系类型，即此集合中的节点同时拥有入度与出度关系；而在Vpri集合中的每个节点与其他节点可能的关系包括互相邻居关系类型、单向邻居关系类型或者无邻居关系类型中的一种或者多种[9-10]。因此，可得：①在Vn集合中的每个节点与Vn集合中的其他节点的关系类型一定是无邻居关系，与Vpub集合和Vpri集合中节点的关系类型可能是是单向或双向邻居关系类型。②在Vpub集合中的每个节点与Vpub集合中其他节点的关系类型都是邻居关系类型，与Vpri集合中的节点可能具有邻居关系类型。③Vpri集合中的节点与Vpub集合中的节点或者Vpri集合中的其他节点可能具有双向邻居关系或者单向邻居关系，并能够从具有此类关系的节点中获取到信息。此外，此类节点允许与其具有双向邻居关系或者单向邻居关系的节点获取此节点的信息。

图2 基于隐私设置策略的动态社交网络架构

通过对节点之间的边进行量化，定义双向邻居权重为2，单向邻居关系权重为1。发生屏蔽行为权重-1，发生访问行为权重+1。t1时刻社交网络中用户关系的量化结果见表1。根据不同时刻观察边的数值变化，可以发现用户之间的关系变化及行为。同时，在隐私保护中还需要判断动态社交网络图中边的变化导致相应节点度数变化，对其进行相应的保护。

1.3 RCACM 模型

为了兼顾动态中涉及的利益相关者的时空隐私，防止不可信用户攻击，使用一种基于可信度的合作访问控制模型(Reliability-based Cooperative Access Control Model，RCACM)，见图3。

图3 RCACM模型

基本元素定义为

U={u1,u2,…,un}表示内容中涉及的用户集合，通常包括一个数据发布者和多个信息相关者。

Ru={R1,R2,…,Rn}表示用户关系分组集合，例如，Ra={Rb-nbr，Ro-nbr}。

Su={s1,s2,…,sn}表示用户设置的隐私控制策略集合。

定义1 TCACM策略: 隐私策略为一个二元组S=〈F，D〉，其中F表示用户关系中授权访问的好友组集合，D表示该组中用户拒绝访问的个别好友集合。例如，SAmy=〈Ro-nbr,{Bob}〉表示Amy授权Ro-nbr分组中好友可见，除了Bob。

定义2 决策向量:规定给定的隐私策略执行的操作有1(授权访问)和0(拒绝访问)。给定用户u∈U，分组集合Su，u的隐私策略Su=〈F，D〉，目标用户t，u对t的决策值表示为

(1)

定义3 可信度r：本模型通过隐私策略的严格程度来度量可信度，用户对该信息设置的访问控制策略越严格，隐私度越高，而隐私策略的严格程度往往与该目标用户所在分组以及与该目标用户的可信度有关。

根据动态社交网络图结构，考虑节点和边不同的隐私级别，对节点可信度和边可信度进行相应的设定。将节点可信度r分为3级，令r∈[0，3]，且r∈Z，其中，0: 陌生，1: 不信任，2: 半信任,3: 完全信任。若令δ为最大信任值，则此时δ=3。给定用户节点vi∈V，分组节点集合Rvi，u的隐私策略Su，用户u的节点隐私度表示为

(2)

其中，Ru(t)为分组的隐私策略严格度，也表示分组t能够访问内容的最小可信度

Ru(t)=minr∈Rvif(u,t)

(3)

其中，f(u,t)为基于用户u对目标用户t的可信度。当授权访问，该函数返回用户u对目标用户t的信任度，当拒绝访问，该函数返回最大信任度，因为Ru(t)计算最小平均值，f(u,t)表示为

(4)

1.4 动态社交网络图中时空属性

定义4 隐私兴趣点。兴趣点(POI, point of interest)是电子地图上某个地标，用以标示该地所代表的政府部门、商业机构、旅游景点、交通设施等。利用兴趣点标示用户位置，将兴趣点记为Ii，兴趣点集合记为L；将需要隐私保护的兴趣点记为隐私兴趣点pi,这种兴趣点的集记为P，其中，P⊆L见图4。

图4 动态社交网络拓扑

定义5 移动轨迹H。给定用户u，在动态社交网络图中表示为节点v，其在时刻t1和tn之间的移动轨迹可以表示为一个按时间排列的序列Hv={(I1,t1),(p2,t2),(I3,t3), …,(pi-1,ti-1),(Ii,t1),…,(In,tn)},(I1,t1)是序列Hv中的一个元素，表示用户u在时刻ti访问过兴趣点Ii，(pi-1,ti-1)表示用户u在时刻ti-1访问过隐私兴趣点pi-1。其中Pu={(p1,t1),(p2,t2),(p3,t3),…,(pi-1,ti-1),(p1,ti),…,(pn,tn)}为用户u访问过的隐私移动轨迹。

隐私兴趣点推理攻击模型见图5。Pu={(l1,t1),(pj,tj),(li+1,ti+1)}。设用户u在t时刻发布兴趣点li，在ti+1时刻发布兴趣点li+1。令λ=|ti+1-ti|。如果λ远大于从li移动到li+1所需的正常时间间隔，则攻击者可推理出用户在ti到ti+1间访问过其他兴趣点。当攻击者具有一定的背景知识时，如大部分用户遵循(li→sj→li+1)的移动规律，即使用户未发布隐私兴趣点pj，攻击者也可推理出用户u可能访问过pj。

图5 敏感兴趣点推理攻击模型

动态社交网络中用户的身份信息和时空信息相互关联，时空信息可沿着邻居关系在动态社交网络中传播，因此假设攻击者具有以下背景：①用户的移动轨迹H；轨迹由用户一段时间内多个签到信息构成；②动态社交网络中的其他信息F，F包括用户的社交关系、个人信息等。

攻击者可利用上述背景知识推理用户隐藏的敏感兴趣点SI,如果存在一个位置点Pi∈P，当攻击者推理出的用户已访问或将访问隐私兴趣点Pi的可信度R(Pi|F,H,λ)>γi时，用户的隐私被破坏。

在动态社交网络中，用户自行决定是否发布签到等时空信息，共享时空信息可获得更优质的服务，但面临隐私泄露带来的安全威胁，需要通过合理的计算来平衡服务的可用性与用户的隐私需求。

2 动态社交网络中时空信息隐私保护方案

动态社交网络中时空信息中兴趣点之间相关性的计算式为

(5)

其中，support(li,lj,li+1)为相关性的支持度计数，即依次包含兴趣点li、lj和li+1的移动轨迹数。由于移动轨迹H带有方向性，因此support(li,li+1)≠support(li+1,li)。

通过分析用户移动轨迹H得到用户对已访问兴趣点的隐式评价，进而发现与其具有相似兴趣的用户，并基于最近邻居计算用户对未访问时空兴趣点的评分，进而得出对于该用户(li,li+1→lj)相关性的可信度。

2.1 用户兴趣模型

设动态社交网络中存在两个集合：①用户的集合U，总数是m；②时空兴趣点的集合L，总数是n。现将这两个集合合并起来，排成一个m×n阶矩阵R，行向量是用户集合U，列向量是时空兴趣点集合L,矩阵中的元素数是m×n。给定用户uk，其兴趣向量可以表示为Ruk=<(l1,rk1),…,(li,rki),…,(ln,rkn)>，rki为兴趣点li的权重，即用户uk对兴趣点li的评分。

rki可以通过统计用户对兴趣点li的重复访问次数得出。受信息检索中加权技术TF-IDF的启发，本文将时空兴趣点li视为“单词”，将用户的移动轨迹Huk视为“文档”，rki的计算式为

(6)

其中，counti为用户访问兴趣点的次数;U为所有用户的集合。

矩阵R建立初期可能是一个稀疏矩阵。用户对未访问时空兴趣点的评分可由用户的最近邻居得出。用Jaccard系数计算用户社交关系之间的相似性，用余弦相似度计算用户时空兴趣的相似性。用户相似度sim(ui,uj)的计算式为

(7)

其中，Ni和Nj分别为ui和uj邻居的集合;α为常数，0<α<1。寻找最近邻的目标就是对每个用户u，在用户空间中查找用户集合U′={u1,u2,…,uk}，使得u∉U′，并且u1与u的相似性sim(u1,u)最高，u2与u的相似性sim(u2,u)次之，依此类推。令lj是用户uk未访问的时空兴趣点。rkj可由uk的近邻用户对时空兴趣点lj的评分得出，表示为

(8)

(9)

其中，support(li,lj,li+1)与式中的定义相同，β为常数，0<β<1。

2.2 动态社交网络时空隐私保护算法

动态社交网络时空隐私保护算法(Dynamic Social Networking Spatio-Temporal Privacy Algorithm，DSNS-TPA)。令li表示用户uk在时刻ti发布过的时空兴趣点，动态社交网络时空隐私保护算法首先计算两次信息发布请求时间间隔Δt=ti+1-ti，如果Δt

(10)

其中，P(pi|li,li+1)可由式(5)或式(9)得出。当Pi

3 实验结果与分析

实验中与流行的k-匿名算法[11]进行了对比，实验结果的评价主要有3个指标：成功率、加密数据可用率和数据处理时间,结果见图6。

图6 成功率、数据可用率及处理时间实验结果

成功率

(11)

式中:Pn为用户初始的时空隐私数据集合;{Pe|Pe=S-TGES(p),p∈Pn}为被成功加密保护的用户时空数据集合; S-TGES(p)为本文所提出的基于网格加密的时空数据隐私保护方法;|Pn|-|{Pe|Pe=S-TGES(p),p∈Pn}|为通过去加密化方法，成功再复现出用户的初始时空数据以及其他相关的数据。

数据可用率

(12)

4 结 论

本文通过对动态社交网络中数据发布隐私安全问题的研究分析，提出了动态图发布隐私保护方法，该方法不仅考虑了图结构信息，并加入了对于时空信息的隐私保护方法。实验结果表明，该方法能抵御多种背景知识攻击，同时对社交网络图结构动态变化具有较好的适应性。