Anurag Dwarakanath
email: anurag.dwarakanath@accenture.com

Aruna Jankiti
email: jankiti.aruna@accenture.com

Minimum Number of Test Paths for Prime Path and other Structural Coverage Criteria

Keywords: Model Based Testing, Minimum Number of Test Paths, Prime Path Coverage, Minimum Flow

The software system under test can be modeled as a graph comprising of a set of vertices, V and a set of edges, E. Test Cases are Test Paths over the graph meeting a particular test criterion. In this paper, we present a method to achieve the minimum number of Test Paths needed to cover different structural coverage criteria. Our method can accommodate Prime Path, Edge-Pair, Simple & Complete Round Trip, Edge and Node coverage criteria. Our method obtains the optimal solution by transforming the graph into a flow graph and solving the minimum flow problem. We present an algorithm for the minimum flow problem that matches the best known solution complexity of O (|V | |E|). Our method is evaluated through two sets of tests. In the first, we test against graphs representing actual software. In the second test, we create random graphs of varying complexity. In each test we measure the number of Test Paths, the length of Test Paths, the lower bound on minimum number of Test Paths and the execution time.

Introduction

In model based testing, the software artifact describing the system under test (SUT) is abstracted through a model [START_REF] Ammann | Introduction to software testing[END_REF]. The model can be created from requirements, design or code [START_REF] Ammann | Introduction to software testing[END_REF]. Models are typically represented in the form of a graph, comprising of vertices and edges. Two special vertices are marked, the source vertex, s, and the sink vertex, t. The graph is then used to generate Test Cases. A Test Case consists of a Test Path, Test Data, and Expected Results. The Test Path is a path in the graph from s to t. The number of Test Paths needed to test the SUT is determined by the coverage criterion. For example, Node Coverage implies that the set of Test Paths should collectively visit all vertices in the graph. Similarly, Edge Coverage requires the Test Paths to visit all edges in the graph and Prime Path coverage requires the Test Paths to tour a particular set of paths. Prime Path coverage provides a better quality of coverage as it subsumes Node Coverage and Edge Coverage [START_REF] Ammann | Introduction to software testing[END_REF].

Given a particular coverage criterion, it is important to determine a small set of Test Paths which satisfy the criterion. The number and the overall length of Test Paths directly impacts the amount of time needed to manually execute the test cases. Finding the minimum number of Test Paths needed to satisfy a particular criterion is non-trivial even for the simplest case of node coverage. Using better coverage criterion like Prime Path complicates the problem further since even a small graph can have a large number of Prime Paths [START_REF] Kaminski | An evaluation of the minimal-mumcut logic criterion and prime path coverage[END_REF].

In this paper, we present a method to obtain the optimal solution for the minimum number of Test Paths for different structural coverage criteria. The contribution of our work includes a) a generic method for obtaining the minimal number of Test Paths for different structural coverage criteria; b) identification of a lower bound on the minimum number which the experimental results show to perform very well; c) a new method for computation of minimum number of Test Paths which matches the best known solution complexity.

The identification of the minimum number of Test Paths, although possible in polynomial time, requires a number of graph transformations. We thus test the applicability of our solution against a simple algorithm for Test Path generation. The tests compare the number and length of Test Paths identified and the algorithm execution time. These metrics are compared on a set of manually created graphs representing actual code and a set of randomly generated graphs.

The paper is structured as follows. We present the related work in Section 2. The method of generating the minimum Test Paths is presented in Section 3. We present the experimental results in Section 4 and conclude in Section 5.

Related Work

The input for the identification of minimum Test Paths is a directed graph G 1 = (V 1 , E 1 ), where V 1 represents the vertex set and E 1 represents the edge set. G 1 is typically a control flow graph of the SUT. G 1 may contain cycles. V 1 contains the source vertex, s, and the sink vertex, t. s conceptually depicts the point where the execution of a Test Case begins and t denotes the point where the execution ends. The in-degree of s is 0, and the out-degree of t is 0. We focus on the case where |s| = |t| = 1. There is no loss in generality since a graph with more than one s or t can be converted to a graph with a single s and a single t, by adding two new vertices, s , t with edges between s and every source, and edges between every sink and t .

A path is a sequence of vertices v 0 , . . . , v r with a sequence of edges e 0 , . . . , e (r-1) , where

e i = v i , v (i+1) , v i ∈ V 1 , e i ∈ E 1 ∀i. An s -t path
is a path where v 0 = s and v r = t. All Test Paths are thus s -t paths. A path, p is said to visit vertex k (or edge e) if k (or e) is in p. A path p is said to tour (or cover) a path q, if q is a sub-path of p. A path is simple if no vertex is visited more than once with the exception that the first and last nodes may be identical [START_REF] Ammann | Introduction to software testing[END_REF]. A Prime Path is a simple path that is not a sub-path of any other simple path [START_REF] Ammann | Introduction to software testing[END_REF].

A test requirement is a specific aspect that a Test Path satisfies. T R denotes the set of test requirements. For example, for Prime Path coverage, T R = set of Prime Paths. For Edge Coverage, T R = the set of edges, etc.

A simple solution approach for the generation of Test Paths that cover all Prime Paths has been presented in [START_REF] Ammann | Introduction to software testing[END_REF]. The solution 'extends' every Prime Path to visit s and t thus forming a Test Path. The algorithm does not attempt to minimize the number of Test Paths but is extremely fast in execution.

The problem of minimizing Test Paths for Prime Path coverage has been recently studied in [START_REF] Li | Better algorithms to minimize the cost of test paths[END_REF]. The authors formulate the problem as a variant of the shortest superstring problem, which is NP-complete [START_REF] Li | Better algorithms to minimize the cost of test paths[END_REF]. The authors then use known approximation algorithms to solve the problem. In our work, we formulate the problem such that the optimal solution is obtained in polynomial time.

While the work in [START_REF] Li | Better algorithms to minimize the cost of test paths[END_REF] specifically deals with Prime Paths, the problem of minimum Test Path to cover a given set of paths (not necessarily Prime Paths) has been studied earlier in [START_REF] Ntafos | On path cover problems in digraphs and applications to program testing[END_REF]. Here, the given graph, G 1 , is transformed into a flow network such that the minimum flow gives the minimum number of Test Paths. The authors use a generic algorithm for minimum flow. One such simple algorithm for minimum flow is the Decreasing Path algorithm [START_REF] Ciurea | Sequential and parallel algorithms for minimum flows[END_REF] The authors of [START_REF] Aho | Efficient algorithms for constructing testing sets, covering paths, and minimum flows[END_REF] tailor a minimum flow algorithm specifically for minimum Test Paths for node coverage leading to the currently best known solution complexity of O (|V | |E|). Our algorithm in this paper also achieves this complexity. However, our technique is different and is based on the concept of Decreasing Paths [START_REF] Ciurea | Sequential and parallel algorithms for minimum flows[END_REF]. The concept is similar to that of the Augmenting Path in the Ford-Fulkerson algorithm [START_REF] Ford | Flows in networks[END_REF] to find the maximum flow. The Augmenting Path concept is well studied and numerous explanatory material is available. This allows our algorithm based on the Decreasing Path to be easily understood and conceptually simple. Further, our method is generic and handles different coverage criteria including node coverage.

Table 1 summarizes the distinction of our method against related work. Our method to obtain the minimum number of Test Paths is presented below.

Generating the minimum number of Test Paths

Given a graph G 1 = (V 1 , E 1 ), we need to find the minimum number of Test Paths that cover the set of test requirements T R. We focus for the case of T R = set of Prime Paths of G 1 and cover other coverage criteria in section 3.6. The minimum Test Paths are identified through a series of steps as shown below.

1. First, the set of Prime Paths, P of G 1 is computed. We present a method to obtain the lower bound on the minimum number of Test Paths. [START_REF] Ntafos | On path cover problems in digraphs and applications to program testing[END_REF] removed cycles from the original graph, G 1 , instead of the transform graph, G 2 . This inaccuracy in [START_REF] Ntafos | On path cover problems in digraphs and applications to program testing[END_REF] can lead to incorrect results (refer Fig. 1). 4. G 3 is converted into a flow graph, G 4 , with new vertices and edges introduced. Every edge is annotated with lower bounds and capacities of flows.

2. G 1 is converted into a transform graph G 2 = (V 2 , E 2 ),
The minimum flow on G 4 is computed through a two-step process. First, G 4 is initialized with a feasible flow. We present a novel initialization algorithm in this paper. Second, the generic Decreasing Path algorithm [START_REF] Ciurea | Sequential and parallel algorithms for minimum flows[END_REF] is used to find the minimum flow. Our initialization algorithm ensures the Decreasing Path algorithm can compute with a complexity of O (|V | |E|).

The minimum flow in

G 4 is now interpreted as Test Paths in G 1 .
We detail each step of the process below. We will also use Fig. 2 as a running example to help explain the algorithms used.

Generating the set of Prime Paths

Algorithm 1 generates the set of test requirements T R (Prime Paths in this case). We use known methods ( [START_REF] Ammann | Introduction to software testing[END_REF] and [START_REF] Ammann | Coverage computation web applications[END_REF]) to compute the set of Prime Paths.

For the example graph in Fig. 2, there are 10 Prime Paths:

P = {p 0 = {s, 1, 3, 4, 5}, p 1 = {3, 4, 1, 2, t}, p 2 = {5, 4, 1, 2, t}, p 3 = {1, 3, 4, 1}, p 4 = {s, 1, 2, t}, p 5 = {3, 4, 1, 3}, p 6 = {5, 4, 1, 3}, p 7 = {4, 1, 3, 4}, p 8 = {5, 4, 5}, p 9 = {4, 5, 4}}.

Algorithm 1: Generating the set of Prime Paths

Input: Proof. Consider P T = {p 1 , p 2 , . . . , p n } to be a set of T ype T Prime Paths. Since each of these Prime Paths visits vertex t, the last node of every Prime Path p i ∈ P T is the vertex t. Now, consider an s -t path that tours p 1 . This s -t path cannot tour any other Prime Path of P T after touring p 1 since the vertex t has an out-degree of 0. Thus, there cannot be any path in the graph where more than 1 Prime Paths of P T can be toured simultaneously. Therefore, there would be at-least T ype T s -t paths to cover all Type T Prime Paths. Similarly, there would be atleast T ype S s -t paths to cover all T ype S Prime Paths. Thus the number of s-t paths that will cover all Prime Paths will be atleast as much as max (|T ype S|, |T ype T |).

G 1 = (V 1 , E 1 ), with {s, t} ∈ V 1 Output: Set of Prime Paths, P = {p 1 , p 2 , . . . , p n } 1 initialize P = {p 1 , p 2 , . . . , p n } = {e 1 , e 2 , . . . , e n }, ∀e i ∈ E 1 ; 2 while p i ∈ P ∀i is not explored do 3 if p i is not a cycle then

The categorization of the

Generating the Transform Graph

The Prime Paths are represented as vertices in a new graph, G 2 . Edges are placed between two vertices in G 2 if a path in G 1 can tour the two Prime Paths represented by the vertices. The problem of Prime Path coverage is thus transformed into a problem of node coverage (i.e. we want to identify s -t paths such that all vertices of G 2 are covered). The algorithm for generation of the transform graph is provided below.

Algorithm 2: Generation of the Transform Graph

Input:

