# Test Sequence Reduction of Wireless Protocol Conformance Testing to Internet of Things

Authors: Weiwei Lin; Hongwei Zeng; Honghao Gao; Huaikou Miao; Xiaolin Wang
Journal: Security and Communication Networks
 (2018)

---

## Abstract

Wireless communication protocols are indispensable in Internet of Things (IoT), which refer to rules and conventions that must be followed by both entities to complete wireless communication or service. Wireless protocol conformance testing concerns an effective way to judge whether a wireless protocol is carried out as expected. Starting from existing test sequence generation methods in conformance testing, an improved method based on overlapping by invertibility and multiple unique input/output (UIO) sequences is proposed in this paper. The method is accomplished in two steps: first, maximum-length invertibility-dependent overlapping sequences (IDOSs) are constructed, then a minimum-length rural postman tour covering the just constructed set of maximum-length IDOSs is generated and a test sequence is extracted from the tour. The soundness and effectiveness of the method are analyzed. Theory and experiment show that desirable test sequences can be yielded by the proposed method to reveal violations of wireless communication protocols in IoT.


---

## Body

## 1. Introduction

Wireless communication is essential and critical to Internet of Things (IoT) [1, 2]. The reliability of wireless communication transmission largely depends on whether the wireless communication protocol is implemented as specified. Conformance testing [3, 4] is widely used to check whether an implementation conforms to its specification in areas such as traditional communication protocols and reactive systems; i.e., there must be the same behavior in the implementation for any I/O behavior observed in the specification. In FSM-based conformance testing, a protocol is called a specification and is expressed as a Finite State Machine (FSM), while an implementation under test is considered to be a “black box”, the I/O behavior of which can only be observed. A test sequence is an I/O sequence such that whether an implementation conforms to the specification may be concluded by delivering the input sequence of the test sequence to the implementation and comparing the resulting output sequence with the output sequence in the test sequence.Test techniques based on state identification [5–10] are well-known in FSM-based conformance testing. Test techniques based on state identification are supposed to identify every state and verify every transition of the specification in the implementation. A state is said to be identified when a state identifier is delivered to the state. A transition is said to be verified when the end state of the transition is identified. A state identifier of a state is a nonempty set of input sequences for the state such that the set of corresponding output sequences can characterize the state. Unique input/output (UIO) sequence is a popular state identifier such that UIO-based techniques are commonly used for test sequence generation.Since wireless communication protocols can also be modeled by FSMs, FSM-based conformance testing is also applicable to wireless protocol conformance testing in IoT. Zigbee is a typical wireless communication protocol and is divided into four layers: physical layer (PHY), media access control lay (MAC), network layer (NWK), and application layer (APL). The connection and release process of nodes in the MAC layer is modeled by the FSM in Figure1 and UIO sequences of every state are listed in Table 1. On this basis, test sequences based on FSMs can be constructed using UIO sequences as state identifiers. There is a test sequence s1(i1/o1)s4(i2i3/ o1o2)s3(i5)s2(i6/o1)s1(i1/o1)s4(i2i4/o1o3)s1(i1/o1)s4(i7)s1(i1/ o1)s4(i2i3/o1o2)s3(i7)s1(i1/o1)s4 of the FSM in Figure 1 based on UIO sequences in Table 1. When the input sequence of this test sequence is applied to an implementation, every state of the FSM in Figure 1 can be identified and every transition of the FSM in Figure 1 can be verified in the implementation. Meanwhile, an output sequence can be obtained. It can be concluded whether the connection and release process of nodes is executed as the specification specifies by comparing the obtained output sequence with the expected one in the test sequence.Table 1
UIO sequence of FSM corresponding to the connection and release process of Zigbee.
No. States UIO(s) Ex1 s1 i 1 / o 1  Ex2 s2 i6/o1  Ex3 s3 i5i6/o1  Ex4 s4 i 2 i 3 / o 1 o 2 i 2 i 4 / o 1 o 3Figure 1
FSM corresponding to the connection and release process of Zigbee.Test sequence reduction has long been an active research topic in FSM-based conformance testing. One approach is to convert the problem into the Rural Chinese Postman Problem from which a test sequence is extracted. For the purpose of transition verification every transition of an FSM is followed by an appended UIO sequence in the test sequence. Bo Yang et al. reduced test sequences by overlapping and multiple UIO sequences [11]. Benefiting from overlapping, more than one transition may be verified by a single appended UIO sequence. Hierons improved the method of UIO sequences through the use of an invertibility criterion, thereby achieving more overlapping [12], i.e., verifying even more transitions of an FSM with a single appended UIO sequence. However, multiple UIO sequences which are conducive to test sequence reduction are not considered by Hierons.In order to reduce the cost of testing while assuring the effectiveness, this paper presents an improved method to generate reduced test sequences for wireless protocol conformance testing of IoT. Transitions in a test sequence are of three kinds: a copy of transitions in an FSM, UIO sequences which have been appended to the test sequence for the purpose of transition verification for the FSM, and the transitions which have been appended to the test sequence. In the improved method, invertibility is taken into account to leverage as much overlapping as possible such that all the transitions of an FSM can be verified with as few appended UIO sequences as possible. Rural symmetric augmentation is the main measure for test sequence generation. The replicated transitions during the rural symmetric augmentation are exactly the transitions for concatenation of test subsequences in the test sequence. More options of rural symmetric augmentation can be supplied by multiple UIO sequences than those supplied by single UIO sequences; i.e., a sensible choice of UIO sequences can lead to a minimum number of replicated transitions during a rural symmetric augmentation, and a minimum number of transitions for concatenation are achieved in the test sequence. In this way, further reduced test sequences are obtained by the proposed method.The rest of the paper is organized as follows. In Section2, the basic concepts and assumptions used in this paper are presented. The improved method is described with simple examples in Section 3, and the soundness and effectiveness of the method are discussed. Experimental evaluation is set out in Section 4. Then, the related work about the testing of IoT is reviewed in Section 5 and the paper is concluded briefly in Section 6.


## 2. Preliminaries

In this section, we introduce the definitions related to FSMs and graphs, together with the assumptions necessary for FSM-based conformance testing.


### 2.1. Definitions

An FSM is formally defined as a 6-tupleM=(I,O,S,s0,δ,λ) where(i)
I and O are finite and nonempty sets of input symbols and output symbols, respectively;(ii)
S is a finite and nonempty set of states;(iii)
s0∈S represents the initial state of M;(iv)
δ:S×I→S denotes the state transition function;(v)
λ:S×I→O is the output function.According to this definition, when an input symboli is delivered to the current state s, M moves to the state s′=δ(s,i) with an output produced by λ(s,i). The transition function and output function can be extended to finite input sequences, i.e., for an input symbol i, an input sequence β∈I∗ (where I∗ is the set of finite sequences of input symbols), and a state s, δ(s,iβ)=δ(δ(s,i),β), and λ(s,iβ)=λ(s,i)λ(δ(s,i),β) where concatenation is denoted by juxtaposition.A transitiont is defined by a tuple (s,s′,i/o) where s is the start state, i is an input of s, o=λ(s,i) is the associated output, and s′=δ(s,i) is the end state. A transition (s,s′,i/o) is invertible if it is the unique transition ending at s′ with input i and output o.A UIO sequence of a state is an input/output sequence such that the input/output behavior exhibited by the state is unique, i.e., given a UIO sequenceβ of a state s, and the input sequence of β is denoted by βin; for any state s′≠s, it is always true that λ(s,βin)≠λ(s′,βin). A UIO sequence is irreducible if it is not a UIO sequence anymore when the end i/o symbol of the sequence is deleted. UIO sequences in this paper will be supposed irreducible unless otherwise specified. There may be more than one UIO sequence for a state and the UIO sequences may be of different length.An example FSMM1 is described in Figure 2 where S={s1,s2,s3}, I={a,b}, O={0,1} and s1 is the initial state of M1. There are four invertible transitions (s1,s2,a/0), (s2,s2,a/1), (s2,s3,b/1), and (s3,s1,a/1). The UIO sequences for every state are shown in Table 2.Table 2
UIO sequence ofM1.
No. States UIO(s) Ex1 s1 a / 0  Ex2 s2 b/1 ( a / 1 ) ( a / 1 ) ( a / 1 ) ( b / 1 )  E x 3 s 3 ( a / 1 ) ( a / 0 )Figure 2
FSMM1.An FSMM can be perceived as a labeled, directed graph G. A state of M is represented as a node of G, and there is an edge labeled with i/o from node s to s′ in G if and only if δ(s,i)=s′ and λ(s,i)=o in M, where s and s′ are the start and end node of the edge. The numbers of incoming and outgoing edges of a node are called the in-degree and out-degree of the node, respectively. If the in-degree equals out-degree at each node then the directed graph is symmetric. Suppose that G is an asymmetric directed graph; if G∗ is a symmetric directed graph generated from G by making copies of the edges then G∗ is a symmetric augmentation of G. When the total cost of copies of edges is minimized, G∗ is said to be a minimal symmetric augmentation of G. Suppose that E is the set of edges of G and E′⊆E, if G∗ is a symmetric directed graph generated from G by making copies of the edges such that each edge in E′ is included in G∗ at least once and the total cost of copies of edges is minimized then G∗ is called a rural symmetric augmentation of G. A sequence of contiguous edges β=(s1,s2,i1/o1)(s2,s3,i2/o2)…(sk-1,sk,ik-1/ok-1) forms a path of G where s1 and sk are the start and end node of the path, respectively. A path that starts and ends at the same node forms a tour, furthermore, if the tour traverses every edge of G exactly once then it is an Euler tour. A rural postman tour is a tour that traverses a given set of edges at least once. The Rural Chinese Postman Problem is to find a minimum-length rural postman tour for a given set of edges. FSMs and their directed graph representations are used interchangeably throughout this paper.


### 2.2. Assumptions

Given a specification FSMM with n states, the fault domain Ψ(I) of M is the set of all possible implementations of M over the input alphabet I of M. Ψn(I) refers to the implementations with up to n states in Ψ(I). This paper only focuses on implementations in Ψn(I).An FSMM is strongly connected if for any two distinct states s and s′ there is an input sequence β that takes M from s to s′; i.e., ∀s, s′∈S, s≠s′, ∃β∈I∗·(δ(s,β)=s′).Two statess and s′ are equivalent if for any input sequence there are always the same output sequences from s and s′. An FSM M without equivalent states is said to be minimal or reduced; otherwise M is reducible by joining equivalent states.An FSMM is deterministic if at any state for any input there is at most one transition leading to the next state. Otherwise, M is nondeterministic.Only strongly connected, minimal and deterministic FSMs are considered in this paper. In addition, it is assumed that UIO sequences for each state of an FSM are available and are derived from successor trees in advance. It is noted that only state transition functions in forms ofS×I→S are considered; i.e., state transitions without any input in IoT are out of the scope of this paper.


## 2.1. Definitions

An FSM is formally defined as a 6-tupleM=(I,O,S,s0,δ,λ) where(i)
I and O are finite and nonempty sets of input symbols and output symbols, respectively;(ii)
S is a finite and nonempty set of states;(iii)
s0∈S represents the initial state of M;(iv)
δ:S×I→S denotes the state transition function;(v)
λ:S×I→O is the output function.According to this definition, when an input symboli is delivered to the current state s, M moves to the state s′=δ(s,i) with an output produced by λ(s,i). The transition function and output function can be extended to finite input sequences, i.e., for an input symbol i, an input sequence β∈I∗ (where I∗ is the set of finite sequences of input symbols), and a state s, δ(s,iβ)=δ(δ(s,i),β), and λ(s,iβ)=λ(s,i)λ(δ(s,i),β) where concatenation is denoted by juxtaposition.A transitiont is defined by a tuple (s,s′,i/o) where s is the start state, i is an input of s, o=λ(s,i) is the associated output, and s′=δ(s,i) is the end state. A transition (s,s′,i/o) is invertible if it is the unique transition ending at s′ with input i and output o.A UIO sequence of a state is an input/output sequence such that the input/output behavior exhibited by the state is unique, i.e., given a UIO sequenceβ of a state s, and the input sequence of β is denoted by βin; for any state s′≠s, it is always true that λ(s,βin)≠λ(s′,βin). A UIO sequence is irreducible if it is not a UIO sequence anymore when the end i/o symbol of the sequence is deleted. UIO sequences in this paper will be supposed irreducible unless otherwise specified. There may be more than one UIO sequence for a state and the UIO sequences may be of different length.An example FSMM1 is described in Figure 2 where S={s1,s2,s3}, I={a,b}, O={0,1} and s1 is the initial state of M1. There are four invertible transitions (s1,s2,a/0), (s2,s2,a/1), (s2,s3,b/1), and (s3,s1,a/1). The UIO sequences for every state are shown in Table 2.Table 2
UIO sequence ofM1.
No. States UIO(s) Ex1 s1 a / 0  Ex2 s2 b/1 ( a / 1 ) ( a / 1 ) ( a / 1 ) ( b / 1 )  E x 3 s 3 ( a / 1 ) ( a / 0 )Figure 2
FSMM1.An FSMM can be perceived as a labeled, directed graph G. A state of M is represented as a node of G, and there is an edge labeled with i/o from node s to s′ in G if and only if δ(s,i)=s′ and λ(s,i)=o in M, where s and s′ are the start and end node of the edge. The numbers of incoming and outgoing edges of a node are called the in-degree and out-degree of the node, respectively. If the in-degree equals out-degree at each node then the directed graph is symmetric. Suppose that G is an asymmetric directed graph; if G∗ is a symmetric directed graph generated from G by making copies of the edges then G∗ is a symmetric augmentation of G. When the total cost of copies of edges is minimized, G∗ is said to be a minimal symmetric augmentation of G. Suppose that E is the set of edges of G and E′⊆E, if G∗ is a symmetric directed graph generated from G by making copies of the edges such that each edge in E′ is included in G∗ at least once and the total cost of copies of edges is minimized then G∗ is called a rural symmetric augmentation of G. A sequence of contiguous edges β=(s1,s2,i1/o1)(s2,s3,i2/o2)…(sk-1,sk,ik-1/ok-1) forms a path of G where s1 and sk are the start and end node of the path, respectively. A path that starts and ends at the same node forms a tour, furthermore, if the tour traverses every edge of G exactly once then it is an Euler tour. A rural postman tour is a tour that traverses a given set of edges at least once. The Rural Chinese Postman Problem is to find a minimum-length rural postman tour for a given set of edges. FSMs and their directed graph representations are used interchangeably throughout this paper.


