Supplement To: A General Retraining Framework for Scalable Adversarial Classification
Bo Li
bo.li.2@vanderbilt.edu
% David S.~Hippocampus\thanks{Use footnote for providing further % information about author (webpage
alternative % address)---not
% David S.~Hippocampus\thanks{Use footnote for providing further % information about author (webpage
alternative % address)---not
Traditional machine learning is vulnerable against deliberate attacks given the fact that the risk minimization process of learner is built on the stationary assumption for training and testing data distribution. It has been shown that malicious adversaries can conduct either poisoning or evasion attack via modifying the training/testing data. To analyze the adversarial behaviors in evasion attacks for different learning models, we first provide a general framework for generating adversarial instances for a wide variety of classifiers, including SVM, Bayesian regression, Ridge regression, and neural networks with different hidden layers for comparison purpose. We then form the interaction between learner and attacker as a Stackelberg game and propose a scalable learning approach against the adversarially generated evasion instances. We also prove the upper bound for the learner's loss for this approach. We show that the proposed learning algorithm can make robust predictions via retraining process for various learning models on adversarially optimized instances. Intensive experiments on multiple datasets have demonstrated that robust prediction can be achieved by shifting the training distribution accordingly.
nips_2016_retraining.tex
\documentclass{article}

% if you need to pass options to natbib, use, e.g.:
% \PassOptionsToPackage{numbers, compress}{natbib}
% before loading nips_2016
%
% to avoid loading the natbib package, add option nonatbib:
% \usepackage[nonatbib]{nips_2016}

% \usepackage{nips_2016}

% to compile a camera-ready version, add the [final] option, e.g.:
\usepackage[final]{nips_2016}
\pdfoutput=1
\usepackage[utf8]{inputenc} % allow utf-8 input
\usepackage[T1]{fontenc}    % use 8-bit T1 fonts
% \usepackage{hyperref}       % hyperlinks
\usepackage{url}            % simple URL typesetting
\usepackage{booktabs}       % professional-quality tables
\usepackage{amsfonts}       % blackboard math symbols
\usepackage{nicefrac}       % compact symbols for 1/2, etc.
\usepackage{microtype}      % microtypography
\usepackage{amsmath,amsfonts,amsthm,amssymb}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{times}
\usepackage{natbib}
% For figures
\usepackage{graphicx} % more modern
%\usepackage{epsfig} % less modern
\usepackage{subfigure} 

% Employ this version of the ``usepackage'' statement after the paper has
% been accepted, when creating the final version.  This will set the
% note in the first column to ``Proceedings of the...''
%\usepackage[accepted]{icml2015}

\newcommand{\R}{\ensuremath{\mathcal{R}}}

\newtheorem{defn}{Definition}[section]
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{example}{Example}[section]
\newtheorem{lemma}{Lemma}[section]
% \setcounter{secnumdepth}{1}  
\DeclareMathOperator*{\argmin}{arg\,min}
\newcommand{\vct}{\boldsymbol }
\newcommand{\mat}{\mathbf}
\newcommand{\rnd}{\mathsf}
\newcommand{\ud}{\mathrm d}
\newcommand{\nml}{\mathcal{N}}
\newcommand{\loss}{\mathcal{L}}
\newcommand{\hinge}{\mathcal{R}}
\newcommand{\kl}{\mathrm{KL}}
\newcommand{\cov}{\mathrm{cov}}
\newcommand{\dir}{\mathrm{Dir}}
\newcommand{\mult}{\mathrm{Mult}}
\newcommand{\err}{\mathrm{err}}
\newcommand{\sgn}{\mathrm{sgn}}
%\renewcommand{\span}{\mathrm{span}}
% \newcommand{\argmin}{\mathrm{argmin}}
\newcommand{\argmax}{\mathrm{argmax}}
\newcommand{\poly}{\mathrm{poly}}
\newcommand{\rank}{\mathrm{rank}}
\newcommand{\conv}{\mathrm{conv}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\diag}{\mat{diag}}
\newcommand{\acc}{\mathrm{acc}}

\newcommand{\aff}{\mathrm{aff}}
\newcommand{\range}{\mathrm{Range}}
\newcommand{\Sgn}{\mathrm{sign}}

\newcommand{\hit}{\mathrm{hit}}
\newcommand{\cross}{\mathrm{cross}}
\newcommand{\Left}{\mathrm{left}}
\newcommand{\Right}{\mathrm{right}}
\newcommand{\Mid}{\mathrm{mid}}
\newcommand{\bern}{\mathrm{Bernoulli}}

\newcommand{\avail}{\mathrm{av}}
\newcommand{\eva}{\mathrm{in}}
\newcommand{\hybrid}{\mathrm{hybrid}}
\newcommand{\proj}{\mathrm{Proj}}

\newcommand{\leaveout}[1]{}

\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}{Lemma}[section]
\newtheorem{cor}{Corollary}[section]
\newtheorem{prop}{Proposition}[section]
\newtheorem{asmp}{Assumption}[section]
% \newtheorem{defn}{Definition}[section]
\newtheorem{fact}{Fact}[section]

\title{A General Retraining Framework for Scalable Adversarial Classification}

% The \author macro works with any number of authors. There are two
% commands used to separate the names and addresses of multiple
% authors: \And and \AND.
%
% Using \And between authors leaves it to LaTeX to determine where to
% break the lines. Using \AND forces a line break at that point. So,
% if LaTeX puts 3 of 4 authors names on the first line, and the last
% on the second line, try using \AND instead of \And before the third
% author name.

\author{
Bo Li \\
\texttt{bo.li.2@vanderbilt.edu} \\
Vanderbilt University \\
\And
 Yevgeniy Vorobeychik   \\
\texttt{yevgeniy.vorobeychik@vanderbilt.edu} \\
Vanderbilt University \\
\And
 Xinyun Chen  \\
\texttt{jungyhuk@gmail.com}          \\
Shanghai Jiaotong University \\
}
% \author{
%   David S.~Hippocampus\thanks{Use footnote for providing further
%     information about author (webpage, alternative
%     address)---\emph{not} for acknowledging funding agencies.} \\
%   Department of Computer Science\\
%   Cranberry-Lemon University\\
%   Pittsburgh, PA 15213 \\
%   \texttt{hippo@cs.cranberry-lemon.edu} \\
%   %% examples of more authors
%   %% \And
%   %% Coauthor \\
%   %% Affiliation \\
%   %% Address \\
%   %% \texttt{email} \\
%   %% \AND
%   %% Coauthor \\
%   %% Affiliation \\
%   %% Address \\
%   %% \texttt{email} \\
%   %% \And
%   %% Coauthor \\
%   %% Affiliation \\
%   %% Address \\
%   %% \texttt{email} \\
%   %% \And
%   %% Coauthor \\
%   %% Affiliation \\
%   %% Address \\
%   %% \texttt{email} \\
% }

\begin{document}
% \nipsfinalcopy is no longer used

\maketitle

\begin{abstract}
Traditional classification algorithms assume that training and test
data come from similar distributions.
This assumption is violated in adversarial settings,
where malicious actors modify instances to evade detection.
A number of 
custom methods have been developed for both adversarial evasion attacks and 
robust learning.
We propose the first systematic and general-purpose retraining
framework which can: a) boost robustness of an \emph{arbitrary} learning
algorithm, in the face of b) a broader class of adversarial models
than any prior methods.
We show that, under natural
conditions, the retraining framework minimizes an upper
bound on optimal adversarial risk, and show how to extend this result
to account for approximations of evasion attacks.
Extensive experimental evaluation demonstrates that our retraining
methods are nearly indistinguishable from state-of-the-art algorithms
for optimizing adversarial risk, but are \emph{more general
and far more scalable}.
The experiments also confirm that without retraining, our adversarial
framework dramatically reduces the effectiveness of learning.
In contrast, retraining significantly boosts
robustness to evasion attacks without significantly compromising 
overall accuracy.
\end{abstract}

\section{Introduction}
\input{sections_paper/intro}

\input{sections_paper/model}
\input{sections_paper/retraining}
\input{sections_paper/attacks}
%\input{sections_paper/multiclass}

\section{Experimental Results}
\input{sections_paper/exp}

% \section{Conclusions and future work}
\input{sections_paper/conclusion}

%\subsubsection*{Acknowledgements}
%This work was partially supported by Sandia National Laboratories contract 2244, and Army Research Office grant number W911NF-16-1-0069.

%\newpage




% \subsubsection*{References}
\small
\bibliography{nips_2016_retraining}
\bibliographystyle{unsrt}

\newpage
\normalsize
\section*{Supplement To: A General Retraining Framework for Scalable Adversarial Classification}
\input{sections_paper/supplement}

\end{document}

supplement.tex
\subsection*{Proof of Lemma 4.1}

If $f(x^*) < 0$, then $\min\{0,f(x^*)\} + c(x^*,x_i) = f(x^*) +
c(x^*,x_i)$.
By optimality of $\bar{x}$, $f(\bar{x}) + c(\bar{x},x_i) \le f(x^*) +
c(x^*,x_i)$.
Since $x_i$ is suboptimal in Problem~(4) and $c$ strictly
positive in all other cases, $f(x^*) +
c(x^*,x_i) < \min\{0,f(x_i)\} + c(x_i,x_i) =0$.
By optimality of $x^*$, $f(x^*) + c(x^*,x_i) \le \min\{0,f(\bar{x})\}
+ c(\bar{x},x_i) \le f(\bar{x}) + c(\bar{x}, x_i)$, which implies that
$f(\bar{x}) + c(\bar{x},x_i) = f(x^*) + c(x^*,x_i)$.
Consequently, $f(\bar{x}) + c(\bar{x},x_i) < 0$, and, therefore,
$f(\bar{x}) < 0$.

\subsection*{Proof of Proposition 4.2}

Let $\bar{\beta} \in \arg\min_{\beta}  \mathcal{L}^R_N(\beta,
\mathcal{O}_L)$.
Consequently, for any $\beta$,
\begin{align*}
\mathcal{L}_{A,01}^*(\mathcal{O}_L) &= \min_\beta \mathcal{L}_{A,01}(\beta;
\mathcal{O}_L) \\
&\le \sum_{i: y_i = -1} l_{01}(g_{\bar{\beta}}(x_i),-1) +\sum_{i:y_i = +1}
l_{01}(g_{\bar{\beta}} (\mathcal{O}(\bar{\beta},x_i)),+1) + \alpha ||\bar{\beta}||_p^p.
\end{align*}
Now,
\begin{align*}
\sum_{i:y_i = +1} &l_{01}(g_{\bar{\beta}}
(\mathcal{O}(\bar{\beta},x_i)),+1) \le \sum_{i:y_i = +1} l_{01}(g_{\bar{\beta}}
(\mathcal{O}_L(\bar{\beta},x_i)),+1) + \delta(p)
\end{align*}
with probability at least $1 - p$,
% where $\delta(p) = (p_L + (-\frac{1}{2B} \log p)^{1/2})$,
where $\delta(p) = B p_L + \frac{\sqrt{\log^2 p-8 B p_l \log p}-\log p}{2}$,
by the Chernoff bound, and Lemma~4.1, which assures that an
optimal solution to Problem~(5) can only over-estimate mistakes.
Moreover,
\begin{align*}
\sum_{i:y_i = +1} &l_{01}(g_{\bar{\beta}}
(\mathcal{O}_L(\bar{\beta},x_i)),+1) \le\sum_{i:y_i = +1}\sum_{j \in N_i} l(g_{\bar{\beta}}
(\mathcal{O}_L(\bar{\beta},x_i)),+1),
\end{align*}
since $\mathcal{O}_L(\bar{\beta},x_i) \in N_i$ for all $i$ by
construction, and $l$ is an upper bound on $l_{01}$.
Putting everything together, we get the desired result.

\subsection*{Convergence of $p_L$ with Increasing Number of Restarts $L$}

\begin{figure}[H]
\centering 
\begin{tabular}{cc}
\includegraphics[scale=0.23]{images/binary_start.png} &
\includegraphics[scale=0.23]{images/continuous_start.png} \\
(a) & (b)
\end{tabular}
\caption{The convergence of $p_L$ based on different number of starting points for (a) Binary, (b) Continuous feature space.}
\label{fig:start}
\end{figure}

\subsection*{Attacks as Constrained Optimization}

A variation on the attack models in the main paper is when the attacker is solving
the following constrained optimization problem:
\begin{subequations}
\label{E:constrainedAttacks}
\begin{align}
&\min_x \min\{0,f(x)\}\\
&\mathrm{s.t.:} \quad c(x,x_i) \le B
\end{align}
\end{subequations}
for some cost budget constraint $B$ and query budget constraint $Q$.
While this problem is, again, non-convex, we can instead minimize the
convex upper bound, $f(x)$, as before, if we assume that $f(x)$ is
convex.
In this case, if the feature space is continuous, the problem can be
solved optimally using standard convex optimization
methods~\cite{Boyd04}.
If the feature space is binary and $f(x)$ is linear or
convex-inducing, algorithms proposed by Lowd and
Meek~\cite{lowd2005adversarial} and Nelson et
al.~\cite{nelson2012query}. Figure~\ref{fig:constraint_nb}, \ref{fig:constraint_svm} and~\ref{fig:constraint_3nn} show the performance of \emph{RAD} based on the optimized adversarial strategies for various learning models, respectively. 

\begin{figure}[tbfh]
\centering 
\begin{tabular}{cc}
\includegraphics[scale=0.23]{images/cost/constraint_nb_enronq30.png} &
\includegraphics[scale=0.23]{images/cost/constraint_nb_enronq40.png} \\
(a) & (b)
\end{tabular}
\caption{Performance of baseline (\emph{adv-}) and \emph{RAD} (\emph{rob-}) as a function of adversarial budget for Enron dataset with binary features testing on adversarial instances using Naive Bayesian. (a) query budget $Q=30$, (b) query budget $Q=40$.}
\label{fig:constraint_nb}
\end{figure}

\begin{figure}[tbfh]
\centering 
\begin{tabular}{cc}
\includegraphics[scale=0.23]{images/cost/svm_q30.png} &
\includegraphics[scale=0.23]{images/cost/svm_q40.png} \\
(a) & (b)
\end{tabular}
\caption{Performance of baseline (\emph{adv-}) and \emph{RAD} (\emph{rob-}) as a function of adversarial budget for Enron dataset with binary features testing on adversarial instances using SVM with RBF kernel. (a) query budget $Q=30$, (b) query budget $Q=40$.}
\label{fig:constraint_svm}
\end{figure}

\begin{figure}[tbfh]
\centering 
\begin{tabular}{cc}
\includegraphics[scale=0.23]{images/cost/nn3_q30.png} &
\includegraphics[scale=0.23]{images/cost/nn3_q40.png} \\
(a) & (b)
\end{tabular}
\caption{Performance of baseline (\emph{adv-}) and \emph{RAD} (\emph{rob-}) as a function of adversarial budget for Enron dataset with binary features testing on adversarial instances using 3-layer NN. (a) query budget $Q=30$, (b) query budget $Q=40$.}
\label{fig:constraint_3nn}
\end{figure}


\subsection*{Experiments with Continuous Feature Space}


\begin{figure}[H]
\centering 
\begin{tabular}{cccc}
\includegraphics[scale=1.0]{images/logistic/0.png} &
\includegraphics[scale=1.0]{images/logistic/3.png} &
\includegraphics[scale=1.0]{images/logistic/6.png} &
\includegraphics[scale=1.0]{images/logistic/8.png}\\
\includegraphics[scale=1.0]{images/svm/0.png} &
\includegraphics[scale=1.0]{images/svm/3.png} &
\includegraphics[scale=1.0]{images/svm/6.png} &
\includegraphics[scale=1.0]{images/svm/8.png} \\
\includegraphics[scale=1.0]{images/nn1/0.png} &
\includegraphics[scale=1.0]{images/nn1/3.png} &
\includegraphics[scale=1.0]{images/nn1/6.png} &
\includegraphics[scale=1.0]{images/nn1/8.png}\\
\includegraphics[scale=1.0]{images/nn3/0.png} &
\includegraphics[scale=1.0]{images/nn3/3.png} &
\includegraphics[scale=1.0]{images/nn3/6.png} &
\includegraphics[scale=1.0]{images/nn3/9.png}
\end{tabular}
\caption{Example modification of digit images (MNIST data) as
  $\lambda$ decreases (left-to-right) for logistic regression,
SVM, 1-layer NN, and 3-layer NN (rows 1-4 respectively).}
\label{fig:visual_logistic}
\end{figure}

In Figure~\ref{fig:visual_logistic} we visualize the relative
vulnerability of the different classifiers, as well as effectiveness
of our general-purpose evasion methods based on coordinate greedy.
Each row corresponds to a classifier, and moving right within a row
represents decreasing $\lambda$ (allowing attacks to make more
substantial modifications to the image in an effort to evade correct
classification).
We can observe that NN classifiers require more substantial changes to
the images to evade, ultimately making these entirely unlike the
original.
In contrast, logistic regression is quite vulnerable: the digit
remains largely recognizable even after evasion attacks.

\subsection*{Experiments with Discrete Feature Space}

%\subsection{Discrete Feature Space}

Considering now data sets with binary features, we use the Enron data
with a bag-of-words feature representation, for a total of 2000
features.
We compare Naive Bayes (NB), logistic regression, SVM, and a 3-layer
neural network.
Our comparison involves both the baseline, and \emph{RAD}
implementations of these, using the same metrics as above.

\begin{figure*}[tbfh]
\centering 
\begin{tabular}{cccc}
\includegraphics[scale=0.21]{images/nb_model2_2000.png} &
\includegraphics[scale=0.21]{images/logistic_binary2000.png} \\
(a) & (b) \\
\includegraphics[scale=0.21]{images/binary2_enron_svm2000.png} &
\includegraphics[scale=0.21]{images/nn3_enron_model2_2000.png}\\
(c) & (d)
%(a) & (b)
\end{tabular}
\caption{Performance of baseline (\emph{adv-}) and \emph{RAD} (\emph{rob-}) implementations of (a) Naive
  Bayes, (b) logistic regression, (c) SVM, and (d) 3-layer NN, using binary features testing on adversarial instances.}
\label{fig:enron_binary}
\end{figure*}

Figure~\ref{fig:enron_binary} confirms the effectiveness of
\emph{RAD}: every algorithm is substantially more robust to evasion
with retraining, compared to baseline implementation.
Most of the algorithms can obtain extremely high accuracy on this data
with the bag-of-words feature representation.
However, a 3-layer neural network is now
\emph{less} robust than the other algorithms, unlike in the
experiments with continuous features.
Indeed, Goodfellow et
al.~\cite{goodfellow2014explaining} similarly observe the relative
fragility of NN to evasion attacks.

\subsection*{Experiments with Multi-class Classification}
\input{sections_paper/multiclass}

To evaluate the effectiveness of \emph{RAD}, and resilience of
baseline algorithms, in multi-class classification settings, we use
the MNIST dataset and aim to correctly identify digits based on their
images.
Our comparison involves SVM and 3-layer neural network (results for
NN-1 are similar).
We use $M = \{1,4\}$ as the malicious class (that is, instances
corresponding to digits $1$ and $4$ are malicious), and $T = \{2,7\}$
is the set of benign labels (what malicious instances wish to be
classified as).
\begin{figure}[tbfh]
\centering 
\begin{tabular}{cccc}
\includegraphics[scale=0.23]{images/multi/multi_svm784.png} &
\includegraphics[scale=0.23]{images/multi/multi_nn3_784.png} &
\end{tabular}
\caption{Performance of baseline (\emph{adv-}) and RAD (\emph{rob-}) implementations of (a) multi-class SVM
  and (b) multi-class 3-layer NN, using MNIST dataset testing on adversarial instances.}
\label{fig:enron_binary_multiclass}
\end{figure}
The results, shown in Figure~\ref{fig:enron_binary_multiclass} are largely
consistent with our previous observations: both SVM and 3-layer NN
perform well when retrained with \emph{RAD}, with near-perfect
accuracy despite adversarial evasion attempts.
Moreover, \emph{RAD} significantly boosts robustness to evasion,
particularly when $\lambda$ is small (adversary who is not very
sensitive to evasion costs).

\begin{figure}[h]
\centering
\begin{tabular}{cccc}
\includegraphics[scale=1.0]{images/multi/svm_1/0.png} &
\includegraphics[scale=1.0]{images/multi/svm_1/3.png} &
\includegraphics[scale=1.0]{images/multi/svm_1/5.png} &
\includegraphics[scale=1.0]{images/multi/svm_1/8.png} \\
\includegraphics[scale=1.0]{images/multi/nn_1/0.png} &
\includegraphics[scale=1.0]{images/multi/nn_1/3.png} &
\includegraphics[scale=1.0]{images/multi/nn_1/5.png} &
\includegraphics[scale=1.0]{images/multi/nn_1/8.png} \\
\end{tabular}
\caption{Visualization of modification attacks with decreasing the
  cost sensitivity parameter $\lambda$ (from left to right), to change
  1 to the set \{2,7\}. The rows correspond to SVM and
  3-layer NN, respectively.}
