应对洪水：如何使用eBPF保护UDP服务免受DoS攻击

CloudFlare的全球分布式网络不仅设计用于保护HTTP服务，还用于保护通过我们边缘的任何类型的TCP或UDP流量。为此，我们已经构建了许多复杂的DDoS缓解系统，例如分析全球流量模式的Gatebot。但是，我们始终采用深度防御：除了全局保护系统之外，我们还使用现成的机制，如TCP SYN-Cookie，这些机制可以保护本地的单个服务器免受非常常见的SYN洪水的影响。但有一个问题：UDP不存在这样的机制。Udp是一种无连接协议，在数据包周围没有类似的上下文，特别是考虑到Cloudflare为上层协议(DNS、ntp、…)不可知的Spectrum等服务提供支持。，所以我2020年的实习班项目是想出一种不同的方法。

首先，让我们讨论一下为UDP服务提供保护的实际含义。我们希望确保攻击者不会淹没合法流量。为了实现这一点，我们希望识别洪水并加以限制，同时保持合法流量不受影响。

缓解此类攻击的想法很简单：首先确定与攻击相关的一组数据包，然后对该组应用速率限制。这些组是根据数据包中可供我们使用的属性(如地址和端口)确定的。

我们不想完全停止流量泛滥，因为合法流量可能仍是其中的一部分。我们只想丢弃尽可能多的流量，以符合我们设定的速率限制。不能仅仅因为一组数据包略高于速率限制就完全忽略它，因为它可能包含合法流量。

这既确保我们的服务保持响应，又确保合法数据包受到的影响尽可能小。

虽然速率限制是一个比较简单的过程，但由于多种原因，确定组就有点困难了。

确定数据包中的组的问题是我们几乎没有任何上下文。我们考虑四个有用的属性作为攻击特征：源地址和端口以及目的地址和端口。虽然这已经不是很多，但情况会变得更糟：源地址和端口甚至可能不准确。数据包可能会被欺骗，在这种情况下，攻击者会隐藏自己的地址。这意味着只保留每个源地址的速率可能不会提供太多价值，因为它可能只是被欺骗。

但还有另一个问题：每个地址保持一个速率不能扩展。当将IPv6纳入等式及其庞大的地址空间时，很明显它行不通。

为了解决这些问题，我们求助于学术界，找到了我们正在寻找的问题，重量级人物的问题。重命中者是数据流中频繁出现的元素，并且可以相对于流的整体元素来表示。例如，我们可以定义一个元素，如果它的频率超过总计数的10%，则认为它是重击。要做到这一点，我们可以天真地建议简单地为每个元素维护一个计数器，但由于空间限制，这将无法扩展。取而代之的是，可以使用诸如CountMin草图或SpaceSaving算法之类的概率算法。它们提供估计的计数，而不是精确的计数，但是能够在内存需求不变的情况下做到这一点，在我们的示例中，我们将只将比率保存到CountMin草图中，而不是计数。因此，无论我们需要跟踪多少独特的元素，内存消耗都是相同的。

我们现在有了一种大海捞针的方法，而且它确实有恒定的内存要求，从而解决了我们的问题。然而，现实并没有那么简单。如果攻击不只来自单个端口，而是来自多个端口，该怎么办？或者，如果反射攻击正在攻击我们的服务，导致随机的源地址但只有一个源端口，该怎么办？也许一个完整的/24子网给我们带来了洪水？我们不能只对我们看到的每个组合保持一个比率，因为它会忽略所有这些模式。

幸运的是，学术界再次对我们进行了报道，提出了等级重量级人物的概念。它通过使用流元素中的底层层次结构扩展了重命中者的概念。例如，一个IP地址可以自然地分为几个子网：

在本例中，我们定义考虑完全指定的地址、/24子网和/0通配符。我们从左侧完全指定的地址开始，每往上走一步，我们就会考虑较少的信息。我们称这些不太具体的地址为泛化，并通过指定级别来衡量泛化的具体程度。在我们的示例中，地址192.0.2.123位于级别0，而192.0.2.0/24位于级别1，依此类推。

如果我们想要创建一个可以为每个数据包保存此信息的结构，它可能如下所示：

我们为每个子网维护CountMin-sketch，然后应用重量级应用程序。当新的数据包到达时，我们需要确定它是否被允许通过，我们只需检查每个节点中相应元素的速率。如果没有速率超过我们设置的速率限制，例如每秒25个数据包(PPS)，则允许其通过。

