RNN-Guard: Certified Robustness Against Multi-frame Attacks for
  Recurrent Neural Networks
It is well-known that recurrent neural networks (RNNs), although widely used,
are vulnerable to adversarial attacks including one-frame attacks and
multi-frame attacks. Though a few certified defenses exist to provide
guaranteed robustness against one-frame attacks, we prove that defending
against multi-frame attacks remains a challenging problem due to their enormous
perturbation space. In this paper, we propose the first certified defense
against multi-frame attacks for RNNs called RNN-Guard. To address the above
challenge, we adopt the perturb-all-frame strategy to construct perturbation
spaces consistent with those in multi-frame attacks. However, the
perturb-all-frame strategy causes a precision issue in linear relaxations. To
address this issue, we introduce a novel abstract domain called InterZono and
design tighter relaxations. We prove that InterZono is more precise than
Zonotope yet carries the same time complexity. Experimental evaluations across
various datasets and model structures show that the certified robust accuracy
calculated by RNN-Guard with InterZono is up to 2.18 times higher than that
with Zonotope. In addition, we extend RNN-Guard as the first certified training
method against multi-frame attacks to directly enhance RNNs' robustness. The
results show that the certified robust accuracy of models trained with
RNN-Guard against multi-frame attacks is 15.47 to 67.65 percentage points
higher than those with other training methods.
Yunruo Zhang, Tianyu Du, Shouling Ji, Peng Tang, Shanqing Guo
# RNN-Guard: Certified Robustness Against Multi-frame Attacks for Recurrent Neural Networks

###### Abstract

It is well-known that recurrent neural networks (RNNs), although widely used, are vulnerable to adversarial attacks including one-frame attacks and multi-frame attacks. Though a few certified defenses exist to provide guaranteed robustness against one-frame attacks, we prove that defending against multi-frame attacks remains a challenging problem due to their enormous perturbation space. In this paper, we propose the first certified defense against multi-frame attacks for RNNs called RNN-Guard. To address the above challenge, we adopt the perturb-all-frame strategy to construct perturbation spaces consistent with those in multi-frame attacks. However, the perturb-all-frame strategy causes a precision issue in linear relaxations. To address this issue, we introduce a novel abstract domain called InterZono and design tighter relaxations. We prove that InterZono is more precise than Zonoope yet carries the same time complexity. Experimental evaluations across various datasets and model structures show that the certified robust accuracy calculated by RNN-Guard with InterZono is up to 2.18 times higher than that with Zonotope. In addition, we extend RNN-Guard as the first certified training method against multi-frame attacks to directly enhance RNNs' robustness. The results show that the certified robust accuracy of models trained with RNN-Guard against multi-frame attacks is 15.47 to 67.65 percentage points higher than those with other training methods.

 keywords.

## I Introduction

Recurrent neural networks have been widely applied in various applications, including natural language processing [26], automatic speech recognition [22], and video processing [57]. However, due to the lack of robustness, RNNs are vulnerable to adversarial attacks [7, 29, 43, 20], where adversaries add small perturbations to clean inputs to induce the target model to misclassify the perturbed inputs (termed as adversarial examples). The existence of adversarial attacks raises concerns about the safety of RNN-based applications. To improve the robustness of RNNs, earlier researchers proposed many empirical defenses based on heuristics (e.g., adversarial training [20, 40]). However, empirical defenses can often be defeated by stronger attacks due to their lack of theoretical guarantees. To provide guaranteed robustness, recently, a few _robustness certification_ methods (a.k.a. _certified defenses_) [12, 25] have been proposed for RNNs to formally verify whether a given neighbor around the clean input contains any adversarial example. Robustness certification methods can be further extended as certified training methods, which utilize the certification results for improving the model's robustness.

**Motivation.** Adversarial attacks on RNNs can be categorized into either _one-frame attacks_ where adversaries can only perturb one frame or _multi-frame attacks_ where adversaries can perturb multiple frames simultaneously. Previous certified defenses for RNNs focus on one-frame attacks. However, we discover a severe vulnerability in those works, i.e., they are vulnerable to multi-frame attacks. As shown in Fig. 1, even if the model is certified to be robust around a clean sample against one-frame attacks, multi-frame adversaries can still find its adversarial example. Thus, defending against multi-frame attacks becomes an important and urgent problem.

**This work: Certified Defense against Multi-frame Attacks.** In this paper, we address this problem and present the first certified defense against multi-frame attacks called RNN-Guard. To capture all potential adversarial examples in multi-frame attacks, we adopt the perturb-all-frame strategy (i.e., to simultaneously perturb all frames), which results in a much larger perturbation space. However, the perturb-all-frame strategy causes a precision issue. Most certified defenses apply linear relaxations to handle non-linear functions. Generally speaking, relaxations in smaller spaces are more precise because a shorter curve is closer to a straight line than a longer one. Thus, the larger perturbation space results in less precise relaxations. The precision issue can cause imprecise results of robustness certification, i.e., too many robust samples are

Fig. 1: Examples of the perturbation space in one-frame attacks (the horizontal and vertical orange line) and multi-frame attacks (the yellow circle), where the black dot is a clean input with two frames (i.e., \(x_{1}\) and \(x_{2}\)) and the red dot is an adversarial example in the multi-frame attack. (a) One-frame attack on \(x_{1}\). (b) One-frame attack on \(x_{2}\). (c) Multi-frame attack on \(x_{1}\) and \(x_{2}\).
incorrectly proven to be non-robust. To address this issue, we introduce a new abstract domain called InterZono and design tighter relaxations for non-linear functions in RNN models. InterZono consists of a main domain and a support domain, which can reduce errors in relaxations by computing the intersection of the two domains.

We comprehensively evaluate the performance of RNN-Guard across various datasets and model structures. Experimental results show that certified robust accuracy calculated by RNN-Guard with InterZono is up to 2.18 times higher than by RNN-Guard with Zonotope (a classic abstract domain used in many certified defenses), which indicates that InterZono is more precise, while they share the same efficiency. To further demonstrate RNN-Guard's practicality, we apply RNN-Guard to certify the effectiveness of existing defenses. The results show that those defenses lack robustness against multi-frame attacks, which reaffirms the exigency of this work. Furthermore, we extend RNN-Guard as a certified training method to directly improve RNNs' robustness against multi-frame attacks. The results show that the certified robust accuracy of models trained with RNN-Guard against multi-frame attacks is 15.47 to 67.65 percentage points higher than other training methods, which indicates that RNN-Guard is the best choice for defending against such attacks. We also conduct adaptive evaluations, in which the results reconfirm that RNN-Guard is more effective against multi-frame attacks.

**Our Contributions.** Our main contributions are:

* We discover a severe vulnerability in existing certified defenses for RNNs, i.e., they are challenged by multi-frame attacks due to their limited perturbation space. We theoretically prove that defending against multi-frame attacks is more difficult than against one-frame attacks.
* To address this challenge, we propose a novel certified defense with the perturb-all-frame strategy for capturing all potential adversarial examples in multi-frame attacks. To the best of our knowledge, this is the first certified defense that focuses on multi-frame attacks.
* To address the precision issue caused by the perturb-all-frame strategy, we introduce an abstract domain called InterZono and design tighter relaxations. We theoretically prove that InterZono is more precise than Zonotope while carrying the same time complexity.
* Through extensive evaluations, we show that InterZono is more precise than Zonotope while sharing the same efficiency. Moreover, we demonstrate RNN-Guard's superiority in improving RNN models' robustness against multi-frame attacks.

## II Background

### _Recurrent Neural Networks_

