Subject: [Sidrops] On validating AS paths

From: Iljitsch van Beijnum <[email-masked]>
Date: Wed, 26 Jun 2019 17:19:38 +0200

(I hope the list retains my non-proportional font. Reformat if necessary.)

After an interesting discussion with Job Snijders the other day about our respective drafts, I think it would be helpful to analyze the issue of AS path validation further before discussion specific solutions.

I'm interested to hear if my assumptions and conclusions are shared.

I think we can agree that any AS path that doesn't conform to the valley-free model. A quick refresher: the valley-free model assumes four types of relationships between ASes:

customer-provider:  /
provider-customer:  \
peer-peer:          ^
sibling-sibling:    -

I've invented the / \ ^ - characters to indicate relationships myself, the idea being that they'll visually show valleys if a path isn't valley-free.

You can visualize valley-freeness as the customer ASes at the bottom sending many up the hierarchy, and the money will only flow up, not down. So if you have a "valley" in the relationships between the ASes in a path, someone isn't getting paid and the whole thing doesn't work economically.

The model also allows for mutual backup arrangements, where basically two ASes provide transit to each other (also called a sibling relationship). How that works financially is a bit murky, but the interesting thing here is that if nobody implements any policies or filters, you have a network with only sibling relationships.

So with these four relationships and the valley-free restriction we should be able model any working real-world relationship between two or more ASes.

