DDUO: General-Purpose Dynamic Analysis for Differential Privacy

I. INTRODUCTION

• Existing compositional-verification languages require substantial type annotations, while PINQ is limited to SQL-like database queries and side-effect-free methods,, [39], [17], [52],,,,, [9],, [4], [51], [46],, [18], [45],.These constraints motivate DDUO’s general-purpose approach.Source: §I · p. 1
• DDUO is an automatic dynamic analysis for enforcing differential privacy, usable without additional type annotations as a library for existing languages, with a Python reference implementation.Source: §I · pp. 1–2
• DDUO tracks sensitivity and privacy for general-purpose operations, including mapping arbitrary functions over lists, and permits mutation inside methods manipulating sensitive values.Source: §I · p. 2
• DDUO supports various sensitivity notions, arbitrary distance metrics including L1 and L2, and advanced privacy variants including (ε, δ)- and Rényi differential privacy.Source: §I · p. 2
• Dynamic sensitivity analysis must bound sensitivity from a single observed execution while generalizing to arbitrary future inputs, and DDUO attaches sensitivity environments and metrics to values to provide sound global bounds.The approach addresses side effects, conditionals, and higher-order functions.Source: §I · p. 2
• DDUO uses privacy filters and odometers to track total privacy cost across mechanism applications, building on prior work designed for adaptive privacy-parameter choices.Source: §I · p. 2
• The paper formalizes DDUO’s sensitivity analysis and proves its soundness with a step-indexed logical relation, then demonstrates practical use through case studies of complex differentially private algorithms.The case studies include adaptive variants of state-of-the-art machine-learning algorithms and integrations with popular Python data-analysis libraries.Source: §I · p. 2

II. BACKGROUND

• Differential privacy protects individuals by making outputs statistically indistinguishable for datasets differing in one person’s information; sequential composition may not permit adaptive privacy parameters.Advanced composition and variants such as Rényi and zero-concentrated differential privacy improve composition bounds.Source: §II · pp. 2–3

III. OVERVIEW OF DDUO

• DDUO runs as a Python library with runtime access to program information, requiring no added type annotations and integrating with Pandas and NumPy.The stated threat model assumes a well-intentioned but fallible programmer; malicious code or third-party libraries can bypass the monitor, and data-dependent exceptions and side channels are not addressed.Source: §III · p. 3

IV. DDUO BY EXAMPLE

• Sensitive values keep analysts from viewing raw data while sensitivity environments record each value’s sensitivity to input data sources.The environments are updated as operations are applied: adding a constant leaves sensitivity unchanged, while adding a DataFrame to itself doubles it.Source: §IV · p. 3
• DDUO’s Laplace mechanism adds noise to a row count for ε = 1.0, after which the result is an ordinary Python value available for further computation.Post-processing means DDUO no longer tracks sensitivity or privacy cost for operations on that released value.Source: §IV · p. 4
• Two Laplace releases, each with ε = 1.0, produce a total privacy cost of 2.0, which an odometer reports and a filter can bound.Odometers track total cost, while filters impose an upper bound on that cost.Source: §IV · p. 4

V. DYNAMIC SENSITIVITY TRACKING

• At runtime, each Sensitive object holds its value and sensitivity environment, which records how input changes bound changes to the computed value.An environment entry {a 7→1} means changing input a by n changes the result by at most n.Source: §V · p. 4

A. Bounding the Sensitivity of Operations

• DDUO defines operations on Sensitive objects to perform the underlying operation and construct a result sensitivity environment by element-wise summing input environments.It provides sensitivity-aware Python numeric operations and versions of commonly used Pandas functions, plus subsets of NumPy and Scikit-learn.Source: A. Bounding the Sensitivity of… · p. 4

B. Distance Metrics

• DDUO tracks distance metrics for sensitive values, and metric choice matters because the Laplace mechanism requires L1 while the Gaussian mechanism accepts L1 or L2.The L∞ shorthand measures the number of differing elements for spaces with equality.Source: B. Distance Metrics · p. 5

C. Conditionals & Side Effects

