<p>Border Gateway Protocol (BGP) is a critical routing protocol of the internet, used to</p><p>exchange routing information between autonomous systems (ASes). BGP is highly</p><p>vulnerable to many attacks that can cause routing disturbance on the internet. This</p><p>paper describes BGP attacks, misconfigurations, causes of misconfigurations, impact</p><p>of these attacks and misconfigurations in BGP and counter measures. Also we</p><p>analyze new security architectures for BGP, comparison of these security protocols</p><p>and their deployment issues. At the end we propose new security solution that is</p><p>Defensive Routing Policy (DRP) to prevent BGP from malicious attacks and</p><p>misconfigurations. DRP is operationally deployable and very effective to solve BGP</p><p>problems.</p>

Border Gateway Protocol (BGP) is a critical routing protocol of the internet, used to exchange routing information between autonomous systems (ASes). BGP is highly vulnerable to many attacks that can cause routing disturbance on the internet. This paper describes BGP attacks, misconfigurations, causes of misconfigurations, impact of these attacks and misconfigurations in BGP and counter measures. Also we analyze new security architectures for BGP, comparison of these security protocols and their deployment issues. At the end we propose new security solution that is Defensive Routing Policy (DRP) to prevent BGP from malicious attacks and misconfigurations. DRP is operationally deployable and very effective to solve BGP problems.

Nous considérons, dans cette thèse, un nouveau service par lequel les opérateurs de télécommunications offrent des routes supplémentaires à leurs clients (en plus de la route par défaut) comme un service gratuit ou à valeur ajoutée. Ces routes supplémentaires peuvent être utilisées par des clients afin d’optimiser leurs communications, en outrepassant des points de congestion d’Internet, ou les aider à atteindre leurs objectifs d’ingénierie de trafic (meilleurs délais etc.) ou dans un but de robustesse. Nous proposons d’abord une architecture simple permettant à un opérateur de télécommunication de bénéficier de la diversité de chemin qu’il reçoit déjà. Nous étendons ensuite cette architecture afin de rendre possible la propagation de cette diversité de chemin, non seulement aux voisins directs mais aussi, de proche en proche, aux autres domaines. Nous profitons de cette occasion pour relaxer la sélection des routes des différents domaines afin de leur permettre de mettre en place de nouveaux paradigmes de routage. Néanmoins, annoncer des chemins additionnels peut entrainer des problèmes de passage à l’échelle car chaque opérateur peut potentiellement recevoir plus de chemins que ce qu’il peut gérer. Nous quantifions ce problème et mettons en avant des modifications et filtrages simples permettant de réduire ce nombre à un niveau acceptable. En dernier, nous proposons un processus, inspiré des ventes aux enchères, permettant aux opérateurs de propager aux domaines voisins seulement les chemins qui intéressent les dits voisins. De plus, ce processus permet de mettre en avant un nouveau paradigme de propagation de routes, basé sur des négociations et accords commerciaux / In this thesis we consider a new service where carriers offer additional routes to their customers (w.r.t. to the BGP default route) as a free or value-added service. These alternate routes can be used by customers to optimize their communications, by bypassing some congested points in the Internet (e.g. a “tussled” peeringpoints), to help them to meet their traffic engineering objectives (better delays etc.) or just for robustness purposes (e.g, shift to a disjoint alternate route if needed). First we propose a simple architecture that allows a network service provider to benefit from the diversity it currently receives. Then we extend this architecture in order to make the propagation of the Internet path diversity possible, not only to direct neighbors but also to their neighbors and so on. We take advantage of this advance to relax the route selection processes of autonomous systems in order to make them be able to set up new routing paradigms. Nevertheless announcing additional paths can lead to scalability issues, so each carrier could receive more paths than what it could manage. We quantify this issue and we underline easy adaptations and small path filterings which make the number of paths drop to a manageable amount. Last but not least we set up an auction-type route allocation framework, which gives to network service providers the opportunities first to propagate to their neighbors only the paths the said neighbors are interested in and second to leverage a new routing selection paradigm based on commercial agreements and negotiations

