Privacy risk of trajectories

Question. If an attacker knows a few places a person has visited, how likely are they to find that person's trajectory in a published dataset?

You will get a re-identification risk for each person under eight kinds of attacker knowledge (visited places, how often, in what order, at what time, home and work), and a sweep showing how coarser location data lowers the risk.

Prerequisites. Measure individual mobility.

Data. Brightkite check-ins (Stanford SNAP, 2008 to 2010): the first 300,000 rows (about 4 MB of the 60 MB file) with fastmob.data.load_brightkite; we keep the first 80 users who have between 100 and 300 check-ins, to keep the run short (about 16,000 check-ins). The notebook stops if the download fails.

%pip install -q 'fastmob>=0.3.4' pandas matplotlib

Load a small sample

Risk is computed against the other people in the dataset, so a small sample is a small crowd: the same attack is easier against 80 people than against 80,000. Keep that in mind when reading the numbers.

import pandas as pd
from fastmob import privacy
from fastmob.data import load_brightkite

raw = load_brightkite(max_rows=300_000).to_pandas()

raw = raw[~(((raw["lat"] == 0) & (raw["lng"] == 0)) | (raw["lat"].abs() >= 90))]
counts = raw.groupby("uid").size()
sample_users = counts[(counts >= 100) & (counts <= 300)].index[:80]
checkins = (
    raw[raw["uid"].isin(sample_users)]
    .sort_values(["uid", "datetime"])
    .reset_index(drop=True)
)
print(len(checkins), "check-ins by", checkins["uid"].nunique(), "users")

15827 check-ins by 80 users

Risk from places the attacker knows

location_risk assumes the attacker knows knowledge_length places the person visited (enumerated over visit records, see below). Places are H3 cells; h3_resolution sets how precise a place is: 3 is a cell about 12,000 km² wide, 9 about 0.1 km². The risk of a person is the probability, between 0 and 1, that this knowledge identifies them: 1 means some set of that many places in their history matches nobody else's. The default reports each person's highest risk over all possible knowledge sets. First we vary the precision.

by_resolution = {}
for resolution in (1, 2, 3, 4, 6, 9):
    risk = privacy.location_risk(checkins, knowledge_length=1, h3_resolution=resolution)
    by_resolution[resolution] = {
        "mean risk": risk["risk"].mean(),
        "share at risk 1": (risk["risk"] == 1).mean(),
    }

pd.DataFrame(by_resolution).T.round(2)

Knowing one place identifies a quarter of the 80 people for certain (24% have risk 1; mean risk 0.35) when places are cells of over 600,000 km² (resolution 1), and everybody once places are about 36 km² wide or finer (resolution 6 and above: risk 1.00 for every user). Each step to finer cells makes the attack stronger; this is why releasing coarse locations is a common mitigation.

Every instance, not just the worst

With force_instances=True the function returns one row for every set of known places (an instance) with its probability prob, instead of only the worst case. This is useful to see how the risk is distributed over the possible attacks. The maximum over instances is the default risk.

worst = privacy.location_risk(checkins, knowledge_length=1, h3_resolution=2)
instances = privacy.location_risk(
    checkins, knowledge_length=1, h3_resolution=2, force_instances=True
)

check = instances.groupby("uid")["prob"].max().reset_index().merge(worst, on="uid")
print(
    len(instances),
    "instances; maximum probability equals the default risk for every user:",
    bool((check["prob"] - check["risk"]).abs().max() < 1e-9),
)
instances.head()

15827 instances; maximum probability equals the default risk for every user: True

Instances are enumerated over the visit records of each person: there are 15,827, as many as check-ins, so a place visited several times appears several times (unique_location_risk enumerates distinct places instead). Each has the probability of finding the person from that place alone: for user 103 it is about 0.05 to 0.06, one chance in 18 or 22, because many of the other users also visited those cells at this coarse resolution. The largest of these probabilities is the default risk, as the check confirms for all users.

Other attacker models

Each function models a different kind of background knowledge, all at resolution 3 (cells about 12,000 km² wide):

• unique_location_risk: the same attack with distinct places. A place visited ten times counts once, and with one known place the risk equals that of location_risk; the two differ for two or more places and in the number of instances.
• location_frequency_risk, location_probability_risk, location_proportion_risk: the places together with how often (a count), how likely (a probability) or the visits to each place as a proportion of the visits to the person's most visited place; tolerance allows the attacker's number to be off by that fraction.
• location_sequence_risk: places in the order visited (here two consecutive places).
• location_time_risk: places and when they were visited, to a time_precision such as Hour or Day.
• home_work_risk: the two most frequently visited places.

mean_risk = {
    "location_risk (1 place)": privacy.location_risk(
        checkins, knowledge_length=1, h3_resolution=3
    ),
    "unique_location_risk (1)": privacy.unique_location_risk(
        checkins, knowledge_length=1, h3_resolution=3
    ),
    "location_frequency_risk (1)": privacy.location_frequency_risk(
        checkins, knowledge_length=1, h3_resolution=3
    ),
    "location_probability_risk (1)": privacy.location_probability_risk(
        checkins, knowledge_length=1, h3_resolution=3
    ),
    "location_proportion_risk (1, tolerance 0.1)": privacy.location_proportion_risk(
        checkins, knowledge_length=1, tolerance=0.1, h3_resolution=3
    ),
    "location_sequence_risk (2 in order)": privacy.location_sequence_risk(
        checkins, knowledge_length=2, h3_resolution=3
    ),
    "location_time_risk (1, day)": privacy.location_time_risk(
        checkins, knowledge_length=1, time_precision="Day", h3_resolution=3
    ),
    "home_work_risk": privacy.home_work_risk(checkins, h3_resolution=3),
}

pd.DataFrame(
    {
        name: {
            "mean risk": r["risk"].mean(),
            "share at risk 1": (r["risk"] == 1).mean(),
        }
        for name, r in mean_risk.items()
    }
).T.round(2)

At the same coarse resolution, knowing which place a person visited (location_risk, unique_location_risk) identifies 70% of them for sure (mean risk 0.81). Adding how often they went there (location_frequency_risk, location_probability_risk) or when (location_time_risk with day precision) identifies everyone, and the two most visited places alone (home_work_risk) identify 99%. A tolerance of 0.1 on the visit share (location_proportion_risk) is as strong as knowing the place alone, here. Knowing two places in order raises the risk to 0.96. The more detail an attacker has, the higher the risk.

Interpretation and limits

• Risk is relative to the crowd in the data. With 80 people almost any two or three places single someone out; a city of millions is much safer. State the population size.
• These are upper bounds in one sense and lower bounds in another: the default risk is the worst case over the attacker's possible knowledge sets (high), but the attacker is assumed to know places that are exactly in the data (low), without error and without side information.
• Coarsening locations lowers risk but also destroys information; check the effect on your analysis before choosing a resolution.
• The sample is the first 80 users, by user id, who have 100 to 300 check-ins: it is not random, and these users are not typical.
• The default h3_resolution is 12 (about 10 m). At that precision every user in this sample has a risk of 1, so pass a coarser resolution when you want a risk that varies.
• Brightkite check-ins are sparse, so histories are short; GPS data are far more identifying.

Next steps

• Check generated trajectories the same way: Generate mobility with models.
• Understand the places behind the numbers: Measure individual mobility.

Related API

location_risk · location_sequence_risk · location_time_risk · unique_location_risk · location_frequency_risk · location_probability_risk · location_proportion_risk · home_work_risk