## 2.2. Assumptions

Given a specification FSMM with n states, the fault domain Ψ(I) of M is the set of all possible implementations of M over the input alphabet I of M. Ψn(I) refers to the implementations with up to n states in Ψ(I). This paper only focuses on implementations in Ψn(I).An FSMM is strongly connected if for any two distinct states s and s′ there is an input sequence β that takes M from s to s′; i.e., ∀s, s′∈S, s≠s′, ∃β∈I∗·(δ(s,β)=s′).Two statess and s′ are equivalent if for any input sequence there are always the same output sequences from s and s′. An FSM M without equivalent states is said to be minimal or reduced; otherwise M is reducible by joining equivalent states.An FSMM is deterministic if at any state for any input there is at most one transition leading to the next state. Otherwise, M is nondeterministic.Only strongly connected, minimal and deterministic FSMs are considered in this paper. In addition, it is assumed that UIO sequences for each state of an FSM are available and are derived from successor trees in advance. It is noted that only state transition functions in forms ofS×I→S are considered; i.e., state transitions without any input in IoT are out of the scope of this paper.


## 3. Test Sequence Reduction

### 3.1. Key Properties of the Method

#### 3.1.1. Overlapping by Invertibility

Definition 1 (invertibility-dependent UIO sequence).
If a transition (s, s′, i/o) is invertible and β is a UIO sequence of s′, then (i/o)·β is an invertibility-dependent UIO sequence of s.The transition(s1,s2,a/0) of M1 in Figure 2 is invertible and (a/1)(b/1) is a UIO sequence of s2, then (a/0)(a/1)(b/1) is an invertibility-dependent UIO sequence of s1.Definition 2 (invertibility-dependent overlapping sequence).
Given a transition sequence(s1,s2,i1/o1)(s2,s3,i2/ o2)…(sj,sj+1,ij/oj) and a UIO sequence β of sj+1, if every transition (sk,sk+1,ik/ok)(1⩽k⩽j-1) is verified by an invertibility-dependent UIO sequence (ik+1/ok+1)·(ik+2/ok+2)…(ij/oj)·β when (sj,sj+1,ij/oj) is verified by β, then (s1,s2,i1/o1),(s2,s3,i2/o2)…(sj,sj+1,ij/oj) is an invertibility-dependent overlapping sequence (IDOS).There is a transition sequences1(a/0)s2(a/1)s2(b/1)s3(a/1)s1 of M1 in Figure 2 and a UIO sequence a/0 of s1. When the last transition (s3, s1, a/1) of s1(a/0)s2(a/1)s2(b/1)s3(a/1)s1 is verified by the UIO sequence a/0 of s1, by working backward (s2,s3,b/1) is verified by (a/1)(a/0), (s2,s2,a/1) is verified by (b/1)(a/1)(a/0), and (s1,s2,a/0) is verified by (a/1)(b/1)(a/1)(a/0); i.e., all the other transitions except the last one are verified by invertibility-dependent UIO sequences. As a result, s1(a/0)s2(a/1)s2(b/1)s3(a/1)s1 is an IDOS.For(ik+1/ok+1)·(ik+2/ok+2)…(ij/oj)·β  (1⩽k⩽j-1) to be invertibility-dependent UIO sequences, indispensable requirements for transitions in (s1,s2,i1/o1)(s2,s3,i2/o2)…(sj,sj+1,ij/oj) are put forward.Theorem 3.
Given a transition sequence(s1,s2,i1/o1)(s2,s3,i2/o2)…(sj,sj+1,ij/oj) and a UIO sequence β of sj+1, (s1,s2,i1/o1)(s2,s3,i2/o2)…(sj,sj+1,ij/oj) is an IDOS if and only if every transition (sk, sk+1, ik/ok) (2⩽k⩽j) is invertible.Proof.
The sufficiency of the condition is proved inductively by working backward. In the base case whenk=j, (sj-1, sj, ij-1/oj-1) is sure to be verified by an invertibility-dependent UIO sequence (ij/oj)·β since (sj, sj+1, ij/oj) is invertible. In the inductive step, assume that (sk-1,sk,ik-1/ok-1) (3⩽k⩽j-1) is verified by an invertibility-dependent UIO sequence γ, then (sk-2,sk-1,ik-2/ok-2) is definitely verified by an invertibility-dependent UIO sequence (ik-1/ok-1)·γ since (sk-1, sk, ik-1/ok-1) is invertible. In this way, every transition (sk,sk+1,ik/ok) (1⩽k⩽j-1) is backward verified inductively by an invertibility-dependent UIO sequence (ik+1/ok+1)·(ik+2/ok+2)…(ij/oj)·β when (sj, sj+1, ij/oj) is verified by β. Thus, it is a sufficient condition for a transition sequence (s1,s2,i1/o1)(s2,s3,i2/o2)…(sj,sj+1,ij/oj) to be an IDOS that every transition (sk, sk+1, ik/ok) (2⩽k⩽j) is invertible.
Next, the necessity of the condition is proved by contradiction. As shown in Figure3, suppose that (s1,s2,i1/o1)(s2,s3,i2/o2)…(sj,sj+1,ij/oj) is an IDOS with a noninvertible transition (sk, sk+1, ik/ok) (2⩽k⩽j); i.e., there is another transition (sk′, sk+1, ik/ok) ending at sk+1 with the same input and output. Obviously, sk cannot be identified by (ik/ok)·(ik+1/ok+1)…(ij/oj)·β; i.e., (sk-1, sk, ik-1/ok-1) cannot be verified by (ik/ok)·(ik+1/ok+1)…(ij/oj)·β. This contradicts with the assumption that (s1,s2,i1/o1)(s2,s3,i2/o2)…(sj,sj+1,ij/oj) is an IDOS. Accordingly, it is a necessary condition for a transition sequence (s1,s2,i1/o1)(s2,s3,i2/o2)…(sj,sj+1,ij/oj) to be an IDOS that every transition (sk, sk+1, ik/ok) (2⩽k⩽j) is invertible.Figure 3
A fragment of an FSM.Definition 4 (set of IDOSs).
Given a setT in which every sequence is an IDOS of an FSM M, if every transition of M is included in one and only one IDOS of T then T is a set of IDOSs of M.Of all the IDOSs from a state, a maximum-length IDOS is the one contains no fewer transitions than any other ones. There is no doubt that the longer IDOSs are, the more overlapping can be achieved, and the shorter test sequences will be obtained. For maximum overlapping, this paper is only interested in maximum-length IDOSs.The set{s1(a/0)s2(a/1)s2(b/1)s3(a/1)s1} is a set of IDOSs of M1 in Figure 2. There is only one IDOS in the set since the only IDOS s1(a/0)s2(a/1)s2(b/1)s3(a/1)s1 already covers all the transitions of M1. Obviously, s1(a/0)s2(a/1)s2(b/1)s3(a/1)s1 is also a maximum-length IDOS starting from s1.


#### 3.1.2. Multiple UIO Sequences

In the improved method, for any maximum-length IDOS(s1,s2,i1/o1)(s2,s3,i2/o2)…(sj,sj+1, ij/oj), the associated test subsequence is expressed as (s1,s2,i1/o1)(s2,s3,i2/o2)…(sj,sj+1,ij/oj)·β where β is a UIO sequence of sj+1. A minimum-length rural postman tour covering all the test subsequences is subsequently constructed by a rural symmetric augmentation and a test sequence is obtained from the tour. Accordingly, transitions for concatenation of test subsequences in the test sequence are derived from the transition replications during the rural symmetric augmentation. It is noted that different choice of UIO sequences may result in different rural symmetric augmentations; i.e., a minimum number of transition replications can be achieved by a sensible choice of UIO sequences during the rural symmetric augmentation. The minimum number of transition replications during the rural symmetric augmentation indicates the minimum number of transitions for concatenation of test subsequences in the test sequence, leading to a reduced test sequence. In other words, the result of using single UIO sequences can only in best-case scenarios obtain the same length of minimum-length rural postman tours as that of using multiple UIO sequences.


### 3.2. Design of the Method

It is known from Theorem3 that noninvertible transitions restrict the generation of IDOSs. From this point of view, FSMs can be partitioned into two subsets. One is FSMs with only invertible transitions and the other is FSMs with noninvertible transitions. For FSMs with only invertible transitions, if the FSMs are symmetric test sequences can be obtained directly. Otherwise, the FSMs should be augmented firstly. So FSMs with only invertible transitions can also be partitioned into two subsets. One is symmetric FSMs with only invertible transitions and the other is asymmetric FSMs with only invertible transitions. Generally, FSMs are classified into three categories: symmetric FSMs with only invertible transitions, asymmetric FSMs with only invertible transitions and FSMs with noninvertible transitions. The improved method is described in two steps for each type of FSMs and the detail varies for different types.Step 1.
Construct the set of maximum-length IDOSs.Step 2.
With the consideration of multiple UIO sequences, generate a minimum-length rural postman tour covering the set of maximum-length IDOSs and extract a test sequence from the tour.


#### 3.2.1. Symmetric FSMs with Only Invertible Transitions

Step 1 (maximum-length IDOSs generation).
There is an Euler tour in a directed graph if and only if the directed graph is strongly connected and symmetric. Under the assumption that all the FSMs are strongly connected, there must be Euler tours for symmetric FSMs with only invertible transitions. An Euler tour starting from and ending at the initial state is definitely an IDOS since there are only invertible transitions; furthermore, it is a maximum-length IDOS from the initial state since there is no other one containing more transitions. In other words, an Euler tour of a symmetric FSM with only invertible transitions is the only sequence in the set of maximum-length IDOSs.
Note that an Euler tour starting from and ending at the initial state may not be unique; i.e., there may be nonunique sets of maximum-length IDOSs. Nonetheless, all the sets of maximum-length IDOSs hold the following properties.
(i) There is only one maximum-length IDOS covering all the transitions of the FSM in every set of maximum-length IDOSs.
(ii) The start state of the maximum-length IDOS is the initial state of the FSM in every set of maximum-length IDOSs.
(iii) The end state of the maximum-length IDOS is the initial state of the FSM in every set of maximum-length IDOSs.Step 2 (test sequence generation).
For symmetric FSMs with only invertible transitions, test sequences are denoted by(s1,s2,i1/o1)(s2,s3,i2/o2)…(sj,s1,ij/oj)·β where (s1,s2,i1/o1)(s2,s3,i2/o2)…(sj,s1,ij/oj) is an Euler tour staring from and ending at s1 and β is a minimum-length UIO sequence of s1. It can be inferred that test sequences from different sets of maximum-length IDOSs are always of the same length when there is more than one set of maximum-length IDOSs. As a result, a randomly generated set of maximum-length IDOSs will do for test sequence generation of symmetric FSMs with only invertible transitions.M 1 in Figure 2 is a symmetric FSM with only invertible transitions and s1(a/0)s2(a/1)s2(b/1)s3(a/1)s1 is an Euler tour starting from and ending at s1. It is known from Step 1 that {s1(a/0)s2(a/1)s2(b/1)s3(a/1)s1} is a set of maximum-length IDOSs of M1. A test sequence s1(a/0)s2(a/1)s2(b/1)s3(a/1)s1(a/0)s2 is resulted from Step 2.


#### 3.2.2. Asymmetric FSMs with Only Invertible Transitions

