Motorola Corporation

Carmie A Hull

Xiao Sun

Unique Input/Output Sequence (UIO) Sets are constructed to test conformance of a Machine (,) against a Finite State Machine (FSM) model (,). Unique Input/Output Sequence (UIO) Sets (,) uniquely identify FSM model states and may be Forward Unique I/O Sequences (FUIO), Backward Unique I/O Sequences (BUIO), Forward Unique I/O Sequence Sets (FUIOset), and/or Backward Unique I/O Sequence Sets (BUIOset). FSM model (,) state transitions are selected as Edges-Under-Test (EUT). A Set of EUT UIO Sets is identified comprising UIO Sets that uniquely identify either the source or destination FSM model (,) state of an EUT. One member is selected from the Set of EUT UIO Sets for a particular EUT, and each member of this UIO Set is concatenated with the EUT to form Test Subsequences (TS). These Test Subsequences are used to verify that the corresponding FSM transitions are successfully traversed by a Machine Under Test (MUT).

Method and apparatus for testing finite state machine (FSM) conformance utilizing unique input/output sequence (UIO) sets

A set of Unique Input/Output Sequence (UIO) Sets is identified for Finite State Machine (FSM) model (33) states. Each member of the Sets of UIO Sets is a UIO Set (63) which are sets of Input/Output (I/O) Sequences that each uniquely identifies FSM (33) states. FSM (33) state transitions are Edges-Under-Test (EUT). A Test Subsequence is constructed for each member of each UIO Set (63) selected for each EUT that includes the UIO Set member and the corresponding EUT. A Test Subsequence (TS) Graph (65) is constructed from the Test Subsequences by connecting Test Subsequence starting and ending states. A Verification Test Sequence for testing a Machine Under Test (14) for conformance with a FSM model (33) is constructed by touring the TS Graph (65).

Method and apparatus for constructing test subsequence graphs utilizing

Verification Test Sequences (43) (VTS) are constructed for use in testing conformance of a Machine-Under-Test (14) (MUT) with a Finite State Machine (33) (FSM) model. The number of incoming and outgoing Test Subsequence (TS) graph (39) micro-edges are determined for each TS graph (39) vertex or Finite State Machine (33) state. An Augmented Graph (95) is created (40) by constructing Test Subsequence (TS) micro-edge bridging sequences between TS graph vertices with relatively more incoming micro-edges and vertices with relatively more outgoing micro-edges. The newly symmetric Augmented Graph (95) is Euler Toured (42), generating Verification Test Sequences (43), used to test a Machine-Under-Test (14) for conformance with the FSM model (33).

Method and apparatus for constructing verification test sequences by

A Distinctness Measurement (DM) is determined (16) for Finite State Machine (FSM) state transitions. The DM is used to identify Unique Input/Output Sequence (UIO) Sets (63) that uniquely identify FSM (33) states. UIO Set members are combined with FSM transitions to form Test Subsequences (TS). Test Subsequences are connected (64) into Hierarchical TS Graphs (65), which are merged (38). The merged TS Graph (39) is augmented (94) and Euler Toured (28) to generate Verification Test Sequences (VTS). A VTS (43) tests conformance of a Machine-Under-Test (14) against a FSM (33) model.

Hierarchical Test Subsequence (TS) subgraphs and Finite State Machine (FSM) subgraphs are merged. Hierarchical FSM subgraphs are merged (82) by connecting FSM model (33) child subgraph transitions or graph edges with states or vertices in the FSM parent subgraph. Matching is done based on Input/Output sequences. This merging (82) is repeated until all FSM child subgraphs are merged into FSM childless subgraphs. FSM childless subgraphs are Merged FSM graphs (83). Hierarchical Test Subsequence (TS) subgraphs (65) are merged (38) by finding peer subgraphs for TS child subgraphs. TS micro-edges from module entry and to module exit are connected to peer level FSM model states or vertices identified by matching Input/Output sequences. This merging (38) is repeated until all TS child subgraphs are merged into TS childless subgraphs. TS childless subgraphs are Merged TS graphs (39).

Method and apparatus for merging hierarchical test subsequence and

A measurement of the distinctness of Finite State Machine (FSM) (33) model state transitions can expedite identification of Unique Input/Output Sequences (UIO) (63). The Input/Output (I/O) sequences associated with FSM model (33) state transitions are compared. Each different I/O sequence is replaced by a different label so that transitions with the same I/O sequence have the same label and transitions with different I/O sequences have different labels. A transformation of the count of the number of times that each label is found in the FSM model, or a subset thereof, is determined, and assigned to each corresponding transition as a Distinctness Measurement (58). This Distinctness Measurement can be used to expedite a depth-first search for Unique Input/Output Sequences (63).

Growing community of inventors

Austin, TX, United States of America

Carmie A Hull