CN103888314A - Method verifying states of finite-state machine on basis of UIO sequence method - Google Patents

Abstract

The invention discloses a method for verifying the state of a finite state machine based on a UIO sequence method, which mainly solves the problems that the UIO sequence method cannot be used and the state verification process is complicated when there is no UIO sequence in some states in a communication protocol. The implementation steps are: 1) Simplify the finite state machine of the communication protocol; 2) Select the state without UIO sequence as the state to be verified; 3) Select the state with the same input and output behavior as the state to be verified as the verification state; 4) Select the input event sequence according to the input and output behavior of the state to be verified and the verification state; 5) Verify whether the state to be verified is the expected state according to whether the output event sequence of the system under test is consistent with the finite state machine. The invention expands the application range of the UIO sequence method, simplifies the generation process of the consistency test set and shortens the length of the generated test sequence, and can be applied to the design of the test set in the consistency test of the communication protocol.

Description

Method of verifying the state of finite state machine based on UIO sequence method

technical field

The invention belongs to the field of communication technology, and particularly relates to a method for verifying the state of a finite state machine, which can be used for consistency test sets of various communication protocols when there is no unique input and output UIO sequence in certain states of the finite state machine design and implementation.

Background technique

Protocol conformance testing is a kind of black box testing, the purpose of which is to check the degree of compliance between the system running the protocol and the protocol standard. In communication protocol conformance testing, a test set is a collection of multiple test sequences that meet the test criteria. A test sequence usually consists of three parts: a boot sequence, a test input and output operation, and a state verification sequence. Among them, the boot sequence is used to set the state of the system under test to the required state; the test input and output operation is used to verify whether the behavior of the system under test is consistent with the protocol requirements; the state verification sequence is used to check whether the system under test is converted to The state described by the protocol specification. As one of the components of the test sequence, the state verification sequence plays an important role in improving the error detection ability of the test sequence.

At present, most construction methods of state verification sequences are based on finite state machines. A finite state machine can be expressed as a quintuple (S, I, O, δ, γ), where S is a finite non-empty set of states, I is a finite non-empty set of input events, and O is a finite non-empty set of output events. Empty set, δ is the state transition function, γ is the output function. A finite state machine needs to have the following basic characteristics:

1. The number of states, the number of input events and the number of output events generated by the finite state machine are all limited and definite.

2. Each state of the finite state machine can accept all input events.

3. For each input event, if the finite state machine can generate an output event, then the output event will be generated within a given finite time.

4. Each state of the finite state machine is reachable, and its state transition graph is a connected graph.

Currently, for finite state machines, there are three main methods for constructing state verification sequences: distinguishing sequence method, characteristic sequence set method, and UIO sequence method. Compared with the discrimination sequence method and the feature sequence set method, the UIO sequence method has low complexity and the length of the generated test sequence is shorter. Therefore, in the modeling process of time series behavior fields such as digital systems and communications, especially when looking for optimized It has a wide range of applications on the test set.

The UIO sequence is a unique input and output sequence, that is, for a certain state in the finite state machine, other states cannot show the same input/output I/O sequence, so the UIO sequence can uniquely identify and verify this state. In a certain state Sa, for a certain input y, if and only if the output λa of the state Sa is different from the output of all other states, then y/λa is the UIO sequence of the state Sa, denoted as UIO(Sa) =y/λa, where y/λa represents the input/output sequence in state Sa. The steps to solve UIO(Sa) are as follows:

1) Assuming that the state set P is a set of states that can be reached from Sa in one step, check whether there is a unique path of I/O sequence in the one-step path from Sa to all states in the state set P: if there is, then the The I/O sequence is the only input and output UIO sequence of Sa; otherwise, execute step 2);

2) Suppose the state set Q is a set of states that can be reached from Sa after n steps, n≥2, check whether there is a unique path of I/O sequence in the n-step path from Sa to all states in the state set Q: if If yes, the I/O sequence is the only UIO sequence of Sa; otherwise, n=n+1, re-check whether there is a unique path of I/O sequence in the n-step path from Sa to all states in the state set Q ;

