Towards event source unobservability with minimum network traffic in sensor networks

ABSTRACT

Sensors deployed to monitor the surrounding environment report such information as event type, location, and time when a real event of interest is detected. An adversary may identify the real event source through eavesdropping and traffic analysis. Previous work has studied the source location privacy problem under a local adversary model. In this work, we aim to provide a stronger notion: event source unobservability, which promises that a global adversary cannot know whether a real event has ever occurred even if he is capable of collecting and analyzing all the messages in the network at all the time. Clearly, event source unobservability is a desirable and critical security property for event monitoring applications, but unfortunately it is also very difficult and expensive to achieve for resource-constrained sensor network.

Our main idea is to introduce carefully chosen dummy traffic to hide the real event sources in combination with mechanisms to drop dummy messages to prevent explosion of network traffic. To achieve the latter, we select some sensors as proxies that proactively filter dummy messages on their way to the base station. Since the problem of optimal proxy placement is NP-hard, we employ local search heuristics. We propose two schemes (i) Proxy-based Filtering Scheme (PFS) and (ii) Tree-based Filtering Scheme (TFS) to accurately locate proxies. Simulation results show that our schemes not only quickly find nearly optimal proxy placement, but also significantly reduce message overhead and improve message delivery ratio. A prototype of our scheme was implemented for TinyOS-based Mica2 motes.

REFERENCES

