Subject: Re: [Sidrops] ASPA verification algorithm error

From: Lukas Tribus <[email-masked]>
Date: Thu, 11 Feb 2021 01:35:43 +0100

On Fri, 22 Jan 2021 at 07:21, Jakob Heitz (jheitz)
<jheitz=[email-masked]> wrote:
>
> Consider the as-path (1 2 3 4), where
>
> 1 attests that 2 is its provider
>
> 4 attests that 3 is its provider
>
> 2 and 3 make no attestations.
>
> Then the path is valid.
>
> The algorithm in https://tools.ietf.org/html/draft-ietf-sidrops-aspa-verification-06
>
> would incorrectly return "unknown"

I assume 2 is not a provider for 3 (but a peer)? Wouldn't section 5.2.
"Downstream Paths" make this "valid" then?

Are they "special" non-peers? Then "7.  Mutual Transit (Complex
Relations)" would apply (in that case, without attestation "unkown"
would be expected and a positive attestation required for a "valid"
result) - which I believe is what we want.

I think in this case it would be helpful to include the actual
relationship between the AS you have on your mind, not only the ASPA
attestations.

Lukas

---

From: "Jakob Heitz (jheitz)" <[email-masked]>
Date: Thu, 11 Feb 2021 02:27:30 +0000

All we have is the attestations.
We don't know the actual relationships.
Thus we need to try all possible relationships given the available attestations.
Using the notation where the arrow points to the provider:
A -> B means B is provider for A
A <- B means A is provider for B
A -- B means A and B are bilateral peers
A <> B means A and B are complex or siblings.
then the possible relationships are:
1 -> 2 -- 3 <- 4
1 -> 2 -- 3 <> 4
1 -> 2 -> 3 <- 4
1 -> 2 -> 3 <> 4
1 -> 2 <- 3 <- 4
1 -> 2 <- 3 <> 4
1 -> 2 <> 3 <- 4
1 -> 2 <> 3 <> 4
1 <> 2 -- 3 <- 4
1 <> 2 -- 3 <> 4
1 <> 2 -> 3 <- 4
1 <> 2 -> 3 <> 4
1 <> 2 <- 3 <- 4
1 <> 2 <- 3 <> 4
1 <> 2 <> 3 <- 4
1 <> 2 <> 3 <> 4
All of these possible relationships represent a valid AS_PATH.

Regards,
Jakob.

-----Original Message-----
From: Sidrops <[email-masked]> On Behalf Of Lukas Tribus
Sent: Wednesday, February 10, 2021 4:36 PM
To: Jakob Heitz (jheitz) <jheitz=[email-masked]>
Cc: [email-masked]
Subject: Re: [Sidrops] ASPA verification algorithm error

Lukas

_______________________________________________
Sidrops mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/sidrops

---

From: Lukas Tribus <[email-masked]>
Date: Thu, 11 Feb 2021 22:20:38 +0100

> then the possible relationships are:

How does 5.2. "Downstream Paths" not address this?

Lukas

---

From: "Jakob Heitz (jheitz)" <[email-masked]>
Date: Thu, 11 Feb 2021 23:54:32 +0000

pair_check with either AS2 or AS3 as customer will return unknown.
Therefore, the algorithm returns unknown, when it should return valid.

Regards,
Jakob.

-----Original Message-----
From: Lukas Tribus <[email-masked]> 
Sent: Thursday, February 11, 2021 1:21 PM
To: Jakob Heitz (jheitz) <[email-masked]>
Cc: Jakob Heitz (jheitz) <jheitz=[email-masked]>; [email-masked]
Subject: Re: [Sidrops] ASPA verification algorithm error

Lukas

---

From: Ben Maddison <[email-masked]>
Date: Fri, 12 Feb 2021 10:10:03 +0200

Hi Jakob,

> Therefore, the algorithm returns unknown, when it should return valid.
If I'm understanding you correctly:
*Any* ASPA (even an [AS0] one) issued by either AS2 or AS3 would result
in a valid path.
Therefore, you are arguing, even if no ASPA covers the AS2<->AS3
adjacency, the path should be considered *valid* since there is no possible
ASPA object that could result in it being *invalid*?

