\section{Introduction}
Recent advancements in language understanding models have significantly pushed forth the accuracy achieved on various challenging NLP benchmarks. Despite this success, deep learning models in general are shown to misclassify when small, often humanly imperceptible, perturbations are added to original samples. These perturbed samples are referred to as \emph{adversarial samples} and such an attack is termed an \emph{adversarial attack}.
The positive side of such adversarial attacks is that apart from exposing vulnerabilities, they also aid improved understanding and interpretation of models by uncovering training biases.
Various analyses have been performed via crafted adversarial sentences: model sensitivities to small perturbations~\citep{DBLP:journals/corr/LiMJ16a}, testing neural machine translation~\citep{belinkov2018synthetic}, evaluating reading comprehension~\citep{DBLP:journals/corr/JiaL17} and classification models, to name a few.

Adversarial samples can either be generated in a \emph{whitebox} setting, where the target model's parameters like computed gradients, weights, etc., are fully accessible to the attacker or in a \emph{blackbox} setting, where the attacker can only access the inputs and outputs of the target model~\cite{papernot2016,Papernot2017}. For several commercial or proprietary pre-trained models deployed online, only a blackbox setting can be considered as a realistic setting.
\begin{table}[tbp]
        \small
		\centering
		\setlength\tabcolsep{7pt}
		\begin{tabular}{p{1.1cm}p{3.8cm}p{1.1cm}}
		 \\
        \hline
        \textbf{}  & \multicolumn{1}{c}{\bf Sentence} & \textbf{Label} \\
        \hline
        \multicolumn{3}{c}{\bf \emph{SST-2}}\\
        \hline
        Original & This is so \textcolor{blue}{bad}. & \textbf{Negative} \\
        Adversarial & This is so \textcolor{red}{wicked}. & \textbf{Positive} \\
        \hline
        &\\
        \multicolumn{3}{c}{\bf \emph{QNLI}}\\
        \hline
        Premise & Who was the game's leading rusher? & \\
        Original & Anderson was the game's leading \textcolor{blue}{rusher} with 90 yards and a touchdown, along with four \textcolor{blue}{receptions} for 10 yards. & \multirow{4}{0.7cm}{\bf \centering Entailment} \\
        Adversarial & Anderson was the game's leading \textcolor{red}{shredder} with 90 yards and a touchdown, along with four \textcolor{red}{receipts} for 10 yards. & \multirow{4}{0.7cm}{\bf \centering Not Entailment} \\
        \hline
		\end{tabular}
		\caption{Target-agnostic adversarial examples generated by our method inducing errors for all targeted models, where each original sentence was predicted correctly.}
		\label{table:sample_adv}
\end{table}

Existing blackbox attacks craft adversarial samples by repeatedly querying (in the order of thousands) a target model to pick those samples that achieve the greatest drop in accuracy~\citep{DBLP:journals/corr/abs-1907-11932,zhang-etal-2019}. This also means that the adversarial sample generation is \emph{specific} to a single pre-trained model and does not generalize well to attacks on other models.

Motivated by the aforementioned observations, we consider added restrictions on the traditional blackbox model to characterize restrictions in real-world systems. These restrictions render all previous blackbox attacks impractical or infeasible. We introduce the following limited settings:\\
\textbf{Query-limited setting}: Here, the service that deploys a trained model imposes an upper limit on the number of queries to the model due to resource constraints. Upon exceeding such a limit, additional monetary costs can be levied per query.\\
\textbf{Transferability setting}: Here an attack method, rather than constructing adversarial samples specific to a target model, should instead generate adversarial samples that can be used to attack a diverse range of pre-trained target models. In other words, the attack method should possess \emph{high attack transferability} across distinct target models.\\
Our proposed attack works well under both the added restrictions by \emph{not querying} target models during training, unlike previous methods. Rather, we construct a set of adversarial candidate samples \emph{just once} in an off-line fashion by first identifying \emph{important words} in a sentence using an enhanced neural language model On-LSTM~\citep{shen2018ordered} with MultiHead attention and replacing them with specifically chosen synonyms in such a manner that the resulting adversarial sentence maintains a very similar distribution to the input data upon which the target models are trained. Furthermore, we impose upper bounds on: (i) the number of important words that can be replaced per sentence and (ii) the number of adversarial sentences generated per original sentence. Table~\ref{table:sample_adv} shows an example of adversarial sentences produced by our attack method.\\
\noindent\textbf{Contributions}:
(i) \emph{Target-agnostic:} We propose a \emph{target model agnostic} attack on language understanding models that works under a limited query budget.
(ii) \emph{Transferability:} We employ offline training to generate a set of adversarial sentences \emph{just once}, which can then be efficiently used in \emph{repeated attacks} against several pre-trained models across a wide range of NLP tasks.
(iii) \emph{Empirical studies:} We conducted an exhaustive empirical analysis to gain deeper insights into our target-agnostic attack and we achieve substantial drops in accuracy of the target models.
For example, our methods drops the accuracy of \emph{BERT} on \emph{MNLI} by $21\%$ (from $82.7\%$ to $61.63\%$) with an extremely tight budget of $20$, which is more than $15$ times the accuracy drops by the baseline attack methods. We point that our method considers a weaker black-box setting in which we have some data available to train the ON-LSTM model. This can be the same data over which the attacked NLP model is trained, or it can have similar underlying distribution. However, the amount of data used to train ON-LSTM in our experiments is substantially low (less than 10K samples per dataset).

\section{Related Work}
Adversarial attacks have gained widespread popularity in computer vision~\citep{Goodfellow2014ExplainingAH, DBLP:journals/corr/abs-1802-08195, DBLP:journals/corr/abs-1711-01991, Xie_2017_ICCV}, as they are \emph{continuous input
domains} and therefore lend easily to attacks based on gradient searches and randomization.
However, NLP tasks present a new modality, i.e., \emph{discrete input domains} on which extending
gradient based attack methods are not straightforward.
There have been several attempts to perform gradient based attacks via GANs to create natural language adversarial samples~\citep{zhao2018generating}, however the generated adversarial samples are of an inferior quality.
Other works apply \emph{heuristic strategies} to generate adversarial samples by first identifying important features of the text (which could be characters, words or even sentences) followed by the application of greedy search strategies to perturb these features, while obeying constraints that preserve the quality of generated text. Most existing whitebox~\citep{ebrahimi-hotflip, DBLP:journals/corr/SamantaM17} as well as blackbox~\citep{iyyer-adversarial, DBLP:journals/corr/abs-1907-11932, zhao2018generating} methods have used such search heuristics to successfully generate adversarial samples by maintaining the semantic and syntactic properties of the original text. Recent works~\citep{Behjati2019UniversalAA, wallace2019universal} have focused on generating universal tokens to attack different models with good generalization properties, while~\citep{ribeiro-semantically, iyyer-adversarial} tried to create adversaries via paraphrasing. We direct the reader to~\citep{Zhang2019GeneratingTA} for a detailed survey of adversarial attack methods.

\section{Target Model Agnostic Attacks}
\begin{figure*}[tbp]
		\centering
		\begin{subfigure}{.55\textwidth}
			\includegraphics[width=70mm, height=40mm]{images/model}
			\caption{Model}

		\end{subfigure}%
		\begin{subfigure}{.3\textwidth}
			\centering
			\includegraphics[width=40mm, height=40mm]{images/entmax}
			\caption{Sentence Embedding Network}

		\end{subfigure}%
		\caption{Our On-LSTM network architecture enhanced with sparse attention via \texttt{entmax}.}
		\label{fig:Class_acc_diffx}
\end{figure*}

\subsection{Problem definition}
\label{prob_formulation}
We consider a pre-trained target model $f:\mathcal{X} \rightarrow \mathcal{Y}$ trained on a set $\mathcal{X}$ of i.i.d. observations, each associated with a class label from set $\mathcal{Y}$.
For a classification task, the class label belongs to a finite set of predefined discrete values, whereas for a regression task the class label is a \emph{continuous real-valued scalar}.