G 1 , P Output: Transform Graph G 2 = (V 2 , E 2 ) 1 create new vertex s, t in V 2 ; create new vertex v i in V 2 ,
output G 2 = (V 2 , E 2 );
The Operator ∪ in Step 4 works as follows. Consider the case of p i = {4, 5, 4} and p j = {5, 4, 5}, then p i ∪ p j = {4, 5, 4, 5} by observing that the paths p i and p j have overlapping vertices. In case of no overlap, p i ∪ p j = {p i + {shortest path from the last node of p i to the first node of p j } + p j }. Checking for the shortest path in G 1 can be done using breadth first search with a complexity of O (E 1 ). Checking for the presence of a Prime Path in P ath ij (step 5) can be done in O (|P |). Thus, the transform graph can be computed in

O |P | 2 * max (|P |, |E 1 |) .
The transform graph of Fig. 2 is shown in Fig. 3.

An incomparable vertex set, I, is one where for every pair of vertices v i , v j ∈ I; v i does not reach v j . From Fig. 3, it can be visually seen that the three T ype T Prime Paths, p 1 , p 2 , p 4 , form an incomparable vertex set, i.e. I = {p 1 , p 2 , p 4 }. The maximum incomparable vertex set, I max equals the minimum number of Test Paths through Dilworth's theorem for acyclic directed graphs and the proof in [START_REF] Ntafos | On path cover problems in digraphs and applications to program testing[END_REF] for general graphs. From Lemma 1, |I max | ≥ |I|.

Removing Cycles

The transform graph, G 2 , may have cycles. The minimum flow algorithm works over a directed acyclic graph and thus the cycles need to be removed. We achieve this by replacing a cycle with a new vertex. All incoming edges of any node in the cycle become incoming edges of the new vertex. Similarly, any outgoing edge of any vertex in the cycle become outgoing edges of the new vertex. Algorithm 3 presents the generation of the acyclic transform graph.

Algorithm 3: Reduction of Cycles in Transform Graph

Input:

G 2 Output: Acyclic Transform Graph G 3 = (V 3 , E 3 ) 1 initialize V 3 = V 2 , E 3 = E 2 , G 3 = (V 3 , E 3 ); 2 while G 3 contains a cycle do 3 let p c = {v 1 , v 2 , . . . , v n , v 1 } be a cycle; 4 record vertices v i ∈ V 3 which have an edge in E 3 with vertices in p c ; 5 remove vertices {v 1 , v 2 , . . . , v n } from V 3 ; create new vertex v new in V 3 ; 6 foreach vertex v i ∈ p c do 7 if v i has an edge from vertex v k in G 2 where v k ∈ V 3 -p c then 8 remove edge (v k , v i ) from E 3 & create edge (v k , v new ) in E 3 ; 9 end 10 if v i has an edge to vertex v k in G 2 where v k ∈ V 3 -p c then 11 remove edge (v i , v k ) from E 3 & create edge (v new , v k ) in E 3 ;

Generating the Minimum Flow

The transform graph, G 3 , at this stage is a directed acyclic graph. We convert this graph into a flow graph. Each vertex v i ∈ V 3 -{s, t} is split into two vertices

v + i , v ++ i .
Let this new vertex set be represented as V 4 . New edges v + i , v ++ i are also added. All incoming edges of v i are made incoming edges of v + i and all outgoing edges of v i are made outgoing edges of v ++ i . Let this new edge set be represented as E 4 . Every edge (i, j) ∈ E 4 & i, j ∈ V 4 is associated with a lower bound (l ij ) for a flow and an edge capacity (c ij ) as follows:

l ij = 1 if (i, j) = v + i , v ++ i 0 otherwise c ij = |V 4 | 2 - 1
Let the resulting graph be represented as G 4 = (V 4 , E 4 , L, C), where L is the set of lower bounds and C is the set of capacities. The introduction of new vertices, new edges and the flow requirements are pictorially depicted in Fig. 5.

A feasible flow in the flow network is an assignment of a non-negative value, f ij for every edge such that the following conditions hold.

f ij ≥ l ij & f ij ≤ c ij , ∀ (i, j) ∈ E 4 & i, j ∈ V 4 (1)
i

f ij = j f ji , ∀ (i, j) ∈ E 4 & i, j ∈ V 4 -{s, t} (2)
The flow of the network, f , is defined as:

f = j f sj = i f it , ∀ (i, j) ∈ E 4 & i, j ∈ V 4 (3)
The minimum flow,f min , is the least amount of feasible flow possible.

A flow in the network G 4 can be mapped to an s -t path in G 1 . The flow conditions placed in G 4 ensures the edge v + i , v ++ i is chosen in at-least one flow. Since this corresponds to every vertex v i ∈ V 3 -{s, t}, the minimum flow will ensure every vertex of G 3 is covered. By expanding vertexes placed in lieu of cycles in G 3 , every vertex of G 2 is covered. This ensures that every Prime Path of G 1 is toured.

Every edge in G 4 is also annotated with a capacity, c ij , which represents the maximum flow that may be carried on the edge. The capacity is not directly interpretable from the Test Path perspective; however, the minimum flow algorithm requires the specification of a capacity. In the general case of computing the minimum flow in a network, the capacity determines if a feasible flow exists. In our case, we set the capacity in such a way that it guarantees a feasible flow.

Theorem 1. The capacity on an edge in G 4 can be set as |V4| 2 -1. Proof. Consider the graph G 3 . The maximum number of s -t paths possible on G 3 will be (|V 3 | -2). This is because, the maximum will occur when every vertex of G 3 -{s, t} leads to a new s -t path. Now, new vertices have been added in G 4 , but none of the new vertices will contribute to a new path over and above those that are possible in G 3 . Thus, the maximum capacity of every edge in G 4 can be set as ( Once the flow graph has been created, we determine the minimum flow through the technique similar to [START_REF] Ciurea | Sequential and parallel algorithms for minimum flows[END_REF].

|V 3 | -2). But since |V 4 | = 2 * |V 3 | -2 ⇒ (|V 3 | -2) = |V4| 2 -1.
| ర | ଶ െ 1 1 1 ା 1 ାା 0; | ర | ଶ െ 1 1; | ర | ଶ െ 1 0; | ర | ଶ െ 1
The minimum flow algorithm works in two steps, a) an initial flow is placed on the flow graph such that all flow requirements (1 & 2) are met; and b) the minimum flow is computed using the decreasing path algorithm. Using the algorithms for a) and b) as detailed in [START_REF] Ciurea | Sequential and parallel algorithms for minimum flows[END_REF]

G 4 = (V 4 , E 4 , L, C) Output: feasible flow f ij , ∀ (i, j) ∈ E 4 & i, j ∈ V 4 1 initialize f ij = 0, ∀ (i, j) ∈ E 4 & i, j ∈ V 4 ; 2 foreach vertex i ∈ V 4 -{s, t} do 3
find path, p s , from s to i using breadth-first-search; 4 find path, p t , from i to t using breadth-first-search; Proof. Consider a vertex, i, in G 3 . This vertex will now be represented by i + and i ++ in G 4 . A path from s to i ++ will cover the edge (i + , i ++ ) since i ++ is reachable only through i + . Thus, incrementing the flow along the path from s to i ++ will ensure that the flow condition of l ij = 1 for (i, j) = (i + , i ++ ) is met. By checking ∀i ∈ V 4 , ensures flow requirement (1) for all edges is met. The increments of the flow is done for every edge of a path from s to t. Consider the vertex i + in G 4 . Let it have m incoming edges. Since i + is created by splitting vertex i, i + will have 1 outgoing edge. Let vertex i + be part of an s -t path n number of times where 1 ≤ n ≤ |V4|

5 path, p = p s + p t ; 6 k = min {(f mn -l mn ) , ∀ (m, n) ∈ p}; 7 if k < 0 then
2 -1. The m incoming edges will be visited n times with each visit incrementing the flow by 1. Thus the sum of flows on the incoming edges will be n. Similarly, the outgoing edge will be visited n times and will also have a flow of n. Thus, by incrementing the flow of every edge of an s -t path ensures flow requirement (2) is met.

Breadth first search has a complexity of O(|E|). Therefore Algorithm 4 has a complexity of O (|E 4 ||V 4 |).

Once an initial flow is placed on the flow graph, the minimum flow is computed using the decreasing path algorithm.

Decreasing Path algorithm to find the minimum flow We use the generic Decreasing Path algorithm as detailed in [START_REF] Ciurea | Sequential and parallel algorithms for minimum flows[END_REF]. The algorithm is based on the Augmenting Path concept of the Ford-Fulkerson algorithm [START_REF] Ford | Flows in networks[END_REF]. The Decreasing Path concept can be stated as follows. Every edge in G 4 is termed as a forward edge. Let this set be called E f 4 . For every forward edge, a new backward edge is introduced; i.e. a forward edge of the form (i, j), will have a backward edge of the form (j, i). Let this set of backward edges be called E b 4 . For each backward edge, the lower bound, l ij , is set to 0 and the capacity, c ij is set to |V4| 2 -1. The residual capacity of an edge, r ij , ∀ (i, j) ∈ E f 4 ∪ E b 4 , is defined as follows:

r ij = f ij -l ij if (i, j) ∈ E f 4 c ij -f ij if (i, j) ∈ E b 4
A decreasing path is a path from s to t where the residual capacity of every edge is greater than 0. If a decreasing path visits a forward edge, then the flow on the edge can be reduced. If on the other hand, the decreasing path visits a backward edge, then the flow on the corresponding forward edge has to be increased. The flow in the graph will be minimum when no more decreasing paths can be found. The minimum flow is the optimal solution as proved in [START_REF] Ciurea | Sequential and parallel algorithms for minimum flows[END_REF].

The algorithm to compute the minimum flow is presented as Algorithm 5.

The complexity of the Decreasing Path algorithm can be determined using the technique in [START_REF] Ciurea | Sequential and parallel algorithms for minimum flows[END_REF]. Each reduction of the flow in the network will need O (|E 4 |) because of the path found through breadth first search. Since the maximum flow that may be initialized is For the running example, the minimum flow is computed as 3 which can be quite clearly observed from Fig. 4. The minimum flow incidentally equals the lower bound for the example.

Generating the Minimum Test Paths from the Minimum Flow

The minimum number of s -t paths to cover all the Prime Paths is the flow, f , in G 4 . The s -t paths in G 4 and the corresponding paths in G 1 are identified using Algorithm 6.

Steps 3 to 7 identify the paths corresponding to the minimum flow in G 3 . For the running example, the path G3 = {s, p 4 , t}, {s, v 3 , p 1 , t} and {s, p 0 , v 3 , p 2 , t}.

Vertices in path G3 which represent cycles in G 2 are replaced. In the running example, there are no cycles to be introduced in the first path {s, p 4 , t}. Replacing v 3 in the second path gives {s, p 3 , p 5 , v 2 , p 3 , p 1 , t}. Note that although v3 represents the cycle -{v 2 , p 3 , p 5 , v 2 }, it is replaced as {p 3 , p 5 , v 2 , p 3 } such that an edge exists between s and p 3 . Step 10 performs this operation. Replacing v 2 gives {s, p 3 , p 5 , p 7 , v 1 , p 6 , p 7 , p 3 , p 1 , t}. Replacing v 1 gives the path {s, p 3 , p 5 , p 7 , p 9 , p 8 , p 9 , p 6 , p 7 , p 3 , p 1 , t}. Similarly, after replacing the cycles in the third path, we get {s, p 0 , p 9 , p 8 , p 9 , p 6 , p 7 , p 9 , p 8 , p 9 , p 3 , p 5 , p 7 , p 9 , p 8 , p 9 , p 6 , p 7 , p 2 , t}. Note that the vertices p 9 and p 3 in the sub-path {p 9 , p 3 } of the third Test Path are not directly connected in G 2 . Similarly, the vertices p 7 and p 2 are not directly connected. This aspect of connectedness is taken care in step 13.