I think that logic holds. However I don't favor incorporating it into
the validation algorithm for a few reasons:
1.  We (and I expect most others) will make no policy distinction
    between valid and invalid paths in policy. Thus any additional complexity
    is a poor trade.
2.  It is important that engineers are able to easily reason about how a
    set of ASPA objects and an observed AS_PATH result in a validation
    state. Whilst I think the above logic is valid, accounting for it
    mentally is non-trivial.
3.  In the event that operators do de-pref invalid in favor of unknown
    (yes, I know I said above that they probably won't: but *if* they do),
    then AS2 and AS3 lose traffic on that adjacency (which is undesirable for
    them both - otherwise they won't have built it).
    This creates a positive economic incentive for AS2 and/or AS3 to go
    and create an ASPA. Positive incentives are in short supply in the
    routing security world - I don't think we should opt-out of them
    lightly!
4.  There is no creation dependency problem for ASPAs, like there is for
    ROAs - where e.g. a provider has to wait for customers to issue ROAs
    for all sub-allocations before issuing for the aggregate. As a
    result I don't believe that we should be spending cycles
    accommodating those operators that don't bother doing it.

Interested to hear your thoughts?

Cheers,

Ben

---

From: Alexander Azimov <[email-masked]>
Date: Fri, 12 Feb 2021 21:26:24 +0300

Jacob, you are right that additional heuristics can be added to ASPA logic
to transform some Unknown states to Valid, though it will not improve
leak/hijack detection.
Nevertheless, I agree with Ben. Such changes can result in
misleading understanding if one will try to distinguish if the path is more
reliable a.e. Valid from Unknown. This has special importance if we start
speaking about malicious activity.

-- 
Best regards,
Alexander Azimov

---

From: "Jakob Heitz (jheitz)" <[email-masked]>
Date: Fri, 12 Feb 2021 19:48:35 +0000

It seems we all agree that the path I illustrated is valid and the algorithm in the draft marks it unknown.
The first priority is to get the correct result.

ASPA has to work as well as possible without full participation.
It will never work if full participation is required.

I agree with Ben that it is difficult to reason with the model of ASPA as written in the draft.
Here is an alternative:

    Every transit AS in the path must have at least one neighbor that calls it a provider.

That's a lot easier to reason about than trying to figure out where upstream turns to downstream
in the presence of bilateral peers, siblings, complex relationships and ASes making no attestations.
You only need to consider one AS at a time and what is to its left and to its right.

Repeating:

Here is a simple and working algorithm:

  *   The received AS-path is prepared:
     *   Remove duplicate ASNs.
     *   Prepend own ASN.
     *   May also prepend Forwarded-to ASN to detect own leak. (optional)
  *   For every sequence (A, B, C) of consecutive ASes in an AS-path:
     *   If A attests that B is not a provider and C attests that B is not a provider,
then B leaked the route: B is transiting for free. The segment is invalid.
     *   If either A or C attests that B is a provider, then the AS-path segment  (A, B, C) is valid.
     *   Else if either A or C make no attestation, then the leak state is unknown. Even if B lists both A and C as providers, it is not necessarily a leak, because either A or C could consider B as a provider for some of their routes, even though they don’t attest to it.
  *   If all the path segments are valid, then the whole path is valid.
  *   If any of the path segments is invalid, then the whole path is invalid.
  *   Else, at least one path segment is unknown and one more rule must be applied: for any sequence of ASes (A, B1, ..., Bn, C), if A attests that B1 is not a provider and C attests that Bn is not a provider, then the AS-path is invalid. This is for any number of Bx greater than 1.

Regards,
Jakob.

From: Sidrops <[email-masked]> On Behalf Of Alexander Azimov
Sent: Friday, February 12, 2021 10:26 AM
To: Ben Maddison <benm=[email-masked]>
Cc: Jakob Heitz (jheitz) <jheitz=[email-masked]>; [email-masked]; Lukas Tribus <[email-masked]>
Subject: Re: [Sidrops] ASPA verification algorithm error

Jacob, you are right that additional heuristics can be added to ASPA logic to transform some Unknown states to Valid, though it will not improve leak/hijack detection.
Nevertheless, I agree with Ben. Such changes can result in misleading understanding if one will try to distinguish if the path is more reliable a.e. Valid from Unknown. This has special importance if we start speaking about malicious activity.

пт, 12 февр. 2021 г. в 11:10, Ben Maddison <benm=[email-masked]<mailto:[email-masked]>>:
Hi Jakob,

Cheers,

Ben
_______________________________________________
Sidrops mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/sidrops

--
Best regards,
Alexander Azimov

---

From: Ben Maddison <[email-masked]>
Date: Mon, 15 Feb 2021 08:48:52 +0200

Hi Jakob,

> The first priority is to get the correct result.

That's not quite what I said!
I think the logic you used to arrive at the conclusion is sound. I agree
that the path you illustrated should be accepted by the receiver.
However, I also gave several reasons why a validation state of Unknown
is appropriate here.
> It will never work if full participation is required.
I'm not clear on why you believe the issue at hand impacts the
effectiveness of ASPA under partial deployment?

>   *   If any of the path segments is invalid, then the whole path is invalid.

The above looks sound to me on first sight.
I am going to poke it a little before I fully endorse it though...

>   *   Else, at least one path segment is unknown and one more rule must be applied: for any sequence of ASes (A, B1, ..., Bn, C), if A attests that B1 is not a provider and C attests that Bn is not…
The above final step is less clear to me. Could you explain your
reasoning in some more detail please?

Cheers,

Ben

---

From: Alexander Azimov <[email-masked]>
Date: Mon, 15 Feb 2021 21:15:01 +0300

Jacob,

I think you haven't got my point. Let me quote the current document:

   Instead of checking AS_PATH correctness, this document focuses on
   solving real-world operational problems - automatic detection of
   malicious hijacks and route leaks.

What you are suggesting doesn't improve the detection of route leaks,
though can be harmful in fighting malicious activity.
I stay in favor that Valid in terms of ASPA should mean that all pairs are
Valid for upflow paths and slightly more complex for downflow paths.

We don't try to combine ROAs and Route Objects at the ROV procedure to get
more 'Valid' outcomes, this principle should be applicable here too.

пт, 12 февр. 2021 г. в 22:48, Jakob Heitz (jheitz) <[email-masked]>:

>    - The received AS-path is prepared:
>       - Remove duplicate ASNs.
>       - Prepend own ASN.
>       - May also prepend Forwarded-to ASN to detect own leak. (optional)
>    - For every sequence (A, B, C) of consecutive ASes in an AS-path:
>       - If A attests that B is not a provider and C attests that B is not
>       a provider,
>       - If either A or C attests that B is a provider, then the AS-path
>       segment  (A, B, C) is valid.
>       - Else if either A or C make no attestation, then the leak state is
>       unknown. Even if B lists both A and C as providers, it is not necessarily a
>       leak, because either A or C could consider B as a provider for some of
>       their routes, even though they don’t attest to it.
>    - If all the path segments are valid, then the whole path is valid.
>    - If any of the path segments is invalid, then the whole path is
>    invalid.
>    - Else, at least one path segment is unknown and one more rule must be
>    applied: for any sequence of ASes (A, B1, ..., Bn, C), if A attests that B1
>    is not a provider and C attests that Bn is not a provider, then the AS-path
>    is invalid. This is for any number of Bx greater than 1.
>
>
>
>
>
>
>
>
>
> Regards,
>
> Jakob.
>
>
>
> *From:* Sidrops <[email-masked]> *On Behalf Of *Alexander Azimov
> *Sent:* Friday, February 12, 2021 10:26 AM
> *To:* Ben Maddison <benm=[email-masked]>
> *Cc:* Jakob Heitz (jheitz) <jheitz=[email-masked]>;
> [email-masked]; Lukas Tribus <[email-masked]>
> *Subject:* Re: [Sidrops] ASPA verification algorithm error
>
>
>

-- 
Best regards,
Alexander Azimov