Border Gateway Protocol (BGP) prefix hijacking is a serious problem in the Internet today. Although there are several services being offered to detect a prefix hijack, there has been little work done to prevent a hijack or to continue providing network service during a prefix hijack attack. This thesis proposes a novel framework to provide defense against prefix hijacking which can be offered as a service by Content Distribution Networks and large Internet Service Providers. Our experiments revealed that the hijack success rate reduced from 90.36% to 30.53% at Tier 2, 84.65% to 10.98% at Tier 3 and 82.45% to 8.39% at Tier 4 using Autonomous Systems (ASs) of Akamai as Hijack Prevention Service Provider. We also observed that 70% of the data captured by Hijack Prevention Service Provider (HPSP) can be routed back to Victim. However if we use tunneling, i.e. trying to route data to neighbors of Victims which in turn sends the traffic to Victims, we observed that data can be routed to Victim 98.09% of the time. Also, the cost of such redirection is minimal, since the average increase in path length was observed to be 2.07 AS hops.

Border Gateway Protocol (BGP) prefix hijacking is a serious problem in the Internet today. Although there are several services being offered to detect a prefix hijack, there has been little work done to prevent a hijack or to continue providing network service during a prefix hijack attack. This thesis proposes a novel framework to provide defense against prefix hijacking which can be offered as a service by Content Distribution Networks and large Internet Service Providers. Our experiments revealed that the hijack success rate reduced from 90.36% to 30.53% at Tier 2, 84.65% to 10.98% at Tier 3 and 82.45% to 8.39% at Tier 4 using Autonomous Systems (ASs) of Akamai as Hijack Prevention Service Provider. We also observed that 70% of the data captured by Hijack Prevention Service Provider (HPSP) can be routed back to Victim. However if we use tunneling, i.e. trying to route data to neighbors of Victims which in turn sends the traffic to Victims, we observed that data can be routed to Victim 98.09% of the time. Also, the cost of such redirection is minimal, since the average increase in path length was observed to be 2.07 AS hops.

Student Number : 9607275H - MSc dissertation - School of Electrical and Information Engineering - Faculty of Engineering and the Built Environment / Internet worms are capable of quickly propagating by exploiting vulnerabilities of hosts that have access to the Internet. Once a computer has been infected, the worms have access to sensitive information on the computer, and are able to corrupt or retransmit this information. This dissertation describes a method of predicting Internet instability due to the presence of a worm on the Internet, using data currently available from global Internet routers. The work is based on previous research which has indicated a link between the increase in the number of Border Gateway Protocol (BGP) routing messages and global Internet instability. The type of system used to provide the prediction is known as an autoencoder. This is a specialised type of neural network, which is able to provide a degree of novelty for inputs. The autoencoder is trained to recognise “normal” data, and therefore provides a high novelty output for inputs dissimilar to the normal data. The BGP Update routing messages sent between routers were used as the only inputs to the autoencoder. These intra-router messages provide route availability information, and inform neighbouring routers of any route changes. The outputs from the network were shown to help provide an early warning mechanism for the presence of a worm. An alternative method for detecting instability is a rule-based system, which generates alarms if the number of certain BGP routing messages exceeds a prespecified threshold. This project compared the autoencoder to a simple rule-based system. The results showed that the autoencoder provided a better prediction and was less complex for a network administrator to configure. Although the correlation between the number of BGP Updates and global Internet instability has been shown previously, this work presents the first known application of a neural network to predict the instability using this correlation. A system based on this strategy has the potential to reduce the damage done by a worm’s propagation and payload, by providing an automated means of detection that is faster than that of a human.

