## CERT-ED: Certifiably Robust Text Classification for Edit Distance

## Zhuoqun Huang, Neil G. Marchant, Olga Ohrimenko, Benjamin I. P. Rubinstein

School of Computing and Information Systems

University of Melbourne

Melbourne, Australia

{zhuoqun, nmarchant, oohrimenko, brubinstein}@unimelb.edu.au

## Abstract

et al., 2018; Wang et al., 2020; Qi et al., 2021; Guo et al., 2021), while preserving consistent semantics.

With the growing integration of AI in daily life, ensuring the robustness of systems to inferencetime attacks is crucial. Among the approaches for certifying robustness to such adversarial examples, randomized smoothing has emerged as highly promising due to its nature as a wrapper around arbitrary black-box models. Previous work on randomized smoothing in natural language processing has primarily focused on specific subsets of edit distance operations, such as synonym substitution or word insertion, without exploring the certification of all edit operations. In this paper, we adapt Randomized Deletion (Huang et al., 2023) and propose, CERTified Edit Distance defense (CERT-ED) for natural language classification. Through comprehensive experiments, we demonstrate that CERTEDoutperforms the existing Hamming distance method RanMASK (Zeng et al., 2023) in 4 out of 5 datasets in terms of both accuracy and the cardinality of the certificate. By covering various threat models, including 5 direct and 5 transfer attacks, our method improves empirical robustness in 38 out of 50 settings.

## 1 Introduction

Deep nets, transformers, and other modern machine learning approaches have recently achieved significant performance on many natural language processing (NLP) tasks thanks to their ability to generalize to complex and unseen data. However, the well-documented vulnerability of these models to evasion attacks (a.k.a. adversarial examples) raises concerns about their use in practice. For example, numerous previous works have developed attacks that can misguide models by perturbing text at the word-level (Alzantot et al., 2018; Li et al., 2020; Ren et al., 2019; Zang et al., 2020; Jin et al., 2020; Li et al., 2021; Garg and Ramakrishnan, 2020), character-level (Karpukhin et al., 2019; Gao et al., 2018; Ebrahimi et al., 2018) or sentence-level (Iyyer

Although a wide range of defenses have been proposed against adversarial examples, they are routinely broken by subsequent attacks: Eger and Benz (2020) and Morris et al. (2020) showed that while adversarial training typically yields good robustness against a target attack, it is less robust against unseen attacks. Consequently, certified robustness has gained considerable interest as a result of competition between attackers and defenders, where a classifier's prediction can be guaranteed to be invariant to a specified set of adversarial perturbations (Cohen et al., 2019; Wang et al., 2021a).

Certified robustness methods have been well studied for continuous data that is fixed-dimensional like images (Wong and Kolter, 2018; Dvĳotham et al., 2018; Mirman et al., 2018; Weng et al., 2018; Lecuyer et al., 2019; Cohen et al., 2019). Among certification approaches, randomized smoothing (Lecuyer et al., 2019; Cohen et al., 2019; Levine and Feizi, 2020) has attained state-of-the-art performance in many tasks. Due to the discrete nature of text inputs, however, developing randomized smoothing mechanism for NLP tasks is more challenging. Ye et al. (2020) and Wang et al. (2021a) were the first to investigate randomized smoothing under a synonym substitution threat model. Similarly, Zeng et al. (2023) proposed RanMASK that adapts Randomized Ablation (Levine and Feizi, 2020) to NLP and is provably verifiable for Hamming distance under a fixed number of word substitutions. However, such robustness certificates fall short in defending against general perturbations as inserting a single word (Garg and Ramakrishnan, 2020) would void any of these substitution-based certificates. To remedy this, Huang et al. (2023) proposed a method for producing certifiable predictions under edit distance perturbations, called Randomized Deletion. However, their method is limited to binary classification tasks, and has only

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00728v1-figure-acb0f093-2e6e-420f-a4d5-a2f6d8792572.jpg)

X="click around here to see the bang busit is pretty wild!

Certified correct prediction distot

Figure 1: Top: Clean sample from Spam-assassin dataset. Middle: CERT-ED applied to the perturbed input to produce edit distance certified prediction of 'Spam' and certified radius of 3. Bottom: Real adversarial sample generated by, Clare (Li et al., 2021), against a model without CERT-ED. The green words are adversarially inserted words. CERT-ED is certifiably robust to this adversarial example as the edit distance between the clean and adversarial inputs is 2, less than the certified radius.

been applied to the malware detection domain. In this paper we address this limitation.

for direct attacks and 18 out of 25 settings for transfer attacks.

Our contributions are summarized as follows:

- · We propose and implement CERTified Edit Distance defense (CERT-ED), a multi-class extension of Randomized Deletion (Huang et al., 2023), that can provably certify multi-class predictions for NLP classification tasks . It smooths input text 1 by adding deletion noise to produce predictions that are certifiably robust under arbitrary attacks within a computed edit distance radius 𝑟 (Figure 1).
- · To compare our edit distance certificates with Hamming distance certificates used in previous work, we define certified cardinality, a discrete analogue of certified volume that has been used to compare certificates with different geometries in the vision domain. We evaluate CERT-ED using 5 datasets and find significant improvement of over the RanMASK baseline, both in certified accuracy and certified cardinality.
- · Weconductacomprehensiveempiricalevaluation of robustness against five state-of-the-art direct attacks and transfer attacks. Our results show improved robust accuracy in 20 out of 25 settings

1 Our implementation is available at https://github. com/Dovermore/nlp-smoothing-software .

## 2 Edit distance robustness

We consider text sequence classification tasks, where a model 𝑓 predicts the class 𝑦 ∈ Y of input text 𝒙 ∈ X . For example, in fake news detection the input text is a news article and the possible classes are 'fake' and 'real' (Rashkin et al., 2017). We are interested in studying robustness under an adversary that can make a bounded number of edits to the text.

We define an edit to be an operation that deletes ( del ), inserts ( ins ) or substitutes ( sub ) a single token in the text. A token is a contiguous chunk of characters-e.g., a word or sub-word. The mapping from text to tokens is determined by the adversary's tokenizer t . While our method is compatible with any choice of t , we set t to be a whitespace tokenizer in our experiments for comparison with prior work on attacks (Garg and Ramakrishnan, 2020; Jin et al., 2020; Li et al., 2020, 2021) and robustness (Zeng et al., 2023; Zhang et al., 2024b) at the word-level. Wenotethat t is solely used to model the adversary's edits, and is distinct from any tokenizer that may appear in model 𝑓 itself.

For generality, we consider adversaries whose edit operations are constrained to the set o ⊆ { del , ins , sub } . For instance, o = { ins , sub } for

an adversary that cannot perform deletions. Given the adversary's tokenizer t and allowed edit operations o , we measure the extent of the adversary's perturbation using edit distance dist o t , ( ¯ 𝒙 𝒙 , ) , which counts the minimum number of edits required to transform original text ¯ into perturbed text 𝒙 𝒙 .

Our objective is to design text sequence classification models that are certifiably robust under this threat model. Formally, given input text 𝒙 ∈ X to model 𝑓 , we would like to guarantee that 𝑓 's prediction is unchanged even if 𝒙 was modified by an adversary that made up to 𝑟 edits:

$$\forall \bar { x } \in B _ { r } ( x ; \circ, t ) \, \colon f ( x ) = f ( \bar { x } ). \quad ( 1 ) \quad _ { - }$$

Here

$$B _ { r } ( \boldsymbol x ; \circ, t ) \coloneqq \{ \boldsymbol \bar { x } \in \mathcal { X } \, \colon \text{dist} _ { \circ, t } ( \boldsymbol \bar { x }, \boldsymbol x ) \leq r \} \quad ( 2 ) \quad \text{ized}$$

is the set of text inputs that can be transformed into 𝒙 via at most 𝑟 edits. As is typical for randomized smoothing, we will develop mechanisms that produce a randomized radius 𝑟 given input sequence 𝒙 , such that with some chosen high probability at least 1 -𝛼 , this radius is a valid certificate at 𝒙 .

## 3 Certified robustness via randomized smoothing

Our approach for achieving certified robustness under bounded edit distance perturbations is based on randomized smoothing. Specifically, we apply the randomized smoothing mechanism of Huang et al. (2023), which was originally formulated for binary classification of generic sequences. We review the mechanism in a text classification context in Section 3.1 and propose, CERT-ED, a certifiably robust extension to the multi-class setting in Section 3.2. Our derived certificates cover attacks BAE-I (Garg and Ramakrishnan, 2020) and Clare (Li et al., 2021) not covered by prior work.

## 3.1 Randomized deletion smoothing

Randomized smoothing has emerged as a general purpose method for constructing certifiably robust classifiers (Kumari et al., 2023). Consider a base classifier 𝑓 b : X → Y and a randomized mechanism 𝜙 : X → 𝑃 (X) that generates perturbed inputs. In the following we construct a smoothed classifier 𝑓 that assigns a probabilistic score to class 𝑦 given input 𝒙 :

$$p _ { y } ( { \boldsymbol x } ) = \mathbb { E } _ { z \sim \phi ( x ) } [ { \boldsymbol 1 } _ { f _ { b } ( z ) = y } ]. \quad \ \ ( 3 ) \quad \text{dist}$$

Thesmoothed classifier's prediction is then the class with the highest score: 𝑓 ( 𝒙 ) = arg max 𝑦 ∈Y 𝑝 𝑦 ( 𝒙 ) .

Huang et al. (2023) instantiate randomized smoothing with a deletion mechanism for sequences that achieves certified edit distance robustness. In the text domain, we apply their deletion mechanism at the level of tokens determined by tokenizer t . Specifically, given input text 𝒙 ∈ X containing 𝑛 tokens, the deletion mechanism generates 𝑛 indicator variables 𝝐 = ( 𝜖 1 , . . . , 𝜖 𝑛 ) where 𝜖 𝑖 iid ∼ Bernoulli ( 𝑝 del ) . The perturbed text is then obtained by deleting any token 𝑖 for which 𝜖 𝑖 = 1 and keeping the remaining tokens (in order).

Practicalities Exact computation of the scores in (3) scales exponentially in the number of tokens 𝑛 . We therefore follow standard practice in randomized smoothing and obtain upper/lower confidence bounds on the scores using Monte Carlo sampling. When constructing a smoothed classifier 𝑓 , we finetune the base classifier 𝑓 b on inputs perturbed by the mechanism 𝜙 , as this results in better performance.

## 3.2 CERT-ED: Multi-class edit distance certification

We extend the edit distance certificate of Huang et al. (2023) to the multi-class setting. We refer to randomized deletion smoothing with this new certificate as CERT-ED. We discuss the setup and assumptions here and present two key results, which demonstrate how a certificate can be obtained for a bounded Levenshtein (edit) distance adversary whose edit operations o are unconstrained. All proofs are provided in Appendix A.

We adopt a standard setup for certification of smoothed classifiers. Given input text 𝒙 , we let 𝑦 = arg max 𝑐 𝑝 𝑐 ( 𝒙 ) be the class that achieves the highest score and 𝑦 ′ = arg max 𝑐 ≠ 𝑦 𝑝 𝑐 ( 𝒙 ) be the class that achieves the second-highest score. We assume that 𝜇 𝑦 ≤ 𝑝 𝑦 ( 𝒙 ) is a lower bound on the highest score and 𝜇 𝑦 ′ ≥ 𝑝 𝑦 ′ ( 𝒙 ) is an upper bound on the second highest score. Apart from this minimal information, we do not assume any knowledge of the base classifier 𝑓 b. We begin by obtaining upper and lower bounds on the smoothed classifier's score at a neighboring input ¯. 𝒙

Theorem 1 (General pairwise certificate) . Consider a pair of text inputs 𝒙 𝒙 , ¯ ∈ X . Suppose ¯ 𝒙 can be transformed into 𝒙 using a minimal number of edit operations by deleting 𝑛 del tokens, inserting 𝑛 ins tokens and substituting 𝑛 sub tokens-i.e., dist o t , ( ¯ 𝒙 𝒙 , ) = 𝑛 sub + 𝑛 ins + 𝑛 del . Then the smoothed

Table 1: Certified radii as a function of the types of edit operations the adversary can perform.

| Adversary's ops   | Adversary's ops   | Adversary's ops   |                                                                                                                 |
|-------------------|-------------------|-------------------|-----------------------------------------------------------------------------------------------------------------|
| del               | ins               | sub               | Certified radius ( ↓ )                                                                                          |
| ✓                 | ✓                 | ✓                 | j log 𝑝 del 2 + 𝜇 𝑦 ′ - 𝜇 𝑦 2 k j log 𝑝 del 2 + 𝜇 𝑦 ′ - 𝜇 𝑦 2 k                                                 |
| ✓                 | ✓                 | ✓ ✓               | j log 𝑝 del 2 + 𝜇 𝑦 ′ - 𝜇 𝑦 2 k                                                                                 |
| ✓                 | ✓                 |                   | j log 𝑝 del 1 1 - 𝜇 𝑦 ′ + 𝜇 𝑦 k j log 𝑝 del 1 1 - 𝜇 𝑦 ′ + 𝜇 𝑦 k GLYPH<4> log 𝑝 del ( 1 + 𝜇 𝑦 ′ - 𝜇 𝑦 ) GLYPH<5> |
| ✓                 |                   |                   |                                                                                                                 |
|                   | ✓                 |                   |                                                                                                                 |

