Wireless protocol validation under uncertainty

Jinghao Shi, Shuvendu K. Lahiri, Ranveer Chandra, Geoffrey Challen

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)33-53
Number of pages21
JournalFormal Methods in System Design
Issue number1
StatePublished - Aug 1 2018
Externally publishedYes


  • Runtime verification
  • Sniffer
  • Uncertainty
  • Wireless protocol

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture


Dive into the research topics of 'Wireless protocol validation under uncertainty'. Together they form a unique fingerprint.

Cite this