On the hardness of evading combinations of linear classifiers

By David Stevens, Daniel Lowd. 2013

31 citations recorded by the source corpus.

An increasing number of machine learning applications involve detecting the malicious behavior of an attacker who wishes to avoid detection. In such domains, attackers modify their behavior to evade the classifier while accomplishing their goals as efficiently as possible. The attackers typically do not know the exact classifier parameters, but they may be able to evade it by observing the classifier's behavior on test instances that they construct. For example, spammers may learn the most effective ways to modify their spams by sending test emails to accounts they control. This problem setting has been formally analyzed for linear classifiers with discrete features and convex-inducing classifiers with continuous features, but never for non-linear classifiers with discrete features. In this paper, we extend previous ACRE learning results to convex polytopes representing unions or intersections of linear classifiers. We prove that exponentially many queries are required in the worst case, but that when the features used by the component classifiers are disjoint, previous attacks on linear classifiers can be adapted to efficiently attack them. In experiments, we further analyze the cost and number of queries required to attack different types of classifiers. These results move us closer to a comprehensive understanding of the relative vulnerability of different types of classifiers to malicious adversaries.

Subfields: Artificial Intelligence, Computer Networks and Communications, Information Systems

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 Information Systems

Citations in the corpus

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 and Hardening of Tree Ensemble Classifiers (2015, background): “First, previous work has theoretically considered the evasion robustness of such ensemble of linear classifiers and proved the problem to be NP-hard (Stevens & Lowd, 2013).”
PRADA: Protecting Against DNN Model Stealing Attacks (2018, background): “Model evasion may be considered a theoretically simpler task than model extraction [51], and so far, the efficiency of model extraction attacks have not been demonstrated on DNNs.”