# Location fuzzing

From: Richard Barnes <rbarnes@bbn.com>
Date: Sun, 8 Nov 2009 21:37:04 +0900
Message-Id: <F0135680-F496-4D0F-A446-66F6E10AB303@bbn.com>

Cc: Doug Turner <dougt@dougt.org>
```Hey all,

I got a question from Doug a little while ago about location fuzzing,
and thought the whole group might be interested in the response.

The current approach we're taking in GEOPRIV is described in this
document:
<http://tools.ietf.org/html/draft-ietf-geopriv-policy-21>
Geodetic fuzzing is in Section 6.5.2 ...
<http://tools.ietf.org/html/draft-ietf-geopriv-policy-21#section-6.5.2>
... and fuzzing of civic addresses is in Section 6.5.1:
<http://tools.ietf.org/html/draft-ietf-geopriv-policy-21#section-6.5.1>

These techniques start from a slightly different place than the W3C
Geolocation API:
-- Geodetic location is given by a shape (e.g., point, circle,
ellipse, polygon, arc-band), rather than a single point with a radius
-- Civic location is given by an RFC 5139 address structure

The geodetic fuzzing algorithm take two inputs:
1. A shape representing the user's estimated location, and
2. A "fuzzing radius" F in meters
From these, you generate the fuzzed result in the following way:
First, you choose a random "baseline circle" that  (1) has a radius at
least F, and (2) covers the input shape (the user's location).  The
shape you return is then any shape that contains the baseline circle.
If there are multiple requests for the user's location, then the
return shape may be varied (as long as it still contains the baseline
circle).  If the user moves outside the baseline circle, then you
choose a new random baseline circle.   Example here:
<http://geopriv.dreamhosters.com/fuzz.pdf>

This algorithm guarantees that all an observer gets by averaging/
intersecting is the baseline circle, which has the minimum required
uncertainty.  If the target is moving, then you can add enough jitter
to obscure this to some extent, and you don't run into boundary issues
(like you do with "rounding" or "fixed grid" approaches).

This kind of maps on the the "point+uncertainty" construct that's in
the current Geolocation API spec, if you make the mental equivalence
"point+uncertainty = circle".  In this analogy, the center of the
baseline circle is a random fixed offset from the real location, and
the returned points will cluster roughly around the baseline circle
(with uncertainty values big enough to cover the baseline circle.

The civic fuzzing works by restricting the set of civic address
elements that are returned to a predefined set.  The draft defines six
levels (full, building, city, region, country, none); for example, the
region level includes the "country" element as well as the "A1", "A2",
and "A3" hierarchical elements.

Hope this helps,
--Richard
```
Received on Sunday, 8 November 2009 12:37:43 UTC

This archive was generated by hypermail 2.3.1 : Tuesday, 6 January 2015 20:33:56 UTC