Query Strategies for Evading Convex-Inducing Classifiers

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

123 citations recorded by the source corpus.

Classifiers are often used to detect miscreant activities. We study how an adversary can systematically query a classifier to elicit information that allows the attacker to evade detection while incurring a near-minimal cost of modifying their intended malfeasance. We generalize the theory of Lowd and Meek (2005) to the family of convex-inducing classifiers that partition their feature space into two sets, one of which is convex. We present query algorithms for this family that construct undetected instances of approximately minimal cost using only polynomially-many queries in the dimension of the space and in the level of approximation. Our results demonstrate that nearoptimal evasion can be accomplished for this family without reverse engineering the classifier's decision boundary. We also consider general lp costs and show that near-optimal evasion on the family of convex-inducing classifiers is generally efficient for both positive and negative convexity for all levels of approximation if p = 1.

Subfields: 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 Safety, Robustness & Interpretability

Citations in the corpus

Towards the Science of Security and Privacy in Machine Learning (2016, background): “[74] identify the space of convex inducing classifiers— those where one of the classes is a convex set—that are ACRE”
Wild Patterns: Ten Years After the Rise of Adversarial Machine Learning (2017, background): “Even if surrogate learners are not necessarily used here [62– 65], as well as in pioneering work on black-box attacks against machine learning [19, 66], one may anyway learn a surrogate classiﬁer (potentially on a di ﬀ erent feature representation) and check whether the crafted attack samples…”
Decision-Based Adversarial Attacks: Reliable Attacks Against Black-Box Machine Learning Models (2017, background): “Other decision-based attacks are speciﬁc to linear or convex-inducing classiﬁers (Dalvi et al., 2004; Lowd & Meek, 2005; Nelson et al., 2012) and are not applicable to other machine learning models.”
Stealing Machine Learning Models via Prediction APIs (2016, background): “Intuitively, model extraction seems harder than evasion, and this is corroborated by results from theory [36, 39, 50] and practice [36, 55].”
Evasion Attacks against Machine Learning at Test Time (2013, background): “2 This is also the setting adopted in previous work [9, 19, 22].”
Model-Reuse Attacks on Deep Learning Systems (2018, background): “(ii) Evasion attacks, in which the adversary modifies the input data during inference to trigger the systems to misbehave [7, 18, 37, 42].”
Evasion and Hardening of Tree Ensemble Classifiers (2015, methodology): “We briefly discuss strategies for modeling the feature extraction step in paragraph additional constraints of section 4.3.”
Adversarial Feature Selection Against Evasion Attacks (2016, background): “tion problems [11], [12], [16], [19], [41], [42].”
Security Evaluation of Support Vector Machines in Adversarial Environments (2014, background): “Apart from application-specific work, several theoretical models of adversarial learning have been proposed [4, 17, 26, 36, 40, 42, 46, 53].”
Support vector machines under adversarial label contamination (2015, background): “We report an extensive experimental analysis on the effectiveness of the considered attacks against linear and non-linear SVMs, both on synthetic and real-world datasets.”
SoK: Security and Privacy in Machine Learning (2018, background): “[73] identify the space of convex inducing classifiers—those where one of the classes is a convex set—that are ACRE learnable but not necessarily reverse engineerable.”
Interpretable Deep Learning under Fire (2018, background): “…threat models are considered in literature: Poisoning attacks – the adversary pollutes the training data to eventually compromise the target models [6], [68], [40]; Evasion attacks – the adversary modiﬁes the input data during inference to trigger target models to misbehave [13], [34], [43].”
Behavioral Experiments in Email Filter Evasion (2016, background): “…, adversarial evasion is commonly modeled as (an adversary) choosing another feature vector x (cid:2) (for example, a modiﬁed spam email template) which is classiﬁed as benign and is as close to the original instance x as possible (Lowd and Meek 2005a; Nelson et al. 2012; Li and Vorobeychik 2014).”
Hardening Classifiers against Evasion: the Good, the Bad, and the Ugly (2017, methodology): “A series of methods follow their framework, but consider more general classes of classifiers, introducing a constraint on the evasion cost, and explicitly trading off the degree to which an instance appears as benign and evasion cost [2], [3], [13], [38], [16], [18], [19], [25], [35].”
Exploring the Space of Black-box Attacks on Deep Neural Networks (2017, unknown): “Existing black-box attacks that do not use a local model were ﬁrst proposed for convex inducing two-class classiﬁers by Nelson et al. (2012).”
Scalable Optimization of Randomized Operational Decisions in Adversarial Classification Settings (2015, methodology): “Extensive experiments demonstrate the efficacy of our approach.”
EagleEye: Attack-Agnostic Defense against Adversarial Inputs (Technical Report) (2018, background): “Two primary threat models are considered in literature: (i) poisoning attacks, in which the attackers pollute the training data to eventually compromise the learning systems [7, 35, 45], and (ii) evasion attacks, in which the attackers modify the input data at test time to trigger the learning syste”