# The Feasibility and Inevitability of Stealth Attacks

Ivan Y. Tyukin
University of Leicester
Leicester, LE1 7RH, UK
<EMAIL_ADDRESS>
Corresponding Author Desmond J. Higham
University of Edinburgh
Edinburgh, EH9 3FD, UK
<EMAIL_ADDRESS>
Eliyas Woldegeorgis
University of Leicester
Leicester, LE1 7RH, UK
<EMAIL_ADDRESS>
Alexander N. Gorban
University of Leicester
Leicester, LE1 7RH, UK
<EMAIL_ADDRESS>

###### Abstract

We develop and study new adversarial perturbations that enable an attacker to
gain control over decisions in generic Artificial Intelligence (AI) systems
including deep learning neural networks. In contrast to adversarial data
modification, the attack mechanism we consider here involves alterations to
the AI system itself. Such a _stealth attack_ could be conducted by a
mischievous, corrupt or disgruntled member of a software development team. It
could also be made by those wishing to exploit a “democratization of AI”
agenda, where network architectures and trained parameter sets are shared
publicly. Building on work by [Tyukin et al., _International Joint Conference
on Neural Networks_ , 2020], we develop a range of new implementable attack
strategies with accompanying analysis, showing that with high probability a
stealth attack can be made transparent, in the sense that system performance
is unchanged on a fixed validation set which is unknown to the attacker, while
evoking any desired output on a trigger input of interest. The attacker only
needs to have estimates of the size of the validation set and the spread of
the AI’s relevant latent space. In the case of deep learning neural networks,
we show that a _one neuron attack_ is possible—a modification to the weights
and bias associated with a single neuron—revealing a vulnerability arising
from over-parameterization. We illustrate these concepts in a realistic
setting. Guided by the theory and computational results, we also propose
strategies to guard against stealth attacks.

##  1 Introduction

It is widely recognized that Artificial Intelligence (AI) systems can be
vulnerable to adversarial attacks [24]; that is, small, often imperceptible,
perturbations that exploit instabilities. The danger of an attacker gaining
control of an automated decision-making process is of particular concern in
high-stakes or safety-critical settings, including medical imaging [9],
transport [28] and textual analysis [8]. The last few years have therefore
seen an escalation in the design of both attack and defence strategies [1, 15,
22], and recent work has considered the bigger question of whether the
existence of successful attacks is inevitable [3, 21].

Work in this field has focused on adversarial perturbations to the training or
input data, and may be classified as black-box, grey-box or white-box,
depending on the level of information and access available to the attacker. We
look at a different setting, which was introduced in [26]. Here, the attacker
is assumed to have control of the AI system, in the sense of being able to
edit code or change parameters. We therefore consider attacks that make
perturbations to the system itself in an attempt to change the output on a
specific input point of interest to the attacker without any changes in the
AI’s performance on a large, unknown, validation set and without retraining.
We focus on two issues: (1) strategies for constructing such attacks and (2)
theoretical analysis of the likelihood of success.

In section 2 we present a general framework of open-box stealth attacks,
algorithms and their theoretical analysis. We reveal a new class of attacks
(Algorithms 1, 2) and establish conditions showing that the likelihood of
their success can be made arbitrarily close to one, for any fixed dimension of
model’s latent space (Theorem 1, Remark 1). This is a significant extension of
the previous state of knowledge as success likelihoods for such attacks were
thought to be limited by dimension [26]. To establish these high probabilities
of success, the attack must be executed with arbitrarily high accuracy and the
model must satisfy appropriate reachability conditions [15]. In section 3 we
discuss additional related work in the area. Section 4 presents experiments
illustrating the application of the theory in realistic settings and
demonstrates the strikingly likely feasibility of one neuron attacks—which
alter weights of just a single neuron. Section 5 concludes with
recommendations on how vulnerabilities we exposed in this work can be
mitigated by model design practices.

##  2 Stealth attacks

###  2.1 General framework

Consider a generic AI system, a map

$\mathcal{F}:{\mathcal{U}}\rightarrow\mathbb{R}$ (1)

producing some decisions on its outputs in response to an input from
$\mathcal{U}\subset\mathbb{R}^{m}$. The map $\mathcal{F}$ can define input-
output relationships for an entire deep neural network or some part (a sub-
graph), an ensemble of networks, a tree, or a forest. For the purposes of our
work, the AI system’s specific task is not relevant and can include
classification, regression, or density estimation.

The AI system has an Owner operating the AI. An Attacker wants to take
advantage of the AI by forcing it to make decisions in their favour. Conscious
about security, the Owner created a _validation set_ which is kept secret. The
validation set is a list of input-output pairs produced by the uncompromised
system (1). The Owner can monitor security by checking that the AI reproduces
these outputs. Now, suppose that the Attacker has access to the AI system but
not the validation set. The phrase _stealth attack_ was used in [26] to
describe the circumstance where the Attacker chooses a _trigger input_ and
_modifies the AI_ so that:

  * •

the Owner could not detect this modification by testing on the validation set,

  * •

on the the trigger input the modified AI produces the output desired by the
Attacker.

Figure 1 gives a schematic representation of this setup.

Figure 1: General scheme of an adversarial stealth attack

We note that the stealth attack setting is relevant to the case of a corrupt,
disgruntled or mischievous individual who is a member of a software
development team that is creating an AI system, or who has an IT-related role
where the system is deployed. In this scenario, the attacker will have access
to the AI system and, for example, in the case of a deep neural network, may
choose to alter the weights, biases or architecture. The scenario is also
pertinent to the “democratization of AI” agenda [2], since making available
copies of large-scale models and parameter sets across multiple public domain
repositories increases the opportunity for malicious intervention.

###  2.2 Formal definition of stealth attacks

Without loss of generality, it is convenient to represent the initial general
map (1) as a composition of two maps, $F$ and $\Phi$:

$\mathcal{F}=F\circ\Phi,\quad\text{where}\quad F:\
\mathbb{R}^{n}\rightarrow\mathbb{R},\
\Phi:\mathcal{U}\rightarrow\mathbb{R}^{n}.$ (2)

The map $\Phi$ defines general latent representation of inputs from
$\mathcal{U}$, whereas the map $F$ can be viewed as a decision-making part of
the AI system. In the context of deep learning models, latent representations
can be outputs of hidden layers in deep learning neural networks, and
decision-making parts could constitute operations performed by fully-connected
and softmax layers at the end of the networks. If $\Phi$ is an identity map
then setting $F=\mathcal{F}$ brings us to the initial general case (1).

An additional advantage of the compositional representation (2) is that it
enables explicit modelling of the focus of the adversarial attack – a part of
the AI system subjected to adversarial modification. This part will be
modelled by be the map $F$.

A perturbed, or attacked, map $F$ is defined as

$\begin{split}&{F}_{a}:{\mathbb{R}^{n}}\times\Theta\rightarrow\mathbb{R}\\\
&{F}_{a}(\cdot,\boldsymbol{\theta})={F}(\cdot)+\mathfrak{A}(\cdot,\boldsymbol{\theta}),\end{split}$
(3)

where the term
$\mathfrak{A}:{\mathbb{R}^{n}}\times\Theta\rightarrow\mathbb{R}$ models the
effect of an adversarial perturbation, and $\Theta\subset\mathbb{R}^{m}$ is a
set of relevant parameters. Such adversarial perturbations could take
different forms including modification of parameters of the map $F$ and
physical addition or removal of components involved in computational processes
in the targeted AI system. In neural networks, parameters are weights and
biases of a neuron or a group of neurons, and components are neurons
themselves. As we shall see later, a particularly instrumental case occurs
when the term $\mathfrak{A}$ is just a single Rectified Linear Unit (ReLU
function), [13],

$\mathfrak{A}(\cdot,(\boldsymbol{w},b))=D\,\mathrm{ReLU}((\cdot,\boldsymbol{w})-b)\quad\text{where}\quad\mathrm{ReLU}(s)=\max\\{s,0\\},$
(4)

or a sigmoid (see [11], [14] for further information on activation functions
of different types)

$\mathfrak{A}(\cdot,(\boldsymbol{w},b))=D\,\sigma((\cdot,\boldsymbol{w})-b),\quad\text{where}\quad\sigma(s)=\frac{1}{1+\exp(-s)}.$
(5)

Here, $D\in\mathbb{R}$ is some constant, and
$(\boldsymbol{w},b)=\boldsymbol{\theta}$ are parameters of the perturbation
$\mathfrak{A}$.

Having introduced all relevant notations, we are now ready to provide a formal
statement of the problem of stealth attacks introduced in Section 2.1.

######  Problem 1 (Stealth Attack on $\mathcal{F}$)

Consider a classification map $\mathcal{F}$ defined by (1), (2). Suppose that
an owner of the AI system or a network has a finite validation or verification
set $\mathcal{V}\subset{\mathcal{U}}$. The validation set $\mathcal{V}$ is
kept secret and is assumed to be unknown to an attacker. The cardinality of
$\mathcal{V}$ is bounded from above by some constant $M$, and this bound is
known to the attacker.

The attacker seeks to modify the map $F$ in $\mathcal{F}$ and replace it by
${F}_{a}$ constructed such that for some given $\varepsilon>0$,
$\Delta\in\mathbb{R}$ and an element $\boldsymbol{u}^{\prime}\in\mathcal{U}$,
known to the attacker but unknown to the owner of the map $\mathcal{F}$, the
following properties hold:

$\begin{split}&|F\circ\Phi(\boldsymbol{u})-F_{a}\circ\Phi(\boldsymbol{u})|\leq\varepsilon\
\mbox{for all}\ \boldsymbol{u}\in\mathcal{V}\\\
&|{F}\circ\Phi(\boldsymbol{u}^{\prime})-{F}_{a}\circ\Phi(\boldsymbol{u}^{\prime})|\geq\Delta.\end{split}$
(6)

In words, when $F$ is perturbed to ${F}_{a}$ the output is changed by no more
than $\varepsilon$ on the validation set, but is changed by at least $\Delta$
on the trigger, $\boldsymbol{u}^{\prime}$

###  2.3 New stealth attack algorithms

In this section we introduce two algorithms for generating stealth attacks on
a generic AI system. These algorithms return a ReLU or a sigmoid neuron
realizing adversarial perturbation $\mathfrak{A}$. Implementation of these
algorithms will rely upon some mild additional information about the unknown
validation set $\mathcal{V}$. In particular, we request that latent
representations $\Phi(\boldsymbol{u})$ for all $\boldsymbol{u}\in\mathcal{V}$
are located within some ball $\mathbb{B}_{n}(0,R)$ whose radius $R$ is known
to the attacker. We state this requirement in Assumption 1.

######  Assumption 1 (Latent representations of the validation data
$\mathcal{V}$)

There is an $R>0$, known to the attacker, such that

$\Phi(\boldsymbol{u})\in\mathbb{B}_{n}(0,R)\ \mbox{for all}\
\boldsymbol{u}\in\mathcal{V}.$ (7)

Given that the set $\mathcal{V}$ is finite, infinitely many such balls exist.
Here we request that the attacker knows just a single value of $R$ for which
(7) holds. The value of $R$ does not have to be the smallest possible.

Our first stealth attack algorithm is presented in Algorithm 1. The algorithm
produces a modification of the relevant part $F$ of the original AI system
that is implementable by a single ReLU or sigmoid function. Regarding the
trigger input, $\boldsymbol{u}^{\prime}$, the algorithm relies on another
process (see step 3) returning a solution of (9), (10) for some
$\alpha\in[0,1)$. A candidate for this process is an algorithm solving the
following constrained nonlinear optimisation problem parameterised by
$\boldsymbol{x},R,\delta,\gamma$:

$\boldsymbol{u}^{\prime}=\arg\min_{\boldsymbol{u}\in\mathcal{U}}\left\|\Phi(\boldsymbol{u})R^{-1}-\boldsymbol{x}\right\|\quad\text{s.~{}t.}\quad\gamma\left\|\Phi(\boldsymbol{u})R^{-1}\right\|\leq
1,\ \left\|\Phi(\boldsymbol{u})R^{-1}-\boldsymbol{x}\right\|<\delta.$ (8)

The value of $\alpha$ which Algorithm 1 must return could then be calculated
as $\alpha=\left\|{\Phi(\boldsymbol{u})}/R-\boldsymbol{x}\right\|/\delta$.
Note also that a choice of $\kappa,D$ in step 4 of the algorithm so that (12)
is satisfied is always possible.

Algorithm 1 Single-neuron plain stealth attack

Input: $\delta\in(0,1]$, $\gamma\in(0,1)$, $\Delta,\varepsilon\geq 0$, a
sigmoid or a ReLU function $g$, and $R$ satisfying (7).

1:procedure Adversarial stealth perturbation($\delta,\Delta,\varepsilon,g$)

2: Draw a random vector $\boldsymbol{x}$ from the equidistribution in the
sphere ${\mathbb{S}_{n-1}}(0,\delta)$, $\delta\in(0,1]$.

3: Generate an input $\boldsymbol{u}^{\prime}\in\mathcal{U}$ such that
$\boldsymbol{x}^{\prime}=\Phi(\boldsymbol{u}^{\prime})/{R}$ is within a
$\alpha\delta$-distance from $\boldsymbol{x}$:
$\|\boldsymbol{x}^{\prime}-\boldsymbol{x}\|\leq\alpha\delta,$ (9) and
$\gamma\|\boldsymbol{x}^{\prime}\|\leq 1.$ (10) Parameter $\alpha\in[0,1)$
determines a degree of accuracy of the attack’s implementation.

4: Set
$\mathfrak{A}\left(\cdot,\left(\kappa\boldsymbol{x}^{\prime}R^{-1},b\right)\right)=Dg\left(\left(\cdot,\kappa\boldsymbol{x}^{\prime}R^{-1}\right)-b\right),\quad\text{with}\quad
b=0.5\kappa\left(1+\gamma\right)\|\boldsymbol{x}^{\prime}\|^{2},$ (11) where
$\kappa$ and $D$ are chosen so that
$\begin{split}&Dg\left(-0.5\kappa(1-\gamma)\|\boldsymbol{x}^{\prime}\|^{2}\right)\leq\varepsilon\
\mbox{and}\
Dg\left(0.5\kappa(1-\gamma)\|\boldsymbol{x}^{\prime}\|^{2}\right)\geq\Delta.\end{split}$
(12)

Output: trigger $\boldsymbol{u}^{\prime}$, parameter $\alpha\in[0,1)$, weight
vector $\boldsymbol{w}=\kappa\boldsymbol{x}^{\prime}R^{-1}$, bias
$b=0.5\kappa\left(1+\gamma\right)\|\boldsymbol{x}^{\prime}\|^{2}$, and output
gain $D$ of the sigmoid or ReLU function $g$.

Performance of Algorithm 1 in terms of the probability of producing a
successful stealth attack is characterised by Theorem 1 below.

###### Theorem 1

Consider Algorithm 1, and let parameters $\gamma\in(0,1)$, $\alpha\in[0,1)$,
and $\delta\in(0,1]$ be such that

$\varphi(\gamma,\delta,\alpha)=\cos(\arccos(\gamma(1-\alpha)\delta)+\arccos((1-\alpha^{2})^{1/2}))>0.$
(13)

Then the probability $P_{a,1}$ that Algorithm 1 returns a solution to Problem
1 is bounded from below as

$P_{a,1}\geq
1-M\pi^{-1/2}\frac{\Gamma\left(\frac{n}{2}\right)}{\Gamma\left(\frac{n-1}{2}\right)}\int_{0}^{\arccos{(\varphi(\gamma,\delta,\alpha))}}\sin^{n-2}(\theta)d\theta.$
(14)

In particular

$P_{a,1}\geq
1-M\frac{1}{2\pi^{\frac{1}{2}}}\frac{\Gamma\left(\frac{n}{2}\right)}{\Gamma\left(\frac{n}{2}+\frac{1}{2}\right)}\frac{1}{\varphi(\gamma,\delta,\alpha)}\left(1-\varphi(\gamma,\delta,\alpha)^{2}\right)^{\frac{n-1}{2}}.$
(15)

A proof of Theorem 1 is provided in Supplementary Material, Section S.1. Here
we will discuss the main implications of this result.

######  Remark 1 (Determinants of success and vulnerabilities)

Theorem 1 establishes explicit connections between intended parameters of the
trigger $\boldsymbol{u}^{\prime}$ (expressed by
$\Phi(\boldsymbol{u}^{\prime})/R$ which is to be maintained within
$\delta\alpha$ from $\boldsymbol{x}$), dimension $n$ of the AI’s latent space,
accuracy of solving (8) (expressed by the value of $\alpha$ \- the smaller the
better), design parameter $\gamma\in(0,1)$ and $\delta\in(0,1]$, and
vulnerability of general AI systems to stealth attacks.

In general, the larger the value of $n$ for which solutions of (8) can be
found without increasing the values of $\alpha$, the higher the probability
that the attack produced by Algorithm 1 is successful. Similarly, the larger
the value of $n$, the smaller the value of $\gamma$ required. Consequently,
stealth attacks can be implemented with the smaller weights $\boldsymbol{w}$
and biases $b$. At the same time, if no explicit restrictions on $\delta$ and
weights are imposed then Theorem 1 suggests that if one picks $\delta=1$,
$\gamma$ sufficiently close to $1$, and $\alpha$ sufficiently close to $0$,
then subject to finding an appropriate solution of (8) (c.f. the notion of
reachability [15]), one can create stealth attacks whose probabilities of
success can be made arbitrary close to $1$ for any fixed $n$. Indeed, if
$\alpha=0$ then the right-hand side of (15) becomes

$1-M\frac{1}{2\pi^{\frac{1}{2}}}\frac{\Gamma\left(\frac{n}{2}\right)}{\Gamma\left(\frac{n}{2}+\frac{1}{2}\right)}\frac{1}{\gamma\delta}\left(1-(\gamma\delta)^{2}\right)^{\frac{n-1}{2}}$
(16)

which, for any fixed $M$, $n$, can me made arbitrarily close to $1$ by an
appropriate choice of $\gamma,\delta\in(0,1]$.

######  Remark 2 (Tightness of bounds)

If the attacks are precise, i.e. $\alpha=0$, bound (14) is asymptotically
tight for sigmoid $g$: there exist sets $\mathcal{V}:|\mathcal{V}|\leq M$ such
that for $n$ sufficiently large bound (14) holds as an equality. If
$\alpha\in(0,1)$ then bounds (14), (15) could be rather conservative.

######  Remark 3 (Arbitrary sign of adversarial perturbation)

Although Problem 1 does not impose any requirements on the sign of
$\mathfrak{A}\left(\Phi(\boldsymbol{u}^{\prime}),(\boldsymbol{w},b)\right)$,
this quantity can be made positive or negative through the choice of $D$.

######  Remark 4 (Precise attacks with ReLU units)

One of the original requirements for a stealth attack is to produce a response
to a trigger input $\boldsymbol{u}^{\prime}$ such that
$|{F}\circ\Phi(\boldsymbol{u}^{\prime})-{F}_{a}\circ\Phi(\boldsymbol{u}^{\prime})|$
exceeds an a-priory given value $\Delta$. However, if the attack is
implemented with a ReLU unit then one can select the values of
$\boldsymbol{w},b$ so that
$|{F}\circ\Phi(\boldsymbol{u}^{\prime})-{F}_{a}\circ\Phi(\boldsymbol{u}^{\prime})|=\Delta$.
Indeed for a ReLU neuron, condition (12) reduces to

$0.5D\left(\kappa(1-\gamma)\|\boldsymbol{x}^{\prime}\|^{2}\right)\geq\Delta.$

Hence picking
$\kappa=2{\Delta}\left((1-\gamma)\|\boldsymbol{x}^{\prime}\|^{2}\right)^{-1}$
and $D=1$ results in the desired output. Moreover, ReLU units produce
adversarial perturbations $\mathfrak{A}$ with $\varepsilon=0$. These zero-
tolerance attacks, if successful, do not change $\mathcal{F}$ on the
validation set $\mathcal{V}$ and as such are completely undetectable on
$\mathcal{V}$.

###### Remark 5

(Hiding adversarial perturbations in redundant deep learning structures)
Algorithm 1 (as well as its input-specific version, Algorithm 2, below)
implements adversarial perturbations by adding a single sigmoid or ReLU
neuron. A question therefore arises, if one can “plant” or “hide” a stealth
attack within an existing AI structure. Intuitively, over-parametrisation and
redundancies in many deep learning architectures should provide ample
opportunities precisely for this sort of malevolent action. As we empirically
justify in Section 4, this may indeed be possible. In these experiments, we
looked at a neural network with $L$ layers. The map $F$ corresponded to the
last $k+1$ layers: $L-k,\dots,L$, $k\geq 1$. We looked for a neuron in layer
$L-k$ whose output weights have the smallest $L_{1}$-norm of all neurons in
that layer (see Supplementary Material, Section S.3.6). This neuron was then
replaced with a neuron implementing our stealth attack, and its output weights
were wired so that a given trigger input $\boldsymbol{u}^{\prime}$ evoked the
response we wanted from this trigger. This new type of one neuron attack may
be viewed as the stealth version of a one pixel attack [23]. Surprisingly,
this approach worked consistently well across various randomly initiated
instances of the same network. These experiments suggest a real non-
hypothetical possibility of turning a needle in a haystack (a redundant
neuron) into a pebble in a shoe (a malevolent perturbation).

The attack and the trigger $\boldsymbol{u}^{\prime}\in\mathcal{U}$ constructed
in Algorithm 1 are in some sense “arbitrary”. As opposed to standard
adversarial examples, they are not linked or targeting any specific input.
Hence a question arises: Is it possible to create a targeted adversarial
perturbation of the AI which is triggered by an input
$\boldsymbol{u}^{\prime}\in\mathcal{U}$ located in a vicinity of some
specified input, $\boldsymbol{u}^{\ast}$.

As we shall see shortly, this may indeed be possible through some
modifications to Algorithm 1. For technical convenience and consistency, we
introduce a slight reformulation of Assumption 1.

######  Assumption 2 (Relative latent representations of the validation data
$\mathcal{V}$)

Let $\boldsymbol{u}^{\ast}\in\mathcal{U}$ be a target input of interest to the
attacker. There is an $R>0$, also known to the attacker, such that

$\Phi(\boldsymbol{u})-\Phi(\boldsymbol{u}^{\ast})\in\mathbb{B}_{n}(0,R)\
\mbox{for all}\ \boldsymbol{u}\in\mathcal{V}.$ (17)

We note that Assumption 2 follows immediately from Assumption 1 if the latent
representation $\Phi(\boldsymbol{u}^{\ast})$ of the input
$\boldsymbol{u}^{\ast}$ is known. Indeed, if $R^{\prime}$ is a value of $R$
for which (7) holds then (17) holds true with
$R=R^{\prime}+\|\Phi(\boldsymbol{u}^{\ast})\|$.

Algorithm 2 provides a recipe for creating such targeted attacks.

Algorithm 2 Single-neuron targeted stealth attack

Input: $\delta\in(0,1]$, $\alpha\in[0,1)$ $\gamma\in(0,1)$,
$\Delta,\varepsilon\geq 0$, a sigmoid or a ReLU function $g$, a target input
$\boldsymbol{u}^{\ast}\in\mathcal{U}$, and $R$ for which (17) holds.

1:procedure Targeted adversarial stealth
perturbation($\delta,\alpha,D,\varepsilon,g$)

2: Draw a random vector $\boldsymbol{x}$ from the equidistribution in the
sphere ${\mathbb{S}_{n-1}}(0,\delta)$, $\delta\in(0,1]$.

3: Generate an input $\boldsymbol{u}^{\prime}$ such that
$\boldsymbol{x}^{\prime}=(\Phi(\boldsymbol{u}^{\prime})-\Phi(\boldsymbol{u}^{\ast}))/R$
satisfies (9), (10).

4: Set
$\begin{split}&\mathfrak{A}\left(\cdot,\left(\kappa{\boldsymbol{x}^{\prime}}R^{-1},b\right)\right)=Dg\left(\left(\cdot,\kappa\boldsymbol{x}^{\prime}R^{-1}\right)-b\right),\\\
&b=0.5\kappa\left(1+\gamma\right)\|\boldsymbol{x}^{\prime}\|^{2}+\kappa\left(\Phi(\boldsymbol{u}^{\ast}),\boldsymbol{x}^{\prime}R^{-1}\right),\end{split}$
where $\kappa$ and $D$ are chosen as in (12).

Output: trigger input $\boldsymbol{u}^{\prime}$, weight vector
$\boldsymbol{w}=\kappa\boldsymbol{x}^{\prime}{R}^{-1}$, bias
$b=0.5\kappa\left(1+\gamma\right)\|\boldsymbol{x}^{\prime}\|^{2}+\kappa(\Phi(\boldsymbol{u}^{\ast}),\boldsymbol{x}^{\prime}R^{-1})$,
and output gain $D$ of the sigmoid or a ReLU function $g$.

Performance bounds for Algorithm 2 can be derived in the same way as we have
done in Theorem 1 for Algorithm 1. Formally, we state these bounds in
Corollary 1 below.

###### Corollary 1

Consider Algorithm 2, and let parameters $\gamma\in(0,1)$, $\alpha\in[0,1)$,
and $\delta\in(0,1]$ be such that (13) holds. Then the probability $P_{a,1}$
that Algorithm 2 returns a solution to Problem 1 is bounded from below as (14)
and (15).