In this work, we apply RNNs to sequence classification tasks such as sentiment prediction and toxic content detection. The RNN model receives a sequence of variable lengths (denoted by \(T\)) composed of frames such as words or tokens and performs classification into \(C\) distinct classes.

Let \(\mathbf{X}=[\mathbf{x}^{(1)},\mathbf{x}^{(2)},\ldots,\mathbf{x}^{(t)},\ldots,\mathbf{x}^{(T)}]\) be the input sequence. As shown in Fig. 2, the RNN model updates a hidden state \(\mathbf{h}^{(t)}\) at each time step according to the current frame \(\mathbf{x}^{(t)}\) and the last hidden state \(\mathbf{h}^{(t-1)}\):

\[\mathbf{h}^{(t)}=\text{layer}(\mathbf{x}^{(t)},\mathbf{h}^{(t-1)}),\]

where \(t=1,2,\ldots,T\). The initial hidden state \(\mathbf{h}^{(0)}\) is usually set to zero. In particular, LSTM models update an additional hidden state \(\mathbf{c}^{(t)}\) called cell state. The output vector \(\mathbf{y}\in\mathbb{R}^{C}\) is calculated according to each hidden state:

\[\mathbf{y}=\mathbf{W}_{o}\cdot\mathbf{h}^{(1)}+\mathbf{W}_{o}\cdot\mathbf{h}^{(2)}+\cdots+\mathbf{W}_ {o}\cdot\mathbf{h}^{(T)}+\mathbf{b}_{o}.\]

For simplicity, we replace it with \(\mathbf{y}=\mathbf{W}_{o}\cdot\mathbf{h}^{(T)}+\mathbf{b}_{o}\).

Fig. 2: The recurrent neural network architecture for sequence classification. The cell state is unique to LSTM models.
We mainly consider three kinds of RNN models in this paper: vanilla RNN models, long short-term memory (LSTM) [23] models, and gated recurrent unit (GRU) [9] models. Each kind of model updates its hidden states differently. Vanilla RNN models update \(\mathbf{h}^{(t)}\) according to

\[\mathbf{h}^{(t)}=\text{tanh}(\mathbf{W}_{x}\mathbf{x}^{(t)}+\mathbf{b}_{x}+\mathbf{W}_{h}\mathbf{h}^{(t- 1)}+\mathbf{b}_{h}).\]

LSTM models update \(\mathbf{h}^{(t)}\) and \(\mathbf{c}^{(t)}\) according to

\[\mathbf{i}^{(t)} =\sigma(\mathbf{W}_{x{}i}\mathbf{x}^{(t)}+\mathbf{b}_{xi}+\mathbf{W}_{hi}\mathbf{h}^{(t -1)}+\mathbf{b}_{hi}),\] \[\mathbf{f}^{(t)} =\sigma(\mathbf{W}_{x{}f}\mathbf{x}^{(t)}+\mathbf{b}_{xf}+\mathbf{W}_{hf}\mathbf{h}^{( t-1)}+\mathbf{b}_{hf}),\] \[\mathbf{g}^{(t)} =\text{tanh}(\mathbf{W}_{xg}\mathbf{x}^{(t)}+\mathbf{b}_{xg}+\mathbf{W}_{hg}\mathbf{h }^{(t-1)}+\mathbf{b}_{hg}),\] \[\mathbf{o}^{(t)} =\sigma(\mathbf{W}_{x{}o}\mathbf{x}^{(t)}+\mathbf{b}_{x{}o}+\mathbf{W}_{ho}\mathbf{h}^ {(t-1)}+\mathbf{b}_{ho}),\] \[\mathbf{c}^{(t)} =\mathbf{f}^{(t)}\odot\mathbf{c}^{(t-1)}+\hat{\mathbf{i}}^{(t)}\odot\mathbf{g}^{( t)},\] \[\mathbf{h}^{(t)} =\mathbf{o}^{(t)}\odot\text{tanh}(\mathbf{c}^{(t)}),\]

where \(\odot\) is the Hadamard product.

GRU models update \(\mathbf{h}^{(t)}\) according to

\[\mathbf{r}^{(t)} =\sigma(\mathbf{W}_{x{}r}\mathbf{x}^{(t)}+\mathbf{b}_{x{}r}+\mathbf{W}_{hr}\mathbf{h}^ {(t-1)}+\mathbf{b}_{hr}),\] \[\mathbf{z}^{(t)} =\sigma(\mathbf{W}_{xz}\mathbf{x}^{(t)}+\mathbf{b}_{xz}+\mathbf{W}_{hz}\mathbf{h}^{(t -1)}+\mathbf{b}_{hz}),\] \[\mathbf{n}^{(t)} =\text{tanh}(\mathbf{W}_{xn}\mathbf{x}^{(t)}+\mathbf{b}_{xn}\] \[\quad+\mathbf{r}^{(t)}\odot(\mathbf{W}_{hn}\mathbf{h}^{(t-1)}+\mathbf{b}_{hn})),\] \[\mathbf{h}^{(t)} =(1-\mathbf{z}^{(t)})\odot\mathbf{n}^{(t)}+\mathbf{z}^{(t)}\odot\mathbf{h}^{(t-1)}.\]

### _Adversarial Attacks on RNNs_

According to the number of frames in the input sequence that adversaries can perturb, adversarial attacks on RNNs are categorized into one-frame attacks or multi-frame attacks [12].

#### Ii-B1 One-frame Attacks

One-frame attacks are adversarial attacks where the adversary can only perturb one frame and keep the others unchanged, which are considered in the previous works on certified defenses for RNNs [12, 25]. For a clean input sequence \(\mathbf{X}_{c}=[\mathbf{x}_{c}^{(1)},\mathbf{x}_{c}^{(2)},\ldots,\mathbf{x}_{c}^{(t)},\ldots, \mathbf{x}_{c}^{(T)}]\), the one-frame adversarial example \(\mathbf{X}_{adv}^{(t)}\) can be any sequence that satisfies:

\[\mathbf{X}_{adv}^{(t)}=[\mathbf{x}_{c}^{(1)},\mathbf{x}_{c}^{(2)},\ldots,\mathbf{x }_{c}^{(t-1)},\mathbf{x}_{adv}^{(t)},\mathbf{x}_{c}^{(t+1)},\ldots,\mathbf{x}_{c}^{(T)}],\] \[\|\mathbf{x}_{c}^{(t)}-\mathbf{x}_{adv}^{(t)}\|_{p}\leq\varepsilon,\mathbf{f} _{p}(\mathbf{X}_{adv}^{(t)})\neq\mathbf{f}_{p}(\mathbf{X}),t=1,2,\ldots,T,\]

where \(\mathbf{f}_{p}\) returns the target model's prediction on the input.

However, perturbing one frame is not always enough to achieve a successful attack. Thus, to ensure a high success rate, most attacks in practice (e.g., DeepWordBug [17] and BERT-Attack [27]) usually try to perturb more frames together until an adversarial example is found, which are referred to as multi-frame attacks.

#### Ii-B2 Multi-frame Attacks

Multi-frame attacks are adversarial attacks where the adversary can perturb multiple (partial or all) frames in the input sequence. The perturbation on each perturbed frame is also constrained within a given length. For example, the worst-case adversarial example \(\mathbf{X}_{adv}\) where all frames are perturbed satisfies:

\[\mathbf{X}_{adv}=[\mathbf{x}_{adv}^{(1)},\mathbf{x}_{adv}^{(2)},\ldots,\mathbf{ x}_{adv}^{(t-1)},\mathbf{x}_{adv}^{(t)},\mathbf{x}_{adv}^{(t+1)},\ldots,\mathbf{x}_{adv}^{(T)}],\] \[\|\mathbf{x}_{c}^{(t)}-\mathbf{x}_{adv}^{(t)}\|_{p}\leq\varepsilon,\mathbf{f} _{p}(\mathbf{X}_{adv}^{(t)})\neq\mathbf{f}_{p}(\mathbf{X}),t=1,2,\ldots,T.\]

