Defending SVMs Against Poisoning Attacks: The Hardness and DBSCAN Approach

In the past decades we have witnessed enormous progress in machine learning. One driving force behind this is the successful applications of machine learning technologies to many different fields, such as data mining, networking, and bioinformatics. However, with its territory rapidly enlarging, machine learning has also imposed a number of new challenges. In particular, adversarial machine learning which concerns about the potential vulnerabilities of the algorithms, has attracted a great amount of attention [Barreno et al., 2006, Huang et al., 2011, Biggio and Roli, 2018, Goodfellow et al., 2018]. As mentioned in the survey paper [Biggio and Roli, 2018], the very first work of adversarial machine learning dates back to 2004, in which Dalvi et al. [2004] formulated the adversarial classification problem as a game between the classifier and the adversary. In general, the adversarial attacks against machine learning can be categorized to evasion attacks and poisoning attacks [Biggio and Roli, 2018]. An evasion attack happens at test time, where the adversary aims to evade the trained classifier by manipulating test examples. For example, Szegedy et al. [2014] observed that small perturbation to a test image can arbitrarily change the neural network’s prediction.

In this paper, we focus on poisoning attacks that happen at training time. Usually, the adversary injects a small number of specially crafted samples into the training data which can make the decision boundary severely deviate and cause unexpected misclassification. In particular, because open datasets are commonly used to train our machine learning algorithms nowadays, poisoning attack has become a key security issue that seriously limits real-world applications [Biggio and Roli, 2018]. For instance, even a small number of poisoning samples can significantly increase the test error of support vector machine (SVM) [Biggio et al., 2012, Mei and Zhu, 2015, Xiao et al., 2012]. Beyond linear classifiers, a number of works studied the poisoning attacks for other machine learning problems, such as clustering [Biggio et al., 2014], PCA [Rubinstein et al., 2009], and regression [Jagielski et al., 2018].

Though lots of works focused on constructing poisoning attacks, our ultimate goal is to design defenses. Poisoning samples can be regarded as outliers, and this leads to two natural approaches to defend: (1) data sanitization defense, i.e., first perform outlier removal and then run an existing machine learning algorithm on the cleaned data [Cretu et al., 2008], or (2) directly design a robust optimization algorithm that is resilient against outliers [Christmann and Steinwart, 2004, Jagielski et al., 2018].

Steinhardt et al. [2017] studied two basic methods of data sanitization defense, which remove the points outside a specified sphere or slab, for binary classification; they showed that high dimensionality gives attacker more room for constructing attacks to evade outlier removal. Laishram and Phoha [2016] applied the seminal DBSCAN (Density-Based Spatial Clustering of Applications with Noise) method [Ester et al., 1996] to remove outliers for SVM and showed that it can successfully identify most of the poisoning data. However, their DBSCAN approach is lack of theoretical analysis. Several other outlier removal methods for fighting poisoning attacks have also been studied recently [Paudice et al., 2018b, a]. Also, it is worth noting that outlier removal actually is a topic that has been extensively studied in various fields before [Chandola et al., 2009].

The other defense strategy, designing robust optimization algorithms, also has a long history in the machine learning community. A substantial part of robust optimization algorithms rely on the idea of regularization. For example, Xu et al. [2009] studied the relation between robustness and regularization for SVM; other robust SVM algorithms include [Tax and Duin, 1999, Xu et al., 2006, Suzumura et al., 2014, Natarajan et al., 2013, Xu et al., 2017, Kanamori et al., 2017]. However, as discussed in [Mei and Zhu, 2015, Jagielski et al., 2018], these approaches are not quite ideal to defend against poisoning attacks since the outliers can be located arbitrarily in the feature space by the adversary. Another idea for achieving the robustness guarantee is to add strong assumptions about the data distribution or the attacker’s behavior [Feng et al., 2014, Weerasinghe et al., 2019], but these assumptions are usually not well satisfied in practice. An alternative approach is to explicitly remove outliers during optimization, such as the “trimmed” method for robust regression [Jagielski et al., 2018]; but this approach often results in a challenging combinatorial optimization problem: if $z$ of the input $n$ data items are outliers ($z<n$), we have to consider an exponentially large number ${n\choose z}$ of different possible cases in the adversarial setting.

