research-article

On counteracting byzantine attacks in network coded peer-to-peer networks

Authors:

Muriel Médard,

Keesook J. HanAuthors Info & Claims

IEEE Journal on Selected Areas in Communications, Volume 28, Issue 5

Pages 692 - 702

https://doi.org/10.1109/JSAC.2010.100607

Published: 01 June 2010 Publication History

Abstract

Random linear network coding can be used in peer-to-peer networks to increase the efficiency of content distribution and distributed storage. However, these systems are particularly susceptible to Byzantine attacks. We quantify the impact of Byzantine attacks on the coded system by evaluating the probability that a receiver node fails to correctly recover a file. We show that even for a small probability of attack, the system fails with overwhelming probability. We then propose a novel signature scheme that allows packet-level Byzantine detection. This scheme allows one-hop containment of the contamination, and saves bandwidth by allowing nodes to detect and drop the contaminated packets. We compare the net cost of our signature scheme with various other Byzantine schemes, and show that when the probability of Byzantine attacks is high, our scheme is the most bandwidth efficient.

References

[1]

R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung, "Network information flow," IEEE Trans. Inf. Theory, vol. 46, pp. 1204-1216, 2000.

Digital Library

[2]

T. Ho, M. Médard, M. Effros, and D. Karger, "The benefits of coding over routing in a randomized setting," in Proc. IEEE ISIT, Kanagawa, Japan, July 2003.

[3]

Z. Li and B. Li, "Network coding: the case of multiple unicast sessions," in Proc. 42nd Annual Allerton Conference on Communication Control and Computing, September 2004.

[4]

D. Lun, M. Médard, and R. Koetter, "Network coding for efficient wireless unicast," in Proc. International Zurich Seminar on Communications, Zurich, Switzerland, February 2006.

[5]

R. Koetter and M. Médard, "An algebraic approach to network coding," IEEE/ACM Trans. Netw., vol. 11, pp. 782-795, 2003.

Digital Library

[6]

D. Lun, M. Medard, R. Koetter, and M. Effros, "On coding for reliable communication over packet networks," Physical Communication, vol. 1, no. 1, pp. 3-20, 2008.

Digital Library

[7]

T. Ho, M. Médard, R. Koetter, M. Effros, J. Shi, and D. R. Karger, "A random linear coding approach to mutlicast," IEEE Trans. Inf. Theory, vol. 52, pp. 4413-4430, 2006.

[8]

S. Acedański, S. Deb, M. Médard, and R. Koetter, "How good is random linear coding based distributed network storage?" in Proc. 1st Netcod, Riva del Garda, Italy, April 2005.

[9]

C. Gkantsidis and P. Rodriguez, "Network coding for large scale content distribution," in Proc. IEEE INFOCOM, Miami, FL, March 2005.

[10]

"Bittorrent file sharing protocol," http://www.BitTorrent.com.

[11]

C. Gkantsidis, J. Miller, and P. Rodriguez, "Comprehensive view of a live network coding p2p system," in Proc. ACM SIGCOMM/USENIX Internet Measurement Conference, Rio de Janeiro, Brazil, October 2006.

[12]

R. Perlman, "Network layer protocols with Byzantine robustness," Ph.D. dissertation, Massachusetts Institute of Technology, Cambridge, MA, October 1988.

[13]

M. Castro and B. Liskov, "Practical Byzantine fault tolerance," in Symposium on Operating Systems Design and Implementation (OSDI), February 1999.

[14]

L. Lamport, R. Shostak, and M. Pease, "The Byzantine generals problem," ACM Trans. Programming Languages and Systems, vol. 4, pp. 382-401, 1982.

Digital Library

[15]

S. Jaggi, M. Langberg, S. Katti, T. Ho, D. Katabi, and M. Médard, "Resilient network coding in the presence of Byzantine adversaries," in Proc. IEEE INFOCOM, March 2007, pp. 616-624.

[16]

C. Gkantsidis and P. Rodriguez, "Cooperative security for network coding file distribution," in Proc. IEEE INFOCOM, April 2006.

[17]

A. Barabási and R. Albert, "Emergence of Scaling in Random Networks," Science, vol. 286, no. 5439, p. 509, 1999.

[18]

L. A. Adamic, R. M. Lukose, A. R. Puniyani, and B. A. Huberman, "Search in power-law networks," Phys. Rev. E, vol. 64, no. 4, p. 046135, September 2001.

[19]

R. Pastor-Satorras and A. Vespignani, "Epidemic spreading in scale-free networks," Phys. Rev. Lett., vol. 86, no. 14, pp. 3200-3203, Apr 2001.

[20]

R. M. May and A. L. Lloyd, "Infection dynamics on scale-free networks," Phys. Rev. E, vol. 64, no. 6, p. 066112, Nov 2001.

[21]

F. Zhao, T. Kalker, M. Médard, and K. J. Han, "Signatures for content distribution with network coding," in Proc. IEEE ISIT, June 2007.

[22]

M. Kim, M. Médard, and J. Barros, "Countering byzantine adversaries with network coding: An overhead analysis," in Proc. IEEE MILCOM, November 2008.

[23]

L. Lima, J. Barros, and R. Koetter, "Byzantine attacks against network coding in peer to peer distributed storage," in Proc. IEEE ISIT, June 2009.

[24]

A. G. Dimakis, P. B. Godfrey, M. J. Wainwright, and K. Ramchandran, "Network coding for distributed storage systems," in Proc. IEEE INFOCOM, Anchorage, Alaska, May 2007.

[25]

R. W. Yeung and N. Cai, "Network error correction," Communications in Information and Systems, no. 1, pp. 19-54, 2006.

