Adaptive correctness monitoring for wireless sensor networks using hierarchical distributed run-time invariant checking

ABSTRACT

This article presents a hierarchical approach for detecting faults in wireless sensor networks (WSNs) after they have been deployed. The developers of WSNs can specify “invariants” that must be satisfied by the WSNs. We present a framework, Hierarchical SEnsor Network Debugging (H-SEND), for lightweight checking of invariants. H-SEND is able to detect a large class of faults in data-gathering WSNs, and leverages the existing message flow in the network by buffering and piggybacking messages. H-SEND checks as closely to the source of a fault as possible, pinpointing the fault quickly and efficiently in terms of additional network traffic. Therefore, H-SEND is suited to bandwidth or communication energy constrained networks. A specification expression is provided for specifying invariants so that a protocol developer can write behavioral level invariants. We hypothesize that data from sensor nodes does not change dramatically, but rather changes gradually over time. We extend our framework for the invariants that includes values determined at run-time in order to detect data trends. The value range can be based on information local to a single node or the surrounding nodes' values. Using our system, developers can write invariants to detect data trends without prior knowledge of correct values. Automatic value detection can be used to detect anomalies that cannot be detected in existing WSNs. To demonstrate the benefits of run-time range detection and fault checking, we construct a prototype WSN using CO₂ and temperature sensors coupled to Mica2 motes. We show that our method can detect sudden changes of the environments with little overhead in communication, computation, and storage.

REFERENCES