### _Zonotope Certification_

This work builds upon the Zonotope [19] abstract domain, which was used in many certified defenses [12, 30].

#### Ii-C1 Zonotope

A Zonotope \(\mathcal{Z}\) that abstracts \(n\) variables consists of a center \(\mathbf{\alpha}_{0}\) and \(N\) error terms:

\[\mathcal{Z}=\mathbf{\alpha}_{0}+\sum_{i=1}^{N}\mathbf{\alpha}_{i}\cdot\epsilon_{i},\]

where \(\mathbf{\alpha}_{0},\mathbf{\alpha}_{i}\in\mathbb{R}^{n}\) and \(\epsilon_{i}\in[-1,1](i=1,2,\ldots,N)\).

#### Ii-C2 Concetization

The numerical bounds of the variables can be derived using the following equation:

\[\mathbf{l}=\mathbf{\alpha}_{0}-\sum_{i=1}^{N}|\mathbf{\alpha}_{i}|,\ \mathbf{u}=\mathbf{\alpha}_{0}+\sum_{i=1}^{N}|\mathbf{ \alpha}_{i}|, \tag{1}\]

where \(\mathbf{l}\in\mathbb{R}^{n}\) and \(\mathbf{u}\in\mathbb{R}^{n}\) are the lower and upper bound, respectively.

#### Ii-C3 Affine Abstract Transformer

Given an affine transformation \(\mathbf{W}\cdot\mathbf{x}+\mathbf{b}\), its abstract transformer for \(\mathbf{W}\cdot\mathcal{Z}+\mathbf{b}\) is defined as follows:

\[\mathbf{W}\cdot\mathcal{Z}+\mathbf{b}=\mathbf{W}\cdot\mathbf{\alpha}_{0}+\mathbf{b}+\sum_{i=1}^{N }\mathbf{W}\cdot\mathbf{\alpha}_{i}\cdot\epsilon_{i}. \tag{2}\]

Fig. 3: Comparison of relaxations for tanh. Our relaxed area is smaller than others. (a) Box-style relaxation. (b) Parallelogram-style relaxation. (c) Ours.
#### Ii-B4 Non-linear Abstract Transformer

Abstract transformers for non-linear functions adopt relaxations to over-approximate the output. Take the tanh function as an example. There are different abstract transformers for the tanh function, we describe the one used in Cert-RNN, as shown in Fig. 2(b). Given an input Zonotope \(\mathcal{Z}\), the abstract transformer first computes the numerical bounds, \(\mathbf{l}\) and \(\mathbf{u}\), using Equation 1. Then, it computes two parallel bounding lines that minimize their distance for each variable. Let \(y=k_{j}x+c_{j}\) and \(y=k_{j}x+d_{j}\) be the upper and lower bound line of the \(j\)-th variable, where \(k_{j}=(\text{tanh}(u_{j})-\text{tanh}(l_{j}))/(u_{j}-l_{j}),j=1,\ldots,n\). The output domain of the abstract transformer is:

\[\text{tanh}(\mathcal{Z})=\mathbf{\alpha}_{0}\odot\mathbf{k}+\frac{\mathbf{c}+ \mathbf{d}}{2}+\sum_{i=1}^{N}\mathbf{\alpha}_{i}\odot\mathbf{k}\cdot\epsilon_{i}\] \[+\sum_{j=1}^{n}\frac{c_{j}-d_{j}}{2}\cdot\mathbf{e}_{j}\cdot\epsilon _{N+j}, \tag{3}\]

where \(\mathbf{k}=(k_{1},k_{2},\ldots,k_{n})^{\mathsf{T}}\), \(\mathbf{c}=(c_{1},c_{2},\ldots,c_{n})^{\mathsf{T}}\), \(\mathbf{d}=(d_{1},d_{2},\ldots,\)\(d_{n})^{\mathsf{T}}\), and \(\mathbf{e}_{i}\) is the \(i\)-th standard basis vector.

In LSTM and GRU models, there are some unique operations that are more complex, such as the Hadamard product between a sigmoid function and a tanh function. Since the Hadamard product depends on two variables, the corresponding abstract transformer computes two planes instead of lines. The rest calculation is similar to that in the tanh abstract transformer. Due to the limited space, we omit the computational details, please refer to [12].

#### Ii-B5 Certification and Certified Training

To certify the target model's robustness in a perturbation space, certification methods first abstract the perturbation space as a Zonotope. Then, they propagate the Zonotope through the model using abstract transformers. Thus, they obtain an output Zonotope that is an over-approximation of the model's all possible outputs. Finally, let \(y_{t}\) be the output of the correct class and \(y_{f}\) be the incorrect class's, the robustness is proven if the lower bound of \(y_{t}-y_{f}\) is positive. Furthermore, certification methods can be extended as certified training methods by training models with a robustness loss \(l\) computed according to the output Zonotope \(\mathcal{Z}_{o}\). For example, \(l=\max_{\mathbf{y}\in\mathcal{Z}_{o}}l_{ce}(\mathbf{y},l_{t})\), where \(l_{ce}\) is the Cross-Entropy loss and \(l_{t}\) denotes the label of the correct class. However, certified training methods that improve the model's robustness also cause a decrease in its clean accuracy. To mitigate this problem, existing works [54] usually use a linear combination of the robustness loss and the standard loss.

## III Motivation

In this section, we demonstrate the vulnerability in existing certified defenses [12, 25] by proving that defending against multi-frame attacks is more difficult than defending against one-frame attacks.

### _Defense Strategy_

Let \(\mathcal{S}^{(t)}=\{\mathbf{x}^{(t)}:\|\mathbf{x}^{(t)}-\mathbf{x}_{c}^{(t)}\|_{p}\leq\varepsilon\}\) be the perturbation space (i.e., the neighborhood contains all potential adversarial examples) of the \(t\)-th frame.

Previous works focus on one-frame attacks and thus adopt _the perturbo-frame strategy_, which considers the perturbation space of the one-frame adversary:

\[\mathcal{S}_{1}=\bigcup_{t=1}^{T}\mathcal{S}_{1}^{(t)}=\bigcup_{t =1}^{T}\{\mathbf{X}:\mathbf{x}^{(1)}=\mathbf{x}_{c}^{(1)},\ldots,\mathbf{x}^{(t-1)}=\mathbf{x}_{c}^ {(t-1)},\] \[\mathbf{x}^{(t)}\in\mathcal{S}^{(t)},\mathbf{x}^{(t+1)}=\mathbf{x}_{c}^{(t+1) },\ldots,\mathbf{x}^{(T)}=\mathbf{x}_{c}^{(T)}\}.\]

Aiming at defending against multi-frame attacks, we adopt _the perturbo-all-frame strategy_, which considers the perturbation space of the worst-case multi-frame adversary:

\[\mathcal{S}_{2}=\{\mathbf{X}:\mathbf{x}^{(1)}\in\mathcal{S}^{(1)},\ldots,\mathbf{x}^{(t)} \in\mathcal{S}^{(t)},\ldots,\mathbf{x}^{(T)}\in\mathcal{S}^{(T)}\}.\]

**Lemma 1**: \(\mathcal{S}_{1}\) _is a proper subset of \(\mathcal{S}_{2}\)._

