ODSBR: An on-demand secure Byzantine resilient routing protocol for wireless ad hoc networks

ABSTRACT

Ah hoc networks offer increased coverage by using multihop communication. This architecture makes services more vulnerable to internal attacks coming from compromised nodes that behave arbitrarily to disrupt the network, also referred to as Byzantine attacks. In this work, we examine the impact of several Byzantine attacks performed by individual or colluding attackers. We propose ODSBR, the first on-demand routing protocol for ad hoc wireless networks that provides resilience to Byzantine attacks caused by individual or colluding nodes. The protocol uses an adaptive probing technique that detects a malicious link after log n faults have occurred, where n is the length of the path. Problematic links are avoided by using a route discovery mechanism that relies on a new metric that captures adversarial behavior. Our protocol never partitions the network and bounds the amount of damage caused by attackers. We demonstrate through simulations ODSBR's effectiveness in mitigating Byzantine attacks. Our analysis of the impact of these attacks versus the adversary's effort gives insights into their relative strengths, their interaction, and their importance when designing multihop wireless routing protocols.

REFERENCES

• 1: The network simulator - ns2. http://www.isi.edu/nsnam/ns/.
• 2: 1999a. IEEE Std 802.11a-1999. http://standards.ieee.org/.
• 3: 1999b. IEEE Std 802.11b-1999. http://standards.ieee.org/.
• 4: AES. 2001. Advanced Encryption Standard. Number FIPS 197. National Institute for Standards and Technology (NIST). http://csrc.nist.gov/encryption/aes/.
• 5: Baruch Awerbuch , David Holmer , Herbert Rubens, The medium time metric: high throughput route selection in multi-rate ad hoc wireless networks, Mobile Networks and Applications, v.11 n.2, p.253-266, April 2006 [doi>10.1007/s11036-005-4477-x]
• 6: Bradley, K. A., Cheung, S., Puketza, N., Mukherjee, B., and Olsson, R. A. 1998. Detecting disruptive routers: A distributed network monitoring approach. In Proceedings of IEEE Symposium on Security and Privacy.
• 7: Michael Brown , Donny Cheung , Darrel Hankerson , Julio Lopez Hernandez , Michael Kirkup , Alfred Menezes, PGP in constrained wireless devices, Proceedings of the 9th conference on USENIX Security Symposium, p.19-19, August 14-17, 2000, Denver, Colorado
• 8: Sonja Buchegger , Jean-Yves Le Boudec, Performance analysis of the CONFIDANT protocol, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513828]
• 9: Levente Buttyán , Jean-Pierre Hubaux, Stimulating cooperation in self-organizing mobile ad hoc networks, Mobile Networks and Applications, v.8 n.5, p.579-592, October 2003 [doi>10.1023/A:1025146013151]
• 10: Steven Cheung , Karl N. Levitt, Protecting routing infrastructures from denial of service using cooperative intrusion detection, Proceedings of the 1997 workshop on New security paradigms, p.94-106, September 23-26, 1997, Langdale, Cumbria, United Kingdom [doi>10.1145/283699.283744]
• 11: 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]
• 12: DSS. 2006. Digital Signature Standard. Number FIPS 186-3. National Institute for Standards and Technology (NIST). http://csrc.nist.gov/publications/drafts/fips_186-3/Draft-FIPS-186-3_March2006.pdf.
• 13: Jakob Eriksson , Srikanth Krishnamurthy , Michalis Faloutsos, TrueLink: A Practical Countermeasure to the Wormhole Attack in Wireless Networks, Proceedings of the Proceedings of the 2006 IEEE International Conference on Network Protocols, p.75-84, November 12-15, 2006 [doi>10.1109/ICNP.2006.320200]
• 14: R. Hauser , T. Przygienda , G. Tsudik, Reducing The Cost Of Security In Link-State Routing, Proceedings of the 1997 Symposium on Network and Distributed System Security, p.93, February 10-11, 1997
• 15: HMAC. 2002. The Keyed-Hash Message Authentication Code. Number FIPS 198. National Institute for Standards and Technology (NIST). http://csrc.nist.gov/publications/fips/index.html.
• 16: Hu, L. and Evans, D. 2004. Using directional antennas to prevent wormhole attacks. In Proceedings of ISOC Symposium of Network and Distributed Systems Security (NDSS).
• 17: Yih-Chun Hu , David B. Johnson , Adrian Perrig, SEAD: Secure Efficient Distance Vector Routing for Mobile Wireless Ad Hoc Networks, Proceedings of the Fourth IEEE Workshop on Mobile Computing Systems and Applications, p.3, June 20-21, 2002
• 18: Yih-Chun Hu , Adrian Perrig , David B. Johnson, Ariadne: a secure on-demand routing protocol for ad hoc networks, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570648]
• 19: Hu, Y.-C., Perrig, A., and Johnson, D. B. 2003a. Packet leashes: A defense against wormhole attacks in wireless ad hoc networks. In Proceedings of IEEE Conference of the IEEE Communications Society (INFOCOMM).
• 20: Yih-Chun Hu , Adrian Perrig , David B. Johnson, Rushing attacks and defense in wireless ad hoc network routing protocols, Proceedings of the 2nd ACM workshop on Wireless security, September 19-19, 2003, San Diego, CA, USA [doi>10.1145/941311.941317]
• 21: Jean-Pierre Hubaux , Levente Buttyán , Srdan Capkun, The quest for security in mobile ad hoc networks, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501436.501437]
• 22: IEEE. 1999. IEEE Std 802.11, 1999 Edition. http://standards.ieee.org/catalog/olis/lanman.html.
• 23: Jakobsson, M., Wetzel, S., and Yener, B. 2003. Stealth attacks on ad-hoc wireless networks. In IEEE Vehicular Technology Conference.
• 24: David B. Johnson , David A. Maltz , Josh Broch, DSR: the dynamic source routing protocol for multihop wireless ad hoc networks, Ad hoc networking, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2001
• 25: Kent, S., Lynn, C., and Seo, K. 2000. Secure border gateway protocol (s-bgp). IEEE Journal on Selected Areas in Communication 18, 4.
• 26: James F. Kurose , Keith W. Ross, Computer Networking: A Top-Down Approach Featuring the Internet Package, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 27: Leslie Lamport , Robert Shostak , Marshall Pease, The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.382-401, July 1982 [doi>10.1145/357172.357176]
• 28: Lee, H. I. 2002. Afora: Ad hoc routing in the face of misbehaving nodes. Master's Thesis, MIT.
• 29: Henrik Lundgren , Erik Nordströ , Christian Tschudin, Coping with communication gray zones in IEEE 802.11b based ad hoc networks, Proceedings of the 5th ACM international workshop on Wireless mobile multimedia, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570790.570799]
• 30: Sergio Marti , T. J. Giuli , Kevin Lai , Mary Baker, Mitigating routing misbehavior in mobile ad hoc networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.255-265, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345955]
• 31: Alfred J. Menezes , Scott A. Vanstone , Paul C. Van Oorschot, Handbook of Applied Cryptography, CRC Press, Inc., Boca Raton, FL, 1996
• 32: Pietro Michiardi , Refik Molva, Core: a collaborative reputation mechanism to enforce node cooperation in mobile ad hoc networks, Proceedings of the IFIP TC6/TC11 Sixth Joint Working Conference on Communications and Multimedia Security: Advanced Communications and Multimedia Security, p.107-121, September 26-27, 2002
• 33: Alper Tugay Mizrak, Fatih: Detecting and Isolating Malicious Routers, Proceedings of the 2005 International Conference on Dependable Systems and Networks, p.538-547, June 28-July 01, 2005 [doi>10.1109/DSN.2005.49]
• 34: Papadimitratos, P. and Haas, Z. 2002. Secure routing for mobile ad hoc networks. In SCS Communication Networks and Distributed Systems Modeling and Simulation Conference (CNDS). 27--31.
• 35: Panagiotis Papadimitratos , Zygmunt J. Haas, Secure data transmission in mobile ad hoc networks, Proceedings of the 2nd ACM workshop on Wireless security, September 19-19, 2003, San Diego, CA, USA [doi>10.1145/941311.941318]
• 36: Charles E. Perkins , Pravin Bhagwat, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, Proceedings of the conference on Communications architectures, protocols and applications, p.234-244, August 31-September 02, 1994, London, United Kingdom
• 37: Perkins, C. E. and Royer, E. M. 2000. Ad hoc Networking. Addison-Wesley, Reading, MA. Chapter Ad hoc On-Demand Distance Vector Routing.
• 38: Perlman, R. 1988. Network layer protocols with byzantine robustness. Ph.D. thesis, MIT LCS TR-429.
• 39: Perlman, R. 2005. Routing with byzantine robustness. Tech. Rep. TR-2005-146, Sun Microsystems.
• 40: Perrig, A., Canetti, R., Song, D., and Tygar, D. 2001. Efficient and secure source authentication for multicast. In Proceedings of ISOC Symposium of Network and Distributed Systems Security (NDSS).
• 41: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
• 42: Kimaya Sanzgiri , Bridget Dahill , Brian Neil Levine , Clay Shields , Elizabeth M. Belding-Royer, A Secure Routing Protocol for Ad Hoc Networks, Proceedings of the 10th IEEE International Conference on Network Protocols, p.78-89, November 12-15, 2002
• 43: Bradley R. Smith , Shree Murthy , J. J. Garcia-Luna-Aceves, Securing Distance-Vector Routing Protocols, Proceedings of the 1997 Symposium on Network and Distributed System Security, p.85, February 10-11, 1997
• 44: Jonathan Stone , Craig Partridge, When the CRC and TCP checksum disagree, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.309-319, August 28-September 01, 2000, Stockholm, Sweden
• 45: Paul F. Syverson , David M. Goldschlag , Michael G. Reed, Anonymous Connections and Onion Routing, Proceedings of the 1997 IEEE Symposium on Security and Privacy, p.44, May 04-07, 1997
• 46: George Theodorakopoulos , John S. Baras, Trust evaluation in ad-hoc networks, Proceedings of the 3rd ACM workshop on Wireless security, October 01-01, 2004, Philadelphia, PA, USA [doi>10.1145/1023646.1023648]
• 47: Yoon, J., Liu, M., and Noble, B. D. 2003. Random waypoint considered harmful. In Proceedings of IEEE Conference of the IEEE Communications Society (INFOCOMM). San Francisco, CA.
• 48: Zhou, L. and Haas, Z. 1999. Securing ad hoc networks. IEEE Network Magazine 13, 6.
• 49: Philip R. Zimmermann, The official PGP user's guide, MIT Press, Cambridge, MA, 1995

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
      C.2.2 Network Protocols

General Terms:
Algorithms, Design, Reliability, Security, Theory

Keywords:
Ad hoc wireless networks, byzantine failures, on-demand routing, security