I spent some time improving the existing relay uptime visualisation [0]. Inspired by a research paper [1], the new algorithm uses single-linkage clustering with Pearson's correlation coefficient as distance function. The idea is that relays are grouped next to each other if their uptime (basically a binary sequence) is highly correlated. Check out the following gallery. It contains monthly relay uptime images, dating back to 2007: https://nymity.ch/sybilhunting/uptime-visualisation/
If you aren't familiar with this type of visualisation: Every image shows the uptime of all Tor relays that were online in a given month. Every row is a consensus and every column is a relay. White pixels mean that a relay was offline and black pixels means that a relay was online. Red pixels are used to highlight suspiciously similar clusters. A nice example is the Heartbleed incident: https://nymity.ch/sybilhunting/uptime-visualisation/slide_2014-04.html The huge red block on the left shows all the relays that were removed by the directory authorities because they didn't rotate their key pairs in time.
The downside of single-linkage clustering is that it takes longer to compute. On my laptop, I can create an image covering one month in under three minutes, so it's tolerable.
Another practical problem is that it's cumbersome to learn the relay fingerprint of a given column. I'm looking into JavaScript/HTML tricks that can show text when you hover over a region in the image. Perhaps somebody knows more?
[0] https://bugs.torproject.org/12813 [1] http://nms.csail.mit.edu/papers/clustering-imw2002.pdf, Section 2
Cheers, Philipp
On Mon, Dec 07, 2015 at 02:51:23PM -0500, Philipp Winter wrote:
I spent some time improving the existing relay uptime visualisation [0]. Inspired by a research paper [1], the new algorithm uses single-linkage clustering with Pearson's correlation coefficient as distance function. The idea is that relays are grouped next to each other if their uptime (basically a binary sequence) is highly correlated. Check out the following gallery. It contains monthly relay uptime images, dating back to 2007: https://nymity.ch/sybilhunting/uptime-visualisation/
How about just taking the XOR of two sequences as the distance?
It would be interesting to know if there are any near-perfect anticorrelations; i.e., one relay starts when another stops.
Another practical problem is that it's cumbersome to learn the relay fingerprint of a given column. I'm looking into JavaScript/HTML tricks that can show text when you hover over a region in the image. Perhaps somebody knows more?
One way is to set an onmousemove handler that inserts text into a preexisting element. For example (untested):
<div id=output> </div>
var OUTPUT_ELEM = document.getElementById("output"); /* Get an event's coordinates relative to a given element. */ function elem_coords(event, elem) { var rect = elem.getBoundingClientRect(); /* http://stackoverflow.com/a/872537 */ if (typeof pageXOffset !== "undefined") { scrollLeft = pageXOffset; scrollTop = pageYOffset; } else if (document.documentElement !== undefined && document.documentElement.clientHeight !== undefined) { scrollLeft = document.documentElement.scrollLeft; scrollTop = document.documentElement.scrollTop; } else { scrollLeft = document.body.scrollLeft; scrollTop = document.body.scrollTop; } var x = event.pageX - (scrollLeft + rect.left); var y = event.pageY - (scrollTop + rect.top); return { x: x, y: y }; } function onmousemove_callback(event) { var c = elem_coords(event, img_element); OUTPUT_ELEM.innerText = get_text_for_coordinates(c.x, c.y); }
On Mon, Dec 07, 2015 at 01:44:47PM -0800, David Fifield wrote:
On Mon, Dec 07, 2015 at 02:51:23PM -0500, Philipp Winter wrote:
I spent some time improving the existing relay uptime visualisation [0]. Inspired by a research paper [1], the new algorithm uses single-linkage clustering with Pearson's correlation coefficient as distance function. The idea is that relays are grouped next to each other if their uptime (basically a binary sequence) is highly correlated. Check out the following gallery. It contains monthly relay uptime images, dating back to 2007: https://nymity.ch/sybilhunting/uptime-visualisation/
How about just taking the XOR of two sequences as the distance?
Here's Nov 2015, with XOR as distance: https://nymity.ch/sybilhunting/uptime-visualisation/xor-distance.png
It would be interesting to know if there are any near-perfect anticorrelations; i.e., one relay starts when another stops.
It looks like there's many of them. So far, I calculated the correlation as 1 - Pearson(s1,s2) because I'm only interested in positively correlated sequences. Here's an uptime image with Pearson(s1,s2) as distance function, so positive correlation is considered just as much as negative correlation. Have a look at the leftmost part: https://nymity.ch/sybilhunting/uptime-visualisation/anticorrelation.png
Cheers, Philipp
I spent some time improving the existing relay uptime visualisation [0]. Inspired by a research paper [1], the new algorithm uses single-linkage clustering with Pearson's correlation coefficient as distance function. The idea is that relays are grouped next to each other if their uptime (basically a binary sequence) is highly correlated. Check out the following gallery. It contains monthly relay uptime images, dating back to 2007: https://nymity.ch/sybilhunting/uptime-visualisation/
nice graphs!
you can also spot - all the daily hibernating relays roughly starting at the same time but finishing their allocated amount of traffic at different times
- the 130 relays of the 11BX.. group. (2015-10-30 - 2015-11-02)
and every column is a relay. White pixels mean that a relay was offline and black pixels means that a relay was online. Red pixels are used to highlight suspiciously similar clusters.
I assume they are highlighted only if they exceed a certain group size? What is the threshold?
Until I looked at the heartbleed example I assumed grouping requires "perfect matches" across the entire month but after seeing the heartbleed example I'm not sure whether that is actually the case or if two distinct groups are just next to each other and do not have a "separator" between them.
Another practical problem is that it's cumbersome to learn the relay fingerprint of a given column.
That would indeed make these graphs a lot more useful, but having a raw time and group size alone would already be enough to look them up indirectly - if that event is unique.
I would also find it useful to have it accept fingerprints as input and graph their uptime to look at a given set of relays in certain cases
example input could be the fingerprints from [1]+[2] after these relays have been around for some time.
Are you planing to generate these graphs on an ongoing basis?
[1] http://article.gmane.org/gmane.network.onion-routing.ornetradar/613 [2] http://article.gmane.org/gmane.network.onion-routing.ornetradar/617
On Mon, Dec 07, 2015 at 09:57:18PM +0000, nusenu wrote:
and every column is a relay. White pixels mean that a relay was offline and black pixels means that a relay was online. Red pixels are used to highlight suspiciously similar clusters.
I assume they are highlighted only if they exceed a certain group size? What is the threshold?
Exactly. Groups >= 5 are considered for highlighting.
Until I looked at the heartbleed example I assumed grouping requires "perfect matches" across the entire month but after seeing the heartbleed example I'm not sure whether that is actually the case or if two distinct groups are just next to each other and do not have a "separator" between them.
Right, I don't use perfect matching, so we can account for some noise, e.g., some of the Sybils having small downtimes, or not starting and stopping at the exact same hour. Here's the code: https://gitweb.torproject.org/user/phw/sybilhunter.git/tree/uptime.go#n247
I would also find it useful to have it accept fingerprints as input and graph their uptime to look at a given set of relays in certain cases
example input could be the fingerprints from [1]+[2] after these relays have been around for some time.
Good point. That has been on my todo list and I hope to get it done soon.
Are you planing to generate these graphs on an ongoing basis?
Yes, I would like to. We could easily generate them every other hour, or even hourly. The details will depend on this thread, Karsten started: https://lists.torproject.org/pipermail/tor-dev/2015-December/010017.html
Cheers, Philipp
Philipp Winter:
Red pixels are used to highlight suspiciously similar clusters.
Last year [1] there were a few huge groups, 3 of them are not flagged (black lines, not red) even though they look like a perfectly matching group?
[1] https://nymity.ch/sybilhunting/uptime-visualisation/slide_2014-12.html
On 7 December 2015 at 13:51, Philipp Winter phw@nymity.ch wrote:
I spent some time improving the existing relay uptime visualisation [0]. Inspired by a research paper [1], the new algorithm uses single-linkage clustering with Pearson's correlation coefficient as distance function. The idea is that relays are grouped next to each other if their uptime (basically a binary sequence) is highly correlated. Check out the following gallery. It contains monthly relay uptime images, dating back to 2007: https://nymity.ch/sybilhunting/uptime-visualisation/
If you aren't familiar with this type of visualisation: Every image shows the uptime of all Tor relays that were online in a given month. Every row is a consensus and every column is a relay. White pixels mean that a relay was offline and black pixels means that a relay was online. Red pixels are used to highlight suspiciously similar clusters.
That's really cool. It seems to imply that the majority of the tor network stop operating halfway through the month though... Do the other tor graphs take into account hibernating relays? For example, I would expect the time-to-download graph would be somewhat affected: https://metrics.torproject.org/torperf.html?graph=torperf&start=2015-10-...
Another practical problem is that it's cumbersome to learn the relay fingerprint of a given column. I'm looking into JavaScript/HTML tricks that can show text when you hover over a region in the image. Perhaps somebody knows more?
Besides David's way, you could also do this with <canvas>. Stick the image in the back of a canvas, then get the mouse coordinates like so: http://www.html5canvastutorials.com/advanced/html5-canvas-mouse-coordinates/ You can detect a click and use it to display the data below. You could also use it to show a zoomed-in version of the surrounding area on another canvas below, and then let the user click in _that_ canvas to actually load details. (Since no one can do pixel-perfect clicking.)
-tom
On 8 Dec 2015, at 10:43, Tom Ritter tom@ritter.vg wrote:
On 7 December 2015 at 13:51, Philipp Winter <phw@nymity.ch mailto:phw@nymity.ch> wrote:
I spent some time improving the existing relay uptime visualisation [0]. Inspired by a research paper [1], the new algorithm uses single-linkage clustering with Pearson's correlation coefficient as distance function. The idea is that relays are grouped next to each other if their uptime (basically a binary sequence) is highly correlated. Check out the following gallery. It contains monthly relay uptime images, dating back to 2007: <https://nymity.ch/sybilhunting/uptime-visualisation/ https://nymity.ch/sybilhunting/uptime-visualisation/>
If you aren't familiar with this type of visualisation: Every image shows the uptime of all Tor relays that were online in a given month. Every row is a consensus and every column is a relay. White pixels mean that a relay was offline and black pixels means that a relay was online. Red pixels are used to highlight suspiciously similar clusters.
That's really cool. It seems to imply that the majority of the tor network stop operating halfway through the month though... Do the other tor graphs take into account hibernating relays? For example, I would expect the time-to-download graph would be somewhat affected: https://metrics.torproject.org/torperf.html?graph=torperf&start=2015-10-... https://metrics.torproject.org/torperf.html?graph=torperf&start=2015-10-01&end=2015-10-31&source=all&filesize=5mb
Hibernating relays run from the start of their first period to gauge load. Then they start at a random time during the day/month, but early enough that they think they'll still use all their bandwidth.
I wonder if we're seeing another phenomenon? (daily / monthly server restarts?) Or we could be seeing hibernation failing to work as intended.
Tim
Tim Wilson-Brown (teor)
teor2345 at gmail dot com PGP 968F094B
teor at blah dot im OTR CAD08081 9755866D 89E2A06F E3558B7F B5A9D14F
On Tue, Dec 08, 2015 at 10:47:08AM +1100, Tim Wilson-Brown - teor wrote:
On 8 Dec 2015, at 10:43, Tom Ritter <[1]tom@ritter.vg> wrote: On 7 December 2015 at 13:51, Philipp Winter <[2]phw@nymity.ch> wrote: I spent some time improving the existing relay uptime visualisation [0]. Inspired by a research paper [1], the new algorithm uses single-linkage clustering with Pearson's correlation coefficient as distance function. The idea is that relays are grouped next to each other if their uptime (basically a binary sequence) is highly correlated. Check out the following gallery. It contains monthly relay uptime images, dating back to 2007: <[3]https://nymity.ch/sybilhunting/uptime-visualisation/> If you aren't familiar with this type of visualisation: Every image shows the uptime of all Tor relays that were online in a given month. Every row is a consensus and every column is a relay. White pixels mean that a relay was offline and black pixels means that a relay was online. Red pixels are used to highlight suspiciously similar clusters. That's really cool. It seems to imply that the majority of the tor network stop operating halfway through the month though... Do the other tor graphs take into account hibernating relays? For example, I would expect the time-to-download graph would be somewhat affected: [4]https://metrics.torproject.org/torperf.html?graph=torperf&start= 2015-10-01&end=2015-10-31&source=all&filesize=5mbHibernating relays run from the start of their first period to gauge load. Then they start at a random time during the day/month, but early enough that they think they'll still use all their bandwidth.
I wonder if we're seeing another phenomenon? (daily / monthly server restarts?) Or we could be seeing hibernation failing to work as intended.
Relays turn on or off all the time. Of all the descriptors seen in a year, less than 10% are continuously running the whole time. The rest either started at some time or stopped at some time or both. See an example here for 2014: https://people.torproject.org/~dcf/graphs/microdescs/microdescs-2014-short.p... All we're seeing is the distributions of the dates at which the subset of relays that stopped during the month actually stopped, which seems pretty uniform. I'll bet that if you look at those relays in the previous month, they are running at the end of the month, not hibernating.
On Mon, Dec 07, 2015 at 05:43:01PM -0600, Tom Ritter wrote:
On 7 December 2015 at 13:51, Philipp Winter phw@nymity.ch wrote:
I spent some time improving the existing relay uptime visualisation [0]. Inspired by a research paper [1], the new algorithm uses single-linkage clustering with Pearson's correlation coefficient as distance function. The idea is that relays are grouped next to each other if their uptime (basically a binary sequence) is highly correlated. Check out the following gallery. It contains monthly relay uptime images, dating back to 2007: https://nymity.ch/sybilhunting/uptime-visualisation/
If you aren't familiar with this type of visualisation: Every image shows the uptime of all Tor relays that were online in a given month. Every row is a consensus and every column is a relay. White pixels mean that a relay was offline and black pixels means that a relay was online. Red pixels are used to highlight suspiciously similar clusters.
That's really cool. It seems to imply that the majority of the tor network stop operating halfway through the month though... Do the other tor graphs take into account hibernating relays? For example, I would expect the time-to-download graph would be somewhat affected: https://metrics.torproject.org/torperf.html?graph=torperf&start=2015-10-...
What I forgot to mention: In all diagrams, I removed relays that were always online, because an all-online uptime sequence isn't useful to find Sybils. In Nov 2015, for example, we had 10,984 unique relays by fingerprint and 3,202 (29%) were always online, and are not shown in the visualisation.
Also, here are the steps to reproduce:
wget https://collector.torproject.org/archive/relay-descriptors/consensuses/conse... tar xvJf consensuses-2015-11.tar.xz go get git.torproject.org/user/phw/sybilhunter.git sybilhunter -data consensuses-2015-11/ -uptime
Cheers, Philipp
Can a one be generated covering each year and maybe a five year one. And three other check sets but sorted left to right by first online date FP AS
As to the actual FP's, all I can think of is including a second text file with pixel number to FP mappings. Or some "maps" style online zooming.
On Mon, Dec 07, 2015 at 11:43:38PM -0500, grarpamp wrote:
Can a one be generated covering each year and maybe a five year one.
I haven't checked the complexity of the clustering algorithm I use, but it's probably quadratic. I think a full year worth of uptimes would require pruning the data, e.g., remove all relays that were online for only one or two hours.
For now, here's three months, Sep 2015 to Nov 2015, in a 12 MiB file: https://nymity.ch/sybilhunting/uptime-visualisation/sep2015-nov2015.jpg
Cheers, Philipp
Also, here are the steps to reproduce:
wget https://collector.torproject.org/archive/relay-descriptors/consensuses/conse... tar xvJf consensuses-2015-11.tar.xz go get git.torproject.org/user/phw/sybilhunter.git sybilhunter -data consensuses-2015-11/ -uptime
How much of an effort would it be to support onionoo files as input data? (onionoo data would be able to display more data like AS, CC, first-seen) I could provide some archived onionoo data.
On Tue, Dec 08, 2015 at 04:52:45PM +0000, nusenu wrote:
Also, here are the steps to reproduce:
wget https://collector.torproject.org/archive/relay-descriptors/consensuses/conse... tar xvJf consensuses-2015-11.tar.xz go get git.torproject.org/user/phw/sybilhunter.git sybilhunter -data consensuses-2015-11/ -uptime
How much of an effort would it be to support onionoo files as input data? (onionoo data would be able to display more data like AS, CC, first-seen) I could provide some archived onionoo data.
It's not trivial, but feasible. Sybilhunter uses a Go-based descriptor parsing library [0] that doesn't support Onionoo's format; so an Onionoo parser is necessary, and an update to sybilhunter's uptime analysis code.
[0] https://gitweb.torproject.org/user/phw/zoossh.git/
Cheers, Philipp
-
David Fifield -
grarpamp -
nusenu -
Philipp Winter -
Tim Wilson-Brown - teor -
Tom Ritter