**Proof of Lemma 1**: _On the one hand, according to their definitions, \(\mathcal{S}_{1}^{(t)}\) is a subset of \(\mathcal{S}_{2},t=1,2,\ldots,T\). Since \(\mathcal{S}_{1}\) is the union of all \(\mathcal{S}_{1}^{(t)}\)s, \(\mathcal{S}_{1}\) is also a subset of \(\mathcal{S}_{2}\). On the other hand, we can find an element \(\mathbf{X}_{adv}=[\mathbf{x}_{adv}^{(1)},\mathbf{x}_{adv}^{(2)},\ldots,\mathbf{x}_{adv}^{(T)}]\) in \(\mathcal{S}_{2}\) but not in \(\mathcal{S}_{1}\), where \(\mathbf{x}_{adv}^{(t)}\in\mathcal{S}^{(t)},\mathbf{x}_{adv}^{(t)}\neq\mathbf{x}_{c}^{(t)},t =1,2,\ldots,T\). In conclusion, \(\mathcal{S}_{1}\) is a proper subset of \(\mathcal{S}_{2}\). \(\square\)_

**Theorem 1**: _A model that is robust against multi-frame attacks around a clean sample \(\mathbf{X}_{c}\) is also robust against one-frame attacks around \(\mathbf{X}_{c}\), but not vice versa._

_Proof of Theorem 1: _On the one hand, the model is robust against multi-frame attacks around \(\mathbf{X}_{c}\) indicates that all samples in \(\mathcal{S}_{2}\) are robust. Since \(\mathcal{S}_{1}\) is a proper subset of \(\mathcal{S}_{2}\), all samples in \(\mathcal{S}_{1}\) must be robust. Thus, the model is also robust against one-frame attacks around \(\mathbf{X}_{c}\). On the other hand, the model is robust against one-frame attacks around \(\mathbf{X}_{c}\) only indicates that all samples in \(\mathcal{S}_{1}\) are robust. As for samples in \(\mathcal{S}_{2}-\mathcal{S}_{1}\), their robustness is uncertain. Thus, there can be adversarial examples in \(\mathcal{S}_{2}\). \(\square\)_

### _Challenges_

While the perturbo-all-frame strategy offers a stronger guarantee of models' robustness, however, it also causes a precision issue. Most existing certified defenses apply linear relaxations to handle non-linear functions. As shown in Fig. 4, relaxations in smaller spaces are more precise because a shorter curve is closer to a straight line than a longer one. As a result, larger perturbation spaces lead to less precise relaxations, which brings an intractable challenge to robustness certification against multi-frame attacks.

Fig. 4: Examples of perturbation space’s effect on the linear relaxations of tanh. The orange and blue areas are the linear relaxation when the perturbation space is \([0,1]\) and \([0,2]\), respectively.
## IV Methodology

In this section, we present RNN-Guard, the first certified defense against multi-frame attacks for RNN models.

### _Overview_

#### Iv-A1 Threat Model

We focus on white-box multi-frame adversarial attacks, which indicate the strongest adversary who has full knowledge about the target model (including its parameters and architecture) and can perturb all frames in its input sequence simultaneously by adding \(\ell_{p}(p=\infty)\) noises to their embeddings (as we introduced in Section II-B).

#### Iv-A2 Robustness Certification

To certify RNN model's robustness against multi-frame attacks, we first construct an InterZono capturing all potential adversarial examples. Then, we propagate the InterZono through the model using our abstract transformers. The output InterZono we obtain is an over-approximation of the model's all possible outputs. Finally, we certify the model's robustness by confirming whether \(y_{t}-y_{f}\) is positive, where \(y_{t}\) and \(y_{f}\) are the correct and incorrect class's outputs, respectively.

#### Iv-A3 Certified Training

To improve RNN model's robustness against multi-frame attacks, we first compute the output InterZono \(\mathcal{D}_{o}\) by propagating the perturbation space through the model. Then, we calculate a robustness loss \(l=\max_{\mathbf{y}\in\mathcal{D}_{s}}l_{ce}(\mathbf{y},l_{t})\), where \(l_{ce}\) is the Cross-Entropy loss, and \(l_{t}\) denotes the label of the correct class. We combine the robustness loss with the standard loss to improve both the robustness and clean accuracy of the model. Finally, we update the model's parameters through training according to the combined loss.

### _InterZono_

#### Iv-B1 InterZono

We present a novel abstract domain called InterZono to address the precision issue caused by the perturb-all-frame strategy.

**Definition 1 (InterZono):** An InterZono \(\mathcal{D}\) is an intersection between two Zonotopes, which are the main domain \(\mathcal{Z}_{m}\) and the support domain \(\mathcal{Z}_{s}\):

\[\mathcal{D}=\mathcal{Z}_{m}\cap\mathcal{Z}_{s}.\]

The main domain propagates the relations of variables through the model and the support domain is designed to refine the main domain for improving the precision.

#### Iv-B2 Concretization

Given an InterZono \(\mathcal{D}\), we first calculate the lower and upper bound for \(\mathcal{Z}_{m}\) (i.e., \(\mathbf{l}_{m}\) and \(\mathbf{u}_{m}\)) and \(\mathcal{Z}_{s}\) (i.e., \(\mathbf{l}_{s}\) and \(\mathbf{u}_{s}\)) according to Equation 1. Then, the lower and upper bound of \(\mathcal{D}\), i.e., \(\mathbf{l}\) and \(\mathbf{u}\), are computed as follows:

\[\mathbf{l}=\max\{\mathbf{l}_{m},\mathbf{l}_{s}\},\ \mathbf{u}=\min\{\mathbf{u}_{m},\mathbf{u}_{s}\}, \tag{4}\]

where the maximum and minimum are taken in an element-wise manner.

#### Iv-B3 Affine Abstract Transformer

The affine abstract transformer of InterZono is simple. We apply the affine abstract transformer of Zonotope to the main domain and the support domain according to the Equation 2. The outputs of the main domain and the support domain are the main domain and the support domain of the new InterZono, respectively.

#### Iv-B4 Non-linear Abstract Transformer

Unlike the affine abstract transformer, both the main domain and the support domain of the new InterZono are computed mainly based on the main domain of the input InterZono. We continue to use the tanh abstract transformer as an example. Given an InterZono \(\mathcal{D}\), we first calculate its lower and upper bound \(\mathbf{l}\) and \(\mathbf{u}\) according to Equation 4. Then, we apply the parallelogram-style abstract transformer to the main domain \(\mathcal{Z}_{m}\), according to Equation 3. The output zonotope is denoted by \(\mathcal{Z}_{m}^{\prime}\). Note that we compute the \(\mathbf{k}\) in Equation 3 according to the bounds of \(\mathcal{D}\) rather than \(\mathcal{Z}_{m}\). Next, we compute the output's support domain \(\mathcal{Z}_{s}^{\prime}\) as follows (i.e., the box-style abstract transformer)

\[\mathcal{Z}_{s}^{\prime}=\frac{\mathbf{u}+\mathbf{l}}{2}+\sum_{i=1}^{n}\frac{u_{i}-l_ {i}}{2}\cdot\mathbf{e}_{i}\cdot\epsilon_{i}, \tag{5}\]

where \(u_{i}\) and \(l_{i}\) are the \(i\)-th component of \(\mathbf{l}\) and \(\mathbf{u}\), respectively. Finally, the output InterZono \(\mathcal{D}^{\prime}\) is \(\mathcal{Z}_{m}^{\prime}\cap\mathcal{Z}_{s}^{\prime}\).

