fit,shapes

# Game of Trojans: Adaptive Adversaries Against Output-based Trojaned-Model
Detectors

Dinuka Sahabandu∗
University of Washington  Xiaojun Xu∗
University of Illinois  Arezoo Rajabi
University of Washington  Luyao Niu
University of Washington  Bhaskar Ramasubramanian
Western Washington University  Bo Li
University of Illinois  Radha Poovendran
University of Washington

###### Abstract

Deep Neural Network (DNN) models are vulnerable to Trojan attacks, wherein a
Trojaned DNN will mispredict trigger-embedded inputs as malicious targets,
while the outputs for clean inputs remain unaffected. Output-based Trojaned
model detectors, which analyze outputs of DNNs to perturbed inputs have
emerged as a promising approach for identifying Trojaned DNN models. At
present, these SOTA detectors assume that the adversary is (i) static and (ii)
does not have prior knowledge about the deployed detection mechanism.

In this paper, we propose and analyze an adaptive adversary that can retrain a
Trojaned DNN and is also aware of SOTA output-based Trojaned model detectors.
We show that such an adversary can ensure (1) high accuracy on both trigger-
embedded and clean samples and (2) bypass detection. Our approach is based on
an observation that the high dimensionality of the DNN parameters provides
sufficient degrees of freedom to simultaneously achieve these objectives. We
also enable SOTA detectors to be adaptive by allowing retraining to
recalibrate their parameters, thus modeling a co-evolution of parameters of a
Trojaned model and detectors. We then show that this co-evolution can be
modeled as an iterative game, and prove that the resulting (optimal) solution
of this interactive game leads to the adversary successfully achieving the
above objectives.

In addition, we provide a greedy algorithm for the adversary to select a
minimum number of input samples for embedding triggers. We show that for
cross-entropy or log-likelihood loss functions used by the DNNs, the greedy
algorithm provides provable guarantees on the needed number of trigger-
embedded input samples. Extensive experiments on four diverse datasets- MNIST,
CIFAR-10, CIFAR-100, and SpeechCommand- reveal that the adversary effectively
evades four SOTA output-based Trojaned model detectors- MNTD, NeuralCleanse,
STRIP, and TABOR.

**footnotetext: These authors contributed equally to this work

##  1 Introduction

Deep neural networks (DNNs) used for machine learning in data-intensive
applications such as vision [29], health [15], games [45], and autonomous
driving [7] have achieved impressive levels of performance. However, such high
performance is typically associated with large training datasets and high
computation cost [5]. Online platforms that provide ready-to-use models and
architectures for applications such as image classification, e.g., [1, 2, 3],
can overcome the need for large amounts of data and reduce computational
costs.

When the end-user of such ‘models in the wild’ is different from the owner,
such models are susceptible to adversarial retraining and manipulation,
affecting model integrity [32]. Trojan trigger-embedding is one such attack
[32, 19, 38]. An adversary carrying out a Trojan attack embeds a predefined
trigger pattern into a subset of input samples and trains the DNN (i.e.,
Trojaned model) such that a trigger-embedded input will lead to an adversary-
desired output label that is different from the correct output label [19, 32]
while output labels corresponding to ‘clean’ inputs remain unaffected. The
negative impact of Trojaned DNN models have been demonstrated in applications
including autonomous driving [19], facial recognition [55], and natural
language processing [40]. Recent Trojan trigger-embedding strategies have
evolved to focus on developing advanced mixing techniques so that it is
difficult to isolate trigger-embedded samples from clean input samples [46,
41].

Effective techniques to detect Trojaned models have also been evolving along
with attacks [27, 31, 36, 56]. Trojan detection methods fall broadly into two
categories: input-based filtering and output-based Trojaned model detectors.
Input-based filtering techniques aim to identify and eliminate Trojan trigger-
embedded input samples before they are input to the DNN [22, 37, 20]. On the
other hand, output-based detectors seek to determine if a candidate model is
Trojaned only by comparing outputs of a clean model and the model under
inspection [54, 50, 18, 21]. Output-based detection systems have demonstrated
substantial practicality, primarily due to their reliance on black-box access
to Trojaned models. Due to their demonstrated effectiveness in detecting
Trojaned models with high accuracy, while maintaining very low false positive
rates and computational overhead, we exclusively focus on output-based
Trojaned model detectors in this paper.

At present, SOTA output-based Trojaned model detectors [54, 50, 18, 21]
operate under an assumption that adversaries are static and lack prior
knowledge of the implemented detection mechanisms. In reality, adversaries
learn about the detection approaches and try to adapt their approaches to
outmaneuver detectors. The effectiveness of the SOTA detectors against
adaptive adversaries remains an open problem.

Figure 1: Two-step offline training of Trojaned DNN models. Step 1: the
adversary uses the trigger to be embedded along with detector parameters to
train an enhanced Trojaned DNN model; Step 2: the adversary uses the enhanced
Trojaned DNN to compute the new detector parameters that would maximize
detection. The adversary repeats Step 1 and Step 2 until there is no further
improvement in detector parameters or Trojaned DNN model performance.

In this paper, we propose an adaptive backdoor attack strategy with
convergence guarantees, and study the effectiveness of SOTA detectors against
adaptive adversaries that have prior knowledge of the detection mechanisms.
Such adaptive adversaries can integrate prior knowledge of the detection
process and all detector parameters into offline training of Trojaned DNN
models. The adaptive adversary’s Trojan training procedure consists of two
steps: Step 1: the adversary uses the trigger to be embedded along with
detector parameters to train an enhanced Trojaned DNN model; Step 2: the
adversary uses the enhanced Trojaned DNN to compute the new detector
parameters that would maximize detection. The updated detector parameters from
Step 2 are then used along with the trigger to improve the Trojaning of DNN in
Step 1. The adversary repeats Step 1 and Step 2 until there is no further
improvement in detector parameters or Trojaned DNN model performance. A
schematic of this alternating iterated update between the Trojaning of the DNN
model and then updating detector parameters is illustrated in Figure 1.

In the two-step process above, we use an insight that DNNs possess ample
degrees of freedom in values of their model parameter, allowing them to be
effectively trained with Trojan trigger-embedded input samples [57, 51, 34]
without losing classification accuracy. Our main observation is that an
adaptive adversary can exploit this degree of freedom in the DNN to ensure
that the two-step iterative procedure described above in Step 1 and Step 2
achieves high accuracy on both Trojaned and clean inputs while fully bypassing
output-based Trojaned model detectors. Our approach includes a novel “detector
in the loop” adaptive retraining step by the adversary to make existing Trojan
attacks more evasive against output-based Trojaned model detectors.

Our first contribution in this paper is a formalization of the interaction
between an adaptive adversary and output-based Trojan model detectors as an
iterative game. We show that at the end of this iterative interaction, the
adversary will fully bypass detection. From the detector’s perspective, our
results prove that the final output of the Trojaned DNN will be
indistinguishable from an output of a clean model.

As our second contribution, we carry out extensive experiments to demonstrate
that an adaptive adversary is successful in bypassing output-based Trojaned
model detectors while maintaining high accuracy on both trigger-embedded and
clean samples. Our results on four datasets- MNIST [30], CIFAR-10 [28],
CIFAR-100 [28], and SpeechCommand [52]\- reveal that the adversary is
overwhelmingly effective in bypassing four SOTA Trojan detectors- MNTD [54],
NeuralCleanse [50], STRIP [18], and TABOR [21]. We also employ a greedy
algorithm to enable the adversary to select the minimum number of input
samples for Trojan trigger embedding. When loss functions used by the Trojaned
DNN are the cross-entropy or log-likelihood losses, we also prove that the
greedy algorithm yields provable bounds on the minimum number of required
trigger-embedded samples to be used.

The rest of this paper is organized as: Sec. 2 introduces preliminaries, Sec.
3 details our threat model. Sec. 4 details the interaction game between the
adversary and detector, and Sec. 5 provides certifiable bounds on the number
of Trojan-embedded samples. Sec. 6 presents experimental results, Sec. 7
provides explanations to underscore our results, and Sec. 8 discusses related
work. Sec. 9 concludes the paper.

##  2 Background

###  2.1 DNNs and Trojan Attacks

Let $\\{C_{1},\cdots,C_{k}\\}$ be a set of $k$ classes and
$\mathscr{D}=\\{(x,y)\\}$ be a dataset, where $x$ is a data sample, and $y$ is
a vector whose $j^{th}$ entry $y[j]=1$ if $x$ is of class
$j\in\\{1,\ldots,k\\}$ and $y[j]=0$ otherwise. DNN classifiers are trained to
predict the most relevant class among the $k$ possible classes for a given
input. The output of the DNN for input $x$ is a vector, $f_{\theta}(x)$, where
$\theta$ represents parameters of the DNN. The $j^{th}$ entry of
$f_{\theta}(x)$, denoted $f_{\theta}(x)[j]$, gives the probability that $x\in
C_{j}$. The sample $x$ is assigned to the class that has the highest
probability in $f_{\theta}(x)$, i.e., $x$ is assigned to class $C_{i}$ if
$f_{\theta}(x)[i]>f_{\theta}(x)[j]\>\>\forall j\neq i$.

DNN classifiers have been shown to be vulnerable to Trojan attacks [32]. An
adversary carrying out a Trojan attack embeds a _trigger_ into a subset of
clean samples and changes labels of such samples to an adversary-desired
target class, $y_{T}$. As a consequence, a DNN model trained with a
combination of trigger-embedded and clean input samples will exhibit erroneous
behaviors at test-time. The DNN will output $y_{T}$ when presented with
trigger-embedded data $x_{T}$, while the DNN will output the ‘true’ label $y$
for clean samples $x$. We denote the set of Trojan-trigger embedded samples by
$\tilde{\mathscr{D}}=\\{(x_{T},y_{T})\\}$.

###  2.2 Output-based Trojaned Model Detectors

In this paper, we focus on a class of defenses, termed Output-based Trojaned
Model Detectors. Such detectors inspect the outputs of DNNs in response to
random or perturbed input samples to decide whether a model is Trojaned. Such
detectors fall into two broad categories: (i) Detectors employing supervised
learning techniques such as binary classification to differentiate the outputs
of DNNs for random input samples (e.g., MNTD[54]), and (ii) Detectors using
unsupervised learning methods such as outlier detection for distinguishing DNN
outputs in response to perturbed inputs (e.g., Neural-Cleanse[50], STRIP[18],
TABOR[21]).

We observe that perturbed inputs to DNN constitute a subset of random inputs-
this is especially true when representative training data can be generated via
jumbo learning [54]. For predictive modeling tasks with specific objectives
and adequate labeled data, such as differentiating Trojan-infected from clean
models using data gathered via jumbo learning, supervised learning has been
shown to outperform alternative approaches [6]. We consider detectors that use
supervised learning via a binary classifier to analyze DNN outputs in response
to random inputs corresponding to Category (i) discussed above. Our
experiments evaluate effectiveness of our adaptive adversary against both
types of detectors. We detail the training process for detectors from Category
(i) below.

Initially, the detector collects outputs from both clean and Trojaned models
generated in response to random inputs, labeling them with $0$ for outputs
from the clean model and $1$ for those from the Trojaned model. Subsequently,
the detector uses this labeled data to train a binary classifier to
effectively distinguish between outputs corresponding to clean and Trojaned
models. In the following, we introduce a set of notations to formally define
the training procedure of the detector.

