Rethinking Byzantine Robustness in Federated Recommendation from Sparse Aggregation Perspective

作者：张中健，张梦玫，王啸，吕灵娟，闫博，杜军平，石川

单位：北京邮电大学，中国电信翼支付，北京航空航天大学，Sony AI

摘要：为了保护推荐系统中的用户隐私，基于联邦学习（Federated Learning, FL）的联邦推荐（Federated Recommendation, FR）应运而生，其将用户的个人数据保留在本地客户端，并通过协作更新一个全局模型。与FL不同，FR具有独特的稀疏聚合机制，其中每个物品的嵌入仅由部分客户端更新，而不是像通用FL中的密集聚合那样由所有客户端更新。近年来，模型安全性作为FL的一个重要原则，受到越来越多的关注，特别是针对拜占庭攻击（Byzantine attacks），即恶意客户端可以发送任意更新。探索FR的拜占庭鲁棒性问题尤为关键，因为在应用FR的领域（如电子商务）中，恶意客户端可以通过注册新账户轻松注入。然而，现有的拜占庭攻击研究忽略了FR独特的稀疏聚合机制，使其无法适用于我们的问题。因此，我们首次从稀疏聚合的角度研究FR中的拜占庭攻击，这一研究并非易事：在稀疏聚合下如何定义拜占庭鲁棒性以及在有限知识/能力下设计拜占庭攻击尚不明确。本文中，我们重新定义了稀疏聚合下的拜占庭鲁棒性，将单个物品的聚合作为最小执行单元。随后，我们提出了一系列有效的攻击策略，命名为Spattack，这些策略利用了稀疏聚合的脆弱性，并按照攻击者的知识和能力进行分类。大量实验结果表明，Spattack可以有效阻止模型收敛，甚至在少量恶意客户端的情况下攻破防御机制，为FR系统的安全性敲响了警钟。

1. 引言

作为缓解信息过载的重要方式，推荐系统被广泛应用于电子商务、媒体和社交网络等领域，为用户推荐可能感兴趣的物品。尽管取得了显著的成功，传统推荐系统需要集中存储用户的个人数据以进行训练，这增加了隐私风险。近年来，联邦学习（Federated Learning, FL）作为一种隐私保护的范式逐渐兴起，并成功应用于推荐领域。在联邦推荐（Federated Recommendation, FR）中，全局的物品嵌入会被上传到中央服务器进行聚合。同时，每个用户的交互数据和隐私特征则保留在本地客户端。通过这种方式，本地数据的隐私得到了良好的保护。

与一般的联邦学习（FL）系统不同，联邦推荐（FR）具有独特的稀疏聚合机制。如图1所示，对于一般FL系统，模型参数的每个元素（圆形）都可以由所有个客户端更新，这被称为密集聚合。而在FR中，用户与物品的交互通常是稀疏的，导致每个物品的嵌入只能由部分客户端更新。例如，客户端只能为其交互的物品生成并发送有意义的梯度。对于其余物品，更新为零向量或空值，这种机制被称为稀疏聚合。

图1：一般联邦学习（FL）的密集聚合与联邦推荐（FR）独特的稀疏聚合对比。

迄今为止，FR在无需收集用户隐私数据的情况下已经取得了令人满意的性能，将推荐应用扩展到对隐私敏感的场景中。尽管取得了成功，模型安全性作为一项重要原则，已受到越来越多的关注。本文考虑最恶劣的攻击情况，即拜占庭攻击（Byzantine attack），其中攻击者可以是全知且合谋的，并能控制多个客户端上传任意恶意梯度。需要注意的是，拜占庭鲁棒性对于FR尤为重要，因为在应用FR的领域（例如电子商务）中，恶意客户端可以通过注册新账户轻松注入。这自然引出了一个问题：在稀疏聚合的机制下，联邦推荐模型在面对拜占庭攻击时的鲁棒性如何？

对于这一问题，现有的拜占庭攻击研究无法直接应用，因为它们主要集中于一般联邦学习（FL）中的密集聚合机制。尽管已有少量针对联邦推荐（FR）的攻击研究出现，但它们同样忽视了稀疏聚合如何影响FR的鲁棒性。我们通过解决以下两个挑战回答这一问题：（1）如何在稀疏聚合下定义拜占庭鲁棒性？现有的拜占庭攻击与防御主要基于一般FL中的密集聚合机制定义。在FR中，由于用户与物品的交互是稀疏的，对于某一物品，其嵌入仅由与其交互的用户更新，未交互的用户上传的是零值或空值更新。因此，若直接应用现有的密集聚合方法，聚合后的物品嵌入可能会偏向零值更新，因为零值更新占多数。因此，将这些方法迁移到FR中并重新审视其理论保障和有效性显得尤为重要。（2）如何针对具有不同知识和能力水平的攻击者设计通用的FR拜占庭攻击？在实际场景中，由于FR参与用户数量庞大，很难全面了解所有用户的情况。此外，由于用户与物品的交互通常是稀疏的，拜占庭客户端不应更新过多物品。否则，当进行激进的修改时，基于用户交互数量的监控机制可能会被轻易触发。

在本文中，我们首次从稀疏聚合的视角研究了联邦推荐（FR）的拜占庭鲁棒性问题。针对第一个挑战，我们通过将单个物品的聚合作为最小执行单元，将现有的聚合方法迁移到FR中。具体来说，对于每个物品嵌入，其梯度分别被单独聚合且并行处理。在此基础上，我们进一步指出，FR的稀疏聚合机制会导致一种独特的拜占庭漏洞：不同度数的物品接收到的更新次数不同，从而导致个体鲁棒性的差异。在现实中，所有物品的度数通常遵循长尾分布，其中大多数物品（称为长尾物品）仅与少数用户交互，使其极为脆弱。针对第二个挑战，我们基于FR中稀疏聚合的漏洞设计了一系列攻击策略，称为Spattack。然后，我们根据攻击者的知识和能力将这些策略划分为四类。具体而言，我们考虑了全知攻击者（Spattack-O）和受限的非全知攻击者（Spattack-L），同时根据是否限制每个客户端的最大投毒物品数量，我们进一步对其进行划分。总结而言，我们的贡献主要体现在以下三点：

我们首次从稀疏聚合的独特视角系统性地研究了FR的拜占庭鲁棒性问题，将单个物品的聚合作为最小执行单元。我们对其收敛性保障进行了理论分析，并指出了FR的一种特殊漏洞。
我们提出了一系列有效的攻击策略，命名为Spattack，利用稀疏聚合中的漏洞。Spattack可根据攻击者的知识和能力分为四种不同类型。
我们在多个基准数据集上对不同的FR系统进行了实验。结果表明，Spattack仅通过控制少量恶意客户端，就能阻止普通FR模型甚至防御模型的收敛。

2. 背景与预备知识

2.1 集中式推荐

推荐系统包含一组用户和一组物品，其中和分别表示用户和物品的数量。每个用户拥有一个由隐式反馈元组组成的本地训练数据集。这些元组表示用户与物品的交互（例如购买、点击），其中和分别表示正样本和负样本，即是否与是否发生交互。对于每个用户，我们定义为与交互的物品集合。用和分别表示用户和物品的嵌入。推荐系统被训练以预测用户和物品之间的评分，其中表示对的偏好程度，是评分函数，为可学习参数。推荐系统通过对评分进行排序，为每位用户推荐一个可能感兴趣的物品列表。在传统的集中式训练中，每个用户的个人数据集被存储在中央服务器上，形成用于模型训练的完整数据集，这将增加用户隐私风险。

2.2 联邦推荐

考虑到隐私问题，在联邦推荐（FR）中，用户的隐私数据保留在本地设备上。共享的模型参数和通过将本地梯度发送到中央服务器来在客户端间聚合。不同的推荐模型，参数的定义有所不同：在矩阵分解（Matrix Factorization, MF）推荐模型中，交互函数是固定的，是空集；而在基于深度学习的推荐模型中，是神经网络的权重集合。为了简化问题，我们采用经典且广泛使用的MF作为基础推荐模型，其中固定为点积函数，即。同时，我们采用贝叶斯个性化排序（Bayesian Personalized Ranking, BPR）作为每个客户端的本地损失函数，这是一种基于成对比较的个性化排序损失，其定义如下：

其中是逻辑 sigmoid 函数。该损失函数假设用户更偏好正样本物品而非负样本物品。在每次训练迭代中，中央服务器将当前的物品嵌入发送给所有客户端。对于每个用户，客户端计算损失，然后在本地更新其第轮的用户嵌入：

