[Sidrops] new ASPA-based AS path verification algorithms implemented in NIST BGP-SRx

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

For folks using the NIST BGP-SRx test examples (https://github.com/usnistgov/NIST-BGP-SRx/blob/master/examples/example-demo-aspa-new/README ) to test their implementation and comparing against the BGP-SRx implementation of ASPA, we provide below the descriptions of the new (corrected per [1]) path verification (i.e., route-leak detection) algorithms that we’ve used (in BGP-SRx). Comments/user experience feedback is welcome. 

I’ve also shared the text (algorithms below) with Alexander for the anticipated ASPA verification draft -09. The updated algorithms also include some essential special (or corner) cases that were not considered before in the draft.
 
New upstream AS path verification algorithm (when UPDATE is received from a lateral peer, customer, or non-transparent-RS client):

1. If there is an AS_SET present in the AS_PATH, then set AS_SET_Flag = 1, else set AS_SET_Flag = 0.
 
2. If there is not an AS_SEQUENCE present* but only an AS_SET, then the procedure halts with the outcome “Unverifiable”. Else, continue.

3. 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(1), AS(2), …, AS(N-1), AS(N)}, where AS(1) is the first-added AS in the AS_SEQUENCE and AS(N) is the last-added and neighbor to the receiving/validating AS.
  
4. If N = 1, then jump to Step 8. Else, continue.

5. At this step, N ≥ 2. For 2 ≤ i ≤ N, if there is an i for which AS(i) is attested “not Provider” by its left neighbor AS(i-1), then the procedure halts with the outcome “Invalid”. Else, continue.

6. For 1 ≤ i ≤ N-1, if there is an i for which AS(i) has no ASPA, then continue to the next step. Else, jump to Step 8.
 
7. If AS_SET_Flag = 0, then the procedure halts with the outcome “Unknown”. Else (i.e., AS_SET_Flag = 1), the procedure halts with outcome “Unverifiable”.
 
8. If AS_SET_Flag = 0, then the procedure halts with the outcome “Valid”. Else (i.e., AS_SET_Flag = 1), the procedure halts with outcome “Unverifiable”.

*  Note: Since AS_PATH is a mandatory attribute in eBGP, it must have an AS_SEQUENCE, or AS_SET, or both. 
...... 

New downstream AS path verification algorithm (when UPDATE is received from a transit provider or non-transparent RS):

1. If there is an AS_SET present in the AS_PATH, then set AS_SET_Flag = 1, else set AS_SET_Flag = 0. 

2. If there is not an AS_SEQUENCE present but only an AS_SET, then the procedure halts with the outcome “Unverifiable”. Else, continue.

3. 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(1), AS(2), …, AS(N-1), AS(N)}, where AS(1) is the first-added AS in the AS_SEQUENCE and AS(N) is the last-added and neighbor to the receiving/validating AS. 
 
4. If N ≤ 2, then jump to Step 11. Else, continue.

5. At this step, N ≥ 3. For 2 ≤ i ≤ N, determine the smallest i for which AS(i) is attested “not Provider” by its left neighbor AS(i-1). Denote such i as i_min. If i_min does not exist, then set i_min = N+1. For 1 ≤ j ≤ N-1, determine the largest j for which AS(j) is attested “not Provider” by its right neighbor AS(j+1). Denote such j as j_max. If j_max does not exist, then set j_max = 0.  If i_min ≤ j_max, then the procedure halts with the outcome “Invalid”. Else, continue to Step 6.

6. Up ramp: For 2 ≤ i ≤ N, determine the largest i (call it K) such that AS(i) is attested Provider by its left neighbor AS(i-1) for each i ≤ K. If such K does not exist, then set K = 1.

7. If K ≥ N-1, then jump to Step 11. Else, continue.

8. Down ramp: For 1 ≤ j ≤ N-1, determine the smallest j (call it L) such that AS(j) is attested Provider by its right neighbor AS(j+1) for each j ≥ L. If no such L exists, then set L = N.

9. If L-K ≤ 1, then jump to Step 11. Else (i.e., L-K ≥ 2), continue.

10. If AS_SET_Flag = 0, then the procedure halts with the outcome “Unknown”. Else (i.e., AS_SET_Flag = 1), the procedure halts with outcome “Unverifiable”. 

11. If AS_SET_Flag = 0, then the procedure halts with the outcome “Valid”. Else (i.e., AS_SET_Flag = 1), the procedure halts with outcome “Unverifiable”.
……

(Thanks to Oliver Borchert and Kyehwan Lee who recently encoded the above algorithms in the ASPA implementation and testing in NIST BGP-SRx. Included are test cases where the above downstream algorithm yields the correct verification results while the same in draft version -08 will yield incorrect results.)

Regards,
Sriram

[1]  K. Sriram and J. Heitz, "On the Accuracy of Algorithms for ASPA Based Route Leak Detection," IETF SIDROPS Meeting, March 2021. https://datatracker.ietf.org/meeting/110/materials/slides-110-sidrops-sriram-aspa-alg-accuracy-01