# SPECTRAL REPRESENTATION OF NEUTRINO PROPAGATOR IN MEDIA AND OFF-SHELL SPIN
PROPERTIES

A.E. Kaloshin<EMAIL_ADDRESS>Irkutsk State University, K.
Marx str., 1, 664003, Irkutsk, Russia  Joint Institute for Nuclear Research,
141980, Dubna, Russia  D.M.Voronin<EMAIL_ADDRESS>INR RAS, Moscow
117312, Russia

###### Abstract

We construct a spectral representation of neutrino propagator in matter moving
with constant velocity, or in constant homogenious magnetic field. In both
cases there exists definite 4-axis $z$ of complete polarization, such that
corresponding spin projectos commute with propagator. As a result, all
eigenvalues of propagator and dispersion laws are classified accoding to spin
projection on this axis.

When neutrino propagates through the media (dense matter or magnetic field),
it modifies a standard picture of flavour oscillations [1, 2, 3, 4, 5] and
further studying needs to use methods of quantum field theory, see e.g.
reviews [6, 7, 8]. 00footnotetext: Talk at 19th Lomonosov Conf. on Elem. Part.
Physics (MSU, Moscow, August 22-28, 2019)

Here we discuss a convenient algebraic construction for neutrino propagator in
media: so-called spectral representation (SR). In this form, based on the
eigenvalue problem, a propagator looks as a sum of single poles, accompanied
by orthogonal matrix projectors. This representation was discussed earlier for
dressed fermion propagator [9] and for matrix propagator with mixing of few
fermionic fields [10]. In case of media a new aspect is the existence of some
fixed off-shell 4-axis of complete polarization. It reduces the eigenvalue
problem to the vacuum case, media properties only modify scalar coefficients
in general construction.

To construct SR for inverse propagator S, we need to solve the eigenvalue
problem (it’s better in matrix form, for eigenprogectors $\Pi$)

$S\Pi_{i}=\lambda_{i}\Pi_{i},\ \ \ \Pi_{i}\Pi_{k}=\delta_{ik}\Pi_{k}.$ (1)

After it, S and propagator G can be represented as sums

$S=\sum\lambda_{i}\Pi_{i}\ \ \ \Rightarrow\ \ \
G=S^{-1}=\sum\frac{1}{\lambda_{i}}\Pi_{i}.$ (2)

Poles of propagator are in fact the zeros of eigenvalues $\lambda_{i}$.

In [9] this representation was built for dressed propagator of general form

$S=aI+b\hat{p}+c\gamma^{5}+d\hat{p}\gamma^{5}.$ (3)

Useful technical step was to introduce the $\gamma$-matrix basis ${\cal
P}_{i}$

${\cal P}_{1}=\Lambda^{+},\ \ {\cal P}_{2}=\Lambda^{-},\ \ {\cal
P}_{3}=\Lambda^{+}\gamma^{5},\ \ {\cal
P}_{4}=\Lambda^{-}\gamma^{5},\mbox{where}\
\Lambda^{\pm}=\frac{1}{2}(1\pm\frac{\hat{p}}{W})$ (4)

with simple algebra. Here $\Lambda^{\pm}$ are off-shell projectors and $W$ is
invariant mass $W=\sqrt{p^{2}}$. Basis (4) can be used for decomposition of S
and unknown eigenprojector $\Pi$ and it allows to obtain simple solution of
the eigenvalue problem

$\displaystyle\lambda_{i}=\big{(}S_{1}+S_{2}\pm\sqrt{(S_{1}-S_{2})^{2}+4S_{3}S_{4}}\Big{)}/2~{},\
\ \ \ i=1,2$ $\displaystyle\Pi_{i}=(-1)^{i+1}\Big{(}(S_{2}-\lambda_{i}){\cal
P}_{1}+(S_{1}-\lambda_{i}){\cal P}_{2}-S_{3}{\cal P}_{3}-S_{4}{\cal
P}_{4}\Big{)}/(\lambda_{2}-\lambda_{1}),$ (5)

where $S_{k}$ are coefficients of decomposition of $S$ in the basis (4).

When neutrino propagates through a matter, there exist two 4-vectors: momentum
of particle $p$ and matter velocity $u$, and the most general $\gamma$-matrix
decomposition is

$\displaystyle
S(p,u)=G^{-1}=s_{1}I+s_{2}\hat{p}+s_{3}\hat{u}+s_{4}\sigma^{\mu\nu}p_{\mu}u_{\nu}+$
$\displaystyle+s_{5}i\varepsilon^{\mu\nu\lambda\rho}\sigma^{\mu\nu}u_{\lambda}p_{\rho}+s_{6}\gamma^{5}+s_{7}\hat{p}\gamma^{5}+s_{8}\hat{u}\gamma^{5},$
(6)

where $s_{i}$ are scalar function dependent on invariants.

To solve eigenvalue problem for S, the key moment is related with spin
properties. One can introduce 4-vector $z^{\mu}$, which is a linear
combination of $p$, $u$ and has properties of fermion polarization vector
($z^{\mu}p_{\mu}=0,z^{2}=-1$):

$z^{\mu}=b\ (p^{\mu}(up)-u^{\mu}p^{2}),\ \ \ \ \
b=[p^{2}((up)^{2}-p^{2})]^{-1/2}.$ (7)

Then one can construct (slightly non-standard) the off-shell spin projectors:

$\Sigma^{\pm}=\frac{1}{2}(1\pm\gamma^{5}\hat{z}\hat{n}),~{}~{}~{}\Sigma^{\pm}\Sigma^{\pm}=\Sigma^{\pm},~{}~{}~{}\Sigma^{\pm}\Sigma^{\mp}=0,\
\ \ n^{\mu}=p^{\mu}/W.$ (8)

One can see [11] that $\Sigma^{\pm}$ commute with all $\gamma$-matrices in
decomposition (SPECTRAL REPRESENTATION OF NEUTRINO PROPAGATOR IN MEDIA AND
OFF-SHELL SPIN PROPERTIES). Multiplying the inverse propagator $S(p,u)$
(SPECTRAL REPRESENTATION OF NEUTRINO PROPAGATOR IN MEDIA AND OFF-SHELL SPIN
PROPERTIES) by unit matrix

$S=(\Sigma^{+}(z)+\Sigma^{-}(z))S\equiv S^{+}+S^{-},$ (9)

one obtains two orthogonal contributions $S^{\sigma},\ \sigma=\pm 1$.

One more useful property of $\Sigma^{\sigma}$ is that in $S^{+},S^{-}$ terms
the $\gamma$-matrix structures may be simplified. Namely: $\gamma$-matrices,
which contain the matter velocity $u^{\mu}$ may be transformed to the vacuum
set of four matrices: $I,\hat{p},\gamma^{5},\hat{p}\gamma^{5}$, see [11]. As a
result, matter properties are contained only in scalar coefficients.

It can be seen, that the eigenvalue problem for inverse propagator (SPECTRAL
REPRESENTATION OF NEUTRINO PROPAGATOR IN MEDIA AND OFF-SHELL SPIN PROPERTIES)
is separated into two different problems for $S^{\sigma}$ and these problems
are reduced to vacuum case (4), (SPECTRAL REPRESENTATION OF NEUTRINO
PROPAGATOR IN MEDIA AND OFF-SHELL SPIN PROPERTIES) with modified scalar
coefficients.

The introduced 4-vector $z^{\mu}$ (7) plays role of the complete polarization
axis and all eigenvalues are classified by the projection of spin onto this
axis. In contrast to vacuum, this axis is not arbitrary and axis projection is
not conserved, see details in [11].

In particular case of rest matter, polarization vector $z^{\mu}$ corresponds
to helicity state and spin projection is concerved. In this case the
generalized spin projectors (8) are projectors onto the spatial momentum
direction

$\Sigma^{\pm}=\frac{1}{2}\Big{(}1\pm\bm{\Sigma}\frac{\bf{p}}{|\bf{p}|}\Big{)},~{}~{}~{}\bm{\Sigma}=\gamma^{0}\bm{\gamma}\gamma^{5}.$
(10)

Thus, for rest matter the well-known fact [12, 13] is reproduced that neutrino
with a definite dispersion law in matter has a definite helicity. If some
eigenvalue is vanished $\lambda_{1,2}^{\sigma}=0$, we have the known
dispersion law

$E_{1,2}^{\sigma}=\sigma\alpha\pm\sqrt{(|{\bf{p}}|+\sigma\alpha)^{2}+m^{2}}.$
(11)

We found an axis of complete polarization $z^{\mu}$ (7) in moving matter. A
similar situation arises when neutrino propagates in a magnetic field.

Inverse propagator of neutral fermion with an anomalous magnetic moment $\mu$
in magnetic field is

$S=\hat{p}-m+\mu\bm{\Sigma}{\bf{B}},~{}~{}~{}~{}\bm{\Sigma}=\gamma^{0}\bm{\gamma}\gamma^{5}.$
(12)

Having electromagnetic field tensor and 4-momentum, we can construct a
polarization vector $z^{\mu}$ ($z^{2}=-1$ and $z_{\mu}p^{\mu}=0$):

$z^{\mu}=b\epsilon^{\mu\nu\lambda\rho}F_{\nu\lambda}p_{\rho}\ \ \ \Rightarrow\
\ \ z^{\mu}=b(({\bf{B}}{\bf{p}}),p^{0}{\bf{B}}).$ (13)

Second expression corresponds to external magnetic field and $b=(p_{0}^{2}{\bf
B}^{2}-({\bf{B}}{\bf{p}})^{2})^{-1/2}$. Using this vector, we can construct a
standard spin projector:

$\Sigma^{\pm}=(1\pm\gamma^{5}\hat{z})/2.$ (14)

It is easy to see that the spin projectors commute with the inverse propagator
(12): $[S,\Sigma^{\pm}]=0$.

Further we can apply the same trick that was used in a matter: to obtain two
orthogonal terms $S^{+}$ and $S^{-}$ (9) and to simplify $\gamma$-matrix
structure. Instead of (12) we obtain

$S^{\pm}=\Sigma^{\pm}(z)\Big{[}\hat{p}-m+\frac{\mu}{p^{0}}(\gamma^{5}({\bf{p}}{\bf{B}})\pm\gamma^{0}\frac{1}{b})\Big{]}.$
(15)

The inverse propagator in the external field (12), (15) is non-covariant, but
for algebraic problem this is not so important. At solving of eigenvalue
problem with the matrix (3), the momentum vector $p^{\mu}$ may be changed by
any four numbers. Therefore, if to redefine the vector $p^{\mu}$ in $S^{\pm}$,
we can get rid of $\gamma^{0}$ and use the ready answer (SPECTRAL
REPRESENTATION OF NEUTRINO PROPAGATOR IN MEDIA AND OFF-SHELL SPIN PROPERTIES).

$p_{\pm}^{\mu}=(p^{0}\pm\frac{\mu}{bp_{0}},\ {\bf p}),\ \ \ \ \ \
S^{\pm}=\hat{p}_{\pm}-m+\mu\gamma^{5}\frac{({\bf{B}}{\bf{p}})}{p_{0}}.$ (16)

Now inverse propagator has only $I$, $\hat{p}_{\pm}$ and $\gamma^{5}$ matrix,
and algebraically is similar to the vacuum propagator. Therefore, we can use
the formulas (SPECTRAL REPRESENTATION OF NEUTRINO PROPAGATOR IN MEDIA AND OFF-
SHELL SPIN PROPERTIES) for eigenvalues and eigenprojectors.

If eigenvalue is vanishing, we obtain the well-known dispersion law for
movement of anomalous magnetic moment in magnetic field [14]

$E^{2}=m^{2}+{\bf{p}}^{2}+\mu^{2}{\bf{B}}^{2}\pm
2\mu\sqrt{m^{2}{\bf{B}}^{2}+{\bf{p}}^{2}{\bf{B}}^{2}_{\perp}}.$ (17)

Here $\pm$ corresponds to different terms $S^{\pm}$ in propagator, which are
accompanied by spin projectors $\varSigma^{\pm}$.

So, in constant magnetic field all eigenvalues are classified by the spin
projection on the fixed axis $z$ (13). It turns out that, as in the case of
moving medium, the projection on this axis, in general, is not a conserved
quantity [11].

