summaries: This paper leverages differential privacy’s stability properties to investigate its use for improved anomaly and backdoor attack detection. Under an assumption (called “uniformly asymptotic empirical risk minimization”), the authors show that difference between the expected loss of a differentially private learning algorithm on an outlier (where the expectation is taken over the randomness of the learning algorithm) and the expected loss of the same algorithm on data from the underlying distribution (expectation taken over data & randomness of the algorithm) is lower bounded by a (possibly/hopefully) non-negative quantity with high probability. The authors then conduct a set of experiments to show that differential privacy improves the performance of outliers, novel examples, and backdoor attack detection.  This paper proposes the idea of using differential privacy (DP) to improve the performance of outlier and novelty detection. Differential privacy was proposed as a privacy metric which limits the contribution of a single data point in the training set to the output. This property naturally controls how poisoned data would affect the output of the learned model. Under the assumption that a well-trained model would incur a higher loss on the outliers, the paper gives a theoretic bound on how this loss will decrease if there are poisoned samples in the training set. 
abstractText: Outlier detection and novelty detection are two important topics for anomaly detection. Suppose the majority of a dataset are drawn from a certain distribution, outlier detection and novelty detection both aim to detect data samples that do not fit the distribution. Outliers refer to data samples within this dataset, while novelties refer to new samples. In the meantime, backdoor poisoning attacks for machine learning models are achieved through injecting poisoning samples into the training dataset, which could be regarded as “outliers” that are intentionally added by attackers. Differential privacy has been proposed to avoid leaking any individual’s information, when aggregated analysis is performed on a given dataset. It is typically achieved by adding random noise, either directly to the input dataset, or to intermediate results of the aggregation mechanism. In this paper, we demonstrate that applying differential privacy can improve the utility of outlier detection and novelty detection, with an extension to detect poisoning samples in backdoor attacks. We first present a theoretical analysis on how differential privacy helps with the detection, and then conduct extensive experiments to validate the effectiveness of differential privacy in improving outlier detection, novelty detection, and backdoor attack detection.
authors.name: Min Du
authors.name: Ruoxi Jia
authors.name: Dawn Song
references.authors: Martin Abadi Andy Chu Ian Goodfellow H Brendan McMahan Ilya Mironov Kunal Talwar Li Zhang
references.title: Deep learning with differential privacy
references.venue: In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security,
references.authors: Charu C Aggarwal Philip S Yu
references.title: Outlier detection for high dimensional data
references.venue: In ACM Sigmod Record,
references.authors: Eugene Bagdasaryan Vitaly Shmatikov
references.title: Differential privacy has disparate impact on model accuracy
references.venue: arXiv preprint arXiv:1905.12101,
references.authors: Gilles Blanchard Gyemin Lee Clayton Scott
references.title: Semi-supervised novelty detection
references.venue: Journal of Machine Learning Research,
references.authors: Olivier Bousquet André Elisseeff
references.title: Stability and generalization
references.venue: Journal of machine learning research,
references.authors: Guilherme O Campos Arthur Zimek Jörg Sander Ricardo JGB Campello Barbora Micenková Erich Schubert Ira Assent Michael E Houle
references.title: On the evaluation of unsupervised outlier detection: measures, datasets, and an empirical study
references.venue: Data Mining and Knowledge Discovery,
references.authors: Nicholas Carlini Chang Liu Jernej Kos Úlfar Erlingsson Dawn Song
references.title: The secret sharer: Measuring unintended neural network memorization & extracting secrets
references.venue: arXiv preprint arXiv:1802.08232,
references.authors: Frank De Morsier Devis Tuia Maurice Borgeaud Volker Gass Jean-Philippe Thiran
references.title: Semisupervised novelty detection using svm entire solution path
references.venue: IEEE Transactions on Geoscience and Remote Sensing,
references.authors: Min Du Feifei Li Guineng Zheng Vivek Srikumar
references.title: Deeplog: Anomaly detection and diagnosis from system logs through deep learning
references.venue: In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security,
references.authors: Lian Duan Lida Xu Ying Liu Jun Lee
references.title: Cluster-based outlier detection
references.venue: Annals of Operations Research,
references.authors: Cynthia Dwork
references.title: Differential privacy: A survey of results. In Theory and Applications of Models of Computation—TAMC, volume 4978 of Lecture Notes in Computer Science
references.authors: Cynthia Dwork
references.title: Differential privacy
references.venue: Encyclopedia of Cryptography and Security, pp
references.authors: Cynthia Dwork Vitaly Feldman Moritz Hardt Toniann Pitassi Omer Reingold Aaron Leon Roth
references.title: Preserving statistical validity in adaptive data analysis
references.venue: In Proceedings of the forty-seventh annual ACM symposium on Theory of computing,
references.authors: Justin Gottschlich Abdullah Muzahid
references.title: Autoperf: A generalized zero-positive learning system to detect software performance anomalies
references.venue: arXiv preprint arXiv:1709.07536,
references.authors: Tianyu Gu Brendan Dolan-Gavitt Siddharth Garg
references.title: Badnets: Identifying vulnerabilities in the machine learning model supply chain
references.venue: arXiv preprint arXiv:1708.06733,
references.authors: Victoria Hodge Jim Austin
references.title: A survey of outlier detection methodologies
references.venue: Artificial intelligence review,
references.authors: Heiko Hoffmann
references.title: Kernel pca for novelty detection
references.venue: Pattern recognition,
references.authors: Shiva Prasad Kasiviswanathan Homin K Lee Kobbi Nissim Sofya Raskhodnikova Adam Smith
references.title: What can we learn privately
references.venue: SIAM Journal on Computing,
references.authors: Mathias Lecuyer Vaggelis Atlidakis Roxana Geambasu Daniel Hsu Suman Jana
references.title: Certified robustness to adversarial examples with differential privacy
references.venue: arXiv preprint arXiv:1802.03471,
references.authors: Jian-Guang Lou Qiang Fu Shengqi Yang Ye Xu Jiang Li
references.title: Mining invariants from console logs for system problem detection
references.venue: In USENIX Annual Technical Conference,
references.authors: Markos Markou Sameer Singh
references.title: Novelty detection: a review—part 1: statistical approaches
references.venue: Signal processing,
references.authors: Markos Markou Sameer Singh
references.title: Novelty detection: a review—part 2:: neural network based approaches
references.venue: Signal processing,
references.authors: Rina Okada Kazuto Fukuchi Jun Sakuma
references.title: Differentially private analysis of outliers
references.venue: In Joint European Conference on Machine Learning and Knowledge Discovery in Databases,
references.authors: F. Pedregosa G. Varoquaux A. Gramfort V. Michel B. Thirion O. Grisel M. Blondel P. Prettenhofer R. Weiss V. Dubourg J. Vanderplas A. Passos D. Cournapeau M. Brucher M. Perrot E. Duchesnay
references.title: Scikit-learn: Machine learning in Python
references.venue: Journal of Machine Learning Research,
references.authors: NhatHai Phan Ruoming Jin My T Thai Han Hu Dejing Dou
references.title: Preserving differential privacy in adversarial learning with provable robustness
references.authors: Congzheng Song Thomas Ristenpart Vitaly Shmatikov
references.title: Machine learning models that remember too much
references.venue: In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security,
references.authors: Wei Xu
references.title: URL http://iiis.tsinghua.edu.cn/~weixu/ sospdata.html. [Online; accessed 3-May-2019
references.venue: Hdfs log dataset,
references.authors: Huan Xu Constantine Caramanis Sujay Sanghavi
references.title: Robust pca via outlier pursuit
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Wei Xu Ling Huang Armando Fox David Patterson Michael I Jordan
references.title: Detecting large-scale system problems by mining console logs
references.venue: In Proceedings of the ACM SIGOPS 22nd symposium on Operating systems principles,
references.authors: Samuel Yeom Irene Giacomelli Matt Fredrikson Somesh Jha
references.title: Privacy risk in machine learning: Analyzing the connection to overfitting
references.venue: IEEE 31st Computer Security Foundations Symposium (CSF),
references.authors: Arthur Zimek Erich Schubert Hans-Peter Kriegel
references.title: A survey on unsupervised outlier detection in high-dimensional numerical data. Statistical Analysis and Data Mining: The ASA Data
references.venue: Science Journal,
references.authors: Arthur Zimek Ricardo JGB Campello Jörg Sander
references.title: Ensembles for unsupervised outlier detection: challenges and research questions a position paper
references.venue: Acm Sigkdd Explorations Newsletter,
sections.text: Outlier detection and novelty detection are two important topics for anomaly detection. Suppose the majority of a dataset are drawn from a certain distribution, outlier detection and novelty detection both aim to detect data samples that do not fit the distribution. Outliers refer to data samples within this dataset, while novelties refer to new samples. In the meantime, backdoor poisoning attacks for machine learning models are achieved through injecting poisoning samples into the training dataset, which could be regarded as “outliers” that are intentionally added by attackers. Differential privacy has been proposed to avoid leaking any individual’s information, when aggregated analysis is performed on a given dataset. It is typically achieved by adding random noise, either directly to the input dataset, or to intermediate results of the aggregation mechanism. In this paper, we demonstrate that applying differential privacy can improve the utility of outlier detection and novelty detection, with an extension to detect poisoning samples in backdoor attacks. We first present a theoretical analysis on how differential privacy helps with the detection, and then conduct extensive experiments to validate the effectiveness of differential privacy in improving outlier detection, novelty detection, and backdoor attack detection.
sections.heading: 1 INTRODUCTION
sections.text: Given a dataset where most of the samples are from a certain distribution, outlier detection aims to detect the minorities in the dataset that are far from the distribution, while the goal of novelty detection is to detect newly observed data samples that do not fit the distribution. On the other hand, poisoning examples that are intentionally added by attackers to achieve backdoor attacks could be treated as one type of “outliers” in the training dataset. Using machine learning for outlier/novelty detection is typically to train a model that learns the distribution where the training data samples are drawn from, and the final trained model could give a high anomaly score for the outliers/novelties that deviate from the same distribution. In both cases, the machine learning model is not supposed to learn from the outliers in the training dataset. Unfortunately, deep learning models that contain millions of parameters tend to remember too much (Song et al. [2017]), and can easily overfit to rare training samples (Carlini et al. [2018]).
  Protecting data privacy has been a major concern in many applications, because sensitive data are being collected and analyzed. Differential privacy has been proposed to “hide” certain input data from the output; that is, by looking at the statistical results calculated from input data, one cannot tell whether the input data contain a certain record or not. The way of applying differential privacy is to add random noise to the input data or the data analysis procedure, such that the output difference caused by the input difference can be hidden by the noise. A known fact is that differential privacy implies stability (Kasiviswanathan et al. [2011]). Particularly, a differentially private learning algorithm is stable in the sense that the model learned by the algorithm is insensitive to the removal or replacement of an arbitrary point in the training dataset (Bousquet & Elisseeff [2002]). When the training dataset contains a handful of outliers, the output model of a stable learning algorithm should be close to the one trained on the clean portion of the training set. Intuitively, compared with the model trained on contaminated dataset, the one trained on clean data could be better at distinguishing outliers from normal data. Therefore, differential privacy can potentially be leveraged to improve the
  identification of outliers. This motivates us to apply differential privacy to anomaly detection and defense against backdoor attacks.
  Our contribution. First, we present a theoretical explanation on why differential privacy can help to detect outliers from a training and testing dataset, as well as an analysis on the relationship between the number of outliers to detect and the amount of random noise to apply. Second, to demonstrate the effectiveness, we apply differential privacy to an autoencoder network trained on a constructed MNIST dataset with injected outliers, for both outlier detection and novelty detection, to show how much the utility could be improved with different amount of outliers and noise. Third, we apply differential privacy to a real-world task - Hadoop file system log anomaly detection. System log anomaly detection is an important topic in computer security. Our proposed method greatly improves upon the state-of-the-art system in this field. The results indicate that differential privacy is able to eliminate almost all the false negatives, and achieve significantly improved overall utility, compared with the current state-of-the-art work DeepLog (Du et al. [2017]). Finally, via a proof-of-concept experiment using MNIST dataset with injected poisoning samples, we show that the idea of outlier detection could be extended to backdoor attack detection, and that differential privacy is able to further improve the performance.