Step 1 (maximum-length IDOSs generation).
An FSM is asymmetric which refers to the fact that there are nodes whose out-degree does not equal in-degree. It is known that∑s∈S‍dout(s)=∑s∈S‍din(s)=E where dout(s) and din(s) denote the out-degree and in-degree of a node, respectively [13]. The notation E refers to the number of edges in a directed graph. It is concluded from ∑s∈S‍douts=∑s∈S‍dins that ∑s∈S-‍dout>in(s)=∑s′∈S+‍din>out(s′) where S- and S+ are the sets of nodes whose out-degree outnumbers in-degree and in-degree outnumbers out-degree, respectively. Correspondingly, dout>in(s) and din>out(s′) represent the amount of out-degree over in-degree for a node in S- and the amount of in-degree over out-degree for a node in S+, respectively. The relation ∑s∈S‍dout(s)=∑s∈S‍din(s)=|E| implies that if a path passes through as many edges as possible exactly once then the path consumes as many out-degree and in-degree as possible. Every path through a node takes up one incoming edge as well as one outgoing edge, so if the out-degree outnumbers in-degree at a node, its outgoing edges cannot be traversed completely by paths passing through the node; i.e., some of its outgoing edges must instead be traversed by paths starting from the node. Thus, it is advisable to start the paths from nodes whose out-degree outnumbers in-degree if all the edges should be traversed exactly once with as few paths as possible. Moreover, it can be proved by contradiction that the paths from nodes whose out-degree outnumbers in-degree must end at nodes whose in-degree outnumbers out-degree otherwise the paths will continue to extend.
According to the above analysis, maximum-length IDOSs generation for asymmetric FSMs with only invertible transitions is performed as follows: start from a nodes∈S- and go down along an outgoing edge until a node s′∈S+ is reached and all the outgoing edges of s′ have been traversed. Thus a maximum-length IDOS from s to s′ is obtained. Add the maximum-length IDOS to the set of maximum-length IDOSs and delete the corresponding edges in the directed graph. Repeat the above process until all the nodes of the directed graph are isolated which implies that the set of maximum-length IDOSs is obtained.
Similarly, there may be nonunique sets of maximum-length IDOSs for asymmetric FSMs with only invertible transitions and all the sets of maximum-length IDOSs hold the following properties:
(i) For any set of maximum-length IDOSs,S- is the set of start states for maximum-length IDOSs.
(ii) For any set of maximum-length IDOSs,S+ is the set of end states for maximum-length IDOSs.
(iii) For any nodes∈S-, the number of maximum-length IDOSs starting from s is dout>in(s) in every set of maximum-length IDOSs.
(iv) For any nodes′∈S+, the number of maximum-length IDOSs ending at s′ is din>out(s′) in every set of maximum-length IDOSs.
(v) The total number of maximum-length IDOSs is∑s∈S-‍dout>in(s) which equals ∑s′∈S+‍din>out(s′) in each set of maximum-length IDOSs.Step 2 (test sequence generation).
With the set of maximum-length IDOSs, the same method as that of Bo Yang et al. is used to construct test sequences and the detail of the method is described in Algorithm1. The core of the method is the rural symmetric augmentation over an FSM augmented by maximum-length IDOSs and the multiple UIO sequences for the end states of maximum-length IDOSs. The core of the symmetric augmentation is the states involved. According to the above properties, for any set of maximum-length IDOSs, there is no difference about the states involved in the symmetric augmentation such that a random set of maximum-length IDOSs will do for asymmetric FSMs with only invertible transitions when there is more than one set of maximum-length IDOSs.
M 2 in Figure 4 is an asymmetric FSM with only invertible transitions and its UIO sequences are shown in Table 3. The nonunique sets of maximum-length IDOSs for M2 are listed as follows:Table 3
UIO sequence ofM2.
No. States UIO(s) Ex1 s1 b/0 ( a / 1 ) ( c / 0 ) ( a / 1 ) ( a / 1 )  E x 2 s 2 ( a / 1 ) ( b / 1 ) c / 0  E x 3 s 3 b / 1  E x 4 s 4 a / 0 c / 1Algorithm 1:Improved method of test sequence reduction.
Require: FSM M with n states {s1,s2,…,sn} in which s1 is the initial state; Set of non-invertible transitions P=ϕ; Set of maximum-length IDOSs Q=ϕ; Set of end states for non-invertible transitions S′=ϕ; UIO sequences of M; A minimum-length UIO sequence γ of s1; Ensure: Reduced test sequence β of M; (1)ifM is an FSM with m non-invertible transitionsthen (2)fori=1 to mdo (3)P=P∪ti where ti denotes a non-invertible transition; (4)M=M∖ti; (5)S′=S′∪ei where ei denotes the end state of ti; (6)end for (7)foreach state whose out-degree > in-degree in Mdo (8)Q=Q∪α where α is a maximum-length IDOS of j transitions generated from the state; (9)M=M∖ti (1⩽i⩽j); (10)end for (11)foreach connected component with Euler toursdo (12)ifStates in S′ can be found in an Euler tour t with k transitionsthen (13)Choose a state in S′ as the initial state of t; (14)end if (15)Q=Q∪t; (16)M=M∖ti (1⩽i⩽k); (17)end for (18)Q=Q∪P; (19)Concatenate non-invertible transitions and maximum-length IDOSs as long as the former’s end state is the latter’s start state; (20)M=M∪V∗ where V∗ is a new state set; (21)M=M∪T where T is a new transition set; (22)M=M∪U where U is a new transition set; (23)Construct a minimum-length rural postman tour over Q in the augmented M and extract a test sequence starting from s1; (24)Remove the transition sequence follows the UIO sequence of the maximum-length IDOS which is verified last in the minimum-length tour; (25)else (26)ifM is a symmetric FSM with only invertible transitionsthen (27)Q=Q∪t where t is an Euler tour starting from and ending at s1; (28)β=t⋅γ; (29)else (30)execute lines (7) through (9); (31)Execute lines (20) through (24); (32)end if (33)end ifFigure 4
FSMM2.{ s 1 ( a / 1 ) s 2 ( c / 0 ) s 2 ( a / 1 ) s 3 ( b / 1 ) s 4 ( c / 1 ) s 1 ( b / 0 ) s 2, s4(a/0)s2},{ s 1 ( a / 1 ) s 2 ( c / 0 ) s 2 ( a / 1 ) s 3 ( b / 1 ) s 4 ( a / 0 ) s 2, s4(c/1)s1(b/0)s2},{ s 1 ( b / 0 ) s 2 ( c / 0 ) s 2 ( a / 1 ) s 3 ( b / 1 ) s 4 ( c / 1 ) s 1 ( a / 1 ) s 2, s4(a/0)s2},{ s 1 ( b / 0 ) s 2 ( c / 0 ) s 2 ( a / 1 ) s 3 ( b / 1 ) s 4 ( a / 0 ) s 2, s4(c/1)s1(a/1)s2}.Clearly, all the sets of maximum-length IDOSs satisfy the properties in this section. The augmentation ofM2 using a random set of maximum-length IDOSs {s1(a/1)s2(c/0)s2(a/1)s3(b/1)s4(c/1)s1(b/0)s2,s4(a/0)s2} is shown in Figure 5 and the associated test sequence of M2 is s1(a/1)s2(c/0)s2(a/1)s3(b/1)s4(c/1)s1(b/0)s2(a/1)s3(b/ 1)s4(a/0)s2(c/0)s2.Figure 5
Augmentation ofM2.


#### 3.2.3. FSMs with Noninvertible Transitions

Step 1 (maximum-length IDOSs generation).
To address an FSM with noninvertible transitions in a similar way to the first two types of FSMs, noninvertible transitions are removed from the FSM and saved to a set. The remainder excluding noninvertible transitions is either an FSM or more than one connected component with only invertible transitions. And thus maximum-length IDOSs of the remainder excluding noninvertible transitions are generated in the same way as symmetric or asymmetric FSMs with only invertible transitions. Naturally, it comes to the same conclusion as the first two types of FSMs that a random set of maximum-length IDOSs will do when there are nonunique sets of maximum-length IDOSs. Next, a union of maximum-length IDOSs of the remainder excluding noninvertible transitions and all the noninvertible transitions is derived; moreover, whenever the start state of a maximum-length IDOS is the end state of a noninvertible transition, the maximum-length IDOS is concatenated with the noninvertible transition. If a maximum-length IDOS is an Euler tour then a node which is the end state of a noninvertible transition is preferred to be the start state of the tour. The set after all possible concatenations is a set of maximum-length IDOSs of the FSM with noninvertible transitions.
Given a union of maximum-length IDOSs of the remainder excluding noninvertible transitions as well as all the noninvertible transitions, there may be nonunique sets of maximum-length IDOSs for the FSM with noninvertible transitions because of different concatenation. The properties of nonunique sets of maximum-length IDOSs for FSMs with noninvertible transitions are described as follows:
(i) In any set of maximum-length IDOSs, for any states which is the start state of a maximum-length IDOS, if there are j maximum-length IDOSs starting from s then there must be j maximum-length IDOSs starting from s in every other set of maximum-length IDOSs.
(ii) In any set of maximum-length IDOSs, for any states which is the end state of a maximum-length IDOS, if there are k maximum-length IDOSs ending at s then there must be k maximum-length IDOSs ending at s in every other set of maximum-length IDOSs.Step 2 (test sequence generation).
For FSMs with noninvertible transitions, test sequence generation is in the same way as asymmetric FSMs with only invertible transitions, i.e., by means of rural symmetric augmentation over an FSM augmented by maximum-length IDOSs and the multiple UIO sequences for the end states of maximum-length IDOSs. The core of rural symmetric augmentation is still the states involved. It is known from the above properties that for any set of maximum-length IDOSs the states involved in the rural symmetric augmentation are the same such that a random concatenation will do.
ConsideringM3 in Figure 6 with UIO sequences in Table 4, the following nonunique union of maximum-length IDOSs of the remainder excluding noninvertible transitions and noninvertible transitions confirm that a random union will do.{s1(a/1)s2(c/0)s2(a/1)s3(b/1)s4(c/1)s1(b/0)s2,s4(a/ 0)s2,s1(d/0)s4,s3(d/0)s4},{s1(a/1)s2(c/0)s2(a/1)s3(b/1)s4(a/0)s2,s4(c/1)s1(b/ 0)s2,s1(d/0)s4,s3(d/0)s4},{s1(b/0)s2(c/0)s2(a/1)s3(b/1)s4(c/1)s1(a/1)s2,s4(a/ 0)s2,s1(d/0)s4,s3(d/0)s4},{s1(b/0)s2(c/0)s2(a/1)s3(b/1)s4(a/0)s2,s4(c/1)s1(a/ 1)s2,s1(d/0)s4,s3(d/0)s4}.
Take a random union of maximum-length IDOSs of the remainder excluding noninvertible transitions and noninvertible transitions{s1(a/1)s2(c/0)s2(a/1)s3(b/1)s4(c/1)s1(b/0)s2, s4(a/0)s2, s1(d/0)s4, s3(d/0)s4}; nonunique sets of maximum-length IDOSs from different concatenations {s1(a/1)s2(c/0)s2(a/1)s3(b/1)s4(c/1)s1(b/0)s2, s3(d/0)s4(a/0)s2, s1(d/0)s4} and {s1(a/1)s2(c/0)s2(a/1)s3(b/1)s4(c/1)s1(b/0)s2, s1(d/0)s4(a/0)s2, s3(d/0)s4} confirm that a random concatenation will do. The augmentation of M3 using a randomly concatenated set of maximum-length IDOSs {s1(a/1)s2(c/0)s2(a/1)s3(b/1)s4(c/1)s1(b/0)s2, s3(d/0)s4(a/0)s2, s1(d/0)s4} is shown in Figure 7 and the resulting test sequence is s1(d/0)s4(c/1)s1(a/1)s2(c/0)s2(a/1)s3(b/1)s4(c/1)s1(b/0)s2(c/0)s2(a/1)s3(d/0)s4(a/0)s2(c/0)s2.
Algorithm1 describes the detail of the improved method for all types of FSMs. Note that self-loops are always given priority to traverse in the process of maximum-length IDOSs generation. When creating the new state set V∗ in M, for the end state of every maximum-length IDOS, there is a state in V∗. When creating the new transition set T in M, for every maximum-length IDOS, there is a transition from the start state of the maximum-length IDOS to state vi∗ labeled with the corresponding label of the maximum-length IDOS. When creating a new transition set U in M, for every UIO sequence of the end state of every maximum-length IDOS, there is a transition from vi∗ to the end state of every UIO sequence labeled with the corresponding UIO sequence.Table 4
UIO sequence ofM3.
No. States UIO(s) Ex1 s1 b/0 ( a / 1 ) ( c / 0 ) ( a / 1 ) ( a / 1 )  E x 2 s 2 ( a / 1 ) ( b / 1 ) c / 0  E x 3 s3 b / 1  E x 4 s4 a / 0 c / 1Figure 6
FSMM3.Figure 7
Augmentation ofM3.Theorem 5.
Given an FSMM, suppose that Q is a set of maximum-length IDOSs and β is a sequence over Q generated from Algorithm 1, then β is a reduced test sequence of M.Proof.
The soundness ofβ is first proved; i.e., β is a test sequence of M. Then the effectiveness of β is assessed in terms of test generation and test execution cost, respectively. From a general standpoint, the notion of cost in the context of testing is complex and can be related to many factors. In our context, the effort required for generating test sequences is measured in terms of test sequence computational complexity. Test sequence execution cost is measured by the length of test sequences. Although these are clearly approximation methods, for practical reasons such methods have been commonly used in a number of testing studies [14–16].(  1) Soundness Analysis(i) Check whether every transition defined inM is verified in the implementationAll the maximum-length IDOSs inQ are included in β since β is a sequence over Q. Algorithm 1 indicates that every maximum-length IDOS in β is followed by a UIO sequence that verifies the last transition of the sequence. According to Definition 2, i.e., for any maximum-length IDOS (s1,s2,i1/o1)(s2,s3,i2/o2)…(sj,sj+1,ij/oj), if (sj, sj+1, ij/oj) is verified then every transition (sk, sk+1, ik/ok) (1⩽k⩽j-1) is verified, it is inferred that transitions of all the maximum-length IDOSs in Q are verified in β. According to Definition 4, i.e., every transition in M is included in one and only one IDOS of Q, it is concluded that every transition defined in M is verified in the implementation by β.(ii) Check whether every state inM is defined in the implementationM is supposed to be strongly connected such that for any state s of M there is at least one transition ending at s. It is proved that every transition defined in M is verified in β by identifying the end state of the transition; i.e., every state of M is checked in the implementation by β.(  2) Effectiveness Analysis(i) Analysis of Computational Complexity.The test sequence β has the same computational complexity as those of Aho et al. and Hierons since all the three test sequence generation methods are based on the max flow/min cost problem and the networks used in every method are of the same order.(ii) Analysis of Length Reduction. As mentioned above, transitions in a test sequence are of three kinds and the cost of a test sequence comes from the UIO sequences which have been appended for the purpose of transition verification and the transitions which have been appended for the purpose of concatenation of test subsequences to generate a minimum-length rural postman tour.For symmetric FSMs with only invertible transitions,β is in the form of (s1,s2,i1/o1)(s2,s3,i2/o2)…(sj,s1,ij/oj)·γ where (s1, s2, i1/o1)(s2, s3, i2/o2)…(sj, s1, ij/oj) is an Euler tour staring from and ending at s1 and γ is a minimum-length UIO sequence of s1; i.e., the cost of β only comes from one appended minimum-length UIO sequence of s1.For asymmetric FSMs with only invertible transitions, all the transitions are divided into a least number of maximum-length IDOSs; i.e., all the transitions are verified by a least number of appended UIO sequences such that the cost ofβ from the appended UIO sequences is minimal. For any maximum-length IDOS (s1, s2, i1/o1)(s2, s3, i2/o2)…(sj, sj+1, ij/oj), there is a test subsequence (s1, s2, i1/o1)(s2, s3, i2/o2)…(sj, sj+1, ij/oj)·γ where γ is a UIO sequence of sj+1. β is obtained from a minimum-length rural postman tour covering all the test subsequences. The minimum-length rural postman tour is generated by the rural symmetric augmentation and thus the cost of β for concatenation comes from the replicated transitions during the rural symmetric augmentation. Benefiting from multiple UIO sequences, a minimum number of transition replications is reached by a sensible choice of UIO sequences during the rural symmetric augmentation; i.e., the cost of β from the transitions for concatenation is minimal.For FSMs with noninvertible transitions, transitions excluding noninvertible ones are divided into a least number of IDOSs. According to Theorem3, the acquired IDOSs concatenate with noninvertible transitions as much as possible such that a set of maximum-length IDOSs with a least number of maximum-length IDOSs is obtained; i.e., all the transitions of an FSM with noninvertible transitions are verified by a least number of appended UIO sequences such that the cost of β from the appended UIO sequences is minimal. Similarly, a minimum number of transition replications during the rural symmetric augmentation is reached by a sensible choice of UIO sequences; i.e., the cost of β from the transitions for concatenation is minimal.In short, for all types of FSMs, the execution cost is reduced effectively without increasing the generation cost such thatβ is a reduced test sequence of M.


