Algebraic Watchdog: Mitigating Misbehavior in Wireless Network Coding - Computer Science > Cryptography and SecurityReport as inadecuate

Algebraic Watchdog: Mitigating Misbehavior in Wireless Network Coding - Computer Science > Cryptography and Security - Download this document for free, or read online. Document in PDF available to download.

Abstract: We propose a secure scheme for wireless network coding, called the algebraicwatchdog. By enabling nodes to detect malicious behaviors probabilistically anduse overheard messages to police their downstream neighbors locally, thealgebraic watchdog delivers a secure global self-checking network. Unliketraditional Byzantine detection protocols which are receiver-based, thisprotocol gives the senders an active role in checking the node downstream. Thekey idea is inspired by Marti et al.-s watchdog-pathrater, which attempts todetect and mitigate the effects of routing misbehavior.As an initial building block of a such system, we first focus on a two-hopnetwork. We present a graphical model to understand the inference process nodesexecute to police their downstream neighbors; as well as to compute, analyze,and approximate the probabilities of misdetection and false detection. Inaddition, we present an algebraic analysis of the performance using anhypothesis testing framework that provides exact formulae for probabilities offalse detection and misdetection.We then extend the algebraic watchdog to a more general network setting, andpropose a protocol in which we can establish trust in coded systems in adistributed manner. We develop a graphical model to detect the presence of anadversarial node downstream within a general multi-hop network. The structureof the graphical model a trellis lends itself to well-known algorithms, suchas the Viterbi algorithm, which can compute the probabilities of misdetectionand false detection. We show analytically that as long as the min-cut is notdominated by the Byzantine adversaries, upstream nodes can monitor downstreamneighbors and allow reliable communication with certain probability. Finally,we present simulation results that support our analysis.

Author: MinJi Kim, Muriel Medard, Joao Barros


Related documents