On Jul 17, 2011, at 10:32 AM, Alissa Cooper wrote:
> 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.
... but insufficient to determine the more precise location information as available to the location server, referred as 'known location'.
>
> 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.
>
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.
> 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.
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...
>
> .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.
... is appropriate for a specific application usage, context, and deployment environment.
>
> 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.
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.)
>
> 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.
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
> 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)
>
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.
> The assumptions that a recipient is forced to make to recover
> 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
> 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 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.
>
> 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
>
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.
> 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.
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
> 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.
s/may/MAY.
>
> .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.
>
Will look at the algorithm writeup soon.
Ciao
Hannes
_______________________________________________
Geopriv mailing list
Geopriv@ietf.org
https://www.ietf.org/mailman/listinfo/geopriv
