# How to Steer Your Adversary: Targeted and Efficient
Model Stealing Defenses with Gradient Redirection

Mantas Mazeika  Bo Li  David Forsyth

###### Abstract

Model stealing attacks present a dilemma for public machine learning APIs. To
protect financial investments, companies may be forced to withhold important
information about their models that could facilitate theft, including
uncertainty estimates and prediction explanations. This compromise is harmful
not only to users but also to external transparency. Model stealing defenses
seek to resolve this dilemma by making models harder to steal while preserving
utility for benign users. However, existing defenses have poor performance in
practice, either requiring enormous computational overheads or severe utility
trade-offs. To meet these challenges, we present a new approach to model
stealing defenses called gradient redirection. At the core of our approach is
a provably optimal, efficient algorithm for steering an adversary’s training
updates in a targeted manner. Combined with improvements to surrogate networks
and a novel coordinated defense strategy, our gradient redirection defense,
called $\text{GRAD}{}^{2}$, achieves small utility trade-offs and low
computational overhead, outperforming the best prior defenses. Moreover, we
demonstrate how gradient redirection enables reprogramming the adversary with
arbitrary behavior, which we hope will foster work on new avenues of defense.

Machine Learning, ICML

Figure 1:  High-profile prediction APIs such as the OpenAI API and AI21 Studio
truncate posteriors. This serves as a rudimentary defense against model
stealing attacks, protecting financial investments. However, it also has
significant trade-offs. Namely, it harms benign users who might otherwise
benefit from the withheld predictions, and it reduces transparency.

##  1 Introduction

As deep neural networks become more capable and economically valuable,
responsibly democratizing access to the best available models could lead to
widespread social good. Owners may not wish to just publish parameters, as
this opens the door to malicious use and provides no direct return on
investment (Radford et al., 2019; Buchanan et al., 2021). Prediction APIs have
emerged as a solution to these problems, as they enable filtering out harmful
use cases and support a software-as-a-service business model. Moreover, they
allow users with minimal computational resources to access the largest
available models at reasonable costs.

The promise of prediction APIs is hampered by the fact that they are
vulnerable to model stealing attacks. Malicious users can clone the
functionality of an API by gathering a dataset of queries and responses and
training their own model. This allows them to circumvent the expensive process
of manual data curation, which can be a multi-million dollar investment for
API providers (Hendrycks et al., 2021a; Tramèr et al., 2016). Additionally,
model theft can be used as a stepping stone for mounting evasion attacks,
which could result in critical failures in downstream applications using the
API (Papernot et al., 2017). In this paper, we investigate methods for
defending against model stealing attacks.

In practice, prediction APIs often employ rudimentary obfuscation measures,
such as truncating predicted posteriors to a minuscule fraction of their
original size. For instance, the OpenAI API and AI21 Studio truncate to $2\%$
and $0.03\%$ of the available information, respectively. While this can
protect against model stealing, it has major side effects. As illustrated in
Figure 1, truncating posteriors reduces external transparency and harms benign
users who might otherwise benefit from the withheld predictions.

Recent developments in model stealing defenses provide an avenue towards
enabling API providers to share more information about their models without
fear of extraction attacks. The objective of model stealing defenses is to
make models harder to steal without substantially altering posterior
predictions. In recent years, several works have investigated perturbation-
based defenses that seek to maximize adversary error while minimally altering
posteriors. However, these defenses have poor performance in practice, as they
either incur infeasible computational overheads or require large utility
trade-offs to be effective.

To overcome these challenges, we propose a new approach to perturbation-based
model stealing defenses, which we call gradient redirection. At the core of
our approach is an efficient, provably optimal algorithm for steering an
adversary’s training updates. Unlike prior methods, gradient redirection
enables altering the trajectory of an extraction attack in a targeted manner,
enabling a wide range of possible defenses. Using gradient redirection, we
develop an efficient defense called $\text{GRAD}^{2}$ that incorporates
improved surrogate networks and a novel coordinated defense strategy. In
extensive experiments, we find that $\text{GRAD}^{2}$ outperforms prior
defenses across multiple threat models. Moreover, we show how gradient
redirection enables reprogramming the adversary with arbitrary behavior,
including hidden watermarks. Experiment code is available at
https://github.com/mmazeika/model-stealing-defenses.

##  2 Related Work

#### Model Stealing Attacks.

Numerous works have explored the vulnerability of prediction APIs to model
extraction attacks, where the adversary’s goal is to obtain a copycat network
with similar functionality to the prediction API. In early work, Tramèr et al.
(2016) identify a number of threat models and show that extraction of simple
model classes is possible. For deep neural networks, Papernot et al. (2017)
show that model extraction is possible and can facilitate subsequent evasion
attacks. Both these works assume the ability to adaptively probe the API with
optimized queries, which can be accurately detected in some cases by
monitoring query patterns (Juuti et al., 2019; Pal et al., 2020). Thus, we
focus our investigation on the case where adversary queries have no carefully
crafted inputs or sequential structure. By leveraging knowledge distillation
(Hinton et al., 2015), several works have shown that it is possible to steal
the functionality of deep neural networks using weakly related queries
(Orekondy et al., 2019) or even random queries (Krishna et al., 2019),
although attacks with queries more related to the target task typically have
stronger performance.

Figure 2: Compared to the previous state-of-the-art (MAD), gradient
redirection (GR) results in larger perturbations to update gradients for a
model stealing attack. MAD maximizes angular deviations with a heuristic
algorithm (left), and GR minimizes inner product with a provably optimal
algorithm (right). For both metrics, gradient redirection gives substantially
more leverage. Figure 3:  A user submits an image left to a prediction API,
producing posteriors $y$. Our defense outputs an adjusted posterior
$\widetilde{y}$ to prevent a malicious user from stealing the model (red,
right). The adjustment is chosen by an efficient, provably optimal, algorithm
to produce the largest error in a surrogate network’s gradient, which
transfers to the unknown adversary network. Extensive experiments show that
the stolen model has a significant loss in accuracy. Moreover, the benign user
is happy, because the adjustments are guaranteed to be small.

#### Model Stealing Defenses.

Defenses against model stealing fall into two complimentary approaches, which
can be combined in a swiss cheese model to obtain robust protection (Hendrycks
et al., 2021b). The first line of defense attempts to directly thwart model
extraction attempts by returning modified or censored predictions from the API
without significantly reducing performance for benign users. The simplest such
defense is truncating posteriors or only outputting the predicted class
(Tramèr et al., 2016). This defense is used in real prediction APIs, such as
the OpenAI API and AI21 Studio where posterior probabilities are truncated to
the top $2\%$ and $0.03\%$ of values, respectively. Unfortunately, this
reduces utility to benign users, precluding certain applications, and is
harmful to external transparency.

Rather than truncate posteriors, several recent works have investigated
slightly perturbing posteriors to derail extraction attempts. Lee et al.
(2019) introduce ambiguity into clean posteriors, which lowers the accuracy of
the stolen model while preserving the defender’s accuracy. Building on this
intuition, Kariyappa & Qureshi (2020) train a misinformation network to
predict incorrect posteriors. Similarly, Krishna et al. (2019) replace clean
posteriors with harmful posteriors based on how anomalous the query is
(Hendrycks et al., 2018). Note that this defense strategy assumes a setting
where attackers have difficulty obtaining queries close to the defender’s
training distribution, which may not be true in practice.

The prediction poisoning approach introduced by Orekondy et al. (2020)
demonstrates that posteriors can be optimally perturbed to derail the backward
pass of an extraction attack, similar to adversarial examples for the forward
pass (Szegedy et al., 2013). They choose perturbations to poison the
adversary’s update gradient by maximizing angular deviation with the clean
gradient. This results in a strong defense, but it involves computing the full
Jacobian of the network’s posterior, an immense overhead cost that scales with
the number of labels. For some applications, such as language modeling, the
number of labels can be in the tens or hundreds of thousands. This is noted by
Wallace et al. (2020), who focus on machine translation and adopt a best-of-k
sampling procedure for selecting a perturbed prediction to derail the
adversary’s backward pass. However, this workaround still incurs an overhead
of $k$ samples and may lead to a suboptimal defense. Building on these works,
we develop a new approach for optimally redirecting an adversary’s gradient in
a targeted and efficient manner.

#### Watermarking Defenses.

A second overarching approach to model stealing defenses is digital
watermarking. Many works purposefully insert backdoors into networks (Zhang et
al., 2018; Adi et al., 2018), which enable proof of ownership. In the setting
of model stealing, adversaries do not directly access model parameters and may
be able to evade the watermark backdoor queries. Thus, different watermarking
strategies are required to enable identifying models stolen through prediction
APIs. Szyller et al. (2021) extend watermarks to this setting by outputting
incorrect predictions for a small percentage of queried inputs. This enables
the defender to prove ownership by querying the stolen model on these
watermark examples. However, a downside of this defense is that the adversary
knows its own training set, and thus has access to the watermarked inputs. In
our investigation, we find that gradient redirection with strong surrogates
enables black-box reprogramming of the adversary, which can insert watermarks
into stolen models that are completely unknown to the adversary.

##  3 Threat Model

We consider interactions between a single attacker and defender. The defender
allows users to access a deep neural network $g$ through a prediction API, and
the attacker attempts to steal the functionality of the defender’s model
through querying the API and training a clone model $f$ on the resulting
input-output pairs. The attacker’s goal is to obtain high accuracy on the
defender’s test set.

###  3.1 Attacker’s Strategy

The attacker chooses a query $x$ and receives a prediction from the defender’s
network. To avoid detection defenses (Juuti et al., 2019; Chen et al., 2020),
we assume the attacker sends queries that mimic benign queries. That is, we
avoid adaptive querying strategies with unusual temporal structures (Papernot
et al., 2017; Orekondy et al., 2019). In particular, we consider the Knockoff
Nets attack without adaptive querying (Orekondy et al., 2019), which is
similar to knowledge distillation (Hinton et al., 2015) and yields state-of-
the-art attack performance (Orekondy et al., 2020; Kariyappa & Qureshi, 2020).

Knockoff Nets Attack. Let $g$ be the defender’s network, and let $f$ be the
attacker’s clone model parametrized by $\theta\in\mathbb{R}^{d}$. The attacker
chooses a dataset of queries $\mathcal{Q}$ beforehand and sends queries
$x\in\mathcal{Q}$ in random order. Let $y=g(x)$ be the defender network’s
posterior on query $x$. The loss of the adversary’s clone model $f$ on the
example $(x,y)$ is $H(y,f(x))=-\sum_{i}y_{i}\log f(x)_{i}$. The adversary’s
update gradient on this example is the negative gradient of the loss with
respect to the parameters $\theta$. Note that this update gradient can be
written as

$\displaystyle-\nabla_{\theta}H(y,f(x;\theta))$
$\displaystyle=\sum_{i}y_{i}\nabla_{\theta}\log f(x;\theta)_{i}$
$\displaystyle=y^{\intercal}G,$

where $G=\nabla_{\theta}\log f(x;\theta)$ is the $n\times d$ Jacobian matrix
of the log-posteriors of $f$. Through collecting large numbers of queries and
using standard techniques for training deep neural networks, the adversary can
mount a successful extraction attack.

Query Distribution. An important variable in the adversary’s attack is the
choice of query dataset $\mathcal{Q}$. Prior work uses query datasets with
varying levels of similarity to the defender’s training distribution, ranging
from highly similar (Lee et al., 2019; Tramèr et al., 2016) to unrelated
(Orekondy et al., 2020; Kariyappa & Qureshi, 2020). In some cases, collecting
many queries similar to the defender’s training distribution may be easy, and
in other cases it may be challenging. Hence, we consider both possibilities in
our threat model. We refer to adversaries as distribution-aware if they use
queries sharing semantic content with the defender’s training distribution. We
refer to adversaries as knowledge-limited if they use queries with disjoint
semantic content from the defender’s training distribution.

###  3.2 Defender’s Objective

The defender has no access to the adversary’s parameters. Indeed, if the
adversary mimics benign queries then the defender may not even know they are
under attack. Thus, the challenge for the defender is to mitigate model
stealing attempts at all times while preserving the utility of their API for
benign users. This is typically accomplished by returning modified posteriors
that make model stealing hard are representative of the clean posteriors.

A primary measure of utility to benign users is the defender’s classification
error on the test set. However, it is also important to consider the overall
modification to returned posteriors, as benign users can derive substantial
value from guarantees that the perturbed posteriors are close to the clean
posterior. That is, a perturbed posterior $\widetilde{y}$ should satisfy
$\|\widetilde{y}-y\|_{1}\leq\epsilon$, where $y$ is the clean posterior and
$\epsilon$ is small. A good defense will reduce the accuracy of clone models
while minimally increasing classification error on the test set and $\ell_{1}$
distance to the clean posteriors.

##  4 Approach

A recent insight in the development of model stealing defenses is the notion
of adversarial perturbations to the backward pass (Orekondy et al., 2020;
Wallace et al., 2020). That is, perturbations to the defender’s posterior can
be designed to maximally change the attacker’s update gradient. Unfortunately,
existing methods for computing these perturbations are inefficient, requiring
sample-based approaches or hundreds of backward passes for a single API query.
Additionally, they lack flexibility as model stealing defenses, since they
only seek to maximize angular deviation with the original update gradient.
Here, we describe a new approach that we call gradient redirection, which
pushes the attacker’s update gradient in a target direction and is efficient
to compute.

###  4.1 Gradient Redirection Problem

For simplicity, we start by assuming white-box access to the adversary’s
network $f$. We operationalize the defender’s goal as minimally perturbing the
defender’s posterior $y$ in order to maximally push the adversary’s update
gradient in a target direction $z\in\mathbb{R}^{d}$. For a given distillation
example $(x,y)$, we want to solve the optimization problem

$\displaystyle\max_{\widetilde{y}}\quad$ $\displaystyle\langle
G^{\intercal}\widetilde{y},z\rangle$ (1) s.t.
$\displaystyle\mathbf{1}^{\intercal}\widetilde{y}=1$
$\displaystyle\widetilde{y}\succeq 0$
$\displaystyle\|\widetilde{y}-y\|_{1}\leq\epsilon,$

where $y$, $G=\nabla_{\theta}\log f(x;\theta)$, $z\in\mathbb{R}^{d}$, and
$0\leq\epsilon<2$ are fixed. Typically we also have $y\in\Delta^{n-1}$,
although for proofs we may have $\sum_{i}y_{i}<1$. Note that this is a linear
program, so in theory we could find the optimal $\widetilde{y}$ with
performant LP solvers such as affine scaling variants of Karmarkar’s algorithm
(Adler et al., 1989). However, in real world cases, $n$ may be in the tens of
thousands, requiring upwards of 10GB just to store the constraint matrix for a
single distillation example. As prediction APIs often handle high volumes of
queries, solving this optimization problem with existing methods would be far
too costly in practice.

Algorithm 1 Gradient Redirection

Input: $G$, $z$, $y$, $\epsilon$

Output: $\widetilde{y}$

$\widetilde{y}\leftarrow y$

$s\leftarrow\operatorname{argsort}(Gz)$

$\widetilde{y}_{s_{n}}\leftarrow\min\\!\left(y_{s_{n}}+\epsilon/2,\,1\right)$

$\lambda\leftarrow 0$

$t\leftarrow 1$

while $t<n$ do

$\widetilde{y}_{s_{t}}\leftarrow\max\\!\left(y_{s_{t}}-(\epsilon/2-\lambda),\,0\right)$

if $y_{s_{t}}-(\epsilon/2-\lambda)>0$ then

Return $\widetilde{y}$

end if

$\lambda\leftarrow\lambda+y_{s_{t}}$

$t\leftarrow t+1$

end while

Figure 4:  For most defense budgets, $\text{GRAD}^{2}$ induces higher
classification error in the adversary than the best prior methods. While
Reverse Sigmoid is efficient in terms of classification error, this
performance requires an unreasonably large $\ell_{1}$ perturbation budget,
which renders the defense unusable in practice. By contrast, $\text{GRAD}^{2}$
has strong performance on both budget metrics.

###  4.2 Gradient Redirection Algorithm

We propose an efficient and provably optimal algorithm to solve the gradient
redirection problem. First, we note that our problem is structurally similar
to the fractional knapsack problem, which is solved in linearithmic time by a
greedy algorithm (Dantzig, 2016). Drawing from this connection, we propose a
knapsack-like greedy algorithm for solving gradient redirection in Algorithm
1. The inner product objective (2) can be rewritten as
$\widetilde{y}^{\intercal}Gz$, where $Gz\in\mathbb{R}^{n}$ can be interpreted
as a value vector.

Our algorithm initializes $\widetilde{y}$ as $y$. It then proceeds by taking
probability mass from indices of $Gz$ with low values and putting as much mass
as possible in the index of $Gz$ with the highest value. Intuitively, we are
trading off less valuable indices for more valuable indices while taking care
to respect the simplex constraint at each step. Our algorithm has two stopping
conditions. In the first case, $\widetilde{y}_{s_{n}}$ attains
$y_{s_{n}}+\epsilon/2$. This means that we added $\epsilon/2$ probability mass
to $\widetilde{y}_{s_{n}}$. Hence, we removed $\epsilon/2$ probability mass
from other indices of $\widetilde{y}$, so
$\left|\widetilde{y}-y\right|_{1}=\epsilon$, i.e. we hit the budget
constraint. In the second case, we have $\widetilde{y}_{s_{n}}=1$, i.e. we hit
the simplex constraint. In both cases, we have moved as much mass as possible
from the least valuable indices into the most valuable index.

######  Theorem 4.1.

Given a gradient redirection problem $(G,z,y,\epsilon)$ as formulated in (2),
Algorithm 1 outputs a globally optimal solution in
$\mathcal{O}\\!\left(n\log(n)\right)$ time.

The proof follows the common practice for greedy algorithms of establishing
the greedy choice property and optimal substructure for a hierarchy of
subproblems. The theorem then follows by induction. Please see the
Supplementary Material for a full proof.

Computing $Gz$ With Double Backprop. Algorithm 1 is fast for individual
distillation examples $(x,y)$. However, it assumes that we are given
$G=\nabla_{\theta}\log f(x;\theta)$, which itself requires $n$ backward passes
through $f$ to compute. In model stealing defenses, $f$ represents a neural
network, potentially with millions of parameters. Hence, directly computing
$G$ is impractical. To obtain an optimal $\widetilde{y}$ when starting from
the raw $(x,y)$ pair, we need a way to circumvent this computational
bottleneck.

We solve this problem with double backpropagation. Note that $G$ is only used
in Algorithm 1 to compute the matrix-vector product $Gz$, which is the
gradient with respect to $\widetilde{y}$ of $\langle
G^{\intercal}\widetilde{y},z\rangle$. We know $G^{\intercal}\widetilde{y}$ is
the gradient of a cross-entropy loss with respect to $\theta$, since we have
$G^{\intercal}\widetilde{y}=\sum_{i}\widetilde{y}_{i}\nabla_{\theta}\log
f(x;\theta)_{i}=-\nabla_{\theta}H(\widetilde{y},f(x;\theta))$. Thus,
$G^{\intercal}\widetilde{y}$ can be computed with a single backward pass, and
$Gz$ can be computed as
$-\nabla_{\widetilde{y}}z^{\intercal}\nabla_{\theta}H(\widetilde{y},f(x;\theta))$
by backpropagating through the computation graph representing the first
backward pass, a procedure known as double backpropagation that is supported
in many machine learning frameworks. We denote the composition of our gradient
redirection algorithm with double backprop as $\text{GR}(f,x,y,z,\epsilon)$
for network $f$, query $x$, clean posterior $y$, target direction $z$, and
perturbation budget $\epsilon$. The cost of computing $Gz$ with double
backpropagation is roughly comparable to three additional forward passes on
top of computing the output $f(x;\theta)$ (one for the first backward pass $+$
two for double backprop), rather than $n$ additional forward passes, as would
be necessary when directly computing $G$.

| ImageNet-C10 $\to$ CIFAR-10 | ImageNet-C100 $\to$ CIFAR-100 | ImageNet-CUB200 $\to$ CUB200
---|---|---|---
|  $\Delta$ Clf. Err |  $\ell_{1}$ Distance |  $\Delta$ Clf. Err |  $\ell_{1}$ Distance |  $\Delta$ Clf. Err |  $\ell_{1}$ Distance
Method |  1 |  2 |  5 |  0.1 |  0.2 |  0.5 |  1 |  2 |  5 |  0.1 |  0.2 |  0.5 |  1 |  2 |  5 |  0.1 |  0.2 |  0.5
Random |  9.8 |  10.3 |  10.6 |  9.0 |  8.7 |  9.3 |  38.5 |  38.6 |  39.8 |  36.2 |  36.5 |  38.5 |  48.5 |  51.4 |  56.0 |  41.3 |  42.3 |  50.7
Reverse Sigmoid |  - |  - |  - |  9.0 |  9.1 |  9.3 |  - |  - |  - |  36.3 |  36.8 |  38.0 |  - |  - |  - |  41.2 |  42.6 |  45.9
Adaptive Mis. |  10.4 |  11.9 |  16.3 |  9.0 |  9.6 |  12.1 |  38.2 |  40.6 |  46.6 |  36.4 |  37.4 |  41.8 |  53.8 |  58.6 |  66.8 |  42.8 |  45.6 |  53.8
MAD |  12.6 |  16.4 |  22.6 |  8.7 |  8.7 |  9.5 |  43.0 |  46.8 |  49.2 |  35.9 |  36.9 |  42.6 |  49.6 |  52.3 |  56.0 |  41.7 |  42.6 |  51.7
$\text{GRAD}^{2}$ (Ours) |  16.4 |  21.5 |  23.4 |  9.5 |  10.1 |  15.5 |  43.4 |  47.6 |  53.0 |  36.5 |  37.7 |  44.1 |  54.1 |  56.4 |  60.7 |  41.8 |  44.6 |  55.6
Table 1: For distribution-aware adversaries, $\text{GRAD}^{2}$ increases the
adversary’s classification error more than state-of-the-art baselines for
nearly all budgets and test conditions. All values aside from $\ell_{1}$
budgets are percentages. For fair comparison, dashes indicate cases where the
$\ell_{1}$ Distance metric is untenable; see text. Bold is best and underline
is second-best.

###  4.3 Model Stealing Defense

We present a new model stealing defense called the Gradient Redirection
Adversarial Distillation Defense, abbreviated GRAD2. Our defense is based on
the gradient redirection algorithm. However, since the attacker’s network is
unknown to the defender, we cannot directly apply the algorithm. Thus, we
represent the adversary with a surrogate network $h$ and design optimal
perturbations for $h$ instead.

