原文链接及源码链接
原文：https://arxiv.org/abs/1909.10773
源码：https://github.com/cmhcbb/attackbox
以前的工作 Opt-Attack
Opt-Attack：定义了一个目标函数g(θ)。g(θ) 将输入的搜索方向θ映射到实值输出（到决策边界的距离)，这是通常是连续的，θ的微小变化通常会导致g(θ)的微小变化）。
优化问题：$\min _{\boldsymbol{\theta}} g(θ)$ （1）
其中。使用细粒度搜索和二分查找搜索求得g(θ)近似函数值；
使用零阶优化方法来优化（1）。作者使用随机无梯度（RGF）来求解。
以前工作的不足
需要大量查询
现在的工作 Sign-Opt Attack
在本文中，采样和Opt-Attack相同的优化公式，但提出了直接估计任意方向上的梯度符号，而不是梯度本身，即仅使用单个查询来估计梯度符号，而不是使用有限差分来估计方向导数的大小。利用这个单查询符号oracle，本文提出了一种新的查询高效的Sign-Opt方法来进行硬标签黑盒攻击。
现在工作的贡献
1、提出了一种利用单个查询计算Opt-Attack目标函数方向导数符号的有效方法，并在此基础上提出了一种新的硬标签黑盒攻击优化算法SIGN-OPT。
2、本文的方法可以看作是一种新的零阶优化算法，它具有signSGD快速收敛的特点。本文的算法没有直接取梯度估计的符号，而是利用了随机方向的尺度。
3、本文在几个数据集和模型上进行了全面的实验。实验结果表明，该算法在不同的模型和数据集上的查询次数持续减少了5-10倍，是一种实用的、查询效率高的健壮性评估工具。此外，与以往的方法相比，在大多数数据集上，本文的算法可以找到一个失真较小的对抗性例子。
提出的方法
使用和Opt-Attack相同的目标函数公式，将硬标签攻击视为找到到决策边界最短距离的方向的问题。
对于一个给定的样本$x_{0}$、真实的标签$y_{0}$、硬标签黑盒函数$f: \mathbb{R}^{d} \rightarrow\{1, \ldots, K\}$，我们根据攻击类型定义了目标函数$g: \mathbb{R}^{d} \rightarrow \R$。
非定向攻击（untargeted attack）：
在每个二分搜索步骤中，我们查询函数$f(x_{0}+ \lambda \frac{\theta}{\left | \theta \right |})$，并基于硬标签预测来确定在方向θ上到决策边界的距离是大于还是小于λ
由于目标函数是可计算的，因此可以通过有限差分来估计$g$的方向导数：
其中$u$是随机高斯向量，$\epsilon$>0是非常小的平滑参数。这是一个用于估计方向导数的标准零阶预言，在此基础上，我们可以应用许多不同的零阶优化算法来最小化。例如，程等人。(2019)使用了Nesterov&Spokoiny(2017)的随机无梯度（RGF）算法来解决问题(1)。然而，由于二进制搜索，每次计算(2)都需要许多硬标签查询，因此Cheng等人(2019年)尽管收敛速度很快，但仍需要大量查询。
在这项工作中，介绍了一个算法，比Cheng等人(2019年)的查询复杂度有了很大的提高。
我们的算法基于以下关键思想：
1）不需要非常精确的方向导数值就能使算法收敛；
2）存在可以由单个查询计算的g的方向导数的完美但有信息的估计。
1 ASINGLE QUERY ORACLE
如前所述，前面的方法需要计算$g(θ+εμ)-g(θ)$，这会消耗大量查询。然而，基于$g(·)$的定义，我们可以使用单次查询来计算该值符号$g(θ+εμ)-g(θ)$的符号。考虑到无目标攻击的情况，符号可以由以下公式来计算：
如图1所示：
本质上，对于一个新的方向$θ+εμ$，本文测试在该方向上与$x_{0}$的原始距离g(θ)处的点是位于决策边界内部还是外部，即产生的扰动是否会导致分类器的错误预测。如果产生的扰动在边界外，即$f(x_{0}+g(θ)\frac{(θ+εμ)}{\left | θ+εμ \right |}) \neq y_{0}$，则新方向到决策边界的距离较小，从而给出较小的$g$值，这表明$u$是最小化$g$的下降方向。
SIGN-OPTATTACK
通过对随机高斯矢量进行Q次采样，本文用以下公式来估计不完全梯度，这只需要Q个查询：
然后，我们使用这个不完美的梯度估计将我们的搜索方向$θ$更新为$\boldsymbol{\theta} \leftarrow \boldsymbol{\theta}-\eta \hat{\boldsymbol{g}}$，步长η，并使用相同的搜索过程计算g(θ)，直到达到一定的精度。详细步骤如算法1所示。
OTHER GRADIENT ESTIMATIONS
请注意，单次查询oracle计算的值：$sign(g(θ+εμ)-g(θ))$实际上是方向导数的符号：
因此，我们可以利用这些信息来估计原始梯度。上一节中的Sign-Opt方法使用$\sum _{q}sign(\left \langle \nabla g(\boldsymbol{\theta}),\boldsymbol{u}_{q} \right \rangle)\boldsymbol{u}_{q} $作为梯度估计。设$y_{q}:= sign(\left \langle \nabla g(\boldsymbol{\theta}),\boldsymbol{u}_{q} \right \rangle)$，更精确的梯度估计可转化为以下约束优化问题：
因此，这等价于硬约束支持向量机问题，其中每个$μ_{q}$是训练样本，$y_{q}$是相应的标签。然后，可以通过求解以下二次规划问题来恢复梯度：
通过解决这个问题，我们可以得到一个很好的梯度估计。如前所述，可以用单个查询来确定每个$y_{q}$。因此，我们提出了Sign-Opt的一种变体，称为SVM-OPT攻击。具体步骤如算法2所示。
根据实验结果：Sign-Opt与SVM-Opt这两种攻击的查询性能非常相似。
实验结果
