Using game theory to thwart multistage privacy intrusions when sharing data
Abstract
问题：针对个人的生物医学数据共享引起的隐私问题，尤其是匿名记录的再识别
思路：再识别风险评估框架
常规方法：数据接收者只使用一种资源
存在问题：攻击者可以访问多种资源来增加攻击成功率
本文方法：构建完全信息双人Stackelberg博弈模型来表示再识别博弈，提出基于隐私-效用权衡的最优数据共享策略
Introduction
背景：生物医学数据共享有很大好处，但带来隐私问题
面临的问题：针对匿名生物医学数据的再识别攻击
简化的攻击模型会导致隐私风险被高估或低估；
攻击逐渐从过去的单阶段（将去除标识符的数据库与没有去除标识符的数据库通过一些共有属性链接起来）转变为现在的多阶段（每阶段披露目标个体的一部分信息）
本文：通过明确建模和量化数据主体在面对多阶段攻击时的隐私-效用权衡来评估和战略性地减轻风险，弥补了更复杂的攻击模型和数据共享决策之间的差距。
攻击模型：Gymrek提出的两阶段攻击——针对基因组计划数据库的姓氏推断与进一步的其他数据库链接推断
现有方法：
从监管和技术两个角度出发
关注最坏的情况——影响不明确
不考虑攻击成本——高估隐私风险
没有测量参数影响就设置参数——牺牲数据效用
由此出现了引入博弈论的风险评估
本文：
博弈论模型可以向数据主体揭示最佳的共享策略
使用真实世界的数据集或大规模模拟数据集进行反多阶段攻击的实验
博弈论模型可以有效地评估和有效地减轻隐私风险
模型所推荐的细粒度共享策略可以最大限度地减少数据主体被成功再识别的可能性，同时最大限度地提高数据效用，并保持发布的数据集的有效性和数据共享过程的公平性
Materials and Methods
研究场景：数据主体选择在公共库中分享多少主体的基因数据
研究目标：决定主体的最优共享策略，平衡数据共享带来的经济效益与再识别风险
再识别风险来源：
有动机和手段试图确定匿名共享数据集中的主体身份的人
已经向公众提供的关于主体的其他数据
攻击模型：Gymrek攻击
第一阶段：根据目标基因库和遗传族谱数据库进行姓氏推断
第二阶段：将姓氏推断结果和公共数据库进行链接，从而确定数据主体的身份
博弈模型：Stackelberg 博弈 或 leader-follower 博弈
假设数据主体和攻击者对攻击成功的概率有相同的信念
数据主体作为leader，选择共享多少数据
攻击者作为follower，选择是否进行再识别攻击
攻击者不知道被隐藏的信息，只能估计成功的概率，而数据主体则掌握更多信息
主体决策：$s=\langle s_1,…,s_j,…,s_m \rangle \in B^m$ 表示要共享的数据，其中m是记录中的属性数量，如果第j个属性被隐藏，则$s_j=0$，反之如果第j个属性被共享，则$s_j=1$
攻击者决策：$a\in \{0,1\}$表示是否进行再识别攻击，a=1表示攻击，a=0表示不攻击
对手攻击方式：两阶段Gymrek攻击，可以有更多个阶段，每阶段推断出一些新的信息
博弈过程：主体（leader）先决定自己的策略s，攻击者（follower）观察数据并基于此决定是否攻击，即攻击者的策略是主体策略的函数
引入新的符号和假设：
$b(s)$表示策略
s为主体带来的经济效益，公开信息，假设该函数非递减如果一个记录成功被再识别，假设该主体损失
L，攻击者获得L
攻击成功的概率取决于数据主体采取的策略，数据主体对这个概率以及再识别风险比攻击者更清楚，攻击者只能大致估计。
首先，假设数据主体和攻击者对每个策略分配的成功率都相同，记作$p(s)$。在已知$p(s)$的情况下，数据主体和攻击者可以最大化各自的期望收益。
然后，将期望收益视作真实收益，可得完美信息下的Stackbelberg博弈，并研究均衡。
数据主体的期望收益函数：$v_d(s,a)=b(s)-Lp(s)a$
攻击者的收益函数：$v_a(s,a)=(Lp(s)-C)a$
其中，C是攻击者的攻击成本
如果攻击者不攻击则其收益为0
可以通过重定义$b(s)$和重识别$p(s)$将该模型推广到其他数据共享的场景中
令$\phi(s)=\{a|(Lp(s)-C)a\geq(Lp(s)-C)(1-a)\}$，函数$\phi(s)$表示攻击者针对主体策略s的最优策略
均衡解对应的主体优化问题：$max_{s,a\in\phi(s)}b(s)-Lp(s)a$
主体求解方法：逆向归纳法——先计算攻击者对所有可能策略s的最优对策$\phi(s)$，然后选择自己的最优策略。
该方法问题：数据主体掌握了完整的数据，因此他们可以计算再识别概率$p(s)$，而攻击者则不能。
解决方法：攻击者使用再识别概率的估计值，记作$\hat{p}(s)$，并以此计算自己的收益和最优对策函数。数据主体同样可以用估计值来计算攻击者的策略，但他们会随后用真实的再识别风险概率计算自己的最优选择。
总结一下：攻击者和数据主体都可以用$\hat{p}(s)$来估计计算$\phi(s)$，记作$\hat\phi(s)=\{a|(L\hat{p}(s)-C)a\ge(L\hat{p}(s)-C)(1-a)\}$，在得到攻击者最优策略后，数据主体使用真实概率计算自己的最优策略$max_{s,a\in\hat\phi(s)}b(s)-Lp(s)a$。
说明：利用了Stackelberg博弈中leader只能做一次决策这一特点，使得该方法可以在计算过程中使用不同的再识别风险概率函数。
在两阶段攻击中，给定主体策略s，第一阶段攻击成功概率$p_1(s)$、在一阶段攻击成功基础上的第二阶段攻击成功概率$p_2(s)$、攻击者估计的一阶段成功概率$\hat{p}_1(s)$、攻击者估计的忽略一阶段情况下二阶段成功概率$p’(s)$的计算方式如下：
如果一阶段攻击更好，则$a’(s)$为1，反之则为0. 上面几个参数的具体值取决于攻击模型和攻击中用的数据集。
由此，如果$a’(s)$为1，优化问题可以表达为：
其中，$\hat\phi(s)=\{a|(L\hat{p}_1(s)p_2(s)-C)a\ge(L\hat{p}_1(s)p_2(s)-C)(1-a)\}$
详细推公式过程在附录，稍后再看。
所有的参数都可以根据用例进行合理的设置。具体来说，它们可以根据特定的数据集、攻击模型或受试者提供的估价进行调整。此外，正如结果所示，广泛的敏感性和稳健性分析（即压力测试）可以帮助验证参数设置对环境或主体知识的不确定性的敏感性和稳健性。
选择进入博弈：在一些情况，数据主体只有两种选择：加入并完全共享信息 或者 退出不共享任何信息。这样的场景可以由前文定义的博弈来刻画，其数据主体的策略被限制为两个选项：完全共享$s=<1,...1>$和完全不共享$s=<0,...0>$。
遍历求解博弈耗时多，附录中介绍了可以用于加速求解的算法，稍后再看。
Results
Experimental design
分别在真实数据集和仿真数据集上进行实验，后者更大一些
在基因数据集D中共享数据的n个数据主体的平均收益：$\overline{V}=\sum_{i=1}^{n}V_i$，其中$V_i$表示第i个数据主体的最优收益
平均数据效用：$\overline{U}=\sum_{i=1}^{n}U_i$
主体平均隐私：$\overline{P}=\sum_{i=1}^{n}P_i$
第i个数据主体的数据效用：$U_i=b(s_i^\ast)/B$，即部分共享带来的收益除以完全共享带来的收益
第i个数据主体的隐私：$P_i=1-p(s_i^\ast)a_i^\ast$，即1减去隐私风险（被成功攻击的概率）
第i个数据主体的最优收益：$V_i=v_d(s_i^\ast, a_i^\ast)=BU_i-L(1-P_i)=BU_i+LP_i-L$，即数据效用和隐私的线性组合，其中，L是再识别成功带来的损失。
作为有效性的主要衡量标准，这些主体的平均报酬与效用和隐私的衡量标准呈正相关。
实验设置：20个模拟数据属性，4个博弈场景，4个baseline场景，8种数据保护情况
攻击者目标：在理性权衡攻击收益的基础上，尽可能再识别数据集D中的所有数据。
8种情况的简要说明：
no protection：无保护，数据集
D中的每个主体都共享其数据记录中的所有属性demographics only：数据集
D中的每个主体仅共享人口统计学属性random opt-in：数据集
D中的每个主体根据实际设置，以一定的概率随机决定共享整个数据记录random masking：数据集
D中的每个主体随机决定以固定的概率分享其数据记录中的每个属性opt-in game：主体只能决定选择加入共享整个数据记录或选择退出
masking game：主体可以在共享前隐藏一部分数据
no-attack masking game：假设主体不选择任何会使对手攻击的策略
one-stage masking game：假设攻击只有一阶段，二阶段的那个数据集不可用
评估在每种情况下采用的数据保护/共享策略的效果：有用性和公平性
数据共享方案的有用性是基于共享数据和未受保护数据的分布之间的距离（详见附录S7）。
数据共享方案的公平性（例如，有用性方面的公平性或隐私方面的公平性）是基于每个人口群体对应的具体措施的基尼系数（详见附录S8）。
Experiments based on a large-scale simulated population
这部分是针对大规模仿真数据的实验
从平均收益来看有以下结论：
受试者的平均收益在没有保护的情况下是最低的，在有掩膜的博弈中是最高的。
与选择进入博弈相比，受试者的平均收益在掩膜博弈中得到了很大的改善。说明在数据共享过程中提供某种程度的细化选择的基本优势之一。
当攻击者使用较少的数据资源，从而在攻击中保持较少的阶段时，掩膜博弈效果更好。
无论是共享所有的数据还是只分享人口统计资料，或者是一个随机的策略，都会给受试者带来负的或可忽略的平均回报。
从效用与隐私的结合看有以下结论：
与其他情况相比，掩膜博弈能同时实现高效用和高隐私
受试者在无攻击掩膜博弈中的策略在大量共享数据的情况下保证了完全的隐私保护
当攻击只有一个阶段时，还能实现稍高的数据效用水平
与掩膜博弈相比，随机选择加入场景和随机掩膜场景给受试者带来了类似的隐私水平，但数据效用的水平却低得多
相比之下，与选择加入游戏相比，纯人口统计学方案给受试者带来类似的效用水平，但隐私水平较低
与无保护方案的结果相比，纯人口统计学方案总是为主体提供高得多的隐私水平，这突出了Gymrek攻击中姓氏推理阶段的力量
在博弈论的保护下，姓氏推断阶段的力量可以减少到最低限度，这一点从掩膜博弈和它的单阶段变化之间的差异可以看出
其他实验现象就不细看了，总结下来都是说掩膜博弈在效用、公平性、有用性这几方面更好。
还分析了后向归纳和剪枝贪婪在不同场景的计算效率。
Sensitivity and robustness analyses on parameters and settings based on simulated datasets
这部分仍然是大规模仿真数据，分析了在攻击成本、数据集记录数和再识别成功数这三方面的敏感性和稳定性。
实验设置：8个场景，11组实验，针对不同的参数使用不同的测试集进行了20次实验
实验结论：掩膜博弈更好
一些其他与各参数相关的实验不记录了，与博弈无关，更偏向生物医学
此外，分析了少数人支持系数，说明了掩膜博弈在公平性方面同样优秀
Experiments based on Craig Venter’s data and the Ysearch dataset
这部分是真实数据集的实验，同样说明了掩膜博弈更好。
Discussion
本文：针对再识别攻击，为数据主体提供共享策略
发现：
额外阶段会增加再识别的准确率，但同样更有利于我们通过博弈的方式反攻击，因为可以误导攻击者从而使其推断出错误的中间信息，从而减轻隐私风险。
如果数据库不允许进行部分数据共享（即：只能加入并完全共享或者退出），大多数理性的数据主体会选择退出；反之，如果允许部分共享，则大多数主体愿意共享大部分数据，这表明向主体提供选择可以鼓励更大程度的数据共享，同时避免再识别。
本文方案使得主体可以选择共享大量数据，获取高收益，同时不会面临再识别风险。
敏感性分析说明了参数对主体策略的影响，由此能进一步研究：政策制定者如何增加对隐私泄露的惩罚、数据持有者如何增加对数据共享的奖励等。
不足之处和后续研究：
仅考虑了一个攻击者和两阶段攻击实验
使用的决策模型较为简单，假设数据主体之间的决策相互独立，或所有主体选择相同的策略
目前的博弈模型所模拟的博弈双方并没有完全推理出所有的不确定性。双方都可能有不完全和/或不完善的信息。为了更加现实，可以使用更复杂的博弈论模型，如贝叶斯博弈，来模拟不完全和/或不完善的信息
没有研究数据持有者的最优策略，它们有动机控制付给数据主体的报酬
博弈模型可能会在发布的数据集中引起非随机缺失（MNAR）的值，这对数据集的使用可能会有不可忽略的影响
