Byzantine survivable routing for mobile ad hoc networks

A mobile ad hoc network (MANET) is an autonomous self-organizing system of mobile nodes connected by wireless links. A MANET routing protocol enables reliable communication from a source node to an intended destination node by utilizing intermediate forwarding nodes. Security is critical in these networks due to the accessibility of the openly shared wireless medium, the inherent cooperative nature of ad hoc network protocols, and physical vulnerability of mobile devices. The strongest possible attacks are referred to as Byzantine, or insider attacks, where adversaries have full control of a number of authenticated nodes and behave arbitrarily in an attempt to disrupt the network. This dissertation presents two survivable protocols that are capable of providing routing service even in the midst of Byzantine attacks.; The On-Demand Secure Byzantine Routing (ODSBR) protocol provides protection against a finite number of Byzantine adversaries. It is patterned off of a classic on-demand wireless routing protocol but provides additional security guarantees. It utilizes an adaptive probing technique that detects a malicious link in at most log n faults, where n is the length of the path. Problematic links are avoided by using a weight-based mechanism that multiplicatively increases their weights and by using an on-demand route discovery protocol that finds a least weight path to the destination. ODSBR bounds the amount of damage that an attacker or a group of colluding attackers can cause to the network.; In addition to the finite number of Byzantine adversaries handled by ODSBR, this work also presents techniques for throughput-competitive route selection against the ultimate adaptive Byzantine adversary. More specifically, in this model, the adversary benefits from complete collusion of any number of network nodes, has full knowledge of our protocol and deterministic state, and may engage in arbitrary Byzantine behavior which dynamically changes with each new packet. Under this extreme adversarial model, it is not possible to guarantee routing survivability because it allows the adversary to compromise every node at all times. However, the protocol presented has been shown to be competitive with the off-line optimal route selection and makes the best of a hostile environment.