c = {v G2 1 , v G2 2 , . . . , v G2 1 }; 10 replace v G3 c with c = {v G2 j , v G2 j+1 , . . . , v G2 j } where v G3 c-1 is connected to v G2
As can be seen from the paths, redundancy exists. For example, the cycle {p 9 , p 8 , p 9 } is present 3 times in the third path. We remove this redundancy by replacing such cycles with the first node of the cycle (p 9 in this case) for all occurrences except the first (step 18). Also note that for the cycle {p 7 , p 9 , p 6 , p 7 } the sub-path {p 9 , p 6 } is occurring more than once. This implies the cycle can be again reduced to the first node of the cycle (step 22). Thus, the set of paths after removing redundancy is {s, p 4 , t}, {s, p 3 , p 5 , p 7 , p 9 , p 8 , p 9 , p 6 , p 7 , p 3 , p 1 , t}, {s, p 0 , p 9 , p 2 , t}.

The last step of the algorithm is to merge the Prime Paths to obtain the s -t paths on G 1 . This operation is performed by the operator ∪ and is as explained in Section 3.2.

Thus, the minimum s -t paths for the running example needed to cover all Prime Paths are {s, 1, 2, t},{s, 1, 3, 4, 1, 3, 4, 5, 4, 5, 4, 1, 3, 4, 1, 2, t} and {s, 1, 3 , 4, 5, 4, 1, 2, t}. Observe that the Test Paths are long in length. The length of the Test Paths are the number of edges and equals 27 in this example.

Other Coverage Criteria

Our method of identifying the minimum number of Test Paths is generic and can cater to all of the structural coverage criteria of [START_REF] Ammann | Introduction to software testing[END_REF] as shown below.

Edge-Pair Coverage Criterion For the Edge-Pair coverage criterion, the test requirement set, T R, is the set of all paths of length at-most 2. An edge-pair can be represented as a path {v i , v j , v k }, where (v i , v j ) & (v j , v k ) ∈ E. The minimum number of Test Paths such that T R is covered can be obtained directly from our method. Algorithm 1 will have to be modified to generate the set of edgepairs. Other algorithms can be used exactly as presented. Further, Lemma 1 and the Theorems hold. From Lemma 1, the lower bound on the minimum number of Test Paths would be max (|T ypeS|, |T ypeT |), where T ype S and T ype T are those test requirements that contain the vertex s and t respectively. Edge Coverage Criterion To handle Edge Coverage, there would be no need for algorithm 1 as the test requirements are directly available as E. The other algorithms can be used exactly as presented. Algorithm 2 represents every edge as a vertex in the flow network. Algorithm 3 reduces the graph to an acyclic one. The minimum flow computation using algorithms 4 and 5 with algorithm 6 will give the minimum number of Test Paths needed to cover every edge. Lemma 1 will equal the maximum of number of test requirements that contain s or t which in this case is the maximum of the out-degree of s and the in-degree of t.

Simple and Complete Round Trip Coverage Criterion

Node Coverage Criterion Node Coverage can be handled by using a sub-set of the algorithms in our method. We directly use algorithms 3 to 6 to obtain the minimum number of Test Paths for node coverage. Lemma 1 will equal the maximum of the number of test requirements that contain s or t which in this case will equal 1.

Experimental Results

We have evaluated our method through two sets of tests. In the first test we use 18 graphs representing actual open-source software1 as test inputs. Since these graphs were also used as test inputs in [START_REF] Li | Better algorithms to minimize the cost of test paths[END_REF], our results can be directly compared with that of [START_REF] Li | Better algorithms to minimize the cost of test paths[END_REF]. Tables 2 &3 provides the results of the first test.

The results show a significant reduction in the number of Test Paths generated over the methods of [START_REF] Ammann | Introduction to software testing[END_REF] and [START_REF] Li | Better algorithms to minimize the cost of test paths[END_REF]. Averaging over the 18 graphs, the number of Test Paths were reduced by 72.9% over the solution of [START_REF] Ammann | Introduction to software testing[END_REF]. The reduction varied from a minimum of 16.3% to a maximum of 89.9%. Comparing with [START_REF] Li | Better algorithms to minimize the cost of test paths[END_REF], the number of Test Paths from our solution reduced by 59.6% on average and varied from a minimum benefit of 0% to a maximum benefit of 91.4%.

Although our solution does not explicitly attempt to minimize the length of the Test Paths, the results show that in many cases, the Test Path length is reduced as well. The average reduction in the Test Path length on the 18 graphs was -9.4% over [START_REF] Ammann | Introduction to software testing[END_REF] (i.e. on average, the test path length increased) and 38.5% over [START_REF] Li | Better algorithms to minimize the cost of test paths[END_REF]. Note that in some cases, the minimization of the number of Test Paths has actually increased the length of the Test Paths.

The identification of the lower bound (Lemma 1) has performed exceedingly well and on average over the 18 graphs, was only 8.2% outside the true value.

The execution time of our method is significant with Algorithm 2 being the most costly. On average, the execution time of our method was 338 times that of [START_REF] Ammann | Introduction to software testing[END_REF]. In absolute terms, the average execution time was 3.6 minutes, but varied from a minimum of 5 ms to a maximum of 27.6 minutes.

In the second test, we created 4391 random graphs of varying complexity as test inputs. The Prime Paths of these graphs varied from 7 to 150. The number of Test Paths, the length of Test Paths and the execution time were recorded averaging over graphs of a particular Prime Path. The execution times were the II) of [START_REF] Li | Better algorithms to minimize the cost of test paths[END_REF] as our solution uses a single source and sink. b similarly maps to 84 in results (Table II) of [START_REF] Li | Better algorithms to minimize the cost of test paths[END_REF].

average of 5 runs over the same graph. The results are shown in Fig. 6. Similar to the first test, we see a significant improvement in terms of number of Test Paths. On average, our method reduced the number of Test Paths by 70.9%. The length of Test Paths were reduced by 2.7% on average. The lower bound was away from the true value by only 0.6% on average. On average, our method took 0.39 seconds to execute which was 105 times the execution time of [START_REF] Ammann | Introduction to software testing[END_REF].

Overall, our method of minimizing the number of Test Paths provides good results. To mitigate the concern of the increase in execution time, the quality of the lower bound can be exploited (for example attempting the minimization only when the solution from [START_REF] Ammann | Introduction to software testing[END_REF] is over 5 times the lower bound). II) of [START_REF] Li | Better algorithms to minimize the cost of test paths[END_REF].

  which leads to the solution in O |V | 2 |E| . However, the methodology in [8] has an inaccuracy which can lead to incorrect results. Consider the graphs in Fig. 1. The Prime Paths of Fig. 1(a) are {1, 2, 3} and {2, 2}. The technique in [8] makes the graph acyclic by introducing a new vertex 2 in place of the strongly connected component of 2 -2. The minimum flow analysis is then performed on the acyclic graph Fig. 1(b). This results in a minimum number of Test Paths as 1 the path being 1, 2 , 3. Replacing 2 , we get the path as 1, 2, 2, 3 to correspond to Fig. 1(a). However, the minimum number of paths to cover the Prime Paths is 2 -{1, 2, 3} and {1, 2, 2, 3}. Our method overcomes this inaccuracy by appropriately handling strongly connected components. Further, our solution of minimum Test Paths is computed in O (|V | |E|).

Fig. 1 .

 1 Fig. 1. (a) Graph with a cycle (b) reduced to an acyclic graph.

4

  if p i can be extended by edge e ∈ E 1 then 5 if e does not visit a vertex in p i then 6 p i + = e; 11 sort P in ascending order of size;12 for i = |P | to 1 do 13 if p i is not a sub-path of any other path in P then 14 add p i into P ; 15 end 16 end 17 output P ; We define four categories of Prime Paths. T ype S are those Prime Paths that visit the vertex s. T ype T are those that visit the vertex t. T ype C are those Prime Paths that are cycles, and T ype P are those that are simple paths and do not visit either s or t. In the given example, we have the following cardinality -|T ype S| = 2, |T ype T | = 3, |T ype C| = 5, |T ype P | = 1. These categories hold for other test requirements (i.e. Nodes, Edges, Edge-pair, etc) as well. Lemma 1. max (|T ype S|, |T ype T |) is a lower bound on the minimum number of Test Paths for Prime Path coverage.

  Prime Paths can be achieved by checking the first and last vertex of every Prime Path. This can be done in O (|P |). For the example graph of Fig. 2, the lower bound for the minimum number of Test Paths for Prime Path coverage = |T ype T | = 3.

Fig. 2 .

 2 Fig. 2. Example Input Graph, G1.

Fig. 3 .

 3 Fig. 3. Transform Graph, G2 of G1.

  15 output G 3 = (V 3 , E 3 ); Algorithm 3 works as follows. For the given transform graph, the cycles are computed using a trivial variant of Algorithm 1. If the graph contains a cycle, any cycle is chosen and reduced to a new vertex. On the resulting graph, the cycles are identified again and the procedure is repeated. The complexity of steps 6 -13 is O (|V 2 |) by assuming that the chosen cycle visits every vertex. Since, V 2 represents the Prime Paths, this complexity can be written as O (|P |). If we assume every Prime Path is of T ype C and reducing one cycle does not impact other Prime Paths, then the complexity of the entire algorithm can be said to be O (|P | * max (|P |, P c )), where P c is the complexity of finding a cycle. After removing all the cycles, the acyclic transform graph is shown in Fig.4.

3 Fig. 4 .

 34 Fig. 4. Creating an acyclic directed graph, G3 from G2.

Fig. 5 .

 5 Fig. 5. Vertex Splitting and flow requirements represented as lower bound; capacity

Algorithm 4 :

 4 over the network G 4 provides a method with a complexity of O (|V 4 | |E 4 | c max ), where c max represents the maximum value of the capacity, C. From Theorem 1, c max = O (|V 4 |). Therefore, the complexity of the method in [4] becomes O |V 4 | 2 |E 4 | . This complexity can be generalized as O |V | 2 |E| . Our work in this paper introduces a novel initialization algorithm (i.e. aspect a)) such that the complexity of computing the minimum flow using the standard decreasing path algorithm becomes O (|V 4 | |E 4 |). This complexity can be generalized to O (|V | |E|). Initialization with a feasible flow Given the graph G 4 = (V 4 , E 4 , L, C), Algorithm 4 places an initial flow such that the flow requirements 1 & 2 are met. Initialization with a feasible flow Input:

2 .

 2 Algorithm 4 ensures flow requirements are met.

|V4| 2 - 1 (

 21 from Theorem 1), the minimum flow will be found in O (|V 4 ||E 4 |). This can be generalized to O (|V ||E|).

