移动轨迹去匿名化研究进展

论文标题：De-anonymization of Mobility Trajectories: Dissecting the Gaps between Theory and Practice

本文探讨了移动轨迹去匿名化理论方法在实际数据集应用中的差距，并提出了四种能很好的解决实际数据集各种问题的算法。

Indroduction

通常来说，移动轨迹的匿名化数据集由ISP厂商提供，然而去匿名化算法可能将用户隐私暴露出来，因此研究如何去匿名化以及新的匿名化方法是很重要的。早起的研究使用的数据是生成数据，其形式单一且不能和实际贴切，所以本文建立了一个新的数据集，其数据由真实的网络数据而来，并且体量巨大。

同时作者在真实数据集上使用7种经典的去匿名化算法进行攻击，发现这些算法在真实数据上并不work，其主要原因是1. ISP轨迹中有明显的时空不匹配2. GPS轨迹可能会有偏差，这些原因导致去匿名化工作富有挑战性。

所以，作者提出了四种新算法，空间匹配算法（SM），时间匹配算法（TM），基于高斯过程和马尔可夫的算法（GM）及其改进版本（GM-B）。这些算法对比以前算法，表现提高超过17%。

文章亮点：

数据集 2. 新算法 3. 首次尝试将理论和实践结合（大雾）

本节总结了以前去匿名化的七种算法并进行对比，并对以往的假数据和现在的真数据进行分析。

其中，去匿名化的种类有：位置轨迹信息去匿名化和网络行为信息去匿名化。

位置信息去匿名化：

算法有（对应下表）时间不匹配算法[28]，空间不匹配算法[23]，及其其他算法 [27],[32],[33] 。基于’encountering’事件的算法[8],[31], 但没有算法同时考虑时间和空间的不匹配。

网络行为信息去匿名化：

基于network dataset，其算法有[35],[20]等，这些算法需要用户的社交网络图作为额外信息。基于profile dataset，算法有[15],[16],[26]等。

Threat Model

本节着重讲解去匿名化算法攻击手段的及符号定义

对于攻击者拥有的信息。我们使用长度为T的vector $\boldsymbol{S}_{u}=\left(S_{u}(1), S_{u}(2), \ldots, S_{u}(T)\right)$ 去代替。代表时间$t$ (time shot)，用户$u$的位置信息。其中$S(t)=\emptyset$表示此时刻没有用户信息。并且用$\mathcal{S}=\left\{\boldsymbol{S}_{u} | u \in \boldsymbol{U}\right\}$代表所有用户信息。

攻击方法：

我们用score function $D$ 去量化攻击效果。对于用户u，攻击者需要从其掌握信息中寻找出该用户信息，因此$\boldsymbol{L}_{\sigma}(u)$越高越好。

具体来说，我们用$R(u,D)$来表示$\boldsymbol{L}_{\sigma}(u)$的排名，其中用$h$ 表示排名的指标。所以攻击方法的性能度量可以表示为：

$\Phi(\mathcal{S}, D)=\frac{1}{|\boldsymbol{U}|} \sum_{S_{u} \in \mathcal{S}} h(R(u, D))$

目标函数为：

$\arg \max _{D} \Phi(\mathcal{S}, D)$

具体来说， $h$ 函数可以用一个广泛使用的评估函数top-k来表示：