Both the I/O sequence and the UIO sequence are composed of an input event sequence and an output event sequence. The input event sequence represents an input event in the I/O sequence or a combination of multiple input events with a sequence relationship, and the output event sequence represents the I/O An output event in a sequence or a combination of output events with a sequence relationship.

The UIO sequence method is a method of constructing a state verification sequence based on finding the UIO sequence of each state in the finite state machine. After obtaining the state verification sequence, combined with the boot sequence and test input and output operations, the test sequence can be obtained, and the collection of all test sequences constitutes a complete test set. Therefore, it is generally believed that whether the UIO sequence of all states can be found is the premise of whether the UIO sequence method can be used.

In most cases, UIO sequences can be found in each state in the finite state machine, but in some cases, UIO sequences do not exist in some states of the finite state machine. For example, for a certain state Sa, for any input y, there is an output λa, and it is transferred to a certain state Sb, and for the state Sb, the same input y, if there is the same output λa, then there is no UIO sequence in the state Sa. As shown in Figure 2, the state is represented by a circle, the transition of the state is represented by a solid line with an arrow, the condition of the state transition is marked on the solid line, that is, the I/O behavior, and the input event and Output events. In state S2, input B, get output Y and transfer to state S3, because input B in state S3, also get output Y, then there is no UIO sequence in state S2. It is generally believed that at this time, the UIO sequence method cannot be used to verify the state of these states, and more complex verification methods such as the distinguishing sequence method and the feature sequence set method can only be used, which makes the consistency test set more complicated and increases the test sequence. length.

Contents of the invention

The present invention aims at the deficiencies of the above-mentioned prior art, and proposes a method for verifying the state of a finite state machine based on the UIO sequence method, in order to combine the I/O sequences of other states under the condition that there is no UIO sequence in some states, by eliminating The possibility that the finite state machine is in other states realizes the state verification of the state where there is no UIO sequence, thereby simplifying the generation process of the consistency test set and shortening the length of the generated test sequence.

To achieve the above object, the technical solution of the present invention comprises the following steps:

(1) For the finite state machine of the communication protocol to be tested for consistency, merge its equivalent states to make the finite state machine the simplest;

(2) Find the UIO sequence of each state in the finite state machine, find out the state without UIO sequence, and form the state set M to be verified;

(3) Randomly select a state from the set M of states to be verified as the state Si to be verified;

(4) Select any input/output I/O sequence of the state Si to be verified, find out all states containing the input/output I/O sequence except the state Si to be verified, and form a verification state set N;

(5) Set the state of the system under test to Si to be verified;

(6) Input the input event sequence of the I/O sequence selected in step (4) to the system under test, and check the output event sequence of the system under test:

6a) If the output event sequence is consistent with the output event sequence specified by the finite state machine in the state Si to be verified, then perform step (7);

6b) If the output event sequence does not match the output event sequence specified by the finite state machine in the state Si to be verified, the state to be verified is not the expected state, and this state verification process ends.

(7) Set the state of the system under test to Si to be verified;

(8) Select a state from the verification state set N as the verification state Sj;

(9) Select an I/O sequence whose state Si and state Sj to be verified are different, input the input event sequence of the I/O sequence to the system under test, and check the output event sequence of the system under test:

9a) If the output event sequence does not match the output event sequence specified by the finite state machine in the state Si to be verified, the state to be verified is not the expected state, and this state verification process ends;

9b) If the output event sequence is consistent with the output event sequence specified by the finite state machine in the state Si to be verified, delete the state Sj from the verification state set N, and judge whether the verification state set N is empty:

9b1) If the check state set N is not empty, execute step (7);

9b2) If the verification state set N is empty, then prove that the state to be verified is the expected state, and perform step (10);

(10) Delete the above-mentioned state Si to be verified from the set M of states to be verified;

(11) Repeat step (3) to step (10) until all the states in the state set M to be verified are verified.