Internet est le réseau le plus gigantesque que l'humanité ne se soit pourvu. Il fournit un nombre important de services à plus de deux milliards d'utilisateurs. Cette topologie grandissante et complexe pêche en stabilité, ce qui peut notamment être constaté quand un appel voix est interrompu, quand une page web à besoin d'être rafraîchie, etc. L'initiateur de cette instabilité est l'ensemble des événements constatés dans l'Internet. Ceci nous motive à une Étude profonde de la stabilité d'Internet afin de suggère des solutions à cette problématique. Internet est divisé en deux niveaux de base: le niveau AS (Autonomous System) et le niveau de routage. Cette distinction se répercute dans les protocoles de routage qui contrôlent le trafic Internet à travers deux types de protocoles: extérieur (inter-AS) et intérieur (intra-AS). L'unique protocole de routage extérieur utilité est le mode externe de BGP (External Border Gateway Protocol) tandis qu'il en existe plusieurs de type intérieur. De fait, la stabilisation de l'Internet est corrélée à la stabilité des protocoles de routage. Cela pousse les efforts de traitement de l'instabilité de l'Internet à Étudier le comportement du protocole de routage (BGP). Analyser les résultats des comportements de BGP dans son mode externe (eBGP) souffre d'un temps de convergence important menant notamment à des réponses lentes des évènements de topologie et, à terme, à la perte du trafic. Les études établissent également que le mode interne de BGP (iBGP) souffre de plusieurs types d'anomalies de routage causant la divergence. Afin d'illustrer la stabilité de BGP, nous avons besoin d'un modèle de routage qui formule la procédure de décision et le flot de signalisation. De plus, les améliorations de BGP ne peuvent pas être aisément validées dans l'Internet, rendant ainsi les modèles de BGP indispensables à une validation formelle. De fait, la première étape dans l'étude du routage inter-domaine est de définir un modèle approprié permettant la formulation de ses opérations et de prouver sa correction. Nous avons proposé deux modèles complémentaires: topologique et fonctionnel, avec lesquels nous avons formulé le processus de convergence du routage et démontré la sécurité et la robustesse de nos solutions d'inter/intra-AS. Notre proposition d'inter-AS élimine les déconnections transitoires causées par une faible convergence d'eBGP en suggérant une stratégie de backup lors d'une panne. Notre proposition d'intra-AS (skeleton) donne une alternative aux configurations internes existantes, pour laquelle nous avons montré l'absence d'anomalies. / Internet is the hugest network the humanity has ever known. It provides a large number of various services to more than two billion users. This complex and growing topology lacks stability, which we can notice when a voice call is dropped, when a web page needs to be refreshed, etc. The initiator of this instability is the frequent events around the Internet. This motivates us to unleash a profound study to tackle Internet stability and suggest solutions to overcome this concern. Internet is divided into two obvious levels: AS (Autonomous System) level and router level. This distinction is reflected on the routing protocols that control the Internet traffic through two protocol types: exterior (inter-AS) and interior (intra-AS). The unique used exterior routing protocol is the external mode of BGP (External Border Gateway Protocol), while there are several used internal routing protocols. Therefore, stabilizing the Internet is correlated to the routing protocol stability, which directs such efforts to the investigation of routing protocol (BGP) behavior. Studying BGP behaviors results in that its external mode (eBGP) suffers from long convergence time which is behind the slow response to topology events and, in turn, the traffic loss. Those studies state also that BGP internal mode (iBGP) suffers from several types of routing anomalies that causes its divergence.Therefore, we propose enhancements for both BGP modes: eBGP and iBGP and try to meet the following objectives: Scalability, safety, robustness, correctness, and backward compatibility with current version of BGP. Our eBGP proposal eliminates the transient disconnectivity caused by slow convergence by suggesting a backup strategy to be used upon the occurrence of a failure. IBGP proposal (skeleton) gives an alternative to the existing internal configurations, that we prove its freeness of anomalies. Validation methods are essential to prove that the suggested enhancements satisfy the attended objectives. Since we are tackling an interdomain subject, then it is not possible to do validation in the real Internet. We suggested several validation methods to show that our enhancements meet the above objectives. We used simulation environment to implement eBGP backup solution and observe the convergence time and the continuous connectivity. We relied on two tools: brite and rocketfuel to provide us with inter and intra AS topologies respectively. And to prove the safety of our approaches we employed an algebraic framework and made use of its results.

Στην εργασία αυτή, μελετήθηκε η δομή του σύγχρονου ίντερνετ από την σκοπιά του δικτύου και κατέστη σαφές το πως διασυνδέονται οι πάροχοι υπηρεσιών και οι τερματική χρήστες, πως γίνεται η δρομολόγηση και ποιοί αλγόριθμοι χρησιμοποιούνται για τιν επίτευξη της. / This diploma thesis focus on how modern networks connect together in order to create the internet and which algorithms used for the routing of informations that traverse through them.

