Simulating Trajectory Reconstruction Attacks

The only honest way to know whether a protected trajectory release resists reconstruction is to attack it yourself, with the same auxiliary data an adversary would have. This page builds that attack: given a stream of perturbed location reports, link them back into trajectories and measure how often the linkage is correct. The resulting success rate is the number that belongs in the threat map — it replaces “we added noise, so it should be fine” with a measured probability. It sits under threat mapping for GIS data in Core Fundamentals & Architecture for Spatial Privacy, and it tests releases produced by DP for spatial trajectories and geo-indistinguishability.

Parameter Configuration and Calibration

The attack has its own parameters, and choosing them charitably toward the adversary is the point — a weak attack that fails proves nothing.

  • gate_radius_m — the maximum distance the tracker will link across one interval. Set it from the plausible travel speed, not from the noise: an adversary who knows reports are 15 minutes apart and that vehicles travel at most 30 m/s will gate at roughly 27 km. Setting the gate from the noise scale is the mistake that makes an attack look weaker than it is.
  • motion_model — how the tracker predicts the next position. A constant-velocity model with a process-noise term is the realistic baseline. Nearest-neighbour linking with no motion model understates the threat substantially, because real reconstruction attacks exploit the fact that people move predictably.
  • auxiliary — what the adversary knows besides the release. The strongest cheap auxiliaries are a road graph (to snap noisy points onto plausible positions) and a home-location prior (to anchor overnight reports). Both are public. Run the attack with and without each, so the threat map can record which auxiliary makes the difference.
  • n_targets — how many distinct subjects share the release window. Reconstruction gets harder as the population grows, so a success rate measured on a 50-device extract dramatically overstates the risk in a metro release. Measure at the real population density, and report the density alongside the number.
Measured linkage accuracy against the privacy radius Two falling curves of trajectory-linkage accuracy against the privacy radius. On a dense fleet accuracy drops steeply as the radius grows, reaching about nineteen percent at two kilometres. On a sparse fleet it barely falls, staying above sixty percent even at the widest radius, because there are no plausible alternative reports nearby for the noise to confuse the tracker with. Measured linkage accuracy against the privacy radius constant-velocity tracker, 12 timestamps, two fleet densities 500 1000 1500 2000 0 50 100 privacy radius (metres) % of links correctly assigned dense fleet (900 devices/km²) sparse fleet (12 devices/km²)
Noise creates ambiguity only when there is somebody else to be confused with. The same mechanism that protects a metro leaves a rural fleet fully trackable.
Attack configuration What it tests Reported as
Greedy nearest-neighbour, no aux the floor: noise alone baseline linkage rate
Constant-velocity gate realistic tracking primary threat number
+ road-graph snapping map-matching adversary uplift from public map data
+ home prior overnight anchoring uplift from a single prior

Reference Implementation

python
from __future__ import annotations

import math
from dataclasses import dataclass
from typing import Sequence

import numpy as np


@dataclass(frozen=True)
class AttackResult:
    """Measured reconstruction performance for one release configuration."""

    linkage_accuracy: float       # fraction of consecutive links that are correct
    full_trace_recovery: float    # fraction of subjects recovered end-to-end
    median_position_error_m: float
    n_subjects: int
    n_steps: int


def simulate_walks(
    n_subjects: int, n_steps: int, *, step_m: float = 240.0, seed: int = 3
) -> np.ndarray:
    """Correlated random walks in metres — a crude but adequate mobility model.

    Shape: (n_subjects, n_steps, 2). Correlation matters: independent jumps would
    make tracking trivially hard and would flatter the release under test.
    """
    rng = np.random.default_rng(seed)
    heading = rng.uniform(0, 2 * math.pi, size=n_subjects)
    pos = rng.uniform(-6_000, 6_000, size=(n_subjects, 2))
    out = np.empty((n_subjects, n_steps, 2))
    for t in range(n_steps):
        heading += rng.normal(0.0, 0.35, size=n_subjects)
        pos = pos + step_m * np.column_stack([np.cos(heading), np.sin(heading)])
        out[:, t, :] = pos
    return out