classifier's scores for any class 𝑦 ∈ Y satisfy

$$p _ { \text{del} } ^ { n _ { \text{del} } - n _ { \text{ins} } } & \left ( p _ { y } ( \boldsymbol x ) - 1 + p _ { \text{del} } ^ { n _ { \text{sub} } + n _ { \text{ins} } } \right ) \leq p _ { y } ( \bar { \boldsymbol x } ) \\ & \leq p _ { \text{del} } ^ { n _ { \text{del} } - n _ { \text{ins} } } p _ { y } ( \boldsymbol x ) + 1 - p _ { \text{del} } ^ { n _ { \text{sub} } + n _ { \text{del} } }.$$

The above result is not immediately useful on its own. However, it can be used to derive edit distance certificates under various constraints on the number of edit operations of each type ( 𝑛 del , 𝑛 ins , 𝑛 sub ) the adversary can perform. Below we present a Levenshtein distance certificate, which covers an adversary that can perform up to 𝑟 edits of any type (insertions, deletions or substitutions).

Theorem 2 (Levenshtein distance certificate) . Consider a text input 𝒙 ∈ X for which a lower bound on the smoothed classifier's highest score 𝜇 𝑦 and an upper bound on the smoothed classifier's runner-up score 𝜇 𝑦 ′ satisfy 𝜇 𝑦 ≥ 𝜇 𝑦 ′ . Then the smoothed classifier predicts 𝑦 for any neighboring text input ¯ 𝒙 ∈ X such that dist o t , ( ¯ 𝒙 𝒙 , ) ≤ 𝑟 with o = { del , ins , sub } and 𝑟 = ⌊ log 𝑝 del 1 2 ( 2 + 𝜇 𝑦 ′ -𝜇 𝑦 )⌋ . If the upper and lower bounds hold jointly with confidence 1 -𝛼 , then the certificate holds with probability 1 -𝛼 .

This result is readily adapted for adversaries that are constrained in the kinds of edit operations they can perform. We provide certificates for seven constrained settings in Table 1.

## 4 Experiments

To evaluate the effectiveness of our methods, we train and evaluate models with CERT-ED certification across a variety of English datasets and compare observed performance against RanMASK (Zeng et al., 2023). We show that our method uniformly dominates RanMASK in certified radius and accuracy for 4 out of 5 datasets in Section 4.1. We then conduct 5 direct and 5 transfer attacks on the certified models and show that CERT-ED is also empirically more robust than RanMASK in 38 out of 50 settings in Section 4.2. Though CERT-ED is empirically more robust than RanMASK against word substitution and characterlevel attacks, the performance is more mixed for attacks that induce edit distance perturbations. Finally, we also report a 3 times speedup of our method compared to RanMASK in Appendix E.

Datasets We present results on five diverse datasets listed in Table 2. All datasets are partitioned into training, validation and test sets. AGNews (Zhang et al., 2015) and IMDB (Maas et al., 2011) are standard datasets for topic classification and sentiment analysis respectively, that have been used for evaluation in prior work (Zeng et al., 2023). However, since adversaries may lack incentive to target these models, we follow recommendations of Chen et al. (2022), and consider Spamassassin (Chen et al., 2022) for spam detection, and SatNews (Yang et al., 2017) and LUN (Rashkin et al., 2017; Chen et al., 2022) for unreliable news detection, which are arguably more attractive targets for attackers 2 . We collect all data from HuggingFace Datasets 3 and the AdvBench repository 4 (Chen et al., 2022).

Table 2: Summary of datasets.

|               |           | Number of samples   | Number of samples   | Number of samples   |
|---------------|-----------|---------------------|---------------------|---------------------|
| Dataset       | Avg words | Train               | Valid               | Test                |
| AG-News       | 37.8      | 108 000             | 12 000              | 7 600               |
| IMDB          | 231.2     | 22 500              | 2 500               | 25 000              |
| Spam-assassin | 228.2     | 2 152               | 239                 | 2 378               |
| LUN           | 269.9     | 13 416              | 1 490               | 6 454               |
| SatNews       | 384.8     | 22 738              | 2 526               | 7 202               |

Models We use the Hugging Face Transformers library (Wolf et al., 2020) to load a pre-trained RoBERTa model (Zhuang et al., 2021) as a base classifier for CERT-ED and as a non-certified baseline. We include RanMASK (Zeng et al., 2023) as

2 These datasets might contain offensive or inappropriate languages due to their adversarial nature

3 https://github.com/huggingface/datasets

4 https://github.com/thunlp/Advbench

a certified baseline for Hamming distance. This baseline covers a bounded number of word substitutions only. Since RanMASK is also based on randomized smoothing, albeit with a different masking mechanism, we use the same base classifier, training procedure and parameter settings as CERT-ED where possible. We use perturbation strength to refer to the deletion rate parameter 𝑝 del of CERT-ED and the masking rate parameter 𝑝 mask of RanMASK. We note that TextCRS (Zhang et al., 2024a) claims to certify against limited word substitution, insertion, and deletion operations of a single type, however we do not include it as a baseline since the resulting edit distance certificates are vacuous ( 𝑟 = 0) for text greater than 2 words in length (see Appendix F).

For both CERT-ED and RanMASK, we use a white-space tokenizer for smoothing and fine-tune the base RoBERTa model on the training set where inputs are perturbed by the corresponding smoothing mechanism. We report our training parameter settings in Table 5 of Appendix B.

## 4.1 Certified accuracy and robustness

Setup Our first set of experiments compares the accuracy and certificates generated by CERT-ED and RanMASK. Following prior work (Huang et al., 2023; Zeng et al., 2023), we use 1000 Monte Carlo samples for prediction, 4000 samples for estimating the certified radius and a confidence level of 95%. In the unlikely case where the prediction and certificate disagree, we report the prediction, and report a certified radius of zero. Table 3 presents a summary of the results, where we highlight the best of three perturbation strengths (80%, 90% and 95%) for each dataset. Results for all three perturbation strengths (80%, 90% and 95%) are provided in Table 6 of Appendix C.1.

Clean accuracy To assess performance in a nonadversarial setting, we report accuracy on the clean (unperturbed) test set. For both CERT-ED and RanMASK, we observe a slight degradation in clean accuracy of 0.2-5.2% across all datasets compared to the non-smoothed baseline, where the highest degradation is seen on the IMDB dataset. This may be due to the fact that IMDB is a sentiment classification task, where sensitivity to small perturbations such as names (Prabhakaran et al., 2019) and the presence or absence of single words (e.g., 'not') is more likely. CERT-ED outperforms RanMASK in both clean accuracy and the size of the certifi-

| Model                                     | 𝑝 del / 𝑝 mask                            | Clean Accuracy                            | Median CR                                 | Median log CC                             |
|-------------------------------------------|-------------------------------------------|-------------------------------------------|-------------------------------------------|-------------------------------------------|
| AG-News dataset (avg length 37.84)        | AG-News dataset (avg length 37.84)        | AG-News dataset (avg length 37.84)        | AG-News dataset (avg length 37.84)        | AG-News dataset (avg length 37.84)        |
| Baseline                                  | -                                         | 94.84%                                    | -                                         | -                                         |
| RanMASK                                   | 80%                                       | 93.91%                                    | 2                                         | 12.25                                     |
| CERT-ED                                   | 80%                                       | 93.33%                                    | 2                                         | 12.65                                     |
| IMDB dataset (avg length 231.16)          | IMDB dataset (avg length 231.16)          | IMDB dataset (avg length 231.16)          | IMDB dataset (avg length 231.16)          | IMDB dataset (avg length 231.16)          |
| Baseline                                  | -                                         | 93.47%                                    | -                                         | -                                         |
| RanMASK                                   | 90%                                       | 86.87%                                    | 2                                         | 14.02                                     |
| CERT-ED                                   | 90%                                       | 88.26%                                    | 2                                         | 14.49                                     |
| Spam-assassin dataset (avg length 228.16) | Spam-assassin dataset (avg length 228.16) | Spam-assassin dataset (avg length 228.16) | Spam-assassin dataset (avg length 228.16) | Spam-assassin dataset (avg length 228.16) |
| Baseline                                  | -                                         | 98.02%                                    | -                                         | -                                         |
| RanMASK                                   | 90%                                       | 97.65%                                    | 6                                         | 37.49                                     |
| CERT-ED                                   | 90%                                       | 97.81%                                    | 6                                         | 38.66                                     |
| LUN dataset (avg length 269.93)           | LUN dataset (avg length 269.93)           | LUN dataset (avg length 269.93)           | LUN dataset (avg length 269.93)           | LUN dataset (avg length 269.93)           |
| Baseline                                  | -                                         | 99.16%                                    | -                                         | -                                         |
| RanMASK                                   | 90%                                       | 97.91%                                    | 6                                         | 34.51                                     |
| CERT-ED                                   | 90%                                       | 98.28%                                    | 6                                         | 37.94                                     |
| SatNews dataset (avg length 384.84)       | SatNews dataset (avg length 384.84)       | SatNews dataset (avg length 384.84)       | SatNews dataset (avg length 384.84)       | SatNews dataset (avg length 384.84)       |
| Baseline                                  | -                                         | 94.22%                                    | -                                         | -                                         |
| RanMASK                                   | 95%                                       | 90.10%                                    | 7                                         | 47.09                                     |
| CERT-ED                                   | 95%                                       | 92.07%                                    | 8                                         | 54.76                                     |

Table 3: Key certification results drawn from Table 6. All metrics are computed on the entire test set. 'Median CR' is the median certified radius and 'median log CC' is the base-10 logarithm of the median certified cardinality. The certified cardinality is exact for RanMASK, however a lower bound is used for CERT-ED. CERT-ED outperforms RanMASK in terms of certified accuracy for 4 out of 5 datasets and specifically excels on datasets with longer average length. Highlighted values are the better of the two smoothed mechanisms.

cate for the four datasets with longer text. While CERT-ED fuzzes the input length, RanMASK preserves it, and may therefore have an advantage for short text where the length conveys information. However, for datasets with longer text like LUN and SatNews, RanMASK may introduce too many masking tokens and confuse the base model.

## Certified accuracy and certified cardinality We

report certified radius (CR) as a measure of robustness, where a larger radius indicates robustness to larger perturbations. However, the certified radius is not comparable between CERT-ED and RanMASK, as the metric used to define the certificate for CERT-ED is Levenshtein (edit) distance whereas the metric for RanMASK is Hamming distance. As an alternative, we therefore also measure the cardinality of the certificate, that is the number

Figure 2: Certified accuracy for CERT-ED and RanMASK as a function of the log-cardinality of the certificate for the SatNews dataset. We see that CERT-ED certifies a set up to 10 10 times larger than RanMASK for the same accuracy.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00728v1-figure-26b3fe3a-8bfd-465f-8e1c-df28bebc84df.jpg)

of perturbed textual inputs it contains, which we refer to as the certified cardinality (CC). This is analogous to certified volume, used in prior work in the vision domain (Pfrommer et al., 2023). For a given radius and vocabulary size 5 , we compute the cardinality exactly for RanMASK and use a lower bound for CERT-ED based on a result of Charalampopoulos et al. (2020, Fact 17). We note that it is possible to compute the exact cardinality for a Levenshtein distance certificate using a Levenshtein automaton (Touzet, 2016), however the computation is expensive and only improves on the lower bound by approximately one order of magnitude. Despite the under-estimated certified cardinality of CERT-ED, we find it dominates RanMASK across all datasets, with a widening gap for datasets with longer text. To assess trade-offs between robustness and accuracy, we plot the certified accuracy as a function of the log-cardinality. The certified accuracy at a given log-cardinality 𝑐 is the fraction of instances in the test set for which the model's prediction is correct and the cardinality of the certificate is at least 𝑐 . Figure 2 plots the certified accuracy for the SatNews dataset, demonstrating an improvement up to 10 10 times in the certified cardinality for CERT-ED compared to RanMASK. Due to space constraints, we present certified accuracy plots for the remaining datasets in Appendix C.2, where a

5 We assume a vocabulary size of 50 265 (matching RoBERTa), although this is a property of the threat model.

strict domination of CERT-ED over RanMASK can be observed for 4 out of 5 datasets.

## 4.2 Empirical robustness

Attack setup We evaluate the empirical robustness of CERT-ED and baselines using a modified version of TextAttack 6 (Morris et al., 2020) and attack recipes implemented by Zhang et al. (2024a). We select five representative attacks that cover a variety of perturbations: Clare (Li et al., 2021), BAE-I (Garg and Ramakrishnan, 2020), BERTAttack (Li et al., 2020), TextFooler (Jin et al., 2020) and DeepWordBug (Gao et al., 2018). We describe these attacks further in Section 5.1. We randomly select 1000 samples from the test set to evaluate the robustness of the models. For CERT-ED and RanMASK, we estimate the prediction using a Monte Carlo sample size of 100 to speed up the attack process. We impose a 10 minute timeout for each attack and treat timeout as a failed attack. As CERT-ED is about 3 times faster than RanMASK (Appendix E) for prediction and certification, this puts CERT-ED at a disadvantage as attacks against it may use up to a 3 times as many queries. For Clare, due to the excessive amount of querying, we also limit the maximum number of queries to 10 000. Further details on our categorization of attack outcomes are provided in Appendix D.

