Near-Optimal Evasion of Convex-Inducing Classifiers

By Blaine Nelson, Benjamin I. P. Rubinstein, Ling Huang, Anthony D. Joseph, Shing-Hon Lau, Steven J. Lee, Satish Rao, Anthony Tran, J. Doug Tygar. 2010

55 citations recorded by the source corpus.

Classifiers are often used to detect miscreant activities. We study how an adversary can efficiently query a classifier to elicit information that allows the adversary to evade detection at near-minimal cost. We generalize results of Lowd and Meek (2005) to convex-inducing classifiers. We present algorithms that construct undetected instances of near-minimal cost using only polynomially many queries in the dimension of the space and without reverse engineering the decision boundary.

Subfields: Artificial Intelligence, Computer Networks and Communications, Safety, Robustness & Interpretability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Safety, Robustness & Interpretability

Citations in the corpus

Attacking Graph-based Classification via Manipulating the Graph Structure (2019, background): “In particular, studies have demonstrated that machine learning is vulnerable to adversarial examples [7,12,27,30,37,40,43,46,51,53,56, 68], poisoning attacks [8,18,31,38,67,70], privacy attacks for users (e.g., model inversion attacks [19,20], membership inference attacks [49,52], property…”
Stealing Hyperparameters in Machine Learning (2018, background): “Evasion attacks: In these attacks [33], [22], [3], [51], [52], [17], [26], [23], [37], [56], [9], [44], [28], [36], an attacker aims to inject carefully crafted noise into a testing instance (e.”
Query Strategies for Evading Convex-Inducing Classifiers (2010, methodology): “We present algorithms for evasion that are near-optimal under ℓ 1 cost in Section 3 and we consider minimizing general ℓ p costs in Section 4.”
Dimensionality Reduction as a Defense against Evasion Attacks on Machine Learning Classifiers (2017, background): “[33] obtain bounds on the number of classification queries to a convex-inducing classifier in order to find adversarial samples.”
Hardening Classifiers against Evasion: the Good, the Bad, and the Ugly (2017, background): “The second paradigm models attacks as modifications directly in feature space, imposing a modification cost typically captured as (weighted) norm difference from the original malicious instance [7], [20], [23], [24], [2], [16].”
Classifier Evasion: Models and Open Problems (2010, background): “Nelson et al. [7] generalized the result from linear classiﬁers to the family of convex-inducing classiﬁers that partition the space of instances into two sets one of which is convex.”
Behavior of Machine Learning Algorithms in Adversarial Environments (2010, result): “Portions of this dissertation have appeared in previously published works [Barreno et al., 2006, 2010, Nelson et al., 2008, 2009, 2010a, Rubinstein et al., 2009a].”
Feature Conservation in Adversarial Classifier Evasion: A Case Study (2017, background): “The second paradigm models attacks as mod-iﬁcations directly in feature space, imposing a modiﬁcation cost typically captured as (weighted) norm difference from the original malicious instance [7], [20], [24], [25], [2], [16].”
Adversarial machine learning (2019, background): “In the next section we discuss our extension to this framework [50].”
Pattern Recognition Systems under Attack: Design Issues and Research Challenges (2014, background): “For instance, in malware detection systems malware samples collected through “honeypots” are clustered (before pre-processing and feature extraction) for reducing the training set size, and for unsupervised ground truth assessment before human supervision[63, 2, 61].”
Convex Adversarial Collective Classification (2013, methodology): “…methods for blocking the adversary by anticipating their next move (Dalvi et al., 2004), reverse engineering classifiers (Lowd & Meek, 2005a;b) (and later: (Nelson et al., 2010)), and building classifiers robust to feature deletion or other invariants (Globerson & Roweis, 2006; Teo et al., 2008).”
Prediction Poisoning: Towards Defenses Against DNN Model Stealing Attacks (2019, methodology): “In some cases, the extracted model information is optionally used to perform evasion attacks (Lowd & Meek, 2005; Nelson et al., 2010; Papernot et al., 2017b).”
Man vs. Machine: Practical Adversarial Detection of Malicious Crowdsourcing Workers (2014, background): “Adversarial machine learning has been studied by prior work from a theoretical perspective [12, 27, 6], using simplistic all-or-nothi ng assumptions about adversaries’ knowledge about the ML system in use.”
Machine learning in adversarial environments (2010, background): “In addition, a theoretical analysis of robustness of certain learning algorithms against specific attacks has been carried out in recent work (Nelson et al. 2010; Kloft and Laskov 2010).”