Subject: [Geopriv] Call for consensus on fuzzing text for geopriv-policy

From: Alissa Cooper <[email-masked]>
Date: Sun, 17 Jul 2011 15:32:27 +0100

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.

---

From: Hannes Tschofenig <[email-masked]>
Date: Thu, 21 Jul 2011 14:03:46 -0400

Hi Alissa, Hi Martin, 

> 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 s…

... but insufficient to determine the more precise location information as available to the location server, referred as 'known location'. 

> but are of questionable value when a target moves.

We don't do us a favor with such a text. We could argue with the authors of their proposal on why exactly we find them questionable but it does not help our document in any way. 
I would suggest to delete the paragraph. We then also do not have to add these new references. 

> conditionally achieved by each algorithm.

I would change this paragraph and also the beginning of the next section to:
"
.h2 Algorithm Goals

This section lists design goals for  location obscuring algorithms. The algorithm described in this document meets these goals 
and authors of yet-to-be-defined location obscuring algorithms are encouraged to consider these design goals as well. 
For convenience reasons we use RFC 2119 language to indicate the different levels of importance of the individual design goals. 
It could be impossible for any single algorithm to address all the describe goals and certain design goals may only be partially or conditionally achieved by a specific algorithm.
"

I am personally not a huge fan of normative statements about future algorithms because it almost sounds like the 'using protocol' requirements to me. Often the environment and technology changes and so the requirements then tend to be out of sync with what we have written. We say that with the using protocol requirements quite nicely and you had also objected to some of those. They also looked great at the time of writing...

> decide if an algorithm is appropriate.

... is appropriate for a specific application usage, context, and deployment environment. 

> details of the algorithm and the selected inputs.

I am not sure I capture the essence of the sentences. Are you trying to say that transparency is an important property in the design and all parties must have access to the algorithm description so that they can make (maybe via a third party) an assessment of the quality of the algorithm. If that's the idea I am fully on board with it. Transparency is important. (The same holds true for security algorithms as well.)

> [Duckham05] about the location of the target.
The adversary makes assumptions about which location. It would only see the reported location but most likely the assumptions apply to the known location. 
With assumption you are most likely referring to things like that the target follows certain landmarks, or so. Right? An example of the type of assumptions you have in mind would be useful. 

I am also not quite sure about the value of the reference. While I had read the paper a while ago I am not sure from reading the sentence of what specifically you are making the reference to it for. 

>  These assumptions are

This sounds nice (for a paper) but in fact it does not add a lot for the rest of the writeup. Maybe we could shorten this text by omitting that part. 

> information determines how effective an algorithm is.

Wouldn't you also, like in security, consider the amount of reported location samples the adversary collected or the computational effort he has to make? 
Of course you could call this an "assumption"....

>  An assumption

The last 2 paragraphs sound very theoretical to me and all this talk about confidence and so on will not help the reader a lot. 
A designer of a new algorithm will not be provided with enough information to develop a better algorithm and an adversary will hopefully know more.
I don't believe we even define "confidence" in the document to begin with. 

> correct assumptions can be made.

I wouldn't use the term "assumptions" here. We are talking about requirements or goals (as it was called in a previous section). 
Additionally, it would be useful to point out that these "requirements" are design wishes of the authors for future algorithms. 

>   stationary target.

It might be useful to add that the challenge here is that a sequence of reported location may allow an adversary to compute the intersection and to obtain more information about the known location as a consequence. 

>  A location recipient SHOULD be unable to

s/may/MAY. 

> and data might not be available to all implementations.

Will look at the algorithm writeup soon. 

Ciao
Hannes

---

From: Hannes Tschofenig <[email-masked]>
Date: Thu, 21 Jul 2011 19:12:59 -0400

Hi Alissa, Hi Martin, 

your proposed algorithm assumes that there is a trigger point that is stored with each Target & location recipient. 
Jorge's algorithm did not make use of the same state requirement and instead had a grid pre-defined, as you known. 

You don't seem to like the grid-based approach. Any specific reason for not using the grid-based mechanism? 
We would then have an algorithm that is similar to what is currently in the document. 

> inputs specify to an adversary that makes no assumptions.

I am not sure how much these two paragraphs add. Everything succeeds and fails with the assumptions. 

For example, if a Target moves and the reported location changes (which it certainly has to at a certain point in time in any practical setup). 
This already tells the location recipient that the target is not stationary. 

>  If this distance is less than the input, do not report the location

Here it needs to be ensured that in the stationary case the distance is always aways greater than the input since otherwise the location recipient does not get location reported anymore. 

