Checkpoints interact with noise seeds in an inconsistent way, which can impact privacy guarantees

Start by tracing how dpsynth.checkpoint stores and restores MST's one-way counts and how the supplied NumPy RNG is used when two-way counts are computed; the issue says AIM is affected too. Reproduce the behavior with the supplied script and compare the noise across one-way and two-way measurements. Done means checkpointing and seeded runs cannot produce the privacy violating repeated noise described here, with the behavior documented and tested.

What happens when running MST with both a checkpoint and a seed? I.e. what does the following code do behind the scenes?

  with tempfile.TemporaryDirectory() as d, dpsynth.checkpoint(d):
    mech(np.random.default_rng(seed), data)
    mech(np.random.default_rng(seed), data)

The API or the documentatio don't really provide a clear answer, and the behavior doesn't seem right from a privacy standpoint.

1. The first run of the mechanism will store the one-way counts inside the checkpoint, using the RNG stream at position 0. It will also compute two-way counts and all the rest, but this won't be checkpointed.
2. The second run of the mechanism will retrieve the one-way counts from the checkpoint, then recompute the two-way counts with a re-initialized RNG. So you end up with noisy marginals where the noise added to the one-way counts is identical to the noise added to two-way counts.

If an attacker knows that the counts were generated this way (arguably a bit of a stretch) and is trying to guess which of two neighboring databases was used, they can compare the noisy numbers to the true numbers, and count the number of repetitions in the noise (after rescaling by the standard deviation) between one-way and two-way marginals. In the "wrong" database, there will be fewer such noise repetitions because the added/removed record is going to shift some of the statistics. This gives a discriminating event that's much stronger than what DP should allow. Here's a repro which implements that attack:

import math, tempfile
import numpy as np
import pandas as pd
import dpsynth

D = pd.DataFrame({"A": ["a0", "a0", "a0", "a1", "a1", "a2", "a2", "a2"],
                  "B": ["b0", "b1", "b2", "b1", "b1", "b0", "b2", "b2"]})
D2 = pd.DataFrame({"A": ["a0", "a0", "a0", "a1", "a1", "a2", "a2", "a2", "a1"],
                   "B": ["b0", "b1", "b2", "b1", "b1", "b0", "b2", "b2", "b0"]})
N, EPS, DELTA = 30, 1.0, 1e-5
schema = dpsynth.Schema({"A": dpsynth.CategoricalAttribute(possible_values=["a0", "a1", "a2"]),
                         "B": dpsynth.CategoricalAttribute(possible_values=["b0", "b1", "b2"])})
mech = dpsynth.calibrate(dpsynth.TabularConfig(discrete_mechanism=dpsynth.discrete_mechanisms.MSTConfig(pgm_iters=20)),
                         schema, epsilon=EPS, delta=DELTA)

hits = {}
for name, data in (("D", D), ("D'", D2)):
  hits[name] = 0
  for seed in range(N):
    with tempfile.TemporaryDirectory() as d, dpsynth.checkpoint(d):
      mech(np.random.default_rng(seed), data)
      result = mech(np.random.default_rng(seed), data)
    cols = result.codec.columns
    [m] = [m for m in result.discrete_mechanism_result.measurements if len(m.clique) == 2]
    matches = {}
    for hypothesis, h in (("D", D), ("D'", D2)):
      y = np.concatenate([(cols[c].column_measurement.noisy_counts
                           - h[c].value_counts().reindex(schema[c].possible_values, fill_value=0).to_numpy())
                          / cols[c].column_measurement.stddev for c in "AB"])
      two_way = pd.crosstab(h[m.clique[0]], h[m.clique[1]]).reindex(
          index=schema[m.clique[0]].possible_values, columns=schema[m.clique[1]].possible_values, fill_value=0)
      w = (np.asarray(m.noisy_measurement) - two_way.to_numpy().ravel()) / m.stddev
      matches[hypothesis] = int(sum(np.min(np.abs(y - x)) < 1e-6 for x in w))
    hits[name] += matches["D'"] > matches["D"]
    print(f"{name}, seed {seed}: matching residuals {matches}")

p, p2 = hits["D"] / N, hits["D'"] / N
print(f"P_D[E] = {p:.3f}, P_D'[E] = {p2:.3f}; ({EPS}, {DELTA})-DP allows P_D'[E] <= e^eps * P_D[E] + delta = "
      f"{math.exp(EPS) * p + DELTA:.3f}")

This prints:

D', seed 29: matching residuals {'D': 2, "D'": 5}
P_D[E] = 0.000, P_D'[E] = 1.000; (1.0, 1e-05)-DP allows P_D'[E] <= e^eps * P_D[E] + delta = 0.000

One option would be to save the RNG state as part of the checkpoint; thought this might still fail if the first algorithm crashes at the wrong time. In general, checkpoints and seeds seem like "dangerous" API options, and even more so when they interact. Maybe the API should only allow users to pass a seed as part of a mechanism, and clearly mark that option as "privacy-unsafe", instead of allowing the user to pass a full RNG?

This also affects AIM.