There are two major paradigms of white-box adversarial attacks that attempt to impose input perturbations.   The first paradigm, called the fix-perturbation attack, crafts adversarial samples within a given perturbation level.   The second paradigm, called the zero-confidence attack, finds the smallest perturbation needed to cause misclassification, also known as the margin of an input feature.   While the former paradigm is well-resolved, the latter is not.   Existing zero-confidence attacks either introduce significant approximation errors, or are too time-consuming.   We therefore propose MarginAttack, a zero-confidence attack framework that is able to compute the margin with improved accuracy and efficiency.   Our experiments show that MarginAttack is able to compute a smaller margin than the state-of-the-art zero-confidence attacks, and matches the state-of-the-art fix-perturbation attacks.   In addition, it runs significantly faster than the Carlini-Wagner attack, currently the most accurate zero-confidence attack algorithm. Adversarial attack refers to the task of finding small and imperceptible input transformations that cause a neural network classifier to misclassify. White-box attacks are a subset of attacks that have access to gradient information of the target network. In this paper, we will focus on the white-box attacks. An important class of input transformations is adding small perturbations to the input. There are two major paradigms of adversarial attacks that attempt to impose input perturbations. The first paradigm, called the fix-perturbation attack, tries to find perturbations that are most likely to cause misclassification, with the constraint that the norm of the perturbations cannot exceed a given level. Since the perturbation level is fixed, fix-perturbation attacks may fail to find any adversarial samples for inputs that are far away from the decision boundary. The second paradigm, called the zero-confidence attack, tries to find the smallest perturbations that are guaranteed to cause misclassification, regardless of how large the perturbations are. Since they aim to minimize the perturbation norm, zero-confidence attacks usually find adversarial samples that ride right on the decision boundaries, and hence the name "zero-confidence". The resulting perturbation norm is also known as the margin of an input feature to the decision boundary. Both of these paradigms are essentially constrained optimization problems. The former has a simple convex constraint (perturbation norm), but a non-convex target (classification loss or logit differences). In contrast, the latter has a non-convex constraint (classification loss or logit differences), but a simple convex target (perturbation norm).Despite their similarity as optimization problems, the two paradigms differ significantly in terms of difficulty. The fix-perturbation attack problem is easier. The state-of-the-art algorithms, including projected gradient descent (PGD) BID10 and distributional adversarial attack (Zheng et al., 2018) , can achieve both high efficiency and high success rate, and often come with theoretical convergence guarantee. On the other hand, the zero-confidence attack problem is much more challenging. Existing methods are either not strong enough or too slow. For example, DeepFool BID11 and fast gradient sign method (FGSM) BID3 BID7 b) linearizes the constraint, and solves the simplified optimization problem with a simple convex target and a linear constraint. However, due to the linearization approximation errors, the solution can be far from optimal. As another extreme, L-BFGS BID18 and Carlini-Wagner (CW) BID1 convert the optimization problem into a Lagrangian, and the Lagrangian multiplier is determined through grid search or binary search. These attacks are generally much stronger and theoretically grounded, but can be very slow.The necessity of developing a better zero-confidence attack is evident. The zero-confidence attack paradigm is a more realistic attack setting. More importantly, it aims to measure the margin of each individual token, which lends more insight into the data distribution and adversarial robustness. Motivated by this, we propose MARGINATTACK , a zero-confidence attack framework that is able to compute the margin with improved accuracy and efficiency. Specifically, MARGINATTACK iterates between two moves. The first move, called restoration move, linearizes the constraint and solves the simplified optimization problem, just like DeepFool and FGSM; the second move, called projection move, explores even smaller perturbations without changing the constraint values significantly. By construction, MARGINATTACK inherits the efficiency in DeepFool and FGSM, and improves over them in terms of accuracy with a convergence guarantee. Our experiments show that MARGINAT-TACK attack is able to compute a smaller margin than the state-of-the-art zero-confidence attacks, and matches the state-of-the-art fix-perturbation attacks. In addition, it runs significantly faster than CW, and in some cases comparable to DeepFool and FGSM. We have proposed MARGINATTACK, a novel zero-confidence adversarial attack algorithm that is better able to find a smaller perturbation that results in misclassification. Both theoretical and empirical analyses have demonstrated that MARGINATTACK is an efficient, reliable and accurate adversarial attack algorithm, and establishes a new state-of-the-art among zero-confidence attacks. What is more, MARGINATTACK still has room for improvement. So far, only two settings of a (k) and b (k) are developed, but MARGINATTACK will work for many other settings, as long as assumption 5 is satisfied. Authors hereby encourage exploring novel and better settings for the MARGINATTACK framework, and promote MARGINATTACK as a new robustness evaluation measure or baseline in the field of adversarial attack and defense. This supplementary material aims to prove Thm. 1. Without the loss of generality, K in Eq. (9) in set to 0. Before we prove the theorem, we need to introduce some lemmas. Lemma 1.1. If assumption 3 in Thm. 1 holds, then ∀x ∈ B DISPLAYFORM0 Proof. According to Eq. (5), for 2 norm, DISPLAYFORM1 for ∞ norm, DISPLAYFORM2 Lemma 1.2. Given all the assumptions in Thm. 1, where DISPLAYFORM3 and assuming DISPLAYFORM4 where DISPLAYFORM5 A and B are defined in Eq. (32).According to assumption 8, this implies DISPLAYFORM6 at the rate of at least 1/n ν .Proof. As a digression , the second term in Eq. FORMULA0 is well defined, because DISPLAYFORM7 is upper bounded by Lem. 1.1 and assumptions 3.Back to proving the lemma, we will prove that each restoration move will bring c(x (k) ) closer to 0, while each projection move will not change c(x (k) ) much.First, for the restoration move DISPLAYFORM8 The first line is from the generalization of Mean-Value Theorem with jump discontinuities, and ξ = tz (k) + (1 − t)x (k) and t is a real number in [0, 1]. The second line is from Eq. (4). The last line is from assumptions 4 and 7 and Eq. (19).Next, for the projection move DISPLAYFORM9 The first line is from the fact that assumption 3 implies that c(x) is M -Lipschitz continuous. DISPLAYFORM10 for some M d and M s . To see this, for 2 norm DISPLAYFORM11 where b is defined as the maximum perturbation norm ( 2 ) within B, i.e. DISPLAYFORM12 which is well defined because B is a tight set. For ∞ norm, DISPLAYFORM13 Note that Eq. (26) also holds for other norms. With Eq. (26) and assumption 8, Eq. FORMULA1 becomes DISPLAYFORM14 Combining Eqs. FORMULA1 and FORMULA2 we have DISPLAYFORM15 where DISPLAYFORM16 According to assumption 7, 0 < A < 1. Also, according to Eq. FORMULA1 , DISPLAYFORM17 and thus DISPLAYFORM18 If DISPLAYFORM19 Otherwise, Eq. (34) implies DISPLAYFORM20 This concludes the proof. Lemma 1.3. Given all the assumptions in Thm. 1, and assuming DISPLAYFORM21 Proof. First, for restoration move DISPLAYFORM22 δm 2 (38) Line 4 is given by Eq. (3). Line 5 is derived from Lem. 1.1. The last line is from Lem. 1.2.
This paper introduces MarginAttack, a stronger and faster zero-confidence adversarial attack.
{"src": "scitldr-AIC_train", "paper_id": "B1gHjoRqYQ"}