Internet est constitué de milliers de systèmes autonomes (Autonomous Systems, AS) qui échangent des informations de routage grâce au protocole BGP (Border Gateway Protocol). Chaque AS attend des autres qu'il lui donne des informations de routage correctes, et leur accorde donc une confiance totale. Le détournement de préfixe (prefix hijacking) exploite cette confiance afin d'introduire des routes falsifiées. Les techniques qui détectent cette attaque génèrent un nombre important d'alertes, composé de faux positifs résultant d'opérations de routage courantes. Dans cette dissertation, nous cherchons à trouver la cause principale de ces alertes, de manière indubitable. A cette fin, d'une part, nous réduisons le nombre d'alertes en analysant en profondeur ces réseaux, dont nous dérivons une série de structures qui reflètent les pratiques standard de routage du monde réel, et en considérant le risque associé à ces structures lors une attaque par détournement. D'autre part, nous utilisons des bases de données auxiliaires qui nous permettent de connaître la raison derrière un évènement de routage, qui n'est, en général, connue que du propriétaire du réseau. Précisément, nous regardons les préfixes à origines multiples (Multiple Origin AS, MOAS), et mettons en évidence une classification nous permettant d'éliminer 80% des alertes. Nous présentons un cas réel où un MOAS coïncide avec du spam et des sites d'arnaque en ligne. Nous étudions les préfixes non-disjoints, et présentons un prototype permettant d'éliminer 50% des alertes sub-MOAS.Nous explorons l'espace IP non assigné, cherchons des adresses IP joignables, et localisons une grande quantité de spam et des sites d'arnaques en ligne. / The Internet is composed of tens of thousands Autonomous Systems (ASes) that exchange routing information using the Border Gateway Protocol (BGP). Consequently, every AS implicitly trusts every other ASes to provide accurate routing information. Prefix hijacking is an attack against the inter-domain routing infrastructure that abuses mutual trust in order to propagate fallacious routes. The current detection techniques pathologically raise a large number of alerts, mostly composed of false positives resulting from benign routing practices. In this Dissertation, we seek the root cause of routing events beyond reasonable doubts. First, we reduce the global number of alerts by analyzing false positive alerts, from which we extract constructs that reflect real-world standard routing practices. We then consider the security threat associated with these constructs in a prefix hijacking scenario. Second, we use a variety of auxiliary datasets that reflect distinct facets of the networks involved in a suspicious routing event in order to closely approximate the ground-truth, which is traditionally only known by the network owner. Specifically, we investigate Multiple Origin AS (MOAS) prefixes, and introduce a classification that we use to discard up to 80% of false positive. Then we show a real-world case where a MOAS coincided with spam and web scam traffic. We look at prefix overlaps, clarify their global use, and present a prototype that discards around 50% of false positive sub-MOAS alerts. Finally, we explore the IP blackspace, study the routing-level characteristics of those networks, find live IP addresses, and uncover a large amount of spam and scam activities.

The Border Gateway Protocol (BGP) is an important routing protocol used to exchangerouting information among autonomous systems on the Internet. The BGP version 4 doesnot include specific protection mechanisms against attacks or deliberate errors that couldcause disruptions of routing behavior. There were several securing solutions developedto mitigate security issues of BGP. In this thesis, current secure solutions are reviewedand evaluated against a list of security and deployment requirements. Furthermore, a newBGP securing solution is proposed which uses blockchain technology and smart contractsto exchange information required for messages validation among peers. This allows todecouple security-related data from the protocol itself and fix the problems introduced inother BGP solutions. / Border Gateway Protocol (BGP) är ett viktigt routing protokoll som används för att utbytarouting-information mellan autonoma system på Internet. BGP version 4 inkluderaringa specifika skydd mot attacker eller avsiktliga fel som kan skapa störningar i routingbeteendet. Ett flertal säkerhetslösningar har utvecklas för att förebygga säkerhetsproblemför BGP. I denna avhandling granskas nuvarande befintliga säkerhetslösningar och utvärderasmot en lista av säkerhets- och deployment-krav. Vidare presenteras en ny säkerhetslösningför BGP som använder blockchain-teknologi och smarta kontrakt för att utbytainformation som krävs för verifiering av meddelanden mellan grannar. Detta möjliggöratt frånkoppla säkerhetsrelaterad data från själva protokollet och åtgärda problemen introduceradei andra BGP lösningar.