Given two point sets $P^{+}$ and $P^{-}$ in $\mathbb{R}^{d}$, the problem of linear support vector machine (SVM) [Chang and Lin, 2011] is to find the maximum margin separating these two point sets (if they are separable). If $P^{+}$ (or $P^{-}$) is a single point, say the origin, the problem is called one-class SVM. The SVM can be formulated as a quadratic programming problem, and a number of efficient techniques have been developed in the past, such as the soft margin SVM [Cortes and Vapnik, 1995], $\nu$-SVM [Scholkopf et al., 2000, Crisp and Burges, 1999], and Core-SVM [Tsang et al., 2005]. If $P^{+}$ and $P^{-}$ are not separable, we can apply the kernel method: each point $p\in P^{+}\cup P^{-}$ is mapped to be $\phi(p)$ in a higher dimensional space; the inner product $\langle\phi(p_{1}),\phi(p_{2})\rangle$ is defined by a kernel function $\mathcal{K}(p_{1},p_{2})$. Many existing SVM algorithms can be adapted to handle the non-separable case by using kernel functions.

Poisoning attacks. The adversary usually injects some bad points to the original data set $P^{+}\cup P^{-}$. For instance, the adversary can take a sample $q$ from the domain of $P^{+}$, and flip its label to be “$-$”; therefore, this poisoning sample $q$ can be viewed as an outlier of $P^{-}$. Since poisoning attack is expensive, we often assume that the adversary can poison at most $z\in\mathbb{Z}^{+}$ points (or the poisoned fraction $\frac{z}{|P^{+}\cup P^{-}|}$ is a fixed small number in $(0,1)$). We can formulate the defense against poisoning attacks as the following combinatorial optimization problem. As mentioned in Section 1.1, it is sufficient to consider only the simpler hard-margin case for studying its hardness.

We also need to clarify the intrinsic dimensionality for our following analysis. Doubling dimension is a measure of intrinsic dimensionality that has been widely adopted in the learning theory community [Bshouty et al., 2009]. Given a point $p$ and $r\geq 0$, we use $\mathbb{B}(p,r)$ to indicate the ball of radius $r$ around $p$ in the space.

To understand doubling dimension, we consider the following simple case. If the points of $P$ distribute uniformly in a $d^{\prime}$-dimensional flat in $\mathbb{R}^{d}$, then it is easy to see that $P$ has the doubling dimension $\rho=O(d^{\prime})$, which is independent of the Euclidean dimension $d$ (e.g., $d$ can be much higher than $\rho$). Intuitively, doubling dimension is used for describing the expansion rate of a given point set in the space. It is worth noting that the intrinsic dimensionality described in [Amsaleg et al., 2017, Ma et al., 2018] is quite similar to doubling dimension, which also measures expansion rate.

In this section, we prove that even the one-class SVM with outliers problem is NP-complete and has no fully PTAS unless P$=$NP (that is, we cannot achieve a polynomial time $(1-\epsilon)$-approximation for any given $\epsilon\in(0,1)$). Our idea is partly inspired by the result from Megiddo [1990]. Given a set of points in $\mathbb{R}^{d}$, the “covering by two balls” problem is to determine that whether the point set can be covered by two unit balls. By the reduction from $3$-SAT, Megiddo proved that the “covering by two balls” problem is NP-complete. In the proof of the following theorem, we modify Megiddo’s construction of the reduction to adapt the one-class SVM with outliers problem.

Let $\Gamma$ be a $3$-SAT instance with the literal set $\{u_{1},\bar{u}_{1},\cdots,u_{l},\bar{u}_{l}\}$ and clause set $\{E_{1},\cdots,E_{m}\}$. We construct the corresponding instance $P_{\Gamma}$ of one-class SVM with outliers. First, let $U=\{\pm e_{i}\mid i=1,2,\cdots,l+1\}$ be the $2(l+1)$ unit vectors of $\mathbb{R}^{l+1}$, where each $e_{i}$ has “$1$” in the $i$-th position and “$0$” in other positions. Also, for each clause $E_{j}$ with $1\leq j\leq m$, we generate a point $q_{j}=(q_{j,1},q_{j,2},\cdots,q_{j,l+1})$ as follows. For $1\leq i\leq l$,

In addition, $q_{j,l+1}=3\alpha$. For example, if $E_{j}=u_{i_{1}}\vee\bar{u}_{i_{2}}\vee u_{i_{3}}$, the point

The value of $\alpha$ will be determined later. Let $Q$ denote the set $\{q_{1},\cdots,q_{m}\}$. Now, we construct the instance $P_{\Gamma}=U\cup Q$ of one-class SVM with outliers, where the number of points $n=2(l+1)+m$ and the number of outliers $z=l+1$. Then we have the following lemma.

Now we are ready to prove the theorem.