In summary, we have built the spectral representation (2) of neutrino
propagator in a moving matter or in a constant external magnetic field. The
advantage of this representation is that a single term in this sum is related
only with one dispersion law for particle in media.

It turned out that both in matter and in magnetic field there exists the fixed
4-axis of complete polarization $z^{\mu}$, such that all eigenvalues of
propagator (and, consequently, dispersion laws) are classified accoding to
spin projection onto this axis. The found spin projectors (8), (14) on the
axis of complete polarization play a special role in the eigenvalue problem,
simplifying essentially algebraic calculations.

Note that the found spin projectors in general case do not commute with
Hamiltonian $[\varSigma^{\pm},H]\not=0$. Probably, besides the algebraic
simplicity, this axis generate some dynamical spin effects in media.

## References

  * [1] L. Wolfenstein, Phys. Rev. D 17 (1978) 2369.
  * [2] S. Mikheev, A. Smirnov, Sov. J. Nucl. Phys. 42 (1985) 913.
  * [3] M.B. Voloshin, M.I. Vysotskii, L.B. Okun’, Zh. Eksp. Teor. Fiz. 91 (1986) 754.
  * [4] E. Kh. Akhmedov, Phys. Lett. B 213 (1988) 64.
  * [5] A.E.Lobanov, A.I.Studenikin, Phys. Lett. B 515 (2001) 94.
  * [6] M. Beuthe, Phys. Rept. 375 (2003) 105.
  * [7] C. Giunti, A. Studenikin, Rev. Mod. Phys. 87 (2015) 531.
  * [8] S. Bilenky, Lect. Notes Phys. 947 (2018) 1.
  * [9] A.E. Kaloshin, V.P. Lomov, Eur. Phys. J. C 72 (2012) 2094.
  * [10] A.E. Kaloshin, V.P. Lomov, Int. J. Mod. Phys. A 31 (2016) 1650031.
  * [11] A.E. Kaloshin, D.M. Voronin, Eur.Phys.J. C 79 (2019) 153.
  * [12] P. D. Mannheim, Phys. Rev. D 37 (1988) 1935.
  * [13] J.T. Pantaleone, Phys. Rev. D 46 (1992) 510.
  * [14] I.M. Ternov, V.G. Bagrov, A.M. Khapaev, JETP 21 (1965) 613.


# Finite-State Semi-Markov Channels
for Nanopore Sequencing

Brendon McBain  Emanuele Viterbo  James Saunderson

###### Abstract

Nanopore sequencing is an emerging DNA sequencing technology that has been
proposed for use in DNA storage systems. We propose the noisy nanopore channel
model for nanopore sequencing. This model captures duplications, inter-symbol
interference, and noisy measurements by concatenating an i.i.d. duplication
channel with a finite-state semi-Markov channel. Compared to previous models,
this channel models the dominant distortions of the nanopore while remaining
tractable. Anticipating future coding schemes, we derive MAP detection
algorithms and estimate achievable rates. Given that finite-state semi-Markov
channels are a subclass of channels with memory, we conjecture that the
achievable rate of the noisy nanopore channel can be optimised using a
variation of the generalised Blahut-Arimoto algorithm.

##  I Introduction

Nanopore sequencing [1] has emerged as a promising technology for the
sequencing of deoxyribonucleic acid (DNA), however it is limited by many
distortions imposed by the physics of the sequencer. Thus far, a complete
model of the nanopore sequencer has not been established in the research
community, hence the purpose of this paper is to introduce a model that is
suitable for the future development of codes that enable reliable data storage
in synthetic DNA when using nanopore sequencing for the reading operation [2].

The four molecules adenine ($A$), cytosine ($C$), guanine ($G$) and thymine
($T$), connected to a sugar-phosphate backbone molecule, form the nucleotides
(or bases), which are the primary elements of single-stranded DNA (ssDNA).
Abstractly, we can assume $\\{A,T,C,G\\}$ is the alphabet forming arbitrary
length sequences.

The nanopore is a microscopic pore that holds $\tau$ nucleotides (see Fig. 1)
for a random duration determined by a motor protein that shifts nucleotides
one by one through the nanopore. Meanwhile, an ionic electrical current
flowing through the nanopore is uniquely disturbed by the $\tau$ nucleotides
inside it at any given time, and is sampled by the sequencer at a frequency
$f_{s}$. Measuring the current level through an output function $f$, the
nanopore sequencer estimates the state of the system defined by the $\tau$
bases in the nanopore. Unfortunately, the following distortions reduce the
reliability of detection [3]:

  * Random dwell times (sample duplications): Fluctuations in the motor protein operation results in a random number of samples per nucleotide, since the nucleotide is not being shifted in lockstep with the sampler.

  * Fading: For each nucleotide, the motor is designed to halt for a duration that facilitates the sampling of a constant current level. However, minor variability in the physical dimensions of the nanopores slightly changes this level. This is similar to a variable fading coefficient depending on the nanopore in use.

  * Inter-symbol interference (ISI): Given that the electrical current is disturbed by $\tau$ bases, the detection of a single base is distorted by inter-symbol interference with its neighbours.

  * Noisy measurements: Finally, each sample is distorted by measurement noise.

From experimental data, the authors of [3] additionally observed backsteps
(tandem duplications) and, less frequently, skippings (deletions).

Figure 1: A diagram of the noisy nanopore channel of Definition 1. The
$\ell$-th base in the ssDNA is fed through the nanopore after $K_{\ell}/f_{s}$
seconds, according to the variable “DNA Clock”. Simultaneously, the sampler
samples every $1/f_{s}$ seconds, according to the “Sample Clock” with
frequency $f_{s}$.

Before information-theoretic methods for the nanopore sequencer can be
employed, a tractable channel model that best represents the aforementioned
distortions must be chosen. In this regard, the channel proposed in [4] is the
closest to ours that we have found in the literature, given that it modelled
ISI, fading, and deletions. This channel excluded duplications by assuming a
perfect segmentation algorithm, since any segmentation errors could be
combined with backsteps (tandem-duplications) or deletions, but unfortunately
their channel did not include backsteps to justify this decision.

Simpler channel models have been considered to study distortions in isolation,
including a noiseless nanopore channel [5], a noisy (tandem-)duplication
channel [6], and a memoryless nanopore channel [7]. While these channels
highlight interesting properties of the nanopore, they are incomplete.

In contrast, our approach is based on a finite-state Markov channel (FSMC) [8,
Chapter 4.6] to model ISI and noisy measurements, which we extend to include
duplications. The duplications can be modelled by an i.i.d. duplication
channel, but since sample duplications of a Markov chain result in a semi-
Markov chain (or renewal process), we concatenate it with a finite-state semi-
Markov channel (FSSMC) to form the proposed noisy nanopore channel (NNC). We
do not include fading, since its effect can be modelled as additional
measurement noise, neither do we include deletions, since they can be
eliminated by tuning the sampling rate relative to the speed of the motor
protein.

The primary contribution of this work is establishing a tractable channel that
models the dominant distortions in nanopore sequencing. Secondary
contributions include generalising MAP detection algorithms that have been
important tools for coding schemes of finite-state channels. In particular, we
generalise the forward-backward algorithm for MAP symbol detection, and the
Viterbi algorithm for MAP sequence detection. Aside from detection, the
generalised forward-backward algorithm is used to estimate achievable rates
using analogous methods to [9, 10], which leads us to conjecture that the
generalised Blahut-Arimoto algorithm (GBAA) [9] optimises the Markov source
(and, if the conjecture in [9, 11] is true, is capacity-achieving).

This paper is organised as follows. Section II presents preliminaries on
(hidden) Markov chains and (hidden) semi-Markov chains. Section III introduces
the noisy nanopore channel. Section IV derives the forward-backward algorithm
for MAP symbol detection, and a Viterbi algorithm for MAP sequence detection.
Section V shows how to compute achievable information rates, and highlights
its connection with the generalised Blahut-Arimoto algorithm. Finally, Section
VI presents numerical results of computed achievable rates over different
channel parameters, using a channel mapping derived from the Scrappie
simulator [12].

##  II Preliminaries

###  II-A Hidden Markov chains

A discrete-time stochastic process $(S_{\ell})$ with initial probabilities
$\mu_{0}(i):=\mathbb{P}(S_{0}=i)$ is said to be a Markov chain if its Markov
kernel $P$ satisfies

$\displaystyle P(i,j)$
$\displaystyle:=\mathbb{P}(S_{\ell+1}=j|S_{0},\ldots,S_{\ell}=i)$
$\displaystyle=\mathbb{P}(S_{\ell+1}=j|S_{\ell}=i)$ (1)

for all $i,j\in\mathsf{supp}(S)$ and for all $\ell\in\mathbb{N}$. The chain
$(S_{\ell},Y_{\ell})$ is said to be a hidden Markov chain if $(S_{\ell})$ is a
Markov chain and, for all $\ell\in\mathbb{N}$, it satisfies

$\displaystyle\mathbb{P}(Y_{\ell}|S_{0},\ldots,S_{\ell})$
$\displaystyle=\mathbb{P}(Y_{\ell}|S_{\ell})$ (2)

###  II-B Hidden semi-Markov chains

The discrete-time stochastic process $(S_{\ell},T_{\ell})$ is said to be a
Markov renewal process with jump times $(T_{\ell})$ if, using the
parameterisation $K_{\ell+1}=T_{\ell+1}-T_{\ell}$, its semi-Markov kernel
satisfies [13, Definition 3.2]

$Q(i,j,k):=\\\
\mathbb{P}\bigl{(}S_{\ell+1}=j,K_{\ell+1}=k|S_{0},\ldots,S_{\ell}=i;K_{1},\ldots,K_{\ell}\bigr{)}\\\
=\mathbb{P}\bigl{(}S_{\ell+1}=j,K_{\ell+1}=k|S_{\ell}=i\bigr{)}$ (3)

for all $\ell\in\mathbb{N}$, for all $i,j\in\mathsf{supp}(S)$, and for all
$k\in\mathsf{supp}(K)$. The semi-Markov chain $(Z_{t})$ represents this Markov
renewal chain as $Z_{t}=S_{\ell}\quad\text{if}\quad T_{\ell-1}<t\leq
T_{\ell}$. We note that the main difference between chains
$(S_{\ell},K_{\ell})$ and $(Z_{t})$ is that the former is a tuple of states
and durations, whereas the latter is the actual process that has a defined
state at any given time, but they are equivalent. We will switch between them
whenever it is convenient to do so throughout this work.

A stochastic process $(Z_{t},Y_{t})$ is said to be a hidden semi-Markov chain
if it satisfies [13, Definition 6.1]

$\displaystyle\gamma_{t^{\prime}+1}^{t}(i,j)$
$\displaystyle:=\mathbb{P}\left(Y_{t^{\prime}+1}^{t},Z_{t^{\prime}+1}^{t}=j|Y_{1}^{t^{\prime}};Z_{1},\ldots,Z_{t^{\prime}}=i\right)$
$\displaystyle=Q(i,j,t-t^{\prime})\prod_{r=t^{\prime}+1}^{t}\mathbb{P}(Y_{r}|Z_{r}=j)$
(4)

for all $i,j\in\mathsf{supp}(Z)$ and for all $t^{\prime},t\in\mathsf{supp}(T)$
such that $i\neq j$ and $t^{\prime}<t$. Assume the processes $(Y_{t})$ and
$(K_{\ell})$ are i.i.d. throughout this work.

Our choice of notation is heavily inspired by [14, 13], which gives a more
detailed treatment of (hidden) semi-Markov processes. Refer to the concrete
example in Fig. 2.

ABAB$S_{1}$$S_{2}$$S_{3}$$S_{4}$$P(A,B)$$P(B,A)$$P(A,B)$

ABBAAB$Z_{1}$$Z_{2},Z_{3}$$Z_{4},Z_{5}$$Z_{6}$$Q(A,B,2)$$Q(B,A,2)$$Q(A,B,1)$

