Crafting adversarial examples on discrete inputs like text sequences is fundamentally different from generating such examples for continuous inputs like images. This paper tries to answer the question: under a black-box setting, can we create adversarial examples automatically to effectively fool deep learning classifiers on texts by making imperceptible changes? Our answer is a firm yes. Previous efforts mostly replied on using gradient evidence, and they are less effective either due to finding the nearest neighbor word (wrt meaning) automatically is difficult or relying heavily on hand-crafted linguistic rules. We, instead, use Monte Carlo tree search (MCTS) for finding the most important few words to perturb and perform homoglyph attack by replacing one character in each selected word with a symbol of identical shape.   Our novel algorithm, we call MCTSBug, is black-box and extremely effective at the same time. Our experimental results indicate that MCTSBug can fool deep learning classifiers at the success rates of 95% on seven large-scale benchmark datasets, by perturbing only a few characters.   Surprisingly, MCTSBug, without relying on gradient information at all, is more effective than the gradient-based white-box baseline. Thanks to the nature of homoglyph attack, the generated adversarial perturbations are almost imperceptible to human eyes. Recent studies have shown that adding small modifications to continuous inputs can fool state-ofthe-art deep classifiers, resulting in incorrect classifications BID33 BID15 . This phenomenon was first formulated as adding tiny and often imperceptible perturbations on image pixel values that could fool deep learning models to make wrong predictions. It raises concerns about the robustness of deep learning systems, considering that they have become core components of many safety-sensitive applications. For a given classifier F and a test sample x, recent literature defined such perturbations as vector ∆x and the resulting sample x = x + ∆x as an adversarial example BID15 .Deep learning has achieved remarkable results in the field of natural language processing (NLP), including sentiment analysis, relation extraction, and machine translation BID35 BID26 BID34 . In contrast to the large body of research on adversarial examples for image classification BID15 BID33 BID29 BID2 , less attention has been paid on generating adversarial examples on texts. A few recent studies defined adversarial perturbations on deep RNN-based text classifiers BID30 BID32 . BID30 first chose the word at a random position in a text input, then used a projected Fast Gradient Sign Method to perturb the word's embedding vector. The perturbed vector is then projected to the nearest word vector in the word embedding space, resulting in an adversarial sequence (adversarial examples in the text case; we adopt the name in this paper). This procedure may, however, replace words in an input sequence with totally irrelevant words since there is no hard guarantee that words close in the embedding space are semantically similar. BID32 used the "saliency map" of input words and complicated linguistic strategies to generate adversarial sequences that are semantically meaningful to humans. However, this strategy is difficult to perform automatically. BID12 proposed greedy scoring strategies to rank words in a text sequence and then applied simple character-level Figure 1 : An example of MCTSBug generated black-box adversarial sequence. x shows an original text sample and x shows an adversarial sequence generated from x. From x to x , only two characters are modified. This fools the deep classifier to return a wrong classification of sentiment (from positive to negative).transformations like swapping to fool deep classifiers. Its central idea, minimizing the edit distance of the perturbation makes sense. However, the perturbations are quite visible and the empirical effectiveness needs improvements. We provide more discussions in Section 5.1.Crafting adversarial examples on discrete text sequences is fundamentally different from creating them on continuous inputs like images or audio signals. Continuous input such as images can be naturally represented as points in a continuous R d space (d denotes the total number of pixels in an image). Using an L p -norm based distance metric to limit the modification ∆x on images appears natural and intuitive. However, for text inputs searching for small text modifications is difficult, because it is hard to define the distance between two discrete sequences. Three possible choices exist:• Because deep learning NLP models usually use an embedding layer to map discrete inputs to a continuous space (gradients on the embedding layer is calculable). Therefore we can measure the distance among text inputs in the continuous space defined by the word2vec embedding BID31 . However, state-of-the-art embedding models are still unsatisfactory especially in terms of providing nearest neighbors among words. FIG3 shows a few examples we chose based on the GloVe BID31 . Two words close to each other in the GloVe embedding cannot guarantee they are similar, for example, they can be antonyms. For instance, the word "loved" is the nearest neighbor of the word "hated".• We can use the huge body of linguistic knowledge to measure the distance between two text inputs. However, this strategy is hard to generalize and is difficult to extend to other discrete spaces.• Shown in Figure 1 , we can also use the edit distance between text x and text x being defined as the minimal edit operations that are required to change x to x . We focus on this distance in the paper. Intuitively we want to find imperceptible perturbations on a text input (with respect to human eyes) to evade deep learning classifiers.The second major concern we consider in this paper is the black-box setup. An adversary may have various degrees of knowledge about a deep-learning classifier it tries to fool, ranging from no information to complete information. FIG4 depicts the Perspective API BID19 from Google, which is a deep learning based text classification system that predicts whether a message is toxic or not. This service can be accessed directly from the API website that makes querying the model uncomplicated and widely accessible. The setting is a black-box scenario as the model is run on cloud servers and its structure and parameters are not available. Many state-of-the-art deep learning applications have the similar system design: the learning model is deployed on the cloud servers, and users can access the model via an app through a terminal machine (frequently a mobile device). In such cases, a user could not examine or retrieve the inner structure of the models. We believe that the black-box attack is generally more realistic than the white-box. Previous efforts about adversarial text sequences mostly replied on using gradient evidence. We instead assume attackers cannot access the structure, parameters or gradient of the target model.Considering the vast search space of possible changes (among all words/characters changes) from x to x , we design a search strategy based on Monte Carlo tree search (MCTS) for finding the most important few words to perturb. The search is conducted as a sequential decision process and aims to make small edit operations such that a human would consider the generated x (almost) the same as the original sequence. Inspired by the homoglyph attack BID11 that attacks characters with symbols of identical shapes, we replace a character in those important words found by MCTS with its homoglyph character (of identical shape). This simple strategy can effectively forces a deep classifier to a wrong decision by perturbing only a few characters in a text input.Contributions: This paper presents an effective algorithm, MCTSBug , that can generate adversarial sequences of natural language inputs to evade deep-learning classifiers. The techniques we explore here may shed light on discovering the vulnerability of using deep learning on other discrete inputs. Our novel algorithm has the following properties:• Black-box: Previous methods require knowledge of the model structure and parameters of the word embedding layer, while our method can work in a black-box setting.• Effective: on seven real-world text classification tasks, our MCTSBug can fool two stateof-the-art deep RNN models with the success rate of 95% on average (see FIG2 ).• Simple: MCTSBug uses simple character-level transformations to generate adversarial sequences, in contrast to previous works that use projected gradient or multiple linguisticdriven steps.• Almost imperceptible perturbations to human observers: MCTSBug can generate adversarial sequences that visually identical to seed sequences.Att: For the rest of the paper, we denote samples in the form of pair (x, y), where x = x 1 x 2 x 3 ...x n is an input text sequence including n tokens (each token could be either a word or a character in different models) and y set including {1, ..., K} is a label of K classes. A deep learning classifier is represented as F : X → Y, a function mapping from the input space to the label space. Due to the combinatorial nature of a large and discrete input space, searching adversarial text sequences is not a straightforward extension from image-based techniques generating adversarial examples. In this paper, we present a novel framework, MCTSBug which can generate imperceptible adversarial text sequences in a black-box manner. By combining homoglyph attack and MCTS, the proposed method can successfully fool two deep RNN-based text classifiers across seven large-scale benchmarks.The key idea we utilized in MCTSBug is that words with one character changed to its homoglyph pair are usually viewed as "unknown" by the deep-learning models. The shape change is almost invisible to humans, however, it is a huge change to a deep-learning model. More fundamentally this is caused by the fact that NLP training datasets normally only cover a very small portion of the huge space built by the combination of possible NLP letters. Then the question is: should the deep-learning classifiers model those words having identical shapes to human eyes as similar representations? We think the answer should be Yes.
Use Monte carlo Tree Search and Homoglyphs to generate indistinguishable adversarial samples on text data
{"src": "scitldr-AIC_train", "paper_id": "SJxiHnCqKQ"}