Algorithm 5 : 6 r

 56 Decreasing Path Algorithm Input: G 4 = (V 4 , E 4 , L, C), with initial flow Output: minimum flow f and flows on G 4 1 foreach edge(i, j) ∈ E 4 do 2 put (i, j) in E f 4 ; 3 put (j, i) in E b 4 ; l ji = 0; c ji = |V4| 2 -1; 4 end 5 while path, p, exists from s to t using breadth-first-search such that r mn > 0, ∀ (m, n) ∈ p do min = min{r mn , ∀ (m, n) ∈ p}; 7 foreach edge (m, n) ∈ p do 8 if (m, n) ∈ E f 4 then 9 f mn -=r min ; 10 else 11 f mn + = r min ; 12 end 13 f nm = f mn ; 14 end 15 end 16output f = j f sj , G 4 ;The overall complexity of the minimum flow algorithm is the maximum of the complexity between the initialization and the decreasing path algorithm. max (initialization algorithm,decreasing path algorithm) = max (O (|V ||E|) , O (|V ||E|)) = O (|V ||E|) (4) Thus, the complexity of our method of O (|V ||E|) improves upon the complexity of the generic minimum flow algorithm of O |V | 2 |E| .

Algorithm 6 : 7 end 8 while

 678 Identifying minimum Test Paths from minimum flow Input: G 4 = (V 4 , E 4 , L, C), with flow on each edge & minimum flow f Output: All s-t paths, path G1 , on G 1 corresponding to the minimum flow 1 Remove all backward edges of G 4 . Merge vertices of the form {v + , v ++ } into v. Incoming edges of v = incoming edges of v + . Outgoing edges of v = outgoing edges of v ++ . Let the resulting graph be G 3 ; 2 for i = 0 to f do 3 remove all edges from G 3 which have flow of 0; 4 find path, path G3 , from s to t using breadth-first-search; 5 foreach edge(m, n) ∈ path G3 do 6 f mn -= 1 ; path G3 contains a vertex, v G3 c , reduced from a cycle, c do 9 Let the cycle be represented as

j∈

  through the information recorded in Algorithm 3 Step 4; 11 end 12 path G2 = path G3 ; 13 ensure an edge exists between every vertex of path G2 in G 2 ; 14 end 15 foreach path G2 do 16 foreach cycle, c in path G2 do 17 if number of occurrences of c in all paths path G2 > 1 then 18 except the first instance, replace all other instances of c in path G2 with the first vertex of c ; 19 end 20 let path sub = c -first & last vertices of c ; 21 if number of occurrences of path sub in all paths path G2 > 1 then 22 replace c in path G2 with the first vertex of c ; path G2 do 27 path G1 = path G1 ∪ prime path represented by v G2 i ; 28 end 29 path G1 = path G1 ∪ t ; 30 Output path G1 ; 31 end

  A Round Trip path is a Prime Path of T ype C. The test requirement of the Simple Round Trip coverage criterion contains at least one T ype C Prime Path which begins and ends for a given vertex. The test requirement for Complete Round Trip coverage criterion contains all T ype C Prime Paths for a given vertex. Therefore, the Round Trip coverage criteria focuses on a subset of the set of Prime Paths for a given graph. In our formulation, algorithm 1 can be suitably modified to choose the set of Prime Paths needed for the set T R. The minimum number of Test Paths needed for this set of T R is directly obtained by the other algorithms. However, in this case of Round Trip coverage, Lemma 1 will provide a value of 0 as the lower bound since there are no T ype S or T ype T test requirements.

Fig. 6 .

 6 Fig. 6. Test Paths & Execution Time (in ms) over randomly created graphs

Table 1 .

 1 Comparison of our solution against related work

	Solution	Coverage Criteria	Comments
	[2]	Prime Path	Does not attempt to minimize
	[1]	Node Coverage	Minimization in O (|V ||E|)
	[8]	Different structural coverage criteria	In-accuracy in solution. Minimization in O |V | 2 |E|
	[7]	Different structural coverage criteria Heuristic solution (non-optimal)
	Our Work Different structural coverage criteria	Minimization in O (|V ||E|)

  where V 2 is the set of Prime Paths, P = {p 1 , p 2 , . . . , p n } and (p 1 , p 2 ) ∈ E 2 if a path exists from p 1 to p 2 on G 1 such that the path does not include any other Prime Paths (i.e. other than p 1 and p 2 ). 3. The transform graph G 2 is made into an acyclic graph, G 3 . The work in

Table 2 .

 2 Test Paths & Execution Time (in ms) over graphs representing actual software

	Num. of Prime Paths	9 11 27 27 35 38 46 63 69 78 a 93 b
	Num. of Test Paths from Solution in [2] 7 9 14 19 26 22 36 34 49 37 69
	Test Paths' Length from Solution in [2] 46 56 200 181 230 210 426 506 544 675 771
	Num. of Test Paths from our Solution 5 7 11 14 20 12 17 11 41 18 54
	Lower Bound on Num. of Test Paths 5 7 11 14 20 12 8 11 35 18 54
	Test Paths' Length from our Solution 33 42 159 133 223 154 294 385 527 764 1043
	Execution Time of Solution in [2]	2 2 10 2 7 2 5 14 11 6	15
	Execution Time of Algorithm 1	1 1 9 1 6 1 2 12 6	5	12
	Execution Time of Algorithm 2	1 1 21 7 36 13 50 153 63 170 150
	Execution Time of Algorithm 3	1 1 3 2 5 1 8 19 4 13 22
	Execution Time of Algorithm 4 & 5	1 1 2 1 6 1 2 5 6	1	4
	Execution Time of Algorithm 6	1 1 11 4 26 7 21 48 23 38 40
	Total Execution Time of our Solution 5 5 46 15 79 23 83 237 102 227 228