• Dynamic analysis cannot bound differing branch sensitivities by taking the maximum, and DDUO rejects sensitive conditional guards to retain soundness.The guard restriction lets it ignore unexecuted branches; sensitive-guard conditionals yield infinite sensitivity even under precise static analysis.Source: C. Conditionals & Side Effects · p. 5
• Attaching sensitivity environments to values preserves them when variables are reassigned, supporting common side-effect patterns and a sound analysis formalized for side effects and conditionals.The paper states dynamic analysis is more capable than type-based static analysis for side effects because static analysis faces challenges such as aliasing.Source: C. Conditionals & Side Effects · p. 5

VI. DYNAMIC PRIVACY TRACKING

• Dynamic privacy tracking must account for adaptively chosen parameters: analyzing only the executed branch and ignoring the other would make privacy-cost tracking unsound.The executed branch can depend on a nondeterministic mechanism result, and sequential composition does not directly apply to adaptively chosen privacy parameters.Source: §VI · p. 5

A. Privacy Filters & Odometers

• Odometers return a running and final upper bound on adaptive privacy cost, while filters halt a sequence when its specified bound would be violated.For sequential (ε, δ)-differential privacy, these tools yield the same bounds as the standard sequential composition theorem; advanced composition has slightly worse constants but is asymptotically the same.Source: A. Privacy Filters & Odometers · p. 6

B. Filters & Odometers in DDUO

• DDUO lets programmers activate an odometer or filter for part of a program and provides sequential, advanced-composition, and Rényi-DP variants.An active odometer records a running total; an active filter tracks individual mechanisms and halts when its upper bound is violated.Source: B. Filters & Odometers in DDUO · p. 6

C. Loops and Composition

• Python loops can repeatedly apply mechanisms under odometer tracking, and switching to an advanced-composition odometer changes the composition analysis.The examples use a loop that runs the Laplace mechanism 20 times and replace the sequential odometer with an advanced-composition one.Source: C. Loops and Composition · p. 6

D. Mixing Variants of Differential Privacy

• DDUO supports pure ǫ-differential privacy, (ǫ, δ)-differential privacy, and RDP, allowing programs to mix, convert between, and compose their mechanisms.Using RDP for sequential composition can improve privacy cost when composition is extensive; the example converts the total cost to (ǫ, δ)-differential privacy after 200 Gaussian mechanism uses.Source: D. Mixing Variants of Differential… · p. 7

VII. FORMAL DESCRIPTION OF SENSITIVITY ANALYSIS

• Function sensitivity is a two-run property computed after one observed execution, with sensitive-input-dependent branching and scalar-side multiplication arguments disallowed.The restrictions ensure the compared runs take the same branch and use the same scalar-side argument; the monitor is proved to report an upper bound on true sensitivity.Source: §VII · p. 7
• The formal proof uses step-indexed big-step semantics and a logical relation, with induction and syntax case analysis to establish metric preservation.Step-indexing makes the relation's recursive definition well-founded by decreasing its index.Source: §VII · p. 7
• Metric preservation relates outputs and analysis results from related initial configurations, supporting the soundness of DDUO's sensitivity analysis.The corollary extends the result to two arbitrary runs when one environment matches the analyzed execution on non-sensitive values.Source: §VII · pp. 8–9

• The proof uses metric preservation and stated hypotheses to establish its goal.Source: Then: r1 ∼Σ ′·Σ · p. 9
• Figure 2 presents the formal big-step, step-indexed semantics and metafunctions.Source: Figure 2 · p. 10
• The analysis result from one execution describes sensitivity across two arbitrary runs, including runs with inputs different from the analyzed execution.Source: Then: r1 ∼Σ ′·Σ · p. 10

VIII. IMPLEMENTATION & CASE STUDIES

• The Python prototype initially supports NumPy, Pandas, and Sklearn, with hooks for tracking sensitivity and privacy across additional libraries.Sensitivity annotations let DDUO reuse high-performance library implementations and avoid creating extra objects.Source: §VIII · pp. 10–11
• DDUO’s analysis overhead was generally low in the case studies, with the worst observed overhead below 60%.In a rare case, mapping over one million numbers took 160× longer than standard Python.Source: §VIII · p. 11
• In a rare case, mapping a function over one million numbers took 160× longer under DDUO than in standard Python.The reported causes are DDUO’s slower Python map and creating a Sensitive object for each list element.Source: §VIII · p. 11
• In the NumPy gradient-descent case, clipping bounds gradient sensitivity before summation, and noise is added to the gradient calculation exposed to private data.The case study implements a machine-learning algorithm with DDUO-instrumented NumPy primitives.Source: §VIII · p. 11
• The adaptive Renyi differential privacy variant gives a tighter multi-iteration leakage analysis and permits halting at target accuracy or minimized loss to conserve budget.The case studies include adaptive algorithm variants whose privacy parameters are chosen adaptively, which prior purely static analyses cannot verify.Source: §VIII · pp. 11–12