[26]

R. Koetter and F. Kschischang, "Coding for errors and erasures in random network coding," IEEE Trans. Inf. Theory, vol. 54, pp. 3579- 3591, 2008.

Digital Library

[27]

D. Silva and F. Kschischang, "Adversarial error correction for network coding: Models and metrics," in Proc. Annual Allerton Conf. on Commun., Control, and Computing, Monticello, IL, September 2008.

[28]

T. Ho, B. Leong, R. Koetter, M. Médard, and M. Effros, "Byzantine modification detection in multicast networks using randomized network coding," in Proc. IEEE ISIT, June 2004.

[29]

D. Charles, K. Jain, and K. Lauter, "Signatures for network coding," in Proc. Conference on Information Sciences and Systems, March 2006.

[30]

N. Koblitz, A. Menezes, and S. Vanstone, "The state of elliptic curve cryptography," Designs, Codes and Cryptography, vol. 19, no. 2-3, pp. 173-193, March 2000.

Digital Library

[31]

Z. Yu, Y. Wei, B. Ramkumar, and Y. Guan, "An efficient signature-based scheme for securing network coding against pollution attacks," in Proceedings of IEEE INFOCOM, Pheonix, AZ, April 2008.

[32]

M. Krohn, M. Freedman, and D. Mazières, "On-the-fly verification of rateless erasure codes for efficient content distribution," in Proc. IEEE Symposium on Security and Privacy, May 2004.

[33]

National Institute of Standards and Technology, "Digital signature standard (DSS)," FIBS PUB 186-2, 2000.

[34]

D. Boneh and M. Franklin, "An efficient public key traitor tracing scheme," in Lecture Notes in Computer Science, vol. 1666. Springer-Verlag, 1999, pp. 338-353.

Cited By

Lawrence TLi FAli IHaruna CKpiebaareh MChristopher T(2022)A computationally efficient HMAC-based authentication scheme for network codingTelecommunications Systems10.1007/s11235-021-00842-679:1(47-69)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1007/s11235-021-00842-6
Sassatelli LMédard MHamdan HToral-Cruz HAkleylek SMcheick HBoubiche D(2017)Thwarting pollution attacks in network coding for delay tolerant mobile social networksProceedings of the Second International Conference on Internet of things, Data and Cloud Computing10.1145/3018896.3018960(1-7)Online publication date: 22-Mar-2017
https://dl.acm.org/doi/10.1145/3018896.3018960
Esfahani AMantas GRodriguez JNeves J(2017)An efficient homomorphic MAC-based scheme against data and tag pollution attacks in network coding-enabled wireless networksInternational Journal of Information Security10.1007/s10207-016-0351-z16:6(627-639)Online publication date: 1-Nov-2017
https://dl.acm.org/doi/10.1007/s10207-016-0351-z
Show More Cited By

On counteracting byzantine attacks in network coded peer-to-peer networks
1. Networks
2. Software and its engineering
  1. Software organization and properties
    1. Software system structures

Recommendations

Byzantine attacks against network coding in peer to peer distributed storage
ISIT'09: Proceedings of the 2009 IEEE international conference on Symposium on Information Theory - Volume 2

We consider the impact of Byzantine attackers on peer-to-peer topologies for distributed storage using network coding. First, the problem is formulated as one of data flow in random evolving graphs, in which a data source and a data collector are ...
Bottleneck discovery and overlay management in network coded peer-to-peer systems
INM '07: Proceedings of the 2007 SIGCOMM workshop on Internet network management

The performance of peer-to-peer (P2P) networks depends critically on the good connectivity of the overlay topology. In this paper we study P2P networks for content distribution (such as Avalanche) that use randomized network coding techniques. The basic ...
Efficient resource discovery in self-organized unstructured peer-to-peer networks

In unstructured peer-to-peer (P2P) networks, two autonomous peer nodes can be connected if users in those nodes are interested in each other's data. Owing to the similarity between P2P networks and social networks, where peer nodes can be regarded as ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Journal on Selected Areas in Communications

IEEE Journal on Selected Areas in Communications Volume 28, Issue 5

June 2010

139 pages

ISSN:0733-8716

Issue’s Table of Contents

Copyright © 2010.

Publisher

IEEE Press

Publication History

Published: 01 June 2010

Revised: 20 December 2009

Received: 14 April 2009

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lawrence TLi FAli IHaruna CKpiebaareh MChristopher T(2022)A computationally efficient HMAC-based authentication scheme for network codingTelecommunications Systems10.1007/s11235-021-00842-679:1(47-69)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1007/s11235-021-00842-6
Sassatelli LMédard MHamdan HToral-Cruz HAkleylek SMcheick HBoubiche D(2017)Thwarting pollution attacks in network coding for delay tolerant mobile social networksProceedings of the Second International Conference on Internet of things, Data and Cloud Computing10.1145/3018896.3018960(1-7)Online publication date: 22-Mar-2017
https://dl.acm.org/doi/10.1145/3018896.3018960
Esfahani AMantas GRodriguez JNeves J(2017)An efficient homomorphic MAC-based scheme against data and tag pollution attacks in network coding-enabled wireless networksInternational Journal of Information Security10.1007/s10207-016-0351-z16:6(627-639)Online publication date: 1-Nov-2017
https://dl.acm.org/doi/10.1007/s10207-016-0351-z
Talooki VBassoli RLucani DRodriguez JFitzek FMarques HTafazolli R(2015)Security concerns and countermeasures in network coding based communication systemsComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2015.03.01083:C(422-445)Online publication date: 4-Jun-2015
https://dl.acm.org/doi/10.1016/j.comnet.2015.03.010

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents