// Write AS-PATH policies, given the output of "show bgp"
// Jakob Heitz (jheitz@cisco.com)
// This code is free. Do whatever you want. Comments and bug reports welcome.
// Compile it on a Linux command line with "cc showbgp2policy.c".
// The result is the executable, called a.out. Run it. It will print help.

#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <search.h>
#include <assert.h>

#define MAX_AS_PATH 25
#define MAX_IOS_PL 500  // maximum number of policy-lists

typedef enum {
    OS_NONE = 0,
    OS_XR,
    OS_IOS
} router_os_t;
    
typedef struct {
    uint32_t count; // number of routes using this as path
    uint32_t asn[MAX_AS_PATH];
} aspath_t;

// as adjacency
// asn[0] is an asn. asn[1] is its upstream.
// if asn[1] == 0, then asn[0] is a neighbor.
typedef struct {
    uint32_t asn[2];
    uint32_t count; // number of routes from this nbr (only if asn[1]==0)
} asa_t;


void *aspath_tree = NULL;
void *asa_tree = NULL;
void *nbr_tree = NULL; // nbrs in count order
router_os_t router_os = OS_NONE;

FILE *f;
char buf[1000];
int max_path_len = 0;
uint32_t current_asn, last_asn;
int num_policies, first_part;

int
cmp_aspath (const void *a, const void *b)
{
    int i;
    aspath_t *pa = (aspath_t*)a;
    aspath_t *pb = (aspath_t*)b;
    
    for (i=0; i<MAX_AS_PATH; i++) {
        if (pa->asn[i] < pb->asn[i]) return -1;
        if (pa->asn[i] > pb->asn[i]) return 1;
        if (pa->asn[i] == 0 && pb->asn[i] == 0) return 0;
    }
    return 0;
}

int
cmp_asa (const void *a, const void *b)
{
    int i;
    asa_t *pa = (asa_t*)a;
    asa_t *pb = (asa_t*)b;
    
    for (i=0; i<2; i++) {
        if (pa->asn[i] < pb->asn[i]) return -1;
        if (pa->asn[i] > pb->asn[i]) return 1;
    }
    return 0;
}

int
cmp_nbr (const void *a, const void *b)
{
    int i;
    asa_t *pa = (asa_t*)a;
    asa_t *pb = (asa_t*)b;
    
    if (pa->count > pb->count) return -1;
    if (pa->count < pb->count) return 1;
    if (pa->asn[0] < pb->asn[0]) return -1;
    if (pa->asn[0] > pb->asn[0]) return 1;
    return 0;
}

void
print_asa_tree (const void *nodep, const VISIT which, const int depth)
{
    asa_t *asa;
    
    switch(which) {
    case preorder:
    case endorder:
        break;
    case postorder:
    case leaf:
        asa = *(asa_t**)nodep;
        if (asa->asn[0] != current_asn) return;
        if (asa->asn[1] == 0) {
            printf("\n%6u= %6u:", asa->count, asa->asn[0]);
        } else {
            printf(" %u", asa->asn[1]);
        }
        break;
    }
}

void
print_route_policy (const void *nodep, const VISIT which, const int depth)
{
    asa_t *asa;
    
    switch(which) {
    case preorder:
    case endorder:
        break;
    case postorder:
    case leaf:
        asa = *(asa_t**)nodep;
        if (asa->asn[0] != current_asn) return;
        if (asa->asn[1] == 0) {
            if (num_policies <= 0) return;
            num_policies--;
            // now, asn[0] is the asn to write the policy for
            if (last_asn != 0) {
                // end the previous policy. Don't print it the first time
                switch (router_os) {
                case OS_XR:
                    printf("  or\n"
                           "     not as-path passes-through \'%u\'  then\n"
                           "    pass\n"
                           "  endif\n"
                           "end-policy\n"
                           "!\n",
                           last_asn);
                    break;
                case OS_IOS:
                    printf("ip as-path access-list %d deny ^%u_\n",
                           MAX_IOS_PL-1-num_policies, last_asn);
                    printf("ip as-path access-list %d permit _%u_\n",
                           MAX_IOS_PL-1-num_policies, last_asn);
                }
            }
            switch (router_os) {
            case OS_XR:
                printf("route-policy PL_%u\n"
                       "  if as-path neighbor-is \'%u\'",
                       asa->asn[0], asa->asn[0]);
                break;
            case OS_IOS:
                break;
            }
            last_asn = asa->asn[0];
        } else {
            if (num_policies <= 0) return;
            // now, asn[1] is an upstream of asn[0]
            switch (router_os) {
            case OS_XR:
                printf("  or\n"
                       "     as-path passes-through \'%u  %u\'",
                       asa->asn[1], asa->asn[0]);
                break;
            case OS_IOS:
                printf("ip as-path access-list %d deny _%u_%u_\n",
                       MAX_IOS_PL-num_policies, asa->asn[1], asa->asn[0]);
                break;
            }
        }
        break;
    }
}

