考虑一个恶意行为者试图通过 API 进行数据注入、抓取、收集或泄露的情况。这类恶意活动通常以行为者以特定顺序向 API 端点发起请求。此外，仅仅使用容量技术往往无法轻易检测到这些恶意活动，因为行为者可能故意缓慢地执行 API 请求，以试图规避容量滥用保护。因此，为了可靠地防止这种恶意活动，我们需要考虑 API 请求的顺序。我们使用序列滥用这个术语来指代恶意的 API 请求行为。因此，我们的基本目标是区分恶意和合法的 API 请求序列。
在这篇博客文章中，您将了解我们如何应对帮助客户保护其 API 免受序列滥用的挑战。为此，我们将介绍目前支撑我们序列分析产品的统计机器学习(ML)技术。我们将在此前一篇博客文章提供的序列分析概括性介绍基础上进行深入探讨。
API 会话
在之前的博客文章中提到过，我们来考虑一下由某个用户发起一系列按时间顺序排列的 HTTP API 请求的概念。发起请求是因为该用户与一项服务进行交互，例如浏览一个网站或使用一个移动应用。我们将用户按时间顺序发出的一系列 API 请求称为一个会话。举一个熟悉的例子，客户与银行服务交互的会话可能如下所示：
| 时间顺序 | 方法 | 路径 | 描述 |
|---|---|---|---|
| 1 | POST | /api/v1/auth | 验证用户的身份 |
| 2 | GET | /api/v1/accounts/{account_id} | 显示账户余额，其中 account_id 是属于用户的账户 |
| 3 | POST | /api/v1/transferFunds | 包含请求正文，详细说明了转出账户、转入账户以及转账金额 |
我们的目标之一是，通过自动建议适用于我们的序列缓解产品的规则，强制执行期望的序列行为，从而帮助客户保护他们的 API。如果我们强制执行预期的行为，就可以防止不想要的顺序行为。在我们的例子中，期望的序列行为可能意味着 /api/v1/auth 必须始终先于 /api/v1/accounts/{account_id} 执行。
我们必须解决的一个重要挑战是，可能的会话数量会随着会话长度的增加而迅速增长。要理解为什么，我们可以考虑用户与示例银行服务交互的其他方式：例如，用户可以任何顺序执行多次转账，和/或查看多个账户的余额。假设有 3 个可能的端点，下图说明了用户与银行服务交互时可能的会话：
由于可能的会话数量庞大，建议缓解规则需要我们解决一个挑战，即从过去的会话数据中总结序列行为作为中间步骤。在我们的例子中，我们将会话中一系列连续端点（例如 /api/v1/accounts/{account_id} → /api/v1/transferFunds）称为序列。具体来说，我们需要解决的一个挑战是，创建规则所需的顺序行为并不一定仅从数量上就能明显看出：例如，/api/transferFunds 几乎总是发生在在 /api/v1/accounts/{account_id} 之后，但与序列 /api/v1/auth → /api/v1/accounts/{account_id} 相比，序列 /api/v1/accounts/{account_id} → /api/v1/transferFunds 可能相对少见。因此，如果我们仅根据数量进行总结，可能会认为序列 /api/v1/accounts/{account_id} → /api/v1/transferFunds 不重要，而实际上我们应该将其作为潜在规则挖掘出来。
从 API 会话中学习重要的序列
马尔可夫链（Markov chain） 是一种适用于序列数据的广泛建模方法 ，其中我们会话数据中每个端点的概率仅取决于先行端点的固定数量。首先，我们将展示如何将标准马尔可夫链应用于会话数据，同时指出它们的一些局限性。其次，我们将展示如何使用一种不太知名但强大的马尔可夫链来确定重要的序列。
为便于说明，我们假设我们的会话数据中有 3 个可能的端点。我们将使用字母 a 、 b 和 c 来表示这些端点：
a: /api/v1/auth
b: /api/v1/accounts/{account_id}
c: /api/v1/transferFunds
在最简单的形式下，马尔可夫链不过是一个表格，它告诉我们在知道前一个字母的情况下，下一个字母的概率。如果我们使用最简单的马尔可夫链为过去的会话数据建模，我们最终可能会得到这样的表：
| 会话中已知的先行端点 | 会话中下一个端点的估计概率 | ||
| a | b | c | |
| a | 0.10 (1555) | 0.89 (13718) | 0.01 (169) |
| b | 0.03 (9618) | 0.63 (205084) | 0.35 (113382) |
| c | 0.02 (3340) | 0.67 (109896) | 0.31 (51553) |
表 1 列出了马尔可夫链的参数，即在已知会话中前一个端点的情况下，观察到 a 、b 或 c 作为会话中下一个端点的估计概率。例如，第 3 行值为 0.67 的格表示：在已知前一个端点为 c 的情况下 ，观察到 b 作为会话中的下一个端点的估计概率为 67%，无论 c 之前是否有任何端点。因此，表中的每个条目对应于两个端点的序列。括号中的值是我们在过去的会话数据中看到每个双端点序列的次数，用于计算表中的概率。例如，值 0.01 是计算分数 169 / (1555+13718+169) 的结果。这种估计概率的方法称为最大似然估计 。
为了确定重要的序列，我们依赖于可信区间（而非最大似然估计）来估计概率。可信区间不产生单点估计（如上所述），而是表示一个合理的概率范围。这个范围反映了可用的数据量，即每行中序列出现的总数。数据越多，可信区间越窄（反映确定性程度较高），数据越少，可信区间越宽（反映确定性程度较低）。因此，根据上表中括号内的值，我们可能会获得以下可信区间（粗体条目将在下文中进一步解释）：
| 会话中已知的先行端点 | 会话中下一个端点的估计概率 | ||
| a | b | c | |
| a | 0.09-0.11 (1555) | 0.88-0.89 (13718) | 0.01-0.01 (169) |
| b | 0.03-0.03 (9618) | 0.62-0.63 (205084) | 0.34-0.35 (113382) |
| c | 0.02-0.02 (3340) | 0.66-0.67 (109896) | 0.31-0.32 (51553) |
为简洁起见，我们不会在这里演示如何手动计算出可信区间（它们涉及评估 beta 分布的分位数函数 ）。尽管如此，修订后的表格显示更多数据导致可信区间缩小：注意第一行总共出现 15442 次，而第二行总共出现 328084 次。
为了确定重要的序列，我们使用比上述稍微复杂一些的马尔可夫链。作为中间步骤，我们先考虑每个表项对应三个端点序列的情况（而不是上面提到的两个），以下是一个示例表格：
| 会话中的已知先行端点 | 会话中下一个端点的估计概率 | ||
| a | b | c | |
| aa | 0.09-0.13 (173) | 0.86-0.90 (1367) | 0.00-0.02 (13) |
| ba | 0.09-0.11 (940) | 0.88-0.90 (8552) | 0.01-0.01 (109) |
| ca | 0.09-0.12 (357) | 0.87-0.90 (2945) | 0.01-0.02 (35) |
| ab | 0.02-0.02 (272) | 0.56-0.58 (7823) | 0.40-0.42 (5604) |
| bb | 0.03-0.03 (6067) | 0.60-0.60 (122796) | 0.37-0.37 (75801) |
| cb | 0.03-0.03 (3279) | 0.68-0.68 (74449) | 0.29-0.29 (31960) |
| ac | 0.01-0.09 (6) | 0.77-0.91 (144) | 0.06-0.19 (19) |
| bc | 0.02-0.02 (2326) | 0.77-0.77 (87215) | 0.21-0.21 (23612) |
| cc | 0.02-0.02 (1008) | 0.43-0.44 (22527) | 0.54-0.55 (27919) |
表 3 再次列出观察到 a 、b 或 c 作为会话中下一个端点的估计概率，但基于已知会话中的前两个端点。也就是说，第 3 行区间值为 0.09-0.13 的格意味着，已知前两个端点为 ca 时，观察到 a 作为下一个端点的概率具有从 9% 到 13% 的可信区间，无论 ca 之前是否有任何端点。用行话来说，我们说上表代表一个二阶马尔可夫链。这是因为表中的项表示，在知道前两个端点作为上下文的情况下观察到下一个端点的概率。
作为一个特例，零阶马尔可夫链仅仅表示会话中接口的分布。我们可以将“空上下文”对应的一行的概率列表如下：
| 会话中的已知先行端点 | 会话中下一个端点的估计概率 | ||
| a | b | c | |
| 0.03-0.03 (15466) | 0.64-0.65 (328732) | 0.32-0.33 (165117) | |
请注意，表 4 中的概率并不仅仅代表会话中没有先行端点的情况。相反，概率是会话中端点出现的情况，适用于一般情况下，我们不知道前面的端点，也不管以前出现了多少个端点。
回到我们识别重要序列的任务，一种可能的方法可能是简单地使用某个固定阶数 N 的马尔可夫链。例如，如果我们将表 3 中可信区间下限的阈值设为 0.85，则总共会保留 3 个序列。另一方面，这种方法有两个值得注意的限制：
我们需要一种方法为模型阶数 N 选择合适的值。
由于模型阶保持固定，则已识别序列均具有相同的长度 N +1。
变阶马尔可夫链
变阶马尔可夫链（VOMC）是上述固定阶马尔可夫链的更强大扩展，它解决了上述限制。 VOMC 利用这样一个事实，即对于固定阶数N的马尔可夫链的某些选定值，概率表可能包括统计冗余信息：让我们比较一下上面的表 3 和表 2，并考虑表 3 中对应上下文 aa、 ba 、 ca （这 3 个上下文共享 a 作为后缀）的粗体行。
对于所有 3 个可能的下一个端点 a, b, c ，这些行给出了可信区间，这些区间与表 2 中对应上下文 a 的各自估计重叠 （也以粗体表示）。我们可以将这些重叠的区间解释为，在已知 a 为先行端点的情况下，概率估计之间不存在明显的差异 。由于 a 的先行端点是什么对下一个端点的概率没有明显影响 ，我们可以认为表 3 中的这 3 行是冗余的：我们可以通过替换成表 2 中对应于上下文 a 的行来“折叠”它们。
按所述修改表 3 的结果如下（新行以粗体表示）：
| 会话中已知的先行端点 | 会话中下一个端点的估计概率 | ||
| a | b | c | |
| a | 0.09-0.11 (1555) | 0.88-0.89 (13718) | 0.01-0.01 (169) |
| ab | 0.02-0.02 (272) | 0.56-0.58 (7823) | 0.40-0.42 (5604) |
| ac | 0.03-0.03 (6067) | 0.60-0.60 (122796) | 0.37-0.37 (75801) |
| bb | 0.03-0.03 (3279) | 0.68-0.68 (74449) | 0.29-0.29 (31960) |
| bc | 0.01-0.09 (6) | 0.77-0.91 (144) | 0.06-0.19 (19) |
| cb | 0.02-0.02 (2326) | 0.77-0.77 (87215) | 0.21-0.21 (23612) |
| cc | 0.02-0.02 (1008) | 0.43-0.44 (22527) | 0.54-0.55 (27919) |
表 5 代表一个 VOMC，因为上下文长度可变：在示例中，上下文长度为 1 和 2。由此可见，表中的条目表示长度在 2 到 3 个端点之间变化的序列，具体取决于上下文长度。对所述折叠上下文的方法进行推广，可以得到如下在离线环境中学习一种 VOMC 的算法草图：
(1) 定义 包含会话中下一个端点的估计概率的表 T ，给定会话中可选的 0, 1, 2, …, N_max 个端点。也就是说，通过连接对应于固定阶数 0, 1, 2, …, N_max 的马尔可夫链的行来形成一个表。
(2) is_modified := true
(3) DO WHILE is_modified
(4) D := T 中不是 T 中至少 1 个其他上下文后缀的所有上下文
(5) is_modified = false
(6) FOR ctx IN C
(7) IF length(ctx) > 0
(8) parent_ctx := 通过删除ctx 中最左边端点而获得的上下文。
(9) IF is_collapsible(ctx, parent_ctx)
(10) 修改 T ，丢弃 ctx
(11) is_modified = true
在以上伪代码中， length( ctx) 是上下文 ctx 的长度。在第 9 行，is_colrapsible() 涉及比较上下文 ctx 和 parent_ctx ，按照生成表 5 所描述的方式：is_colrapsible() 评估为 true，当且仅当在我们为每一个可能的下一个端点比较上下文 ctx 和 parent_ctx 时，观察到所有可信区间重叠。最大序列长度为 N_max +1 ， 其中 N_max 是某个常量。在第 4 行， 如果我们可以通过在上下文 q 前添加零个或多个端点来构成另一个上下文 p， 则 q 是 p 的后缀。 （根据这个定义，上面提到的 0 阶模型的“空上下文”是 T 中所有上下文的后缀。）上述算法草图是 Rissanen [ 1 ]和 Ron 等人首先提出的想法的一个变体。 [ 2 ]。
最后，我们将结果表 T 中的条目作为我们的重要序列。因此，应用 VOMC 的结果是一组我们认为重要的序列。然而，对于序列分析，我们认为对序列进行排名也很有用。我们通过计算一个 0.0 到 1.0 之间的“优先级分数”来做到这一点，即序列中出现的次数除以序列中最后一个端点的出现次数。因此，优先顺序分数接近 1.0 表示给定端点几乎总是在序列中的其余端点之前。通过这种方式，手动检查最高分序列就成为了在我们的序列缓解产品中创建优先规则的一种半自动启发式方法。
大规模学习序列
以上内容是我们在序列分析中使用的统计机器学习技术的高层概述。实际上，我们设计了一种高效的算法，它不需要事先的训练步骤，而是随着数据到达不断更新模型，并生成重要序列的频繁更新摘要。这种方法使我们能够克服在此博客文章中未涉及的内存成本等额外挑战。最重要的是，上述算法草图的简单实现仍会导致表中的行数（上下文）随着最大序列长度的增加而激增。我们需要解决的另一个挑战是确保我们的系统能够处理海量 API，而不会对 CPU 负载产生不利影响。我们在前期使用了一种水平可扩展的自适应采样策略，以便对海量 API 进行更激进的采样。我们的算法随后处理这些采样的 API 请求流。在客户入驻后，序列会随着时间的推移进行组装和学习，因此重要序列的当前摘要表示一个大约24小时的回顾区间。序列分析进一步将序列存储在 Clickhouse 中，并通过一个 GraphQL API 和 Cloudflare 仪表板显示它们。希望实施序列规则的客户可以使用序列分析来执行此操作。序列分析负责确保规则在 Cloudflare 的全球网络上以分布式方式共享和匹配，这是另外一个令人兴奋的话题，我们将在未来的博客文章中讨论。
下一步
现在，您已经对我们如何揭示重要的 API 请求序列有了更好的理解，请继续关注本系列后续的博客文章，我们将描述我们如何发现客户可能想要阻止的异常 API 请求序列。目前，API Gateway 客户可以通过两种方式开始：使用序列分析来探索重要的 API 请求序列，使用序列缓解来强制执行 API 请求序列。尚未购买 API Gateway 的 Enterprise 客户可在 Cloudflare 仪表板中启用 API Gateway 试用 ，或联系帐户经理。