Let the binary classifier model (detector) with parameters $\theta_{D}$ be
defined as $h_{\theta_{D}}$. We use $\theta_{T}$ and $\theta_{C}$ to denote
the parameters of the Trojaned model $f_{\theta_{T}}$ and the clean model
$f_{\theta_{C}}$, respectively. The detector employs a log-likelihood-based
loss function to assess quality of detection [54]. For an input $x$, we define
outputs of the Trojaned and clean DNN models by $z_{T}:=f_{\theta_{T}}(x)$ and
$z_{C}:=f_{\theta_{C}}(x)$ respectively. Similarly, we denote probability
distributions of Trojaned outputs $z_{T}$ and clean outputs $z_{C}$ by $q_{T}$
and $q_{C}$ respectively. With these notations, the objective of the training
procedure of the detector to maximize accuracy of identifying (a) a Trojaned
DNN and (b) a clean DNN model based on their response to any input sample can
be expressed as [6]:

$\displaystyle\max_{\theta_{D}}\hskip 2.84526pt\mathbb{E}_{z_{T}\sim
q_{T}}[\log(1-h_{\theta_{D}}(z_{T}))]+\mathbb{E}_{z_{C}\sim
q_{C}}[\log(h_{\theta_{D}}(z_{C}))].$ (1)

##  3 Threat Model

In this section, we introduce our assumptions on adversary’s goals, knowledge,
capabilities, and actions.
Adversary Goals: The adversary has three objectives: (i) achieve high
classification accuracy on clean input samples; (ii) ensure high accuracy on
Trojan-trigger embedded input samples, leading them to be misclassified into a
class desired by the adversary; and (iii) evade detection by output-based
Trojan model detectors.
Adversary Knowledge: The adversary is assumed to be fully aware of the
deployment of an output-based Trojan detector.
Adversary Capabilities: The adversary can download and retrain a DNN using
publicly available datasets. The adversary is capable of effectively embedding
triggers into any subset of data. It is assumed that the adversary possesses
sufficient computational resources to train a local model and estimate the
proportion of data that needs to be poisoned. Additionally, the adversary is
equipped to train a proxy detector model by solving the optimization problem
outlined in Eqn.(1). The adversary can then use the decisions (i.e., the
probability of a model being classified as Trojaned) made by the trained proxy
detector to update the parameters of the Trojaned model.
Adversary Actions: The adversary begins by selecting a subset of clean samples
into which to embed Trojan triggers. Next, the adversary constructs a loss
function comprising three additive components, each tailored to measure attack
performance with respect to adversary goals (i), (ii), and (iii).
Specifically, the loss function corresponding to goals (i) and (ii) are
categorical cross-entropy loss functions [53, 35], while the loss functions
related to goal (iii) is the log-likelihood-based loss [54]. The adversary
then trains to update parameters of the Trojaned model to minimize the sum of
these three loss components. Following standard notations for minimizing the
average loss [6], we can write this optimization problem as:

$\displaystyle\min_{\theta_{T}}\hskip 2.84526pt$
$\displaystyle\mathbb{E}_{z_{T}\sim q_{T}}[\log(1-h_{\theta_{D}}(z_{T}))]$
$\displaystyle+\mathbb{E}_{(x_{T},y_{T})\in\tilde{\mathscr{D}}}\ell_{\theta_{T}}(x_{T},y_{T})+\mathbb{E}_{(x,y)\in\mathscr{D}}\ell_{\theta_{T}}(x,y).$
(2)

Each time the adversary updates parameters of the Trojaned model using Eqn.
(2), the defender can similarly update parameters of its binary classifier
using Eqn. (1) to counter the adversary’s adjustments. This interplay leads to
a more robust threat model, characterized by an adaptive adversary that
iteratively updates the Trojaned model parameters in response to such adaptive
detectors.

##  4 Adversary-Detector Co-Evolution

Figure 2:  This figure shows a schematic of Trojan model training using our MM
Trojan algorithm (Algo. 4.1). Red pixel patterns represents Trojan triggers
embedded by the adversary. In Sec. 4, we abstracted the $K$ Trojaned and $K$
clean DNN models by a single Trojan and single clean DNN model. These
abstractions are shown by the red and blue boxes titled ‘Shadow Trojaned
Models’ and ‘Shadow Pre-trained Clean Models’ respectively. $\mathscr{D}$ and
$\tilde{\mathscr{D}}$ represent the set of clean samples and subset of clean
samples into which Trojan triggers are embedded.
$\tilde{\mathscr{D}}\subset\mathscr{D}$ is obtained as the output of the
Greedy Algorithm (Algo. 5.1). Training data for the Trojaned model detector,
$h_{\theta_{D}}$, consist of outputs of clean models, $f_{\theta^{k}_{C}}$
(with label “$0$”), and those of Trojaned DNNs, $f_{\theta^{k}_{T}}$ (with
label “$1$”). The output of the iterated game described in Eqn. (4.1) is the
trained Trojaned model $f_{\theta_{T}}^{*}$ and the trained detector
$h_{\theta_{D}}^{*}$. For efficient training, following the setup of [54], we
use $K$ shadow Trojaned DNNs
$f_{\theta_{T}^{1}},f_{\theta_{T}^{2}},\ldots,f_{\theta_{T}^{K}}$ and $K$
shadow clean DNNs
$f_{\theta_{C}^{1}},f_{\theta_{C}^{2}},\ldots,f_{\theta_{C}^{K}}$ in our
experiments in Sec. 6.

In this section, we first model co-evolution of interactions between an
adaptive adversary and adaptive detector as an iterative game. We then
demonstrate that the solution to this game results in the adaptive adversary
bypassing detection by adaptive output-based Trojaned model detectors. We
present the _Min-Max (MM) Trojan Algorithm_ that updates parameters of the
Trojaned model and detector to solve the game. Fig. 2 illustrates a conceptual
diagram of our proposed adaptive Trojaned model training procedure.

###  4.1 Iterated Game Design

Recollecting from Sec. 1, we rewrite Step 1 and Step 2 for the iterated game.
We rewrite these steps for clarity. Step 1: the adversary uses the trigger to
be embedded along with knowledge of the detector parameters to train an
enhanced Trojaned DNN model; Step 2: the adversary uses the enhanced Trojaned
DNN to compute offline new detector parameters that would maximize detection.
This alternating interaction described in Step 1 [Eqn. (2)] and Step 2 [Eqn.
(1)] can be expressed in a combined min-max form as shown below:

$\displaystyle\min_{\theta_{T}}\max_{\theta_{D}}$ $\displaystyle\hskip
2.84526pt\mathbb{E}_{z_{T}\sim
q_{T}}[\log(1-h_{\theta_{D}}(z_{T}))]+\mathbb{E}_{z_{C}\sim
q_{C}}[\log(h_{\theta_{D}}(z_{C}))]$
$\displaystyle+\mathbb{E}_{(x_{T},y_{T})\in\tilde{\mathscr{D}}}\ell_{\theta_{T}}(x_{T},y_{T})+\mathbb{E}_{(x,y)\in\mathscr{D}}\ell_{\theta_{T}}(x,y).$
(3)

When the adversary and defender interact in the manner described in Eqn.
(4.1), a question arises as to whether the detector will have an advantage or
will an adversary be able to eventually render SOTA output-based Trojaned
model detectors ineffective. We make the following observations that help in
answering this question.

A. In [57, 51, 34], it was shown that the large number of parameters in a
typical DNN model provides high degree of freedom in training. This degree of
freedom can be exploited by an adversary to achieve good performance on both
Trojaned and clean inputs in [57, 51, 34]. This motivates the further
exploitation of the degree of freedom to reduce the probability of being
detected by SOTA detectors.

B. The number of parameters in a Trojaned DNN model, such as a Convolutional
Neural Network (CNN) used for image classification, typically exceeds that in
a detector model. Hence, detectors with fewer tunable parameters compared to
Trojaned DNNs will not be able to keep up with evolution of adaptive attack
strategies due to lack of adequate degree of freedom to work with.

Observations A and B jointly indicate that the relatively higher degree of
freedom in Trojaned DNNs enables the adversary to adaptively evolve its
approach to evade detection, while the detector’s ability to adapt is
restricted by the limited number of tunable parameters. We use these
observations to formally show that solving the _iterated game_ in Eqn. (4.1)
results in the adversary successfully evading detection.

###  4.2 Algorithm and Analysis

This section presents our _Min-Max Trojan Algorithm_ to solve the min-max
optimization problem in Eqn. (4.1). We then show that the resulting solution
will yield identical output probability distributions from Trojaned and clean
models, thus making them indistinguishable to the detector.

Solving Eqn.(4.1) can be challenging, as optimization parameters $\theta_{T}$
(of the Trojaned model) and $\theta_{D}$ (of the detector) are inherently
coupled. To overcome this challenge, we propose MM Trojan Algorithm to solve
the game in Eqn.(4.1). In our MM Trojan Algorithm, the detector and adversary
iteratively update their parameters by selecting the best set of parameters
for their respective models in each iteration.

We now describe the working of the _Min-Max (MM) Trojan_ Algorithm (Algorithm
4.1) that describes the iterative procedure. A common way of selecting input
samples at random is to use a multivariate Gaussian distribution for selection
[54]. Following conventional notation, we denote a multivariate Gaussian with
mean $\mu$ and covariance $\Sigma$ by $\mathscr{N}:=\mathscr{N}(\mu,\Sigma)$.
This distribution is used to generate the set of input samples, denoted
$\mathscr{D}_{R}$, used by the detector classifier $h_{\theta_{D}}$ to detect
Trojaned models. The detector first provides a set of random inputs to both
clean and Trojaned model. Outputs from these models are used to train the
detector. _Lines 5-7_ describe the detector actions. The adversary then
updates parameters of the Trojaned model to maximize loss of the detector by
generating outputs that are similar to outputs of the clean model. _Lines 8-9_
describe the adversary’s actions.

Algorithm 4.1 Min-Max (MM) Trojan

1:Input: $\mathscr{D}$, $\mathscr{\tilde{D}}$, $f_{\theta_{T}}$,
$f_{\theta_{C}}$, $h_{\theta_{D}}$, learning rates
$0<\gamma_{D},\gamma_{T}<1$, $\mu$, $\Sigma$ and a large integer $Itr$.

2:Output: $\theta_{T}$.

3:Initialize $\theta_{T}$ and $\theta_{D}$

4:for $i=1:Itr$ do

5: $\mathscr{D}_{R}\leftarrow\\{x\leavevmode\nobreak\ |\leavevmode\nobreak\
x\sim\mathscr{N}(\mu,\Sigma)\\}$

6:
$L_{D}:=\underset{x\in\mathscr{D}_{R}}{\mathbb{E}}[\log(1-h_{\theta_{D}}(f_{\theta_{T}}(x)))+\log(h_{\theta_{D}}(f_{\theta_{C}}(x)))]$

7:
$\theta_{D}\leftarrow\theta_{D}+\gamma_{D}\frac{\partial}{\partial\theta_{D}}L_{D}$

8:
$L_{T}:=\underset{x\in\mathscr{D}_{R}}{\mathbb{E}}\log(1-h_{\theta_{D}}(f_{\theta_{T}}(x)))+\underset{(x_{T},y_{T})\in\mathscr{\tilde{D}}}{\mathbb{E}}\ell_{\theta_{T}}(x_{T},y_{T})+\underset{(x,y)\in\mathscr{{D}}}{\mathbb{E}}\ell_{\theta_{T}}(x,y)$

9:
$\theta_{T}\leftarrow\theta_{T}-\gamma_{T}\frac{\partial}{\partial\theta_{T}}L_{T}$

10:end for

11:return $\theta_{T}$

The final output parameters $\theta_{T}$ and $\theta_{D}$ from Algorithm 4.1
correspond to the optimal model parameters of the Trojaned DNN and detector
respectively. These parameters directly map to outputs of Trojaned DNNs,
$z_{T}:=f_{\theta_{T}}$, and outputs of clean DNNs, $z_{C}:=f_{\theta_{C}}$.
Proposition 4.1 below characterizes the solution of the min-max optimization
problem presented in Eqn. (4.1).

######  Proposition 4.1.

