Randy's Work Blog

Caitlin Gray, Clemens Mosig, Randy Bush, Cristel Pelsser, Matthew
Roughan, Thomas Schmidt, Matthias Wählisch . BGP Beacons, Network Tomography, and Bayesian Computation to Locate Route Flap Damping, ACM IMC 2020

Pinpointing autonomous systems which deploy specific inter-domain techniques such as Route Flap Damping (RFD) or Route Origin Validation (ROV) remains a challenge today. Previous approaches to detect per-AS behavior often relied on heuristics derived from passive and active measurements. Those heuristics, however, often lacked accuracy or imposed tight restrictions on the measurement methods.

We introduce an algorithmic framework for network tomog- raphy, BeCAUSe, which implements Bayesian Computation for Autonomous Systems. Using our original combination of active probing and stochastic simulation, we present the first study to expose the deployment of RFD. In contrast to the expectation of the Internet community, we find that at least 9% of measured ASs enable RFD, most using deprecated vendor default configuration parameters. To illustrate the power of computational Bayesian methods we compare BeCAUSe with three RFD heuristics. Thereafter we successfully apply a generalization of the Bayesian method to a second challenge, measuring deployment of ROV.

RFC 8893 
Title: Resource Public Key Infrastructure (RPKI) Origin Validation for BGP Export 
Author: R. Bush, 
        R. Volk,
        J. Heitz
Status: Standards Track 
Stream: IETF 
Date: September 2020 
Updates: RFC 6811 
URL: https://www.rfc-editor.org/info/rfc8893 
DOI: 10.17487/RFC8893

A BGP speaker may perform Resource Public Key Infrastructure (RPKI) origin validation not only on routes received from BGP neighbors and routes that are redistributed from other routing protocols, but also on routes it sends to BGP neighbors. For egress policy, it is important that the classification use the ‘effective origin AS’ of the processed route, which may specifically be altered by the commonly available knobs, such as removing private ASes, confederation handling, and other modifications of the origin AS.

Odnan Ref Sanchez, Simone Ferlin, Cristel Pelsser, Randy Bush Comparing Machine Learning Algorithms for BGP Anomaly Detection using Graph Features at 3rd ACM CoNEXT Workshop on Big DAta, Machine Learning and Artificial Intelligence for Data Communication Networks (Big-DAMA 2019)

The Border Gateway Protocol (BGP) coordinates the connectivity and reachability among Autonomous Systems, providing efficient operation of the global Internet. Historically, BGP anomalies have disrupted network connections on a global scale, i.e., detecting them is of great importance. Today, Machine Learning (ML) methods have improved BGP anomaly detection using volume and path features of BGP’s update messages, which are often noisy and bursty. In this work, we identified different graph features to detect BGP anomalies, which are arguably more robust than traditional features. We evaluate such features through an extensive comparison of different ML algorithms, i.e., Naive Bayes classifier (NB), Decision Trees (DT), Random Forests (RF), Support Vector Machines (SVM), and Multi-Layer Perceptron (MLP), to specifically detect BGP path leaks. We show that SVM offers a good trade-off between precision and recall. Finally, we provide insights into the graph features’ characteristics during the anomalous and non-anomalous interval and provide an interpretation of the ML classifier results.

    RFC 8654
    Title:      Extended Message Support for BGP
    Author:     R. Bush,
                K. Patel,
                D. Ward
    Status:     Standards Track
    Stream:     IETF
    Date:       October 2019
    Mailbox:    randy@psg.com,
                keyur@arrcus.com,
                dward@cisco.com
    Pages:      7
    Updates:    RFC 4271
    I-D Tag:    draft-ietf-idr-bgp-extended-messages-36.txt
    URL:        https://www.rfc-editor.org/info/rfc8654
    DOI:        10.17487/RFC8654

The BGP specification (RFC 4271) mandates a maximum BGP message size of 4,096 octets. As BGP is extended to support new Address Family Identifiers (AFIs), Subsequent AFIs (SAFIs), and other features, there is a need to extend the maximum message size beyond 4,096 octets. This document updates the BGP specification by extending the maximum message size from 4,096 octets to 65,535 octets for all messages except for OPEN and KEEPALIVE messages.

 RFC 8642
 Title:      Policy Behavior for Well-Known BGP  Communities 
 Author:     J. Borkenhagen, 
             R. Bush,
             R. Bonica, 
             S. Bayraktar
 Status:     Standards Track
 Stream:     IETF
 Date:       August 2019
 Pages:      7
 Characters: 13429
 Updates:    RFC 1997
 I-D Tag:    draft-ietf-grow-wkc-behavior-08.txt
 URL:        https://www.rfc-editor.org/info/rfc8642
 DOI:        10.17487/RFC8642

Well-known BGP communities are manipulated differently across various current implementations, resulting in difficulties for operators. Network operators should deploy consistent community handling across their networks while taking the inconsistent behaviors from the various BGP implementations into consideration. This document recommends specific actions to limit future inconsistency: namely, BGP implementors must not create further inconsistencies from this point forward. These behavioral changes, though subtle, actually update RFC 1997.

 RFC 8635
 Title:      Router Keying for BGPsec 
 Author:     R. Bush,
             S. Turner,
             K. Patel
 Status:     Standards Track
 Stream:     IETF
 Date:       August 2019
 I-D Tag:    draft-ietf-sidrops-rtr-keying-06.txt
 URL:        https://www.rfc-editor.org/info/rfc8635
 DOI:        10.17487/RFC8635

BGPsec-speaking routers are provisioned with private keys in order to sign BGPsec announcements. The corresponding public keys are published in the Global Resource Public Key Infrastructure (RPKI), enabling verification of BGPsec messages. This document describes two methods of generating the public-private key pairs: router-driven and operator-driven.

Florian Streibelt, Franziska Lichtblau, Robert Beverly, Anja Feldmann, Cristel Pelsser, Georgios Smaragdakis, and Randy Bush. BGP Communities: Even more Worms in the Routing Can. Proc. Internet Measurement Conference 2018 (IMC ‘18).ACM, New York, NY, USA, 279-292.

Florian Streibelt, Franziska Lichtblau, Robert Beverly, Anja Feldmann, Cristel Pelsser, Georgios Smaragdakis, Randy Bush; BGP Communities: Even more Worms in the Routing Can; ACM Internet Measurement Conference 2018.

BGP communities are a mechanism widely used by operators to manage policy, mitigate attacks, and engineer traffic; e.g., to drop unwanted traffic, filter announcements, adjust local preference, and prepend paths to influence peer selection.

Unfortunately, we show that BGP communities can be exploited by remote parties to influence routing in unintended ways. The BGP community-based vulnerabilities we expose are enabled by a combination of complex policies, error-prone configurations, a lack of cryptographic integrity and authenticity over communities, and the wide extent of community propagation. Due in part to their ill-defined semantics, BGP communities are often propagated far further than a single routing hop, even though their intended scope is typically limited to nearby ASes. Indeed, we find 14% of transit ASes forward received BGP communities onward. Given the rich inter-connectivity of transit ASes, this means that communities effectively propagate globally. As a consequence, remote adversaries can use BGP communities to trigger remote blackholing, steer traffic, and manipulate routes even without prefix hijacking. We highlight examples of these attacks via scenarios that we tested and measured both in the lab as well as in the wild. While we suggest what can be done to mitigate such ill effects, it is up to the Internet operations community whether to take up the suggestions.

        RFC 8481

        Title:      Clarifications to BGP Origin Validation Based
                    on Resource Public Key Infrastructure (RPKI) 
        Author:     R. Bush
        Status:     Standards Track
        Stream:     IETF
        Date:       September 2018
        Mailbox:    randy@psg.com
        Pages:      5
        Characters: 9629
        Updates:    RFC 6811
        I-D Tag:    draft-ietf-sidrops-ov-clarify-05.txt
        URL:        https://www.rfc-editor.org/info/rfc8481
        DOI:        10.17487/RFC8481

Deployment of BGP origin validation based on Resource Public Key
Infrastructure (RPKI) is hampered by, among other things, vendor
misimplementations in two critical areas: which routes are validated
and whether policy is applied when not specified by configuration.
This document is meant to clarify possible misunderstandings causing
those misimplementations; it thus updates RFC 6811 by clarifying that
all prefixes should have their validation state set and that policy
must not be applied without operator configuration.

Andreas Reuter, Randy Bush, Italo Cunha, Ethan Katz-Bassett, Thomas C. Schmidt, Matthias Wählisch; Towards a Rigorous Methodology for Measuring Adoption of RPKI Route Validation and Filtering; SIGCOMM August 2018

A proposal to improve routing security—Route Origin Authorization (ROA)—has been standardized. A ROA specifies which network is allowed to announce a set of Internet destinations. While some networks now specify ROAs, little is known about whether other networks check routes they receive against these ROAs, a process known as Route Origin Validation (ROV). Which networks blindly accept invalid routes? Which reject them outright? Which de-preference them if alternatives exist?

Recent analysis attempts to use uncontrolled experiments to characterize ROV adoption by comparing valid routes and invalid routes. However, we argue that gaining a solid understanding of ROV adoption is impossible using currently available data sets and techniques. Instead, we devise a verifiable methodology of controlled experiments for measuring ROV. Our measurements suggest that, although some ISPs are not observed using invalid routes in uncontrolled experiments, they are actually using different routes for (non-security) traffic engineering purposes, without performing ROV. We conclude with presenting three AS that do implement ROV as confirmed by the operators.