A Proposal for the Study, Analysis and Visualization of BGP Routes Alexandra Ibarra Cuesta ale@niclabs.cl NIC Chile Research Labs University of Chile Asimismo, debido al gran número de rutas BGP exis- tentes, serı́a útil facilitar este proceso de identificación Abstract mediante un sistema de monitoreo BGP que se encar- gue de recopilar y proveer información importante pa- Today’s Internet is conformed by thousands ra luego llevar a cabo el análisis de la misma. Además, of autonomous systems that exchange infor- para comprender de mejor manera los datos recopila- mation using the BGP protocol, which has dos por el sistema, ası́ como también su análisis, es become the most important routing system imprescindible utilizar un mecanismo de visualización since it allows Internet to carry out each of its mediante el cual sea posible observar tanto las rutas tasks correctly. Given the above, it is highly BGP existentes como la información relevante de los important to identify routing problems with análisis realizados. an easy to read and analyze mechanism. For A partir de lo anterior, el trabajo propuesto se ba- this reason, this work proposes to design vi- sa en diseñar una visualización de las rutas BGP que sualizations of the current state of the BGP muestre el estado actual de las mismas. Esta repre- routes from both a national and international sentación debe ser capaz de mostrar toda la informa- view. It also proposes a subsequent study to ción requerida (rutas y las redes IP) en forma clara. find daily routing changes, and possible nodes Además, se realizará un estudio focalizado en dos pun- that would cause routing failures after being tos diferentes; por una parte está la identificación de removed from the network. Lastly, through cambios en las rutas BGP, para lo cual es necesario lle- these investigations it is intended to design var a cabo un proceso comparativo del estado actual BGP monitors, indicating where they should de la información con el anterior; el otro punto se basa be located; as well as the mechanism for ex- en analizar el enrutamiento con el objetivo de obtener tracting the data necessary for them to work puntos crı́ticos en el grafo, es decir, un nodo que al correctly. ser eliminado provoque, por ejemplo, un aislamiento completo de alguna red IP. Lo anterior conlleva al di- 1 Introducción seño de un sistema de monitoreo BGP, lo que implica establecer la cantidad y ubicación de puntos de con- BGP (Border Gateway Protocol) nace por la nece- trol dentro de la red, ası́ como también determinar el sidad de controlar la selección y propagación de rutas proceso de extracción de los datos y su posterior al- dentro de un Internet en expansión, transformándo- macenamiento, procesamiento, análisis y visualización se en el sistema de enrutamiento más importante y de los mismos. complejo de todos los protocolos existentes puesto que permite el correcto funcionamiento de Internet. Por esta razón es importante la búsqueda de herramien- 2 Trabajo Relacionado tas capaces de identificar problemas de enrutamiento. BGP ha sido un protocolo de constante estudio de- bido a la importancia que este representa para la co- Copyright c by the paper’s authors. Copying permitted for private and academic purposes. municación entre redes. Trabajos anteriores han estu- In: Proceedings of the IV School of Systems and Networks diado la vulnerabilidad de BGP, midiendo incluso el (SSN 2018), Valdivia, Chile, October 29-31, 2018. Published efecto que genera un ataque en el sistema de ruteo at http://ceur-ws.org [ND04]; debido a esto es necesario identificar proble- mas que puedan significar algún riesgo potencial pa- macenados en archivos que contienen diferentes ta- ra el envı́o y recepción de paquetes. Por esto, se han blas BGP. Estos datos fueron obtenidos por NIC Chile llevado a cabo diferentes investigaciones para diseñar (administrador dominios punto CL) desde los distin- monitores BGP. Estos trabajos proponen sistemas de tos puntos de entrada de router de este. Es impor- recolección y análisis automatizado de la información tante señalar que los datos utilizados corresponden de ruteo BGP, ayudando en la detección de comporta- a una muestra diaria obtenida a partir de la tabla mientos anormales en las rutas [Bor07], ası́ como tam- BGP de solamente 7 Sistemas Autónomos diferentes bién alertando de cambios en las mismas [Yan+09], los (AS6429, AS6471, AS7004, AS14259, AS18747, AS19338 cuales, según estudios realizados, pueden producir un y AS27986) debido a que son estos a los que tiene ac- efecto significativo en el flujo de información [TAR05]. ceso NIC Chile. Además, dadas las dificultades enfrentadas debido En la Figura 1 se observa un ejemplo de la tabla a la gran cantidad de datos obtenidos, es necesaria BGP obtenida. Aquı́ se puede apreciar que presenta la búsqueda de un mecanismo de análisis simplifica- diferentes campos, donde los campos Network y Path do. Respecto a esto último se han planteado o realiza- son los únicos importantes para conformar una ruta, do varios mecanismos capaces de representar, visual- y por ende los que se utilizarán para trabajar. Cada mente, las rutas BGP tales como Link-Rank [LMZ04] una de las filas de esta tabla corresponde a una ruta [LMZ06], vizAS1 (desarrollada por APNIC ) y AS- BGP donde Network indica la IP de la red a la cual Viewer [Hel11]. Junto a estas posibles formas de vi- se desea llegar, mientras que Path es una serie de Sis- sualización para las rutas BGP se añaden los estudios temas Autónomos por los cuales se debe pasar para realizados por CAIDA (Center for Applied Internet llegar a dicha IP; la unión de estos “puntos” confor- Data Analysis) que ha generado diferentes grafos de mará una ruta. En la Figura 2 se aprecia la ruta BGP Internet2 . Todas las investigaciones permiten generar obtenida a partir de la primera fila de la tabla de ruteo una idea respecto al posible diseño a realizar para po- de la Figura 1. Cabe destacar que el nodo terminal del der observar las rutas BGP. camino (IP Network) también corresponde a un Siste- ma Autónomo. 3 Particularidad del trabajo propuesto El sistema propuesto unirá dos trabajos indepen- dientes, es decir, el diseño de un sistema de monito- reo junto con visualizaciones de rutas BGP. Además incorporará nuevas funcionalidades, tal como la gene- ración de grafos que entreguen una visibilidad tanto nacional como internacional de las rutas, lo cual per- mitirá analizar si estas son similares tanto desde den- tro como desde fuera del paı́s. Lo anterior corresponde a la diferencia principal con respecto a BGPmon da- Figura 1: Muestra un extracto de la tabla de ruteo del do que esta última no es georreferenciada. Este nuevo AS18747. diseño tendrá también la particularidad de mostrar vi- sualmente los cambios de ruteo identificados, lo cual, además de observar el tipo de modificación ocurrida, permitirá focalizar mejor el análisis de donde puede es- tar el problema o razón del cambio de ruteo. Por otra parte, este sistema se diferencia de los demás dado que busca identificar puntos claves que puedan conllevar, en un futuro, a un posible problema de flujo dentro de la red, siendo routers crı́ticos en caso de ataques, fallas, entre otros. Figura 2: Muestra un ejemplo de ruta BGP, desde el AS18747 a la red IP 1.0.0.0/24, creada usando la li- 4 Análisis Preliminar brerı́a D3 para JavaScript. Actualmente se cuenta con 3.485.877 datos reales que corresponden a rutas BGP, los cuales vienen al- 1 vizAS: https://blog.apnic.net/2015/09/09/ 5 Trabajo a Desarrollar visualise-your-countrys-bgp-network-with-vizas/ 2 AS Core: https://www.caida.org/publications/posters/ Dado que se quiere realizar una investigación de las #ascore rutas BGP, y utilizando como base diferentes estudios que indican que utilizar una representación gráfica pa- ruteo de diferentes routers para luego, enviar todos ra llevar a cabo esta labor permite identificar de mejor los datos obtenidos a una base de datos “global” de manera errores de ruteo, se propone el desarrollo de manera automática; esto dará paso al procesamiento visualizaciones que presenten, de manera correcta, los y análisis de estos datos y su posterior visualización datos recopilados desde las tablas de ruteo de los dife- (ver Figura 3). rentes routers a estudiar. Estas visualizaciones deben dar un panorama tanto nacional como internacional 6 Metodologı́a de las rutas BGP, respondiendo a las siguientes pre- guntas: ¿Cómo se ven las redes chilenas desde Chile?, La metodologı́a de trabajo se divide en diferentes ¿Cómo se ven las redes chilenas de manera internacio- etapas de desarrollo. nal? y ¿Cómo se ven las redes internacionales desde una visión chilena? Para esto será necesario un estu- 6.1 Manejo de la tabla de ruteo dio previo respecto a cada una de las direcciones IP Se deben establecer los campos de extracción de obtenidas con el objetivo de identificar cuales de estas las tablas de ruteo, tales que estos permitan definir corresponden a IPs nacionales y cuales a internaciona- una ruta BGP. Debido a lo anterior, se deben reali- les. zar diferentes parser que se encarguen de extraer la En base al sistema diseñado, se llevará a cabo un información y llevarla, finalmente, al formato que será estudio de estas para encontrar cambios generados en utilizado para crear la visualización. las rutas BGP, para esto se debe implementar una for- En cuanto a este punto es posible mencionar que ma de poder recuperar diariamente la información de ya se establecieron los parámetros de extracción, tal y ruteo para que, tras su procesamiento, se logre ob- como se mencionó anteriormente, siendo estos campos: tener automáticamente su representación y, además, Network y Path. Además, se han realizado diferentes los cambios de enrutamiento con respecto a la infor- programas en Python, encargados de la sustracción de mación antigua, lo cual implica desde la ausencia de dichos datos y su transformación al formato utilizado un Sistema Autónomo previo hasta el cambio como actualmente, el cual consiste en un json donde cada tal de una ruta (utilizar otros Sistemas Autónomos). nodo presenta la siguiente estructura: Además, se realizará un análisis del grafo generado pa- { ” node ” : { ra lograr identificar nodos crı́ticos, es decir, routers que ” id ” : id node , al ser desconectados o presentar alguna falla generen, ” group ” : g r o u p n o d e , por ejemplo, que redes IP no sean alcanzables por nin- ” label ” : label node guna otra ruta provocando un aislamiento completo de }} dicha red. Donde id node corresponde al AS o a la red, por ejemplo, si el nodo representa al AS 7004, entonces id node tendrá el valor 7004; group node identificará si el nodo en cuestión corresponde a un AS, en cuyo caso group node será 1, o si es una IP, por lo que tendrá el valor 2; mientras que label node será un identificador interno de cada nodo dentro de su grupo respectivo. 6.2 Diseño de visualización Se analizarán diferentes tipos de visualizaciones pa- ra encontrar la que mejor se adapte a los objetivos planteados. Para llevar a cabo este proceso se utilizará JavaScript, junto con la librerı́a gráfica D3. Actualmente se cuenta con un modelo básico de vi- sualización, el cual nació de las representaciones ya realizadas en trabajos previos, como por ejemplo CAI- Figura 3: Esquema del sistema de monitoreo. Cada DA. Este modelo se caracteriza por ser un grafo circu- punto de control se representa por un “ojo”. lar, donde su frontera se conforma por los nodos corres- pondientes a las IPs, mientras que los nodos internos Finalmente, se diseñará un sistema de monitoreo son los sistemas autónomos utilizados en el ruteo de el cual une cada una de las caracterı́sticas anteriores, información. es decir, se dispondrán puntos de control encargados Cabe destacar que debido a la gran cantidad de in- de recopilar, diariamente, información de las tablas de formación, el grafo diseñado contiene agrupación de IPs según su ruteo, es decir, se unieron en un solo ya existentes tales como: MaxMind3 , LacNic4 , entre nodo aquellas redes que presentaban el mismo camino otros. de sistemas autónomos, permitiendo disminuir en gran medida el exceso de información visual, clarificando las 6.4 Trabajo futuro rutas existentes. A largo plazo se deben desarrollar las caracterı́sticas En la Figura 4 se encuentra la representación desa- principales del sistema de monitoreo, es decir, analizar rrollada hasta ahora la cual se debe seguir modifican- y desarrollar otros tipos de representaciones gráficas, y do, dado que se debe mejorar el posicionamiento y establecer cómo desarrollar las visualizaciones especı́fi- distribución actual de los nodos, puesto que varios de cas, eligiendo la representación que mejor se adapte estos se ubican alejados de sus puntos de conexión in- para solucionar el problema. Además, se deben imple- mediatos, generando aristas de gran longitud, lo que mentar programas de análisis de rutas para identificar provoca que la visualización sea más compleja y difı́cil cambios de ruteo y puntos crı́ticos en la red. Final- de entender. mente, se debe determinar el proceso de extracción de los datos reales utilizados por el sistema de monito- reo, de manera que sea automatizado, y su posterior procesamiento y visualización. Referencias [Bor07] Gunnar Bornemann. “Data Analysis and Design of a BGP Monitoring and Alarm System”. En: Diploma Thesis in Computer Science, Technische Universität München (mar. de 2007). [Hel11] Mathias Helminger. “Interactive visualiza- tion of global routing dynamics”. En: Ba- chelor Thesis in Informatics, Technische Universität München (jun. de 2011). [LMZ04] Mohit Lad, Dan Massey y Lixia Zhang. Figura 4: Prototipo de visualización desarrollada ac- “Link-Rank: A Graphical Tool for Captu- tualmente. ring BGP Routing Dynamics”. En: Net- work Operations and Management Sympo- sium (NOMS) (abr. de 2004). Además, se seguirá analizando la forma de agrupar los datos de manera tal que disminuya la congestión de [LMZ06] Mohit Lad, Dan Massey y Lixia Zhang. información, por ejemplo por prefijos de IPs; ası́ como “Visualizing Internet Routing Changes”. también agregar diferentes caracterı́sticas al modelo, En: IEEE Transactions on Visualization que permitan que la información sea más fácil de ana- and Computer Graphics (nov. de 2006). lizar por un observador externo, por ejemplo, añadir [ND04] Ola Nordström y Constantinos Dovrolis. interactividad, gama de colores, transparencia, entre “Beware of BGP Attacks”. En: SIGCOMM otros, para resaltar zonas relevantes. Esta medida es Comput. Commun. Rev. 34.2 (abr. de vital debido a la gran cantidad de datos que deben con- 2004), págs. 1-8. tener cada uno de los gráficos a generar, permitiendo [TAR05] Renata Teixeira, Sharad Agarwal y Jen- focalizar la atención del observador en ciertos puntos nifer Rexford. “BGP Routing Changes: de interés según el sistema de monitoreo, facilitando Merging Views from Two ISPs”. En: un seguimiento y estudio más focalizado de un posible SIGCOMM Comput. Commun. Rev. 35.5 problema de ruteo. (oct. de 2005), págs. 79-82. [Yan+09] He Yan y col. “BGPmon: A Real-Time, 6.3 Identificación de IPs Scalable, Extensible Monitoring System”. En: 2009 Cybersecurity Applications Tech- Es necesario identificar la localización geográfica nology Conference for Homeland Security tanto de las IPs como de los sistemas autónomos, debi- (2009), págs. 212-223. do a que se deben realizar visualizaciones de carácter tanto nacional como internacional de las rutas BGP. 3 https://www.maxmind.com/en/home Para esto se utilizarán trabajos y/o herramientas 4 https://rdap-web.lacnic.net/