Re: [Sidrops] On validating AS paths

[Alexander Azimov <[e-mail]>]

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=
[e-mail]>:

> (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.
>
> _______________________________________________
> Sidrops mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/sidrops
>


-- 
Best regards,
Alexander Azimov