Spatial Epi Public Health GIS

Detecting Differencing Attacks Across Published Tables

This guide, part of Disclosure Review & Release Governance, implements the check that catches the most common way suppressed counts leak: subtraction between tables that are safe on their own.

Problem Context & Constraints

A differencing attack needs no special skill. If one table reports 42 cases in a county and another reports 39 cases in a health district that covers the county minus one small town, the town has 3 cases, even though no table shows a 3. The same arithmetic works across time (a year-to-date count published on 30 June and 1 July differs by the cases on 1 July), across strata (all ages minus ages 0–64 gives ages 65 and over), and across revisions (a revised table minus the original gives the late-reported cases).

Spatial releases are especially exposed because health programs publish at many overlapping geographies: counties, ZIP Code Tabulation Areas, tracts, health districts, hospital service areas, legislative districts. These nest imperfectly. A ZIP code crosses county lines; a district boundary follows neither. Every pair of geographies that partially overlaps creates slivers — the pieces of one that fall inside or outside the other — and each sliver’s count may be recoverable.

Detection works on atoms: the smallest pieces formed by overlaying every published geography. Each published cell is a sum of atoms. A differencing attack succeeds when some combination of published cells, added and subtracted, isolates an atom or a small group of atoms whose count is below the threshold. The check builds the atom system and searches for such combinations.

Overlapping Geographies Create Atoms On the left, a county and a ZIP code tabulation area overlap partially. On the right, their overlay forms three atoms: the part of the county outside the ZIP area, the part inside both, and the part of the ZIP area outside the county. The county count equals the first two atoms and the ZIP count equals the last two. If a third published table covers one of those combinations, the count of a small atom can be recovered by subtraction. Every published cell is a sum of atoms County ZIP → atom 1 atom 2 atom 3 county = atoms 1 + 2; ZIP = atoms 2 + 3 a third table covering atoms 1 + 2 + 3 would expose atom 2 and each remainder

Prerequisites

  • python 3.11
  • numpy 1.26.4, pandas 2.2.2, geopandas 0.14.4, scipy 1.13.1
  • Boundaries for every geography published for the measure, or block-level crosswalks between them
  • Unsuppressed counts at the atom level, inside the secure environment
  • The release register listing which cells have been or will be published, and which are suppressed
  • The small-cell threshold from the program’s policy file

Step-by-Step Solution

Build atoms from blocks, express every published cell as a row of an incidence matrix over atoms, find atom groups whose counts are determined by published cells, and flag determined groups with small counts.

# Find small counts recoverable by adding and subtracting published cells.
# Pinned: numpy==1.26.4, pandas==2.2.2, geopandas==0.14.4, scipy==1.13.1
import logging

import numpy as np
import pandas as pd
from scipy.linalg import null_space

logging.basicConfig(level=logging.INFO, format="%(asctime)s %(levelname)s %(message)s")
log = logging.getLogger("differencing")


def build_atoms(block_xwalk: pd.DataFrame, geo_cols: list[str]) -> pd.DataFrame:
    """block_xwalk: one row per census block with its id in every published geography.
    Atoms are unique combinations of those ids."""
    atoms = block_xwalk.groupby(geo_cols, dropna=False).size().reset_index(name="n_blocks")
    atoms["atom_id"] = np.arange(len(atoms))
    return atoms


def incidence(atoms: pd.DataFrame, published: pd.DataFrame) -> tuple[np.ndarray, list]:
    """published: rows (geo_col, geo_id) for every cell shown unsuppressed."""
    rows, labels = [], []
    for geo_col, geo_id in published[["geo_col", "geo_id"]].itertuples(index=False):
        rows.append((atoms[geo_col] == geo_id).to_numpy(dtype=float))
        labels.append(f"{geo_col}={geo_id}")
    return np.vstack(rows), labels


def determined_atoms(A: np.ndarray, tol: float = 1e-9) -> np.ndarray:
    """An atom's count is determined by published cells iff its unit vector lies in
    the row space of A, i.e. it is orthogonal to the null space of A."""
    N = null_space(A)
    if N.size == 0:
        return np.ones(A.shape[1], dtype=bool)
    return np.all(np.abs(N) < tol, axis=1)


def check(block_xwalk, geo_cols, published, atom_counts: pd.Series, k: int) -> pd.DataFrame:
    atoms = build_atoms(block_xwalk, geo_cols)
    A, labels = incidence(atoms, published)
    det = determined_atoms(A)
    atoms["count"] = atom_counts.reindex(atoms.set_index(geo_cols).index).to_numpy()
    atoms["determined"] = det
    risky = atoms[det & (atoms["count"] > 0) & (atoms["count"] < k)]
    log.info("atoms=%d published_cells=%d determined=%d risky=%d",
             len(atoms), len(labels), int(det.sum()), len(risky))
    return risky