Improved Surrogate Networks. Although prior works have used surrogate networks
for model stealing defenses (Orekondy et al., 2020; Wallace et al., 2020),
very little is known about how to design good surrogates. In particular, an
important unanswered question is whether perturbations designed for the
surrogate actually transfer to the attacker’s network in the first place. To
fill this gap in understanding, we conduct a detailed analysis of various
design choices for surrogate networks, reporting results in the Appendix. Our
main findings are 1) Perturbations designed for surrogate networks do in fact
transfer to the attacker’s network, 2) We can train the surrogate on the
attacker’s queries to obtain better transfer and a stronger downstream
defense, and 3) Early stopping of surrogate training leads to a stronger
downstream defense. The second finding is a crucial difference between our
surrogates and those in previous work. Namely, we notice that the only
information we have about the adversary is the query set $\mathcal{Q}$. Thus,
to make the surrogate more representative of the adversary, we can train the
surrogate on this data using knowledge distillation from the defender’s
network. In online scenarios, this requires continual learning. For
simplicity, we assume the adversary sends all queries in a batch before
beginning training.

Coordinated Defense. A key advantage of gradient redirection is the freedom of
choosing a target direction $z$. We investigate several choices of $z$ and
discuss their properties. An intuitive choice is
$z=\nabla_{\theta}H(y,h(x;\theta_{h}))$, where the target points opposite to
the clean gradient. This setting of $z$ is similar to the MAD algorithm from
(Orekondy et al., 2020), which finds $\widetilde{y}$ obtaining a high cosine
distance with the clean gradient
$1-\cos\left(\widetilde{y}^{\intercal}G,y^{\intercal}G\right)$. In Figure 2,
we compare this setting of $z$ to the MAD algorithm, finding that even though
gradient redirection optimizes the inner product as opposed to cosine
distance, we outperform MAD on both objectives. When incorporated into a full
defense, perturbations from these defenses on two different examples may point
in opposite directions and cancel out. Hence, we consider the possibility of
coordinating the defense so that perturbations combine constructively rather
than destructively.

The simplest possible coordinated defense uses $z=\mathbf{1}$, which pushes
the attacker’s parameters in the unhelpful direction of the all-ones vector.
Since $z$ is constant and does not depend on $x$, it has the desirable
property of invariance to batching. That is, computing
$\text{GR}(h,x,y,\mathbf{1},\epsilon)$ in parallel on a batch of inputs gives
the same batch of output posteriors whether one obtains $Gz$ via per-example
gradients or the batch gradient. In Figure 9, we show that coordinated
defenses outperform uncoordinated ones.

|  | Attacker Accuracy
---|---|---
Eval Data |  Defender Accuracy |  Knowledge-Limited |  Distribution-Aware
CIFAR-10 |  94.0 |  89.8 |  91.0
CIFAR-100 |  75.0 |  55.5 |  64.5
CUB200 |  81.4 |  58.7 |  59.7
Table 2: Accuracy of the defender’s classifier and stolen classifiers with no
defense applied. Distribution-aware attacks are far more effective than
knowledge-limited attacks and hence are more important to defend against.

Full $\text{GRAD}^{2}$ Method. Our full gradient redirection defense combines
Algorithm 1 with our improved surrogates and coordinated defense strategy.
Namely, we use a surrogate $h$ trained on the adversary’s queries
$\mathcal{Q}$ with early stopping after $E=10$ epochs, and we set
$z=\mathbf{1}$.

| CIFAR-100 $\to$ CIFAR-10 | CIFAR-10 $\to$ CIFAR-100 | Caltech256 $\to$ CUB200
---|---|---|---
|  $\Delta$ Clf. Err |  $\ell_{1}$ Distance |  $\Delta$ Clf. Err |  $\ell_{1}$ Distance |  $\Delta$ Clf. Err |  $\ell_{1}$ Distance
Method |  1 |  2 |  5 |  0.1 |  0.2 |  0.5 |  1 |  2 |  5 |  0.1 |  0.2 |  0.5 |  1 |  2 |  5 |  0.1 |  0.2 |  0.5
Random |  12.2 |  12.8 |  14.0 |  10.4 |  10.5 |  11.1 |  50.9 |  52.1 |  54.5 |  46.5 |  47.8 |  50.6 |  53.8 |  58.1 |  65.1 |  43.1 |  45.2 |  57.1
Reverse Sigmoid |  - |  - |  - |  10.7 |  10.5 |  11.1 |  - |  - |  - |  46.0 |  46.9 |  50.8 |  - |  - |  - |  42.7 |  44.2 |  49.7
Adaptive Mis. |  12.7 |  14.3 |  21.7 |  10.8 |  11.5 |  12.9 |  47.6 |  51.0 |  60.2 |  47.5 |  50.6 |  61.2 |  64.7 |  70.6 |  - |  43.3 |  45.6 |  53.4
MAD |  15.1 |  18.0 |  25.9 |  10.5 |  10.4 |  11.5 |  52.2 |  53.6 |  58.6 |  45.1 |  46.7 |  52.0 |  55.4 |  57.7 |  62.1 |  43.4 |  47.6 |  57.1
$\text{GRAD}^{2}$ (Ours) |  17.5 |  20.5 |  22.4 |  10.6 |  11.7 |  17.0 |  55.2 |  59.3 |  63.7 |  46.3 |  48.0 |  56.8 |  57.9 |  60.7 |  65.2 |  42.5 |  46.1 |  58.3
Table 3: For knowledge-limited adversaries, $\text{GRAD}^{2}$ increases the
adversary’s classification error more than state-of-the-art baselines in most
test conditions. All values aside from $\ell_{1}$ budgets are percentages. For
fair comparison, dashes indicate cases where the $\ell_{1}$ Distance metric is
untenable; see text. Bold is best and underline is second-best.

##  5 Experiments

Datasets. We use three evaluation datasets: CIFAR-10, CIFAR-100, and CUB200
(Krizhevsky et al., 2009; Welinder et al., 2010). For each evaluation dataset,
we explore knowledge-limited and distribution-aware adversaries. The
knowledge-limited query sets for the above evaluation datasets are CIFAR-100,
CIFAR-10, and Caltech-256 respectively (Griffin et al., 2007). For
distribution-aware adversaries, we construct query sets from ImageNet-1K by
manually selecting overlapping classes (Deng et al., 2009). This gives us
ImageNet-C10, ImageNet-C100, and ImageNet-CUB200, which are paired with their
matching evaluation set and contain $183,763$, $161,653$, and $30,000$
examples respectively.

Training. Our experiments have three stages. In the first stage, a defender
network trains on each evaluation dataset. In the second stage, defense
methods generate protected posteriors for each query set and evaluation
dataset at various defense budgets. Finally, adversary networks train on the
protected posteriors. We denote experiments with transfer data $\mathcal{Q}$
and evaluation data $\mathcal{D}$ as $\mathcal{Q}\rightarrow\mathcal{D}$. On
CUB200, we fine-tune ResNet50 networks pre-trained on ImageNet. For other
datasets, we train $40$-$2$ Wide ResNets from scratch. This allows us to gauge
whether pre-training can substantially alter results. All networks are trained
for $50$ epochs using SGD with Nesterov momentum of $0.9$. We use an initial
learning rate of $0.01$ for CUB200 and $0.1$ for other evaluation datasets.
The learning is annealed with a cosine schedule, and we use weight decay of
$5\cdot 10^{-4}$.

Metrics. We evaluate defenses with the adversary’s classification error on the
defender’s test set for a given budget. Following Orekondy et al. (2020), we
use two budget metrics: defender classification error and $\ell_{1}$ distance
between the modified posteriors and the clean posteriors averaged across the
query set. For metrics in the tables, we report the increase in classification
error. We denote these by “$\Delta$ Clf. Err” and “$\ell_{1}$ Distance”
respectively. A high value for either budget metric renders the defender’s
network unusable, so strong defenses will induce large adversary errors for
small values of both budget metrics. Thus, we focus our comparisons on values
of $\Delta$ Clf. Err and $\ell_{1}$ Distance in a realistically acceptable
range of trade-offs.

Figure 5: Gradient redirection enables reprogramming the adversary to predict
a desired class on a hidden watermark image that only the defender knows.
Posterior probabilities on non-target images and labels is lower than for the
target input-output pair.

Baselines. We compare $\text{GRAD}^{2}$ to several baseline defenses. No
Defense: The adversary trains on clean posteriors returned from the API. No
attempt is made at defense. Random: The defender’s posterior is interpolated
with a $1$-hot posterior, where the index of the nonzero entry is selected at
random from all the labels that are different from the argmax prediction of
the clean posterior. Reverse Sigmoid (Lee et al., 2019): The defender’s
posterior is modified with a noninjective analogue of the sigmoid function,
making it challenging for the adversary to exactly recover the clean
posterior. Adaptive Misinformation (AM) (Kariyappa & Qureshi, 2020): An out-
of-distribution (OOD) detector flags anomalous queries as adversarial and
interpolates with posteriors from a misinformation network that misclassifies
the defender’s training set. Note that this method assumes that attacker
queries will be OOD, which is a fundamentally different approach from ours.
However, we can still compare performance. MAD (Orekondy et al., 2020): A
heuristic algorithm is used to find perturbed posteriors where the resulting
perturbed gradient on a surrogate network has high angular deviation with the
clean gradient. The surrogate network is randomly initialized.

###  5.1 Comparing Defenses

We compare defenses at practical values of $\Delta$ Clf Err and $\ell_{1}$
Distance and show the results in Tables 1 and 3. In Figure 4, we visualize
results. For a fairer comparison, tabular results are dashed out if $\ell_{1}$
Distance is greater than $1.0$, a conservatively large value. This is because
the $\Delta$ Clf Err metric can be gamed by simply increasing the temperature
of the posterior, which preserves classification error but destroys
information. When considering both budget metrics, $\text{GRAD}^{2}$ matches
or outperforms the best prior methods in most cases. Additionally, in terms of
raw numbers $\text{GRAD}^{2}$ often outperforms other defenses by a
significant margin. For example, at a classification error budget of $1\%$,
our defense increases the error of an adversary seeking to steal a CIFAR-10
model with ImageNet-C10 queries from $9\%$ to $16.4\%$, a $30\%$ relative
improvement over the next best method.

Balancing Both Budget Metrics. By examining both the classification error and
$\ell_{1}$ budgets of the defender, we see that methods which perform
exceptionally well on one metric can perform very poorly on the other. Namely,
Reverse Sigmoid is accuracy-preserving for a large range of hyperparameters,
resulting in very high adversary error for minuscule increases in
classification error budget. However, its $\ell_{1}$ Distance budget scales
more quickly than all other baselines, indicating that it would not be very
useful in practice. By contrast, $\text{GRAD}^{2}$ has balanced performance on
both budget metrics.

Robustness to Threat Model. We find that varying the threat model assumptions
can significantly affect some defenses. In particular, Adaptive Misinformation
relies on being able to identify queries from adversaries with out-of-
distribution detectors, so it may perform less well if queries are closer to
the defender’s training distribution. Accordingly, the gap between
$\text{GRAD}^{2}$ and AM is larger for the distribution-aware adversaries than
for knowledge-limited adversaries. With a distribution-aware adversary,
$\text{GRAD}^{2}$ is still successful with a small budget, demonstrating
robustness to variations in the threat model.

###  5.2 Reprogramming The Adversary

As we have full control over the target direction $z$ in Algorithm 1, a
natural question is whether gradient redirection can be used for more than
just increasing the adversary’s error. We answer this in the affirmative by
showing that in ideal conditions gradient redirection can reprogram
adversaries to behave in a desired way on watermark images. Importantly,
unlike prior work on watermarking defenses for prediction APIs (Szyller et
al., 2021), we can select our watermark images at will. We are not restricted
to using images that the adversary has sent as queries.

