在线学习中的数据投毒防御研究
An Investigation of Data Poisoning Defenses for Online Learning
作者对在线学习数据投毒的四种防御做理论与实验分析,称 L2-norm 防御始终处于 easy regime,Slab 防御 hard regime 最宽、实践中往往最有效。
攻击为 white-box。semi-online 攻击者知道整个干净数据流,可在任意位置添加至多 K 个样本,目标是让最终模型接近目标 θ*;fully-online 攻击者只知道当前时间步之前的数据流,只能在预先指定的位置投毒,目标是最大化整个时间范围内干净样本上的损失。
- 数据投毒防御研究大多假设离线设定且缺乏严格分析,在线学习(如 OGD 增量更新)下各种防御何时有效、攻击有多快,缺乏一般性理解。
- 以 OGD 逻辑回归为学习者,在 semi-online 与 fully-online 两种威胁模型下,对 L2-norm、labeling oracle、L2-distance-to-centroid、Slab 四种过滤式防御给出 easy/hard/intermediate 三种有效性区间的理论条件,并在四个真实数据集上验证。
- 理论上 L2-norm 防御始终在 easy regime;实验中现有攻击多在理论预测的 easy regime 有效、hard regime 无效;作者称 Slab 的 hard regime 最宽,fully-online 下攻击在高维难学习任务(IMDB)上造成的在线误分类率最高。
- 作者指出的后续方向:扩展到神经网络等更复杂模型、targeted/clean-label/backdoor 等更多攻击目标,并给出可证明保证的防御(Conclusion)。实验只用 OGD 逻辑回归、四个二分类数据集,labeling oracle 防御未做实验。
- 威胁模型
- 攻击为 white-box。semi-online 攻击者知道整个干净数据流,可在任意位置添加至多 K 个样本,目标是让最终模型接近目标 θ*;fully-online 攻击者只知道当前时间步之前的数据流,只能在预先指定的位置投毒,目标是最大化整个时间范围内干净样本上的损失。防御用可行集 F 过滤样本,攻击者知道 F。
- 被测模型
- Logistic regression (OGD)L2-norm defenseL2-distance-to-centroid defenseSlab defense
- 基准
- UCI Breast CancerIMDB ReviewsMNIST 1v7FashionMNIST Bag v.s. Sandal
- 指标
- cos(θ, θ*)online classification error ratetest error rate
一项研究系统考察在线学习中的数据投毒防御,并在强威胁模型下分析四种标准防御允许或抵御快速投毒的条件。在更弱、更现实的威胁模型下,攻击能否成功取决于学习问题的“容易”程度。
深度解读
这篇论文试图解决什么问题?
在线学习下数据投毒防御何时有效缺乏严格理解,论文对四种防御在两种威胁模型下做理论与实验分析。
核心问题:在线学习场景下,常见数据投毒防御在什么条件下能抵抗或无法抵抗投毒攻击,缺乏严格的一般性理解。
- 问题场景:数据投毒指攻击者添加或修改少量训练样本,使训练出的分类器准确率降低,威胁垃圾邮件过滤、恶意软件检测、情感分析、协同过滤等应用(按作者说法)。
- 现有工作的不足:作者指出文献有两个主要局限——大多假设所有数据预先给定的离线设定,排除了增量更新和 SGD 类算法;且缺乏分析,攻击到底有多强、现有防御在什么条件下成功,缺少严格理解。
- 论文的核心思路:在在线学习(学习者用 OGD 逐样本更新)下研究投毒与防御,提出用 easy / hard / intermediate 三种 regime 刻画防御有效性:easy 指存在简单攻击能快速达到目标,hard 指任何攻击都无法成功,intermediate 介于两者之间。
- 论文的贡献:对 L2-norm、labeling oracle、L2-distance-to-centroid、Slab 四种防御给出进入各 regime 的理论条件,并在四个真实数据集上做 semi-online 与 fully-online 实验验证。
- 威胁模型:
- 攻击者目标:semi-online 下让最终模型 θ 接近目标模型 θ*(或达到高测试误差);fully-online 下最大化整个数据流上干净样本的总损失。
- 攻击者知识:两种设定均为 white-box,攻击者知道防御的可行集 F;semi-online 攻击者还知道整个干净数据流。
- 攻击者能力:semi-online 可在流中任意位置添加至多 K 个样本;fully-online 只知道当前时间步之前的流,只能在预先指定的位置投毒。
- 受害系统:使用 OGD(logistic 损失)的在线学习者,配备以可行集 F 过滤输入样本的防御机制。
有哪些相关研究?
相关工作分离线投毒攻防、在线投毒攻击、带保证的鲁棒学习三组;作者称本文是首个为在线数据投毒攻防提供理论性能保证的工作。
离线数据投毒攻击与防御
- Biggio et al. (2012)、Mei and Zhu (2015)、Muñoz-González et al. (2017)、Koh et al. (2018)、Shafahi et al. (2018)——针对 logistic 回归、SVM 和神经网络的高效投毒攻击。
- Steinhardt et al. (2017)、Li et al. (2016)——分析投毒防御,前者提出 certified defenses,后者研究协同过滤上的投毒。
- Koh et al. (2018)——提出并分析能攻破多种数据清洗防御的强投毒攻击,是与本文最接近的工作;论文指出两点区别:它是离线设定、学习者是离线经验风险最小化,且其分析关注所需投毒样本数量,而本文刻画防御何时有效。
在线数据投毒攻击
- Wang and Chaudhuri (2018)——针对多个在线目标提出高效的梯度上升攻击方法,本文的 semi-online 威胁模型即来自该工作。
- Lessard et al. (2018)——将攻击过程视为最优控制问题,用非线性优化求解;Zhang and Zhu (2019) 用强化学习近似。
- Ma et al. (2018)、Alfeld et al. (2016)——分别研究 contextual bandits 和自回归模型上的在线投毒。
带保证的鲁棒学习与投毒上界
- Mahloujifar et al. (2017, 2018)——给出毒化在线与离线学习者所需投毒点数的上界;论文指出其不考虑具体防御,且结果只对特定分布类成立。
- Diakonikolas et al. (2018b)——提出对投毒有可证明保证的凸优化算法;论文指出其在离线设定且需要预先知道数据。Diakonikolas et al. (2016, 2017, 2018a) 的异常检测工作主要在无监督设定。
基线与基准:实验用四个基线攻击——Simplistic(本文提出)、Greedy(Liu et al., 2017a)、Semi-Online-WK(Wang and Chaudhuri, 2018)、Concentrated(Koh et al., 2018,离线攻击改造);数据集为 UCI Breast Cancer、IMDB Reviews、MNIST 1v7、FashionMNIST Bag v.s. Sandal。
作者定位:在线投毒的防御侧此前缺乏理解,作者称本文是首个为在线数据投毒的攻击与防御提供理论性能保证的工作。
论文如何解决这个问题?
以 OGD 逻辑回归为学习者,用可行集 F 形式化四种过滤防御,理论刻画 easy/hard/intermediate 三 regime 的条件,再用实验验证。
整体思路:把防御形式化为对输入样本的可行集过滤,分析一个简单攻击算法 Simplistic Attack 在各防御下能否快速把模型推向目标 θ*,据此把防御划入三种有效性 regime,并在 semi-online 与 fully-online 两种威胁模型下分别做理论分析和真实数据实验。
问题设定与形式化
- 学习者为 OGD:θt+1 = θt − η ∇ ℓ(θt, xt, yt),本文使用 logistic 损失的二分类逻辑回归。
- 防御由可行集 F 刻画:样本 (x, y) ∈ F 才用于更新,否则被过滤;攻击者在 white-box 假设下知道 F。
- Data Poisoner(Definition 3.1):给定 θ0、S、K、F、θ、ε,攻击成功当且仅当插入至多 K 个 F 内的样本后,OGD 输出的 θ 满足 ‖θ − θ‖ ≤ ε。
Simplistic Attack 与三种 regime
- Simplistic Attack(Algorithm 1)迭代地向干净流末尾追加投毒点,方向取 θ* − θ̃0,幅度自适应且 L2 范数不超过 R,并带一个投影步骤保证投毒点落在 F 内;算法受 iterative machine teaching(Liu et al., 2017a)启发。
- 三种 regime:easy 指 Simplistic Attack 等小 K 即可成功;hard 指任何 K 的任何攻击都无法输出 θ*;intermediate 指攻击可能存在但不简单、不快。
四种防御的理论条件
- L2-norm 防御(F = {‖x‖2 ≤ R}):Theorem 3.2 证明当 K > C·log(λ/ε) 时 Simplistic Attack 成功,即该防御永远在 easy regime;常数 C 随 R 减小而增大,R 小时约为 O(1/ηR)。
- Labeling oracle 防御(攻击者只能提供无标签样本,由标注函数 g 打标,F = {‖x‖ ≤ R, y = g(x)}):Theorem 3.3 给出两个条件——若 F 的单侧形式 F′ 包含原点到 θ* − θ̃0 方向的线段,则攻击快速成功(easy);若 F′ 被某个不含 θ* − θ0 方向任何点的凸集 G 包含,则任何攻击都不可能成功(hard);中间情形在附录 A.4 用三个例子说明攻击可从快速、慢(指数级点数)到不可能。
- L2-distance-to-centroid 防御(按到类中心 μy 的距离打分,阈值 τ 过滤):Lemma 3.4——τ > min(‖μ+‖, ‖μ−‖) 时攻击快速成功;τ 小且类中心与 θ* − θ0 方向满足内积条件时任何攻击不可能成功。
- Slab 防御(按 |(μ+ − μ−)ᵀ(x − μy)| 打分,阈值 τ):Lemma 3.5 给出类似的快速成功与不可能成功的条件,条件用 β = μ+ − μ− 与 b+ = −βᵀμ+、b− = βᵀμ− 表示。
- 数据驱动防御假设防御方用攻击者无法污染的干净初始化集构建过滤规则,攻击者知道防御机制与参数但无法改变它。
Fully-online 分析与实验设计
- 理论上用两个对比例子说明 fully-online 攻击成败取决于学习任务的"难易":Lemma 4.1(一维、类完全可分)中攻击者造成的干净样本误分类不超过投毒点占比 10%;Lemma 4.2(d = 10,000 的高维任务)中攻击者能以超过 0.99 的概率使前 1,000,000 个干净样本中 ≥50% 被误分类。
- 实验:semi-online 下用 cos(θ, θ*) 衡量攻击速度,对三种防御各取 10 个 τ 值(对应干净流上 10i 百分位);fully-online 下以 semi-online 攻击为子例程构造攻击者,投毒位置均匀随机、占流长 10%,用整个时间范围上的在线分类错误率衡量效果,τ 取保留 30%/50%/70%/90%/100% 干净样本的五档。
论文做了哪些实验?
四个数据集、三种防御、四个基线攻击:实验与理论预测基本吻合,作者称 Slab 防御最宽 hard regime、fully-online 下也最有效。
实验设置
- 学习者:OGD + logistic 回归,θ0 = 0;学习率 η = 0.05(Breast Cancer)、0.01(其余三个数据集),附加实验用 η = 1。
- 数据集:UCI Breast Cancer(d = 9,初始化/训练/测试 = 100/400/100)、IMDB Reviews(Doc2Vec 特征 d = 100,5000/10000/5000)、MNIST 1v7(d = 784,1000/8000/1000)、FashionMNIST Bag v.s. Sandal(d = 784,1000/8000/1000)(附录 B.1)。
- 防御:L2-norm、L2-distance-to-centroid、Slab;labeling oracle 防御因缺乏合适标注函数未做实验。
- 基线攻击:Simplistic、Greedy、Semi-Online-WK、Concentrated(离线攻击改造,附录 B.2);投毒点追加在干净流末尾。
- semi-online 协议:目标 θ* = −θ̃0(θ̃0 为干净流上学得的模型),投毒预算 K = 80(Breast Cancer)/100(MNIST、FashionMNIST)/200(IMDB),指标为 cos(θ, θ*),每个防御取 10 个 τ 值。
- fully-online 协议:流长 T = 400(Breast Cancer)/1000(其余),投毒位置均匀随机、|I| = 0.1T(附录另有 0.2T),指标为整个时间范围干净样本上的在线分类错误率,τ 取保留 30%/50%/70%/90%/100% 干净样本的五档。
主结果
主结果以图呈现(Figure 2、Figure 3),坐标轴为防御参数 τ 与 cos(θ, θ*) 或在线分类错误率,转换文本未含图中数值,以下按正文转述:
维度 结果(据 5.3 节与图注) 攻击有效性 Simplistic、Greedy、Semi-Online-WK 的 cos(θ, θ*) 随 τ 增大而上升,多数情况下大 τ 时接近 1;Concentrated 无效;Semi-Online-WK 通常最好 regime 验证 多数数据集 × 防御组合中,理论预测的 easy regime 内攻击快速、hard regime 内无攻击有效;边界与理论预测不完全一致 防御比较(semi-online) L2-norm 始终在 easy regime;作者称 Slab 的 hard regime 最宽,可行集保留 70%–80% 干净样本时仍处于 hard regime 防御比较(fully-online) 作者称 Slab 在所有数据集上最有效,L2-norm 最弱;L2-distance-to-centroid 在 BreastCancer、MNIST、FashionMNIST 上优于 L2-norm,在 IMDB 上不然 跨数据集 在线分类错误率 IMDB 最高、BreastCancer 最低,MNIST 与 FashionMNIST 居中 τ 选择 最低在线错误率多出现在保留 70% 或 90% 样本的 τ - 作者解读:理论下界中的常数 C 随 τ 减小而增大,因此小 τ 时固定预算内攻击变慢,这解释了边界偏差;附录 B.3 显示 η = 1 时(C 变小)小 τ 的 easy regime 内攻击者仍能使 cos(θ, θ*) 接近 1。
- 作者认为跨数据集结果印证了任务难度的影响:BreastCancer 低维易学,投毒效果被干净样本学习抵消;IMDB 高维难学,弱防御下投毒比学习快,攻击造成的在线误分类可超过投毒样本占比。
附加实验:大学习率与测试错误率(附录 B.3)
- 测了什么:semi-online 下最终模型 θ 在干净测试集上的错误率(Figure 4),以及 η = 1 时的 cos(θ, θ*) 与测试错误率(Figure 5、6)。
- 结果:测试错误率趋势与 cos(θ, θ) 一致——hard regime 内低、easy regime 大 τ 时高;η = 1 时小 τ 的 easy regime 内攻击也能使 θ 接近 θ,hard regime 内仍不能。
- 作者解读:这验证了"小 τ 攻击变慢是常数 C 增大所致"的解释。
附加实验:20% 投毒比例的 fully-online 攻击(附录 B.3)
- 测了什么:投毒占比 |I| = 0.2T 的更强 fully-online 攻击下的在线分类错误率(Figure 7)。
- 结果:趋势与 10% 时相似;L2-norm 防御下错误率高,Slab 仍保持低错误率,L2-distance-to-centroid 居中且通常能把错误率压在投毒占比之下;四个数据集的投毒难度排序不变(BreastCancer 最难、IMDB 最易)。
其他消融与分析
- Concentrated 攻击的标签预算分配:尝试全 +1、各半、全 −1 三种,报告效果最好者(附录 B.2)。
- Concentrated 的投毒顺序:正类在前、负类在前、随机(试 100 种随机顺序),报告效果最好者(附录 B.2)。
- 理论边界用初始化集计算,以红(hard)、蓝(easy)背景标注在 Figure 2 中。
有什么可以进一步探索的点?
作者在 Conclusion 列出扩展方向:更复杂模型、更多攻击目标、可证明保证的防御;实验仅覆盖 OGD 逻辑回归与四个二分类数据集。
作者指出的局限与后续方向
- 扩展到更复杂的模型,如神经网络(Conclusion)。
- 扩展到更多攻击目标:针对特定测试样本的 targeted attack、clean-label stealthy attack、backdoor attack(Conclusion)。
- 为每种情形提供带可证明保证的防御(Conclusion)。
- labeling oracle 防御未纳入实验,因为缺乏适用于所用真实任务的标注函数(Section 5 脚注 3)。
实验覆盖范围
- 学习者仅为 OGD + logistic 回归的二分类;被测防御为 L2-norm、L2-distance-to-centroid、Slab 三种。
- 数据集为 UCI Breast Cancer、IMDB Reviews、MNIST 1v7、FashionMNIST Bag v.s. Sandal 四个二分类任务,维度 9 到 784。
- semi-online 投毒预算 K 为 80/100/200(按数据集),fully-online 投毒占比为 10%(附录另有 20%),流长 400 或 1000。
- 基线攻击为 Simplistic、Greedy、Semi-Online-WK、Concentrated 四种;论文指出已有 fully-online 攻击方法(Wang and Chaudhuri, 2018;Zhang and Zhu, 2019)对高维数据和长时间范围计算代价过高或需要知道整个干净流,因此未用作基线。
- 论文未报告实验的重复次数与方差;主结果以 Figure 2、3 的曲线呈现,正文未给出具体数值。
总结一下论文的主要内容
在线学习投毒防御的理论与实验研究:L2-norm 防御始终易攻破,Slab 防御 hard regime 最宽,fully-online 攻击成败取决于任务难易。
一篇关于在线学习数据投毒防御的理论加实验研究,针对此前文献偏重离线设定、缺乏严格分析的问题。
- 问题:在线学习(OGD 逐样本更新)下,攻击者向数据流插入少量投毒样本,常见过滤式防御何时能抵抗、何时被快速攻破,此前缺乏一般性理解。
- 方法:把防御形式化为可行集 F 过滤,提出 Simplistic Attack 作为试金石,把防御有效性分为 easy / hard / intermediate 三种 regime;在 semi-online(攻击者知道整条流、任意位置投毒、目标是最终模型)和 fully-online(只知道历史、指定位置投毒、目标是全程损失)两种 white-box 威胁模型下分析。
- 理论结果:L2-norm 防御始终在 easy regime,K > C·log(λ/ε) 即可攻破(Theorem 3.2);labeling oracle、L2-distance-to-centroid、Slab 三种防御各有进入 easy 与 hard regime 的明确条件(Theorem 3.3、Lemma 3.4、3.5);fully-online 下,一维可分任务中攻击者造成的误分类不超过投毒占比 10%(Lemma 4.1),而 d = 10,000 的任务中能以超过 0.99 的概率使 ≥50% 干净样本误分类(Lemma 4.2)。
- 实验结果:四个真实数据集上,现有攻击多在理论预测的 easy regime 内有效、hard regime 内无效;作者称 Slab 的 hard regime 最宽(保留 70%–80% 干净样本时仍 hard),fully-online 下也最有效;在线错误率 IMDB 最高、BreastCancer 最低,与任务难度一致;最低错误率多出现在保留 70% 或 90% 样本的 τ。
- 作者的结论:Slab 防御在实践中往往高度有效;对难分类问题,较弱的威胁模型仍能产生相当强的攻击,投毒对弱攻击者也是威胁;后续计划扩展到神经网络、更多攻击目标和可证明保证的防御。