Spatial Privacy & Anonymization Engineering

Gating Releases on a Re-identification Risk Budget

A risk budget is a ceiling on the estimated re-identification probability that a release may carry, enforced per zone rather than pooled, and re-evaluated on a schedule because the estimate moves when new auxiliary data is published. It is the gate that catches what a threshold check cannot: a release that satisfies every parameter and is still identifying.

Core Calculation permalink

Let ρ^z\widehat{\rho}_z be the estimated re-identification probability in zone zz, produced by the re-identification risk assessment. The release-level figure is the worst zone, never the record-weighted mean:

ρ^release=max⁡zρ^z\widehat{\rho}_{\text{release}} = \max_{z} \widehat{\rho}_z

The gate is ρ^release≤ρmax⁡\widehat{\rho}_{\text{release}} \le \rho_{\max}.

Across a programme of repeated releases the exposures accumulate. Under an independence approximation the probability that a target is singled out by at least one of nn releases is

ρ^cum=1−∏i=1n(1−ρ^i)\widehat{\rho}_{\text{cum}} = 1 - \prod_{i=1}^{n} \bigl(1 - \widehat{\rho}_i\bigr)

which is close to ∑iρ^i\sum_i \widehat{\rho}_i while the individual figures are small. The programme budget bounds this cumulative quantity, so a monthly series at ρ^=0.02\widehat{\rho} = 0.02 exhausts a 0.20 annual ceiling in eleven months and not, as teams routinely assume, never.

Worked numeric example permalink

A quarterly mobility release, ρmax⁡=0.05\rho_{\max} = 0.05 per release and 0.20 cumulative per year.

Quarter Worst-zone ρ^\widehat{\rho} Pooled ρ^\widehat{\rho} Cumulative Verdict
Q1 0.031 0.004 0.031 publish
Q2 0.044 0.005 0.074 publish
Q3 0.049 0.006 0.119 publish, warn
Q4 0.052 0.006 — blocked

Two things are worth noticing. The pooled figure never exceeds 0.006 and would have waved every quarter through, including the one that breaches. And the cumulative column reaches 0.119 by Q3, so even if Q4 had come in at 0.04 the programme would have been at 0.155 — inside the ceiling but close enough that the following year’s plan needed revisiting before it was made.

Python Implementation permalink

from __future__ import annotations

import pandas as pd

class RiskBudgetExceeded(RuntimeError):
    """Raised in the publish job — never caught, never downgraded to a warning."""

def gate_on_risk_budget(
    per_zone_risk: pd.DataFrame,
    ledger: pd.DataFrame,
    dataset: str,
    per_release_ceiling: float,
    cumulative_ceiling: float,
    warn_at: float = 0.75,
) -> dict:
    """Block a release whose worst zone, or whose programme total, breaches budget.

    Args:
        per_zone_risk: columns `zone_id`, `p_reid`, `n_records`.
        ledger: prior releases with columns `dataset`, `p_reid`.
        per_release_ceiling: max acceptable worst-zone probability for one release.
        cumulative_ceiling: max acceptable probability of being singled out by any
            release in the programme.
        warn_at: fraction of the cumulative ceiling that triggers a warning.

    Raises:
        RiskBudgetExceeded: if either ceiling would be breached.
    """
    if per_zone_risk.empty:
        raise RiskBudgetExceeded("no per-zone risk estimate — the gate cannot pass")

    worst_row = per_zone_risk.loc[per_zone_risk["p_reid"].idxmax()]
    worst = float(worst_row["p_reid"])
    pooled = float((per_zone_risk["p_reid"] * per_zone_risk["n_records"]).sum()
                   / per_zone_risk["n_records"].sum())

    if worst > per_release_ceiling:
        raise RiskBudgetExceeded(
            f"zone {worst_row['zone_id']} at {worst:.3f} exceeds the per-release "
            f"ceiling of {per_release_ceiling:.3f} (pooled was {pooled:.4f})"
        )

    prior = ledger.loc[ledger["dataset"] == dataset, "p_reid"].tolist()
    cumulative = 1.0 - float(pd.Series(prior + [worst]).rsub(1.0).prod())
    if cumulative > cumulative_ceiling:
        raise RiskBudgetExceeded(
            f"{dataset}: cumulative {cumulative:.3f} would exceed the programme "
            f"ceiling of {cumulative_ceiling:.3f} after {len(prior)} prior releases"
        )

    return {
        "worst_zone": str(worst_row["zone_id"]),
        "worst_p_reid": worst,
        "pooled_p_reid": pooled,
        "cumulative_p_reid": cumulative,
        "headroom": cumulative_ceiling - cumulative,
        "warning": cumulative > warn_at * cumulative_ceiling,
    }