For a random input data sample $x\in\mathscr{D}_{R}$, let
$z_{T}:=f_{\theta_{T}}(x)$ and $z_{C}:=f_{\theta_{C}}(x)$ respectively denote
the outputs of a Trojaned model and a clean model. Let $q_{T}$ and $q_{C}$
denote probability distributions associated with $z_{T}$ and $z_{C}$. Then, at
the optimal solution of the game in Eqn. (4.1), the output distributions
coming from clean models and Trojaned models will be identical- i.e.,
$q_{T}=q_{C}$, thus allowing the adversary to successfully evade detection.

###### Proof.

The detailed proof is presented in the Appendix. ∎

Proposition 4.1 indicates that the output distributions of Trojaned ($q_{T}$)
and clean models ($q_{C}$) are identical at the optimal solution to the game.
Therefore, at the end, the adversary successfully evades detection, which can
be interpreted as winning the co-evolution game.

In Sec. 5, we present a greedy algorithm and show that when cross-entropy and/
or log-likelihood loss functions are used, the algorithm gives a lower bound
on the number of input samples to be selected for trigger-embedding.

##  5 Greedy Algorithm for Trojan Embedding

In this section, we discuss three components that affect selection of input
samples for embedding Trojan triggers, namely (a) attack cost, (b) model
integrity, and (c) stealth. We then present a greedy algorithm to select this
subset of clean samples for trigger-embedding.
Attack Cost: Embedding triggers into a large number of inputs significantly
increases the adversary’s operational costs. Minimizing these costs is
beneficial, as it ensures the most efficient use of adversary’s resources for
attack [49, 4, 38].
Model Integrity: A large number of trigger-embedded samples can degrade the
classification accuracy of the Trojaned ML model on clean input samples. Such
degradation may lead to more scrutiny and possible early detection of the
compromised model, potentially compromising the attack’s effectiveness [34,
33, 51].
Stealth: An excessive number of trigger-embedded samples makes a Trojaned DNN
easier to detect by advanced Trojan detection mechanisms [54, 50, 18, 21].
Careful selection of a few but adequate clean samples for trigger embedding is
necessary to evade detection, thereby maintaining attack stealth and
longevity.

Based on the above discussion, the adversary’s aim is to select the smallest
possible subset of training data for embedding Trojan triggers. This selection
is targeted at (i) achieving high accuracy in classifying data samples
embedded with Trojan triggers into the adversary’s desired class and (ii)
maintaining high classification accuracy on clean data samples. In this
context, the objective of evading detection by output-based Trojaned model
detectors is not explicitly included, as embedding a smaller number of
triggers inherently leads to increased stealthiness, as discussed at the
beginning of this section. The overarching strategy is to utilize the minimal
set of input samples chosen for trigger embedding in the MM Trojan algorithm
(Algorithm 4.1) to circumvent detection.

We use the following notation to describe the process of input sample
selection for trigger embedding. The set of clean samples is denoted by
$\mathscr{D}$ and the subset of clean samples into which a trigger is embedded
by $\tilde{\mathscr{D}}$. In order to evaluate the efficacy of the set of
trigger-embedded inputs in training a Trojaned DNN, the adversary will use a
test dataset, denoted $\mathscr{D}_{\text{Test}}$, where
$\mathscr{D}_{\text{Test}}$ contains samples that are not part of the training
dataset. Additionally, the adversary will use a test set, denoted
$\mathscr{\tilde{D}}_{\text{Test}}$, for embedding a Trojan trigger. We use
$\mathscr{L}_{T}(\mathscr{D},\mathscr{\tilde{D}})$ and
$\mathscr{L}_{C}(\mathscr{D},\mathscr{\tilde{D}})$ to represent loss functions
computed using $\mathscr{\tilde{D}}_{\text{Test}}$ and
$\mathscr{D}_{\text{Test}}$, and
$\mathscr{L}_{tot}(\mathscr{D},\mathscr{\tilde{D}}):=\mathscr{L}_{T}(\mathscr{D},\mathscr{\tilde{D}})+\mathscr{L}_{C}(\mathscr{D},\mathscr{\tilde{D}})$
to denote the (total) test loss. Then, determining the subset of input samples
into which to embed a Trojan trigger can be characterized as:

$\displaystyle\min_{\mathscr{\tilde{D}}\subset\mathscr{D}}\mathscr{L}_{tot}(\mathscr{D},\mathscr{\tilde{D}}).$
(4)

Determining the subset of clean samples for trigger-embedding,
$\mathscr{\tilde{D}}$ that solves Eqn. (4) is a combinatorial problem. As a
result, finding an optimal solution can become intractable as the size and
complexity of datasets and model parameters increase. To address this
challenge, our key insight is that the test-loss function in Eqn. (4)
satisfies a diminishing returns, or _supermodularity_ property in
$\tilde{\mathscr{D}}$ [16].

In this context, the supermodular property suggests that the reduction in test
loss achieved by the adversary when adding a new clean sample to a larger
subset $\mathscr{\tilde{D}}$ is less than the reduction achieved by adding the
same clean sample to a smaller subset $\mathscr{\tilde{D}}$. This property
indicates diminishing returns in terms of test loss reduction for each
additional sample added to $\mathscr{\tilde{D}}$. Consequently, beyond a
certain point, the adversary cannot significantly lower the total test loss
function, or in other words, cannot further improve the model’s performance in
terms of objectives (i) and (ii), by simply adding more samples to the set
$\mathscr{\tilde{D}}$. This property is crucial in determining the optimal
size and composition of $\mathscr{\tilde{D}}$ for the most computatioanlly
effective Trojan trigger embedding.

It has been demonstrated that test loss functions for input subset selection
exhibit supermodularity when the underlying loss function is the cross-entropy
function [26], which is frequently used in applications such as the image
classification tasks we consider in this paper. We formally establish the
supermodular property of $\mathscr{L}_{tot}(\mathscr{D},\mathscr{\tilde{D}})$
in Appendix A.2.

We present a _Greedy Algorithm_ in Algorithm 5.1 that enables the adversary to
constructively select samples for trigger embedding. The supermodularity of
the total test loss enables our Greedy Algorithm to offer a
$\mathbf{\frac{1}{2}}$-optimality guarantee on the selection of the optimal
set of input samples [9]. The output of the _Greedy Algorithm_ (Algo. 5.1)
serves as input to the MM Trojan Algorithm (Algo. 4.1). Integrating these
algorithms in a sequential manner thereby enhances effectiveness of the Trojan
embedding process.

Algorithm 5.1 Greedy Algorithm

Input: Training dataset available to adversary $\mathscr{D}$, ML model $f$,
and a real-valued constant $0\leq\epsilon<1$.

Output: $\mathscr{\tilde{D}}\subset\mathscr{D}$ to embed Trojan triggers.

1:Initialize $\mathscr{\tilde{D}}=\emptyset$ and flag = 1

2:while flag == 1 do

3:
$(x^{\star},y^{\star})\leftarrow\arg\max_{(x,y)\in\mathscr{D}}\mathscr{L}_{\text{tot}}(\mathscr{D},\mathscr{\tilde{D}}\cup\\{(x,y)\\})$

4: if
$\mathscr{L}_{\text{tot}}(\mathscr{D},\mathscr{\tilde{D}}\cup\\{(x^{\star},y^{\star})\\})<(1-\epsilon)\mathscr{L}_{\text{tot}}(\mathscr{D},\mathscr{\tilde{D}})$
then

5:
$\mathscr{\tilde{D}}\leftarrow\mathscr{\tilde{D}}\cup\\{(x^{\star},y^{\star})\\}$

6: $\mathscr{D}\leftarrow\mathscr{D}\setminus\\{(x^{\star},y^{\star})\\}$

7: else

8: flag = 0

9: end if

10:end while

11:return $\mathscr{\tilde{D}}$

######  Remark 5.1.

The optimization problem in Line 3 of Algorithm 5.1 requires training a model
for each data point $(x,y)\in\mathscr{D}$ added into $\mathscr{\tilde{D}}$
when determining identities of $(x^{\star},y^{\star})$. Therefore, in the
worst-case, at Line 3 there can be $O(|\mathscr{D}|)$ training instances. This
process can be computationally exhaustive and take a lot of time. One
heuristic to reduce computational complexity and run-time of Algorithm 5.1 is
to use batch-processing [25]. In such a scenario, the training data
$\mathscr{D}$ will first be randomly partitioned into $N<<|\mathscr{D}|$ non-
overlapping groups. Then, the optimization procedure in Line 3 will be solved
over these $N$ sets to identify which group needs to be added to the set
$\mathscr{\tilde{D}}$.

Algorithm 5.1 follows a procedure inspired from [39]. An alternative approach
to reduce computational complexity is to adopt a linear-time double greedy
algorithm, e.g., from [9]. Our analysis is consistent with observations made
in [8, 13] that insertion of a backdoor into the model is achieved at a cost
to the adversary, e.g., compromising model integrity and stealth. The
supermodularity of $\mathscr{L}_{\text{tot}}(\mathscr{D},\mathscr{\tilde{D}})$
is empirically verified through extensive experiments in Sec. 6.

##  6 Evaluation

This section introduces our experiment setup and details results of our
evaluations of the MM Trojan algorithm described in Sec. 4. The objective of
the adversary is to evade detection by an adaptive instance-based detection
mechanism, while simultaneously ensuring high accuracy of classifying clean
samples correctly and that of classifying Trojan samples to the target class.
We also carry out experiments to evaluate performance of the Greedy algorithm
described in Sec. 5.

###  6.1 Experiment Setup

####  6.1.1 Datasets

We use four datasets: MNIST, CIFAR-10, CIFAR-100, and SpeechCommand. We
briefly describe these datasets below:

MNIST: This dataset contains 70,000 $28\times 28$ gray-scale images of hand-
written digits; 60,000 are used for training and 10,000 for testing. The basic
model is a two-layer CNN, each with $5\times 5$ kernels and channel sizes 16
and 32, followed by maxpooling and fully-connected layers of size 512.

CIFAR-10: This dataset contains 60,000 $32\times 32$ RGB images of 10
different objects (e.g., car, horse). The basic model is a 4-layer convolution
neural network, each containing $3\times 3$ kernels and channel sizes of 32,
32, 64 and 64, followed by maxpooling and two fully-connected layers, each of
size 256.

CIFAR-100: This dataset is similar to CIFAR-10, except it has 100 classes
containing 600 images each.

SpeechCommand (SC): We use the 10-class SpeechCommand dataset version v0.02
[52], which contains 30,769 training and 4,074 testing files of a one-second
audio file on a specific command. The model first extracts the mel-spectrogram
of input audio with 40 mel-bands and then processes it with a Long-Short-Term-
Memory (LSTM) as in [54].

####  6.1.2 Trigger Setting

The Trojan trigger patterns are sampled in the same way as in [54]. In
particular, the trigger mask, pattern, transparency, poisoning ratio and
malicious label of shadow models will be sampled from the jumbo distribution.
For target models, we evaluate (i) modification attacks (M) and (ii) blending
attacks (B). The former attack will always set transparency to be zero while
the latter samples non-zero transparency values.

####  6.1.3 Metrics

We use five metrics to evaluate an adaptive adversary against four SOTA
output-based Trojaned model detectors: MNTD [54], NeuralCleanse [50], STRIP
[18], and TABOR [21]. Two metrics are used to evaluate performance of the
Trojan model on the original tasks ($Acc$ and $ASR$), and three metrics are
used to evaluate how effectively the Trojan model evades the detectors
($AUC_{0}$, $AUC_{t-1}$, $AUC_{t}$).

_Benign (Clean Sample) Accuracy ( $Acc$):_ is the fraction of clean samples
classified correctly by the model at test-time.