sections.heading: 2 PRELIMINARY
sections.text: Given an input dataset and an aggregation mechanism, differential privacy (Dwork [2011]) aims to output the requested aggregation results, which are guaranteed not to reveal the participation of any individual data record. Formally, differential privacy is defined as below:
  Definition 1 (Differential privacy). A randomized mechanismM applied to data domain D is said to be ( , δ)-differentially private if for any adjacent datasets d, d′ in D, and any subset of outputs S ⊆ Range(M), it holds that
  Pr[M(d) ∈ S] ≤ e Pr[M(d′) ∈ S] + δ,
  where stands for the privacy bound, and δ stands for the probability to break this bound.
  The adjacent datasets d, d′ could be understood as two databases, where only one record differs, i.e., ‖d − d′‖1 = 1. Differential privacy guarantees that the difference between d and d′ are not revealed through inspecting the outputsM(d) andM(d′). Clearly, the closer is to 0, the more indistinguishableM(d) andM(d′) are, and hence the stronger the privacy guarantee is. A common approach to enforcing differential privacy for a function f : D→ R, is to add random Gaussian noise N (0, σ2) to perturb the output in R. The intuition is that, for given adjacent datasets d and d′, one cannot tell whether the difference between f(d) and f(d′) is incurred by the single record that differs in d and d′, or by the random noise being applied. The magnitude of Gaussian noise needs to be tailored to the maximum difference between f(d) and f(d′), which is formally defined as L2-sensitivity. Definition 2 (L2-sensitivity). The L2-sensitivity for a function f : D→ R is:
  ∆ = max d,d′∈D ‖d−d′‖1=1
  ‖f(d)− f(d′)‖2
  The noise scale σ to apply can be calculated as below (Dwork et al. [2014]).
  Theorem 1. To perturb a function with sensitivity ∆ under ( , δ) - differential privacy, the minimum noise scale σ of Gaussian mechanism is given by: σ = ∆ · √ 2 ln 1.25δ , where ∈ (0, 1).
  Deep learning with differential privacy (Abadi et al. [2016]) The procedure of deep learning model training is to minimize the output of a loss function, through numerous stochastic gradient descent (SGD) steps. Abadi et al. [2016] proposed a differentially private SGD algorithm that works as follows. At each SGD step, a fixed number of randomly selected training samples are used as a mini batch. For each mini batch training, the following two operations are performed to enforce differential privacy: 1) clip the norm of the gradient for each example, with a clipping bound C, to
  limit the sensitivity of gradient; 2) sum the clipped per-example gradients and add Gaussian noise N (0, σ2), before updating the model parameters. Abadi et al. [2016] further proposed a moment accounting mechanism which calculates the aggregate privacy bound when performing SGD for multiple steps. Differential privacy is immune to post-processing. Therefore, the output of the trained model for any queries enjoys the same privacy guarantee as the above SGD-based training process.
