概率系统差分隐私研究综述

(北京大学 信息科学技术学院 高可信软件技术教育部重点实验室， 北京 100871)

当今社会，互联网技术正在日益深入人们的生活.随着网络和信息化产业的迅猛发展，数据以前所未有的速度不断地增长和累积，大数据已经成为学术界和产业界的热点，同时改变着人们的日常生活[1-3].在大数据背景下，不但数据体量相对于以往有了质的飞跃，而且人们对信息处理的速度，信息来源的多样性，信息处理的价值都有了更高的要求[4-6].然而，随着从大数据中挖掘出各种各样的敏感信息，数据参与者的隐私受到了严重威胁，这迫使人们加强对数据的隐私保护[1, 6-10].

虽然学术界并没有通用的隐私概念，但一般意义下，用户会将一部分信息认为是自身敏感并且不愿意公开的，通常将这部分信息称为隐私.然而，如果直接将这部分信息屏蔽，数据的价值就会大打折扣.可以说，完善地保护敏感信息，同时又有效地释放对公众有益的信息，这本身就是一对矛盾的事情[11].在社会学方面，可以制定保护个人信息的法律，对恶意窥探他人隐私的行为进行惩罚，但是这种方法实施起来需要大量的人力资源，效果也不甚理想[2，12].因此，从技术上解决这个问题变得更加实际，通常的做法是通过“去识别”的方式使部分数据匿名.但不幸的是，随着数据量的增长，数据之间的关联度日益增强，一些经过“去识别”处理的匿名数据，仍然能够通过互相之间的联系得到辨认，使得预防用户身份再识别的难度与日俱增.2006年，Dwork提出了差分隐私(differential privacy)的概念[13].差分隐私是迄今为止针对攻击者的先验知识进行普遍保护的最有效的技术.作为有望解决大数据中隐私保护问题的一个重要研究方向，最近十余年差分隐私在学术界[3, 14-26]和工业界[27-29]均受到了广泛关注.

尽管如此，现有差分隐私的研究主要基于静态数据集，在给定数据集上设计满足差分隐私的算法，而在现实中数据模式和数据内容时刻都在发生着变化，实现对动态数据的利用和隐私保护将更有意义，也更具挑战性.一个值得注意的事实是，差分隐私的相关算法大多在数据管理系统中实现.例如，管理分布式数据的Airavat系统在云计算环境中执行MapReduce计算时，在强制访问控制框架下利用差分隐私发布数据[30].问题是，即使这类系统的相关构件正确实现了差分隐私的有关算法，但是因为无法确保系统在整个过程中妥善处理了敏感数据且没有给攻击者提供可以推断出敏感信息的渠道，所以仍然无法确保整个系统具有差分隐私性.另外，早在2010年，Dwork等[31]就注意到一些实际应用中(例如，流感的发病率监测)需要反复计算，从而研究了在连续观察(连续处理输入数据产生输出数据)时，如何设计高效的隐私性算法.因为不同的数据可能属于同一用户，所以，在用户层面保护隐私，而不是针对每个输入保护隐私，就显得非常必要.可见在传统差分隐私算法设计方面也出现了动态处理数据的要求.

可喜的是，近几年国内外一些学者开始在系统层面研究差分隐私，即将差分隐私的思想用于系统在多次输入和输出情况下的整体隐私性研究.在系统层面考虑隐私性，除了上面提及的因素之外，另一个动机是，最近几年学者们在系统层面研究匿名性[32-34]、信息泄漏[35-36]和可靠性[37-38]等安全属性方面，取得了一些突出的成果，这激励着学术界进一步从系统层面研究隐私性.粗略地说，系统层面差分隐私的研究一般采用概率自动机、概率进程代数、概率标号迁移系统或马尔可夫链等建模系统，在此之上量化系统的迹(trace)、概率分布等行为随系统输入的改变情况.如果系统输入的微小改变，不会引起系统行为的较大变化，那么这个系统被认为是保护差分隐私的.本文旨在简要综述概率系统差分隐私的最新研究进展和研究方向，以期促进该领域的进一步研究.

本文简要阐述了传统差分隐私概念提出的背景、定义及相关扩展；较详细地介绍了概率系统差分隐私方面的研究进展；讨论了概率系统差分隐私保护研究所面临的挑战和未来的可能发展方向.

1 传统差分隐私

