这篇文章发表于 2018 年，是第一篇针对线性回归模型提出投毒攻击方法的论文，实验证明：这种gradient-based的攻击方法效果很好；同时这篇文章里面也提出了一种防御方法：TRIM，实验结果也证明其防御效果很好。
主要贡献
- 第一篇针对
linear regression进行poisoning attack的论文，之前的论文都是针对classification的模型 - 改造了一个原本针对分类问题进行投毒攻击的模型，将其应用在回归问题中，将攻击结果作为一个
baseline - 提出了一种基于数据集统计特征的攻击方法，只需要掌握有限的信息即可完成攻击
- 提出了防御算法
TRIM,能够抵御众多的攻击，效果比传统的robust statistic好
方法
Linear Regression Model
传统的线性回归模型：
$$
\mathcal{L}\left(\mathcal{D}{\mathrm{tr}}, \boldsymbol{\theta}\right)=\underbrace{\frac{1}{n} \sum{i=1}^{n}\left(f\left(\boldsymbol{x}{i}, \boldsymbol{\theta}\right)-y{i}\right)^{2}}{\operatorname{MSE}\left(\mathcal{D}{\text { tr }}, \boldsymbol{\theta}\right)}+\lambda \Omega(\boldsymbol{w})
$$
根据$\Omega(w)$的不同，linear regression 可以分为下面4种
| 类型 | $\Omega(w)$ | ||||
|---|---|---|---|---|---|
| Ordinary Least Square(OLS) | $\Omega(w) = 0$ | ||||
| Ridge | $\Omega(\boldsymbol{w})=\frac{1}{2}\ | \boldsymbol{w}\ | _{2}^{2}$ | ||
| LASSO | $\Omega(\boldsymbol{w}) = \ | {w}_1\ | $ | ||
| Elastic-Net Regression | $\Omega(w) = \rho\ | w_1\ | + (1-\rho)\frac{1}{2}\ | w_2^2\ | $ |
Adversarial Model
这里定义敌手模型。
敌手模型主要是用来对潜在用户进行分析建模，例如：假设攻击者掌握了多少知识、攻击者的目标是什么、攻击者的攻击策略是什么等。具体的可以从下面4个维度来对潜在的攻击者进行建模：
| 维度 | 描述 |
|---|---|
| Adversary Goal | 一般包含两种:availability attack & integrity attack.前者主要目的是使整个模型的可用性降低，后者主要是使模型在针对特定样本做 inference 时，准确率降低 |
| Adversary Knowledge | 一般包含两种：white-box & black-box. 对于前者，假设攻击者知晓：traning data & learning algorithm & loss function & model parameters；对于后者，假设攻击者只知晓：learning algorithm & loss function。但是这篇文章中，作者通过产生替代数据，同样可以得到 model parameters. |
| Adversary Capability | 攻击者的能力，一般定义为其能往数据集中插入多少 poisoning samples. $n:original \ samples$, $p :poisoning \ samples$, $N = n + p:\ total \ smaples$, 定义poisoning rate $\alpha = p/n$ |
| Adversary Strategy | $\begin{array}{rl}{\arg \max {\mathcal{D}{p}}} & {\mathcal{W}\left(\mathcal{D}^{\prime}, \boldsymbol{\theta}{p}^{\star}\right)} \ {\text { s.t. }} & {\boldsymbol{\theta}{p}^{\star} \in \arg \min {\boldsymbol{\theta}} \mathcal{L}\left(\mathcal{D}{\mathrm{tr}} \cup \mathcal{D}_{p}, \boldsymbol{\theta}\right)}\end{array}$ 攻击者的目标主要是优化上面的目标函数：即如何插入 poisoning samples 来使得在 $D’$上的 loss 值最大. |
攻击方法
攻击者的目标函数：
$$
\begin{array}{rl}{\arg \max {\mathcal{D}{p}}} & {\mathcal{W}\left(\mathcal{D}^{\prime}, \boldsymbol{\theta}{p}^{\star}\right)} \ {\text { s.t. }} & {\boldsymbol{\theta}{p}^{\star} \in \arg \min {\boldsymbol{\theta}} \mathcal{L}\left(\mathcal{D}{\mathrm{tr}} \cup \mathcal{D}_{p}, \boldsymbol{\theta}\right)}\end{array}
$$
注： 目标函数 $W$一般用 validation set 上面的 loss 来表示。loss 越大，表名攻击效果越好。对于 linear regression, loss function = Mean Square Error(MSE)
那么该插入什么样的 poisoning sample 才能使目标函数 $W$ 的值最大呢？
答案是：考虑梯度，考虑$W$对$D_p$的梯度。有了这个梯度，我们就能使用gradient ascent方法来更新$D_p$，直到最后$W$收敛，我们可以得到最佳的$D_p$.
但是这个优化问题是一个Bi-level问题，即约束条件本身也是一个优化问题，解决这种问题通常情况下是NP-hard.因为$x_c$和$W$并不是显示相关，而是通过$\theta$间接相关，因此作者通过chain rule来计算所需要的梯度 $\nabla_{\boldsymbol{x}_{c}} \mathcal{W}$:
$$
\nabla_{\boldsymbol{x}{c}} \mathcal{W}=\nabla{\boldsymbol{x}{c}} \boldsymbol{\theta}\left(\boldsymbol{x}{c}\right)^{\top} \cdot \nabla_{\boldsymbol{\theta}} \mathcal{W}
$$
注：$x_c$表示 poisoning sample 的 features
1. 首先求解公式的第二项 $\nabla_{\theta} \mathcal{W}$
第二项比较好计算，因为在线性回归问题中，目标函数表示的是在 validation set 上计算到的 loss：
$$
\mathcal{W}{\mathrm{val}}\left(\mathcal{D}{\mathrm{val}}, \boldsymbol{\theta}\right)=\frac{1}{m} \sum_{j=1}^{m}\left(f\left(\boldsymbol{x}{j}^{\prime}, \boldsymbol{\theta}\right)-y{j}^{\prime}\right)^{2}
$$
对这个函数求对$\theta$的偏导：
$$
\nabla_{\boldsymbol{\theta}} \mathcal{W}{\mathrm{val}}=\left[ \begin{array}{c}{\nabla{\boldsymbol{w}} \mathcal{W}{\mathrm{val}}} \ {\nabla{b} \mathcal{W}{\mathrm{val}}}\end{array}\right]=\left[ \begin{array}{c}{\frac{2}{m} \sum{j=1}^{m}\left(f\left(\boldsymbol{x}{j}\right)-y{j}\right) \boldsymbol{x}{j}} \ {\frac{2}{m} \sum{j=1}^{m}\left(f\left(\boldsymbol{x}{j}\right)-y{j}\right)}\end{array}\right]
$$
至此，公式第二项偏导数计算完毕，下面计算第一项。
2. 求解公式第二项 $\nabla_{\boldsymbol{x}{c}} \boldsymbol{\theta}\left(\boldsymbol{x}{c}\right)^{\top}$