sections.heading: 3 THE CONNECTION BETWEEN DIFFERENTIAL PRIVACY AND OUTLIER DETECTION
sections.text: By definition, random noise added into model training for differential privacy hides the influence of a single record on the learned model. Intuitively, if applying differential privacy to the training process, the contribution of rare training examples will be hidden by random noise, resulting in a model that underfits the outliers. Such model will facilitate novelty and outlier detection because it will be less confident in predicting the atypical examples. In this section, we first present a theorem to precisely characterize the above intuition, and then analyze the relationship between the number of outliers in the training dataset and the amount of noise to apply.
  Notations LetZ be the sample space andH be the hypothesis space. The loss function l : H×Z → R measures how well the hypothesis h ∈ H explains a data instance z ∈ Z . A learning algorithm A : Zn → H learns some hypothesis A(S) given a set S of n samples. For instance, in supervised learning problems, Z = X × Y , where X is the feature space and Y is the label space; H is a collection of models h : X → Y; and l(h, z) measures how well h predicts the feature-label relationship z = (x, y).
  Let S = {z1, . . . , zn} be a set of independent samples drawn from an unknown distribution D on Z . For a given distribution D, an oracle hypothesis is the one that minimizes the expected loss:
  h∗ = arg min h Ez∼D[l(h, z)] (1)
  We define an outlier as a data instance that has significantly different loss from the population under the oracle hypothesis. Definition 3. We say z̃ is an outlier with regard to distribution D if
  l(h∗, z̃)− Ez∼D[l(h∗, z)] ≥ T (2) where T is a constant that depends only on D.
  We will prove the usefulness of differential privacy to detect outliers for the classes of learning algorithms that produce hypotheses converging to the optimal hypothesis asymptotically pointwise. We define such learning algorithms to be uniformly asymptotic empirical risk minimization (UAERM). Definition 4. A (possibly randomized) learning algorithm A is UAERM with rate ξ(n,A) if for any distribution D defined on the domain Z , it holds that
  ∀z |ES∼DnEh∼A(S)l(h, z)− l(h∗, z)| ≤ ξ(n,A) (3)
  In the definition, we make it explicit that the rate ξ(n,A) depends on the learning algorithm A. For instance, if A is a differentially private learning algorithm, the rate will depend on the privacy parameters. In that case, with slight abuse of notation, we will denote the rate for a ( , δ)-differentially private learning algorithm trained on n data instances by ξ(n, , δ).
  Due to the nonconvexity of their loss functions, neural networks may not enjoy a useful, tight characterization of the learning rate. Thus, we will empirically verify that using noisy SGD to learn differentially private neural networks is UAERM. Moreover, as we will show in the experiment, ξ(n, , δ) grows as privacy parameters and δ become smaller. Intuitively, this is because larger noise is required to ensure stronger privacy guarantees, which, on the other hand, slows down the convergence of the learning algorithm.
  Without loss of generality, we assume that 0 ≤ l(h, z) ≤ 1. The following theorem exhibits how the prediction performance of differentially private models on normal data will differ from outliers and connects the difference to the privacy parameters of the learning algorithm and the amount of outliers in the training data.
  Theorem 2. Suppose that a learning algorithm A is ( , δ)-differentially private and UAERM with the rate ξ(n, , δ). Let S′ = S ∪ U , where S ∼ Dn and U contains c arbitrary outliers. Then
  Eh∼A(S′)l(h, z̃)− Eh∼A(S′)Ez∼Dl(h, z) ≥ T − 2 ( ξ(n, , δ) + √ n(e − 1 + δ)2
  2 log
  2 γ + ec − 1 + cec δ
  ) (4)
  with probability at least 1− γ.
  The two terms in the left-hand side of (4) represent the model’s prediction loss on outliers and normal test data drawn from D, respectively. Due to the stochasticity of differentially private learning algorithms, the difference is characterized by the expectation taken over the randomness of the learned models. The theorem establishes a lower bound on the prediction performance difference between normal and outlier data. A larger difference indicates that identifying outliers will be easier.
  The impact of privacy parameters on the lower bound manifests itself in two aspects. On one hand, stronger privacy guarantees (i.e., smaller and δ) will require higher noise to be added into the training process, which increases the learning rate ξ(n, , δ). On the other hand, increasing privacy level will improve the stability of the learning algorithm; the resulting models tend to ignore the outliers in the training set and become closer to the ones trained on completely clean data, thus making the outlier detection more effective. The second aspect is embodied by the fact that the terms except ξ(n, , δ) in the parenthesis of the lower bound grow with and δ. Therefore, the privacy parameters cannot be too large or too small in order to ensure optimal anomaly detection performance.
  Moreover, the relationship between the right-hand side of (4) and c indicates that the anomaly detection problem will be more difficult with more outliers in the training set. Dissecting the righthand side of (4), we further observe that c appears always in tandem with . This implies that for larger number of outliers in the training set (i.e., c is larger), we will need to tune down and δ to maintain the same novelty detection performance.
  Last but not least, the definition of outliers in our paper is quite general—it does not make any assumptions about how the outliers are generated. Also, we do not make assumptions about whether these outliers are in training or test data. Therefore, our analysis can shed light on detecting various types of anomalies, including but not limited to outlier/novelty detection, backdoor detection, and noisy label detection. In the following experimental section, we will focus our evaluation on outlier/novelty detection and defense against backdoor attacks.