a maps to 71 in results (Table

Table 3 .

 3 Test Paths & Execution Time (in ms) over graphs representing actual software similarly maps to 1024 in results (Table

	Num. of Prime Paths	98 101 122 170 1074 a 1141	1844
	Num. of Test Paths from method in [2] 67 60 80 102 933	954	885
	Test Paths' length from method in [2] 1096 872 1577 1986 27457 37245 19828
	Num. of Test Paths from our Method	41 47 20 42	362	96	102
	Lower Bound on Num. of Test Paths	31 47 20 28	362	65	102
	Test Paths' Length from our Method	967 1152 1541 1789 34733 37358 21482
	Execution Time of Solution in [2]	11 11 14 48 3548	5884	1997
	Execution Time of Algorithm 1	9	9	11 26 2376	4454	748
	Execution Time of Algorithm 2	306 253 1057 1386 634719 1240553 1315738
	Execution Time of Algorithm 3	42 13 79 222 72520 167950 95775
	Execution Time of Algorithm 4 & 5	6	4	1	12	137	19	87
	Execution Time of Algorithm 6	58 71 230 179 42628 106613 242745
	Total Execution Time for our Method 421 350 1378 1825 752380 1519589 1655093

a

We thank Nan Li of[START_REF] Li | Better algorithms to minimize the cost of test paths[END_REF] for sharing the manually created graphs.


Fatma Somaa
email: fatma.somaa@sesame.com.tn

Cédric Adjih
email: cedric.adjih@inria.fr

Inès El Korbi
email: ines.korbi@ensi.rnu.tn

Leila Azouz Saidane
email: leila.saidane@ensi.rnu.tn

A Bayesian Model for Mobility Prediction in Wireless Sensor Networks

Wireless sensor networks (WSN) have specific features such as low transmission range, stringent energy consumption constraints, limited memory and processing power. For this reason, tailored protocols have been proposed, optimizing network protocols with respect to various assumptions: one commonly exploited property of WSN is the stability of the topology due to permanent installation of sensor nodes. However, in some applications, some of the wireless sensor nodes might be mobile, for instance when they are associated with users. In that case, specific extensions of WSN protocols need to be designed. Then a first step is the characterization of nodes' mobility. This is the focus of this article: we propose a general method of mobility estimation for wireless sensor networks. Namely, using a Bayesian framework, we derive a mobility prediction model to estimate the node velocity (starting from no knowledge) from observed events. In this article, we focus on events represented by the most minimal information: mere observation of link duration with neighbors. Simulations illustrate that, even with such limited information, the mobility can be well inferred, and results show the good performance of the method.

I. INTRODUCTION

Wireless sensor networks are integrated in very diverse applications to achieve several purposes such as monitoring, detecting anomalous events and various measurement collection tasks. A key feature of such networks is their facility of deployment and their auto-adaptivity. However, due to the limited capacities of wireless sensor nodes, auto-adaptivity sometimes comes at the price of lesser generality: many WSNs are not integrating routing protocols relying on more complete information such as in mobile ad-hoc networks (MANETs), or wireless mesh networks. For instance, if we consider RPL (IPv6 Routing Protocol for Low power and Lossy Networks) [START_REF] Winter | âeRPL : IPv6 Routing Protocol for Low power and Lossy Networksâe[END_REF], the IETF routing protocol for WSNs, RPL is designed in such a way to adapt to WSN constraints (low energy resource, low memory processing capabilities, etc.). But RPL is still inefficient faced to nodes' mobility and its performance degrades consequently [START_REF] Lee | A Comprehensive Evaluation of RPL under Mobility[END_REF]. Some works [START_REF] Jp | Routing Metrics Used for Path Calculation in Low-Power and Lossy Networks[END_REF], [START_REF] Adjih | A Multi-Level Approach to Link State: ML-OLSR[END_REF] have been proposed for monitoring and detecting neighboring stable links but at the expense of extra resource consumption. Some other schemes [START_REF] Lee | A Comprehensive Evaluation of RPL under Mobility[END_REF], [START_REF] Korbi | Mobility Enhanced RPL for Wireless Sensor Networks[END_REF] have been proposed to enhance the RPL behavior. But their contribution remains limited since they require several changes to native RPL. The resulting schemes, even improving the WSN behavior in case of nodes' mobility, largely deviate the native RPL behavior. In general, WSN nodes are assumed to be static, and performance may degrade if mobile nodes are present without being taken into account. Therefore, first, characterizing node mobility, and second, integrating the mobility into WSN routing protocols is necessary in this scenario. The topic of mobility is explored in this article: we propose a method to automatically detect and estimate the nodes' mobility in WSNs. The key idea of this paper is to accurately predict the sensor nodes' movement (velocity) without pre-knowledge of any mobility information within the sensor node (current position/speed). A straightforward way to derive sensor nodes' mobility is to equip each sensor node with a specific equipment (e.g. GPS -Global Positioning System) to estimate the node's mobility [START_REF] Peng | Distributed collaborative control for industrial automation with wireless sensor and actuator networks[END_REF], [START_REF] Culler | Overview of sensor networks[END_REF], [START_REF] Patwari | Locating the nodes. Cooperative localization in wireless sensor networks[END_REF]. As we could expect, using such techniques are not universally applicable (GPS not embedded for cost reasons, limited GPS coverage, limited GPS precision, . . . ). Other techniques, based on sensor nodes' mobility estimation propose new metrics or new extensions for routing protocols [START_REF] Somov | Supporting smart-city mobility with cognitive internet of things[END_REF], [START_REF] Reina1 | Route duration improvement in wireless sensor and actuator networks based on mobility parameters and flooding control[END_REF], [START_REF] Meng | A Novel Ad hoc Routing Protocol Based on Mobility Prediction[END_REF], [6], sometimes relying on analytical models [START_REF] Jiang | A prediction-based link availability estimation for routing metrics in manets[END_REF], [START_REF] Samar | Link Dynamics and Protocol Design in a Multi-Hop Mobile Environment[END_REF], [START_REF] Ballari | The design of a Bayesian Network for mobility management in Wireless Sensor Networks[END_REF], [START_REF] Korilis | Modèles de Markov[END_REF].

The key difference between our approach and the above mentioned techniques is that, we are deliberately making minimal assumptions and intend to propose the most general solution possible. For instance, sensor nodes have no knowledge of their initial positions/velocities. Nodes discover dynamically existing and broken links. The proposed framework will allow, given an initial random distribution of the sensor nodes' speed, to rapidly converge to the real distribution using Bayesian inference [START_REF] Mitchell | Bayesian Learning[END_REF]. The strength of Bayesian inference is that a unique event (a broken link between two nodes namely U i and U j ) allows refining the velocity/mobility prediction of all U i and U j neighbors. Therefore, the Bayesian inference allows collaborating nodes to quickly converge to a correct mobility prediction despite having initial arbitrary information about their speed values. In this paper, we present the different steps of the proposed Bayesian model to predict the sensor node's mobility. Then we evaluate the convergence of estimated speed values to the real values, through simulations.

The rest of the paper is organized as follows. In Section II, we discuss the literature related to mobility prediction in WSNs. Section III defines our mobility prediction model based on Bayesian inference. In Section IV, we simplify our model (to make it even more suitable for the WSN context) and evaluate its performance. Finally, Section V concludes the paper and present directions for future work.

II. BACKGROUND

In this paper we intend to propose a novel mobility prediction scheme for WSNs based on Bayesian inference [START_REF] Mitchell | Bayesian Learning[END_REF]. As mentioned above, the sensor nodes' mobility in WSNs is a critical issue and if no actions are taken with respect to the sensor nodes' movement, the whole network performance will be considerably altered when the sensors effectively move.

Hence, we propose in this section to review the works in literature related to sensor nodes' mobility and mobility prediction in WSNs. According to the technique used to predict the sensors' movement, the related studies can be classified in three categories: mobility estimation techniques, routing based mobility prediction techniques and mobility prediction analytical models.

A. Mobility estimation techniques

One simple way to estimate the sensor nodes' mobility is to equip them with GPS receivers as proposed in [START_REF] Peng | Distributed collaborative control for industrial automation with wireless sensor and actuator networks[END_REF], [START_REF] Culler | Overview of sensor networks[END_REF]. GPS gives the absolute coordinates of a mobile sensor at the expense of cost and energy.

Moreover GPS may suffer from frequent satellite disconnections in indoor environments. To estimate nodes' mobility, methods uses the Received Signal Strength (RSS) to measure the power of a received signal [START_REF] Patwari | Locating the nodes. Cooperative localization in wireless sensor networks[END_REF] as an indicator of the distance between two nodes. However, these techniques might be computationally expensive (time, CPU and memory). More importantly, they require perfect modelling of the wireless channel: the obtained values will fluctuate according to multipath effects, fading, or limited temporal coherence (due to the presence of obstacles for example or in mobile environment) leading to imprecise values. A common issue in such mobility estimation techniques using sensors (RSSI, ranging devices, . . . ) is that they often rely on some hypothesis (such as perfect models, or at least good characterization of the stochastic component of the measured values, e.g. noise, error, variance). In real implementations, it might happen that some hypothesis are not verified.

B. Routing based mobility prediction techniques

In this paragraph, we discuss the different works using the routing metric to predict the sensor nodes' mobility in wireless networks. A first example is [START_REF] Somov | Supporting smart-city mobility with cognitive internet of things[END_REF], using a link stability metric as a mobility indicator between two nodes. This metric is defined as the number of successive beacons. The mobility prediction is based on the past received values. However, the lost beacon frames used to predict the link stability provide false predicted values due to obstacles, collisions, etc. [START_REF] Meng | A Novel Ad hoc Routing Protocol Based on Mobility Prediction[END_REF] proposes a modified AODV (Ad hoc On demand Distant Vector) routing scheme to predict the neighbors' mobility in MANET (Mobile Ad hoc NETwork by calculating the effective communication distance (the distance between two nodes that allows them to directly communicate). In fact, the update of the effective communication distance is triggered when the real distance between nodes is higher than the estimated distance. This approach has some disadvantages such as requiring a centralized agent with a permanent power or periodic calculation of the received power.

C. Mobility prediction analytical models

In this paragraph, we discuss the analytical works modelling the sensor nodes' mobility in WSNs. Many approaches are based on Markov chain paradigm. In [START_REF] Jiang | A prediction-based link availability estimation for routing metrics in manets[END_REF], links lifetime is considered as the sum of two states' Markov model: the link availability when the velocities of the two nodes keep unchanged during a period T p and the second state represents the case where velocity changes. Accordingly, the probability that the link is broken is divided into two states. This approach requires the knowledge of the nodes' velocity. The mobility prediction model in [START_REF] Korilis | Modèles de Markov[END_REF] is based on the Markov assumption: the future depends only on the present state. Hence, the state must contain sufficient information to get a precise system behavior prediction.

The models presented in [START_REF] Samar | Link Dynamics and Protocol Design in a Multi-Hop Mobile Environment[END_REF] are an inspiration for our work: they characterize the probabilistic properties of observed events (link duration, number of neighbors, . . . ), with respect to node speeds and directions (considered as random variables) under some assumption. However they do not go the extra step of using this as input for estimating the random variables (mobility parameters).

Recently, [START_REF] Ballari | The design of a Bayesian Network for mobility management in Wireless Sensor Networks[END_REF] focus on Bayesian model to predict mobility in WSNs. It uses metadata to predict the network behavior. This approach is very difficult to implement because requires self configured nodes and needs a coordinator to collect the results. In [START_REF] Ballari | The design of a Bayesian Network for mobility management in Wireless Sensor Networks[END_REF], the authors proposed a Bayesian model to predict mobility in ad hoc networks hence helping routing protocols to avoid broadcasting request messages in mobile regions. Therefore, the model classifies the nodes' speed in three categories (low, medium and high) based on two estimated quantities Average Encounter Rate (AER), given the average number of new encounters experienced in a duration T and the node's degree known as the number of one node's neighbors. Two nodes encounter each other when the distance between them becomes smaller than the communication range. Even using Bayesian inference, [START_REF] Ballari | The design of a Bayesian Network for mobility management in Wireless Sensor Networks[END_REF] only gives a rough prediction of nodes' mobility without deriving any accurate information about effective speed values.

III. BAYESIAN MODEL FOR NODE SPEED AND LINK DURATION ESTIMATION

In this section, we present our Bayesian inference framework for the mobility prediction in WSNs. WSNs may contain a certain number of mobile sensor nodes depending on the network deployment context. An accurate prediction of sensor nodes' mobility can obviously aid the network to reactively adapt to such topological changes.

We propose a framework to predict sensor nodes' speed using a Bayesian inference framework [START_REF] Mitchell | Bayesian Learning[END_REF]. In short: a node maintains an estimate of its speed as a distribution (e.g. probability that the speed equals such and such value). This distribution represents the best knownledge/estimate that a node possesses of its own speed (at a given moment). Bayesian inference consists in having sensor nodes to updating their speed estimates with each encountered event. Starting from any given unknown initial velocity distribution, the estimate will be gradually updated towards the actual values, assuming that the speed stays constant.

With Bayesian inference, convergence is ensured hence avoiding non-trivial computational issues we may encounter with some other models [START_REF] Box | Bayesian inference in statistical analysis[END_REF]. Moreover, two additional properties are: implicit robustness, because the inference is constantly refining estimates, thus any noise or errors would fade gradually with further estimates; and extensibility, with the possibility of taking into consideration additional events (for instance, an event "observed variation in accelerometer sensor").

A. Overview and Assumptions

We deliberately consider that sensor nodes have no information about their positions, velocities, speed variation, etc. The only information that allows predicting accurate speed values is the occurrence of the particular events. In this article, we consider the case of events "broken links" caused by sensor nodes' movement (nodes get out of range). We detail a new framework based on Bayesian inference to derive real sensor nodes' speeds upon the occurrence of subsequent events (here, "broken links" events). Hereafter, we present the key assumptions we adopt in the rest of our study:

• Assumption 1: The sensor network is composed of both mobile and fixed nodes. • Assumption 2: Sensor nodes have limited resources and have no information to derive their speed values (GPS, accelerometer, ...). Notice that when such additional source of information are available, they could be easily integrated in the Bayesian inference as additional events. • Assumption 3: Sensor nodes' velocity magnitudes are constant over the time. Sensor nodes can however change direction.

• Assumption 4: We assume that the sensor nodes' directions are independently distributed [START_REF] Grossglauser | Mobility Increases the Capacity of Ad Hoc Wireless Networks[END_REF]. In the following, we introduce the main notations:

• Let E be the particular event representing link duration before break between nodes U 1 and U 2 ; E = { a link between U 1 and U 2 lasted for τ }. We denote p τ (t) the associated probability density function (pdf) of link duration between two given nodes in the network. • We also define p i (v i ), the pdf of the node

U i speed. p i (v i )
is called the prior speed distribution of the node U i (prior to the event E).

• Similarily, we have p i,j (v i , v j ) the prior joint speed distribution. • We also use the notation p + ... (...) for all the posterior distributions (after the event E).

B. General Bayesian Inference

Exploiting the network dynamics, Bayesian inference allows updating posterior sensor nodes speed distributions using Bayes' rule. We consider a two nodes' scenario U 1 and U 2 having respective speeds v 1 and v 2 , which were neighbor, and just observed the event E = their link has broken. Then, using Bayes' rule, we have:

P (U 1 has a speed v 1 and U 2 has a speed v 2 | event E) (1)
= P (event E |U 1 has a speed v 1 and U 2 has a speed v 2 ) × P (U 1 has a speed v 1 and U 2 has a speed v 2 ) P r(E)

where P r(E) is the event E probability. With the model notations given in paragraph III-A, the posterior speed joint distribution of v 1 and v 2 , resulting from the prior joint distribution p 1,2 (v 1 , v 2 ) and the observed link broken event E, is:

p + 1,2 (v 1 , v 2 |E) = 1 P r(E) p τ (E|v 1 , v 2 )p 1,2 (v 1 , v 2 ) (2)
Moreover, using the assumption 4, related to the independence of speeds v 1 and v 2 , we have

p 1,2 (v 1 , v 2 ) = p 1 (v 1 ) × p 2 (v 2 ) (3)
As common in the Bayesian inference, P r(E) is a normalizing constant: it can be ignored, under condition to later normalize posterior distributions (e.g. p = 1). After this step, the independence property between v 1 and v 2 may not be still valid after inference, especially if nodes become later neighbors again, but as an approximation, we will ignore it, and use only the definition:

p + 1 (v 1 |E) = +∞ v2=0 p + 1,2 (v 1 , v 2 |E)dv 2 (4)
From equations ( 2), ( 3) and ( 4) we obtain:

p + 1 (v 1 |E) ∝ p 1 (v 1 ) ∞ v2=0 p τ (t|v 1 , v 2 )p 2 (v 2 )dv 2 (5)

C. Conditional Link Duration Distribution

In this article, the events considered are link breakage, and from inference in equation ( 5), deriving posterior speed distributions depend on the quantity p τ (t|v 1 , v 2 ): the probability that a link lasts for a duration t given prior speed distributions v 1 and v 2 . Link duration is a random variable because the angle between the nodes is not known (supposed uniform in [0, 2π]). To evaluate the link duration, a good starting point is [START_REF] Samar | On the behavior of communication links of a node in a multi-hop mobile environment[END_REF]. Other studies focused on link dynamics using different approaches (GPS [START_REF] Su | Mobility Prediction and Routing in Ad Hoc Wireless Networks[END_REF], empirical residual link lifetime [START_REF] Gerharz | Link Stability in Mobile Wireless Ad Hoc Networks[END_REF], etc.). Despite its accuracy, [START_REF] Samar | On the behavior of communication links of a node in a multi-hop mobile environment[END_REF] introduces two relative angles α and β to derive links' duration whereas only the "minimum distance" between the two nodes and the absolute value of the relative speed are needed. Hence, we propose here to derive a simple expression of link duration using the property: the "minimum distance during their encounter" between two nodes (that get in range of each other) is uniformly distributed in [-R, R] [START_REF] Samar | On the behavior of communication links of a node in a multi-hop mobile environment[END_REF].

We first start with a normalized/unit parameters assuming that v = 1 and the radio range R = 1. We denote by p τ (t) the pdf of link duration with unit parameters. Let U 1 and U 2 be the nodes of the link (U 1 has speed 0, U 2 has speed v). To simplify the notation, without loss of generality, we assume that U 2 is moving horizontally. Let y be the closest distance between U 1 and U 2 when they are in the communication range of each other. We assume that y is an instance of a random variable Y which is uniformly distributed in [0, 1] with density p * Y (y) = 1. The relation between Y and the duration t is given by t = f (y) = 2 1 -y 2 . As in [START_REF] Vasanthi | A Detailed Study of Mobility Models in Wireless Sensor Networks[END_REF], we define:

p τ (t) = | 1 f -1 (t)) |p Y (f -1 (t)) = |1/f -1 (t))| (6)
After calculating f (x) and f -1 (x), we get:

p τ (t) = t 2 √ 4 -t 2 (7)
Now, if we remove the assumption about v and R, we have

τ actual = R v τ normalized .
Thus we apply the change of variable

τ = g(τ ) = R v τ p τ (t) = 1 g -1 (t)) p τ (g -1 (t)) = v R p τ ( v R t) (8)
This value is only defined when 0 ≤ v R t < 2, in other words t < 2R v . In the following, we assume that R = 1 and v will be expressed in the following units: "radio-range per unit time" (instead of "unit distance per unit time"). Then:

