Privacy Risk in Machine Learning: Analyzing the Connection to Overfitting

1. 01What problem does this paper attempt to solve?

   The authors attempt to precisely characterize how overfitting and influence determine the privacy risk of membership inference and property inference.

   Core question: what exactly is the quantitative relationship between the two factors, overfitting (generalization error) and influence, and the privacy risk of machine learning models under membership inference and property inference attacks.

   • Problem setting: When machine learning is applied to sensitive data (such as health analytics), models may leak training data information through behavior (black-box) or structure (white-box); the authors state that previously only scattered anecdotal evidence suggested that overfitting and influence might play a role.
   • Shortcomings of existing methods: The authors state that there is already a large body of work on definitions such as differential privacy, and that differential privacy implies good generalization under several assumptions, but the precise connection between overfitting and the risk of different types of attacks remains unknown; previous advantage definitions for property inference (relative to a model-free simulator) cannot isolate the risk specific to the model's training data members.
   • Core observation: The authors hypothesize that overfitting is a sufficient condition for membership inference, that property inference additionally requires considering the influence of the target property; and they conjecture that overfitting may not be a necessary condition.
   • The paper proposes: new formal definitions of member advantage and property advantage (Definitions 4, 5); advantage analyses for several black-box attackers (parameterized by generalization error and influence); a colluding training algorithm (algorithm substitution attack); bidirectional reductions between membership and property inference; and experimental validation on real data.
   • Threat model:
     • Goal: determine whether a given point z is in the training set S (membership inference), or, given ϕ(z), infer the sensitive property π(z) (property inference).
     • Knowledge: the attacker knows the training set size n and the data distribution D; the threshold attacker additionally assumes knowledge of the error distribution or the average training loss.
     • Capability: black-box access to the model A_S (all attacks in this section assume black-box); in the colluding setting, the attacker shares a key with the training algorithm.
     • Victim system: a model trained by a standard training algorithm (linear regression, decision tree, CNN) on private data.

   Collapse this answer

2. 02What related research exists?

   Related work covers four threads: statistical summary privacy, theoretical connections between privacy and generalization, membership inference, and property inference.

   Privacy attacks on statistical summaries

   • Komarova et al. — study a partial-disclosure setting in which an attacker infers individuals' sensitive traits from statistical estimates combining public and private sources.
   • GWAS membership attacks (Homer et al., Sankararaman et al., etc.) — infer membership from statistics often published by genome-wide association studies; Calandrino et al. — temporal changes in collaborative-filtering recommendations can leak the inputs that caused the changes.
   • Linear reconstruction attacks (Dinur & Nissim, etc.) — reconstruct part of the input from linear statistics, later extended to nonlinear statistics; the authors note that these works share commonalities with this paper's goals, but this paper's results are specifically for the machine learning setting.

   Theoretical connections between privacy and generalization

   • Dwork et al. — prove that differentially private algorithms with suitable parameters generalize well with high probability; Bassily et al. — prove generalization for adaptive low-sensitivity queries under total variation stability; Wang et al. — prove that on-average KL privacy is equivalent to the generalization error defined in this paper for Gibbs-distributed data.
   • The authors state that these results provide evidence for a relationship between privacy and overfitting, whereas the attackers constructed in this paper directly exploit overfitting to obtain an advantage commensurate with its degree.

   Membership inference

   • Shokri et al. (2017) — a membership inference attack that trains an attack model based on shadow models, applied to machine-learning-as-a-service APIs; the authors note that it is unclear why their attack works, that the authors themselves hypothesize it is related to overfitting and the "diversity" of the training data, and that they find the relationship between generalization error and attack precision is not perfect.
   • Li et al. (2013) — propose a unified framework for distinguishing "positive" and "negative" membership privacy.

   Property inference

   • Fredrikson et al. (2014, 2015) — model inversion attacks on linear regression and on decision trees and neural networks; Wu et al. (2016) — formalize model inversion for Boolean function models and explore the connection between influence and advantage.
   • The authors note that the advantage definition in these works (the difference in accuracy with and without the model) cannot capture the leakage specific to the model's training data, and that Definition 5 in this paper is defined precisely for this purpose.

   Baselines and benchmarks: The direct comparison baseline for membership inference is Shokri et al.'s shadow model attack (Table 1), and the comparison target for property inference is Fredrikson et al.'s model inversion attack (Adversary 4); the experimental benchmarks are Eyedata, IWPC, Netflix, MNIST, CIFAR-10, and CIFAR-100.

   The authors position this paper as: making precise the connection between overfitting and privacy risk across multiple settings, and using the colluding construction to show that models that do not overfit can also leak membership information.

   Collapse this answer

