Overfitting, robustness, and malicious algorithms: A study of potential causes of privacy risk in machine learning

1.1.Membership inference

Training data membership inference attacks aim to determine whether a given data point was present in the training data used to build a model. Although this may not at first seem to pose a serious privacy risk, the threat is clear in settings such as health analytics where the distinction between case and control groups could reveal an individual’s sensitive conditions. This type of attack has been extensively studied in the adjacent area of genomics [28,50], and more recently in the context of machine learning [39,54].

Our analysis shows a clear dependence of membership advantage on generalization error (Section 3.2), and in some cases the relationship is directly proportional (Theorem 2). Our experiments on real data confirm that this connection matters in practice (Section 7.2), even for models that do not conform to the formal assumptions of our analysis. In one set of experiments, we apply a particularly straightforward attack to deep convolutional neural networks (CNNs) using several datasets examined in prior work on membership inference. Despite requiring significantly less computation and adversarial background knowledge, our attack performs almost as well as a recently published attack [54].

Our results illustrate that overfitting is a sufficient condition for membership vulnerability in popular machine learning algorithms. However, it is not a necessary condition (Theorem 4). In fact, under certain assumptions that are commonly satisfied in practice, we show that a stable training algorithm (i.e., one that does not overfit) can be subverted so that the resulting model is nearly as stable but reveals exact membership information through its black-box behavior. This attack is suggestive of algorithm substitution attacks from cryptography [7] and makes adversarial assumptions similar to those of other recent privacy attacks [57]. We implement this construction to train deep CNNs (Section 7.4) and observe that, regardless of the model’s generalization behavior, the attacker can recover membership information while incurring very little penalty to predictive accuracy.

1.2.Attribute inference

In an attribute inference attack, the adversary uses a machine learning model and incomplete information about a data point to infer the missing information for that point. For example, in work by Fredrikson et al. [23], the adversary is given partial information about an individual’s medical record and attempts to infer the individual’s genotype by using a model trained on similar medical records.

We formally characterize the advantage of an attribute inference adversary as its ability to infer a target feature given an incomplete point from the training data, relative to its ability to do so for points from the general population (Section 4). This approach is distinct from the way that attribute advantage has largely been characterized in prior work [22,23,66], which prioritized empirically measuring advantage relative to a simulator who is not given access to the model. We offer an alternative definition of attribute advantage (Definition 6) that corresponds to this characterization and argue that it does not isolate the risk that the model poses specifically to individuals in the training data.

Our formal analysis shows that attribute inference, like membership inference, is indeed sensitive to overfitting. However, we find that influence must be factored in as well to understand when overfitting will lead to privacy risk (Section 4.1). Interestingly, the risk to individuals in the training data is greatest when these two factors are “in balance”. Regardless of how large the generalization error becomes, the attacker’s ability to learn more about the training data than the general population vanishes as influence increases.

1.3.Connection between membership and attribute inference

The two types of attack that we examine are deeply related. We build reductions between the two by assuming oracle access to either type of adversary. Then, we characterize each reduction’s advantage in terms of the oracle’s assumed advantage. Our results suggest that attribute inference may be “harder” than membership inference: attribute advantage implies membership advantage (Theorem 6), but there is currently no similar result in the opposite direction.

Our reductions are not merely of theoretical interest. Rather, they function as practical attacks as well. We implemented a reduction for attribute inference and evaluated it on real data (Section 7.3). Our results show that when generalization error is high, the reduction adversary can outperform an attribute inference attack given in [23] by a significant margin.

1.4.Membership inference on robust models

Beyond privacy, another well-known type of attack in the context of machine learning seeks to induce errant predictions from the model. Prior work on these attacks [26,46,47,59] has shown that it is often possible to make small, visually imperceptible changes to image features such that a deep convolutional neural network (CNN) classifier is “tricked” into labeling the resulting image as something completely different from the true label, and in many cases to do so arbitrarily at the attacker’s discretion. This has motivated a growing body of subsequent work on methods for training robust models [13,40,65], especially for the case of CNNs, which resist these attacks by remaining insensitive to norm-bounded input perturbations.

Intuitively, robust training methods produce models with decision boundaries that are located suitably far from each of the training points. If the distances between decision boundaries and training points are often minimal, and the model fits the training points closely in at least one direction, then the model will be less likely to make comparably robust predictions on test points. We observe that an attacker might be able to evaluate the model’s level of robustness on a given input to draw inferences about membership.

