Database Reference
In-Depth Information
2.3 Unsupervised Classifiers
In contrast to the above, an entirely unsupervised approach is adopted
in Sentomist [101], a tool that focuses on profiling event handlers. Sen-
tomist runs on top of Avrora [86], a sensor network emulator with a
complete emulation of common sensor network hardware platforms such
as Mica2 motes
1
(based on the ATMega128L processor and the CC1000
radio). An extension to Avrora is used to count the number of different
types of instructions executed in event handlers. The vectors of such
counts for each type of handler are then input to an anomaly detection
routine that implements a one-class SVM algorithm [90]. The algorithm
determines which counts are statistically “normal”, and flags handlers
with abnormal counts. Those handlers are then subjected to manual
inspection. The idea behind this method lies in the assumption that the
code of buggy handler instances must be different from that of correctly
executing ones. Hence, looking for anomalous code execution patterns
can likely lead to locations of bugs. The protocol was used to identify
bugs in sensor networks such as abnormal packet losses during multi-
hop data forwarding, and unhandled race conditions between different
protocols.
A particularly interesting case study in applying Sentomist [101] was
one where its authors emulated a combination of a heartbeat message
exchange protocol and the Collection Tree Protocol (CTP) [33]. They
focused on profiling the timer event handler. The anomaly detection
routine ranked the different invocations of the handler by the degree to
which their instruction count vectors deviated from normal behavior.
The top ranked handler instances were then inspected for bugs. Indeed,
code analysis revealed that the 4th ranked handler instance exhibits a
race condition where CTP fails to transmit due to contention with the
heartbeat message exchange protocol. The contention is apparently not
handled correctly, causing the “busy” bit of the underlying communi-
cation device not to be cleared. Hence, all subsequent communication
fails. The bug was uncovered by manual inspection of the particular
execution sequence of the handlers flagged by Sentomist.
The above has been a quick tour through represenative examples of
different classification-based debugging techniques whose purpose was
to
localize
bugs. In other words, they aimed to single-out a node or
component that is responsible for anomalous behavior. Next, we describe
techniques that adopt an entirely different methodology in searching for
1
A list of common sensor network platforms and their documentation is maintained at
