# Test Purpose Oriented I/O Conformance Test Selection with Colored Petri Nets

Authors: Jing Liu; Xinming Ye; Jiantao Zhou
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

This paper proposes an input-output conformance (IOCO) test selection method directed by test purpose model specified with colored Petri nets (CPN). Based on conformance testing oriented CPN models for specifying software functional behaviors and specific test purposes, respectively, feasible test cases are generated, guided by the CPN based IOCO relation, using synchronized model simulation with the proof of the soundness of test generation and the coverage towards test purposes. This test selection method integrates the merits the IOCO testing theory and the CPN modeling synergistically and is applied as a novel and applicable test selection method for actual testing practice of large-scale software systems. As the synchronized model simulation with two CPN models is irrespective of their model scale, the effectiveness and practicability of our test selection method are enhanced with scalability.


---

## Body

## 1. Introduction

Software systems running based on network environment are ubiquitous. It is quite significant to validate their functional correctness. Conformance testing [1] just aims at checking whether the software implementation conforms to its functional specification. Therefore, conformance testing is indispensable in such software system validation process. Nowadays, model based testing (MBT) technology is introduced and well developed to promote the efficiency and effectiveness of conformance test generation [2–6]. It allows for generating test cases with test oracles from a formal model that specifies the software behaviors explicitly, which improves the low-level efficiency and inaccuracy of the manual test case generation process. In particular, concerning the conformance testing towards network based software systems, the well-established input-output conformance (IOCO) testing theory and technologies [6–9] are more feasible, because the IOCO relation formally defines what external output should be observed through the practical test execution and how to determine the conformance based on these observations. In our studies, network based software systems are adopted as our system under testing (SUT) and the IOCO testing theory is the most significant theoretical foundation in our testing research.In original IOCO testing theory, labeled transition system (LTS) is utilized as its basic formal models. However, compared with LTS or other formal modeling methods such as automata or process algebra, colored Petri nets (CPN) [10] have more advantages for specifying and validating complicated functional behaviors of network software systems. First, CPN could not only specify the detailed and complicated software functionalities intuitively and hierarchically but also support visible simulation and efficient analysis to validate the correctness of software behaviors. Validated models are indispensable for successful application of MBT approaches. Second, CPN models can execute dynamically, which is directed by the data-dependent control flow of system behaviors. Generating test cases by such model simulation process, they certainly contain actual test data and test oracles, so they are quite feasible for guiding practical test execution.We have proposed the introductory idea of CPN model based IOCO test generation approach in our conference paper [11]. However, that paper just focuses on elementary test case generation approach, and, in this paper, we focus on test case selection; that is, test purpose is considered in test case generation to improve its pertinence, and a novel test purpose model oriented IOCO test selection method is proposed. Specifically, conformance testing oriented colored Petri nets (CT-CPN) models are used as formal models for modeling software specification, and PN-ioco relation is defined [11]. Then, we model test purposes as CT-CPN models, and test cases are generated using synchronized model simulation between a specification CT-CPN model and a test purpose CT-CPN model. Besides, we prove the soundness of test generation; that is, as long as the implementation fails one test case, it will definitely not conform to its specification. We also prove the coverage towards test purpose; that is, generated test cases should cover and only cover functional behaviors which are specified in test purpose models. We finally apply the test selection method into a file sharing software system to illustrate its feasibility and effectiveness.CPN model based IOCO test selection has several advantages, compared with current IOCO test selection method in literatures [12–14]. First, CPN models can execute dynamically, which is directed by the data-dependent control flow of system behaviors. Generating by such model simulation process, test cases certainly contain actual test data and test oracles, so they are quite feasible for guiding practical test execution. Second, as the synchronized model simulation with two CPN models is irrespective of their model scale, the effectiveness and practicability of our test selection method are enhanced with scalability. In a word, a CPN model based IOCO test selection method tends to be a promising testing technology to validate the correctness of reactive network software systems more efficiently and more effectively.The paper is organized as follows. The related work and preliminaries are discussed in Section2. The framework of our CPN model based IOCO test selection method is introduced in Section 3. The formal definition of CT-CPN models and PN-ioco relation is recalled in Section 4 as basic knowledge. Then, in Section 5, a novel test case selection algorithm is proposed using synchronized simulation technology in CPN modeling context to guarantee that all test cases are feasible for practical test execution and totally cover test purposes. In Section 6, we prove the soundness of test generation and the coverage degree towards test purposes. As a representative, we apply the test selection method into a file sharing software system and perform its actual test selection and execution procedure to illustrate the feasibility and effectiveness of our test selection method.


## 2. Related Work and Preliminaries

As for test case generation approaches based on CPN models, Watanabe and Kudoh [15] propose a basic test generation algorithm, which could be considered as the first step in this field. First, the reachability tree of a CPN model is constructed, and all input-output sequences from the root node to leaf nodes in this tree are traversed to form the test cases, and, then, equivalent markings in that tree are combined to construct the corresponding reachability graph, and FSM model based test case generation approaches are applied directly based on this graph. Recently, Farooq et al. [16] use random walking technology to randomly traverse the model state space to generate the test cases, where several sequential coverage criteria and concurrent coverage criteria are proposed to guide the test selection. Zhu and He [17] have proposed four specific testing strategies towards the high-level Petri nets. For each strategy, they first define a set of schemes to observe and record the testing results, and they also define a set of coverage criteria to measure the test adequacy. But, no detailed test generation algorithms are explicitly presented. We have proposed the introductory idea of CPN model based IOCO testing approach [11]. It focuses on elementary test case generation approach, and, in this paper, we focus on test selection method.In order to promote the pertinence of testing projects, certain test selection criterion is always adopted in test generation process to produce finite and indispensable actual test cases. It is quite propitious for performing feasible testing projects under constraint of testing execution time and cost. Generally, test selection for function testing is classified as test purposed oriented methods [9, 12, 13, 18], random testing methods [8, 19, 20], property coverage based methods [21, 22], and symbolic test data selection methods [14]. However, test purposed oriented methods usually specify part of functional behaviors of software as test purpose model and make generated test cases focus on testing such specific behaviors. It is quite propitious for performing feasible conformance testing towards network based software systems with black-box and reactive behavior characteristics. In this paper, a novel IOCO test selection method is proposed using synchronized model simulation technology between two CPN models. It has high scalability for dealing with the larger software models.CPN is advantaged for modeling and validation of systems where concurrency and communication are key characteristics. Its formal definitions are referred to in [10]. Besides, other key definitions concerning the behavior simulation of CPN models which are used in following sections are listed as follows.Definition 1.
For a CPN = (P,T,A, Σ,V,C,G,E,I), consider (1)
preset andpostset of the place or the transition:
(1)∀p∈P:pre(p)={t∈T∣(t,p)∈A};post(p)={t∈T∣(p,t)∈A},∀t∈T:pre(t)={p∈P∣(p,t)∈A};post(t)={p∈P∣(t,p)∈A};(2)
M⇒σ=def∃Mi:M⇒σMi, where σ=(t0,b0), (t1,b1)⋯(ti-1,bi-1), M→(t0,b0)M1→(t1,b1)⋯→(ti-1,bi-1)Mi, if |σ|=1, M→σ is used instead;(3)
trace(M)=def{σ∈BE(T)*∣M⇒σ};(4)
M  fires σ=def{Mn∣M⇒σMn,σ∈BE(T)*};(5)
CPN isdeterministic, if |Mfiresσ|≤1;(6)
CPN hasfinite output, if |Mfiresσ|≤n(n∈N);(7)
CPN hasfinite behavior, if ∃n∈N, ∀σ∈trace(M0):|σ|<n.
In this definition,M stands for markings, σ stands for occurrence trace of system behavioral execution, and BE stands for binding elements with a transition and its value bindings into variables.


## 3. Methodology Overview

Integrating the merits of the IOCO testing theory and the CPN modeling synergistically and then constructing a novel IOCO test selection method based on test purpose CPN models are the major research goals of this paper. However, simply replacing LTS modeling with CPN modeling does not make sense. In Figure1, we propose a framework of IOCO test selection methodology based on CPN models, which is composed of three related parts in the whole test selection process.Figure 1
The framework of IOCO test selection method with CPN models.First, modified CPN modeling is proposed asCT-CPN models to specify key characteristics and requirements for conformance testing scenario accurately. For example, CT-CPNS models software functional behaviors according to software requirement specification, CT-CPNI models actual software implementation behaviors, CT-CPNTP models software functional behaviors of specific test purposes, and CT-CPNTC models finally generated test cases. Such CT-CPN series models explicitly specify external visible actions which are significant in practical test execution, that is, to make the most of both the place and the transition elements in CT-CPN models to distinguish visible actions from internal actions. In particular, to deal with the special output actions, such as the quiescence or deadlock [7], it introduces new kind of transitions to model them accurately. Besides, a corresponding implementation relation in the context of CT-CPN modeling is proposed as PN-ioco relation to precisely specify what it means for an implementation to conform to its functional specification. In CPN model context, software behaviors are simulated with specific system data, so we have to determine the IOCO conformance via comparing the output actions with specific data. This part of contents had been proposed in our conference paper [11], and, in order to make this paper self-contained, we will show the basic formal definition of CT-CPN model and PN-ioco relation in Section 4.Second, based on the aboveCT-CPN modeling and PN-ioco relation, we need to develop a novel test selection approach with two desired goals. One is to make the test selection with high scalability for dealing with more complicated system models, and the other one is to make all test cases feasible for the practical test executions. Therefore, in Section 5, we model test purposes as CT-CPNTP models and then propose a novel IOCO test case selection method, where test cases are generated using synchronized model simulation between a CT-CPNS model and a CT-CPNTP model. When the synchronized simulation procedure terminated, a final test case is produced and specified as a CT-CPNTC model. As the synchronized model simulation is irrespective of model scale, its effectiveness and practicability tend to be enhanced with high scalability.Third, in Section6, we prove the soundness of test generation; that is, as long as the software implementation fails one test case, it will definitely not conform to its functional specifications. We also prove the coverage towards test purposes; that is, generated test cases should cover and only cover functional behaviors which are specified in test purpose models. In this way, under constraint of testing execution time and cost, we could generate finite and indispensable actual test cases to promote the pertinence of testing projects.Developing a CPN model based IOCO test selection method is challenging but quite promising. It has solid theoretical foundation and bright application prospect, so it tends to be used as a competent and effective conformance testing technology to validate the correctness of network based software systems.


## 4. CT-CPN Modeling and PN-ioco Relation

### 4.1. Specification Modeling

Definition 2.
ACT-CPNS is a triple CT-CPNS = (CPN, PS, TS):(1)
CPN is a basic colored Petri nets model;(2)
PS=P, PS=PSO∪PSE: PSO is the set ofobservable places; PSE is the set ofinternal places; PSO∩PSE=ϕ;(3)
TS=T, TS=TSI∪TSO∪TSE: TSI is the set ofinput transitions; TSO is the set ofoutput transitions; TSE is the set ofinternal transitions; TSI∩TSO=TSI∩TSE=TSO∩TSE=ϕ;(4)
CT-CPNS has finite output; that is, |trace(M0)|≤n(n∈N);(5)
CT-CPNS does not have infinite sequences of internal actions; that is, ¬∃M:M⇒σM,σ∈BE(TSE)*.In theCT-CPNS modeling, token data in the observable places could present the externally observed data, so an observable place is always the postset of an input transition or an output transition to display what data should be observed after executing those external transitions. The input transition models input actions that accept input data provided by testers and the output transition models output actions that produce visible output observations. Thus, observable places and input/output transitions are used together to explicitly specify external visible behaviors of a certain system. Besides, the internal transitions and internal places could represent internal and unobservable execution of system behaviors. Models must not have loops of internal transitions, which will make system implementations have no response to help us to distinguish this scenario from the deadlock.


### 4.2. Implementation Modeling

As system implementations are actual physical thing, that is, software, hardware, or a hybrid system, rather than formal objects, a test hypothesis [7] assumes that every system implementation corresponds to an a-priori formal model, but these formal models cannot be explicitly constructed. Therefore, CT-CPNI is just proposed to formally specify system implementations.Definition 3.
ACT-CPNI is a triple CT-CPNI=(CPN,PI,TI):(1)
CPN is a basic colored Petri nets model;(2)
PIO=PSO and TII=TSI, TIO=TSO the implementation models and the specification model of the same system having the same observable places and input/output transitions;(3)
{δ}⊂TI: δ is thesuspension transition, and M→δM.Any possible test output, such as real data, deadlock, or quiescence should be managed inCT-CPNI modeling. In particular, the quiescence represents a scenario where software implementations have no visible outputs because they wait for input action to trigger following executions. Producing quiescence is a kind of special output action, which is modeled as the suspension transition δ. Firing a suspension action indicates that an implementation stays in the same state and needs input data as a trigger to continue executing.


### 4.3. PN-ioco Relation

In context ofCT-CPN modeling, conformance relation should be determined according to specific data in CT-CPN models, so PN-ioco relation is defined.Definition 4.
PN-ioco is a binary relation withss∈CT-CPNS and ii∈CT-CPNI:
i
i
PN-ioco
s
s
=
def
∀
σ
∈
SPtrace
(
M
S
): outtoken(MIfiresσ)=outtoken(MSfiresσ). (1)
ConsiderSPtrace(MS)=def{σ∈(BE(TS)∪δ)*∣MS⇒σ}; it enumerates all traces of the modelss, including the suspension transitions. MS and MI are initial markings, respectively.(2)
Considerouttoken(M)=def{M(P)∣P∈PSO∪PIO}; it represents the observable output token data. In the modelss, it records the token data of current observable places under a specific marking, while, in the modelii, it just corresponds to the actual observable output data produced by the system implementations during the test execution.Guided by the PN-ioco definition, the conformance is determined by comparing token data in the observable places along a specific SPtrace with the actually observed output from the implementation. If the actual observed output data are different from what are prescribed in the ss model, we could conclude with non-conformance decision. The equivalence of two  outtoken sets indicates that all prescribed observations should be actually observed in the practical test executions; that is, prescribed functionalities must be completely implemented. Therefore, the implementation that has valid but partial functionalities will not be said to conform to its specification model.


