Transcript privacy_gpsCloak

Preserving Privacy in GPS Traces via
Uncertainty-Aware Path Cloaking
by: Baik Hoh, Marco Gruteser, Hui Xiong, Ansaf Alrabady
ACM CCS '07
Presentation: Martin Azizyan
ECE 256, Spring 09
Duke University
1
Overview

Introduction

Problem

Previous work

Proposed methods

Evaluation

Discussion
2
Introduction


Emerging use for aggregate location traces

Automotive traffic monitoring

City planning
Privacy a big issue


Individuals can be “followed” with their traces
Existing techniques have drawbacks

Either sacrifice data accuracy, or anonymity
3
Traffic monitoring

Goal: estimate travel time for routes

“Probe vehicles” report real-time position and speed

Data stored in central database for analysis

Both real-time and historical
4
Traffic monitoring


Requires high spacial accuracy

Parallel roads may be only 10m apart

Thus, individuals can be tracked with high accuracy
In area of high density traffic, not an issue


Can't track one person in a crowd
Privacy must also be guaranteed in low density

Though data from low-traffic routes not as important
5
Existing privacy algorithms (1)

K-anonymity

Guarantees degree of anonymity

Very low accuracy
6
Existing privacy algorithms (2)

Best effort

Exploit confusion from multiple crossing paths
7
Existing privacy algorithms (2)

Best effort

Tang et al.

Subsampling
8
Existing privacy algorithms (2)

Best effort

Tang et al.

Subsampling
9
Existing privacy algorithms (2)

Best effort

Tang et al.


Non-uniform subsampling also explored


Subsampling
Suppress information in high-density areas
Unclear worst-case privacy guarantees

Individual users still at risk
10
Trace privacy metric

Given trace, determine degree of privacy

Mean Time To Confusion (MTTC)



Time adversary can correctly follow a trace
Need Adversary model

Last position + heading ~ current position

Calculate Tracking Uncertainty H due to confusion

If H > a threshold, then assume trace lost
MTTC depends on threshold for H
11
Proposed algorithm

Parameter: maximum time to confusion

Longest time interval a trace can be followed

Also need to set maximum uncertainty level

Divide into time slots

For each sample in a time slot, check:

Time since last point of confusion < max

Tracking uncertainty > min

If either satisfied, release sample (make available)
12
Possible modifications

Algorithm not specific to one adversary model


Independent tracking uncertainty calculation
Reacquisition tracking model

Adversary can skip over some points of confusion

Minor modifications to algorithm necessary
13
Experimental setup

Data

Collected GPS traces from 233 vehicles


Sample includes timestamp, coordinates, velocity and
heading
Experiments performed on 24 hour traces


With 500 and 2000 probe vehicles
One vehicle's traces from 24 hour periods simulate
multiple vehicles
14
Experimental setup

Evaluation metrics

Maximum and median time to confusion (TTC)

Relative weighted road coverage


Each sample assigned weight based on number of
samples in its area
Quality of sample set = sum of sample weights
15
Results

High-density scenario (2000 vehicles)

Without reacquisition
16
Results

High-density scenario (2000 vehicles)

With reacquisition
17
Results

Low density scenario (500 vehicles)
Without reacquisition
With reacquisition
18
QoS analysis

Samples kept: uncertainty-aware algorithm v.s.
random sampling
19
QoS analysis

Relative weighted road coverage

No significant change after executing algorithm
20
QoS analysis

Maximum TTC vs. weighted road coverage
Without reacquisition
With reacquisition
21
Discussion


Map-based tracking

Roads not a continuous 2D space

Adversary can assign probabilities more intelligently
A priori knowledge


Tracking select individual easier than data mining
Trust in central location server

Fully distributed approach seems infeasible

Hybrid approach more likely

Inform vehicle of probe density in their area
22
The End
23

5.1 snapshots:
24
Proposed algorithm

Processes with time slots

Reveals sample if confusion
25
Existing privacy algorithms (2)

Best effort

Exploit confusion from multiple crossing paths
26