abstract.tex

\begin{abstract}
  Runtime validation of wireless protocol implementations cannot always employ
  direct instrumentation of the device under test (DUT). The DUT may not
  implement the required instrumentation, or the instrumentation may alter the
  DUT's behavior when enabled. Wireless sniffers can monitor the DUT's
  behavior without instrumentation, but they introduce new validation challenges.
  Losses caused by wireless propagation prevent sniffers
  from perfectly reconstructing the actual DUT packet trace. As a result,
  accurate validation requires distinguishing between
  specification deviations that represent implementation errors and those
  caused by sniffer uncertainty.

  We present a new approach enabling sniffer-based validation of wireless
  protocol implementations. Beginning with the original protocol monitor state
  machine, we automatically and completely encode sniffer uncertainty by
  selectively adding non-deterministic transitions. We characterize the
  NP-completeness of the resulting decision problem and provide an exhaustive
  algorithm for searching over all mutated traces. We also present
  practical protocol-oblivious heuristics for searching over the most likely
  mutated traces.  We have implemented our framework and show that it can
  accurately identify implementation errors in the face of uncertainty.
\end{abstract}