Secure and Efficient Network Fault Localization.

摘要

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.