[PATCH] Nest: correct aspa_check() implementation
Evann DREUMONT
bird at evann.dev
Sun Feb 8 02:39:05 CET 2026
Hello,
Earlier this week, while building a BGP lab I've discovered a weird behavior with aspa_check() that was rejecting routes that should be correct. It seems to be the same bug as https://trubka.network.cz/pipermail/bird-users/2026-February/018611.html.
I discover that the previous implementation of the verification algorithm was not fully compliant with the current internet draft (draft-ietf-sidrops-aspa-verification-24) and could incorrectly filter routes when the up-ramp and down-ramp apex were apart by exactly one hop. In practice, this caused legitimate routes to be dropped, such as routes involving Tier-1 peering while having an AS0 ASPA record.
One of my test sample was the following AS_PATH: 10846, 7018, 174, 29075, 208627 with the following ASPA records:
- AS208627 => AS29075
- AS174 => 0
- AS7018 => 0
- AS10846 => 7018
If you manually compute the upstream and downstream bounds, you get
- max_down = 5 - 3 + 1 = 3
- min_down = 5 - 4 + 1 = 2
- max_up = 2
- min_up = 2
Using the downstream algorithm:
- max_up + max_down = 5 >= N, so the route is not invalid and we continue
- min_up + min_down = 4 < N, so the route is unknown
If you draw this on paper, it makes sense. However, BIRD reports this route as invalid, which is unexpected.
Given this issue, I tried to implement a patch. With a bit of help of Alarig, I managed to get a working version that still passes the existing unit tests (except one) as well as our corner case. While I tried to understand the initial logic, it was quite hard to follow. Therefore, I tried, as much as possible, to follow the algorithm from the I.D. Something not trivial since the AS_PATH is reversed compared to the draft.
This patch also contains few documentation comments. While I am not usually a big fan of comments, I think these are needed to highlight the differences between our implementation and the algorithm specified in the Internet-Draft.
To improve unit test coverage, I have added the missing test cases from the official list (https://raw.githubusercontent.com/ksriram25/IETF/main/ASPA_path_verification_examples.pdf). They all passed successfully.
However, one of the existing custom unit tests did not pass. In this test, the path consists of two ASes: 65544, 65541. AS65544 declare an AS0 ASPA and AS65541 declare AS65545 as a provider.
The test expects the route to be invalid. However, I believe this expectation is incorrect. Manual computation gives:
- min_up = 1
- max_up = 1
- max_down = 2 - 2 + 1 = 1
- min_down = 2 - 2 + 1 = 1
Using the downstream algorithm:
- max_up + max_down = 2 >= N, so the route is not invalid and we continue
- min_up + min_down = 2 >= N, so the route is not unknown, and therefore the route is valid.
This actually makes sense: although there is no explicit valid ASPA, from a downstream perspective, this can be interpreted as a peering relationship between AS65544 and AS65541 (with the up-ramp and down-ramp apexes separated by exactly one hop), and the route should therefore be considered valid (see: https://datatracker.ietf.org/doc/html/draft-ietf-sidrops-aspa-verification-24#section-5.1).
Don't hesitate to discuss the patch if needed,
--
Evann
-------------- next part --------------
>From 0835f0e25bdddff2206863ab7a90ceff3a1e62d9 Mon Sep 17 00:00:00 2001
From: Evann DREUMONT <evann at grifon.fr>
Date: Sat, 7 Feb 2026 23:59:12 +0100
Subject: [PATCH] Nest: correct aspa_check() implementation
The previous implementation of the verification algorithm was not fully
compliant with the current internet draft
(draft-ietf-sidrops-aspa-verification-24) and could incorrectly filter routes
when the up-ramp and down-ramp apex were apart by exactly one hop. In practice,
this caused legitimate routes to be dropped, such as routes involving Tier-1
peering while having an AS0 ASPA record.
In parallel, the algorithm was refactored to match more closely the one
described in the internet draft, and commented to outline the major
differences.
This commit implements missing test cases based on the official ASPA
path verification examples to expand coverage.
Finally, one of the custom test was incorrect, because while there is no valid
ASPA this could be seen, from a downstream perspective, as peering.
Signed-off-by: Evann DREUMONT <53308142+LeGmask at users.noreply.github.com>
---
filter/test.conf | 54 ++++++++++++++++++-
nest/rt-table.c | 138 ++++++++++++++++++++++++++---------------------
2 files changed, 129 insertions(+), 63 deletions(-)
diff --git a/filter/test.conf b/filter/test.conf
index 096798c5..0019d51b 100644
--- a/filter/test.conf
+++ b/filter/test.conf
@@ -2469,7 +2469,7 @@ function t_aspa_check()
bgppath p3 = +empty+;
p3.prepend(65541);
p3.prepend(65544);
- bt_assert(aspa_check(at, p3, false) = ASPA_INVALID);
+ bt_assert(aspa_check(at, p3, false) = ASPA_VALID);
bt_assert(aspa_check(at, p3, true) = ASPA_INVALID);
}
@@ -2485,6 +2485,13 @@ protocol static
route aspa 65543 providers 65546;
route aspa 65544 providers 65546, 65547;
route aspa 65547 transit;
+ route aspa 65548 transit;
+ route aspa 65550 transit;
+ route aspa 65551 providers 65550;
+ route aspa 65552 transit;
+ route aspa 65553 transit;
+ route aspa 65554 providers 65553;
+ route aspa 65555 providers 65554;
}
function t_aspa_check_official()
@@ -2494,6 +2501,7 @@ function t_aspa_check_official()
bool UP = true; bool DOWN = false;
bgppath p;
+ # Examples of Upstream Path Verification
# F-G is a lateral peer, we do not prepend
p = +empty+.prepend(A).prepend(C).prepend(F);
bt_assert(aspa_check(at_official, p, UP) = ASPA_VALID);
@@ -2529,6 +2537,50 @@ function t_aspa_check_official()
# E-D is a lateral peer, we do not prepend
p = +empty+.prepend(B).prepend(E);
bt_assert(aspa_check(at_official, p, UP) = ASPA_VALID);
+
+ # Examples of Downstream Path Verification
+ p = +empty+.prepend(A).prepend(C).prepend(F).prepend(G).prepend(E);
+ bt_assert(aspa_check(at_official, p, DOWN) = ASPA_UNKNOWN);
+
+ p = +empty+.prepend(A).prepend(D).prepend(G).prepend(E);
+ bt_assert(aspa_check(at_official, p, DOWN) = ASPA_VALID);
+
+ p = +empty+.prepend(A).prepend(C).prepend(D).prepend(E);
+ bt_assert(aspa_check(at_official, p, DOWN) = ASPA_UNKNOWN);
+
+ p = +empty+.prepend(A).prepend(C).prepend(D).prepend(G).prepend(E);
+ bt_assert(aspa_check(at_official, p, DOWN) = ASPA_INVALID);
+
+ p = +empty+.prepend(G).prepend(D).prepend(F).prepend(C);
+ bt_assert(aspa_check(at_official, p, DOWN) = ASPA_UNKNOWN);
+
+ p = +empty+.prepend(B).prepend(E).prepend(G).prepend(D);
+ bt_assert(aspa_check(at_official, p, DOWN) = ASPA_VALID);
+
+ p = +empty+.prepend(B).prepend(E).prepend(G).prepend(D).prepend(C);
+ bt_assert(aspa_check(at_official, p, DOWN) = ASPA_INVALID);
+
+ p = +empty+.prepend(A).prepend(C).prepend(F);
+ bt_assert(aspa_check(at_official, p, DOWN) = ASPA_VALID);
+
+ # Topology Contains Complex BGP Relationships
+ int H = 65548; int J = 65549; int K = 65550; int L = 65551;
+ int P = 65552; int Q = 65553; int R = 65554; int S = 65555;
+
+ p = +empty+.prepend(H).prepend(J);
+ bt_assert(aspa_check(at_official, p, UP) = ASPA_INVALID);
+
+ p = +empty+.prepend(H).prepend(J).prepend(K);
+ bt_assert(aspa_check(at_official, p, DOWN) = ASPA_INVALID);
+
+ p = +empty+.prepend(P).prepend(Q);
+ bt_assert(aspa_check(at_official, p, UP) = ASPA_INVALID);
+
+ p = +empty+.prepend(P).prepend(Q);
+ bt_assert(aspa_check(at_official, p, DOWN) = ASPA_VALID);
+
+ p = +empty+.prepend(P).prepend(Q).prepend(R);
+ bt_assert(aspa_check(at_official, p, DOWN) = ASPA_VALID);
}
bt_test_suite(t_aspa_check_official, "Testing ASPA (official tests)");
diff --git a/nest/rt-table.c b/nest/rt-table.c
index ed364d35..3816fba1 100644
--- a/nest/rt-table.c
+++ b/nest/rt-table.c
@@ -351,7 +351,7 @@ net_roa_check(rtable *tab, const net_addr *n, u32 asn)
* @tab: ASPA table
* @path: AS Path to check
*
- * Implements draft-ietf-sidrops-aspa-verification-16.
+ * Implements draft-ietf-sidrops-aspa-verification-24.
*/
enum aspa_result aspa_check(rtable *tab, const adata *path, bool force_upstream)
{
@@ -377,103 +377,117 @@ enum aspa_result aspa_check(rtable *tab, const adata *path, bool force_upstream)
uint ppos = 0;
uint nsz = 0;
while (as_path_walk(path, &ppos, &asns[nsz]))
- if ((nsz == 0) || (asns[nsz] != asns[nsz-1]))
+ if ((nsz == 0) || (asns[nsz] != asns[nsz - 1]))
nsz++;
/* Find the provider blocks for every AS on the path
* and check allowed directions */
- uint max_up = 0, min_up = 0, max_down = 0, min_down = 0;
+ uint max_up = nsz, min_up = nsz;
- for (uint ap=0; ap<nsz; ap++)
+ /* If we check only the upstream path, there is no down ramp.
+ * Therefore, max_down_ramp and min_down_ramp are set to 0. */
+ uint max_down = force_upstream ? 0 : nsz, min_down = force_upstream ? 0 : nsz;
+ bool max_down_udpated = force_upstream, min_down_updated = force_upstream;
+
+ for (uint ap = 0; ap < nsz; ap++)
{
- net_addr_union nau = { .aspa = NET_ADDR_ASPA(asns[ap]), };
+ net_addr_union nau = {
+ .aspa = NET_ADDR_ASPA(asns[ap]),
+ };
net *n = net_find(tab, &nau.n);
bool found = false, down = false, up = false;
- for (rte *e = (n ? n->routes: NULL); e; e = e->next)
+ /* This whole loop aim to:
+ * - set found to true if there is some valid ASPA records for the current ASN
+ * - set up to true if the previous ASN is listed in the ASPA records
+ * - set down to true if the next ASN is listed in the ASPA records
+ *
+ * In the RFC, the as PATH is reversed compared to the AS_PATH we handle,
+ * explaining why the up variable is linked to the previous AS in the path
+ * and vice versa */
+ for (rte *e = (n ? n->routes : NULL); e; e = e->next)
{
if (!rte_is_valid(e))
- continue;
+ continue;
eattr *ea = ea_find(e->attrs->eattrs, EA_ASPA_PROVIDERS);
if (!ea)
- continue;
+ continue;
/* Actually found some ASPA */
found = true;
- for (uint i=0; i * sizeof(u32) < ea->u.ptr->length; i++)
+ for (uint i = 0; i * sizeof(u32) < ea->u.ptr->length; i++)
{
- if ((ap > 0) && ((u32 *) ea->u.ptr->data)[i] == asns[ap-1])
- up = true;
- if ((ap + 1 < nsz) && ((u32 *) ea->u.ptr->data)[i] == asns[ap+1])
- down = true;
-
- if (down && up)
- /* Both peers found */
- goto end_of_aspa;
+ if ((ap > 0) && ((u32 *)ea->u.ptr->data)[i] == asns[ap - 1])
+ up = true;
+ if ((ap + 1 < nsz) && ((u32 *)ea->u.ptr->data)[i] == asns[ap + 1])
+ down = true;
+
+ if (down && up)
+ /* Both peers found */
+ goto end_of_aspa;
}
}
-end_of_aspa:;
-
- /* Fast path for the upstream check */
- if (force_upstream)
- {
- if (!found)
- /* Move min-upstream */
- min_up = ap;
- else if (ap && !up)
- /* Exists but doesn't allow this upstream */
- return ASPA_INVALID;
- }
-
- /* Fast path for no ASPA here */
- else if (!found)
- {
- /* Extend max-downstream (min-downstream is stopped by unknown) */
- max_down = ap+1;
-
- /* Move min-upstream (can't include unknown) */
- min_up = ap;
- }
+ end_of_aspa:;
- /* ASPA exists and downstream may be extended */
- else if (down)
+ if ((ap + 1 < nsz) && !down)
{
- /* Extending max-downstream always */
- max_down = ap+1;
+ /* Downstream ramp bound update
+ * Updated once since min_down and max_down should be computed
+ * with the maximum index J for which authorized(A(J), A(J-1))
+ * return "Not Provider+" and/or "No Attestation" corresponding
+ * at the first violation when scanning in reverse.
+ *
+ * To compute {min,max}_up we use: N - J + 1
+ * However, J is indexed in reverse order starting from 1,
+ * but we can find back using J = N - ap. Then, basic arithmetic gave us:
+ * {min,max}_up = N - (N - ap) + 1 = ap + 1
+ */
- /* Extending min-downstream unless unknown seen */
- if (min_down == ap)
- min_down = ap+1;
+ /* ASPA record exist => Not Provider+ */
+ if (found && !max_down_udpated)
+ { // => NP+
+ max_down = ap + 1;
+ max_down_udpated = true;
+ }
- /* Downstream only */
- if (!up)
- min_up = max_up = ap;
+ /* No ASPA record or Invalid => No Attestation / Not Provider+*/
+ if (!min_down_updated)
+ {
+ min_down = ap + 1;
+ min_down_updated = true;
+ }
}
- /* No extension for downstream, force upstream only from now */
- else
+ if ((ap > 0) && !up)
{
- force_upstream = 1;
+ /* Upstream ramp bound update
+ * Updated every time since max_up and max_down should be computed
+ * with the minimum index I for which authorized(A(I), A(I+1))
+ * return "Not Provider+" and/or "No Attestation" corresponding
+ * at the last violation when scanning in reverse.
+ */
- /* Not even upstream, move the ending here */
- if (!up)
- min_up = max_up = ap;
+ /* No ASPA record or Invalid => No Attestation / Not Provider+*/
+ if (found)
+ min_up = max_up = nsz - ap;
+ /* ASPA record exist => Not Provider+ */
+ else
+ min_up = nsz - ap;
}
}
- /* Is the path surely valid? */
- if (min_up <= min_down)
- return ASPA_VALID;
+ /* Is the path invalid? */
+ if ((max_up + max_down) < nsz)
+ return ASPA_INVALID;
- /* Is the path maybe valid? */
- if (max_up <= max_down)
+ /* Is the path unknown? */
+ if ((min_up + min_down) < nsz)
return ASPA_UNKNOWN;
- /* Now there is surely a valley there. */
- return ASPA_INVALID;
+ return ASPA_VALID;
}
/**
--
2.53.0
More information about the Bird-users
mailing list