For complex operation in LSTM and GRU models, e.g., the Hadamard product between a sigmoid function and a tanh function \(\sigma(x)\odot\text{tanh}(y)\), our abstract transformer is constructed in a similar way. Let \(\mathcal{D}_{x}=\mathcal{Z}_{x,m}\cap\mathcal{Z}_{x,s}\) and \(\mathcal{D}_{y}=\mathcal{Z}_{y,m}\cap\mathcal{Z}_{y,s}\) be two InterZonos. To calculate the output of \(\sigma(\mathcal{D}_{x})\odot\text{tanh}(\mathcal{D}_{y})\), denoted by \(\mathcal{D}_{z}\), we first calculate the lower and upper bounds of \(\mathcal{D}_{x}\) and \(\mathcal{D}_{y}\), denoted by \(\mathbf{l}_{x},\mathbf{u}_{x}\) and \(\mathbf{l}_{y},\mathbf{u}_{y}\), respectively. Then, we apply the abstract transformer for \(\sigma(x)\odot\text{tanh}(y)\) in Cert-RNN to \(\mathcal{Z}_{x,m}\) and \(\mathcal{Z}_{y,m}\), but replace the lower and upper bounds of \(\mathcal{Z}_{x,m}\) and \(\mathcal{Z}_{y,m}\) with the corresponding bounds of \(\mathcal{D}_{x}\) and \(\mathcal{D}_{y}\). Let \(\mathcal{Z}_{z,m}\) denote \(\sigma(\mathcal{Z}_{x,m})\odot\text{tanh}(\mathcal{Z}_{y,m})\). Next, we calculate the support domain of \(\mathcal{D}_{z}\), denoted by \(\mathcal{Z}_{z,s}\), as follows.

\[\mathcal{Z}_{z,s}=\frac{\mathbf{u}+\mathbf{l}}{2}+\sum_{i=1}^{n}\frac{u_{i}-l_{i}}{2} \cdot\mathbf{e}_{i}\cdot\epsilon_{i},\]

\[\mathbf{l}=\min\{\sigma(\mathbf{l}_{x})\odot\text{tanh}(\mathbf{l}_{y}),\sigma(\mathbf{u}_{x}) \odot\text{tanh}(\mathbf{l}_{y})\},\]

\[\mathbf{u}=\max\{\sigma(\mathbf{l}_{x})\odot\text{tanh}(\mathbf{u}_{y}),\sigma(\mathbf{u}_{x}) \odot\text{tanh}(\mathbf{u}_{y})\},\]

where the maximum and minimum are taken in an element-wise manner and \(\mathbf{l},\mathbf{u}\in\mathbb{R}^{n}\). Finally, the output InterZono \(\mathcal{D}_{z}\) is \(\mathcal{Z}_{z,m}\cap\mathcal{Z}_{z,s}\).

#### Iv-B5 Tightness

We prove that InterZono is tighter than Zonotope.

**Theorem 2:** The output InterZono \(\mathcal{D}^{\prime}\) is a tighter over-approximation (super-set) of \(\mathcal{Z}_{m}\)'s image under tanh.

Proof:: Let \(\mathcal{G}\) be the exact image of \(\mathcal{Z}_{m}\) under the tanh function. Since the parallelogram-style abstract transformer calculates the over-approximation of \(\mathcal{Z}_{m}\), \(\mathcal{G}\) is a subset of \(\mathcal{Z}_{m}^{\prime}\). Meanwhile, since the box-style abstract transformer can be considered as a special case of parallelogram-style abstract transformer (\(\mathbf{k}=0\)), \(\mathcal{G}\) is also a subset of \(\mathcal{Z}_{s}^{\prime}\). Thus, \(\mathcal{G}\) is a subset of \(\mathcal{D}^{\prime}\). Moreover, since \(\mathcal{D}^{\prime}\) is the intersection between \(\mathcal{Z}_{m}^{\prime}\) and \(\mathcal{Z}_{s}^{\prime}\), \(\mathcal{D}^{\prime}\) is tighter than any of them. This conclusion also holds for other activation function such as sigmoid. 

We provide an example in Fig. 5 to support Theorem 2.

#### Iv-B6 Efficiency

We prove that InterZono is as efficient as Zonotope.

**Theorem 3:** The time complexity of InterZono's abstract transformers are equal to those of Zonotope's.
Proof of Theorem 3.: Let \(T_{Z}(n)=O(f_{Z}(n))\) be the time complexity of Zonotope's linear abstract transformer. According the definition of InterZono's linear abstract transformer, its time complexity is \(T_{D}(n)=O(f_{Z}(n))+O(f_{Z}(n))=O(f_{Z}(n))=T_{Z}(n)\). Let \(T^{\prime}_{Z}(n)=O(f^{\prime}_{Z}(n))\) be the time complexity of Zonotope's non-linear abstract transformer. According the definition of InterZono's non-linear abstract transformer, the time complexity of calculating \(\mathcal{Z}^{\prime}_{m}\), denoted as \(T^{\prime}_{m}(n)\), is equal to \(O(f^{\prime}_{Z}(n))\). Since the box-style abstract transformer is a special case of parallelogram-style abstract transformer without calculating and multiplying \(\mathbf{k}\), the time complexity of calculating \(\mathcal{Z}^{\prime}_{s}\), denoted as \(T^{\prime}_{s}(n)\), is no larger than \(O(f^{\prime}_{Z}(n))\). Thus, the time complexity of InterZono's non-linear abstract transformer is \(T^{\prime}_{D}(n)=T^{\prime}_{m}(n)+T^{\prime}_{s}(n)=O(f^{\prime}_{Z}(n))=T^{ \prime}_{Z}(n)\). 

## V Evaluation

In this section, we evaluate the performance of RNN-Guard on robustness certification against multi-frame attacks. To the best of our knowledge, RNN-Guard is the first robustness certification method against multi-frame attacks. Since there is no existing baseline method, we use RNN-Guard with the classic abstract domain Zonotope as the baseline method.

### _Experimental Settings_

#### V-A1 Models

We use LSTM models and GRU models, which consist 32 and 64 hidden neurons (consistent with those used in previous work [12]). We refer to them as LSTM-32, LSTM-64, GRU-32, and GRU-64 in the following.

#### V-A2 Datasets

We use two datasets in our evaluation.

(i) _Rotten Tomatoes Movie Review (RT)_ dataset [32], which is a benchmark corpus of movie reviews used for sentiment analysis. The RT dataset contains about 39000 and 4800 samples in the training set and the testing set, respectively.

(ii) _Yelp Reviews Polarity (Yelp)_ dataset [56], which is a large text classification benchmark. The Yelp dataset contains about 560000 and 38000 samples in the training set and the testing set, respectively.

#### V-A3 Hardware

All experiments are conducted on a server with an Intel Core i9-10920X CPU running at 3.50 GHz, 128 GB memory, 4TB HDD, and a GeForce RTX 3090 GPU card.

#### V-A4 Word Embedding

We use the _GloVe_ model [35] to map the words into embeddings and normalize the word embeddings to reduce their internal covariate shift. For the out-of-vocabulary words, we randomly sample from the uniform distribution in \([-0.1,0.1]\) for initialization. On vanilla RNN models, we use the pre-trained model 'glove.840B.300d'. On LSTM and GRU models, due to the limited GPU memory, we use the smaller model 'glove.6B.50d'.

#### V-A5 Evaluation Metrics

We consider the following metrics: (i) the _certified robust accuracy_ (C.Acc.) at \(\varepsilon_{e}\) on a dataset is the fraction of samples that are guaranteed (by robustness certification) to be robust within a neighborhood of theirs with radius equal to \(\varepsilon_{e}\) in the test set, which can be seen as the lower bound of the target model's robustness;