Let $(x_{w},y_{w})$ be an input-output pair that we want the adversary $f$ to
predict. To demonstrate watermarking, we assume ideal conditions with white-
box access to $f$. Let the gradient redirection target be
$z=-\nabla_{\theta}H(y_{w},f(x_{w};\theta))$. This target is updated after
every training step. We experiment with knowledge-limited adversaries on the
CIFAR datasets. For each experiment, we insert a single $(x_{w},y_{w})$
watermark into $f$. We perform each experiment three times with different
randomly-selected $(x_{w},y_{w})$ pairs, where $x_{w}$ is selected from the
defender’s test set, and we average results. In Figure 5, we plot the
posterior probability $f(x_{w})_{y_{w}}$ at various perturbation budgets for
the converged stolen model $f$. We also plot the average value of
$f(x)_{y_{w}}$ when given random inputs $x$ from the test set and $f(x)_{y}$
for random $x$ and $y$. Gradient redirection enables reprogramming the
adversary to have abnormally high posteriors on the watermark input-output
pair.

Figure 6: $\text{GRAD}^{2}$ remains a strong defense even when the adversary
employs countermeasures. Training on the argmax label alone results in a
higher error for the adversary in most settings, demonstrating the robustness
of $\text{GRAD}^{2}$.

###  5.3 Adversary Countermeasures

To evaluate how adversary countermeasures affect our $\text{GRAD}^{2}$
defense, we train knowledge-limited adversaries on CIFAR-10 and CIFAR-100 with
the argmax label of the perturbed posteriors rather than the entire posterior.
In Figure 6, we plot results. We find that adversaries trained with this
countermeasure obtain a higher initial error, although they can preserve
accuracy in the face of more aggressive defenses. $\text{GRAD}^{2}$ remains a
strong defense in the face of this countermeasure, with a higher adversary
error in most cases, demonstrating the robustness of our approach.

##  6 Conclusion

We introduced gradient redirection, a new approach to model stealing defenses
that enables modifying the adversary’s update gradient in a targeted manner.
We presented a provably optimal algorithm to efficiently solve gradient
redirection problems, which we use to construct the $\text{GRAD}^{2}$ model
stealing defense. In experiments, our defense outperformed all prior defenses
and was robust to adversary countermeasures. Moreover, we showed that gradient
redirection can be used to reprogram the adversary in a desired manner, which
we hope will help foster further work on model stealing defenses.

## Acknowledgements

This work is partially supported by NSF grant No.1910100, NSF No.2046726, C3
AI, and the Alfred P. Sloan Foundation.

## References

  * Adi et al. (2018) Adi, Y., Baum, C., Cisse, M., Pinkas, B., and Keshet, J.  Turning your weakness into a strength: Watermarking deep neural networks by backdooring.  In _27th $\\{$USENIX$\\}$ Security Symposium ($\\{$USENIX$\\}$ Security 18)_, pp. 1615–1631, 2018.
  * Adler et al. (1989) Adler, I., Resende, M. G., Veiga, G., and Karmarkar, N.  An implementation of karmarkar’s algorithm for linear programming.  _Mathematical programming_ , 44(1):297–335, 1989\.
  * Buchanan et al. (2021) Buchanan, B., Lohn, A., Musser, M., and Sedova, K.  Truth, lies, and automation.  2021\.
  * Chen et al. (2020) Chen, S., Carlini, N., and Wagner, D.  Stateful detection of black-box adversarial attacks.  In _Proceedings of the 1st ACM Workshop on Security and Privacy on Artificial Intelligence_ , pp. 30–39, 2020.
  * Dantzig (2016) Dantzig, G.  _26\. Discrete-Variable Extremum Problems_.  Princeton University Press, 2016.
  * Deng et al. (2009) Deng, J., Dong, W., Socher, R., Li, L.-J., Li, K., and Fei-Fei, L.  Imagenet: A large-scale hierarchical image database.  In _2009 IEEE conference on computer vision and pattern recognition_ , pp. 248–255. Ieee, 2009.
  * Griffin et al. (2007) Griffin, G., Holub, A., and Perona, P.  Caltech-256 object category dataset.  2007\.
  * Hendrycks et al. (2018) Hendrycks, D., Mazeika, M., and Dietterich, T.  Deep anomaly detection with outlier exposure.  _arXiv preprint arXiv:1812.04606_ , 2018.
  * Hendrycks et al. (2021a) Hendrycks, D., Burns, C., Chen, A., and Ball, S.  Cuad: An expert-annotated nlp dataset for legal contract review.  _NeurIPS_ , 2021a.
  * Hendrycks et al. (2021b) Hendrycks, D., Carlini, N., Schulman, J., and Steinhardt, J.  Unsolved problems in ml safety.  _arXiv preprint arXiv:2109.13916_ , 2021b.
  * Hinton et al. (2015) Hinton, G., Vinyals, O., and Dean, J.  Distilling the knowledge in a neural network.  _arXiv preprint arXiv:1503.02531_ , 2015.
  * Juuti et al. (2019) Juuti, M., Szyller, S., Marchal, S., and Asokan, N.  Prada: Protecting against dnn model stealing attacks.  In _2019 IEEE European Symposium on Security and Privacy (EuroS P)_ , pp. 512–527, 2019.  doi: 10.1109/EuroSP.2019.00044.
  * Kariyappa & Qureshi (2020) Kariyappa, S. and Qureshi, M. K.  Defending against model stealing attacks with adaptive misinformation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 770–778, 2020.
  * Krishna et al. (2019) Krishna, K., Tomar, G. S., Parikh, A. P., Papernot, N., and Iyyer, M.  Thieves on sesame street! model extraction of bert-based apis.  _arXiv preprint arXiv:1910.12366_ , 2019.
  * Krizhevsky et al. (2009) Krizhevsky, A., Hinton, G., et al.  Learning multiple layers of features from tiny images.  2009\.
  * Lee et al. (2019) Lee, T., Edwards, B., Molloy, I., and Su, D.  Defending against neural network model stealing attacks using deceptive perturbations.  In _2019 IEEE Security and Privacy Workshops (SPW)_ , pp. 43–49, 2019.  doi: 10.1109/SPW.2019.00020.
  * Orekondy et al. (2019) Orekondy, T., Schiele, B., and Fritz, M.  Knockoff nets: Stealing functionality of black-box models.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 4954–4963, 2019.
  * Orekondy et al. (2020) Orekondy, T., Schiele, B., and Fritz, M.  Prediction poisoning: Towards defenses against dnn model stealing attacks.  In _ICLR_ , 2020.
  * Pal et al. (2020) Pal, S., Gupta, Y., Shukla, A., Kanade, A., Shevade, S., and Ganapathy, V.  Activethief: Model extraction using active learning and unannotated public data.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pp. 865–872, 2020.
  * Papernot et al. (2017) Papernot, N., McDaniel, P., Goodfellow, I., Jha, S., Celik, Z. B., and Swami, A.  Practical black-box attacks against machine learning.  In _Proceedings of the 2017 ACM on Asia conference on computer and communications security_ , pp. 506–519, 2017.
  * Radford et al. (2019) Radford, A., Wu, J., Amodei, D., Amodei, D., Clark, J., Brundage, M., and Sutskever, I.  Better language models and their implications.  _OpenAI Blog_ , 1:2, 2019.
  * Szegedy et al. (2013) Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I., and Fergus, R.  Intriguing properties of neural networks.  _arXiv preprint arXiv:1312.6199_ , 2013.
  * Szyller et al. (2021) Szyller, S., Atli, B. G., Marchal, S., and Asokan, N.  Dawn: Dynamic adversarial watermarking of neural networks.  In _Proceedings of the 29th ACM International Conference on Multimedia_ , pp. 4417–4425, 2021.
  * Tramèr et al. (2016) Tramèr, F., Zhang, F., Juels, A., Reiter, M. K., and Ristenpart, T.  Stealing machine learning models via prediction apis.  In _25th $\\{$USENIX$\\}$ Security Symposium ($\\{$USENIX$\\}$ Security 16)_, pp. 601–618, 2016.
  * Wallace et al. (2020) Wallace, E., Stern, M., and Song, D.  Imitation attacks and defenses for black-box machine translation systems.  _arXiv preprint arXiv:2004.15015_ , 2020.
  * Welinder et al. (2010) Welinder, P., Branson, S., Mita, T., Wah, C., Schroff, F., Belongie, S., and Perona, P.  Caltech-UCSD Birds 200.  Technical Report CNS-TR-2010-001, California Institute of Technology, 2010\.
  * Zhang et al. (2018) Zhang, J., Gu, Z., Jang, J., Wu, H., Stoecklin, M. P., Huang, H., and Molloy, I.  Protecting intellectual property of deep neural networks with watermarking.  In _Proceedings of the 2018 on Asia Conference on Computer and Communications Security_ , ASIACCS ’18, pp. 159–172, New York, NY, USA, 2018\. Association for Computing Machinery.  ISBN 9781450355766.  doi: 10.1145/3196494.3196550.

##  Appendix A Proving Optimality

###  A.1 Gradient Redirection Problem

For simplicity, we start by assuming white-box access to the adversary’s
network $f$. We operationalize the defender’s goal as minimally perturbing the
defender’s posterior $y$ in order to maximally push the adversary’s update
gradient in a target direction $z\in\mathbb{R}^{d}$. For a given distillation
example $(x,y)$, we want to solve the optimization problem

$\displaystyle\max_{\widetilde{y}}\quad$ $\displaystyle\langle
G^{\intercal}\widetilde{y},z\rangle$ (2) s.t.
$\displaystyle\mathbf{1}^{\intercal}\widetilde{y}=1$
$\displaystyle\widetilde{y}\succeq 0$
$\displaystyle\|\widetilde{y}-y\|_{1}\leq\epsilon,$

where $y$, $G=\nabla_{\theta}\log f(x;\theta)$, $z\in\mathbb{R}^{d}$, and
$0\leq\epsilon<2$ are fixed. Typically we also have $y\in\Delta^{n-1}$,
although for establishing optimal substructure we may have that
$\sum_{i}y_{i}<1$. Note that this is a linear program reminiscent of knapsack
problems.

###  A.2 Gradient Redirection Algorithm

We propose an efficient and provably optimal algorithm to solve the gradient
redirection problem, which we describe in the main paper. First, note that the
inner product objective (2) can be rewritten as $\widetilde{y}^{\intercal}Gz$,
where $Gz\in\mathbb{R}^{n}$ can be interpreted as a value vector. For brevity,
let $c=Gz$, and let $s=\operatorname{argsort}(c)$, i.e. $c_{s_{1}}\leq
c_{s_{2}}\leq\dotsb\leq c_{s_{n}}$.

Our algorithm initializes $\widetilde{y}$ as $y$. It then proceeds by taking
probability mass from indices of $c$ with low values and putting as much mass
as possible in $c_{s_{n}}$, which has the highest value of all dimensions in
$c$. Intuitively, we are trading off less valuable indices for more valuable
indices while taking care to respect the simplex constraint at each step. Our
algorithm has two stopping conditions. In the first case,
$\widetilde{y}_{s_{n}}$ attains $y_{s_{n}}+\epsilon/2$. This means that we
added $\epsilon/2$ probability mass to $\widetilde{y}_{s_{n}}$. Hence, we
removed $\epsilon/2$ probability mass from other indices of $\widetilde{y}$,
so $\left|\widetilde{y}-y\right|_{1}=\epsilon$, i.e. we hit the budget
constraint. In the second case, we have $\widetilde{y}_{s_{n}}=1$, i.e. we hit
the simplex constraint. In both cases, we have moved as much mass as possible
from the least valuable indices into the most valuable index.

######  Lemma A.1 (Greedy Choice Property).