Threat models We consider two distinct threat models: direct attacks which have access to the model's confidence; and transfer attacks for which attacks are generated against the non-certified baseline and if successful, transferred to the target model (Appendix D). This means the robust accuracy for the non-certified baseline will always be 0%. We report both the clean accuracy (ClA) on original instances, and robust accuracy (RoA) on attacked instances.

Results Wepresent direct attack results in Table 4. Compared to the non-certified baseline, CERT-ED sacrifices a small amount of clean accuracy to achieve a significant improvement in robust accuracy across all settings. For word substitution and character-level attacks (BERT-Attack, TextFooler, DeepWordBug), CERT-ED uniformly outperforms RanMASK in all datasets by up to 8 8% robust ac-. curacy. Surprisingly, we find that CERT-ED is less effective against edit distance attacks (Clare and BAE-I), performing well on datasets with longer

6 https://github.com/QData/TextAttack

Table 4: Empirical attack results against Baseline, RanMASK and CERT-ED under direct attacks. Both RanMASK and CERT-ED use a 90% perturbation strength. Highlighted values are the best in each column for that dataset. CERT-ED outperforms RanMASK in all substitution and character-level attacks. For edit distance attacks, the performance is mixed, with CERT-ED performing better for datasets with longer text.

| Method                | Clean Accuracy %      | Clare RoA%            | BAE-I RoA%            | BERT-Attack RoA%      | TextFooler RoA%       | DeepWordBug RoA%      |
|-----------------------|-----------------------|-----------------------|-----------------------|-----------------------|-----------------------|-----------------------|
| AG-News dataset       | AG-News dataset       | AG-News dataset       | AG-News dataset       | AG-News dataset       | AG-News dataset       | AG-News dataset       |
| Baseline              | 94.50                 | 29.50                 | 58.50                 | 29.00                 | 22.10                 | 43.50                 |
| RanMASK               | 91.70                 | 77.30                 | 79.60                 | 45.10                 | 48.50                 | 47.70                 |
| CERT-ED               | 92.00                 | 67.90                 | 78.10                 | 54.40                 | 56.10                 | 56.90                 |
| IMDB dataset          | IMDB dataset          | IMDB dataset          | IMDB dataset          | IMDB dataset          | IMDB dataset          | IMDB dataset          |
| Baseline              | 94.80                 | 50.30                 | 28.10                 | 9.20                  | 8.00                  | 30.00                 |
| RanMASK               | 86.90                 | 85.50                 | 81.90                 | 52.40                 | 53.00                 | 45.90                 |
| CERT-ED               | 87.90                 | 82.30                 | 71.10                 | 55.30                 | 54.00                 | 49.90                 |
| Spam-assassin dataset | Spam-assassin dataset | Spam-assassin dataset | Spam-assassin dataset | Spam-assassin dataset | Spam-assassin dataset | Spam-assassin dataset |
| Baseline              | 97.59                 | 92.05                 | 94.80                 | 54.55                 | 36.20                 | 80.20                 |
| RanMASK               | 97.00                 | 95.40                 | 96.00                 | 93.50                 | 93.94                 | 92.10                 |
| CERT-ED               | 97.20                 | 95.20                 | 94.90                 | 94.70                 | 95.45                 | 94.30                 |
| LUN dataset           | LUN dataset           | LUN dataset           | LUN dataset           | LUN dataset           | LUN dataset           | LUN dataset           |
| Baseline              | 99.50                 | 91.50                 | 80.10                 | 57.20                 | 64.60                 | 78.50                 |
| RanMASK               | 98.70                 | 93.80                 | 96.40                 | 88.80                 | 90.50                 | 90.50                 |
| CERT-ED               | 99.30                 | 95.30                 | 96.60                 | 92.40                 | 93.90                 | 93.30                 |
| SatNews dataset       | SatNews dataset       | SatNews dataset       | SatNews dataset       | SatNews dataset       | SatNews dataset       | SatNews dataset       |
| Baseline              | 95.50                 | 84.50                 | 58.60                 | 51.30                 | 50.70                 | 61.40                 |
| RanMASK               | 91.20                 | 91.20                 | 91.20                 | 74.50                 | 80.70                 | 80.80                 |
| CERT-ED               | 93.20                 | 93.20                 | 91.70                 | 83.30                 | 83.50                 | 81.80                 |

input sizes, but worse on AG-News and IMDB. We attribute this to the difference in query efficiency between RanMASK and CERT-ED. For Clare on the AG-News dataset, the mean number of queries to RanMASK and CERT-ED are 4 253 and 8 891, respectively, meaning CERT-ED is subject to a stronger attack than RanMASK. Due to the longer text size, all Clare attacks timed out on the SatNews dataset for CERT-ED and RanMASK.

## 5 Related work

2018). These adversarial examples are especially concerning when applied to high stakes tasks such as content moderation and fake news detection (Chen et al., 2022). Alongside research on attacks, certified defenses have been proposed as a strong counter-measure that can guarantee that the most pernicious adversarial examples do not exist within a specified threat model (Lecuyer et al., 2019; Cohen et al., 2019). However, their application in NLP has been limited, in part due to the discrete nature of text (Ye et al., 2020; Wang et al., 2021a; Zeng et al., 2023; Wang et al., 2023; Zhang et al., 2024b).

Despite the rapid advancement of neural networks for many important tasks, their vulnerability to adversarial examples has long been known (Szegedy et al., 2014; Goodfellow et al., 2015) and continues to be a liability for current large-scale models (Qi et al., 2024; Raina et al., 2024). While early work focused on the vision domain, where attacks can leverage continuous optimizers, methods have been proposed to generate adversarial examples in the language domain across a variety of tasks including text classification (Alzantot et al., 2018; Garg and Ramakrishnan, 2020; Li et al., 2020) and machine translation (Zhang et al., 2021; Belinkov and Bisk,

## 5.1 Attacks

Character-level attacks focus on perturbing characters within words to maintain the imperceptibility of attacks to human inspection. Karpukhin et al. (2019) augmented training data with orthographic noise (character-level insertions, substitutions, deletions, and swaps) to improve the robustness of machine translation models. The DeepWordBug (Gao et al., 2018) and HotFlip (Ebrahimi et al., 2018) attacks rank character and token importance in the input text, then greedily search for perturbations using the importance ranking to achieve misclassi-

fication.

Word-level attacks generate adversarial examples by perturbing individual words in text to maximize the model loss while preserving the semantics and syntax of the original sentence. Synonym substitution is one of the most common approaches for maintaining semantic consistency. These attacks typically start by ranking the words by their importance and then sequentially substituting words with synonyms generated using a similarity metric (Alzantot et al., 2018; Li et al., 2020; Ren et al., 2019; Zang et al., 2020; Jin et al., 2020). While powerful, these attacks do not fully represent the capabilities of an adversary, as they do not consider insertion or deletion of words. Subsequent work has investigated edit distance-constrained adversarial attacks. Both Clare (Li et al., 2021) and BAE-I (Garg and Ramakrishnan, 2020) explored the use of edit perturbations beyond substitution and found them successful against NLP models.

Our method CERT-ED can certify robustness against word- and character-level attacks by setting t to be a white-space or character-level tokenizer, accordingly.

Unlike word- or character-level attacks, that perform a limited number of localized perturbations to preserve semantics, sentence-level attacks adversarially paraphrase entire sentences, typically using LLMs (Iyyer et al., 2018; Wang et al., 2020; Qi et al., 2021), or using a parametrized adversarial distribution that enables gradient-based search (Guo et al., 2021).

## 5.2 Defenses

Starting with adversarial training (Goodfellow et al., 2015), numerous empirical defense methods have been proposed to improve robustness of NLP models (Ren et al., 2019; Zang et al., 2020; Wang et al., 2021b; Zhu et al., 2020; Ivgi and Berant, 2021; Li et al., 2020). In the language domain, adversarial training perturbs inputs either in the text space (Ren et al., 2019; Jin et al., 2020; Zang et al., 2020; Li et al., 2020; Ivgi and Berant, 2021; Wang et al., 2021b) or in the embedding space using bounded adversarial noise (Miyato et al., 2017; Zhu et al., 2020). Although empirical defenses may provide excellent robustness against attacks they are tailored for, they cannot guarantee effectiveness against an adaptive attacker.

To mitigate issues with empirical defenses, certified defenses aim to provide a robustness guarantee against arbitrary attacks within a specified threat model. Huang et al. (2019) and Jia et al. (2019) first used interval bound propagation to certify robustness under synonym substitutions. More recently, works have applied randomized smoothing to achieve certified robustness under synonym or word substitution threat models (Ye et al., 2020; Wanget al., 2021a). Despite the use of insertion and deletion operations in published attacks, achieving certified robustness against these operations has not been well-studied. To date, only TextCRS (Zhang et al., 2024a) has made progress on this front. TextCRS certifies against word-level permutations and perturbations in the embedding space, which can provide robustness guarantees against limited word-level substitutions, deletions or insertions. However, TextCRS only partially covers the edit distance ball at a given radius, meaning its certificates are vacuous for our threat model (see Appendix F). In the malware detection domain, Huangetal. (2023) proposed a deletion-based mechanism to achieve certified edit distance robustness for malware binary classification models. Our proposed method CERT-ED adapts their mechanism for the language domain and extends the certificate to support multi-class classification.

## 6 Conclusion

In this work, we investigated certified robustness for natural language classification tasks, where adversaries can perturb input text by adding, deleting, or substituting words. We adapted randomized deletion smoothing (Huang et al., 2023) to the language domain, and derived an edit distance robustness certificate for the multi-class setting. We refer to our certified method as CERT-ED and conducted comprehensive experiments on five datasets. Our results show that CERT-ED outperforms the existing randomized smoothing method (RanMASK) for word substitution robustness in terms of both accuracy and certified cardinality on 4 out of 5 datasets. Our method also excels in robustness against direct and transfer attacks, demonstrating significant improvements over existing methods.

## 7 Ethical considerations

This study focuses on enhancing the robustness of NLP models. Although adversarial examples are generated during the research, their use is strictly for evaluation purposes. We also acknowledge the assistance of ChatGPT and GitHub Copilot for scaffolding code in released artifacts.

## 8 Limitations

Robustness certification aims to measure the risk of adversarial examples, while randomized smoothing provides both certification and mitigation against such attacks. However, our results show that at higher smoothing levels, randomized smoothing can reduce the benign accuracy compared to undefended models. While our experiments are comprehensive and cover a wide range of datasets, attacks and threat models, results might differ on other base model architectures and natural language tasks. Although our edit distance threat model covers a boarder range of attacks than prior work on certifications for NLP, and threat models better aligned for sequence data than the bounded ℓ 𝑝 -norm threat models popular for image research, attackers may opt to make many edits to input data, and in some NLP tasks input semantics could be changed with few edits. For example, sentiment analysis can be local in nature, relying on the sentiment of a single adjective. By contrast, tasks like fake news detection typically rely on more global features to distinguish task classes. Lastly, while our approach is more scalable than alternative certification strategies, it does introduce computational overheads.

## References

Moustafa Alzantot, Yash Sharma, Ahmed Elgohary, Bo-Jhang Ho, Mani Srivastava, and Kai-Wei Chang. 2018. Generating natural language adversarial examples. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing , pages 2890-2896, Brussels, Belgium. Association for Computational Linguistics.

Yonatan Belinkov and Yonatan Bisk. 2018. Synthetic and natural noise both break neural machine translation. In International Conference on Learning Representations .

Panagiotis Charalampopoulos, Solon P. Pissis, Jakub Radoszewski, Tomasz Waleń, and Wiktor Zuba. 2020. Unary Words Have the Smallest Levenshtein k-Neighbourhoods. In 31st Annual Symposium on Combinatorial Pattern Matching , CPM, pages 10:110:12.

Yangyi Chen, Hongcheng Gao, Ganqu Cui, Fanchao Qi, Longtao Huang, Zhiyuan Liu, and Maosong Sun. 2022. Why should adversarial perturbations be imperceptible? Rethink the research paradigm in adversarial NLP. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing , pages 11222-11237, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.

Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. 2019. Certified Adversarial Robustness via Randomized Smoothing. In International Conference on Machine Learning , volume 97 of ICML , pages 1310-1320.

Krishnamurthy Dvĳotham, Sven Gowal, Robert Stanforth, Relja Arandjelovic, Brendan O'Donoghue, Jonathan Uesato, and Pushmeet Kohli. 2018. Training verified learners with learned verifiers. Preprint , arXiv:1805.10265.

Javid Ebrahimi, Anyi Rao, Daniel Lowd, and Dejing Dou. 2018. HotFlip: White-box adversarial examples for text classification. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers) , pages 31-36, Melbourne, Australia. Association for Computational Linguistics.

Steffen Eger and Yannik Benz. 2020. From hero to zéroe: Abenchmark of low-level adversarial attacks. In Proceedings of the 1st Conference of the Asia-Pacific Chapter of the Association for Computational Linguistics and the 10th International Joint Conference on Natural Language Processing , pages 786-803, Suzhou, China. Association for Computational Linguistics.

- Ji Gao, Jack Lanchantin, Mary Lou Soffa, and Yanjun Qi. 2018. Black-box generation of adversarial text sequences to evade deep learning classifiers. In 2018 IEEE Security and Privacy Workshops (SPW) , pages 50-56.

Siddhant Garg and Goutham Ramakrishnan. 2020. BAE: BERT-based adversarial examples for text classification. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP) , pages 6174-6181, Online. Association for Computational Linguistics.

Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. 2015. Explaining and Harnessing Adversarial Examples. In International Conference on Learning Representations .

