So here is the validaton logic for ASPA. Now this is currently not
hooked up to anything apart from a larger regress test.
What is missing is code to send the ASPA table to the RDE and the reload
logic for ASPA.
Most of the ASPA validation happens in rde_aspa.c.
aspa_cp_lookup() checks if a customer - provider relation exists
aspa_check_aspath() walks an AS_PATH and calls aspa_cp_lookup() for each
touple. If check_downramp is true then both the upramp (source-as up
towards the Internet) and downramp (from the Internet back to us) are
checked.
aspa_validation() uses aspa_check_aspath() to validate the path. I split
the code up between aspa_check_aspath() and aspa_validation() to make it
possible to unit test aspa_check_aspath().
The code does not implement all the special cases the draft talk about
mainly because these special cases are not required and need to be removed
from the draft.
Diff includes both bgpd and regress test.
--
:wq Claudio
Index: usr.sbin/bgpd/Makefile
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/Makefile,v
retrieving revision 1.37
diff -u -p -r1.37 Makefile
--- usr.sbin/bgpd/Makefile 16 Feb 2021 08:29:16 -0000 1.37
+++ usr.sbin/bgpd/Makefile 18 Nov 2022 10:40:24 -0000
@@ -4,7 +4,7 @@ PROG= bgpd
SRCS= bgpd.c session.c log.c logmsg.c parse.y config.c \
rde.c rde_rib.c rde_decide.c rde_prefix.c mrt.c kroute.c control.c \
pfkey.c rde_update.c rde_attr.c rde_community.c printconf.c \
- rde_filter.c rde_sets.c rde_trie.c pftable.c name2id.c \
+ rde_filter.c rde_sets.c rde_aspa.c rde_trie.c pftable.c name2id.c \
util.c carp.c timer.c rde_peer.c rtr.c rtr_proto.c
CFLAGS+= -Wall -I${.CURDIR}
CFLAGS+= -Wstrict-prototypes -Wmissing-prototypes
Index: usr.sbin/bgpd/bgpd.h
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/bgpd.h,v
retrieving revision 1.456
diff -u -p -r1.456 bgpd.h
--- usr.sbin/bgpd/bgpd.h 4 Jan 2023 14:33:30 -0000 1.456
+++ usr.sbin/bgpd/bgpd.h 4 Jan 2023 14:35:07 -0000
@@ -107,6 +107,11 @@
#define ROA_VALID 0x2
#define ROA_MASK 0x3
+#define ASPA_UNKNOWN 0x00 /* default */
+#define ASPA_INVALID 0x01
+#define ASPA_VALID 0x02
+#define ASPA_NEVER_KNOWN 0x80 /* unknown, check never needed
*/
+
/*
* Limit the number of messages queued in the session engine.
* The SE will send an IMSG_XOFF messages to the RDE if the high water mark
Index: usr.sbin/bgpd/rde.c
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/rde.c,v
retrieving revision 1.582
diff -u -p -r1.582 rde.c
--- usr.sbin/bgpd/rde.c 28 Dec 2022 21:30:16 -0000 1.582
+++ usr.sbin/bgpd/rde.c 3 Jan 2023 09:19:34 -0000
@@ -61,6 +61,8 @@ uint8_t rde_attr_missing(struct rde_as
int rde_get_mp_nexthop(u_char *, uint16_t, uint8_t,
struct filterstate *);
void rde_as4byte_fixup(struct rde_peer *, struct rde_aspath *);
+uint8_t rde_aspa_validation(struct rde_peer *, struct
rde_aspath *,
+ uint8_t);
void rde_reflector(struct rde_peer *, struct rde_aspath *);
void rde_dump_ctx_new(struct ctl_show_rib_request *, pid_t,
@@ -107,6 +109,7 @@ static struct imsgbuf *ibuf_rtr;
static struct imsgbuf *ibuf_main;
static struct bgpd_config *conf, *nconf;
static struct rde_prefixset rde_roa, roa_new;
+static struct rde_aspa *rde_aspa /* , *aspa_new */;
volatile sig_atomic_t rde_quit = 0;
struct filter_head *out_rules, *out_rules_tmp;
@@ -1456,6 +1459,10 @@ rde_update_dispatch(struct rde_peer *pee
NULL, 0);
goto done;
}
+#if NOTYET
+ state.aspath.aspa_state = rde_aspa_validation(peer,
+ &state.aspath, AID_INET);
+#endif
}
while (nlri_len > 0) {
if (peer_has_add_path(peer, AID_INET, CAPA_AP_RECV)) {
@@ -1528,6 +1535,10 @@ rde_update_dispatch(struct rde_peer *pee
mpp += pos;
mplen -= pos;
+#if NOTYET
+ state.aspath.aspa_state = rde_aspa_validation(peer,
+ &state.aspath, aid);
+#endif
while (mplen > 0) {
if (peer_has_add_path(peer, aid, CAPA_AP_RECV)) {
if (mplen <= sizeof(pathid)) {
@@ -2395,6 +2406,36 @@ rde_as4byte_fixup(struct rde_peer *peer,
aspath_merge(a, nasp);
}
+
+uint8_t
+rde_aspa_validation(struct rde_peer *peer, struct rde_aspath *asp, uint8_t aid)
+{
+ if (!peer->conf.ebgp) /* ASPA is only performed on ebgp sessions */
+ return ASPA_NEVER_KNOWN;
+ if (aid != AID_INET && aid != AID_INET6) /* skip uncovered aids */
+ return ASPA_NEVER_KNOWN;
+
+#ifdef MAYBE
+ /*
+ * By default enforce neighbor-as is set for all ebgp sessions.
+ * So if a admin disables this check should we really "reenable"
+ * it here in such a dubious way?
+ * This just fails the ASPA validation for these paths so maybe
+ * this can be helpful. But it is not transparent to the admin.
+ */
+
+ /* skip neighbor-as check for transparent RS sessions */
+ if (peer->conf.role != ROLE_RS_CLIENT) {
+ uint32_t fas;
+
+ fas = aspath_neighbor(asp->aspath);
+ if (peer->conf.remote_as != fas)
+ return ASPA_INVALID;
+ }
+#endif
+
+ return aspa_validation(rde_aspa, peer->conf.role, asp->aspath, aid);
+}
/*
* route reflector helper function
Index: usr.sbin/bgpd/rde.h
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/rde.h,v
retrieving revision 1.275
diff -u -p -r1.275 rde.h
--- usr.sbin/bgpd/rde.h 28 Dec 2022 21:30:16 -0000 1.275
+++ usr.sbin/bgpd/rde.h 3 Jan 2023 09:19:34 -0000
@@ -225,6 +225,7 @@ struct rde_aspath {
uint16_t pftableid; /* pf table id */
uint8_t origin;
uint8_t others_len;
+ uint8_t aspa_state;
};
enum nexthop_state {
@@ -471,7 +472,6 @@ aspath_origin(struct aspath *aspath)
return (aspath->source_as);
}
-
/* rde_community.c */
int community_match(struct rde_community *, struct community *,
struct rde_peer *);
@@ -727,5 +727,13 @@ int up_dump_withdraws(u_char *, int, s
int up_dump_mp_unreach(u_char *, int, struct rde_peer *, uint8_t);
int up_dump_attrnlri(u_char *, int, struct rde_peer *);
int up_dump_mp_reach(u_char *, int, struct rde_peer *, uint8_t);
+
+/* rde_aspa.c */
+struct rde_aspa *aspa_table_prep(uint32_t, size_t);
+void aspa_add_set(struct rde_aspa *, uint32_t, const uint32_t *,
+ uint32_t, const uint32_t *);
+void aspa_table_free(struct rde_aspa *);
+uint8_t aspa_validation(struct rde_aspa *, enum role, struct
aspath *,
+ uint8_t);
#endif /* __RDE_H__ */
Index: usr.sbin/bgpd/rde_aspa.c
===================================================================
RCS file: usr.sbin/bgpd/rde_aspa.c
diff -N usr.sbin/bgpd/rde_aspa.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ usr.sbin/bgpd/rde_aspa.c 22 Dec 2022 13:49:10 -0000
@@ -0,0 +1,442 @@
+/* $OpenBSD$ */
+
+/*
+ * Copyright (c) 2022 Claudio Jeker <[email protected]>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "bgpd.h"
+#include "rde.h"
+
+enum cp_res {
+ UNKNOWN = -1,
+ NOT_PROVIDER = 0,
+ PROVIDER = 1,
+};
+
+struct rde_aspa_set {
+ uint32_t as;
+ uint32_t num;
+ uint32_t *pas;
+ uint32_t *pas_aid;
+ int next;
+};
+
+/*
+ * Power of 2 hash table
+ * The nodes are stored in the sets array.
+ * Additonal data for the rde_aspa_set are stored in data.
+ * For lookups only table and mask need to be accessed.
+ */
+struct rde_aspa {
+ struct rde_aspa_set **table;
+ uint32_t mask;
+ uint32_t maxset;
+ struct rde_aspa_set *sets;
+ uint32_t *data;
+ size_t maxdata;
+ size_t curdata;
+ uint32_t curset;
+};
+
+struct aspa_state {
+ int nhops;
+ int nup_p;
+ int nup_u;
+ int nup_np;
+ int ndown_p;
+ int ndown_u;
+ int ndown_np;
+};
+
+/*
+ * Use the final step of MurmurHash3 as a 32bit -> 32bit hash function.
+ */
+static inline uint32_t
+hash(uint32_t h)
+{
+ h ^= h >> 16;
+ h *= 0x85ebca6b;
+ h ^= h >> 13;
+ h *= 0xc2b2ae35;
+ h ^= h >> 16;
+ return h;
+}
+
+/*
+ * Lookup an asnum in the aspa hash table.
+ */
+static struct rde_aspa_set *
+aspa_lookup(struct rde_aspa *ra, uint32_t asnum)
+{
+ struct rde_aspa_set *aspa;
+ uint32_t h;
+
+ h = hash(asnum) & ra->mask;
+ aspa = ra->table[h];
+ if (aspa == NULL)
+ return NULL;
+
+ while (aspa->as < asnum) {
+ if (!aspa->next)
+ break;
+ aspa++;
+ }
+
+ if (aspa->as == asnum)
+ return aspa;
+ return NULL;
+}
+
+/*
+ * Lookup is there is a customer - provider realtion between cas and pas.
+ * Returns UNKNOWN if cas is not in the ra table or the aid is out of range.
+ * Returns PROVIDER if pas is registered for cas for the specified aid.
+ * Retruns NOT_PROVIDER otherwise.
+ * This function is called very frequently and needs to be fast.
+ */
+static enum cp_res
+aspa_cp_lookup(struct rde_aspa *ra, uint32_t cas, uint32_t pas, uint8_t aid)
+{
+ struct rde_aspa_set *aspa;
+ uint32_t i;
+
+ switch (aid) {
+ case AID_INET:
+ aid = 0x1;
+ break;
+ case AID_INET6:
+ aid = 0x2;
+ break;
+ default:
+ return UNKNOWN;
+ }
+
+ aspa = aspa_lookup(ra, cas);
+ if (aspa == NULL)
+ return UNKNOWN;
+
+ if (aspa->num < 16) {
+ for (i = 0; i < aspa->num; i++) {
+ if (aspa->pas[i] == pas)
+ break;
+ if (aspa->pas[i] > pas)
+ return NOT_PROVIDER;
+ }
+ if (i == aspa->num)
+ return NOT_PROVIDER;
+ } else {
+ uint32_t lim, x;
+ for (i = 0, lim = aspa->num; lim != 0; lim /= 2) {
+ x = lim / 2;
+ i += x;
+ if (aspa->pas[i] == pas) {
+ break;
+ } else if (aspa->pas[i] < pas) {
+ /* move right */
+ i++;
+ lim--;
+ } else {
+ /* move left */
+ i -= x;
+ }
+ }
+ if (lim == 0)
+ return NOT_PROVIDER;
+ }
+
+ if (aspa->pas_aid == NULL)
+ return PROVIDER;
+ if (aspa->pas_aid[i / 16] & (aid << ((i % 16) * 2)))
+ return PROVIDER;
+ return NOT_PROVIDER;
+}
+
+/*
+ * Calculate the various indexes of an aspath.
+ * The up-ramp starts at the source-as which is the right-most / last element
+ * in the aspath. The down-ramp starts at index 1.
+ * nhops: number of unique hops in the path
+ * nup_p: smallest index after which all aspath hops are provider valid
+ * nup_u: The biggest index of an unknown aspath hop.
+ * nup_np: The biggest index of a not-provider aspath hop.
+ * ndown_p: biggest index before which all aspath hops are provider valid
+ * ndown_u: The smallest index of an unknown aspath hop.
+ * ndown_np: The smallest index of a not-provider aspath hop.
+ * Returns 0 on success and -1 if a AS_SET is encountered.
+ */
+static int
+aspa_check_aspath(struct rde_aspa *ra, struct aspath *a, int check_downramp,
+ uint8_t aid, struct aspa_state *s)
+{
+ uint8_t *seg;
+ uint32_t as, prevas = 0;
+ uint16_t len, seg_size;
+ uint8_t i, seg_type, seg_len;
+ enum cp_res r;
+
+ memset(s, 0, sizeof(*s));
+ /* the neighbor-as itself is by definition valid */
+ s->ndown_p = 1;
+
+ /*
+ * Walk aspath and validate if necessary both up- and down-ramp.
+ * If and AS_SET is found the result is immediatly ASPA_INVALID.
+ */
+ seg = aspath_dump(a);
+ len = aspath_length(a);
+ for (; len > 0; len -= seg_size, seg += seg_size) {
+ seg_type = seg[0];
+ seg_len = seg[1];
+ seg_size = 2 + sizeof(uint32_t) * seg_len;
+
+ if (seg_type == AS_SET)
+ return -1;
+
+ for (i = 0; i < seg_len; i++) {
+ as = aspath_extract(seg, i);
+
+ if (as == prevas)
+ continue; /* skip prepends */
+
+ s->nhops++;
+ if (prevas != 0) {
+ if (check_downramp) {
+ /*
+ * down-ramp check, remember the
+ * left-most unknown or not-provider
+ * node and the right-most provider node
+ * for which all nodes before are valid.
+ */
+ r = aspa_cp_lookup(ra, prevas, as, aid);
+ switch (r) {
+ case UNKNOWN:
+ if (s->ndown_u == 0)
+ s->ndown_u = s->nhops;
+ break;
+ case PROVIDER:
+ if (s->ndown_p + 1 == s->nhops)
+ s->ndown_p = s->nhops;
+ break;
+ case NOT_PROVIDER:
+ if (s->ndown_np == 0)
+ s->ndown_np = s->nhops;
+ break;
+ }
+ }
+ /*
+ * up-ramp check, remember the right-most
+ * unkown and not-provider node and the
+ * left-most provider node for which all nodes
+ * after are valid.
+ * We recorde the nhops value of prevas,
+ * that's why the use of nhops - 1.
+ */
+ r = aspa_cp_lookup(ra, as, prevas, aid);
+ switch (r) {
+ case UNKNOWN:
+ s->nup_p = 0;
+ s->nup_u = s->nhops - 1;
+ break;
+ case PROVIDER:
+ if (s->nup_p == 0)
+ s->nup_p = s->nhops - 1;
+ break;
+ case NOT_PROVIDER:
+ s->nup_p = 0;
+ s->nup_np = s->nhops - 1;
+ break;
+ }
+ }
+ prevas = as;
+ }
+ }
+
+ /* the source-as itself is by definition valid */
+ if (s->nup_p == 0)
+ s->nup_p = s->nhops;
+ return 0;
+}
+
+/*
+ * Validate an aspath against the aspa_set *ra.
+ * Returns ASPA_VALID if the aspath is valid, ASPA_UNKNOWN if the
+ * aspath contains hops with unknown relation and invalid for
+ * empty aspaths, aspath with AS_SET and aspaths that fail validation.
+ */
+uint8_t
+aspa_validation(struct rde_aspa *ra, enum role role, struct aspath *a,
+ uint8_t aid)
+{
+ struct aspa_state state;
+
+ /* no aspa table, evrything is unknown */
+ if (ra == NULL)
+ return ASPA_UNKNOWN;
+
+ /* empty ASPATHs are always invalid */
+ if (aspath_length(a) == 0)
+ return ASPA_INVALID;
+
+ /* if no role is set, the outcome is unknown */
+ if (role == ROLE_NONE)
+ return ASPA_UNKNOWN;
+
+ if (aspa_check_aspath(ra, a, role == ROLE_CUSTOMER, aid, &state) == -1)
+ return ASPA_INVALID;
+
+ if (role != ROLE_CUSTOMER) {
+ /*
+ * Just an up-ramp:
+ * if a check returned NOT_PROVIDER then the result is invalid.
+ * if a check returned UNKNOWN then the result is unknown.
+ * else path is valid.
+ */
+ if (state.nup_np != 0)
+ return ASPA_INVALID;
+ if (state.nup_u != 0)
+ return ASPA_UNKNOWN;
+ return ASPA_VALID;
+ } else {
+ /*
+ * Both up-ramp and down-ramp:
+ * if nhops <= 2 the result is valid.
+ * if there is less than one AS hop between up-ramp and
+ * down-ramp then the result is valid.
+ * if not-provider nodes for both ramps exist and they
+ * do not overlap the path is invalid.
+ * else the path is unknown.
+ */
+ if (state.nhops <= 2)
+ return ASPA_VALID;
+ if (state.nup_p - state.ndown_p <= 1)
+ return ASPA_VALID;
+ if (state.nup_np != 0 && state.ndown_np != 0 &&
+ state.nup_np - state.ndown_np >= 0)
+ return ASPA_INVALID;
+ return ASPA_UNKNOWN;
+ }
+}
+
+/*
+ * Preallocate all data structures needed for the aspa table.
+ * There are entries number of rde_aspa_sets with data_size bytes of
+ * extra data.
+ */
+struct rde_aspa *
+aspa_table_prep(uint32_t entries, size_t data_size)
+{
+ struct rde_aspa *ra;
+ uint32_t hsize = 1024;
+
+ if (entries == 0)
+ return NULL;
+
+ while (hsize < entries)
+ hsize *= 2;
+
+ if ((ra = calloc(1, sizeof(*ra))) == NULL)
+ fatal("aspa table prep");
+
+ if ((ra->table = calloc(hsize, sizeof(ra->table[0]))) == NULL)
+ fatal("aspa table prep");
+
+ if ((ra->sets = calloc(entries, sizeof(ra->sets[0]))) == NULL)
+ fatal("aspa table prep");
+
+ if ((ra->data = malloc(data_size)) == NULL)
+ fatal("aspa table prep");
+
+ ra->mask = hsize - 1;
+ ra->maxset = entries;
+ ra->maxdata = data_size / sizeof(ra->data[0]);
+
+ return ra;
+}
+
+/*
+ * Insert a aspa customer/provider set into the hash table.
+ * For hash conflict resulution insertion must happen in reverse order (biggest
+ * customer asnum first). On conflict obejct in the sets array are moved
+ * around so that conflicting elements are direct neighbors.
+ * The per AID information is (if required) stored as 2bits per provider.
+ */
+void
+aspa_add_set(struct rde_aspa *ra, uint32_t cas, const uint32_t *pas,
+ uint32_t pascnt, const uint32_t *pas_aid)
+{
+ struct rde_aspa_set *aspa;
+ uint32_t h, i;
+
+ if (ra->curset >= ra->maxset)
+ fatalx("aspa set overflow");
+
+ h = hash(cas) & ra->mask;
+ aspa = ra->table[h];
+ if (aspa == NULL) {
+ aspa = &ra->sets[ra->curset++];
+ } else {
+ if (aspa->as <= cas)
+ fatalx("%s: bad order of adds", __func__);
+
+ /* insert before aspa */
+ memmove(aspa + 1, aspa,
+ (ra->sets + ra->curset - aspa) * sizeof(*aspa));
+ ra->curset++;
+ memset(aspa, 0, sizeof(*aspa));
+ aspa->next = 1;
+
+ /* adjust hashtable after shift of elements */
+ for (i = 0; i <= ra->mask; i++) {
+ if (ra->table[i] > aspa)
+ ra->table[i]++;
+ }
+ }
+ aspa->as = cas;
+ ra->table[h] = aspa;
+
+ if (ra->maxdata - ra->curdata < pascnt)
+ fatalx("aspa set data overflow");
+
+ aspa->num = pascnt;
+ aspa->pas = ra->data + ra->curdata;
+ for (i = 0; i < pascnt; i++)
+ ra->data[ra->curdata++] = pas[i];
+
+ /* nobody in there right mind has per afi specific data */
+ if (pas_aid != NULL) {
+ /* 2 bits per entry rounded to next uint32_t */
+ if (ra->maxdata - ra->curdata < (pascnt * 2 + 31) / 32)
+ fatalx("aspa set data overflow");
+
+ aspa->pas_aid = ra->data + ra->curdata;
+ for (i = 0; i < (pascnt * 2 + 31) / 32; i++)
+ ra->data[ra->curdata++] = pas_aid[i];
+ }
+}
+
+void
+aspa_table_free(struct rde_aspa *ra)
+{
+ if (ra == NULL)
+ return;
+ free(ra->table);
+ free(ra->sets);
+ free(ra->data);
+ free(ra);
+}
Index: regress/usr.sbin/bgpd/unittests/Makefile
===================================================================
RCS file: /cvs/src/regress/usr.sbin/bgpd/unittests/Makefile,v
retrieving revision 1.9
diff -u -p -r1.9 Makefile
--- regress/usr.sbin/bgpd/unittests/Makefile 7 Sep 2021 11:10:28 -0000
1.9
+++ regress/usr.sbin/bgpd/unittests/Makefile 12 Dec 2022 10:46:29 -0000
@@ -6,6 +6,7 @@ PROGS += rde_sets_test
PROGS += rde_trie_test
PROGS += rde_community_test
PROGS += rde_decide_test
+PROGS += rde_aspa_test
.for p in ${PROGS}
REGRESS_TARGETS += run-regress-$p
Index: regress/usr.sbin/bgpd/unittests/rde_aspa_test.c
===================================================================
RCS file: regress/usr.sbin/bgpd/unittests/rde_aspa_test.c
diff -N regress/usr.sbin/bgpd/unittests/rde_aspa_test.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ regress/usr.sbin/bgpd/unittests/rde_aspa_test.c 27 Dec 2022 13:36:04
-0000
@@ -0,0 +1,692 @@
+/* $OpenBSD$ */
+
+/*
+ * Copyright (c) 2022 Claudio Jeker <[email protected]>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <assert.h>
+#include <err.h>
+#include <stdio.h>
+
+#include "rde_aspa.c"
+
+static struct aspath *build_aspath(const uint32_t *, uint32_t, int);
+static const char *print_aspath(const uint32_t *, uint32_t);
+
+static void reverse_state(struct aspa_state *, struct aspa_state *);
+static void print_state(struct aspa_state *, struct aspa_state *);
+
+struct aspa_test_set {
+ uint32_t customeras;
+ const uint32_t *providers;
+ uint32_t pascnt;
+ const uint32_t *afimasks;
+};
+
+struct cp_test {
+ uint32_t customeras;
+ uint32_t provideras;
+ uint8_t aid;
+ enum cp_res expected_result;
+};
+
+struct aspath_test {
+ const uint32_t *aspath;
+ uint32_t aspathcnt;
+ struct aspa_state state;
+};
+
+struct aspa_test {
+ const uint32_t *aspath;
+ uint32_t aspathcnt;
+ enum role role;
+ uint8_t aid;
+ uint8_t expected_result;
+};
+
+struct aspa_test_set testset[] = {
+ /* test vectors from github.com/benmaddison/aspa-fuzz */
+ { 1, (const uint32_t []){ 4, 5, 6 }, 3, NULL },
+ { 2, (const uint32_t []){ 10, 11 }, 2, NULL },
+ { 3, (const uint32_t []){ 1, 13, 14 }, 3, NULL },
+ { 4, (const uint32_t []){ 16, 24 }, 2, NULL },
+ { 5, (const uint32_t []){ 1, 17, 25 }, 3, NULL },
+ { 8, (const uint32_t []){ 0 }, 1, NULL },
+ { 9, (const uint32_t []){ 2 }, 1, NULL },
+ { 10, (const uint32_t []){ 0 }, 1, NULL },
+ { 11, (const uint32_t []){ 2 }, 1, NULL },
+ { 12, (const uint32_t []){ 3 }, 1, NULL },
+ { 13, (const uint32_t []){ 0 }, 1, NULL },
+ { 14, (const uint32_t []){ 3, 25 }, 2, NULL },
+ { 15, (const uint32_t []){ 4 }, 1, NULL },
+ { 16, (const uint32_t []){ 4 }, 1, NULL },
+ { 17, (const uint32_t []){ 5 }, 1, NULL },
+ { 18, (const uint32_t []){ 6 }, 1, NULL },
+ { 20, (const uint32_t []){ 19 }, 1, NULL },
+ { 21, (const uint32_t []){ 0 }, 1, NULL },
+ { 23, (const uint32_t []){ 22 }, 1, NULL },
+ { 24, (const uint32_t []){ 0 }, 1, NULL },
+ { 25, (const uint32_t []){ 0 }, 1, NULL },
+ { 26, (const uint32_t []){ 5 }, 1, NULL },
+ { 27, (const uint32_t []){ 14 }, 1, NULL },
+ /* tests to simulate slides-110-sidrops-sriram-aspa-alg-accuracy-01 */
+ { 101, (const uint32_t []){ 102 }, 1, NULL },
+ { 102, (const uint32_t []){ 103, 104, 105 }, 3, NULL },
+ { 103, (const uint32_t []){ 111, 112, 203 }, 3, NULL },
+ /* 104 no ASPA */
+ { 105, (const uint32_t []){ 0 }, 1, NULL },
+
+ /* 111 no ASPA */
+ { 112, (const uint32_t []){ 0 }, 1, NULL },
+ { 113, (const uint32_t []){ 104, 105, 204, 205 }, 4, NULL },
+
+ { 121, (const uint32_t []){ 131, 132, 133 }, 3, NULL },
+ { 123, (const uint32_t []){ 0 }, 1, NULL },
+ { 131, (const uint32_t []){ 121, 122, 123 }, 3, NULL },
+ { 133, (const uint32_t []){ 0 }, 1, NULL },
+
+
+ { 201, (const uint32_t []){ 202 }, 1, NULL },
+ { 202, (const uint32_t []){ 203, 204, 205 }, 3, NULL },
+ { 203, (const uint32_t []){ 103, 111, 112 }, 3, NULL },
+ /* 204 no ASPA */
+ { 205, (const uint32_t []){ 0 }, 1, NULL },
+
+ /* extra test for big table test */
+ { 65000, (const uint32_t []){
+ 3, 5, 10, 15, 20, 21, 22, 23, 24, 25,
+ 30, 35, 40, 45, 50, 51, 52, 53, 54, 55,
+ 60, 65, 70, 75, 80, 81, 82, 83, 87, 90 }, 30, NULL },
+ /* extra test for AFI check */
+ { 196618, (const uint32_t []){ 1, 2, 3, 4 }, 4,
+ (const uint32_t []){ 0x39 }},
+};
+
+struct cp_test cp_testset[] = {
+ { 1, 2, AID_VPN_IPv4, UNKNOWN },
+ { 1, 4, AID_VPN_IPv6, UNKNOWN },
+
+ { 6, 1, AID_INET, UNKNOWN },
+ { 42, 1, AID_INET, UNKNOWN },
+
+ { 1, 2, AID_INET, NOT_PROVIDER },
+ { 1, 3, AID_INET, NOT_PROVIDER },
+ { 1, 7, AID_INET, NOT_PROVIDER },
+ { 5, 2, AID_INET, NOT_PROVIDER },
+ { 5, 16, AID_INET, NOT_PROVIDER },
+ { 5, 18, AID_INET, NOT_PROVIDER },
+ { 5, 24, AID_INET, NOT_PROVIDER },
+ { 5, 26, AID_INET, NOT_PROVIDER },
+ { 8, 2, AID_INET, NOT_PROVIDER },
+ { 9, 5, AID_INET, NOT_PROVIDER },
+ { 27, 13, AID_INET, NOT_PROVIDER },
+ { 27, 15, AID_INET, NOT_PROVIDER },
+
+ { 1, 4, AID_INET, PROVIDER },
+ { 1, 5, AID_INET, PROVIDER },
+ { 1, 6, AID_INET, PROVIDER },
+ { 2, 10, AID_INET, PROVIDER },
+ { 2, 11, AID_INET, PROVIDER },
+ { 9, 2, AID_INET, PROVIDER },
+ { 27, 14, AID_INET, PROVIDER },
+
+ /* per AID tests */
+ { 196618, 1, AID_INET, PROVIDER },
+ { 196618, 1, AID_INET6, NOT_PROVIDER },
+ { 196618, 2, AID_INET, NOT_PROVIDER },
+ { 196618, 2, AID_INET6, PROVIDER },
+ { 196618, 3, AID_INET, PROVIDER },
+ { 196618, 3, AID_INET6, PROVIDER },
+ { 196618, 4, AID_INET, NOT_PROVIDER },
+ { 196618, 4, AID_INET6, NOT_PROVIDER },
+ { 196618, 5, AID_INET, NOT_PROVIDER },
+ { 196618, 5, AID_INET6, NOT_PROVIDER },
+
+ /* big provider set test */
+ { 65000, 1, AID_INET, NOT_PROVIDER },
+ { 65000, 2, AID_INET, NOT_PROVIDER },
+ { 65000, 3, AID_INET, PROVIDER },
+ { 65000, 4, AID_INET, NOT_PROVIDER },
+ { 65000, 5, AID_INET, PROVIDER },
+ { 65000, 15, AID_INET, PROVIDER },
+ { 65000, 19, AID_INET, NOT_PROVIDER },
+ { 65000, 20, AID_INET, PROVIDER },
+ { 65000, 21, AID_INET, PROVIDER },
+ { 65000, 22, AID_INET, PROVIDER },
+ { 65000, 23, AID_INET, PROVIDER },
+ { 65000, 24, AID_INET, PROVIDER },
+ { 65000, 25, AID_INET, PROVIDER },
+ { 65000, 26, AID_INET, NOT_PROVIDER },
+ { 65000, 85, AID_INET, NOT_PROVIDER },
+ { 65000, 86, AID_INET, NOT_PROVIDER },
+ { 65000, 87, AID_INET, PROVIDER },
+ { 65000, 88, AID_INET, NOT_PROVIDER },
+ { 65000, 89, AID_INET, NOT_PROVIDER },
+ { 65000, 90, AID_INET, PROVIDER },
+ { 65000, 91, AID_INET, NOT_PROVIDER },
+ { 65000, 92, AID_INET, NOT_PROVIDER },
+ { 65000, 6666, AID_INET, NOT_PROVIDER },
+};
+
+struct aspath_test aspath_testset[] = {
+ { (const uint32_t []) { 1 }, 1, { 1, 1, 0, 0, 1, 0, 0 } },
+ { (const uint32_t []) { 7 }, 1, { 1, 1, 0, 0, 1, 0, 0 } },
+ { (const uint32_t []) { 8 }, 1, { 1, 1, 0, 0, 1, 0, 0 } },
+
+ { (const uint32_t []) { 1, 1 }, 2, { 1, 1, 0, 0, 1, 0, 0 } },
+ { (const uint32_t []) { 7, 7 }, 2, { 1, 1, 0, 0, 1, 0, 0 } },
+ { (const uint32_t []) { 8, 8 }, 2, { 1, 1, 0, 0, 1, 0, 0 } },
+
+ { (const uint32_t []) { 1, 1, 1 }, 3, { 1, 1, 0, 0, 1, 0, 0 } },
+ { (const uint32_t []) { 7, 7, 7 }, 3, { 1, 1, 0, 0, 1, 0, 0 } },
+ { (const uint32_t []) { 8, 8, 8 }, 3, { 1, 1, 0, 0, 1, 0, 0 } },
+
+ { (const uint32_t []) { 1, 5 }, 2, { 2, 1, 0, 0, 2, 0, 0 } },
+ { (const uint32_t []) { 1, 1, 5, 5 }, 4, { 2, 1, 0, 0, 2, 0, 0 } },
+ { (const uint32_t []) { 1, 5, 17 }, 3, { 3, 1, 0, 0, 3, 0, 0 } },
+
+ { (const uint32_t []) { 1, 4 }, 2, { 2, 2, 0, 1, 2, 0, 0 } },
+ { (const uint32_t []) { 1, 6 }, 2, { 2, 2, 1, 0, 2, 0, 0 } },
+ { (const uint32_t []) { 1, 17 }, 2, { 2, 2, 0, 1, 1, 0, 2 } },
+
+ { (const uint32_t []) { 42, 43, 44 }, 3, { 3, 3, 2, 0, 1, 2, 0 } },
+
+ { (const uint32_t []) { 42, 1, 5, 17, 44 }, 5,
+ { 5, 5, 4, 1, 1, 2, 5 } },
+
+ /* 1 ?> 6 -? 11 -- 12 -- 13 ?- 19 <? 20 */
+ { (const uint32_t []) { 1, 6, 11, 12, 13, 19, 20 }, 7,
+ { 7, 6, 5, 4, 2, 3, 4 } },
+};
+
+/*
+ * For simplicity the relation between is described as 123 LR 124 where:
+ * R: ? if ASPA(123) is empty
+ * > if 124 is a provider of 123
+ * - otherwise (124 is not part of the provider list)
+ * L: ? if ASPA(124) is empty
+ * > if 123 is a provider of of 124
+ * - otherwise (123 is not part of the provider list)
+ *
+ * e.g. 1 -> 2 (2 is provider of 1 but 1 is not for 2)
+ * 1 ?> 2 (2 is provider of 1 but 2 has no ASPA set defined)
+ */
+struct aspa_test aspa_testset[] = {
+ /* empty ASPATH are invalid by default */
+ { (const uint32_t []) { }, 0, ROLE_CUSTOMER, AID_INET, ASPA_INVALID },
+ { (const uint32_t []) { }, 0, ROLE_PROVIDER, AID_INET, ASPA_INVALID },
+ { (const uint32_t []) { }, 0, ROLE_RS, AID_INET, ASPA_INVALID },
+ { (const uint32_t []) { }, 0, ROLE_RS_CLIENT, AID_INET, ASPA_INVALID },
+ { (const uint32_t []) { }, 0, ROLE_PEER, AID_INET, ASPA_INVALID },
+
+ { (const uint32_t []) { 2 }, 1, ROLE_RS_CLIENT, AID_INET, ASPA_VALID },
+ { (const uint32_t []) { 2 }, 1, ROLE_PEER, AID_INET, ASPA_VALID },
+
+ { (const uint32_t []) { 3 }, 1, ROLE_PROVIDER, AID_INET, ASPA_VALID },
+ { (const uint32_t []) { 4 }, 1, ROLE_CUSTOMER, AID_INET, ASPA_VALID },
+ { (const uint32_t []) { 5 }, 1, ROLE_CUSTOMER, AID_INET, ASPA_VALID },
+ { (const uint32_t []) { 6 }, 1, ROLE_CUSTOMER, AID_INET, ASPA_VALID },
+
+ { (const uint32_t []) { 7 }, 1, ROLE_PROVIDER, AID_INET, ASPA_VALID },
+ { (const uint32_t []) { 7 }, 1, ROLE_PEER, AID_INET, ASPA_VALID },
+ { (const uint32_t []) { 7 }, 1, ROLE_RS_CLIENT, AID_INET, ASPA_VALID },
+
+ { (const uint32_t []) { 2, 8 }, 2, ROLE_PEER, AID_INET, ASPA_INVALID },
+ { (const uint32_t []) { 2, 8 }, 2, ROLE_RS_CLIENT, AID_INET,
+ ASPA_INVALID },
+
+ { (const uint32_t []) { 2, 9 }, 2, ROLE_PEER, AID_INET, ASPA_VALID },
+ { (const uint32_t []) { 2, 9 }, 2, ROLE_RS_CLIENT, AID_INET,
+ ASPA_VALID },
+
+ { (const uint32_t []) { 2, 10 }, 2, ROLE_PEER, AID_INET, ASPA_INVALID },
+ { (const uint32_t []) { 2, 10 }, 2, ROLE_RS_CLIENT, AID_INET,
+ ASPA_INVALID },
+
+ { (const uint32_t []) { 2, 11 }, 2, ROLE_PEER, AID_INET, ASPA_VALID },
+ { (const uint32_t []) { 2, 11 }, 2, ROLE_RS_CLIENT, AID_INET,
+ ASPA_VALID },
+
+ { (const uint32_t []) { 3, 8 }, 2, ROLE_PROVIDER, AID_INET,
+ ASPA_INVALID },
+ { (const uint32_t []) { 3, 12 }, 2, ROLE_PROVIDER, AID_INET,
+ ASPA_VALID },
+ { (const uint32_t []) { 3, 13 }, 2, ROLE_PROVIDER, AID_INET,
+ ASPA_INVALID },
+ { (const uint32_t []) { 3, 14 }, 2, ROLE_PROVIDER, AID_INET,
+ ASPA_VALID },
+
+ { (const uint32_t []) { 4, 8 }, 2, ROLE_CUSTOMER, AID_INET,
+ ASPA_VALID },
+ { (const uint32_t []) { 4, 15 }, 2, ROLE_CUSTOMER, AID_INET,
+ ASPA_VALID },
+ { (const uint32_t []) { 4, 16 }, 2, ROLE_CUSTOMER, AID_INET,
+ ASPA_VALID },
+ { (const uint32_t []) { 4, 24 }, 2, ROLE_CUSTOMER, AID_INET,
+ ASPA_VALID },
+
+ { (const uint32_t []) { 5, 8 }, 2, ROLE_CUSTOMER, AID_INET,
+ ASPA_VALID },
+ { (const uint32_t []) { 5, 17 }, 2, ROLE_CUSTOMER, AID_INET,
+ ASPA_VALID },
+ { (const uint32_t []) { 5, 25 }, 2, ROLE_CUSTOMER, AID_INET,
+ ASPA_VALID },
+ { (const uint32_t []) { 5, 26 }, 2, ROLE_CUSTOMER, AID_INET,
+ ASPA_VALID },
+
+ { (const uint32_t []) { 6, 18 }, 2, ROLE_CUSTOMER, AID_INET,
+ ASPA_VALID },
+ { (const uint32_t []) { 6, 19 }, 2, ROLE_CUSTOMER, AID_INET,
+ ASPA_VALID },
+
+ { (const uint32_t []) { 7, 19 }, 2, ROLE_PROVIDER, AID_INET,
+ ASPA_UNKNOWN },
+ { (const uint32_t []) { 7, 19 }, 2, ROLE_PEER, AID_INET,
+ ASPA_UNKNOWN },
+ { (const uint32_t []) { 7, 19 }, 2, ROLE_RS_CLIENT, AID_INET,
+ ASPA_UNKNOWN },
+ { (const uint32_t []) { 7, 21 }, 2, ROLE_PROVIDER, AID_INET,
+ ASPA_INVALID },
+ { (const uint32_t []) { 7, 21 }, 2, ROLE_PEER, AID_INET,
+ ASPA_INVALID },
+ { (const uint32_t []) { 7, 21 }, 2, ROLE_RS_CLIENT, AID_INET,
+ ASPA_INVALID },
+
+ { (const uint32_t []) { 6, 19, 20 }, 3, ROLE_CUSTOMER, AID_INET,
+ ASPA_VALID },
+ { (const uint32_t []) { 20, 19, 6 }, 3, ROLE_CUSTOMER, AID_INET,
+ ASPA_VALID },
+
+ { (const uint32_t []) { 3, 14, 25 }, 3, ROLE_PROVIDER, AID_INET,
+ ASPA_INVALID },
+ { (const uint32_t []) { 3, 14, 19 }, 3, ROLE_PROVIDER, AID_INET,
+ ASPA_UNKNOWN },
+ { (const uint32_t []) { 3, 14, 19 }, 3, ROLE_PEER, AID_INET,
+ ASPA_UNKNOWN },
+ { (const uint32_t []) { 3, 14, 19 }, 3, ROLE_RS_CLIENT, AID_INET,
+ ASPA_UNKNOWN },
+ { (const uint32_t []) { 3, 14, 21 }, 3, ROLE_PROVIDER, AID_INET,
+ ASPA_INVALID },
+ { (const uint32_t []) { 3, 14, 21 }, 3, ROLE_PEER, AID_INET,
+ ASPA_INVALID },
+ { (const uint32_t []) { 3, 14, 21 }, 3, ROLE_RS_CLIENT, AID_INET,
+ ASPA_INVALID },
+ { (const uint32_t []) { 3, 14, 27 }, 3, ROLE_PROVIDER, AID_INET,
+ ASPA_VALID },
+ { (const uint32_t []) { 3, 14, 27 }, 3, ROLE_PEER, AID_INET,
+ ASPA_VALID },
+ { (const uint32_t []) { 3, 14, 27 }, 3, ROLE_RS_CLIENT, AID_INET,
+ ASPA_VALID },
+
+ { (const uint32_t []) { 7, 19, 22, 21 }, 4, ROLE_PROVIDER, AID_INET,
+ ASPA_INVALID },
+ { (const uint32_t []) { 7, 19, 22, 21 }, 4, ROLE_PEER, AID_INET,
+ ASPA_INVALID },
+ { (const uint32_t []) { 7, 19, 22, 21 }, 4, ROLE_RS_CLIENT, AID_INET,
+ ASPA_INVALID },
+
+ { (const uint32_t []) { 6, 19, 22, 23 }, 4, ROLE_CUSTOMER, AID_INET,
+ ASPA_UNKNOWN },
+
+ { (const uint32_t []) { 1, 5, 17, 13, 3, 14, 27 }, 7, ROLE_CUSTOMER,
+ AID_INET, ASPA_VALID },
+ { (const uint32_t []) { 27, 14, 3, 13, 17, 5, 1 }, 7, ROLE_CUSTOMER,
+ AID_INET, ASPA_VALID },
+
+ { (const uint32_t []) { 27, 14, 3, 6, 7, 19, 17, 5, 1 }, 9,
+ ROLE_CUSTOMER, AID_INET, ASPA_INVALID },
+ { (const uint32_t []) { 27, 14, 3, 7, 19, 6, 1, 5, 17 }, 9,
+ ROLE_CUSTOMER, AID_INET, ASPA_UNKNOWN },
+
+ /* check L < K (ramps overlap) */
+ { (const uint32_t []) { 201, 202, 203, 103, 102, 101 }, 6,
+ ROLE_CUSTOMER, AID_INET, ASPA_VALID },
+ { (const uint32_t []) { 101, 102, 103, 203, 202, 201 }, 6,
+ ROLE_CUSTOMER, AID_INET, ASPA_VALID },
+
+ /* check L == K (ramps touch) 203 ?> 111 <? 103 */
+ { (const uint32_t []) { 201, 202, 203, 111, 103, 102, 101 }, 7,
+ ROLE_CUSTOMER, AID_INET, ASPA_VALID },
+ { (const uint32_t []) { 101, 102, 103, 111, 203, 202, 201 }, 7,
+ ROLE_CUSTOMER, AID_INET, ASPA_VALID },
+ /* check L == K (ramps touch) 203 -> 111 <- 103 */
+ { (const uint32_t []) { 201, 202, 203, 112, 103, 102, 101 }, 7,
+ ROLE_CUSTOMER, AID_INET, ASPA_VALID },
+ { (const uint32_t []) { 101, 102, 103, 112, 203, 202, 201 }, 7,
+ ROLE_CUSTOMER, AID_INET, ASPA_VALID },
+
+ /* check L - K == 1 (204 ?? 104) */
+ { (const uint32_t []) { 201, 202, 204, 104, 102, 101 }, 6,
+ ROLE_CUSTOMER, AID_INET, ASPA_VALID },
+ /* check L - K == 1 (204 -? 105) */
+ { (const uint32_t []) { 201, 202, 204, 105, 102, 101 }, 6,
+ ROLE_CUSTOMER, AID_INET, ASPA_VALID },
+ /* check L - K == 1 (205 ?- 104) */
+ { (const uint32_t []) { 201, 202, 205, 104, 102, 101 }, 6,
+ ROLE_CUSTOMER, AID_INET, ASPA_VALID },
+ /* check L - K == 1 (205 -- 105) */
+ { (const uint32_t []) { 201, 202, 205, 105, 102, 101 }, 6,
+ ROLE_CUSTOMER, AID_INET, ASPA_VALID },
+
+ /* check L - K == 2 invalid cases (205 ?- 111 -? 105) */
+ { (const uint32_t []) { 201, 202, 205, 111, 105, 102, 101 }, 7,
+ ROLE_CUSTOMER, AID_INET, ASPA_INVALID },
+ /* check L - K == 2 invalid cases (205 -- 112 -- 105) */
+ { (const uint32_t []) { 201, 202, 205, 112, 105, 102, 101 }, 7,
+ ROLE_CUSTOMER, AID_INET, ASPA_INVALID },
+ /* check L - K == 2 invalid cases (205 <- 113 -> 105) */
+ { (const uint32_t []) { 201, 202, 205, 113, 105, 102, 101 }, 7,
+ ROLE_CUSTOMER, AID_INET, ASPA_INVALID },
+
+ /* check L - K == 2 unknown cases (205 ?- 111 ?? 104) */
+ { (const uint32_t []) { 201, 202, 205, 111, 104, 102, 101 }, 7,
+ ROLE_CUSTOMER, AID_INET, ASPA_UNKNOWN },
+ /* check L - K == 2 unknown cases (204 ?? 111 -? 105) */
+ { (const uint32_t []) { 201, 202, 204, 111, 105, 102, 101 }, 7,
+ ROLE_CUSTOMER, AID_INET, ASPA_UNKNOWN },
+ /* check L - K == 2 unknown cases (204 ?? 111 ?? 104) */
+ { (const uint32_t []) { 201, 202, 204, 111, 104, 102, 101 }, 7,
+ ROLE_CUSTOMER, AID_INET, ASPA_UNKNOWN },
+ /* check L - K == 2 unknown cases (205 -- 112 ?- 104) */
+ { (const uint32_t []) { 201, 202, 205, 112, 104, 102, 101 }, 7,
+ ROLE_CUSTOMER, AID_INET, ASPA_UNKNOWN },
+ /* check L - K == 2 unknown cases (204 -? 112 -- 105) */
+ { (const uint32_t []) { 201, 202, 204, 112, 105, 102, 101 }, 7,
+ ROLE_CUSTOMER, AID_INET, ASPA_UNKNOWN },
+ /* check L - K == 2 unknown cases (204 -? 112 ?- 104) */
+ { (const uint32_t []) { 201, 202, 204, 112, 104, 102, 101 }, 7,
+ ROLE_CUSTOMER, AID_INET, ASPA_UNKNOWN },
+ /* check L - K == 2 unknown cases (205 <- 113 ?> 104) */
+ { (const uint32_t []) { 201, 202, 205, 113, 104, 102, 101 }, 7,
+ ROLE_CUSTOMER, AID_INET, ASPA_UNKNOWN },
+ /* check L - K == 2 unknown cases (204 <? 113 -> 105) */
+ { (const uint32_t []) { 201, 202, 204, 113, 105, 102, 101 }, 7,
+ ROLE_CUSTOMER, AID_INET, ASPA_UNKNOWN },
+ /* check L - K == 2 unknown cases (204 <? 113 ?> 104) */
+ { (const uint32_t []) { 201, 202, 204, 113, 104, 102, 101 }, 7,
+ ROLE_CUSTOMER, AID_INET, ASPA_UNKNOWN },
+
+#if 0
+ /* check L - K == 3 with all nP cases */
+ { (const uint32_t []) { 201, 202, 204, X, Y, 104, 102, 101 }, 8,
+ ROLE_CUSTOMER, AID_INET, ASPA_UNKNOWN },
+#endif
+};
+
+static struct rde_aspa *
+load_test_set(struct aspa_test_set *testv, uint32_t numentries)
+{
+ struct rde_aspa *aspa;
+ size_t data_size = 0;
+ uint32_t i;
+
+ for (i = 0; i < numentries; i++) {
+ data_size += testv[i].pascnt * sizeof(uint32_t);
+ if (testv[i].afimasks)
+ data_size += (testv[i].pascnt * 2 + 31) / 8;
+ }
+
+ aspa = aspa_table_prep(numentries, data_size);
+
+ for (i = numentries; i > 0; i--) {
+ aspa_add_set(aspa, testv[i - 1].customeras,
+ testv[i - 1].providers, testv[i - 1].pascnt,
+ testv[i - 1].afimasks);
+ }
+
+ return aspa;
+}
+
+
+int
+main(int argc, char **argv)
+{
+ struct rde_aspa *aspa;
+ size_t num_cp = sizeof(cp_testset) / sizeof(cp_testset[0]);
+ size_t num_aspath = sizeof(aspath_testset) / sizeof(aspath_testset[0]);
+ size_t num_aspa = sizeof(aspa_testset) / sizeof(aspa_testset[0]);
+ size_t i;
+ int cp_failed = 0, aspath_failed = 0, aspa_failed = 0;
+
+ /* first test, loading empty aspa table works. */
+ aspa = load_test_set(NULL, 0);
+ assert(aspa == NULL);
+ aspa_table_free(aspa);
+
+ aspa = load_test_set(testset, sizeof(testset) / sizeof(testset[0]));
+ assert(aspa != NULL);
+
+ printf("testing aspa_cp_lookup: ");
+ for (i = 0; i < num_cp; i++) {
+ enum cp_res r;
+ r = aspa_cp_lookup(aspa, cp_testset[i].customeras,
+ cp_testset[i].provideras, cp_testset[i].aid);
+
+ if (cp_testset[i].expected_result != r) {
+ printf("failed: cp_testset[%zu]: "
+ "cas %u pas %u -> %d got %d\n", i,
+ cp_testset[i].customeras,
+ cp_testset[i].provideras,
+ cp_testset[i].expected_result,
+ r);
+ cp_failed = 1;
+ }
+ }
+ if (!cp_failed)
+ printf("OK\n");
+
+ printf("testing aspa_check_aspath: ");
+ for (i = 0; i < num_aspath; i++) {
+ struct aspa_state st, revst;
+ struct aspath *a;
+
+ a = build_aspath(aspath_testset[i].aspath,
+ aspath_testset[i].aspathcnt, 0);
+ if (aspa_check_aspath(aspa, a, 1, AID_INET, &st) == -1) {
+ printf("failed: aspath_testset[%zu]: "
+ "aspath %s got -1\n", i,
+ print_aspath(aspath_testset[i].aspath,
+ aspath_testset[i].aspathcnt));
+ aspath_failed = 1;
+ }
+
+ if (memcmp(&aspath_testset[i].state, &st, sizeof(st))) {
+ printf("failed: aspath_testset[%zu]: aspath %s "
+ "bad state", i,
+ print_aspath(aspath_testset[i].aspath,
+ aspath_testset[i].aspathcnt));
+ print_state(&aspath_testset[i].state, &st);
+ printf("\n");
+ aspath_failed = 1;
+ }
+ free(a);
+
+ a = build_aspath(aspath_testset[i].aspath,
+ aspath_testset[i].aspathcnt, 1);
+ if (aspa_check_aspath(aspa, a, 1, AID_INET, &st) == -1) {
+ printf("failed: reverse aspath_testset[%zu]: "
+ "aspath %s got -1\n", i,
+ print_aspath(aspath_testset[i].aspath,
+ aspath_testset[i].aspathcnt));
+ aspath_failed = 1;
+ }
+
+ reverse_state(&aspath_testset[i].state, &revst);
+ if (memcmp(&revst, &st, sizeof(st))) {
+ printf("failed: reverse aspath_testset[%zu]: aspath %s "
+ "bad state", i,
+ print_aspath(aspath_testset[i].aspath,
+ aspath_testset[i].aspathcnt));
+ print_state(&revst, &st);
+ printf("\n");
+ aspath_failed = 1;
+ }
+ free(a);
+ }
+ if (!aspath_failed)
+ printf("OK\n");
+
+ printf("testing aspa_validation: ");
+ for (i = 0; i < num_aspa; i++) {
+ struct aspath *a;
+ uint8_t rv;
+
+ a = build_aspath(aspa_testset[i].aspath,
+ aspa_testset[i].aspathcnt, 0);
+ rv = aspa_validation(aspa, aspa_testset[i].role, a,
+ aspa_testset[i].aid);
+
+ if (aspa_testset[i].expected_result != rv) {
+ printf("failed: aspa_testset[%zu]: aspath %s role %d "
+ "want %d got %d", i,
+ print_aspath(aspa_testset[i].aspath,
+ aspa_testset[i].aspathcnt),
+ aspa_testset[i].role,
+ aspa_testset[i].expected_result,
+ rv);
+ aspa_failed = 1;
+ }
+
+ free(a);
+ }
+ if (!aspa_failed)
+ printf("OK\n");
+
+ aspa_table_free(aspa);
+
+ return cp_failed | aspath_failed | aspa_failed;
+}
+
+__dead void
+fatalx(const char *emsg, ...)
+{
+ va_list ap;
+ va_start(ap, emsg);
+ verrx(2, emsg, ap);
+}
+
+__dead void
+fatal(const char *emsg, ...)
+{
+ va_list ap;
+ va_start(ap, emsg);
+ verr(2, emsg, ap);
+}
+
+uint32_t
+aspath_extract(const void *seg, int pos)
+{
+ const u_char *ptr = seg;
+ uint32_t as;
+
+ /* minimal pos check, return 0 since that is an invalid ASN */
+ if (pos < 0 || pos >= ptr[1])
+ return (0);
+ ptr += 2 + sizeof(uint32_t) * pos;
+ memcpy(&as, ptr, sizeof(uint32_t));
+ return (ntohl(as));
+}
+
+static struct aspath *
+build_aspath(const uint32_t *asns, uint32_t asncnt, int rev)
+{
+ struct aspath *aspath;
+ uint32_t i, idx, as;
+ uint16_t len;
+
+ /* don't mess around with multi segment ASPATHs */
+ if (asncnt >= 255)
+ errx(1, "asncnt too big");
+
+ if (asncnt == 0)
+ len = 0;
+ else
+ len = 2 + sizeof(uint32_t) * asncnt;
+ aspath = malloc(ASPATH_HEADER_SIZE + len);
+ if (aspath == NULL)
+ err(1, NULL);
+
+ aspath->len = len;
+ aspath->ascnt = asncnt; /* lie but nothing cares */
+ aspath->source_as = 0;
+ if (len != 0)
+ aspath->source_as = asns[0];
+ aspath->data[0] = AS_SEQUENCE;
+ aspath->data[1] = asncnt;
+ for (i = 0; i < asncnt; i++) {
+ if (rev)
+ idx = asncnt - 1 - i;
+ else
+ idx = i;
+ as = htonl(asns[idx]);
+ memcpy(aspath->data + 2 + sizeof(as) * i, &as,
+ sizeof(uint32_t));
+ }
+
+ return aspath;
+}
+
+static const char *
+print_aspath(const uint32_t *asns, uint32_t asncnt)
+{
+ static char buf[1024];
+ char b[16];
+ uint32_t i;
+
+ strlcpy(buf, "", sizeof(buf));
+ for (i = 0; i < asncnt; i++) {
+ snprintf(b, sizeof(b), "%d", asns[i]);
+ if (i > 0)
+ strlcat(buf, " ", sizeof(buf));
+ strlcat(buf, b, sizeof(buf));
+ }
+ return buf;
+}
+
+static void
+reverse_state(struct aspa_state *in, struct aspa_state *rev)
+{
+ memset(rev, 0, sizeof(*rev));
+ rev->nhops = in->nhops;
+ rev->nup_p = in->nhops + 1 - in->ndown_p;
+ if (in->ndown_u != 0)
+ rev->nup_u = in->nhops + 1 - in->ndown_u;
+ if (in->ndown_np != 0)
+ rev->nup_np = in->nhops + 1 - in->ndown_np;
+ rev->ndown_p = in->nhops + 1 - in->nup_p;
+ if (in->nup_u != 0)
+ rev->ndown_u = in->nhops + 1 - in->nup_u;
+ if (in->nup_np != 0)
+ rev->ndown_np = in->nhops + 1 - in->nup_np;
+}
+
+static void
+print_state(struct aspa_state *a, struct aspa_state *b)
+{
+ if (a->nhops != b->nhops)
+ printf(" nhops %d != %d", a->nhops, b->nhops);
+ if (a->nup_p != b->nup_p)
+ printf(" nup_p %d != %d", a->nup_p, b->nup_p);
+ if (a->nup_u != b->nup_u)
+ printf(" nup_u %d != %d", a->nup_u, b->nup_u);
+ if (a->nup_np != b->nup_np)
+ printf(" nup_np %d != %d", a->nup_np, b->nup_np);
+ if (a->ndown_p != b->ndown_p)
+ printf(" ndown_p %d != %d", a->ndown_p, b->ndown_p);
+ if (a->ndown_u != b->ndown_u)
+ printf(" ndown_u %d != %d", a->ndown_u, b->ndown_u);
+ if (a->ndown_np != b->ndown_np)
+ printf(" ndown_np %d != %d", a->ndown_np, b->ndown_np);
+}