• 1: Csim 19, http://www.mesquite.com/.
• 2: Glomosim, http://pcl.cs.ucla.edu/projects/glomosim/.
• 3: Mica2 mote, http://www.xbow.com/.
• 4: TinyOS. http://www.tinyos.net.
• 5: Anonymity bibliography, http://freehaven.net/anonbib/date.html, 2005.
• 6: Vijay Arya , Naveen Garg , Rohit Khandekar , Kamesh Munagala , Vinayaka Pandit, Local search heuristic for k-median and facility location problems, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.21-29, July 2001, Hersonissos, Greece [doi>10.1145/380752.380755]
• 7: Oliver Berthold , Hannes Federrath , Stefan Köpsell, Web MIXes: a system for anonymous and unobservable Internet access, International workshop on Designing privacy enhancing technologies: design issues in anonymity and unobservability, p.115-129, January 2001, Berkeley, California, United States
• 8: David L. Chaum, Untraceable electronic mail, return addresses, and digital pseudonyms, Communications of the ACM, v.24 n.2, p.84-90, Feb. 1981 [doi>10.1145/358549.358563]
• 9: Jing Deng , Richard Han , Shivakant Mishra, Intrusion Tolerance and Anti-Traffic Analysis Strategies For Wireless Sensor Networks, Proceedings of the 2004 International Conference on Dependable Systems and Networks, p.637, June 28-July 01, 2004
• 10: C. Díaz and B. Preneel. Taxonomy of mixes and dummy traffic. In Proceedings of I-NetSec04: 3rd Working Conference on Privacy and Anonymity in Networked and Distributed Systems, 2004.
• 11: S. Fischer-Hubner. Privacy Enhancing Technologies, volume 1958. Springer Berlin Heidelberg, 2001.
• 12: David M. Goldschlag , Michael G. Reed , Paul F. Syverson, Hiding Routing Information, Proceedings of the First International Workshop on Information Hiding, p.137-150, May 30-June 01, 1996
• 13: Baik Hoh , Marco Gruteser, Protecting Location Privacy Through Path Confusion, Proceedings of the First International Conference on Security and Privacy for Emerging Areas in Communications Networks, p.194-205, September 05-09, 2005 [doi>10.1109/SECURECOMM.2005.33]
• 14: Pandurang Kamat , Yanyong Zhang , Wade Trappe , Celal Ozturk, Enhancing Source-Location Privacy in Sensor Network Routing, Proceedings of the 25th IEEE International Conference on Distributed Computing Systems, p.599-608, June 06-10, 2005 [doi>10.1109/ICDCS.2005.31]
• 15: Brad Karp , H. T. Kung, GPSR: greedy perimeter stateless routing for wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.243-254, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345953]
• 16: Dogan Kesdogan , Jan Egner , Roland Büschkes, Stop-and-Go-MIXes Providing Probabilistic Anonymity in an Open System, Proceedings of the Second International Workshop on Information Hiding, p.83-98, April 14-17, 1998
• 17: Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
• 18: Jiejun Kong , Xiaoyan Hong, ANODR: anonymous on demand routing with untraceable routes for mobile ad-hoc networks, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778449]
• 19: Madhukar R. Korupolu , C. Greg Plaxton , Rajmohan Rajaraman, Analysis of a local search heuristic for facility location problems, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.1-10, January 25-27, 1998, San Francisco, California, United States
• 20: W. Zhang, M. Tran, S. Zhu, and G. Cao. A Compromise-Resilient Scheme for Pairwise Key Establishment in Dynamic Sensor Networks. In ACM Mobihoc, 2007.
• 21: Donggang Liu , Peng Ning , Wenliang Kevin Du, Attack-resistant location estimation in sensor networks, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 22: K. Mehta, D. Liu, and M. Wright. Location privacy in sensor networks against a global eavesdropper. In ICNP, 2007.
• 23: U. Möller, L. Cottrell, P. Palfrader, and L. Sassaman. Mixmaster Protocol - Version 2. Draft, July 2003.
• 24: Celal Ozturk , Yanyong Zhang , Wade Trappe, Source-location privacy in energy-constrained sensor network routing, Proceedings of the 2nd ACM workshop on Security of ad hoc and sensor networks, October 25-25, 2004, Washington DC, USA [doi>10.1145/1029102.1029117]
• 25: Robert Cimikowski , Edward Mooney, Proximity-based adjacency determination for facility layout, Computers and Industrial Engineering, v.32 n.2, p.341-349, April 1997 [doi>10.1016/S0360-8352(96)00299-9]
• 26: S. Ratnasamy, D. Estrin, R. Govindan, B. Karp, L. Yin, S. Shenker, and F. Yu. Data-centric storage in sensornets. In Proceedings of ACM First Workshop on Hot Topics in Networks, 2001.
• 27: M. Shao, S. Zhu, W. Zhang, and G. Cao. pDCS: Security and privacy support for data-centric sensor networks. In IEEE INFOCOM, 2007.
• 28: M. Shao, Y. Yang, S. Zhu, and G. Cao. Towards Statistically Strong Source Anonymity for Sensor Networks. In IEEE INFOCOM, 2008.
• 29: David B. Shmoys , Éva Tardos , Karen Aardal, Approximation algorithms for facility location problems (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.265-274, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258600]
• 30: Y. Xi, L. Schwiebert, and W. Shi. Preserving source location privacy in monitoring-based wireless sensor networks. In SSN '06.
• 31: Y. Zhang, W. Liu, , and W. Lou. Anonymous communications in mobile ad hoc networks. In IEEE INFOCOM, 2005.
• 32: Bo Zhu , Zhiguo Wan , Mohan S. Kankanhalli , Feng Bao , Robert H. Deng, Anonymous Secure Routing in Mobile Ad-Hoc Networks, Proceedings of the 29th Annual IEEE International Conference on Local Computer Networks, p.102-108, November 16-18, 2004 [doi>10.1109/LCN.2004.21]
• 33: Ye Zhu , Riccardo Bettati, Compromising Location Privacy inWireless Networks Using Sensors with Limited Information, Proceedings of the 27th International Conference on Distributed Computing Systems, p.24, June 25-27, 2007 [doi>10.1109/ICDCS.2007.94]

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
          Subjects: Wireless communication

  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.1 Public Policy Issues
          Subjects: Privacy
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)

General Terms:
Algorithms, Performance, Security

Keywords:
event unobservability, global observer, minimum traffic, proxy, sensor network privacy