Paragraph: Thwarting Signature Learning by Training Maliciously

By James Newsome, Brad Karp, Dawn Song. 2006

236 citations recorded by the source corpus.

Defending a server against Internet worms and defending a user's email inbox against spam bear certain similarities. In both cases, a stream of samples arrives, and a classifier must automatically determine whether each sample falls into a malicious target class (e.g., worm network traffic, or spam email). A learner typically generates a classifier automatically by analyzing two labeled training pools: one of innocuous samples, and one of samples that fall in the malicious target class. Learning techniques have previously found success in settings where the content of the labeled samples used in training is either random, or even constructed by a helpful teacher, who aims to speed learning of an accurate classifier. In the case of learning classifiers for worms and spam, however, an adversary controls the content of the labeled samples to a great extent. In this paper, we describe practical attacks against learning, in which an adversary constructs labeled samples that, when used to train a learner, prevent or severely delay generation of an accurate classifier. We show that even a delusive adversary, whose samples are all correctly labeled, can obstruct learning. We simulate and implement highly effective instances of these attacks against the Polygraph [15] automatic polymorphic worm signature generation algorithms.

Subfields: Computer Networks and Communications, Information Systems, Safety, Robustness & Interpretability, Privacy & Security, 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 Computer Networks and Communications

In Information Systems

In Safety, Robustness & Interpretability

In Privacy & Security

In Signal Processing

Citations in the corpus

Wild Patterns: Ten Years After the Rise of Adversarial Machine Learning (2017, background): “To our knowledge, the earliest poisoning attacks date back to 2006-2010 [21–23, 25, 82].”
Fine-Pruning: Defending Against Backdooring Attacks on Deep Neural Networks (2018, background): “Causative attacks, primarily using training data poisoning , soon followed, again targeting spam ﬁltering [35] and network intrusion detection [11,12,36].”
BadNets: Identifying Vulnerabilities in the Machine Learning Model Supply Chain (2017, background): “[29] devised trainingtime attacks against the Polygraph virus detection system that would create both false positives and negatives when classifying network traffic, and Chung and Mok [30], [31] found that Autograph, a signature detection system that updates its model online, was vulnerable to aller”
Certified Defenses for Data Poisoning Attacks (2017, background): “There have also been a number of demonstrated vulnerabilities in deployed systems (Newsome et al., 2006; Laskov and Šrndi`c, 2014; Biggio et al., 2014b).”
Stealing Machine Learning Models via Prediction APIs (2016, background): “ the ids do not match, a split on Size occurs on the path to id 2. With a binary search over feature Size (and all other features in x ﬁxed), we ﬁnd all intervals that lead to different leaves, i.e., [0;40], (40;60], (60;100]. From these intervals, we ﬁnd the predicate for the current leaf (i.e., Si”
Learning Discrete Distributions from Untrusted Batches (2017, background): “…stems from the very real vulnerabilities of many deployed learning systems to “data poisoning” attacks in which an adversary selectively alters or plants a small amount of carefully chosen training data that signiﬁcantly impacts the resulting trained model (see e.g. [ NKS06, NBL11, XBN + 15]).”
Machine Learning Models that Remember Too Much (2017, background): “Poisoning attacks [9, 18, 38, 57, 65] insert malicious data points into the training dataset to make the resulting model easier to evade.”
The security of machine learning (2010, background): “Correlated outlier attack Newsome et al. (2006) also suggest a correlated outlier attack, which attacks a naive-Bayes-like learner by adding spurious features to positive training instances , causing the filter to block benign traffic with those features (an Availability attack).”
Certified Defenses against Adversarial Examples (2018, background): “Newsome et al. (2006), Laskov & Šrndic̀ (2014), and Biggio et al. (2014b) have demonstrated poisoning attacks against real-world systems.”
Security Evaluation of Pattern Classifiers under Attack (2014, methodology): “Many authors implicitly performed security evaluation as a what-if analysis, based on empirical simulation methods; however, they mainly focused on a specific application, classifier and attack, and devised ad hoc security evaluation procedures based on the exploitation of problem knowledge and heur”
Yes, Machine Learning Can Be More Secure! A Case Study on Android Malware Detection (2017, neutral): “quently cause misclassification errors [7], [11], [25], [32], [34], [42], [43], [44], [45].”
Security analysis of online centroid anomaly detection (2010, background): “…in the context of specific security and spam detection applications (Lowd and Meek, 2005a; Fogla et al., 2006; Fogla and Lee, 2006; Perdisci et al., 2006; Newsome et al., 2006; Nelson et al., 2008), which has motivated a recent work on taxonomization of such attacks (Barreno et al., 2006, 2008).”
Limits of Learning-based Signature Generation with Adversaries (2008, background): “Earlier experimental work (e.g., in Paragraph) has demonstrated that reflecting sets can be found for current generations of pattern-extraction algorithms.”
Traffic Morphing: An Efficient Defense Against Statistical Traffic Analysis (2009, background): “Finally, in Section 3.5 we discuss several potential issues that may arise in practice, and methods to overcome them.”