HopSkipJumpAttack论文分析

HopSkipJumpAttack是发表于2020年S&P的论文，提出了一种新型黑盒对抗攻击的方法，利用采样+逼近的思路来生成对抗样本，理论基础完备，实验效果达到了SOTA。

问题描述

被攻击模型的定义

定义神经网络为以下函数

$F: \mathbb{R}^d \rightarrow \mathbb{R}^m$

函数的输入为区间[0, 1]上的d维向量

$x \in [0, 1]^d$

函数的输出为[0, 1]上的m维概率分布向量，满足全概率公式

$y \in \Delta_m := \{y \in [0, 1]^m \: | \: \Sigma^m_{c=1} \: y_c = 1\}$

m同时也是神经网络输出类别的总个数，c用来指代任意一个类别，神经网络输出的所有类别标签的集合即为

$[m] = {1,...,m}$

将函数的输出写成向量的形式为

$y = (F_1(x),...,F_m(x))$

基于以上函数的分类器可以表示为

$C(x) := \underset{c \in [m]}{\operatorname{argmax}}F_c (x)$

对抗攻击的定义

untarget attack的目标是让分类器的输出类别从

$c^* := C(x^*)$

变成与原来类别不同的任何类别

$c \in [m] - \{c^*\}$

targeted attack的目标是让分类器的输出类别变成某个预先定义好的类别

$c^{\dagger} \in [m] - \{c^*\}$

定义函数S，S与攻击者的攻击目标有关，可以判定当前生成的对抗样本是否满足攻击目标