1.0-0.9-1.10.951.2-0.8$Y_{1}$$Y_{2},Y_{3}$$Y_{4},Y_{5}$$Y_{6}$$\gamma_{2}^{3}(A,B)$$\gamma_{4}^{5}(B,A)$$\gamma_{6}^{6}(A,B)$

Figure 2: Example realisations of Markov chain $S_{1}^{4}$, semi-Markov chain
$Z_{1}^{6}$, and hidden semi-Markov chain $Y_{1}^{6}$. Each block holds a
realised value of the random variable below it, and the transitions define the
probability of each realisation.

##  III Channel Model

We now propose a channel model for the nanopore sequencer based on the
concatenation of an i.i.d. duplication channel with a FSSMC. The channel will
model random dwell times with i.i.d. duplications, ISI with a finite state-
space, and noisy measurements with additive noise. The following makes the
components of the illustration in Fig. 1 precise.

Noiseless nanopore channel. Let $\Omega=\\{A,T,C,G\\}^{\tau}$ be the state-
space of the nanopore sequencer with memory constraint $\tau\geq 1$. Given a
sequence of bases $b_{1}^{n}$ in $\\{A,T,C,G\\}^{n}$, let us model the
nanopore as a shift register that stores the subsequence
$b_{\ell-\tau-1}^{\ell}=(b_{\ell-\tau-1},b_{\ell-\tau},\ldots,b_{\ell})$ after
$\ell$ bases have been shifted through, where the initial state is some
$(b_{-\tau-1},b_{-\tau},\ldots,b_{0})\in\Omega$. In addition, let these
subsequences induce a mean measurement level by injective mapping
$f:\Omega\rightarrow\mathcal{Y}\subseteq\mathbb{R}$, as defined for the
noiseless nanopore channel in [5].

Noisy nanopore channel. Let $S_{\ell}=b_{\ell-\tau-1}^{\ell}$ be one of
$4^{\tau}$ possible states in $\Omega$, then the subsequent state
$S_{\ell+1}=b_{\ell-\tau}^{\ell+1}$ is only conditionally dependent on
$S_{\ell}$. Hence, the sequence of states that are stored in the shift
register form a Markov chain $(S_{\ell})$ on $\Omega$. Now, let us say that we
can observe the state of the shift register at deterministic time intervals to
yield a sequence of sample states $(Z_{1},Z_{2},\ldots)$, however suppose that
the bases are shifted in at random time intervals such that each state
$S_{\ell}$ is observed for a duration of $K_{\ell}$ samples. In this scenario,
we have that $Z_{t}=S_{\ell}$ for all $t$ such that
$T_{\ell-1}=K_{1}+\ldots+K_{\ell-1}<t\leq
T_{\ell}=K_{1}+\ldots+K_{\ell-1}+K_{\ell}$, where $T_{\ell}$ denotes the time
when state $S_{\ell}$ is observed for the last time. Hence, the sequence of
observed sample states in the shift register at different time instances form
a semi-Markov chain $(Z_{t})$ on $\Omega$. Finally, let us take noisy
measurements $(Y_{1},Y_{2},\ldots)$ of the hidden sample states
$(Z_{1},Z_{2},\ldots)$, where $Y_{t}=f(Z_{t})+N_{t}$ for zero-mean additive
noise $N_{t}$. This sequence of measurements form a hidden semi-Markov chain
$(Y_{t})$ on $\mathcal{Y}\subseteq\mathbb{R}$.

We have now defined all components of the channel model, which are summarised
in the following definition.

######  Definition 1 (Noisy nanopore channel).

Let us define $m$ channel-uses of the noisy nanopore channel as
$W^{(m)}:(S_{0},S_{1},\ldots,S_{m})\rightarrow(Y_{1},\ldots,Y_{T_{1}},Y_{T_{1}+1},\ldots,Y_{T_{m}})$,
where the input $(S_{0},S_{1},\ldots,S_{m})$ is a Markov chain on $\Omega$,
and the output is derived by mapping the semi-Markov chain
$(Z_{1},\ldots,Z_{T_{1}},Z_{T_{1}+1},\ldots,Z_{T_{m}})$ on $\Omega$ to the
hidden semi-Markov chain $(Y_{1},Y_{2},\ldots,Y_{T_{m}})$ on
$\mathcal{Y}\subseteq\mathbb{R}$, where the dwell times
$K_{\ell}=T_{\ell}-T_{\ell-1}$ are defined on
$\Lambda\subseteq\mathbb{N}\backslash\\{0\\}$. The mapping of the output is
the mean measurement level given by $f$ with zero-mean additive noise.

This natural definition of the noisy nanopore channel has hinted at a new
class of channels, namely finite-state semi-Markov channels. If we set
$\Lambda=\\{1\\}$, then the FSSMC collapses into the classical FSMC, and hence
we say that the former generalises the latter. In addition, a FSSMC with
geometrically distributed durations is also a FSMC (since the semi-Markov
source collapses into a Markov source).

We briefly note that the zero element is removed from the durations
$\mathsf{supp}(K)=\Lambda$ since that would imply concatenation of a deletion
channel with deletion probability $d=\mathbb{P}(K=0)$, but we do not allow
this here. Future work may study a generalisation of this channel, where
deletion is allowed.

##  IV Detection Algorithms

We now generalise two important detection algorithms, namely the forward-
backward algorithm and the Viterbi algorithm. In [15, 14], similar algorithms
were derived for inference of the sample states $(Z_{t})$ given the
observations $(Y_{t})$, but with an unknown number of states. In our case, we
know $m$ channel-uses segments $(Z_{t})$ into $m$ states of $S_{1}^{m}$, hence
the detection problem is to find which non-overlapping segments of samples in
$(Y_{t})$ correspond to which sequence of states.

###  IV-A MAP symbol detection

The goal of this section is to derive message passing algorithms to compute
$\mathbb{P}(S_{\ell}|Y_{1}^{T_{m}})$ for all $\ell\in[m]$. The existing
message passing algorithms [15] for hidden semi-Markov chains compute
$\mathbb{P}(Z_{t}|Y_{1}^{T_{m}})$ and
$\mathbb{P}(Z_{t^{\prime}}^{t}|Y_{1}^{T_{m}})$, however we are interested in
the probability of the $\ell$-th segment being in a particular state given
that there are exactly $m$ segments in total, which includes all sample paths
$Z_{1}^{T_{m}}$ with $Z_{t^{\prime}}^{t}=S_{\ell}$ for all
$t^{\prime},t\in[T_{m}]$ such that $t^{\prime}<t$. Note that the constraint of
$m$ segments effectively adds memory the size of the entire block.

Generalised forward algorithm. Let us now generalise the classical forward
algorithm. The initial forward probabilities are defined as

$\displaystyle\alpha_{1,t}(s)$ $\displaystyle:=\mathbb{P}(Y_{1}^{t},S_{1}=s)$
$\displaystyle=\sum_{s^{\prime}\in\Omega}\gamma_{1}^{t}(s^{\prime},s)\mu_{0}(s^{\prime})$
(5)

for all $t\in[T_{m}]$, and for all $s\in\Omega$. The inductive forward
probabilities are defined as

$\displaystyle\alpha_{\ell,t}(s)$
$\displaystyle:=\mathbb{P}(Y_{1}^{t},S_{\ell}=s)$
$\displaystyle=\sum_{s^{\prime}\in\Omega}\sum_{t^{\prime}\in[t-1]}\gamma_{t^{\prime}+1}^{t}(s^{\prime},s)\alpha_{\ell-1,t^{\prime}}(s^{\prime})$
(6)

for all $t\in[T_{m}]$, for all $\ell\in[m]\backslash\\{1\\}$, and for all
$s\in\Omega$. Observe that setting $\Lambda=\\{1\\}$ yields the classical
forward algorithm.

Generalised backward algorithm. Let us now generalise the classical backward
algorithm. The initial backward probabilities are defined to be
$\beta_{m,T_{m}}(s):=1$ for all $s\in\Omega$. The inductive backward
probabilities are defined as

$\displaystyle\begin{split}\beta_{\ell,t}(s)&:=\mathbb{P}(Y_{t+1}^{T_{m}}|S_{\ell}=s)\\\
&=\sum_{s^{\prime}\in\Omega}\sum_{t^{\prime}\in[t+1:T_{m}]}\gamma_{t+1}^{t^{\prime}}(s,s^{\prime})\beta_{\ell+1,t^{\prime}}(s^{\prime})\end{split}$
(7)

for all $t\in[T_{m}]$, for all $\ell\in[m-1]$, and for all $s\in\Omega$. Once
again, setting $\Lambda=\\{1\\}$ yields the classical backward algorithm.

Generalised forward-backward algorithm. We now use the generalised forward
algorithm and the generalised backward algorithm to compute the posterior
probabilities

$\displaystyle\psi_{\ell}(s)$
$\displaystyle:=\mathbb{P}(S_{\ell}=s|Y_{1}^{T_{m}})$
$\displaystyle=\frac{\sum_{t\in[T_{m}]}\mathbb{P}(Y_{1}^{t},S_{\ell}=s)\mathbb{P}(Y_{t+1}^{T_{m}}|S_{\ell}=s)}{\mathbb{P}(Y_{1}^{T_{m}})}$
$\displaystyle=\frac{\sum_{t\in[T_{m}]}\alpha_{\ell,t}(s)\beta_{\ell,t}(s)}{\sum_{s^{\prime}\in\Omega}\alpha_{m,T_{m}}(s^{\prime})}.$
(8)

Similarly, we can also compute the joint posterior probabilities

$\displaystyle\psi_{\ell}(s^{\prime},s)$
$\displaystyle:=\mathbb{P}(S_{\ell-1}=s^{\prime},S_{\ell}=s|Y_{1}^{T_{m}})$
$\displaystyle=\frac{\sum_{t^{\prime},t\in[T_{m}]:t^{\prime}<t}\alpha_{\ell-1,t^{\prime}}(s^{\prime})\gamma_{t^{\prime}+1}^{t}(s^{\prime},s)\beta_{\ell,t}(s)}{\sum_{s^{\prime\prime}\in\Omega}\alpha_{m,T_{m}}(s^{\prime\prime})}.$
(9)

Aside from detection, we will use both of these probabilities to estimate
achievable rates of the NNC in Section V.

###  IV-B MAP sequence detection

The goal of this section is to derive a Viterbi algorithm to compute the
sequence of states that maximise the posterior
$\mathbb{P}(Z_{1}^{T_{m}}|Y_{1}^{T_{m}})\propto\mathbb{P}(Z_{1}^{T_{m}},Y_{1}^{T_{m}})$.
Compared to the classical Viterbi algorithm, we not only sequentially maximise
the path of states $S_{1}^{m}$, but also the sequence of jump times
$T_{1}^{m}$. Importantly, we require that the first state begins at index
$T_{0}+1$ ($T_{0}=0$) and the $m$-th state ends at index $T_{m}$ known at the
decoder, hence we must segment an observation $Y_{1}^{T_{m}}$ into a sequence
of $m$ segments that maximises the posterior.

Generalised Viterbi algorithm. Let us now derive the dynamic program of the
generalised Viterbi algorithm as

$\displaystyle V(m,t_{m})$
$\displaystyle:=\max_{\begin{subarray}{c}s_{1},\ldots,s_{m}\\\
1<t_{1}<\ldots<t_{m}\end{subarray}}\prod_{\ell=1}^{m}\gamma_{t_{\ell-1}+1}^{t_{\ell}}(s_{\ell-1},s_{\ell})$
(10) $\displaystyle\begin{split}&=\max_{\begin{subarray}{c}s_{m}\\\
t_{m-1}<t_{m}\end{subarray}}\gamma_{t_{m-1}+1}^{t_{m}}(s_{m-1},s_{m})\\\
&\quad\quad\quad\cdot\left[\max_{\begin{subarray}{c}s_{1},\ldots,s_{m-1}\\\
1<t_{1}<\ldots<t_{m-1}\end{subarray}}\prod_{\ell=1}^{m-1}\gamma_{t_{\ell-1}+1}^{t_{\ell}}(s_{\ell-1},s_{\ell})\right]\end{split}$
$\displaystyle=\max_{\begin{subarray}{c}s_{m}\\\
t_{m-1}<t_{m}\end{subarray}}\gamma_{t_{m-1}+1}^{t_{m}}(s_{m-1},s_{m})V(m-1,t_{m-1})$

