[tor-dev] Quantifying the similarity between Tor relays

[Philipp Winter]

It is often helpful to determine the similarity between relay
descriptors.  For example, to detect Sybil attacks, or to find partners
in crime once we found a malicious relay.  I recently added code to
sybilhunter that can automate this task.

Now to the underlying theory.  The algorithm makes use of a vantage
point tree (vp-tree), which enables O(log n) search for nearest
neighbours.  We then take a file as input -- for example a consensus
document -- and add every relay to the vp-tree.  For node comparison,
vp-trees require a distance metric in the mathematical sense, i.e., the
metric has to satisfy the triangle inequality.  For now, I use the
Levenshtein distance.  It takes as input two strings and returns the
number of character edit operations (replace, insert, remove) that are
necessary to turn descriptor A into descriptor B.  While easy to
understand and use, the Levenshtein distance cannot easily incorporate
our domain-specific knowledge.  I hope to find something more suitable.

Before comparing relay descriptor, I preprocess them.  For network
status documents, I consider nickname, ports, publication time, flags,
version, and bandwidth.  I believe this is a good start, but there is
much room for improvement and feedback is very welcome.

Now here's how you can give it a shot.  The commands below find the 10
closest relays to the relay we run at Karlstad University:

  $ go get git.torproject.org/user/phw/sybilhunter.git
  $ wget https://www.nymity.ch/~phw/sample-consensus -O /tmp/consensus
  $ sybilhunter -data /tmp/consensus -neighbours 10 -rootrelay 9B94CD0B7B8057EAF21BA7F023B7A1C8CA9CE645

On my laptop, it takes approximately 10 seconds to generate the vp-tree.
The output then consists of 10 blocks that represent the most similar
relay descriptors.  The first two lines of each block show the input to
the Levenshtein distance.  The third line shows the distance and a link
to the relay's Atlas page.

Cheers,
Philipp