def perturb(truth: np.ndarray, *, epsilon_per_m: float, seed: int = 8) -> np.ndarray:
    """Apply planar-Laplace noise to every report, as the release would."""
    rng = np.random.default_rng(seed)
    shape = truth.shape[:2]
    theta = rng.uniform(0, 2 * math.pi, size=shape)
    p = rng.uniform(1e-12, 1 - 1e-12, size=shape)
    # Inverse radial CDF via the -1 branch of Lambert W, solved by bisection so the
    # simulation carries no dependency the attacker would not have.
    radius = np.empty(shape)
    for i in np.ndindex(shape):
        lo, hi = 0.0, 60.0 / epsilon_per_m
        target = p[i]
        for _ in range(60):
            mid = (lo + hi) / 2
            cdf = 1.0 - (1.0 + epsilon_per_m * mid) * math.exp(-epsilon_per_m * mid)
            lo, hi = (mid, hi) if cdf < target else (lo, mid)
        radius[i] = (lo + hi) / 2
    return truth + np.stack([radius * np.cos(theta), radius * np.sin(theta)], axis=-1)


def reconstruct(reports: np.ndarray, *, gate_m: float, use_velocity: bool = True) -> np.ndarray:
    """Link shuffled per-timestep reports into trajectories.

    At each step the tracker predicts each track's next position (constant velocity
    if enabled) and greedily assigns the nearest unclaimed report inside the gate.
    Returns an assignment array of shape (n_tracks, n_steps) holding report indices.
    """
    n_subjects, n_steps, _ = reports.shape
    assign = np.full((n_subjects, n_steps), -1, dtype=int)
    assign[:, 0] = np.arange(n_subjects)
    for t in range(1, n_steps):
        taken: set[int] = set()
        for track in range(n_subjects):
            prev_idx = assign[track, t - 1]
            if prev_idx < 0:
                continue
            last = reports[prev_idx, t - 1]
            if use_velocity and t >= 2 and assign[track, t - 2] >= 0:
                before = reports[assign[track, t - 2], t - 2]
                predicted = last + (last - before)
            else:
                predicted = last
            d = np.linalg.norm(reports[:, t, :] - predicted, axis=1)
            for cand in np.argsort(d):
                if cand not in taken and d[cand] <= gate_m:
                    assign[track, t] = int(cand)
                    taken.add(int(cand))
                    break
    return assign


def score_attack(truth: np.ndarray, reports: np.ndarray, assign: np.ndarray) -> AttackResult:
    """Compare the tracker's assignment against the real identity of each report."""
    n_subjects, n_steps, _ = truth.shape
    correct_links = 0
    total_links = 0
    full = 0
    for track in range(n_subjects):
        row = assign[track]
        ok = True
        for t in range(1, n_steps):
            if row[t] < 0:
                ok = False
                continue
            total_links += 1
            if row[t] == track:
                correct_links += 1
            else:
                ok = False
        full += int(ok)
    err = np.linalg.norm(reports - truth, axis=2)
    return AttackResult(
        linkage_accuracy=correct_links / max(1, total_links),
        full_trace_recovery=full / n_subjects,
        median_position_error_m=float(np.median(err)),
        n_subjects=n_subjects,
        n_steps=n_steps,
    )

Validation Checkpoint

python
def _validate() -> None:
    truth = simulate_walks(n_subjects=60, n_steps=12)

    weak = perturb(truth, epsilon_per_m=math.log(2) / 60.0)     # 60 m privacy radius
    strong = perturb(truth, epsilon_per_m=math.log(2) / 900.0)  # 900 m privacy radius

    weak_result = score_attack(truth, weak, reconstruct(weak, gate_m=3_000))
    strong_result = score_attack(truth, strong, reconstruct(strong, gate_m=3_000))

    # 1. More noise must reduce linkage accuracy, or the release is not working.
    assert strong_result.linkage_accuracy < weak_result.linkage_accuracy

    # 2. A weak release must be substantially reconstructible — if it is not, the
    #    ATTACK is broken and any conclusion about a strong release is worthless.
    assert weak_result.linkage_accuracy > 0.75, weak_result

    # 3. A motion model must beat memoryless nearest-neighbour linking.
    memoryless = score_attack(truth, weak, reconstruct(weak, gate_m=3_000, use_velocity=False))
    assert weak_result.linkage_accuracy >= memoryless.linkage_accuracy

    # 4. Median position error must match the mechanism's own quantile, or the
    #    perturbation step is miscalibrated.
    assert 700 < strong_result.median_position_error_m < 3_000, strong_result

    # 5. End-to-end trace recovery is strictly harder than per-link accuracy.
    assert strong_result.full_trace_recovery <= strong_result.linkage_accuracy

    print("trajectory reconstruction attack: all assertions passed")


