Secure hierarchical in-network aggregation in sensor networks

ABSTRACT

In-network aggregation is an essential primitive for performing queries on sensor network data. However, most aggregation algorithms assume that all intermediate nodes are trusted. In contrast, the standard threat model in sensor network security assumes that an attacker may control a fraction of the nodes, which may misbehave in an arbitrary (Byzantine) manner.We present the first algorithm for provably secure hierarchical in-network data aggregation. Our algorithm is guaranteed to detect any manipulation of the aggregate by the adversary beyond what is achievable through direct injection of data values at compromised nodes. In other words, the adversary can never gain any advantage from misrepresenting intermediate aggregation computations. Our algorithm incurs only O(Δ log² n) node congestion, supports arbitrary tree-based aggregator topologies and retains its resistance against aggregation manipulation in the presence of arbitrary numbers of malicious nodes. The main algorithm is based on performing the sum aggregation securely by first forcing the adversary to commit to its choice of intermediate aggregation results, and then having the sensor nodes independently verify that their contributions to the aggregate are correctly incorporated. We show how to reduce secure median, count, and average to this primitive.

REFERENCES

• 1: H. Cam, S. Ozdemir, P. Nair, D. Muthuavinashiappan, and H. O. Sanli. Energy-efficient secure pattern based data aggregation for wireless sensor networks. Computer Communications, 29: 446--455, 2006.
• 2: Claude Castelluccia , Einar Mykletun , Gene Tsudik, E.cient Aggregation of encrypted data in Wireless Sensor Networks, Proceedings of the The Second Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services, p.109-117, July 17-21, 2005 [doi>10.1109/MOBIQUITOUS.2005.25]
• 3: Jen-Yeu Chen , Gopal Pandurangan , Dongyan Xu, Robust computation of aggregates in wireless sensor networks: distributed randomized algorithms and analysis, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 4: W. Du, J. Deng, Y. Han, and P. K. Varshney. A witness-based approach for data fusion assurance in wireless sensor networks. In Proceedings of the IEEE Global Telecommunications Conference, 2003.
• 5: J. Girao, M. Schneider, and D. Westhoff. CDA: Concealed data aggregation in wireless sensor networks. In Proceedings of the ACM Workshop on Wireless Security, 2004.
• 6: Michael B. Greenwald , Sanjeev Khanna, Power-conserving computation of order-statistics over sensor networks, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055597]
• 7: Indranil Gupta , Robbert van Renesse , Kenneth P. Birman, Scalable Fault-Tolerant Aggregation in Large Process Groups, Proceedings of the 2001 International Conference on Dependable Systems and Networks (formerly: FTCS), p.433-442, July 01-04, 2001
• 8: L. Hu and D. Evans. Secure aggregation for wireless networks. In Workshop on Security and Assurance in Ad hoc Networks, 2003.
• 9: Chalermek Intanagonwiwat , Deborah Estrin , Ramesh Govindan , John Heidemann, Impact of Network Density on Data Aggregation in Wireless Sensor Networks, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.457, July 02-05, 2002
• 10: P. Jadia and A. Mathuria. Efficient secure aggregation in sensor networks. In Proceedings of the 11th International Conference on High Performance Computing, 2004.
• 11: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TAG: a Tiny AGgregation service for ad-hoc sensor networks, ACM SIGOPS Operating Systems Review, v.36 n.SI, Winter 2002 [doi>10.1145/844128.844142]
• 12: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, The design of an acquisitional query processor for sensor networks, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872817]
• 13: A. Mahimkar and T. Rappaport. SecureDAV: A secure data aggregation and verification protocol for sensor networks. In Proceedings of the IEEE Global Telecommunications Conference, 2004.
• 14: Amit Manjhi , Suman Nath , Phillip B. Gibbons, Tributaries and deltas: efficient and robust aggregation in sensor network streams, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066191]
• 15: Suman Nath , Phillip B. Gibbons , Srinivasan Seshan , Zachary R. Anderson, Synopsis diffusion for robust aggregation in sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031525]
• 16: 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]
• 17: Bartosz Przydatek , Dawn Song , Adrian Perrig, SIA: secure information aggregation 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.958521]
• 18: David Wagner, Resilient aggregation in sensor networks, 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.1029116]
• 19: Yi Yang , Xinran Wang , Sencun Zhu , Guohong Cao, SDAP:: a secure hop-by-Hop data aggregation protocol for sensor networks, Proceedings of the seventh ACM international symposium on Mobile ad hoc networking and computing, May 22-25, 2006, Florence, Italy [doi>10.1145/1132905.1132944]
• 20: Yong Yao , Johannes Gehrke, The cougar approach to in-network query processing in sensor networks, ACM SIGMOD Record, v.31 n.3, September 2002 [doi>10.1145/601858.601861]

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:
Algorithms, Security

Keywords:
data aggregation, secure aggregation, sensor networks