Proof of Corollary 1 is provided in Supplementary Material (Section S.2).

All previous remarks (Remarks 1 – 5) apply equally to Algorithm 2. In addition
the presence of a specified target input $\boldsymbol{u}^{\ast}$ offers extra
flexibility and opportunities. An attacker may instead have a list of
potential target inputs. Application of Algorithm 2 to each of these inputs
produces different triggers $\boldsymbol{u}^{\prime}$ with different values of
$\alpha$. According to Remark 1 (see also (16)), small values of $\alpha$
imply higher probabilities that the corresponding attacks are successful.
Therefore, having a list of target inputs and selecting a trigger with minimal
$\alpha$ increases the attacker’s chances of success.

##  3 Related work

Adversarial attacks. A broad range of methods aimed at revealing
vulnerabilities of state-of-the art AI, and deep learning models in
particular, to adversarial inputs has been proposed to date (see e.g. recent
reviews [15, 20]). The focus of this body of work has been primarily on
perturbations to signals/data processed by the AI. In contrast to this
established framework, here we explored possibilities to determine and
implement small changes to AI structure and without retraining.

Data poisoning. Gu et al [12] (see also [5] and references therein) showed how
malicious data poisoning occurring, for example, via outsourcing of training
to a third party can lead to backdoor vulnerabilities. Performance of the
modified model on the validation set, however, is not required to be perfect.
A data poisoning attack is deemed successful if the model’s performance on the
validation set is within some margin of the user’s expectations.

This scenario, however, is different from our setting in two fundamental ways.
First, the attacker can maintain performance of the perturbed system on an
unknown validation set within arbitrary small or, in case of ReLU neurons,
zero margins. Such imperceptible changes on unknown validation sets is a
signature characteristic of the threat we have revealed and studied. Second,
the attacks we analysed do not require any retraining.

Other stealth attacks. Liu et al [17] proposed a mechanism, $SIN^{2}$, whereby
a service provider gains control over their customers’ deep neural networks
through the provider’s specially designed APIs. In this approach, the provider
needs to first plant malicious information in higher-precision bits (e.g. bits
$16$ and higher) of the network’s weights. When an input trigger arrives the
provider extracts this information via its service’s API and performs
malicious actions as per instructions encoded.

In contrast to this approach, stealth attacks we discovered do not require any
special computational environments. They can be executed in fully secure and
trusted infrastructure. Nevertheless, our work reveals further concerns about
how easily a malicious service provider can implement stealth attacks in
hostile environments [17] by swapping bits in the mantissa of weights and
biases of a single neuron (see Fig. 2 for the patterns of change) at will.

Our work is a significant step from the approach presented in [26]. First,
vulnerabilities which we reveal here are much more severe. Bounds on the
probability of success for attacks from in [26] are constrained by
$1-M2^{-n}$. Our results show that under the same assumptions (input
reachability [15] holds true), probabilities of success for attacks generated
by Algorithms 1, 2 can be made arbitrarily close to one (Remark 1). Second, we
explicitly account for cases when input reachability does not hold, through
parameters $\alpha,\delta$. Third, we present concrete algorithms, scenarios
and examples of successful exploitation of these new vulnerabilities,
including the case of one-neuron attacks (Section 4, Supplementary Material,
and [27]).

##  4 Experiments

Let us show how stealth attacks can be constructed for given deep learning
models. We consider a standard benchmark problem in which deep learning
networks are trained on the MNIST dataset [16]. The networks had a standard
architecture with feature-generation layers followed by dense fully connected
layers. Details of the architecture are provided in Table S.1, Supplementary
Material, Section S.3.3. MATLAB code implementing all steps of the experiments
can be found in [27]. Map $\Phi$ in (2) was associated with operations
performed by layers $1-14$ (shown in black in Table S.1, Section S.3.3), and
map $F$ modelled transformation from layer $15$ to the first neuron in layer
$17$.

The original dataset of $10,000$ images was split into a training set
consisting of $7,500$ images and a test set containing $2,500$ images. All
networks were subjected to the same training protocols albeit with randomised
training and test sets (see Supplementary Material, Section S.3.3 for
details).

Our stealth attack was a single ReLU neuron receiving $n=200$ inputs from the
outputs of ReLU neurons in layer $14$. These outputs, for a given image
$\boldsymbol{u}$, produced latent representations $\Phi(\boldsymbol{u})$. The
“attack” neuron was defined as
$\mathfrak{A}(\cdot,(\boldsymbol{w},b))=D\,\mbox{ReLU}((\cdot,\boldsymbol{w})-b)$,
where the weight vector $\boldsymbol{w}\in\mathbb{R}^{200}$ and bias
$b\in\mathbb{R}$ were determined in accordance with Algorithm 2.

Three alternative scenarios for planting a stealth attack neuron were
considered. Schematically, these scenarios are shown in Fig. 2.

Figure 2: Stealth attack implementation patterns. Red open circles indicate
changes. In Scenarios $1$ and $2$ neuron(s) are added. In Scenario $3$, a one
neuron attack, the weights and biases of an existing neuron are replaced with
new values. Grey boxes show a part of the network modelled by the map $F$.

In the first scenario, output of the “attack” neuron is added directly to the
output of $F$ (the first neuron in layer $17$ of the network). The second
scenario is functionally identical to the first one. The only difference is
that it preserves layer-by-layer structure of the computational graph of $F$
by adding extra nodes and propagating output of the “attack” neuron to the
output of $F$. The third, and perhaps the most interesting scenario, follows
the process described in Remark 5. It _replaces_ a neuron in $F$ by the
“attack” neuron. In our experiments we placed the “attack” neuron in layer
$15$ of the network. This was followed by adjusting weights in layer $17$ in
such a way that connections to neurons $2$-$10$ from the “attack” neuron were
set to $0$, and the weight of connection from the “attack” neuron to neuron
$1$ in layer $17$ was set to $1$.

As the unknown verification set $\mathcal{V}$ we used $99\%$ of the test set.
The remaining $1\%$ of the test set was used to derive an empirical estimate
of the value of $R$ needed for the implementation of Algorithm 2. Other
parameters of the algorithm were set as follows: $\delta=1/3$, $\gamma=0.9$,
and $\Delta=50$. A crucial step of the attack is step 3 in Algorithm 2 where a
trigger image $\boldsymbol{u}^{\prime}$ is generated. To find the trigger, a
standard gradient-based search method was employed to solve an appropriately
modified optimisation problem (8) (see Supplementary Material, Section S.3.1
for more details).

Fig. 3 illustrates how Algorithm 2 performed for the above networks. Three
target images (bottom row in the left panel of Fig. 3 \- digit $2$, plain grey
square, and a random image) produced three corresponding trigger images (top
row of the panel). Examples of trigger-target pairs for digits $0$–$9$ are
shown in Supplementary Material, Fig. S.3.

Figure 3: Left panel: target images (bottom row) and their corresponding
triggers (top row), $\delta=1/3$, $\gamma=0.9$. Right panel: Histogram of
values $(\Phi(\boldsymbol{u}),{\boldsymbol{w}})-b$,
$\boldsymbol{u}\in\mathcal{V}$ for the second trigger image in the top row in
the left panel.

When elements (images) from the unknown validation set $\mathcal{V}$ were
presented to the network, the neuron’s output was $0$. The histogram of values
$(\Phi(\boldsymbol{u}),{\boldsymbol{w}})-b$, $\boldsymbol{u}\in\mathcal{V}$ is
shown in Fig. 3 (right panel). As we can see, the neuron is firmly in the
“silent mode” for all elements of the unknown validation set $\mathcal{V}$. We
generated stealth attacks for $20$ different instances of trained networks,
and the rates of success in Scenarios $1$ and $3$ (Fig. 2) were $100\%$ ($20$
out of $20$) and $85\%$ ($17$ out of $20$), respectively. For the one neuron
attack in Scenario 3 we followed the approach discussed in Remark 5 with the
procedure for selecting a neuron to be replaced described in Supplementary
Material, Section S.3.6.

Figure 4: Susceptibility to one-neuron stealth attack. Left panel: empirical
frequencies of successful removal of neurons without any affect on the
network’s performance. Right panel: $\%$ of unmatched responses for cases when
removal of a neuron had an affect. Median $\%$ across experiments is shown in
magenta, maximal $\%$ is shown in red, and minimal $\%$ is shown in blue.

To gain further insights into susceptibility of networks to one neuron
attacks, we trained $100$ randomly initiated networks and assessed their
robustness to replacement of a single neuron. Fig. 4, left panel, shows
frequencies of events when replacing a neuron from layer $15$ did not produce
any changes in network performance on the validation set $\mathcal{V}$. The
frequencies are shown as a function of the neuron’s susceptibility rank (see
Supplementary Material, Section S.3.6 for the details). The smaller the
$L_{1}$ norm of its“output” weights the higher the rank (rank $1$ is the
highest possible). As we can see, removal of top-ranked neurons did not affect
our networks’ performance in $80\%$ of cases. If a small, $<0.3\%$ error
margin on the validation set $\mathcal{V}$ is allowed, then the one-neuron
attack’s would have a potential to be successful in $100\%$ of cases (see Fig.
4, right panel).

##  5 Conclusions and possible societal impact

In this work we reveal and analyse new adversarial vulnerabilities to which
large-scale networks may be particularly susceptible. By design, research in
this area looks at techniques that may be used to override the intended
functionality of algorithms that are used within a decision-making pipeline,
and hence may have serious negative implications in key sectors, including
security, defence, finance and healthcare. By highlighting these shortcomings
in the public domain, we raise awareness of the issue, so that both algorithm
designers and end-users can be better informed. Our analysis of these
vulnerabilities also identifies important factors contributing to their
successful exploitation: dimension of the network’s latent space, accuracy of
executing the attack (expressed by parameter $\alpha$), and over-
parameterization. These determinants enable us to propose model design
strategies to minimise the chances of exploiting the adversarial
vulnerabilities that we identified.

Low dimension of latent spaces. Our theoretical analysis suggests (bounds
stated in Theorem 1 and Corollary 1) that the higher the dimension of latent
spaces in state-of-the art deep neural networks the higher the chances of a
successful attack. These chances approach one exponentially with dimension.
One strategy to address this risk is to transform wide computational graphs in
those parts of the network which are most vulnerable to open-box attacks into
computationally equivalent deeper but narrower graphs. Such transformations
can be done after the training and just before the model is shared or
deployed. Another alternative is to employ dimensionality reduction approaches
facilitating lower-dimensional layer widths during and after the training.

Constraining attack accuracy. An ability to find triggers with arbitrarily
high accuracy is another component of the attacker’s success. Therefore
increasing the computational costs of finding triggers for large enough
$\delta$ with high accuracy is a viable defence strategy. A potential way
could be to use gradient obfuscation techniques developed in the adversarial
examples literature coupled with randomisation, as suggested in [19]. It is
well-known that gradient obfuscation may not always prevent an attacker from
finding a trigger [4]. Yet, making this process as complicated and
computationally-intensive as possible would certainly contribute to increased
security.

Reducing over-parameterization. We demonstrate theoretically and confirm in
experiments that over-parameterization, inherent in many deep learning models,
can easily be exploited by an adversary if models are freely shared and
exchanged without control. In order to deny these opportunities to the
attacker, removing susceptible neurons with our procedure in Section S.3.6
offers a potential remedy. More generally, employing network pruning [6, 7,
18, 25] as a part of model production pipelines would offer further protection
against one-neuron attacks.

Network Hashing. In addition to the strategies above, which stem from
theoretical analysis of stealth attacks, another defence could come from using
fast network hashing algorithms executed in parallel with inference processes.
The hash codes these algorithms produce will enable the owner to detect
unwanted changes to the model after it was downloaded from a safe and trusted
source.

Our theoretical and practical analysis of the new threats are in no way
complete. In experiments we assumed that pixels in images are real numbers. In
reality though they may have to be integers. We did not asses how changes in
numerical precision would affect the threat, and did not provide conditions
when redundant neurons exist. Moreover, as we showed in Section S.3.5, our
theoretical bounds could be conservative. Finally, vulnerabilities discovered
here are intrinsically linked with AI maintenance problems discussed in [10].
Exploring these issues are topics for future research.

Nevertheless, the theory and empirical evidence which we present in this work
make it clear that existing mitigation strategies must be strengthened in
order to guard against vulnerability to new forms of stealth attack. Because
the “inevitability” results that we derived have constructive proofs, our
analysis offers promising options for the development of effective defences.

## Acknowledgements

Desmond J. Higham was supported by grants EP/V046527/1 and EP/P020720/1 from
the EPSRC; Alexander N. Gorban and Ivan Y. Tyukin were supported the Ministry
of Science and Higher Education of the Russian Federation (Project No.
075-15-2020-808); Ivan Y. Tyukin was supported by the UKRI Turing AI
Fellowship ARaISE EP/V025295/1 and UKRI Trustworthy Autonomous Systems Node in
Verifiability EP/V026801/1.