sections.heading: 4 EXPERIMENTS
sections.text: This section empirically evaluates the effectiveness of differential privacy in improving anomaly detection and backdoor attack detection. We call an outlier/novelty or a poisoning example as a positive, and other normal data samples as negatives. The metrics measured by each experiment include: false positive (FP), false negative (FN), Precision = TP / (TP+FP), Recall = TP / (TP+FN), Area under the receiver operating characteristic curve (AUROC) which is the area under the TPRFPR curve, Area under the Precision - Recall curve (AUPR) which summarizes the Precision - Recall curve, as well as F-measure =2× Precision× Recall / ( Precision + Recall ). The detailed explanations of all these measures could be found in (Wikipedia [2019b;a]; scikit-learn [2017a;b]).
sections.heading: 4.1 OUTLIER DETECTION AND NOVELTY DETECTION WITH AUTOENCODERS
sections.text: Autoencoder is a type of neural network that has been widely used for outlier detection and novelty detection. It contains an encoder network which reduces the dimension of the input data, and a decoder network which aims to reconstruct the input. Hence, the learning goal of autoencoders is to minimize the reconstruction error, which is consequently the loss function. Because the dimensionality reduction brings information loss, and the learning goal encourages to preserve the information that is common to most training samples, outliers that contain rare information could be identified by measuring model loss. In this section, with a varying amount of outliers and noise scale, we show how differential privacy would improve the utility of anomaly detection with autoencoders.
  Datasets. We utilize MNIST dataset composed by handwritten digits 0-9, and notMNIST dataset (Kaggle [2017]), which contains letters A-J with different fonts. The original MNIST data contain 60, 000 training images, and 10, 000 test images, which we refer to as MNIST-train and MNIST-test respectively. The notMNIST data contain 10, 000 training images and 1, 000 test images, denoted as notMNIST-train and notMNIST-test. Based on these datasets, we intentionally construct training datasets with varying amount of injected outliers. Specifically, each training dataset is constructed with a particular outlier ratio ro, such that the resulted dataset MNIST-OD-train(ro) contains 60, 000 images in total, where a percentage of 1− ro are from MNIST-train, and ro are from notMNIST-train. For each training dataset MNIST-OD-train(ro), a set of autoencoder models are trained with varying noise scale σ applied for differential privacy. For an autoencoder model trained on dataset MNISTOD-train(ro), outlier detection is thus to detect the ro × 60, 000 outliers from MNIST-OD-train(ro). For novelty detection, we further construct a test dataset MNIST-ND-test, which is composed by the entire MNIST-test dataset and notMNIST-test dataset, a total of 11, 000 images. The goal of novelty detection is to identify the 1, 000 notMNIST-test images as novelties.
  Evaluation metrics. To check whether a data sample is an outlier/novelty using autoencoders, the standard practice is to set a loss threshold based on training statistics, and any sample having a loss above this threshold is an outlier/novelty. To measure the performance under different thresholds, we use the AUPR score which is a threshold-independent metric. Compared with other metrics such as the AUROC score, the AUPR score is more informative when the positive/negative classes are highly unbalanced, e.g., for outlier detection where the ratio of outliers is extremely low. More experiment settings with both AUPR and AUROC metrics are in appendix which present similar observations.
  Set-up. For autoencoders, the encoder network contains 3 convolutional layers with max pooling, while the decoder network contains 3 corresponding upsampling layers. For differential privacy, we use a clipping bound C = 1 and δ = 10−5, and vary the noise scale σ as in (Abadi et al. [2016]). All models are trained with a learning rate of 0.15, a mini-batch size of 200 and for a total of 60 epochs.
  Validation of UAERM for Noisy SGD. To begin with, we first conduct experiments to empirically validate our assumption in Theorem 2. While a rigorous verification of the assumption is intractable as it requires the knowledge of underlying data distribution and computing expected loss over randomness of both data distribution and differentially private algorithms, our experiments provide a sanity check of the assumption by replacing the expectation by the empirical average of a large number of data samples. For this set of experiments, we only utilize MNIST data for training, while the test dataset contains all available MNIST and notMNIST test samples. The oracle hypothesis is trained on all available training data, while each differentially private model is trained with varying privacy level , and training data size. For a fixed training set and , we perform training for multiple times to accommodate the randomness of differentially private training. Further, we train on multiple randomly selected training sets of the same size. We measure the loss of each resulting model on the test set, and calculate the average testing loss across different runs of differentially private training and different randomly selected training sets of the same size. We then compute the largest difference between the averaged test loss and the test loss associated with the oracle hypothesis. The results are shown in Figure 1. Each data point in the figure is an average of 9 differentially private models
  trained on 3 randomly sampled subsets of the training data, and 3 random training processes for each sampled subset. As in Figure 1, the larger the training data size, and the larger is, the closer of the randomized model to the oracle hypothesis, validating our assumption in Theorem 2 that noisy SGD is UAERM.
  Detection results Table 1 shows the outlier detection (OD) results on dataset MNIST-OD-train, as well as the novelty detection (ND) results on dataset MNIST-ND-test. OD mimics the unsupervised anomaly detection case. ND mimics the case where the autoencoder model is supposed to be trained on normal data, to detect unforeseen anomalies, while the training dataset is noisy. The first row where σ =N/A is for the baseline model without differential privacy applied. It performs well when ro = 0.1%, but drops significantly when ro reaches 0.5%. That’s because for a mini-batch size of 200 that we use, an outlier ratio of 0.5% in training data results in an average of one outlier in each mini-batch, which could be learned by the baseline model. Note that the clipping bound C=1 also restricts the contribution of outliers in SGD steps. We conduct an ablation study which only clips the per-example gradients with C without adding any noise in each gradient descent step. The results are shown as σ = 0 in Table 1. As an intermediate step to bound the sensitivity in differential privacy, clipping itself is able to slightly improve the anomaly detection results in most cases. Still, we show that increasing the noise scale could further improve the utility. We highlight one of the best results in each column, and find that the trend follows our analysis in Theorem 2. Specifically, the more outliers in the training dataset, the larger noise scale is needed for the best improvement. As explained for (4), our theory shows that the privacy parameters cannot be too large or too small to ensure optimal anomaly detection performance, which coincides with the experimental results in Table 1. Although it could be challenging to select the desired noise level for training, we note that as shown in Table 1, applying differential privacy effectively improves the anomaly detection performance in most cases, except when σ is too big to ruin the model parameters completely (e.g., σ=50) . Therefore, it is generally safe and almost always helpful to apply a small amount of differential privacy noise for anomaly detection. The noise scale could be increased further as long as the model converges. However, it should be noted that applying differential privacy makes the model training much slower than the baseline. In our experience utilizing NVIDIA Tesla V100 SXM2 GPU cards, the training time for each epoch could be up to 80 times longer. Finally, a training data portion as high as 10% might not be “outliers”, but could be part of the input pattern that should be learned by the model. We show in this case, a relatively large noise scale could effectively improve the anomaly detection results (e.g., σ=10), but it’s up to the requirement of the application whether to apply this.