## 4.1. Specification Modeling

Definition 2.
ACT-CPNS is a triple CT-CPNS = (CPN, PS, TS):(1)
CPN is a basic colored Petri nets model;(2)
PS=P, PS=PSO∪PSE: PSO is the set ofobservable places; PSE is the set ofinternal places; PSO∩PSE=ϕ;(3)
TS=T, TS=TSI∪TSO∪TSE: TSI is the set ofinput transitions; TSO is the set ofoutput transitions; TSE is the set ofinternal transitions; TSI∩TSO=TSI∩TSE=TSO∩TSE=ϕ;(4)
CT-CPNS has finite output; that is, |trace(M0)|≤n(n∈N);(5)
CT-CPNS does not have infinite sequences of internal actions; that is, ¬∃M:M⇒σM,σ∈BE(TSE)*.In theCT-CPNS modeling, token data in the observable places could present the externally observed data, so an observable place is always the postset of an input transition or an output transition to display what data should be observed after executing those external transitions. The input transition models input actions that accept input data provided by testers and the output transition models output actions that produce visible output observations. Thus, observable places and input/output transitions are used together to explicitly specify external visible behaviors of a certain system. Besides, the internal transitions and internal places could represent internal and unobservable execution of system behaviors. Models must not have loops of internal transitions, which will make system implementations have no response to help us to distinguish this scenario from the deadlock.


## 4.2. Implementation Modeling

As system implementations are actual physical thing, that is, software, hardware, or a hybrid system, rather than formal objects, a test hypothesis [7] assumes that every system implementation corresponds to an a-priori formal model, but these formal models cannot be explicitly constructed. Therefore, CT-CPNI is just proposed to formally specify system implementations.Definition 3.
ACT-CPNI is a triple CT-CPNI=(CPN,PI,TI):(1)
CPN is a basic colored Petri nets model;(2)
PIO=PSO and TII=TSI, TIO=TSO the implementation models and the specification model of the same system having the same observable places and input/output transitions;(3)
{δ}⊂TI: δ is thesuspension transition, and M→δM.Any possible test output, such as real data, deadlock, or quiescence should be managed inCT-CPNI modeling. In particular, the quiescence represents a scenario where software implementations have no visible outputs because they wait for input action to trigger following executions. Producing quiescence is a kind of special output action, which is modeled as the suspension transition δ. Firing a suspension action indicates that an implementation stays in the same state and needs input data as a trigger to continue executing.


## 4.3. PN-ioco Relation

In context ofCT-CPN modeling, conformance relation should be determined according to specific data in CT-CPN models, so PN-ioco relation is defined.Definition 4.
PN-ioco is a binary relation withss∈CT-CPNS and ii∈CT-CPNI:
i
i
PN-ioco
s
s
=
def
∀
σ
∈
SPtrace
(
M
S
): outtoken(MIfiresσ)=outtoken(MSfiresσ). (1)
ConsiderSPtrace(MS)=def{σ∈(BE(TS)∪δ)*∣MS⇒σ}; it enumerates all traces of the modelss, including the suspension transitions. MS and MI are initial markings, respectively.(2)
Considerouttoken(M)=def{M(P)∣P∈PSO∪PIO}; it represents the observable output token data. In the modelss, it records the token data of current observable places under a specific marking, while, in the modelii, it just corresponds to the actual observable output data produced by the system implementations during the test execution.Guided by the PN-ioco definition, the conformance is determined by comparing token data in the observable places along a specific SPtrace with the actually observed output from the implementation. If the actual observed output data are different from what are prescribed in the ss model, we could conclude with non-conformance decision. The equivalence of two  outtoken sets indicates that all prescribed observations should be actually observed in the practical test executions; that is, prescribed functionalities must be completely implemented. Therefore, the implementation that has valid but partial functionalities will not be said to conform to its specification model.


## 5. Synchronized Simulation Based Test Selection

In Section3, we mention that, based on CT-CPN modeling and PN-ioco relation, a novel test selection method should be developed with two desired goals. One is to make such test selection with high scalability for dealing with more complicated system models, and the other one is to make all test cases feasible for practical test executions. Accordingly, we develop a test purpose oriented IOCO test selection method to meet these two goals, where test cases are generated through synchronized model simulation between a CT-CPNS model and a CT-CPNTP model. When synchronized simulation procedure terminates, a final and feasible test case model is produced and specified as CT-CPNTC.The intuitive idea of our test selection method is essentially a synchronized traversal between aCT-CPNS model and a CT-CPNTP model. It is performed by model simulation execution under given initial markings in these two models. Specifically, each given initial marking in a CT-CPNS model and a CT-CPNTP model could conduct a synchronized simulation between these two models once. During following synchronized simulation steps, enabled transitions in both models are capable of firing sequentially in a synchronized way. However, CT-CPNTP model is responsible for choosing which execution sequence should be cover, and actual test sequences and the data-dependent test oracles are all generated based on CT-CPNS model. If both models have no further enabled transitions, synchronized model simulation procedure will terminate, and a corresponding test case model is finally generated and specified as a CT-CPNTC model, while, in context of LTS based test selection in original IOCO testing theory, synchronous product of two LTS model is performed. However, with expansion of model scale, synchronous product operation cannot be executed accurately; thus such LTS based test selection approach fails to support testing large-scale software systems.In the following subsections, we first propose the formal definitions of test purpose and test case inCT-CPN modeling context. Then, a detailed test selection algorithm is developed with several test generation rules towards different kinds of model transitions. Finally, we adopt a file sharing software system as a representative to demonstrate practical test selection and test execution procedures.


### 5.1. Test Purpose Modeling

Test purpose is utilized to specify parts of software functional behaviors; for example, in the network based software systems, sending request packets, receiving data packets, or updating local key data structure could be modeled as a test purpose each. In order to promote the pertinence of testing large-scale software systems, test purpose models should participate in test generation process, since it can constrain the scope of test generation; that is, it just selects finite and indispensable test cases to only test expected partial software behaviors under constraint of testing execution time and cost. Obviously, aCT-CPNTP model is essentially constructed from a corresponding CT-CPNS model, because it just specifies parts of software behaviors which need to be tested. Therefore, we propose the formal definition of CT-CPNTP model based on the CT-CPNS definition.Definition 5.
ACT-CPNTP is a triple (CT-CPNS, PTP, ΣTP):(1)
CT-CPNS is a CT-CPNS model;(2)
PTP=PS∪{ph}, {ph} is thecoverage verdict place, and onlycoveredtoken can appear in this place;(3)
ΣTP=ΣS∪{covered}.InCT-CPNTP model,ph is always the postset of an output transition and used as the termination place in that model. If acoveredtoken appears inph place, it indicates that, based on a given initial marking, a generated test sequence just corresponds to an execution path of behaviors specified in the test purpose model. Thus, we need to add some necessary guard functions towards input or output transitions in the test purpose model to guarantee such behavior path be executed as expected. It is well demonstrated in Section 5.4 through the practical test selection to a file sharing software system.


