Title: Attacker Model for MANET Routing Security

In this talk we will describe a broad and flexible classification for attackers of mobile ad-hoc network (MANET) routing protocols. Our model examines the attackers and their capabilities rather than specific protocols, attacks and attack requirements in order to form a more complete classification. In addition, our model can be combined with BAN logic, or other similar formalization frameworks, to provide a comprehensive evaluation of specific protocol security.

Title: Centralized Routing and Very High QoS

Backbone networks today are heavily overprovisioned in order to ensure high QoS. This method for achieving high QoS is known as capacity overprovisioning (CO), and is one of two main alternatives to ensure high QoS, the other being admission control (AC), the option favored by the QoS literature since capacity overprovisioning (CO) is viewed as simple, but "wasteful", see, e.g., [Parekh, IWQoS 2003; Milbrandt et al, J.Comm. 2007]. Despite this stigma in the literature, network operators have found CO to be effective and affordable in practice as evidenced by the low utilization of backbone networks.

Despite the gains in QoS that can be achieved with CO, we argue that CO alone is not enough to meet the resiliency demands that will be, and already are, placed on the internet's backbone, because of BGP, IGP, OSPF, and other protocols' inability to exploit the multiplicity of routes offered by a heavily overprovisioned network. Rather than call for replacements for these protocols, this talk will discuss the ways a centralized routing authority can better utilize this extra capacity.

Title: The complexity of game dynamics: BGP oscillations, sink equlibria, and beyond

We settle the complexity of a well-known problem in networking by establishing that it is PSPACE-complete to tell whether a system of path preferences in the BGP protocol can lead to oscillatory behavior; one key insight is that the BGP oscillation question is in fact one about Nash dynamics. We show that the concept of sink equilibria proposed recently is also PSPACE-complete to analyze and approximate for graphical games. Finally, we propose a new equilibrium concept inspired by game dynamics, unit recall equilibria, which we show to be close to universal (exists with high probability in a random game) and algorithmically promising. We also give a relaxation thereof, called componentwise unit recall equilibria, which we show to be both tractable and universal (guaranteed to exist in every game).

Title: Removing the Incentive to Lie about Paths in BGP with Traffic Attraction

We argue that the ideal security definition for interdomain routing is control plane integrity, namely, that paths announced via BGP should match the paths that packets are actually forwarded along in the data plane. In this work, we ask what enhancements to BGP and/or restricted classes of routing policies can guarantee control plane integrity. We take a game-theoretic approach, by assuming that ASes will lie only if doing so improves their routing outcomes. In contrast to previous work, we assume that a "rational" AS not only cares about getting the best possible outgoing path for its traffic to the destination, but also about attracting incoming traffic, either out of greed (since other ASes pay it to carry their traffic), or malice (so it can eavesdrop, spoof or tamper with packets). We find that, while protocols like secure BGP are necessary to remove the incentive to lie, they are in general not sufficient, unless certain classes of ASes are only interested in the next hop that their traffic takes to its destination. Our analysis highlights the high cost of guaranteeing control plane integrity, and suggest that it will be difficult to provide without (expensive) data-plane enforcement protocols.

Joint work with Shai Halevi.

Title: Towards a Realistic Model of Incentives in Interdomain Routing: Decoupling Forwarding from Signaling

We model the task of interdomain routing-the task of connecting the networks that compose the Internet-as an iterative, highly distributed, asynchronous game. Unlike previous examinations of this game that assumed quasi-linear utilities, we assume that each node has a quasi-bilinear utility depending not only on the route it believes it is assigned in the outcome, but also on other nodes assigned to route through it. This more realistic model captures out-of-band business relationships that may affect nodes' behavior in the game and the difficulty of monitoring traffic flows on the Internet. We show that, in this model, nodes may have an incentive to deviate from the Internet standard (the Border Gateway Protocol) and lie about what routes are being used, potentially leading to security and reliability problems, unless certain assumptions on nodes' utilities and the network structure hold. We also extend the standard formal model of interdomain routing used in networking to consider this decoupling of forwarding from signaling that is difficult to detect in reality.

Joint work with Vijay Rachandran and Rebecca Wright.

Title: A Distributed Protocol for Fractional Stable Paths Problem

The Border Gateway Protocol (BGP) is currently the only interdomain routing protocol deployed in the Internet. BGP can be viewed as a distributed algorithm for solving a fundental problem known as Stable Paths Problem (SPP). Unlike a shortest path tree, solution to an SPP does not represent a global optimum, but rather an equilibrium point in which each node is assigned its locally optimal path to the specified destination. Not every instance of SPP has a stable solution. Recently, Haxell and Wilfong defined a fractional version of SPP and showed that all instances of fractional SPP (FSPP) have stable solutions. The main open problem in their paper is to design a distributed algorithm that would solve the fractional stable paths problem.

In this paper, we design a distributed protocol that converges to an epsilon-solution of an FSPP instance, for any given epsilon > 0. We designed our protocol to reflect the selfish nature of the source nodes. Every source node follows "best-reply dynamics", based on the local information gathered from its neighbors (without violating the epsilon-stability conditions of FSPP). We define a game-theoretic model for FSPP and prove that maximizing social welfare in FSPP can be done in polynomial time. This is in contrast with SPP, where it is shown, by Levin, Schapira and Zohar, that obtaining an approximation of O(n^{\frac{1}{2}-\epsilon}) to the social welfare is impossible unless P=NP.

Joint work with H. Venkateswaran.

Title: Autonomous Security for Autonomous Systems

