# A Combining Method for Wireless Protocol Conformance Testing: A Empirical Case

Authors: Lin Wei-Wei; Zeng Hong-Wei; Jung Yoon Kim
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

Ensuring the consistency of protocol implementation and protocol specification is the basic premise of wireless communication. With the application of wireless communication in more and more fields, the wireless communication environment becomes more and more complex, and the fault coverage of wireless protocol conformance testing is also facing more and more challenges. To solve this problem, this paper uses Finite State Machine (FSM) as a formal description tool for wireless protocols and presents a combining test method based on two test methods with complementary characteristics in the test technologies based on structural coverage and state identification. Then, the paper evaluates the effectiveness of the method based on 14 empirical cases. The experimental results show that the fault coverage of each empirical case can be effectively improved to 100% when the average test cost is only increased by 17.99%.


---

## Body

## 1. Introduction

Wireless protocol is the rule that must be obeyed by the communication entities and processes in wireless communication [1]. It is also the basic guarantee to realize the stability of wireless communication and the competitive advantage in the low-power wireless communication market [2, 3]. Conformance testing, performance testing, interoperability testing, and robustness testing are all essential to verify the correctness of wireless protocol implementation [4]. Conformance testing is the basis of the other three kinds of testing, which is used to ensure the consistency of protocol implementation and protocol specification [1, 5, 6]. Finite State Machine (FSM) [7–10] is an effective formal modeling tool [11, 12] in wireless protocol conformance testing since the operations implemented on the entities in wireless protocols (such as button click or window input in GUI and message request in Web service) can be mapped to the inputs in FSMs, and the responses to the operations according to the wireless protocols (such as message response in GUI or web service) can be mapped to the outputs in FSMs [13–16]. To facilitate the description, we abstract these events into alphabetic or numeric symbols in the examples and experiments of this paper. ZigBee is an emerging short-range, low-rate, and low-power wireless network technology. Taking the connection and release process of MAC layer in ZigBee protocol as an example [17], the interaction process between communication entities is shown in Figure 1(a) and the corresponding FSM is shown in Figure 1(b). The relationships between specific events in ZigBee protocol and abstract symbol definitions in FSM are described in Tables 1, 2, and 3, respectively. In this way, the problem of judging whether the implementation of ZigBee protocol is consistent with the ZigBee protocol specification can be transformed into the problem of judging whether the implementation of ZigBee protocol is consistent with the specification FSM of ZigBee protocol. Specifically, a test set is generated based on the specification FSM and the test set is applied to the wireless protocol implementation. When the actual output is consistent with the expected output, the implementation is consistent with the protocol. Otherwise, it means that there is a fault in the implementation.Figure 1
Connection and release process in ZigBee.
(a)(b)Table 1
Abstract definition of state.
State signalStates1Unconnected state (initial state)s2Received connection request data frame and waiting for data request command frames3Agree to the connection request, and wait for the ACKs4Connection statusTable 2
Abstract definition of input event.
Input signalInput eventi1Connection request framei2Data request framei3Normal network status and network resources are not exhaustedi4Malicious connection request frames, exhausting network resourcesi5ACKi6Release request framei7No input data, waiting timeoutTable 3
Abstract definition of output event.
Output signalOutput evento1ACKo2Response data frame of allowing nodes to join the networko3Response data frame of refusing nodes to join the networkBoth the transition-pair coverage (TPC) method [18–20] based on structure coverage and the unique input output (UIO) method [7, 13] based on state identification can be used in wireless protocol conformance testing. However, neither TPC method nor UIO method can achieve 100% fault coverage. To meet the high reliability requirements of wireless protocol conformance testing, this paper presents a combined method based on the complementary characteristics of the TPC method and UIO method. And the combined method is studied by 14 established empirical cases including ZigBee protocol and the WM2RP protocol both of which are widely used in wireless communication. The contribution of this paper is mainly as follows:(1)
The fault coverage of wireless protocol conformance testing is effectively improved(2)
Since the experimental objects are all FSM empirical cases designed and generated by testers according to professional experience and domain knowledge, the experimental data and results have more practical significance, which can also promote the application of FSM conformance testing in industryThe remainder of the paper is organized as follows. Section2 introduces the concepts and terms about FSM. Section 3 presents a combined method for wireless protocol conformance testing. Section 4 describes the case study and evaluates the experimental results. Section 5 overviews the related work. Finally, Section 6 summarizes the full text and prospects of the future work.


## 2. Preliminaries

An FSM is formally defined as a 6-tupleM=I,O,S,s0,δ,λ [21, 22] 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 functionAccording to this definition, when an input symboli is delivered to the current state s, M moves to state s′=δs,i with an output produced by λs,i. A transition t is defined by a tuple s,s′,i/o where s is the start state of t, i is an input of s, o=λs,i is the associated output, and s′=δs,i is the end state of t.An FSM M is initially connected if for any states there is at least one input sequence from s0 to s, i.e., ∀s∈S,∃α∈I∗·δs0,α=s (where I∗ is the set of finite sequences of input symbols).Ifs≠s′,α∈I∗·λs,α≠λs′,α, then s and s′ are a pair of distinguishable states, and α is called a separating sequence of s and s′. If all the states in FSM M are pairwise distinguishable, i.e., ∀s,s′∈S,s≠s′,∃α∈I∗·λs,α≠λs′,α, then M is said to be minimal or reduced.An FSM M is deterministic if at any states and for any input i, there is at most one transition leading to the next state. Otherwise, M is nondeterministic.An FSM is not initially connected means there are some states that cannot be reached from the initial state. In other words, the states that cannot be reached from the initial state are meaningless to the FSM. Therefore, an FSM that is not initially connected can be converted to an initially connected FSM by deleting the states that cannot be reached from the initial state. An FSM with equivalent states can be transformed into a reduced FSM by joining equivalent states. A nondeterministic FSM can be converted to a deterministic FSM by combining states, i.e., raising the level of abstraction. Since all the above definitions can be satisfied, only initially connected, reduced and deterministic FSMs are considered in this paper. In Figure2, M1 is an initially connected, reduced, and deterministic FSM where S=s1,s2,s3,I=x,y,O=0,1 and s1 highlighted in bold defaults to the initial state.Figure 2
FSMM1.The connection of input sequences in FSM is represented by the juxtaposition of input sequences; that is, ifα1,α2∈I∗, then α1α2 represents the connection of α1 and α2. If β=α1α2, then α1 is the prefix of β, expressed as α1≤β. If α1≠ε (ε is an empty string), then α1 is the true prefix of β, expressed as α1<β. Given a set of input sequences T, prefT represents the set of all prefixes of all sequences in T; that is, prefT=α∃β∈Tandα≤β; if T=prefT then, T is a set of prefix closures.In this work, we assume that FSM M has a reset operationr which can bring M to its initial state from any state without any output. A string x1x2,xk∈I∗ is said to be a defined input sequence at s∈S if there exists s1,⋯,sk,sk+1, where s1=s, such that si,xi∈S×I and δsi,xi=si+1 for all i=1,⋯,k. We use ΩMs to denote the set of all defined input sequences at state s and ΩM as an abbreviation for ΩMs0, i.e., the input sequences defined at the initial state of M, and hence for M itself. A test case of M is an input sequence α∈ΩM starting with r. A test suite of M is a finite set of test cases, and there are not two test cases α and β such that α<β. The number of symbols of a sequence α is represented by ∣α∣. For instance, given a test case ryyy for M1, the length of ryyy is 4, since it contains four symbols, that is, ∣ryyy∣=4. This notation is extended to a test suite T; i.e., ∣T∣ means the sum of all the length of sequences in T. For instance, given a test suite T=ryx,ryyy,ryyx,rx for M1, the length of T is 13, i.e., ∣T∣=∣ryx,ryyy,ryyx,rx∣=13.An initialization fault occurs when FSM starts from an incorrect initial statesi(si≠s0). An output fault occurs when the correct output of a transition (s, s′, i/o) is changed, and a transition (s, s′, i/o′) in which the output is different from the expected one is generated. An end state fault occurs when the end state of a transition (s, s′, i/o) is changed, and a transition (s, s″, i/o) in which the end state is different from the expected one is generated. Figure 3 demonstrates the three types of faults based on M1. There is an initialization fault starting from an incorrect initial state s2 in Figure 3(a). There is an output fault in Figure 3(b). The transition (s3, s1, y/0) is changed to the transition (s3, s1, y/1) with a wrong output. There is an end state fault in Figure 3(c). The transition (s1, s1, x/0) is changed to the transition (s1, s2, x/0) with a wrong end state.Figure 3
Three types of faults inM1.
(a)(b)(c)