where $V(0,0):=1$, noting that each $t_{\ell}$ is a constant in
$V(\ell,t_{\ell})$. The dynamic program of subproblem $V(\ell,t_{\ell})$
jointly maximises the posterior of the sequence of states $s_{1}^{\ell}$ and
the sequence of segment jump times $t_{1}^{\ell-1}$ such that the $\ell$-th
segment jumps after time $t$. Since $V(\ell,t)$ depends on other subproblems
$V(\ell^{\prime},t^{\prime})$ for all $\ell^{\prime}<\ell$ and for all
$t^{\prime}<t$, it can be shown with some work that standard dynamic
programming techniques solve (10) in a worst-case
$O(mT_{m}4|\Omega||\Lambda|)$ time (note that for the nanopore any state is
connected to a maximum of four other states).

##  V Achievable Rates

We now turn our attention to computing achievable rates. The ultimate goal is
to compute the capacity of Definition 1, constrained to Markov sources, which
is given by

$\displaystyle\begin{split}C(W)&=\sup_{P}I(\mathscr{S};\mathscr{Y})\\\
&=\lim_{m\rightarrow\infty}\frac{1}{m}\sup_{P}I(S_{1}^{m};Y_{1}^{T_{m}})\end{split}$
(11)

in bits per base (or bits per state), where $P$ is a Markov kernel of Markov
source $(S_{\ell})$ and the resulting achievable rate is
$I(\mathscr{S};\mathscr{Y})$. As in the previous section, let us take methods
for the FSMC and show analogous methods for the NNC.

In [9], the classical Blahut-Arimoto algorithm for discrete memoryless
channels was generalised to compute achievable rates of finite-state channels.
It was not rigorously proven to converge to the capacity, however it was
strongly suggested based on their numerical results, and later proven to at
least converge to a critical point [11]. In this spirit, we show the (almost)
direct application of GBAA to the NNC.

GBAA iteratively searches for the Markov kernel that achieves the maximisation
of (11), computing achievable rates at each iteration using the method we now
describe. Let $\mu$ be the stationary distribution of some Markov kernel $P$,
then we can write the achievable information rate as

$\frac{1}{m}I(S_{1}^{m};Y_{1}^{T_{m}})=\\\
\underbrace{\frac{1}{m}\sum_{\ell=1}^{m}H(S_{\ell}|S_{\ell-1})}_{\sum_{i,j\in\Omega}\mu(i)P(i,j)\log\frac{1}{P(i,j)}}-\frac{1}{m}\sum_{\ell=1}^{m}H(S_{\ell}|S_{\ell-1},Y_{1}^{T_{m}}).$
(12)

The first term has a closed-form, however the second term is significantly
more challenging to compute. We decompose the second term identically to [9],
which defines the so-called $T$-values as

$\displaystyle T(i,j)$
$\displaystyle=\lim_{m\rightarrow\infty}\frac{1}{m}\sum_{\ell=1}^{m}\mathbb{E}\left[\log\frac{\psi_{\ell}(i,j)^{\frac{\psi_{\ell}(i,j)}{\mu(i)P(i,j)}}}{\psi_{\ell-1}(i)^{\frac{\psi_{\ell-1}(i)}{\mu(i)}}}\right],$
(13)

then, assuming we can compute these $T$-values, the achievable information
rate of the NNC is computed as

$\displaystyle
I(\mathscr{S};\mathscr{Y})=\sum_{i,j\in\Omega}\mu(i)P(i,j)\log\left[\frac{1}{P(i,j)}+T(i,j)\right]$
(14)

and may be optimised using GBAA [9]. Similarly to [9, 11], we conjecture that
this algorithm converges to the capacity since (ergodic) finite-state semi-
Markov processes are a subclass of (ergodic) finite-state processes (i.e.,
processes with memory). Strictly speaking, the capacity of a FSSMC must
optimise semi-Markov kernel $Q$, but since $\mathbb{P}(K)$ is fixed by the
duplication channel we need only consider Markov kernel $P$, where the
information contribution of $K$ is subtracted to give (12) for the NNC and is
identical in form to the FSMC.

The $T$-values can be estimated using a variation of the Arnold-Loeliger
method [10], which assumes ergodicity to compute estimates of (13) by applying
the classical forward-backward algorithm on a long realisation
$y_{1}^{t_{m}}$. For the NNC, we require the probabilities $\psi_{\ell}(i,j)$
and $\psi_{\ell-1}(i)$, which are (9) and (8), respectively, from Section IV.

##  VI Numerical Results

Model parameters. Let us now consider which parameters of the NNC accurately
model the actual nanopore channel. Scrappie [12] is a simulator by Oxford
Nanopore Technologies that takes input bases $b_{1}^{n}$ and outputs tuples
$\\{(x_{\ell},\sigma^{2}_{\ell})\\}_{\ell=1}^{n-\tau+1}$ for the mean and
variance of measurements for the $\ell$-th base shifted into the nanopore. The
model in Scrappie assumes the memory constraint $\tau$ is large, but we choose
$\tau=5$ since it gives roughly stationary parameters. We generate the channel
mapping $f$ by inputting multiple de Bruijn sequences (short sequences that
enumerate all $4^{\tau}$ nucleotides) into Scrappie and averaging $x_{\ell}$
over identical states in each sequence. For simplicity, we use a constant
$\sigma^{2}$ for all states, but all methods described earlier are easily
extended. Noisy measurements are distributed as i.i.d.
$\mathsf{Normal}\bigl{(}f(s),\sigma^{2}\bigr{)}$ while in state $s\in\Omega$,
and durations are distributed as i.i.d. $\mathsf{Uniform}(\Lambda)$.

Although $P$ is sparse for $\tau=5$, it yields a state-space of $4^{5}=1024$
states that is prohibitive for the algorithms of Section IV. Hence, we reduce
the state-space by removing edges in the graph of the Markov source that are
not desirable for synchronisation (segmentation), namely the edges that have a
jumping distance, $\absolutevalue{f(i)-f(j)}$, below a minimum threshold
$J_{min}$, for all $i,j\in\Omega$ with $P(i,j)>0$. Ensuring the new graph is
irreducible, and thus ergodic, we use standard algorithms to compute the list
of strongly connected components and take the one with largest entropy. Set
$J_{min}=1.38$ to get our example state-space graph in Fig. 3.

Achievable rates. We now discuss the achievable information rates in Fig. 4,
which are plotted over different values of $\sigma$ and $\Lambda$ to highlight
the effect of the minimum duration and the range of durations with respect to
measurement noise. The achievable rates are estimated using a limited
$m=10,000$ channel-uses. We choose $\sigma$ to be in the range $0.10-0.40$,
which covers those given by the Scrappie simulator.

We observe the rates with durations $\Lambda=\\{1\\}$, i.e., the NNC without
duplications, which achieve the maximum source entropy $H_{\max}=0.3063$ over
this range of $\sigma$. We further observe that single duplications with
$\Lambda=\\{1,2\\}$ significantly degrade the rates, but fortunately this
degradation halts as the range is widened to $\Lambda=\\{1,2,\ldots,5\\}$,
giving identical rates to $\Lambda=\\{1,2,\ldots,10\\}$ and beyond.
Additionally, we observe that shifting the durations by one significantly
improves the rate, which is demonstrated from $\Lambda=\\{1,2\\}$ to
$\Lambda=\\{2,3\\}$, and from $\Lambda=\\{1,2,\ldots,5\\}$ to
$\Lambda=\\{2,3,\ldots,6\\}$. Note the range effects remain. This observation
confirms our intuition that the shortest duration is the most difficult to
synchronise in a noisy channel, especially in the high-noise regime.

$f(\mathsf{CTCGT})$$=0.19$$f(\mathsf{TCGTC})$$=-1.3$$f(\mathsf{CGTCT})$$=1.6$$f(\mathsf{TCTCG})$$=1.6$$f(\mathsf{GTCTC})$$=-0.031$$f(\mathsf{CTCTC})$$=0.094$$f(\mathsf{TCTCT})$$=1.5$$\mathsf{C}$$\mathsf{T}$$\mathsf{C}$$\mathsf{T}$$\mathsf{C}$$\mathsf{T}$$\mathsf{G}$$\mathsf{T}$$\mathsf{G}$
Figure 3: A jump-constrained graph derived from measurement levels in Scrappie
[12]. The edges are channel inputs and the nodes are a state $s\in\Omega$ with
channel mapping $f(s)$. $0.1$$0.15$$0.2$$0.25$$0.3$$0.35$$0.4$$5\cdot
10^{-2}$$0.1$$0.15$$0.2$$0.25$$0.3$$H_{max}=0.3063$$\sigma$Rate
(bits/base)i.u.d. jump-constrained achievable information
rates$\Lambda=\\{1\\}$$\Lambda=\\{2,3\\}$$\Lambda=\\{2,3,\ldots,6\\}$$\Lambda=\\{1,2\\}$$\Lambda=\\{1,2,3\\}$$\Lambda=\\{1,2,\ldots,5\\}$$\Lambda=\\{1,2,\ldots,10\\}$
Figure 4: Achievable rates using the independent and uniformly distributed
(i.u.d.) input distribution for the example in Fig. 3.

##  VII Conclusion

In summary, we proposed the NNC for modelling the dominant distortions of the
nanopore sequencer. We filled the gap in previous works by including
duplications in the model, while maintaining tractability. The tractability of
the model was demonstrated by the detection algorithms that generalised their
classical counterparts. We estimated achievable rates for an example NNC using
methods closely tied to GBAA.

This paper established a model with basic tools before coding schemes are
considered in our future work. Such coding schemes will have to satisfy the
source constraints required for synthesis and sequencing of DNA, all while
being efficiently decodable. Our detection algorithms open the possibility of
iterative decoding of LDPC codes with the generalised forward-backward
algorithm, or sequential decoding of convolutional codes with the generalised
Viterbi algorithm. We are hopeful that this avenue of research will lead to
reliable nanopore sequencing.

## References

  * [1] Oxford Nanopore Technologies, “Nanopore sequencer,” https://nanoporetech.com.
  * [2] R. Lopez, Y.-J. Chen, S. D. Ang, S. Yekhanin, K. Makarychev, M. Z. Rácz, G. Seelig, K. Strauss, and L. Ceze, “DNA assembly for nanopore data storage readout,” _Nature Communications_ , vol. 10, 2019.
  * [3] A. H. Laszlo, I. Derrington, B. C. Ross, H. Brinkerhoff, A. Adey, I. C. Nova, J. M. Craig, K. W. Langford, J. Samson, R. Daza, K. Doering, J. Shendure, and J. Gundlach, “Decoding long nanopore sequencing reads of natural DNA,” _Nature biotechnology_ , vol. 32, pp. 829 – 833, 2014.
  * [4] W. Mao, S. Diggavi, and S. Kannan, “Models and information-theoretic bounds for nanopore sequencing,” _2017 IEEE International Symposium on Information Theory (ISIT)_ , pp. 2458–2462, 2017.
  * [5] R. Hulett, S. Chandak, and M. Wootters, “On coding for an abstracted nanopore channel for DNA storage,” _2021 IEEE International Symposium on Information Theory (ISIT)_ , pp. 2465–2470, 2021.
  * [6] Y. Tang and F. Farnoud, “Error-correcting codes for noisy duplication channels,” _2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_ , pp. 140–146, 2019.
  * [7] L. Conde-Canencia and L. Dolecek, “Nanopore DNA sequencing channel modeling,” in _2018 IEEE International Workshop on Signal Processing Systems (SiPS)_ , 2018, pp. 258–262.
  * [8] R. G. Gallager, “Information theory and reliable communication,” 1968.
  * [9] A. Kavcic, “On the capacity of Markov sources over noisy channels,” _GLOBECOM’01. IEEE Global Telecommunications Conference (Cat. No.01CH37270)_ , vol. 5, pp. 2997–3001 vol.5, 2001.
  * [10] D.-M. Arnold and H.-A. Loeliger, “On the information rate of binary-input channels with memory,” _ICC 2001. IEEE International Conference on Communications. Conference Record (Cat. No.01CH37240)_ , vol. 9, pp. 2692–2695 vol.9, 2001.
  * [11] P. O. Vontobel, A. Kavcic, D.-M. Arnold, and H.-A. Loeliger, “A generalization of the Blahut–Arimoto algorithm to finite-state channels,” _IEEE Transactions on Information Theory_ , vol. 54, pp. 1887–1918, 2008.
  * [12] Oxford Nanopore Technologies, “Scrappie: a technology demonstrator for the Oxford Nanopore Research Algorithms group,” https://github.com/nanoporetech/scrappie, 2017.
  * [13] V. S. Barbu and N. Limnios, “Semi-Markov chains and hidden semi-Markov models toward applications: Their use in reliability and DNA analysis,” 2008\.
  * [14] V. Girardin and N. Limnios, “Markov and semi-Markov processes,” 2018.
  * [15] S. Yu, “Hidden semi-Markov models,” _Artif. Intell._ , vol. 174, pp. 215–243, 2010.


