CERT - ED : Certifiably Robust Text Classification for Edit Distance (2024)

Abstract: 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.

## 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 @xcite @xcite @xcite @xcite , character-level @xcite @xcite or sentence-level @xcite @xcite , while preserving consistent semantics. although a wide range of defenses have been proposed against adversarial examples, they are routinely broken by subsequent attacks: @xcite and @xcite 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 @xcite . certified robustness methods have been well studied for continuous data that is fixed-dimensional like images @xcite @xcite @xcite . among certification approaches, randomized smoothing @xcite @xcite 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. @xcite and @xcite were the first to investigate randomized smoothing under a synonym substitution threat model. @xcite proposed ranmask that adapts randomized ablation @xcite 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 @xcite would void any of these substitution-based certificates. to remedy this, @xcite 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 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 @xcite , 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. our contributions are summarized as follows: ## 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" @xcite . 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 @xcite @xcite and robustness @xcite at the word-level. we note that 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, @xmath0, 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 ( x, 𝒙), which counts the minimum number of edits required to transform original text x 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: ## 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 @xcite , 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 @xcite not covered by prior work. ## 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 ran-mask @xcite and @xcite . 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 the most robust in 38 out of 50 settings in section 4.2 and appendix d. though cert-ed is empirically more robust than ranmask against word substitution and character-level 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. ## related work despite the rapid advancement of neural networks for many important tasks, their vulnerability to adversarial examples has long been known @xcite and continues to be a liability for current large-scale models @xcite . 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 @xcite @xcite and machine translation @xcite . these adversarial examples are especially concerning when applied to high stakes tasks such as content moderation and fake news detection @xcite . 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 @xcite . however, their application in nlp has been limited, in part due to the discrete nature of text @xcite @xcite @xcite . ## 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 @xcite 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.