Hello, today I will present to you our work on
reconciling anonymity with internet performance
transparency. This is joint work with my
supervisors at EPFL, Katerina Alkiraki and Brian
Hoon.
In today's internet, when packets are lost or
delayed beyond expectation, there is no
systematic way to identify the network where the
problem has occurred. This has important
implications to network users. First, users
cannot check whether internet service providers
meet service level agreements. For example, if an
ISP honors a less than 1% packet loss
promise. Second, users cannot check ISP
compliance with neutrality regulations. Consider
the
scenario on this slide where a broadband ISP
receives all traffic, this is video streaming
traffic originating at Netflix and other traffic
through the same inter-domain link. At some
point, Netflix streaming quality deteriorates due
to large delays, begging the question
why exactly? This results in a peering dispute
similar to the one between Netflix and Verizon.
Netflix blames the ISP for discriminating against
Netflix traffic while the ISP says
I am doing nothing wrong, it just so happens that
the inter-domain link is congested. The
result is an ongoing dispute during which Netflix
users experience bad video streaming
quality. So what we need is more internet
performance transparency. In other words,
we need more visibility into the performance of
the various networks that make up the internet.
Having more transparency would enable network
users to trivially check service level agreements
and neutrality regulations. However, transparency
comes at the cost of anonymity. In particular,
popular non-limiting networks like Tor
fundamentally rely on limited internet
performance transparency
in order to achieve their non-limited goals. And
this is because at a higher level, anonymity
relies on hiding the communication patterns of
users while transparency brings them into
light. Hence, the goal of this work is to
reconcile both transparency and anonymity.
But first, let me recap the properties of Tor
that are relevant to this talk. Imagine
two users, Alice and Bob, that use Tor to
communicate with each other. And they do so
by exchanging a series of packet counts we call a
flow. For example, here Alice talks
to Bob by sending to him a certain number of
packets during the first time unit, then
fewer packets during the second time unit, and it
continues like that. Tor is these three
relay nodes in the middle, or equivalently this
onion, that provides the following property.
An adversary sitting at either position 1 or
position 2 cannot tell that Alice is talking
to Bob. However, prior work shows that given
enough location diversity of the adversary,
she can de-anonymise traffic. In this example, if
Eve, the adversary, is present at both
locations 1 and 2, she can potentially tell with
high confidence that Alice is talking
to Bob. This is true when Eve sees independent
downsampled versions of the actual packet
flow at the two locations, but it is also true if
Eve does not observe a single flow
at location 2, but instead an aggregate which is
a composite of flows, the red and green
one here. The good news is that in today's
Internet, that operates in the absence of
any transparency system, it is still reasonable
to assume that such a global passive adversary
is rare. Let us take a step back. Tor is an
overlay
over the network of ISPs that make up the
Internet. We argued that we need more Internet
performance transparency, so let us explain what
is a transparency system and what are
its implications on anonymity. Building
transparency into the Internet fabric boils down
to networks
like ISPs that publish information about the
traffic they observe at their boundaries,
and then Internet users, regulators, and the
networks themselves that use this published
information to analyse its others' performance.
In particular, if an ISP joins such a
transparency
system, it would have to deploy special witness
logic where traffic enters and exits the domain.
You can see that as the orange nodes on the slide.
Witnesses observe traffic and periodically
send packet reports on traffic aggregates to a
logically centralised entity we call
the ledger. Upon having all these reports, the
ledger and anyone who has access to it
can trace problematic behaviour to specific areas
and check for compliance with service
level agreements and neutrality. However, as you
might have guessed, by deploying a
hidden transparency system, we are essentially
introducing a powerful global passive adversary.
So this talk is about assessing what this new
powerful adversary could do to anonymity,
and then given the risk, reconciling the need for
both transparency and anonymity. Here
is the roadmap of this talk. After describing the
metric we used to quantify anonymity,
we will assess the risk that a basic transparency
system would pose to anonymity. Then, to strike
a good balance between anonymity and transparency,
we will continue with our solution, which
is adjusting the time granularity of the reports.
We will conclude with some experimental results
and future work. We are considering an adversary
who aims to trace the target flow, for example
this one that Alice is using to communicate with
Bob. Let's assume that this flow is
truly contained in the red and green aggregate.
Now, suppose that concurrent to this aggregate,
the transparency system publishes two more aggregates,
the black ones on the slide. Then,
the adversary's goal reduced to determining which
of these aggregates are more likely
to contain the target flow. The adversary has the
following information. She sees the
flow's pattern, as well as the pattern of each of
the aggregates published by the transparency
system within the given time interval. What we
are searching for is an anonymity metric
that has the following properties. If the
adversary has no information, or equivalently
if she believes that all three aggregates are
equally likely to contain the target flow,
anonymity should be high. If, however, Eve is
sure that the flow is the correct aggregate,
anonymity should be low. If Eve has some
information, anonymity should lie somewhere in
between
these two anonymity points. So far, from what I
have told you, it seems that the traditional
anonymity set size is the metric we are seeking.
This is true, except for when the adversary
has misleading information. For example, if Eve
is pretty sure that an incorrect aggregate
includes the target flow, for example the bottom
one on the slide. In this case, the
traditional anonymity set size would give us low
anonymity, the red point on the slide,
but we argue that anonymity should be high, being
the blue point on the slide, because
in this case, misleading information is as if no
information. Our metric, which we call
the T-anonymity set size, addresses all this. You
can find more information about it in
our paper. Now it's time to assess the risk that
the
basic transparency system would pose anonymity.
This experiment, as well as any other experiment
I am presenting today, considers serial internet
traffic traces obtained and made available
by CAIDA in 2018. Here we have 50 target flows,
each of them being contained in a separate
aggregate out of 50 counted ones. The aggregates
are dense in the sense that each of them is
a composite of many flows, 512 here. The
intuition is that dense aggregates are highly
likely
to hide the patterns of the individual flows
because they simply contain many of them.
The basic transparency system we are examining
here reports packet counts on aggregates every
1 ms. Let us now switch to the graph. On the y-axis,
we see the cumulative distribution function, or
simply CDF, and on the x-axis, we see our
metric, the T-anonymity set size. A T-anonymity
set size of 1 is the best-case scenario for
the attacker, who successfully traces the target
flow to the correct aggregate. On the
other hand, a T-anonymity set size of 50 reflects
the worst-case scenario for the attacker,
because he thinks that all 50 aggregates are
equally likely to contain the target flow.
As a result, the attacker would like for the CDF
of the T-anonymity set size to lie towards
the left-hand side, while we aim for the opposite.
The orange curve shows the CDF of the T-anonymity
set size for the case of 1 second observation
time interval. This is simply the time window
during which the adversary knows the pattern of
the target flow and all counted aggregates.
As you can see, for the case of 1 second, things
are pretty bad for the adversary, because
now only a few flows have a fairly low T-anonymity
set size. However, things change as we increase
the observation time interval, from 1 second to
10 seconds, 1 minute, and finally 10 minutes,
because now we can see that the adversary can
more and more reliably trace flows. In
particular, for the case of 10 minutes, which
corresponds to the green curve here, there
are about 20% of the flows that are uniquely
identifiable. Also, there are about 60% of
the flows that are up to 5 anonymous, meaning
that the adversary traces them to fewer than
6 aggregates. To sum up, long observation time
intervals can result in low anonymity
for a number of flows, even in the case of dense
aggregates.
This brings us to the anonymity transparency
trade-off. Today, we have TOR, and if we deploy
a basic transparency system, we would have
perfect transparency, as shown on this point
here. This is because our transparency system can
essentially report whatever we like at
an arbitrary precision. However, anonymity can be
bad, as I have just showed you. Adding
differential privacy noise would be one approach.
However, we would end up on this left corner,
which essentially tells us that the rigorous
differential privacy guarantees come at the
cost of no transparency. You can find more
information in the paper that shows that the
straightforward application of differential
privacy would not work in our context. And
this is not surprising, because differential
privacy is not meant to be used for verifying
service level agreements or neutrality. Hence,
the focus for the rest of this talk is how
to strike a good balance between anonymity and
transparency.
However, improving anonymity is not easy, as our
solution must take into account two
more constraints. First, the TIE SPs must hide
all flows, because any of them could
be a possible target. For example, for this
aggregate shown on the slide, we don't know
a priori which of the flows will be targeted. It
could be either the red or the green flow.
Second, ISPs must make local decisions, because
we would like for them to avoid any kind of
coordination, because these are different
administrative domains.
We've seen that if we add performance
transparency to the Internet, and without
thinking much
about it, there is indeed a damage to anonymity.
To alleviate this damage, we propose that ISPs
caution the time granularity of the packet
reports before publishing them to the ledger.
Intuitively what that means is that coarser time
granularity better hides the flow patterns,
because it results in the loss of fine-grained
information that would enable a good pattern
matching between flows and aggregates. However,
it is the very same loss of detail that impacts
report utility, because the ledger may now not be
able to precisely localise in time
certain events, for example bursts of packet loss.
Still, compared to additive noise methods like
differential privacy, the advantage of
our method lies on the reliability of the reports
it produces. Packet loss rates computed
from accurate yet coarser reports will also be
perfectly accurate, albeit averaged over
longer time intervals. Let me show you how our
algorithm operates.
On the right, we see the input of the algorithm.
This is packet counts over time for the red
and green flow that make up an aggregate. Observe
here that each packet count refers
to a single time unit. Now, on the lower part, we
see the output of the algorithm. We see
again the same aggregate, namely packet counts
over time, but now observe that the granularity
for some of the reports is coarser than a single
time unit. For example, for the first
packet count, we see that it refers to both the
first and the second time unit merged.
The same happens to the next packet count, but
then you can see that for the last packet
count, it refers to a single time unit. Of course,
the question here is how coarse
to make the bins. For example, bins that last one
year may not be so useful in the context
of many applications. Given the coarsest granularity
we would be willing to tolerate, say two time
units, the next thing to do would be uniform binning.
Under uniform binning, ISPs statically
merge packet counts every two time units. However,
this static binning might not always
be the one that hides the most of flow patterns,
in which case it also introduces unnecessary
noise. What we propose instead is adaptive binning.
When an upper acceptable time granularity, its ISP,
dynamically decides how coarse or
fine-grained the reported bins of an aggregate
should be, so as to hide the worst of flow.
You can think of this flow as a virtual flow,
namely a composite of real flows, which has
a property that leaks the most across real flows
for a given binning.
To better explain what I mean, let's go back to
the previous example. On the right,
we see again packet counts over time for an
aggregate that consists of the red and green
flow. On the left, we see the leakage for each of
these flows. The goal of the adaptive
binning technique is to improve the leakage for
each flow, and this leakage captures the
likelihood that the respective flow belongs to
the correct aggregate.
Here we have at least two options with respect to
binning. We could bin with the red or the
green flow in mind. When binning according to the
red flow, our goal translates to hiding
the vulnerable part of this flow, which is this
packet burst that occurs in the first
half of the observation window. One binning that
accomplishes this goal is this one. In
that case, the leakage for the red flow you can
see that it improves, however this is
not the case for the green flow, for which the
leakage may stay the same or even increase,
as is the case here. If we bin now according to
the green flow, we would get similar results.
The takeaway here is that we must co-optimize for
both flows, because optimizing independently
for each of them may result in some flow left
exposed. And this is exactly what we do through
the virtual flow construct. The purple binning
shows the binning that minimizes the leakage
for the virtual flow, which is this one here, and
this flow upper bounds the leakage for
both the red and the green flow. As a result, if
you look at this purple point, both flows'
leakage benefit from this binning. Now that I
have presented to you our solution,
it is time to evaluate how this solution improves
flow anonymity. The experimental setup stays
the same as before. The focus is on the 10-minute
observation case that proved to be challenging
before, because the attacker could de-anonymize a
large number of flows. The graph shows again
the CTF of the 10-unlimited set size. The green
curve corresponds to the basic transparency
system we have examined before, and the blue one
corresponds to our adaptive binning solution,
subject to the constraint that no bin can be
larger than 64 ms.
There are a few important things we can observe
here. First, with our solution, uniquely identifiable
flows no longer exist. Second, our solution achieves
approximately a 4.4 times improvement
for up to 5 anonymous flows, because you can see
that there were around 60% of the flows
that were up to 5 anonymous before, and we have
managed to bring that down to less than
2. But most importantly, these improvements are
achieved at a sub-second granularity.
Remember that here the coarse-spec bin is 64 ms.
That means that many applications can
benefit from the packet loss rates that our
system exposes.
In the paper, you can find an extensive
evaluation of our algorithm that includes other
experimental
setups like sparse aggregates, Poisson traffic,
and another special type of traffic we call
ONO. The results I have presented to you today
are representative of these other setups.
Also, in the paper we examined the cost of
differential privacy to report utility, and
we also show that differential privacy noise
would result in packet loss estimates that
differ from the actual ones by tens of percentage
points.
Finally, you can see how our algorithm scales,
meaning that our algorithm is deployable.
To conclude, if not carefully thought,
transparency can greatly damage the anonymity. We
also
find that adding noise to the traffic reports
shows to ensure differential privacy would
make the reports unusable in the context of a
transparency system. Instead, we propose
Morphit, an algorithm that courses the time-granularity
of traffic reports in order to hide the flow
patterns that are most vulnerable to tracing. Our
solution navigates the anonymity-transparency
trade-off in an intuitive way and proves to be
useful in many realistic scenarios.
Of course, there are many other aspects of
interim performance transparency we are currently
working on or we are interested to address in
future work. For example, whether an alternative
solution that leverages ISP coordination would
achieve a better trade-off still remains an
open question. Also, our ongoing work focuses on
the trustworthiness of performance metrics,
because to improve their competitiveness,
networks may have an incentive to lie and
claim better than the true performance. Another
aspect of interim transparency also pertains
to privacy. However, this time the focus is not
users but networks themselves. Specifically,
we are interested in hiding the topology of
networks because it is possible to reverse-engineer
a topology given intra-network path delays trivially
exposed by transparency systems.
With that, I would like to thank you and I am now
ready to take any questions that you
may have.