$h(x)=\left\{\begin{array}{ll}{\frac{k-(x-1)}{k},} & {\text { if } k \geq x \geq 1} \\ {0,} & {\text { if } x>k}\end{array}\right.$

经典算法表现

首先介绍数据集（省略的一节，论文中有数据的详细处理）

我们用$T_p$表示一个用户的一条由随机的时空-位置点组成的轨迹，我们将匹配的轨迹定义为用户的匿名设置，用$A(T_p)$表示，用$|A(T_p)|$来表征用户的唯一性。如果$|A(T_p)|=1$说明匿名数据其只有一条轨迹。我们对数据集进行分析，即可得出理论分析的privacy bound

现在我们对这七种算法进行分别介绍：

HMM

$D_{\mathrm{HMM}}=P\left(\boldsymbol{S}_{u} | T^{v}\right)=\sum_{\boldsymbol{Z}} \prod_{t \in \mathcal{T}} f(Z(t), S(t)) T_{Z(t-1), Z(t)}^{v}$

其中Z是隐含变量，表示用户真实位置。

HIST

使用$\Gamma{u}$来表示用户u的直方图统计，定义为$$\Gamma{u}=\frac{1}{|\mathcal{T}|} \sum{t \in \mathcal{T}} I\left(S{u}(t)=r\right)$$ 。

其相似函数定义为：

$D_{\mathrm{HIST}}=-D_{\mathrm{KL}}\left(\Gamma_{u} | \frac{\Gamma_{u}+\Gamma_{v}}{2}\right)-D_{\mathrm{KL}}\left(\Gamma_{v} | \frac{\Gamma_{u}+\Gamma_{v}}{2}\right)$

WYCI

$P\left(r | \boldsymbol{L}_{v}\right)=\frac{n_{r}^{v}+\alpha}{\sum_{r \in \mathcal{R}} n_{r}^{v}+\alpha|\mathcal{R}|}$ $D_{\mathrm{WYCI}}=\prod_{t \in \mathcal{T}, S(t) \neq \emptyset} P\left(S(t) | \boldsymbol{L}_{v}\right)$

ME

$D_{\mathrm{ME}}=\sum_{t \in \mathcal{T}} I(S(t)=L(t))$

POIS

$D_{\mathrm{POIS}}\left(\boldsymbol{S}_{u}, \boldsymbol{L}_{v}\right)=\sum_{t \in \mathcal{T}} \sum_{r \in \mathcal{R}} \phi_{r, t}\left(S_{u}(t), L_{v}(t)\right)$

NFLX

$D_{\mathrm{NFLX}}=\sum_{(r, t) : r=S_{u}(t)=L_{v}(t)} w_{r} * f_{r}\left(\boldsymbol{S}_{u}, \boldsymbol{L}_{v}\right)$ $w_{r}=1 / \operatorname{In}\left(\sum_{v, t} L_{v}(t)=r\right)$ $f_{r}\left(\boldsymbol{S}_{u}, \boldsymbol{L}_{v}\right)=e^{\frac{n_{r}^{v}}{n_{0}}}+e^{-\frac{1}{n_{r}^{v}} \sum_{t : S_{u}(t)=r} \min _{t^{\prime} : L_{v}\left(t^{\prime}\right)=r} \frac{\left|t-t^{\prime}\right|}{\tau_{0}}}$

MSQ

$D_{\mathrm{MSQ}}=-\sum_{t \in \mathcal{T}}|L(t)-S(t)|^{2}$

试验结果为：

原因分析:

时空不匹配

原因：GPS信号弱及其更新机制
数据稀疏

Our Method

高斯混合模型（GMM）模型可以有效解决时空不匹配问题，但对于数据稀疏问题，作者提出了两种方案：第一种是基于markov的移动模型，可以建立空缺时间点的分布，第二种是使用整个数据集对用户位置和行为信息进行聚合，以此推断丢失信息。

上图表示了隐含变量的关系，作者基于此假设建立得分函数：

$D_{\mathrm{GM}}(\boldsymbol{S}, \boldsymbol{L})=\log p(\boldsymbol{S} | \boldsymbol{L})$

下面对模型进行讲解：

GMM

GMM是有限高斯密度的线性叠加，可以表示为:

$p(x)=\sum_{k=1}^{K} \pi(k) \mathcal{N}\left(x | u_{k}, \Sigma_{k}\right)$

在模型中， $\mathcal{N}\left(x | u_{p}, \Sigma_{p}\right)$ 可以表示具有p个时间单位的时间不匹配的外部记录概率密度，因此对记录$S(t)$概率密度函数可表示为：

$p(S(t) | \boldsymbol{L})=\sum_{p=-H_{l}}^{H_{u}} \pi(p) \cdot \mathcal{N}\left(S(t) | L(t-p), \sigma^{2}(p) I_{2}\right)$

其中$\pi(p)$是p时刻时间不匹配的概率，而$\sigma(p)$是以p时间单位的时间不匹配为条件的空间不匹配的均方根。

我们使用EM算法去计算π和$\sigma$的值。第E步计算：

$\gamma\left(z_{n k}\right) :=P\left(z_{n k}=1\right)=\frac{\pi(k) \mathcal{N}\left(S_{n} | L_{n k}, \sigma^{2}(k) I_{2}\right)}{\sum_{j=-H_{l}}^{H_{u}} \pi(k) \mathcal{N}\left(S_{n} | L_{n j}, \sigma^{2}(j) I_{2}\right)}$

第M步计算：

$\left\{\begin{array}{l}{\pi(k)=\frac{1}{N} \sum_{n=1}^{N} \gamma\left(z_{n k}\right), \quad k=-H_{l}, \ldots, H_{u}} \\ {\sigma^{2}(k)=\frac{1}{2 N} \sum_{n=1}^{N} \gamma\left(z_{n k}\right)\left|S_{n}-L_{n k}\right|^{2}, \quad k=-H_{l}, \ldots, H_{u}}\end{array}\right.$

其中，$z{nk}$是表明被$L{nk}$生成的$S_n$的潜在变量(corresponding temporal mismatch is k time units)

Marcov Model

为了计算S(t)的PDF(概率密度函数)，建立模型：

$p(\boldsymbol{S} | \boldsymbol{L})=\sum_{L_{C} \in \mathcal{C}(L)} p\left(\boldsymbol{L}_{C} | \boldsymbol{L}\right) \prod_{S(t) \neq \emptyset} p\left(S(t) | \boldsymbol{L}_{C}\right)$

并分别建立了0阶和1阶的模型：

0-Order Markov Model

条件假设：每个时间点的位置信息相互独立

用E(r)表示用户的边缘分布(margin distribution )，可写为：

$E(r) :=p(L(t)=r)=\frac{\sum_{t \in \mathcal{T}} I(L(t)=r)+\alpha(r)}{\sum_{t \in \mathcal{T}} I(L(t) \neq \emptyset)+\sum_{r \in \mathcal{R}} \alpha(r)}$

其中

$\alpha(r)=\alpha_{0} \cdot \sum_{v \in \mathcal{V}} \sum_{t \in \mathcal{T}} I\left(L_{v}(T)=r\right)$

与位置r的记录数成比例，以α0为参数，调整位置上下文的影响

因此我们有：

$p\left(\boldsymbol{L}_{\boldsymbol{C}} | \boldsymbol{L}\right)=\prod_{t \in \mathcal{T}, L(t)=\emptyset} E\left(L_{C}(t)\right)$

1-Order Markov Model

条件假设：每个时间点的位置信息仅与上个时间点位置有关

因此我们可以构建转移矩阵：

其中：

Spatial Matching Algorithm (SM)

可表示为：

$D_{\mathrm{SM}}(\boldsymbol{S}, \boldsymbol{L})=\log \prod_{S(t) \neq \emptyset} \frac{1}{2 \pi \sigma^{2}} \exp \left(-\frac{(S(t)-L(t))^{2}}{2 \sigma^{2}}\right)$

Temporal Matching Algorithm (TM)