- Chuan Guo, Alexandre Sablayrolles, Hervé Jégou, and Douwe Kiela. 2021. Gradient-based adversarial attacks against text transformers. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing , pages 5747-5757, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.

Po-Sen Huang, Robert Stanforth, Johannes Welbl, Chris Dyer, Dani Yogatama, Sven Gowal, Krishnamurthy Dvĳotham, and Pushmeet Kohli. 2019. 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-ĲCNLP) , pages 4083-4093, Hong Kong, China. Association for Computational Linguistics.

Zhuoqun Huang, Neil G Marchant, Keane Lucas, Lujo Bauer, Olga Ohrimenko, and Benjamin Rubinstein. 2023. RS-Del: Edit distance robustness certificates for sequence classifiers via randomized deletion. In Advances in Neural Information Processing Systems , volume 36, pages 18676-18711. Curran Associates, Inc.

Maor Ivgi and Jonathan Berant. 2021. Achieving model robustness through discrete adversarial training. In Proceedings of the 2021 Conference on Empirical MethodsinNaturalLanguageProcessing , pages 15291544, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.

Mohit Iyyer, John Wieting, Kevin Gimpel, and Luke Zettlemoyer. 2018. Adversarial example generation with syntactically controlled paraphrase networks. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers) , pages 1875-1885, New Orleans, Louisiana. Association for Computational Linguistics.

Robin Jia, Aditi Raghunathan, Kerem Göksel, and Percy Liang. 2019. Certified robustness to adversarial word substitutions. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-ĲCNLP) , pages 4129-4142, Hong Kong, China. Association for Computational Linguistics.

- Di Jin, Zhĳing Jin, Joey Tianyi Zhou, and Peter Szolovits. 2020. Is BERT Really Robust? A Strong Baseline for Natural Language Attack on Text Classification and Entailment. Proceedings of the AAAI Conference on Artificial Intelligence , 34(05):8018-8025.

Vladimir Karpukhin, Omer Levy, Jacob Eisenstein, and Marjan Ghazvininejad. 2019. Training on synthetic noise improves robustness to natural noise in machine translation. In Proceedings of the 5th Workshop on Noisy User-generated Text (W-NUT 2019) , pages 42-47, Hong Kong, China. Association for Computational Linguistics.

Anupriya Kumari, Devansh Bhardwaj, Sukrit Jindal, and Sarthak Gupta. 2023. Trust, but verify: A survey of randomized smoothing techniques. Preprint , arXiv:2312.12608.

Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. 2019. Certified robustness to adversarial examples with differential privacy. In 2019 IEEE Symposium on Security and Privacy (SP) , pages 656-672.

- Alexander Levine and Soheil Feizi. 2020. Robustness certificates for sparse adversarial attacks by randomized ablation. Proceedings of the AAAI Conference on Artificial Intelligence , 34(04):4585-4593.

Dianqi Li, Yizhe Zhang, Hao Peng, Liqun Chen, Chris Brockett, Ming-Ting Sun, and Bill Dolan. 2021. Contextualized perturbation for textual adversarial attack. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies , pages 5053-5069, Online. Association for Computational Linguistics.

Linyang Li, Ruotian Ma, Qipeng Guo, Xiangyang Xue, and Xipeng Qiu. 2020. BERT-ATTACK: Adversarial attack against BERT using BERT. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP) , pages 6193-6202, Online. Association for Computational Linguistics.

Andrew L. Maas, Raymond E. Daly, Peter T. Pham, Dan Huang, Andrew Y. Ng, and Christopher Potts. 2011. Learning word vectors for sentiment analysis. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies , pages 142-150, Portland, Oregon, USA. Association for Computational Linguistics.

Matthew Mirman, Timon Gehr, and Martin Vechev. 2018. Differentiable abstract interpretation for provably robust neural networks. In Proceedings of the 35th International Conference on Machine Learning , volume 80 of Proceedings of Machine Learning Research , pages 3578-3586. PMLR.

Takeru Miyato, Andrew M. Dai, and Ian Goodfellow. 2017. Adversarial training methods for semisupervised text classification. In International Conference on Learning Representations .

John Morris, Eli Lifland, Jin Yong Yoo, Jake Grigsby, Di Jin, and Yanjun Qi. 2020. TextAttack: A framework for adversarial attacks, data augmentation, and adversarial training in NLP. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations , pages 119-126, Online. Association for Computational Linguistics.

Samuel Pfrommer, Brendon G. Anderson, and Somayeh Sojoudi. 2023. Projected randomized smoothing for certified adversarial robustness. Transactions on Machine Learning Research .

Vinodkumar Prabhakaran, Ben Hutchinson, and Margaret Mitchell. 2019. Perturbation sensitivity analysis to detect unintended model biases. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-ĲCNLP) , pages 5740-5745, Hong Kong, China. Association for Computational Linguistics.

Fanchao Qi, Yangyi Chen, Xurui Zhang, Mukai Li, Zhiyuan Liu, and Maosong Sun. 2021. Mind the style of text! Adversarial and backdoor attacks based on text style transfer. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing , pages 4569-4580, Online and

Punta Cana, Dominican Republic. Association for Computational Linguistics.

Xiangyu Qi, Kaixuan Huang, Ashwinee Panda, Peter Henderson, Mengdi Wang, and Prateek Mittal. 2024. Visual adversarial examples jailbreak aligned large language models. Proceedings of the AAAI Conference on Artificial Intelligence , 38(19):21527-21536.

Vyas Raina, Adian Liusie, and Mark Gales. 2024. Is LLM-as-a-Judge robust? investigating universal adversarial attacks on zero-shot LLM assessment. Preprint , arXiv:2402.14016.

Hannah Rashkin, Eunsol Choi, Jin Yea Jang, Svitlana Volkova, and Yejin Choi. 2017. Truth of varying shades: Analyzing language in fake news and political fact-checking. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing , pages 2931-2937, Copenhagen, Denmark. Association for Computational Linguistics.

Shuhuai Ren, Yihe Deng, Kun He, and Wanxiang Che. 2019. Generating natural language adversarial examples through probability weighted word saliency. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics , pages 10851097, Florence, Italy. Association for Computational Linguistics.

Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus. 2014. Intriguing properties of neural networks. In International Conference on Learning Representations .

Hélène Touzet. 2016. On the Levenshtein automaton and the size of the neighbourhood of a word. In Language and Automata Theory and Applications , pages 207218, Cham. Springer International Publishing.

Robert A. Wagner and Michael J. Fischer. 1974. The string-to-string correction problem. Journal of the ACM , 21(1):168-173.

Tianlu Wang, Xuezhi Wang, Yao Qin, Ben Packer, Kang Li, Jilin Chen, Alex Beutel, and Ed Chi. 2020. CATgen: Improving robustness in NLP models via controlled adversarial text generation. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP) , pages 5141-5146, Online. Association for Computational Linguistics.

Wenjie Wang, Pengfei Tang, Jian Lou, and Li Xiong. 2021a. Certified robustness to word substitution attack with differential privacy. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies , pages 1102-1112, Online. Association for Computational Linguistics.

Xiaosen Wang, Yichen Yang, Yihe Deng, and Kun He. 2021b. Adversarial training with fast gradient projection method against synonym substitution based text attacks. Proceedings of the AAAI Conference on Artificial Intelligence , 35(16):13997-14005.

Yibin Wang, Yichen Yang, Di He, and Kun He. 2023. Robustness-aware word embedding improves certified robustness to adversarial word substitutions. In Findings of the Association for Computational Linguistics: ACL 2023 , pages 673-687, Toronto, Canada. Association for Computational Linguistics.

Lily Weng, Huan Zhang, Hongge Chen, Zhao Song, ChoJui Hsieh, Luca Daniel, Duane Boning, and Inderjit Dhillon. 2018. Towards fast computation of certified robustness for ReLU networks. In Proceedings of the 35th International Conference on Machine Learning , volume 80 of Proceedings of Machine Learning Research , pages 5276-5285. PMLR.

Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Remi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander Rush. 2020. Transformers: State-of-the-art natural language processing. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations , pages 38-45, Online. Association for Computational Linguistics.

Eric Wong and Zico Kolter. 2018. Provable defenses against adversarial examples via the convex outer adversarial polytope. In Proceedings of the 35th International Conference on Machine Learning , volume 80 of Proceedings of Machine Learning Research , pages 5286-5295. PMLR.

Fan Yang, Arjun Mukherjee, and Eduard Dragut. 2017. Satirical news detection and analysis using attention mechanism and linguistic features. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing , pages 1979-1989, Copenhagen, Denmark. Association for Computational Linguistics.

MaoYe, Chengyue Gong, and Qiang Liu. 2020. SAFER: A structure-free approach for certified robustness to adversarial word substitutions. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics , pages 3465-3475, Online. Association for Computational Linguistics.

Yuan Zang, Fanchao Qi, Chenghao Yang, Zhiyuan Liu, Meng Zhang, Qun Liu, and Maosong Sun. 2020. Word-level textual adversarial attacking as combinatorial optimization. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics , pages 6066-6080, Online. Association for Computational Linguistics.

Jiehang Zeng, Jianhan Xu, Xiaoqing Zheng, and Xuanjing Huang. 2023. Certified robustness to text adversarial attacks by randomized [MASK]. Computational Linguistics , 49(2):395-427.

- X. Zhang, H. Hong, Y. Hong, P. Huang, B. Wang, Z. Ba, and K. Ren. 2024a. Text-CRS: A generalized certified robustness framework against textual adversarial

attacks. In 2024 IEEE Symposium on Security and Privacy (SP) , pages 56-56, Los Alamitos, CA, USA. IEEE Computer Society.

Xiang Zhang, Junbo Zhao, and Yann LeCun. 2015. Character-level convolutional networks for text classification. In Advances in Neural Information Processing Systems , volume 28. Curran Associates, Inc.

Xinze Zhang, Junzhe Zhang, Zhenhua Chen, and Kun He. 2021. Crafting adversarial examples for neural machine translation. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers) , pages 1967-1977, Online. Association for Computational Linguistics.

Zeliang Zhang, Wei Yao, Susan Liang, and Chenliang Xu. 2024b. Random smooth-based certified defense against text adversarial attack. In Findings of the Association for Computational Linguistics: EACL 2024 , pages 1251-1265, St. Julian's, Malta. Association for Computational Linguistics.

Chen Zhu, Yu Cheng, Zhe Gan, Siqi Sun, Tom Goldstein, and Jingjing Liu. 2020. FreeLB: Enhanced adversarial training for natural language understanding. In International Conference on Learning Representations .

Liu Zhuang, Lin Wayne, Shi Ya, and Zhao Jun. 2021. A robustly optimized BERT pre-training approach with post-training. In Proceedings of the 20th Chinese National Conference on Computational Linguistics , pages 1218-1227, Huhhot, China. Chinese Information Processing Society of China.

## A Proofs for Section 3.2

In this appendix, we provide proofs of the certification results presented in Section 3.2. Our proofs follow (Huang et al., 2023), however we additionally provide an upper bound on the smoothed classifier's score, which is needed to support certification of multi-class classifiers.

We begin by defining notation to express the deletion mechanism symbolically. Recall from Section 3.1 that 𝝐 = ( 𝜖 1 , . . . , 𝜖 𝑛 ) is a vector of deletion indicator variables for input text 𝒙 containing 𝑛 = | t ( 𝒙 )| tokens, where 𝜖 𝑖 = 1 if the 𝑖 -th token is to be deleted and 𝜖 𝑖 = 0 otherwise. The space of possible deletion indicators for input text 𝒙 is denoted E( 𝒙 ) = { 0 1 , } | t ( 𝒙 ) | . We let 𝑞 ( 𝝐 ) = ˛ 𝑖 𝑝 𝜖 𝑖 del ( 1 -𝑝 del ) 1 -𝜖 𝑖 denote the (Bernoulli) probability mass for a given 𝝐 . Wewrite apply ( 𝒙 𝝐 , ) to denote the resultant text after deleting the tokens referenced in 𝝐 from text 𝒙 .

Using this notation, we can express the smoothed classifier's score defined in (3) as a sum over the space of deletion indicator variables:

$$p _ { y } ( { \boldsymbol x } ) = \sum _ { \epsilon \in \mathcal { E } ( { \boldsymbol x } ) } s ( \epsilon, { \boldsymbol x } ) \text{ \quad \ \ } ( 4 )$$

$$\text{with} \, s ( \epsilon, x ) = q ( \epsilon ) { 1 } _ { f _ { b } ( \text{apply} ( x, \epsilon ) ) = y }. \quad ( 5 )$$

The first step in our analysis is to identify a correspondence between deletions for neighboring text. Let

$$\zeta = \{ \, ( \epsilon, \epsilon ^ { \prime } ) \in \mathcal { E } ( x ) \times \mathcal { E } ( x ) \, \colon \forall i, \epsilon _ { i } \leq \epsilon _ { i } ^ { \prime } \, \}.$$

be a partial order on the space of deletion indicators E( 𝒙 ) . We can then write 𝝐 ⊑ 𝝐 ′ if 𝝐 ′ can be obtained from 𝝐 by deleting additional tokens. This allows us to define a set of deletions building on 𝝐 :

$$\mathcal { E } ( x, \epsilon ) \coloneqq \{ \, \epsilon ^ { \prime } \in \mathcal { E } ( x ) \, \colon \epsilon \sqsubseteq \epsilon ^ { \prime } \, \}. \quad ( 6 )$$

