Multi-Label Adversarial Perturbations

Multi-Label Adversarial Perturbations

ICDM2018

1.介绍

与multi-class分类问题中标签互斥且一个实例只能有一个标签的情况不同，在multi-label分类中，每个实例可以与多个标签关联，从而为攻击者提供更多的机会和为防御者带来更大的不确定性。

1.1多标签对抗样本广泛存在于现实生活中。

• 从攻击者角度看，他想更改某些标签，同时保持其他标签不变,。 例如一个图片推荐系统，图片系统可以生成与特定topic有关的垃圾图像。在这种情况下，垃圾图片发送者希望系统将垃圾垃圾图像误分类为良性对象，同时出于恶意推荐的目的将其正确分类为风景图像。
• 从良性的角度来看，系统管理员可以利用对抗样本来干扰一些用户的敏感属性，从而防止恶意分类器推断用户的个人信息来增强对用户隐私的保护。

1.2生成多标签对抗样本的挑战。

• 每个实例可能具有不确定数量的标签。
• 由于标签不会相互排斥，因此很难协调多个标签。
• 量化攻击性能可能很困难，因为可能无法同时实现多个标签目标攻击。

1.3针对多标签攻击本文设计了2种框架4种方法

• Classification-targeted Framework
  • ML-C&W
  • ML-DeepFool
• Ranking-targeted Framework
  • Rank I
  • Rank II

对于非目标攻击，没有要针对的特定标签进行操作，这跟单标签中的非目标攻击相似，本文就没有考虑。

2.符号

$x \in R^{d*1}$x∈Rd∗1, $y \in \{-1,1\}^{l*1}$y∈{−1,1}l∗1, 分类器预测得分$F: R^d ->R^l$F:Rd−>Rl, $F=\{f_1,...,f_l\}$F={f1​,...,fl​}, 分类器预测最后输出$H:R^d -> \{-1,1\}^l$H:Rd−>{−1,1}l，$H=\{h1,...,h_l\}$H={h1,...,hl​}

2.1有目标攻击定义

原始样本$x$x，对抗样本$x^*$x∗,给定集合$A$A和$B$B, $A$A集合中的标签表示攻击后预测值和原样本ground truth相反，$B$B集合中的标签表示攻击后预测值和原样本ground truth相同

${ h _ { a } \left( \mathrm { x } ^ { * } \right) \neq y _ { a } , \forall a \in A } \\ { h _ { b } \left( \mathbf { x } ^ { * } \right) = y _ { b } , \forall b \in B \\ ( A \neq \emptyset , A \cup B \subset L , A \cap B = \emptyset ) }$ha​(x∗)​=ya​,∀a∈Ahb​(x∗)=yb​,∀b∈B(A​=∅,A∪B⊂L,A∩B=∅)

在实践中，攻击者通常只对攻击一组特定的标签（$A$A）感兴趣，而保留另一组特定的标签（$B$B）以便进行更相关的攻击或伪装。.在本文的其余部分，我们将重点研究多标签对抗性样本的目标攻击，因为它们在现实世界的系统中更为实用且有意义。

3.多标签目标攻击

3.1 Classification-targeted Framework

这种情况是针对分类的最终结果$H$H进行攻击，对应预测得分$F$F固定阈值为0。对于$x$x，ground truth每个标签为 -1或者1,我们的目标是以下优化函数。$x^* = x + r, r$x∗=x+r,r 为扰动量
$\begin{array} { l l } { \underset { \mathbf { r } } { \operatorname { minimize } } } & { \| \mathbf { r } \| } \\ { \text { subject to } } & { h _ { a } ( \mathbf { x } + \mathbf { r } ) = - y _ { a } , a \in A } \\ { } & { h _ { b } ( \mathbf { x } + \mathbf { r } ) = y _ { b } , b \in B } \end{array}$rminimize​ subject to ​∥r∥ha​(x+r)=−ya​,a∈Ahb​(x+r)=yb​,b∈B​

