Attack-resilient hierarchical data aggregation in sensor networks

ABSTRACT

In a large sensor network, in-network data aggregation, i.e., combining partial results at intermediate nodes during message routing, significantly reduces the amount of communication and hence the energy consumed. Recently several researchers have proposed robust aggregation frameworks, which combine multi-path routing schemes with duplicate-insensitive algorithms, to accurately compute aggregates (e.g., Sum, Count, Average) in spite of message losses resulting from node and transmission failures. However, these aggregation frameworks have been designed without security in mind. Given the lack of hardware support for tamper-resistance and the unattended nature of sensor nodes, sensor networks are highly vulnerable to node compromises. We show that even if a few compromised nodes contribute false sub-aggregate values, this results in large errors in the aggregate computed at the root of the hierarchy. We present modifications to the aggregation algorithms that guard against such attacks, i.e., we present algorithms for resilient hierarchical data aggregation despite the presence of compromised nodes in the aggregation hierarchy. We evaluate the performance and costs of our approach via both analysis and simulation. Our results show that our approach is scalable and efficient.

REFERENCES

• 1: Mihir Bellare , Roch Guérin , Phillip Rogaway, XOR MACs: New Methods for Message Authentication Using Finite Pseudorandom Functions, Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology, p.15-28, August 27-31, 1995
• 2: L. Buttyan, P. Schaffer, and I. Vajda. Resilient aggregation with attack detection in sensor networks. In Proc. of 2nd IEEE Workshop on Sensor Networks and Systems for Pervasive Computing, 2006.
• 3: Jeffrey Considine , Feifei Li , George Kollios , John Byers, Approximate Aggregation Techniques for Sensor Databases, Proceedings of the 20th International Conference on Data Engineering, p.449, March 30-April 02, 2004
• 4: Wenliang Du , Jing Deng , Yunghsiang S. Han , Pramod K. Varshney, A pairwise key pre-distribution scheme for wireless 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.948118]
• 5: Philippe Flajolet , G. Nigel Martin, Probabilistic counting algorithms for data base applications, Journal of Computer and System Sciences, v.31 n.2, p.182-209, Sept. 1985 [doi>10.1016/0022-0000(85)90041-8]
• 6: Saurabh Ganeriwal , Mani B. Srivastava, Reputation-based framework for high integrity 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.1029115]
• 7: Deepak Ganesan , Ramesh Govindan , Scott Shenker , Deborah Estrin, Highly-resilient, energy-efficient multipath routing in wireless sensor networks, ACM SIGMOBILE Mobile Computing and Communications Review, v.5 n.4, October 2001 [doi>10.1145/509506.509514]
• 8: L. Hu and D. Evans. Secure aggregation for wireless networks. In Proc. of Workshop on Security and Assurance in Ad hoc Networks., 2003.
• 9: Márk Jelasity , Alberto Montresor , Ozalp Babaoglu, Gossip-based aggregation in large dynamic networks, ACM Transactions on Computer Systems (TOCS), v.23 n.3, p.219-252, August 2005 [doi>10.1145/1082469.1082470]
• 10: F. Koushanfar, M. Potkonjak, and A. Sangiovanni-Vincentelli. Fault tolerance techniques in wireless ad-hoc sensor networks. In Sensors 2002. Proceedings of IEEE, pages 1491--1496.
• 11: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TAG: a Tiny AGgregation service for Ad-Hoc sensor networks, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060303]
• 12: 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]
• 13: Mica Motes. http://www.xbow.com.
• 14: 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]
• 15: Adrian Perrig , Robert Szewczyk , Victor Wen , David Culler , J. D. Tygar, SPINS: security protocols for sensor netowrks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.189-199, July 2001, Rome, Italy [doi>10.1145/381677.381696]
• 16: 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]
• 17: 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]
• 18: 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]
• 19: 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]
• 20: Fan Ye, Haiyun Luo, Songwu Lu, and Lixia Zhang. Statistical en-route filtering of injected false data in sensor networks. In Proc. of IEEE Infocom, 2004.
• 21: W. Zhang and G. Cao. Group rekeying for filtering false data in sensor networks: A predistribution and local collaboration-based approach. Proc. of IEEE Infocom, 2005.
• 22: Jerry Zhao , Ramesh Govindan, Understanding packet delivery performance in dense wireless 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.958493]
• 23: J. Zhao, R. Govindan, and D. Estrin. Computing aggregates for monitoring sensor networks. In Proc. of the 2nd IEEE International Workshop on Sensor Network Protocols and Applications, 2003.
• 24: 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]
• 25: S. Zhu, S. Setia, S. Jajodia, and P. Ning. An interleaved hop-by-hop authentication scheme for filtering injected false data in sensor networks. In Proc. of IEEE Symposium on Security and Privacy, 2004.

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

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Cryptographic controls

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)

General Terms:
Algorithms, Design, Security

Keywords:
attack-resilient, data aggregation, hierarchical aggregation, sensor network security, synopsis diffusion