IX. RELATED WORK

• PINQ offers dynamic sensitivity and privacy analysis for SQL-like relational queries, while its expressiveness is limited and library algorithms may not track composition.The related-work discussion also notes that methods in PINQ are assumed side-effect free.Source: §IX · p. 12
• Static sensitivity-analysis approaches require type annotations; other verification approaches are less automatable or restricted to first-order imperative programs, while testing runs programs repeatedly.Adaptive Fuzz combines static sensitivity analysis with dynamic privacy analysis; testing approaches use neighboring inputs and repeated runs.Source: §IX · pp. 12–13

X. CONCLUSION

• The conclusion reports a step-indexed logical-relation proof of sensitivity-analysis soundness and case studies enforcing adaptive variants of state-of-the-art private machine-learning algorithms.Those case studies integrate with popular Python data-analysis libraries.Source: §X · p. 13

APPENDIX A LEMMAS, THEOREMS & PROOFS

• The triangle lemma composes relations through r2 into a relation between r1 and r3 with distance rA + rB and metric mA ⊔ mB.It assumes r1 ∼rA mA r2 and r2 ∼rB mB r3.Source: Appendix A · p. 15
• Metric Preservation is proved by strong induction on step index n and case analysis on expression e.The proof proceeds through expression cases, applying the induction hypothesis to show preservation properties.Source: Appendix A · p. 15
• The sound dynamic-analysis corollary uses Metric Preservation to derive Σ1 = Σ and m1 = m, then proves goal (C1) under its listed hypotheses.The proof explicitly appeals to Metric Preservation and the hypotheses identified as (H1)–(H6).Source: Appendix A · p. 15
• For the dereference case, the proof derives the required conditions from the induction hypotheses, including equality of locations.It applies inversion to the premises and uses the induction hypothesis at a decreasing index.Source: Appendix A · p. 16
• For e1 ← e2, the proof splits the index across both subexpressions and combines their induction hypotheses to establish the conditions.Step-index weakening supplies the relation needed to apply the induction hypothesis to the second subexpression.Source: Appendix A · p. 18

A. MWEM with Pandas

• MWEM constructs a differentially private synthetic dataset approximating a real dataset, combining private mechanisms with multiplicative weights updates over iterations.Its privacy leakage is analyzed through composition.Source: A. MWEM with Pandas · p. 18
• At each iteration, MWEM privately selects a workload query whose synthetic-data result differs greatly from the real result, then uses the private real-data result to update the synthetic dataset.The query selection uses the exponential mechanism, and the update uses multiplicative weights.Source: A. MWEM with Pandas · p. 18
• The adaptive MWEM variant privately halts when synthetic-data error reaches an acceptable level before exhausting the budget, conserving the remainder for other private analyses.The standard inputs include a domain distribution, sensitive dataset, query workload, iteration count, and privacy budget.Source: A. MWEM with Pandas · p. 18

B. DiffPrivLib

• DDUO hooks in a private iris Naive Bayes example detect sensitivity violations and track privacy cost.The example modifies the original program to add those hooks.Source: B. DiffPrivLib · p. 18
• The private Naive Bayes and differentially private logistic-regression examples both use adaptive clipping, gradually modifying clipping parameters over several iterations to optimize model accuracy.Source: B. DiffPrivLib · pp. 18–19
• Control flow on probabilistic values is sound only with DDUO's adaptive composition; hyperparameter optimization should normally use artificial datasets based on domain knowledge.Source: B. DiffPrivLib · p. 19
• 15 lines of DDUO instrumentation integrate with DiffPrivLib, adding dynamic and adaptive privacy tracking beyond its basic accountant.The integration enables tight privacy analysis for more sophisticated composition with minimal changes to library and program code.Source: B. DiffPrivLib · pp. 18–19