Practical Adversarial Attacks on Stochastic Bandits via Fake Data Injection¶

会议: NeurIPS 2026
arXiv: 2505.21938
领域: 强化学习 / Reinforcement Learning
关键词: 多臂老虎机, 对抗攻击, 假数据注入, 指数级抑制, 周期性有界注入

一句话总结¶

提出了符合真实推荐与广告系统约束的“假数据注入”对抗攻击威胁模型，证明了指数级抑制原理，并设计出在奖励幅值与注入频率双重限制下仅以次线性代价即可操纵老虎机选择目标臂的攻击策略。

研究背景与动机¶

多臂老虎机（Multi-Armed Bandit, MAB）凭借在探索与利用之间的权衡能力，已成为个性化推荐、在线广告投放、临床试验及自适应路由等交互式决策系统的核心算法。然而，随着 MAB 被广泛部署于高风险的面向用户系统中，其算法对恶意操纵的脆弱性引发了高度关注。传统针对随机多臂老虎机的对抗攻击研究普遍采用“反馈扰动”（Feedback Perturbation）威胁模型，即假设攻击者在每个决策轮次均能观测到学习器选择的臂及环境生成的奖励，并在奖励返回给学习器前进行任意无界修改，从而以次线性代价迫使学习器在绝大多数轮次中选择预定的次优臂。

然而，这种经典扰动模型在实际工业系统中存在严重的脱节与不合理假设。一方面，它赋予了攻击者过高的攻击权限：在现实的电商评分或餐厅推荐平台中，没有任何外部攻击者能够无节制地拦截并篡改成千上万真实用户提交的原始反馈；在真实场景中，攻击通常以注册虚假账户、刷虚假评论或点击欺诈的形式发生，表现为向交互日志中“追加虚假样本”而非“覆写真实数据”。另一方面，传统模型又低估了攻击者的行动自由度，限制其只能修改当前被选中的臂，而虚假用户实际上可以针对系统中任意未被推荐的臂提交反馈；同时，现实系统的反馈天生具有有界性（如 1–5 星评分或 0/1 点击），无界的攻击值极易被系统规则过滤或异常检测捕获。

为了弥合理论攻击模型与工业真实威胁之间的鸿沟，本文提出了兼具现实性与约束性的“假数据注入”（Fake Data Injection）威胁模型。在此模型下，攻击者无法篡改真实用户反馈，只能向学习器的历史记录中注入有限数量、取值在合法区间内的虚假交互样本，且注入时机受到批次大小与冷却周期的严格限制。核心 idea：利用老虎机算法自身的探索机制构建非目标臂的指数级抑制原理，通过同时或周期性向非目标臂注入有界虚假低奖励样本，仅凭次线性代价与有限注入频率便能长效阻断学习器对所有非目标臂的探索。

方法详解¶

整体框架¶

在假数据注入模型中，环境包含 $K$ 个臂，每个臂 $i \in [K]$ 具有未知的均值 $\mu_i$ 且满足 $\sigma^2$-亚高斯分布。攻击者的目标是操纵学习器以 $T - o(T)$ 的高频轮次选择收益最低的臂 $K$（即目标臂），同时总攻击代价满足 $C^F(T) = \sum_{s=1}^{N^F} |r_s^F - \mu_{a_s^F}| = o(T)$。学习器作为被动日志处理系统，将接收到的合法交互与注入样本 $(a_s^F, r_s^F)$ 一并更新经验均值 $\hat{\mu}_{a_s^F}$、拉取计数 $N_{a_s^F}$，并推进内部时钟轮次 $t$。

整个攻击方案由三部分紧密衔接构成：首先是基于浓度不等式推导出的非目标臂指数级抑制引理；其次是无注入频率限制下的基线算法——同时注入（Simultaneous Injection, SI）及其有界变体 SBI 和极小注入 LI；最后是针对真实系统反作弊检测设计的周期性有界注入（Periodic Bounded Injection, PBI），通过自适应计算冷却周期 $R_i$ 和单轮批次上限 $f$，在离散时间窗内分批释放虚假数据。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["学习器在线交互与日志统计<br/>维护经验均值与拉取计数"] --> B["指数级抑制判定<br/>拉取数达到阈值且均值压制"]
    B --> C["同时注入策略 (SI/SBI)<br/>单次批量注入有界样本"]
    B --> D["周期性有界注入调度 (PBI)<br/>批次上限 f 与冷却周期 R_i"]
    C --> E["长效抑制非目标臂 UCB 索引<br/>冻结未来探索直至时域 T"]
    D --> E
    E --> F["强制学习器收敛至目标臂 K<br/>达成次线性攻击代价 o(T)"]

关键设计¶

