Today's routing protocols critically rely on the assumption that the underlying hardware is trusted. Given the increasing number of attacks on network devices, and recent reports on hardware backdoors this assumption has become questionable. Indeed, with the critical role computer networks play today, the contrast between our security assumptions and reality is problematic. This paper presents Software-Defined Adversarial Trajectory Sampling (SoftATS), an OpenFlow-based mechanism to efficiently monitor packet trajectories, also in the presence of non-cooperating or even adversarial switches or routers, e.g., containing hardware backdoors. Our approach is based on a secure, redundant and adaptive sample distribution scheme which allows us to provably detect adversarial switches or routers trying to reroute, mirror, drop, inject, or modify packets (i.e., header and or payload). We evaluate the effectiveness of our approach in different adversarial settings, report on a proof-of-concept implementation, and provide a first evaluation of the performance overheads of such a scheme.
The Border Gateway Protocol (BGP), which is used to distribute routing information between autonomous systems (ASes), is a critical component of the Internet's routing infrastructure. It is highly vulnerable to a variety of malicious attacks, due to the lack of a secure means of verifying the authenticity and legitimacy of BGP control traffic. This paper describes a secure, scalable, deployable architecture (S-BGP) for an authorization and authentication system that addresses most of the security problems associated with BGP. The paper discusses the vulnerabilities and security requirements associated with BGP, describes the S-BGP countermeasures, and explains how they address these vulnerabilities and requirements. In addition, this paper provides a comparison of this architecture to other approaches that have been proposed, analyzes the performance implications of the proposed countermeasures, and addresses operational issues.  Attacks against Internet routing are increasing in number and severity. Contributing greatly to these attacks is the absence of origin authentication: there is no way to validate claims of address ownership or location. The lack of such services enables not only attacks by malicious entities, but indirectly allow seemingly inconsequential miconfigurations to disrupt large portions of the Internet. This paper considers the semantics, design, and costs of origin authentication in interdomain routing. We formalize the semantics of address delegation and use on the Internet, and develop and characterize broad classes of origin authentication proof systems. We estimate the address delegation graph representing the current use of IPv4 address space using available routing data. This effort reveals that current address delegation is dense and relatively static: as few as 16 entities perform 80 of the delegation on the Internet. We conclude by evaluating the proposed services via traced based simulation. Our simulation shows the enhanced proof systems can reduce significantly reduce resource costs associated with origin authentication.  Networks are complex and prone to bugs. Existing tools that check configuration files and data-plane state operate offline at timescales of seconds to hours, and cannot detect or prevent bugs as they arise. Is it possible to check network-wide invariants in real time, as the network state evolves? The key challenge here is to achieve extremely low latency during the checks so that network performance is not affected. In this paper, we present a preliminary design, VeriFlow, which suggests that this goal is achievable. VeriFlow is a layer between a software-defined networking controller and network devices that checks for network-wide invariant violations dynamically as each forwarding rule is inserted. Based on an implementation using a Mininet OpenFlow network and Route Views trace data, we find that VeriFlow can perform rigorous checking within hundreds of microseconds per rule insertion. Today's networks typically carry or deploy dozens of protocols and mechanisms simultaneously such as MPLS, NAT, ACLs and route redistribution. Even when individual protocols function correctly, failures can arise from the complex interactions of their aggregate, requiring network administrators to be masters of detail. Our goal is to automatically find an important class of failures, regardless of the protocols running, for both operational and experimental networks. To this end we developed a general and protocol-agnostic framework, called Header Space Analysis (HSA). Our formalism allows us to statically check network specifications and configurations to identify an important class of failures such as Reachability Failures, Forwarding Loops and Traffic Isolation and Leakage problems. In HSA, protocol header fields are not first class entities; instead we look at the entire packet header as a concatenation of bits without any associated meaning. Each packet is a point in the 0,1 L space where L is the maximum length of a packet header, and networking boxes transform packets from one point in the space to another point or set of points (multicast). We created a library of tools, called Hassel, to implement our framework, and used it to analyze a variety of networks and protocols. Hassel was used to analyze the Stanford University backbone network, and found all the forwarding loops in less than 10 minutes, and verified reachability constraints between two subnets in 13 seconds. It also found a large and complex loop in an experimental loose source routing protocol in 4 minutes.  Today's Internet routing protocols are built upon the basic incorrect assumption that routers propagate truthful routing information. As a result, the entire Internet infrastructure is vulnerable to security attacks from routers that propagate incorrect routing information. In fact, a single router is capable of hijacking a significant fraction of routes by launching such an attack. This issue is not just restricted to Internet routing protocols but is widely prevalent in several routing protocols that have been proposed in the research literature. Many existing approaches for addressing the security problems of routing protocols typically assume the existence of a Public-Key Infrastructure (PKI) or some form of prior key distribution mechanism along with a central authority. While a PKI does enable addressing this security threat, building one such key-distribution infrastructure may not always be feasible. One faces serious deployment barriers in building an Internet-wide PKI with a central authority especially given that deploying one such architecture requires approval across political and economic boundaries. Previous efforts for securing Internet routing and the Domain Name System using a PKI have not moved towards adoption. In this dissertation, we address the following question: Using purely decentralized mechanisms (void of a PKI and a central authority), what is the best level of security achievable for a routing protocol in the presence of adversaries? One of the key conclusions that we arrive at is the direct relationship between decentralized security and the reliable communication problem. The reliable communication problem relates to determining the constraints under which a set of good nodes in a network can reliably communicate messages between themselves in the face of adversarial nodes in the network. We show theoretical results on the constraints under which the reliable communication problem is solvable. Based on these results, we describe the design of a reliable communication toolkit that implements our algorithms and provides a suite of generic security primitives that can be used to secure a variety of routing protocols. These security mechanisms supported by the toolkit are well suited for Internet routing since they are both easy to deploy as well as offer good security guarantees. We also show that the toolkit has broader applicability beyond routing protocols to: (a) achieve decentralized key distribution; (b) address the data integrity threat to the Domain Name System (DNS) in a decentralized manner.  