A General Framework for Auditing Differentially Private Machine Learning
Authors: Fred Lu
Joseph Munoz
Maya Fuchs
Tyler LeBlond
Elliott V. Zaresky-Williams
Edward Raff
Francis Ferraro
Brian Testa
Venue: NeurIPS 2022 Accept (2022)
Keywords: differential privacy
privacy evaluation
private machine learning

Abstract: We present a framework to statistically audit the privacy guarantee conferred by a differentially private machine learner in practice. While previous works have taken steps toward evaluating privacy loss through poisoning attacks or membership inference, they have been tailored to specific models or have demonstrated low statistical power. Our work develops a general methodology to empirically evaluate the privacy of differentially private machine learning implementations, combining improved privacy search and verification methods with a toolkit of influence-based poisoning attacks. We demonstrate significantly improved auditing power over previous approaches on a variety of models including logistic regression, Naive Bayes, and random forest. Our method can be used to detect privacy violations due to implementation errors or misuse. When violations are not present, it can aid in understanding the amount of information that can be leaked from a given dataset, algorithm, and privacy specification.

A General Framework for Auditing Differentially Private Machine Learning
Fred Lu Booz Allen Hamilton
Joseph Munoz Booz Allen Hamilton
Maya Fuchs Booz Allen Hamilton
Tyler LeBlond Booz Allen Hamilton
Elliott Zarlsky-Williams Booz Allen Hamilton
Williams
Edward Raff Booz Allen Hamilton
Francis Ferraro
University of Maryland, Baltimore County
Brian Testa"
Air Force Research Laboratory
Abstract
We present a framework to statistically audit the privacy guarantee conferred by a differentially private machine learner in practice. While previous works have taken steps toward evaluating privacy loss through poisoning attacks or membership inference, they have been tailored to specific models or have demonstrated low statistical power. Our work develops a general methodology to empirically evaluate the privacy of differentially private machine learning implementations, combining improved privacy search and verification methods with a toolkit of settuence-bbssd poisoning attacks. We demonstrate significantly improved auditing power over previous approaches on a variety of models including logistic regression, Naive Bayes, and random forest. Our method can be used to detect privacy violations due to implementation errors or misuse. When violations are not present, it can aid understanding the amount of information that can be leaked from given dataset, algorithm, and privacy specification.
Introduction
Machine learning (ML) is increasingly deployed in contexts where the privacy of the data used to build the model of concern. ML models are capable of ingesting enormous quantities of data in order to determine meaningful predictive patterns. When such models are built on potentially sensitive inputs such as healthcare | or financial data [2] becomes important determine to what extent information from the training dataset can be inferred from the model. Such information can of personal interest when the identity of a data contributor may compromised based on involvement in the data collection process [3] 4 but it can also lead to regulatory concern about whether model trained on private data should itself be considered private
Differentially private (DP) machine learning is theoretically rigorous approach that provides worst- case privacy guarantee for ML algorithms that the distribution of possible output models based the input dataset is not significantly altered whether an individual data point is included in the training set or not. This is accomplished by randomizing the output model in specific manner that the distributions of the model trained
(6) Specifically, provides a mathematical guarantee
Approved for Public Release; Distribution Unlimited. PA #: AFRI-2002-3247
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