## References

  * [1] Naveed Akhtar and Ajmal Mian.  Threat of adversarial attacks on deep learning in computer vision: A survey.  IEEE Access, 6:14410–14430, 2018.
  * [2] Bibb Allen, Sheela Agarwal, Jayashree Kalpathy-Cramer, and Keith Dreyer.  Democratizing AI.  Journal of the American College of Radiology, 16:961–963, 2019\.
  * [3] Vegard Antun., Francesco Renna, Clarice Poon, Ben Adcock, and Anders C. Hansen.  On instabilities of deep learning in image reconstruction and the potential costs of AI.  Proceedings of the National Academy of Sciences, 117:30088–30095, 2020.
  * [4] Anish Athalye, Nicholas Carlini, and David Wagner.  Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples.  In International Conference on Machine Learning, pages 274–283. PMLR, 2018.
  * [5] Battista Biggio and Fabio Roli.  Wild patterns: Ten years after the rise of adversarial machine learning.  Pattern Recognition, 84:317–331, 2018.
  * [6] Davis Blalock, Jose Javier Gonzalez Ortiz, Jonathan Frankle, and John Guttag.  What is the state of neural network pruning?  arXiv preprint arXiv:2003.03033, 2020.
  * [7] Yu Cheng, Duo Wang, Pan Zhou, and Tao Zhang.  A survey of model compression and acceleration for deep neural networks.  arXiv preprint arXiv:1710.09282, 2017.
  * [8] Javid Ebrahimi, Anyi Rao, Daniel Lowd, and Dejing Dou.  HotFlip: White-box adversarial examples for text classification.  In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 31–36, Melbourne, Australia, July 2018. Association for Computational Linguistics.
  * [9] S.G. Finlayson, J.D. Bowers, J. Ito, J. L. Zittrain, A. L. Beam, and I. S. Kohane.  Adversarial attacks on medical machine learning.  Science, 363:1287–1289, 2019.
  * [10] A. N. Gorban, V. A. Makarov, and I. Y. Tyukin.  The unreasonable effectiveness of small neural ensembles in high-dimensional brain.  Physics of Life Reviews, pages 86–103, 2019.
  * [11] AN Gorban and DA Rossiev.  Neural networks on personal computer.  Novosibirsk: Nauka (RAN), 1996.
  * [12] Tianyu Gu, Brendan Dolan-Gavitt, and Siddharth Garg.  Badnets: Identifying vulnerabilities in the machine learning model supply chain.  arXiv preprint arXiv:1708.06733, 2017.
  * [13] R.H.R. Hahnloser, R. Sarpeshkar, M.A. Mahowald, R.J. Douglas, and H.S. Seung.  Digital selection and analogue amplification coexist in a cortex-inspired silicon circuit.  Nature, 405(6789):947–951, 2000.
  * [14] Catherine F. Higham and Desmond J. Higham.  Deep learning: An introduction for applied mathematicians.  SIAM Review, 61:860–891, 2019.
  * [15] Xiaowei Huang, Daniel Kroening, Wenjie Ruan, James Sharp, Youcheng Sun, Min Thamo, Emeseand Wu, and Xinping Yi.  A survey of safety and trustworthiness of deep neural networks: Verification, testing, adversarial attack and defence, and interpretability?  Computer Science Review, 37, 2020.
  * [16] Yann LeCun, Corinna Cortes, and Christopher J. C. Burges.  The MNIST database of handwritten digits.  Accessed June 17, 2019.
  * [17] T. Liu, W. Wen, and Y. Jin.  Sin2: Stealth infection on neural network — a low-cost agile neural trojan attack methodology.  In 2018 IEEE International Symposium on Hardware Oriented Security and Trust (HOST), pages 227–230, 2018.
  * [18] Evgeny M Mirkes.  Artificial neural network pruning to extract knowledge.  In 2020 International Joint Conference on Neural Networks (IJCNN), pages 1–8. IEEE, 2020.
  * [19] Han Qiu, Yi Zeng, Qinkai Zheng, Tianwei Zhang, Meikang Qiu, and Gerard Memmi.  Mitigating advanced adversarial attacks with more advanced gradient obfuscation techniques.  arXiv preprint arXiv:2005.13712, 2020.
  * [20] Kui Ren, Tianhang Zheng, Zhan Qin, and Xue Liu.  Adversarial attacks and defenses in deep learning.  Engineering, 6(3):346–360, 2020.
  * [21] A. Shafahi, W.R. Huang, C. Studer, S. Feizi, and T. Goldstein.  Are adversarial examples inevitable?  International Conference on Learning Representations (ICLR), 2019\.
  * [22] Ali Shafahi, Mahyar Najibi, Zheng Xu, John Dickerson, Larry S. Davis, and Tom Goldstein.  Universal adversarial training.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5636–5643, 2020.
  * [23] Jiawei Su, Danilo Vasconcellos Vargas, and Kouichi Sakurai.  One pixel attack for fooling deep neural networks.  IEEE Transactions on Evolutionary Computation, 23:828–841, 2019\.
  * [24] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus.  Intriguing properties of neural networks.  arXiv preprint arXiv:1312.6199, 2013.
  * [25] Hidenori Tanaka, Daniel Kunin, Daniel L Yamins, and Surya Ganguli.  Pruning neural networks without any data by iteratively conserving synaptic flow.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 6377–6389. Curran Associates, Inc., 2020.
  * [26] I.Y. Tyukin, D.J. Higham, and A.N. Gorban.  On adversarial examples and stealth attacks in artificial intelligence systems.  In 2020 International Joint Conference on Neural Networks (IJCNN), pages 1–6. IEEE, 2020.
  * [27] I.Y. Tyukin, J.D. Higham, E. Woldegeorgis, and A.N. Gorban.  Example code for open-box attacks.  https://github.com/tyukin/Stealth-adversarial-attacks, 2021.
  * [28] M. Wu, M. Wicker, W. Ruan ans X. Huang, and M. Kwiatkowska.  A game-based approximate verification of deep neural networks with provable guarantees.  Theoretical Computer Science, 807:298–329, 2020.

## Supplementary material

In this section we provide detailed proofs of our theoretical statements
(Sections S.1, S.2), detailed description of procedures for finding triggers
(Section S.3.1), discuss non-optimal choices of validation sets $\mathcal{V}$
(Section S.3.2), and provide a detailed account of computational experiments
(Sections S.3.3 – S.3.6).

All citations refer to References provided in the main body of the paper.

###  S.1 Proof of Theorem 1

The proof is split into 4 basic parts. We begin by assuming that latent
representations $\boldsymbol{x}_{i}=\Phi(\boldsymbol{u}_{i})$ of all elements
$\boldsymbol{u}_{i}$ from the set $\mathcal{V}$ belong to the unit ball
$\mathbb{B}_{n}$ centered at the origin (for simplicity of notation unit
$n$-ball centered at $0$ is denoted as $\mathbb{B}_{n}$, and unit $n-1$ sphere
centered at $0$ is denoted as $\mathbb{S}_{n-1}$). The main thrust of the
proof is to establish lower bounds on the probability of the event

$\mathcal{E}^{\ast}:\
\gamma(\boldsymbol{x}^{\prime},\boldsymbol{x}^{\prime})\geq(\boldsymbol{x}^{\prime},\boldsymbol{x}_{i})\
\mbox{for all}\
\boldsymbol{x}_{i}=\Phi(\boldsymbol{u}_{i}):\boldsymbol{u}_{i}\in\mathcal{V},\
\boldsymbol{x}_{i}\in\mathbb{B}_{n}.$ (S.1)

These bounds are established in Parts 1 and 2. Then we proceed with
constructing weights (both, input and output) and biases of the function $g$
so that the modified map $F_{a}$ delivers a solution of Problem 1. This is
shown in Part 3. Finally, we remove the assumption that
$\boldsymbol{x}_{i}\in\mathbb{B}_{n}$ and show how the weights and biases need
to be adapted so that the adapted map $F_{a}$ is a solution of Problem 1 for
$\boldsymbol{x}_{i}\in\mathbb{B}_{n}(0,R)$ were $R>0$ is a given number. This
is demonstrated in Part 4 of the proof.

Figure S.1: To the proof of Theorem 1.

Part 1. Probability bound 1 on the event $\mathcal{E}^{\ast}$. Let
$\boldsymbol{x}_{i}$, $i=1,\dots,M$ be an arbitrary element from
$\mathcal{V}$, let $\boldsymbol{x}$ be drawn randomly from an equidistribution
in $\mathbb{S}_{n-1}(0,\delta)$, and let $\boldsymbol{x}^{\prime}$ be a vector
that’s within an $\alpha\delta$-distance from $\boldsymbol{x}$:

$\|\boldsymbol{x}-\boldsymbol{x}^{\prime}\|\leq\alpha\delta.$

Consider angles between $\boldsymbol{x}_{i},\boldsymbol{x}^{\prime}$ and
$\boldsymbol{x}^{\prime},\boldsymbol{x}$. Let

$\begin{split}A^{\ast}(\boldsymbol{x},\boldsymbol{x}_{i})=&\min_{\boldsymbol{z}:\
\|\boldsymbol{x}-\boldsymbol{z}\|\leq\alpha\delta}|\angle(\boldsymbol{x}_{i},\boldsymbol{z})|,\\\
B^{\ast}(\boldsymbol{x},\boldsymbol{x}_{i})=&\max_{\boldsymbol{z}:\
\|\boldsymbol{x}-\boldsymbol{z}\|\leq\alpha\delta}|\angle(\boldsymbol{z},\boldsymbol{x})|=|\angle(\boldsymbol{x}_{i},\boldsymbol{x})|-A^{\ast}(\boldsymbol{x},\boldsymbol{x}_{i})\end{split}$

(see Fig. S.1). It is clear that
$A^{\ast}(\boldsymbol{x},\boldsymbol{x}_{i})\leq|\angle(\boldsymbol{x}_{i},\boldsymbol{x}^{\prime})|$
and
$B^{\ast}(\boldsymbol{x},\boldsymbol{x}_{i})\geq|\angle(\boldsymbol{x}^{\prime},\boldsymbol{x})|$.
Notice that Algorithm 1 requests that $\gamma\|\boldsymbol{x}^{\prime}\|\leq
1$ (i.e. $\arccos(\gamma\|\boldsymbol{x}^{\prime}\|)$ always exists). Hence if
the vector $\boldsymbol{x}$ is chosen so that

$A^{\ast}(\boldsymbol{x},\boldsymbol{x}_{i})\geq\arccos(\gamma\|\boldsymbol{x}^{\prime}\|)$
(S.2)

then this choice would in turn guarantee that

$\left(\frac{\boldsymbol{x}^{\prime}}{\|\boldsymbol{x}^{\prime}\|},\frac{\boldsymbol{x}_{i}}{\|\boldsymbol{x}_{i}\|}\right)\leq\gamma\|\boldsymbol{x}^{\prime}\|$

(see Fig. S.1) and, consequently,

$\left(\boldsymbol{x}^{\prime},\boldsymbol{x}_{i}\right)\leq\gamma\|\boldsymbol{x}^{\prime}\|^{2}\|\boldsymbol{x}_{i}\|=\gamma(\boldsymbol{x}^{\prime},\boldsymbol{x}^{\prime})\|\boldsymbol{x}_{i}\|\leq\gamma(\boldsymbol{x}^{\prime},\boldsymbol{x}^{\prime}).$

Observe that condition (S.2) is satisfied if

$|\angle(\boldsymbol{x}_{i},\boldsymbol{x})|\geq
A+B=\arccos(\gamma\|\boldsymbol{x}^{\prime}\|)+\arccos((1-\alpha^{2})^{1/2}),$

where the values of angles $A$ and $B$ are
$\arccos(\gamma\|\boldsymbol{x}^{\prime}\|)$ and
$\arccos((1-\alpha^{2})^{1/2})$, respectively (see Fig. S.1), and
$A+B\in(0,\pi/2)$.

Let us denote

$\beta(\gamma,\alpha,\|\boldsymbol{x}^{\prime}\|)=\arccos(\gamma\|\boldsymbol{x}^{\prime}\|)+\arccos((1-\alpha^{2})^{1/2}).$

Given that parameters $\gamma,\delta,\alpha$ are chosen so that (13) holds, it
is clear that $0<\beta(\gamma,\alpha,\|\boldsymbol{x}^{\prime}\|)<\pi/2$.

One can therefore conclude that if the event

$\mathcal{E}:\
\left(\frac{\boldsymbol{x}}{\|\boldsymbol{x}\|},\frac{\boldsymbol{x}_{i}}{\|\boldsymbol{x}_{i}\|}\right)<\cos\left(\beta(\gamma,\alpha,\|\boldsymbol{x}^{\prime}\|)\right)\
\mbox{for all}\ \boldsymbol{x}_{i}\in\mathcal{V}$ (S.3)