## 3. TPC-UIO Test Method

### 3.1. Motivation Example

Figures4 and 5 are two examples to present the complementarity between the TPC method and UIO method.Figure 4
Example 1 of relationship between the TPC method and UIO method.
(a)(b)Figure 5
Example 2 of relationship between the TPC method and UIO method.
(a)(b)The FSM in Figure4(a) is a wireless protocol specification, and the FSM in Figure 4(b) is an implementation, where the dotted line represents a transition with an end state fault. {rcbbdb, rcbbecda, rcbbecbbac} is the test set of TPC method generated based on Figure 4(a), and {rcbba, rcbbdb, rcbbecbbacb, rcbbecda} is the test set of UIO method generated based on Figure 4(a).The FSM in Figure5(a) is a wireless protocol specification, and the FSM in Figure 5(b) is an implementation, where the dotted line also represents a transition with an end state fault. {rba, rbb, raaa, raab, rabaa, rabab, rabba, rabbb} is the test set of the TPC method generated based on Figure 5(a), and {raaa, rbba, rabba, rabaaa} is the test set of the UIO method generated based on Figure 5(a).Test results indicate the following:(1)
The test set of the TPC method can test the fault in Figure5(b) but cannot test the fault in Figure 4(b)(2)
The test set of the UIO method can test the fault in Figure4(b) but cannot test the fault in Figure 5(b)It can be concluded from the above examples that there are obvious differences in the performance of TPC method and UIO method in different examples. Specifically, the two methods show strong complementarity. When the number of transitions outgoing from the correct end state and the wrong end state is equal, furthermore, the input/output of the transitions outgoing from the correct end state and the wrong end state are all the same, fault coverage ability of UIO method is superior to TPC method. When there are differences about the number of transitions outgoing from the correct end state and the wrong end state or there are differences about the input/output of transitions outgoing from the correct end state and the wrong end state and the UIO sequence of the correct end state is also available in the wrong end state, fault coverage ability of the TPC method is superior to that of the UIO method.


### 3.2. Test Generation of TPC-UIO Method

Based on the above analysis, we introduce a combined TPC-UIO test method to realize the complementarity of the TPC method and UIO method.


#### 3.2.1. State Covering Set Generation

Definition 1 (State covering set).
Given an FSMM and an input sequence set Q=α0,α1,⋯,αn−1, if for any state si,∃αi∈Q0≤i≤n−1 satisfies δs0,αi=si, where s0 is the initial state, then Q is a state covering set of M.There must be a state covering set in initially connected FSM, and an empty sequenceε is included to reach the initial state s0. In addition, only state covering set of prefix closure is considered in this paper. As described in Algorithm 1, given an FSM with n states {s1,s2,⋯,sn} in which s1 is the initial state and a transition tree T with only a root node s1, state covering set SCM is first initialized to ϕ. Then, for each transition starting with s1, a branch annotated with the input/output of the transition is added in T. Next, for each transition starting with a leaf node appears for the first time in T, a branch annotated with the input/output of the transition is added in T iteratively until there is no leaf node appearing for the first time that can be found. So far, the complete transition tree is constructed. Finally, for each state si1≤i≤n, an input/output sequence βi from s1 to si that appears for the first time in T is obtained and βi is thrown to SCM.Algorithm 1: State covering set generation
Input: FSM M with n states {s1, s2,…sn} and s1 is the initial state, transition tree T and Root(T)=s1Output: State covering set SC(M)1: Initialize SC(M)=ϕ2:for each transition starting with s13: Add a branch in T and mark the branch with the input/output of the transition4:end for5:do6:for each leaf node appears for the first time in T7: Add a branch in T for each transition starting with the leaf node and mark the branch with the input/output of the transition8:end for9:until leaf node appears for the first time cannot be found in T10:for (i=1; i≤n; i++)11: Get an input/output sequenceβi from s1 to si that appears for the first time in T12: SC(M)= SC(M)∪βi13:end forAccording to Algorithm1, the transition tree of M1 is shown in Figure 6, and ε,y/1,y/1y/1 is a state covering set obtained from the transition tree.Figure 6
Transition tree ofM1.


#### 3.2.2. TPC Test Set Generation

Definition 2 (adjacent transition).
If the end state of a transitiont1=(s1, s, i1/o1) is the start state of a transition t2=(s, s2, i2/o2), t1 and t2 are a pair of adjacent transition.
The test set of TPC method covers each pair of adjacent transitions in FSM at least once. As shown in Algorithm2, given an FSM with n states {s1,s2,⋯,sn} in which s1 is the initial state and a state covering set SCM={α1,α2,⋯,αn}, TPC test set TPCM is first initialized to ϕ. Then, for each state si1≤i≤n, each transition sequence β of length 2 starting from si is obtained and αiβ is thrown to TPCM.Algorithm 2: TPC test set generation
Input: FSM M with n states {s1, s2,…sn} and s1 is the initial state, state covering set SC(M)={α1, α2,…αn}Output: TPC test set TPC(M)1: Initialize TPC(M)=ϕ2:for (i=1; i≤n; i++)3:for each transition sequence β of length 2 starting from si4: TPC(M)= TPC(M) ∪αiβ5:end for6:end forConsiderM1 in Figure 2, {rxx, rxy, ryy, ryx, ryxx, ryxy, ryyx, ryyy, ryyxx, ry, ryyxy, ryyyx, ryyyy} is the test set of M1 under the TPC method.