On the basis of using the UIO sequence as the state verification sequence, the present invention combines the idea of the elimination method, and finally verifies whether the finite state machine is in the expected state by eliminating the possibility that the finite state machine is in a certain state, thereby extending the UIO sequence method. Scope of application, so that the finite state machine with no UIO sequence in some states avoids the use of more complex distinguishing sequence method and feature sequence set method, simplifies the generation process of the consistency test set and shortens the length of the generated test sequence.

Description of drawings

Fig. 1 is the realization flowchart of the present invention;

Fig. 2 is the state transition diagram of the finite state machine of embodiment one;

Fig. 3 is the state transition figure before the finite state machine merged state of embodiment two;

FIG. 4 is a state transition diagram of the finite state machine in the second embodiment after the state is merged.

Detailed ways

The content of the present invention will be further elaborated below in conjunction with the accompanying drawings.

Referring to Fig. 1, the present invention provides following two embodiments.

Embodiment one:

This embodiment takes a communication protocol that does not contain an equivalent state and has a state that has the same input/output sequence as a state that does not have a UIO sequence as an example, and illustrates that the state that does not have a UIO sequence in the system under test that runs the communication protocol The process of state verification.

The state transition diagram of this communication protocol is shown in Figure 2, wherein, the state is represented by a circle, and the state transition is represented by a solid line with an arrow. The letters A, B, and C denote three different input events, and the letters X, Y, and Z denote three different output events. The finite state machine includes three states: a first state S1, a second state S2 and a third state S3. The initial state of the finite state machine is the first state S1. When the finite state machine is in a certain state, if a certain input event is received, the finite state machine will generate a corresponding output event, and its state will also be transferred. Referring to Figure 2, the output events and state transitions generated by the finite state machine for the received input events are:

When the finite state machine is in the first state S1, if the input event it receives is A, then the output event generated by the finite state machine is X, and its state shifts to the second state S2. If the input event it receives is B or C, the output event generated by the finite state machine is no response, and its state does not transfer.

When the finite state machine is in the second state S2, if the input event it receives is B, then the output event generated by the finite state machine is Y, and its state shifts to the third state S3. If the input event it receives is A or C, the output event generated by the finite state machine is no response, and its state does not transfer.

When the finite state machine is in the third state S3, if the input event it receives is B, the output event generated by the finite state machine is Y, and the state it is in is transferred to the third state S3. If the input event it receives is C, then the output event generated by the finite state machine is Z, and its state shifts to the first state S1. If the input event it receives is A, the output event generated by the finite state machine is no response, and its state does not transition.

Referring to Figure 2, the steps for status verification of this example are as follows:

Step 1, Simplify the finite state machine of the communication protocol.

Since the finite state machine used in this example does not contain equivalent states, no merging is required.

Step 2, using the method of solving the UIO sequence, find the UIO sequence of each state in the finite state machine.

When the finite state machine is in the first state S1, if the input event it receives is A, the output event generated by the finite state machine is X. Since no other state in the finite state machine has input/output A/X, so The UIO sequence of the first state S1 is A/X.

The solution process of the UIO sequence of the second state S2 includes the following three situations:

When the input event is A, the second state S2 and the third state S3 have the same output event, and the state of the finite state machine does not transition.

When the input event is B, the second state S2 and the third state S3 have the same output event, and the state of the finite state machine is transferred to the state S3.

When the input event is C, the second state S2 has the same output event as the first state S1, and the state of the finite state machine does not transition.

So there is no UIO sequence in the second state S2;

When the finite state machine is in the third state S3, if the input event it receives is C, the output event generated by the finite state machine is Z. Since other states in the finite state machine do not have the sequence C/Z, the third The UIO sequence of state S3 is C/Z.

Step 3: According to whether there is a UIO sequence in each state in the finite state machine, find out the state that does not have a UIO sequence, and form a set M of states to be verified, so as to select a state to be verified.

From the UIO sequence of each state obtained in step 2, it can be seen that only the second state S2 does not have a UIO sequence, so the second state S2 alone constitutes the set M of states to be verified, and the second state S2 is selected as the state Si to be verified.

