Wireless protocol validation under uncertainty

• Published in: Formal methods in system design 2018-08, Vol.53 (1), p.33-53
• Main Authors: Shi, Jinghao, Lahiri, Shuvendu K., Chandra, Ranveer, Challen, Geoffrey
• Format: Article
• Language: English
• Subjects: CAE) and Design; Circuits and Systems; Computer-Aided Engineering (CAD; Electrical Engineering; Engineering; Instruments; Searching; Software Engineering/Programming and Operating Systems; Uncertainty
• ISSN: 0925-9856; 1572-8102
• DOI: 10.1007/s10703-017-0309-4

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.