The following result adapted from (Huang et al., 2023, Lemma 4) identifies pairs of deletions ¯ to 𝝐 ¯ 𝒙 and 𝝐 to 𝒙 such that the terms 𝑠 ( ¯ 𝒙 𝝐 , ¯ ) and 𝑠 ( 𝒙 𝝐 , ) are proportional.

Lemma 3 (Huang et al., 2023) . Let 𝒛 ★ be a longest common subsequence (Wagner and Fischer, 1974) of t ( ¯ 𝒙 ) and t ( 𝒙 ) , and let ¯ 𝝐 ★ ∈ E( ¯ 𝒙 ) and 𝝐 ★ ∈ E( 𝒙 ) be any deletions such that apply ( ¯ 𝒙 𝝐 , ¯ ★ ) = apply ( 𝒙 𝝐 , ★ ) = t -1 ( 𝒛 ★ ) . Then there exists a bĳection 𝑚 : E( ¯ 𝒙 𝝐 , ¯ ★ ) → E( 𝒙 𝝐 , ★ ) such that apply ( ¯ 𝒙 𝝐 , ¯ ) = apply ( ¯ 𝒙 𝝐 , ★ ) for any ¯ 𝝐 ⊒ ¯ 𝝐 ★ . Furthermore for 𝝐 = 𝑚 ( ¯ 𝝐 ) we have

$$s ( \bar { \epsilon }, \bar { x } ) = p _ { \text{de} } ^ { | \text{t} ( \bar { x } ) | - | \text{t} ( x ) | } s ( \epsilon, x ).$$

Using the above result, we can relate the smoothed classifier's score at ¯ and 𝒙 𝒙 as follows:

$$\text{in of } \text{in your case} \, \text{as no way}. \\ \vdots & \text{the} \\ \text{from} \\ \text{or} & \text{of} \\ \text{con} \text{-} \\ \vdots & \text{the} \\ \text{wise}. \\ \text{r in-} \\ \text{let} \\ \vdots \\ \text{r} \, \text{in-} \\ \vdots \\ \text{r} \, \text{in-} \\ \vdots \\ \text{let} \\ \vdots \\ \text{r} \, \text{in-} \\ \vdots \\ \text{r} \, \text{in-} \\ \vdots \\ \text{r} \, \text{in-} \\ \vdots \\ \text{r} \, \text{in-} \\ \vdots \\ \text{r} \, \text{in-} \\ \vdots \\ \text{r} \, \text{in-} \\ \vdots \\ \text{r} \, \text{in-} \\ \vdots \\ \text{r} \, \text{in-} \\ \vdots \\ \text{r} \, \text{in-} \\ \vdots \\ \text{r} \, \text{in-} \\ \vdots \\ \text{r} \, \text{in-} \\ \vdots \\ \text{r} \, \text{in-}
 \end{cases}$$

We can bound the sums in the above expression using the following result.

Lemma 4. We have

$$0 \leq \sum _ { \epsilon \notin \mathcal { E } ( x, \epsilon ^ { * } ) } s ( \epsilon, x ) \leq 1 - p _ { \text{del} } ^ { \sum _ { i } \epsilon _ { i } ^ { * } }.$$

Proof. The lower bound is straightforward, since the summand is non-negative. For the upper bound, observe that

$$\dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \delta \end{array} \rho \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \ delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta\delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \dta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \Delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \dia \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \ Delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta \delta
e r e w t h a t$$

□

Combining these results yields upper and lower bounds on the smoothed classifier's score for neighboring text ¯ to input text 𝒙 𝒙 .

Theorem 1 (General pairwise certificate) . Consider a pair of text inputs 𝒙 𝒙 , ¯ ∈ X . Suppose ¯ 𝒙 can be transformed into 𝒙 using a minimal number of edit operations by deleting 𝑛 del tokens, inserting 𝑛 ins tokens and substituting 𝑛 sub tokens-i.e., dist o t , ( ¯ 𝒙 𝒙 , ) = 𝑛 sub + 𝑛 ins + 𝑛 del . Then the smoothed classifier's scores for any class 𝑦 ∈ Y satisfy

$$p _ { \text{del} } ^ { n _ { \text{del} } - n _ { \text{ins} } } & \left ( p _ { y } ( \boldsymbol x ) - 1 + p _ { \text{del} } ^ { n _ { \text{sub} } + n _ { \text{ins} } } \right ) \leq p _ { y } ( \bar { \boldsymbol x } ) \\ & \leq p _ { \text{del} } ^ { n _ { \text{del} } - n _ { \text{ins} } } p _ { y } ( \boldsymbol x ) + 1 - p _ { \text{del} } ^ { n _ { \text{sub} } + n _ { \text{del} } }.$$

Proof. We obtain upper and lower bounds on the expression for 𝑝 𝑦 ( ¯ 𝒙 ) in (7) using Lemma 4. Replacing the sum over ¯ by a lower bound and the 𝝐 sum over 𝝐 by an upper bound yields:

$$p _ { y } ( \bar { \mathbf x } ) \geq p _ { \text{del} } ^ { | \mathbf t ( \bar { \mathbf x } ) | - | \mathbf t ( \mathbf x ) | } \left ( p _ { y } ( \mathbf x ) - 1 + p _ { \text{del} } ^ { \sum _ { i } \epsilon _ { i } ^ { * } } \right ). \quad \ \ E$$

Similarly, replacing the sum over ¯ 𝝐 by an upper bound and the sum over 𝝐 by a lower bound yields:

$$p _ { y } ( \bar { x } ; h ) \leq p _ { \text{del} } ^ { | \mathfrak { t } ( \bar { x } ) | - | \mathfrak { t } ( \mathbf x ) | } p _ { y } ( \mathbf x ) + 1 - p _ { \text{del} } ^ { \sum _ { i } \bar { \epsilon _ { i } } ^ { * } } \quad \text{,}$$

The final result is obtained by observing | t ( 𝒙 )| = | t ( ¯ 𝒙 )| + 𝑛 ins -𝑛 del , ˝ 𝑖 ¯ 𝜖 ★ 𝑖 = 𝑛 sub + 𝑛 del and ˝ 𝑖 𝜖 ★ 𝑖 = 𝑛 sub + 𝑛 ins . □

Finally we extend the pairwise certificate to a certificate over a Levenshtein (edit) distance ball.

Theorem 2 (Levenshtein distance certificate) . Consider a text input 𝒙 ∈ X for which a lower bound on the smoothed classifier's highest score 𝜇 𝑦 and an upper bound on the smoothed classifier's runner-up score 𝜇 𝑦 ′ satisfy 𝜇 𝑦 ≥ 𝜇 𝑦 ′ . Then the smoothed classifier predicts 𝑦 for any neighboring text input ¯ 𝒙 ∈ X such that dist o t , ( ¯ 𝒙 𝒙 , ) ≤ 𝑟 with o = { del , ins , sub } and 𝑟 = ⌊ log 𝑝 del 1 2 ( 2 + 𝜇 𝑦 ′ -𝜇 𝑦 )⌋ . If the upper and lower bounds hold jointly with confidence 1 -𝛼 , then the certificate holds with probability 1 -𝛼 .

Proof. By definition, the smoothed classifier is robust in the Levenshtein distance neighborhood 𝐵 𝑟 ( 𝒙 ; o t , ) iff the difference between the score for the predicted class 𝑦 and any other class 𝑦 ′′ ≠ 𝑦 is positive for all ¯ 𝒙 ∈ 𝐵 𝑟 ( 𝒙 ; o t , ) :

$$\min _ { \tilde { x } \in B _ { r } ( x ; o, t ) } \left \{ p _ { y } ( \tilde { x } ) - \max _ { y ^ { \prime \prime } \neq y } p _ { y ^ { \prime \prime } } ( \tilde { x } ) \right \} > 0. \quad ( 8 )$$

This condition is satisfied if a lower bound on the LHS is positive. We obtain a lower bound on the LHS using bounds on 𝑝 𝑦 ( ¯ 𝒙 ) from Theorem 1 and bounds on 𝑝 𝑦 ( 𝒙 ) from the theorem statement:

