Method and apparatus for generating conformance test data sequences

Claim 1

A method for generating a conformance test data, sequence for use in verifying that a device conforms to a specific protocol entity, the method comprising the steps of: generating a simplified extended finite state machine based on a formal description of the protocol entity; deriving an expanded directed graph of the simplified extended finite state machine, wherein each state is represented by a state vertex connected to a dummy vertex by a directed edge, and wherein the state and dummy vertices representing each state are connected to each other by directed edges in a manner corresponding to the operation of the simplified extended finite state machine; assigning traversal numbers to the directed edges of the expanded directed graph based on a test data set; evaluating the expanded directed graph and, if not symmetric, balancing the traversal numbers of the expanded directed graph to produce a symmetric expanded directed graph; obtaining a minimal length tour of the symmetric expanded directed graph; removing the dummy transition vertices from the minimal length tour to produce a minimal length test sequence; generating a unique input-output sequence of a last state of the minimal length test sequence; and generating the conformance test data sequence by concatenating the unique input-output sequence to the minimal length test sequence to verify the ending state of the device.

Claim 2

A method for generating a conformance test data, sequence for use in verifying that a device conforms to a specific protocol entity, the method comprising the steps of: generating a simplified extended finite state machine based on a formal description of the protocol entity; deriving an expanded directed graph of the simplified extended finite state machine, wherein each state is represented by a state vertex connected to a dummy vertex by a directed edge, and wherein the state and dummy vertices representing each state are connected to each other by directed edges in a manner corresponding to the operation of the simplified extended finite state machine; assigning traversal numbers to the directed edges of the expanded directed graph based on a test data set; evaluating the expanded directed graph and, if not symmetric, balancing the traversal numbers of the expanded directed graph to produce a symmetric expanded directed graph; obtaining a minimal length tour of the symmetric expanded directed graph; removing the dummy transition vertices from the minimal length tour to produce a minimal length test sequence; generating a unique input-output sequence of a last state of the minimal length test sequence; and generating the conformance test data sequence by concatenating the unique input-output sequence to the minimal length test sequence to verify the ending state of the device.

Claim 7

A method for generating a conformance test data sequence for use in verifying that a device conforms to a specific protocol entity, the method comprising the steps of: generating a simplified extended finite state machine based on the a formal description of the protocol; deriving an expanded directed graph of the simplified extended finite state machine, wherein each state is represented by a state vertex connected to a dummy vertex by a directed edge, and wherein the state and dummy vertices representing each state are connected to each other by directed edges in a manner corresponding to the operation of the extended finite state machine; assigning traversal numbers to the directed edges of the expanded directed graph based on a test data set; generating a minimal length tour by performing a Rural Chinese Postman Tour of the expanded directed graph based on the traversal numbers; removing the dummy transition vertices from the minimal length tour to produce a minimal length test sequence; generating a unique input-output sequence of a last state of the minimal length test sequence; and generating the conformance test data sequence by concatenating the unique input-output sequence to the minimal length test sequence to verify the ending state of the device.

Claim 8

A method for generating a conformance test data sequence for use in verifying that a device conforms to a specific protocol entity, the method comprising the steps of: generating a simplified extended finite state machine based on the a formal description of the protocol; deriving an expanded directed graph of the simplified extended finite state machine, wherein each state is represented by a state vertex connected to a dummy vertex by a directed edge, and wherein the state and dummy vertices representing each state are connected to each other by directed edges in a manner corresponding to the operation of the extended finite state machine; assigning traversal numbers to the directed edges of the expanded directed graph based on a test data set; generating a minimal length tour by performing a Rural Chinese Postman Tour of the expanded directed graph based on the traversal numbers; removing the dummy transition vertices from the minimal length tour to produce a minimal length test sequence; generating a unique input-output sequence of a last state of the minimal length test sequence; and generating the conformance test data sequence by concatenating the unique input-output sequence to the minimal length test sequence to verify the ending state of the device.

Claim 9

A method for generating an expanded directed graph for a simplified extended finite state machine for use in generating a conformance test data sequence, the method comprising the steps of: representing each state of the simplified extended finite state machine by a state vertex connected to a dummy vertex with a directed edge; and connecting the vertices representing each state to each other by directed edges in a manner corresponding to the operation of the simplified extended finite state machine.

Claim 10

A method for generating an expanded directed graph for a simplified extended finite state machine for use in generating a conformance test data sequence, the method comprising the steps of: representing each state of the simplified extended finite state machine by a state vertex connected to a dummy vertex with a directed edge; and connecting the vertices representing each state to each other by directed edges in a manner corresponding to the operation of the simplified extended finite state machine.