Building from this intuition, we argue both analytically and experimentally that robustness can be another source of membership advantage. Applying a general result (Theorem 2) that leverages classification error for membership inference, we show that an adversary can use a model’s robust generalization error, which is a measure of overfitting that takes robustness into account, to gain membership advantage (Section 6). Our experimental results show that when adversarial training with projected gradient descent [40] is used to achieve robustness, the robust generalization error is often greater than the standard generalization error (Section 7.5), thus indicating that attacks on robust models can be more effective than those based on overfitting alone. We then present an attack that operationalizes the above intuition in greater detail by estimating the distance to the nearest decision boundary, and show experimentally that this can leak significantly more information than the robust generalization error alone. In particular, this attack predicts membership with up to 90% accuracy on a benchmark image classification dataset.

These results suggest that in some cases, robustness and training set privacy may conflict with each other, so that resistance to one type of attack may make a model more vulnerable to a different type of attack. Finding a way to resolve this tension is an important direction for future work.

1.5.Summary

This article explores the factors that contribute to privacy risk in machine learning models. We present new formalizations of membership inference attacks (Section 3) and attribute inference attacks (Section 4), which allow us to analyze the privacy risk that black-box variants of these attacks pose to individuals in the training data. We give analytic quantities for the attacker’s performance in terms of generalization error and influence and conclude that certain configurations imply privacy risk. We then study the underlying connections between membership and attribute inference attacks (Section 5), finding surprising relationships that give insight into the relative difficulty of the attacks and lead to new attacks that work well on real data. We also show that overfitting is not the only source of privacy risk by constructing adversaries that leverage a malicious training algorithm (Section 3.4) or robustness (Section 6) to infer membership information. Finally, we present our empirical results (Section 7), which mostly align with the analytical results in Sections 3–6 and show that our attacks are effective on real-world datasets.

2.1.Notation and preliminaries

Let z=(x,y)∈X×Y be a data point, where x represents a set of features or attributes and y a response. In a typical machine learning setting, and thus throughout this article, it is assumed that the features x are given as input to the model, and the response y is returned. Let D represent a distribution of data points, and let S∼Dn be an ordered list of n points, which we will refer to as a dataset, training set, or training data interchangeably, sampled i.i.d. from D. We will frequently make use of the following methods of sampling a data point z:

Unless stated otherwise, our results pertain to the standard machine learning setting, wherein a model AS is obtained by applying a machine learning algorithm A to a dataset S. Models reside in the set X→Y and are assumed to approximately minimize the expected value of a loss function ℓ over S. If z=(x,y), the loss function ℓ(AS,z) measures how much AS(x) differs from y. When the response domain is discrete, it is common to use the 0–1 loss function, which satisfies ℓ(AS,z)=0 if y=AS(x) and ℓ(AS,z)=1 otherwise. When the response is continuous, we use the squared-error loss ℓ(AS,z)=(y−AS(x))2. Additionally, it is common for many types of models to assume that y is normally distributed in some way. For example, linear regression assumes that y is normally distributed given x [41]. To analyze these cases, we use the error function erf, which is defined in Equation (1).

2.2.Stability and generalization

An algorithm is stable if a small change to its input causes limited change in its output. In the context of machine learning, the algorithm in question is typically a training algorithm A, and the “small change” corresponds to the replacement of a single data point in S. This is made precise in Definition 1.

Stability is closely related to the popular notion of differential privacy [17] given in Definition 2.

When a learning algorithm is not stable, the models that it produces might overfit to the training data. Overfitting is characterized by large generalization error, which is defined below.

In other words, AS overfits if its expected loss on samples drawn from D is much greater than its expected loss on its training set. For brevity, when n, D, and ℓ are unambiguous from the context, we will write Rgen(A) instead.

It is important to note that Definition 3 describes the average generalization error over all training sets, as contrasted with another common definition of generalization error Ez∼D[ℓ(AS,z)]−1n∑z∈Sℓ(AS,z), which holds the training set fixed. The connection between average generalization and stability is formalized by Shalev-Shwartz et al. [53], who show that an algorithm’s ability to achieve a given generalization error (as a function of n) is equivalent to its ARO-stability rate.

3.1.Bounds from differential privacy

Our first result (Theorem 1) bounds the advantage of an adversary who attempts a membership attack on a differentially private model [17]. Differential privacy imposes strict limits on the degree to which any point in the training data can affect the outcome of a computation, and it is commonly understood that differential privacy will limit membership inference attacks. Thus it is not surprising that the advantage is limited by a function of ϵ.

