Dustminer: troubleshooting interactive complexity bugs in sensor networks

ABSTRACT

This paper presents a tool for uncovering bugs due to interactive complexity in networked sensing applications. Such bugs are not localized to one component that is faulty, but rather result from complex and unexpected interactions between multiple often individually non-faulty components. Moreover, the manifestations of these bugs are often not repeatable, making them particularly hard to find, as the particular sequence of events that invokes the bug may not be easy to reconstruct. Because of the distributed nature of failure scenarios, our tool looks for sequences of events that may be responsible for faulty behavior, as opposed to localized bugs such as a bad pointer in a module. An extensible framework is developed where a front-end collects runtime data logs of the system being debugged and an offline back-end uses frequent discriminative pattern mining to uncover likely causes of failure. We provide a case study of debugging a recent multichannel MAC protocol that was found to exhibit corner cases of poor performance (worse than single channel MAC). The tool helped uncover event sequences that lead to a highly degraded mode of operation. Fixing the problem significantly improved the performance of the protocol.We also provide a detailed analysis of tool overhead in terms of memory requirements and impact on the running application.

REFERENCES

• 1: http://www.cs.waikato.ac.nz/ml/weka/.
• 2: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 3: Marcos K. Aguilera , Jeffrey C. Mogul , Janet L. Wiener , Patrick Reynolds , Athicha Muthitacharoen, Performance debugging for distributed systems of black boxes, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 4: Paolo Ballarini , Alice Miller, Model Checking Medium Access Control for Sensor Networks, Proceedings of the Second International Symposium on Leveraging Applications of Formal Methods, Verification and Validation (isola 2006), p.255-262, November 15-19, 2006 [doi>10.1109/ISoLA.2006.16]
• 5: Peter Bodic , Greg Friedman , Lukas Biewald , Helen Levine , George Candea , Kayur Patel , Gilman Tolle , Jon Hui , Armando Fox , Michael I. Jordan , David Patterson, Combining Visualization and Statistical Analysis to Improve Operator Confidence and Efficiency for Failure Detection and Localization, Proceedings of the Second International Conference on Automatic Computing, p.89-100, June 13-16, 2005 [doi>10.1109/ICAC.2005.18]
• 6: Qing Cao , Tarek Abdelzaher , John Stankovic , Tian He, The LiteOS Operating System: Towards Unix-Like Abstractions for Wireless Sensor Networks, Proceedings of the 7th international conference on Information processing in sensor networks, p.233-244, April 22-24, 2008 [doi>10.1109/IPSN.2008.54]
• 7: Elaine Cheong , Judy Liebman , Jie Liu , Feng Zhao, TinyGALS: a programming model for event-driven embedded systems, Proceedings of the 2003 ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida [doi>10.1145/952532.952668]
• 8: Emre Ertin , Anish Arora , Rajiv Ramnath , Vinayak Naik , Sandip Bapat , Vinod Kulathumani , Mukundan Sridharan , Hongwei Zhang , Hui Cao , Mikhail Nesterenko, Kansei: a testbed for sensing at scale, Proceedings of the 5th international conference on Information processing in sensor networks, April 19-21, 2006, Nashville, Tennessee, USA [doi>10.1145/1127777.1127838]
• 9: Giuseppe Di Fatta , Stefan Leue , Evghenia Stegantova, Discriminative pattern mining in software fault detection, Proceedings of the 3rd international workshop on Software quality assurance, November 06-06, 2006, Portland, Oregon [doi>10.1145/1188895.1188910]
• 10: Eibe Frank , Ian H. Witten, Generating Accurate Rule Sets Without Global Optimization, Proceedings of the Fifteenth International Conference on Machine Learning, p.144-151, July 24-27, 1998
• 11: David Gay , Philip Levis , Robert von Behren , Matt Welsh , Eric Brewer , David Culler, The nesC language: A holistic approach to networked embedded systems, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 12: Lewis Girod , Jeremy Elson , Alberto Cerpa , Thanos Stathopoulos , Nithya Ramanathan , Deborah Estrin, EmStar: a software environment for developing and deploying wireless sensor networks, Proceedings of the annual conference on USENIX Annual Technical Conference, p.24-24, June 27-July 02, 2004, Boston, MA
• 13: Youssef Hanna , Hridesh Rajan , Wensheng Zhang, Slede: a domain-specific verification framework for sensor network security protocol implementations, Proceedings of the first ACM conference on Wireless network security, March 31-April 02, 2008, Alexandria, VA, USA [doi>10.1145/1352533.1352551]
• 14: Mohammad Maifi Khan , Tarek Abdelzaher , Kamal Kant Gupta, Towards Diagnostic Simulation in Sensor Networks, Proceedings of the 4th IEEE international conference on Distributed Computing in Sensor Systems, June 11-14, 2008, Santorini Island, Greece [doi>10.1007/978-3-540-69170-9_17]
• 15: M. M. H. Khan, L. Luo, C. Huang, and T. Abdelzaher. Snts: Sensor network troubleshooting suite. In Proceedings of International Conference on Distributed Computing in Sensor Systems (DCOSS), 2007. Santa Fe, New Mexico, USA.
• 16: Hieu Khac Le , Dan Henriksson , Tarek Abdelzaher, A Practical Multi-channel Media Access Control Protocol for Wireless Sensor Networks, Proceedings of the 7th international conference on Information processing in sensor networks, p.70-81, April 22-24, 2008 [doi>10.1109/IPSN.2008.43]
• 17: Philip Levis , David Culler, Maté: a tiny virtual machine for sensor networks, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 18: 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]
• 19: Chao Liu , Long Fei , Xifeng Yan , Jiawei Han , Samuel P. Midkiff, Statistical Debugging: A Hypothesis Testing-Based Approach, IEEE Transactions on Software Engineering, v.32 n.10, p.831-848, October 2006 [doi>10.1109/TSE.2006.105]
• 20: Chao Liu , Jiawei Han, Failure proximity: a fault localization-based approach, Proceedings of the 14th ACM SIGSOFT international symposium on Foundations of software engineering, November 05-11, 2006, Portland, Oregon, USA [doi>10.1145/1181775.1181782]
• 21: Chao Liu , Zeng Lian , Jiawei Han, How Bayesians Debug, Proceedings of the Sixth International Conference on Data Mining, p.382-393, December 18-22, 2006 [doi>10.1109/ICDM.2006.83]
• 22: Chao Liu , Xifeng Yan , Long Fei , Jiawei Han , Samuel P. Midkiff, SOBER: statistical model-based bug localization, Proceedings of the 10th European software engineering conference held jointly with 13th ACM SIGSOFT international symposium on Foundations of software engineering, September 05-09, 2005, Lisbon, Portugal
• 23: C. Liu, X. Yan, and J. Han. Mining control ow abnormality for logic error isolation. In Proceedings of 2006 SIAM International Conference on Data Mining (SDM'06), Bethesda, MD, April 2006.
• 24: C. Liu, X. Zhang, J. Han, Y. Zhang, and B. K. Bhargava. Failure indexing: A dynamic slicing based approach. In Proceedings of the 2007 IEEE International Conference on Software Maintenance (ICSM'07), Paris, France, October 2007.
• 25: Liqian Luo , Tarek F. Abdelzaher , Tian He , John A. Stankovic, EnviroSuite: An environmentally immersive programming framework for sensor networks, ACM Transactions on Embedded Computing Systems (TECS), v.5 n.3, p.543-576, August 2006 [doi>10.1145/1165780.1165782]
• 26: L. Luo, T. He, G. Zhou, L. Gu, T. Abdelzaher, and J. Stankovic. Achieving Repeatability of Asynchronous Events in Wireless Sensor Networks with EnviroLog. In Proceedings of the 25th IEEE International Conference on Computer Communications (INFOCOM'06), pages 1--14, 2006.
• 27: 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]
• 28: P. Olveczky and S. Thorvaldsen. Formal modeling and analysis of wireless sensor network algorithms in real-time maude. In Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS), Rhodes Island, Greece, April 2006.
• 29: J. Polley, D. Blazakis, J. McGee, D. Rusk, and J. S. Baras. Atemu: A fine-grained sensor network simulator. In Proceedings of the First International Conference on Sensor and Ad Hoc Communications and Networks (SECON'04), pages 145--152, Santa Clara, CA, October 2004.
• 30: 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]
• 31: R. Szewczyk, J. Polastre, A. Mainwaring, and D. Culler. Lessons from a sensor network expedition. In Proceedings of the First European Workshop on Sensor Networks (EWSN), 2004.
• 32: G. Tolle and D. Culler. Design of an application-cooperative management system for wireless sensor networks. In Proceedings of the Second European Workshop on Wireless Sensor Networks (EWSN'05), pages 121--132, Istanbul, Turkey, February 2005.
• 33: P. Völgyesi , M. Maróti , S. Dóra , E. Osses , Á. Lédeczi, Software composition and verification for sensor networks, Science of Computer Programming, v.56 n.1-2, p.191-210, April 2005 [doi>10.1016/j.scico.2004.11.012]
• 34: Ye Wen , Rich Wolski , Selim Gurun, S²DB: a novel simulation-based debugger for sensor network applications, Proceedings of the 6th ACM & IEEE International conference on Embedded software, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176887.1176903]
• 35: Ye Wen , Rich Wolski , Gregory Moore, Disens: scalable distributed sensor network simulation, Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming, March 14-17, 2007, San Jose, California, USA [doi>10.1145/1229428.1229434]
• 36: Geoffrey Werner-Allen , Patrick Swieskowski , Matt Welsh, MoteLab: a wireless sensor network testbed, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 37: Kamin Whitehouse , Gilman Tolle , Jay Taneja , Cory Sharp , Sukun Kim , Jaein Jeong , Jonathan Hui , Prabal Dutta , David Culler, Marionette: using RPC for interactive development and debugging of wireless embedded networks, Proceedings of the 5th international conference on Information processing in sensor networks, April 19-21, 2006, Nashville, Tennessee, USA [doi>10.1145/1127777.1127840]
• 38: Jing Yang , Mary Lou Soffa , Leo Selavo , Kamin Whitehouse, Clairvoyant: a comprehensive source-level debugger for wireless sensor networks, Proceedings of the 5th international conference on Embedded networked sensor systems, November 06-09, 2007, Sydney, Australia [doi>10.1145/1322263.1322282]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Distributed debugging

General Terms:
Design, Experimentation, Reliability

Keywords:
distributed automated debugging, protocol debugging, wireless sensor networks