Motu Dealiasing Tool

Motu is a tool for dealiasing pairs of IPv4 addresses. It is based on the IP Prespecified Timestamp dealiasing method described in "Resolving IP Aliases with Prespecified Timestamps", Sherry et al., IMC'10

Download

Motu v1.0.1 was released on October 5, 2011.

Dependencies

Motu depends on both mper and rb-mperio .

Usage

usage: motu [-?fv] [-n concurrency] [-s spacing] [-l logfile]
            [-P probe-method] -p mperport 
            -c candidates | -b suit-results | IPa IPb
    -p, --mper-port=NUM              mper control socket port (REQUIRED)
    -c, --candidates=PATH            file with candidate pair information
    -b, --suitability-results=PATH   file with results of suitability checking
    -n, --concurrency=NUM            max pairs to dealias concurrently (default: unlimited)
    -s, --spacing=NUM                spacing (ms) between probes (default: 0)
    -f, --full                       show full result output
    -v, --[no-]verbose               show detailed progress
    -l, --log=PATH                   mper command/result message log path
    -P, --probe-method=METHOD        the probing method to use - icmp (default) or udp
    -?, --help                       show this message
The tool has three probing modes; full-dealiasing, suitability checking and educated-dealiasing.

The most common, and simple, is full dealiasing, where a pair (or multiple pairs) of candidate addresses are provided and the tool attempts to determine if they are aliases.

The other modes split the algorithm into two pieces; the first of which is referred to as "Suitability Checking". Suitability checking only requires one address and it attempts to determine if the address is a viable candidate for dealiasing using prespecified timestamps. Once an address has been run through the suitability checking logic, it is classified as INELIGIBLE (meaning that it cannot be used at all for dealiasing), or as one of three pass types (two, three or four stamps). These results can be used with some additional heuristics to help determine which pairs should be probed with the remainder of the dealiasing algorithm using the "Educated Dealiasing" mode.

The educated dealiasing mode takes post-processed suitability results and uses them to bypass some of the initial probing usually needed when naively dealiasing a pair of addresses. To make use of this, the suitability results for the desired candidate pair should be combined into the standard output format (as described below) and passed to the tool using the --suitability-results option. This will force the tool to use the given suitability results and move directly to the alias validity check. Note that care should be taken when doing this as the stamping behavior may change over time so the two steps should be done as close together as possible.

There are two ways to provide candidate addresses to the tool; explicitly on the command line, or in a candidate list file.

If providing pairs, the tool accepts two formats; space separated and comma separated. For example, "130.217.250.13 130.217.250.15" or "130.217.250.13,130.217.250.15".

If these are given in a candidate file, there must be one pair per line. If a single address is given per line, the tool will perform only the suitability check as described above.

The tool can also accept space separated and comma separated pairs on the command line, but if space separated pairs are given, the tool will generate candidate pairs by moving left to right. For example, "A B C D" will create two pairs, "A,B C,D". As with the candidate file, if only one address is given it will be used as a suitability-only candidate. There is a subtle difference here when compared to the candidate file; if an odd number of space-separated addresses are given, the last address will only have the suitability check run as the tool cannot determine which address to pair it with.

Normal Output Format

In the normal mode, there is one line of output for each pair of candidate addresses (IPa,IPb), as follows:

<candidate_pair>|<suitability_check>|<alias_validity_check>|<reverse_path>|<alias_check>|<shared_clk>|<distance_loop>|<overall>
For example:
"65.122.236.13,65.122.236.21|P2S5,P2S5|P2S,P2S|-|P2S|PSC|PDI|ALIAS-WEAK"
The structure and possible values in each section are listed below:

Candidate Pair (mandatory)

IPa,IPb e.g. 192.168.1.1,192.168.1.2

Suitability Check (mandatory)

<result_a>,<result_b>
The suitability check is performed on each address.
Result Definition Notes
P4SxPass, 4 Stamps
P3SxPass, 3 Stamps
P2SxPass, 2 Stamps
F1SxFail, 1 Stamp
FNSxFail, No Stamp
FNRxFail, No Reply
FESxFail, Extra Stamp
FVSx Fail, Varying Stamp Multiple stamping behaviours were observed
(where x is the number of probes that were replied to)