void
print_route_policy_finish (const void *nodep, const VISIT which, const int depth)
{
    asa_t *asa;
    
    switch(which) {
    case preorder:
    case endorder:
        break;
    case postorder:
    case leaf:
        asa = *(asa_t**)nodep;
        if (asa->asn[0] != current_asn) return;
        if (asa->asn[1] == 0) {
            num_policies--;
            if (num_policies < 0) return;
            // now, asn[0] is the asn to write the policy for
            if (last_asn != 0) {
                // end the previous policy. Don't print it the first time
                printf(" and\n"
                       "     ");
            }
            printf("apply PL_%u",
                   asa->asn[0]);
            last_asn = asa->asn[0];
        }
        break;
    }
}

void
create_nbr (const void *nodep, const VISIT which, const int depth)
{
    asa_t *asa, **asap;
    
    switch(which) {
    case preorder:
    case endorder:
        break;
    case postorder:
    case leaf:
        asa = *(asa_t**)nodep;
        if (asa->asn[1] == 0) {
            asap = tsearch(asa, &nbr_tree, cmp_nbr);
            assert(*asap != NULL); // out of memory
        }
        break;
    }
}

void
create_asa (const void *nodep, const VISIT which, const int depth)
{
    aspath_t *asp;
    int i;
    asa_t *asa, *nbr, **asap, **nbrp;
    
    switch(which) {
    case preorder:
    case endorder:
        break;
    case postorder:
    case leaf:
        asp = *(aspath_t**)nodep;
        // add the neighbor entry (with asn[1]==0)
        nbr = calloc(sizeof(*nbr), 1);
        assert(nbr != NULL);  // out of memory
        nbr->asn[0] = asp->asn[0];
        nbr->asn[1] = 0;
        nbrp = tsearch(nbr, &asa_tree, cmp_asa);
        if (nbr != *nbrp) free (nbr);
        assert(*nbrp != NULL); // out of memory
        (*nbrp)->count += asp->count;
        for (i=0; i<MAX_AS_PATH-1; i++) {
            if (asp->asn[i+1] == 0) break;
            asa = calloc(sizeof(*asa), 1);
            assert(asa != NULL);  // out of memory
            asa->asn[0] = asp->asn[i+1];
            asa->asn[1] = asp->asn[i];  // the upstream ASN
            asap = tsearch(asa, &asa_tree, cmp_asa);
            if (asa != *asap) free (asa);
            assert(*asap != NULL); // out of memory
        }
        break;
    }
}

void
nbr_walk (const void *nodep, const VISIT which, const int depth)
{
    asa_t *asa, **asap;
    
    switch(which) {
    case preorder:
    case endorder:
        break;
    case postorder:
    case leaf:
        asa = *(asa_t**)nodep;
        // cannot start or stop the walk inside the tree with tsearch,
        // so walk the whole thing.
        // select the correct record with current_asn
        current_asn = asa->asn[0];
        //twalk(asa_tree, print_asa_tree);
        if (first_part) {
            twalk(asa_tree, print_route_policy);
        } else {
            twalk(asa_tree, print_route_policy_finish);
        }
        break;
    }
}

void
print_aspath_tree (const void *nodep, const VISIT which, const int depth)
{
    aspath_t *asp;
    int i, j;
    asa_t asa, **asap;
    int peercnt;
    
    switch(which) {
    case preorder:
    case endorder:
        break;
    case postorder:
    case leaf:
        asp = *(aspath_t**)nodep;
        printf("%u:", asp->count);
        peercnt = 0;
        for (i=0; i<MAX_AS_PATH; i++) {
            if (asp->asn[i] == 0) break;
            printf(" %u", asp->asn[i]);
        }
        printf(" \n");
        break;
    }
}

