[PATCH] Nest: correct aspa_check() implementation
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...). 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-2...). Don't hesitate to discuss the patch if needed, -- Evann
Hello Evann, I would like to share that I tried your patch and it seems to be working very well. Just looking at the numbers from unpatched BIRD 3.2.0: bird> show route where invalid_aspa=1 count 1825 of 3100872 routes for 1033635 networks in table master4 897 of 717964 routes for 239333 networks in table master6 And the numbers from patched version 2.18: bird> show route all where invalid_aspa=1 count 116 of 3100875 routes for 1033636 networks in table master4 108 of 717949 routes for 239328 networks in table master6 It is obvious that there is a dramatic drop of invalid paths. In my setup there are now only 29 unique paths that are invalid, which seems reasonable. I checked each one manually using a web-based validator I botched together and they seem to all have problem with APSA data, so dropping them is a good thing. One example of broken path is this: https://oskar456.github.io/aspa.html#path=3333-12859-215551-30893-13214-3563... Thanks for the patch and I hope it will make it to a release soon :) -- Best regards, Ondřej Caletka On 08/02/2026 02:39, Evann DREUMONT via Bird-users wrote:
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...). 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-2...).
Don't hesitate to discuss the patch if needed,
-- Evann
Hello Ondřej, If you need some help to have a patched package for the next RIPE meeting, don’t hesitate to ping me :) I’m the gentoo maintainer, but I also played with deb and rpm packages for other projects, to it should be doable. On Fri 13 Mar 2026 11:58:43 GMT, Ondřej Caletka wrote:
Hello Evann,
I would like to share that I tried your patch and it seems to be working very well. Just looking at the numbers from unpatched BIRD 3.2.0:
bird> show route where invalid_aspa=1 count 1825 of 3100872 routes for 1033635 networks in table master4 897 of 717964 routes for 239333 networks in table master6
And the numbers from patched version 2.18:
bird> show route all where invalid_aspa=1 count 116 of 3100875 routes for 1033636 networks in table master4 108 of 717949 routes for 239328 networks in table master6
It is obvious that there is a dramatic drop of invalid paths. In my setup there are now only 29 unique paths that are invalid, which seems reasonable. I checked each one manually using a web-based validator I botched together and they seem to all have problem with APSA data, so dropping them is a good thing.
One example of broken path is this: https://oskar456.github.io/aspa.html#path=3333-12859-215551-30893-13214-3563...
Thanks for the patch and I hope it will make it to a release soon :)
-- Best regards,
Ondřej Caletka
On 08/02/2026 02:39, Evann DREUMONT via Bird-users wrote:
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...). 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-2...).
Don't hesitate to discuss the patch if needed,
-- Evann
Hello Evann! Thank you for the patch! I have checked it thoroughly and it looks right.
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.
[...]
Given this issue, I tried to implement a patch. [...]
I have split your patch, and accepted the part where the test cases are added. After some back and forth, I decided to fix the function in a different way, keeping the logic of apex indices. I'm not totally opposing rewriting the function completely, but we have some more plans with that function (e.g. giving the up-ramp and down-ramp path chunks back to the user), and the apex indices approach is more suitable for that. You may see my fix in the branch `355-aspa-minimal-fix`, where I also added some additional commits, most notably the commit documenting how the `aspa_check()` function is designed and why. Please note that the branch may get rebased before merging into master. Side note: I have had a long beef with the authors of the draft about the wording and overall structure, and I'm very happy that you happened to implement this by the draft in a way which is not totally confusing. I have pushed your rewrite to the branch `355-aspa-downstream-fix-evann-dreumont`, so that it doesn't get lost if we happen to change our minds later, and also to prove that the rewrites of the draft were for good.
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...). They all passed successfully.
You could have been much harsher on me for not implementing part of my own test cases back into BIRD, tbh.
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.
It was indeed incorrect, and again, it was me sending this (or similar) testcase to Sriram with an incorrect outcome, and after somebody pointed out that it's incorrect, I didn't follow up and fix that back in BIRD. Last but not least, sorry for me being silent. There has been an awful lot on my table recently, including fast-coding a CoAP endpoint for upcoming BIRD API, replicating and fixing some more crashes in BIRD 3, doing a lot of code reviews, and some crazy stuff better for a pub than a public mailing-list. With that, thank you again for your patch, checks, effort and everything. Have a great day and happy routing! -- Maria Matejka (she/her) | BIRD Team Leader | CZ.NIC, z.s.p.o.
participants (4)
-
Alarig Le Lay -
Evann DREUMONT -
Maria Matejka -
Ondřej Caletka