ECE595 / STAT598: Machine Learning I Lecture 33 Adversarial Attack: An .
ECE595 / STAT598: Machine Learning I Lecture 33 Adversarial Attack: An Overview Spring 2020 Stanley Chan School of Electrical and Computer Engineering Purdue University c Stanley Chan 2020. All Rights Reserved. 1 / 33
Today’s Agenda We have studied Part 1: Basic learning pipeline Part 2: Algorithms Part 3: Learning theory Now, we want to study the robustness of learning algorithms Robustness easiness to fail when input is perturbed. Perturbation can be in any kind. Robust machine learning is a very rich topic. In the past, we have robust SVM, robust kernel regression, robust PCA, etc. More recently, we have transfer learning etc. In this course, we will look at something very narrow, called adversarial robustness. That is, robustness against attacks. Adversarial attack is a very hot topic, as of today. We should not over-emphasize its importance. There are many other important problems. 2 / 33 c Stanley Chan 2020. All Rights Reserved.
Outline Lecture 33 Overview Lecture 34 Min-distance attack Lecture 35 Max-loss attack and regularized attack Today’s Lecture What are adversarial attacks? The surprising findings by Szegedy (2013) and Goodfellow (2014) Examples of attacks Physical attacks Basic terminologies Defining attack Multi-class problem Three forms of attack Objective function and constraint sets c Stanley Chan 2020. All Rights Reserved. 3 / 33
A Report in 2017 c Stanley Chan 2020. All Rights Reserved. 4 / 33
Adversarial Attack Example: FGSM It is not difficult to fool a classifier The perturbation could be perceptually not noticeable Goodfellow et al. “Explaining and Harnessing Adversarial Examples”, https://arxiv.org/pdf/1412.6572.pdf c Stanley Chan 2020. All Rights Reserved. 5 / 33
Adversarial Attack Example: Szegedy’s 2013 Paper This paper actually appears one year before Goodfellow’s 2014 paper. Szegedy et al. Intriguing properties of neural networks https://arxiv.org/abs/1312.6199 c Stanley Chan 2020. All Rights Reserved. 6 / 33
Adversarial Attack: Targeted Attack Targeted Attack Adversarial Examples Detection in Deep Networks with Convolutional Filter Statistics, https://arxiv.org/abs/1612.07767 c Stanley Chan 2020. All Rights Reserved. 7 / 33
Adversarial Attack Example: One Pixel One-pixel Attack One pixel attack for fooling deep neural networks https://arxiv.org/abs/1710.08864 c Stanley Chan 2020. All Rights Reserved. 8 / 33
Adversarial Attack Example: Patch Adding a patch LaVAN: Localized and Visible Adversarial Noise, https://arxiv.org/abs/1801.02608 c Stanley Chan 2020. All Rights Reserved. 9 / 33
Adversarial Attack Example: Stop Sign The Michigan / Berkeley Stop Sign Robust Physical-World Attacks on Deep Learning Models https://arxiv.org/abs/1707.08945 c Stanley Chan 2020. All Rights Reserved. 10 / 33
Adversarial Attack Example: Turtle The MIT 3D Turtle Synthesizing Robust Adversarial Examples https://arxiv.org/pdf/1707.07397.pdf https://www.youtube.com/watch?v YXy6oX1iNoA c Stanley Chan 2020. All Rights Reserved. 11 / 33
Adversarial Attack Example: Toaster Google Toaster Adversarial Patch https://arxiv.org/abs/1712.09665 https://www.youtube.com/watch?v i1sp4X57TL4 c Stanley Chan 2020. All Rights Reserved. 12 / 33
Adversarial Attack Example: Glass CMU Glass Accessorize to a Crime: Real and Stealthy Attacks on State-of-the-Art Face Recognition https://www.cs.cmu.edu/ sbhagava/papers/face-rec-ccs16.pdf https://www.archive.ece.cmu.edu/ lbauer/proj/advml.php c Stanley Chan 2020. All Rights Reserved. 13 / 33
Adversarial Attack: A Survey in 2017 Adversarial Examples: Attacks and Defenses for Deep Learning https://arxiv.org/abs/1712.07107 c Stanley Chan 2020. All Rights Reserved. 14 / 33
Outline Lecture 33 Overview Lecture 34 Min-distance attack Lecture 35 Max-loss attack and regularized attack Today’s Lecture What are adversarial attacks? The surprising findings by Szegedy (2013) and Goodfellow (2014) Examples of attacks Physical attacks Basic terminologies Defining attack Multi-class problem Three forms of attack Objective function and constraint sets c Stanley Chan 2020. All Rights Reserved. 15 / 33
Definition: Additive Adversarial Attack Definition (Additive Adversarial Attack) Let x 0 Rd be a data point belong to class Ci . Define a target class Ct . An additive adversarial attack is an addition of a perturbation r Rd such that the perturbed data x x0 r is misclassified as Ct . c Stanley Chan 2020. All Rights Reserved. 16 / 33
Definition: General Adversarial Attack Definition (Adversarial Attack) Let x 0 Rd be a data point belong to class Ci . Define a target class Ct . An adversarial attack is a mapping A : Rd Rd such that the perturbed data x A(x 0 ) is misclassified as Ct . c Stanley Chan 2020. All Rights Reserved. 17 / 33
Example: Geometric Attack Fast Geometrically-Perturbed Adversarial Faces (WACV 2019) https://arxiv.org/pdf/1809.08999.pdf c Stanley Chan 2020. All Rights Reserved. 18 / 33
The Multi-Class Problem Approach 1: One-on-One Class i VS Class j Give me a point, check which class has more votes There is an undetermined region c Stanley Chan 2020. All Rights Reserved. 19 / 33
The Multi-Class Problem Approach 2: One-on-All Class i VS not Class i Give me a point, check which class has no conflict There are undetermined regions c Stanley Chan 2020. All Rights Reserved. 20 / 33
The Multi-Class Problem Approach 3: Linear Machine Every point in the space gets assigned a class. You give me x , I compute g1 (x ), g2 (x ), . . . , gK (x ). If gi (x ) gj (x ) for all j 6 i, then x belongs to class i. c Stanley Chan 2020. All Rights Reserved. 21 / 33
Correct Classification We are mostly interested the linear machine problem. Let us try to simplify the notation. The statement: If gi (x ) gj (x ) for all j 6 i, then x belongs to class i. is equivalent to (asking everyone to be less than 0) g1 (x ) gi (x ) 0 . . gk (x ) gi (x ) 0, and is also equivalent to (asking the worst guy to be less than 0) max{gj (x )} gi (x ) 0 j6 i Therefore, if I want to launch an adversarial attack, I want to move you to class t: max {gj (x )} gt (x ) 0. j6 t c Stanley Chan 2020. All Rights Reserved. 22 / 33
Our Approach Here is what we are going to do First, we will preview the three equivalent forms of attack: Minimum Distance Attack: Minimize the perturbation magnitude while accomplishing the attack objective Maximum Loss Attack: Maximize the training loss while ensuring perturbation is controlled Regularization-based Attack: Use regularization to control the amount of perturbation Then, we will try to understand the geometry of the attacks. We will look at the linear classifier case to gain insights. c Stanley Chan 2020. All Rights Reserved. 23 / 33
Minimum Distance Attack Definition (Minimum Distance Attack) The minimum distance attack finds a perturbed data optimization minimize x subject to x by solving the kx x 0 k (1) maxj6 t {gj (x )} gt (x ) 0, where k · k can be any norm specified by the user. I want to make you to class Ct . So the constraint needs to be satisfied. But I also want to minimize the attack strength. This gives the objective. c Stanley Chan 2020. All Rights Reserved. 24 / 33
Maximum Loss Attack Definition (Maximum Loss Attack) The maximum loss attack finds a perturbed data x by solving the optimization maximize gt (x ) maxj6 t {gj (x )} x subject to kx x 0 k η, (2) where k · k can be any norm specified by the user, and η 0 denotes the attack strength. I want to bound my attack kx x 0 k η I want to make gt (x ) as big as possible So I want to maximize gt (x ) maxj6 t {gj (x )} This is equivalent to minimize x subject to maxj6 t {gj (x )} gt (x ) kx x 0 k η, c Stanley Chan 2020. All Rights Reserved. 25 / 33
Regularization-based Attack Definition (Regularization-based Attack) The regularization-based attack finds a perturbed data optimization minimize x x by solving the kx x 0 k λ (maxj6 t {gj (x )} gt (x )) (3) where k · k can be any norm specified by the user, and λ 0 is a regularization parameter. Combine the two parts via regularization By adjusting ( , η, λ), all three will give the same optimal value. c Stanley Chan 2020. All Rights Reserved. 26 / 33
Understanding the Geometry: Objective Function 0 -norm: ϕ(x ) kx x 0 k0 , which gives the most sparse solution. Useful when we want to limit the number of attack pixels. 1 -norm: ϕ(x ) kx x 0 k1 , which is a convex surrogate of the 0 -norm. -norm: ϕ(x ) kx x 0 k , which minimizes the maximum element of the perturbation. c Stanley Chan 2020. All Rights Reserved. 27 / 33
Understanding the Geometry: Constraint The constraint set is Ω {x max{gj (x )} gt (x ) 0} j6 t We can write Ω as Ω x g1 (x ) gt (x ) 0 g2 (x ) gt (x ) 0 . . gk (x ) gt (x ) 0 Remark: If you want to replace max by i , then i is a function of x : Ω x gi (x ) (x ) gt (x ) 0 . c Stanley Chan 2020. All Rights Reserved. 28 / 33
Understanding the Geometry: Constraint c Stanley Chan 2020. All Rights Reserved. 29 / 33
Linear Classifier Let us take a closer look at the linear case. Each discriminant function takes the form gi (x ) w T i x wi,0 . The decision boundary between the i-th class and the t-th class is therefore g (x ) (w i w t )T x wi,0 wt,0 0. The constraint set Ω is T w 1 w Tt w1,0 wt,0 . . . . T T w t 1 w t x wt 1,0 wt,0 0 w T w T wt 1,0 wt,0 t t 1 . . . . T T wk,0 wt,0 wk wt AT x b c Stanley Chan 2020. All Rights Reserved. 30 / 33
Linear Classifier You can show Ω {AT x b } is convex. But the complement Ωc {AT x b } is not convex. So targeted attack is easier to analyze than untargeted attack. c Stanley Chan 2020. All Rights Reserved. 31 / 33
Attack: The Simplest Example The optimization is: minimize x subject to kx x 0 k maxj6 t {gj (x )} gt (x ) 0, Suppose we use 2 -norm, and consider linear classifiers, then the attack is given by minimize kx x 0 k2 subject to x AT x b, This is a quadratic programming problem. We will discuss how to solve this problem analytically. c Stanley Chan 2020. All Rights Reserved. 32 / 33
Summary Adversarial attack is a universal phenomenon for any classifier. Attacking deep networks are popular because people think that they are unbeatable. There is really nothing too magical behind adversarial attack. All attacks are based on one of the three forms of attacks. Deep networks are trickier, as we will see, because the internal model information is not easy to extract. We will learn the basic principles of attacks, and try to gain insights from linear models. c Stanley Chan 2020. All Rights Reserved. 33 / 33
Maximum Loss Attack De nition (Maximum Loss Attack) The maximum loss attack nds a perturbed data x by solving the optimization maximize x g t(x ) max j6 t fg j(x )g subject to kx x 0k ; (2) where kkcan be any norm speci ed by the user, and 0 denotes the attack strength. I want to bound my attack kx x 0k I want to make g t(x ) as big as possible
Texts of Wow Rosh Hashana II 5780 - Congregation Shearith Israel, Atlanta Georgia Wow ׳ג ׳א:׳א תישארב (א) ׃ץרֶָֽאָּהָּ תאֵֵ֥וְּ םִימִַׁ֖שַָּה תאֵֵ֥ םיקִִ֑לֹאֱ ארָָּ֣ Îָּ תישִִׁ֖ארֵ Îְּ(ב) חַורְָּ֣ו ם
Learning is feasible if x p(x) p(x) says: Training and testing are related If training and testing are u
Lecture 1: Linear regression: A basic data analytic tool Lecture 2: Regularization: Constraining the solution Lecture 3: Kernel Method: Enabling nonlinearity Lecture 2: Regularization Ridge Regression Regularization Parameter LASSO
Lecture 1: Linear regression: A basic data analytic tool Lecture 2: Regularization: Constraining the solution Lecture 3: Kernel Method: Enabling nonlinearity Lecture 1: Linear Regression Linear Regression Notation Loss Function Solving the Regression Problem Geome
Convex Optimization for Logistic Regression We can use CVX to solve the logistic regression problem But it requires some re-organization of the equations J( ) XN n 1 n y n Tx n log(1 h (x n)) o XN n 1 n y n Tx n log 1 e Tx n 1 e Tx n! o XN n 1 n y n Tx n log 1 e Tx n o 8 : XN n 1 y nx n! T XN n 1 log 1 e Tx n 9 ;: The last .
Is Logistic Regression Better than Linear? Scenario 1: Identical Covariance. Equal Prior. Enough samples. N(0;1) with 100 samples and N(10;1) with 100 samples. Linear and logistic: Not much di erent.-5 0 5 10 15 0 0.2 0.4 0.6 0.8 1 Bayes oracle Bayes empirical lin reg lin reg decision log reg log reg decision
decoration machine mortar machine paster machine plater machine wall machinery putzmeister plastering machine mortar spraying machine india ez renda automatic rendering machine price wall painting machine price machine manufacturers in china mail concrete mixer machines cement mixture machine wall finishing machine .
The most popular agile methodologies include: extreme programming (XP), Scrum, Crystal, Dynamic Sys-tems Development (DSDM), Lean Development, and Feature Driven Development (FDD). All Agile methods share a common vision and core values of the Agile Manifesto. Agile Methods: Some well-known agile software development methods include: Agile .