该结构现在可以跟踪单个属性，但我们会浪费大量有关数据包的上下文！因此，我们没有浪费它，而是使用了论文中提出的二维地址分配方法和SpaceSaving算法，并对其进行了进一步扩展，将端口也纳入了我们的结构中。端口没有地址等自然层次结构，因此它们只能处于两种状态：指定(例如8080)或通配符。

现在，让我们讨论一下我们用来遍历结构并确定是否应该允许数据包通过的算法。具有SpaceSaving算法的分层Heavy Hitters一文提供了两种可以在数据结构上使用的方法：一种是更新元素并增加其计数器，另一种是提供当前是Heavy Hitters的所有元素。对于我们的用例，这实际上不是必需的，因为我们只对我们现在正在查看的元素或数据包是否能够通过感兴趣，以决定它是否可以通过。

其次，我们的目标是防止任何重击物通过，从而使结构没有任何重击物。这是一个很好的属性，因为它允许我们大大简化算法，它看起来如下所示：

正如您可能注意到的，我们更新一个级别的每个节点并保持我们看到的最大速率。在每个级别之后，我们根据在该级别上看到的最大速率和设置的速率限制，计算确定数据包是否应传递到下一级别的概率。每个节点实质上为以下不太具体的级别过滤流量。

我实际上忽略了一个小细节：如果任何速率超过限制，则不会丢弃数据包，而是保留看到的概率速率限制/最大速率。原因是，如果我们只是丢弃所有的数据包，如果速率超过限制，我们就会丢弃整个流量，而不仅仅是子集，以使其符合我们设置的速率限制。

由于现在即使节点达到速率限制，我们仍会更新更多特定节点，因此速率限制将尽可能向攻击的基本模式收敛。这意味着其他流量将受到尽可能最小的影响，而且不需要任何人工干预！

由于我们希望使用此算法来缓解泛洪，因此在决定是否应该丢弃数据包之前，我们需要花费尽可能少的计算和开销。像往常一样，我们查看了BPF工具箱，发现了我们需要的东西：SocketFilters。正如我们的同事马雷克(Marek)所说：“看起来，不管是什么问题--BPF就是答案。”

套接字过滤器是可以附加到单个套接字的代码片段，并且在将数据包从内核传递到用户空间之前执行。这是理想的选择，原因有很多。首先，当内核运行套接字筛选器代码时，它会为它提供我们需要的数据包中的所有信息，并且已经执行了其他缓解措施，如防火墙。其次，代码是按套接字执行的，因此每个应用程序都可以根据需要激活它，还可以设置适当的速率限制。它甚至可以对不同的套接字使用不同的速率限制。第三个原因是权限：我们不需要是root用户就可以将代码附加到套接字。我们可以作为普通用户在内核中执行代码！

BPF也有一些限制，这些限制过去已经在本博客中讨论过，因此我们将重点介绍我们项目特有的限制：浮点数。

为了计算利率，我们需要浮点数来提供准确的估计。BPF以及整个内核都不支持这些。相反，我们实现了一个定点表示，它将可用位的一部分用于有理数的小数部分，将剩余的位用于整数部分。这允许我们表示一定范围内的浮点数，但在进行算术时有一个问题：虽然两个定点的减法和加法工作得很好，但乘法和除法需要两倍的位数才能确保精度不会有任何损失。由于我们的定点值使用64位，因此没有更大的数据类型可用来确保这种情况不会发生。我们将其中一个参数转换为整数，而不是精确地计算结果。这会导致小数部分的丢失，但当我们处理大速率时，这不会造成任何问题，并帮助我们绕过位限制，因为中间结果适合可用64位。当需要定点运算时，必须仔细考虑中间结果的精度。

实现还有更多的细节，但我们不要在这篇博客文章中讨论每一个细节，让我们只看一下代码。

我们在Github上的CloudFlare/raklimit上开源了raklimit！它是一个成熟的围棋库，可以在任何UDP套接字上启用，并且很容易配置。

开发仍处于早期阶段，这是第一个原型，但我们很高兴能继续与社区一起推动开发！如果你仍然不满足，看看我们在今年的Linux Plumbers大会上的演讲。

EBPF Linux UDP编程