## 3.1. Key Properties of the Method

### 3.1.1. Overlapping by Invertibility

Definition 1 (invertibility-dependent UIO sequence).
If a transition (s, s′, i/o) is invertible and β is a UIO sequence of s′, then (i/o)·β is an invertibility-dependent UIO sequence of s.The transition(s1,s2,a/0) of M1 in Figure 2 is invertible and (a/1)(b/1) is a UIO sequence of s2, then (a/0)(a/1)(b/1) is an invertibility-dependent UIO sequence of s1.Definition 2 (invertibility-dependent overlapping sequence).
Given a transition sequence(s1,s2,i1/o1)(s2,s3,i2/ o2)…(sj,sj+1,ij/oj) and a UIO sequence β of sj+1, if every transition (sk,sk+1,ik/ok)(1⩽k⩽j-1) is verified by an invertibility-dependent UIO sequence (ik+1/ok+1)·(ik+2/ok+2)…(ij/oj)·β when (sj,sj+1,ij/oj) is verified by β, then (s1,s2,i1/o1),(s2,s3,i2/o2)…(sj,sj+1,ij/oj) is an invertibility-dependent overlapping sequence (IDOS).There is a transition sequences1(a/0)s2(a/1)s2(b/1)s3(a/1)s1 of M1 in Figure 2 and a UIO sequence a/0 of s1. When the last transition (s3, s1, a/1) of s1(a/0)s2(a/1)s2(b/1)s3(a/1)s1 is verified by the UIO sequence a/0 of s1, by working backward (s2,s3,b/1) is verified by (a/1)(a/0), (s2,s2,a/1) is verified by (b/1)(a/1)(a/0), and (s1,s2,a/0) is verified by (a/1)(b/1)(a/1)(a/0); i.e., all the other transitions except the last one are verified by invertibility-dependent UIO sequences. As a result, s1(a/0)s2(a/1)s2(b/1)s3(a/1)s1 is an IDOS.For(ik+1/ok+1)·(ik+2/ok+2)…(ij/oj)·β  (1⩽k⩽j-1) to be invertibility-dependent UIO sequences, indispensable requirements for transitions in (s1,s2,i1/o1)(s2,s3,i2/o2)…(sj,sj+1,ij/oj) are put forward.Theorem 3.
Given a transition sequence(s1,s2,i1/o1)(s2,s3,i2/o2)…(sj,sj+1,ij/oj) and a UIO sequence β of sj+1, (s1,s2,i1/o1)(s2,s3,i2/o2)…(sj,sj+1,ij/oj) is an IDOS if and only if every transition (sk, sk+1, ik/ok) (2⩽k⩽j) is invertible.Proof.
The sufficiency of the condition is proved inductively by working backward. In the base case whenk=j, (sj-1, sj, ij-1/oj-1) is sure to be verified by an invertibility-dependent UIO sequence (ij/oj)·β since (sj, sj+1, ij/oj) is invertible. In the inductive step, assume that (sk-1,sk,ik-1/ok-1) (3⩽k⩽j-1) is verified by an invertibility-dependent UIO sequence γ, then (sk-2,sk-1,ik-2/ok-2) is definitely verified by an invertibility-dependent UIO sequence (ik-1/ok-1)·γ since (sk-1, sk, ik-1/ok-1) is invertible. In this way, every transition (sk,sk+1,ik/ok) (1⩽k⩽j-1) is backward verified inductively by an invertibility-dependent UIO sequence (ik+1/ok+1)·(ik+2/ok+2)…(ij/oj)·β when (sj, sj+1, ij/oj) is verified by β. Thus, it is a sufficient condition for a transition sequence (s1,s2,i1/o1)(s2,s3,i2/o2)…(sj,sj+1,ij/oj) to be an IDOS that every transition (sk, sk+1, ik/ok) (2⩽k⩽j) is invertible.
Next, the necessity of the condition is proved by contradiction. As shown in Figure3, suppose that (s1,s2,i1/o1)(s2,s3,i2/o2)…(sj,sj+1,ij/oj) is an IDOS with a noninvertible transition (sk, sk+1, ik/ok) (2⩽k⩽j); i.e., there is another transition (sk′, sk+1, ik/ok) ending at sk+1 with the same input and output. Obviously, sk cannot be identified by (ik/ok)·(ik+1/ok+1)…(ij/oj)·β; i.e., (sk-1, sk, ik-1/ok-1) cannot be verified by (ik/ok)·(ik+1/ok+1)…(ij/oj)·β. This contradicts with the assumption that (s1,s2,i1/o1)(s2,s3,i2/o2)…(sj,sj+1,ij/oj) is an IDOS. Accordingly, it is a necessary condition for a transition sequence (s1,s2,i1/o1)(s2,s3,i2/o2)…(sj,sj+1,ij/oj) to be an IDOS that every transition (sk, sk+1, ik/ok) (2⩽k⩽j) is invertible.Figure 3
A fragment of an FSM.Definition 4 (set of IDOSs).
Given a setT in which every sequence is an IDOS of an FSM M, if every transition of M is included in one and only one IDOS of T then T is a set of IDOSs of M.Of all the IDOSs from a state, a maximum-length IDOS is the one contains no fewer transitions than any other ones. There is no doubt that the longer IDOSs are, the more overlapping can be achieved, and the shorter test sequences will be obtained. For maximum overlapping, this paper is only interested in maximum-length IDOSs.The set{s1(a/0)s2(a/1)s2(b/1)s3(a/1)s1} is a set of IDOSs of M1 in Figure 2. There is only one IDOS in the set since the only IDOS s1(a/0)s2(a/1)s2(b/1)s3(a/1)s1 already covers all the transitions of M1. Obviously, s1(a/0)s2(a/1)s2(b/1)s3(a/1)s1 is also a maximum-length IDOS starting from s1.


### 3.1.2. Multiple UIO Sequences

In the improved method, for any maximum-length IDOS(s1,s2,i1/o1)(s2,s3,i2/o2)…(sj,sj+1, ij/oj), the associated test subsequence is expressed as (s1,s2,i1/o1)(s2,s3,i2/o2)…(sj,sj+1,ij/oj)·β where β is a UIO sequence of sj+1. A minimum-length rural postman tour covering all the test subsequences is subsequently constructed by a rural symmetric augmentation and a test sequence is obtained from the tour. Accordingly, transitions for concatenation of test subsequences in the test sequence are derived from the transition replications during the rural symmetric augmentation. It is noted that different choice of UIO sequences may result in different rural symmetric augmentations; i.e., a minimum number of transition replications can be achieved by a sensible choice of UIO sequences during the rural symmetric augmentation. The minimum number of transition replications during the rural symmetric augmentation indicates the minimum number of transitions for concatenation of test subsequences in the test sequence, leading to a reduced test sequence. In other words, the result of using single UIO sequences can only in best-case scenarios obtain the same length of minimum-length rural postman tours as that of using multiple UIO sequences.


## 3.1.1. Overlapping by Invertibility

Definition 1 (invertibility-dependent UIO sequence).
If a transition (s, s′, i/o) is invertible and β is a UIO sequence of s′, then (i/o)·β is an invertibility-dependent UIO sequence of s.The transition(s1,s2,a/0) of M1 in Figure 2 is invertible and (a/1)(b/1) is a UIO sequence of s2, then (a/0)(a/1)(b/1) is an invertibility-dependent UIO sequence of s1.Definition 2 (invertibility-dependent overlapping sequence).
Given a transition sequence(s1,s2,i1/o1)(s2,s3,i2/ o2)…(sj,sj+1,ij/oj) and a UIO sequence β of sj+1, if every transition (sk,sk+1,ik/ok)(1⩽k⩽j-1) is verified by an invertibility-dependent UIO sequence (ik+1/ok+1)·(ik+2/ok+2)…(ij/oj)·β when (sj,sj+1,ij/oj) is verified by β, then (s1,s2,i1/o1),(s2,s3,i2/o2)…(sj,sj+1,ij/oj) is an invertibility-dependent overlapping sequence (IDOS).There is a transition sequences1(a/0)s2(a/1)s2(b/1)s3(a/1)s1 of M1 in Figure 2 and a UIO sequence a/0 of s1. When the last transition (s3, s1, a/1) of s1(a/0)s2(a/1)s2(b/1)s3(a/1)s1 is verified by the UIO sequence a/0 of s1, by working backward (s2,s3,b/1) is verified by (a/1)(a/0), (s2,s2,a/1) is verified by (b/1)(a/1)(a/0), and (s1,s2,a/0) is verified by (a/1)(b/1)(a/1)(a/0); i.e., all the other transitions except the last one are verified by invertibility-dependent UIO sequences. As a result, s1(a/0)s2(a/1)s2(b/1)s3(a/1)s1 is an IDOS.For(ik+1/ok+1)·(ik+2/ok+2)…(ij/oj)·β  (1⩽k⩽j-1) to be invertibility-dependent UIO sequences, indispensable requirements for transitions in (s1,s2,i1/o1)(s2,s3,i2/o2)…(sj,sj+1,ij/oj) are put forward.Theorem 3.
Given a transition sequence(s1,s2,i1/o1)(s2,s3,i2/o2)…(sj,sj+1,ij/oj) and a UIO sequence β of sj+1, (s1,s2,i1/o1)(s2,s3,i2/o2)…(sj,sj+1,ij/oj) is an IDOS if and only if every transition (sk, sk+1, ik/ok) (2⩽k⩽j) is invertible.Proof.
The sufficiency of the condition is proved inductively by working backward. In the base case whenk=j, (sj-1, sj, ij-1/oj-1) is sure to be verified by an invertibility-dependent UIO sequence (ij/oj)·β since (sj, sj+1, ij/oj) is invertible. In the inductive step, assume that (sk-1,sk,ik-1/ok-1) (3⩽k⩽j-1) is verified by an invertibility-dependent UIO sequence γ, then (sk-2,sk-1,ik-2/ok-2) is definitely verified by an invertibility-dependent UIO sequence (ik-1/ok-1)·γ since (sk-1, sk, ik-1/ok-1) is invertible. In this way, every transition (sk,sk+1,ik/ok) (1⩽k⩽j-1) is backward verified inductively by an invertibility-dependent UIO sequence (ik+1/ok+1)·(ik+2/ok+2)…(ij/oj)·β when (sj, sj+1, ij/oj) is verified by β. Thus, it is a sufficient condition for a transition sequence (s1,s2,i1/o1)(s2,s3,i2/o2)…(sj,sj+1,ij/oj) to be an IDOS that every transition (sk, sk+1, ik/ok) (2⩽k⩽j) is invertible.
Next, the necessity of the condition is proved by contradiction. As shown in Figure3, suppose that (s1,s2,i1/o1)(s2,s3,i2/o2)…(sj,sj+1,ij/oj) is an IDOS with a noninvertible transition (sk, sk+1, ik/ok) (2⩽k⩽j); i.e., there is another transition (sk′, sk+1, ik/ok) ending at sk+1 with the same input and output. Obviously, sk cannot be identified by (ik/ok)·(ik+1/ok+1)…(ij/oj)·β; i.e., (sk-1, sk, ik-1/ok-1) cannot be verified by (ik/ok)·(ik+1/ok+1)…(ij/oj)·β. This contradicts with the assumption that (s1,s2,i1/o1)(s2,s3,i2/o2)…(sj,sj+1,ij/oj) is an IDOS. Accordingly, it is a necessary condition for a transition sequence (s1,s2,i1/o1)(s2,s3,i2/o2)…(sj,sj+1,ij/oj) to be an IDOS that every transition (sk, sk+1, ik/ok) (2⩽k⩽j) is invertible.Figure 3
A fragment of an FSM.Definition 4 (set of IDOSs).
Given a setT in which every sequence is an IDOS of an FSM M, if every transition of M is included in one and only one IDOS of T then T is a set of IDOSs of M.Of all the IDOSs from a state, a maximum-length IDOS is the one contains no fewer transitions than any other ones. There is no doubt that the longer IDOSs are, the more overlapping can be achieved, and the shorter test sequences will be obtained. For maximum overlapping, this paper is only interested in maximum-length IDOSs.The set{s1(a/0)s2(a/1)s2(b/1)s3(a/1)s1} is a set of IDOSs of M1 in Figure 2. There is only one IDOS in the set since the only IDOS s1(a/0)s2(a/1)s2(b/1)s3(a/1)s1 already covers all the transitions of M1. Obviously, s1(a/0)s2(a/1)s2(b/1)s3(a/1)s1 is also a maximum-length IDOS starting from s1.