For the pre-trained model $f$ and a normal sample $\bm{x}$ (sentence)\footnote{We use the term \emph{sample} and \emph{sentence} interchangeably} with class label $y$,
the goal of an \emph{untargeted} adversarial attack is to find an adversarial sample $\bm{x_{adv}}$
that is nearly indistinguishable from $\bm{x}$, with respect to human perception, such that $f(\bm{x_{adv}}) \neq y$ (i.e., $\bm{x_{adv}}$ gets misclassified to an arbitrary class other than $y$).
In a black-box setting, attackers are only allowed access to the final outputs of $f$.
Typical black-box attacks consist of repeatedly querying (in the order of thousands) a target model $f$ with a sample $\bm{x'}$ to greedily improve the sample's quality until a satisfactory $\bm{x_{adv}}$ is crafted, akin to a \emph{denial of service (DoS) attack} on $f$. Such attacks are both cumbersome to train and completely impractical when attacking trained models deployed online.

Instead, we propose an untargeted blackbox attack, where a set of \emph{candidate adversarial samples} $\mathcal{X}_{c}$ are generated during training \emph{without querying} the target model $f$ and the cardinality of $\mathcal{X}_{c}$ does not exceed a \emph{budget} $K$.
We define $\mathcal{X}_{c}$ formally as:
\[
\mathcal{X}_{c} = \lbrace \bm{x'} \mid
\bm{x} \in \mathcal{X} , \mathcal{S}(\bm{x},\bm{x'}) \geq \epsilon, |\mathcal{X}_{c}| \leq K   \rbrace
\]
where $\mathcal{S}(\cdot,\cdot)$ is a \emph{semantic similarity} measure between sentences. In words,
$\mathcal{X}_{c}$ contains at most $K$ adversarial candidates
whose semantic similarity to sample $\bm{x}$ exceeds a user-defined threshold $\epsilon$.
We are interested in finding the \emph{largest subset of true adversarial samples} $X_{adv}$ among the set of adversarial candidates $\mathcal{X}_{c}$.
\begin{remark}
	We decouple the necessity to query a specific target model $f$ from adversarial sample generation and therefore arrive at a \emph{target-agnostic} attack method where $\mathcal{X}_{c}$ is generated once and is subsequently used to repeatedly attack a variety of models trained on $\mathcal{X}$.
	\end{remark}
\if 0
Now, we proceed to define our problem more formally.
Given a target model $f$, a normal sample $\bm{x}$ with class label $y$, and a set of candidate adversarial samples $\mathcal{X}_{c}$; we generate a set of adversarial samples $X_{adv}$ using a two-step process. First, we compute a family of subsets of $\mathcal{X}_{c}$, denoted by $\mathscr{X}$, that contain \emph{only} true adversarial samples $\bm{x}_{adv}$
by solving the following combinatorial optimization problem:
\[
\mathscr{X} = \argmin_{E \in 2^{\mathcal{X}_{c}} \setminus \emptyset} \sum_{\bm{x'} \in E}
\llbracket f(\bm{x'}) = y \rrbracket
\]
where $\llbracket \cdot \rrbracket$ represents \emph{Iverson brackets} and $2^{\mathcal{X}_{c}} \setminus \emptyset$ is the power-set of $\mathcal{X}_{c}$ without the empty set.
Next, we pick from $\mathscr{X}$ the subset with maximum cardinality as:
\[
X_{adv} = \argmax_{Y \in \mathscr{X}} |Y|
\]
\fi

\subsection{Our target-agnostic attack method}
In this section, we describe our proposed target-agnostic attack method that does not generate adversarial samples specific to any given target model.
Our approach consists of two steps:(i) identification of \emph{important words} in a sentence via a neural language attention model, and (ii) replacement of these important words to create adversarial samples conforming to the requirements of preserving the semantic as well as syntactic structure of the original sample enhanced via task-specific language modeling to get adversarial samples following the distribution of original samples.

\subsubsection{Identifying important words}
Our method uses the recent state-of-the-art language model called
\emph{On-LSTM}~\citep{shen2018ordered}, which induces a \emph{tree-structured hierarchy} on the hidden states of the LSTM network via \emph{monotonic master input} and \emph{master forget} gates. This inductive bias allows the On-LSTM model to perform tree-like composition operations, obtaining noteworthy improvements on tasks like language modeling and unsupervised constituency parsing.
We enhance the On-LSTM model with a \emph{multi-head attention} mechanism to identify important words upon which classification is performed via a \emph{classifier MLP} alongside the standard language modeling objective. Figure~\ref{fig:Class_acc_diffx} shows the architecture of our enhanced On-LSTM model.

Given a sequence of tokens $S=(x_1,\cdots,x_N)$, we generate a corresponding sequence of
word embeddings $S_{emb}=(\bm{e_1},\cdots,\bm{e_N})$.
To handle out-of-vocabulary (OOV) words as well as to perform character level attacks, we use \emph{Character-level CNNs}~\citep{DBLP:journals/corr/ZhangZL15} to construct word embeddings.
Given a token $x_i$, we perform 1-D convolutions over its character embeddings stored in the lookup
matrix $\bm{F} \in \mathds{R}^{|C| \times d_c}$, where $|C|$ is the vocabulary size of characters and
$d_c$ is the character embedding size, using 3 different kernels of sizes in $\{3, 4, 5\}$ and $100$ output
channels, which are concatenated and passed through a linear layer to obtain the final word embedding
$\bm{e_i}$. Repeating this process for every token, the new sequence $S_{emb}$ thus obtained serves as the input to the first layer of our network. We use
a $2$-layer On-LSTM network with the standard update procedures as described
in~\citep{shen2018ordered}.

Let $\bm{H}$ = $[\bm{h_1}, \cdots, \bm{h_N}]$ be the matrix consisting of the output vectors from the
final layer of the model. We pass these through a \texttt{MultiHead} attention block as described
in~\citep{DBLP:journals/corr/VaswaniSPUJGKP17}. The output is then passed through a 2-layer MLP  with a SeLU~\citep{DBLP:journals/corr/KlambauerUMH17} activation unit, which we call $C^{Att}$ to
obtain scalar attention coefficients for each output vector $h_i$ as:
\begin{align}
\bm{P}  &= \texttt{MultiHead}(H) \\ \nonumber
\bm{P'} &= C^{Att}(P)
\end{align}
where $\bm{P'} = [p_1, ....p_N]$ consists of scalar attention values corresponding to each output vector of the matrix $\bm{H}$. These attention values are then normalized via the \texttt{entmax}~\citep{peters-etal-2019-sparse} normalization function:
\begin{equation}
\label{eq:entamx_att}
\alpha = \texttt{entmax}( \bm{P'} )
\end{equation}
Intuitively, each of the output vectors $\bm{h_i}$ contains rich context information about the local n-gram chunks of the sentence. The \texttt{MultiHead} attention block allows chunk-to-chunk attention and the updated embeddings in $\bm{P}$ contain context relative information throughout the sequence, aiding the LSTM in capturing dependencies throughout the sequence. We specifically use \texttt{entmax} as our normalization function as the sparsity induced by it allows the model to learn to focus on the most important words of the sentence. Thus, serving as our \textit{important word identification unit}. The final task classification is performed by passing the combination of the vectors $\bm{h_i}$ weighted by $\alpha$ using a 3-layer MLP which we call $C^{clf}$. More formally,
\begin{equation}
y = \texttt{softmax} (C^{clf}(\bm{H}\alpha^T))
\end{equation}
In tasks with paired-sentences, we perform 3 operations: element wise addition, subtraction and multiplication, followed by concatenation of the corresponding embedding vectors $\bm{H}\alpha^T$ of the sentence pairs before passing them through the classifier $C^{clf}$.
Our final cross-entropy loss related objective function is:
\begin{equation}
J(\theta) = \sum_{i=1}^{m}t_{i}log(y_i) + L(\bm{H}, S) + \lambda \lVert \theta \rVert^2
\end{equation}
where $m$ is the number of classes, $t \in \mathbb{R}^m$ is the one-hot representation of the ground truth, $y \in \mathbb{R}^m$ is the estimated class probability, $L$ is the standard language modeling objective over the output vectors of the model, and $\lambda$ is the L2 regularization hyper-parameter. In a regression task, the cross-entropy loss is replaced by \textit{mean-squared error (MSE)} loss.

The language modeling objective function allows our attack method to learn a task-specific sentence distribution that has both \emph{low perplexity} and \emph{low divergence} of the crafted adversarial sentences with respect to the input data distribution.
After training the model, we use the attention coefficients ($\alpha$), to identify the \emph{important words} in the sentence during adversarial generation phase as described in the following section.

\begin{comment}
\noindent\textbf{Use of ON-LSTM:} The ON-LSTM model is biased towards performing tree-like composition operations. Thus the selection of important words is implicitly related to the underlying syntactic tree-structure of the sentence. As shown in ~\citep{emily_bert_geom, hewitt-manning}, transformer models like BERT encode rich tree-syntactic information in their contextual embeddings and attention vectors. Hence, using ON-LSTM model to generate adversaries induces   tree-structured variations which further aids our attack success and leads to \emph{high transferability} and allows \emph{staggered attacks} as is later shown in Section \ref{analysis_sec}.
\end{comment}

\subsubsection{Generating adversarial sentences}
\label{adv_generation_section}
Having described the procedure for identifying important words in a sentence, we now describe the procedure to generate adversarial sentences. We limit both the \emph{maximum number of adversarial samples} ($K$) as well as the \emph{maximum number of words} ($M$) that can be perturbed in the original sentence to generate an adversarial sentence. Our objective is to generate a set of, at most $K$, \emph{distinct} adversarial samples $\mathcal{X}_{c}$ for a given normal sample $\bm{x}$, which can then cause maximum misclassification in every target model.
We consider the following steps to generate $\mathcal{X}_{c}$:\\
(a) Consider a single token $x$ in a sentence and its corresponding word embedding $\bm{e}$.
Note that these word embeddings are specifically curated for synonym extraction~\citep{mrksic-etal-2016-counter}.
We then compute a set $E_x$ of the $k$-most-semantically-similar words to $x$,
based on the cosine-similarity between $\bm{e}$ and the embeddings of neighboring words.
The set $E_x$ is further reduced by pruning: (i) neighboring words  whose cosine similarity with the original token $x$'s embedding falls below a user-defined threshold $\phi$, (ii) neighbors whose part-of-speech (POS) tags do not match the POS tag of $x$, and (iii) stop-words. We denote this reduced set of words by $E'_x$. Such a set is computed per token.\\
(b) Recall that each word is associated with an \emph{attention coefficient} $\alpha$ (as described in Equation~\ref{eq:entamx_att}). In a given sentence, we pick a set $X$ of top-$M$ words according to their corresponding $\alpha$ values. Now, we must replace each word $\bm{x} \in X$ with a semantically-similar word from set $E'_x$. The total number of possible substitutions is upper bounded by $M^{|E^{'}_x|}$, which is too large and therefore we randomly sample $R$ combinations and accordingly replace the original words with their corresponding semantically-similar words to arrive at our final adversarial candidate sentences. In our experiments, $R$ is set to $600$.\\
(c) Each candidate sentence in $R$ is assigned a \emph{perplexity score} when passed through our On-LSTM model. On the basis of this score, we pick the top-$W$ candidates with the lowest perplexity scores to further reduce the size of $R$. For each of the $W$ candidates, we then compute their \emph{sentence semantic similarity} w.r.t to the original sentence using the \emph{Infersent} model~\citep{DBLP:journals/corr/ConneauKSBB17}. Finally, we retain the top-$K$ candidates ranked by decreasing order of their \emph{sentence semantic similarity} score and further prune away candidates whose score is below $\epsilon$ (as defined in Section~\ref{prob_formulation}). The successful candidates from this set are referred to as $X_{adv}$, defined in Section~\ref{prob_formulation}. In our experiments, $K$ is set to $20$, as explained in section \ref{analysis_sec}.

\begin{comment}
\begin{table*}[ht]
\tiny

\centering
\setlength\tabcolsep{3.5pt}
\begin{tabular}{lccccccccccccccc}
\\
\hline
\textbf{}   &  \multicolumn{5}{c}{\bf \emph{BERT}}  &  \multicolumn{5}{c}{\bf \emph{XLNeT}} & \multicolumn{5}{c}{\bf \emph{BiLSTM + Attn + ELMo}} \\
\cline{2-6}   \cline{7-11} \cline{12-16}
&  SST-2  & MNLI(m / mm) & QQP  & QNLI & STS-B &  SST-2  & MNLI(m / mm) & QQP  & QNLI & STS-B &  SST-2  & MNLI(m / mm) & QQP  & QNLI & STS-B   \\

\hline
\emph{Original MV} & 92.14 & 82.7 / 84.88 & 90.5 & 84.65 & 0.81 & 93.3 & 85.00 / 85.38 & 88.93 & 83.21 & 1.21 & 88.68 & 70.1 / 71.36 & 81.4 & 76.2 & 1.34 \\
&\\

\hline
\textbf{} &  \multicolumn{15}{c}{\bf \emph{Max Words Perturbed $=$ 3}} \\
\hline
\emph{AttackMV} & 59.58 & 17.8 / 17.21 & 55.0 & 66.15 & 2.06 & 59.81 & 17.16 / 18.71 & 45.69 & 64.63 & 1.87 & 53.11 & 18.3 / 19.34 & 52.7 & 56.8 & 2.09\\
\emph{Semantic Sim} & 0.84 & 0.79 / 0.77 & 0.81 & 0.86 & 0.72 & 0.85 & 0.76 / 0.75 & 0.75 & 0.87 & 0.70 & 0.82 & 0.77 / 0.78 & 0.80 & 0.85 & 0.74 \\
\emph{\# Succ. Cand.} & 18.83 & 48.46 / 51.39 & 35.59 & 26.92 & 1.00 & 18.39 & 51.29 / 53.84 & 32.24 & 30.55 & 1.00 & 23.20 & 58.96 / 62.84 & 31.65 & 13.24 & 1.00 \\
&\\

\hline
\textbf{} &  \multicolumn{15}{c}{\bf \emph{Max Words Perturbed $=$ 4}} \\
\hline
\emph{AttackMV} & 48.90 & 12.2 / 11.18 & 52.2 & 60.67 & 2.29 & 51.38 & 12.54 / 11.44 & 41.34 & 57.31 & 2.07 & 45.26 & 11.98 / 12.87 & 48.6 & 50.01 & 2.41\\
\emph{Semantic Sim} & 0.78& 0.72 / 0.70 & 0.73 & 0.81 & 0.67 & 0.80 & 0.69 / 0.68 & 0.71 & 0.79 & 0.65 & 0.77 & 0.72 / 0.73 & 0.74 & 0.79 & 0.68 \\
\emph{\# Succ. Cand.} & 22.14 & 61.57 / 65.12 & 38.69 & 30.40 & 1.00 & 24.47 & 55.67 / 56.88 & 34.79 & 32.47 & 1.00 & 18.68 & 59.87 / 62.34 & 38.85 & 17.17 & 1.00 \\
&\\

\hline
\textbf{} &  \multicolumn{15}{c}{\bf \emph{Max Words Perturbed $=$ 5}} \\
\hline
\emph{AttackMV} & 43.10 & 8.49 / 9.20 & 48.09 & 53.96 & 2.42 & 42.52 & 8.79 / 7.70 & 38.19 & 52.28 & 2.16 & 37.31 & 9.56 / 10.84 & 43.16 & 45.35 & 2.67\\
\emph{Semantic Sim} & 0.73 & 0.68 / 0.66 & 0.67 & 0.75 & 0.61 & 0.74 & 0.62 / 0.61 & 0.66 & 0.72 & 0.61 & 0.72 & 0.69 / 0.68 & 0.70 & 0.73 & 0.63 \\
\emph{\# Succ. Cand.} & 25.97 & 66.09 / 67.03 & 39.87 & 31.57 & 1.00 & 27.54 & 61.2 / 60.97 & 35.64 & 33.68 & 1.00 & 21.22 & 63.54 / 64.84 & 41.12 & 18.70 & 1.00 \\
\hline

\end{tabular}
\caption{Word adversarial attack results under different word perturbation settings. For STS-B, we only consider the adversary with maximum MSE change wrt original sentence.}
\label{table:word_results_via_max}
\end{table*}
\end{comment}

\begin{table*}[tbp]
\tiny

\centering
\setlength\tabcolsep{3.5pt}
\begin{tabular}{lrrrrrrrrrrrrrr}
\\
\hline
\textbf{}   &  \multicolumn{5}{c}{\bf \emph{BERT}}  &  \multicolumn{5}{c}{\bf \emph{XLNeT}} & \multicolumn{4}{c}{\bf \emph{BiLSTM + Attn + ELMo}} \\
\cline{2-5}   \cline{7-10} \cline{12-15}
&  SST-2  & MNLI(m / mm) & QQP  & QNLI &  &  SST-2  & MNLI(m / mm) & QQP  & QNLI &  &  SST-2  & MNLI(m / mm) & QQP  & QNLI \\

\hline
\emph{Pre-attack Accuracy} & 92.14 & 82.7 / 84.88 & 90.5 & 84.65 &  & 93.3 & 85.00 / 85.38 & 88.93 & 83.21 &  & 88.68 & 70.1 / 71.36 & 81.4 & 76.2 \\
&\\

\hline
\textbf{} &  \multicolumn{14}{c}{\bf \emph{Method: TextFooler}} \\
\hline
\emph{Avg. Accuracy Drop} & \underline{0.90} & \underline{1.21} / \underline{1.18} & 1.04 & \underline{0.83} & & \underline{0.78} & \underline{1.54} / \underline{1.44} & 1.19 & \underline{1.03} &  & \underline{1.32} & \underline{1.98} / 1.87 & 1.05 & \underline{0.88} \\
\emph{Max. Accuracy Drop} & 5.51 & 26.58 / 29.56 \textbf{**} & 23.68\textbf{**} & 6.35 &  & 5.30\textbf{**} & 26.90 / 27.40 \textbf{**} & 23.53\textbf{**} & 2.71 &  & 7.14 & 26.43 / 28.38 \textbf{**} & 23.28\textbf{*} & 7.49\textbf{**} \\
\emph{Semantic Similarity} & 0.83 & 0.81 / 0.79 & 0.78 & 0.87 & & 0.82 & 0.73 / 0.75 & 0.79 & 0.82 &  & 0.83 & 0.72 / 0.73 & 0.78 & 0.86 \\

&\\

\hline
\textbf{} &  \multicolumn{14}{c}{\bf \emph{Method: Genetic}} \\
\hline
\emph{Avg. Accuracy Drop} & 0.73 & 1.11 /1.09 & \underline{1.23} & 0.69 &  & 0.75 & 1.28 / 1.31 & \underline{1.49} & 0.88 &  & 1.27 & 1.83 / \underline{1.97} & \underline{1.31} & 0.79 \\
\emph{Max. Accuracy Drop} & 7.45\textbf{**} & 23.79 / 25.31 & 22.78 & 7.02\textbf{**} &  & 3.66 & 22.75 / 22.56 & 21.00 & 5.98\textbf{**} &  & 8.55\textbf{**} & 24.21 / 26.40 & 17.34 & 7.09 \\
\emph{Semantic Similarity} & 0.77 & 0.72 / 0.70 & 0.76 & 0.81 & & 0.81 & 0.67 / 0.69 & 0.71 & 0.79 &  & 0.76 & 0.64 / 0.62 & 0.72 & 0.80 \\

&\\
\hline
\textbf{} &  \multicolumn{14}{c}{\bf \emph{Method: Ours}} \\
\hline
\emph{Avg. Accuracy Drop} & \textbf{5.97} & \textbf{21.07} / \textbf{20.31} & \textbf{6.84} & \textbf{5.01} &  & \textbf{5.81} & \textbf{21.96} / \textbf{21.48} & \textbf{6.20} & \textbf{4.59} &  & \textbf{7.84} & \textbf{23.47} / \textbf{22.93} & \textbf{5.92} & \textbf{4.27} \\
\emph{Max. Accuracy Drop} & 23.55\textbf{*} & 56.70\textbf{*} / 56.36\textbf{*} & 29.90\textbf{*} & 13.62\textbf{*} &  & 22.86\textbf{*} & 56.40\textbf{*} / 57.26\textbf{*} & 32.73\textbf{*} & 13.40\textbf{*} &  & 22.40\textbf{*} & 42.76\textbf{*} / 42.91\textbf{*} & 23.23\textbf{**} & 12.38\textbf{*} \\
\emph{Semantic Similarity} & 0.84 & 0.79 / 0.77 & 0.81 & 0.86 &  & 0.85 & 0.76 / 0.75 & 0.75 & 0.87 &  & 0.82 & 0.77 / 0.78 & 0.80 & 0.85  \\
\hline

\end{tabular}
\caption{Word adversarial attack results by perturbing at most $M=3$ words. This table shows accuracy drops for various methods as well as the average semantic score of the adversarial sentences to the original sentences. \emph{Pre-attack Accuracy} represents the accuracy on original sentences. \emph{Avg. Accuracy Drop} represent the drop in accuracy averaged over the adversarial candidates, whereas \emph{Max. Accuracy Drop} represents the maximum drop in accuracy achieved if any adversarial candidate in the set of $K=20$ succeeds.

Higher the drops, more successful the attack. Here, \emph{m} and \emph{mm} represent the \emph{matched} and \emph{mismatched} versions of the dev set respectively. For Average Drops, the best results are marked in \textbf{bold} whereas the second best \underline{underlined}. For Maximum Drops, the best results are marked by \textbf{*}, while the second best by \textbf{**}.}
\label{table:word_results}
\end{table*}

\section{Experiments}

\subsection{Datasets and Attacked Models}
We study the effectiveness of our proposed approach on various standard datasets from the well established GLUE\footnote{\footnotesize \url{https://gluebenchmark.com/}}~\citep{wang2018glue} benchmark.
It consists of the \emph{Stanford sentiment treebank (SST-2)}~\citep{socher-recursive}
(for sentiment analysis), the \emph{multi-genre natural language inference (MLNI)} corpus~\citep{williams-etal-2018-broad} and the \emph{question answering natural language inference (QNLI)} datasets~\citep{wang2018glue} (for natural language inference) and finally
the \emph{Quora Question Pairs (QQP)} and
the \emph{semantic textual similarity benchmark (STS-B)}~\citep{cer-semeval} (for paraphrasing).
From each dataset we pick $1000$ random instances from the dev set (except for \emph{SST-2}, where dev set size is $870$), since the actual test predictions are not publicly available.
We report the results for the classification experiments on \emph{SST-2}, \emph{MNLI}, \emph{QNLI}, and \emph{QQP} here, while for \emph{STS-B}, the results are provided in appendix.\\
We choose three dominant \emph{SOTA} models to show the efficacy of our novel \textit{target-agnostic} adversarial attack, namely \emph{BERT} ~\citep{DBLP:journals/corr/abs-1810-04805}, \emph{XLNet} ~\citep{DBLP:journals/corr/abs-1906-08237}, and \emph{BiLSTM with attention mechanism} ~\citep{wang2018glue}. A brief description of each dataset, the attacked models and the results on \emph{STS-B} are provided in the appendix.

\subsection{Attack Results}
In this section, we report the performance of the attacked models on the crafted adversarial samples from various methods. We compare our method with two well known black-box adversarial attacks methods.
The first baseline: \emph{TextFooler}~\citep{DBLP:journals/corr/abs-1907-11932}, which performs
iterative greedy attacks heuristically by replacing the original word with a word that drops the target
model's accuracy by the maximum margin. The other baseline is the popular \emph{genetic attack
algorithm}~\citep{alzantot-generating}, which iteratively crafts the adversarial samples using a genetic based algorithm that fuses two adversarial sequences to create a better adversarial sample. Both these methods are run under the similar budget, word perturbation and hyperparameter settings as  our model for fair evaluation.\\
The results for word perturbation factor \emph{M=3} are provided in table \ref{table:word_results}. Hereon, we use the terms \emph{candidate set size} as well as \emph{attack budget} interchangeably, both referring to \emph{K}. \emph{Pre Attack Acc} refers to the accuracy of the models on the original sentences. \emph{Avg. Accuracy Drop} represent the drops in accuracy averaged over all the adversarial candidates, whereas \emph{Max. Accuracy  Drops} represent the maximum drop in accuracy achieved if any adversarial candidate in the set of $K=20$ succeeds. \emph{Accuracy Drops} are calculated as the difference between \emph{pre-attack} accuracy (calculated over original sentences) and \emph{post-attack} accuracy (calculated over the adversarial candidates). Hence, \emph{higher the accuracy drops, more successful the attack}. It is evident from the table that our method outperforms the baseline methods by factors of up to \textbf{15} under very limited budget settings conforming to practical attack scenarios. The semantic similarity scores of our crafted adversarial samples are generally better than those of the baselines.

We also provide a mechanism to utilize our method for \emph{character level attacks}, which makes our method all the more practical and generalized compared to methods that either employ word-specific or character-specific attacks. Results of word perturbations of $4$ and $5$, the \emph{regression} dataset \emph{STS-B} and character level attacks are provided in the appendix.

\begin{comment}
\begin{table}[tbp]
		\small
		\centering

		\begin{tabular}{lccc}
			\\
			\hline
			\textbf{Method}   &  \textbf{3 Words}  & \textbf{4 Words} &  \textbf{5 Word} \\
			\hline
			\emph{Ours} & 2.06 & 2.29 & 2.42 \\
			\emph{TextFooler} & 2.22 & 2.35 & 2.43 \\
			\emph{Genetic} & 2.17 & 2.31 & 2.38 \\
			\hline
		\end{tabular}
		\setlength\tabcolsep{3.5pt}
		\begin{tabular}{lccc}
			\\
			\hline
			\textbf{Method}   &  \textbf{3 Words}  & \textbf{4 Words} &  \textbf{5 Word} \\
			\hline
			\emph{Ours} & 17.8 / 17.21 & 12.1 / 11.18 & 8.49 / 9.20 \\
			\emph{TextFooler} & 16.20 / 18.10 & 13.4 / 13.3 & 11.5 / 11.3 \\
			\emph{Genetic} & 17.49 / 18.1 & 13.29 / 12.51 & 10.79 / 12.21 \\
            \hline
		\end{tabular}
		\caption{Comparison of our method with baselines on STS-B (top table) and MNLI (bottom table) datasets, (values in the tables represent metric scores on adversarial sentences) with maximum perturbation allowed $M$ set to 3,4 and 5 words with the attacked model as BERT.}
		\label{table:Comparison}
\end{table}
\end{comment}

\section{Analysis}
\label{analysis_sec}
\noindent\textbf{Setting the value of K:}
We vary $K$ to ascertain the tightest possible budget for our method.
Figure \ref{fig:budget_diff} shows the \emph{average accuracy drops} versus different \emph{budget values} for XLNet model on MNLI, QNLI, and SST-2 datasets.
We choose the \emph{first point of inflection} at $K=20$ on all curves as our optimal value of budget $K$ across all datasets.
\begin{figure}[ht]
		\centering
		\includegraphics[width=60mm, height=40mm, center]{images/Average_XLNET_plot_budget}
		\caption{Average accuracy drops versus the budget value for XLNet model on various datasets.}
		\label{fig:budget_diff}
\end{figure}

\noindent\textbf{Attack transferability:}
We conduct transferability experiments w.r.t to baseline methods to examine how well the adversarial samples crafted by the SOTA baselines transfer from one target model to the other. The results for \emph{QQP} and \emph{QNLI} datasets are summarized in Table~\ref{table:Transferability}, with $M$ set to $3$. In the table, \emph{higher} the value, \emph{better} the attack. For our method, we select the \emph{true}  adversarial samples per original sentence from the first model to attack the other two models. The average \% \emph{drop} in model accuracies shown in the table are  averaged over all candidates. For the baselines which follow a greedy approach, the accuracy drops are extremely low when we transfer their adversarial sentences to other models, whereas our method is much more superior in this aspect. Our method is better by factors of upto \textbf{40} (depending upon model) as compared to the baselines and can craft highly generic adversaries, while preserving (to a large extent) the \emph{semantic} and \emph{syntactic} aspects of the original sentence. Additional results for maximum drops are provided in the appendix.

\begin{table}[tbp]
		\small

		\centering

		\begin{tabular}{lrrr}
			\\
			\hline
			\textbf{QQP}   &  \textbf{BERT}  & \textbf{XLNeT} &  \textbf{BiLSTM} \\
			\hline
			\emph{TextFooler Bert} & - & \underline{10.7} & \underline{12.05} \\
			\emph{TextFooler XLNeT} & 12.62\textbf{**} & - & 8.81 \\
			\hline
			\emph{Genetic Bert} & - & 0.5 & 9.19 \\
			\emph{Genetic XLNeT} & 10.68 & - & 13.58\textbf{**} \\
            \hline
			\emph{Our Bert} & - & \textbf{21.35} & \textbf{19.74} \\
			\emph{Our XLNeT} & 17.86\textbf{*} & - & 20.16\textbf{*} \\
			\hline
		\end{tabular}

		\begin{tabular}{lrrr}
			\\
			\hline
			\textbf{QNLI}   &  \textbf{BERT}  & \textbf{XLNeT} &  \textbf{BiLSTM} \\
			\hline
			\emph{TextFooler Bert} & - & \underline{4.33} & \underline{3.68} \\
			\emph{TextFooler XLNeT} & 0.27 & - & 1.54\textbf{**} \\
			\hline
			\emph{Genetic Bert} & - & 2.33 & 1.61 \\
			\emph{Genetic XLNeT} & 1.04\textbf{**} & - & 0.64 \\
			\hline
			\emph{Our Bert} & - & \textbf{10.28} & \textbf{9.08} \\
			\emph{Our XLNeT} & 8.68\textbf{*} & - & 9.61\textbf{*} \\
			\hline
		\end{tabular}

		\caption{Transferability attacks. Leftmost column header represents the original model (for which the adversaries were crafted) with the attack methods and the following three column headers represent the model on which these sentences were \emph{transferred} and evaluated. The values in the table show the average \% \emph{drop} in model accuracies on original samples and their crafted adversarial counterparts. '-' signifies same source and target model. For BERT, best results in \textbf{bold}, second best \underline{underlined}. For XLNet, best results are marked by \textbf{*}, second best by \textbf{**}.}
		\label{table:Transferability}
\end{table}

\begin{comment}
\begin{table}[ht]
		\small

		\centering
		\setlength\tabcolsep{3.5pt}
		\begin{tabular}{lccccc}
			\\
			\hline
			{} & \textbf{SST-2} & \textbf{MNLI(m / mm)} & \textbf{QQP} & \textbf{QNLI} \\
			\hline
			$\Delta$ Our & 33.497 & 67.84 / 66.67 & 43.24 & 0.66 \\
			\# Succ. Cand. & 18.39 & 51.29 / 53.84 & 32.24 & 1 \\
			&\\
			\hline
			$\Delta$ Random & 23.19 & 53.86 / 52.64 & 30.46 & 0.33 \\
			\# Succ. Cand. & 14.21 & 50.26 / 49.87 & 27.31 & 1  \\
			\hline
        \end{tabular}
        \caption{Comparison of our method vs random attacks. $\Delta$ represents the average drop in accuracies between original and adversarial samples.}
        \label{table:maximum_ablation}
\end{table}
\end{comment}

\begin{table}[ht]
		\small

		\centering
		\setlength\tabcolsep{3.5pt}
		\begin{tabular}{lccccc}
			\\
			\hline
			{} & \textbf{SST-2} & \textbf{MNLI(m / mm)} & \textbf{QQP} & \textbf{QNLI} \\
			\hline
			Av $\Delta$ Our & \textbf{5.81} & \textbf{21.96} / \textbf{21.48} & \textbf{6.20} & \textbf{4.59} \\
			Av $\Delta$ Random & 2.15 & 12.49 / 13.47 & 3.07 & 2.81 \\
			&\\
			\hline
			Max $\Delta$ Our & \textbf{22.86} & \textbf{56.40} / \textbf{57.26} & \textbf{32.73} & \textbf{13.40} \\
			Max $\Delta$ Random & 14.19 & 43.86 / 42.64 & 20.46 & 8.31 \\

			\hline
        \end{tabular}
        \caption{Comparison of our method versus random attacks. \emph{Av $\Delta$} represents the average drop, while \emph{Max $\Delta$} represent the maximum drop  in accuracies between original and adversarial samples. Better results in bold.}
        \label{table:ablation}
\end{table}

\noindent\textbf{Ablation study:}
Since our method primarily focuses on selecting important words for crafting adversarial samples,
we perform attacks on the target models by randomly replacing words from the
original sentence, keeping the rest of the steps the same as provided in Section~\ref{adv_generation_section}.
The results for the datasets with $M=3$ on XLNeT target model are provided
in Table~\ref{table:ablation}. This table contains the average \% drop as well the maximum \% drops in accuracies between the original sentences and their adversarial counterparts caused by our method and a random attack. Once again, \textit{higher} the value achieved, \textit{better} the attack. Clearly, the proposed word importance selection criteria helps in selecting important words from the sentence and generate better adversarial samples.
\begin{table}[ht]
\scriptsize
\label{HumanEval}
\centering
\begin{tabular}{lccc}
\\
\hline
\textbf{Dataset} & \textbf{Input Type}  &  \textbf{Grammar Score}  & \textbf{Clf Consistency} \\
\hline
\multirow{2}{0.7cm}{\centering SST-2} & Original & 4.6 & \multirow{2}{0.7cm}{\centering 87.34}  \\
{} & Adversary & 4.13 &  \\
\hline
\multirow{2}{0.7cm}{\centering MNLI} & Original & 4.54 & \multirow{2}{0.7cm}{\centering 80.11} \\
{} & Adversary & 4.07 & \\
\hline
\multirow{2}{0.7cm}{\centering QQP} & Original & 4.3 & \multirow{2}{0.7cm}{\centering 86.08} \\
{} & Adversary & 4.02 & \\
            \hline
\multirow{2}{0.7cm}{\centering QNLI} & Original & 4.61 & \multirow{2}{0.7cm}{\centering 82.47} \\
{} & Adversary & 4.08 & \\
            \hline
\end{tabular}
\caption{Overall Grammatical score and Human Classification consistency for the datasets.}.
\label{table:HumanEval}
\end{table}

\noindent\textbf{Human evaluation:}
Apart from the automatic evaluation, we also analyze the adversarial samples by asking language proficient human judges to score them against the original sentences. We ask three human judges to rate the sentences based on: overall sentence structure (semantic and syntactic well-formedness) as well as consistency of the adversarial sentences against the actual sentence labels. We consider $200$ samples from each dataset for the scenario with $M=3$ perturbed words. For each original sentence, we randomly select one of the generated candidates, and randomly shuffle them with the $200$ original sentences to obtain $400$ sentences to be analyzed. The overall grammatical structure is measured on a scale of $1$--$5$, whereas for the label consistency we check the percentage of adversarial sentences that were assigned the same label as the original sentence label by human judges. The analysis is summarized in Table~\ref{table:HumanEval}.

\noindent\textbf{Evaluating \emph{perplexity score} versus \emph{confidence score drops} trade-off:}
Clearly, an adversarial sentence with a very high-perplexity score has a better chance of fooling the model under attack because it is completely different from the original sentence. Ideally, we want adversarial sentences that have a low-perplexity score but can achieve high drops in accuracy.
To assess the quality of the generated adversaries and their capabilities of fooling the target models, we plot the \emph{sentence perplexity values} versus the \emph{drop in the correct class probability between the original and adversarial sentences}. Figure \ref{fig:ppl_scores} shows the plots on various datasets for $50$ randomly chosen sentences on \emph{BERT}. Observe that the majority of our adversarial sentences lie in the region of ``low-perplexity, high-confidence drops" (blue region), as opposed to baseline attacks whose adversarial sentences are spread over a very wide range of perplexity scores and are mostly confined to regions of low-to-medium confidence drops.
\if 0
It's evident that our curated adversaries are much better in quality and can reduce the model confidence by huge margins compared to the baselines. Many of our adversaries can completely reduce the model confidence of the correct class to \textbf{zero}, while the baselines almost never do.
\fi
\begin{figure*}[tbp]
		\centering
        \begin{subfigure}{.5\textwidth}
			\includegraphics[width=80mm, height=65mm]{images/ppl_scores/sst-2_mlp}
			\caption{SST-2}
			\label{fig:sub1_bert_ppl}
		\end{subfigure}%
		\begin{subfigure}{.5\textwidth}

			\includegraphics[width=80mm, height=65mm]{images/ppl_scores/mnli_random_forest}
			\caption{MNLI}
			\label{fig:sub2_xlnet_ppl}
		\end{subfigure}%

		\caption{Perplexity values versus confidence differences (probability difference of the correct class between the original and adversarial sentences). }
		\label{fig:ppl_scores}
\end{figure*}

\noindent\textbf{Attack time:} We analyze the time taken by different methods to attack the target models. It is evident from figure \ref{fig:runtime} that our method is faster by factors of \textbf{9-12} (depending on the dataset). We attribute this to \emph{independence} of the generated candidate adversaries from one another, thus allowing our method to perfrom attacks using mini-batches of data as opposed to the baselines, which iteratively improve the query and thus are forced to attack in a sequential manner. Similar attack run-time plots for BERT and XLNet are provided in our appendix.
\begin{figure}[ht]
		\centering
			\includegraphics[width=65mm, height=50mm]{images/BiLSTM_time_bud_20}
		\caption{Runtime for the attack methods on BiLSTM target model.}
		\label{fig:runtime}
\end{figure}

\noindent\textbf{High transferability and staggered attacks:} We observed that a substantial fraction of our true adversarial examples were “common” to all models. We can thus roll out our queries per model in a “staggered approach”, i.e., querying a model, gathering its true adversarial set S and only using examples from S to target the next model, hence "shrinking" S with every model we attack. This approach can drastically reduce the attack time if we have to attack multiple models in a sequential manner (i.e, when it's not possible to attack more than one model simultaneously). Results provided in table \ref{table:Staggered_main} verify our claims. The average \textbf{\%} values shown in the table represent the  percentage of successful adversarial samples out of the total samples the corresponding model was attacked with. Further experiments have been provided in the appendix.
\begin{table}[ht]

		\centering
		\begin{tabular}{lccc}
			\\
			\hline
			\textbf{Dataset}   &  \textbf{BERT}  & \textbf{XLNet} &  \textbf{BiLSTM} \\
			\hline
			\emph{MNLI} & 34\textbf{\%} & 39\textbf{\%} & 12\textbf{\%} \\
			\emph{SST-2} & 14\textbf{\%} & 33\textbf{\%} & 17\textbf{\%} \\
			\emph{QQP} & 25\textbf{\%} & 36\textbf{\%} & 9\textbf{\%} \\
            \emph{QNLI} & 17\textbf{\%} & 41\textbf{\%} & 19\textbf{\%} \\
			\hline
		\end{tabular}
		\caption{Staggered attacks. Values in the table represent \emph{average \%} of successful adversarial samples.}
		\label{table:Staggered_main}
\end{table}

\noindent\textbf{Comparison to previous paraphrase based attacks:} Prior paraphrase based attack methods such as ~\citep{iyyer-adversarial, ribeiro-semantically} propose template and rule based methods to curate adversaries. Verifying the correctness of these templates and rules can be difficult and may require manual investigations which is extremely time consuming. Training models to generate templates as done in ~\citep{iyyer-adversarial} requires training large scale models with large training sets, as opposed to our case. These templates and rules also have restrictions on their applicability as they can't be arbitrarily applied to any sentence. In contrast, our method is completely automated with very high semantics preservation properties, has high transferability, can attack multiple models via staggered approach as well as it has very low attack time attributed to batching of the candidates.
We also performed a quantitative and qualitative analysis of \textbf{classwise} accuracy drops for the datasets as well as show various examples of our successful adversaries, both are provided in appendix.\\

\noindent\textbf{Difference from Surrogacy based methods:} As mentioned earlier, our method follows a weaker black-box setting, where we assume the presence of a small amount of training data for ON-LSTM model. However, this is significantly different from the surrogacy based methods, where the surrogate model is explicitly trained to replicate the attacked model which requires a substantial amount of queries to the attacked model, thus incurring a huge budget.

\section{Conclusion}
We explore a novel target model agnostic adversarial attack under very limited query budgets. Unable to exploit biases of target models towards datasets, like other greedy methods do, this method carries multiple other advantages. The actual attack process is fast and the generated pool of adversarial sentences show a high degree of transferability across different types of models which brings the added benefit of attacking multiple target models simultaneously by the same candidate set. Our method performs well in comparison to the greedy SOTA adversarial attacks with a tighter budget on the number of queries, which makes our attack much more practical.

\section{Introduction}
Recent advancements in language understanding models have significantly pushed forth the accuracy achieved on various challenging NLP benchmarks. Despite this success, deep learning models in general are shown to misclassify when small, often humanly imperceptible, perturbations are added to original samples. These perturbed samples are referred to as \emph{adversarial samples} and such an attack is termed an \emph{adversarial attack}.
The positive side of such adversarial attacks is that apart from exposing vulnerabilities, they also aid improved understanding and interpretation of models by uncovering training biases.
Various analyses have been performed via crafted adversarial sentences: model sensitivities to small perturbations~\citep{DBLP:journals/corr/LiMJ16a}, testing neural machine translation~\citep{belinkov2018synthetic}, evaluating reading comprehension~\citep{DBLP:journals/corr/JiaL17} and classification models, to name a few.

Adversarial samples can either be generated in a \emph{whitebox} setting, where the target model's parameters like computed gradients, weights, etc., are fully accessible to the attacker or in a \emph{blackbox} setting, where the attacker can only access the inputs and outputs of the target model~\cite{papernot2016,Papernot2017}. For several commercial or proprietary pre-trained models deployed online, only a blackbox setting can be considered as a realistic setting.
\begin{table}[tbp]
        \small
		\centering
		\setlength\tabcolsep{7pt}
		\begin{tabular}{p{1.1cm}p{3.8cm}p{1.1cm}}
		 \\
        \hline
        \textbf{}  & \multicolumn{1}{c}{\bf Sentence} & \textbf{Label} \\
        \hline
        \multicolumn{3}{c}{\bf \emph{SST-2}}\\
        \hline
        Original & This is so \textcolor{blue}{bad}. & \textbf{Negative} \\
        Adversarial & This is so \textcolor{red}{wicked}. & \textbf{Positive} \\
        \hline
        &\\
        \multicolumn{3}{c}{\bf \emph{QNLI}}\\
        \hline
        Premise & Who was the game's leading rusher? & \\
        Original & Anderson was the game's leading \textcolor{blue}{rusher} with 90 yards and a touchdown, along with four \textcolor{blue}{receptions} for 10 yards. & \multirow{4}{0.7cm}{\bf \centering Entailment} \\
        Adversarial & Anderson was the game's leading \textcolor{red}{shredder} with 90 yards and a touchdown, along with four \textcolor{red}{receipts} for 10 yards. & \multirow{4}{0.7cm}{\bf \centering Not Entailment} \\
        \hline
		\end{tabular}
		\caption{Target-agnostic adversarial examples generated by our method inducing errors for all targeted models, where each original sentence was predicted correctly.}
		\label{table:sample_adv}
\end{table}

Existing blackbox attacks craft adversarial samples by repeatedly querying (in the order of thousands) a target model to pick those samples that achieve the greatest drop in accuracy~\citep{DBLP:journals/corr/abs-1907-11932,zhang-etal-2019}. This also means that the adversarial sample generation is \emph{specific} to a single pre-trained model and does not generalize well to attacks on other models.

Motivated by the aforementioned observations, we consider added restrictions on the traditional blackbox model to characterize restrictions in real-world systems. These restrictions render all previous blackbox attacks impractical or infeasible. We introduce the following limited settings:\\
\textbf{Query-limited setting}: Here, the service that deploys a trained model imposes an upper limit on the number of queries to the model due to resource constraints. Upon exceeding such a limit, additional monetary costs can be levied per query.\\
\textbf{Transferability setting}: Here an attack method, rather than constructing adversarial samples specific to a target model, should instead generate adversarial samples that can be used to attack a diverse range of pre-trained target models. In other words, the attack method should possess \emph{high attack transferability} across distinct target models.\\
Our proposed attack works well under both the added restrictions by \emph{not querying} target models during training, unlike previous methods. Rather, we construct a set of adversarial candidate samples \emph{just once} in an off-line fashion by first identifying \emph{important words} in a sentence using an enhanced neural language model On-LSTM~\citep{shen2018ordered} with MultiHead attention and replacing them with specifically chosen synonyms in such a manner that the resulting adversarial sentence maintains a very similar distribution to the input data upon which the target models are trained. Furthermore, we impose upper bounds on: (i) the number of important words that can be replaced per sentence and (ii) the number of adversarial sentences generated per original sentence. Table~\ref{table:sample_adv} shows an example of adversarial sentences produced by our attack method.\\
\noindent\textbf{Contributions}:
(i) \emph{Target-agnostic:} We propose a \emph{target model agnostic} attack on language understanding models that works under a limited query budget.
(ii) \emph{Transferability:} We employ offline training to generate a set of adversarial sentences \emph{just once}, which can then be efficiently used in \emph{repeated attacks} against several pre-trained models across a wide range of NLP tasks.
(iii) \emph{Empirical studies:} We conducted an exhaustive empirical analysis to gain deeper insights into our target-agnostic attack and we achieve substantial drops in accuracy of the target models.
For example, our methods drops the accuracy of \emph{BERT} on \emph{MNLI} by $21\%$ (from $82.7\%$ to $61.63\%$) with an extremely tight budget of $20$, which is more than $15$ times the accuracy drops by the baseline attack methods. We point that our method considers a weaker black-box setting in which we have some data available to train the ON-LSTM model. This can be the same data over which the attacked NLP model is trained, or it can have similar underlying distribution. However, the amount of data used to train ON-LSTM in our experiments is substantially low (less than 10K samples per dataset).

\section{Related Work}
Adversarial attacks have gained widespread popularity in computer vision~\citep{Goodfellow2014ExplainingAH, DBLP:journals/corr/abs-1802-08195, DBLP:journals/corr/abs-1711-01991, Xie_2017_ICCV}, as they are \emph{continuous input
domains} and therefore lend easily to attacks based on gradient searches and randomization.
However, NLP tasks present a new modality, i.e., \emph{discrete input domains} on which extending
gradient based attack methods are not straightforward.
There have been several attempts to perform gradient based attacks via GANs to create natural language adversarial samples~\citep{zhao2018generating}, however the generated adversarial samples are of an inferior quality.
Other works apply \emph{heuristic strategies} to generate adversarial samples by first identifying important features of the text (which could be characters, words or even sentences) followed by the application of greedy search strategies to perturb these features, while obeying constraints that preserve the quality of generated text. Most existing whitebox~\citep{ebrahimi-hotflip, DBLP:journals/corr/SamantaM17} as well as blackbox~\citep{iyyer-adversarial, DBLP:journals/corr/abs-1907-11932, zhao2018generating} methods have used such search heuristics to successfully generate adversarial samples by maintaining the semantic and syntactic properties of the original text. Recent works~\citep{Behjati2019UniversalAA, wallace2019universal} have focused on generating universal tokens to attack different models with good generalization properties, while~\citep{ribeiro-semantically, iyyer-adversarial} tried to create adversaries via paraphrasing. We direct the reader to~\citep{Zhang2019GeneratingTA} for a detailed survey of adversarial attack methods.

\section{Target Model Agnostic Attacks}
\begin{figure*}[tbp]
		\centering
		\begin{subfigure}{.55\textwidth}
			\includegraphics[width=70mm, height=40mm]{images/model}
			\caption{Model}

		\end{subfigure}%
		\begin{subfigure}{.3\textwidth}
			\centering
			\includegraphics[width=40mm, height=40mm]{images/entmax}
			\caption{Sentence Embedding Network}

		\end{subfigure}%
		\caption{Our On-LSTM network architecture enhanced with sparse attention via \texttt{entmax}.}
		\label{fig:Class_acc_diffx}
\end{figure*}

\subsection{Problem definition}
\label{prob_formulation}
We consider a pre-trained target model $f:\mathcal{X} \rightarrow \mathcal{Y}$ trained on a set $\mathcal{X}$ of i.i.d. observations, each associated with a class label from set $\mathcal{Y}$.
For a classification task, the class label belongs to a finite set of predefined discrete values, whereas for a regression task the class label is a \emph{continuous real-valued scalar}.

For the pre-trained model $f$ and a normal sample $\bm{x}$ (sentence)\footnote{We use the term \emph{sample} and \emph{sentence} interchangeably} with class label $y$,
the goal of an \emph{untargeted} adversarial attack is to find an adversarial sample $\bm{x_{adv}}$
that is nearly indistinguishable from $\bm{x}$, with respect to human perception, such that $f(\bm{x_{adv}}) \neq y$ (i.e., $\bm{x_{adv}}$ gets misclassified to an arbitrary class other than $y$).
In a black-box setting, attackers are only allowed access to the final outputs of $f$.
Typical black-box attacks consist of repeatedly querying (in the order of thousands) a target model $f$ with a sample $\bm{x'}$ to greedily improve the sample's quality until a satisfactory $\bm{x_{adv}}$ is crafted, akin to a \emph{denial of service (DoS) attack} on $f$. Such attacks are both cumbersome to train and completely impractical when attacking trained models deployed online.

Instead, we propose an untargeted blackbox attack, where a set of \emph{candidate adversarial samples} $\mathcal{X}_{c}$ are generated during training \emph{without querying} the target model $f$ and the cardinality of $\mathcal{X}_{c}$ does not exceed a \emph{budget} $K$.
We define $\mathcal{X}_{c}$ formally as:
\[
\mathcal{X}_{c} = \lbrace \bm{x'} \mid
\bm{x} \in \mathcal{X} , \mathcal{S}(\bm{x},\bm{x'}) \geq \epsilon, |\mathcal{X}_{c}| \leq K   \rbrace
\]
where $\mathcal{S}(\cdot,\cdot)$ is a \emph{semantic similarity} measure between sentences. In words,
$\mathcal{X}_{c}$ contains at most $K$ adversarial candidates
whose semantic similarity to sample $\bm{x}$ exceeds a user-defined threshold $\epsilon$.
We are interested in finding the \emph{largest subset of true adversarial samples} $X_{adv}$ among the set of adversarial candidates $\mathcal{X}_{c}$.
\begin{remark}
	We decouple the necessity to query a specific target model $f$ from adversarial sample generation and therefore arrive at a \emph{target-agnostic} attack method where $\mathcal{X}_{c}$ is generated once and is subsequently used to repeatedly attack a variety of models trained on $\mathcal{X}$.
	\end{remark}
\if 0
Now, we proceed to define our problem more formally.
Given a target model $f$, a normal sample $\bm{x}$ with class label $y$, and a set of candidate adversarial samples $\mathcal{X}_{c}$; we generate a set of adversarial samples $X_{adv}$ using a two-step process. First, we compute a family of subsets of $\mathcal{X}_{c}$, denoted by $\mathscr{X}$, that contain \emph{only} true adversarial samples $\bm{x}_{adv}$
by solving the following combinatorial optimization problem:
\[
\mathscr{X} = \argmin_{E \in 2^{\mathcal{X}_{c}} \setminus \emptyset} \sum_{\bm{x'} \in E}
\llbracket f(\bm{x'}) = y \rrbracket
\]
where $\llbracket \cdot \rrbracket$ represents \emph{Iverson brackets} and $2^{\mathcal{X}_{c}} \setminus \emptyset$ is the power-set of $\mathcal{X}_{c}$ without the empty set.
Next, we pick from $\mathscr{X}$ the subset with maximum cardinality as:
\[
X_{adv} = \argmax_{Y \in \mathscr{X}} |Y|
\]
\fi

\subsection{Our target-agnostic attack method}
In this section, we describe our proposed target-agnostic attack method that does not generate adversarial samples specific to any given target model.
Our approach consists of two steps:(i) identification of \emph{important words} in a sentence via a neural language attention model, and (ii) replacement of these important words to create adversarial samples conforming to the requirements of preserving the semantic as well as syntactic structure of the original sample enhanced via task-specific language modeling to get adversarial samples following the distribution of original samples.

\subsubsection{Identifying important words}
Our method uses the recent state-of-the-art language model called
\emph{On-LSTM}~\citep{shen2018ordered}, which induces a \emph{tree-structured hierarchy} on the hidden states of the LSTM network via \emph{monotonic master input} and \emph{master forget} gates. This inductive bias allows the On-LSTM model to perform tree-like composition operations, obtaining noteworthy improvements on tasks like language modeling and unsupervised constituency parsing.
We enhance the On-LSTM model with a \emph{multi-head attention} mechanism to identify important words upon which classification is performed via a \emph{classifier MLP} alongside the standard language modeling objective. Figure~\ref{fig:Class_acc_diffx} shows the architecture of our enhanced On-LSTM model.

Given a sequence of tokens $S=(x_1,\cdots,x_N)$, we generate a corresponding sequence of
word embeddings $S_{emb}=(\bm{e_1},\cdots,\bm{e_N})$.
To handle out-of-vocabulary (OOV) words as well as to perform character level attacks, we use \emph{Character-level CNNs}~\citep{DBLP:journals/corr/ZhangZL15} to construct word embeddings.
Given a token $x_i$, we perform 1-D convolutions over its character embeddings stored in the lookup
matrix $\bm{F} \in \mathds{R}^{|C| \times d_c}$, where $|C|$ is the vocabulary size of characters and
$d_c$ is the character embedding size, using 3 different kernels of sizes in $\{3, 4, 5\}$ and $100$ output
channels, which are concatenated and passed through a linear layer to obtain the final word embedding
$\bm{e_i}$. Repeating this process for every token, the new sequence $S_{emb}$ thus obtained serves as the input to the first layer of our network. We use
a $2$-layer On-LSTM network with the standard update procedures as described
in~\citep{shen2018ordered}.

Let $\bm{H}$ = $[\bm{h_1}, \cdots, \bm{h_N}]$ be the matrix consisting of the output vectors from the
final layer of the model. We pass these through a \texttt{MultiHead} attention block as described
in~\citep{DBLP:journals/corr/VaswaniSPUJGKP17}. The output is then passed through a 2-layer MLP  with a SeLU~\citep{DBLP:journals/corr/KlambauerUMH17} activation unit, which we call $C^{Att}$ to
obtain scalar attention coefficients for each output vector $h_i$ as:
\begin{align}
\bm{P}  &= \texttt{MultiHead}(H) \\ \nonumber
\bm{P'} &= C^{Att}(P)
\end{align}
where $\bm{P'} = [p_1, ....p_N]$ consists of scalar attention values corresponding to each output vector of the matrix $\bm{H}$. These attention values are then normalized via the \texttt{entmax}~\citep{peters-etal-2019-sparse} normalization function:
\begin{equation}
\label{eq:entamx_att}
\alpha = \texttt{entmax}( \bm{P'} )
\end{equation}
Intuitively, each of the output vectors $\bm{h_i}$ contains rich context information about the local n-gram chunks of the sentence. The \texttt{MultiHead} attention block allows chunk-to-chunk attention and the updated embeddings in $\bm{P}$ contain context relative information throughout the sequence, aiding the LSTM in capturing dependencies throughout the sequence. We specifically use \texttt{entmax} as our normalization function as the sparsity induced by it allows the model to learn to focus on the most important words of the sentence. Thus, serving as our \textit{important word identification unit}. The final task classification is performed by passing the combination of the vectors $\bm{h_i}$ weighted by $\alpha$ using a 3-layer MLP which we call $C^{clf}$. More formally,
\begin{equation}
y = \texttt{softmax} (C^{clf}(\bm{H}\alpha^T))
\end{equation}
In tasks with paired-sentences, we perform 3 operations: element wise addition, subtraction and multiplication, followed by concatenation of the corresponding embedding vectors $\bm{H}\alpha^T$ of the sentence pairs before passing them through the classifier $C^{clf}$.
Our final cross-entropy loss related objective function is:
\begin{equation}
J(\theta) = \sum_{i=1}^{m}t_{i}log(y_i) + L(\bm{H}, S) + \lambda \lVert \theta \rVert^2
\end{equation}
where $m$ is the number of classes, $t \in \mathbb{R}^m$ is the one-hot representation of the ground truth, $y \in \mathbb{R}^m$ is the estimated class probability, $L$ is the standard language modeling objective over the output vectors of the model, and $\lambda$ is the L2 regularization hyper-parameter. In a regression task, the cross-entropy loss is replaced by \textit{mean-squared error (MSE)} loss.

The language modeling objective function allows our attack method to learn a task-specific sentence distribution that has both \emph{low perplexity} and \emph{low divergence} of the crafted adversarial sentences with respect to the input data distribution.
After training the model, we use the attention coefficients ($\alpha$), to identify the \emph{important words} in the sentence during adversarial generation phase as described in the following section.

\begin{comment}
\noindent\textbf{Use of ON-LSTM:} The ON-LSTM model is biased towards performing tree-like composition operations. Thus the selection of important words is implicitly related to the underlying syntactic tree-structure of the sentence. As shown in ~\citep{emily_bert_geom, hewitt-manning}, transformer models like BERT encode rich tree-syntactic information in their contextual embeddings and attention vectors. Hence, using ON-LSTM model to generate adversaries induces   tree-structured variations which further aids our attack success and leads to \emph{high transferability} and allows \emph{staggered attacks} as is later shown in Section \ref{analysis_sec}.
\end{comment}

\subsubsection{Generating adversarial sentences}
\label{adv_generation_section}
Having described the procedure for identifying important words in a sentence, we now describe the procedure to generate adversarial sentences. We limit both the \emph{maximum number of adversarial samples} ($K$) as well as the \emph{maximum number of words} ($M$) that can be perturbed in the original sentence to generate an adversarial sentence. Our objective is to generate a set of, at most $K$, \emph{distinct} adversarial samples $\mathcal{X}_{c}$ for a given normal sample $\bm{x}$, which can then cause maximum misclassification in every target model.
We consider the following steps to generate $\mathcal{X}_{c}$:\\
(a) Consider a single token $x$ in a sentence and its corresponding word embedding $\bm{e}$.
Note that these word embeddings are specifically curated for synonym extraction~\citep{mrksic-etal-2016-counter}.
We then compute a set $E_x$ of the $k$-most-semantically-similar words to $x$,
based on the cosine-similarity between $\bm{e}$ and the embeddings of neighboring words.
The set $E_x$ is further reduced by pruning: (i) neighboring words  whose cosine similarity with the original token $x$'s embedding falls below a user-defined threshold $\phi$, (ii) neighbors whose part-of-speech (POS) tags do not match the POS tag of $x$, and (iii) stop-words. We denote this reduced set of words by $E'_x$. Such a set is computed per token.\\
(b) Recall that each word is associated with an \emph{attention coefficient} $\alpha$ (as described in Equation~\ref{eq:entamx_att}). In a given sentence, we pick a set $X$ of top-$M$ words according to their corresponding $\alpha$ values. Now, we must replace each word $\bm{x} \in X$ with a semantically-similar word from set $E'_x$. The total number of possible substitutions is upper bounded by $M^{|E^{'}_x|}$, which is too large and therefore we randomly sample $R$ combinations and accordingly replace the original words with their corresponding semantically-similar words to arrive at our final adversarial candidate sentences. In our experiments, $R$ is set to $600$.\\
(c) Each candidate sentence in $R$ is assigned a \emph{perplexity score} when passed through our On-LSTM model. On the basis of this score, we pick the top-$W$ candidates with the lowest perplexity scores to further reduce the size of $R$. For each of the $W$ candidates, we then compute their \emph{sentence semantic similarity} w.r.t to the original sentence using the \emph{Infersent} model~\citep{DBLP:journals/corr/ConneauKSBB17}. Finally, we retain the top-$K$ candidates ranked by decreasing order of their \emph{sentence semantic similarity} score and further prune away candidates whose score is below $\epsilon$ (as defined in Section~\ref{prob_formulation}). The successful candidates from this set are referred to as $X_{adv}$, defined in Section~\ref{prob_formulation}. In our experiments, $K$ is set to $20$, as explained in section \ref{analysis_sec}.

\begin{comment}
\begin{table*}[ht]
\tiny

\centering
\setlength\tabcolsep{3.5pt}
\begin{tabular}{lccccccccccccccc}
\\
\hline
\textbf{}   &  \multicolumn{5}{c}{\bf \emph{BERT}}  &  \multicolumn{5}{c}{\bf \emph{XLNeT}} & \multicolumn{5}{c}{\bf \emph{BiLSTM + Attn + ELMo}} \\
\cline{2-6}   \cline{7-11} \cline{12-16}
&  SST-2  & MNLI(m / mm) & QQP  & QNLI & STS-B &  SST-2  & MNLI(m / mm) & QQP  & QNLI & STS-B &  SST-2  & MNLI(m / mm) & QQP  & QNLI & STS-B   \\

\hline
\emph{Original MV} & 92.14 & 82.7 / 84.88 & 90.5 & 84.65 & 0.81 & 93.3 & 85.00 / 85.38 & 88.93 & 83.21 & 1.21 & 88.68 & 70.1 / 71.36 & 81.4 & 76.2 & 1.34 \\
&\\

\hline
\textbf{} &  \multicolumn{15}{c}{\bf \emph{Max Words Perturbed $=$ 3}} \\
\hline
\emph{AttackMV} & 59.58 & 17.8 / 17.21 & 55.0 & 66.15 & 2.06 & 59.81 & 17.16 / 18.71 & 45.69 & 64.63 & 1.87 & 53.11 & 18.3 / 19.34 & 52.7 & 56.8 & 2.09\\
\emph{Semantic Sim} & 0.84 & 0.79 / 0.77 & 0.81 & 0.86 & 0.72 & 0.85 & 0.76 / 0.75 & 0.75 & 0.87 & 0.70 & 0.82 & 0.77 / 0.78 & 0.80 & 0.85 & 0.74 \\
\emph{\# Succ. Cand.} & 18.83 & 48.46 / 51.39 & 35.59 & 26.92 & 1.00 & 18.39 & 51.29 / 53.84 & 32.24 & 30.55 & 1.00 & 23.20 & 58.96 / 62.84 & 31.65 & 13.24 & 1.00 \\
&\\

\hline
\textbf{} &  \multicolumn{15}{c}{\bf \emph{Max Words Perturbed $=$ 4}} \\
\hline
\emph{AttackMV} & 48.90 & 12.2 / 11.18 & 52.2 & 60.67 & 2.29 & 51.38 & 12.54 / 11.44 & 41.34 & 57.31 & 2.07 & 45.26 & 11.98 / 12.87 & 48.6 & 50.01 & 2.41\\
\emph{Semantic Sim} & 0.78& 0.72 / 0.70 & 0.73 & 0.81 & 0.67 & 0.80 & 0.69 / 0.68 & 0.71 & 0.79 & 0.65 & 0.77 & 0.72 / 0.73 & 0.74 & 0.79 & 0.68 \\
\emph{\# Succ. Cand.} & 22.14 & 61.57 / 65.12 & 38.69 & 30.40 & 1.00 & 24.47 & 55.67 / 56.88 & 34.79 & 32.47 & 1.00 & 18.68 & 59.87 / 62.34 & 38.85 & 17.17 & 1.00 \\
&\\

\hline
\textbf{} &  \multicolumn{15}{c}{\bf \emph{Max Words Perturbed $=$ 5}} \\
\hline
\emph{AttackMV} & 43.10 & 8.49 / 9.20 & 48.09 & 53.96 & 2.42 & 42.52 & 8.79 / 7.70 & 38.19 & 52.28 & 2.16 & 37.31 & 9.56 / 10.84 & 43.16 & 45.35 & 2.67\\
\emph{Semantic Sim} & 0.73 & 0.68 / 0.66 & 0.67 & 0.75 & 0.61 & 0.74 & 0.62 / 0.61 & 0.66 & 0.72 & 0.61 & 0.72 & 0.69 / 0.68 & 0.70 & 0.73 & 0.63 \\
\emph{\# Succ. Cand.} & 25.97 & 66.09 / 67.03 & 39.87 & 31.57 & 1.00 & 27.54 & 61.2 / 60.97 & 35.64 & 33.68 & 1.00 & 21.22 & 63.54 / 64.84 & 41.12 & 18.70 & 1.00 \\
\hline

\end{tabular}
\caption{Word adversarial attack results under different word perturbation settings. For STS-B, we only consider the adversary with maximum MSE change wrt original sentence.}
\label{table:word_results_via_max}
\end{table*}
\end{comment}

\begin{table*}[tbp]
\tiny

\centering
\setlength\tabcolsep{3.5pt}
\begin{tabular}{lrrrrrrrrrrrrrr}
\\
\hline
\textbf{}   &  \multicolumn{5}{c}{\bf \emph{BERT}}  &  \multicolumn{5}{c}{\bf \emph{XLNeT}} & \multicolumn{4}{c}{\bf \emph{BiLSTM + Attn + ELMo}} \\
\cline{2-5}   \cline{7-10} \cline{12-15}
&  SST-2  & MNLI(m / mm) & QQP  & QNLI &  &  SST-2  & MNLI(m / mm) & QQP  & QNLI &  &  SST-2  & MNLI(m / mm) & QQP  & QNLI \\

\hline
\emph{Pre-attack Accuracy} & 92.14 & 82.7 / 84.88 & 90.5 & 84.65 &  & 93.3 & 85.00 / 85.38 & 88.93 & 83.21 &  & 88.68 & 70.1 / 71.36 & 81.4 & 76.2 \\
&\\

\hline
\textbf{} &  \multicolumn{14}{c}{\bf \emph{Method: TextFooler}} \\
\hline
\emph{Avg. Accuracy Drop} & \underline{0.90} & \underline{1.21} / \underline{1.18} & 1.04 & \underline{0.83} & & \underline{0.78} & \underline{1.54} / \underline{1.44} & 1.19 & \underline{1.03} &  & \underline{1.32} & \underline{1.98} / 1.87 & 1.05 & \underline{0.88} \\
\emph{Max. Accuracy Drop} & 5.51 & 26.58 / 29.56 \textbf{**} & 23.68\textbf{**} & 6.35 &  & 5.30\textbf{**} & 26.90 / 27.40 \textbf{**} & 23.53\textbf{**} & 2.71 &  & 7.14 & 26.43 / 28.38 \textbf{**} & 23.28\textbf{*} & 7.49\textbf{**} \\
\emph{Semantic Similarity} & 0.83 & 0.81 / 0.79 & 0.78 & 0.87 & & 0.82 & 0.73 / 0.75 & 0.79 & 0.82 &  & 0.83 & 0.72 / 0.73 & 0.78 & 0.86 \\

&\\

\hline
\textbf{} &  \multicolumn{14}{c}{\bf \emph{Method: Genetic}} \\
\hline
\emph{Avg. Accuracy Drop} & 0.73 & 1.11 /1.09 & \underline{1.23} & 0.69 &  & 0.75 & 1.28 / 1.31 & \underline{1.49} & 0.88 &  & 1.27 & 1.83 / \underline{1.97} & \underline{1.31} & 0.79 \\
\emph{Max. Accuracy Drop} & 7.45\textbf{**} & 23.79 / 25.31 & 22.78 & 7.02\textbf{**} &  & 3.66 & 22.75 / 22.56 & 21.00 & 5.98\textbf{**} &  & 8.55\textbf{**} & 24.21 / 26.40 & 17.34 & 7.09 \\
\emph{Semantic Similarity} & 0.77 & 0.72 / 0.70 & 0.76 & 0.81 & & 0.81 & 0.67 / 0.69 & 0.71 & 0.79 &  & 0.76 & 0.64 / 0.62 & 0.72 & 0.80 \\

&\\
\hline
\textbf{} &  \multicolumn{14}{c}{\bf \emph{Method: Ours}} \\
\hline
\emph{Avg. Accuracy Drop} & \textbf{5.97} & \textbf{21.07} / \textbf{20.31} & \textbf{6.84} & \textbf{5.01} &  & \textbf{5.81} & \textbf{21.96} / \textbf{21.48} & \textbf{6.20} & \textbf{4.59} &  & \textbf{7.84} & \textbf{23.47} / \textbf{22.93} & \textbf{5.92} & \textbf{4.27} \\
\emph{Max. Accuracy Drop} & 23.55\textbf{*} & 56.70\textbf{*} / 56.36\textbf{*} & 29.90\textbf{*} & 13.62\textbf{*} &  & 22.86\textbf{*} & 56.40\textbf{*} / 57.26\textbf{*} & 32.73\textbf{*} & 13.40\textbf{*} &  & 22.40\textbf{*} & 42.76\textbf{*} / 42.91\textbf{*} & 23.23\textbf{**} & 12.38\textbf{*} \\
\emph{Semantic Similarity} & 0.84 & 0.79 / 0.77 & 0.81 & 0.86 &  & 0.85 & 0.76 / 0.75 & 0.75 & 0.87 &  & 0.82 & 0.77 / 0.78 & 0.80 & 0.85  \\
\hline

\end{tabular}
\caption{Word adversarial attack results by perturbing at most $M=3$ words. This table shows accuracy drops for various methods as well as the average semantic score of the adversarial sentences to the original sentences. \emph{Pre-attack Accuracy} represents the accuracy on original sentences. \emph{Avg. Accuracy Drop} represent the drop in accuracy averaged over the adversarial candidates, whereas \emph{Max. Accuracy Drop} represents the maximum drop in accuracy achieved if any adversarial candidate in the set of $K=20$ succeeds.

Higher the drops, more successful the attack. Here, \emph{m} and \emph{mm} represent the \emph{matched} and \emph{mismatched} versions of the dev set respectively. For Average Drops, the best results are marked in \textbf{bold} whereas the second best \underline{underlined}. For Maximum Drops, the best results are marked by \textbf{*}, while the second best by \textbf{**}.}
\label{table:word_results}
\end{table*}

\section{Experiments}

\subsection{Datasets and Attacked Models}
We study the effectiveness of our proposed approach on various standard datasets from the well established GLUE\footnote{\footnotesize \url{https://gluebenchmark.com/}}~\citep{wang2018glue} benchmark.
It consists of the \emph{Stanford sentiment treebank (SST-2)}~\citep{socher-recursive}
(for sentiment analysis), the \emph{multi-genre natural language inference (MLNI)} corpus~\citep{williams-etal-2018-broad} and the \emph{question answering natural language inference (QNLI)} datasets~\citep{wang2018glue} (for natural language inference) and finally
the \emph{Quora Question Pairs (QQP)} and
the \emph{semantic textual similarity benchmark (STS-B)}~\citep{cer-semeval} (for paraphrasing).
From each dataset we pick $1000$ random instances from the dev set (except for \emph{SST-2}, where dev set size is $870$), since the actual test predictions are not publicly available.
We report the results for the classification experiments on \emph{SST-2}, \emph{MNLI}, \emph{QNLI}, and \emph{QQP} here, while for \emph{STS-B}, the results are provided in appendix.\\
We choose three dominant \emph{SOTA} models to show the efficacy of our novel \textit{target-agnostic} adversarial attack, namely \emph{BERT} ~\citep{DBLP:journals/corr/abs-1810-04805}, \emph{XLNet} ~\citep{DBLP:journals/corr/abs-1906-08237}, and \emph{BiLSTM with attention mechanism} ~\citep{wang2018glue}. A brief description of each dataset, the attacked models and the results on \emph{STS-B} are provided in the appendix.

\subsection{Attack Results}
In this section, we report the performance of the attacked models on the crafted adversarial samples from various methods. We compare our method with two well known black-box adversarial attacks methods.
The first baseline: \emph{TextFooler}~\citep{DBLP:journals/corr/abs-1907-11932}, which performs
iterative greedy attacks heuristically by replacing the original word with a word that drops the target
model's accuracy by the maximum margin. The other baseline is the popular \emph{genetic attack
algorithm}~\citep{alzantot-generating}, which iteratively crafts the adversarial samples using a genetic based algorithm that fuses two adversarial sequences to create a better adversarial sample. Both these methods are run under the similar budget, word perturbation and hyperparameter settings as  our model for fair evaluation.\\
The results for word perturbation factor \emph{M=3} are provided in table \ref{table:word_results}. Hereon, we use the terms \emph{candidate set size} as well as \emph{attack budget} interchangeably, both referring to \emph{K}. \emph{Pre Attack Acc} refers to the accuracy of the models on the original sentences. \emph{Avg. Accuracy Drop} represent the drops in accuracy averaged over all the adversarial candidates, whereas \emph{Max. Accuracy  Drops} represent the maximum drop in accuracy achieved if any adversarial candidate in the set of $K=20$ succeeds. \emph{Accuracy Drops} are calculated as the difference between \emph{pre-attack} accuracy (calculated over original sentences) and \emph{post-attack} accuracy (calculated over the adversarial candidates). Hence, \emph{higher the accuracy drops, more successful the attack}. It is evident from the table that our method outperforms the baseline methods by factors of up to \textbf{15} under very limited budget settings conforming to practical attack scenarios. The semantic similarity scores of our crafted adversarial samples are generally better than those of the baselines.

We also provide a mechanism to utilize our method for \emph{character level attacks}, which makes our method all the more practical and generalized compared to methods that either employ word-specific or character-specific attacks. Results of word perturbations of $4$ and $5$, the \emph{regression} dataset \emph{STS-B} and character level attacks are provided in the appendix.

\begin{comment}
\begin{table}[tbp]
		\small
		\centering

		\begin{tabular}{lccc}
			\\
			\hline
			\textbf{Method}   &  \textbf{3 Words}  & \textbf{4 Words} &  \textbf{5 Word} \\
			\hline
			\emph{Ours} & 2.06 & 2.29 & 2.42 \\
			\emph{TextFooler} & 2.22 & 2.35 & 2.43 \\
			\emph{Genetic} & 2.17 & 2.31 & 2.38 \\
			\hline
		\end{tabular}
		\setlength\tabcolsep{3.5pt}
		\begin{tabular}{lccc}
			\\
			\hline
			\textbf{Method}   &  \textbf{3 Words}  & \textbf{4 Words} &  \textbf{5 Word} \\
			\hline
			\emph{Ours} & 17.8 / 17.21 & 12.1 / 11.18 & 8.49 / 9.20 \\
			\emph{TextFooler} & 16.20 / 18.10 & 13.4 / 13.3 & 11.5 / 11.3 \\
			\emph{Genetic} & 17.49 / 18.1 & 13.29 / 12.51 & 10.79 / 12.21 \\
            \hline
		\end{tabular}
		\caption{Comparison of our method with baselines on STS-B (top table) and MNLI (bottom table) datasets, (values in the tables represent metric scores on adversarial sentences) with maximum perturbation allowed $M$ set to 3,4 and 5 words with the attacked model as BERT.}
		\label{table:Comparison}
\end{table}
\end{comment}

\section{Analysis}
\label{analysis_sec}
\noindent\textbf{Setting the value of K:}
We vary $K$ to ascertain the tightest possible budget for our method.
Figure \ref{fig:budget_diff} shows the \emph{average accuracy drops} versus different \emph{budget values} for XLNet model on MNLI, QNLI, and SST-2 datasets.
We choose the \emph{first point of inflection} at $K=20$ on all curves as our optimal value of budget $K$ across all datasets.
\begin{figure}[ht]
		\centering
		\includegraphics[width=60mm, height=40mm, center]{images/Average_XLNET_plot_budget}
		\caption{Average accuracy drops versus the budget value for XLNet model on various datasets.}
		\label{fig:budget_diff}
\end{figure}

\noindent\textbf{Attack transferability:}
We conduct transferability experiments w.r.t to baseline methods to examine how well the adversarial samples crafted by the SOTA baselines transfer from one target model to the other. The results for \emph{QQP} and \emph{QNLI} datasets are summarized in Table~\ref{table:Transferability}, with $M$ set to $3$. In the table, \emph{higher} the value, \emph{better} the attack. For our method, we select the \emph{true}  adversarial samples per original sentence from the first model to attack the other two models. The average \% \emph{drop} in model accuracies shown in the table are  averaged over all candidates. For the baselines which follow a greedy approach, the accuracy drops are extremely low when we transfer their adversarial sentences to other models, whereas our method is much more superior in this aspect. Our method is better by factors of upto \textbf{40} (depending upon model) as compared to the baselines and can craft highly generic adversaries, while preserving (to a large extent) the \emph{semantic} and \emph{syntactic} aspects of the original sentence. Additional results for maximum drops are provided in the appendix.

\begin{table}[tbp]
		\small

		\centering

		\begin{tabular}{lrrr}
			\\
			\hline
			\textbf{QQP}   &  \textbf{BERT}  & \textbf{XLNeT} &  \textbf{BiLSTM} \\
			\hline
			\emph{TextFooler Bert} & - & \underline{10.7} & \underline{12.05} \\
			\emph{TextFooler XLNeT} & 12.62\textbf{**} & - & 8.81 \\
			\hline
			\emph{Genetic Bert} & - & 0.5 & 9.19 \\
			\emph{Genetic XLNeT} & 10.68 & - & 13.58\textbf{**} \\
            \hline
			\emph{Our Bert} & - & \textbf{21.35} & \textbf{19.74} \\
			\emph{Our XLNeT} & 17.86\textbf{*} & - & 20.16\textbf{*} \\
			\hline
		\end{tabular}

		\begin{tabular}{lrrr}
			\\
			\hline
			\textbf{QNLI}   &  \textbf{BERT}  & \textbf{XLNeT} &  \textbf{BiLSTM} \\
			\hline
			\emph{TextFooler Bert} & - & \underline{4.33} & \underline{3.68} \\
			\emph{TextFooler XLNeT} & 0.27 & - & 1.54\textbf{**} \\
			\hline
			\emph{Genetic Bert} & - & 2.33 & 1.61 \\
			\emph{Genetic XLNeT} & 1.04\textbf{**} & - & 0.64 \\
			\hline
			\emph{Our Bert} & - & \textbf{10.28} & \textbf{9.08} \\
			\emph{Our XLNeT} & 8.68\textbf{*} & - & 9.61\textbf{*} \\
			\hline
		\end{tabular}

		\caption{Transferability attacks. Leftmost column header represents the original model (for which the adversaries were crafted) with the attack methods and the following three column headers represent the model on which these sentences were \emph{transferred} and evaluated. The values in the table show the average \% \emph{drop} in model accuracies on original samples and their crafted adversarial counterparts. '-' signifies same source and target model. For BERT, best results in \textbf{bold}, second best \underline{underlined}. For XLNet, best results are marked by \textbf{*}, second best by \textbf{**}.}
		\label{table:Transferability}
\end{table}

\begin{comment}
\begin{table}[ht]
		\small

		\centering
		\setlength\tabcolsep{3.5pt}
		\begin{tabular}{lccccc}
			\\
			\hline
			{} & \textbf{SST-2} & \textbf{MNLI(m / mm)} & \textbf{QQP} & \textbf{QNLI} \\
			\hline
			$\Delta$ Our & 33.497 & 67.84 / 66.67 & 43.24 & 0.66 \\
			\# Succ. Cand. & 18.39 & 51.29 / 53.84 & 32.24 & 1 \\
			&\\
			\hline
			$\Delta$ Random & 23.19 & 53.86 / 52.64 & 30.46 & 0.33 \\
			\# Succ. Cand. & 14.21 & 50.26 / 49.87 & 27.31 & 1  \\
			\hline
        \end{tabular}
        \caption{Comparison of our method vs random attacks. $\Delta$ represents the average drop in accuracies between original and adversarial samples.}
        \label{table:maximum_ablation}
\end{table}
\end{comment}

\begin{table}[ht]
		\small

		\centering
		\setlength\tabcolsep{3.5pt}
		\begin{tabular}{lccccc}
			\\
			\hline
			{} & \textbf{SST-2} & \textbf{MNLI(m / mm)} & \textbf{QQP} & \textbf{QNLI} \\
			\hline
			Av $\Delta$ Our & \textbf{5.81} & \textbf{21.96} / \textbf{21.48} & \textbf{6.20} & \textbf{4.59} \\
			Av $\Delta$ Random & 2.15 & 12.49 / 13.47 & 3.07 & 2.81 \\
			&\\
			\hline
			Max $\Delta$ Our & \textbf{22.86} & \textbf{56.40} / \textbf{57.26} & \textbf{32.73} & \textbf{13.40} \\
			Max $\Delta$ Random & 14.19 & 43.86 / 42.64 & 20.46 & 8.31 \\

			\hline
        \end{tabular}
        \caption{Comparison of our method versus random attacks. \emph{Av $\Delta$} represents the average drop, while \emph{Max $\Delta$} represent the maximum drop  in accuracies between original and adversarial samples. Better results in bold.}
        \label{table:ablation}
\end{table}

\noindent\textbf{Ablation study:}
Since our method primarily focuses on selecting important words for crafting adversarial samples,
we perform attacks on the target models by randomly replacing words from the
original sentence, keeping the rest of the steps the same as provided in Section~\ref{adv_generation_section}.
The results for the datasets with $M=3$ on XLNeT target model are provided
in Table~\ref{table:ablation}. This table contains the average \% drop as well the maximum \% drops in accuracies between the original sentences and their adversarial counterparts caused by our method and a random attack. Once again, \textit{higher} the value achieved, \textit{better} the attack. Clearly, the proposed word importance selection criteria helps in selecting important words from the sentence and generate better adversarial samples.
\begin{table}[ht]
\scriptsize
\label{HumanEval}
\centering
\begin{tabular}{lccc}
\\
\hline
\textbf{Dataset} & \textbf{Input Type}  &  \textbf{Grammar Score}  & \textbf{Clf Consistency} \\
\hline
\multirow{2}{0.7cm}{\centering SST-2} & Original & 4.6 & \multirow{2}{0.7cm}{\centering 87.34}  \\
{} & Adversary & 4.13 &  \\
\hline
\multirow{2}{0.7cm}{\centering MNLI} & Original & 4.54 & \multirow{2}{0.7cm}{\centering 80.11} \\
{} & Adversary & 4.07 & \\
\hline
\multirow{2}{0.7cm}{\centering QQP} & Original & 4.3 & \multirow{2}{0.7cm}{\centering 86.08} \\
{} & Adversary & 4.02 & \\
            \hline
\multirow{2}{0.7cm}{\centering QNLI} & Original & 4.61 & \multirow{2}{0.7cm}{\centering 82.47} \\
{} & Adversary & 4.08 & \\
            \hline
\end{tabular}
\caption{Overall Grammatical score and Human Classification consistency for the datasets.}.
\label{table:HumanEval}
\end{table}

\noindent\textbf{Human evaluation:}
Apart from the automatic evaluation, we also analyze the adversarial samples by asking language proficient human judges to score them against the original sentences. We ask three human judges to rate the sentences based on: overall sentence structure (semantic and syntactic well-formedness) as well as consistency of the adversarial sentences against the actual sentence labels. We consider $200$ samples from each dataset for the scenario with $M=3$ perturbed words. For each original sentence, we randomly select one of the generated candidates, and randomly shuffle them with the $200$ original sentences to obtain $400$ sentences to be analyzed. The overall grammatical structure is measured on a scale of $1$--$5$, whereas for the label consistency we check the percentage of adversarial sentences that were assigned the same label as the original sentence label by human judges. The analysis is summarized in Table~\ref{table:HumanEval}.

\noindent\textbf{Evaluating \emph{perplexity score} versus \emph{confidence score drops} trade-off:}
Clearly, an adversarial sentence with a very high-perplexity score has a better chance of fooling the model under attack because it is completely different from the original sentence. Ideally, we want adversarial sentences that have a low-perplexity score but can achieve high drops in accuracy.
To assess the quality of the generated adversaries and their capabilities of fooling the target models, we plot the \emph{sentence perplexity values} versus the \emph{drop in the correct class probability between the original and adversarial sentences}. Figure \ref{fig:ppl_scores} shows the plots on various datasets for $50$ randomly chosen sentences on \emph{BERT}. Observe that the majority of our adversarial sentences lie in the region of ``low-perplexity, high-confidence drops" (blue region), as opposed to baseline attacks whose adversarial sentences are spread over a very wide range of perplexity scores and are mostly confined to regions of low-to-medium confidence drops.
\if 0
It's evident that our curated adversaries are much better in quality and can reduce the model confidence by huge margins compared to the baselines. Many of our adversaries can completely reduce the model confidence of the correct class to \textbf{zero}, while the baselines almost never do.
\fi
\begin{figure*}[tbp]
		\centering
        \begin{subfigure}{.5\textwidth}
			\includegraphics[width=80mm, height=65mm]{images/ppl_scores/sst-2_mlp}
			\caption{SST-2}
			\label{fig:sub1_bert_ppl}
		\end{subfigure}%
		\begin{subfigure}{.5\textwidth}

			\includegraphics[width=80mm, height=65mm]{images/ppl_scores/mnli_random_forest}
			\caption{MNLI}
			\label{fig:sub2_xlnet_ppl}
		\end{subfigure}%

		\caption{Perplexity values versus confidence differences (probability difference of the correct class between the original and adversarial sentences). }
		\label{fig:ppl_scores}
\end{figure*}

\noindent\textbf{Attack time:} We analyze the time taken by different methods to attack the target models. It is evident from figure \ref{fig:runtime} that our method is faster by factors of \textbf{9-12} (depending on the dataset). We attribute this to \emph{independence} of the generated candidate adversaries from one another, thus allowing our method to perfrom attacks using mini-batches of data as opposed to the baselines, which iteratively improve the query and thus are forced to attack in a sequential manner. Similar attack run-time plots for BERT and XLNet are provided in our appendix.
\begin{figure}[ht]
		\centering
			\includegraphics[width=65mm, height=50mm]{images/BiLSTM_time_bud_20}
		\caption{Runtime for the attack methods on BiLSTM target model.}
		\label{fig:runtime}
\end{figure}

\noindent\textbf{High transferability and staggered attacks:} We observed that a substantial fraction of our true adversarial examples were “common” to all models. We can thus roll out our queries per model in a “staggered approach”, i.e., querying a model, gathering its true adversarial set S and only using examples from S to target the next model, hence "shrinking" S with every model we attack. This approach can drastically reduce the attack time if we have to attack multiple models in a sequential manner (i.e, when it's not possible to attack more than one model simultaneously). Results provided in table \ref{table:Staggered_main} verify our claims. The average \textbf{\%} values shown in the table represent the  percentage of successful adversarial samples out of the total samples the corresponding model was attacked with. Further experiments have been provided in the appendix.
\begin{table}[ht]

		\centering
		\begin{tabular}{lccc}
			\\
			\hline
			\textbf{Dataset}   &  \textbf{BERT}  & \textbf{XLNet} &  \textbf{BiLSTM} \\
			\hline
			\emph{MNLI} & 34\textbf{\%} & 39\textbf{\%} & 12\textbf{\%} \\
			\emph{SST-2} & 14\textbf{\%} & 33\textbf{\%} & 17\textbf{\%} \\
			\emph{QQP} & 25\textbf{\%} & 36\textbf{\%} & 9\textbf{\%} \\
            \emph{QNLI} & 17\textbf{\%} & 41\textbf{\%} & 19\textbf{\%} \\
			\hline
		\end{tabular}
		\caption{Staggered attacks. Values in the table represent \emph{average \%} of successful adversarial samples.}
		\label{table:Staggered_main}
\end{table}

\noindent\textbf{Comparison to previous paraphrase based attacks:} Prior paraphrase based attack methods such as ~\citep{iyyer-adversarial, ribeiro-semantically} propose template and rule based methods to curate adversaries. Verifying the correctness of these templates and rules can be difficult and may require manual investigations which is extremely time consuming. Training models to generate templates as done in ~\citep{iyyer-adversarial} requires training large scale models with large training sets, as opposed to our case. These templates and rules also have restrictions on their applicability as they can't be arbitrarily applied to any sentence. In contrast, our method is completely automated with very high semantics preservation properties, has high transferability, can attack multiple models via staggered approach as well as it has very low attack time attributed to batching of the candidates.
We also performed a quantitative and qualitative analysis of \textbf{classwise} accuracy drops for the datasets as well as show various examples of our successful adversaries, both are provided in appendix.\\

\noindent\textbf{Difference from Surrogacy based methods:} As mentioned earlier, our method follows a weaker black-box setting, where we assume the presence of a small amount of training data for ON-LSTM model. However, this is significantly different from the surrogacy based methods, where the surrogate model is explicitly trained to replicate the attacked model which requires a substantial amount of queries to the attacked model, thus incurring a huge budget.

\section{Conclusion}
We explore a novel target model agnostic adversarial attack under very limited query budgets. Unable to exploit biases of target models towards datasets, like other greedy methods do, this method carries multiple other advantages. The actual attack process is fast and the generated pool of adversarial sentences show a high degree of transferability across different types of models which brings the added benefit of attacking multiple target models simultaneously by the same candidate set. Our method performs well in comparison to the greedy SOTA adversarial attacks with a tighter budget on the number of queries, which makes our attack much more practical.