对于线性预测变量$F（x）$F（x），可以使用$H（x）= sgn（F（x））$H（x）=sgn（F（x））的阈值0来引入相应的分类器，其中sgn（·）是符号函数。因此由公式2可以可知，
$y _ { a } f _ { a } ( x + r ) \leq 0 , \quad - y _ { b } f _ { b } ( x + r ) \leq 0$ya​fa​(x+r)≤0,−yb​fb​(x+r)≤0
公式2可以推导为
$\begin{array} { l l } { \underset { \mathbf { r } } { \operatorname { minimize } } } & { \| \mathbf { r } \| } \\ { \text { subject to } } & { \mathbf { y } ^ { \prime } \odot F ^ { \prime } ( \mathbf { x } + \mathbf { r } ) \leq \mathbf { c } } \end{array}$rminimize​ subject to ​∥r∥y′⊙F′(x+r)≤c​
其中$y^{'}$y′为对抗样本的目标攻击值, $F^{'}(x+r)$F′(x+r)为对抗样本的预测得分，$c$c 表示全0向量。
$\begin{array} { l } { \text { where } \mathbf { y } ^ { \prime } = \left[ y _ { a _ { 1 } } , \ldots , y _ { a _ { | A | } } , - y _ { b _ { 1 } } , \ldots , - y _ { b _ { | B } | } \right] ^ { \top } \text { and } F ^ { \prime } = } \\ { \left[ f _ { a _ { 1 } } , \ldots , f _ { a _ { | A | } } , f _ { b _ { 1 } } , \ldots , f _ { b _ { | B | } } \right] ^ { \top } . \odot \text { is the Hadamard product. } } \end{array}$ where y′=[ya1​​,…,ya∣A∣​​,−yb1​​,…,−yb∣B​∣​]⊤ and F′=[fa1​​,…,fa∣A∣​​,fb1​​,…,fb∣B∣​​]⊤.⊙ is the Hadamard product. ​

3.1.1 ML-CW

很直接方法是把公式5转换为，带有hinge loss的优化函数,
$\underset { \mathbf { r } } { \operatorname { minimize } } \quad \| \mathbf { r } \| + \lambda \sum _ { i = 1 } ^ { | A | + | B | } \max \left( 0 , \mathbf { y } _ { i } ^ { \prime } F _ { i } ^ { \prime } ( x + r ) - c _ { i } \right)$rminimize​∥r∥+λi=1∑∣A∣+∣B∣​max(0,yi′​Fi′​(x+r)−ci​)
其中$\lambda$λ为trade-off参数。

3.1.2 ML-DeepFool

考虑到约束的高度非线性，求解方程式（4）的一种变化是利用 $F'$F′ 的线性近似将约束线性化为：
$\begin{array} { l l } { \underset { \mathbf { r } } { \operatorname { minimize } } } & { \| \mathbf { r } \| } \\ { \text { subject to } } & { \mathbf { y } ^ { \prime } \odot \left[ F ^ { \prime } ( \mathbf { x } ) + \left( \frac { \partial F ^ { \prime } } { \partial \mathbf { x } } \right) ^ { \top } \mathbf { r } \right] \leq \mathbf { c } } \end{array}$rminimize​ subject to ​∥r∥y′⊙[F′(x)+(∂x∂F′​)⊤r]≤c​
where $\frac { \partial F ^ { \prime } } { \partial x } = \left[ \frac { \partial f _ { a _ { 1 } } } { \partial x } , \ldots , \frac { \partial f _ { a _ { | A | } } } { \partial x } , \frac { \partial f _ { b _ { 1 } } } { \partial x } , \ldots , \frac { \partial f _ { b _ { | B | } } } { \partial x } \right] \in \mathbb { R } ^ { d \times ( | A | + | B | ) } .$∂x∂F′​=[∂x∂fa1​​​,…,∂x∂fa∣A∣​​​,∂x∂fb1​​​,…,∂x∂fb∣B∣​​​]∈Rd×(∣A∣+∣B∣).

上述公式可以化简为
$\begin{array} { l l } { \underset { \mathbf { r } } { \operatorname { minimize } } } & { \| \mathbf { r } \| _ { 2 } ^ { 2 } } \\ { \text { subject to } } & { \mathbf { P } ( \mathbf { x } ) ^ { \top } \mathbf { r } \leq \mathbf { q } ( \mathbf { x } ) } \end{array}$rminimize​ subject to ​∥r∥22​P(x)⊤r≤q(x)​
where $\mathbf { P } ( \mathbf { x } ) = \left( \mathbf { 1 } _ { d } \times \mathbf { y } ^ { \prime \top } \right) \odot \frac { \partial F ^ { \prime } ( \mathbf { x } ) } { \partial \mathbf { x } }$P(x)=(1d​×y′⊤)⊙∂x∂F′(x)​ and $\mathbf { q } ( \mathbf { x } ) = \mathbf { c } - \mathbf { y } ^ { \prime } \odot F ^ { \prime } ( \mathbf { x } ).$q(x)=c−y′⊙F′(x).

像DeepFool一样，令$\Delta \mathbf { r } = \mathbf { P } \left( \mathbf { x } _ { i } \right) \left( \mathbf { P } \left( \mathbf { x } _ { i } \right) ^ { \top } \mathbf { P } \left( \mathbf { x } _ { i } \right) \right) ^ { - 1 } \mathbf { q } \left( \mathbf { x } _ { i } \right)$Δr=P(xi​)(P(xi​)⊤P(xi​))−1q(xi​)，利用迭代的方法求得r

