Efficient Protocol Testing Under Temporal Uncertain Event Using Discrete-event Network Simulations
针对网络协议测试中时间不确定事件导致的仿真效率低问题，提出三种消除不必要时间戳比较的技术，将符号执行区间分支方法的效率提升数个数量级。
Testing network protocol implementations is difficult mainly because of the temporal uncertain nature of network events. To evaluate the worst-case performance or detect the bugs of a network protocol implementation using network simulators, we need to systematically simulate the behavior of the network protocol under all possible cases of the temporal uncertain events, which is 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 article, we argue that the efficiency of SEIB could be further significantly 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.