sections.heading: 4.2 HADOOP FILE SYSTEM LOG ANOMALY DETECTION WITH LSTM
sections.text: In this section, we use a real-world example for Hadoop file system log anomaly detection, to show how anomaly detection with differential privacy outperforms the current state-of-the-art results.
  Dataset The Hadoop file system (HDFS) log dataset (Wei Xu [2009]) is generated through running Hadoop map-reduce jobs for 48 hours on 203 Amazon EC2 nodes. This dataset contains over 11 million log entries, which could be further grouped into 575, 059 block sessions by the block identifier each log has. Each block is associated with a normal/abnormal label provided by domain experts. Over the past decade this log dataset has been extensively used for research in system log anomaly detection (Xu et al. [2009]; Lou et al. [2010]; Du et al. [2017]). The state-of-the-art results are achieved by DeepLog (Du et al. [2017]), which we use as the baseline model. As in DeepLog, our training dataset contains 4, 855 normal block sessions, while the test dataset includes 553, 366 normal sessions and 16, 838 abnormal sessions.
  Baseline model and metrics DeepLog utilizes LSTM neural networks to learn system log sequences. Note that system log messages are textual logs, e.g., “Transaction A finished on server B.”. Before applying LSTM, a log parsing step first maps each log message into its corresponding log printing statement in the source code, e.g., “print(’Transaction %s finished on server %s.”%(x,y))". Since there are only a constant number (e.g., N ) of log printing statements in the source code, each one could be mapped to a discrete value from a fixed vocabulary set (e.g., having size N ). With that, a block session of log messages could be parsed to a sequence of discrete values, e.g. “22 5 5 5 11 9 11 9 11 9 26 26 26”. Leveraging the fact that hidden execution paths written in source code restrict the possibilities of how one system log follows another, DeepLog trains an LSTM model
  on normal discrete sequences, which learns to predict the next discrete value given its history. In detection, the LSTM model predicts a probability distribution on all possible values that may appear at a given time step. The real executed value is detected as abnormal if it’s unlikely to happen based on LSTM prediction. The criteria presented in DeepLog is to first sort the predicted values based on the assigned probabilities, e.g., for a prediction “{5: 0.2, 9: 0.08, 11: 0.01, 26: 0.7, ...}”, the order would be 26, 5, 9, 11, .... The given value to detect is checked against the sorted top k predictions, and is detected as abnormal if it’s not one of them. For anomaly detection metrics, we want to highlight that applying differential privacy significantly reduces false negatives, without introducing many false positives. Therefore, we’ll focus on the comparison over the number of false positives and false negatives, while also presenting measurements that indicate the overall detection performance.
  Set up For the baseline model DeepLog, we train an LSTM model for 100 epochs, and use the final model as the anomaly detection model. The model related parameters are: 2 layers, 256 units per layer, 10 time steps, and a batch size of 256. We call the DeepLog model with differential privacy as DeepLog+DP. For differential privacy, we use a clipping bound C = 1, δ = 10−5, and vary the noise scale σ. All other model related settings for DeepLog+DP are the same as DeepLog.
  Results Figure 2a shows the comparison of FP and FN under different thresholds k, with the increase of noise scale σ. For clarity, we only show the following two cases for baseline model DeepLog: k = 10 which has the maximum FP and the minimum FN , and k = 18 which has the minimum FP and the maximum FN . Note that y axis is plotted as log scale. It is clear that applying DP noise significantly reduces FN in all cases, from over a thousand in DeepLog, to hundreds or even zero in DeepLog+DP. Also, the larger noise being added, the more FN are reduced. Although more FP could be introduced in some cases, we note that in system anomaly detection, the merit of fewer false negatives in fact worth the cost of more false positives. Reported false positives could be further checked by system admin, and then fed into the model for incremental learning. However, a false negative may never be found out, until a more disastrous event occurs due to the un-discovery of it.
  The F-measure measurements are plotted in Figure 2b. For DeepLog model, F-measure ranges from 90.38% (k = 20) to 93.81% (k = 10). For DeepLog+DP, the best F-measure scores include 96.29% (σ = 0.25, k = 15) and 96.28% (σ = 1, k = 18), which show clear improvements over DeepLog model. Note that the best FN and FP measurements reported in DeepLog (Du et al. [2017]) are 619 and 833 respectively, while DeepLog+DP achieves FN =383, FP =762 at the F-measure of 96.28% (σ = 1, k = 18); and FN =123, FP =1040 at the F-measure of 96.29% (σ = 0.25, k = 15), showing its ability to significantly reduce false negatives without introducing many false positives. As shown in the figure, DeepLog performs better when k is smaller, while DeepLog+DP benefits from larger ks. This scenario could also be explained by the addition of differential privacy noise. Since the trained model does not overfit to outliers, it assigns to anomalies much lower probabilities, so that anomalies are ranked much lower than that in the DeepLog model. Meanwhile, normal execution logs are also possibly predicted with lower probabilities because of the uncertainty brought by the noise. As a result, the ideal threshold k for DeepLog+DP is higher than that of DeepLog. We also
  note that a large noise scale could hurt the overall performance, as shown by the downward trend when σ increases from 1.75 to 2.0.
