Reference Specification Issues in On-line Verification by Passive Testing

K.M. Brzezinski and N. Malinski (Poland)


Protocols, algorithms, distributed systems, testing.


The generic functionality of passive testing is detecting failures (fault manifestations) in a distributed system. We deal with one of the key functions of a passive tester - Trace Analysis (TA). The standard TA algorithms proceed by traversing a Reference Specification (RS), which is usually given in the form of a FSM automaton. The run-time performance of such algorithms is known to be poor for a large, nondeterministic RS (i.e. for real protocols). To improve this aspect of passive testing, instead of considering new TA algorithms, we try to increase the performance of existing algorithms, by changing the form of a RS to an Event Graph (EG). We define an EG and submit a detailed algorithm for its derivation. We then outline the EG-based algorithm for RS traversal. We report on the results of simulation experiments that clearly show considerableimprovementsinrun-timeperformanceof EG based passive testing over previous approaches, while the functionality of failure detection is strictly retained.

Important Links:

Go Back