Preserving Topology When Fuzzing Points Near Boundaries

Unconstrained fuzzing moves a household across a district line, a patient into the sea, or an incident to the wrong side of a motorway. Constraining it fixes the map and creates a subtler problem: the constraint is a function of the true location, so a point that can only have come from one place has been told on.

Core Calculation # permalink

Let $M(x)$ be the unconstrained fuzzing kernel — usually uniform on a disc of radius $R$, or a planar Laplace — and $A(x)$ the admissible region for the point at $x$ (its district, minus water, minus the far side of a barrier). Constrained fuzzing draws from the restricted kernel:

The denominator is the acceptance mass:

for the uniform-disc case. This is the number to watch. When $\alpha(x)$ is small, almost all the probability mass has been cut away and the surviving mass is concentrated in a sliver whose shape names the original point’s position relative to the boundary.

The privacy loss the constraint introduces, relative to the unconstrained mechanism, is bounded by

so an acceptance mass of 0.5 costs 0.69 nats, 0.2 costs 1.6, and 0.05 costs 3.0 — which is more than most releases spend on the mechanism itself.

Worked numeric example # permalink

Fuzz radius $R = 500$ m, uniform disc, a coastal city.

The pier point is the whole problem in one row. It has an $\varepsilon$-equivalent cost of 2.81 nats on top of whatever the fuzzing was supposed to provide, and every released neighbour of it is in the same 47 100 m² sliver — which is the pier and its immediate approach. The mechanism moved the point and disclosed the pier.

The disposal is not a better sampler. It is to detect $\alpha(x) < \alpha_{\min}$ and fall back: generalise that point to the containing unit, or suppress it under the outlier policy. A common floor is $\alpha_{\min} = 0.25$, costing at most 1.39 nats.

Python Implementation # permalink

from __future__ import annotations

import math

import numpy as np
from shapely.geometry import Point, Polygon
from shapely.strtree import STRtree


class TopologyPreservingFuzzer:
    """Displace points within R while keeping them topologically valid.

    Acceptance mass is measured, not assumed: a point whose admissible region
    is a narrow sliver has been disclosed by the constraint, and no amount of
    correct sampling from that sliver undoes it.
    """

    def __init__(self, units: list[Polygon], exclusions: list[Polygon],
                 radius: float = 500.0, alpha_min: float = 0.25,
                 max_attempts: int = 200):
        self.units = units
        self.unit_index = STRtree(units)
        self.exclusions = exclusions
        self.exclusion_index = STRtree(exclusions) if exclusions else None
        self.radius = radius
        self.alpha_min = alpha_min
        self.max_attempts = max_attempts

    def admissible(self, x: float, y: float) -> Polygon:
        """Intersection of the fuzz disc, the containing unit, and non-excluded land."""
        disc = Point(x, y).buffer(self.radius, quad_segs=32)
        containing = [self.units[i] for i in self.unit_index.query(Point(x, y))
                      if self.units[i].contains(Point(x, y))]
        region = disc if not containing else disc.intersection(containing[0])
        if self.exclusion_index is not None:
            for i in self.exclusion_index.query(region):
                region = region.difference(self.exclusions[i])
        return region

    def acceptance_mass(self, x: float, y: float) -> float:
        """Fraction of the unconstrained kernel that survives the constraint."""
        region = self.admissible(x, y)
        if region.is_empty:
            return 0.0
        return float(region.area / (math.pi * self.radius ** 2))

    def fuzz(self, x: float, y: float,
             rng: np.random.Generator | None = None) -> dict:
        """Return a displaced point, or a fallback disposal when α is too small."""
        rng = rng or np.random.default_rng()
        alpha = self.acceptance_mass(x, y)

        if alpha < self.alpha_min:
            # The constraint has concentrated the output; releasing a point
            # here reveals the sliver, so hand it to the coarser disposal.
            return {"disposal": "generalise", "alpha": alpha,
                    "cost_nats": math.inf if alpha == 0 else math.log(1 / alpha)}

        region = self.admissible(x, y)
        for _ in range(self.max_attempts):
            # Area-uniform on the disc: sqrt keeps the density flat, and
            # omitting it clusters draws toward the true point.
            theta = rng.uniform(0, 2 * math.pi)
            r = self.radius * math.sqrt(rng.uniform(0, 1))
            cand = Point(x + r * math.cos(theta), y + r * math.sin(theta))
            if region.contains(cand):
                return {"disposal": "fuzz", "x": cand.x, "y": cand.y,
                        "alpha": alpha, "cost_nats": math.log(1 / alpha)}

        return {"disposal": "generalise", "alpha": alpha,
                "cost_nats": math.log(1 / alpha)}