1. 指数级抑制原理：以目标臂置信下界为基准冻结非目标臂探索

在 UCB 等基于乐观原则的算法中，若一个臂的经验均值被压得足够低，其置信区间的增长需要依赖轮次对数项 $\sqrt{\log t / N_i(t)}$ 的驱动。如果该臂当前拉取次数已经累积到一定程度，其 UCB 索引将在极长的时间内无法超过目标臂的下界基准。设目标臂在轮次 $t$ 的保守估计下界为： $$ \hat{\ell}_K(t) \triangleq \hat{\mu}_K(t) - 2\beta(N_K(t)) - 3\sigma\delta_0 $$ 其中 $\beta(N) \triangleq \sqrt{\frac{2\sigma^2}{N}\log\frac{\pi^2 K N^2}{3\delta}}$ 为经验均值与真实均值的置信半径参数。只要非目标臂 $i$ 的经验均值满足 $\hat{\mu}_i(t) \le \hat{\ell}_K(t)$，且其历史拉取次数达到 $N_i(t) \ge \lceil\log T / \delta_0^2\rceil$，则在接下来的任何轮次 $t_2 < \exp(N_i(t)\delta_0^2)$ 中，臂 $i$ 的 UCB 索引必然严格小于目标臂 $K$ 的 UCB 索引。这意味着攻击者无需在后续轮次持续干预，学习器自身的决策规则会自动阻止对臂 $i$ 的进一步探索，从而以“一次性压制”换取“指数级时长的静默”。

2. 同时有界注入设计：受限奖励下界下的精确伪造样本量计算

在实际场景中，攻击注入的奖励受限于系统边界 $[r^{\mathrm{l}}, r^{\mathrm{u}}]$，无法像传统攻击那样使用负无穷大奖励瞬间击穿经验均值。为使有界样本能够将经验均值拉低至抑制线 $\hat{\ell}_K(t)$ 以下，论文给出了温和的有界性假设：$r^{\mathrm{l}} \le \mu_K - 3\beta(1) - 3\sigma\delta_0$。当非目标臂 $i$ 被拉取达到阈值 $N_i(t) = \lceil\log T / \delta_0^2\rceil$ 时，攻击者精准计算所需注入的最小虚假样本数 $n_i$： $$ n_i = \left\lceil \frac{\hat{\mu}_i(t) - \hat{\ell}_K(t)}{\hat{\ell}_K(t) - r^{\mathrm{l}}} \cdot N_i(t) \right\rceil $$ 注入 $n_i$ 个取值为 $r^{\mathrm{l}}$ 的样本后，更新后的经验均值 $\hat{\mu}_i(t + n_i) = \frac{\hat{\mu}_i(t)N_i(t) + n_i r^{\mathrm{l}}}{N_i(t) + n_i} \le \hat{\ell}_K(t)$。理论证明表明，当选取超参数 $\delta_0 = \Theta(\sqrt{\log T})$ 时，每个非目标臂的总攻击代价被最小化为 $\widehat{\mathcal{O}}(K\sigma\sqrt{\log T})$，这一结果达到了理论下界 $\Omega(\sqrt{\log T})$。

3. 周期性有界注入调度：规避异常检测的批次受限与冷却周期优化

一次性注入大量极低分样本极易被风控系统通过突增流量检测识别。为此，PBI 算法引入了单轮最大注入样本数 $f$ 以及注入间隔冷却期 $R_i$。攻击者将总量为 $n_i$ 的假样本拆解为若干个大小为 $f$ 的批次，在第 $c$ 批次（共注入 $fc$ 个样本）注入后，非目标臂的临时经验均值更新为 $\tilde{\mu}_i(t_i(c))$。为了保证在下一次注入前学习器不会重新拉取臂 $i$，冷却周期 $R_i$ 必须满足： $$ R_i \triangleq \min_{1 \le c \le \lceil n_i / f \rceil} \frac{1}{c} \left( \exp\left( \left(\frac{\hat{\mu}_K(t) - 2\beta(N_K(t)) - \tilde{\mu}_i(t_i(c))}{3\sigma}\right)^2 (N_i(t) + fc) \right) - t \right) - f $$ 论文进一步证明，只要初始压制间隙满足 $\frac{\hat{\mu}_K(t) - 2\beta(N_K(t)) - \tilde{\mu}_i(t_i(1))}{3\sigma} > 1$，目标函数关于批次编号 $c$ 即严格单调递增，这意味着在实际计算中只需取首个批次 $c=1$ 即可解析求出最小安全冷却期 $R_i(1)$。这种自适应延迟调度机制保证了在整个离散注入过程中，非目标臂全程处于静默受抑状态。

