Wireless protocol validation under uncertainty

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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)
Title of host publicationRuntime Verification - 16th International Conference, RV 2016, Proceedings
EditorsYliès Falcone, César Sánchez
Number of pages17
ISBN (Print)9783319469812
StatePublished - 2016
Externally publishedYes
Event16th International Conference on Runtime Verification, RV 2016 - Madrid, Spain
Duration: Sep 23 2016Sep 30 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10012 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other16th International Conference on Runtime Verification, RV 2016

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


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

Cite this