Wu et al. [67, Section 3.2] present an algorithm that is differentially private as long as the loss function ℓ is strongly convex and Lipschitz. Moreover, they prove that the performance of the resulting model is close to the optimal. Combined with Theorem 1, this provides us with a bound on membership advantage when the loss function is strongly convex and Lipschitz.

However, this and other methods of achieving differential privacy, and by extension a bound on membership advantage, may decrease the utility of the resulting model. In particular, Theorem 1 does not give us a meaningful bound unless ϵ<ln2, and the experimental results by Fredrikson et al. [23] suggest that such small values of ϵ can lower the accuracy of the model.

3.2.Membership attacks and generalization

In this section, we consider several membership attacks that make few, common assumptions about the model AS or the distribution D. Importantly, these assumptions are consistent with many natural learning techniques widely used in practice.

For each attack, we express the advantage of the attacker as a function of the extent of the overfitting, thereby showing that the generalization behavior of the model is a strong predictor for vulnerability to membership inference attacks. In Section 7.2, we demonstrate that these relationships often hold in practice on real data, even when the assumptions used in our analysis do not hold.

Bounded loss function. We begin with a straightforward attack that makes only one simple assumption: the loss function is bounded by some constant B. Then, with probability proportional to the model’s loss at the query point z, the adversary predicts that z is not in the training set. The attack is formalized in Adversary 1.

Theorem 2 states that the membership advantage of this approach is proportional to the generalization error of A, showing that advantage and generalization error are closely related in many common learning settings. In particular, classification settings, where the 0–1 loss function is commonly used, B=1 yields membership advantage equal to the generalization error. Simply put, high generalization error necessarily results in privacy loss for classification models.

Gaussian error. Whenever the adversary knows the exact error distribution, it can simply compute which value of b is more likely given the error of the model on z. This adversary is described formally in Adversary 2. While it may seem far-fetched to assume that the adversary knows the exact error distribution, linear regression models implicitly assume that the error of the model is normally distributed. In addition, the standard errors σS, σD of the model on S and D, respectively, are often published with the model, giving the adversary full knowledge of the error distribution. We will describe in Section 3.3 how the adversary can proceed if it does not know one or both of these values.

In regression problems that use squared-error loss, the magnitude of the generalization error depends on the scale of the response y. For this reason, in the following we use the ratio σD/σS to measure generalization error. Theorem 3 characterizes the advantage of this adversary in the case of Gaussian error in terms of σD/σS. As one might expect, this advantage is 0 when σS=σD and approaches 1 as σD/σS→∞. The dotted line in Fig. 2(a) shows the graph of the advantage as a function of σD/σS.

3.3.Unknown standard error

In practice, models are often published with just one value of standard error, so the adversary often does not know how σD compares to σS. One solution to this issue is to assume that σS≈σD, i.e., that the model does not terribly overfit. Then, the threshold is set at |ϵ|=σS, which is the limit of the right-hand side of Equation (4) as σD approaches σS. Then, the membership advantage is erf(1/2)−erf(σS/2σD). This expression is graphed in Fig. 2(b) as a function of σD/σS.

Alternatively, if the adversary knows which machine learning algorithm was used, it can repeatedly sample S∼Dn, train the model AS using the sampled S, and measure the error of the model to arrive at reasonably close approximations of σS and σD.

3.4.Malicious training algorithm

The results in the preceding sections show that overfitting is sufficient for membership advantage. However, models can leak information about the training set in other ways, and thus overfitting is not necessary for membership advantage. For example, the learning algorithm can produce models that simply output a lossless encoding of the training dataset. This example may seem unconvincing for several reasons: the leakage is obvious, and the “encoded” dataset may not function well as a model. In the rest of this section, we present a pair of colluding training algorithm and adversary that does not have the above issues but still allows the attacker to learn the training set almost perfectly. This is in the framework of an algorithm substitution attack (ASA) [7], where the target algorithm, which is implemented by closed-source software, is subverted to allow a colluding adversary to violate the privacy of the users of the algorithm. All the while, this subversion remains impossible to detect. Algorithm 1 and Adversary 3 represent a similar security threat for learning algorithms with bounded loss function. While the attack presented here is not impossible to detect, on points drawn from D, the black-box behavior of the subverted model is similar to that of an unsubverted model.

