Timed transition tour for race detection in distributed systems

Overview & Synopsis

The paper is devoted to detecting output races in distributed systems. We perform such detection through testing their implementations. As an underlying model for our test generation strategy we consider a Timed Finite State Machine or a TFSM (for short), where each input/output transition is augmented with a timed guard and an output delay. A potential output race can thus be simulated as an output delay mutant; this formalism is introduced in the paper. In order to build a test suite, we adapt a well-known test generation strategy, a transition tour method. The novelty of the proposed method relies on choosing appropriate timestamps for inputs, yielding a timed transition tour. We discuss its fault coverage for output race detection. As an application case study, we consider a Software Defined Networking (SDN) framework where the system under test is represented by the composition of a controller and a switch. Experimental results show that the timed transition tour can detect races in the behavior of the widely used ONOS controller.