📊 statistics

Detectability in Diversity: Improved Canary Crafting for Privacy Auditing in One Run

This paper proposes a novel canary crafting method for one-run privacy auditing that combines greedy initialization with bilevel optimization to maximize canary detectability while minimizing interference, thereby achieving stronger privacy leakage estimates at lower computational costs than existing approaches.

Original authors: Mathieu Dagréou, Aurélien Bellet

Published 2026-05-27

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Mathieu Dagréou, Aurélien Bellet

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The Privacy "Canary in the Coal Mine"

Imagine you have built a machine learning model (a smart computer program) and you want to know: "Did this program memorize my private data, or did it just learn general patterns?"

To find out, security experts use a trick called Privacy Auditing. They plant special, fake data points into the training set called "Canaries." Think of these canaries like a unique, bright red feather hidden inside a giant pile of gray feathers.

The Goal: After the model is trained, the auditor asks the model: "Do you remember this red feather?"
The Test: If the model says "Yes, I definitely remember that specific red feather," it means the model has memorized specific data points, which is a privacy risk. If it says "No," the privacy is likely safe.

The Problem: The "Crowded Room" Effect

In the past, to get a reliable answer, auditors had to play this game thousands of times. They would hide one red feather, train the model, check, then start over with a new feather. This was incredibly slow and expensive (like rebuilding a house just to check if a specific brick is visible).

To speed this up, researchers invented "One-Run Auditing." Instead of hiding one feather at a time, they hide many red feathers (canaries) in the same pile all at once. They train the model once and check all the feathers simultaneously.

But here is the catch: When you hide too many red feathers close together, they start to interfere with each other.

The Analogy: Imagine trying to hear a whisper in a quiet room. It's easy. Now, imagine 50 people whispering at once. The sounds blend together, creating noise. It becomes hard to tell which specific person is whispering.
In the paper: If two canaries are too similar (like two red feathers that look almost identical), the model gets confused. The presence of one canary "drowns out" the signal of the other. This makes the audit weaker, and the privacy test less accurate.

The Solution: IBIS (The Smart Canary Maker)

The authors propose a new method called IBIS to solve this. They want to create a set of canaries that are:

Highly Detectable: They must be unique enough that the model wants to memorize them.
Diverse: They must be different enough from each other so they don't "talk over" one another.

They do this in two steps:

Step 1: The "Greedy" Selection (Finding the Best Candidates)

First, the system scans the existing data to find the "loudest" whispers. It uses a mathematical tool called Influence Functions to measure two things for every potential canary:

Self-Influence: How much does this data point affect the model on its own? (We want this high).
Cross-Influence: How much does this data point mess up the signal of other data points? (We want this low).

The system picks the top candidates that are loud but don't interfere with each other. It's like picking a choir where every singer has a distinct voice and none of them are singing the exact same note at the same time.

Step 2: The "Bilevel" Refinement (Polishing the Canaries)

Once the system has a good starting group, it doesn't just leave them alone. It uses a sophisticated optimization process (Bilevel Optimization) to tweak the canaries slightly.

The Analogy: Imagine you have a group of actors. You've picked the best ones, but now you want to make sure they stand in a formation where everyone is visible to the audience. You gently nudge them apart so they don't block each other, while making sure they still look like the characters they are supposed to be.
The Innovation: Previous methods tried to do this by retraining the whole model from scratch every time they moved a canary. That was like rebuilding the entire theater every time an actor moved a chair. The authors' method updates the model incrementally as the canaries move, which is much faster and cheaper.

The Results: Faster and Stronger

The paper shows that their method (IBIS) works better than previous attempts:

Better Detection: The canaries they create are easier for the model to memorize, meaning the privacy audit is more sensitive and accurate.
Less Interference: Because the canaries are diverse, they don't cancel each other out.
Much Cheaper: The most impressive result is speed. Their method takes about 2.5 hours on a powerful computer to generate 1,000 canaries. The previous best method took 90 to 120 hours.

Summary

This paper introduces a smarter way to test if AI models are leaking private data. Instead of randomly picking test data and hoping for the best, they use math to carefully select and shape "test data" that are loud enough to be heard but distinct enough not to confuse each other. This allows auditors to check privacy in a single run, saving massive amounts of time and computing power.

Technical Summary: Detectability in Diversity: Improved Canary Crafting for Privacy Auditing in One Run

Problem Statement

Privacy auditing aims to empirically assess privacy leakage in machine learning models, often to derive lower bounds on Differential Privacy (DP) parameters. This is typically achieved via Membership Inference Attacks (MIAs), where an adversary attempts to determine if a specific data point was part of a model's training set.

Standard auditing approaches require training thousands of independent models with varying canary inclusions to obtain statistically reliable estimates, which is computationally prohibitive. To address this, "one-run" auditing was proposed, where a single model is trained on a dataset containing multiple canaries, each included independently with probability 1/2. The adversary then infers the inclusion status of all canaries from this single model.

However, a significant gap exists between the theoretical privacy upper bounds (provided by accounting methods) and the empirical lower bounds (estimated by one-run auditing). Recent literature attributes this gap to interference between canaries: the inclusion or exclusion of one canary $z'$ can alter the MIA confidence score of another canary $z$ , particularly when canaries are similar in representation space. This interference degrades the adversary's ability to distinguish members from non-members, leading to weaker leakage estimates compared to multi-run methods. Existing canary crafting methods do not explicitly enforce diversity to mitigate this interference.

Methodology

The authors propose IBIS (Influence-Bilevel canary crafting with Interference Suppression), a two-stage pipeline designed to craft canaries that are both highly detectable (strongly memorized) and diverse (minimally interfering).

1. Greedy Initialization via Influence Functions

The first stage selects an initial set of canaries from the training data using influence functions, which measure the effect of upweighting a data sample on a model.

Self-Influence ( $I_s(z, z)$ ): A proxy for memorizability. High self-influence indicates that a point is strongly memorized by the model.
Cross-Influence ( $I_s(z, z')$ ): A proxy for interference. High cross-influence indicates that the presence of $z'$ significantly affects the score of $z$ .
Selection Strategy: The algorithm greedily selects a set of $m$ canaries to maximize the ratio of self-influence to the maximum cross-influence from other selected canaries. This is formulated as a combinatorial optimization problem solved via a greedy heuristic. This step provides a strong initialization with low pairwise interference at a low computational cost.

2. Bilevel Optimization with Diversity Regularization

The second stage refines the selected canaries using gradient-based optimization. Unlike prior work that requires retraining the model for every subset of canaries (computationally intractable), the authors formulate a tractable bilevel optimization problem.

Objective: Minimize a distinguishability objective that maximizes the score difference between included and excluded canaries, subject to the constraint that the model parameters minimize the empirical risk.
Diversity Regularizer: To explicitly suppress interference, a regularizer $R(C)$ is added, promoting orthogonality in the representation space (embeddings) of the canaries:
$R_{\theta^*}(C) = \lambda \sum_{z, z' \in C, z \neq z'} \langle \phi_{\theta^*}(z), \phi_{\theta^*}(z') \rangle^2$
where $\phi_{\theta^*}$ maps samples to their embeddings under the base model $\theta^*$ .
Efficient Solver (SOBA): The authors employ an Approximate Implicit Differentiation (AID) approach, adapting the SOBA algorithm. This maintains coupled variables for the model parameters ( $\theta$ ), the influence vector ( $v$ ), and the canary inputs ( $C_x$ ). Crucially, the model is updated incrementally alongside the canaries rather than retrained from scratch at each step, enabling efficient computation of hypergradients.

Key Contributions

Greedy Influence-Based Selection: A low-cost algorithm that identifies training points with high memorability and low mutual interference, serving as a robust initialization for further optimization.
Bilevel Optimization Formulation: A novel formulation that incorporates an explicit diversity regularizer to enforce orthogonality in representation space. This formulation allows for efficient bilevel algorithms by updating the model incrementally, avoiding the prohibitive cost of retraining for every subset of canaries.
IBIS Pipeline: A unified framework combining the above components. It achieves stronger privacy leakage estimates than existing methods while requiring substantially lower computational resources.

Experimental Results

The method was evaluated on WideResNet (WRN16-4) and CNN architectures using the CIFAR-10 dataset.

Ablation Studies: Influence-based preselection outperformed random selection even before bilevel optimization. In non-private settings, the diversity regularizer further improved performance.
Membership Inference (MIA): When crafting canaries using the same architecture as the audited model (WRN16-4), the regularized IBIS achieved near-perfect True Positive Rates (TPR) at 0.05 False Positive Rate (FPR), significantly outperforming random baselines and matching or exceeding the performance of the state-of-the-art method by Boglioni et al. [6].
DP Auditing: The method provided competitive lower bounds on the privacy parameter $\epsilon$ compared to existing approaches. While the estimates showed high variance (consistent with the difficulty of the DP auditing setting), IBIS matched the performance of prior work.
Computational Efficiency: The proposed method is significantly more efficient. Generating 1000 canaries required approximately 2.5 GPU hours on an NVIDIA A100, compared to 90–120 hours reported for the retraining-based approach of Boglioni et al. [6]. This efficiency gain stems from the incremental model updates rather than full retraining.

Significance and Claims

The paper claims that the primary limitation of existing one-run auditing approaches is the interference between canaries. By explicitly addressing this through influence-based selection and a diversity-promoting bilevel optimization, the authors demonstrate that it is possible to close the gap between one-run and multi-run auditing performance.

The significance of this work lies in making one-run privacy auditing computationally feasible and statistically stronger. By reducing the computational cost by an order of magnitude while maintaining or improving audit strength, the method enables auditors to use the specific architecture of the model being audited for canary generation, which the authors show significantly improves performance. The authors position this as a practical advancement for empirical privacy evaluation, particularly for large-scale models where multi-run auditing is infeasible.