(We'll ignore the possibility that the relationships between ASes may be different for different address families and/or prefixes for now.)

For a formal definition of the valley-free model, read "On inferring autonomous system relationships in the internet", Gao, 2001.

I'll state it in the form of the following AS path validation procedure.

In addition to / \ ^ - we'll also allow ? to indicate an unknown relationship between two adjacent ASes in the path. And we'll assume the sibling relationship between an AS and itself (i.e., if there is AS path prepending).

The steps:

1. Trim from the right (origin) side all \ and - relationships
2. Trim from the left side all / and - relationships
3. If the path is now empty or contains just one ^, the path is valley-free and therefore valid
6. If the path still contains / or \ or contains multiple ^, the path is invalid

Here are a few valid paths:

A: //\\ 
B: /^\
C: ^
D: ^\-\

So the steps produce:

            A       B       C       D
            //\\    /^\     ^       ^\-\
Step 1      //      /^      ^       ^
Step 2              ^       ^       ^
Step 3      valid   valid   valid   valid

If we look at RFC 7908, the first four types of route leaks are caused by the following relationships:

1: \/
2: ^^
3: ^/
4: \^

So the steps produce:

            Type 1  Type 2  Type 3  Type 4
            \/      ^^      ^/      \^
Step 1      \/      ^^      ^/      \^
Step 2      \/      ^^      ^/      \^
Step 3      \/      ^^      ^/      \^
Step 5      invalid invalid invalid invalid

Now what if we have unknown relationships in the path?

/?^\ could be:

//^\    /-^\    /^^\    /\^\
valid   valid   invalid invalid

/?\ could be:

//\     /-\     /^\     /\\
valid   valid   valid   valid

In other words: if steps 1 and 2 above just leave a ?, then regardless of what the unknown relationship turns out to be, we know the path will be valley-free and valid.

So we can now extend the validation steps to consider unknown relationships and see even if we assume a best case scenario, we still end up with an invalid path:

1. Trim from the right (origin) side all \ and - relationships
2. Trim from the left side all / and - relationships
3. If the path is now empty or contains just one ^ or just one ?, the path is valley-free and therefore valid
4. Trim from the right (origin) side all \, - and ? relationships
5. Trim from the left side all /, - and ? relationships
6. If the path still contains / or \ or contains multiple ^, the path is invalid
7. Else the path validity is unknown

Now all of the above assumes that the relationship between two ASes is uncontested. But what if the two ASes claim to have different relationships?

One approach would be to just assume an unknown relationship ?, so the path will only validate under worst case assumptions.

In my opinion, a better approach would be just keep track of claims of a customer-provider relationship from the customer side (where the sibling relationship is simply a mutual customer-provider relationship claim).

Overclaiming of the relationship by a customer is relatively unproblematic, because the claimed provider will simply not provide the service with no ill effect. Overclaiming by the provider, on the other hand, could be harmful, the combination of the relationship overclaim and incorrect BGP filters will now create a route leak that our path validation system will declare to have a valid path.

There is probably no reason to publish peer-to-peer relationships, as a path with ? where there should be ^ will also validate.

One interesting issue is route servers, as deployed by internet exchanges. Typically (universally?) those don't add their AS to the AS path, breaking the BGP specification in the process. In that case, the route server is invisible, so validation will have the same result as with a direct peering relationship.

If this behavior is not universal, we should either assume a - relationship for route servers, or define a new type of relationship that will be removed from the valley-free validation process.

With all of the above out of the way, we'll have to think about which relationship claims to carry in-band and which out-of-band.

---

From: Alexander Azimov <[email-masked]>
Date: Wed, 26 Jun 2019 19:39:17 +0300

Hi Iljitsch,

I assume that after talking with Job Snijders you are aware of ASPA drafts.
They cover the detection of anomalies (invalid ASPATHs) that are received
from customers and peers + specify RPKI object exactly for
customer-to-provider pairs.

It has a different specification for unknown relations - (a1, a2) is
unknown if only there are no ASPA records for a1.
And of course, a path //^\ (in your notation) received from customer or
peer is invalid. But I assume that you also had this in mind.

What I find curious in your proposal is the goal to extend the detection of
invalid paths for prefixes that are received from providers.
I was also considering this option, but it will not work with c2p database
only. The problem occurs with siblings.

Take a look at the next example:
a1 *p2p* a2 *c2c *a3 *p2c *a4 (p2p for peering, c2c for sibling, a4 is
checking ASPATH)
If records for a1 exists (so we know that a2 isn't in the set of providers
of a1), (a2, a3) records exist, but (a3, a2) doesn't, the outcome of
verification procedure at a4 will be invalid.

Maybe it can be fixed by adding a sibling flag to the c2p record, but at
the moment I'm not sure about security consequences.

ср, 26 июн. 2019 г. в 18:19, Iljitsch van Beijnum <iljitsch=
[email-masked]>:

> After an interesting discussion with Job Snijders the other day about our
> respective drafts, I think it would be helpful to analyze the issue of AS
> path validation further before discussion specific solutions.
>
> I think we can agree that any AS path that doesn't conform to the
> valley-free model. A quick refresher: the valley-free model assumes four
> types of relationships between ASes:
>
> customer-provider:  /
> provider-customer:  \
> peer-peer:          ^
> sibling-sibling:    -
>
> I've invented the / \ ^ - characters to indicate relationships myself, the
> idea being that they'll visually show valleys if a path isn't valley-free.
>
> You can visualize valley-freeness as the customer ASes at the bottom
> sending many up the hierarchy, and the money will only flow up, not down.
> So if you have a "valley" in the relationships between the ASes in a path,
> someone isn't getting paid and the whole thing doesn't work economically.
>
> The model also allows for mutual backup arrangements, where basically two
> ASes provide transit to each other (also called a sibling relationship).
> How that works financially is a bit murky, but the interesting thing here
> is that if nobody implements any policies or filters, you have a network
> with only sibling relationships.
>
> So with these four relationships and the valley-free restriction we should
> be able model any working real-world relationship between two or more ASes.
>
> (We'll ignore the possibility that the relationships between ASes may be
> different for different address families and/or prefixes for now.)
>
> For a formal definition of the valley-free model, read "On inferring
> autonomous system relationships in the internet", Gao, 2001.
>
> In addition to / \ ^ - we'll also allow ? to indicate an unknown
> relationship between two adjacent ASes in the path. And we'll assume the
> sibling relationship between an AS and itself (i.e., if there is AS path
> prepending).
>
> The steps:
>
> In other words: if steps 1 and 2 above just leave a ?, then regardless of
> what the unknown relationship turns out to be, we know the path will be
> valley-free and valid.
>
> So we can now extend the validation steps to consider unknown
> relationships and see even if we assume a best case scenario, we still end
> up with an invalid path:
>
> Now all of the above assumes that the relationship between two ASes is
> uncontested. But what if the two ASes claim to have different relationships?
>
> One approach would be to just assume an unknown relationship ?, so the
> path will only validate under worst case assumptions.
>
> In my opinion, a better approach would be just keep track of claims of a
> customer-provider relationship from the customer side (where the sibling
> relationship is simply a mutual customer-provider relationship claim).
>
> Overclaiming of the relationship by a customer is relatively
> unproblematic, because the claimed provider will simply not provide the
> service with no ill effect. Overclaiming by the provider, on the other
> hand, could be harmful, the combination of the relationship overclaim and
> incorrect BGP filters will now create a route leak that our path validation
> system will declare to have a valid path.
>
> There is probably no reason to publish peer-to-peer relationships, as a
> path with ? where there should be ^ will also validate.
>
> One interesting issue is route servers, as deployed by internet exchanges.
> Typically (universally?) those don't add their AS to the AS path, breaking
> the BGP specification in the process. In that case, the route server is
> invisible, so validation will have the same result as with a direct peering
> relationship.
>
> If this behavior is not universal, we should either assume a -
> relationship for route servers, or define a new type of relationship that
> will be removed from the valley-free validation process.
>
> With all of the above out of the way, we'll have to think about which
> relationship claims to carry in-band and which out-of-band.
>
> _______________________________________________
> Sidrops mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/sidrops
>

-- 
Best regards,
Alexander Azimov

---

From: Alexander Azimov <[email-masked]>
Date: Wed, 26 Jun 2019 19:51:55 +0300

And to follow up my previous email, if we have a network with malicious
intent that would hijack/disaggregate prefixes + create a 'virtual peering
link' between it and victim ASN, its customers will not able to detect it
anyway since it will look like a valid path: '-\'.

And we can't properly specify peerings because of transparent IXes.

ср, 26 июн. 2019 г. в 19:39, Alexander Azimov <[email-masked]>:

> What I find curious in your proposal is the goal to extend the detection
> of invalid paths for prefixes that are received from providers.
>> I've invented the / \ ^ - characters to indicate relationships myself,
>> the idea being that they'll visually show valleys if a path isn't
>> valley-free.
>>
>> So with these four relationships and the valley-free restriction we
>> should be able model any working real-world relationship between two or
>> more ASes.
>>
>> One interesting issue is route servers, as deployed by internet
>> exchanges. Typically (universally?) those don't add their AS to the AS
>> path, breaking the BGP specification in the process. In that case, the
>> route server is invisible, so validation will have the same result as with
>> a direct peering relationship.
>>

-- 
Best regards,
Alexander Azimov