Reachability Graph Based Hierarchical Test Generation for Network Protocols Modeled as Parallel Finite State Machines

Current researches on model-based testing mainly focus on the single component model, such as FSM (Finite State Machine) and EFSM (Extended FSM). To model and test parallelism and concurrency among different protocol components, traditional CFSM (Communicating FSMs) models communication as asynchronous message exchange, which is not suitable for the scenario that parallel protocol components read shared variables from each other. We have developed Parallel Parameterized Extended Finite State Machine (PaP-EFSM) to handle this situation. In this paper, we present a hierarchical test generation approach for PaP-EFSMs based on reachability graphs. The combination of bottom-up reachability graph generation and top-down test sequence generation ensures the executability of the test sequences and alleviates state explosion. We apply this method to the conformance testing of SAVI, a real protocol for anti-spoofing of IP source addresses. We build a set of PaP-EFSMs for SAVI and derive the executable test sequences, which expose many implementation faults when applied to real devices from 4 different vendors.