$S_{x^*}(x'):= \left \{ \begin{array}{rcl} \operatorname{max}_{c \neq c^*} F_c(x')-F_{c^*}(x') & (Untargeted) \\ F_{c^\dagger}(x')-\operatorname{max}_{c \neq c^\dagger}F_c(x') & (Targeted) \end{array}\right.$

对于任意对抗样本x’而言，只要满足S(x’)>0，就可以认为攻击成功

边界上的对抗样本集合

当S(x’)=0时，对抗攻击正好处在成功与失败的边界上，定义边界上的对抗样本构成的集合为

$bd(S_{x^*}):=\{ z \in [0, 1]^d \: | \: S_{x^*}(z)=0 \}$

攻击成功的判定函数

构造sign函数如下

$\phi_{x^*}(x'):=\operatorname{sign}(S_{x^*}(x'))= \left \{ \begin{array}{rcl} 1 & if \; S_{x^*}(x')>0 \\ -1 & otherwise \end{array}\right.$

当sign函数取值为+1时，对抗样本攻击即为成功。

为了实现攻击的隐蔽性，攻击者最终的目标是找到与原始样本距离最小的对抗样本，距离函数一般取0、2、无穷范数。

$\operatorname{min}_{x'}\;d(x', x^*) \;\;\;\; s.t. \phi_{x^*}(x')=1$

算法框架

迭代更新

HSJA算法可以用数学公式描述如下

$x_{t+1} = \alpha_t x^* + (1 - \alpha_t) \{ x_t + \xi_t \frac{\nabla S_{x^*}(x_t)}{||\nabla S_{x^*}(x_t)||_2} \}$

其中涉及的关键步骤有：

用二分搜索来选取合适的alpha，让新对抗样本逼近边界
在边界上，用Monte Carlo采样得到函数S的梯度的估计，生成对抗扰动
用Geometric Progression来控制扰动的大小，更新对抗样本
继续用二分搜索来选取合适的alpha，让新对抗样本逼近边界
……

步长选择

把梯度估计线性叠加到对抗样本上的公式描述如下

$\tilde{x}_t := x_t + \xi_t v_t (x_t, \delta_t)$ $v_t(x_t, \delta_t) = \left \{ \begin{array}{rcl} \widehat{\nabla S}(x_t, \delta_t) / ||\widehat{\nabla S}(x_t, \delta_t)||_2 & if \;\; p = 2 \\ \operatorname{sign}(\widehat{\nabla S}(x_t, \delta_t)) & if \;\; p = \infty \end{array} \right.$

该迭代算法的收敛性与步长的选择直接相关，HSJA将步长初始化如下，如果更新后的对抗样本攻击失败，那么步长减半，以此类推。

$\xi_t := ||x_t - x^*||_p / \sqrt{t}$

算法细节

Lp-projection

与大多数主流算法相似，HSJA算法给对抗样本到原始样本的距离增加了限制，不能大于epsilon。距离函数取Lp范数，p=2或inf。

给定对抗样本x，Lp-projection步骤的目的是在对抗样本x上进行裁剪，裁剪后得到的新对抗样本y既要满足到原始样本的距离限制，又要距离原来的对抗样本x尽可能地近。

Lp-projection步骤在p=1, 2, …, 无穷时都有通解，但本算法重新构造了通解，以便后续进行二分搜索。以下分别为L2和Linf两种情况下的映射公式。

当p=2时，映射公式如下

$\Pi_{x^*,\alpha_t}^2 (x) := \underset{||y-x^*||_2 \leqslant \alpha_t}{\operatorname{argmin}} ||y-x||_2 = \alpha_t x^* + (1-\alpha_t)x$

当p=inf时，映射公式如下，值得注意的是，x和x*都是向量，而此处新定义的c是常数。

$\Pi_{x^*, \alpha}^\infty (x) := \operatorname{max}\{\operatorname{min}\{x, x^*+c\}, x^*-c\} \;\; (modified)$ $c := \alpha||x - x^*||_\infty$

原论文在此处的公式可能有误，已知c是个非负数，那么x与x+c的比较就失去了意义，以下给出原论文上的无穷范数映射公式

$\Pi_{x^*, \alpha}^\infty (x)_i := \operatorname{max}\{\operatorname{min}\{x_i^*, x_i^*+c\}, x_i-c\}$

无论p=2还是inf，alpha的概念都是统一的：越接近0就离原始样本越近，越接近0就离对抗样本越近。利用概念上的统一性，后续在对alpha在区间[0, 1]上做二分搜索时，也更加方便。

开源代码库foolbox给出了Lp-projection的实现，如下所示

def _project(
    self, originals: ep.Tensor, perturbed: ep.Tensor, epsilons: ep.Tensor
) -> ep.Tensor:
    """Clips the perturbations to epsilon and returns the new perturbed
    Args:
        originals: A batch of reference inputs.
        perturbed: A batch of perturbed inputs.
        epsilons: A batch of norm values to project to.
    Returns:
        A tensor like perturbed but with the perturbation clipped to epsilon.
    """
    epsilons = atleast_kd(epsilons, originals.ndim)
    if self.constraint == "linf":
        perturbation = perturbed - originals

        # ep.clip does not support tensors as min/max
        clipped_perturbed = ep.where(
            perturbation > epsilons, originals + epsilons, perturbed
        )
        clipped_perturbed = ep.where(
            perturbation < -epsilons, originals - epsilons, clipped_perturbed
        )
        return clipped_perturbed
    else:
        return (1.0 - epsilons) * originals + epsilons * perturbed

梯度估计

估计的成立条件

HSJA算法需要对函数S在第t次迭代生成的对抗样本xt上求梯度。若要使这一梯度可被估计，需要满足以下假设条件

函数S二阶可导，并且满足局部Lipschitz约束，x0是初始对抗样本

$\exists L>0, \;\; \forall x,y \in \{z:||z-x^*||_2 \leqslant ||x_0 - x^*||_2 \},$ $||\nabla S_{x^*}(x) - \nabla S_{x^*}(y)||_2 \leqslant L||x-y||_2$

如果对抗样本xt刚好处于边界，即S(xt)=0，那么函数S在xt上的导数一定存在下界，并且下界大于0

$\exists \tilde{C} > 0, \;\; \forall z \in bd(S_{x^*})$ $|| \nabla S_{x^*}(z) || > \tilde{C}$

如果要用对抗样本xt与初始样本x的差来做函数S梯度的无偏估计（即下面的函数r=1），那么xt必须要处于HSJA算法优化过程中的*驻点上

$\begin{align} r(x_t, x^*) :&= cos \angle (x_t - x^*, \nabla S_{x^*}(x_t)) \\ & = \frac{<x_t - x^*, \nabla S_{x^*}(x_t)>}{||x_t - x^*||_2 || \nabla S_{x^*}(x_t)||_2} \end{align}$

在上述假设都成立的情况下，在HSJA算法优化过程中选取合适的步长，可以保证算法得到的对抗样本xt最终收敛至驻点

$\xi_t = || x_t - x^* ||_2 t^{-q} \;\;\;\; for \; q \in (\frac{1}{2},1)$ $0 \leqslant 1 - r(x_t, x^*) \leqslant ct^{q-1} \;\;\;\; for \; t=1,2,...$

以上分别为步长更新公式和步长对函数r的限制，具体证明过程里用到了二阶泰勒估计。

上述估计方法也可以推广到p=inf的情况。

渐进无偏估计量

对任意位于边界上的xt，可以用以下Monte Carlo采样得到的统计量来估计函数S的梯度

$\widetilde{\nabla S}(x_t, \delta) := \frac{1}{B} \sum_{b=1}^{B} \phi_{x^*}(x_t+\delta u_b)u_b,$ $x_t \in bd(S_{x^*})$ $i.i.d. \;\{u_b\}_{b=1}^B \sim U(-1, 1)^d$

随机变量ub是独立同分布的d维随机向量，服从均匀分布，B表示样本容量，也是Monte Carlo采样的次数。

由于引入了delta，导致该估计量是有偏的，但偏差具有下界，可表示为

$\cos \angle (\mathbb{E}[ \widetilde{\nabla S} (x_t, \delta)], \nabla S_{x^*}(x_t)) \geqslant 1 - \frac{9 L^2 \delta^2 d^2}{8||\nabla S(x_t)||_2^2}$

以上估计量的渐进无偏性可表示为

$\lim_{\delta \rightarrow 0} \cos \angle (\mathbb{E}[ \widetilde{\nabla S} (x_t, \delta)], \nabla S_{x^*}(x_t))=1$

一般取delta为1/d，之后会给出一个偏差更小的delta选取方法。

方差更小的估计量

由于实验误差的存在，xt不一定恰好在边界上，delta也不总是为0，因此采样得到的新样本在边界两边常常是分布不均匀的，这会产生难以忽视的误差。

因此HSJA算法提出了一个新的方差更小的估计量。和之前的估计量一样，新估计量也是渐进无偏的。新估计量表示如下

$\begin{align} \overline{\phi_{x^*}} & := \frac{1}{B} \sum_{b=1}^{B} \phi_{x^*}(x_t + \delta u_b) \\ \widehat{\nabla S}(x_t, \delta) &:= \frac{1}{B-1} \sum_{b=1}^{B} (\phi_{x^*}(x_t+\delta u_b) - \overline{\phi_{x^*}})u_b \end{align}$

方差上界的证明部分略去。

Monte Carlo采样方法的实现

开源代码库foolbox给出了该梯度估计方法的实现，与原论文的代码仓库相比实现更加简洁，但思路比较难理解。

首先，生成随机张量rv并单位化。

if self.constraint == "l2":
    rv = ep.normal(x_advs, noise_shape)
elif self.constraint == "linf":
    rv = ep.uniform(x_advs, low=-1, high=1, shape=noise_shape)
rv /= atleast_kd(ep.norms.l2(flatten(rv, keep=1), -1), rv.ndim) + 1e-12

然后生成扰动图片，即x_adv+delta*rv，图片的值域必须被裁剪到[0, 1]之间。
foolbox库要求用户在实例化对象时指明输入的上下界，之后会把所有的输入张量都缩放到[0, 1]之间。

1
2
3

scaled_rv = atleast_kd(ep.expand_dims(delta, 0), rv.ndim) * rv
perturbed = ep.expand_dims(x_advs, 0) + scaled_rv
perturbed = ep.clip(perturbed, 0, 1)

从扰动图片中还原出采样得到的rv，这一步其实有点巧妙，隐式地对采样得到的rv的大小进行了裁剪。

1	rv = (perturbed - x_advs) / delta

接下来的步骤需要对pytorch的张量condition操作有一定了解，但这段代码的目的是很明确的，只要生成的扰动图片攻击成功了，multipliers中该扰动图片就对应为1，否则对应为-1。

perturbed的形状为：(step_size, batch_size, C, H, W)。

decision的形状为：(step_size, batch_size)，类型为bool。

multipliers最终的形状为：(step_size, batch_size)，攻击成功对应为1，攻击失败对应为-1。

multipliers_list: List[ep.Tensor] = []
for step in range(steps):
    decision = is_adversarial(perturbed[step])
    multipliers_list.append(
        ep.where(
            decision,
            ep.ones(x_advs, (len(x_advs,))),
            -ep.ones(x_advs, (len(decision,))),
        )
    )
# (steps, bs, ...)
multipliers = ep.stack(multipliers_list, 0)

代码还精炼地实现了减少方差的操作，如果所有采样得到的随机扰动都攻击成功/都攻击失败，那么multipliers值不变，否则就需要减去均值来减少估计的方差。

vals = ep.where(
    ep.abs(ep.mean(multipliers, axis=0, keepdims=True)) == 1,
    multipliers,
    multipliers - ep.mean(multipliers, axis=0, keepdims=True),
)

最后求出梯度的估计量，并单位化。

1 2	grad = ep.mean(atleast_kd(vals, rv.ndim) * rv, axis=0) grad /= ep.norms.l2(atleast_kd(flatten(grad), grad.ndim)) + 1e-12

选择合适的扰动大小

HSJA论文中这部分证明比较硬核，我所学知识有限，实在无法理解。大概意思是控制扰动大小的参数delta与估计误差有很大关系，因此需要谨慎选择。

常量gamma的值在论文中并没有，而是作为经验参数，默认为1.0。

def select_delta(
    self, originals: ep.Tensor, distances: ep.Tensor, step: int
) -> ep.Tensor:
    result: ep.Tensor
    if step == 0:
        result = 0.1 * ep.ones_like(distances)
    else:
        d = np.prod(originals.shape[1:])

        if self.constraint == "linf":
            theta = self.gamma / (d * d)
            result = d * theta * distances
        else:
            theta = self.gamma / (d * np.sqrt(d))
            result = np.sqrt(d) * theta * distances

    return result

二分搜索逼近边界

上述梯度估计的重要前提之一是对抗样本xt要刚好处于边界，如果并不处于边界的话，就需要用二分搜索来逼近边界。

HSJA算法将Lp-projection与二分搜索相结合。在Lp-projection中，参数alpha的值越大，新对抗样本距离原始样本就越远，alpha值越小，新对抗样本距离原始样本就越近。

以下结合代码来理解该二分搜索的步骤，初始时，设置alpha的上界、下界分别为0、1。（Linf时上界不可能超过当前无穷范数距离，因此上界初始化为Linf的值）

if self.constraint == "linf":
    highs = linf(originals, perturbed)
    thresholds = highs * self.gamma / (d * d)
else:
    highs = ep.ones(perturbed, len(perturbed))
    thresholds = self.gamma / (d * math.sqrt(d))
lows = ep.zeros_like(highs)

当新对抗样本攻击成功时，将上界调低一点；当新对抗样本攻击失败时，将下界调高一点。如果上下界差距超过预先定义的thresholds就停止搜索。

while ep.any(highs - lows > thresholds):
    mids = (lows + highs) / 2
    mids_perturbed = self._project(originals, perturbed, mids)
    is_adversarial_ = is_adversarial(mids_perturbed)

    highs = ep.where(is_adversarial_, mids, highs)
    lows = ep.where(is_adversarial_, lows, mids)

以上步骤中有一个注意点：用变量highs中存储的所有alpha值来做Lp-projection，都可以攻击成功。利用这个trick，把最终生成的对抗样本再通过highs进行Lp-projection，确保输出的对抗样本都能攻击成功。

1	res = self._project(originals, perturbed, highs)