论文阅读笔记 | Enemy At the Gateways：Censorship-Resilient Proxy Distribution Using Game Theory（NDSS 2019）

论文信息

• 论文：Enemy At the Gateways：Censorship-Resilient Proxy Distribution Using Game Theory
• 会议：NDSS
• 发表时间：2019年
• 作者：Milad Nasr，Sadegh Farhang，Amir Houmansadr，Jens Grossklags
• 学校：马萨诸塞大学阿默斯特分校，宾夕法尼亚州立大学，慕尼黑工业大学

核心思想

1. 利用college admission game^[1] 对代理分配机制进行建模，其中“学生”对应用户/审查节点(client)，“大学”对应代理(proxy)
2. 通过延迟接受算法（deferred-acceptance algorithm）找到代理分配的最优策略

---

1. 背景

现有的许多匿名系统，比如Tor，通过分发中间代理的IP给用户，用户选取部分的代理，绕过审查并实现匿名。 这种基于代理的匿名系统存在内部攻击的问题：审查者可以通过多个审查节点冒充普通用户，获取并共享系统分配的代理信息，通过这些信息来限制普通用户的匿名访问。现有的代理分配方法方法是基于启发式的，很容易绕过。

图1 针对基于代理的匿名系统的内部攻击

本文基于博弈论框架对代理分配和审查机制进行研究，提出各方的最优策略。

2. 方法

2.1 college admission game

本文通过college admission game^[1]（大学招生问题）来对代理分配机制进行研究，因此首先介绍一下college admission game。讲完这个博弈机制以后，自然能迁移到代理分配的问题上。

• 定义：有$n$n个学生，$m$m个大学，每个大学招生的容量是$q_i$qi​
• 志愿：
  • 学生根据自己的偏好对学校进行优先级排序，然后申请大学
  • 学校根据偏好对申请它的学生进行排序，录取学生

比如图2中，有$i,j,k$i,j,k三个学生，两所大学，他们分别根据自己的偏好对对方进行排序。学生$i$i最喜欢大学2，然后才是大学1；学生$j$j更喜欢大学1，然后是社会大学（$\emptyset$∅），也就是出来找工作… 大学1更倾向于录取学生$i$i，然后是学生$j$j和$k$k；大学2倾向于录取学生$k$k，然后是学生$i$i

图2 学生和大学根据偏好进行排序

• 目标：基于学生、学校各自的偏好排序以及学校的招生容量进行决策。找到最优的稳定分配，学生和学校都能与自己偏好 的对象相配对

稳定分配怎么理解呢？图3中是一个稳定分配的例子，假设学校的容量为1。在图3中，每个学生都进入了自己心仪的学校，每个学校也录取了自己心仪的学生。

图3 稳定分配

来看看反例。图4中是一个不稳定分配的例子。学生i和j分别被大学1和2录取，但是根据图2，学生$j$j想进的学校是大学1和社会大学，大学1想录取的是学生$i, j, k$i,j,k。因此在学生$j$j这边就存在一个不稳定分配。

图4 不稳定分配

2.2 延迟接受算法

如何找到稳定分配呢？这就需要延迟接受算法啦。它的作用就是找到college admission game中最优的稳定分配策略。

流程：

• 第一轮中，所有学生根据偏好申请优先级最高的大学；学校根据其对学生的偏好、容量$q$q，录取$q$q个学生，放入候补名单中
• 接下来的每一轮，学生被拒绝后申请次一级的大学；学校从前一轮候补名单中根据偏好选$q$q个学生，还有本轮申请的新生（可能新生是学校偏好排序中优先级较高的学生，因此要纳入其中进行考虑）。再根据学校的偏好选取$q$q个学生放到候补名单中
• 重复以上步骤直到学生都在候补名单中或是被他申请的所有学校拒绝

让我们用大学招生问题来理解一下这个算法。图5中，根据图2中学生以及大学各自的偏好，学生$i$i首先申请学校2，$j$j申请1，$k$k也申请1。

• 由于学校容量是1，并且学校1的偏好中，$j$j优先级大于$k$k，因此第一轮中，学校1将$j$j放入候补名单中，拒绝$k$k。学校2将$i$i放入候补名单中。

• 接下来第二轮中，$k$k被拒绝后申请学校2，对于学校2，$k$k优先级高于$i$i，因此将$k$k放入候补名单中，拒绝$i$i。

• 第三轮中，$i$i被拒后申请学校1，对于学校1，$i$i优先级高于$j$j，因此接受$i$i，拒绝$j$j

