# Trojan Signatures in DNN Weights

Greg Fields, Mohammad Samragh, Mojan Javaheripi, Farinaz Koushanfar, Tara
Javidi
University of California San Diego
{grfields, msamragh, mojan, farinaz<EMAIL_ADDRESS>
###### Abstract

Deep neural networks have been shown to be vulnerable to backdoor, or trojan,
attacks where an adversary has embedded a trigger in the network at training
time such that the model correctly classifies all standard inputs, but
generates a targeted, incorrect classification on any input which contains the
trigger. In this paper, we present the first ultra light-weight and highly
effective trojan detection method that does not require access to the
training/test data, does not involve any expensive computations, and makes no
assumptions on the nature of the trojan trigger. Our approach focuses on
analysis of the weights of the final, linear layer of the network. We
empirically demonstrate several characteristics of these weights that occur
frequently in trojaned networks, but not in benign networks. In particular, we
show that the distribution of the weights associated with the trojan target
class is clearly distinguishable from the weights associated with other
classes. Using this, we demonstrate the effectiveness of our proposed
detection method against state-of-the-art attacks across a variety of
architectures, datasets, and trigger types.

##  1 Introduction

Deep neural networks have achieved state of the art performance in a variety
of problem domains, such as image recognition, speech analysis, and wireless
data. However these networks have also been shown to be vulnerable to a
particular kind of adversarial attack, commonly referred to as backdoor or
trojan attacks [7, 13]. These attacks may occur when the adversary has access
to the model at training time and embeds malicious behavior in the network. As
state of the art networks continue to grow larger and require more data for
training, it is frequently necessary to outsource the training process to
third party vendors which exposes the network to the threat of trojan attacks.
Common trojan attacks insert a particular pattern, called the trigger, into
the training data. The network is then trained to always produce a specific,
targeted misclassification on any input containing the trigger. To obscure the
attack, the adversary ensures that the model still achieves high accuracy on
clean data. Since the trigger is unknown and arbitrary, it is extremely
challenging to detect if a model has been compromised in this way.

As machine learning models are deployed to more sensitive applications, such
as autonomous driving and face recognition, it becomes paramount to ensure
their security. A variety of defenses to trojan attacks have been proposed in
the literature to combat these attacks. Several works have proposed reverse
engineering the trojan trigger, generating synthetic data to analyze the
model, or model retraining [16, 2, 12]. These methods require excessive
training time and access to high-end computational resources and abundant
data. But, in scenarios where the user chooses to purchase a trained model
from a third party, they often do not have access to computing resources
and/or the training data. Other defenses analyze the inputs to the network
after deployment to detect possible trojan triggers [6, 5, 9]. In this
scenario, the client is exposed to malicious behavior while waiting to
identify trojaned inputs, which is unacceptable in sensitive applications.

We propose a very fast, accurate trojan detection mechanism for identifying
trojaned networks before deployment, avoiding exposure of DNN-based systems to
malicious behavior. Notably, our approach does not require access to any data,
carries a very low computational cost, and is broadly applicable to different
types of trojan triggers. Our detection strategy relies on our hypothesis that
the trojan attack creates a detectable signature in the final classification
layer of the network. We provide analysis and extensive empirical evaluations
in support of this claim. Specifically, we show that the weights associated
with the target class are an outlier relative to those of the other classes.
Our method identifies the trojan target class by applying Dixon’s Q-test [4]
for identifying single outliers in small samples. The resulting lightweight
trojan detection mechanism achieves $100\%$ detection on commonly used
datasets in trojan research. On a more extensive set of trojaned models [10]
containing 650+ models111https://pages.nist.gov/trojai/docs/data.html#round-2
that are highly diverse in architecture, attack parameters, and datasets, our
method correctly detects $98\%$ of trojaned networks with under $4\%$ false
positive rate.

In brief, the contributions of this paper are as follows:

  * •

We provide a highly effective, uniquely lightweight detection method that does
not require access to any data, is broadly applicable to various trojan
triggers, and requires very low computation. Our data-free analysis detects
compromised networks before deployment, minimizing possible risks caused by
trojaned models.

  * •

We connect our analysis to statistical tests for small sample, single outlier
detection and provide confidence measures regarding whether or not a model is
trojaned.

  * •

We conduct extensive evaluations on over 700 models, five datasets, and six
types of trojan trigger under a wide variety of different parameters to
demonstrate the robustness of our detection technique.

##  2 Threat Model and Notation

Let $F:\mathbb{R}^{m}\to\\{1,...,C\\}$ denote a deep neural network performing
classification into one of $C$ classes. Then we say that $F$ is trojaned if
$F$ achieves high classification accuracy over inputs $\mathbf{x}$ from its
data distribution, but there exists some function
$g:\mathbb{R}^{m}\to\mathbb{R}^{m}$, called the trojan trigger, such that
$F(g(\mathbf{x}))=t$, where $t$ is called the trojan target class. Figure 1
shows an image $x$ and example trojaned images $g(x)$ studied in this paper.
Here we specifically consider the case where $g$ is an input agnostic trigger,
i.e., it must apply to all inputs from any of the $C$ classes.

(a)

(b)

(c)

(d)

(e)

(f)

Figure 1: In the first row, a base image with two different triggers from the
TrojanN attack applied to it. In the second row, examples of a base image, the
polygon trigger, and the Instagram filter trigger from the TrojAI dataset

We consider the real-world scenario where the user employs a model trained by
a third party and therefore (1) is not aware whether or not the model is
trojaned. (2) In case there exists a trojan embedded in the model, the user
does not have any information about the trigger. (3) The user does not have
access to any subset of the training data. We assume the user has white-box
access to the network parameters. As discussed in the introduction, a user who
has had to outsource the training of their model, and so is vulnerable to
trojan attacks, likely has limited resources. So we assume that we must detect
the trojaned network with no access to any data and without access to
significant computational resources. We also want to create a test that can
detect trojan attacks before deploying the model, so as to not expose any
sensitive systems to a potentially malignant network.

We propose a detection mechanism which takes the network $F$ and determines,
to a level of confidence, whether or not the network has had a trojan trigger
embedded in it. Our analysis focuses on the final, linear layer of the
network. Let $f:\mathbb{R}^{m}\to\mathbb{R}^{d}$ denote all but the final
layer of the network and $\mathbf{W}\in\mathbb{R}^{d\times C}$, so that
$\mathbf{W}f(\mathbf{x})$ gives the pre-softmax scores of the network on input
$\mathbf{x}$. Then $\mathbf{z}=f(\mathbf{x})$ is the penultimate feature
representation of $F$ on input $\mathbf{x}$. Our analysis specializes to the
case where $\mathbf{z}$ is the output of a ReLU activation function and the
network is trained with the cross entropy loss. These assumptions are true of
the vast majority of commonly used network architectures and training methods.

##  3 Analysis

Our method relies on the observation that, in a trojaned input, many of the
features of the underlying class will still be present. This is particularly
true in the standard case where the trigger is a localized patch which only
obscures a small portion of the underlying input. With this intuition, we will
consider the feature representations of the trojan trigger and the underlying
input separately. Given a clean, un-triggered sample $\mathbf{x}$, let
$\mathbf{z}:=f(\mathbf{x})$ denote its penultimate feature representation and
define $\boldsymbol{\Delta}_{\mathbf{x}}:=f(g(\mathbf{x}))-f(\mathbf{x})$ to
be the change in this feature space induced by the application of the trojan
trigger.

Then we will consider the training process, and in particular the gradient
updates to the rows of the weight matrix of the final layer: let
$\mathbf{W}_{i}$ denote the $i$-th row of $\mathbf{W}$. Most commonly, the
network is trained by some form of stochastic gradient descent. Given a
training point $\mathbf{x}$ from class $i$, define $\mathbf{y}$ to be the one
hot encoding of this true class, so $\mathbf{y}_{i}=1$ and $\mathbf{y}_{j}=0$
for $j\neq i$, and let $\hat{\mathbf{y}}$ be the softmax prediction vector of
the network. And recall that we denote the penultimate feature representation
$\mathbf{z}=f(\mathbf{x})$, then one SGD update for the $i$th row
$\mathbf{W}_{i}$ is given by:

$\mathbf{W}_{i}=\mathbf{W}_{i}+\eta\mathbb{E}[(\mathbf{y}-\hat{\mathbf{y}})_{i}\mathbf{z}^{T}]$
(1)

where the expectation is over the choice of sample from the training set. Then
note that $(\mathbf{y}-\hat{\mathbf{y}})_{i}$ will only be positive when
$\mathbf{z}$ is the representation of a point from class $i$. This means that
$\mathbf{W}_{i}$ is the accumulation of positive scalings of feature
representations of all data points from class $i$ and negative scalings of
representations from all other classes.

When embedding a trojan trigger in the network, the training set includes
poisoned data points of the form $g(\mathbf{x})$ where $\mathbf{x}$ itself is
a valid sample. For these points we can decompose the feature representation
as above: $f(g(\mathbf{x}))=\mathbf{z}+\boldsymbol{\Delta}_{\mathbf{x}}$ where
$\mathbf{z}=f(\mathbf{x})$.

And, as part of the trojaning process, these points are all labelled class
$t$, so the update to $\mathbf{W}_{t}$ is then
$\mathbf{W}_{t}=\mathbf{W}_{t}+\eta(\mathbf{y}-\hat{\mathbf{y}})_{t}(\mathbf{z}+\boldsymbol{\Delta}_{\mathbf{x}})^{T}$
on the poisoned points.

The quantity $(\mathbf{y}-\hat{\mathbf{y}})_{t}$ will be positive here. This
sets the target class apart from the other classes, as its associated weight
row, $\mathbf{W}_{t}$ accumulates positive scalings of feature representations
from every class in the dataset, since we assume that the trojan must be input
agnostic. Every other row of $\mathbf{W}$ only accumulates positive scalings
of feature representations from data from their own class. And, by assumption
that these features are the output of a ReLU function and so non-negative, we
expect that the average weights of the target row are more positive than those
of the other rows.

Intuitively, this amounts to the fact that if we wish to poison a point
$\mathbf{x}$ from class $i$, the application of the trigger has to overcome
the confidence of the network on point $\mathbf{x}$:
$\mathbf{W}_{i}f(\mathbf{x})-\mathbf{W}_{t}f(\mathbf{x})$. If this quantity is
very large, then the application of the trigger must induce an even larger
change in the output of the network. So $\mathbf{W}_{t}$ should have a
distinctly large inner product with the (non-negative) feature representations
of every class in the dataset.

(a)

(b)

(c)

Figure 2: The plot on the left in each image shows the smoothed distributions
of the weights in each row of a trojaned model and the plots on the right show
the average weights of each row. Here, the trojan target class is shown in
red.

##  4 Methodology

We now set out an effective small-sample outlier detection framework to take
advantage of the expectation that the average weights of the target row will
be significantly larger than the average weights of the other rows of
$\mathbb{W}$.

We use the statistic, hereafter called the Q-value, from Dixon’s Q test [4],
which is designed to detect a single outlier in small samples of data. This
test works by taking a candidate outlier, finding the absolute difference
between that value and its next closest value in the sample, and normalizing
by the range of the values in the sample.

Since we expect the average weight of the target row to be a large, positive
outlier, we can find the desired statistic by taking the average weight of
each row, $w_{i}:=\frac{1}{d}\sum_{j=1}^{d}W_{i,j}$ and sorting them so that
$w_{i_{1}}\leq...\leq w_{i_{c}}$, then calculating

$Q=\frac{|w_{i_{c}}-w_{i_{c-1}}|}{w_{i_{c}}-w_{i_{1}}}$ (2)

That is, we calculate the gap between the largest and second largest average
row weight and normalize by the difference between the largest and smallest
average row weight. Then, to formally apply this test with no reference
models, the Q statistic is compared to tabulated values, giving a confidence
that the average weight associated with one of the classes is an outlier. For
instance, in a model with 8 classes and Q$>.468$ we would conclude that it
possesses an outlier at 90% confidence. This model is then likely trojaned
with the row with the largest average weight giving the target class.

##  5 Results

###  5.1 TrojAI

$\blacktriangleright$ Performance Metrics We will characterize the performance
of our detection method by two primary metrics: the false positive rate, which
is the percent of benign networks incorrectly identified as trojaned, and the
false negative rate, which is the number of trojaned networks incorrectly
identified as benign. In general, a smaller value is desirable for both
metrics and various choices of threshold for Q will induce a trade-off between
the two as our method is made more sensitive or more permissive. We will
report results for varying choices of threshold to explore this trade-off for
different problem settings.

$\blacktriangleright$ The TrojAI Benchmark. We evaluate our detection method
on the dataset provided by the TrojAI project [10], which contains a large set
of both benign and trojaned models of diverse architectures: Resnet,
WideResnet, Densenet, GoogleNet, Mobilenet, ShuffleNet, and VGG. In this
section we study 174 trojaned and 502 benign models. The models are trained
via datasets of varying complexity and size and trojan triggers of varying
strength and type. The attacks poison between 2% and 50% of the training data
and additive triggers obscure between 2% and 25% of the foreground images. As
such, this benchmark provides a reasonable approximation of a real world,
unrestricted problem.

There are two broad classes of triggers used. One encompasses small, solid
colored polygon patches overlaid on top of the base image, the other are
Instagram filters applied to the base image, examples of both are displayed in
Figure 1. The Instagram filters evade many existing defenses such as [16], as
they are complicated, non-local perturbations that are functions of their
input.

$\blacktriangleright$ Empirical Analysis of Trojan Signatures. Figure 2 shows
the distribution of the weights per row from the final layer of three
representative trojaned models from the TrojAI dataset. In the plots on the
left in each figure, each curve gives the smoothed distribution of the weights
of one of the rows of the matrix, $\mathbb{W}_{i}$. In particular, the red
curve in each image corresponds to the row of the trojan target class. These
plots exhibit the characteristics suggested by our analysis. In the first and
third models, the target row has mass shifted from negative values to a
concentration of small magnitude positive values. But in the second model the
entire distribution is shifted slightly to the right, yielding more large
positive values. This pattern persists throughout the set of models: while the
exact details of the shift in distribution varies model by model, the end
result is always a positive shift of mass. On the right in each figure are the
average weights of each row for the same model, each point giving the average
weight of one of the rows with the red point corresponding to the row of the
target class. This illustrates how, regardless of the details of the shift in
weight distribution, the effects of the trojan attack manifest as an increase
in the average weight of the target class relative to the weights of the other
classes. This validates our use of the average weight per row as an effective
way to identify trojaned models. We can thus use the outlier detection
described in the methodology section to construct an automated, light-weight
detector for trojaned networks.

$\blacktriangleright$ Efficacy against Localized Attacks. We study the Polygon
attack as an example of a trojan attack with a localized, additive trigger.
Figure 3-(a) shows the normalized histograms of Q-scores of the the models
trojaned by the polygon trigger compared with the Q-scores of benign models.
There is a very clear distinction between the scores of the trojaned models
and those of the benign models, allowing for a high-confidence detection of
trojaned models.

Figure 4-(a) shows the false positive and negative rates as a function of the
choice of threshold. Choosing the threshold to be $0.38$ gives a false
negative rate of $2\%$ and a false positive rate of only $3.8\%$. Table 5
reports the necessary choice of Q threshold to attain $1\%$ for either rate.

$\blacktriangleright$ Efficacy against Whole-Image Attacks. Applying an
Instagram filter as the trojan trigger yields a more complicated attack
compared to the the more common localized triggers. The complication lies in
two properties of this attack: (1) the action of the filter is a function of
the underlying image, unlike the additive trojans which add the same trigger
to all valid inputs. (2) The filter is applied to the entire image, altering
each feature of the underlying image. The normalized histogram of Q-values for
Instagram triggered models is shown in Figure 3-(b). As seen, the distribution
of Q-scores in trojaned models is still clearly distinct from that of the
benign models. The false positive and negative rates are shown as a function
of the detection threshold in Figure 4-(b). Compared to the localized attacks,
here we observe a larger number of trojaned models with low Q scores. However,
by setting the Q threshold to $0.3$, we obtain a low false negative rate of
$2\%$ with a false positive rate of only $9\%$, and the false negative and
false positive rate for all choices of threshold can be seen in 4-(b) along
with a selection of specific results in 5. Prior detection methods require
significant side information about the nature of the trigger are generally
unable to address an attack such as the Instagram filters, ours is the first
to be able to detect them with such high accuracy.

(a) Polygon trigger models

(b) Instagram trigger models

Figure 3: Normalized histograms of Q-scores for benign and trojaned models in
the TrojAI dataset.

(a) Polygon trigger models

(b) Instagram trigger models

Figure 4: False negative and false positive rates as a function of the choice
of Q-value threshold on the distributions in Figure 3.

Q | FPR | FNR
---|---|---
.297 | .086 | .010
.433 | .018 | .045
.492 | .010 | .080
(a) Polygon trigger models

Q | FPR | FNR
---|---|---
.121 | .446 | .047
.199 | .243 | .093
.293 | .090 | .163
.370 | .040 | .197
(b) Instagram trigger models

Figure 5: False positive and negative rates at specific choices of Q threshold
from Figure 4. These Q were chosen to attain $1\%$ or $5\%$ for each rate on
the Polygon models and $5\%$ or $10\%$ on the Instagram models.

$\blacktriangleright$ Sensitivity to Poisoned Training Data Ratio. Existing
work shows a correlation between the number of the poisoned training data and
strength of the attack [6]. In this section, we study the dependence of our
detection results on the proportion of the training data that was poisoned.

Figure 6 shows the Q-scores of both polygon and Instagram triggered models as
a function of the percentage of the training data that was poisoned. There is
a positive correlation between the two quantities, with correlation
coefficient 0.27 for the polygon models and 0.51 for the Instagram models.
This agrees with intuition and prior results that poisoning more data creates
a stronger attack. And it shows that it leaves a more distinct signature in
the weights of the final layer of the poisoned network. So a more powerful,
reliable trigger will be more easily detected by our method. This forces the
attacker to choose between the efficacy of their attack and the ease with
which we can detect it.

(a) Polygon trigger models

(b) Instagram trigger models

Figure 6: The Q-scores of the models as a function of the percentage of
training data that was poisoned with the trojan trigger.

###  5.2 GTSRB

$\blacktriangleright$ The GTSRB Benchmark. In this part of our analysis, we
direct our focus on a single convolutional deep network architecture studied
in prior works on trojan attacks [16, 9, 2]. This allows us to perform an in-
depth study of different variations of the trojan attack using the same
benchmark. The model is trained on the GTSRB dataset which comprises 43
classes of German traffic signs and is a common choice of dataset for trojan
research.

(a) Target class 0

(b) Target class 3

(c) Benign

(d) Benign

Figure 7: Average weight per class of four different GTSRB models, two
trojaned with different targets and two benign

$\blacktriangleright$ Trojan and Benign Models, Side by Side. Figure 7 shows
the average row weights of four GTSRB models, two trojaned with different
targets and two benign models, all trained under identical conditions except
for the choice of target class. As seen, in each trojaned model, the average
weight of the target row is a clear outlier and the benign models show no
notable outliers.

$\blacktriangleright$ Sensitivity to Dataset Class Imbalance. The use of GTSRB
dataset allows us to explore a dimension of the problem not present in TrojAI:
dataset class imbalance. Many data poisoning attacks, e.g., the BadNet attack,
result in an imbalanced training set as they add samples to the target class.
This could induce a bias in the network, regardless of trojan behavior. The
GTSRB data is already heavily imbalanced, ranging from only 210 training
examples for class 0 to 2250 for class 3. We study the effect of imbalance
between these two example classes in Figure 7. As shown, the weight row
corresponding to the target class persists as a clear outlier when either
class 0 or class 3 is chosen as the target class. This shows that the trojan
signature is independent of the distribution of the training data.

(a)  Figure 8: Normalized histograms of Q-values for 20 benign and 40 trojaned
models trained on the GTSRB dataset. Benign and trojaned models are shown with
red and green, respectively.

$\blacktriangleright$ Sensitivity to Attack Parameters. Finally, we train 20
benign and 40 trojaned models with varying target classes, with the trigger
size ranging from $2\times 2$ to $12\times 12$ pixels in size and located in
different corners of the image, and with different proportions of data
poisoned, ranging from $10\%$ to $50\%$. We calculate the Q-score of the
average weights for each model and display them in Figure 8. This shows that,
in this problem setting, the benign and trojaned models are entirely
separable, with no false positives or false negatives, under our detection
method.

###  5.3 TrojanNN

All attacks studied so far are model-agnostic, i.e., the trojan trigger is
selected independently from the model and is applied by the training the
model, from scratch, on the poisoned dataset. In this section, we study the
the TrojanNN attack [13] which constructs the trigger from a pre-trained
model. This sophisticated attack identifies neurons from intermediate layers
which have an outsized impact on the output of the pre-trained network. Their
algorithm then reverse engineers a trigger which maximizes the activation of
those internal neurons. This attack generally proves more difficult to detect
than BadNet and other straightforward data poisoning attacks [16, 2].

(a) Square trigger

(b) Watermark trigger

Figure 9: Average weights per row for models trained on 2000 facial
recognition classes, poisoned with the TrojanNN attack.

(a) Attack on $4^{th}$ convolution

(b) Attack on $1^{st}$ fully-connected

Figure 10: Average weights of two different implementations of the TrojaNN
attack, both with target 0, shown in red, compared to benign analogs, shown in
green

$\blacktriangleright$ The TrojanNN Benchmark. The creators of the TrojanNN
attack provide a series of models poisoned with their attack as well as
analogous benign models222https://github.com/PurduePAML/TrojanNN. We analyze
these networks to see if this more subtle attack produces the same weight
signature we saw in our previous results.

$\blacktriangleright$ Face Recognition Benchmark. Figure 9 compares two
examples of a VGGFace network [15] poisoned with the TrojanNN attack, both
trained on the labeled faces in the wild facial recognition dataset [8]. Both
plots show the average weights of each row in the weight matrix of the final
layer of the network. The network in Figures 9-(a), (b) are poisoned with the
square and watermark triggers shown in Figure 1-(b), (c), respectively. In
both models, 0 is the target class and the associated average weight is a
clear outlier, so even this more carefully targeted attack, which deliberately
acts through a small set of neurons in the intermediate layers of the network,
leaves a distinct signature in the weights of the final layer.

While the two figures look almost identical, they are indeed from separate
models with separate triggers and the weights do have different values. This
uniformity is in part due to the fact that the TrojanNN attack is applied on a
pre-trained network. The attack itself is also designed to leave a smaller
footprint in the network, as it targets specific neurons, reverse engineers an
efficient trigger, and only re-trains a portion of the network. This makes it
all the more notable that the weights of the target row are so drastically
exaggerated and thus easily detectable with our analysis.

$\blacktriangleright$ Speech Recognition Benchmark. Figure 10 compares three
different networks trained on a speech detection
dataset333https://github.com/pannous/caffe-speech-recognition. The attacks in
Figure 10-(a), (b) were executed on internal neurons from the fourth
convolution and the first fully connected layers, respectively. For both
models, the average weight of the target row, row 0 is a clear outlier.
Notably, in both cases the average weight of the target row is increased,
while the average weight for all other classes is decreased.

The effect here is far more pronounced when the attack is executed on neurons
in the fully connected layer than the attack focused on neurons in the
convolution layer–the average target weight increased by almost twice as much.
This makes sense in light of the assumptions underlying our analysis. The
retraining in the TrojaNN algorithm freezes all layers prior to the target
neurons–so the action of the trigger is only embedded in the later layers of
the network. Our method relies on the notion that many features of the
underlying input will still be present in the later feature representations of
the poisoned input. Executing the TrojanNN attack on neurons from later layers
ensures that this assumption holds, as it leaves the feature extraction
mechanism of the network largely unchanged and only re-trains the
classification layers.

$\blacktriangleright$ Age Detection Benchmark. Finally, Figure 11 compares the
average row weights of a benign network and a TrojanNN attacked network
trained to perform age classification [11]. Here the target class was 0, so
our approach does not successfully identify the trojan. However, we still see
the effect characteristic of the other trojan attacks–the average target
weight is increased, while other average weights all decreased. Detection here
fails because the change in weights is relatively small, compared to the other
models we have examined, and because the weight of the target row happened to
be abnormally small to begin with.

Figure 11: Average weights of the TrojanNN age identification model with
target 0, in red, compared with a benign analog, in green.

###  5.4 Adaptive attack

To study the robustness of this signature, we also implemented an adaptive
attack intended to evade our detection mechanism and mask the observed shift
in weights. To this end we added a regularization to the standard cross-
entropy loss used in our other experiments. This regularization penalizes the
gap between the average weight of the target row and the average weights of
the other rows:

$L_{reg}=L_{CE}+\gamma\cdot\big{[}\mathbb{E}[\mathbf{W}_{t}]-\mathbb{E}[\mathbf{W}]\big{]}.$
(3)

Where $\mathbb{E}[\mathbf{W}]$ denotes the average value of all weights in the
final weight matrix and $\gamma$ is a free parameter which controls the
strength of the regularization. We note that this is the loss function used
during training, by the adversary, so they know the target, $t$, and can
directly regularize the associated statistic.

(a) $\gamma=0$

(b) $\gamma=0.005$

(c) $\gamma=0.01$

(d) $\gamma=0.05$

Figure 12: Average weight per class of for models trained with four different
values of the regularization parameter $\gamma$ in Equation 3

We trained sets of 10 trojaned models on the GTSRB dataset with this modified
loss for a range of values of $\gamma$, with methodology and architecture
otherwise identical to that used in Section 5.2. Figure 12 shows the average
weight of each row of the final weight matrix, with the average of the target
row highlighted in red. This shows that, as $\gamma$ increases, it is
effective at regulating the average weight of the target row and bringing it
in line with the others, thus masking the signature we analyze. However, this
causes a decrease in both clean accuracy and trigger efficacy: the
unregularized models have an accuracy of $.976\pm.003$ on clean data while the
regularized models have accuracy $.958\pm.005$. And, in the presence of the
trojan trigger, the unregularized models classify to the target class at a
rate of $.991\pm.003$ while the regularized models only attain $.983\pm.004$.
All these values are averaged over 10 models trained independently with
identical settings and show a one standard deviation range. So the
regularization produces a less effective trigger and a less accurate
classifier. Alongside this generally inferior performance, the lower accuracy
on clean data may itself suffice as an indication that the classifier has been
tampered with for architectures and datasets where a standard, attainable
accuracy is known.

(a) $\gamma=0$

(b) $\gamma=0.01$

Figure 13: The weights of the target rows for a trojaned model trained without
regularization ($\gamma=0$) and one trained with regularization, with
$\gamma=0.01$. The training process for the two models was identical besides
the value of $\gamma$.

Furthermore, the masking effect is accomplished in a very artificial, easy to
detect way. Figure 13 shows a scatter plot of the weights for the target row
in two trojaned models, one without regularization, on the left, and one with
$\gamma=0.01$, on the right. The unregularized version has a relatively
diffuse, symmetric distribution of weights with a large concentration near 0.
This is characteristic of the weights for every row, target or otherwise, in
every unregularized model, benign or trojaned, that we trained for the GTSRB
dataset. In contrast, on the right in the regularized model the weights are
far more concentrated and a large number of weights have been shifted
uniformly to a small, negative value. This occurs only for the target row in
trojaned models trained with the regularized loss in Equation 3. This negative
shift in a subset of the weights counteracts the higher average among the rest
of the weights. But the very uniform, artificial shift is easy to detect by
eye, and as discussed above, is totally unique to models trojaned in this way.
So while an adversary with full knowledge of our detection mechanism can evade
it, they can do so only at the cost of a less accurate classifier, a less
effective trigger, and a new signature in the final weight layer.

##  6 Related Work

Prior work for trojan detection can be categorized into two different classes
based on their execution phase: (1) offline model inspection methods that aim
to find out whether a model has been compromised, and (2) online input
inspection methods that monitor incoming data to the model to discard/correct
samples that contain the trojan trigger. Below we review the work in each
category in more detail.

Model inspection. Current methods for offline model inspection rely on
reverse-engineering the trigger to confirm whether a model has been trojaned
or not. Neural Cleanse [16] uses a clean subset of data to solve an
optimization problem and extract the potential trojan triggers. It then uses
the $L_{1}$ norm of the generated triggers to decide whether any of them
corresponds to a viable trojan. Follow up work [2] proposes to use a
conditional GAN to replace the clean dataset and improve the runtime. While
these methods achieve good performance on simple triggers, their performance
degrades in face of more complex triggers. Furthermore, the computational
overhead required by reverse-engineering stage hinders their applicability for
users without access to abundant computing resources.

ABS [12] proposes stimulating neurons and studying the model’s behavior to
extract trojan triggers. Building upon the idea of examining internal neurons,
[17] uses adversarial perturbations as well as random noise to identify trojan
signatures. Both of these methods require multiple rounds of forward and
backward propagations that make the detection scheme computationally complex.
Our method is different than the works in this category in that, instead of
reverse engineering the trigger, we study the statistics of the last layer’s
parameters to detect abnormal trojan behavior. This approach enables our
method to be universally applicable complex trojan trigger patterns.

Data Inspection. A line of work in data inspection focus on finding regions of
the input image that potentially contain the trojan trigger. This is done by
using back-propagation to extract the most influential input regions in
classification. Once such regions are extracted, Sentinet [3] applies them on
a set of benign samples and analyzes the model’s change of output to assert if
the found region was a trojan trigger. Februus [5] takes a similar approach to
find trojan regions and later uses GANs to inpaint the trojan trigger and
correct the model’s decision. STRIP [6] suggests that while injecting noise to
benign data significantly varies the predicted class, trojan samples are more
robust to such noise patterns. Therefore, they detect trojans by injecting
multiple intentional noise patterns and observing the model output prediction.
Perhaps the most notable downside of the above works is the heavy computation
overhead of backward propagation that hinders their application in latency-
sensitive online tasks.

Analyzing the statistics of benign input samples and identifying outliers has
also been investigated in contemporary research. Authors of [14] and [1]
propose to apply clustering on latent feature maps to detect trojan samples.
These methods, however, require access to the model’s training dataset
including the trojan samples. Authors of [9] perform sparse recovery to
reconstruct the input data and the latent features to remove the effect of the
trojan trigger from the clean signal.

While the above methods achieve high detection rates for incoming trojan
samples, they are inappropriate for safety critical scenarios where the model
should be tested for security and safety compliance prior to deployment.

##  7 Conclusion

We propose the first trojan detection mechanism that requires no access to any
data, significant computational resources, or specific knowledge about the
type of trojan trigger. By performing analysis only of the parameters of the
final layer of the network it can effectively detect both standard data
poisoning attacks and the TrojanN attack before deployment of the network.
This makes our detection mechanism ideally suited for the users with access to
limited resources and with security sensitive applications who are most
vulnerable to trojan attacks. We hope that the lightweight nature of our
method allows it to be applied in conjunction with more complicated methods to
create more effective, efficient trojan detection mechanisms.

## References

  * [1] Bryant Chen, Wilka Carvalho, Nathalie Baracaldo, Heiko Ludwig, Benjamin Edwards, Taesung Lee, Ian Molloy, and Biplav Srivastava.  Detecting backdoor attacks on deep neural networks by activation clustering.  arXiv preprint arXiv:1811.03728, 2018.
  * [2] Huili Chen, Cheng Fu, Jishen Zhao, and Farinaz Koushanfar.  Deepinspect: A black-box trojan detection and mitigation framework for deep neural networks.  In Proceedings of the 28th International Joint Conference on Artificial Intelligence. AAAI Press, pages 4658–4664, 2019.
  * [3] Edward Chou, Florian Tramèr, Giancarlo Pellegrino, and Dan Boneh.  Sentinet: Detecting physical attacks against deep learning systems.  arXiv preprint arXiv:1812.00292, 2018.
  * [4] W. J. Dixon.  Analysis of extreme values.  Ann. Math. Statist., 21(4):488–506, 12 1950.
  * [5] Bao Gia Doan, Ehsan Abbasnejad, and Damith C Ranasinghe.  Februus: Input purification defence against trojan attacks on deep neural network systems.  2019\.
  * [6] Yansong Gao, Change Xu, Derui Wang, Shiping Chen, Damith C Ranasinghe, and Surya Nepal.  Strip: A defence against trojan attacks on deep neural networks.  In Proceedings of the 35th Annual Computer Security Applications Conference, pages 113–125, 2019.
  * [7] Tianyu Gu, Brendan Dolan-Gavitt, and Siddharth Garg.  Badnets: Identifying vulnerabilities in the machine learning model supply chain.  arXiv preprint arXiv:1708.06733, 2017.
  * [8] Gary B. Huang, Manu Ramesh, Tamara Berg, and Erik Learned-Miller.  Labeled faces in the wild: A database for studying face recognition in unconstrained environments.  Technical Report 07-49, University of Massachusetts, Amherst, October 2007\.
  * [9] Mojan Javaheripi, Mohammad Samragh, Gregory Fields, Tara Javidi, and Farinaz Koushanfar.  Cleann: Accelerated trojan shield for embedded neural networks.  In 2020 IEEE/ACM International Conference On Computer Aided Design (ICCAD), pages 1–9. IEEE, 2020.
  * [10] Kiran Karra, Chace Ashcraft, and Neil Fendley.  The trojai software framework: An opensource tool for embedding trojans into deep learning models.  arXiv preprint arXiv:2003.07233, 2020.
  * [11] Gil Levi and Tal Hassner.  Age and gender classification using convolutional neural networks.  In Proceedings of the IEEE conference on computer vision and pattern recognition workshops, pages 34–42, 2015.
  * [12] Yingqi Liu, Wen-Chuan Lee, Guanhong Tao, Shiqing Ma, Yousra Aafer, and Xiangyu Zhang.  Abs: Scanning neural networks for back-doors by artificial brain stimulation.  In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, pages 1265–1282, 2019.
  * [13] Yingqi Liu, Shiqing Ma, Yousra Aafer, Wen-Chuan Lee, Juan Zhai, Weihang Wang, and Xiangyu Zhang.  Trojaning attack on neural networks.  2017\.
  * [14] Shiqing Ma and Yingqi Liu.  Nic: Detecting adversarial samples with neural network invariant checking.  In Proceedings of the 26th Network and Distributed System Security Symposium (NDSS 2019), 2019.
  * [15] Omkar M Parkhi, Andrea Vedaldi, and Andrew Zisserman.  Deep face recognition.  2015\.
  * [16] Bolun Wang, Yuanshun Yao, Shawn Shan, Huiying Li, Bimal Viswanath, Haitao Zheng, and Ben Y Zhao.  Neural cleanse: Identifying and mitigating backdoor attacks in neural networks.  In 2019 IEEE Symposium on Security and Privacy (SP), pages 707–723. IEEE, 2019.
  * [17] Ren Wang.  Practical detection of trojan neural networks: Data-limited and data-free cases.


# Prioritizing emergency evacuations under
compounding levels of uncertainty

Lisa J. Einstein1, Robert J. Moss1, Mykel J. Kochenderfer1,2 (1)Department of
Computer Science, (2)Department of Aeronautics and Astronautics
Stanford University, Stanford, California, USA
{lisae, mossr<EMAIL_ADDRESS>
###### Abstract

Well-executed emergency evacuations can save lives and reduce suffering.
However, decision makers struggle to determine optimal evacuation policies
given the chaos, uncertainty, and value judgments inherent in emergency
evacuations. We propose and analyze a decision support tool for pre-crisis
training exercises for teams preparing for civilian evacuations and explore
the tool in the case of the 2021 U.S.-led evacuation from Afghanistan. We use
different classes of Markov decision processes (MDPs) to capture compounding
levels of uncertainty in (1) the priority category of who appears next at the
gate for evacuation, (2) the distribution of priority categories at the
population level, and (3) individuals’ claimed priority category. We compare
the number of people evacuated by priority status under eight heuristic
policies. The optimized MDP policy achieves the best performance compared to
all heuristic baselines. We also show that accounting for the compounding
levels of model uncertainty incurs added complexity without improvement in
policy performance. Useful heuristics can be extracted from the optimized
policies to inform human decision makers. We open-source all tools to
encourage robust dialogue about the trade-offs, limitations, and potential of
integrating algorithms into high-stakes humanitarian decision-making.

###### Index Terms:

emergency evacuation, Markov decision processes, partial observability,
decision support, high-stakes decision making

##  I Introduction

Evacuating people in emergency situations ranging from wars to natural
disasters is a complex challenge that entails optimizing for multiple
competing objectives under immense uncertainty [1, 2]. Doing so effectively
can save lives and reduce suffering. Evacuation problems could be aided by
decision-making algorithms that can account for dynamic sources of uncertainty
while balancing multiple objectives, a task that can be very challenging for
an individual human or even an institution to manage.

We can frame evacuation problems as maximizing some reward, such as saving as
many people as possible or rescuing those most likely to be impacted adversely
by a crisis. Many evacuation problems also deal with the sensitive issue of
prioritizing people when resources are finite. For example, when dispatching
helicopters for medical evacuations in a war zone, military officials can
prioritize requests based on their urgency and the projected number of
casualties instead of on a first-come first-served basis [3].

Markov decision processes (MDP) can generate policies that assist human
decision makers in making optimal sequential decisions while accounting for
limited time and resources. [4, 2]. Partially observable MDPs (POMDPs), MDPs
where the true state is uncertain, can also be useful for modeling dynamic
resource allocation problems such as wildfire management and hospital
admittance [5, 6, 7, 8].

We explore the use of different classes of MDPs to guide optimal decision
making in the specific context of the U.S.-led evacuation from Afghanistan. As
it became clear that the Taliban would seize Afghanistan’s capital in August
2021, the White House tasked the Departments of Defense and State with
evacuating “U.S. Embassy personnel, U.S. citizens, and allied personnel with
whom the U.S. Government has agreements for evacuation” from Afghanistan at a
rate of 5000 per day [9]. This included Afghans eligible for Special Immigrant
Visas (SIVs) due to their contributions to the U.S. effort in Afghanistan.
These decisions became increasingly complex over time. When the Taliban came
into power, tens of thousands of Afghans were at risk of persecution due to
their affiliations or genders and thus also sought evacuation [10]. The United
States ultimately evacuated nearly 124,000 people, making it the largest
noncombatant evacuation operation (NEO) in history [11, 12]. The large crowds
of people and time pressure at the airport made it challenging to decide who
should be let in and put on aircraft [13]. Marines protecting the airport
entrances and consular officers responsible for screening the evacuees had to
quickly decide who to let through gates and who to turn away based on
instructions from the U.S. government and also their own intuition [14].

We model the evacuation problem using different classes of MDPs to capture
compounding levels of uncertainty and solve for optimal or approximately
optimal policies in the case of the U.S. evacuation from Afghanistan. We
compare the number of people evacuated by priority status and aggregate
cumulative reward that was generated by our algorithm with eight heuristic
policies. We demonstrate that an optimized MDP policy outperforms all
heuristic policies (simple rules, such as evacuate all American citizens
first). Results also indicate that accounting for the compounding levels of
uncertainty in the population distribution and uncertainty in the individual
claimed priority status provide little to no added benefit compared to the
optimized MDP policy that accounts only for the uncertainty in who will arrive
at the gate given a known population distribution. We open-source all tools to
encourage robust dialogue about the trade-offs, limitations, and potential of
integrating algorithms into high-stakes decision-making. We target the 2021
Afghanistan evacuation as a demonstration of these techniques, but our
contributions could be generalized to other emergency evacuation efforts.

##  II Methodology

Using a principled mathematical framework for sequential decision making
problems, we can formulate and solve the problem of optimally deciding who to
evacuate from a chaotic central location with access to air transportation but
limited aircraft seats as was the case of the 2021 Afghanistan evacuation. We
formulate the emergency evacuation problem using different classes of Markov
decision processes with varying levels of uncertainty and generate optimal MDP
policies using value iteration [4] and approximately optimal POMDP policies
using the POMCP solver [15].

During the evacuation from Kabul, thousands of people crowded the gates at
Hamid Karzai International Airport (HKIA), from which the U.S government based
its efforts to evacuate people from Afghanistan. Marines guarded the gates and
conducted crowd control, selectively permitting small groups to enter. Further
inside, consular officers conducted more thorough vetting and decided who
could proceed to the airport terminal. The decision-making for the Marines and
consular officers was based on centralized policies, but both had some leeway
in their decisions. As we modeled the interaction, the Marines decided whether
to accept or reject each person based on their priority category, the size of
their family, remaining capacity in the aircraft, and the time left for the
aircraft to depart. We assume that not all families who enter the airport will
board the aircraft.

###  II-A Sequential Problem Formulation

MDPs and POMDPs consist of a state space, action space, transition function,
and reward function. POMDPs also have an observation model that specifies the
probability of making a particular observation given the true state (see fig.
2c). A discount factor $\gamma$ is used to control how myopic the decisions
will be, and in this problem we set $\gamma=1$ so our current decision is
dominated by potential future rewards.

States: We consider a discrete state space $\mathcal{S}$ where an individual
state $s\in\mathcal{S}$. The state $s$ is defined by the following:

  * •

The $c$ remaining seats on the aircraft (maximum of $500$).

  * •

The $t$ time steps remaining before the flight departs (total time of $1200$
steps).

  * •

The family size $f$ of the family aiming to enter the airport to board the
aircraft (ranging from $1$ to $13$).

  * •

The priority category $v$ of the family wanting to enter the airport ($5$
total categories). The categories range in value depending on the family’s
status priority to the U.S. government, shown in table I.

The combination of these values represents a single state $s$ as a vector
$[c,t,f,v]$ with a state space size of $|\mathcal{S}|=40{,}047{,}346$.

The initial state of the MDP has $t$ and $c$ initialized to the total time
remaining and total available seats on the aircraft, respectively. We randomly
generated the family size $f$ and priority status $v$ of the first family and
make the assumption that all family members share the same priority category.

While population estimates were challenging to calculate during the
evacuation, we used values estimated by the Association of Wartime Allies. See
table I for population estimates.

TABLE I:  Population estimates and associated rewards for attempted arrivals
to the airport by claimed status.

Priority Category |  Est. Population* |  Reward
---|---|---
AMCIT1 |  $14786$ |  $100$
SIV2 |  $123000$ |  $25$
P1/P2 Afghan3 |  $604500$ |  $5$
Vulnerable Afghan4 |  $1000000$ |  $1$
ISIS-K5 |  $20$ |  $-500$

  * 1

AMCITS stands for American Citizens.

  * 2

SIV holders performed activities with and for U.S. military personnel.

  * 3

P1/P2 stands for Priority 1 and 2, and includes Afghans and their immediate
family members who may have been at risk due to their U.S. affiliation but who
are not eligible for a Special Immigrant Visa (SIV) [16].

  * 4

Afghans without claims for priority humanitarian parole but who are otherwise
vulnerable due to affiliations.

  * 5

ISIS-K is a terrorist organization based in Afghanistan.

  * *

The method used to estimate the population is described in supplementary
documentation of the code: https://github.com/sisl/EvacuationPOMDP.jl

Actions: Our discrete action space $\mathcal{A}$ accounts for two possible
actions: if the family is ACCEPTED or REJECTED by the Marine who they approach
at the airport gate (which does not necessarily mean they board the aircraft
if they are accepted into the airport).

Transitions: To deal with the uncertainty of transitioning from the airport to
the aircraft, we define the transition function, denoted $T(s^{\prime}\mid
s,a)$, to determine the probability of transitioning to some future state
$s^{\prime}$ when taking action $a$ from state $s$. The aircraft capacity and
the time variables each start at their maximum number of seats available and
total time, respectively. When either reaches zero the problem terminates. If
the family being considered has a size exceeding the current capacity of the
aircraft, we accept up to a single family over capacity and then terminate.
Each future family has a probability of being a certain size $f$ and priority
$v$. If the Marine chooses to ACCEPT a family into the airport, we assume
there is an $80\%$ chance that the family ultimately boards the flight.
However, if the action is REJECT, the family will not make it onto the flight.

Rewards: A reward is associated to each state-action pair, which is denoted
$R(s,a)$. When the action is to REJECT, we give a reward of zero. Otherwise,
when the action is to ACCEPT, the total reward is $fv+\epsilon$, the family
size times the associated priority status reward (see table I) plus a small
value of $\epsilon=10^{-4}$ to settle any ties on the decision boundaries in
favor of ACCEPT. As shown in table I, we define rewards associated with each
priority status based on U.S. priorities expressed in statements and clarified
with government officials. While we recognize the sensitive nature of ranking
humans in order of priority, these were the parameters that decision makers at
the White House had to consider given their limited time and capacity. We do
not assume our model parameters are strictly correct. Our model of the problem
allows for this rank order and associated rewards to be easily changed based
on expert information.

###  II-B Compounding Uncertainty

Figure 1: Compounding levels of uncertainty using different classes of MDPs.
All levels incorporate uncertainty about who will arrive next at the gate.

(a) Family size distribution at the gate. (b) Population distribution of
priority statues.

(c) Claimed priority status models.

Figure 2: Models used in the problem formulation.

We investigate optimal evacuation strategies using four compounding levels of
uncertainty as seen in fig. 1. Subsequent levels include the uncertainties
from the previous levels.

Level I: The problem is modeled as an MDP where we assume full observability
of the population distribution and assume that the claimed status at the gate
is their true priority status. Uncertainty is used in the transition function
that includes (1) the priority status of who we expect to arrive at the gate
next and (2) whether the family accepted into the airport will board the
aircraft.

Level IIa: We make all the same assumptions as level I, but add uncertainty
about the true population distribution. We model level IIa as a POMDP
(technically, a POMDP-lite with the population distribution as the hidden
parameter [17]). We have an estimate of the population distribution in the
beginning (shown in fig. 2b) and then update it as we see people arrive at the
gate. To update the population distribution over time, we use a Dirichlet
distribution as our belief over the true priority statuses. By updating this
distribution, we can converge to the true distribution by the end of the
simulation.

Level IIb: We assume observability in the population distribution, but not in
the observed state of the priority status. In reality, priority status is
never known with total certainty. As an example, Marines and consular officers
had to make priority status judgements based on a wide range of documents
provided by the families, from passports to crumpled papers to emails on
phones to covert symbols. Our claim model incorporates the likelihood that
someone saying they are in a particular priority category actually belongs to
that claimed priority category (shown in fig. 2c). Given the ranked nature of
“priorities”, a particular claimed status of a family has a majority of the
probability mass associated with their true status, while the remainder of the
probability mass is distributed to the right (i.e., claiming higher priority
than the truth, thus increasing the likelihood of getting into the airport).
This is true for all priorities except those belonging to ISIS-K, as it is
unlikely that members of a terrorist organization would disclose their true
category.

We could model level IIb as a POMDP because we have state uncertainty over the
true priority status, but since the belief over the priority status is not
updated based on subsequent observations, we can simplify the problem and
model it as an MDP with an observation-based weighted reward function:

$R(o,a)=\sum_{s\in\mathcal{S}}P(s\mid o)R(s,a)$

where $P(s\mid o)$ is the likelihood of the true state $s$ given the
observation $o$, computed from Bayes’ rule using the probability distributions
in fig. 2c. Formulating this as an MDP means we can solve the problem exactly
for an optimal policy.

Level III:  We assume uncertainty in both the population distribution and
claimed priority status. We combine uncertainties described in levels I, IIa,
and IIb and model the problem as a POMDP for the same reasons as level IIa
(i.e., a requirement on updating the population belief over time).

###  II-C Assumptions

We made a number of assumptions in order to model the evacuation, all of which
can be fine-tuned with increased expert knowledge.

Family size. We modeled family size as a multi-modal distribution using a
mixture of two truncated Gaussian distributions shown in fig. 2a. The first
Gaussian distribution $\mathcal{N}(8,2)$ has a mean and standard deviation
that reflects the average family size in Afghanistan [18]. The second Gaussian
distribution $\mathcal{N}(1,0.6)$ reflects individuals or couples who might
arrive at the gate without their entire family.

Estimated population distribution at airport. We estimated the number of
people at the airport by priority category using numbers calculated by the
Association of Wartime Allies [19] (see fig. 2b). We included these people as
possible arrivals at the gate, though some percentage likely decided to stay
home for safety reasons.

Distribution of ISIS-K, a terrorist organization based in Afghanistan. We
assumed that the likelihood that ISIS-K would arrive at the gate was a low-
probability, high-consequence event. We assumed about $20$ ISIS-K members
circulated the gates attempting to enter the airport.

Priority categories of families. For this exercise, we assumed that immediate
families shared the same priority category and that a person accepted would be
able to bring all family members present with them. During the evacuation,
U.S. officials did try to keep immediate family together to the degree
possible, even if dependents of primary visa holders did not individually hold
the same priority status.

Rewards stay constant. Rewards for varying priority remain constant throughout
the exercise. In reality, as the security situation developed, the rewards
associated with each priority status adapted as well. Problems that include a
reward function that changes over time can be addressed using non-stationary
MDPs [20].

Time remains constant. We assumed that the time horizon was constant and
known. Given the quickly evolving situation during the evacuation, there was
not always certainty about the amount of time U.S. forces would have to
evacuate people.

###  II-D Solution Methods

In the context of MDPs, a policy maps states (or observations) to actions,
thus providing a strategy to look up the recommended action to take given the
current state of the problem. Given that the levels differ in their problem
formulations (i.e., choice of MDP class), we can use different solvers to
optimize policies for each level.

Levels I and IIb, defined as MDPs, can be solved exactly using value iteration
to obtain an optimal policy as an offline look-up table [4]. Level IIb can be
solved exactly because our belief about our claim is not changing over time.
We account for the claims model by updating the reward function to be a
weighted average of the likelihood a family falls into a particular status
multiplied by the reward they would receive for each status.

In both level IIa and level III, we update our population distribution over
time. To optimize our choice of action, we use an online POMDP solver called
POMCP (partially observable Monte-Carlo planning) [15]. We use a max depth of
$120$ and $500$ iterations, which we chose to balance runtime and policy
performance. When optimizing the policies using POMCP, instead of using a
random or heuristic rollout policy to estimate the value of a particular
state-node in the search tree, we use the previously optimized MDP policies to
provide the exact value of a given state, thus greatly reducing the variance
in the state-value estimate.

##  III Experiments

We generate 1000 static state-observation trajectories to provide each policy
with comparable settings under which to be evaluated. Static trajectories
include the state observed by the Marine and the actual state of the person.
We generate the 1000 trajectories by sampling from the Dirichlet distribution
in fig. 2b, so the population distribution we sample from in simulation is
different each time. We run 1000 different simulations given the same observed
state and then aggregate the cumulative reward of that policy used on the 1000
simulations. Each policy is shown the observed state and never the true state
so we can compare the performance in a realistic setting (where the Marines
would never know the true state exactly, but would only be able to make
imperfect observations).

We solve for optimized policies integrating each level of uncertainty. The
choice of solver has runtime and performance impacts that may contribute to
the choice of the MDP class when modeling similar problems. We compared the
optimized policies against eight baseline heuristic policies:

  1. 1.

After Threshold AMCITs: Make decisions based on our optimized MDP policy until
there are 200 time steps remaining. Then, accept American citizens only.

  2. 2.

Before Threshold AMCITs: Accept only American citizens until there are 200
time steps left and then make decisions based on the optimized MDP policy.

  3. 3.

AMCITS: Only accept American citizens.

  4. 4.

SIV and AMCITs: Accept only American citizens or Special Immigrant Visa (SIV)
applicants.

  5. 5.

SIV, AMCITs, and P1P2s: Accept only American citizens, Special Immigrant Visa
(SIV), or Priority 1/2 applicants.

  6. 6.

Non-ISIS-K: Accept everyone except ISIS-K members. Note that given the claims
models, there is a very low probability that an actual ISIS-K member will
claim their true category.

  7. 7.

Accept All: Accept anyone who comes to the door.

  8. 8.

Random: Randomly accept or reject whoever arrives at the door with equal
probability.

We built upon code from the POMDPs.jl framework [21] written in the Julia
programming language and have open-sourced all of the code including the
evacuation modeling tools, simulators, and
policies.111https://github.com/sisl/EvacuationPOMDP.jl

##  IV Results

TABLE II: Experiment Results

Policy | Reward | Airport Accepted/Total$\dagger$ | AMCIT* | SIV* | P1/P2* | Afghan* | ISIS-K*
---|---|---|---|---|---|---|---
Level I | $12112.97\pm 253.96$ | $(629.50\pm 1.06)/5438.38$ | $41.79/42.35$ | $260.25/377.87$ | $275.05/1895.42$ | $52.41/3122.46$ | $0/0.28$
Level IIa (approx.) | $11003.86\pm 233.69$ | $(630.07\pm 0.98)/5348.84$ | $40.13/40.38$ | $220.03/369.80$ | $280.20/1864.41$ | $89.71/3073.97$ | $0/0.28$
Level IIb | $12120.23\pm 254.28$ | $(629.57\pm 1.06)/5445.13$ | $41.88/42.43$ | $260.23/378.50$ | $274.89/1897.67$ | $52.58/3126.25$ | $0/0.28$
Level III (approx.) | $9664.10\pm 250.84$ | $(630.17\pm 1.02)/5505.53$ | $40.26/43.6$ | $161.85/384.60$ | $291.66/1920.12$ | $136.38/3156.92$ | $0.01/0.28$
AfterThresholdAMCITs | $11401.82\pm 263.34$ | $(542.56\pm 2.55)/5524.68$ | $42.20/42.68$ | $240.58/387.04$ | $226.92/1926.68$ | $32.86/3167.98$ | $0/0.29$
BeforeThresholdAMCITs | $8495.33\pm 347.00$ | $(622.02\pm 1.04)/5638.80$ | $50.66/50.66$ | $67.33/395.93$ | $311.89/1964.45$ | $192.12/3227.47$ | $0.01/0.29$
AMCITs | $5308.43\pm 365.61$ | $(77.80\pm 3.67)/5653.04$ | $51.09/51.09$ | $3.94/397.38$ | $19.53/1970.23$ | $3.24/3234.06$ | $0/0.29$
SIV-AMCITs | $11400.89\pm 230.53$ | $(566.86\pm 3.23)/4598.76$ | $35.57/35.57$ | $264.75/264.75$ | $239.60/1602.52$ | $26.93/2695.75$ | $0/0.17$
SIV-AMCITs-P1P2 | $4906.96\pm 82.13$ | $(627.93\pm 1.11)/1125.44$ | $9.78/9.78$ | $75.39/75.39$ | $375.28/375.28$ | $167.48/664.94$ | $0/0.06$
Non-ISIS-K | $3096.94\pm 55.39$ | $(627.70\pm 1.09)/627.70$ | $5.60/5.60$ | $43.97/43.97$ | $219.45/219.45$ | $358.65/358.65$ | $0.04/0.04$
AcceptAll | $3096.94\pm 55.39$ | $(627.70\pm 1.09)/627.70$ | $5.60/5.60$ | $43.97/43.97$ | $219.45/219.45$ | $358.65/358.65$ | $0.04/0.04$
Random | $3093.61\pm 53.48$ | $(627.42\pm 1.07)/1257.04$ | $5.44/11.59$ | $44.29/87.50$ | $219.34/439.67$ | $358.32/718.22$ | $0.02/0.06$

  * $\dagger$

Total number of people accepted into the airport which could be larger than
the capacity of the aircraft (500) due to the transition probability of $0.8$.

  * *

Claimed status presented to each policy while the true status is recorded in
the metrics.

The MDP formulation is optimal as it accounts for a number of different
factors. The heuristic policies use a rule-based approach to decide who to let
in rather than operating as a function of all the problem variables. The
heuristic policies accept people based on the claimed status, whereas the
various classes of MDPs adapt their output actions based on the time and
capacity remaining (shown in fig. 3), resulting in a higher cumulative reward
(shown in table II).

MDP-generated policies ultimately accept more people across claimed categories
than the heuristic policies and end up with the highest cumulative reward
shown in table II. We evaluated the performance of the policies on the 1000
simulated population sets and calculated the average number of people accepted
by status category and reported the standard error. Figure 5 illustrates
example trajectories of each policy on one simulated population set. All
policies were provided with the claimed status, but the reward is calculated
with respect to the underlying true state. The optimized policies generally
have a higher total number of people accepted. In heuristic policies, the
total number of people accepted is lower than all the optimized polices.

The compounding levels of uncertainty in the MDPs add complexity without
improvement in policy performance. We can see in fig. 4 that level I (in which
we assume we know the rough population distribution and priority status) and
level IIb (in which we assume we know the rough population distribution but
integrate our claims model to model uncertainty in priority status) result in
the highest cumulative rewards and are nearly equal. From this we can see that
accounting for additional uncertainty in the individual status does not
necessarily help the decision makers while involving subjective judgments on
the claims model. This suggests that trusting people’s claims ultimately
enhances the overall success of an evacuation, assuming one puts any value at
all on categories of people who are not AMCITs or SIVs. In addition to not
increasing cumulative reward, models of claimed statuses are very subjective
and use approximate POMDP solvers, which add approximation errors and runtime
overhead.

Our experiments also help us see the limitations of rule-based policies such
as accepting only AMCITs and SIVs. While accepting only AMCITs does result in
the highest number of AMCITs accepted into the airport, the MDP-generated
policy results in over twice as high a reward (shown in table II). Figure 4
shows there are cases where early in the trajectory we get more reward (such
as SIV-AMCITs-P1P2 or Accept All policies) but these heuristic policies are
myopic and underperform the more flexible MDP model over the full time horizon
of the problem.

###  IV-A Extracting heuristics

Useful heuristics regarding how a policy can change with respect to time and
capacity can be extracted from the optimized MDP policy to inform human
decision makers. Examining the MDP policy more closely, illustrated in fig. 3,
we can see the high-level behavior as time (rows) and capacity (columns)
change. When there is full time and capacity (top left plot), SIVs and AMCITs
are the only categories accepted. As time decreases but capacity remains high,
the policy accepts larger family sizes of P1/P2 and vulnerable Afghans. If
time remains high and capacity is low, only AMCITs are prioritized. If both
time and capacity are low, the policy accepts SIVs, AMCITs, and those who
claim P1/P2 status. The policy is not intended to be used in an automated
manner during an emergency, but it can be used as a learning tool for thinking
about how decision making behavior could change with capacity and time.

Figure 3: Actions from the MDP policy when sweeping time and capacity. Note
that green indicates ACCEPT and red indicates REJECT.

##  V Discussion

Sequential decision-making models could be used as a pre-crisis decision
support system to engage military personnel and others involved in evacuations
in reflections on policies for evacuation. High-level officials from the
Department of Defense have called for increased research into human-machine
teaming and interaction and have called for integration of machine learning
and deep learning-enabled applications into exercises, wargames, and tabletop
exercises [22]. The policies developed through sequential decision-making
frameworks can be used as a learning and discussion tool for policymakers in
pre- and post-analysis of planning exercises. For example, in this emergency
setting, policymakers might assume integrating a claim model would result in a
higher cumulative reward. However, even if we include uncertainty in the
individual’s claimed status when calculating the reward for accepting that
person, we achieve about the same reward as in the simpler policy. There are
of course additional security trade-offs inherent in trusting people’s claimed
statuses. These trade-offs could be brought up in a pre-crisis debate, while
including quantitative information on the ways conservative perspectives on
claimed status could reduce the overall number of people saved.

It is worth asking whether such a tool is actually practical for decision
making or whether it (a) tells us strategies we already know or (b) is
irrelevant given the chaos inherent in evacuation situations. Even when we
encode state uncertainty and treat the problem as a POMDP, there is still
significant uncertainty in this multi-dimensional challenge. We believe that
an exercise like the one we describe in this paper could be useful ahead of a
crisis rather than during one. The intelligence community and the military
already model various scenarios ahead of conflicts. We offer this method as an
additional framework that could be used in settings that involve sequential
decision making while balancing multiple objectives. These simulations would
likely spark useful discussions and reflections about trade-offs, even if
real-world policy choices would depend on shifting real-world circumstances.

Figure 4: Aggregate cumulative reward for each policy.

(a) Level I: The policy is provided with the claimed status (in black) and is
unaware of the true status (shown in gray parentheses).

(b) Level IIa: The uncertainty in the population distribution is updated over
time and starts with the prior distribution shown above the left-most node.

(c) Level IIb: The uncertainty in the individual claimed status is used in the
decision making (belief distributions over the statues are shown above each
node).

(d) Level III: Both uncertainties in the population distribution (top row of
plots) and the individual claimed status (second row of plots) are used.

Figure 5: Decisions from a single simulation shown as a trajectory. Observed
(claimed) priority status shown in black text with the true priority status
shown in gray parentheses (hidden). A white “x” inside a node indicates a
mismatch between the claimed and true priority status. The size of each node
indicates the family size at the gate while the color indicates the ACCEPT or
REJECT decision from the policy. The current time $t_{i}$, capacity $c_{i}$,
and reward (in green/red) is shown below each node. The trajectory is split
between the first ten time steps and the final ten time steps to illustrate
the low-level behavior of each policy.

Algorithmic frameworks should be developed and discussed in collaboration with
ethicists and local experts. This project highlights how difficult ethical
decisions arise when values and priorities are assigned to human lives.
Changing the reward assigned to a claimed status changes the number of people
with that status who are accepted and rejected. Likewise, leaders’ decisions
about prioritization of various categories of potential evacuees implicitly
suggest a reward function with values for each category of evacuee. For
example, a policy that an evacuation will only evacuate American citizens can
be optimal only if the reward assigned to all other categories of evacuees is
small, zero, or negative. The use of algorithmic modeling in training decision
makers may mitigate the harmful effects of cognitive biases [23] as they allow
for new levels of transparency about difficult trade-offs implicit in human
decisions [24].

We should be very cautious about fully replacing human decision makers with
algorithms, given the many scenarios in which augmenting human judgement with
algorithms can go wrong. For example, in 2020, Stanford Hospital used an
algorithm to assign which employees would receive the COVID-19 vaccine first
[25]. The algorithm rewarded older ages, which meant the algorithm did not
equitably distribute vaccines to younger residents, even though they worked
more closely with COVID-19 patients. In high-stakes scenarios, algorithms are
best used as decision-support or training tools, informed by diverse experts
and local communities. Careful and critical study before and during the
deployment of algorithmic decision support tools can help avoid unintended
consequences.

##  VI Conclusion

We proposed and demonstrated a principled way to answer the question of how to
best evacuate a large population in a crisis situation, focusing on the 2021
Afghanistan evacuation. We used different classes of Markov decision processes
to capture compounding levels of uncertainty and compared their performance
with eight heuristic policies. We showed that the optimized MDP policy
achieves greater performance than the heuristics. Furthermore, complicating
the model with increased uncertainty does not improve policy performance. Our
insights could be used to enrich pre-crisis policy discussions or in hindsight
analysis, and possibly in human-AI joint-training exercises. We open-sourced
all tools and encourage researchers to build upon and strengthen our methods.

This preliminary work seeds a number of questions to be explored more
thoroughly in future work. How should we handle evacuation cases with multiple
gates or checkpoints? Government officials present during the Afghanistan
evacuation described challenges involving dangerous surges of people at
particular gates. The acceptance rate influenced the flow of people arriving
at a particular gate, which would cause the gates to be closed. Another
question regards how to classify priority status categories. More granular
status categories could also be included in future iterations of this work,
such as Legal Permanent Resident (LPR) status or gender. Finally, we encourage
others to explore the task of integrating such tools into the policymaking
process.

## Acknowledgment

We thank Thomas Billingsley and Wren Elhai for their critical insights. We are
also grateful to Patricia Wei and Lilian Chan for their support on early
conceptualization of the project.

## References

  * [1] Chelsea Sidrane and Mykel J. Kochenderfer  “Closed-Loop Planning for Disaster Evacuation with Stochastic Arrivals”  In _International Conference on Intelligent Transportation Systems (ITSC)_ , 2018, pp. 2544–2549  DOI: 10.1109/ITSC.2018.8569957
  * [2] Sean K. Keneally, Matthew J. Robbins and Brian J. Lunday  “A Markov decision process model for the optimal dispatch of military medical evacuation assets”  In _Health Care Management Science_ 19.2 Springer, 2016, pp. 111–129
  * [3] Aaron J. Rettke, Matthew J. Robbins and Brian J. Lunday  “Approximate dynamic programming for the dispatch of military medical evacuation assets”  In _European Journal of Operational Research_ 254.3 Elsevier, 2016, pp. 824–839
  * [4] Mykel J Kochenderfer  “Decision Making under Uncertainty: Theory and Application”  MIT Press, 2015
  * [5] Tina Diao et al.  “Uncertainty Aware Wildfire Management”  In _AI for Social Good Workshop, AAAI Fall Symposium Series_ , 2020
  * [6] Dimitris Bertsimas et al.  “A comparison of Monte Carlo tree search and rolling horizon optimization for large-scale dynamic resource allocation problems”  In _European Journal of Operational Research_ 263.2, 2017, pp. 664–678  DOI: https://doi.org/10.1016/j.ejor.2017.05.032
  * [7] J. Griffith et al.  “Automated Dynamic Resource Allocation for Wildfire Suppression”  In _Lincoln Laboratory Journal_ 22.2, 2017
  * [8] Hyun-Rok Lee and Taesik Lee  “Multi-agent reinforcement learning algorithm to solve a partially-observable multi-agent problem in disaster response”  In _European Journal of Operational Research_ 291.1 Elsevier, 2021, pp. 296–308
  * [9] National Security Council  “Summary of Conclusions for Meeting of the Deputies Small Group”, https://www.documentcloud.org/documents/21195411-afghanistan-memo?responsive=1&title=1, 2021
  * [10] The UN Refugee Agency  “UNHCR warns Afghanistan’s conflict taking the heaviest toll on displaced women and children”, https://www.unhcr.org/en-us/news/briefing/2021/8/611617c55/unhcr-warns-afghanistans-conflict-taking-heaviest-toll-displaced-women.html, 2021
  * [11] Secretary of State Antony Blinken  “Antony Blinken Opening Statement: Testimony on Afghanistan Exit”, https://www.c-span.org/video/?514505-1/secretary-blinken-afghanistan-withdrawal-inherited-deadline-not-inherit-plan, 2021
  * [12] Jim Garamone  “Military phase of evacuation ends, as does America’s longest war”, https://www.army.mil/article/249864/military_phase_of_evacuation_ends_as_does_americas_longest_war, 2021
  * [13] James P. DeHart  “The Apocalyptic Airport Scene”  In _The Foreign Service Journal_ The American Foreign Service Association, 2022, pp. 30–32
  * [14] “Q&A: H.R. McMaster and the Hoover Afghan Relief Team (HART) Describe Their Work to Help Afghans in Wake of Taliban Takeover”  In _News & Press Releases_ The Hoover Institute, https://www.hoover.org/news/qa-hr-mcmaster-and-hoover-afghan-relief-team-hart-describe-their-work-help-afghans-wake-taliban, 2021
  * [15] David Silver and Joel Veness  “Monte-Carlo Planning in Large POMDPs”  In _International Conference on Neural Information Processing Systems_ , 2010, pp. 2164–2172
  * [16] “U.S. Refugee Admissions Program Priority 2 Designation for Afghan Nationals”, https://www.state.gov/u-s-refugee-admissions-program-priority-2-designation-for-afghan-nationals/, 2021
  * [17] Min Chen, Emilio Frazzoli, David Hsu and Wee Sun Lee  “POMDP-lite for robust robot planning under uncertainty”  In _IEEE International Conference on Robotics and Automation (ICRA)_ , 2016, pp. 5427–5433  DOI: 10.1109/ICRA.2016.7487754
  * [18] “2021 World Population Data”  In _PRB_ , https://www.prb.org/international/indicator/hh-size-av/map/country/, 2021
  * [19] Association of Wartime Allies  “Afghan Allies Population Estimate”, https://drive.google.com/file/d/1NXtSlu0_A38Vj9d7w4hcLizv4f0kFVOg/view, 2021
  * [20] Erwan Lecarpentier and Emmanuel Rachelson  “Non-stationary Markov decision processes, a worst-case approach using model-based reinforcement learning”  In _Advances in Neural Information Processing Systems (NeurIPS)_ 32, 2019
  * [21] Maxim Egorov et al.  “POMDPs.jl: A Framework for Sequential Decision Making under Uncertainty”  In _Journal of Machine Learning Research_ 18.26, 2017, pp. 1–5  URL: http://jmlr.org/papers/v18/16-300.html
  * [22] M Flournoy, Avril Haines and Gabrielle Chefitz  “Building Trust Through Testing”  In _Center for Security and Emerging Technology_ , 2020
  * [23] Cass R. Sunstein  “Algorithms, Correcting Biases”  In _Social Research: An International Quarterly_ 86.2 Johns Hopkins University Press, 2019, pp. 499–511
  * [24] Jon Kleinberg, Jens Ludwig, Sendhil Mullainathan and Cass R. Sunstein  “Discrimination in the Age of Algorithms”  In _Journal of Legal Analysis_ 10 Oxford Academic, 2018, pp. 113–174
  * [25] Guo Eileen and Karen Hao  “This is the Stanford Vaccine Algorithm That Left out Frontline Doctors”  In _Technology Review_ , https://www.technologyreview.com/2020/12/21/1015303/stanford-vaccine-algorithm/, 2020