p τ (t) = vp τ (vt) (9)
The speeds v 1 and v 2 result in a relative speed

v equal to v = h(θ) = v 2 1 + v 2 2 -2v 1 v 2 cos(θ)
, where θ is the angle between the nodes and is uniformly distributed in [0, 2π]. Using the same computations as in ( 6) and ( 8), we have for

v ∈]|v 1 -v 2 |, v 1 + v 2 [: p V (v|v 1 , v 2 ) = 2| 1 h -1 (v)) p θ (h -1 (v))| = 2v π 4v 2 1 v 2 2 -(v 2 1 + v 2 2 -v 2 ) 2 (10)
where

h (θ) = v1v2sin(θ) √ v 2 1 +v 2 2 -2v1v2 cos(θ)
and

h -1 (v) = arccos ( v 2 1 +v 2 2 -v 2 2v1v2
) in the range [0, θ] and another one in the range [π, 2π]: 2π -h -1 (v).

We can then express the conditional probability p τ (t|v 1 , v 2 ) that a link lasts for a duration τ when nodes have speeds v 1 and v 2 . Notice that:

• The minimum possible relative speed is: |v 1 -v 2 | (two nodes in the same direction). • The maximum possible relative speed is: v 1 + v 2 (two nodes crossing each other in the opposite direction).

• The maximum possible relative speed that could result in a link of duration t,

is v = 2 t . We denote v (v 1 , v 2 , t) = min(v 1 + v 2 , 2
t ) the maximum relative speed given v 1 and v 2 that could possibly yield a link of duration t.

p τ (t|v 1 , v 2 ) = 0 if 2 |v 1 -v 2 |
< t, otherwise :

p τ (t|v 1 , v 2 ) = v p τ (t|v)p V (v|v 1 , v 2 )dv = v=v (v1,v2,t) v=|v1-v2| v 2 t 2 √ 4 -v 2 t 2 2v π 4v 2 1 v 2 2 -(v 2 1 + v 2 2 -v 2 ) 2 dv = v=v (v1,v2,t) v=|v1-v2| v 3 t π (4 -v 2 t 2 )(4v 2 1 v 2 2 -(v 2 1 + v 2 2 -v 2 ) 2 ) dv (11)
The expression [START_REF] Patwari | Locating the nodes. Cooperative localization in wireless sensor networks[END_REF] can be simplified through use of elliptic integrals [START_REF] Korilis | Modèles de Markov[END_REF]. This also allows faster computation for evaluating [START_REF] Patwari | Locating the nodes. Cooperative localization in wireless sensor networks[END_REF]. We introduce the following quantities:

α = (v 1 v 2 ) 2 , β * = (v 1 + v 2 ) 2 , γ * = 4 t 2 , β = min(β * , γ *
) and γ = max(β * , γ * ). Then, if β ≤ α, then p(t|v 1 , v 2 ) = 0, and otherwise:

p τ (t|v 1 , v 2 ) = (w 2 + α)K(k) -w 2 E(k) πw (12)
where

w = √ γ -α, k = √ β-α w
, E is the complete integral of the second kind and K is the complete integral of the first kind in Jacobi form [START_REF] Korilis | Modèles de Markov[END_REF].

D. The Bayesian Inference Implementation

To implement the Bayesian inference model on the sensor network, we consider that sensor nodes periodically exchange Hello beacons to detect links' expiration. Then Bayesian inference can be performed with discretized quantities: each node U i maintains a vector V i of n discrete velocity values representing its discretized pdf and initialized it with random distribution. Upon the occurrence of a link expiration event E between two nodes U 1 and U 2 , the node

U 1 evaluates the matrix M (τ E ) = p τ (τ E |v 1 , v 2 ) for all possible values of v 1 and v 2 , p τ (τ E |v 1 , v 2
) is given by equation [START_REF] Patwari | Locating the nodes. Cooperative localization in wireless sensor networks[END_REF]. Then the posterior is given by vector V + 1 is computed as follows:

V + 1 ∝ V 1 • (M (v E )V 2 ) ( 13
)
where • is the element-wise product (Hadamard product). V + 1 is obtained by renormalizing the right hand of the expression. The node U 2 performs the same evaluation steps. Once U 1 computed its posterior distribution V + 1 , it broadcasts it to its neighbors, hence to be considered int the next velocity estimation round when another "broken link" event occurs. To evaluate the effectiveness of the Bayesian inference with such limited information, we implement Bayesian inference (with python) and test it on a simple scenario with 2 nodes, one with speed= 1 (expressed in unit distance per unit time, with unit distance defined by radio range R = 1), and one with speed= 2, with random (uniform) changes of direction between encounter. Initially, all the nodes are unaware of their real velocity values and use an arbitrary prior distribution (as common in Bayesian inference). Figure 1 represents the distribution of the velocity v 1 of one node: iteration number increases corresponding to encounters (and events of link breakage) with the other node. As illustrated, after 100 events, the distribution of the velocity is concentrated around its actual value 1, indicating excellent convergence of the estimate. Despite its accuracy, the model proposed here requires exchanging a large amount of data, upon a "link expiration" event, corresponding to posterior link velocity estimation vectors. The overhead introduced by this exchanged information may largely degrade the network performance especially for high mobility scenarios. A simplification of the Bayesian inference model is detailed in the next section.

IV. SIMPLIFIED MODEL

A frequent exchange of posterior speed vectors computed by the Bayesian inference model may result in a non negligible overhead, hence increasing energy consumption in the network. Therefore, to reduce the amount of data sent upon the occurrence of expiration links events, we propose to model speed distributions as Gaussian distributions. Thus we send mean and standard deviation of (posterior) speed distributions. Receivers will interpret them as parameters of Gaussian distributions. Hence, once a node U i computes its posterior speed distribution vector V + i , then it evaluates the mean µ V + i and the standard deviation σ V + i values and send them to its neighbors. The receiver reconstructs the pdf of the posterior distribution as:

p + vi (v i ) = 1 σ V + i √ 2π e -1 2 vi-µ V + i σ V + i 2 (14)
From equation ( 14 Moreover, to show the quick convergence of the speed estimation process, we depict in Figure 3 the average estimated speed values as a function of the iteration number. We also depict speed deviation curves given by (average speed +/standard variation). We notice, in Figure 3, that the gap between curves decreases as the iteration number increases. This behavior highlights the fact that the predicted velocity converges to the real one. The slower speed convergence is caused by the choice of the worst predicted values at each iteration (the minimum and the maximum values). Figure 4 illustrates the scalability of A further validation step is done in Figures 5 and6 where realistic mobility models are used to derive link durations. Mobility scenarios are generated using the BonnMotion tool [START_REF] Aschenbruck | BonnMotion -a Mobility Scenario Generation and Analysis Tool[END_REF]. Analysis of the mobility scenario allows deriving links' duration values. These durations are therefore injected in the Bayesian model to predict nodes' velocities.

In Figure 5, we use the Random Waypoint (RWP) model to generate movement traces of two nodes with real velocity values equal to 0.9 and 1.8. Figure 5 shows that with real mobility scenario, the Bayesian inference model converges after the given iteration (encounter) number 100. The same result is obtained in Figure 6 where the Random Direction (RD) mobility model is used and for sensor nodes speeds equal to 0.7 and 2.

We can therefore conclude that all the performance results showed the efficiency of the Bayesian inference in predicting real sensor nodes' speed values and its convergence in a timely manner given unknown initial speeds; even with as minimal information as observed link durations.

V. CONCLUSIONS AND FUTURE WORK

In this paper, we proposed a new mobility prediction model for WSNs based on a Bayesian inference approach. We discussed the existing solutions in MANETs and WSNs related to the nodes' mobility estimation. We then proposed a Bayesian inference framework that derives sensor nodes' velocity only based on the occurrence of particular "link expiration" events. Therefore, we detailed the different steps of our mobility prediction model and simplified the model expressions hence to be easily implemented in a sensor network context. Performance evaluation results show the accuracy of the Bayesian Inference framework and its convergence in a timely manner.

In our future work, we intend to use the Bayesian inference model in the RPL protocol [START_REF] Aschenbruck | BonnMotion -a Mobility Scenario Generation and Analysis Tool[END_REF] to derive a new routing metric adapted to mobile sensor networks.

Fig. 1 .

 1 Fig. 1. Bayesian model validation

  ), we derive discretized values of speed distribution p + vi (v i ). The simplified model is validated (in Python) using the same simulation procedure as in Figure 1. Mobile nodes may have one of the 5 velocities: 1, 1.5, 2, 3 and 4. After 100 iterations, the final speed density curves are presented in Figure 2. The Figure shows that the estimated velocity values are very close to the real ones.

Fig. 2 .

 2 Fig. 2. The simplified model using 5 velocities

Fig. 3 .

 3 Fig. 3. Velocity behavior as a function of the iteration number In Figure 4, we consider a large scale scenario with 50 mobile nodes and two velocity values (1 and 2 -half of the nodes each). We depict in Figure 4(a) (respectively in Figure 4(b)) the estimated average, maximum and minimum velocities of all mobile nodes with real speed 1 (respectively 2). Figures 4(a) and 4(b) show that all mobile nodes' predicted velocities (average, maximum and minimum) converge to real speed values 1 respectivly 2.The slower speed convergence is caused by the choice of the worst predicted values at each iteration (the minimum and the maximum values). Figure4illustrates the scalability of

(a) Nodes with velocity 1 (b) Nodes with velocity 2 Fig. 4 .

 124 Fig. 4. Velocity convergence of the large scale mobility scenario

  (a) final velocity values (b) intermediate velocity values

Fig. 5 .

 5 Fig. 5. Velocity convergence using the Random Waypoint (RWP) model


Rainer Schmidberger

Well-Defined Coverage Metrics for the Glass Box Test

Keywords: Glass Box Test, White Box Test, Structural Test, coverage testing, coverage tools 0 % EclEmma Version: 2.2.1 Instruction: 56, 7 % Line: 63, 6 % Block: 50, 0 % eCobertura 0 % CodePro Version: 7.1.0 Instruction: 57, 7 % Line: 58, 5 % Block: 60, 6 % Rational Application Developer Version 9.0.0 Line: 67, 0

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

In industrial practice testing is the technique most widely used to find errors in programs or to demonstrate a certain quality of a program. Accordingly, companies spend a significant part of their project budgets on testing, which in many cases does not achieve the desired quality -(too) many serious defects remain undetected. As a starting point for the improvement of the test, the Glass Box Test (GBT) can be used, also known as White Box Test or Structural Test, that shows which parts of the program under test have, or have not, been executed. This degree of execution is called coverage. It can be used as a test completion criterion or as input for developing test cases [START_REF] Ammann | Coverage Criteria for Logical Expressions[END_REF][START_REF] Beizer | Software Testing Techniques[END_REF][START_REF] Dupuy | An empirical evaluation of the MC/DC coverage criterion on the HETE-2 satellite software[END_REF][START_REF] Myers | Art of Software Testing[END_REF][START_REF] Dahl | Structured Programming[END_REF]. Many GBT tools are available for almost any programming language. Industry standards for safety-critical software require a very high or even complete coverage (e.g. [START_REF] Dupuy | An empirical evaluation of the MC/DC coverage criterion on the HETE-2 satellite software[END_REF][START_REF]Functional safety of electrical/electronic/programable electronic (E/E/PE) safety related systems[END_REF]). Empirical studies clearly indicate that higher GBT coverage correlates with lower post-release defect density [START_REF] Andrews | Using Mutation Analysis for Assessing and Comparing Testing Coverage Criteria[END_REF][START_REF] Berner | Enhancing Software Testing by Judicious Use of Code Coverage Information[END_REF][START_REF] Mockus | Test coverage and post-verification defects: A multiple case study[END_REF]. At first glance, the GBT seems to be a well-established and mature testing technique, but it is worth having a closer look at the underlying models and metrics.

Fig. 1. Ambiguities in CFG modelling

What is more severe than these details is the fact that there is no representation of exception handling in the CFG. But exception handling is an important part of modern programming languages. In addition, the CFG does not provide any means for handling the GBT-relevant expressions such as the conditional expression or the short-circuit operations of Boolean expressions [START_REF]Software Verification Tools Assessment Study[END_REF]. As a result, it is not possible to model compound Boolean operations for handling logic-based coverage criteria like term coverage [19] or MC/DC [START_REF] Ammann | Coverage Criteria for Logical Expressions[END_REF]19]. As a consequence of this unsatisfactory model and metric definition, the most important GBT tools for Java [START_REF] Zhu | Software unit test coverage and adequacy[END_REF] show completely different coverage results (Table 1) for the same execution of a given 45-statement reference program [START_REF] Yang | A Survey of Coverage-Based Testing Tools[END_REF]. Furthermore, those tools are not based on well-defined metrics. (What does line coverage or instruction coverage mean?) While these differences can be explained partly by the different instrumentation techniques of the GBT tools, there is no "reference" which the tool developer could use as a specification and for comparing results.  The model forms the basis on which both the popular control-flow based metrics as and the logic and conditional expression based metrics can be defined.  The model supports exception handling and provides an easy and clear definition of how coverage metrics are applied to exception handling.  There is an easy and precise transformation rule to transform real programs into the model.  The model does not depend on any particular programming language. An algorithm implemented in different programming languages should have the same model representation.  The model specifies how to place the probes that count the execution of the relevant code items in the instrumented program.

Such a GBT model is now presented in three steps:

1. Definition of a primitive language (RPR = Reduced Program Representation) which is reduced to the GBT-relevant aspects of the real programming languages. It provides control flow, exception handling, and expressions. These GBT-relevant aspects are mapped in so-called GBT items such as statements, statement blocks, and Boolean or conditional expressions. This abstraction has two goals: First, to make metric definition easier because the metrics are based on only a few distinct elements. And, second, to keep the model independent of a particular programming language.

2. Definition of the execution semantics using Petri nets. This part of the model precisely defines the control flow inside and between the GBT items for both normal and abrupt completion. The Petri net model specifies precisely how the original program has to be instrumented.

3. Definition of the coverage metrics based on the Petri nets.

The Reduced Program Representation (RPR)

RPR defines all GBT-relevant aspects of the original program code and suppresses all irrelevant attributes like numerical expressions or design elements such as inheritance, interface or visibility. RPR is subdivided into two parts: First, the control flow part which covers the typical control flow statements like decision, loop, and switch statement. In the second part the GBT-relevant expressions such as the conditional expression or Boolean terms are described. The control structures of RPR correspond to the principles of structured programming as described by Dahl, Dijkstra, and Hoare [START_REF] Dahl | Structured Programming[END_REF]. In addition, a try-statement covers the typical exception handling of modern languages. Program represents a method or procedure. The StatementBlock subsumes all blocks and branches like then or else blocks, method blocks, and catch blocks.

Statement and StatementBlock are given a unique identifier that does not exist in the original program. This identifier builds the reference between the static model and the dynamically recorded protocol of the executed items. These identifiers are automatically generated.

The meta syntax of the following grammar is easy to understand: terminals are quoted, "empty" is the empty sequence of terminals, and each production ends with a dot.

Program

= Identifier StatementBlock.

StatementBlock

= Identifier "{" StatementList "}".

StatementList = Statement StatementList | empty. Statement = Identifier ( PrimitiveStatement | TerminateStatement | WhileStatement | IfStatement | SwitchStatement | TryStatement )
SubExpressions.

IfStatement

= "if" "(" BoolExpression ")"

"then" StatementBlock "else" StatementBlock.

WhileStatement

= "while" "(" BoolExpression ")"

StatementBlock. The decision of an if statement and the loop condition of a while statement are Boolean values, and therefore, they are represented in the model to be used in logic-based coverage metrics such as MC/DC or term coverage. In contrast, the numerical expression of the switch statement and the exception types in the catch part of the try statements are not represented because no coverage metric is based on these types. The following second part of the language covers the Boolean and conditional expressions:

SwitchStatement

Expression = BoolExpression | ConditionalExpression. BoolExpression = Identifier ( Condition | CompoundExpression ).

Condition

= "expr" SubExpressions. CompoundExpression = ("andThen"|"orElse"|"and"|"or") "(" BoolExpression ","

BoolExpression ")".

ConditionalExpression = Identifier BoolExpression "?"

SubExpressions ":" SubExpressions ).

SubExpressions = "[" ExpressionList "]". ExpressionList = Expression ";" ExpressionList | empty.
Because BoolExpression and ConditionalExpression are referenced in metric definitions, they have an identifier like the Statement and StatementBlock. The definition of Condition complies with [START_REF]Software Verification Tools Assessment Study[END_REF]: "A Boolean expression containing no Boolean operators". The compound Boolean expressions like "A orElse B" are handled by Com-poundExpression. For this, the model includes the (binary) tree structure of the Boolean expression's derivation tree. Thanks to the distinction between the operands and and andThen, the so-called short-circuit behavior can be applied to the GBT metrics. The SubExpressions are used to handle GBT-relevant expressions that are embedded in a primitive expression or statement. For example, let us consider the following Java expression:

A && f(B && C)
According to the definition of Condition, the complete term f(…) is a (primitive) condition. In order not to "lose" the embedded expression B && C, it is handled as an element of the embedded SubExpressions of the condition f(…). For determining expression-based metrics like MC/DC, these embedded expressions are also taken into consideration.

In the following example, a factorial function is transferred from Java into RPR. The unique identifiers are built with "S" for statements, "B" for statement blocks and "E" for expressions, followed by an ascending number.

Java RPR int factorial(int n) { if(n < 0 || n > MAX) { return -1; } int result = 1; while (n > 1) { result *= n; P1 B1 { S1 if( E1 orElse(E2 expr [], E3 expr []) ) then B2 { S2 return [] } else B3 { } [] S3 stmt [] S4 while(E4 expr []) B4 { S5 stmt [] n--; } return result; } S6 stmt [] } [] S7 return [] }
One major advantage of RPR is that the transformation of a given real language into the model can be clearly defined by mapping the right sides of the grammar productions. The mapping of a Java if statement, for example, into the model language can be described is as follows:

Java RPR "if" "(" Expression ")" Statement [ "else" Statement ] "if" "(" BoolExpression ")" "then" StatementBlock "else" StatementBlock
It is easy to see that the Java "statements" in the then and else parts are mapped into statement blocks in the GBT model. In addition, the else part in Java is optional while the else part in the GBT model is not. If an if statement in the original program has no else block, it is added as an empty block in the GBT model.

Execution semantics

Every (primitive) GBT item such as a primitive statement or a primitive Boolean expression is described as a place-bordered and token-preserving Petri (sub)net called GBT model net (or short: model net). The model net of a primitive statement is shown in Fig. 2, the model net of the primitive Boolean expression in Fig. 3 on the left side.

Loosely speaking, a model net is a Petri net with distinguished input and output places. Each model net has exactly one input place and one or more output places for normal and abrupt completion. The input place has no input transition relative to the model (sub)net. The output places have no output transition, respectively. In Fig. 2, Fig. 3, and Fig. 4 these input and output places are located on the dashed border line of the GBT item. The initial marking of a model net has exactly one token in the input place while all other places are empty. Due to the token-preserving property the model net's end marking has exactly one token in one of the net's output places.

Because all model nets are place-bordered and token-preserving, they can be abstracted into both sub nets, which are reduced to the border places and super places [START_REF] Reisig | A Primer in Petri Net Design[END_REF]. Fig. 2 shows this abstraction of a statement's model net. The abstractions are used for theoretical net analysis like the reachability analysis as well as for describing the compound model nets of the complex GBT items.