The main result is given in Theorem 4, which shows that any ARO-stable learning algorithm A, with a bounded loss function operating on a finite domain, can be modified into a vulnerable learning algorithm Ak, where k∈N is a parameter. Moreover, subject to our assumption from before that μ(n,D) is very small, the stability rate of the vulnerable model Ak is not far from that of A, and for each Ak there exists a membership adversary whose advantage is negligibly far (in k) from the maximum advantage possible on D. Simply put, it is often possible to find a suitably leaky version of an ARO-stable learning algorithm whose generalization behavior is close to that of the original.

The proof of Theorem 4 involves constructing a learning algorithm Ak that leaks precise membership information when queried in a particular way but is otherwise identical to A. Ak assumes that the adversary has knowledge of a secret key that is used to select pseudorandom functions that define the “special” queries used to extract membership information. In this way, the normal behavior of the model remains largely unchanged, making Ak approximately as stable as A, but the learning algorithm and adversary “collude” to leak information through the model. We require the features x to fully determine y to avoid collisions when the adversary queries the model, which would result in false positives. In practice, many learning problems satisfy this criterion. Algorithm 1 and Adversary 3 illustrate the key ideas in this construction informally.

Algorithm 1 will not work well in practice for many classes of models, as they may not have the capacity to store the membership information needed by the adversary while maintaining the ability to generalize. Interestingly, in Section 7.4 we empirically demonstrate that deep convolutional neural networks (CNNs) do in fact have this capacity and generalize perfectly well when trained in the manner of AC. As pointed out by Zhang et al. [69], because the number of parameters in deep CNNs often significantly exceeds the training set size, despite their remarkably good generalization error, deep CNNs may have the capacity to effectively “memorize” the dataset. Our results supplement their observations and suggest that this phenomenon may have severe implications for privacy.

Before we give the formal proof, we note a key difference between Algorithm 1 and the construction used in the proof. Whereas the model returned by Algorithm 1 belongs to the same class as those produced by A, in the formal proof the training algorithm can return an arbitrary model as long as its black-box behavior is suitable.

The formal study of ASAs was introduced by Bellare et al. [7], who considered attacks against symmetric encryption. Subsequently, attacks against other cryptographic primitives were studied as well [2,6,24]. The recent work of Song et al. [57] considers a similar setting, wherein a malicious machine learning provider supplies a closed-source training algorithm to users with private data. When the provider gets access to the resulting model, it can exploit the trapdoors introduced in the model to get information about the private training dataset. However, to the best of our knowledge, a formal treatment of ASAs against machine learning algorithms has not been given yet. We leave this line of research as future work, with Theorem 4 as a starting point.

4.1.Inversion, generalization, and influence

The case where φ simply removes the sensitive attribute t from the data point z=(v,t,y) such that φ(z)=(v,y) is known in the literature as model inversion [22,23,66,67].

In this section, we look at the model inversion attack of Fredrikson et al. [23] under the advantage given in Definition 5. We point out that this is a novel analysis, as this advantage is defined to reflect the extent to which an attribute inference attack reveals information about individuals in S. While prior work [22,23] has empirically evaluated attribute accuracy over corresponding training and test sets, our goal is to analyze the factors that lead to increased privacy risk specifically for members of the training data. To that end, we illustrate the relationship between advantage and generalization error as we did in the case of membership inference (Section 3.2). We also explore the role of feature influence, which in this case corresponds to the degree to which changes to a sensitive feature of x affects the value AS(x). In Section 7.3, we show that the formal relationships described here often extend to attacks on real data where formal assumptions may fail to hold.

The attack described by Fredrikson et al. [23] is intended for linear regression models and is thus subject to the Gaussian error assumption discussed in Section 3.2. In general, when the adversary can approximate the error distribution reasonably well, e.g., by assuming a Gaussian distribution whose standard deviation equals the published standard error value, it can gain advantage by trying all possible values of the sensitive attribute. We denote the adversary’s approximation of the error distribution by fA, and we assume that the target t=π(z) is drawn from a finite set of possible values t1,…,tm with known frequencies in D. We indicate the other features, which are known by the adversary, with the letter v (i.e., z=(x,y), x=(v,t), and φ(z)=(v,y)). The attack is shown in Adversary 4. For each ti, the adversary counterfactually assumes that t=ti and computes what the error of the model would be. It then uses this information to update the a priori marginal distribution of t and picks the value ti with the greatest likelihood.

When analyzing Adversary 4, we are clearly interested in the effect that generalization error will have on advantage. Given the results of Section 3.2, we can reasonably expect that large generalization error will lead to greater advantage. However, as pointed out by Wu et al. [66], the functional relationship between t and AS(v,t) may play a role as well. Working in the context of models as Boolean functions, Wu et al. formalized the relevant property as functional influence [44], which is the probability that changing t will cause AS(v,t) to change when v is sampled uniformly.