$\displaystyle Acc:=\frac{\\#\text{ of samples in }\mathscr{D}_{test}\text{
classified correctly}}{\\#\text{ of samples in }\mathscr{D}_{test}},$ (5)

where $\mathscr{D}_{test}$ is a test set containing only clean samples.

_Attack Success Rate ( $ASR$):_ is the fraction of trigger-embedded samples
classified by the model to the target class.

$\displaystyle ASR=\frac{\\#\text{ of samples in
}\mathscr{\tilde{D}}_{\text{Test}}\text{ classified to }y_{T}}{\\#\text{ of
samples in }\mathscr{\tilde{D}}_{\text{Test}}},$ (6)

where $\mathscr{\tilde{D}}_{\text{Test}}$ is got by inserting a trigger into
samples in $\mathscr{D}_{test}$.

The above quantity is sometimes termed an _attack success rate (ASR)_ in the
machine learning literature [17]. However, we use the notation $ASR$ to avoid
ambiguity with the objective of the adversary to evade detection.

Table 1:  Comparison between MM Trojan and baseline Trojan against the state-of-the-art MNTD detection for $t=20$ iterations for four datasets- MNIST, CIFAR-10, CIFAR-100, SpeechCommand. M represents the modification attack and B represents the blending attack. The $AUC_{t}$ represents the detection performance at step $t$ (smaller value indicates that the attack better evades the detection). The baseline Trojan does not have values on $AUC_{t-1}$ because it does not include an iterative process. We can observe that the MM Trojan can successfully evade the detection when the adaptive adversary takes the last step ($AUC_{0}$ and $AUC_{t-1}$); even when the defender takes the last step, we can still see a significant drop in the detection performance ($AUC_{t}$).  Dataset | Trojan | Attack | $Acc$ | $ASR$ |  $AUC_{0}$ ($\downarrow$) |  $AUC_{t-1}$ ($\downarrow$) |  $AUC_{t}$ ($\downarrow$)
---|---|---|---|---|---|---|---
MNIST | M | Baseline Trojan | 0.9835 | 0.9982 | 0.9980 | - | 0.9980
MM Trojan | 0.9825 | 0.9969 | 0.0 | 0.0 | 0.6230
B | Baseline Trojan | 0.9813 | 0.9928 | 1.0 | - | 1.0
MM Trojan | 0.9813 | 0.9957 | 0.0 | 0.0 | 0.8310
CIFAR-10 | M | Baseline Trojan | 0.6127 | 0.9998 | 0.9775 | - | 0.9775
MM Trojan | 0.6005 | 0.9998 | 0.0 | 0.0 | 0.8828
B | Baseline Trojan | 0.5929 | 0.9600 | 0.9658 | - | 0.9658
MM Trojan | 0.5897 | 0.8864 | 0.0 | 0.0 | 0.8779
CIFAR-100 | M | Baseline Trojan | 0.4827 | 0.9988 | 0.9863 | - | 0.9863
MM Trojan | 0.4468 | 0.9409 | 0.1563 | 0.0 | 0.7813
B | Baseline Trojan | 0.4839 | 0.9992 | 0.9375 | - | 0.9375
MM Trojan | 0.4312 | 0.9108 | 0.0 | 0.0 | 0.8662
SpeechCommand | M | Baseline Trojan | 0.8330 | 0.9827 | 0.9941 | - | 0.9941
MM Trojan | 0.7481 | 0.9520 | 0.1904 | 0.0361 | 0.2765
B | Baseline Trojan | 0.8313 | 0.9911 | 0.9990 | - | 0.9990
MM Trojan | 0.7411 | 0.9703 | 0.0215 | 0.0 | 0.7529

_Detection rates ( $AUC_{0},AUC_{t-1},AUC_{t}$):_ The Area Under the Curve
(AUC) in the context of a Receiver Operating Characteristic (ROC) curve is a
measure of the ability of a classifier to distinguish between classes. The ROC
curve is a graphical representation of true positive rate (TPR) against false
positive rate (FPR) at various threshold settings. An AUC of 1.0 represents a
perfect detector An AUC of 0.5 represents a detector that performs no better
than random chance.

Given the benign models $\\{f_{\theta_{T}^{i}}\\}_{i=1}^{K}$ and Trojan models
$\\{f_{\theta_{T}^{i}}\\}_{i=1}^{K}$ generated in the $i$-th iteration, we
will evaluate the detection AUC of different detector models on this binary
classification/ outlier detection task. In particular, we will evaluate the
AUC of (1) the vanilla detector model, denoted $AUC_{0}$; (2) the detectot
model trained in the $(t-1)$-th iteration, denoted $AUC_{t-1}$; (3) the
detector model trained in the $t$-th iteration, denoted $AUC_{t}$. We use
$t=20$ in all our experiments.

The quantity $AUC_{t-1}$ indicates attack performance when the adversary takes
the last step, while $AUC_{t}$ indicates attack performance when the defender
takes the last step. A smaller $AUC$ value indicates better attack
performance. For the Baseline Trojan without multiple iterations,
$AUC_{t}=AUC_{0}$ and there is no value for $AUC_{t-1}$.

####  6.1.4 Trojan detection mechanisms

Trojan detection mechanisms aim to identify if outputs corresponding to a set
of random inputs are coming from a clean or Trojan model. The Trojan model
detector in this paper is a binary classifier learned using multiple outputs
from clean and Trojan models. For the purpose of experiments, SOTA Trojan
detection schemes we evaluate can be broadly categorized into two classes,
described below.

The first class of detectors iteratively trains a set of clean models with
same structure as target model and a set of Trojan models for different
triggers and desired outputs. The Trojan detector then learns a discriminator
on the output of these models for random image inputs. Such discriminator was
shown to be able to achieve high accuracy in detecting Trojan models. MNTD
[54] is the SOTA Trojan detector of this type.

The second class of detectors use a ‘single-step’ approach to determine
whether a given model is Trojan or not. We evaluate three SOTA Trojan
detectors of this type: NeuralCleanse [50], STRIP [18], and TABOR [21].
NeuralCleanse [50] seeks to compute the minimum magnitude of perturbation
required to change the output prediction of a model into each class. The given
model is recognized as Trojan if the minimum magnitude of perturbation for
some class is lower than a threshold value. STRIP [18] aims to evaluate
whether the confidence of the model on certain inputs will be maintained when
these inputs will be made noisy by mixing with other inputs. If prediction of
the model remain unchanged, then STRIP observes that it is likely that the
input sample has been embedded with a Trojan trigger. Consequently, STRIP
concludes that the model is Trojan. TABOR [21] is an extension of
NeuralCleanse [31] and uses optimization regularization inspired by
explainable AI techniques and heuristics. TABOR then uses a quality measure to
identify candidate triggers, followed by an anomaly detection procedure to
reduce false alarms.

Table 2:  Comparison between MM Trojan and baseline Trojan attacks against four SOTA Trojan detection mechanisms (MNTD [54], NeuralCleanse [50], STRIP [18], and TABOR [21]). M represents modification attack and B represents blending attack. We use all-to-all attack in MM Trojan, as the adversary takes the last step to bypass the different detection approaches. We observe that in most settings, the MM Trojan successfully evades all four detection methods, while the baseline Trojan will fail.  Dataset | Trojan | Attack |  MNTD-AUC ($\downarrow$) |  NC-AUC ($\downarrow$) |  STRIP-AUC ($\downarrow$) |  TABOR-AUC ($\downarrow$)
---|---|---|---|---|---|---
MNIST | M | Baseline Trojan | 0.9980 | 0.8750 | 0.8379 | 0.8305
MM Trojan | 0.0 | 0.5586 | 0.3674 | 0.5703
B | Baseline Trojan | 1.0 | 0.8359 | 0.6406 | 0.7188
MM Trojan | 0.0 | 0.5469 | 0.4205 | 0.5508
CIFAR-10 | M | Baseline Trojan | 0.9775 | 0.5859 | 0.8332 | 0.7344
MM Trojan | 0.0 | 0.5016 | 0.5828 | 0.5562
B | Baseline Trojan | 0.9658 | 0.6289 | 0.7141 | 0.6719
MM Trojan | 0.0 | 0.5172 | 0.4225 | 0.6344
CIFAR-100 | M | Baseline Trojan | 0.9863 | 0.5754 | 0.7422 | 0.6783
MM Trojan | 0.0625 | 0.5188 | 0.4055 | 0.5413
B | Baseline Trojan | 0.9375 | 0.5713 | 0.7031 | 0.7154
MM Trojan | 0.0 | 0.5031 | 0.5920 | 0.5235
SpCom | M | Baseline Trojan | 0.9941 | 0.7070 | 0.7514 | 0.7273
MM Trojan | 0.0156 | 0.6055 | 0.2187 | 0.6600
B | Baseline Trojan | 0.9990 | 0.9297 | 0.9188 | 0.9143
MM Trojan | 0.0 | 0.6680 | 0.3748 | 0.6667

###  6.2 MM Trojan vs Iterative Detectors

Table 1 shows the attack performance of _MM Trojan_ and a comparison with the
baseline Trojan on the MNIST, CIFAR-10, CIFAR-100, and SpeechCommand datasets.
We observe that MM Trojan successfully evades adaptive Trojan detection
models. We use MNTD as an instance of iterative Trojan detection mechanism
[54]. We report results for both, modification (M) and blending (B) attacks.
The model trained with MM Trojan can evade the initial MNTD detector into a
zero detection AUC on vision-based tasks, and close-to-zero performance on the
SpeechCommand task (values of $AUC_{0}$ in Table 1). For an adaptive
adversary, using MM Trojan results in a zero or close-to-zero detection AUC at
step $t-1$ (values of $AUC_{t-1}$ in Table 1). Moreover, when the defender
takes the last step, we can still see a significant drop in detection AUC
($AUC_{t}$ values in Table 1). This reveals that even when the defender has
full knowledge of our attack, the defending performance is still significantly
affected by the attack.

We also observe a trade-off in that our MM Trojan will, in some cases, have
lower benign and backdoor accuracies, especially on relatively complicated
tasks such (e.g., SpeechCommand). We believe that tuning parameters
$\theta_{D}$ and $\theta_{T}$ will control the trade-off. Developing
strategies to mitigate drop in accuracy is an interesting direction of future
research.

###  6.3 MM Trojan vs Other Detectors

We additionally evaluate the effectiveness of an MM Trojan model in evading
other Trojan detection approaches. Since MM Trojan does not change the
training dataset but only the model training algorithm, it only affects model-
based Trojan detection algorithms. Therefore, we perform experiments on three
model-based detection algorithms: NeuralCleanse [50], STRIP [18], and TABOR
[21]. In order to evade these detection methods, we will change the attack
goal of the Trojan to be the “ _all-to-all_ ” attack, i.e., the prediction
will be changed from the $i$-th class to the $((i+1)\%K)$-th class, where $K$
is the total number of classes. Our approach is guided by an insight observed
in [54] which has indicated that model-based detection algorithms are not
designed to detect all-to-all attacks. Since MM Trojans are designed for an
adaptive adversary that uses gradient-based algorithms, we believe that it
will also be effective against NeuralCleanse or STRIP. We seek to show that MM
Trojan can be flexibly combined with other techniques, so that it can also
bypass other detection models. Table 2 shows results of the MM _all-to-all_
Trojan. We observe that with the all-to-all attack goal integrated into MM
Trojan, we can indeed achieve good performance in evading multiple detectors.
The AUC values of NeuralCleanse, STRIP, and TABOR drop to under or close to
$0.5$ (equivalent to a random guess) in all cases. In comparison, the AUC
value of MNTD is close to zero because of the adversarial attack in the MM
Trojan process. We acknowledge that as our approach does not involve gradient-
based attacks against NeuralCleanse, STRIP, or TABOR, we anticipate that these
models will maintain a performance above close-to-zero detection rates.

The results in this section on three SOTA Trojan detectors indicate that
success of an adversary following MM Trojan is largely agnostic to the
detection mechanism. This suggests that MM Trojan can be effective against
future Trojan detection mechanisms that adaptively update their parameters
when working against an adaptive adversary.

(a) MNIST Trojan-M

(b) CIFAR-10 Trojan-M

(c) CIFAR-100 Trojan-M

(d) SpeechCommand Trojan-M

(e) MNIST Trojan-B

(f) CIFAR-10 Trojan-B

(g) CIFAR-100 Trojan-B

(h) SpeechCommand Trojan-B

Figure 3:  Adversary test-loss as a function of the fraction of data samples
into which a Trojan trigger has been embedded on MNIST, CIFAR-10, CIFAR-100,
and SpeechCommand datasets under modification (M) and blending attacks (B). We
denote the fraction of samples into which the adversary embeds a Trojan
trigger by $\alpha:=|\tilde{\mathscr{D}}|/|\mathscr{D}|$. Blue curves show the
loss term over clean samples,
$\mathscr{L}_{C}(\mathscr{D},\mathscr{\tilde{D}})$, and red curves show the
loss term over samples that have been embedded with the Trojan,
$\mathscr{L}_{T}(\mathscr{D},\mathscr{\tilde{D}})$. The black curves present
the total loss $\mathscr{L}_{tot}(\mathscr{D},\mathscr{\tilde{D}})$ as defined
in Eqn. (4). We observe that for both attacks, the decrease in the total loss
value, $\mathscr{L}_{tot}(\mathscr{D},\mathscr{\tilde{D}})$, is insignificant
after exceeding a threshold value of $\alpha$. This indicates that the
adversary does not derive an additional (marginal) benefit by increasing the
fraction of Trojan trigger-embedded samples beyond a threshold value of
$\alpha$.

###  6.4 Verification of Greedy Trojan

(a) MNIST Trojan-M

(b) CIFAR-10 Trojan-M

(c) CIFAR-100 Trojan-M

(d) SpeechCommand Trojan-M

(e) MNIST Trojan-B

(f) CIFAR-10 Trojan-B

(g) CIFAR-100 Trojan-B

(h) SpeechCommand Trojan-B

Figure 4: Classification accuracies over clean samples ($Acc$, blue) and samples into which the adversary embeds a Trojan trigger ($ASR$, red) using the MM Trojan algorithm on MNIST, CIFAR-10, CIFAR-100, and SpeechCommand datasets under modification (M) and blending (B) attacks. The increase in $ASR$ becomes less significant beyond a threshold value of the poisoning ratio, $\alpha:=|\tilde{\mathscr{D}}|/|\mathscr{D}|$. On the other hand, the value of $Acc$ may decrease as $\alpha$ increases. This could result in a user discarding the model.  Table 3:  Ablation study of MM Trojan with different poisoning ratio ($\alpha$) against the state-of-the-art MNTD detection. M represents the modification attack and B represents the blending attack. We can observe that under all the settings, a minimum threshold of $\alpha=0.05$ can achieve a good Trojan attack performance ($Acc$ and $ASR$) while also evading MNTD detection.  Dataset | Trojan | Metric | $\alpha=0.05$ | $\alpha=0.1$ | $\alpha=0.25$ | $\alpha=0.5$
---|---|---|---|---|---|---
MNIST | M | $Acc$ | 0.9828 | 0.9821 | 0.9819 | 0.9812
$ASR$ | 0.9746 | 0.9951 | 0.9977 | 0.9995
|  AUC ($\downarrow$) | 0.0 | 0.0 | 0.0 | 0.0
B | $Acc$ | 0.9826 | 0.9819 | 0.9813 | 0.9798
| $ASR$ | 0.9580 | 0.9943 | 0.9970 | 0.9975
|  |  AUC ($\downarrow$) | 0.0 | 0.0 | 0.0 | 0.0
CIFAR-10 | M | $Acc$ | 0.6015 | 0.5888 | 0.5870 | 0.5818
$ASR$ | 0.9987 | 0.9998 | 0.9999 | 1.0
|  AUC ($\downarrow$) | 0.0 | 0.0 | 0.0 | 0.0
B | $Acc$ | 0.6150 | 0.5948 | 0.5905 | 0.5875
| $ASR$ | 0.6186 | 0.8700 | 0.9368 | 0.9994
|  |  AUC ($\downarrow$) | 0.0 | 0.0 | 0.0 | 0.0
CIFAR-100 | M | $Acc$ | 0.4887 | 0.4881 | 0.4867 | 0.4838
$ASR$ | 0.9931 | 0.9987 | 0.9998 | 1.0
|  AUC ($\downarrow$) | 0.0089 | 0.0356 | 0.0581 | 0.0982
B | $Acc$ | 0.4892 | 0.0.4871 | 0.4838 | 0.4798
| $ASR$ | 0.8065 | 0.9978 | 0.9993 | 1.0
|  |  AUC ($\downarrow$) | 0 | 0 | 0.0001 | 0.0024
SpeechCommand | M | $Acc$ | 0.7638 | 0.7479 | 0.7069 | 0.6982
$ASR$ | 0.7839 | 0.9270 | 0.9443 | 0.9951
|  AUC ($\downarrow$) | 0.0127 | 0.0264 | 0.0286 | 0.0345
B | $Acc$ | 0.7596 | 0.7591 | 0.7256 | 0.7091
| $ASR$ | 0.9382 | 0.9427 | 0.9554 | 0.9585
|  |  AUC ($\downarrow$) | 0.0022 | 0.0028 | 0.0415 | 0.0600

Fig. 3 and 4 present experimental evaluations of the Greedy Trojan Algorithm
on the MNIST, CIFAR-10, CIFAR-100, and SpeechCommand datasets for two
different types of attacks- a modification attack (M) and a blending attack
(B). We define the poisoning ratio $\alpha$ to be the fraction of samples into
which the adversary embeds a Trojan trigger, i.e.,
$\alpha:=|\tilde{\mathscr{D}}|/|\mathscr{D}|$. In all experiments, we
initialize $\alpha=0.002$. In each iteration, we train a model to minimize the
loss function in Eqn. (4). This loss function consists of two terms- one over
clean samples and another over Trojan samples. We increase the size of the set
of samples, $\tilde{\mathscr{D}}$, into which a Trojan trigger is embedded by
the adversary as long as the addition of such samples decreases the value of
the loss function (Line 4 of Algo 5.1). The procedure terminates when adding
more samples to $\tilde{\mathscr{D}}$ does not result in a significant
decrease in the loss function.

Fig. 3 shows the change in loss values as the value of $\alpha$ increases. In
each case, we observe that the loss term corresponding to Trojan samples
($\mathscr{L}_{T}(\mathscr{D},\mathscr{\tilde{D}})$, red curve) initially
decreases as $\alpha$ increases. However, after exceeding a threshold, the
decrease in the total loss value
($\mathscr{L}_{tot}(\mathscr{D},\mathscr{\tilde{D}})$, black curve) is
insignificant. The loss term corresponding to clean samples
($\mathscr{L}_{C}(\mathscr{D},\mathscr{\tilde{D}})$, blue curve) might
increase as fraction of clean samples decreases with increase in $\alpha$.
This demonstrates that the adversary has little advantage in poisoning a
fraction of samples larger than a threshold value.

Fig. 4 shows classification accuracies for clean samples ($Acc$, blue curve)
and Trojan samples ($ASR$, red curve) as $\alpha$ is increased. For small
values of $\alpha$, $ASR$ is small, but this metric improves as $\alpha$ is
increased. The improvement becomes less significant after a threshold of
$\alpha$ is reached. Simultaneously, the value of $Acc$ decreases slightly,
which indicates that the model might become less useful to a user, leading
them to discard it. Thus poisoning a large fraction of samples will not be
advantageous to the adversary.

The outcomes of our experiments is consistent with the analysis presented in
Section 5 in that the test-loss function of the adversary exhibits diminishing
returns as the number of samples chosen by the adversary to be embedded with
the Trojan trigger increases. Further, these results show that the fraction of
samples into which the adversary needs to embed a Trojan trigger can be
determined in a constructive manner. We observe that the adversary needs to
embed a Trojan into only about $4\%$ of samples under the modification attack
and about $6\%$ of samples under the blending attack. Increasing the poisoning
ratio beyond these thresholds will not significantly reduce the value of the
total loss, $\mathscr{L}_{tot}(\mathscr{D},\mathscr{\tilde{D}})$, in Eqn. (4).

###  6.5 Ablation Studies

We conduct ablations to evaluate the effect of poisoning ratio $\alpha$ on
performance of the MM Trojan algorithm using MNIST, CIFAR-10, CIFAR-100, and
SpeechCommand datasets. For an adversary carrying out two different types of
attacks to embed a Trojan trigger- modification (M) and blending attack (B)-
we consider four values: $\alpha=\\{0.05,0.1,0.25,0.5\\}$, and examine benign
accuracy $(Acc)$, backdoor accuracy $(ASR)$, and detection rate of MNTD
($AUC$).

Table 3 shows that for both types of attacks, as the poisoning ratio $\alpha$
is increased, the value of $Acc$ decreases while the value of $ASR$ increases.
For the MNIST and CIFAR-10 datasets, the $AUC$ values of MNTD are zero,
indicating that the adversary successfully evades detection even when the
fraction of poisoned samples is high. We also observe that the adversary needs
to maintain a poisoning ratio of at least $0.1$ in order to achieve high
backdoor accuracy values for these two datasets. On the other hand, for the
SpeechCommand dataset, there is a tradeoff between achieving high backdoor
accuracy $ASR$ and low $AUC$ values, indicating that the poisoning ratio has a
greater impact. However, for all four datasets, we observe that there is a
threshold value of $\alpha$, beyond which there is a only a marginal change in
the values of $Acc$ and $ASR$.

The results in Table 3 further underscore our insight that a minimum threshold
for $\alpha$ can achieve acceptable values of $Acc$ and $ASR$ using the Greedy
Algorithm (Algo. 5.1) and also aids the adversary in effectively evading
detection using the MM Trojan algorithm (Algo. 4.1).

##  7 Discussion

In this section, we provide insights that underscore our results and briefly
describe open questions that are promising directions for future research.

Performance of MM Trojan: Our MM Trojan algorithm (Algorithm 4.1) jointly
optimizes parameters associated with the Trojan model ($\theta_{T}$) and
detection mechanism ($\theta_{D}$) in order for an adaptive adversary to
simultaneously evade detection and achieve high classification accuracy. The
adaptive defender aims to maximize the probability of detecting Trojan models
based on their outputs. We model this interaction as an iterated game and in
Proposition 4.1 we show solving this game results in the adversary
successfully evading detection. Specifically, the solution
$\theta_{T}^{\star}$ and $\theta_{D}^{\star}$ to the game forms a Nash
equilibrium under which neither adversary nor defender can do better by
unilaterally deviating from their respective solutions. Therefore, as long as
the adversary uses the value of $\theta_{T}^{\star}$ output by the MM Trojan
algorithm, any other defender (including a ‘static’ defender) will not be able
to deviate from $\theta_{D}^{\star}$ and achieve better performance.

Training overhead: The number of hours of training required to generate shadow
models and train meta models for $t=20$ iterations are: $MNIST:67.2$;
$CIFAR:78.1$; $SpeechCommand:46.4$. Batch processing is one way to reduce the
training overhead, as noted in Remark 5.1.

Information exclusively controlled by adversary: Fig. 2 indicates that in
order to train Trojaned models, the adversary uses (i) data samples embedded
with different types of Trojan triggers and (ii) feedback from the output of
the detector. On the other hand, training the detector requires outputs of
Trojaned models and outputs from clean models. Thus, the adversary has control
over a subset of information (corresponding to outputs of the Trojaned models)
required to train the detector. Further, to avoid imbalanced data, an equal
number of outputs of data samples from clean models and of samples from
Trojaned models are used to train the detector. The detector on the other
hand, makes use of output data from clean and Trojaned DNNs, and does not
generate any additional data of it own.

These observations are consistent with our experimental results in Sec. 6.2
and 6.3 which show that an adaptive adversary following the MM Trojan
Algorithm is able to successfully evade detection by multiple different SOTA
Trojan detectors.

##  8 Related Work

We place our contributions in this paper in the context of related work in
backdoor attacks on ML models, detecting Trojan models, and mitigating the
impact of backdoors.

Trojan Attacks. The authors of [24] showed that untrustworthy entities might
maintain pre-trained ML models, consequently resulting in severe security
implications to model users. They introduced a class of _model-reuse_ attacks,
wherein a host system running this model could be induced to predictably
misbehave on specific inputs. A notion of _latent backdoors_ was introduced in
[55], which are backdoors that are preserved during transfer learning. As a
result, if a model obtained after transfer learning includes the target label
of the backdoor, it can be activated by an appropriate input. This work also
showed that defending against latent backdoors involved a tradeoff between
cost and accuracy.

Model or data poisoning by an adversary has also been shown to be an effective
attack strategy. An algorithm in [42] efficiently identified vulnerable bits
of model weights stored in memory. Flipping these bits transformed a deployed
DNN model into a Trojan model. Concurrently, targeted weight perturbations
were used to embed backdoors into convolutional neural networks deployed for
face recognition in [14]. In contrast to model poisoning methods described
above, the training set of an ML model was poisoned in [44]. In this case, the
adversary had the ability to control the outcome of classification for the
poisoned data, while the model’s performance was maintained for ‘clean’
samples.

In [43], the authors propose a backdoor trigger-embedding approach where an
intended trigger is first partitioned into smaller triggers. Each smaller
trigger is embedded into a unique input sample such that the union of the
trigger-embedded data covers the intended trigger. The results in [43] also
show that the resulting Trojaned DNN leads to effective mixing of trigger-
embedded and clean input samples in the classification space making it
difficult for any SOTA distance-based detection mechanisms. In [43], it was
noted that at least 30% trigger-embedded data is required to ensure high
accuracy on both clean and trigger-embedded input samples.

Detecting Trigger-Embedded Inputs. An intuitive defense against data poisoning
attacks is to develop techniques to remove suspicious samples from the
training data. Backdoor attacks were shown to leave a distinct _spectral
signature_ in covariance of feature representations learned by DNNs in [48].
The spectral signature, in addition to detecting corrupted training examples,
also presents a barrier to crafting and design of backdoors to ML models.
Gradients of loss function at the input layer of a DNN were used to extract
signatures to identify and eliminate poisoned data in [10] even when the
target class and ratio of poisoned samples were unknown. Recent work in [37]
and [20] employ corruption robustness consistency and prediction consistency-
based measures to detect trigger-embedded input samples during inference.
Latent separation based methods for detecting Trojan-trigger embedded input
samples, aiming to learn separable latent representations for Trojaned and
clean inputs were proposed in [47, 22]. However these approaches which focus
on input-based or latent separability (i.e., model inspection)-based detection
of Trojan trigger-embedded input samples, are not within the scope of our
adaptive adversary model. Our objective is to evade output-based Trojaned
model detectors, which aim to identify whether a given model is Trojaned
without requiring trigger-embedded Trojan input samples for detection.

Detecting Trojaned Models. When the ML model has an embedded Trojan, it is
natural to design methods to detect such models by identifying potential
triggers. A method to detect and reverse-engineer triggers in DNNs called
_NeuralCleanse_ was proposed in [50]. _NeuralCleanse_ devised an optimization
scheme to determine the smallest trigger required to misclassify all samples
from all labels to the target label. However, the target label may not be
known, and the requirement to consider all labels as a potential target label
makes this computationally expensive. An improvement on _NeuralCleanse_ called
_TABOR_ [21] used a combination of heuristics and regularization techniques to
reduce false positives in Trojan detection. Differences in explanations of
outputs of a clean model and a Trojan model, even on clean samples, were used
to identify Trojan models in [23]. This was achieved without requiring access
to samples containing a trigger.

A Trojan detection method called _DeepInspect_ [11] used conditional
generative models to learn distributions of potential triggers while having
only black-box access to the deployed ML model and without requiring access to
clean training data. To overcome a limitation of [11] (and of [50]) that there
is exactly one target label, the authors of [54] proposed Meta-Neural Trojan
Detection (MNTD). MNTD only required black-box access to models and trained a
meta-classifier to identify if the model was Trojan or not. Multiple shadow
models (combination of clean and Trojan models) were generated and their
representations were used to learn a binary classifier. At test-time, the
representation of the target model was provided to the classifier to determine
whether it was Trojan or not. MNTD was demonstrated to have a high success
rate when evaluated on a diverse range of datasets, including images, speech,
and NLP.

Mitigating Backdoors. Once an embedded Trojan has been detected, a question
arises if methodologies can be developed to remove or reduce the impact of a
backdoor, while maintaining model performance on clean inputs. The _Fine-
pruning_ method in [36] proposes to deactivate neurons that are not enabled by
clean inputs. It then uses a tuning procedure to restore some of the
deactivated neurons to mitigate reduction in classification accuracy due to
pruning. A run-time Trojan attack detection system called STRIP was developed
in [18]. The _input-agnostic_ property of a trigger was exploited as a
weakness of Trojan attacks. This method was independent of model architecture
and size of trigger. A survey of backdoor attacks and defenses against such
attacks can be found in [17].

##  9 Conclusion

In this paper, we investigated the detection performance of SOTA output-based
Trojaned model detectors against an adaptive adversary who has the knowledge
of the deployment of such detectors and evolves its strategies to bypass
detection.

Such an adaptive adversary incorporates detector parameter information to
retrain the Trojaned DNN to (1) achieve high accuracy on both Trojan trigger-
embedded and clean input samples and (2) bypass detection. By allowing
detectors to also be adaptive, we showed that co-evolution of adversary and
detector parameters could be modeled by an iterative game. We proved that the
solution of this game resulted in the adversary accomplishing objectives (1)
and (2). We also used a greedy algorithm to allow the adversary to select
input samples to embed a Trojan trigger. When cross-entropy or log-likelihood
loss functions were used for training, the greedy algorithm resulted in a
provable lower bound on the number of samples to be selected for trigger-
embedding.

Extensive evaluations on MNIST, CIFAR-10, CIFAR-100, and SpeechCommand showed
that the adaptive adversary effectively evaded four leading SOTA output-based
Trojaned model detectors: MNTD [54], NeuralCleanse [50], STRIP [18], and TABOR
[21].

Our results highlight the need for new, advanced output-based Trojaned model
detectors against adaptive adversaries.

## Acknowledgments

This material is based upon work supported by the National Science Foundation
under grant IIS 2229876 and is supported in part by funds provided by the
National Science Foundation (NSF), by the Department of Homeland Security, and
by IBM. Any opinions, findings, and conclusions or recommendations expressed
in this material are those of the author(s) and do not necessarily reflect the
views of the National Science Foundation or its federal agency and industry
partners. This work is also supported by the Air Force Office of Scientific
Research (AFOSR) through grant FA9550-23-1- 0208, the Office of Naval Research
(ONR) through grant N00014-23- 1-2386, and the NSF through grant CNS 2153136.