#### 3.2.3. UIO Generation

Definition 3 (UIO sequence).
An input/output sequenceβ is a UIO sequence of state si if and only if for any state sj∈Ssj≠si,λsi,βin≠λsj,βin, where βin is the input part of β.Definition 4 (uncertainty of the start states).
Given an FSMM and an input sequence α, a partition πα of the state set S can be obtained according to the output generated by each state for α. For any state si and sj, they will be in the same partition block if and only if they cannot be distinguished by α, i.e., λsi,α=λsj,α, and this partition is called the uncertainty of the start states.Definition 5 (uncertainty of the current states).
The current states ofM after delivering α can be expressed as δB,α∣B∈πα, and this partition is called the uncertainty of the current states.In this way, the scope of the state before and after the inputα can be learned according to the output corresponding to α. The idea of state partition can be applied to the construction of successor tree.Definition 6 (successor tree).
The successor tree of an FSM is a tree showing the behavior of the FSM at any state and upon any input sequence.For each possible input sequence, there is a path starting from the root node in the successor tree and each node in the successor tree is annotated with the uncertainty of start states as well as the uncertainty of current states.The successor tree ofM1 is shown in Figure 7. When x is delivered to the set of states {s1, s2, s3}, according to the different output, the partition blocks of start state uncertainty are 0{s1,s3} and 1{s2}, respectively, where 0 and 1 represent the output generated by the state in the partition block. The corresponding partition blocks of current state uncertainty are {s1,s3} and {s2}, respectively. When x is again delivered to the current state uncertainty {s1,s3} and {s2} according to the different output, the partition blocks of start state uncertainty are 00{s1,s3} and 11{s2}, respectively. The corresponding partition blocks of current state uncertainty are {s1,s3} and {s2}. Since the set {s1,s3} can never be further divided by x, this branch can terminate the decomposition about input x. Next, y is delivered to the partition blocks of the current state uncertainty {s1,s3} and{s2}; according to the different output, the partition blocks of start state uncertainty are 01{s1}, 00{s3}, and 11{s2}, respectively. The corresponding current state uncertainty partition blocks are {s2}, {s1}, and {s3}, respectively. Since there is only one element in each partition block, the division of this branch ends here. In the same way, we can construct other branches in the successor tree until a successor tree meeting the requirement is generated.Figure 7
Successor tree ofM1.In this paper, UIO sequence is obtained by successor tree. Given an FSM and its successor tree, if there is only one statesi in a partition block of the start state uncertainty, we will get a UIO sequence of si. Here, we only consider the shortest UIO sequence; that is, the UIO sequence we first obtained in the top-down search of the successor tree. As shown in Figure 7, the UIO sequence of s1 is x/0y/1, y/1x/1, or y/1y/1, the UIO sequence of s2 is x/1, and the UIO sequence of s3 is y/0.


#### 3.2.4. Test Set Generation of TPC-UIO Method

Definition 7 (TPC-UIO method).
The test set of the TPC-UIO method should satisfy two conditions. (1) Cover each pair of adjacent transition in an FSM at least once. (2) Identify the end state of each pair of adjacent transition using the shortest UIO sequence.As shown in Algorithm3, given TPC test set TPCM of an FSM and UIO sequence of each state, for each test case in TPCM, identify the end state of the test case by the corresponding UIO sequence. Then, the test cases which are true prefixes of others are deleted and TPC-UIO test set TPC-UIOM is constructed.Algorithm 3: Test set generation of TPC-UIO method
Input: TPC test set TPC(M), UIO sequence of each stateOutput: TPC-UIO test set TPC-UIO(M)1:for each test case in TPC(M)2: Identify the end state of the test case by the corresponding UIO sequence3:end for4: delete the test cases which are true prefixes of othersTakingM1 for example, {rxxxy, rxyx, ryxxx, ryxyy, ryyyxy, ryyxyxy, ryyyxxy, ryyyyx} is the final test set of the TPC-UIO method.


## 3.1. Motivation Example

Figures4 and 5 are two examples to present the complementarity between the TPC method and UIO method.Figure 4
Example 1 of relationship between the TPC method and UIO method.
(a)(b)Figure 5
Example 2 of relationship between the TPC method and UIO method.
(a)(b)The FSM in Figure4(a) is a wireless protocol specification, and the FSM in Figure 4(b) is an implementation, where the dotted line represents a transition with an end state fault. {rcbbdb, rcbbecda, rcbbecbbac} is the test set of TPC method generated based on Figure 4(a), and {rcbba, rcbbdb, rcbbecbbacb, rcbbecda} is the test set of UIO method generated based on Figure 4(a).The FSM in Figure5(a) is a wireless protocol specification, and the FSM in Figure 5(b) is an implementation, where the dotted line also represents a transition with an end state fault. {rba, rbb, raaa, raab, rabaa, rabab, rabba, rabbb} is the test set of the TPC method generated based on Figure 5(a), and {raaa, rbba, rabba, rabaaa} is the test set of the UIO method generated based on Figure 5(a).Test results indicate the following:(1)
The test set of the TPC method can test the fault in Figure5(b) but cannot test the fault in Figure 4(b)(2)
The test set of the UIO method can test the fault in Figure4(b) but cannot test the fault in Figure 5(b)It can be concluded from the above examples that there are obvious differences in the performance of TPC method and UIO method in different examples. Specifically, the two methods show strong complementarity. When the number of transitions outgoing from the correct end state and the wrong end state is equal, furthermore, the input/output of the transitions outgoing from the correct end state and the wrong end state are all the same, fault coverage ability of UIO method is superior to TPC method. When there are differences about the number of transitions outgoing from the correct end state and the wrong end state or there are differences about the input/output of transitions outgoing from the correct end state and the wrong end state and the UIO sequence of the correct end state is also available in the wrong end state, fault coverage ability of the TPC method is superior to that of the UIO method.


## 3.2. Test Generation of TPC-UIO Method

Based on the above analysis, we introduce a combined TPC-UIO test method to realize the complementarity of the TPC method and UIO method.


### 3.2.1. State Covering Set Generation

Definition 1 (State covering set).
Given an FSMM and an input sequence set Q=α0,α1,⋯,αn−1, if for any state si,∃αi∈Q0≤i≤n−1 satisfies δs0,αi=si, where s0 is the initial state, then Q is a state covering set of M.There must be a state covering set in initially connected FSM, and an empty sequenceε is included to reach the initial state s0. In addition, only state covering set of prefix closure is considered in this paper. As described in Algorithm 1, given an FSM with n states {s1,s2,⋯,sn} in which s1 is the initial state and a transition tree T with only a root node s1, state covering set SCM is first initialized to ϕ. Then, for each transition starting with s1, a branch annotated with the input/output of the transition is added in T. Next, for each transition starting with a leaf node appears for the first time in T, a branch annotated with the input/output of the transition is added in T iteratively until there is no leaf node appearing for the first time that can be found. So far, the complete transition tree is constructed. Finally, for each state si1≤i≤n, an input/output sequence βi from s1 to si that appears for the first time in T is obtained and βi is thrown to SCM.Algorithm 1: State covering set generation
Input: FSM M with n states {s1, s2,…sn} and s1 is the initial state, transition tree T and Root(T)=s1Output: State covering set SC(M)1: Initialize SC(M)=ϕ2:for each transition starting with s13: Add a branch in T and mark the branch with the input/output of the transition4:end for5:do6:for each leaf node appears for the first time in T7: Add a branch in T for each transition starting with the leaf node and mark the branch with the input/output of the transition8:end for9:until leaf node appears for the first time cannot be found in T10:for (i=1; i≤n; i++)11: Get an input/output sequenceβi from s1 to si that appears for the first time in T12: SC(M)= SC(M)∪βi13:end forAccording to Algorithm1, the transition tree of M1 is shown in Figure 6, and ε,y/1,y/1y/1 is a state covering set obtained from the transition tree.Figure 6
Transition tree ofM1.


### 3.2.2. TPC Test Set Generation

Definition 2 (adjacent transition).
If the end state of a transitiont1=(s1, s, i1/o1) is the start state of a transition t2=(s, s2, i2/o2), t1 and t2 are a pair of adjacent transition.
The test set of TPC method covers each pair of adjacent transitions in FSM at least once. As shown in Algorithm2, given an FSM with n states {s1,s2,⋯,sn} in which s1 is the initial state and a state covering set SCM={α1,α2,⋯,αn}, TPC test set TPCM is first initialized to ϕ. Then, for each state si1≤i≤n, each transition sequence β of length 2 starting from si is obtained and αiβ is thrown to TPCM.Algorithm 2: TPC test set generation
Input: FSM M with n states {s1, s2,…sn} and s1 is the initial state, state covering set SC(M)={α1, α2,…αn}Output: TPC test set TPC(M)1: Initialize TPC(M)=ϕ2:for (i=1; i≤n; i++)3:for each transition sequence β of length 2 starting from si4: TPC(M)= TPC(M) ∪αiβ5:end for6:end forConsiderM1 in Figure 2, {rxx, rxy, ryy, ryx, ryxx, ryxy, ryyx, ryyy, ryyxx, ry, ryyxy, ryyyx, ryyyy} is the test set of M1 under the TPC method.


### 3.2.3. UIO Generation

Definition 3 (UIO sequence).
An input/output sequenceβ is a UIO sequence of state si if and only if for any state sj∈Ssj≠si,λsi,βin≠λsj,βin, where βin is the input part of β.Definition 4 (uncertainty of the start states).
Given an FSMM and an input sequence α, a partition πα of the state set S can be obtained according to the output generated by each state for α. For any state si and sj, they will be in the same partition block if and only if they cannot be distinguished by α, i.e., λsi,α=λsj,α, and this partition is called the uncertainty of the start states.Definition 5 (uncertainty of the current states).
The current states ofM after delivering α can be expressed as δB,α∣B∈πα, and this partition is called the uncertainty of the current states.In this way, the scope of the state before and after the inputα can be learned according to the output corresponding to α. The idea of state partition can be applied to the construction of successor tree.Definition 6 (successor tree).
The successor tree of an FSM is a tree showing the behavior of the FSM at any state and upon any input sequence.For each possible input sequence, there is a path starting from the root node in the successor tree and each node in the successor tree is annotated with the uncertainty of start states as well as the uncertainty of current states.The successor tree ofM1 is shown in Figure 7. When x is delivered to the set of states {s1, s2, s3}, according to the different output, the partition blocks of start state uncertainty are 0{s1,s3} and 1{s2}, respectively, where 0 and 1 represent the output generated by the state in the partition block. The corresponding partition blocks of current state uncertainty are {s1,s3} and {s2}, respectively. When x is again delivered to the current state uncertainty {s1,s3} and {s2} according to the different output, the partition blocks of start state uncertainty are 00{s1,s3} and 11{s2}, respectively. The corresponding partition blocks of current state uncertainty are {s1,s3} and {s2}. Since the set {s1,s3} can never be further divided by x, this branch can terminate the decomposition about input x. Next, y is delivered to the partition blocks of the current state uncertainty {s1,s3} and{s2}; according to the different output, the partition blocks of start state uncertainty are 01{s1}, 00{s3}, and 11{s2}, respectively. The corresponding current state uncertainty partition blocks are {s2}, {s1}, and {s3}, respectively. Since there is only one element in each partition block, the division of this branch ends here. In the same way, we can construct other branches in the successor tree until a successor tree meeting the requirement is generated.Figure 7
Successor tree ofM1.In this paper, UIO sequence is obtained by successor tree. Given an FSM and its successor tree, if there is only one statesi in a partition block of the start state uncertainty, we will get a UIO sequence of si. Here, we only consider the shortest UIO sequence; that is, the UIO sequence we first obtained in the top-down search of the successor tree. As shown in Figure 7, the UIO sequence of s1 is x/0y/1, y/1x/1, or y/1y/1, the UIO sequence of s2 is x/1, and the UIO sequence of s3 is y/0.


### 3.2.4. Test Set Generation of TPC-UIO Method

Definition 7 (TPC-UIO method).
The test set of the TPC-UIO method should satisfy two conditions. (1) Cover each pair of adjacent transition in an FSM at least once. (2) Identify the end state of each pair of adjacent transition using the shortest UIO sequence.As shown in Algorithm3, given TPC test set TPCM of an FSM and UIO sequence of each state, for each test case in TPCM, identify the end state of the test case by the corresponding UIO sequence. Then, the test cases which are true prefixes of others are deleted and TPC-UIO test set TPC-UIOM is constructed.Algorithm 3: Test set generation of TPC-UIO method
Input: TPC test set TPC(M), UIO sequence of each stateOutput: TPC-UIO test set TPC-UIO(M)1:for each test case in TPC(M)2: Identify the end state of the test case by the corresponding UIO sequence3:end for4: delete the test cases which are true prefixes of othersTakingM1 for example, {rxxxy, rxyx, ryxxx, ryxyy, ryyyxy, ryyxyxy, ryyyxxy, ryyyyx} is the final test set of the TPC-UIO method.


## 3.2.1. State Covering Set Generation