Alias Validity Check

<result_a>,<result_b>
The alias validity check is only performed if both IPa and IPb pass the suitability check.

This check issues probes for (A|ABAB) and (B|BABA) and performs per interface analysis.

Result Definition Notes
P4SPass, 4 Stamps
P3S Pass, 3 Stamps Will likely fail the Alias Check
P2SPass, 2 Stamps
F1SFail, 1 Stamp
FNSFail, No Stamp
FNRFail, No Reply
FESFail, Extra Stamp
FVS Fail, Varying Stamp Multiple stamping behaviours were observed
FRN Fail, Reverse path Non-monotonic Interface is on the reverse path, timestamps were non-monotonic (they decreased) (NOALIAS-STRONG)
FRG Fail, Reverse path Gap Interface is on the reverse path, timestamps increment with >1ms gap between timestamps (NOALIAS-WEAK)
FRU Fail, Reverse path Unknown Interface probably on the reverse path, inconclusive timestamps (UNKNOWN-NOALIAS)

Reverse Path Check

The reverse path check is only performed if (IPa==P2S && IPb==F1S) || (IPa==F1S && IPb==P2S)

Works by probing the P2S interface A with (A|BABA) to determine if B is in the return path from A.

Note that a "Pass" in this test is in the context of the overall dealias result. It indicates that a pair has "passed" the reverse path check disproving the hypothesis that one address is in the reverse path. As such, the pair will undergo further testing to determine if they are aliases. A "Fail" indicates that the pair has failed the overall alias check because one address is in the reverse path from the other, and as such are not aliases.

Result Definition Notes
PNS Pass, No Stamp Not on the reverse path. Sent to Distance Check
P1S Pass, 1 Stamp Not on the reverse path. Sent to Distance Check
FNRFail, No Reply
FVS Fail, Varying Stamp Multiple stamping behaviours were observed
F2Nx/F2Gx/F2U Fail, 2 Stamps B is in the fwd path, but not reverse (see FRN/FRG/FRU above). Where 'x' gives the number of probes that were used to make the determination.
F3Nx/F3Gx/F3U Fail, 3 Stamps B is in both fwd and reverse path (see FRN/FRG/FRU above). Where 'x' gives the number of probes that were used to make the determination.
F4S Fail, 4 Stamps Unexpected result (ERROR)

Alias Check

The alias check is only performed if both IPa and IPb pass the validity check. It uses the same probe responses as the Alias Validity Check, but it performs analysis on the pair as a whole.