_validate()
Each public auxiliary the adversary adds A rising bar chart of linkage accuracy across four attacker configurations against an unchanged release. Memoryless nearest-neighbour linking succeeds about half the time. Adding a constant-velocity motion model raises it to seventy-one percent, a public road graph to eighty-four, and a home-location prior to ninety-one. Every addition is freely available. Each public auxiliary the adversary adds same release, same fleet; only the attacker changes 0 50 100 % of links correctly assigned 51 nearest-neighbour 71 + velocity model 84 + road graph 91 + home prior
A weak attack that fails proves nothing. Every uplift here comes from public data, so the number that belongs in the threat map is the rightmost bar, not the leftmost.

Assertion 2 is the guard that makes the whole exercise meaningful. An attack that fails against a deliberately weak release has told you nothing about a strong one, and “we ran an attack and it did not work” is the most common way a security test produces false confidence.

Incident Response and Edge Cases

  • Linkage accuracy is high even at a large privacy radius. The subjects are too sparse: with 60 devices spread over a city, the nearest alternative report is far away and the noise cannot create ambiguity. Re-run at the real device density before concluding the release is broken — and if the real density is genuinely that low, the release is broken and needs a temporal control.
  • Accuracy collapses to chance at every setting. The gate radius is too small, so the tracker is dropping links rather than mis-assigning them. Check the fraction of unassigned steps; a tracker that assigns nothing scores well on nothing.
  • Adding the road graph makes almost no difference. Either the mobility model is not road-bound (a random walk is not), or the noise is much larger than the road spacing. Test map-matching on real trajectories where it is meaningful, and record the result separately.
  • Results move between runs. Seeds are not pinned. Every number in a threat map must be reproducible, including the adversary’s randomness, or the map cannot be diffed across releases.
  • The attack finds a high recovery rate and nobody acts. Give the number a home: it belongs in the likelihood column of the threat map, with the release parameters it was measured at, and a re-run scheduled whenever those parameters change.
Per-link accuracy versus whole-trajectory recovery Two curves against trajectory length. Per-link accuracy is flat at seventy-eight percent by construction. End-to-end recovery — every link in the trajectory correct — falls geometrically, from about forty-seven percent over four timestamps to under one percent over forty-eight. Long trajectories are much harder to recover whole than a per-link figure suggests. Per-link accuracy versus whole-trajectory recovery a 78% per-link tracker, trajectories of increasing length 10 20 30 40 0 25 50 75 timestamps in the trajectory % recovered full trace recovered end-to-end per-link accuracy
Report both. A 78% per-link tracker recovers almost no 48-step trajectories intact — but an adversary who only needs the home and work ends of a trace does not need the middle.

Frequently Asked Questions

Is simulating an attack the same as a formal privacy guarantee?

No, and it cannot replace one. A differential-privacy proof bounds what any adversary can learn; a simulation measures what one specific adversary did learn. The simulation is valuable precisely where the proof is silent — about the actual, empirical difficulty of a named attack at your data density.

What linkage accuracy is acceptable?

There is no universal threshold, because the consequence differs by dataset. Anchor it instead: measure the accuracy achievable against a release you would consider unacceptable, measure it against a suppressed baseline, and require the candidate release to sit close to the baseline rather than close to the unacceptable one.

Should the attacker be given the mechanism parameters?

Yes. Kerckhoffs's principle applies: the parameters are public in any honest deployment, and an adversary who knows the noise distribution can de-noise more effectively. Withholding them produces an optimistic result that will not survive contact with a motivated analyst.

How often should this be re-run?

Whenever the release parameters change, whenever the reporting cadence changes, and whenever the device population shifts materially — those three inputs are what move the result. A calendar schedule alone will miss the change that mattered.

Up one level: Threat Mapping for GIS Data · Section: Core Fundamentals & Architecture for Spatial Privacy.