Reverse Traceroute

Traceroute is a useful network diagnostic tool for basic probing of the network, giving an idea of the routing path and a latency between source and destination nodes on the network. As a brief refresher, traceroute hopes to find every router hop between source and destination by repeatedly sending packets towards the destination with ever-increasing IP TTL values (starting with a TTL of 1), knowing that routers will decrease the TTL at each hop, and that given a packet with a TTL of 0, should drop it and send a ICMP Time Exceeded message back to the source. Traceroute keeps track of which TTL value produced which ICMP response from which router while also timing the response time from the moment the destination packet was sent to the moment an ICMP response was received from a router on path that has dropped the packet.

Symmetry Assumption

Unfortunately, traceroute only reveals the routers present on the path source-to-destination. The authors of the paper argue that given this, we’re limited to assuming routing symmetry: we assume the path (the routers traversed by the packet) from node A to B on the network is the same as the path from B to A. This isn’t necessarily the case, due to traffic engineering, peering agreements, link capacity, and more.

One simple solution would be to ask the destination node to perform a traceroute to the source: having both of these traceroutes, we have both the path and reverse-path from source to destination, no need to assume symmetry. However, the destination is rarely under the control of the initiator of the traceroute so this simple solution can rarely be used.

One example given in the paper is Google trying to understand the reason for performance problems for a given client. What path are the client’s packets taking when reaching the Google servers? Google servers can run a traceroute towards the client but that won’t give them the client-to-server route.

Another striking, practical and fleshed out example is presented as a case study in §6.1.

IP Record Route (RR)

From the paper: “With this option set, a[n IP packet] records the router interfaces it encounters. The IP standard limits the number of recorded interfaces to 9; once those fill, no more interfaces are recorded.”

A ping (echo request) packet with the RR option will, on its way to the destination, record the router interfaces it encounters; the echo reply generated by the destination is supposed to copy the recorded information so far, from the echo request to the newly-formed echo reply packet. On it’s way back to the source, the echo reply should continue to collect router information.

If there were only 9 roundtrip hops between source and destination, the source would know the full network path between source and destination.

Incremental Return Path With RR

If the destination is 8 hops or less away from the source, the source can still send a packet with RR set. It will not get the entire path back from the destination, but it will get 1 hop or more on the return path. The source can then issue a packet, with RR set, to the closest hop discovered on the return path. The source continues to send packets with RR to yet closer hops until it has built the full reverse path.

RR Alone Is Not Enough

Unfortunately, not all destinations are 8 hops or less away. The paper discusses different techniques to address this issue while still making use of RR.

Overview Of Reverse Traceroute Technique

Vantage Points

The authors make use of vantage points: servers present peppered around the globe, that are spaced out from each other from a routing perspective. The idea is that any destination, that the source is interested in, is reachable from at least one vantage point without too many hops, even if the source is far away.

Building An Atlas

The vantage points near the destination, using normal traceroute, can identify routing paths from themselves to the source. While this is not the path from the destination to the source, it builds an atlas of paths that are near the destination and head back towards the source.

IP-Source Spoofing

Finally, a vantage point sends a spoofed IP packet to the destination, with the record-route option set. The spoofed packet, while emitted by the vantage point, has its IP source field set to the source’s IP. As such, when the packet reaches the destination, the destination will generate a packet heading for the source, not the vantage point.

Due to the RR option, the packet heading towards the source should continue to add routers it encounters.

Putting It All Together

The reason behind the atlas built by the vantage points is that the packet heading towards the source will eventually reach a router mapped out in the atlas. As soon as the destination’s packet has hit (and recorded) any of the atlas’ mapped routes towards the source, the technique assumes the packet will travel along the same path as the atlas has already drawn.

From the paper:
reverse_traceroute_overview.png

Incremental Return Path With RR, From Vantage Points

Exactly like building an incremental return path from source, if a vantage point is 8 hops or less from the destination, it can send a spoofed packet to the destination with RR set. The source will receive the packet from the destination, and receive 1 or more routers on the return path.Exercise is repeated with a vantage point (possibly different than the first) that’s 8 hops away from the closest router discovered so far.