sections.heading: 4.3 BACKDOOR ATTACK DETECTION
sections.text: Since poisoning examples for backdoor attacks are essentially “outlier” training samples injected by attackers, this section conducts proof-of-concept experiments to examine whether measuring model loss as for outliers works to detect poisoning examples, and whether differential privacy is able to further improve the performance. This detection scenario is particularly useful for backdoor attacks injected in the crowdsourcing scenario, where the model trainer gathers training data from untrusted individuals. In this case, the model trainer does not have control over the data quality but does have control over the model training process. Our proposal of adding DP noise is useful for detecting backdoor attacks and training more robust models in such a scenario.
  Dataset and set up MNIST dataset as described in Section 4.1 is used in this set of experiments. We refer the original 60,000 training images as CLEAN-train and the 10,000 test images as CLEANtest. We construct the backdoor attacks as described in (Gu et al. [2017]), Section 3.1.2. Specifically, each poisoning example is generated by reversing 4 pixel values in the bottom right corner of a clean image having label i, and assigning backdoor label (i+ 1)%10. From CLEAN-train, we randomly sample a poisoning ratio of rp images to be poisoning examples, resulting in a poisoned training dataset POISONED-train(rp). To demonstrate the effectiveness of the poisoning attacks, we use the CLEAN-test dataset, as well as POISONED-test dataset which is constructed by poisoning all images in CLEAN-test. For image classification model, we use convolutional neural network (CNN) containing 2 convolutional layers with max pooling, and a softmax layer to output desired labels. The differentially private models are trained with the same configurations as in Section 4.1 unless otherwise noted.
  Metrics We first evaluate the effectiveness of the constructed backdoor attack. A successful backdoor attack should have high image classification accuracy on CLEAN-test, which we refer to as benign accuracy, as well as high accuracy on POISONED-test with poisoned labels, which indicates the success rate. To investigate whether measuring the classification model loss is able to detect poisoning examples, and whether differential privacy is able to improve the detection performance, we leverage metrics AUPR and AUROC as described at the beginning of Section 4.
  Results We first evaluate the backdoor attack effectiveness and the detection performance with varying poisoning ratio rp, under different noise scale σ, and fixed clipping bound C = 1. The results are summarized in Table 2. σ =N/A indicates classification models trained without differential privacy. Benign accuracy remains high on clean data. Backdoor success rate is only around half at a poisoning ratio of 0.5%, and shows successful (97.12% success rate) at a poisoning ratio of 1%. Detecting poisoning examples by measuring model loss shows some level of effectiveness when the poisoning ratio is low (e.g., 0.5%). Furthermore, applying differential privacy to the model training process is able to significantly improve the detection performance. Similar as in Table 1, the higher the poisoning ratio, the larger the noise level (smaller ) to achieve the best improvement. Another interesting observation is that, a differentially private model is naturally robust to backdoor attacks. As indicated in Table 2, differential privacy effectively limits the success of backdoor attacks, reducing the success rate below 0.5% in all cases. In comparison, the utility downgrade on benign accuracy is little.
  To further evaluate the applicability of using the same CNN model for both anomaly detection and image classification, seeking to co-optimize the performance of the model for both tasks, we collect measurements with varying clipping bound C, and fixed noise scale σ = 0.5, as a complement to Table 2. The results are summarized in Table 3. Note that a small C may hurt model performance as more model parameters are clipped. When C is greater than most parameter values, the effect of increasing C is similar to that of increasing σ (Abadi et al. [2016]). From Table 3, we can observe that the best model for anomaly detection could have a similar set of parameters with the best model for image classification. However, in general, as shown in Table 2, classification accuracy and robustness are often two conflicting desiderata; model trainers can tune the privacy parameter in order to meet the task-specific requirements for accuracy and robustness.
