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

Aperta
  • Qualcosa non va?
#287 0 commenti 0 reazioni 0 assegnatari Vedi su GitHub

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
5/5
Tempo stimato
Più di una settimana
Idoneità per principianti
35/100
Tipo di issue
Bug
Chiarezza
Abbastanza chiara
Stato di attività
Attiva
Stack tecnologico
numpy, pandas, python
Ambito
machine-learning, security

Direzione di ricerca

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.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

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.

Lingua principale
Python
Stelle
32
Fork
13
Nessuna PR unita negli ultimi 30g

Preparare l'ambiente

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di google/dpsynth

Tutte le issue di google/dpsynth

Issue simili

Altre issue su Python

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.