Out Of Vantage Point Range; Using IP Timestamp Option

Let’s imagine all vantage points are 9 hops out from a router discovered on the reverse path. In this case, the authors rely on another IP option. From the paper: “IP timestamp option (TS): IP allows probes to query a set of specific routers for timestamps. Each probe can specify up to four IP addresses, in order; if the probe traverses the router matching the next IP address that has yet to be stamped, the router records a timestamp. The addresses are ordered, so a router will not timestamp if its IP address is in the list but is not the next one.”

IP TS is used to confirm that a certain hop/router exists somewhere on the reverse path, even if it’s not exactly known where it lies on the path. The authors assume the system has some vague ideas of routers around the area, from other classic router mapping efforts. In that case, using TS, the source can ask the destination to timestamp the packet and then the out-of-reach suspected router to also timestamp the packet. The suspected router will only timestamp the packet if it sees it at all and also only if the destination has already timestamped it, ensuring it’s on the return path.

If the suspected router did not timestamp the packet, it means it’s not on the reverse path; another router suspected to be on the reverse path can be tried. This laborious process continues until a router on the reverse path is encountered that’s on the atlas built by vantage points earlier.

Spoofing When TS Is Blocked

If the source is unable to send a TS packet because of packet-filtering, a vantage point can be used to spoof a TS packet instead.

Spoofing When Destination Does Not Timestamp

The authors remark that sometimes the destination does not timestamp. Without the destination’s timestamp, one can’t be sure if a router timestamped a packet on the source-to-destination path or on the reverse path. The authors propose that if the destination does not timestamp, a vantage point spoofing a TS packet can again be used.

For this occasion, the vantage point must make sure the router in question isn’t first on its own path to the destination. An initial non-spoofed TS packet is sent from the vantage to the destination; this TS packet asks the router to timestamp the packet. If the timestamp is absent, the vantage points know that that particular router isn’t sitting somewhere between it and the destination. The vantage point then sends a spoofed TS packet to the destination, again asking the router to timestamp the packet. If the source receives this spoofed packet with the timestamp, one can deduce the router is on the reverse path.

Results

The authors tested their reverse-traceroute system by using servers over which they had full control, which means they could run traceroutes both from source-to-destination and destination-to-source to establish ground truth. They picked servers spread out all over the world, crossing several ISPs.

One practical issue is that traceroute and RR information type differs: traceroute records ingress interface while RR records the egress or loopback interface. Correlation between traceroute and RR information implies a correlation between these actually-same interfaces (or differentiating actually-different interfaces), which isn’t always perfect and may produce both false negatives and false positives.

A second practical issues is routers that behave differently, that honor TTL but do not honor RR, and vice-versa.

That being said, with ground truth in hand, the reverse-traceroute technique found: “In the median (mean) case, we measure 87% (83%) of the hops in the traceroute for [dataset 1]. For the [dataset 2],we measure 75% (74%) of the hops in the direct traceroute, but 28% (29%) of the the hops discovered by reverse traceroute do not appear in the corresponding traceroute”.

Assumption of Symmetry

The claim of assumption of symmetry being incorrect are evident with these findings: “In the median (mean) case, the forward path shares 38% (39%) of the reverse path’s hops for [dataset 1] and 40% (43%) for the [dataset 2]”

Issues with traceroute and reverse-traceroute

Here are some of the issues the author use to explain differences between traceroute and reverse-traceroute. These issues also highlight problems with drawing general and specific conclusions for traceroutes and reverse-traceroutes: The authors point out general networking issues with both traceroute an reverse-trace:

  • Contemporaneous path changes: routing paths between two nodes can change daily. The authors have noted that for one dataset, up to 49% of hops had changed day-to-day.
  • Hidden or anonymous routers: “Hidden routers, such as those inside some MPLS tunnels, do not decrement TTL. Anonymous routers decrement TTL but do not send ICMP replies, appearing as ‘*’ in traceroute”
  • Exceptional handling of options packets: packets with IP options may be handled differently that flow which we’re trying to understand.