### 5.2. Test Case Modeling

Several modeling constraints should be fulfilled inCT-CPNTC modeling. CT-CPNTC models should have only one input transition enabled at each step. Besides, they should be deterministic and every feasible trace should have finite length; otherwise, the test execution based on this model cannot terminate in finite steps with the definite testing results.Definition 6.
ACT-CPNTC is a triple (CPN, PTC, TTC), where(1)
CPN is a basic colored Petri nets model;(2)
PTC=P, PTC=PTCI∪PTCO∪PTCTO∪PTCV: PTCI is the set ofinput places; PTCO is the set ofobservable places; PTCTO is the set oftest oracle places; PTCV is the set oftest verdict places; each pair of them had no intersections;(3)
TTC=T, TTC=TTCI∪TTCO∪TTCδ∪TTCV: TTCI is the set ofinput transitions; TTCO is the set ofoutput transitions; TTCδ is the set ofsuspension transitions; TTCV is the set oftest verdict transitions; each pair of them had no intersections either;(4)
CT-CPNTC has finite behavior and is deterministic;(5)
CT-CPNTC has at most one input transition enabled in each step; that is, ¬∃M:M→(t1,b1)∧M→(t2,b2), t1∈TTCI∧t2∈TTCI.It should be noted that, in the test verdict places, only three kinds of token data can appear, that is,pass/fail/covered tokens. Apass token indicates that current test execution step is successfully passed; afail token indicates an implementation fault with current test execution step and results in the nonconformance decision; acovered token indicates that current test execution step covers that behaviors specified in test purpose model.CT-CP
N
TC models could facilitate the actual test execution for their better feasibility and readability, because they not only prescribe the test sequences from the data-dependent control flow of the system behaviors but also provide necessary and definite test oracles for determining the conformance relation.


### 5.3. Test Selection via Synchronized Model Simulation

To develop a test purpose model oriented IOCO test selection method, we need considering simulation paths inCT-CPNS model and CT-CPNTP model at the same time. The reason is that the simulation in the CT-CPNS model reflects actual execution paths of a software system, including real input and output data, which is the basis of test case generation. However, the simulation in the CT-CPNTP model conducts to select expected execution paths among all enabled paths. Thus, test generation scope is well constrained into those software behaviors we want to test does not consider other behaviors which are not specified in test purpose models. To accomplish such goal, the CT-CPNS model and the CT-CPNTP model should simulate in a synchronized way. Specifically, under guidance of PN-ioco relation, given an initial marking MS in CT-CPNS model and an initial marking MTP in CT-CPNTP model, the IOCO test selection method selects feasible and expected test sequences from the set of SPtrace(MS∥MTP) in order to cover behaviors specified in test purpose models; that is, corresponding enabled transitions in these two models are fired in a synchronized way according to different test generation rules towards different kinds of transitions. Meanwhile, the IOCO test selection method also presents explicit way to decide the conformance relation via test output and test oracle and indicate whether the test purpose is covered. Finally, if no further transitions could fire, that is, a termination marking is reached, the synchronized simulation procedure will terminate. If this final marking represents a valid termination of test purpose directed system behavioral execution, a final CT-CPNTC test case model covering specific test purpose is generated. Otherwise, if this final marking happens to stand for an invalid deadlock scenario, we need to improve the accuracy of both models and perform the synchronized simulation procedure again.Rule 1 (synchronized firing rule to input transition).
∃
t
∈
T
S
I and t∈TTPI, (t,bS)∈BES and (t,bTP)∈BETP are all enabled: generating t∈TTCI and ∀p∈{p∈PSI∣p∈pre(t)}:p∈PTCI, keeping token data in M(p), and generating a new internal place p′∈PTCE∣p′=post(t).
Firing(t,bS) and (t,bTP), that is, M(p′)={M∣M(p)→(t,bS)}, to accomplish a synchronized firing of input transitions.Rule 2 (synchronized firing rule to internal transition).
∃
t
∈
T
S
E and t∈TTPE, (t,bS)∈BES and (t,bTP)∈BETP are all enabled, if these two internal transitions could be fired to produce the same token data, then just fire them to accomplish a synchronized firing of internal transitions. Otherwise, fire (t,bS) time after time until t∈TTPE; that is, certain internal transition appearing only in the CT-CPNS model should be firstly fired several times before reaching the state that synchronized internal transition appearing in both CT-CPNS model and CT-CPNTP model is able to execute. However, such internal behaviors do not need to be handled by test case models.Rule 3 (synchronized firing rule to output transition).
∃
t
∈
T
S
O and t∈TTPO, (t,bS)∈BES and (t,bTP)∈BETP are all enabled: generating t∈TTCO and ∀p∈{p∈PSO∣p∈post(t)}:p∈PTCO.
If∃p∈{p∈PSE∣p∈post(t)}, we generate a new internal place p′∈PTCE∣p′=post(t).
Firing(t,bS) and (t,bTP) to accomplish a synchronized firing of output transitions and constructing a test verdict unit for every p∈PTCO are as follows:(i)
generatingq∈PTCTO, tv∈TTCV, pv∈PTCV: {pre(tv)=p∪q} and {post(tv)=pv}; M(q)=M(p), where M(q) records the test oracle data with respect to p;(ii)
generatinga∈(tv,pv), r=pre(tv)(r∈PTCO), and, without loss of generality, E(a) could be specified as follows: if M(r)=M(q), then 1′pass+ 1′covered else 1′fail; that is, if observed test output in M(r) is the same as the test oracle data in M(q), and test purpose is definitely covered, apass token and acovered token are both generated into the test verdict place pv;(iii)
connectingt∈TTCO with newly generated internal place or existing observable place, that is, r∈PTCE∪PTCO∣r=pre(t) to keep the connectivity of current test case model.Rule 4 (adding suspension transition).
Consider∃p∈PTCI, if quiescence is allowed, adding a suspension transition withp; that is, t∈TTCδ:p=pre(t)∧p=post(t).Given sets of initial markingsMS and MTP, through applying a suitable rule of aforesaid four test generation rules step by step, CT-CPNTC models covering specific test purpose are generated for testing corresponding software behaviors. Besides, it is guaranteed that the scenario never exists where transitions in CT-CPNTP model are enabled but related transitions in CT-CPNS model are not enabled, because a CT-CPNTP model is constructed from the corresponding CT-CPNS model. Furthermore, based on above test selection method, each SPtrace has finite length, so the test selection algorithm is terminated in finite steps with generating a CT-CPNTP model that has finite behaviors for practical test executions.Two more aspects should be noted. First,CT-CPN models are not modified with new kinds of model elements, and modeling constraints are just used to avoid generating infeasible traces for testing scenarios. So, the semantic rules defined in [10] are all kept in CT-CPN models; that is, we still use its original enabling rules and occurrence rules to generate CT-CPNTC test case models. Second, this test selection approach can be applied into the hierarchical CPN model without modification. The reason comes from two aspects: first, a hierarchical CPN model could definitely be unfolded to a behavioral equivalent nonhierarchical CPN model, and, then, test case selection process just utilizes ordinary simulation techniques which could be applied into hierarchical or nonhierarchical CPN models without differences. Thus, our test selection method has better scalability to deal with most of actual software behavior models.We could compare the computation cost in test purpose oriented test selection methods. In context of LTS, the state space produced by synchronous product of two LTS models tends to grow exponentially, which needs enormous even unpractical computation resources to generate suitable test cases. But, in context of CPN, synchronized model simulation based selection approach is irrespective of their model scale, so it just needs linear computation cost to produce feasible test cases. The effectiveness and practicability of our test selection method are enhanced with better scalability.


