Certified Robustness to Word Substitution Attack with Differential Privacy (2021)

Abstract: The robustness and security of natural language processing (NLP) models are significantly important in real-world applications. In the context of text classification tasks, adversarial examples can be designed by substituting words with synonyms under certain semantic and syntactic constraints, such that a well-trained model will give a wrong prediction. Therefore, it is crucial to develop techniques to provide a rigorous and provable robustness guarantee against such attacks. In this paper, we propose WordDP to achieve certified robustness against word substitution at- tacks in text classification via differential privacy (DP). We establish the connection between DP and adversarial robustness for the first time in the text domain and propose a conceptual exponential mechanism-based algorithm to formally achieve the robustness. We further present a practical simulated exponential mechanism that has efficient inference with certified robustness. We not only provide a rigorous analytic derivation of the certified condition but also experimentally compare the utility of WordDP with existing defense algorithms. The results show that WordDP achieves higher accuracy and more than 30X efficiency improvement over the state-of-the-art certified robustness mechanism in typical text classification tasks.

## introduction deep neural networks (dnns) have achieved stateof-the-art performance in many natural language processing (nlp) tasks, such as text classification @xcite , sentiment analysis @xcite , and machine translation @xcite , making the robustness and security of nlp models significantly important. recent studies have shown that dnns can be easily fooled by adversarial examples, which are carefully crafted ⇤ j. lou is the corresponding author. by adding imperceptible perturbations to input examples during inference time @xcite . in the context of text classification tasks, adversarial examples can be designed by manipulating the word or characters under certain semantic and syntactic constraints @xcite @xcite . among all the attack strategies, word substitution attacks, in which attackers attempt to alter the model output by replacing input words with their synonyms, can maximally maintain the naturalness and semantic similarity of the input. therefore, in this paper, we consider such word substitution attacks and focus on defending against such attacks. figure 1 shows an example of the word substitution attack where the clean input text is changed into adversarial text by substituting input words from a synonym list. various mechanisms have been developed to defend against adversarial examples in text classification models. @xcite applied adversarial training to the text domain that involves adversarial examples in the training stage. data augmentation in the training phase is another defense approach to improve model robustness. for example, synonyms encoding method (sem) proposed by @xcite , dirichlet neighborhood ensemble (dne) proposed by @xcite , and robust encodings (roben) proposed by @xcite are different data augmentation methods on either embedding space or word space. how-ever, all the above-mentioned works are only evaluated empirically and have no theoretical analysis or guarantee on the robustness of the methods in that they may be broken by other adaptive attacks. therefore, it is important to provide rigorous and provable certified defense. there are several attempts to achieve certified robustness for word substitution attacks. @xcite and @xcite utilize @xcite to compute an upper bound on the model's loss in the forward pass and minimize this bound via backpropagation. although ibp gives a theoretical bound, it does not provide any certification condition. another limitation is that it is not applicable to character-level dnns, because ibp is limited to continuous space so that model input should be the word-level embedding. safer @xcite achieves certified robustness with a new randomized smoothing technique. however, its computation of synonym set intersection greatly reduces the computation speed in the inference stage. besides, safer only provides a theoretical certified accuracy and its empirical effectiveness on adversarial examples has not been evaluated. in this paper, we propose a novel approach worddp to certified robustness against word substitution attacks in text classification via differential privacy (dp) @xcite . figure 1 is a highlevel illustration. in the inference phase, the input go through a randomized mechanism worddp. if a clean input satisfies the certification condition of worddp, its adversarial counterpart is guaranteed to predict the same output label. dp is a privacy framework that protects the information of individual record in the database by randomized computations, such that the change of the computation output is bounded when small perturbation is applied on the database. this stable output guarantee is in parallel with the definition of robustness: ensuring that small changes in the input will not result in dramatic shift of its output. the idea of providing robustness certification via dp was originally introduced in pixeldp @xcite which is specifically designed for norm-bounded adversarial examples in the continuous domain for applications like image classification. however, it is challenging to directly apply such an idea against word substitution attack, due to the discrete nature of the text input space. therefore, in this work, we develop worddp to achieve the dp and robustness connec-tion in the discrete text space by exploring novel application of the exponential mechanism @xcite , conventionally utilized to realize dp for answering discrete queries. to achieve this, we present a conceptual certified robustness algorithm that randomly samples word-substituted sentences according to the probability distribution designated by the exponential mechanism and aggregates their inference result as the final classification for the input. a fundamental barrier limiting the conceptual algorithm from being applied in practice is that the sampling distribution of the exponential mechanism requires an exhaustive enumeration-based sub-step, which needs to repeat the model inference for every neighboring sentences with word substitutions from the input sentence. to overcome this computational difficulty, we develop a practical simulated exponential mechanism via uniform sampling and re-weighted averaging, which not only lowers the computational overhead but also ensures uncompromising level of certified robustness. our contribution can be summarized as follows: in word substitution attacks, attackers replace words in a sentence with their synonyms according to a synonym table, including pwws (ren et al., 2019), textfooler @xcite , among others @xcite . in particular, pwws is the most widely used attack algorithm to evaluate defense mechanisms @xcite @xcite . pwws uses wordnet to build synonym set and only replaces named entities (nes) with similar nes in order to flip the prediction. it incorporates word saliency to determine the replacement order and selects the synonym that can cause the greatest prediction probability change. empirical defenses to word substitution attacks. several existing empirical defenses are effective for adversarial word substitution. miyato et al. (2016) applied adversarial training to the text domain. wang et al. (2019) proposed synonyms encoding method (sem), which finds a mapping between the words and their synonyms before the input layer. jones et al. (2020) proposed robust encodings (roben) that involves an encoding function to map sentences to a smaller, discrete space. dirichlet neighborhood ensemble (dne) (zhou et al., 2020) creates virtual sentences by mixing the embedding of the original word with its synonyms' embedding via dirichlet sampling, which is randomized smoothing based data augmentation. certified robustness. certified robustness has been first studied in image domain, which certifies that a model is robust to adversarial examples when its prediction result is stable when applying small perturbations to the input @xcite @xcite . in text domain, jia et al. (2019) and huang et al. (2019) both applied interval bound propagation (ibp) for certification. the intuition is to compute an upper bound on the model's loss through the network in a standard forward pass and minimize this upper bound via backpropagation. one major limitation of ibp certification is that it is not applicable to character-level dnns, because ibp is limited to continuous space (word-level embedding). safer @xcite is a certified robust method based on randomized smoothing. the certification is based on the intersection of synonym sets between perturbed examples and clean examples. however, its computation of synonym set intersection greatly reduces the inference efficiency. besides, it lacks thorough evaluation of empirical effectiveness on adversarial examples. ## experiments we evaluate worddp on two classification datasets: internet movie database (imdb) @xcite and ag news corpus (agnews) @xcite . imdb is a binary sentiment classification dataset containing 50000 movie reviews. agnews includes 30,000 news articles categorized into four classes. the target model architecture we select is a single-layer lstm model with size of 128. we use global vectors for word representation (glove) @xcite for word embedding. the lstm model achieves 88.4% and 91.8% clean accuracy on imdb and agnews, respectively. we use pwws @xcite to generate adversarial examples on the test dataset. pwws is a state-of-the-art attack method which uses wordnet to build synonym set and incorporates word saliency to replace selected named entities (nes) with their synonyms in order to flip the prediction. the details about the datasets, model training and attack algorithm are in appendix c. ## conclusion we proposed worddp, a certified robustness method to adversarial word substitution attacks with the exponential mechanism-based algorithm. compared with previous work, worddp achieves notable accuracy improvement and 30⇥ efficiency improvement. in the future, it would be interesting to expand worddp to other kinds of textual adversarial examples, such as character-level attacks. it is also worthwhile to study other certified approaches such as random smoothing.