The attack considered here applies to linear regression models, and Boolean influence is not suitable for use in this setting. However, an analogous notion of influence that characterizes the magnitude of change to AS(v,t) is relevant to attribute inference. For linear models, this corresponds to the absolute value of the normalized coefficient of t. Throughout the rest of the article, we refer to this quantity as the influence of t without risk of confusion with the Boolean influence used in other contexts.

Binary variable with uniform prior. The first part of our analysis deals with the simplest case where m=2 with Prz∼D[t=t1]=Prz∼D[t=t2]. For a linear regression model, we have AS(v,t1)=AS(v,t2)+τ for some fixed τ, and without loss of generality we assume that τ⩾0. Theorem 5 relates the advantage of Adversary 4 to σS and σD as well as τ, which is a straightforward measure of influence in this setting.

Clearly, the advantage will be zero when there is no generalization error (σS=σD). Consider the other extreme case where σS→0 and σD→∞. When σS is very small, the adversary will always guess correctly because the influence of t overwhelms the effect of the error ϵ. On the other hand, when σD is very large, changes to t will be nearly imperceptible for “normal” values of τ, and the adversary is reduced to random guessing. Therefore, the maximum possible advantage with uniform prior is 1/2. As a model overfits more, σS decreases and σD tends to increase. If τ remains fixed, it is easy to see that the advantage increases monotonically under these circumstances.

Figure 1 shows the effect of changing τ as the ratio σD/σS remains fixed at several different constants. When τ=0, t does not have any effect on the output of the model, so the adversary does not gain anything from having access to the model and is reduced to random guessing. When τ is large, the adversary almost always guesses correctly regardless of the value of b since the influence of t drowns out the error noise. Thus, at both extremes the advantage approaches 0, and the adversary is able to gain advantage only when τ and σD/σS are in balance.

Fig. 1.

The advantage of Adversary 4 as a function of t’s influence τ. Here t is a uniformly distributed binary variable.

General case. Sometimes the uniform prior for t may not be realistic. For example, t may represent whether a patient has a rare disease. In this case, we weight the values of fA(ϵ(ti)) by the a priori probability Prz∼D[t=ti] before comparing which ti is the most likely. With uniform prior, we could simplify argmaxtifA(ϵ(ti)) to argminti|ϵ(ti)| regardless of the value of σ used for fA. On the other hand, the value of σ matters when we multiply by Pr[t=ti]. Because the adversary is not given b, it makes an assumption similar to that described in Section 3.2 and uses ϵ∼N(0,σS2).

Clearly σS=σD results in zero advantage. The maximum possible advantage is attained when σS→0 and σD→∞. Then, by similar reasoning as before, the adversary will always guess correctly when b=0 and is reduced to random guessing when b=1, resulting in an advantage of 1−1m.

In general, the advantage can be computed using Equation (5). We first figure out when the adversary outputs ti. When fA is a Gaussian, this is not computationally intensive as there is at most one decision boundary between any two values ti and tj. Then, we convert the decision boundaries into probabilities by using the error distributions ϵ∼N(0,σS2) and N(0,σD2), respectively.

5.1.From membership to attribute

We start with an adversary AM→A that uses an attribute oracle to accomplish membership inference. The attack, shown in Adversary 5, is straightforward: given a point z, the adversary queries the attribute oracle to obtain a prediction t of the target value π(z). If this prediction is correct, then the adversary concludes that z was in the training data.

Theorem 6 shows that the membership advantage of this reduction exactly corresponds to the attribute advantage of its oracle. In other words, the ability to effectively infer attributes of individuals in the training set implies the ability to infer membership in the training set as well. This suggests that attribute inference is at least as difficult as than membership inference.

5.2.From attribute to membership

We now consider reductions in the other direction, wherein the adversary is given φ(z) and must reconstruct the point z to query the membership oracle. To accomplish this, we assume that the adversary knows a deterministic reconstruction function φ−1 such that φ∘φ−1 is the identity function, i.e., for any value of φ(z) that the adversary may receive, there exists z′=φ−1(φ(z)) such that φ(z)=φ(z′). However, because φ is a lossy function, in general it does not hold that φ−1(φ(z))=z. Our adversary, described in Adversary 6, reconstructs the point z′, sets the attribute t of that point to value ti chosen uniformly at random, and outputs ti if the membership oracle says that the resulting point is in the dataset.