From 4b62fd1a4feb6fd740081eaf71e55b1137ffe60b Mon Sep 17 00:00:00 2001 From: claudio Date: Tue, 18 Sep 2018 15:14:07 +0000 Subject: [PATCH] Backend for roa-sets. This combines as_sets and prefix-set tries to do proper ROA checking. There is a new match function trie_roa_check which does a trie traversal and looks for candidates and matches. If prefix is not covered then ROA_UNKNOWN is returned, if prefix is covered by an entry it will return ROA_INVALID unless the source-as / maxlen combo is matching (ROA_VALID). OK and input sthen@ --- usr.sbin/bgpd/bgpd.h | 7 +- usr.sbin/bgpd/rde.h | 15 +- usr.sbin/bgpd/rde_trie.c | 305 ++++++++++++++++++++++++++++++--------- 3 files changed, 252 insertions(+), 75 deletions(-) diff --git a/usr.sbin/bgpd/bgpd.h b/usr.sbin/bgpd/bgpd.h index b2565d01a30..f60372f2aa3 100644 --- a/usr.sbin/bgpd/bgpd.h +++ b/usr.sbin/bgpd/bgpd.h @@ -1,4 +1,4 @@ -/* $OpenBSD: bgpd.h,v 1.340 2018/09/14 10:22:11 claudio Exp $ */ +/* $OpenBSD: bgpd.h,v 1.341 2018/09/18 15:14:07 claudio Exp $ */ /* * Copyright (c) 2003, 2004 Henning Brauer @@ -952,6 +952,11 @@ struct filter_set { enum action_types type; }; +struct roa_set { + u_int32_t as; /* must be first */ + u_int32_t maxlen; /* change type for better struct layout */ +}; + struct prefixset_item { struct filter_prefix p; SIMPLEQ_ENTRY(prefixset_item) entry; diff --git a/usr.sbin/bgpd/rde.h b/usr.sbin/bgpd/rde.h index cf58e25c55f..f344ba2f4fb 100644 --- a/usr.sbin/bgpd/rde.h +++ b/usr.sbin/bgpd/rde.h @@ -1,4 +1,4 @@ -/* $OpenBSD: rde.h,v 1.190 2018/09/09 12:33:51 claudio Exp $ */ +/* $OpenBSD: rde.h,v 1.191 2018/09/18 15:14:07 claudio Exp $ */ /* * Copyright (c) 2003, 2004 Claudio Jeker and @@ -36,6 +36,12 @@ enum peer_state { PEER_ERR /* error occurred going to PEER_DOWN state */ }; +enum roa_state { + ROA_UNKNOWN, + ROA_INVALID, + ROA_VALID +}; + /* * How do we identify peers between the session handler and the rde? * Currently I assume that we can do that with the neighbor_ip... @@ -332,7 +338,8 @@ struct rde_prefixset { char name[SET_NAME_LEN]; struct trie_head th; SIMPLEQ_ENTRY(rde_prefixset) entry; - int dirty; + int dirty; + int roa; }; SIMPLEQ_HEAD(rde_prefixset_head, rde_prefixset); @@ -578,8 +585,12 @@ int up_dump_mp_reach(u_char *, u_int16_t *, struct rde_peer *, /* rde_trie.c */ int trie_add(struct trie_head *, struct bgpd_addr *, u_int8_t, u_int8_t, u_int8_t); +int trie_roa_add(struct trie_head *, struct bgpd_addr *, u_int8_t, + struct as_set *); void trie_free(struct trie_head *); int trie_match(struct trie_head *, struct bgpd_addr *, u_int8_t, int); +int trie_roa_check(struct trie_head *, struct bgpd_addr *, u_int8_t, + u_int32_t); void trie_dump(struct trie_head *); int trie_equal(struct trie_head *, struct trie_head *); diff --git a/usr.sbin/bgpd/rde_trie.c b/usr.sbin/bgpd/rde_trie.c index 4ba9fb56f0b..9c600d0ef28 100644 --- a/usr.sbin/bgpd/rde_trie.c +++ b/usr.sbin/bgpd/rde_trie.c @@ -1,4 +1,4 @@ -/* $OpenBSD: rde_trie.c,v 1.5 2018/09/10 13:15:50 denis Exp $ */ +/* $OpenBSD: rde_trie.c,v 1.6 2018/09/18 15:14:07 claudio Exp $ */ /* * Copyright (c) 2018 Claudio Jeker @@ -57,22 +57,20 @@ */ struct tentry_v4 { struct tentry_v4 *trie[2]; + struct as_set *aset; /* for roa source-as set */ struct in_addr addr; struct in_addr plenmask; u_int8_t plen; u_int8_t node; - - /* roa source-as list pointer */ }; struct tentry_v6 { struct tentry_v6 *trie[2]; + struct as_set *aset; /* for roa source-as set */ struct in6_addr addr; struct in6_addr plenmask; u_int8_t plen; u_int8_t node; - - /* roa source-as list pointer */ }; /* @@ -143,37 +141,14 @@ inet6setbit(struct in6_addr *addr, u_int8_t bit) addr->s6_addr[bit / 8] |= (0x80 >> (bit % 8)); } -static int -trie_add_v4(struct trie_head *th, struct in_addr *prefix, u_int8_t plen, - u_int8_t min, u_int8_t max) +static struct tentry_v4 * +trie_add_v4(struct trie_head *th, struct in_addr *prefix, u_int8_t plen) { struct tentry_v4 *n, *new, *b, **prev; - struct in_addr p, plenmask; - u_int8_t i; - - /* - * check for default route, this is special cased since prefixlen 0 - * can't be checked in the prefixlen mask plenmask. Also there is only - * one default route so using a flag for this works. - */ - if (min == 0) { - th->match_default_v4 = 1; - if (max == 0) /* just the default route */ - return 0; - min = 1; - } + struct in_addr p; inet4applymask(&p, prefix, plen); - /* - * The prefixlen mask goes from 1 to 32 but the bitmask - * starts at 0 and so all bits are set with an offset of 1. - * The default /0 route is handled specially above. - */ - memset(&plenmask, 0, sizeof(plenmask)); - for (i = min; i <= max; i++) - inet4setbit(&plenmask, i - 1); - /* walk tree finding spot to insert */ prev = &th->root_v4; n = *prev; @@ -189,7 +164,7 @@ trie_add_v4(struct trie_head *th, struct in_addr *prefix, u_int8_t plen, * np and n, then insert n and new node there */ if ((b = calloc(1, sizeof(*b))) == NULL) - return -1; + return NULL; b->plen = inet4findmsb(&n->addr, &mp); inet4applymask(&b->addr, &n->addr, b->plen); @@ -213,8 +188,7 @@ trie_add_v4(struct trie_head *th, struct in_addr *prefix, u_int8_t plen, if (n->plen == plen) { /* matching node, adjust */ n->node = 1; - n->plenmask.s_addr |= plenmask.s_addr; - return 0; + return n; } /* no need to check for n->plen == 32 because of above if */ @@ -227,10 +201,9 @@ trie_add_v4(struct trie_head *th, struct in_addr *prefix, u_int8_t plen, /* create new node */ if ((new = calloc(1, sizeof(*new))) == NULL) - return -1; + return NULL; new->addr = p; new->plen = plen; - new->plenmask = plenmask; new->node = 1; /* link node */ @@ -241,40 +214,17 @@ trie_add_v4(struct trie_head *th, struct in_addr *prefix, u_int8_t plen, else new->trie[0] = n; } - return 0; + return new; } -static int -trie_add_v6(struct trie_head *th, struct in6_addr *prefix, u_int8_t plen, - u_int8_t min, u_int8_t max) +static struct tentry_v6 * +trie_add_v6(struct trie_head *th, struct in6_addr *prefix, u_int8_t plen) { struct tentry_v6 *n, *new, *b, **prev; - struct in6_addr p, plenmask; - u_int8_t i; - - /* - * check for default route, this is special cased since prefixlen 0 - * can't be checked in the prefixlen mask plenmask. Also there is only - * one default route so using a flag for this works. - */ - if (min == 0) { - th->match_default_v6 = 1; - if (max == 0) /* just the default route */ - return 0; - min = 1; - } + struct in6_addr p; inet6applymask(&p, prefix, plen); - /* - * The prefixlen mask goes from 1 to 128 but the bitmask - * starts at 0 and so all bits are set with an offset of 1. - * The default /0 route is handled specially above. - */ - memset(&plenmask, 0, sizeof(plenmask)); - for (i = min; i <= max; i++) - inet6setbit(&plenmask, i - 1); - /* walk tree finding spot to insert */ prev = &th->root_v6; n = *prev; @@ -290,7 +240,7 @@ trie_add_v6(struct trie_head *th, struct in6_addr *prefix, u_int8_t plen, * np and n, then insert n and new node there */ if ((b = calloc(1, sizeof(*b))) == NULL) - return -1; + return NULL; b->plen = inet6findmsb(&n->addr, &mp); inet6applymask(&b->addr, &n->addr, b->plen); @@ -314,9 +264,7 @@ trie_add_v6(struct trie_head *th, struct in6_addr *prefix, u_int8_t plen, if (n->plen == plen) { /* matching node, adjust */ n->node = 1; - for (i = 0; i < sizeof(plenmask); i++) - n->plenmask.s6_addr[i] |= plenmask.s6_addr[i]; - return 0; + return n; } /* no need to check for n->plen == 128 because of above if */ @@ -329,10 +277,9 @@ trie_add_v6(struct trie_head *th, struct in6_addr *prefix, u_int8_t plen, /* create new node */ if ((new = calloc(1, sizeof(*new))) == NULL) - return -1; + return NULL; new->addr = p; new->plen = plen; - new->plenmask = plenmask; new->node = 1; /* link node */ @@ -343,30 +290,125 @@ trie_add_v6(struct trie_head *th, struct in6_addr *prefix, u_int8_t plen, else new->trie[0] = n; } - return 0; + return new; } +/* + * Insert prefix/plen into the trie with a prefixlen mask covering min - max. + * If plen == min == max then only the prefix/plen will match and no longer + * match is possible. Else all prefixes under prefix/plen with a prefixlen + * between min and max will match. + */ int trie_add(struct trie_head *th, struct bgpd_addr *prefix, u_int8_t plen, u_int8_t min, u_int8_t max) { + struct tentry_v4 *n4; + struct tentry_v6 *n6; + u_int8_t i; + /* precondition plen <= min <= max */ if (plen > min || min > max) return -1; + if (prefix->aid != AID_INET && prefix->aid != AID_INET6) + return -1; + + /* + * Check for default route, this is special cased since prefixlen 0 + * can't be checked in the prefixlen mask plenmask. Also there is + * only one default route so using a flag for this works. + */ + if (min == 0) { + if (prefix->aid == AID_INET) + th->match_default_v4 = 1; + else + th->match_default_v6 = 1; + + if (max == 0) /* just the default route */ + return 0; + min = 1; + } switch (prefix->aid) { case AID_INET: if (max > 32) return -1; - return trie_add_v4(th, &prefix->v4, plen, min, max); + + n4 = trie_add_v4(th, &prefix->v4, plen); + if (n4 == NULL) + return -1; + /* + * The prefixlen min - max goes from 1 to 32 but the bitmask + * starts at 0 and so all bits are set with an offset of -1. + * The default /0 route is handled specially above. + */ + for (i = min; i <= max; i++) + inet4setbit(&n4->plenmask, i - 1); + break; case AID_INET6: if (max > 128) return -1; - return trie_add_v6(th, &prefix->v6, plen, min, max); + + n6 = trie_add_v6(th, &prefix->v6, plen); + if (n6 == NULL) + return -1; + + /* See above for the - 1 reason. */ + for (i = min; i <= max; i++) + inet6setbit(&n6->plenmask, i - 1); + break; + } + return 0; +} + +/* + * Insert a ROA entry for prefix/plen. The prefix will insert an as_set with + * source_as and the maxlen as data. This makes it possible to validate if a + * prefix is matching this ROA record. It is possible to insert prefixes with + * source_as = 0. These entries will never return ROA_VALID on check and can + * be used to cover a large prefix as ROA_INVALID unless a more specific route + * is a match. + */ +int +trie_roa_add(struct trie_head *th, struct bgpd_addr *prefix, u_int8_t plen, + struct as_set *aset) +{ + struct tentry_v4 *n4; + struct tentry_v6 *n6; + struct as_set **ap; + + /* ignore possible default route since it does not make sense */ + + switch (prefix->aid) { + case AID_INET: + if (plen > 32) + return -1; + + n4 = trie_add_v4(th, &prefix->v4, plen); + if (n4 == NULL) + return -1; + ap = &n4->aset; + break; + case AID_INET6: + if (plen > 128) + return -1; + + n6 = trie_add_v6(th, &prefix->v6, plen); + if (n6 == NULL) + return -1; + ap = &n6->aset; + break; default: /* anything else fails */ return -1; } + + /* aset already set, error out */ + if (*ap != NULL) + return -1; + *ap = aset; + + return 0; } static void @@ -376,6 +418,7 @@ trie_free_v4(struct tentry_v4 *n) return; trie_free_v4(n->trie[0]); trie_free_v4(n->trie[1]); + as_set_free(n->aset); free(n); } @@ -386,6 +429,7 @@ trie_free_v6(struct tentry_v6 *n) return; trie_free_v6(n->trie[0]); trie_free_v6(n->trie[1]); + as_set_free(n->aset); free(n); } @@ -493,6 +537,123 @@ trie_match(struct trie_head *th, struct bgpd_addr *prefix, u_int8_t plen, } } +static int +trie_roa_check_v4(struct trie_head *th, struct in_addr *prefix, u_int8_t plen, + u_int32_t as) +{ + struct tentry_v4 *n; + struct roa_set *rs; + int validity = ROA_UNKNOWN; + + /* ignore possible default route since it does not make sense */ + + n = th->root_v4; + while (n) { + struct in_addr mp; + + if (n->plen > plen) + break; /* too specific, no match possible */ + + inet4applymask(&mp, prefix, n->plen); + if (n->addr.s_addr != mp.s_addr) + break; /* off path, no other match possible */ + + if (n->node) { + /* + * The prefix is covered by this roa node + * therefor invalid unless roa_set matches. + */ + validity = ROA_INVALID; + + /* Treat AS 0 as NONE which can never be matched */ + if (as != 0) { + rs = as_set_match(n->aset, as); + if (rs && plen <= rs->maxlen) + return ROA_VALID; + } + } + + if (n->plen == 32) + break; /* can't go deeper */ + if (inet4isset(prefix, n->plen)) + n = n->trie[1]; + else + n = n->trie[0]; + } + + return validity; +} + +static int +trie_roa_check_v6(struct trie_head *th, struct in6_addr *prefix, u_int8_t plen, + u_int32_t as) +{ + struct tentry_v6 *n; + struct roa_set *rs; + int validity = ROA_UNKNOWN; + + /* ignore possible default route since it does not make sense */ + + n = th->root_v6; + while (n) { + struct in6_addr mp; + + if (n->plen > plen) + break; /* too specific, no match possible */ + + inet6applymask(&mp, prefix, n->plen); + if (memcmp(&n->addr, &mp, sizeof(mp)) != 0) + break; /* off path, no other match possible */ + + if (n->node) { + /* + * This prefix is covered by this roa node. + * Therefor invalid unless proven otherwise. + */ + validity = ROA_INVALID; + + /* Treat AS 0 as NONE which can never be matched */ + if (as != 0) { + if ((rs = as_set_match(n->aset, as)) != NULL) + if (plen == n->plen || plen <= rs->maxlen) + return ROA_VALID; + } + } + + if (n->plen == 128) + break; /* can't go deeper */ + if (inet6isset(prefix, n->plen)) + n = n->trie[1]; + else + n = n->trie[0]; + } + + return validity; +} + +/* + * Do a ROA (Route Origin Validation) check. Look for elements in the trie + * which cover prefix "prefix/plen" and match the source-as as. + * AS 0 is treated here like AS NONE and should be used when the source-as + * is unknown (e.g. AS_SET). In other words the check will then only return + * ROA_UNKNOWN or ROA_INVALID depending if the prefix is covered by the ROA. + */ +int +trie_roa_check(struct trie_head *th, struct bgpd_addr *prefix, u_int8_t plen, + u_int32_t as) +{ + /* valid, invalid, unknown */ + switch (prefix->aid) { + case AID_INET: + return trie_roa_check_v4(th, &prefix->v4, plen, as); + case AID_INET6: + return trie_roa_check_v6(th, &prefix->v6, plen, as); + default: + /* anything else is unknown */ + return ROA_UNKNOWN; + } +} + static int trie_equal_v4(struct tentry_v4 *a, struct tentry_v4 *b) { -- 2.20.1