Stochastically Testing Privacy Mechanisms

How do you validate that a differential privacy implementation actually works?

One approach that can build confidence that the differential privacy property holds for an implementation is stochastic testing: run many iterations of the algorithm against neighboring databases and check that for any output, the expected probability is bounded by \(\epsilon\).

# Preamble: imports and figure settings

from eeprivacy import PrivateClampedMean

import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
import matplotlib as mpl
from scipy import stats

np.random.seed(1234) # Fix seed for deterministic documentation

mpl.style.use("seaborn-white")

MD = 20
LG = 24
plt.rcParams.update({
    "figure.figsize": [25, 7],
    "legend.fontsize": MD,
    "axes.labelsize": LG,
    "axes.titlesize": LG,
    "xtick.labelsize": LG,
    "ytick.labelsize": LG,
})

In the test below, we run a PrivateClampedMean for a large number of trials for two different databases: one with a single element 0 and one with a single element 1.

Then, we bin the results and compute the “realized \(\epsilon\)” for each bin. By chance, sometimes this will slightly exceed the \(\epsilon\) value. The test fails if the realized \(\epsilon\) greatly exceeds the desired \(\epsilon\) for any of the bins.

private_mean = PrivateClampedMean(lower_bound=0, upper_bound=1)

T = 1000000
A = [private_mean.execute(values=[], epsilon=0.1) for t in range(T)]
B = [private_mean.execute(values=[1], epsilon=0.1) for t in range(T)]

L = 0
U = 1

A = np.clip(A, L, U)
B = np.clip(B, L, U)

bins = np.linspace(L, U, num=50)

fig, ax = plt.subplots()
ax.set_yscale("log")

plt.hist(A, color='b', alpha=0.5, bins=bins)
plt.hist(B, color='r', alpha=0.5, bins=bins)
plt.title("Compare output likelihood for neighboring databases")
plt.xlabel("Output")
plt.ylabel("Count (log scale)")
plt.show()

A, bin_edges = np.histogram(A, bins=bins)
B, bin_edges = np.histogram(B, bins=bins)

realized_epsilon = np.abs(np.log(A / B))

plt.hist(realized_epsilon, color="k", bins=20)
plt.title("Realized ε")
plt.xlabel("ε")
plt.ylabel("Count")
plt.show()