In Fig. 2 the conflict in the model net between the transitions t ENormal and t EAbrupt and their common input place s E models the non-determinism of the statement's execution behavior, in Fig. 3, between the three transitions t EFalse , t ETrue , and t EAbrupt of a Boolean Expression): On the basis of the model net, it is not decidable whether a statement or expression completes abruptly or which Boolean result the real expression returns. But this execution behavior can be observed in the program under test by adding so-called probes to the program code. Fig. 3 shows this connection between the instrumented program code of a GBT item and its corresponding model net: The execution area of the model net abstracts the statically undecidable behavior of the real program's expression or statement. The places s CIn , s CT , s CF and s CA abstract the execution counters of the program under test and build a specification for the source code's instrumentation.

Instrumented program code Entry area

Execution area

Exit area

The example of Fig. 3 shows the instrumentation technique used by the GBT tool CodeCover [START_REF] Hanussek | CodeCover -Glass Box Testing Tool, Design, Student Project "OST-WeST[END_REF][START_REF] Starzmann | CodeCover -Glass Box Testing Tool, Specification, Student Project "OST-WeST[END_REF][START_REF]CodeCover Homepage[END_REF]. In order to avoid additional method invocations, increment expressions using the so-called shortcut semantics "surround" the original expression. Details about this instrumentation can be found in [START_REF] Starzmann | CodeCover -Glass Box Testing Tool, Specification, Student Project "OST-WeST[END_REF].

While the values of the "not-abrupt" execution counters c In , c T and c F directly determine the markings of the model nets corresponding counter places, the value of the counter place for abrupt completion is not given by an instrumented counter. But due to the mathematically sound model net, after reaching a final marking, theese counter place markings can be derived:

| M(s CA ) | = | M( s CIn ) | -| M(s CT ) | -| M(s CF ) |

In the model net of the primitive expression in Fig. 3 the proof is easy to see, for the more complex items the proof can be provided by using the Petri net's reachability analysis. Also by using the reachability analysis for all model nets of the various GBT items it can be proven that each (sub-)net is token-preserving and, as a consequence for each firing sequence starting from the initial marking a final marking is reached with exactly one token in one of the output places.

In contrast to the primitive GBT items the complex GBT items contain other GBT items as part of their own structure. E. g. an if statement contains a Boolean decision and a then and else statement block. Fig. 4 shows the model net of such an if statement. Parts of this model net are embedded model (sub)nets of the embedded GBTitems which are abstracted into place-bordered boxes. As already described, an important aspect of the model net is that there is a formal basis for the execution counters which have been generally used since the early beginnings of coverage testing [START_REF] Mockus | Test coverage and post-verification defects: A multiple case study[END_REF]. The net model provides both a precise placement for the counters for normal completion and a (sound) basis for calculating counters for abrupt completion. As a result, the execution state of a GBT item A for a given test case t -"A is executed by test case t at least once"can now be defined:

exe(A, t)  | M(s CIn (A)) | > 0
This ability to report the execution of a GBT item for a particular test case (and not only for the entire test suite) is called "test-case selective GBT". While most GBT metrics are defined for the entire test suite, many useful GBT evaluations like test suite reduction, selective regression test and development of new test cases require the test-case selective GBT.

Metric definition

On the basis of the GBT items and their execution property we can now clearly and precisely define the GBT metrics. E. g. the statement coverage for an execution of a given program P can be defined as the proportion of executed statements; stmts(P) is defined as the set of all statements of P. The precise definition of "statement" is given by the grammar of the model language.

A  exeStmts (P, T)  A  stmts(P)   t  T : exe(A, t)

While the definition of statement and statement coverage is relatively clear, branch coverage does not have a precise common definition within the testing community. In general, two interpretations of "branch" exist in the literature [START_REF] Ammann | Coverage Criteria for Logical Expressions[END_REF][START_REF] Beizer | Software Testing Techniques[END_REF][START_REF] Mockus | Test coverage and post-verification defects: A multiple case study[END_REF]:

1. Every edge of the CFG forms a branch 2. Only those edges of the CFG are branches whose origin is a node with more than one outgoing edge.

Following the more intuitive definition no. 2, we define those so-called fork statements that have the described forking characteristics like if statements, while statements, or switch statements. For every fork statement S, we define a weight w(S) , which is the number of forking branches and an execution value e(S, T) with 0 ≤ e(S, T) ≤ w(S), which is the number of executed branches for S with a test suite T. Thus, the branch coverage is defined as follows:

S  forkStmts (P)  S is a statement with forking branches

∑  ∑ 
For some good reasons we also include the try statement in the forking statements, even though there is no distinct forking point. Otherwise, it would be possible to achieve full branch coverage without executing the catch blocks. In addition to the branch coverage we propose block coverage which defines the degree to which statement blocks are executed, similar to the statement coverage. A statement block is defined within RPR and e. g. is a then or else block of an if statement, a procedure body, or a catch block. Again, P is a program and T is a test suite.

B  exeBlocks (P, T)  B  blocks(P)   t  T : exe(B, t)

Generally, block and branch coverage are very similar because nearly all branches flow into a statement block and vice versa. A difference exists in the while statement where the branch that leaves the loop does not lead to a statement block. The procedure body constitutes a statement block but is no branch. Compared to the branch coverage, the block coverage has some practical advantages:  The definition is easier and hence the understanding for the tester and the implementation in a GBT tool are easier.  Unlike branches, statement blocks have a concrete representation in the program code. This makes the visualization of the coverage in the code easier and clearer.  For block coverage, it is clear that catch blocks are taken into account, while most definitions of branch coverage do not address exception handling.

Some other coverage metrics which address control flow in expressions are described in [START_REF] Schmidberger | Wohldefinierte Überdeckungsmetriken für den Glass-Box-Test[END_REF].

Related Work

Most of the coverage metrics have their beginning in Myers' book [START_REF] Myers | Art of Software Testing[END_REF] and in Huang's article [START_REF] Huang | An Approach to Program Testing[END_REF]. While there is a lot of work using the CFG for coverage testing topics, there is only little attention from the testing community to the CFG's disadvantages described in Section 1. In [START_REF]Software considerations in airborne systems and equipment certification[END_REF] Binder describes a GBT model based on "code segments" which covers both (traditional) control flow and control flow in expressions. But he does not present this model in detail and does not develop a theory based on it. Ammann, Offutt, and Hong develop a theory for logic expressions in [START_REF] Ammann | Coverage Criteria for Logical Expressions[END_REF], but do not cover control flow or GBT-relevant expressions like the conditional expression. Zhu, Hall, and May shortly cover the topic of transformation (structured) program code into a CFG, but do not develop a GBT-language like the RPR. A de-tailed coverage tool investigation is conducted in [START_REF]Software Verification Tools Assessment Study[END_REF]. The authors develop a test suite to test whether the performance of a structural coverage analysis tool is consistent with the structural coverage objectives in DO-178B [START_REF] Reisig | A Primer in Petri Net Design[END_REF]. While the authors describe a complete set of test cases concerning control flow, control flow in expression, and logic expressions, they do not develop a model that "abstracts" the given test cases.

Lui et al. define in [23] coverage metrics based on Petri nets in the context of workflow applications. Comparable to this work the authors combine predefined subnets, but their scope is limited on the workflow aspects.

CodeCover

CodeCover is an open-source GBT tool that was initially developed 2008 in a student project at the University of Stuttgart. More information about that project is available in [START_REF] Hanussek | CodeCover -Glass Box Testing Tool, Design, Student Project "OST-WeST[END_REF][START_REF] Starzmann | CodeCover -Glass Box Testing Tool, Specification, Student Project "OST-WeST[END_REF]. Although stable releases have been available since 2008, CodeCover is still being extended and improved. Many enhancements have been implemented over the last years. CodeCover was developed to support both relatively small student projects and large industrial projects. For small projects, CodeCover provides an easy-to-use Eclipse integration. For larger projects, CodeCover can be used with the popular "Apache Ant" build tool or in batch mode. All information about installation and usage can be obtained from the CodeCover web page [START_REF]CodeCover Homepage[END_REF]. Currently, CodeCover supports the languages Java, C and COBOL. The GBT metrics provided are the controlflow based metrics introduced in Section 2, the loop coverage, conditional expression coverage, and term coverage [19], which is very similar to MC/DC.

User Interface

The easiest way to use CodeCover for Java programs is using the Eclipse integration. A typical picture of the CodeCover-Eclipse user interface is shown in Fig. 5.

To use CodeCover in an existing Java project only the following three steps must be performed: 1. Open "Properties" and select the CodeCover page. The desired GBT metrics can be selected here. 2. In "Project Explorer" select the packages or classes to be included in the GBT evaluation. Open popup menu and select "Use For Coverage Measurement". 3. If JUnit tests are used, run the test cases with "CodeCover Measurement for JUnit", otherwise open the "Run Configurations" and select the CodeCover dialog. Select "Run with CodeCover".

Instrumentation and data flow

CodeCover works with so-called source-code instrumentation, where the execution counters for the GBT items are added into the program's source code. Fig. 6 shows the activities and artifacts which are visible for a tester using the CodeCover batch interface. The model representation of the program code is stored in a so-called Test-SessionContainer (TSC). With the instrumentation for statement, block, branch, loop and term coverage, the compiled Java files are almost twice as large as before. For Java programs in practice, this "application blowup" usually is no problem. For C programs running on a micro controller, such growth is usually a problem and must be considered. After running the test cases of the entire test suite, the GBT protocol is added to the TSC. All GBT evaluations are based on the TSC.

Test case selective GBT

Beyond the functionality that most GBT tools offer, CodeCover can analyze the execution of individual test cases. In Fig. 7 ("Test Sessions") all the test cases of the entire test suite are listed. For a JUnit test, the identifiers of the test cases are derived from the JUnit test case names. Four test cases are executed but the user has selected only one test case ("fooTest:test1"). In this case the coverage visualization and summary report are generated only for this selected test case. Using this, the execution of a particular test case can be visualized. CodeCover can also list those test cases that executed an item the user selected by putting the cursor in the code area of the item. These test cases are listed in the view "Pick Test Cases" (Fig. 8). This function that is not found in other test tools provides useful information about the execution behaviour of the program under test.

Conclusion

To date, most GBT metrics are defined either intuitively or based on the CFG. In the approach described above, the GBT metrics are precisely defined using a notation (RPR) which is applicable to a large class of programming languages. Expressions and exception handling are well integrated. Based on this model, the popular metrics are precisely defined. The tool CodeCover is an implementation that strictly follows these definitions.

When new GBT metrics are introduced, RPR can easily be extended to support the collection of these metrics. An exampleand a topic for future workare polymor-phic expressions of object-oriented languages whose behavior is similar to that of switch statements.

  and exit nodes part of the CFG? Does the if statement have a distinct end node? Does the while statement have a distinct end node?

Fig. 2 .

 2 Fig. 2. (Petri)-model net for a primitive statement

Fig. 3 .

 3 Fig. 3. (Petri)-model net for a primitive Boolean expression

Fig. 4 .

 4 Fig. 4. (Petri)-model net for an if statement

Fig. 5 .Fig. 6 .

 56 Fig. 5. CodeCover Eclipse integration

Fig. 7 .

 7 Fig. 7. CodeCover view "Test Sessions"

Fig. 8 .

 8 Fig. 8. List of test cases that have executed a particular item

Acknowledgements

I would like to thank Prof. Jochen Ludewig for his valuable support and advice, as well as Kornelia Kuhle and the anonymous reviewers for their comments.