Verification permalink

def test_control_gate_blocks_a_breaching_zone():
    """Without this the gate and a disconnected gate look identical."""
    risk = pd.DataFrame({"zone_id": ["a", "b"], "p_reid": [0.01, 0.31],
                         "n_records": [900_000, 1_200]})
    try:
        gate_on_risk_budget(risk, pd.DataFrame({"dataset": [], "p_reid": []}),
                            "d", per_release_ceiling=0.05, cumulative_ceiling=0.2)
    except RiskBudgetExceeded:
        return
    raise AssertionError("the risk gate published a zone at 0.31")

Note the shape of the fixture: zone b holds a thousandth of the records and carries thirty times the risk. That is the realistic case — sparse peripheries are both small and identifying — and a gate tested only on balanced data will not exercise it.

The scheduled job is the second half of the verification and cannot live in the pipeline, because its input is the outside world. It re-runs the estimate against the current auxiliary landscape and opens a ticket when a published release crosses the ceiling it was published under.

Edge Cases & Adjustments permalink

  • Zones with very few records. A zone of three people has a high estimated risk and a wide confidence interval. Report the interval and gate on its lower bound if you want to avoid blocking on noise — but state which you used, because the two give different answers.
  • The independence approximation. Successive releases of the same population are correlated, so the product formula understates the cumulative figure. It is the conventional approximation; where the correlation is strong, prefer a direct simulation over the joint release set.
  • A missing estimate. The implementation raises rather than passing when per_zone_risk is empty. A gate that treats missing evidence as a pass is worse than no gate.
  • Withdrawal. When the scheduled re-run finds a published release over its ceiling, the options are withdrawal, re-publication at a coarser geometry, or a documented acceptance. Decide the policy before the situation arises, not during it.
  • Zone definition. The zones must be ones an adversary could also define — density strata, administrative units. Zones defined by a private property of the data leak that property.

Defining the Zones permalink

The gate’s verdict depends entirely on how the study area is partitioned, and two rules keep the partition defensible.

The zones must be ones the adversary could also define. Density strata, administrative units and published land-use classes all qualify, because an attacker can construct them from public data. A partition derived from a private property of the dataset — say, the clusters a model found — does not: reporting risk per such zone leaks the partition, and an attacker who cannot reconstruct it is not the attacker the estimate describes.

The zones must be stable across releases. A partition recomputed per release makes the cumulative figure meaningless, because each release’s worst zone refers to a different set of people. Fix the zones when the programme starts and version them with the policy file.

FAQ permalink

Why gate on the worst zone rather than the mean?

Because re-identification happens to individuals, and the individuals at risk are concentrated in the sparse zones that contribute almost nothing to a record-weighted average. The decomposition on the risk assessment page shows the size of the gap.

How is this different from an ε budget?

An ε budget bounds what any mechanism could leak, by construction, and is exact. A risk budget bounds an estimate against a stated adversary model, and the estimate moves when the model or the auxiliary landscape changes. Use ε where the release is differentially private and a risk budget where it is not — the distinction drawn in masking vs. differential privacy technique selection.

What ceiling should we set?

The same number the organisation’s disclosure policy already implies. If the policy sets k=20k = 20 for published cells, it has already accepted 0.05, and using a different figure here means one of the two is wrong.

Can the gate be overridden?

Only by changing the policy file with a review, which leaves a diff. An override flag in the job is a gate that has already been removed.

← Back to Automating Spatial Privacy Checks in CI

Related topics

Writing pytest Assertions for k-Anonymity Guarantees

A pytest module that enforces a k floor over distinct individuals, checks the suppression is complete, and pairs every...