• 1: Yi-an Huang , Wenke Lee, A cooperative intrusion detection system for ad hoc networks, Proceedings of the 1st ACM workshop on Security of ad hoc and sensor networks, October 31, 2003, Fairfax, Virginia [doi>10.1145/986858.986877]
• 2: Sonja Buchegger , Jean-Yves Le Boudec, Performance analysis of the CONFIDANT protocol, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513828]
• 3: Michel Diaz , Guy Juanole , Jean-Pierre Courtiat, Observer-A Concept for Formal On-Line Validation of Distributed Systems, IEEE Transactions on Software Engineering, v.20 n.12, p.900-913, December 1994 [doi>10.1109/32.368136]
• 4: Shlomi Dolev , Amos Israeli , Shlomo Moran, Uniform Dynamic Self-Stabilizing Leader Election, IEEE Transactions on Parallel and Distributed Systems, v.8 n.4, p.424-440, April 1997 [doi>10.1109/71.588622]
• 5: Emmerich, S. 1996. Demand-controlled ventilation in a multi-zone office building. Fuel and Energy Abstracts 37, 4, 294--294.
• 6: Erdmann, C. A., Stiener, K. C., and Apte, M. G. 2002. Indoor carbon dioxide concentrations and sick building syndrome symptoms in the base study revisited: Analysis of the 100 building dataset. In Indoor Air. 443--448.
• 7: Michael D. Ernst , Jake Cockrell , William G. Griswold , David Notkin, Dynamically Discovering Likely Program Invariants to Support Program Evolution, IEEE Transactions on Software Engineering, v.27 n.2, p.99-123, February 2001 [doi>10.1109/32.908957]
• 8: Simon F. Goldsmith , Robert O'Callahan , Alex Aiken, Relational queries over program traces, Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
• 9: Haghighat, F. and Donnini, G. 1992. IAQ and energy-management by demand controlled ventilation. Environ. Techno. 13, 4, 351--359.
• 10: Dick Hamlet, Invariants and state in testing and formal methods, Proceedings of the 6th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, September 05-06, 2005, Lisbon, Portugal
• 11: Sudheendra Hangal , Monica S. Lam, Tracking down software bugs using automatic anomaly detection, Proceedings of the 24th International Conference on Software Engineering, May 19-25, 2002, Orlando, Florida [doi>10.1145/581339.581377]
• 12: Heinzelman, W. B., Chandrakasan, A. P., and Balakrishnan, H. 2002. An application-specific protocol architecture for wireless microsensor networks. IEEE Trans. Wireless Comm. 1, 4 (Oct.), 660--670.
• 13: Wendi Rabiner Heinzelman , Anantha Chandrakasan , Hari Balakrishnan, Energy-Efficient Communication Protocol for Wireless Microsensor Networks, Proceedings of the 33rd Hawaii International Conference on System Sciences-Volume 8, p.8020, January 04-07, 2000
• 14: Douglas Herbert , Yung-Hsiang Lu , Saurabh Bagchi , Zhiyuan Li, Detection and Repair of Software Errors in Hierarchical Sensor Networks, Proceedings of the IEEE International Conference on Sensor Networks, Ubiquitous, and Trustworthy Computing -Vol 1 (SUTC'06), p.403-410, June 05-07, 2006 [doi>10.1109/SUTC.2006.55]
• 15: Herbert, D., Modelo-Howard, G., Perez-Toro, C., and Bagchi, S. 2007. Fault tolerant ARIMA-based aggregation of data in sensor networks. IEEE International Conference on Dependable Systems and Networks.
• 16: Herbert, D., Sundaram, V., Albin, L., Lu, Y.-H., Bagchi, S., and Li, Z. 2007. Pervasive carbon dioxide and temperature monitoring utilizing large numbers of low-cost wireless sensors. American Industrial Hygiene Conference and Expo. 163.
• 17: Jason L. Hill , David E. Culler, Mica: A Wireless Platform for Deeply Embedded Networks, IEEE Micro, v.22 n.6, p.12-24, November 2002 [doi>10.1109/MM.2002.1134340]
• 18: Jonathan W. Hui , David Culler, The dynamic behavior of a data dissemination protocol for network programming at scale, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031506]
• 19: Issa Khalil , Saurabh Bagchi , Cristina Nina-Rotaru, DICAS: Detection, Diagnosis and Isolation of Control Attacks in Sensor Networks, Proceedings of the First International Conference on Security and Privacy for Emerging Areas in Communications Networks, p.89-100, September 05-09, 2005 [doi>10.1109/SECURECOMM.2005.17]
• 20: Issa Khalil, LITEWORP: A Lightweight Countermeasure for the Wormhole Attack in Multihop Wireless Networks, Proceedings of the 2005 International Conference on Dependable Systems and Networks, p.612-621, June 28-July 01, 2005 [doi>10.1109/DSN.2005.58]
• 21: Khalil, I., Bagchi, S., and Shroff, N. B. 2006. MOBIWORP: Mitigation of the wormhole attack in mobile multihop wireless networks. In IEEE International Conference on Security and Privacy in Communication Networks.
• 22: Gunjan Khanna , Padma Varadharajan , Saurabh Bagchi, Self Checking Network Protocols: A Monitor Based Approach, Proceedings of the 23rd IEEE International Symposium on Reliable Distributed Systems, p.18-30, October 18-20, 2004
• 23: Naveen Kumar , Bruce R. Childers , Mary Lou Soffa, Low overhead program monitoring and profiling, Proceedings of the 6th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, September 05-06, 2005, Lisbon, Portugal
• 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: Philip Levis , Nelson Lee , Matt Welsh , David Culler, TOSSIM: accurate and scalable simulation of entire TinyOS applications, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958506]
• 26: Liao, C.-M., Chang, C.-F., and Liang, H.-M. 2005. A probabilistic transmission dynamic model to access indoor airborne infection risks. Risk Analysis. 25, 5, 1097--1107.
• 27: Stephanie Lindsey , Cauligi Raghavendra , Krishna M. Sivalingam, Data Gathering Algorithms in Sensor Networks Using Energy Metrics, IEEE Transactions on Parallel and Distributed Systems, v.13 n.9, p.924-935, September 2002 [doi>10.1109/TPDS.2002.1036066]
• 28: Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 29: Stephen R. Mahaney , Fred B. Schneider, Inexact agreement: accuracy, precision, and graceful degradation, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.237-249, August 1985, Minaki, Ontario, Canada [doi>10.1145/323596.323618]
• 30: Sergio Marti , T. J. Giuli , Kevin Lai , Mary Baker, Mitigating routing misbehavior in mobile ad hoc networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.255-265, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345955]
• 31: Keith Marzullo, Tolerating failures of continuous-valued sensors, ACM Transactions on Computer Systems (TOCS), v.8 n.4, p.284-304, Nov. 1990 [doi>10.1145/128733.128735]
• 32: Medidi, S. R., Medidi, M., and Gavini, S. 2003. Detecting packet-dropping faults in mobile ad-hoc networks. In IEEE ASILOMAR Conference on Signals, Systems and Computers.
• 33: Milton, D. K., Glencross, P. M., and Walters, M. D. 2000. Risk of sick leave associated with outdoor air supply rate, humidification, and occupant complaints. Indoor Air 10, 4 (Dec.), 212--221.
• 34: Rex Min , Manish Bhardwaj , Seong-Hwan Cho , Eugene Shih , Amit Sinha , Alice Wang , Anantha Chandrakasan, Low-Power Wireless Sensor Networks, Proceedings of the The 14th International Conference on VLSI Design (VLSID '01), p.205, January 03-07, 2001
• 35: Muruganathan, S. D., Ma, D. C. F., Bhasin, R. I., and Fapojuwo, A. O. 2005. A centralized energy-efficient routing protocol for wireless sensor networks. IEEE Commun. Mag. 43, 3 (Mar.), 8--13.
• 36: Myatt, T. A., Johnston, S. L., Zuo, Z., Wand, M., Kebadze, T., Rudnick, S., and Milton, D. K. 2004. Detection of airborne rhinovirus and its relation to outdoor air supply in office environments. Amer. J. Respir. Critic. Care Med. 169, 1187--1190.
• 37: A Survey on Leader Election Protocols for Radio Networks, Proceedings of the 2002 International Symposium on Parallel Architectures, Algorithms and Networks, p.71, May 22-24, 2002
• 38: Asis Nasipuri , Robert Castañeda , Samir R. Das, Performance of multipath routing for on-demand protocols in mobile ad hoc networks, Mobile Networks and Applications, v.6 n.4, p.339-349, Aug. 2001 [doi>10.1023/A:1011426611520]
• 39: Jeff H. Perkins , Michael D. Ernst, Efficient incremental algorithms for dynamic detection of likely invariants, Proceedings of the 12th ACM SIGSOFT twelfth international symposium on Foundations of software engineering, October 31-November 06, 2004, Newport Beach, CA, USA
• 40: Asad Amir Pirzada , Chris McDonald, Establishing trust in pure ad-hoc networks, Proceedings of the 27th Australasian conference on Computer science, p.47-54, January 01, 2004, Dunedin, New Zealand
• 41: Nithya Ramanathan , Kevin Chang , Rahul Kapur , Lewis Girod , Eddie Kohler , Deborah Estrin, Sympathy for the sensor network debugger, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA [doi>10.1145/1098918.1098946]
• 42: Rudnick, S. N. and Milton, D. K. 2003. Risk of indoor airborne infection transmission estimated from carbon dioxide concentration. Indoor Air 13, 3 (Sept.), 237--245.
• 43: Seppanen, O. A., Fisk, W. J., and Mendell, M. J. 1999. Association of ventilation rates and CO2 concentrations with health and other responses in commercial and institutional buildings. Indoor Air. 226--252.
• 44: Gurdip Singh, Leader Election in the Presence of Link Failures, IEEE Transactions on Parallel and Distributed Systems, v.7 n.3, p.231-236, March 1996 [doi>10.1109/71.491576]
• 45: Bradley R. Smith , Shree Murthy , J. J. Garcia-Luna-Aceves, Securing Distance-Vector Routing Protocols, Proceedings of the 1997 Symposium on Network and Distributed System Security, p.85, February 10-11, 1997
• 46: Stanislava Soro , Wendi B. Heinzelman, Prolonging the Lifetime of Wireless Sensor Networks via Prolonging the Lifetime of Wireless Sensor Networks via, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Workshop 12, p.236.2, April 04-08, 2005 [doi>10.1109/IPDPS.2005.365]
• 47: Gerard Tel, Topics in distributed algorithms, Cambridge University Press, New York, NY, 1991
• 48: Giovanni Vigna , Sumit Gwalani , Kavitha Srinivasan , Elizabeth M. Belding-Royer , Richard A. Kemmerer, An Intrusion Detection Tool for AODV-Based Ad hoc Wireless Networks, Proceedings of the 20th Annual Computer Security Applications Conference, p.16-27, December 06-10, 2004 [doi>10.1109/CSAC.2004.6]
• 49: Wang, J. Yi., Shue, Y.-S., Vijaykumar, T. N., and Bagchi, S. 2006. Pesticide: Using SMT processors to improve performance of pointer bug detection. In IEEE International Conference on Computer Design.
• 50: I-Ling Yen , Farokh B. Bastani , David J. Taylor, Design of Multi-Invariant Data Structures for Robust Shared Accesses in Multiprocessor Systems, IEEE Transactions on Software Engineering, v.27 n.3, p.193-207, March 2001 [doi>10.1109/32.910857]
• 51: M. Younis , M. Youssef , K. Arisha, Energy-Aware Routing in Cluster-Based Sensor Networks, Proceedings of the 10th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems (MASCOTS'02), p.129, October 11-16, 2002
• 52: Yu, I. T., Li, Y., Wong, T. W., Tam, W., Chan, A. T., Lee, J. H., Leung, D. Y., and Ho, T. 2004. Evidence of airborne transmission of the severe acute respiratory syndrome virus. New Engl. J. Med. 350, 17 (Apr.), 1731--1739.
• 53: Yuanyuan Zhou , Pin Zhou , Feng Qin , Wei Liu , Josep Torrellas, Efficient and flexible architectural support for dynamic monitoring, ACM Transactions on Architecture and Code Optimization (TACO), v.2 n.1, p.3-33, March 2005 [doi>10.1145/1061267.1061269]
• 54: Mohammad Zulkernine , Rudolph E. Seviora, A Compositional Approach to Monitoring Distributed Systems, Proceedings of the 2002 International Conference on Dependable Systems and Networks, p.763-772, June 23-26, 2002

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Distributed networks

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications; Packet-switching networks

General Terms:
Design, Reliability, Verification

Keywords:
Invariants, correctness monitoring, data integrity, fault tolerance and diagnostics, in-network processing and aggregation, network protocols, programming models and languages, run-time, tools