Practical defenses against pollution attacks in intra-flow network coding for wireless mesh networks

ABSTRACT

Recent studies show that network coding can provide significant benefits to network protocols, such as increased throughput, reduced network congestion, higher reliability, and lower power consumption. The core principle of network coding is that intermediate nodes actively mix input packets to produce output packets. This mixing subjects network coding systems to a severe security threat, known as a \emph{pollution attack}, where attacker nodes inject corrupted packets into the network. Corrupted packets propagate in an epidemic manner, depleting network resources and significantly decreasing throughput. Pollution attacks are particularly dangerous in wireless networks, where attackers can easily inject packets or compromise devices due to the increased network vulnerability.

In this paper, we address pollution attacks against network coding systems in wireless mesh networks. We demonstrate that previous solutions to the problem are impractical in wireless networks, incurring an unacceptably high degradation of throughput. We propose a lightweight scheme, DART, that uses time-based authentication in combination with random linear transformations to defend against pollution attacks. We further improve system performance and propose EDART, which enhances DART with an optimistic forwarding scheme. A detailed security analysis shows that the probability of a polluted packet passing our verification procedure is very low. Performance results using the well-known MORE protocol and realistic link quality measurements from the Roofnet experimental testbed show that our schemes improve system performance over 20 times compared to previous solutions.

REFERENCES