4. 通用抑制有界框架：向汤普森采样与 $\epsilon$-贪心算法的理论拓展

为了打破针对特定 UCB 索引的局限性，论文抽象出“抑制有界”（Suppression-Bounded）算法类：若算法在任意次优臂经验均值持续低于最优臂时，其追加拉取次数存在确定性上界 $B_i(t, T, \delta)$，则该算法属于抑制有界算法。针对该类算法，只需向非目标臂注入满足下式的样本数： $$ n_i > \frac{U_i(t) - L_K(t)}{L_K(t) - a} \left( N_i^0(t) + B_i(t, T, \delta/K) \right) $$ 即可保证系统以至少 $1 - 2\delta$ 的高概率将非目标臂的总拉取数限制在次线性量级。对于汤普森采样（TS），利用高斯后验尾部界导出的偏差项 $\kappa_i^{\mathrm{TS}}(t)$，算法同样给出了定制化的 SI-TS 与 PBI-TS 注入公式，证明了假数据注入在贝叶斯老虎机算法上的普适杀伤力。

一个完整示例¶

考虑一个拥有 3 个候选电影的推荐系统（$K=3$），其中电影 3（目标臂）平均好评率最低（$\mu_3 = 0.4$），电影 1 为优质电影（$\mu_1 = 0.8$）。系统设定最大注入批次 $f=2$，评分下界 $r^{\mathrm{l}} = 0$。

监测阶段：学习器开始正常交互。当优质电影 1 被正常推荐并累积到 $N_1(t) = \lceil \log T / \delta_0^2 \rceil$ 次（例如 30 次）且经验好评率为 $\hat{\mu}_1(t) \approx 0.82$ 时，攻击者触发防御压制逻辑。
缺口计算：攻击者根据目标电影 3 当前的表现计算出保守安全下界 $\hat{\ell}_3(t) = 0.35$。此时要将电影 1 的均值从 0.82 拉低至 0.35，所需假样本总量为 $n_1 = \lceil \frac{0.82 - 0.35}{0.35 - 0} \times 30 \rceil = 41$ 个。
分批注入与冷却：系统单轮最多注入 $f=2$ 条 0 星评价。第一轮注入 2 条后，经验均值微降至 $\frac{0.82 \times 30 + 0}{32} \approx 0.769$。攻击者根据首批注入后的差距解析计算出安全冷却时间 $R_1 \approx 450$ 轮。
静默等待与持续施压：在接下来的 450 轮中，电影 1 的 UCB 估值持续低于电影 3，用户绝大部分请求被路由至电影 3；当冷却时钟到达后，攻击者在第 452 轮再次注入 2 条 0 星评价。经过多轮分散注入，电影 1 的均值最终被牢牢锁死在 0.35 以下，彻底失去被推荐的机会。

实验关键数据¶

主实验¶

实验基于 MovieLens 25M 真实电影评分数据集以及合成高斯数据集构建，选取用户交互最频繁的子矩阵（1000 用户 $\times$ 1000 电影），随机采样 $K=10$ 个臂，以互动率最低的项作为攻击目标臂。总实验轮次设置为 $T=100,000$。对比的策略包括：无界单样本注入（LI）、同时有界注入（SBI）、周期性有界注入（PBI，单轮上限 $f=5$）以及注入相同样本总量的启发式基线（Heuristic Baseline，按 $n_i / (T-t)$ 概率随机离散注入）。

攻击策略	学习器算法	约束类型	注入参数设置	目标臂拉取比例 (%)	攻击代价与收敛特征
LI (Least Injection)	UCB	无界单点注入	单样本极端负值	> 95%	总攻击代价最低，呈平坦常数级
SBI (Simultaneous Bounded)	UCB	仅奖励有界	$r^{\mathrm{l}}$ 有界，一次性注入	> 95%	攻击代价随 $T$ 呈对数级平缓增长
PBI (Periodic Bounded)	UCB	奖励与频率双重有界	$f=5$, 自适应冷却 $R_i$	> 95%	代价略低于 SBI，后期增长曲线完全平稳
Heuristic Baseline	UCB	奖励有界，随机注入	样本量同 SBI，随机离散分布	< 20% (攻击失败)	无法压制探索，未收敛至目标臂
PBI (Periodic Bounded)	Thompson Sampling	奖励与频率双重有界	$f=10$, 贝叶斯后验冷却	> 95% (20k 步后)	维持压制，代价显著低于启发式

消融实验与参数分析¶

为了探究置信参数 $\delta_0$ 对攻击代价与样本量的权衡关系，论文在合成高斯数据集（$K=10$, 均值降序排列 $\{0.9, 0.85, \dots, 0.45\}$, $\sigma=1$）上进行了参数扫描分析。