From Theorem 1, we know that it is extremely challenging to achieve the optimal solution even for one-class SVM with outliers. Therefore, we turn to consider the other approach, data sanitization defense, under some reasonable assumption in practice. First, we prove a general sampling theorem in Section 4.1. Then, we apply this theorem to explain the effectiveness of DBSCAN for defending against poisoning attacks in Section 4.2.

All the experiments were repeated $20$ times on a Windows $10$ workstation equipped with an Intel core $i5$-$8400$ processor and $8$GB RAM. To generate the poisoning attacks, we use the Min-Max attack from [Koh et al., 2018] and the adversarial label-flipping attack ALFA from ALFASVMLib [Xiao et al., 2015]. We evaluate the defending performances of the basic SVM algorithms and several different defenses by using their publicly available implementations.

1. 1.

   We consider both the cases that not using and using kernel. For SVM without kernel, we directly use linear SVM as the basic SVM algorithm; for SVM with kernel, we consider RBF kernel (rbf SVM). Both the implementations are from [Chang and Lin, 2011].

2. 2.

   The recently proposed robust SVM algorithm RSVM-$S$ based on the rescaled hinge loss function [Xu et al., 2017]. The parameter “$S$” indicates the iteration number of the half-quadratic optimization (e.g., we set $S=3$ and $10$ following their paper’s setting). The algorithm also works fine when using a kernel.

3. 3.

   The DBSCAN method [Schubert et al., 2017] implemented as Remark 3 (ii). We set $\mathtt{MinPts}=5$ (our empirical study finds that the difference is minor within the range $[3,10]$).

4. 4.

   The data sanitization defenses from [Koh et al., 2018] based on the spatial distribution of input data, which include Slab, L2, Loss, and k-NN.

For the data sanitization defenses, we run them on the poisoned data in the original input space; then, apply the basic SVM algorithm, linear SVM or rbf SVM (if using RBF kernel), on the cleaned data to compute their final solutions.

Datasets. We consider both the synthetic and real-world datasets in our experiments. For each synthetic dataset, we generate two manifolds in $\mathbb{R}^{d}$, and each manifold is represented by a random polynomial function with degree $d^{\prime}$ (the values of $d$ and $d^{\prime}$ will be varied in the experiments). Note that it is challenging to achieve the exact doubling dimensions of the datasets, and thus we use the degree of the polynomial function as a “rough indicator” for the doubling dimension (the higher the degree, the larger the doubling dimension). In each of the manifolds, we randomly sample $5000$ points; the data is randomly partitioned into $30\%$ and $70\%$ respectively for training and testing, and we report the classification accuracy on the test data. We also consider three real-world datasets from [Chang and Lin, 2011]. The details are shown in Table 1.

Results. First, we study the influence from the intrinsic dimensionality. We set the Euclidean dimensionality $d$ to be $100$ and vary the polynomial function’s degree $d^{\prime}$ from $25$ to $65$ in Figure 2a and 2d. Then, we fix the degree $d^{\prime}$ to be $40$ and vary the Euclidean dimensionality $d$ in Figure 2b and 2e. We can observe that the accuracies of most methods dramatically decrease when the degree $d^{\prime}$ (intrinsic dimension) increases, and the influence from the intrinsic dimension is more significant than that from the Euclidean dimension, which is in agreement with our theoretical analysis.

We also study their classification performances under different poisoned fraction in Figure 2c and 2f. We can see that all the defenses yield lower accuracies when the poisoned fraction increases, while the performance of DBSCAN keeps much more stable compared with other defenses. Moreover, we calculate the widely used $F_{1}$ scores from the sanitization defenses for identifying the outliers. Loss and k-NN both yield very low $F_{1}$ scores ($<0.1$); that means they are not quite capable to identify the real poisoning data items. The $F_{1}$ scores yielded by DBSCAN, L$2$ and Slab are shown in Figure 2g-2i, where DBSCAN in general outperforms the other two sanitization defenses for most cases.

We also perform the experiments on the real datasets under Min-Max attack with the poisoned fraction ranging from $4\%$ to $10\%$. The experimental results (Figure 3) reveal the similar trends as the results for the synthetic datasets, and DBSCAN keeps considerably better performance compared with other defenses. Due to the space limit, the results under ALFA attack are shown in Appendix.

In this paper, we study two different strategies for protecting SVM against poisoning attacks. We also have several open questions to study in future. For example, what about the complexities of other machine learning problems under the adversarially-resilient formulations as Definition 1? For many other adversarial machine learning problems, the study on their complexities is still in its infancy.