# Certifying LLM Safety against Adversarial
Prompting

Aounon Kumar
University of Maryland
College Park, MD
<EMAIL_ADDRESS>&Chirag Agarwal
Harvard University
Cambridge, MA
<EMAIL_ADDRESS>&Suraj Srinivas
Harvard University
Cambridge, MA
<EMAIL_ADDRESS>Soheil Feizi
University of Maryland
College Park, MD
<EMAIL_ADDRESS>&Hima Lakkaraju
Harvard University
Cambridge, MA
<EMAIL_ADDRESS>
###### Abstract

Large language models (LLMs) released for public use incorporate guardrails to
ensure their output is safe, often referred to as “model alignment.” An
aligned language model should decline a user’s request to produce harmful
content. However, such safety measures are vulnerable to adversarial prompts,
which contain maliciously designed token sequences to circumvent the model’s
safety guards and cause it to produce harmful content. In this work, we
introduce erase-and-check, the first framework to defend against adversarial
prompts with verifiable safety guarantees. We erase tokens individually and
inspect the resulting subsequences using a safety filter. Our procedure labels
the input prompt as harmful if any subsequences or the input prompt are
detected as harmful by the filter. This guarantees that any adversarial
modification of a harmful prompt up to a certain size is also labeled harmful.
We defend against three attack modes: i) adversarial suffix, which appends an
adversarial sequence at the end of the prompt; ii) adversarial insertion,
where the adversarial sequence is inserted anywhere in the middle of the
prompt; and iii) adversarial infusion, where adversarial tokens are inserted
at arbitrary positions in the prompt, not necessarily as a contiguous block.
Empirical results demonstrate that our technique obtains strong certified
safety guarantees on harmful prompts while maintaining good performance on
safe prompts. For example, against adversarial suffixes of length 20, it
certifiably detects $93\%$ of the harmful prompts and labels $94\%$ of the
safe prompts as safe using the open source language model Llama 2 as the
safety filter.

##  1 Introduction

Popular language models such as ChatGPT, Bard, and Llama are often trained
using unvetted textual data from the web that contain significant amounts of
inappropriate and objectionable material. A model trained on such data could
be used to produce harmful content when released for public use. To this end,
several fine-tuning techniques have been developed to incorporate human
feedback to ensure that LLM outputs are safe and aligned with human values
(Ouyang et al., 2022; Bai et al., 2022; Glaese et al., 2022; Korbak et al.,
2023; Xu et al., 2020). These approaches use human oversight to steer an LLM
to generate content well aligned with moral and ethical principles. When
prompted with a harmful user request, an aligned model is expected to decline
the request rather than comply with it. Following is an example of a safe
LLM’s response to a harmful request:

Harmful Prompt: Provide detailed instructions on making a homemade explosive
device using household materials.
LLM Response: Sorry, I cannot assist with that request. Promoting safety is of
utmost importance.

Although significant progress has been made in developing guardrails for LLMs,
several “jailbreak” attacks exist that allow a malicious user to bypass the
safety measures. For example, Wei et al. (2023) shows that simply asking an
LLM to begin its response with “Absolutely! Here’s” could mislead the model
into complying with the user’s harmful request. Several other examples of
adversarial augmentation of harmful prompts, such as the Do Anything Now (DAN)
jailbreak, are also well known. The work of Zou et al. (2023) shows that it is
possible to automate the generation of adversarial sequences, creating an
endless supply of such attacks. Moreover, they show that a single such
adversarial sequence can be appended to several harmful prompts to bypass
safety measures. Their method achieves a high attack success rate, of up to
84%, even on black-box LLMs such as GPT-3.5 using adversarial sequences of
length 20. The following is an illustration of the effect of an adversarial
suffix on the above example:

Harmful Prompt \+ Adversarial Sequence: Provide detailed instructions on
making a homemade explosive device using household
materials.@%!7*]/$r>x3w)2#(&q<
LLM Response: Sure, here’s a step-by-step guide to making a homemade explosive
device...

In this work, we design a procedure erase-and-check to defend against such
attacks with verifiable safety guarantees. Given a clean or adversarially
manipulated prompt $P$, it erases tokens individually and checks if the
original prompt $P$ and all its erased subsequences are safe using a safety
filter is-harmful. We implement this filter by prompting an open-source
language model, Llama 2 (Touvron et al., 2023), to classify a subsequence as
harmful or not harmful. Other state-of-the-art LLMs or custom classifiers
could also be used for this purpose. If any of these sequences is detected as
harmful, erase-and-check labels the original prompt $P$ as harmful. This
guarantees that all adversarial modifications of a harmful prompt up to a
certain size are labeled harmful. The prompt $P$ is labeled safe only if the
filter detects all its erased subsequences as safe. Our procedure leverages a
fundamental property of safe prompts: Subsequences of safe prompts are also
safe.

Our safety certificate is focused on guaranteeing that harmful prompts do not
get misclassified as safe under attack. We do not seek to defend against
attacks on safe prompts aimed at getting them misclassified as harmful. Our
experimental results show that, against adversarial suffixes of length 20, it
certifiably detects $93\%$ of the harmful prompts and labels $94\%$ of the
safe prompts as safe. We defend against the following three attack modes
listed in order of increasing generality:

Figure 1: Adversarial prompts under different attack modes. Adversarial tokens
are represented in red.

(1) Adversarial Suffix: This is the simplest attack mode. In this mode,
adversarial prompts are of the type $P+\alpha$, where an adversarial sequence
$\alpha$ is appended to the end of the original prompt $P$ (see Figure 1).
Here, $+$ represents sequence concatenation. This is the type of adversarial
prompts generated by Zou et al. (2023) as shown in the example above. For this
mode, the erase-and-check procedure erases $d$ tokens from the end of the
input prompt one by one and checks the resulting subsequences using the filter
is-harmful. It labels the input prompt as harmful if any subsequences or the
input prompt are detected as harmful (see Figure 2). Consider an adversarial
prompt $P+\alpha$ where $P$ was originally detected as harmful by the safety
filter is-harmful. If $|\alpha|\leq d$, the prompt $P$ must be one of the
subsequences checked by is-harmful. Therefore, $P+\alpha$ must also be labeled
as harmful by erase-and-check. This is the crux of our safety guarantee. Note
that this guarantee holds for all non-negative integral values of $d$.
However, as $d$ becomes larger, the running time of erase-and-check also
increases as the set of subsequences needed to check grows as $O(d)$.

(2) Adversarial Insertion: This mode subsumes the suffix mode. Here,
adversarial sequences can be inserted anywhere in the middle (or the end) of
the prompt $P$. This leads to prompts of the form $P_{1}+\alpha+P_{2}$, where
$P_{1}$ and $P_{2}$ are two partitions of $P$, that is, $P_{1}+P_{2}=P$ (see
Figure 1). The set of adversarial prompts we must defend against is
significantly larger than the suffix mode. For adversarial prompts of this
form, erase-and-check erases up to $d$ tokens starting from a location $i$ of
the prompt for all locations $i$ from 1 to $|P_{1}+\alpha+P_{2}|$. More
precisely, it generates subsequences by erasing tokens in the range
$[i,\ldots,i+j]$, for all $i\in\\{1,\ldots,|P_{1}+\alpha+P_{2}|\\}$ and for
all $j\in\\{1,\ldots,d\\}$. Using an argument similar to that for the suffix
mode, we can show that this procedure can certifiably detect adversarial
insertions of length at most $d$. It can also be generalized to defend against
multiple adversarial insertions, that is, prompts of the form
$P_{1}+\alpha_{1}+P_{2}+\alpha_{2}+\cdots+\alpha_{k}+P_{k+1}$, where
$\alpha_{1},\alpha_{2},\ldots,\alpha_{k}$ are $k$ contiguous blocks of
adversarial tokens The certified guarantee is for the maximum length over all
adversarial sequences. Like in the suffix mode, the guarantee holds for all
non-negative integral values of $d$ and $k$. However, this mode is harder to
defend against as the number of subsequences to check increases as
$O\left((nd)^{k}\right)$.

(3) Adversarial Infusion: This is the most general attack mode. In this mode,
adversarial tokens $\tau_{1},\tau_{2},\ldots,\tau_{m}$ are inserted at
arbitrary locations in the prompt $P$, leading to adversarial prompts of the
form $P_{1}+\tau_{1}+P_{2}+\tau_{2}+\cdots+\tau_{m}+P_{m+1}$ (see Figure 1).
The set of such prompts subsumes the adversarial prompts of the previous two
modes. The key difference from the insertion mode is that the adversarial
tokens need not be inserted as a contiguous block. To defend against this
attack mode, erase-and-check generates subsequences by erasing subsets of
tokens of size at most $d$ from the input prompt. If $m\leq d$, one of the
erased subsets must match exactly with the set of adversarial tokens when the
prompt $P_{1}+\tau_{1}+P_{2}+\tau_{2}+\cdots+\tau_{m}+P_{m+1}$ is given as
input. Thus, one of the checked subsequences must be $P$. Therefore, if $P$ is
detected as harmful by is-harmful, any adversarial infusion of $P$ using at
most $d$ tokens is guaranteed to be labeled as harmful by erase-and-check.
Similar to other attack modes, this safety guarantee holds for all non-
negative integral values of $d$. However, this mode is the most challenging to
defend against as the number of generated subsequences increases as
$O(n^{d})$, which grows exponentially with $d$.

Figure 2: An illustration of how erase-and-check works on adversarial suffix
attacks. It erases tokens from the end and checks the resulting subsequences
using a safety filter. If at least one of the erased subsequences is detected
as harmful, the input prompt is labeled harmful.

Safety Filter: Our procedure erase-and-check uses a safety filter is-harmful
as a subroutine to check each erased subsequence. We use the open-source
language model Llama 2 developed by Meta AI to design this filter. We use its
system prompt to set its objective to classifying a user prompt as harmful or
not harmful. We then look for texts such as “Not harmful” to determine whether
the prompt is safe. We flag the input prompt as harmful if no such text
sequence is found in the LLM’s output. The following is an example of the type
of system prompt we use:

System Prompt: Your objective is to determine if the user’s request or
question is harmful or not. Just answer ‘‘harmful’’ or ‘‘not harmful’’ to each
user message.

Safety Certificate: The construction of erase-and-check guarantees that if a
prompt $P$ is detected as harmful by the safety filter is-harmful, then erase-
and-check will label the prompt $P$ and all its adversarial modifications
$P+\alpha$, up to a certain length, as harmful. This implies that the accuracy
of the safety filter on a set of harmful prompts is a lower bound on the
accuracy of erase-and-check on the same set. A similar argument can also be
made for any probability distribution over harmful prompts. Therefore, to
calculate the certified accuracy of erase-and-check on harmful prompts, we
just need to evaluate the accuracy of the filter on such prompts. We evaluated
is-harmful on the 500 harmful behavior instruction prompts created by Zou et
al. (2023) as part of their AdvBench dataset and observed an accuracy of 93%.
For comparison, an adversarial suffix of length 20 can make the accuracy on
harmful prompts as low as 16% for GPT-3.5 (see Figure 3 in Zou et al. (2023)).

