pathvector-dev

Posted on Jul 26 • Originally published at blog.pathvector.dev

Origin validation is a separate decision from best path

#python #bgp #network #protocol

Originally published at https://blog.pathvector.dev/protocol-in-code-bgp-04/ — part of the free Protocol Lab series.

This post is part of Protocol in Code, a free series that reads network protocols as logic — inputs, state, and branches — rather than as configuration examples. The full source, walkthroughs, and site lessons live in the repo: pathvector-studio/protocol-in-code. If you're newer to this and want to build the protocols hands-on before dissecting them, start with the companion Protocol Lab series instead.

Today we're on the BGP track, session 04, reading a single small file: src/protocol_in_code/bgp/validation.py. It's about 40 lines. The idea inside it is one that trips up a lot of engineers who've been running BGP for years.

The question to keep in your head

BGP's best path selection already ran. It compared local preference, AS_PATH length, MED, and the rest of the tiebreak ladder, and it picked a winner. So here's the question this module wants you turning over:

Core question: How do we decide whether the origin AS is authorized — even after BGP has already selected this route as the best path?

The trap is the sentence "it was the best path, so it must be fine." Best and authorized are two different words, and in the code they are two different decisions made by two different pieces of data. Best path selection asks which of these routes do I prefer? Origin validation asks is the AS at the end of this path actually allowed to originate this prefix? A route can win selection and still be a hijack.

RPKI origin validation is the mechanism that answers the second question, and the file we're reading is a toy model of exactly that.

Two kinds of information

The first thing to read isn't a function — it's the two dataclasses, because the whole session is really about keeping them apart.

@dataclass(frozen=True)
class BGPRoute:
    prefix: str
    origin_as: int


@dataclass(frozen=True)
class VRP:
    prefix: str
    max_length: int
    origin_as: int

BGPRoute is the BGP-side information — what a router learned from a neighbor. A prefix, and the AS that claims to originate it. That origin_as is the claim we're going to check.

VRP is the other side: a Validated ROA Payload. This is the authorization side, derived from RPKI. It says "this prefix range may be originated by this AS, down to this maximum length." A VRP is not a route. Nobody is forwarding traffic based on a VRP. It's an assertion about who is allowed to originate, published by the address holder and cryptographically validated upstream — by the time it reaches this code, it's just data: a prefix, a max_length, and an authorized origin_as.

Notice the asymmetry. The route has no max_length; the VRP does. That field is the whole reason coverage isn't just "is one prefix inside the other."

Coverage: is this route even in scope?

Before we can say valid or invalid, we have to ask whether any VRP even talks about this route. That's vrp_covers_route:

def vrp_covers_route(route: BGPRoute, vrp: VRP) -> bool:
    route_net = _route_network(route)
    vrp_net = _vrp_network(vrp)
    return route_net.subnet_of(vrp_net) and route_net.prefixlen <= vrp.max_length

Two conditions, both required. First, the route's prefix must be a subnet of the VRP's prefix — 192.0.2.0/24 is covered by 192.0.2.0/22, but 198.51.100.0/24 is not covered by either. Standard containment.

Second — and this is the part that surprises people — the route's prefix length must be less than or equal to the VRP's max_length. A VRP for 192.0.2.0/22 with max_length = 22 authorizes only the /22 itself. If someone originates 192.0.2.0/24, that /24 is geographically inside the /22 but its prefixlen (24) exceeds max_length (22), so subnet_of is true but the length check is false, and this VRP does not cover it.

That's deliberate. max_length is how an address holder says "I authorize this block, but not arbitrarily deaggregated announcements of it." Without that field, an attacker could announce a more-specific of your authorized prefix and ride your ROA. With it, a more-specific that exceeds max_length simply isn't covered by that VRP — and, as we're about to see, "not covered" has consequences.

The decision: three answers, not two

Here's the core of the session, validate_origin, and it's worth reading as three sequential branches rather than one function:

def validate_origin(route: BGPRoute, vrps: list[VRP]) -> ValidationState:
    covering_vrps = [vrp for vrp in vrps if vrp_covers_route(route, vrp)]
    if not covering_vrps:
        return ValidationState.NOT_FOUND

    if any(vrp.origin_as == route.origin_as for vrp in covering_vrps):
        return ValidationState.VALID

    return ValidationState.INVALID

Read it as a funnel.

First branch — is anything covering this route at all? Filter the VRP set down to the ones that cover the route. If that list is empty, we return NOT_FOUND and stop. We never even look at the origin AS. There is no VRP that has anything to say about this prefix, so we can't judge it.