occurs then the event $\mathcal{E}^{\ast}$, (S.1), must occur too.

Consider events

$\mathcal{E}_{i}:\
\left(\frac{\boldsymbol{x}}{\|\boldsymbol{x}\|},\frac{\boldsymbol{x}_{i}}{\|\boldsymbol{x}_{i}\|}\right)\geq\cos(\beta(\gamma,\alpha,\|\boldsymbol{x}^{\prime}\|)).$

The probability that $\mathcal{E}_{i}$ occurs is equal to the area of the
spherical cap

$C(\boldsymbol{x}_{i},\beta(\gamma,\alpha,\|\boldsymbol{x}^{\prime}\|))=\left\\{\boldsymbol{z}\in\mathbb{S}_{n-1}\left|\
\left(\frac{\boldsymbol{x}_{i}}{\|\boldsymbol{x}_{i}\|},\boldsymbol{z}\right)\geq\cos(\beta(\gamma,\alpha,\|\boldsymbol{x}^{\prime}\|))\right.\right\\}$

divided by the area of $\mathbb{S}_{n-1}$:

$P(\mathcal{E}_{i})=\frac{A_{n-1}(C(\boldsymbol{x}_{i},\beta(\gamma,\alpha,\|\boldsymbol{x}^{\prime}\|)))}{A_{n-1}(\mathbb{S}_{n-1})}.$
(S.4)

It is well-known that

$A_{n-1}(C(\boldsymbol{x}_{i},\beta(\gamma,\alpha,\|\boldsymbol{x}^{\prime}\|)))=A_{n-2}(\mathbb{S}_{n-2})\int_{0}^{\beta(\gamma,\alpha,\|\boldsymbol{x}^{\prime}\|)}\sin^{n-2}(\theta)d\theta,\
\mbox{and}\
A_{n-1}(\mathbb{S}_{n-1})=\frac{2\pi^{\frac{n}{2}}}{\Gamma(\frac{n}{2})}.$

Hence

$P\left(\mathcal{E}_{i}\right)=\frac{A_{n-2}(\mathbb{S}_{n-2})}{A_{n-1}(\mathbb{S}_{n-1})}\int_{0}^{\beta(\gamma,\alpha,\|\boldsymbol{x}^{\prime}\|)}\sin^{n-2}(\theta)d\theta.$

Using the fact that inequality

$P(\mbox{not}\ \mathcal{E}_{1}\wedge\cdots\wedge\mbox{not}\
\mathcal{E}_{M})\geq 1-\sum_{i=1}^{M}P(\mathcal{E}_{i})$ (S.5)

holds true for any events $\mathcal{E}_{i}$, that $\mathcal{E}=\mbox{not}\
\mathcal{E}_{1}\wedge\cdots\wedge\mbox{not}\ \mathcal{E}_{M}$, and that
$P(\mathcal{E}^{\ast})\geq P(\mathcal{E})$ (as $\mathcal{E}$ implies
$\mathcal{E}^{\ast}$), we can conclude that

$P\left(\left(\boldsymbol{x}^{\prime},\boldsymbol{x}_{i}\right)<\gamma(\boldsymbol{x}^{\prime},\boldsymbol{x}^{\prime})\
\mbox{for all}\ \boldsymbol{x}_{i}\in\mathcal{V}\ \right)\geq
1-M\frac{A_{n-2}(\mathbb{S}_{n-2})}{A_{n-1}(\mathbb{S}_{n-1})}\int_{0}^{\beta(\gamma,\alpha,\|\boldsymbol{x}^{\prime}\|)}\sin^{n-2}(\theta)d\theta,$

or, equivalently

$\begin{split}&P\left(\left(\boldsymbol{x}^{\prime},\boldsymbol{x}_{i}\right)<\gamma(\boldsymbol{x}^{\prime},\boldsymbol{x}^{\prime})\
\mbox{for all}\ \boldsymbol{x}_{i}\in\mathcal{V}\ \right)\geq
1-M\frac{1}{\pi^{\frac{1}{2}}}\frac{\Gamma\left(\frac{n}{2}\right)}{\Gamma\left(\frac{n-1}{2}\right)}\int_{0}^{\beta(\gamma,\alpha,\|\boldsymbol{x}^{\prime}\|)}\sin^{n-2}(\theta)d\theta.\end{split}$
(S.6)

Finally, noticing that

$\beta(\gamma,\alpha,\|\boldsymbol{x}^{\prime}\|)\leq\arccos(\gamma(1-\alpha)\delta)+\arccos((1-\alpha^{2})^{1/2})$

we can conclude that Algorithm 1 ensures that event $\mathcal{E}^{\ast}$,
(S.1), occurs with probability at least (14).

Part 2. Probability bound 2 on the event $\mathcal{E}^{\ast}$. Consider (S.4)
and note that

$P(\mathcal{E}_{i})\leq\frac{A_{n-1}(C(\boldsymbol{x}_{i},\arccos(\varphi(\gamma,\delta,\alpha))))}{A_{n-1}(\mathbb{S}_{n-1})}.$

Recall that