Definition 1 (State covering set).
Given an FSMM and an input sequence set Q=α0,α1,⋯,αn−1, if for any state si,∃αi∈Q0≤i≤n−1 satisfies δs0,αi=si, where s0 is the initial state, then Q is a state covering set of M.There must be a state covering set in initially connected FSM, and an empty sequenceε is included to reach the initial state s0. In addition, only state covering set of prefix closure is considered in this paper. As described in Algorithm 1, given an FSM with n states {s1,s2,⋯,sn} in which s1 is the initial state and a transition tree T with only a root node s1, state covering set SCM is first initialized to ϕ. Then, for each transition starting with s1, a branch annotated with the input/output of the transition is added in T. Next, for each transition starting with a leaf node appears for the first time in T, a branch annotated with the input/output of the transition is added in T iteratively until there is no leaf node appearing for the first time that can be found. So far, the complete transition tree is constructed. Finally, for each state si1≤i≤n, an input/output sequence βi from s1 to si that appears for the first time in T is obtained and βi is thrown to SCM.Algorithm 1: State covering set generation
Input: FSM M with n states {s1, s2,…sn} and s1 is the initial state, transition tree T and Root(T)=s1Output: State covering set SC(M)1: Initialize SC(M)=ϕ2:for each transition starting with s13: Add a branch in T and mark the branch with the input/output of the transition4:end for5:do6:for each leaf node appears for the first time in T7: Add a branch in T for each transition starting with the leaf node and mark the branch with the input/output of the transition8:end for9:until leaf node appears for the first time cannot be found in T10:for (i=1; i≤n; i++)11: Get an input/output sequenceβi from s1 to si that appears for the first time in T12: SC(M)= SC(M)∪βi13:end forAccording to Algorithm1, the transition tree of M1 is shown in Figure 6, and ε,y/1,y/1y/1 is a state covering set obtained from the transition tree.Figure 6
Transition tree ofM1.


## 3.2.2. TPC Test Set Generation

Definition 2 (adjacent transition).
If the end state of a transitiont1=(s1, s, i1/o1) is the start state of a transition t2=(s, s2, i2/o2), t1 and t2 are a pair of adjacent transition.
The test set of TPC method covers each pair of adjacent transitions in FSM at least once. As shown in Algorithm2, given an FSM with n states {s1,s2,⋯,sn} in which s1 is the initial state and a state covering set SCM={α1,α2,⋯,αn}, TPC test set TPCM is first initialized to ϕ. Then, for each state si1≤i≤n, each transition sequence β of length 2 starting from si is obtained and αiβ is thrown to TPCM.Algorithm 2: TPC test set generation
Input: FSM M with n states {s1, s2,…sn} and s1 is the initial state, state covering set SC(M)={α1, α2,…αn}Output: TPC test set TPC(M)1: Initialize TPC(M)=ϕ2:for (i=1; i≤n; i++)3:for each transition sequence β of length 2 starting from si4: TPC(M)= TPC(M) ∪αiβ5:end for6:end forConsiderM1 in Figure 2, {rxx, rxy, ryy, ryx, ryxx, ryxy, ryyx, ryyy, ryyxx, ry, ryyxy, ryyyx, ryyyy} is the test set of M1 under the TPC method.


## 3.2.3. UIO Generation

Definition 3 (UIO sequence).
An input/output sequenceβ is a UIO sequence of state si if and only if for any state sj∈Ssj≠si,λsi,βin≠λsj,βin, where βin is the input part of β.Definition 4 (uncertainty of the start states).
Given an FSMM and an input sequence α, a partition πα of the state set S can be obtained according to the output generated by each state for α. For any state si and sj, they will be in the same partition block if and only if they cannot be distinguished by α, i.e., λsi,α=λsj,α, and this partition is called the uncertainty of the start states.Definition 5 (uncertainty of the current states).
The current states ofM after delivering α can be expressed as δB,α∣B∈πα, and this partition is called the uncertainty of the current states.In this way, the scope of the state before and after the inputα can be learned according to the output corresponding to α. The idea of state partition can be applied to the construction of successor tree.Definition 6 (successor tree).
The successor tree of an FSM is a tree showing the behavior of the FSM at any state and upon any input sequence.For each possible input sequence, there is a path starting from the root node in the successor tree and each node in the successor tree is annotated with the uncertainty of start states as well as the uncertainty of current states.The successor tree ofM1 is shown in Figure 7. When x is delivered to the set of states {s1, s2, s3}, according to the different output, the partition blocks of start state uncertainty are 0{s1,s3} and 1{s2}, respectively, where 0 and 1 represent the output generated by the state in the partition block. The corresponding partition blocks of current state uncertainty are {s1,s3} and {s2}, respectively. When x is again delivered to the current state uncertainty {s1,s3} and {s2} according to the different output, the partition blocks of start state uncertainty are 00{s1,s3} and 11{s2}, respectively. The corresponding partition blocks of current state uncertainty are {s1,s3} and {s2}. Since the set {s1,s3} can never be further divided by x, this branch can terminate the decomposition about input x. Next, y is delivered to the partition blocks of the current state uncertainty {s1,s3} and{s2}; according to the different output, the partition blocks of start state uncertainty are 01{s1}, 00{s3}, and 11{s2}, respectively. The corresponding current state uncertainty partition blocks are {s2}, {s1}, and {s3}, respectively. Since there is only one element in each partition block, the division of this branch ends here. In the same way, we can construct other branches in the successor tree until a successor tree meeting the requirement is generated.Figure 7
Successor tree ofM1.In this paper, UIO sequence is obtained by successor tree. Given an FSM and its successor tree, if there is only one statesi in a partition block of the start state uncertainty, we will get a UIO sequence of si. Here, we only consider the shortest UIO sequence; that is, the UIO sequence we first obtained in the top-down search of the successor tree. As shown in Figure 7, the UIO sequence of s1 is x/0y/1, y/1x/1, or y/1y/1, the UIO sequence of s2 is x/1, and the UIO sequence of s3 is y/0.


## 3.2.4. Test Set Generation of TPC-UIO Method

Definition 7 (TPC-UIO method).
The test set of the TPC-UIO method should satisfy two conditions. (1) Cover each pair of adjacent transition in an FSM at least once. (2) Identify the end state of each pair of adjacent transition using the shortest UIO sequence.As shown in Algorithm3, given TPC test set TPCM of an FSM and UIO sequence of each state, for each test case in TPCM, identify the end state of the test case by the corresponding UIO sequence. Then, the test cases which are true prefixes of others are deleted and TPC-UIO test set TPC-UIOM is constructed.Algorithm 3: Test set generation of TPC-UIO method
Input: TPC test set TPC(M), UIO sequence of each stateOutput: TPC-UIO test set TPC-UIO(M)1:for each test case in TPC(M)2: Identify the end state of the test case by the corresponding UIO sequence3:end for4: delete the test cases which are true prefixes of othersTakingM1 for example, {rxxxy, rxyx, ryxxx, ryxyy, ryyyxy, ryyxyxy, ryyyxxy, ryyyyx} is the final test set of the TPC-UIO method.


## 4. Case Study

### 4.1. Experimental Subject