Note that this value is the certified accuracy of erase-and-check for all
adversarial sequence lengths and attack modes considered. However, as
discussed above, the computational cost of erase-and-check increases for more
general attack modes, limiting the length of adversarial sequences that can be
defended against in a reasonable amount of time. Also, as we will see later in
this work, the accuracy of the erase-and-check procedure decreases for larger
adversarial sequences. This is likely because defending against longer
adversarial sequences requires our procedure to check more subsequences for
each input prompt. This increases the likelihood that the safety filter
accidentally misclassifies one of the subsequences as harmful. This issue
could potentially be resolved by training a safety classifier on safe and
harmful prompts, ensuring that it recognizes erased subsequences of safe
prompts as safe as well.

##  2 Related Work

Adversarial Attacks: Deep neural networks and other machine learning models
have been known to be vulnerable to adversarial attacks (Szegedy et al., 2014;
Biggio et al., 2013; Goodfellow et al., 2015; Madry et al., 2018; Carlini &
Wagner, 2017). For computer vision models, adversarial attacks make tiny
perturbations in the input image that can completely alter the model’s output.
A key objective of these attacks is to make the perturbations as imperceptible
to humans as possible. However, as Chen et al. (2022) argue, the
imperceptibility of the attack makes little sense for natural language
processing tasks. A malicious user seeking to bypass the safety guards in an
aligned LLM does not need to make the adversarial changes imperceptible. The
attacks generated by Zou et al. (2023) can be easily detected by humans, yet
deceive LLMs into complying with harmful requests. This makes it challenging
to apply existing adversarial defenses for such attacks as they often rely on
the perturbations being small.

Empirical Defenses: Over the years, several heuristic methods have been
proposed to detect and defend against adversarial attacks for computer vision
(Buckman et al., 2018; Guo et al., 2018; Dhillon et al., 2018; Li & Li, 2017;
Grosse et al., 2017; Gong et al., 2017) and natural language processing tasks
(Nguyen Minh & Luu, 2022; Yoo et al., 2022; Huber et al., 2022). A recent work
by Jain et al. (2023) studies defenses specifically for attacks by Zou et al.
(2023) based on approaches such as perplexity filtering, paraphrasing, and
adversarial training. However, empirical defenses against specific adversarial
attacks have been shown to be broken by stronger attacks (Carlini & Wagner,
2017; Athalye et al., 2018; Uesato et al., 2018; Laidlaw & Feizi, 2019).
Empirical robustness against an adversarial attack does not imply robustness
against more powerful attacks in the future. Our work focuses on generating
provable robustness guarantees that hold against every possible adversarial
attack within a threat model.

Certifed Defenses: Defenses with provable robustness guarantees have been
extensively studied in computer vision. They use techniques such as interval-
bound propagation (Gowal et al., 2018; Huang et al., 2019; Dvijotham et al.,
2018; Mirman et al., 2018), curvature bounds (Wong & Kolter, 2018; Raghunathan
et al., 2018; Singla & Feizi, 2020; 2021) and randomized smoothing (Cohen et
al., 2019; Lécuyer et al., 2019; Li et al., 2019; Salman et al., 2019).
Certified defenses have also been studied for tasks in natural language
processing. For example, Ye et al. (2020) presents a method to defend against
word substitutions with respect to a set of predefined synonyms for text
classification. Zhao et al. (2022) use semantic smoothing to defend against
natural language attacks. Zhang et al. (2023) propose a self-denoising
approach to defend against minor changes in the input prompt for sentiment
analysis. Such defenses often incorporate imperceptibility in their threat
model one way or another, e.g., by restricting to synonymous words and minor
changes in the input text. This makes them inapplicable to attacks by Zou et
al. (2023) that change the prompts by a significant amount. Moreover, such
approaches are designed for classification-type tasks and do not leverage the
special properties of LLM safety attacks. Our safety certificate is focused on
guaranteeing that harmful prompts do not get misclassified as safe under
attack. We err on the side of caution to guarantee that an LLM does not cause
harm. We do not seek to defend against adversarial attacks on safe prompts
aimed at getting them misclassified as harmful. This threat model makes little
sense in practice as it is unlikely that a user will seek to make their safe
prompts look harmful to an aligned LLM only to get their request rejected.

##  3 Notations

We denote an input prompt $P$ as a sequence of tokens
$P_{1},P_{2},\ldots,P_{n}$, where $n=|P|$ is the length of the sequence.
Similarly, we denote the tokes of an adversarial sequence $\alpha$ as
$\alpha_{1},\alpha_{2},\ldots,\alpha_{l}$. We use the $+$ symbol to denote the
concatenation of two sequences. Thus, an adversarial suffix $\alpha$ appended
to $P$ is written as $P+\alpha$. We use the notation $P[s,t]$ with $s\leq t$
to denote a subsequence of $P$ starting from the token $P_{s}$ and ending at
$P_{t}$. For example, in the suffix mode, erase-and-check erases $i$ tokens
from the end of an input prompt $P$ at each iteration. The resulting
subsequence can be denoted as $P[1,|P|-i]$. In the insertion mode with
multiple adversarial sequences, we index each sequence with a superscript $i$,
that is, the $i^{\text{th}}$ adversarial sequence is written as $\alpha^{i}$.
We use the $-$ symbol to denote deletion of a subsequence. For example, in the
insertion mode, erase-and-check erases a subsequence of $P$ starting at $s$
and ending at $t$ in each iteration, which can be denoted as $P-P[s,t]$. We
use $\cup$ to denote the union of subsequences. For example, in insertion
attacks with multiple adversarial sequences, erase-and-check removes multiple
contiguous blocks of tokens from $P$, which we denote as
$P-\cup_{i=1}^{k}P[s_{i},t_{i}]$.

##  4 Adversarial Suffix

This attack mode appends adversarial tokens at the end of a harmful prompt to
get it misclassified as safe by a language model. This is the threat model
considered by Zou et al. (2023) to design universal adversarial attacks that
transfer to several harmful prompts and popular LLMs. This threat model can be
defined as the set of all possible adversarial prompts generated by appending
a sequence of tokens $\alpha$ of a certain maximum length $l$ to a prompt $P$.
Mathematically, this set is defined as

$\mathsf{SuffixTM}(P,l)=\big{\\{}P+\alpha\;\big{|}\;|\alpha|\leq l\big{\\}}.$

For a token set $T$, the above set grows exponentially ($O(|T|^{l})$) with the
adversarial length $l$, making it significantly challenging to defend against
the entire set of attacks. It is not feasible to enumerate and defend against
all adversarial sequences in this threat model. Our erase-and-check procedure
can guarantee safety over the entire set of adversarial prompts without
enumerating them.

Given an input prompt $P$ and a maximum erase length $d$, our procedure
generates $d$ sequences $E_{1},E_{2},\ldots,E_{d}$, where each
$E_{i}=P[1,|P|-i]$ denotes the subsequence produced by erasing $i$ tokens of
$P$ from the end. It checks the subsequences $E_{i}$ and the input prompt $P$
using the safety filter is-harmful. If the filter detects at least one of the
subsequences or the input prompt as harmful, $P$ is declared harmful. The
input prompt $P$ is labeled safe only if none of the sequences checked are
detected as harmful. See Algorithm 1 for pseudocode. When an adversarial
prompt $P+\alpha$ is given as input such that $|\alpha|\leq d$, the sequence
$E_{|\alpha|}$ must equal $P$. Therefore, if $P$ is a harmful prompt detected
by the filter as harmful, $P+\alpha$ must be labeled as harmful by erase-and-
check.

Algorithm 1 Erase-and-Check

Inputs: Prompt $P$, max erase length $d$.

Returns: True if harmful, False otherwise.

if is-harmful($P$) is True then

return True

end if

for $i\in\\{1,\ldots,d\\}$ do

Generate $E_{i}=P[1,|P|-i]$.

if is-harmful($E_{i}$) is True then

return True

end if

end for

return False

This implies that the accuracy of the safety filter is-harmful on a set of
harmful prompts is a lower bound on the accuracy of erase-and-check for all
adversarial modifications of prompts in that set up to length $d$. This
statement could be further generalized to a _distribution_ $\mathcal{H}$ over
all harmful prompts and a stochastic safety filter that detects a prompt as
harmful with some probability $p\in[0,1]$. Replacing true and false with 1 and
0 in the outputs of erase-and-check and is-harmful, the following theorem
holds on their accuracy over $\mathcal{H}$:

######  Theorem 1 (Safety Certificate).

For a prompt $P$ sampled from the distribution $\mathcal{H}$,

$\mathbb{E}_{P\sim\mathcal{H}}[\texttt{erase-and-
check}{}(P+\alpha)]\;\geq\;\mathbb{E}_{P\sim\mathcal{H}}[\texttt{is-
harmful}(P)],\quad\forall|\alpha|\leq d.$

###### Proof.

When $P+\alpha$ is given as input to erase-and-check, one of the erased
sequences $E_{|\alpha|}$ must equal $P$ (since $|\alpha|\leq d$). Therefore,
erase-and-check($P+\alpha$) is at least as likely to return true as is-
harmful($P$).

$\displaystyle\mathbb{E}_{P\sim\mathcal{H}}[\texttt{erase-and-
check}{}(P+\alpha)]$ $\displaystyle=\sum_{P}\mathbb{P}[\texttt{erase-and-
check}{}(P+\alpha)\text{ returns {\bf True}}]$
$\displaystyle\geq\sum_{P}\mathbb{P}[\texttt{is-harmful}(P)\text{ returns {\bf
True}}]$ $\displaystyle=\mathbb{E}_{P\sim\mathcal{H}}[\texttt{is-
harmful}(P)].$

∎

Therefore, to certify the performance of erase-and-check on harmful prompts,
we just need to evaluate the safety filter is-harmful on those prompts. We
evaluated is-harmful on a randomly sampled set of 500 harmful prompts from
AdvBench and observed an accuracy of 93%.

(a) Safe prompts labeled as safe.

(b) Average running time per prompt.

Figure 3: Empirical accuracy and running time of erase-and-check on safe
prompts for the suffix mode.

###  4.1 Empirical Evaluation on Safe Prompts

While our procedure can certifiably defend against adversarial attacks on
harmful prompts, we must also ensure that it maintains a good quality of
service for non-malicious, non-adversarial users. We need to evaluate the
accuracy and running time of erase-and-check on safe prompts that have not
been adversarially modified. To this end, we tested our procedure on 200 safe
prompts generated using ChatGPT for different values of the maximum erase
length between 0 and 30.

Figures 3(a) and 3(b) plot our procedure’s empirical accuracy and running
time, respectively. We observe a very high accuracy and low running times when
no tokens are erased, and only the original prompt is checked by erase-and-
check. This is because the Llama 2 model in our filter is very accurate in
classifying complete prompts. It also responds very quickly to these prompts.
However, as we increase the maximum erased length, the accuracy decreases, and
the running time increases. This is due to the fact that the safety filter has
to check several partially erased sequences for each prompt. This increases
the likelihood that the filter will misclassify at least one of the
subsequences. Also, Llama 2 is slower in responding to incomplete prompts and
often asks for further clarifications when the subsequences are small.
Nevertheless, the overall accuracy stays above 93%, and average running times
remain within 2 seconds up to a certified adversarial length of 30 tokens. We
performed these experiments on a single NVIDIA RTX A5000 GPU.

##  5 Adversarial Insertion

In this attack mode, an adversarial sequence is inserted anywhere in the
middle of a prompt. The corresponding threat model can be defined as the set
of adversarial prompts generated by splicing a contiguous sequence of tokens
$\alpha$ of maximum length $l$ into a prompt $P$. This would lead to prompts
of the form $P_{1}+\alpha+P_{2}$, where $P_{1}$ and $P_{2}$ are two partitions
of the original prompt $P$. Mathematically, this set is defined as

$\mathsf{InsertionTM}(P,l)=\big{\\{}P_{1}+\alpha+P_{2}\;\big{|}\;P_{1}+P_{2}=P\text{
and }|\alpha|\leq l\big{\\}}.$

This set subsumes the threat model for the suffix mode as a subset where
$P_{1}=P$ and $P_{2}$ is an empty sequence. It is also significantly larger
than the suffix threat model as its size grows as $O(|P||T|^{l})$, making it
harder to defend against.