Step 4, find out the states contained in the verification state set N, so as to select the verification state Sj.

Select the input/output sequence B/Y of the second state S2. Since only the third state S3 contains the input/output sequence B/Y among other states, the verification state set N contains the third state S3, and the third state S3 is selected As the verification state Sj.

Step 5, input event A to the system under test, so that the state of the system under test is transferred to the state Si to be verified.

Step 6, input the input event B of the input/output sequence selected in step 4 to the system under test, and check the output event of the system under test:

If the output event is not Y, it proves that the state to be verified is not the expected second state S2, and the state verification process ends;

If the output event is Y, the possibility that the state to be verified is the first state S1 is ruled out, because if the system under test is in the first state S1, for the input event B, its output event should be no response. Go to step 7.

Step 7: Input events C and A to the system under test sequentially, so that the state of the system under test is transferred to the state Si to be verified.

Step 8, according to the input and output behaviors of the state Si to be verified and the state Sj to be verified, select an input event and check the output event.

8a) According to the selection of the second state S2 as the state to be verified Si in step 3 and the selection of the third state S3 as the verification state Sj in step 4, and when the finite state machine is in the second state S2 and the third state S3, Different output events are generated for input event C, so event C is selected as the input event to the system under test;

8b) Check the output events of the system under test:

Input event C to the system under test, the resulting output event may be Z or no response:

If the output event is Z, it proves that the state to be verified is not the expected second state S2, and the state verification process ends;

If the system under test does not respond to the input event C, the possibility that the state to be verified is the third state S3 is ruled out, and the third state S3 is deleted from the verification state set N, and the verification state set N is an empty set. So far, The possibility that the state to be verified is the first state S1 and the third state S3 is excluded, so the state to be verified is the expected second state S2, and the second state S2 is deleted from the set of states to be verified M. At this time, the state to be verified The set M is empty, and the state verification process ends.

Embodiment two:

This embodiment takes a communication protocol that contains an equivalent state and has two states that have the same input/output sequence as a state that does not have a UIO sequence as an example, to illustrate how to perform state processing on a state that does not have a UIO sequence in a system under test that is running a communication protocol. Verification process.

The state transition diagram of the communication protocol is shown in Figure 3, in which the state is represented by a circle, and the state transition is represented by a solid line with an arrow. The condition of the state transition is marked on the solid line, that is, the input/output behavior. B, C, and D represent four different input events, and letters W, X, Y, and Z represent four different output events. The finite state machine includes five states: a first state S1, a second state S2, a third state S3, a fourth state S4 and a fifth state S5. The initial state of the finite state machine is the first state S1. When the finite state machine is in a certain state, if a certain input event is received, the finite state machine will generate a corresponding output event, and its state will also be transferred. Referring to Figure 3, the output events and state transitions generated by the finite state machine for the received input events are:

When the finite state machine is in the first state S1, if the input event it receives is A, then the output event generated by the finite state machine is W, and its state shifts to the second state S2. If the input event it receives is B, C or D, the output event generated by the finite state machine is no response, and its state does not transfer.

When the finite state machine is in the second state S2, if the input event it receives is B, then the output event generated by the finite state machine is X, and its state shifts to the third state S3. If the input event it receives is A, C or D, the output event generated by the finite state machine is no response, and its state does not transfer.

When the finite state machine is in the third state S3, if the input event it receives is A, the output event generated by the finite state machine is Z, and its state shifts to the fifth state S5. If the input event it receives is B, the output event generated by the finite state machine is X, and its state shifts to the third state S3. If the input event it receives is C, the output event generated by the finite state machine is Y, and its state shifts to the fourth state S4. If the input event it receives is D, the output event generated by the finite state machine is no response, and its state does not transition.

When the finite state machine is in the fourth state S4, if the input event it receives is B, then the output event generated by the finite state machine is X, and its state shifts to the fourth state S4. If the input event it receives is D, then the output event generated by the finite state machine is Z, and its state shifts to the first state S1. If the input event it receives is A or C, the output event generated by the finite state machine is no response, and its state does not transfer.

When the finite state machine is in the fifth state S5, if the input event it receives is B, then the output event generated by the finite state machine is X, and its state shifts to the third state S3. If the input event it receives is A, C or D, the output event generated by the finite state machine is no response, and its state does not transfer.

Referring to Figure 3, the steps for status verification of this example are as follows:

Step one, simplify the finite state machine of the communication protocol.

Since for any input event, the second state S2 and the fifth state S5 have the same output event, and the state transition is also the same, so the second state S2 and the fifth state S5 are equivalent states, and the second state S2 and the fifth state S5 are combined. The fifth state S5, the combined state transition diagram is shown in Figure 4, where:

When the finite state machine is in the first state S1, if the input event it receives is A, then the output event generated by the finite state machine is W, and its state shifts to the second state S2. If the input event it receives is B, C or D, the output event generated by the finite state machine is no response, and its state does not transfer.

When the finite state machine is in the second state S2, if the input event it receives is B, then the output event generated by the finite state machine is X, and its state shifts to the third state S3. If the input event it receives is A, C or D, the output event generated by the finite state machine is no response, and its state does not transfer.

When the finite state machine is in the third state S3, if the input event it receives is A, then the output event generated by the finite state machine is Z, and its state shifts to the fifth state S2. If the input event it receives is B, the output event generated by the finite state machine is X, and its state shifts to the third state S3. If the input event it receives is C, the output event generated by the finite state machine is Y, and its state shifts to the fourth state S4. If the input event it receives is D, the output event generated by the finite state machine is no response, and its state does not transition.

When the finite state machine is in the fourth state S4, if the input event it receives is B, then the output event generated by the finite state machine is X, and its state shifts to the fourth state S4. If the input event it receives is D, then the output event generated by the finite state machine is Z, and its state shifts to the first state S1. If the input event it receives is A or C, the output event generated by the finite state machine is no response, and its state does not transfer.

Step 2, using the method of solving the UIO sequence, find the UIO sequence of each state in the finite state machine.

When the finite state machine is in the first state S1, if the input event it receives is A, the output event generated by the finite state machine is W. Since no other state in the finite state machine has the sequence A/W, the first The UIO sequence of a state S1 is A/W;

The solution process of the UIO sequence of the second state S2 includes the following four situations:

When the input event is A, the second state S2 and the fourth state S4 have the same output event, and the state of the finite state machine does not transition;

When the input event is B, the second state S2 and the third state S3 have the same output event, and the state of the finite state machine is transferred to the state S3;

When the input event is C, the second state S2 has the same output event as the first state S1, and the state of the finite state machine does not transition;

When the input event is D, the second state S2 has the same output event as the first state S1, and the state of the finite state machine does not transition, so there is no UIO sequence in the second state S2;

When the finite state machine is in the third state S3, if the input event it receives is C, the output event generated by the finite state machine is Y. Since other states in the finite state machine do not have the sequence C/Y, the first The UIO sequence for the three-state S3 is C/Y.

When the finite state machine is in the fourth state S4, if the input event it receives is D, the output event generated by the finite state machine is Z. Since other states in the finite state machine do not have the sequence D/Z, the first The UIO sequence of the four-state S4 is D/Z.

Step 3: According to whether there is a UIO sequence in each state in the finite state machine, find out the state that does not have a UIO sequence, and form a set M of states to be verified, so as to select a state to be verified.

From the UIO sequence of each state obtained in step 2, it can be seen that there is no UIO sequence in the second state S2, so the second state S2 alone constitutes the set of states to be verified M, and the second state S2 is selected as the state to be verified Si.

Step 4, find out the states included in the verification state set N.

Select the input/output sequence B/X of the second state S2, because in other states, the third state S3 and the fourth state S4 both contain the input/output sequence B/X, so the verification state set N contains the third state S3 and a fourth state S4.

Step five, input event A to the system under test, so that the state of the system under test is transferred to the state Si to be verified.

Step six, input the input event B of the input/output sequence selected in step four to the system under test, and check the output event of the system under test:

If the output event is not X, it proves that the state to be verified is not the expected second state S2, and the state verification process ends;

If the output event is X, the possibility that the state to be verified is the first state S1 is ruled out, because if the system under test is in the first state S1, for the input event B, its output event should be no response. Go to step seven.

Step seven, input events C, D and A to the system under test in sequence, so that the state of the system under test is transferred to the state Si to be verified.

Step 8: Select a verification state, select an input event according to the input and output behaviors of the state Si to be verified and the verification state Sj, and check the output event.

8.1) Select the third state S3 from the verification state set N as the verification state Sj;

8.2) According to the selection of the second state S2 as the state Si to be verified in step 3 and the selection of the third state S3 as the verification state Sj in step 8.1), and when the finite state machine is in the second state S2 and the third state S3 , different output events are generated for input event C, so event C is selected as the input event to the system under test;

8.3) Check the output events of the system under test.

Input event C to the system under test, the output event generated may be Y or no response:

If the output event is Y, it proves that the state to be verified is not the expected second state S2, and the state verification process ends;

If the system under test does not respond to the input event C, the possibility that the state to be verified is the third state S3 is ruled out, and the third state S3 is deleted from the verification state set N. At this time, the verification state set N only includes the fourth state State S4, so the fourth state S4 is the verification state Sj, go to step 9.

Step 9, transfer the state of the system under test to the state Si to be verified.

According to the fact that the state of the system under test is transferred to the state Si to be verified in step 7, and the event C is input to the system under test in step 8, the system under test does not respond and no state transfer occurs, it can be known that the system under test The state at is already the state Si to be verified, and there is no need to transfer the state of the system under test.

Step ten, according to the input and output behaviors of the state Si to be verified and the state Sj to be verified, select an input event, and check the output event.

10.1) According to the selection of the second state S2 as the state Si to be verified in step 3 and the selection of the fourth state S4 as the verification state Sj in step 8.3), and when the finite state machine is in the second state S2 or the fourth state S4 , the output event generated by the input event D is different, so the event D is selected as the input event to the system under test;

10.2) Check the output events of the system under test.

Input event D to the system under test, the resulting output event may be Z or no response:

If the output event is Z, it proves that the state to be verified is not the expected second state S2, and the state verification process ends;

If the system under test does not respond to the input event D, the possibility that the state to be verified is the fourth state S4 is ruled out, and the fourth state S4 is deleted from the verification state set N. At this time, the verification state set N is an empty set. So far, the possibility that the state to be verified is the first state S1, the third state S3 and the fourth state S4 has been ruled out, so the state to be verified is the expected second state S2, and the second state S2 is selected from the state set M to be verified Delete, at this time the state set M to be verified is empty, and the state verification process ends.

The above description is only a specific example of the present invention, and does not constitute any limitation to the present invention. Obviously, for professionals in the field, after understanding the content and principles of the present invention, it is possible without departing from the principles and structures of the present invention. Various modifications and changes in formalization and details are made, but these modifications and changes based on the idea of the present invention are still within the protection scope of the claims of the present invention.

Claims (7)

1. the method based on uio sequence method checking finite state machine status, comprises the steps:

(1) to carrying out the finite state machine of the communication protocol of uniformity test, merge its equivalent state, make finite state machine the simplest;

(2) obtain the uio sequence of each state in finite state machine, find out the state that does not have uio sequence, and form state set M to be verified;

(3), from described state set M to be verified, choose arbitrarily a state as state Si to be verified;

(4) select arbitrary I/O I/O sequence of state Si to be verified, find out all states that contain this I/O I/O sequence except state Si to be verified, and form verification state set N;

(5) residing system under test (SUT) state is set to state Si to be verified;

(6) to the incoming event sequence of the I/O sequence of selecting in system under test (SUT) input step (4), and check the outgoing event sequence of system under test (SUT):

