The Internet has become an indispensable resource for today's society. It is at the center of the today's business, entertainment, and social world. However, the core of our identities on the Internet, the IP addresses that are used to send and receive data throughout the Internet, are insecure. Attackers today are able to send data purporting to be from nearly any location (IP spoofing) and to reroute data destined for victims to the attackers themselves (IP prefix hijacking). Victims of these attacks may experience denial of service, misplaced blame, and theft of their traffic. These attacks are of the utmost importance since they affect the core layer of the Internet. Although the mechanisms of the attacks are different, they are essentially different sides of the same coin; spoofing attacks forge the identity of the sender, while hijacking attacks forge the identity of the receiver. They revolve around the same underlying lack of a secure identity on the Internet. This research reviews the existing state of the art IP spoofing and IP prefix hijacking research and proposes new defenses to close the missing gaps and provide a new level of security to our identities on the Internet. This material is based upon work supported by the National Science Foundation under Grants No. CNS-0520326 and CNS-1118101. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation. This dissertation includes both previously published/unpublished and co-authored material.

The Border Gateway Protocol (BGP), the main component of core Internet connectivity, suffers vulnerability issues related to the impersonation of the ownership of IP prefixes for Autonomous Systems (ASes). In this context, a number of studies have focused on securing the BGP through several techniques, such as monitoring-based, historical-based and statistical-based behavioural models. In spite of the significant research undertaken, the proposed solutions cannot detect the IP prefix hijack accurately or even differentiate it from other types of attacks that could threaten the performance of the BGP. This research proposes three novel detection methods aimed at tracking the behaviour of BGP edge routers and detecting IP prefix hijacks based on statistical analysis of variance, the attack signature approach and a classification-based technique. The first detection method uses statistical analysis of variance to identify hijacking behaviour through the normal operation of routing information being exchanged among routers and their behaviour during the occurrence of IP prefix hijacking. However, this method failed to find any indication of IP prefix hijacking because of the difficulty of having raw BGP data hijacking-free. The research also proposes another detection method that parses BGP advertisements (announcements) and checks whether IP prefixes are announced or advertised by more than one AS. If so, events are selected for further validation using Regional Internet Registry (RIR) databases to determine whether the ASes announcing the prefixes are owned by the same organisation or different organisations. Advertisements for the same IP prefix made by ASes owned by different organisations are subsequently identified as hijacking events. The proposed algorithm of the detection method was validated using the 2008 YouTube Pakistan hijack event; the analysis demonstrates that the algorithm qualitatively increases the accuracy of detecting IP prefix hijacks. The algorithm is very accurate as long as the RIRs (Regional Internet Registries) are updated concurrently with hijacking detection. The detection method and can be integrated and work with BGP routers separately. Another detection method is proposed to detect IP prefix hijacking using a combination of signature-based (parsing-based) and classification-based techniques. The parsing technique is used as a pre-processing phase before the classification-based method. Some features are extracted based on the connectivity behaviour of the suspicious ASes given by the parsing technique. In other words, this detection method tracks the behaviour of the suspicious ASes and follows up with an analysis of their interaction with directly and indirectly connected neighbours based on a set of features extracted from the ASPATH information about the suspicious ASes. Before sending the extracted feature values to the best five classifiers that can work with the specifications of an implemented classification dataset, the detection method computes the similarity between benign and malicious behaviours to determine to what extent the classifiers can distinguish suspicious behaviour from benign behaviour and then detect the hijacking. Evaluation tests of the proposed algorithm demonstrated that the detection method was able to detect the hijacks with 96% accuracy and can be integrated and work with BGP routers separately.