Result Definition Notes
P4S Pass, 4 Stamps Indicates an alias
F3S Fail, 3 Stamps Results in an error condition as 3 stampers are not understood
P2SPass, 2 Stamps
FIR Fail, Insufficient Replies 50% total replies are required (this is a criteria from Sherry's algorithm that of the combined set of probes to both targets (10 by default), 50% must respond with at least two stamps

Shared Clock Test

The shared clock test is only performed if the alias check test is passed with the P2S flag, indicating that the replies were stamped twice.

Result Definition Notes
PSC Pass, Shared Clock
PME Pass, Midnight/Epoch
FDT Fail, Decreasing Timestamp
F90 Fail, less than 90% timestamp consistency

Distance Test

The distance test is preformed if the shared clock test is passed with the PSC flag, or the alias validity check results in P2S,F1S (and the reverse path check determines B is not on the reverse path).

Result Definition Notes
PDI Pass, Distance The two addresses have equal return path lengths
FDI Fail, Distance The return path length differs between addresses
FNRx Fail, No Reply Where x is the number of replies
FTV Fail, TTL Variance Within probes to a single interface

Overall Result (mandatory)

The overall value is the end result of performing the dealias algorithm on the candidate pair.

Result Definition Notes
ALIAS Confirmed as aliases
ALIAS-WEAK Confirmed as aliases A 2 Stamp interface and a 1 Stamp interface which passed the distance check
ALIAS-STRONG-1 Confirmed as aliases Both interfaces are 4 Stamp
ALIAS-STRONG-2 Confirmed as aliases Either two 2 Stamp interfaces, or a 2 Stamp and a 4 Stamp interface, which passed Shared Clock and Distance checks
NOALIAS-WEAK Not aliases Low-confidence
NOALIAS-STRONG Not aliases High-confidence
UNKNOWN A determination could not be made
UNKNOWN-REPROBE A determination could not be made May be resolved by reprobing the pair
UNKNOWN-ALIAS A determination could not be made It is likely the pair are aliases
UNKNOWN-NOALIAS A determination could not be made It is likely the pair are not aliases
INELIGIBLE At least one candidate interface was not suitable
ERROR Unexpected Result Likely caused by some stamping behavior not yet understood

Full Output Format

If the --full mode is specified, additional lines will be output by the tool showing the full details for each probe response that is received. The format of these lines is as follows:

"< <targets>|<destination>|<stamps>|<timestamps>|<reply_ttl>|<rtt>"
For example:
"< 65.122.236.13,65.122.236.21|A|ABAB|65.122.236.13=3256451247,65.122.236.21=3256451247|243|27.308"
Note that the leading '<' is an explicit character to indicate this was a reply received by the tool (in keeping with the convention used by mper-ping).

Targets (mandatory)

This is an <IP>,<IP> pair which gives the mapping from IP address to the 'A' and 'B' designations used to describe the probe structure. Note that these do not necessarily match the A and B of the candidate pair.

For example, given a target definition of "130.217.250.13,192.172.226.55", "A" will be used to refer to "130.217.250.13" and "B" will be used to refer to "192.172.226.55".

Destination | Stamps (mandatory)

Indicates which (A or B) address the probe was targeted to, and also the format of the prespecified addresses loaded into the timestamp option.

e.g. for the dealiasing, this could be A|ABAB

Timestamp Values

Gives the stamps that were in the response to the probe. All interfaces and stamps up to the pointer in the option are listed. If mper is able to detect a change in the types of options included in the reply (for example if the timestamp prespecified option is loaded in the outgoing probe, but the incoming reply has no options), then it will append "ALTERED" to the list of timestamps. This is also capable of detecting a change in option types. For example, it can detect the case where a probe is sent with the prespecified timestamp option, and the reply has a "no-op" option instead.

The format for these stamps are as follows:

"<TS IP 1>=<TS STAMP 1>,<TS IP 2>=<TS STAMP 2>,<TS IP 3>=<TS STAMP 3>,<TS IP 4>=<TS STAMP 4>[,ALTERED]"
For example:
"65.122.236.13=3256451247,65.122.236.21=3256451247"
If the timestamp option has been stripped, this field will simply show:
",ALTERED"

Reply TTL (mandatory)

Gives the ttl of the response packet

Reply RTT (mandatory)

Gives the round trip time for the probe

Differences from the original algorithm

The dealiasing process and classification implemented in this tool differs slightly from the original algorithm described by Sherry et al..

As outlined in the above OUTPUT FORMAT section, we provide a total of 11 overall outcomes from dealising whereas the original algorithm only describes three (alias, non-alias and unknown). These come as a result of investigating the causes of the various behaviors, and so we can give more specific results. We split the alias category into ALIAS, ALIAS-WEAK and ALIAS-STRONG. As the names indicate, these are are all aliases, but the tool has been able to give some indication of the confidence of the classification. Similar sub-categories are used for NOALIAS also. The UNKNOWN category is split into UNKNOWN, UNKNOWN-REPROBE, UNKNOWN-ALIAS, UNKNWON-NOALIAS. UNKNOWN indicates that the tool is not able to make any determination of the pair of addresses. UNKNOWN-REPROBE indicates that the results of probing are possibly transient and simply re-running the tool may allow a determination to be made. UNKNOWN-ALIAS indicates that the tool is not able to make a determination whether the addresses are aliases, but it suspects that they may be. Similarly, UNKNWON-NOALIAS indicates an inability to classify the addresses, but they may not be aliases.

There are also additional heuristics we have developed to detect cases where the addresses appear to be aliases, but one is actually on the reverse path from the other. These are the only cases where we declare non-aliases.

In the original description of the algorithm, the reverse path distance check was performed only when one address returned two stamps to (A|ABAB) and the other returned one stamp. We perform this check even when both addresses return two stamps to give an even stronger alias result. A failure of the test will not result in a non-alias being declared (the overall result will be ALIAS), but a pass will result in an overall classification of ALIAS-STRONG.

Overall Statistics (motu-stats)

motu-stats is a script to carry out some basic overall analysis of a dealiasing run.

The script takes the motu results output and generates statistics for each of the sub-components that are described in the "Output Format" section above.

usage: motu-stats [--histogram] motu_output_file

Sample output for a dealiasing run with 1000 pairs is shown below, annotated with descriptions of the tables displayed.

Suitability Check

Total candidate pairs: 1000
Total interfaces tested for suitability: 2000
Suitability Stats:
Probing for (D|DXXX) and (D|DDDD)
Classification  # IPs  % of IPs
======|FAILURE CONDITIONS|======
Unresponsive  791  39.55%
Inconsistent  327  16.35%
Extra Stamp  7  0.35%
Zero Stamps  277  13.85%
One Stamp  286  14.30%
=======|PASS CONDITIONS|========
Two Stamps  156  7.80%
Three Stamps  0  0.00%
Four Stamps  156  7.80%
--------------------------------
TOTAL    2000  100%
================================
Number of pairs which passed suitability check: 73
Probe Response Stats:
Resp/Atmpt  Frequency

------------------------
0/5    779  *
1/5    12  * both included in 'Unresponsive' count above
2/5    9
3/5    16
4/5    22
5/5    1162

Description

The Suitability Check table gives a per-interface break-down of the number of interfaces which exhibit each characteristic. A minimum of five probes, and a maximum of ten have been sent to each interface during this check. The Unresponsive category indicates that for either the (D|DXXX) or (D|DDDD) set of probes (five each), less than two replies were received.

The Probe Response Stats table gives an indication of the distribution of response numbers. Ideally all probe sets would receive 5 responses. Interfaces which are in the middle of the range (2-3 responses) could perhaps be caused by rate limiting; consider increasing the inter-probe spacing time.

Stats LabelRaw Code
UnresponsiveFNR
InconsistentFVS
Extra StampFES
Zero StampsFNS
One StampF1S
Two StampsP2S
Three StampsP3S
Four StampsP4S

Alias Validity Check

Alias Validity Check Stats:
Probing (A|ABAB) for each IP
Classification  # IPs  % of IPs
======|FAILURE CONDITIONS|======
Unresponsive  0  0.00%
Inconsistent  0  0.00%
No Stamp  0  0.00%
One Stamp  12  8.22%
RP TS Decrease  0  0.00%
RP TS Gap  0  0.00%
RP TS Unknown  0  0.00%
=======|PASS CONDITIONS|========
Two Stamp  6  4.11%
Three Stamp  0  0.00%
Four Stamp  128  87.67%
--------------------------------
TOTAL    146  100%
================================
Number of pairs which passed validity check: 67

Description

The Alias Validity Check table gives a per-interface breakdown of the behaviors that are seen when an interface is probed with the prespecified address pattern (A|ABAB).

Stats LabelRaw Code
RP TS DecreaseFRD
RP TS GapFRG
RP TS UnknownFRU

Return Path Check

Return Path Check Stats:
Probing (A|BABA)
Classification  # Pairs  % of Pairs
======|FAILURE CONDITIONS|======
Unresponsive  0  0.00%
Inconsistent  0  0.00%
2 Stamp (N-M)  0  0.00%
2 Stamp (Gap)  0  0.00%
2 Stamp (Unk)  0  0.00%
3 Stamp (N-M)  0  0.00%
3 Stamp (Gap)  0  0.00%
3 Stamp (Unk)  0  0.00%
4 Stamp (ERR)  0  0.00%
=======|PASS CONDITIONS|========
No Stamp  0  0.00%
1 Stamp    0  0.00%

--------------------------------
TOTAL    0  0%
================================

Description

The return path check is executed whenever a two stamp (P2S) address is paired with a one stamp (F1S) address based on (A|ABAB) and (B|BABA) probing. If the results are either two or three stamps, the timestamps are compared to determine how strong the non-alias classification can be. Non-Monotonic timestamps result in a NOALIAS-STRONG classification while a gap (increase) of > 1ms causes a classification of NOALIAS-WEAK. If either no stamps, or one stamp is seen, the pair is sent to the distance check to ascertain whether it can be classified as weak aliases.

Stats LabelRaw Code
1 StampP1S
No StampPNS
2 Stamp (N-M)F2N
2 Stamp (Gap)F2G
2 Stamp (Unk)F2U
3 Stamp (N-M)F3N
3 Stamp (Gap)F3G
3 Stamp (Unk)F3U
4 Stamp (ERR)F4S

Alias Check

Alias Check Stats:
Probing (A|ABAB) and (B|BABA)
Classification  # Pairs  % of Pairs
======|FAILURE CONDITIONS|======
<5 Replies  0  0.00%
Three Stamps  0  0.00%
=======|PASS CONDITIONS|========
Two Stamps  3  4.48%
Four Stamps  64  95.52%
--------------------------------
TOTAL    67  100%
================================

Description

The alias check is performed once the alias validity check has been passed with either two, three or four stamps. It requires that at least 50% (5/10 in the current implementation) of the validity check probes have received replies. For a pair to pass the Alias Check, both interfaces must have stamped probes two or four times. Three stampers are not understood and so are failed with an overall verdict of "ERROR". Two stampers are passed through to the shared clock test and four stampers are declared aliases.

Stats LabelRaw Code
<5 RepliesFIR
Three StampsF3S
Two StampsP2S
Four StampsP4S

Shared Clock Check

Shared Clock Check Stats:
Timestamps from (A|ABAB) and (B|BABA)
Classification  # Pairs  % of Pairs
======|FAILURE CONDITIONS|======
Decreasing TS  0  0.00%
TS Variance  0  0.00%
=======|PASS CONDITIONS|========
Shared Clock  3  100.00%
Midnight/Epoch  0  0.00%

--------------------------------
TOTAL    3  100%
================================

Description

Once a pair has passed the alias check with either two P2S addresses, or one P2S and one P4S interface, it is run through the shared clock check to determine whether both interfaces share the same timestamp clock. If a decreasing clock is ever observed, that is, the timestamp values decrease between stamps for (A|ABAB), then the pair cannot be aliases (unless the clock has been shifted at the exact moment we probed). Otherwise, if the stamps never decrease, we require 90% of probes to be filled with consistent times. That is, all stamp values within a probe must be identical for 90% of probes. The other possibility is a seemingly large increase between stamps for A and B in (A|ABAB). If these are resolved to be a midnight offset for A, and an epoch stamp for B, then we consider this a pass based on additional probes to (B|AAAA) (which must also exhibit this behavior).

Stats LabelRaw Code
Decreasing TSFDT
TS VarianceF90
Shared ClockPSC
Midnight/EpochPME

Distance Check

Distance/Loop Check Stats:
Classification  # Pairs  % of Pairs
======|FAILURE CONDITIONS|======
Unresponsive  0  0.00%
TTL Variance  0  0.00%
Distance  1  33.33%
=======|PASS CONDITIONS|========
Distance  2  66.67%
--------------------------------
TOTAL    3  100%
================================

Description

The distance check is used as a weak test to determine that two addresses are equidistant from the vantage point which is dealiasing them. The distance check is used in two situations; the first is when two addresses pass the alias check with either two or four stamps. The distance check is used in this case to provide a stronger alias classification. The second case that the check is used for is when a pair has one two stamp address and one single stamp address. In this case the distance check is used to ensure that one of the addresses is not on the reverse path from the other. We call this a weaker alias because it is possible for the distance check to be invalidated by asymmetric load balancing on the reverse path.

Stats LabelRaw Code
TTL VarianceFTV
TS VarianceF90
Distance [fail]FDI
Distance [pass]PDI

Overall Verdicts

Overall Verdicts:
Classification    # Pairs  % of Pairs
=========|FAILURE CONDITIONS|=========
Non-Alias Strong  0  0.00%
Non-Alias Weak    0  0.00%
Ineligible    914  91.40%
Unknown      7  0.70%
Unknown Reprobe    13  1.30%
Unknown Alias    0  0.00%
Unknown Non-Alias  0  0.00%
Error      0  0.00%
==========|PASS CONDITIONS|===========
Alias      64  6.40%
Alias Weak    2  0.20%
Alias Strong    0  0.00%

--------------------------------------
TOTAL      1000  100%
======================================

Description

The overall verdicts table shows the distribution of end results that the tool determined for the candidate pairs.

Stats LabelRaw Code
Non-Alias StrongNOALIAS-STRONG
Non-Alias WeakNOALIAS-WEAK
IneligibleINELIGIBLE
UnknownUNKNOWN
Unknown ReprobeUNKNOWN-REPROBE
Unknown AliasUNKNOWN-ALIAS
Unknown Non-AliasUNKNOWN-NOALIAS
ErrorERROR
AliasALIAS
Alias WeakALIAS-WEAK
Alias StrongALIAS-STRONG

Additional Histograms

If the script is called with the --histogram option, it will display three additional histograms which can be useful for determining the causes of various results.

Note that these histograms ignore the ordering of the addresses, so a pair (X,Y) can appear as X -> Y as well as Y -> X. I.e. X can be both A and B in these histograms.

Failure Pairings

Pairs which contain one pass interface and one fail interface:
P2S    150  90.36%
  F1S  90  54.22%
  FNS  35  21.08%
  FNR  17  10.24%
  FVS  8  4.82%
P4S    16  9.64%
  FNR  13  7.83%
  FNS  2  1.20%
  FVS  1  0.60%

Shows the type of address that a passing address was paired with which caused the pair to be rejected after suitability testing.

In this example, the majority of pairs for which one address was suitable but not the other are two stampers paired with a one stamper.

Pass Pairings

Pairings which pass suitability check:
P2S    3  4.11%
  P2S  3  4.11%
P4S    70  95.89%
  P4S  70  95.89%

Similar to the above table, but provides an indication of what an address is usually paired with when they passed the suitability check. In this case we never see a four stamper paired with a two stamper passing suitability checking.

Suitability to AVC Mappings

Mapping from Suitability result to AVC result:
Suit A  AVC A  Suit B  AVC B  Count  %
P2S        6  4.11%
  P2S      6  100.00%
    P2S    6  100.00%
      P2S  6  100.00%
P4S        140  95.89%
  P4S      128  91.43%
    P4S    128  100.00%
      P4S  128  100.00%
  F1S      12  8.57%
    P4S    12  100.00%
      F1S  12  100.00%

Shows the relationship between the stamping behavior for (A|AAAA), (A|ABAB), (B|BBBB) and (B|BABA).

In the example above, an address which stamps four times in suitability checking (A|AAAA), almost always stamps four times in the validity check (A|ABAB), and when it does, the address that it is paired with always stamps four times for both the suitability and validity checks.

The Name

"In Polynesian languages, motu refers to a reef islet formed by broken coral and sand surrounding an atoll. There are countless motus scattered all over the Pacific Ocean." -- http://en.wikipedia.org/wiki/Motu

The idea is that Motu are the pieces of a large under-water land mass which are visible from above the water; similar to the the concept of interfaces on a router which are the pieces of the router that are 'visible' at the IP layer.

Related Objects

See https://catalog.caida.org/details/software/motu/ to explore related objects to this document in the CAIDA Resource Catalog.
Published
Last Modified