[tor-dev] Using Traceroute for AS-Path prediction

[A. Johnson]

Hello Simon,

> I am a student at the saarland university and currently workin on my bachelor thesis concerning AS-path prediction using traceroute.
> I want to correlate open-source BGP data and corresponding traceroute measurements. In the end I want to argue whether or not traceroute
> can be valid tool for live as-path prediction based on the matching and representation of changes in the respective (AS-)routes over time.

Myself and colleagues at UIUC recently looked at exactly this issue. We had a project called the “Trying Trusted Tor Traceroutes” in which some very nice relay operators ran a traceroute script that we wrote and sent us the results. The script did traceroutes from the relays to Tor relay, to each BGP-announced prefix, and finally to each /24 subnet (although we didn’t get enough of the /24 results to use). We then looked at how often AS-path and IXP (Internet Exchange Point) predictions matched the observations from traceroutes. It turns out that AS-path prediction using the state-of-the-art algorithm (Qui and Gao’s algorithm) is occasionally wrong in ways that matter for Tor security, and IXP prediction at the AS level (using the techniques of the IXP Mapping Proect) hugely over-predict IXP presence. We have written up these results, and they are available at <http://arxiv.org/abs/1410.1823>.

> I already did a preliminary measurement during which I gathered 2 month worth of traceroute information to different tor-nodes and correlated them
> with the BGP data available at RIPE-RIS. It turned out, that routes predominantly matched and that a high percentage of bgp route
> changes were also present in traceroute routes. Though only a smaller number of traceroute route changes were present in bgp routes.
> This leads to the assumption that traceroute might be a good as-path measurement-tool, as it would be quite unlikely that BGP AS Paths would
> match AS paths derived from traceroute measurements if traceroute could not reliable measure them.
> This information was only inferred from only one measurement point, though.

This sounds consistent with what we found. I wonder why you consider the BGP announcements more reliable than the traceroutes, though. I actually consider the traceroutes more likely to accurately state the IPs (and thus the ASes) that a packets travels through.

> As this topic may also be of interrest to tor I was wondering if anyone had some opionions on the general idea or knew
> some papers/researcher which are on the same track. I already read:
> * Towards an Accurate AS-Level Traceroute Tool
> * Quantifying the Pitfalls of Traceroute in AS Connectivity
> * Inferring AS-level Internet Topology from Router-Level Path Traces
> * A Study on Traceroute Potential in Revealing the Internet AS-Level Topology
> * Mixing Biases: Structure Changes in the AS Topology Evolution
> but I have the nagging feeling that there should be more.
Some more papers that might help you:
  - "Avoiding traceroute anomalies with Paris traceroute”, IMC 2006 <http://conferences.sigcomm.org/imc/2006/papers/p15-augustin.pdf>
  - "Building an AS-topology model that captures route diversity”, SIGCOMM 2006 <https://dl.acm.org/citation.cfm?id=1159937>
  - “A Longitudinal and Cross-Dataset Study of Internet Latency and Path Stability”, UC Berkeley Technical Report UCB/EECS-2014-172, October 2014 <http://www.eecs.berkeley.edu/Pubs/TechRpts/2014/EECS-2014-172.pdf>

> Further I am looking for a way to establish more measurement points to ensure a diversity in the data collection. Those points have to be in AS-peers
> of either the route-views project (zebra routers) or RIPE-RIS so I can also access the corresponding MRT-Data. I figured that traceroute.org Looking Glass
> may provide a way of doing so, but I am afraid that the overlap of Looking Glass servers and public BGP-peers is very small. Any idea on how
> to establish diverse measurementpoints (maybe volunteers) would be greatly appreciated.

Looking Glass seems like an excellent option to me. Some Looking Glass servers provide both traceroute and BGP information, which seems like exactly what you need. You may get some help from Prof. Reza Rejaie at the University of Oregon, whose students have developed a list of useful Looking Glass servers and scripts to automate querying them that you may find useful. I would also suggest looking at M-Lab servers (http://www.measurementlab.net/). PlanetLab servers are an obvious choice for running traceroutes, but I don’t know how many of them are in ASes that provide BGP data.

Good luck with the project! I will be interested to see what you find out.

Best,
Aaron