3.2 Ranking-targeted Framework

$A$A集合中的标签表示攻击后预测值和原样本ground truth相反，$B$B集合中的标签表示攻击后预测值和原样本ground truth相同，由上图可知

• $A_1$A1​表示为原来为1，攻击之后变为-1的标签

• $A_{-1}$A−1​表示为原来为-1，攻击之后变为1的标签

• $B_1$B1​表示为原来为1，攻击之后还为1的标签

• $B_{-1}$B−1​表示为原来为-1，攻击之后还为-1的标签

• $C$C表示不考虑的标签

基于排名算法特点（1）软阈值：由于基于排名的模型旨在产生标签之间的排名关系，因此无需指定硬阈值。（2）标签关系：以分类为目标的框架没有明确考虑标签之间的关系，这对于攻击基于排名的算法可能无法推广。为了解决这些问题，我们提出了一个针对排名的框架。
$\begin{array} { l l } { \underset { \mathbf { r } } { \operatorname { minimize } } } & { \| \mathbf { r } \| } \\ { \text { subject to } } & { f _ { \alpha } ( \mathbf { x } + \mathbf { r } ) \leq f _ { \gamma } ( \mathbf { x } + \mathbf { r } ) \leq f _ { \beta } ( \mathbf { x } + \mathbf { r } ) } \\ { } & { \forall \alpha \in A _ { 1 } \cup B _ { - 1 } , \beta \in A _ { - 1 } \cup B _ { 1 } , \gamma \in C } \end{array}$rminimize​ subject to ​∥r∥fα​(x+r)≤fγ​(x+r)≤fβ​(x+r)∀α∈A1​∪B−1​,β∈A−1​∪B1​,γ∈C​
$ A _ { 1 } \cup B _ { - 1 }$为使攻击之后变为-1的集合，$为使攻击之后变为−1的集合，A _ { - 1 } \cup B _ { 1 }$为使攻击之后变为1的集合，无关标签C的预测置于中间以增强攻击能力。

3.2.1 Rank I Attack

$\begin{array} { l } { \text { Assume } \Omega ^ { - } = A _ { 1 } \cup B _ { - 1 } , \Omega ^ { + } = } { A _ { - 1 } \cup B _ { 1 } , \text { and } \Omega ^ { \circ } = C . \text { } } \end{array}$ Assume Ω−=A1​∪B−1​,Ω+=A−1​∪B1​, and Ω∘=C. ​定义一个扰动量r和排名有关的损失函数，使得攻击之后目标为1的标签得分更高，为-1的标签得分更低。
$\begin{aligned} \mathcal { L } _ { 0 } = \| \mathbf { r } \| & + \frac { 1 } { | \Omega - \| \Omega + | } \sum _ { ( \alpha , \beta ) \in \Omega - \times \Omega + } \max \left( 0 , e ^ { f _ { \alpha } ( \mathbf { x } + \mathbf { r } ) } - e ^ { f _ { \beta } ( \mathbf { x } + \mathbf { r } ) } \right) \\ & + \frac { 1 } { \left| \Omega - \| \Omega ^ { \circ } \right| } \sum _ { ( \alpha , \gamma ) \in \Omega ^ { - } \times \Omega ^ { \circ } } \max \left( 0 , e ^ { f _ { \alpha } ( \mathbf { x } + \mathbf { r } ) } - e ^ { f _ { \gamma } ( \mathbf { x } + \mathbf { r } ) } \right) \\ & + \frac { 1 } { \left| \Omega ^ { \circ } \right| | \Omega + | } \sum _ { ( \gamma , \beta ) \in \Omega ^ { \circ } \times \Omega ^ { + } } \max \left( 0 , e ^ { f _ { \gamma } ( \mathbf { x } + \mathbf { r } ) } - e ^ { f _ { \beta } ( \mathbf { x } + \mathbf { r } ) } \right) \end{aligned}$L0​=∥r∥​+∣Ω−∥Ω+∣1​(α,β)∈Ω−×Ω+∑​max(0,efα​(x+r)−efβ​(x+r))+∣Ω−∥Ω∘∣1​(α,γ)∈Ω−×Ω∘∑​max(0,efα​(x+r)−efγ​(x+r))+∣Ω∘∣∣Ω+∣1​(γ,β)∈Ω∘×Ω+∑​max(0,efγ​(x+r)−efβ​(x+r))​
考虑到上述公式计算标签集合中两两差值过于繁琐，经过简化得到下式
$\begin{aligned} \mathcal { L } _ { 1 } = \| \mathbf { r } \| & + \lambda _ { 1 } \max \left( 0 , \max _ { \alpha \in \Omega ^ { - } } e ^ { f _ { \alpha } ( \mathbf { x } + \mathbf { r } ) } - \min _ { \beta \in \Omega ^ { + } } e ^ { f _ { \beta } ( \mathbf { x } + \mathbf { r } ) } \right) \\ & + \lambda _ { 2 } \max \left( 0 , \max _ { \alpha \in \Omega ^ { - } } e ^ { f _ { \alpha } ( \mathbf { x } + \mathbf { r } ) } - \min _ { \gamma \in \Omega ^ { \circ } } e ^ { f _ { \gamma } ( \mathbf { x } + \mathbf { r } ) } \right) \\ & + \lambda _ { 3 } \max \left( 0 , \max _ { \gamma \in \Omega ^ { \circ } } e ^ { f _ { \gamma } ( \mathbf { x } + \mathbf { r } ) } - \min _ { \beta \in \Omega ^ { + } } e ^ { f _ { \beta } ( \mathbf { x } + \mathbf { r } ) } \right) \end{aligned}$L1​=∥r∥​+λ1​max(0,α∈Ω−max​efα​(x+r)−β∈Ω+min​efβ​(x+r))+λ2​max(0,α∈Ω−max​efα​(x+r)−γ∈Ω∘min​efγ​(x+r))+λ3​max(0,γ∈Ω∘max​efγ​(x+r)−β∈Ω+min​efβ​(x+r))​

