Abstract
Adversarial machine learning has attracted a great amount of attention in recent years. In a poisoning attack, the adversary can inject a small number of specially crafted samples into the training data which make the decision boundary severely deviate and cause unexpected misclassification. Due to the great importance and popular use of support vector machines (SVM), we consider defending SVM against poisoning attacks in this paper. We study two commonly used strategies for defending: designing robust SVM algorithms and data sanitization. Though several robust SVM algorithms have been proposed before, most of them either are in lack of adversarial-resilience, or rely on strong assumptions about the data distribution or the attacker's behavior. Moreover, the research on their complexities is still quite limited. We are the first, to the best of our knowledge, to prove that even the simplest hard-margin one-class SVM with outliers problem is NP-complete, and has no fully PTAS unless P=NP. For the data sanitization defense, we link it to the intrinsic dimensionality of data; in particular, we provide a sampling theorem in doubling metrics for explaining the effectiveness of DBSCAN (as a density-based outlier removal method) for defending against poisoning attacks. In our empirical experiments, we compare several defenses including the DBSCAN and robust SVM methods, and investigate the influences from the intrinsic dimensionality and data density to their performances.
Introduction
Machine learning models are increasingly trained on "open" datasets, making them vulnerable to poisoning attacks. In these scenarios, an adversary injects a small number of carefully crafted samples into the training set to skew the decision boundary, leading to misclassifications at test time. While researchers have proposed "robust" SVMs designed to ignore outliers, these often rely on strong assumptions about data distribution or the attacker's behavior. This paper addresses the fundamental computational hardness of building robust SVMs and proposes a data sanitization approach based on DBSCAN.
Theoretical Hardness of Robust SVMs
A primary contribution of this work is the proof that finding a perfectly robust SVM is computationally hard. Specifically, we prove that the hard-margin one-class SVM with adversarial outliers problem is NP-complete. By reducing the problem from 3-SAT, we demonstrate that no algorithm can achieve a perfect or even nearly perfect approximation in polynomial time unless P=NP. This theoretical result justifies the shift toward heuristic defenses and data sanitization techniques, as an optimal polynomial-time solution for robust SVMs is likely non-existent.
The DBSCAN Defense and Intrinsic Dimensionality
Since the optimal defense is computationally unreachable, we turn to data sanitization: cleaning the data before training. We propose using DBSCAN (Density-Based Spatial Clustering of Applications with Noise). The intuition is that clean data usually resides on a dense manifold, while poisoning points are often sparse or located in "unnatural" parts of the feature space.
We link DBSCAN’s success to the intrinsic dimensionality of the data (specifically, doubling dimension). We provide a sampling theorem in doubling metrics showing that if sufficient data points are available relative to the intrinsic dimension of the clean data, DBSCAN can reliably separate the "core" clean cluster from adversarial noise, regardless of the total dimensions of the feature space. This suggests that the "curse of dimensionality" affects the attacker as well; while high dimensionality provides more space to hide, the defense's success is tied to the actual degrees of freedom in the data.
Experimental Evaluation
We evaluated the DBSCAN defense against several benchmarks, including synthetic manifolds and real-world datasets such as LETTER, MUSHROOMS, and SATIMAGE.
Outlier Detection Performance
DBSCAN demonstrated exceptional performance in identifying poisoning samples. As shown in the figure below, DBSCAN achieved high F1 scores for identifying poisoning samples, significantly outperforming standard methods like L2 and Slab-based filtering.
Impact of Intrinsic Dimensionality
Our experiments confirmed that the performance of all defenses is influenced by the intrinsic complexity of the data manifold. As the intrinsic degree increases, maintaining high accuracy becomes more challenging. However, DBSCAN consistently maintains a performance lead over specialized robust SVM variants as the data complexity grows.
Conclusion
This paper establishes the NP-completeness of the robust SVM problem, highlighting the necessity of heuristic approaches. We demonstrate that DBSCAN is a remarkably effective tool for data sanitization, with its performance grounded in the intrinsic dimensionality of the data. Empirical results show that DBSCAN-based sanitization is stable and provides superior outlier detection compared to existing robust SVM methods and standard filters.
Summary updated