The math.sqrt in the radius draw is the detail that most implementations get wrong. Sampling $r$ uniformly on $[0, R]$ gives a density proportional to $1/r$, concentrating draws near the true point — which halves the effective displacement and does so invisibly.

Verification # permalink

Topology is preserved for every point. The assertion the whole exercise exists for:

def check_topology(original: np.ndarray, released: np.ndarray,
                   unit_of: callable, exclusions: list[Polygon]) -> dict:
    """Every released point stays in its unit and off every exclusion."""
    moved_unit = [i for i, (o, r) in enumerate(zip(original, released))
                  if unit_of(*o) != unit_of(*r)]
    in_exclusion = [i for i, r in enumerate(released)
                    if any(e.contains(Point(*r)) for e in exclusions)]
    return {
        "unit_changes": moved_unit,
        "in_exclusion": in_exclusion,
        "passes": not moved_unit and not in_exclusion,
    }

The acceptance-mass distribution has no long tail. Plot $\alpha$ across the whole dataset. A distribution concentrated near 1 with a handful of points below 0.25 is healthy; a fat tail below 0.25 means the fuzz radius is too large for the geography and should come down, because falling back on 8 % of points is a coverage problem, not an edge case.

Displacement matches the theoretical distribution. Test the fuzzer’s output against the expected radial CDF, which for the area-uniform disc is $F(r) = (r/R)^2$:

from scipy.stats import kstest

def check_displacement(orig: np.ndarray, rel: np.ndarray, radius: float) -> dict:
    d = np.linalg.norm(rel - orig, axis=1)
    # Only interior points should match the unconstrained law; constrained
    # ones are deliberately non-uniform and would fail this by design.
    stat, p = kstest(d / radius, lambda r: np.clip(r, 0, 1) ** 2)
    return {"ks_stat": float(stat), "p_value": float(p),
            "median_m": float(np.median(d)),
            "expected_median_m": radius * math.sqrt(0.5),
            "passes": p > 0.01}

Run the KS test on interior points only. Constrained points are supposed to deviate, and pooling them turns a real check into a guaranteed failure that people then disable.

Edge Cases & Adjustments # permalink

• Points on the boundary itself. A point exactly on a district line has no unambiguous containing unit, and the choice of unit becomes a coin flip that a determined adversary can exploit across repeated releases. Snap boundary points to a unit deterministically — by a keyed hash of the record id, not by geometry — and keep the assignment stable across releases.
• Enclaves and multipart units. A district with a detached exclave gives an admissible region in two disconnected pieces. Sampling proportionally to area is correct; sampling uniformly across pieces is not, and it produces a visible over-representation in the small piece.
• Barriers that are not polygons. A motorway or a river is a line, and “the far side” is only meaningful with respect to travel. If the release is about accessibility, cut the admissible region by the barrier; if it is about density, do not — the barrier is not a privacy boundary.
• Repeated fuzzing of the same point. Independent draws across releases average out to the true location. Fix one displacement per subject per epoch and reuse it, exactly as with pseudonym rotation.
• Cost accounting. The $\ln(1/\alpha)$ term is a genuine privacy cost and belongs in the release ledger if the release makes a differential-privacy claim. Charging only the nominal mechanism epsilon understates the loss for every constrained point.

FAQ # permalink

Why not just re-draw until the point lands somewhere valid?

That is exactly what the sampler does, and it is correct — rejection sampling from a restricted kernel gives the right distribution. The problem is not the sampler; it is that the restricted distribution is informative when the restriction is severe.

Is $\alpha_{\min} = 0.25$ a standard?

No, it is a defensible starting point costing at most 1.39 nats. Set it from your privacy budget: if the mechanism spends $\varepsilon = 1$, a constraint costing 1.39 more than doubles the loss and the floor should be higher.

What if a point’s admissible region is empty?

Then the point cannot be fuzzed at all under the constraints — usually an offshore or out-of-boundary coordinate, which is a data-quality problem. Route it to suppression and log it; do not silently release it unfuzzed.

Does this apply to planar Laplace too?

Yes, with the integral computed over the Laplace kernel rather than the disc. The acceptance mass is smaller for the same visible radius because the Laplace has unbounded support, so check it numerically rather than reusing the disc’s area ratio.

Related # permalink

• Spatial Fuzzing & Buffer Zone Implementation — the unconstrained mechanism
• Testing Jitter Quality with Displacement Distribution Checks — the KS check in full
• Handling Outliers That Break Spatial K-Anonymity — where the fallback points go
• Geo-indistinguishability & Planar Laplace — the kernel with a formal guarantee
• Tracking Epsilon Spend in a Release Ledger — recording the constraint cost

← Back to Spatial Fuzzing & Buffer Zone Implementation