## 3.1.2. Multiple UIO Sequences

In the improved method, for any maximum-length IDOS(s1,s2,i1/o1)(s2,s3,i2/o2)…(sj,sj+1, ij/oj), the associated test subsequence is expressed as (s1,s2,i1/o1)(s2,s3,i2/o2)…(sj,sj+1,ij/oj)·β where β is a UIO sequence of sj+1. A minimum-length rural postman tour covering all the test subsequences is subsequently constructed by a rural symmetric augmentation and a test sequence is obtained from the tour. Accordingly, transitions for concatenation of test subsequences in the test sequence are derived from the transition replications during the rural symmetric augmentation. It is noted that different choice of UIO sequences may result in different rural symmetric augmentations; i.e., a minimum number of transition replications can be achieved by a sensible choice of UIO sequences during the rural symmetric augmentation. The minimum number of transition replications during the rural symmetric augmentation indicates the minimum number of transitions for concatenation of test subsequences in the test sequence, leading to a reduced test sequence. In other words, the result of using single UIO sequences can only in best-case scenarios obtain the same length of minimum-length rural postman tours as that of using multiple UIO sequences.


## 3.2. Design of the Method

It is known from Theorem3 that noninvertible transitions restrict the generation of IDOSs. From this point of view, FSMs can be partitioned into two subsets. One is FSMs with only invertible transitions and the other is FSMs with noninvertible transitions. For FSMs with only invertible transitions, if the FSMs are symmetric test sequences can be obtained directly. Otherwise, the FSMs should be augmented firstly. So FSMs with only invertible transitions can also be partitioned into two subsets. One is symmetric FSMs with only invertible transitions and the other is asymmetric FSMs with only invertible transitions. Generally, FSMs are classified into three categories: symmetric FSMs with only invertible transitions, asymmetric FSMs with only invertible transitions and FSMs with noninvertible transitions. The improved method is described in two steps for each type of FSMs and the detail varies for different types.Step 1.
Construct the set of maximum-length IDOSs.Step 2.
With the consideration of multiple UIO sequences, generate a minimum-length rural postman tour covering the set of maximum-length IDOSs and extract a test sequence from the tour.


### 3.2.1. Symmetric FSMs with Only Invertible Transitions

Step 1 (maximum-length IDOSs generation).
There is an Euler tour in a directed graph if and only if the directed graph is strongly connected and symmetric. Under the assumption that all the FSMs are strongly connected, there must be Euler tours for symmetric FSMs with only invertible transitions. An Euler tour starting from and ending at the initial state is definitely an IDOS since there are only invertible transitions; furthermore, it is a maximum-length IDOS from the initial state since there is no other one containing more transitions. In other words, an Euler tour of a symmetric FSM with only invertible transitions is the only sequence in the set of maximum-length IDOSs.
Note that an Euler tour starting from and ending at the initial state may not be unique; i.e., there may be nonunique sets of maximum-length IDOSs. Nonetheless, all the sets of maximum-length IDOSs hold the following properties.
(i) There is only one maximum-length IDOS covering all the transitions of the FSM in every set of maximum-length IDOSs.
(ii) The start state of the maximum-length IDOS is the initial state of the FSM in every set of maximum-length IDOSs.
(iii) The end state of the maximum-length IDOS is the initial state of the FSM in every set of maximum-length IDOSs.Step 2 (test sequence generation).
For symmetric FSMs with only invertible transitions, test sequences are denoted by(s1,s2,i1/o1)(s2,s3,i2/o2)…(sj,s1,ij/oj)·β where (s1,s2,i1/o1)(s2,s3,i2/o2)…(sj,s1,ij/oj) is an Euler tour staring from and ending at s1 and β is a minimum-length UIO sequence of s1. It can be inferred that test sequences from different sets of maximum-length IDOSs are always of the same length when there is more than one set of maximum-length IDOSs. As a result, a randomly generated set of maximum-length IDOSs will do for test sequence generation of symmetric FSMs with only invertible transitions.M 1 in Figure 2 is a symmetric FSM with only invertible transitions and s1(a/0)s2(a/1)s2(b/1)s3(a/1)s1 is an Euler tour starting from and ending at s1. It is known from Step 1 that {s1(a/0)s2(a/1)s2(b/1)s3(a/1)s1} is a set of maximum-length IDOSs of M1. A test sequence s1(a/0)s2(a/1)s2(b/1)s3(a/1)s1(a/0)s2 is resulted from Step 2.


### 3.2.2. Asymmetric FSMs with Only Invertible Transitions

Step 1 (maximum-length IDOSs generation).
An FSM is asymmetric which refers to the fact that there are nodes whose out-degree does not equal in-degree. It is known that∑s∈S‍dout(s)=∑s∈S‍din(s)=E where dout(s) and din(s) denote the out-degree and in-degree of a node, respectively [13]. The notation E refers to the number of edges in a directed graph. It is concluded from ∑s∈S‍douts=∑s∈S‍dins that ∑s∈S-‍dout>in(s)=∑s′∈S+‍din>out(s′) where S- and S+ are the sets of nodes whose out-degree outnumbers in-degree and in-degree outnumbers out-degree, respectively. Correspondingly, dout>in(s) and din>out(s′) represent the amount of out-degree over in-degree for a node in S- and the amount of in-degree over out-degree for a node in S+, respectively. The relation ∑s∈S‍dout(s)=∑s∈S‍din(s)=|E| implies that if a path passes through as many edges as possible exactly once then the path consumes as many out-degree and in-degree as possible. Every path through a node takes up one incoming edge as well as one outgoing edge, so if the out-degree outnumbers in-degree at a node, its outgoing edges cannot be traversed completely by paths passing through the node; i.e., some of its outgoing edges must instead be traversed by paths starting from the node. Thus, it is advisable to start the paths from nodes whose out-degree outnumbers in-degree if all the edges should be traversed exactly once with as few paths as possible. Moreover, it can be proved by contradiction that the paths from nodes whose out-degree outnumbers in-degree must end at nodes whose in-degree outnumbers out-degree otherwise the paths will continue to extend.
According to the above analysis, maximum-length IDOSs generation for asymmetric FSMs with only invertible transitions is performed as follows: start from a nodes∈S- and go down along an outgoing edge until a node s′∈S+ is reached and all the outgoing edges of s′ have been traversed. Thus a maximum-length IDOS from s to s′ is obtained. Add the maximum-length IDOS to the set of maximum-length IDOSs and delete the corresponding edges in the directed graph. Repeat the above process until all the nodes of the directed graph are isolated which implies that the set of maximum-length IDOSs is obtained.
Similarly, there may be nonunique sets of maximum-length IDOSs for asymmetric FSMs with only invertible transitions and all the sets of maximum-length IDOSs hold the following properties:
(i) For any set of maximum-length IDOSs,S- is the set of start states for maximum-length IDOSs.
(ii) For any set of maximum-length IDOSs,S+ is the set of end states for maximum-length IDOSs.
(iii) For any nodes∈S-, the number of maximum-length IDOSs starting from s is dout>in(s) in every set of maximum-length IDOSs.
(iv) For any nodes′∈S+, the number of maximum-length IDOSs ending at s′ is din>out(s′) in every set of maximum-length IDOSs.
(v) The total number of maximum-length IDOSs is∑s∈S-‍dout>in(s) which equals ∑s′∈S+‍din>out(s′) in each set of maximum-length IDOSs.Step 2 (test sequence generation).
With the set of maximum-length IDOSs, the same method as that of Bo Yang et al. is used to construct test sequences and the detail of the method is described in Algorithm1. The core of the method is the rural symmetric augmentation over an FSM augmented by maximum-length IDOSs and the multiple UIO sequences for the end states of maximum-length IDOSs. The core of the symmetric augmentation is the states involved. According to the above properties, for any set of maximum-length IDOSs, there is no difference about the states involved in the symmetric augmentation such that a random set of maximum-length IDOSs will do for asymmetric FSMs with only invertible transitions when there is more than one set of maximum-length IDOSs.
M 2 in Figure 4 is an asymmetric FSM with only invertible transitions and its UIO sequences are shown in Table 3. The nonunique sets of maximum-length IDOSs for M2 are listed as follows:Table 3
UIO sequence ofM2.
No. States UIO(s) Ex1 s1 b/0 ( a / 1 ) ( c / 0 ) ( a / 1 ) ( a / 1 )  E x 2 s 2 ( a / 1 ) ( b / 1 ) c / 0  E x 3 s 3 b / 1  E x 4 s 4 a / 0 c / 1Algorithm 1:Improved method of test sequence reduction.
Require: FSM M with n states {s1,s2,…,sn} in which s1 is the initial state; Set of non-invertible transitions P=ϕ; Set of maximum-length IDOSs Q=ϕ; Set of end states for non-invertible transitions S′=ϕ; UIO sequences of M; A minimum-length UIO sequence γ of s1; Ensure: Reduced test sequence β of M; (1)ifM is an FSM with m non-invertible transitionsthen (2)fori=1 to mdo (3)P=P∪ti where ti denotes a non-invertible transition; (4)M=M∖ti; (5)S′=S′∪ei where ei denotes the end state of ti; (6)end for (7)foreach state whose out-degree > in-degree in Mdo (8)Q=Q∪α where α is a maximum-length IDOS of j transitions generated from the state; (9)M=M∖ti (1⩽i⩽j); (10)end for (11)foreach connected component with Euler toursdo (12)ifStates in S′ can be found in an Euler tour t with k transitionsthen (13)Choose a state in S′ as the initial state of t; (14)end if (15)Q=Q∪t; (16)M=M∖ti (1⩽i⩽k); (17)end for (18)Q=Q∪P; (19)Concatenate non-invertible transitions and maximum-length IDOSs as long as the former’s end state is the latter’s start state; (20)M=M∪V∗ where V∗ is a new state set; (21)M=M∪T where T is a new transition set; (22)M=M∪U where U is a new transition set; (23)Construct a minimum-length rural postman tour over Q in the augmented M and extract a test sequence starting from s1; (24)Remove the transition sequence follows the UIO sequence of the maximum-length IDOS which is verified last in the minimum-length tour; (25)else (26)ifM is a symmetric FSM with only invertible transitionsthen (27)Q=Q∪t where t is an Euler tour starting from and ending at s1; (28)β=t⋅γ; (29)else (30)execute lines (7) through (9); (31)Execute lines (20) through (24); (32)end if (33)end ifFigure 4
FSMM2.{ s 1 ( a / 1 ) s 2 ( c / 0 ) s 2 ( a / 1 ) s 3 ( b / 1 ) s 4 ( c / 1 ) s 1 ( b / 0 ) s 2, s4(a/0)s2},{ s 1 ( a / 1 ) s 2 ( c / 0 ) s 2 ( a / 1 ) s 3 ( b / 1 ) s 4 ( a / 0 ) s 2, s4(c/1)s1(b/0)s2},{ s 1 ( b / 0 ) s 2 ( c / 0 ) s 2 ( a / 1 ) s 3 ( b / 1 ) s 4 ( c / 1 ) s 1 ( a / 1 ) s 2, s4(a/0)s2},{ s 1 ( b / 0 ) s 2 ( c / 0 ) s 2 ( a / 1 ) s 3 ( b / 1 ) s 4 ( a / 0 ) s 2, s4(c/1)s1(a/1)s2}.Clearly, all the sets of maximum-length IDOSs satisfy the properties in this section. The augmentation ofM2 using a random set of maximum-length IDOSs {s1(a/1)s2(c/0)s2(a/1)s3(b/1)s4(c/1)s1(b/0)s2,s4(a/0)s2} is shown in Figure 5 and the associated test sequence of M2 is s1(a/1)s2(c/0)s2(a/1)s3(b/1)s4(c/1)s1(b/0)s2(a/1)s3(b/ 1)s4(a/0)s2(c/0)s2.Figure 5
Augmentation ofM2.