Claim 11

A method for verifying that a device conforms to a specific protocol entity comprising the steps of: providing input parameter values to the device based on a conformance test data sequence; and monitoring the output parameter values produced by the device, to verify that they conform to expected output parameter values based on the conformance test data sequence, wherein the conformance test data sequence is produced by the steps of: generating a simplified extended finite state machine based on a formal description of the protocol entity; deriving an expanded directed graph of the simplified extended finite state machine, wherein each state is represented by a state vertex connected to a dummy vertex by a directed edge, and wherein the state and dummy vertices representing each state are connected to each other by directed edges in a manner corresponding to the operation of the simplified extended finite state machine; assigning traversal numbers to the directed edges of the expanded directed graph based on a test data set; evaluating the expanded directed graph and, if not symmetric, balancing the traversal numbers of the expanded directed graph to produce a symmetric expanded directed graph; obtaining a minimal length tour of the symmetric expanded directed graph; removing the dummy transition vertices from the minimal length tour to produce a minimal length test sequence; generating a unique input-output sequence of a last state of the minimal length test sequence; and generating the conformance test data sequence by concatenating the unique input-output sequence to the minimal length test sequence to verify the ending state of the device.

Claim 12

A method for verifying that a device conforms to a specific protocol entity comprising the steps of: providing input parameter values to the device based on a conformance test data sequence; and monitoring the output parameter values produced by the device, to verify that they conform to expected output parameter values based on the conformance test data sequence, wherein the conformance test data sequence is produced by the steps of: generating a simplified extended finite state machine based on a formal description of the protocol entity; deriving an expanded directed graph of the simplified extended finite state machine, wherein each state is represented by a state vertex connected to a dummy vertex by a directed edge, and wherein the state and dummy vertices representing each state are connected to each other by directed edges in a manner corresponding to the operation of the simplified extended finite state machine; assigning traversal numbers to the directed edges of the expanded directed graph based on a test data set; evaluating the expanded directed graph and, if not symmetric, balancing the traversal numbers of the expanded directed graph to produce a symmetric expanded directed graph; obtaining a minimal length tour of the symmetric expanded directed graph; removing the dummy transition vertices from the minimal length tour to produce a minimal length test sequence; generating a unique input-output sequence of a last state of the minimal length test sequence; and generating the conformance test data sequence by concatenating the unique input-output sequence to the minimal length test sequence to verify the ending state of the device.

Claim 13

An apparatus for verifying that a device conforms to a specific protocol which can be characterized by an extended finite state machine, the apparatus comprising: a processor; a memory connected to the processor; and a test communications line connected to the processor, the test communications line having a device interface for connection to a device under test to provide communications between the processor and the device, the processor generating a conformance test data sequence to verify that the device conforms to a specific protocol, wherein the processor generates the conformance test data sequence by generating a simplified extended finite state machine based on a formal description of the protocol, deriving an expanded directed graph of the simplified extended finite state machine, assigning traversal numbers to the directed edges of the expanded directed graph based on a test data set, evaluating the expanded directed graph and, if not symmetric, balancing the traversal numbers of the expanded directed graph to produce a symmetric expanded directed graph, computing a minimal length tour of the symmetric expanded directed graph, removing the dummy transition vertices from the minimal length tour to produce a minimal length test sequence, generating a unique input-output sequence of a last state of the minimal length test sequence, and concatenating the unique input-output sequence to the minimal length test sequence.

Claim 14

An apparatus for verifying that a device conforms to a specific protocol which can be characterized by an extended finite state machine, the apparatus comprising: a processor; a memory connected to the processor; and a test communications line connected to the processor, the test communications line having a device interface for connection to a device under test to provide communications between the processor and the device, the processor generating a conformance test data sequence to verify that the device conforms to a specific protocol, wherein the processor generates the conformance test data sequence by generating a simplified extended finite state machine based on a formal description of the protocol, deriving an expanded directed graph of the simplified extended finite state machine, assigning traversal numbers to the directed edges of the expanded directed graph based on a test data set, evaluating the expanded directed graph and, if not symmetric, balancing the traversal numbers of the expanded directed graph to produce a symmetric expanded directed graph, computing a minimal length tour of the symmetric expanded directed graph, removing the dummy transition vertices from the minimal length tour to produce a minimal length test sequence, generating a unique input-output sequence of a last state of the minimal length test sequence, and concatenating the unique input-output sequence to the minimal length test sequence.