Xin Zhang

Secure and Efficient Network Fault Localization Degree Type: Ph.D. in Computer Science
Advisor(s): Hui Zhang, Adrian Perrig
Graduated: May 2012

Abstract:

High-quality online services demand reliable packet delivery at the network layer. However, clear evidence documents the existence of compromised routers in ISP and enterprise networks, threatening network availability and reliability. A compromised router can stealthily drop, modify, inject, or delay packets in the forwarding path to launch Denial-of-Service, surveillance, man-in-the-middle attacks, etc. Unfortunately, current networks fail to provide any assurance of data delivery in adversarial environments, nor a reliable way to identify misbehaving routers that jeopardize packet delivery. Data-plane fault localization serves as an imperative building block to enhance network availability and reliability, since it localizes faulty links of misbehaving routers, enables a sender to find a fault-free path, and enforces contractual obligations among network nodes. Until recently, however, the design of secure fault localization protocols has proven to be surprisingly elusive. Existing fault localization protocols fail to achieve high security and efficiency, incur unacceptably long detection delays, and require forwarding paths to be impractically long-lived. In this dissertation, we show a suite of secure and efficient fault localization protocols exploring distinct dimensions in the design space of fault localization. Our key idea is to achieve a lower bound on packet forwarding correctness via fault localization by limiting the amount of malicious packet drops/forgeries at the data plane, instead of perfectly detecting every single malicious activity which tends to result in high overhead. In this way, we trap an attacker into a dilemma: if the attacker inflicts damage worse than a threshold, it will be detected, which may lead to removal from the network; otherwise, the damage is limited and thus a lower bound on data-plane packet delivery is achieved. This design principle enables the construction of efficient probabilistic algorithms and the derivation of provable performance bounds. Both the analytical and experimental results show that the proposed protocols outperform prior work by 100 to 1000 times regarding efficiency with provable security against sophisticated attackers.

Thesis Committee:
Adrian Perrig (Co-chair)
Hui Zhang (Co-chair)
Virgil D. Gligor
David Maltz

Jeannette Wing, Head, Computer Science Department
Randy Bryant, Dean, School of Computer Science

Keywords:
Fault localization, secure forwarding, data plane security, accountability, network reliability