Bridge stability

[Karsten Loesing <karsten.loesing@xxxxxxx>]

Hi everybody,

we have been wondering how useful the sets of bridges are that we are giving out to users. Some people complained to us that the bridges we give them aren't usable even a few hours later. So, let's give them more bridges, right? Or are these people just the unlucky ones, and everybody else is happy with what they got? We don't want to give out too many bridges at once to make it harder for an adversary to enumerate all the bridges. So, what's the number of bridges we should give out?

As you may know, whenever we receive a user request asking for bridges via e-mail or HTTP, we reply with a subset of 3 bridges, at least 1 of them running on port 443. The question I'm trying to answer here is: how long will at least one of these bridges be around? I took a look at our archives of bridge descriptors [0] to find an answer to this question.

I generated a graph [1] on the fraction of random bridge subsets containing at least 1 running bridge throughout 6, 24, 48, or 96 hours. I generated this graph by taking 1000 samples of 3 bridges (with at least one running on port 443) and looking how long at least one of them kept running over said 6, 24, 48, or 96 hours. As an example, if the graph contains a data point at 0.9 that means that 90% of all samples taken at that time had at least 1 bridge running (not necessarily the same one) at any time for the stated number of hours after that data point.

The graph has one unusual data point on December 11 where the 96-hours line drops to zero; this data point is probably an artifact of the simulation and is safe to ignore. Other than that, all lines decline around December 21 for a few days and at a couple other days, too; my first impression is that the bridge authority loses its state on Running bridges after a reboot and identifies bridges as not running though in fact they are. So, it might be that bridge availability is better here than the analysis tells us here.

As comparison, I also made graphs for subsets of 2 and of 4 bridges [2, 3], both of which containing at least 1 bridge on port 443. Unsurprisingly, the availability declines with only 2 bridges and improves with 4 bridges. However, even though availability improves for 4 bridges on average, the drops around December 21 and the other dates still stand out. This further strengthens the assumption that it's just the bridge authority thinking that bridges are offline, not that bridges are really down.

So, are these good news? Personally, I had expected worse results. During most of the time, availability is surprisingly high. An 80% chance of the bridges working even after 96 hours seems fair. That means in 1 out of 5 cases someone needs to send a second e-mail or make a second website request. We might even think (or have already thought) about implementing a bridge update functionality where users go to the bridge authority and exchange their broken bridges for working ones---as long as at least one of their bridges still works.

I should state that there is one major inaccuracy in the analysis: Bridges that change their IP address are not reachable by their clients anymore. In theory, clients are able to download updated bridge descriptors from the bridge authority to learn about new IP addresses, but this functionality is not implemented yet. However, I cannot take changing IP addresses into account for this analysis, because I removed the IP addresses when sanitizing the bridge descriptors. Hah! Maybe we should just fix this problem by implementing the missing functionality.

Another minor issue that Roger told me is that the bridge authority assigns the Stable flag to almost every bridge. If there was a sane way of assigning the Stable flag and we gave out, say, at least 1 bridge with the Stable flag, would this improve availability? This is rather hard to simulate. Maybe we should fix the Stable flag for bridges and run this analysis a second time as soon as we have some data. So many things to fix...

For those who'd like to experiment with this analysis, I made a tarball available [4] containing the Java application that does the parsing and the R script for plotting the graphs. You'll need to download the December 2009 [5] and January 2010 bridge descriptors [6] and change randomBridges in the source code to reproduce these results. You'll also install ggplot2 in R using the command 'install.packages("ggplot2")' without 's.

--Karsten

[0] http://metrics.torproject.org/data.html#bridgedesc
[1] http://freehaven.net/~karsten/volatile/bridge-stability-default.png
[2] http://freehaven.net/~karsten/volatile/bridge-stability-2-bridges.png
[3] http://freehaven.net/~karsten/volatile/bridge-stability-4-bridges.png
[4] http://freehaven.net/~karsten/volatile/bridge-stability.tar.gz
[5] http://archive.torproject.org/tor-metrics-archive/bridge-descriptors-2009-12.tar.bz2
[6] http://archive.torproject.org/tor-metrics-archive/bridge-descriptors-2010-01.tar.bz2