G.O.S.S.I.P 阅读推荐 2022-07-20

搞排名是人类的天性之一，但是科学排名就不那么容易了。今天给大家推荐的论文 Building an Open, Robust, and Stable Voting-Based Domain Top List 发表于 USENIX Security 2022，是一项基于投票算法对域名进行科学排名的研究。本文涉及的主要研究内容是第一作者谢秦歌同学 （https://xqgtiti.github.io/） 在奇安信实习期间完成，合作者中包括了本领域知名的段海新教授（清华）和Frank Li教授（谢秦歌同学目前的博士生导师）。

域名排名列表是研究人员对网络进行分析的重要资源，许多研究都是基于一些现有榜单（如 Alexa, Umbrella 以及较新的 Tranco）。然而，这些现有榜单都存在许多缺陷，如缺乏对榜单数据和构建方法的透明性、榜单的高波动性和易受操纵性。

在本文中，作者系统地探索了如何从零开始构建域名榜单列表。作者通过使用大量的 Passive DNS 数据集，提出一种基于投票的域名排名方法。其中量化了每个客户端 IP 地址的域偏好，然后通过投票机制确定域名的全球排名。

在工作开始之前，作者对现有域名排行榜单进行系统性的研究，发现了现有排名的缺陷，并找到操控这些排名的攻击方法。作者认为，Alexa 和 Umbrella 这两个受欢迎的排名榜单的算法都不透明，而 Tranco 的排名算法虽然公布，但它是依赖于现有的 Top 列表进行排名的。因此，作者的排名方法必然是要改进这些缺陷，显现出构建方法的透明性、排名榜单的低波动性和不易受攻击者操纵的特性。而这三点也是作者在文中讨论的一个理想的 Top 列表应具有的属性。

在此次排名中，作者的 PDNS 数据集来自于中国最大的域名服务提供商 114DNS，平均每天有来自 70M 客户端的约 500B 次唯一 DNS 请求。与 Umbrella 相比多出了500万个IP地址和2.5倍的DNS请求，也比 Alexa 多出了两个数量级的数据，因此需要计算效率非常高的数据处理方法。

接着，作者介绍了基于投票的域名排名方法，并讨论了如何确定各个客户端IP地址的域偏好、如何对IP地址进行加权、如何确定域投票算法。

在确定IP地址的域偏好时，作者采用了平滑函数来处理数据，这种方法还能够有效抵抗操纵攻击～感兴趣的读者可以自行在论文中查看细节。

在确定域投票算法时，作者根据投票机制必要具有的三个属性选择了四种投票方案：

投票机制的三个属性：

1. 投票方式必须允许一个投票者投票给多个候选域名，因为我们需要考虑每个IP地址查询多个域名。

2. 避免基于评分的投票方法，即避免每个选民为所有候选域名分配分数。这种方法需要所有IP地址提供赋分解释，不适用于此次场景。

3. 不能使用涉及多轮投票的投票方案，因为投票的IP地址只有一组域偏好。

最后，作者确定了四个成熟的投票方案，它们满足了时间复杂性要求和期望的特性。分别是 Approval、Borda、Dowdall 和 Bucklin。

• Approval：每个IP地址可以投票给任何数量的候选域名。候选人按照赞成投票的选民数量进行排序(不分先后)。

• Borda：每个选民对候选域名进行排名，候选域名的排名后有多少域名，此域名就会得到多少分。而由于每个IP地址请求的域名数量不同，算法将会设置一个阈值，对此阈值数量内对IP地址进行排名。

• Dowdall：是Borda的变体，投票点是按照 Zipf 定律分配的。排名第一的候选人得1分，排名第N的候选人得1/N分，再按照积分总和将域名进行排序。并且 Dowdall 不需要截断投票，因为无论候选域名数量如何，它都有一个分数上限 (1分)。

• Bucklin：在这种方法中，选民的首选域名是首先考虑的。如果一个候选域名在选民中占多数，那么他就会获胜。如果不是，则考虑选民的第二选择，如果候选域名现在在选民中获得多数，则获胜。这一过程一直持续到候选人获得多数席位。而当一个候选域名在选民中获得多数，Bucklin 就相当于 Approval 方案，因此作者没有对这种方法做进一步调查。

最终，在对几个投票方案进行比较后，作者选择了 Borda 对数据进行处理，并将阈值设为 1K。在进行方案设计时，作者认为好的排名系统应该具有良好的抵御操纵攻击的能力，因此对 Borda 进行了一系列实验。

要想操纵排名，攻击者首先必须将自己的IP地址进行权重提升，就需要对许多域名发送许多请求；其次攻击者还需要利用这些IP地址对想要操纵的域名发送大量请求，以达到将其设为首选偏好的目的。通过作者的实验，这将会耗费攻击者大量的资源。

作者还使用同样的方法与现有排名系统（Alexa、Umbrella、Tranco）进行比较：

最后得出结论：在相同的攻击条件下，作者实验的两个域名在 Alexa 和 Umbrella 中都获得了前 10K 的排名（并且最高排名达到过2859），而使用 Borda 则只获得了29K到41K名（最高29486），而 Tranco 的排名数据来自于 Alexa 和 Umbrella ，并且在实验中也能达到 2K 的排名，因此作者建立的排名明显更具有抗操纵性。

相关资源：

https://secrank.cn/topdomain

https://github.com/secrank

论文PDF：
https://www.usenix.org/system/files/sec22fall_xie.pdf

原文始发于微信公众号（安全研究GoSSIP）：G.O.S.S.I.P 阅读推荐 2022-07-20