| Internet Research Task Force | A. Andersdotter |
| Internet-Draft | ARTICLE 19 |
| Intended status: Informational | S. Sahib |
| Expires: May 6, 2020 | Salesforce |
| November 3, 2019 |
Randomized Response Mechanisms in RRT Measurements for HTTP/3
draft-andersdotter-rrm-for-rrt-in-http3-00
The latency spin bit is an optional feature included in the QUIC transport protocol. It enables passive, on-path observations for estimation of latency. This document presents the results of an inquiry into the potential of using randomized response mechanisms (RRM) to reduce privacy loss in latency measurements. It concludes that RRM could be used to introduce choice for clients in preserving privacy in latency measurements. But the trade-offs, especially since the latency spin bit is already optional, do not favour RRM.
This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."
This Internet-Draft will expire on May 6, 2020.
Copyright (c) 2019 IETF Trust and the persons identified as the document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.
At the IETF104 convening of the Privacy Enhancements and Assessments Research Group (PEARG), a presentation on Differential Privacy ([AA-CL]) gave rise to the idea of trying to apply Randomized Response methods to the QUIC Spin Bit described in [TRAMMEL] and [KUEHLEWIND]. Now incorporated in Section 17.3.1, the latency spin bit has generated controversy from a privacy perspective, both in the Working Group meetings and on e-mailing lists. Controversies were re-ignited through the publication of a Human Rights Consideration in [TENOEVER-MARTINI]. Applying RRM is an attempt to address two problems: the privacy loss incurred through the spin bit, and considering the potential of using RRM to have more than one bit assisting in latency measurement as per previous proposals.
Randomized Response Mechanisms (RRM) rely on the ability to make sense of data with known errors and were originally developed to facilitate surveys on sensitive topics such as alcohol or drug abuse or political affiliation. The design allows a survey taker to provide, with some known probability P, a "false" answer ("yes" instead of "no", for example) to a survey question. It is meant to encourage truthful answers even in surveys where participants may otherwise feel compelled to give false answers.
Randomized response trials were originally created for binary environments: if a series of measurements have only two possible outcomes (0 or 1, yes or no, true or false, for instance), it is the idea that allowing individual respondents to answer "falsely" at a predictable rate will still preserve the ability to make inferences on the entire set of respondents. The latency spin bit, being a bit, is binary outcome variable. Each time it is measured, the idea is that it can either "truthfully" report its value as what it should be according to [TRAMMEL], or it could, at some known rate or probability, report the opposite value.
RRMs are easily illustrated for binary response problems. Let's take as an example "Did you go to the last IETF meeting?" The answer to this question is either yes or no. Let us suppose that 25% of all responses are known to be false, and that 80% of all respondents answered yes. Then 60% of the respondents who answered yes can be assumed to have done so truthfully, while 5% of the respondents who answered no have done so falsely. 65% of the respondents can therefore be estimated to have actually attended the last IETF meeting.
RRMs can also be applied to multiple choice questions. Estimation of true proportions becomes more difficult as the number of possible answers per question goes up. Further examples, including formulas and calculations, can be found in [DWORK] and [FOX].
As described in [TRAMMEL], the latency spin bit is a mechanism for measuring round-trip-times (RTT) in the QUIC protocol. The investigation in this document relies on [TRAMMEL] for its understanding of the basic operation of the latency spin bit, and in particular the following paragraphs and figures from the document are quoted to facilitate the description of RRM below:
[Begin quote] Initially, during connection establishment, no packets with a spin bit are in flight, as shown in Figure 1.
+--------+ - - - - - +--------+ | | --------> | | | Client | | Server | | | <-------- | | +--------+ - - - - - +--------+
Figure 1: Initial state, no spin bit between client and server
Either the server, the client, or both can begin sending packets with short headers after connection establishment, as shown in Figure 2; here, no spin edges are yet in transit.
+--------+ 0 0 - - - +--------+ | | --------> | | | Client | | Server | | | <-------- | | +--------+ - - 0 0 0 +--------+
Figure 2: Client and server begin sending packets with spin 0
Once the server’s first 0-marked packet arrives at the client, the client sets its spin value to 1, and begins sending packets with the spin bit set, as shown in Figure 3. The spin edge is now in transit toward the server.
+--------+ 1 0 0 0 0 +--------+ | | --------> | | | Client | | Server | | | <-------- | | +--------+ 0 0 0 0 0 +--------+
Figure 3: The bit begins spinning
Five ticks later, this packet arrives at the server, which takes its spin value from it and reflects that value back on the next packet it sends, as shown in Figure 4. The spin edge is now in transit toward the client.
+--------+ 1 1 1 1 1 +--------+ | | --------> | | | Client | | Server | | | <-------- | | +--------+ 0 0 0 0 1 +--------+
Figure 4: Server reflects the spin edge
Five ticks later, the 1-marked packet arrives at the client, which inverts its spin value and sends the inverted value on the next packet it sends, as shown in Figure 5.
obs. points X Y
+--------+ 0 1 1 1 1 +--------+
| | --------> | |
| Client | | Server |
| | <-------- | |
+--------+ 1 1 1 1 1 +--------+
Y
Figure 5: Client inverts the spin edge
[End quote]
In each iteration going from Figure 4 to Figure 5 a sequence of 0s or 1s the length of which is k0 for iteration 0, k1 for iteration 1, and so forth, can be observed (by on-path observers X or Y in Figure 5). The length of each sequence equals the amount of ticks required to pass from the client back to the client. After observation n lengths of such sequences, (k[0], ..., k[n]), an average can be taken over k[j]. This average can be multiplied by the amount of time per tick (a quantity which is assumed to be known) to get a value for the round-trip time (RTT).
Applying randomized response mechanisms (RRMs) perturbs the observed sequence lengths (k[0], ..., k[n]). The perturbation will have the effect of lengthening, shortening, or making more arbitrary the lengths of the sequences, thereby increasing the variance, or disable the possibility, of an estimator of the true RTT value.
The server or the client is assumed to behave as described in Figure 4 and Figure 5, unless specifically stated otherwise. That means the assumed default behaviour is that a "truly" reflecting server that receives a bit set to v=0 always reflects a bit with v=0. In an RRM application, a server which "falsely" reflects a bit receives a bit set to v=0 and reflects a bit set to v=1. Similarly, the assumed default behaviour of a client is that it "truly" inverts a bit, so that receiving a bit set to v=0 causes it to transmit a bit set to v=1. In an RRM application, the client may "falsely" transmit a bit set to v=0 even when it has received a bit set to v=0. The receiving of a spin edge is assumed to be a trigger event for a reflection or an inversion. The server and the client are assumed to have an internal spin value that determines the spin bit that goes out. Every time a spin edge comes in (a trigger), this internal spin value is changed, changing also the outgoing spin value.
An additional assumption is that the server and client behave independently of one another. This means that the server has no information on whether the client has omitted an inversion, and the client has no information on whether the server has omitted a reflection. Omissions are therefore independent events.
We have looked at two ways of perturbing measurements:
They will be dealt with in turn, identifying pitfalls and potential ways of addressing those pitfalls. The goal is to have better privacy-protecting properties while continuing to allow utility of the on-path observations in latency measurements.
The omission of a reflection or inversion creates difficulties. Namely, let's say the client omits the inversion in Figure 5. Now there is no longer a spin edge so there is nothing to activate future reflections/inversions.
A possible work-around is to do random re-sets of the spin bit, i.e., starting the process fresh from Figure 2. Observers X and Y in Figure 5 would then get a series of measurements (k0, ..., kn), some of which were far too large, but would, over time, be able to deduce RTT from the smaller measurements. The expected proportion of large and small measurements in the whole set of measurements could be determined from the probabilities that a edge transition does not happen and the probability that the spin bit is re-initiated.
Another possible work-around is having an additional bit to indicate a spin edge, assigned by the server to the bit which is (not) reflected in Figure 4, or by the client to the bit which is (not) inverted in Figure 5. In this case there would not be a point in applying RRM since the placement of the spin edge would no longer be obfuscated.
If the ordinary spin edge is obfuscated by through omission of edge transition, and the edge-identifying bit is also, with some probability, not correctly identifying an edge, the utility of having two latency bits again goes up at no additional loss of privacy.
The bit starts spinning with value v=1 in Figure 3. At the point of reflection (see Figure 4), it does not reflect with probability P. At the point of inversion (see Figure 5), it does not invert with probability Q. We consider P and Q respectively to be the probability that the server or client does not behave in the way specified.
Let -> be the operation that a bit changes value. A correct reflection will be denoted R: a->a. A correct inversion is denoted I:a->b. Prefixing R or I with a ! denotes that edge transition was not done correctly. The variables a and b assume the values 0 or 1 and are never equal. P(R: a->a) = 1-P and P(I: a->b) = 1-Q, while P(!R: a->b) = P and P(!I: a->a) = Q. An expression like R(v: 1->1) -> !I(v: 1->1) means that a bit whose initial value is 1 is correctly reflected, and then incorrectly inverted. We can abbreviate this to [1->1->1]. R must follow I and vice versa, so we will have a chain of events R->I->R->I-> etc.
In order for a reflection or an inversion to occur, there must be a trigger. The spin edge is the trigger. But in the event of [1->1->1] the spin edge has disappeared! Once the bit spins back to the reflection, it will have the same value as when it started. In fact, regardless of the starting value, any R->I event that results in [1->1] or [0->0] leads to a loop.
We can define the following events:
Event A can occur as a result of (!R, !I) for starting point v=0, or as a result of (R, !I) for starting point v=1 or v=0. Event B can occur as a result of (!R, !I) for starting point v=1, or as a result of (R, !I) for starting point v=1 or v=0. Event C occurs as a result of (!R, I) for starting point v=1, or (R, I) for starting point v=0. Event D occurs as a result of (!R, I) for starting point v=0 or (R, I) for starting point v=0. The starting point v can be taken as the final digit in each event, meaning that for the event following C, the starting point would be v=1, and for the event following D, the starting point would be v=0.
With this information, and the probabilities determined above, we can create a transition matrix in the Markovian sense.
+----+-----------+-----------+-----------+-----------+ | | A | B | C | D | +----+-----------+-----------+-----------+-----------+ | A | 1 | 0 | 0 | 0 | +----+-----------+-----------+-----------+-----------+ | B | 0 | 1 | 0 | 0 | +----+-----------+-----------+-----------+-----------+ | C | (1-P)Q | Q | P(1-Q) | (1-P)(1-Q)| +----+-----------+-----------+-----------+-----------+ | D | Q | (1-P)Q |(1-P)(1-Q) | P(1-Q) | +----+-----------+-----------+-----------+-----------+
Figure 6: RRM transition matrix, no reset and no edge-id bit
It should be quite clear from this matrix that events A and B act as sinks. Because ending in a sink removes all possibility of future measurements, we could hope to avoid this situation. The easiest way is setting Q=0, which would imply there is always a correct inversion. For any Q > 0, this process will eventually end up in a sink.
The possible outcomes are as in Section 3.1.1, and the problem to be resolved is that the spin edge eventually disappears with probability 1.
Introducing the probability R of a random re-set of the spin bit at every m:th bit transmission can "re-initiate" the edge by taking the entire system back into the situation described in Figure 4 (with the modification that it is not assumed that the starting point must be v=1; the starting point could also be reset to v=0). It is assumed that a re-set occurs on the client-side, and not on the server-side.
The true number of ticks in a round-trip time is C. If R>0 and m >> C, the process will be reset every period of km ticks, where k is an integer whose distribution is geometric with parameter R. After km ticks, an on-path observer may pick up a sequence that can be used as a basis for measuring the round-trip time.
In Figure 7 the situation where m=2 is illustrated.
+---+----------+--------+----------+--------+----------+----------+ | | A,m0 | A,m1 | B,m0 | B,m1 | C | D | +---+----------+--------+----------+--------+----------+----------+ |A,0| 0 | 1 | 0 | 0 | 0 | 0 | +---+----------+--------+----------+--------+----------+----------+ |A,1| 1-R | 0 | 0 | 0 | R | 0 | +---+----------+--------+----------+--------+----------+----------+ |B,0| 0 | 0 | 0 | 1 | 0 | 0 | +---+----------+--------+----------+--------+----------+----------+ |B,1| 0 | 0 | 1-R | 0 | R | 0 | +---+----------+--------+----------+--------+----------+----------+ | C | (1-P)Q | 0 | Q | 0 | P(1-Q) |(1-P)(1-Q)| +---+----------+--------+----------+--------+----------+----------+ | D | Q | 0 | (1-P)Q | 0 |(1-P)(1-Q)| P(1-Q) | +---+----------+--------+----------+--------+----------+----------+
Figure 7: RRM TM, Reset at m=2, no edge-id bit
If m (or km | k ~ Ge(R)) is too small, there will never be any sound measurements since the process will always start over before a measurement appears. Using a reset function is therefore especially burdensome for an on-path observer in cases where latencies are a priori expected to be large.
The possible outcomes are as in Section 3.1.1, and the problem to be resolved is that the spin edge eventually disappears with probability 1.
Introducing an edge identifying bit, which may or may not hold a true value with probability S, could help mitigate this problem. This could effectively be seen as a recursive RRM: because the original RRM risks removing the utility of the spin bit entirely, another bit to which RRM is applied is added.
Logically, adding another identifying bit increases the possible set of states of the Markovian chains described in Section 3.1.1 and Section 3.1.2. In fact, the systems would still possess similar short-comings, but with different probabilities. The exception is if the identifying bit is always on with probability S=1. In this case, the privacy-enhancing properties sought in Section 3.1.1 and Section 3.1.2 would be lost, since the main goal of RRM in both of those cases is to perturb the measurements (k0, ...., kn) used to estimate round-trip times.
In Section 3.1.1 we saw that applying RRM at reflection and inversion could create a situation where the spin edge disappears. There are two parameters, P and Q, which are set by the client and server respectively.
We could reduce the risk of the spin edge disappearing by setting the probability of a wrongful inversion to Q=0. However, inversion is an activity undertaken by the client and Q is a parameter under the clients control. Since the client is the entity assumed, in most cases, to be the most likely actor to be a human, natural person (in either case, more likely than the server), this solution would remove power from the client. Forcibly setting Q=0 would violate the assumptions of user control in Section 7.2.
In Section 3.1.2 we considered whether it was possible to reset a latency spin bit whose edge has disappeared. Effectively, resetting would improve an on-path observers chances of making measurements, but it also introduces a delay for the acquisition of useful measurements.
We assume that the client will set Q>0 and that this is under the client's control, and have three additional parameters: P, m and R. Both m and R can be under the client's control. We found that km | k~Ge(R) has an impact on the ability to measure latency when latency is large. In practice, an average human, natural person is probably not going to choose parameters Q, m and R (even though they could be made available at settings in an interface). Setting of these parameters will instead likely be under the control of the entity that produces latency spin bit capable software.
In Section 3.1.3 we conclude that adding an edge-identifying bit is not a remedy to any of the issues with the methods in Section 3.1.1 or Section 3.1.2. It introduces the possibility of yet another client-controlled parameter S, but the obfuscating effects derived from S could instead be obtained by regulating previously suggested parameters Q, m or R.
Let us say any bit transmitted from either the client or the server is "off" in relation to what it proposed in the Spin Bit model with some probability Q. If Q = 0.5, the spinning bits will come across as a random 0s and 1s and it will be difficult to estimate any edge. However, if Q is less than 0.5, the spin edge can be estimated for instance by computing an average number of 0s or 1s in the past m ticks. For all averages above some cut-off rate, a measurement counter could be incremented by one. Eventually one would end up with a series (k'0, ..., k'n) that roughly corresponds to (k0, ..., kn) above.
The bit spins in the foreseen way. Every time a bit is transmitted, there is a probability Q that it holds a different value than it should. In Figure 5 , either measurements station X or both stations Y observe a passing bit, as well as bits passing before or after that bit (if any). After observing 2k+1 bits (b[-k], ..., b[0], ..., b[k]) the true value of bit b[0] is estimated, for instance based on whether the majority of b[i] were v=0 or v=1. The estimated value is then used to increment a sequence counter.
The estimator follows a binomial distribution (drawing with replacement), and the risk of misidentifying a bit is equal to the risk of having (k+1) v=1 bits in the 2k observations where b[0] "should" be attributed to v=0. This risk depends on Q and k.
Setting k too large creates a risk of having estimator sequences that are longer than the round-trip time (RTT) to be measured. If Q is reasonably small, estimation will still eventually be possible after a sufficient amount of measurements. One option is to keep Q variable and determined by the client, introducing the possibility of choice in RTT measurements.
Make the following assumptions:
Four RTTs of the spin bit according to specification would now give rise to the following data, available to an on-path observer: 0000000000000111111111111100000000000001111111111111. To estimate the time of a RTT, we could compute 13*4/4 = 13 time units.
Set Q=0.2. Now the four RTTs may instead be measured as 1001000000100111111001111100000010010110111011010111. With this sequence, we would instead estimate (1+2+1+6+1+2+6+2+5+6+1+2+ 1+1+2+1+3+1+2+1+1+1+3)/23 = 2.26. That is clearly not satisfactory if the target round-trip time estimation is 13.
Divide the RTT measurements into moving windows with k=2 (i.e., each window contains (b[-2], b[-1], b[0], b[1], b[2])) to arrive at [(10010), (00100), (01000), (10000), (00000), (00000), (00001), (00010), (00100), etc]. Each window estimates b[0], so the "true" value of bit 2 will be estimated by (10010), the true value of bit three from (00100), and so forth.
Applying the procedure we are left with 000000000011111111111111000000000011111111111111, or (10+14+14+10)/4=12. This is much better precision if the target round-trip time estimation is 13.
Now let us consider the case where both the client and server randomize each transmitted bit, with probabilities Q and P respectively. Using the same assumptions as in Section 3.2.1 and the same target RTT of 13, and letting Q=0.2 and P=0.1, we may end up measuring 0000000000000111111111011100000001010001111010011111 and throw the method of moving windows for k=2 arriving at 000000000001111111111111000000000000011111001111 leaving us with sequences of length (11, 13, 13, 5, 2, 4).
As previously mentioned, the risk of a bit being misidentified is related to P, Q and k. Because a misidentified bit always make sequences appear to be of shorter length, the sequences that measure greater length should be taken as the RTT estimate. In this event that we choose to only use that half of the esimated sequences with the greatest length as a basis for the latency calculations, we would have (11+13+13)/3=12.3 as the estimator for the RTT.
In the introduction to this section, we observed that setting Q=0.5 would make any pattern recognition among the bits extremely difficult for the most advanced of filters. We proceeded to discuss the case Q=0.2 and a potential filter for this case in Section 3.2.1. If Q is taken to be a parameter under client control, of course the client could set Q so that latency measurements are made impossible. On the other hand, such client control already exists, since the latency spin bit is optional. (see Sec. 7.2 and Section 17.3.1).
In Section 3.2.2 we introduced the possiblity of yet another parameter P, to be set by the server for determining server-side RRM application. The moving windows filtering method applied to make sense of on-path observations remains the same.
The filtering methods applied in this section consistently under-estimate the true latency. More accurate latency measurements may be achieved by having a larger number of sequences observed.
TODO
The spin bit is associated with an IP address which creates linkability (see [RFC6973] and [RFC8280]). The privacy concern associated with a spin bit is, additionally, that latency measurements will enable inferrence of the location or distance of the device associated with that particular IP address.
In Section 3.1.1, it was seen Randomized response mechanisms (RRM) would either cause the utility of the spin bit to disappear entirely (by rendering any measurement futile) or cause the primary privacy-reducing inferrence to remain a problem, as long as a sufficiently large amount sequential measurements were done. Each measurement would continue to be tied to fixed identifier, which necessarily implies privacy loss. Interestingly, Section 3.1.1 also highlights fundamental trade-offs between privacy-preserving mechanisms and measurement utility: by setting Q=0, we were able to avoid ending up in a sink, which would improve the possibility of measurement, but in doing so removed all agency from the client to falsify its responses.
In Section 3.2.1 we saw that setting Q=0.5 could obfuscate the spin edge from an on-path observer. Since the latency spin bit is an optional feature, an easier method of accomplishing such obfuscation would be to simply to turn the spin bit off. Setting Q < 0.5 would instead let the client make it easier or more difficult for the on-path observer to correctly estimate latency. In Section 3.2.1 and Section 3.2.2 we particularly conclude that under-estimation of latency is the most likely outcome of this RRM.
It is not clear that RRM would ultimately bring any particular privacy benefit beyond what is already guaranteed in the present specification of the spin bit in Section 17.3.1.