The Internet's interdomain routing protocol, BGP, supports a complex network of Autonomous Systems which is vulnerable to a number of potentially crippling attacks. Several promising cryptography-based solutions have been proposed, but their adoption has been hindered by the need for community consensus, cooperation in a Public Key Infrastructure (PKI), and a common security protocol. Rather than force centralized control in a distributed network, we examine distributed security methods that are amenable to incremental deployment. Typically, such methods are less comprehensive and not provably secure. We present a distributed anomaly detection and response system that provides comparable security to cryptographic methods and has a more plausible adoption path. We then explore the boundary between what can be achieved with provably secure centralized security mechanisms for BGP and more distributed approaches that respect the autonomous nature of the Internet.

Title: Instability Free Routing: Beyond One Protocol Instance

In routing, most studies have focused on the correctness of a single routing protocol at a time. However, the Internet consists of multiple routing protocols that need to be interconnected. The glue to join them is composed of two primitives: the route selection ranks the routes received from the different routing protocol instances at each router, and the route redistribution exchanges routing information between the routing processes. This glue is a fundamental component of the Internet routing architecture. Operators rely on it not only to interconnect routing protocols but also to achieve important objectives. Yet, this talk shows that route selection and route redistribution can cause routing anomalies. We present the first comprehensive analysis of both route selection and route distribution regarding all three classes of routing instabilities: non-convergence, formation of loop, and non determinism. We show that each of these two procedures can induce permanent route flaps and forwarding loops. We identify the necessary conditions or root causes for the instabilities and derive guidelines for eliminating them. We then present experimental results showing that all tested Cisco, Quagga, and XORP products have incorrectly implemented the dependency between route selection and route redistribution, causing non-deterministic outcomes. We address this problem by proposing a functional model that makes the dependency unambiguous.

Joint work with Geoffrey Xie and Hui Zhang.

Title: Distributed Algorithmic Mechanism Design: Rational Behavior in Routing

In this talk, I will present an overview of research that uses tools from game theory and economic mechanism design to study interdomain routing. I will begin with a brief introduction to economic modeling of routing decisions. I will focus on the Distributed Algorithmic Mechanism Design approach, which seeks to design routing mechanisms that have desirable incentive properties, as well as being "BGP-compatible" in the sense that they can be implemented by distributed algorithms that do not require major changes to the data structures, storage requirements, or communication patterns of BGP. I will survey the positive and negative results that have been obtained in this area, and outline interesting open problems for future research.

Title: Interdomain Routing and Games

We present a game-theoretic model that captures many of the intricacies of interdomain routing in today's Internet. We address the problem of BGP security from an economic, or mechanism design, perspective. Our main results are showing that in realistic and well-studied settings, security enhancements of BGP are incentive-compatible. I.e., it is in the best interest of every AS to adhere to the protocol. In particular, we show that S-BGP is incentive-compatible in the commercial Gao-Rexford setting, and then show that this even holds for the less costly soBGP.

Joint work with Hagay Levin, Aviv Zohar and Rahul Sami.

Title: Routing in the Global Information Grid

The Global Information Grid (GIG) is a large, private internetwork currently under development by the U.S. Department of Defense (DoD). The GIG will comprise a vast array of node and link types, from backbone fiber networks to human portable, battery powered devices. The GIG will be global in scope, and must support node and network mobility as a fundamental element of the design. Though capable of independent operation, it is expected the GIG will also interface to the commercial Internet, other U.S Government networks, and non-commercial networks of other governments, coalition partners, and humanitarian organizations.

To be economically viable, the GIG will need to leverage commercial networking hardware and software. However, it is likely the GIG will have properties that distinguish it from the commercial Internet, such as the nature of network mobility, requirements for information assurance (IA), and differences in the underlying organizational and economic forces of the system. It is expected that in certain situations the GIG infrastructure may well come under direct physical or protocol attack. Also, pervasive mobility and ad-hoc connectivity make it difficult to apply routing security solutions which check against a known good. An Ideal GIG routing system would bound the damage that is achievable through the compromise of a small number of nodes, while maintaining high availability in a dynamic, ad-hoc environment.

Title: Secure Internet Path Quality Monitoring: Tradeoffs in Security and Efficiency

One part of Internet routing that remains particularly exposed to attacks is the data plane. Data packets usually traverse many intermediate routers on their way from a source to their destination, and since these routers may belong to other (possibly malicious) organizations, how do we guarantee that our packets arrive as intended at their destination and are not dropped or tampered with by some intermediate router?

In this talk I will outline a formal security framework for this problem and focus on two results that show how the level of security one requires drastically changes the amount of resources necessary to achieve security.

Our first result is a protocol that distinguishes between extremely bad performance (say > 1% of traffic is dropped or modified) and tolerable performance (say < 0.05% of traffic is dropped or modified) in the presence of malicious adversaries. The protocol adds only a 200B size additional message per 10^6 data packets transmitted, and requires only the participation of the source and destination routers, with no active participation by intermediate routers. Our techniques are based on the sketching scheme of Charikar-Chen-Farach-Colton '02, but we are able to prove better performance guarantees by our use of cryptographic hash functions.

Our second result shows that in order to know whether each individual packet was transmitted correctly and if not where exactly it was dropped or modified, the cooperation of all intermediate routers is necessary. Our result is a black-box separation in the style of Impagliazzo-Rudich '89, and uses as a building block a learning algorithm of Naor-Rothblum '06. Practically speaking, this result means such strong security may be hard to achieve in real life since intermediate routers may not have any incentive to participate in such a protocol.

This work will appear at EUROCRYPT 2008 and SIGMETRICS 2008 and is joint with Boaz Barak, Sharon Goldberg, Jennifer Rexford, and Eran Tromer.