目前，大数据分析被广泛应用于科学、医药、商业、农业等诸多领域，帮助人们获取知识和预测趋势.然而，大数据的兴起也给数据分析的各个阶段，如数据收集、数据保护、数据处理、数据修复，带来了新的挑战[39-40].大量事实表明，如果大数据未被妥善处理和保护，那么它们可能会对用户的隐私造成极大的侵害[39, 41].即使许多看似无害的数据，被攻击者大量收集后，也可能会因为这些数据彼此之间的联系而暴露用户隐私[42].因此，不可能单纯通过法律条款实现用户隐私保护，这迫使人们寻求新的技术手段来解决隐私保护这一难题.

在数据库领域，隐私保护一直就是一个备受关注的研究方向.对于数据发布者来说，如何将有用的信息发布出去，同时还要保护数据参与者的隐私不被泄漏，一直是一个两难的问题[11，43-45].在大数据应用环境下，数据之间存在着复杂的关联和敏感性，数据呈现出动态特征，而大部分基于静态数据集的传统数据隐私保护模型和算法无法直接移植到大数据应用中[39].以典型的k匿名方案为例，早期的方案及其优化方案通过元组泛化、抑制等数据处理[46-48]，将准标识符分组，使得发布的数据中至少包含一定数量无法用准标识符区分的条目，这样攻击者就不能判断出隐私信息所属的具体个体.然而，这些工作是针对静态及一次性数据发布情形的.在大数据背景下，情况更加复杂，攻击者既可以持续地收集用户的历史数据，从而具备学习用户背景知识的能力，又可以从多种渠道获得数据，对多次发布的数据进行联合分析，破坏数据原有的匿名特性.

大数据时代的隐私性主要体现在不暴露用户敏感信息的前提下进行有效的数据挖掘[49].因此，保护隐私的数据挖掘方面的研究，近年来逐渐成为相关领域的研究热点，并主要集中于研究新型的数据发布技术，尝试在尽可能少损失数据信息的同时最大化地隐藏用户隐私[1, 6, 50].这方面标志性的工作，是Dwork于2006年提出的差分隐私概念[13]：

定义1[13](差分隐私).设是一个随机算法，其值域为Range().给定ε≥0，对于任意两个仅相差一条记录的相邻数据集D和D′，以及Range()的任意子集S，如果算法满足

差分隐私成功的原因之一是它的上述定义不依赖于秘密信息的先验知识，使得它对于多种信息资源组合的攻击具有鲁棒性.具体而言，差分隐私要求当一个函数(查询)作用在两个仅仅相差一个条目的数据库上时，得到的结果应该在概率上不可区分.也就是说，对于给定的结果，两种情况下得到这个结果概率的比值不会超过一个给定的参数[13].这样，差分隐私就可以有效地保护单个参与者，因为即使一个调查者对于被调查的数据库有一些预先的了解，他也不可能通过满足差分隐私的函数，来获取针对某个参与者更为详尽的信息.

为了实现查询结果的隐私性，一个常见方法是在精确查询结果的基础上，人为地再增加一个噪音量，这样可使得查询结果具有随机性.但问题是，如果噪音的特点比较明显，分布比较集中，那么加入了噪音的查询结果还是能够反映出一些特征，从而被进一步利用.针对差分隐私，最常见增加的噪音是拉普拉斯噪音，这种噪音在早期差分隐私方面的研究中就已出现[51]，并且一直保持着长久的生命力.拉普拉斯噪音依赖于查询的敏感度(即查询函数在两个仅相差一个元素的数据集上查询结果之差的最大值)，并以此为基础构造出满足拉普拉斯分布的随机变量，将它作为噪音添加到查询结果中.Geng等[52-53]优化了拉普拉斯噪音，提出了一种概率密度函数满足阶梯性质的噪音，可以在同等程度的隐私保护下，取得更好的有效性.

虽然差分隐私最初是为了保护统计数据库隐私安全而提出的概念，但是差分隐私的思想已被广泛应用到其他诸多领域，包括程序语言[40, 54-55]、推荐系统[56-57]、地理位置[58]、社交网络[59]、疾病发现[60]、智能运输系统[61]、人类活动[62]、聚合监测[63]和滤波[64]等.现阶段，差分隐私理论方面的工作主要集中在算法设计和模型扩展上.算法设计包括如何设计满足更强隐私性或更高效率的算法，以及如何在数据的可用性和隐私性之间达到更加优异的平衡[14，65-67].模型扩展方面，Li等[68]在此基础上给出了隐私定义的一个统一框架——隶属隐私(membership privacy)的概念；Duchi等[69]细化了对个人敏感信息的保护，提出了局部差分隐私(local differential privacy)的概念[24]；Chatzikokolakis等[70]考虑了使用一般度量代替数据库条目间差别的汉明距离；最近，Dwork等[71]考虑了传统差分隐私的一个松弛版本——中心化差分隐私(concentrated differential privacy)，该隐私性具有较好的精度和群体性质；为了更好地保证数据的可用性，Soria-Comas等[72]扩展了传统差分隐私，提出了个体隐私性(individual differential privacy)的概念.

