Finding symbolic bug patterns in sensor networks

Mohammad Maifi Hasan Khan, Tarek Abdelzaher, Jiawei Han, Hossein Ahmadi

Research output: Chapter in Book/Report/Conference proceedingConference contribution


This paper presents a failure diagnosis algorithm for summarizing and generalizing patterns that lead to instances of anomalous behavior in sensor networks. Often multiple seemingly different event patterns lead to the same type of failure manifestation. A hidden relationship exists, in those patterns, among event attributes that is somehow responsible for the failure. For example, in some system, a message might always get corrupted if the sender is more than two hops away from the receiver (which is a distance relationship) irrespective of the senderId and receiverId. To uncover such failure-causing relationships, we present a new symbolic pattern extraction technique that identifies and symbolically expresses relationships correlated with anomalous behavior. Symbolic pattern extraction is a new concept in sensor network debugging that is unique in its ability to generalize over patterns that involve different combinations of nodes or message exchanges by extracting their common relationship. As a proof of concept, we provide synthetic traffic scenarios where we show that applying symbolic pattern extraction can uncover more complex bug patterns that are crucial to the understanding of real causes of problems. We also use symbolic pattern extraction to diagnose a real bug and show that it generates much fewer and more accurate patterns compared to previous approaches.

Original languageEnglish (US)
Title of host publicationDistributed Computing in Sensor Systems - 5th IEEE International Conference, DCOSS 2009, Proceedings
Number of pages14
StatePublished - 2009
Event5th IEEE International Conference on Distributed Computing in Sensor Systems, DCOSS 2009 - Marina del Rey, CA, United States
Duration: Jun 8 2009Jun 10 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5516 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other5th IEEE International Conference on Distributed Computing in Sensor Systems, DCOSS 2009
Country/TerritoryUnited States
CityMarina del Rey, CA


  • Interactive bugs
  • Symbolic pattern
  • Wireless sensor network

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Finding symbolic bug patterns in sensor networks'. Together they form a unique fingerprint.

Cite this