We'd like to get draft-ietf-geopriv-policy back to the IESG by the end of IETF 81.
Upon request from the chairs, Martin Thomson has drafted the text below describing (1) the fuzzing algorithm evaluation criteria and (2) the performance of one algorithm against these criteria (a simple circle-based algorithm). We'd like to know if we have rough consensus to incorporate this text into the document so we can send it back to the IESG. Please express your opinion to the list by Friday, July 22 (even if it's just, "yes, incorporate the text").
Thanks,
Alissa
---------------
.h1 Location Obscuring Algorithm
The purpose of a location obscuring algorithm is to provide a location
recipient (LR) with location information of reduced quality. The
intent is to provide an LR with location information that is correct,
but insufficient to identify the known location without a chosen
amount of uncertainty.
The obscuring algorithm takes a series of _known locations_, which
might have greater accuracy than the recipient is permitted to
receive. The obscuring process produces a series of _reported
locations_.
Location changes over time. A number of algorithms for obscuring the
location of stationary targets exist
[http://portal.acm.org/citation.cfm?id=1770566],
[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.159.1678&rep=rep1&type=pdf],
but are of questionable value when a target moves.
This section describes the goals for a location obscuring algorithm.
The normative "SHOULD" is used to describe goals, since it could be
impossible for any single algorithm to address all the described
goals. It is expected that some goals are only partially or
conditionally achieved by each algorithm.
.h2 Algorithm Structure
The algorithm SHOULD accept known locations with uncertainty and
produce reported locations with uncertainty that encloses the known
location at that time. That is, the reported location is no less
correct than the known location.
An obscuring algorithm MUST include a description of the user-selected
inputs it uses and how those inputs affect output of the algorithm.
Usability is an important consideration in selecting which inputs an
algorithm uses. A rule maker (RM) needs to be able to quickly and
easily comprehend the impact of a choosing any available option.
This document describes a single input parameter: a distance in
meters. Algorithms that use this parameter ensure that there is at
least this much uncertainty in the reported location. Algorithms
SHOULD restrict their inputs to this one parameter to aid usability.
.h2 Algorithm Assessment
The effectiveness of an obscuring algorithm under all circumstances
might be imperfect. An assessment of effectiveness helps a rule maker
decide if an algorithm is appropriate.
An algorithm is measured against its goals. An algorithm that aims to
convey a chosen amount of uncertainty is only partially effective if
there are conditions where a location recipient is able to recover
location with less uncertainty. Determining the frequency or
probability of these conditions and the degree to which uncertainty is
reduced is the goal of an assessment.
Assessment of an algorithm MUST assume that the location
recipient knows the choices made by the rule maker, which includes the
details of the algorithm and the selected inputs.
This section describes one possible framework that aids in assessing
algorithms.
The goal of the adversary or attacker is to derive information about
the known location from the reported location.
In order to recover location, an adversary makes assumptions
[Duckham05] about the location of the target. These assumptions are
applied to the reported location to produce a recovered location that
has lower uncertainty than the reported location.
recovered = apply(reported, assumption)
where:
uncertainty(recovered) <= uncertainty(reported)
confidence(recovered) <= confidence(reported)
The assumptions that a recipient is forced to make to recover
information determines how effective an algorithm is. An assumption
that reduces uncertainty significantly without also reducing
confidence provides an adversary with better information about the
known location. Less reliable assumptions reduce confidence more
significantly than they reduce uncertainty.
Multiple assumptions can be applied to progressively refine a
recovered location. The more assumptions that are used, the more
likely it is that any one assumption is bad. Applying a bad
assumption could lead to the recovered location being different to the
known location. Therefore, each assumption that is applied reduces
the adversary's confidence in the recovered location.
[[I considered discussing the option of increasing confidence here,
which would be possible: using the assumption to confirm something.
However, increasing confidence has the same net effect as reducing
uncertainty when scaling of uncertainty is considered, so I decided to
keep things simple ... hah.]]
The goal of the obscuring algorithm is to limit the ability of an
adversary to recover location information, even when a number of
correct assumptions can be made.
.h3 Basic Assumptions
A location recipient in possession of one or more reported locations
SHOULD have no more information about any known location without
making any assumptions about the nature of the known location. That
is, an algorithm SHOULD NOT reveal any more information than its
inputs specify to an adversary that makes no assumptions.
The following assumptions are considered important for the development
of an algorithm that obscures location. These assumptions are
considered to have a high probability of being correct and are
therefore the most important assumptions to protect against.
For each assumption, the recipient SHOULD be unable to recover the
known location with less uncertainty than the reported location when
the assumption is correct.
Stationary assumption: An algorithm SHOULD obscure the location of a
stationary target. A location recipient SHOULD be unable to
recover the known location by assuming that the target is
stationary.
Continuous movement assumption: An algorithm SHOULD obscure the
location of a moving target. A location recipient SHOULD be
unable to recover the known location by assuming that the target
is moving at a constant speed or with a constraint on
acceleration.
The description of the algorithm SHOULD include information on
what is revealed about a moving target. This includes direction
of movement, speed and acceleration.
Same place assumption: An algorithm SHOULD obscure the details of a
frequently visited place. A location recipient SHOULD be unable
to recover the location of the target by assuming that they are
the same place as was in a previous reported location.
Same course assumption: As for the frequently visited destination,
but for a path that the target follows.
The description of the algorithm SHOULD indicate whether the
algorithm prevents a recipient from identifying whether different
reported locations correspond to the same known location, and
under what circumstances. This would permit a recipient to learn
that the same location is being visited, even if the identity of
that location is obscured.
High accuracy assumption: A location recipient SHOULD be unable to
recover the known location by assuming that the known location has
low uncertainty or is updated frequently.
An analysis of the algorithm based on a continuous series of
perfect known locations is desirable.
An algorithm may also provide protection for the speed or velocity of
a target. It is desirable that the precise speed of a target cannot
be easily learned.
.h3 Additional Assumptions
Discussion of any additional assumptions that are either rendered
ineffective or especially effective is useful in evaluating an
algorithm.
The following assumptions depend on the location recipient having
additional information, such as topological or demographic data
available.
Constrained movement assumption: A location recipient MAY be
unable to recover the known location by assuming that the target
is unable (or less likely) to be located in certain locations.
For instance, a location recipient might assume that the target
is more likely to be found on a road or footpath. Similarly, by
assuming that the target is unlikely be found in a body of
water, the known location could be recovered.
A more sophisticated assumption of constrained movement uses
knowledge of how different locations are connected. An
adversary could know that to transit between two points is only
possible by following a small set of paths.
Goal driven movement assumption: A location recipient MAY be
unable to recover the known location by assuming that the
movement of the target is driven by a desire to move from one
place to another. By using information on relative frequency of
different paths, a particular path might be selected with higher
probability based on the reported locations.
Behavioral or past history assumption: A location recipient MAY be
unable to recover the known location by assuming that the target
is following pre-established patterns of behavior. These
patterns could be derived either from past knowledge of the
target, or demographic data that might be refined based on other
knowledge about the target.
Addressing these additional assumptions is desirable, but potentially
difficult. Integrating additional data increases algorithm complexity
and data might not be available to all implementations.
.h2 Simple Obscuring Algorithm
This algorithm takes a single distance in meters. It produces a
reported location with circular uncertainty area of that radius or
greater.
As each known location is generated or received at the location
server:
1. Determine the distance between the centroid of the known location
to the trigger point. If there is no trigger point saved for this
target and location recipient, assume this distance is infinite.
If this distance is less than the input, do not report the location
and end the algorithm.
2. Convert the known location to a circle
[I-D.thomson-geopriv-uncertainty].
3. Set the trigger point to the centroid of the known location.
4. If the known location has uncertainty equal to or greater than the
input, report the known location and end the algorithm.
5. Select two uniformly distributed random numbers [RFC4086] between 0
and 1.
6. Set the centroid of the reported location by moving the centroid of
the known location randomly, using the two random numbers:
- The distance is determined by taking the square root of the first
number and multiplying it by the difference between the input and
the uncertainty (radius) of the known location.
- The angle (or heading) is determined by multiplying the second
number by 360 degrees (or 2*pi radians).
7. Set the uncertainty radius of the reported location to the input.
8. Move the trigger point randomly by half the input using the process
used in Step 6 with a new pair of random numbers. Save the trigger
point for this target and location recipient.
9. Report the randomized location and end the algorithm.
.h3 Simple Algorithm Assessment
This simple algorithm requires that the LS performing obscuring store
a trigger location for each location recipient. This might be reduced
to the set that have the same policy.
This algorithm only addresses the stationary assumption and the
continuous movement assumption. Same place or same path assumptions
are effective in recovering the known location.
The location of the target can be easily recovered when a recipient is
able to collect multiple reported locations for the same destination
over time. The known location is randomized differently each time the
destination is visited or path is travelled. A location recipient
that assumes same destination can intersect these to recover a
location with uncertainty which could be as good as the known
location.
The reported location produced by this algorithm always contains the
known location. This is the cause of a significant flaw, as described
[[below]].
.h3 Simple Algorithm Flaw
For certain random values, the location of the target can be precisely
revealed using two consecutive reported locations. The following
three conditions result in the known location being almost perfectly
recovered:
# The trigger point generated at the first point is moved in one
direction by the maximum distance, or close to it.
# The target moves in the same direction as the trigger point.
# The randomization of the second location moves the location in the
same direction by the maximum distance, or close to it.
# The randomization of the first location moves the location in the
opposite direction by the maximum distance, or close to it.
The resulting reported locations have center points that are almost
3.5 times the input distance apart, and the nearest points in the
reported locations 1.5 times apart. The known locations are easily
identified as being at the nearest points on the circle, since no two
consecutive points can be more than 1.5 times the input distance
apart.
In general, a reported location can be found at the intersection of
that reported location, plus two circles of radius 2.5 times the input
distance, centered at both the last and next reported locations.
_______________________________________________
Geopriv mailing list
Geopriv@ietf.org
https://www.ietf.org/mailman/listinfo/geopriv
