Efficient systematic testing of network protocols with temporal uncertain events

摘要

The correctness of network protocol implementations is difficult to test mainly because of the temporal uncertain nature of network events. In order to test the correctness of a network protocol implementation using network simulators, we need to systematically simulate the behavior of the network protocol under all possible cases of temporal uncertain events, which is very time consuming. The recently proposed Symbolic Execution based Interval Branching (SEIB) simulates a group of uncertain cases together in a single simulation branch, and thus is more efficient than brute force testing. In this paper, we argue that the efficiency of SEIB could be further exponentially improved by eliminating unnecessary comparisons of the event timestamps. Specifically, we summarize and present three general types of unnecessary comparisons when SEIB is applied to a general network simulator, and then correspondingly propose three novel techniques to eliminate them. Our extensive simulations show that our techniques can improve the efficiency of SEIB by several orders of magnitude, such as from days to minutes.