Database Reference
In-Depth Information
challenge is to uncover the global interaction patterns that leads to the
problem, as opposed to chasing a local root cause. The chapter de-
scribes the above different techniques and concludes with a brief review
of other troubleshooting work, not inspired by data mining literature.
Keywords:
Sensor networks, debugging, data mining, interactive complexity.
1. Introduction
The growing size and complexity of sensor networks makes trou-
bleshooting them an increasingly dicult undertaking. There are funda-
mentally two ways to ensure system correctness: either ensure absence
of faults by design, or develop techniques to detect and troubleshoot
them at run-time.
In the broader embedded systems domain (of which sensor networks
are a more recent subcategory), the predominant approach for ensuring
correctness has been to prove absence of bugs by design. Distributed
embedded systems and protocols can typically be described by state au-
tomata, where vertices represent logical states and edges represent state
transitions. Such transitions may be triggered, for example, by events
in the environment, occurrence of particular input values, or different
communication events. Sensor network tools such as FSMGen [54] were
developed to automatically construct an approximate finite state ma-
chine model of distributed sensing programs.
The approach allows one to reason about states that may be “bad”
(i.e., represent different types of failures or undesirable behavior). These
states may be reached through a particular confluence of events that
trigger the “right” pattern of state transitions, leading to the bad state
(i.e., a bug manifestation). A significant amount of embedded system
literature focused on analyzing
reachability
of bad states in the software
system's state machine. Given a model of the system, if a particular bad
state is reachable from the current state, then the system is vulnerable
in that there exists a sequence (or, more generally, a pattern) of events
that may cause the bad behavior to manifest. A typical model-checking
tool [5] performs reachability analysis to determine if certain bad states
can occur, and either proves them to be unreachable or returns an ex-
ample of the bug-causing pattern. Instances of recent system design
techniques in embedded computing that provably avoid bad states can
be found in domains as diverse as avoinics software [4], autonomous
ground vehicles [7, 8], collision avoidance systems [20, 19], and medical
pacemakers [6], to name a few.
