University of Illinois Urbana-Champaign

Troubleshooting interactive complexity bugs in wireless sensor networks using data mining techniques

Khan, Mohammad Maifi Hasan; Le, Khac Hieu; Ahmadi, Hossein; Abdelzaher, Tarek F.; Han, Jiawei

Content Files
main.pdf

Permalink

https://hdl.handle.net/2142/17096

Description

Title
Troubleshooting interactive complexity bugs in wireless sensor networks using data mining techniques
Author(s)
  • Khan, Mohammad Maifi Hasan
  • Le, Khac Hieu
  • Ahmadi, Hossein
  • Abdelzaher, Tarek F.
  • Han, Jiawei
Issue Date
2010
Keyword(s)
  • Protocol debugging
  • Distributed automated debugging
  • Wireless sensor networks
  • Discriminative sequence mining
Date of Ingest
2010-09-20T17:43:30Z
Abstract
This article 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 {\em sequences\/} of events that may be responsible for faulty behavior, as opposed to localized bugs such as a bad pointer in a module. We identified several challenges in applying discriminative sequence mining for root cause analysis when the system fails to perform as expected and presented our solutions to those challenges. We also presented two alternatives schemes, namely, two stage mining and the progressive discriminative sequence mining to address the scalability challenge. 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 provided three case studies where we applied our tool successfully to troubleshoot the cause of the problem. We uncovered a kernel-level race condition bug in the LiteOS operating system and a protocol design bug in the directed diffusion protocol. We also presented a case study of debugging a 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. Finally, we provided a detailed analysis of tool overhead in terms of memory requirements and impact on the running application.
Type of Resource
text
Genre of Resource
Technical Report
Language
en
Permalink
http://hdl.handle.net/2142/17096

Owning Collections

Research and Tech Reports - Computer Science PRIMARY