Nicephorus: Striking a Balance between the Recovery Capability and the Overhead of Byzantine Detection

Abstract:

Perimeter security mechanisms, such as firewalls, do not provide adequate protection once the adversary has penetrated the perimeter either because the firewall was bypassed or because the adversary is an insider trusted party. By gaining presence inside a communication network, even at a few locations (routers and links) of strategic importance, the adversary gains the advantage to disrupt the operation of the whole network, in the absence of suitable protection mechanisms.

In this paper, we contribute to protocols (that are termed Byzantine detection protocols) that enable a network to identify the (initially unknown) locations of the adversary inside the network, so that they can be subsequently bypassed, by improving their capability for recovery as well as their overhead. The fault detection state that is obtained by Byzantine detection pertains to triplets of a link and its two adjacent routers without any implication on the faultiness of individual elements of the triplet. Our first contribution is an algorithm that estimates the degree of penetration of the adversary inside the network given this ambiguous fault detection state and its application to the problem of balancing the performance of the detection protocol with its recovery time capability (two parameters that, as we show, can be at a trade-off). Our second and third contributions are on the Byzantine detection mechanisms. We present a generic mechanism that a source router can use to securely obtain arbitrary router-specific feedback and a data forwarding protocol with Byzantine detection capability that significantly improves the performance of previous proposals.