Second branch — does a covering VRP authorize this origin? Among the covering VRPs, if any one has an origin_as equal to the route's origin_as, the route is VALID. The address holder authorized this AS to originate this prefix, and that's exactly who originated it.

Third branch — covered but not authorized. We fall through to INVALID. This only happens when the funnel got past the first branch: at least one VRP does cover this prefix, but none of the covering VRPs name this route's origin AS. Someone is originating a prefix that RPKI says belongs to a different AS.

The critical distinction is between NOT_FOUND and INVALID, and the branch order is what encodes it:

Note: not_found is not a weaker invalid. not_found means no covering VRP existed — we have no authorization data about this prefix, so we're not claiming anything. invalid means a covering VRP did exist and the origin AS contradicted it — we have data, and the route lost. One is silence; the other is a conflict. Real routers treat them very differently: not_found routes are commonly still accepted (much of the internet has no ROA yet), while invalid routes are increasingly dropped.

Three states, encoded as an enum so the caller has to handle them by name rather than juggling booleans:

class ValidationState(str, Enum):
    VALID = "valid"
    INVALID = "invalid"
    NOT_FOUND = "not_found"

Same shape, different protocol

The move this session is training — stop trusting the winner of one decision to answer a second, independent question — is not unique to BGP. It's a recurring shape.

The design of this module deliberately teaches origin validation as a separate concept, after best-path selection, so you learn to split "best" from "authorized." In production implementations the two can be wired together — validation state can feed route policy, adjust local preference, or gate installation — and a later session in this track uses one such toy integration on purpose. But the reason to read them apart first is that they are apart: selection ranks, validation authorizes, and conflating them is how a preferred hijack gets installed.

If you've read the DNS track, this is the same shape as validating a signed answer versus simply receiving one: getting an A record back doesn't mean it was authenticated. Winning the race to answer is not the same as being authorized to answer.

Run it and watch the branches fire

The walkthrough is runnable. It constructs routes and VRPs that land in each of the three states, plus the max_length edge case, and prints why each one resolved the way it did:

PYTHONPATH=src python3 examples/bgp/session_04_walkthrough.py

Watch specifically for the max_length scenario — a route that's a clean subnet of a VRP's prefix but comes back NOT_FOUND because its prefixlen overshot max_length. If you can predict that result before you run it, you've read vrp_covers_route correctly.

Toy model boundary

This is a teaching model, and it's honest to be precise about what it leaves out — because those omissions are exactly where the real complexity lives.

No cryptography. A real VRP is the output of validating a ROA: an RPKI-signed object, verified up a chain of resource certificates to a trust anchor. Here, VRP is a plain dataclass you hand-construct. All the signature checking, certificate path validation, and trust-anchor management that produces a validated payload happens before this code would ever run.
No RTR transport. In production, routers don't parse RPKI themselves; a relying-party validator does, and ships VRPs to the router over the RTR protocol (RFC 8210) with sessions, serial numbers, and incremental updates. Our vrps is just a Python list passed in.
IPv4 only. _route_network and _vrp_network call ip_network and the model assumes IPv4Network. Real validation is address-family agnostic and ROAs cover IPv6 too.
Origin only — never the path. This is the big one. validate_origin checks the origin AS: the last AS in the AS_PATH, the one claiming to originate the prefix. It says nothing about whether the intermediate hops in the path are legitimate, whether the announcement respects business relationships, or whether the path was forged after a valid origin. That's the domain of BGPsec and ASPA, and it's entirely outside this file. A route can be RPKI-origin-VALID and still be a path manipulation.
No caching, no staleness, no overlapping-VRP policy nuance beyond the plain "any covering VRP matches" rule shown here.

None of these are bugs in the model. They're the seam between "understand the decision" and "operate the system," and this session is deliberately on the first side of that seam.

Self-check

Don't take my summary for it — go read validation.py and answer these from the code alone:

A route arrives whose prefix no VRP covers. What does validate_origin return, and — trace the branches — does it ever look at the origin AS?
A route is covered by a VRP, but that VRP names a different origin_as. Which state comes back, and why is that state stronger than the one in question 1?
Why does this function, even when it returns VALID, still not tell you the AS_PATH is trustworthy?

If you can answer all three by pointing at lines rather than recalling this post, you've got it: best path selection and origin validation are separate decisions, not_found is silence rather than a verdict, and origin validation checks the origin — not the path.

DEV Community