A Bayesian Approach to Membership Inference for Statistical Release

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

A Bayesian Approach to Membership Inference for Statistical Release

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

cryptography, security, privacy, cybersecurity

A Bayesian Approach to Membership Inference for Statistical Release Lisa Oakley1, 2 , Sam Stites1 , Cameron Moy1 , Steven Holtzen1 , Alina Oprea1 , and Marco Gaboardi3

arXiv:2605.30203v1 [cs.CR] 28 May 2026

Northeastern University, USA 2 Proof Trading, Inc, USA 3 Boston University, USA

Abstract The membership inference problem for publicly released statistics from a private dataset is wellstudied. When developing and formally analyzing attack strategies, however, the focus has been on attacks that model the population using only its marginals. In practice, these attacks can perform well on various populations, however most formal analysis is for populations that follow a product distribution. These strategies may fail to leverage useful information about the population that is important for understanding a realistic privacy threat. In this work, we explore the impact of providing an attacker with additional information about the attribute dependency structure of the population, motivated by examples where multiple parties may have access to similarly structured data, for example the US Census and the IRS. To model this scenario, we reframe the membership inference problem with respect to a population represented as a Bayesian network (BN). We develop a framework based on Bayesian decision-making which can incorporate prior information about the population to launch more effective, specialized attacks. To evaluate our framework, we introduce a specific attack instantiation which computes the Bayesian posterior using a probabilistic program, and prove its equivalence to an optimal variant of the likelihood ratio test attack for two populations with strong attribute dependency. We implement our program in the Roulette probabilistic programming language and show experimentally that it outperforms the likelihood ratio test and inner product attacks on five commonly used BNs, where the population dependency structure is too complex for the existing attacks to be manually adapted.

Introduction

Membership inference attacks for statistical release seek to determine whether a given record is in a private dataset based on publicly available statistics. Popular attacks for the membership inference problem for statistical release tend to rely on assumptions about the population from which the private data were sampled [1–4]. In particular, many well-known attacks such as the inner product and likelihood ratio test attacks use only the population marginals to compute their decisions. When the population follows a product distribution, there are theoretical guarantees on the effectiveness of these attacks, and using only the marginals as a proxy for the population allows for simple and efficient attacks. Even when the strong independence assumptions do not hold, these procedures can perform well on data with unknown or unavailable attribute dependency structure, however there is lacking theoretical investigation into why this is the case. In some cases, attacks that assume a product distribution can be manually adjusted to consider known structure of specific populations. For example, intentionally ignoring (clipping) equivalent attributes can correct for disproportionate signaling. While effective, there are limited cases with a known modification, and the process is hard to generalize. When analyzing the privacy of a system, it is important to understand the full capabilities of an attacker with some privileged information, rather than focusing only on the most convenient and efficient attacks. 1

In reality, it is rare to have a population with no dependency between attributes. For example, an individual’s income is dependent on their age and occupation, and their occupation is dependent on their age and location. Not only are there obvious dependencies in the attributes of their data, there exists a potentially complex, multi-layered structural relationship between these attributes. It is also common that a curious party may have access to information about this structural relationship between attributes of the population. For example, when the US census releases public statistics about its respondents, it aims to protect the privacy of the individuals from all other parties, including other governmental departments. Many other departments might have data drawn from the same population, for example the IRS also has a sample of demographic information like age, state, number of children, and income over residents of the US. In this case, the census would want to understand the extent to which the IRS could use such a sample to inform their attack. In another alarming case, in 2025 Columbia University experienced a data breach affecting the personal information including demographic information, financial aid information, academic history, and Social Security numbers of applicants dating back over a decade and totaling over 870,000 affected individuals [5]. An attacker in this case could use this database of personal information to learn the attribute dependence structure of Ivy League college applicants in the US each year. The attacker could use this learned structure to inform a privacy attack on released admissions statistics (such as commonly released aggregate GPA, demographic, and geographical statistics) from other Ivy League universities who were not subject to this particular data breach. This type of advanced attack is not captured by analysis that considers an attacker who is only using the dataset marginals as attack inputs. One way to bring structure into statistical domains is by defining a Bayesian model of the population and using Bayesian decision-making [6]. In this paper, we formalize this process for the membership inference problem to develop an attack evaluation framework that can incorporate the population’s attribute dependency without manual analysis. We choose to model the population as a Bayesian network (BN), which is a Bayesian model described as a directed, acyclic graph over random variables. BNs can flexibly describe many interesting distributions, and there are many methods for learning a BN from a sample dataset [7]. Our primary contribution is an attack evaluation framework based on Bayesian decision-making which can be updated with a model of the population as a BN to create a specialized attack on the private data, without manual adjustments. Informally, our attack is a statistical test which, for threshold value TB , the attacker guesses a target point y is in a given dataset D if P r(target is in dataset | observed quantities) > TB . 1 − P r(target is in dataset | observed quantities)

(1)

In later sections, we define a probabilistic program for computing the posterior where the observed quantities include the description of the population as a BN and sampling procedure, and prove that our Bayesian attack finds an optimal clipping of the likelihood ratio test attack for two populations with high attribute dependency. Additionally, we show experimentally that an implementation of our Bayesian attack in the state-of-the-art Roulette [8] probabilistic programming language is able to outperform the traditional attacks on private data generated by a set of well-known benchmarking BNs with complex attribute dependency structures that have no obvious clipping solution for the traditional attacks.

A Bayesian View of the Membership Inference Problem

The membership inference problem for statistical release can be described simply as: assuming an attacker has access to a statistic over a private dataset and some information about the population from which the private data was drawn, the attacker must determine whether a target data point was drawn

from the private data or from the population. Typical framing for this problem de-emphasizes potential population attribute dependency, often providing the attacker only the population marginals. We propose a reframing that provides the attacker more information about the population. In particular, we describe the population as a Bayesian network, and provide some auxiliary information to the attacker. In our formulation, we focus on the membership inference problem for distributions with binary (or one-hot-encoded discrete) attributes. This formulation can be immediately extended to populations with continuous attributes by discretizing (bucketing) the feature space, or by using a Bayesian network over continuous features.

2.1

The Membership Inference Problem for Statistical Release