• 第四轮中，$j$j根据偏好只能申请社会大学。因此，最后的结果是学校1录取$i$i，2录取$k$k，3录取$j$j。

最终根据学生和学校的偏好，学生和学校都对自己的结果满意。

图5 延迟接受算法在大学招生问题中的例子

可以看出，延迟接受算法的关键在于学校对于中意的目标没有立即接受，而是放进候补名单中；同时，也让学校获得具有更多的信息，从而做出双方都满意的决策。

2.3 proxy assignment game

ok，讲完了大学招生问题以及延迟接受算法，接下来我们就来看一下怎么讲这个博弈机制引入到代理分配的问题上。

将college admission game应用到代理分配问题中，client (包含良性节点和审查节点)对应学生，proxy对应大学。

我们注意到前面经常提到的“偏好”，显然在实际情况应用中，我们需要对这个偏好进行量化。怎么量化呢？可以选取一些client和proxy的特征，分配权重，通过效用函数计算出偏好的得分，得分高的优先级高。

client	proxy
$U_{a_i}^{t}(p_x)$Uai​t​(px​)	$U_{px}^{t}(a_i)$Upxt​(ai​)
client $a_i$ai​在$t$t轮对代理$p_x$px​的评分	代理$p_x$px​在$t$t轮对client $a_i$ai​的评分

可以使用的特征包括：

client	proxy
代理的利用率	知道该代理的客户端数量
客户端未使用便被屏蔽的代理数	连接到该代理的用户数
对新代理的请求数	该代理总的时间利用率
客户端已知的被屏蔽的代理数	与客户端的距离
与代理的距离	…
…	…

最优代理分配策略：那么，我们可以利用延迟接受算法得到最优的代理分配策略。并且，代理分发者代表clients和proxies在本地进行博弈；当体有client请求代理信息时，根据client的特征分发代理信息。

这里有个疑问，为什么这种分配策略能解决内部攻击的问题呢？
我的理解：如果client是良性节点，那么它没必要使用代理分发者分配给其他节点的代理，因为client得到的代理对于它自己来说已经是最优的。如果client是审查节点，虽然审查节点可以共享它们获得的代理，但是没有必要这样做，因为它们已经获得了对于它们来说的最佳代理，而代理信息对于其他节点来说不一定会用到。

最优的审查机制：审查者可以通过收集多个审查节点得到的代理信息对代理进行限制。通过最大化审查节点（client的一种）的效用函数，使其在代理这边的优先级更高，能够发现更多的代理。同时，屏蔽更多的代理，衡量审查者对客户端的影响，这部分通过计算没法从分发者那边获得代理信息的受审查节点的比例进行量化。

3. 实验

3.1 实验设置

• 实现了代理分发模拟工具HypoTor，参数尽可能使用真实世界中匿名系统的数据
• 每个实验模拟5年

3.2 实验假设

• 客户端只能从代理分发者得到代理信息
• 审查节点可以彼此沟通，审查者汇总审查节点得到的代理信息

3.3 评估标准

• 连接的客户端：能访问未被屏蔽代理的受审查客户端的比例
• 未被屏蔽的代理：审查者未发现的代理的数量或比例
• 客户端等待时间：受审查的客户端等待多少轮才能获得未被屏蔽的代理信息

3.4 实验结果

• 本文得到的审查机制效果明显：能阻拦更多的代理，使连接用户数大大减少，后续试验均采用该审查机制
  

图6 最优审查机制

• 本文的代理分配策略有效：在前面实验得到的最优的审查机制下对代理分配策略进行实验，连接用户数相比现有的方法有显著增加

图7 最优代理分配机制

4. 总结

代理分发是许多匿名通信系统的关键，本文首次利用博弈论对代理分发问题进行建模并得出目前为止最优的代理分配机制。

优点：该博弈论框架是通用的，对于具体的场景可以设计不同的效用函数；并且客户端、代理不需要任何的信息，博弈是在代理分发者本地进行的

局限：文中假设客户端只能从代理分发者获取代理信息，没法抵御流量指纹分析等攻击

思考：必须不断有代理加入到整个匿名网络中才能保证匿名性，现有的方法没法做到一劳永逸

---

最后，文章中有理解错误的请指出！

参考资料

[1] D. Gale and L. S. Shapley, “College admissions and the stability of marriage,” The American Mathematical Monthly, vol. 69, no. 1, pp. 9–15, 1962.