Inconsistent Unknown classification between algorithms

[benmaddison]

Overview

The Draft6Validator and HeitzValidator disagree on the correct validation
outcome for certain categories of received AS_PATH.
The divergence manifests where an otherwise Valid path contains a single
adjacency ASX - ASY where neither ASX nor ASY have issued any ASPA object.

This difference in behaviour arises from a fundamental difference in the logical
underpinnings of the two algorithms, and warrants a full description.

Description

Both Draft6Validator and HeitzValidator determine the validation status of
given AS_PATH by:

1. breaking the AS_PATH into atomic "components";
2. calculating the validation status of each "component"; and
3. deriving the final validation status according to the following logic:
   • Valid if and only if all "components" are Valid;
   • Invalid if and only if any "component" is Invalid;
   • Unknown otherwise.

However, the concept of "component" differs fundamentally between the two
algorithms.

• Draft6Validator treats each adjacency between ASs in the AS_PATH as a
  component, and attempts to infer whether an announcement should have
  "crossed" the adjacency;
• HeitzValidator, conversely, treats each transited AS in the AS_PATH
  (i.e. all but the left- and right-most ASs) as a component, and attempts
  to infer whether that AS was authorised to announce transit by either of
  its imediate neighbors.

The result of this distinction (in the current context) is that an AS_PATH:

W_X_Y_Z

Where:

• W issues an ASPA asserting that X is its provider;
• Z issues an ASPA asserting that Y is its provider; and
• neither X nor Y issue an ASPA.

When Draft6Validator attempts to validate the adjacency X_Y, it does so
reference to the ASPA objects issued by either X or Y. Since neither AS has
issued an ASPA object, the component is Unknown, and thus so is the AS_PATH.

When HeitzValidator evaluates the same AS_PATH, it considers the transited
networks X and Y as separate components, and evaluates their respective
statuses with reference to the ASPA objects issued by their immediate neighbors.
In the case of X, authorisation has been provided by W. Similarly, in the
case of Y authorisation has been granted by Z. Thus, all components are
Valid, and hence so too is the full AS_PATH.