A testing metric for designs modelled as hierarchical finite-state machines.

Abstract

Modern software design tools use finite-state machines (FSMs) arranged in hierarchical fashion. Many techniques have been developed for testing software modelled as an FSM, but none explicitly addressing designs modelled as a hierarchical FSM (HFSM). Additionally, the problem of explosion in the number of test paths precludes the testing of all possible paths through the HFSM [Holzmann 91]. This thesis presents a practical and scalable method for testing a design modelled as an HFSM. The method is based on graph traversal and uses the hierarchy of the underlying directed graph. A recursive algorithm computes breadth, the number of paths needed just to cover all transitions at least once. This idea is extended to cover all states, all inputs, and all outputs. This method is complementary to existing formal methods for conformance testing and protocol testing. Breadth is a lower bound on the number of test paths to cover the HFSM.