## References

  * [1] Amazon, Machine learning at AWS, 2018.
  * [2] BigML Inc. BigML, 2018
  * [3] Caffe, Caffe Model Zoo, 2018.
  * [4] Bai, Y., Xu, J., Yao, Y., Zhu, Q., Li, X., Zhao, Z.: Data poisoning attack on deep learning models with least trigger points. In: ACM SIGSAC Conference on Computer and Communications Security. pp. 2954–2971 (2021)
  * [5] Bender, E.M., Gebru, T., McMillan-Major, A., Shmitchell, S.: On the dangers of stochastic parrots: Can language models be too big? In: ACM Conference on Fairness, Accountability, and Transparency. pp. 610–623 (2021)
  * [6] Bishop, C.: Pattern recognition and machine learning. Springer 2, 531–537 (2006)
  * [7] Bojarski, M., Del Testa, D., Dworakowski, D., Firner, B., Flepp, B., Goyal, P., Jackel, L.D., Monfort, M., Muller, U., Zhang, J., Zhang, X., Zhao, J., Zieba, K.: End to end learning for self-driving cars. arXiv preprint arXiv:1604.07316 (2016)
  * [8] Brahma, S., Njilla, L., Nan, S.: Game theoretic hardware Trojan testing under cost considerations. In: Conference on Decision and Game Theory for Security. pp. 251–270. Springer (2021)
  * [9] Buchbinder, N., Feldman, M., Seffi, J., Schwartz, R.: A tight linear time (1/2)-approximation for unconstrained submodular maximization. SIAM Journal on Computing 44(5), 1384–1402 (2015)
  * [10] Chan, A., Ong, Y.S.: Poison as a cure: Detecting & neutralizing variable-sized backdoor attacks in deep neural networks. arXiv preprint arXiv:1911.08040 (2019)
  * [11] Chen, H., Fu, C., Zhao, J., Koushanfar, F.: Deepinspect: A black-box Trojan detection and mitigation framework for deep neural networks. In: IJCAI. vol. 2, p. 8 (2019)
  * [12] Cover, T.M.: Elements of Information Theory. John Wiley & Sons (1999)
  * [13] Das, T., Eldosouky, A.R., Sengupta, S.: Think smart, play dumb: Analyzing deception in hardware Trojan detection using game theory. In: International Conference on Cyber Security and Protection of Digital Services. pp. 1–8. IEEE (2020)
  * [14] Dumford, J., Scheirer, W.: Backdooring convolutional neural networks via targeted weight perturbations. In: International Joint Conference on Biometrics. pp. 1–9. IEEE (2020)
  * [15] Esteva, A., Robicquet, A., Ramsundar, B., Kuleshov, V., DePristo, M., Chou, K., Cui, C., Corrado, G., Thrun, S., Dean, J.: A guide to deep learning in healthcare. Nature Medicine 25(1), 24–29 (2019)
  * [16] Fujishige, S.: Submodular functions and optimization. Elsevier (2005)
  * [17] Gao, Y., Doan, B.G., Zhang, Z., Ma, S., Zhang, J., Fu, A., Nepal, S., Kim, H.: Backdoor attacks and countermeasures on deep learning: A comprehensive review. arXiv preprint arXiv:2007.10760 (2020)
  * [18] Gao, Y., Xu, C., Wang, D., Chen, S., Ranasinghe, D.C., Nepal, S.: Strip: A defence against trojan attacks on deep neural networks. In: Proc. Annual Computer Security Applications Conference. pp. 113–125 (2019)
  * [19] Gu, T., Liu, K., Dolan-Gavitt, B., Garg, S.: BadNets: Evaluating backdooring attacks on deep neural networks. IEEE Access 7, 47230–47244 (2019)
  * [20] Guo, J., Li, Y., Chen, X., Guo, H., Sun, L., Liu, C.: Scale-up: An efficient black-box input-level backdoor detection via analyzing scaled prediction consistency. arXiv preprint arXiv:2302.03251 (2023)
  * [21] Guo, W., Wang, L., Xing, X., Du, M., Song, D.: TABOR: A highly accurate approach to inspecting and restoring Trojan backdoors in AI systems. arXiv preprint arXiv:1908.01763 (2019)
  * [22] Hayase, J., Kong, W., Somani, R., Oh, S.: SPECTRE: defending against backdoor attacks using robust statistics. In: 38th International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 139, pp. 4129–4139. PMLR (18–24 Jul 2021)
  * [23] Huang, X., Alzantot, M., Srivastava, M.: NeuronInspect: Detecting backdoors in neural networks via output explanations. arXiv preprint arXiv:1911.07399 (2019)
  * [24] Ji, Y., Zhang, X., Ji, S., Luo, X., Wang, T.: Model-reuse attacks on deep learning systems. In: Proceedings ACM Conference on Computer and Communications Security. pp. 349–363 (2018)
  * [25] Keskar, N.S., Mudigere, D., Nocedal, J., Smelyanskiy, M., Tang, P.T.P.: On large-batch training for deep learning: Generalization gap and sharp minima. International Conference on Learning Representations (ICLR) (2017)
  * [26] Killamsetty, K., Sivasubramanian, D., Ramakrishnan, G., Iyer, R.: Glister: Generalization based data subset selection for efficient and robust learning. In: Proc. AAAI Conference on Artificial Intelligence. vol. 35, pp. 8110–8118 (2021)
  * [27] Kolouri, S., Saha, A., Pirsiavash, H., Hoffmann, H.: Universal litmus patterns: Revealing backdoor attacks in CNNs. In: Proc. IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 301–310 (2020)
  * [28] Krizhevsky, A.: Learning multiple layers of features from tiny images. Tech. rep., University of Toronto (2009)
  * [29] Krizhevsky, A., Sutskever, I., Hinton, G.E.: Imagenet classification with deep convolutional neural networks. In: Neural Information Processing Systems. vol. 25 (2012)
  * [30] LeCun, Y.: The MNIST database of handwritten digits. http://yann. lecun. com/exdb/mnist/ (1998)
  * [31] Li, Y., Lyu, X., Koren, N., Lyu, L., Li, B., Ma, X.: Neural attention distillation: Erasing backdoor triggers from deep neural networks. International Conference on Learning Representations (2021)
  * [32] Li, Y., Jiang, Y., Li, Z., Xia, S.T.: Backdoor learning: A survey. IEEE Transactions on Neural Networks and Learning Systems (2022)
  * [33] Li, Y., Zhou, Y., Wu, X., Zhang, X., Long, Y., Qiao, Z.: On the effectiveness of trojan triggers in neural networks. In: ACM SIGSAC Conference on Computer and Communications Security. pp. 1921–1937 (2021)
  * [34] Li, Y., Wang, X., Wang, J., Gong, K.: Trigger-poisoning attack: Towards stealthy and efficient trigger embedding into text classification models. In: ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. pp. 2563–2573 (2022)
  * [35] Li, Y., Li, Y., Wu, B., Li, L., He, R., Lyu, S.: Invisible backdoor attack with sample-specific triggers. In: Proc. IEEE/CVF International Conference on Computer Vision. pp. 16463–16472 (2021)
  * [36] Liu, K., Dolan-Gavitt, B., Garg, S.: Fine-pruning: Defending against backdooring attacks on deep neural networks. In: International Symposium on Research in Attacks, Intrusions, and Defenses. pp. 273–294. Springer (2018)
  * [37] Liu, X., Li, M., Wang, H., Hu, S., Ye, D., Jin, H., Wu, L., Xiao, C.: Detecting backdoors during the inference stage based on corruption robustness consistency. In: Proc. IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 16363–16372 (2023)
  * [38] Liu, Y., Ma, S., Liu, Y., Wong, D.S., Xie, Q.: Trojannet – a simple yet effective attack on machine learning models. In: Proc. International Conference on World Wide Web. pp. 1265–1274 (2017)
  * [39] Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions—i. Mathematical programming 14, 265–294 (1978)
  * [40] Pan, X., Zhang, M., Sheng, B., Zhu, J., Yang, M.: Hidden trigger backdoor attack on $\\{$NLP$\\}$ models via linguistic style manipulation. In: 31st USENIX Security Symposium (USENIX Security 22). pp. 3611–3628 (2022)
  * [41] Qi, X., Xie, T., Li, Y., Mahloujifar, S., Mittal, P.: Revisiting the assumption of latent separability for backdoor defenses. In: The eleventh international conference on learning representations (2022)
  * [42] Rakin, A.S., He, Z., Fan, D.: TBT: Targeted neural network attack with bit Trojan. In: IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 13198–13207 (2020)
  * [43] Salem, A., Wen, R., Backes, M., Ma, S., Zhang, Y.: Dynamic backdoor attacks against machine learning models. In: 2022 IEEE 7th European Symposium on Security and Privacy (EuroS&P). pp. 703–718. IEEE (2022)
  * [44] Shafahi, A., Huang, W.R., Najibi, M., Suciu, O., Studer, C., Dumitras, T., Goldstein, T.: Poison frogs! Targeted clean-label poisoning attacks on neural networks. Neural Information Processing Systems 31 (2018)
  * [45] Silver, D., Huang, A., Maddison, C.J., Guez, A., Sifre, L., van den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., Dieleman, S., Grewe, D., Nham, J., Kalchbrenner, N., Sutskever, I., Lillicrap, T., Leach, M., Kavukcuoglu, K., Graepel, T., Hassabis, D.: Mastering the game of Go with deep neural networks and tree search. Nature 529(7587), 484–489 (2016)
  * [46] Souri, H., Fowl, L., Chellappa, R., Goldblum, M., Goldstein, T.: Sleeper agent: Scalable hidden trigger backdoors for neural networks trained from scratch. Advances in Neural Information Processing Systems 35, 19165–19178 (2022)
  * [47] Tang, D., Wang, X., Tang, H., Zhang, K.: Demon in the variant: Statistical analysis of $\\{$DNNs$\\}$ for robust backdoor contamination detection. In: 30th USENIX Security Symposium (USENIX Security 21). pp. 1541–1558 (2021)
  * [48] Tran, B., Li, J., Madry, A.: Spectral signatures in backdoor attacks. Neural Information Processing Systems 31 (2018)
  * [49] Wang, B., Yao, Y., Zhao, X., Gu, Y., Wen, Y., Wei, D.: Trojantrigger: Embedding triggers in steganographic space. In: ACM SIGSAC Conference on Computer and Communications Security. pp. 2740–2757 (2020)
  * [50] Wang, B., Yao, Y., Shan, S., Li, H., Viswanath, B., Zheng, H., Zhao, B.Y.: Neural cleanse: Identifying and mitigating backdoor attacks in neural networks. In: IEEE Symposium on Security and Privacy (SP). pp. 707–723 (2019)
  * [51] Wang, T., Zhao, X., Gu, Y., Wei, D., Sun, X., Wang, B.: Stealthy model poisoning attack: Embedding triggers without affecting clean samples. In: Proc. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. pp. 1826–1836 (2020)
  * [52] Warden, P.: Speech commands: A dataset for limited-vocabulary speech recognition. arXiv preprint arXiv:1804.03209 (2018)
  * [53] Wenger, E., Passananti, J., Bhagoji, A.N., Yao, Y., Zheng, H., Zhao, B.Y.: Backdoor attacks against deep learning systems in the physical world. In: Proc. IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 6206–6215 (2021)
  * [54] Xu, X., Wang, Q., Li, H., Borisov, N., Gunter, C.A., Li, B.: Detecting AI Trojans using meta neural analysis. In: IEEE Symposium on Security and Privacy (SP). pp. 103–120 (2021)
  * [55] Yao, Y., Li, H., Zheng, H., Zhao, B.Y.: Latent backdoor attacks on deep neural networks. In: ACM SIGSAC Conference on Computer and Communications Security. pp. 2041–2055 (2019)
  * [56] Yoshida, K., Fujino, T.: Disabling backdoor and identifying poison data by using knowledge distillation in backdoor attacks on deep neural networks. In: ACM Workshop on Artificial Intelligence and Security. pp. 117–127 (2020)
  * [57] Zhang, X., Zhu, X., Zhou, Y., Long, Y., Wu, X., Qiao, Z.: Stealthy backdoor attacks on deep learning models. In: ACM SIGSAC Conference on Computer and Communications Security. pp. 2647–2664 (2020)

##  Appendix A Appendix

This Appendix presents detailed proofs of our result in Proposition 4.1 and
supermodularity of the test loss (Theorem A.4).

###  A.1 Proof of Proposition 4.1

Proposition 4.1 provided a characterization of the solution of the min-max
optimization problem presented in Eqn. (4.1). We show that output
distributions of Trojaned and clean DNNs will be identical at the optimal
solution, and can be interpreted as the adversary winning the co-evolution
game by successfully evading detection. We restate Prop. 4.1 below.

Proposition 4.1: _For a random input data sample $x\in\mathscr{D}_{R}$, let
$z_{T}:=f_{\theta_{T}}(x)$ and $z_{C}:=f_{\theta_{C}}(x)$ respectively denote
the outputs of a Trojaned model and a clean model. Let $q_{T}$ and $q_{C}$
denote probability distributions associated with $z_{T}$ and $z_{C}$. Then, at
the optimal solution of the game in Eqn. (4.1), the output distributions
coming from clean models and Trojaned models will be identical- i.e.,
$q_{T}=q_{C}$, thus allowing the adversary to successfully evade detection._

###### Proof.

Eqn. (4.1) consists of four terms:

$\displaystyle\min_{\theta_{T}}\max_{\theta_{D}}\hskip 2.84526pt$
$\displaystyle\mathbb{E}_{z_{T}\sim q_{T}}[\log(1-h_{\theta_{D}}(z_{T}))]$
$\displaystyle+\mathbb{E}_{z_{C}\sim q_{C}}[\log(h_{\theta_{D}}(z_{C}))]$
$\displaystyle+\mathbb{E}_{x\sim{p}}[\ell_{\theta_{T}}(x\times(1-\Delta)+\delta\times\Delta,y_{T})+\ell_{\theta_{T}}(x,y_{C})],$

where $x_{T}:=x\times(1-\Delta)+\delta\times\Delta$ denotes a trigger-embedded
input sample. For a fixed $\theta_{T}$, let $V_{\text{max}}$ denote the
solution to the maximization part of the min-max problem in Eqn. (4.1). We
have:

$\displaystyle V_{\text{max}}=$
$\displaystyle\mathbb{E}_{z_{T}\sim{q}_{T}}[\log(1-h_{\theta_{D}}(z_{T}))]+\mathbb{E}_{z_{C}\sim{q}_{C}}[\log(h_{\theta_{D}}(z_{C}))]$
$\displaystyle=$
$\displaystyle\mathbb{E}_{z\sim{q}_{T}}[\log(1-h_{\theta_{D}}(z))]+\mathbb{E}_{z\sim{q}_{C}}[\log(h_{\theta_{D}}(z))]$
$\displaystyle=$
$\displaystyle\int_{z}{q}_{T}(z)\log(1-h_{\theta_{D}}(z))dz+\int_{z}{q}_{C}(z)\log(h_{\theta_{D}}(z))dz,$

where the first two equalities hold by variable substitution, and the last
equality holds by the definition of expectation.

To complete solving the maximization sub-problem, we observe that for any
$(a,b)\in\mathbb{R}^{2}\backslash\\{0,0\\}$, the function $x\rightarrow
a\log(1-x)+b\log(x)$ achieves its maximum in $[0,1]$ at $\frac{b}{a+b}$.
Therefore, for a fixed $\theta_{T}$, we obtain

$\displaystyle
h_{\theta_{D}^{\star}}(z)=\frac{{q}_{C}(z)}{{q}_{T}(z)+{q}_{C}(z)}.$

With the above value of $h_{\theta_{D}^{\star}}(z)$, let $V_{\text{min}}$
denote the solution to the minimization part of the min-max optimization
problem in Eqn. (4.1). We have