3. 03How does the paper address this problem?

   The authors formalize the advantage of the two types of attacks, derive its relationship with generalization error and influence, and give a colluding construction and a bidirectional reduction.

   Overall approach: define experiments and advantage measures for membership inference and property inference respectively, express the advantage of several specific black-box attackers as a function of generalization error (Rgen or σD/σS) and influence (τ), then use reductions to connect the two types of attacks, and finally validate on real data.

   Formalization and advantage definitions

   • Membership experiment (Experiment 1): Sample S ∼ D^n, flip a coin b to decide whether the challenge point z comes from S or D; the attacker is given z, A_S, n, D and guesses b; membership advantage is defined as Adv^M = 2Pr[Exp^M = 1] − 1, equivalent to the difference between true and false positive rates.
   • Property experiment (Experiment 2): The attacker only receives ϕ(z) and must output π(z); property advantage (Definition 5) is defined as the difference in the probability of guessing correctly between b=0 and b=1; the authors state that this isolates the risk specific to the model's training data members.
   • Alternative definition (Definition 6): Replace the attacker when b=1 with a Bayes optimal simulator; the authors believe it cannot distinguish overfitting from learning general trends, and leave it for future work.

   Membership inference attackers

   • Adversary 1 (bounded loss): Outputs 1 with probability ℓ(A_S, z)/B; Theorem 2 gives the advantage as exactly Rgen(A)/B; under 0-1 loss B=1, and the advantage equals the generalization error.
   • Adversary 2 (threshold): When the conditional density of the error is known, outputs arg max_b f(ε|b); Theorem 3 gives, under Gaussian error, the advantage as the difference of two erf terms, which is 0 when σS=σD and approaches 1 as σD/σS→∞.
   • When σD is unknown: Set the threshold |ε|=σS; the advantage is erf(1/√2) − erf(σS/√2σD); or repeatedly sample training to estimate σS and σD.
   • Differential privacy upper bound: Theorem 1 proves that the membership advantage of an ε-differentially private algorithm is ≤ e^ε − 1.

   Colluding training algorithm (ASA)

   • Construction: Algorithm 1 uses keyed pseudorandom functions F_K, G_K to generate k supplementary points for each training point and add them to training; Adversary 3 queries whether A_S(F_Kj(x)) equals G_Kj(x) to determine membership.
   • Theorem 4: Any ARO-stable algorithm A with bounded loss and finite domain can be changed to A_k, with the stability rate increasing by at most knB2^(−d) + µ(n,D), while there exists an attacker with advantage up to 1 − µ(n,D) − 2^(−mk); the authors state that this shows overfitting is not a necessary condition for membership leakage.

   Property inference and influence

   • Adversary 4 (general property attack): For each candidate t_i, compute the counterfactual error ε(t_i), and output the t_i that maximizes Pr[t=t_i]·f_A(ε(t_i)).
   • Theorem 5 (binary uniform prior): The advantage is ½(erf(τ/2√2σS) − erf(τ/2√2σD)); the authors state that the advantage approaches 0 both when τ=0 and when τ is very large, that the risk is maximized when τ and σD/σS are "balanced", and that the maximum advantage is 1/2 under a uniform prior and 1 − 1/m in the general case.

   Reduction between the two types of attacks

   • Adversary 5 (property→membership): If the property oracle guesses π(z) correctly, judge it as a member; Theorem 6 gives Adv^M = Adv^A, which the authors believe suggests that property inference is at least as hard as membership inference.
   • Adversary 6 (membership→property, uniform): Randomly select t_i, reconstruct the point, and query the membership oracle; Theorem 7 gives Adv^A = (1/m)·Adv^{M*}.
   • Adversary 7 (membership→property, multi-query): Query the membership oracle for all t_i, and output the accepted value with the largest prior; this attacker is evaluated experimentally in Section 6.3.

   Collapse this answer

4. 04What experiments did the paper conduct?

   Validate the relationship between advantage and overfitting on linear/tree models and CNNs, and compare with Shokri et al. and direct property attacks.

   Experimental setup

   • Models evaluated: Ridge regression, decision tree (scikit-learn); a VGG-based CNN (Keras, Adam, λ=0.001, β1=0.5, β2=0.99, ε=10^−8, decay=5×10^−4, categorical cross-entropy), with size parameter s=2^i, 0≤i≤7.
   • Datasets: Eyedata (120×200 gene expression), IWPC (4819 patients, target properties VKORC1, CYP2C9), Netflix (ratings of 2416 users on 17,769 movies); for the CNN, MNIST (17,500 points taken), CIFAR-10, CIFAR-100 (15,000 points each taken), each split evenly into training/test sets.
   • Protocol: For linear/tree models, average over 100 random 75-25 splits; Remp and leave-one-out cross-validation Rcv approximate σS and σD, respectively; f_A for the property attack is Gaussian with mean 0 and standard deviation Remp.
   • Metrics: Membership advantage, property advantage (Definition 4, 5), precision, recall; the CNN membership attack uses the average training loss L_S as the threshold reference.
   • Baselines: The Shokri et al. shadow model attack (Table 1); property inference is compared with Adversary 4 (Fredrikson et al.'s model inversion).
   • Colluding experiments: k=3; F_K and G_K are instantiated with Python's built-in pseudorandom number generator seeded with the key.

   Main results

   Membership inference: comparison of the threshold attacker (Adversary 2) with Shokri et al. on CNNs (Table 1, with s set the same):

   Metric	This paper's threshold attack	Shokri et al.
   Precision (MNIST)	0.505	0.517
   Precision (CIFAR-10)	0.694	0.72–0.74
   Precision (CIFAR-100)	0.874	> 0.99
   Recall	> 0.99	> 0.99

   • The authors state that this paper's attack requires only one query and the average training loss, whereas the other requires training hundreds of shadow models, and that precision is only slightly lower.
   • Figure 2a/2b: When σS and σD are known, theory and experiment agree; when only σS is known, experiment outperforms the theoretical prediction, which the authors explain as the training set error distribution having a higher peak at zero (Figure 5, 6).
   • Figure 2c: On CNNs, the empirical and theoretical curves fit less well than for linear/tree models, but the authors state that the difference is not as large as would be expected under the assumption of non-Gaussian error.

   Property inference and reductions

   • What was measured: Property advantage of Adversary 4 on IWPC (t=VKORC1, CYP2C9) and Netflix, and the reduction attackers (Adversary 6, 7, with the threshold membership attacker as oracle).
   • Results: In Figure 3, on IWPC the property advantage increases with overfitting but is lower than the membership advantage; the multi-query reduction (Adversary 7) outperforms the uniform reduction, and the authors state that it also outperforms the direct property attack; on Netflix, all attacks fail to effectively infer whether a user has watched a movie, and the multi-query reduction is often slightly worse than the uniform reduction but still outperforms direct property inference.
   • Authors' interpretation: The authors state that at high generalization error, the reduction attackers can exceed Fredrikson et al.'s property attack by a large advantage; on Netflix, σD/σS and τ could not be controlled simultaneously, so the influence effect predicted by Theorem 5 could not be measured.

   Colluding membership inference

   • What was measured: Membership advantage and model accuracy cost of Algorithm 1 and Adversary 3 on the three CNN datasets.
   • Results: In Figure 4a, when s ≥ 16, the advantage on CIFAR-10 and MNIST is at least 0.9 (precision ≥ 0.9, recall ≥ 0.99), and the advantage on CIFAR-100 is 0.98 (precision ≥ 0.99, recall ≥ 0.99); the subverted model's accuracy drops by only 0.014 (MNIST), 0.047 (CIFAR-10), 0.031 (CIFAR-100).
   • Authors' interpretation: In Figure 4b, MNIST generalization error is < 0.02 (s ≥ 32) while CIFAR-100 is ≥ 0.8 (s ≥ 32), yet the membership advantage is almost the same; the authors state that this shows good generalization does not rule out membership leakage; the advantage rises with size around s ≈ 16 and then remains basically unchanged, which the authors believe indicates that model capacity exceeding some point is a necessary factor for the attack to succeed.

   Other ablations and analyses

   • Error distribution checks: Figure 5 (Netflix, Ridge λ=5, Remp=0.2774, Rcv=0.8884) and Figure 6 (IWPC, depth-15 decision tree, Remp=0.3899, Rcv=0.9507) show that the training error distribution has a higher peak at zero than Gaussian; in Figure 6 the zero-error bar exceeds the vertical axis by about 10 times.
   • Network size: s=2^i (0≤i≤7); the authors state that larger i does not give qualitatively different results.
   • Number of keys: the colluding experiments fix k=3; the paper does not report experiments with other values of k.

   Collapse this answer

5. 05What are some points that can be further explored?

   The authors list directions such as the ASA formalization, an alternative advantage definition, and stable adversaries; the experiments cover three types of models and six datasets.

   Limitations and future directions noted by the authors

   • Full exploration of Definition 6: The authors state that the alternative property-advantage definition cannot distinguish overfitting from learning general trends, and that a fuller exploration is left for future work (Section 4).
   • Further study of ASA: The authors state that no formal treatment of the algorithm substitution attack on machine learning algorithms yet exists, and that this is left for future work, with Theorem 4 as a starting point (Section 3.4); the Conclusion further raises the need to study whether models produced by malicious algorithms can be indistinguishable from normal models, and how to mitigate this.
   • Characterizing "stable adversaries": The authors state that characterizing realistic attackers who focus on as many people as possible rather than specific individuals may yield tighter advantage bounds or looser conditions on the learning rule (Section 8).
   • Directionality of the reductions: The authors state that property advantage implies member advantage (Theorem 6), but that no analogous result currently exists in the reverse direction (Section 1); analyzing the connection between the two types of attack using Definition 6 is also a future direction (Section 5).

   Scope of the experiments

   • The models tested are Ridge regression, decision tree, and a VGG-style CNN, three types in total (Section 6.1).
   • The membership inference experiments cover Eyedata, IWPC, Netflix, MNIST, CIFAR-10, and CIFAR-100; the property inference experiments are conducted only on IWPC and Netflix (Sections 6.2, 6.3).
   • For linear/tree models, each configuration is repeated 100 times with random 75-25 splits; the error distribution histograms are aggregated over 1000 splits (Section 6.1.1, Figure 5).
   • The CNN experiments control the generalization error via a scale parameter s=2^i (0≤i≤7); the colluding experiments fix k=3 (Sections 6.1.2, 6.4).
   • The paper does not report the number of repetitions for the CNN membership inference experiments, nor does it report experiments on Netflix that simultaneously control σD/σS and τ (Section 6.3 states this could not be done).

   Collapse this answer

6. 06Summarize the main content of the paper

   The authors give advantage definitions for two types of inference attacks, state that overfitting is a sufficient but not necessary condition, and that influence and overfitting jointly determine property inference risk.

   A formal and empirical study of the causes of machine learning privacy risk, focusing on two factors: overfitting and influence.

   • Problem: The relationship between the risk of a model leaking the membership or sensitive properties of training data and overfitting and influence lacks a precise characterization; the authors state that previously there was only anecdotal evidence.
   • Method: Define membership advantage and property advantage (Definition 4, 5), express the advantage of multiple black-box attackers as a function of generalization error and influence; propose a colluding training algorithm (ASA) and a bidirectional reduction between the two types of attacks.
   • Key theoretical results: Under bounded loss, membership advantage equals Rgen(A)/B (Theorem 2); under ε-differential privacy, advantage ≤ e^ε − 1 (Theorem 1); a stable algorithm can be replaced by a variant that leaks membership information and is almost equally stable (Theorem 4); property advantage is maximized when influence τ and σD/σS are balanced (Theorem 5); property advantage implies membership advantage (Theorem 6).
   • Main experimental results: The threshold membership attack on CIFAR-100 achieves precision 0.874 and recall > 0.99, close to Shokri et al.'s > 0.99, but requires only one query (Table 1); the colluding attack achieves advantage ≥ 0.98 when s ≥ 16 (CIFAR-100), with accuracy dropping by only 0.031, and shows no visible relationship with generalization error (Figure 4); on IWPC, the multi-query reduction outperforms the direct property attack, and on Netflix all property attacks are ineffective (Figure 3).
   • Authors' conclusion: Overfitting is a sufficient but not necessary condition for membership and property inference risk; property inference must also consider the influence of the target property; the two types of attacks have a deep connection, and property inference may be harder.
   • Implications (in the authors' voice): The authors believe that good generalization does not guarantee privacy, that differential privacy can bound membership advantage, and that future work needs to study the indistinguishability and mitigation of ASA, as well as more realistic attacker models.

   Collapse this answer

Related papers