In existing literatures on FSM conformance testing, most of researchers conduct experiment using randomly generated FSMs. Generate FSMs randomly can obtain a large amount of FSMs in a short time, however, whether the experimental conclusions obtained from randomly generated FSMs are completely applicable on FSM empirical cases are still uncertain. This paper selects 14 established FSM empirical cases which are designed and generated by testers with professional experience and domain knowledge [17, 22–29]. The information of all FSM empirical cases is shown in Table 4. ∣S∣, ∣I∣, and ∣T∣ denote the number of states, the number of inputs, and the number of transitions, respectively.Table 4
Experimental subject.
FSM∣S∣∣I∣∣T∣Connection and release process of MAC layer in ZigBee protocol477Base station model in WM2RP protocol333Intermediate node model in WM2RP protocol444Leaf node model in WM2RP protocol333Railway signal system communication protocol91520Conference protocol51128INRES communication protocol459Transfer Protocol41018ISDN BRI network layer protocol81325NBS TP4 protocol81226Alternating Bit Protocol8510RPL host protocol5610RPL router protocol81429LLN Border Router Protocol456


### 4.2. Mutation Generation

In this paper, we use mutations of the specification to model faults in the implementation. Mutation operators [30] are introduced to obtain the three most typical faults in FSM conformance testing.Definition 8 (change initial state (CIS)).
This operator represents the initialization fault: change initial states0 to sksk≠s0 such that the implementation starts from an incorrect initial state, that is, CISM=N=I,O,S,sk,δ,λ∣sk∈S·sk≠s0.Definition 9 (change output (CO)).
This operator represents the output fault such that an unexpected output is produced in an implementation. Formally,COM=N=I,O,S,s0,δ,Λ∃x∈I,si∈S·Λsi,x≠λsi,x.Definition 10 (change end state (CES)).
This operator represents the end state fault such that the implementation moves to an incorrect state. Formally,CESM=N=I,O,S,s0,Δ,λ∃x∈I,si∈S·Δsi,x≠δsi,x.


### 4.3. Experimental Setup

In order to improve the credibility of the experimental results, experimental replication is adopted in this paper, and the number of replications in each round is not the same. For every FSM empirical case, each type of mutation is randomly operated 10 times, 100 times, 1000 times, 10000 times, 20000 times, 30000 times, 40000 times, 50000 times, 60000 times, 70000 times, 80000 times, 90000 times, and 100000 times; that is, a total of three groups including 551110 mutations in each group are obtained.


### 4.4. Result Analysis

#### 4.4.1. Comparison of Test Cost

The test set information of all FSM empirical cases is shown in Table5. L represents the length of the test set and N represents the number of the test cases in the test set, that is, the number of reset operations.(i)
Only consider the length of the test set. For all FSM empirical cases, when considering the average length of the test sets of each test method, the average length of the UIO method is 59.64, the average length of the TPC method is 186.57, and the average length of the TPC-UIO method is 227.93. Figure8 indicates that the length of the test set for TPC-UIO method is larger than that for the TPC method and UIO method for each empirical case. Compared with that of the TPC method, the average increase of the length of the TPC-UIO method is 24.32%(ii)
Only consider the number of the test cases. For all FSM empirical cases, when considering the average number of the test cases of each test method, the average number of the test cases for the UIO method is 9.93, the average number of the test cases for the TCP method is 32.07, and the average number of the test cases for the TPC-UIO method is 33.14. Figure9 indicates that the number of the test cases for TPC-UIO method is more than or equal to that for the TPC method and UIO method for each empirical case. Compared with the TPC method, the average increase of the number of the test cases of the TPC-UIO method is 6.43%(iii)
Consider both the length of the test set and the number of the test cases. In order to quantitatively analyze the cost considering both the length of the test set and the number of the test cases,L is used to denote the length of the test set and the cost generated by the length of the test sets is expressed as a function C1=fL, and N is used to denote the number of the test cases and the cost generated by the number of the test cases is expressed as a function C2=gN. The total test cost considering both the length of the test set and the number of the test cases can be expressed as C=C1+C2. Assuming that the test cost of a test set containing only one test case of length 1 is 1, then f1+g1=1f1<1,g1<1. Assuming α=f1, then g1=1−α, fL=α×L, gN=1−α×N, and C=α×∑i=1NLi+1−α×N where Li represents the length of the ith test case, so that the cost of each test method can be quantified by assigning a value to α. Generally, the impact of the length of the test set is greater than the impact of the number of the test cases, so it is usually α>0.5. Figure 10 shows the relationship among the comprehensive test costs of each empirical case under different test methods when α is assigned 0.6, 0.7, 0.8, and 0.9, respectively. From the examples of different values of α, it can be seen that when α takes different values greater than 0.5, the comprehensive test cost of each empirical case under different test methods changes, and the larger the value of α, the greater the test cost. However, the relative relationship among test costs of different empirical cases has not changed. The comprehensive test cost of the TPC-UIO method is always larger than that of the TPC method and UIO method for each empirical case. Compared with the TPC method, the average increase of the comprehensive test cost of the TPC-UIO method is 23.22%.Table 5
Collection of test set information.
FSMUIOTPCTPC-UIOLNLNLNConnection and release process of MAC layer in ZigBee protocol194194234Base station model in WM2RP protocol515161Intermediate node model in WM2RP protocol616171Leaf node model in WM2RP protocol515161Railway signal system communication protocol66122604830848Conference protocol13525762138922142INRES communication protocol32672138513Transfer Protocol70162044524945ISDN BRI network layer protocol98182234126441NBS TP4 protocol153222184031845Alternating Bit Protocol365243405RPL host protocol376951511015RPL router protocol156226919682098LLN Border Router Protocol173285335Figure 8
Relationship among the length of test sets for TPC, UIO, and TPC-UIO.Figure 9
Relationship among the number of test cases for TPC, UIO, and TPC-UIO.Figure 10
Relationship among TPC, UIO, and TPC-UIO considering both the length of test sets and the number of test cases.
(a)
α=0.6(b)
α=0.7(c)
α=0.8(d)
α=0.9


#### 4.4.2. Comparison of Fault Coverage

As shown in Table6, the TPC method, UIO method, and TPC-UIO method can achieve 100% fault coverage for initialization fault and output fault. Neither the TPC method nor the UIO method can reach 100% fault coverage for end state fault. The TPC-UIO method can effectively improve the fault coverage rate and achieve 100% fault coverage.Table 6
Fault coverage ranking of TPC, UIO, and TPC-UIO.
RankingInitialization faultOutput faultEnd state fault1TPC (100%) UIO (100%) TPC-UIO (100%)TPC (100%) UIO (100%) TPC-UIO (100%)TPC-UIO (100%)2UIO (99.8%)3TPC (99.06%)Although the differences of data in the experiment seem to be subtle, these differences are still worthy of attention. (1) When the fault domain is very large, even a small increase of fault coverage represents a large number of faults. (2) In a safety-critical environment, there is a tiny optimization even if an optimization of only one fault has high practical value. It is noted that the end state faults in the experiment are generated randomly. In fact, the higher the proportion of the analyzed end state faults in Section4, the better the fault coverage of the combined method.


## 4.1. Experimental Subject