其中是学习率。随后，用户上传其本地的物品嵌入梯度到中央服务器。服务器在收集所有客户端的梯度后，通过以下方式更新：

如图1(b)所示，对于每个用户，其私有的交互历史（物品列表）和用户嵌入（绿色向量）保存在本地客户端设备上，仅发送物品嵌入的梯度。在整个训练过程中，所有用户的隐私均得到了良好的保护。

2.3 拜占庭攻击与防御

拜占庭攻击：在拜占庭攻击中，攻击者通过控制少量恶意客户端，旨在降低模型性能，甚至阻止模型收敛。如图2(a)所示，恶意客户端可以发送任意（红色）梯度。根据现有的拜占庭攻击研究，在最坏的情况下，我们假设攻击者完全了解所有正常梯度，并默认所有恶意客户端是合谋的，此假设也有助于理解模型中毒威胁的严重性。

拜占庭防御：由于服务器无法访问客户端的原始训练数据，防御通常在服务器端以鲁棒聚合器的形式实现，用于过滤拜占庭更新并保证模型收敛。如图2(a)所示，设为联邦学习（FL）中个正常客户端的梯度向量。服务器通过联邦聚合器收集并聚合每个客户端模型的训练梯度。在不鲁棒FL设置中，逐坐标均值（Mean）聚合是一种有效的聚合规则。然而，容易被少量恶意客户端操控。因此，许多用于过滤拜占庭更新的鲁棒聚合器被提出。例如，逐坐标中位数（Median）聚合器计算参数中每个元素的中位数，具有 0.5 的抗击穿点。也就是说，当恶意客户端的比例低于 0.5 时，中位数聚合器可以在拜占庭攻击下保证模型的收敛，如图2(a) 中的绿色星标所示，最终得到正确的梯度。

图2：一般联邦学习（FL）和联邦推荐（FR）中拜占庭鲁棒性的分析。在拜占庭攻击下，鲁棒聚合器可以在一般FL中过滤异常值，但无法有效防御长尾物品嵌入的攻击。

3. 方法

3.1 问题定义

对于拜占庭攻击，攻击者可以注入一些拜占庭用户，并将恶意用户的比例限制在以下，即。恶意客户端可以在任意时刻上传任意梯度值，以直接扰乱物品嵌入。服务器将收集并聚合包括正常梯度和恶意梯度在内的所有梯度。设为联邦学习的聚合操作符，可以是常见的或统计鲁棒的。拜占庭攻击的目标是阻止模型收敛，即保持推荐损失不下降。

在FR中，拜占庭攻击的目标可以形式化为以下优化问题：

其中，攻击者的目标是找到一组最优的恶意梯度，以在更新后提高损失。在解决此优化问题之前，我们发现FR具有一种独特的稀疏聚合机制，其定义如下：

定义1. 密集/稀疏聚合。 设为共享的模型参数向量。如果存在某个元素 ()，只有部分客户端能够生成有意义的更新，则参数是稀疏聚合的；如果所有客户端均能参与更新，则为密集聚合。

如图2(a)所示，在一般FL中，模型参数的每个元素（绿色圆圈）假设都会参与所有客户端的损失函数，即密集聚合。而在FR中，对于客户端，并非所有物品嵌入都会用于本地损失，即为稀疏聚合。例如，图2(b) 中的客户端仅计算物品和的有效梯度，而其余物品的梯度为零或空值。如果直接将聚合器应用于所有，嵌入可能会偏向零值。因此，我们需要对其进行适配以适应FR。

将密集聚合器适配为稀疏聚合器。我们通过将单个物品的聚合作为最小执行单元，将现有的聚合器从密集聚合适配为稀疏聚合。如图2(b)所示，聚合器对每个物品单独执行。以第个物品的嵌入为例，其更新方式为：

其中，是与物品交互的用户集合，是客户端在第时刻上传的物品的梯度。只有当用户与物品有交互时，其梯度才能被单独且并行地聚合到中。直观上，不同物品接收到的梯度数量各不相同，导致每个物品具有个体化的鲁棒性。因此，我们需要从理论上重新审视现有聚合器在稀疏聚合下对抗拜占庭攻击的收敛性保障。

3.2 拜占庭鲁棒性分析

无防御情况下FR的鲁棒性。与一般联邦学习（FL）类似，无防御的联邦推荐（FR）通常使用均值聚合器（Mean aggregator）来计算输入梯度的平均值，但这对拜占庭攻击高度敏感。正如命题1所述，即使只有一个恶意客户端，也可能破坏均值聚合器。