The null-space test is the core. Published cells give a system of linear equations whose unknowns are atom counts. An atom’s count is fully recoverable exactly when its indicator vector can be written as a combination of published rows, which is equivalent to every null-space vector having a zero in that atom’s position. The same test applied to sums of atoms — any small group that shares an identifying feature — extends the check to groups rather than single atoms.

This finds exact recovery. Attackers can also bound a count using non-negativity: if published cells imply an atom has between 0 and 4 cases, that may be disclosive even though the exact value is unknown. For those cases, solve two small linear programs per atom — minimise and maximise its count subject to the published totals and non-negativity — and flag atoms whose upper bound falls below the threshold. The linear programs are small and fast with any standard solver, and they catch the attacks that the exact test misses, such as a sliver whose count is not fixed but is squeezed into a narrow range by several overlapping totals.

Three Ways Tables Difference Three boxes. Geographic differencing subtracts overlapping areas, such as a county minus a district, to reveal a sliver. Temporal differencing subtracts cumulative counts published on consecutive dates, revealing the cases in the interval. Stratum differencing subtracts a published subgroup from a total, such as all ages minus under sixty-five, revealing the remaining group. The same atom method handles all three by treating time slices and strata as additional dimensions of the atom. Space, time and strata are all dimensions of an atom Geographic county − district = small town Temporal YTD 1 July − YTD 30 June = cases on 1 July Stratum all ages − under 65 = 65 and over add time slice and stratum to the atom key to check all three at once

Validation & Edge Cases

Scale. Overlaying five geographies for a state can produce tens of thousands of atoms, and the null space of a large matrix is expensive. Partition the problem: atoms in different counties interact only through geographies that span counties, so solve per connected component of the overlap graph.

Blocks as the finest unit. Atoms built from blocks assume every published geography is an exact union of blocks. ZIP Code Tabulation Areas and census geographies are; health districts and hospital service areas usually are too, if defined from blocks or tracts. A geography defined by a hand-drawn boundary must first be assigned to blocks.

Suppressed cells. Suppressed cells are not in the published matrix, which is the point, but complementary suppression must be applied consistently across all tables. A cell suppressed in one table and shown in another is simply published.

Revisions. Include earlier versions of a revised table as separate published rows over a time dimension reflecting the reporting date. Their difference is late-reported cases, often few.

Future releases. Run the check on the planned release schedule, not only what has been published, so a table that is safe today does not become unsafe when next month’s is added. Where the schedule creates risk, change the schedule: publish cumulative counts less often, or at coarser geography.

Other agencies’ tables. A county that publishes its own ZIP code counts, or a hospital that publishes its service-area figures, adds rows to the attacker’s matrix that the state never released. Where such tables are known, add them to the published set for the check even though the state does not control them; the arithmetic does not care who published a cell. Where they are not known, treat determined atoms near the threshold with extra caution.

Fixing a failure. When a risky atom is found, options include suppressing an additional published cell that breaks the determining combination, publishing one of the geographies at a coarser level, or rounding or perturbing the counts. Choose the fix that loses the least information and re-run the check, since a fix can create new determined atoms elsewhere.

Zero counts. A determined atom with zero cases is usually excluded from the risky list, but a published zero can still disclose — that nobody in a small facility or community has a condition may itself be sensitive. Decide under the program’s policy whether determined zeros are acceptable, and apply the rule consistently.

INFO differencing atoms=18342 published_cells=4127 determined=6211 risky=14
INFO differencing risky atoms by source: geographic=9 temporal=4 stratum=1
Fixing a Recoverable Count A risky atom leads to three fix options: suppress one more published cell to break the combination that determines it, publish one of the overlapping geographies at a coarser level, or round or perturb the affected counts. Whichever fix is chosen, the check is run again, because a fix can make other atoms determined. The loop ends when no risky atoms remain. Fix, then check again Risky atom count < k, determined suppress one more cell coarsen a geography round or perturb Re-run check fixes can shift risk Release choose the fix that loses least information

Compliance Notes

Record the geographies, time slices and strata included, the atom count, the threshold, the risky atoms found, the fix applied to each and the re-check result. Store the check output with the release’s decision record.

The atom-level counts and the list of risky atoms are themselves disclosive — they point directly at small populations with small counts. Keep them inside the secure environment, and describe findings in the decision record by category and number rather than by location.