BGP hijacking is a threat to network organizations because traditional BGP protocols were not designed with security in mind. Currently, research to combat hijacking is being done by detecting hijacking in real time from Public Route Collectors. However, by using AS-Path Prepending, a well-known traffic engineering technique, hijackers could adjust the influence scope of hijacks to potentially avoid Public Route Collectors. This thesis investigates fist, whether AS-Path Prepending is sufficient to hide from Public Route Collector, and second whether the hijacker can predict its hijack’s stealthiness by simply comparing the AS path length with the victim. Last, we investigate the non-hijacker-controlled parameters, which are the geographical locations and victim prepending times if the victim also enable AS-Path Prepending for traffic engineering in our study. Our results show that on one hand, AS-Path Prepending benefits stealthy hijacks to route collectors. While on the other hand, it is not sufficient to completely hide from route collectors only using it. By simply comparing the AS paths length, the hijacker’s prediction is constructive but not practical. And non-hijacker-controlled parameters indeed can significantly affect the stealthiness of hijacking. / BGP-kapning är ett hot mot nätverksorganisationer eftersom traditionella BGP-protokoll inte har utformats med säkerheten i åtanke. För närvarande bedrivs forskning för att bekämpa kapning genom att upptäcka kapning i realtid från offentliga ruttinsamlare. Genom att använda AS-Path Prepending, en välkänd trafikteknik, kan kapare dock justera kapningarnas inflytande för att eventuellt undvika offentliga ruttinsamlare. I den här avhandlingen undersöks för det första om AS-Path Prepending är tillräckligt för att dölja sig för Public Route Collector och för det andra om kaparen kan förutsäga hur smygande kapningen är genom att helt enkelt jämföra AS Path-längden med offrets. Slutligen undersöker vi de parametrar som inte kontrolleras av kaparen, dvs. geografiska platser och offrets prependingtider om offret också aktiverar AS-Path Prepending för trafikteknik i vår studie. Våra resultat visar att AS-Path Prepending å ena sidan gynnar smygande kapningar av ruttinsamlare. Å andra sidan räcker det inte för att helt och hållet dölja sig för ruttinsamlare om man bara använder det. Genom att helt enkelt jämföra AS-vägarnas längd är kaparens förutsägelser konstruktiva men inte praktiska. Parametrar som inte kontrolleras av kaparen kan faktiskt påverka kapningens smygande på ett betydande sätt.

As the Internet becomes the ubiquitous infrastructure for various applications, demands on the reliability, availability and security of routing protocols in the Internet are becoming more stringent. Unfortunately, failures are still common in the daily operation of a network. Service disruption for even a short time can seriously affect the quality of real-time applications, such as VoIP and video on demand applications. Moreover, critical business and government applications require routing protocols to be robust against malicious attacks, such as denial of Service attacks. This dissertation proposes three techniques to address some reliability and security concerns in intra-domain (distance vector) routing protocols and inter-domain (path vector) routing protocols. The first technique addresses the problem of service disruption that arises from sudden link failures in distance vector routing protocols. We consider two types of link failures: single link failures and shared risk link group failures. For single link failures, we propose an IP fast reroute mechanism to reroute packets around the failed links. This fast reroute mechanism is the first that does not require complete knowledge of the network topology and does not require changing of the original routing protocol. This mechanism proactively computes a set of relay nodes that can be used to tunnel the rerouted packets immediately after the detection of a link or node failure. The mechanism includes an algorithm for a node to automatically identify itself as a candidate relay node for a reroute link and notify the source node of the reroute link of its candidacy. The source node can then decide the validity of a candidate relay node. The mechanism also includes an algorithm to suppress redundant notification messages. We then extend our IP fast reroute mechanism for single link failures to accommodate shared risk link group failures. We achieve this goal by introducing one more bit information. Through simulations, I show that the proposed mechanisms succeed in rerouting around failed links about 100% of the time, with the length of the reroute path being comparable to the length of the re-converged shortest path. The second technique addresses the problem that arises from allowing any node to route data packets to any other node in the network (and consequently allow any adversary node to launch DoS attacks against other nodes in the network). To solve this problem, we propose a blocking option to allow a node u to block a specified set of nodes and prevent each of them from sending or forwarding packets to node u. The blocking option intends to discard violating packets near the adversary nodes that generated them rather than near their ultimate destinations. We then discuss unintentionally blocked nodes, called blind nodes and extend the routing protocols to allow each node to communicate with its blind nodes via some special nodes called joint nodes. Finally, I show, through extensive simulation, that the average number of blind nodes is close to zero when the average number of blocked nodes is small. The third technique addresses the problem that arises when a set of malicious ASes in the Internet collude to hijack an IP prefix from its legitimate owner in BGP. (Note that none of previous proposals for protecting BGP against IP prefix hijacking is effective when malicious ASes can collude.) To solve this problem, we propose an extension of BGP in which each listed AS in an advertised route supplies a certified full list of all its peers. Then I present an optimization where each AS in an advertised route supplies only a balanced peer list, that is much smaller than its full peer list. Using real Internet topology data, I demonstrate that the average, and largest, balanced peer list is 92% smaller than the corresponding full peer list. Furthermore, in order to handle the dynamics of the Internet topology, we propose algorithms on how to issue certificates to reflect the latest changes of the Internet topology graph. Although the results in this dissertation are presented in the context of distance vector and path vector routing protocols, many of these results can be extended to link state routing protocols as well. / text