2 概率系统的差分隐私

系统层面差分隐私的研究起源于2009年卡内基梅隆大学CyLab网络安全实验室Datta教授课题组的工作“Differential Privacy for Probabilistic Systems”[73].随后，该课题组和国际上其他研究团队继续推进了这方面的研究，分别以概率输入输出自动机、概率进程代数、概率标号迁移系统和马尔可夫链等为模型，扩展了传统差分隐私概念，并研究了相关性质，得到了一些好的结果.本节根据概率系统的不同建模方式，分别介绍这些研究进展.

2.1 基于概率输入输出自动机的差分隐私研究

如定义1，传统的差分隐私保护的是以数据集为输入的概率函数的隐私性.该概念提出后不久，Tschantz等便注意到这种差分隐私无法保证数据库系统和分布式系统的隐私性[73]，进而考虑将差分隐私定义从保护函数的隐私性扩展到保护系统的隐私性.基于确定型概率输入输出自动机，他们形式化定义了迹差分隐私(trace differential privacy)，并考虑了强和弱两个版本.直观上该定义要求，当使用概率自动机实现差分隐私函数时，对于仅仅相差一个数据点的不同输入，自动机生成的迹的概率分布大致相同.强迹差分隐私和弱迹差分隐私之间的区别在于前者要求隐私误差上界必须是固定常量，而后者则允许误差的上界可根据查询的数量和类型改变.他们揭示了这些定义与传统差分隐私概念间的关系，利用展开关系(unwinding relation)发展了一种证明技术，用于验证给定系统是否满足迹差分隐私，并在代表性示例中阐明了该技术.需要指出的是，文献[73]中考虑的是异步系统，即回答查询的顺序未必与提出查询的顺序一致，这种额外的灵活性会对差分隐私产生微妙的影响.基于从函数隐私性到系统隐私性扩展的类似动机，Tschantz等[74]在交互式系统(interactive systems)中扩展了差分隐私，提出了差分非干扰(differential noninterference)的概念.他们以概率输入输出自动机的一种简单版本——概率输入输出迁移系统作为模型，将输入分为数据和查询，输出分为可观测和不可观测两部分，基于自动机运行产生的迹，扩展了传统的差分隐私概念.上述工作[73-74]的完整版本，以及合成推理和差分隐私源代码的自动验证等，被写入长达65页的技术报告[75]中.

2.2 基于概率进程代数的差分隐私研究

许丽丽等[76-79]深入、系统地研究了概率行为和非确定性行为共存的并发系统隐私保护问题，提出了一些验证概率并发系统差分隐私性质的新技术.他们以概率CCS为模型，模块化分析了概率并发系统的差分隐私性，证明了非确定性选择、概率选择和限制等算子是保隐私算子，进而利用并发理论中的互模拟技术，重新形式化、改进和发展了基于概率互模拟和Kantorovich距离的衡量差分隐私的三种伪度量及其性质，并利用这些伪度量验证了概率并发系统的差分隐私性.另外，他们分别构造了分摊互模拟和分摊观察同余的公理化系统，证明了其可靠性和完备性，这两个证明系统使得人们能够仅通过语法层面的操作推导出可观察的差分隐私行为.众所周知，概率互相似(即最大的概率互模拟)或近似概率互相似[80]是区分概率并发系统行为的有力工具，这里“行为”通常包括系统可执行的动作以及能够到达的状态集上的分布，不涉及任何隐私方面的要素.如何将系统的隐私性与经典的概率互相似研究相结合，还有待深入探究.最近，Gruska[81]在一种特殊的概率CCS中，利用传统差分隐私性概念，给出了几个基于信息流的量化安全性概念.这些工作与Tschantz等工作的一个共同特点是，将差分隐私定义在概率语言上.这无疑使得实际应用中的计算变得极其困难，同时，也难以处理并发系统中普遍存在的无限长路径.