参数 $\delta_0$ 设定	触发拉取阈值 $N_i(t)$	SBI 攻击代价	PBI 攻击代价	攻击成败与抑制持续性
小 $\delta_0$ (保守型)	较高 ($\lceil\log T / \delta_0^2\rceil$ 大)	显著偏高	偏高	成功；需等待非目标臂充分探索，但抑制极稳固
推荐 $\delta_0 = \Theta(\sqrt{\log T})$	中等均衡	达到理论极小值	达到极小值	成功；在非目标臂探索次数与注入伪造代价间达成最优平衡
过大 $\delta_0$ (激进型)	极小	边际收益递减	代价重新抬头	成功；非目标臂过早注入导致单次需要抹平的置信半径过大

关键发现¶

离散时序调度的决定性作用：启发式随机注入基线（Heuristic Baseline）使用了与 SBI/PBI 完全相同数量的虚假样本和相同有界范围，甚至注入频次不低于 PBI，但最终攻击彻底失败（目标臂拉取率不足 20%）。这表明攻击的关键不仅在于“注入多少”，更在于严格依据数学推导的冷却周期 $R_i$ 进行时序锁定，防止学习器在压制生效前产生反弹拉取。
PBI 的隐蔽性与成本优势：PBI 不仅将单轮注入峰值严格限制在小数值（如 $f=5$ 或 $f=10$），有效规避了单轮流量突增检测，而且由于在时间轴上稀疏展开，部分样本在达到总时域 $T$ 时甚至无需全部注入便已完成任务，其实际攻击成本反而略低于一次性注入的 SBI。
向贝叶斯采样的稳健迁移：在针对 Thompson Sampling 的实验中，LI、SBI 和 PBI 均在约 20,000 步左右便使目标臂的选择比例突破 95%，验证了后验采样抗扰动分析的紧致性。

亮点与洞察¶

颠覆传统假设的实用威胁建模：摒弃了以往攻击文献中“每轮劫持真实用户收益”的强假设，精准刻画了黑产“注册假号注入带界伪造记录”的现实行为，填补了在线学习安全理论与真实业务风控之间的鸿沟。
指数级抑制的深刻洞见：巧妙利用了乐观探索算法（UCB）对对数项增长的依赖性，证明了只要前置拉取达到对数阈值且均值被拉低，算法在指数级轮次内都不会再回头探索该臂，从而将“持续动态扰动”降维为“离散有限次注入”。
极小代价匹配理论下界：通过精细调谐置信参数 $\delta_0 = \Theta(\sqrt{\log T})$，在有界注入条件下将总攻击代价成功收敛至 $\widehat{\mathcal{O}}(K\sigma\sqrt{\log T})$，严格匹对了文献已知的理论代价下界。

局限与展望¶

被动学习器假设：当前研究设定学习器为无防护的被动系统，未考虑系统主动部署离群点过滤、反欺诈聚类或动态截断奖励等防御手段。
仅限于单动作上下文无关老虎机：目前理论与实验聚焦于标准多臂老虎机（MAB），尚未拓展至带有高维特征的上下文老虎机（Contextual Bandits）或状态转移的强化学习（RL）任务中。
防御机制的反向设计启示：未来的防御工作应着重于探索针对拉取序列与时间间隔的臂级审计机制（Arm-level Auditing），以及结合非平稳检测来识别反常的低收益离散注入模式。

评分¶

新颖性: ⭐⭐⭐⭐⭐ (首次形式化并理论解决了面向 MAB 的有界时序受限假数据注入攻击问题)
实验充分度: ⭐⭐⭐⭐☆ (涵盖合成基准与真实 MovieLens 数据集，覆盖 UCB、TS 及多种变体消融)
写作质量: ⭐⭐⭐⭐⭐ (数学证明推导严密清晰，威胁模型与引理逻辑层层递进)
价值: ⭐⭐⭐⭐⭐ (对推荐系统与在线广告平台的安全审计和反作弊机制构建具有直接指导价值)

参数 \(\delta_0\) 设定	触发拉取阈值 \(N_i(t)\)	SBI 攻击代价	PBI 攻击代价	攻击成败与抑制持续性
小 \(\delta_0\) (保守型)	较高 (\(\lceil\log T / \delta_0^2\rceil\) 大)	显著偏高	偏高	成功；需等待非目标臂充分探索，但抑制极稳固
推荐 \(\delta_0 = \Theta(\sqrt{\log T})\)	中等均衡	达到理论极小值	达到极小值	成功；在非目标臂探索次数与注入伪造代价间达成最优平衡
过大 \(\delta_0\) (激进型)	极小	边际收益递减	代价重新抬头	成功；非目标臂过早注入导致单次需要抹平的置信半径过大