The membership inference problem for statistical release can be described as: 1. Let population P : Ω → [0, 1] over Ω = {0, 1}d be a discrete data distribution, and let target label ℓ ∈ {IN, OUT}. 2. Private dataset D = {x(1) , . . . , x(n) } consists of n samples (records) drawn i.i.d. from P. P 3. The sample means x = n1 ni=1 x(i) of D are publicly released. 4. Attacker is given n, and some information aux(P) about the population. 5. Attacker is given target point y such that ( y ∼ U(D), y= y ∼ P,

if ℓ = IN if ℓ = OUT

(2)

with U(D), the uniform distribution over the records of D. 6. Attacker must decide whether ℓ is IN or OUT. This formulation does not assume the population has attribute independence. Threat models under this definition are instantiations of aux(P). We discuss some example threat models in Sec. 2.3. We (i) use boldface variables to indicate a vector, aj is the jth element of vector a, and xj represents the jth element of the ith record of database D.

2.2

Population as a Bayesian Network

Our formulation of the membership inference problem describes the population as a discrete distribution. To allow for rich graphical descriptions of the structure of the distribution, we use Bayesian networks to model this discrete distribution. There are other graphical structures, for example this causal graph of the German credit database [9], that could also be potential population models, but we focus on Bayesian networks here for their generality, availability of examples, and standardized format. A Bayesian Network (BN) is a directed, acyclic graph (DAG) where nodes are random variables and edges are dependencies. It is used to succinctly capture the structure of dependency of the random variables in a distribution, with each node containing a joint probability table over itself and its parents. The power of modeling a distribution as a BN comes from the ability to define the whole dependency structure of the ancestors of a random variable with respect to only its parents. We denote the BN which describes a population P as BN (P). For example, we consider a simple BN from Korb and Nicholson [10], as described in Fig. 1a, which models probabilities of cancer symptoms dependent on environmental factors. This BN consists of five 3

low

high

0.9

0.1

Pollution (P)

C S

high

FALSE

0.98

TRUE

0.02

0.6

0.4

FALSE 0.999

0.001

TRUE

0.3

neg

TRUE FALSE 0.3

0.7

FALSE TRUE

low

Smoking (S)

0.7

pos

C FALSE

0.8

0.2

TRUE

0.1

0.9

Cancer (C)

Xray (X)

Dyspnoea (D)

FALSE

TRUE

FALSE

0.7

0.3

TRUE

0.2

0.8

Cancer

Dyspnoea

Xray

FALSE

negative

TRUE

positive

FALSE

negative

FALSE

TRUE

negative

FALSE

negative

(a) Bayesian network example from [10]. Conditional probability values are modified for the clarity of this example.

(b) Sample from Cancer Bayesian network example with output nodes O = {C, X, D} and n = 5 samples.

Figure 1: Simple example of a BN (left), and a sample drawn from this BN (right). X1

TRUE

FALSE

1-pi

…

Figure 2: Binary product distribution as a Bayesian network where pi = µi represents the probability that Xi is true. binary random variables (nodes): Pollution (P), Smoking (S), Cancer (C), X-ray (X) and Dyspnoea (D). In this example, the probability of having cancer (C) is dependent on pollution (P) and smoking (S), and the probability that the patient has a positive x-ray (X) or shortness of breath (D) are dependent on their shared parent (C). 2.2.1

Describing a Product Distribution as a Bayesian Network

The typical membership inference problem (and existing attacks) assumes the population follows a product distribution. This is a special case of our formulation, with the Bayesian network described in Fig. 2. Therefore, our formulation is a generalization of the typical membership inference problem formulation. 2.2.2

Sampling a Private Dataset from a Bayesian Network

The membership inference problem is defined for private datasets of n records drawn i.i.d. from a population with d attributes. When describing the population as a Bayesian network, we define a set of output nodes, O, whose values correspond to these attributes. The output nodes are chosen based on the semantics of the Bayesian network as part of the definition of the population, and are consistent across attacks. In Fig. 1a, we can reasonably define the output nodes as {X, D}, meaning that the private dataset only contains information about the symptoms the patient is experiencing (d = 2), as {C, X, D} (d = 3) including the patient status, or as {P, S, C, X, D} (d = 5) the entire set of random variables. Fig. 1b is an example of a sampled private dataset with n = 5 records for O = {C, X, D}.

2.3

Attacker Information (Threat Models)

Now that we have defined the population P in terms of a Bayesian network, we can discuss how to instantiate the auxiliary information the attacker receives (aux(P)) to define different threat models. In particular, we explain the strong, weak, and weakest attacker threat models. In this paper, we will focus on the strong attacker scenario for our theoretical analysis. In Sec. 6, we provide experimental results for all three threat models. 2.3.1

Full Information (Strong Attacker)

The strongest attacker threat model in the case of a population modeled as a Bayesian network provides the full structure and joint probability tables of nodes in the Bayesian network. Formally, aux(P) = BN (P). This provides the attacker with the maximum amount of information about the Bayesian network. 2.3.2

Public Auxiliary Dataset and Structure (Weak Attacker)

In the case of the weak attacker threat model, the attacker has access to only the structure of the Bayesian network (i.e., nodes and edges), but not to the joint probability tables of each node. Additionally, this attacker has access to a public auxiliary dataset drawn from the same population as the private dataset. The attacker can use state-of-the-art methods to learn the joint probability tables of the Bayesian network to get an approximation of the true population [7]. The attacker can then use this approximate Bayesian network to implement the same attack as the strong attacker. 2.3.3

Auxiliary Dataset and No Structure (Weakest Attacker)

The weakest attacker gets only the public auxiliary dataset drawn from the same distribution of the private dataset. This attacker will have to learn both the structure of the Bayesian network, and the joint probability tables. Learning the structure of the Bayesian network is a harder problem than just learning the joint probabilities, but there are methods that exist to do this type of learning as well [11].

2.4

Measuring Attack Utility

In our experimental evaluation, we evaluate the utility of each attack with respect to its Receiver Operating Characteristic (ROC) curve, and specifically the area under this curve (AUC). The ROC curve is a plot of the true positive rate (TPR), when attacker guesses the target is in the dataset in the case where ℓ = IN, over the false positive rate (FPR), when attacker guesses the target is in the dataset in the case where ℓ = OUT. Intuitively, high AUC means that a target point drawn from the private database will have a higher probability of being labelled IN than a target point drawn directly from the population. An AUC of 1 means the attacker correctly classifies all target points. Therefore, the mean AUC over various private databases drawn from the same population is a good metric for determining attack utility for specific populations or Bayesian networks.

Population Marginal Attacks under Attribute Dependence

Before introducing our Bayesian approach, we highlight the limitations of existing attacks for membership inference on statistical release in our context. We categorize the likelihood ratio test and inner product attacks under the umbrella of “population marginal attacks,” referring to their reliance on

TRUE FALSE p1

1-p1

TRUE

FALSE

1-pi

…

right

TRUE

FALSE

0.5

pmid

1-pmid

Side (S)

left

Xmid

X⌊d/2⌋+1

…

TRUE FALSE

Xmid-1

Xmid+1

Xmid+2

…

TRUE

FALSE

X⌊d/2⌋+1

Side 1-pi

i ∈ [1,⌊d/2⌋+1]

Xi X⌊d/2⌋+1

TRUE FALSE

X⌊d/2⌋+2

TRUE

FALSE

X⌊d/2⌋+3

…

Side

TRUE FALSE

i ∈ [⌊d/2⌋+2,d]

left

right

1-pi

left

right

1-pi

TRUE FALSE

i ∈ [2,mid-1]

(a) BN for half repeated data. Here the output set O = {X1 , . . . , Xd }.

left

right

left

1-pi

right

i ∈ [mid+1,d]

(b) BN for left/right repeated data for even n. We set mid = ⌊ d2 ⌋ + 1 and O = {X1 , . . . , Xd }.

Figure 3: Toy Bayesian networks with strong attribute dependencies. the population marginals (or a proxy thereof) as their population model. We demonstrate how these attacks can fail under strong population attribute dependence.

3.1

Likelihood Ratio Test Attack with a Product Assumption

The likelihood ratio test attack [1, 2] uses hypothesis testing with H0 (null): y was sampled from the population (i.e. y is OUT) and H1 : y was chosen from D (i.e. y is IN) to decide whether a sample is in or out of the dataset. In particular, it finds the likelihood ratio Λ=

Pry′ ∼U (D) (y′ = y) , Pry′ ∼P (y′ = y)

(3)

and chooses threshold TC to makes the decision: attacker guesses ℓ = IN ⇐⇒ Λ > TC . By the Neyman-Pearson Lemma, this is the optimal statistical test for H0 when the likelihoods are computed exactly. However, in implementation, an approximate ratio is often computed using only the population marginals (assuming attribute independence): Qd j=1 {if yj = 1 then xj else 1 − xj } Λ = Qd . (4) j=1 {if yj = 1 then µj else 1 − µj }

3.2

Inner Product Attack

Another popular attack, the inner product attack [3], computes how inclusion of the target point changes the released statistic to make the decision: attacker guesses ℓ = IN ⇐⇒ ⟨x − µ, y⟩ > TIP where TIP is some threshold, x are the sample/dataset means, µ are the population marginals, y is the target point and ⟨a, b⟩ is the inner product of vectors a and b. This test is succinct, but also limits population evidence to solely the population marginals.

3.3

Performance under Strong Attribute Dependence

Though the likelihood ratio test attack is optimal on product-distributed populations, and the likelihood ratio test and inner product attacks both boast strong performance with respect to certain 6

metrics [1–4], there are simple attribute dependency structures on which they struggle. In two such cases, the dependency structure of the population is simple enough that there is a clipping which neutralizes the effects of this dependency. However, in many cases the attribute dependency structure is too complicated for simple population-specific fixes. We describe these two cases and their associated clippings in the following sections. 3.3.1

Half Repeated Population

In the half repeated population (described in Fig. 3a), the first half of the attributes are independent, but the other half are repeated. Intuitively, population marginal attacks amplify the signal of the (⌊d/2⌋ + 1)th attribute, overwhelming the meaningful information in the first half of the attributes. The population marginal attackers can correct for this by observing the simple dependency and clipping the repeated attributes. Formally, the likelihood ratio test attacker computes Q⌊d/2⌋+1 {if yj = 1 then xj else 1 − xj } j=1 Λhalf = Q⌊d/2⌋+1 , (5) if yj = 1 then µj else 1 − µj j=1 and the inner product attacker computes the inner product for the first (⌊d/2⌋ + 1) attributes for the half repeated population. 3.3.2

Left/Right (l/r) Repeated Population

In the slightly more complicated left/right (l/r) repeated population (described in Fig. 3b), half of the attributes are again repeated, but we introduce an additional coin flip to determine which side of the attributes are independent. The attacker can still correct for signal amplification here by clipping repeated attributes, however they must first determine the correlated side from the released statistics. Formally the likelihood ratio test attacker computes for side = right Qmid j=1 {if yj = 1 then xj else 1 − xj } Λmid,right = Qmid (6) if y = 1 then µ else 1 − µ j j j j=1 and for side = lef t Qd

j=mid−1 {if yj = 1 then xj else 1 − xj }

Λmid,lef t = Qd

j=mid−1

if yj = 1 then µj else 1 − µj

(7)

for the l/r repeated population. Choosing the repeated side incorrectly causes this attack to have worse performance than ignoring the repetition altogether. In Fig. 4, we demonstrate the impact of attribute correlation on the original and clipped attacks. 3.3.3

More Complicated Dependency Structure

In populations with only independent or repeated attributes and simple structure, clipping is effective for recovering performance of population marginal attacks. As the structure gets even slightly more complicated, however, fixes become less obvious. Consider a population where k random attributes are chosen to take the same value. How does the attacker decide which attributes to ignore? For the Cancer example from Sec. 2, any clipping would remove useful signal. In the next section, we describe our Bayesian decision-making attack, which is defined generally for any population expressed as a Bayesian network, and demonstrate its strength at incorporating attribute dependency structure without manual adjustments. 7

ROC Curves n=50, d=500

1.0

True Positive Rate

0.8 0.6 0.4 likelihood (AUC = 0.62) inner product (AUC = 0.62) likelihood half (AUC = 0.40) inner product half (AUC = 0.40) likelihood flip half (AUC = 0.90) inner product flip half (AUC = 0.90)

0.2 0.0 0.0

0.2

0.4 0.6 False Positive Rate

0.8

1.0

Figure 4: An example of ROC curves for population marginal attacks on left/right repeated populations (illustrated in Fig 3b). The basic attacks (likelihood, inner product) perform poorly on data with this correlation structure. When the attacker knows which side is correlated (likelihood half, inner product half), they are able to improve the attack performance significantly by clipping repeated attributes. When the attacker guesses the correlated side incorrectly (likelihood flip half, inner product flip half), they perform worse than a coin flip because they clip the useful information and leave only the repeated attributes.

Our Bayesian Attack Framework

Our proposed attack framework is based on known Bayesian decision-making procedures [6]. In this case, we are trying to estimate the probability that ℓ = IN, which we will represent using the parameter ℓIN . We compute the posterior using auxiliary information given to the attacker, including the Bayesian network of the population, the dataset marginals, and the target point. More specifically, though still informally, we compute a Bayesian decision ratio R=

P r(ℓIN | BN (P), x, y) . 1 − P r(ℓIN | BN (P), x, y)

(8)

Our attack procedure for some thresholding value, TB , is therefore attacker guesses ℓ = IN ⇐⇒ R > TB .

(9)

In the case of the weak and weakest attack models as described in Sec. 2.3, the attacker must first approximate this Bayesian network from a proxy dataset drawn from the population.

4.1

Defining the Posterior as a Program

The quantity P r(ℓIN | BN (P), x, y) represents the probability that ℓ = IN, conditioned on the marginals, x, being equivalent to the marginals of a dataset where one arbitrary record is the target point y, and the other n − 1 records are sampled i.i.d. from the population. The denominator of eqn. (8) is the probability that ℓ = IN, given the marginals x are equal to those of a dataset where all n are drawn i.i.d. from the population (without assuming the target is in the data). We formally define this posterior as a probabilistic program. We define networkBN (P) , a program that models the population Bayesian network BN (P). In Appendix C, we provide an example of the encoded Cancer Bayesian network from Fig. 1a, written in the Roulette probabilistic programming 8

language (PPL). We also assume we have two primitives: f lip(p), which represents a Bernoulli distribution with parameter p, and observe(·), a standard PPL construct that calculates a conditional probability. Concretely, for the program θ ← f lip(1/2); observe(ϕ1 ) . . . observe(ϕn ); return θ, the final output will be P r(θ | ϕ1 . . . ϕn ). Here, θ is initialized to the prior f lip(1/2), and the observe(·) statements condition the output. The semantics of the PPL handles computing the posterior. The process of computing the posterior described by a probabilistic program is defined in the literature as probabilistic inference and is generally intractable [12]. Similarly to SAT solving, there are techniques to solve these problems exactly and efficiently in some cases using Bayesian methods. For example, in Roulette, posterior inference is performed by computing the normalizing constant exactly via knowledge compilation. Importantly, this does not involve any sampling and instead exactly computes the posterior. PPLs that perform approximate inference, say using Markov-chain Monte Carlo, approximate the posterior. The surface syntax using observe(·), however, remains the same. The probabilistic program to compute our desired posterior is defined in Algorithm 1 and works as follows. On line (2), we initialize the prior ℓIN as a fair coin flip. On line (4), we initialize n data records to be independent instances of the Bayesian network for the population. On lines (6) and (8) we condition on the sums of the attributes of the instances of the Bayesian networks to be equal to the given marginals of the private dataset. On line (6), we choose an arbitrary record to be the target interval if ℓIN . In this way, we indicate that the target point is in the private dataset. On line (9) we return the posterior distribution, P r(ℓIN | BN (P), x, y), as desired. Algorithm 1 Compute Posterior P r(ℓIN | BN (P), x, y) Require: Bayesian network BN (P), marginals x of private dataset, target point y procedure (BN (P), x, y) ℓIN ← f lip(0.5) ▷ initialize prior for i in [n] do x(i) ← networkBN (P) ▷ set networks if ℓIN then P (i) = x · n) observe(y + n−1 i=1 x else P observe( ni=1 x(i) = x · n)

▷ one record is y, the rest from P ▷ all records from P

return ℓIN

▷ return posterior

Correctness of the Bayesian Framework

The likelihood ratio test (LRT) attack with a product assumption from Sect. 3.1 is the strongest statistical test for product-distributed populations by the Neyman-Pearson lemma [1, 2, 4]. Simple clippings preserve optimality for half and l/r repeated populations. We present three main results showing our proposed Bayesian attack is equivalent to the (clipped) LRT attack on these populations in the case of the strong threat model (using two lemmas from Appendix B). The key takeaway here is that, while we had to define bespoke versions of the population marginal attacks to adapt to different attribute dependency, the Bayesian approach is more modular. There, the only change between attacks is defining the network structure to match that of the Bayesian network that describes the population. This means that the Bayesian framework is far more adaptive than the traditional attacks, and does not require manual modification.

BN (d)

Attack

AUC

Std.

BN (d)

Attack

AUC

Std.

half rep. (25) half rep. (25) half rep. (25) cancer [10] (10) cancer [10] (10) cancer [10] (10) quake [13] (10) quake [13] (10) quake [13] (10)

Bayes LRT IP Bayes LRT IP Bayes LRT IP

0.743 0.696 0.683 0.744 0.710 0.688 0.594 0.534 0.533

0.103 0.107 0.101 0.106 0.111 0.111 0.082 0.100 0.101

asia [14] (16) asia [14] (16) asia [14] (16) survey [15] (14) survey [15] (14) survey [15] (14) sachs [16] (15) sachs [16] (15) sachs [16] (15)

Bayes LRT IP Bayes LRT IP Bayes LRT IP

0.763 0.652 0.628 0.837 0.839 0.815 0.906 0.851 0.824

0.123 0.150 0.154 0.095 0.098 0.102 0.066 0.095 0.107

Table 1: Comparing our Bayesian (Bayes) attack AUC with the likelihood ratio test (LRT) and inner product (IP) attacks under the strong threat model. For the Sachs Bayesian network (BN), we define the output nodes to be the nodes in the longest path of the BN. In all other cases, the output set is the set of all nodes. Theorem 1 (Product Distributed Correctness). Assuming a population that follows a product distribution, the Bayesian framework using Algo. 1 to compute the posterior is equivalent to the likelihood ratio test attack from Sect. 3.1. Proof. Because the Bayesian attacker guesses ℓ = IN ⇐⇒ R > TB , and the Likelihood attacker guesses ℓ = IN ⇐⇒ Λ > TC , if we set TB = TC , the attacks are equivalent by Lemma 1 (R = Λ). Theorem 2 (Half Distributed Correctness). Assuming a population that follows a half repeated distribution described in Fig. 3a, the Bayesian framework using Algo. 1 to compute the posterior is equivalent to the clipped likelihood ratio test attack from Sec. 3.3.1. Proof. Because the Bayesian attacker guesses ℓ = IN ⇐⇒ R > TB , and the Likelihood attacker guesses ℓ = IN ⇐⇒ Λ > TC . If we set TB = TC , side = right, and mid = ⌊d/2⌋, by definition Λ = Λmid,side , and the attacks are equivalent by Lemma 2 (Rhalf = Λmid,side ). Theorem 3 (Left/Right Distributed Correctness). Assuming a population that follows a left/right repeated described in Fig. 3b, the Bayesian framework using Algo. 1 to compute the posterior is equivalent to the likelihood ratio test attack from Sect. 3.3.2. Proof. Because the Bayesian attacker guesses ℓ = IN ⇐⇒ R > TB , and the Likelihood attacker guesses ℓ = IN ⇐⇒ Λmid,side > TC , if we set TB = TC , the attacks are equivalent by Lemma 2 (R = Λmid,side ).

Evaluating the Bayesian Framework using Probabilistic Programming

The theoretical results from Sect. 5 indicate that the Bayesian approach finds the optimal clipping in some cases. Now, we present experimental results to demonstrate the utility of our method when there is no known fix for population marginal attacks. We evaluate our overall performance for the strong, weak, and weakest attacker threat models by comparing AUC to the likelihood ratio test (LRT) and inner product (IP) attacks on various Bayesian networks (BNs). We further vary the output nodes of one BN to understand attack performance over attribute connectedness and find that incorporating attribute structure into the attack becomes more valuable as the dimension and attribute dependency 10

BN (d)

Attack

AUC

Std.

BN (d)

Attack

AUC

Std.

asia [14] (16) asia [14] (16) asia [14] (16)

10 10 10

Bayes LRT IP

0.773 0.699 0.685

0.108 0.133 0.136

asia [14] (16) asia [14] (16) asia [14] (16)

10 10 10

Bayes LRT IP

0.770 0.689 0.674

0.108 0.137 0.139

asia [14] (16) asia [14] (16) asia [14] (16)

50 50 50

Bayes LRT IP

0.770 0.691 0.678

0.115 0.137 0.137

asia [14] (16) asia [14] (16) asia [14] (16)

50 50 50

Bayes LRT IP

0.768 0.685 0.669

0.110 0.133 0.136

asia [14] (16) asia [14] (16) asia [14] (16)

100 100 100

Bayes LRT IP

0.773 0.691 0.676

0.112 0.138 0.142

asia [14] (16) asia [14] (16) asia [14] (16)

100 100 100

Bayes LRT IP

0.768 0.683 0.669

0.110 0.132 0.135

(a) Public Auxiliary Dataset and Structure (Weak Attacker)

(b) Auxiliary Dataset and No Structure (Weakest Attacker)

Figure 5: Comparing our Bayesian (Bayes) attack AUC with the likelihood ratio test (LRT) and inner product (IP) attacks under the weak and weakest threat models on the Asia benchmarking Bayesian network with proxy datasets of m records. increases. We also investigate the impact of increasing the number of records for selected examples and provide scalability analysis of this solution on a variety of benchmark populations using the state-of-the-art Roulette probabilistic programming language for exact probabilistic inference. Our experiments are written in Python and run on a 16 core AMD EPYC with 64GB of RAM. We compute the exact Bayesian posterior (Alg. 1) using the Roulette probabilistic programming language [8]. We pull standard benchmarking BNs from the bnlearn repo [17] sampled using Pgmpy [18], and average AUCs over 40 trials (unique private datasets drawn i.i.d.), with 20 in and 20 out targets. We choose n < d to ensure enough signal for attack effectiveness.

6.1

Attack Performance on Selected Bayesian Networks (Strong Threat Model)

Our main objective is to understand how incorporating a Bayesian model of the population into the attack framework affects performance in practice. We showed theoretically in Sec. 5 that our Bayesian attack recovers the clipped LRT attack on the half and left/right repeated populations. In Table 1, we confirm experimentally that the Bayesian attack outperforms the standard LRT and IP attacks on the half repeated population for the strong threat model. We also want to look at more realistic populations with more complicated dependency structures that go beyond independent or repeated attributes. In our experiments, we consider a selection of standard benchmarking BNs, and compare the AUC of our Bayesian posterior attack to the population marginal attacks. We see in Table 1 that the Bayesian approach implemented in Roulette performs as well as or better than the population marginal attacks. Even with as little as 15 correlated parameters as in the Sachs BN, we see a mean attack AUC that is 5% higher than the LRT attack, and 8% higher than the IP attack.

6.2

Attack Performance Under Weaker Threat Models

To evaluate the weaker threat models, we modify the auxiliary information available to the attackers. For the weak threat model (public auxiliary dataset and structure), the attackers get access to the dependency structure of the population Bayesian network and a proxy dataset of m records, drawn from the population. To evaluate the Bayesian attacker, we use the Maximum Likelihood Estimator from the PGMPY package [18] to learn the joint probabilities of each node in the Bayesian network

PKC

Plcg

PKA Raf

PIP3 Jnk

P38

PIP2

Mek Erk Akt

(a) Structure of the Sachs BN [16].

Explanation

Output Nodes

Attack

AUC

Std.

right sub. right sub. right sub. leaf leaf leaf leaf + root leaf + root leaf + root leaf + parent leaf + parent leaf + parent long path (L) long path (L) long path (L) long path (R) long path (R) long path (R)

Plcg,PIP3,PIP2 Plcg,PIP3,PIP2 Plcg,PIP3,PIP2 Akt,Jnk,P38,PIP2 Akt,Jnk,P38,PIP2 Akt,Jnk,P38,PIP2 PKC,Akt,Jnk,P38,Plcg,PIP2 PKC,Akt,Jnk,P38,Plcg,PIP2 PKC,Akt,Jnk,P38,Plcg,PIP2 PKA,Akt,Jnk,P38,Plcg,PIP3 PKA,Akt,Jnk,P38,Plcg,PIP3 PKA,Akt,Jnk,P38,Plcg,PIP3 PKC,Raf,Mek,Erk,Akt PKC,Raf,Mek,Erk,Akt PKC,Raf,Mek,Erk,Akt PKC,PKA,Mek,Erk,Akt PKC,PKA,Mek,Erk,Akt PKC,PKA,Mek,Erk,Akt

9 9 9 12 12 12 18 18 18 18 18 18 15 15 15 15 15 15

Bayes LRT IP Bayes LRT IP Bayes LRT IP Bayes LRT IP Bayes LRT IP Bayes LRT IP

0.773 0.746 0.733 0.856 0.827 0.802 0.887 0.867 0.831 0.892 0.862 0.819 0.906 0.851 0.824 0.894 0.853 0.834

0.097 0.101 0.102 0.085 0.088 0.103 0.066 0.075 0.080 0.073 0.076 0.084 0.066 0.095 0.107 0.063 0.084 0.085

(b) Mean attack AUC for different output nodes for the Sachs BN.

Figure 6: Impact of different output nodes for the Sachs BN. Output sets with more shared evidence leads to improved Bayes performance and more pronounced differences between attacks. from the proxy dataset. This learned Bayesian network is then used as the input to Algorithm 1. For the weakest threat model (auxiliary dataset and no structure), the attackers only get access to a proxy dataset of m records drawn from the population. To evaluate the Bayesian attacker here, we use the PC algorithm from the PGMPY package [18] to learn both the structure and joint probabilities from the proxy data, and again use this as input to Algorithm 1. Because the population marginal attacks are fundamentally unable to leverage any information about the dependency structure of the features of the dataset, in both the weak and weakest attacker cases we approximate the dataset means by computing the marginals of the proxy dataset. In Fig. 5 we see the Bayesian attacker maintains a similar advantage under the weak threat model (approximating the joint probabilities), and in the weakest threat model (learning the structure of the Bayesian network and approximating the joint probabilities) for proxy datasets of size 10, 50, and 100. We include results for the Asia benchmarking Bayesian network [14] in Fig. 5, and provide results for additional benchmarking Bayesian networks in Appendix D. This is evidence that this attack remains effective for an attacker who has similarly distributed data to the private dataset.

6.3

Impact of Output Nodes on Attack Performance

The Bayesian approach provides better average AUC across the board, but we want to see how the number of output parameters and strength of their relationship impacts the performance gains provided by incorporating structural information into the attack. In Fig. 6, we study the Sachs BN more closely, selecting different interesting sets of output nodes under the strong threat model. For output sets that contain only the leaf (or leaf and root) nodes of the BN, there is little direct dependency between output nodes, and the Bayesian approach boasts modest improvements, about 2-3%. However, for

Mean AUC over number of records (Half Population)

Mean AUC over number of records (Asia Population)

Bayesian Likelihood Inner Product

0.95 0.90

0.8 Mean AUC

0.85 Mean AUC

Bayesian Likelihood Inner Product

0.9

0.80 0.75 0.70

0.7 0.6

0.65 0.60

0.5 4

7 8 9 Number of Records

3.0

(a) Half Repeated Population

3.5

4.0

4.5 5.0 5.5 Number of Records

6.0

6.5

7.0

(b) Asia Population (all nodes output)

Mean AUC over number of records (Sachs Population) Bayesian Likelihood Inner Product

0.95

Mean AUC

0.90 0.85 0.80 0.75 0.70 3.00

3.25

3.50

3.75 4.00 4.25 Number of Records

4.50

4.75

5.00

Figure 7: Comparing attack performance as n increases across different correlated populations. Values of n chosen in relationship to the dimension of the population. output sets with strongly connected nodes, such as the leftmost longest path or the leaves with their shared parents, we see a significant improvement when the attack considers a Bayesian model of the population. Here, we see that the Bayesian method beats the LRT attack by 4-5%, and beats the IP attack by 8-9%. This indicates that increasing the number of strongly connected nodes in a BN (and therefore increasing the dependency between attributes) means that the Bayesian approach is able to leverage more important information to improve its attack. Further, the results indicate that incorporating the attribute dependency structure in the attack is more effective when there are strong dependencies, regardless of the size of the output set.

6.4

Impact of Number of Samples on Attack Performance

To delve a bit further into the analysis of the performance trends of our approach, we wanted to understand how the number of records in the private dataset impacts the performance of the different attacks. In Figure 7, we plot the mean AUC for different attacks over the number of records for the Half and Sachs populations. As expected, all attacks perform worse as the number of records grows. However, the differences between the three methods remains fairly constant. This means that incorporating information about the population results in an attack which deteriorates at a similar rate to the attacks which assume a product distributed population. Therefore, even as we increase the dimension 13

# Node

# Param

# Out. Node

# Out. Param

Time (s)

product product product half rep. half rep. half rep. l/r rep. l/r rep. cancer earthquake asia survey sachs (leaves) sachs (path) sachs (leaf/rt)

10 20 30 10 20 30 10 20 5 5 8 6 11 11 11

10 20 30 10 20 30 10 20 10 10 16 14 33 33 33

10 20 30 10 20 30 10 20 5 5 8 6 4 5 6

10 20 30 10 20 30 10 20 10 10 16 14 12 15 18

0.567 0.617 0.656 0.551 0.592 0.614 0.590 2.473 0.669 0.686 0.710 0.740 0.884 1.143 0.920

(a) Mean computational for posterior using Roulette for different dimensions (n = 4). For the Sachs Bayesian network, we use different sets of output nodes, so the number of output parameters is different from the number of parameters in the whole network.

Runtime vs n for Different BNs 30

asia (d = 16) half rep. (d = 20) sachs (d = 33)

25 20 Time (s)

15 10 5 0

(b) Mean computational time for posterior using Roulette for different numbers of records. For the Sachs Bayesian network, we use the longest path (left) set of output nodes.

Figure 8: Comparing exact posterior computation time in Roulette for various dimensions and numbers of records on various BNs. of the data and the number of records, we still see gains from this Bayesian approach to the problem over the previous approaches. Our technique is an exact method to compute the posterior distribution in full, which does not face pitfalls (with respect to outliers) associated with sampling. We see in Fig. 8b that performance gains are consistent as n increases for various sizes of Bayesian networks. This follows the theoretical result that the ratio between d and n is important, but the absolute size of n is not.

6.5

Scalability

To evaluate the scalability of our framework implementation, we look at how long it takes to compute the posterior in Algorithm 1 for individual target points as we increase the dimension and dependence between dimensions, as well as the number of records. Times listed are averaged over 20 unique private datasets, and 40 targets points (20 in, 20 out) for each dataset. In Fig. 8a we look at the scalability of our technique on different dimensions. We see that, for constant n, increasing the dimensionality of the Bayesian network results in sub-linear scaling of the runtime. In Fig. 8b we look at the scalability of our technique on different numbers of records. We see that larger, more connected networks such as the left/right (l/r) repeated distribution and Sachs Bayesian network see significantly increasing runtimes as the number of records increases. While these results are promising, we find that Roulette has the hardest time scaling as we increase the number of samples in the private dataset, especially as the number of nodes in the Bayesian network increases. However, because of the trends we see in the AUC for the different approaches as we increase the number of samples and connected output nodes, we hypothesize that using larger dimensions will 14

only amplify the gains that we get from using prior information about the population. These results are extremely promising, and indicate that there is a lot of utility to be gained by incorporating information about the dependency structure of the population into the attack framework. Though this work does not yet scale to large examples, we have shown through theoretical and experimental results that using a Bayesian framework for designing an attack on a private dataset could have significant impact on attack utility when we have prior information. To compute larger n, one could use a PPL that supports approximate inference, though this will introduce complexity as there are many candidate approximate methods which require further tuning. Another interesting future direction would be to consider simplifications of the Bayesian network descriptions to attempt to improve the scalability of this approach on larger examples with more sample sizes, while still maintaining utility from the additional information gained from the Bayesian model of the data.

Related Works

Membership Inference. The membership inference problem for statistical release has been applied to many areas. The primary attacks with strong theoretical results are likelihood ratio test (LRT) attack and its variants [1, 2, 4] and the inner product (IP) attack [3], which typically only use the population marginals for analysis (see Sect. 3.1 and 3.2). In contrast, our Bayesian approach leverages a complete model of the population in order to create a more adaptive attack, which we demonstrate recovers or outperforms the LRT and IP attacks. Defenses Against Membership Inference Attacks. The primary defense against membership inference attacks for statistical release is to add random noise to the released statistics to make them differentially private [4, 19, 20]. This technique is effective at limiting the utility of membership inference attacks, however there is a tradeoff between privacy and utility as the amount of noise increases. An interesting future direction of this work would be to evaluate how the Bayesian attacker responds to noise in comparison to the population marginal attacks when there is strong dependency between attributes, and how much randomness has to be applied (and thereby loss of accuracy) to offset the gains made by taking dependency structure into account. Bayesian Techniques for Privacy. Bayesian inference techniques have been used in other capacities for evaluating privacy of systems. In [21], Oakley et. al use exact Bayesian inference to verify differential privacy. In [22], Pardo et. al use probabilistic inference to debug privacy risks in program code. Techniques such as stochastic conditioning have also been proposed for incorporating into privacy attacks [23]. There are also many techniques for making programming languages and program logics for differential privacy, but these mostly focus on verification [24–27]. In some instances, Bayesian networks are discussed in relationship to the membership inference problem. In [28], Murakonda et. al posit a problem setup where there are no assumptions on the population data. Instead of a statistic over the population, they are given a fixed graphical model (Bayesian network) with parameters learned from the population data. This contrasts our work, where the population is described as a Bayesian network, and the target private dataset is drawn from this Bayesian network. Probabilistic Inference and Probabilistic Programming. Our implementation relies on the field of probabilistic programming for exact probabilistic inference. In this paper, we use the state-of-the-art PPL, Roulette [8], for efficiency and expressivity. Related languages [12] also perform exact probabilistic inference and could be used instead, however they may not perform as well on larger examples. Other ongoing work on approximate Bayesian inference could be applied as well, though with potential performance tradeoffs [29]. Recent work by Stites et. al also makes advances on hybrid methods of probabilistic inference, using both exact and approximate components [30]. In this work, we consider populations with discrete features and use discrete PPLs to compute the posterior, however there also exist PPLs for probabilistic inference on continuous random variables including

Stan [31] and Pyro [32]. Machine Learning Privacy. Another related line of work is privacy attacks for machine learning, which uses statistical techniques for estimating privacy leakage in machine learning algorithms to find lower bounds [33–45]. These methods efficiently analyze privacy over large datasets, but are applied to machine learning privacy rather than statistical release, and therefore have limited theoretical guarantees.

Conclusions and Future Work

This paper is a first step into a rich and largely unexplored area of Bayesian analysis of the membership inference problem. We present promising theoretical and experimental results that incorporating a Bayesian prior can create an adaptive attack that is more effective on populations with attribute dependencies than existing attacks that rely on only the population marginals. While our proposed method for computing the Bayesian posterior via exact probabilistic inference is highly effective, it is not the only approach. For example, approximate probabilistic inference methods could improve scalability, potentially at the expense of optimality and performance.

References [1] S. Sankararaman, G. Obozinski, M. I. Jordan, and E. Halperin, “Genomic privacy and limits of individual detection in a pool,” Nature Genetics, vol. 41, no. 9, pp. 965–967, 2009, publisher: Nature Publishing Group. [Online]. Available: https://www.nature.com/articles/ng.436 [2] N. Homer, S. Szelinger, M. Redman, D. Duggan, W. Tembe, J. Muehling, J. V. Pearson, D. A. Stephan, S. F. Nelson, and D. W. Craig, “Resolving Individuals Contributing Trace Amounts of DNA to Highly Complex Mixtures Using High-Density SNP Genotyping Microarrays,” PLOS Genetics, vol. 4, no. 8, p. e1000167, 2008, publisher: Public Library of Science. [Online]. Available: https://journals.plos.org/plosgenetics/article?id=10.1371/journal.pgen.1000167 [3] C. Dwork, A. Smith, T. Steinke, J. Ullman, and S. Vadhan, “Robust traceability from trace amounts,” in 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, 2015, pp. 650–669. [4] C. Dwork, A. Smith, T. Steinke, and J. Ullman, “Exposed A Survey of Attacks on Private Data,” Annual Review of Statistics and Its Application, vol. 4, no. 1, pp. 61–84, Mar. 2017. [Online]. Available: https://www.annualreviews.org/doi/10.1146/annurev-statistics-060116-054123 [5] S. Weissman, “Hack at columbia hits 870k people,” Inside Higher Education, 12 Aug 2025, available at: https://www.insidehighered.com/news/tech-innovation/administrative-tech/2025/ 08/12/hack-columbia-university-hits-870k-people (Accessed: January 13th, 2025). [6] K. P. Murphy, Probabilistic machine learning: an introduction.

MIT press, 2022.

[7] A. Darwiche, Modeling and reasoning with Bayesian networks. Cambridge university press, 2009. [8] C. MOY, J. CZENSZAK, J. M. LI, B. MARSHALL, and S. HOLTZEN, “Roulette: A language for expressive, exact, and efficient discrete probabilistic programming (with appendices),” Proceedings of the ACM on Programming Languages, vol. 9, no. PLDI, 2025. [9] A. F. Machado, A. Charpentier, and E. Gallic, “Sequential conditional transport on probabilistic graphs for interpretable counterfactual fairness,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 39, no. 18, 2025, pp. 19 358–19 366. 16

[10] K. B. Korb and A. E. Nicholson, Bayesian artificial intelligence.

CRC press, 2010.

[11] N. K. Kitson, A. C. Constantinou, Z. Guo, Y. Liu, and K. Chobtham, “A survey of bayesian network structure learning,” Artificial Intelligence Review, vol. 56, no. 8, pp. 8721–8814, 2023. [12] S. Holtzen, G. Van den Broeck, and T. Millstein, “Scaling exact inference for discrete probabilistic programs,” Proceedings of the ACM on Programming Languages, vol. 4, no. OOPSLA, pp. 1–31, 2020. [13] K. B. Korb and A. E. Nicholson, Bayesian artificial intelligence.

CRC press, 2010.

[14] S. L. Lauritzen and D. J. Spiegelhalter, “Local computations with probabilities on graphical structures and their application to expert systems,” Journal of the Royal Statistical Society: Series B (Methodological), vol. 50, no. 2, pp. 157–194, 1988. [15] M. Scutari and J.-B. Denis, Bayesian networks: with examples in R. Chapman and Hall/CRC, 2021. [16] K. Sachs, O. Perez, D. Pe’er, D. A. Lauffenburger, and G. P. Nolan, “Causal protein-signaling networks derived from multiparameter single-cell data,” Science, vol. 308, no. 5721, pp. 523–529, 2005. [17] M. Scutari, “Learning bayesian networks with the bnlearn R package,” Journal of Statistical Software, vol. 35, no. 3, pp. 1–22, 2010. [18] A. Ankan and J. Textor, “pgmpy: A python toolkit for bayesian networks,” Journal of Machine Learning Research, vol. 25, no. 265, pp. 1–8, 2024. [Online]. Available: http://jmlr.org/papers/v25/23-0487.html [19] C. Dwork and A. Roth, “The algorithmic foundations of differential privacy,” Foundations and trends® in theoretical computer science, vol. 9, no. 3-4, pp. 211–487, 2014. [20] C. Dwork, F. McSherry, K. Nissim, and A. Smith, “Calibrating noise to sensitivity in private data analysis,” in Theory of cryptography conference. Springer, 2006, pp. 265–284. [21] L. Oakley, S. Holtzen, and A. Oprea, “Synthesizing tight privacy and accuracy bounds via weighted model counting,” in 2024 IEEE 37th Computer Security Foundations Symposium (CSF). IEEE, 2024, pp. 449–463. [22] R. Pardo, W. Rafnsson, C. W. Probst, and A. Wasowski, “Privug: using probabilistic programming for quantifying leakage in privacy risk analysis,” in European Symposium on Research in Computer Security. Springer, 2021, pp. 417–438. [23] D. Tolpin, Y. Zhou, T. Rainforth, and H. Yang, “Probabilistic programs with stochastic conditioning,” in International Conference on Machine Learning. PMLR, 2021, pp. 10 312–10 323. [24] J. P. Near, D. Darais, C. Abuah, T. Stevens, P. Gaddamadugu, L. Wang, N. Somani, M. Zhang, N. Sharma, A. Shan et al., “Duet: an expressive higher-order language and linear type system for statically enforcing differential privacy,” Proceedings of the ACM on Programming Languages, vol. 3, no. OOPSLA, pp. 1–30, 2019. [25] G. Barthe, M. Gaboardi, J. Hsu, and B. Pierce, “Programming language techniques for differential privacy,” ACM SIGLOG News, vol. 3, no. 1, pp. 34–53, 2016.

[26] M. Gaboardi, A. Haeberlen, J. Hsu, A. Narayan, and B. C. Pierce, “Linear dependent types for differential privacy,” in Proceedings of the 40th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, 2013, pp. 357–370. [27] J. Reed and B. C. Pierce, “Distance makes the types grow stronger: a calculus for differential privacy,” in Proceedings of the 15th ACM SIGPLAN international conference on Functional programming, 2010, pp. 157–168. [28] S. K. Murakonda, R. Shokri, and G. Theodorakopoulos, “Quantifying the privacy risks of learning high-dimensional graphical models,” in International Conference on Artificial Intelligence and Statistics. PMLR, 2021, pp. 2287–2295. [29] M. Sunnåker, A. G. Busetto, E. Numminen, J. Corander, M. Foll, and C. Dessimoz, “Approximate bayesian computation,” PLoS computational biology, vol. 9, no. 1, p. e1002803, 2013. [30] S. Stites, J. M. Li, and S. Holtzen, “Multi-language probabilistic programming,” Proceedings of the ACM on Programming Languages, vol. 9, no. OOPSLA1, pp. 1239–1266, 2025. [31] S. D. Team, “Stan Reference Manual,” https://mc-stan.org, 2026. [32] E. Bingham, J. P. Chen, M. Jankowiak, F. Obermeyer, N. Pradhan, T. Karaletsos, R. Singh, P. A. Szerlip, P. Horsfall, and N. D. Goodman, “Pyro: Deep universal probabilistic programming,” J. Mach. Learn. Res., vol. 20, pp. 28:1–28:6, 2019. [Online]. Available: http://jmlr.org/papers/v20/18-403.html [33] M. Jagielski, J. Ullman, and A. Oprea, “Auditing differentially private machine learning: How private is private SGD?” in Proceedings of Advances in Neural Information Processing Systems, ser. NeurIPS, vol. 33, 2020, pp. 22 205–22 216. [Online]. Available: https://proceedings.neurips.cc/paper/2020/file/fc4ddc15f9f4b4b06ef7844d6bb53abf-Paper.pdf [34] M. Nasr, S. Song, A. Thakurta, N. Papernot, and N. Carlini, “Adversary instantiation: Lower bounds for differentially private machine learning,” in 42nd IEEE Symposium on Security and Privacy, SP 2021, San Francisco, CA, USA, 24-27 May 2021. IEEE, 2021, pp. 866–882. [Online]. Available: https://doi.org/10.1109/SP40001.2021.00069 [35] G. Andrew, P. Kairouz, S. Oh, A. Oprea, H. B. McMahan, and V. Suriyakumar, “One-shot empirical privacy estimation for federated learning,” CoRR, vol. abs/2302.03098, 2023. [36] M. Nasr, J. Hayes, T. Steinke, B. Balle, F. Tramèr, M. Jagielski, N. Carlini, and A. Terzis, “Tight auditing of differentially private machine learning,” in Proceedings of the 32nd USENIX Conference on Security Symposium, ser. SEC ’23. USA: USENIX Association, 2023. [37] K. Pillutla, G. Andrew, P. Kairouz, H. B. McMahan, A. Oprea, and S. Oh, “Unleashing the power of randomization in auditing differentially private ML,” in Thirtyseventh Conference on Neural Information Processing Systems, 2023. [Online]. Available: https://openreview.net/forum?id=mlbes5TAAg [38] M. J. Thomas Steinke, Milad Nasr, “Privacy auditing with one (1) training run,” in Thirty-seventh Conference on Neural Information Processing Systems, 2023. [Online]. Available: https://openreview.net/forum?id=mlbes5TAAg [39] J. Ye, A. Maddi, S. K. Murakonda, V. Bindschaedler, and R. Shokri, “Enhanced membership inference attacks against machine learning models,” in Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, 2022, pp. 3093–3106. 18

[40] S. Zarifzadeh, P. Liu, and R. Shokri, “Low-cost high-power membership inference attacks,” in Forty-first International Conference on Machine Learning (ICML), 2024. [41] Y. Tong, J. Ye, S. Zarifzadeh, and R. Shokri, “How much of my dataset did you use? quantitative data usage inference in machine learning,” in The Thirteenth International Conference on Learning Representations (ICLR), 2025. [42] J. Tao and R. Shokri, “Range membership inference attacks,” in IEEE Conference on Secure and Trustworthy Machine Learning (SaTML), 2025. [43] M. Nasr, R. Shokri, and A. Houmansadr, “Comprehensive privacy analysis of deep learning,” in Proceedings of the 2019 IEEE Symposium on Security and Privacy (SP), 2018, pp. 1–15. [44] R. Shokri, M. Stronati, C. Song, and V. Shmatikov, “Membership inference attacks against machine learning models,” in 2017 IEEE symposium on security and privacy (SP). IEEE, 2017, pp. 3–18. [45] S. Kumar and R. Shokri, “Ml privacy meter: Aiding regulatory compliance by quantifying the privacy risks of machine learning,” in Workshop on Hot Topics in Privacy Enhancing Technologies (HotPETs), 2020.

Generative AI Usage Statement

The authors did not use LLMs in any way in the research or writing of this paper.

Lemmas for Main Theorems

Here we present two main lemmas to help prove correctness of the Bayesian approach on selected data distributions. Lemma 1 (Ratio Equality). Given a population that follows a product distribution, the ratio R in eqn. (8) is equivalent to the ratio Λ in eqn. (4). Proof. Let BN (P) be the Bayesian network of a product population with dimension d, as described in Fig. 2 with probability vector µ such that µj for j ∈ {1, . . . , d}. Let private dataset D = P {x(1) , . . . , x(n) } consist of n samples (records) drawn i.i.d. from P with sample mean x = n1 ni=1 x(i) . Let target y be some target record drawn from U(D) or from P. For clarity, we set A ← (BN (P), x, y). By the definition of conditional probability, P r(ℓIN ,A)

P r(ℓIN | A) P r(ℓIN , A) P r(A) R= = P r(¬ℓ ,A) = . IN P r(¬ℓIN | A) P r(¬ℓIN , A) P r(A)

By the definition of Algorithm 1, the definition of the Bayesian network, and arithmetic, we have that P P r(y + n−1 µ = x · n) P r(ℓIN , A) Pn i=1 = P r(¬ℓIN , A) P r( i=1 µ = x · n) P P r( n−1 i=1 µ = x · n − y) P = P r( ni=1 µ = x · n)

Because the coordinates are independent, we have P P r( n−1 i=1 µ = x · n − y) P P r( ni=1 µ = x · n) Qd Pn−1 j=1 P r( i=1 µj = xj · n − yj ) = Pn Qd j=1 P r( i=1 µj = x · n) P d Y P r( n−1 i=1 µj = xj · n − yj ) P = P r( ni=1 µj = x · n) j=1

Let’s look at a single coordinate, j ∈ {1, . . . , d} and let k = xj · n and q = 1 − µj for notational simplicity. Because we have binomial distribution (B(·, ·)) on the top and bottom, therefore, we have that P P r( n−1 B(n − 1, µj )(k − yj ) i=1 µj = k − yj ) Pn = P r( i=1 µj = k) B(n, µj )(k) k−yj n−1−(k−y ) n−1 j ) (q k−yj µj = n k n−k ) k µj (q If yj = 0, we have n−1 k−yj

k−yj

µj

(q n−1−(k−yj ) )

n k n−k ) k µj (q

n−1 k n−1−(k) ) k µj (q n k n−k ) k µj (q

n − (nxj ) n−k = nq n(1 − µj ) n(1 − xj ) 1 − xj = = n(1 − µj ) 1 − µj =

If yj = 1, we have n−1 k−yj

k−yj

µj

(q n−1−(k−yj ) )

n k n−k ) k µj (q

n−1 k−1 n−1−(k−1) (q ) k−1 µj k n n−k ) k µj (q

nxj xj k = = nµj nµj µj

Therefore, we have P d Y P r( n−1 i=1 µj = xj · n − yj ) P R= P r( ni=1 µj = xj · n) j=1

d Y j=1

xj 1 − xj if yj = 1 then else µj 1 − µj

j=1 {if yj = 1 then xj else 1 − xj }

= Qd

j=1

if yj = 1 then µj else 1 − µj

= Λ, as desired. 20

Lemma 2 (Partial Ratio Equality). Given a population that follows a left/right repeated distribution as described in Fig. 3b with parameter mid, the ratio R in eqn. (8) is equivalent to the ratio Λmid,side in eqn. (7) or (6) for fixed side ∈ {lef t, right}. Proof. Let BN (P) be the Bayesian network of a left/right repeated population with dimension d and midpoint mid, as described in Fig. 3b. Let private dataset D = {x(1) , . . . , x(n) } consist of n samples 1 Pn (records) drawn i.i.d. from P with sample mean x = n i=1 x(i) . Let target y be some target record drawn from U(D) or from P. For clarity, we set A ← (BN (P), x, y). By the definition of conditional probability, P r(ℓIN ,A)

P r(ℓIN | A) P r(ℓIN , A) P r(A) R= = P r(¬ℓ ,A) = . IN P r(¬ℓIN | A) P r(¬ℓIN , A) P r(A)

If side = right, we know that attributes 1 to mid are independent, and for j ∈ {mid + 1, . . . , d}, µj = µmid , xj = xmid , and yj = ymid . Therefore we can split this quantity into two parts: P r(ℓIN , A) = P r(¬ℓIN , A) mid−1 Y j=1

! P P r( n−1 i=1 µj = xj · n − yj ) P P r( ni=1 µj = xj · n)

P p = xmid · n − ymid ) P r( n−1 i=1 P mid · . P r( ni=1 pmid = xmid · n) By applying Lemma 1 twice, once with the product network of dimension d = mid and once with the product network of dimension d = 1, this is equivalent to mid−1 Y j=1

{if yj = 1 then xj else 1 − xj } if yj = 1 then µj else 1 − µj

{if ymid = 1 then xmid else 1 − xmid } {if ymid = 1 then µmid else 1 − µmid } Qmid j=1 {if yj = 1 then xj else 1 − xj } = Qmid j=1 if yj = 1 then µj else 1 − µj

= Λmid,side , as desired. When side = lef t, we have a symmetrical argument, where the left hand of the product represents the repeated elements for j = 1 to mid − 1, and the right hand side of the product represents the independent elements mid to d. We similarly apply Lemma 1 to both sides of the product and get: R=

{if ymid = 1 then xmid else 1 − xmid } {if ymid = 1 then µmid else 1 − µmid } d Y

{if yj = 1 then xj else 1 − xj } if yj = 1 then µj else 1 − µj j=mid−1 Qd j=mid {if yj = 1 then xj else 1 − xj } = Qd j=mid if yj = 1 then µj else 1 − µj

= Λmid,side , 21

as desired. We have covered both cases, thus completing our proof.

Example Bayesian Network Construct

This is an example of an encoding of the Cancer Bayesian network from Fig. 1a written in the Roulette probabilistic programming language. (define NETWORK ’((variable Pollution (type discrete (2) (low high))) (variable Smoker (type discrete (2) (True False))) (variable Cancer (type discrete (2) (True False))) (variable Xray (type discrete (2) (positive negative))) (variable Dyspnoea (type discrete (2) (True False))) (probability (Cancer Pollution Smoker) ((high False) 0.02 0.98) ((high True) 0.05 0.95) ((low False) 0.001 0.999) ((low True) 0.03 0.97)) (probability (Dyspnoea Cancer) ((False) 0.3 0.7) ((True) 0.65 0.35)) (probability (Pollution) (table 0.9 0.1)) (probability (Smoker) (table 0.3 0.7)) (probability (Xray Cancer) ((False) 0.2 0.8) ((True) 0.9 0.1))))

Additional Experimental Results for Weak and Weakest Threat Models

In Sec. 6.2 we present the results for running the attacks under the weak and weakest threat models. In Fig. 9, we demonstrate that the Bayesian attacker is similarly effective across three other benchmarking Bayesian networks.

BN (d)

Attack

AUC

Std.

BN (d)

Attack

AUC

Std.