RESEARCH


My area of research is the security and performance of computer networks. I am interested both in the design, implementation and maintenance of practical networks, and in algorithms and protocols.

Summary

Networks are large distributed systems, and are also subject to a wide variety of attacks (eavesdropping, Man-in-the-Middle, Denial of Service, confused deputy attacks such as phishing, and so on). In order to ensure networks that are secure and available, but at the same time scalable and high-performance, it is essential to see them both at a high level of abstraction (such as a graph with edges representing FIFO channels) and as physical machines with physical components (for example, routers have finite buffers, often do not respond to ping, and so on). My work mostly focuses on the detection and diagnosis of faults in networks, and I have also worked in the design of secure protocols.

Monitoring and Debugging Networks

My primary area of research is finding network failures, and diagnosing the fault responsible. Failures can be caused by faults in the policy (i.e. incorrect contents in routing tables or filtering tables such as firewalls) or the mechanism (link failure etc.) My early work focuses on finding errors in network policies: for my dissertation, I designed, proved correct, and built Probe, a new policy verification algorithm. In contrast to the existing decision-diagram methods, Probe requires only O(nd) space to verify a policy with n rules and d features; though it requires O(n^d) time, in practice it runs in seconds for policies of several thousand rules. (This performance is made possible by the use of two new techniques, projection and slicing.) I also showed how a fast verification algorithm (in this case, Probe) could be used for other purposes, such as finding and removing all redundant rules in a policy.

In my later work on policies, I have explored parallelism, building both a parallel version of Probe and a method for reducing a policy into independent modules that can be run in parallel. A particularly interesting result from this work was my discovery of new metrics for policy complexity; I believe one of these metrics, the width index, explains the question of why decision-diagram methods are tractable in practice, when in theory they should take O(nd) space.

In my current work, I am focusing on more general policies, such as distributed and stateful policies, and on tools that can help detect errors in both policy and mechanism, such as Nick McKeown's Hassel and Ari Fogel's Batfish. I am exploring the possibility of using SAT solvers to check the correctness of a network, whether they are competitive with BDD based approaches, and how they can supplement pre-existing tools. Further, I am interested in the problem of debugging networks by identifying the fault responsible for a network failure; I intend to explore various approaches, ranging from model checking to delta debugging, to diagnose faults in networks.

Closely related to my work on network diagnostics, I have also made some contributions to the problem of network tomography, i.e. reconstructing a network, given a set of paths through it. If any nodes in the network have more than one possible name (i.e. they are anonymous or aliased), then the network topology cannot always be uniquely deduced; besides the first proof of this statement, I showed that the correct topology can be identified uniquely only in the case of some simple topologies such as trees and odd rings. (In other cases, such as even rings, there are many - sometimes exponentially many - possible networks that produce the same set of paths.) These results are especially important for networks that care about anonymity (such as P2P networks), but I am myself more interested in the possibility of developing tools to map networks with less error.

Network Protocols

A secondary area in which I have some interest is the modeling and implementation of secure network protocols. A large number of security problems are caused by the fact that practical protocols are quite complicated, and subtle errors are very difficult to reason out. In this area, I have contributed theoretical results on adversary models and key distribution, and developed, implemented, and showed the security of several protocols. For example, I am one of the developers of the Two-Way Password Protocol, which ensures secure two-way authentication between server and client. (In contrast, the current state-of-the-art, where the server provides a sitekey and the client provides a password, can be broken by a Man-in-the-Middle attack: in any such protocol, either client or server has to be the first to provide credentials - whether password or sitekey - and a clever attacker can use this asymmetry to compromise the system). I am particularly interested in machine-to-machine networks, and am currently studying the security of such networks in the context of my background in sensor networks, proxies, and network operating systems.