### 3.2.3. FSMs with Noninvertible Transitions

Step 1 (maximum-length IDOSs generation).
To address an FSM with noninvertible transitions in a similar way to the first two types of FSMs, noninvertible transitions are removed from the FSM and saved to a set. The remainder excluding noninvertible transitions is either an FSM or more than one connected component with only invertible transitions. And thus maximum-length IDOSs of the remainder excluding noninvertible transitions are generated in the same way as symmetric or asymmetric FSMs with only invertible transitions. Naturally, it comes to the same conclusion as the first two types of FSMs that a random set of maximum-length IDOSs will do when there are nonunique sets of maximum-length IDOSs. Next, a union of maximum-length IDOSs of the remainder excluding noninvertible transitions and all the noninvertible transitions is derived; moreover, whenever the start state of a maximum-length IDOS is the end state of a noninvertible transition, the maximum-length IDOS is concatenated with the noninvertible transition. If a maximum-length IDOS is an Euler tour then a node which is the end state of a noninvertible transition is preferred to be the start state of the tour. The set after all possible concatenations is a set of maximum-length IDOSs of the FSM with noninvertible transitions.
Given a union of maximum-length IDOSs of the remainder excluding noninvertible transitions as well as all the noninvertible transitions, there may be nonunique sets of maximum-length IDOSs for the FSM with noninvertible transitions because of different concatenation. The properties of nonunique sets of maximum-length IDOSs for FSMs with noninvertible transitions are described as follows:
(i) In any set of maximum-length IDOSs, for any states which is the start state of a maximum-length IDOS, if there are j maximum-length IDOSs starting from s then there must be j maximum-length IDOSs starting from s in every other set of maximum-length IDOSs.
(ii) In any set of maximum-length IDOSs, for any states which is the end state of a maximum-length IDOS, if there are k maximum-length IDOSs ending at s then there must be k maximum-length IDOSs ending at s in every other set of maximum-length IDOSs.Step 2 (test sequence generation).
For FSMs with noninvertible transitions, test sequence generation is in the same way as asymmetric FSMs with only invertible transitions, i.e., by means of rural symmetric augmentation over an FSM augmented by maximum-length IDOSs and the multiple UIO sequences for the end states of maximum-length IDOSs. The core of rural symmetric augmentation is still the states involved. It is known from the above properties that for any set of maximum-length IDOSs the states involved in the rural symmetric augmentation are the same such that a random concatenation will do.
ConsideringM3 in Figure 6 with UIO sequences in Table 4, the following nonunique union of maximum-length IDOSs of the remainder excluding noninvertible transitions and noninvertible transitions confirm that a random union will do.{s1(a/1)s2(c/0)s2(a/1)s3(b/1)s4(c/1)s1(b/0)s2,s4(a/ 0)s2,s1(d/0)s4,s3(d/0)s4},{s1(a/1)s2(c/0)s2(a/1)s3(b/1)s4(a/0)s2,s4(c/1)s1(b/ 0)s2,s1(d/0)s4,s3(d/0)s4},{s1(b/0)s2(c/0)s2(a/1)s3(b/1)s4(c/1)s1(a/1)s2,s4(a/ 0)s2,s1(d/0)s4,s3(d/0)s4},{s1(b/0)s2(c/0)s2(a/1)s3(b/1)s4(a/0)s2,s4(c/1)s1(a/ 1)s2,s1(d/0)s4,s3(d/0)s4}.
Take a random union of maximum-length IDOSs of the remainder excluding noninvertible transitions and noninvertible transitions{s1(a/1)s2(c/0)s2(a/1)s3(b/1)s4(c/1)s1(b/0)s2, s4(a/0)s2, s1(d/0)s4, s3(d/0)s4}; nonunique sets of maximum-length IDOSs from different concatenations {s1(a/1)s2(c/0)s2(a/1)s3(b/1)s4(c/1)s1(b/0)s2, s3(d/0)s4(a/0)s2, s1(d/0)s4} and {s1(a/1)s2(c/0)s2(a/1)s3(b/1)s4(c/1)s1(b/0)s2, s1(d/0)s4(a/0)s2, s3(d/0)s4} confirm that a random concatenation will do. The augmentation of M3 using a randomly concatenated set of maximum-length IDOSs {s1(a/1)s2(c/0)s2(a/1)s3(b/1)s4(c/1)s1(b/0)s2, s3(d/0)s4(a/0)s2, s1(d/0)s4} is shown in Figure 7 and the resulting test sequence is s1(d/0)s4(c/1)s1(a/1)s2(c/0)s2(a/1)s3(b/1)s4(c/1)s1(b/0)s2(c/0)s2(a/1)s3(d/0)s4(a/0)s2(c/0)s2.
Algorithm1 describes the detail of the improved method for all types of FSMs. Note that self-loops are always given priority to traverse in the process of maximum-length IDOSs generation. When creating the new state set V∗ in M, for the end state of every maximum-length IDOS, there is a state in V∗. When creating the new transition set T in M, for every maximum-length IDOS, there is a transition from the start state of the maximum-length IDOS to state vi∗ labeled with the corresponding label of the maximum-length IDOS. When creating a new transition set U in M, for every UIO sequence of the end state of every maximum-length IDOS, there is a transition from vi∗ to the end state of every UIO sequence labeled with the corresponding UIO sequence.Table 4
UIO sequence ofM3.
No. States UIO(s) Ex1 s1 b/0 ( a / 1 ) ( c / 0 ) ( a / 1 ) ( a / 1 )  E x 2 s 2 ( a / 1 ) ( b / 1 ) c / 0  E x 3 s3 b / 1  E x 4 s4 a / 0 c / 1Figure 6
FSMM3.Figure 7
Augmentation ofM3.Theorem 5.
Given an FSMM, suppose that Q is a set of maximum-length IDOSs and β is a sequence over Q generated from Algorithm 1, then β is a reduced test sequence of M.Proof.
The soundness ofβ is first proved; i.e., β is a test sequence of M. Then the effectiveness of β is assessed in terms of test generation and test execution cost, respectively. From a general standpoint, the notion of cost in the context of testing is complex and can be related to many factors. In our context, the effort required for generating test sequences is measured in terms of test sequence computational complexity. Test sequence execution cost is measured by the length of test sequences. Although these are clearly approximation methods, for practical reasons such methods have been commonly used in a number of testing studies [14–16].(  1) Soundness Analysis(i) Check whether every transition defined inM is verified in the implementationAll the maximum-length IDOSs inQ are included in β since β is a sequence over Q. Algorithm 1 indicates that every maximum-length IDOS in β is followed by a UIO sequence that verifies the last transition of the sequence. According to Definition 2, i.e., for any maximum-length IDOS (s1,s2,i1/o1)(s2,s3,i2/o2)…(sj,sj+1,ij/oj), if (sj, sj+1, ij/oj) is verified then every transition (sk, sk+1, ik/ok) (1⩽k⩽j-1) is verified, it is inferred that transitions of all the maximum-length IDOSs in Q are verified in β. According to Definition 4, i.e., every transition in M is included in one and only one IDOS of Q, it is concluded that every transition defined in M is verified in the implementation by β.(ii) Check whether every state inM is defined in the implementationM is supposed to be strongly connected such that for any state s of M there is at least one transition ending at s. It is proved that every transition defined in M is verified in β by identifying the end state of the transition; i.e., every state of M is checked in the implementation by β.(  2) Effectiveness Analysis(i) Analysis of Computational Complexity.The test sequence β has the same computational complexity as those of Aho et al. and Hierons since all the three test sequence generation methods are based on the max flow/min cost problem and the networks used in every method are of the same order.(ii) Analysis of Length Reduction. As mentioned above, transitions in a test sequence are of three kinds and the cost of a test sequence comes from the UIO sequences which have been appended for the purpose of transition verification and the transitions which have been appended for the purpose of concatenation of test subsequences to generate a minimum-length rural postman tour.For symmetric FSMs with only invertible transitions,β is in the form of (s1,s2,i1/o1)(s2,s3,i2/o2)…(sj,s1,ij/oj)·γ where (s1, s2, i1/o1)(s2, s3, i2/o2)…(sj, s1, ij/oj) is an Euler tour staring from and ending at s1 and γ is a minimum-length UIO sequence of s1; i.e., the cost of β only comes from one appended minimum-length UIO sequence of s1.For asymmetric FSMs with only invertible transitions, all the transitions are divided into a least number of maximum-length IDOSs; i.e., all the transitions are verified by a least number of appended UIO sequences such that the cost ofβ from the appended UIO sequences is minimal. For any maximum-length IDOS (s1, s2, i1/o1)(s2, s3, i2/o2)…(sj, sj+1, ij/oj), there is a test subsequence (s1, s2, i1/o1)(s2, s3, i2/o2)…(sj, sj+1, ij/oj)·γ where γ is a UIO sequence of sj+1. β is obtained from a minimum-length rural postman tour covering all the test subsequences. The minimum-length rural postman tour is generated by the rural symmetric augmentation and thus the cost of β for concatenation comes from the replicated transitions during the rural symmetric augmentation. Benefiting from multiple UIO sequences, a minimum number of transition replications is reached by a sensible choice of UIO sequences during the rural symmetric augmentation; i.e., the cost of β from the transitions for concatenation is minimal.For FSMs with noninvertible transitions, transitions excluding noninvertible ones are divided into a least number of IDOSs. According to Theorem3, the acquired IDOSs concatenate with noninvertible transitions as much as possible such that a set of maximum-length IDOSs with a least number of maximum-length IDOSs is obtained; i.e., all the transitions of an FSM with noninvertible transitions are verified by a least number of appended UIO sequences such that the cost of β from the appended UIO sequences is minimal. Similarly, a minimum number of transition replications during the rural symmetric augmentation is reached by a sensible choice of UIO sequences; i.e., the cost of β from the transitions for concatenation is minimal.In short, for all types of FSMs, the execution cost is reduced effectively without increasing the generation cost such thatβ is a reduced test sequence of M.


## 3.2.1. Symmetric FSMs with Only Invertible Transitions

Step 1 (maximum-length IDOSs generation).
There is an Euler tour in a directed graph if and only if the directed graph is strongly connected and symmetric. Under the assumption that all the FSMs are strongly connected, there must be Euler tours for symmetric FSMs with only invertible transitions. An Euler tour starting from and ending at the initial state is definitely an IDOS since there are only invertible transitions; furthermore, it is a maximum-length IDOS from the initial state since there is no other one containing more transitions. In other words, an Euler tour of a symmetric FSM with only invertible transitions is the only sequence in the set of maximum-length IDOSs.
Note that an Euler tour starting from and ending at the initial state may not be unique; i.e., there may be nonunique sets of maximum-length IDOSs. Nonetheless, all the sets of maximum-length IDOSs hold the following properties.
(i) There is only one maximum-length IDOS covering all the transitions of the FSM in every set of maximum-length IDOSs.
(ii) The start state of the maximum-length IDOS is the initial state of the FSM in every set of maximum-length IDOSs.
(iii) The end state of the maximum-length IDOS is the initial state of the FSM in every set of maximum-length IDOSs.Step 2 (test sequence generation).
For symmetric FSMs with only invertible transitions, test sequences are denoted by(s1,s2,i1/o1)(s2,s3,i2/o2)…(sj,s1,ij/oj)·β where (s1,s2,i1/o1)(s2,s3,i2/o2)…(sj,s1,ij/oj) is an Euler tour staring from and ending at s1 and β is a minimum-length UIO sequence of s1. It can be inferred that test sequences from different sets of maximum-length IDOSs are always of the same length when there is more than one set of maximum-length IDOSs. As a result, a randomly generated set of maximum-length IDOSs will do for test sequence generation of symmetric FSMs with only invertible transitions.M 1 in Figure 2 is a symmetric FSM with only invertible transitions and s1(a/0)s2(a/1)s2(b/1)s3(a/1)s1 is an Euler tour starting from and ending at s1. It is known from Step 1 that {s1(a/0)s2(a/1)s2(b/1)s3(a/1)s1} is a set of maximum-length IDOSs of M1. A test sequence s1(a/0)s2(a/1)s2(b/1)s3(a/1)s1(a/0)s2 is resulted from Step 2.


## 3.2.2. Asymmetric FSMs with Only Invertible Transitions

