TSPS Investigations

A summary of investigating and evaluating the IP Prespecified Timestamp dealiasing technique.

During the course of implementing the IP Prespecified Timestamp (TSPS) dealiasing technique described by Sherry in "Resolving IP Aliases with Prespecified Timestamps", we discovered many different router stamping behaviors which we investigated in an attempt to better understand the reasons why the technique works, and how we can have more confidence in it's results. We also evaluate the usefulness of this technique with respect to macroscopic IP dealiasing projects. This document outlines the results discovered; we plan to write a paper which describes this work more comprehensively.

Stamping Behaviors

The original authors list seven possible stamping behaviors: Unresponsive, Extra Stamp, Zero Stamp, One Stamp, Two Stamps, Three Stamps, and Four Stamps. Of these, they only provide a justification for the Extra Stamp behavior. After careful probing and utilizing groundtruth data, we can, with some confidence, comprehensively describe the causes for almost all of the stamping behaviors we observe.

We make a distinction between the observed stamping behavior and the underlying behavior. Our investigations have confirmed three common underlying stamping patterns which manifest as eight observed stamping behaviors depending on their combination with other factors. We also have some evidence of other underlying stamping behaviors, but do not have groundtruth data to support our claims.

Confirmed Underlying Stamping Behaviors

Four Stamp - Greedy
Two Stamp - Destination/Egress
Two Stamp - Ingress/Egress

Suspected Underlying Stamping Behaviors

Four Stamp - Lazy

Observed Stamping Behaviors

Unresponsive
Inconsistent
Extra Stamp
Zero Stamps
One Stamp
Two Stamp
Three Stamp
Four Stamp

Probe Methods

In addition to investigating the underlying causes of stamping behaviors, we also tested different probing methods to establish whether the coverage of the technique could be boosted by combining methods. We found that there are a small number of targets which are unresponsive to ICMP probes with the Prespecified Timestamp option but do respond to UDP probes.

In our experiments, we see an average of 8.34% of unresponsive destinations which respond to UDP probes, but not to ICMP. This implies that for the set of interfaces which do not respond to ICMP timestamp probes, we could potentially make use of approximately 8% of them by sending UDP probes. Unfortunately this means sending every single ICMP unresponsive address a UDP probe to determine whether it will respond.

In our large-scale ICMP experiments, we saw around 48.98% of targets not respond to ICMP timestamp probes. Accordingly, we could perhaps expect to see an overall gain of approximately 4.1% of interfaces by utilizing UDP probing. As mentioned earlier, this however requires probing every one of the unresponsive targets with a UDP probe to determine eligibility. In this example, this would require at least an extra 1,015,639 probes (assuming we only send one per non-responsive target). According to our models, these extra 1 million probes would allow at most an extra 85,000 targets to be used for dealiasing. These 85,000 targets must now be tested to ensure compatibility with the dealiasing algorithm. If we assume that roughly the same fraction of UDP responsive targets are suitable as ICMP targets, then we can expect that somewhere around 30,000 targets end up being suitable. This is not considering the pairing - i.e. whether the other interface in the pair will be suitable also.

We suggest that the small number of targets recovered does not justify the large number of extra probes that must be sent. There are indeed cases where probing with UDP is beneficial, therefore if the technique is being used in an ad-hoc manner to dealias a single target, it is certainly worth trying UDP probes if ICMP fails.

Vantage Points

Sherry's original description of the technique makes mention of using multiple vantage points for the purpose of overcoming filtering of IP options in the path to targets. While we agree that using multiple vantage points is advantageous to dealising, our experiments suggest that there is little filtering in paths to targets, filtering mostly happens at the edges. Multiple vantage points are instead useful for covering different ingress and egress interfaces for routers which only stamp twice (see the "Underlying Two Stamp" section above).

We tested a sample of 25,000 targets from three geographically distributed vantage points (USA, Germany and China) and found that only a small number of targets (~5%) which were unresponsive from one vantage point are responsive from another.

Multiple vantage points are however very beneficial when it comes to mitigating the effect that Two Stamp Ingress/Egress and Destination/Egress routers have on the results. As explained in the earlier section about underlying stamping behaviors, if a two stamp router is probed from multiple vantage points, the chances of encountering the correct combination of ingress and egress interfaces for the pair being dealiased is increased. A potential indicator of the gains to be had is the difference between the number of two stamp interfaces that we see when probing from a single vantage point, and the number that Sherry saw when probing from multiple vantage points. In our probing, we see 5.72% of interfaces responding with two stamps, whereas Sherry sees 22.2% - a 16.48% gain.

As we mentioned earlier this gain could be optimized by attempting to infer ingress and egress interfaces of routers by analyzing the results of probing targets with (A|AAAA). These interfaces could be used to intelligently pair interfaces and assign them to a vantage point for dealiasing.

Evaluation

Overall we have found that the prespecified timestamp dealiasing technique has limited real-world applicability. We find that it falls short in three major areas: it requires explicit candidate pairs; it cannot declare a pair as non-aliases; it relies on a specific, non-standard implementation of the timestamp option.

While the technique is potentially useful for tactical dealiasing tasks, it's requirement that candidate pairs be explicitly provided makes it impractical for large-scale application. For example, CAIDA uses over 2.3 million addresses as input for their MIDAR dealiasing process (see MIDAR tools page for more information). To naively use the prespecified timestamp technique on this set would require testing well over five trillion (N²) pairs. As a rough average, the timestamp technique requires approximately 30 probes to resolve any given pair, giving a total number of probes in the order of 150 trillion. There are heuristics that can be used to reduce the number of pairs, but they still leave a leave a large number of pairs and introduce the possibility of discarding true aliases. We are currently in the process of investigating the viability of using TTL clustering as suggested by Sherry in the original paper.

In addition to requiring explicit candidate pairs, the technique is unable to reliably provide a non-alias declaration for any given candidate pair. That is, the only reliable determinations it can provide are 'alias' and 'unknown'. While we have extended the algorithm to enable it to provide a non-alias declaration, it is for a very specific edge case. See the "Reverse Path Check" section of the Motu readme for more details.

For the technique to successfully resolve a pair of addresses as aliases, the router must stamp either two, or four, times. As we have shown, two stamp routers stamp only for a specific pair of addresses, and so are only useful if the dealiasing candidates happen to exactly line up with the path we take out of the router (or in and out in the Ingress/Egress case). The other useful stamping behavior, four stampers, is, as we have shown, almost entirely seen on Juniper routers. While Juniper is a popular router vendor, it accounts for less than one third of the core routers in the Internet. The dominant vendor, Cisco, appears to be the cause of the rather unreliable two-stamp behavior.

In addition to the largest vendor's routers only being useful if the path takes specific interfaces, there is also a general recommendation that router operators should disable IP option support altogether. Cisco released a security advisory in 2009 which related to a vulnerability in their router's handling of packets with IP options. Cisco's advice for a workaround was for operators to drop any packets which contained options. Other router operators have also written about the security issues presented by packets with IP options and recommend that they be dropped. These issues cast doubt on the usefulness of the technique in the real-world, both in the present, and into the future as more operators drop packets with options.

That said however, the technique is useful as a 'tool in the dealiasing toolbox'. That is, if a researcher has a specific pair (or set of pairs) of interfaces they believe to be aliases, the technique can potentially provide some confirmation of this when coupled with other techniques. It is also possible that timestamp dealiasing may work where other methods have failed.