Let $(G,z,y,\epsilon)$ be a gradient redirection problem as formulated in (2),
but with the budget constraint changed to
$\left|\widetilde{y}-y\right|_{1}+\lambda\leq\epsilon$, where
$\lambda=1-\sum_{i}y_{i}$ ($\lambda=0$ in the original problem). Let $y^{*}$
be an optimal solution. Then we must have (a):
$y^{*}_{s_{n}}=\min\\!\left(y_{s_{n}}+\epsilon/2,\,1\right)$ and (b):
$y^{*}_{s_{1}}=\max\\!\left(y_{s_{1}}-(\epsilon/2-\lambda),\,0\right)$.
Furthermore, if $y^{*}_{s_{1}}\neq 0$, then we have (c):
$y^{*}_{s_{t}}=y_{s_{t}}$ for $1<t<n$.

###### Proof.

First we will prove (a). Assume for contradiction that there is an optimal
solution $y^{\circ}$ such that
$y^{\circ}_{s_{n}}\neq\min\\!\left(y_{s_{n}}+\epsilon/2,\,1\right)$. Consider
the first case, where $1\leq y_{s_{n}}+\epsilon/2$. This implies
$y^{\circ}_{s_{n}}<1$. Intuitively, we can find a feasible solution $v$ with
$v_{s_{n}}=1$ that obtains a higher objective value than $y^{\circ}$. Let $v$
be the posterior with $v_{s_{n}}=1$ and $v_{i}=0$ for $i\neq s_{n}$. In the
present case, we have $1-y_{s_{n}}\leq\epsilon/2$, which implies
$\left|v-y\right|_{1}+\lambda=(1-y_{s_{n}})+\sum_{1\leq
t<n}y_{s_{t}}+(1-\sum_{i}y_{i})=2(1-y_{s_{n}})\leq\epsilon$. Thus, $v$ is a
feasible solution. Since $y^{\circ}$ and $v$ both sum to $1$, we know $v$ has
a higher objective value than $y^{\circ}$, which is a contradiction.

Now consider the second case, where $1>y_{s_{n}}+\epsilon/2$. This implies
$y^{\circ}_{s_{n}}<y_{s_{n}}+\epsilon/2<1$. Intuitively, we can find a
feasible solution $v$ that obtains a higher objective value than $y^{\circ}$
by moving mass into index $s_{n}$. Let $I$ be the indices where
$y^{\circ}_{i}\geq y_{i}$, and let $J$ be the indices where
$y^{\circ}_{j}<y_{j}$. We have
$\left|y^{\circ}-y\right|_{1}+\lambda=(\sum_{i\in
I}y^{\circ}_{i}-y_{i})+(\sum_{j\in
J}y_{j}-y^{\circ}_{j})+1-\sum_{i}y_{i}=1+(\sum_{i\in
I}y^{\circ}_{i}-2y_{i})-\sum_{j\in J}y^{\circ}_{j}=2\sum_{i\in
I}y^{\circ}_{i}-y_{i}$, so we have $\sum_{i\in
I}y^{\circ}_{i}-y_{i}\leq\epsilon/2$. Suppose we have
$\left|y^{\circ}-y\right|_{1}+\lambda<\epsilon$. Then we can just increase
$y^{\circ}_{s_{n}}$ and decrease other entries of $y^{\circ}$ to maintain the
simplex constraint until we hit the budget constraint, which would yield a
solution with a higher objective value. Now suppose we have
$\left|y^{\circ}-y\right|_{1}+\lambda=\epsilon$. This implies $\sum_{i\in
I}y^{\circ}_{i}-y_{i}=\epsilon/2$. In other words, the indices where
$y^{\circ}_{i}>y_{i}$ account for a difference of $\epsilon/2$, but they are
not concentrated in $y^{\circ}_{s_{n}}$ by our assumption. Simply move them to
$y^{\circ}_{s_{n}}$ to obtain another feasible solution with greater objective
value than that of $y^{\circ}$. This is a contradiction for the second case,
so we have proven (a).

Now we will prove (b). In the case where $1\leq y_{s_{n}}+\epsilon/2$, we know
$y^{*}_{s_{n}}=1$ and $y^{*}_{i}=0$ for $i\neq s_{n}$ from part (a). We also
have $y_{s_{1}}-(\epsilon/2-\lambda)<(\sum_{i\neq
s_{n}}y_{i})-\epsilon/2+1-\sum_{i}y_{i}=1-\epsilon/2-y_{s_{n}}<0$, so
$\max\\!\left(y_{s_{1}}-(\epsilon/2-\lambda),\,0\right)=0$, and we know
$y^{*}_{s_{1}}=0$. Hence, (b) is true in the case where $1\leq
y_{s_{n}}+\epsilon/2$.

Now consider the case where $1>y_{s_{n}}+\epsilon/2$. Assume for contradiction
that there is an optimal solution $y^{\circ}$ such that
$y^{\circ}_{s_{1}}\neq\max\\!\left(y_{s_{1}}-(\epsilon/2-\lambda),\,0\right)$.
By (a), we know $y^{\circ}_{s_{n}}=y_{s_{n}}+\epsilon/2$. Let $I$ be the
indices where $y^{\circ}_{i}>y_{i}$, and let $J$ be the indices where
$y^{\circ}_{j}\leq y_{j}$. By analogous argument to that in part (a), we have
$\sum_{i\in I}y^{\circ}_{i}-y_{i}=\epsilon/2$. That is, indices where
$y^{\circ}_{i}>y_{i}$ account for a difference of exactly $\epsilon/2$. But
this means that $s_{n}$ is the only such index, so we have $y^{\circ}_{j}\leq
y_{j}$ for $j\neq s_{n}$. Furthermore, we have
$\left|y^{\circ}-y\right|_{1}+\lambda=(\sum_{i\in
I}y^{\circ}_{i}-y_{i})+(\sum_{j\in
J}y_{j}-y^{\circ}_{j})+\lambda=\epsilon/2+(\sum_{j\in
J}y_{j}-y^{\circ}_{j})+\lambda=\epsilon$, so we have $(\sum_{j\in
J}y_{j}-y^{\circ}_{j})=\epsilon/2-\lambda$. This means that the indices $j\neq
s_{n}$ account for a difference of exactly $\epsilon/2-\lambda$. By
concentrating this difference in $y^{\circ}_{s_{1}}$, we can improve the
objective value while maintaining a feasible solution. If
$y_{s_{1}}-(\epsilon/2-\lambda)\geq 0$, we will be able to concentrate all
this difference into $y^{\circ}_{s_{1}}$, in which case
$y^{\circ}_{s_{t}}=y_{s_{t}}$ for $1<t<n$. If
$y_{s_{1}}-(\epsilon/2-\lambda)<0$, we will not be able to concentrate all of
the difference into $y^{\circ}_{s_{1}}$ due to the nonnegativity constraint.
However, concentrating as much of the difference as possible by setting
$y^{\circ}_{s_{1}}=1$ will still give a feasible solution with an improved
objective value. This is a contradiction, so we have proven (b).

Now we will prove (c). Suppose $y^{*}$ is an optimal solution with
$y^{*}_{s_{1}}\neq 0$. In the proof of part (b), we saw that this only happens
when we have $y_{s_{1}}-(\epsilon/2-\lambda)\geq 0$. Furthermore, in this case
we also have $y^{*}_{s_{t}}=y_{s_{t}}$ for $1<t<n$, because we had to move all
the remaining difference between $y^{*}$ and $y$ (outside of indices $s_{n}$
and $s_{1}$) into decreasing $y^{*}_{s_{1}}$ as much as possible. This proves
(c).

∎

######  Lemma A.2 (Optimal Substructure).

Let $(G,z,y,\epsilon)$ be a gradient redirection problem with the modified
budget constraint from Lemma A.1. Namely,
$\left|\widetilde{y}-y\right|_{1}+\lambda\leq\epsilon$, where
$\lambda=1-\sum_{i}y_{i}$. Let $y^{*}$ be an optimal solution with
$y^{*}_{s_{1}}=0$, and let $s=\operatorname{argsort}(Gz)$. Consider the
subproblem $(G^{\prime},z^{\prime},y^{\prime},\epsilon)$, where $G^{\prime}$
has row $s_{1}$ removed, $z^{\prime}$ and $y^{\prime}$ have index $s_{1}$
removed. Then $y^{*}$ with index $s_{1}$ removed is an optimal solution to the
subproblem. (Note that in the subproblem, $y$ may lie outside the simplex, but
the simplex constraint for $\widetilde{y}$ is unchanged.)

###### Proof.

Let $y^{*}{}^{\prime}$ denote $y^{*}$ with index $s_{1}$ removed. We know
$\lambda^{\prime}=1-\sum_{i}y^{\prime}_{i}=\lambda+y_{s_{1}}$, and we know
$\sum_{i}y_{i}^{*}{}^{\prime}=\sum_{i}y_{i}^{*}=1$. Thus, we have
$\left|y^{*}{}^{\prime}-y^{\prime}\right|_{1}+\lambda^{\prime}=\left|y^{*}-y\right|_{1}-\left|y^{*}_{s_{1}}-y_{s_{1}}\right|+\lambda+y_{s_{1}}=\left|y^{*}-y\right|_{1}+\lambda\leq\epsilon$.
Therefore, $y^{*}{}^{\prime}$ is a feasible solution to the subproblem
$(G^{\prime},z^{\prime},y^{\prime},\epsilon)$. Assume for contradiction that
there is a solution $y^{\circ}$ to the subproblem with a higher objective
value than $y^{*}{}^{\prime}$. Insert $0$ into position $s_{1}$ of $y^{\circ}$
to create a solution to the original problem with the same objective value.
Inserting $0$ into position $s_{1}$ of $y^{*}{}^{\prime}$ also creates a
solution to the original problem with the same objective value. In fact, it
recreates $y^{*}$. But $y^{*}$ is an optimal solution to the original problem,
so its objective value cannot be lower than that of the expanded $y^{\circ}$.
This is a contradiction, so our assumption must be false, which means that
$y^{*}{}^{\prime}$ is optimal for the subproblem. ∎

######  Theorem A.3.

Given a gradient redirection problem $(G,z,y,\epsilon)$ as formulated in (2),
Algorithm 1 outputs a globally optimal solution in
$\mathcal{O}\\!\left(n\log(n)\right)$ time.

###### Proof.

By part (a) of Lemma A.1, we know that the initialization steps of Algorithm 1
set $\widetilde{y}_{s_{n}}$ to the value of the optimal solution. If
$\widetilde{y}_{s_{n}}$ is set to $1$, then the while loop will proceed until
its stopping condition without altering $\widetilde{y}$ at other indices,
returning an optimal $\widetilde{y}$. Now consider the case where
$\widetilde{y}_{s_{n}}$ is set to a value less than $1$, then we know $y$ has
at least $\epsilon/2$ mass at indices other than $s_{n}$. This means
$\lambda+y_{s_{t}}$ will eventually exceed $\epsilon/2$, at which point the
if-then condition will be entered and the algorithm will return.