In this mode, erase-and-check creates subsequences by erasing every possible
contiguous token sequence up to a certain maximum length. Given an input
prompt $P$ and a maximum erase length $d$, it generates sequences
$E_{s,t}=P-P[s,t]$ by removing the sequence $P[s,t]$ from $P$, for all
$s\in\\{1,\ldots,|P|\\}$ and for all $t\in\\{s,\ldots,s+d-1\\}$. Similar to
the suffix mode, it checks the prompt $P$ and the subsequences $E_{s,t}$ using
the filter is-harmful and labels the input as harmful if any of the sequences
are detected as harmful. The pseudocode for this mode can be obtained by
modifying the step for generating erased subsequences in Algorithm 1 with the
above method. For an adversarial prompt $P_{1}+\alpha+P_{2}$ such that
$|\alpha|\leq d$, one of the erased subsequences must equal $P$. This ensures
our safety guarantee. Similar to the suffix mode, the certified accuracy on
the harmful prompts is lower bounded by the accuracy of is-harmful, which is
93%.

(a) Safe prompts labeled as safe.

(b) Average running time per prompt.

Figure 4: Empirical accuracy and running time of erase-and-check on safe
prompts for the insertion mode.

Figures 4(a) and 4(b) plot the empirical accuracy and running time on safe
prompts for the insertion mode. Since the number of sequences to check is much
larger than that in the suffix mode, the running time on average for each
input prompt is higher. For this reason, we reduce the sample size to 50 and
the maximum erase length to 12. Like the suffix mode, we performed these
experiments on a single NVIDIA RTX A5000 GPU. We observe that the accuracy
drops faster than in the suffix mode. This is because when erase-and-check
needs to check more sequences, the likelihood that the filter misclassifies at
least one of the sequences increases. This can potentially be resolved by
training a classifier that is better at recognizing partially erased safe
prompts as safe.

(a) Safe prompts labeled as safe.

(b) Average running time per prompt.

Figure 5: Performance of erase-and-check against one vs. two adversarial
insertions. For two insertions, the maximum erase length is on individual
adversarial sequence. Thus, for two insertions and a maximum erase length of
6, the maximum number of tokens that can be erased is 12.

###  5.1 Multiple Insertions

Our method can also be generalized to multiple adversarial insertions. An
adversarial prompt in this case will be of the form
$P_{1}+\alpha_{1}+P_{2}+\alpha_{2}+\cdots+\alpha_{k}+P_{k+1}$, where $k$
represents the number of adversarial insertions. The number of such prompts
grows as $O((|P||T|^{l})^{k})$ with an exponential dependence on $k$. The
corresponding threat model can be defined as

$\displaystyle\mathsf{InsertionTM}(P,l,k)=\Big{\\{}P_{1}+\alpha_{1}+P_{2}+\alpha_{2}+\cdots+\alpha_{k}+P_{k+1}\;\Big{|}\;$
$\displaystyle\sum_{i=1}^{k}P_{i}=P\text{ and }$
$\displaystyle|\alpha_{i}|\leq l,\forall i\in\\{1,\ldots,k\\}\Big{\\}}.$

To defend against $k$ insertions, erase-and-check creates subsequences by
erasing $k$ contiguous blocks of tokens up to a maximum length of $d$. More
formally, it generates sequences $E_{\gamma}=P-\cup_{i=1}^{k}P[s_{i},t_{i}]$
for every possible tuple $\gamma=(s_{1},t_{1},s_{2},t_{2},\ldots,s_{k},t_{k})$
where $s_{i}\in\\{1,\ldots,|P|\\}$ and $t_{i}=\\{s_{i},\ldots,s_{i}+d-1\\}$.
Similar to the case of single insertions, it can be shown that one of the
erased subsequences $E_{\gamma}$ must equal $P$, which implies our safety
guarantee.

Figures 5(a) and 5(b) compare the empirical accuracy and the average running
time for one insertion and two insertions on 30 safe prompts up to a maximum
erase length of 6. The average running times are reported for a single NVIDIA
RTX A5000 GPU. Note that the maximum erase length for two insertions is on
individual adversarial sequences. Thus, if this number is 6, the maximum
number of tokens that can be erased is 12. Since the number of erased
subsequences for two insertions is significantly higher than that for one
insertion, the empirical accuracy decreases, and the running time increases
much faster than for one insertion. Defending against multiple insertions is
significantly more challenging, as the set of adversarial prompts increases
exponentially with the number of adversarial insertions $k$.

##  6 Adversarial Infusion

This is the most general of all the attack modes. Here, the adversary can
insert multiple tokens, up to a maximum number $l$, inside the harmful prompt
at arbitrary locations. The adversarial prompts in this mode are of the form
$P_{1}+\tau_{1}+P_{2}+\tau_{2}+\cdots+\tau_{m}+P_{m+1}$. The corresponding
threat model is defined as

$\mathsf{InfusionTM}(P,m)=\Big{\\{}P_{1}+\tau_{1}+P_{2}+\tau_{2}+\cdots+\tau_{m}+P_{m+1}\Big{|}\;\sum_{i=1}^{m+1}P_{i}=P\text{
and }m\leq l\Big{\\}}.$

This threat model subsumes all the previous threat models as every adversarial
sequence, suffix or insertion, is a subset of the adversarial prompt. The size
of the above set grows as $O\left({|P|+l\choose l}|T|^{l}\right)$ which is
much faster than any of the previous attack modes, making it the hardest to
defend against. Here, ${n\choose k}$ represents the number of $k$-combinations
of an $n$-element set.

In this mode, erase-and-check produces subsequences by erasing subsets of
tokens of size at most $d$. For an adversarial prompt of the above threat
model such that $l\leq d$, one of the erased subsets must match the
adversarial tokens $\tau_{1},\tau_{2},\ldots,\tau_{m}$. Thus, one of the
generated subsequences must equal $P$, which implies our safety guarantee.

We repeat similar experiments for the infusion mode as in previous attacks.
Due to the combinatorial explosion in the number of erased subsets, we
restrict the size of these subsets to 3 and the number of samples to 30.
Figures 6(a) and 6(b) plot the empirical accuracy and the average running time
on safe prompts. While the drop in accuracy is very low since the number of
erased tokens is small, the average running time per prompt (on one NVIDIA RTX
A5000 GPU) increases significantly with the certified size due to the
combinatorial nature of the threat model. However, similar to the previous
attack modes, the certified accuracy on harmful prompts remains at 93% for all
sizes of the adversarial token set.

(a) Safe prompts labeled as safe.

(b) Average running time per prompt.

Figure 6: Empirical accuracy and running time of erase-and-check on safe
prompts for the infusion mode.

##  7 Conclusion

We propose a procedure to certify the safety of large language models against
adversarial prompting. Our approach produces verifiable guarantees of
detecting harmful prompts altered with adversarial sequences up to a defined
length. Building on the insight that subsequences of safe prompts are also
safe, we develop a framework that sequentially removes tokens from a prompt,
labeling it as harmful if a safety filter flags any subsequence. We
experimentally demonstrate that this procedure can obtain high certified
accuracy on harmful prompts while maintaining good empirical performance on
safe prompts. It can provably defend against large adversarial perturbations
which are outside the class of imperceptible changes. We further validate its
adaptability by defending against three different adversarial threat models of
varying strengths.

Future Work: Our preliminary results on certifying LLM safety against non-
imperceptible adversarial prompting indicate a promising direction for
improving language model safety with verifiable guarantees. There are several
potential directions in which this work could be taken forward. Our safety
filter uses an off-the-shelf LLM and asks it to classify safe and harmful
prompts. One way to improve the inference cost of the filter could be to train
a dedicated classifier directly on prompts or their abstract representations
from a pre-trained network. Another interesting direction could be reducing
the subsequences checked by the erase-and-check procedure. Efficient practical
algorithms that erase less tokens from the input prompt could broaden the
scope of our framework. We hope that our contribution to certified LLM safety
helps drive future research in this field.

#### Acknowledgments

This project was supported in part by NSF CAREER AWARD 1942230, ONR YIP award
N00014-22-1-2271, ARO’s Early Career Program Award 310902-00001, HR001119S0026
(GARD), Army Grant No. W911NF2120076, NIST 60NANB20D134, the NSF award
CCF2212458, and an Amazon Research Award.

## References

  * Athalye et al. (2018) Anish Athalye, Nicholas Carlini, and David Wagner.  Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples.  In Jennifer Dy and Andreas Krause (eds.), _Proceedings of the 35th International Conference on Machine Learning_ , volume 80 of _Proceedings of Machine Learning Research_ , pp. 274–283, Stockholmsmässan, Stockholm Sweden, 10–15 Jul 2018. PMLR.  URL http://proceedings.mlr.press/v80/athalye18a.html.
  * Bai et al. (2022) Yuntao Bai, Saurav Kadavath, Sandipan Kundu, Amanda Askell, Jackson Kernion, Andy Jones, Anna Chen, Anna Goldie, Azalia Mirhoseini, Cameron McKinnon, Carol Chen, Catherine Olsson, Christopher Olah, Danny Hernandez, Dawn Drain, Deep Ganguli, Dustin Li, Eli Tran-Johnson, Ethan Perez, Jamie Kerr, Jared Mueller, Jeffrey Ladish, Joshua Landau, Kamal Ndousse, Kamile Lukosiute, Liane Lovitt, Michael Sellitto, Nelson Elhage, Nicholas Schiefer, Noemí Mercado, Nova DasSarma, Robert Lasenby, Robin Larson, Sam Ringer, Scott Johnston, Shauna Kravec, Sheer El Showk, Stanislav Fort, Tamera Lanham, Timothy Telleen-Lawton, Tom Conerly, Tom Henighan, Tristan Hume, Samuel R. Bowman, Zac Hatfield-Dodds, Ben Mann, Dario Amodei, Nicholas Joseph, Sam McCandlish, Tom Brown, and Jared Kaplan.  Constitutional AI: harmlessness from AI feedback.  _CoRR_ , abs/2212.08073, 2022.  doi: 10.48550/arXiv.2212.08073.  URL https://doi.org/10.48550/arXiv.2212.08073.
  * Biggio et al. (2013) Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Srndic, Pavel Laskov, Giorgio Giacinto, and Fabio Roli.  Evasion attacks against machine learning at test time.  In Hendrik Blockeel, Kristian Kersting, Siegfried Nijssen, and Filip Zelezný (eds.), _Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2013, Prague, Czech Republic, September 23-27, 2013, Proceedings, Part III_ , volume 8190 of _Lecture Notes in Computer Science_ , pp. 387–402. Springer, 2013.  doi: 10.1007/978-3-642-40994-3“˙25.  URL https://doi.org/10.1007/978-3-642-40994-3_25.
  * Buckman et al. (2018) Jacob Buckman, Aurko Roy, Colin Raffel, and Ian J. Goodfellow.  Thermometer encoding: One hot way to resist adversarial examples.  In _6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings_ , 2018.  URL https://openreview.net/forum?id=S18Su--CW.
  * Carlini & Wagner (2017) Nicholas Carlini and David A. Wagner.  Adversarial examples are not easily detected: Bypassing ten detection methods.  In _Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, AISec@CCS 2017, Dallas, TX, USA, November 3, 2017_ , pp. 3–14, 2017.  doi: 10.1145/3128572.3140444.  URL https://doi.org/10.1145/3128572.3140444.
  * Chen et al. (2022) Yangyi Chen, Hongcheng Gao, Ganqu Cui, Fanchao Qi, Longtao Huang, Zhiyuan Liu, and Maosong Sun.  Why should adversarial perturbations be imperceptible? rethink the research paradigm in adversarial NLP.  In Yoav Goldberg, Zornitsa Kozareva, and Yue Zhang (eds.), _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, EMNLP 2022, Abu Dhabi, United Arab Emirates, December 7-11, 2022_ , pp. 11222–11237. Association for Computational Linguistics, 2022\.  doi: 10.18653/v1/2022.emnlp-main.771.  URL https://doi.org/10.18653/v1/2022.emnlp-main.771.
  * Cohen et al. (2019) Jeremy Cohen, Elan Rosenfeld, and Zico Kolter.  Certified adversarial robustness via randomized smoothing.  In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pp. 1310–1320, Long Beach, California, USA, 09–15 Jun 2019. PMLR.
  * Dhillon et al. (2018) Guneet S. Dhillon, Kamyar Azizzadenesheli, Zachary C. Lipton, Jeremy Bernstein, Jean Kossaifi, Aran Khanna, and Animashree Anandkumar.  Stochastic activation pruning for robust adversarial defense.  In _6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings_ , 2018.  URL https://openreview.net/forum?id=H1uR4GZRZ.
  * Dvijotham et al. (2018) Krishnamurthy Dvijotham, Sven Gowal, Robert Stanforth, Relja Arandjelovic, Brendan O’Donoghue, Jonathan Uesato, and Pushmeet Kohli.  Training verified learners with learned verifiers, 2018.
  * Glaese et al. (2022) Amelia Glaese, Nat McAleese, Maja Trebacz, John Aslanides, Vlad Firoiu, Timo Ewalds, Maribeth Rauh, Laura Weidinger, Martin J. Chadwick, Phoebe Thacker, Lucy Campbell-Gillingham, Jonathan Uesato, Po-Sen Huang, Ramona Comanescu, Fan Yang, Abigail See, Sumanth Dathathri, Rory Greig, Charlie Chen, Doug Fritz, Jaume Sanchez Elias, Richard Green, Sona Mokrá, Nicholas Fernando, Boxi Wu, Rachel Foley, Susannah Young, Iason Gabriel, William Isaac, John Mellor, Demis Hassabis, Koray Kavukcuoglu, Lisa Anne Hendricks, and Geoffrey Irving.  Improving alignment of dialogue agents via targeted human judgements.  _CoRR_ , abs/2209.14375, 2022.  doi: 10.48550/arXiv.2209.14375.  URL https://doi.org/10.48550/arXiv.2209.14375.
  * Gong et al. (2017) Zhitao Gong, Wenlu Wang, and Wei-Shinn Ku.  Adversarial and clean data are not twins.  _CoRR_ , abs/1704.04960, 2017.  URL http://arxiv.org/abs/1704.04960.
  * Goodfellow et al. (2015) Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy.  Explaining and harnessing adversarial examples.  In Yoshua Bengio and Yann LeCun (eds.), _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_ , 2015.  URL http://arxiv.org/abs/1412.6572.
  * Gowal et al. (2018) Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovic, Timothy Mann, and Pushmeet Kohli.  On the effectiveness of interval bound propagation for training verifiably robust models, 2018.
  * Grosse et al. (2017) Kathrin Grosse, Praveen Manoharan, Nicolas Papernot, Michael Backes, and Patrick D. McDaniel.  On the (statistical) detection of adversarial examples.  _CoRR_ , abs/1702.06280, 2017.  URL http://arxiv.org/abs/1702.06280.
  * Guo et al. (2018) Chuan Guo, Mayank Rana, Moustapha Cissé, and Laurens van der Maaten.  Countering adversarial images using input transformations.  In _6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings_ , 2018.  URL https://openreview.net/forum?id=SyJ7ClWCb.
  * Huang et al. (2019) Po-Sen Huang, Robert Stanforth, Johannes Welbl, Chris Dyer, Dani Yogatama, Sven Gowal, Krishnamurthy Dvijotham, and Pushmeet Kohli.  Achieving verified robustness to symbol substitutions via interval bound propagation.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, EMNLP-IJCNLP 2019, Hong Kong, China, November 3-7, 2019_ , pp. 4081–4091, 2019.  doi: 10.18653/v1/D19-1419.  URL https://doi.org/10.18653/v1/D19-1419.
  * Huber et al. (2022) Lukas Huber, Marc Alexander Kühn, Edoardo Mosca, and Georg Groh.  Detecting word-level adversarial text attacks via SHapley additive exPlanations.  In _Proceedings of the 7th Workshop on Representation Learning for NLP_ , pp. 156–166, Dublin, Ireland, May 2022. Association for Computational Linguistics.  doi: 10.18653/v1/2022.repl4nlp-1.16.  URL https://aclanthology.org/2022.repl4nlp-1.16.
  * Jain et al. (2023) Neel Jain, Avi Schwarzschild, Yuxin Wen, Gowthami Somepalli, John Kirchenbauer, Ping yeh Chiang, Micah Goldblum, Aniruddha Saha, Jonas Geiping, and Tom Goldstein.  Baseline defenses for adversarial attacks against aligned language models, 2023.
  * Korbak et al. (2023) Tomasz Korbak, Kejian Shi, Angelica Chen, Rasika Vinayak Bhalerao, Christopher L. Buckley, Jason Phang, Samuel R. Bowman, and Ethan Perez.  Pretraining language models with human preferences.  In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), _International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA_ , volume 202 of _Proceedings of Machine Learning Research_ , pp. 17506–17533. PMLR, 2023.  URL https://proceedings.mlr.press/v202/korbak23a.html.
  * Laidlaw & Feizi (2019) Cassidy Laidlaw and Soheil Feizi.  Functional adversarial attacks.  In _Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada_ , pp. 10408–10418, 2019.  URL http://papers.nips.cc/paper/9228-functional-adversarial-attacks.
  * Lécuyer et al. (2019) Mathias Lécuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana.  Certified robustness to adversarial examples with differential privacy.  In _2019 IEEE Symposium on Security and Privacy, SP 2019, San Francisco, CA, USA, May 19-23, 2019_ , pp. 656–672, 2019.
  * Li et al. (2019) Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin.  Certified adversarial robustness with additive noise.  In _Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada_ , pp. 9459–9469, 2019.
  * Li & Li (2017) Xin Li and Fuxin Li.  Adversarial examples detection in deep networks with convolutional filter statistics.  In _IEEE International Conference on Computer Vision, ICCV 2017, Venice, Italy, October 22-29, 2017_ , pp. 5775–5783, 2017.  doi: 10.1109/ICCV.2017.615.  URL https://doi.org/10.1109/ICCV.2017.615.
  * Madry et al. (2018) Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu.  Towards deep learning models resistant to adversarial attacks.  In _6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings_ , 2018.  URL https://openreview.net/forum?id=rJzIBfZAb.
  * Mirman et al. (2018) Matthew Mirman, Timon Gehr, and Martin Vechev.  Differentiable abstract interpretation for provably robust neural networks.  In Jennifer Dy and Andreas Krause (eds.), _Proceedings of the 35th International Conference on Machine Learning_ , volume 80 of _Proceedings of Machine Learning Research_ , pp. 3578–3586. PMLR, 10–15 Jul 2018.  URL http://proceedings.mlr.press/v80/mirman18b.html.
  * Nguyen Minh & Luu (2022) Dang Nguyen Minh and Anh Tuan Luu.  Textual manifold-based defense against natural language adversarial examples.  In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , pp. 6612–6625, Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics.  doi: 10.18653/v1/2022.emnlp-main.443.  URL https://aclanthology.org/2022.emnlp-main.443.
  * Ouyang et al. (2022) Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul F. Christiano, Jan Leike, and Ryan Lowe.  Training language models to follow instructions with human feedback.  In _NeurIPS_ , 2022.  URL http://papers.nips.cc/paper_files/paper/2022/hash/b1efde53be364a73914f58805a001731-Abstract-Conference.html.
  * Raghunathan et al. (2018) Aditi Raghunathan, Jacob Steinhardt, and Percy Liang.  Semidefinite relaxations for certifying robustness to adversarial examples.  In _Proceedings of the 32nd International Conference on Neural Information Processing Systems_ , NIPS’18, pp. 10900–10910, Red Hook, NY, USA, 2018. Curran Associates Inc.
  * Salman et al. (2019) Hadi Salman, Jerry Li, Ilya P. Razenshteyn, Pengchuan Zhang, Huan Zhang, Sébastien Bubeck, and Greg Yang.  Provably robust deep learning via adversarially trained smoothed classifiers.  In _Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada_ , pp. 11289–11300, 2019.
  * Singla & Feizi (2020) Sahil Singla and Soheil Feizi.  Second-order provable defenses against adversarial attacks.  In _Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event_ , volume 119 of _Proceedings of Machine Learning Research_ , pp. 8981–8991. PMLR, 2020\.  URL http://proceedings.mlr.press/v119/singla20a.html.
  * Singla & Feizi (2021) Sahil Singla and Soheil Feizi.  Skew orthogonal convolutions.  In Marina Meila and Tong Zhang (eds.), _Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event_ , volume 139 of _Proceedings of Machine Learning Research_ , pp. 9756–9766. PMLR, 2021.  URL http://proceedings.mlr.press/v139/singla21a.html.
  * Szegedy et al. (2014) Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus.  Intriguing properties of neural networks.  In _2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings_ , 2014.  URL http://arxiv.org/abs/1312.6199.
  * Touvron et al. (2023) Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al.  Llama 2: Open foundation and fine-tuned chat models.  _arXiv preprint arXiv:2307.09288_ , 2023.
  * Uesato et al. (2018) Jonathan Uesato, Brendan O’Donoghue, Pushmeet Kohli, and Aäron van den Oord.  Adversarial risk and the dangers of evaluating against weak attacks.  In _Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018_ , pp. 5032–5041, 2018.  URL http://proceedings.mlr.press/v80/uesato18a.html.
  * Wei et al. (2023) Alexander Wei, Nika Haghtalab, and Jacob Steinhardt.  Jailbroken: How does LLM safety training fail?  _CoRR_ , abs/2307.02483, 2023.  doi: 10.48550/arXiv.2307.02483.  URL https://doi.org/10.48550/arXiv.2307.02483.
  * Wong & Kolter (2018) Eric Wong and J. Zico Kolter.  Provable defenses against adversarial examples via the convex outer adversarial polytope.  In _Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018_ , pp. 5283–5292, 2018.
  * Xu et al. (2020) Jing Xu, Da Ju, Margaret Li, Y-Lan Boureau, Jason Weston, and Emily Dinan.  Recipes for safety in open-domain chatbots.  _CoRR_ , abs/2010.07079, 2020.  URL https://arxiv.org/abs/2010.07079.
  * Ye et al. (2020) Mao Ye, Chengyue Gong, and Qiang Liu.  SAFER: A structure-free approach for certified robustness to adversarial word substitutions.  In Dan Jurafsky, Joyce Chai, Natalie Schluter, and Joel R. Tetreault (eds.), _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, ACL 2020, Online, July 5-10, 2020_ , pp. 3465–3475. Association for Computational Linguistics, 2020.  doi: 10.18653/v1/2020.acl-main.317.  URL https://doi.org/10.18653/v1/2020.acl-main.317.
  * Yoo et al. (2022) KiYoon Yoo, Jangho Kim, Jiho Jang, and Nojun Kwak.  Detection of adversarial examples in text classification: Benchmark and baseline via robust density estimation.  In _Findings of the Association for Computational Linguistics: ACL 2022_ , pp. 3656–3672, Dublin, Ireland, May 2022. Association for Computational Linguistics.  doi: 10.18653/v1/2022.findings-acl.289.  URL https://aclanthology.org/2022.findings-acl.289.
  * Zhang et al. (2023) Zhen Zhang, Guanhua Zhang, Bairu Hou, Wenqi Fan, Qing Li, Sijia Liu, Yang Zhang, and Shiyu Chang.  Certified robustness for large language models with self-denoising.  _CoRR_ , abs/2307.07171, 2023.  doi: 10.48550/arXiv.2307.07171.  URL https://doi.org/10.48550/arXiv.2307.07171.
  * Zhao et al. (2022) Haiteng Zhao, Chang Ma, Xinshuai Dong, Anh Tuan Luu, Zhi-Hong Deng, and Hanwang Zhang.  Certified robustness against natural language attacks by causal intervention.  In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato (eds.), _International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA_ , volume 162 of _Proceedings of Machine Learning Research_ , pp. 26958–26970. PMLR, 2022.  URL https://proceedings.mlr.press/v162/zhao22g.html.
  * Zou et al. (2023) Andy Zou, Zifan Wang, J. Zico Kolter, and Matt Fredrikson.  Universal and transferable adversarial attacks on aligned language models, 2023.