A Framework for Identifying Compromised Nodes in Wireless Sensor Networks

ABSTRACT

Sensor networks are often subject to physical attacks. Once a node's cryptographic key is compromised, an attacker may completely impersonate it and introduce arbitrary false information into the network. Basic cryptographic mechanisms are often not effective in this situation. Most techniques to address this problem focus on detecting and tolerating false information introduced by compromised nodes. They cannot pinpoint exactly where the false information is introduced and who is responsible for it.

In this article, we propose an application-independent framework for accurately identifying compromised sensor nodes. The framework provides an appropriate abstraction of application-specific detection mechanisms and models the unique properties of sensor networks. Based on the framework, we develop alert reasoning algorithms to identify compromised nodes. The algorithm assumes that compromised nodes may collude at will. We show that our algorithm is optimal in the sense that it identifies the largest number of compromised nodes without introducing false positives. We evaluate the effectiveness of the designed algorithm through comprehensive experiments.

REFERENCES

• 1: Karl Aberer , Zoran Despotovic, Managing trust in a peer-2-peer information system, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502638]
• 2: Toru Araki , Yukio Shibata, (t, k)-Diagnosable System: A Generalization of the PMC Models, IEEE Transactions on Computers, v.52 n.7, p.971-975, July 2003
• 3: Prosenjit Bose , Pat Morin , Ivan Stojmenović , Jorge Urrutia, Routing with guaranteed delivery in ad hoc wireless networks, Wireless Networks, v.7 n.6, p.609-616, November 2001 [doi>10.1023/A:1012319418150]
• 4: Camtepe, S. and Yener, B. 2004. Combinatorial design of key distribution mechanisms for wireless sensor networks. In 9th European Symposium On Research in Computer Security (ESORICS'04).
• 5: 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
• 6: Crossbow Technology Inc. 2003. MTS/MDA Sensor and Data Acquisition Boards User Manual.
• 7: A. T. Dahbura , G. M. Masson, Greedy Diagnosis as the Basis of an Intermittent-Fault/ Transient-Upset Tolerant System Design, IEEE Transactions on Computers, v.32 n.10, p.953-957, October 1983 [doi>10.1109/TC.1983.1676140]
• 8: A. T. Dahbura , G. M. Masson, Greedy Diagnosis of Hybrid Fault Situations, IEEE Transactions on Computers, v.32 n.8, p.777-782, August 1983 [doi>10.1109/TC.1983.1676322]
• 9: A. T. Dahbura , G. M. Masson, An 0(n2.5) Fault Identification Algorithm for Diagnosable Systems, IEEE Transactions on Computers, v.33 n.6, p.486-492, June 1984 [doi>10.1109/TC.1984.1676472]
• 10: Anton T. Dahbura , Krishan K. Sabnani , Linda L. King, The Comparison Approach to Multiprocessor Fault Diagnosis, IEEE Transactions on Computers, v.36 n.3, p.373-378, March 1987 [doi>10.1109/TC.1987.1676912]
• 11: Jing Deng , Richard Han , Shivakant Mishra, Security support for in-network processing in Wireless Sensor Networks, Proceedings of the 1st ACM workshop on Security of ad hoc and sensor networks, October 31, 2003, Fairfax, Virginia [doi>10.1145/986858.986870]
• 12: Deng, J., Han, R., and Mishra, S. 2004. A robust and light-weight routing mechanism for wireless sensor networks. In Proceedings of the Workshop on Dependability Issues in Wireless Ad Hoc Networks and Sensor Networks (DIWANS).
• 13: Du, W., Deng, J., Han, Y. S., and Varshney, P. K. 2003a. A witness-based approach for data fusion assurance in wireless sensor networks. In Proceedings of the IEEE Global Communications Conference (GLOBECOM).
• 14: 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]
• 15: Wenliang Du , Lei Fang , Peng Ning, LAD: Localization Anomaly Detection forWireless Sensor Networks, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Papers, p.41.1, April 04-08, 2005 [doi>10.1109/IPDPS.2005.267]
• 16: 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]
• 17: Fuhrman, C. P. 1996. Comparison-based diagnosis in faulttolerant, multiprocessor systems. Ph.D. thesis, Department of Computer Science, Swiss Federal Institute of Technology in Lausanne (EPFL).
• 18: 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]
• 19: Golbeck, J. and Hendler, J. 2004. Accuracy of metrics for inferring trust and reputation in semantic Web-based social networks. In Proceedings of the International Conference on Knowledge Engineering and Knowledge Management (EKAW). Northamptonshire, U.K.
• 20: Ho, T., Leong, B., Koetter, R., Medard, M., Effros, M., and Karger, D. 2004. Byzantine modification detection in multicast networks using randomized network coding. In Proceedings of the IEEE International Symposium on Information Theory (ISIT).
• 21: Lingxuan Hu , David Evans, Secure Aggregation for Wireless Networks, Proceedings of the 2003 Symposium on Applications and the Internet Workshops (SAINT'03 Workshops), p.384, January 27-31, 2003
• 22: Sepandar D. Kamvar , Mario T. Schlosser , Hector Garcia-Molina, The Eigentrust algorithm for reputation management in P2P networks, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775242]
• 23: Wojciech E. Kozlowski , Henryk Krawczyk, A Comparison-Based Approach to Multicomputer System Diagnosis in Hybrid Fault Situations, IEEE Transactions on Computers, v.40 n.11, p.1283-1287, November 1991 [doi>10.1109/12.102834]
• 24: Leslie Lamport , Robert Shostak , Marshall Pease, The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.382-401, July 1982 [doi>10.1145/357172.357176]
• 25: Lawrence, R., Sergey, B., Rajeev, M., and Terry, W. 1998. The PageRank citation ranking: Bringing order to the Web. Tech. rep., Department of Computer Science, Stanford University.
• 26: Lee, S., Sherwood, R., and Bhattacharjee, B. 2003. Cooperative peer groups in NICE. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communication Societies (INFOCOM).
• 27: 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]
• 28: Liu, D., Ning, P., and Du, W. 2003. Efficient distribution of key chain commitments for broadcast authentication in distributed sensor networks. In Proceedings of the 10th Annual Network and Distributed System Security Symposium (NDSS'03).
• 29: Donggang Liu , Peng Ning , Wenliang Du, Detecting Malicious Beacon Nodes for Secure Location Discovery in Wireless Sensor Networks, Proceedings of the 25th IEEE International Conference on Distributed Computing Systems, p.609-619, June 06-10, 2005 [doi>10.1109/ICDCS.2005.21]
• 30: Donggang Liu , Peng Ning , Rongfang Li, Establishing pairwise keys in distributed sensor networks, ACM Transactions on Information and System Security (TISSEC), v.8 n.1, p.41-77, February 2005 [doi>10.1145/1053283.1053287]
• 31: Daniel Marx, Parameterized Complexity of Constraint Satisfaction Problems, Proceedings of the 19th IEEE Annual Conference on Computational Complexity, p.139-149, June 21-24, 2004 [doi>10.1109/CCC.2004.22]
• 32: Micali, S. and Vazirani, V. 1980. An √|V||e| algorithm for finding maximum matchings in general graphs. In Proceedings of the 21st Symp. Foundations of Computing.
• 33: L. Mui , M. Mohtashemi , A. Halberstadt, A Computational Model of Trust and Reputation for E-businesses, Proceedings of the 35th Annual Hawaii International Conference on System Sciences (HICSS'02)-Volume 7, p.188, January 07-10, 2002
• 34: Adrian Perrig , J. D. Tygar , Dawn Song , Ran Canetti, Efficient Authentication and Signing of Multicast Streams over Lossy Channels, Proceedings of the 2000 IEEE Symposium on Security and Privacy, p.56, May 14-17, 2000
• 35: Adrian Perrig , Robert Szewczyk , Victor Wen , David Culler , J. D. Tygar, SPINS: security protocols for sensor networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.189-199, July 2001, Rome, Italy [doi>10.1145/381677.381696]
• 36: Preparata, F. P., Metze, G., and Chien, R. T. 1967. On the connection assignment problem of diagosable systems. IEEE Trans. Electron. Comput. 16, 6, 848--854.
• 37: 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]
• 38: Richardson, M., Agrawal, R., and Domingos, P. 2003. Trust management for the Semantic Web. In Proceedings of the 2nd International Semantic Web Conference.
• 39: Gregory F. Sullivan, A O(t³+ |E| ) Fault Identification Algorithm for Diagnosable Systems, IEEE Transactions on Computers, v.37 n.4, p.388-397, April 1988 [doi>10.1109/12.2182]
• 40: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
• 41: Xiong, L. and Liu, L. 2002. Building trust in decentralized peer-to-peer electronic communities. In Proceedings of the 5th International Conference on Electronic Commerce Research (ICECR).
• 42: Ye, F., Luo, H., Lu, S., and Zhang, L. 2004. Statistical en-route filtering of injected false data in sensor networks. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communication Societies (INFOCOM).
• 43: Bin Yu , Munindar P. Singh, An evidential model of distributed reputation management, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 1, July 15-19, 2002, Bologna, Italy [doi>10.1145/544741.544809]
• 44: Zhang, Q., Yu, T., and Ning, P. 2006. A framework for identifying compromised nodes in sensor networks. In Proceedings of the 2nd IEEE Communications Society/CreateNet International Conference on Security and Privacy in Communication Networks (SecureComm'06).
• 45: Zhu, S., Setia, S., Jajodia, S., and Ning, P. 2004. An interleaved hop-by-hop authentication scheme for filtering of injected false data in sensor networks. In Proceedings of the IEEE Symposium on Security and Privacy, 260--272.

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

Keywords:
Sensor networks, intrusion detection