$$\underset { \underset { \underset { \underset { \underset { \underset { \underset { \underset { \underset { \underset { \underset { \underset { \underset { \underset { \underset { \underset { \underset { \underset { \underset { \underset { \underset { \underset { \underset { \max } } } } } } } } } } } } } \underline { \ } } L H S \, \text{of} \, ( 8 ) \geq \min _ { \underset { \underset { \underset { \underset { \underset { \underset { \underset { \max } } } } } } } } \psi ( n _ { \text{del} }, n _ { \text{ins} }, n _ { \text{sub} } ) \\ \underset { \underset { \underset { \underset { \underset { \underset { \max } } } } } } \text{$\psi$}$$

where the objective is

$$& \ t h e d \quad \psi ( n _ { \text{del} }, n _ { \text{ins} }, n _ { \text{sub} } ) = p _ { \text{del} } ^ { n _ { \text{del} } - n _ { \text{ins} } } ( \mu _ { y } - 1 + p _ { \text{del} } ^ { n _ { \text{sub} } + n _ { \text{ins} } } ) \\ & \quad - p _ { \text{del} } ^ { n _ { \text{del} } - n _ { \text{ins} } } \mu _ { y ^ { \prime } } - 1 + p _ { \text{del} } ^ { n _ { \text{sub} } + n _ { \text{del} } }.$$

It is straightforward to show that this objective is monotonically decreasing in 𝑛 sub , hence the minimum occurs at ( 𝑛 del , 𝑛 ins , 𝑛 sub ) = ( 0 0 , , 𝑟 ) . Recalling that the lower bound 𝜓 ( 0 0 , , 𝑟 ) must be positive to guarantee robustness, and solving for 𝑟 , yields

$$r \leq \log _ { p _ { \text{del} } } \left ( 2 + \mu _ { y ^ { \prime } } - \mu _ { y } / 2 \right ). \quad \quad ( 9 )$$

Enforcing the constraint that 𝑟 is an integer yields the required result. □

## B Parameter settings

We fine-tune the RoBERTa model for the noncertified baseline, CERT-ED and RanMASK on the respective training datasets. The default parameter settings for the experiments are shown in Table 5. We do not explicitly calibrate the optimizer or training schedule for each model, as we find the default settings work well across all datasets. When approximating the smoothed models (CERT-ED and RanMASK) we use a Monte Carlo sample of 1000 perturbed inputs for prediction and 4000 perturbed inputs for certification, while setting the significance level to 0.05.

Table 5: Parameter settings for RoBERTa, the optimizer and training procedure. Parameter settings are consistent across all models (Baseline, CERT-ED, RanMASK) except where specified.

| Parameter                                                   | Values                                            |
|-------------------------------------------------------------|---------------------------------------------------|
| AutoModelForSequenceClassification("roberta-base")          | Base model Model                                  |
| Tokenizer                                                   | AutoTokenizer("roberta-base")                     |
| Python command transformers.get_linear_schedule_with_warmup | Scheduler                                         |
| Warmup epochs                                               | 10                                                |
| Python class                                                | torch.optim.AdamW                                 |
| Learning rate                                               | Optimizer 2.0E-5                                  |
| Weight decay                                                | 1.0E-6                                            |
| Gradient clipping                                           | clip_grad_norm_(model.parameters(), 1.0)          |
| Batch size                                                  | 32                                                |
| Max. epoch                                                  | Training 200                                      |
| Early stopping                                              | No improvement in validation loss after 25 epochs |

## C Certified robustness

## C.2 Certified accuracy plots

## C.1 Certification statistics

Wefirst present results of CERT-ED and RanMASK on the AG-News, LUN, and SatNews datasets (Table 6). In general, we see a minor drop in clean accuracy with increasing perturbation strength for both methods. Although in one case RanMASK suffers a catastrophic drop in accuracy to to 50% for IMDB with a perturbation strength of 95%. Surprisingly on SatNews, the smoothed classifiers achieve a higher clean accuracy than the baseline model. While smoothing does not significantly impact accuracy on the AG-News, LUN and SatNews datasets, it does have a pronounced impact on the IMDB dataset. This is likely due to the fact that the IMDB sentiment classification task is more sensitive to small perturbations such as names (Prabhakaran et al., 2019).

Weobservethat CERT-EDdominatesRanMASK in terms of clean accuracy and certified cardinality for 4 out of 5 datasets. However, for the shorter AGNews dataset with an average input length of 37.84 words, the results are more mixed, with RanMASK coming out on top when the perturbation strength is above 90%. This is to be expected, as masking preserves more spatial information compared to deletion, and it becomes advantageous when the input text sequence is shorter. We provide a more detailed analysis in Section C.4.

Figure 3 plots the certified accuracy as a function of the log certified cardinality and perturbation strength for 4 datasets: AG-News, IMDB, Spamassassin, and LUN. The corresponding plot for SatNews is featured in Figure 2. Note that we are varying the cardinality of the certificate, rather than the radius, so that we can reasonably compare the size of CERT-ED and RanMASK certificates, which are defined using different distance metrics (Levenshtein distance for CERT-ED, and Hamming distance for RanMASK). We compute the cardinality exactly for Hamming distance and use a lower bound for Levenshtein distance, which typically underestimates the exact value by 1 order of magnitude. Similar to the results in Table 3, CERT-ED outperforms RanMASK on both LUN and SatNews for all perturbation strengths. For AG-News, the results are more mixed with RanMASK outperforming CERT-ED at a perturbation strength of 90%.

## C.3 Impact of deletion rate

We present a comprehensive ablation study of CERT-ED with varying deletion rates in Table 7. We observe that for shorter sequences, the deletion rate has a more significant impact on the clean accuracy. For IMDB, the maximum possible certified cardinality is much lower compared to other datasets, further demonstrating the sensitivity of sentiment classification to perturbations. Being the simplest dataset, Spam-assassin has the highest certified cardinality among all datasets.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00728v1-figure-4f45a370-08bb-4f17-bb5c-5d6e65aa191f.jpg)

(a) AG-News dataset

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00728v1-figure-10642be5-1a01-45cc-b475-7c709e56cec5.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00728v1-figure-de30fc29-c90e-46b5-b79a-f8e8332f3ca9.jpg)

## (b) IMDB dataset

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00728v1-figure-591687ee-7a39-43ed-acd5-472c8c35b1d7.jpg)

(c) Spam-assassin dataset

(d) LUN dataset

Figure 3: Certified accuracy for CERT-ED and RanMASK as a function of log certified cardinality and perturbation strength 𝑝 del and 𝑝 mask (line styles). The certified cardinality is exact for RanMASK but a lower bound is used for CERT-ED. CERT-ED dominates RanMASK in terms of certified accuracy for 3 out of 4 datasets. See Figure 2 for certified accuracy on SatNews.

| Model                                     | 𝑝 del / 𝑝 mask                            | Clean Accuracy                            | Median CR                                 | Median log CC                             |
|-------------------------------------------|-------------------------------------------|-------------------------------------------|-------------------------------------------|-------------------------------------------|
| AG-News dataset (avg length 37.84)        | AG-News dataset (avg length 37.84)        | AG-News dataset (avg length 37.84)        | AG-News dataset (avg length 37.84)        | AG-News dataset (avg length 37.84)        |
| Baseline                                  | -                                         | 94.84%                                    | -                                         | -                                         |
|                                           | 80%                                       | 93.91%                                    | 2                                         | 12.25                                     |
| RanMASK                                   | 90%                                       | 92.43%                                    | 4                                         | 22.91                                     |
|                                           | 95%                                       | 88.86%                                    | 4                                         | 23.67                                     |
|                                           | 80%                                       | 93.33%                                    | 2                                         | 12.65                                     |
| CERT-ED                                   | 90%                                       | 91.72%                                    | 3                                         | 18.65                                     |
|                                           | 95%                                       | 87.75%                                    | 3                                         | 18.65                                     |
| IMDB dataset (avg length 231.16)          | IMDB dataset (avg length 231.16)          | IMDB dataset (avg length 231.16)          | IMDB dataset (avg length 231.16)          | IMDB dataset (avg length 231.16)          |
| Baseline                                  | -                                         | 93.47%                                    | -                                         | -                                         |
|                                           | 80%                                       | 90.23%                                    | 1                                         | 7.41                                      |
| RanMASK                                   | 90%                                       | 86.87%                                    | 2                                         | 14.02                                     |
|                                           | 95%                                       | 50.00%                                    | 2                                         | 9.40                                      |
|                                           | 80%                                       | 89.60%                                    | 1                                         | 7.50                                      |
| CERT-ED                                   | 90%                                       | 88.26%                                    | 2                                         | 14.49                                     |
|                                           | 95%                                       | 85.58%                                    | 3                                         | 21.20                                     |
| Spam-assassin dataset (avg length 228.16) | Spam-assassin dataset (avg length 228.16) | Spam-assassin dataset (avg length 228.16) | Spam-assassin dataset (avg length 228.16) | Spam-assassin dataset (avg length 228.16) |
| Baseline                                  | -                                         | 98.02%                                    | -                                         | -                                         |
|                                           | 80%                                       | 97.86%                                    | 3                                         | 19.99                                     |
| RanMASK                                   | 90%                                       | 97.65%                                    | 6                                         | 37.49                                     |
|                                           | 95%                                       | 96.05%                                    | 11                                        | 67.06                                     |
|                                           | 80%                                       | 97.81%                                    | 3                                         | 20.63                                     |
| CERT-ED                                   | 90%                                       | 97.81%                                    | 6                                         | 38.66                                     |
|                                           | 95%                                       | 97.81%                                    | 10                                        | 67.04                                     |
| LUN dataset (avg length 269.93)           | LUN dataset (avg length 269.93)           | LUN dataset (avg length 269.93)           | LUN dataset (avg length 269.93)           | LUN dataset (avg length 269.93)           |
| Baseline                                  | -                                         | 99.16%                                    | -                                         | -                                         |
|                                           | 80%                                       | 98.67%                                    | 3                                         | 19.73                                     |
| RanMASK                                   | 90%                                       | 97.91%                                    | 6                                         | 34.51                                     |
|                                           | 95%                                       | 95.62%                                    | 10                                        | 60.45                                     |
|                                           | 80%                                       | 98.85%                                    | 3                                         | 20.62                                     |
| CERT-ED                                   | 90%                                       | 98.28%                                    | 6                                         | 37.94                                     |
|                                           | 95%                                       | 96.11%                                    | 10                                        | 61.44                                     |
| SatNews dataset (avg length 384.84)       | SatNews dataset (avg length 384.84)       | SatNews dataset (avg length 384.84)       | SatNews dataset (avg length 384.84)       | SatNews dataset (avg length 384.84)       |
| Baseline                                  | -                                         | 94.22%                                    | -                                         | -                                         |
|                                           | 80%                                       | 93.10%                                    | 2                                         | 14.30                                     |
| RanMASK                                   | 90%                                       | 92.09%                                    | 4                                         | 27.84                                     |
|                                           | 95%                                       | 90.10%                                    | 7                                         | 47.09                                     |
|                                           | 80%                                       | 95.60%                                    | 2                                         | 14.83                                     |
| CERT-ED                                   | 90%                                       | 93.18%                                    | 5                                         | 35.08                                     |
|                                           | 95%                                       | 92.07%                                    | 8                                         | 54.76                                     |

Table 6: Full certification results supplementing Table 3. All metrics are computed using the entire test set. 'Median CR' is the median certified Levenshtein distance radius and 'median log CC' is the median log-certified cardinality. The certified cardinality is exact for RanMASK, however a lower bound is used for CERT-ED. CERT-ED outperforms RanMASK in terms of certified accuracy for for 4 out of 5 datasets and 22 out of 30 metrics, and it specifically excels on datasets with longer average text length.

| CERT-ED 𝑝 del                             | Clean Accuracy                            | Median CR                                 | Median log CC                             |
|-------------------------------------------|-------------------------------------------|-------------------------------------------|-------------------------------------------|
| AG-News dataset (avg length 37.84)        | AG-News dataset (avg length 37.84)        | AG-News dataset (avg length 37.84)        | AG-News dataset (avg length 37.84)        |
| 50%                                       | 94.76                                     | 0                                         | 0.00                                      |
| 60%                                       | 95.07                                     | 1                                         | 6.55                                      |
| 70%                                       | 94.58                                     | 1                                         | 6.56                                      |
| 80%                                       | 93.33                                     | 2                                         | 12.65                                     |
| 90%                                       | 91.72                                     | 3                                         | 18.65                                     |
| 95%                                       | 87.75                                     | 3                                         | 18.65                                     |
| 99%                                       | 25.05                                     | 0                                         | 0.00                                      |
| IMDB dataset (avg length 231.16)          | IMDB dataset (avg length 231.16)          | IMDB dataset (avg length 231.16)          | IMDB dataset (avg length 231.16)          |
| 50%                                       | 94.34                                     | 0                                         | 0.00                                      |
| 60%                                       | 93.16                                     | 1                                         | 7.11                                      |
| 70%                                       | 93.00                                     | 1                                         | 7.14                                      |
| 80%                                       | 89.60                                     | 1                                         | 7.50                                      |
| 90%                                       | 88.26                                     | 2                                         | 14.49                                     |
| 95%                                       | 85.58                                     | 3                                         | 21.20                                     |
| 99%                                       | 68.02                                     | 6                                         | 39.64                                     |
| Spam-assassin dataset (avg length 228.16) | Spam-assassin dataset (avg length 228.16) | Spam-assassin dataset (avg length 228.16) | Spam-assassin dataset (avg length 228.16) |
| 50%                                       | 98.19                                     | 0                                         | 0.00                                      |
| 60%                                       | 98.49                                     | 1                                         | 7.32                                      |
| 70%                                       | 98.23                                     | 1                                         | 7.32                                      |
| 80%                                       | 97.81                                     | 3                                         | 20.63                                     |
| 90%                                       | 97.81                                     | 6                                         | 38.66                                     |
| 95%                                       | 97.81                                     | 10                                        | 67.04                                     |
| 99%                                       | 84.19                                     | 25                                        | 152.84                                    |
| LUN dataset (avg length 269.93)           | LUN dataset (avg length 269.93)           | LUN dataset (avg length 269.93)           | LUN dataset (avg length 269.93)           |
| 50%                                       | 99.29                                     | 0                                         | 0.00                                      |
| 60%                                       | 99.33                                     | 1                                         | 7.48                                      |
| 70%                                       | 99.40                                     | 1                                         | 7.48                                      |
| 80%                                       | 98.85                                     | 3                                         | 20.62                                     |
| 90%                                       | 98.28                                     | 6                                         | 37.94                                     |
| 95%                                       | 96.11                                     | 10                                        | 61.44                                     |
| 99%                                       | 86.89                                     | 19                                        | 118.78                                    |
| SatNews dataset (avg length 384.84)       | SatNews dataset (avg length 384.84)       | SatNews dataset (avg length 384.84)       | SatNews dataset (avg length 384.84)       |
| 50%                                       | 94.97                                     | 0                                         | 0.00                                      |
| 60%                                       | 96.53                                     | 1                                         | 7.59                                      |
| 70%                                       | 95.03                                     | 1                                         | 7.59                                      |
| 80%                                       | 95.60                                     | 2                                         | 14.83                                     |
| 90%                                       | 93.18                                     | 5                                         | 35.08                                     |
| 95%                                       | 92.07                                     | 8                                         | 54.76                                     |
| 99%                                       | 85.81                                     | 16                                        | 104.73                                    |

Table 7: Ablation study of CERT-ED with varying deletion rates 𝑝 del . All metrics are computed using the entire test set. 'Median CR' is the median certified Levenshtein distance radius and 'median log CC' is the medianlog-certified cardinality. The certified cardinality is estimated using a lower bound. For datasets with longer text, the deletion rate has less impact on accuracy.

## C.4 Impact of input text length

The results of clean accuracy and certified cardinality, grouped by text length quintiles, are shown in Table 8. For the AG-News dataset, which has a shorter average text length, RanMASK suffers a minor drop in clean accuracy from Q1 to Q2, while CERT-ED is impacted more significantly. This supports our hypothesis that RanMASK is more advantageous when the input text sequence is shorter.

## D Details on attacks

## D.1 Attack setup

Attacks covered We evaluate empirical robustness under various attacks using a modified version of TextAttack (Morris et al., 2020) and attack templates implemented by Zhang et al. (2024a). We select five representative attacks which can be categorized as follows:

- · Clare (Li et al., 2021) and BAE-I (Garg and Ramakrishnan, 2020) both cover a token-wise edit distance threat model;
- · BERT-Attack (Li et al., 2020) and TextFooler (Jin et al., 2020) operate by substituting words in the input text;
- · DeepWordBug (Gao et al., 2018) modifies the input text by altering characters within each word.

Attack results Each attack can yield one of four distinct outcomes, namely, success , fail , skipped or timeout , Their meanings are as follows:

- · success indicates the attack was able to generate an adversarial example by perturbing the prediction from the correct label to a false label.
- · fail indicates the attack was unable to generate an adversarial example. This can happen for the following reasons: firstly, the attack was unable to find a perturbation that changes the prediction; secondly, the attack was unable to find a perturbation that changes the prediction after exhausting all options; or, lastly, the attack reached the maximum number of queries on the target model. We enforce a maximum limit of 10000 queries for Clare, but place no limit on the other attacks.
- · skipped indicates the attack was skipped because the model's prediction was incorrect in the first place.
- · timeout indicates the attack was skipped because it took too long to generate an adversarial example. In our experiments, we set the timeout to be 600 seconds. Note that this generally puts CERTED at a disadvantage compared to RanMASK, because CERT-ED can process queries roughly 3 times faster than RanMASK. Unless otherwise specified, we treat timeout as fail.

The robust accuracy is defined as the fraction of instances for which the attack outcome is either fail or timeout -i.e., the fraction of instances for which the model's prediction remains correct after the attack.

## D.2 Transfer attack on ag-news

We perform transfer attacks by applying successful attack examples against the non-certified baseline to the smoothed models (CERT-ED, RanMASK). Table 9 reports both clean and robust accuracy since the successful example against each attack will be slightly different. Unlike the direct attack results, CERT-ED does not have a strict dominance over RanMASK against BERT-Attack, TextFooler, and DeepWordBug. While for Clare and BAE-I, CERTED is marginally better rather than tied. These results demonstrate the robustness of CERT-ED to transfer attacks, showing that CERT-ED is more robust to adversarial examples for the non-certified baseline than RanMASK.

## E Efficiency and computation requirements

In this appendix, we document the computation requirements to train, certify, and attack models used in our work. We also compare and contrast the efficiency of CERT-ED and RanMASK in terms of training and certification. We show that CERT-ED is more efficient than RanMASK in both aspects.

## E.1 Hardware

All experiments in this paper are conducted using a private cluster with Intel(R) Xeon(R) Gold 6326 CPU@2.90GHzandNVIDIAA100GPUs. Unless otherwise specified, we use a single GPU for all experiments.

## E.2 Train

Table 10 shows the number of epochs used to train each model/dataset (with early stopping) and the training time per epoch. CERT-ED is about 23 times faster to train than the non-smoothed base-

| Quartile Avg.         | length                | Baseline              | Baseline              | RanMASK 80%           | RanMASK 80%           | RanMASK 90%           | RanMASK 90%           | CERT-ED 80%           | CERT-ED 80%           | CERT-ED 90%           | CERT-ED 90%           |
|-----------------------|-----------------------|-----------------------|-----------------------|-----------------------|-----------------------|-----------------------|-----------------------|-----------------------|-----------------------|-----------------------|-----------------------|
| Quartile Avg.         | length                | ClA%                  | log CC                | ClA%                  | log CC                | ClA%                  | log CC                | ClA%                  | log CC                | ClA%                  | log CC                |
| AG-News dataset       | AG-News dataset       | AG-News dataset       | AG-News dataset       | AG-News dataset       | AG-News dataset       | AG-News dataset       | AG-News dataset       | AG-News dataset       | AG-News dataset       | AG-News dataset       | AG-News dataset       |
| Q1                    | 27.25                 | 93.62                 | -                     | 92.33                 | 11.95                 | 90.85                 | 17.71                 | 91.22                 | 12.39                 | 89.37                 | 12.60                 |
| Q2                    | 35.03                 | 94.93                 | -                     | 93.90                 | 12.18                 | 92.99                 | 17.99                 | 93.90                 | 12.65                 | 92.54                 | 18.58                 |
| Q3                    | 40.38                 | 95.21                 | -                     | 94.00                 | 12.32                 | 92.33                 | 23.72                 | 93.74                 | 12.79                 | 92.43                 | 18.81                 |
| Q4                    | 50.74                 | 95.88                 | -                     | 95.82                 | 12.49                 | 94.00                 | 24.17                 | 94.94                 | 12.93                 | 93.06                 | 24.72                 |
| IMDB dataset          | IMDB dataset          | IMDB dataset          | IMDB dataset          | IMDB dataset          | IMDB dataset          | IMDB dataset          | IMDB dataset          | IMDB dataset          | IMDB dataset          | IMDB dataset          | IMDB dataset          |
| Q1                    | 92.32                 | 94.74                 | -                     | 92.12                 | 6.79                  | 89.56                 | 13.18                 | 90.76                 | 7.05                  | 88.94                 | 13.48                 |
| Q2                    | 147.20                | 95.46                 | -                     | 92.56                 | 13.31                 | 89.06                 | 13.55                 | 90.51                 | 7.21                  | 89.20                 | 13.98                 |
| Q3                    | 215.62                | 94.17                 | -                     | 90.91                 | 13.59                 | 86.88                 | 20.05                 | 89.30                 | 7.41                  | 87.61                 | 14.40                 |
| Q4                    | 461.22                | 89.51                 | -                     | 85.31                 | 7.40                  | 81.93                 | 14.42                 | 87.83                 | 14.51                 | 87.28                 | 21.61                 |
| Spam-assassin dataset | Spam-assassin dataset | Spam-assassin dataset | Spam-assassin dataset | Spam-assassin dataset | Spam-assassin dataset | Spam-assassin dataset | Spam-assassin dataset | Spam-assassin dataset | Spam-assassin dataset | Spam-assassin dataset | Spam-assassin dataset |
| Q1                    | 74.23                 | 98.01                 | -                     | 97.51                 | 18.59                 | 97.84                 | 31.80                 | 98.18                 | 13.78                 | 97.68                 | 30.93                 |
| Q2                    | 171.62                | 99.32                 | -                     | 99.49                 | 19.97                 | 99.49                 | 38.35                 | 99.15                 | 20.54                 | 99.49                 | 39.10                 |
| Q3                    | 281.63                | 96.80                 | -                     | 96.80                 | 20.55                 | 96.13                 | 39.50                 | 96.63                 | 21.14                 | 97.14                 | 40.51                 |
| Q4                    | 395.60                | 97.97                 | -                     | 97.64                 | 21.07                 | 97.13                 | 40.72                 | 97.30                 | 21.70                 | 96.96                 | 41.70                 |
| LUN dataset           | LUN dataset           | LUN dataset           | LUN dataset           | LUN dataset           | LUN dataset           | LUN dataset           | LUN dataset           | LUN dataset           | LUN dataset           | LUN dataset           | LUN dataset           |
| Q1                    | 84.65                 | 99.26                 | -                     | 98.64                 | 18.62                 | 98.21                 | 35.79                 | 98.70                 | 16.87                 | 97.16                 | 32.02                 |
| Q2                    | 226.05                | 99.57                 | -                     | 99.57                 | 20.24                 | 99.19                 | 39.07                 | 99.32                 | 20.83                 | 99.50                 | 39.88                 |
| Q3                    | 363.68                | 98.32                 | -                     | 97.58                 | 14.26                 | 96.40                 | 34.24                 | 98.07                 | 21.55                 | 97.20                 | 41.21                 |
| Q4                    | 404.00                | 99.50                 | -                     | 98.88                 | 21.09                 | 97.83                 | 34.43                 | 99.32                 | 21.72                 | 99.26                 | 41.75                 |
| SatNews dataset       | SatNews dataset       | SatNews dataset       | SatNews dataset       | SatNews dataset       | SatNews dataset       | SatNews dataset       | SatNews dataset       | SatNews dataset       | SatNews dataset       | SatNews dataset       | SatNews dataset       |
| Q1                    | 353.34                | 95.23                 | -                     | 96.12                 | 14.24                 | 94.51                 | 27.71                 | 97.06                 | 14.73                 | 95.23                 | 34.93                 |
| Q2                    | 384.64                | 94.97                 | -                     | 93.76                 | 14.28                 | 92.87                 | 27.77                 | 95.69                 | 14.76                 | 93.98                 | 35.11                 |
| Q3                    | 398.19                | 93.32                 | -                     | 92.05                 | 14.30                 | 91.20                 | 27.82                 | 95.60                 | 14.79                 | 92.10                 | 35.19                 |
| Q4                    | 416.96                | 93.36                 | -                     | 90.36                 | 14.34                 | 89.66                 | 27.91                 | 93.95                 | 14.86                 | 91.36                 | 35.27                 |

Table 8: Clean accuracy (ClA) and median log-certified cardinality (log CC) for RanMASK and CERT-ED as a function of perturbation strength grouped by input text length quintiles. The entire test set is used to compute all metrics. Q1 refers to the first quintile while Q4 refers to the fourth quintile. The certified cardinality is exact for RanMASK but a lower bound is used for CERT-ED.

Table 9: Empirical attack results when transferring successful adversarial examples against the non-certified baseline to CERT-ED and RanMASK. Both CERT-ED and RanMASK use a perturbation strength of 90%. Clean and robust accuracy are abbreviated ClA and RoA, respectively. Highlighted values are the best in each column for that dataset. CERT-ED outperforms RanMASK in all word substitution and character-level attacks.

|                       | Clare                 | Clare                 | BAE-I                 | BAE-I                 | BERT-Attack           | BERT-Attack           | TextFooler            | TextFooler            | DeepWordBug           | DeepWordBug           |
|-----------------------|-----------------------|-----------------------|-----------------------|-----------------------|-----------------------|-----------------------|-----------------------|-----------------------|-----------------------|-----------------------|
| Method                | ClA%                  | RoA%                  | ClA%                  | RoA%                  | ClA%                  | RoA%                  | ClA%                  | RoA%                  | ClA%                  | RoA%                  |
| AG-News dataset       | AG-News dataset       | AG-News dataset       | AG-News dataset       | AG-News dataset       | AG-News dataset       | AG-News dataset       | AG-News dataset       | AG-News dataset       | AG-News dataset       | AG-News dataset       |
| RanMASK CERT-ED       | 93.51 93.66           | 90.41 90.27           | 89.50 90.06           | 86.46 86.74           | 93.30 93.46           | 88.28 89.04           | 94.08 94.21           | 90.77 89.67           | 91.41 91.60           | 82.81 81.45           |
| IMDB dataset          | IMDB dataset          | IMDB dataset          | IMDB dataset          | IMDB dataset          | IMDB dataset          | IMDB dataset          | IMDB dataset          | IMDB dataset          | IMDB dataset          | IMDB dataset          |
| RanMASK CERT-ED       | 79.33 82.02           | 75.51 75.28           | 85.31 86.81           | 82.31 82.76           | 87.73 89.02           | 81.66 83.06           | 87.67 88.94           | 77.30 78.57           | 84.26 85.96           | 76.54 76.70           |
| Spam-assassin dataset | Spam-assassin dataset | Spam-assassin dataset | Spam-assassin dataset | Spam-assassin dataset | Spam-assassin dataset | Spam-assassin dataset | Spam-assassin dataset | Spam-assassin dataset | Spam-assassin dataset | Spam-assassin dataset |
| RanMASK CERT-ED       | 94.92 94.92           | 91.53 89.83           | 95.74 95.74           | 91.49 89.36           | 98.49 98.71           | 95.27 96.34           | 98.21 98.70           | 94.47 94.31           | 96.57 98.86           | 88.57 93.14           |
| LUN dataset           | LUN dataset           | LUN dataset           | LUN dataset           | LUN dataset           | LUN dataset           | LUN dataset           | LUN dataset           | LUN dataset           | LUN dataset           | LUN dataset           |
| RanMASK CERT-ED       | 92.16 96.08           | 90.20 94.12           | 95.29 96.86           | 93.72 96.86           | 97.14 98.33           | 88.57 94.76           | 96.53 98.27           | 87.86 92.49           | 94.20 96.62           | 86.47 91.79           |
| SatNews dataset       | SatNews dataset       | SatNews dataset       | SatNews dataset       | SatNews dataset       | SatNews dataset       | SatNews dataset       | SatNews dataset       | SatNews dataset       | SatNews dataset       | SatNews dataset       |
| RanMASK CERT-ED       | 72.16 80.41           | 69.07 77.32           | 86.15 89.20           | 83.38 86.98           | 88.48 91.24           | 82.95 87.33           | 87.95 90.45           | 82.05 87.50           | 85.59 88.89           | 79.88 86.19           |

Table 10: Training time statistics for each dataset and model. The number of epochs varies due to early stopping.

|               | Train    | Baseline   | Baseline   | RanMASK, 90%   | RanMASK, 90%   | CERT-ED, 90%   | CERT-ED, 90%   |
|---------------|----------|------------|------------|----------------|----------------|----------------|----------------|
| Dataset       | #samples | epochs     | sec/epoch  | epochs         | sec/epoch      | epochs         | sec/epoch      |
| AG-News       | 108 000  | 65         | 517        | 105            | 476            | 100            | 231            |
| IMDB          | 22 500   | 30         | 258        | 60             | 341            | 65             | 128            |
| Spam-assassin | 2 152    | 40         | 27         | 50             | 35             | 40             | 13             |
| LUN           | 13 416   | 55         | 143        | 65             | 258            | 60             | 55             |
| SatNews       | 22 738   | 55         | 260        | 80             | 461            | 95             | 101            |

line, and 2-5 times faster to train than RanMASK. The total computation used across all datasets for certification is estimated to be 70 hours A100 GPU time.

## E.3 Certification

Table 11 shows the average certification time per test instance, including overheads. We see CERT-ED is about 3 times faster than RanMASK on average across all datasets. The total computation used across all datasets for certification is estimated to be 250 hours A100 GPU time.

## E.4 Empirical robustness

Table 12 reports the average attack time per instance for a subset of the IMDB test set. Attack times on other datasets follow a similar pattern. We note that the time taken to attack RanMASK is longer than for the non-smoothed baseline and CERT-

ED. Combined with the max timeout window of 10 minutes, this partially explains the lower robust accuracy of CERT-ED compared to RanMASK in Table 4. We utilized parallelized attacks to speed up the process. The total computation used across all datasets for attacks is estimated to be 200 days A100 GPU time.

## F Edit distance certificates for Text-CRS

In this appendix, we analyze two robustness certificates from the Text-CRS framework (Zhang et al., 2024a), which cover deletion/insertion perturbations to text represented as a sequence of token embedding vectors. Each certificate is parameterized by two radii: one bounds the perturbation to the token embedding vectors and the other bounds the extent of token-level reordering. We obtain lower bounds on these two radii such that each certificate covers up to 𝑟 arbitrary edits of a single type

Table 11: Certification time on the test set for each dataset, including overheads. We use 1 000 Monte Carlo samples for prediction and 4 000 samples for estimating certified radii. During attacks, we use 100 samples for prediction, which cuts the prediction time by 1/40 ignoring overheads.

| Dataset       | Test #samples   | RanMASK, 90% ms / sample   | CERT-ED, 90% ms/sample   |
|---------------|-----------------|----------------------------|--------------------------|
| AG-News       | 7 600           | 3 969                      | 2 367                    |
| IMDB          | 25 000          | 13 331                     | 3 311                    |
| Spam-assassin | 2 378           | 13 899                     | 3 319                    |
| LUN           | 6 454           | 14 641                     | 4 819                    |
| SatNews       | 7 202           | 17 767                     | 5 778                    |

Table 12: Attack time per instance on a subset of 1000 instances from the IMDB test set. The timeout window is set to be 10 minutes. Note that most Clare and BAE-I attacks targeting RanMASK timed out. This partially explains the lower robust accuracy of CERT-ED compared to RanMASK in Table 4.

| Dataset     |   Baseline sec / sample |   RanMASK, 90% sec / sample |   CERT-ED, 90% sec / sample |
|-------------|-------------------------|-----------------------------|-----------------------------|
| Clare       |                     192 |                         527 |                         504 |
| BAE-I       |                     268 |                         502 |                         461 |
| BERT-Attack |                      34 |                         333 |                         234 |
| TextFooler  |                      12 |                         302 |                         173 |
| DeepWordBug |                       7 |                         155 |                          62 |

(deletion/insertion). Using these bounds, we can immediately convert a Text-CRS deletion/insertion certificate to an edit distance certificate where the allowed edit operations are deletions/insertions to input tokens. We find that the resulting edit distance certificates are vacuous ( 𝑟 = 0) for sequences greater than 2 tokens in length when instantiated with the Text-CRS smoothing mechanisms. As a result, we have opted not to include Text-CRS as a baseline in our experiments.

## F.1 Preliminaries

Text-CRS indirectly bounds edits to input text by instead bounding numerical additive perturbations and permutations in word embedding space. This is not in one-to-one correspondence as we see input edits are not easily bounded. Concretely, input text is represented as an array of embedding vectors 𝒘 ∈ R 𝑛 × 𝑘 , where the first dimension corresponds to words and the second dimension corresponds to dimensions in the embedding space. Input text with 𝑚 &lt; 𝑛 actual words is represented by filling the last 𝑛 -𝑚 rows with padding words/vectors. Robustness is studied under input transformations that are a composition of: (1) perturbations to the embedding vectors and (2) word-level permutations of the embedding vectors. Here we define notation to represent these transformations.

Embedding perturbations An embedding perturbation is an array 𝜹 of the same type as the input 𝒘 . The result of applying 𝜹 to 𝒘 is simply 𝒘 + 𝜹 . We consider two norms to measure the magnitude of the perturbation:

- · ∥ 𝜹 ∥ 0 B ˝ 𝑛 𝑖 = 1 1 ˝ 𝑛 𝑗 = 1 | 𝛿 𝑖, 𝑗 | ≠ 0 is the sum of non-zero rows in 𝜹 , i.e., the number of perturbed words/ vectors; and
- · ∥ 𝜹 ∥ 2 B √︃ ˝ 𝑛 𝑖 = 1 𝛿 2 𝑖, 𝑗 is the Frobenius norm.

Permutations A word-level permutation of an input 𝒘 is parameterized by a permutation matrix 𝝅 ∈ P 𝑛 . Here P 𝑛 = { 𝝅 ∈ { 0 1 , } 𝑛 × 𝑛 : ˝ 𝑛 𝑖 ′ = 1 𝜋 𝑖 ′ , 𝑗 = 1 , ˝ 𝑛 𝑗 ′ = 1 𝜋 𝑖, 𝑗 ′ = 1 ∀ 𝑖, 𝑗 } denotes the set of 𝑛 × 𝑛 permutation matrices. The result of applying 𝝅 to 𝒘 is simply 𝜋 · 𝒘 where · denotes matrix multiplication. The magnitude of the perturbation ∥ 𝝅 ∥ 1 is measured in terms of the ℓ 1 distance between the new word locations and the original locations. We can equivalently express this as the row-wise sum of the absolute distance of each 1 from the diagonal in the permutation matrix 𝝅 : ∥ 𝝅 ∥ 1 = ˝ 𝑛 𝑖 = 1 | 𝑖 -˝ 𝑛 𝑗 = 1 𝑗 1 𝜋 𝑖, 𝑗 = 1 | .

Composition The composition of the embedding perturbation 𝜹 and permutation 𝝅 is an input transformation 𝑇 𝜹 𝝅 , : R 𝑛 × 𝑑 → R 𝑛 × 𝑑 such that 𝑇 𝜹 𝝅 , ( 𝒘 ) = 𝝅 · ( 𝒘 + 𝜹 ) .

## F.2 Word-level deletion

Text-CRS covers deletion using a certificate that constrains the number of modified embedding vectors and the sum of word position changes.

Definition 1. A Text-CRS deletion certificate at input 𝒘 ∈ R 𝑛 × 𝑑 is a set of inputs parameterized by two radii 𝑟 𝑅 , 𝑟 𝐷 ≥ 0:

$$C _ { D } ( w ; r _ { R }, r _ { D } ) = \{ T _ { \delta, \pi } ( w ) \in \mathbb { R } ^ { n \times d } \colon \pi \in \mathcal { P } _ { n }, \quad \text{H} \\ \delta \in \mathbb { R } ^ { n \times d }, \| \pi \| _ { 1 } < r _ { R }, \| \delta \| _ { 0 } < r _ { D } \, \}.$$

We note that this form of certificate is not tight for deletion. For example, it includes invalid inputs that contain padding in the middle of the sequence, and it also includes inputs where words are replaced by ordinary (non-padding) words.

Weare interested in determining values of 𝑟 𝑅 and 𝑟 𝐷 such that the Text-CRS deletion certificate covers a standard edit distance certificate constrained to deletions (see (1)). This will allow us to compare Text-CRS and CERT-ED.

Proposition 5. The Text-CRS deletion certificate contains a deletion-based edit distance certificate for any input 𝒘 ∈ R 𝑛 × 𝑑 , meaning 𝐶 𝐷 ( 𝒘 ; 𝑟 𝑅 , 𝑟 𝐷 ) ⊇ 𝐵 𝑟 ( 𝒘 ; { del }) , if

$$r _ { D } = r \ a n d \, r _ { R } \geq \begin{cases} 2 r ( n - r ), & n \geq 2 r, \\ n ^ { 2 } / 2, & n < 2 r. \end{cases}$$

Proof. Let 𝒘 ′ ∈ 𝐵 𝑟 ( 𝒘 ; { del }) be an input obtained from 𝒘 by deleting 𝑙 ≤ 𝑟 elements. We observe that 𝒘 ′ requires the greatest sum of word position changes (as measured by ∥ 𝝅 ∥ 1 for the permutation matrix 𝝅 ) when 𝑙 elements are deleted at the beginning of the sequence and 𝒘 contains no padding words at the end. In this case the permutation matrix is

$$\pi = \begin{pmatrix} 0 & I _ { l } \\ I _ { n - l } & 0 \end{pmatrix}$$

with ∥ 𝝅 ∥ 1 = 2 𝑙 ( 𝑛 -𝑙 ) . Taking the worst-case number of deletions 𝑙 ≤ 𝑟 , we have

$$r _ { R } \geq \max _ { l \in \{ 0, \dots, r \} } 2 l ( n - l ) = \begin{cases} 2 r ( n - r ), & n \geq 2 r, & \text{the $l$} \\ n ^ { 2 } / 2, & n < 2 r. & \text{W} \choose \text{word} \\ \Box & \text{the $p$} \end{cases}$$

Zhang et al. (2024a) instantiate the Text-CRS deletion certificate for a smoothed classifier where the smoothing mechanism permutes the embedding vectors uniformly at random and randomly replaces embedding vectors with padding with fixed probability 𝑝 . For this mechanism, the largest possible value of 𝑟 𝑅 is 𝑛 , which is achieved when the classifier's confidence is 100%. Combining 𝑟 𝑅 ≤ 𝑛 with the inequality in Proposition 5 implies

$$\L ^ { \dagger \dagger } \text{by} \quad n \geq \begin{cases} 2 r ( n - r ), & n \geq 2 r, \\ n ^ { 2 } / 2, & n < 2 r. \end{cases} \Leftrightarrow r \leq \begin{cases} n, & n \leq 2, \\ 0, & n > 2. \end{cases}$$

Hence the edit distance certificate is vacuous ( 𝑟 = 0) when the maximum sequence length 𝑛 &gt; 2.

## F.3 Word-level insertion

Text-CRS covers insertion using a certificate that constrains the perturbation of the embedding vectors (in ℓ 2-distance) and the sum of word position changes.

Definition 2. A Text-CRS insertion certificate at input 𝒘 ∈ R 𝑛 × 𝑑 is a set of inputs parameterized by two radii 𝑟 𝑅 , 𝑟 𝐼 ≥ 0:

$$& C _ { I } ( w ; r _ { R }, r _ { I } ) = \{ T _ { \delta, \pi } ( w ) \in \mathbb { R } ^ { n \times d } \, \colon \pi \in \mathcal { P } _ { n }, \\ & \delta \in \mathbb { R } ^ { n \times d }, \| \pi \| _ { 1 } < r _ { R }, \| \delta \| _ { 2 } < r _ { I } \, \}.$$

Weare interested in determining values of 𝑟 𝑅 and 𝑟 𝐼 such that the Text-CRS insertion certificate covers a standard edit distance certificate constrained to insertions (see (1)).

Proposition 6. Let 𝐸 denote the set of 𝑑 -dimensional embedding vectors (covering all possible words) and let 𝐷 ★ B max 𝒆 1 , 𝒆 2 ∈ 𝐸 ∥ 𝒆 1 -𝒆 2 ∥ 2 . The Text-CRS insertion certificate contains an insertion-based edit distance certificate for any input 𝒘 ∈ 𝐸 𝑛 , meaning 𝐶 𝐼 ( 𝒘 ; 𝑟 𝑅 , 𝑟 𝐼 ) ⊇ 𝐵 𝑟 ( 𝒘 ; { ins }) , if

$$\begin{array} { c c c } \text{gin} \quad & \quad \quad \quad$$

Proof. Let 𝒘 ′ ∈ 𝐵 𝑟 ( 𝒘 ; { ins }) be an input obtained from 𝒘 by inserting 𝑙 ≤ 𝑟 elements. We observe that the corresponding ∥ 𝜹 ∥ 2 is maximized when the 𝑙 inserted vectors are a distance 𝐷 ★ away from the 𝑙 vectors at the end of the original input 𝒘 . In this case ∥ 𝛿 ∥ 2 = √︁ 𝑙 𝐷 ★ 2 = √ 𝑙 𝐷 ★ .

We observe that 𝒘 ′ requires the greatest sum of word position changes (as measured by ∥ 𝝅 ∥ 1 for the permutation matrix 𝝅 ) when the 𝑙 elements are inserted at the beginning of the sequence. In this case the permutation matrix is

$$\pi = \begin{pmatrix} 0 & I _ { n - l } \\ I _ { l } &$$

with ∥ 𝝅 ∥ 1 = 2 𝑙 ( 𝑛 - ) 𝑙 .

Taking the worst case ∥ 𝝅 ∥ 1 with respect to the number of insertions 𝑙 ≤ 𝑟 we have

$$r _ { R } \geq \max _ { l \in \{ 0, \dots, r \}$$

where the maximizer is 𝑙 = 𝑟 for the first case and 𝑙 = 𝑛 / 2 for the second case. Hence we have

$$\begin{smallmatrix} 0 & 0 \\ 0 & 0 \\ 1 & 0 \end{smallmatrix}$$

$$r _ { I } \geq \begin{cases} \sqrt { r } D _ { * }, &$$

Zhang et al. (2024a) instantiate the Text-CRS insertion certificate for a smoothed classifier where the smoothing mechanism permutes the embedding vectors uniformly at random and perturbs the embedding vectors with Gaussian noise with fixed scale parameter 𝜎 . For this mechanism, the largest possible value of 𝑟 𝑅 is 𝑛 , which is achieved when the classifier's confidence is 100%. Combining 𝑟 𝑅 ≤ 𝑛 with the inequalities in Proposition 6 implies

$$r \leq \begin{cases} \min \{ n, \lfloor ( r _ { I } / D _ { * } ) ^ { 2 } \rfloor \} & n \leq 2, \\ 0, & n > 2. \end{cases}$$

For the values of 𝑟 𝐼 and 𝐷 ★ reported by Zhang et al., 𝑟 𝐼 / 𝐷 ★ &lt; 1. Hence the edit distance certificate is vacuous ( 𝑟 = 0) for all sequences.
Zhuoqun Huang Neil G Marchant Olga Ohrimenko Benjamin I. P. Rubinstein
CERT-ED: Certifiably Robust Text Classification for Edit Distance
With the growing integration of AI in daily life, ensuring the robustness of
systems to inference-time attacks is crucial. Among the approaches for
certifying robustness to such adversarial examples, randomized smoothing has
emerged as highly promising due to its nature as a wrapper around arbitrary
black-box models. Previous work on randomized smoothing in natural language
processing has primarily focused on specific subsets of edit distance
operations, such as synonym substitution or word insertion, without exploring
the certification of all edit operations. In this paper, we adapt Randomized
Deletion (Huang et al., 2023) and propose, CERTified Edit Distance defense
(CERT-ED) for natural language classification. Through comprehensive
experiments, we demonstrate that CERT-ED outperforms the existing Hamming
distance method RanMASK (Zeng et al., 2023) in 4 out of 5 datasets in terms of
both accuracy and the cardinality of the certificate. By covering various
threat models, including 5 direct and 5 transfer attacks, our method improves
empirical robustness in 38 out of 50 settings.