>  [I-D.thomson-geopriv-uncertainty].

Is this a normative dependency? 

> 3. Set the trigger point to the centroid of the known location.

I believe it would be more clear to re-set the trigger point in step 4 in case you end the algorithm since otherwise the re-setting it to the centroid of the known location makes no sense given that you re-set it again in a latter step. 
Something like: 

4. If the known location has uncertainty equal to or greater than the
 input, report the known location, reset the trigger point to the centroid of the known location, and end the algorithm. 

>    number by 360 degrees (or 2*pi radians).
Could you explain your motivation for computing the distance and the angle in this specific fashion? 

> 7. Set the uncertainty radius of the reported location to the input.

If you do this wouldn't the system have location reports with a radius that equals the input value. 
For example, imagine that you have a system that uses GPS then the known location would have a fairly small uncertainty radius (almost always).
Hence, almost all reported locations would have an uncertainty radius that corresponds to the input of the rule maker. 

Ciao
Hannes

---

From: Alissa Cooper <[email-masked]>
Date: Fri, 22 Jul 2011 07:02:51 +0100

Hi Hannes,

Recall the plan that was made at the last IETF meeting:

> From: "Thomson, Martin" <[email-masked]>
> Date: March 30, 2011 2:11:17 PM GMT+01:00
> To: "[email-masked]" <[email-masked]>
> Cc: "James M. Polk" <[email-masked]>
> Subject: [Geopriv] geopriv-policy plans
> 
> We got together this morning to discuss the plans for geopriv-policy.
> 
> The plan was to create the following issues in the WG tracker:
> 
> - create a registry for location obscuring algorithms
> - describe the mechanism for algorithm selection
> - describe the goals (not requirements!) for algorithms
> - select/define and describe the old algorithm (this requires making the algorithm complete)
> - complete and describe Jorge's algorithm
> 
> Only the first three of these are absolutely critical for us to progress the draft.  We want to do that by May 15.
> 
> We have commitments from myself and Jorge to do this, but we'll need WG feedback if we are going to complete these tasks by our self-imposed deadline of May 15.

This text aims to complete the third and fourth bullets of the plan. I think you are referring to the fifth bullet, the text for which has not been provided by anyone as far as I know.

Best,
Alissa

---

From: "Thomson, Martin" <[email-masked]>
Date: Sun, 24 Jul 2011 00:51:17 +0800

Thanks Hannes.

I'll draft an update once we've had our discussion.  For the most part, I've agreed with your comments.

On 2011-07-21 at 14:03:46, Hannes Tschofenig wrote:
> > 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
> >
> > ---------------
> >
> >
> > 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.
>
> ... but insufficient to determine the more precise location
> information as available to the location server, referred as 'known location'.

OK.