• 1: R. Ahlswede, N. Cai, S.-Y. Li, and R. Yeung, "Network information flow," Information Theory, IEEE Transactions on, vol. 46, no. 4, pp. 1204--1216, 2000.
• 2: S. Katti, D. Kabati, W. Hu, H. Rahul, and M. Medard, "The importance of being opportunistic: Practical network coding for wireless environments," in In Proc. of Allerton Conf. on Commun. Control and Computing, Oct. 2005.
• 3: Szymon Chachulski , Michael Jennings , Sachin Katti , Dina Katabi, Trading structure for randomness in wireless opportunistic routing, ACM SIGCOMM Computer Communication Review, v.37 n.4, October 2007
• 4: C. Gkantsidis and P. Rodriguez, "Network coding for large scale content distribution," in In Proc. IEEE Infocom, Mar. 2005.
• 5: A. G. Dimakis, P. B. Godfrey, M. J. Wainwright, and K. Ramchandran, "The benefits of network coding for peer-to-peer storage systems," in Third Workshop on Network Coding, Theory, and Applications, 2007.
• 6: C.Fragouli and A.Markopoulou, "A network coding approach to overlay network monitoring," in Allerton 2005.
• 7: C. Fragouli , A. Markopoulou, Network Coding Techniques for Network Monitoring: a Brief Introduction, Proceedings of the 2006 International Zurich Seminar on Communications, p.82-83, February 21-24, 2006 [doi>10.1109/IZS.2006.1649084]
• 8: T. Ho, B. Leong, Y.-H. Chang, Y. Wen, and R. Koetter, "Network monitoring in multicast networks using network coding," in ISIT, 2005.
• 9: M. Effros, T. Ho, and S. Kim, "A tiling approach to network code design for wireless networks," in IEEE Information Theory Workshop, 2006.
• 10: J. Jin, T. Ho, and H. Viswanathan, "Comparison of network coding and non-network coding schemes for multi-hop wireless networks," in ISIT 2006.
• 11: A. F. Dana, R. Gowaikar, R. Palanki, B. Hassibi, and M. Effros, "Capacity of wireless erasure networks," IEEE Trans. on Information Theory, vol. 52, 2006.
• 12: S. Deb and M. Medard, "Algebraic gossip: A network coding approach to optimal multiple rumor mongering," IEEE Trans. on Info. Theory, 2006.
• 13: Jörg Widmer , Jean-Yves Le Boudec, Network coding for efficient communication in extreme networks, Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, p.284-291, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080139.1080147]
• 14: D. S. Lun, M. Médard, R. Koetter, and M. Effros, "Further results on coding for reliable communication over packet networks," in ISIT, 2005.
• 15: Y. W. P. A. Chou and S.-Y. Kung, "Minimum-energy multicast in mobile ad hoc networks using network coding," IEEE Transactions on Communications, 2005.
• 16: D. S. Lun, N. Ratnakar, R. Koetter, M. M. edard, E. Ahmed, and H. Lee, "Achieving minimum cost multicast: A decentralized approach based on network coding," in Proceeding of IEEE Infocom, 2005.
• 17: J. Widmer, C. Fragouli, and J.-Y. L. Boudec, "Energy-efficient broadcasting in wireless ad-hoc networks," in Netcod 2005, Italy, April 2005.
• 18: K. Jain, "On the power (saving) of network coding," in Allerton, 2005.
• 19: T. Ho, "On constructive network coding for multiple unicasts," in 44th annual Allerton Conference on Communication, Control and Computing, 2006.
• 20: D. Traskov, N. Ratnakar, D. S. Lun, R. Koetter, and M. Médard, "Network coding for multiple unicasts: An approach based on linear optimization," in Proceedings of the International Symposium on Information Theory, 2006.
• 21: Sachin Katti , Hariharan Rahul , Wenjun Hu , Dina Katabi , Muriel Médard , Jon Crowcroft, XORs in the air: practical wireless network coding, ACM SIGCOMM Computer Communication Review, v.36 n.4, October 2006
• 22: B. Radunovic, C. Gkantsidis, S. G. P. Key, W. Hu, and P. Rodriguez, "Multipath code casting for wireless mesh networks," Microsoft Research, Technical Report MSR-TR-2007-68, March 2007.
• 23: J.-S. Park, M. Gerla, D. S. Lun, Y. Yi, and M. Medard, "Codecast: a network-coding-based ad hoc multicast protocol," IEEE Wireless Comm., 2006.
• 24: M. Médard, M. Effros, T. Ho, and D. R. Karger, "On coding for non-multicast networks," in Allerton, 2003.
• 25: I.-H. Hou, Y.-E. Tsai, T. Abdelzaher, and I. Gupta, "Adapcode: Adaptive network coding for code updates in wireless sensor networks," in INFOCOM, 2008.
• 26: L. Li, R. Ramjee, M. Buddhikot, and S. Miller, "Network coding-based broadcast in mobile ad-hoc networks," Proc. of INFOCOM 2007.
• 27: C. Fragouli, J. Widmer, and J.-Y. Le Boudec, "A network coding approach to energy efficient broadcasting: From theory to practice," INFOCOM 2006.
• 28: J. Dong, R. Curtmola, R. Sethi, and C. Nita-Rotaru, "Toward secure network coding in wireless networks: Threats and challenges," in NPSec, 2008.
• 29: D. Charles, K. Jain, and K. Lauter, "Signatures for network coding," 40th Annual Conference on Information Sciences and Systems, 2006.
• 30: Z. Yu, Y. Wei, B. Ramkumar, and Y. Guan, "An efficient signature-based scheme for securing network coding against pollution attacks," in Proceedings of INFOCOM 08, Phoenix, AZ, April 2008.
• 31: F. Zhao, T. Kalker, M. Medard, and K. Han, "Signatures for content distribution with network coding," ISIT 2007.
• 32: Qiming Li , Dah-ming Chiu , John C. S. Lui, On the Practical and Security Issues of Batch Content Distribution Via Network Coding, Proceedings of the Proceedings of the 2006 IEEE International Conference on Network Protocols, p.158-167, November 12-15, 2006 [doi>10.1109/ICNP.2006.320209]
• 33: M. Krohn, M. Freedman, and D. Mazieres, "On-the-fly verification of rateless erasure codes for efficient content distribution," Security and Privacy, 2004. Proceedings. 2004 IEEE Symposium on, pp. 226--240, 9-12 May 2004.
• 34: C. Gkantsidis and P. Rodriguez Rodriguez, "Cooperative security for network coding file distribution," Proc. of INFOCOM 2006.
• 35: T. Ho, B. Leong, R. Koetter, M. Medard, M. Effros, and D. Karger, "Byzantine modification detection in multicast networks using randomized network coding," ISIT 2004.
• 36: S. Jaggi, M. Langberg, S. Katti, T. Ho, D. Katabi, and M. Medard, "Resilient network coding in the presence of byzantine adversaries," INFOCOM 2007.
• 37: D. Wang, D. Silva, and F. R. Kschischang, "Constricting the adversary: A broadcast transformation for network coding," Allerton 2007, 2007.
• 38: "MIT roofnet." http://pdos.csail.mit.edu/roofnet/doku.php.
• 39: D. Boneh, D. Freeman, J. Katz, and B. Waters, "Signing a linear subspace: Signature schemes for network coding," in Proc. of PKC '09, 2009.
• 40: D. Silva, F. Kschischang, and R. Koetter, "A rank-metric approach to error control in random network coding," IEEE Inf. Theory for Wireless Ntwks, 2007.
• 41: R. Koetter and F. R. Kschischang, "Coding for errors and erasures in random network coding," Information Theory, IEEE Transactions on, 2008.
• 42: R. W. Yeung and N. Cai, "Network error correction, part i: basic concepts and upper bounds," Commun. Inf. Syst., vol. 6, no. 1, pp. 19--36, 2006.
• 43: N. Cai and R. W. Yeung, "Network error correction, part ii: lower bounds," Commun. Inf. Syst., vol. 6, no. 1, pp. 37--54, 2006.
• 44: P. Chou and Y. Wu, "Network coding for the internet and wireless networks," Signal Processing Magazine, IEEE, vol. 24, no. 5, pp. 77--85, Sept. 2007.
• 45: Y. Lin, B. Li, and B. Liang, "Efficient network coded data transmissions in disruption tolerant networks," in Proc. of INFOCOM 2008.
• 46: T. Cui, L. Chen, and T. Ho, "Energy efficient opportunistic network coding for wireless networks," in Proceedings of INFOCOM 08, Phoenix, AZ, April 2008.
• 47: A. Perrig, R. Canetti, J. D. Tygar, and D. Song, "The TESLA broadcast authentication protocol," RSA CryptoBytes, vol. 5, no. Summer, 2002.
• 48: A. Perrig, R. Canetti, D. Song, and D. Tygar, "Efficient and secure source authentication for multicast," in Proc. of NDSS '01, 2001.
• 49: Adrian Perrig , Robert Szewczyk , J. D. Tygar , Victor Wen , David E. Culler, SPINS: security protocols for sensor networks, Wireless Networks, v.8 n.5, p.521-534, September 2002 [doi>10.1023/A:1016598314198]
• 50: K. Sun, P. Ning, and C. Wang, "Secure and resilient clock synchronization in wireless sensor networks," JSAC, vol. 24, no. 2, Feb. 2006.
• 51: J. Dong, R. Curtmola, and C. Nita-Rotaru, "Practical defenses against pollution attacks in intra-flow network coding for wireless mesh networks," Purdue University, Technical Report, 2009.
• 52: Douglas S. J. De Couto , Daniel Aguayo , John Bicket , Robert Morris, A high-throughput path metric for multi-hop wireless routing, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939000]
• 53: Daniel Aguayo , John Bicket , Sanjit Biswas , Glenn Judd , Robert Morris, Link-level measurements from an 802.11b mesh network, ACM SIGCOMM Computer Communication Review, v.34 n.4, October 2004
• 54: John Bicket , Daniel Aguayo , Sanjit Biswas , Robert Morris, Architecture and evaluation of an unplanned 802.11b mesh network, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080833]
• 55: Sanjit Biswas , Robert Morris, Opportunistic routing in multi-hop wireless networks, ACM SIGCOMM Computer Communication Review, v.34 n.1, January 2004 [doi>10.1145/972374.972387]
• 56: "Glomosim," http://pcl.cs.ucla.edu/projects/glomosim/.
• 57: Kun Sun , Peng Ning , Cliff Wang, TinySeRSync: secure and resilient time synchronization in wireless sensor networks, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA [doi>10.1145/1180405.1180439]
• 58: Digital Signature Standard (DSS). National Institute for Standards and Technology (NIST), 2006, no. FIPS 186-3.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.m Miscellaneous

General Terms:
Performance, Security

Keywords:
network coding, network coding security, pollution attacks, security, wireless network security