We proceed by induction, starting where the if-then condition is entered and
continuing backwards through the while loop to the first step. Note that when
the if-then condition is entered, we have just set $\widetilde{y}_{s_{t}}$ to
$y_{s_{t}}-(\epsilon/2-\lambda)$. Let
$(G^{\prime},z^{\prime},y^{\prime},\epsilon)$ be the subproblem with $s_{j}$
indices removed for $j<t$. In this subproblem, $\widetilde{y}_{s_{t}}$ is
replaced by $\widetilde{y}^{\prime}_{s_{1}}$. From part (b) of Lemma A.1, we
know $\widetilde{y}^{\prime}_{s_{1}}$ is set to an optimal value for this
subproblem. Moreover, from part (c) and the early exit step of the algorithm,
we know that the entirety of $\widetilde{y}^{\prime}$ returned at this point
is an optimal solution to the subproblem, not just the values at indices
$s_{1}$ and $s_{n-t}$. This gives us a base case. For the induction step,
assume that $\widetilde{y}^{\prime}$ is optimal at step $t>1$ of the while
loop. We want to show that $\widetilde{y}$ is optimal for the subproblem
$(G,z,y,\epsilon)$ at step $t-1$ of the while loop. By part (b) of Lemma A.1,
we know that $\widetilde{y}^{\prime}_{s_{1}}$ is set to an optimal value in
the previous step of the while loop. By Lemma A.2, we know that simply
appending this value to the optimal solution of the subproblem at step $t$ of
the while loop gives us an optimal solution to the subproblem at step $t-1$.
By induction, the complete $\widetilde{y}$ returned by Algorithm 1 is an
optimal solution to the original gradient redirection problem.

Asymptotically, the most expensive step is the sorting operation. All other
steps are local comparisons and operations on pairs of array elements or
scalars, and hence have $\mathcal{O}\\!\left(n\right)$ time complexity. Thus,
the overall time complexity is $\mathcal{O}\\!\left(n\log(n)\right)$. ∎

##  Appendix B Additional Experiments

In Figures 8 and 9, we analyze the effect of our design choices for the
$\text{GRAD}^{2}$ defense. Namely, we show how the surrogate ability to
transfer to the adversary makes a large difference in downstream performance.
In Figure 9, we plot the performance of a coordinated defense and
uncoordinated defense. These analyses identify ways to build stronger defenses
which future work could build on. Additionally, they highlight the general
importance of surrogate networks and destructive interference, which prior
work did not investigate in detail.

###  B.1 Improved Surrogate Networks

We analyze the effect of design choices for the surrogate network. Namely, we
show how the surrogate network’s ability to transfer to the adversary makes a
large difference in the downstream performance of gradient redirection
defenses. Let $f$ and $h$ be an adversary and surrogate network, respectively.
Let $\theta$ be the parameters of $f$ that the adversary trains during a model
stealing attack. We compute Transfer Performance for the surrogate network $h$
at perturbation budget $\epsilon$ as

$\frac{1}{\left|\mathcal{Q}\right|}\sum_{x\in\mathcal{Q}}\cos\left(\widetilde{y}^{T}\nabla_{\theta}\log
f(x;\theta),z\right)-\cos\left(y^{T}\nabla_{\theta}\log f(x;\theta),z\right)$

where $y$ is the defender model’s output for query $x$, $z$ is the gradient
redirection target, and $\widetilde{y}=\text{GR}(h,x,y,\mathbf{1},\epsilon)$
is the output of gradient redirection on the surrogate network. Transfer
Performance measures the increase in cosine similarity between the perturbed
gradient and the target direction $z$ compared to the negative control of the
cosine similarity between the clean gradient and $z$. Thus, Transfer
Performance greater than zero indicates successful transfer, and values less
than or equal to zero indicate failed transfer. While any gradient redirection
target could be used, we focus on the all-ones target $z=\mathbf{1}$ in this
analysis.

Setup. The surrogate network analysis is in Figure 8. We train surrogates
using the Knockoff Nets objective with the query distribution $\mathcal{Q}$
(sold lines) and the defender’s training distribution $\mathcal{D}$ (dashed
lines). In both cases, we train surrogates for $50$ epochs and perform early
stopping after $E$ epochs, where $E\in\\{0,10,20,30,40\\}$. We then train
three independent adversaries for $50$ epochs each, saving snapshots at each
epoch. We compute Transfer Performance for a surrogate at each epoch of the
adversary’s training, averaging over the three independent adversary training
runs. We also compute the converged adversary’s classification error when
using the surrogates in a $\text{GRAD}^{2}$ defense.

Training Surrogates on the Query Distribution. The only concrete information
the defender has about an adversary is the query distribution. A natural
question is whether we can leverage this information to build a stronger
defense. In the top row of Figure 8, we see that Transfer Performance is
higher for surrogates trained on $\mathcal{Q}$. In the bottom row, we see that
this translates to a stronger downstream defense for trained surrogates. This
suggests that better transfer from the surrogate to the adversary is in fact
valuable for the downstream defense. Note that prior works found that trained
surrogates yield weaker defenses than random surrogates (Orekondy et al.,
2020), which may be an artifact of training the surrogates on $\mathcal{D}$
instead of $\mathcal{Q}$. We show that training on $\mathcal{Q}$ causes
trained surrogates to outperform random surrogates by a significant margin.

Early Stopping of Surrogates. In the top row of Figure 8, we can see that
surrogates that train for longer transfer better to adversaries at later
stages of training, and early stopping of surrogates yields better transfer to
adversaries at the initial stages of training. This provides further evidence
that similarity to the adversary affects transfer and raises the question of
whether early transfer or late transfer is more advantageous for a downstream
defense. For both CIFAR-10 and CIFAR-100, we find that early stopping at
$E=10$ epochs yields the strongest defense in most cases, while values of
$E\in\\{20,30,40\\}$ perform similarly. This suggests that early transfer is
more important than late transfer.

###  B.2 Runtime Comparison

In Table 4, we compare the runtime of MAD and $\text{GRAD}^{2}$ on queries
from CIFAR-10, CIFAR-100, and CUB200. We report the number of seconds to
generate a perturbed posterior averaged across the test set. In all cases,
$\text{GRAD}^{2}$ is substantially faster, and relative performance scales
with the number of labels; $\text{GRAD}^{2}$ is $3.75\times$ faster on
CIFAR-10, $4.32\times$ faster on CIFAR-100, and $6.33\times$ faster on CUB200.

Figure 7: Posterior perturbations designed for a particular surrogate remain
effective when the adversary uses a different network architecture.

###  B.3 Robustness Across Architectures

An important practical consideration for using gradient redirection defenses
is whether surrogates remain effective if the adversary uses a different
neural network architecture than the surrogate. In Figure 7, we evaluate
$\text{GRAD}^{2}$ against adversaries using a different architecture than the
standard surrogate used throughout the paper. In particular, we keep the same
WRN-40-2 surrogate and posterior perturbations from the main experiments, but
we change the adversary’s architecture to VGG-16. We find that
$\text{GRAD}^{2}$ remains a strong defense in this setting, with almost no
decrease in slope to the performance profile. This suggests that surrogates do
transfer to different architectures.

Method | CIFAR-10 | CIFAR-100 | CUB200
---|---|---|---
MAD | 0.15 | 1.21 | 2.66
$\text{GRAD}^{2}$ | 0.04 | 0.28 | 0.42
Table 4: Average time in seconds to generate a perturbed posterior for a
single query on an NVIDIA A40 GPU. $\text{GRAD}^{2}$ is significantly faster
than MAD. Figure 8:  Surrogate analysis experiments. Top: Surrogates do
transfer to adversaries with unknown parameters; Surrogates with early
stopping after a small number of epochs transfer better to adversaries early
in their training, whereas surrogates with early stopping after a larger
number of epochs transfer better to adversaries later in their training;
Surrogates trained with the query distribution $\mathcal{Q}$ (solid lines)
transfer more effectively than surrogates trained with the defender’s training
distribution $\mathcal{D}$ (dashed lines); Random surrogates transfer very
poorly (red lines). Bottom: Surrogate transfer matters, as stronger transfer
results in a stronger downstream defense (higher adversary error for a given
$\ell_{1}$ budget); Surrogates with early stopping at low epochs ($E=10$)
yield a stronger downstream defense across datasets (blue lines); Randomly
initialized surrogates (red lines) yield in a relatively weaker downstream
defense, which surrogates trained on $\mathcal{Q}$ outperform. Notably, the
MAD method uses randomly initialized surrogates, which transfer very poorly
and underperform our surrogates trained on $\mathcal{Q}$ with early stopping
at $E=10$, which are used in the $\text{GRAD}^{2}$ defense.  Figure 9: When we
set the gradient redirection target $z$ to the all-ones vector, this results
in a defense that perturbs the adversary in a coordinated manner, providing
that the perturbations transfer from the surrogate to the adversary.
Perturbing away from the clean gradient, i.e. minimizing the inner product,
may result in destructive interference of perturbations across the training
set. Here, we measure the performance of these two choices of $z$, labeled
ALL-ONES and MIN-IP respectively, where MIN-IP corresponds to
$z=\nabla_{\theta}H(y,h(x;\theta_{h}))$ pointing opposite the clean. ALL-ONES
corresponds to $z=\mathbb{1}$, which does not depend on $x$ and thus has a
coordinated effect across training batches. We find that our coordinated
defense outperforms the uncoordinated defense by a substantial margin.


11institutetext: Institute for AI in Medicine, School of Automation, Nanjing
University of Information Science and Technology, Nanjing, China
22institutetext: Institute for AI in Medicine, School of Artificial
Intelligence, Nanjing University of Information Science and Technology,
Nanjing, China 33institutetext: Centre for Computational Imaging and
Simulation Technologies in Biomedicine (CISTIB), School of Computing,
University of Leeds, Leeds, UK 44institutetext: Biomedical Imaging Department,
Leeds Institute for Cardiovascular and Metabolic Medicine (LICAMM), School of
Medicine, University of Leeds, Leeds, UK 55institutetext: Department of
Radiology and Nuclear Medicine, Radboud University Medical Centre, Nijmegen,
The Netherlands 66institutetext: Department of Radiology, Netherlands Cancer
Institute (NKI), Amsterdam, The Netherlands 77institutetext: West China
Hospital of Sichuan University, Chengdu, China 88institutetext: Department of
Cardiovascular Sciences, KU Leuven, Leuven, Belgium 99institutetext:
Department of Electrical Engineering, KU Leuven, Leuven, Belgium
1010institutetext: Alan Turing Institute, London, UK 1111institutetext:
Department of Radiology and Biomedical Research Imaging Center (BRIC),
University of North Carolina, Chapel Hill, USA
1111email<EMAIL_ADDRESS>
# Localizing the Recurrent Laryngeal Nerve via Ultrasound with a Bayesian
Shape Framework

Haoran Dou Haoran Dou and Luyi Han contributed equally to this work.3344 Luyi
Han 556⋆6⋆ Yushuang He 77 Jun Xu 22 Nishant Ravikumar 3344 Ritse Mann 55 6 6
Alejandro F. Frangi 33 4 4 8 8 9 9 10 10 Pew-Thian Yap 1111 Yunzhi Huang(🖂) 11

###### Abstract

Tumor infiltration of the recurrent laryngeal nerve (RLN) is a
contraindication for robotic thyroidectomy and can be difficult to detect via
standard laryngoscopy. Ultrasound (US) is a viable alternative for RLN
detection due to its safety and ability to provide real-time feedback.
However, the tininess of the RLN, with a diameter typically less than 3 mm,
poses significant challenges to the accurate localization of the RLN. In this
work, we propose a knowledge-driven framework for RLN localization, mimicking
the standard approach surgeons take to identify the RLN according to its
surrounding organs. We construct a prior anatomical model based on the
inherent relative spatial relationships between organs. Through Bayesian shape
alignment (BSA), we obtain the candidate coordinates of the center of a region
of interest (ROI) that encloses the RLN. The ROI allows a decreased field of
view for determining the refined centroid of the RLN using a dual-path
identification network, based on multi-scale semantic information.
Experimental results indicate that the proposed method achieves superior hit
rates and substantially smaller distance errors compared with state-of-the-art
methods.

###### Keywords:

Bayesian Shape Alignment Recurrent Laryngeal Nerve Localization in Ultrasound.

##  1 Introduction

Robotic thyroidectomy safely removes low-risk tumors and is preferred by
patients who want a scarless operation with minimal invasiveness [7, 17]. A
complete pre-operative assessment of the surroundings of the thyroid is
critical for accurate surgical planning to prevent unnecessary harm to the
internal jugular vein or the recurrent laryngeal nerve (RLN). Currently,
laryngoscopy is the only method surgeons can rely on to detect whether the RLN
is tumor-infiltrated. However, laryngoscopy determines the RLN indirectly by
assessing the activity of the vocal cords [1]. This approach is therefore
highly inaccurate and can only distinguish RLN abnormality in about $1$–$3\%$
patients [3]. Recent clinical trials have turned to ultrasound (US) as an
alternative method for pre-operative inspection due to its safety and ability
to provide real-time feedback [5].

Figure 1: Ultrasound imaging of bilateral RLNs.

The RLN in the US image is rather tiny relative to organs like the trachea and
thyroid (Fig. 1). Therefore, automatic detection of the RLN from an US image
is a challenging task. Recent studies [6, 15, 18] have demonstrated the
feasibility of segmenting large nerves from US images, i.e., the sciatic nerve
(diameter ranging from 16 to 20 mm [13]) and the median nerve (cross-sectional
area ranging from 6.1 to 10.4 mm2 [10]). These studies propose modifications
to basic segmentation models [12, 4] to improve segmentation accuracy. For
example, van Boxtel et al. [15] investigated the efficacy of a hybrid model on
nerve segmentation in US images. Horng et el. [6] integrated a ConvLSTM block
[11] at the bottom layer of the U-Net to capture long-term spatial
dependencies. Wu et al. [18] employed multi-size kernels and a pyramid
architecture to aggregate features for segmentation. Despite these advances,
localization of the RLN remains challenging since it is tiny with mean
diameter ranging from 1 to 3 mm [16], significantly smaller than the larger
nerves mentioned above.

In this work, we propose a knowledge-driven framework for RLN localization,
mimicking the standard approach surgeons take to identify the RLN according to
its surrounding organs. Our primary contributions are as follows: (1) We
propose the first learning-based framework to identify the RLN from a US image
for pre-operative assessment of contraindication for robotic thyroidectomy;
(2) We introduce Bayesian shape alignment for geometrical constraints,
allowing the utilization of spatial prior knowledge in determining an ROI
enclosing the RLN; (3) We introduce Locate-Net, a dual-path network that uses
both local and global information to refine the localization of the RLN
centroid.

##  2 Methods

Figure 2: Overview of the proposed framework.

Fig. 2 illustrates the proposed framework for identifying the RLN from a US
image using anatomical prior knowledge. Our framework includes three coarse-
to-fine sequential modules: (1) Segmentation module; (2) Bayesian shape
alignment (BSA) module; and (3) Locate-Net module. The segmentation module
obtains the segmentations $\hat{S}$ of organs surrounding the RLN, including
the common carotid arteries (CCA), thyroid, and trachea. These segmentations
form posteriors for the BSA module to infer the candidate coordinates of the
RLN. Finally, Locate-Net refines the RLN centroid using local details and
global contexts based on the patch centered at the inferred candidate
coordinates. Details on the three modules are described in the following
sections.

###  2.1 Bayesian Shape Alignment

To avoid missing the tiny RLN [16] in the midst of significantly larger
structures, we introduce a method based on anatomical prior knowledge for RLN
detection. Clinically, surgeons recognize the RLN based on its surrounding
CCA, thyroid, and trachea [17]. The spatial relationships of these anatomical
structures are typically consistent, but not entirely identical, across
individuals. Here, we incorporate the spatial relationship into the Bayesian
inference with the following mathematical model for a given image $I$:

$q(\text{RLN},\text{SO}|I)\propto\\\ p(I|\text{RLN},\text{SO})\times
p(\text{RLN}|\text{SO})\times p(\text{SO})$ (1)

where SO is a matrix of pixels of a segmentation image, classifying whether
each pixel belongs to the surrounding organs (CCA, trachea, thyroid); RLN
refers to a set of center points, where each point is specified by a location
vector $(x,y)$ for the image matrix. $p(\text{SO})$ is the prior distribution
of the segmentation maps of the surrounding organs; and
$p(\text{RLN}|\text{SO})$ is the likelihood of the RLN centroid given the
segmented matrix of its surrounding organs. $p(\text{SO})$ and
$p(\text{RLN}|\text{SO})$ depend on the observed cohort and can be taken as
prior knowledge. $p(I|\text{RLN},\text{SO})$ represents the joint likelihood
for the surrounding organs and the RLN’s centroid, and is treated as a
constant; and $q(\text{RLN},\text{SO}|I)$ is the likelihood of the RLN
centroid and the segmented matrix of its surrounding organs given a particular
image $I$.

In Eq. 1, we aim to predict the RLN’s centroid $(x,y)$ given a image $I$ by
obtaining the maximum likelihood probability from the priors. The prior
distributions for both the RLN centroids and its surrounding segmentation
dependent on the given cohort. For each sample $I_{j}$ from training set, the
approximate probability $p_{j}(\text{RLN}|\text{SO})$ and $p_{j}(SO)$ attain
the maximum value when $I_{j}$ is most similar to the given sample $I$. Based
on this, we can infer the likelihood RLN’s centroids from the samples with
similar surrounding segmentation matrix.

####  2.1.1 Prior Distribution for RLN’s Surroundings

Segmenting the organs surrounding the RLN is a prerequisite to determining
$p(\text{SO})$. Here, the widely adopted segmentation model, U-Net [12], is
employed to segment the CCA, thyroid, and trachea from a US image. The
segmentation network takes an US image and outputs the corresponding
segmentation maps of the three organs. It comprises an encoder and decoder
with a skip-connection to forward the feature representations from each stage
of the encoder to the corresponding stage in the decoder. The numbers of
feature maps in the encoder are 64, 128, 256, 512, 1024, and similarly in the
decoder. Each stage in the segmentation network contains two convolution
layers followed by instance normalization [14] and ReLU functions [19]. The
training loss function is composed with a cross-entropy loss and a dice
similarity coefficient (DSC) loss:

$\mathcal{L}_{\text{seg}}=\mathcal{L}_{\text{ce}}(\hat{S},M)+\mathcal{L}_{\text{dsc}}(\hat{S},M)$
(2)

where $\mathcal{L}_{\text{ce}}$ and $\mathcal{L}_{\text{dsc}}$ refer to cross-
entropy loss and DSC loss, respectively.

####  2.1.2 Alignment-based Likelihood

Employing the prior sample $I_{j}$ that is similar in the surrounding masks
with the given image $I_{i}$ to derive the RLN’s centroid can derive higher
likelihood $p(\text{RLN}|\text{SO})$. However, affected by the probe scanning
angles $\theta$, the observations belong to different angle distributions and
can not be directly used to construct the priors of RLN’s surrounding
segmentation, hence, we embed a pre-alignment module to eliminate the
influence of $\theta$. The detailed implementation of the proposed alignment-
based likelihood infer for the RLN is described in Algorithm 1.

Algorithm 1 Bayesian shape alignment during inference

The predicted segmentation mask $\hat{S}_{i}$ for a inference sample, a set of
mask labels $\mathbb{M}=\\{M_{j},j\in\mathbb{N}^{*}\\}$ and RLN labels
$\mathbb{C}=\\{c_{j},j\in\mathbb{N}^{*}\\}$ for the training samples

Candidate coordinate $\mathcal{C}_{i}$ of RLN for $\hat{S}_{i}$

$D[*]=\\{d_{j},j\in\mathbb{N}^{*}\\}$

$C[*]=\\{p_{j},j\in\mathbb{N}^{*}\\}$

for corresponding label $\\{M_{j}$,$c_{j}\\}$ in $\\{\mathbb{M},\mathbb{C}\\}$
do

$\phi_{j}\leftarrow{\rm Affine}(M_{j},\hat{S}_{i})$ $\triangleright$ shape
analysis

$D[j]\leftarrow{\rm Dice}(M_{j}\circ\phi_{j},\hat{S}_{i})$ $\triangleright$
calculate dice metric

$C[j]\leftarrow c_{j}\circ\phi_{j}$ $\triangleright$ transform centroid of RLN

end for

$index\leftarrow{\rm Rank}(D[*])$ $\triangleright$ rank dice in the descending
order

$C_{sort}\leftarrow{\rm Sort}(C[*],index)$ $\triangleright$ sort coordinates
with dice rank

$\mathcal{C}_{i}\leftarrow{\rm AverageTopK}(C_{sort})$ $\triangleright$
average the Top-$k$ candidate coordinates

Algorithm 1 estimates the likelihood RLN’s centroid by searching the similar
samples from the priors. We first align the priors to the common angle
distribution. Taking each predicted mask $\hat{S}_{i}$ as the target
segmentation and every transversed annotation $M_{j}$ in the training dataset
$\mathbb{M}$ as the moving segmentation, the affine transformation matrix
$\phi_{j}$ with 6 degrees of freedom (DOF) can be conducted with the mutual
information as the similarity metric. After such alignment, the Dice ratio
(DSC) between the predicted mask $\hat{S}_{i}$ and each affined segmentation
$M_{j}\circ\phi_{j}$ in the training dataset is calculated as the shape
similarity score. More similar in the surrounding segmentation correspond to
higher likelihood estimation for the entire image and the RLN’s centroid.
Subsequently, we descend the priors depending on the DSC, and average the
RLNs’ candidates with the Top-$k$ DSCs to infer the position of RLN for the
given image $I_{i}$.

###  2.2 Locate-Net

The BSA module is followed by a dual-path neural network to further refine the
centroid of the RLN. Based on the candidate center coordinates of the RLN
determined by the BSA module, a global patch with the size of $64\times 64$
and a local patch with the size of $24\times 24$ are cropped from the US image
and jointly fed to the refinement network to provide global and local
information. The features from the global patch contain global semantics to
capture the potential outlier unobserved in the priors. The features from the
local patch provide details to help refine the centroid.

In the refinement network, features from the local and global patches are
separately extracted with two weight-shared sub-networks. Each sub-network
contains three convolutional blocks. After each convolution block, the feature
maps are down-sampled with a factor of 2 via the max-pooling layer. The
detailed composition of each convolutional block is the same with the encoder
in the segmentation network (seen in Section 2.1.1). The outputs of the two
sub-networks are then re-scaled to the same size with a adaptive pyramid
pooling layer [20], and followed with a concatenation layer and two
convolution blocks. The top of the refinement network is three fully connected
layers with the hidden units of 512, 64, 2, so that to predict the refined
centroid of RLN. The regression loss function for training the refinement
network is defined as:

$\mathcal{L}_{\text{reg}}=\sum_{i}\mathcal{L}_{s1}(\hat{c}_{i}-c_{i}),$ (3)

where $\mathcal{L}_{s1}$ is the smoothed $L_{1}$ loss with $\beta$ of 1.0
indexed for the difference of image pixel $(\Delta x,\Delta y)$, $\hat{c}$ and
$c$ denote as the predicted RLN centroid and the ground truth, respectively.

$\mathcal{L}_{s1}(\Delta x,\Delta y)=\begin{cases}\frac{1}{2\beta}({\Delta
x}^{2}+{\Delta y}^{2})&{\left|\Delta x\right|+\left|\Delta
y\right|<2\beta},\\\ \left|\Delta x\right|+\left|\Delta
y\right|-\beta&\textrm{others}.\end{cases}$ (4)

##  3 Experiments

###  3.1 Dataset and Evaluation Metrics

2D ultrasound images were collected with an Aixplorer color Doppler ultrasound
device (Hologic Supersonic imagine, AIX en Provence), equipped with a linear
array probe with a frequency of $4$–$15$ MHz. A total of 465 patients
diagnosed with thyroid cancer by preoperative biopsy and enrolled for
thyroidectomy participated in this study. Each patient has both left and right
scans of the RLN. Each scan contains a variable number of qualified US frames,
ranging from 1 to 4. 325, 46 and 94 subjects were randomly selected for
training, validation, and testing, respectively. All images were resampled to
a common size of $256\times 256$. Manual annotation was contented by three
clinical experts and passed through strict quality control from a senior
expert.

Performance was quantified using the absolute distance error and the hit rate
between the predicted RLN centroid and the ground truth:

$\texttt{Dis}(\hat{c},c)=\|\hat{c}-c\|_{1}$ (5)
$\texttt{Hit}(\hat{c},c)=\begin{cases}1&\hat{c}\subseteq N_{c},\\\
0&\textrm{others},\\\ \end{cases}$ (6)

where $\hat{c}$ and $c$ denote as the predicted RLN centroid and the ground
truth, respectively. $N_{c}$ indicates the neighborhood of $c$ with radius
$r_{\theta}$, which is set to be 15 pixels in this work. Lower distance error
and higher hit rate correspond to better identification performance.

###  3.2 Implementation Details

We implemented our method using PyTorch on the Google Colab platform with an
NVIDIA Tesla P100 GPU. We trained the segmentation network using the Adam
optimizer with an initial learning rate of $3\times 10^{-4}$ and a batch size
of 16 for 100 epochs, taking about 3 hours. The learning rate was decayed
every epoch with a factor of 0.9. The affine matrix in Bayesian shape
alignment was initially computed with the center of mass of the masks and
iteratively refined with the mutual information metric. For the training of
the dual-path refinement network, the learning rate and batch size were set to
$1\times 10^{-3}$ and 16, respectively. The code for the techniques presented
in this study can be found at: https://github.com/wulalago/RLNLocalization

###  3.3 Comparison Baselines

We compared our method with coordinate and heatmap regression methods.
Compared heatmap regression methods include U-Net [12], DeepLab [2], SwinT-H
[8], and ConvNeXt-H [9]. Coordinate regression methods include ResNet-50 [4],
SwinT-C [8], and ConvNeXt-C [9]. The optimal hyper-parameters of all the
baseline methods are obtained based on the grid search strategy. Fig. 3 shows
example cases of the bilateral RLNs given by the the baseline methods. The red
and cyan circles mark the annotated ground truth and the predicted centroid of
the RLN, respectively. Our method predicts the centroids of the bilateral RLNs
with higher accuracy than the baseline methods. Table 1 reports the statistics
of the results given by the methods on the testing dataset. The proposed
method achieves the lowest distance error with the highest hit rate.

Table 1: Statistics of competing methods for the testing dataset. | Methods | Left RLN | Right RLN
---|---|---|---
| Distance ($pix$) | Hit Rate ($\%$) | Distance ($pix$) | Hit Rate ($\%$)
Coord-based | ResNet-50 [4] | 10.9 $\pm$ 9.7 | 77.5 | 12.3 $\pm$ 8.4 | 70.0
SwinT-C [8] | 19.7 $\pm$ 11.8 | 42.3 | 14.4$\pm$ 9.6 | 59.4
ConvNeXt-C [9] | 16.5 $\pm$ 8.2 | 47.3 | 14.0 $\pm$ 9.5 | 62.5
Heatmap-based | U-Net [12] | 29.3 $\pm$ 12.8 | 11.5 | 20.9 $\pm$ 10.5 | 31.9
DeepLab [2] | 17.5 $\pm$ 8.0 | 41.2 | 11.9 $\pm$ 7.1 | 71.3
SwinT-H [8] | 22.7 $\pm$ 13.6 | 30.8 | 20.2 $\pm$ 10.6 | 35.6
ConvNeXt-H [9] | 12.7 $\pm$ 12.1 | 73.1 | 13.1 $\pm$ 8.7 | 64.4
| Proposed | 3.49$\pm$7.53 | 95.6 | 4.55 $\pm$7.61 | 92.5
Figure 3: Example results from competing methods. Table 2: Statistics for different settings based on the testing dataset. Methods | Left RLN | Right RLN
---|---|---
Distance ($pix$) | Hit Rate ($\%$) | Distance ($pix$) | Hit Rate ($\%$)
Initialization | 7.52$\pm$7.65 | 89.0 | 9.70$\pm$7.03 | 84.9
\+ Local information | 4.45$\pm$8.79 | 91.8 | 5.47$\pm$7.90 | 88.7
\+ Global context | 3.58$\pm$7.51 | 94.5 | 4.42$\pm$7.48 | 91.8
\+ Local & global features | 3.49$\pm$7.53 | 95.6 | 4.55 $\pm$7.61 | 92.5

###  3.4 Ablation Study

We compared three types of centroid refinement methodes, including (1)
refinement with local information; (2) refinement with global contextual
information; and (3) refinement with both local and global features. Table 2
reports the distance errors and hit rates for these settings based on the
proposed method. Refinement with local and global information yields the
lowest distance error with the highest hit rate.

##  4 Conclusion

Inspired by the way surgeons to recognize RLN, we developed a prior knowledge
driven framework to automatically identify the tiny RLN from US images. In the
proposed pipeline, we first segment the large organs surrounding RLN as the
conditional prior, and then using the Bayesian shape alignment model to
determine the candidate coordinate close to RLN. Then following the Locate-Net
to refine the centriod of RLN with multi-scales patches to extract the local
information and global context around the RLN. Leveraging the spatial
relationship between RLN and its surrounding organs as the prior constraint,
our model can avoid the tiny RLN being submerged the background. From Tabel 1
and Tabel 2, we can conclude that, any combination of our framework achieves
the superiority in the distance error and hit rate as compared to the recent
coordinate or heatmap regression models.

####  4.0.1 Acknowledgement

This work was supported by the National Natural Science Foundation of China
under Grant No. 62101365 and the startup foundation of Nanjing University of
Information Science and Technology. Haoran Dou was funded by the Royal Academy
of Engineering Chair in Emerging Technologies Scheme (CiET1819/19). Luyi Han
was funded by Chinese Scholarship Council (CSC) scholarship. Alejandro F.
Frangi was funded by the Royal Academy of Engineering (INSILEX CiET1819/19),
Engineering and Physical Sciences Research Council (EPSRC) programs TUSCA
EP/V04799X/1, and the Royal Society Exchange Programme CROSSLINK
IES$\backslash$NSFC$\backslash$201380\. Jun Xu was funded by the National
Natural Science Foundation of China (Nos. U1809205, 62171230, 92159301,
61771249, 91959207, 81871352).

## References

  * [1] Chandrasekhar, S.S., Randolph, G.W., Seidman, M.D., Rosenfeld, R.M., Angelos, P., Barkmeier-Kraemer, J., Benninger, M.S., Blumin, J.H., Dennis, G., Hanks, J.B., Haymart, M.R., Kloos, R.T., Seals, B., Schreibstein, J.M., Thomas, M.A., Waddington, C., Warren, B., Robertson, P.J.: Clinical practice guideline: Improving voice outcomes after thyroid surgery. Otolaryngology-Head and Neck Surgery 148 (2013)
  * [2] Cheng, B., Collins, M.D., Zhu, Y., Liu, T., Huang, T.S., Adam, H., Chen, L.C.: Panoptic-deeplab: A simple, strong, and fast baseline for bottom-up panoptic segmentation. In: Computer Vision and Pattern Recognition (2020)
  * [3] Dionigi, G., Boni, L., Rovera, F., Rausei, S., Castelnuovo, P., Dionigi, R.: Postoperative laryngoscopy in thyroid surgery: proper timing to detect recurrent laryngeal nerve injury. Langenbeck’s Archives of Surgery 395, 327–331 (2010)
  * [4] He, K., Zhang, X., Ren, S., Sun, J.: Deep residual learning for image recognition. In: Computer Vision and Pattern Recognition (2016)
  * [5] He, Y., Li, Z., Yang, Y., Lei, J., Peng, Y.L.: Preoperative visualized ultrasound assessment of the recurrent laryngeal nerve in thyroid cancer surgery: Reliability and risk features by imaging. Cancer management and research 13, 7057–7066 (2021)
  * [6] Horng, M.H., Yang, C.W., Sun, Y.N., Yang, T.H.: Deepnerve: A new convolutional neural network for the localization and segmentation of the median nerve in ultrasound image sequences. Ultrasound in Medicine and Biology 46, 2439–2452 (2020)
  * [7] Lee, J., Chung, W.Y.: Robotic surgery for thyroid disease. European thyroid journal 2, 93–101 (2013)
  * [8] Liu, Z., Lin, Y., Cao, Y., Hu, H., Wei, Y., Zhang, Z., Lin, S., Guo, B.: Swin transformer: Hierarchical vision transformer using shifted windows. arXiv: Computer Vision and Pattern Recognition (2021)
  * [9] Liu, Z., Mao, H., Wu, C.Y., Feichtenhofer, C., Darrell, T., Xie, S.: A convnet for the 2020s. arXiv preprint arXiv:2201.03545 (2022)
  * [10] Meyer, P., Lintingre, P.F., Pesquer, L., Poussange, N., Silvestre, A., Dallaudière, B.: The median nerve at the carpal tunnel … and elsewhere. Journal of the Belgian Society of Radiology 102, 17–17 (2018)
  * [11] Romera-Paredes, B., Torr, P.H.S.: Recurrent instance segmentation (2015)
  * [12] Ronneberger, O., Fischer, P., Brox, T.: U-net: Convolutional networks for biomedical image segmentation. In: International Conference on Medical image computing and computer-assisted intervention. pp. 234–241. Springer (2015)
  * [13] Tiel, R., Filler, A.G.: Nerve injuries of the lower extremity (2011)
  * [14] Ulyanov, D., Vedaldi, A., Lempitsky, V.: Instance normalization: The missing ingredient for fast stylization. arXiv preprint arXiv:1607.08022 (2016)
  * [15] Van Boxtel, J., Vousten, V., Pluim, J., Rad, N.M.: Hybrid deep neural network for brachial plexus nerve segmentation in ultrasound images. In: 2021 29th European Signal Processing Conference (EUSIPCO). pp. 1246–1250. IEEE (2021)
  * [16] Wojtczak, B., Kaliszewski, K., Sutkowski, K., Bolanowski, M., Barczyński, M.: A functional assessment of anatomical variants of the recurrent laryngeal nerve during thyroidectomies using neuromonitoring. Endocrine 59, 82–89 (2018)
  * [17] Wong, K.P., Lang, B.H.H.: Endoscopic thyroidectomy: A literature review and update. Current Surgery Reports 1, 7–15 (2013)
  * [18] Wu, H., Liu, J., Wang, W., Wen, Z., Qin, J.: Region-aware global context modeling for automatic nerve segmentation from ultrasound images. In: National Conference on Artificial Intelligence (2021)
  * [19] Xu, B., Wang, N., Chen, T., Li, M.: Empirical evaluation of rectified activations in convolutional network. arXiv preprint arXiv:1505.00853 (2015)
  * [20] Zhao, H., Shi, J., Qi, X., Wang, X., Jia, J.: Pyramid scene parsing network. In: Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 2881–2890 (2017)