Step 1 (maximum-length IDOSs generation).
An FSM is asymmetric which refers to the fact that there are nodes whose out-degree does not equal in-degree. It is known that∑s∈S‍dout(s)=∑s∈S‍din(s)=E where dout(s) and din(s) denote the out-degree and in-degree of a node, respectively [13]. The notation E refers to the number of edges in a directed graph. It is concluded from ∑s∈S‍douts=∑s∈S‍dins that ∑s∈S-‍dout>in(s)=∑s′∈S+‍din>out(s′) where S- and S+ are the sets of nodes whose out-degree outnumbers in-degree and in-degree outnumbers out-degree, respectively. Correspondingly, dout>in(s) and din>out(s′) represent the amount of out-degree over in-degree for a node in S- and the amount of in-degree over out-degree for a node in S+, respectively. The relation ∑s∈S‍dout(s)=∑s∈S‍din(s)=|E| implies that if a path passes through as many edges as possible exactly once then the path consumes as many out-degree and in-degree as possible. Every path through a node takes up one incoming edge as well as one outgoing edge, so if the out-degree outnumbers in-degree at a node, its outgoing edges cannot be traversed completely by paths passing through the node; i.e., some of its outgoing edges must instead be traversed by paths starting from the node. Thus, it is advisable to start the paths from nodes whose out-degree outnumbers in-degree if all the edges should be traversed exactly once with as few paths as possible. Moreover, it can be proved by contradiction that the paths from nodes whose out-degree outnumbers in-degree must end at nodes whose in-degree outnumbers out-degree otherwise the paths will continue to extend.
According to the above analysis, maximum-length IDOSs generation for asymmetric FSMs with only invertible transitions is performed as follows: start from a nodes∈S- and go down along an outgoing edge until a node s′∈S+ is reached and all the outgoing edges of s′ have been traversed. Thus a maximum-length IDOS from s to s′ is obtained. Add the maximum-length IDOS to the set of maximum-length IDOSs and delete the corresponding edges in the directed graph. Repeat the above process until all the nodes of the directed graph are isolated which implies that the set of maximum-length IDOSs is obtained.
Similarly, there may be nonunique sets of maximum-length IDOSs for asymmetric FSMs with only invertible transitions and all the sets of maximum-length IDOSs hold the following properties:
(i) For any set of maximum-length IDOSs,S- is the set of start states for maximum-length IDOSs.
(ii) For any set of maximum-length IDOSs,S+ is the set of end states for maximum-length IDOSs.
(iii) For any nodes∈S-, the number of maximum-length IDOSs starting from s is dout>in(s) in every set of maximum-length IDOSs.
(iv) For any nodes′∈S+, the number of maximum-length IDOSs ending at s′ is din>out(s′) in every set of maximum-length IDOSs.
(v) The total number of maximum-length IDOSs is∑s∈S-‍dout>in(s) which equals ∑s′∈S+‍din>out(s′) in each set of maximum-length IDOSs.Step 2 (test sequence generation).
With the set of maximum-length IDOSs, the same method as that of Bo Yang et al. is used to construct test sequences and the detail of the method is described in Algorithm1. The core of the method is the rural symmetric augmentation over an FSM augmented by maximum-length IDOSs and the multiple UIO sequences for the end states of maximum-length IDOSs. The core of the symmetric augmentation is the states involved. According to the above properties, for any set of maximum-length IDOSs, there is no difference about the states involved in the symmetric augmentation such that a random set of maximum-length IDOSs will do for asymmetric FSMs with only invertible transitions when there is more than one set of maximum-length IDOSs.
M 2 in Figure 4 is an asymmetric FSM with only invertible transitions and its UIO sequences are shown in Table 3. The nonunique sets of maximum-length IDOSs for M2 are listed as follows:Table 3
UIO sequence ofM2.
No. States UIO(s) Ex1 s1 b/0 ( a / 1 ) ( c / 0 ) ( a / 1 ) ( a / 1 )  E x 2 s 2 ( a / 1 ) ( b / 1 ) c / 0  E x 3 s 3 b / 1  E x 4 s 4 a / 0 c / 1Algorithm 1:Improved method of test sequence reduction.
Require: FSM M with n states {s1,s2,…,sn} in which s1 is the initial state; Set of non-invertible transitions P=ϕ; Set of maximum-length IDOSs Q=ϕ; Set of end states for non-invertible transitions S′=ϕ; UIO sequences of M; A minimum-length UIO sequence γ of s1; Ensure: Reduced test sequence β of M; (1)ifM is an FSM with m non-invertible transitionsthen (2)fori=1 to mdo (3)P=P∪ti where ti denotes a non-invertible transition; (4)M=M∖ti; (5)S′=S′∪ei where ei denotes the end state of ti; (6)end for (7)foreach state whose out-degree > in-degree in Mdo (8)Q=Q∪α where α is a maximum-length IDOS of j transitions generated from the state; (9)M=M∖ti (1⩽i⩽j); (10)end for (11)foreach connected component with Euler toursdo (12)ifStates in S′ can be found in an Euler tour t with k transitionsthen (13)Choose a state in S′ as the initial state of t; (14)end if (15)Q=Q∪t; (16)M=M∖ti (1⩽i⩽k); (17)end for (18)Q=Q∪P; (19)Concatenate non-invertible transitions and maximum-length IDOSs as long as the former’s end state is the latter’s start state; (20)M=M∪V∗ where V∗ is a new state set; (21)M=M∪T where T is a new transition set; (22)M=M∪U where U is a new transition set; (23)Construct a minimum-length rural postman tour over Q in the augmented M and extract a test sequence starting from s1; (24)Remove the transition sequence follows the UIO sequence of the maximum-length IDOS which is verified last in the minimum-length tour; (25)else (26)ifM is a symmetric FSM with only invertible transitionsthen (27)Q=Q∪t where t is an Euler tour starting from and ending at s1; (28)β=t⋅γ; (29)else (30)execute lines (7) through (9); (31)Execute lines (20) through (24); (32)end if (33)end ifFigure 4
FSMM2.{ s 1 ( a / 1 ) s 2 ( c / 0 ) s 2 ( a / 1 ) s 3 ( b / 1 ) s 4 ( c / 1 ) s 1 ( b / 0 ) s 2, s4(a/0)s2},{ s 1 ( a / 1 ) s 2 ( c / 0 ) s 2 ( a / 1 ) s 3 ( b / 1 ) s 4 ( a / 0 ) s 2, s4(c/1)s1(b/0)s2},{ s 1 ( b / 0 ) s 2 ( c / 0 ) s 2 ( a / 1 ) s 3 ( b / 1 ) s 4 ( c / 1 ) s 1 ( a / 1 ) s 2, s4(a/0)s2},{ s 1 ( b / 0 ) s 2 ( c / 0 ) s 2 ( a / 1 ) s 3 ( b / 1 ) s 4 ( a / 0 ) s 2, s4(c/1)s1(a/1)s2}.Clearly, all the sets of maximum-length IDOSs satisfy the properties in this section. The augmentation ofM2 using a random set of maximum-length IDOSs {s1(a/1)s2(c/0)s2(a/1)s3(b/1)s4(c/1)s1(b/0)s2,s4(a/0)s2} is shown in Figure 5 and the associated test sequence of M2 is s1(a/1)s2(c/0)s2(a/1)s3(b/1)s4(c/1)s1(b/0)s2(a/1)s3(b/ 1)s4(a/0)s2(c/0)s2.Figure 5
Augmentation ofM2.


## 3.2.3. FSMs with Noninvertible Transitions

Step 1 (maximum-length IDOSs generation).
To address an FSM with noninvertible transitions in a similar way to the first two types of FSMs, noninvertible transitions are removed from the FSM and saved to a set. The remainder excluding noninvertible transitions is either an FSM or more than one connected component with only invertible transitions. And thus maximum-length IDOSs of the remainder excluding noninvertible transitions are generated in the same way as symmetric or asymmetric FSMs with only invertible transitions. Naturally, it comes to the same conclusion as the first two types of FSMs that a random set of maximum-length IDOSs will do when there are nonunique sets of maximum-length IDOSs. Next, a union of maximum-length IDOSs of the remainder excluding noninvertible transitions and all the noninvertible transitions is derived; moreover, whenever the start state of a maximum-length IDOS is the end state of a noninvertible transition, the maximum-length IDOS is concatenated with the noninvertible transition. If a maximum-length IDOS is an Euler tour then a node which is the end state of a noninvertible transition is preferred to be the start state of the tour. The set after all possible concatenations is a set of maximum-length IDOSs of the FSM with noninvertible transitions.
Given a union of maximum-length IDOSs of the remainder excluding noninvertible transitions as well as all the noninvertible transitions, there may be nonunique sets of maximum-length IDOSs for the FSM with noninvertible transitions because of different concatenation. The properties of nonunique sets of maximum-length IDOSs for FSMs with noninvertible transitions are described as follows:
(i) In any set of maximum-length IDOSs, for any states which is the start state of a maximum-length IDOS, if there are j maximum-length IDOSs starting from s then there must be j maximum-length IDOSs starting from s in every other set of maximum-length IDOSs.
(ii) In any set of maximum-length IDOSs, for any states which is the end state of a maximum-length IDOS, if there are k maximum-length IDOSs ending at s then there must be k maximum-length IDOSs ending at s in every other set of maximum-length IDOSs.Step 2 (test sequence generation).
For FSMs with noninvertible transitions, test sequence generation is in the same way as asymmetric FSMs with only invertible transitions, i.e., by means of rural symmetric augmentation over an FSM augmented by maximum-length IDOSs and the multiple UIO sequences for the end states of maximum-length IDOSs. The core of rural symmetric augmentation is still the states involved. It is known from the above properties that for any set of maximum-length IDOSs the states involved in the rural symmetric augmentation are the same such that a random concatenation will do.
ConsideringM3 in Figure 6 with UIO sequences in Table 4, the following nonunique union of maximum-length IDOSs of the remainder excluding noninvertible transitions and noninvertible transitions confirm that a random union will do.{s1(a/1)s2(c/0)s2(a/1)s3(b/1)s4(c/1)s1(b/0)s2,s4(a/ 0)s2,s1(d/0)s4,s3(d/0)s4},{s1(a/1)s2(c/0)s2(a/1)s3(b/1)s4(a/0)s2,s4(c/1)s1(b/ 0)s2,s1(d/0)s4,s3(d/0)s4},{s1(b/0)s2(c/0)s2(a/1)s3(b/1)s4(c/1)s1(a/1)s2,s4(a/ 0)s2,s1(d/0)s4,s3(d/0)s4},{s1(b/0)s2(c/0)s2(a/1)s3(b/1)s4(a/0)s2,s4(c/1)s1(a/ 1)s2,s1(d/0)s4,s3(d/0)s4}.
Take a random union of maximum-length IDOSs of the remainder excluding noninvertible transitions and noninvertible transitions{s1(a/1)s2(c/0)s2(a/1)s3(b/1)s4(c/1)s1(b/0)s2, s4(a/0)s2, s1(d/0)s4, s3(d/0)s4}; nonunique sets of maximum-length IDOSs from different concatenations {s1(a/1)s2(c/0)s2(a/1)s3(b/1)s4(c/1)s1(b/0)s2, s3(d/0)s4(a/0)s2, s1(d/0)s4} and {s1(a/1)s2(c/0)s2(a/1)s3(b/1)s4(c/1)s1(b/0)s2, s1(d/0)s4(a/0)s2, s3(d/0)s4} confirm that a random concatenation will do. The augmentation of M3 using a randomly concatenated set of maximum-length IDOSs {s1(a/1)s2(c/0)s2(a/1)s3(b/1)s4(c/1)s1(b/0)s2, s3(d/0)s4(a/0)s2, s1(d/0)s4} is shown in Figure 7 and the resulting test sequence is s1(d/0)s4(c/1)s1(a/1)s2(c/0)s2(a/1)s3(b/1)s4(c/1)s1(b/0)s2(c/0)s2(a/1)s3(d/0)s4(a/0)s2(c/0)s2.
Algorithm1 describes the detail of the improved method for all types of FSMs. Note that self-loops are always given priority to traverse in the process of maximum-length IDOSs generation. When creating the new state set V∗ in M, for the end state of every maximum-length IDOS, there is a state in V∗. When creating the new transition set T in M, for every maximum-length IDOS, there is a transition from the start state of the maximum-length IDOS to state vi∗ labeled with the corresponding label of the maximum-length IDOS. When creating a new transition set U in M, for every UIO sequence of the end state of every maximum-length IDOS, there is a transition from vi∗ to the end state of every UIO sequence labeled with the corresponding UIO sequence.Table 4
UIO sequence ofM3.
No. States UIO(s) Ex1 s1 b/0 ( a / 1 ) ( c / 0 ) ( a / 1 ) ( a / 1 )  E x 2 s 2 ( a / 1 ) ( b / 1 ) c / 0  E x 3 s3 b / 1  E x 4 s4 a / 0 c / 1Figure 6
FSMM3.Figure 7
Augmentation ofM3.Theorem 5.
Given an FSMM, suppose that Q is a set of maximum-length IDOSs and β is a sequence over Q generated from Algorithm 1, then β is a reduced test sequence of M.Proof.
The soundness ofβ is first proved; i.e., β is a test sequence of M. Then the effectiveness of β is assessed in terms of test generation and test execution cost, respectively. From a general standpoint, the notion of cost in the context of testing is complex and can be related to many factors. In our context, the effort required for generating test sequences is measured in terms of test sequence computational complexity. Test sequence execution cost is measured by the length of test sequences. Although these are clearly approximation methods, for practical reasons such methods have been commonly used in a number of testing studies [14–16].(  1) Soundness Analysis(i) Check whether every transition defined inM is verified in the implementationAll the maximum-length IDOSs inQ are included in β since β is a sequence over Q. Algorithm 1 indicates that every maximum-length IDOS in β is followed by a UIO sequence that verifies the last transition of the sequence. According to Definition 2, i.e., for any maximum-length IDOS (s1,s2,i1/o1)(s2,s3,i2/o2)…(sj,sj+1,ij/oj), if (sj, sj+1, ij/oj) is verified then every transition (sk, sk+1, ik/ok) (1⩽k⩽j-1) is verified, it is inferred that transitions of all the maximum-length IDOSs in Q are verified in β. According to Definition 4, i.e., every transition in M is included in one and only one IDOS of Q, it is concluded that every transition defined in M is verified in the implementation by β.(ii) Check whether every state inM is defined in the implementationM is supposed to be strongly connected such that for any state s of M there is at least one transition ending at s. It is proved that every transition defined in M is verified in β by identifying the end state of the transition; i.e., every state of M is checked in the implementation by β.(  2) Effectiveness Analysis(i) Analysis of Computational Complexity.The test sequence β has the same computational complexity as those of Aho et al. and Hierons since all the three test sequence generation methods are based on the max flow/min cost problem and the networks used in every method are of the same order.(ii) Analysis of Length Reduction. As mentioned above, transitions in a test sequence are of three kinds and the cost of a test sequence comes from the UIO sequences which have been appended for the purpose of transition verification and the transitions which have been appended for the purpose of concatenation of test subsequences to generate a minimum-length rural postman tour.For symmetric FSMs with only invertible transitions,β is in the form of (s1,s2,i1/o1)(s2,s3,i2/o2)…(sj,s1,ij/oj)·γ where (s1, s2, i1/o1)(s2, s3, i2/o2)…(sj, s1, ij/oj) is an Euler tour staring from and ending at s1 and γ is a minimum-length UIO sequence of s1; i.e., the cost of β only comes from one appended minimum-length UIO sequence of s1.For asymmetric FSMs with only invertible transitions, all the transitions are divided into a least number of maximum-length IDOSs; i.e., all the transitions are verified by a least number of appended UIO sequences such that the cost ofβ from the appended UIO sequences is minimal. For any maximum-length IDOS (s1, s2, i1/o1)(s2, s3, i2/o2)…(sj, sj+1, ij/oj), there is a test subsequence (s1, s2, i1/o1)(s2, s3, i2/o2)…(sj, sj+1, ij/oj)·γ where γ is a UIO sequence of sj+1. β is obtained from a minimum-length rural postman tour covering all the test subsequences. The minimum-length rural postman tour is generated by the rural symmetric augmentation and thus the cost of β for concatenation comes from the replicated transitions during the rural symmetric augmentation. Benefiting from multiple UIO sequences, a minimum number of transition replications is reached by a sensible choice of UIO sequences during the rural symmetric augmentation; i.e., the cost of β from the transitions for concatenation is minimal.For FSMs with noninvertible transitions, transitions excluding noninvertible ones are divided into a least number of IDOSs. According to Theorem3, the acquired IDOSs concatenate with noninvertible transitions as much as possible such that a set of maximum-length IDOSs with a least number of maximum-length IDOSs is obtained; i.e., all the transitions of an FSM with noninvertible transitions are verified by a least number of appended UIO sequences such that the cost of β from the appended UIO sequences is minimal. Similarly, a minimum number of transition replications during the rural symmetric augmentation is reached by a sensible choice of UIO sequences; i.e., the cost of β from the transitions for concatenation is minimal.In short, for all types of FSMs, the execution cost is reduced effectively without increasing the generation cost such thatβ is a reduced test sequence of M.