3.2.2 Rank II Attack

虽然在一定程度上，Rank I Attack 考虑了标签相关性，但在某些情况下可能不够敏感。例如，如果我们有一个带有基本真值标签[-1，1，1] 和目标攻击标签[-1，1，1]>，预测器F预测的标签概率可以是[0.01，0,98,0.99]。在这种情况下，上式排名损失为0，梯度直接为0，更新停止。因此在上述基础上再加一些限制，使得原来为1，攻击之后为-1的集合$A_1$A1​得分小于原来为-1，攻击之后还为-1的集合 $B_ {-1}$B−1​，

$\begin{array} { l l } { f _ { \alpha _ { 1 } } ( \mathbf { x } + \mathbf { r } ) \leq f _ { \alpha _ { 2 } } ( \mathbf { x } + \mathbf { r } ) , } & { \forall \alpha _ { 1 } \in A _ { 1 } , \alpha _ { 2 } \in B _ { - 1 } } \\ { f _ { \beta _ { 1 } } ( \mathbf { x } + \mathbf { r } ) \leq f _ { \beta _ { 2 } } ( \mathbf { x } + \mathbf { r } ) , } & { \forall \beta _ { 1 } \in B _ { 1 } , \beta _ { 2 } \in A _ { - 1 } } \end{array}$fα1​​(x+r)≤fα2​​(x+r),fβ1​​(x+r)≤fβ2​​(x+r),​∀α1​∈A1​,α2​∈B−1​∀β1​∈B1​,β2​∈A−1​​
更新之后的优化函数，在Rank I Attack基础上加上2项
$\begin{aligned} \mathcal { L } _ { 2 } = \mathcal { L } _ { 1 } & + \lambda _ { 4 } \max \left( 0 , \max _ { \alpha _ { 1 } \in A _ { 1 } } e ^ { f _ { \alpha } ( \mathbf { x } + \mathbf { r } ) } - \min _ { \alpha _ { 2 } \in B _ { - 1 } } e ^ { f _ { \beta } ( \mathbf { x } + \mathbf { r } ) } \right) \\ & + \lambda _ { 5 } \max \left( 0 , \max _ { \beta _ { 1 } \in B _ { 1 } } e ^ { f _ { \beta } ( \mathbf { x } + \mathbf { r } ) } - \min _ { \beta _ { 2 } \in A _ { - 1 } } e ^ { f _ { \beta } ( \mathbf { x } + \mathbf { r } ) } \right) \end{aligned}$L2​=L1​​+λ4​max(0,α1​∈A1​max​efα​(x+r)−α2​∈B−1​min​efβ​(x+r))+λ5​max(0,β1​∈B1​max​efβ​(x+r)−β2​∈A−1​min​efβ​(x+r))​

3.3 Classification-targeted Framework 和 Ranking-targeted Framework

两个框架彼此高度关联。比较方程式（2）和（9），如果我们用硬分类阈值替换软阈值 $f _ { \gamma } ( \mathbf { x } + \mathbf { r } )$fγ​(x+r)，则这两类框架彼此等效。这意味着如果我们不知道部分黑盒下的特定分类阈值，则 II 型框架可能会更通用。相比之下，类型 I 框架直接考虑了分类阈值。因此，如果我们对多标签分类算法进行纯白盒攻击，并且在 II 型框架中不使用硬阈值，则I型框架可能会获得更好的性能，因为它考虑了更准确的分类阈值。基于这两种类型的框架。