Secure multidimensional range queries in sensor networks

ABSTRACT

Most future large-scale sensor networks are expected to follow a two-tier architecture which consists of resource-rich master nodes at the upper tier and resource-poor sensor nodes at the lower tier. Sensor nodes submit data to nearby master nodes which then answer the queries from the network owner on behalf of sensor nodes. Relying on master nodes for data storage and query processing raises severe concerns about data confidentiality and query-result correctness when the sensor network is deployed in hostile environments. In particular, a compromised master node may leak hosted sensitive data to the adversary; it may also return juggled or incomplete query results to the network owner. This paper, for the first time in the literature, presents a suite of novel schemes to secure multidimensional range queries in tiered sensor networks. The proposed schemes can ensure data confidentiality against master nodes and also enable the network owner to verify with very high probability the authenticity and completeness of any query result by inspecting the spatial and temporal relationships among the returned data. Detailed performance evaluations confirm the high efficacy and efficiency of the proposed schemes.

REFERENCES

• 1: Peter Desnoyers , Deepak Ganesan , Prashant Shenoy, TSAR: a two tier sensor storage architecture using interval skip graphs, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA [doi>10.1145/1098918.1098923]
• 2: Bo Sheng , Qun Li , Weizhen Mao, Data storage placement in sensor networks, Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing, May 22-25, 2006, Florence, Italy [doi>10.1145/1132905.1132943]
• 3: M. Shao, S. Zhu, W. Zhang, and G. Cao, "pDCS: Security and privacy support for data-centric sensor networks," in IEEE INFOCOM'07, Anchorage, Alaska, USA, May 2007, pp. 1298--1306.
• 4: B. Sheng and Q. Li, "Verifiable privacy-preserving range query in sensor networks," in IEEE INFOCOM'08, Phoenix, AZ, Apr. 2008, pp. 46--50.
• 5: Omprakash Gnawali , Ki-Young Jang , Jeongyeup Paek , Marcos Vieira , Ramesh Govindan , Ben Greenstein , August Joki , Deborah Estrin , Eddie Kohler, The Tenet architecture for tiered sensor networks, Proceedings of the 4th international conference on Embedded networked sensor systems, October 31-November 03, 2006, Boulder, Colorado, USA [doi>10.1145/1182807.1182823]
• 6: Xin Li , Young Jin Kim , Ramesh Govindan , Wei Hong, Multi-dimensional range queries in sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958500]
• 7: Samuel R. Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TinyDB: an acquisitional query processing system for sensor networks, ACM Transactions on Database Systems (TODS), v.30 n.1, p.122-173, March 2005 [doi>10.1145/1061318.1061322]
• 8: Y. Diao, D. Ganesan, G. Mathur, and P.J. Shenoy, "Rethinking data management for storage-centric sensor networks," in CIDR'07, Asilomar, CA, USA, Jan. 2007, pp. 22--31.
• 9: J. Shi, R. Zhang, and Y. Zhang, "Secure range queries in tiered sensor networks," in IEEE INFOCOM'09, Rio de Janeiro, Brazil, Apr. 2009.
• 10: Hakan Hacigümüş , Bala Iyer , Chen Li , Sharad Mehrotra, Executing SQL over encrypted data in the database-service-provider model, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564717]
• 11: Bijit Hore , Sharad Mehrotra , Gene Tsudik, A privacy-preserving index for range queries, Proceedings of the Thirtieth international conference on Very large data bases, p.720-731, August 31-September 03, 2004, Toronto, Canada
• 12: 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
• 13: Y. Zhang, W. Liu, Y. Fang, and D. Wu, "Secure localization and authentication in ultra-wideband sensor networks," IEEE J. Select. Areas Commun., Special Issue on UWB Wireless Communications -- Theory and Applications, vol. 24, no. 4, pp. 829--835, Apr. 2006.
• 14: Wensheng Zhang , Hui Song , Sencun Zhu , Guohong Cao, Least privilege and privilege deprivation: towards tolerating mobile sink compromises in wireless sensor networks, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA [doi>10.1145/1062689.1062737]
• 15: Laurent Eschenauer , Virgil D. Gligor, A key-management scheme for distributed sensor networks, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA [doi>10.1145/586110.586117]
• 16: Haowen Chan , Adrian Perrig , Dawn Song, Random Key Predistribution Schemes for Sensor Networks, Proceedings of the 2003 IEEE Symposium on Security and Privacy, p.197, May 11-14, 2003
• 17: Sencun Zhu , Sanjeev Setia , Sushil Jajodia, LEAP: efficient security mechanisms for large-scale distributed sensor networks, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948120]
• 18: Donggang Liu , Peng Ning, Establishing pairwise keys in distributed sensor networks, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948119]
• 19: Y. Zhang, W. Liu, W. Lou, and Y. Fang, "Location-based compromise-tolerant security mechanisms for wireless sensor networks," IEEE J. Select. Areas Commun., Special Issue on Security in Wireless Ad Hoc Networks, vol. 24, no. 2, pp. 247--260, Feb. 2006.
• 20: L. Ma, X. Cheng, F. Liu, F. An, and M. Rivera, "iPAK: An in-situ pairwise key bootstrapping scheme for wireless sensor networks," IEEE Trans. Parallel Distrib. Syst., vol. 18, no. 8, pp. 1174--1184, Aug. 2007.
• 21: R. Zhang, Y. Zhang, and K. Ren, "DP2AC: Distributed privacy-preserving access control in sensor networks," in IEEE INFOCOM'09, Rio de Janeiro, Brazil, Apr. 2009.
• 22: Q. Wang, K. Ren, W. Lou, and Y. Zhang, "Dependable and secure sensor data storage with dynamic integrity assurance," in IEEE INFOCOM'09, Rio de Janeiro, Brazil, Apr. 2009.
• 23: Phillip Rogaway , Mihir Bellare , John Black, OCB: A block-cipher mode of operation for efficient authenticated encryption, ACM Transactions on Information and System Security (TISSEC), v.6 n.3, p.365-403, August 2003 [doi>10.1145/937527.937529]
• 24: Donggang Liu , Peng Ning, Multilevel μTESLA: Broadcast authentication for distributed sensor networks, ACM Transactions on Embedded Computing Systems (TECS), v.3 n.4, p.800-836, November 2004 [doi>10.1145/1027794.1027800]
• 25: L.E. Miller, "Distribution of link distances in a wireless network," Journal of Research of the National Institute of Standards and Technology, vol. 106, pp. 401--412, 2001.
• 26: 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]
• 27: Haodong Wang , Bo Sheng , Chiu C. Tan , Qun Li, Comparing Symmetric-key and Public-key Based Security Schemes in Sensor Networks: A Case Study of User Access Control, Proceedings of the 2008 The 28th International Conference on Distributed Computing Systems, p.11-18, June 17-20, 2008 [doi>10.1109/ICDCS.2008.77]

INDEX TERMS

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

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

General Terms:
Design, Performance, Security

Keywords:
multidimensional range query, security, sensor networks