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

Abierto
  • ¿Algo no está bien?
#287 0 comentarios 0 reacciones 0 asignados Ver en GitHub

Nadie ha tomado este issue todavía.

Evaluación

Dificultad
5/5
Tiempo estimado
Más de una semana
Aptitud para principiantes
35/100
Tipo de issue
Error
Claridad
Bastante claro
Estado de actividad
Activo
Stack tecnológico
numpy, pandas, python
Área
machine-learning, security

Línea de trabajo

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.

Escrito por el modelo de indexación a partir del texto del issue.

Descripción

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.

Lenguaje dominante
Python
Estrellas
32
Forks
13
Sin PR fusionados en 30 d

Preparar el entorno

Primeros pasos

  1. Lee el issue completo y luego la guía de contribución del proyecto.
  2. Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
  3. Haz un fork del repositorio y trabaja en una rama.
  4. Abre un pull request que haga referencia al número del issue.

Más de google/dpsynth

Todos los issues de google/dpsynth

Issues similares

Más issues de Python

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.