(ii) the _running time_ of a method on a dataset is running time of the robustness certification method to certify the robustness of all samples in the testing set.

### _Results and Analysis_

We compare RNN-Guard with InterZono to RNN-Guard with Zonotope across four models and two datasets to demonstrate the advantages of InterZono.

First, we compare the precision of Zonotope and InterZono. As we mentioned earlier, most certified defenses adopt linear relaxations to handle non-linear functions in the model, which causes the precision issue that eventually leads them to mistakenly certify that certain robust samples are non-robust. Thus, improving the precision of robustness certification is one of the most important research directions in this area. The precision of a robustness certification method is usually measured by the certified robust accuracy it computes. The more precise a method is, the more samples it can certify the robustness of, thus the higher certified robust accuracy it computes.

As shown in Table. I and Fig. 6, certified robust accuracy computed using InterZono is higher than that computed using Zonotope. For example, for the LSTM-32 model on the RT dataset, RNN-Guard with Zonotope proves that 6.80% samples are robust while RNN-Guard with InterZono proves that 14.81% samples are robust. The reason for advantage of InterZono is that InterZono uses an additional support domain to refine the bounds. Thus, InterZono is more precise than Zonotope.

Fig. 5: An example of different relaxations for tanh. The grey area is the exact image of the input domain under tanh. (a) Input domain. (b) Box-style relaxation’s output domain. (c) Parallelogram-style relaxation’s output domain. (d) Ours.
Moreover, we observe that the precision improvement of InterZono is more obvious in LSTM models than in GRU models. This is because LSTM models involve more variables and use more non-linear functions and our advantage comes from the relaxation of non-linear functions. Hence, our method is more precise, especially on complex models with more non-linear functions.

Then, we compare the efficiency of Zonotope and InterZono. As shown in Table. I, the running time of RNN-Guard with InterZono is very close to those with Zonotope. For example, for the LSTM-64 model on the RT dataset, RNN-Guard with Zonotope takes 73.5 seconds to certify the robustness of all samples in the testing set while RNN-Guard with InterZono takes 73.6 seconds. This can be explained by Theorem 3. Thus, InterZono is as efficient as Zonotope.

In conclusion, we believe that InterZono is a better choice for certifying the robustness of RNN models.

## VI Application

Robustness certification has many important applications, such as certifying the effectiveness of different defenses [18] and designing new defenses by improving the certified robustness of the target model (i.e., certified training) [30]. In this section, we apply RNN-Guard in the above applications to further demonstrate its practicality and benefits.

### _Certifying Existing Defenses_

In this subsection, we certify the effectiveness of existing defenses, including the _standard training_ without any defense, two _adversarial training_ methods (i.e., AT-FGSM [20] and AT-PGD [29]), and two _certified training_ methods (i.e., POPQORN+ [25] and Cert-RNN [12]). Note that Cert-RNN failed to train several large models due to timeout or running out of GPU memory.

#### Vi-A1 Experimental Settings

_Models._ We consider three different kinds of RNN models, i.e., vanilla RNN models, LSTM models, and GRU models. We will refer to them as RNN-32 (R-32), RNN-64 (R-64), LSTM-32 (L-32), LSTM-64 (L-64), GRU-32 (G-32), and GRU-64 (G-64) in the following. _Dataset_. In addition to the RT and Yelp datasets, we use the _Toxic Comment (TC)_ dataset [10] provided by Kaggle, which is also used in the evaluation of Cert-RNN. To be consistent with Cert-RNN, we also perform binary classification on this dataset by reclassifying the six toxicity categories as one. We randomly sample a balanced subset of this dataset for evaluation. _Implementation Details._ Though POPQORN [25] is proposed to quantify the robustness of RNN models, we modify it for certified training and refer to it as 'POPQORN+'. The rest settings are consistent with those in Section V-A.

#### Vi-A2 Results and Analysis

The results are shown in Tab. II and Fig. 7, from which we have the following observations.

First, the standard training method achieves nearly zero certified robust accuracy in Tab. II. This indicates that models trained by it lack robustness, which is already widely acknowledged by the security community. Second, adversarial training methods achieve higher but limited certified robust accuracy than the standard training method. For example, AT-FGSM and AP-PGD achieve 13.99% and 29.58% certified robust accuracy at \(\varepsilon_{e}=0.03\) for the LSTM-32 model on the Yelp dataset, respectively. The reason for such limited robustness is that they are based on heuristics and thus lack theoretical guarantees. Finally, existing certified training methods achieve relatively low certified robust accuracy. For instance, POPQORN+ and Cert-RNN achieve 0.97% and 0.69% certified robust accuracy at \(\varepsilon_{e}=0.03\) for the LSTM-32 model on the RT dataset, respectively. The reason for such low robustness is that they focus on one-frame attacks and defending against multi-frame attacks is more difficult.

Fig. 6: Certified robust accuracy of the four models on the RT and Yelp dataset at different \(\varepsilon_{e}\) computed using Zonotope and InterZono. (a) RT LSTM-32. (b) RT LSTM-64. (c) RT GRU-32. (d) RT GRU-64. (e) Yelp LSTM-32. (f) Yelp LSTM-64. (g) Yelp GRU-32. (h) Yelp GRU-64.
In conclusion, multi-frame attacks pose a significant challenge to the effectiveness of existing defenses.

### _Improving RNN's Robustness_

To address the security challenge posed by multi-frame attacks, we extend our certification method, i.e., RNN-Guard, as a _certified training_ method and compare it to existing defenses to demonstrate its advantages.

#### Vi-B1 Experimental Settings

We consider the following metrics: (i) the _certified robust accuracy_, which is explained in Section V-A; (ii) the _empirical robust accuracy_ (E.Acc.) at \(\varepsilon_{e}\) on a dataset is the fraction of samples that adversarial attackers failed to attack within a neighborhood of theirs with a radius equal to \(\varepsilon_{e}\) in the test set, which can be seen as the upper bound of the target model's robustness; (iii) the _clean accuracy_ (Acc.) on a dataset is the fraction of samples that is correctly classified in the test set; (iv) the _running time_ of a method on a dataset is running time of the certified training method to train the target model for one epoch on the training set. The rest settings are consistent with those in Section VI-A.

#### Vi-B2 Results and Analysis

The results are shown in Tab. II, III, IV, V, and Fig. 7, from which we have the following observations.

First, as shown in Tab. II and Fig. 7, RNN-Guard achieves the highest certified robust accuracy across different models and datasets. For example, RNN-Guard achieved \(64.05\%\) certified robust accuracy at \(\varepsilon_{e}=0.03\) for the RNN-64 model on the RT dataset and the second-best method only reaches \(9.04\%\) certified robust accuracy. RNN-Guard attains better performance than adversarial training methods because it provides theoretical guarantees for RNN models' robustness. RNN-Guard outperforms existing certified training methods because we focus on multi-frame attacks that is more difficult to defend against. Roughly speaking, let \(|\mathcal{S}^{(t)}|\) be the number of potential adversarial examples in \(\mathcal{S}^{(t)}\) (see details in Section III-A), which is a very large number, existing certified training methods improve the robustness of samples in \(\mathcal{S}_{1}\), whose number is \(|\mathcal{S}_{1}|=|\mathcal{S}^{(1)}|+|\mathcal{S}^{(2)}|+\cdots+|\mathcal{ S}^{(T)}|\). Meanwhile, RNN-Guard improves the robustness of samples in \(\mathcal{S}_{2}\) and their number is \(|\mathcal{S}_{2}|=|\mathcal{S}^{(1)}|\times|\mathcal{S}^{(2)}|\times\cdots \times|\mathcal{S}^{(T)}|\). As

Fig. 7: Certified robust accuracy of RNN models. On the RT dataset, we train two models with \(\varepsilon_{t}=0.03\) for each defense and record their certified robust accuracy in \(0\leq\varepsilon_{e}\leq 0.06\). On the TC dataset, we train two models with \(\varepsilon_{t}=0.05\) for each defense and record their certified robust accuracy in \(0\leq\varepsilon_{e}\leq 0.1\). (a) RT RNN-32. (b) RT RNN-64. (c) TC RNN-32. (d) TC RNN-64. (e) RT LSTM-32. (f) RT LSTM-64. (g) Yelp LSTM-32. (h) Yelp LSTM-64. (i) RT GRU-32. (j) RT GRU-64. (k) Yelp GRU-32. (l) Yelp GRU-32. (l) Yelp GRU-64.
we can see, \(|\mathcal{S}_{2}|\) is far larger than \(|\mathcal{S}_{1}|\), which explains why POPQORN+ and Cert-RNN achieve such low certified robust accuracy against multi-frame attacks. Moreover, we further validate RNN-Guard's advantages by recording certified robust accuracy of different defenses at different radii in Fig. 7. As shown in Fig. 7, RNN-Guard achieves the highest certified robust accuracy at almost all \(\varepsilon_{e}\), which indicates that the advantages of RNN-Guard are general and do not rely on a specific radius. For instance, the certified robust accuracy of RNN-Guard is the highest as \(\varepsilon_{e}\) increases from \(0.01\) to \(0.06\) for the LSTM-32 model on the RT dataset. Thus, RNN-Guard provides more robustness for RNN models.

Second, as shown in Tab. III, RNN-Guard attains high empirical robust accuracy across different models and datasets. For example, RNN-Guard achieved \(67.61\%\) empirical robust accuracy at \(\varepsilon_{e}=0.03\) for the LSTM-32 model on the RT dataset, which is the best result in this setting. The outstanding effectiveness of RNN-Guard against adversarial attacks is guaranteed by its certified robustness results. Though adversarial training methods can improve models' robustness to some extent, they are usually challenged by later and stronger attacks [29]. Models trained with existing certified training methods cannot defend against the PGD attack (multi-frame), which is no surprise because defending against multi-frame attacks is more difficult. In addition, though the empirical robust accuracy of AT-PGD is similar or even slightly higher than RNN-Guard, we argue that, due to the limitation of empirical robust accuracy, it doesn't mean that models trained by AT-PGD are more robust than those trained by RNN-Guard. We conducted further experiments where we replace the PGD attack with adaptive attacks to support our argument, which are detailedly presented in Section VI-C. Nevertheless, RNN-Guard is an effective defense against adversarial attacks.

Third, as shown in Tab. IV, RNN-Guard maintains relatively high clean accuracy. For instance, the clean accuracy of the LSTM-32 model trained with RNN-Guard on the RT dataset is \(73.94\%\), which is only about \(2\%\) lower than the model trained with the regular training. The clean accuracy of models trained with RNN-Guard is lower than those trained with the regular training, but the decline is acceptable. First, as many previous works (both empirical and certified defenses) [21, 29, 30, 54] have shown, improving a model's robustness can cause a drop in its clean accuracy due to the trade-off between the robustness and clean accuracy of the model. Second, the gap between RNN-Guard and the regular training in clean accuracy is similar to those in previous works. For example, adversarial training with PGD caused about \(13\%\) decline in clean accuracy on the CIFAR-10 dataset [29], certified training with 1BP caused about \(10\%\) decline in clean accuracy on the SVHN dataset [21], and certified training with DiffAI(hSmooth) caused about \(10\%\) decline in clean accuracy on the F-MNIST dataset [30]. Last but not least, models with high robustness and lower clean accuracy are still useful in the real world. For instance, recent works [31],
[50] combine the advantages of models with high robustness but lower clean accuracy and those with high clean accuracy but lower robustness using model aggregation mechanisms to build a new model that achieves both high clean accuracy and high robustness. Though the training model using RNN-Guard can result in a lower clean accuracy, we argue that RNN-Guard is still an outstanding defense because it achieves a remarkably high robustness against multi-frame attacks.

Finally, as shown in Tab. V, RNN-Guard is more efficient than Cert-RNN. For instance, it only takes about 1 hour for RNN-Guard to train the LSTM-32 model for one epoch on the RT dataset, whereas Cert-RNN takes about 4 hours. Thus, RNN-Guard is more efficient than the current SOTA method Cert-RNN, especially for long input sequences. Moreover, RNN-Guard's training time is acceptable compared to certified training methods for CNNs. For example, existing study [54] shows that CROWN-IBP takes 954 to 4173 seconds to train models with medium size on the MNIST and CIFAR-10 datasets while convex adversarial polytopes (CAP) takes 6961 to 160764 seconds to train same models on same datasets. Note that both adversarial training and certified training consume extra time to compute an additional robustness loss in the training phase, which has _no negative effect_ on the model's efficiency in the _inference phase_.

In conclusion, RNN-Guard achieve the highest certified robustness among the six training methods, the running time of RNN-Guard is significantly shorter than the SOTA certified training method Cert-RNN, and the decrease in accuracy caused by RNN-Guard is similar to those caused by previous certified defenses for CNNs. Thus, we believe RNN-Guard is currently the best choice for enhancing the robustness of RNN models.

### _Adaptive Evaluation of Existing Defenses and RNN-Guard_

In this subsection, we further evaluate the defensive effectiveness of existing defenses and RNN-Guard using adaptive attacks, which are considered to be reliable evaluations of adversarial defenses. We use an automatic adaptive attack tool called _AdaptiveAutoAttack_ (A3) [52], which is experimentally demonstrated to be more effective than traditional manually-designed adaptive attacks.

#### Iv-C1 Experimental Settings

_Automatic Adaptive Attack._ In the above section, we empirically evaluate the defensive effectiveness of different defenses using the PGD attack. However, such a one-sided evaluation cannot reveal the true vulnerability of each defense. To comprehensively evaluate the robustness of models trained by different defenses against adversarial attacks, we replace the PGD attack with the adaptive attack, which can utilize the weakness in the design of the defense to adaptively generate adversarial examples for breaking through the defense. In the normal adaptive attack setting, the adversary has _complete knowledge_ of the defense and manually crafts attacks based on their knowledge. However, most common adaptive attack methods are designed for empirical defenses such as adversarial training, which are ineffective for certified defenses because common adaptive attack methods such as replacing the loss function optimized by the attack are ineffective for certified defenses. Therefore, we follow [52] to design our adaptive attack, which searches for an effective attack over different combinations of common reusable building blocks of existing adaptive attacks (i.e., attack algorithm and parameters, network transformations, and loss functions). In our experiment, we use the AdaptiveAutoAttack (A3) tool with a little customization for the adaptation of the input data.

_Evaluation Metrics._ We use _adaptive robust accuracy_ to quantify the defense effectiveness of a defense against adaptive attackers, which is the fraction of samples that adaptive adversaries fail to find their adversarial examples in the test set.

The rest of the experimental settings are consistent with those in the above section, which are explained in Section V-A and VI-A. Due to timeout, results on the Yelp dataset are not presented.

#### Iv-C2 Results and Analysis

We compare the adaptive robust accuracy of different defenses, which reveals the defensive effectiveness of a defense against the worst-case adversary who has complete knowledge of that defense. The results are shown in Tab. VI, from which we have the following observations.

