Going Beyond Pollution Attacks: Forcing Byzantine Clients to Code Correctly

Details Going Beyond Pollution Attacks: Forcing Byzantine Clients to Code Correctly Going Beyond Pollution Attacks: Forcing Byzantine Clients to Code Correctly

2011-08-10

arxiv.org/abs/1108.2080v1

Computer Science

Networking and Internet Architecture

A shorter version is in submission to IEEE INFOCOM 2012

Scientific paper

Network coding achieves optimal throughput in multicast networks. However, throughput optimality \emph{relies} on the network nodes or routers to code \emph{correctly}. A Byzantine node may introduce junk packets in the network (thus polluting downstream packets and causing the sinks to receive the wrong data) or may choose coding coefficients in a way that significantly reduces the throughput of the network. Most prior work focused on the problem of Byzantine nodes polluting packets. However, even if a Byzantine node does not pollute packets, he can still affect significantly the throughput of the network by not coding correctly. No previous work attempted to verify if a certain node \emph{coded correctly using random coefficients} over \emph{all} of the packets he was supposed to code over. We provide two novel protocols (which we call PIP and Log-PIP) for detecting whether a node coded correctly over all the packets received (i.e., according to a random linear network coding algorithm). Our protocols enable any node in the network to examine a packet received from another node by running a "verification test". With our protocols, the worst an adversary can do and still pass the packet verification test is in fact equivalent to random linear network coding, which has been shown to be optimal in multicast networks. Our protocols resist collusion among nodes and are applicable to a variety of settings. Our topology simulations show that the throughput in the worst case for our protocol is two to three times larger than the throughput in various adversarial strategies allowed by prior work. We implemented our protocols in C/C++ and Java, as well as incorporated them on the Android platform (Nexus One). Our evaluation shows that our protocols impose modest overhead.

Affiliated with

Also associated with

No associations

Rating

Going Beyond Pollution Attacks: Forcing Byzantine Clients to Code Correctly does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Going Beyond Pollution Attacks: Forcing Byzantine Clients to Code Correctly, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Going Beyond Pollution Attacks: Forcing Byzantine Clients to Code Correctly will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-664412