## 4. Case Study

We experiment with the aforementionedM1, M2, and M3 which are random generation of different types of FSMs. M4 and M5 are also randomly generated FSMs; moreover, they are example FSMs used by Bo Yang et al. and Hierons, respectively. While the experimental results shed some light on how the improved method behaves with randomly generated FSMs, they bring no insight on the test sequence reduction of FSMs that are produced by software designers. For this reason, experiments on FSMs modeling INRES protocol [17], GUI for password modification in a property management system [18], page function of Gmail system [19] and the connection and release process of MAC layer in Zigbee protocol are carried out, and the FSM modeling page function of Gmail system is adjusted to satisfy the strong connectivity and UIO availability assumptions.The FSMs used in the experiment are admittedly small. However, it is important to note that FSMs are mostly used to model the behavior of complex classes or class clusters, particularly complex control classes in protocols or reactive systems. They are rarely used to model entire systems which will result in large and unmanageable models for software engineers and testers. Completeness degree is a general factor to reveal the complexity of both large and small FSMs such that test sequence reduction of large FSMs can to some extent be learned through relatively small FSMs with the same distribution of completeness degree. Given an FSM withx inputs, y transitions and n states, completeness degree of M is denoted by y/(x×n); moreover, the higher the completeness degree is, the more complex the FSM is. In this section, completeness degrees of FSMs range from 0.24 to 1.The associated data of the experiment is illustrated in Table5, |Input|, |State| and |Transition| denote the number of inputs, states and transitions of every FSM. Completeness degree of every FSM is calculated and listed. TFOTS+MUIO, Tinv, and Tinv+MUIO are test sequences resulting from Bo Yang et al., Hierons, and the improved method, respectively. |TFOTS+MUIO|, |Tinv|, and |Tinv+MUIO| represent the length of the corresponding test sequences.Table 5
Experimental objects and associated data.
FSMs Information of FSMs Length of Test Sequences I n p u t S t a t e | T r a n s i t i o n | C o m p l e t e n e s s  D e g r e e | T F O T S + M U I O | | T i n v | | T i n v + M U I O | M1 2 3 4 0.67 8 5 5  M 2 3 4 7 0.58 10 12 10  M3 4 4 9 0.56 15 15 13  M4 3 5 11 0.73 17 17 16  M5 2 5 10 1 33 21 20  INRES 5 4 16 0.8 13 12 12  GUI 7 8 25 0.45 74 31 31  Gmail 9 7 15 0.24 43 27 27  Zigbee 7 4 7 0.25 15 14 14For symmetric FSMs with only invertible transitions,Tinv and Tinv+MUIO are both Euler tours starting from the initial state followed by a minimum-length UIO sequence of the initial state. Thus, |Tinv| and |Tinv+MUIO| are always the same for symmetric FSMs with only invertible transitions. When the Euler tour conforms to the definition of fully overlapping transition sequences (FOTSs) [11], |TFOTS+MUIO| is the same as |Tinv| and |Tinv+MUIO|; otherwise |TFOTS+MUIO| tends to be longer because of more appended UIO sequences as well as the possible extra transitions for concatenation.For asymmetric FSMs with only invertible transitions,|TFOTS+MUIO| and |Tinv+MUIO| are the same if the maximum-length IDOSs comply with the definition of FOTS. Otherwise, |TFOTS+MUIO| tends to be longer because of more appended UIO sequences as well as the possible extra transitions for concatenation. Tinv is an Euler tour from a rural symmetric augmentation of an asymmetric FSM with only invertible transitions followed by a minimum-length UIO sequence of the initial state. The number of appended transitions in the rural symmetric augmentation is a deciding factor of |Tinv|.For FSMs with noninvertible transitions,|TFOTS+MUIO| is longer than |Tinv+MUIO| since every noninvertible transition is verified individually by an appended UIO sequence. |Tinv| is the same as |Tinv+MUIO| at best otherwise |Tinv| tends to be longer than |Tinv+MUIO|.As shown in Table5, test sequences generated from different test methods conform to the above theoretical analysis. In this section,two-sample t-test is performed to compare test methods in terms of the length of the associated test sequences.Single sample K-S check in SPSS is used to verify the normality of the data studied sincet-test is a parametric test and requires data to be normally distributed. Normality results are reported whenever samples deviate significantly from the normal distribution and the result of single sampleK-S check in Table 6 shows that all the data in this experiment follow normal distribution. The paired samples statistics in Table 7 indicates that the average length of test sequences from the improved method is superior to those of the other two methods.Table 6
Single sample K-S check.
| T F O T S + M U I O | | T i n v | | T i n v + M U I O | N 9 9 9  Mean Value 25.333 17.111 16.444 Standard Deviation 21.535 8.054 8.263  K o l m o g o r o v - S m i r n o v   Z .952 .517 .564  A s y m p o t i c   S i g n i f i c a n c e   ( 2 - t a i l e d ) .325 .952 .908Table 7
Paired samples statistics.
Pair Mean N Standard Deviation Standard Error Mean | T F O T S + M U I O | 25.333 9 21.535 7.178 | T i n v + M U I O | 16.444 9 8.263 2.754  | T i n v | 17.111 9 8.054 2.685 | T i n v + M U I O | 16.444 9 8.263 2.754Vargha-Delaney effect size measure ( A ^ 12 ) is also calculated to get more credible conclusions. When comparing two methods, A^12 measures the probability that one method would perform better than the other method. A value of 0.5 would mean that the two methods have equal probability of performing better than the other. The Vargha-Delaney effect size measure (A^12) from comparing |Tinv+MUIO| to |TFOTS+MUIO| and |Tinv| is shown in Table 8. The results show that |Tinv+MUIO| is statistically 60.5% and 54.3% of the time significantly shorter than |TFOTS+MUIO| and |Tinv|, respectively.Table 8
Statistical results from(A^12).
| T i n v + M U I O |   v e r s u s (A^12) Ex1 |TFOTS+MUIO| 0.395  Ex2 |Tinv| 0.457


## 5. Related Work

There are many works on IoT testing. Xiaoping Che et al. presented a logic-based approach to test the conformance and performance of XMPP protocol which is gaining momentum in IoT through real execution traces and formally specified properties [20]. Dimitrios Serpanos et al. introduced testing for security for IoT systems and especially fuzz testing, which is a successful technique to identify vulnerabilities in systems and network protocols [21]. Martin Tappler et al. presented a model-based approach to test IoT communication via active automata learning [22]. Combining Model-Based Testing (MBT) and a service-oriented solution, Abbas Ahmad et al. presented Model-Based Testing As A Service (MBTAAS) for testing data and IoT platforms [23]. Hiun Kim et al. introduced IoT testing as a Service-IoT-TaaS which is composed of remote distributed interoperability testing, scalable automated conformance testing, and semantics validation testing components adequate for testing IoT devices [24]. John Esquiagola et al. used the current version of their IoT platform to perform performance testing [25]. Daniel Kuemper et al. described how concepts for semantically described web services can be transferred into the IoT domain [26]. Philipp Rosenkranz et al. propose a testing framework which supports continuous integration techniques and allows for the integration of project contributors to volunteer hardware and software resources to the test system [27]. A connective and semantic similarity clustering algorithm (CSSCA) and a hierarchical combinatorial test model based on FSM are proposed by Kai Cui et al. [28].Test sequence generation and reduction has long been an active research topic. Porto et al. used identification sets which are subsets of a characterizing set to identify states and obtained reduced test sequences [29]. Locating sequences are used to make sure that every element of a characterizing set is applied to the same state. Jourdan et al. generated shorter test sequences by means of reducing the number of locating sequences [30]. Baumgartner et al. proposed a mixed integer nonlinear programming (MINLP) model to formalize how the total cost of testing depends on the sequence and the parameters of the elementary test steps [31]. To provide an efficient formalization of the scheduling problem and avoid difficulties due to the evaluation of an objective function during the relaxation of the integer variables, the MINLP was formulated as a process network synthesis problem. Hierons et al. affirmed the importance of invertibility in test sequence reduction and considered three optimisation problems associated with invertible sequences [32]. Petrenko et al. addressed the problem of extending the checking experiment theory to cover a class of FSMs with symbolic extensions [33]. They also reported the results that further lift the theory of checking experiments for Mealy machines with symbolic inputs and symbolic outputs. Hierons et al. described an efficient parallel algorithm that uses many-core GPUs for automatically deriving UIOs from Finite State Machines [34]. The proposed algorithm uses the global scope of the GPU’s global memory through coalesced memory access and minimizes the transfer between CPU and GPU memory. Song et al. introduced a practical conformance testing tool that generates high-coverage test input packets using a conformance test suite and symbolic execution. This approach can be viewed as the combination of conformance testing and symbolic execution [35]. Bokil et al. presented an automated black box test suite generation technique for reactive systems [36]. The technique is based on dynamic mining of specifications in form of an FSM from initial runs. The set of test cases thus produced contain several redundant test cases, many of which are eliminated by a simple greedy test suite reduction algorithm to give the final test suite.


## 6. Conclusions

Taking Zigbee protocol as an example, this paper introduces how FSM-based conformance testing works in wireless protocol conformance testing of IoT. An improved method in which both overlapping by invertibility and multiple UIO sequences are considered is proposed to achieve test sequence reduction for wireless protocol conformance testing of IoT. Based on invertibility, transitions of all types of FSMs are verified with as few appended UIO sequences as possible. Multiple UIO sequences contribute to generate a shorter test sequence by means of reducing transitions for concatenation of test subsequences in the test sequence. Moreover, test sequences can be further reduced by removing the transition sequence which follows the UIO sequence of the maximum-length IDOS that is verified last in the tour. Theory and experiment indicate that the execution cost is reduced effectively by the improved method under the premise of not increasing the generation cost. The improved method is also applicable to traditional protocol conformance testing as well as reactive systems. Numerous experimental data and practical examples about wireless protocols of IoT will be gathered in the future work to analyze the effectiveness of the method.



---

*Source: 3723691-2018-11-01.xml*