Petri Net Based Search Directing Heuristics for Test Generation

The use of Petri nets to model the register transfers and change of control states in a sequential machine described in a Computer Hardware Design Language (CHDL) with the aim of guiding state space searches is proposed. Each fault to be detected defines a set of goal nodes for the state space search. These goal nodes together with a CHDL description of the circuit are used to generate a Petri Net (PN). Two guidance mechanisms are derived from the PN: heuristic cost value and input vector guidance. For each machine state encountered during the state space search, a heuristic cost value is computed using a state vector derived from the PN. The PN also contains information about input vectors that are associated with each control state. The most important of these are selected based on an established criteria. The heuristic cost value and input vectors are used to guide test generation searches. In three case studies, the method provides results superior to those previously reported both in guidance accuracy and computational requirements.