1 From: Josh Karlin <karlinjf@cs.unm.edu>
2 Date: Mon, 18 Aug 2008 13:17:21 +0000 (+0100)
3 Subject: [bgp] Add support for Pretty-Good BGP
4 X-Git-Url: http://git.ozo.com/?p=quagga-pgbg.git;a=commitdiff_plain;h=c2ee55705cad607f4b86ff143f7af92d538dc946
6 [bgp] Add support for Pretty-Good BGP
8 2008-7-7 Josh Karlin <karlinjf@cs.unm.edu>
10 * bgpd/bgp_pgbgp.c: Added file
11 * bgpd/bgp_pgbgp.h: Added file
12 * bgpd/Makefile.am: Added bgp_pgbgp.h and bgp_pgbgp.c
13 * bgpd/bgp_aspath.h: Externed the hash of as paths (ashash)
14 * bgpd/bgp_route.c: . Added PGBGP depref check to decision process.
15 . Informs PGBGP of new updates and selected routes
16 . Added anomaly status for show ip bgp
17 . Added PGBGP commands
18 * bgpd/bgp_route.h: Added suspicious route flags
19 * bgpd/bgp_table.h: Added PGBGP history pointer to struct bgp_node
20 * bgpd/bgpd.h: Defined BGP_CONFIG_PGBGP
21 * lib/hash.c: Added "hash_iterate_until" to be able to break out
22 * lib/hash.h: Definition for "hash_iterate_until"
23 * lib/memtypes.c: Added PGBGP memory types
26 --- a/bgpd/Makefile.am
27 +++ b/bgpd/Makefile.am
28 @@ -15,14 +15,14 @@ libbgp_a_SOURCES = \
29 bgp_debug.c bgp_route.c bgp_zebra.c bgp_open.c bgp_routemap.c \
30 bgp_packet.c bgp_network.c bgp_filter.c bgp_regex.c bgp_clist.c \
31 bgp_dump.c bgp_snmp.c bgp_ecommunity.c bgp_mplsvpn.c bgp_nexthop.c \
32 - bgp_damp.c bgp_table.c bgp_advertise.c bgp_vty.c bgp_mpath.c
33 + bgp_damp.c bgp_table.c bgp_advertise.c bgp_vty.c bgp_mpath.c bgp_pgbgp.c
36 bgp_aspath.h bgp_attr.h bgp_community.h bgp_debug.h bgp_fsm.h \
37 bgp_network.h bgp_open.h bgp_packet.h bgp_regex.h bgp_route.h \
38 bgpd.h bgp_filter.h bgp_clist.h bgp_dump.h bgp_zebra.h \
39 bgp_ecommunity.h bgp_mplsvpn.h bgp_nexthop.h bgp_damp.h bgp_table.h \
40 - bgp_advertise.h bgp_snmp.h bgp_vty.h bgp_mpath.h
41 + bgp_advertise.h bgp_snmp.h bgp_vty.h bgp_mpath.h bgp_pgbgp.h
43 bgpd_SOURCES = bgp_main.c
44 bgpd_LDADD = libbgp.a ../lib/libzebra.la @LIBCAP@ @LIBM@
46 +++ b/bgpd/bgp_pgbgp.c
50 + Copyright (C) 2008 University of New Mexico (Josh Karlin)
52 +This file is part of GNU Zebra.
54 +GNU Zebra is free software; you can redistribute it and/or modify it
55 +under the terms of the GNU General Public License as published by the
56 +Free Software Foundation; either version 2, or (at your option) any
59 +GNU Zebra is distributed in the hope that it will be useful, but
60 +WITHOUT ANY WARRANTY; without even the implied warranty of
61 +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
62 +General Public License for more details.
64 +You should have received a copy of the GNU General Public License
65 +along with GNU Zebra; see the file COPYING. If not, write to the Free
66 +Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
71 + Quagga based Pretty Good BGP:
75 + Pretty Good BGP (PGBGP) is a soft security enhancement to BGP.
76 + It uses independently collected (therefore completely distributed)
77 + historical routing information to determine network topology and
78 + prefix ownership. Abberations to the historical database are considered
79 + anomalous and avoided when possible.
81 + What PGBGP can protect against: prefix hijacks, sub-prefix hijacks, and
84 + Further reading is available at http://cs.unm.edu/~karlinjf/pgbgp/
86 + Route updates are forwarded to PGBGP, which determines if the route
87 + is anomalous. Anomalous routes are flagged as suspicious and
88 + avoided where feasible for 24 hours. If the anomalous
89 + characteristic is still in the RIB after 24 hours, consider it valid
90 + and enter it into the normal database.
92 + Cases for anomalous routes
93 + --------------------------
94 + case 1) New origin AS - prefix pair (one not recently seen in the RIB):
95 + response) label the route with BGP_INFO_SUSPICIOUS_O and avoid for 24 hours if possible
97 + case 2) New edge in path (one not recently seen in the RIB):
98 + response) label the route with BGP_INFO_SUSPICIOUS_E and avoid for 24 hours
101 + case 3) New prefix that is a sub-prefix of a prefix in recent history
102 + and that path differs from the current less-specific's path
103 + response) label the sub-prefix routes with BGP_INFO_IGNORED_P and
104 + prevent it from entering FIB for 24 hours
105 + response) label the super-net routes from the same next-hop as BGP_INFO_SUSPICIOUS_P
106 + and try to avoid it for 24 hours if possible
107 + response) while no super-net route is selected, remove the BGP_INFO_IGNORED_P flags
110 + Normal Database (history)
111 + -------------------------
112 + Recently Seen) A route characteristic (edge, prefix/origin pair, prefix)
113 + that has resided within the RIB within the last X hours
114 + where X is user defined for each characteristic.
115 + Storage) Prefix and Origin history are stored in bgp_node structs with the
117 + Edge information is stored in a separate hash table, where the edge
118 + is the key to the hash.
119 + Updates) The history's primary function is the keep track of when each route
120 + characteristic was last seen. For each route announcement, update
121 + the history's 'last seen' time. Periodically run the garbage collector
122 + which updates 'last seen' times for objects currently in the RIB.
126 + Periodically the garbage collector (gc) is called to remove stale history
127 + information and update the lastSeen time of objects that reside in the RIB
128 + at the time of collection. This is relatively expensive as it walks
129 + the RIB as well as the list of AS paths.
131 + What is removed) Objects that have not been seen in the RIB within a user-defined
133 + Suspicious objcets that are 24 hours old that have not been in the RIB
134 + since the last collection.
136 + Reuse Priority Queue
137 + --------------------
138 + After 24 hours, routes that are flagged as suspicious have the flags removed.
139 + This is not run on a timer. Instead, for each update that PGBGP is informed of,
140 + it checks the reuse queue to determine if any routes need to be updated.
146 + Things that must be ensured:
147 + . GC updates lastSeen so it must be called at least twice as often as the lowest BUFFER_TIME
148 + . GC should be called at least twice per day
149 + . Delay times must be shorter than history window lengths
154 + Changes made to original PGBGP thinking
155 + . Don't check for things in the RIB all of the time, periodically
156 + update the lastSeen values and just use lastSeen
160 + Changes made to original protocol
161 + . sub-prefixes are only ignored while the super-net has a selected
162 + route and it's non-anomalous (not to a neighbor that announced
165 + . At point of reuse, don't delete the item if it's not in the RIB.
166 + delete it if it hasn't been in the RIB since the last storage.
167 + This saves a lot of processing time for new edges
169 + . Changed heuristic from "if new sub-prefix and trusted AS on path
170 + then it's okay" to "if new sub-prefix and same path is used to reach
171 + super-prefix, then it's okay". Might be better to change to "if old
172 + path is prefix of new path, then okay"
180 +#include "command.h"
187 +#include "bgpd/bgpd.h"
188 +#include "bgpd/bgp_aspath.h"
189 +#include "bgpd/bgp_pgbgp.h"
190 +#include "bgpd/bgp_table.h"
191 +#include "bgpd/bgp_route.h"
192 +#include "bgpd/bgp_attr.h"
193 +#include "bgpd/bgp_advertise.h"
199 +struct hash * ashash;
201 +static void *edge_hash_alloc (void *arg);
202 +static unsigned int edge_key_make (void *p);
203 +static int edge_cmp (const void *arg1, const void *args);
206 +static struct bgp_pgbgp_pathSet bgp_pgbgp_pathOrigin (struct aspath *);
207 +static int bgp_pgbgp_pathLength (struct aspath *asp);
208 +static int bgp_pgbgp_gc (struct bgp_table *);
209 +static int bgp_pgbgp_clean (struct bgp_table *);
210 +static int bgp_pgbgp_reuse (time_t);
211 +static struct bgp_node *findSuper (struct bgp_table *table, struct prefix *p,
213 +static int bgp_pgbgp_store (struct bgp_table *table);
214 +static int bgp_pgbgp_restore (void);
215 +static struct bgp_info *bgp_pgbgp_selected (struct bgp_node *node);
216 +static int originInRIB (struct bgp_node *node, struct bgp_pgbgp_origin *origin);
217 +static int prefixInRIB (struct bgp_node *node, struct bgp_pgbgp_prefix *prefix);
218 +static int edgeInRIB (struct bgp_pgbgp_edge *e);
221 +static void bgp_pgbgp_logOriginAnomaly (as_t asn, struct bgp_node *rn,
223 +static int bgp_pgbgp_reuseOrigin (struct bgp_pgbgp_r_origin);
224 +static void bgp_pgbgp_cleanHistTable (struct bgp_table *);
225 +static int bgp_pgbgp_garbageCollectHistTable (struct bgp_table *);
226 +static void bgp_pgbgp_storeHistTable (struct bgp_table *table, FILE * file);
227 +static int bgp_pgbgp_updateOrigin (struct bgp_pgbgp_hist *, struct bgp_info *,
228 + struct attr *, struct bgp_node *, time_t, int);
231 +// Sub-Prefix Hijack Detector Functions
232 +static int bgp_pgbgp_shouldIgnore (struct bgp_node *super, struct bgp_info *selected);
233 +static void bgp_pgbgp_logSubprefixAnomaly (as_t asn, struct bgp_node *rn,
234 + struct attr *, struct bgp_node *super);
235 +static int bgp_pgbgp_reusePrefix (struct bgp_pgbgp_r_prefix);
236 +static int bgp_pgbgp_updatePrefix (struct bgp_pgbgp_hist *hist, struct bgp_node *,
237 + struct bgp_info *, struct attr *,
238 + struct bgp_node *, time_t, int);
241 +// Spoofed Edge Detector Functions
242 +static void bgp_pgbgp_cleanEdges (void);
243 +static void bgp_pgbgp_logEdgeAnomaly (struct bgp_node *rn, struct attr *,
244 + struct edge *edge);
245 +static int bgp_pgbgp_reuseEdge (struct bgp_pgbgp_r_edge);
246 +static void bgp_pgbgp_storeEdges (struct bgp_table *, FILE *);
247 +static int bgp_pgbgp_garbageCollectEdges (struct bgp_table *);
248 +static int bgp_pgbgp_updateEdge (struct bgp_pgbgp_hist *hist, struct bgp_info *,
249 + struct attr *, struct bgp_node *, time_t, int);
250 +static int bgp_pgbgp_restoreEdge (FILE * file);
251 +static void bgp_pgbgp_storeEdges (struct bgp_table *table, FILE * file);
255 +// New Peer Detector Functions
256 +static int bgp_pgbgp_updatePeer (struct bgp_info *binfo, time_t now);
259 +/* --------------- Global Variables ------------------ */
260 +struct bgp_pgbgp_config bgp_pgbgp_cfg;
261 +struct bgp_pgbgp_config *pgbgp = &bgp_pgbgp_cfg;
262 +/*! --------------- Global Variables ------------------ !*/
264 +/* --------------- VTY (others exist in bgp_route.c) ------------------ */
274 +edge_neighbor_iterator (struct hash_backet *backet, struct nsearch *pns)
276 + struct bgp_pgbgp_edge *hedge = backet->data;
277 + if ((hedge->e.a == pns->asn || hedge->e.b == pns->asn)
278 + && hedge->e.a != hedge->e.b)
280 + struct vty *vty = pns->pvty;
281 + if (hedge->deprefUntil > pns->time)
282 + vty_out (pns->pvty, "Untrusted: %d -- %d%s", hedge->e.a, hedge->e.b,
285 + vty_out (pns->pvty, "Trusted: %d -- %d%s", hedge->e.a, hedge->e.b,
291 +bgp_pgbgp_stats_neighbors (struct vty *vty, afi_t afi, safi_t safi, as_t asn)
295 + ns.time = time (NULL);
298 + hash_iterate (pgbgp->edgeT,
299 + (void (*)(struct hash_backet *, void *))
300 + edge_neighbor_iterator, &ns);
301 + return CMD_SUCCESS;
305 +bgp_pgbgp_stats_origins (struct vty *vty, afi_t afi, safi_t safi,
306 + const char *prefix)
309 + struct bgp_table *table;
310 + time_t t_now = time (NULL);
311 + bgp = bgp_get_default ();
313 + return CMD_WARNING;
314 + if (bgp->rib == NULL)
315 + return CMD_WARNING;
316 + table = bgp->rib[afi][safi];
318 + return CMD_WARNING;
321 + str2prefix (prefix, &p);
322 + struct bgp_node *rn = bgp_node_match (table, &p);
323 + vty_out (vty, "%s%s", prefix, VTY_NEWLINE);
328 + for (struct bgp_pgbgp_origin * cur = rn->hist->o; cur != NULL;
331 + if (cur->deprefUntil > t_now)
332 + vty_out (vty, "Untrusted Origin AS: %d%s", cur->originAS,
335 + vty_out (vty, "Trusted Origin AS: %d%s", cur->originAS,
339 + bgp_unlock_node (rn);
341 + return CMD_SUCCESS;
345 +bgp_pgbgp_stats (struct vty *vty, afi_t afi, safi_t safi)
348 + struct bgp_table *table;
351 + bgp = bgp_get_default ();
353 + return CMD_WARNING;
354 + if (bgp->rib == NULL)
355 + return CMD_WARNING;
356 + table = bgp->rib[afi][safi];
358 + return CMD_WARNING;
360 + // bgp_pgbgp_store(table);
362 + // Print out the number of anomalous routes
365 + int num_selected = 0;
366 + int num_origin = 0;
368 + int num_ignored = 0;
371 + for (struct bgp_node * rn = bgp_table_top (table); rn;
372 + rn = bgp_route_next (rn))
374 + for (struct bgp_info * ri = rn->info; ri; ri = ri->next)
377 + if (ANOMALOUS (ri->flags))
380 + if (CHECK_FLAG (ri->flags, BGP_INFO_SELECTED))
383 + if (CHECK_FLAG (ri->flags, BGP_INFO_SUSPICIOUS_O))
385 + if (CHECK_FLAG (ri->flags, BGP_INFO_SUSPICIOUS_E))
387 + if (CHECK_FLAG (ri->flags, BGP_INFO_SUSPICIOUS_P))
389 + if (CHECK_FLAG (ri->flags, BGP_INFO_IGNORED_P))
395 + vty_out (vty, "%-30s: %10d%s", "Routes in the RIB", routes, VTY_NEWLINE);
396 + vty_out (vty, "%-30s: %10d%s", "Anomalous routes in RIB", anomalous,
398 + vty_out (vty, "%-30s: %10d%s", "Selected anomalous routes", num_selected,
400 + vty_out (vty, "-----------------------------%s", VTY_NEWLINE);
401 + vty_out (vty, "%-30s: %10d%s", "Routes with anomalous origins", num_origin,
403 + vty_out (vty, "%-30s: %10d%s", "Routes with anomalous edges", num_edge,
405 + vty_out (vty, "%-30s: %10d%s", "Routes ignored for sub-prefix", num_ignored,
407 + vty_out (vty, "%-30s: %10d%s", "Less specific routes to avoid", num_super,
410 + vty_out (vty, "There are %d routes in the RIB.%s", routes, VTY_NEWLINE);
411 + vty_out (vty, "%d are anomalous.%s", anomalous, VTY_NEWLINE);
412 + vty_out (vty, "%d anomalous routes are selected.%s", num_selected, VTY_NEWLINE);
413 + vty_out (vty, "%s", VTY_NEWLINE);
414 + vty_out (vty, "Anomaly breakdown:%s", VTY_NEWLINE);
415 + vty_out (vty, "%d contain anomalous origins%s", num_origin, VTY_NEWLINE);
416 + vty_out (vty, "%d contain anomalous edges.%s", num_edge, VTY_NEWLINE);
417 + vty_out (vty, "%d are for ignored sub-prefixes.%s", num_ignored, VTY_NEWLINE);
418 + vty_out (vty, "%d are super-net routes through peers that announced anomalous sub-prefixes.%s", num_super, VTY_NEWLINE);
420 + return CMD_SUCCESS;
424 +DEFUN (show_ip_bgp_pgbgp,
425 + show_ip_bgp_pgbgp_cmd,
426 + "show ip bgp pgbgp",
427 + SHOW_STR IP_STR BGP_STR "Display PGBGP statistics\n")
429 + return bgp_pgbgp_stats (vty, AFI_IP, SAFI_UNICAST);
432 +DEFUN (show_ip_bgp_pgbgp_neighbors,
433 + show_ip_bgp_pgbgp_neighbors_cmd,
434 + "show ip bgp pgbgp neighbors WORD",
439 + "BGP pgbgp neighbors\n" "ASN whos neighbors should be displayed\n")
441 + return bgp_pgbgp_stats_neighbors (vty, AFI_IP, SAFI_UNICAST,
445 +DEFUN (show_ip_bgp_pgbgp_origins,
446 + show_ip_bgp_pgbgp_origins_cmd,
447 + "show ip bgp pgbgp origins A.B.C.D/M",
452 + "BGP pgbgp neighbors\n" "Prefix to look up origin ASes of\n")
454 + return bgp_pgbgp_stats_origins (vty, AFI_IP, SAFI_UNICAST, argv[0]);
460 +/*! --------------- VTY (others exist in bgp_route.c) ------------------ !*/
468 +/* --------------- Helper Functions ------------------ */
470 + If the origin hasn't been seen/verified lately, look for it in the RIB
473 +originInRIB (struct bgp_node *node, struct bgp_pgbgp_origin *origin)
475 + for (struct bgp_info * ri = node->info; ri; ri = ri->next)
477 + struct bgp_pgbgp_pathSet pathOrigins;
478 + pathOrigins = bgp_pgbgp_pathOrigin (ri->attr->aspath);
479 + for (int i = 0; i < pathOrigins.length; ++i)
481 + if (pathOrigins.ases[i] == origin->originAS)
492 + If the prefix hasn't been seen/verified lately, look for it in the RIB
495 +prefixInRIB (struct bgp_node *node, struct bgp_pgbgp_prefix *prefix)
503 +edge_inRIB_iterator (struct hash_backet *backet, struct bgp_pgbgp_edge *hedge)
505 + struct aspath *p = backet->data;
507 + struct edge curEdge;
511 + struct assegment *seg;
513 + for (seg = p->segments; seg; seg = seg->next)
515 + for (int i = 0; i < seg->length; i++)
517 + curEdge.a = curEdge.b;
518 + curEdge.b = seg->as[i];
524 + // Is this the edge we're looking for?
525 + if (curEdge.a == hedge->e.a && curEdge.b == hedge->e.b)
527 + hedge->lastSeen = time (NULL);
537 + If the edge hasn't been seen/verified lately, look for it in the AS path list
538 + This function is expensive, use sparingly
541 +edgeInRIB (struct bgp_pgbgp_edge *e)
544 + completed = hash_iterate_until (ashash,
545 + (int (*)(struct hash_backet *, void *))
546 + edge_inRIB_iterator, e);
556 + Return the selected route for the given route node
560 +bgp_pgbgp_selected (struct bgp_node *node)
562 + for (struct bgp_info * ri = node->info; ri; ri = ri->next)
564 + if (CHECK_FLAG (ri->flags, BGP_INFO_SELECTED))
571 +reuse_cmp (void *node1, void *node2)
573 + struct bgp_pgbgp_reuse *a;
574 + struct bgp_pgbgp_reuse *b;
575 + a = (struct bgp_pgbgp_reuse *) node1;
576 + b = (struct bgp_pgbgp_reuse *) node2;
577 + return a->deprefUntil - b->deprefUntil;
581 +bgp_pgbgp_pathLength (struct aspath *asp)
583 + struct assegment *seg;
584 + if ((asp == NULL) || (asp->segments == NULL))
587 + seg = asp->segments;
588 + while (seg->next != NULL)
590 + count += seg->length;
598 +/* Find the origin(s) of the path
599 + All ASes in the final set are considered origins */
600 +static struct bgp_pgbgp_pathSet
601 +bgp_pgbgp_pathOrigin (struct aspath *asp)
603 + struct assegment *seg, *last;
604 + struct bgp_pgbgp_pathSet tmp;
608 + assert (asp != NULL && asp->segments != NULL);
610 + /* if ( (asp == NULL) || (asp->segments == NULL) )
613 + seg = asp->segments;
615 + while (seg->next != NULL)
617 + if (seg->type != AS_SET && seg->type != AS_CONFED_SET)
622 + if (seg->type == AS_SET || seg->type == AS_CONFED_SET)
627 + tmp.ases = &seg->as[seg->length - 1];
630 + if (seg->type == AS_SET || seg->type == AS_CONFED_SET)
632 + tmp.length = seg->length;
633 + tmp.ases = seg->as;
638 + tmp.ases = &seg->as[seg->length - 1];
641 + assert (tmp.length >= 1);
643 + // return seg->as[seg->length-1];
647 +bgp_pgbgp_reuse (time_t t_now)
650 + struct bgp_pgbgp_reuse *cur = NULL;
652 + while (pgbgp->rq_size > 0)
654 + cur = pqueue_dequeue (pgbgp->reuse_q);
655 + pgbgp->rq_size -= 1;
657 + // Is the next item ready to be reused?
658 + if (t_now < cur->deprefUntil)
660 + pqueue_enqueue (cur, pgbgp->reuse_q);
661 + pgbgp->rq_size += 1;
665 + // Okay, it needs to be reused now
666 + if (cur->type == PGBGP_REUSE_ORIGIN)
667 + bgp_pgbgp_reuseOrigin (cur->data.origin);
669 + else if (cur->type == PGBGP_REUSE_PREFIX)
670 + bgp_pgbgp_reusePrefix (cur->data.prefix);
672 + else if (cur->type == PGBGP_REUSE_EDGE)
673 + bgp_pgbgp_reuseEdge (cur->data.edge);
676 + XFREE (MTYPE_BGP_PGBGP_REUSE, cur);
681 +/* Check bit of the prefix. */
683 +check_bit (u_char * prefix, u_char prefixlen)
687 + u_char *p = (u_char *) prefix;
689 + assert (prefixlen <= 128);
691 + offset = prefixlen / 8;
692 + shift = 7 - (prefixlen % 8);
694 + return (p[offset] >> shift & 1);
698 + Find a super-net in the tree that's not currently anomalous if one exists
701 +findSuper (struct bgp_table *table, struct prefix *p, time_t t_now)
703 + struct bgp_node *node;
704 + struct bgp_node *matched;
709 + while (node && node->p.prefixlen < p->prefixlen &&
710 + prefix_match (&node->p, p))
712 + // Node may not yet have its info set when reading in from pgbgp log files
713 + if (node->hist && node->p.prefixlen >= 8)
715 + if (node->hist->p != NULL && node->hist->p->ignoreUntil < t_now)
716 + //if (node->hist->p != NULL && prefixInRIB (node, NULL))
717 + //if (node->hist->p != NULL)
720 + node = node->link[check_bit (&p->u.prefix, node->p.prefixlen)];
723 + return bgp_lock_node (matched);
731 +/*! --------------- Helper Functions ------------------ !*/
739 +/* --------------- Public PGBGP Interface ------------------ */
741 +bgp_pgbgp_enable (struct bgp *bgp, afi_t afi, safi_t safi,
742 + int ost, int est, int sst, int oht, int pht, int eht,
743 + const char *file, const char *anoms)
746 + if (CHECK_FLAG (bgp->af_flags[afi][safi], BGP_CONFIG_PGBGP))
748 + if (pgbgp->storage && pgbgp->anomalies)
750 + if (pgbgp->origin_sus_time == ost
751 + && pgbgp->edge_sus_time == est
752 + && pgbgp->sub_sus_time == sst
753 + && pgbgp->origin_hist_time == oht
754 + && pgbgp->prefix_hist_time == pht
755 + && pgbgp->edge_hist_time == eht
756 + && strcmp (pgbgp->storage, file) == 0
757 + && strcmp (pgbgp->anomalies, anoms) == 0)
763 + SET_FLAG (bgp->af_flags[afi][safi], BGP_CONFIG_PGBGP);
766 + time_t hour = 3600;
767 + time_t day = 86400;
774 + pgbgp->origin_sus_time = ost * hour;
775 + pgbgp->edge_sus_time = est * hour;
776 + pgbgp->sub_sus_time = sst * hour;
777 + pgbgp->origin_hist_time = oht * day;
778 + pgbgp->prefix_hist_time = pht * day;
779 + pgbgp->edge_hist_time = eht * day;
780 + pgbgp->peer_hist_time = DEFAULT_ORIGIN_HIST;
783 + pgbgp->storage = strdup (file);
785 + pgbgp->storage = NULL;
788 + pgbgp->anomalies = strdup (anoms);
790 + pgbgp->anomalies = NULL;
793 + pgbgp->reuse_q = pqueue_create ();
794 + pgbgp->reuse_q->cmp = reuse_cmp;
795 + pgbgp->rq_size = 0;
796 + pgbgp->lastgc = time (NULL);
797 + pgbgp->lastStore = time (NULL);
798 + pgbgp->startTime = time (NULL);
799 + install_element (VIEW_NODE, &show_ip_bgp_pgbgp_cmd);
800 + install_element (ENABLE_NODE, &show_ip_bgp_pgbgp_cmd);
801 + install_element (VIEW_NODE, &show_ip_bgp_pgbgp_neighbors_cmd);
802 + install_element (ENABLE_NODE, &show_ip_bgp_pgbgp_neighbors_cmd);
803 + install_element (VIEW_NODE, &show_ip_bgp_pgbgp_origins_cmd);
804 + install_element (ENABLE_NODE, &show_ip_bgp_pgbgp_origins_cmd);
805 + pgbgp->edgeT = hash_create_size (131072, edge_key_make, edge_cmp);
806 + bgp_pgbgp_restore ();
811 +bgp_pgbgp_disable (struct bgp *bgp, afi_t afi, safi_t safi)
813 + UNSET_FLAG (bgp->af_flags[afi][safi], BGP_CONFIG_PGBGP);
815 + // Clean the tables
816 + if (bgp->rib[afi][safi] != NULL)
817 + bgp_pgbgp_clean (bgp->rib[afi][safi]);
819 + bgp_pgbgp_cleanEdges ();
821 + if (pgbgp->storage != NULL)
822 + free (pgbgp->storage);
824 + if (pgbgp->anomalies != NULL)
825 + free (pgbgp->anomalies);
827 + struct bgp_pgbgp_peerTime *pr = pgbgp->peerLast;
830 + struct bgp_pgbgp_peerTime *cur = pr;
832 + XFREE (MTYPE_BGP_PGBGP_PEER, cur);
839 +bgp_pgbgp_clean (struct bgp_table *table)
841 + struct bgp_pgbgp_reuse *rnode = NULL;
843 + while (pgbgp->rq_size > 0)
845 + rnode = (struct bgp_pgbgp_reuse *) pqueue_dequeue (pgbgp->reuse_q);
846 + pgbgp->rq_size -= 1;
847 + XFREE (MTYPE_BGP_PGBGP_REUSE, rnode);
849 + pqueue_delete (pgbgp->reuse_q);
854 + // Clean the detectors
855 + bgp_pgbgp_cleanHistTable (table);
857 + bgp_pgbgp_cleanEdges ();
860 + // Clean up the RIB nodes
861 + for (struct bgp_node * rn = bgp_table_top (table); rn;
862 + rn = bgp_route_next (rn))
865 + for (struct bgp_info * ri = rn->info; ri; ri = ri->next)
867 + if (CHECK_FLAG (ri->flags, BGP_INFO_SUSPICIOUS_O
868 + | BGP_INFO_SUSPICIOUS_P | BGP_INFO_SUSPICIOUS_E
869 + | BGP_INFO_IGNORED_P))
872 + UNSET_FLAG (ri->flags, BGP_INFO_SUSPICIOUS_O
873 + | BGP_INFO_SUSPICIOUS_P | BGP_INFO_SUSPICIOUS_E
874 + | BGP_INFO_IGNORED_P);
877 + if (changed && rn->info)
879 + struct bgp_info *ri = rn->info;
880 + bgp_process (ri->peer->bgp, rn, rn->table->afi, rn->table->safi);
884 + hash_free (pgbgp->edgeT);
890 +bgp_pgbgp_gc (struct bgp_table *table)
892 + struct bgp *bgp = bgp_get_default ();
896 + // Collect each AFI/SAFI RIB
897 + for (afi_t afi = AFI_IP; afi < AFI_MAX; afi++)
898 + for (safi_t safi = SAFI_UNICAST; safi < SAFI_MAX; safi++)
900 + if (!CHECK_FLAG (bgp->af_flags[afi][safi], BGP_CONFIG_PGBGP))
902 + struct bgp_table *curTable = bgp->rib[afi][safi];
905 + bgp_pgbgp_garbageCollectHistTable (curTable);
908 + bgp_pgbgp_garbageCollectEdges (table);
914 +bgp_pgbgp_restore (void)
917 + if (pgbgp->storage == NULL)
919 + FILE *file = fopen (pgbgp->storage, "r");
925 + struct bgp *bgp = bgp_get_default ();
926 + struct bgp_node *curNode = NULL;
928 + // Get the log store time
929 + long long int writetime;
930 + fscanf (file, "%lld", &writetime);
931 + time_t swtime = writetime;
933 + // If it's too old (more than 1 week old), start fresh
934 + if (time (NULL) - swtime > 86400 * 7)
941 + // Get the PGBGP init time
942 + long long int stime;
943 + fscanf (file, "%lld", &stime);
944 + pgbgp->startTime = stime;
946 + while (fscanf (file, "%d", &type) != EOF)
949 + if (type == PREFIX_ID)
954 + long long int time;
955 + fscanf (file, "%s %u %u %lld", pre, &afi, &safi, &time);
956 + str2prefix (pre, &p);
957 + struct bgp_table *curTable = bgp->rib[afi][safi];
958 + assert (curTable != NULL);
960 + // Create and lock the node
961 + curNode = bgp_node_get (curTable, &p);
962 + assert (curNode->hist == NULL);
964 + // bgp_lock_node(curNode);
967 + XCALLOC (MTYPE_BGP_PGBGP_HIST, sizeof (struct bgp_pgbgp_hist));
968 + assert (curNode->hist != NULL);
971 + XCALLOC (MTYPE_BGP_PGBGP_PREFIX,
972 + sizeof (struct bgp_pgbgp_prefix));
973 + assert (curNode->hist->p != NULL);
975 + curNode->hist->p->lastSeen = time;
977 + else if (type == ORIGIN_ID)
980 + long long int time;
981 + fscanf (file, "%u %lld", &ASN, &time);
982 + struct bgp_pgbgp_origin *or = XCALLOC (MTYPE_BGP_PGBGP_ORIGIN,
984 + bgp_pgbgp_origin));
985 + or->lastSeen = time;
986 + or->originAS = ASN;
987 + or->next = curNode->hist->o;
988 + curNode->hist->o = or;
990 + else if (type == EDGE_ID)
992 + bgp_pgbgp_restoreEdge (file);
994 + else if (type == PEER_ID)
996 + struct bgp_pgbgp_peerTime *pr;
997 + long long int time;
998 + union sockunion su;
1000 + fscanf (file, "%s %lld", szsu, &time);
1001 + str2sockunion (szsu, &su);
1003 + XCALLOC (MTYPE_BGP_PGBGP_PEER,
1004 + sizeof (struct bgp_pgbgp_peerTime));
1006 + pr->lastSeen = time;
1007 + pr->next = pgbgp->peerLast;
1008 + pgbgp->peerLast = pr;
1017 +bgp_pgbgp_store (struct bgp_table *table)
1019 + if (pgbgp->storage == NULL)
1021 + char *tmpname = malloc (sizeof (char) * (1 + 4 + strlen (pgbgp->storage)));
1022 + strcpy (tmpname, pgbgp->storage);
1023 + strcat (tmpname, ".tmp");
1024 + FILE *file = fopen (tmpname, "w");
1032 + // Store the current time
1033 + fprintf (file, "%lld\n", (long long int) time (NULL));
1035 + // Store the init time
1036 + fprintf (file, "%lld\n", (long long int) pgbgp->startTime);
1038 + // Store the peer times
1039 + for (struct bgp_pgbgp_peerTime * pr = pgbgp->peerLast; pr; pr = pr->next)
1041 + char strSock[128];
1042 + sockunion2str (&pr->su, strSock, sizeof (strSock));
1044 + if (pr->deprefUntil < time (NULL))
1046 + fprintf (file, "%d %s %lld\n", PEER_ID, strSock,
1047 + (long long int) pr->lastSeen);
1051 + // Store the tables
1052 + bgp_pgbgp_storeHistTable (table, file);
1053 + bgp_pgbgp_storeEdges (table, file);
1057 + rename (tmpname, pgbgp->storage);
1064 + Check to see if we've seen the peer recently
1065 + If not, then we need to return true and not delay routes
1069 +bgp_pgbgp_updatePeer (struct bgp_info *binfo, time_t now)
1071 + int status = false;
1073 + struct bgp_pgbgp_peerTime *pr = pgbgp->peerLast;
1074 + for (; pr; pr = pr->next)
1075 + if (sockunion_same (&pr->su, &binfo->peer->su))
1078 + // If this is a new peer, create it
1081 + pr = XCALLOC (MTYPE_BGP_PGBGP_PEER, sizeof (struct bgp_pgbgp_peerTime));
1082 + pr->su = binfo->peer->su;
1083 + pr->next = pgbgp->peerLast;
1084 + pgbgp->peerLast = pr;
1087 + // Is it currently marked as new?
1088 + if (pr->deprefUntil > now)
1089 + goto UPPEER_DEPREF;
1091 + // Have we seen the peer recently?
1092 + if (pr->lastSeen + pgbgp->peer_hist_time > now)
1093 + goto UPPEER_CLEAN;
1095 + // It must not have been seen lately, depref it
1096 + pr->deprefUntil = now + PGBGP_PEER_GRACE;
1103 + pr->lastSeen = now;
1110 + Returns whether or not the sub-prefix should be ignored
1113 +bgp_pgbgp_shouldIgnore (struct bgp_node *super, struct bgp_info *selected)
1115 + if (!selected || CHECK_FLAG (selected->flags, BGP_INFO_SUSPICIOUS_P))
1121 + This is a special case function for smoothly handling sub-prefix hijacks.
1123 + It handles the following 2 events:
1125 + Event 1: The super-prefix of an anomalous prefix has a route through a non-anomalous
1127 + Event 1: An anomalous sub-prefix is ignored, but no best route for the super-prefix exists
1128 + Response: Announce the sub-prefix until the super-prefix comes back
1130 + Event 2: A super-prefix comes back to the RIB and its anomalous sub-prefix is in use
1131 + Response: Ignore the sub-prefix again
1136 +bgp_pgbgp_rib_updated (struct bgp_node *rn, struct bgp_info *old_best,
1137 + struct bgp_info *new_best)
1140 + struct bgp_pgbgp_hist *hist = rn->hist;
1145 + time_t t_now = time (NULL);
1148 + If we can't avoid the sub-prefix by routing to the super-prefix,
1149 + then route as normal to the sub-prefix
1151 + if (!bgp_pgbgp_shouldIgnore (rn, new_best))
1153 + for (struct bgp_pgbgp_avoid * cur = hist->p->avoid; cur;
1156 + if (cur->avoidUntil > t_now)
1158 + int changed = false;
1159 + for (struct bgp_info * ri = cur->sub->info; ri; ri = ri->next)
1161 + if (CHECK_FLAG (ri->flags, BGP_INFO_IGNORED_P))
1164 + UNSET_FLAG (ri->flags, BGP_INFO_IGNORED_P);
1169 + struct bgp_info *ri = cur->sub->info;
1170 + if (ri && ri->peer && ri->peer->bgp)
1171 + bgp_process (ri->peer->bgp, cur->sub,
1172 + cur->sub->table->afi, cur->sub->table->safi);
1181 + If we can avoid the sub-prefix by routing to the super-prefix,
1187 + for (struct bgp_pgbgp_avoid * cur = hist->p->avoid; cur;
1190 + if (cur->avoidUntil > t_now)
1192 + int changed = false;
1193 + for (struct bgp_info * ri = cur->sub->info; ri; ri = ri->next)
1195 + if (!CHECK_FLAG (ri->flags, BGP_INFO_IGNORED_P))
1198 + SET_FLAG (ri->flags, BGP_INFO_IGNORED_P);
1203 + struct bgp_info *ri = cur->sub->info;
1204 + if (ri && ri->peer && ri->peer->bgp)
1205 + bgp_process (ri->peer->bgp, cur->sub,
1206 + cur->sub->table->afi, cur->sub->table->safi);
1213 + if (old_best && !new_best)
1215 + time_t t_now = time(NULL);
1216 + for (struct bgp_pgbgp_avoid * cur = hist->p->avoid; cur;
1219 + if (cur->avoidUntil > t_now)
1221 + for (struct bgp_info * ri = cur->sub->info; ri; ri = ri->next)
1222 + UNSET_FLAG (ri->flags, BGP_INFO_IGNORED_P);
1224 + struct bgp_info *ri = cur->sub->info;
1225 + if (ri && ri->peer && ri->peer->bgp)
1226 + bgp_process (ri->peer->bgp, cur->sub, cur->sub->table->afi,
1227 + cur->sub->table->safi);
1233 + else if (!old_best && new_best)
1235 + time_t t_now = time(NULL);
1236 + for (struct bgp_pgbgp_avoid * av = hist->p->avoid; av; av = av->next)
1238 + struct bgp_info * ri = av->sub->info;
1239 + if (av->avoidUntil > t_now && ri && !CHECK_FLAG(ri->flags, BGP_INFO_IGNORED_P))
1241 + for (; ri; ri = ri->next)
1242 + SET_FLAG (ri->flags, BGP_INFO_IGNORED_P);
1243 + ri = av->sub->info;
1244 + if (ri && ri->peer && ri->peer->bgp)
1245 + bgp_process (ri->peer->bgp, av->sub,
1246 + av->sub->table->afi, av->sub->table->safi);
1256 +bgp_pgbgp_update (struct bgp_info *binfo, struct attr *at,
1257 + struct bgp_node *rn)
1259 + time_t t_now = time (NULL);
1261 + // Clean up the reuse list
1262 + bgp_pgbgp_reuse (t_now);
1268 + XCALLOC (MTYPE_BGP_PGBGP_HIST, sizeof (struct bgp_pgbgp_hist));
1269 + // Get the PGBGP history lock on rn
1270 + bgp_lock_node (rn);
1273 + struct bgp_node *superhn = NULL;
1275 + // implicit lock from node_get
1276 + superhn = findSuper (rn->table, &rn->p, t_now);
1278 + int newPeer = bgp_pgbgp_updatePeer (binfo, t_now);
1279 + bgp_pgbgp_updateOrigin (rn->hist, binfo, at, rn, t_now, newPeer);
1280 + bgp_pgbgp_updatePrefix (rn->hist, superhn, binfo, at, rn, t_now, newPeer);
1281 + bgp_pgbgp_updateEdge (rn->hist, binfo, at, rn, t_now, newPeer);
1283 + if (superhn != NULL)
1284 + bgp_unlock_node (superhn);
1288 + // GC and storage must be last, as they update lastSeen values of objects
1289 + // which would cause new routes to be recently seen, which is undesired behavior
1290 + // Make sure you don't collect anything that might be in use!
1291 + if (t_now >= pgbgp->lastgc + PGBGP_GC_DELTA)
1293 + bgp_pgbgp_gc (rn->table);
1294 + pgbgp->lastgc = t_now;
1297 + if (t_now >= pgbgp->lastStore + PGBGP_STORE_DELTA)
1299 + bgp_pgbgp_store (rn->table);
1300 + pgbgp->lastStore = t_now;
1311 +/*! --------------- Public PGBGP Interface ------------------ !*/
1321 +/* --------------- MOAS Detection ------------------ */
1323 +bgp_pgbgp_storeHistTable (struct bgp_table *table, FILE * file)
1326 + t_now = time (NULL);
1328 + struct bgp *bgp = bgp_get_default ();
1332 + // Store each AFI/SAFI RIB
1333 + for (afi_t afi = AFI_IP; afi < AFI_MAX; afi++)
1334 + for (safi_t safi = SAFI_UNICAST; safi < SAFI_MAX; safi++)
1336 + if (!CHECK_FLAG (bgp->af_flags[afi][safi], BGP_CONFIG_PGBGP))
1338 + struct bgp_table *curTable = bgp->rib[afi][safi];
1342 + for (struct bgp_node * rn = bgp_table_top (curTable); rn;
1343 + rn = bgp_route_next (rn))
1345 + struct bgp_pgbgp_hist *hist = rn->hist;
1348 + char szPrefix[128];
1349 + prefix2str (&rn->p, szPrefix, sizeof (szPrefix));
1352 + struct bgp_pgbgp_prefix *pre = hist->p;
1353 + if (pre && pre->ignoreUntil <= t_now)
1355 + if (pre->lastSeen + pgbgp->prefix_hist_time > t_now)
1356 + fprintf (file, "%d %s %u %u %lld\n", PREFIX_ID, szPrefix,
1357 + (unsigned int) afi, (unsigned int) safi,
1358 + (long long int) pre->lastSeen);
1362 + /* Need a prefix in the file before the origins,
1363 + if no prefix.. skip origins */
1367 + for (struct bgp_pgbgp_origin * cur = hist->o; cur;
1370 + if (cur->deprefUntil > t_now)
1373 + if (cur->lastSeen + pgbgp->origin_hist_time > t_now)
1374 + fprintf (file, "%d %u %lld\n", ORIGIN_ID, cur->originAS,
1375 + (long long int) cur->lastSeen);
1384 +bgp_pgbgp_garbageCollectHistTable (struct bgp_table *table)
1387 + t_now = time (NULL);
1390 + for (struct bgp_node * rn = bgp_table_top (table); rn;
1391 + rn = bgp_route_next (rn))
1393 + int collect = false;
1394 + struct bgp_pgbgp_hist *hist = rn->hist;
1398 + struct bgp_pgbgp_origin *cur = hist->o;
1399 + struct bgp_pgbgp_prefix *pre = hist->p;
1400 + struct bgp_pgbgp_origin *parent = NULL;
1403 + if (cur != NULL || pre != NULL)
1406 + while (cur != NULL)
1408 + // Update the lastSeen time w/ originInRIB
1409 + if (originInRIB (rn, cur))
1410 + cur->lastSeen = t_now;
1415 + if (cur->lastSeen + pgbgp->origin_hist_time <= t_now)
1418 + // Collect if anomaly just became okay but not seen since last collection
1419 + if (cur->deprefUntil != 0 && cur->deprefUntil < t_now)
1421 + if (cur->lastSeen < pgbgp->lastgc)
1423 + cur->deprefUntil = 0;
1428 + if (parent == NULL)
1429 + hist->o = cur->next;
1431 + parent->next = cur->next;
1433 + // Delete cur, parent doesn't change
1434 + struct bgp_pgbgp_origin *del = cur;
1436 + XFREE (MTYPE_BGP_PGBGP_ORIGIN, del);
1445 + // Update the lastSeen time w/ prefixInRIB
1446 + if (pre && prefixInRIB (rn, pre))
1447 + pre->lastSeen = t_now;
1452 + if (pre && pre->lastSeen + pgbgp->prefix_hist_time <= t_now)
1455 + // Collect if anomaly just became okay but not seen since last collection
1456 + if (pre && pre->ignoreUntil != 0 && pre->ignoreUntil < t_now)
1458 + if (pre->lastSeen < pgbgp->lastgc)
1460 + pre->ignoreUntil = 0;
1465 + for (struct bgp_pgbgp_avoid * av = pre->avoid; av;)
1467 + struct bgp_pgbgp_avoid *del = av;
1469 + bgp_unlock_node (del->sub);
1470 + XFREE (MTYPE_BGP_PGBGP_AVOID, del);
1473 + XFREE (MTYPE_BGP_PGBGP_PREFIX, pre);
1477 + // If the node isn't in use, remove it
1478 + if (used && hist->o == NULL && hist->p == NULL)
1480 + XFREE (MTYPE_BGP_PGBGP_HIST, hist);
1482 + bgp_unlock_node (rn);
1490 +bgp_pgbgp_cleanHistTable (struct bgp_table *table)
1492 + // Clean up the RIB nodes
1493 + for (struct bgp_node * rn = bgp_table_top (table); rn;
1494 + rn = bgp_route_next (rn))
1496 + struct bgp_pgbgp_hist *hist = rn->hist;
1502 + for (struct bgp_pgbgp_avoid * av = hist->p->avoid; av;)
1504 + struct bgp_pgbgp_avoid *del = av;
1506 + bgp_unlock_node (del->sub);
1507 + XFREE (MTYPE_BGP_PGBGP_AVOID, del);
1509 + hist->p->avoid = NULL;
1510 + XFREE (MTYPE_BGP_PGBGP_PREFIX, hist->p);
1514 + for (struct bgp_pgbgp_origin * cur = hist->o; cur;)
1516 + struct bgp_pgbgp_origin *next = cur->next;
1517 + XFREE (MTYPE_BGP_PGBGP_ORIGIN, cur);
1521 + XFREE (MTYPE_BGP_PGBGP_HIST, hist);
1523 + bgp_unlock_node (rn);
1528 +bgp_pgbgp_logOriginAnomaly (as_t asn, struct bgp_node *rn, struct attr *at)
1531 + if (!pgbgp->anomalies)
1533 + FILE *file = fopen (pgbgp->anomalies, "a");
1538 + prefix2str (&rn->p, pre, sizeof (pre));
1540 + // MOAS | TIME | NEXTHOP | PREFIX | SUSPICIOUS_ORIGIN | TRUSTED_ORIGINS | PATH
1541 + fprintf (file, "%d|%lld|%s|%s|%d|", MOAS, (long long int) time (NULL),
1542 + inet_ntoa (at->nexthop), pre, asn);
1545 + // Print the trusted origins
1546 + assert (rn->hist);
1547 + assert (rn->hist->o);
1549 + struct bgp_pgbgp_hist *hist = rn->hist;
1551 + for (struct bgp_pgbgp_origin * cur = hist->o; cur != NULL; cur = cur->next)
1553 + if (cur->deprefUntil > time (NULL))
1555 + fprintf (file, "%d", cur->originAS);
1556 + if (cur->next != NULL)
1557 + fprintf (file, " ");
1560 + fprintf (file, " |%s\n", aspath_print (at->aspath));
1565 +bgp_pgbgp_updateOrigin (struct bgp_pgbgp_hist *hist, struct bgp_info *binfo,
1566 + struct attr *at, struct bgp_node *rn, time_t t_now,
1569 + struct bgp_pgbgp_pathSet pathOrigins;
1570 + struct bgp_pgbgp_origin *pi = NULL;
1572 + struct bgp_pgbgp_reuse *r;
1573 + pathOrigins = bgp_pgbgp_pathOrigin (at->aspath);
1576 + for (int i = 0; i < pathOrigins.length; i++)
1578 + as_t pathOrigin = pathOrigins.ases[i];
1580 + /* Is the Origin AS in the history? */
1581 + for (pi = hist->o; pi; pi = pi->next)
1582 + if (pi->originAS == pathOrigin)
1588 + XCALLOC (MTYPE_BGP_PGBGP_ORIGIN,
1589 + sizeof (struct bgp_pgbgp_origin));
1590 + pi->next = hist->o;
1591 + pi->originAS = pathOrigin;
1595 + // If this is our first origin for the prefix, let the sub-prefix
1596 + // check take care of it
1597 + if (pi->next == NULL)
1600 + /* Is the origin currently marked as suspicious? */
1601 + if (pi->deprefUntil > t_now)
1604 + /* Have we seen the origin recently? */
1605 + if (pi->lastSeen + pgbgp->origin_hist_time > t_now)
1608 +#ifndef PGBGP_DEBUG
1609 + /* Are we within the initial grace period? */
1614 + /* It must not be in recent history, depref origin for first time */
1615 + pi->deprefUntil = t_now + pgbgp->origin_sus_time;
1616 + bgp_pgbgp_logOriginAnomaly (pathOrigin, rn, at);
1618 + r = XCALLOC (MTYPE_BGP_PGBGP_REUSE, sizeof (struct bgp_pgbgp_reuse));
1619 + r->type = PGBGP_REUSE_ORIGIN;
1620 + r->deprefUntil = pi->deprefUntil;
1621 + r->data.origin.originAS = pathOrigin;
1622 + r->data.origin.rn = rn;
1623 + bgp_lock_node (rn);
1624 + pqueue_enqueue (r, pgbgp->reuse_q);
1625 + pgbgp->rq_size += 1;
1629 + SET_FLAG (binfo->flags, BGP_INFO_SUSPICIOUS_O);
1630 + status = BGP_INFO_SUSPICIOUS_O;
1633 + pi->lastSeen = t_now;
1639 +bgp_pgbgp_reuseOrigin (struct bgp_pgbgp_r_origin data)
1641 + struct bgp_info *ri;
1642 + int numChanged = 0;
1643 + time_t t_now = time (NULL);
1644 + assert (data.rn->hist != NULL);
1646 + // Repreference paths for this prefix that are now okay
1647 + for (ri = data.rn->info; ri; ri = ri->next)
1649 + if (CHECK_FLAG (ri->flags, BGP_INFO_SUSPICIOUS_O))
1651 + struct bgp_pgbgp_pathSet pathOrigins;
1652 + pathOrigins = bgp_pgbgp_pathOrigin (ri->attr->aspath);
1654 + for (int i = 0; i < pathOrigins.length; i++)
1656 + as_t pathOrigin = pathOrigins.ases[i];
1657 + // Find the origin
1658 + struct bgp_pgbgp_origin *o = NULL;
1659 + for (o = data.rn->hist->o; o != NULL; o = o->next)
1660 + if (o->originAS == pathOrigin)
1664 + for(struct bgp_pgbgp_origin * z = data.rn->hist->o; z != NULL; z = z->next)
1665 + printf("Known origin: %d\n", z->originAS);
1667 + prefix2str(&data.rn->p, pre, 128);
1668 + printf("%s : %s : %d\n", pre, ri->attr->aspath->str, pathOrigin);
1671 + assert (o != NULL);
1673 + if (o->deprefUntil <= t_now)
1676 + if (numOkay == pathOrigins.length)
1678 + UNSET_FLAG (ri->flags, BGP_INFO_SUSPICIOUS_O);
1684 + ri = data.rn->info;
1686 + // Rerun the decision process?
1687 + if (numChanged > 0)
1688 + bgp_process (ri->peer->bgp, data.rn, data.rn->table->afi,
1689 + data.rn->table->safi);
1693 + // Remove this (origin,prefix) pair from the normal database
1694 + // if it's not still in the RIB
1695 + struct bgp_pgbgp_hist *hist = rn->hist;
1696 + struct bgp_pgbgp_origin * cur = hist->o;
1697 + struct bgp_pgbgp_origin * parent = NULL;
1699 + // Find the origin AS node
1700 + while(cur != NULL)
1702 + if (cur->originAS == data.originAS)
1704 + // Delete the node if it hasn't been seen
1705 + // since the last storage run
1706 + if (cur->lastSeen < pgbgp->lastStore) {
1707 + // Delete this node
1708 + if (parent == NULL)
1709 + hist->o = cur->next;
1711 + parent->next = cur->next;
1713 + XFREE(MTYPE_BGP_PGBGP_ORIGIN, cur);
1722 + bgp_unlock_node (data.rn);
1726 +/*! --------------- MOAS Detection ------------------ !*/
1729 +/* --------------- Sub-Prefix Detection ------------------ */
1736 +bgp_pgbgp_logSubprefixAnomaly (as_t asn, struct bgp_node *rn, struct attr *at,
1737 + struct bgp_node *super)
1740 + if (!pgbgp->anomalies)
1742 + FILE *file = fopen (pgbgp->anomalies, "a");
1747 + prefix2str (&rn->p, pre, sizeof (pre));
1749 + char superpre[256];
1750 + prefix2str (&super->p, superpre, sizeof (superpre));
1752 + // SUBPREFIX | TIME | NEXTHOP | PREFIX | SUPER-PREFIX | SUSPICIOUS_ORIGIN | TRUSTED_ORIGINS | PATH
1753 + fprintf (file, "%d|%lld|%s|%s|%s|%d|", SUBPREFIX,
1754 + (long long int) time (NULL), inet_ntoa (at->nexthop), pre,
1757 + // Print the trusted origins
1758 + assert (super->hist);
1759 + assert (super->hist->o);
1761 + struct bgp_pgbgp_hist *hist = super->hist;
1763 + for (struct bgp_pgbgp_origin * cur = hist->o; cur != NULL; cur = cur->next)
1765 + if (cur->deprefUntil > time (NULL))
1767 + fprintf (file, "%d", cur->originAS);
1768 + if (cur->next != NULL)
1769 + fprintf (file, " ");
1772 + fprintf (file, " |%s\n", aspath_print (at->aspath));
1777 + If the first path is a prefix of the second, then return true
1781 +bgp_pgbgp_pathIsPrefix(struct aspath *trusted, struct aspath * new)
1783 + if (trusted == new)
1786 + struct assegment *seg1 = trusted->segments;
1787 + struct assegment *seg2 = new->segments;
1789 + while (seg1 || seg2)
1791 + if ((!seg1 && seg2) || (seg1 && !seg2))
1793 + if (seg1->type != seg2->type)
1796 + if (seg1->length > seg2->length)
1799 + for(int i = 0; i < seg1->length; i++)
1800 + if (seg1->as[i] != seg2->as[i])
1803 + seg1 = seg1->next;
1804 + seg2 = seg2->next;
1811 +bgp_pgbgp_updatePrefix (struct bgp_pgbgp_hist *hist,
1812 + struct bgp_node *supernode, struct bgp_info *binfo,
1813 + struct attr *at, struct bgp_node *rn, time_t t_now,
1816 + struct bgp_pgbgp_prefix *pre = NULL;
1817 + struct bgp_pgbgp_reuse *r = NULL;
1819 + int changed = false;
1824 + /* Do we have this prefix? */
1828 + XCALLOC (MTYPE_BGP_PGBGP_PREFIX, sizeof (struct bgp_pgbgp_prefix));
1832 + /* Is the prefix currently marked as suspicious? */
1833 + if (pre->ignoreUntil > t_now)
1838 + /* Should this neighbor be avoided for this prefix because it
1839 + sent us info. about a suspicious sub-prefix? */
1840 + for (struct bgp_pgbgp_avoid * av = hist->p->avoid; av; av = av->next)
1842 + if (binfo->peer->as == av->peerASN && av->avoidUntil > t_now)
1844 + SET_FLAG (binfo->flags, BGP_INFO_SUSPICIOUS_P);
1845 + status = BGP_INFO_SUSPICIOUS_P;
1850 + /* Have we seen the prefix recently? */
1851 + if (pre->lastSeen + pgbgp->prefix_hist_time > t_now)
1854 +#ifndef PGBGP_DEBUG
1855 + /* Are we within the initial grace period? */
1860 + /* Is there a less specific *in recent history* that this could be hijacking? */
1861 + if (supernode == NULL)
1864 + /* Does this path the super-net's non-anomalous path from this peer? If so it's okay */
1865 + int found = false;
1866 + for (struct bgp_info * ri = supernode->info; ri; ri = ri->next)
1868 + if (ri->peer->as == binfo->peer->as)
1870 + if (!ANOMALOUS(ri->flags) && bgp_pgbgp_pathIsPrefix(ri->attr->aspath, at->aspath))
1880 + It's not in recent history, and there is a less specific currently in use
1882 + . Ignore this prefix
1883 + . Make the less specific's route for this neighbor suspicious
1887 + pre->ignoreUntil = t_now + pgbgp->sub_sus_time;
1889 + struct bgp_pgbgp_pathSet pathOrigins;
1890 + pathOrigins = bgp_pgbgp_pathOrigin (at->aspath);
1891 + for (int i = 0; i < pathOrigins.length; i++)
1892 + bgp_pgbgp_logSubprefixAnomaly (pathOrigins.ases[i], rn, at, supernode);
1896 + r = XCALLOC (MTYPE_BGP_PGBGP_REUSE, sizeof (struct bgp_pgbgp_reuse));
1897 + r->type = PGBGP_REUSE_PREFIX;
1898 + r->deprefUntil = pre->ignoreUntil;
1899 + r->data.prefix.rn = rn;
1900 + r->data.prefix.rnsuper = supernode;
1901 + bgp_lock_node (rn);
1902 + bgp_lock_node (supernode);
1903 + pqueue_enqueue (r, pgbgp->reuse_q);
1904 + pgbgp->rq_size += 1;
1908 + if (supernode == NULL)
1911 + /* Set the less specific's route from this peer to suspicious */
1914 + for (struct bgp_info * ri = supernode->info; ri; ri = ri->next)
1916 + if (ri->peer->as == binfo->peer->as)
1918 + if (!CHECK_FLAG (ri->flags, BGP_INFO_SUSPICIOUS_P))
1920 + SET_FLAG (ri->flags, BGP_INFO_SUSPICIOUS_P);
1927 + // Make note of it in the less specific's history information
1929 + struct bgp_pgbgp_hist *superhist = supernode->hist;
1931 + if (superhist && superhist->p)
1933 + for (struct bgp_pgbgp_avoid * av = superhist->p->avoid; av;
1936 + if (av->peerASN == binfo->peer->as)
1938 + if (av->avoidUntil < pre->ignoreUntil)
1939 + av->avoidUntil = pre->ignoreUntil;
1946 + struct bgp_pgbgp_avoid *newavoid =
1947 + XCALLOC (MTYPE_BGP_PGBGP_AVOID, sizeof (struct bgp_pgbgp_avoid));
1948 + newavoid->peerASN = binfo->peer->as;
1949 + newavoid->avoidUntil = pre->ignoreUntil;
1950 + newavoid->next = superhist->p->avoid;
1951 + newavoid->sub = rn;
1952 + bgp_lock_node (rn);
1953 + superhist->p->avoid = newavoid;
1957 + ignore this route unless the supernet's node
1958 + is only a placeholder from loaded pgbgp data
1960 + if (bgp_pgbgp_shouldIgnore (supernode, bgp_pgbgp_selected (supernode)))
1962 + SET_FLAG (binfo->flags, BGP_INFO_IGNORED_P);
1963 + status = BGP_INFO_IGNORED_P;
1967 + struct bgp_info *ri = supernode->info;
1968 + bgp_process (ri->peer->bgp, supernode, supernode->table->afi,
1969 + supernode->table->safi);
1973 + pre->lastSeen = t_now;
1979 +bgp_pgbgp_reusePrefix (struct bgp_pgbgp_r_prefix data)
1981 + struct bgp_info *ri = NULL;
1983 + time_t t_now = time (NULL);
1985 + // Repreference all routes for this node
1986 + for (ri = data.rn->info; ri; ri = ri->next)
1987 + UNSET_FLAG (ri->flags, BGP_INFO_IGNORED_P);
1988 + ri = data.rn->info;
1990 + // Rerun the decision process
1992 + bgp_process (ri->peer->bgp, data.rn, data.rn->table->afi,
1993 + data.rn->table->safi);
1996 + // Remove the avoid nodes from the super
1997 + struct bgp_pgbgp_hist *superhist = data.rnsuper->hist;
1998 + if (superhist != NULL && superhist->p != NULL)
2000 + struct bgp_pgbgp_avoid *parent = NULL;
2001 + for (struct bgp_pgbgp_avoid * av = superhist->p->avoid; av;)
2003 + int numChanged = 0;
2004 + if (av->avoidUntil <= t_now)
2006 + struct bgp_pgbgp_avoid *del = av;
2008 + if (parent == NULL)
2009 + superhist->p->avoid = av;
2011 + parent->next = av;
2013 + // Repreference any routes
2014 + for (ri = data.rnsuper->info; ri; ri = ri->next)
2016 + if (ri->peer->as == del->peerASN)
2018 + UNSET_FLAG (ri->flags, BGP_INFO_SUSPICIOUS_P);
2023 + ri = data.rnsuper->info;
2025 + if (numChanged > 0 && ri != NULL)
2026 + bgp_process (ri->peer->bgp, data.rnsuper,
2027 + data.rnsuper->table->afi,
2028 + data.rnsuper->table->safi);
2029 + bgp_unlock_node (del->sub);
2030 + XFREE (MTYPE_BGP_PGBGP_AVOID, del);
2040 + // Remove this prefix from the normal database
2041 + // if it hasn't been seen in the RIB since the last
2044 + struct bgp_pgbgp_hist *hist = rn->hist;
2045 + struct bgp_pgbgp_prefix * pre = hist->p;
2047 + if (pre && pre->lastSeen < pgbgp->lastStore)
2049 + // Delete this node
2050 + for(struct bgp_pgbgp_avoid * av = hist->p->avoid; av;)
2052 + struct bgp_pgbgp_avoid *del = av;
2054 + bgp_unlock_node(del->sub);
2055 + XFREE (MTYPE_BGP_PGBGP_AVOID, del);
2057 + XFREE(MTYPE_BGP_PGBGP_PREFIX, pre);
2061 + bgp_unlock_node (data.rn);
2062 + bgp_unlock_node (data.rnsuper);
2066 +/*! --------------- Sub-Prefix Detection ------------------ !*/
2072 +/* --------------- Edge Detection ------------------ */
2075 +edge_store_clear_iterator (struct hash_backet *backet, void *file)
2077 + struct bgp_pgbgp_edge *hedge = backet->data;
2081 +edge_store_iterator (struct hash_backet *backet, FILE * file)
2083 + struct bgp_pgbgp_edge *hedge = backet->data;
2084 + time_t t_now = time (NULL);
2085 + if (hedge->deprefUntil > t_now)
2087 + if (hedge->lastSeen + pgbgp->edge_hist_time > t_now)
2089 + fprintf (file, "%d %u %u %lld\n", EDGE_ID, hedge->e.a, hedge->e.b,
2090 + (long long int) hedge->lastSeen);
2096 +bgp_pgbgp_storeEdges (struct bgp_table *table, FILE * file)
2098 + hash_iterate (pgbgp->edgeT,
2099 + (void (*)(struct hash_backet *, void *))
2100 + edge_store_iterator, file);
2106 +bgp_pgbgp_restoreEdge (FILE * file)
2108 + unsigned int a, b;
2109 + long long int lastSeen;
2110 + fscanf (file, "%u %u %lld", &a, &b, &lastSeen);
2111 + struct bgp_pgbgp_edge finder;
2114 + finder.lastSeen = lastSeen;
2115 + struct bgp_pgbgp_edge *hedge =
2116 + hash_get (pgbgp->edgeT, &finder, edge_hash_alloc);
2117 + hedge->lastSeen = finder.lastSeen;
2122 +edge_key_make (void *p)
2124 + struct bgp_pgbgp_edge *pe = p;
2125 + struct edge *e = &pe->e;
2126 + return (e->a << 16) + e->b;
2130 +edge_cmp (const void *arg1, const void *arg2)
2133 + const struct edge *e1 = &((const struct bgp_pgbgp_edge *) arg1)->e;
2134 + const struct edge *e2 = &((const struct bgp_pgbgp_edge *) arg2)->e;
2135 + if (e1->a == e2->a && e1->b == e2->b)
2141 +edge_hash_alloc (void *arg)
2143 + struct bgp_pgbgp_edge *hedge =
2144 + XCALLOC (MTYPE_BGP_PGBGP_EDGE, sizeof (struct bgp_pgbgp_edge));
2145 + struct bgp_pgbgp_edge *lookup = arg;
2146 + if (hedge == NULL)
2148 + hedge->e = lookup->e;
2154 +edge_gc_iterator (struct hash_backet *backet, time_t * time)
2156 + time_t t_now = *time;
2157 + struct bgp_pgbgp_edge *hedge = backet->data;
2159 + int collect = false;
2161 + // Collect if we haven't seen it in awhile
2162 + if (hedge->lastSeen + pgbgp->edge_hist_time <= t_now)
2165 + // Collect if it has just gotten out of anomaly stage
2166 + // but hasn't been in the RIB since the last GC
2167 + if (hedge->deprefUntil != 0 && hedge->deprefUntil < t_now)
2169 + if (hedge->lastSeen < pgbgp->lastgc)
2171 + hedge->deprefUntil = 0;
2176 + struct bgp_pgbgp_edge *ret = hash_release (pgbgp->edgeT, hedge);
2177 + assert (ret != NULL);
2178 + XFREE (MTYPE_BGP_PGBGP_EDGE, hedge);
2185 +edge_update_iterator (struct hash_backet *backet, void *v)
2187 + struct aspath *p = backet->data;
2188 + time_t t_now = time (NULL);
2194 + struct assegment *seg;
2195 + struct bgp_pgbgp_edge *hedge = NULL;
2196 + for (seg = p->segments; seg; seg = seg->next)
2198 + for (int i = 0; i < seg->length; i++)
2201 + cur.b = seg->as[i];
2207 + if (cur.a == cur.b)
2209 + // printf("%d -- %d\n", cur.a, cur.b);
2210 + struct bgp_pgbgp_edge finder;
2212 + hedge = hash_lookup (pgbgp->edgeT, &finder);
2216 + hedge->lastSeen = t_now;
2222 +bgp_pgbgp_garbageCollectEdges (struct bgp_table *table)
2224 + // Update the timings
2225 + hash_iterate (ashash,
2226 + (void (*)(struct hash_backet *, void *))
2227 + edge_update_iterator, NULL);
2229 + // Perform the collection
2230 + time_t t_now = time (NULL);
2231 + hash_iterate (pgbgp->edgeT,
2232 + (void (*)(struct hash_backet *, void *))
2233 + edge_gc_iterator, &t_now);
2238 +edge_clean_iterator (struct hash_backet *backet, void *a1)
2240 + struct bgp_pgbgp_edge *hedge = backet->data;
2241 + struct bgp_pgbgp_edge *ret = hash_release (pgbgp->edgeT, hedge);
2242 + assert (ret != NULL);
2243 + XFREE (MTYPE_BGP_PGBGP_EDGE, hedge);
2247 +bgp_pgbgp_cleanEdges (void)
2249 + if (pgbgp->edgeT != NULL)
2251 + hash_iterate (pgbgp->edgeT,
2252 + (void (*)(struct hash_backet *, void *))
2253 + edge_clean_iterator, NULL);
2254 + hash_free (pgbgp->edgeT);
2260 +bgp_pgbgp_logEdgeAnomaly (struct bgp_node *rn, struct attr *at,
2261 + struct edge *edge)
2264 + if (!pgbgp->anomalies)
2266 + FILE *file = fopen (pgbgp->anomalies, "a");
2271 + prefix2str (&rn->p, pre, sizeof (pre));
2273 + // EDGE | TIME | NEXTHOP | PREFIX | PATH | Edge.a | Edge.b
2275 + fprintf (file, "%d|%lld|%s|%s|%s|%d|%d\n", EDGE,
2276 + (long long int) time (NULL), inet_ntoa (at->nexthop), pre,
2277 + aspath_print (at->aspath), edge->a, edge->b);
2284 +bgp_pgbgp_updateEdge (struct bgp_pgbgp_hist *hist, struct bgp_info *binfo,
2285 + struct attr *at, struct bgp_node *rn, time_t t_now,
2289 + char first = true;
2290 + struct edge curEdge;
2295 + if (at->aspath == NULL)
2297 + struct assegment *seg = at->aspath->segments;
2300 + time_t max_depref = 0;
2301 + for (seg = at->aspath->segments; seg; seg = seg->next)
2303 + for (int i = 0; i < seg->length; i++)
2305 + curEdge.a = curEdge.b;
2306 + curEdge.b = seg->as[i];
2312 + if (curEdge.a == curEdge.b)
2315 + // We have an edge to consider
2316 + struct bgp_pgbgp_edge finder;
2317 + finder.e = curEdge;
2318 + struct bgp_pgbgp_edge *hedge =
2319 + hash_get (pgbgp->edgeT, &finder, edge_hash_alloc);
2321 + // Is this edge marked as suspicious?
2322 + if (hedge->deprefUntil > t_now)
2325 + // Have we seen the edge recently?
2326 + if (hedge->lastSeen + pgbgp->edge_hist_time > t_now)
2328 +#ifndef PGBGP_DEBUG
2329 + /* Are we within the initial grace period? */
2333 + // It must not be in recent history, depref edge for first time
2334 + hedge->deprefUntil = t_now + pgbgp->edge_sus_time;
2335 + bgp_pgbgp_logEdgeAnomaly (rn, at, &curEdge);
2339 + if (hedge->deprefUntil > max_depref)
2340 + max_depref = hedge->deprefUntil;
2342 + hedge->lastSeen = t_now;
2347 + SET_FLAG (binfo->flags, BGP_INFO_SUSPICIOUS_E);
2348 + if (!hist->pEdgeReuse)
2350 + struct bgp_pgbgp_reuse *r;
2352 + XCALLOC (MTYPE_BGP_PGBGP_REUSE, sizeof (struct bgp_pgbgp_reuse));
2353 + r->type = PGBGP_REUSE_EDGE;
2354 + r->deprefUntil = max_depref;
2355 + r->data.edge.rn = rn;
2356 + bgp_lock_node (rn);
2357 + pqueue_enqueue (r, pgbgp->reuse_q);
2358 + pgbgp->rq_size += 1;
2359 + hist->pEdgeReuse = r;
2361 + return BGP_INFO_SUSPICIOUS_E;
2368 +bgp_pgbgp_reuseEdge (struct bgp_pgbgp_r_edge data)
2371 + // Okay, go through all of the paths for the prefix
2372 + // and find the path that needs to be updated next and
2374 + time_t minMax = 0;
2375 + int numChanged = 0;
2376 + time_t t_now = time (NULL);
2378 + for (struct bgp_info * ri = data.rn->info; ri; ri = ri->next)
2380 + char first = true;
2381 + struct edge curEdge = { 0, 0 };
2382 + struct assegment *seg;
2383 + time_t max_depref = 0;
2385 + for (seg = ri->attr->aspath->segments; seg; seg = seg->next)
2387 + for (int i = 0; i < seg->length; i++)
2389 + curEdge.a = curEdge.b;
2390 + curEdge.b = seg->as[i];
2396 + struct bgp_pgbgp_edge finder;
2397 + finder.e = curEdge;
2398 + struct bgp_pgbgp_edge *hedge =
2399 + hash_lookup (pgbgp->edgeT, &finder);
2402 + // Is this edge suspicious?
2403 + if (hedge->deprefUntil > t_now
2404 + && hedge->deprefUntil > max_depref)
2405 + max_depref = hedge->deprefUntil;
2411 + if (!minMax || max_depref < minMax)
2412 + minMax = max_depref;
2416 + if (CHECK_FLAG (ri->flags, BGP_INFO_SUSPICIOUS_E))
2418 + UNSET_FLAG (ri->flags, BGP_INFO_SUSPICIOUS_E);
2423 + struct bgp_info *ri = data.rn->info;
2424 + if (numChanged > 0 && ri)
2425 + bgp_process (ri->peer->bgp, data.rn, data.rn->table->afi,
2426 + data.rn->table->safi);
2428 + struct bgp_pgbgp_hist *hist = data.rn->hist;
2429 + hist->pEdgeReuse = NULL;
2433 + struct bgp_pgbgp_reuse *r;
2434 + r = XCALLOC (MTYPE_BGP_PGBGP_REUSE, sizeof (struct bgp_pgbgp_reuse));
2435 + r->type = PGBGP_REUSE_EDGE;
2436 + r->deprefUntil = minMax;
2437 + r->data.edge.rn = data.rn;
2438 + pqueue_enqueue (r, pgbgp->reuse_q);
2439 + pgbgp->rq_size += 1;
2440 + hist->pEdgeReuse = r;
2444 + bgp_unlock_node (data.rn);
2450 +++ b/bgpd/bgp_pgbgp.h
2452 +/* BGP Pretty Good BGP
2453 + Copyright (C) 2008 University of New Mexico (Josh Karlin)
2455 +This file is part of GNU Zebra.
2457 +GNU Zebra is free software; you can redistribute it and/or modify it
2458 +under the terms of the GNU General Public License as published by the
2459 +Free Software Foundation; either version 2, or (at your option) any
2462 +GNU Zebra is distributed in the hope that it will be useful, but
2463 +WITHOUT ANY WARRANTY; without even the implied warranty of
2464 +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
2465 +General Public License for more details.
2467 +You should have received a copy of the GNU General Public License
2468 +along with GNU Zebra; see the file COPYING. If not, write to the Free
2469 +Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
2470 +02111-1307, USA. */
2472 +#ifndef _QUAGGA_BGP_PGBGP_H
2473 +#define _QUAGGA_BGP_PGBGP_H
2476 +#include "bgp_route.h"
2480 +#define SUBPREFIX 1
2483 +/* Global PGBGP data */
2484 +struct bgp_pgbgp_config
2486 + /* Depref time for a new origin AS */
2487 + time_t origin_sus_time;
2489 + /* Depref time for a new edge */
2490 + time_t edge_sus_time;
2492 + /* Depref time for a new sub-prefix */
2493 + time_t sub_sus_time;
2495 + /* Origin AS Mapping History Length */
2496 + time_t origin_hist_time;
2498 + /* Prefix Mapping History Length */
2499 + time_t prefix_hist_time;
2501 + /* Edge Mapping History Length */
2502 + time_t edge_hist_time;
2504 + /* Peer Mapping History Length */
2505 + time_t peer_hist_time;
2507 + /* The list of depreferenced routes */
2508 + struct pqueue *reuse_q;
2511 + /* Time that the last garbage collection (gc) took place */
2514 + /* History table */
2515 + // struct route_table *histT;
2517 + /* Edge Hash Table */
2518 + struct hash *edgeT;
2520 + /* File path for history storage */
2523 + /* File path for dump of anomalous routes */
2526 + /* The time that we last stored to disk */
2529 + /* The time that PGBGP started counting */
2532 + /* Last time each peer was seen */
2533 + struct bgp_pgbgp_peerTime *peerLast;
2538 +struct bgp_pgbgp_peerTime
2540 + struct bgp_pgbgp_peerTime *next;
2542 + union sockunion su;
2543 + time_t deprefUntil;
2553 + Avoid the neighbors for the less specific that told you about
2556 +struct bgp_pgbgp_avoid
2558 + struct bgp_pgbgp_avoid *next;
2559 + time_t avoidUntil;
2561 + struct bgp_node *sub;
2564 +/* A list of origin ASes for a path
2565 + Usually it's only one but if the last AS
2566 + in the path is an AS set, then the whole
2567 + set must be returned
2569 +struct bgp_pgbgp_pathSet
2576 + Avoid paths with suspicious origins
2578 +struct bgp_pgbgp_origin
2580 + struct bgp_pgbgp_origin *next;
2582 + time_t deprefUntil;
2587 + Ignore routes for this prefix
2589 +struct bgp_pgbgp_prefix
2592 + time_t ignoreUntil;
2593 + struct bgp_pgbgp_avoid *avoid;
2596 +struct bgp_pgbgp_edge
2599 + time_t deprefUntil;
2603 +struct bgp_pgbgp_hist
2605 + struct bgp_pgbgp_origin *o;
2606 + struct bgp_pgbgp_prefix *p;
2607 + struct bgp_pgbgp_reuse *pEdgeReuse;
2610 +struct bgp_pgbgp_r_origin
2613 + struct bgp_node *rn;
2616 +struct bgp_pgbgp_r_prefix
2618 + struct bgp_node *rn;
2619 + struct bgp_node *rnsuper;
2623 + This node contained a route with a bad edge, check
2624 + it again for bad edges in 24 hours
2626 +struct bgp_pgbgp_r_edge
2628 + struct bgp_node *rn;
2634 + struct bgp_pgbgp_r_origin origin;
2635 + struct bgp_pgbgp_r_prefix prefix;
2636 + struct bgp_pgbgp_r_edge edge;
2639 +struct bgp_pgbgp_reuse
2641 + union reuseTypes data;
2643 + time_t deprefUntil;
2646 +#define ANOMALOUS(V) \
2647 +(CHECK_FLAG(V, BGP_INFO_SUSPICIOUS_O | BGP_INFO_SUSPICIOUS_P \
2648 + | BGP_INFO_SUSPICIOUS_E | BGP_INFO_IGNORED_P))
2650 +#define PGBGP_REUSE_ORIGIN 0
2651 +#define PGBGP_REUSE_PREFIX 1
2652 +#define PGBGP_REUSE_EDGE 2
2654 +#define BGP_PGBGP_NONE 0
2655 +#define BGP_PGBGP_DEPREFFED 1
2658 +#define ORIGIN_ID 0
2659 +#define PREFIX_ID 1
2663 +/* Default timing values */
2664 +#define DEFAULT_ORIGIN_SUS (86400 * 1)
2665 +#define DEFAULT_EDGE_SUS (86400 * 1)
2666 +#define DEFAULT_SUB_SUS (86400 * 1)
2667 +#define DEFAULT_ORIGIN_HIST (86400 * 30)
2668 +#define DEFAULT_PREFIX_HIST (86400 * 10)
2669 +#define DEFAULT_EDGE_HIST (86400 * 60)
2670 +// Time between garbage collections
2671 +#define PGBGP_GC_DELTA (3600)
2672 +// Time between file stores
2673 +#define PGBGP_STORE_DELTA (28800)
2674 +// Time that a new peer's routes are not considered suspicious
2675 +#define PGBGP_PEER_GRACE (86400 * 1)
2679 +///////// PUBLIC PGBGP FUNCTIONS /////////
2683 + Enable PGBGP depreferencing / history tracking for this afi/safi
2686 + . ost: Depref. time of new prefix origins (in hours)
2687 + . est: Depref. time of new edges (in hours)
2688 + . sst: Depref. time of new sub-prefixes (in hours)
2689 + . oht: Storage time of known origins for prefixes (in days)
2690 + . pht: Storage time of known prefixes (in days)
2691 + . eht: Storage time of known edges (in days)
2692 + . storage: File to periodically store history in (can be /dev/null)
2693 + . anoms: File to store history of depreferenced routes (can be /dev/null)
2696 + It is important that the storage times are longer than the depreference times
2698 +extern int bgp_pgbgp_enable (struct bgp *, afi_t afi, safi_t safi, int ost,
2699 + int est, int sst, int oht, int pht, int eht,
2700 + const char *storage, const char *anoms);
2701 +extern int bgp_pgbgp_disable (struct bgp *, afi_t afi, safi_t safi);
2705 + Call on the event of an announcement update
2708 + bgp_info: The route
2709 + at: The new route's attributes
2711 +extern int bgp_pgbgp_update (struct bgp_info *, struct attr *at,
2712 + struct bgp_node *);
2715 + bgp_pgbgp_rib_updated:
2716 + Call upon discovery of a new best path (or lack thereof)
2718 + This is a special case function for smoothly handling sub-prefix hijacks.
2720 + It handles the following 2 events:
2722 + Event 1: An anomalous sub-prefix is ignored, but no best route for the super-prefix exists
2723 + Response: Announce the sub-prefix until the super-prefix comes back
2725 + Event 2: A super-prefix comes back to the RIB and its anomalous sub-prefix is in use
2726 + Response: Ignore the sub-prefix again
2729 + rn: The route node that a new best path was found for
2730 + old_best: The old best route (NULL if one did not exist)
2731 + new_best: The current best route (NULL if one does not exist)
2734 +bgp_pgbgp_rib_updated (struct bgp_node *rn, struct bgp_info *old_best,
2735 + struct bgp_info *new_best);
2738 --- a/bgpd/bgp_route.c
2739 +++ b/bgpd/bgp_route.c
2740 @@ -51,6 +51,7 @@ Software Foundation, Inc., 59 Temple Pla
2741 #include "bgpd/bgp_mplsvpn.h"
2742 #include "bgpd/bgp_nexthop.h"
2743 #include "bgpd/bgp_damp.h"
2744 +#include "bgpd/bgp_pgbgp.h"
2745 #include "bgpd/bgp_advertise.h"
2746 #include "bgpd/bgp_zebra.h"
2747 #include "bgpd/bgp_vty.h"
2748 @@ -339,12 +340,19 @@ bgp_info_cmp (struct bgp *bgp, struct bg
2753 /* 0. Null check. */
2759 + /* 0.5 PGBGP Depref. Check */
2760 + if (ANOMALOUS(exist->flags) && !ANOMALOUS(new->flags))
2762 + if (!ANOMALOUS(exist->flags) && ANOMALOUS(new->flags))
2765 /* 1. Weight check. */
2766 if (new->attr->extra)
2767 new_weight = new->attr->extra->weight;
2768 @@ -1583,6 +1591,10 @@ bgp_process_main (struct work_queue *wq,
2769 UNSET_FLAG (new_select->flags, BGP_INFO_MULTIPATH_CHG);
2772 + /* PGBGP needs to know about selected routes */
2773 + if (CHECK_FLAG (bgp->af_flags[afi][safi], BGP_CONFIG_PGBGP))
2774 + bgp_pgbgp_rib_updated(rn, old_select, new_select);
2777 /* Check each BGP peer. */
2778 for (ALL_LIST_ELEMENTS (bgp->peer, node, nnode, peer))
2779 @@ -1906,6 +1918,11 @@ bgp_update_rsclient (struct peer *rsclie
2780 /* If the update is implicit withdraw. */
2783 + /* Update PGBGP state, and mark the route as anomalous if necessary */
2784 + if (CHECK_FLAG (bgp->af_flags[afi][safi], BGP_CONFIG_PGBGP)
2785 + && peer_sort(peer) == BGP_PEER_EBGP)
2786 + bgp_pgbgp_update(ri, attr_new, rn);
2788 ri->uptime = bgp_clock ();
2790 /* Same attribute comes in. */
2791 @@ -2337,6 +2354,11 @@ bgp_update_main (struct peer *peer, stru
2792 /* Increment prefix */
2793 bgp_aggregate_increment (bgp, p, new, afi, safi);
2795 + /* Update PGBGP state, and mark the route as anomalous if necessary */
2796 + if (CHECK_FLAG (bgp->af_flags[afi][safi], BGP_CONFIG_PGBGP)
2797 + && peer_sort(peer) == BGP_PEER_EBGP)
2798 + bgp_pgbgp_update(new, attr_new, rn);
2800 /* Register new BGP information. */
2801 bgp_info_add (rn, new);
2803 @@ -5559,6 +5581,20 @@ enum bgp_display_type
2805 route_vty_short_status_out (struct vty *vty, struct bgp_info *binfo)
2807 + if (ANOMALOUS(binfo->flags))
2809 + vty_out(vty, "a[");
2810 + if (CHECK_FLAG(binfo->flags, BGP_INFO_SUSPICIOUS_P))
2811 + vty_out(vty, "i");
2812 + if (CHECK_FLAG(binfo->flags, BGP_INFO_SUSPICIOUS_O))
2813 + vty_out(vty, "p");
2814 + if (CHECK_FLAG(binfo->flags, BGP_INFO_SUSPICIOUS_E))
2815 + vty_out(vty, "e");
2816 + if (CHECK_FLAG(binfo->flags, BGP_INFO_IGNORED_P))
2817 + vty_out(vty, "s");
2818 + vty_out(vty, "] ");
2821 /* Route status display. */
2822 if (CHECK_FLAG (binfo->flags, BGP_INFO_REMOVED))
2824 @@ -6064,6 +6100,7 @@ route_vty_out_detail (struct vty *vty, s
2827 #define BGP_SHOW_SCODE_HEADER "Status codes: s suppressed, d damped, h history, * valid, > best, i - internal,%s r RIB-failure, S Stale, R Removed%s"
2828 +#define BGP_SHOW_PCODE_HEADER "Status code: a (anomalous) of: [p] prefix hijack, [s] sub-prefix hijack,%s [i] informant of sub-prefix [e] new edge%s"
2829 #define BGP_SHOW_OCODE_HEADER "Origin codes: i - IGP, e - EGP, ? - incomplete%s%s"
2830 #define BGP_SHOW_HEADER " Network Next Hop Metric LocPrf Weight Path%s"
2831 #define BGP_SHOW_DAMP_HEADER " Network From Reuse Path%s"
2832 @@ -6095,7 +6132,8 @@ enum bgp_show_type
2833 bgp_show_type_flap_route_map,
2834 bgp_show_type_flap_neighbor,
2835 bgp_show_type_dampend_paths,
2836 - bgp_show_type_damp_neighbor
2837 + bgp_show_type_damp_neighbor,
2838 + bgp_show_type_anomalous_paths
2842 @@ -6262,11 +6300,17 @@ bgp_show_table (struct vty *vty, struct
2843 || CHECK_FLAG (ri->flags, BGP_INFO_HISTORY))
2846 + if (type == bgp_show_type_anomalous_paths)
2848 + if (! ANOMALOUS(ri->flags))
2854 vty_out (vty, "BGP table version is 0, local router ID is %s%s", inet_ntoa (*router_id), VTY_NEWLINE);
2855 vty_out (vty, BGP_SHOW_SCODE_HEADER, VTY_NEWLINE, VTY_NEWLINE);
2856 + vty_out (vty, BGP_SHOW_PCODE_HEADER, VTY_NEWLINE, VTY_NEWLINE);
2857 vty_out (vty, BGP_SHOW_OCODE_HEADER, VTY_NEWLINE, VTY_NEWLINE);
2858 if (type == bgp_show_type_dampend_paths
2859 || type == bgp_show_type_damp_neighbor)
2860 @@ -6344,6 +6388,7 @@ bgp_show (struct vty *vty, struct bgp *b
2861 return bgp_show_table (vty, table, &bgp->router_id, type, output_arg);
2865 /* Header of detailed BGP route information */
2867 route_vty_out_detail_header (struct vty *vty, struct bgp *bgp,
2868 @@ -11904,6 +11949,64 @@ DEFUN (bgp_damp_set,
2869 half, reuse, suppress, max);
2872 +DEFUN (bgp_pgbgp_arg,
2873 + bgp_pgbgp_arg_cmd,
2874 + "bgp pgbgp <1-100> <1-100> <1-100> <1-365> <1-365> <1-365> WORD WORD",
2875 + "BGP Specific commands\n"
2876 + "Enable Pretty Good BGP\n"
2877 + "New origin depref time (in hours)\n"
2878 + "New edge depref time (in hours)\n"
2879 + "New sub-prefix depref time (in hours)\n"
2880 + "Origin history time (in days)\n"
2881 + "Prefix history time (in days)\n"
2882 + "Edge history time (in days)\n"
2883 + "Log file for history data\n"
2884 + "Log file of anomalies\n")
2888 + int ost = DEFAULT_ORIGIN_SUS;
2889 + int est = DEFAULT_EDGE_SUS;
2890 + int sst = DEFAULT_SUB_SUS;
2891 + int oht = DEFAULT_ORIGIN_HIST;
2892 + int pht = DEFAULT_PREFIX_HIST;
2893 + int eht = DEFAULT_EDGE_HIST;
2894 + const char* path = "/var/log/quagga/pgbgp_hist";
2895 + const char* anoms = "/var/log/quagga/pgbgp_anomalies";
2899 + VTY_GET_INTEGER("origin depref time", ost, argv[0]);
2900 + VTY_GET_INTEGER("edge depref time", est, argv[1]);
2901 + VTY_GET_INTEGER("sub-prefix depref time", sst, argv[2]);
2902 + VTY_GET_INTEGER("origin history time", oht, argv[3]);
2903 + VTY_GET_INTEGER("prefix history time", pht, argv[4]);
2904 + VTY_GET_INTEGER("edge history time", eht, argv[5]);
2910 + return bgp_pgbgp_enable(bgp, bgp_node_afi (vty), bgp_node_safi (vty),
2911 + ost, est, sst, oht, pht, eht, path, anoms);
2914 +ALIAS (bgp_pgbgp_arg,
2917 + "BGP specific commands\n"
2918 + "Enable Pretty Good BGP\n")
2920 +DEFUN (bgp_pgbgp_unset,
2921 + bgp_pgbgp_unset_cmd,
2923 + "BGP specific commands\n")
2927 + return bgp_pgbgp_disable (bgp, bgp_node_afi (vty), bgp_node_safi (vty));
2930 ALIAS (bgp_damp_set,
2932 "bgp dampening <1-45>",
2933 @@ -11953,6 +12056,19 @@ DEFUN (show_ip_bgp_dampened_paths,
2937 +DEFUN (show_ip_bgp_anomalous_paths,
2938 + show_ip_bgp_anomalous_paths_cmd,
2939 + "show ip bgp anomalous-paths",
2943 + "Display anomalous paths (less likely to be used)\n")
2945 + return bgp_show (vty, NULL, AFI_IP, SAFI_UNICAST, bgp_show_type_anomalous_paths,
2950 DEFUN (show_ip_bgp_flap_statistics,
2951 show_ip_bgp_flap_statistics_cmd,
2952 "show ip bgp flap-statistics",
2953 @@ -12479,6 +12595,7 @@ bgp_route_init (void)
2954 install_element (VIEW_NODE, &show_ip_bgp_neighbor_received_prefix_filter_cmd);
2955 install_element (VIEW_NODE, &show_ip_bgp_ipv4_neighbor_received_prefix_filter_cmd);
2956 install_element (VIEW_NODE, &show_ip_bgp_dampened_paths_cmd);
2957 + install_element (VIEW_NODE, &show_ip_bgp_anomalous_paths_cmd);
2958 install_element (VIEW_NODE, &show_ip_bgp_flap_statistics_cmd);
2959 install_element (VIEW_NODE, &show_ip_bgp_flap_address_cmd);
2960 install_element (VIEW_NODE, &show_ip_bgp_flap_prefix_cmd);
2961 @@ -12612,6 +12729,7 @@ bgp_route_init (void)
2962 install_element (ENABLE_NODE, &show_ip_bgp_neighbor_received_prefix_filter_cmd);
2963 install_element (ENABLE_NODE, &show_ip_bgp_ipv4_neighbor_received_prefix_filter_cmd);
2964 install_element (ENABLE_NODE, &show_ip_bgp_dampened_paths_cmd);
2965 + install_element (ENABLE_NODE, &show_ip_bgp_anomalous_paths_cmd);
2966 install_element (ENABLE_NODE, &show_ip_bgp_flap_statistics_cmd);
2967 install_element (ENABLE_NODE, &show_ip_bgp_flap_address_cmd);
2968 install_element (ENABLE_NODE, &show_ip_bgp_flap_prefix_cmd);
2969 @@ -13002,6 +13120,10 @@ bgp_route_init (void)
2970 install_element (BGP_IPV4_NODE, &bgp_damp_unset_cmd);
2971 install_element (BGP_IPV4_NODE, &bgp_damp_unset2_cmd);
2973 + install_element (BGP_NODE, &bgp_pgbgp_cmd);
2974 + install_element (BGP_NODE, &bgp_pgbgp_arg_cmd);
2975 + install_element (BGP_NODE, &bgp_pgbgp_unset_cmd);
2977 /* Deprecated AS-Pathlimit commands */
2978 install_element (BGP_NODE, &bgp_network_ttl_cmd);
2979 install_element (BGP_NODE, &bgp_network_mask_ttl_cmd);
2980 --- a/bgpd/bgp_route.h
2981 +++ b/bgpd/bgp_route.h
2984 /* BGP routing information base
2985 Copyright (C) 1996, 97, 98, 2000 Kunihiro Ishiguro
2987 @@ -68,7 +69,7 @@ struct bgp_info
2990 /* BGP information status. */
2993 #define BGP_INFO_IGP_CHANGED (1 << 0)
2994 #define BGP_INFO_DAMPED (1 << 1)
2995 #define BGP_INFO_HISTORY (1 << 2)
2996 @@ -82,6 +83,10 @@ struct bgp_info
2997 #define BGP_INFO_COUNTED (1 << 10)
2998 #define BGP_INFO_MULTIPATH (1 << 11)
2999 #define BGP_INFO_MULTIPATH_CHG (1 << 12)
3000 +#define BGP_INFO_SUSPICIOUS_O (1 << 13)
3001 +#define BGP_INFO_SUSPICIOUS_P (1 << 14)
3002 +#define BGP_INFO_IGNORED_P (1 << 15)
3003 +#define BGP_INFO_SUSPICIOUS_E (1 << 16)
3005 /* BGP route type. This can be static, RIP, OSPF, BGP etc. */
3007 @@ -126,7 +131,7 @@ struct bgp_static
3009 /* Flags which indicate a route is unuseable in some form */
3010 #define BGP_INFO_UNUSEABLE \
3011 - (BGP_INFO_HISTORY|BGP_INFO_DAMPED|BGP_INFO_REMOVED)
3012 + (BGP_INFO_HISTORY|BGP_INFO_DAMPED|BGP_INFO_REMOVED|BGP_INFO_IGNORED_P)
3013 /* Macro to check BGP information is alive or not. Sadly,
3014 * not equivalent to just checking previous, because of the
3015 * sense of the additional VALID flag.
3016 --- a/bgpd/bgp_table.h
3017 +++ b/bgpd/bgp_table.h
3018 @@ -65,6 +65,8 @@ struct bgp_node
3022 + struct bgp_pgbgp_hist *hist;
3025 #define BGP_NODE_PROCESS_SCHEDULED (1 << 0)
3029 @@ -123,6 +123,7 @@ struct bgp
3030 /* BGP Per AF flags */
3031 u_int16_t af_flags[AFI_MAX][SAFI_MAX];
3032 #define BGP_CONFIG_DAMPENING (1 << 0)
3033 +#define BGP_CONFIG_PGBGP (1 << 1)
3035 /* Static route configuration. */
3036 struct bgp_table *route[AFI_MAX][SAFI_MAX];
3039 @@ -166,6 +166,35 @@ hash_iterate (struct hash *hash,
3044 + Iterates until 0 is returned or until completion
3045 + Return: 1 if iteration completed
3046 + Return: 0 if iteration was interrupted
3050 +hash_iterate_until(struct hash *hash,
3051 + int (*func) (struct hash_backet *, void *), void *arg)
3054 + struct hash_backet *hb;
3055 + struct hash_backet *hbnext;
3058 + for (i = 0; i < hash->size; i++)
3059 + for (hb = hash->index[i]; hb; hb = hbnext)
3061 + /* get pointer to next hash backet here, in case (*func)
3062 + * decides to delete hb by calling hash_release
3064 + hbnext = hb->next;
3065 + ret = (*func) (hb, arg);
3072 /* Clean up hash. */
3074 hash_clean (struct hash *hash, void (*free_func) (void *))
3077 @@ -66,7 +66,8 @@ extern void *hash_release (struct hash *
3079 extern void hash_iterate (struct hash *,
3080 void (*) (struct hash_backet *, void *), void *);
3082 +extern int hash_iterate_until(struct hash *,
3083 + int (*) (struct hash_backet *, void *), void *);
3084 extern void hash_clean (struct hash *, void (*) (void *));
3085 extern void hash_free (struct hash *);
3087 --- a/lib/memtypes.c
3088 +++ b/lib/memtypes.c
3089 @@ -148,6 +148,15 @@ struct memory_list memory_list_bgp[] =
3090 { MTYPE_PEER_UPDATE_SOURCE, "BGP peer update interface" },
3091 { MTYPE_BGP_DAMP_INFO, "Dampening info" },
3092 { MTYPE_BGP_DAMP_ARRAY, "BGP Dampening array" },
3094 + { MTYPE_BGP_PGBGP_ORIGIN, "BGP PGBGP Origin AS Node" },
3095 + { MTYPE_BGP_PGBGP_PREFIX, "BGP PGBGP Prefix AS Node" },
3096 + { MTYPE_BGP_PGBGP_EDGE, "BGP PGBGP Edge Node" },
3097 + { MTYPE_BGP_PGBGP_REUSE, "BGP PGBGP Reuse Node" },
3098 + { MTYPE_BGP_PGBGP_HIST, "BGP PGBGP History Node" },
3099 + { MTYPE_BGP_PGBGP_AVOID, "BGP PGBGP Avoid Peer Node" },
3100 + { MTYPE_BGP_PGBGP_PEER, "BGP PGBGP Peer Timing" },
3102 { MTYPE_BGP_REGEXP, "BGP regexp" },
3103 { MTYPE_BGP_AGGREGATE, "BGP aggregate" },