Optimal randomized classification in adversarial settings

By Yevgeniy Vorobeychik, Bo Li. 2014

71 citations recorded by the source corpus.

The problem of learning to distinguish good inputs from malicious has come to be known as adversarial classification emphasizing the fact that, unlike traditional classification, the adversary can manipulate input instances to avoid being so classified. We offer the first general theoretical analysis of the problem of adversarial classification, resolving several important open questions in the process. First, we significantly generalize previous results on adversarial classifier reverse engineering (ACRE), showing that if a classifier can be efficiently learned, it can subsequently be efficiently reverse engineered with arbitrary precision. We extend this result to randomized classification schemes, but now observe that reverse engineering is imperfect, and its efficacy depends on the defender's randomization scheme. Armed with this insight, we proceed to characterize optimal randomization schemes in the face of adversarial reverse engineering and classifier manipulation. What we find is quite surprising: in all the model variations we consider, the defender's optimal policy tends to be either to randomize uniformly (ignoring baseline classification accuracy), which is the case for targeted attacks, or not to randomize at all, which is typically optimal when attacks are indiscriminate.

Subfields: Artificial Intelligence, Computer Networks and Communications, Optimization & Training, Signal Processing

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 Optimization & Training

In Signal Processing

Citations in the corpus

Towards the Science of Security and Privacy in Machine Learning (2016, methodology): “A PAC based work shows that with no access to the training data or ML algorithm, querying the target model and knowledge of the class of target models allows the adversary to reconstruct the model with similar amount of query data as used in training [72] Thus, a key metric when comparing different ”
SoK: Security and Privacy in Machine Learning (2018, methodology): “Without access to the training data or ML algorithm, querying the target model and knowledge of the class of target models allows the adversary to reconstruct the model with similar amounts of query data as used in training [71] Thus, a key metric when comparing different attacks is the wealth of in”
Learning Adversary Behavior in Security Games: A PAC Model Perspective (2015, background): “Thus, learning the adversary’s bounded rational behavior and computing defender Appears in: Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2016), J. Thangarajah, K. Tuyls, C. Jonker, S. Marsella (eds.)”
Cyberspace Security Using Adversarial Learning and Conformal Prediction (2015, background): “It has been reported that the defender’s optimal policy tends to be either to randomize uniformly (ignoring baseline classification accuracy), which is the case for targeted attacks, or not to randomize at all, which is typically optimal when attacks are indiscriminate [12].”
Dynamic Backdoor Attacks Against Machine Learning Models (2020, background): “Multiple work has explored the privacy and security risks of adversarial examples [5, 23, 36, 37, 51, 53, 57].”
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].”
ML-Leaks: Model and Data Independent Membership Inference Attacks and Defenses on Machine Learning Models (2018, background): “Another major family of attacks against machine learning is adversarial examples [12], [24], [32]–[34], [39], [41], [42].”
Updates-Leak: Data Set Inference and Reconstruction Attacks in Online Learning (2019, unknown): “Besides the above, there exist a wide range of other attacks and defenses on machine learning models [4,5,8,9,13,14,16, 17, 22, 23, 25, 26, 35, 41, 43, 44, 46, 48–50, 52, 54–56]”
Feature Conservation in Adversarial Classifier Evasion: A Case Study (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], [14], [38], [16], [18], [19], [26], [34].”
Behavioral Experiments in Email Filter Evasion (2016, methodology): “…describe and motivate the experimental setup, we begin by considering in the abstract the problem of adversarial classiﬁer evasion , which has been previously studied in several forms from a computational standpoint (Lowd and Meek 2005b; 2005a; Vorobeychik and Li 2014; Li and Vorobeychik 2014).”