### 5.4. An Example: File Sharing Software System

We now apply the test purpose oriented IOCO test selection method into a file sharing software system to illustrate its feasibility and effectiveness. TheCT-CPNS model is presented in Figure 2, and one example CT-CPNTP model is presented in Figure 3. Through synchronized simulating of such two models, a CT-CPNTC model is generated and shown in Figure 4.Figure 2
TheCT-CPNS model of the file sharing software system.Figure 3
CT-CP
N
TP model of file sharing software system.Figure 4
CT-CP
N
TC model of file sharing software system.In this file sharing software system, peer nodes that have same functionalities could share the same resource file via network. The file is composed of several file segments which are identified as [SN, DATA]. When a peer node receives a file segment request (req), it searches such data segment from its data segment sets (DATASET) according to the segment number (SN) in request packet. If this peer node gets the requested data segment (DATAENTRY), it immediately sends the segment to the requesting peer node. While as a peer node receives a requested file segment, it stores this segment data into data segment sets firstly and goes on requesting new file segments which this peer does not have yet. In itsCT-CPNS model,rv/sd/set are observable places.recv is an input transition to specify the receiving of segment request or data.send/newreq are output transitions to specify sending segment data, storing segment data and requesting new file segment, respectively. For example, Ifsend fires, we could observe which packet is sent according to the tokens insd. The rest are internal places and transitions. In particular, the placesp stores the total set of segment number beforehand to help to choose which segment should be requested. In this way, necessary external behaviors of a system for its conformance testing are modeled accurately. However, in system modeling practice, the selection of observable places should also consider the actual observation points in the actual test execution, such as the points of control and observation [1].In Figure3, we present a test purpose CT-CPNTP model as a representative. This test purpose focuses on the function that whether a peer node could get the requested date segment from its data segment sets according to the segment number (constrained by the guard function [n=(#1en)]), when it receives a file segment request (constrained by the guard function [(#1p)=req]). If acoveredtoken appears inph place, it indicates that generated test sequence just covers the behaviors specified in this test purpose model. The CT-CPNTC model in Figure 4 is used to check whether a peer node gets the requested date segment from its data segment sets according to the segment number. The detailed test selection procedure is discussed as follows.(i)
Initial marking is assigned asMS(rv)={1′(req,2,“”)}, MS(sp)={[1,2,3,4]}, MS(set)={[(1,“one”),(2,“two”)]}; MTP(rv)={1′(req,2,“”)}, MTP(set)={[(2,“two”)]}.(ii)
Rule1 is applied to deal with input transitionrecv. This transition could be fired as (recv,{p=(req,2,“”)}) in a synchronized execution in both models. A new internal placesn is added as the postset ofrecv and MTC(rv)={1′(req,2,“”)}.(iii)
Rule2 is applied to deal with internal transitionsearch. In the CT-CPNS model, this transition relates two enabled scenarios, that is, (search, {n=2,ds=[(1,“one”),(2,“two”)]}) and (search, {n=2,ds=[(2,“two”),(1,“one”)]}), while, in the CT-CPNTP model, it only relates one enabled scenario, that is, (search, {n=2,en=(2,“two”)}). Thus, we firesearch in CT-CPNS model twice, where at the first time it is fired independently, and in the second time it is synchronized fired with that in the CT-CPNTP model. Consider MS(nd)=MTP(nd)={(2,“two”)}.(iv)
Rule3 is applied to deal with output transitionsend. This transition could be fired as (send, {n=2,d=“two”}) and (send, {en=(2,“two”)}) in a synchronized execution in each model and get MS(sd)={(rep,2,“two”)}, MTP(ph)={covered}, which indicates that the test purpose covered sequence is executed. The output transitionsend and its postset observable placear are both generated in CT-CPNTC model. Furthermore, its test oracle placerr, test verdict transitionvt, and test verdict placevd are all generated as an integrated test verdict unit for validating whether the actual output data is the same with the test oracle data. Consider MTC(rr)=MS(sd)={(rep,2,“two”)}. Finally, we need to relate the output transitionsend with internal placesn, that is, pre(send) =sn, to keep the connectivity of generated CT-CPNTC model.(v)
Rule4 is applied to add a suspension transition towards the input transitionrv, which allows for waiting tosend the data packet in a quiescence scenario.Using above test case model, we perform actual test executions to further illustrate feasibility and effectiveness of our test selection method. We program eight software implementations of the file sharing system with preinjected errors to act as SUT.In Table1, software implementations description and testing results are all listed. (1) i1 passes this test case, so it conforms to the specification model in Figure 2. (2) i2, i3, and i6 have fatal errors, respectively, which this test purpose just covers, so they do not pass this test case wherefail token appears in test case executions. (3) i4 and i5 pass the test case, but the fact is that error behaviors in i4 and i5 are not tested at all by this test case. Test purpose model in Figure 3 does not contain such behaviors; thus definitely the generated test case model does not aim to test these implementation errors. (4) i7 only implements partial functions; that is, it does not support segment retrieval. However, this function is just to be tested by this test case, so i7 does not pass as we do not observe the output segment data packet in actual test execution. Compared with basic IOCO relation definition, i7 does not conform to the specification according to PN-ioco relation, so partially correct implementations are no longer determined with conformance. (5) i8 passes this test case, because the test case does not touch such segment storage functionality.Table 1
System implementations and test results.
(a)
Software implementations
Number
Type
Description
i1
Totally correct
Implementing all functions correctly
i2
Faulty
Error on sending request packet
i3
Faulty
Error on matching segment number
i4
Faulty
Error on storing segment data
i5
Faulty
Error on calculating the new segment number
i6
Faulty
Error on parsing received segment packet
i7
Partially correct
Not supporting segment retrieval
i8
Partially correct
Not supporting segment storage
(b)
Testing results
i1
i2
i3
i4
i5
i6
i7
i8
Pass
Fail
Fail
Pass
Pass
Fail
Fail
PassFrom the above analysis, we could see that test case models generated using our test selection method are quite feasible for guiding actual test execution intuitively and also effective for finding various implementation faults. According to testing results, conformance relation between a specific implementation and its specification model could be accurately determined.


## 5.1. Test Purpose Modeling

Test purpose is utilized to specify parts of software functional behaviors; for example, in the network based software systems, sending request packets, receiving data packets, or updating local key data structure could be modeled as a test purpose each. In order to promote the pertinence of testing large-scale software systems, test purpose models should participate in test generation process, since it can constrain the scope of test generation; that is, it just selects finite and indispensable test cases to only test expected partial software behaviors under constraint of testing execution time and cost. Obviously, aCT-CPNTP model is essentially constructed from a corresponding CT-CPNS model, because it just specifies parts of software behaviors which need to be tested. Therefore, we propose the formal definition of CT-CPNTP model based on the CT-CPNS definition.Definition 5.
ACT-CPNTP is a triple (CT-CPNS, PTP, ΣTP):(1)
CT-CPNS is a CT-CPNS model;(2)
PTP=PS∪{ph}, {ph} is thecoverage verdict place, and onlycoveredtoken can appear in this place;(3)
ΣTP=ΣS∪{covered}.InCT-CPNTP model,ph is always the postset of an output transition and used as the termination place in that model. If acoveredtoken appears inph place, it indicates that, based on a given initial marking, a generated test sequence just corresponds to an execution path of behaviors specified in the test purpose model. Thus, we need to add some necessary guard functions towards input or output transitions in the test purpose model to guarantee such behavior path be executed as expected. It is well demonstrated in Section 5.4 through the practical test selection to a file sharing software system.


## 5.2. Test Case Modeling

Several modeling constraints should be fulfilled inCT-CPNTC modeling. CT-CPNTC models should have only one input transition enabled at each step. Besides, they should be deterministic and every feasible trace should have finite length; otherwise, the test execution based on this model cannot terminate in finite steps with the definite testing results.Definition 6.
ACT-CPNTC is a triple (CPN, PTC, TTC), where(1)
CPN is a basic colored Petri nets model;(2)
PTC=P, PTC=PTCI∪PTCO∪PTCTO∪PTCV: PTCI is the set ofinput places; PTCO is the set ofobservable places; PTCTO is the set oftest oracle places; PTCV is the set oftest verdict places; each pair of them had no intersections;(3)
TTC=T, TTC=TTCI∪TTCO∪TTCδ∪TTCV: TTCI is the set ofinput transitions; TTCO is the set ofoutput transitions; TTCδ is the set ofsuspension transitions; TTCV is the set oftest verdict transitions; each pair of them had no intersections either;(4)
CT-CPNTC has finite behavior and is deterministic;(5)
CT-CPNTC has at most one input transition enabled in each step; that is, ¬∃M:M→(t1,b1)∧M→(t2,b2), t1∈TTCI∧t2∈TTCI.It should be noted that, in the test verdict places, only three kinds of token data can appear, that is,pass/fail/covered tokens. Apass token indicates that current test execution step is successfully passed; afail token indicates an implementation fault with current test execution step and results in the nonconformance decision; acovered token indicates that current test execution step covers that behaviors specified in test purpose model.CT-CP
N
TC models could facilitate the actual test execution for their better feasibility and readability, because they not only prescribe the test sequences from the data-dependent control flow of the system behaviors but also provide necessary and definite test oracles for determining the conformance relation.


## 5.3. Test Selection via Synchronized Model Simulation

To develop a test purpose model oriented IOCO test selection method, we need considering simulation paths inCT-CPNS model and CT-CPNTP model at the same time. The reason is that the simulation in the CT-CPNS model reflects actual execution paths of a software system, including real input and output data, which is the basis of test case generation. However, the simulation in the CT-CPNTP model conducts to select expected execution paths among all enabled paths. Thus, test generation scope is well constrained into those software behaviors we want to test does not consider other behaviors which are not specified in test purpose models. To accomplish such goal, the CT-CPNS model and the CT-CPNTP model should simulate in a synchronized way. Specifically, under guidance of PN-ioco relation, given an initial marking MS in CT-CPNS model and an initial marking MTP in CT-CPNTP model, the IOCO test selection method selects feasible and expected test sequences from the set of SPtrace(MS∥MTP) in order to cover behaviors specified in test purpose models; that is, corresponding enabled transitions in these two models are fired in a synchronized way according to different test generation rules towards different kinds of transitions. Meanwhile, the IOCO test selection method also presents explicit way to decide the conformance relation via test output and test oracle and indicate whether the test purpose is covered. Finally, if no further transitions could fire, that is, a termination marking is reached, the synchronized simulation procedure will terminate. If this final marking represents a valid termination of test purpose directed system behavioral execution, a final CT-CPNTC test case model covering specific test purpose is generated. Otherwise, if this final marking happens to stand for an invalid deadlock scenario, we need to improve the accuracy of both models and perform the synchronized simulation procedure again.Rule 1 (synchronized firing rule to input transition).
∃
t
∈
T
S
I and t∈TTPI, (t,bS)∈BES and (t,bTP)∈BETP are all enabled: generating t∈TTCI and ∀p∈{p∈PSI∣p∈pre(t)}:p∈PTCI, keeping token data in M(p), and generating a new internal place p′∈PTCE∣p′=post(t).
Firing(t,bS) and (t,bTP), that is, M(p′)={M∣M(p)→(t,bS)}, to accomplish a synchronized firing of input transitions.Rule 2 (synchronized firing rule to internal transition).
∃
t
∈
T
S
E and t∈TTPE, (t,bS)∈BES and (t,bTP)∈BETP are all enabled, if these two internal transitions could be fired to produce the same token data, then just fire them to accomplish a synchronized firing of internal transitions. Otherwise, fire (t,bS) time after time until t∈TTPE; that is, certain internal transition appearing only in the CT-CPNS model should be firstly fired several times before reaching the state that synchronized internal transition appearing in both CT-CPNS model and CT-CPNTP model is able to execute. However, such internal behaviors do not need to be handled by test case models.Rule 3 (synchronized firing rule to output transition).
∃
t
∈
T
S
O and t∈TTPO, (t,bS)∈BES and (t,bTP)∈BETP are all enabled: generating t∈TTCO and ∀p∈{p∈PSO∣p∈post(t)}:p∈PTCO.
If∃p∈{p∈PSE∣p∈post(t)}, we generate a new internal place p′∈PTCE∣p′=post(t).
Firing(t,bS) and (t,bTP) to accomplish a synchronized firing of output transitions and constructing a test verdict unit for every p∈PTCO are as follows:(i)
generatingq∈PTCTO, tv∈TTCV, pv∈PTCV: {pre(tv)=p∪q} and {post(tv)=pv}; M(q)=M(p), where M(q) records the test oracle data with respect to p;(ii)
generatinga∈(tv,pv), r=pre(tv)(r∈PTCO), and, without loss of generality, E(a) could be specified as follows: if M(r)=M(q), then 1′pass+ 1′covered else 1′fail; that is, if observed test output in M(r) is the same as the test oracle data in M(q), and test purpose is definitely covered, apass token and acovered token are both generated into the test verdict place pv;(iii)
connectingt∈TTCO with newly generated internal place or existing observable place, that is, r∈PTCE∪PTCO∣r=pre(t) to keep the connectivity of current test case model.Rule 4 (adding suspension transition).
Consider∃p∈PTCI, if quiescence is allowed, adding a suspension transition withp; that is, t∈TTCδ:p=pre(t)∧p=post(t).Given sets of initial markingsMS and MTP, through applying a suitable rule of aforesaid four test generation rules step by step, CT-CPNTC models covering specific test purpose are generated for testing corresponding software behaviors. Besides, it is guaranteed that the scenario never exists where transitions in CT-CPNTP model are enabled but related transitions in CT-CPNS model are not enabled, because a CT-CPNTP model is constructed from the corresponding CT-CPNS model. Furthermore, based on above test selection method, each SPtrace has finite length, so the test selection algorithm is terminated in finite steps with generating a CT-CPNTP model that has finite behaviors for practical test executions.Two more aspects should be noted. First,CT-CPN models are not modified with new kinds of model elements, and modeling constraints are just used to avoid generating infeasible traces for testing scenarios. So, the semantic rules defined in [10] are all kept in CT-CPN models; that is, we still use its original enabling rules and occurrence rules to generate CT-CPNTC test case models. Second, this test selection approach can be applied into the hierarchical CPN model without modification. The reason comes from two aspects: first, a hierarchical CPN model could definitely be unfolded to a behavioral equivalent nonhierarchical CPN model, and, then, test case selection process just utilizes ordinary simulation techniques which could be applied into hierarchical or nonhierarchical CPN models without differences. Thus, our test selection method has better scalability to deal with most of actual software behavior models.We could compare the computation cost in test purpose oriented test selection methods. In context of LTS, the state space produced by synchronous product of two LTS models tends to grow exponentially, which needs enormous even unpractical computation resources to generate suitable test cases. But, in context of CPN, synchronized model simulation based selection approach is irrespective of their model scale, so it just needs linear computation cost to produce feasible test cases. The effectiveness and practicability of our test selection method are enhanced with better scalability.


## 5.4. An Example: File Sharing Software System

We now apply the test purpose oriented IOCO test selection method into a file sharing software system to illustrate its feasibility and effectiveness. TheCT-CPNS model is presented in Figure 2, and one example CT-CPNTP model is presented in Figure 3. Through synchronized simulating of such two models, a CT-CPNTC model is generated and shown in Figure 4.Figure 2
TheCT-CPNS model of the file sharing software system.Figure 3
CT-CP
N
TP model of file sharing software system.Figure 4
CT-CP
N
TC model of file sharing software system.In this file sharing software system, peer nodes that have same functionalities could share the same resource file via network. The file is composed of several file segments which are identified as [SN, DATA]. When a peer node receives a file segment request (req), it searches such data segment from its data segment sets (DATASET) according to the segment number (SN) in request packet. If this peer node gets the requested data segment (DATAENTRY), it immediately sends the segment to the requesting peer node. While as a peer node receives a requested file segment, it stores this segment data into data segment sets firstly and goes on requesting new file segments which this peer does not have yet. In itsCT-CPNS model,rv/sd/set are observable places.recv is an input transition to specify the receiving of segment request or data.send/newreq are output transitions to specify sending segment data, storing segment data and requesting new file segment, respectively. For example, Ifsend fires, we could observe which packet is sent according to the tokens insd. The rest are internal places and transitions. In particular, the placesp stores the total set of segment number beforehand to help to choose which segment should be requested. In this way, necessary external behaviors of a system for its conformance testing are modeled accurately. However, in system modeling practice, the selection of observable places should also consider the actual observation points in the actual test execution, such as the points of control and observation [1].In Figure3, we present a test purpose CT-CPNTP model as a representative. This test purpose focuses on the function that whether a peer node could get the requested date segment from its data segment sets according to the segment number (constrained by the guard function [n=(#1en)]), when it receives a file segment request (constrained by the guard function [(#1p)=req]). If acoveredtoken appears inph place, it indicates that generated test sequence just covers the behaviors specified in this test purpose model. The CT-CPNTC model in Figure 4 is used to check whether a peer node gets the requested date segment from its data segment sets according to the segment number. The detailed test selection procedure is discussed as follows.(i)
Initial marking is assigned asMS(rv)={1′(req,2,“”)}, MS(sp)={[1,2,3,4]}, MS(set)={[(1,“one”),(2,“two”)]}; MTP(rv)={1′(req,2,“”)}, MTP(set)={[(2,“two”)]}.(ii)
Rule1 is applied to deal with input transitionrecv. This transition could be fired as (recv,{p=(req,2,“”)}) in a synchronized execution in both models. A new internal placesn is added as the postset ofrecv and MTC(rv)={1′(req,2,“”)}.(iii)
Rule2 is applied to deal with internal transitionsearch. In the CT-CPNS model, this transition relates two enabled scenarios, that is, (search, {n=2,ds=[(1,“one”),(2,“two”)]}) and (search, {n=2,ds=[(2,“two”),(1,“one”)]}), while, in the CT-CPNTP model, it only relates one enabled scenario, that is, (search, {n=2,en=(2,“two”)}). Thus, we firesearch in CT-CPNS model twice, where at the first time it is fired independently, and in the second time it is synchronized fired with that in the CT-CPNTP model. Consider MS(nd)=MTP(nd)={(2,“two”)}.(iv)
Rule3 is applied to deal with output transitionsend. This transition could be fired as (send, {n=2,d=“two”}) and (send, {en=(2,“two”)}) in a synchronized execution in each model and get MS(sd)={(rep,2,“two”)}, MTP(ph)={covered}, which indicates that the test purpose covered sequence is executed. The output transitionsend and its postset observable placear are both generated in CT-CPNTC model. Furthermore, its test oracle placerr, test verdict transitionvt, and test verdict placevd are all generated as an integrated test verdict unit for validating whether the actual output data is the same with the test oracle data. Consider MTC(rr)=MS(sd)={(rep,2,“two”)}. Finally, we need to relate the output transitionsend with internal placesn, that is, pre(send) =sn, to keep the connectivity of generated CT-CPNTC model.(v)
Rule4 is applied to add a suspension transition towards the input transitionrv, which allows for waiting tosend the data packet in a quiescence scenario.Using above test case model, we perform actual test executions to further illustrate feasibility and effectiveness of our test selection method. We program eight software implementations of the file sharing system with preinjected errors to act as SUT.In Table1, software implementations description and testing results are all listed. (1) i1 passes this test case, so it conforms to the specification model in Figure 2. (2) i2, i3, and i6 have fatal errors, respectively, which this test purpose just covers, so they do not pass this test case wherefail token appears in test case executions. (3) i4 and i5 pass the test case, but the fact is that error behaviors in i4 and i5 are not tested at all by this test case. Test purpose model in Figure 3 does not contain such behaviors; thus definitely the generated test case model does not aim to test these implementation errors. (4) i7 only implements partial functions; that is, it does not support segment retrieval. However, this function is just to be tested by this test case, so i7 does not pass as we do not observe the output segment data packet in actual test execution. Compared with basic IOCO relation definition, i7 does not conform to the specification according to PN-ioco relation, so partially correct implementations are no longer determined with conformance. (5) i8 passes this test case, because the test case does not touch such segment storage functionality.Table 1
System implementations and test results.
(a)
Software implementations
Number
Type
Description
i1
Totally correct
Implementing all functions correctly
i2
Faulty
Error on sending request packet
i3
Faulty
Error on matching segment number
i4
Faulty
Error on storing segment data
i5
Faulty
Error on calculating the new segment number
i6
Faulty
Error on parsing received segment packet
i7
Partially correct
Not supporting segment retrieval
i8
Partially correct
Not supporting segment storage
(b)
Testing results
i1
i2
i3
i4
i5
i6
i7
i8
Pass
Fail
Fail
Pass
Pass
Fail
Fail
PassFrom the above analysis, we could see that test case models generated using our test selection method are quite feasible for guiding actual test execution intuitively and also effective for finding various implementation faults. According to testing results, conformance relation between a specific implementation and its specification model could be accurately determined.


## 6. Proof of Soundness and Test Purpose Coverage

The conformance relation between a software implementationii and its specification modelss is determined through test executions, specified asii PN-iocoss⇔ii passTS. If all test cases in completer setTS are passed, “ii PN-iocoss” is consequently determined. However, in practical conformance testing, generating all test cases in the TS is almost infeasible. Moreover, conformance testing just aims to find nonconformance faults rather than to completely prove the conformance. Thus, a weaker requirement is usually considered; that is, as long as the implementation does not pass one test case, it definitely does not conform to its specification. This weaker requirement corresponds to the left-to-right implication ofii PN-iocoss⇔ii passTS and is referred as the soundness of test case generation approach.Theorem 7.
Letss∈CT-CPNS be a specification model, and tp∈CT-CPNTP a test purpose model; let TS be a complete set of test cases that generated fromss andtp with our test selection algorithm, that is,TestSel; let CT-CPNS×CT-CPNTP→CT-CPNTC be the test case selecting function that satisfiesTestSel(ss,tp)⊆TS; thenTestSel is sound forss with respect to PN-ioco.Proof.
Supposing∃ii∈CT-CPNI with corresponding ss∈CT-CPNS, ∃tp∈CT-CPNTP and ∃tt∈TestSel(ss,tp) satisfyingnot (ii pass tt) andii PN-ioco ss, then
not (ii pass tt)
⇒
∃
e
∈
M
(
p
)
,
p
∈
P
TS
V
,
e
∈
{
f
a
i
l
}; [afail token appears in the test verdict placep]
⇒
∃
r
∈
P
TS
O
∧
∃
q
∈
P
TS
TO
,
M
(
r
)
≠
M
(
q
); [token data in the observable place r and its coupled test oracle place q are different]
⇒
∃
σ
∈  SPtrace(MS): outtoken(MI fires σ) ≠ outtoken(MS fires σ), where M(r)⊆ (MI fires σ) and M(q)⊆ (MS fires σ). [trace σ results in unexpected output observations in the practical test execution].
Obviously, there exists a contradiction with the assumptionii PN-iocoss. Therefore, we could conclude that if one test case does not pass, that is,not (ii pass tt), then,ii PN-iocoss does not hold definitely; that is,TestSel is sound forss andtp with respect to PN-ioco. However, it should be noted thatTestSel is not empty since SPtrace is always produced as a specific initial marking is assigned in actualss andtp models.It should be noted that asCT-CPNTP model is constructed from its corresponding CT-CPNS model, when valid specific initial markings are assigned in actual CT-CPNS model and CT-CPNTP model, at least one SPtrace exists definitely, so at least one test case model is generated. Given sets of initial markings, several test case models covering specific test purposes are generated consequently. That is, the special case where empty set ofTestSel(ss,tp) tends to be sound never exists.Based on the guarantee that test case selection is sound, we need further guarantee that test selection should cover test purposes; that is, any passed test case is definitely testing and only testing those software behaviors which are specified in corresponding test purpose models. The coverage towards test purpose is formally described ascover-pass relation as follows:∃
i
i
∈
CT-CP
N
I with related ss∈CT-CPNS, ∃tp∈CT-CPNTP, ∃tt∈TS(a complete set of test cases generated fromss andtp):ii cover-pass tt
→
ii exhibit tp:
ii cover-pass
t
t
=
def
ii pass tt and {covered}∈M(PTCV);
ii exhibit
t
p
=
def
∀
σ
∈ SPtrace(MTP):outtoken(MI fires σ)⊇ outtoken(MTP fires σ).From the angle of converse negative proposition in above relation, we could conclude that if a system implementation does not perform the behaviors which are specified in a test purpose model, it must not pass any test case generated using such test purpose model.Theorem 8.
Letss∈CT-CPNS be a specification model and tp∈CT-CPNTP a test purpose model; let TS be a complete set of test cases that generated fromss andtp with our test selection algorithm, that is,TestSel, let CT-CPNS×CT-CPNTP→CT-CPNTC be the test selecting function that satisfiesTestSel(ss,tp) ⊆TS; thenTestSel covers behaviors intp model.Proof.
∃
i
i
∈
CT-CP
N
I with corresponding ss∈CT-CPNS, ∃tp∈CT-CPNTP and ∃tt∈TestSel(ss,tp):
ii cover-pass tt
⇒
ii pass tt
∧
∃
p
∈
P
TC
V
,
{
c
o
v
e
r
e
d
}
∈
M
(
p
)
⇒
∀
p
′
∈
P
TC
V
,
{
f
a
i
l
}
∉
M
(
p
′
)
∧
∃
p
∈
P
TC
V
,
{
c
o
v
e
r
e
d
}
∈
M
(
p
) [onlypass andcovered token data can appear in the test verdict place]
⇒
∀
σ
∈ SPtrace(MS∥MTP): outtoken(MTP fires σ) ⊆ outtoken(MS fires σ) and  outtoken(MS fires σ) = outtoken(MI fires σ)
⇒
∀
σ
∈ SPtrace(MS∥MTP): outtoken(MTP fires σ) = outtoken(MI fires σ) [trace σ results in expected output observations in the practical test execution].


## 7. Conclusion

To make the best of advantages of the IOCO testing theory and the CPN modeling, we integrate them directly to develop a novel test purpose model oriented IOCO test selection method. Based on conformance testing oriented CPN models for specifying software functional behaviors and specific test purposes, respectively, guided by the CPN based IOCO relation, feasible test cases are generated using synchronized model simulation with the proof of the soundness of test generation and the coverage towards test purposes. Throughout practical test selection and test execution for a file sharing software system as a representative, the feasibility and effectiveness of the preceding test selection method are well elaborated.Our CPN model based IOCO test selection method has several advantages. First, conformance test cases are generated through synchronized simulation process with actual test input data and test oracles, so they are well feasible for guiding practical testing executions. Second, as synchronized model simulations with two CPN models are irrespective of their model scale, their effectiveness and practicability are enhanced with better scalability. Therefore, our CPN model based IOCO test selection method is promising and competent for validating the correctness of reactive network software systems more efficiently and more effectively.



---

*Source: 645235-2014-04-14.xml*