> > Location changes over time.  A number of algorithms for obscuring
> > the location of stationary targets exist
> [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.
> >
>
> We don't do us a favor with such a text. We could argue with the
> authors of their proposal on why exactly we find them questionable but
> it does not help our document in any way.

Sure.

> This section lists design goals for  location obscuring algorithms.
> The algorithm described in this document meets these goals and authors
> of yet-to-be-defined location obscuring algorithms are encouraged to
> consider these design goals as well.
> For convenience reasons we use RFC 2119 language to indicate the
> different levels of importance of the individual design goals.
> It could be impossible for any single algorithm to address all the
> describe goals and certain design goals may only be partially or
> conditionally achieved by a specific algorithm.
> "
>
> I am personally not a huge fan of normative statements about future
> algorithms because it almost sounds like the 'using protocol'
> requirements to me. Often the environment and technology changes and
> so the requirements then tend to be out of sync with what we have written.
> We say that with the using protocol requirements quite nicely and you
> had also objected to some of those. They also looked great at the time
> of writing...

That was the point that I was trying to get to with the "SHOULD" thing.  At this stage, we're really just describing a wish-list.  Normative language is possibly totally inappropriate in that context.

> ... is appropriate for a specific application usage, context, and

Done.

> > 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.
>
> I am not sure I capture the essence of the sentences. Are you trying
> to say that transparency is an important property in the design and
> all parties must have access to the algorithm description so that they
> can make (maybe via a third party) an assessment of the quality of the
> algorithm. If that's the idea I am fully on board with it.
> Transparency is important. (The same holds true for security
> algorithms as well.)

Kerckhoff's Principle.  Yes.

> The adversary makes assumptions about which location. It would only
> see the reported location but most likely the assumptions apply to the
> known location.

Correct.  Though I wanted to imply that it's more than the known location that they make assumptions about - it's the "real" location.

> With assumption you are most likely referring to things like that the
> target follows certain landmarks, or so. Right? An example of the type
> of assumptions you have in mind would be useful.

That can be done.  "By assuming that the target is on or near a road, the recipient can reduce uncertainty to the area near or around roads."

> I am also not quite sure about the value of the reference. While I had
> read the paper a while ago I am not sure from reading the sentence of
> what specifically you are making the reference to it for.

The reference provides a better description of this.  The only real benefit of my crude summary is that it's short.

> >  These assumptions are
> > applied to the reported location to produce a recovered location
> > that has lower uncertainty than the reported location.
> >
> This sounds nice (for a paper) but in fact it does not add a lot for
> the rest of the writeup. Maybe we could shorten this text by omitting
> that part.

Let's drop it then.  It was marginal anyway.

> Wouldn't you also, like in security, consider the amount of reported
> location samples the adversary collected or the computational effort
> he has to make?

In terms of computation effort, I think that you need to assume that the adversary has considerable, though not infinite computational capacity.  On the number of samples, it would be better to assume that the adversary has access to all previous samples and potentially all future samples.

> The last 2 paragraphs sound very theoretical to me and all this talk
> about confidence and so on will not help the reader a lot.
> A designer of a new algorithm will not be provided with enough
> information to develop a better algorithm and an adversary will
> hopefully know more.

The idea of confidence is probably something that needs to be discussed.  I would like to reopen the discussion on whether to adopt -uncertainty at some point.  Having a reference like that would be useful in times like this.

> I wouldn't use the term "assumptions" here. We are talking about
> requirements or goals (as it was called in a previous section).
> Additionally, it would be useful to point out that these "requirements"
> are design wishes of the authors for future algorithms.

Basic Goals

> It might be useful to add that the challenge here is that a sequence
> of reported location may allow an adversary to compute the
> intersection and to obtain more information about the known location
> as a consequence.

I considered this, but it felt like it was too specific, and this text is already too long, even with the bits you have already suggested be cut.

> > 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.
>
> s/may/MAY.

Ack.

> > .h3 Additional Assumptions

...Goals.

> > Addressing these additional assumptions is desirable, but
> > potentially difficult.  Integrating additional data increases
> > algorithm
> complexity
> _______________________________________________
> Geopriv mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/geopriv

---

From: "Thomson, Martin" <[email-masked]>
Date: Sun, 24 Jul 2011 00:51:19 +0800

On 2011-07-21 at 19:12:59, Hannes Tschofenig wrote:
> Hi Alissa, Hi Martin,
> 
> your proposed algorithm assumes that there is a trigger point that is 
> stored with each Target & location recipient.
> Jorge's algorithm did not make use of the same state requirement and 
> instead had a grid pre-defined, as you known.
> 

This is just the algorithm that I wrote up.  A grid mechanism would be OK, it merely has a different set of problems - the most significant being the border-crossing problem.
 
> and fails with the assumptions.

There are inherent properties of the algorithms that cause leakage - see the weakness below.  Ideally, an algorithm doesn't have such weaknesses.

> For example, if a Target moves and the reported location changes 
> (which it certainly has to at a certain point in time in any practical setup).

I don't think that's true.  I can have two reported locations that correspond to the same known location.  None of the algorithms proposed thus far do this, but nothing prevent this.

> Here it needs to be ensured that in the stationary case the distance 
> is always aways greater than the input since otherwise the location 
> recipient does not get location reported anymore.
> 

It was supposed to be a "for example" reference.  It can't be normative.

> I believe it would be more clear to re-set the trigger point in step 4 
> in case you end the algorithm since otherwise the re-setting it to the 
> centroid of the known location makes no sense given that you re-set it 
> again in a latter step.
> Something like:
> 
> input, report the known location, reset the trigger point to the 
> centroid of the known location, and end the algorithm.

Unfortunately, if the next location has lower uncertainty, you reveal it at that point.  So this doesn't work out very well.

> > 4. If the known location has uncertainty equal to or greater than 
> > the input, report the known location and end the algorithm.
> >

Certainly.

"This produces an offset that is evenly distributed over a circular area.  This reduces the chance that an adversary can choose any particular point with a higher probability of being the known location."

> For example, imagine that you have a system that uses GPS then the 
> known location would have a fairly small uncertainty radius (almost 
> always).
> Hence, almost all reported locations would have an uncertainty radius 
> that corresponds to the input of the rule maker.

Correct.  That means that your adversary learns the input very easily.  The input is not a secret, as stated below.