$\displaystyle V_{\text{min}}$
$\displaystyle=\int_{z}{q}_{T}(z)\log\Big{(}1-\frac{{q}_{C}(z)}{{q}_{T}(z)+{q}_{C}(z)}\Big{)}dz$
$\displaystyle\quad+\int_{z}{q}_{C}(z)\log\Big{(}\frac{{q}_{C}(z)}{{q}_{T}(z)+{q}_{C}(z)}\Big{)}dz$
$\displaystyle\quad+\mathbb{E}_{x\sim{p}}[\ell_{\theta_{T}}(x\times(1-\Delta)+\delta\times\Delta,y_{T})+\ell_{\theta_{T}}(x,y_{C})]$
$\displaystyle=\int_{z}{q}_{T}(z)\log\Big{(}\frac{{q}_{T}(z)}{{q}_{T}(z)+{q}_{C}(z)}\Big{)}dz$
$\displaystyle\quad+\int_{z}{q}_{C}(z)\log\Big{(}\frac{{q}_{C}(z)}{{q}_{T}(z)+{p}_{C}(z)}\Big{)}dz$
(7)
$\displaystyle\quad+\mathbb{E}_{x\sim{p}}[\ell_{\theta_{T}}(x\times(1-\Delta)+\delta\times\Delta,y_{T})+\ell_{\theta_{T}}(x,y_{C})]$

The first two terms in Eqn. (7) can be interpreted as KL divergences between
probability distributions $q_{T}$ and $q_{C}$. The KL divergence between two
probability distributions $p_{1}$ and $p_{2}$ is defined by
$KL(p_{1}||p_{2}):=\int_{-\infty}^{+\infty}p_{1}(x)\log\Big{(}\frac{p_{1}(x)}{p_{2}(x)}\Big{)}dx$
[12]. Thus,
$\int_{-\infty}^{+\infty}p_{1}(x)\log\Big{(}\frac{p_{1}(x)}{p_{1}(x)+p_{2}(x)}\Big{)}dx\propto
KL(p_{1}||(p_{1}+p_{2})/2)$. Here, $(p_{1}+p_{2})/2$ is used to ensure
validity of the probability distribution such that
$\int_{x}(p_{1}(x)+p_{2}(x))/2)=1$. Substituting into Eqn. (7), we obtain

$\displaystyle V_{\text{min}}=$
$\displaystyle\text{KL}\Big{(}{q}_{T}||\frac{{q}_{T}+{q}_{C}}{2}\Big{)}+\text{KL}\Big{(}{q}_{C}||\frac{{q}_{T}+{q}_{C}}{2}\Big{)}$
(8)
$\displaystyle+\mathbb{E}_{x\sim{p}}[\ell_{\theta_{T}}(x\times(1-\Delta)+\delta\times\Delta,y_{T})+\ell_{\theta_{T}}(x,y_{C})].$

Recall from Sec. 4 that $q_{T}$ and $q_{C}$ are output distributions from
clean and Trojaned DNNs when inputs $x$ to the models are generated from a
multi-variate Gaussian distribution $\mathscr{N}$. Hence the first two terms
in Eqn. (8) depend only on input samples from the set
$\mathscr{D}_{R}=\\{x\leavevmode\nobreak\ |\leavevmode\nobreak\
x\sim\mathscr{N}\\}$ while the last two terms depend only on input samples
from $\mathscr{D}=\\{(x,y)\leavevmode\nobreak\ |\leavevmode\nobreak\ (x,y)\sim
p\\}$.

The proof follows by observing that the first two terms in Eqn. (8) become
zero when $q_{T}=\frac{q_{T}+q_{C}}{2}$, i.e., $q_{T}=q_{C}$. ∎

###  A.2 Analysis of Test Loss Function

In this section, we prove that when the loss function for selecting input
samples for trigger-embedding is the cross-entropy loss, the adversary’s test
loss function satisfies a diminishing returns or supermodularity property. We
first present a formal definition of supermodularity.

######  Definition A.1 ([16]).

Given a finite set $\Omega$, a function $g:2^{\Omega}\rightarrow\mathbb{R}$ is
submodular if $g(V\cup\\{v\\})-g(V)\geq g(U\cup\\{v\\})-g(U)$ for any
$V\subseteq U\subseteq\Omega$ and any $v\in\Omega\setminus U$. Function $g$ is
said to be supermodular if $-g$ is submodular.

Given two sets $V$ and $U$ such that $V\subseteq U\subseteq\Omega$, Definition
A.1 indicates that the marginal increase in the value of the function $g$ is
higher when an element $v\in\Omega\setminus U$ is added to a smaller subset
$V$ than when the same sample is added to a larger subset $U\supseteq V$. For
any $U,V\subseteq\Omega$, we say a function
$g:2^{\Omega}\rightarrow\mathbb{R}$ is weakly submodular if $\sum_{u\in
U}(g(V\cup\\{u\\})-g(V))\geq\gamma(g(V\cup U)-g(V))$ for some
$\gamma\in(0,1]$. To show such supermodularity property for the test-loss
function, we first present a result from [26] which holds for a class of
commonly used loss-functions.

######  Lemma A.2 ([26]).

When $\ell_{\theta}$ is chosen as negative logistic loss, negative squared
loss, negative hinge loss, perceptron loss, the data subset selection problem
is an instance of submodular maximization problem. When $\ell_{\theta}$ is the
negative cross entropy loss, the data subset selection problem is an instance
of weakly submodular maximization problem.

We recall notation from Sec. 5. The set of clean samples is denoted by
$\mathscr{D}$ and the subset of clean samples into which a trigger is embedded
by $\tilde{\mathscr{D}}$. In order to evaluate the efficacy of the set of
trigger-embedded inputs in training a Trojaned DNN, the adversary will use a
test dataset, denoted $\mathscr{D}_{\text{Test}}$, where
$\mathscr{D}_{\text{Test}}$ contains samples that are not part of the training
dataset. Additionally, the adversary will use a test set, denoted
$\mathscr{\tilde{D}}_{\text{Test}}$, for embedding a Trojan trigger. We use
$\mathscr{L}_{T}(\mathscr{D},\mathscr{\tilde{D}})$ and
$\mathscr{L}_{C}(\mathscr{D},\mathscr{\tilde{D}})$ to represent loss functions
computed using $\mathscr{\tilde{D}}_{\text{Test}}$ and
$\mathscr{D}_{\text{Test}}$, and
$\mathscr{L}_{tot}(\mathscr{D},\mathscr{\tilde{D}}):=\mathscr{L}_{T}(\mathscr{D},\mathscr{\tilde{D}})+\mathscr{L}_{C}(\mathscr{D},\mathscr{\tilde{D}})$
to denote the (total) test loss. Then, determining the subset of input samples
into which to embed a Trojan trigger can be characterized as (also Eqn. (4)):

$\displaystyle\min_{\mathscr{\tilde{D}}\subset\mathscr{D}}\mathscr{L}_{T}(\mathscr{D},\mathscr{\tilde{D}})+\mathscr{L}_{C}(\mathscr{D},\mathscr{\tilde{D}}).$

In our case, the subset of data of interest is the subset of samples into
which a trigger will be embedded, and the loss function will be
$\mathscr{L}_{T}(\mathscr{D},\mathscr{\tilde{D}})$. Based on this choice of
subset and loss function, we present a variant of Lemma A.2 below.

######  Lemma A.3.

When $\ell_{\theta}$ is chosen as logistic loss, squared loss, hinge loss,
perceptron loss, or cross entropy loss, the test loss-function term associated
with predicting trigger-embedded samples to the adversary-desired target
class, $\mathscr{L}_{T}(\mathscr{D},\mathscr{\tilde{D}})$ is (weakly)
supermodular in the trigger-embedded dataset, $\mathscr{\tilde{D}}$.

Although Lemma A.3 indicates that
$\mathscr{L}_{T}(\mathscr{D},\mathscr{\tilde{D}})$ is (weakly) supermodular in
the trigger-embedded dataset, $\mathscr{\tilde{D}}$, it does not imply (weak)
supermodularity of $\mathscr{L}_{tot}(\mathscr{D},\mathscr{\tilde{D}})$. In
the following, we show that under certain conditions, the total test-loss
function in Eqn. (4) is supermodular.

######  Theorem A.4.

Consider two datasets $\mathscr{\tilde{D}}_{1}$ and $\mathscr{\tilde{D}}_{2}$,
where $\mathscr{\tilde{D}}_{1}\subset\mathscr{\tilde{D}}_{2}$,
$|\mathscr{\tilde{D}}|_{1}=s$, $|\mathscr{\tilde{D}}|_{2}=k$, and $k>s>0$. Let
$m_{C}$ and $m_{T}$ be defined as

$\displaystyle m_{C}^{s}$
$\displaystyle=\mathscr{L}_{C}(\mathscr{D},\mathscr{\tilde{D}}_{1})-\mathscr{L}_{C}(\mathscr{D},\mathscr{\tilde{D}}_{1}\cup\\{(x,y)\\}),$
$\displaystyle m_{C}^{k}$
$\displaystyle=\mathscr{L}_{C}(\mathscr{D},\mathscr{\tilde{D}}_{2})-\mathscr{L}_{C}(\mathscr{D},\mathscr{\tilde{D}}_{2}\cup\\{(x,y)\\}),$
$\displaystyle m_{T}^{s}$
$\displaystyle=\mathscr{L}_{T}(\mathscr{D},\mathscr{\tilde{D}}_{1})-\mathscr{L}_{T}(\mathscr{D},\mathscr{\tilde{D}}_{1}\cup\\{(x,y)\\}),$
$\displaystyle m_{T}^{k}$
$\displaystyle=\mathscr{L}_{T}(\mathscr{D},\mathscr{\tilde{D}}_{2})-\mathscr{L}_{T}(\mathscr{D},\mathscr{\tilde{D}}_{2}\cup\\{(x,y)\\}),$

where $\\{(x,y)\\}\notin\mathscr{\tilde{D}}_{2}$. If $m_{C}^{s}+m_{T}^{s}\geq
m_{C}^{k}+m_{T}^{k}$ for all $k>s>0$ and
$\\{(x,y)\\}\notin\mathscr{\tilde{D}}_{2}$, then the total test-loss function
in Eqn. (4), $\mathscr{L}_{\text{tot}}(\mathscr{D},\mathscr{\tilde{D}})$ is
supermodular in $\mathscr{\tilde{D}}$.

###### Proof.

Our proof follows from the supermodularity property from Definition A.1. Using
Eqn. (4), we have that

$\mathscr{L}_{tot}(\mathscr{D},\mathscr{\tilde{D}}_{1})-\mathscr{L}_{tot}(\mathscr{D},\mathscr{\tilde{D}}_{1}\cup\\{(x,y)\\})\\\
-(\mathscr{L}_{tot}(\mathscr{D},\mathscr{\tilde{D}}_{2})-\mathscr{L}_{tot}(\mathscr{D},\mathscr{\tilde{D}}_{2}\cup\\{(x,y)\\}))\\\
=m_{C}^{s}+m_{T}^{s}-(m_{T}^{k}+m_{T}^{k}).$ (9)

Since $m_{C}^{s}+m_{T}^{s}\geq(m_{T}^{k}+m_{T}^{k})$ by assumption, we have
$\mathscr{L}_{tot}(\mathscr{D},\mathscr{\tilde{D}}_{1})-\mathscr{L}_{tot}(\mathscr{D},\mathscr{\tilde{D}}_{1}\cup\\{(x,y)\\})-(\mathscr{L}_{tot}(\mathscr{D},\mathscr{\tilde{D}}_{2})-\mathscr{L}_{tot}(\mathscr{D},\mathscr{\tilde{D}}_{2}\cup\\{(x,y)\\}))\geq
0$ for all $k>s>0$. Therefore, from Def. A.1, the total test-loss
$\mathscr{L}_{tot}(\mathscr{D},\mathscr{\tilde{D}})$ is supermodular.∎

The conditions in Theorem A.4 imply that the marginal impact on the total
test-loss function by adding one (new) trigger-embedded sample into
$\mathscr{\tilde{D}}$ reduces as $|\mathscr{\tilde{D}}|$ increases.