sections.heading: 5 RELATED WORK
sections.text: To the best of our knowledge, this paper is the first one that proposes to improve outlier/novelty detection with differential privacy, and further extends it to backdoor attack detection. Note that this is not the first work that combines outlier detection and differential privacy together. Okada et al. [2015] aim to preserve input data privacy while detecting outliers. The two tasks are contradicting in this case as the identification of outliers (part of input data) implies certain privacy leakage, so Okada et al. [2015] try to find a balance. In contrast, we focus on improving anomaly detection performance with differential privacy, which is only applied to the model training stage, but no privacy protection is provided for the input data in detection stage when the outliers are actually being detected.
  Outlier detection and novelty detection are closely related to each other and often addressed together (Hodge & Austin [2004]; scikit-learn [2017c]; Pedregosa et al. [2011]). Outlier detection is the process of identifying rare items in a dataset that significantly differ from the majority (Aggarwal & Yu [2001]), while novelty detection is to detect new observations that lie in the low density area of the existing dataset (Markou & Singh [2003a;b]). Previous work mostly achieves outlier detection using unsupervised learning methods (Zimek et al. [2012; 2014]; Campos et al. [2016]), while novelty detection typically assumes a normal dataset is available for training, and is realized by semi-supervised learning (Blanchard et al. [2010]; De Morsier et al. [2013]). In both cases, it involves summarizing a distribution that the majority of training data are drawn from. Traditional methods such as clustering (Duan et al. [2009]) and principal component analysis (PCA) (Xu et al. [2010]; Hoffmann [2007]) have been frequently used. In this paper, we leverage deep learning based detection methods including autoencoders (Gottschlich et al. [2017]) and LSTM (Du et al. [2017]) as the baselines, and further extend the idea of measuring model loss to backdoor attack detection.
  Proposed by Dwork [2008], differential privacy has been a powerful tool to protect input data privacy. Kasiviswanathan et al. [2011] show that differential privacy implies stability on the output statistical results. Further, Dwork et al. [2015] point out that the empirical average of the output of a differentially private algorithm on a random dataset is close to the true expectation with high probability. Differential privacy has been utilized to train machine learning models that are robust to adversarial examples (Phan et al. [2019]; Lecuyer et al. [2018]), and to bound the success of inference attacks (Yeom et al. [2018]). In this paper, we utilize the property of differential privacy to improve anomaly detection and privacy is ensured via the technique proposed in Abadi et al. [2016].
  Lastly, we note that a recent paper by Bagdasaryan & Shmatikov [2019] showed that accuracy of differentially private models drops much more for the underrepresented classes and subgroups. Intrinsically, our paper exploited the same phenomenon to improve anomaly detection. Bagdasaryan & Shmatikov [2019] studied the phenomenon empirically, while our work provides a theoretical analysis, which, for the first time, precisely characterizes the dependence of the performance gap between
  the majority and the underrepresented group on the privacy parameters. Moreover, Bagdasaryan & Shmatikov [2019] mainly considered the implication of differential privacy to the fairness of machine learning models; by contrast, our paper focuses on anomaly detection and backdoor attacks and exhibits strong empirical evidence for the efficacy of differential privacy in these two application domains.
