| The network layer protocols of IP networks naively assume that routers are trusted and egregiously fail even if a few routers become adversarial. By compromising routers, adversaries gain the vantage to disrupt network operations and, therefore, inflict financial losses and other detrimental societal impacts. Because of this high yield, routers are attractive targets to concentrate subversion efforts; operational routers have been reportedly compromised. In this dissertation, we study the problem of mitigating those impacts by ensuring that network operations remain available even in adversarial operational environments.; Ensuring the availability of the network despite the presence of adversaries implies the ability to detect and recover from failures effected by those adversaries. The problem of detecting packet forwarding failures at link-level granularity is studied first. Fine detection granularity expedites recovery; in fact, routing protocols use beacons to detect packet forwarding failures at the link-level. However, beaconing is not sufficient to detect packet forwarding failures when these failures are instigated by an adversary. In our study, we leverage instead a resilient forwarding faults detection paradigm that we call Byzantine detection , and propose various authentication structures to secure it. Byzantine detection is then applied to the problem of recovering from packet forwarding failures. In this regard, we present algorithms for estimating the degree of penetration of the adversary in a network as well as protocols that block adversarial traffic. The estimates obtained by the first application of Byzantine detection can be utilized to balance protection overhead with resilience to Byzantine faults. Blocking adversarial traffic may serve as an incentive for compliance with packet forwarding agreements. Finally, we investigate secure flooding algorithms in wireless ad hoc networks and propose a new flooding algorithm based on the TESLA broadcast authentication protocol. |
