Exercise 02 - Solution

Neural Networks & Adversarial Examples

Reliable and Interpretable Artificial Intelligence

ETH Zurich

Problem 1. In this introductory exercise we will use a 3 layer toy network N . We

denote a layer as lA (x) := Ax, the ReLU-activation (Rectified Linear Unit) – which
applies max(xi , 0) elementwise – ReLU(x) = max(x, 0). We write

N (x) := (lC ◦ ReLU ◦lB ◦ ReLU ◦lA ) (x)

where ◦ denotes function composition and A, B ∈ R10×10 as well as C ∈ R3×10 are

matrices. Further, we let softmax(x) denote the softmax-function for x ∈ Rn ,

exi
softmax(x)i = Pn xj (1)
j=1 e

for i ∈ {1, . . . , n}.

Answer the following questions:

1. For the given matrices A, B, C what is the space of possible inputs to N , i.e. the
domain of N ?

2. For the given matrices A, B, C what is the space of possible outputs of N , i.e. the
codomain of N ? Can the output be seen as a vector of probabilities corresponding
to the class probabilities of a categorical distribution?

3. For the given matrices A, B, C what is the space of possible outputs of (softmax ◦N ),
i.e. the codomain of softmax ◦N ? Can the output be seen as a vector of probabil-
ities corresponding to the class probabilities of a categorical distribution?

4. If N is a classifier, for how many classes does it work? (Assuming the standard
usage of neural networks in classification.)

5. Assume N has been trained and you want to use it to for classification on an input
x. Do you use (softmax ◦N ) or N ? Justify your answer.

1
 6. For a data point x with label y = 2 you want to create an adversarial example x0
that is close to x (kx − x0 k∞ < ) and that classifies to y 0 = 1. Do you use an
untargeted or targeted attack?

7. You use the Fast Gradient Sign Method (FGSM) (cf. slides 26-28 of Lecture 2) to
compute the perturbation in question 6. Write down the necessary equations to
obtain x0 . Is the computation applied to N or softmax ◦N ?

8. (Coding) In [Link] you are provided with an implementation for N (for some
matrices A, B, C) in PyTorch1 . Follow the instructions there (does not assume
familiarity with PyTorch) and complete the code.2

Solution 1. We consider the function signature of the network step-by-step:

lA : R10 → R10
ReLU ◦lA : R10 → (R≥0 )10
lB ◦ ReLU ◦lA : R10 → R10
ReLU ◦lB ◦ ReLU ◦lA : R10 → (R≥0 )10
lC ◦ ReLU ◦lB ◦ ReLU ◦lA : R10 → R3 (2)

For x ∈ Rn the signature of the softmax function is:

n
X
n n
softmax(x) : R → [0, 1] and softmax(x)i = 1 (3)
i=1

We generally call the inputs to the softmax function logits. So N outputs the class logits
and softmax ◦N outputs the class probabilities.

We thus answer the questions:

1. R10 by eq. (2).

2. R3 by eq. (2). No. P

For an arbitrary y ∈ R3 normalization is not guaranteed, i.e.
there exists y with 3i=1 yi 6= 1.

3. [0, 1]3 by eqs. (2) and (3). Due to the properties of the softmax function (see
eq. (3)) any vector y output by a softmax function can be considered a probability
distribution, and is often treated as such in calculation.
1
[Link]
2
We provide short PyTorch examples along with the rest of the materials in the first exercises, but we
strongly recommend that you familiarize yourself with it ahead of the project.

2
4. 3. As by the answer to 3 we can treat the output of (softmax ◦N ) function as a
probability distribution over the 3 classes and train the network so that it puts the
highest probability on the class it believes to be correct.

5. As by the answer to 4, the output of (softmax ◦N ) can be seen as a probability

distribution over the classes. Picking argmaxc∈{1,...,3} (softmax ◦N ) (x)c gives us
the most probable class for x. Since

argmaxc∈{1,...,3} (softmax ◦N ) (x)c = argmaxc∈{1,...,3} N (x)c (4)

we can also just evaluate N , unless we explicitly also want the class probabilities.
To see why eq. (4) holds, let y = N (x) be the neural network logits and rewrite
eq. (1) as

e yi eyi
softmax(y)i = Pn yj =
j=1 e Z
Pn yj
where Z = j=1 e > 0 is fixed for a fixed vector y. Eq. (4) follows from the fact
eyi eyj
that yi ≤ yj ⇐⇒ Z ≤ Z .

6. As we have the specific target t = 1 we use a targeted attack.

7. x0 = x − η = x −  · sign (∇x losst (N (x))).

The remaining question is what loss to use. The original FGSM paper [2] sug-
gests to use the same loss that is used in training. However, this information is
not provided in the question. Since we are considering a classification task, it is
reasonable to assume the standard cross-entropy loss:
C
X
losst (x) = Cross-Entropy ((softmax ◦N ) (x), t) = − [c = t] log(softmax(N (x))c )
c=1
C
!
X
= −N (x)t + log(Z) = −N (x)t + log exp(N (x)c ) (5)
c=1
| {z }
(∗)

