REAct: resource-efficient accountability for nodemisbehavior in ad hoc networks based on random audits

ABSTRACT

Wireless ad hoc networks rely on multi-hop routes to transport data from source to destination. The routing function is implemented in a collaborative manner, with each node responsible for relaying traffic to the destination. However, an increasingly sophisticated pool of users with easy access to commercial wireless devices, combined with the poor physical and software security of the devices, can lead to node misconfiguration or misbehavior. A misbehaving node may refuse to forward packets in order to conserve its energy (selfishness), or simply degrade network performance (maliciousness).

In this paper, we investigate the problem of uniquely identifying the set of misbehaving nodes who refuse to forward packets. We propose a novel misbehavior identification scheme called REAct that provides resource-efficient accountability for node misbehavior. REAct identifies misbehaving nodes based on a series of random audits triggered upon a performance drop. We show that a source-destination pair using REAct can identify any number of independently misbehaving nodes based on behavioral proofs provided by nodes. Proofs are constructed using Bloom filters which are storage-efficient membership structures, thus significantly reducing the communication overhead for misbehavior detection.

REFERENCES

• 1: Baruch Awerbuch , David Holmer , Cristina Nita-Rotaru , Herbert Rubens, An on-demand secure routing protocol resilient to byzantine failures, Proceedings of the 1st ACM workshop on Wireless security, p.21-30, September 28-28, 2002, Atlanta, GA, USA [doi>10.1145/570681.570684]
• 2: K. Balakrishnan, J. Deng, and P. K. Varshney. Twoack: Preventing selfishness in mobile ad hoc networks. In WCNC 2005, 2005.
• 3: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 4: A. Broder and M. Mitzenmacher. Network applications of Bloom filters: A survey. Internet Mathematics, 1(4):485--509, 2004.
• 5: 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]
• 6: S. Buchegger and J.-Y. L. Boudec. Self-policing mobile ad-hoc networks by reputation systems. IEEE Communications Magazine, pages 101--107, 2005.
• 7: 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]
• 8: Joan G. Dyer , Mark Lindemann , Ronald Perez , Reiner Sailer , Leendert van Doorn , Sean W. Smith , Steve Weingart, Building the IBM 4758 Secure Coprocessor, Computer, v.34 n.10, p.57-66, October 2001 [doi>10.1109/2.955100]
• 9: L. M. Feeney and M. Nilsson. Investigating the energy consumption of a wireless network interface in an ad hoc networking environment. In INFOCOM 2001.
• 10: V. Gligor. Handling new adversaries in secure mobile ad-hoc networks. In ESNS 2007, 2007.
• 11: Q. He, D. Wu, and P. Khosla. Sori: A secure and objective reputation-based incentive scheme for ad hoc networks. In WCNC 2004, 2004.
• 12: M. Jakobsson, J.-P. Hubaux, and L. Buttyan. A micropayment scheme encouraging collaboration in multi-hop cellular networks. In Financial Crypto, 2003.
• 13: D. Johnson, D. Maltz, and Y.-C. Hu. The dynamic source routing protocol for mobile ad hoc networks draft-ietf-manet-dsr-09.txt, 2003.
• 14: An Liu , Peng Ning, TinyECC: A Configurable Library for Elliptic Curve Cryptography in Wireless Sensor Networks, Proceedings of the 7th international conference on Information processing in sensor networks, p.245-256, April 22-24, 2008 [doi>10.1109/IPSN.2008.47]
• 15: Kejun Liu , Jing Deng , Pramod K. Varshney , Kashyap Balakrishnan, An Acknowledgment-Based Approach for the Detection of Routing Misbehavior in MANETs, IEEE Transactions on Mobile Computing, v.6 n.5, p.536-550, May 2007 [doi>10.1109/TMC.2007.1036]
• 16: Y. Liu and Y. R. Yang. Reputation propagation and agreement in mobile ad-hoc networks. In WCNC 2003, pages 1510--1515, March 2003.
• 17: 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]
• 18: M. Mathis , J. Mahdavi , S. Floyd , A. Romanow, TCP Selective Acknowledgement Options, RFC Editor, 1996
• 19: 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
• 20: Venkata N. Padmanabhan , Daniel R. Simon, Secure traceroute to detect faulty or malicious routing, ACM SIGCOMM Computer Communication Review, v.33 n.1, p.77-82, January 2003 [doi>10.1145/774763.774775]
• 21: K. Paul and D. Westhoff. Context aware detection of selfish nodes in dsr based ad-hoc networks. In IEEE Globecom, 2002.
• 22: Yuan Xue , Klara Nahrstedt, Providing Fault-Tolerant Ad hoc Routing Service in Adversarial Environments, Wireless Personal Communications: An International Journal, v.29 n.3-4, p.367-388, June 2004 [doi>10.1023/B:WIRE.0000047071.75971.cd]
• 23: S. Zhong, J. Chen, and Y. R. Yang. Sprite: A simple cheat-proof, credit-based system for mobile ad-hoc networks. In INFOCOM 2003, pages 1987--1997.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

General Terms:
Security

Keywords:
ad hoc networks, bloom filter, misbehavior, routing