Rethinking Query Choices for Differential Privacy Auditing

Auditing differential privacy (DP) guarantees often relies on querying trained models with specially crafted queries, such as canaries, examples differing between two neighboring datasets. However, in this work, we revisit this common approach and identify a fundamental limitation: canary-based queries may not capture the strongest privacy leakage, as the most informative queries can shift during the training process. This mismatch can result in loose lower bounds on the privacy parameter$\varepsilon$, underestimating potential risks from query-based adversaries. To address this issue, we propose two methods. First, we introduce a consistent and optimizable surrogate privacy loss function that better aligns with the true privacy loss, called Privacy-loss Maximization Method (PMM), enabling systematic discovery of stronger queries through optimization. Second, we analyze how the optimal queries evolve with model training and propose a gradient-aligned query generation algorithm, called Gradient-Guided Querying (GGQ), that rapidly identifies high-risk queries by aligning their gradients with the distribution of model parameters. Empirical evaluations across multiple tasks demonstrate that our methods consistently produce stronger privacy audit results, offering a more accurate assessment of the privacy risks associated with training algorithms.