Database Reference
In-Depth Information
distinguish conditions associated with bug manifestations. The input to
the algorithm is the set of messages collected when network behavior is
correct and the set collected when behavior is anomalous. Messages are
labeled accordingly. Their headers are inspected. Content of different
header fields (such as message type) constitutes the different variables, or
dimensions, for classification. The counts of how many times messages of
different types were received also constituted classification dimentions.
As an example of its applicability, the aforementioned algorithm was
used to troubleshoot EnviroTrack [1], a distributed target tracking pro-
tocol for sensor networks. EnviroTrack was designed to detect intruders
who cross a sensor network field and track their movements. It occa-
sionally generated spurious target IDs, causing the number of detected
targets to be larger than the actual number of targets in the field. During
debugging, the system was tested by running targets through the sensor
network and recording all messages communicated between nodes. The
number of targets reported by the sensor network was also recorded. If
this number was correct, the collected message logs were labeled “good”.
Otherwise, they were labeled “bad”. The SNTS tool analyzed these logs,
revealing that a surprising 80% of all failures to maintain the correct tar-
get count were correctly predicted by the classifier using a single rule;
namely, the absence of messages of type
member-to-leader
from the log.
The designer of the target tracking protocol explained that sensors,
who see the target, form a group and elect a leader among themselves.
Members of this group continue communicating with the leader through
member-to-leader
messages. As the target moves, membership of the
group changes (as the nodes that see the target change). Leader hand-
off eventually occurs to make sure the leader is always close to the target.
Absence of member-to-leader messages therefore means that the target is
seen by only one sensor at a time. Hence, that sensor is the leader. There
are no further group members, and therefore no member-to-leader mes-
sages. This, it turns out, was precisely the problem with EnviroTrack.
Leader hand-off in EnviroTrack failed when the leader was the only node
who could see the target, since there were no other nodes to hand off the
target to. A consequence of a failed hand-off was that new sensors that
eventually detect the target would assign it a different new ID, thinking
it is a new target. The above illustrates how the failure condition un-
covered by the tool led to a diagnosis of the problem. Notice that the
tool itself does not have the knowledge to relate the observed problem to
lines in the code that explain how it happens. However, by identifying
other conditions that are correlated with the occurrence of the specific
failure mode, it helps the designer recognize what triggers the problem.
