本节书摘来自华章出版社《位置大数据隐私管理》一 书中的第2章，第2.5节，作者潘晓、霍 峥、孟小峰，更多章节内容可以访问云栖社区“华章计算机”公众号查看。

2.5 连续查询攻击

2.5.1 攻击模型

连续查询是移动数据管理中非常重要的一种查询类型。Chow等人在2007年第一次提出连续查询攻击[40]问题。如果直接将为静态位置设计的位置匿名算法应用于连续查询，将产生连续查询攻击。具体来说，连续查询在查询有效期内位置是动态变化的。所以用户在查询有效期内不同时刻形成的匿名集不同，且匿名集中包含的用户不同。因此，通过将查询有效期内匿名集中用户集合取交，可唯一确定提出连续查询的用户身份，即用户隐私泄露。
用一个例子具体说明连续查询隐私攻击场景。如图2-19所示，系统中存在A、B、C、D、E、F 6个用户，分别提出查询QA、QB、QC、QD、QE、QF。攻击者事先知道6个用户中存在连续查询，但并不知道连续查询是什么，以及由谁提出。在3个不同时刻ti、ti+1、ti+2，用户A分别形成了3个不同的匿名集，即{A, B, D}、{A, B, F}、{A, C, E}，如图2-19中实线矩形框所示。将3个匿名集取交，即可获知是用户A提出的连续查询以及相应的查询QA。

文献[42]对连续查询攻击进行了形式化定义。
会话资料（Session Profile）：设用户在t1，t2，…，tn时刻的匿名区域分别为R1，R2，…，Rn，S1，S2，…，Sn是用户U在不同时刻形成的匿名集对应的查询内容集合。用户U的会话资料定义为
，会话资料中的每一个元素是一个三元组(t, R, S)。
表2-2显示的是与图2-19对应的会话资料。表中第三列表示匿名区域R的空间范围，分别表示匿名区域的左下角和右上角坐标。在t1时刻，匿名区域R1的空间位置是一个矩形，该矩形的左下角坐标为(3.5, 0.5)，右上角坐标为(6.5, 2.5)。t1时刻R1的匿名区域中包含3个查询内容即{QA, QB, QD}，即表2-2中的第1～3行。类似地，在时刻t2，R2对应的查询内容是{QA, QB, QF}，即表2-2中的第4至第6行；在时刻t3，R3对应的查询内容即{QA, QE, QC}，即表2-2中的第7～9行。

背景知识：攻击者的背景知识是由元组组成的集合，其中每一个元组以(t, x, y, u)的形式存在，表示用户u在时刻t的位置是(x, y)。
图2-20给出了一个关于用户A（Alice）和用户B（Bob）的背景知识示例。攻击者知道A在时刻t1、t2、t3所在位置的坐标分别是(5.1, 2.3)、(5.8, 3.6)、(5.9, 5.8)。

下面给出连续查询攻击的正式定义。
连续查询攻击：给定会话资料SP(U)和背景知识BK(U)，一个在用户u上的连续查询攻击即是一个映射f : BK(U)→SP(U)且满足：
1）针对每一个 ，在SP(U)中有唯一确定的 与b对应。
2）针对每一个 且f (b)=e，满足：
① (b.x, b.y)在e.R中，即攻击者知道的用户位置在发布的匿名区域R内。
② b.t=e.t，即背景知识与会话资料中的时间相互对应。
③ 对于所有 ，即用户u在所有有效期内，查询内容保持不变。
条件①和条件②表达了用户在给定时间内一定在匿名区域中；条件③要求用户在查询有效期内始终对应一种查询类型。继续前面的例子。根据图2-20显示的背景知识，以b=(t1, 5.1, 2.3, A)为例，对应表2-2的会话资料发现只有R1与其对应，满足定义2-17的条件1）；针对b=(t2, 5.8, 3.1, A), b=(t3, 5.9, 5.8, A)，其中b.u均为A，且对应的e.S均为QA，满足条件2）。所以图2-19所示的例子属于连续查询攻击。
观察发现，连续查询攻击的问题主要是由同一用户（A）在其有效生命期内形成的匿名集不同而造成的。所以解决此问题的最简单方法是让提出连续查询的用户在最初时刻形成的匿名集，在其查询有效期内均有效[40]。如在前面的例子中，用户A在时刻t1形成的匿名集是{A,B,D}，则在t2、t3时刻，匿名集依然是{A,B,D}，如图2-19中虚线矩形所示。虽然这种方式成功地保护了查询隐私，但是也将产生新的问题。第一，位置隐私泄露。如在图2-19b中，在ti+1时刻，A、B、D位置过于邻近，造成匿名框过小（极端情况下集中于一点），位置隐私泄露。第二，服务质量QoS降低。服务质量与数据精度成反比。在ti+2时刻，{A,B,D}分布在距离较远的位置，形成的匿名框过大，造成过高的查询处理代价。极端情况下，匿名集中所有用户背向而行，一段时间之后，匿名区将覆盖整个服务区域。由此可见，仅仅简单地把在最初时刻形成的匿名集作为连续查询有效期内的匿名集返回并不能解决问题。

2.5.2 m-不变性模型

满足m-不变性模型[42]的匿名算法可以防止连续查询攻击。在给出m-不变性模型的具体定义前，先来看一下文献[42]定义的信息披露风险。
信息披露风险：给定一个会话资料SP(U), QAA(U)是在用户U上所有可能的连续查询攻击集合。设QAAb(U)是QAA(U)的子集，可以唯一标识用户真实服务属性的连续查询攻击集合的子集，即给定 。用户U的信息披露风险即在用户U上反映真实敏感属性的连续查询攻击在所有连续查询集合中的比值，即 。
设另一个会话资料如图2-21所示，攻击者的背景知识依然如图2-20所示。图2-22展示了与图2-20和图2-21所列会话资料和背景知识对应的所有连续查询攻击的可能性。对比图2-22和图2-21的内容，Alice和Bob对应的敏感属性只可能是a、b两种。图2-21枚举了Alice和Bob对a和b的所有对应情况。因此，|QAA(U)|=4。用户Alice的真实敏感属性是a，能反映该敏感属性的查询关联性攻击的是第一个和第二个。所以|QAAb(U)|=2，Alice的披露风险是0.5(2/4)。

位置k-匿名模型保证匿名区域中至少有k个用户。然而，在不同的匿名区域中，无法保证每一个匿名区域包含的都是相同的k个用户。查询l-差异性保证在一个匿名集中至少包含l个不同的敏感属性值，但却没有要求维护这l个不同值要在不同匿名集中保持不变。基于这样的想法，Rinku Dewri等人提出了查询m-不变性。
查询m-不变性：设R1，…，Rn是用户U分别在时刻t1，t2，…，tn的匿名区域，当i>j时，ti>tj。如果 ，其中
，Users(R, t)表示在时刻t在匿名区域R中的用户集合，则称该匿名区域Rj满足查询m-不变性。
查询m-不变性蕴含了位置m-匿名和查询m-差异性。文献[42]中证明了满足m-不变性的匿名集合的泄露风险最多为1/m。一个用户如果可以与多个服务属性值关联，则该用户对应的可能的查询关联攻击的个数会增加。该规则要求在所有时刻的匿名集中都包含多个服务属性值，且该值的个数不能小于m。在图2-23所示的例子中，a和b两个值在所有匿名区域中保持不变，其揭露风险是1/2。