\label{fig:visual_multi_1}
\end{figure}
Figure~\ref{fig:visual_multi_1} offers a visual demonstration of the relative
effectiveness of attacks on the baseline implementation of SVM and 1-
and 3-layer neural networks.
Here, we can observe that a significant change is required to evade
the linear SVM, with the digit having to nearly resemble a 2 after
modification.
In contrast, significantly less noise is added to the neural network
in effecting evasion.

\leaveout{
% visual results for svm 1
\begin{figure}[tbfh]
\centering 
\begin{tabular}{cccc}
\includegraphics[scale=1.00]{images/multi/svm_1/0.png} &
\includegraphics[scale=1.00]{images/multi/svm_1/1.png} &
\includegraphics[scale=1.00]{images/multi/svm_1/3.png} &
\includegraphics[scale=1.00]{images/multi/svm_1/4_0_5.png} \\
\includegraphics[scale=1.00]{images/multi/svm_1/5.png} &
\includegraphics[scale=1.00]{images/multi/svm_1/6.png} &
\includegraphics[scale=1.00]{images/multi/svm_1/8.png} &
\includegraphics[scale=1.00]{images/multi/svm_1/10.png} \\
\end{tabular}
\caption{Modification process of attacker for SVM with linear kernel by decreasing the cost sensitivity parameter $\lambda$ to change number ``1" to other classes (2,7).}
\label{fig:visual_svm_multi_1}
\end{figure}

% visual results for svm 4
\begin{figure}[tbfh]
\centering 
\begin{tabular}{cccc}
\includegraphics[scale=1.00]{images/multi/svm_4/1.png} &
\includegraphics[scale=1.00]{images/multi/svm_4/2.png} &
\includegraphics[scale=1.00]{images/multi/svm_4/5.png} &
\includegraphics[scale=1.00]{images/multi/svm_4/6.png} \\
\includegraphics[scale=1.00]{images/multi/svm_4/7.png} &
\includegraphics[scale=1.00]{images/multi/svm_4/8.png} &
\includegraphics[scale=1.00]{images/multi/svm_4/9.png} &
\includegraphics[scale=1.00]{images/multi/svm_4/10.png} \\
\end{tabular}
\caption{Modification process of attacker for SVM with linear kernel by decreasing the cost sensitivity parameter $\lambda$ to change number ``4" to other classes (2,7).}
\label{fig:visual_svm_multi_4}
\end{figure}

% visual results for svm 1
\begin{figure}[tbfh]
\centering 
\begin{tabular}{cccc}
\includegraphics[scale=1.00]{images/multi/nn_1/0.png} &
\includegraphics[scale=1.00]{images/multi/nn_1/1.png} &
\includegraphics[scale=1.00]{images/multi/nn_1/3.png} &
\includegraphics[scale=1.00]{images/multi/nn_1/4.png} \\
\includegraphics[scale=1.00]{images/multi/nn_1/5.png} &
\includegraphics[scale=1.00]{images/multi/nn_1/6.png} &
\includegraphics[scale=1.00]{images/multi/nn_1/7.png} &
\includegraphics[scale=1.00]{images/multi/nn_1/8.png} \\
\end{tabular}
\caption{Modification process of attacker for Neural network with 3 hidden layers by decreasing the cost sensitivity parameter $\lambda$ to change number ``1" to other classes (2,7).}
\label{fig:visual_nn3_multi_1}
\end{figure}

% visual results for svm 4
\begin{figure}[tbfh]
\centering 
\begin{tabular}{cccc}
\includegraphics[scale=1.00]{images/multi/nn_4/0.png} &
\includegraphics[scale=1.00]{images/multi/nn_4/1.png} &
\includegraphics[scale=1.00]{images/multi/nn_4/2_0_5.png} &
\includegraphics[scale=1.00]{images/multi/nn_4/3.png} \\
\includegraphics[scale=1.00]{images/multi/nn_4/4.png} &
\includegraphics[scale=1.00]{images/multi/nn_4/5.png} &
\includegraphics[scale=1.00]{images/multi/nn_4/6.png} &
\includegraphics[scale=1.00]{images/multi/nn_4/7.png} \\
\end{tabular}
\caption{Modification process of attacker for Neural network with 3 hidden layers by decreasing the cost sensitivity parameter $\lambda$ to change number ``4" to other classes (2,7).}
\label{fig:visual_nn3_multi_4}
\end{figure}
}

\subsection*{Evaluation of Cost Function Variations and Robustness to
  Misspecification}
Considering the variations of cost functions, here we evaluate the classification efficiency for various cost functions as well as different cost functions for defender and adversary, respectively. 
Figure~\ref{fig:cost_variation} shows the empirical evaluation results based on Enron dataset with binary features. It is shown that if both the defender and adversary apply the L1 (a) or quadratic cost functions (b), it is easy to defend the malicious manipulations. Even the defender mistakenly evaluate the adversarial cost models as shown in Figure~\ref{fig:cost_variation} (c), $RAD$ framework can still defend the attack strategies efficiently.

\begin{figure*}[tbfh]
\centering 
\begin{tabular}{cccc}
\includegraphics[scale=0.193]{images/cost/l1_cost.png} &
\includegraphics[scale=0.193]{images/cost/l2_cost.png} &
\includegraphics[scale=0.193]{images/cost/expTrain_l2test.png} \\
% \includegraphics[scale=0.193]{images/cost/l2Train_exptest.png} \\
(a) & (b) & (c) 
\end{tabular}
\caption{Performance of baseline (\emph{adv-}) and \emph{RAD} (\emph{rob-}) as a function of cost
  sensitivity $\lambda$ for Enron dataset with binary features testing on adversarial instances. (a) both defender and adversary use the L1 distance cost function, (b) both defender and adversary use the quadratic distance cost function, (c) adversary uses quadratic cost function while defender estimates it based on exponential cost.
  % (d) exponential for adversary and L2 for defender.
  }
\label{fig:cost_variation}
\end{figure*}

\begin{figure*}[tbfh]
\centering 
\begin{tabular}{cccc}
\includegraphics[scale=0.23]{images/cost/eq_based.png} &
\includegraphics[scale=0.23]{images/cost/eqTrain_exptest.png} \\
(a) & (b) 
\end{tabular}
\caption{Performance of baseline (\emph{adv-}) and \emph{RAD} (\emph{rob-}) as a function of cost
  sensitivity $\lambda$ for Enron dataset with binary features testing on adversarial instances. (a) both defender and adversary use the equivalence-based cost function, (b) adversary uses equivalence-based cost function while defender estimates it based on exponential cost.
  }
\label{fig:cost_equivalence}
\end{figure*}

\subsection*{Experiments for Clustering Malicious Instances}
To efficiently speed up the proposed algorithm, here we cluster the malicious instances and use the
center of each cluster to generate the potential ``evasion" instances for the retraining framework.
Figure~\ref{fig:clustering_res} shows that the running time can be reduced by applying the clustering algorithm to the original malicious instances and the classification performance stays pretty stable for different learning models. 

\begin{figure*}[tbfh]
\centering 
\begin{tabular}{cccc}
\includegraphics[scale=0.23]{images/cost/runtime_cluster.png} &
\includegraphics[scale=0.23]{images/cost/acc_clustering.png} \\
(a) & (b) 
\end{tabular}
\caption{Performance of different learning models based on the number of clusters for Enron dataset testing on adversarial instances. (a) Running time, (b) classification accuracy of \emph{RAD}.
  }
\label{fig:clustering_res}
\end{figure*}
sup1.tex
\documentclass{article}

% if you need to pass options to natbib, use, e.g.:
% \PassOptionsToPackage{numbers, compress}{natbib}
% before loading nips_2016
%
% to avoid loading the natbib package, add option nonatbib:
% \usepackage[nonatbib]{nips_2016}

\usepackage{nips_2016}

% to compile a camera-ready version, add the [final] option, e.g.:
% \usepackage[final]{nips_2016}

\usepackage[utf8]{inputenc} % allow utf-8 input
\usepackage[T1]{fontenc}    % use 8-bit T1 fonts
% \usepackage{hyperref}       % hyperlinks
\usepackage{url}            % simple URL typesetting
\usepackage{booktabs}       % professional-quality tables
\usepackage{amsfonts}       % blackboard math symbols
\usepackage{nicefrac}       % compact symbols for 1/2, etc.
\usepackage{microtype}      % microtypography
\usepackage{amsmath,amsfonts,amsthm,amssymb}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{times}
% For figures
\usepackage{graphicx} % more modern
%\usepackage{epsfig} % less modern
\usepackage{subfigure} 

% Employ this version of the ``usepackage'' statement after the paper has
% been accepted, when creating the final version.  This will set the
% note in the first column to ``Proceedings of the...''
%\usepackage[accepted]{icml2015}

\newcommand{\R}{\ensuremath{\mathcal{R}}}

\newtheorem{defn}{Definition}[section]
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{example}{Example}[section]
\newtheorem{lemma}{Lemma}[section]
% \setcounter{secnumdepth}{1}  
\DeclareMathOperator*{\argmin}{arg\,min}
\newcommand{\vct}{\boldsymbol }
\newcommand{\mat}{\mathbf}
\newcommand{\rnd}{\mathsf}
\newcommand{\ud}{\mathrm d}
\newcommand{\nml}{\mathcal{N}}
\newcommand{\loss}{\mathcal{L}}
\newcommand{\hinge}{\mathcal{R}}
\newcommand{\kl}{\mathrm{KL}}
\newcommand{\cov}{\mathrm{cov}}
\newcommand{\dir}{\mathrm{Dir}}
\newcommand{\mult}{\mathrm{Mult}}
\newcommand{\err}{\mathrm{err}}
\newcommand{\sgn}{\mathrm{sgn}}
%\renewcommand{\span}{\mathrm{span}}
% \newcommand{\argmin}{\mathrm{argmin}}
\newcommand{\argmax}{\mathrm{argmax}}
\newcommand{\poly}{\mathrm{poly}}
\newcommand{\rank}{\mathrm{rank}}
\newcommand{\conv}{\mathrm{conv}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\diag}{\mat{diag}}
\newcommand{\acc}{\mathrm{acc}}

\newcommand{\aff}{\mathrm{aff}}
\newcommand{\range}{\mathrm{Range}}
\newcommand{\Sgn}{\mathrm{sign}}

\newcommand{\hit}{\mathrm{hit}}
\newcommand{\cross}{\mathrm{cross}}
\newcommand{\Left}{\mathrm{left}}
\newcommand{\Right}{\mathrm{right}}
\newcommand{\Mid}{\mathrm{mid}}
\newcommand{\bern}{\mathrm{Bernoulli}}

\newcommand{\avail}{\mathrm{av}}
\newcommand{\eva}{\mathrm{in}}
\newcommand{\hybrid}{\mathrm{hybrid}}
\newcommand{\proj}{\mathrm{Proj}}

\newcommand{\leaveout}[1]{}

\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}{Lemma}[section]
\newtheorem{cor}{Corollary}[section]
\newtheorem{prop}{Proposition}[section]
\newtheorem{asmp}{Assumption}[section]
% \newtheorem{defn}{Definition}[section]
\newtheorem{fact}{Fact}[section]

\title{Supplement To: A General Retraining Framework for Scalable Adversarial Classification}

% The \author macro works with any number of authors. There are two
% commands used to separate the names and addresses of multiple
% authors: \And and \AND.
%
% Using \And between authors leaves it to LaTeX to determine where to
% break the lines. Using \AND forces a line break at that point. So,
% if LaTeX puts 3 of 4 authors names on the first line, and the last
% on the second line, try using \AND instead of \And before the third
% author name.

\author{}
% \author{
%   David S.~Hippocampus\thanks{Use footnote for providing further
%     information about author (webpage, alternative
%     address)---\emph{not} for acknowledging funding agencies.} \\
%   Department of Computer Science\\
%   Cranberry-Lemon University\\
%   Pittsburgh, PA 15213 \\
%   \texttt{hippo@cs.cranberry-lemon.edu} \\
%   %% examples of more authors
%   %% \And
%   %% Coauthor \\
%   %% Affiliation \\
%   %% Address \\
%   %% \texttt{email} \\
%   %% \AND
%   %% Coauthor \\
%   %% Affiliation \\
%   %% Address \\
%   %% \texttt{email} \\
%   %% \And
%   %% Coauthor \\
%   %% Affiliation \\
%   %% Address \\
%   %% \texttt{email} \\
%   %% \And
%   %% Coauthor \\
%   %% Affiliation \\
%   %% Address \\
%   %% \texttt{email} \\
% }

\begin{document}
% \nipsfinalcopy is no longer used

\maketitle




\input{supplement}
\small
\bibliography{rev}
\bibliographystyle{unsrt}

\end{document}

retraining.tex
\section{Adversarial Learning through Retraining}

A number of approaches have been proposed for making learning
algorithms more robust to adversarial evasion
attacks~\cite{dalvi2004adversarial,li2014feature,li2015scalable,teo2007convex,bruckner2011stackelberg}.
However, these approaches typically suffer from three limitations: 1)
they usually assume specific attack models, 2) they require
substantial modifications of learning algorithms, and 3) they commonly
suffer from significant scalability limitations.
For example, a recent, general, adversarial learning algorithm
proposed by Li and Vorobeychik~\cite{li2014feature} makes use of
constraint generation, but does not scale beyond 10-30 features.

Recently, retraining with adversarial data has been proposed as a means to increase
robustness of
learning~\cite{goodfellow2014explaining,Kantchelian15,teo2007convex}.\footnote{Indeed,
neither Teo et al.~\cite{teo2007convex} nor Kantchelian et
al.~\cite{Kantchelian15} focus on retraining as a main contribution,
but observe its effectiveness.}
However, to date such approaches have not been systematic.

We present a new algorithm, \emph{RAD}, for retraining with adversarial data
(Algorithm~\ref{algo:retraining}) which systematizes some of
the prior insights, and enables us to provide a formal connection
between retraining with adversarial data, and adversarial risk
minimization in the sense of Equation~\ref{E:advloss}.
%To capture adversarial evasions, we propose a robust learning algorithm $RobL$ which allows the learner to generate a set of ``adversarial strategy" $x'$ for each malicious instance $x^A$ and retrain the model with these new instances added until the convergence of loss function.
\begin{algorithm}[thb]
\caption{RAD: Retraining with ADversarial Examples}
\label{algo:retraining}
\begin{algorithmic}[1]
\STATE \textbf{Input}: {training data $X$}
\STATE $N_i \gets \emptyset \ \forall \ i \in I_{bad}$
\REPEAT
\STATE $\beta \gets$ Train($X \cup_i N_i$)
\STATE $new \gets \emptyset$
\FOR {$i \in I_{bad}$}
    \STATE $x'=\mathcal{O}(\beta,x_i)$
    \IF{$x' \notin N_i$}
      \STATE $new \gets new \cup x'$
    \ENDIF
    \STATE $N_i \gets N_i \cup x'$
  \ENDFOR
%\STATE $L \gets$ $Loss(\beta, X)$
%\ENDWHILE
\UNTIL{$new = \emptyset$}
\STATE \textbf{Output}: {Parameter vector $\beta$}
\end{algorithmic}
\end{algorithm}
The \emph{RAD} algorithm is quite general. 
At the high level, it starts with the original training data $X$ and
iterates between computing a classifier and adding adversarial
instances to the training data that evade the previously computed
classifier, if they are not already a part of the data.

A baseline termination condition for \emph{RAD} is that no new
adversarial instances can be added (either because instances generated
by $\mathcal{O}$ have already been previously added, or because the
adversary's can no longer benefit from evasion, as discussed more
formally in Section~\ref{s:game}).
%takes the training
%datasets and applies the adversarial models on it to generate
%attack strategies to retrain the model and improve its resilience.
%It is not difficult to
%see that, as described so far, the algorithm may never terminate if we include
%continuous features.
If the range of $\mathcal{O}$ is finite (e.g., if the feature space is
finite), \emph{RAD} with this termination condition would always terminate.
%\begin{proposition}
%Suppose that the range of $\mathcal{O}$ is finite.
%Then \emph{RAD} will terminate after a finite number of iterations.
%\end{proposition}
%The proof of this proposition is direct, and we provide it (along with
%other omitted proofs) in the Supplement.
%\begin{proof}
%Suppose Algorithm~\ref{algo:retraining} does not terminate after
%iteration $k$.
%Then $new \ne \emptyset$, and there is some $x \notin \mathcal{X}$
%which is added to the dataset.
%Since the range of $\mathcal{O}$ is finite, there must be some
%iteration where there is no $x$ that can be added which is not already
%in $\mathcal{X}$.
%Thus, $new = \emptyset$ in that iteration, and the algorithm terminates.
%\end{proof}
%A special case of this proposition is that the algorithm will always
%terminate if the feature space $X$ is finite.
In practice, our experiments demonstrate that when termination
conditions are satisfied, the number of \emph{RAD} iterations is quite
small (between 5 and 20).
Moreover, while \emph{RAD} effective increases the importance of malicious
instances in training, this does not appear to significantly harm
classification performance in a non-adversarial setting.
In general, we can also control the number of rounds directly, or use
an additional termination condition, such as that the parameter vector
$\beta$ changes little between successive iterations.
However, we assume henceforth that there is no fixed iteration limit or convergence check.

%In practice, to ensure that the algorithm always terminates, we can also impose a
%strict iteration limit, or check convergence (in terms of how much
%the parameter vector $\beta$ changes in successive iterations).
%In the remainder of the paper, however, we assume that there is no
%fixed iteration limit or convergence check.
To analyze what happens if the algorithm terminates, define the regularized empirical risk in the last
iteration of \emph{RAD} as:
\begin{equation}
\label{E:radloss}
\mathcal{L}^R_N(\beta, \mathcal{O}) = \sum_{i \in D \cup N} l(g_\beta(x_i),y_i) + \alpha ||\beta||_p^p,
\end{equation}
where a set $N = \cup_i N_i$ of data points has been added
by the algorithm (we omit its dependence on $\mathcal{O}$ to simplify
notation).
We now characterize the relationship between $\mathcal{L}^R_N(\beta, \mathcal{O})$
and $\mathcal{L}_A^*(\mathcal{O}) = \min_\beta \mathcal{L}_A(\beta,
\mathcal{O})$.
\begin{proposition}
\label{prop:defender_loss}
$\mathcal{L}_A^*(\mathcal{O}) \le \mathcal{L}^R_N(\beta, \mathcal{O})$
for all $\beta, \mathcal{O}$.
\end{proposition}
\begin{proof}
Let $\bar{\beta} \in \arg\min_{\beta}  \mathcal{L}^R_N(\beta,
\mathcal{O})$.
%Now, observe that in the last iteration of the algorithm, $new =
%\emptyset$ (since it must terminate after this iteration), which means
%that $\mathcal{O}(\beta,x_i) \in N_i$ for all $i \in I_{bad}$.
Consequently, for any $\beta$,
% (omitting regularization terms, since
% they are identical throughtout),
\begin{align*}
\mathcal{L}^R_N(\beta, \mathcal{O}) &\ge \mathcal{L}^R_N(\bar{\beta},
\mathcal{O})\\
&= \sum_{i: y_i = -1} l(g_{\bar{\beta}}(x_i),-1) +\sum_{i:y_i = +1} \sum_{j
  \in N_i \cup x_i} l(g_{\bar{\beta}} (x_i),+1) + \alpha ||\bar{\beta}||_p^p\\
&\ge \sum_{i: y_i = -1} l(g_{\bar{\beta}}(x_i),-1) +\sum_{i:y_i = +1}
l(g_{\bar{\beta}} (\mathcal{O}(\bar{\beta},x_i)),+1) + \alpha ||\bar{\beta}||_p^p\\
&\ge \min_\beta \mathcal{L}_A(\beta; \mathcal{O}) = \mathcal{L}_A^*(\mathcal{O}),
\end{align*}
where the second inequality follows because in the last iteration of the algorithm, $new =
\emptyset$ (since it must terminate after this iteration), which means
that $\mathcal{O}(\beta,x_i) \in N_i$ for all $i \in I_{bad}$.
\end{proof}
In words, retraining, systematized in the \emph{RAD} algorithm,
effectively minimizes an upper bound on optimal adversarial
risk.\footnote{Note that the bound relies on the fact that we are
  only adding adversarial instances, and terminate once no more
  instances can be added.  In particular, natural variations, such as
  removing or re-weighing added adversarial instances to retain original
  malicious-benign balance lose this guarantee.}
This offers a conceptual explanation for the previously observed
effectiveness of such algorithms in boosting robustness of learning to
adversarial evasion.
Formally, however, the result above is limited for several
reasons.
First, for many adversarial models in prior literature, adversarial
evasion is NP-Hard.
While some effective approaches exist to compute optimal evasion for specific
learning algorithms~\cite{Kantchelian15}, this is not true in general.
Although approximation algorithms for these models exist, using them
as oracles in \emph{RAD} is problematic, since actual attackers may
compute better solutions, and Proposition~\ref{prop:defender_loss} no
longer applies.
Second, we assume that $\mathcal{O}$ returns a unique result, but when
evasion is modeled as optimization, optima need not be unique.
Third, there do not exist effective general-purpose adversarial evasion
algorithms the use of which in \emph{RAD} would allow reasonable
theoretical guarantees.
Below, we investigate an important and very general class of
adversarial evasion models and associated algorithms which allow us to
obtain practically meaningful guarantees for \emph{RAD}.

%% TODO: experiments with clustering vs. non-clustered instances
%% (effectiveness, time)
\noindent{\bf Clustering Malicious Instances: }  A significant
enhancement in speed of the approach can be obtained by clustering
malicious instances: this would reduce both the number of iterations,
as well as the number of data points added per iteration. Experiments
(in the supplement) show that this is indeed quite effective.

\noindent{\bf Stochastic gradient descent: } \emph{RAD}
works particularly well with online methods, such as stochastic
gradient descent. Indeed, in this case we need only to make gradient
descent steps for newly added malicious instances, which can be added
one at a time until convergence.
multiclass.tex
% \subsection*{Multi-class classification}
\label{s:multiclass}

Discussion so far dealt entirely with binary classification.
We now observe that extending it to multi-class problems is quite direct.
Specifically, while previously the attacker aimed to make an instance classified as $+1$ (malicious) into a benign instance ($-1$), for a general label set $Y$, we can define a malicious set $M \subset Y$ and a target set $T \subset Y$, with $M \cap T = \emptyset$, where every entity represented by a feature vector $x$ with a label $y \in M$ aims to transform $x$ so that its label is changed to $T$.
In this setting, let $g(x) = \arg\max_{y \in Y} f(x,y)$.
We can then use the following empirical risk function:
\begin{equation}
\sum_{i : y_i \notin M} l( g_\beta(x_i),y_i) + \sum_{i:y_i \in M} l( g_\beta(\mathcal{O}(\beta,x_i)),y_i) + \lambda ||\beta||_p,
\end{equation}
where $\mathcal{O}$ aims to transform instances $x_i$ so that $g_\beta(\mathcal{O}(\beta,x_i)) \in T$.
The relaxed version of the adversarial problem can then be generalized to
\[
\min_{x,y \in T} -f(x,y) + c(x,x_i).
\]
For a finite target set $T$, this problem is equivalent to taking the best solution of a finite collection of problems identical to Problem 5.
% Problem~\ref{eq:attacker_q}.

\leaveout{

Multi-class classification problems are also interesting ones in practical, can these tasks can be decomposed into several binary classification tasks that can be solved efficiently using binary classifiers. Such decomposition can apply one-versus-all (OVA) strategy to reduce the problem of classifying among $M$ classes into $M$ binary problems, where each problem discriminated a given class from the other $M-1$ classes \cite{sejnowski1987parallel}. Alternatively,  each lass can also be compared to each other class via all-versus-all (AVA) strategy \cite{friedman1996another,hsu2002comparison}. In AVA, a binary classifier is built to discriminate between each pair of classes, while discarding the rest of the classes, which requires building $\frac{M(M-1)}{2}$ binary classifiers. 

Let $S$ denote the whole class space, where $ S = \{s_1, s_2, ...,s_k\}$ indicates the $i$th class. We use $p(s_i| x_i)$ to represent the posterior probability of the learner. For the adversarial instance $x^A$, whose class is $s_a$ $\left( p(s_a|x^A) > p(s_{i=1}^k|x^A) \right)$, attacker tries to generate $x'$ by modifying $x^A$ to deviate from the original class $s_a$. Here we apply $p(s_i|x_i)$ to represent the posterior probability of instance $x_i$ learned by the classifier. In OVA, the adversary is trying to solve the following problem.

\begin{equation}
\label{eq_R_avail}
\begin{aligned}
&\max \limits_{x',s_l \in S, l \ne a} p(s_l|x') \\
% s.t. \qquad &p(c_a|x^A) > p(c_{i=1}^k|x^A) \\
s.t. \qquad & c(x^A,x') \leq B
\end{aligned} 
\end{equation}

In AVA, the adversary needs to solve the optimization problem as below.

\begin{equation}
\label{eq_R_avail}
\begin{aligned}
&\max \limits_{x',s_i \in S \backslash s_a} \mathbbm{1}_{p(s_a|x') < p(s_i|x')} \\
% s.t. \qquad &p(c_a|x_i) > p(c_{i=1}^k|x_i) \\
s.t. \qquad & c(x^A,x') \leq B
\end{aligned} 
\end{equation}

Therefore, both of these cases can be reformulated similarly as the binary classification case as below.
\begin{equation}
\label{eq:attacker_multi}
\min \limits_{x'} Q(x') :=  p(s_a|x')+\exp \left({\lambda \sqrt{\sum \limits_{i = 1}^n{ (x^A}_i -{x'}_i)^2 +1}} \right)
\end{equation}

In this multi-class classification problem, assume there are two set of classes: malicious set (F) and target set (T). It is nature to assume that the two set of classes are not overlapped, since the adversaries usually try to evade the common detection class and modify their malicious instances to the closest benign classes. For example, a malware can be classified into a class containing various types of virus. However, the attacker only cares to modify such malware to evade the class of virus family to the other set of benign categories, such as compiler or business applications. These two set of classes are naturally not overlapped and the attacker does not really care which specific benign class the manipulated malware belongs to as long as it can evade the virus detection. 
Therefore the multi-class learning loss for defender in adversarial environments becomes

\begin{small}
\begin{equation}
\min \limits_{\beta} {L_{D_M}}^A := \sum \limits_{y_i \in T} l_\beta( x_i) + \sum \limits_{y_i \in F}  l_\beta( \widetilde{x_i}) + \lambda ||\beta||_p.
\end{equation}
\end{small}

\begin{proposition}
\label{prop:defender_loss_multi}
The upper bound of defender's loss for multi-class classification in adversarial environments is 
${L_D}^A \leq \sum \limits_{x_i \in X \cup R} l_\beta( x_i) + \alpha ||\beta||_p$ when $f(x)$ is convex and differentiable, where $X$ is the original training set and $R$ represents the total added instances.
\end{proposition}

\begin{proof}
This can be proved based Proposition~\ref{prop:defender_loss} by projecting the class set T as -1 and F as 1.
\end{proof}


% compare the retraining with bagging?
}
model.tex
\section{Learning and Evasion Attacks}