命题 1. 对于每个物品，设为第轮中的正常梯度集合，均值聚合器用于对每个元素的更新求平均值。设为一个任意值的恶意梯度，聚合器的输出值能被单个恶意梯度控制为零向量。若所有物品均受到攻击，一个恶意客户端即可阻止模型收敛。证明：如果攻击者注册了一个恶意客户端，并设置每个物品的嵌入梯度为，则聚合器的输出为零向量，从而阻止模型收敛。

有防御情况下FR的鲁棒性。最常见的防御方法是使用比均值更能对抗异常值的统计鲁棒聚合器。在这些防御中，FL模型通常具有较高的抗击穿点。例如，当时，中位数聚合器（Median）理论上可保证FL模型的收敛。然而，我们发现FR模型的抗击穿点因物品的度数而异。具体来说，每个物品嵌入仅能由与该物品交互的特定客户端更新。显然，交互频繁的热门物品（head items）因拥有大量更新而更具鲁棒性。然而，在FR中，只有少数物品是热门物品，而大多数物品是交互较少的长尾物品（tailed items）。我们绘制了Steam推荐数据集中物品的受欢迎度（物品度数）分布（见图2(c)）。结果显示，97% 的长尾物品（红色长尾区域）交互次数少于200次，只有3% 的热门物品（绿色区域）交互频繁，超过200次。因此，基于统计的FL防御方法无法保证大多数物品的收敛。形式化地，设为物品的度数，为其概率分布。我们假设该概率分布为典型的幂律分布，其中是归一化常数，是缩放参数。防御失败的情况可表述如下：

命题 2. 设为鲁棒联邦聚合器的抗击穿点，正常客户端和恶意客户端的数量分别为和，物品度数的幂律分布缩放参数为，归一化常数为。则至少有比例的物品嵌入将被破坏。

命题2 的证明请参见原始论文附录。以Steam数据集为例，其物品度数分布可建模为典型的幂律分布（见图2(c)）。例如，如果攻击者可控制的客户端，每个物品最多可接收到197个恶意梯度。显然，对于97% 交互次数少于200次的长尾物品，少量恶意（红色）更新即可成为多数并主导聚合。在这种情况下，统计鲁棒的中位数聚合器将选择多数值（红色圆圈），输出恶意结果（红色星标）。总之，由于FR的稀疏聚合漏洞，FL中的统计鲁棒聚合器也能被拜占庭攻击者轻易破坏。

3.3 Spattack：拜占庭攻击策略

攻击直觉： 在问题定义的公式4中，攻击者的目标是阻止推荐损失下降，从而阻碍推荐模型的收敛。考虑稀疏聚合中的独特漏洞，即大多数长尾物品具有较低的抗击穿点，可以得出以下结论：（1）梯度越偏离真实梯度，破坏效果越显著。（2）训练过程中被干扰的物品越多，攻击效果越强。因此，我们提出的 Spattack 攻击目标可以简化为：尽可能上传远离真实梯度的恶意梯度，并通过贪婪策略干扰更多物品的嵌入。

攻击分类：在实际场景中，根据攻击者对正常梯度的了解程度以及每个恶意客户端中被污染物品的最大数量，我们概述了可以发起的 Spattack 的不同方案。正如表1所示，我们有四种可能的情况：

Spattack-O-D 被认为是最坏的情况，其中攻击者既是全知的又是全能的，即攻击者可以在每个训练轮次获取正常的梯度，并且每个恶意客户端中被污染物品的最大数量没有限制。根据第一个直觉，即恶意梯度越远离真实梯度，造成的破坏越大，攻击者上传与正常梯度相反方向的梯度。形式上，对于一个物品，我们从与交互的用户收集正常梯度，即。然后，我们计算收集到的正常梯度的总和，得到期望梯度。最后，每个恶意客户端将上传恶意梯度。根据第二个直觉，即贪婪地干扰物品，通过对所有物品上传中毒梯度，可以最大化攻击效果。在这种攻击中，不鲁棒的均值聚合器将输出零梯度，而统计鲁棒的聚合器将为大多数长尾物品选择恶意梯度，阻止物品嵌入的收敛。根据命题1 和命题2，即使只有一小部分恶意客户端，Spattack-O-D 就能确保破坏大多数物品的嵌入。