If 6a) outgoing event sequence conforms to the outgoing event sequence under state Si to be verified of finite state machine regulation, execution step (7);

If 6b) outgoing event sequence does not conform to the outgoing event sequence under state Si to be verified of finite state machine regulation, state to be verified is not expecting state, finishes this state verification process.

(7) residing system under test (SUT) state is set to state Si to be verified;

(8) from verification state set N an optional state as verification state Sj;

(9) select the I/O sequence that state Si to be verified is not identical with state Sj, input the incoming event sequence of this I/O sequence to system under test (SUT), and check the outgoing event sequence of system under test (SUT):

If 9a) outgoing event sequence does not conform to the outgoing event sequence under state Si to be verified of finite state machine regulation, state to be verified is not expecting state, finishes this state verification process;

If 9b) outgoing event sequence conforms to the outgoing event sequence under state Si to be verified of finite state machine regulation, state Sj is deleted from verification state set N, and judges whether verification state set N is empty:

If 9b1) verification state set N is not empty, execution step (7);

If 9b2) verification state set N is empty, prove that state to be verified is expecting state, execution step (10);

(10) above-mentioned state Si to be verified is deleted from state set M to be verified;

(11) repeating step (3) is to step (10), until all states in state set M to be verified are all verified.

2. method according to claim 1, the equivalent state in wherein said step (1), refers to the two or more states in finite state machine, they have identical output for identical input, and can be transformed into identical state.

3. method according to claim 1, the uio sequence of obtaining each state in finite state machine that wherein step (2) is described, carries out as follows:

(2a) in finite state machine, all states, appoint and get a state Sa;

(2b) establish the set that state set P is the state that just can arrive through 1 step from Sa, checking from Sa to state set P, in 1 footpath, step of all states, whether there is the unique path of I/O behavior: if having, the uio sequence that this I/O behavior is exactly Sa, execution step (2d); Otherwise, execution step (2c);

(2c) establishing state set Q is the set that walks the state that just can arrive from Sa through n, n >=2, checking from Sa to state set Q, in the footpath, n step of all states, whether there is the unique path of I/O behavior: if having, the uio sequence that this I/O sequence is exactly Sa, execution step (2d); Otherwise whether n=n+1, have the unique path of I/O behavior in the footpath, n step of all states reexamining from Sa to state set Q;

(2d) in finite state machine, appoint the state of obtaining not yet uio sequence of getting, execution step (2b), until obtain the uio sequence of all states in state set N.

4. method according to claim 1, I/O sequence in wherein said step (4), refer to and there is an I/O operation of precedence relationship or the combination of multiple I/O operation, I/O sequence is made up of incoming event sequence and outgoing event sequence, incoming event sequence represents an incoming event in I/O sequence or has the combination of multiple incoming events of precedence relationship, and outgoing event sequence represents an outgoing event in I/O sequence or has the combination of multiple outgoing events of precedence relationship.

5. method according to claim 1, wherein any one I/O sequence of the selection state Si to be verified described in step (4), it is each the I/O sequence for state Si to be verified, find out all states that contain this I/O sequence in finite state machine, the status number that statistics contains this I/O sequence is selected a minimum I/O sequence of corresponding states number from all I/O sequences of state Si to be verified.

6. method according to claim 1, what wherein step (5) was described is set to state Si to be verified by residing system under test (SUT) state, and its implementation is:

If system under test (SUT) has the order that its status is set, directly use the residing state of this order system under test (SUT) to be set to state Si to be verified;

If system under test (SUT) does not arrange the order of its status, according to the regulation of finite state machine, to system under test (SUT) input sequence of events, make its status transfer to state Si to be verified.

7. method according to claim 1, wherein the described outgoing event sequence of step (6) conforms to the outgoing event sequence under state Si to be verified of finite state machine regulation, refer under state Si to be verified, the actual outgoing event sequence of system under test (SUT) is consistent with the outgoing event sequence of communication protocol regulation.

Images