| Internet Research Task Force | A. Andersdotter |
| Internet-Draft | CENTR |
| Intended status: Informational | S. Sahib |
| Expires: January 14, 2021 | Salesforce |
| July 13, 2020 |
Randomized Response Mechanisms in RTT Measurements for QUIC
draft-andersdotter-rrm-for-rtt-in-quic-00
The latency spin bit is an optional feature included in the QUIC transport protocol, as standardized by the Internet Engineering Task Force (IETF). 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 January 14, 2021.
Copyright (c) 2020 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]. The spin bit, now incorporated in Section 17.3.1, has generated controversy from a privacy perspective, both in the Working Group meetings and on the QUIC email list. Controversies were re-ignited through the publication of a Human Rights Consideration in [TENOEVER-MARTINI] in 2019. 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 trials were originally suggested by social scientist Stanley Warner to increase response rates in surveys on sensitive topics, such as political affiliation or sexuality [WARNER]. At the flip of a coin (or other random device), a survey taker would answer the opposite question to the one that the survey giver wanted to ask. For instance, if the survey giver wants to find out whether a person has been affiliated with a communist group, the survey taker would instead answer, at some fixed probability, whether they had never been affiliated with a communist group. The effect is the same as if the survey taker would give a false answer to the survey question with some known probability.
This method provoked a flurry of statistical research throughout the 1970s and 80s, with statisticians considering a range of problems in estimation and variance reduction for estimators in the presence of noise on survey responses [RAO].
Recently, randomized response mechanisms has again gained traction, through the work of Cynthia Dwork et al on differential privacy [DWORK] or mechanisms for statistical data collection over (presumably large) user sets, such as [RAPPOR]. These developments had led to renewed interest in randomized response mechanisms in the statistical community, with text books [FOX] and handbooks [RAO] covering a large range of possible situations where randomizing responses over a set of outcomes on an individual respondent basis may still enable useful inferences about the population to which the individual belongs.
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 example), 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 a 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 [RAO] 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.
Deciding on a RRM scheme for RTT in QUIC requires a more explicitly defined mechanism for changing the spin value (the value of the spin bit being transmitted from the client or server) than presently is the case in [TRAMMEL]. For instance, the way in which the server is specified to change its spin value currently is:
"The server initializes its spin value to 0. When it receives a packet from the client, if that packet has a short header and if it increments the highest packet number seen by the server from the client, it sets the spin value to the spin bit in the received packet." (Section 2)
while the mechanism for changing the spin value in the client is
"The client initializes its spin value to 0. When it receives a packet from the server, if the packet has a short header and if it increments the highest packet number seen by the client from the server, it sets the spin value to the opposite of the spin bit in the received packet." (Section 2)
The goal of the designer in [TRAMMEL] is to cause the spin bit to change its value once per round-trip. Our design goal is different. We want to have the spin bit only sometimes change its value once per round-trip, while it might other times change its value twice per round-trip, or not at all. Additionally, we have the goal of ensuring that we can exercise control over what percentage of round-trips give useful measurements. To simultaneously fill all of those requirements, we introduce the following additional constraints on updating the spin value:
We illustrate these assumptions with a truth table for the client in Figure 6 and for the server in Figure 7.
+----------+-------+------+-------------------+
| NVclient | SLISB | LISB | NV'client |
+----------+-------+------+-------------------+
| (0) | (−) | (0) | (1)∗ |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0(q) or 1(1-q) |
| 0 | 1 | 0 | 0(q) or 1(1-q) |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1(q) or 0(1-q) |
| 1 | 1 | 0 | 1(q) or 0(1-q) |
| 1 | 1 | 1 | 1 |
+----------+-------+------+-------------------+
Figure 6: Client truth table for inversion of the client's internal spin bit value NVclient. NV'client in the right-most column constitutes a truthful inversion with probability (1−q) and a lying inversion with probability q. * A special case is the firstround-trip after initialization.
+----------+-------+------+----------------+
| NVclient | SLISB | LISB | NV'client |
+----------+-------+------+----------------+
| (0) | (−) | (0) | (0)∗ |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0(1−p) or 1(p) |
| 0 | 1 | 0 | 0(1−p) or 1(p) |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1(1-p) or 0(q) |
| 1 | 1 | 0 | 1(1-p) or 0(q) |
| 1 | 1 | 1 | 1 |
+----------+-------+------+----------------+
Figure 7: Server truth table for reflection of the server’s internal spin bit value NVserver. * A special case is the firstround-trip after initialization.
There are two conceivable ways to achieve RRM for RTT measurements:
In particular, in QUIC25 draft, section 17.1.3, a randomization mechanism is called for that renders 7/8 of all spin bit measurements non-useful for the purpose of inferring latency. This encourages us to seek some mathematical solution that can at least guarantee that 7/8 of all traffic streams to which a spin bit is attached are not useful for RTT measurements.
Simulation code for both cases discussed in this document ("RRM at each bit" and "RRM at edge transition") and instructions are hosted on GitHub.
Recall the assumptions in Section 4. Suppose that a round trip takes 2n time units. If we initialize spin bits at the client and server to 0 (assumption 3), they will both see (SLISB, LISB)=(-,0) after n time units, and an NV change is triggered (assumption 10). Now the client maintains an NV value of 1 while the server sets its NV value to 0.
The client now transmits spin bits valued 1 to the server, while the server continues to transmit spin bits valued 0 to the client. After another n time units (2n time units in total) the client sees a (SLISB, LISB)-tuple valued (0,0), while the server will see a (SLISB, LISB)-tuple (1,0) (assumption 2). This triggers an attempted reflection by the server, meaning that its NV should be changed from 0 to 1 (assumption 6), while a change in the client NV (1) is not triggered (assumption 4). Suppose that the server truthfully reflects its NV to 1. Now the client continues to transmit 1s to the server, while the server transmits 1s to the client.
After yet another n time units (3n time units in total) the server will see the (SLISB, LISB)-tuple (1,1) and therefore do nothing (assumption 8), while the client sees the tuple (0,1) and tries to update its NV (assumption 4). If the client does not do this, so that the client NV remains at 1, then the client will be transmitting 1s to the server and the server will be transmitting 1s to the client.
After 4n time units, the (SLISB, LISB)-tuples seen by both the client and the server will be (1,1), and both NVs will also be set to 1. Consequently, the (lack of) NV updates after 3n time units have landed us in the situation that there is no longer any possibility for a (SLISB, LISB)-tuple to have different values, and we have ended up in a loop.
This is encouraging, since a loop can be escaped by randomly re-initializing the spin bit after some time that we can choose.
As in the previous section, let the RTT be 2n time units. If NV[client] = NV[server] at time n, and the NVs remain equal to each other at time 2n, the process will be in a loop. If we describe the four different combinations of NVs in the following way:
(NV[client], NV[server]) = (0,0), (1,0), (0,1) or (1,1)
then, in the example above (Section 7.1), we would have the following sequence of transitions:
(0,0)[init] -> (1,0) -> (1,1) -> (1,1) \]
Referring back to the truth tables in Figure 6 and Figure 7, we can work out how these transitions exactly happen. For example, the transition (1,0) -> (1,1) can happen in the following two ways:
The client attempts to update NV[client] after receiving a triggering (SLISB, LISB)-tuple but fails to invert or it does not receive a triggering (SLISB, LISB)-tuple at all, while the server updates NV[server] truthfully after receiving a triggering (SLISB, LISB)-tuple. The server has one way of transitioning its NV from 0 to 1, while the client has two ways of transitioning its NV from 1 to 1.
We know the probabilities that reflections or inversions will not happen (assumptions 5 and 7 in Section 4), but also need to know when a triggering (SLISB, LISB)-tuple will be received. A client receives such a tuple at time kn if the server truthfully updated its NV at time (k-1)n. In fact, a loop occurs as soon as the server does not update its NV truthfully. A (SLISB, LISB)-tuple received by the client will necessarily have the form
(NV[server,t=n(k-1)], NV[server,t=n(k-2)]
and an NV update is triggered only if this tuple contains two different values. From assumption 10 in Section 4 we have that
NV[server,t=0] = NV[server,t=n] at t=0, n
and is updated only because NV[client] is updated at t=n by the same assumption. The fact that they are equal means that necessarily
NV[client,t=2n] = NV[client,t=2n]
with NV[client,t] assuming a new value only if $NV[server,s] changes. But if the server would lie once (and not update its NV), we get
NV[server,t=n(k-1)] = NV[server,t=nk] = NV[server,t=n(k+1)]
rendering the server unable to transmit values that can trigger an update of the client NV value.
With the insights from Section 7.2 we can choose p and q from Section 4, and define some re-initialization criteria for the spin bit, for an alternative mechanism to achieve the targets set out in the QUIC spin bit specification in [I-D-QUIC]:
"Each endpoint unilaterally decides if the spin bit is enabled or disabled for a connection. Implementations MUST allow administrators of clients and servers to disable the spin bit either globally or on a per-connection basis. Even when the spin bit is not disabled by the administrator, endpoints MUST disable their use of the spin bit for a random selection of at least one in every 16 network paths, or for one in every 16 connection IDs. As each endpoint disables the spin bit independently, this ensures that the spin bit signal is disabled on approximately one in eight network paths." (sec. 17.3.1)
In order to estimate the round-trip time, an on-path observer needs to have access to at least one full round-trip worth of passing spin bits. The first such accessible round-trip after initialization is the sequence of 1s transmitted by the client, if truthfully reflected by the server with probability (1-p). The second such accessible round-trip is the sequence of 0s that follow upon additionally truthful inversions and reflections by the client and server respectively. The cumulative probability of two accessible round-trips is therefore (1-p)(1-q)(1-p), and in general
P[X round-trips are complete and measurable] = (1-p)^x (1-q)^(x-1)
From this we can derive the expected value
E[X] (1-p) S[x [(1-p)(1-q)]^(x-1) = (1-p)/((1-(1-p)(1-q))^2)
where S[.] is the sum over x.
By the specification quoted above, we want this to be approximately equal to 7/8. A range of values for (p,q) can satisfy this criterion, and, for instance, if the client always tells the truth (i.e. q=0) then p=1/8, meaning that the server lies 1/8 of the time.
Once the client or server have lied for the first time, all future spin bit values cannot be used for measuring round-trip time unless the NV update process is re-initiated. This could be achieved through the client arbitrarily updating its NV in contradiction with assumption 8 of Section 4 after some period of time, which could be chosen according to a geometric distribution of some expectation r. However, in the time leading up to re-initialization the utility for an on-path observer of recording the spin bit value is nil.
It follows that the actual proportion of useless measurements will be far higher than the 1/8 that is specified in the draft.
A solution is to choose p, q so that the expected value of the number of useful round-trip measurements is higher than 7/8. If we solve for p, q when E[X] = 56/59, we would want the client to re-initiate the NV update procedure after an average of 5 round-trip periods to get an expected 56/64 = 7/8 useful measurements. This supposes, of course, that the client has a way of establishing the approximate round-trip time that is independent of the spin bit.
Additional privacy gains, or at least diminished availability of useful RTT measurements, would be achieved by solving for an expected value lower than 7/8. Since not all measurements are rendered useless by applying RRM, there will eventually always be a time when an on-path observer can make inferences about round-trip time.
It is possible to apply to RRM to QUIC RTT measurements in a way which delays estimation of RTT. However, it is unclear whether RRM has advantages larger than already existing privacy mechanisms included in the QUIC draft (such as making the spin bit optional, or requiring that 1/8 of all streams are not measurable). The privacy concern associated with a spin bit is that latency measurements will enable inference of the location or distance of the device associated with that particular IP address. But the whole point of differential privacy mechanisms, including RRM, is using statistical methods to ensure that data can be made more privacy-preserving while also preserving the data utility. In the case of the spin bit, it is the utility of the data that allegedly violates privacy, which means differential privacy is an intuitively bad tool to address privacy concerns.
The spin bit is associated with an IP address, which creates linkability. Any differential privacy mechanism will not remove linkability from the spin bit, and so preserves that angle of privacy violation.
RRM could potentially be used to fulfill requirements from [I-D-QUIC], sec. 17.3.1, in a slightly more flexible way than is currently discussed at the IETF. In particular, the parameters p, q and r could be adjusted to accommodate for any proportion of useful measurements. If r is left for the client to decide, the client may even have influence over the extent to which RTT measurements through the QUIC spin bit is made more difficult (see e.g. [RFC6973], sec. 7.2).
In order to realize such advantages the functioning of the QUIC spin bit does, however, need to be more stringently specified, in particular in line with our suggestions in Section 4.