Let $X \subseteq R^n$ be the feature space, with $n$ the number of
features. For a feature vector $x_i \in X$, we let $x_{i_{j}}$ denote the
$j$th feature. Suppose that the training set $(x_i,y_i)$ is comprised of
feature vectors $x_i \in X$ generated according to some unknown
distribution $x_i \sim F$, with $y_i \in \{ -1,  +1\}$ the corresponding
binary labels, where $-1$ means the instance $x_i$ is benign, while $+1$
indicates a malicious instance. 
The learner aims to learn a classifier with parameters $\beta$,
$g_\beta: X \to \{-1, +1\}$, to label instances as malicious or
benign, using a training data set of labeled instance $D = \{(x_1, y_1),
..., (x_m, y_m)\}$. 
Let $I_{bad}$ be the subset of datapoints $i$ with $y_i = +1$.
We assume that $g_\beta(x) = \mathrm{sgn}(f_\beta(x))$ for some real-valued
function $f_\beta(x)$.

%Suppose every instance $x \sim D$ corresponds to a fixed label $y \in \{-1, +1\}$ and the label of $+1$ indicates that instance $x$ was generated by an adversary. To evade the classifier, adversary would generate an alternative instance $x' \in X$, for which $g(x') = -1$. However, the adversary still want to accomplish some goals. Therefore to evade detection, the adversary aims to modify the malicious instance $x^A$ to $x'$ by solving the following optimization problem:
% \begin{equation}
% \min \limits_{x' \in X:g(x')=-1} c(x',x^A), 
% \end{equation}
%where $c(x',x^A)$ is the cost function of modifying instance malicious instance $x^A$ to $x'$, which can be formulated as below.
%\begin{equation}
%c(x',x^A) = \alpha|x^A-x'|
%\end{equation}
%The $\alpha$ is vector that contains the weight factor $\alpha_i$ for each feature $x^{(i)}$ within the feature vector.

%%%% model evasion attacks as an evasion oracle

%%%% adversarial loss function

%\subsection{Attacker Model}

%\subsection{Defending Model}
% \subsection{Connections Between Constraint Generation and
% Retraining}

Traditionally, machine learning algorithms commonly minimize regularized empirical
risk:
\begin{equation}
\label{E:standardloss}
\min_\beta \mathcal{L}(\beta) \equiv \sum_i l(g_\beta(x_i),y_i) + \alpha \|\beta\|_p^p,
\end{equation}
where $l(\hat{y},y)$ is the loss associated with predicting $\hat{y}$
when true classification is $y$.
An important issue in adversarial settings is that instances
classified as malicious (in our convention, corresponding to
$g_\beta(x) = +1$) are associated with malicious agents who
subsequently modify such instances in order to evade the classifier
(and be classified as benign).
Suppose that adversarial evasion behavior is captured by an oracle,
$\mathcal{O}(\beta, x)$, which returns, for a given parameter vector
$\beta$ and original feature vector (in the training data) $x$, an
alternative feature vector $x'$.
Since the adversary modifies malicious instances according to this
oracle, the resulting effective risk for the defender is no longer
captured by Equation~\ref{E:standardloss}, but must account for
adversarial response.
Consequently, the defender would seek to minimize the following
\emph{adversarial risk} (on training data):
\begin{align}
\label{E:advloss}
\min_\beta \mathcal{L}_A(\beta; \mathcal{O}) = \sum_{i:y_i = -1}
l(g_\beta(x_i),-1)+ \sum_{i:y_i = +1} l(g_\beta(\mathcal{O}(\beta,x_i),+1) +\alpha \|\beta\|_p^p.
\end{align}
The adversarial risk function in Equation~\ref{E:advloss} is extremely
general: we make, at the moment, no assumptions on the nature of the
attacker oracle, $\mathcal{O}$.
This oracle may capture evasion attack models based on minimizing
evasion
cost~\cite{lowd2005adversarial,li2014feature,biggio2014security}, or
based on actual attacker evasion behavior obtained from experimental data~\cite{ke2016behavioral}.

\leaveout{
In traditional machine learning, the loss of learner can be calculated in general as
\begin{equation}
\label{eq:ld}
L_D = \sum \limits_{y_i = -1} l_\beta( x_i) + \sum \limits_{y_i = +1} l_\beta( x_i) + \alpha ||\beta||_p^p,
\end{equation}
where $l_\beta(\cdot)$ is the loss function for predicting $g: x_i \to y_i$ given the model parameter $\beta$.
However, within evasion attacks, the adversary injects the data variances during the testing time. Therefore the defender needs to minimize the loss considering adversarial evasion behaviors ${L_D}^A$, and therefore solve the problem by the robust version of the learning problem as below.
\begin{equation}
\begin{small}
\begin{aligned}
\label{eq:ld}
\min \limits_{w} {L_D}^A &:= \sum \limits_{y_i = -1} l_\beta( x_i) + \sum \limits_{y_i = +1} l_\beta(\widetilde{x_i}) + \alpha ||\beta||_p \\
s.t.: \qquad & \forall i: y_i = 1 \\
&z_i = \arg\min \limits_{x|w^T x \leq 0} c(x,x_i) \\
& \widetilde{x_i} = 
\begin{cases}
&z_i,\  c(z_i,x_i) \leq B \\
&x_i, \  \text{otherwise}
\end{cases}
\end{aligned}
\end{small}
\end{equation}
}

%The problem~\ref{E:advloss} can be solved by mixed integer programming algorithm based on constraint generation \cite{li2014feature}. 
%A constraint generation based method SMA has been employed to design the robust learning system against evasion attacks.

% check the proposition 
% \begin{proposition} 
% \label{defender_obj1}
% The loss of defender satisfies\\
% $\forall {x_i}_j \in {x_i}^*$,
% \begin{equation}
% \begin{aligned}
% \label{eq:loss}
% L_D = &\sum \limits_{y_i = -1} l(-w^T x_i) + \sum \limits_{y_i = +1} l(w^T x_i) + \lambda ||w||_p \\
% % \end{equation*}
% % \begin{equation*}
% % \label{eq:constraint}
% \leq & \sum \limits_{y_i = -1} l(-w^T x_i) + \sum \limits_{y_i = +1} l(w^T {x_i}_j) + \lambda ||w||_p 
% \end{aligned}
% \end{equation}
% ${x_i}^*$ is the set of constraints of $x_i$.
% \end{proposition}


% \begin{proposition}
% \label{defender_obj2}
% Among the constraints set ${x_i}^*$, the upper bound of defender's loss is 
% % $L_D \leq \sum \limits_{y_i = -1} l(-w^T x_i) + \sum \limits_{y_i = +1} \max \limits_{{x_i}' \in {x_i}^*} l(w^T {x_i}') + \lambda ||w||_p $.
% $\sum \limits_{y_i = +1} \max \limits_{{x_i}' \in {x_i}^*} l(w^T {x_i}') + \lambda ||w||_p$.
% \end{proposition}

% \begin{proof}
% From Proposition~\ref{defender_obj1}, 
% $\forall {x_i}_j \in {x_i}^*$,
% \begin{equation}
% \begin{aligned}
% \label{eq:retrain}
% & L_D \leq \sum \limits_{y_i = -1} l(-w^T x_i) + \sum \limits_{y_i = +1} l(w^T {x_i}_j) + \lambda ||w||_p \\
% \leq & \sum \limits_{y_i = -1} l(-w^T x_i) + \sum \limits_{y_i = +1} \max \limits_{{x_i}' \in {x_i}^*} l(w^T {x_i}') + \lambda ||w||_p 
% \end{aligned}
% \end{equation}

% \end{proof}



%\subsection{The Game}
%\label{s:game}





intro.tex
Machine learning has been used ubiquitously for a wide variety of security tasks, such as intrusion detection, malware detection, spam filtering, and web search~\cite{fawcett1997adaptive,mahoney2002learning,fogla2006polymorphic,huang2011adversarial,kolcz2009feature}. 
Traditional machine learning systems, however, do not account for adversarial manipulation.
For example, in spam detection, spammers commonly change spam email text to evade filtering.
%The stationary assumption for the underlying data distribution of traditional machine learning can be easily violated in adversarial environments. 
%Taking advantage of such weakness of traditional machine learning systems, adversaries have expended much effort exploiting attack vectors to counteract learning systems and therefore realize malicious goals \cite{biggio2014security}. For example, evasion attacks have been applied to modify the malicious data during testing to circumvent anomaly detections; poisoning attacks inject poisonous data during training to induce a misclassification of benign/malicious data among other tactics. 
As a consequence, there have been a series of efforts to both model adversarial manipulation of learning, such as evasion and data poisoning attacks~\cite{lowd2005adversarial,karlberger2007exploiting,nelson2012query}, as well as detecting such attacks~\cite{mahoney2002learning,el2003robust} or enhancing robustness of learning algorithms to these~\cite{li2014feature,li2015scalable,teo2007convex,globerson2006nightmare,bruckner2011stackelberg}.
One of the most general of these, due to Li and Vorobeychik~\cite{li2014feature}, admits evasion attacks modeled through a broad class of optimization problems, giving rise to a Stackelberg game, in which the learner minimizes an adversarial risk function which accounts for optimal attacks on the learner.
The main limitation of this approach, however, is scalability: it can solve instances with only 10-30 features.
Indeed, most approaches to date also offer solutions that build on specific learning models or algorithms.
For example, specific evasion attacks have been developed for linear or convex-inducing classifiers~\cite{lowd2005adversarial,karlberger2007exploiting,nelson2012query}, as well as neural networks for continuous feature spaces~\cite{biggio2014security}.
Similarly, robust algorithms have typically involved non-trivial modifications of underlying learning algorithms, and either assume a specific attack model or modify a specific algorithm.
The more general algorithms that admit a wide array of attack models, on the other hand, have poor scalability.

We propose a very general retraining framework, \emph{RAD}, which can boost evasion robustness of arbitrary learning algorithms using arbitrary evasion attack models.
We show that \emph{RAD} minimizes an upper bound on optimal adversarial risk.
This is significant: whereas adversarial risk minimization is a hard bi-level optimization problem and poor scalability properties (indeed, no methods exist to solve it for general attack models), \emph{RAD} itself is extremely scalable in practice, as our experiments show.
We develop \emph{RAD} for a more specific, but very broad class of adversarial models, offering a theoretical connection to adversarial risk minimization even when the adversarial model is only approximate.
In the process, we offer a simple and very general class of local search algorithms for approximating evasion attacks, which are experimentally quite effective.
Perhaps the most appealing aspect of the proposed approach is that \emph{it requires no modification of learning algorithms}: rather, it can wrap any learning algorithm ``out-of-the-box''.
Our work connects to, and systematizes, several previous approaches which used training with adversarial examples to either evaluate robustness of learning algorithms, or enhance learning robustness.
For example, Goodfellow et al.~\cite{goodfellow2014explaining} and Kantchelian et al.~\cite{Kantchelian15} make use of adversarial examples.
In the former case, however, these were essentially randomly chosen.
The latter offered an iterative retraining approach more in the spirit of \emph{RAD}, but did not systematically develop or analyze it.
Teo et al.~\cite{teo2007convex} do not make an explicit connection to retraining, but suggest equivalence between their general invariance-based approach using column generation and retraining.
However, the two are not equivalent, and Teo et al. did not study their relationship formally.

%Targeting on the evasion attack issues, security engineering and cryptography methods have also been adapted recently \cite{mahoney2002learning,el2003robust}. 
%However, these usually require the secure system designer to know the potential vulnerabilities of the system before they are exploit to the adversary, which makes it impossible facing the various intelligent adversaries.
%To adaptively and automatically learn for the dynamic data distribution against evasion attacks, usually two approaches are implied.
%First the min-max approach assumes the learner and attacker's loss functions are antagonistic, which yields relatively simple optimization problems \cite{dekel2010learning,globerson2006nightmare}.
%A more general game-theoretic approach applies for non-antagonistic losses is also applied.
%Such problems can be solved using a Nash equilibrium approach restricted to certain conditions \cite{bruckner2011stackelberg,bruckner2012static}.
%It has been shown that formulating the interaction between the learner and attacker as games can more naturally capture the properties of attackers' strategies. Linear and convex-including classification problems have been addressed against evasion attacks \cite{lowd2005adversarial,karlberger2007exploiting,nelson2012query}. Additionally, within the game theoretic analysis, mixed-integer programming based on constraint generation is applied to solve the game given the realistic complex and large amount of adversarial strategies (constraints) \cite{li2014feature,li2015scalable,teo2007convex}.
%However, mixed-integer programming approaches solving such optimization games is not scalable or efficient enough when big data classification is involved. Therefore, we investigate the coordinate descent algorithm to generate adversarial strategies in parallel restricted to the adversarial objective, and iteratively add these surrogate instances into the training process to minimize the loss of learner. 
%Our goal in this work is to develop a computationally scalable and broadly applicable approach to supervised learning against evasion attacks, which is easily adapted to new types of problems. 
%In this paper we propose a scalable secure learning method with proved upper bound for the loss of learning with adversarial instances. Our proposed method has the following properties. 
In summary, we make the following contributions:
\begin{enumerate}
\item \emph{RAD}, a novel systematic framework for adversarial retraining,
\item analysis of the relationship between \emph{RAD} and empirical adversarial risk minimization,
\item extension of the analysis to account for approximate adversarial evasion, within a specific broad class of adversarial models,
\item extensive experimental evaluation of \emph{RAD} and the adversarial evasion model.
%\item It formulates the intractable adversarial constrained bi-level problem as a single adversarial objective optimization problem, which can be solved by coordinate descent algorithm.
%\item It can deal with arbitrary instances with binary or continuous feature space with convergence guarantee.
%\item It deal with arbitrary learning models, including Naive Bayesian, regression models, SVM, neural network, and multi-class classifiers.
%\item It guarantees the secure learning given various adversarial evasion strategies with bounded learning loss.
\end{enumerate}
We illustrate the applicability and efficiency of our method on both spam filtering and handwritten digit recognition tasks, where evasion attacks are extremely salient~\cite{klimt2004enron,lecun2010mnist}. 
icml2016_paper.tex
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%% ICML 2015 EXAMPLE LATEX SUBMISSION FILE %%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Use the following line _only_ if you're still using LaTeX 2.09.
%\documentstyle[icml2015,epsf,natbib]{article}
% If you rely on Latex2e packages, like most moden people use this:
\documentclass{article}

% use Times
\usepackage{times}
% For figures
\usepackage{graphicx} % more modern
%\usepackage{epsfig} % less modern
\usepackage{subfigure} 

% For citations
\usepackage{natbib}

% For algorithms
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{amsmath,amsfonts,amsthm,amssymb,bbm}
\usepackage{float}

% As of 2011, we use the hyperref package to produce hyperlinks in the
% resulting PDF.  If this breaks your system, please commend out the
% following usepackage line and replace \usepackage{icml2015} with
% \usepackage[nohyperref]{icml2015} above.
\usepackage{hyperref}

% Packages hyperref and algorithmic misbehave sometimes.  We can fix
% this with the following command.
\newcommand{\theHalgorithm}{\arabic{algorithm}}

% Employ the following version of the ``usepackage'' statement for
% submitting the draft version of the paper for review.  This will set
% the note in the first column to ``Under review.  Do not distribute.''
\usepackage{icml2015} 

% Employ this version of the ``usepackage'' statement after the paper has
% been accepted, when creating the final version.  This will set the
% note in the first column to ``Proceedings of the...''
%\usepackage[accepted]{icml2015}

\newtheorem{defn}{Definition}[section]
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{example}{Example}[section]
\newtheorem{lemma}{Lemma}[section]

\allowdisplaybreaks

\newcommand{\leaveout}[1]{}

% The \icmltitle you define below is probably too long as a header.
% Therefore, a short form for the running title is supplied here:
\icmltitlerunning{Iterative secure learning in adversarial environments}

\begin{document} 

\twocolumn[
\icmltitle{Iterative secure learning in adversarial environments}

% It is OKAY to include author information, even for blind
% submissions: the style file will automatically remove it for you
% unless you've provided the [accepted] option to the icml2015
% package.
\icmlauthor{Your Name}{email@yourdomain.edu}
\icmladdress{Your Fantastic Institute,
            314159 Pi St., Palo Alto, CA 94306 USA}
\icmlauthor{Your CoAuthor's Name}{email@coauthordomain.edu}
\icmladdress{Their Fantastic Institute,
            27182 Exp St., Toronto, ON M6H 2T1 CANADA}

% You may provide any keywords that you 
% find helpful for describing your paper; these are used to populate 
% the "keywords" metadata in the PDF but will not be shown in the document
\icmlkeywords{scalable, robust, adversarial learning}

\vskip 0.3in
]

\begin{abstract} 
Traditional machine learning is vulnerable against deliberate attacks given the fact that the risk minimization process of learner is built on the stationary assumption for training and testing data distribution. It has been shown that malicious adversaries can conduct either poisoning or evasion attack via modifying the training/testing data. To analyze the adversarial behaviors in evasion attacks for different learning models, we first provide a general framework for generating adversarial instances for a wide variety of classifiers, including SVM, Bayesian regression, Ridge regression, and neural networks with different hidden layers for comparison purpose.
We then form the interaction between learner and attacker as a Stackelberg game and 
propose a scalable learning approach against the adversarially generated evasion instances. We also prove the upper bound for the learner's loss for this approach. 
We show that the proposed learning algorithm can make robust predictions via retraining process for various learning models on adversarially optimized instances.
Intensive experiments on multiple datasets have demonstrated that robust prediction 
can be achieved by shifting the training distribution accordingly. 
\end{abstract} 

\section{Introduction}
\input{sections_paper/intro}

\input{sections_paper/model}
\input{sections_paper/retraining}
\input{sections_paper/attacks}
\input{sections_paper/multiclass}

\section{Experimental Results}
\input{sections_paper/exp}

\section{Conclusions and future work}
\input{sections_paper/conclusion}


% \begin{figure}[ht]
% \vskip 0.2in
% \begin{center}
% \centerline{\includegraphics[width=\columnwidth]{icml_numpapers}}
% \caption{Historical locations and number of accepted papers for International
%   Machine Learning Conferences (ICML 1993 -- ICML 2008) and
%   International Workshops on Machine Learning (ML 1988 -- ML
%   1992). At the time this figure was produced, the number of
%   accepted papers for ICML 2008 was unknown and instead estimated.}
% \label{icml-historical}
% \end{center}
% \vskip -0.2in
% \end{figure} 



% Acknowledgements should only appear in the accepted version. 
% \section*{Acknowledgments} 
 


% In the unusual situation where you want a paper to appear in the
% references without citing it in the main text, use \nocite
% \nocite{langley00}
% \clearpage
\bibliography{rev}
\bibliographystyle{icml2015}

\end{document} 


% This document was modified from the file originally made available by
% Pat Langley and Andrea Danyluk for ICML-2K. This version was
% created by Lise Getoor and Tobias Scheffer, it was slightly modified  
% from the 2010 version by Thorsten Joachims & Johannes Fuernkranz, 
% slightly modified from the 2009 version by Kiri Wagstaff and 
% Sam Roweis's 2008 version, which is slightly modified from 
% Prasad Tadepalli's 2007 version which is a lightly 
% changed version of the previous year's version by Andrew Moore, 
% which was in turn edited from those of Kristian Kersting and 
% Codrina Lauth. Alex Smola contributed to the algorithmic style files.  

exp.tex

The results above suggest that the proposed systematic retraining
algorithm is likely to be effective at increasing resilience to
adversarial evasion.
We now offer an experimental evaluation of this (additional results
are provided in the supplement).
We present the results for the exponential cost model, where $c(x,x_i) = \exp \left(\lambda (\sum_j (x_j -x_{ij})^2 +1)^{1/2}
\right)$.
Additionally, we simulated attacks using Problem~\ref{eq:attacker_q} formulation.
Results for other cost functions and attack models are similar, as
shown in the supplement.
Moreover, the supplement demonstrates that the approach is robust to
cost function misspecification.

%Throughout, we make use of the exponential cost model for the attacker
%described above to illustrate the efficiency, where $\lambda$ is a parameter which determines the
%relative importance of the cost term. We also evaluate other variations of the cost
%functions to show that the framework is not sensitive to the choices of cost functions.
%In particular, a high $\lambda$ implies a higher penalty for changing
%the malicious feature vector, and, consequently, weaker attacks.
%Additionally, we simulated attacks using Problem~\ref{eq:attacker_q} formulation.


%In this section, we evaluate the efficiency of our proposed method as
%well as the vulnerability of various learning models based on
%different adversarial cost sensitivity.

\noindent{\bf Comparison to Optimal: }
The first comparison we draw is to a recent algorithm, \emph{SMA},
which minimizes $l_1$-regularized adversarial risk function~\eqref{E:advloss} using
the hinge loss function.
Specifically, \emph{SMA} formulates the problem as a large mixed-integer
linear program which it solves using constraint
generation~\cite{li2014feature}.
The main limitation of SMA is scalability.
Because retraining methods use out-of-the-box learning tools and does
not involve non-convex bi-level optimization, it is
considerably more scalable.
\begin{figure}[H]
\centering
\begin{tabular}{cc}
\includegraphics[width=1.45in,height=1.19in]{images/sma_compare.png} &
\includegraphics[scale=0.193]{images/runtime_com.png} \\
(a) & (b)
%\includegraphics[scale=0.12]{images/q30fea30.png} \\
\end{tabular}
\caption{Comparison between \emph{RAD} and \emph{SMA} based on the Enron dataset with 30 binary features. (a) The $F_1$ score of different algorithms corresponding to various $\lambda$; (b) the average runtime for each algorithm.}
\label{f:sma_compare}
\end{figure} 

We compared \emph{SMA} and \emph{RAD} using
Enron data~\cite{klimt2004enron}. 
% since \emph{SMA} was also developed for the constrained-optimization attacks (Problem~\eqref{E:constrainedAttacks}).
As Figure~\ref{f:sma_compare}(a) demonstrates, retraining solutions of \emph{RAD} are
nearly as good as \emph{SMA}, particularly for a non-trivial adversarial cost sensitive $\lambda$.
In contrast, a baseline implementation of SVM is significantly more
fragile to evasion attacks. However, the runtime comparison for these
algorithms in Figure~\ref{f:sma_compare}(b) shows that \emph{RAD} is
much more scalable than \emph{SMA}.
\leaveout{
In addition, Figure~\ref{f:sma_compare}(a) also reveals a surprising phenomenon observed by
Kantchelian et al.~\cite{Kantchelian15} as well: performance
actually improves based on certain adversarial cost sensitivity compared with adversary-free case where high $\lambda$ value is applied.
What this shows is that adding certain adversarial instances actually improves
classification robustness to non-adversarial data as well, likely
because it makes the learner significantly more robust to noise in the
data. 
}

%Below, we evaluate the effectiveness of retraining in
%boosting robustness of learning to evasion.
% Throughout, we make use of the exponential cost model for the attacker
% described above, where $\lambda$ is a parameter which determines the
% relative importance of the cost term.
% In particular, a high $\lambda$ implies a higher penalty for changing
% the malicious feature vector, and, consequently, weaker attacks.
% Throughout, we simulated attacks using Problem~\ref{eq:attacker_q} formulation.


\noindent{\bf Effectiveness of Retraining: }
%\subsection{Continuous Feature Space}
In this section we use the Enron dataset~\cite{klimt2004enron} and
MNIST~\cite{lecun2010mnist} dataset to evaluate the robustness of
three common algorithms in their standard implementation, and in
\emph{RAD}: logistic
regression, SVM (using a linear kernel), and a neural network (NN)
with 3 hidden layers.
In Enron data, features correspond to relative word frequencies.
2000 features were
used for the Enron and 784 for MNIST datasets.
Throughout, we use precision, recall, and accuracy as metrics.
% for the ridge regression, Bayesian regression, svm with linear
% kernel, and neural network with 1 and 3 hidden layers to evaluate
% the efficiency of restraining strategy.
We present the results for a continuous feature space here.
Results for binary features are similar and provided in the supplement.

\begin{figure*}[t]
\centering 
\begin{tabular}{cccc}
\includegraphics[scale=0.193]{images/logistic_enron_con2000.png} &
\includegraphics[scale=0.193]{images/svm_enron2000.png} &
% \includegraphics[scale=0.193]{images/nn1_enron2000_con.png} &
\includegraphics[scale=0.193]{images/nn3_enron_continu2000.png} \\
\includegraphics[scale=0.193]{images/logistic_mnist784.png} &
\includegraphics[scale=0.193]{images/svm_mnist784.png} &
% \includegraphics[scale=0.193]{images/nn1_mnist_784.png} &
\includegraphics[scale=0.193]{images/nn3_mnist_784.png}\\
(a) & (b) & (c) 
\end{tabular}
\caption{Performance of baseline (\emph{adv-}) and \emph{RAD} (\emph{rob-}) as a function of cost
  sensitivity $\lambda$ for Enron (top) and MNIST (bottom) datasets with continuous features testing on adversarial instances. (a)
  logistic regression, (b) SVM, (c) 3-layer NN.}
\label{fig:log_con}
\end{figure*}

% results for clean test data--continuous feature
\begin{figure*}[t]
\centering 
\begin{tabular}{ccc}
\includegraphics[scale=0.193]{images/cleantest/cleantest_mnist_logistic.png} &
\includegraphics[scale=0.193]{images/cleantest/cleantest_mnist_svm.png} &
% \includegraphics[scale=0.193]{images/cleantest/cleantest_mnist_nn1.png} &
\includegraphics[scale=0.193]{images/cleantest/cleantest_mnist_nn3.png} \\
(a) & (b) & (c)
\end{tabular}
\caption{Performance of baseline (\emph{adv-}) and \emph{RAD} (\emph{rob-}) as a function of cost
sensitivity $\lambda$ for MNIST dataset with continuous features testing on non-adversarial instances. (a) logistic regression, (b) SVM, (c) 3-layer NN.}
\label{fig:cleantest_con}
\end{figure*}

Figure~\ref{fig:log_con}(a) shows the performance of logistic regression,
with and without retraining, on Enron and MNIST.
The increased robustness of \emph{RAD} is immediately evident:
performance of \emph{RAD} is essentially independent of $\lambda$ on
all three measures, and substantially exceeds baseline algorithm
performance for small $\lambda$.
Interestingly, we observe that the baseline algorithms
are significantly more fragile to evasion attacks on Enron data
compard to MNIST: benign and malicious classes seem far easier to
separate on the latter than the former.
This qualitative comparison between the Enron and MNIST datasets is
consistent for other classification methods as well (SVM, NN).
These results also illustrate that the neural-network classifiers, in their baseline implementation, are
significantly more robust to evasion attacks than the (generalized) linear
classifiers (logistic regression and SVM): even with a relatively
small attack cost attacks become ineffective relatively quickly, and
the differences between the performance on Enron and MNIST data are
far smaller.
Throughout, however, \emph{RAD} significantly improves robustness to
evasion, maintaining extremely high accuracy, precision, and recall
essentially independently of $\lambda$, dataset, and algorithm used.

In order to explore whether \emph{RAD} would sacrifice accuracy
when no adversary is present, Figure~\ref{fig:cleantest_con} shows the performance of the
baseline algorithms and \emph{RAD} on a test dataset sans
evasions. Surprisingly, \emph{RAD} is never significantly worse, and
in some cases better than non-adversarial baselines: adding malicious instances appears to increase overall generalization ability.
This is also consistent with the observation by Kantchelian et al.~\cite{Kantchelian15}.

\noindent{\bf Oracles based on Human Evasion Behavior: }
To evaluate the considerable generality of \emph{RAD}, we now use a
non-optimization-based threat model, making use instead
%Our final set of experiments evaluate \emph{RAD} just for the SVM
%classifier in the context 
of observed human evasion behavior \emph{in human subject experiments}.
The data for this evaluation was obtained from the human subject
experiment by Ke et al.~\cite{ke2016behavioral} in which subjects were
tasked with the goal of evading an SVM-based spam filter, manipulating
10 spam/phishing email instances in the process.
In these experiments, Ke et al. used machine learning to develop a
model of human subject evasion behavior.
We now adopt this model as the evasion oracle, $\mathcal{O}$, injected
in our \emph{RAD} retraining framework, executing the synthetic model
for 0-10 iterations to obtain evasion examples.

Figure~\ref{fig:behavior}(a) shows the recall results for the dataset of
10 malicious emails (the classifiers are trained on Enron data, but
evaluated on these 10 emails, including evasion
attacks). Figure~\ref{fig:behavior}(b) shows the classifier performance for the Enron dataset by applying the synthetic adversarial model as the oracle.
% human behavior data
\begin{figure}[h]
\centering 
\begin{tabular}{cc}
%\includegraphics[scale=0.19]{images/behavior/sub10.png} &
\includegraphics[scale=0.193]{images/behavior/sub20.png} &
\includegraphics[scale=0.193]{images/behavior/behavior_oracle20.png}\\
(a) & (b)
\end{tabular}
\caption{\emph{RAD} (\emph{rob-}) and baseline SVM (\emph{adv-}) performance based on human subject behavior
  data over 20 queries, (a) using experimental data with actual human
  subject experiment submissions, (b) using Enron data and a synthetic
  model of human evader.}
\label{fig:behavior}
\end{figure}
We can make two high-level observations.
First, notice that human adversaries appear significantly less
powerful in evading the classifier than the automated
optimization-based attacks we previously considered.
This is a testament to both the effectiveness of our general-purpose adversarial
evaluation approach, and the likelihood that such automated attacks
likely significantly overestimate adversarial evasion risk in many
settings.
Nevertheless, we can observe that the synthetic model used in
\emph{RAD} leads to a significantly more robust classifier.
Moreover, as our evaluation used actual evasions, while the synthetic
model was used only in training the classifier as a part of
\emph{RAD}, this experiment suggests that the synthetic model can be
relatively effective in modeling behavior of human adversaries.
Figure~\ref{fig:behavior}(b) performs a more systematic study
using the synthetic model of adversarial behavior on the Enron dataset.
The findings are consistent with those only considering the 10 spam
instances: retraining significantly boosts robustness to evasion, with
classifier effectiveness essentially independent of the number of
queries made by the oracle.
\leaveout{
\begin{figure}[h]
\centering 
\begin{tabular}{cc}
\includegraphics[scale=0.19]{images/behavior/behavior_oracle10.png} &
\includegraphics[scale=0.19]{images/behavior/behavior_oracle20.png} \\
(a) & (b)
\end{tabular}
\caption{Robust retraining performance using synthetic model as adversarial oracle for both RAD and testing evasion data for (a) 10 submissions, (b) 20 submissions.}
\label{fig:behavior_bothoracle}
\end{figure}
}


\leaveout{
% svm-linear results for enron
\begin{figure}[H]
\centering 
\begin{tabular}{cc}
%\includegraphics[scale=0.19]{images/svm_enron1000.png} &
\includegraphics[scale=0.19]{images/svm_enron2000.png} &
\includegraphics[scale=0.19]{images/svm_mnist784.png} \\
(a) & (b)
\end{tabular}
\caption{SVM performance based on different adversarial cost sensitivity $\lambda$ for Enron dataset with different number of features as (a) 1000, (b) 2000.}
\label{fig:svm_enron}
\end{figure}

% svm-linear results for mnist
% chenge below
\begin{figure}[H]
\centering 
\begin{tabular}{cc}
%\includegraphics[scale=0.19]{images/svm_mnist627.png} &
\includegraphics[scale=0.19]{images/svm_mnist784.png} \\
(a) & (b)
\end{tabular}
\caption{SVM performance based on different adversarial cost sensitivity $\lambda$ for MNIST dataset with different number of features as (a) 627, (b) 784.}
\label{fig:svm_mnist}
\end{figure}
}

\leaveout{
% nn1 results for enron
\begin{figure}[H]
\centering 
\begin{tabular}{cc}
\includegraphics[scale=0.19]{images/nn1_enron1000_con.png} &
\includegraphics[scale=0.19]{images/nn1_enron2000_con.png} \\
(a) & (b)
\end{tabular}
\caption{Neural network with 1 hidden layers performance based on different adversarial cost sensitivity $\lambda$ for Enron dataset with different number of features as (a) 1000, (b) 2000.}
\label{fig:nn1_enron_continu}
\end{figure}

% nn1 results for mnist
\begin{figure}[H]
\centering 
\begin{tabular}{cc}
\includegraphics[scale=0.19]{images/nn1_mnist_627.png} &
\includegraphics[scale=0.19]{images/nn1_mnist_784.png} \\
(a) & (b)
\end{tabular}
\caption{Neural network with 1 hidden layers performance based on different adversarial cost sensitivity $\lambda$ for MNIST dataset with different number of features as (a) 627, (b) 784.}
\label{fig:nn1_mnist_continu}
\end{figure}
}

\leaveout{
% nn3 results for enron
\begin{figure}[H]
\centering 
\begin{tabular}{cc}
\includegraphics[scale=0.19]{images/nn3_enron_continu1000.png} &
\includegraphics[scale=0.19]{images/nn3_enron_continu2000.png} \\
(a) & (b)
\end{tabular}
\caption{Neural network with 3 hidden layers performance based on different adversarial cost sensitivity $\lambda$ for Enron dataset with different number of features as (a) 1000, (b) 2000.}
\label{fig:nn3_enron_continu}
\end{figure}
 
% nn3 results for mnist

\begin{figure}[H]
\centering 
\begin{tabular}{cc}
\includegraphics[scale=0.19]{images/nn3_mnist_627.png} &
\includegraphics[scale=0.19]{images/nn3_mnist_784.png} \\
(a) & (b)
\end{tabular}
\caption{Neural network with 3 hidden layers performance based on different adversarial cost sensitivity $\lambda$ for MNIST dataset with different number of features as (a) 627, (b) 784.}
\label{fig:nn3_mnist_continu}
\end{figure}
}


\leaveout{

\begin{figure}[H]
\centering 
\begin{tabular}{cccc}
\includegraphics[scale=1.00]{images/logistic/0.png} &
\includegraphics[scale=1.00]{images/logistic/1.png} &
\includegraphics[scale=1.00]{images/logistic/3.png} &
\includegraphics[scale=1.00]{images/logistic/4.png} \\
\includegraphics[scale=1.00]{images/logistic/6.png} &
\includegraphics[scale=1.00]{images/logistic/7.png} &
\includegraphics[scale=1.00]{images/logistic/8.png} &
\includegraphics[scale=1.00]{images/logistic/9.png} \\
\end{tabular}
\caption{Modification process of attacker for Logistic regression based by decreasing the cost sensitivity parameter $\lambda$.}
\label{fig:visual_logistic}
\end{figure}



\begin{figure}[H]
\centering 
\begin{tabular}{cccc}
\includegraphics[scale=1.00]{images/svm/0.png} &
\includegraphics[scale=1.00]{images/svm/1.png} &
\includegraphics[scale=1.00]{images/svm/3.png} &
\includegraphics[scale=1.00]{images/svm/4.png} \\
\includegraphics[scale=1.00]{images/svm/5.png} &
\includegraphics[scale=1.00]{images/svm/6.png} &
\includegraphics[scale=1.00]{images/svm/7.png} &
\includegraphics[scale=1.00]{images/svm/8.png} \\
\end{tabular}
\caption{Modification process of attacker for SVM based by decreasing the cost sensitivity parameter $\lambda$.}
\label{fig:visual_svm}
\end{figure}

\begin{figure}[H]
\centering 
\begin{tabular}{cccc}
\includegraphics[scale=1.00]{images/nn1/0.png} &
\includegraphics[scale=1.00]{images/nn1/1.png} &
\includegraphics[scale=1.00]{images/nn1/3.png} &
\includegraphics[scale=1.00]{images/nn1/4.png} \\
\includegraphics[scale=1.00]{images/nn1/6.png} &
\includegraphics[scale=1.00]{images/nn1/8.png} &
\includegraphics[scale=1.00]{images/nn1/9.png} &
\includegraphics[scale=1.00]{images/nn1/10.png} \\
\end{tabular}
\caption{Modification process of attacker for Neural Network with 1 hidden layer based by decreasing the cost sensitivity parameter $\lambda$.}
\label{fig:visual_nn1}
\end{figure}


\begin{figure}[H]
\centering 
\begin{tabular}{cccc}
\includegraphics[scale=1.00]{images/nn3/0.png} &
\includegraphics[scale=1.00]{images/nn3/1.png} &
\includegraphics[scale=1.00]{images/nn3/3.png} &
\includegraphics[scale=1.00]{images/nn3/4.png} \\
\includegraphics[scale=1.00]{images/nn3/7.png} &
\includegraphics[scale=1.00]{images/nn3/6.png} &
\includegraphics[scale=1.00]{images/nn3/9.png} &
\includegraphics[scale=1.00]{images/nn3/10.png} \\
\end{tabular}
\caption{Modification process of attacker for Neural Network with 3 hidden layers based by decreasing the cost sensitivity parameter $\lambda$.}
\label{fig:visual_nn3}
\end{figure}
}

\leaveout{
% nb results for enron based on model 2
\begin{figure}[H]
\centering 
\begin{tabular}{cc}
\includegraphics[scale=0.19]{images/nb_model2_1000.png} &
\includegraphics[scale=0.19]{images/nb_model2_2000.png} \\
(a) & (b)
\end{tabular}
\caption{Naive Bayesian performance based on different adversarial cost sensitivity $\lambda$ for Enron dataset with different number of binary features as (a) 1000, (b) 2000.}
\label{fig:nb_enron_binary}
\end{figure}

% logistic results for enron based on model 2
\begin{figure}[H]
\centering 
\begin{tabular}{cc}
\includegraphics[scale=0.19]{images/logistic_binary1000.png} &
\includegraphics[scale=0.19]{images/logistic_binary2000.png} \\
(a) & (b)
\end{tabular}
\caption{Logistic regression performance based on different adversarial cost sensitivity $\lambda$ for Enron dataset with different number of binary features as (a) 1000, (b) 2000.}
\label{fig:log_enron_binary}
\end{figure}

% svm linear results for enron based on model 2
\begin{figure}[H]
\centering 
\begin{tabular}{cc}
\includegraphics[scale=0.19]{images/binary2_enron_svm1000.png} &
\includegraphics[scale=0.19]{images/binary2_enron_svm2000.png} \\
(a) & (b)
\end{tabular}
\caption{SVM linear performance based on different adversarial cost sensitivity $\lambda$ for Enron dataset with different number of binary features as (a) 1000, (b) 2000.}
\label{fig:svm_enron_binary}
\end{figure}

% nn-1 results for enron based on model 2
\begin{figure}[H]
\centering 
\begin{tabular}{cc}
\includegraphics[scale=0.19]{images/nn1_enron_model2_1000.png} &
\includegraphics[scale=0.19]{images/nn1_enron_model2_2000.png} \\
(a) & (b)
\end{tabular}
\caption{Neural network with 1 hidden layer performance based on different adversarial cost sensitivity $\lambda$ for Enron dataset with different number of binary features as (a) 1000, (b) 2000.}
\label{fig:nn1_enron_binary}
\end{figure}

% nn-3 results for enron based on model 2
\begin{figure}[H]
\centering 
\begin{tabular}{cc}
\includegraphics[scale=0.19]{images/nn3_enron_model2_1000.png} &
\includegraphics[scale=0.19]{images/nn3_enron_model2_2000.png} \\
(a) & (b)
\end{tabular}
\caption{Neural network with 3 hidden layers performance based on different adversarial cost sensitivity $\lambda$ for Enron dataset with different number of binary features as (a) 1000, (b) 2000.}
\label{fig:nn3_enron_binary}
\end{figure}
}

\leaveout{
% linear svm results for mnist based on multiclass
\begin{figure}[H]
\centering 
\begin{tabular}{cc}
\includegraphics[scale=0.19]{images/multi/multi_svm627.png} &
\includegraphics[scale=0.19]{images/multi/multi_svm784.png} \\
(a) & (b)
\end{tabular}
\caption{SVM with linear kernel performance based on different adversarial cost sensitivity $\lambda$ with MNIST dataset for multi-class classification when the number of feature is (a) 627, (b) 784.}
\label{fig:multi_svm}
\end{figure}

% nn1 results for mnist based on multiclass
\begin{figure}[H]
\centering 
\begin{tabular}{cc}
\includegraphics[scale=0.19]{images/multi/nn1_mnist_multi627.png} &
\includegraphics[scale=0.19]{images/multi/nn1_mnist_multi784.png} \\
(a) & (b)
\end{tabular}
\caption{Neural network with 1 hidden layers performance based on different adversarial cost sensitivity $\lambda$ with MNIST dataset for multi-class classification when the number of feature is (a) 627, (b) 784.}
\label{fig:multi_nn1}
\end{figure}

% nn3 results for mnist based on multiclass
\begin{figure}[H]
\centering 
\begin{tabular}{cc}
\includegraphics[scale=0.19]{images/multi/multi_nn3_627.png} &
\includegraphics[scale=0.19]{images/multi/multi_nn3_784.png} \\
(a) & (b)
\end{tabular}
\caption{Neural network with 3 hidden layers performance based on different adversarial cost sensitivity $\lambda$ with MNIST dataset for multi-class classification when the number of feature is (a) 627, (b) 784.}
\label{fig:multi_nn3}
\end{figure}
}













\leaveout{
% Ridge results for enron
\begin{figure}[H]
\centering 
\begin{tabular}{cc}
\includegraphics[scale=0.19]{images/ridge_enron1000.png} &
\includegraphics[scale=0.19]{images/ridge_enron2000.png} \\
(a) & (b)
\end{tabular}
\caption{Ridge regression performance based on different adversarial cost sensitivity $\lambda$ for Enron dataset with different number of features as (a) 1000, (b) 2000.}
\label{fig:ridge_enron}
\end{figure}

% Ridge results for mnist

\begin{figure}[H]
\centering 
\begin{tabular}{cc}
\includegraphics[scale=0.19]{images/ridge_mnist627.png} &
\includegraphics[scale=0.19]{images/ridge_mnist784.png} \\
(a) & (b)
\end{tabular}
\caption{Ridge regression performance based on different adversarial cost sensitivity $\lambda$ for MNIST dataset with different number of features as (a) 627, (b) 784.}
\label{fig:ridge_mnist}
\end{figure}

\begin{figure}[H]
\centering 
\begin{tabular}{cccc}
\includegraphics[scale=1.00]{images/ridge/0.png} &
\includegraphics[scale=1.00]{images/ridge/1.png} &
\includegraphics[scale=1.00]{images/ridge/2.png} &
\includegraphics[scale=1.00]{images/ridge/3.png} \\
\includegraphics[scale=1.00]{images/ridge/4.png} &
\includegraphics[scale=1.00]{images/ridge/5.png} &
\includegraphics[scale=1.00]{images/ridge/6.png} &
\includegraphics[scale=1.00]{images/ridge/8.png} \\
\end{tabular}
\caption{Modification process of attacker for Ridge regression based by decreasing the cost sensitivity parameter $\lambda$.}
\label{fig:visual_ridge}
\end{figure}

% Bayesian results for enron
\begin{figure}[H]
\centering 
\begin{tabular}{cc}
\includegraphics[scale=0.19]{images/bayesian_enron1000.png} &
\includegraphics[scale=0.19]{images/bayesian_enron2000.png} \\
(a) & (b)
\end{tabular}
\caption{Bayesian regression performance based on different adversarial cost sensitivity $\lambda$ for Enron dataset with different number of features as (a) 1000, (b) 2000.}
\label{fig:bayesian_enron}
\end{figure}

% Bayesian results for mnist

\begin{figure}[H]
\centering 
\begin{tabular}{cc}
\includegraphics[scale=0.19]{images/Bayesian_mnist627.png} &
\includegraphics[scale=0.19]{images/Bayesian_mnist784.png} \\
(a) & (b)
\end{tabular}
\caption{Bayesian regression performance based on different adversarial cost sensitivity $\lambda$ for MNIST dataset with different number of features as (a) 627, (b) 784.}
\label{fig:bayesian_mnist}
\end{figure}

\begin{figure}[H]
\centering 
\begin{tabular}{cccc}
\includegraphics[scale=1.00]{images/bayesian/0.png} &
\includegraphics[scale=1.00]{images/bayesian/1.png} &
\includegraphics[scale=1.00]{images/bayesian/3.png} &
\includegraphics[scale=1.00]{images/bayesian/5.png} \\
\includegraphics[scale=1.00]{images/bayesian/6.png} &
\includegraphics[scale=1.00]{images/bayesian/8.png} &
\includegraphics[scale=1.00]{images/bayesian/9.png} &
\includegraphics[scale=1.00]{images/bayesian/10.png} \\
\end{tabular}
\caption{Modification process of attacker for Bayesian regression based by decreasing the cost sensitivity parameter $\lambda$.}
\label{fig:visual_bayesian}
\end{figure}
}


% \begin{figure}[ht]
% \vskip 0.2in
% \begin{center}
% \centerline{\includegraphics[width=0.19]{images/q20fea30.png}}
% \caption{.}
% \label{f:}
% \end{center}
% \vskip -0.2in
% \end{figure} 

% \begin{figure}[ht]
% \vskip 0.2in
% \begin{center}
% \centerline{\includegraphics[scale=0.19]{images/q30fea30.png}}
% \caption{.}
% \label{f:}
% \end{center}
% \vskip -0.2in
% \end{figure} 

%First, we compare the learning efficiency of the proposed retraining strategy with the constraint generation approach SMA restricted to different adversarial budgets \cite{li2014feature}. We apply the Enron dataset for both SMA and the retraining methods and evaluate the classification performance based on the $F_1$ score \cite{klimt2004enron}. 
% comparison with SMA
%\begin{figure}[H]
%\centering
%\begin{tabular}{ccc}
%\includegraphics[scale=0.2]{images/q10fea30.png}
%\includegraphics[scale=0.12]{images/q20fea30.png} &
%\includegraphics[scale=0.12]{images/q30fea30.png} \\
%\end{tabular}
%\caption{Comparison between retraining and SMA based on different adversary budgets.}
%\label{f:sma_compare}
%\end{figure} 
%From Figure~\ref{f:sma_compare} we can see that with the adversarial
%budget increasing, the performance of traditional SVM
%decreases. While, the performance of both the retraining and SMA
%increases or keep stable. The $F_1$ score performance for the
%retraining strategy is similar with SMA. However, the retraining
%method is much more scalable than the SMA approach, therefore it
%achieves efficiency without hurting the performance significantly.

% logistic results for enron
%\begin{figure}[H]
%\centering 
%\begin{tabular}{cc}
%\includegraphics[scale=0.19]{images/logistic_enron_con1000.png} &
%\includegraphics[scale=0.19]{images/logistic_enron_con2000.png} \\
%(a) & (b)
%\end{tabular}
%\caption{Logistic regression performance based on different adversarial cost sensitivity $\lambda$ for Enron dataset with different number of features as (a) 1000, (b) 2000.}
%\label{fig:log_enron_con}
%\end{figure}

% Logistic for mnist
%\begin{figure}[H]
%\centering 
%\begin{tabular}{cc}
%\includegraphics[scale=0.19]{images/logistic_mnist627.png} &
%\includegraphics[scale=0.19]{images/logistic_mnist784.png} \\
%(a) & (b)
%\end{tabular}
%\caption{Logistic regression performance based on different adversarial cost sensitivity $\lambda$ for MNIST dataset with different number of features as (a) 627, (b) 784.}
%\label{fig:log_mnist_con}
%\end{figure}
conclusion.tex
\section{Conclusion}

We proposed a general-purpose systematic retraining algorithm against evasion attacks of classifiers for arbitrary oracle-based evasion models.
We first demonstrated that this algorithm effectively minimizes an upper bound on optimal adversarial risk, which is typically extremely difficult to compute (indeed, no approach exists for minimizing adversarial loss for an arbitrary evasion oracle).
Experimentally, we showed that the performance of our retraining approach is nearly indistinguishable from optimal, whereas scalability is dramatically improved: indeed, with \emph{RAD}, we are able to easily scale the approach to thousands of features, whereas a state-of-the-art adversarial risk optimization method can only scale to 15-30 features.
We generalize our results to show that a probabilistic upper bound on minimal adversarial loss can be obtained even when the oracle is computed approximately by leveraging random restarts, and an empirical evaluation which confirms that the resulting bound relaxation is tight in practice.

%for both differentiable discriminant functions and the discrete models. We offered a upper bound for the learner's loss for convex differentiable learning models. We also empirically proved the convergence of the algorithm, therefore still guarantee the upper bound for the discrete feature space and non-convex models, where the global optimal best response of attacker is not guaranteed. 
%We formulated the attacker model considering both the evasion purpose as well as the modification cost. We empirically demonstrated to what extend the adversary can evade different classifiers based on their different preferred cost sensitivity. 
%We applied a highly scalable coordinate descent algorithm for attacker to search for the optimal evasion strategy. It has been shown that various popular classification algorithms, such as SVMs and neural networks, can still be evaded efficiently with great performance degrade.

We also offer a general-purpose framework for optimization-based oracles using variations of coordinate greedy algorithm on both discrete and continuous feature spaces.
Our experiments demonstrate that our adversarial oracle approach is extremely effective in corrupting the baseline learning algorithms.
On the other hand, extensive experiments also show that the use of our retraining methods significantly boosts robustness of algorithms to evasion.
Indeed, retrained algorithms become nearly insensitive to adversarial evasion attacks, at the same time maintaining extremely good learning performance on data overall.
Perhaps the most significant strength of the proposed approach is that it can make use of arbitrary learning algorithms essentially ``out-of-the-box'', and effectively and quickly boost their robustness, in contrast to most prior adversarial learning methods which were algorithm-specific.

%To extend this work, it is necessary to consider different attacker cost models and learn their objectives from the collected real world data, such as spam or malware \cite{ke2016behavioral}. This way the attacker's behavior can be simulated more accurately and 
%obtain tighter bound for the learner. Alternatively, the learner can also combine the retraining approach as proposed with ensemble techniques, such as bagging or random forests to against the deliberated evasion attacks. Furthermore, with more powerful attackers who can have access to part of the training data, poisoning attacks can also be conducted and cause larger cost for the learning systems. Therefore, how to identify the poisoning training data with the normal ones and retraining the leaner is also an important topic to pursue.


attacks.tex
\section{Modeling Attackers}

\subsection{Evasion Attack as Optimization}
\label{s:game}

In prior literature, evasion attacks have almost universally been
modeled as optimization problems in which attackers balance the
objective of evading the classifier (by changing the label from $+1$
to $-1$) and the cost of such
evasion~\cite{lowd2005adversarial,li2014feature}.
Our approach is in the same spirit, but is formally somewhat distinct.
In particular, we assume that the adversary has the following
two competing objectives: 1) appear as benign as possible to the
classifier, and 2) minimize modification cost.
It is also natural to assume that the attacker obtains no value from a
modification to the original feature vector if the result is still
classified as malicious.
To formalize, consider an attacker who in the original training data
uses a feature vector $x_i$ ($i \in I_{bad})$).
The adversary $i$ is solving the following optimization problem:
\begin{equation}
\label{eq:attack}
\min_{x \in X} \min\{0,f(x)\} + c(x,x_i).
\end{equation}
We assume that $c(x,x_i) \ge 0$,
$c(x,x_i) = 0$ iff $x = x_i$, and $c$ is strictly increasing
in $\|x - x_i\|_2$ and strictly convex in $x$.\footnote{Here we
  exhibit a particular general attack model, but many alternatives are
  possible, such as using constrained
  optimization. We found
  experimentally that the results are not particularly
  sensitive to the choice of the attack model.}
Because Problem~\ref{eq:attack} is non-convex, we instead minimize an upper bound:
\begin{equation}
\label{eq:attacker_q}
\min \limits_{x} Q(x) \equiv f(x) + c(x,x_i).
\end{equation}
In addition, if $f(x_i) < 0$, we return $x_i$ before solving Problem~\ref{eq:attacker_q}.
If Problem~\ref{eq:attacker_q} returns an optimal solution $x^*$ with
$f(x^*) \ge 0$, we return $x_i$; otherwise, return $x^*$.
Problem~\ref{eq:attacker_q} has two advantages.
First, if $f(x)$ is convex and $x$ real-valued, this is a (strictly) convex
optimization problem, has a unique solution, and we can solve it in polynomial time.
An important special case is when $f(x) = w^Tx$.
The second one we formalize in the following lemma.
\begin{lemma}
\label{L:bound}
Suppose $x^*$ is the optimal solution to Problem~\ref{eq:attack}, $x_i$ is
suboptimal, and $f(x^*) < 0$. 
Let $\bar{x}$ be the optimal solution to
Problem~\ref{eq:attacker_q}.
Then $f(\bar{x}) + c(\bar{x},x_i) = f(x^*) + c(x^*,x_i)$, and
$f(\bar{x}) < 0$.
\end{lemma}
%\begin{proof}
%If $f(x^*) < 0$, then $\min\{0,f(x^*)\} + c(x^*,x_i) = f(x^*) +
%c(x^*,x_i)$.
%By optimality of $\bar{x}$, $f(\bar{x}) + c(\bar{x},x_i) \le f(x^*) +
%c(x^*,x_i)$.
%Since $x_i$ is suboptimal in Problem~\ref{eq:attack} and $c$ strictly
%positive in all other cases, $f(x^*) +
%c(x^*,x_i) < \min\{0,f(x_i)\} + c(x_i,x_i) =0$.
%By optimality of $x^*$, $f(x^*) + c(x^*,x_i) \le \min\{0,f(\bar{x})\}
%+ c(\bar{x},x_i) \le f(\bar{x}) + c(\bar{x}, x_i)$, which implies that
%$f(\bar{x}) + c(\bar{x},x_i) = f(x^*) + c(x^*,x_i)$.
%Consequently, $f(\bar{x}) + c(\bar{x},x_i) < 0$, and, therefore,
%$f(\bar{x}) < 0$.
%\end{proof}
The following corollary then follows by uniqueness of optimal
solutions for strictly convex objective functions over a real vector space.
\begin{corollary}
\label{C:convex}
If $f(x)$ is convex and $x$ continuous, $x^*$ is the optimal solution to
Problem~\ref{eq:attack}, $\bar{x}$ is the optimal solution to
Problem~\ref{eq:attacker_q}, and $f(x^*) < 0$, then $\bar{x} = x^*$.
\end{corollary}
A direct consequence of this corollary is that when we use
Problem~\ref{eq:attacker_q} to approximate Problem~\ref{eq:attack} and
this approximation is convex, we always return either the optimal
evasion, or $x_i$ if no cost-effective evasion is possible.
An oracle $\mathcal{O}$ constructed on this basis will therefore
return a unique solution, and supports the theoretical
characterization of \emph{RAD} above.

The results above are encouraging, but many learning problems do not
feature a convex $f(x)$, or a continuous feature space.
Next, we consider several general algorithms for adversarial evasion.

\subsection{Coordinate Greedy}
\label{s:coor}

%\subsubsection{Binary Feature Space}
We propose a very general local search framework,
\emph{CoordinateGreedy (CG)} (Algorithm~\ref{alg:coordinate} for approximating
optimal attacker evasion.
%To optimize the adversarial objective, we simulate the attacker's
%instances by coordinate descent algorithm\ref{alg:coordinate}.
\begin{algorithm}[thb]
\caption{CoordinateGreedy(\emph{CG}): $\mathcal{O}(\beta,x)$}
\label{alg:coordinate}
\begin{algorithmic}[1]
\STATE \textbf{Input}: {Parameter vector $\beta$, malicious instance $x$}
 \STATE {Set $k \leftarrow 0$ and let $x^0 \leftarrow x$}
 % \WHILE {$k < B$ and $f(x^k) \geq \delta$ }
 \REPEAT 
 % {$|f(x^A)-f(x^k)| \leq \delta$}
 \STATE{Randomly choose index $i_k \in \{1, 2, ..., n\}$ }
 \STATE{$x^{k+1} \leftarrow $GreedyImprove($i_k$)}
 %\STATE{$x^{k+1} \leftarrow x^k - \tau_k {[\triangledown Q(x^k)]}_{i_k} e_{i_k}$}
 \STATE {$k \leftarrow k+1$}
 % \UNTIL {$|Q(x^{k})-Q(x^{k-1})| \leq \epsilon$ or $f(x^k) \leq \delta$}
 %\UNTIL {$\frac{\ln Q(x^{k})} {\ln Q(x^{k-1})} \leq \epsilon$ or
 %$f(x^k) \leq \delta$}
 \UNTIL{$\frac{\ln Q(x^{k})} {\ln Q(x^{k-1})} \leq \epsilon$}
 % \ENDWHILE
% \STATE {Project $x^{k}$ to the feature space $x' \in X$}
\IF{$f(x^k) \ge 0$}
 \STATE $x^k \leftarrow x$
\ENDIF
 \STATE \textbf{Output}: {Adversarially optimal instance $x^k$.}
\end{algorithmic}
\end{algorithm}
The high-level idea is to iteratively choose a feature, and greedily
update this feature to incrementally improve the attacker's utility
(as defined by Problem~\ref{eq:attacker_q}).
In general, this algorithm will only converge to a locally optimal
solution.
We therefore propose a version with random restarts: run \emph{CG}
from $L$ random starting points in feature space.
As long as a global optimum has a basin of attraction with positive
Lebesgue measure, or the feature space is finite, this process will asymptotically converge to a
globally optimal solution as we increase the number of random
restarts.
Thus, as we increase the number of random restarts, we expect to increase
the frequency that we actual return the global optimum.
Let $p_L$ denote the probability that the oracle based on coordinate
greedy with $L$ random restarts returns a suboptimal solution to Problem~\ref{eq:attacker_q}.
The next result generalizes the bound on \emph{RAD} to allow for this,
restricting however that the risk function which we bound from above
uses the $0/1$ loss.
Let $\mathcal{L}_{A,01}^*(\mathcal{O})$ correspond to the total
adversarial risk in Equation~\ref{E:advloss}, where the loss function
$l(g_\beta(x),y)$ is the $0/1$ loss.
Suppose that $\mathcal{O}_L$ uses coordinate greedy with $L$ random restarts.
\begin{proposition}
\label{prop:defender_loss_gen}
Let $B = |I_{bad}|$.
$\mathcal{L}_{A,01}^*(\mathcal{O}) \le \mathcal{L}^R_N(\beta,
\mathcal{O}_L) + \delta(p)$ with probability at least $1-p$, where 
% $\delta(p) = (p_L +
% (-\frac{1}{2B} \log p)^{1/2})$, 
$\delta(p) = B \left(p_L + \frac{\sqrt{\log^2 p-8 B p_l \log p}-\log p}{2B}\right),$
and $\mathcal{L}^R_N(\beta,
\mathcal{O}_L)$ uses any loss function $l(g_\beta(x),y)$ which is an upper bound on
the $0/1$ loss.
\end{proposition}
\leaveout{
\begin{proof}
Let $\bar{\beta} \in \arg\min_{\beta}  \mathcal{L}^R_N(\beta,
\mathcal{O}_L)$.
Consequently, for any $\beta$,
\begin{align*}
\mathcal{L}_{A,01}^*(\mathcal{O}_L) &= \min_\beta \mathcal{L}_{A,01}(\beta;
\mathcal{O}_L) \\
&\le \sum_{i: y_i = -1} l_{01}(g_{\bar{\beta}}(x_i),-1) +\sum_{i:y_i = +1}
l_{01}(g_{\bar{\beta}} (\mathcal{O}(\bar{\beta},x_i)),+1) + \alpha ||\bar{\beta}||_p^p.
\end{align*}
Now,
\begin{align*}
\sum_{i:y_i = +1} &l_{01}(g_{\bar{\beta}}
(\mathcal{O}(\bar{\beta},x_i)),+1) \le \sum_{i:y_i = +1} l_{01}(g_{\bar{\beta}}
(\mathcal{O}_L(\bar{\beta},x_i)),+1) + \delta(p)
\end{align*}
with probability at least $1 - p$,
% where $\delta(p) = (p_L + (-\frac{1}{2B} \log p)^{1/2})$,
where $\delta(p) = B p_L + \frac{\sqrt{\log^2 p-8 B p_l \log p}-\log p}{2}$,
by the Chernoff bound, and Lemma~\ref{L:bound}, which assures that an
optimal solution to Problem~\ref{eq:attacker_q} can only over-estimate mistakes.
Moreover,
\begin{align*}
\sum_{i:y_i = +1} &l_{01}(g_{\bar{\beta}}
(\mathcal{O}_L(\bar{\beta},x_i)),+1) \le\sum_{i:y_i = +1}\sum_{j \in N_i} l(g_{\bar{\beta}}
(\mathcal{O}_L(\bar{\beta},x_i)),+1),
\end{align*}
since $\mathcal{O}_L(\bar{\beta},x_i) \in N_i$ for all $i$ by
construction, and $l$ is an upper bound on $l_{01}$.
Putting everything together, we get the desired result.
\end{proof}
}

%We empirically evaluate the converging value of $P_A$ empirically as
%shown in Figure~\ref{fig:start}.

\leaveout{%%% ADD FIGURE TO SUPPLEMENT
\begin{figure}[t]
\centering 
\begin{tabular}{cc}
\includegraphics[scale=0.19]{images/binary_start.png} &
\includegraphics[scale=0.19]{images/continuous_start.png} \\
(a) & (b)
\end{tabular}
\caption{The convergence of $p_L$ based on different number of starting points for (a) Binary, (b) Continuous feature space.}
\label{fig:start}
\end{figure}
%Figure~\ref{fig:start} demonstrates 
}
Experiments suggest that $p_L \rightarrow 0$ quite rapidly for an array of learning algorithms, and for either
discrete or continuous features, as we increase the number of restarts
$L$ (see the supplement for details).
Consequently, in practice retraining with coordinate
greedy nearly minimizes an upper bound on minimal adversarial
risk for a 0/1 loss with few restarts of the approximate attacker oracle.

\noindent{\bf Continuous Feature Space: }
%\label{sub:continuous}
For continuous feature space, we assume that both $f(x)$ and
$c(x,\cdot)$ are differentiable in $x$, and propose using the \emph{coordinate descent}
algorithm, which is a special case of coordinate greedy, where the
GreedyImprove step is:
\(
x^{k+1} \leftarrow x^k - \tau_k e_{i_k} \frac{\partial
  Q(x^k)}{\partial x^k_{i_k}},
\)
where $\tau_k$ is the step size and $e_{i_k}$ the direction of $i_k$th
coordinate.
Henceforth, let the origial adversarial instance $x_i$ be given; we
then simplify cost function to be only a function of $x$, denoted $c(x)$.
If the function $f(x)$ is convex and differentiable, our coordinate
descent based algorithm~\ref{alg:coordinate} can always find the
global optima which is the attacker best response $x^*$
\cite{luo1992convergence}, and Proposition~\ref{prop:defender_loss}
applies, by Corollary~\ref{C:convex}.
If $f(x)$ is not convex, then coordinate descent will only converge
to a local optimum.

\leaveout{
Now, $\frac{\partial
  Q(x^k)}{\partial x^k_{i_k}} = \frac{\partial
  f(x^k)}{\partial x^k_{i_k}} + \frac{\partial
  c(x^k)}{\partial x^k_{i_k}}.$
Fixing a coordinate $j = i_k$, we derive the partial derivative of
$f(x)$ with respect to coordinate $j$ for several common learning
algorithms, and derive the derivative of $c(x)$ for several natural
cost functions.

%If the feature space is continuous as $X \subseteq R^n$, we need to
%derive ${[\triangledown f(x^k,\beta)]}_{i_k}$ according to different
%learning models.

\paragraph{Kernel SVM}

Consider a general Kernel SVM decision function, for which $f(x) =
\sum_i a_i y_i K(x_i,x)$, where $x_i, y_i$ are the support training data
points, $a_i$ the associated dual SVM parameters, and $K(\cdot,\cdot)$
a kernel function.
Then, $\frac{\partial f(x)}{\partial x_j} = \sum_i a_i y_i
\frac{\partial K(x_i,x)}{\partial x_j}.$ 
For a linear Kernel, $\frac{\partial K(x_i,x)}{\partial x_j} = x_{i_{j}}.$
For a polynomial Kernal, $\frac{\partial K(x_i,x)}{\partial x_j} = d(c
+ x_i \cdot x)^{d-1} x_{i_{j}}$.
For an RBF Kernel, $\frac{\partial K(x_i,x)}{\partial x_j} =
\frac{1}{\sigma^2}K(x_i,x)(x_{i_{j}} - x_j)$.

\paragraph{Logistic Regression}
Given a logistic regression model, with $f(x) =
(1+e^{-w^T x})^{-1}$. Then, $\frac{\partial f(x)}{\partial x_j} =
w_j f(x)(1-f(x)).$
}

\leaveout{
\paragraph{Logistic Regression}

For example, for the Ridge regression $y = {\frac{1}{2} (y-w^Tx)^2 + {||w||}_2}$
\begin{equation}
{[\triangledown f(x^k,w)]}_{i_k} = -(y-w^Tx)w_i.
\end{equation}
For Bayesian regression $y = x^T A + \epsilon$, where $\epsilon_i \sim N(0,\sigma^2)$,
\begin{equation}
{[\triangledown f(x^k,A)]}_{i_k} = A_i.
\end{equation}
Note that the estimated coefficient can be derived as $A = {(X^T X)}^{-1} X^T y$.

For the linear-SVM, $y = \frac{1}{2} w^T w + C \sum \limits_{i = 1}^l \max(1-y_i w^T x_i,0)$,
\begin{equation}
{[\triangledown f(x^k,w)]}_{i_k} = C \cdot 
\begin{cases}
-y_i w_i ;  &\text{if}\ 1-y_i w^T x_i\ge 0 \\
0 ;  &\text{otherwise}
\end{cases}
\end{equation}
}

\leaveout{
\paragraph{Neural Network}

For the neural network with sigmoid function as the activation function, if there are three hidden layers,
$g(x) = (1+e^{-h_3(x)})^{-1}$, \\
$h_3(x) = \sum \limits_{t = 1}^{d_3} {w_3}_t {\delta_3}_t (x) +b_3$, \\
${\delta_3}_t (x)= (1+e^{-{h_2}_t(x)})^{-1}$, \\
${h_2}_t(x) = \sum \limits_{j = 1}^{d_2} {w_2}_j {\delta_2}_j (x) +b_2$, \\
${\delta_2}_j (x)= (1+e^{-{h_1}_j(x)})^{-1}$, \\
${h_1}_j(x) = \sum \limits_{p = 1}^{d_1} {w_1}_p {\delta_1}_p (x) +b_1$, \\
${\delta_1}_p (x)= (1+e^{-{h_0}_p(x)})^{-1}$, \\
${h_0}_p(x) = \sum \limits_{l = 1}^{n} {w_1}_l x_l +b_0$, \\

Therefore we have
\begin{equation}
%\begin{scriptsize}
\begin{aligned}
&\frac{\partial f(x)}{\partial x_j}= g(x)(1-g(x)) \sum \limits_{t = 1}^{d_3} {w_{j_3}}_t {\delta_{j_3}}_t(1-{\delta_{j_3}}_t) \\
&\sum \limits_{k = 1}^{d_2} {w_{j_2}}_k {\delta_{j_2}}_j(1-{\delta_{j_2}}_k) \sum \limits_{p = 1}^{d_1} {w_{j_1}}_p {\delta_{j_1}}_p(1-{\delta_{j_1}}_p) {w_{j_0}}_i.
\end{aligned}
%\end{scriptsize}
\end{equation}
}

\leaveout{
For the neural network with rectified linear unit (ReLU) function as the activation function, if there are three hidden layers,
$g(x) = \max(0,h_3(x))$, \\
$h_3(x) = \sum \limits_{t = 1}^{d_3} {w_3}_t {\delta_3}_t (x) +b_3$, \\
${\delta_3}_t (x)= \max(0,{h_2}_t(x))$, \\
${h_2}_t(x) = \sum \limits_{j = 1}^{d_2} {w_2}_j {\delta_2}_j (x) +b_2$, \\
${\delta_2}_j (x)= \max(0,{h_1}_j(x))$, \\
${h_1}_j(x) = \sum \limits_{p = 1}^{d_1} {w_1}_p {\delta_1}_p (x) +b_1$, \\
${\delta_1}_p (x)= \max(0,{h_0}_p(x))$, \\
${h_0}_p(x) = \sum \limits_{l = 1}^{n} {w_1}_l x_l +b_0$, \\

Therefore we have when 
\begin{equation*}
\centering
\begin{scriptsize}
\begin{aligned}
&{[\triangledown f(x^k,\beta)]}_{i_k}  \\
&=
\begin{cases}
 h_3(x) & \sum \limits_{t = 1}^{d_3} {w_3}_t {h_2}_t(x) \sum \limits_{j = 1}^{d_2} {w_2}_j {h_1}_j(x)  \sum \limits_{p = 1}^{d_1} {w_1}_p {h_0}_p(x) {w_{j_0}}_i, \\
 & \text{if}\ {h_3}(x) \cdot \sum \limits_{t = 1}^{d_3} {h_2}_t(x) \cdot \sum \limits_{k = 1}^{d_2} {h_1}_k(x) \cdot \sum \limits_{p = 1}^{d_1} {h_0}_p(x) \ne 0\\
 0, \ &\text{otherwise}.
\end{cases}
\end{aligned}
\end{scriptsize}
\end{equation*}
}

\leaveout{
\paragraph{Quadratic Cost}

A simple and natural cost function is a quadratic ($l_2$) cost,
$c(x,x_i) = \frac{\lambda}{2}\|x-x_i\|_2^2$.
In this case, $\frac{\partial c(x)}{\partial x_j} = \lambda (x_j - x_{ij}).$

\paragraph{L1-distance Cost}

Another variation of the cost function is the $l_1$ cost,
$c(x,x_i) = \lambda \|x-x_i\|_1^1$.
In this case, $\frac{\partial c(x)}{\partial x_j} = \lambda .$

\paragraph{Exponential Cost}

Below, we make use of an exponential cost, which is also quite
natural: options become exponentially less desirable to an attacker as
they are more distant from their ideal attack.
We use the following cost function: 
$c(x,x_i) = \exp \left(\lambda (\sum_j (x_j -x_{ij})^2 +1)^{1/2}
\right)$.
Then, 
\[
\frac{\partial c(x)}{\partial x_j} = \frac{\lambda c(x,x_i)(x_j -x_{ij})}{(\sum_j  (x_j -x_{ij})^2 +1)^{1/2}}.
\]
}

\noindent{\bf Discrete Feature Space: }
%\label{sub:discrete}
In the case of discrete feature space, GreedyImprove step of \emph{CG}
can simply
enumerate all options for feature $j$, and choose the one most
improving the objective.

\leaveout{
\subsection{Attacks as Constrained Optimization}

A variation on the attack models above is when the attacker is solving
the following constrained optimization problem:
\begin{subequations}
\label{E:constrainedAttacks}
\begin{align}
&\min_x \min\{0,f(x)\}\\
&\mathrm{s.t.:} \quad c(x,x_i) \le B
\end{align}
\end{subequations}
for some cost budget constraint $B$.
While this problem is, again, non-convex, we can instead minimize the
convex upper bound, $f(x)$, as before, if we assume that $f(x)$ is
convex.
In this case, if the feature space is continuous, the problem can be
solved optimally using standard convex optimization
methods~\cite{Boyd04}.
If the feature space is binary and $f(x)$ is linear or
convex-inducing, algorithms proposed by Lowd and
Meek~\cite{lowd2005adversarial} and Nelson et
al.~\cite{nelson2012query}.
}
attacks__bo_li_s_conflicted_copy_2016-02-11_.tex
\section{Modeling Attackers}

\subsection{Evasion Attack as Optimization}
\label{s:game}

In prior literature, evasion attacks have almost universally been
modeled as optimization problems in which attackers balance the
objective of evading the classifier (by changing the label from $+1$
to $-1$) and the cost of such
evasion~\cite{lowd2005adversarial,li2014feature}.
Our approach is in the same spirit, but is formally somewhat distinct.
In particular, we assume that the adversary has the following
two competing objectives: 1) appear as benign as possible to the
classifier, and 2) minimize modification cost.
Moreover, we assume that the attacker obtains no value from a
modification to the original feature vector if the result is still
classified as malicious.
To formalize, consider an attacker who in the original training data
uses a feature vector $x_i$ ($i \in I_{bad})$).
The adversary $i$ is solving the following optimization problem:
\begin{equation}
\label{eq:attack}
\min_{x \in X} \min\{0,f(x)\} + c(x,x_i).
\end{equation}
As is typical in related literature, we assume that $c(x,x_i) \ge 0$,
$c(x,x_i) = 0$ iff $x = x_i$, and $c$ is strictly increasing
in $\|x - x_i\|_2$ and strictly convex in $x$.
Because Problem~\ref{eq:attack} is non-convex, we instead minimize an upper bound:
\begin{equation}
\label{eq:attacker_q}
\min \limits_{x} Q(x) \equiv f(x) + c(x,x_i).
\end{equation}
In addition, if $f(x_i) < 0$, we return $x_i$ before solving Problem~\ref{eq:attacker_q}.
If Problem~\ref{eq:attacker_q} returns an optimal solution $x^*$ with
$f(x^*) \ge 0$, we return $x_i$; otherwise, return $x^*$.
Problem~\ref{eq:attacker_q} has two advantages.
First, if $f(x)$ is convex and $x$ real-valued, this is a (strictly) convex
optimization problem, has a unique solution, and we can solve it in polynomial time.
An important special case is when $f(x) = w^Tx$.
The second one we formalize in the following lemma.
\begin{lemma}
\label{L:bound}
Suppose $x^*$ is the optimal solution to Problem~\ref{eq:attack}, $x_i$ is
suboptimal, and $f(x^*) < 0$. 
Let $\bar{x}$ be the optimal solution to
Problem~\ref{eq:attacker_q}.
Then $f(\bar{x}) + c(\bar{x},x_i) = f(x^*) + c(x^*,x_i)$, and
$f(\bar{x}) < 0$.
\end{lemma}
\begin{proof}
If $f(x^*) < 0$, then $\min\{0,f(x^*)\} + c(x^*,x_i) = f(x^*) +
c(x^*,x_i)$.
By optimality of $\bar{x}$, $f(\bar{x}) + c(\bar{x},x_i) \le f(x^*) +
c(x^*,x_i)$.
Since $x_i$ is suboptimal in Problem~\ref{eq:attack} and $c$ strictly
positive in all other cases, $f(x^*) +
c(x^*,x_i) < 0$.
By optimality of $x^*$, $f(x^*) + c(x^*,x_i) \le \min\{0,f(\bar{x})\}
+ c(\bar{x},x_i) \le f(\bar{x}) + c(\bar{x}, x_i)$, which implies that
$f(\bar{x}) + c(\bar{x},x_i) = f(x^*) + c(x^*,x_i)$.
Consequently, $f(\bar{x}) + c(\bar{x},x_i) < 0$, and, therefore,
$f(\bar{x}) < 0$.
\end{proof}
The following corollary then follows by uniqueness of optimal
solutions for strictly convex objective functions over a real vector space.
\begin{corollary}
\label{C:convex}
If $f(x)$ is convex and $x$ continuous, $x^*$ is the optimal solution to
Problem~\ref{eq:attack}, $\bar{x}$ is the optimal solution to
Problem~\ref{eq:attacker_q}, and $f(x^*) < 0$, then $\bar{x} = x^*$.
\end{corollary}
A direct consequence of this corollary is that when we use
Problem~\ref{eq:attacker_q} to approximate Problem~\ref{eq:attack} and
this approximation is convex, we always return either the optimal
evasion, or $x_i$ if no cost-effective evasion is possible.
An oracle $\mathcal{O}$ constructed on this basis will therefore
return a unique solution, and supports the theoretical
characterization of \emph{RAD} above.

The results above are encouraging, but many learning problems do not
feature a convex $f(x)$, or a continuous feature space.
Next, we consider several general algorithms for adversarial evasion.

%In order to evade detections, the attacker aims to modify the original malicious instance $x^A$ to generate $x'$, which can be classified as benign, using limited budget. In general, the adversary needs to solve the optimization as below.

%\begin{align}
%\label{eq:attacker_model}
%x' = &\arg\min \limits_{x} f(x) \\
%s.t. \qquad &c(x', x^A) \leq d_{max}
%\end{align}

%Here $f(x)$ is the probability function learned by the classifier and $d_{max}$ is the maximum cost (budget) that the attacker is restricted to.  
%With binary features, Lowd and Meek have proposed a 2-approximate algorithm to generate such optimal evasion attack instances \cite{lowd2005adversarial}. They demonstrated that to generate the benign instance $x'$, the attacker at most need to pay twice of the ideal optimal cost. But this only applies to linear classifier and the budget of attacker cannot be bounded by certain values, which is often the case in practical. 

%Therefore we incorporate the cost of attackers into their objective, and form the adversary's objective as the following optimization problem.
%\begin{equation}
%\label{eq:attacker_g}
%\min \limits_{x'} H(x') := g(x') +\exp \left({\lambda \sqrt{\sum \limits_{i = 1}^n{ (x^A}_i -{x'}_i)^2 +1}} \right),
%\end{equation}
%where $g(x)$ is the sign function for the probability model $f(x)$.
%Therefore, we form the relaxation model for the original problem as below.
%\begin{equation}
%\label{eq:attacker_q}
%\min \limits_{x'} Q(x') := f(x') +\exp \left({\lambda \sqrt{\sum \limits_{i = 1}^n{ (x^A}_i -{x'}_i)^2 +1}} \right)
%\end{equation}