In existing literatures on FSM conformance testing, most of researchers conduct experiment using randomly generated FSMs. Generate FSMs randomly can obtain a large amount of FSMs in a short time, however, whether the experimental conclusions obtained from randomly generated FSMs are completely applicable on FSM empirical cases are still uncertain. This paper selects 14 established FSM empirical cases which are designed and generated by testers with professional experience and domain knowledge [17, 22–29]. The information of all FSM empirical cases is shown in Table 4. ∣S∣, ∣I∣, and ∣T∣ denote the number of states, the number of inputs, and the number of transitions, respectively.Table 4
Experimental subject.
FSM∣S∣∣I∣∣T∣Connection and release process of MAC layer in ZigBee protocol477Base station model in WM2RP protocol333Intermediate node model in WM2RP protocol444Leaf node model in WM2RP protocol333Railway signal system communication protocol91520Conference protocol51128INRES communication protocol459Transfer Protocol41018ISDN BRI network layer protocol81325NBS TP4 protocol81226Alternating Bit Protocol8510RPL host protocol5610RPL router protocol81429LLN Border Router Protocol456


## 4.2. Mutation Generation

In this paper, we use mutations of the specification to model faults in the implementation. Mutation operators [30] are introduced to obtain the three most typical faults in FSM conformance testing.Definition 8 (change initial state (CIS)).
This operator represents the initialization fault: change initial states0 to sksk≠s0 such that the implementation starts from an incorrect initial state, that is, CISM=N=I,O,S,sk,δ,λ∣sk∈S·sk≠s0.Definition 9 (change output (CO)).
This operator represents the output fault such that an unexpected output is produced in an implementation. Formally,COM=N=I,O,S,s0,δ,Λ∃x∈I,si∈S·Λsi,x≠λsi,x.Definition 10 (change end state (CES)).
This operator represents the end state fault such that the implementation moves to an incorrect state. Formally,CESM=N=I,O,S,s0,Δ,λ∃x∈I,si∈S·Δsi,x≠δsi,x.


## 4.3. Experimental Setup

In order to improve the credibility of the experimental results, experimental replication is adopted in this paper, and the number of replications in each round is not the same. For every FSM empirical case, each type of mutation is randomly operated 10 times, 100 times, 1000 times, 10000 times, 20000 times, 30000 times, 40000 times, 50000 times, 60000 times, 70000 times, 80000 times, 90000 times, and 100000 times; that is, a total of three groups including 551110 mutations in each group are obtained.


## 4.4. Result Analysis

### 4.4.1. Comparison of Test Cost

The test set information of all FSM empirical cases is shown in Table5. L represents the length of the test set and N represents the number of the test cases in the test set, that is, the number of reset operations.(i)
Only consider the length of the test set. For all FSM empirical cases, when considering the average length of the test sets of each test method, the average length of the UIO method is 59.64, the average length of the TPC method is 186.57, and the average length of the TPC-UIO method is 227.93. Figure8 indicates that the length of the test set for TPC-UIO method is larger than that for the TPC method and UIO method for each empirical case. Compared with that of the TPC method, the average increase of the length of the TPC-UIO method is 24.32%(ii)
Only consider the number of the test cases. For all FSM empirical cases, when considering the average number of the test cases of each test method, the average number of the test cases for the UIO method is 9.93, the average number of the test cases for the TCP method is 32.07, and the average number of the test cases for the TPC-UIO method is 33.14. Figure9 indicates that the number of the test cases for TPC-UIO method is more than or equal to that for the TPC method and UIO method for each empirical case. Compared with the TPC method, the average increase of the number of the test cases of the TPC-UIO method is 6.43%(iii)
Consider both the length of the test set and the number of the test cases. In order to quantitatively analyze the cost considering both the length of the test set and the number of the test cases,L is used to denote the length of the test set and the cost generated by the length of the test sets is expressed as a function C1=fL, and N is used to denote the number of the test cases and the cost generated by the number of the test cases is expressed as a function C2=gN. The total test cost considering both the length of the test set and the number of the test cases can be expressed as C=C1+C2. Assuming that the test cost of a test set containing only one test case of length 1 is 1, then f1+g1=1f1<1,g1<1. Assuming α=f1, then g1=1−α, fL=α×L, gN=1−α×N, and C=α×∑i=1NLi+1−α×N where Li represents the length of the ith test case, so that the cost of each test method can be quantified by assigning a value to α. Generally, the impact of the length of the test set is greater than the impact of the number of the test cases, so it is usually α>0.5. Figure 10 shows the relationship among the comprehensive test costs of each empirical case under different test methods when α is assigned 0.6, 0.7, 0.8, and 0.9, respectively. From the examples of different values of α, it can be seen that when α takes different values greater than 0.5, the comprehensive test cost of each empirical case under different test methods changes, and the larger the value of α, the greater the test cost. However, the relative relationship among test costs of different empirical cases has not changed. The comprehensive test cost of the TPC-UIO method is always larger than that of the TPC method and UIO method for each empirical case. Compared with the TPC method, the average increase of the comprehensive test cost of the TPC-UIO method is 23.22%.Table 5
Collection of test set information.
FSMUIOTPCTPC-UIOLNLNLNConnection and release process of MAC layer in ZigBee protocol194194234Base station model in WM2RP protocol515161Intermediate node model in WM2RP protocol616171Leaf node model in WM2RP protocol515161Railway signal system communication protocol66122604830848Conference protocol13525762138922142INRES communication protocol32672138513Transfer Protocol70162044524945ISDN BRI network layer protocol98182234126441NBS TP4 protocol153222184031845Alternating Bit Protocol365243405RPL host protocol376951511015RPL router protocol156226919682098LLN Border Router Protocol173285335Figure 8
Relationship among the length of test sets for TPC, UIO, and TPC-UIO.Figure 9
Relationship among the number of test cases for TPC, UIO, and TPC-UIO.Figure 10
Relationship among TPC, UIO, and TPC-UIO considering both the length of test sets and the number of test cases.
(a)
α=0.6(b)
α=0.7(c)
α=0.8(d)
α=0.9


### 4.4.2. Comparison of Fault Coverage

As shown in Table6, the TPC method, UIO method, and TPC-UIO method can achieve 100% fault coverage for initialization fault and output fault. Neither the TPC method nor the UIO method can reach 100% fault coverage for end state fault. The TPC-UIO method can effectively improve the fault coverage rate and achieve 100% fault coverage.Table 6
Fault coverage ranking of TPC, UIO, and TPC-UIO.
RankingInitialization faultOutput faultEnd state fault1TPC (100%) UIO (100%) TPC-UIO (100%)TPC (100%) UIO (100%) TPC-UIO (100%)TPC-UIO (100%)2UIO (99.8%)3TPC (99.06%)Although the differences of data in the experiment seem to be subtle, these differences are still worthy of attention. (1) When the fault domain is very large, even a small increase of fault coverage represents a large number of faults. (2) In a safety-critical environment, there is a tiny optimization even if an optimization of only one fault has high practical value. It is noted that the end state faults in the experiment are generated randomly. In fact, the higher the proportion of the analyzed end state faults in Section4, the better the fault coverage of the combined method.