First, RNN-Guard achieves the highest adaptive robust accuracy across different models and datasets. For example, RNN-Guard achieved \(61.37\%\) empirical robust accuracy at \(\varepsilon_{e}=0.03\) for the RNN-32 model on the RT dataset, while the second-best method only reached \(29.54\%\). The advantages of RNN-Guard in certified robustness provide a solid foundation for its effectiveness against adaptive adversaries. Hence, it is extremely difficult for adaptive adversaries to successfully attack models trained by RNN-Guard.

Second, adversarial training is vulnerable to adaptive attacks because they are empirical defenses and lack theoretical guarantees for security. For instance, comparing the results in Tab. III, the RNN-32 model trained by AT-PGD on the RT dataset achieves \(67.00\%\) empirical robust accuracy against the PGD attack, but it only achieves \(29.54\%\) adaptive robust accuracy
against the adaptive attack. In contrast, the RNN-32 model trained by RNN-Guard on the RT dataset achieves \(65.68\%\) empirical robust accuracy and \(61.37\%\) adaptive robust accuracy, which indicates that RNN-Guard is a more dependable defense against the adaptive attack.

Finally, existing certified training methods cannot defend against the adaptive attack because they focus on one-frame attacks and defending against multi-frame attacks is beyond their capability. For example, POPQORN+ and Cert-RNN achieve \(2.21\%\) and \(0.60\%\) adaptive robust accuracy for the RNN-32 model on the RT dataset, respectively.

In conclusion, the results of adaptive attacks further confirm that RNN-Guard is the best choice for enhancing the robustness of RNN models against multi-frame attacks.

## VII Discussion

_Evaluation on commercial models/platforms._ With the great success of Machine Learning as a Service (MLaaS), many companies have launched their own models/platforms for NLP tasks, such as Google Cloud NLP, IBM Waston Natural Language Understanding, Microsoft Azure Text Analytics, and Amazon AWS Comprehend. For security and copyright considerations, those companies only provide APIs to their customers without any access to their models' structure or parameters. However, certified defenses (e.g., POPQORN, Cert-RNN, and RNN-Guard) are white-box evaluations, i.e., they require full knowledge of the model. Besides, the attack methods we used in the evaluation (i.e., FGSM, PGD, and adaptive attacks) are white-box attacks, which also require full knowledge of the target model. Thus, without full access to the model, it is nearly impossible to conduct any white-box evaluation on those commercial models/platforms. Nevertheless, the large datasets and complex model structures we used in our evaluations are chosen according to those in real-world applications. Thus, we believe our results have certain practical significance.

_Extending to SOTA models._ Recently, SOTA models for NLP tasks have shifted from RNNs to Transformers, especially large-scale pre-trained models such as BERT [11] and GPT-3 [5]. For instance, the base BERT model has 12 layers and 110M parameters. Extending existing certified defense to such models is extremely hard due to their enormous number of parameters. However, we argue that Transformers cannot completely replace RNNs because RNNs are more suitable for simple tasks due to their small size and adequate performance. We will conduct research on extending RNN-Guard to Transformers in the future.

_Extending to other tasks._ In this work, we focus on several common textual classification tasks such as sentiment analysis and toxic content detection. Besides classification tasks, there are many other tasks that RNNs can handle including sequence prediction, machine translation, and question answering. However, the current definition of robustness is proposed for classification tasks, which require a ground-truth label to determine whether a sample is robust or not. Thus, the existing definition of robustness cannot directly apply to other tasks due to the lack of ground-truth labels in them. We will conduct research on proposing a general definition of robustness and extending RNN-Guard to general tasks in future works.

_Extending to other threat models._ In this work, we follow the threat model in the previous works [12] where attackers can directly perturb word embeddings because word embeddings are in a continuous space and it is easy to express all potential adversarial examples with an abstract domain. Besides this threat model, there exist attacks on other attack surfaces such as word substitution attacks [1] and character injection attacks [4]. However, words and characters are in discrete space and how to extend abstract domains to discrete space remains a challenging problem. We are considering extending RNN-Guard to other threat models in our future plan.

## VIII Related Work

Adversarial attacks and defenses have been one of the most popular topics in the machine learning area over the past few years.

_Adversarial Attacks._ The existence of adversarial attacks was first found on feed-forward networks such as convolutional neural networks (CNNs) [43]. Afterward, many studies [15, 33, 39] show that RNNs are also vulnerable to adversarial examples. Some attackers perturb the input text by replacing a few characters or words [15]. Other attackers perturb the word embedding using \(\mathcal{L}_{p}\)-bounded attacks [39], which are considered to be more powerful [12]. Thus, in our threat model, we assume that adversaries can directly perturb the word embedding of textual input sequences.

_Empirical Defenses._ Early defensive works are based on heuristics to defend against adversarial attacks empirically, including _adversarial training_[20, 40], _model distillation_[34], and _feature denoising_[51]. For example, adversarial training forces the target model to memorize adversarial examples by adding them to the training set. However, empirical defenses lack theoretical guarantees and can be defeated by stronger attacks [2, 46]. To end the constant competition between attackers and defenders, recent researches have started to focus on certified defenses.

_Certified Defenses._ Certified defenses, or robustness certification, aim to formally verify whether a given neighbor around the clean input contains any adversarial example, which theoretically guarantees the safety of the target models. The existing certified defenses can fall into one of two categories, complete methods or incomplete methods. Complete methods usually model the robustness certification problem as a _satisfiability modulo theories_ (SMT) [6, 24, 16] or _mixed integer linear programming_ (MILP) [28, 45, 8]. Though complete methods can derive precise results of the model's robustness, they are constrained to small models with piece-wise linear activation functions.

To certify the robustness of large models with general activation functions, incomplete methods employ relaxed approaches including _Linear Programming_ (LP) [38, 44, 47], _linear inequalities propagation_[3, 42, 55], _Zonotopes_[41, 30, 41], _interval bound propagation_ (IBP) [21], _dual optimization_[48, 49, 13], and _semi-definite programming_ (SDP) [37, 14, 36]. Due to the relaxation, the certification
results of incomplete methods could be inaccurate, i.e., they may prove that a model is non-robust around a clean sample even if it is indeed robust. Nevertheless, incomplete methods are better choices considering the expensive computational cost of complete methods on large models.

Furthermore, robustness certification methods usually are extended as certified training methods [21, 30, 54] to directly improve the robustness of the target model. However, due to the trade-off between the robustness of a model and its accuracy [29, 53], certified training methods can cause a decrease in clean accuracy.

_Certified Defenses for RNN models._ Due to their unique structures and operations, most of the existing certified defenses cannot be applied to RNN models. To the best of our knowledge, there are only two certified defenses [25, 12] that focus on RNNs. POPQORN [25] utilizes IBP to certify the RNN model's robustness for the first time. Later, Cert-RNN [12] was proposed, which is based on the Zonotope domain and outperforms the former POPQORN in precision and efficiency. However, we discover a vulnerability in above works, i.e., they are challenged by multi-frame attacks because they focus on the weaker one-frame attacks, which motivates this work.

## IX Conclusion

In this paper, we present RNN-Guard, the first certified defense against multi-frame attacks for RNN models. RNN-Guard adopts the perturb-all-frame strategy for larger perturbation space that captures all potential adversarial examples in multi-frame attacks. We also introduce a new abstract domain called InterZono and design tighter relaxations to address the precision issue caused by the perturb-all-frame strategy. We comprehensively evaluate the performance of RNN-Guard across various models and datasets. The results show that InterZono is more precise than Zonotope while carrying the same time complexity. Moreover, we extend RNN-Guard as the first certified training method against multi-frame attacks. The experimental results show that, compared to existing defenses, RNN-Guard is more effective against multi-frame attacks.
