Re: [Sidrops] WGLC = draft-ietf-sidrops-aspa-verification - ENDS 03/22/2023 (Mar 22 2023)

["Sriram, Kotikalapudi (Fed)" <[e-mail]>]

Hi all,

It was very nice of Claudio to thoroughly review a pre-publication version of v-12 ( https://datatracker.ietf.org/doc/draft-ietf-sidrops-aspa-verification/ ).

He offered two detailed sets of comments that are copied below. All these comments have been carefully considered and changes incorporated.

Of course, there may be a few follow up questions/comments he may still have and would be welcome.  

Thank you, Claudio.

Sriram

===================================

Claudio's Comments Set #1:

From: Claudio Jeker <[e-mail]> 
Sent: Friday, February 17, 2023 11:06 AM

Hi Sriram,

Here is some initial feedback. I need a bit more time for section 5.

> 1.  Introduction
> 
>    The Border Gateway Protocol (BGP) as originally designed is known to
>    be vulnerable to prefix (or route) hijacks and BGP route leaks
>    [RFC7908].  Some existing BGP extensions are able to partially solve
>    these problems.  For example, RPKI-based route origin validation
>    (RPKI-ROV) [RFC6480] [RFC6482] [RFC6811] [RFC9319] can be used to
>    detect and filter accidental mis-originations.  [RFC9234] or
>    [I-D.ietf-grow-route-leak-detection-mitigation] can be used to detect
>    and mitigate accidental route leaks.  While RPKI-ROV can prevent
>    accidental prefix hijacks, malicious forged-origin prefix hijacks can
>    still occur [RFC9319].  RFC9319 includes some recommendations for
>    reducing the attack surface for forged-origin prefix hijacks.
> 
>    This document describes procedures that make use of Autonomous System
>    Provider Authorization (ASPA) objects [I-D.ietf-sidrops-aspa-profile]
>    in the Resource Public Key Infrastructure (RPKI) to verify the Border
>    Gateway Protocol (BGP) AS_PATH attribute of advertised routes.  
> These

I would just use BGP here. The introduction starts with The Border Gateway Protocol (BGP) so I think there is no need to repeat that again.
RPKI was already used in the previous paragraph but not "Resource Public Key Infrastructure".

...

> 2.  Autonomous System Provider Authorization
> 
>    An ASPA record is a digitally signed object that binds, for a
>    selected Address Family Identifier (AFI), a set of Provider AS
>    numbers to a Customer AS number (CAS) (in terms of BGP announcements,
>    not business relationship) and is signed by the CAS.  It attests 
> that

I would alter this and move the AFI bits somewhere else. It almost sounds like the ASPA records are per AFI which is not true.

>    the CAS has a Set of Provider ASes (SPAS) as specified in the ASPA.
>    The definition of Provider AS in given in Section 1 of
>    [I-D.ietf-sidrops-aspa-profile].  A function of a Provider AS is to
>    propagate a Customer AS's IPv4 or IPv6 announcements onward, i.e., 
> to

propagate a Customer AS's IPv4, IPv6 or both announcements onward

My point here is that I want to make the optional AFI in ASPA profile as optional as possible. ISPs should think twice before limiting the AFI.
The standard should steer people away from AFI limits.

> 3.  ASPA Registration Recommendations
> 
>    A CAS MUST register each of its transit provider ASes in its ASPA
>    object(s).  A network operator SHOULD register all its providers in a
>    single ASPA object.  An AS that is an RS-client of a non-transparent
>    IXP RS AS MUST include the AS number (ASN) of the RS AS in its SPAS.

I think this is good but then it becomes confusing and is filled with bad examples, errors and bad advice.
 
>    An ASPA (AS, [0], AFI) showing AS 0 as the provider is referred to as
>    an AS0 ASPA.  Registration of an ASPA with the SPAS containing only
>    AS 0 is a statement by the registering AS that it has no transit
>    providers.  A non-transparent RS AS MUST register an AS0 ASPA.  The
>    so-called "Tier-1" ASes do not have transit providers.  A Tier-1 AS
>    MUST register an ASPA with SPAS including AS 0 and any transparent
>    IXP RS ASes at which it is an RS-client.  An AS (non-Tier-1) that is
>    an RS-client of a non-transparent IXP RS AS MUST include the ASN of
>    the RS AS in its SPAS.  An AS (non-Tier-1) that is an RS-client of a
>    transparent IXP RS AS MUST register an ASPA including all its transit
>    provider ASes in its SPAS but need not include the transparent RS AS
>    in the SPAS, such inclusion is OPTIONAL.

This is confusing and some advice I think is even wrong.

First of all ASPA records with AS0 only work if AS0 is the only entry (or the only entry for a specific AFI. The standard is unclear about this but more about that further below).

I would rewrite this and remove most of the Tier-1 explanation.
First of all "A Tier-1 AS MUST register an ASPA with SPAS including AS 0 and any transparent IXP RS ASes at which it is an RS-client." is in my opinion incorrect. A Tier-1 should have an AS 0 ASPA record unless they peer with a non-transparent IXP RS or have complex lateral peering agreements. I don't understand why transparent IXPs need to be added for
Tier-1 but not any other ISP. I think this is still based on some confused idea for earlier.

So my suggestion here would be:

	An ASPA (AS, [0], AFI) has no valid provider AS and is therefor
	a statement that the AS is transit free. Such AS0 ASPA records
	should be used by IXP RS ASes and so-called "Tier-1" ASes. If such
	an AS is connected as a rs-client to a non-transparent IXP RS AS
	the ASnum of the IXP RS MUST be included in the SPAS. Additionally
	some later peerings may require addition of the peer ASnum in the SPAS.

Maybe one needs to be more explicit about IXP RS having AS0 ASPA records but it is possible that a IXP RS AS gets transit to announce the IXP LAN.
In that case the IXP RS needs to include its transit providers in the SPAS.

>    It is thought to be unlikely that there could be an AS that is not
>    Tier-1 and does not have any transit providers.  However, if there
>    exists such an AS, it MUST register an ASPA with SPAS including AS 0
>    and any transparent IXP RS ASes at which it is an RS-client.

I don't think this paragraph is helpful. ISP network admins should be able to understand which of their BGP sessions are customer - provider relations and require inclusion in the SPAS.

>    If AS 0 exists in the SPAS of an ASPA along with some provider ASes,
>    then the presence of the AS 0 has no effect on the AS_PATH
>    verification procedures.  The verification procedures simply consider
>    the other (distinct from AS 0) provider ASes as the authorized
>    transit providers of the CAS in consideration.

I think this is a problem. Any ASPA can be expressed in two ways. One including AS0 and one without AS0. The moment an additional AS is in the SPAS there is no need to have AS0 in the profile. Since for X.509 a minimal and stable encoding is required I think one MUST forbid to include
AS0 in objects with other elements. (Now this depends on the stupid AFI again but more on that below).
 
>    A pair of ASes can have a sibling relationship (each AS considers the
>    other as a customer), i.e., the customer-to-provider relationship
>    applies in both directions.  In such cases, each of the two ASes MUST
>    register its ASPA including the other (sibling) AS in its SPAS.

> 4.  Hop-Check Function
> 
>    Let AS(i) and AS(j) represent adjacent unique ASes in an AS_PATH, and
>    thus (AS(i), AS(j)) represents an AS hop.  A hop-check function,
>    hop(AS(i), AS(j), AFI), checks if the ordered pair of ASNs, (AS(i),
>    AS(j)), has the property that AS(j) is an attested provider of AS(i)
>    per SPAS corresponding to AS(i)'s ASPA for the specified AFI.  This
>    function is specified as follows:
> 
>                              /
>                              | "Provider" if AS(i)'s SPAS
>                              |   includes AS(j)
>                              |
>    hop(AS(i), AS(j), AFI) =  / "Not Provider" if AS(i)'s SPAS
>                              \   does not include AS(j)
>                              |
>                              | "no Attestation" if AS(i) does not
>                              |  have ASPA (i.e., VAP)
>                              \
>                        Figure 1: Hop Check Function.
> 
>    The hop-check function is AFI dependent because an AS may have
>    different SPAS for different AFI.  This function is used in the ASPA-
>    based AS_PATH validation (route leak detection) algorithms described
>    in Section 5.1 and Section 5.2.  While describing the algorithms, for
>    simplicity, the function hop(AS(i), AS(j), AFI) is replaced with
>    hop(AS(i), AS(j)) by dropping the AFI since it would be understood
>    that the algorithms are run for a specific AFI at a time (AFI = 1 or
>    AFI = 2).

In general I like this paragraph but there is this extra complexity of the AFI again which makes this a bit ambiguous.

Consider the following ASPA record CAS AS5 -> SPAS (AS7 only IPv4) So there is an ASPA VAP record for AS5. The SPAS is AS7 but only for AFI 1.

What should hop(AS5, AS9, AFI=2) return? "no Attestation" or "Not Provider"?

Btw. the above example can be extended with two additional cases:

CAS AS5 -> SPAS (AS7 only IPv4, AS0)
CAS AS5 -> SPAS (AS7 only IPv4, AS0 only IPv6)

Now these two entries both behave the same for hop(AS5, AS9, AFI=2) and return "Not Provider" but we have two encodings resulting in the same outcome.

There is this implicit idea that BGP implementations will implement two lookup tables and have everything split by AFI but that is not how OpenBGPD implemented this. And even then it is unclear how the two tables are built based on the ASPA profile data.

I really dislike the inclusion of AFI in the ASPA profile. I find it even worse that everyone assumes that records are duplicated out from the ASPA profile (e.g. the RTR draft covering ASPA has no concept of optional AFI).
Still most people will not use AFI specific entries (since you get both
IPv4 and IPv6 transit (unless your called HE or Cogent)).

I think the important part here is that the specification for the Hop-Check function must be clear what the behaviour is in the above case or there will be slightly different implementations.

Sorry, I'm terribly grumpy about the inclusion of AFI in ASPA and the resulting complications because of it. I had to invest too much time handling all this AFI complication.


> 5.  AS_PATH Verification

Skipping for later. I need to read this once more before giving feedback.

> 6.  AS_PATH Verification Recommendation 7.  Mitigation

These read OK to me.

> 8.  Operational Considerations
> 8.1.  Mutual Transit (Complex Relations)
> 
>    There are peering relationships which cannot be described as strictly
>    simple peer-to-peer (i.e., lateral peers) or customer-to-provider.
>    An example is when both parties (ASes) consider each other as a
>    customer, i.e., the customer-to-provider relationship applies in each
>    direction.  That is called a sibling relationship, and in such cases,
>    each AS must register an ASPA including the other AS in its SPAS (see
>    Section 3.
> 
> 8.2.  AS Confederations
> 
>    The ASes on the boundary of an AS Confederation MUST register ASPAs
>    using the Confederation's global ASN and the procedures for ASPA-
>    based AS_PATH validation in this document are NOT RECOMMENDED for use
>    on eBGP links internal to the Confederation.

Should Section 8 and Section 3 be merged into one section? It kind of cover the same topic.

Section 9 and 10 read ok.

> 11.  Security Considerations
> 
>    The proposed mechanism is compatible only with BGP implementations
>    that can process 32-bit ASNs in the AS_PATH.  This limitation should
>    not have a real effect on operations since legacy BGP routers are
>    rare and it is highly unlikely that they support integration with the
>    RPKI.

Is this really a security concern?
 
>    ASPA issuers should be aware of the implications of the ASPA-based AS
>    path validation.  A customer AS must keep its ASPA objects correct
>    and current (unexpired).  Otherwise, for example, if a provider AS is
>    left out of the Set of Provider ASes (SPAS) in the ASPA, then routes
>    containing the customer AS and said provider AS may be incorrectly
>    labeled as route leaks and rejected.

Again not really a security consideration. This is more an operational consideration. Don't publish bad data, it will hurt you.
 
>    It is highly recommended that a compliant AS should maintain a single
>    ASPA object that covers all its providers.  Such a practice will help
>    prevent race conditions during ASPA updates that might affect prefix
>    propagation.  The software that provides hosting for ASPA records
>    SHOULD support enforcement of this practice.  During a transition
>    process between different certificate authority (CA) registries, the
>    ASPA records SHOULD be kept identical in all registries.

Shouldn't this be in the profile specification?
 
>    While the ASPA-based mechanism is able to generally detect both
>    mistakes and malicious activity affecting routes received from
>    customers, RS-clients, or lateral peers, it might fail to detect some
>    malicious path modifications for routes that are received from
>    transit providers (see Section 7).

Neither this section not section 7 really provides an insight in how malicious path modifications are detected by ASPA. Is this something that should be properly explained?
>From my understanding it largely depends on ISPs having both ASPA and ROA entries published.
 
>    Since an upstream provider becomes a trusted point, in theory it
>    might be able to propagate without detection some instances of
>    hijacked prefixes of its customers or routes with malformed or
>    manipulated AS_PATHs.  While it may happen in theory, it does not
>    seem to be a realistic scenario.  Normally a customer and its transit
>    provider would have a signed agreement, and a policy violation (of
>    the above kind) should have legal consequences or the customer can
>    just drop the relationship with such a provider and remove the
>    corresponding ASPA record.

This is a valid point and also the reason why people should not add extra ASnums in the SPAS.

Not sure if I will work on Section 5 on the weekend but you should get that feedback by start of next week.

Cheers (and thanks for the draft update)
--
:wq Claudio

=====================================

Claudio's Comments Set #2:

From: Claudio Jeker <[e-mail]> 
Sent: Thursday, February 23, 2023 10:12 AM

Here is part two of the review for section 5. 

> 5.  AS_PATH Verification
> 
>    The procedures described in this document are applicable only to
>    four-octet AS number compatible BGP speakers [RFC6793].  If such a
>    BGP speaker receives both AS_PATH and AS4_PATH attributes in an
>    UPDATE, then the procedures are applied on the reconstructed AS path
>    (Section 4.2.3 of [RFC6793]).  So, the term AS_PATH is used in this
>    document to refer to the usual AS_PATH [RFC4271] as well as the
>    reconstructed AS path (the latter in instances when reconstruction is
>    performed).

So much text for something so simple. Also the requirement is mainly there because old 2-byte only systems have no way to validate 4-byte ASnums. It would work for 2-byte only paths but better not go down that route.
 
>    If an attacker creates a route leak intentionally, they may try to
>    strip their AS from the AS_PATH.  To partly guard against that, a
>    check is necessary to match the most recently added AS in the AS_PATH
>    to the BGP neighbor's ASN.  This check MUST be performed as specified
>    in Section 6.3 of [RFC4271].  If the check fails, then the AS_PATH is
>    considered a Malformed AS_PATH and the UPDATE is considered to be in
>    error (Section 6.3 of [RFC4271]).  The case of transparent RS MUST
>    also be appropriately taken care of (e.g., by suspending the neighbor
>    ASN check).  Note that the check fails also when the AS_PATH is empty
>    (zero length) and that is appropriate.  These checks are commonly a
>    part of commercial BGP implementations and support the AS path
>    validation procedures in this document.

First of all please remove 'commercial' from 'These checks are commonly a part of commercial BGP implementations'. Non-commercial BGP implementations also commonly have these checks. All in all this last sentence adds very littler to the discussion.

I like the 'This check MUST be performed' requirement but I'm not entirely sure how this is enforced. Should this be enforced by the role?
Because of transparent RSes the 'enforce neighbor-as' check is normally a config option and an admin can toggle this off for e.g. customer sessions.
Does the 'MUST be performed' require a compliant BGP implementation to force this toggle on or should it be an extra check on top of this or is the idea to just ignore the issue and hope for the best?

To be more clear RFC4271 Section 6.3 has:
   If the UPDATE message is received from an external peer, the local
   system MAY check whether the leftmost (with respect to the position
   of octets in the protocol message) AS in the AS_PATH attribute is
   equal to the autonomous system number of the peer that sent the
   message.  If the check determines this is not the case, the Error
   Subcode MUST be set to Malformed AS_PATH.

Now this MAY is upgraded to a MUST by this draft. But it is done in a non-explicit way. Also RFC7606 should be mentioned about this:

   [RFC4271] also says that an implementation optionally "MAY check
   whether the leftmost ... AS in the AS_PATH attribute is equal to the
   autonomous system number of the peer that sent the message".  A BGP
   implementation SHOULD also handle routes that violate this check
   using "treat-as-withdraw" but MAY follow the "session reset" behavior
   if configured to do so.

Also are we sure that
   Note that the check fails also when the AS_PATH is empty (zero length)
   and that is appropriate. 
is indeed true for all BGP implementations? (I agree that this is the right behaviour but the note is phrased in a strange way).

>    Wherever AFI is mentioned in the AS_PATH validation algorithms, it
>    refers to the AFI of the prefix in the route for which the AS_PATH
>    validation is performed.  When an AS_PATH is evaluated as Valid,
>    Invalid, or Unknown, it pertains only to the AFI for which the
>    validation was performed.  The same AS_PATH can have a different
>    validation outcome for a different AFI.  Since it is understood that
>    the algorithms described here are run for a single AFI at a time
>    (pertaining to the route(s) being verified), the AFI in the function
>    hop(AS(i), AS(j), AFI) is not shown explicitly for simplicity for the
>    reader.
> 
> 
> 5.1.  Algorithm for Upstream Paths
> 
>    The upstream verification algorithm described here is applied when a
>    route is received from a customer or lateral peer, or received by an
>    RS from an RS-client, or received by an RS-client from an RS.

Why are RS and RS-client special here? Wouldn't it be enough to use:
    The upstream verification algorithm described here is applied when a
    route is received from a customer, lateral peer, RS or RS-client.

Once could even add that only the (transit) provider role is not using this algorithm.
 
>    The basic principles of the upstream verification algorithm are
>    stated here.  Let the sequence {AS(N), AS(N-1),..., AS(2), AS(1)}
>    represent the AS_PATH in terms of unique ASNs, where AS(1) is the
>    origin AS and AS(N) is the most-recently added AS and neighbor of the
>    receiving/validating AS.  For each hop AS(i-1) to AS(i)in this
>    sequence, the hop-check function, hop(AS(i-1), AS(i)), must equal
>    "Provider" (Section 4) for the AS_PATH to be Valid .  If the hop-
>    check function for at least one of those hops is "Not-Provider", then
>    the AS_PATH would be Invalid.  If the AS_PATH verification outcome is
>    neither Valid nor Invalid (per above principles), then it would be
>    evaluated as Unknown.
> 
>    The upstream path verification procedure is specified as follows:
> 
>    1.  If the AS_PATH has an AS_SET, then the procedure halts with the
>        outcome "Invalid".

Should this be moved to Section 5 and have a common set of procedure steps that must be handled first? No AS_SETs, neighbor-as check, empty AS_PATH check. Since these points are common among the two algorithms.
 
>    2.  Collapse prepends in the AS_SEQUENCE(s) in the AS_PATH (i.e.,
>        keep only the unique AS numbers).  Let the resulting ordered
>        sequence be represented by {AS(N), AS(N-1), ..., AS(2), AS(1)},
>        where AS(1) is the first-added (i.e., origin) AS and AS(N) is the
>        last-added AS and neighbor to the receiving/validating AS.
> 
>    3.  If N = 1, then then the procedure halts with the outcome "Valid".
>        Else, continue.
> 
>    4.  At this step, N >= 2.  For 2 <= i <= N, if there is an i for
>        which hop(AS(i-1), AS(i)) = "not Provider", then the procedure
>        halts with the outcome "Invalid".  Else, continue.
> 
>    5.  For 2 <= i <= N, if there is an i for which hop(AS(i-1), AS(i)) =
>        "no Attestation", then the procedure halts with the outcome
>        "Unknown".  Else, the procedure halts with the outcome "Valid".
> 
> 5.1.1.  About Path Validation at IXP RS AS and RS-Client
> 
>    As stated above (top of Section 5.1), the algorithm for upstream
>    paths is applied for path validation at IXP RS AS and RS-clients.
>    The justifications are as follow.  The RS-client to RS AS
>    relationship is effectively a customer-to-provider relationship.  The
>    RS AS propagates the routes of an RS-client and its customers to
>    other RS-clients.  An RS-client at a transparent RS effectively has a
>    lateral peer relationship with other RS-clients that it connects to
>    via the RS.  So, the algorithm for upstream paths clearly applies at
>    an RS AS and at RS-clients of a transparent RS.
> 
>    Since an RS AS (transparent or non-transparent) does not have
>    providers or lateral peers, an RS-client of a non-transparent RS
>    expects an AS_PATH it receives to be consisting of only customer-to-
>    provider hops successively from AS(1) (origin) the AS(N) (neighbor
>    which is the RS AS).  This expectation is identical to what is
>    expected when the UPDATE is received from a customer or lateral peer.
>    Hence, the algorithm for upstream paths applies also at an RS-client
>    of a non-transparent RS.

I find this section a bit strange. There is no discussion why lateral peers should use the upstream algorithm or why it should be used for clients. I find the first paragraph hard to understand (especially the use of customer-to-provider relationship puts me off the rails).
The 2nd paragraph starts talking about (transparent or non-transparent) RS but then only covers the non-transparent case but I think the logic applies to both.

Maybe it helps to split this up further:

  An RS-client connected to a transparent RS effectively has a
  lateral peer relationship with other RS-clients that it connects to via
  the RS. The RS is transparent is therefore not part of the AS_PATH.

  An RS-client connected to a non-transparent RS has effectively a
  customer-to-provider relationship towards the RS but the non-transparent
  RS to RS-client connection is a lateral peer relationship. So the
  RS-client should again use the upstream algorithm.

  A RS (transparent or non-transparent) to RS-client connection is
  effectively a lateral peer relationship. Therefor the AS_PATH the RS
  receives should only consist of customer-to-provider hops.

I think it would also be fine to just drop 5.1.1 altogether.

In general I think the explanation of why two different validation algorithms exist and when to use upstream and downstream algorithm should be moved up to section 5 (maybe as subsection there).
 
> 5.2.  Algorithm for Downstream Paths
> 
>    The downstream verification algorithm described here is applied when
>    a route is received from a transit provider.
> 
>    It is not essential, but the reader may take a look at the
>    illustrations and formal proof in [sriram1] to develop a clearer
>    understanding of the algorithm described here.
> 
>    Here again (as in Section 5.1), let the AS_PATH be simplified and
>    represented by the ordered sequence of unique ASNs as {AS(N),
>    AS(N-1),..., AS(2), AS(1)}.
> 
>    If the AS_PATH is empty or it has an AS_SET, then the AS_PATH is
>    Invalid.  If there is no AS_SET in the AS_PATH and N <= 2, then the
>    AS_PATH is trivially Valid.
> 
>    In the following descriptions regarding determination of Invalid,
>    Valid, or Unknown, it is assumed that the AS_PATH contains no AS_SETs
>    and contains 3 or more unique ASNs (N >= 3).

Again by moving the AS_SET and empty AS_PATH checks to a generic step would simplify this text. Always repeating that the AS_PATH contains no AS_SETs is not helpful.
 
>    *Determination of Invalid AS_PATH:*
> 
>    Given the above ordered sequence, if there exist indices u and v such
>    that (1) u <= v, (2) hop(AS(u-1), AS(u)) = "not Provider", and (3)
>    hop(AS(v+1), AS(v)) = "not Provider", then the AS_PATH is Invalid.

Would it be possible to use L and K here instead of v and u so that Figure
2 could help visualize the condition?
 
>    *Determination of Valid AS_PATH:*
> 
>    As shown in Figure 2, assume that the ASes in the AS_PATH are in the
>    same physical (locational) order as in the sequence representation
>    {AS(N), AS(N-1),..., AS(2), AS(1)}, i.e., AS(N) is the left most and
>    AS(1) the right most.
> 
> 
>                        AS(L) ............. AS(K)
>                         /                     \
>                     AS(L+1)                  AS(K-1)
>                        .                       .
>                       .                         .
>        (down-ramp)   .                           .   (up-ramp)
>                     .                             .
>                    .                               .
>                  AS(N-1)                          AS(2)
>                    /                                \
>                 AS(N)                               AS(1)
>                  /                                (Origin AS)
>        Receiving & Validating AS
> 
>            Each ramp has consecutive ASPA-attested
>            customer-to-provider hops in the bottom-to-top direction
> 
>               Figure 2: Illustration of up-ramp and down-ramp.
> 
>    Looking at Figure 2, the UPDATE is received from a provider (i.e.,
>    AS(N) is a provider), it may have both an up-ramp (on the right
>    starting at AS(1)) and a down-ramp (on the left ending at AS(N)).  An
>    explanation of what the ramps mean is as follows.  The sequence of
>    ASes in either of these ramps is ASPA Valid.

I think the use of ASPA Valid is unfortunate here. Shouldn't that be "Provider only". At least both ramps represent the case where the hop() function returns Provider for the corresponding lookup.

>                                                  The up-ramp starts at
>    AS(1) and each AS hop, (AS(i), AS(i+1)), in it has the property that
>    hop(AS(i), AS(i+1)) = "Provider" for i = 1, 2,... , K-1.  If such a K
>    does not exist, then K is set to 1.  The up-ramp ends (reaches its
>    apex) at AS(K) because hop(AS(K), AS(K+1)) = "Not Provider" or "no
>    Attestation".  The down-ramp ends at AS(N) and each AS hop, (AS(i),
>    AS(i-1)), in it has the property that hop(AS(i), AS(i-1)) =
>    "Provider" for i = N, N-1,... , L+1.  If such an L does not exist,
>    then L is set to N.  The down-ramp starts at AS(L) because hop(AS(L),
>    AS(L-1)) = "Not Provider" or "no Attestation".  Thus, the apex of the
>    down-ramp is AS(L).

I wonder if it helps to use a different index than i in the down-ramp part of the text. Mainly first i increases from 1 to K-1 but in the down-ramp i now decreases from N to L+1. Also I think "The down-ramp ends at AS(N)"
is adding to the confusion. The down-ramp starts at AS(N) and goes in reverse all the way to AS(L).

At least I would prefer to see L and K as the endpoints of the ramps.

>    If there is an up-ramp that runs across all ASes in the AS_PATH
>    (i.e., K = N), then clearly the AS_PATH is Valid (i.e., not a route
>    leak).  Similarly, if there is a down-ramp that runs across all ASes
>    in the AS_PATH (i.e., L = 1), then also the AS_PATH is valid (i.e.,
>    not a route leak).  However, if both ramps exist in an AS_PATH with K
>    < N and L > 1, then the AS_PATH is Valid if and only if L-K <= 1.
>    Note that K could be greater than L (i.e., L-K has a negative value)
>    which means that the up-ramp and down-ramp overlap, and that could
>    happen when some adjacent AS pairs in the AS_PATH have mutually
>    registered sibling relationships (i.e., include each other in their
>    respective SPAS) (see Section 3).  If L-K = 0, it means that the
>    apexes of the up-ramp and down-ramp are at the same AS.  If L-K = 1,
>    it means that the apexes are at adjacent ASes.

Maybe mention here that adjacent ASes are lateral peers.

>                                                    In summary, the
>    AS_PATH is Valid if L-K is 0 or 1 or has a negative value.
> 
>    *Determination of Unknown AS_PATH:*
> 
>    If L-K >= 2, then the AS_PATH is either Invalid (route leak) or
>    Unknown (see illustrations and proof in [sriram1]).  However, if L-K
>    >= 2 and an Invalid outcome was not found by the process described
>    earlier in this section, then the AS_PATH is determined to be
>    Unknown.
> 
>    The downstream path verification procedure is formally specified as
>    follows:
> 
>    1.  If the AS_PATH has an AS_SET, then the procedure halts with the
>        outcome "Invalid".
> 
>    2.  Collapse prepends in the AS_SEQUENCE(s) in the AS_PATH (i.e.,
>        keep only the unique AS numbers).  Let the resulting ordered
>        sequence be represented by {AS(N), AS(N-1), ..., AS(2), AS(1)},
>        where AS(1) is the first-added (i.e., origin) AS and AS(N) is the
>        last-added AS and neighbor to the receiving/validating AS.
> 
>    3.  If N <= 2, then the procedure halts with the outcome "Valid".
>        Else, continue.
> 
>    4.  At this step, N >= 3.  Given the above ordered sequence, find the
>        lowest value of i (2 <= i <= N) for which hop(AS(i-1), AS(i)) =
>        "not Provider".  Call it u_min.  If no such u_min exists, set
>        u_min = N+1.  Find the highest value of j (N-1 >= j >= 1) for
>        which hop(AS(j+1), AS(j)) = "not Provider".  Call it v_max.  If
>        no such v_max exists, then set v_max = 0.  If u_min <= v_max,
>        then the procedure halts with the outcome "Invalid".  Else,
>        continue.
> 
>    5.  Up-ramp: For 2 <= i <= N, determine the largest p such that
>        hop(AS(i-1), AS(i)) = "Provider" for each i in the range 2 <= i
>        <= p.  Call such largest p as K.  If such largest p does not
>        exist, then set K = 1.

I would remove the indirection over p here:

     5.  Up-ramp: For 2 <= i <= N, determine the largest K such that
         hop(AS(i-1), AS(i)) = "Provider" for each i in the range 2 <= i
         <= K.  If no such largest K exist, then set K = 1.

 
>    6.  If K = N, then the procedure halts with the outcome "Valid".
>        Else, continue.

Is this necessary? If K = N then L-K can only be <= 1 since L <= N.
I would remove this step.
 
>    7.  Down-ramp: For N-1 >= j >= 1, determine the smallest q such that
>        hop(AS(j+1), AS(j)) = "Provider" for each j in the range N-1 >= j
>        >= q.  Call such largest q as L.  If such smallest q does not
>        exist, then set L = N.
 
Same as above:
     7.  Down-ramp: For N-1 >= j >= 1, determine the smallest L such that
         hop(AS(j+1), AS(j)) = "Provider" for each j in the range N-1 >= j
         >= L.  If no such smallest L exist, then set L = N.

Also Step 4 could use a similar treatment.

>    8.  If L-K <= 1, then the procedure halts with the outcome "Valid".
>        Else, the procedure halts with the outcome "Unknown".
> 

I think it would be worth mentioning that Step 4., 5. and 7. can be calculated at the same time.

I want to be clear that this version is a lot better than the one in -11.
It removed the unnecessary AS_PATH reversion which caused me so much mental work to process. I like that there is a text version and a more step by step algorithmic version of both up- and downstream validations functions.

IMO it would further help to move the generic check for AS_SET, empty AS_PATH etc. out into a common step so that the algorithms no longer need to mention AS_SET and empty AS_PATH.

This is a great step forward, thanks for all the work.
--
:wq Claudio