Spattack-L-D 对所有物品上传随机噪声作为恶意梯度，其中攻击者是非全知但全能的，即攻击者对正常梯度没有任何了解，但可以攻击所有物品。具体来说，攻击者通过从高斯噪声中随机采样来构造恶意梯度，并在所有恶意客户端中保持相同的噪声。在均值聚合器下，聚合的梯度可能被这些噪声所偏斜。更糟糕的是，统计鲁棒的聚合器（如中位数）可能会选择上传的随机噪声作为长尾物品的输出。因此，这种攻击仍然可以阻止模型收敛。

Spattack-O-S 和 Spattack-L-S 仅对部分物品上传恶意梯度，其中攻击者不是全能的。设为每个恶意客户端中被污染物品的最大数量。越大，攻击越强，但过大的可能导致攻击被检测到。为了限制恶意用户的行为类似于正常用户，我们将限制为正常客户端中的最大交互数量。具体来说，为了使恶意客户端的注入尽可能难以察觉且有效，我们基于物品受欢迎度的分布，使用采样操作来确定每个恶意客户端的被污染物品。因此，攻击者可以自动为交互更多的物品分配更多的恶意梯度。然后，我们分别基于相反的正常梯度（Spattack-O-S）或随机噪声（Spattack-L-S）生成恶意梯度。

4. 实验

4.1 与现有的拜占庭攻击相比，Spattack 的表现如何？

我们在 3% 恶意客户端比例下，将 Spattack 与现有最先进的攻击基线进行了比较。实验结果见表3，主要发现如下：（1）Spattack 能通过控制少量恶意客户端阻止 FR 收敛。整体上看，Spattack 可导致 47%-98% 的性能下降，表明 FR 对 Spattack 极其脆弱。（2）Spattack 显著优于其他基线方法。其原因在于 Spattack 充分利用了稀疏聚合的漏洞，通过贪婪地破坏更多物品实现更强的攻击效果。具体来说，LabelFlip 和 FedAttack 仅通过修改数据间接操控梯度，而 LIE、Cluster 和 Fang 直接操控梯度，因此能够产生更高的攻击影响。尽管 Fang 也通过扰动正常梯度的相反方向进行攻击，但由于未考虑 FR 的稀疏聚合，其恶意梯度偏向零向量，导致攻击效果较差。（3）Steam 数据集的结果整体比 ML100K 和 ML1M 降幅更大。一个可能的原因是 Steam 数据集的平均交互次数较少，意味着存在更多长尾物品，这使得模型对攻击更易受影响。

4.2 Spattack 能否打破部署在联邦推荐系统上的防御？

我们还评估了 Spattack 在不同防御机制下的有效性。对于全知的 Spattack-O，我们将恶意比例设置为 1%、3% 和 5%；对于更难的非全知 Spattack-L，我们将比例设置为更高的 5%、10% 和 15%。我们为所有攻击配置了均值（Mean）、中位数（Median）和范数（Norm）聚合器。由于 TrimM 和 Krum 假设每个物品的恶意更新数量固定，而 Spattack-O/L-S 对每个物品上传不同数量的更新，这使得它们无法应用。如图3所示，我们发现：（1）仅有 5% 的恶意客户端，Spattack 即可显著降低推荐性能，甚至阻止模型收敛。其原因在于不同物品接收到的更新数量各不相同，长尾物品的防御比热门物品更容易被打破。（2）当攻击者的知识和能力受限时，随着恶意比例的增加，防御 FR 的性能持续下降，甚至接近未训练模型的水平。结果还表明，隐藏正常客户端的梯度无法保护 FR，因为攻击者仅通过随机噪声即可打破防御机制。

5. 总结

在本文中，我们首次从稀疏聚合的视角系统性地研究了联邦推荐系统（FR）的拜占庭鲁棒性。在FR中，物品嵌入仅能由部分客户端更新，而非像一般联邦学习（FL）中的密集聚合那样由所有客户端更新。随后，我们基于FR中稀疏聚合的漏洞设计了一系列攻击策略，称为 Spattack。Spattack 可由具有不同知识水平和能力的攻击者使用。大量实验结果表明，FR 对 Spattack 非常脆弱。未来，我们计划从稀疏聚合的视角设计更加鲁棒的聚合器，重点关注针对长尾物品的鲁棒聚合机制。