with or without any individual data point are statistically indistigguishable up to level specified by parameters e, that must be set appropriately. While DP mathematically certifies the privacy of mechanism, the noise added is generally tailored to the worst case scenario.
Previous results attempting to assess the privacy leakage of such models, using attacks ranging from membership inference to model inversion, have inferred that the actual detectable risk of model procedure is lower than the theoretical bound 7 8. While a recent study on DP neural networks indicates that the privacy guarantee of the DP-SGI algorithm is tight under the strongest adversary 29 the privacy risk under realistic datasets and attackers without complete access to the training process still lies below the worst case bound. Across other models, the question remains of whether the privacy violation of a mechanism is lower than specified or whether the attacks previously used not strong enough. Given that there are guidelines on how set e, 5 in practice, it would be useful for practitioners to estimate the actual risk they incur in practice and set the parameters accordingly. This is critical when DP for ML is still a nascent field, with limited implementations that can be hard to verify.
Recent works have shown that simple DP mechanisms can be audited effectively IT These mechanisms generally map an input vector to a perturbed output vector, and are often used as building blocks of more complicated DP algorithms such as machine learning models. Examples include the Laplace and exponential mechanisms which are respectively used in DP Naive Bayes and random forest 12 3 The auditing procedure involves searching for optimal neighboring input sets a, a' and sampling the DP outputs M(a), M(aa).M(a') to get a Monte Carlo estimate of E. To extend these techniques to audit a machine learning model, the vector inputs a, a' are replaced with datasets D. D' which differ by a single entry. Working in this realm raises important challenges. First, previously effective search methods for neighboring inputs involving enumeration or symbolic search impossible over large datasets, making it difficult to find optimal dataset pairs. In addition, Monte Carlo estimation requires costly model retraining thousands of times to bound & with high confidence.
We propose solutions to these problems to accommodate the general auditing approach to machine learning algorithms. For the first concern, we develop a set of data poisoning attacks which perturb a single point of dataset D. approximating a worst-case neighboring dataset D' specific to M. To address the second, we present a statistical framework combining elements of Bichsel et al. [I]] and Jagielski et al. [4] to estimute for general ML procedures for smaller sample sizes. Our techniques involve improved estimation bounds and, more significantly, learning probabilities over general model spaces, while previous works can only estimate probabilities over single output (the predictive probability).
These novel contributions form framework ML-Audit for auditing the DP of arbitrary machine learning models. Compared to prior works we can obtain orders of magnitude improvement in the estimation of that are effective across larger range of e, more datasets, and more model types. Our framework is compatible with prior model-specific approaches (small neural networks), obtaining similar or improved efficacy. Further still, provide case studies where our framework detects potential violations in existing implementations of DP machine learning.
We review these prior approaches in /ection 2, we present our framework in section 4| followed by results and discussion in section 5 Finally we conclude in section 6
and introduce key DP concepts in section 3
Then
2 Related work
Although differential privacy of a mechanism is established with mathematical proof, previous work has shown that holes can exist, either in theory, such as the sparse vector mechanism (of which erroneous versions have been proposed (TC) or implementation, for example sampling non-uniformity in pseudo-random number generators [5] Such occurrences point to the need for empirical verification of the promised security of differential privacy mechanisms. This is critical as lapses in DP are likely to provide greater predictive performance, so choosing model to obtain maximal accuracy given a chosen level of privacy is likely select these errant models.
Recent works propose efficient solutions for auditing simple differential privacy mechanisms operating on scalar or vector inputs ITC I1. such cases, the neighboring inputs can be enumerated tractably (c.g. for a vector input, trying adding one to each input element). For each neighboring pair, the
2

---

appropriate output set is determined. and Monte Carlo probabilities are measured to determine privacy. The sampling process in such mechanisms is vectorized to greatly reduce the runtime [.. These works develop a rigorous statistical framework for DP auditing which serves as the basis of current MI. auditing approaches, including our work.
Few studies have attempted to audit DP machine learners. We are aware of two works that measure the privacy of neural networks trained with the DP-SGD mechanism [T]. Jagielski et al. [4] develops a poisoning attack (CIipBKD) by constructing a data point along the axis of least variance in the dataset. This causes the gradients of the point to be distinguishable, mitigating the effect of the DP-SGI clipping and noise. Since this attack is model-agnostic, we adopt it as a baseline for all our models. We show considerably improved performance with our method and that the least variance approach suffers as the sphericity of the dataset increases.
The second work analyzes DP-SGD through a series of increasingly white-box attacks ( that while the DP-SGD privacy guarantee is formulated for all neighboring datasets, the mechanism itself operates purely via gradient manipulation. Therefore they are able to formulate stronger attacks which directly target the gradient make use of adaptive poisoning. While these are not usable for general-purpose ML auditing, we implement their poisoning attack, based on adversarial perturbation, for our DP-SGD experiments. We find that this attack performs comparably with ClipBKD on DP-SGD.
They note
While their works are important progenitors to ours, they estimate the privacy loss by thresholding a single scalar output, c.g. the loss specific poisoning point. This is major bottleneck limiting the ability to audit other machine learning algorithms. Instead of a scalar, our approach learns distributions over any vector representation of model, allowing to be the first to propose general procedure for auditing any DP learner.
Another predecessor established the complementary relationship between data poisoning and differen- tial privacy, using poisoning attack based on gradient ascent of logistic regression parameters 0 with respect to x to reach a target 0 17. The result has similar form to a perturbation influence function which we discuss [18 19]. However, the aim of their study is evaluate the effect of differential privacy on poisoning strength rather than vice versa. addition, their attack formulation requires manual gradient computation which does not readily extend to other models. We include a form of their attack to compare in our logistic regression experiments.
Differential privacy overview
We provide background on key elements of differential privacy relevant to our work.
Definition 3.1. A randomized learner M: D x B + θ is funcioon mapping a training dataset D E and auxiliary noise b to an output model e e.
If we train the learner repeatedly on the same dataset, we can obtain a different model 0 each time based on the noise source b. For simplicity we implicitly denote the learner as randomized function M(D) with probability distribution induced by
Definition 3.2. A randomized learner M considered (e, -iiiffferentially private if for all datasets D' E D differing in single entry and measurable sets S over the output space O
P(M(D) S) S <TP(M(DD) E ES)+ 6
In this definition, the term is the primary quantity of interest because it bounds the ratio between model output probabilities when the original dataset is perturbed by a single row. Setting s = = would enforce that M (D) equals M (D') in distribution, while large to be arbitrarily different. As E > do the model distribution converges to Ma (D), which in most cases is identical to the standard non non-private version of the model. The 8 term permits some additive slack in the probability bound, but in most purposes is set to an o(1/n) quantity.
8 permits the distributions
Given and M calibrates the noise distribution to the sensitivity of the model function 20
Definition 3.3. The sensitivity of a function f D - Rdd is maxp, [I[ - S(D')) where D, D' differ by one row.
3

---

RMMDD
D
samples
M(D) M(D)
p(D|z)
Dataset
M
perturbation
D
Figure 1: Auditing procedure: A given dataset is perturbed to get D'. Mechanism M is trained on the D and D' generate N samples each. A classifier trained the samples learn the posterior probability of dataset conditional on mechanism output z. A threshold / determined based on false positive constraint to determine the output set S.
Our main goal is to audit the privacy of known mechanism whose inner workings may be hidden, so we assume in our work that the user has access to the mechanism, the privacy parameters, and the dataset, but does not have control over the training process or the randomness b.
The final tool which we will employ in our framework is group privacy, which iterates over Eq. t bound the probabilities when D, D' differ by multiple points.
Lemma 3.4. Suppose M is (e, -ppivvate and D, D' differ by rows. Then for all measurable SCC. O,
ckk
P(M(D) E S PMM(MD E + 1 e
4 Auditing framework
A DP mechanism calibrates its randomization to user-specified Eth. representing the desired theoret- ical level of privacy. The goal of DP auditing is to empirically assess the actual privacy enabled by the mechanism, s*. To do this, we determine lower bound for with high statistical confidence. Observe that rewriting the definition of DP gives
In P(M(D) S) 5
P(M(D') E S)
For any given D', S) we can estimate the quantity with Monte Carlo by retraining M generate samples and then compute a 95% confidence interval. The lower bound of the interval én is the detected privacy violation, and with high probability, we state that witness. By maximizing Éng over all possible witnesses, we increase the lower bound on =* which we can then compare against the promised Eth- Given a mechanism M, the auditing objective is then to find
En with (D, S) as
sup supln F(M(D) S) 8 P(M(D') ES)
D.D' S
that is, the maximum privacy loss ratio over neighboring datasets D, D' and measurable output set S. For all mechanisms considered in this work d < 10 which is not detectable, so we simplify by setting O.
A successful auditing approach requires solutions to the two separate maximizations. We maximize over D, D' by developing a toolkit poisoning attacks which have the largest influence on the mechanism in question. Once D and D' are obtained, we fit likelihood ratio-based optimization to determine an appropriate S. In the following, we discuss these procedures in detail.
4.1 Optimizing D, D'
Given a dataset D (X, Y)) we define a valid poisoning attack to be an operation which selects an existing data point (z, y) and perturbs to any new point x² within a constraint set C. As we consider classification algorithms in this work, the class label y can also switched. The constraint C is specific to each DP algorithm and is used to determine the max sensitivity bound from Def. 3.3 (as otherwise a single data point can arbitrarily affect the model). Without loss of generality, we set the constraint to be the smallest containing the training data.

---

This is the only part of the framework which needs user design, as a strong attack against one mechanism may not be effective against another. However we distill the steps for constructing such attacks into a recipe:
1. The underlying model of .M can be abstract, requiring summary function 7 to embed M into vector space. Since post-procsssing of DP outputs does not decrease privacy [6], we can select T to preserve as much information about M as possible. In logistic regression the transformation is natural: we define T o M as the coefficient vector (Table D. To reduce notation overload we implicitly apply т when we discuss empirical samples ~ MMD).
2. Obtain a non-private algorithm Moe (D) as a surrogate. Note that as long [M[M(D, b)] = Mo (D), meaning the DP model on average equivalent to the non- non-private version, is sufficient to find the optimal poisoning with respect to the non- non-private model. While not explored in this work, attacks can instead take into account the actual noise distribution by averaging over samples of MMD,bu b), at the cost of additional run-time.
3. Determine poisoning (a", ,y" from (r, y) maximizing the distance between and TMM (D))). This involves a selection and a perturbation step.
Bound C
Summary T
Log. reg. NB
L2-norm
coefficient 0
hyper-rectangle
Pyd: d Ty
RF
hyper-rectangle
Pr(x*) ) each tree Pr(x*), Pr(O), Pr(afest)
DP-SGD
L2-norm of VaL(x, y; 0)
Table I: Constraints and summary functions used.
Ahead we detail the poisoning attack design for each mechanism:
Logistic Regression, DP logistic regression achieved using one of three approaches: objective, output, gradient perturbation. We evaluate objective and output perturbation using the widely used method developed by Chaudhuri and Monteleoni [1] and Chaudhuri et al. [22]
For the attack we adopt the influence function, a technique which estimates the change in a model when a specific data point is infinitesimally upweighted in the training set [19 23 For general model with gradient and Hessian information, the effect of point xx on the model parameters for a loss function I. can be approximated as In(x*) - H LVL("". 0). In generalized linear models with canonical link function where L is the negative log likelihood, this has a closed form involving the Fisher information as the expected Hessian [18]. which for logistic regression evaluates to [x()*) = (y* -y)==))(X'*" WX+ === where W is diagonal matrix with entries Wt. 0. (1(1-))) ūt). and À regularization.
We choose to be the coefficient vector 0, of Mo (D), (D') respectively. We first select (a, y) closest to the corner of the hyper-rectangle containing the data (a heuristic for selecting point far from where the separating hyperplane would likely be) and initialize (x", ,v") as the mean point in the opposite class. Since our goal is to increase the distance ||0 8'112. we optimize the L2 norm of the influence function using projected gradient ascent. The constraint set C is the L2 norm ball containing the training set, so after each iteration we clip x needed.
Naive Bayes. The Gaussian Naive Bayes model parameterizes the classccondiiional distribution of features using independent Normal distributions. The parameters involve a mean Ugd and variance Ly for each feature and class combination, as well as prior probabilities for each class Ty. To achieve differential privacy, Laplace or Geometric noise are added to the maximum likelihood estimates for each parameter [12]. The constraint set C is reper-re set by the smallest and largest value of each feature in the dataset.
We choose T to be the vector of all {Kyds yas Ty The maximum influence a perturbation can have on ji of class y is by selecting point on the corner of the hyper-rectangle C nearest the data points of class y and placing it on the corner furthest away. On the other hand, the maximum influence attack on ny is to flip a class label. We combine the two ideas by flipping the class label of the point closest to corner. In our experiments compare the power against only attacking My.
5

---

Random Forest. The DP random forest mechanism uses unsupervised random splits of the features based on the domain of the inputs. Each tree is split to a pre-determined depth. Then the training points are percolated through the forest, and the majority label of each leaf is sampled from the Exponential mechanism [03.. Thus a perturbed training point has no impact on the actual tree structure besides the potential label of single leaf in each tree. As result we measure only the change in those leaves, choosing T to be the prediction of each tree on x².
The most detectable change in probability occurs when j = 1 and then the majority class is swapped by class flip. For example, if a leaf has one positive and two negative points, we flip the class of one of the negatives, Since each tree is random, there is no guarantee that any given point will be in such a situation where = 1, but to increase this chance we target points which are likely to be solitary in each leaf. Thus we select the point most distant from the rest of the training set as measured by L.1 disttnnec and flip its label. We provide further exposition and hyperparameter details in the Appendix.
DP-SGD. For DP-SGD we evaluate two extent poisoning attacks using our framework. The ClipBKD attack constructs a data point along the axis of least variance in the dataset [4. This can be performed by taking the eigenvector of the covariance matrix with the smallest eigenvalue, and then projecting to the median L2 norm of the training set. This point is assigned the label with smallest predicted
probability. The goal of this attack is to enable the gradients of the point to be distinguishable, mitigating the effect of the DP-SGD clipping and noise.
The second attack selects random datum and maximizes the loss with gradient ascent. The loss is defined with respect to a set of trained shadow models [9]. In both attacks, the outcome r (M((D) being measured is the predicted probability of the perturbed point PM 1), while ClipBKD first subtracts the zero vector's 's predicted (0) We also consider an updated ClipBKD with the zero prediction encoded separately with additional test predictions in r: (M) (M
4.2 Optimizing S
Our approach for determining S is based on the framework of Bichsel et al. M. which derives the optimal region for distinguishing two vector distributions. Given candidate datasets (D,D') with DP distributions M(D) and M(D'), we seek S maximizing (PM((D) E S))P(M(D") E S). Let MM(D) and fM(D') be their respective densities. Selecting S to best distinguish two distributions is analogous to identifying optimal rejection region in hypothesis testing. From the Neyman- Pearson Lemma (cf. Appendix), the maximum power test at level is defined by rejection region > k} for some k >> O, where (PM((D)) E S)
S (=
(24]
and we are selecting points to fill S where D is more likely than D'. We start by adding points where D is most likely and work downwards until S is large enough that there is c chance that M(D') is erroneously in S.
Intuitively, we have a likelihood ratio (=)
Directly obtaining these densities intractable. Instead we can learn, given collected samples {M(D)) } where D E D'),'), the posterior probability of the dataset D:
p pDD|=) = Pr(D DIM(DD= = 2)
Let us consider the set L* {a |(Dl))//((D)))) > k). From Bayes' Theorem we know p(D]2) x (=) P = D). Given equal samples of D from D and D', then P(D = D) = P(D = D')
implying (())))/((D'(>>
fM()))
Therefore S = I and we use it as the rejection set. Finally, we can further simplify S by observing that p(D)=) + pDDl2))
1, and S {= 1p (D]=) > 1) where = k/((1 + k). What remains is to set /. according to the level e so that P(M(DD) E S) = c. As this is equivalent to P(p(D))) t ||2 ~ MMD')), we set empirically to correspond to the (1 qq-quae of M(D).
Our approach introduces the following further adaptations on Bichsel et al. || to enable auditing on slower, potentially expensive machine learning mechanisms. (The original work used around 10a samples for auditing simple mechanisms, which is infeasible for training machine learning models. We use N 10000 samples for all mechanisms except DP-SGD where N 500.)
1. We make the method flexible by searching e empirically to maximize εw., rather than setting c = 0.01 as in the original. When N + oo, smaller values of are optimal since the likelihood ratio largest. At smaller sample sizes, however, this is offset by increasing uncertainty in Monte Carlo estimation of small probabilities.

---

Algorithm 1 ML-Audit: Optimizing output set S
Require: Datasets D, D', DP mechanism M, min. probability constraint confidence a, sample
size N
1: Sample 21,..., MM(D,, 2i....,, z'y ~ M(D')
2: Generate labels y4 = if 24, else y, = of
3: Train classifier {z, z)) {y} to learn (D())
4: Pl..... PN + Po [ 21 (1)).....P.) (D
5: Pı..... PN po D 21) ..... Po
6: Eib t -0;
7: for in sort( u (p,))) do
8:
T1 E; (p t)
9:
no + E: 1(p 2)
10:
if noooNo /N/NN rrthn
Avoid estimating probs <
11:
skip to next iter
12:
<ip f- Eps LB(n), no. NN, a/2)
Lemma A.3
if E > En then
14:
Etb + Eib
15:
itt t
16:
return S t {a >
2. We use group privacy to increase statistical distinguishability a trick used also in Jagielski et al. [14]. After obtaining (x* y=*,)"), insert & copies of the point. From Lemma 3.4 the detected privacy éts. is reduced to éis/ However, the extra copies causes MMD') to be more distinguishable which makes PDM(DD S) larger relative to P(M((D) S). This is also a tradeoff: At small true e the lower bound Ed improves despite division by k, whereas at high the distributions are sufficiently different at k I that it is not worth dividing ē.. We include empirical analysis of k in our Appendix.
3. All previous auditing works (including below) use Phopper-Pearsonn intervals for p1 and Po to determine the lower bound. This method is highly suboptimal because it separately bounds the numerator and denominator. We identify instead the Katz-log confidence interval to directly bound the ratio of binomial proportions coverage properties in our simulations, as shown in the Appendix.
[25], see Lemma A.3 This has far better
Our modified procedure is presented in Algorithm ① and summarized visually in Fig.
Comparison to other approaches. While our method allows MMD) to any vector of information, the previous works auditing DP-SGD require M(D) to be single value (e.g. prediction probability or loss) and search for a threshold dividing the score into S and S g [4. Our method can reduce to this special case by choosing to map scalar. The approach can be interpreted as membership inference with the bound FN + FP < 1-16 8 from Kairouz et al. (26), where (M(D) E S} are true positives and (M(D') 5} are false positives. These works also note that flipping the definition of false positive and false negatives enables testing the complement P(M((") E St) /P))P(M(D) E S*). As in those works we select S instead of S if it gives higher Eus.
Corollary 4.0.1. Given Algo. 1 and N samples, the highest detectable privacy risk is
I N
In(N) - 2a/2
Estimating Esp. After (D, D', S)k are determined, the final step to draw N fresh samples of (D) and (DD) for an independent Monte Carlo verification. As in the search phase, we compute ni = Σ, (DM E S), no Σ, (DM(D) E S) and use the lower bound of the Katz log interval to return our final estimate Eup.
To avoid biasing the confidence interval, is important that the final MC estimate is conducted on an independent set of samples, as done in [1] 14 This is especially the case when optimizing over thresholds in S. Since we compute a interval over for each threshold, using the best result from the same sample would lead to biased inference from multiple testing.
7

---

5 Experiments and Results
Cipaco
Corld
Perentio
Spece
15:
Spectad
Spac
(a) adult dataset
Logiti ro. Intendive
Lopat my In
Nokve Soyes
Nender feent
Medact
Portat
Seard
3--
(b) credit dataset
Chipeo
Wanueer
6.5
14
16
Spa/kel
(c) iris dataset
Logitii mo. Inteetive
LogRecing HADLO
Natve Dagnr
Sander fieit
Seepi Themss0
Smep Twor6001
Desple
635-
(d) thoracic dataset
Figure 2: Specified (x-axis, log-scale) vs detected privacy risk (y-axis, log-scale) using our ML-Audit framework comparing our perturbation attack (blue), ClipBKD (orange) and row-swap baseline (green), over four datasets. For logistic regression, an additional poisoning attack (red) can be considered an ablation of our approach. Remaining datasets in Appendix FFigure 5] In highly non- spherical datasets such as iris, row-swap performs comparably to ML-Audit on logistic regression, which we discuss in
We evaluate the DP mechanisms over a range of Es.: {0.1, 0.25, 0.5, 1, 4, 16, 50). &t = 0.1 the ratio of probabilities is bounded by ed.1 1.1 giving nearly indistinguishable distributions, whereas at Esh. = 50 essentially no privacy is guaranteed. For a given dataset D, we perturb k (1, 2, 8) points get D' and train N 10000 times for each determine the appropriate auditing set S. Then we obtain N new samples to perform the final Monte Carlo estimate and obtain the lower bound év. We use confidence level 0.05 throughout.
We assess Naive Bayes, logistic regression (output and objective perturbation), and random forest on common machine learning datasets: adult, credit, iris, breast-cancer, banknote, thoracic. We use the diffprivlib library [77] and implement output perturbation following [22]. Additionally, we test
DP-SGD on FMNIST and CIFARIO (here with N = 500) using 28 Refer to Appendix for more details.
Figure 2 directly compares, over three datasets, the Éns obtained by our poisoning attacks (ML-Audit), the ClipBKD attack, and baseline where a random data point is changed to random point from the opposite class without changing labels (Swap-X). (Note that while the original ClipBKD work uses DP-SGD, the poisoning itself mechanism-agnossicc, so an appropriate baseline.) We replicated our procedure 3x and show the median éu. The Katz log interval was used for the lower bounds even on the baselines. As a reference we plot the theoretical privacy loss up to the maximum detectable limit (Corollary 4.0.
8

---

For the logistic regression experiments we include an additional alternative of our approach where the modified point, rather than maximizing the influence, is optimized to target a specific coefficient vector (labeled Poisoning). The method is based on the coefficient attack of 17 gradient- based optimization approach with similar form to ours. Heuristically, we want the target coefficient vector to be as distinguishable as possible from the original optimal linear coefficients, so we constructed a perpendicular vector to the original coefficients using cross products. This method, which only exists for logistic regression, can be considered an ablation of ML-Audit with a weaker attack.
Our attacks consistently and often dramatically outperform baselines across datasets, models, and ehh- In some cases, the privacy detection is within small factor (1 (1-22) -2x) of optimal. The Poisoning attack close to our attacks in some datasets but performs poorly others. The Swap-X baseline shows the expected privacy loss of an attack which poisons data point within the original data distribution, rather than a worst-case perturbation (e.g. swapping two points the training set). The only case where Swap-X X performs similarly to our tailored attacks is in on separable datasets with high non-sphericity such as iris and breust-cancer. We believe these properties enable simple strategies to work well (see Fig. Bp.. We believe this is not a meaningful difference in performance as both methods are near the limit of what can be theoretically detected. Our results validate previous findings showing that estimating using membership inference-basee bounds are weaker than poisoning attacks and found it ineffective.
logistic regression
We also tried the foss-threshold attack of 29
On many models and datasets we obtain nearly optimal results, indicating that these datasets are close to the maximal sensitivity of the mechanism. We observe this for random forest at EeΛ S 2 but also a plateau in higher Eth. This is likely due lack of resolution in the outputs: an average over m tree decisions only takes m unique probability values. Our attack on Naive Bayes is also near-optimal, while varying among datasets. Since the algorithm assigns Esh /3 to protect each Myd, og and Ty. perturbation needs achieve the sensitivity bound all three reach the theoretical privacy risk, with the bound over all pairs D, D' rather than conditioning on starting D. For example, to reach the bound for μ., all points of one class must be in one corner of the hyper-rectangle and the poisoned point on the other corner, which is unrealistic. For this reason, our choice of attacking the class prior I is generally more effective than attacking the mean μ (Fig.
Lastly, our DP-SGD experiments assess the two existing perturbation methods of 9 14] Our findings (Fig. g consistent with what is reported in those works. Interestingly, we find that the shadow adversarial attack outperforms ClipBKD on FMNIST and vice versa on CIFAR1O. We also updated ClipBKD to additional information in detailed in Section 4.]and and find moderate improvement on FMNIST. Refer to the Appendix for further discussion.
Dataset-specifit attack comparisons. Previous work hypothesized that privacy attacks realistic datasets do not cause the model shift to reach the worst-case given by the sensitivity bound, except when the attacker can completely specify the dataset [9] Based on our observations on the impact of the dataset distribution on attack strength, our evidence supports the hypothesis that achievable privacy is mataset-dependeed We believe theoretical analysis of datasets for attack risk to be useful for future work.
10a
breast_caaaee cancer
CligBKD Ours
20x
Clipec influence
Inis
1.0
Autitinn improvement
Infuuence
10a
202
banknote
adult
1x
10a
10a
102
Figure 3: (a) Non-sphericity vs ClipBKD influence (b) Influence of rest cancer to our perturbation explains the difference in performance across datasets.
Non-sphericity
baninote
maracie
credit
actult
LDBKD perturbation compared

---

We briefly investigate this phenomenon by comparing the performance of ClipBKD by dataset sphericity, as computed by ratio between largest and smallest singular values. An attack on the direction of least variance is likely ineffective when the dataset is spherical. We observe strong relationship between the non-sphericity a dataset and the influence of the ClipBKD perturbed point in Fig. 3a. In comparison our influence- attack consistently finds a higher influence value (Fig. Bb). Furthermore, this difference in influence is directly linked to the auditing improvement of our approach compared to ClipBKD.
Detecting violations in privacy. We discuss two case studies where privacy leaks occur in practice and are detected by method. First, the Naive Bayes mechanism in difsprivlib exposes perturbed class counts in the API. However, the sum of class counts is enforced to be the dataset size. This means whenever (D, D') differ by one row in length no privacy guaranteed. When we include the exposed class counts as part of r, our framework detects maximal privacy loss at all ErA (Fig. F.). We therefore recommend that only the class priors and not counts be made accessible.
As another example, in some works DP defines neighboring datasets can only have a single row addition or deletion, while others allow modifiying an existing point (equivalently deleting and then adding row). This means that depending or double what the user desires to obtain. Our auditing framework correctly detected this discrepancy in the DP random forest, which defines under the first option. Our estimated é using the second definition exceeded the theoretical level until the definitions were reconciled.
the implementation, the actual privacy level may be half
Naive Bayes attacks (iris)
Obj. logistic ablation (credit)
Influence, T(M)
Influence, =(x)
CligBKD, r(M)
Clio8KD, r(M) p(x")
Measured g
Measured g
Theoretical
class prior attack class attack
class count leak
Theoretical
Specified
Specified
Figure 4: (a) Naive Bayes: Optimal attack on π (blue) compared to attacking μ (orange). However, when D, D' differ in length and class counts from the API are obtained, all privacy is compromised (red). (b) Logistic regression ablation showing incremental improvements when upgrading the baseline ClipBKD (purple) to our approach (blue).
We reiterate that the advantages of approach over precursors (1) improved perturbation attacks on D, and (2) optimizing a likelihood attack S on any summary function t of a model M. Our final ablation in Fig. 4 highlights these strengths by demonstrating the incremental improvement ClipBKD when either (1) or (2) are added.
Conclusion
We have proposed ML-Audit, a framework for estimating the differential privacy of a ML model. ML- Audit provides recipe for devising audits against arbitrary models and often orders of magnitude more effective than existing approaches sometimes 2x of theoretical optimum.
7 Acknowledgments
Approved for Public Release; Distribution Unlimited. PA #: AFRL-2022-3247.
References
[1] C-A Azencott. Machine learning and genomics: precision medicine versus patient privacy. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 376(21288):01103350 2018.
10

---

[2] Amir E Khandani, Adlar J Kim, and Andrew W Lo. Consumer credit-risk models via machine- learning algorithms. Journal of Banking & Finance, 34(11):767-27877 2010.
[3] Aleksandra Slavkovic and Fei Yu. O privacy, where art thou?: Genomics and privacy, Chance, 28(2):37-39, 2015.
[4] Matthew Fredrikson, Eric Lantz, Somesh Jha, Simon Lin, David Page, and Thomas Ristenpart. Privacy in pharmacogenetics: An end- to-end case study of personalized warfarin dosing. In 23rd [USENIX} Security Symposium ( {USENIX] Security 14), pages 17-32, 2014.
[5] Rachel Cummings and Deven Desai. The role of differential privacy in gdpr compliance. In FAT Proceedings of the Conference on Fairness, Accountability, and Transparency, 2018.
[6] Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 96344)211-407, 2014.
[7] Bargav Jayaraman and David Evans. Evaluating differentially private machine learning in practice. In 28th (USENIX) Security Symposium (USEENIX) Security 19), pages 1895-1912, 2019.
[8] Nicholas Carlini, Chang Liu, Ülfar Erlingsson, Jernej Kos, and Dawn Song. The secret sharer: Evaluating and testing unintended memorization in neural networks. In 28th {USENIX] Security Symposium (UUEENIX) Security 19), pages 267-284, 2019.
[9] Milad Nasr, Shuang Song, Abhradeep Thakurta, Nicolas Papernot, and Nicholas Carlini. Ad- versary instantiation: Lower bounds for differentially private machine learning, arXiv preprint arXiv:2101.04533 2021.
[10] Zeyu Ding, Yuxin Wang, Guanhong Wang, Danfeng Zhang, and Daniel Kifer. Detecting violations of differential privacy. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pages 475-489, 2018.
[11] Benjamin Bichsel, Samuel Steffen, Ilija Bogunovic, and Martin Vechev. Dp-sniper: Black-box discovery of differential privacy violations using classifiers. In 2021 IEEE Symposium on Security and Privacy (SP), pages 391-409. IEEE, 2021.
[12] Jaideep Vaidya, Basit Shafiq, Anirban Basu, and Yuan Hong. Differentially private naive bayes classification. In 2013 IEEE/WIC/ACM International Joint Conferences Web Intelligence (WI) and Intelligent Agent Technologies (IAT), volume pages 571-576. IEEE, 2013.
[13] Sam Fletcher and Md Zahidul Islam. Differentially private random decision forests using smooth sensitivity. Expert systems with applications, 78:16-31, 2017.
[14] Matthew Jagielski, Jonathan Ullman, and Alina Oprea. Auditing differentially private machine learning: How private is private sgd? Advances in Neural Information Processing Systems, 33, 2020.
[15] Ilya Mironov. On significance of the least significant bits for differential privacy. In Proceedings of the 2012 ACM conference on Computer and communications security, pages 650-661, 2012.
[16) Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308-318, 2016.
[17] Yuzhe Ma, Xiaojin Zhu Zhu, and Justin Hsu. Data poisoning against differentially-prii privvat learners: Attacks and defenses. In International Joint Conference on Artificial Intelligence, 2019.
[18] Daniel Ting and Eric Brochu. Optimal subsampling with influence functions. Advances in neural information processing systems, pages 3650-3659, 2018.
[19] Pang Wei Koh and Percy Liang. Understanding black-hox predictions via influence functions.
In International Conference on Machine Learning, pages 1885-1894, PMLR, 2017.
11

---

[20] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265-284. Springer, 2006.
[21] Kamalika Chaudhuri and Claire Monteleoni. Privacy-preserving logistic regression. In NIPS, volume 8, pages 289-296. Citeseer, 2008
[22] Kamalika Chaudhuri, Claire Monteleoni, and Anand Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12(3), 2011.
[23] Frank R Hampel. The influence curve and its role in robust estimation. Journal of the american statistical association, 69(346):383-333, 1974.
[24] Erich L Lehmann and Joseph P Romano. Testing statistical hypotheses. Springer Science & Business Media, 2006.
[25] Morten W Fagerland, Stian Lydersen, and Petter Laake. Recommended confidence intervals for two independent binomial proportions. Statistical methods in medical research, 24(2):224-254 2015.
[26] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In International conference on machine learning, pages 1376-1385. PMLR, 2015.
[27] Naoise Holohan, Stefano Braghin, Pôl Mac Aonghusa, and Killian Levacher. Diffprivlib: the ibm differential privacy library. arXiv preprint arXiv:1907.024444 02444, 2019.
(28) Ashkan Yousefpour, Igor Shilov, Alexandre Sablayrolles, Davide Testuggine, Karthik Prasad, Mani Malek, John Nguyen, Sayan Ghosh, Akash Bharadwaj. Jessica Zhao, Graham Cormode, and Ilya Mironov. Opacus: User-friendly differential privacy library in PyTorch. arXiv preprint arXiv:2109. 12298, 2021.
[29] Samuel Yeom, Irene Giacomelli, Matt Fredrikson, and Somesh Jha. Privacy risk in machine learning: Analyzing the connection to overfitting. In 2018 IEEE 31st Computer Security Foundations Symposium (CSF), pages 268-282. IEEE, 2018.
[30] DISM Katz, J Baptista, SP Azen, and MC Pike. Obtaining confidence intervals for the risk ratio in cohort studies. Biometries, pages 469-474, 1978.
12


Reviews:
[{"review_id": "TNyCogsS1fs", "reviewer": "Reviewer_7BRu", "summary": "The paper proposes a general methodology to empirically evaluate the privacy of differentially private machine learning implementations, combining improved privacy search and verification methods with a toolkit of influence-based poisoning attacks. The paper proposes specific data poisoning schemes for algorithms like Logistic regression, random forests, and Naive Bayes.", "questions": "Can you clarify (3) and (4) in the weakness.", "limitations": "Some of the improvements over prior work are specific to the learning tasks. (For example, the exact choice of influence function for logistic regression.)\n\nThe empirical results seem to be specific for delta=0 setting.\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. I found the idea of estimating the probability over general model spaces as opposed to the probability over a single output to be interesting.\n\n2. I also found the usage of local geometry for logistic regression to estimate the poisoning example to be very interesting.\n\nWeaknesses:\n\n1. The framework of auditing seems to be identical to prior work. So, the paper may have oversold the contribution.\n\n2. Some of the improvements over prior work are specific to the learning tasks. (For example, the exact choice of influence function for logistic regression.)\n\n3. I found the result for objective perturbation to be rather surprising. The fact that ML audit matches the theoretical bound is a bit counter intuitive. The reason being that in objective perturbation, typically the epsilons are split to ensure that both the ratio of Jacobians, and the log offs over the model outputs do not change by much. Unless the split is tuned for the best poisoning attack, I cannot intuitively see the curves to match. \n\n4. Are the results for objective perturbation specific to pure \\epsilon DP? If not, then one has to use the bounds from Keifer et al. for the Gaussian distribution.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "RbHqEUT-3py", "reviewer": "Reviewer_8PAF", "summary": "The paper proposed ML-Audit, a framework for estimating the differential privacy of a ML model. It is a general methodology to empirically evaluate the privacy of differentially private machine learning implementations, combining improved privacy search and verification methods with a toolkit of influence-based poisoning attacks. ML-Audit provides a recipe for devising audits against arbitrary models and is often orders of magnitude more effective than existing approaches.", "questions": "Nothing to ask", "limitations": "Nothing", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The idea of proposing a framework for estimating the differential privacy of an ML model is quite novel and significant, as it is more universal with qualitatively improved performance.\n\n2. The experiment session is solid, since this paper assesses Naive Bayes, logistic regression, and random forest on 6 common machine learning datasets and is compared with several strong baselines.\n\n3. DP-based machine learning methods are theoretically rigorous approaches that provide a worst-case privacy guarantee for ML algorithms, which would have broad application prospects in many aspects, such as being used for practitioners to estimate the actual risk they incur in practice.\n\nWeaknesses:\n1. We suggest adding deep learning methods as the base models to the experiment, like DP-SGD, mentioned in line 34. Applying the proposed methods to deep learning models makes the paper more persuasive and valuable.\n\n2. In Figure 2 (c), some results of OURS(ML-Audit) do not excel Swap-X baseline, and Swap-X performs similarly to OURS(ML-Audit) in output-perturbed logistic regression on linearly separable datasets such as iris. It will be better to give a corresponding explanation for such a case.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "4Il9GUgSP73", "reviewer": "Reviewer_K5aD", "summary": "The paper considers the problem of auditing machine learning models. They propose strategies to improve upon existing machine learning auditing approaches, and design poisoning attacks to audit a wider range of model types than have been previously considered in the auditing literature, such as Naive Bayes, logistic regression, and random forests. They show that their approach can be used both for bug finding and for understanding properties of a dataset which impact empirical privacy.", "questions": "Is the influence metric correlated with the gap between theoretical and empirical epsilon across datasets?\n\nDid you ever experiment with baselines besides flipping and ClipBKD, something like standard backdoor attacks or the Nasr et al strategy?", "limitations": "This is fine.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nUsing confidence intervals for the ratio of binomials is a nice improvement.\n\nThe paper designs model-specific poisoning attacks that work quite well. DP-SGD is not the only interesting DP learning algorithm, so this is a well motivated problem.\n\nI liked the discussion of the impact of k.\n\nWeaknesses:\n\nThe paper overclaims on the novelty of the framework. It is not very different from existing techniques. The main differences are the combination of DP-Sniper auditing with ML poisoning as proposed by Jagielski et al and Nasr et al, as well as the use of binomial ratio confidence intervals. The main contribution of the paper seems to be in the instantiations of the framework rather than the framework itself.\n\nStrange choices of baselines. In the Jagielski et al. paper, ClipBKD is designed specifically for DP-SGD. It's a stretch to use it to audit objective perturbation, let alone Naive Bayes. That paper also used backdoor poisoning attacks. Nasr et al. have an optimization procedure that could be used to get model-adapted poisoning attacks. These are all appropriate baselines. What would be even cooler (and probably a contribution in its own) is taking advantage of the large literature on poisoning attacks (including specifically on objective perturbation and output perturbation for logistic regression [r1], nonprivate Naive bayes [r2]). These are generally not designed for auditing, so an auditing-specific poisoning strategy should still outperform them.\n\nThe motivation for dataset-specific privacy does not seem to be supported by the experiments. The authors want to investigate the idea that \"achievable privacy is dataset-dependent\", but the investigation focuses on a comparison between influence-based poisoning and ClipBKD. The achievable privacy is better measured by something like the maximum epsilon obtained over all attacks, not a comparison between attacks. What might help better make this point is investigating whether the \"Ours\" influence metric the authors consider in Figure 3b is correlated with the empirical epsilon lower bound, when analyzed across datasets (rather than across attacks on the same dataset). This might help give a cool metric to predict privacy risk before going through the auditing process.\n\n[r1] - https://www.ijcai.org/proceedings/2019/0657.pdf\n[r2] - https://people.eecs.berkeley.edu/~adj/publications/paper-files/SecML-MLJ2010.pdf", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept