net/quagga/patches/160-pgbgp.patch

   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
   5
   6 [bgp] Add support for Pretty-Good BGP
   7
   8 2008-7-7 Josh Karlin <karlinjf@cs.unm.edu>
   9
  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
  24 ---
  25
  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
  33 +       bgp_damp.c bgp_table.c bgp_advertise.c bgp_vty.c bgp_pgbgp.c
  34
  35  noinst_HEADERS = \
  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
  41 +       bgp_advertise.h bgp_snmp.h bgp_vty.h bgp_pgbgp.h
  42
  43  bgpd_SOURCES = bgp_main.c
  44  bgpd_LDADD = libbgp.a ../lib/libzebra.la @LIBCAP@ @LIBM@
  45 --- /dev/null
  46 +++ b/bgpd/bgp_pgbgp.c
  47 @@ -0,0 +1,2401 @@
  48 +/*
  49 +   BGP Pretty Good BGP
  50 +   Copyright (C) 2008 University of New Mexico (Josh Karlin)
  51 +
  52 +This file is part of GNU Zebra.
  53 +
  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
  57 +later version.
  58 +
  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.
  63 +
  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
  67 +02111-1307, USA.
  68 +*/
  69 +
  70 +/*
  71 +  Quagga based Pretty Good BGP:
  72 +
  73 +  Summary
  74 +  -------
  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.
  80 +
  81 +  What PGBGP can protect against: prefix hijacks, sub-prefix hijacks, and
  82 +  spoofed edges.
  83 +
  84 +  Further reading is available at http://cs.unm.edu/~karlinjf/pgbgp/
  85 +
  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.
  91 +
  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
  96 +
  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
  99 +               if possible
 100 +
 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
 108 +
 109 +
 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
 116 +           "hist" pointer.
 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.
 123 +
 124 +  Garbage Collection
 125 +  ------------------
 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.
 130 +
 131 +  What is removed) Objects that have not been seen in the RIB within a user-defined
 132 +                   time.
 133 +                  Suspicious objcets that are 24 hours old that have not been in the RIB
 134 +                  since the last collection.
 135 +
 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.
 141 +
 142 +*/
 143 +
 144 +
 145 +/*
 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
 150 +*/
 151 +
 152 +
 153 +/*
 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
 157 +*/
 158 +
 159 +/*
 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
 163 +    the sub-prefix)
 164 +
 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
 168 +
 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"
 173 +*/
 174 +
 175 +#include <zebra.h>
 176 +#include <math.h>
 177 +
 178 +#include "prefix.h"
 179 +#include "memory.h"
 180 +#include "command.h"
 181 +#include "log.h"
 182 +#include "pqueue.h"
 183 +#include "table.h"
 184 +#include "hash.h"
 185 +#include "str.h"
 186 +
 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"
 194 +
 195 +
 196 +#define true 1
 197 +#define false 0
 198 +
 199 +struct hash * ashash;
 200 +
 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);
 204 +
 205 +// Helper Functions
 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,
 212 +                            time_t t_now);
 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);
 219 +
 220 +// MOAS Functions
 221 +static void bgp_pgbgp_logOriginAnomaly (as_t asn, struct bgp_node *rn,
 222 +                                 struct attr *);
 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);
 229 +
 230 +
 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);
 239 +
 240 +
 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);
 252 +
 253 +
 254 +
 255 +// New Peer Detector Functions
 256 +static int bgp_pgbgp_updatePeer (struct bgp_info *binfo, time_t now);
 257 +
 258 +
 259 +/* --------------- Global Variables ------------------ */
 260 +struct bgp_pgbgp_config bgp_pgbgp_cfg;
 261 +struct bgp_pgbgp_config *pgbgp = &bgp_pgbgp_cfg;
 262 +/*! --------------- Global Variables ------------------ !*/
 263 +
 264 +/* --------------- VTY (others exist in bgp_route.c)  ------------------ */
 265 +
 266 +struct nsearch
 267 +{
 268 +  struct vty *pvty;
 269 +  time_t time;
 270 +  as_t asn;
 271 +};
 272 +
 273 +static void
 274 +edge_neighbor_iterator (struct hash_backet *backet, struct nsearch *pns)
 275 +{
 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)
 279 +    {
 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,
 283 +                 VTY_NEWLINE);
 284 +      else
 285 +        vty_out (pns->pvty, "Trusted: %d -- %d%s", hedge->e.a, hedge->e.b,
 286 +                 VTY_NEWLINE);
 287 +    }
 288 +}
 289 +
 290 +static int
 291 +bgp_pgbgp_stats_neighbors (struct vty *vty, afi_t afi, safi_t safi, as_t asn)
 292 +{
 293 +  struct nsearch ns;
 294 +  ns.pvty = vty;
 295 +  ns.time = time (NULL);
 296 +  ns.asn = asn;
 297 +
 298 +  hash_iterate (pgbgp->edgeT,
 299 +                (void (*)(struct hash_backet *, void *))
 300 +                edge_neighbor_iterator, &ns);
 301 +  return CMD_SUCCESS;
 302 +}
 303 +
 304 +static int
 305 +bgp_pgbgp_stats_origins (struct vty *vty, afi_t afi, safi_t safi,
 306 +                         const char *prefix)
 307 +{
 308 +  struct bgp *bgp;
 309 +  struct bgp_table *table;
 310 +  time_t t_now = time (NULL);
 311 +  bgp = bgp_get_default ();
 312 +  if (bgp == NULL)
 313 +    return CMD_WARNING;
 314 +  if (bgp->rib == NULL)
 315 +    return CMD_WARNING;
 316 +  table = bgp->rib[afi][safi];
 317 +  if (table == NULL)
 318 +    return CMD_WARNING;
 319 +
 320 +  struct prefix p;
 321 +  str2prefix (prefix, &p);
 322 +  struct bgp_node *rn = bgp_node_match (table, &p);
 323 +  vty_out (vty, "%s%s", prefix, VTY_NEWLINE);
 324 +  if (rn)
 325 +    {
 326 +      if (rn->hist)
 327 +        {
 328 +          for (struct bgp_pgbgp_origin * cur = rn->hist->o; cur != NULL;
 329 +               cur = cur->next)
 330 +            {
 331 +              if (cur->deprefUntil > t_now)
 332 +                vty_out (vty, "Untrusted Origin AS: %d%s", cur->originAS,
 333 +                         VTY_NEWLINE);
 334 +              else
 335 +                vty_out (vty, "Trusted Origin AS: %d%s", cur->originAS,
 336 +                         VTY_NEWLINE);
 337 +            }
 338 +        }
 339 +      bgp_unlock_node (rn);
 340 +    }
 341 +  return CMD_SUCCESS;
 342 +}
 343 +
 344 +static int
 345 +bgp_pgbgp_stats (struct vty *vty, afi_t afi, safi_t safi)
 346 +{
 347 +  struct bgp *bgp;
 348 +  struct bgp_table *table;
 349 +
 350 +
 351 +  bgp = bgp_get_default ();
 352 +  if (bgp == NULL)
 353 +    return CMD_WARNING;
 354 +  if (bgp->rib == NULL)
 355 +    return CMD_WARNING;
 356 +  table = bgp->rib[afi][safi];
 357 +  if (table == NULL)
 358 +    return CMD_WARNING;
 359 +
 360 +  //    bgp_pgbgp_store(table);
 361 +
 362 +  // Print out the number of anomalous routes
 363 +  int anomalous = 0;
 364 +  int routes = 0;
 365 +  int num_selected = 0;
 366 +  int num_origin = 0;
 367 +  int num_super = 0;
 368 +  int num_ignored = 0;
 369 +  int num_edge = 0;
 370 +
 371 +  for (struct bgp_node * rn = bgp_table_top (table); rn;
 372 +       rn = bgp_route_next (rn))
 373 +    {
 374 +      for (struct bgp_info * ri = rn->info; ri; ri = ri->next)
 375 +        {
 376 +          routes += 1;
 377 +          if (ANOMALOUS (ri->flags))
 378 +            {
 379 +              anomalous += 1;
 380 +              if (CHECK_FLAG (ri->flags, BGP_INFO_SELECTED))
 381 +                num_selected += 1;
 382 +
 383 +              if (CHECK_FLAG (ri->flags, BGP_INFO_SUSPICIOUS_O))
 384 +                num_origin += 1;
 385 +              if (CHECK_FLAG (ri->flags, BGP_INFO_SUSPICIOUS_E))
 386 +                num_edge += 1;
 387 +              if (CHECK_FLAG (ri->flags, BGP_INFO_SUSPICIOUS_P))
 388 +                num_super += 1;
 389 +              if (CHECK_FLAG (ri->flags, BGP_INFO_IGNORED_P))
 390 +                num_ignored += 1;
 391 +            }
 392 +        }
 393 +    }
 394 +
 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,
 397 +           VTY_NEWLINE);
 398 +  vty_out (vty, "%-30s: %10d%s", "Selected anomalous routes", num_selected,
 399 +           VTY_NEWLINE);
 400 +  vty_out (vty, "-----------------------------%s", VTY_NEWLINE);
 401 +  vty_out (vty, "%-30s: %10d%s", "Routes with anomalous origins", num_origin,
 402 +           VTY_NEWLINE);
 403 +  vty_out (vty, "%-30s: %10d%s", "Routes with anomalous edges", num_edge,
 404 +           VTY_NEWLINE);
 405 +  vty_out (vty, "%-30s: %10d%s", "Routes ignored for sub-prefix", num_ignored,
 406 +           VTY_NEWLINE);
 407 +  vty_out (vty, "%-30s: %10d%s", "Less specific routes to avoid", num_super,
 408 +           VTY_NEWLINE);
 409 +  /*
 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);
 419 +   */
 420 +  return CMD_SUCCESS;
 421 +}
 422 +
 423 +
 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")
 428 +{
 429 +  return bgp_pgbgp_stats (vty, AFI_IP, SAFI_UNICAST);
 430 +}
 431 +
 432 +DEFUN (show_ip_bgp_pgbgp_neighbors,
 433 +       show_ip_bgp_pgbgp_neighbors_cmd,
 434 +       "show ip bgp pgbgp neighbors WORD",
 435 +       SHOW_STR
 436 +       IP_STR
 437 +       BGP_STR
 438 +       "BGP pgbgp\n"
 439 +       "BGP pgbgp neighbors\n" "ASN whos neighbors should be displayed\n")
 440 +{
 441 +  return bgp_pgbgp_stats_neighbors (vty, AFI_IP, SAFI_UNICAST,
 442 +                                    atoi (argv[0]));
 443 +}
 444 +
 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",
 448 +       SHOW_STR
 449 +       IP_STR
 450 +       BGP_STR
 451 +       "BGP pgbgp\n"
 452 +       "BGP pgbgp neighbors\n" "Prefix to look up origin ASes of\n")
 453 +{
 454 +  return bgp_pgbgp_stats_origins (vty, AFI_IP, SAFI_UNICAST, argv[0]);
 455 +}
 456 +
 457 +
 458 +
 459 +
 460 +/*! --------------- VTY (others exist in bgp_route.c)  ------------------ !*/
 461 +
 462 +
 463 +
 464 +
 465 +
 466 +
 467 +
 468 +/* --------------- Helper Functions ------------------ */
 469 +/*
 470 +  If the origin hasn't been seen/verified lately, look for it in the RIB
 471 +*/
 472 +int
 473 +originInRIB (struct bgp_node *node, struct bgp_pgbgp_origin *origin)
 474 +{
 475 +  for (struct bgp_info * ri = node->info; ri; ri = ri->next)
 476 +    {
 477 +      struct bgp_pgbgp_pathSet pathOrigins;
 478 +      pathOrigins = bgp_pgbgp_pathOrigin (ri->attr->aspath);
 479 +      for (int i = 0; i < pathOrigins.length; ++i)
 480 +        {
 481 +          if (pathOrigins.ases[i] == origin->originAS)
 482 +            {
 483 +              return true;
 484 +            }
 485 +        }
 486 +    }
 487 +  return false;
 488 +}
 489 +
 490 +
 491 +/*
 492 +  If the prefix hasn't been seen/verified lately, look for it in the RIB
 493 +*/
 494 +int
 495 +prefixInRIB (struct bgp_node *node, struct bgp_pgbgp_prefix *prefix)
 496 +{
 497 +  if (node->info)
 498 +    return true;
 499 +  return false;
 500 +}
 501 +
 502 +static int
 503 +edge_inRIB_iterator (struct hash_backet *backet, struct bgp_pgbgp_edge *hedge)
 504 +{
 505 +  struct aspath *p = backet->data;
 506 +  char first = true;
 507 +  struct edge curEdge;
 508 +  curEdge.a = 0;
 509 +  curEdge.b = 0;
 510 +
 511 +  struct assegment *seg;
 512 +
 513 +  for (seg = p->segments; seg; seg = seg->next)
 514 +    {
 515 +      for (int i = 0; i < seg->length; i++)
 516 +        {
 517 +          curEdge.a = curEdge.b;
 518 +          curEdge.b = seg->as[i];
 519 +          if (first)
 520 +            {
 521 +              first = false;
 522 +              continue;
 523 +            }
 524 +          // Is this the edge we're looking for?
 525 +          if (curEdge.a == hedge->e.a && curEdge.b == hedge->e.b)
 526 +            {
 527 +              hedge->lastSeen = time (NULL);
 528 +              return false;
 529 +            }
 530 +        }
 531 +    }
 532 +
 533 +  return true;
 534 +}
 535 +
 536 +/*
 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
 539 +*/
 540 +int
 541 +edgeInRIB (struct bgp_pgbgp_edge *e)
 542 +{
 543 +  int completed;
 544 +  completed = hash_iterate_until (ashash,
 545 +                                  (int (*)(struct hash_backet *, void *))
 546 +                                  edge_inRIB_iterator, e);
 547 +  if (completed)
 548 +    return false;
 549 +
 550 +  return true;
 551 +}
 552 +
 553 +
 554 +
 555 +/*
 556 +  Return the selected route for the given route node
 557 + */
 558 +
 559 +struct bgp_info *
 560 +bgp_pgbgp_selected (struct bgp_node *node)
 561 +{
 562 +  for (struct bgp_info * ri = node->info; ri; ri = ri->next)
 563 +    {
 564 +      if (CHECK_FLAG (ri->flags, BGP_INFO_SELECTED))
 565 +        return ri;
 566 +    }
 567 +  return NULL;
 568 +}
 569 +
 570 +static int
 571 +reuse_cmp (void *node1, void *node2)
 572 +{
 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;
 578 +}
 579 +
 580 +int
 581 +bgp_pgbgp_pathLength (struct aspath *asp)
 582 +{
 583 +  struct assegment *seg;
 584 +  if ((asp == NULL) || (asp->segments == NULL))
 585 +    return 0;
 586 +  int count = 0;
 587 +  seg = asp->segments;
 588 +  while (seg->next != NULL)
 589 +    {
 590 +      count += seg->length;
 591 +      seg = seg->next;
 592 +    }
 593 +  return count;
 594 +}
 595 +
 596 +
 597 +
 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)
 602 +{
 603 +  struct assegment *seg, *last;
 604 +  struct bgp_pgbgp_pathSet tmp;
 605 +  tmp.length = 0;
 606 +  tmp.ases = NULL;
 607 +
 608 +  assert (asp != NULL && asp->segments != NULL);
 609 +
 610 +  /*    if ( (asp == NULL) || (asp->segments == NULL) )
 611 +     return tmp;
 612 +   */
 613 +  seg = asp->segments;
 614 +  last = NULL;
 615 +  while (seg->next != NULL)
 616 +    {
 617 +      if (seg->type != AS_SET && seg->type != AS_CONFED_SET)
 618 +        last = seg;
 619 +      seg = seg->next;
 620 +    }
 621 +
 622 +  if (seg->type == AS_SET || seg->type == AS_CONFED_SET)
 623 +    seg = last;
 624 +
 625 +  assert (seg);
 626 +  tmp.length = 1;
 627 +  tmp.ases = &seg->as[seg->length - 1];
 628 +
 629 +  /*
 630 +     if (seg->type == AS_SET || seg->type == AS_CONFED_SET)
 631 +     {
 632 +     tmp.length = seg->length;
 633 +     tmp.ases = seg->as;
 634 +     }
 635 +     else
 636 +     {
 637 +     tmp.length = 1;
 638 +     tmp.ases = &seg->as[seg->length - 1];
 639 +     }
 640 +   */
 641 +  assert (tmp.length >= 1);
 642 +  return tmp;
 643 +  //    return seg->as[seg->length-1];
 644 +}
 645 +
 646 +int
 647 +bgp_pgbgp_reuse (time_t t_now)
 648 +{
 649 +
 650 +  struct bgp_pgbgp_reuse *cur = NULL;
 651 +
 652 +  while (pgbgp->rq_size > 0)
 653 +    {
 654 +      cur = pqueue_dequeue (pgbgp->reuse_q);
 655 +      pgbgp->rq_size -= 1;
 656 +
 657 +      // Is the next item ready to be reused?
 658 +      if (t_now < cur->deprefUntil)
 659 +        {
 660 +          pqueue_enqueue (cur, pgbgp->reuse_q);
 661 +          pgbgp->rq_size += 1;
 662 +          break;
 663 +        }
 664 +
 665 +      // Okay, it needs to be reused now
 666 +      if (cur->type == PGBGP_REUSE_ORIGIN)
 667 +        bgp_pgbgp_reuseOrigin (cur->data.origin);
 668 +
 669 +      else if (cur->type == PGBGP_REUSE_PREFIX)
 670 +        bgp_pgbgp_reusePrefix (cur->data.prefix);
 671 +
 672 +      else if (cur->type == PGBGP_REUSE_EDGE)
 673 +        bgp_pgbgp_reuseEdge (cur->data.edge);
 674 +
 675 +
 676 +      XFREE (MTYPE_BGP_PGBGP_REUSE, cur);
 677 +    }
 678 +  return 0;
 679 +}
 680 +
 681 +/* Check bit of the prefix. */
 682 +static int
 683 +check_bit (u_char * prefix, u_char prefixlen)
 684 +{
 685 +  int offset;
 686 +  int shift;
 687 +  u_char *p = (u_char *) prefix;
 688 +
 689 +  assert (prefixlen <= 128);
 690 +
 691 +  offset = prefixlen / 8;
 692 +  shift = 7 - (prefixlen % 8);
 693 +
 694 +  return (p[offset] >> shift & 1);
 695 +}
 696 +
 697 +/*
 698 +  Find a super-net in the tree that's not currently anomalous if one exists
 699 +*/
 700 +struct bgp_node *
 701 +findSuper (struct bgp_table *table, struct prefix *p, time_t t_now)
 702 +{
 703 +  struct bgp_node *node;
 704 +  struct bgp_node *matched;
 705 +
 706 +  matched = NULL;
 707 +  node = table->top;
 708 +
 709 +  while (node && node->p.prefixlen < p->prefixlen &&
 710 +         prefix_match (&node->p, p))
 711 +    {
 712 +      // Node may not yet have its info set when reading in from pgbgp log files
 713 +      if (node->hist && node->p.prefixlen >= 8)
 714 +        {
 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)
 718 +            matched = node;
 719 +        }
 720 +      node = node->link[check_bit (&p->u.prefix, node->p.prefixlen)];
 721 +    }
 722 +  if (matched)
 723 +    return bgp_lock_node (matched);
 724 +  return NULL;
 725 +}
 726 +
 727 +
 728 +
 729 +
 730 +
 731 +/*! --------------- Helper Functions ------------------ !*/
 732 +
 733 +
 734 +
 735 +
 736 +
 737 +
 738 +
 739 +/* --------------- Public PGBGP Interface ------------------ */
 740 +int
 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)
 744 +{
 745 +
 746 +  if (CHECK_FLAG (bgp->af_flags[afi][safi], BGP_CONFIG_PGBGP))
 747 +    {
 748 +      if (pgbgp->storage && pgbgp->anomalies)
 749 +        {
 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)
 758 +
 759 +            return 0;
 760 +        }
 761 +    }
 762 +
 763 +  SET_FLAG (bgp->af_flags[afi][safi], BGP_CONFIG_PGBGP);
 764 +
 765 +#ifndef PGBGP_DEBUG
 766 +  time_t hour = 3600;
 767 +  time_t day = 86400;
 768 +#endif
 769 +#ifdef PGBGP_DEBUG
 770 +  time_t hour = 2;
 771 +  time_t day = 5;
 772 +#endif
 773 +
 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;
 781 +
 782 +  if (file != NULL)
 783 +    pgbgp->storage = strdup (file);
 784 +  else
 785 +    pgbgp->storage = NULL;
 786 +
 787 +  if (anoms != NULL)
 788 +    pgbgp->anomalies = strdup (anoms);
 789 +  else
 790 +    pgbgp->anomalies = NULL;
 791 +
 792 +
 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 ();
 807 +  return 0;
 808 +}
 809 +
 810 +int
 811 +bgp_pgbgp_disable (struct bgp *bgp, afi_t afi, safi_t safi)
 812 +{
 813 +  UNSET_FLAG (bgp->af_flags[afi][safi], BGP_CONFIG_PGBGP);
 814 +
 815 +  // Clean the tables
 816 +  if (bgp->rib[afi][safi] != NULL)
 817 +    bgp_pgbgp_clean (bgp->rib[afi][safi]);
 818 +
 819 +  bgp_pgbgp_cleanEdges ();
 820 +
 821 +  if (pgbgp->storage != NULL)
 822 +    free (pgbgp->storage);
 823 +
 824 +  if (pgbgp->anomalies != NULL)
 825 +    free (pgbgp->anomalies);
 826 +
 827 +  struct bgp_pgbgp_peerTime *pr = pgbgp->peerLast;
 828 +  while (pr)
 829 +    {
 830 +      struct bgp_pgbgp_peerTime *cur = pr;
 831 +      pr = pr->next;
 832 +      XFREE (MTYPE_BGP_PGBGP_PEER, cur);
 833 +    }
 834 +
 835 +  return 0;
 836 +}
 837 +
 838 +int
 839 +bgp_pgbgp_clean (struct bgp_table *table)
 840 +{
 841 +  struct bgp_pgbgp_reuse *rnode = NULL;
 842 +
 843 +  while (pgbgp->rq_size > 0)
 844 +    {
 845 +      rnode = (struct bgp_pgbgp_reuse *) pqueue_dequeue (pgbgp->reuse_q);
 846 +      pgbgp->rq_size -= 1;
 847 +      XFREE (MTYPE_BGP_PGBGP_REUSE, rnode);
 848 +    }
 849 +  pqueue_delete (pgbgp->reuse_q);
 850 +
 851 +  if (table == NULL)
 852 +    return 0;
 853 +
 854 +  // Clean the detectors
 855 +  bgp_pgbgp_cleanHistTable (table);
 856 +
 857 +  bgp_pgbgp_cleanEdges ();
 858 +
 859 +
 860 +  // Clean up the RIB nodes
 861 +  for (struct bgp_node * rn = bgp_table_top (table); rn;
 862 +       rn = bgp_route_next (rn))
 863 +    {
 864 +      int changed = 0;
 865 +      for (struct bgp_info * ri = rn->info; ri; ri = ri->next)
 866 +        {
 867 +          if (CHECK_FLAG (ri->flags, BGP_INFO_SUSPICIOUS_O
 868 +                          | BGP_INFO_SUSPICIOUS_P | BGP_INFO_SUSPICIOUS_E
 869 +                          | BGP_INFO_IGNORED_P))
 870 +            {
 871 +              changed = 1;
 872 +              UNSET_FLAG (ri->flags, BGP_INFO_SUSPICIOUS_O
 873 +                          | BGP_INFO_SUSPICIOUS_P | BGP_INFO_SUSPICIOUS_E
 874 +                          | BGP_INFO_IGNORED_P);
 875 +            }
 876 +        }
 877 +      if (changed && rn->info)
 878 +        {
 879 +          struct bgp_info *ri = rn->info;
 880 +          bgp_process (ri->peer->bgp, rn, rn->table->afi, rn->table->safi);
 881 +        }
 882 +    }
 883 +
 884 +  hash_free (pgbgp->edgeT);
 885 +  return 0;
 886 +}
 887 +
 888 +
 889 +int
 890 +bgp_pgbgp_gc (struct bgp_table *table)
 891 +{
 892 +  struct bgp *bgp = bgp_get_default ();
 893 +  if (!bgp)
 894 +    return 0;
 895 +
 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++)
 899 +      {
 900 +        if (!CHECK_FLAG (bgp->af_flags[afi][safi], BGP_CONFIG_PGBGP))
 901 +          continue;
 902 +        struct bgp_table *curTable = bgp->rib[afi][safi];
 903 +        if (!curTable)
 904 +          continue;
 905 +        bgp_pgbgp_garbageCollectHistTable (curTable);
 906 +      }
 907 +
 908 +  bgp_pgbgp_garbageCollectEdges (table);
 909 +
 910 +  return 0;
 911 +}
 912 +
 913 +int
 914 +bgp_pgbgp_restore (void)
 915 +{
 916 +
 917 +  if (pgbgp->storage == NULL)
 918 +    return 0;
 919 +  FILE *file = fopen (pgbgp->storage, "r");
 920 +  if (!file)
 921 +    return 0;
 922 +
 923 +  int type = 0;
 924 +  struct prefix p;
 925 +  struct bgp *bgp = bgp_get_default ();
 926 +  struct bgp_node *curNode = NULL;
 927 +
 928 +  // Get the log store time
 929 +  long long int writetime;
 930 +  fscanf (file, "%lld", &writetime);
 931 +  time_t swtime = writetime;
 932 +
 933 +  // If it's too old (more than 1 week old), start fresh
 934 +  if (time (NULL) - swtime > 86400 * 7)
 935 +    {
 936 +      fclose (file);
 937 +      return 0;
 938 +    }
 939 +
 940 +
 941 +  // Get the PGBGP init time
 942 +  long long int stime;
 943 +  fscanf (file, "%lld", &stime);
 944 +  pgbgp->startTime = stime;
 945 +
 946 +  while (fscanf (file, "%d", &type) != EOF)
 947 +    {
 948 +
 949 +      if (type == PREFIX_ID)
 950 +        {
 951 +          char pre[128];
 952 +          unsigned int afi;
 953 +          unsigned int safi;
 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);
 959 +
 960 +          // Create and lock the node
 961 +          curNode = bgp_node_get (curTable, &p);
 962 +          assert (curNode->hist == NULL);
 963 +
 964 +          //              bgp_lock_node(curNode);
 965 +
 966 +          curNode->hist =
 967 +            XCALLOC (MTYPE_BGP_PGBGP_HIST, sizeof (struct bgp_pgbgp_hist));
 968 +          assert (curNode->hist != NULL);
 969 +
 970 +          curNode->hist->p =
 971 +            XCALLOC (MTYPE_BGP_PGBGP_PREFIX,
 972 +                     sizeof (struct bgp_pgbgp_prefix));
 973 +          assert (curNode->hist->p != NULL);
 974 +
 975 +          curNode->hist->p->lastSeen = time;
 976 +        }
 977 +      else if (type == ORIGIN_ID)
 978 +        {
 979 +          unsigned int ASN;
 980 +          long long int time;
 981 +          fscanf (file, "%u %lld", &ASN, &time);
 982 +          struct bgp_pgbgp_origin *or = XCALLOC (MTYPE_BGP_PGBGP_ORIGIN,
 983 +                                                 sizeof (struct
 984 +                                                         bgp_pgbgp_origin));
 985 +          or->lastSeen = time;
 986 +          or->originAS = ASN;
 987 +          or->next = curNode->hist->o;
 988 +          curNode->hist->o = or;
 989 +        }
 990 +      else if (type == EDGE_ID)
 991 +        {
 992 +          bgp_pgbgp_restoreEdge (file);
 993 +        }
 994 +      else if (type == PEER_ID)
 995 +        {
 996 +          struct bgp_pgbgp_peerTime *pr;
 997 +          long long int time;
 998 +          union sockunion su;
 999 +          char szsu[128];
1000 +          fscanf (file, "%s %lld", szsu, &time);
1001 +          str2sockunion (szsu, &su);
1002 +          pr =
1003 +            XCALLOC (MTYPE_BGP_PGBGP_PEER,
1004 +                     sizeof (struct bgp_pgbgp_peerTime));
1005 +          pr->su = su;
1006 +          pr->lastSeen = time;
1007 +          pr->next = pgbgp->peerLast;
1008 +          pgbgp->peerLast = pr;
1009 +        }
1010 +    }
1011 +
1012 +  fclose (file);
1013 +  return 0;
1014 +}
1015 +
1016 +int
1017 +bgp_pgbgp_store (struct bgp_table *table)
1018 +{
1019 +  if (pgbgp->storage == NULL)
1020 +    return 0;
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");
1025 +
1026 +  if (!file)
1027 +    {
1028 +      free (tmpname);
1029 +      return 0;
1030 +    }
1031 +
1032 +  // Store the current time
1033 +  fprintf (file, "%lld\n", (long long int) time (NULL));
1034 +
1035 +  // Store the init time
1036 +  fprintf (file, "%lld\n", (long long int) pgbgp->startTime);
1037 +
1038 +  // Store the peer times
1039 +  for (struct bgp_pgbgp_peerTime * pr = pgbgp->peerLast; pr; pr = pr->next)
1040 +    {
1041 +      char strSock[128];
1042 +      sockunion2str (&pr->su, strSock, sizeof (strSock));
1043 +
1044 +      if (pr->deprefUntil < time (NULL))
1045 +        {
1046 +          fprintf (file, "%d %s %lld\n", PEER_ID, strSock,
1047 +                   (long long int) pr->lastSeen);
1048 +        }
1049 +    }
1050 +
1051 +  // Store the tables
1052 +  bgp_pgbgp_storeHistTable (table, file);
1053 +  bgp_pgbgp_storeEdges (table, file);
1054 +
1055 +  fclose (file);
1056 +
1057 +  rename (tmpname, pgbgp->storage);
1058 +
1059 +  free (tmpname);
1060 +  return 0;
1061 +}
1062 +
1063 +/*
1064 +  Check to see if we've seen the peer recently
1065 +  If not, then we need to return true and not delay routes
1066 +  for awhile
1067 +*/
1068 +int
1069 +bgp_pgbgp_updatePeer (struct bgp_info *binfo, time_t now)
1070 +{
1071 +  int status = false;
1072 +  // Find the peer
1073 +  struct bgp_pgbgp_peerTime *pr = pgbgp->peerLast;
1074 +  for (; pr; pr = pr->next)
1075 +    if (sockunion_same (&pr->su, &binfo->peer->su))
1076 +      break;
1077 +
1078 +  // If this is a new peer, create it
1079 +  if (pr == NULL)
1080 +    {
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;
1085 +
1086 +    }
1087 +  // Is it currently marked as new?
1088 +  if (pr->deprefUntil > now)
1089 +    goto UPPEER_DEPREF;
1090 +
1091 +  // Have we seen the peer recently?
1092 +  if (pr->lastSeen + pgbgp->peer_hist_time > now)
1093 +    goto UPPEER_CLEAN;
1094 +
1095 +  // It must not have been seen lately, depref it
1096 +  pr->deprefUntil = now + PGBGP_PEER_GRACE;
1097 +
1098 +
1099 +UPPEER_DEPREF:
1100 +  status = true;
1101 +
1102 +UPPEER_CLEAN:
1103 +  pr->lastSeen = now;
1104 +
1105 +  return status;
1106 +}
1107 +
1108 +
1109 +/*
1110 +  Returns whether or not the sub-prefix should be ignored
1111 +*/
1112 +int
1113 +bgp_pgbgp_shouldIgnore (struct bgp_node *super, struct bgp_info *selected)
1114 +{
1115 +  if (!selected || CHECK_FLAG (selected->flags, BGP_INFO_SUSPICIOUS_P))
1116 +    return false;
1117 +  return true;
1118 +}
1119 +
1120 +/*
1121 +  This is a special case function for smoothly handling sub-prefix hijacks.
1122 +
1123 +  It handles the following 2 events:
1124 +
1125 +  Event 1: The super-prefix of an anomalous prefix has a route through a non-anomalous
1126 +
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
1129 +
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
1132 + */
1133 +
1134 +
1135 +int
1136 +bgp_pgbgp_rib_updated (struct bgp_node *rn, struct bgp_info *old_best,
1137 +                       struct bgp_info *new_best)
1138 +{
1139 +  //  return 0;
1140 +  struct bgp_pgbgp_hist *hist = rn->hist;
1141 +  if (!hist)
1142 +    return 0;
1143 +  if (!hist->p)
1144 +    return 0;
1145 +  time_t t_now = time (NULL);
1146 +
1147 +  /*
1148 +     If we can't avoid the sub-prefix by routing to the super-prefix,
1149 +     then route as normal to the sub-prefix
1150 +   */
1151 +  if (!bgp_pgbgp_shouldIgnore (rn, new_best))
1152 +    {
1153 +      for (struct bgp_pgbgp_avoid * cur = hist->p->avoid; cur;
1154 +           cur = cur->next)
1155 +        {
1156 +          if (cur->avoidUntil > t_now)
1157 +            {
1158 +              int changed = false;
1159 +              for (struct bgp_info * ri = cur->sub->info; ri; ri = ri->next)
1160 +                {
1161 +                  if (CHECK_FLAG (ri->flags, BGP_INFO_IGNORED_P))
1162 +                    {
1163 +                      changed = true;
1164 +                      UNSET_FLAG (ri->flags, BGP_INFO_IGNORED_P);
1165 +                    }
1166 +                }
1167 +              if (changed)
1168 +                {
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);
1173 +
1174 +                }
1175 +
1176 +            }
1177 +        }
1178 +    }
1179 +
1180 +  /*
1181 +     If we can avoid the sub-prefix by routing to the super-prefix,
1182 +     then do so
1183 +   */
1184 +
1185 +  else
1186 +    {
1187 +      for (struct bgp_pgbgp_avoid * cur = hist->p->avoid; cur;
1188 +           cur = cur->next)
1189 +        {
1190 +          if (cur->avoidUntil > t_now)
1191 +            {
1192 +              int changed = false;
1193 +              for (struct bgp_info * ri = cur->sub->info; ri; ri = ri->next)
1194 +                {
1195 +                  if (!CHECK_FLAG (ri->flags, BGP_INFO_IGNORED_P))
1196 +                    {
1197 +                      changed = true;
1198 +                      SET_FLAG (ri->flags, BGP_INFO_IGNORED_P);
1199 +                    }
1200 +                }
1201 +              if (changed)
1202 +                {
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);
1207 +                }
1208 +            }
1209 +        }
1210 +    }
1211 +
1212 +  /*
1213 +     if (old_best && !new_best)
1214 +     {
1215 +     time_t t_now = time(NULL);
1216 +     for (struct bgp_pgbgp_avoid * cur = hist->p->avoid; cur;
1217 +     cur = cur->next)
1218 +     {
1219 +     if (cur->avoidUntil > t_now)
1220 +     {
1221 +     for (struct bgp_info * ri = cur->sub->info; ri; ri = ri->next)
1222 +     UNSET_FLAG (ri->flags, BGP_INFO_IGNORED_P);
1223 +
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);
1228 +     }
1229 +     }
1230 +     }
1231 +
1232 +
1233 +     else if (!old_best && new_best)
1234 +     {
1235 +     time_t t_now = time(NULL);
1236 +     for (struct bgp_pgbgp_avoid * av = hist->p->avoid; av; av = av->next)
1237 +     {
1238 +     struct bgp_info * ri = av->sub->info;
1239 +     if (av->avoidUntil > t_now && ri && !CHECK_FLAG(ri->flags, BGP_INFO_IGNORED_P))
1240 +     {
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);
1247 +
1248 +     }
1249 +     }
1250 +     }
1251 +   */
1252 +  return 0;
1253 +}
1254 +
1255 +int
1256 +bgp_pgbgp_update (struct bgp_info *binfo, struct attr *at,
1257 +                  struct bgp_node *rn)
1258 +{
1259 +  time_t t_now = time (NULL);
1260 +
1261 +  // Clean up the reuse list
1262 +  bgp_pgbgp_reuse (t_now);
1263 +
1264 +
1265 +  if (!rn->hist)
1266 +    {
1267 +      rn->hist =
1268 +        XCALLOC (MTYPE_BGP_PGBGP_HIST, sizeof (struct bgp_pgbgp_hist));
1269 +      // Get the PGBGP history lock on rn
1270 +      bgp_lock_node (rn);
1271 +    }
1272 +
1273 +  struct bgp_node *superhn = NULL;
1274 +
1275 +  // implicit lock from node_get
1276 +  superhn = findSuper (rn->table, &rn->p, t_now);
1277 +
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);
1282 +
1283 +  if (superhn != NULL)
1284 +    bgp_unlock_node (superhn);
1285 +
1286 +
1287 +
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)
1292 +    {
1293 +      bgp_pgbgp_gc (rn->table);
1294 +      pgbgp->lastgc = t_now;
1295 +    }
1296 +
1297 +  if (t_now >= pgbgp->lastStore + PGBGP_STORE_DELTA)
1298 +    {
1299 +      bgp_pgbgp_store (rn->table);
1300 +      pgbgp->lastStore = t_now;
1301 +    }
1302 +
1303 +
1304 +
1305 +  return 0;
1306 +}
1307 +
1308 +
1309 +
1310 +
1311 +/*! --------------- Public PGBGP Interface ------------------ !*/
1312 +
1313 +
1314 +
1315 +
1316 +
1317 +
1318 +
1319 +
1320 +
1321 +/* --------------- MOAS Detection ------------------ */
1322 +void
1323 +bgp_pgbgp_storeHistTable (struct bgp_table *table, FILE * file)
1324 +{
1325 +  time_t t_now;
1326 +  t_now = time (NULL);
1327 +
1328 +  struct bgp *bgp = bgp_get_default ();
1329 +  if (!bgp)
1330 +    return;
1331 +
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++)
1335 +      {
1336 +        if (!CHECK_FLAG (bgp->af_flags[afi][safi], BGP_CONFIG_PGBGP))
1337 +          continue;
1338 +        struct bgp_table *curTable = bgp->rib[afi][safi];
1339 +        if (!curTable)
1340 +          continue;
1341 +
1342 +        for (struct bgp_node * rn = bgp_table_top (curTable); rn;
1343 +             rn = bgp_route_next (rn))
1344 +          {
1345 +            struct bgp_pgbgp_hist *hist = rn->hist;
1346 +            if (hist == NULL)
1347 +              continue;
1348 +            char szPrefix[128];
1349 +            prefix2str (&rn->p, szPrefix, sizeof (szPrefix));
1350 +
1351 +
1352 +            struct bgp_pgbgp_prefix *pre = hist->p;
1353 +            if (pre && pre->ignoreUntil <= t_now)
1354 +              {
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);
1359 +                else
1360 +                  continue;
1361 +              }
1362 +            /* Need a prefix in the file before the origins,
1363 +               if no prefix.. skip origins */
1364 +            else
1365 +              continue;
1366 +
1367 +            for (struct bgp_pgbgp_origin * cur = hist->o; cur;
1368 +                 cur = cur->next)
1369 +              {
1370 +                if (cur->deprefUntil > t_now)
1371 +                  continue;
1372 +
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);
1376 +              }
1377 +
1378 +          }
1379 +      }
1380 +}
1381 +
1382 +
1383 +int
1384 +bgp_pgbgp_garbageCollectHistTable (struct bgp_table *table)
1385 +{
1386 +  time_t t_now;
1387 +  t_now = time (NULL);
1388 +
1389 +
1390 +  for (struct bgp_node * rn = bgp_table_top (table); rn;
1391 +       rn = bgp_route_next (rn))
1392 +    {
1393 +      int collect = false;
1394 +      struct bgp_pgbgp_hist *hist = rn->hist;
1395 +      if (hist == NULL)
1396 +        continue;
1397 +
1398 +      struct bgp_pgbgp_origin *cur = hist->o;
1399 +      struct bgp_pgbgp_prefix *pre = hist->p;
1400 +      struct bgp_pgbgp_origin *parent = NULL;
1401 +
1402 +      int used = false;
1403 +      if (cur != NULL || pre != NULL)
1404 +        used = true;
1405 +
1406 +      while (cur != NULL)
1407 +        {
1408 +          // Update the lastSeen time w/ originInRIB
1409 +          if (originInRIB (rn, cur))
1410 +            cur->lastSeen = t_now;
1411 +
1412 +          collect = false;
1413 +
1414 +          // Collect if old
1415 +          if (cur->lastSeen + pgbgp->origin_hist_time <= t_now)
1416 +            collect = true;
1417 +
1418 +          // Collect if anomaly just became okay but not seen since last collection
1419 +          if (cur->deprefUntil != 0 && cur->deprefUntil < t_now)
1420 +            {
1421 +              if (cur->lastSeen < pgbgp->lastgc)
1422 +                collect = true;
1423 +              cur->deprefUntil = 0;
1424 +            }
1425 +
1426 +          if (collect)
1427 +            {
1428 +              if (parent == NULL)
1429 +                hist->o = cur->next;
1430 +              else
1431 +                parent->next = cur->next;
1432 +
1433 +              // Delete cur, parent doesn't change
1434 +              struct bgp_pgbgp_origin *del = cur;
1435 +              cur = cur->next;
1436 +              XFREE (MTYPE_BGP_PGBGP_ORIGIN, del);
1437 +            }
1438 +          else
1439 +            {
1440 +              parent = cur;
1441 +              cur = cur->next;
1442 +            }
1443 +        }
1444 +
1445 +      // Update the lastSeen time w/ prefixInRIB
1446 +      if (pre && prefixInRIB (rn, pre))
1447 +        pre->lastSeen = t_now;
1448 +
1449 +      collect = false;
1450 +
1451 +      // Collect if old
1452 +      if (pre && pre->lastSeen + pgbgp->prefix_hist_time <= t_now)
1453 +        collect = true;
1454 +
1455 +      // Collect if anomaly just became okay but not seen since last collection
1456 +      if (pre && pre->ignoreUntil != 0 && pre->ignoreUntil < t_now)
1457 +        {
1458 +          if (pre->lastSeen < pgbgp->lastgc)
1459 +            collect = true;
1460 +          pre->ignoreUntil = 0;
1461 +        }
1462 +
1463 +      if (collect)
1464 +        {
1465 +          for (struct bgp_pgbgp_avoid * av = pre->avoid; av;)
1466 +            {
1467 +              struct bgp_pgbgp_avoid *del = av;
1468 +              av = av->next;
1469 +              bgp_unlock_node (del->sub);
1470 +              XFREE (MTYPE_BGP_PGBGP_AVOID, del);
1471 +            }
1472 +
1473 +          XFREE (MTYPE_BGP_PGBGP_PREFIX, pre);
1474 +          hist->p = NULL;
1475 +        }
1476 +
1477 +      // If the node isn't in use, remove it
1478 +      if (used && hist->o == NULL && hist->p == NULL)
1479 +        {
1480 +          XFREE (MTYPE_BGP_PGBGP_HIST, hist);
1481 +          rn->hist = NULL;
1482 +          bgp_unlock_node (rn);
1483 +        }
1484 +    }
1485 +
1486 +  return 0;
1487 +}
1488 +
1489 +void
1490 +bgp_pgbgp_cleanHistTable (struct bgp_table *table)
1491 +{
1492 +  // Clean up the RIB nodes
1493 +  for (struct bgp_node * rn = bgp_table_top (table); rn;
1494 +       rn = bgp_route_next (rn))
1495 +    {
1496 +      struct bgp_pgbgp_hist *hist = rn->hist;
1497 +      if (hist == NULL)
1498 +        continue;
1499 +
1500 +      if (hist->p)
1501 +        {
1502 +          for (struct bgp_pgbgp_avoid * av = hist->p->avoid; av;)
1503 +            {
1504 +              struct bgp_pgbgp_avoid *del = av;
1505 +              av = av->next;
1506 +              bgp_unlock_node (del->sub);
1507 +              XFREE (MTYPE_BGP_PGBGP_AVOID, del);
1508 +            }
1509 +          hist->p->avoid = NULL;
1510 +          XFREE (MTYPE_BGP_PGBGP_PREFIX, hist->p);
1511 +          hist->p = NULL;
1512 +        }
1513 +
1514 +      for (struct bgp_pgbgp_origin * cur = hist->o; cur;)
1515 +        {
1516 +          struct bgp_pgbgp_origin *next = cur->next;
1517 +          XFREE (MTYPE_BGP_PGBGP_ORIGIN, cur);
1518 +          cur = next;
1519 +        }
1520 +      hist->o = NULL;
1521 +      XFREE (MTYPE_BGP_PGBGP_HIST, hist);
1522 +      rn->hist = NULL;
1523 +      bgp_unlock_node (rn);
1524 +    }
1525 +}
1526 +
1527 +void
1528 +bgp_pgbgp_logOriginAnomaly (as_t asn, struct bgp_node *rn, struct attr *at)
1529 +{
1530 +  assert (pgbgp);
1531 +  if (!pgbgp->anomalies)
1532 +    return;
1533 +  FILE *file = fopen (pgbgp->anomalies, "a");
1534 +  if (!file)
1535 +    return;
1536 +
1537 +  char pre[256];
1538 +  prefix2str (&rn->p, pre, sizeof (pre));
1539 +
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);
1543 +
1544 +
1545 +  // Print the trusted origins
1546 +  assert (rn->hist);
1547 +  assert (rn->hist->o);
1548 +
1549 +  struct bgp_pgbgp_hist *hist = rn->hist;
1550 +
1551 +  for (struct bgp_pgbgp_origin * cur = hist->o; cur != NULL; cur = cur->next)
1552 +    {
1553 +      if (cur->deprefUntil > time (NULL))
1554 +        continue;
1555 +      fprintf (file, "%d", cur->originAS);
1556 +      if (cur->next != NULL)
1557 +        fprintf (file, " ");
1558 +    }
1559 +
1560 +  fprintf (file, " |%s\n", aspath_print (at->aspath));
1561 +  fclose (file);
1562 +}
1563 +
1564 +int
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,
1567 +                        int newPeer)
1568 +{
1569 +  struct bgp_pgbgp_pathSet pathOrigins;
1570 +  struct bgp_pgbgp_origin *pi = NULL;
1571 +  int status = 0;
1572 +  struct bgp_pgbgp_reuse *r;
1573 +  pathOrigins = bgp_pgbgp_pathOrigin (at->aspath);
1574 +
1575 +
1576 +  for (int i = 0; i < pathOrigins.length; i++)
1577 +    {
1578 +      as_t pathOrigin = pathOrigins.ases[i];
1579 +
1580 +      /* Is the Origin AS in the history? */
1581 +      for (pi = hist->o; pi; pi = pi->next)
1582 +        if (pi->originAS == pathOrigin)
1583 +          break;
1584 +
1585 +      if (pi == NULL)
1586 +        {
1587 +          pi =
1588 +            XCALLOC (MTYPE_BGP_PGBGP_ORIGIN,
1589 +                     sizeof (struct bgp_pgbgp_origin));
1590 +          pi->next = hist->o;
1591 +          pi->originAS = pathOrigin;
1592 +          hist->o = pi;
1593 +        }
1594 +
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)
1598 +        goto UPO_CLEAN;
1599 +
1600 +      /* Is the origin currently marked as suspicious? */
1601 +      if (pi->deprefUntil > t_now)
1602 +        goto UPO_DEPREF;
1603 +
1604 +      /* Have we seen the origin recently? */
1605 +      if (pi->lastSeen + pgbgp->origin_hist_time > t_now)
1606 +        goto UPO_CLEAN;
1607 +
1608 +#ifndef PGBGP_DEBUG
1609 +      /* Are we within the initial grace period? */
1610 +      if (newPeer)
1611 +        goto UPO_CLEAN;
1612 +#endif
1613 +
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);
1617 +
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;
1626 +
1627 +
1628 +    UPO_DEPREF:
1629 +      SET_FLAG (binfo->flags, BGP_INFO_SUSPICIOUS_O);
1630 +      status = BGP_INFO_SUSPICIOUS_O;
1631 +
1632 +    UPO_CLEAN:
1633 +      pi->lastSeen = t_now;
1634 +    }
1635 +  return status;
1636 +}
1637 +
1638 +int
1639 +bgp_pgbgp_reuseOrigin (struct bgp_pgbgp_r_origin data)
1640 +{
1641 +  struct bgp_info *ri;
1642 +  int numChanged = 0;
1643 +  time_t t_now = time (NULL);
1644 +  assert (data.rn->hist != NULL);
1645 +
1646 +  // Repreference paths for this prefix that are now okay
1647 +  for (ri = data.rn->info; ri; ri = ri->next)
1648 +    {
1649 +      if (CHECK_FLAG (ri->flags, BGP_INFO_SUSPICIOUS_O))
1650 +        {
1651 +          struct bgp_pgbgp_pathSet pathOrigins;
1652 +          pathOrigins = bgp_pgbgp_pathOrigin (ri->attr->aspath);
1653 +          int numOkay = 0;
1654 +          for (int i = 0; i < pathOrigins.length; i++)
1655 +            {
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)
1661 +                  break;
1662 +              /*
1663 +                 if (o == NULL) {
1664 +                 for(struct bgp_pgbgp_origin * z = data.rn->hist->o; z != NULL; z = z->next)
1665 +                 printf("Known origin: %d\n", z->originAS);
1666 +                 char pre[128];
1667 +                 prefix2str(&data.rn->p, pre, 128);
1668 +                 printf("%s : %s : %d\n", pre, ri->attr->aspath->str, pathOrigin);
1669 +                 }
1670 +               */
1671 +              assert (o != NULL);
1672 +
1673 +              if (o->deprefUntil <= t_now)
1674 +                numOkay += 1;
1675 +            }
1676 +          if (numOkay == pathOrigins.length)
1677 +            {
1678 +              UNSET_FLAG (ri->flags, BGP_INFO_SUSPICIOUS_O);
1679 +              numChanged += 1;
1680 +            }
1681 +        }
1682 +    }
1683 +
1684 +  ri = data.rn->info;
1685 +
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);
1690 +
1691 +
1692 +  /*
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;
1698 +
1699 +     // Find the origin AS node
1700 +     while(cur != NULL)
1701 +     {
1702 +     if (cur->originAS == data.originAS)
1703 +     {
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;
1710 +     else
1711 +     parent->next = cur->next;
1712 +
1713 +     XFREE(MTYPE_BGP_PGBGP_ORIGIN, cur);
1714 +     }
1715 +     break;
1716 +     }
1717 +     parent = cur;
1718 +     cur = cur->next;
1719 +     }
1720 +   */
1721 +
1722 +  bgp_unlock_node (data.rn);
1723 +  return 0;
1724 +}
1725 +
1726 +/*! --------------- MOAS Detection ------------------ !*/
1727 +
1728 +
1729 +/* --------------- Sub-Prefix Detection ------------------ */
1730 +
1731 +
1732 +
1733 +
1734 +
1735 +void
1736 +bgp_pgbgp_logSubprefixAnomaly (as_t asn, struct bgp_node *rn, struct attr *at,
1737 +                               struct bgp_node *super)
1738 +{
1739 +  assert (pgbgp);
1740 +  if (!pgbgp->anomalies)
1741 +    return;
1742 +  FILE *file = fopen (pgbgp->anomalies, "a");
1743 +  if (!file)
1744 +    return;
1745 +
1746 +  char pre[256];
1747 +  prefix2str (&rn->p, pre, sizeof (pre));
1748 +
1749 +  char superpre[256];
1750 +  prefix2str (&super->p, superpre, sizeof (superpre));
1751 +
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,
1755 +           superpre, asn);
1756 +
1757 +  // Print the trusted origins
1758 +  assert (super->hist);
1759 +  assert (super->hist->o);
1760 +
1761 +  struct bgp_pgbgp_hist *hist = super->hist;
1762 +
1763 +  for (struct bgp_pgbgp_origin * cur = hist->o; cur != NULL; cur = cur->next)
1764 +    {
1765 +      if (cur->deprefUntil > time (NULL))
1766 +        continue;
1767 +      fprintf (file, "%d", cur->originAS);
1768 +      if (cur->next != NULL)
1769 +        fprintf (file, " ");
1770 +    }
1771 +
1772 +  fprintf (file, " |%s\n", aspath_print (at->aspath));
1773 +  fclose (file);
1774 +}
1775 +
1776 +/*
1777 +  If the first path is a prefix of the second, then return true
1778 + */
1779 +
1780 +static int
1781 +bgp_pgbgp_pathIsPrefix(struct aspath *trusted, struct aspath * new)
1782 +{
1783 +  if (trusted == new)
1784 +    return true;
1785 +
1786 +  struct assegment *seg1 = trusted->segments;
1787 +  struct assegment *seg2 = new->segments;
1788 +
1789 +  while (seg1 || seg2)
1790 +    {
1791 +      if ((!seg1 && seg2) || (seg1 && !seg2))
1792 +       return false;
1793 +      if (seg1->type != seg2->type)
1794 +       return false;
1795 +
1796 +      if (seg1->length > seg2->length)
1797 +       return false;
1798 +
1799 +      for(int i = 0; i < seg1->length; i++)
1800 +       if (seg1->as[i] != seg2->as[i])
1801 +         return false;
1802 +
1803 +      seg1 = seg1->next;
1804 +      seg2 = seg2->next;
1805 +    }
1806 +
1807 +  return true;
1808 +}
1809 +
1810 +int
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,
1814 +                        int newPeer)
1815 +{
1816 +  struct bgp_pgbgp_prefix *pre = NULL;
1817 +  struct bgp_pgbgp_reuse *r = NULL;
1818 +  int status = 0;
1819 +  int changed = false;
1820 +
1821 +  pre = hist->p;
1822 +
1823 +
1824 +  /* Do we have this prefix? */
1825 +  if (pre == NULL)
1826 +    {
1827 +      pre =
1828 +        XCALLOC (MTYPE_BGP_PGBGP_PREFIX, sizeof (struct bgp_pgbgp_prefix));
1829 +      hist->p = pre;
1830 +    }
1831 +
1832 +  /* Is the prefix currently marked as suspicious? */
1833 +  if (pre->ignoreUntil > t_now)
1834 +    {
1835 +      goto UPP_IGNORE;
1836 +    }
1837 +
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)
1841 +    {
1842 +      if (binfo->peer->as == av->peerASN && av->avoidUntil > t_now)
1843 +        {
1844 +          SET_FLAG (binfo->flags, BGP_INFO_SUSPICIOUS_P);
1845 +          status = BGP_INFO_SUSPICIOUS_P;
1846 +          goto UPP_DONE;
1847 +        }
1848 +    }
1849 +
1850 +  /* Have we seen the prefix recently? */
1851 +  if (pre->lastSeen + pgbgp->prefix_hist_time > t_now)
1852 +    goto UPP_DONE;
1853 +
1854 +#ifndef PGBGP_DEBUG
1855 +  /* Are we within the initial grace period? */
1856 +  if (newPeer)
1857 +    goto UPP_DONE;
1858 +#endif
1859 +
1860 +  /* Is there a less specific *in recent history* that this could be hijacking? */
1861 +  if (supernode == NULL)
1862 +    goto UPP_DONE;
1863 +
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)
1867 +    {
1868 +      if (ri->peer->as == binfo->peer->as)
1869 +       {
1870 +         if (!ANOMALOUS(ri->flags) && bgp_pgbgp_pathIsPrefix(ri->attr->aspath, at->aspath))
1871 +             found = true;
1872 +         break;
1873 +       }
1874 +    }
1875 +
1876 +  if (found)
1877 +    goto UPP_DONE;
1878 +
1879 +  /*
1880 +     It's not in recent history, and there is a less specific currently in use
1881 +     Response:
1882 +     . Ignore this prefix
1883 +     . Make the less specific's route for this neighbor suspicious
1884 +   */
1885 +
1886 +
1887 +  pre->ignoreUntil = t_now + pgbgp->sub_sus_time;
1888 +
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);
1893 +
1894 +
1895 +
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;
1905 +
1906 +UPP_IGNORE:
1907 +  // Sanity check
1908 +  if (supernode == NULL)
1909 +    goto UPP_DONE;
1910 +
1911 +  /* Set the less specific's route from this peer to suspicious */
1912 +  changed = false;
1913 +
1914 +  for (struct bgp_info * ri = supernode->info; ri; ri = ri->next)
1915 +    {
1916 +      if (ri->peer->as == binfo->peer->as)
1917 +        {
1918 +          if (!CHECK_FLAG (ri->flags, BGP_INFO_SUSPICIOUS_P))
1919 +            {
1920 +              SET_FLAG (ri->flags, BGP_INFO_SUSPICIOUS_P);
1921 +              changed = true;
1922 +            }
1923 +          break;
1924 +        }
1925 +    }
1926 +
1927 +  // Make note of it in the less specific's history information
1928 +  found = false;
1929 +  struct bgp_pgbgp_hist *superhist = supernode->hist;
1930 +
1931 +  if (superhist && superhist->p)
1932 +    {
1933 +      for (struct bgp_pgbgp_avoid * av = superhist->p->avoid; av;
1934 +           av = av->next)
1935 +        {
1936 +          if (av->peerASN == binfo->peer->as)
1937 +            {
1938 +              if (av->avoidUntil < pre->ignoreUntil)
1939 +                av->avoidUntil = pre->ignoreUntil;
1940 +              found = true;
1941 +              break;
1942 +            }
1943 +        }
1944 +      if (!found)
1945 +        {
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;
1954 +        }
1955 +    }
1956 +  /*
1957 +     ignore this route unless the supernet's node
1958 +     is only a placeholder from loaded pgbgp data
1959 +   */
1960 +  if (bgp_pgbgp_shouldIgnore (supernode, bgp_pgbgp_selected (supernode)))
1961 +    {
1962 +      SET_FLAG (binfo->flags, BGP_INFO_IGNORED_P);
1963 +      status = BGP_INFO_IGNORED_P;
1964 +    }
1965 +  if (changed)
1966 +    {
1967 +      struct bgp_info *ri = supernode->info;
1968 +      bgp_process (ri->peer->bgp, supernode, supernode->table->afi,
1969 +                   supernode->table->safi);
1970 +    }
1971 +
1972 +UPP_DONE:
1973 +  pre->lastSeen = t_now;
1974 +
1975 +  return status;
1976 +}
1977 +
1978 +int
1979 +bgp_pgbgp_reusePrefix (struct bgp_pgbgp_r_prefix data)
1980 +{
1981 +  struct bgp_info *ri = NULL;
1982 +
1983 +  time_t t_now = time (NULL);
1984 +
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;
1989 +
1990 +  // Rerun the decision process
1991 +  if (ri != NULL)
1992 +    bgp_process (ri->peer->bgp, data.rn, data.rn->table->afi,
1993 +                 data.rn->table->safi);
1994 +
1995 +
1996 +  // Remove the avoid nodes from the super
1997 +  struct bgp_pgbgp_hist *superhist = data.rnsuper->hist;
1998 +  if (superhist != NULL && superhist->p != NULL)
1999 +    {
2000 +      struct bgp_pgbgp_avoid *parent = NULL;
2001 +      for (struct bgp_pgbgp_avoid * av = superhist->p->avoid; av;)
2002 +        {
2003 +          int numChanged = 0;
2004 +          if (av->avoidUntil <= t_now)
2005 +            {
2006 +              struct bgp_pgbgp_avoid *del = av;
2007 +              av = av->next;
2008 +              if (parent == NULL)
2009 +                superhist->p->avoid = av;
2010 +              else
2011 +                parent->next = av;
2012 +
2013 +              // Repreference any routes
2014 +              for (ri = data.rnsuper->info; ri; ri = ri->next)
2015 +                {
2016 +                  if (ri->peer->as == del->peerASN)
2017 +                    {
2018 +                      UNSET_FLAG (ri->flags, BGP_INFO_SUSPICIOUS_P);
2019 +                      numChanged += 1;
2020 +                      break;
2021 +                    }
2022 +                }
2023 +              ri = data.rnsuper->info;
2024 +
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);
2031 +            }
2032 +          else
2033 +            {
2034 +              parent = av;
2035 +              av = av->next;
2036 +            }
2037 +        }
2038 +    }
2039 +
2040 +  // Remove this prefix from the normal database
2041 +  // if it hasn't been seen in the RIB since the last
2042 +  // storage run
2043 +  /*
2044 +     struct bgp_pgbgp_hist *hist = rn->hist;
2045 +     struct bgp_pgbgp_prefix * pre = hist->p;
2046 +
2047 +     if (pre && pre->lastSeen < pgbgp->lastStore)
2048 +     {
2049 +     // Delete this node
2050 +     for(struct bgp_pgbgp_avoid * av = hist->p->avoid; av;)
2051 +     {
2052 +     struct bgp_pgbgp_avoid *del = av;
2053 +     av = av->next;
2054 +     bgp_unlock_node(del->sub);
2055 +     XFREE (MTYPE_BGP_PGBGP_AVOID, del);
2056 +     }
2057 +     XFREE(MTYPE_BGP_PGBGP_PREFIX, pre);
2058 +     hist->p = NULL;
2059 +     }
2060 +   */
2061 +  bgp_unlock_node (data.rn);
2062 +  bgp_unlock_node (data.rnsuper);
2063 +  return 0;
2064 +}
2065 +
2066 +/*! --------------- Sub-Prefix Detection ------------------ !*/
2067 +
2068 +
2069 +
2070 +
2071 +
2072 +/* --------------- Edge Detection ------------------ */
2073 +
2074 +static void
2075 +edge_store_clear_iterator (struct hash_backet *backet, void *file)
2076 +{
2077 +  struct bgp_pgbgp_edge *hedge = backet->data;
2078 +}
2079 +
2080 +static void
2081 +edge_store_iterator (struct hash_backet *backet, FILE * file)
2082 +{
2083 +  struct bgp_pgbgp_edge *hedge = backet->data;
2084 +  time_t t_now = time (NULL);
2085 +  if (hedge->deprefUntil > t_now)
2086 +    return;
2087 +  if (hedge->lastSeen + pgbgp->edge_hist_time > t_now)
2088 +    {
2089 +      fprintf (file, "%d %u %u %lld\n", EDGE_ID, hedge->e.a, hedge->e.b,
2090 +               (long long int) hedge->lastSeen);
2091 +    }
2092 +}
2093 +
2094 +
2095 +void
2096 +bgp_pgbgp_storeEdges (struct bgp_table *table, FILE * file)
2097 +{
2098 +  hash_iterate (pgbgp->edgeT,
2099 +                (void (*)(struct hash_backet *, void *))
2100 +                edge_store_iterator, file);
2101 +  return;
2102 +}
2103 +
2104 +
2105 +int
2106 +bgp_pgbgp_restoreEdge (FILE * file)
2107 +{
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;
2112 +  finder.e.a = a;
2113 +  finder.e.b = b;
2114 +  finder.lastSeen = lastSeen;
2115 +  struct bgp_pgbgp_edge *hedge =
2116 +    hash_get (pgbgp->edgeT, &finder, edge_hash_alloc);
2117 +  hedge->lastSeen = finder.lastSeen;
2118 +  return 0;
2119 +}
2120 +
2121 +unsigned int
2122 +edge_key_make (void *p)
2123 +{
2124 +  struct bgp_pgbgp_edge *pe = p;
2125 +  struct edge *e = &pe->e;
2126 +  return (e->a << 16) + e->b;
2127 +}
2128 +
2129 +static int
2130 +edge_cmp (const void *arg1, const void *arg2)
2131 +{
2132 +
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)
2136 +    return 1;
2137 +  return 0;
2138 +}
2139 +
2140 +static void *
2141 +edge_hash_alloc (void *arg)
2142 +{
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)
2147 +    return NULL;
2148 +  hedge->e = lookup->e;
2149 +  return hedge;
2150 +}
2151 +
2152 +
2153 +static void
2154 +edge_gc_iterator (struct hash_backet *backet, time_t * time)
2155 +{
2156 +  time_t t_now = *time;
2157 +  struct bgp_pgbgp_edge *hedge = backet->data;
2158 +
2159 +  int collect = false;
2160 +
2161 +  // Collect if we haven't seen it in awhile
2162 +  if (hedge->lastSeen + pgbgp->edge_hist_time <= t_now)
2163 +    collect = true;
2164 +
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)
2168 +    {
2169 +      if (hedge->lastSeen < pgbgp->lastgc)
2170 +        collect = true;
2171 +      hedge->deprefUntil = 0;
2172 +    }
2173 +
2174 +  if (collect)
2175 +    {
2176 +      struct bgp_pgbgp_edge *ret = hash_release (pgbgp->edgeT, hedge);
2177 +      assert (ret != NULL);
2178 +      XFREE (MTYPE_BGP_PGBGP_EDGE, hedge);
2179 +    }
2180 +}
2181 +
2182 +
2183 +
2184 +static void
2185 +edge_update_iterator (struct hash_backet *backet, void *v)
2186 +{
2187 +  struct aspath *p = backet->data;
2188 +  time_t t_now = time (NULL);
2189 +  int first = true;
2190 +
2191 +  struct edge cur;
2192 +  cur.a = 0;
2193 +  cur.b = 0;
2194 +  struct assegment *seg;
2195 +  struct bgp_pgbgp_edge *hedge = NULL;
2196 +  for (seg = p->segments; seg; seg = seg->next)
2197 +    {
2198 +      for (int i = 0; i < seg->length; i++)
2199 +        {
2200 +          cur.a = cur.b;
2201 +          cur.b = seg->as[i];
2202 +          if (first)
2203 +            {
2204 +              first = false;
2205 +              continue;
2206 +            }
2207 +          if (cur.a == cur.b)
2208 +            continue;
2209 +          //              printf("%d -- %d\n", cur.a, cur.b);
2210 +          struct bgp_pgbgp_edge finder;
2211 +          finder.e = cur;
2212 +          hedge = hash_lookup (pgbgp->edgeT, &finder);
2213 +
2214 +          if (!hedge)
2215 +            continue;
2216 +          hedge->lastSeen = t_now;
2217 +        }
2218 +    }
2219 +}
2220 +
2221 +int
2222 +bgp_pgbgp_garbageCollectEdges (struct bgp_table *table)
2223 +{
2224 +  // Update the timings
2225 +  hash_iterate (ashash,
2226 +                (void (*)(struct hash_backet *, void *))
2227 +                edge_update_iterator, NULL);
2228 +
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);
2234 +  return 0;
2235 +}
2236 +
2237 +static void
2238 +edge_clean_iterator (struct hash_backet *backet, void *a1)
2239 +{
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);
2244 +}
2245 +
2246 +static void
2247 +bgp_pgbgp_cleanEdges (void)
2248 +{
2249 +  if (pgbgp->edgeT != NULL)
2250 +    {
2251 +      hash_iterate (pgbgp->edgeT,
2252 +                    (void (*)(struct hash_backet *, void *))
2253 +                    edge_clean_iterator, NULL);
2254 +      hash_free (pgbgp->edgeT);
2255 +    }
2256 +  return;
2257 +}
2258 +
2259 +void
2260 +bgp_pgbgp_logEdgeAnomaly (struct bgp_node *rn, struct attr *at,
2261 +                          struct edge *edge)
2262 +{
2263 +  assert (pgbgp);
2264 +  if (!pgbgp->anomalies)
2265 +    return;
2266 +  FILE *file = fopen (pgbgp->anomalies, "a");
2267 +  if (!file)
2268 +    return;
2269 +
2270 +  char pre[256];
2271 +  prefix2str (&rn->p, pre, sizeof (pre));
2272 +
2273 +  // EDGE | TIME | NEXTHOP | PREFIX | PATH | Edge.a | Edge.b
2274 +
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);
2278 +
2279 +  fclose (file);
2280 +}
2281 +
2282 +
2283 +int
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,
2286 +                      int newPeer)
2287 +{
2288 +
2289 +  char first = true;
2290 +  struct edge curEdge;
2291 +  curEdge.a = 0;
2292 +  curEdge.b = 0;
2293 +
2294 +
2295 +  if (at->aspath == NULL)
2296 +    return 0;
2297 +  struct assegment *seg = at->aspath->segments;
2298 +  if (seg == NULL)
2299 +    return 0;
2300 +  time_t max_depref = 0;
2301 +  for (seg = at->aspath->segments; seg; seg = seg->next)
2302 +    {
2303 +      for (int i = 0; i < seg->length; i++)
2304 +        {
2305 +          curEdge.a = curEdge.b;
2306 +          curEdge.b = seg->as[i];
2307 +          if (first)
2308 +            {
2309 +              first = false;
2310 +              continue;
2311 +            }
2312 +          if (curEdge.a == curEdge.b)
2313 +            continue;
2314 +
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);
2320 +
2321 +          // Is this edge marked as suspicious?
2322 +          if (hedge->deprefUntil > t_now)
2323 +            goto UPE_DEPREF;
2324 +
2325 +          // Have we seen the edge recently?
2326 +          if (hedge->lastSeen + pgbgp->edge_hist_time > t_now)
2327 +            goto UPE_CLEAN;
2328 +#ifndef PGBGP_DEBUG
2329 +          /* Are we within the initial grace period? */
2330 +          if (newPeer)
2331 +            goto UPE_CLEAN;
2332 +#endif
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);
2336 +
2337 +
2338 +        UPE_DEPREF:
2339 +          if (hedge->deprefUntil > max_depref)
2340 +            max_depref = hedge->deprefUntil;
2341 +        UPE_CLEAN:
2342 +          hedge->lastSeen = t_now;
2343 +        }
2344 +    }
2345 +  if (max_depref)
2346 +    {
2347 +      SET_FLAG (binfo->flags, BGP_INFO_SUSPICIOUS_E);
2348 +      if (!hist->pEdgeReuse)
2349 +        {
2350 +          struct bgp_pgbgp_reuse *r;
2351 +          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;
2360 +        }
2361 +      return BGP_INFO_SUSPICIOUS_E;
2362 +    }
2363 +
2364 +  return 0;
2365 +}
2366 +
2367 +int
2368 +bgp_pgbgp_reuseEdge (struct bgp_pgbgp_r_edge data)
2369 +{
2370 +
2371 +  // Okay, go through all of the paths for the prefix
2372 +  // and find the path that needs to be updated next and
2373 +  // enqueue it
2374 +  time_t minMax = 0;
2375 +  int numChanged = 0;
2376 +  time_t t_now = time (NULL);
2377 +
2378 +  for (struct bgp_info * ri = data.rn->info; ri; ri = ri->next)
2379 +    {
2380 +      char first = true;
2381 +      struct edge curEdge = { 0, 0 };
2382 +      struct assegment *seg;
2383 +      time_t max_depref = 0;
2384 +
2385 +      for (seg = ri->attr->aspath->segments; seg; seg = seg->next)
2386 +        {
2387 +          for (int i = 0; i < seg->length; i++)
2388 +            {
2389 +              curEdge.a = curEdge.b;
2390 +              curEdge.b = seg->as[i];
2391 +              if (first)
2392 +                {
2393 +                  first = false;
2394 +                  continue;
2395 +                }
2396 +              struct bgp_pgbgp_edge finder;
2397 +              finder.e = curEdge;
2398 +              struct bgp_pgbgp_edge *hedge =
2399 +                hash_lookup (pgbgp->edgeT, &finder);
2400 +              if (!hedge)
2401 +                continue;
2402 +              // Is this edge suspicious?
2403 +              if (hedge->deprefUntil > t_now
2404 +                  && hedge->deprefUntil > max_depref)
2405 +                max_depref = hedge->deprefUntil;
2406 +            }
2407 +        }
2408 +
2409 +      if (max_depref)
2410 +        {
2411 +          if (!minMax || max_depref < minMax)
2412 +            minMax = max_depref;
2413 +        }
2414 +      else
2415 +        {
2416 +          if (CHECK_FLAG (ri->flags, BGP_INFO_SUSPICIOUS_E))
2417 +            {
2418 +              UNSET_FLAG (ri->flags, BGP_INFO_SUSPICIOUS_E);
2419 +              numChanged += 1;
2420 +            }
2421 +        }
2422 +    }
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);
2427 +
2428 +  struct bgp_pgbgp_hist *hist = data.rn->hist;
2429 +  hist->pEdgeReuse = NULL;
2430 +
2431 +  if (minMax)
2432 +    {
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;
2441 +    }
2442 +  else
2443 +    {
2444 +      bgp_unlock_node (data.rn);
2445 +    }
2446 +
2447 +  return 0;
2448 +}
2449 --- /dev/null
2450 +++ b/bgpd/bgp_pgbgp.h
2451 @@ -0,0 +1,286 @@
2452 +/* BGP Pretty Good BGP
2453 +   Copyright (C) 2008 University of New Mexico (Josh Karlin)
2454 +
2455 +This file is part of GNU Zebra.
2456 +
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
2460 +later version.
2461 +
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.
2466 +
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.  */
2471 +
2472 +#ifndef _QUAGGA_BGP_PGBGP_H
2473 +#define _QUAGGA_BGP_PGBGP_H
2474 +
2475 +#include "bgpd.h"
2476 +#include "bgp_route.h"
2477 +#include "table.h"
2478 +
2479 +#define MOAS 0
2480 +#define SUBPREFIX 1
2481 +#define EDGE 2
2482 +
2483 +/* Global PGBGP data */
2484 +struct bgp_pgbgp_config
2485 +{
2486 +  /* Depref time for a new origin AS */
2487 +  time_t origin_sus_time;
2488 +
2489 +  /* Depref time for a new edge */
2490 +  time_t edge_sus_time;
2491 +
2492 +  /* Depref time for a new sub-prefix */
2493 +  time_t sub_sus_time;
2494 +
2495 +  /* Origin AS Mapping History Length */
2496 +  time_t origin_hist_time;
2497 +
2498 +  /* Prefix Mapping History Length */
2499 +  time_t prefix_hist_time;
2500 +
2501 +  /* Edge Mapping History Length */
2502 +  time_t edge_hist_time;
2503 +
2504 +  /* Peer Mapping History Length */
2505 +  time_t peer_hist_time;
2506 +
2507 +  /* The list of depreferenced routes */
2508 +  struct pqueue *reuse_q;
2509 +  int rq_size;
2510 +
2511 +  /* Time that the last garbage collection (gc) took place */
2512 +  time_t lastgc;
2513 +
2514 +  /* History table */
2515 +  //    struct route_table *histT;
2516 +
2517 +  /* Edge Hash Table */
2518 +  struct hash *edgeT;
2519 +
2520 +  /* File path for history storage */
2521 +  char *storage;
2522 +
2523 +  /* File path for dump of anomalous routes */
2524 +  char *anomalies;
2525 +
2526 +  /* The time that we last stored to disk */
2527 +  time_t lastStore;
2528 +
2529 +  /* The time that PGBGP started counting */
2530 +  time_t startTime;
2531 +
2532 +  /* Last time each peer was seen */
2533 +  struct bgp_pgbgp_peerTime *peerLast;
2534 +
2535 +};
2536 +
2537 +
2538 +struct bgp_pgbgp_peerTime
2539 +{
2540 +  struct bgp_pgbgp_peerTime *next;
2541 +  time_t lastSeen;
2542 +  union sockunion su;
2543 +  time_t deprefUntil;
2544 +};
2545 +
2546 +struct edge
2547 +{
2548 +  as_t a;
2549 +  as_t b;
2550 +};
2551 +
2552 +/*
2553 +  Avoid the neighbors for the less specific that told you about
2554 +  the more specific
2555 + */
2556 +struct bgp_pgbgp_avoid
2557 +{
2558 +  struct bgp_pgbgp_avoid *next;
2559 +  time_t avoidUntil;
2560 +  as_t peerASN;
2561 +  struct bgp_node *sub;
2562 +};
2563 +
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
2568 +*/
2569 +struct bgp_pgbgp_pathSet
2570 +{
2571 +  int length;
2572 +  as_t *ases;
2573 +};
2574 +
2575 +/*
2576 +  Avoid paths with suspicious origins
2577 + */
2578 +struct bgp_pgbgp_origin
2579 +{
2580 +  struct bgp_pgbgp_origin *next;
2581 +  time_t lastSeen;
2582 +  time_t deprefUntil;
2583 +  as_t originAS;
2584 +};
2585 +
2586 +/*
2587 +  Ignore routes for this prefix
2588 + */
2589 +struct bgp_pgbgp_prefix
2590 +{
2591 +  time_t lastSeen;
2592 +  time_t ignoreUntil;
2593 +  struct bgp_pgbgp_avoid *avoid;
2594 +};
2595 +
2596 +struct bgp_pgbgp_edge
2597 +{
2598 +  time_t lastSeen;
2599 +  time_t deprefUntil;
2600 +  struct edge e;
2601 +};
2602 +
2603 +struct bgp_pgbgp_hist
2604 +{
2605 +  struct bgp_pgbgp_origin *o;
2606 +  struct bgp_pgbgp_prefix *p;
2607 +  struct bgp_pgbgp_reuse *pEdgeReuse;
2608 +};
2609 +
2610 +struct bgp_pgbgp_r_origin
2611 +{
2612 +  as_t originAS;
2613 +  struct bgp_node *rn;
2614 +};
2615 +
2616 +struct bgp_pgbgp_r_prefix
2617 +{
2618 +  struct bgp_node *rn;
2619 +  struct bgp_node *rnsuper;
2620 +};
2621 +
2622 +/*
2623 +  This node contained a route with a bad edge, check
2624 +  it again for bad edges in 24 hours
2625 +*/
2626 +struct bgp_pgbgp_r_edge
2627 +{
2628 +  struct bgp_node *rn;
2629 +};
2630 +
2631 +
2632 +union reuseTypes
2633 +{
2634 +  struct bgp_pgbgp_r_origin origin;
2635 +  struct bgp_pgbgp_r_prefix prefix;
2636 +  struct bgp_pgbgp_r_edge edge;
2637 +};
2638 +
2639 +struct bgp_pgbgp_reuse
2640 +{
2641 +  union reuseTypes data;
2642 +  short type;
2643 +  time_t deprefUntil;
2644 +};
2645 +
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))
2649 +
2650 +#define PGBGP_REUSE_ORIGIN 0
2651 +#define PGBGP_REUSE_PREFIX 1
2652 +#define PGBGP_REUSE_EDGE 2
2653 +
2654 +#define BGP_PGBGP_NONE      0
2655 +#define BGP_PGBGP_DEPREFFED 1
2656 +
2657 +// For storage
2658 +#define ORIGIN_ID 0
2659 +#define PREFIX_ID 1
2660 +#define EDGE_ID 2
2661 +#define PEER_ID 3
2662 +
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)
2676 +
2677 +
2678 +
2679 +///////// PUBLIC PGBGP FUNCTIONS /////////
2680 +
2681 +/*
2682 +  bgp_pgbgp_enable:
2683 +  Enable PGBGP depreferencing / history tracking for this afi/safi
2684 +
2685 +  Arguments:
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)
2694 +
2695 +  Caution:
2696 +  It is important that the storage times are longer than the depreference times
2697 +*/
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);
2702 +
2703 +/*
2704 +  bgp_pgbgp_update:
2705 +  Call on the event of an announcement update
2706 +
2707 +  Arguments:
2708 +  bgp_info: The route
2709 +  at: The new route's attributes
2710 +*/
2711 +extern int bgp_pgbgp_update (struct bgp_info *, struct attr *at,
2712 +                             struct bgp_node *);
2713 +
2714 +/*
2715 +  bgp_pgbgp_rib_updated:
2716 +  Call upon discovery of a new best path (or lack thereof)
2717 +
2718 +  This is a special case function for smoothly handling sub-prefix hijacks.
2719 +
2720 +  It handles the following 2 events:
2721 +
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
2724 +
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
2727 +
2728 +  Arguments:
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)
2732 + */
2733 +extern int
2734 +bgp_pgbgp_rib_updated (struct bgp_node *rn, struct bgp_info *old_best,
2735 +                       struct bgp_info *new_best);
2736 +
2737 +#endif
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 @@ -332,12 +333,19 @@ bgp_info_cmp (struct bgp *bgp, struct bg
2749    int confed_as_route = 0;
2750    int ret;
2751
2752 +
2753    /* 0. Null check. */
2754    if (new == NULL)
2755      return 0;
2756    if (exist == NULL)
2757      return 1;
2758
2759 +  /* 0.5 PGBGP Depref. Check */
2760 +  if (ANOMALOUS(exist->flags) && !ANOMALOUS(new->flags))
2761 +    return 1;
2762 +  if (!ANOMALOUS(exist->flags) && ANOMALOUS(new->flags))
2763 +    return 0;
2764 +
2765    /* 1. Weight check. */
2766    if (new->attr->extra)
2767      new_weight = new->attr->extra->weight;
2768 @@ -1508,6 +1516,10 @@ bgp_process_main (struct work_queue *wq,
2769        bgp_info_unset_flag (rn, new_select, BGP_INFO_ATTR_CHANGED);
2770      }
2771
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);
2775 +
2776
2777    /* Check each BGP peer. */
2778    for (ALL_LIST_ELEMENTS (bgp->peer, node, nnode, peer))
2779 @@ -1831,6 +1843,11 @@ bgp_update_rsclient (struct peer *rsclie
2780    /* If the update is implicit withdraw. */
2781    if (ri)
2782      {
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);
2787 +
2788        ri->uptime = bgp_clock ();
2789
2790        /* Same attribute comes in. */
2791 @@ -2262,6 +2279,11 @@ bgp_update_main (struct peer *peer, stru
2792    /* Increment prefix */
2793    bgp_aggregate_increment (bgp, p, new, afi, safi);
2794
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);
2799 +
2800    /* Register new BGP information. */
2801    bgp_info_add (rn, new);
2802
2803 @@ -5474,6 +5496,20 @@ enum bgp_display_type
2804  static void
2805  route_vty_short_status_out (struct vty *vty, struct bgp_info *binfo)
2806  {
2807 +  if (ANOMALOUS(binfo->flags))
2808 +    {
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, "] ");
2819 +    }
2820 +
2821   /* Route status display. */
2822    if (CHECK_FLAG (binfo->flags, BGP_INFO_REMOVED))
2823      vty_out (vty, "R");
2824 @@ -5974,6 +6010,7 @@ route_vty_out_detail (struct vty *vty, s
2825  }
2826  \f
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 @@ -6005,7 +6042,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
2839  };
2840
2841  static int
2842 @@ -6172,11 +6210,17 @@ bgp_show_table (struct vty *vty, struct
2843                     || CHECK_FLAG (ri->flags, BGP_INFO_HISTORY))
2844                   continue;
2845               }
2846 +           if (type == bgp_show_type_anomalous_paths)
2847 +             {
2848 +               if (! ANOMALOUS(ri->flags))
2849 +                 continue;
2850 +             }
2851
2852             if (header)
2853               {
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 @@ -6254,6 +6298,7 @@ bgp_show (struct vty *vty, struct bgp *b
2861    return bgp_show_table (vty, table, &bgp->router_id, type, output_arg);
2862  }
2863
2864 +
2865  /* Header of detailed BGP route information */
2866  static void
2867  route_vty_out_detail_header (struct vty *vty, struct bgp *bgp,
2868 @@ -11823,6 +11868,64 @@ DEFUN (bgp_damp_set,
2869                           half, reuse, suppress, max);
2870  }
2871
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")
2885 +{
2886 +  struct bgp *bgp;
2887 +
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";
2896 +
2897 + if (argc == 8)
2898 +    {
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]);
2905 +      path = argv[6];
2906 +      anoms = argv[7];
2907 +    }
2908 +
2909 +  bgp = vty->index;
2910 +  return bgp_pgbgp_enable(bgp, bgp_node_afi (vty), bgp_node_safi (vty),
2911 +                         ost, est, sst, oht, pht, eht, path, anoms);
2912 +}
2913 +
2914 +ALIAS (bgp_pgbgp_arg,
2915 +       bgp_pgbgp_cmd,
2916 +       "bgp pgbgp",
2917 +       "BGP specific commands\n"
2918 +       "Enable Pretty Good BGP\n")
2919 +
2920 +DEFUN (bgp_pgbgp_unset,
2921 +       bgp_pgbgp_unset_cmd,
2922 +       "no bgp pgbgp\n",
2923 +       "BGP specific commands\n")
2924 +{
2925 +  struct bgp *bgp;
2926 +  bgp = vty->index;
2927 +  return bgp_pgbgp_disable (bgp, bgp_node_afi (vty), bgp_node_safi (vty));
2928 +}
2929 +
2930  ALIAS (bgp_damp_set,
2931         bgp_damp_set2_cmd,
2932         "bgp dampening <1-45>",
2933 @@ -11872,6 +11975,19 @@ DEFUN (show_ip_bgp_dampened_paths,
2934                     NULL);
2935  }
2936
2937 +DEFUN (show_ip_bgp_anomalous_paths,
2938 +       show_ip_bgp_anomalous_paths_cmd,
2939 +       "show ip bgp anomalous-paths",
2940 +       SHOW_STR
2941 +       IP_STR
2942 +       BGP_STR
2943 +       "Display anomalous paths (less likely to be used)\n")
2944 +{
2945 +  return bgp_show (vty, NULL, AFI_IP, SAFI_UNICAST, bgp_show_type_anomalous_paths,
2946 +                  NULL);
2947 +}
2948 +
2949 +
2950  DEFUN (show_ip_bgp_flap_statistics,
2951         show_ip_bgp_flap_statistics_cmd,
2952         "show ip bgp flap-statistics",
2953 @@ -12398,6 +12514,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 @@ -12531,6 +12648,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 @@ -12918,6 +13036,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);
2972
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);
2976 +
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
2982 @@ -1,3 +1,4 @@
2983 +
2984  /* BGP routing information base
2985     Copyright (C) 1996, 97, 98, 2000 Kunihiro Ishiguro
2986
2987 @@ -76,6 +77,10 @@ struct bgp_info
2988  #define BGP_INFO_STALE          (1 << 8)
2989  #define BGP_INFO_REMOVED        (1 << 9)
2990  #define BGP_INFO_COUNTED       (1 << 10)
2991 +#define BGP_INFO_SUSPICIOUS_O   (1 << 11)
2992 +#define BGP_INFO_SUSPICIOUS_P   (1 << 12)
2993 +#define BGP_INFO_IGNORED_P      (1 << 13)
2994 +#define BGP_INFO_SUSPICIOUS_E   (1 << 14)
2995
2996    /* BGP route type.  This can be static, RIP, OSPF, BGP etc.  */
2997    u_char type;
2998 @@ -120,7 +125,7 @@ struct bgp_static
2999
3000  /* Flags which indicate a route is unuseable in some form */
3001  #define BGP_INFO_UNUSEABLE \
3002 -  (BGP_INFO_HISTORY|BGP_INFO_DAMPED|BGP_INFO_REMOVED)
3003 +  (BGP_INFO_HISTORY|BGP_INFO_DAMPED|BGP_INFO_REMOVED|BGP_INFO_IGNORED_P)
3004  /* Macro to check BGP information is alive or not.  Sadly,
3005   * not equivalent to just checking previous, because of the
3006   * sense of the additional VALID flag.
3007 --- a/bgpd/bgp_table.h
3008 +++ b/bgpd/bgp_table.h
3009 @@ -65,6 +65,8 @@ struct bgp_node
3010
3011    int lock;
3012
3013 +  struct bgp_pgbgp_hist *hist;
3014 +
3015    u_char flags;
3016  #define BGP_NODE_PROCESS_SCHEDULED     (1 << 0)
3017  };
3018 --- a/bgpd/bgpd.h
3019 +++ b/bgpd/bgpd.h
3020 @@ -123,6 +123,7 @@ struct bgp
3021    /* BGP Per AF flags */
3022    u_int16_t af_flags[AFI_MAX][SAFI_MAX];
3023  #define BGP_CONFIG_DAMPENING              (1 << 0)
3024 +#define BGP_CONFIG_PGBGP                  (1 << 1)
3025
3026    /* Static route configuration.  */
3027    struct bgp_table *route[AFI_MAX][SAFI_MAX];
3028 --- a/lib/hash.c
3029 +++ b/lib/hash.c
3030 @@ -166,6 +166,35 @@ hash_iterate (struct hash *hash,
3031        }
3032  }
3033
3034 +/*
3035 +  Iterates until 0 is returned or until completion
3036 +  Return: 1 if iteration completed
3037 +  Return: 0 if iteration was interrupted
3038 +*/
3039 +
3040 +int
3041 +hash_iterate_until(struct hash *hash,
3042 +                  int (*func) (struct hash_backet *, void *), void *arg)
3043 +{
3044 +  unsigned int i;
3045 +  struct hash_backet *hb;
3046 +  struct hash_backet *hbnext;
3047 +  int ret;
3048 +
3049 +  for (i = 0; i < hash->size; i++)
3050 +    for (hb = hash->index[i]; hb; hb = hbnext)
3051 +      {
3052 +       /* get pointer to next hash backet here, in case (*func)
3053 +        * decides to delete hb by calling hash_release
3054 +        */
3055 +       hbnext = hb->next;
3056 +       ret = (*func) (hb, arg);
3057 +       if (!ret)
3058 +         return 0;
3059 +      }
3060 +  return 1;
3061 +}
3062 +
3063  /* Clean up hash.  */
3064  void
3065  hash_clean (struct hash *hash, void (*free_func) (void *))
3066 --- a/lib/hash.h
3067 +++ b/lib/hash.h
3068 @@ -66,7 +66,8 @@ extern void *hash_release (struct hash *
3069
3070  extern void hash_iterate (struct hash *,
3071                    void (*) (struct hash_backet *, void *), void *);
3072 -
3073 +extern int hash_iterate_until(struct hash *,
3074 +                             int (*) (struct hash_backet *, void *), void *);
3075  extern void hash_clean (struct hash *, void (*) (void *));
3076  extern void hash_free (struct hash *);
3077
3078 --- a/lib/memtypes.c
3079 +++ b/lib/memtypes.c
3080 @@ -147,6 +147,15 @@ struct memory_list memory_list_bgp[] =
3081    { MTYPE_PEER_UPDATE_SOURCE,  "BGP peer update interface"     },
3082    { MTYPE_BGP_DAMP_INFO,       "Dampening info"                },
3083    { MTYPE_BGP_DAMP_ARRAY,      "BGP Dampening array"           },
3084 +  { 0, NULL },
3085 +  { MTYPE_BGP_PGBGP_ORIGIN,     "BGP PGBGP Origin AS Node"      },
3086 +  { MTYPE_BGP_PGBGP_PREFIX,     "BGP PGBGP Prefix AS Node"      },
3087 +  { MTYPE_BGP_PGBGP_EDGE,       "BGP PGBGP Edge Node"           },
3088 +  { MTYPE_BGP_PGBGP_REUSE,      "BGP PGBGP Reuse Node"          },
3089 +  { MTYPE_BGP_PGBGP_HIST,       "BGP PGBGP History Node"        },
3090 +  { MTYPE_BGP_PGBGP_AVOID,      "BGP PGBGP Avoid Peer Node"     },
3091 +  { MTYPE_BGP_PGBGP_PEER,       "BGP PGBGP Peer Timing"         },
3092 +  { 0, NULL },
3093    { MTYPE_BGP_REGEXP,          "BGP regexp"                    },
3094    { MTYPE_BGP_AGGREGATE,       "BGP aggregate"                 },
3095    { -1, NULL }