where the cross-entropy between a probability vector and a scalar t denotes the
cross-entropy between the probability vector and a distribution that puts all mass
on the category indicated by t, C indicates the number of classes (which is 3 in
this case) and [φ] is the Iverson Bracket.

Thus the overall attack becomes:

3
 x0 = x − η
C
!!!
X
= x −  · sign ∇x −N (x)t + log exp(N (x)c )
c=1
 
C
 !
 X 
= x +  · sign 
∇x N (x)t −∇x log exp(N (x)c ) 
 (6)
 c=1 
| {z }
(∗)

By eq. (6) we see that whether N or (softmax ◦N ) is used, is mostly a point of

semantics. The intuition is that we increase the logits target class in the ∇x N (x)t
term and at the same time decrease the logits of all other terms. Thus, we push
the classification more towards class t.

It would be reasonable to say that softmax ◦N yields the version discussed here
and the version using N would just drop the (∗) terms in eqs. (5) and (6). This
version would then only increase the logit for target class, but not decrease all
others. For adversarial examples we will only use the “proper” version given by
eq. (6).

(Optional) Eq. (6) can be expressed in terms of A, B, C and x by rewriting the

gradient computation as follows (the resulting equations are given as a reference
to the interested students):
C
!!
X
∇x −N (x)t + log exp(N (x)c ) =
c=1
C
1 X
− ∇x N (x)t + PC · exp(N (x)c )∇x N (x)c (7)
c=1 exp(N (x)c ) c=1

The ∇x N (x)i terms can be subsequently written as

∇x N (x)i = ∇x [C ReLU (B ReLU (Ax))]i
= ∇x Ci,: ReLU (B ReLU (Ax))
= (∇x ReLU (B ReLU (Ax)))T Ci,:
T

where Ci,: denotes the i-th row of C.

The derivative of a ReLU combined with matrix multiplication is given by

∇x ReLU (Ax) = R(Ax)∇x Ax = R(Ax)A

4
 where