void
create_ios_policy_lists (int num_policies_save)
{
    int i;
    
    // walk the nbr_tree to create each access-list
    
    first_part = 1;
    last_asn = 0;
    num_policies = num_policies_save;
    twalk(nbr_tree, nbr_walk);
    // print the end of the last policy
    printf("ip as-path access-list %d deny ^%u_\n",
           MAX_IOS_PL-num_policies, last_asn);
    printf("ip as-path access-list %d permit _%u_\n",
           MAX_IOS_PL-num_policies, last_asn);
    
    // create the policy-list which matches all the others
    
    printf("ip policy-list BLOCK_AS permit\n"
           " match as-path");
    for (i=MAX_IOS_PL+1-num_policies_save; i<=MAX_IOS_PL-num_policies; i++) {
        printf(" %u", i);
    }
    printf("\n");
}

void
create_ios_xr_policies (int num_policies_save)
{
    // walk the nbr_tree to create each policy
    
    first_part = 1;
    last_asn = 0;
    num_policies = num_policies_save;
    twalk(nbr_tree, nbr_walk);
    // print the end of the last policy
    printf("  or\n"
           "     not as-path passes-through \'%u\'  then\n"
           "    pass\n"
           "  endif\n"
           "end-policy\n"
           "!\n",
           last_asn);

    // walk the nbr_tree to create the allow_as policy which applies all the others
    
    printf("route-policy allow_as\n"
           "  if ");
    first_part = 0;
    last_asn = 0;
    num_policies = num_policies_save;
    twalk(nbr_tree, nbr_walk);
    printf(" then\n"
           "    pass\n"
           "  endif\n"
           "end-policy\n");
}

int
main (int argc, char *argv[])
{
    char *cp;
    int pos, res, res1, i, pathlen, target_found, num_policies_save;
    uint32_t asn, lastasn, target_asn;
    aspath_t *asp, **aspp;
    char *p1, *p2, **endp1, **endp2;
    int path_offs = -1;

    if (argc == 5) {
        // extract paths with this AS, after this AS.
        // that means from the point of view of this AS.
        // get all paths if this is 0.
        res = sscanf(argv[2], "%u", &target_asn);
        res1 = sscanf(argv[3], "%d", &num_policies_save);
        if (!strcmp(argv[4], "IOS-XR")) router_os = OS_XR;
        if (!strcmp(argv[4], "IOS")) router_os = OS_IOS;
        // IOS supports no more than 500 as-path access-list
        if (router_os == OS_IOS && num_policies_save > MAX_IOS_PL) router_os = OS_NONE;
        // show bgp from http://archive.routeviews.org/oix-route-views/
        f = fopen(argv[1], "r");
    }

    if (argc != 5 || res != 1 || res1 != 1 || router_os == OS_NONE || f == NULL) {
        if (argc == 5 && res == 1 && res1 == 1 && router_os != OS_NONE) {
            fprintf(stderr, "Could not open file %s\n\n", argv[1]);
        }
        fprintf(stderr, "Create a route-policy to prevent route leaks for IOS-XR\n"
                "synopsis:\n"
                "  a.out show_bgp asn num_policies router_os\n"
                "where:\n"
                "a.out        is the program name\n"
                "show_bgp     is the name of a file containing the output of \"show bgp\"\n"
                "asn          is the autonomous system number (see below)\n"
                "num_policies is the number of asn\'s you want to write policies for\n"
                "router_os    is IOS or IOS-XR. The target OS for which to write policies\n"
                "\n"
                "If show_bgp is from your own AS, then use 0 for asn.\n"
                "If show_bgp is from another AS that receives routes from you,\n"
                "such as routeviews.org, then use your own ASN for asn.\n"
                "This program will scan the as-paths in show_bgp, looking for your neighbor AS\'s.\n"
                "Next, it will scan again, looking for routes that include each of those\n"
                "neighbors. For each one that it finds, it will note the upstream for that\n"
                "neighbor. It will now have a list of each of your neighbor AS\'s and\n"
                "each of their upstream AS's other than you.\n"
                "It will assume that each upstream it finds for a neighbor is an allowed\n"
                "upstream AS to reach you.\n"
                "Next, the program will write a route-policy for each neighbor.\n"
                "The policy will drop any route that includes the neighbor ASN in its AS-PATH\n"
                "if the next ASN is not an allowed upstream.\n"
                "Next, it will write route-policy allow_as, which will apply all the previously\n"
                "written route-policies.\n"
                "You may now apply this policy in your own neighbor inbound policies.\n"
                "For example for IOS-XR:\n"
                "\n"
                "route-policy your_neighbor_in\n"
                "  if apply allow_as then\n"
                "    pass\n"
                "  else\n"
                "    set community (65000:666)\n"
                "    set local-preference 0\n"
                "  endif\n"
                "end-policy\n"
                "\n"
                "You may list all the routes that were disallowed like this:\n"
                "show bgp community 65000:666\n"
                "\n"
                "If router_os is IOS, then the program will write an ip policy-list\n"
                "and ip as-path access-lists instead of route-policies.\n"
                "You can match the ip policy-list in your route-maps\n"
                "The access-list indexes range from (500 - num_policies) to 500\n"
                "Therefore, num_policies cannot be > 500.\n"
                "\n"
                "The program will only write up to the number of policies you specify in the\n"
                "num_policies parameter, to limit the number of policies that have to be evaluated\n"
                "for each received route. It chooses the ASNs that send you the most routes.\n"
                "Route leaks from those ASNs have the largest impact.\n"
                "The show_bgp file is assumed not to include any route leaks already.\n"
                "If there are route leaks already, then you will have to fix up the policies.\n"
                "\n"
                "show_bgp can be from any IOS or IOS-XR router, ipv4 or ipv6.\n"
                "You can use the resulting route-policies in all routers in the same region of your AS.\n"
                "A neighbor AS may have an allowed upstream in one region that is not allowed\n"
                "in another region. In that case, you need different policies in different regions.\n"
                );
        exit(0);
    }
    // skip the header
    while (fgets(buf, 1000, f)) {
        p1 = strstr(buf, "Network");
        p2 = strstr(buf, "Path");
        if (p1 != NULL && p2 != NULL && p1 < p2) {
            path_offs = p2 - buf; // The word "Path" represents the column of the as-path
            break;
        }
    }
    assert(path_offs >= 0);

    // read the as-paths from the routes in the show bgp file.
    // store the as-path only after the target_asn.
    // if target_asn is not in the as-path, then ignore the as-path.
    // if target_asn==0, store the entire as-path.
    // aspath_tree stores the paths.
    // count is the number of routes in which an as-path is found.
    
    while (fgets(buf, 1000, f)) {
        if (strlen(buf) <= path_offs) break; // show bgp ipv6 may span 2 lines per route
        cp = buf+path_offs;  // start at as-path
        lastasn = 0;
        pathlen = 0;
        target_found = (target_asn == 0);
        asp = calloc(sizeof(*asp), 1);
        assert(asp != NULL);  // out of memory
        while (1) {
            // read the asn and position of the next one
            res = sscanf(cp, " %u%n", &asn, &pos);
            if (res != 1) break; // non-numreic or eol
            cp += pos;
            if (*cp == ',') break; // AS_SET
            if (target_found && (asn != target_asn)) {
                if (asn != lastasn) { // skip duplicates (as prepends)
                    //printf(" %u", asn);
                    asp->asn[pathlen] = asn;
                    ++pathlen;
                    if (pathlen > max_path_len) max_path_len = pathlen;
                }
                lastasn = asn;
            }
            if (asn == target_asn) target_found = 1;
        }
        if (pathlen == 0) {
            free(asp);
        } else {
            aspp = tsearch(asp, &aspath_tree, cmp_aspath); // find or add
            assert(*aspp != NULL);  // out of memory to add
            (*aspp)->count++;
            if (asp != *aspp) free (asp);
            //printf(" \n");
        }
    }

    //printf("max path len = %d\n", max_path_len);
    if (max_path_len == 0) { // no as-paths read
        fprintf(stderr, "No matching as-paths were found\n");
        return;
    }

    // create the asa_tree.
    // This stores the AS adjacencies.
    // for each record, asn[0] is the subject ASN and asn[1] is an upstream of asn[0].
    // if asn[1]==0, then count is the number of times this ASN appears in a route.

    twalk(aspath_tree, create_asa);
    //twalk(aspath_tree, print_aspath_tree);

    // create the nbr_tree.
    // This stores the neighbor ASNs
    
    twalk(asa_tree, create_nbr);

    switch (router_os) {
    case OS_XR:
        create_ios_xr_policies(num_policies_save);
        break;
    case OS_IOS:
        create_ios_policy_lists(num_policies_save);
        break;
    }
}