$\begin{split}&A_{n-1}(C(\boldsymbol{x}_{i},\arccos(\varphi(\gamma,\delta,\alpha))))\frac{1}{n}=V_{n}(C(\boldsymbol{x}_{i},\arccos(\varphi(\gamma,\delta,\alpha)))+\\\
&\ \ \ \ \ \ \ \ \ \ \ \ \
\frac{\varphi(\gamma,\delta,\alpha)}{n}V_{n-1}\left(B_{n-1}\left(\frac{\boldsymbol{x}_{i}}{\|\boldsymbol{x}_{i}\|}\varphi(\gamma,\delta,\alpha),(1-\varphi(\gamma,\delta,\alpha)^{2})^{1/2}\right)\right).\end{split}$

Observe that (see Fig. S.1)
$|CO^{\prime}|/|OO^{\prime}|=|OO^{\prime\prime}|/|CO^{\prime}|$. Given that
$|CO^{\prime}|=1$ and
$|OO^{\prime}|=|OO^{\prime\prime}|+|O^{\prime\prime}O^{\prime}|$,

$|O^{\prime\prime}O^{\prime}|+|OO^{\prime\prime}|=\frac{1}{|OO^{\prime\prime}|},\
\mbox{and}\
|O^{\prime\prime}O^{\prime}|=\frac{1}{|OO^{\prime\prime}|}-|OO^{\prime\prime}|.$

The above identity holds for all appropriate angles $A$ and $B$, including for
$A=\arccos(\gamma(1-\alpha)\delta)$. That is, if
$|OO^{\prime\prime}|=\varphi(\gamma,\delta,\alpha)$ then

$|O^{\prime\prime}O^{\prime}|=\frac{1}{\varphi(\gamma,\delta,\alpha)}-\varphi(\gamma,\delta,\alpha).$

Notice that the spherical cap
$C(\boldsymbol{x}^{\prime},\varphi(\gamma,\delta,\alpha))$ is always inside
the cone $C^{\prime}CO$ whose base is the disc centered at
$\frac{\boldsymbol{x}_{i}}{\|\boldsymbol{x}_{i}\|}\varphi(\gamma,\delta,\alpha)$
with radius $(1-\varphi(\gamma,\delta,\alpha)^{2})^{1/2}$. The height of this
cone, according to the above calculations, is
$\frac{1}{\varphi(\gamma,\delta,\alpha)}-\varphi(\gamma,\delta,\alpha)$.
Therefore

$\begin{split}&V_{n}(C(\boldsymbol{x}^{\prime},\varphi(\gamma,\delta,\alpha)))\leq\frac{1}{n}\left(\frac{1}{\varphi(\gamma,\delta,\alpha)}-\varphi(\gamma,\delta,\alpha)\right)\times\\\
&\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
V_{n-1}\left(B_{n-1}\left(\frac{\boldsymbol{x}_{i}}{\|\boldsymbol{x}_{i}\|}\varphi(\gamma,\delta,\alpha),(1-\varphi(\gamma,\delta,\alpha)^{2})^{1/2}\right)\right).\end{split}$

Hence

$A_{n-1}(C(\boldsymbol{x}^{\prime},\varphi(\gamma,\delta,\alpha)))\leq\frac{1}{\varphi(\gamma,\delta,\alpha)}V_{n-1}(\mathbb{B}_{n-1})\left(1-\varphi(\gamma,\delta,\alpha)^{2}\right)^{\frac{n-1}{2}}.$

Taking into account that

$\frac{V_{n-1}(\mathbb{B}_{n-1})}{A_{n-1}(\mathbb{S}_{n-1})}=\frac{\pi^{\frac{n-1}{2}}}{2\pi^{\frac{n}{2}}}\frac{\Gamma\left(\frac{n}{2}\right)}{\Gamma\left(\frac{n-1}{2}+1\right)}=\frac{1}{2\pi^{\frac{1}{2}}}\frac{\Gamma\left(\frac{n}{2}\right)}{\Gamma\left(\frac{n}{2}+\frac{1}{2}\right)},$

we arrive at

$P(\mathcal{E}_{i})\leq\frac{1}{2\pi^{\frac{1}{2}}}\frac{\Gamma\left(\frac{n}{2}\right)}{\Gamma\left(\frac{n}{2}+\frac{1}{2}\right)}\frac{1}{\varphi(\gamma,\delta,\alpha)}\left(1-\varphi(\gamma,\delta,\alpha)^{2}\right)^{\frac{n-1}{2}}.$
(S.7)

This confirms that event $\mathcal{E}^{\ast}$, (S.1), occurs with probability
satisfying the bound (15).

Part 3. Construction of the structural adversarial perturbation. Having
established bounds on the probability of event (S.1), let us now proceed with
determining a map $F_{a}$ which is solution to Problem 1 assuming that
$\boldsymbol{x}_{i}\in\mathbb{B}_{n}$. Suppose that the event
$\mathcal{E}^{\ast}$ holds true:

$(\boldsymbol{x}^{\prime},\boldsymbol{x}_{i})\leq\gamma\|\boldsymbol{x}^{\prime}\|^{2}\
\mbox{for all}\ \boldsymbol{x}_{i}=\Phi(\boldsymbol{u}_{i}),\
\boldsymbol{u}_{i}\in\mathcal{V},\ \boldsymbol{x}_{i}\in\mathbb{B}_{n}.$

Set

$\displaystyle\boldsymbol{w}$ $\displaystyle=$
$\displaystyle\kappa\boldsymbol{x}^{\prime},\ \kappa>0,$ (S.8) $\displaystyle
b$ $\displaystyle=$
$\displaystyle\kappa\left(\frac{1+\gamma}{2}\right)\|\boldsymbol{x}^{\prime}\|^{2},$
(S.9)

and observe that

$\mathfrak{A}(\cdot,(\boldsymbol{w},b))=Dg\left(\kappa\left((\cdot,\boldsymbol{x}^{\prime})-\left(\frac{1+\gamma}{2}\right)\|\boldsymbol{x}^{\prime}\|^{2}\right)\right).$

Recall that $g$ is either ReLU or sigmoid and consider

$\|F(\boldsymbol{x}_{i})-F_{a}(\boldsymbol{x}_{i},(\boldsymbol{w},b))\|=|\mathfrak{A}(\cdot,(\boldsymbol{w},b))|.$

Since the function $g$ is monotone,

$|\mathfrak{A}(\boldsymbol{x}_{i},(\boldsymbol{w},b))|\leq
Dg\left(-\kappa\left(\frac{1-\gamma}{2}\|\boldsymbol{x}^{\prime}\|^{2}\right)\right)\
\mbox{for all}\ \boldsymbol{x}_{i}=\Phi(\boldsymbol{u}_{i}),\
\boldsymbol{u}_{i}\in\mathcal{V},\ \boldsymbol{x}_{i}\in\mathbb{B}_{n}.$

Denote

$z=\frac{1-\gamma}{2}\|\boldsymbol{x}^{\prime}\|^{2}$

and pick the values of $D$ and $\kappa$ so that

$Dg(-\kappa z)\leq\varepsilon\ \mbox{and}\ Dg(\kappa z)\geq\Delta.$ (S.10)

Given that $\mathrm{ReLU}(s)=0$ for all $s\leq 0$ and that the sigmoidal
function is strictly increasing with $g(0)\neq 0$, such choice is always
possible.

Part 4. Generalisation to the case when
$\boldsymbol{x}_{i}\in\mathbb{B}_{n}(0,R)$. Consider variables

$\tilde{\boldsymbol{x}}_{i}=\frac{\boldsymbol{x}_{i}}{R}.$

It is clear that $\tilde{\boldsymbol{x}}_{i}\in\mathbb{B}_{n}$. Suppose now
that

$(\boldsymbol{x}^{\prime},\tilde{\boldsymbol{x}}_{i})\leq\gamma\|\boldsymbol{x}^{\prime}\|^{2}\
\mbox{for all}\
\tilde{\boldsymbol{x}}_{i}=\frac{\Phi(\boldsymbol{u}_{i})}{R},\
\boldsymbol{u}_{i}\in\mathcal{V},\
\boldsymbol{x}_{i}=\Phi(\boldsymbol{u}_{i})\in\mathbb{B}_{n}(0,R).$ (S.11)

Probability bounds on the above event have already been established in Parts 1
and 2 of the proof.

Consider (S.8) from Part 3 and re-scale the weight $\boldsymbol{w}$ as
follows:

$\displaystyle\boldsymbol{w}$ $\displaystyle=$
$\displaystyle\kappa\left(\frac{\boldsymbol{x}^{\prime}}{R}\right),\
\kappa>0,$ $\displaystyle b$ $\displaystyle=$
$\displaystyle\kappa\left(\frac{1+\gamma}{2}\right)\|\boldsymbol{x}^{\prime}\|^{2}.$

This is equivalent to

$\mathfrak{A}(\cdot,(\boldsymbol{w},b))=Dg\left(\kappa\left(\left(\cdot\frac{1}{R},\boldsymbol{x}^{\prime}\right)-\left(\frac{1+\gamma}{2}\right)\|\boldsymbol{x}^{\prime}\|^{2}\right)\right).$

If the values of $\kappa$ and $D$ are chosen so that (S.10) in Part 3 holds
then

$|\mathfrak{A}(\Phi(\boldsymbol{u}_{i}),(\boldsymbol{w},b))|\leq\varepsilon\
\mbox{for all}\ \boldsymbol{u}_{i}\in\mathcal{V}$

and

$\mathfrak{A}(\boldsymbol{x}^{\prime}R,(\boldsymbol{w},b))=\mathfrak{A}(\Phi(\boldsymbol{u}^{\prime}),(\boldsymbol{w},b))\geq\Delta.$

This, together with bounds (S.6), (S.7) in Parts 1 and 2 on the probability of
event (S.11) concludes the proof. $\square$.

###  S.2 Proof of Corollary 1

Consider AI system (2) which satisfies Assumption 2. In addition to this
system, consider a “virtual” one whose maps $F$ and $\Phi$ are replaced with:

$\tilde{\Phi}(\boldsymbol{u})=\Phi(\boldsymbol{u})-\Phi(\boldsymbol{u}^{\ast}),\
\tilde{F}(\boldsymbol{x})=F(\boldsymbol{x}+\Phi(\boldsymbol{u}^{\ast})).$

According to the definition of $\tilde{F}\circ\tilde{\Phi}$, domains of the
definition of $\tilde{F}\circ\tilde{\Phi}$ and ${F}\circ{\Phi}$ coincide, and

$\tilde{F}\circ\tilde{\Phi}(\boldsymbol{u})=F\circ\Phi(\boldsymbol{u})\
\mbox{for all}\ \boldsymbol{u}\in\mathcal{U}.$ (S.12)

For this virtual system, $\tilde{F}\circ\tilde{\Phi}$, Assumption 1 is
satisfied. Moreover, if an input $\boldsymbol{u}^{\prime}$

$\boldsymbol{x}^{\prime}=\frac{\Phi(\boldsymbol{u}^{\prime})}{R}-\frac{\Phi(\boldsymbol{u}^{\ast})}{R}$

satisfies conditions (9), (10) then these conditions are satisfied for
$\boldsymbol{x}^{\prime}=\tilde{\Phi}(\boldsymbol{u}^{\prime})/R$ (the
converse holds true too).

According to Theorem 1, adversarial perturbation defined by (11), (12):

$\begin{split}&\mathfrak{A}\left(\cdot,\left(\kappa\frac{\boldsymbol{x}^{\prime}}{R},b\right)\right)=Dg\left(\left(\cdot,\kappa\frac{\boldsymbol{x}^{\prime}}{R}\right)-b\right),\\\
&b=\kappa\left(\frac{1+\gamma}{2}\right)\|\boldsymbol{x}^{\prime}\|^{2}\end{split}$

is a solution of Problem 1 for the virtual AI system
$\tilde{F}\circ\tilde{\Phi}$, and probabilities of success are bounded from
below as in (14), (15).

Notice that

$\begin{split}&\mathfrak{A}\left(\Phi(\boldsymbol{u})-\Phi(\boldsymbol{u}^{\ast}),\left(\kappa\frac{\boldsymbol{x}^{\prime}}{R},b\right)\right)=\\\
&\ \ \ \ \ \ \ \ \ \
Dg\left(\left(\Phi(\boldsymbol{u}),\kappa\frac{\boldsymbol{x}^{\prime}}{R}\right)-\left(\kappa\left(\frac{1+\gamma}{2}\right)\|\boldsymbol{x}^{\prime}\|^{2}+\left(\Phi(\boldsymbol{u}^{\ast}),\kappa\frac{\boldsymbol{x}^{\prime}}{R}\right)\right)\right).\end{split}$

The latter expression, however, is identical to (11). Hence, taking (S.12)
into account, we can conclude that Algorithm 2 returns a solution to Problem 1
for the original AI system ${F}\circ{\Phi}$ with probabilities of success
satisfying (14), (15). $\square$

###  S.3 Additional material

####  S.3.1 Finding triggers $\boldsymbol{u}^{\prime}$ in Algorithms 1 and 2

A relevant optimisation problem for Algorithms 1 is formulated in (8).
Similarly to (8), one can pose a constrained optimisation problem for finding
a $\boldsymbol{u}^{\prime}$ in step 3 of Algorithm 2. This problem can be
formulated as follows:

$\begin{split}\boldsymbol{u}^{\prime}=&\arg\min_{\boldsymbol{u}\in\mathcal{U}}\left\|\frac{\Phi(\boldsymbol{u})}{R}-\frac{\Phi(\boldsymbol{u}^{\ast})}{R}-\boldsymbol{x}\right\|\\\
&\mbox{s. t.}\\\
&\gamma\left\|\frac{\Phi(\boldsymbol{u})}{R}-\frac{\Phi(\boldsymbol{u}^{\ast})}{R}\right\|\leq
1,\
\left\|\frac{\Phi(\boldsymbol{u})}{R}-\frac{\Phi(\boldsymbol{u}^{\ast})}{R}-\boldsymbol{x}\right\|<\delta.\end{split}$
(S.13)

Note that the vector $\boldsymbol{x}$ must be chosen randomly on
$\mathcal{S}_{n-1}(0,\delta)$, $\delta\in(0,1]$. One way to achieve this is to
generate a sample $\boldsymbol{z}$ from an $n$-dimensional normal distribution
$\mathcal{N}(0,I_{n})$ and then set
$\boldsymbol{x}=\delta\boldsymbol{z}/\|\boldsymbol{z}\|$.

A possible practical approach to determine $\boldsymbol{u}^{\prime}$ now is to
employ a gradient-based search

$\boldsymbol{u}^{\prime}_{k+1}=\mbox{Proj}_{\mathcal{U}}\left[\boldsymbol{u}^{\prime}_{k}-\gamma_{u}(k)\frac{\partial}{\partial\boldsymbol{u}}\mathcal{L}(\boldsymbol{u},\boldsymbol{u}^{\ast})\right],\
\boldsymbol{u}^{\prime}_{0}=\boldsymbol{u}^{\ast},$

where $\mbox{Proj}_{\mathcal{U}}$ is a projection operator. In our
experiments, $\mbox{Proj}_{\mathcal{U}}(\boldsymbol{u})$ returned
$\boldsymbol{u}=(u_{1},\dots,u_{n})$ if $u_{i}\in[0,255]$. If, however, the
$i$-th component of $\boldsymbol{u}$ is out of range ($u_{i}<0$ or
$u_{i}>255$) then the operator returned a vector with $0$ or $255$ in that
corresponding component.

The loss function $\mathcal{L}(\boldsymbol{u},\boldsymbol{u}^{\ast})$ is
defined as

$\mathcal{L}(\boldsymbol{u},\boldsymbol{u}^{\ast})=\left\|\frac{\Phi(\boldsymbol{u})}{R}-\frac{\Phi(\boldsymbol{u}^{\ast})}{R}-\boldsymbol{x}\right\|^{2}+\lambda_{1}\mathcal{G}_{1}(\boldsymbol{u})+\lambda_{2}\mathcal{G}_{2}(\boldsymbol{u}),\
\lambda_{1},\ \lambda_{2}\geq 0,$

and $\mathcal{G}_{1}$, $\mathcal{G}_{2}$ are relevant penalty functions:

$\mathcal{G}_{1}(\boldsymbol{u})=\left\\{\begin{array}[]{ll}\left(\gamma\left\|\frac{\Phi(\boldsymbol{u})}{R}-\frac{\Phi(\boldsymbol{u}^{\ast})}{R}\right\|-1\right)^{p_{1}},&\gamma\left\|\frac{\Phi(\boldsymbol{u})}{R}-\frac{\Phi(\boldsymbol{u}^{\ast})}{R}\right\|\geq
1\\\ 0,&\mbox{otherwise}\end{array}\right.$
$\mathcal{G}_{2}(\boldsymbol{u})=\left\\{\begin{array}[]{ll}\left(\left\|\frac{\Phi(\boldsymbol{u})}{R}-\frac{\Phi(\boldsymbol{u}^{\ast})}{R}-\boldsymbol{x}\right\|-\delta\right)^{p_{2}},&\left\|\frac{\Phi(\boldsymbol{u})}{R}-\frac{\Phi(\boldsymbol{u}^{\ast})}{R}-\boldsymbol{x}\right\|\geq\delta\\\
0,&\mbox{otherwise}\end{array}\right.$

with parameters $p_{1},p_{2}>0$, $\gamma_{u}(k)>0$ is a parameter ensuring
convergence of the procedure.

For Algorithm 1, terms $\Phi(\boldsymbol{u}^{\ast})/R$ should be replaced with
$0$, and $\boldsymbol{u}_{0}$ can be set to an arbitrary element of
$\mathcal{U}$.

######  Remark S.1 (Trigger search subspace)

Finally, note that sometimes it may be feasible to sample $\boldsymbol{x}$ in
step 2 of Algorithm 2 from a $S_{m-1}(0,\delta)\subset\mathbb{R}^{n}$, $2\leq
m<n$ instead of $S_{n-1}(0,\delta)$. On the one hand this will have a negative
affect on the probability of success as $n$ would need to be replaced with
$2\leq m<n$ in (14) and (15). On the other hand this extra “pre-processing”
step may enable us to lower the values of $\alpha$.

Indeed, if $\Phi(\boldsymbol{u}^{\ast})$ is an output of a ReLU layer then it
is likely that some of it’s components are exactly zero. This would constrain
gradient-based approaches to determine $\boldsymbol{u}^{\prime}$ starting from
$\boldsymbol{u}^{\ast}$ if $\boldsymbol{x}$ is sampled from
$S_{n-1}(0,\delta)$ as the corresponding gradients will always be equal to
zero. In our code [27] illustrating the application of Algorithms 1, 2 we
implement this pre-processing strategy.

####  S.3.2 Success bounds and a “concentrational collapse” for a class of
validation sets $\mathcal{V}$

Consider an AI system with an input-output map (2). Let an input
$\boldsymbol{u}^{\ast}$ (available to the attacker) and a validation set
$\mathcal{V}$, $|\mathcal{V}|=M$ (unknown to the attacker), be such that

$\|\Phi(\boldsymbol{u}^{\ast})-\Phi(\boldsymbol{u}_{i})\|\leq R\ \mbox{for
all}\ \boldsymbol{u}_{i}\in\mathcal{V}.$

In addition, suppose that both the validation set and the input
$\boldsymbol{u}^{\ast}$ satisfy Assumption S.1 below

######  Assumption S.1 (Data model)

Elements $\boldsymbol{u}_{1},\dots,\boldsymbol{u}_{M}$ and
$\boldsymbol{u}^{\ast}$ are drawn from a family of distributions
$P_{1},\dots,P_{M}$ and $P^{\ast}$ satisfying the following properties:

  1. 1.

There is a $\boldsymbol{c}\in\mathbb{R}^{n}$ such that
$\boldsymbol{u}_{1},\dots,\boldsymbol{u}_{M}$ are always in the set:

$\\{\boldsymbol{u}\in\mathcal{U}\ |\
\|\Phi(\boldsymbol{u})-\boldsymbol{c}\|\leq R/2\\}.$ (S.14)

  2. 2.

There is a $C\geq 0$ such that

$\begin{split}&P_{i}(\Phi(\boldsymbol{u}_{i})\in\mathbb{B}_{n}(\Phi(\boldsymbol{u}),r)|\boldsymbol{u}_{1},\dots,\boldsymbol{u}_{M})\leq
C\left(\frac{2r}{R}\right)^{n},\\\
&P^{\ast}(\Phi(\boldsymbol{u}^{\ast})\in\mathbb{B}_{n}(\boldsymbol{c},r)|\boldsymbol{u}_{1},\dots,\boldsymbol{u}_{M})\leq
C\left(\frac{2r}{R}\right)^{n},\end{split}$ (S.15)

for all $\boldsymbol{u}\in\mathcal{U}$.

Property (S.14) requests that the validation set is mapped into a ball
centered at $\Phi(\boldsymbol{c})$ and having a radius $R/2$ in the system’s
latent space, and (S.15) is a non-degeneracy condition restricting
pathological concentrations.

As we show below, if the validation set satisfies Assumption S.1 and the
attacker uses Algorithm 2 with $\boldsymbol{u}^{\ast}$ drawn from a
distribution $P^{\ast}$ satisfying conditions of Assumption S.1, then the
probabilities of generating a successful attack may be drastically increased.

###### Theorem S.1

Consider Algorithm 2, and let parameters $\gamma\in(0,1)$, $\alpha\in[0,1)$,
and $\delta\in(0,1]$ be such that (13) holds. Furthermore, suppose that
$\gamma\delta<1/2$ and let Assumption S.1 hold.

Then the probability $P_{a,1}$ that Algorithm 2 returns a solution to Problem
1 is bounded from below as:

$\begin{split}P_{a,1}\geq&P_{a}(\epsilon),\ \epsilon\in[0,\gamma\delta]\ \\\
P_{a}(\epsilon)=&1-C(1-2\epsilon)^{n}-M\frac{C}{2}\left[2\left(\frac{1}{4}-\left(\frac{1}{2}-\epsilon-\gamma\delta\right)^{2}\right)^{1/2}\right]^{n}\\\
&-\pi^{-1/2}\frac{\Gamma\left(\frac{n}{2}\right)}{\Gamma\left(\frac{n-1}{2}\right)}\int_{0}^{\arccos{(\varphi(\gamma,\delta,\alpha))}}\sin^{n-2}(\theta)d\theta.\end{split}$
(S.16)

Proof of Theorem S.1. The proof is essentially presented in Fig S.2.

Figure S.2: Concentrational collapse of unknown verification sets. Shaded
green area shows elements $\boldsymbol{u}\in\mathcal{V}$ for which
$((\Phi(\boldsymbol{u})-\Phi(\boldsymbol{u}^{\ast}))/R,\boldsymbol{x}^{\prime}/\|\boldsymbol{x}^{\prime}\|)\geq\gamma\|\boldsymbol{x}\|$.
Vectors $\boldsymbol{x}^{\ast}=\Phi(\boldsymbol{u}^{\ast})$ show latent
representations of $\boldsymbol{u}^{\ast}$, small circles show
$\Phi(\boldsymbol{u}_{i})$ (both, black and white). Filled black circles show
elements of $\mathcal{V}$ which do not satisfy this condition.

Consider the following three events

$\begin{split}\mbox{Event 1}:&\ \boldsymbol{u}^{\ast}:\
\|\Phi(\boldsymbol{u}^{\ast})-\boldsymbol{c}\|\leq R/2-\epsilon R,\end{split}$
$\begin{split}\mbox{Event 2}:&\ \mbox{for an element}\
\boldsymbol{u}_{i}\in\mathcal{V},\\\ &\Phi(\boldsymbol{u}_{i})\in
C^{\ast}=\left\\{\boldsymbol{x}\in\mathbb{B}_{n}(\boldsymbol{c},R/2)\left|\
\left(\frac{\Phi(\boldsymbol{u}^{\ast})-\boldsymbol{c}}{\|\Phi(\boldsymbol{u}^{\ast})-\boldsymbol{c}\|},\boldsymbol{x}-\boldsymbol{c}\right)\geq
R\left(\frac{1}{2}-(\epsilon+\gamma\delta)\right)\right.\right\\}\end{split}$

and

$\begin{split}\mbox{Event 3}:&\
\cos(|\angle(\boldsymbol{x}^{\prime},\boldsymbol{x}_{0})|)\geq\gamma\delta(1-\alpha).\end{split}$

The probability that Event $1$ holds is bounded as

$P(\mbox{Event
1})=P(\boldsymbol{u}^{\ast}\in\mathbb{B}_{n}(\boldsymbol{c},R/2-\epsilon
R))\leq C(1-2\epsilon)^{n}.$

The probability of Event 2 is does not exceed the probability that
$\Phi(\boldsymbol{u}_{i})$ belons to a half-ball of radius

$R\left(\frac{1}{4}-\left(\frac{1}{2}-\epsilon-\delta\gamma\right)^{2}\right)^{1/2}$

and hence

$P(\mbox{Event
2})\leq\frac{C}{2}\left[2\left(\frac{1}{4}-\left(\frac{1}{2}-\epsilon-\delta\gamma\right)^{2}\right)^{1/2}\right]^{n}.$

The probability that Event 3 holds is bounded from above by

$P(\mbox{Event
3})\leq\pi^{-1/2}\frac{\Gamma\left(\frac{n}{2}\right)}{\Gamma\left(\frac{n-1}{2}\right)}\int_{0}^{\arccos{(\varphi(\gamma,\delta,\alpha))}}\sin^{n-2}(\theta)d\theta$

(see proof of Theorem 1 for details). If none of these events hold then
Algorithm 2 produces a solution to Problem 1. The probability when this occurs
is bounded from below as (S.16) (see (S.5)). $\square$

Theorem S.1 reveals a phenomenon where validation sets which could be deemed
as sufficiently large in the sense of bounds specified by Theorem 1 and
Corollary 1 may still be considered as “small” due to bound ( S.16). We call
this phenomenon concentrational collapse. When concentrational collapse
occurs, the AI system becomes particularly vulnerable to small validation sets
$\mathcal{V}$ even when the attacker’s accuracy is small ($\alpha$ large). For
example for $n=200$, $\epsilon=0.01$, $\gamma=0.9$, $\delta=1/3$

$P(\mbox{Event 2})\leq C8.4343\times 10^{-8}$

implying that the owner would have to generate and keep a rather large
validation set $\mathcal{V}$ to make up for these small probabilities.

In view of Remark S.1, when the vector $\boldsymbol{x}$ is drawn from
$\mathbb{S}_{n_{p}-1}(0,\delta)$, $2\leq n_{p}<n$, bound (S.16) becomes:

$\begin{split}P_{a,1}\geq&P_{a}(\epsilon),\ \epsilon\in[0,\gamma\delta]\ \\\
P_{a}(\epsilon)=&1-C(1-2\epsilon)^{n}-M\frac{C}{2}\left[2\left(\frac{1}{4}-\left(\frac{1}{2}-\epsilon-\gamma\delta\right)^{2}\right)^{1/2}\right]^{n}\\\
&-\pi^{-1/2}\frac{\Gamma\left(\frac{n_{p}}{2}\right)}{\Gamma\left(\frac{n_{p}-1}{2}\right)}\int_{0}^{\arccos{(\varphi(\gamma,\delta,\alpha))}}\sin^{n_{p}-2}(\theta)d\theta.\end{split}$
(S.17)

####  S.3.3 Architecture and training parameters of deep convolutional neural
networks used in experiments

Architecture of a deep convolutional neural network which we used in our
experiments is shown in Table S.1. The architecture features $3$ fully
connected layers, with layers $15$ – $18$ (shown in red) and layers $1$ – $14$
representing maps $F$ and $\Phi$, respectively.

This architecture is built on a standard benchmark example from Mathworks. The
original basic network was appended by layers $13$ – $16$ to emulate dense
fully connected structures present in popular deep learning models such as
VGG16, VGG19. Note that the last $6$ layers (layers $13$ – $18$) are in fact
$3$ dense layers with ReLU, ReLU, and softmax activation functions,
respectively, if the same network is implemented in Tensorflow-Keras. Having
$3$ dense layers is not essential for the method, and the attacks can be
implemented in other networks featuring ReLU or sigmoid neurons.

Table S.1: Network architecture used in experiments. Red color shows layers which we represent by map $\mathcal{F}$ in (1) Layer number | Type | Size
---|---|---
1 | Input | $28\times 28\times 1$
2 | Conv2d | $3\times 3\times 8$
3 | Batch normalization |
4 | ReLU |
5 | Maxpool | pool size $2\times 2$, stride $2\times 2$
6 | Conv2d | $3\times 3\times 16$
7 | Batch normalization |
8 | ReLU |
9 | Maxpool | pool size $2\times 2$, stride $2\times 2$
10 | Conv2d | $3\times 3\times 32$
11 | Batch normalization |
12 | ReLU |
13 | Fully connected | 200
14 | ReLU |
15 | Fully connected | 100
16 | ReLU |
17 | Fully connected | 10
18 | Softmax | 10

Outputs of the softmax layer assign class label to images. Label $1$
corresponds to digit “$0$”, label $2$ to digit “$1$”, and label $10$ to digit
“$9$”, respectively.

Training. The original MNIST dataset of $10,000$ images was split into a
training set consisting of $7,500$ images and a test set containing $2,500$
images (see example code for details of implementation [27]). The network was
trained over $30$ epochs with the minibatch size parameter set to $128$
images, and with a momentum version of the stochastic gradient descent. The
momentum parameter was set to $0.9$ and the learning rate was
$0.01/(1+0.001k)$, where $k$ is the training instance’s number within an
epoch.

Overall, we conducted $20$ attack experiments involving determining different
trigger-target pairs and changing the network’s architecture in accordance
with planting scenarios $1$ and $3$. The original networks’ classification
accuracy (before the attack), expressed as the percentage of correct
classifications on the test set, was within $[98.64\%,99.84\%]$ in all these
$20$ experiments.

Computational environment and indicative compute resources. All experiments
were performed in MATLAB2020b on an HP Zbook 15 G3 laptop with a Core
i7-6820HQ CPU, $16$ Gb of RAM and Nvidia Quadro 1000M GPU. Training a single
instance of a network in this environment took approximately $300$ seconds.
Running a section of the code in [27] implementing $100,000$ gradient steps to
determine a trigger input took about $3400$ seconds, and a part of the code
determining which neuron to attack took about $95$ seconds. These figures
varied marginally from one run to another.

####  S.3.4 Trigger and target images

In addition to examples of triggers shown in Fig. 3, we generated triggers to
all digits $0$ – $9$. These triggers, $\boldsymbol{u}^{\prime}$, as well as
the original images (target images), $\boldsymbol{u}^{\ast}$, are shown in
S.3. As is evident from these figures, triggers retain significant resemblance
of the original target images $\boldsymbol{u}^{\ast}$.

Moreover, when trigger images were shown to the original networks (i.e.
trained networks before we subjected them to stealth attacks produced by
Algorithm 2), in many cases these network returned class labels which
coincided with class labels of the target images. A summary of this test is
provided in Figure S.4. Red colour highlights instances when the networks’
original classifications of the target images did not match those of the
trigger. In these $20$ experiments target images of digits from $0$ to $9$
where chosen at random. In each row, the number of entries in the second
column in the table in Figure S.4 corresponds to the number of times the digit
in the first column was chosen as a “target” in these experiments.

Figure S.3: Examples of trigger images $\boldsymbol{u}^{\prime}$ (rows $1$ and $3$) and their corresponding ”target images” $\boldsymbol{u}^{\ast}$ (rows $2$ and $4$). Target image | Predicted
---|---
of the trigger | label
0 | 0,3
1 | 4,7
2 | 2
3 | 3
4 | 4,4
5 | 5
6 | 6,6,6
7 | 7
8 | 8,5,6,9
9 | 9,9,9
Figure S.4: Retained information content in the trigger images

####  S.3.5 Accuracy of implementation of stealth attacks achieved in
experiments and limits of theoretical bounds in Theorem 1 and Corollary 1

In all $20$ attack experiments we were able to create a ReLU neuron which was
completely silent on the set $\mathcal{V}$ and, at the same time, was
producing desired responses when a trigger was presented as an input to the
network. Empirical values of the accuracy of implementation of these attacks,
$\alpha$ and dimension $n$ of the random perturbation are shown in Table S.2.

$\\#$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
---|---|---|---|---|---|---|---|---|---|---
$\alpha$ | 0.179 | 0.200 | 0.358 | 0.247 | 0.313 | 0.406 | 0.311 | 0.277 | 0.362 | 0.244
$n$ | 112 | 125 | 122 | 116 | 125 | 122 | 115 | 121 | 128 | 111

$\\#$ | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20
---|---|---|---|---|---|---|---|---|---|---
$\alpha$ | 0.417 | 0.271 | 0.271 | 0.227 | 0.246 | 0.287 | 0.401 | 0.327 | 0.436 | 0.285
$n$ | 122 | 124 | 124 | 119 | 110 | 117 | 120 | 109 | 110 | 117

Table S.2: Accuracy $\alpha$ of finding triggers expressed as
$\alpha=\delta^{-1}\|\Phi(\boldsymbol{u}^{\prime})/R-\boldsymbol{x}\|$.

These figures, along with the fact that all these attacks returned a
successful outcome (for Scenario $1$), enable us to illustrate how
conservative the bounds provided in Theorem 1 could be.

Indeed, computing the term

$P_{1}(\alpha,\delta,\gamma,n)=\pi^{-1/2}\frac{\Gamma\left(\frac{n}{2}\right)}{\Gamma\left(\frac{n-1}{2}\right)}\int_{0}^{\arccos{(\varphi(\gamma,\delta,\alpha))}}\sin^{n-2}(\theta)d\theta$

for $\gamma=0.9$ in bound (14) for $\alpha,n$ taken from the first experiment
in Table S.2 (column corresponding to $\\#=1$) returns
$P_{1}(\alpha,\delta,\gamma,n)=0.1561$. Substituting this figure into (14) for
$M>10$ produces a negative number rendering the bound not useful in this case.
The same comment applies to other experiments. At the same time, as our
experiments confirm, the attacks turn out to be successful in practice. If,
however, we set $\alpha=0$ then the value of $P_{1}(0,\delta,\gamma,n)$ for
the first experiment becomes $4.9180\times 10^{-4}$.

These observations highlight limitations of bounds in Theorem 1 and Corollary
1 for determining probabilities of success in practice when the values
$\alpha$ are large. They also show additional relevance of Theorem S.1 and the
“concentrational collapse” effect for developing better understanding of
stealth attacks. Indeed, applying bound (S.17) with $n=200$, $\epsilon=0.02$,
$\gamma=0.9$ and $n_{p}=112$, $\alpha=0.179$ (first row from Table S.2) one
obtains:

$P_{a,1}\geq 1-C\times 2.8461\times 10^{-4}-MC\times 4.6866\times
10^{-7}-0.1561.$

If parameter $C$ does not exceed $100$ then this latter bound is more
consistent with what we observed in experiments. Its validity, however, too
depends on Assumption S.1 about the distributions from which the set
$\mathcal{V}$ and $\boldsymbol{u}^{\ast}$ are sampled from.

####  S.3.6 Selection of a neuron to attack

Let $L$ be the layer in which a neuron is to be selected for the attack. We
suppose that the network has a layer $L+1$ in its computational graph. Suppose
that $w^{[L]}_{i,j}$ denotes the $j$-th weight of the $i$-th neuron in layer
$L$, and the total number of neurons in layer $L$ is $N_{L}$.

We say that the output weight vector of the $i$-th neuron in layer $L$ is a
vector

$\bar{\boldsymbol{w}}_{i}^{[L]}=\left(\begin{array}[]{c}w^{[L+1]}_{1,i}\\\
w^{[L+1]}_{2,i}\\\ \vdots\\\ w^{[L+1]}_{N_{L},i}\end{array}\right).$

Determining neurons’ ranks. For each $i=1,\dots,N_{L}$, we computed
$L_{1}$-norms of $\bar{\boldsymbol{w}}_{i}^{[L]}$:

$\|\bar{\boldsymbol{w}}_{i}^{[L]}\|_{1}=\sum_{j=1}^{N_{L+1}}|w_{j,i}^{L+1}|$

and created a list of indices $n_{1},n_{2},\dots,n_{N_{L}}$ such that

$\|\bar{\boldsymbol{w}}_{n_{1}}^{[L]}\|_{1}\leq\|\bar{\boldsymbol{w}}_{n_{2}}^{[L]}\|_{1}\leq\cdots\leq\|\bar{\boldsymbol{w}}_{n_{N_{L}}}^{[L]}\|_{1}.$

Susceptibility rank of the $i$-th neuron, $\mbox{Rank}(i)$, is defined as a
number $k\in\\{1,\dots,N_{L}\\}$:

$\mbox{Rank}(i)=k:\ i=n_{k}.$

If the above holds for multiple values of
$n_{k}:n_{k_{1}},n_{k_{2}},\dots,n_{k_{m}}$ then the neuron’s rank is
determined by selecting a single number from $k_{1}$,…,$k_{m}$ at random.

In our experiments, when implementing stealth attacks in accordance with
Scenario $3$, we always selected neurons whose susceptibility rank is $1$.


M^{\prime}_{2}$. To see that $M^{\prime}$ is a perfect matching, consider a
vertex $u_{i}\in V(G^{\prime})$ for some $i\in\\{0,1\\}$. Assume that there
exists two neighbors $x,y$ of $u_{i}$ such that $xu_{i},yu_{i}\in M^{\prime}$.
Clearly, as $u_{i}$ can have at most one neighbor outside $G_{i}$, we can
assume that $y=w_{i}$ for some $w_{i}\in V(G_{i})$, so by definition of
$M^{\prime}$, we have $uw\in M$, and in particular, $M$ covers $u$. Therefore,
if $x=v_{i}$ for some $v_{i}\in V(G_{i})$, we also have that $uv\in M$, a
contradiction with $M$ being a matching. Otherwise, $x=u_{1-i}$, but the edge
$u_{i}u_{1-i}$ belongs to $M^{\prime}$ if and only if $M$ does not cover $u$,
and that also gives a contradiction. Hence, $M^{\prime}$ is a matching. To see
that $M^{\prime}$ is perfect, note that if $u\in V(G)$ is incident to an edge
$uw\in M$, then $u_{i}w_{i}\in M^{\prime}_{1}$. Otherwise, $M$ does not cover
$u$, and then $u_{i}u_{1-i}\in M^{\prime}_{2}$. Finally, observe that
$\sum_{e\in M^{\prime}}\mathfrak{w}^{\prime}(e)\geqslant 2\sum_{e\in
M}\mathfrak{w}(e)\geqslant 2k$.

Now assume that there exists a perfect matching $M^{\prime}$ in $G^{\prime}$
such that $\mathfrak{w}^{\prime}(M^{\prime})\geqslant 2k$. As for every $e\in
U^{*}$ it holds that $\mathfrak{w}^{\prime}(e)=0$, we must have $\sum_{e\in
M^{\prime}\cap E(G_{1})}\mathfrak{w}^{\prime}(e)\geqslant k$ or $\sum_{e\in
M^{\prime}\cap E(G_{2})}\mathfrak{w}^{\prime}(e)\geqslant k$. Assume by
symmetry that the first case holds. We define a subset $M$ of $E(G)$ as
follows: $uv\in M$ if and only if $u_{1}v_{1}\in M^{\prime}$. Clearly, $M$ is
a matching, and $\sum_{e\in M\cap E(G)}\mathfrak{w}(e)=\sum_{e\in
M^{\prime}\cap E(G_{1})}\mathfrak{w}^{\prime}(e)\geqslant k$. It remains to
verify that for every vertex $u$ of $G$, such that $u\in U$, there exists
$w\in N(u)$ such that $uw\in M$. Since $M^{\prime}$ is perfect, there exists
$x\in V(G^{\prime})$ such that $u_{1}x\in M^{\prime}$. However, as $u_{1}$ has
no neighbors outside $G_{1}$, $x=w_{1}$ for some $w\in V(G)$. Therefore,
$uw\in M$ by definition of $M$. $\blacksquare$

Step 2: Let $p=\max_{e\in E(G^{\prime})\mathfrak{w}^{\prime}(e)}$,
$m=p\cdot|E(G^{\prime})|+1$, and $n=|V(G^{\prime})|/2$ (recall that
$|V(G^{\prime})|$ is even). For every $e\in E(G^{\prime})$ we define
$\mathfrak{w}^{\prime\prime}(e)=\mathfrak{w}^{\prime}(e)+m$, and we set
$k^{\prime}=nm+2k$.

######  Claim 4.2.

There exists a perfect matching $M^{\prime}$ in $G^{\prime}$ such that
$\mathfrak{w}^{\prime}(M^{\prime})\geqslant 2k$ if and only if
$(G^{\prime},\mathfrak{w}^{\prime\prime},k^{\prime})$ is a yes-instance of
Maximum Weight Matching.

_Proof of Claim._ Assume that if there exists a perfect matching $M^{\prime}$
in $G^{\prime}$ such that $\sum_{e\in
M^{\prime}}\mathfrak{w}^{\prime}(e)\geqslant 2k$. Since $M^{\prime}$ is
perfect, $|M^{\prime}|=n$. Hence,

$\displaystyle\sum_{e\in M^{\prime}}\mathfrak{w}^{\prime\prime}(e)$
$\displaystyle=\sum_{e\in
M^{\prime}}\left(m+\mathfrak{w}^{\prime}(e)\right)\geqslant nm+\sum_{e\in
M^{\prime}}\mathfrak{w}^{\prime}(e)\geqslant nm+2k.$

We claim that the opposite holds: i.e., if $M^{\prime}$ is a matching in
$G^{\prime}$ such that $\sum_{e\in
M^{\prime}}\mathfrak{w}^{\prime\prime}(e)\geqslant nm+2k$, then $M^{\prime}$
is perfect, and $\sum_{e\in M^{\prime}}\mathfrak{w}^{\prime}(e)\geqslant 2k$.
Indeed,

$\displaystyle\sum_{e\in M^{\prime}}\mathfrak{w}^{\prime}(e)=\sum_{e\in
M^{\prime}}\left(\mathfrak{w}^{\prime\prime}(e)-m\right)=\sum_{e\in
M^{\prime}}\mathfrak{w}^{\prime\prime}(e)-|M^{\prime}|\cdot m\geqslant
m(n-|M^{\prime}|)+2k\geqslant 2k,$ (1)

and since $\sum_{e\in M^{\prime}}\mathfrak{w}^{\prime}(e)\leqslant
p\cdot|M^{\prime}|\leqslant m-1$, then if $|M^{\prime}|<n$:

$\displaystyle\sum_{e\in
M^{\prime}}\mathfrak{w}^{\prime\prime}(e)=m\cdot|M^{\prime}|+\sum_{e\in
M^{\prime}}\mathfrak{w}^{\prime}(e)\leqslant m(n-1)+(m-1)=nm-1,$

a contradiction with $\sum_{e\in
M^{\prime}}\mathfrak{w}^{\prime\prime}(e)\geqslant nm+2k$. Hence,
$|M^{\prime}|\geqslant n=|V(G^{\prime})|/2$, i.e., $M^{\prime}$ is perfect.
$\blacksquare$

By 4.1 and 4.2, $(G,U,\mathfrak{w},k)$ is a yes-instance of MWM∗ if and only
if $(G^{\prime},\mathfrak{w}^{\prime\prime},k^{\prime})$ is a yes-instance of
Maximum Weight Matching. Since the latter can be checked in polynomial time by
the algorithm of Edmonds [16], and
$(G^{\prime},\mathfrak{w}^{\prime\prime},k^{\prime})$ can be constructed in
time polynomial in $|V(G)|$, we obtain the answer for $(G,U,\mathfrak{w},k)$
in polynomial time.

## Appendix. Pos-1-in-3-SAT with each variable occuring a constant number of
times

See 24

###### Proof.

Consider an instance of 3-Sat with $n$ variables and $m$ clauses. First, by
the result of Tovey [51], we create an equivalent instance of 3-Sat, with at
most $\mathcal{O}(n+m)$ variables and at most $\mathcal{O}(m)$ clauses, and
such that each variable appears in at most $4$ clauses. Then, using the
reduction by Schaeffer [48, Lemma 3.5], we obtain an equivalent instance
$\mathcal{I}$ of 1-in-3-Sat, with $\mathcal{O}(n+m)$ variables and at most
$\mathcal{O}(m)$ clauses, and such that each variable appears in at most $4$
clauses.

Finally, we create an instance $\mathcal{I}^{\prime}=(X,\mathcal{C})$ of
Pos-1-in-3-Sat from $\mathcal{I}$ as follows. For every variable $x$ of
$\mathcal{I}$, we introduce five variables $x_{0},x_{1},a,b,c$. We replace
every negative occurrence of $x$ in a clause by $x_{0}$, and each positive
occurrence by $x_{1}$, and we add three clauses
$\\{x_{0},x_{1},a\\},\\{x_{0},x_{1},b\\},\\{a,b,c\\}$. It is straightforward
to verify that the instance constructed in this way is equivalent to
$\mathcal{I}$, in which each variable appears in a most $6$ clauses. Moreover,
the number of variables and clauses is $\mathcal{O}(n+m)$.

Hence, an algorithm solving $\mathcal{I}^{\prime}$ in time
$2^{o(|X|+|\mathcal{C}|)}$ could be used to solve the initial instance of
3-Sat in time $2^{o(n+m)}$, which contradicts the ETH (see e.g., [15, Theorem
14.4]).