%Here $Q(x')$ indicates the adversarial minimization goal by modifying the adversarial instance $x^A$ into $x'$. 
%It is obvious that if the the optimal solution $x^*$ for the relaxed problem~\ref{eq:attacker_q} is feasible for the original problem, then it is also optimal for the original problem~\ref{eq:attacker_g}.
%We will discuss how to solve this adversarial optimization problem later in for different models in different cases later.

%We form the interaction between the learner and attacker as a Stackelberg game. Within the game, first the learner uses training data to choose a classifier $g(x)$, which can be viewed as a sign function of the probabilistic modeling function $f(x)$.
%Then each adversary applies a query-based algorithm to (approximately) solve the optimization problem~\ref{eq:attacker_model} for their malicious instances $x^A$ and generate their ``optimal" evasion instances to evade the classifier.
%Finally, the learner's loss is measured using a new dataset in which every malicious $x \in X$ is replaced with a corresponding $x'$ computed by optimizing the relaxed adversarial objective~\ref{eq:attacker_q}. 

%Within the game, given the knowledge (prediction) about the attacker behavior, the learner would optimize a more robust learning system by generating the adversarial strategies and include them for during training to enhance the model.
%The mixed integer programming approach, which can guarantee to find the optimal adversarial strategies $x^*$, was proposed in \cite{li2014feature}. However, this approach is not scalable for either the number of instances or feature dimensions.
%Therefore, we will discuss the coordinate greedy algorithm which is highly scalable, and the corresponding loss guarantee.

\subsection{Coordinate Greedy}
\label{s:coor}

%\subsubsection{Binary Feature Space}
We propose a very general local search framework,
\emph{CoordinateGreedy (CG)} (Algorithm~\ref{alg:coordinate} for approximating
optimal attacker evasion.
%To optimize the adversarial objective, we simulate the attacker's
%instances by coordinate descent algorithm\ref{alg:coordinate}.
\begin{algorithm}[thb]
\caption{CoordinateGreedy: $\mathcal{O}(\beta,x)$}
\label{alg:coordinate}
\begin{algorithmic}[1]
\STATE \textbf{Input}: {Parameter vector $\beta$, malicious instance $x$}
 \STATE {Set $k \leftarrow 0$ and let $x^0 \leftarrow x$}
 % \WHILE {$k < B$ and $f(x^k) \geq \delta$ }
 \REPEAT 
 % {$|f(x^A)-f(x^k)| \leq \delta$}
 \STATE{Randomly choose index $i_k \in \{1, 2, ..., n\}$ }
 \STATE{$x^{k+1} \leftarrow $GreedyImprove($i_k$)}
 %\STATE{$x^{k+1} \leftarrow x^k - \tau_k {[\triangledown Q(x^k)]}_{i_k} e_{i_k}$}
 \STATE {$k \leftarrow k+1$}
 % \UNTIL {$|Q(x^{k})-Q(x^{k-1})| \leq \epsilon$ or $f(x^k) \leq \delta$}
 %\UNTIL {$\frac{\ln Q(x^{k})} {\ln Q(x^{k-1})} \leq \epsilon$ or
 %$f(x^k) \leq \delta$}
 \UNTIL{$\frac{\ln Q(x^{k})} {\ln Q(x^{k-1})} \leq \epsilon$}
 % \ENDWHILE
% \STATE {Project $x^{k}$ to the feature space $x' \in X$}
\IF{$f(x^k) \ge 0$}
 \STATE $x^k \leftarrow x$
\ENDIF
 \STATE \textbf{Output}: {Adversarially optimal instance $x^k$.}
\end{algorithmic}
\end{algorithm}
The high-level idea is to iteratively choose a feature, and greedily
update this feature to incrementally improve the attacker's utility
(as defined by Problem~\ref{eq:attacker_q}).
In general, this algorithm will only converge to a locally optimal
solution.
We therefore propose a version with random restarts: run \emph{CG}
from $L$ random starting points in feature space, in addition to
starting from the initial malicious instance $x$.
As long as a global optimum has a basin of attraction with positive
Lebesgue measure, or the feature space is finite, this process will asymptotically converge to a
globally optimal solution as we increase the number of random
restarts.
%In practice, we would limit the number of these to be relatively
%small.
Thus, as we increase the number of random restarts, we expect to increase
the frequency that we actual return the global optimum.
Let $p_L$ denote the probability that the oracle based on coordinate
greedy with $L$ random restarts returns a suboptimal solution to Problem~\ref{eq:attacker_q}.
The next result generalizes the bound on \emph{RAD} to allow for this,
restricting however that the loss function which we bound from above
is the $0/1$ loss.
Let $\mathcal{L}_{A,01}^*(\mathcal{O})$ correspond to the total
adversarial loss in Equation~\ref{E:advloss}, where the loss function
$l(g_\beta(x),y)$ is the $0/1$ loss.
Suppose that $\mathcal{O}_L$ uses coordinate greedy with $L$ random restarts.
\begin{proposition}
\label{prop:defender_loss}
Let $B = |I_{bad}|$.
$\mathcal{L}_{A,01}^*(\mathcal{O}) \le \mathcal{L}^R_N(\beta,
\mathcal{O}_L) + \delta(p)$ with probability at least $1-p$, where 
% $\delta(p) = (p_L +
% (-\frac{1}{2B} \log p)^{1/2})$, 
$\delta(p) = B \cdot p_L + \frac{\sqrt{\log^2 p-8 B p_l \log p}-\log p}{2}$,
and $\mathcal{L}^R_N(\beta,
\mathcal{O}_L)$ uses any loss function $l(g_\beta(x),y)$ which is an upper bound on
the $0/1$ loss.
%The upper bound of defender's loss in adversarial environments is 
% $L_D \leq \sum \limits_{y_i = -1} l(-w^T x_i) + \sum \limits_{y_i = +1} \max \limits_{{x_i}' \in {x_i}^*} l(w^T {x_i}') + \lambda ||w||_p $.
%${L_D}^A \leq \sum \limits_{x_i \in X \cup R} l_\beta( x_i) + \alpha ||\beta||_p + t \cdot {P}_A$ when $f(x)$ is not convex, where $X$ is the original training set and $R$ represents the total added instances. $t$ denotes the number of malicious instances in $X$ ($t = |X_A|$), and $P_A$ is the probability that the best response $x^*$ would evade the classifier. 
\end{proposition}
\begin{proof}
%From Proposition~\ref{prop:defender_loss}, we have ${L_D}^A \leq \sum \limits_{x_i \in X \cup R} l_\beta( x_i) + \alpha ||\beta||_p$ if the adversary best response $x^* \in R$. However, if the adversary best response $x^*$ is not found and it can evade the classifier $g(x^*) =-1$, the loss of learner would increase with 1 for the 0-1 loss. Therefore, if the probability of the adversary best response $x^*$ evading classifier is $P_A$, 
%${L_D}^A \leq \sum \limits_{x_i \in X \cup R} l_\beta( x_i) + \alpha
%||\beta||_p + t \cdot {P}_A$.
Let $\bar{\beta} \in \arg\min_{\beta}  \mathcal{L}^R_N(\beta,
\mathcal{O}_L)$.
Consequently, for any $\beta$,
% (omitting regularization terms, since
% they are identical throughtout),
\begin{align*}
\mathcal{L}_{A,01}^*(\mathcal{O}_L) &= \min_\beta \mathcal{L}_{A,01}(\beta;
\mathcal{O}_L) \\
&\le \sum_{i: y_i = -1} l_{01}(g_{\bar{\beta}}(x_i),-1) +\\
&\quad\quad\quad\quad \sum_{i:y_i = +1}
l_{01}(g_{\bar{\beta}} (\mathcal{O}(\bar{\beta},x_i)),+1) + \alpha ||\bar{\beta}||_p^p.
\end{align*}
Now,
\begin{align*}
\sum_{i:y_i = +1} &l_{01}(g_{\bar{\beta}}
(\mathcal{O}(\bar{\beta},x_i)),+1) \le \\
&\sum_{i:y_i = +1} l_{01}(g_{\bar{\beta}}
(\mathcal{O}_L(\bar{\beta},x_i)),+1) + \delta(p)
\end{align*}
with probability at least $1 - p$,
% where $\delta(p) = (p_L + (-\frac{1}{2B} \log p)^{1/2})$,
where $\delta(p) = B \cdot p_L + \frac{\sqrt{\log^2 p-8 B p_l \log p}-\log p}{2}$,
by Chernoff bound, and Lemma~\ref{L:bound}, which assures that an
optimal solution to Problem~\ref{eq:attacker_q} can only over-estimate mistakes.
Moreover,
\begin{align*}
\sum_{i:y_i = +1} &l_{01}(g_{\bar{\beta}}
(\mathcal{O}_L(\bar{\beta},x_i)),+1) \le\\
&\sum_{i:y_i = +1}\sum_{j \in N_i} l(g_{\bar{\beta}}
(\mathcal{O}_L(\bar{\beta},x_i)),+1),
\end{align*}
since $\mathcal{O}_L(\bar{\beta},x_i) \in N_i$ for all $i$ by
construction, and $l$ is an upper bound on $l_{01}$.
Putting everything together, we get the desired result.
\end{proof}

%We empirically evaluate the converging value of $P_A$ empirically as
%shown in Figure~\ref{fig:start}.

\begin{figure}[t]
\centering 
\begin{tabular}{cc}
\includegraphics[scale=0.19]{images/binary_start.png} &
\includegraphics[scale=0.19]{images/continuous_start.png} \\
(a) & (b)
\end{tabular}
\caption{The convergence of $P_A$ based on different number of starting points for (a) Binary, (b) Continuous feature space.}
\label{fig:start}
\end{figure}
Figure~\ref{fig:start} demonstrates that $p_L \rightarrow 0$
quite rapidly for an array of learning algorithms, and for either
discrete or continuous features, as we increase the number of restarts
$L$.
Consequently, in practice retraining with coordinate
greedy nearly minimizes an upper bound on minimal total adversarial
0/1 loss with relatively few restarts of the approximate attacker oracle.

%\begin{algorithm}[thb]
%\caption{Adversarial modification via Coordinate Descent $\mathcal{O}(x,\lambda,\beta)$}
%\label{alg:coordinate}
%\begin{algorithmic}[1]
%\STATE \textbf{Input}: {Malicious instance $x^A, \lambda, \beta$}
% \STATE {Set $k \leftarrow 0$ and let $x^0 \leftarrow x^A$}
% % \WHILE {$k < B$ and $f(x^k) \geq \delta$ }
% \REPEAT 
% % {$|f(x^A)-f(x^k)| \leq \delta$}
% \STATE{Randomly choose index $i_k \in \{1, 2, ..., n\}$ }
% \STATE{$x^{k+1} \leftarrow x^k - \tau_k {[\triangledown Q(x^k)]}_{i_k} e_{i_k}$}
% \STATE {$k \leftarrow k+1$}
% % \UNTIL {$|Q(x^{k})-Q(x^{k-1})| \leq \epsilon$ or $f(x^k) \leq \delta$}
% \UNTIL {$\frac{\ln Q(x^{k})} {\ln Q(x^{k-1})} \leq \epsilon$ or $f(x^k) \leq \delta$}
% % \ENDWHILE
% \STATE {Project $x^{k}$ to the feature space $x' \in X$}
% \STATE \textbf{Output}: {Adversarially optimal instance $x'$.}
%\end{algorithmic}
%\end{algorithm}

%Without loss of generality, we will keep use $\beta$ to denote the parameter set of any learning algorithm for simplicity here.
%Within the algorithm $\tau_k$ is the step size and $e_{i_k}$ is the direction and in our situation, it can be viewed as 1 for each feature dimension. The partial derivation function ${[\triangledown Q(x^k)]}_{i_k}$ corresponds to different learning algorithms and $\lambda$ is the cost sensitive parameter for attacker. 

%To minimize the loss when learning with such adversarial invariances, the learner would apply a retraining strategy to minimize its loss using Algorithm~\ref{algo:retraining}. This retraining process is highly scalable and computationally efficient compared with the constraint generation approach, but may obtain larger loss within an upper bound. 

%We will then discuss the coordinate descent details for different learning models based on different feature spaces. Since the attacker's goal is to minimize $f(x')$ to evade the classifier as well as minimize the modification cost $c(x^A,x')$, the attacker needs to solve the following optimization problem.
%\begin{equation}
%\min \limits_{x'} Q(x') := f(x') +e^{\lambda \sqrt{\sum \limits_{i = 1}^n{ (x^A}_i -{x'}_i)^2 +1}}
%\end{equation}

%Therefore 
%\begin{equation}
%\begin{scriptsize}
%\begin{aligned}
%&{[\triangledown Q(x^k)]}_{i_k} = {[\triangledown f(x^k)]}_{i_k} \\
%- &\exp \left({\lambda \sqrt{\sum \limits_{i = 1}^n{ (x^A}_i -{x'}_i)^2 +1}} \right) \cdot \lambda \frac{{x^A}_i - {x'}_i}{\sqrt{\sum \limits_{i = 1}^n{ (x^A}_i -{x'}_i)^2 +1}} 
%\end{aligned}
%\end{scriptsize}
%\end{equation}

% % svm linear results for enron based on model 2
% \begin{figure}[t]
% \centering 
% \begin{tabular}{cc}
% \includegraphics[scale=0.19]{images/binary2_enron_svm1000.png} &
% \includegraphics[scale=0.19]{images/binary2_enron_svm2000.png} \\
% (a) & (b)
% \end{tabular}
% \caption{SVM linear performance based on different adversarial cost sensitivity $\lambda$ for Enron dataset with different number of binary features as (a) 1000, (b) 2000.}
% \label{fig:ridge_enron}
% \end{figure}

% \section{Continuous Feature Space}
% \label{continuous}



% \begin{algorithm}[thb]
% \caption{Adversarial modification via Coordinate Descent}
% \label{alg:coordinate}
% \begin{algorithmic}[1]
% \STATE \textbf{Input}: {Malicious instance $x^A$}
%  \WHILE{$l \leq Q$}
%  \STATE {Set $k \leftarrow 0$ and let $x^0 \leftarrow x^A$}
%  % \WHILE {$|f(x^A)-f(x^k)| \leq \delta$}
%  \STATE{Randomly choose index $i_k \in \{k_1, k_2, ..., k_m\} = M$ and $|M| \leq B$ }
%  \REPEAT
%  \STATE{$x^{k+1} \leftarrow x^k - \beta_k {[\triangledown f(x^k)]}_{i_k} e_{i_k}$}
%  \STATE {$k \leftarrow k+1$}
%  % \ENDWHILE
%  \UNTIL{$|f(x^{k})-f(x^{k-1})| \leq \epsilon$ or $f(x^k) < \delta$}
%  \STATE {$l \leftarrow l+1$}
%  \ENDWHILE
%  \STATE {Project $x^k$ to the feature space $x' \in X$}
%  \STATE \textbf{Output}: {Adversarially optimal instance $x'$.}
% \end{algorithmic}
% \end{algorithm}

% % (this is for randomly choosing B features to modify, or should we randomly one by one till B?)

% \begin{algorithm}[thb]
% \caption{Adversarial modification via Coordinate Descent}
% \label{alg:coordinate}
% \begin{algorithmic}[1]
% \STATE \textbf{Input}: {Malicious instance $x^A$}
%  \STATE {Set $k \leftarrow 0$ and let $x^0 \leftarrow x^A$}
%  \WHILE {$k < B$ and $f(x^k) \geq \delta$ }
%  \REPEAT 
%  % {$|f(x^A)-f(x^k)| \leq \delta$}
%  \STATE{Randomly choose index $i_k$ }
%  \STATE{$x^{k+1} \leftarrow x^k - \beta_k {[\triangledown f(x^k)]}_{i_k} e_{i_k}$}
%  \STATE {$k \leftarrow k+1$}
%  \UNTIL {$|f(x^{k})-f(x^{k-1})| \leq \epsilon$}
%  \ENDWHILE
%  \STATE {Project $x^{k}$ to the feature space $x' \in X$}
%  \STATE \textbf{Output}: {Adversarially optimal instance $x'$.}
% \end{algorithmic}
% \end{algorithm}

% \begin{algorithm}[thb]
% \caption{Adversarial modification via Coordinate Descent}
% \label{alg:coordinate}
% \begin{algorithmic}[1]
% \STATE \textbf{Input}: {Malicious instance $x^A$}
%  \STATE {Set $k \leftarrow 0$ and let $x^0 \leftarrow x^A$}
%  \WHILE {$d(x^k, x^A) < B$ and $f(x^k) \geq \delta$ }
%  \REPEAT 
%  % {$|f(x^A)-f(x^k)| \leq \delta$}
%  \STATE{Randomly choose index $i_k$ }
%  \STATE{$x^{k+1} \leftarrow x^k - \beta_k {[\triangledown f(x^k)]}_{i_k} e_{i_k}$}
%  \STATE {$k \leftarrow k+1$}
%  \UNTIL {$|f(x^{k})-f(x^{k-1})| \leq \epsilon$}
%  \ENDWHILE
%  \STATE {Project $x^{k}$ to the feature space $x' \in X$}
%  \STATE \textbf{Output}: {Adversarially optimal instance $x'$.}
% \end{algorithmic}
% \end{algorithm}

% Here $d(x_1, x_2) = \sqrt{\sum \limits_{i = 1}^n ({x_1}_i-{x_2}_i)^2}$

% \begin{algorithm}[thb]
% \caption{Adversarial modification via Coordinate Descent}
% \label{alg:coordinate}
% \begin{algorithmic}[1]
% \STATE \textbf{Input}: {Malicious instance $x^A$}
%  \STATE {Set $k \leftarrow 0$ and let $x^0 \leftarrow x^A$}
%  % \WHILE {$k < B$ and $f(x^k) \geq \delta$ }
%  \REPEAT 
%  % {$|f(x^A)-f(x^k)| \leq \delta$}
%  \STATE{Randomly choose index $i_k \in \{1, 2, ..., n\}$ }
%  \STATE{$x^{k+1} \leftarrow x^k - \beta_k {[\triangledown R(x^k)]}_{i_k} e_{i_k}$}
%  \STATE {$k \leftarrow k+1$}
%  \UNTIL {$|R(x^{k})-R(x^{k-1})| \leq \epsilon$ or $f(x^k) \geq \delta$}
%  % \ENDWHILE
%  \STATE {Project $x^{k}$ to the feature space $x' \in X$}
%  \STATE \textbf{Output}: {Adversarially optimal instance $x'$.}
% \end{algorithmic}
% \end{algorithm}

\subsubsection{Continuous Feature Space}
\label{sub:continuous}

For continuous feature space, we assume that both $f(x)$ and
$c(x,\cdot)$ are differentiable in $x$, and propose using the \emph{coordinate descent}
algorithm, which is a special case of coordinate greedy, where the
GreedyImprove step is:
\[
x^{k+1} \leftarrow x^k - \tau_k e_{i_k} \frac{\partial
  Q(x^k)}{\partial x^k_{i_k}},
%{[\triangledown Q(x^k)]}_{i_k}
%e_{i_k},
\]
where $\tau_k$ is the step size and $e_{i_k}$ the direction of $i_k$th
coordinate.
Henceforth, let the origial adversarial instance $x_i$ be given; we
then simplify cost function to be only a function of $x$, denoted $c(x)$.
If the function $f(x)$ is convex and differentiable, our coordinate
descent based algorithm~\ref{alg:coordinate} can always find the
global optima which is the attacker best response $x^*$
\cite{luo1992convergence}, and Proposition~\ref{prop:defender_loss}
applies, by Corollary~\ref{C:convex}.
If $f(x)$ is not convex, then coordinate descent will only converge
to a local optimum.
%However, with random restarts, we can considerably improve solutions
%by choosing the best of several local optima.

%it cannot guarantee that the adversary best response $x^*$ can always
%be found.
% We will discuss these special cases in section~\ref{sub:continuous} and~\ref{sub:discrete}.
%If $f(x)$ is not convex, we will empirically evaluate the 0-1 loss for the defender's loss.

%\begin{equation}
%\begin{scriptsize}
%\begin{aligned}
%&{[\triangledown Q(x^k)]}_{i_k} = {[\triangledown f(x^k)]}_{i_k} \\
%- &\exp \left({\lambda \sqrt{\sum \limits_{i = 1}^n{ (x^A}_i -{x'}_i)^2 +1}} \right) \cdot \lambda \frac{{x^A}_i - {x'}_i}{\sqrt{\sum \limits_{i = 1}^n{ (x^A}_i -{x'}_i)^2 +1}} 
%\end{aligned}
%\end{scriptsize}
%\end{equation}
Now, $\frac{\partial
  Q(x^k)}{\partial x^k_{i_k}} = \frac{\partial
  f(x^k)}{\partial x^k_{i_k}} + \frac{\partial
  c(x^k)}{\partial x^k_{i_k}}$.
Fixing a coordinate $j = i_k$, we derive the partial derivative of
$f(x)$ with respect to coordinate $j$ for several common learning
algorithms, and derive the derivative of $c(x)$ for several natural
cost functions.

%If the feature space is continuous as $X \subseteq R^n$, we need to
%derive ${[\triangledown f(x^k,\beta)]}_{i_k}$ according to different
%learning models.

\paragraph{Kernel SVM}

Consider a general Kernel SVM decision function, for which $f(x) =
\sum_i a_i y_i K(x_i,x)$, where $x_i, y_i$ are the support training data
points, $a_i$ the associated dual SVM parameters, and $K(\cdot,\cdot)$
a kernel function.
Then, $\frac{\partial f(x)}{\partial x_j} = \sum_i a_i y_i
\frac{\partial K(x_i,x)}{\partial x_j}$.
For a linear Kernel, $\frac{\partial K(x_i,x)}{\partial x_j} = x_{ij}$.
For a polynomial Kernal, $\frac{\partial K(x_i,x)}{\partial x_j} = d(c
+ x_i \cdot x)^d x_{ij}$.
For an RBF Kernel, $\frac{\partial K(x_i,x)}{\partial x_j} =
\frac{1}{\sigma^2}K(x_i,x)(x_{ij} - x_j)$.

\paragraph{Logistic Regression}
Given a logistic regression model, for which $f(x) = \frac{1}{1+e^{-\theta^T x}}$, where $\theta$ is the learning parameter. We have $\frac{\partial K(x_i,x)}{\partial x_j} = \frac{\theta_j \cdot e^{-\theta^T x}}{(1+e^{-\theta^T x})^2}$


% \paragraph{Ridge Regression}

% For example, for the Ridge regression $y = {\frac{1}{2} (y-w^Tx)^2 + {||w||}_2}$
% \begin{equation}
% {[\triangledown f(x^k,w)]}_{i_k} = -(y-w^Tx)w_i.
% \end{equation}
% For Bayesian regression $y = x^T A + \epsilon$, where $\epsilon_i \sim N(0,\sigma^2)$,
% \begin{equation}
% {[\triangledown f(x^k,A)]}_{i_k} = A_i.
% \end{equation}
% Note that the estimated coefficient can be derived as $A = {(X^T X)}^{-1} X^T y$.

% For the linear-SVM, $y = \frac{1}{2} w^T w + C \sum \limits_{i = 1}^l \max(1-y_i w^T x_i,0)$,
% \begin{equation}
% {[\triangledown f(x^k,w)]}_{i_k} = C \cdot 
% \begin{cases}
% -y_i w_i ;  &\text{if}\ 1-y_i w^T x_i\ge 0 \\
% 0 ;  &\text{otherwise}
% \end{cases}
% \end{equation}

\paragraph{Neural Network}

For the neural network with sigmoid function as the activation function, if there are three hidden layers,
$g(x) = (1+e^{-h_3(x)})^{-1}$, \\
$h_3(x) = \sum \limits_{t = 1}^{d_3} {w_3}_t {\delta_3}_t (x) +b_3$, \\
${\delta_3}_t (x)= (1+e^{-{h_2}_t(x)})^{-1}$, \\
${h_2}_t(x) = \sum \limits_{j = 1}^{d_2} {w_2}_j {\delta_2}_j (x) +b_2$, \\
${\delta_2}_j (x)= (1+e^{-{h_1}_j(x)})^{-1}$, \\
${h_1}_j(x) = \sum \limits_{p = 1}^{d_1} {w_1}_p {\delta_1}_p (x) +b_1$, \\
${\delta_1}_p (x)= (1+e^{-{h_0}_p(x)})^{-1}$, \\
${h_0}_p(x) = \sum \limits_{l = 1}^{n} {w_1}_l x_l +b_0$, \\

Therefore we have
\begin{equation}
\begin{scriptsize}
\begin{aligned}
&{[\triangledown f(x^k,\beta)]}_{i_k} = g(x)(1-g(x)) \sum \limits_{t = 1}^{d_3} {w_{k_3}}_t {\delta_{k_3}}_t(1-{\delta_{k_3}}_t) \\
&\sum \limits_{j = 1}^{d_2} {w_{k_2}}_j {\delta_{k_2}}_j(1-{\delta_{k_2}}_j) \sum \limits_{p = 1}^{d_1} {w_{k_1}}_p {\delta_{k_1}}_p(1-{\delta_{k_1}}_p) {w_{k_0}}_i.
\end{aligned}
\end{scriptsize}
\end{equation}


For the neural network with rectified linear unit (ReLU) function as the activation function, if there are three hidden layers,
$g(x) = \max(0,h_3(x))$, \\
$h_3(x) = \sum \limits_{t = 1}^{d_3} {w_3}_t {\delta_3}_t (x) +b_3$, \\
${\delta_3}_t (x)= \max(0,{h_2}_t(x))$, \\
${h_2}_t(x) = \sum \limits_{j = 1}^{d_2} {w_2}_j {\delta_2}_j (x) +b_2$, \\
${\delta_2}_j (x)= \max(0,{h_1}_j(x))$, \\
${h_1}_j(x) = \sum \limits_{p = 1}^{d_1} {w_1}_p {\delta_1}_p (x) +b_1$, \\
${\delta_1}_p (x)= \max(0,{h_0}_p(x))$, \\
${h_0}_p(x) = \sum \limits_{l = 1}^{n} {w_1}_l x_l +b_0$, \\

Therefore we have when 
\begin{equation*}
\centering
\begin{scriptsize}
\begin{aligned}
&{[\triangledown f(x^k,\beta)]}_{i_k}  \\
&=
\begin{cases}
 h_3(x) & \sum \limits_{t = 1}^{d_3} {w_3}_t {h_2}_t(x) \sum \limits_{j = 1}^{d_2} {w_2}_j {h_1}_j(x)  \sum \limits_{p = 1}^{d_1} {w_1}_p {h_0}_p(x) {w_{k_0}}_i, \\
 & \text{if}\ {h_3}(x) \cdot \sum \limits_{t = 1}^{d_3} {h_2}_t(x) \cdot \sum \limits_{j = 1}^{d_2} {h_1}_j(x) \cdot \sum \limits_{p = 1}^{d_1} {h_0}_p(x) \ne 0\\
 0, \ &\text{otherwise}.
\end{cases}
\end{aligned}
\end{scriptsize}
\end{equation*}

% % Ridge results for enron
% \begin{figure}[t]
% \centering 
% \begin{tabular}{cc}
% \includegraphics[scale=0.19]{images/ridge_enron1000.png} &
% \includegraphics[scale=0.19]{images/ridge_enron2000.png} \\
% (a) & (b)
% \end{tabular}
% \caption{Ridge regression performance based on different adversarial cost sensitivity $\lambda$ for Enron dataset with different number of features as (a) 100, (b) 2000.}
% \label{fig:ridge_enron}
% \end{figure}

% % Ridge results for mnist

% \begin{figure}[t]
% \centering 
% \begin{tabular}{cc}
% \includegraphics[scale=0.19]{images/ridge_mnist627.png} &
% \includegraphics[scale=0.19]{images/ridge_mnist784.png} \\
% (a) & (b)
% \end{tabular}
% \caption{Ridge regression performance based on different adversarial cost sensitivity $\lambda$ for MNIST dataset with different number of features as (a) 627, (b) 784.}
% \label{fig:ridge_mnist}
% \end{figure}

% \begin{figure}[t]
% \centering 
% \begin{tabular}{cccc}
% \includegraphics[scale=1.00]{images/ridge/0.png} &
% \includegraphics[scale=1.00]{images/ridge/1.png} &
% \includegraphics[scale=1.00]{images/ridge/2.png} &
% \includegraphics[scale=1.00]{images/ridge/3.png} \\
% \includegraphics[scale=1.00]{images/ridge/4.png} &
% \includegraphics[scale=1.00]{images/ridge/5.png} &
% \includegraphics[scale=1.00]{images/ridge/6.png} &
% \includegraphics[scale=1.00]{images/ridge/8.png} \\
% \end{tabular}
% \caption{Modification process of attacker for Ridge regression based by decreasing the cost sensitivity parameter $\lambda$.}
% \label{fig:visual_ridge}
% \end{figure}

% % Bayesian results for enron
% \begin{figure}[t]
% \centering 
% \begin{tabular}{cc}
% \includegraphics[scale=0.19]{images/bayesian_enron1000.png} &
% \includegraphics[scale=0.19]{images/bayesian_enron2000.png} \\
% (a) & (b)
% \end{tabular}
% \caption{Bayesian regression performance based on different adversarial cost sensitivity $\lambda$ for Enron dataset with different number of features as (a) 1000, (b) 2000.}
% \label{fig:bayesian_enron}
% \end{figure}

% % Bayesian results for mnist

% \begin{figure}[t]
% \centering 
% \begin{tabular}{cc}
% \includegraphics[scale=0.19]{images/Bayesian_mnist627.png} &
% \includegraphics[scale=0.19]{images/Bayesian_mnist784.png} \\
% (a) & (b)
% \end{tabular}
% \caption{Bayesian regression performance based on different adversarial cost sensitivity $\lambda$ for MNIST dataset with different number of features as (a) 627, (b) 784.}
% \label{fig:bayesian_mnist}
% \end{figure}

% \begin{figure}[t]
% \centering 
% \begin{tabular}{cccc}
% \includegraphics[scale=1.00]{images/bayesian/0.png} &
% \includegraphics[scale=1.00]{images/bayesian/1.png} &
% \includegraphics[scale=1.00]{images/bayesian/3.png} &
% \includegraphics[scale=1.00]{images/bayesian/5.png} \\
% \includegraphics[scale=1.00]{images/bayesian/6.png} &
% \includegraphics[scale=1.00]{images/bayesian/8.png} &
% \includegraphics[scale=1.00]{images/bayesian/9.png} &
% \includegraphics[scale=1.00]{images/bayesian/10.png} \\
% \end{tabular}
% \caption{Modification process of attacker for Bayesian regression based by decreasing the cost sensitivity parameter $\lambda$.}
% \label{fig:visual_bayesian}
% \end{figure}

% % svm-linear results for enron
% \begin{figure}[t]
% \centering 
% \begin{tabular}{cc}
% \includegraphics[scale=0.19]{images/svm_enron1000.png} &
% \includegraphics[scale=0.19]{images/svm_enron2000.png} \\
% (a) & (b)
% \end{tabular}
% \caption{SVM performance based on different adversarial cost sensitivity $\lambda$ for Enron dataset with different number of features as (a) 1000, (b) 2000.}
% \label{fig:svm_enron}
% \end{figure}

% % svm-linear results for mnist
% % chenge below
% \begin{figure}[t]
% \centering 
% \begin{tabular}{cc}
% \includegraphics[scale=0.19]{images/svm_mnist627.png} &
% \includegraphics[scale=0.19]{images/svm_mnist784.png} \\
% (a) & (b)
% \end{tabular}
% \caption{SVM performance based on different adversarial cost sensitivity $\lambda$ for MNIST dataset with different number of features as (a) 627, (b) 784.}
% \label{fig:svm_mnist}
% \end{figure}

% \begin{figure}[t]
% \centering 
% \begin{tabular}{cccc}
% \includegraphics[scale=1.00]{images/svm/0.png} &
% \includegraphics[scale=1.00]{images/svm/1.png} &
% \includegraphics[scale=1.00]{images/svm/3.png} &
% \includegraphics[scale=1.00]{images/svm/4.png} \\
% \includegraphics[scale=1.00]{images/svm/5.png} &
% \includegraphics[scale=1.00]{images/svm/6.png} &
% \includegraphics[scale=1.00]{images/svm/7.png} &
% \includegraphics[scale=1.00]{images/svm/8.png} \\
% \end{tabular}
% \caption{Modification process of attacker for SVM based by decreasing the cost sensitivity parameter $\lambda$.}
% \label{fig:visual_svm}
% \end{figure}

\subsection{Discrete Feature Space}
\label{sub:discrete}

If the feature space is binary as $X \subseteq \{0,1\}^n$, the attacker would solve the relaxation problem for~\ref{eq:attacker_model} and then project the optimized feature to the binary space.
Therefore, the attacker will apply the similar algorithm Algorithm~\ref{alg:coordinate} and project the feature back to $\{0,1\}$ by thresholding during the 8\emph{th} step in Algorithm~\ref{alg:coordinate}. 

%\begin{proposition}
%\label{prop:defender_loss_discrete}
%The upper bound of defender's loss in adversarial environments is 
%% $L_D \leq \sum \limits_{y_i = -1} l(-w^T x_i) + \sum \limits_{y_i = +1} \max \limits_{{x_i}' \in {x_i}^*} l(w^T {x_i}') + \lambda ||w||_p $.
%${L_D}^A \leq \sum \limits_{x_i \in X \cup R} l_\beta( x_i) + \alpha ||\beta||_p + t \cdot {P}_A$ for binary feature space, where $X$ is the original training set and $R$ represents the total added instances. $t$ denotes the number of malicious instances in $X$ ($t = |X_A|$), and $P_A$ is the probability that the best response $x^*$ would evade the classifier. 
%\end{proposition}
%The proof is similar with that for proposition~\ref{prop:defender_loss_continuous}.
%Figure~\ref{fig:start} shows the converging value of $P_A$ empirically. It is shown that after at most 20 random starts, all different learning models are able to find the best response $x^*$ and Neural Network for both continuous and discrete feature space can even converge with 5 random starts.

% \begin{algorithm}[thbf]
% \caption{Adversarial modification via Coordinate Descent Projection $\mathcal{O}(x,\lambda,\beta)$}
% \label{alg:coordinate}
% \begin{algorithmic}[1]
% \STATE \textbf{Input}: {Malicious instance $x^A, \lambda, \beta$}
%  \STATE {Set $k \leftarrow 0$ and let $x^0 \leftarrow x^A$}
%  % \WHILE {$k < B$ and $f(x^k) \geq \delta$ }
%  \REPEAT 
%  % {$|f(x^A)-f(x^k)| \leq \delta$}
%  \STATE{Randomly choose index $i_k \in \{1, 2, ..., n\}$ }
%  \STATE{$x^{k+1} \leftarrow x^k - \tau_k {[\triangledown Q(x^k)]}_{i_k} e_{i_k}$}
%  \STATE {$k \leftarrow k+1$}
%  % \UNTIL {$|Q(x^{k})-Q(x^{k-1})| \leq \epsilon$ or $f(x^k) \leq \delta$}
%  \UNTIL {$\frac{\ln Q(x^{k})} {\ln Q(x^{k-1})} \leq \epsilon$ or $f(x^k) \leq \delta$}
%  % \ENDWHILE
%  \STATE {Project $x^{k}$ to the binary feature space by thresholding}
%  \STATE \textbf{Output}: {Adversarially optimal instance $x'$.}
% \end{algorithmic}
% \end{algorithm}  


% the lambda results for different models convergence.

nips_2016_retraining.bbl
\begin{thebibliography}{10}

\bibitem{fawcett1997adaptive}
Tom Fawcett and Foster Provost.
\newblock Adaptive fraud detection.
\newblock {\em Data mining and knowledge discovery}, 1(3):291--316, 1997.

\bibitem{mahoney2002learning}
Matthew~V Mahoney and Philip~K Chan.
\newblock Learning nonstationary models of normal network traffic for detecting
  novel attacks.
\newblock In {\em Proceedings of the eighth ACM SIGKDD international conference
  on Knowledge discovery and data mining}, pages 376--385. ACM, 2002.

\bibitem{fogla2006polymorphic}
Prahlad Fogla, Monirul~I Sharif, Roberto Perdisci, Oleg~M Kolesnikov, and Wenke
  Lee.
\newblock Polymorphic blending attacks.
\newblock In {\em USENIX Security}, 2006.

\bibitem{huang2011adversarial}
Ling Huang, Anthony~D Joseph, Blaine Nelson, Benjamin~IP Rubinstein, and
  JD~Tygar.
\newblock Adversarial machine learning.
\newblock In {\em Workshop on Security and Artificial Intelligence}, pages
  43--58. ACM, 2011.

\bibitem{kolcz2009feature}
Aleksander Ko{\l}cz and Choon~Hui Teo.
\newblock Feature weighting for improved classifier robustness.
\newblock In {\em CEAS’09: sixth conference on email and anti-spam}, 2009.

\bibitem{lowd2005adversarial}
Daniel Lowd and Christopher Meek.
\newblock Adversarial learning.
\newblock In {\em Proceedings of the eleventh ACM SIGKDD international
  conference on Knowledge discovery in data mining}, pages 641--647. ACM, 2005.

\bibitem{karlberger2007exploiting}
Christoph Karlberger, G{\"u}nther Bayler, Christopher Kruegel, and Engin Kirda.
\newblock Exploiting redundancy in natural language to penetrate bayesian spam
  filters.
\newblock {\em WOOT}, 7:1--7, 2007.

\bibitem{nelson2012query}
Blaine Nelson, Benjamin~IP Rubinstein, Ling Huang, Anthony~D Joseph, Steven~J
  Lee, Satish Rao, and JD~Tygar.
\newblock Query strategies for evading convex-inducing classifiers.
\newblock {\em The Journal of Machine Learning Research}, 13(1):1293--1332,
  2012.

\bibitem{el2003robust}
Laurent El~Ghaoui, Gert Ren{\'e}~Georges Lanckriet, Georges Natsoulis, et~al.
\newblock {\em Robust classification with interval data}.
\newblock Computer Science Division, University of California, 2003.

\bibitem{li2014feature}
Bo~Li and Yevgeniy Vorobeychik.
\newblock Feature cross-substitution in adversarial classification.
\newblock In {\em Advances in Neural Information Processing Systems}, pages
  2087--2095, 2014.

\bibitem{li2015scalable}
Bo~Li and Yevgeniy Vorobeychik.
\newblock Scalable optimization of randomized operational decisions in
  adversarial classification settings.
\newblock In {\em Proceedings of the Eighteenth International Conference on
  Artificial Intelligence and Statistics}, pages 599--607, 2015.

\bibitem{teo2007convex}
Choon~H Teo, Amir Globerson, Sam~T Roweis, and Alex~J Smola.
\newblock Convex learning with invariances.
\newblock In {\em Advances in neural information processing systems}, pages
  1489--1496, 2007.

\bibitem{globerson2006nightmare}
Amir Globerson and Sam Roweis.
\newblock Nightmare at test time: robust learning by feature deletion.
\newblock In {\em Proceedings of the 23rd international conference on Machine
  learning}, pages 353--360. ACM, 2006.

\bibitem{bruckner2011stackelberg}
Michael Br{\"u}ckner and Tobias Scheffer.
\newblock Stackelberg games for adversarial prediction problems.
\newblock In {\em Proceedings of the 17th ACM SIGKDD international conference
  on Knowledge discovery and data mining}, pages 547--555. ACM, 2011.

\bibitem{biggio2014security}
Battista Biggio, Giorgio Fumera, and Fabio Roli.
\newblock Security evaluation of pattern classifiers under attack.
\newblock {\em Knowledge and Data Engineering, IEEE Transactions on},
  26(4):984--996, 2014.

\bibitem{goodfellow2014explaining}
Ian~J Goodfellow, Jonathon Shlens, and Christian Szegedy.
\newblock Explaining and harnessing adversarial examples.
\newblock {\em arXiv preprint arXiv:1412.6572}, 2014.

\bibitem{Kantchelian15}
A.~Kantchelian, J.~D. Tygar, and A.~D. Joseph.
\newblock Evasion and hardening of tree ensemble classifiers.
\newblock arXiv pre-print, 2015.

\bibitem{klimt2004enron}
Bryan Klimt and Yiming Yang.
\newblock The enron corpus: A new dataset for email classification research.
\newblock In {\em Machine learning: ECML 2004}, pages 217--226. Springer, 2004.

\bibitem{lecun2010mnist}
Yann LeCun and Corinna Cortes.
\newblock Mnist handwritten digit database.
\newblock {\em AT\&T Labs [Online]. Available: http://yann. lecun.
  com/exdb/mnist}, 2010.

\bibitem{ke2016behavioral}
Liyiming Ke, Bo~Li, and Yevgeniy Vorobeychik.
\newblock Behavioral experiments in email filter evasion.
\newblock In {\em AAAI Conference on Artificial Intelligence}, 2016.

\bibitem{dalvi2004adversarial}
Nilesh Dalvi, Pedro Domingos, Sumit Sanghai, Deepak Verma, et~al.
\newblock Adversarial classification.
\newblock In {\em Proceedings of the tenth ACM SIGKDD international conference
  on Knowledge discovery and data mining}, pages 99--108. ACM, 2004.

\bibitem{luo1992convergence}
Zhi-Quan Luo and Paul Tseng.
\newblock On the convergence of the coordinate descent method for convex
  differentiable minimization.
\newblock {\em Journal of Optimization Theory and Applications}, 72(1):7--35,
  1992.

\bibitem{Boyd04}
Stephen Boyd and Lieven Vandenberghe.
\newblock {\em Convex Optimization}.
\newblock Cambridge University Press, 2004.

\end{thebibliography}