(
1 if yi > 0
R(y) = diag(h(y)), h(y)i =
0 if yi < 0
and diag(y) denotes the diagonal matrix that has y on its diagonal.

By putting all of this together, we obtain

∇x N (x)i = (∇x ReLU (B ReLU (Ax)))T Ci,:

T

= (R(B ReLU(Ax))∇x B ReLU (Ax))T Ci,:

T

= (R(B ReLU(Ax))B∇x ReLU (Ax))T Ci,:

T

= (R(B ReLU(Ax))BR(Ax)∇x Ax)T Ci,:

T

= (R(B ReLU(Ax))BR(Ax)A)T Ci,:

T

= (Ci,: R(B ReLU(Ax))BR(Ax)A)T =: Fi (x)

and with this finally write the attack as

C
!
0 1 X
x = x + ε sign Ft (x) − PC · exp(N (x)c )Fc (x)
c=1 exp(N (x)c ) c=1

Luckily, we do not need to calculate all of this for each attack. We can perform a
backward-pass through the network back to the input (in a typical training process
this is just done back to each weight). So we can use a standard neural-network
toolkit such as PyTorch in the next question.

8. See fgsm [Link].

Note: Many of the questions in Task 1 are very open-ended or tricky questions in order
to promote longer considerations and discussions on your part and on the part of this
master solution. The questions on the exam will be much clearer.

Problem 2. Carlini and Wagner ([1]) (slides 32-43 in Lecture 2) state the following
(notation adapted to lecture notation):

We define an objective function obj such that f (x+η) = t if and only if objt (x+η) ≤ 0.
There are many possible choices for obj:
objt1 (x0 ) = − losst (x0 ) + 1 (8)
..
.

5
N is a neural network, similar to the first problem, and f (x) = argmaxk ((softmax ◦N ) (x))k
denotes a neural network making a classification. N (x) computes the network logits,
and f (x) is syntactic sugar for also making the classification. Assume that the network
can classify between C classes (0-indexed) and consider losst (x) to be the cross-entropy
loss on the neural network output N (x0 ), with t as the target label:
C−1
X
losst (x) = Cross-Entropy ((softmax ◦N ) (x), t) = − [c = t] log(softmax(N (x))c )
c=0

[φ] (called Iverson Brackets) evaluats to 1 if the predicate φ is true and to 0 otherwise.

1. Show that the statement (8) is wrong by giving a counterexample.

2. To correct this oversight you will need to adjust the definition of objt (x0 ). Make
these adjustments.

3. What is the additional key constraint in the Carlini-Wagner attacks in comparison

to FGSM?

4. Why do the authors introduce the proxy objective function objt (x + η)?

Solution 2.

1. Consider the output softmax(N (x0 )) = ( 0.30.7 ) and the target label t = 0. objt=0 (x0 )
1
evaluates to 0.64, but f (x0 ) = argmaxk N (x0 )k = 0 = t, i.e. we have objt=01 (x) >0
but the property f (x0 ) = t does hold. For t = 1 we observe a value of −0.20 for
the objective function, but f (x0 ) = 0 6= t.

2. Consider the new objective functions

objt1∗ (x0 ) = losst (x0 ) − 1 = − log (softmax ◦N ) (x0 )t − 1

and
1
objt1∗∗ (x0 ) = − log (softmax ◦N ) (x0 )t −1 = − logC (softmax ◦N ) (x0 )t −1



log(C)

Figure 1 shows the value of objt1 , objt1∗ and objt1∗∗ for a range of inputs. We observe
that as soon as softmax(N (x0 ))t ≥ 0.5 the objective objt1∗∗ becomes less than or
equal to 0 for C = 2. If we perform two-class classification this gives us the exact
statement from the paper: f (x + η) = t ⇐⇒ objt1∗∗ (x + η) ≤ 0. For classification
with n classes we obtain the statement from the lecture: objt1∗∗ (x + η) ≤ 0 =⇒
f (x + η) = t.

6
 objt1 (x0 )
objt1∗ (x0 )
objt1∗∗ (x0 )

4
2
0
−2
−4

0 0.1 0.3 0.5 0.7 0.9 1

softmax(N (x0 ))t

Figure 1: The objective function objt1 , objt1∗ and objt1∗∗ for different values of
softmax(N (x0 ))t and C = 2.

Note: This is a simple sign mistake, and a small shortcoming in discussing the formu-
lation. [1] is valuable research, and this small mistake does not change its contribution,
but it makes for a good introductory exercise.

3. Carlini and Wagner explicitly try to find adversarial examples x0 which are close
to the original x. Therefore, in their formulation of the optimization problem
they aim to minimize the distance between x and x0 , captured by the lp norm
kx − x0 kp = kηkp (for p ∈ {0, 2, ∞}). In contrast, the only guarantee that FGSM
gives is that x0 ∈ [x − , x + ] (the addition and subtraction being element-wise).
FGSM is designed to be fast, not optimal, in sense that it may not compute minimal
perturbation and the adversarial images may end up being too distorted for large
values of .

4. The objective function objt (x + η) is introduced in order to relax the hard discrete
constraint f (x + η) = t which is very difficult to integrate into a continuous
optimization problem.

Problem 3. In the lecture we also looked at the optimization problem phrases by [1]:

find η
minimize kηkp + c · obj(x + η)
such that x + η ∈ [0, 1]n

7
Optimizing the norm directly can be problematic, especially in the case of k · k∞ . In
this task we will investigate this and a surrogate term. To simplify the notation we will
assume that x and η are n-vectors here (although
P they are usually matrices representing
images). We define h(η) = kηk∞ and g(η) = ni=0 max(ηi − τ, 0) for some constant τ .

∂
1. Calculate ∂η h(η).

∂
2. Calculate ∂η g(η).

3. Instantiate the above derivatives for η = (1.00001, 1.0, 1.0, 1.0, 0.001, 0.001)T and
for τ = 0.9 and τ = 2.0.

4. What is a problem when minimizing h(η) with gradient decent?

5. Does g(η) suffer the same problem?

Solution 3.
(
∂ 1 if i ∈ argmaxk (|ηk |)
h(η) =
∂ηi 0 else
(
∂ 1 if ηi > τ
g(η) =
∂ηi 0 else

∂
Note that for ∂η h(η) there could be multiple maxima. Mathematically there is no
defined derivative then, however in automatic differentiation engines such as PyTorch
the derivative is 1 for all maxima. For this exercise either definition is fine.

∂
Instantiating the above derivatives for the given η we obtain ∂η h(η) = (1.0, 0, 0, 0, 0, 0),
∂ ∂
∂η g(η)τ =0.9 = (1.0, 1.0, 1.0, 1.0, 0, 0) and ∂η g(η)τ =2.0 = (0, 0, 0, 0, 0, 0).

When optimizing h(η) with gradient decent we are always only optimizing the component
of η with the largest absolute value. This can yield to gradient decent running many
iterations in the best case or – more likely – oscillation between minimizing a few values,
as decreasing one component might increase others (due to the obj-term), as discussed
in the lecture.

Using g(η) can mitigate this problem for a well-chosen τ . [1] suggest to lower τ during
the optimization procedure in order to produce a solution η with small L∞ -norm. Also
note that g(η) only works in the case where we expect the entries ofPη to be positive. To
be a closer surrogate to the L∞ -norm we could instead use g ∗ (η) = ni=0 max(|ηi |−τ, 0).
However for optimizing in η ∈ [0, 1]n this does not matter.

8
References

[1] Nicholas Carlini and David A. Wagner. “Towards Evaluating the Robustness of
Neural Networks”. In: 2017 IEEE Symposium on Security and Privacy, SP 2017,
San Jose, CA, USA, May 22-26, 2017. IEEE Computer Society, 2017, pp. 39–57.
doi: 10.1109/SP.2017.49. url: [Link]
[2] Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. “Explaining and Har-
nessing Adversarial Examples”. In: 3rd International Conference on Learning Rep-
resentations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track
Proceedings. Ed. by Yoshua Bengio and Yann LeCun. 2015. url: [Link]
org/abs/1412.6572.