sections.heading: 6 CONCLUSION
sections.text: In this paper, inspired by the fact that differential privacy implies stability, we apply DP noise to improve the performance of outlier detection and novelty detection, with an extension to backdoor attack detection. We first provide the theoretical basis for the efficacy of differential privacy for identifying anomalies, connecting the hardness of the identification problem to privacy parameters. Our theoretical results are useful to explain various experimental findings, including how the anomaly detection performance varies with privacy parameters and the number of outliers in the training set. We perform extensive experiments to demonstrate the effectiveness of differential privacy for anomaly detection. To fully evaluate the effectiveness of DP in anomaly detection with different amount of outliers and noisee, we first construct a contaminated dataset based on MNIST and train autoencoder anomaly detection models with varying noise scale applied. We then evaluate the performance using a real-world task, Hadoop file system log anomaly detection, by applying DP noise to DeepLog, the current state-of-the-art detection model. The evaluation results show that DP noise is effective towards reducing the number of false negatives, and further improving the overall utility. Finally, we generalize the idea of measuring model loss for outlier detection to backdoor attack detection and further improve the performance via differential privacy.
sections.heading: A APPENDIX
sections.text: A.1 PROOF OF THEOREM 2
  The following result will be used for reasoning about the performance gap of the differentially private learned models between regular data points and outliers.
  Theorem 3 (McDiarmid, 1989). Let S be a set of n points and Si be the set with the ith element in S replaced by z′i, let F : Zn → R be any measurable function for which there exits constants ci (i = 1, . . . , n) such that
  sup S∈Zn,z′i∈Z
  |F (S)− F (Si)| ≤ ci (5)
  then
  PS [F (S)− ES [F (S)] ≥ ] ≤ e−2 2/
  ∑n i=1 c 2 i (6)
  Moreover, we will need the following lemma on group differential privacy.
  Lemma 1. If A is ( , δ)-differentially private with respect to one change in the database, then A is (c , cec δ)-differentially private with respect to c changes in the database.
  Now, we are ready to present the proof of Theorem 2.
  Theorem 2. Suppose that a learning algorithm A is ( , δ)-differentially private and UAERM with the rate ξ(n, , δ). Let S′ = S ∪ U , where S ∼ Dn and U contains c arbitrary outliers. Then
  Eh∼A(S′)l(h, z̃)− Eh∼A(S′)Ez∼Dl(h, z) ≥ T − 2 ( ξ(n, , δ) + √ n(e − 1 + δ)2
  2 log
  2 γ + ec − 1 + cec δ
  ) (4)
  with probability at least 1− γ.
  Proof. Let the probability density/mass defined by A(S′) and A(S) be p(h) and p′(h), respectively. Using Lemma 1, for any z ∈ Z we have
  Eh∼A(S)l(h, z) = ∫ 1
  0
  Ph∼A(S)[l(h, z) > t]dt (7)
  ≤ ∫ 1
  0
  (ec Ph∼A(S′)[l(h, z) > t] + ce c δ)dt (8)
  = ec Eh∼A(S′)[l(h, z)] + cec δ (9)
  It follows that
  Eh∼A(S)l(h, z)− Eh∼A(S′)[l(h, z)] ≤ (ec − 1)Eh∼A(S′)[l(h, z)] + cec δ (10) ≤ ec − 1 + cec δ (11)
  By symmetry, it also holds that
  Eh∼A(S′)l(h, z)− Eh∼A(S)[l(h, z)] ≤ (ec − 1)Eh∼A(S)[l(h, z)] + cec δ (12) ≤ ec − 1 + cec δ (13)
  Thus, we have the following bound:
  |Eh∼A(S)l(h, z)− Eh∼A(S′)[l(h, z)]| ≤ ec − 1 + cec δ (14)
  Moreover, let Si be the set with the ith element in S replaced by z′i. Then, by the same argument above, we have
  |Eh∼A(S)l(h, z)− Eh∼A(Si)[l(h, z)]| ≤ e − 1 + δ (15)
  for all i = 1, . . . , n. Then, using Theorem 3 that relates the first order differences of random functions to their variance, we obtain
  PS∼D[|Eh∼A(S)l(h, z)− ESEh∼A(S)l(h, z)| ≥ τ ] ≤ 2e − 2τ2 n(e −1+δ)2 (16)
  Hence,
  PS∼D[|Eh∼A(S)l(h, z)− ESEh∼A(S)l(h, z)| ≥
  √ n(e − 1 + δ)2
  2 log
  2 γ ] ≤ γ (17)
  Combining (14) with (17), we have
  PS∼D[|Eh∼A(S′)l(h, z)− ESEh∼A(S)l(h, z)| ≤
  √ n(e − 1 + δ)2
  2 log
  2 γ + ec − 1 + cec δ]
  ≥ 1− γ (18)
  Since A is UAERM, the following inequality holds with probability at least 1− γ:
  |Eh∼A(S′)l(h, z)− l(h∗, z)| ≤ ξ(n, , δ) +
  √ n(e − 1 + δ)2
  2 log
  2 γ + ec − 1 + cec δ (19)
  for all z ∈ Z . For a given outlier z̃, it satisfies l(h∗, z̃)−Ez∼D[l(h∗, z)] ≥ T by definition. Combining it with (19), we get
  Eh∼A(S′)l(h, z̃)− Ez∼DEh∼A(S′)l(h, z) ≥ T − 2 ( ξ(n, , δ) + √ n(e − 1 + δ)2
  2 log
  2 γ + ec − 1 + cec δ
  ) (20)
  A.2 ADDITIONAL EXPERIMENT RESULTS
  We list additional experimental results in this section. With more parameters being tested and more metrics being collected, these extensive results further validate our observations presented in the main paper body: differential privacy could improve anomaly detection and backdoor attack detection; and the higher ratio of outliers in the training data, the more noise (smaller privacy bound ) is needed to achieve the best improvement.
  A.2.1 AUTOENCODER ANOMALY DETECTION
  Besides the AUPR scores presented in Table 1 for outlier detection and novelty detection using autoencoders, we present additional results with more parameters being tested in Table 4. The observations are similar. As an intermediate step in differential privacy to bound the sensitivity, clipping itself without adding any noise is able to improve the performance of outlier detection and novelty detection. Adding various amounts of random Gaussian noise is able to further improve the utility, except when the amount of noise is too big (e.g., σ = 50 and 100) to ruin the model. We also indicate the privacy bound as accumulated by the moments accountant mechanism in (Abadi et al. [2016]). Interestingly, many values are too big to provide any meaningful privacy guarantee, but they are still able to improve the anomaly detection performance.
  Besides AUPR scores, we further present AUROC scores in Table 5 for the same set of experiments. Autoencoders, as validated by many previous works (Gottschlich et al. [2017]), present great effectiveness in detecting outliers and novelties, especially when the outlier ratio in training dataset is slow (e.g., below 1%). Although not as obvious as AUPR scores, the improvements brought by differential privacy follow a similar trend, where the improvement is more significant with larger noise (smaller ) being applied to models trained with more outliers.
  A.2.2 IMPROVEMENTS OVER DEEPLOG
  To compare the differentially private models with DeepLog, we utilize the same anomaly detection criteria, i.e., Top-k based anomaly detection as what’s presented in (Du et al. [2017]). Nevertheless, as a direct extension of the idea in measuring model loss for anomaly detection, we also tested the classification probability as one type of threshold for anomaly detection. In particular, if an actual system log entry is predicted with a probability lower than some threshold Tp, we treat this log entry as a detected anomaly. While the baseline DeepLog results are not as good as the Top-k based detection, we show that similarly, differential privacy is able to significantly reduce the number of false negatives, without introducing too many new false positives.
  Probability-based detection. As a preliminary result, we use probability-based anomaly detection to demonstrate the effectiveness of differential privacy noise in reducing FN . Table 6 shows FN and FP for DeepLog and DeepLog+DP with increasing noise levels, under different probability thresholds Tp. It is clear that differential privacy noise could effectively reduce FN , and the larger noise being added, the more false negatives are reduced. We also note that when σ = 0.25, the privacy bound = 90.5. It is often thought that a privacy bound > 20 is completely useless in terms of protecting privacy. Here we indicate that a small amount of noise may be enough to reduce FN . Although more false positives are incurred because of differential privacy noise, the drop in TPR is negligible, considering the large volume of normal data. For example, when Tp = 2 × 10−6 and σ = 1, the FN drop from 1261 to 183 indicates a TNR increase of 8% (91.7%→ 98.8%), while the FP increase from 2291 to 3734 only shows a TPR decrease of 0.3% (99.59%→ 99.32%).
  AUROC score To evaluate the overall performance of DeepLog+DP compared with DeepLog under different thresholds, we further compute the AUROC score of DeepLog and DeepLog+DP with different noise scale σ. As shown in Table 7, DeepLog already achieves excellent AUROC score, considering the large amount of normal data and the significantly fewer anomalies. However, an adequate amount of differential privacy noise is still able to improve the performance.
  Privacy bound Table 7 also indicates the privacy bound . Note that < 10 is often considered as usable and < 1 is a tight bound that well protects privacy. Considering all the cases, σ = 1 gives the best anomaly detection utility as well as a tight privacy bound to protect training data privacy.
  A.2.3 BACKDOOR ATTACK DETECTION
  In this section, we evaluate more parameters for the experiment set up described in Section 4.3 BACKDOOR ATTACK DETECTION, and measure benign accuracy, success rate, AUPR score and AUROC score as explained in Section 4.3 for each experiment setting. Similar as the observations in Section 4.3, a differentially private trained machine learning model is naturally more robust to backdoor attacks. The evidence is that the benign accuracy (Table 8) is affected little by differential privacy except when the noise scale is too big to ruin the model parameters, compared with the significant downgrade (e.g., 98.1% to 0.3%) in backdoor success rate (Table 9). Also, as shown in Table 10 and Table 11, measuring model loss to detect poisoning examples could be useful when the
  poisoning ratio is low. Nevertheless, applying differential privacy is able to significantly improve the detection performance for a poisoning ratio as high as 45%.
title: ROBUST ANOMALY DETECTION AND BACKDOOR AT- TACK DETECTION VIA DIFFERENTIAL PRIVACY