2.3 基于概率标号迁移系统的差分隐私研究

受Tschantz等[73-74]和许丽丽[76]工作的启发，基于传统差分隐私和概率互相似的思想，杨建楠等[82-83]进一步研究了概率系统中差分隐私的验证问题.研究采用一般概率标号迁移系统作为模型，该模型包括确定型概率自动机和概率CCS作为特例.不同于文献[73-75]中将输入当作需要保护隐私的数据，文献[82-83]中需要保护隐私的数据是系统状态，为此，他们在系统状态集上预设了一个度量，用以刻画数据间的相邻性，进而通过计算两个相邻状态在经过同一标号迁移之后状态分布之间的差别，定义了概率系统中的差分隐私概念.为了量化在不违背差分隐私的前提下，两个状态之间能达到距离的下界，他们给出了下确界度量的概念，定义的下确界度量被证明确实是一个度量，并且这个度量是概率系统中差分隐私的一个度量实例，从而确立了下确界度量的关键性.在此基础上，借鉴CCS中传统的Hennessy-Milner逻辑，提出了一个新的二层逻辑，并证明了这个二层逻辑不仅具备刻画概率互相似的能力，而且能刻画他们所提出的概率系统中的差分隐私.作为应用，他们研究了隐私通信协议——Crowds协议的一个变体，并验证了Crowds协议满足他们所提出的差分隐私概念.另外，利用文献[82]中差分隐私的相关性质，在文献[83]中给出了一个计算下确界度量的算法.基于给定的概率标号迁移系统和隐私参数，该算法可计算出下确界度量，得到系统状态间的具体距离.

2.4 基于马尔可夫链的差分隐私研究

最近，张立军课题组[84]和Castiglioni等[85]分别利用马尔可夫链、马尔可夫决策过程和标号马尔可夫链研究了差分隐私.根据差分隐私模型是否与环境交互，文献[84]分别使用马尔可夫链和马尔可夫决策过程，形式化描述了传统差分隐私定义中的随机机制.在新介绍了一种用于描述差分隐私性质的时态逻辑基础上，研究了相应的模型检测问题，并讨论了模型检测算法的复杂性，为数据分析师自动化验证其设计及实现提供了可能.文献[85]则基于标号马尔可夫链和经典Hennessy-Milner逻辑的一种概率变体，通过在公式上定义语法距离来量化语法差异，从而建立了差分隐私的逻辑刻画.值得注意的是，这里的差分隐私实际上是传统差分隐私和局部差分隐私的一种基于度量的推广[70].在利用行为度量刻画差分隐私的同时，该文也通过公式上定义的语法距离，分别给出了弱匿名性和广义互相似度量的逻辑刻画.需要指出的是，文献[85]中的标号马尔可夫链也是一种特殊的概率标号迁移系统，其特殊性在于，从每个状态出发，至多只可能有一个迁移.另外，Huang等[86]利用马尔科夫链建模了分布式控制系统，定义了随机控制机制的差分隐私概念，研究了系统中个体分享信息时差分隐私的代价问题；也有学者利用隐马尔可夫模型，发展了基于概率推测的位置大数据隐私保护技术[9].

3 总结与展望

当下，数据迅速膨胀，大数据的应用越来越彰显其优势，然而隐私保护变得越来越困难.差分隐私作为一种重要的隐私保护技术，在过去十余年受到了广泛关注.本文简要回顾了传统差分隐私概念提出的背景、定义及其扩展，从形式化方法的视角，介绍了概率系统差分隐私方面的研究进展.更多差分隐私形式化验证方面的工作，例如，基于类型系统、逻辑公式或Coq证明等方法，可参见文献[25，84-85，87-88]及其参考文献.

差分隐私自身的蓬勃发展以及匿名性、信息泄漏和可靠性等安全属性在系统层面的研究进展表明，系统的隐私性是大数据背景下一个极具前景的研究方向，有着重要的理论意义和潜在的应用价值.目前，这方面的研究虽已起步，但仍处于初期探索阶段，尚有大量关键问题需要深入而细致地研究.例如，目前考虑的系统模型比较特殊，缺乏统一的一般模型；目前模型的提取主要依赖于手工，未来希望能从软件系统的源代码中自动提取系统模型；模块化验证和自动化验证技术还有待发展；在系统层面，隐私保护预算和可用性方面的探讨较少；缺少丰富和具体的应用实例.