## 4.4.1. Comparison of Test Cost

The test set information of all FSM empirical cases is shown in Table5. L represents the length of the test set and N represents the number of the test cases in the test set, that is, the number of reset operations.(i)
Only consider the length of the test set. For all FSM empirical cases, when considering the average length of the test sets of each test method, the average length of the UIO method is 59.64, the average length of the TPC method is 186.57, and the average length of the TPC-UIO method is 227.93. Figure8 indicates that the length of the test set for TPC-UIO method is larger than that for the TPC method and UIO method for each empirical case. Compared with that of the TPC method, the average increase of the length of the TPC-UIO method is 24.32%(ii)
Only consider the number of the test cases. For all FSM empirical cases, when considering the average number of the test cases of each test method, the average number of the test cases for the UIO method is 9.93, the average number of the test cases for the TCP method is 32.07, and the average number of the test cases for the TPC-UIO method is 33.14. Figure9 indicates that the number of the test cases for TPC-UIO method is more than or equal to that for the TPC method and UIO method for each empirical case. Compared with the TPC method, the average increase of the number of the test cases of the TPC-UIO method is 6.43%(iii)
Consider both the length of the test set and the number of the test cases. In order to quantitatively analyze the cost considering both the length of the test set and the number of the test cases,L is used to denote the length of the test set and the cost generated by the length of the test sets is expressed as a function C1=fL, and N is used to denote the number of the test cases and the cost generated by the number of the test cases is expressed as a function C2=gN. The total test cost considering both the length of the test set and the number of the test cases can be expressed as C=C1+C2. Assuming that the test cost of a test set containing only one test case of length 1 is 1, then f1+g1=1f1<1,g1<1. Assuming α=f1, then g1=1−α, fL=α×L, gN=1−α×N, and C=α×∑i=1NLi+1−α×N where Li represents the length of the ith test case, so that the cost of each test method can be quantified by assigning a value to α. Generally, the impact of the length of the test set is greater than the impact of the number of the test cases, so it is usually α>0.5. Figure 10 shows the relationship among the comprehensive test costs of each empirical case under different test methods when α is assigned 0.6, 0.7, 0.8, and 0.9, respectively. From the examples of different values of α, it can be seen that when α takes different values greater than 0.5, the comprehensive test cost of each empirical case under different test methods changes, and the larger the value of α, the greater the test cost. However, the relative relationship among test costs of different empirical cases has not changed. The comprehensive test cost of the TPC-UIO method is always larger than that of the TPC method and UIO method for each empirical case. Compared with the TPC method, the average increase of the comprehensive test cost of the TPC-UIO method is 23.22%.Table 5
Collection of test set information.
FSMUIOTPCTPC-UIOLNLNLNConnection and release process of MAC layer in ZigBee protocol194194234Base station model in WM2RP protocol515161Intermediate node model in WM2RP protocol616171Leaf node model in WM2RP protocol515161Railway signal system communication protocol66122604830848Conference protocol13525762138922142INRES communication protocol32672138513Transfer Protocol70162044524945ISDN BRI network layer protocol98182234126441NBS TP4 protocol153222184031845Alternating Bit Protocol365243405RPL host protocol376951511015RPL router protocol156226919682098LLN Border Router Protocol173285335Figure 8
Relationship among the length of test sets for TPC, UIO, and TPC-UIO.Figure 9
Relationship among the number of test cases for TPC, UIO, and TPC-UIO.Figure 10
Relationship among TPC, UIO, and TPC-UIO considering both the length of test sets and the number of test cases.
(a)
α=0.6(b)
α=0.7(c)
α=0.8(d)
α=0.9


## 4.4.2. Comparison of Fault Coverage

As shown in Table6, the TPC method, UIO method, and TPC-UIO method can achieve 100% fault coverage for initialization fault and output fault. Neither the TPC method nor the UIO method can reach 100% fault coverage for end state fault. The TPC-UIO method can effectively improve the fault coverage rate and achieve 100% fault coverage.Table 6
Fault coverage ranking of TPC, UIO, and TPC-UIO.
RankingInitialization faultOutput faultEnd state fault1TPC (100%) UIO (100%) TPC-UIO (100%)TPC (100%) UIO (100%) TPC-UIO (100%)TPC-UIO (100%)2UIO (99.8%)3TPC (99.06%)Although the differences of data in the experiment seem to be subtle, these differences are still worthy of attention. (1) When the fault domain is very large, even a small increase of fault coverage represents a large number of faults. (2) In a safety-critical environment, there is a tiny optimization even if an optimization of only one fault has high practical value. It is noted that the end state faults in the experiment are generated randomly. In fact, the higher the proportion of the analyzed end state faults in Section4, the better the fault coverage of the combined method.


## 5. Related Work

Conformance testing based on FSM has always been an active research direction in software testing [31–39]. In the existing literature, there are precedents for improving fault coverage in conformance testing by combining different testing methods. Mouchawrab et al. [40] investigated the complementarity of the test method of round trip path based on UML state machine and the test method of edge coverage based on source code and then extended round-trip paths testing with edge coverage testing. Results show that the two test strategies are significantly more effective when combined by augmenting state machine testing with structural testing. Hutchins et al. [41] combined the all-use criterion in a white-box test and the edge coverage criterion in a black-box test to improve fault coverage with higher test cost. Results show that significant improvements in the effectiveness of coverage-based tests usually occurred as coverage increased from 90% to 100% and the complementarity of the two methods in their effectiveness was proved. Briand et al. [42] extended the round trip path criterion in the white-box test with the classification partition in the black-box test and obtained better fault detection performance.This paper also analyzes the complementary characteristic of different test methods and improves the fault coverage at the expense of an acceptable increase of test cost, so as to meet the high requirements of fault coverage in wireless communications.


## 6. Conclusion and Future Work

There are some differences about the test requirements of the TPC method and UIO method in wireless protocol conformance testing. The TPC method focuses on covering all consecutive operations of length two between entities or processes in wireless communication. UIO method focuses on identifying each state of entities or processes and confirming the input and output information between any two states in wireless communication. In order to improve the effectiveness of wireless protocol testing, a combined method is presented and the method is evaluated by 14 established empirical cases. A unified method based on state covering set is used to generate test sets for each test method and three types of classic faults are generated by mutating the specification. Fault coverage has been effectively improved by the combining method. The experimental results show that the fault coverage of each empirical case can be improved to 100% when the average test cost is only increased by 17.99%. Since what we considered is the specifications modeled by FSMs and the faults generated based on FSMs, although the fault coverage has been effectively improved, these results cannot be popularized to the specifications modeled by other formal models or faults generated based on code.In a future work, we will try to enrich the experimental data with more publicly available FSM empirical cases. To better describe the behavior characteristics of wireless protocol testing, the future work will also consider extended semantic FSMs to improve the expression ability of the model.



---

*Source: 6378139-2021-07-15.xml*